# Finding Heterophilic Neighbors via Confidence-based Subgraph Matching for Semi-supervised Node Classification

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 58 references that are in the map.
- First posted on arXiv 20 Feb 2023.

## Builds on (most cited first, 30 of 34)

- [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)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Non-local Neural Networks](https://mlsanity.com/paper/1711.07971/) (2017)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [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)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [Beyond Low-frequency Information in Graph Convolutional Networks](https://mlsanity.com/paper/2101.00797/) (2021)
- [PairNorm: Tackling Oversmoothing in GNNs](https://mlsanity.com/paper/1909.12223/) (2019)
- [Is Homophily a Necessity for Graph Neural Networks?](https://mlsanity.com/paper/2106.06134/) (2021)
- [Learning to Drop: Robust Graph Neural Network via Topological Denoising](https://mlsanity.com/paper/2011.07057/) (2020)
- [Gromov-Wasserstein Learning for Graph Matching and Node Embedding](https://mlsanity.com/paper/1901.06003/) (2019)
- [Node Similarity Preserving Graph Convolutional Networks](https://mlsanity.com/paper/2011.09643/) (2020)
- [Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching](https://mlsanity.com/paper/1905.07645/) (2019)
- [How to Find Your Friendly Neighborhood: Graph Attention Design with Self-Supervision](https://mlsanity.com/paper/2204.04879/) (2022)
- [Unifying Graph Convolutional Neural Networks and Label Propagation](https://mlsanity.com/paper/2002.06755/) (2020)
- [Non-Local Graph Neural Networks](https://mlsanity.com/paper/2005.14612/) (2020)
- [Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?](https://mlsanity.com/paper/2109.05641/) (2021)
- [GEMSEC: Graph Embedding with Self Clustering](https://mlsanity.com/paper/1802.03997/) (2018)
- [Wasserstein Embedding for Graph Learning](https://mlsanity.com/paper/2006.09430/) (2020)
- [AdaGNN: Graph Neural Networks with Adaptive Frequency Response Filter](https://mlsanity.com/paper/2104.12840/) (2021)
- [Confidence May Cheat: Self-Training on Graph Neural Networks under Distribution Shift](https://mlsanity.com/paper/2201.11349/) (2022)

## Built on by (most cited first, 7 of 7)

- [DSLR: Diversity Enhancement and Structure Learning for Rehearsal-based Graph Continual Learning](https://mlsanity.com/paper/2402.13711/) (2024)
- [Causality and Independence Enhancement for Biased Node Classification](https://mlsanity.com/paper/2310.09586/) (2023)
- [A Survey on Learning from Graphs with Heterophily: Recent Advances and Future Directions](https://mlsanity.com/paper/2401.09769/) (2024)
- [Self-Guided Robust Graph Structure Refinement](https://mlsanity.com/paper/2402.11837/) (2024)
- [Heterophilous Distribution Propagation for Graph Neural Networks](https://mlsanity.com/paper/2405.20640/) (2024)
- [Better Not to Propagate: Understanding Edge Uncertainty and Over-smoothing in Signed Graph Neural Networks](https://mlsanity.com/paper/2408.04895/) (2024)
- [Training Robust Graph Neural Networks by Modeling Noise Dependencies](https://mlsanity.com/paper/2502.19670/) (2025)

## Abstract (arXiv)

Graph Neural Networks (GNNs) have proven to be powerful in many graph-based applications. However, they fail to generalize well under heterophilic setups, where neighbor nodes have different labels. To address this challenge, we employ a confidence ratio as a hyper-parameter, assuming that some of the edges are disassortative (heterophilic). Here, we propose a two-phased algorithm. Firstly, we determine edge coefficients through subgraph matching using a supplementary module. Then, we apply GNNs with a modified label propagation mechanism to utilize the edge coefficients effectively. Specifically, our supplementary module identifies a certain proportion of task-irrelevant edges based on a given confidence ratio. Using the remaining edges, we employ the widely used optimal transport to measure the similarity between two nodes with their subgraphs. Finally, using the coefficients as supplementary information on GNNs, we improve the label propagation mechanism which can prevent two nodes with smaller weights from being closer. The experiments on benchmark datasets show that our model alleviates over-smoothing and improves performance.