Cohesiveness-aware Hierarchical Compressed Index for Community Search on Attributed Graphs
Open Access
- 10 February 2025
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (1) , 1-27
Abstract
Community search on attributed graphs (CSAG) is a fundamental topic in graph data mining. Given an attributed graph G and a query node q , CSAG seeks a structural- and attribute-cohesive subgraph from G that contains q . Exact methods based on graph traversal are time-consuming, especially for large graphs. Approximate methods improve efficiency by pruning the search space with heuristics but still take hundreds of milliseconds to tens of seconds to respond, hindering their use in time-sensitive applications. Moreover, pruning strategies are typically tailored to specific algorithms and their cohesiveness metrics, making them difficult to generalize. To address this, we study a general approach to accelerate various CSAG methods. We first present a proximity graph-based, cohesiveness-aware hierarchical index that accommodates different cohesiveness metrics. Then, we present two optimizations to enhance the index's navigability and reliability. Finally, we design a compressed storage structure for space-efficient indexing. Experiments on real-world datasets show that integrating our index with existing mainstream CSAG methods results in an average 30.7× speedup while maintaining a comparable or even better attribute cohesiveness.Keywords
Funding Information
- Universitas Brawijaya (2023C03198)
- Universitas Brawijaya (62072149,62376058)
- Fundamental Research Funds for the Provincial Universities of Zhejiang (GK219909299001-006)
This publication has 41 references indexed in Scilit:
- ICS-GNN$^+$: lightweight interactive community search via graph neural networkThe VLDB Journal, 2022
- Academic Expert Finding via $(k, \mathcal{P})$-Core based Embedding over Heterogeneous Graphs2022
- Effective and Efficient Truss Computation over Large Heterogeneous Information Networks2020
- A survey of community search over big graphsThe VLDB Journal, 2019
- Keyword-Centric Community Search2019
- Contextual Community Search Over Large Social Networks2019
- Effective and efficient attributed community searchThe VLDB Journal, 2017
- Efficient and effective community searchData Mining and Knowledge Discovery, 2015
- Defining and evaluating network communities based on ground-truthKnowledge and Information Systems, 2013
- Navigation in a small worldNature, 2000