TY - JOUR
T1 - On analyzing graphs with motif-paths
AU - Li, Xiaodong
AU - Cheng, Reynold
AU - Chang, Kevin Chen Chuan
AU - Shan, Caihua
AU - Ma, Chenhao
AU - Cao, Hongtai
N1 - Funding Information:
X. Li, C. Shan, C. Ma and R. Cheng were supported by the Research Grants Council of Hong Kong (RGC Projects HKU 17229116 and 106150091), the University of Hong Kong (Projects 104005858, 104005994), the Innovation and Technology Commission of Hong Kong (ITF project RP/029/18), and the HKU-TCL Joint Research Center for Artificial Intelligence (200009430). K. Chang and H. Cao were supported by the National Science Foundation IIS 16-19302 and IIS 16-33755, Zhejiang University ZJU Research 083650, Fu-turewei Technologies HF2017060011 and 094013, UIUC OVCR CCIL Planning Grant 434S34, UIUC CSBS Small Grant 434C8U, and IBM-Illinois Center for Cognitive Computing Systems Research (C3SR).
Publisher Copyright:
© is held by the owner/author(s).
PY - 2021
Y1 - 2021
N2 - Path-based solutions have been shown to be useful for various graph analysis tasks, such as link prediction and graph clustering. However, they are no longer adequate for handling complex and gigantic graphs. Recently, motif-based analysis has attracted a lot of attention. A motif, or a small graph with a few nodes, is often considered as a fundamental unit of a graph. Motif-based analysis captures high-order structure between nodes, and performs better than traditional “edge-based” solutions. In this paper, we study motif-path, which is conceptually a concatenation of one or more motif instances. We examine how motif-paths can be used in three path-based mining tasks, namely link prediction, local graph clustering and node ranking.We further address the situation when two graph nodes are not connected through a motif-path, and develop a novel defragmentation method to enhance it. Experimental results on real graph datasets demonstrate the use of motif-paths and defragmentation techniques improves graph analysis effectiveness.
AB - Path-based solutions have been shown to be useful for various graph analysis tasks, such as link prediction and graph clustering. However, they are no longer adequate for handling complex and gigantic graphs. Recently, motif-based analysis has attracted a lot of attention. A motif, or a small graph with a few nodes, is often considered as a fundamental unit of a graph. Motif-based analysis captures high-order structure between nodes, and performs better than traditional “edge-based” solutions. In this paper, we study motif-path, which is conceptually a concatenation of one or more motif instances. We examine how motif-paths can be used in three path-based mining tasks, namely link prediction, local graph clustering and node ranking.We further address the situation when two graph nodes are not connected through a motif-path, and develop a novel defragmentation method to enhance it. Experimental results on real graph datasets demonstrate the use of motif-paths and defragmentation techniques improves graph analysis effectiveness.
UR - http://www.scopus.com/inward/record.url?scp=85102659378&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85102659378&partnerID=8YFLogxK
U2 - 10.14778/3447689.3447714
DO - 10.14778/3447689.3447714
M3 - Article
AN - SCOPUS:85102659378
VL - 14
SP - 1111
EP - 1123
JO - Proceedings of the VLDB Endowment
JF - Proceedings of the VLDB Endowment
SN - 2150-8097
IS - 6
ER -