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

arXiv: https://arxiv.org/abs/2512.22221 · HTML: https://mlsanity.com/paper/2512.22221/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 21 references that are in the map.
- First posted on arXiv 22 Dec 2025.

## Builds on (most cited first, 15 of 15)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Beyond Low-frequency Information in Graph Convolutional Networks](https://mlsanity.com/paper/2101.00797/) (2021)
- [Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods](https://mlsanity.com/paper/2110.14446/) (2021)
- [PairNorm: Tackling Oversmoothing in GNNs](https://mlsanity.com/paper/1909.12223/) (2019)
- [Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks](https://mlsanity.com/paper/2102.06462/) (2021)
- [Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing](https://mlsanity.com/paper/2302.01524/) (2023)
- [Improving Graph Neural Networks with Simple Architecture Design](https://mlsanity.com/paper/2105.07634/) (2021)
- [Simplified Graph Convolution with Heterophily](https://mlsanity.com/paper/2202.04139/) (2022)

## Abstract (arXiv)

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.