Interpretable and Efficient Heterogeneous Graph Convolutional Network

Yaming Yang, Ziyu Guan, Jianxin Li, Wei Zhao, Jiangtao Cui, Quan WangIEEE TKDE 2020 · DOI · OpenReview

Abstract

Graph Convolutional Network (GCN) has achieved extraordinary success in learning effective task-specific representations of nodes in graphs. However, regarding Heterogeneous Information Network (HIN), existing HIN-oriented GCN methods still suffer from two deficiencies: (1) they cannot flexibly explore all possible meta-paths and extract the most useful ones for a target object, which hinders both effectiveness and interpretability; (2) they often need to generate intermediate meta-path based dense graphs, which leads to high computational complexity. To address the above issues, we propose an interpretable and efficient Heterogeneous Graph Convolutional Network (ie-HGCN) to learn the representations of objects in HINs. It is designed as a hierarchical aggregation architecture, i.e., object-level aggregation first, followed by type-level aggregation. The novel architecture can automatically extract useful meta-paths for each object from all possible meta-paths (within a length limit), which brings good model interpretability. It can also reduce the computational cost by avoiding intermediate HIN transformation and neighborhood attention. We provide theoretical analysis about the proposed ie-HGCN in terms of evaluating the usefulness of all possible meta-paths, its connection to the spectral graph convolution on HINs, and its quasi-linear time complexity. Extensive experiments on three real network datasets demonstrate the superiority of ie-HGCN over the state-of-the-art methods.

Introduction

Most real-world data—from academic citations to social networks—exists as Heterogeneous Information Networks (HINs), where nodes (e.g., authors, papers, venues) and edges (e.g., "writes," "published in") have different types. To capture high-order relationships, researchers typically use "meta-paths" (e.g., Author-Paper-Author).

However, existing Graph Convolutional Networks (GCNs) for HINs face significant hurdles. First is efficiency: many models calculate "commuting matrices" to represent meta-paths, leading to dense graphs and $O(N^2)$ complexity, which is prohibitive for large-scale data. Second is interpretability and flexibility: most models require manual meta-path selection or apply global weights to relations, failing to capture "personalized" importance for specific nodes.

The ie-HGCN (Interpretable and Efficient Heterogeneous Graph Convolutional Network) addresses these by automatically discovering the most important meta-paths for specific tasks without massive computational overhead.

Methodology

The ie-HGCN architecture employs a hierarchical aggregation strategy that operates in three primary steps:

  1. Projection: Since different node types (e.g., "Author" and "Paper") reside in different feature spaces, the model projects them into a common semantic space using type-specific matrices.
  2. Object-level Aggregation: Instead of constructing complex meta-path graphs, ie-HGCN aggregates information from immediate neighbors of each type separately. This step is mathematically equivalent to spectral graph convolution on bipartite graphs.
  3. Type-level Aggregation (Personalized Attention): This core innovation uses an attention mechanism to weight each neighbor type. Crucially, this attention is "personalized"—the importance of a neighbor type is calculated based on the target node's own features, allowing the model to adaptively "choose" which meta-paths to follow for each specific object.
The architecture of ie-HGCN showing an instance on DBLP and the internal calculation flow of a P block.

By stacking $N$ layers, the model automatically evaluates all possible meta-paths up to length $N$ without explicit calculation.

Key Insights and Results

The model was evaluated on three benchmarks: DBLP (academic), ACM (academic), and IMDB (movies). Key findings include:

  • State-of-the-Art Performance: ie-HGCN consistently outperformed ten major baselines (including HAN, GTN, and HGT) in Micro-F1 and Macro-F1 scores.
  • Quasi-Linear Scalability: By avoiding dense matrix multiplication, its complexity is $O(N \cdot (|V| + |E|))$, scaling linearly with the number of nodes and edges.
  • Automatic Meta-path Discovery: The model "discovers" important paths mathematically by learning weights for neighbor types across layers.
  • Theoretical Grounding: The authors proved that their local aggregation is a valid form of spectral convolution.
Comparison of ie-HGCN properties against other state-of-the-art methods, highlighting its unique combination of automatic meta-path discovery and linear scalability.

Conclusion

The ie-HGCN provides a robust framework for learning in HINs by balancing efficiency with interpretability. While it faces challenges like "over-smoothing" at great depths and dependency on initial features, its ability to perform personalized meta-path discovery at scale marks a significant advancement. Future work includes extending this architecture to dynamic networks and tasks like link prediction.

Summary updated

Abstract

Graph Convolutional Network (GCN) has achieved extraordinary success in learning representations of nodes in graphs. However, regarding Heterogeneous Information Network (HIN), existing HIN-oriented GCN methods still suffer from two deficiencies: (1) they cannot flexibly explore all possible meta-paths and extract the most useful ones for each target object, which hinders both effectiveness and interpretability; (2) before performing aggregation, they often require some additional time-consuming pre-processing operations, which increase the computational complexity. To address the above issues, we propose an interpretable and efficient Heterogeneous Graph Convolutional Network (ie-HGCN) to learn the representations of objects in HINs. It is designed as a hierarchical aggregation architecture, i.e., object-level aggregation and type-level aggregation. The new architecture can automatically evaluate all possible meta-paths within a length limit, and discover and exploit the most useful ones for each target object, i.e., at fine granularity. It also reduces the computational cost by avoiding additional time-consuming pre-processing operations. Theoretical analysis shows its ability to evaluate the usefulness of all possible meta-paths, its connection to the spectral graph convolution on HINs, and its quasi-linear time complexity. Extensive experiments on four real network datasets demonstrate its interpretability, efficiency as well as its superiority against thirteen baselines.
BibTeX
@article{yang2020interpretable,
  author = {Yaming Yang and Ziyu Guan and Jianxin Li and Wei Zhao and Jiangtao Cui and Quan Wang},
  title = {{Interpretable and Efficient Heterogeneous Graph Convolutional Network}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2020},
  doi = {10.1109/tkde.2021.3101356},
}
Figure