GCN

Overview

A GCN, or graph convolutional network, is a neural network that learns from data shaped like a graph. Each node updates its vector by averaging the vectors of its neighbours and itself, then applying a learned linear layer and a non-linearity. Stacking a few such layers lets a node see information from nodes several steps away.

GCNs are best known for node classification, where only a few nodes have labels and the graph structure supplies the rest of the signal. They are simple, fast and a good first baseline for relational data such as citation networks, social networks and molecules. For tabular work, a GCN is a useful way to think about rows that are linked by keys, and it sits next to GAT and GraphSAGE in the family of graph neural networks.

What it is

A GCN is a graph neural network that generalises the idea of a convolution from grids to graphs. In an image, a convolution mixes a pixel with its fixed set of neighbours. In a graph, nodes have different numbers of neighbours and no fixed order, so the GCN uses a normalised average over whatever neighbours each node has.

The input

A GCN takes three things:

• A graph with n nodes, described by an adjacency matrix A that says which nodes are connected.

• A feature matrix X with one row of features per node.

• Optional labels for some nodes, used for training.

The output

The output is a new vector for every node. For node classification, the last layer produces class scores per node. For graph classification, the node vectors are pooled into one vector for the whole graph. For link prediction, pairs of node vectors are compared.

Semi-supervised learning on graphs

The classic setting is semi-supervised learning. Only a small fraction of nodes have labels. The loss is computed on labelled nodes, but the forward pass uses the whole graph, so unlabelled nodes still shape the result through their links.

Where it came from

Early graph neural networks in the 2000s defined node states through repeated message passing until they settled. Later work in the mid 2010s connected convolution to the spectral properties of graphs, using the eigenvectors of the graph Laplacian as a Fourier basis. Those spectral methods were powerful but costly and tied to a single graph.

The GCN, introduced in the paper "Semi-Supervised Classification with Graph Convolutional Networks" in 2017, simplified this. It used a first-order approximation of spectral filters, which collapsed into a very simple rule: a normalised average over neighbours followed by a linear map. This made graph learning cheap and easy to implement, and it became the standard baseline.

Many successors followed. GAT replaced the fixed average with learned attention. GraphSAGE added neighbour sampling for large graphs and for nodes unseen in training. Later work studied depth, expressive power and scaling. See /model/research for how relational ideas feed into tabular research.

How it works

Think of a village where each person holds an opinion. In each round, every person talks to their direct neighbours and updates their opinion to a blend of their own and their neighbours. After one round, a person knows about friends. After two rounds, they know a little about friends of friends.

Step 1: Add self-loops

The adjacency matrix A has a one wherever two nodes are linked. A node's own vector would be left out of its average, so GCN adds the identity matrix: A_hat = A + I. Now each node counts itself as a neighbour.

Step 2: Compute degrees

The degree of a node is how many connections it has, now including its self-loop. Collect these into a diagonal matrix D_hat. Nodes with many neighbours would otherwise get very large sums, so degrees are used to rescale.

Step 3: Normalise

GCN uses symmetric normalisation:

A_norm = D_hat^(-1/2) * A_hat * D_hat^(-1/2)

Each entry becomes the link weight divided by the square root of the degrees of both endpoints. This keeps the scale of features stable and stops hubs from dominating.

Step 4: Propagate and transform

One layer is:

H_next = activation( A_norm * H * W )

Here H is the matrix of node vectors from the previous layer, W is a learned weight matrix, and the activation is usually ReLU. The product A_norm times H averages neighbours. The product with W mixes feature channels.

Analogy: first everyone averages opinions with neighbours, then everyone applies the same personal rule to turn the averaged opinion into a new opinion.

Step 5: Stack layers

A two-layer GCN gives each node a view of its two-hop neighbourhood. The first layer uses input features as H. The last layer outputs class scores, usually followed by a softmax.

Z = softmax( A_norm * ReLU( A_norm * X * W0 ) * W1 )

Step 6: Train with a masked loss

The cross-entropy loss is summed over labelled nodes only. Back-propagation updates W0 and W1. Because the same weights are shared by all nodes, the number of parameters does not depend on the size of the graph.

Step 7: Regularise

Dropout is applied to features and to hidden layers. Weight decay is applied to the first layer. With few labels, regularisation is important.

The spectral view in one paragraph

A graph signal, such as one feature across all nodes, can be split into smooth and rough parts. Smooth parts change slowly between neighbours. The GCN rule acts as a low-pass filter. It keeps the smooth part and damps the rough part. That is why GCNs work well when connected nodes tend to share labels, a property called homophily.

The spatial view in one paragraph

Equivalently, each layer is a message passing step. Every node sends its vector to neighbours, receives theirs, aggregates by a degree-normalised mean, and updates by a shared linear map. This view generalises easily, which is how GraphSAGE and GAT arise: change the aggregator or the weights on messages.

Why the rule is shaped this way

Each design choice in the layer solves a specific problem.

• Averaging instead of summing keeps feature scale steady for nodes of different degree.

• Self-loops let a node keep its own information instead of replacing it with its neighbours.

• Symmetric normalisation treats an edge fairly from both ends, so a link between a hub and a leaf is not dominated by either.

• Shared weights keep the parameter count independent of graph size.

• A non-linearity between layers lets the stack represent more than one big averaging step.

Shapes at a glance

For a graph with n nodes, input width f, hidden width h and c classes:

Because A_norm is sparse, the cost of a layer is roughly the number of edges times the feature width, plus the cost of the dense product with the weight matrix.

Variants you will meet

• Simplified GCN, which removes the non-linearities between layers so propagation can be precomputed once.

• GCN with residual links, which adds each layer's input to its output to fight over-smoothing.

• GCN with edge weights, where the adjacency holds weights instead of zeros and ones.

• Relational GCN, which keeps a separate weight matrix for each type of edge.

• Cluster-based mini-batch training, which splits the graph into sub-graphs so a large graph fits in memory.

Key concepts and terms

A worked example

A tiny numeric walk-through

Take a graph with three nodes in a line: node 1 is linked to node 2, and node 2 is linked to node 3. Each node has one feature: x = [1, 2, 3].

1. Adjacency with self-loops: node 1 connects to 1 and 2. Node 2 connects to 1, 2 and 3. Node 3 connects to 2 and 3.

2. Degrees: node 1 has 2, node 2 has 3, node 3 has 2.

3. Normalised weight between nodes i and j is 1 divided by the square root of degree i times degree j.

4. For node 1: 1 / sqrt(22) = 0.5 on itself, and 1 / sqrt(23) = 0.408 on node 2. New value = 0.51 + 0.4082 = 1.316.

5. For node 2: 1 / sqrt(33) = 0.333 for each of three entries. New value = 0.333(1+2+3) = 2.0.

6. For node 3: 0.53 + 0.4082 = 2.316.

After one propagation the values move from [1, 2, 3] to about [1.32, 2.0, 2.32]. The ends have moved toward the middle. Repeating this many times would push all values toward each other, which is the seed of over-smoothing.

A two-layer GCN in plain PyTorch

import torch
import torch.nn as nn
import torch.nn.functional as F

def normalise_adj(A):
    A_hat = A + torch.eye(A.size(0))
    deg = A_hat.sum(dim=1)
    d_inv_sqrt = deg.pow(-0.5)
    return d_inv_sqrt[:, None] * A_hat * d_inv_sqrt[None, :]

class GCN(nn.Module):
    def __init__(self, in_dim, hid, out_dim, p=0.5):
        super().__init__()
        self.w0 = nn.Linear(in_dim, hid)
        self.w1 = nn.Linear(hid, out_dim)
        self.p = p

    def forward(self, X, A_norm):
        h = F.dropout(X, self.p, self.training)
        h = F.relu(A_norm @ self.w0(h))
        h = F.dropout(h, self.p, self.training)
        return A_norm @ self.w1(h)

# Fake data: 6 nodes, 4 features, 2 classes.
A = torch.tensor([
    [0,1,1,0,0,0],
    [1,0,1,0,0,0],
    [1,1,0,1,0,0],
    [0,0,1,0,1,1],
    [0,0,0,1,0,1],
    [0,0,0,1,1,0],
], dtype=torch.float)
X = torch.randn(6, 4)
y = torch.tensor([0,0,0,1,1,1])
train_mask = torch.tensor([1,0,0,0,0,1], dtype=torch.bool)

A_norm = normalise_adj(A)
model = GCN(4, 8, 2)
opt = torch.optim.Adam(model.parameters(), lr=0.01, weight_decay=5e-4)

for epoch in range(100):
    model.train()
    opt.zero_grad()
    out = model(X, A_norm)
    loss = F.cross_entropy(out[train_mask], y[train_mask])
    loss.backward()
    opt.step()

Only nodes 0 and 5 are labelled, yet nodes 1 to 4 receive useful signals through the links. This is the semi-supervised effect.

Building a graph from a table

Rows in a relational table can become nodes, and foreign keys can become edges. The SQL below uses placeholder tables to show the idea.

-- nodes: one row per account
SELECT account_id, balance, age_days FROM accounts;

-- edges: accounts that transferred money to each other
SELECT sender_id AS src, receiver_id AS dst
FROM transfers
WHERE created_at >= DATE '2026-01-01';

The first query gives the feature matrix. The second gives the edge list that becomes the adjacency matrix.

Practical checks on the toy run

• Print the accuracy on unlabelled nodes after training. With so few labels, it should be better than random if the graph is homophilous.

• Try removing the edges and train a plain two-layer network. The gap between the two shows how much the structure helps.

• Try adding a third layer and watch whether accuracy falls. That is a quick way to see over-smoothing.

Turning raw rows into graph inputs

The following sketch builds a normalised sparse adjacency from an edge list. The names are placeholders.

import numpy as np
import scipy.sparse as sp

edges = np.array([[0, 1], [1, 2], [2, 3], [3, 4]])   # src, dst
n = 5

A = sp.coo_matrix(
    (np.ones(len(edges)), (edges[:, 0], edges[:, 1])), shape=(n, n)
)
A = A + A.T                      # make undirected
A = A + sp.eye(n)                # add self-loops
deg = np.asarray(A.sum(axis=1)).ravel()
d_inv_sqrt = sp.diags(deg ** -0.5)
A_norm = d_inv_sqrt @ A @ d_inv_sqrt
print(A_norm.shape, A_norm.nnz)

The sparse form keeps memory proportional to the number of edges, not to n squared.

A numeric look at two hops

Using the three-node line from above, apply the propagation twice. After the first step the values were about 1.32, 2.0 and 2.32. After the second step, node 1 becomes 0.5 times 1.32 plus 0.408 times 2.0, which is about 1.48. Node 3 becomes about 2.12 in the same way. The spread between the end nodes has shrunk from 2.0 to about 0.64. The ends are drifting toward the centre. That shrinking spread is exactly what over-smoothing means, and it shows why depth must be chosen with care.

Strengths and limitations

Strengths

• Very simple. One matrix product and one weight matrix per layer.

• Few parameters, so it works with few labels.

• Uses graph structure and features together.

• Fast on moderate graphs, since propagation is a sparse matrix product.

• Strong baseline. Many new graph methods are compared with it.

• Easy to explain, which helps when results must be reviewed.

Limitations

• Fixed averaging treats all neighbours as equally important, up to degree scaling. GAT fixes this with learned weights.

• Full-graph training can be memory heavy on very large graphs. GraphSAGE and sampling methods help.

• Over-smoothing limits useful depth. Two or three layers are typical.

• Standard GCN is transductive: it expects the full graph at training time.

• It assumes homophily. When neighbours tend to have different labels, plain averaging can hurt.

• Edge features and edge types are not handled in the basic form.

• Expressive power is limited. Some different graph structures look the same to it.

How it compares with alternatives

A common practical comparison is a graph model against a boosted tree model on features that were engineered from the graph, such as degree, neighbour averages and counts. The tree model is often competitive. The graph model wins most when the structure has rich multi-hop patterns that are hard to hand-craft.

Role in tabular foundation models

A tabular foundation model learns from raw tables with mixed column types, missing cells and often no useful column names. A GCN is not such a model. It is relevant because tables rarely live alone. Rows link to rows in other tables, and those links carry signal.

Rows, keys and graphs

A relational database is a graph in disguise. Each row is a node. A foreign key is an edge. A GCN turns this structure into features: a row's new vector blends its own columns with those of related rows. A tabular foundation model, in contrast, usually reads one flat table at a time. Combining them gives two common patterns:

• Use a graph model to compute neighbour-aware embeddings, then add them as extra columns to a flat table that a model such as TabPFN or TabICL reads.

• Flatten the neighbourhood by hand into aggregate columns such as counts, means and maxima, which is close to what one GCN layer computes.

Mixed types and missing values

A GCN expects a numeric feature matrix. For a real table you must first encode categories, dates and text, and decide how to treat missing cells. Tabular foundation models handle this inside the network with per-cell encoders and missing-value flags. When you feed a table to a GCN, you take on that preprocessing yourself. Impute with care, add missing indicators, and scale numeric columns, otherwise the averaging step will spread bad values to neighbours.

No column names

A GCN has no use for column names. Each feature is just a channel. This matches the way tabular foundation models treat anonymous columns: identity comes from position and from data statistics, not from the label. That makes both approaches robust when headers are missing or misleading.

In-context learning versus trained weights

A GCN learns weights for one graph or one family of graphs. A tabular foundation model is pre-trained on vast numbers of synthetic or real tables and predicts at inference time by reading labelled rows as context, a form of few-shot learning. Graph versions of this idea exist: a model can be pre-trained over many graphs and then adapt with little data. See /model/research and /model/architecture for how related ideas are explored for tables.

Imputation, anomaly detection and sector classification

• Imputation: neighbours often tell you the value of a missing cell. A node whose neighbours all share a category probably shares it too. This is the same logic as masked cell modeling with graph context.

• Anomaly detection: a node whose vector differs sharply from the average of its neighbours is suspicious. GCN-style models are used for fraud rings and unusual accounts. See anomaly detection.

• Semantic and sector classification: pooling node vectors gives a graph-level vector that can feed a classifier, in the spirit of semantic sector heads.

Continual learning

Graphs change. New nodes and edges appear daily. A transductive GCN must be retrained, while inductive models adapt more easily. Replay and regularisation methods such as experience replay and EWC help a model keep old knowledge as the graph grows. Benchmarks that compare these ideas against flat-table models are discussed at /model/benchmarks.

Practical guidance and best practices

Prepare the graph

• Make the graph undirected unless direction truly matters, or use separate directions as separate relations.

• Remove duplicate edges and decide how to treat self-loops.

• Keep degree scaling. Do not skip normalisation.

• Check homophily: the share of edges that join nodes with the same label. If it is low, expect weaker results.

Prepare the features

• Encode categorical columns with embeddings or one-hot vectors.

• Standardise numeric columns.

• Add a missing indicator for each column that has missing values.

• Drop identifiers that leak labels.

Choose the architecture

• Start with two layers and a hidden width of 16 to 128.

• Use dropout between 0.3 and 0.6.

• Add weight decay on the first layer.

• Add residual links or normalisation if you need more than three layers.

Train well

• Use early stopping based on a validation set of nodes.

• Evaluate on nodes that were hidden from the loss, never on the training nodes.

• Repeat with several random seeds, since results on small graphs vary.

• Compare with a feature-only baseline to prove the graph helps.

Scale up

• Use mini-batch training with neighbour sampling for large graphs.

• Consider GraphSAGE style sampling when the graph does not fit in memory.

• Precompute propagated features for simplified, linear variants when speed matters.

A short evaluation recipe

1. Fix a split of nodes into train, validation and test, and keep it for all experiments.

2. Train a feature-only model such as logistic regression or a small network on node features alone.

3. Train the GCN with the same features and the graph.

4. Train a graph-free boosted tree model with hand-made neighbour aggregates.

5. Report all three with several seeds and the spread across seeds.

6. Keep only the graph model if it beats the best baseline by more than the seed noise.

Questions to ask before using a graph at all

• Do the links exist at prediction time, or are they created after the fact?

• Are links reliable, or are they noisy guesses?

• Do linked rows really share useful properties?

• Is the extra pipeline cost justified by the gain over a flat-table model?

Common mistakes

• Leaking test labels through features or through edges that link test nodes to the answer.

• Evaluating on training nodes and reporting inflated accuracy.

• Forgetting self-loops, which makes a node ignore its own features.

• Skipping normalisation, so high-degree nodes dominate.

• Stacking many layers and then wondering why accuracy drops.

• Using a graph model when the graph carries no information, such as random links.

• Ignoring heterogeneity. A graph with different node and edge types needs relation-aware layers.

• Splitting nodes at random when the real task is to predict for future nodes. Use a time-based split instead.

Frequently asked questions

What does a GCN do in simple terms?

A GCN lets every node in a graph update its description by averaging the descriptions of its neighbours and itself, and then passing the result through a learned layer. Repeating this a few times lets each node absorb information from nodes several links away, which helps it predict a label or a property.

Why is it called a convolution?

A convolution mixes a point with its neighbours using shared weights. The GCN does the same on a graph. The neighbourhood is defined by links instead of a fixed grid, and the mixing is a normalised average. The weights in the linear layer are shared across all nodes, just as a kernel is shared across all pixels.

Why add self-loops and normalise the adjacency matrix?

Without self-loops, a node would ignore its own features during averaging. Without normalisation, nodes with many neighbours would produce very large sums and the scale of features would change from layer to layer. Dividing by the square root of the degrees keeps values on a stable scale and treats hubs and leaves more fairly.

How many layers should a GCN have?

Two or three layers are the usual choice. Each layer extends the reach by one hop, but more layers cause over-smoothing, where node vectors become nearly identical. If you need a wider reach, use residual connections, normalisation or a different architecture rather than simply going deeper.

What is over-smoothing?

Over-smoothing happens when repeated neighbour averaging makes all node vectors converge toward the same values. Once that occurs, the model can no longer tell nodes apart. It is the graph analogue of a very blurry image. Shallow networks, skip connections and normalisation reduce it.

Is a GCN transductive or inductive?

The standard GCN is usually trained transductively, meaning the whole graph, including unlabelled test nodes, is present during training. It can be extended to new nodes, but methods such as GraphSAGE were designed for the inductive case and handle unseen nodes more naturally.

When should I choose GAT instead of GCN?

Choose GAT when neighbours differ in importance and you want the model to learn that difference. For example, in a transaction network, a few neighbours may be far more informative than the rest. GCN is simpler and faster, so start there and move to attention if a baseline leaves room for improvement.

Can a GCN work with tabular data?

Yes, if the table has meaningful links between rows, such as shared customers or foreign keys. You treat rows as nodes and links as edges. If rows are independent, a graph adds nothing, and a model made for flat tables, such as a boosted tree or a tabular foundation model, is the better choice.

How does a GCN handle missing features?

It does not handle them on its own. You must impute missing values and preferably add indicator columns before building the feature matrix. Because propagation spreads values to neighbours, a poorly imputed value can affect many nodes, so imputation quality matters more than usual.

What are the main uses of GCNs?

Typical uses include classifying papers or users in a network, predicting properties of molecules, detecting fraud and unusual behaviour in transaction graphs, recommending items from interaction graphs, and enriching tabular models with relational context.

Glossary

• Adjacency matrix: A matrix whose entries show which nodes are connected.

• Aggregation: Combining neighbour vectors into one vector.

• Degree: The number of edges attached to a node.

• Edge: A link between two nodes.

• Graph Laplacian: A matrix that measures how much a signal varies across edges.

• Homophily: The tendency of connected nodes to be alike.

• Inductive learning: Generalising to nodes or graphs not seen in training.

• Message passing: The exchange of vectors between neighbouring nodes.

• Node: An entity in the graph.

• Over-smoothing: Loss of node distinctiveness after many propagation steps.

• Receptive field: The nodes that can influence a given node's output.

• Self-loop: An edge from a node to itself.

• Transductive learning: Learning where test nodes are part of the training graph.

Summary

A GCN updates each node by taking a degree-normalised average of its neighbours and itself, then applying a shared linear layer and a non-linearity. Two or three layers give a strong, cheap baseline for node classification, especially with few labels and homophilous links. Its limits are fixed weighting, over-smoothing and a transductive habit, which GAT and GraphSAGE address. For tabular foundation models, GCNs matter because real tables are linked by keys: graph embeddings can enrich flat tables, supply context for imputation and anomaly detection, and complement models that learn from raw tables in context. See /model/architecture, /model/research and /model/benchmarks for more.

Related

It belongs to Architectures in my stack, under AI and machine learning. Others in the same group: