Budgeted Neighbor Influence: GNNs That Degrade Gracefully When Homophily Fails at Test Time

A graph neural network (GNN) classifies a node by mixing its own features with those of its neighbors. Doing so is a bet that connected nodes tend to share labels, which is the homophily assumption. Learning-augmented algorithms make bets of the same kind. They follow a machine-learned prediction when it is right and fall back to a safe worst-case strategy when it is wrong, and their best versions guarantee that performance declines smoothly as prediction error grows, with no sudden cliff. This note treats the graph as the "prediction." The neighborhood is advice about a node's label, and a graph-free classifier that sees only the node's own features is the safe fallback. The proposal is to build a GNN whose neighbors can shift its decision by at most a fixed, tunable amount. With that budget in place, three things become provable for any test-time change to the edges: the model can never fall far below the graph-free classifier, its accuracy loss grows at most in proportion to the fraction of corrupted neighbors, and on clean graphs it stays close to an unconstrained GNN.

The motivation is that heterophily (edges linking dissimilar nodes) often appears after training. Fraud accounts rewire toward legitimate users to evade detection, and new regions of a graph have different mixing patterns than the labeled region. The heterophily literature has learned to fit low-homophily graphs at training time. It offers no account of what happens when the homophily a trained model relies on is wrong at test time. The goal here is to measure that failure honestly on leakage-free benchmarks and to bound it.

Core Claim

Platonov et al. showed that ego-neighbor separation beats most specialized heterophily architectures on leakage-free benchmarks A critical look at the evaluation of GNNs under heterophily. Ego-neighbor separation means keeping a node's own representation apart from the aggregate of its neighbors and concatenating the two rather than summing them. Its weights are fit to training-time neighborhoods, though. Nothing stops a corrupted neighborhood at test time from overriding a confident, correct prediction made from the node's own features. Our claim is that one structural change turns this strong heuristic into an algorithm with consistency-robustness guarantees: split the model into a graph-free ego tower and a graph-dependent correction, then clip the correction's magnitude.

Concretely, let $z_{\text{ego}}(v)$ be the class scores from a multi-layer perceptron (MLP) applied to node $v$'s features alone. Let $z_{\text{nbr}}(v)$ be the scores produced by any message-passing network over $v$'s neighborhood. The model predicts

$$z(v) = z_{\text{ego}}(v) + \min\!\Big(1, \tfrac{B}{\lVert z_{\text{nbr}}(v)\rVert_\infty}\Big)\, z_{\text{nbr}}(v),$$

where $B \ge 0$ is the influence budget. Write $m_{\text{ego}}(v)$ for the ego tower's margin, the gap between its top class score and its second-highest. Two facts follow directly.

The first is a robustness floor. No edge modification of any size can change the predicted class of a node with $m_{\text{ego}}(v) > 2B$, because each class score moves by at most $B$, so the gap can close by at most $2B$.

The second is graceful degradation. Suppose the correction is computed by mean aggregation followed by an $L$-Lipschitz map. Corrupting a fraction $\rho$ of $v$'s neighbors then shifts the correction by at most $2L\rho R$, where $R$ bounds neighbor representation norms; this is because the mean moves by at most $\rho$ times the diameter of the representation set. A node can therefore flip only if

$$m(v) \le 2\min(B,\; 2L\rho R),$$

where $m(v)$ is the full model's clean margin. The accuracy lost under corruption level $\rho$ is at most the fraction of correctly classified nodes whose margin lies below this threshold. That fraction can be read off a held-out margin histogram, so it gives a data-dependent, label-free certificate curve.

This is the "price of mispredicted homophily" curve in the spirit of Mitzenmacher's price of misprediction Scheduling with Predictions and the Price of Misprediction. Here it is a measured bound rather than a closed-form queueing constant. The clip is the graph analogue of capacity splitting, in which a bounded share of resources is reserved for the robust policy, as in time-sharing schedules Permutation Predictions for Non-Clairvoyant Scheduling and split knapsack capacity Augmenting Online Algorithms for Knapsack Problem with Total Weight Information. In our version the reserve is margin rather than capacity. For deeper message passing, the multi-hop Lipschitz constant compounds. We will state the one-layer bound as the theorem and treat the multi-layer version empirically, checking the certificate against observed flips.

Relation to Prior Work

Two existing learning-augmented graph papers are the closest neighbors, and both are combinatorial. Fan and Shin give a $(1+O(\alpha^{1/q}))$ approximation for metric $k$-clustering under a predictor with misclassification rate $\alpha$ Learning Augmented Graph k-Clustering. Azar, Panigrahi and Touitou give scale-free bounds for online Steiner and facility problems Online Graph Algorithms with Predictions. Both papers treat the predictor as the advice and the graph as a fixed metric. They rely on the triangle inequality, which heterophilic edges break. We reverse the roles: the graph's edges are the untrusted advice, and the learned feature model is the fallback.

The heterophily literature constrains the design in three ways. First, rigorous re-evaluations find that tuned GCNs and MLPs match most specialized architectures, and they separate "malignant" heterophily, where structure hurts below an MLP, from "benign" heterophily, where it still helps Are Heterophily-Specific GNNs and Homophily Metrics Really Effective?. That rules out proposing yet another filter bank as the contribution. Second, those same papers show that global scalar homophily misdescribes local structure. That rules out any switch keyed to a single homophily number, and it is why our floor is per-node and margin-based. Third, channel-mixing models such as ACM learn per-node softmax weights over low-pass, high-pass and identity channels Is Heterophily A Real Nightmare For Graph Neural Networks on Performing Node Classification?, and sheaf diffusion learns edge-wise transport maps Neural Sheaf Diffusion. In both, the mixing weights are themselves computed from the possibly corrupted neighborhood, so neither bounds how much an adversarial neighborhood can move a prediction. Our budget is fixed and does not depend on what the neighbors look like, and that independence is what makes the floor hold.

Research Program

The work has three parts. The first is the theory. We state and prove the floor and the $\rho$-proportional bound for one-layer mean aggregation with an ego-separated readout. We also show the matching consistency statement: on a clean graph, the clipped model's accuracy differs from the unclipped model's only on nodes whose graph correction exceeds $B$. That fraction is measurable at training time, which gives a validation-based rule for choosing $B$ under a target clean-accuracy loss $\epsilon$ without knowing the test-time error.

The second part is training. If the ego tower is trained only jointly with the graph correction, the correction can take over and leave the ego tower weak, which makes the floor vacuous. We therefore add an auxiliary cross-entropy loss on $z_{\text{ego}}$ alone, so that the ego tower is a real MLP. We study the trade-off this weight controls, together with a margin-encouraging term on the ego tower.

The third part, the main empirical contribution, is a test-time homophily shift protocol for leakage-free benchmarks. Models are trained on the original graph. At test time we corrupt a fraction $\rho \in [0,1]$ of each test node's edges in one of two ways. Random-heterophilic injection rewires edges to random nodes of different labels. Camouflage-style injection rewires them to the nodes the trained GNN scores most confidently as some other class, a worst-case-leaning attacker. We also define a natural shift that requires no synthetic edges: train on nodes with high local homophily and test on nodes with low local homophily.

Baselines

The naive reference points are the graph-free MLP and a plain GCN with ego-neighbor summation. The MLP is immune to edge corruption by construction, so it is the robustness floor we must stay near. The GCN shows the unprotected cliff. Both get the same hyperparameter search budget as our model, because Luan et al. show that under-tuning baselines manufactures fake gains Are Heterophily-Specific GNNs and Homophily Metrics Really Effective?.

The strongest existing competitor is GAT and GraphSAGE-style models with ego-neighbor separation, run with the residual and normalization recipe of Platonov et al. These won 13 of the top 15 spots across roman-empire, amazon-ratings, minesweeper, tolokers and questions A critical look at the evaluation of GNNs under heterophily. For their per-dataset scores, no reported result was found on Lacuna, so we will reproduce them under identical splits and tuning budget before comparing. We also include ACM-GCN, one of the few specialized models that survived Luan et al.'s re-evaluation, to represent learned channel gating. On Cora, the reproduction is sanity-checked against MixHop's reported 81.9% standard-split test accuracy MixHop.

The key ablation is our exact architecture with $B=\infty$ (no clip) and the same auxiliary ego loss. This isolates the budget as the ingredient, since everything else matches the ego-separated competitor. A second ablation is a hard fallback: predict with the ego tower whenever its margin exceeds a threshold, and with the full model otherwise. This tests whether the continuous clip matters at all.

Beating the baselines means the following. At clean-accuracy loss of at most one point relative to the unclipped ego-separated model, our model's accuracy at every corruption level stays within a small tolerance of the MLP or above it. The unclipped models must fall clearly below the MLP at high $\rho$. Our accuracy-versus-$\rho$ curve must also dominate on area. Finally, observed flips must never exceed the margin certificate.

Why not just…?

Why not just train an MLP when heterophily is suspected? The MLP is the floor, not the goal. On benign-heterophily graphs, structure is informative and the MLP leaves accuracy on the table Are Heterophily-Specific GNNs and Homophily Metrics Really Effective?. At $\rho=0$, the clean-graph column of our experiments measures exactly how much the clipped model keeps over the MLP. If that gap is negligible on a dataset, the honest conclusion is that the graph was not worth using there, and we will report it per dataset.

Why not just use ego-neighbor separation, which already lets the model ignore neighbors? This is the most serious threat. Our model is ego-neighbor separation plus a clip and an auxiliary loss. The difference is that separation lets training choose to downweight neighbors given training-time statistics, while nothing bounds the influence of a neighborhood that changes later. The $B=\infty$ ablation settles it. If unclipped separation already stays above the MLP under camouflage injection, the clip adds nothing beyond the certificate, and we will say so. We expect it to fail under targeted rewiring, because the neighbor projection is unbounded in the aggregate.

Why not just train with heterophilic edge-rewiring augmentation? Augmentation protects against the shifts it simulates, and it may well match the clip under random injection. It gives no guarantee against a different shift, such as the camouflage attacker or the natural local-homophily split. We will train an augmented version of the strongest baseline on random injection and evaluate it on all three shifts. If it matches the clip everywhere, the contribution reduces to the certificate, and the note's claim narrows accordingly. Augmentation and the clip also compose, so we will test the combination.

Why not just switch to the MLP below a homophily threshold? Global homophily misjudges local structure Is Heterophily A Real Nightmare For Graph Neural Networks on Performing Node Classification?, and hard switches create cliffs near the threshold Non-Clairvoyant Scheduling with Progress Bars. The hard-fallback ablation measures the variance of accuracy as a function of $\rho$ near the switch point against the clip's curve.

Proposed Experiments

We will run the five leakage-free datasets of Platonov et al. and filtered Chameleon and Squirrel as the heterophilic core. Cora, CiteSeer and PubMed serve as homophilic controls, where consistency should be nearly free. Synthetic graphs with homophily swept from 0.0 to 0.9 give a controlled check that the certificate tracks true degradation. Metrics are accuracy for multi-class tasks and ROC-AUC for the imbalanced binary tasks, averaged over the benchmarks' fixed splits. For each model we report three numbers. Consistency is clean performance relative to the unclipped ego-separated model. Robustness is minimum performance over $\rho$ relative to the MLP. Degradation area is the area under the performance-versus-$\rho$ curve. We also report the gap between certified and observed flips.

Four checks are decisive. First, under camouflage injection at $\rho=1$, the unclipped ego-separated GNN must drop below the MLP while the clipped model stays near it; if the unclipped model does not drop, the problem we target does not exist in practice. Second, the clean-accuracy cost of the $B$ selected on validation must be small on benign datasets, or the trade-off is too expensive. Third, observed flips must stay within the margin bound for one-layer models, with any violation in deeper models quantified rather than hidden. Fourth, on the natural high-to-low local-homophily split, which needs no synthetic attacker, the clipped model must beat both the unclipped model and augmentation-trained baselines. That last result would show the guarantee matters for shifts nobody simulated.