Revisiting Heterophily For Graph Neural Networks

In plain words

Most graph neural networks work by letting each node average the features of its neighbours. That works well when neighbours tend to share a label. On graphs where neighbours tend to differ, plain averaging blurs the nodes together and the model loses accuracy. The paper asks when this blurring really hurts, and proposes a way to measure it that looks at the neighbourhood after averaging, not only at how often neighbours share labels.

The method is a layer that keeps three views of each node side by side: the average of its neighbours, the difference between the node and its neighbours, and the node's own features. A small learned gate then decides, separately for each node, how much of each view to use. Nodes that need smoothing get more averaging, nodes that need to stand out from their neighbours get more difference, and the rest keep their own features. The layer can be dropped into standard GNN layers. On ten node-classification benchmarks, some with and some without many different-label neighbours, the authors report that adding it to baseline GNNs gives clear gains.

TL;DR

• Standard GNN aggregation can erase the difference between nodes whose neighbours disagree with them. The paper defines homophily metrics from post-aggregation similarity and reports that they track GNN accuracy better than the usual edge, node and class homophily §3.1 §3.2 fig. 2.
• The proposed ACM layer runs three channels in parallel (low-pass, high-pass, identity) and mixes them with node-wise weights §4.2.
• Author-reported results on ten benchmarks with 60/20/20 random splits: ACM-GCN reaches 94.75% on Cornell and 90.66% on PubMed app. A.1.
• The official code (MIT, author's repository) is close to the paper but differs in several details. Read "Paper vs code" before reimplementing.

Problem

Message passing averages neighbour features. Averaging helps when neighbours share labels (homophily). When neighbours have different labels (heterophily), the averaged features can mix classes and become hard to separate §1 §2.2. The usual homophily measures count label agreement across edges, but they ignore the features and the aggregation operator. The paper shows cases where they give a low score even though nodes remain separable after aggregation, such as a bipartite example where nodes swap colours §3.1 fig. 1.

Existing uni-channel GNNs use only a low-pass filter (averaging) or only a high-pass filter. Each keeps only part of the input signal §4.2. The paper argues that the best channel differs per node §4.2 fig. 4.

Method

Notation: graph with N nodes, adjacency A, one-hot labels Z (N x C), features X (N x F). The renormalised random-walk matrix is Â_rw = D̃⁻¹Ã with à = A + I. The low-pass operator is Â_rw and the high-pass operator is I − Â_rw §2.1.

1. Two graph-signal filters. The affinity matrices act as low-pass filters, and their complements I − Â_rw act as high-pass filters. In its experiments the paper uses Â_rw as the low-pass operator and I − Â_rw as the high-pass operator §2.1 §6.2.

2. Post-aggregation similarity. Define S(Â, X) = ÂX (ÂX)ᵀ. The aggregation similarity score counts nodes whose mean similarity to their own class is at least their mean similarity to other classes eq. 4 §3.1. The paper rescales it to [0, 1] with max(2 S_agg − 1, 0) eq. 8. The label-only version, H_agg^M, replaces X with Z eq. 9. The derivation of the gradient link is in eq. 5 and eq. 6 §3.1.

3. Diversification. The high-pass operator I −  can separate some nodes that aggregation cannot. The paper defines a diversification-distinguishability score eq. 10 eq. 11 §4.1. For two classes, with X = Z and  = Â_rw, every node is diversification-distinguishable §4.1, Theorem 1.

4. ACM channels (option 1, called "ACM"). For each layer, compute three channels: low-pass H_L = ReLU(Â_rw H W_L), high-pass H_H = ReLU((I − Â_rw) H W_H), and identity H_I = ReLU(H W_I). Option 2 ("ACMII") puts the ReLU before propagation instead §4.2, unnumbered display. The paper says the same framework can be combined with many other GNN layers in a similar way §4.2.

5. Node-wise weights. Each channel gets a per-node score σ(H_c w_c), where w_c has size F_out x 1. The three scores are divided by a temperature T and multiplied by a learned 3 x 3 matrix W_Mix. A row-wise softmax gives the weights α_L, α_H, α_I §4.2.

6. Mixing. The layer output is H = ReLU(diag(α_L) H_L + diag(α_H) H_H + diag(α_I) H_I) §4.2, unnumbered display. The paper's count of layer parameters is 3 F_{l−1}(F_l + 1) + 9, against F_{l−1} F_l for GCN. Its cost is about twice a GCN layer in the reported timings §4.2 tab. 1.

7. Variants. ACM-GCN+ adds a structure channel H_A = ReLU(A W_A), with W_A of size N x F_l, and a fourth weight. ACM-GCN++ also adds a residual H_X = ReLU(X W_X). Both use layer normalisation before the scores in the paper's notation app. B. The code does not apply that normalisation (see "Paper vs code").

8. Experiments. Ten benchmark datasets: Cornell, Wisconsin, Texas, Film, Chameleon, Squirrel, Deezer-Europe, Cora, CiteSeer, PubMed §6.2 app. A.1.

Key equation for the mixing step, as written in the paper (§4.2, unnumbered):

H^{l} = \mathrm{ReLU}\big(\mathrm{diag}(\alpha_L^{l}) H_L^{l} + \mathrm{diag}(\alpha_H^{l}) H_H^{l} + \mathrm{diag}(\alpha_I^{l}) H_I^{l}\big)

Pseudocode for one ACM layer (option 1), following the paper's Section 4.2 display. The paper's temperature T is set in the appendix app. B:

# One ACM layer, option 1 ("ACM")  [§4.2]
# H_prev: (N, F_in); A_lp = D~^-1 (I + A) (N, N); A_hp = I - A_lp
# Returns H: (N, F_out)

def acm_layer(H_prev, A_lp, A_hp, params, T):
    # Feature extraction: propagate, then ReLU  [§4.2]
    H_low = relu(A_lp @ (H_prev @ params.W_low))     # (N, F_out)
    H_high = relu(A_hp @ (H_prev @ params.W_high))   # (N, F_out)
    H_id = relu(H_prev @ params.W_id)                # (N, F_out)
    # Per-node score for each channel  [§4.2]
    s_low = sigmoid(H_low @ params.v_low)            # (N, 1)
    s_high = sigmoid(H_high @ params.v_high)         # (N, 1)
    s_id = sigmoid(H_id @ params.v_id)               # (N, 1)
    # Row-wise softmax over the 3 channels, temperature T  [§4.2]
    scores = concat([s_low, s_high, s_id], axis=1)   # (N, 3)
    alpha = softmax((scores / T) @ params.W_mix, axis=1)  # (N, 3)
    # Node-wise weighted sum, then ReLU  [§4.2]
    mixed = (alpha[:, 0:1] * H_low
             + alpha[:, 1:2] * H_high
             + alpha[:, 2:3] * H_id)
    # Official code multiplies this sum by 3 (see Paper vs code)
    # [code: ACM-Pytorch/models/layers.py#L200]
    return relu(mixed)

The two-layer model used by the official code, with dropout placement from the code (the paper does not state it):

# ACM-GCN forward, 2 layers  [§4.2] [app. C]
# Dropout placement is taken from the code, not the paper.

def acm_gcn_forward(X, A_lp, A_hp, p_drop, training):
    # Dropout on the input  [code: ACM-Pytorch/models/models.py#L116]
    H0 = dropout(X, p_drop, training)
    # First ACM layer, T = 3  [app. B] [code: ACM-Pytorch/models/layers.py#L95]
    H1 = acm_layer(H0, A_lp, A_hp, params_1, T=3)
    # Dropout between layers  [code: ACM-Pytorch/models/models.py#L160]
    H1 = dropout(H1, p_drop, training)
    # Output layer, same form with F_out = number of classes  [§4.2]
    logits = acm_layer(H1, A_lp, A_hp, params_2, T=3)
    # Log-softmax, then negative log-likelihood  [code: ACM-Pytorch/train.py#L118]
    return log_softmax(logits, axis=1)

Pseudocode for the modified aggregation homophily H_agg^M (label-only):

# Modified aggregation homophily H_agg^M  [§3.1] [eq. 7] [eq. 8] [eq. 9]
# A_hat: (N, N) aggregation operator; Z: (N, C) one-hot labels

def h_agg_modified(A_hat, Z):
    # Post-aggregation similarity, with labels in place of features  [eq. 9]
    AZ = A_hat @ Z                                   # (N, C)
    S = AZ @ AZ.T                                    # (N, N)
    # True where two nodes share a label, self included  [eq. 7]
    same = (Z @ Z.T) > 0                             # (N, N) bool
    count = 0
    for v in nodes:
        # Mean similarity to v's class, v included  [eq. 7]
        mean_same = mean(S[v, same[v]])
        # Mean similarity to all other classes  [eq. 7]
        mean_other = mean(S[v, ~same[v]])
        if mean_same >= mean_other:
            count = count + 1
    S_agg = count / N                                # [eq. 7]
    # Rescale to [0, 1]  [eq. 8]
    return max(2 * S_agg - 1, 0)                     # H_agg^M  [eq. 9]

Hyperparameters

Optimal ACM-GCN settings on random 60/20/20 splits app. C (2 layers, hidden 64 throughout):

Optimal ACM-GCN+ settings on random splits app. C. "With A" marks whether the structure channel is on:

The fixed-split runs use a script with per-dataset settings for ACM-GCN+ and ACMII-GCN+ acmgcnp_reproduce_fixed_splits.sh. I did not check those values line by line against the appendix table for fixed splits.

Results

Author-reported, mean ± standard deviation of test accuracy (%). Setup: ten benchmark datasets, random 60/20/20 splits, 10 runs (Deezer-Europe: 50/25/25, 5 runs), Adam §6.2 app. A.1. Rows are a subset of the paper's table. Omitted rows (GAT, APPNP, GCN+JK, GAT+JK, MixHop, FAGCN, GraphSAGE, Geom-GCN, GCNII, SGC-2, Snowball-3, ACM-SGC-2, ACM-GCNII, ACM-GCNII*, ACM-Snowball-2/3, ACMII-Snowball-2/3) are in app. A.1. In the paper, some baseline rows are copied from earlier papers. The GCNII* in the table is a model variant, not a marker. NA means not reported, OOM means out of memory.

Fixed 48/32/20 splits from Geom-GCN, nine datasets (no Deezer-Europe) app. A.2. Subset of rows:

Dataset statistics as reported app. A.1. H_agg^M is the paper's label-only aggregation homophily eq. 9:

Ablation on nine datasets, ACM-GCN block only tab. 1, §6.1. ✓ marks a component on. The paper's ACM-SGC-1 and ACMII-GCN blocks are in the same table. Rank is the paper's average rank:

Paper's efficiency claim: running time per epoch roughly doubles relative to the base model §6.1. For ACM-GCN on Cornell the table gives 8.25 ms per epoch against 3.67 ms for GCN tab. 1.

Paper vs code

Official code: SitaoLuan/ACM-GNN at 75b4853f29b2ce0844283e4a64c4b1120feb295c (MIT). The repository's own PDF is named ..._updated.pdf, so the code may match a later version than arXiv v1, which this card cites. I checked the PyTorch implementation in ACM-Pytorch/. Differences:

• Layer count. The paper describes an L-layer model §4.2. The code always builds two graph layers for acmgcn, acmgcnp and acmgcnpp models.py. The --layers flag has no effect on these models arg_parser.py.
• Output scale. The paper's mixing step has no constant §4.2. The code multiplies the three-channel mix by 3 layers.py layers.py, and the structure version multiplies by 1 layers.py. The constant scales the layer output, so it interacts with the learning rate and weight decay.
• Layer normalisation in ACM+ and ACM++. The appendix puts layer normalisation before the channel scores app. B. The code tests model_type == "acmgcn+" or "acmgcn++" layers.py layers.py. The model names passed in are acmgcnp and acmgcnpp arg_parser.py, so the normalisation is never applied in the shipped code.
• Residual in ACM++. The paper adds H_X = ReLU(X W_X) to every layer output app. B. The code adds a dropout-applied ReLU(Linear(X)) once, to the input of the second layer models.py models.py models.py.
• Structure channel. The code uses a learned N x F embedding multiplied by the raw adjacency A, which has no self-loops and is not normalised layers.py layers.py utils.py. The paper writes H_A = ReLU(A W_A) without saying which A app. B.
• Feature normalisation. The code row-normalises X, except for acmgcnp with structure channel on utils.py. The paper does not state feature preprocessing §6.2.
• Propagation operators. Match: the low-pass operator is row-normalised I + A, and the high-pass operator is I minus it utils.py utils.py.
• Option 1 and option 2. Match: the default ACM uses ReLU after propagation, and the variant flag, which gives ACMII, applies ReLU before propagation layers.py.
• Random splits. The paper says 60/20/20 random splits §6.2. The code takes round(0.6 · N / C) training nodes per class, round(0.2 · N) validation nodes and the rest as test utils.py utils.py.
• Model selection. The code records test accuracy at the epoch with the lowest validation loss, not the highest validation accuracy train.py. Early stopping compares the current validation loss with the mean of the previous 200 epochs train.py. The paper says only "same as GPRGNN" §6.2.
• Deezer-Europe. The code uses AdamW, 500 epochs and validation-accuracy selection train.py train.py. The paper says Adam with the protocol of another paper §6.2.
• Weight decay. The code applies weight decay to every parameter, including the mixing matrix and channel vectors train.py. The paper does not say.
• Ablation variants. The paper's ablation includes a "no mixing" variant that adds the three channels §6.1. The shipped code has no switch for disabling a channel or the mixing layers.py, so these rows cannot be reproduced from it.
• GCNII variants. ACM-GCNII and ACM-GCNII* are reported §6.2. The model module has no branch for them models.py.
• SGC-2. For two hops the code uses Â_rw² as the low-pass operator but keeps I − Â_rw (one hop) as the high-pass operator utils.py utils.py. The paper states "the corresponding HP filter is I − Â_rw" §6.2 and does not define SGC-2 separately.
• Aggregation homophily. The helper in the synthetic code takes the argmax over class means and ignores its modified argument. It does not apply the paper's same-versus-other comparison or the 2S − 1 rescaling homophily.py eq. 7 eq. 8. Nothing in the repository calls it.
• Fixed-split settings. Per-dataset settings are in a shell script acmgcnp_reproduce_fixed_splits.sh. I did not check them against the appendix table.
• Table and text inconsistencies in the paper. The text names ACMII-GCN+ as best by average rank with 4.40 app. A.1, but the same table gives ACM-GCN++ 4.30. The optimal-hyperparameter table lists ACM-GCN results of 68.18 on Chameleon and 90.54 on PubMed app. C, against 69.04 and 90.66 in the main table. The ablation's full ACM-GCN row also differs from the main table, for example Wisconsin 96.75 against 95.75 and Cora 88.95 against 88.62 tab. 1 app. A.1.

Pitfalls

• Scale factor. The ×3 in the code is not in the paper. If you copy the paper's equation, the effective learning rate and the weight-decay strength will differ from the released results.
• Layer normalisation. The appendix describes it for the ACM+ and ACM++ variants. The released code never applies it, so implementing the appendix literally gives a different model from the one that produced the reported numbers.
• Two-layer fixed. Setting --layers does nothing for ACM-GCN. Do not expect a depth sweep to change anything in the shipped code.
• Splits are not exactly 60%. Training takes a fixed count per class utils.py, capped by the class size. With unequal class sizes the training fraction can fall below 60% (inference from the code, not measured). Compare results only under the same split procedure.
• Model selection. The paper does not state the selection rule. The code reports test accuracy at the minimum-validation-loss epoch, not at the best validation accuracy train.py. The reported standard deviations are 0.3 to 4 points, so a different rule could shift results by a similar amount (inference, not tested).
• Small datasets. Cornell, Wisconsin and Texas have 183 to 251 nodes app. A.1. A difference of one to two points between top models is within one standard deviation.
• Undefined means. H_agg^M takes means over sets that can be empty, for example when a node is the only member of its class. The paper does not say how to handle this eq. 7.
• Cost. The paper reports about twice the per-epoch time of the base layer tab. 1. On Deezer-Europe the appendix lists about 136 ms per epoch for ACM-GCN and about 282 ms for ACM-GCN+ app. C.
• Dropout placement. The paper gives dropout values but not where dropout is applied. The code applies it to the input and after the first layer models.py models.py.
• Not run. I did not run the code. The results above are as reported in the paper.

Lineage

• Builds on: GCN, Kipf and Welling [arXiv:1609.02907] §2.1 eq. 1; SGC, Wu et al. [arXiv:1902.07153] §3.1. Both are the baselines the analysis uses.
• Uses ideas from earlier work: the filterbank view from graph signal processing §4.2, and learned signed weights in GPRGNN (Chien et al., 2021) §5.
• Compared against: MLP-2, GAT, APPNP, GPRGNN, H2GCN, MixHop, GCN+JK, GAT+JK, FAGCN, GraphSAGE, Geom-GCN, BernNet, GCNII, Snowball networks §6.2 app. A.1. Fixed-split comparison adds GGCN, GloGNN and GloGNN++ app. A.2.