# Principle of Relevant Information for Graph Sparsification

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 61 references that are in the map.
- First posted on arXiv 31 May 2022.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Parameterized Explainer for Graph Neural Network](https://mlsanity.com/paper/2011.04573/) (2020)
- [Graph Information Bottleneck](https://mlsanity.com/paper/2010.12811/) (2020)
- [How to learn a graph from smooth signals](https://mlsanity.com/paper/1601.02513/) (2016)
- [Cooperative Game Theory Approaches for Network Partitioning](https://mlsanity.com/paper/1707.03587/) (2017)
- [Graph Information Bottleneck for Subgraph Recognition](https://mlsanity.com/paper/2010.05563/) (2020)
- [Graph Coarsening with Neural Networks](https://mlsanity.com/paper/2102.01350/) (2021)
- [Layer aggregation and reducibility of multilayer interconnected networks](https://mlsanity.com/paper/1405.0425/) (2014)
- [A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarsening](https://mlsanity.com/paper/1902.09702/) (2019)
- [BrainNNExplainer: An Interpretable Graph Neural Network Framework for Brain Network based Disease Analysis](https://mlsanity.com/paper/2107.05097/) (2021)
- [Efficient and Scalable Multi-task Regression on Massive Number of Tasks](https://mlsanity.com/paper/1811.05695/) (2018)
- [Fast Incremental von Neumann Graph Entropy Computation: Theory, Algorithm, and Applications](https://mlsanity.com/paper/1805.11769/) (2018)
- [Brain Network Construction and Classification Toolbox (BrainNetClass)](https://mlsanity.com/paper/1906.09908/) (2019)
- [Graph Sparsification with Generative Adversarial Network](https://mlsanity.com/paper/2009.11736/) (2020)
- [PRI-VAE: Principle-of-Relevant-Information Variational Autoencoders](https://mlsanity.com/paper/2007.06503/) (2020)

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

- [Graph Distillation with Eigenbasis Matching](https://mlsanity.com/paper/2310.09202/) (2023)
- [Combating Bilateral Edge Noise for Robust Link Prediction](https://mlsanity.com/paper/2311.01196/) (2023)
- [Self-organization Preserved Graph Structure Learning with Principle of Relevant Information](https://mlsanity.com/paper/2301.00015/) (2022)
- [Two Trades is not Baffled: Condensing Graph via Crafting Rational Gradient Matching](https://mlsanity.com/paper/2402.04924/) (2024)
- [IGNN-Solver: A Graph Neural Solver for Implicit Graph Neural Networks](https://mlsanity.com/paper/2410.08524/) (2024)
- [Spectral Neural Graph Sparsification](https://mlsanity.com/paper/2510.27474/) (2025)
- [Knowledge Graph Pruning for Recommendation](https://mlsanity.com/paper/2405.11531/) (2024)
- [A Novel Sparse Regularizer](https://mlsanity.com/paper/2301.07285/) (2023)
- [Robust Learning on Heterogeneous Graphs with Heterophily: A Graph Structure Learning Approach](https://mlsanity.com/paper/2604.27387/) (2026)

## Abstract (arXiv)

Graph sparsification aims to reduce the number of edges of a graph while maintaining its structural properties. In this paper, we propose the first general and effective information-theoretic formulation of graph sparsification, by taking inspiration from the Principle of Relevant Information (PRI). To this end, we extend the PRI from a standard scalar random variable setting to structured data (i.e., graphs). Our Graph-PRI objective is achieved by operating on the graph Laplacian, made possible by expressing the graph Laplacian of a subgraph in terms of a sparse edge selection vector w. We provide both theoretical and empirical justifications on the validity of our Graph-PRI approach. We also analyze its analytical solutions in a few special cases. We finally present three representative real-world applications, namely graph sparsification, graph regularized multi-task learning, and medical imaging-derived brain network classification, to demonstrate the effectiveness, the versatility and the enhanced interpretability of our approach over prevalent sparsification techniques. Code of Graph-PRI is available at https://github.com/SJYuCNEL/PRI-Graphs