Learning from Labeled and Unlabeled Data using Graph Mincuts

By Avrim Blum, S. Chawla. 2001

1,115 citations recorded by the source corpus.

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

Citations in the corpus

Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning (2018, background): “Researches along this line include min-cuts (Blum and Chawla 2001) and randomized min-cuts (Blum et al. 2004), spectral graph transducer (Joachims 2003), label propagation (Zhu, Ghahra-mani, and Lafferty 2003) and its variants (Zhou et al. 2004; Bengio, Delalleau, and Le Roux 2006), modiﬁed…”
Attention-based Graph Neural Network for Semi-supervised Learning (2018, background): “There is a long line of literature on this topic since [7] which seeks graph cuts that preserve the known labels and [50] which uses graph Laplacian to regularize the nearby nodes to have similar labels.”
Semi-Supervised Self-Training of Object Detection Models (2005, background): “A number of authors have taken the approach of representing the relationships between labeled and unlabeled data using a graph in which the edge weights are inversely related to the similarity between the different examples in feature space [3].”
Regularization and Semi-supervised Learning on Large Graphs (2004, methodology): “This last example is an instantiation of transductive learning where other approaches include the Naive Bayes for text classification in [12], transductive SVM [15,9], the graph mincut approach in [2], and the random walk on the adjacency graph in [14].”
Using X-ray images and deep learning for automated detection of coronavirus disease (2020, methodology): “The performance of the proposed classification model was evaluated based on accuracy, sensitivity, specificity, precision, and F1 score (Bhandary et al., 2020; Blum & Chawla, 2001).”
Semi-Supervised Learning on Riemannian Manifolds (2004, methodology): “Although the area of partially labeled classification is fairly new, a considerable amount of work has been done in that field since the early 90's (e.g., (Blum and Chawla, 2001; Castelli and Cover, 1995; Nigam, et al, 2000; Szummer and Jaakkola, 2002)).”
Semi-Supervised Learning (2019, neutral): “Graph-Based Models This semi-supervised learning method assumes that there is a graph G = {V,E} such that the vertices V are the labeled and unlabeled training instances, and the undirected edges E connect instances i, j with weight wij [4, 14, 3].”
Label Efficient Semi-Supervised Learning via Graph Filtering (2019, background): “Another line of works rely on graph partition, where the cuts should agree with the labeled vertices and be placed in low density regions [7, 8, 28, 63], among which the most popular one is perhaps the label propagation methods [5, 15, 61].”
Group-Wise Learning for Aurora Image Classification With Multiple Representations (2019, positive): “In a semisupervised manner, graph mincuts [50] minimizes the number of similar pairs of vertices that are given different labels.”
Semi-Supervised Polarity Lexicon Induction (2009, background): “Mincuts for semi-supervised learning proposed by Blum and Chawla (2001) tries to classify data-points by partitioning the similarity graph such that it minimizes the number of similar points being labeled differently.”
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.”
Node Classification in Social Networks (2011, background): “Blum and Chawla [7] assume that the weights on edges of the graph denote similarity between the associated nodes.”
Learning from Imbalanced Data (2009, background): “Other representative works for semisupervised learning include the selftraining methods [138], [139], semisupervised support vector machines [140], [141], graph-based methods [142], [143], and Expectation-Maximization (EM) algorithm with generative mixture models [144], [145].”
Self-labeled techniques for semi-supervised learning: taxonomy, software and empirical study (2015, background): “Alternatively, SSC can also be viewed as a graph min-cut problem [10].”
Q-Cut - Dynamic Discovery of Sub-goals in Reinforcement Learning (2002, background): “further details on the Max-Flow algorithms and associated applications), and recently also for enabling efficient use of unlabeled data in classification tasks (see [3]).”