Context-aware Sampling of Large Networks via Graph Representation Learning

Authors: Zhiguang Zhou, Chen Shi, Xilong Shen, Lihong Cai, Haoxuan Wang, Yuhua Liu, Ying Zhao, Wei Chen
Numerous sampling strategies have been proposed to simplify large-scale networks for highly readable visualizations. It is of great challenge to preserve contextual structures formed by nodes and edges with tight relationships in a sampled graph, because they are easily overlooked during the process of sampling due to their irregular distribution and immunity to scale. In this paper, a new graph sampling method is proposed oriented to the preservation of contextual structures. We first utilize a graph representation learning (GRL) model to transform nodes into vectors so that the contextual structures in a network can be effectively extracted and organized. Then, we propose a multi-objective blue noise sampling model to select a subset of nodes in the vectorized space to preserve contextual structures with the retention of relative data densities and relative cluster densities in addition to those significant topology features, such as bridging nodes and graph connections. We also design a visual interface that supports conduct context-aware sampling, compare results with various sampling strategies, and deeply explore large networks. Case studies and quantitative comparisons of sampling results based on real-world datasets have demonstrated the effectiveness of our method in the abstraction and exploration of large networks.