Interpretable and Efficient Heterogeneous Graph Convolutional Network

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.Source: §1 · p. 1

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.Source: §1 · pp. 1–2
• 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.Source: §1 · pp. 1–2

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.Source: §1 · pp. 1–2

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.Source: §1 · p. 2
• 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.Source: §1 · pp. 2–3

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.Source: §2 · p. 3

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.Source: §2 · p. 3

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.Source: §2 · p. 3
• 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.Source: §2 · p. 3

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 Ω.Source: §3 · p. 3
• 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.Source: §3 · p. 3

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.Source: §3 · pp. 3–4

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.Source: §3 · p. 4, Figure 1 · p. 4

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Ω|.Source: §3 · p. 4

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.Source: §4 · p. 4, §4.1 · p. 4, §4.3 · p. 6

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′Ω.Source: §4.1 · p. 4

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.Source: §4.2 · p. 5

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.Source: §4.2 · p. 5
• 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.Source: §4.2 · p. 5

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.Source: §4.3 · pp. 5–6

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.Source: §4.5.1 · pp. 6–7
• 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.Source: §4.5.1 · p. 7

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.Source: §4.5.2 · p. 7

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.Source: §4.5.3 · p. 8

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.Source: §5 · p. 8

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.Source: §5 · p. 8

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.Source: §5.1 · p. 8

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.Source: §5.1 · p. 8

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.Source: §5.1 · pp. 8–9

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.Source: §5.2 · p. 9

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.Source: §5.2 · p. 9

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.Source: §5.2 · p. 9

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.Source: §5.2 · p. 9
• 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.Source: §5.2 · p. 9

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.Source: §5.3 · p. 9

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.Source: §5.3 · p. 9

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.Source: §5.3 · p. 9

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.Source: §5.3 · p. 9

• ie-HGCN outperforms ie-HGCNmean, indicating that type-level attention improves object-level heterogeneous convolution.Source: §5.4 · p. 10
• ie-HGCN achieves the best overall classification results on DBLP, ACM, and IMDB.Source: §5.4 · p. 10
• GTN performs worse than ie-HGCN because its shared relation weights are less flexible for capturing different objects’ complexity.Source: §5.4 · p. 10

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.Source: §5.5 · pp. 10–11

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.Source: §5.5 · p. 11

Baseline comparison

• Homogeneous baselines typically rely on APCPA because their graph convolutions require symmetric meta-path-based homogeneous graphs, preventing direct use of CPA.Source: §5.5 · p. 11

Cross-dataset findings

• On ACM and IMDB, ie-HGCN discovers task-relevant meta-paths including PSP, PAP, MUM, MAM, and UM.Source: §5.5 · p. 11

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

• 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.Source: §5.7 · p. 12
• Increasing attention hidden dimensionality from 8 to 512 produces an initial performance increase followed by decline.The decline is attributed to overfitting.Source: §5.8 · p. 12
• 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.Source: §5.8 · p. 12

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