Is Heterophily a Logic Problem? Separating Neighbor Similarity from Target Complexity in Deep GNNs

Graph neural networks (GNNs), which update each node by combining its own features with a summary of its neighbors' features, are known to fail in two ways. They fail on heterophilous graphs, where linked nodes usually belong to different classes. They also fail when stacked deeply, because repeated neighbor-averaging makes all node representations look alike. This second failure is called over-smoothing. Recent work treats the two failures as one phenomenon. Its explanation is that averaging across dissimilar neighbors pushes nodes over decision boundaries, and deep averaging creates that dissimilarity on its own. A separate line of theory describes exactly which node properties a GNN can compute by matching it to a logic. In that logic, a statement like "at least 3 of my neighbors satisfy φ" corresponds to one round of sum aggregation.

This note proposes that "homophily" is mostly a stand-in for something logic can measure directly: the form of the rule that defines the label. That form includes how deeply the rule nests statements about neighbors, whether it negates a property inside a neighbor statement, and whether it mixes "some neighbor" with "all neighbors." We would build graphs in which the labeling rule is held exactly fixed while edge homophily is swept from low to high. We would also build a layer-wise probe that measures which logical properties a network's representations still encode. With these two tools we can test whether depth and heterophily failures are predicted by the logical form of the target rather than by homophily or by representation rank.

Core Claim

The claim has two parts. First, when the labeling rule is held fixed, GNN accuracy should depend weakly on edge homophily. When homophily is held fixed, accuracy should depend strongly on the rule's logical form. The form is measured by modal depth (how many neighbor-hops the rule nests), by negation under a neighbor statement, and by alternation between "some" and "all." Second, over-smoothing should be measured by formula decodability: the fraction of logical properties, up to a given depth, that remain linearly recoverable from a layer's representations. Effective rank should not be the measure. Rank-based diagnostics are known to be necessary but not sufficient, since random noise has full rank. Formula decodability should therefore catch collapses that rank misses, and it should explain which architectural fixes help on which targets.

Background and Position

The logical side supplies the method. The Logical Expressiveness of Graph Neural Networks showed that local aggregate-combine GNNs capture exactly graded modal logic, meaning formulas built from node propositions, Boolean connectives, and counting statements about neighbors. It also showed that adding a global readout lifts these GNNs to two-variable first-order logic with counting. Graded modal logic and counting message passing automata tightened this correspondence with automata. Logical Characterizations of GNNs with Mean Aggregation showed two further results. Mean aggregation captures ratio statements ("at least 30% of neighbors satisfy φ"). Practical continuous mean-GNNs drop to an alternation-free fragment that cannot freely nest "some" inside "all." All of this work assumes depth only adds expressiveness, and none of it tests heterophilous targets. We reuse its formula languages as a measurement instrument. We do not try to prove new expressiveness theorems.

The homophily and over-smoothing side motivates the question. Two Sides of the Same Coin explains node failures through node-level homophily and relative degree. It then proposes GGCN, which uses signed, degree-corrected messages. Complete the Missing Half adds a high-pass "diversification" channel next to standard averaging. Both papers frame the problem in terms of neighbor similarity and spectral filtering. Neither asks what rule the labels follow, and both report results on WebKB and Wikipedia graphs. A critical look at the evaluation of GNNs under heterophily found that over half the nodes in those Wikipedia graphs are duplicates that leak test labels. It also found that plain GNNs with ego-neighbor separation, which keep a node's own features in a channel separate from the neighbor summary, take 13 of the top 15 spots on a cleaned suite. This result constrains us: any explanation must account for why such a simple change works so well. The rank papers, Are we measuring oversmoothing in graph neural networks correctly? and Rethinking Oversmoothing in Graph Neural Networks: A Rank-Based Perspective, replaced Dirichlet energy (a measure of how much features differ across edges) with effective rank. They report an average Pearson correlation of 0.9103 between effective rank and accuracy, against −0.7179 for Dirichlet energy. They also state openly that high rank does not guarantee useful content. Our probe is designed to fill that gap.

None of these papers holds the target function fixed while varying homophily. That is the experiment that separates the two explanations. It is also what separates this proposal from the closest prior work, GGCN's unified homophily and over-smoothing analysis.

Research Program

Homophily sweeps with a fixed target. We sample graphs from stochastic block models and grids, and assign binary node propositions $p_1,\dots,p_m$. The label of node $v$ is the truth value of a chosen formula φ at $v$. We then run degree-preserving double-edge swaps. A swap is accepted only if every node's truth value for φ is unchanged, which we verify exactly after each proposal. Swaps are biased toward raising or lowering edge homophily. The result is a family of graphs that share one exact labeling rule and one degree sequence but span a wide homophily range. The formula bank is stratified by modal depth (1 to 4), by negation under a neighbor statement (for example "some neighbor does not satisfy $p$" versus "some neighbor satisfies $p$"), by alternation (for example "some neighbor has all neighbors satisfying $p$"), and by quantifier type (count thresholds versus ratio thresholds). A separate set of first-order formulas with global reach tests readout.

Formula-decodability probe. For a network trained on a given task, we freeze the layer-$\ell$ representations $H^{(\ell)}$. For every formula ψ in a bank $\Psi_d$ of formulas up to depth $d$, we evaluate the truth of ψ exactly on the graph's propositions. We then fit a linear probe on held-out nodes. The score is

$$D_d(H^{(\ell)}) = \frac{1}{|\Psi_d|}\sum_{\psi \in \Psi_d} \mathrm{BalAcc}\big(\text{probe}_\psi(H^{(\ell)}),\ \psi\big),$$

where BalAcc is balanced accuracy, so that rare formulas count fully. On synthetic graphs the propositions are the planted ones. On real graphs they are binarized input features, using the top principal components thresholded at the median. Where available we also use features with direct meaning, such as the mine-count features in minesweeper. Truth values computed from binarized inputs are a coarse proxy on real data, and we report them as such. We also compute $D_d$ on randomly initialized networks. This control separates what training preserves from what the architecture keeps by default.

Analysis. We fit accuracy as a function of homophily, formula class, and their interaction across the sweeps. Across depths 2 to 64, we compare $D_d$, effective rank, numerical rank, and Dirichlet energy as predictors of accuracy, using partial correlations that control for each other.

Baselines

The naive reference point is a graph-agnostic MLP (and a ResNet), trained on the same splits with the same hyperparameter budget. It cannot express any neighbor statement, so on synthetic tasks it should succeed only on depth-0 formulas. Any graph model that fails to beat it on a depth-≥1 rule is not using the graph. On the cleaned real benchmarks, this baseline was competitive with many specialized heterophily models in A critical look at the evaluation of GNNs under heterophily.

The strongest architectural competitor is a standard GNN with ego-neighbor separation, run as a GAT and a GraphSAGE-style model, following A critical look at the evaluation of GNNs under heterophily. It dominated the cleaned suite. We found no reported per-dataset accuracy for roman-empire, amazon-ratings, minesweeper, tolokers, or questions on Lacuna. We will therefore rerun it ourselves under the authors' splits and report it next to our numbers. We will not quote a figure we do not have. GGCN from Two Sides of the Same Coin and the filterbank GCN from Complete the Missing Half are the heterophily-and-depth specialists. They are the right competitors for the depth sweeps, since GGCN is reported stable to 64 layers and has the best average rank of 1.78 across its nine datasets. ACR-GNN from The Logical Expressiveness of Graph Neural Networks is the reference for global formulas, where it reaches 100% accuracy with transfer from small to larger graphs. All models share the same data, equal tuning trials per model, the same depth grid, and three to five seeds. The central ablation turns ego-neighbor separation on and off in an otherwise identical mean-aggregation GNN. This ablation isolates whether separation specifically helps formulas with negation or alternation, as the alternation-free limit of Logical Characterizations of GNNs with Mean Aggregation would suggest.

For the diagnostic itself, the baselines are effective rank and numerical rank from Rethinking Oversmoothing, with the reported 0.9103 correlation, and Dirichlet energy, with the reported −0.7179. We also include edge homophily, plus a plain layer-wise probe for the task label. Formula decodability counts as beating the rank measures only if it adds significant partial correlation with accuracy after controlling for effective rank. It must also correctly flag configurations where effective rank stays high but accuracy falls.

Why not just…?

Why not just use effective rank, which already correlates at 0.91 with accuracy? This is a real threat. If rank already explains nearly all the variance in accuracy, a richer probe may add little on the benchmarks where rank was tested. The rank papers themselves concede that rank is insufficient, because noise is full-rank, and that is the regime where we expect the probe to matter. We will create such cases deliberately: depth sweeps with noise injection, and signed-message models like GGCN that can keep variance high while scrambling content. If $D_d$ adds no partial correlation beyond effective rank on both synthetic and real data, we will report that the diagnostic contribution fails. The fixed-target sweeps would still stand as a separate result.

Why not just measure homophily better, for example with label informativeness? Better homophily metrics still describe the relation between edges and labels. They do not describe the rule generating the labels. The fixed-formula sweeps answer this directly. If accuracy tracks homophily even when the rule and degree sequence are identical, our claim is wrong and homophily metrics are the right tool. We will include such metrics as regressors wherever we can compute them.

Why not just probe for the task label at each layer? A label probe says whether information is lost, but not what kind. It cannot tell us that ego separation recovers negated neighbor statements while leaving deep alternation lost. On real graphs, a label probe may predict final accuracy about as well as $D_d$. If so, we will say that the formula bank's value is explanatory rather than predictive, and we will rest the claim on the stratified synthetic results.

Why not just add ego separation and stop? That may be the right engineering answer. Our goal is to explain why it works and where it stops working. The ablation predicts that its gains concentrate on formulas with negation under a neighbor statement. It also predicts no gain on deep alternating formulas or global formulas, where readout is needed. If the gains turn out uniform across formula classes, the logical explanation is wrong.

Proposed Experiments and Decisive Checks

The synthetic program uses stochastic block model, Erdős–Rényi, and grid graphs, with formula-labeled nodes as in the logic papers. Graphs are trained at 50–100 nodes and tested at 100–200 nodes, matching the protocol of The Logical Expressiveness of Graph Neural Networks. Each formula is swept over at least five homophily bins. The real-data program uses the cleaned suite of roman-empire, amazon-ratings, minesweeper, tolokers, and questions as the primary evaluation, with Cora, PubMed, and OGB-Arxiv for homophilic depth behavior. Results on Squirrel and Chameleon are reported only in filtered form, given the leakage finding.

Three outcomes would decide the question. First, in the fixed-target sweeps, the variance in accuracy explained by formula class should exceed the variance explained by homophily by a wide margin. If homophily dominates, the reframing fails. Second, across depths, $D_d$ should fall before accuracy does, and should do so in cases where effective rank stays near its maximum. If $D_d$ and effective rank always move together, the probe is redundant. Third, the ego-separation ablation should show gains concentrated on negated neighbor statements. Neither ego separation nor signed messages should rescue depth-3 alternating formulas under mean aggregation. If a continuous ego-separated mean-GNN does learn alternating formulas reliably, that is a direct empirical counterexample to the expected alternation-free ceiling, and it would be worth reporting on its own.