Gradient scarcity with Bilevel Optimization for Graph Learning

Hashem Ghanem, Samuel Vaiter, Nicolas KerivenarXiv 2023 · DOI · arXiv

Introduction

Semi-supervised learning (SSL) on graphs often relies on a small set of labeled nodes to infer properties of a much larger unlabeled population. A common approach to enhance these models is to learn the underlying graph structure itself. However, this process is frequently hindered by gradient scarcity—a phenomenon where edges distant from labeled nodes receive negligible updates. This paper provides a rigorous mathematical characterization of this issue, proving it persists even in sophisticated bilevel optimization frameworks.

The Gradient Scarcity Phenomenon

In graph learning, if an edge is "too far" from any labeled node, the gradient of the loss function with respect to that edge's weight tends toward zero. Consequently, these distant edges remain at their initial values, failing to contribute to the model's structural refinement.

While this was previously observed in joint optimization, the authors demonstrate that bilevel optimization—where the graph is treated as a hyperparameter optimized to minimize validation loss—does not inherently solve the problem. The complex dependency between optimal weights and the graph structure is insufficient to overcome the localization of labels.

Theoretical Bounds

The authors establish two key theoretical results regarding the flow of information:

  1. For GNNs: In a $k$-layer GNN, edges more than $k$ hops away from the training or validation sets receive exactly zero hypergradients due to the finite receptive field.
  2. For Laplacian Regularization: Even with an "infinite receptive field" where every node theoretically influences every other node, gradients are exponentially damped based on the distance to labeled nodes.
Visualization of hypergradient magnitude decay as a function of distance from labeled nodes.

As shown in the figure above, the magnitude of the hypergradient drops sharply as the cumulated distance to the training ($V_{tr}$) and validation ($V_{out}$) sets increases. This "dead zone" effectively prevents the optimizer from learning meaningful structures in the graph's periphery, even when information can theoretically flow across the whole network.

Proposed Solutions

To mitigate gradient scarcity and "bridge the gap" between distant nodes, the authors propose three primary strategies:

  • Latent Graph Learning (G2G): Parameterizing the graph using a "Graph-to-Graph" model (e.g., an MLP) that predicts edge weights from node features, allowing information to bypass local topological constraints.
  • Graph Regularization: Forcing global structure by adding loss terms that penalize undesirable properties, such as low-degree nodes.
  • Adjacency Powering ($A^r$): Optimizing higher powers of the adjacency matrix to effectively reduce the graph's diameter, bringing distant nodes closer in the eyes of the optimizer.

Experimental Results

The effectiveness of these methods was evaluated on synthetic datasets (like the "Cheaters" dataset) and the Cora citation network.

Comparison of outer training accuracy across different optimization strategies.

The results indicate that while standard bilevel optimization ("No fix") may struggle or converge slowly, strategies like G2G and regularization significantly improve the learning trajectory and final accuracy. For instance, on the Cora dataset, GNN accuracy improved from 77.0% to 82.0% with the G2G model. Notably, while refining $A^6$ technically solves the scarcity issue, it can sometimes lead to overfitting, highlighting the importance of choosing appropriate structural priors.

Conclusion

Gradient scarcity is a fundamental bottleneck in graph learning that theoretical "infinite receptive fields" do not automatically resolve. By understanding the exponential decay of signals across a graph, researchers can better design models—such as G2G architectures—that maintain gradient flow and improve structural learning in sparse-label environments. Future work will focus on tighter theoretical bounds and exploring how label distribution impacts the severity of this scarcity.

Summary updated

Abstract

A common issue in graph learning under the semi-supervised setting is referred to as gradient scarcity. That is, learning graphs by minimizing a loss on a subset of nodes causes edges between unlabelled nodes that are far from labelled ones to receive zero gradients. The phenomenon was first described when optimizing the graph and the weights of a Graph Neural Network (GCN) with a joint optimization algorithm. In this work, we give a precise mathematical characterization of this phenomenon, and prove that it also emerges in bilevel optimization, where additional dependency exists between the parameters of the problem. While for GCNs gradient scarcity occurs due to their finite receptive field, we show that it also occurs with the Laplacian regularization model, in the sense that gradients amplitude decreases exponentially with distance to labelled nodes. To alleviate this issue, we study several solutions: we propose to resort to latent graph learning using a Graph-to-Graph model (G2G), graph regularization to impose a prior structure on the graph, or optimizing on a larger graph than the original one with a reduced diameter. Our experiments on synthetic and real datasets validate our analysis and prove the efficiency of the proposed solutions.
BibTeX
@misc{ghanem2023gradient,
  author = {Hashem Ghanem and Samuel Vaiter and Nicolas Keriven},
  title = {{Gradient scarcity with Bilevel Optimization for Graph Learning}},
  year = {2023},
  eprint = {2303.13964},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2303.13964},
}
Figure