# 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.

Source: https://www.mlfoundry.in/learn/relational-gcn  
Section: Deep Learning › Graph Neural Networks (GNNs)  
Level: advanced · 8 min read · updated 2026-10-21

**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)$, 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 $W$ 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

$$
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)
$$

- $\mathcal R$: relation types, with every relation's inverse added as a separate type, so messages flow both ways
- $\mathcal N_i^r$: neighbours of $i$ under relation $r$
- $c_{i,r}$: a normaliser; the paper uses $c_{i,r}=|\mathcal N_i^r|$, a mean per relation
- $W_r,\;W_0$: a $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 $|\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=500$ that is 118.5 M weights per layer, and rare relations would have a handful of training edges each.

> Figure: 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

$$
\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})
$$

- $V_b$: $B$ basis matrices $d\times d'$ shared by all relations; $a_{rb}$ are scalar coefficients per relation
- $Q_{br}$: $B$ small blocks of $(d/B)\times(d'/B)$ per relation; features interact only within a block

Basis decomposition costs $Bd^2+|\mathcal R|B$ parameters. It is a low-rank constraint across relations: stack $\mathrm{vec}(W_r)$ as the rows of an $|\mathcal R|\times d^2$ matrix and it may have rank at most $B$. Rare relations then borrow statistical strength from frequent ones through the shared $V_b$. Block-diagonal decomposition costs $|\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.

> Figure: 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.

## Link prediction: R-GCN as an encoder

For link prediction the R-GCN is an **encoder**. Its output $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)=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]
$$

- $R_r$: a diagonal $d\times d$ matrix per relation (DistMult)
- $\omega$: negative triples per positive, made by corrupting the subject or the object
- $y$: 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. **Features and weights.** $h_P=(1,0)$, $h_{A1}=(1,0)$, $h_{A2}=(0,1)$, $h_{P2}=(1,1)$. $W_\text{written\_by}=\begin{pmatrix}1&1\\0&1\end{pmatrix}$, $W_\text{cites}=\begin{pmatrix}0&-1\\1&0\end{pmatrix}$, $W_0=I$.
2. **written_by group.** $c=2$: mean $(0.5,0.5)$, times $W_\text{written\_by}$ gives $(0.5,\,1.0)$.
3. **cites group.** $c=1$: $(1,1)\,W_\text{cites}=(1,\,-1)$.
4. **Self-loop and sum.** $h_PW_0=(1,0)$. Sum $(0.5+1+1,\;1-1+0)=(2.5,\,0)$; ReLU leaves $h'_P=(2.5,\,0)$.
5. **Swap the edge labels.** Make P2 an author and A2 a cited paper. Then written_by averages $(1,0.5)\to(1,1.5)$, cites gives $(0,1)W_\text{cites}=(1,0)$, and $h'_P=(3,\,1.5)$. A relation-blind layer would see the same three neighbours and give the same output both times.

Weights per layer at d = 500 with 474 relation matrices (237 FB15k-237 relations and their inverses; W₀ not counted)

| 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 |

```python
import numpy as np

def rgcn_layer(H, triples, n_rel, V, a, W0):
    """One R-GCN layer with basis decomposition W_r = sum_b a[r, b] V[b].
    triples: (src, rel, dst) edges, already including the inverse relations."""
    W = np.einsum("rb,bio->rio", a, V)                 # (R, d_in, d_out)
    out = H @ W0                                       # self-loop term
    for r in range(n_rel):
        E = [(s, d) for s, rr, d in triples if rr == r]
        if not E:
            continue
        msg = np.zeros((H.shape[0], H.shape[1]))
        cnt = np.zeros(H.shape[0])
        for s, d in E:
            msg[d] += H[s]
            cnt[d] += 1
        msg[cnt > 0] /= cnt[cnt > 0, None]             # 1 / c_{i,r} = mean per relation
        out += msg @ W[r]
    return np.maximum(out, 0)

# nodes: 0 = P, 1 = A1, 2 = A2, 3 = P2 ; relations: 0 = written_by, 1 = cites, 2/3 = inverses
H = np.array([[1.0, 0.0], [1.0, 0.0], [0.0, 1.0], [1.0, 1.0]])
fwd = [(1, 0, 0), (2, 0, 0), (3, 1, 0)]                # messages into P
triples = fwd + [(d, r + 2, s) for s, r, d in fwd]     # add inverse relations
V = np.array([[[1, 1], [0, 1]], [[0, -1], [1, 0]]], dtype=float)  # B = 2 bases
a = np.array([[1, 0], [0, 1], [0.5, 0], [0, 0.5]])     # R = 4 relations x B = 2
print(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

> **Inverse relations are not optional:** Without the inverse types, information flows only along the stored edge direction. In (paper, written_by, author) the author would never hear from its papers. The paper adds $r^{-1}$ for every $r$. In code that means doubling the relation count and appending the reversed edges *before* building the layer, as the example does.

> **The template for heterogeneous GNNs:** "One transform per edge type, then sum over types" became the standard recipe for typed graphs. PyG's `HeteroConv` and `to_hetero` generalise it to node types and arbitrary per-type layers (see **Heterogeneous graph neural networks**). Attention over relations, as in RGAT and HGT, replaces the fixed $1/c_{i,r}$.

**Question:** A graph has 200 relation types (400 with inverses) and d = 256. Which choice gives the fewest R-GCN weights per layer (ignoring W₀)?

- A. Full matrices
- B. Basis decomposition with B = 4
- C. Block-diagonal with 4 blocks
- D. Block-diagonal with 16 blocks

**Answer:** B. Basis decomposition with B = 4 — Full: $400\cdot256^2=26.2$ M. Basis $B=4$: $4\cdot65{,}536+400\cdot4=263{,}744$. Block 4: $26.2\text{ M}/4=6.55$ M. Block 16: $1.64$ M. Basis wins because its cost barely depends on the number of relations.

**Question:** Why does R-GCN normalise by c_{i,r} = |N_i^r| per relation rather than by the node's total degree?

- A. It makes the layer permutation invariant
- B. So that a relation with many edges cannot drown out a relation with few; each relation contributes a mean
- C. It is required by the basis decomposition
- D. It removes the need for the self-loop

**Answer:** B. So that a relation with many edges cannot drown out a relation with few; each relation contributes a mean — The sum over $j\in\mathcal N_i^r$ with $1/|\mathcal N_i^r|$ is a per-relation mean, so 500 cited_by edges and 2 written_by edges give two messages of comparable size. Permutation invariance already comes from summing; the normaliser is a separate modelling choice.

**Key points**

- Layer: $h_i'=\sigma(\sum_r\sum_{j\in\mathcal N_i^r}\frac{1}{c_{i,r}}W_rh_j+W_0h_i)$, one $W_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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
