Relational GCN

R-GCN (Schlichtkrull et al., ESWC 2018) gives each relation type its own weight matrix and averages messages per relation; basis or block-diagonal decomposition keeps parameters manageable with hundreds of relations.

8 min read622 wordsadvanced0 viewsupdated 2026-10-21

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 (s,r,o)(s,r,o), 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 WW 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

hi(l+1)=σ ⁣(∑r∈R∑j∈Nir1ci,rWr(l)hj(l)+W0(l)hi(l))h_i^{(l+1)}=\sigma\!\Big(\sum_{r\in\mathcal R}\sum_{j\in\mathcal N_i^r}\frac{1}{c_{i,r}}W_r^{(l)}h_j^{(l)}+W_0^{(l)}h_i^{(l)}\Big)
R\mathcal R
relation types, with every relation's inverse added as a separate type, so messages flow both ways
Nir\mathcal N_i^r
neighbours of ii under relation rr
ci,rc_{i,r}
a normaliser; the paper uses ci,r=∣Nir∣c_{i,r}=|\mathcal N_i^r|, a mean per relation
Wr,  W0W_r,\;W_0
a d×d′d\times d' 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 ∣R∣+1|\mathcal R|+1 matrices, so its parameters grow linearly with the number of relations. FB15k-237 has 237 relations, or 474 with inverses. At d=500d=500 that is 118.5 M weights per layer, and rare relations would have a handful of training edges each.

h′_P = ReLU( Σ_r Σ_(j ∈ N_P^r) (1/c_P,r) W_r h_j + W₀ h_P ), c_P,r = |N_P^r|written_byA1A21/2 · W_written_bycitesP21 · W_citescites⁻¹P3P4P51/3 · W_cites⁻¹published_inV1 · W_published_inself-loopPW₀ (own features)ΣReLUh′_Pevery edge type and itsinverse is a relation:2R + 1 matrices d × d′per layer (incl. W₀)basis decomposition (shared across relations)= a_r1+ a_r2W_r = Σ_b a_rb V_b · params B·d² + R·Bblock-diagonal (sparse within a relation)W_r = diag(Q_1r, …, Q_Br)B blocks of (d/B) × (d/B)params R·d²/B
fig.One R-GCN layer for paper P. Neighbours are grouped by relation, and the inverse of cites is its own relation. Each group is averaged (½, 1, ⅓, 1) and transformed by its own matrix, the self-loop W₀ adds P's own features, and the sum goes through ReLU. Below: the two ways the paper shares or sparsifies the W_r.

Basis and block-diagonal decomposition

basis: Wr=∑b=1Barb Vbblock-diagonal: Wr=⨁b=1BQbr=diag⁡(Q1r,…,QBr)\text{basis: } W_r=\sum_{b=1}^{B}a_{rb}\,V_b\qquad\qquad \text{block-diagonal: } W_r=\bigoplus_{b=1}^{B}Q_{br}=\operatorname{diag}(Q_{1r},\dots,Q_{Br})
VbV_b
BB basis matrices d×d′d\times d' shared by all relations; arba_{rb} are scalar coefficients per relation
QbrQ_{br}
BB small blocks of (d/B)×(d′/B)(d/B)\times(d'/B) per relation; features interact only within a block

Basis decomposition costs Bd2+∣R∣BBd^2+|\mathcal R|B parameters. It is a low-rank constraint across relations: stack vec(Wr)\mathrm{vec}(W_r) as the rows of an ∣R∣×d2|\mathcal R|\times d^2 matrix and it may have rank at most BB. Rare relations then borrow statistical strength from frequent ones through the shared VbV_b. Block-diagonal decomposition costs ∣R∣d2/B|\mathcal R|d^2/B and shares nothing across relations. It is a sparsity prior within each relation, suited to features that fall into groups.

R = 8 relations, d = 8: W_r ≈ Σ_b a_rb V_b vs W_r = diag(Q_1r … Q_2r)target weights: 3 shared bases + 0.3 × relation-specific noiseW₁ (target)basis, B = 3block-diag, 2 × 4²error 10.2% (all R)error 64.7% (all R)‖W − Ŵ‖_F / ‖W‖_Fparameters (one layer)full R·d²512 · error 0%basis B·d² + R·B216 · error 10.2%block R·d²/2256 · error 64.7%singular values of the R × d² stack [vec W₁; …; vec W_R]; basis keeps the top 312345678discarded energy Σ_(k>B) s_k² / Σ s_k² = 1.0% → error = its square rootthe best B-basis fit is arank-B truncation (SVD):relations share bases V_band differ only in a_rbblock-diag shares nothingacross relations; it dropscross-block feature terms
blocks
target weights
fig.Eight 8 × 8 relation matrices built from 3 shared bases plus relation-specific noise (ν = 0.3). The best B-basis fit is a rank-B SVD truncation. Defaults (B = 3, 2 blocks): basis needs 216 parameters for 10.2% error, block-diagonal needs 256 for 64.7%, and full weights need 512. With B = 1, error is 54.1%; with B = 2, 19.1%. Switch the target to block-sparse: now 2 blocks give 30.5% and B = 3 bases give 66.0%, and only B = 8 (576 parameters, more than full) is exact. Each scheme wins only when its prior matches.

For link prediction the R-GCN is an encoder. Its output ei=hi(L)e_i=h_i^{(L)} replaces the free entity embedding of a factorisation model, and a DistMult decoder scores each triple:

f(s,r,o)=es⊤Rr eo,L=−1(1+ω)∣E^∣∑(s,r,o,y)[ylog⁡σ(f)+(1−y)log⁡(1−σ(f))]f(s,r,o)=e_s^{\top}R_r\,e_o,\qquad \mathcal L=-\frac{1}{(1+\omega)|\hat{\mathcal E}|}\sum_{(s,r,o,y)}\Big[y\log\sigma\big(f\big)+(1-y)\log\big(1-\sigma(f)\big)\Big]
RrR_r
a diagonal d×dd\times d matrix per relation (DistMult)
ω\omega
negative triples per positive, made by corrupting the subject or the object
yy
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

  1. 1Features and weights. hP=(1,0)h_P=(1,0), hA1=(1,0)h_{A1}=(1,0), hA2=(0,1)h_{A2}=(0,1), hP2=(1,1)h_{P2}=(1,1). Wwritten_by=(1101)W_\text{written\_by}=\begin{pmatrix}1&1\\0&1\end{pmatrix}, Wcites=(0−110)W_\text{cites}=\begin{pmatrix}0&-1\\1&0\end{pmatrix}, W0=IW_0=I.
  2. 2written_by group. c=2c=2: mean (0.5,0.5)(0.5,0.5), times Wwritten_byW_\text{written\_by} gives (0.5, 1.0)(0.5,\,1.0).
  3. 3cites group. c=1c=1: (1,1) Wcites=(1, −1)(1,1)\,W_\text{cites}=(1,\,-1).
  4. 4Self-loop and sum. hPW0=(1,0)h_PW_0=(1,0). Sum (0.5+1+1,  1−1+0)=(2.5, 0)(0.5+1+1,\;1-1+0)=(2.5,\,0); ReLU leaves hP′=(2.5, 0)h'_P=(2.5,\,0).
  5. 5Swap the edge labels. Make P2 an author and A2 a cited paper. Then written_by averages (1,0.5)→(1,1.5)(1,0.5)\to(1,1.5), cites gives (0,1)Wcites=(1,0)(0,1)W_\text{cites}=(1,0), and hP′=(3, 1.5)h'_P=(3,\,1.5). A relation-blind layer would see the same three neighbours and give the same output both times.
SchemeFormulaParameters
FullR·d²118,500,000
Basis, B = 2B·d² + R·B500,948
Basis, B = 30B·d² + R·B7,514,220
Block-diagonal, 5 blocks of 100 × 100R·d²/B23,700,000
Block-diagonal, 50 blocks of 10 × 10R·d²/B2,370,000
Weights per layer at d = 500 with 474 relation matrices (237 FB15k-237 relations and their inverses; W₀ not counted)
python
1import numpy as np
2
3def 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 term
8 for r in range(n_rel):
9 E = [(s, d) for s, rr, d in triples if rr == r]
10 if not E:
11 continue
12 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] += 1
17 msg[cnt > 0] /= cnt[cnt > 0, None] # 1 / c_{i,r} = mean per relation
18 out += msg @ W[r]
19 return np.maximum(out, 0)
20
21# nodes: 0 = P, 1 = A1, 2 = A2, 3 = P2 ; relations: 0 = written_by, 1 = cites, 2/3 = inverses
22H = 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 P
24triples = fwd + [(d, r + 2, s) for s, r, d in fwd] # add inverse relations
25V = np.array([[[1, 1], [0, 1]], [[0, -1], [1, 0]]], dtype=float) # B = 2 bases
26a = np.array([[1, 0], [0, 1], [0.5, 0], [0, 0.5]]) # R = 4 relations x B = 2
27print(rgcn_layer(H, triples, 4, V, a, np.eye(2))[0]) # [2.5 0. ]
An R-GCN layer with basis decomposition in numpy, on the worked example (runs as is). In PyTorch Geometric the same layer is RGCNConv(in_channels, out_channels, num_relations, num_bases=B), or num_blocks=B for block-diagonal

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: hi′=σ(∑r∑j∈Nir1ci,rWrhj+W0hi)h_i'=\sigma(\sum_r\sum_{j\in\mathcal N_i^r}\frac{1}{c_{i,r}}W_rh_j+W_0h_i), one WrW_r 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.
← back to Deep Learning roadmap