Latent Graph Inference with Limited Supervision

Jianglin Lu, Yi Xu, Huan Wang, Yue Bai, Yun Fu

TL;DR

Existing Latent Graph Inference (LGI) methods often fail because many edges never "see" a label during training—a problem called Supervision Starvation. This paper identifies graph sparsification as the primary culprit and introduces a model-agnostic "repair" technique inspired by CUR matrix decomposition to reconnect isolated nodes to labeled ones, boosting accuracy by over 6% in extremely low-label scenarios.

The Problem: Supervision Starvation in Latent Graphs

In many real-world scenarios, we don't have a pre-defined graph (like a social network or citation web); we only have data features. Latent Graph Inference (LGI) attempts to learn the graph structure and the data representations simultaneously.

However, these models struggle with Supervision Starvation (SS). If a node and all its neighbors are unlabeled, the weights of the edges connecting them do not contribute to the training loss. These edges are essentially "guessing" and never get corrected by backpropagation. When it comes time to test the model, these under-trained edges lead to poor predictions.

The authors discovered that the common practice of graph sparsification (keeping only the strongest connections to save memory) actually exacerbates this issue. Sparsification accidentally severs the "pivotal" lines of communication between unlabeled nodes and the few labeled nodes available, isolating large clusters of data from the training signal.

Number of starved nodes across different k-hop neighborhoods.

Methodology: Identifying and Repairing Starved Nodes

The authors propose a framework to identify "starved" nodes and strategically add connections back to the graph, ensuring every node can "feel" the influence of a label.

  1. Defining Starved Nodes: They define a $k$-hop starved node as one that has no labeled nodes within its $k$-hop neighborhood.
  2. Efficient Identification via CUR Decomposition: Calculating neighborhoods for every node using matrix powers is computationally expensive ($O(n^3)$). Instead, the authors use a strategy inspired by CUR matrix decomposition. By treating labeled nodes as columns ($C$) and starved nodes as rows ($R$), they show that the intersection matrix ($U$) naturally reveals where connections are missing.
  3. Graph Restoration: They "replenish" supervision by reconstructing the $U$ matrix—essentially forcing connections between starved nodes and their nearest labeled neighbors.
  4. Weight Balancing: Adding these new edges can dilute the importance of the original learned graph. To fix this, they introduce strategies to balance the "Weight Contribution Rate," ensuring the restored connections provide supervision without overwhelming the features the model is trying to learn.

Key Insights and Results

The researchers evaluated their method on several standard graph benchmarks with varying "labeling rates" (the percentage of nodes that have known labels), including Cora, Citeseer, ogbn-arxiv, and Pubmed.

One might assume that simply using deeper Graph Neural Networks (GNNs) would allow the model to reach labeled nodes further away. However, the authors show that deeper GNNs suffer from "over-smoothing" and "over-squashing," which degrades performance more than the starvation itself. Instead of inventing a new GNN architecture, "repairing" the graph topology proves to be a more effective, model-agnostic solution.

Performance comparison across datasets showing consistent gains, especially on Pubmed.

The proposed CUR-based extension was added to several state-of-the-art LGI models (like SLAPS, IDGL, and GRCN), yielding impressive results:

  • Massive Gains with Low Labels: On the Pubmed dataset, which featured an extremely low labeling rate of just 0.3% (only 60 labeled nodes out of nearly 20,000), their method improved the baseline GCN+KNN accuracy by 6.12%.
  • Consistency: The method consistently improved performance across all tested models and datasets, proving it is a robust "plug-and-play" enhancement.
  • Efficiency: The CUR-inspired identification of starved nodes is significantly faster than traditional matrix-based methods, making it highly feasible for larger datasets.

Limitations and Future Work

While highly effective, the approach has a few open challenges:

  • $k$-hop Complexity: The paper provides an efficient solution for 1-hop and 2-hop starvation, but identifying starved nodes for $k > 2$ using CUR decomposition remains mathematically complex.
  • Degree Distribution: Adding connections to labeled nodes changes the "degree" (number of edges) of those nodes. While no negative effects were observed in these experiments, drastically altering the graph's degree distribution could theoretically impact certain models.
  • Hyperparameter Sensitivity: The method introduces parameters like $\tau$ (number of restored neighbors) and $\alpha$ (weight of the restoration). If $\tau$ is set too high, the model might start connecting nodes to labeled examples that aren't actually semantically related, introducing unwanted noise.

Summary updated

Abstract

Latent graph inference (LGI) aims to jointly learn the underlying graph structure and node representations from data features. However, existing LGI methods commonly suffer from the issue of supervision starvation, where massive edge weights are learned without semantic supervision and do not contribute to the training loss. Consequently, these supervision-starved weights, which determine the predictions of testing samples, cannot be semantically optimal, resulting in poor generalization. In this paper, we observe that this issue is actually caused by the graph sparsification operation, which severely destroys the important connections established between pivotal nodes and labeled ones. To address this, we propose to restore the corrupted affinities and replenish the missed supervision for better LGI. The key challenge then lies in identifying the critical nodes and recovering the corrupted affinities. We begin by defining the pivotal nodes as k-hop starved nodes, which can be identified based on a given adjacency matrix. Considering the high computational burden, we further present a more efficient alternative inspired by CUR matrix decomposition. Subsequently, we eliminate the starved nodes by reconstructing the destroyed connections. Extensive experiments on representative benchmarks demonstrate that reducing the starved nodes consistently improves the performance of state-of-the-art LGI methods, especially under extremely limited supervision (6.12% improvement on Pubmed with a labeling rate of only 0.3%).
BibTeX
@inproceedings{lu2023latent,
  author = {Jianglin Lu and Yi Xu and Huan Wang and Yue Bai and Yun Fu},
  title = {{Latent Graph Inference with Limited Supervision}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=tGuMwFnRZX},
}
Figure