Density-Preserving Heterogeneous Graph Sparsification for Representation Learning

Graph sparsification is the task of compressing a graph with fewer edges or nodes while preserving its essential structural characteristics. It has been used in machine learning to significantly improve the computational efficiency over homogeneous graphs. In heterogeneous graphs with diverse types of nodes and edges, however, sparsification has not been extensively explored. This work develops sparsification methods that can preserve edge density across different edge types and/or edge importance in terms of eigenvector centrality, improving over existing methods. The methods have been tested on real-world networks, and the results indicate great improvements in the computational efficiency and memory cost.