Graph Autoencoders (GAE & VGAE)

Graph Autoencoders bring the "Compression & Reconstruction" philosophy of deep learning to graph structures. By learning to compress a graph into a low-dimensional bottleneck and then reconstruct it, we can identify hidden relationships and perform high-accuracy link prediction.

---

1. The Architectural Logic

A Graph Autoencoder consists of two distinct components:

1. Encoder: Typically a GNN (GCN or GAT) that maps both node features $X$ and graph structure $A$ into a latent matrix $Z$.
2. Decoder: A simple generative model that predicts the presence of edges based on the latent embeddings $Z$.

The Mathematical Forward Pass

For a standard GAE with a GCN encoder:

1. Latent Encoding: $Z = \text{GCN}(X, A)$
2. Edge Reconstruction: $\hat{A} = \sigma(Z Z^T)$

The term $Z Z^T$ calculates the inner product between all pairs of node embeddings. If the dot product between $z_i$ and $z_j$ is high, the decoder predicts that an edge $(i, j)$ should exist.

---

2. VGAE: The Variational Evolution

Standard GAEs are deterministic—they map each node to a single point. Variational Graph Autoencoders (VGAE) represent nodes as distributions (typically Gaussians), allowing for better generalization and a smoother latent space.

The VGAE Encoder

Instead of learning one vector $z$, the encoder learns two: a mean $\mu$ and a standard deviation $\sigma$.

• $\mu = \text{GCN}_{\mu}(X, A)$
• $\log \sigma = \text{GCN}_{\sigma}(X, A)$

We then sample the final embedding $z$ using the reparameterization trick: $z = \mu + \epsilon \odot \sigma$.

---

3. Loss Function: Binary Cross-Entropy

The goal is to make the reconstructed adjacency matrix $\hat{A}$ as close as possible to the original matrix $A$.

$\mathcal{L} = -\sum_{(i,j) \in \mathcal{E}} \log(\hat{A}_{ij}) - \sum_{(i,j) \notin \mathcal{E}} \log(1 - \hat{A}_{ij})$

For VGAE, we also add a KL-Divergence term to force the latent distributions to stay close to a standard normal distribution $\mathcal{N}(0, I)$.

---

4. Why Use GAEs?

Task	Explanation
Link Prediction	Predicting future friendships or chemical bonds between molecules.
Denoising	Reconstructing a "cleaner" version of a noisy or incomplete graph.
Dimensionality Reduction	Visualizing complex, high-dimensional networks in 2D or 3D space.

---

5. Python Implementation (PyG Style)

gae_model.py

import torch
from torch_geometric.nn import GCNConv, GAE

class GCNEncoder(torch.nn.Module):
    def __init__(self, in_channels, out_channels):
        super().__init__()
        self.conv1 = GCNConv(in_channels, 2 * out_channels)
        self.conv2 = GCNConv(2 * out_channels, out_channels)

    def forward(self, x, edge_index):
        x = self.conv1(x, edge_index).relu()
        return self.conv2(x, edge_index)

# Initialize
# encoder = GCNEncoder(num_features, 16)
# model = GAE(encoder)

# Training step
# z = model.encode(x, edge_index)
# loss = model.recon_loss(z, edge_index)
# loss.backward()

Pro Tip: Link Prediction Metrics

When evaluating a GAE, don't just use Accuracy. Because most graphs are sparse (mostly zeros in $A$), a model that predicts "no edge" everywhere will have high accuracy. Instead, use AUC-ROC and Average Precision (AP).