From Motif to Path: Connectivity and Homophily

While motif has been widely employed in graph analytics, a fundamental question remains open: How should overlapping motif edges connect into a path? Existing works address this question with simple but inconsistent generalizations from standard graphs. This paper studies this issue by proposing the concept of connectivity degree (CD), i.e. the number of overlapping nodes needed for motif edges to be adjacent, as the requirement for path connection. We further study three research questions. First, is CD significant? We study how CD impacts motif analytics, more specifically, three motif-based methods. Second, how to estimate the right CD? We develop a minimax estimator based on minimizing the worst-case risk. Finally, how to detect the connected components with connectivity degree, an important task by itself and necessary for our estimator. As the traditional BFS or DFS approaches are not valid anymore, we develop a disjoint set algorithm instead. Our experiments validate that our CD can improve the performance of motif analytics. Also, our estimator is effective and our connected component detection algorithm is efficient.