![[2601.01703] Beyond Homophily: Community Search on Heterophilic Graphs](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2601.01703] Beyond Homophily: Community Search on Heterophilic Graphs
Summary
This paper presents Adaptive Community Search (AdaptCS), a novel framework designed to improve community search in heterophilic graphs, outperforming existing algorithms by enhancing signal processing and computational efficiency.
Why It Matters
Understanding community structures in heterophilic graphs is crucial for applications like fraud detection and recommendation systems. This research addresses limitations in current algorithms, offering a more effective approach that can significantly enhance performance in real-world networks.
Key Takeaways
- AdaptCS effectively captures both homophilic and heterophilic relationships in graphs.
- The framework includes a memory-efficient optimization method, improving scalability.
- AdaptCS demonstrates an average 11% improvement in F1-score over existing models.
- The model achieves significant speed improvements, up to 200 times faster than traditional methods.
- This research highlights the importance of adapting algorithms to the nature of real-world networks.
Computer Science > Social and Information Networks arXiv:2601.01703 (cs) [Submitted on 5 Jan 2026 (v1), last revised 20 Feb 2026 (this version, v2)] Title:Beyond Homophily: Community Search on Heterophilic Graphs Authors:Qing Sima, Xiaoyang Wang, Wenjie Zhang View a PDF of the paper titled Beyond Homophily: Community Search on Heterophilic Graphs, by Qing Sima and 2 other authors View PDF HTML (experimental) Abstract: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) relati...
