R-GCN: Relational Graph Convolutional Networks
Published:
The Problem: Multi-Relational Graphs
A knowledge graph (KG) is a directed multigraph where edges have types (relations). For example, Freebase contains entities (John_Lennon, Beatles, UK) connected by relations (member_of, born_in, from_country).
Standard GCN cannot handle this — it uses a single aggregation weight and cannot distinguish “member_of” from “born_in” edges.
The R-GCN Update Rule
Where:
- \(\mathcal{N}_r(v)\) — the neighbours of \(v\) connected via relation \(r\)
- \(c_{v,r}\) — a normalisation constant, problem-specific but typically \(\lvert \mathcal{N}_r(v)\rvert\), so each relation’s contribution is a mean rather than a sum
- \(W_0^{(k)}\) — the self-loop weight, applied to the node’s own representation
- \(W_r^{(k)}\) — the relation-specific weight matrix, one per relation per layer
Interpretation: for each relation \(r\), node \(v\) collects messages from all neighbours connected by \(r\), transforms them by \(W_r\), and averages. The per-relation results are then summed and added to the self-loop term.
This is equivalent to running a separate GCN on each relation’s adjacency subgraph and summing the results — which is also the clearest way to see where the parameter cost comes from.
Worked Example: One R-GCN Update Step
Consider entity John Lennon with \(d = 3\) and \(h = [1, 0, 0]\), having two neighbours:
- The Beatles via relation member of: \(h = [0, 1, 0]\)
- UK via relation born in: \(h = [0, 0, 1]\)
Suppose, purely for illustration, that \(W_{\text{member}} = I\), \(W_{\text{born}} = 2I\), and the self-loop weight is \(W_0 = 0.5\,I\). Each node has one neighbour per relation, so \(c_{v,r} = 1\) throughout. Take \(\sigma\) to be the logistic sigmoid.
h_new = σ( W_0·h_JL + W_member·h_Beatles + W_born·h_UK )
= σ( 0.5·[1,0,0] + 1·[0,1,0] + 2·[0,0,1] )
= σ( [0.5, 1.0, 2.0] )
≈ [0.62, 0.73, 0.88]
The result reflects the band-membership signal (coordinate 2) and the nationality signal (coordinate 3, larger because \(W_{\text{born}}\) scales by 2) as separately identifiable contributions. A standard GCN, applying one shared \(W\) to both neighbours, would produce a sum in which the two are no longer distinguishable — that is precisely the information R-GCN recovers.
The Parameter Problem: Basis Decomposition
A separate \(W_r \in \mathbb{R}^{d \times d}\) per relation means the layer’s parameter count grows as \(\lvert\mathcal{R}\rvert d^2\). For a KG with \(\lvert\mathcal{R}\rvert = 100\) relations (200 once inverses are included) and \(d = 200\), that is \(100 \times 200 \times 200 = 4\) million parameters for a single layer.
The problem is not only the count. Relation frequencies in a knowledge graph are heavily long-tailed: a handful of relations account for most triples while many appear a few dozen times. Each rare relation still gets its own \(d^2\) free parameters, fit from almost no data, with no way to borrow strength from the common relations. Overfitting on the tail is the predictable result.
Basis decomposition (the R-GCN solution): express each \(W_r\) as a linear combination of \(B\) shared basis matrices:
The bases \(V_b \in \mathbb{R}^{d \times d}\) are shared across all relations; only the \(B\) coefficients \(a_{rb}\) are relation-specific. Parameters drop from \(\lvert\mathcal{R}\rvert d^2\) to \(B d^2 + \lvert\mathcal{R}\rvert B\), a large saving when \(B \ll \lvert\mathcal{R}\rvert\). The mechanism is weight sharing, so it also addresses the long tail directly: a rare relation only needs to learn \(B\) numbers, and it inherits structure the frequent relations paid for.
Block-diagonal decomposition (the alternative): constrain each \(W_r\) to be block-diagonal with \(B\) blocks of size \((d/B) \times (d/B)\):
This cuts parameters per relation from \(d^2\) to \(d^2/B\) without sharing anything between relations. Its inductive bias is different: it says the latent features come in groups, and a relation may only mix features within a group. Basis decomposition shares across relations; block decomposition sparsifies within each one.
R-GCN for Entity Classification
Task: given a KG with some labelled entities, predict labels for unlabelled entities.
Example: Freebase entity type classification — is this entity a Person, Organisation, or Location?
Setup:
- Entity features: one-hot or learned embeddings
- 2-layer R-GCN
- Final \(h_v^{(K)}\) fed to a softmax classifier
- Trained with cross-entropy on labelled entities
The R-GCN paper evaluates this on four RDF benchmarks — AIFB, MUTAG, BGS and AM (note that this MUTAG is the RDF entity-classification dataset, not the molecule graph-classification dataset of the same name). R-GCN is competitive with the feature-engineering and kernel baselines used there, such as WL kernels and RDF2Vec, winning on some of the four and not on others; it is a structural encoder rather than a uniformly better method.
R-GCN for Link Prediction
Task: predict missing triples (subject, relation, object) — i.e., “does this relation exist between these two entities?”
Setup: R-GCN as an encoder, DistMult as a decoder.
- Encoder: run R-GCN to get entity embeddings \(e_s\) and \(e_o\)
- Decoder (DistMult): score the triple \((s, r, o)\) with a relation-specific diagonal matrix, i.e. a vector \(w_r \in \mathbb{R}^{d}\):
- Training: binary cross-entropy with negative sampling
This encoder–decoder split (GNN encodes structure, shallow decoder scores triples) is a common pattern for KG link prediction. Note the decoder’s relation parameters \(w_r\) are separate from the encoder’s \(W_r\) — the model learns each relation twice, once as a message transform and once as a scoring vector.
R-GCN vs DistMult / TransE
Before R-GCN, KG link prediction used shallow embedding methods:
- TransE: relations as translations, \(e_s + w_r \approx e_o\)
- DistMult: the diagonal bilinear score above
- ComplEx: the same trilinear form over complex-valued embeddings
These learn one vector per entity from the triples that entity appears in, but the vector itself is a free parameter — it is not a function of the neighbourhood. R-GCN changes that: an entity’s embedding is computed from the embeddings of its neighbours and the relations connecting them, so structure enters the representation rather than only the training signal.
Summary
| Property | R-GCN |
|---|---|
| Handles typed edges | Yes — a separate \(W_r\) for each \(r \in \mathcal{R}\) |
| Handles typed nodes | Partial — via features; no type-specific architecture |
| Parameters per layer | \(\lvert\mathcal{R}\rvert d^2\) unconstrained; \(Bd^2 + \lvert\mathcal{R}\rvert B\) with basis decomposition; \(\lvert\mathcal{R}\rvert d^2/B\) with block decomposition |
| Scales to many relations | Via basis or block-diagonal decomposition |
| Tasks | Entity classification, link prediction |
| Key hyperparameter | Number of bases / blocks \(B\), tuned per dataset |
| Limitation | No attention — within a relation, all neighbours are weighted equally by \(1/c_{v,r}\) |
R-GCN is the foundational model for applying GNNs to knowledge graphs. It introduced the relation-specific weight matrix pattern that nearly all subsequent heterogeneous GNN architectures inherit.
References
- Schlichtkrull, M., Kipf, T. N., Bloem, P., van den Berg, R., Titov, I., & Welling, M. (2018). Modeling Relational Data with Graph Convolutional Networks. ESWC 2018.
- Kipf, T. N., & Welling, M. (2016). Variational Graph Auto-Encoders. arXiv preprint (graph autoencoder for link prediction).
- Yang, B., Yih, W.-T., He, X., Gao, J., & Deng, L. (2015). Embedding Entities and Relations for Learning and Inference in Knowledge Bases. ICLR 2015 (DistMult decoder).