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 and adjacency to embeddings . A parameter-free inner-product decoder, , 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 nodes, a symmetric adjacency matrix and optionally node features . The output is an embedding 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 , and 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 , with no message passing.
Encoder and decoder
- symmetrically normalised adjacency with self-loops; is the degree matrix of
- the only trained weights: and in the paper, so is
- node features; the featureless variant (GAE*) uses , so becomes a free embedding table that the GCN smooths over neighbours
- logistic sigmoid, applied entrywise
- large when two embeddings point the same way and have large norms; negative when they point in opposite directions
Loss: reconstruct a sparse matrix
Training minimises Binary cross-entropy between and over all 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.
- built from the training edges, with ones
- positive weight, so ones and zeros contribute equally in total; on Cora it is over 600
- 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 before is built. Each validation or test set is paired with the same number of sampled non-edges. All pairs are ranked by , 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
| Method | Cora AUC | Cora AP | Citeseer AUC | Citeseer AP | PubMed AUC | PubMed AP |
|---|---|---|---|---|---|---|
| Spectral clustering | 84.6 | 88.5 | 80.5 | 85.0 | 84.2 | 87.8 |
| DeepWalk | 83.1 | 85.0 | 80.5 | 83.6 | 84.4 | 84.1 |
| GAE* (no features) | 84.3 | 88.1 | 78.7 | 84.1 | 82.2 | 87.4 |
| GAE | 91.0 | 92.0 | 89.5 | 89.9 | 96.4 | 96.5 |
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
| Pair | In A? | zᵢ·zⱼ | σ(zᵢ·zⱼ) |
|---|---|---|---|
| 0–1 | yes | 1.16 | 0.761 |
| 3–4 | held out | 1.12 | 0.754 |
| 0–2 | yes | 1.08 | 0.746 |
| 2–3 | yes | 0.76 | 0.681 |
| 1–2 | yes | 0.68 | 0.664 |
| 0–3 | no | 0.44 | 0.608 |
| 2–4 | no | 0.40 | 0.599 |
| 1–3 | no | 0.00 | 0.500 |
| 0–4 | no | −0.24 | 0.440 |
| 1–4 | no | −0.64 | 0.345 |
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, , so the test AUC is also 1. For the loss, the training graph has ones in (the held-out edge is a zero during training), so . On a graph this small, ones and zeros are nearly balanced. On Cora, is over 600.
1import torch2import torch_geometric.transforms as T3from torch_geometric.datasets import Planetoid4from torch_geometric.nn import GAE, GCNConv56data = 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 only1011class 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)1718model = 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 negatives24 loss.backward(); opt.step()2526model.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)Later variants change one part of the model and keep the rest. Variational graph autoencoders make a Gaussian posterior with a KL term. ARGA (Pan et al., IJCAI 2018) adds an adversarial regulariser on . GraphMAE (Hou et al., KDD 2022) masks node features and reconstructs those instead of . 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: (32 → 16 in the paper). Decoder: , no parameters.
- ✓Loss: BCE against , with positives weighted by 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.