Heterogeneous Graph Embedding Made More Practical

Heterogeneous graphs are prevalent in the real-world applications, and a key analytical task for such graphs is heterogeneous graph embedding, which seeks to represent each heterogeneous graph as a low-dimensional feature vector while preserving its inherent heterogeneity. Although the traditional methods have achieved significant advancements, they predominantly rely on modeling basic pairwise relationships between nodes, limiting their ability to capture the intricate structures and interactions present in heterogeneous graphs. Recent studies have begun incorporating simplicial complexes, which effectively encode higher-order interactions, into the Graph Neural Network (GNN) framework. However, these GNN-based approaches are computationally intensive due to the substantial parameter training involved. To address these challenges, we propose HGSketch, a practical heterogeneous graph embedding algorithm that balances performance and temporal efficiency without the powerful workhorses. By leveraging the Locality Sensitive Hashing (LSH) technique, HGSketch efficiently captures higher-order information from simplicial complexes locally and globally without the need for parameter learning. The extensive experiment results display that HGSketch achieves performance comparable to the state-of-the-art learning-based methods, while significantly reducing runtime by a factor of up to 1223.86; also, HGSketch generally outperforms the state-of-the-art LSH-based methods. We have released the source code and the datasets in https://github.com/AIandBD/graph-hashing/tree/main/HGSketch.