Semi-Supervised Classification With Graph Structure Similarity and Extended Label Propagation

Junliang Ma, Nannan Wang, Bing XiaoIEEE Access 2019 · DOI

Introduction

Graph-based semi-supervised learning (GSSL) has emerged as a powerful paradigm for classification tasks where labeled data is scarce but unlabeled data is abundant. By representing data points as nodes in a graph and their relationships as edges, GSSL allows labels to propagate from a small set of known examples to the rest of the dataset. However, the performance of these methods is fundamentally limited by two factors: the quality of the initial graph construction and the logic governing how labels transition across that graph. This paper introduces a two-stage framework designed to address these bottlenecks through Fusing Local and Global Structural Similarity (FLGSS) and Extended Label Propagation (ELP).

The Challenges of Traditional GSSL

Most existing GSSL frameworks rely on K-Nearest Neighbors (KNN) to build the underlying data manifold. While simple, KNN is prone to creating "hubs"—nodes with disproportionately high degrees—or leaving sparse regions of the data space entirely disconnected. These structural flaws prevent labels from flowing accurately across the true manifold.

Furthermore, traditional Label Propagation (LP) algorithms are often "blind" to the actual label space during the inference process. They calculate transition probabilities based solely on unsupervised feature similarities (e.g., Euclidean distance). By failing to leverage the correlations and interactions between known labels during propagation, these methods often suffer from label "bleeding" across class boundaries in ambiguous regions of the feature space.

Proposed Methodology

To overcome these limitations, the authors propose a pipeline that first refines the graph structure and then enhances the propagation mechanism.

The proposed two-stage pipeline: FLGSS for graph construction followed by ELP for label inference.

1. FLGSS: Fusing Local and Global Structural Similarity

FLGSS treats graph construction as a link prediction problem rather than a simple distance-based search. It enhances a base KNN graph by predicting missing links using two complementary metrics:

  • Local Similarity (Common Neighbors): If two nodes share many mutual neighbors, they are likely to belong to the same class, even if their direct distance is high. This helps densify local clusters.
  • Global Similarity (Katz Index): The Katz Index considers all possible paths between two nodes, capturing long-range connectivity that local metrics miss. This ensures the manifold remains globally consistent.

These two perspectives are fused using a weighting hyperparameter ($\alpha$), resulting in a richer, more balanced graph that better represents the underlying data distribution.

2. ELP: Extended Label Propagation

Standard LP uses a transition matrix $P$ derived from edge weights. ELP introduces a second matrix, $P^F$, which captures transition probabilities within the label space based on known ground truth. During each iteration, ELP fuses $P$ and $P^F$. This "steers" the random walk of label propagation, forcing the algorithm to respect known class boundaries and correlations. This dual-matrix approach prevents the unsupervised feature distances from dominating the process when label information suggests a different path.

Experimental Evaluation

The framework was tested across a diverse range of datasets, including synthetic manifolds (e.g., twomoon, three_ring), small-scale image benchmarks (e.g., MNIST, COIL-20), and large-scale data (e.g., CIFAR-10). For high-dimensional image data like CIFAR-10, features were extracted using a pre-trained VGGnet19 and reduced via PCA before applying the graph algorithms.

Key Results

  • Accuracy: The combination of FLGSS and ELP consistently outperformed standard KNN + LP baselines. On a 50,000-sample subset of CIFAR-10 with 10% labels, the proposed method achieved 60.18% accuracy compared to the baseline's 58.34%.
  • Efficiency: Despite the added complexity of link prediction, the time complexity of FLGSS remains $O(n^2)$, matching traditional methods. Interestingly, ELP often converged faster than standard LP because the label-guided transitions helped the algorithm reach a stable state more quickly.
  • Robustness: Statistical significance tests (Nemenyi post-hoc) confirmed that the performance gains were consistent across various data types and labeling ratios.

Conclusion

By integrating local and global structural information into graph construction and guiding label propagation with known class correlations, the FLGSS + ELP framework significantly improves the robustness of semi-supervised classification. While the method currently relies on pre-extracted features for complex datasets, future work may involve integrating these graph-refinement techniques directly into end-to-end Graph Neural Networks (GNNs).

Summary updated

BibTeX
@article{ma2019semi,
  author = {Junliang Ma and Nannan Wang and Bing Xiao},
  title = {{Semi-Supervised Classification With Graph Structure Similarity and Extended Label Propagation}},
  journal = {IEEE Access},
  year = {2019},
  doi = {10.1109/access.2019.2914034},
}
Figure