The DOI matches its Crossref record; 9 of the 9 references it cites were found in a registry or an index.
Semi-supervised learning using randomized mincuts
Abstract
In many application domains there is a large amount of unlabeled data but only a very limited amount of labeled training data. One general approach that has been explored for utilizing this unlabeled data is to construct a graph on all the data points based on distance relationships among examples, and then to use the known labels to perform some type of graph partitioning. One natural partitioning to use is the minimum cut that agrees with the labeled data (Blum & Chawla, 2001), which can be thought of as giving the most probable label assignment if one views labels as generated according to a Markov Random Field on the graph. Zhu et al. (2003) propose a cut based on a relaxation of this field, and Joachims (2003) gives an algorithm based on finding an approximate min-ratio cut.In this paper, we extend the mincut approach by adding randomness to the graph structure. The resulting algorithm addresses several short-comings of the basic mincut approach, and can be given theoretical justification from both a Markov random field perspective and from sample complexity considerations. In cases where the graph does not have small cuts for a given classification problem, randomization may not help. However, our experiments on several datasets show that when the structure of the graph supports small cuts, this can result in highly accurate classifiers with good accuracy/coverage tradeoffs. In addition, we are able to achieve good performance with a very simple graph-construction procedure.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Semi-supervised learning using Gaussian fields and harmonic functions
Zhu, X., Zoubin Ghahramani, A., & Lafferty, J. (2003) · Cited by 3,509
Self-citationA database for handwritten text recognition research
Hull, J. J. (1994) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.291440 · Cited by 2,244
Exact Maximum A Posteriori Estimation for Binary Images
Greig, D. M., Porteous, B. T., & Seheult, A. H. (1989) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1989.tb01764.x · Cited by 1,055
Learning from Labeled and Unlabeled Data using Graph Mincuts
Blum, A. L., & Chawla, S. (2018) · doi:10.1184/r1/6606860 · Cited by 928
Self-citationTransductive learning via spectral graph partitioning
Joachims, T. (2003) · Cited by 633
Polynomial-Time Approximation Algorithms for the Ising Model
Jerrum, M., & Sinclair, A. (1993) · SIAM Journal on Computing · doi:10.1137/0222066 · Cited by 548
PAC-Bayesian Stochastic Model Selection
McAllester, D. A. (2003) · Machine Learning · doi:10.1023/a:1021840411064 · Cited by 190
Learnability with respect to fixed distributions
Benedek, G. M., & Itai, A. (1991) · Theoretical Computer Science · doi:10.1016/0304-3975(91)90026-x · Cited by 118
Kleinberg, J. M. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892110 · Cited by 29
Cited by
Sentiment Analysis and Opinion Mining
Liu, B. (2012) · Synthesis Lectures on Human Language Technologies · doi:10.1007/978-3-031-02145-9 · Cited by 3,281
Sentiment Analysis and Opinion Mining
Zhang, L., & Liu, B. (2017) · Encyclopedia of Machine Learning and Data Mining · doi:10.1007/978-1-4899-7687-1_907 · Cited by 3,260
Deeper Insights Into Graph Convolutional Networks for Semi-Supervised Learning
Li, Q., Han, Z., & Wu, X.-M. (2018) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v32i1.11604 · Cited by 2,872
A survey on semi-supervised learning
van Engelen, J. E., & Hoos, H. H. (2020) · Machine Learning · doi:10.1007/s10994-019-05855-6 · Cited by 2,666
Introduction to Semi-Supervised Learning
Zhu, X., & Goldberg, A. B. (2009) · Synthesis Lectures on Artificial Intelligence and Machine Learning · doi:10.1007/978-3-031-01548-9 · Cited by 1,766
Metadata
- Authors
- Blum, A., Lafferty, J., Rwebangira, M. R., & Reddy, R.
- Venue
- Twenty-first international conference on Machine learning - ICML '04
- Publisher
- ACM Press
- Published
- 2004
- Pages
- 13
- OpenAlex
- W2061526129
- Cited by
- 260
- References
- 9
- Type
- conference abstract
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Semi-supervised learning using randomized mincuts. https://app.cochat.ai/papers/10.1145/1015330.1015429
- The paper
- Blum, A., Lafferty, J., Rwebangira, M. R., & Reddy, R. (2004). Semi-supervised learning using randomized mincuts. Twenty-first international conference on Machine learning - ICML '04. https://doi.org/10.1145/1015330.1015429
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.