Regularization and Semi-supervised Learning on Large Graphs

By Mikhail Belkin, Irina Matveeva, Partha Niyogi. Annual Conference Computational Learning Theory, 2004

633 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics

View Paper: https://www.semanticscholar.org/paper/c5c6ea2f23fe8d3e986c4c99e83a90c204538619

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

Citations in the corpus

Semi-supervised time series classification (2006, methodology): “After the graph is constructed, several approaches can be used, such as graph mincut [5], Tikhonov Regularization [2], Manifold Regularization [3], etc.”
Learning Deep Architectures for AI (2007, methodology): “Similar limitations have been proved for a large class of semi-supervised learning algorithms also based on the neighborhoodgraph (Zhu et al., 2003; Zhou et al., 2004; Belkin et al., 2004; Delalleau et al., 2005).”
Unsupervised Image Matching and Object Discovery as Optimization (2019, background): “Several alternatives are possible, including weakly supervised approaches that rely on readily available meta-data [2, 9] or image-level labels [14, 23, 24, 25, 39, 45] instead of more complex annotations such as bounding boxes [17, 38] or object masks [20] as supervisory signal; semi supervised met”
Discrete Signal Processing on Graphs: Frequency Analysis (2013, methodology): “In signal processing on graphs, minimization problems similar to (39) and (41) formulated with the Laplacian quadratic form (see (51) in Appendix B) are used for data classiﬁcation [46], [47], [41], [48], characterization of graph signal smoothness [18] and recovery [8].”
Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate (2018, methodology): “This provides a graph-based interpolated semi-supervised learning algorithm similar to label propagation [53] or interpolated graph regularization [10].”
Learning Transferable Knowledge Through Embedding Spaces (2019, background): “This problem can be formulated as a graph-based semi-supervised label propagation [74; 75].”
Tighter PAC-Bayes bounds through distribution-dependent priors (2013, background): “(15) The exponent seeks to minimize empirical risk plus the smoothness on the graph formed on the sample, as is a typical methodology in semi-supervised learning (Belkin et al., 2006, 2004).”
Semi-Supervised Classification by Low Density Separation (2005, methodology): “We compare our algorithms to one state of the art supervised method, SVM, and to two state of the art semisupervised methods, the TSVM optimization scheme as implemented in SVMlight [12] and a graph-based manifold learning, which is closely related to those in [1, 22, 23].”
Learning With $\ell ^{1}$-Graph for Image Analysis (2010, methodology): “Then, a series of new algorithms for various machine learning tasks, e.g., data clustering, subspace learning, and semisupervised learning, are derived upon the -graphs.”
Label Propagation through Linear Neighborhoods (2006, methodology): “More concretely, most of these methods (Szummer & Jaakkola, 2002; Zhou et al, 2004a; Zhu et al, 2003 ) adopted a gaussian function to calculate the edge weights of the graph (i.e.”
Mining User Intents in Twitter: A Semi-Supervised Approach to Inferring Intent Categories for Tweets (2015, methodology): “6 can be obtained as follows (see (Belkin, Matveeva, and Niyogi 2004) for details), f̂ c = (Il + γ∆) −1Ilý c (7) Because (f c)>∆f c > 0, ∆ is a symmetric and positive semi-definite matrix.”
Manifold Regularization: A Geometric Framework for Learning from Labeled and Unlabeled Examples (2006, background): “Some very preliminary steps in that direction have been taken in Belkin et al. (2004).”