Latent Graph Inference with Limited Supervision

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

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 may 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. We identify pivotal nodes using a method inspired by CUR matrix decomposition and eliminate starvation by reconstructing destroyed connections. Extensive experiments demonstrate that reducing starved nodes consistently improves performance, particularly under extremely limited supervision (e.g., a 6.12% improvement on Pubmed with a labeling rate of only 0.3%).

Introduction

Graph Neural Networks (GNNs) have become the standard for processing non-Euclidean data. However, their performance is often predicated on the existence of a high-quality graph structure. In many real-world applications, this structure is unknown or noisy, leading to the development of Latent Graph Inference (LGI). LGI models attempt to learn the graph topology and node embeddings simultaneously. While promising, LGI faces a significant hurdle: the scarcity of labeled data.

In this work, we identify a critical phenomenon called "Supervision Starvation" (SS). We demonstrate that the common practice of graph sparsification—intended to reduce noise and computational overhead—unintentionally isolates large portions of the graph from labeled nodes. This isolation prevents the model from effectively learning the edge weights for these "starved" nodes, leading to suboptimal generalization.

The Supervision Starvation Problem

In LGI, the model learns an adjacency matrix $A$. To ensure efficiency and remove noise, $A$ is typically sparsified (e.g., via k-nearest neighbors or thresholding). We define a node as "starved" if it cannot reach any labeled node within $k$ hops, where $k$ is the number of GNN layers.

When a node is starved, the edge weights connecting it to its neighbors do not participate in the backpropagation of the loss function. Because these weights receive no gradient signal, they remain essentially random or poorly optimized. During inference, these "starved" weights are used to aggregate features for the node, resulting in inaccurate predictions. This problem is particularly acute in low-labeling regimes, where the probability of a node being disconnected from the sparse set of labels is high. Sparsification, while useful for efficiency, acts as a double-edged sword by creating these structural disconnections.

Methodology: Identifying and Feeding Starved Nodes

To mitigate Supervision Starvation, we propose a framework to identify starved nodes and restore their connection to the supervision signal.

1. Efficient Identification via CUR Decomposition

Identifying $k$-hop starved nodes through brute-force matrix multiplication is computationally expensive, scaling at $O(n^3)$. To address this, we leverage CUR matrix decomposition, a low-rank approximation technique. By treating the adjacency matrix through the lens of CUR, we can identify starved nodes much more efficiently. We prove that if specific sub-matrices in the CUR decomposition are zero, the corresponding nodes are starved, allowing for rapid identification even in large-scale graphs.

2. Affinity Restoration

Once starved nodes are identified, we "replenish" their supervision. We construct a regularization graph that explicitly connects these starved nodes to their nearest labeled neighbors. This ensures that every node in the graph has a path to a labeled node, allowing the loss gradient to flow through the entire structure during training.

3. Balancing Influence

Adding these restorative connections can sometimes lead to "Weight Contribution Rate Decay," where the new connections might overshadow the features learned by the LGI model. We introduce two strategies to maintain balance:

  • Sampling: Limiting the number of labeled neighbors each starved node connects to.
  • Weight Boosting: Adjusting the weights of non-starved nodes to ensure the original graph structure still plays a primary role in representation learning.

Experimental Evaluation

We evaluated our approach by integrating it as a regularization module into several state-of-the-art LGI models, including IDGL, SLAPS, and GRCN, across standard benchmarks like Cora, Citeseer, Pubmed, and ogbn-arxiv.

Performance in Low-Supervision Scenarios

The most significant gains were observed in datasets with extremely limited labels. On the Pubmed dataset, with a labeling rate of only 0.3%, our method improved the accuracy of a GCN+KNN baseline by 6.12% and the SLAPS model by 2.26%. This confirms that addressing the structural disconnection caused by sparsification is key to performance in label-sparse environments.

Scalability and Robustness

Our CUR-based identification method proved scalable to large datasets like ogbn-arxiv, proving significantly faster than brute-force alternatives. Furthermore, the approach showed robustness across different GNN depths, mitigating the "over-smoothing" issues that usually occur when trying to fix starvation by simply making the GNN deeper.

Conclusion

Supervision Starvation is a structural byproduct of graph sparsification in Latent Graph Inference. By identifying starved nodes through efficient CUR decomposition and restoring their affinities to labeled data, we can significantly improve the generalization of GNNs. This approach is model-agnostic and provides a robust solution for graph learning tasks where labels are a scarce resource.

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 may 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