# Compact Graph Structure Learning via Mutual Information Compression

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 47 references that are in the map.
- First posted on arXiv 14 Jan 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [Momentum Contrast for Unsupervised Visual Representation Learning](https://mlsanity.com/paper/1911.05722/) (2019)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Deep Graph Infomax](https://mlsanity.com/paper/1809.10341/) (2018)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Contrastive Multi-View Representation Learning on Graphs](https://mlsanity.com/paper/2006.05582/) (2020)
- [Graph Contrastive Learning with Adaptive Augmentation](https://mlsanity.com/paper/2010.14945/) (2020)
- [Graph Structure Learning for Robust Graph Neural Networks](https://mlsanity.com/paper/2005.10203/) (2020)
- [A simple neural network module for relational reasoning](https://mlsanity.com/paper/1706.01427/) (2017)
- [Wiki-CS: A Wikipedia-Based Benchmark for Graph Neural Networks](https://mlsanity.com/paper/2007.02901/) (2020)
- [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)
- [Position-aware Graph Neural Networks](https://mlsanity.com/paper/1906.04817/) (2019)
- [Graph Information Bottleneck](https://mlsanity.com/paper/2010.12811/) (2020)
- [Reinforcement Learning Based Graph-to-Sequence Model for Natural Question Generation](https://mlsanity.com/paper/1908.04942/) (2019)

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

- [Graph Data Augmentation for Graph Machine Learning: A Survey](https://mlsanity.com/paper/2202.08871/) (2022)
- [GSLB: The Graph Structure Learning Benchmark](https://mlsanity.com/paper/2310.05174/) (2023)
- [GraphEdit: Large Language Models for Graph Structure Learning](https://mlsanity.com/paper/2402.15183/) (2024)
- [OpenGSL: A Comprehensive Benchmark for Graph Structure Learning](https://mlsanity.com/paper/2306.10280/) (2023)
- [Probabilistically Rewired Message-Passing Neural Networks](https://mlsanity.com/paper/2310.02156/) (2023)
- [DeepRicci: Self-supervised Graph Structure-Feature Co-Refinement for Alleviating Over-squashing](https://mlsanity.com/paper/2401.12780/) (2024)
- [Probabilistic Graph Rewiring via Virtual Nodes](https://mlsanity.com/paper/2405.17311/) (2024)
- [Self-Guided Robust Graph Structure Refinement](https://mlsanity.com/paper/2402.11837/) (2024)
- [Demystifying Higher-Order Graph Neural Networks](https://mlsanity.com/paper/2406.12841/) (2024)
- [Enhancing the Influence of Labels on Unlabeled Nodes in Graph Convolutional Networks](https://mlsanity.com/paper/2411.02279/) (2024)
- [Uncertainty-Aware Graph Structure Learning](https://mlsanity.com/paper/2502.12618/) (2025)
- [Semi-Supervised Heterogeneous Graph Learning with Multi-level Data Augmentation](https://mlsanity.com/paper/2212.00024/) (2022)
- [Bridging Large Language Models and Graph Structure Learning Models for Robust Representation Learning](https://mlsanity.com/paper/2410.12096/) (2024)
- [Graph Structure Refinement with Energy-based Contrastive Learning](https://mlsanity.com/paper/2412.17856/) (2024)
- [Towards Scalable Web Accessibility Audit with MLLMs as Copilots](https://mlsanity.com/paper/2511.03471/) (2025)
- [Training Robust Graph Neural Networks by Modeling Noise Dependencies](https://mlsanity.com/paper/2502.19670/) (2025)
- [Toward Data-centric Directed Graph Learning: An Entropy-driven Approach](https://mlsanity.com/paper/2505.00983/) (2025)
- [When LLM Agents Meet Graph Optimization: An Automated Data Quality Improvement Approach](https://mlsanity.com/paper/2510.08952/) (2025)
- [Graph Topology Information Enhanced Heterogeneous Graph Representation Learning](https://mlsanity.com/paper/2604.05732/) (2026)
- [Informative Graph Structure Learning](https://mlsanity.com/paper/2605.16809/) (2026)

## Abstract (arXiv)

Graph Structure Learning (GSL) recently has attracted considerable attentions in its capacity of optimizing graph structure as well as learning suitable parameters of Graph Neural Networks (GNNs) simultaneously. Current GSL methods mainly learn an optimal graph structure (final view) from single or multiple information sources (basic views), however the theoretical guidance on what is the optimal graph structure is still unexplored. In essence, an optimal graph structure should only contain the information about tasks while compress redundant noise as much as possible, which is defined as "minimal sufficient structure", so as to maintain the accurancy and robustness. How to obtain such structure in a principled way? In this paper, we theoretically prove that if we optimize basic views and final view based on mutual information, and keep their performance on labels simultaneously, the final view will be a minimal sufficient structure. With this guidance, we propose a Compact GSL architecture by MI compression, named CoGSL. Specifically, two basic views are extracted from original graph as two inputs of the model, which are refinedly reestimated by a view estimator. Then, we propose an adaptive technique to fuse estimated views into the final view. Furthermore, we maintain the performance of estimated views and the final view and reduce the mutual information of every two views. To comprehensively evaluate the performance of CoGSL, we conduct extensive experiments on several datasets under clean and attacked conditions, which demonstrate the effectiveness and robustness of CoGSL.