.png){kind=icon}
.png){kind=icon}
Return
Self-Supervised Similar Community Search Based on Graph Matching Network
.png){kind=icon}
PRE
AI
R
Y
T
Z
X
X
Y
DOI：10.1109/tkde.2026.3707934.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Communities in information networks often appear as cohesive subgraphs, reflecting strong relationships among entities. Given an information network <inline-formula><tex-math notation="LaTeX">$G$</tex-math></inline-formula> and a query community <inline-formula><tex-math notation="LaTeX">$C_{q}$</tex-math></inline-formula>, similar community search (SCS) identifies a result community <inline-formula><tex-math notation="LaTeX">$C_{r}\subseteq G$</tex-math></inline-formula> that is similar to <inline-formula><tex-math notation="LaTeX">$C_{q}$</tex-math></inline-formula> in terms of community-level features. SCS has broad applications in social marketing, online recommendation, and other domains. Supervised learning-based methods, such as neural subgraph matching (NSM) and graph alignment (GA), offer flexible learning and efficient inference, showing promising potential. However, they still have certain drawbacks. First, no existing method defines an effective metric to quantify the similarity between <inline-formula><tex-math notation="LaTeX">$C_{q}$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$C_{r}$</tex-math></inline-formula> at the community level. Second, GA emphasizes node-wise feature matching, but overlooks structure-wise matching, leading to matching failures when node features are missing. Third, the lack of high-quality human-annotated communities limits the effectiveness of supervised learning. To address these issues, we propose a unified metric for SCS that evaluates community similarity from multiple perspectives, including community cohesiveness, size, and density. We then propose SCS-GMN, an SCS solution based on the Graph Matching Network, which utilizes community similarity-guided self-supervised learning to enhance the cross-graph matching between <inline-formula><tex-math notation="LaTeX">$G$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$C_{q}$</tex-math></inline-formula>, considering not only node-wise features but also structure-wise features. Moreover, we extend SCS-GMN to large graphs by introducing candidate subgraph generation and a graph-matching transformer. Empirical results over seven real-world datasets show that SCS-GMN efficiently returns <inline-formula><tex-math notation="LaTeX">$C_{r}$</tex-math></inline-formula> with an average community similarity of 96.65% to <inline-formula><tex-math notation="LaTeX">$C_{q}$</tex-math></inline-formula> within 64.5 ms, representing a 14.61% similarity improvement and a 2× inference speedup over suboptimal methods.
Keywords:
Similar community search
graph matching network
graph transformer
information network
Journal
IF:
10.4
Papers:
6.7K
Citations:
3.2W
Organization
Cited Papers