PaperlayerView exact revision on arXiv

Source-linked AI summary

Interpretable and Efficient Heterogeneous Graph Convolutional Network

Yaming Yang, Ziyu Guan, Jianxin Li, Wei Zhao, Jiangtao Cui, Quan Wang

arXiv:2005.13183v3cs.LGcs.SIstat.ML

TL;DR

Existing HIN GCN methods have limited flexibility in exploring task-relevant meta-paths and may incur high costs by constructing intermediate dense graphs. The paper proposes ie-HGCN, a hierarchical object-level and type-level aggregation model that evaluates meta-path usefulness per object while directly processing HINs. The authors report theoretical support for its interpretability and quasi-linear efficiency, alongside superior performance over state-of-the-art methods on three real datasets.

  • Problem

    Existing HIN GCN methods cannot flexibly identify useful meta-paths for each target object and often construct costly intermediate meta-path-based dense graphs.

  • Method

    ie-HGCN projects heterogeneous neighbors into a common semantic space, aggregates them at the object level, and then applies type-level attention directly on the HIN.

  • Results

    The authors report that ie-HGCN evaluates all possible meta-paths within a length limit, provides interpretable personalized usefulness scores, and achieves superior performance over state-of-the-art methods.

  • Takeaways & Limitations

    ie-HGCN combines personalized meta-path evaluation with heterogeneous spectral convolution and avoids intermediate HIN transformation, supporting interpretable and efficient HIN representation learning.

  • Takeaways & Limitations

    For object types without real features, the experiments generate 128-dimensional random vectors, and the method requires features for all object types.

Abstract

from arXiv · show

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.

1 INTRODUCTION

HIN representation learning must capture diverse, task-relevant meta-path proximities while remaining computationally efficient. ie-HGCN addresses these needs through hierarchical aggregation that adaptively evaluates meta-path usefulness without constructing intermediate meta-path graphs.

  • Motivation: HIN representations support tasks such as object classification and link prediction by capturing structural proximities and semantic information.Meta-paths describe higher-order proximities, but their usefulness can vary by task and target object.
  • Limitations of Existing Methods: Existing methods often require user-specified or restricted meta-paths, limiting their ability to exploit all possible structural proximities.Restrictions include symmetric, fixed-length, or same-type-ending meta-paths.
  • Limitations of Existing Methods: Many HIN methods fail to distinguish meta-path importance, although different meta-paths may have unequal usefulness for a specific task.This limits personalized assessment of structural relevance.
  • Efficiency: Existing approaches may construct intermediate meta-path-based dense graphs, increasing computational cost on large HINs.Efficiency is important because real-world HINs contain many objects and links and GPU memory is limited.
  • Proposed Approach: ie-HGCN directly processes the HIN through object-level followed by type-level aggregation to learn task-specific object representations.Relation-specific and self-projection matrices first map representations into a common semantic space, while normalized adjacency performs neighbor aggregation.
  • Proposed Approach: The architecture adaptively learns personalized meta-path importance distributions while avoiding meta-path graph construction and large-scale neighborhood softmax calculations.The paper reports theoretical analysis and experiments on three benchmark datasets against state-of-the-art methods.

2 RELATED WORK

Related work comprises HIN embedding methods and GCN-based methods. These approaches differ in the structural proximities they preserve, how they use meta-paths, and how they aggregate information across heterogeneous graphs.

  • HIN Embedding Methods: HIN embedding methods learn representations non-parametrically by preserving selected structural properties, including first-order, second-order, or meta-path-based proximities.Examples include EOE, PTE, HEER, HIN2Vec, and HINE.
  • GCNs for Homogeneous Graphs: Homogeneous GCN research progressed from spectral graph convolution to Chebyshev-polynomial approximations and first-order graph convolution.These developments motivate extensions of convolutional methods to heterogeneous graphs.
  • GCNs for Heterogeneous Graphs: Several HIN GCN methods transform HINs into homogeneous graphs based on user-specified or structurally restricted meta-paths before applying GCNs.They then combine representations using attention or concatenation.
  • GCNs for Heterogeneous Graphs: MAGNN performs intra-meta-path aggregation over path instances before aggregating information across meta-paths.This represents another strategy for incorporating heterogeneous structural information into GCN-style models.

3 PROBLEM FORMULATION

The paper formalizes HINs, their schemas and meta-paths, and the representation-learning objective. The formulation defines heterogeneous objects and relations together with the structural representations to be learned for downstream tasks.

  • HIN Definitions: An HIN is G = (V, E, φ, ψ), with object and link type mappings and more than two combined object or relation types.VΩ denotes objects of type Ω, while NΩ denotes object types linked to Ω.
  • HIN Definitions: A network schema is a directed graph over object types whose edges represent relations, serving as a meta-template for the HIN.It abstracts the type-level organization of the heterogeneous network.
  • Meta-Paths: A meta-path is a schema path whose composite relation is formed by composing its constituent relations; its length equals the number of relations.Meta-paths may be symmetric or asymmetric, and concrete realizations are path instances.
  • DBLP Example: The DBLP example contains Paper, Author, Conference, and Term object types connected by six directed relations.For Paper, neighboring types are Conference, Author, and Term; APA is symmetric whereas CPA is asymmetric, both of length 2.
  • Learning Objective: HIN representation learning seeks one representation matrix per object type that captures structural proximities and semantic information useful for a specified task.For type Ω, XΩ has one row per object and representation dimensionality dΩ much smaller than |VΩ|.

4 MODEL

ie-HGCN processes heterogeneous neighborhoods through projection, object-level aggregation, and type-level attention. Stacked layers support personalized meta-path importance estimation while avoiding object-level attention and intermediate HIN transformations.

  • Layer Architecture: Each layer contains blocks for object types and applies projection, object-level aggregation, and type-level aggregation.Neighbor and self representations are projected into a common semantic space before aggregation; final block outputs feed the next layer.
  • Projection: Relation-specific and dummy self-relation projections align neighbor and target representations in the target type’s common semantic space.For neighbor type Γ, WΓ→Ω projects HΓ, while WSelf−Ω projects HΩ; the resulting representations share dimension d′Ω.
  • Object-level Aggregation: Row-normalized adjacency matrices aggregate projected representations within each neighbor type without applying attention over individual objects.For each target object, normalized adjacency coefficients linearly combine corresponding projected neighbor representations; this avoids softmax computation in large neighborhoods.
  • Theoretical Properties: Including self-representation in the aggregation enables evaluation of all meta-paths within the model-depth length limit.The architecture’s stacked object-level and type-level aggregations provide probabilistic importance scores for meta-paths on a per-object basis.
  • Theoretical Properties: The object-level operation is theoretically connected to spectral graph convolution on bipartite graphs despite non-square cross-type adjacency matrices.The projection matrices act as convolution filters in the heterogeneous spectral convolution interpretation.
  • Type-level Aggregation: Type-level attention learns the relative importance of self and neighbor-type representations for each target object.The convolved representations serve as keys and values, while the target’s self-representation supplies the query, enabling personalized importance estimation.

11 end

ie-HGCN evaluates task-specific importance for all meta-paths shorter than the model depth while directly performing heterogeneous graph convolution. Its hierarchical aggregation supports personalized path preferences and linear complexity in HIN size.

  • Automatically learning useful meta-paths: ie-HGCN evaluates the task-specific importance of all meta-paths with length less than the model depth.The theorem defines the evaluated paths as those ending with the target object type.
  • Automatically learning useful meta-paths: Each target object can have personalized meta-path preferences through object-specific attention coefficients.A meta-path score for a target object sums its path-instance scores, formed from selection probabilities along the path.
  • Connection to spectral graph convolution: The heterogeneous convolution can be connected to spectral graph convolution on augmented bipartite graphs and approximated with localized Chebyshev filters.The approximation uses K-localized filters and, following GCN, sets K = 1 while stacking layers.
  • Efficiency: O(N · (|V| + |E|)) is the overall time complexity, linear in the total number of objects and links in the HIN.This avoids the at-least-square-time commuting-matrix computations required by many previous methods.

5 EXPERIMENTS

The experiments evaluate ie-HGCN on three publicly available real-world HIN datasets using shared computational and dataset documentation. The datasets differ in object types, relations, labels, and feature availability.

  • Experimental datasets: Three publicly available HIN datasets—IMDB, ACM, and DBLP—are used to evaluate ie-HGCN.The experiments compare the method on networks constructed from real-world data.
  • Experimental setup: The experiments use a server with 16 Intel Xeon E5-2620 CPUs, one Nvidia GeForce GTX 1080Ti GPU, and 128GB main memory.Unless otherwise specified, experiments run on GPU to accelerate computation.
  • IMDB: IMDB contains Movie, Actor, User, and Director objects, with movie labels for comedy, documentary, drama, and horror.Movie objects use 14 numerical and categorical features after task-irrelevant features are removed.
  • ACM: ACM contains Paper, Author, and Subject objects, with papers labeled as data mining, database, or computer network.Paper features are TF-IDF representations of titles.
  • DBLP: DBLP contains Paper, Author, Conference, and Term objects, with authors labeled according to four research areas.Paper titles are excluded as real features because they provide information similar to connected terms.

5.2 Baselines

The baseline study compares ie-HGCN with homogeneous GCN methods, HIN embedding and convolutional methods, GTN, and an ie-HGCN variant without type-level attention.

  • Compared methods: The comparison includes three homogeneous GCN methods, one HIN embedding method, five HIN GCN methods, and ie-HGCNmean.The homogeneous methods are GraphSAGE, GCN, and GAT; the HIN methods include HAN, HAHE, DHNE, HetSANN, and GTN.
  • Homogeneous baselines: GraphSAGE, GCN, and GAT are evaluated on homogeneous graphs constructed from selected meta-paths.GraphSAGE uses a convolutional mean aggregator, while GAT uses node-level attention.
  • HIN embedding baseline: metapath2vec performs random walks guided by user-specified meta-paths and cannot learn their importance.It is described as a state-of-the-art HIN embedding baseline.
  • HIN baselines: HAN transforms an HIN into homogeneous graphs for given symmetric meta-paths, whereas HAHE initializes target features with meta-path structural features and cannot exploit object features.Both methods use meta-path-based processing before attention-based fusion or aggregation.
  • HIN baselines: DHNE considers only fixed-length meta-paths and cannot learn meta-path importance, while HetSANN directly aggregates heterogeneous neighbors with sparse attention.GTN computes graphs for possible meta-paths and then performs graph convolution; ie-HGCNmean replaces type-level attention with an element-wise mean.

5.3 Hyper-parameter Settings

The experiments use shared data splits and validation-based hyperparameter tuning, with ie-HGCN configured using five layers and progressively smaller hidden dimensions. Baselines use established meta-path choices where required.

  • Data splits: For x ∈ {20, 40, 60, 80}, x% of objects form the training set, while the remainder is split equally between validation and test sets.All methods use identical splits for fairness.
  • Hyperparameter tuning: Hyperparameters are tuned on validation data, with settings selected on DBLP reused for ACM and IMDB.The procedure is applied consistently across methods.
  • ie-HGCN settings: ie-HGCN uses 5 layers, hidden dimensions [64, 32, 16, 8], ELU nonlinearity, and type-level attention dimensionality 64.The first layer uses dimensions determined by object features; the listed dimensions apply to the four hidden layers.
  • Baseline settings: Baselines requiring user-specified meta-paths use APA, APTPA, and APCPA on DBLP; PAP and PSP on ACM; and MAM, MUM, and MDM on IMDB.For GraphSAGE, GCN, GAT, and metapath2vec, results are reported from homogeneous graphs built from these paths.

5.4 Object Classification

ie-HGCN achieves the strongest overall object-classification performance and provides interpretable, object-specific meta-path importance estimates. Its type-level attention improves over mean aggregation and identifies task-relevant meta-paths across datasets.

  • ie-HGCN outperforms ie-HGCNmean, indicating that type-level attention improves object-level heterogeneous convolution.
  • ie-HGCN achieves the best overall classification results on DBLP, ACM, and IMDB.
  • GTN performs worse than ie-HGCN because its shared relation weights are less flexible for capturing different objects’ complexity.
  • Global meta-path importance: For DBLP author classification, CPA is the most useful meta-path with an importance score of 0.4228.CPA represents the conferences where authors have published papers.
  • Object-specific importance: ie-HGCN assigns different highest-scoring meta-paths to individual authors, including CPCPA for Yoshua Bengio and CPAPA for Chen Chen.These assignments align with the authors’ conference and coauthor publication patterns.
  • Baseline comparison: Homogeneous baselines typically rely on APCPA because their graph convolutions require symmetric meta-path-based homogeneous graphs, preventing direct use of CPA.
  • Cross-dataset findings: On ACM and IMDB, ie-HGCN discovers task-relevant meta-paths including PSP, PAP, MUM, MAM, and UM.

5.6 Scalability

The scalability study evaluates heterogeneous GCN methods across HINs that grow from 6,183 to 37,791 objects and from 21,308 to 170,794 links. ie-HGCN scales better than DHNE, while GTN has the worst scalability and several methods exceed GPU memory limits.

  • The scalability evaluation uses eight HIN scales ranging from 6,183 to 37,791 objects and 21,308 to 170,794 links.
  • ie-HGCN is more efficient than DHNE because type-level attention uses fewer parameters than hidden-representation concatenation.
  • GTN shows the worst scalability because of its square time complexity.
  • HAHE, HAN, and GTN cannot run on large-scale HINs because they exceed 12 GB of GPU memory.

5.7 Depth Study

The depth study varies ie-HGCN from 2 to 9 layers on DBLP and examines attention hidden dimensionalities from 8 to 512. Performance generally improves initially with capacity, then declines when overfitting emerges.

  • The depth study evaluates eight ie-HGCN instances with layers increasing from 2 to 9 on DBLP.Each instance is randomly run 10 times, with average Micro F1 and Macro F1 reported.
  • Increasing attention hidden dimensionality from 8 to 512 produces an initial performance increase followed by decline.The decline is attributed to overfitting.
  • DBLP performance is not very sensitive to attention dimensionality, whereas Macro F1 is more sensitive on ACM and IMDB.The difference is linked to skewed classes in ACM and IMDB.

6 CONCLUSION

ie-HGCN combines projection, object-level aggregation, and type-level attention to learn HIN representations while connecting heterogeneous convolution to spectral graph convolution. Experiments and scalability analysis support its effectiveness, interpretability, and efficiency.

  • ie-HGCN projects heterogeneous neighbors into a common semantic space, aggregates them at the object level, and then applies type-level attention.
  • The first two steps intrinsically perform heterogeneous spectral graph convolution on HINs.
  • ie-HGCN evaluates all possible meta-paths and discovers the most useful ones for specific tasks, supporting model interpretability.
  • Theoretical analysis, scalability experiments, and extensive benchmarks support ie-HGCN’s efficiency and superior performance over several state-of-the-art methods.
Loading 2005.13183v3…