Keeping Neighbor Differences Alive: Deep Message Passing in the Edge Space of a Simplicial Complex

Graph neural networks classify nodes by repeatedly averaging each node's features with those of its neighbors. That averaging is the root of two well-known failures. When linked nodes tend to have different labels (heterophily), averaging blurs away exactly the differences that matter. When many layers are stacked, averaging drives all nodes toward the same vector (over-smoothing). Our proposal is to stop storing the useful signal on nodes at all. Instead we store it on edges, as oriented differences between endpoints, and run the deep part of the network only with triangle-based diffusion. A basic identity of algebraic topology guarantees that this kind of diffusion cannot touch the "difference between neighbors" component of an edge signal, however many layers are stacked. Node predictions are read out from the edges once, at the end.

In two sentences: heterophily information is, almost by definition, the pattern of how features differ across edges, and an elementary fact about the Hodge decomposition says that diffusing edge signals through triangles leaves that difference pattern exactly invariant. So a network that propagates in edge space with only the "upper" (triangle) operator can go deep without washing out heterophilous structure. The empirical question is whether the triangle-level smoothing it performs adds anything beyond a simple high-pass filter.

Core Claim

Take a graph and lift it to its clique complex, so that nodes, edges and filled triangles become 0-, 1- and 2-dimensional pieces. Let $B_1$ be the node-to-edge incidence matrix, of size nodes × edges with entries ±1, and $B_2$ the edge-to-triangle incidence matrix. The edge-space Hodge Laplacian splits as $L_1 = B_1^\top B_1 + B_2 B_2^\top$. The first term is the "lower" part, where edges talk through shared nodes, and the second is the "upper" part, where edges talk through shared triangles. Any node feature matrix $X$ induces an edge signal $B_1^\top X$, the oriented difference $x_u - x_v$ on every edge. This gradient signal is the heterophily signal. Because $B_1 B_2 = 0$,

$$B_2 B_2^\top (B_1^\top X) = 0,$$

so repeated upper diffusion $E_{k+1} = (I - \alpha B_2 B_2^\top) E_k$ leaves the gradient component of $E_k$ exactly unchanged at every depth $k$. It only smooths the curl component, which measures inconsistency around triangles.

The lower term, by contrast, satisfies $B_1^\top B_1 B_1^\top = B_1^\top L_0$, where $L_0$ is the ordinary graph Laplacian. The lower channel is therefore ordinary node diffusion in disguise, and it is the channel responsible for over-smoothing. The claim is that a node classifier built as "lift once, diffuse deeply in edge space with learned upper-only operators, read out once" has a depth-invariant floor on the node-difference information it retains. It should therefore degrade gracefully with depth on heterophilous graphs, precisely where node-space diffusion degrades fastest.

This sits in a specific place relative to prior work. Hodge-Aware Convolutional Learning on Simplicial Complexes (SCCNN) supplies the method. It uncouples lower and upper Laplacians with separate weights and uses Dirichlet energy to show that deep simplicial signals do not collapse into the harmonic subspace. However, it keeps both channels active, targets edge-flow and coauthorship tasks, and never evaluates node classification under heterophily. We deliberately remove the lower channel from the deep stack and aim the construction at heterophily.

How Smoothing is N-simplicial Attention? constrains the design. It proves that simplicial attention still collapses exponentially to rank 1, so being higher-order does not by itself protect against smoothing. Our guarantee comes from an operator identity rather than from receptive-field size, which is why we avoid attention in the deep stack.

Neural Sheaf Diffusion and Polynomial Neural Sheaf Diffusion motivate the proposal. Both argue that heterophily and over-smoothing come from a trivial, scalar diffusion geometry, and both fix it by learning restriction maps on the 1-dimensional graph skeleton. We change a different ingredient. We keep the geometry simple but move the signal into the space where the diffusion operator provably ignores it. The two ideas compose, and we test them as competitors rather than claiming priority over sheaves on complexes, which the research file lists as an open gap.

Research Program

The architecture has three stages. First, a lift: each edge $(u,v)$ gets an antisymmetric feature $\phi(x_u) - \phi(x_v)$, which is a proper 1-cochain, plus a symmetric feature $\psi(x_u, x_v)$ carried as an orientation-invariant channel. Second, a deep stack of $K$ layers. Each layer applies a learned polynomial in $B_2 B_2^\top$, an edge-wise weight matrix, and a residual connection, with pointwise nonlinearities applied only to the symmetric channel and to magnitudes, so that the antisymmetric channel stays orientation-equivariant. Third, a readout: each node aggregates its incident edges once, using signed incidence for the antisymmetric channel and unsigned incidence for the symmetric one, and then concatenates its own lifted feature.

Nonlinearities break the exact invariance. The first analysis task is therefore to bound how much gradient energy a layer can move. We will measure this empirically as the fraction of $\|P_{\text{grad}} E_k\|$ retained versus $k$, where $P_{\text{grad}}$ is the projection onto the image of $B_1^\top$.

Sparse heterophilous graphs such as Texas have few triangles. On such graphs $B_2 B_2^\top$ is nearly zero and the model degenerates into an edge-difference model with no diffusion. We treat this as a prediction, not a flaw. The model should help only where triangles or higher cells exist, so we also build a variant that attaches 2-cells to short induced cycles, following Weisfeiler and Lehman Go Cellular: CW Networks. The identity $B_1 B_2 = 0$ still holds there. We will also define triangle-level homophily, the label composition of each 2-cell, and test whether it predicts where upper diffusion helps better than edge homophily does.

Following Oversmoothing, "Oversquashing", Heterophily, Long-Range, and more, which shows that Dirichlet energy and Rayleigh quotient give contradictory smoothing diagnoses and that separable representations can have near-zero energy, we will not report Dirichlet energy alone. For every depth we report three things: node Dirichlet energy of the readout, the effective rank of node representations, and the accuracy of a linear probe trained on frozen representations. Following Backward Oversmoothing, we also log gradient norms so that optimization failure is not mistaken for smoothing.

Baselines

The naive reference points are a feature-only MLP and a standard GCN. On Texas, Geom-GCN reports accuracy of 52.16% for GCN, 58.38% for GAT and 67.57% for Geom-GCN-P. On Citeseer it reports 73.68% for GCN and 77.99% for Geom-GCN-I. We will rerun GCN and MLP ourselves on identical splits, and use the published figures only as a check that our runs are sane.

The strongest pairwise competitors are GGCN from Two Sides of the Same Coin and O(d)-NSD from Neural Sheaf Diffusion. GGCN uses signed cosine-similarity messages with degree correction and is reported stable to 64 layers with average rank 1.78 across nine datasets. The file gives only relative margins for it, 6% on Chameleon and 3% on Cornell, and no absolute per-dataset accuracies were found on Lacuna. O(d)-NSD learns orthogonal restriction maps on the graph. It is reported first on 5 of 6 heterophilic benchmarks with a +7% margin on Squirrel, but no reported per-dataset accuracy was found on Lacuna for Texas, Wisconsin or Chameleon. PolyNSD is included as the deep sheaf variant, reported stable to 32 layers; no reported numbers were found on Lacuna.

On Minesweeper, the strongest figure in the file is GCN with MixMP at 74.5% accuracy, against 52.3% for the base GCN, from Heterophily-informed Message Passing. We include MixMP-GCN as the similarity-gating baseline.

The higher-order baselines are SCCNN, adapted to node classification with our readout and with both lower and upper channels active, and CWN.

Fairness rules apply to every method. All models get the same splits, the same feature preprocessing, the same number of random-search trials over a shared grid of hidden size, learning rate, dropout and weight decay, and the same depth sweep of 2, 4, 8, 16, 32 and 64 layers. Accuracy is reported as mean ± standard deviation over the standard ten splits.

Three ablations isolate the key ingredient. The first is the same model with the lower Laplacian added back into the deep stack; this should reintroduce depth degradation. The second removes the deep stack entirely, leaving lift plus readout; this is a pure edge-difference model. The third replaces clique-complex triangles with randomly placed triangles of equal count.

Beating the field means two things. At the best depth, the model must match or exceed the stronger of GGCN and O(d)-NSD on triangle-rich heterophilous graphs. And its linear-probe accuracy must be flat, within one standard deviation, from 4 to 64 layers while node-space baselines decline.

Why not just…?

Why not just add a high-pass channel to a GCN? This is the real threat. Complete the Missing Half gains roughly 10% on Texas and Cornell by adding an $I - A$ diversification channel. That channel is essentially the gradient signal $B_1^\top X$ reaggregated in one step. Our second ablation, lift plus readout with no deep stack, is almost exactly this baseline. If the full model does not beat it, the upper diffusion contributes nothing and the paper's conclusion becomes "high-pass is enough." We expect a tie on triangle-poor WebKB graphs and a gap only where curl content correlates with labels. The synthetic suite below is designed to separate these two cases cleanly.

Why not just use signed messages (GGCN) or similarity gating (MixMP)? Both keep the signal on nodes and repeatedly apply node diffusion, with signs or gates acting as corrections. Their depth stability comes from decaying aggregation or gating, not from an invariance. Our depth sweep with linear probes, compared against theirs under the same budget, tests whether the invariance matters in practice. If GGCN is equally flat at 64 layers, our advantage must come from accuracy on triangle-rich graphs or from nothing.

Why not just use SCCNN as is? SCCNN already separates the channels but keeps the lower one, which by the identity above is node diffusion. The first ablation is precisely "SCCNN-style with lower channel," so the comparison directly measures whether dropping it is what protects heterophilous information.

Why not just run sheaf diffusion on the graph? NSD addresses heterophily with learned geometry at the cost of an $Nd \times Nd$ operator. Ours needs no learned restriction maps. If O(d)-NSD wins everywhere, the conclusion is that learned transport matters more than signal placement. We will then test whether adding upper-only edge diffusion on top of NSD features still helps.

Proposed Experiments

The first step decides where the method can matter at all. For Texas, Wisconsin, Cornell, Squirrel, Chameleon, Minesweeper, Cora and Citeseer, we compute triangle counts, induced-cycle counts, edge homophily and triangle-level homophily. We also verify numerically that $\|P_{\text{grad}}E_k\|$ stays constant under linear upper diffusion.

Next comes a synthetic suite in the spirit of the one in Sheaf Hypergraph Networks. It varies edge homophily and triangle label patterns independently. In one family, labels are fully determined by node differences, where high-pass should suffice. In another, labels depend on the composition of the triangles a node belongs to, where upper diffusion should be necessary. The decisive predictions are these. The full model beats the no-diffusion ablation only in the second family. Adding the lower channel causes linear-probe accuracy to fall with depth on heterophilous settings but not on homophilous ones. Randomly rewired triangles erase the gain.

On real benchmarks we run the full depth sweep against all baselines, reporting accuracy, effective rank, Dirichlet energy and probe accuracy. For a native higher-order check, we use the Semantic Scholar coauthorship task, where SCCNN reports triadic AUC 98.7% and tetradic AUC 99.4%. We verify that dropping the lower channel does not cost accuracy there.

The proposal fails cleanly if the no-diffusion edge model matches the full model everywhere, or if the gradient-retention measure decays sharply once nonlinearities are added.