  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
