Definition
Relational GCN (R-GCN) is a graph convolutional layer for multi-relational graphs such as knowledge graphs. Each node sums messages from its neighbours, and each message is transformed by a weight matrix chosen by the edge's relation type and direction. Schlichtkrull, Kipf, Bloem, van den Berg, Titov and Welling introduced it in "Modeling Relational Data with Graph Convolutional Networks" (ESWC 2018) for entity classification and link prediction.
A knowledge graph is a set of triples , for example (paper, written_by, author). The two tasks are entity classification (predict a label for some entities, such as the research group of a person) and link prediction (score missing triples). Edge types carry meaning: "cites" and "written_by" should not be averaged as if they were the same thing. Yet a Graph Convolutional Network (GCN) uses one for every edge and ignores both the type and the direction.
Before R-GCN, entity classification on RDF data used hand-built graph kernels (Weisfeiler–Lehman) or RDF2Vec walk embeddings fed to a separate classifier. Link prediction used factorisation models such as DistMult, TransE and ComplEx, which score each triple from two free embeddings and ignore the neighbourhood (see Knowledge graph embeddings).
The layer
- relation types, with every relation's inverse added as a separate type, so messages flow both ways
- neighbours of under relation
- a normaliser; the paper uses , a mean per relation
- a matrix per relation, and a self-loop matrix for the node's own features
Normalising per relation means a node with 500 "cited_by" edges and 2 "written_by" edges still gives both relations equal say. A layer has matrices, so its parameters grow linearly with the number of relations. FB15k-237 has 237 relations, or 474 with inverses. At that is 118.5 M weights per layer, and rare relations would have a handful of training edges each.
Basis and block-diagonal decomposition
- basis matrices shared by all relations; are scalar coefficients per relation
- small blocks of per relation; features interact only within a block
Basis decomposition costs parameters. It is a low-rank constraint across relations: stack as the rows of an matrix and it may have rank at most . Rare relations then borrow statistical strength from frequent ones through the shared . Block-diagonal decomposition costs and shares nothing across relations. It is a sparsity prior within each relation, suited to features that fall into groups.
Link prediction: R-GCN as an encoder
For link prediction the R-GCN is an encoder. Its output replaces the free entity embedding of a factorisation model, and a DistMult decoder scores each triple:
- a diagonal matrix per relation (DistMult)
- negative triples per positive, made by corrupting the subject or the object
- 1 for observed triples, 0 for corrupted ones; the loss is Binary cross-entropy
The encoder lets an entity with few direct triples be described by its multi-hop neighbourhood. On FB15k-237, where inverse-relation shortcuts were removed from the test set, this is where R-GCN gains most over plain DistMult.
Results reported in the paper
- Entity classification
- accuracy 95.83% AIFB, 73.23% MUTAG, 83.10% BGS, 89.29% AM; best on AIFB and AM, below the WL-kernel and RDF2Vec baselines on MUTAG and BGS
- Why MUTAG / BGS lag
- labelled entities there connect mainly through high-degree hub nodes, where a fixed 1/c normaliser dilutes the useful messages; the authors suggest attention as a fix
- Model (classification)
- 2 R-GCN layers, 16 hidden units (10 for AM), basis decomposition, softmax output, Adam with learning rate 0.01, full-batch, 50 epochs
- Link prediction, FB15k-237
- filtered MRR 0.248 for R-GCN vs 0.191 for DistMult (+29.8%); Hits@10 0.414
Worked example: one layer on four nodes
Paper P with authors A1, A2 (written_by) and cited paper P2 (cites); d = 2, row-vector convention hW
- 1Features and weights. , , , . , , .
- 2written_by group. : mean , times gives .
- 3cites group. : .
- 4Self-loop and sum. . Sum ; ReLU leaves .
- 5Swap the edge labels. Make P2 an author and A2 a cited paper. Then written_by averages , cites gives , and . A relation-blind layer would see the same three neighbours and give the same output both times.
| Scheme | Formula | Parameters |
|---|---|---|
| Full | R·d² | 118,500,000 |
| Basis, B = 2 | B·d² + R·B | 500,948 |
| Basis, B = 30 | B·d² + R·B | 7,514,220 |
| Block-diagonal, 5 blocks of 100 × 100 | R·d²/B | 23,700,000 |
| Block-diagonal, 50 blocks of 10 × 10 | R·d²/B | 2,370,000 |
1import numpy as np23def rgcn_layer(H, triples, n_rel, V, a, W0):4 """One R-GCN layer with basis decomposition W_r = sum_b a[r, b] V[b].5 triples: (src, rel, dst) edges, already including the inverse relations."""6 W = np.einsum("rb,bio->rio", a, V) # (R, d_in, d_out)7 out = H @ W0 # self-loop term8 for r in range(n_rel):9 E = [(s, d) for s, rr, d in triples if rr == r]10 if not E:11 continue12 msg = np.zeros((H.shape[0], H.shape[1]))13 cnt = np.zeros(H.shape[0])14 for s, d in E:15 msg[d] += H[s]16 cnt[d] += 117 msg[cnt > 0] /= cnt[cnt > 0, None] # 1 / c_{i,r} = mean per relation18 out += msg @ W[r]19 return np.maximum(out, 0)2021# nodes: 0 = P, 1 = A1, 2 = A2, 3 = P2 ; relations: 0 = written_by, 1 = cites, 2/3 = inverses22H = np.array([[1.0, 0.0], [1.0, 0.0], [0.0, 1.0], [1.0, 1.0]])23fwd = [(1, 0, 0), (2, 0, 0), (3, 1, 0)] # messages into P24triples = fwd + [(d, r + 2, s) for s, r, d in fwd] # add inverse relations25V = np.array([[[1, 1], [0, 1]], [[0, -1], [1, 0]]], dtype=float) # B = 2 bases26a = np.array([[1, 0], [0, 1], [0.5, 0], [0, 0.5]]) # R = 4 relations x B = 227print(rgcn_layer(H, triples, 4, V, a, np.eye(2))[0]) # [2.5 0. ]Check yourself
A graph has 200 relation types (400 with inverses) and d = 256. Which choice gives the fewest R-GCN weights per layer (ignoring W₀)?
Check yourself
Why does R-GCN normalise by c_{i,r} = |N_i^r| per relation rather than by the node's total degree?
Remember
- ✓Layer: , one per relation and per direction.
- ✓Parameters grow as |R|·d²; basis decomposition (B·d² + |R|·B) shares bases across relations, block-diagonal (|R|·d²/B) sparsifies each one.
- ✓The best B-basis fit is a rank-B truncation of the stacked relation weights.
- ✓Entity classification: 95.83% AIFB, 89.29% AM; weaker on hub-dominated MUTAG and BGS.
- ✓As an encoder with a DistMult decoder: FB15k-237 filtered MRR 0.248 vs 0.191 for DistMult alone.