GraphMSE: Efficient Meta-path Selection in Semantically Aligned Feature Space for Graph Neural Networks

Yi Li, Yilun Jin, Guojie Song, Zihao Zhu, Chuan Shi, Yiming Wang

In the realm of Graph Neural Networks (GNNs), Heterogeneous Information Networks (HINs)—graphs containing diverse types of nodes and edges—serve as the gold standard for representing complex real-world data, such as academic citations or e-commerce transactions. However, leveraging HINs effectively typically requires "meta-path engineering": the manual definition of sequences like Author-Paper-Author to capture specific semantics.

At AAAI-21, researchers from Peking University and their collaborators introduced GraphMSE, a framework that automates this tedious process while being orders of magnitude faster than previous state-of-the-art methods. GraphMSE replaces exhaustive matrix multiplications with intelligent sampling and introduces a novel "semantic feature space alignment" technique, achieving a staggering 240x speedup in training time while maintaining or exceeding state-of-the-art accuracy.

The Challenge of Meta-path Selection

To extract meaning from an HIN, researchers use meta-paths to define relationships. For example, in a movie database, a Movie-Actor-Movie path might represent "co-starring" relationships. Traditionally, these paths are hand-picked by domain experts. While recent models like Graph Transformer Networks (GTN) attempted to automate this selection, they faced two significant hurdles:

  1. Computational Scalability: GTN uses heavy matrix multiplications to enumerate every possible meta-path instance, which fails to scale to large graphs.
  2. Feature Heterogeneity: Real-world nodes have different features (e.g., a "Movie" node might have a text description, while an "Actor" node has demographic data). Most existing models assume all nodes share the same feature space, which is rarely true in practice.

The GraphMSE Framework

GraphMSE (Graph Meta-path Selection and Embedding) addresses these issues through a four-stage pipeline: sampling, embedding, alignment, and selection.

The overall architecture of GraphMSE, illustrating the flow from HIN sampling to meta-path selection.

1. Efficient Sampling

Instead of calculating every path instance, GraphMSE samples a subset of "candidate" nodes and uses Breadth-First Search (BFS) to sample meta-path instances. This approach is analogous to how GraphSAGE brought scalability to homogeneous graphs, allowing the model to handle massive datasets that would otherwise cause out-of-memory (OOM) errors.

2. Injective Embedding

The model concatenates node features along a path and passes them through a "SUM-MLP" encoder. The authors provide a mathematical proof that this "SUM" aggregation is "injective," meaning it preserves unique structural information—such as the number of neighbors—that standard "MEAN" aggregation often loses. In HINs, the frequency of a meta-path (e.g., how many times an author publishes at a specific conference) is a vital signal that SUM aggregation captures effectively.

3. Semantic Feature Space Alignment

This is the paper's most novel contribution. To help the model compare different meta-paths fairly, GraphMSE uses discriminators to ensure that specific segments of the embedding vector always correspond to specific node types.

The Semantic Feature Space Alignment mechanism ensures that embeddings are disentangled and comparable across different meta-paths.

As shown in the figure above, this process "disentangles" the feature space. Without alignment, "Author" information might end up in the first 10 dimensions of one meta-path embedding but the last 10 dimensions of another, confusing the selection mechanism. Alignment provides a "common language" for the selector, ensuring that the model compares "apples to apples."

4. Attention-based Selection

Finally, a graph attention layer learns weights for each candidate meta-path. The paths with the highest weights are deemed the most "important," allowing the model to effectively select the optimal meta-paths for the specific downstream task.

Empirical Results and Insights

The authors evaluated GraphMSE on three standard HIN benchmarks: ACM (Papers, Authors, Subjects), DBLP (Authors, Papers, Conferences), and IMDB (Movies, Actors, Directors).

  • Performance: GraphMSE consistently outperformed SOTA baselines like HAN, MAGNN, and GTN in node classification tasks across all datasets.
  • Efficiency: On the DBLP dataset, GraphMSE reached its lowest validation error in just 22.9 seconds on a CPU, compared to 5,527 seconds for GTN—a roughly 240x speedup. On GPUs, GTN often ran out of memory, while GraphMSE remained highly efficient.
  • Robustness: To test the alignment technique, the authors created "shuffled" datasets where feature indices were randomized for different node types. While standard GCNs and GTN saw performance drops of up to 10%, GraphMSE maintained its accuracy, proving the effectiveness of its semantic alignment.

Conclusion

GraphMSE demonstrates that exhaustive enumeration is not necessary for effective meta-path selection. By combining smart sampling with semantic alignment, the framework provides a scalable and robust solution for heterogeneous graph representation learning. Future work may involve pruning "weak" meta-paths post-training to further optimize inference and exploring more complex sampling strategies to enhance model capability.

Summary updated

Abstract

Heterogeneous information networks (HINs) are ideal for describing real-world data with different types of entities and relationships. To carry out machine learning on HINs, meta-paths are widely utilized to extract semantics with pre-defined patterns, and models such as graph convolutional networks (GCNs) are thus enabled. However, previous works generally assume a fixed set of meta-paths, which is unrealistic as real-world data are overwhelmingly diverse. Therefore, it is appealing if meta-paths can be automatically selected given an HIN, yet existing works aiming at such problem possess drawbacks, such as poor efficiency and ignoring feature heterogeneity. To address these drawbacks, we propose GraphMSE, an efficient heterogeneous GCN combined with automatic meta-path selection. Specifically, we design highly efficient meta-path sampling techniques, and then injectively project sampled meta-path instances to vectors. We then design a novel semantic feature space alignment, aiming to align the meta-path instance vectors and hence facilitate meta-path selection. Extensive experiments on real-world datasets demonstrate that GraphMSE outperforms state-of-the-art counterparts, figures out important meta-paths, and is dramatically (e.g. 200 times) more efficient.
BibTeX
@inproceedings{li2021graphmse,
  author = {Yi Li and Yilun Jin and Guojie Song and Zihao Zhu and Chuan Shi and Yiming Wang},
  title = {{GraphMSE: Efficient Meta-path Selection in Semantically Aligned Feature Space for Graph Neural Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i5.16544},
}
Figure