Generic network sparsification via degree- and subgraph-based edge sampling

Network (or graph) sparsification accelerates many downstream analyses. For graph sparsification, sampling methods derived from local heuristic considerations are common in practice, due to their efficiency in generating sparse subgraphs using only local information. Filtering-based edge sampling is the most typical approach in this respect, yet it heavily depends on an appropriate definition of edge importance. Instead, we propose a generalized node-focused edge sampling framework by preserving scaled/expected local node characteristics. Apart from expected degrees, these local node characteristics include the expected number of triangles and the expected number of non-closed wedges associated with a node. From a technical point of view, we adapt a game-theoretic sampling method from uncertain graph generation to obtain sparse subgraphs that approximate the expected local properties. We include a tolerance threshold for much faster convergence. Within this framework, we provide appropriate algorithmic variants for sparsification. Moreover, we propose a network measure called tri-wedge assortativity for the selection of the most suitable variant when sparsifying a given network. Extensive experimental studies on functional climate, observed real-world, and synthetic networks show the effectiveness of our method in preserving overall structural network properties – on average consistently better than the state of the art.