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.
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.
- Defining Starved Nodes: They define a $k$-hop starved node as one that has no labeled nodes within its $k$-hop neighborhood.
- 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.
- Graph Restoration: They "replenish" supervision by reconstructing the $U$ matrix—essentially forcing connections between starved nodes and their nearest labeled neighbors.
- 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.
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