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.
Abstract
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.
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, M. Bouguessa· 0 citations
Graph Neural Networks exhibit a puzzling numerical fragility under mixed-precision training, failing significantly more often than MLPs or CNNs. This failure is inherently tied to graph structure, with heterophilic graphs and high-degree nodes being particularly vulnerable. We identify the root cause as catastrophic cancellation during neighborhood aggregation. When neighboring node embeddings point in opposite directions, their sum collapses toward zero and amplifies floating-point errors by orders of magnitude. We formalize this through the cancellation ratio ?, proving that it is fundamentally governed by graph topology, including heterophily, node degree, and network depth. Consequently, we propose Aggregation-Aware Representation Learning (AARL) to learn numerically stable and cancellation-resistant representations without sacrificing expressiveness. Unlike naive approaches that enforce neighbor alignment and destroy discriminative power, AARL maintains representation diversity while ensuring numerically safe aggregation. Experiments on diverse benchmarks demonstrate that AARL substantially improves training stability under low precision while preserving or improving classification accuracy.
Jiawei Gu, Ziyue Qiao· Proceedings of the 32nd ACM...· 0 citations
This work proposes Graph Diffusion Counterfactual Explanation via Inversion (GDCE-I), a discrete denoising diffusion model with a novel discrete inversion scheme that enables distribution-aware edits leveraging the whole domain edit space and qualitatively shows that GDCE-I attains interpretable in-distribution solutions.
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.
Graph Neural Networks (GNNs) have exhibited extraordinary performance in data mining. The success depends on the message passing mechanism, which is consistent with the homophily assumption that adjacent nodes share similar behaviors. However, the connected nodes in real-world graphs often show dissimilar behaviors, which is presented as the heterophily problem. A series of works proposed various models to solve the heterophily problem. They usually assume that the neighborhood distribution of nodes with the same class tends to be similar, while distinguishable from nodes of different classes. However, our experiments discovered that many nodes belonging to different classes share the same neighbor distribution in the mainstream datasets. The performance of GNN also degrades in these conflicting nodes. To detect the conflicting nodes and improve their prediction accuracy, we propose the Conflicting Node Discrimination GNN (CNDGNN). It firstly detects the possible conflicting nodes with the same neighbor distribution according to the selected high-quality pseudo-label. Then it estimates the class type of conflicting nodes with the same neighbor distribution through nodes' high-order neighbor distributions and original features, and the aggregation weights are learned to assign positive weights for nodes of the same class type and negative weights for nodes of different classes. The theoretical analysis proves that CNDGNN performs better than GCN in the conflicting nodes and explores the key design view when solving the conflicting node problem. The experiments demonstrate the effectiveness of our method in the mainstream datasets and verify that our method performs better in conflicting nodes.
Wenjun Wang, Xin Cao, Yawen Li et al.· Proceedings of the 32nd ACM...· 0 citations
This work uses a recently introduced neuro-symbolic framework, to embed a standard GNN into a Relational Bayesian Network (RBN), enabling maximum a-posteriori (MAP) inference that jointly optimises node labels to match the observed local homophily structure of a graph.
Raffaele Pojer, Andrea Passerini, Kim G. Larsen et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
