# Exploring Adaptive Structure Learning for Heterophilic Graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 10 references that are in the map.
- First posted on arXiv 27 Jul 2025.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks](https://mlsanity.com/paper/2102.06462/) (2021)
- [Graph Neural Networks for Graphs with Heterophily: A Survey](https://mlsanity.com/paper/2202.07082/) (2022)
- [Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing](https://mlsanity.com/paper/2302.01524/) (2023)
- [Locality-Aware Graph-Rewiring in GNNs](https://mlsanity.com/paper/2310.01668/) (2023)

## Abstract (arXiv)

Graph Convolutional Networks (GCNs) gained traction for graph representation learning, with recent attention on improving performance on heterophilic graphs for various real-world applications. The localized feature aggregation in a typical message-passing paradigm hinders the capturing of long-range dependencies between non-local nodes of the same class. The inherent connectivity structure in heterophilic graphs often conflicts with information sharing between distant nodes of same class. We propose structure learning to rewire edges in shallow GCNs itself to avoid performance degradation in downstream discriminative tasks due to oversmoothing. Parameterizing the adjacency matrix to learn connections between non-local nodes and extend the hop span of shallow GCNs facilitates the capturing of long-range dependencies. However, our method is not generalizable across heterophilic graphs and performs inconsistently on node classification task contingent to the graph structure.