Principle of Relevant Information for Graph Sparsification
This work addresses the problem of efficiently simplifying graphs for researchers and practitioners in fields like machine learning and medical imaging, though it appears incremental as it adapts an existing principle to a new domain.
The paper tackles graph sparsification by proposing a new information-theoretic formulation based on the Principle of Relevant Information, extending it to graphs and applying it to reduce edges while preserving structural properties. It demonstrates effectiveness in applications like graph sparsification, multi-task learning, and brain network classification, showing enhanced interpretability over existing methods.
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 $\mathbf{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