Abstract
Graph sparsification is a powerful tool to approximate an arbitrary graph and has been used in machine learning over homogeneous graphs. In heterogeneous graphs (HGs) such as knowledge graphs, however, sparsification has not been systematically exploited to improve the 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 the time and space complexities of representation learning while achieving comparable, or even better, performance in subsequent graph learning tasks based on the learned embeddings.
Introduction
Heterogeneous graphs (HGs) are the backbone of modern AI, modeling diverse relationships in fields like biology (drug-target interactions) and social media (user-business reviews). Unlike standard graphs, HGs contain multiple types of entities and relations. As these networks scale to millions of nodes and edges—such as the Freebase knowledge graph with over 60 million edges—training mathematical representations (embeddings) becomes computationally grueling and memory-intensive.
While sparsification techniques exist for simple graphs, applying them to HGs is risky. Randomly sampling edges can inadvertently delete rare but vital relationship types, effectively "blinding" the model to critical semantic information. This paper introduces the first systematic approach to heterogeneous graph sparsification, designed to shrink massive networks while preserving their essential structural and semantic properties.
Methodology: The Sparsify-Graph Algorithm
The proposed Sparsify-Graph algorithm is a sampling-based approach specifically engineered for the complexities of HGs. It employs several key strategies:
- Type-Aware Sampling: Instead of treating all edges equally, the algorithm iterates through every edge type for every node, ensuring that the diversity of relationships is maintained.
- The $k$-Neighbor Constraint: For a given node and edge type, the algorithm ensures that at least $k$ edges are preserved. This prevents node isolation and ensures that rare relationship types are not lost.
- Degree-Ordered Processing: Nodes are processed in ascending order of their degree. This heuristic prioritizes the connections of low-degree nodes, which are most vulnerable to being disconnected during the thinning process.
The algorithm is highly efficient, with a computational complexity of $O(ktn)$, where $n$ is the number of nodes, $t$ is the number of edge types, and $k$ is the user-defined sparsity parameter.
Experimental Evaluation
The researchers evaluated the method on three diverse, real-world benchmarks: PubMed (63k nodes), Yelp (82k nodes), and Freebase (12M nodes, 62M edges). The method was tested against five different embedding techniques, including random-walk (HIN2Vec), message-passing (HAN, HGT), and relation-learning (ComplEx) models.
Results and Discussion
The experimental results demonstrate that heterogeneous graph sparsification significantly improves efficiency while maintaining, and sometimes even enhancing, model performance.
Efficiency and Memory Gains
Sparsification leads to dramatic reductions in training time and memory usage. On the PubMed dataset, the training time for the HIN2Vec model dropped to less than 44% of the original time across all tested values of $k$. For the ComplEx model, running times were consistently lower than 40% of the baseline at lower sparsity levels.
In large-scale graphs like Yelp and Freebase, memory consumption was reduced to less than 70% of the original requirements, enabling the processing of massive datasets on more modest hardware.
Performance Maintenance and the "Noise Removal" Effect
Despite removing a significant portion of the graph, metrics like AUC and F1-score remained comparable to the full-graph baseline. Surprisingly, models trained on sparsified graphs sometimes outperformed those trained on the full graphs. This suggests that sparsification acts as a filter, removing "noisy" or redundant edges that might otherwise confuse the learning algorithm.
Conclusion
This study confirms that heterogeneous graph sparsification is a powerful technique for improving the efficiency of representation learning. By using type-aware sampling and degree-ordered processing, the Sparsify-Graph algorithm achieves significant time and space savings while preserving the accuracy of downstream tasks. Future work will explore importance-based sampling and end-to-end learning of sparsification strategies.
Summary updated