High-order structure exploration on massive graphs: A local graph clustering perspective

Modeling and exploring high-order connectivity patterns, also called network motifs, are essential for understanding the fundamental structures that control and mediate the behavior of many complex systems. For example, in social networks, triangles have been proven to play the fundamental role in understanding social network communities; in online transaction networks, detecting directed looped transactions helps identify money laundering activities; in personally identifiable information networks, the star-shaped structures may correspond to a set of synthetic identities. Despite the ubiquity of such high-order structures, many existing graph clustering methods are either not designed for the high-order connectivity patterns, or suffer from the prohibitive computational cost when modeling high-order structures in the large-scale networks. This article generalizes the challenges in multiple dimensions. First (Model), we introduce the notion of high-order conductance, and define the high-order diffusion core, which is based on a high-order random walk induced by the user-specified high-order network structure. Second (Algorithm), we propose a novel high-order structure-preserving graph clustering framework named HOSGRAP, which partitions the graph into structure-rich clusters in polylogarithmic time with respect to the number of edges in the graph. Third (Generalization), we generalize our proposed algorithm to solve the real-world problems on various types of graphs, such as signed graphs, bipartite graphs, and multi-partite graphs. Experimental results on both synthetic and real graphs demonstrate the effectiveness and efficiency of the proposed algorithms.