Semi-supervised K-Nearest Neighbors
- Introduced by
- Zhu, X. & Ghahramani, Z. (label propagation); Cover, T. & Hart, P. (KNN base)
- Year
- 2002 (semi-supervised extension); 1967 (KNN base)
- Type
- Semi-supervised classifier / label propagation
- Family
- Machine learning
What does it do?
Semi-supervised KNN extends the classic K-nearest neighbors algorithm to exploit large pools of unlabeled data alongside a small labeled set.
By building a KNN graph over all observations and propagating known labels through the graph's edges, the method infers labels for unlabeled points without requiring expensive manual annotation of every sample.
The intuition behind the method
Imagine a classroom where only a handful of students have name tags and the rest are anonymous. Standard KNN can only classify an anonymous student by looking at the handful of tagged neighbors close by. Semi-supervised KNN instead maps the entire room as a network — each student connected to their nearest neighbors — and floods labels outward from the tagged students like ink spreading through wet paper. Because the network captures the overall structure of the data, labels reach unlabeled points in a principled way that respects the underlying geometry rather than ignoring the unlabeled majority.
History
Label propagation on KNN graphs was systematized by Zhu and Ghahramani in 2002, building on Vapnik's transductive SVM and earlier graph-based diffusion ideas. The framework was consolidated in the MIT Press volume Semi-Supervised Learning (Chapelle et al., 2006), which remains the standard reference. Scalable approximate-KNN libraries (FAISS, Annoy) later made the approach practical on millions of points, and it continues to be used as a strong baseline for semi-supervised image and text classification.
When to use it
Use semi-supervised KNN when you have a small labeled set and a large unlabeled pool from the same distribution, the data lives in a relatively low-dimensional space (fewer than about 50 features), and you believe neighboring points share the same class. It is well suited to image patch classification, text categorization with sparse annotations, and medical screening tasks where expert labeling is expensive. Avoid it when labeled and unlabeled data come from different distributions (covariate shift), the feature space is very high-dimensional (the KNN graph becomes unreliable), the dataset is small enough that fully supervised KNN already suffices, or the class boundaries do not align with the local density structure of the data.
Limitations and considerations
- Graph construction scales quadratically with dataset size unless approximate nearest-neighbor methods are used.
- Performance degrades sharply in high-dimensional spaces where distance metrics lose discriminative power.
- Assumes labeled and unlabeled data are drawn from the same distribution; covariate shift breaks the method.
- Requires careful tuning of k, the edge-weight bandwidth, and the propagation mixing parameter.
- Label propagation can amplify initial labeling errors across large portions of the graph.
Source conditions do not replace independent scientific review or validation by an analysis engine.
Strengths
- Exploits cheap unlabeled data to improve accuracy beyond what is possible with the labeled set alone.
- No parametric model assumptions: relies only on local neighborhood geometry.
- Naturally handles multi-class problems without modification.
- The KNN graph construction is transparent and easy to inspect.
- Works well when classes form compact, well-separated clusters in feature space.
Applications
- Image classification with a small set of labeled images and a large unlabeled corpus.
- Text and document categorization where manual labeling is expensive.
- Medical record or pathology slide classification with limited expert annotations.
- Fraud detection when only a small number of confirmed fraud cases are available.
- Sensor data labeling in industrial IoT settings with sparse ground-truth events.
How it works
How it works
A graph is built over all observations — both labeled and unlabeled. Each node corresponds to one data point, and directed or undirected edges connect each node to its k nearest neighbors in the feature space. The choice of k controls how locally or globally labels will be propagated: small k keeps propagation tight; large k allows labels to jump across larger gaps.
Edge weights capture the strength of similarity between connected nodes, typically via a Gaussian (RBF) kernel applied to the Euclidean distance between feature vectors. A bandwidth parameter sigma controls how quickly similarity decays with distance. Stronger edges carry labels more readily during propagation.
Formula
w_{ij} = \exp(-\|x_i - x_j\|^2 / \sigma^2)Labels are spread iteratively from labeled nodes to unlabeled neighbors. At each iteration, every node updates its soft label distribution as a weighted combination of its neighbors' current distributions and its own initial label (if labeled). A mixing parameter alpha balances the influence of the graph structure versus the hard labels, and iteration continues until the distributions converge.
Formula
F \leftarrow \alpha W D^{-1} F + (1-\alpha) YOnce propagation converges, each unlabeled node is assigned the class with the highest soft-label score in its converged distribution. Labeled nodes are clamped to their true labels throughout, so known labels are never overridden.
Formula
\hat{y}_i = \arg\max_c F_{ic}Common pitfalls
- Constructing the KNN graph without normalizing features, causing high-variance features to dominate distance calculations.
- Setting k too large, which smooths over genuine class boundaries and produces over-smoothed label distributions.
- Ignoring the possibility that unlabeled data are out-of-distribution relative to the labeled set.
- Reporting accuracy on unlabeled nodes as if it were an unbiased test-set estimate — unlabeled nodes leaked into the graph during training.
- Skipping convergence checks and using a fixed, arbitrary number of propagation iterations.
Frequently asked questions
How do I choose k?
Start with k in the range 5-15 and tune by held-out labeled validation accuracy. Smaller k gives sharper, more local boundaries; larger k allows labels to propagate further but risks crossing true class boundaries.
Can I evaluate the method honestly when most data are unlabeled?
Hold out a dedicated labeled test set that is never added to the graph. Nodes in the graph — even unlabeled ones — are part of training, so any labeled node that participates in graph construction must not also serve as a test point.
What if my dataset is too large to build a full KNN graph?
Use approximate nearest-neighbor libraries such as FAISS or Annoy to construct the graph in O(n log n) rather than O(n^2), then apply label propagation on the sparse approximate graph.
Does semi-supervised KNN always outperform supervised KNN?
Not necessarily. If unlabeled data are out-of-distribution or the feature space is very high-dimensional, the graph is noisy and propagation can hurt performance. Always compare against a supervised KNN baseline before claiming a benefit from unlabeled data.
Is this the same as label spreading or label propagation in scikit-learn?
Closely related. Scikit-learn's LabelPropagation and LabelSpreading implement Zhu and Ghahramani's framework using a KNN or RBF kernel graph, so they are direct implementations of the method described here.
Related methods
Sources
Zhu, X. & Ghahramani, Z. (2002). Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University.
Open publication referenceCopied.Chapelle, O., Scholkopf, B. & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press.
ISBN: 978-0-262-03358-9Copied.