Graph neural networks classify a node by repeatedly averaging the features of its neighbours. That works when linked nodes tend to share a label, which is called homophily. It fails in two well-known ways. When linked nodes usually have different labels (heterophily), averaging blurs away what makes a node distinctive. When many rounds of averaging are stacked, every node drifts toward the same vector, which is called over-smoothing. Two families of fixes exist, and they do not talk to each other. The first family iteratively rewires the graph: it predicts labels, deletes edges between nodes predicted to differ, adds edges between nodes predicted to agree, and retrains. The second family looks several hops away in a single layer, using powers of the adjacency matrix, so that the model can see far without stacking many averaging layers. The rewiring methods only ever edit direct edges and assume that every cross-label edge is noise. The multi-hop methods compute their 2- and 3-hop neighbourhoods on the raw, uncleaned graph, so a noisy edge's damage is multiplied at every power.
We propose to refine each hop's neighbourhood separately, and to use a criterion that keeps cross-label connections when they are predictable. A pair of nodes two hops apart is kept and weighted according to how much its predicted class pair tells you, at that particular hop distance, about labels. The test is not whether the two nodes share a class. Under this criterion a "class A links to class B" pattern that holds reliably is kept and signed. A link whose endpoints' classes look statistically independent is pruned, because it adds smoothing without adding information. In two sentences: build a separate, cleaned neighbour set for hops 1, 2, and 3, and judge each pair by hop-specific label-pair informativeness rather than by agreement. This should keep the useful structure in heterophilic graphs that homophily-enforcing rewiring destroys. It should also slow representation collapse, because the edges it removes are exactly the ones that average without informing.
Core Claim
The refinement methods closest to this proposal treat heterophily as damage. AdaEdge iteratively deletes predicted inter-class edges and inserts predicted intra-class ones. Its authors report that this lifts a GGNN backbone on Amazon Computers from 42.4% to 61.5%. SCA-GNN rewires toward homophily around confident pseudo-labels and adds singular-value stretching. Both methods motivate our proposal, because they show that changing the topology slows over-smoothing. Both also constrain it. On a graph like Squirrel or Texas, their rule deletes the cross-class structure that heterophily-aware models rely on. GGCN shows this structure matters: it puts negative weights on dissimilar existing edges and argues that over-smoothing is "pseudo-heterophily," in which misclassified nodes become misleading neighbours. GREET also shows it, by routing edges it classifies as heterophilic through a high-pass channel in an alternating loop. GGCN and GREET, however, only reweight or relabel existing 1-hop edges. Neither builds cleaned multi-hop neighbourhoods.
On the multi-hop side, MixHop concatenates $\hat{A}^0 H, \hat{A}^1 H, \hat{A}^2 H$. It proves that a plain 1-hop GCN cannot represent the needed difference operator, and it prunes whole hop channels with group lasso. Ordered GNN reserves separate blocks of embedding dimensions for each hop. hpGAT injects precomputed community structure into attention. All three supply the hop-separated aggregation we reuse, and all three keep the graph fixed. MixHop can switch off a hop entirely, but it cannot keep the good 2-hop pairs of a node while dropping the bad ones.
The new element is therefore pair-level, hop-specific refinement under a compatibility criterion rather than an agreement criterion. We will test whether this beats two cheaper options: refining the 1-hop graph first and then taking powers, and learning hop weights on the static graph.
Research Program
For each hop $k \in \{1,2,3\}$ we maintain a sparse candidate set $\mathcal{C}_k$ of node pairs. These are the pairs reachable by a $k$-step walk, capped at $m$ per node by random-walk sampling. The cap avoids the densification of explicit $A^k$ and keeps the cost near linear in edges, as MixHop's right-to-left multiplication does.
From the current model's soft predictions $p_u$, we estimate a hop-specific class co-occurrence matrix $\hat{P}_k(a,b)$, with marginals $\hat{P}(a)$, $\hat{P}(b)$. Labeled training nodes are weighted fully and unlabeled nodes by their confidence. Each candidate pair gets a score
$$s_k(u,v) = \sum_{a,b} p_u(a)\, p_v(b)\, \log \frac{\hat{P}_k(a,b)}{\hat{P}(a)\hat{P}(b)},$$
which is the expected pointwise mutual information of the pair's class labels at hop $k$. The score is large and positive for homophilic pairs in assortative graphs. It is also large and positive for structured cross-class pairs, such as A-to-B pairs where B neighbours reliably follow A. It is near zero when the two endpoints' classes look independent. The refined hop-$k$ operator keeps pairs with $s_k$ above a threshold. The threshold is chosen per hop as a quantile, tuned on validation data, rather than as a fixed confidence cutoff. Each kept pair is weighted by $s_k$, and its message is signed by whether the dominant class pair is same-class or cross-class. This borrows GGCN's signed messages, but takes the sign from estimated compatibility instead of feature cosine similarity.
The backbone is a MixHop-style layer, so the comparison isolates the refinement. Each hop has its own channel and weight matrix, and the network is shallow, two layers, so the receptive field grows sideways rather than through depth.
To limit confirmation bias, the main open problem of iterative refinement, we take three precautions. Weights are soft and only re-estimated every few epochs. Pairs touching labeled training nodes are scored with true labels only. Edits are staged over successive rounds with retraining in between, following the batched purification argument of Jin et al., who show that removing noisy edges in successive batches avoids the bias of one-shot detection.
We will also run an oracle variant that computes $\hat{P}_k$ and $s_k$ from true labels on all nodes. This gives an upper bound and tells us how much of any shortfall is pseudo-label error rather than a flaw in the criterion.
Over-smoothing is measured two ways. The first is Effective Rank of the final embeddings, which Zhang et al. show tracks accuracy with average Pearson correlation 0.91, whereas Dirichlet energy can stay high while accuracy collapses. Because those authors also warn that high rank is not sufficient (noise has full rank), we pair it with MADGap from Chen et al., the gap between inter-class and intra-class embedding distance, which they report correlates above 0.9 with accuracy. A method that raises rank without raising MADGap is amplifying noise, and we will count that against it.
Baselines
The naive reference point is a two-layer GCN and the static MixHop layer with hops $\{0,1,2,3\}$, run with no refinement. MixHop is the direct parent architecture: if our method does not beat it, refinement adds nothing. On the standard splits MixHop reports 81.9% on Cora, 71.4% on CiteSeer and 80.8% on PubMed (MixHop). We will rerun it under our splits rather than copy these numbers.
The strongest homophily-enforcing refinement baselines are AdaEdge and SCA-GNN. AdaEdge is the canonical predict-prune-add-retrain loop. SCA-GNN is its strongest descendant in the file and reports 83.53% on Cora versus 80.65% for its base model, and 73.16% on ogbn-arxiv (SCA-GNN). We will run both on the same MixHop backbone as well as their native backbones, so that the difference is the refinement rule and not the architecture.
The strongest heterophily-aware competitors are Ordered GNN and GGCN. Ordered GNN reports 62.44% on Squirrel against roughly 55% for the prior best, and 89.10% on Cora at 64 layers (Ordered GNN). GGCN reports the best average rank, 1.78, across nine datasets (GGCN). Geom-GCN's 67.57% on Texas (Geom-GCN) is a reference for the small WebKB graphs. The file reports no Lacuna result for GREET in supervised node classification accuracy. We will include GREET's edge discriminator as a refinement rule plugged into our backbone.
Fairness rules apply to all methods. Every method uses the same splits and ten seeds. Every method gets the same hyperparameter search budget: the same number of trials, and the same training-time cap measured in GPU-hours. Refinement baselines get the same number of refinement rounds as ours.
Beating the field means two things. On heterophilic graphs, we must be statistically better than the best of Ordered GNN and GGCN, with paired tests across seeds. On homophilic graphs, we must not be worse than SCA-GNN.
Two ablations isolate the key ingredient. The first, "agreement criterion," replaces $s_k$ with AdaEdge's same-predicted-label rule while keeping per-hop refinement. The second, "refine-then-power," refines only hop 1 with our criterion and then forms its powers.
Why not just…?
Why not just learn hop weights on the static graph, as MixHop's group lasso already does? This is the most serious threat. Down-weighting a whole noisy hop may capture most of the benefit. The difference is granularity. Hop weights treat all of a node's 2-hop pairs alike, while our score keeps informative pairs and drops uninformative ones within the same hop. We will settle this directly. If static MixHop with tuned hop weights matches us on Squirrel, Chameleon, arXiv-year and Amazon Ratings, the pair-level claim is false. We would report that result rather than reframe the method.
Why not just refine the 1-hop graph and then take powers of the cleaned matrix? This is cheaper and composes existing tools. But powers of a cleaned 1-hop graph inherit its criterion. A 1-hop edge that is uninformative locally may lie on 2-hop paths that are highly informative, which is the A→B→A alternation MixHop exploits. Deleting it at hop 1 deletes those paths too. The refine-then-power ablation measures this. On synthetic graphs with alternating class structure, we expect it to lose; on homophilic citation graphs, we expect it to tie.
Why not just use signed edges as GGCN does, with no refinement loop? GGCN signs only existing edges and judges them by feature similarity. That is unreliable exactly when features of different classes look alike, and GGCN cannot add multi-hop pairs at all. If GGCN matches us, then the multi-hop refinement is unnecessary. The comparison is included for that reason.
Proposed Experiments
The decisive first experiment is synthetic. We generate graphs with controllable homophily from 0.0 to 0.9, following MixHop's synthetic setting. The design crosses two factors. The first is the share of cross-class edges that follow a fixed class-compatibility pattern versus the share that are random. The second is the amount of injected random edge noise.
The prediction is specific. AdaEdge and SCA-GNN should degrade as the structured cross-class share grows, because they delete it. Our method should track the oracle variant. Effective Rank and MADGap should stay higher than under static MixHop as noise increases. If the agreement-criterion ablation performs as well as our method on structured heterophily, the core claim fails.
On real data, we emphasise the larger heterophilic graphs, Squirrel, Chameleon, Actor, arXiv-year and Amazon Ratings, because the file notes high split variance on Texas, Cornell and Wisconsin with about 200 nodes. We report those small graphs only with confidence intervals. Cora, CiteSeer, PubMed and ogbn-arxiv test whether the method does no harm under homophily, where low-pass averaging is close to optimal. ogbn-arxiv also tests whether the candidate cap keeps cost close to MixHop's.
A depth study with 2 to 32 layers on Cora and Squirrel, tracking accuracy, Effective Rank and MADGap, checks whether refined hop operators slow collapse when depth is forced. A robustness study perturbs edges at increasing rates on Cora and Chameleon. It tests the motivating claim that errors in raw $A$ compound in $A^k$ while per-hop refinement contains them.
Finally, a diagnostic tracks, across refinement rounds, the fraction of pruned pairs whose true class pair has near-zero mutual information. This shows directly whether the loop removes uninformative pairs or drifts with its own pseudo-labels.
References
- Measuring and Relieving the Over-Smoothing Problem for Graph Neural Networks from the Topological View
- Mitigating Over-Smoothing in Graph Neural Networks via Separation Coefficient-Guided Adaptive Graph Structure Adjustment
- Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks
- Beyond Smoothing: Unsupervised Graph Representation Learning with Edge Heterophily Discriminating
- MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing
- Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing
- hpGAT: High-Order Proximity Informed Graph Attention Network
- Rethinking Contrastive Learning in Graph Anomaly Detection: A Clean-View Perspective
- Are we measuring oversmoothing in graph neural networks correctly?
- Geom-GCN: Geometric Graph Convolutional Networks