Abstract
Semi-supervised learning (SSL) relies heavily on the underlying graph structure to propagate labels from a small set of labeled instances to a larger unlabeled pool. While much research focuses on the propagation algorithms themselves, the initial graph construction phase is often overlooked. This paper explores three novel strategies for robust graph construction: efficient regular graph construction (S-kNN), label-aware hub creation (GBILI), and link prediction. Experimental results on benchmark datasets demonstrate that these specialized construction techniques significantly enhance classification accuracy and stability compared to traditional methods like $k$-Nearest Neighbors (kNN).
Introduction
In scenarios characterized by abundant unlabeled data and scarce labeled examples, graph-based semi-supervised learning offers a powerful framework. By representing data points as nodes and similarities as edges, labels can "flow" through the network. However, the efficacy of this process is intrinsically tied to the graph's quality. Standard "off-the-shelf" construction methods, such as $k$-Nearest Neighbors (kNN), often introduce noise in dense regions or fail to capture the manifold structure accurately. This research addresses these deficiencies by proposing graph construction techniques specifically optimized for label propagation.
Methodology
The authors propose three distinct methodologies to refine the graph construction process:
1. Efficient Regular Graph Construction (S-kNN)
Regular graphs, where each node maintains a constant degree, typically yield better SSL performance than standard kNN graphs. However, their construction is traditionally computationally expensive ($O(n^3)$). The proposed S-kNN method reduces this complexity to $O(n^2)$ by utilizing topological measures like "closeness" to guide edge selection, ensuring a regular structure without prohibitive overhead.
2. Graph-based on Informativeness of Labeled Instances (GBILI)
Traditional graph construction is unsupervised and ignores available label information. GBILI leverages these labels to designate labeled instances as "hubs"—nodes with high centrality. By positioning labeled points as structural anchors within the network, the method facilitates more effective and natural label diffusion.
3. Link Prediction
This approach views graph construction as an evolving process. Starting from a baseline graph (e.g., MST or kNN), link prediction algorithms estimate missing connections based on existing network topology. This refinement step strengthens the graph structure prior to the final classification phase.
Experimental Setup
The proposed methods were evaluated against standard benchmarks: g241c and g241n (synthetic manifold datasets), Digit1 (handwritten digits), and USPS (postal service digits). To simulate a realistic semi-supervised environment, experiments were conducted using only 10 labeled instances per dataset.
Results
The proposed construction methods consistently outperformed traditional baselines, including standard kNN, Mutual kNN (MkNN), and Minimum Spanning Trees (MST).
As shown in Table 1, the integration of link prediction (LP) provided substantial gains. On the Digit1 dataset, MST+LP achieved an accuracy of 0.917, a dramatic improvement over the base MST accuracy of 0.499. Similarly, the GBILI method demonstrated superior performance on the USPS dataset with an accuracy of 0.85, compared to the kNN baseline of 0.838.
Beyond raw accuracy, the GBILI method exhibited remarkable stability. Unlike traditional kNN, which can suffer from performance degradation as $k$ increases due to "label noise," GBILI maintains a constant average degree, ensuring the graph remains informative even as the neighborhood size grows.
Discussion and Conclusion
The findings underscore that graph construction is a critical, yet often neglected, component of the SSL pipeline. By ensuring graph regularity, leveraging labeled instances as hubs, and refining edges through link prediction, we can create more robust structures for label propagation.
Future work will address the scalability of these $O(n^2)$ methods for large-scale datasets and explore the comparative effectiveness of different link prediction algorithms. Additionally, developing self-tuning mechanisms to reduce parameter sensitivity remains a key objective for making these advanced graph construction techniques more accessible.
Summary updated