Paper Info
Title
Discovering Maximal Motif Cliques in Large Heterogeneous Information Networks
Abstract
We study the discovery of cliques (or "complete" subgraphs) in heterogeneous information networks (HINs). Existing clique-finding solutions often ignore the rich semantics of HINs. We propose motif clique, or m-clique, which redefines subgraph completeness with respect to a given motif. A motif, essentially a small subgraph pattern, is a fundamental building block of an HIN. The m-clique concept is general and allows us to analyse "complete" subgraphs in an HIN with respect to desired high-order connection patterns. We further investigate the maximal m-clique enumeration problem (MMCE), which finds all maximal m-cliques not contained in any other m-cliques. Because MMCE is NP-hard, developing an accurate and efficient solution for MMCE is not straightforward. We thus present the META algorithm, which employs advanced pruning strategies to effectively reduce the search space. We also design fast techniques to avoid generating duplicated maximal m-clique instances. Our extensive experiments on large real and synthetic HINs show that META is highly effective and efficient.
Year
DOI
Venue
2019
10.1109/ICDE.2019.00072
2019 IEEE 35th International Conference on Data Engineering (ICDE)
Keywords
Field
DocType
Social networking (online),Computer science,Semantics,Databases,Biology,Space exploration,Conferences
Data mining,Information networks,Clique,Computer science,Enumeration,Motif (music),Completeness (statistics),Semantics
Conference
ISSN
ISBN
Citations 
1084-4627
978-1-5386-7474-1
2
PageRank 
References 
Authors
0.39
0
6
Name
Order
Citations
PageRank
Jiafeng Hu116210.87
Reynold Cheng23069154.13
Kevin Chen-Chuan Chang34071342.80
Aravind Sankar4556.03
Yixiang Fang522723.06
brian yee hong lam6322.65