Generalized PageRank propagation

Overview

Graph neural networks often propagate node representations along the edges, for example by repeatedly multiplying with a normalised adjacency matrix. The problem: on graphs where neighbours tend to share a label (homophily), this smooths features well, but on graphs where neighbours tend to differ (heterophily) it erases the signal, and many propagation steps make every node look alike (over-smoothing) 2006.07988 §1 2006.07988 §3 2210.07606 §1.

The shared core of the step-weighted variants is a weighted sum over propagation steps. With the symmetric normalised adjacency Ã_sym and a feature network output H^(0), the model computes Z = Σ_k γ_k H^(k), where H^(k) = Ã_sym H^(k-1) 2006.07988 eq. 1. The variants differ only in how the weights γ_k are chosen: from a fixed rule, or learned from data 2006.07988 §3.

Viewed as a spectral filter, the sum equals U g(Λ) Uᵀ with g(λ) = Σ_k γ_k λᵏ, where Ã_sym = U Λ Uᵀ. So choosing γ is choosing a polynomial graph filter 2006.07988 §4.

Not every variant here weights steps. Adaptive Channel Mixing keeps a low-pass channel and a high-pass channel side by side and chooses the mix per node 2210.07606 §4.2. It is covered below as a separate variant.

Variants

Fixed PageRank-style weights

Weights γ_k = α(1-α)^k, with the last weight set to (1-α)^K so the weights sum to one 2006.07988 §3. The paper says this family contains APPNP as a special case 2006.07988 §3. Non-negative weights that sum to one give a low-pass filter 2006.07988 §4, so this variant cannot amplify high-frequency signal.

Single K-hop weights

Only the last step is kept: γ_k = δ_Kk. The paper says SGC is this case 2006.07988 §3. Information is taken from exactly K hops.

Learned weights (GPR-GNN)

The weights γ_k are trained together with the feature network f_θ by gradient descent 2006.07988 §3. The paper compares four initialisations: a PageRank-style start for α in {0.1, 0.2, 0.5, 0.9}, one-hot at step 0, one-hot at step K, and random 2006.07988 §5. The learned weights are not constrained to be non-negative. The paper's filter view notes that a choice like γ_k = (-α)^k with large K acts as a high-pass filter [arxiv:2006.07988 §4] 2006.07988 app. A.3. The paper reports learned weights with positive values on the homophilic PubMed and Photo, and negative values on the heterophilic Actor and Squirrel 2006.07988 §5.

Adaptive Universal Generalized PageRank Graph Neural Network is the card for this variant family and its learned-weight design.

Per-node channel mixing (ACM)

Each layer computes three channels: a low-pass channel that averages over neighbours, a high-pass channel that takes differences from neighbours, and an identity channel that keeps the node's own features. A per-node softmax over learned channel scores then mixes them 2210.07606 §4.2. The weights differ per node and per layer, not per propagation step, so this variant does not fit the γ_k sum above. The paper draws on the filterbank view from graph signal processing 2210.07606 §4.2.

The paper also gives variants that add a structure channel (ACM-GCN+) or a feature residual (ACM-GCN++) 2210.07606 app. B.

Revisiting Heterophily For Graph Neural Networks is the card for this variant. It also proposes homophily measures based on the features after aggregation 2210.07606 §3.1. Its card lists where the released code differs from the paper, for example an output scale of 3 in the code that the paper does not state. Read it before reimplementing.

When to use which

The paper does not say which initialisation gives each Table 2 entry 2006.07988 §5. Report the initialisation and α you used, because the choice moves results (see the random-initialisation row above).

Implementation sketch

The common core of the step-weighted variants is the weighted sum. The variants differ only in how gamma is filled. Shapes are per node and class.

# Generalized PageRank propagation  [arxiv:2006.07988 eq. 1]
# h0:    (n, C)   output of the feature network  [arxiv:2006.07988 §3]
# adj:   (n, n)   symmetric normalised adjacency  [arxiv:2006.07988 §2]
# gamma: (K+1,)   one weight per step  [arxiv:2006.07988 §3]

def gpr_propagate(h0, adj, gamma, K):
    # Start with the un-propagated term, weighted by gamma_0  [eq. 1]
    z = gamma[0] * h0                             # (n, C)
    h = h0
    for k in range(1, K + 1):
        # One more propagation step: H^(k) = adj H^(k-1)  [eq. 1]
        h = adj @ h                               # (n, C)
        # Add the weighted k-step term to the sum  [eq. 1]
        z = z + gamma[k] * h                      # (n, C)
    # Class scores; softmax over classes gives predictions  [eq. 1]
    return z

# Fixed PageRank-style weights, with alpha in (0, 1)  [§3]:
#   gamma[k] = alpha * (1 - alpha)**k  for k < K
#   gamma[K] = (1 - alpha)**K
# Single K-hop weights  [§3]:  gamma = one-hot at index K
# Learned weights  [§3] [§5]:  gamma is a trainable vector, initialised
#   from one of the four options in the Learned weights section

ACM does not fit this sketch. Each layer computes a low-pass channel, a high-pass channel and an identity channel, then mixes them with a per-node softmax over channel scores 2210.07606 §4.2. Use the ACM card for its layer equations, and read its "Paper vs code" section before copying them.

Contradictions

Cross-paper:

• Same GPR-GNN numbers, different protocols. The GPRGNN row in the ACM results has the same values as the GPR-GNN paper's Table 2 for Cora (79.51), CiteSeer (67.63) and PubMed (85.07) 2006.07988 tab. 2 2210.07606 app. A.1. The GPR-GNN paper runs its homophilic datasets on sparse splits and its heterophilic ones on dense splits [arxiv:2006.07988 §5]. The ACM paper says its table uses random 60/20/20 splits [arxiv:2210.07606 §6.2]. The two papers therefore report the same numbers under different protocols, and their GPRGNN rows should not be compared with each other. The ACM paper does not say which rows were copied from earlier papers 2210.07606 app. A.1.
• Column name. The ACM table's "Film" column carries the values that the GPR-GNN paper reports for Actor, for example 39.30 for GPRGNN 2006.07988 tab. 2 2210.07606 app. A.1. Match columns by the numbers and the dataset statistics, not by name.

Inside one paper:

• Timing (GPR-GNN). Table 3 and Tables 9 and 10 give different per-epoch times for the same model and dataset. For example, GCN on Chameleon is 13.83 ms in Table 3 and 16.63 ms in Table 10 2006.07988 tab. 3 2006.07988 tab. 10. Treat the timings as rough.
• Baseline count (GPR-GNN). The text says "6 baseline models" and then lists nine 2006.07988 §5.
• Figure 4 (GPR-GNN). The caption refers to panels (e)-(f), the text to panels (e)-(h) 2006.07988 fig. 4 2006.07988 §5.
• ACM-GCN values. The optimal-hyperparameter table gives ACM-GCN 68.18 on Chameleon and 90.54 on PubMed, against 69.04 and 90.66 in the main results 2210.07606 app. C 2210.07606 app. A.1. The ablation's full ACM-GCN row also differs from the main table, for example on Wisconsin (96.75 against 95.75) 2210.07606 tab. 1.
• Mixing in the ablation (ACM). The ablation without the mixing step is higher on Texas (95.25 against 95.08) 2210.07606 tab. 1. The mixing step is not uniformly better in the paper's own table.

Papers

• Adaptive Universal Generalized PageRank Graph Neural Network: proposes learned generalized PageRank weights for graph node classification and reports results on homophilic and heterophilic benchmarks. Author-reported.
• Revisiting Heterophily For Graph Neural Networks: proposes Adaptive Channel Mixing, a per-node mix of low-pass, high-pass and identity channels, and homophily measures based on post-aggregation similarity. Author-reported.

Named but not linked, because they have no card: APPNP, SGC and GCN, which the papers name as special cases or baselines 2006.07988 §3 [arxiv:2210.07606 §2.1]. Nothing from their papers is used here.