Noise to One, Signal to Another: Under Strong Heterophily, a Separate Self-Path Decides Whether Edges Help a GNN

When edges are removed from a graph, do graph neural networks lose performance because they lose information, or because they lose specific structural signals? We study this with a controlled edge-removal probe. We sparsify graphs from 0% to 95% under three strategies: random removal, removal of cross-label (heterophilic) edges first, and removal of same-label (homophilic) edges first. The two label-aware strategies use ground-truth labels and serve only as a diagnostic. We train five two-layer GNNs and a graph-free MLP on four benchmarks (Cora, Roman-empire with all 10 splits, Amazon-ratings and Tolokers), across 11,739 training runs. Four of the GNNs form a 2 × 2 design: mean vs attention aggregation, with vs without a separate self-path (GCN, GraphSAGE, GAT, GAT-sep). The fifth, GCN-res, adds a residual self-path to GCN at GraphSAGE's parameter count. On the strongly heterophilous Roman-empire graph, the same edges are noise to one architecture and signal to another. Removing 95% of edges at random raises GCN's accuracy by 16.4 points and GAT's by 13.1, but lowers GraphSAGE's by 9.9, GAT-sep's by 10.3 and GCN-res's by 9.9. Every model keeps this sign in all 10 splits. The decisive factor is the separate self-path, not attention. On the two medium-homophily graphs, random removal hurts every model, so edges act as noise only when heterophily is strong and the self-path is missing. Under label-aware removal, the accuracy peak sits at a sparsity of about 1 − h, where h is the graph's edge homophily. The height of that peak includes label leakage and is not a usable gain. We report one pre-registered prediction that failed in part.