Adaptive Universal Generalized PageRank Graph Neural Network

In plain words

Many graph neural networks work by letting each node average information from its neighbours. That helps when neighbours tend to share a label, as in a citation network. It hurts when neighbours tend to have different labels, as in a dating graph, and stacking many such layers blurs every node's features into one another.

The paper's idea is to keep the neighbour averaging, but to let the model learn how much weight each distance from a node gets. Information from direct neighbours, neighbours of neighbours, and so on each gets its own weight. The weights are trained together with the rest of the network, and they may be negative. The weights may be negative, which the paper ties to heterophilic graphs (see the filter view in the Method).

The authors argue that this makes one model work across both kinds of graph, and that it avoids the blurring problem even when many steps are used. They show what the learned weights look like on different graphs, and they report better accuracy than the baselines on most of their benchmarks.

TL;DR

• GPR-GNN feeds a 2-layer MLP's output through K+1 weighted propagation steps and learns the weights end to end eq. 1 §3.
• The weights are not restricted to be positive, which lets the filter pass high frequencies and suits heterophilic graphs §3 §4.
• Author-reported: best mean accuracy on 7 of 10 benchmark datasets (Table 2), and best at 17 of 18 settings on the authors' synthetic cSBM graphs (sparse and dense splits) tab. 2 tab. 5 tab. 6.
• The official code is public, but the repository has no LICENSE file, so no reuse right is granted; this card cites it only for the design.
• Relevant when you build a node classifier and do not know whether your graph is homophilic.

Problem

Graph neural networks have two weaknesses that the paper targets §1. First, most are built for homophilic graphs, where linked nodes share a label, and they fail on heterophilic graphs §1 §3. Second, stacking many layers causes over-smoothing: node features converge towards values set by node degree, so the features lose discriminative power §1 §3.

The paper shows that fixed propagation weights make the problem worse. APPNP and SGC use fixed Personalized PageRank (PPR) weights §3. The paper's theorem says that non-negative weights summing to one give a low-pass filter §4, which removes the high-frequency part of the signal that a heterophilic graph carries.

Assumptions: the graph is undirected and the task is semi-supervised node classification in the transductive setting §5. The theory assumes a connected graph and a training set with nodes from every class §4 app. A.4.

Method

GPR-GNN separates feature extraction from propagation. A neural network f_θ turns each node's features into a first representation. Then the model combines propagated versions of this representation with learned weights γ_k §3 eq. 1.

1. Feature network f_θ. A 2-layer MLP with 64 hidden units and ReLU §5 app. A.9. In the official code the second layer outputs one value per class, so the representation that gets propagated is the class-logit matrix GNN_models.py.
2. Propagation operator. Ã = A + I adds self-loops, D̃ is its degree matrix, and Ã_sym = D̃^(-1/2) Ã D̃^(-1/2) §2. The code uses PyTorch Geometric's gcn_norm, called with its default self-loop setting GNN_models.py.
3. Weighted sum of propagated features. The model sums the K+1 terms γ_k H^(k), where H^(0) is the network output and each further term applies Ã_sym once more eq. 1 §3. The paper uses K = 10 §5.
4. Prediction and loss. P̂ is the row-wise softmax of Z. The loss is the cross-entropy summed over training nodes app. A.4. The code uses the negative log-likelihood of log-softmax outputs, which is the same loss train_model.py.
5. Joint training. γ_k and θ are learned together, end to end, by gradient descent §3 fig. 1. The paper uses Adam app. A.9.
6. Initialisation of γ. Four choices: PPR-like weights γ_k = α(1-α)^k with γ_K = (1-α)^K for α in {0.1, 0.2, 0.5, 0.9}; the one-hot weights γ_k = δ_0k; the one-hot weights γ_k = δ_Kk; and random initialisation §5. The paper shows learned weights under random initialisation for Cora and Texas and says the patterns are not forced by the initialisation §3 fig. 1.
7. Special cases. APPNP is the case γ_k = α(1-α)^k with γ_K = (1-α)^K. SGC is the case γ_k = δ_Kk §3.
8. Filter view. Let Ã_sym = U Λ U^T. Then Σ_k γ_k Ã_sym^k = U g(Λ) U^T with g(λ) = Σ_k γ_k λ^k, so learning γ means learning a polynomial graph filter §4.

Formula, in the paper's notation eq. 1:

\hat{P} = \mathrm{softmax}(Z), \quad Z = \sum_{k=0}^{K} \gamma_k H^{(k)}, \quad H^{(k)} = \tilde{A}_{sym} H^{(k-1)}, \quad H^{(0)}_{i:} = f_\theta(X_{i:}) eq. 1

Theory, informal §4 app. A.3 app. A.4:

• If every γ_k is non-negative, the γ_k sum to one, and some γ_k is positive, the filter is low-pass. With γ_k = (-α)^k for α in (0, 1) and large K, it acts as a high-pass filter §4 app. A.3.
• Over-smoothing: for large k, the gradient with respect to γ_k has the same sign as γ_k, so |γ_k| shrinks when those steps hurt the loss. The result assumes an optimizer with a decreasing learning rate, such as SGD §4 app. A.4.

The synthetic graphs come from a contextual stochastic block model (cSBM) §5 app. A.5. The paper gives the homophily knob φ in terms of λ and μ, where ξ = n/f and ε is a margin:

\phi = \frac{2}{\pi}\arctan\!\left(\frac{\lambda\sqrt{\xi}}{\mu}\right), \qquad \lambda^2 + \frac{\mu^2}{\xi} = 1 + \epsilon §5

The paper sets n = 5000, f = 2000 (so ξ = 2.5) and ε = 3.25 app. A.5.

Pseudocode for the forward pass eq. 1 §3:

# GPR-GNN forward pass  [eq. 1] [§3]
# Input:  features (n, f); adj (n, n) = A~_sym; gammas (K+1,)
# Output: log-probabilities (n, C)

def gpr_gnn_forward(features, adj, gammas, training):
    # Feature network f_theta: dropout, linear, ReLU, dropout, linear
    # [app. A.9] [code: src/GNN_models.py#L109-L115]
    hidden = dropout(features, 0.5, training)     # (n, f)
    hidden = relu(linear_1(hidden))               # (n, 64)
    hidden = dropout(hidden, 0.5, training)       # (n, 64)
    first = linear_2(hidden)                      # H^(0), (n, C)

    # Optional dropout on the propagated input, rate searched
    # [app. A.9] [code: src/GNN_models.py#L117-L122]
    first = dropout(first, dprate, training)      # (n, C)

    # Start the weighted sum with gamma_0 * H^(0)  [eq. 1]
    # [code: src/GNN_models.py#L76]
    propagated = gammas[0] * first                # (n, C)
    step = first
    for k in range(1, K + 1):
        # H^(k) = A~_sym H^(k-1)  [eq. 1]
        step = adj @ step                         # (n, C)
        # Z = sum_k gamma_k H^(k)  [eq. 1] [code: src/GNN_models.py#L77-L80]
        propagated = propagated + gammas[k] * step
    # P = softmax(Z), returned in log form  [eq. 1]
    return log_softmax(propagated)                # (n, C)

Training loop with validation-based selection app. A.9 §5:

# Training with validation-based model selection
# [app. A.9] [code: src/train_model.py#L82-L106]
# Input:  graph with train, val and test masks; max_epochs = 1000
# Output: test accuracy at the epoch with the lowest validation loss

def train_one_run(graph, max_epochs):
    # Adam with a searched learning rate; no scheduler in the code
    # [app. A.9] [code: src/train_model.py#L57-L71]
    optimizer = adam(parameters, learning_rate)
    best_val_loss = infinity
    selected_test_acc = 0.0
    val_loss_history = []
    for epoch in range(max_epochs):
        # Full-batch step; NLL on training nodes only
        # [code: src/train_model.py#L24-L33]
        train_step(graph, optimizer)
        val_loss, test_acc = evaluate(graph)      # eval mode, no dropout
        # Keep the test accuracy of the best validation loss so far
        # [code: src/train_model.py#L88-L97]
        if val_loss < best_val_loss:
            best_val_loss = val_loss
            selected_test_acc = test_acc
        # Stop when the loss is above the mean of the last 200 epochs
        # Paper: checked after half of max_epochs; code: after epoch 200
        # [app. A.9] [code: src/train_model.py#L99-L106]
        if epoch > 200 and val_loss > mean(val_loss_history[-200:]):
            break
        val_loss_history.append(val_loss)
    return selected_test_acc

Hyperparameters

Values stated in the paper are cited to the paper. Values taken from the repository are marked as code-only, because the paper does not state them.

Per-dataset GPR-GNN settings (code-only: the paper does not give them, and they come from the repository's reproduction script, whose settings the README repeats). Unset values use the code defaults: weight decay 0.0005 train_model.py and GPR dropout 0.5 train_model.py.

Results

Author-reported. Setup: GPR-GNN and nine baselines, each run 100 times with random splits and initialisations, on five homophilic and five heterophilic benchmarks §5. The paper gives mean accuracy with a 95% confidence interval tab. 2. The bold marking below follows the paper, which also underlines cells within the interval of the best result; the underline is not shown. Hardware: one NVIDIA Tesla P100 GPU app. A.9.

Dataset statistics tab. 1:

Main results, mean accuracy (%) ± 95% CI, real benchmarks tab. 2:

Reading of Table 2 tab. 2 §5: GPR-GNN has the best mean on seven datasets (Cora, PubMed, Photo, Chameleon, Actor, Squirrel, Texas). On Computers and Cornell it is within the interval of the best mean (SAGE and APPNP). On Citeseer, APPNP is higher. The MLP is close to the GNNs on Texas and Cornell, where the paper conjectures that the graph topology is weakly informative §5.

Homophilic results with dense splits tab. 7:

Synthetic cSBM, sparse split: mean accuracy (%) ± 95% CI tab. 5. The paper's Figure 2 shows the same comparison fig. 2.

Synthetic cSBM, dense split: mean accuracy (%) ± 95% CI tab. 6.

Oversmoothing test: GPR weights initialised at δ_Kk, dense cSBM at φ = -1 (mean accuracy at epoch 0 and at the final epoch) tab. 8 app. A.10.

The text gives a cSBM run for φ = -1 with dense split: 96 of 100 runs predict one label for all nodes at epoch 0, and the final accuracy is 98.79% against 50.07% at epoch 0 §5.

Efficiency, average time per epoch and total time, selected datasets tab. 3. The table and the appendix tables disagree in several cells (see Pitfalls), so use these as rough orders of magnitude only.

Efficiency, homophilic datasets tab. 9:

Efficiency, heterophilic datasets tab. 10:

Other reported results §5 fig. 3 fig. 4:

• The learned weights are positive on the homophilic datasets PubMed and Photo and include negative values on the heterophilic Actor and Squirrel §5 fig. 4.
• On cSBM with random initialisation, the weights decrease at φ = 0.25, increase at φ = 0.75, and shrink in size at φ = -0.25. For heterophilic graphs in general, the paper reports a zig-zag shape §5 fig. 3.
• The learned γ_0 has the largest magnitude on Actor, which the paper reads as most of the information lying in the node features §5 fig. 4.

Paper vs code

The official repository is jianhao2016/GPRGNN at commit 4e0a7ee5435058b70eaec3c23c55fb96dc37f2d5. The paper's footnote links it directly, its README names the ICLR 2021 paper as the source, and the owner name matches author Jianhao Peng README.md §1. It is used as the official code on that basis. The repository has no LICENSE file, so its code is not licensed for reuse. This card does not quote any code, and it cites the code only for design details.

The following are discrepancies or details that the paper does not state. Each item cites both sides where both exist.

• Early stopping. The appendix says the stopping check starts after half of the maximum epoch count, which is 500 for 1000 epochs app. A.9. The code starts the check after epoch 200 train_model.py (default early_stopping = 200 train_model.py). The 200-epoch averaging window is the same in both.
• Weight decay on γ. The paper says weight decay is searched "for all models" §5. The code gives the GPR weights a weight decay of 0 and applies the searched value only to the two MLP layers train_model.py.
• Random initialisation. The paper says random initialisation uses PyTorch's default §5. The code draws uniformly from ±sqrt(3/(K+1)) and divides by the L1 norm GNN_models.py GNN_models.py.
• α = 0 and α = 1. The paper lists α in {0.1, 0.2, 0.5, 0.9} plus the two one-hot initialisations §5. In the code's PPR path, α = 0 gives the one-hot weights at step K, and α = 1 gives the one-hot weights at step 0 GNN_models.py. The reproduction script uses α = 0.0 for Squirrel and α = 1.0 for Chameleon and Texas Reproduce_GPRGNN.sh Reproduce_GPRGNN.sh Reproduce_GPRGNN.sh. This reading is ours, derived from the formula.
• Initialisation used in Table 2. The paper does not say which initialisation gives each Table 2 entry. The reproduction script keeps the code's default PPR path and sets α per dataset Reproduce_GPRGNN.sh train_model.py.
• Confidence intervals. The paper reports 95% intervals tab. 2. The code prints the mean and the standard deviation only train_model.py. The repository does not show the conversion.
• Model selection. The paper does not say which epoch's accuracy is reported. The code reports the test accuracy at the epoch with the lowest validation loss train_model.py.
• Optimiser schedule. The over-smoothing theorem assumes SGD with a decreasing learning rate §4 app. A.4. The experiments use Adam with a constant learning rate; the repository has no scheduler train_model.py.
• Propagated tensor. The paper's Eq. 1 writes H^(0) as "hidden state features" eq. 1. The code propagates the C-column output of the second linear layer, so the propagated tensor has one column per class GNN_models.py.
• Dropout. The paper says the GPR dropout is searched over {0, 0.5, 0.7} app. A.9. The code applies it to the propagated input, after the second linear layer and before the first propagation step GNN_models.py.
• GAT width. The paper says the first GAT layer has 8 heads of 8 units app. A.9. The code's first layer uses args.hidden per head, whose default is 64 GNN_models.py train_model.py. Run with --hidden 8 to match the paper.
• JK-Net. The code adds one propagation step with α = 0 before the output layer GNN_models.py GNN_models.py. The appendix does not mention it app. A.9.
• Baselines not in the repository. The --net choices are GCN, GAT, APPNP, ChebNet, JKNet and GPRGNN train_model.py. SGC, SAGE and MLP are not implemented there. The paper says the baselines use the PyTorch Geometric implementations §5 app. A.9, and Geom-GCN uses the authors' own code §5.
• Average degree. The paper gives n, f and ε but not d app. A.5. The code generates the graphs with average degree 5 create_cSBM_dataset.sh.
• Heterophilic graph preparation. The paper says the directed heterophilic graphs were made undirected app. A.9. The WebKB loader symmetrises its edges dataset_utils.py. For Chameleon, Squirrel and Actor the code takes the edges from PyTorch Geometric without an explicit symmetrisation step dataset_utils.py. We did not run the loader to check the result.
• Dataset names. The code calls Actor "film" dataset_utils.py.
• Learning rate default. The code default is 0.002 train_model.py. Table 2's per-dataset values are 0.01 or 0.05, so the default is not the one used for the reported numbers.

Pitfalls

• Learned weights can be negative. The paper's low-pass result needs non-negative weights that sum to one §4. Nothing in the paper constrains the learned weights, so check their signs and magnitudes on your own graph before you read the filter as low-pass or high-pass.
• Propagate the class-logit tensor. Eq. 1 reads like propagation of a hidden representation. The code propagates the output of the second linear layer, which has one column per class GNN_models.py. Implement the propagation on the logits, unless you have a reason to change it.
• Self-loops. The paper defines à with self-loops §2. The code's normalisation adds them by default GNN_models.py. Using the adjacency without self-loops changes the operator.
• Early-stopping rule. The paper and code disagree on when the rule starts (see Paper vs code). Pick one and state it when you report numbers.
• Initialisation affects the result. The paper says random initialisation costs little on dense splits and more on sparse splits §5. On the sparse cSBM split, GPRGNN(random) trails GPRGNN by 8.8 points at φ = -1 and by 14.6 points at φ = -0.5 (88.39 against 97.19, and 66.91 against 81.54) tab. 5. The gaps are our arithmetic from the table.
• Sparse split, weak signal. On the sparse cSBM split at φ = -0.25, GPR-GNN reaches 60.65%, below SAGE (63.88%) and GCN-Cheby (63.96%) tab. 5. The claim of wins holds for the other settings.
• Baseline count. The paper says it compares against "6 baseline models" and then names nine §5.
• Theorem assumptions. The over-smoothing and filter results assume a connected graph, a training set with nodes from every class, and a large enough k' §4 app. A.4. The paper does not check whether the benchmark graphs satisfy these, and the claims are asymptotic.
• Homophily measure. The paper says H(G) cannot separate graphs whose topology is informative from graphs whose topology is not, using a two-graph example app. A.2 fig. 6. Do not select a method by H(G) alone.
• Cost. Each forward pass runs K sparse propagations and keeps K+1 propagated tensors for backpropagation GNN_models.py. The paper's efficiency tables show GPR-GNN close to APPNP per epoch tab. 3. This memory point is our reading of the code.
• Timing tables disagree. Table 3 and Tables 9–10 differ in several cells. For example, GCN on Chameleon is 13.83 ms per epoch in Table 3 and 16.63 ms in Table 10. The GCN-Cheby row of Table 3 matches the SAGE row of Table 10 on Chameleon and Squirrel (89.41 ms and 440.55 ms). Treat the timings as rough.
• Figure 4 caption. The caption refers to panels (e)-(f) fig. 4, but the text refers to panels (e)-(h) §5. The figure shows four epoch snapshots.
• Split effects. The homophilic results use sparse splits and the heterophilic results use dense splits §5 tab. 2. Compare numbers within a dataset only.
• Geom-GCN numbers. The paper says Geom-GCN uses "the best variants in the original paper" §5. It is not stated whether the Table 2 entries were copied or re-run. Two cells are NA tab. 2.
• Over-smoothing test. The authors' test at δ_Kk tab. 8 reports how often the model predicts one label for every node at epoch 0. The result is for the stated initialisation and splits only.
• Code licence. The repository has no LICENSE file. Reading the code to check the design is fine; copying it into a commercial product is not covered.

Lineage

• Builds on: Generalized PageRank methods for seed-expansion graph clustering §3, with the learned-weight view taken from Kloumann et al. and Li et al. (2019). The paper cites Personalized PageRank as a special case §3.
• Uses: the symmetric normalised adjacency Ã_sym §2, the same operator the GCN layer applies §3.
• Compared against: MLP, GCN, GAT, JK-Net, GCN-Cheby, APPNP, SGC, SAGE and Geom-GCN §5 tab. 2. APPNP and SGC are special cases of the model §3.
• Benchmark sources: the cSBM generator of Deshpande et al. app. A.5, and the heterophilic benchmarks and the H(G) measure of Pei et al. (Geom-GCN) §3 §5.
• Superseded by: none recorded in this wiki.