More Web Proxy on the site http://driver.im/

research-article

Public Access

CLARE: A Semi-supervised Community Detection Algorithm

Authors:

Philip S. YuAuthors Info & Claims

KDD '22: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

Pages 2059 - 2069

https://doi.org/10.1145/3534678.3539370

Published: 14 August 2022 Publication History

Abstract

Community detection refers to the task of discovering closely related subgraphs to understand the networks. However, traditional community detection algorithms fail to pinpoint a particular kind of community. This limits its applicability in real-world networks, e.g., distinguishing fraud groups from normal ones in transaction networks. Recently, semi-supervised community detection emerges as a solution. It aims to seek other similar communities in the network with few labeled communities as training data. Existing works can be regarded as seed-based: locate seed nodes and then develop communities around seeds. However, these methods are quite sensitive to the quality of selected seeds since communities generated around a mis-detected seed may be irrelevant. Besides, they have individual issues, e.g., inflexibility and high computational overhead. To address these issues, we propose CLARE, which consists of two key components, Community Locator and Community Rewriter. Our idea is that we can locate potential communities and then refine them. Therefore, the community locator is proposed for quickly locating potential communities by seeking subgraphs that are similar to training ones in the network. To further adjust these located communities, we devise the community rewriter. Enhanced by deep reinforcement learning, it suggests intelligent decisions, such as adding or dropping nodes, to refine community structures flexibly. Extensive experiments verify both the effectiveness and efficiency of our work compared with prior state-of-the-art approaches on multiple real-world datasets.

Supplemental Material

MP4 File

Presentation video of KDD'2022 research track full paper "CLARE: A Semi-supervised Community Detection Algorithm".

Download
28.13 MB

References

[1]

Boanerges Aleman-Meza, Christian Halaschek-Wiener, Satya Sanket Sahoo, A. Sheth, and Ismailcem Budak Arpinar. 2005. Template Based Semantic Similarity for Security Applications. In ISI .

[2]

Lars Backstrom, Daniel P. Huttenlocher, Jon M. Kleinberg, and Xiangyang Lan. 2006. Group formation in large social networks: membership, growth, and evolution. In KDD.

[3]

Yunsheng Bai, Haoyang Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. 2019. SimGNN: A Neural Network Approach to Fast Graph Similarity Computation. In WSDM.

[4]

Arjun Bakshi, Srinivasan Parthasarathy, and Kannan Srinivasan. 2018 Semi-Supervised Community Detection Using Structure and Size. In ICDM. 869--874.

[5]

Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. 2008. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, Vol. 2008 (2008), 10008.

[6]

Chen Cai and Yusu Wang. 2019. A simple yet effective baseline for non-attributed graph classification. arxiv: 1811.03508 [cs.LG]

[7]

Sandro Cavallari, V. Zheng, HongYun Cai, K. Chang, and E. Cambria. 2017. Learning Community Embedding with Community Detection and Node Embedding on Graphs. In CIKM.

[8]

Tanmoy Chakraborty, Ayushi Dalmia, Animesh Mukherjee, and Niloy Ganguly. 2016. Metrics for Community Analysis: A Survey. arxiv: 1604.03512 [cs.SI]

[9]

Aaron Clauset, Mark E. J. Newman, and Cristopher Moore. 2004. Finding community structure in very large networks. Physical review. E, Statistical, nonlinear, and soft matter physics, Vol. 70 6 Pt 2 (2004).

[10]

Luigi P Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento. 2004. A (sub) graph isomorphism algorithm for matching large graphs. In PAMI.

[11]

Michelle Guo, Edward Chou, De-An Huang, Shuran Song, Serena Yeung, and Li Fei-Fei. 2018. Neural Graph Matching Networks for Fewshot 3D Action Recognition. In ECCV.

[12]

William L. Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive Representation Learning on Large Graphs. In NIPS.

[13]

Xia Hu, Jiliang Tang, and Huan Liu. 2014. Online Social Spammer Detection. In AAAI.

[14]

Yuting Jia, Qinqin Zhang, Weinan Zhang, and Xinbing Wang. 2019. CommunityGAN: Community Detection with Generative Adversarial Nets. In WWW.

[15]

Yizhu Jiao, Yun Xiong, Jiawei Zhang, Yao Zhang, Tianqi Zhang, and Yangyong Zhu. 2020. Sub-graph Contrast for Scalable Self-Supervised Graph Representation Learning. In

[16]

Di Jin, Ziyang Liu, Weihao Li, Dongxiao He, and Weixiong Zhang. 2019. Graph Convolutional Networks Meet Markov Random Fields: Semi-Supervised Community Detection in Attribute Networks. In AAAI.

[17]

Sham M. Kakade. 2001. A Natural Policy Gradient. In NIPS.

[18]

Elias Boutros Khalil, Hanjun Dai, Yuyu Zhang, Bistra N. Dilkina, and Le Song. 2017. Learning Combinatorial Optimization Algorithms over Graphs. In NIPS.

[19]

Thomas Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. ArXiv, Vol. abs/1609.02907 (2017).

[20]

Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. 2019. Graph Matching Networks for Learning the Similarity of Graph Structured Objects. In ICML.

[21]

Ye Li, Chaofeng Sha, Xin Huang, and Yanchun Zhang. 2018. Community Detection in Attributed Graphs: An Embedding Approach. In AAAI.

[22]

Qiang Ma, Suwen Ge, Danyang He, Darshan D. Thaker, and Iddo Drori. 2019. Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning. ArXiv, Vol. abs/1911.04936 (2019).

[23]

Aaron F. McDaid, Derek Greene, and Neil Hurley. 2013. Normalized Mutual Information to evaluate overlapping community finding algorithms. arxiv: 1110.2515 [physics.soc-ph]

[24]

Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin A. Riedmiller, Andreas Fidjeland, Georg Ostrovski, Stig Petersen, Charlie Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. 2015. Human-level control through deep reinforcement learning. Nature, Vol. 518 (2015), 529--533.

[25]

Bryan Perozzi, Leman Akoglu, Patricia Iglesias Sánchez, and Emmanuel Müller. 2014. Focused clustering and outlier detection in large attributed graphs. In KDD.

[26]

Frank Rosenblatt. 1963. PRINCIPLES OF NEURODYNAMICS. PERCEPTRONS AND THE THEORY OF BRAIN MECHANISMS. American Journal of Psychology, Vol. 76 (1963), 705.

[27]

Caihua Shan, Yifei Shen, Yao Zhang, Xiang Li, and Dongsheng Li. 2021. Reinforcement Learning Enhanced Explainer for Graph Neural Networks. In NIPS.

[28]

Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. 2018. Pitfalls of Graph Neural Network Evaluation. ArXiv, Vol. abs/1811.05868 (2018).

[29]

Jianbo Shi and Jitendra Malik. 1997. Normalized cuts and image segmentation. In CVPR. 731--737.

[30]

Fan-Yun Sun, Meng Qu, Jordan Hoffmann, Chin-Wei Huang, and Jian Tang. 2019. vGraph: A Generative Model for Joint Community Detection and Node Representation Learning. In NIPS.

[31]

Richard S. Sutton, David A. McAllester, Satinder Singh, and Y. Mansour. 1999. Policy Gradient Methods for Reinforcement Learning with Function Approximation. In NIPS.

[32]

Julian R. Ullmann. 1976. An Algorithm for Subgraph Isomorphism. Journal of the ACM (JACM), Vol. 23 (1976), 31--42.

Digital Library

[33]

Xiao Wang, Di Jin, Xiaochun Cao, Liang Yang, and Weixiong Zhang. 2016. Semantic Community Identification in Large Attribute Networks. In AAAI.

[34]

Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. How Powerful are Graph Neural Networks? ArXiv, Vol. abs/1810.00826 (2019).

[35]

Jaewon Yang and Jure Leskovec. 2012. Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems, Vol. 42 (2012), 181--213.

Digital Library

[36]

Jaewon Yang and Jure Leskovec. 2013. Overlapping community detection at scale: a nonnegative matrix factorization approach. In WSDM. 587--596.

[37]

Jaewon Yang, Julian McAuley, and Jure Leskovec. 2013. Community Detection in Networks with Node Attributes. In ICDM.

[38]

Rex Ying, Zhaoyu Lou, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, and Jure Leskovec. 2020. Neural Subgraph Matching. arxiv: 2007.03092 [cs.LG]

[39]

Hongyi Zhang, Irwin King, and Michael R. Lyu. 2015. Incorporating Implicit Link Preference Into Overlapping Community Detection. In AAAI.

Digital Library

[40]

Tianqi Zhang, Yun Xiong, Jiawei Zhang, Yao Zhang, Yizhu Jiao, and Yangyong Zhu. 2020 b. CommDGI: Community Detection Oriented Deep Graph Infomax. In CIKM.

[41]

Yao Zhang, Yun Xiong, Yun Ye, Tengfei Liu, Weiqiang Wang, Yangyong Zhu, and Philip S. Yu. 2020 a. SEAL: Learning Heuristics for Community Detection with Generative Adversarial Networks. In KDD. 1103--1113.

Cited By

Li YYang YZhu JChen HWang HSerra ESpezzano F(2024)LLM-Empowered Few-Shot Node Classification on Incomplete Graphs with Real Node DegreesProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679861(1306-1315)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3679861
Li JLai SShuai ZTan YJia YYu MSong ZPeng XXu ZNi YQiu HYang JLiu YLu Y(2024)A comprehensive review of community detection in graphsNeurocomputing10.1016/j.neucom.2024.128169600(128169)Online publication date: Oct-2024
https://doi.org/10.1016/j.neucom.2024.128169
Liu HWei JWu YLiang C(2024)Information-enhanced deep graph clustering networkNeurocomputing10.1016/j.neucom.2024.127992597:COnline publication date: 7-Sep-2024
https://dl.acm.org/doi/10.1016/j.neucom.2024.127992
Show More Cited By

Index Terms

CLARE: A Semi-supervised Community Detection Algorithm
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Reinforcement learning
2. Information systems
  1. Information systems applications
    1. Data mining
      1. Clustering

Recommendations

SEAL: Learning Heuristics for Community Detection with Generative Adversarial Networks
KDD '20: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining

Community detection is an important task with many applications. However, there is no universal definition of communities, and a variety of algorithms have been proposed based on different assumptions. In this paper, we instead study the semi-supervised ...
ProCom: A Few-shot Targeted Community Detection Algorithm
KDD '24: Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

Targeted community detection aims to distinguish a particular type of community in the network. This is an important task with a lot of real-world applications, e.g., identifying fraud groups in transaction networks. Traditional community detection ...
A deep learning approach for semi-supervised community detection in Online Social Networks
Abstract
Social Network Analysis (SNA) has gained popularity as a way to unveil and identify useful social patterns as communities among users. However the continuous, exponential growth of these networks (both in terms of number ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '22: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 2022

5033 pages

ISBN:9781450393850

DOI:10.1145/3534678

General Chairs:
Aidong Zhang
University of Virginia
,
Huzefa Rangwala
Amazon/George Mason University

Copyright © 2022 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 August 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

KDD '22

Sponsor:

KDD '22: The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 14 - 18, 2022

Washington DC, USA

Acceptance Rates

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
1,670
Total Downloads

Downloads (Last 12 months)872
Downloads (Last 6 weeks)99

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li YYang YZhu JChen HWang HSerra ESpezzano F(2024)LLM-Empowered Few-Shot Node Classification on Incomplete Graphs with Real Node DegreesProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679861(1306-1315)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3679861
Li JLai SShuai ZTan YJia YYu MSong ZPeng XXu ZNi YQiu HYang JLiu YLu Y(2024)A comprehensive review of community detection in graphsNeurocomputing10.1016/j.neucom.2024.128169600(128169)Online publication date: Oct-2024
https://doi.org/10.1016/j.neucom.2024.128169
Liu HWei JWu YLiang C(2024)Information-enhanced deep graph clustering networkNeurocomputing10.1016/j.neucom.2024.127992597:COnline publication date: 7-Sep-2024
https://dl.acm.org/doi/10.1016/j.neucom.2024.127992
Xiang NYou MWang QTian B(2024)Hypergraph network embedding for community detectionThe Journal of Supercomputing10.1007/s11227-024-06003-180:10(14180-14202)Online publication date: 16-Mar-2024
https://dl.acm.org/doi/10.1007/s11227-024-06003-1
Paxinou EManousou EFeretzakis GVerykios V(2023)Community detection and social presence in students’ discussion foraIntelligent Decision Technologies10.3233/IDT-23031517:4(879-891)Online publication date: 20-Nov-2023
https://dl.acm.org/doi/10.3233/IDT-230315
Zhao JWang ZCao JCheong K(2023)A Self-Adaptive Evolutionary Deception Framework for Community StructureIEEE Transactions on Systems, Man, and Cybernetics: Systems10.1109/TSMC.2023.324076553:8(4954-4967)Online publication date: Aug-2023
https://doi.org/10.1109/TSMC.2023.3240765
Wang YCao JBu ZWu JWang Y(2023)Dual Structural Consistency Preserving Community Detection on Social NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.323050235:11(11301-11315)Online publication date: 16-Jan-2023
https://dl.acm.org/doi/10.1109/TKDE.2022.3230502
Costa ANogalha de Lima RRalha C(2023)Machine Learning Approaches for Community Detection in Online Social Networks2023 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI52147.2023.10371982(7-12)Online publication date: 5-Dec-2023
https://doi.org/10.1109/SSCI52147.2023.10371982
Ma TQian YZhang CYe Y(2023)Hypergraph Contrastive Learning for Drug Trafficking Community Detection2023 IEEE International Conference on Data Mining (ICDM)10.1109/ICDM58522.2023.00149(1205-1210)Online publication date: 1-Dec-2023
https://doi.org/10.1109/ICDM58522.2023.00149
Mittal AGoel A(2023)Community Detection using Unsupervised Learning Approach2023 Third International Conference on Artificial Intelligence and Smart Energy (ICAIS)10.1109/ICAIS56108.2023.10073881(946-951)Online publication date: 2-Feb-2023
https://doi.org/10.1109/ICAIS56108.2023.10073881
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents