Alessio Borgi

Alessio Borgi

PhD in Graph Neural Networks and Generative AI ๐Ÿ‘จ๐Ÿปโ€๐Ÿ’ป๐Ÿค–

Heterogeneous Graphs: When Nodes and Edges Have Types

5 minute read

Published:

TL;DR: A heterogeneous graph has multiple node types and edge types. Standard GNNs use a single message function and aggregation โ€” they cannot differentiate a "cites" edge from an "is-authored-by" edge. Handling heterogeneity requires type-specific message functions, meta-path decomposition, or relation-aware aggregation.
Heterogeneous attention network
Heterogeneous graph with multiple node and edge types (Wang et al., 2019)
Key Insight: A standard GNN is like a phone directory that treats every contact the same โ€” it cannot tell your doctor from your friend. A heterogeneous GNN reads the type tag on every node and edge, applying different transformations to "doctor" and "friend" relationships. The type structure often carries as much information as the topology itself.

What Is a Heterogeneous Graph?

A heterogeneous graph (or heterogeneous information network, HIN) is defined as:

\[ G = \bigl(V,\; E,\; \tau,\; \phi\bigr), \qquad \tau : V \to \mathcal{A}, \qquad \phi : E \to \mathcal{R} \]

where \(\tau\) maps each node to a node type from the type set \(\mathcal{A}\), and \(\phi\) maps each edge to a relation from the relation set \(\mathcal{R}\). The graph is heterogeneous when \(\lvert\mathcal{A}\rvert > 1\) or \(\lvert\mathcal{R}\rvert > 1\) โ€” one of the two suffices. A knowledge graph with a single entity type but hundreds of relations is heterogeneous; so is a bipartite userโ€“item graph with a single edge type. The homogeneous case that standard GNNs assume is \(\lvert\mathcal{A}\rvert = \lvert\mathcal{R}\rvert = 1\).

Examples:

Academic network:

  • Node types: Paper, Author, Venue
  • Edge types: cites, written-by, published-in, reviews

Recommender system:

  • Node types: User, Item, Category, Brand
  • Edge types: clicks, purchases, belongs-to, manufactured-by

Biomedical knowledge graph:

  • Node types: Gene, Disease, Drug, Protein
  • Edge types: associated-with, treats, inhibits, encodes

Why Standard GNNs Fail on Heterogeneous Graphs

Standard message passing:

\[ h_v^{(k)} \;=\; \mathrm{UPDATE}\Bigl(h_v^{(k-1)},\; \mathrm{AGG}\bigl(\bigl\{\,h_u^{(k-1)} : u \in \mathcal{N}(v) \,\bigr\}\bigr)\Bigr) \]

applies the same message function to every neighbour in \(\mathcal{N}(v)\), regardless of the edge type connecting them. This conflates semantically very different relationships:

  • โ€œUser A clicked Item Bโ€ and โ€œItem B belongs-to Category Cโ€ are both aggregated identically
  • The model cannot learn that โ€œcitesโ€ edges carry different information than โ€œco-authored-byโ€ edges
  • Node type differences are ignored โ€” a Gene node and a Drug node are processed identically

Solutions Overview

1. Type-specific message functions: learn a separate weight matrix \(W_r\) for each relation \(r \in \mathcal{R}\). A message arriving over relation \(r\) is \(W_r h_u\). Used in R-GCN.

2. Meta-path decomposition: define semantically meaningful paths through the graph (e.g., Author โ†’ Paper โ†’ Author = co-authorship). Run separate GNNs along each meta-path. Used in HAN.

3. Relation-aware attention: attend differentially to different relation types when aggregating. Used in HAN, HGT.

4. Type-specific projections: project all node types into a common embedding space with type-specific linear transforms before message passing. Used in HGT (Heterogeneous Graph Transformer).

Visualising a Bipartite Heterogeneous Graph

User A User B User C Users Item 1 Item 2 Item 3 Item 4 Items Electronics Books Categories clicks belongs-to
A heterogeneous bipartite graph: three node types (Users, Items, Categories) and two edge types (clicks, belongs-to). A standard GNN would process all edges identically โ€” losing the semantic distinction between "User clicks Item" and "Item belongs-to Category".

Meta-Paths: Semantic Bridges

A meta-path is a sequence of node and edge types defining a composite relationship:

Author -[writes]โ†’ Paper -[written-by]โ†’ Author
= APA (Author-Paper-Author) = co-authorship

Paper -[cites]โ†’ Paper -[published-in]โ†’ Venue -[publishes]โ†’ Paper
= PPVP (a longer multi-hop semantic relation)

Meta-paths allow encoding domain knowledge into the graph structure. A model operating on the APA meta-path captures co-authorship patterns; one on the APVPA meta-path (Author โ†’ Paper โ†’ Venue โ†’ Paper โ†’ Author) captures researchers working in the same venue.

Meta-paths as graph views: Each meta-path defines a new homogeneous graph (all nodes same type, all edges same type) where two nodes are connected if there exists a path of the given type between them. Running a standard GNN on each of these views, then combining, is one approach to heterogeneous GNN design.

Node Projection to Common Space

When node types have different feature dimensions (e.g., Papers have text embeddings, Authors have profile embeddings), we must first project all types to a common dimension \(d\):

\[ h_v^{(0)} \;=\; W_{\tau(v)}\, x_v \;+\; b_{\tau(v)} \]

A separate linear projection \(W_{\tau(v)}\) per node type ensures all nodes live in the same embedding space before message passing begins. Note this is indexed by node type \(\tau(v)\), not relation type โ€” it is a different mechanism from the relation-specific \(W_r\) above, and a full heterogeneous architecture typically needs both.

Heterogeneous Graph Benchmarks

  • ogbn-mag (Open Graph Benchmark: Microsoft Academic Graph): four node types โ€” 736,389 papers, 1,134,649 authors, 8,740 institutions and 59,965 fields of study โ€” connected by citation, authorship, affiliation and topic edges. Only papers carry input features; the other three types do not, which is itself a defining difficulty of the benchmark.
  • IMDB (heterogeneous): Movies, Actors, Directors โ€” classify movie genre
  • ACM: Papers, Authors, Subjects โ€” classify research area
  • DBLP: Authors, Papers, Venues, Terms โ€” author classification

Summary

ApproachHow it handles heterogeneityExample
Type-specific weightsSeparate \(W_r\) per relation \(r \in \mathcal{R}\)R-GCN
Meta-path aggregationRun GNNs on meta-path subgraphsHAN
Relation-aware attentionAttention over relation typesHAN, HGT
Type projectionMap all types to common spaceHGT

Heterogeneous GNNs extend the MPNN framework to handle the multi-relational, multi-typed structure of real knowledge graphs, recommendation systems, and biomedical networks โ€” domains where the type structure is often as important as the graph topology.

References

You May Also Enjoy

The Standard Library Modules Worth Knowing Before You pip install

8 minute read

Published:

Python ships with a counter, a queue, a memoiser, a CLI parser, a test frameworkโ€™s smaller cousin, and a JSON-safe date library already installed โ€” most of what people reach for a package to solve is one import away.

Files and Context Managers: Why with Is Not Optional

9 minute read

Published:

A file object that falls out of scope without with does get closed eventually โ€” but โ€˜eventuallyโ€™ means whenever the garbage collector gets around to it, which is not a promise any program handling more than a handful of files can live with.

Errors and Exceptions: EAFP, the Hierarchy, and Reading a Traceback

9 minute read

Published:

Exceptions in Python are not exceptional. They are a normal control-flow mechanism that the language leans on so heavily that the idiomatic style is to try the operation and handle the failure, rather than check first โ€” which is faster, shorter, and free of race conditions.