Graph neural networks lose much of their advantage on heterophilic graphs, where connected nodes often carry different labels. Graph rewiring is a popular remedy, but rewiring methods are usually evaluated with a single classifier, which makes it hard to tell whether the gains come from the new topology or from that particular pairing. We propose an affinity-guided rewiring method that estimates the graph and the node representation together. It alternates, in the spirit of expectation maximisation, between training a lightweight graph neural network on the current graph and re-weighting candidate edges under a modularity objective with a pseudo-label homophily term. Candidate edges come from a compact pool scored by a contrastively learned node similarity and a neighbourhood-distribution affinity. The method returns two classifier-independent outputs: a rewired graph and a node embedding learned on it. Across six heterophilic benchmarks and five downstream classifiers, it improves accuracy over the original graph with normalised features in 23 of 30 classifier-dataset combinations, with a mean gain of 5.8 points, and reduces the accuracy spread between classifiers about fourfold. A controlled ablation shows that the two outputs are each useful and play complementary roles: the embedding contributes most of the accuracy gain, while the rewired graph makes different classifiers agree. A fully unsupervised variant, which uses no labels during rewiring, retains most of the improvement. The rewired graphs are also more homophilic and improve label propagation and community detection.
Figures & tables
Figure 1: Glare pipeline. A contrastively pretrained encoder produces a node similarity S ; a compact candidate pool is scored by an affinity that blends S with a neighbourhood-distribution signal Φ ; an EM-style loop then alternates between training a lightweight GNN on the current soft graph (E-step) and updating per-edge logits under a modularity-with-homophily objective (M-step). The rewired graph and a multi-hop representation are finally passed to any downstream classifier.
Method
Type
Supporting classifier
IDGL ( Chen et al., 2020b )
Graph structure learning
2-layer GCN (joint)
FoSR ( Karhadkar et al., 2023 )
Spectral rewiring
GCN
ComFy ( Rubio-Madrigal et al., 2025 )
Community/feature rewiring
GCN
LPkG ( Park and Park, 2024 )
k -NN + label propagation
GAE + LP + GNN
DHGR ( Bi et al., 2022 )
Heterophily rewiring
GCN
Glare (ours)
Affinity-guided rewiring
GCN, GAT, SAGE, H2GCN, LINKX
Table 3: Competing methods and the downstream classifier each uses, as recommended in its own paper. Glare is the only method evaluated across all five classifiers.
Figure 2: Macro-F1 scores of the baseline models, the fully unsupervised Glare -U and Glare across the six datasets. The heatmap provides a complementary view of the baseline accuracy comparison, showing the performance of each rewiring method and the downstream classifiers used with Glare .
Figure 3: Accuracy points gained by Glare over the original graph with ℓ2 -normalised features, per classifier and dataset. Green is a gain, red a loss. Glare helps in 23 of 30 cells.
Figure 4: (a) Glare narrows the accuracy gap between the five classifiers. (b) Mean accuracy over the five classifiers for the original graph with ℓ2(X) , the fully unsupervised Glare -U and Glare . Glare -U keeps most of the gain without using any label during rewiring.
Are heterophilic nodes in a graph harder to classify because they are heterophilic or because they are rare? Some existing work frames classification of such nodes as a subgroup generalisation problem, where a model performs well on the majority group at the expense of the rare group. Others explain this as a problem of neighbourhood aggregation in graph neural networks (GNNs). We assess these two viewpoints through a detailed evaluation of six GNNs on five datasets of varying homophily, and find that homophilic nodes tend to be easier to classify, even when they are rare---challenging the subgroup framing. However, our findings also nuance existing beliefs about how GNNs misrepresent heterophilic nodes. We demonstrate that the information needed to classify heterophilic nodes correctly is often recoverable by retraining the classification head of a model, or even just the final linear classification layer.
We introduce Graph Cascades, a mesoscopic rewiring strategy for Graph Neural Networks (GNNs) and Graph Transformers (GTs) that captures intermediate-scale graph structure beyond purely local edges or fully global attention. Using contagion-based diffusion processes, Graph Cascades constructs, in O(|V|+|E|) time, an auxiliary graph where node pairs supported by repeated multi-hop reinforcement are promoted to direct neighbors. We theoretically characterize when reinforcement-based rewiring helps: sufficient conditions under which reinforcement-based edge selection is more label-aligned than direct adjacency, an SBM witness in which two-hop reinforcement is perfectly homophilic, and a formalization of mesoscopic connectivity via graph effective resistance. Empirically, across node-classification benchmarks, Graph Cascades improves multiple GNN and sparse-GT backbones, with the most reliable gains observed on heterophilic and moderate- to high-degree homophilic graphs. The theoretical conditions also identify regimes where mesoscopic rewiring is unlikely to be beneficial -- low-degree regular graphs and graphs with structural bottlenecks -- and these predictions match the observed failures. We additionally observe tight correlations between performance and structural properties in the rewired graphs.
Node classification in graph neural networks (GNNs) has been widely applied in various fields of graph analysis. GNNs achieve high-accuracy node classification in homophilous graphs, where nodes with the same class label tend to be connected. However, their performance remains limited in heterophilous graphs, where nodes with different class labels are more likely to be connected. In particular, current GNNs derived from graph convolutional networks cannot capture higher-order class label connectivity, which is frequently observed in real-world heterophilous graphs. To address this issue, we propose a novel classifier, Label Context Classifier (LCC), designed to capture higher-order class label connectivity in directed graphs. LCC estimates the class label of a target node by leveraging label context embeddings that are generated through four distinct types of walks. In addition, our approach allows the integration of LCC and any GNN by adaptively learning their importance. Experimental results demonstrate that GNNs integrated with LCC outperform SOTA methods and the label context embeddings improve the node classification performance in heterophilous directed graphs.