Semi-supervised K-Nearest Neighbors
Semi-supervised K-Nearest Neighbors (Label Propagation via KNN Graph) · Also known as: SS-KNN, semi-supervised KNN, KNN label propagation, graph-based semi-supervised KNN
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.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
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.
Strengths & limitations
- 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.
- 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.
Frequently asked
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.
Sources
- Zhu, X. & Ghahramani, Z. (2002). Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University. link ↗
- Chapelle, O., Scholkopf, B. & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press. ISBN: 978-0-262-03358-9
How to cite this page
ScholarGate. (2026, June 3). Semi-supervised K-Nearest Neighbors (Label Propagation via KNN Graph). ScholarGate. https://scholargate.app/en/machine-learning/semi-supervised-k-nearest-neighbors
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Label PropagationMachine learning↔ compare
- Semi-supervised Gaussian ProcessMachine learning↔ compare
- Semi-supervised LearningMachine learning↔ compare
- Semi-supervised Support Vector MachineMachine learning↔ compare