Odd Cycles Decide When Two-Hop Aggregation Rescues Heterophilous Graphs

Graph neural networks classify nodes by averaging information from their neighbors. That works when linked nodes tend to share a label, which is called homophily. It fails on heterophilous graphs, where links mostly join nodes of different labels. The best-known remedy is to also aggregate over nodes two hops away. The textbook justification is a bipartite graph, one whose nodes split into two sides with every edge crossing between them. There, every one-hop neighbor is on the other side and every two-hop neighbor is back on your own. Real heterophilous graphs are not bipartite. They contain triangles, pentagons and other odd cycles, and an odd cycle means a node can reach the same vertex by both an even-length and an odd-length path. For such a pair, "two hops away means same class" no longer holds.

This note proposes measuring, for every node and without using labels, how bipartite its neighborhood is. The measurement uses counts of short odd closed walks. We test whether this one quantity predicts where two-hop and high-pass aggregation helps and where it hurts. We then use it as a fixed structural input to the gate that picks an aggregation channel for each node. The bet is that a classical graph-theory notion, distance to bipartiteness, explains failures that label-based homophily metrics cannot. The payoff should be largest on low-degree nodes, where learned gates have too little data to estimate the right choice.

Core Claim

Two-hop recovery of class signal is controlled jointly by edge homophily and by local parity consistency. Parity consistency is the share of a node's short closed walks that have even length. In a bipartite neighborhood it equals 1, and it falls as odd cycles pass through the node. At fixed homophily and degree, nodes with low parity consistency should gain little or lose accuracy from two-hop channels. A gate that sees this score should beat a gate that must infer it from features alone, and the advantage should concentrate on low-degree nodes.

The claim is exact only when the label structure is itself bipartite-like. That means two classes, or K classes whose connection pattern pairs them up, so that taking the class-to-class compatibility matrix twice gives roughly the identity. In other multi-class settings an odd cycle can be perfectly consistent with heterophily: a triangle can join three different classes. We therefore treat this as a scoped hypothesis. For each dataset we estimate from training labels how close its compatibility matrix is to an involution, and we predict that the parity effect is strong when it is close and weak when it is not.

Relation to Prior Work

Two papers motivate the question. Beyond Homophily in Graph Neural Networks introduced H2GCN. Its design D2 aggregates exact two-hop neighbors separately from one-hop neighbors, and it uses the bipartite case as justification. Revisiting Heterophily For Graph Neural Networks proves that bipartite heterophily is harmless after one aggregation. It also introduced ACM, which gates three channels for each node: low-pass (averaging), high-pass (differences from neighbors) and identity (the node's own features).

Neither paper says what happens between bipartite graphs and arbitrary ones. H2GCN's exclusion of one-hop neighbors from the two-hop set removes the triangle case. It does not remove pentagons or longer odd cycles, where a two-hop neighbor is also reachable by a three-hop path.

The metric literature constrains the design. Characterizing Graph Datasets for Node Classification shows that classic homophily ratios are biased. It proposes adjusted homophily and label informativeness, and it reports a Spearman correlation with GraphSAGE accuracy on synthetic stochastic block models of 0.93 for label informativeness against 0.05 for adjusted homophily. Our score must beat that bar as a predictor, not just correlate. All of those metrics also need labels, while ours does not.

Beyond Fixed Depth derives a per-node stopping rule (AD-GNN) under a two-class contextual stochastic block model, a random-graph model with Gaussian features. Such random graphs contain odd cycles at a rate set only by edge density, so the model cannot separate cycle structure from homophily. Our synthetic generator is built to do exactly that separation.

The technique comes from Measure-theoretic bounds on the spectral radius of graphs from walks. That paper treats each node's closed-walk counts as moments of a local spectral measure. The odd moments of this measure vanish exactly when no odd closed walk of that length passes through the node. This gives a principled, cheap, label-free local bipartiteness score.

Research Program

The first component is the score itself. For node $v$ and maximum walk length $L$ (we use $L=5$), let $m_k(v)$ be the $v$-th diagonal entry of the $k$-th power of the degree-normalized adjacency matrix. Parity consistency is then

$$\pi_v = \frac{\sum_{k \le L,\ k\ \text{even}} m_k(v)}{\sum_{k \le L} m_k(v)},$$

which equals 1 on a bipartite neighborhood and decreases as odd closed walks through $v$ accumulate. The diagonal entries are estimated with random probe vectors, which costs a few sparse matrix-vector products per probe. No dense two-hop matrix is ever formed. We also compute a graph-level counterpart, a greedy approximation of the frustration index (the fewest edge deletions that make the graph bipartite), for dataset-level analysis.

The second component is analysis. In the two-class setting with symmetric heterophily $h$, we derive the expected signal-to-noise of the exact-two-hop aggregate as a function of $h$, degree, and the fraction of two-hop neighbors that are parity-ambiguous. A parity-ambiguous neighbor is one also reachable by a path of length 3. The derivation should show how odd cycles shrink the "flip twice and return" signal toward the one-hop signal, and it gives a predicted accuracy surface we can compare with experiment.

The third component is a synthetic generator that holds homophily and degree distribution fixed while varying odd-cycle content. It starts from a bipartite heterophilous graph with Cora-like features, in the style of syn-cora, and plants odd cycles of controlled length with label-preserving edge swaps. This breaks the confound present in every existing benchmark.

The fourth component is the model, and it is deliberately small. We take ACM's three-channel gate, add H2GCN's exact-two-hop channel, and feed $\pi_v$ and log-degree into the gate as fixed inputs alongside the learned features. We call this the parity-gated model. Nothing else changes, so any gain is attributable to the structural input.

Baselines

The naive reference is a structure-free multilayer perceptron on node features, together with a vanilla GCN (graph convolutional network, the basic averaging model). On Texas, Beyond Fixed Depth reports vanilla GCN at about 60% accuracy. On Squirrel, Make Heterophily Graphs Better Fit GNN reports 26%. Any structural method must beat the multilayer perceptron or it has learned nothing from edges.

The strongest direct competitor is ACM from Revisiting Heterophily. It already learns a per-node channel choice, so it is precisely the thing our structural input claims to improve. Its paper reports gains of 2.04% to 27.50% over base models across seven heterophilous datasets. I found no reported per-dataset absolute ACM accuracy on Lacuna, so we rerun it ourselves.

H2GCN represents fixed two-hop aggregation and reports up to 40% gains on synthetic low-homophily graphs. AD-GNN is the per-node depth-adaptive alternative, with a reported 92.3% on Texas. DHGR is the rewiring alternative, with a reported GCN+DHGR accuracy of about 67% on Squirrel. A learnable polynomial spectral filter, following A Piece-wise Polynomial Filtering Approach, is included because an alternating-sign polynomial in the adjacency matrix can mimic parity weighting globally.

For fairness, every method is reimplemented or rerun on identical splits with identical feature preprocessing. Each gets the same hyperparameter search budget: equal trials and the same validation-based selection. Each is reported as mean and spread over ten splits. Reported numbers from the papers are cited only as sanity checks on our reproductions.

The key ablation replaces $\pi_v$ in the gate with three alternatives in turn. The first is a shuffled $\pi$, which keeps its distribution but destroys node alignment. The second is the local clustering coefficient, which counts triangles only. The third is degree alone. Beating ACM means a statistically reliable gain in overall accuracy, or ROC AUC on Questions, on at least the heterophilous datasets with bipartite-like compatibility, plus a larger gain in the lowest-degree quartile. Beating the ablations means the real $\pi_v$ outperforms all three substitutes.

Why not just…?

Why not just measure two-hop homophily from training labels? For dataset-level diagnosis this may work as well, and we report it head to head with $\pi$ and label informativeness. Labels cannot give a reliable estimate at a low-degree test node with no labeled vertices within two hops, and that is where gating decisions matter. The decisive test is whether $\pi_v$ predicts the per-node two-hop accuracy gain on such nodes. If label-based two-hop homophily wins even there, the structural score adds nothing and we will say so.

Why not just let ACM's attention learn the right channel? ACM's own authors note that its gates fail under class imbalance and are hard to estimate on low-degree nodes. That is an argument, not evidence that a structural input fixes it. The parity-gated model versus ACM comparison, split by degree quartile and with the shuffled-$\pi$ control, settles the question directly.

Why not just use triangle counts or a global polynomial filter? This is the most serious threat. Clustering coefficients capture three-cycles, and an alternating-sign polynomial filter captures parity globally. We include both as ablations. If clustering matches $\pi$, we adopt the simpler score and the paper becomes a triangle-gating result. If the global polynomial matches the node-wise gate, the conclusion is that parity matters at the dataset level only. Our prediction is that pentagon-rich graphs and graphs with mixed local structure separate them. The synthetic generator plants five-cycles specifically to test this.

Why not just drop the edges with an MLP or rewire them away? The multilayer perceptron discards the structured signal that H2GCN and AD-GNN show is worth up to 27–40%. Rewiring with DHGR changes the very cycle structure we study. We report DHGR, and we also measure $\pi$ before and after rewiring to see whether DHGR's gains come from accidentally increasing parity consistency.

Proposed Experiments

On the synthetic generator, we sweep odd-cycle density at fixed homophily (0.1, 0.2, 0.3) and fixed degree. The decisive check is that the two-hop gain over one-hop falls monotonically with planted odd-cycle density while edge homophily, adjusted homophily and label informativeness stay constant. That outcome would show that existing metrics miss this axis. If the gain is flat, the core claim is false.

On real benchmarks we use Texas, Wisconsin, Cornell, Chameleon, Squirrel, Actor, Questions and Twitch-gamers for heterophily, and Cora, CiteSeer, PubMed and ogbn-arxiv as homophilous controls. For each dataset we report the graph-level frustration estimate, the involution-closeness of its compatibility matrix, and the Spearman correlation between $\pi_v$ and the per-node two-hop gain. That correlation is computed over held-out nodes and compared against label-informativeness-style local estimates. The scoped prediction is that correlations are strong only where compatibility is bipartite-like.

We then compare the parity-gated model with all baselines on accuracy (ROC AUC for Questions), broken down by degree quartile. On homophilous controls we check that there is no regression.

The cost check confirms that probe-based estimation of $\pi$ scales to ogbn-arxiv without forming two-hop matrices, and reports wall-clock time relative to a GCN.