Deep Overlapping Community Search via Subspace Embedding

Qing Sima; Jianke Yu; Xiaoyang Wang; Wenjie Zhang; Ying Zhang; Xuemin Lin

doi:10.1145/3709678

journal article Feb 10, 2025

Deep Overlapping Community Search via Subspace Embedding

Qing Sima

Proceedings of the ACM on Management of Data Vol. 3 No. 1 pp. 1-26 · Association for Computing Machinery (ACM)

View at Publisher Save 10.1145/3709678

Abstract

Overlapping Community Search (OCS) identifies nodes that interact with multiple communities based on a specified query. Existing community search approaches fall into two categories: algorithm-based models and Machine Learning-based (ML) models. Despite the long-standing focus on this topic within the database domain, current solutions face two major limitations: 1) Both approaches fail to address personalized user requirements in OCS, consistently returning the same set of nodes for a given query regardless of user differences. 2) Existing ML-based CS models suffer from severe training efficiency issues. In this paper, we formally redefine the problem of OCS. By analyzing the gaps in both types of approaches, we then propose a general solution for OCS named
S
parse
S
ubspace
F
ilter (SSF), which can extend any ML-based CS model to enable personalized search in overlapping structures. To overcome the efficiency issue in the current models, we introduce
S
implified
M
ulti-hop Attention
N
etworks (SMN), a lightweight yet effective community search model with larger receptive fields. To the best of our knowledge, this is the first ML-based study of overlapping community search. Extensive experiments validate the superior performance of SMN within the SSF pipeline, achieving a 13.73% improvement in F1-Score and up to 3 orders of magnitude acceleration in model efficiency compared to state-of-the-art approaches.

Topics

No keywords indexed for this article. Browse by subject →

References

56

[1]

10.14778/3137628.3137640

[2]

10.14778/3570690.3570700

[3]

10.1109/cvpr52688.2022.00012

[4]

10.1145/2463676.2463722

[5]

Ehsan Elhamifar and René Vidal. 2013. Sparse subspace clustering: Algorithm, theory, and applications. IEEE transactions on pattern analysis and machine intelligence, Vol. 35, 11 (2013), 2765--2781.

[6]

Shuheng Fang, Kangfei Zhao, Guanghua Li, and Jeffrey Xu Yu. 2023. Community search: a meta-learning approach. In IEEE 39th ICDE. 2358--2371.

[7]

10.14778/2994509.2994538

[8]

Yixiang Fang and Reynold Cheng. 2017. On attributed community search. In International Workshop on Mobility Analytics for Spatio-temporal and Social Data. 1--21.

[9]

10.1007/s00778-017-0482-5

[10]

10.1007/s00778-019-00556-x

[11]

10.1109/tkde.2018.2845414

[12]

Hypergraph Neural Networks

Yifan Feng, Haoxuan You, Zizhao Zhang et al.

Proceedings of the AAAI Conference on Artificial I... 10.1609/aaai.v33i01.33013558

[13]

10.1007/s10618-016-0464-z

[14]

ICS-GNN

Jun Gao, Jiazun Chen, Zhao Li et al.

Proceedings of the VLDB Endowment 10.14778/3447689.3447704

[15]

10.1145/2723372.2723723

[16]

Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017a. Inductive representation learning on large graphs. Advances in neural information processing systems, Vol. 30 (2017).

[17]

Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017b. Inductive representation learning on large graphs. Advances in neural information processing systems, Vol. 30 (2017).

[18]

10.1145/3543873.3587654

[19]

10.1145/3397271.3401063

[20]

10.1145/2588555.2610495

[21]

10.14778/2856318.2856323

[22]

Ajay Kumar Jaiswal, Haoyu Ma, Tianlong Chen, Ying Ding, and Zhangyang Wang. 2022. Training your sparse neural network better with any mask. In International Conference on Machine Learning. PMLR, 9833--9844.

[23]

Pan Ji, Tong Zhang, Hongdong Li, Mathieu Salzmann, and Ian Reid. 2017. Deep subspace clustering networks. Advances in neural information processing systems, Vol. 30 (2017).

[24]

10.14778/3514061.3514070

[25]

10.1145/3514221.3526137

[26]

Thomas N Kipf and Max Welling. 2016. Semi-Supervised Classification with Graph Convolutional Networks. (2016).

[27]

Ismael Lemhadri, Feng Ruan, Louis Abraham, and Robert Tibshirani. 2021. Lassonet: A neural network with feature sparsity. Journal of Machine Learning Research, Vol. 22, 127 (2021), 1--29.

[28]

Jure Leskovec and Julian Mcauley. 2012. Learning to discover social circles in ego networks. Advances in neural information processing systems, Vol. 25 (2012).

[29]

10.1109/iccv.2019.00936

[30]

Ling Li, Siqiang Luo, Yuhai Zhao, Caihua Shan, Zhengkui Wang, and Lu Qin. 2023. COCLEP: Contrastive Learning-based Semi-Supervised Community Search. IEEE 39th ICDE (2023).

[31]

Guangcan Liu, Zhouchen Lin, Shuicheng Yan, Ju Sun, Yong Yu, and Yi Ma. 2012. Robust recovery of subspace structures by low-rank representation. IEEE transactions on pattern analysis and machine intelligence, Vol. 35, 1 (2012), 171--184.

[32]

10.1145/3560485

[33]

Vishal M Patel and René Vidal. 2014. Kernel sparse subspace clustering. In 2014 ieee international conference on image processing (icip). 2849--2853. 10.1109/icip.2014.7025576

[34]

10.1109/iccv48922.2021.00015

[35]

10.1007/s11227-017-1976-z

[36]

Oleksandr Shchur and Stephan Günnemann. 2019. Overlapping Community Detection with Graph Neural Networks. Deep Learning on Graphs Workshop, KDD (2019).

[37]

10.1145/1835804.1835923

[38]

10.1109/cvprw.2017.61

[39]

10.1145/3583780.3615209

[40]

Xingyu Tan, Xiaoyang Wang, Qing Liu, Xiwei Xu, Xin Yuan, and Wenjie Zhang. 2024. Paths-over-Graph: Knowledge Graph Empowered Large Language Model Reasoning. arXiv preprint arXiv:2410.14211 (2024).

[41]

10.1080/10494820.2021.1875001

[42]

Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2018. GRAPH ATTENTION NETWORKS. stat, Vol. 1050 (2018), 4.

[43]

10.1145/3514221.3526163

[44]

H Wang D Lian Y Zhang L Qin and X Lin. 2021a. GoGNN: Graph of graphs neural network for predicting structured entity interactions. (2021). 10.24963/ijcai.2020/183

[45]

Jianwei Wang, Kai Wang, Xuemin Lin, Wenjie Zhang, and Ying Zhang. 2024a. Efficient Unsupervised Community Search with Pre-trained Graph Transformer. arXiv preprint arXiv:2403.18869 (2024).

[46]

Jianwei Wang, Kai Wang, Xuemin Lin, Wenjie Zhang, and Ying Zhang. 2024b. Neural Attributed Community Search at Billion Scale. Proceedings of the ACM on Management of Data, Vol. 1, 4 (2024), 1--25. 10.1145/3626738

[47]

10.14778/3675034.3675042

[48]

10.1007/s41019-017-0051-3

[49]

Yifei Wang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin. 2021b. Dissecting the diffusion process in linear graph convolutional networks. Advances in Neural Information Processing Systems, Vol. 34 (2021), 5758--5769.

[50]

Rongzhe Wei, Haoteng Yin, Junteng Jia, Austin R Benson, and Pan Li. 2022. Understanding non-linearity in graph neural networks from the bayesian-inference perspective. Advances in Neural Information Processing Systems, Vol. 35 (2022), 34024--34038.

Showing 50 of 56 references

Metrics

9

Citations

56

References

Details

Published: Feb 10, 2025
Vol/Issue: 3(1)
Pages: 1-26
License: View

Authors

Q

Qing Sima

University of New South Wales, Sydney, Australia

J

Jianke Yu

University of Technology Sydney, Sydney, Australia

X

Xiaoyang Wang

University of New South Wales, Sydney, Australia

W

Wenjie Zhang

University of New South Wales, Sydney, Australia

Y

Ying Zhang

University of Technology Sydney, Sydney, Australia

X

Xuemin Lin

Shanghai Jiaotong University, Shanghai, China

Cite This Article

Qing Sima, Jianke Yu, Xiaoyang Wang, et al. (2025). Deep Overlapping Community Search via Subspace Embedding. Proceedings of the ACM on Management of Data, 3(1), 1-26. https://doi.org/10.1145/3709678

Deep Overlapping Community Search via Subspace Embedding

You May Also Like