# Informative Graph Structure Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 33 of its 52 references that are in the map.
- First posted on arXiv 16 May 2026.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Graph Structure Learning for Robust Graph Neural Networks](https://mlsanity.com/paper/2005.10203/) (2020)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [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)
- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [A Unified Lottery Ticket Hypothesis for Graph Neural Networks](https://mlsanity.com/paper/2102.06790/) (2021)
- [Towards Unsupervised Deep Graph Structure Learning](https://mlsanity.com/paper/2201.06367/) (2022)
- [How Powerful are K-hop Message Passing Graph Neural Networks](https://mlsanity.com/paper/2205.13328/) (2022)
- [Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited](https://mlsanity.com/paper/2202.03580/) (2022)
- [Factorized Contrastive Learning: Going Beyond Multi-view Redundancy](https://mlsanity.com/paper/2306.05268/) (2023)
- [Graph Mixture of Experts: Learning on Large-Scale Graphs with Explicit Diversity Modeling](https://mlsanity.com/paper/2304.02806/) (2023)
- [Graph-Revised Convolutional Network](https://mlsanity.com/paper/1911.07123/) (2019)
- [SE-GSL: A General and Effective Graph Structure Learning Framework through Structural Entropy Optimization](https://mlsanity.com/paper/2303.09778/) (2023)
- [A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarsening](https://mlsanity.com/paper/1902.09702/) (2019)
- [OpenGSL: A Comprehensive Benchmark for Graph Structure Learning](https://mlsanity.com/paper/2306.10280/) (2023)
- [Early-Bird GCNs: Graph-Network Co-Optimization Towards More Efficient GCN Training and Inference via Drawing Early-Bird Lottery Tickets](https://mlsanity.com/paper/2103.00794/) (2021)
- [Compact Graph Structure Learning via Mutual Information Compression](https://mlsanity.com/paper/2201.05540/) (2022)
- [DSLR: Diversity Enhancement and Structure Learning for Rehearsal-based Graph Continual Learning](https://mlsanity.com/paper/2402.13711/) (2024)
- [Sketch-GNN: Scalable Graph Neural Networks with Sublinear Training Complexity](https://mlsanity.com/paper/2406.15575/) (2024)
- [Beyond Redundancy: Information-aware Unsupervised Multiplex Graph Structure Learning](https://mlsanity.com/paper/2409.17386/) (2024)
- [Dimensionwise Separable 2-D Graph Convolution for Unsupervised and Semi-Supervised Learning on Graphs](https://mlsanity.com/paper/1909.12038/) (2019)
- [Self-Guided Robust Graph Structure Refinement](https://mlsanity.com/paper/2402.11837/) (2024)
- [Generating Graphs via Spectral Diffusion](https://mlsanity.com/paper/2402.18974/) (2024)
- [Contrastive Graph Condensation: Advancing Data Versatility through Self-Supervised Learning](https://mlsanity.com/paper/2411.17063/) (2024)

## Abstract (arXiv)

The quality of graph-structured data is fundamental to the success of modern graph analysis techniques such as Graph Neural Networks (GNNs). However, real-world graph data is often suboptimal, suffering from issues such as noise and incomplete connections. Graph Structure Learning (GSL) has emerged as a promising technique that adaptively optimizes node connections. However, we observe that the effectiveness of GSL often comes at the cost of a dramatic expansion in edge count, resulting in significant storage and computational overhead. In this work, we reveal that this limitation stems from the prevalent use of similarity-based edge construction, which predominantly connects highly similar neighbors based on their embeddings, introducing substantial structure redundancy. To address this, we propose a novel Informative Graph Structure Learning method (InGSL), which jointly considers both similarity and diversity in edge construction by incorporating a mutual-information-guided learning strategy. Notably, InGSL serves as a plug-in module that can be seamlessly integrated into existing GSL frameworks. Through extensive experiments on six representative GSL methods, we demonstrate that InGSL achieves significant performance improvements at a reduced number of edges.