Interpretable and Adaptive Node Classification on Heterophilic Graphs via Combinatorial Scoring and Hybrid Learning

• URL: http://arxiv.org/abs/2512.22221v1
• Date: Mon, 22 Dec 2025 20:50:44 GMT
• Title: Interpretable and Adaptive Node Classification on Heterophilic Graphs via Combinatorial Scoring and Hybrid Learning
• Authors: Soroush Vahidi,
• Abstract summary: Graph neural networks (GNNs) achieve strong performance on homophilic graphs but often struggle underphily, where adjacent nodes frequently belong to different classes.<n>We propose an interpretable and adaptive framework for semi-supervised node classification based on explicit inference rather than deep message passing.<n> Experiments on heterophilic and transitional benchmarks demonstrate competitive performance with modern GNNs while offering advantages in interpretability, tuna, and computational efficiency.
• Score: 1.2691047660244335
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Graph neural networks (GNNs) achieve strong performance on homophilic graphs but often struggle under heterophily, where adjacent nodes frequently belong to different classes. We propose an interpretable and adaptive framework for semi-supervised node classification based on explicit combinatorial inference rather than deep message passing. Our method assigns labels using a confidence-ordered greedy procedure driven by an additive scoring function that integrates class priors, neighborhood statistics, feature similarity, and training-derived label-label compatibility. A small set of transparent hyperparameters controls the relative influence of these components, enabling smooth adaptation between homophilic and heterophilic regimes. We further introduce a validation-gated hybrid strategy in which combinatorial predictions are optionally injected as priors into a lightweight neural model. Hybrid refinement is applied only when it improves validation performance, preserving interpretability when neuralization is unnecessary. All adaptation signals are computed strictly from training data, ensuring a leakage-free evaluation protocol. Experiments on heterophilic and transitional benchmarks demonstrate competitive performance with modern GNNs while offering advantages in interpretability, tunability, and computational efficiency.

Related papers

• Limits of message passing for node classification: How class-bottlenecks restrict signal-to-noise ratio [0.6117371161379209]
  Message passing neural networks (MPNNs) are powerful models for node classification but suffer from performance limitations under heterophily and structural bottlenecks in the graph.<n>We provide a unifying statistical framework exposing the relationship between heterophily and bottlenecks through the signal-to-noise ratio (SNR) of MPNN representations.<n>We prove that optimal graph structures for maximising higher-order homophily are disjoint unions of single-class and two-class-bipartite clusters.<n>This yields BRIDGE, a graph ensemble-based rewiring algorithm that achieves near-perfect classification accuracy across all homophily
  arXiv  Detail & Related papers  (2025-08-25T09:25:14Z)
• ReDiSC: A Reparameterized Masked Diffusion Model for Scalable Node Classification with Structured Predictions [64.17845687013434]
  We propose ReDiSC, a structured diffusion model for structured node classification.<n>We show that ReDiSC achieves superior or highly competitive performance compared to state-of-the-art GNN, label propagation, and diffusion-based baselines.<n> Notably, ReDiSC scales effectively to large-scale datasets on which previous structured diffusion methods fail due to computational constraints.
  arXiv  Detail & Related papers  (2025-07-19T04:46:53Z)
• Matcha: Mitigating Graph Structure Shifts with Test-Time Adaptation [66.40525136929398]
  Test-time adaptation (TTA) has attracted attention due to its ability to adapt a pre-trained model to a target domain, without re-accessing the source domain.<n>We propose Matcha, an innovative framework designed for effective and efficient adaptation to structure shifts in graphs.<n>We validate the effectiveness of Matcha on both synthetic and real-world datasets, demonstrating its robustness across various combinations of structure and attribute shifts.
  arXiv  Detail & Related papers  (2024-10-09T15:15:40Z)
• Heterophily-Based Graph Neural Network for Imbalanced Classification [19.51668009720269]
  We introduce a unique approach that tackles imbalanced classification on graphs by considering graph heterophily. We propose Fast Im-GBK, which integrates an imbalance classification strategy with heterophily-aware GNNs. Our experiments on real-world graphs demonstrate our model's superiority in classification performance and efficiency for node classification tasks.
  arXiv  Detail & Related papers  (2023-10-12T21:19:47Z)
• Variational Classification [51.2541371924591]
  We derive a variational objective to train the model, analogous to the evidence lower bound (ELBO) used to train variational auto-encoders. Treating inputs to the softmax layer as samples of a latent variable, our abstracted perspective reveals a potential inconsistency. We induce a chosen latent distribution, instead of the implicit assumption found in a standard softmax layer.
  arXiv  Detail & Related papers  (2023-05-17T17:47:19Z)
• Boosting Differentiable Causal Discovery via Adaptive Sample Reweighting [62.23057729112182]
  Differentiable score-based causal discovery methods learn a directed acyclic graph from observational data. We propose a model-agnostic framework to boost causal discovery performance by dynamically learning the adaptive weights for the Reweighted Score function, ReScore.
  arXiv  Detail & Related papers  (2023-03-06T14:49:59Z)
• Pseudo Contrastive Learning for Graph-based Semi-supervised Learning [67.37572762925836]
  Pseudo Labeling is a technique used to improve the performance of Graph Neural Networks (GNNs) We propose a general framework for GNNs, termed Pseudo Contrastive Learning (PCL)
  arXiv  Detail & Related papers  (2023-02-19T10:34:08Z)
• Descent Steps of a Relation-Aware Energy Produce Heterogeneous Graph Neural Networks [25.59092732148598]
  Heterogeneous graph neural networks (GNNs) achieve strong performance on node classification tasks in a semi-supervised learning setting. We propose a novel heterogeneous GNN architecture in which layers are derived from optimization steps that descend a novel relation-aware energy function.
  arXiv  Detail & Related papers  (2022-06-22T13:48:08Z)
• Simplifying Node Classification on Heterophilous Graphs with Compatible Label Propagation [6.071760028190454]
  We show that a well-known graph algorithm, Label Propagation, combined with a shallow neural network can achieve comparable performance to GNNs in semi-supervised node classification on graphs with high homophily. In this paper, we show that this approach falls short on graphs with low homophily, where nodes often connect to the nodes of the opposite classes. Our algorithm first learns the class compatibility matrix and then aggregates label predictions using LP algorithm weighted by class compatibilities.
  arXiv  Detail & Related papers  (2022-05-19T08:34:34Z)
• Deep Contrastive Graph Representation via Adaptive Homotopy Learning [76.22904270821778]
  Homotopy model is an excellent tool exploited by diverse research works in the field of machine learning. We propose a novel adaptive homotopy framework (AH) in which the Maclaurin duality is employed. AH can be widely utilized to enhance the homotopy-based algorithm.
  arXiv  Detail & Related papers  (2021-06-17T04:46:04Z)
• Bayesian Graph Neural Networks with Adaptive Connection Sampling [62.51689735630133]
  We propose a unified framework for adaptive connection sampling in graph neural networks (GNNs) The proposed framework not only alleviates over-smoothing and over-fitting tendencies of deep GNNs, but also enables learning with uncertainty in graph analytic tasks with GNNs.
  arXiv  Detail & Related papers  (2020-06-07T07:06:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.