On Analyzing Graphs with Motif-Paths
On Analyzing Graphs with Motif-Paths
复制标题
DOI：
10.14778/3447689.3447714
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Xiaodong Li;Reynold Cheng;K. Chang;Caihua Shan;Chenhao Ma;Hongtai Cao
中科院分区：
文献类型：
--
作者：
Xiaodong Li;Reynold Cheng;K. Chang;Caihua Shan;Chenhao Ma;Hongtai Cao
基于路径的解决方案已被证明对各种图分析任务有用，例如链接预测和图聚类。然而，它们不再足以处理复杂和巨大的图形。近年来，基于母题的分析引起了人们的广泛关注。模体，或有几个节点的小图，通常被认为是图的基本单位。基于Motif的分析抓住了节点之间的高阶结构，比传统的基于边的解决方案具有更好的性能。在本文中，我们研究了Motif-Path，它概念上是一个或多个Motif实例的串联。我们研究了Motif-Path如何用于三种基于路径的挖掘任务，即链接预测、局部图聚类和节点排序。我们进一步解决了两个图节点没有通过Motif路径连接的情况，并开发了一种新的碎片整理方法来增强它。在真实图数据集上的实验结果表明，使用Motif-Path和碎片整理技术可以提高图分析的效率。
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.