Heterogeneous Graphs: Multiple Node & Edge Types

A bank's fraud team is building a graph to catch UPI fraud rings. They lay out four kinds of nodes: Users (with features like KYC score and average transaction size), Merchants (category, monthly volume, GST status), Devices (OS, number of accounts linked to that device's IMEI hash), and Bank Accounts (age of account, linked bank). Between these nodes run several kinds of edges: a User pays a Merchant, a User shares a device with another User, a User owns an Account, an Account is linked to a Bank. The team's plan is to run a graph neural network over this structure so that a User's final embedding reflects not just their own behaviour but the behaviour of everyone they are connected to — including, crucially, users who share a suspicious device with them.

The GNN you met earlier — the graph convolution rule h_v = σ(W · aggregate(h_u for u in neighbours(v))) — was built for a graph where every node is the same kind of thing and every edge means the same kind of relationship: a citation graph where every node is a paper and every edge is "cites", or a road network where every node is a junction and every edge is "is connected by a road". Try to point that same machinery at the fraud graph and it breaks immediately, in two different ways, before it even gets to learning anything useful. First, a User's feature vector and a Device's feature vector don't even live in the same space — they measure different things and can have different dimensionality. Second, and more subtly, even if you force them into the same dimensionality by padding, one shared weight matrix W applied to every edge means the network is claiming that "being paid by a user" and "being someone's shared device" transform information in the same way. They don't. That gap — between a graph where node identity and edge meaning are uniform, and a graph where they are not — is exactly what heterogeneous graphs are built to close.

Formalizing "heterogeneous": node types, edge types, and the schema

A heterogeneous graph is a tuple G = (V, E, φ, ψ) where V is the node set, E is the edge set, φ: V → A maps every node to a node type drawn from a type set A, and ψ: E → R maps every edge to a relation type drawn from a type set R. The graph is called heterogeneous precisely when |A| + |R| is greater than two — that is, whenever there is more than one node type, more than one edge type, or both. A plain social network (one node type "Person", one edge type "follows") is homogeneous even though it can be huge and structurally complex; the fraud graph above, with four node types and four relation types, is heterogeneous even though it might be small.

The shape of the allowed types — which node type can be connected to which other node type by which relation — is called the network schema. For the fraud graph the schema says: User –pays→ Merchant, User –shares_device→ Device, User –owns→ Account, Account –linked_to→ Bank. The schema is itself a small graph over types rather than over instances, and it is what a heterogeneous GNN's architecture has to respect: a relation-specific operation for "pays" should only ever be applied to a User-Merchant pair, never to an Account-Bank pair, because those two relations carry different information even if, by coincidence, the raw feature vectors on both sides happened to have the same dimensionality.

The misconception: "just add the type as a feature"

The most common mistake at this point is to think heterogeneity is a data-preprocessing problem, not an architecture problem — one-hot encode each node's type and concatenate it onto the feature vector, pad every node to a common dimensionality, then run an ordinary GCN or GraphSAGE layer as before. This is wrong, and it is worth being precise about why. Concatenating a type indicator does let the network see that a neighbour is a Device rather than a Merchant. But the aggregation step still multiplies every neighbour's message by the same weight matrix W before summing. A single linear map cannot simultaneously be the correct transformation for "this neighbour paid me money" and "this neighbour shares my device" — those are different relationships with different statistical structure, and forcing one matrix to serve both means the network can only learn a compromise that is subtly wrong for both. Worse, because the aggregation sums over all neighbours regardless of relation before the type information can exert much influence, the signal that "many users share this device" gets diluted by however many paying-merchant edges are mixed in with it — exactly the fraud-ring signal the bank's team most needs to preserve. The fix is not a feature engineering trick; it is to give each relation type its own transformation.

Relation-specific message passing: the R-GCN update

The standard architecture for this is the Relational Graph Convolutional Network (R-GCN), introduced by Schlichtkrull and colleagues in 2018. Its update rule looks almost identical to the ordinary GCN rule, with one change that matters enormously:

h_v^(k) = ReLU( W_0^(k) h_v^(k-1)  +  Σ_{r in R} Σ_{u in N_r(v)} (1 / c_{v,r}) W_r^(k) h_u^(k-1) )

Read it term by term. N_r(v) is the set of neighbours of v reached specifically through relation r — not all neighbours, only the ones connected by that particular edge type. W_r^(k) is a weight matrix that belongs to relation r alone, at layer k; a "pays" edge and a "shares_device" edge are transformed by two completely different matrices, so the network is free to learn that device-sharing should compress two users' embeddings toward each other while a payment relation should not. c_{v,r} is a normalization constant, typically the number of neighbours v has under relation r, which stops nodes with many edges of one type from dominating the sum purely by count. Finally W_0^(k) h_v^(k-1) is a self-loop term with its own weight matrix, letting the node retain and transform its own previous-layer representation independent of any neighbour — this is what keeps a node's own identity from being washed out by aggregation, and it is the one term that does not depend on relation type at all, since a node only ever has one relationship with itself.

Taming the parameter explosion

Giving every relation its own d × d weight matrix scales badly: a graph with 20 relation types and 128-dimensional features needs 20 × 128 × 128 parameters per layer just for the relation transforms, and most real relations in a schema like this have far fewer training edges than the common ones, so their dedicated matrices overfit quickly. R-GCN's own answer is basis decomposition: instead of learning W_r directly for each relation, learn a small shared bank of B basis matrices V_1 ... V_B and let every relation's matrix be a learned linear combination of them, W_r = Σ_{b=1}^{B} a_{rb} V_b, where only the scalar coefficients a_rb are relation-specific. A rare relation type still gets its own matrix, but that matrix is forced to be built from the same small vocabulary of transformations that well-observed relations use, which sharply cuts the parameter count from |R| d^2 down to roughly B d^2 + |R| B and lets statistical strength flow from common relations to rare ones.

Worked example: one layer of R-GCN, by hand

Take a four-node slice of the fraud graph: two users U1, U2, one merchant M1, and one device D1. Both users pay the same merchant and both users are logged in from the same device — the device-sharing pattern an investigator would flag as suspicious. Use 2-dimensional toy features and treat each relation as carrying messages in both directions for this single layer, so a node aggregates over every edge touching it regardless of which side it started from:

h_U1 = [1.0, 0.0]      h_U2 = [0.5, 0.2]
h_M1 = [0.0, 1.0]      h_D1 = [1.0, 1.0]

W_pays          = [[0.5, 0.0],
                    [0.0, 0.5]]

W_shares_device = [[1.0, 1.0],
                    [0.0, 1.0]]

W_0 (self-loop) = identity matrix

Compute the new embedding for U1. Its typed neighbourhoods are N_pays(U1) = {M1} and N_shares_device(U1) = {D1}, each of size 1, so the normalization constant c_{v,r} is 1 for both relations and can be dropped from the arithmetic.

Pays term: W_pays · h_M1 = [0.5×0 + 0×1, 0×0 + 0.5×1] = [0, 0.5]

Shares-device term: W_shares_device · h_D1 = [1×1 + 1×1, 0×1 + 1×1] = [2, 1]

Self term: W_0 · h_U1 = [1, 0] (identity, unchanged)

Sum: [0, 0.5] + [2, 1] + [1, 0] = [3, 1.5]. ReLU leaves both entries positive as-is, so h_U1^(1) = [3, 1.5].

Now do the same for U2, whose typed neighbourhoods are identical in structure — M1 under "pays", D1 under "shares_device" — but whose own feature vector differs. The pays term and shares-device term are unchanged from U1's computation, since they depend only on M1's and D1's features, not on U2's: [0, 0.5] and [2, 1] respectively. Only the self term changes: W_0 · h_U2 = [0.5, 0.2]. Summing gives [0, 0.5] + [2, 1] + [0.5, 0.2] = [2.5, 1.7], and ReLU leaves it unchanged: h_U2^(1) = [2.5, 1.7].

Look at what happened. U1 and U2 started with quite different feature vectors — [1, 0] versus [0.5, 0.2] — but after one layer their embeddings, [3, 1.5] and [2.5, 1.7], are much closer to each other, and both are dominated by the identical [2, 1] contribution coming from the device they share. That is not a coincidence of the toy numbers; it is the entire point of giving "shares_device" its own weight matrix — the architecture lets that relation exert a strong, consistent pull on any pair of nodes that share a device, a pull that a single undifferentiated weight matrix averaged in with ordinary payment edges would have blurred away.

Tracing it in code

The same computation, run programmatically rather than by hand, should reproduce those two vectors exactly:

import numpy as np

h = {
    'U1': np.array([1.0, 0.0]),
    'U2': np.array([0.5, 0.2]),
    'M1': np.array([0.0, 1.0]),
    'D1': np.array([1.0, 1.0]),
}

W = {
    'pays':          np.array([[0.5, 0.0], [0.0, 0.5]]),
    'shares_device': np.array([[1.0, 1.0], [0.0, 1.0]]),
    'self':          np.eye(2),
}

edges = [
    ('U1', 'pays', 'M1'),
    ('U2', 'pays', 'M1'),
    ('U1', 'shares_device', 'D1'),
    ('U2', 'shares_device', 'D1'),
]

def neighbours_by_relation(target, edges):
    grouped = {}
    for a, r, b in edges:
        if a == target:
            grouped.setdefault(r, []).append(b)
        elif b == target:
            grouped.setdefault(r, []).append(a)
    return grouped

def rgcn_update(target, h, W, edges):
    total = W['self'] @ h[target]
    for r, nbrs in neighbours_by_relation(target, edges).items():
        c = len(nbrs)
        msg = sum(W[r] @ h[n] for n in nbrs) / c
        total = total + msg
    return np.maximum(total, 0)   # ReLU

for node in ['U1', 'U2']:
    vec = rgcn_update(node, h, W, edges)
    print(node, [round(float(x), 2) for x in vec])

Tracing it: for U1, neighbours_by_relation walks the four edges and finds {'pays': ['M1'], 'shares_device': ['D1']}, since U1 is the source of exactly one edge of each type. rgcn_update starts total at W['self'] @ h['U1'] = [1.0, 0.0], adds the pays message [0.0, 0.5] (degree 1, so no scaling), then adds the shares_device message [2.0, 1.0], giving [3.0, 1.5]; ReLU leaves it unchanged. The same walk for U2 yields [2.5, 1.7]. The script's output is:

U1 [3.0, 1.5]
U2 [2.5, 1.7]

which matches the hand computation exactly, confirming the arithmetic in both directions.

Beyond one hop: metapaths

R-GCN's relation-specific matrices handle direct, single-hop typed edges well, but some of the most useful heterogeneous patterns are indirect. Consider an IRCTC-style graph with node types Passenger, Train, and Station, and relation types boards and departs_from. Two passengers who never interact directly might still be worth linking if they boarded the same train on the same date — a pattern captured not by a single edge but by a metapath: Passenger –boards→ Train ←boards– Passenger, a length-2 chain of typed edges that defines "co-passenger" as a derived relation. Heterogeneous Graph Attention Networks (HAN), introduced by Wang and colleagues in 2019, generalize R-GCN by first aggregating along a chosen set of such metapaths and then learning an attention weight over which metapath matters most for a given task — for instance, weighting the "co-passenger on a long-distance train" metapath heavily when the task is detecting ticket-touting rings, versus weighting "booked through the same agent" heavily when the task is detecting payment fraud. The relation-specific weight matrix idea you just traced by hand is the foundation; metapath aggregation and attention are what let a heterogeneous GNN reach beyond direct neighbours to the multi-hop, multi-type patterns that single-relation edges cannot express on their own.

Active recall

Attempt each question before reading its answer.

1. A graph has node types {Student, Course, Instructor} and edge types {enrolled_in, teaches}. Is this graph heterogeneous? Justify using the formal condition.
2. Why can't a single shared weight matrix W, applied uniformly to every edge, correctly handle both a "pays" relation and a "shares_device" relation, even after you pad both node types to the same feature dimensionality?
3. Using the weights from the worked example (W_pays, W_0 = identity) and features h_U1 = [1, 0], h_U2 = [0.5, 0.2], h_M1 = [0, 1], compute h_M1's updated embedding after one R-GCN layer, given that M1's only neighbours are U1 and U2 under the "pays" relation.
4. Why does R-GCN need basis decomposition when the number of relation types |R| is large? Name the specific problem it solves.
5. Define a length-2 metapath in the IRCTC-style graph (node types Passenger, Train, Station; relations boards, departs_from) that captures "two passengers who travelled on the same train." Why can't a single relation type express this directly?
6. In the worked example, U1 and U2 start with different feature vectors but end up with embeddings that are much closer together after one layer. Explain, in terms of the R-GCN formula, why that happened — and what would go wrong if "pays" and "shares_device" used the same weight matrix instead of separate ones.

Answers.

1. Yes. The node type set has size |A| = 3 and the edge type set has size |R| = 2, so |A| + |R| = 5, which is greater than 2. A graph only needs to fail that condition — a single node type and a single edge type — to be homogeneous; this one clearly has more than one of each.

2. Padding fixes the dimensionality mismatch but not the semantic one. A weight matrix is a learned transformation, and one matrix applied to both relations is forced to find a single set of parameters that is simultaneously the best transformation for "money moved from this neighbour" and for "this neighbour shares my device" — two relationships with different statistical structure and different implications for the target node. The compromise the network settles on is generically wrong for both, and, as the worked example showed, it also erases the sharp, relation-specific signal (like device-sharing) that a fraud model most needs to preserve, because that signal gets averaged in with unrelated edges before it can dominate.

3. M1's neighbourhood under "pays" is {U1, U2}, so c = 2. W_pays · h_U1 = [0.5, 0] and W_pays · h_U2 = [0.25, 0.1]; summing gives [0.75, 0.1], divided by c = 2 gives [0.375, 0.05]. The self term is W_0 · h_M1 = [0, 1] (identity). Total: [0.375, 1.05], and ReLU leaves it unchanged since both entries are already positive. So h_M1^(1) = [0.375, 1.05].

4. Without basis decomposition, the number of parameters grows as |R| × d^2, and most relation types in a real schema have far fewer training edges than the most common ones — their dedicated d × d matrices would overfit badly. Basis decomposition writes every relation's matrix as a learned combination of a small shared bank of B basis matrices, W_r = Σ_b a_rb V_b, so rare relations borrow statistical strength from the shared bases instead of learning an independent transformation from scratch, and total parameters drop from order |R| d^2 to order B d^2 + |R| B.

5. Passenger –boards→ Train ←boards– Passenger: follow the "boards" relation forward from one passenger to a train, then backward from that same train to a second passenger. No single relation type can express this because "co-passenger" is not a direct edge in the schema at all — it only exists as a two-hop composition through the Train node, which is exactly what a metapath is built to represent.

6. In the update rule, the terms coming from M1 (via W_pays) are identical for both U1 and U2 because they depend only on M1's features, and likewise the term from D1 (via W_shares_device) is identical for both because it depends only on D1's features — only the self-loop term differs between the two users. Since the shared-device term, [2, 1], is larger in magnitude than the small difference between their self terms, it dominates the sum and pulls both final embeddings toward each other. If "pays" and "shares_device" used the same matrix, the network would lose the ability to make the device-sharing term structurally different (and, if trained to, disproportionately larger) than an ordinary payment term — the two relations would blend into one generic "neighbour" signal, and the fraud-relevant pattern of shared-device convergence would no longer be something the architecture could specifically learn to amplify.

Think About It

Think about this: How would you explain heterogeneous graphs: multiple node & edge types to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where heterogeneous graphs: multiple node & edge types is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting heterogeneous graphs: multiple node & edge types to at least 3 other topics you have studied.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind heterogeneous graphs: multiple node & edge types, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.