Skip to content

Learning the Graph and the Embedding Together: Classifier-Independent Rewiring for Heterophilic Node Classification

Sep 2026 · arXiv.org · Vol abs/2609.32613 · 0 citations · 42 references
Computer Science

TL;DR

An affinity-guided rewiring method that estimates the graph and the node representation together and 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.

Abstract

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.

View source

Similar papers

HERALD: High-Fidelity Exemplar Retrieval with Adaptive Landmark Distillation for Heterophily-Aware Graph Condensation

HerALD (High-fidelity Exemplar Retrieval with Adaptive Landmark Distillation with Adaptive Landmark Distillation), a gradient-free graph condensation framework that adapts the node scoring and feature selection in the condensation pipeline to the graph's measured heterophily, is proposed.

Sujan Chakraborty, Priyanka Saha, S. Bej · 0 citations

An Integration of Fuzzy-Enhanced Heterophilic Graph Representation Learning for Improving Performance of Link Prediction

Extensive experiments ensure that FHGE consistently outperforms state-of-the-art baselines and demonstrate the power of fuzzy-driven learning in improving graph embedding quality and establish FHGE as a promising solution for real-world link prediction tasks.

Linh Nguyen Thi My, Tham Vo · 5 citations

Beyond Fixed Features: Architecture-Dependent Sensitivity to Node Representations under Heterophily

Graph Neural Networks perform well on homophilic graphs but struggle in heterophilic settings, where connected nodes often carry dissimilar labels, so architecture and representation cannot be treated as independent evaluation factors.

Priyanath Maji, Sidharth Gaur, Rajavinoth Paul Durai · 0 citations
Preprint Aug 2026

Disentangling Homophily and Rarity: Explaining Failure in Graph Neural Networks

It is demonstrated 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.

Preben M. Ness, Fariz Ikhwantri, D. Marijan · 0 citations

Heterophily-Aware Node Classification in Multiplex Graphs

This work proposes HAAM, an adaptive node classification approach for multiplex graphs that models per-dimension degrees of homophily and heterophily through dimension-specific compatibility matrices, and shows that HAAM achieves competitive performance compared to representative baseline methods.

K. Abdous, Nairouz Mrabah, Mohamed Bouguessa · 0 citations
Sep 2026

Generalizing on Diverse Shifts: A Unified Topology-Aware Reweighting Algorithm for Graphs.

Topology-Aware Dynamic Reweighting (TAR+), a model-agnostic framework for node classification under strict graph distribution shifts and related robustness stressors, is proposed, supporting the broad applicability of topology-aware reweighting across heterogeneous graph learning conditions.

Jia-Xing Li, Jia-Shuo Liu, Wei-Huang Zheng et al. · 0 citations

Related blog posts

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.