# Beyond Homophily: Community Search on Heterophilic Graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 52 references that are in the map.
- First posted on arXiv 5 Jan 2026.

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

- [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)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [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)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [Beyond Low-frequency Information in Graph Convolutional Networks](https://mlsanity.com/paper/2101.00797/) (2021)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [Revisiting Heterophily For Graph Neural Networks](https://mlsanity.com/paper/2210.07606/) (2022)
- [Does GNN Pretraining Help Molecular Representation?](https://mlsanity.com/paper/2207.06010/) (2022)
- [Beyond Smoothing: Unsupervised Graph Representation Learning with Edge Heterophily Discriminating](https://mlsanity.com/paper/2211.14065/) (2022)
- [SDGNN: Learning Node Representation for Signed Directed Networks](https://mlsanity.com/paper/2101.02390/) (2021)
- [Paths-over-Graph: Knowledge Graph Empowered Large Language Model Reasoning](https://mlsanity.com/paper/2410.14211/) (2024)
- [A Survey of Community Search Over Big Graphs](https://mlsanity.com/paper/1904.12539/) (2019)
- [HomoGCL: Rethinking Homophily in Graph Contrastive Learning](https://mlsanity.com/paper/2306.09614/) (2023)
- [MemoTime: Memory-Augmented Temporal Knowledge Graph Enhanced Large Language Model Reasoning](https://mlsanity.com/paper/2510.13614/) (2025)
- [Restructuring Graph for Higher Homophily via Adaptive Spectral Clustering](https://mlsanity.com/paper/2206.02386/) (2022)
- [Approximate Closest Community Search in Networks](https://mlsanity.com/paper/1505.05956/) (2015)
- [Query Driven-Graph Neural Networks for Community Search: From Non-Attributed, Attributed, to Interactive Attributed](https://mlsanity.com/paper/2104.03583/) (2021)
- [Neural Attributed Community Search at Billion Scale](https://mlsanity.com/paper/2403.18874/) (2024)
- [Simpler is More: Efficient Top-K Nearest Neighbors Search on Large Road Networks](https://mlsanity.com/paper/2408.05432/) (2024)
- [SGPT: Few-Shot Prompt Tuning for Signed Graphs](https://mlsanity.com/paper/2412.12155/) (2024)
- [DHG-Bench: A Comprehensive Benchmark for Deep Hypergraph Learning](https://mlsanity.com/paper/2508.12244/) (2025)
- [Factorized Graph Representations for Semi-Supervised Learning from Sparse Data](https://mlsanity.com/paper/2003.02829/) (2020)
- [Deep Overlapping Community Search via Subspace Embedding](https://mlsanity.com/paper/2404.14692/) (2024)

## Abstract (arXiv)

Community search aims to identify a refined set of nodes that are most relevant to a given query, supporting tasks ranging from fraud detection to recommendation. Unlike homophilic graphs, many real-world networks are heterophilic, where edges predominantly connect dissimilar nodes. Therefore, structural signals that once reflected smooth, low-frequency similarity now appear as sharp, high-frequency contrasts. However, both classical algorithms (e.g., k-core, k-truss) and recent ML-based models struggle to achieve effective community search on heterophilic graphs, where edge signs or semantics are generally unknown. Algorithm-based methods often return communities with mixed class labels, while GNNs, built on homophily, smooth away meaningful signals and blur community boundaries. Therefore, we propose Adaptive Community Search (AdaptCS), a lightweight framework featuring three key designs: (i) an AdaptCS Encoder that disentangles multi-hop and multi-frequency signals, enabling the model to capture both smooth (homophilic) and contrastive (heterophilic) relations; (ii) a memory-efficient low-rank optimization that removes the main computational bottleneck and ensures model scalability; and (iii) an Adaptive Community Score (ACS) that guides online search by balancing embedding similarity and topological relations. Extensive experiments on both heterophilic and homophilic benchmarks demonstrate that AdaptCS outperforms the best-performing baseline by an average of 11% in F1-score, retains robustness across heterophily levels, and achieves up to 2 orders of magnitude speedup over the strongest ML-based CS baselines.