Principle of Relevant Information for Graph Sparsification

arXiv2206.00118MaRDI QIDQ6400737

Author name not available (Why is that?)

Publication date: 31 May 2022

Abstract: 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 $mathbfw$. 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

Has companion code repository: https://github.com/sjyucnel/pri-graphs

This page was built for publication: Principle of Relevant Information for Graph Sparsification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6400737)