Fast Nonparametric Inference of Network Backbones for Weighted Graph Sparsification

Network backbones provide useful sparse representations of weighted networks by keeping only their most important links, permitting a range of computational speedups and simplifying network visualizations. A key limitation of existing network backboning methods is that they either require the specification of a free parameter (e.g., significance level) that determines the number of edges to keep in the backbone or impose specific restrictions on the topology of the backbone (e.g., that it is a spanning tree). Here we develop a completely nonparametric framework for inferring the backbone of a weighted network that overcomes these limitations and automatically selects the optimal set of edges to retain using the minimum description length principle. We develop objective functions for global and local network backboning which evaluate the importance of an edge in the context of the whole network and individual node neighborhoods, respectively, and are generalizable to any weight distribution under Bayesian model specifications that fix the average edge weight either exactly or in expectation. We then construct an efficient and provably optimal greedy algorithm to identify the backbone minimizing our objectives, whose run-time complexity is log-linear in the number of edges. We demonstrate our methods by comparing them with existing methods in a range of tasks on real and synthetic networks, finding that both the global and local backboning methods can preserve network connectivity, weight heterogeneity, and spreading dynamics while removing a substantial fraction of edges.