Heterogeneous Graph Sparsification for Efficient Representation Learning
This work addresses efficiency challenges in representation learning for heterogeneous graphs, which is incremental as it extends sparsification from homogeneous to heterogeneous graphs.
The paper tackles the problem of applying graph sparsification to heterogeneous graphs like knowledge graphs, which had not been systematically explored, and shows that the proposed sampling-based algorithms improve time and space complexities while achieving comparable or better performance in graph learning tasks.
Graph sparsification is a powerful tool to approximate an arbitrary graph and has been used in machine learning over homogeneous graphs. In heterogeneous graphs such as knowledge graphs, however, sparsification has not been systematically exploited to improve efficiency of learning tasks. In this work, we initiate the study on heterogeneous graph sparsification and develop sampling-based algorithms for constructing sparsifiers that are provably sparse and preserve important information in the original graphs. We have performed extensive experiments to confirm that the proposed method can improve time and space complexities of representation learning while achieving comparable, or even better performance in subsequent graph learning tasks based on the learned embedding.