# Gradient scarcity with Bilevel Optimization for Graph Learning

arXiv: https://arxiv.org/abs/2303.13964 · HTML: https://mlsanity.com/paper/2303.13964/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 31 references that are in the map.
- First posted on arXiv 24 Mar 2023.

## Builds on (most cited first, 19 of 19)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Effective Approaches to Attention-based Neural Machine Translation](https://mlsanity.com/paper/1508.04025/) (2015)
- [Self-supervised Learning: Generative or Contrastive](https://mlsanity.com/paper/2006.08218/) (2020)
- [Bilevel Programming for Hyperparameter Optimization and Meta-Learning](https://mlsanity.com/paper/1806.04910/) (2018)
- [Graph Self-Supervised Learning: A Survey](https://mlsanity.com/paper/2103.00111/) (2021)
- [Learning Discrete Structures for Graph Neural Networks](https://mlsanity.com/paper/1903.11960/) (2019)
- [Constrained Graph Variational Autoencoders for Molecule Design](https://mlsanity.com/paper/1805.09076/) (2018)
- [How to learn a graph from smooth signals](https://mlsanity.com/paper/1601.02513/) (2016)
- [Self-supervised Learning on Graphs: Contrastive, Generative,or Predictive](https://mlsanity.com/paper/2105.07342/) (2021)
- [Towards Unsupervised Deep Graph Structure Learning](https://mlsanity.com/paper/2201.06367/) (2022)
- [SLAPS: Self-Supervision Improves Structure Learning for Graph Neural Networks](https://mlsanity.com/paper/2102.05034/) (2021)
- [Not too little, not too much: a theoretical analysis of graph (over)smoothing](https://mlsanity.com/paper/2205.12156/) (2022)
- [How to Find Your Friendly Neighborhood: Graph Attention Design with Self-Supervision](https://mlsanity.com/paper/2204.04879/) (2022)
- [Unifying Graph Convolutional Neural Networks and Label Propagation](https://mlsanity.com/paper/2002.06755/) (2020)
- [Generalized Inner Loop Meta-Learning](https://mlsanity.com/paper/1910.01727/) (2019)

## Abstract (arXiv)

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.