Graph autoencoders

A graph autoencoder encodes nodes with a two-layer GCN into embeddings Z and decodes every possible edge as σ(zᵢ·zⱼ). Trained to reconstruct A, it reached 91.0% AUC on held-out Cora links (Kipf & Welling, 2016).

8 min read770 wordscore0 viewsupdated 2026-10-21

Definition

Graph autoencoder (GAE) is an unsupervised model that learns node embeddings by reconstructing the graph's own adjacency matrix. A Graph Convolutional Network (GCN) encoder maps the features XX and adjacency AA to embeddings ZZ. A parameter-free inner-product decoder, A^=σ(ZZ⊤)\hat A=\sigma(ZZ^\top), turns them back into edge probabilities. Introduced with its variational version by Thomas Kipf and Max Welling, "Variational Graph Auto-Encoders" (NIPS 2016 Workshop on Bayesian Deep Learning).

The input is one graph with NN nodes, a symmetric adjacency matrix AA and optionally node features X∈RN×FX\in\mathbb R^{N\times F}. The output is an embedding zi∈Rdz_i\in\mathbb R^d for each node, plus a score for every pair. Nothing is labelled. The training signal is the graph itself: which pairs are linked and which are not. The usual test is Link prediction: hide some edges, train on the rest, and check that the hidden edges score higher than random non-edges.

A plain Autoencoder does not fit this setting. Nodes have no fixed order, the number of neighbours varies, and there is no grid. An encoder for graphs has to treat nodes in a way that does not depend on how they are numbered. GCN layers do this: permuting the nodes permutes the rows of ZZ, and σ(ZZ⊤)\sigma(ZZ^\top) is permuted in the same way. Earlier embeddings came from spectral clustering (eigenvectors of the Laplacian; see Spectral clustering) or from random walks (DeepWalk, Perozzi et al., 2014). Neither could use node features. SDNE (Wang et al., 2016) was an autoencoder on the rows of AA, with no message passing.

Encoder and decoder

Z=GCN(X,A)=A^ ReLU(A^XW0) W1,A^=D~−1/2(A+I)D~−1/2Z=\mathrm{GCN}(X,A)=\hat{\mathcal A}\,\mathrm{ReLU}\big(\hat{\mathcal A}XW_0\big)\,W_1,\qquad \hat{\mathcal A}=\tilde D^{-1/2}(A+I)\tilde D^{-1/2}
A^\hat{\mathcal A}
symmetrically normalised adjacency with self-loops; D~\tilde D is the degree matrix of A+IA+I
W0, W1W_0,\ W_1
the only trained weights: F×32F\times32 and 32×1632\times16 in the paper, so ZZ is N×16N\times16
XX
node features; the featureless variant (GAE*) uses X=IX=I, so W0W_0 becomes a free N×32N\times32 embedding table that the GCN smooths over neighbours
A^=σ ⁣(ZZ⊤),p(Aij=1∣zi,zj)=σ(zi⊤zj)\hat A=\sigma\!\big(ZZ^\top\big),\qquad p(A_{ij}=1\mid z_i,z_j)=\sigma\big(z_i^\top z_j\big)
σ\sigma
logistic sigmoid, applied entrywise
zi⊤zjz_i^\top z_j
large when two embeddings point the same way and have large norms; negative when they point in opposite directions
graph autoencoder (Kipf & Welling, 2016): GCN encoder, inner-product decoderinputA: N × NX: N × FGCN layer 1ReLU(Â X W₀)H: N × 32GCN layer 2Â H W₁Z: N × 16decoderσ(Z Zᵀ)N × N, no weightslossweighted BCEvs A + IÂ = D̃^(−½)(A + I)D̃^(−½), built from training edges only · Cora: N = 2708, F = 1433 (or X = I)score of any pair (i, j) = σ(zᵢ·zⱼ): rank held-out edges against sampled non-edges → AUC, AP5-node example, d = 2held out01234Zz01.2, 0.2z11.0, -0.2z20.8, 0.6z30.2, 1.0z4-0.4, 1.2σ(zᵢ·zⱼ).81.76.75.61.44.76.74.66.50.35.75.66.73.68.60.61.50.68.74.75.44.35.60.75.83outlined:true edgesedges ≥ .66non-edges≤ .61held-out (3, 4): σ(1.12) = .75 > non-edges (0, 4) .44 and (1, 3) .50, so this test pair ranks first
fig.The GAE pipeline with the paper's sizes. A two-layer GCN (32 then 16 units) produces Z; the decoder σ(ZZᵀ) has no weights and outputs an N × N matrix; a weighted binary cross-entropy compares it with A + I. Below, the 5-node worked example with d = 2: the four training edges score between .66 and .76, all six non-edges score .61 or less, and the held-out pair (3, 4) scores .75.

Loss: reconstruct a sparse matrix

Training minimises Binary cross-entropy between A^\hat A and A+IA+I over all N2N^2 entries (self-loops count as positives). Real graphs are very sparse, so the zeros would swamp the ones. The paper notes that one can either reweight the positive terms or subsample the zeros. The reference implementation reweights.

L=ηN2∑i,j[w+ Aij+(−log⁡A^ij)+(1−Aij+)(−log⁡(1−A^ij))],w+=N2−PP,η=N22(N2−P)\mathcal L=\frac{\eta}{N^2}\sum_{i,j}\Big[w_+\,A^{+}_{ij}\big(-\log\hat A_{ij}\big)+\big(1-A^{+}_{ij}\big)\big(-\log(1-\hat A_{ij})\big)\Big],\qquad w_+=\frac{N^2-P}{P},\quad \eta=\frac{N^2}{2(N^2-P)}
A+A^{+}
A+IA+I built from the training edges, with PP ones
w+w_+
positive weight, so ones and zeros contribute equally in total; on Cora it is over 600
η\eta
a constant normaliser from the reference code; it rescales the loss but does not move the optimum

Evaluation follows the link-prediction protocol. 85% of edges are used for training, 5% for validation and 10% for testing. The held-out edges are removed from AA before A^\hat{\mathcal A} is built. Each validation or test set is paired with the same number of sampled non-edges. All pairs are ranked by σ(zi⊤zj)\sigma(z_i^\top z_j), and the paper reports area under the ROC curve (AUC) and average precision (AP).

Setting (Kipf & Welling, 2016)

Datasets
Cora 2,708 nodes, 5,429 edges, 1,433 features · Citeseer 3,327, 4,732, 3,703 · PubMed 19,717, 44,338, 500
Model
2-layer GCN encoder, 32 hidden units, 16-dimensional Z, Glorot initialisation
Training
full batch, 200 iterations of Adam with learning rate 0.01
Split
85 / 5 / 10% of edges; validation and test each get an equal number of random non-edges
Reporting
mean over 10 runs with random initialisation on fixed splits
MethodCora AUCCora APCiteseer AUCCiteseer APPubMed AUCPubMed AP
Spectral clustering84.688.580.585.084.287.8
DeepWalk83.185.080.583.684.484.1
GAE* (no features)84.388.178.784.182.287.4
GAE91.092.089.589.996.496.5
Link prediction, AUC / AP in % (Kipf & Welling, 2016). GAE ignores the features (X = I). The variational rows are in Variational graph autoencoders*

Without features, the GAE only matches the spectral and random-walk baselines. The gain comes from combining features with message passing. On PubMed, 500 TF-IDF features lift AUC from 82.2 to 96.4.

Try it: train a GAE and score hidden edges

GAE · 40 nodes, 4 communities · p_in 0.6, p_out 0.02 · X = I · epoch 200Z = GCN(X, Â): 40→16→2upper: σ(zᵢ·zⱼ) · lower: input Aorigin at centre; same direction → high scoreweighted BCE 0.428 · test AUC 0.907 · AP 0.862 (17 held-out edges vs 17 non-edges)116 edges: 99 for training, 17 hidden from  and from the loss · pos_weight = 5.72mean σ(zᵢ·zⱼ): same community 0.882, different communities 0.372edges never seen in training score high because their endpoints share neighbours
held-out edges
fig.A 40-node graph with four communities of 10 (p_in = 0.6, p_out = 0.02, 116 edges). 17 edges are hidden from  and from the loss, and 17 random non-edges serve as negatives. The encoder is a GCN with X = I (40 → 16 → 2), trained with Adam (lr 0.01) on the weighted BCE (pos_weight 5.72). At epoch 0 every embedding is near the origin, every score is about 0.5, and test AUC is 0.571. After 200 epochs, same-community pairs score 0.882 on average and cross-community pairs 0.372; test AUC is 0.907 and AP 0.862. With p_out = 0 the four groups are disconnected and AUC is 1.000. At p_out = 0.2 (220 edges) it falls to 0.640, because a 2-d inner product can say little beyond which group a node is in.
PairIn A?zᵢ·zⱼσ(zᵢ·zⱼ)
0–1yes1.160.761
3–4held out1.120.754
0–2yes1.080.746
2–3yes0.760.681
1–2yes0.680.664
0–3no0.440.608
2–4no0.400.599
1–3no0.000.500
0–4no−0.240.440
1–4no−0.640.345
Worked example: 5 nodes, d = 2, Z = (1.2, 0.2), (1.0, −0.2), (0.8, 0.6), (0.2, 1.0), (−0.4, 1.2). Edges 0–1, 0–2, 1–2, 2–3 are for training; 3–4 is held out

Every edge outranks every non-edge, so the AUC over all ten pairs is 1. With (3, 4) as the test positive and (0, 4), (1, 3) as sampled negatives, 0.754>0.500>0.4400.754>0.500>0.440, so the test AUC is also 1. For the loss, the training graph has 5+2⋅4=135+2\cdot4=13 ones in A+IA+I (the held-out edge is a zero during training), so w+=(25−13)/13=0.92w_+=(25-13)/13=0.92. On a graph this small, ones and zeros are nearly balanced. On Cora, w+w_+ is over 600.

python
1import torch
2import torch_geometric.transforms as T
3from torch_geometric.datasets import Planetoid
4from torch_geometric.nn import GAE, GCNConv
5
6data = Planetoid("data", "Cora", transform=T.NormalizeFeatures())[0]
7split = T.RandomLinkSplit(num_val=0.05, num_test=0.10, is_undirected=True,
8 split_labels=True, add_negative_train_samples=False)
9train_data, val_data, test_data = split(data) # edge_index holds training edges only
10
11class Encoder(torch.nn.Module):
12 def __init__(self, f_in, hidden=32, d=16):
13 super().__init__()
14 self.conv1, self.conv2 = GCNConv(f_in, hidden), GCNConv(hidden, d)
15 def forward(self, x, edge_index):
16 return self.conv2(self.conv1(x, edge_index).relu(), edge_index)
17
18model = GAE(Encoder(data.num_features)) # default decoder: sigmoid(z_i . z_j)
19opt = torch.optim.Adam(model.parameters(), lr=0.01)
20for epoch in range(200):
21 model.train(); opt.zero_grad()
22 z = model.encode(train_data.x, train_data.edge_index)
23 loss = model.recon_loss(z, train_data.pos_edge_label_index) # positives + sampled negatives
24 loss.backward(); opt.step()
25
26model.eval()
27with torch.no_grad():
28 z = model.encode(test_data.x, test_data.edge_index)
29 auc, ap = model.test(z, test_data.pos_edge_label_index, test_data.neg_edge_label_index)
GAE link prediction on Cora with PyTorch Geometric (not run here: no torch in this environment). PyG's recon_loss samples one random non-edge per positive instead of using the weighted full-matrix BCE

Later variants change one part of the model and keep the rest. Variational graph autoencoders make ZZ a Gaussian posterior with a KL term. ARGA (Pan et al., IJCAI 2018) adds an adversarial regulariser on ZZ. GraphMAE (Hou et al., KDD 2022) masks node features and reconstructs those instead of AA. The encoder can be any message-passing network, for example GraphSAGE or Graph Attention Network (GAT).

Use when

  • +Needs no labels: the adjacency matrix is the supervision
  • +Tiny model: two weight matrices, and the decoder has no parameters
  • +Uses node features, which gave +6 to +12 AUC points over the spectral and DeepWalk baselines

Avoid when

  • −The full decoder is O(N²) in time and memory; large graphs need negative sampling
  • −Transductive as trained here: the embeddings are tied to one graph (the GCN weights can still be applied to new nodes)
  • −Symmetric inner product: no edge direction or edge types

Check yourself

A GAE gets 99% test AUC on Cora, far above the paper's 91%. What is the most likely cause?

Check yourself

A graph has N = 1000 nodes and 2,000 undirected training edges. What is the positive weight w₊ of the reference implementation (self-loops included as positives)?

Remember

  • ✓Encoder: Z=A^ ReLU(A^XW0)W1Z=\hat{\mathcal A}\,\mathrm{ReLU}(\hat{\mathcal A}XW_0)W_1 (32 → 16 in the paper). Decoder: A^=σ(ZZ⊤)\hat A=\sigma(ZZ^\top), no parameters.
  • ✓Loss: BCE against A+IA+I, with positives weighted by w+=(N2−P)/Pw_+=(N^2-P)/P or with negatives sampled.
  • ✓Evaluation: 85/5/10 edge split, held-out edges removed from the encoder's graph, AUC and AP against an equal number of non-edges.
  • ✓Cora AUC 91.0, Citeseer 89.5, PubMed 96.4, against 84.6 / 80.5 / 84.2 for spectral clustering; without features, the GAE only matches the baselines.
  • ✓An inner product is symmetric and low-rank: good for communities, blind to direction.
← back to Deep Learning roadmap