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

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

**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 $X$ and adjacency $A$ to embeddings $Z$. A parameter-free inner-product decoder, $\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 $N$ nodes, a symmetric adjacency matrix $A$ and optionally node features $X\in\mathbb R^{N\times F}$. The output is an embedding $z_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 $Z$, and $\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 $A$, with no message passing.

## Encoder and decoder

$$
Z=\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}
$$

- $\hat{\mathcal A}$: symmetrically normalised adjacency with self-loops; $\tilde D$ is the degree matrix of $A+I$
- $W_0,\ W_1$: the only trained weights: $F\times32$ and $32\times16$ in the paper, so $Z$ is $N\times16$
- $X$: node features; the featureless variant (GAE*) uses $X=I$, so $W_0$ becomes a free $N\times32$ embedding table that the GCN smooths over neighbours

$$
\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
- $z_i^\top z_j$: large when two embeddings point the same way and have large norms; negative when they point in opposite directions

> Figure: 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 $\hat A$ and $A+I$ over all $N^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.

$$
\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+I$ built from the training edges, with $P$ ones
- $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 $A$ before $\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 $\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

Link prediction, AUC / AP in % (Kipf & Welling, 2016). GAE* ignores the features (X = I). The variational rows are in **Variational graph autoencoders**

| 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

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

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

| 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, $0.754>0.500>0.440$, so the test AUC is also 1. For the loss, the training graph has $5+2\cdot4=13$ ones in $A+I$ (the held-out edge is a zero during training), so $w_+=(25-13)/13=0.92$. On a graph this small, ones and zeros are nearly balanced. On Cora, $w_+$ is over 600.

```python
import torch
import torch_geometric.transforms as T
from torch_geometric.datasets import Planetoid
from torch_geometric.nn import GAE, GCNConv

data = Planetoid("data", "Cora", transform=T.NormalizeFeatures())[0]
split = T.RandomLinkSplit(num_val=0.05, num_test=0.10, is_undirected=True,
                          split_labels=True, add_negative_train_samples=False)
train_data, val_data, test_data = split(data)   # edge_index holds training edges only

class Encoder(torch.nn.Module):
    def __init__(self, f_in, hidden=32, d=16):
        super().__init__()
        self.conv1, self.conv2 = GCNConv(f_in, hidden), GCNConv(hidden, d)
    def forward(self, x, edge_index):
        return self.conv2(self.conv1(x, edge_index).relu(), edge_index)

model = GAE(Encoder(data.num_features))        # default decoder: sigmoid(z_i . z_j)
opt = torch.optim.Adam(model.parameters(), lr=0.01)
for epoch in range(200):
    model.train(); opt.zero_grad()
    z = model.encode(train_data.x, train_data.edge_index)
    loss = model.recon_loss(z, train_data.pos_edge_label_index)   # positives + sampled negatives
    loss.backward(); opt.step()

model.eval()
with torch.no_grad():
    z = model.encode(test_data.x, test_data.edge_index)
    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

> **Hide test edges from the encoder too:** It is not enough to leave held-out edges out of the loss. If they remain in $A$ when $\hat{\mathcal A}$ is built, message passing mixes the two endpoints' features, and their embeddings end up close for a trivial reason. Test AUC is then inflated. Build the encoder's graph from training edges only, as `RandomLinkSplit` does. Also sample negatives only from pairs that are non-edges in the full graph.

> **What an inner product can and cannot express:** $\sigma(z_i^\top z_j)$ is symmetric, so it cannot model edge direction. It also favours large norms: a node whose $\lVert z\rVert$ is large scores highly with everyone it points toward, which is how the GAE encodes high degree. With $d$ dimensions it is a rank-$d$ logistic factorisation of $A$. That fits community structure well but fits "friends of friends who are not friends" badly. Directed graphs need asymmetric decoders such as $z_i^\top R\,z_j$ (see **Knowledge graph embeddings**). Learned MLP decoders are another option.

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

**Strengths**

- 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

**Limitations**

- 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

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

- A. The 16-dimensional latent space is too small
- B. The test edges were left in the adjacency matrix the encoder propagates over
- C. pos_weight was set too high
- D. The decoder should have used a softmax instead of a sigmoid

**Answer:** B. The test edges were left in the adjacency matrix the encoder propagates over — If held-out edges stay in Â, the GCN averages each endpoint's features with the other's, so the inner product of the two embeddings is high for a trivial reason. Building Â from training edges only removes this leak.

**Question:** 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)?

- A. About 1
- B. About 50
- C. About 199
- D. About 1000

**Answer:** C. About 199 — $P=1000+2\cdot2000=5000$ ones in $A+I$, so $w_+=(10^6-5000)/5000=199$. Each positive counts about 199 times as much as a zero, so both classes contribute equally in total.

**Key points**

- Encoder: $Z=\hat{\mathcal A}\,\mathrm{ReLU}(\hat{\mathcal A}XW_0)W_1$ (32 → 16 in the paper). Decoder: $\hat A=\sigma(ZZ^\top)$, no parameters.
- Loss: BCE against $A+I$, with positives weighted by $w_+=(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.

---

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