# Latent Graph Inference with Limited Supervision

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 48 references that are in the map.
- First posted on arXiv 6 Oct 2023.

## Builds on (most cited first, 30 of 31)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Dynamic Graph CNN for Learning on Point Clouds](https://mlsanity.com/paper/1801.07829/) (2018)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [E(n) Equivariant Graph Neural Networks](https://mlsanity.com/paper/2102.09844/) (2021)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Graph Structure Learning for Robust Graph Neural Networks](https://mlsanity.com/paper/2005.10203/) (2020)
- [A Fair Comparison of Graph Neural Networks for Graph Classification](https://mlsanity.com/paper/1912.09893/) (2019)
- [Learning Discrete Structures for Graph Neural Networks](https://mlsanity.com/paper/1903.11960/) (2019)
- [Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings](https://mlsanity.com/paper/2006.13009/) (2020)
- [NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification](https://mlsanity.com/paper/2306.08385/) (2023)
- [Adaptive Graph Convolutional Neural Networks](https://mlsanity.com/paper/1801.03226/) (2018)
- [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)
- [Learning Dynamic Graph Representation of Brain Connectome with Spatio-Temporal Attention](https://mlsanity.com/paper/2105.13495/) (2021)
- [Differentiable Graph Module (DGM) for Graph Convolutional Networks](https://mlsanity.com/paper/2002.04999/) (2020)
- [Graph Structure Learning with Variational Information Bottleneck](https://mlsanity.com/paper/2112.08903/) (2021)
- [Multi-view Contrastive Graph Clustering](https://mlsanity.com/paper/2110.11842/) (2021)
- [Graph-Revised Convolutional Network](https://mlsanity.com/paper/1911.07123/) (2019)
- [Adaptive Trajectory Prediction via Transferable GNN](https://mlsanity.com/paper/2203.05046/) (2022)
- [Learning Conditioned Graph Structures for Interpretable Visual Question Answering](https://mlsanity.com/paper/1806.07243/) (2018)
- [Latent-Graph Learning for Disease Prediction](https://mlsanity.com/paper/2003.13620/) (2020)
- [Optimal CUR Matrix Decompositions](https://mlsanity.com/paper/1405.7910/) (2014)
- [Learning to Learn Graph Topologies](https://mlsanity.com/paper/2110.09807/) (2021)
- [Latent Graph Inference using Product Manifolds](https://mlsanity.com/paper/2211.16199/) (2022)
- [Robust CUR Decomposition: Theory and Imaging Applications](https://mlsanity.com/paper/2101.05231/) (2021)
- [Ada-NETS: Face Clustering via Adaptive Neighbour Discovery in the Structure Space](https://mlsanity.com/paper/2202.03800/) (2022)
- [Boosting Graph Structure Learning with Dummy Nodes](https://mlsanity.com/paper/2206.08561/) (2022)

## Built on by (most cited first, 9 of 9)

- [The Indra Representation Hypothesis for Multimodal Alignment](https://mlsanity.com/paper/2604.04496/) (2026)
- [NeuroMambaLLM: Dynamic Graph Learning of fMRI Functional Connectivity in Autistic Brains Using Mamba and Language Model Reasoning](https://mlsanity.com/paper/2602.13770/) (2026)
- [Scale-Free Graph-Language Models](https://mlsanity.com/paper/2502.15189/) (2025)
- [FALCON: Feature-Label Constrained Graph Net Collapse for Memory Efficient GNNs](https://mlsanity.com/paper/2312.16542/) (2023)
- [Inference of Sequential Patterns for Neural Message Passing in Temporal Graphs](https://mlsanity.com/paper/2406.16552/) (2024)
- [Boolean Product Graph Neural Networks](https://mlsanity.com/paper/2409.14001/) (2024)
- [Dependency Parsing is More Parameter-Efficient with Normalization](https://mlsanity.com/paper/2505.20215/) (2025)
- [LLMs Underperform Graph-Based Parsers on Supervised Relation Extraction for Complex Graphs](https://mlsanity.com/paper/2604.08752/) (2026)
- [A Unified Perspective for Learning Graph Representations Across Multi-Level Abstractions](https://mlsanity.com/paper/2605.12685/) (2026)

## Abstract (arXiv)

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%).