Alessio Borgi

Alessio Borgi

PhD in Graph Neural Networks and Generative AI 👨🏻‍💻🤖

APPNP: Personalized PageRank Meets Graph Neural Networks

7 minute read

Published:

TL;DR: APPNP (Klicpera / Gasteiger et al., 2019) separates two entangled operations in GCN: (1) transform features with a neural network \(f_\theta(X)\), (2) propagate with \(K\) steps of personalised PageRank. The teleport probability \(\alpha\) re-injects each node's own representation at every step, so the propagation converges to a fixed point that still depends on the node — over-smoothing does not set in even at \(K = 10\).

The Problem: Transformation and Propagation Are Entangled

In GCN, each layer simultaneously:

  • Aggregates neighbour features (graph propagation)
  • Transforms the aggregated features (learned weights)

This entanglement means you cannot independently control how deep you propagate (how large a neighbourhood you use) and how expressive the per-node transformation is. More layers → both deeper propagation AND more transformation depth → over-smoothing and vanishing gradients.

APPNP’s Decoupling

APPNP breaks this into two explicit, separate steps:

Step 1: Transform — apply an MLP to the raw node features:

\[ H = f_\theta(X) \in \mathbb{R}^{N \times C}. \]

This is a standard neural network (any depth, any nonlinearity) that processes each node independently. No graph structure is used here.

Step 2: Propagate — run \(K\) steps of personalised PageRank starting from \(H\):

\[ Z^{(0)} = H, \qquad Z^{(k+1)} = (1-\alpha)\,\hat{A}\, Z^{(k)} + \alpha H, \qquad \hat{Y} = \mathrm{softmax}\!\left(Z^{(K)}\right), \]

where \(\hat{A} = \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}\) is the self-looped normalised adjacency, \(\alpha \in (0,1)\) is the teleport probability, and \(H\) is the transformed representation that gets re-injected at every step.

Why Personalised PageRank?

An unrestarted walk on a connected non-bipartite graph forgets where it started: \(\hat{A}^k\) converges to a rank-one matrix, so every node’s representation collapses onto a single shared direction. That is exactly over-smoothing. The personalised (restarting) variant prevents it.

At each step, with probability \(\alpha\), the walk restarts at its own starting node, re-injecting \(H_v\). Each node stays anchored to its own identity while still aggregating from its neighbourhood.

Because the iteration is an affine map with contraction factor \((1-\alpha) \lVert \hat{A}\rVert_2 \le 1-\alpha < 1\), it converges from any starting point to a unique fixed point, obtained by solving \(Z = (1-\alpha)\hat{A}Z + \alpha H\):

\[ Z^{\ast} = \alpha \left(I - (1-\alpha)\hat{A}\right)^{-1} H = \alpha \sum_{k=0}^{\infty} (1-\alpha)^{k} \hat{A}^{k} H . \]

The matrix \(I - (1-\alpha)\hat{A}\) is invertible precisely because the spectrum of \(\hat{A}\) lies in \([-1,1]\), so \(1 - (1-\alpha)\lambda \ge \alpha > 0\) for every eigenvalue. APPNP approximates \(Z^{\ast}\) with \(K\) power iterations; the error decays like \((1-\alpha)^K\).

Why this prevents over-smoothing — the precise statement: Write \(\hat{A} = U\Lambda U^{\top}\). The propagation acts on eigen-component \(\lambda\) with gain \(g(\lambda) = \alpha / \left(1 - (1-\alpha)\lambda\right)\). At \(\lambda = 1\) (the smooth, constant-like direction) \(g = 1\); at \(\lambda = -1\), \(g = \alpha/(2-\alpha)\), which for \(\alpha = 0.1\) is about \(0.053\). Small, but never zero. Compare plain propagation, whose gain is \(\lambda^{K} \to 0\) for every \(\lvert\lambda\rvert < 1\). That is the whole difference: unrestarted propagation annihilates all non-smooth components in the limit, whereas personalised PageRank merely attenuates them and keeps them forever. Increasing \(K\) moves you toward a fixed point, not toward a constant.

Concrete worked example — two connected nodes, \(\alpha = 0.2\).

Take a graph with just two nodes \(v, u\) joined by an edge. With self-loops, \(\tilde{A}\) is all-ones, \(\tilde{D} = 2I\), so \(\hat{A} = \begin{pmatrix}0.5 & 0.5\\ 0.5 & 0.5\end{pmatrix}\). After the MLP, \(H_v = [1.0,\, 0.0]\) and \(H_u = [0.0,\, 1.0]\).

Z⁽⁰⁾ = H                          Z⁽⁰⁾[v] = [1.00, 0.00]

Step 1:  Z⁽¹⁾ = 0.8·Â·Z⁽⁰⁾ + 0.2·H
         ·Z⁽⁰⁾ at v = 0.5·[1,0] + 0.5·[0,1] = [0.50, 0.50]
         Z⁽¹⁾[v] = 0.8·[0.50, 0.50] + 0.2·[1.00, 0.00] = [0.60, 0.40]

Step 2:  ·Z⁽¹⁾ at v = 0.5·[0.60,0.40] + 0.5·[0.40,0.60] = [0.50, 0.50]
         Z⁽²⁾[v] = 0.8·[0.50, 0.50] + 0.2·[1.00, 0.00] = [0.60, 0.40]
         → already at the fixed point

Check against the closed form: \(\left(I - 0.8\hat{A}\right)^{-1} = \begin{pmatrix}3 & 2\\ 2 & 3\end{pmatrix}\), and \(\alpha\) times that, applied to \(H = I\), gives \(Z^{\ast} = \begin{pmatrix}0.6 & 0.4\\ 0.4 & 0.6\end{pmatrix}\) — matching row for row.

Now drop the teleport (\(\alpha = 0\)): \(\hat{A}^k H \to \begin{pmatrix}0.5 & 0.5\\ 0.5 & 0.5\end{pmatrix}\), so both nodes land on \([0.5, 0.5]\) and become indistinguishable after a single step. With \(\alpha = 0.2\) the gap \(Z^{\ast}_v - Z^{\ast}_u = [0.2, -0.2]\) persists no matter how many steps you run.

Why This Works: The Neumann series \(Z^{\ast} = \alpha\sum_{k\ge 0}(1-\alpha)^{k}\hat{A}^{k}H\) says the fixed point is a weighted average over walks of every length, with a walk of length \(k\) discounted by \((1-\alpha)^{k}\). The \(k = 0\) term alone contributes a full \(\alpha\) of node \(v\)'s own \(H_v\), and no amount of propagation ever removes it. That is the anchor.

Hyperparameter Choices

  • \(\alpha = 0.1\) to \(0.2\): works well empirically. Small \(\alpha\) → more propagation weight, larger effective receptive field; large \(\alpha\) → more anchoring, closer to the plain MLP. In the limit \(\alpha \to 1\) APPNP reduces to the graph-free MLP \(f_\theta(X)\).
  • \(K = 10\) to \(20\): since the truncation error decays like \((1-\alpha)^K\), \(\alpha = 0.1\) and \(K = 10\) leaves roughly \(0.9^{10} \approx 0.35\) of the tail — enough for the approximation to behave like the fixed point in practice, and adding steps costs only sparse products, not parameters. Contrast GCN, which typically degrades beyond 2–3 layers.
  • The MLP (step 1) is typically 2 layers with ReLU and dropout.

APPNP and the Transformation-Propagation Paradigm

APPNP pioneered the idea of separating transformation from propagation, which became influential:

ModelTransformationPropagation
GCNInterleavedInterleaved
SGCNone (single linear map at the end)\(\hat{A}^K\) (pre-computed)
APPNPMLP on \(X\)Personalised PageRank
SIGNMLP on concatenated featuresMultiple \(\hat{A}^k X\), pre-computed

Pre-computation: What Can and Cannot Be Cached

Like SGC, APPNP’s propagation has no learned parameters. But unlike SGC it cannot be pre-computed away, because it is applied after the MLP: \(Z\) depends on \(H = f_\theta(X)\), which changes every gradient step. So the \(K\) sparse products must be redone each forward pass, at \(O(K\lvert E\rvert C)\) for \(C\) output channels.

Two things make this cheap anyway. First, \(C\) is the number of classes, not a wide hidden dimension, so the propagated matrix is narrow. Second, the graph is fixed, so the sparsity pattern can be prepared once. The parameter count is that of the MLP alone — independent of \(K\).

Performance

APPNP was evaluated on citation-network node classification (Cora-ML, CiteSeer, PubMed, MS Academic) and reported accuracy above GCN and GAT baselines under its own evaluation protocol, using far fewer parameters — a single MLP, with the propagation adding none.

One caveat worth internalising before you compare rows across papers: published numbers on these datasets depend heavily on the train/validation split, on how many random seeds are averaged, and on whether hyperparameters were tuned per dataset. The APPNP paper’s own contribution here was partly methodological — it argued for multiple random splits rather than the single fixed Planetoid split — so its numbers are not directly comparable to figures quoted from the GCN or GAT papers. Treat the qualitative claim (decoupling helps, and lets you propagate much further) as the durable result.

Summary

PropertyGCNAPPNP
Propagation + transformationInterleavedSeparate
Propagation depth before collapse2–3 layers10–20 steps (no collapse: converges to a fixed point)
Behaviour as depth growsGain \(\lambda^K \to 0\) off the smooth directionGain \(\alpha/(1-(1-\alpha)\lambda) > 0\) at every frequency
ParametersOne \(W^{(l)}\) per layerOne MLP, independent of \(K\)
Theoretical basisChebNet (\(K=1\))Personalised PageRank

APPNP is not just a better GCN — it is a proof of concept that separating what to compute (transformation) from where to get information (propagation) is a productive design principle. Nearly all scalable modern GNNs inherit this idea.

References

You May Also Enjoy

The Standard Library Modules Worth Knowing Before You pip install

8 minute read

Published:

Python ships with a counter, a queue, a memoiser, a CLI parser, a test framework’s smaller cousin, and a JSON-safe date library already installed — most of what people reach for a package to solve is one import away.

Files and Context Managers: Why with Is Not Optional

9 minute read

Published:

A file object that falls out of scope without with does get closed eventually — but ‘eventually’ means whenever the garbage collector gets around to it, which is not a promise any program handling more than a handful of files can live with.

Errors and Exceptions: EAFP, the Hierarchy, and Reading a Traceback

9 minute read

Published:

Exceptions in Python are not exceptional. They are a normal control-flow mechanism that the language leans on so heavily that the idiomatic style is to try the operation and handle the failure, rather than check first — which is faster, shorter, and free of race conditions.