Motif Counting in Complex Networks: A Comprehensive Survey DOI: XXXXXXX.XXXXXXX Journal: JACM Volume: 37 4 111 8 CCS: Mathematics of computing Graph algorithms CCS: Information systems Data mining CCS: Computing methodologies Parallel algorithms

Haozhe Yin, Kai Wang, Wenjie Zhang, Yizhang He, Ying Zhang, Xuemin Lin · 2025

Read Motif Counting in Complex Networks: A Comprehensive Survey DOI: XXXXXXX.XXXXXXX Journal: JACM Volume: 37 4 111 8 CCS: Mathematics of computing Graph algorithms CCS: Information systems Data mining CCS: Computing methodologies Parallel algorithms by Haozhe Yin, Kai Wang, Wenjie Zhang, Yizhang He, Ying Zhang, Xuemin Lin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-19573.txt.

Introduction

Small repeated patterns called motifs reveal how a network is built, from social graphs to brain maps. Haozhe Yin, Kai Wang, Wenjie Zhang, Yizhang He, Ying Zhang, and Xuemin Lin survey the methods for counting those patterns in a 2025 review.

Counting motifs gets hard as networks grow and change shape, and each kind of graph, plain, mixed-type, or hypergraph, brings its own patterns and costs. The survey sorts known algorithms by their core strategy and weighs their speed and limits. It closes with open directions: faster counting on huge networks, methods for graphs that change over time or carry labels, and links with language models and graph-based question answering.

Catalog record

CREATORHaozhe Yin, Kai Wang, Wenjie Zhang, Yizhang He, Ying Zhang, Xuemin Lin
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE116 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-19573

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Motif Counting in Complex Networks: A Comprehensive Survey DOI: XXXXXXX.XXXXXXX Journal: JACM Volume: 37 4 111 8 CCS: Mathematics of computing Graph algorithms CCS: Information systems Data mining CCS: Computing methodologies Parallel algorithms Haozhe Yin, Kai Wang, Wenjie Zhang, Yizhang He, Ying Zhang, Xuemin Lin Abstract . Motif counting plays a crucial role in understanding the structural properties of networks. By computing motif frequencies, researchers can draw key insights into the structural properties of the underlying network. As networks become increasingly complex, different graph models have been proposed, giving rise to diverse motif patterns. These variations introduce unique computational challenges that require specialized algorithms tailored to specific motifs within different graph structures. This survey provides a comprehensive and structured overview of motif counting techniques across general graphs, heterogeneous graphs, and hypergraphs. We categorize existing algorithms according to their underlying computational strategies, emphasizing key similarities and distinctions. In addition to reviewing current methodologies, we examine their strengths, limitations, and computational trade-offs. Furthermore, we explore future directions in motif counting, including scalable implementations to improve efficiency in large-scale networks, algorithmic adaptations for dynamic, temporal, and attributed graphs, and deeper integration with large language models (LLMs) and graph-based retrieval-augmented generation (GraphRAG). By offering a detailed analysis of these approaches, this survey aims to support researchers and practitioners in advancing motif counting for increasingly complex network data. 1. INTRODUCTION In recent years, graphs have become a fundamental tool for modeling interactions among different types of entities across various domains such as social networks ( Coyle and Vaughn 2008 ; Hampton et al. 2011 ) , biological networks ( Wong et al. 2012 ; Masoudi-Nejad et al. 2012 ) , citation networks ( Choobdar et al. 2012 ; Boekhout et al. 2021 ) , etc. While modeling these networks is a critical step in network analytics, a key challenge lies in understanding their structural properties. In networks, motifs (i.e., small repeated sub-graphs) are regarded as basic building blocks, and identifying these motifs can gain valuable insights into underlying interactions among entities within networks ( Wang et al. 2020 ; Ma et al. 2019 ; Gao et al. 2022 ; Marcus and Shavitt 2010 ; Cai et al. 2023 ; Liu et al. 2020 ) . Currently, the field of motif counting has garnered substantial interest from the research community, focusing on the development of motif models and diverse counting algorithms within general graphs ( Danisch et al. 2017 ; Lee et al. 2010 ; Angel et al. 2012 ; Letsios et al. 2016 ) . As data becomes increasingly complex in modern applications, different graph models are proposed including bipartite graphs ( Ye et al. 2023b ; Yang et al. 2021b ; Qiu et al. 2024 ; Wang et al. 2022 ; Wang et al. 2023c ) and heterogeneous graphs ( Fang et al. 2020b ; Luo et al. 2021 ) to achieve effective data modeling. For example, bipartite graphs naturally represent relationships between two distinct sets of entities, making them particularly useful for applications such as user-item networks in e-commerce ( Li et al. 2020b ) and people-location networks in contact tracing ( Chen et al. 2021 ) . Additionally, researchers have developed heterogeneous graph models, characterized by multiple types of nodes and relations, to better model complex relational structures, as in graph-based retrieval-augmented generation (GraphRAG) ( Chen et al. 2025 ; Cai et al. 2024 ; Li et al. 2024 ) , where entity and relation diversity is critical for accurate retrieval and reasoning. However, the diverse structural characteristics of different types of graphs mean that the motif patterns and counting algorithms applicable to one may not be transferable to another. Consequently, specialized motif patterns and corresponding counting techniques have been developed for specific graph types. For example, in general graphs, extensive studies have focused on counting and listing triangles ( Itai and Rodeh 1977 ; Burkhardt 2017 ; Schank and Wagner 2005 ; Cohen 2009 ; Alon et al. 1997 ; Low et al. 2017 ) . In contrast, such triangles cannot exist in bipartite graphs due to their structural constraints. Instead, researchers have proposed the concept of the butterfly ( Wang et al. 2014 ; Sanei-Mehri et al. 2018 ; Wang et al. 2019 ; Zhou et al. 2021 ; Zhou et al. 2023 ) , which serves as an analogue to the triangle in general graphs, capturing similar local connectivity patterns within bipartite graphs. In this paper, we systematically survey motif patterns and their corresponding algorithms in complex networks, enabling researchers to uncover valuable insights into network structure, application-specific motif patterns, and computational techniques associated with different graph types. Our main contributions are outlined as follows: • Review of Motif Counting Algorithms Across Different Graph Types. Our survey covers motif counting algorithms across three graph types: general graphs, heterogeneous graphs, and hypergraphs. Furthermore, since bipartite graphs are a special case of heterogeneous graphs and have been extensively studied, we further categorize heterogeneous graphs into two main types: bipartite graphs and other heterogeneous graphs. We present the distinct motif models introduced in these graph structures, along with the corresponding counting algorithms. • Investigation and Classification of Motif-Specific Counting Algorithms. We focus on algorithms specifically designed for counting particular motif patterns. These algorithms encompass a range of approaches, including exact counting methods, estimation techniques, and their extended versions, such as parallel implementations and GPU-based approaches. To provide a clear understanding of their fundamental principles, we systematically classify algorithms based on their computational logic and provide complete overview tables. • Comparative Analysis and Future Directions. We conduct a comprehensive comparison of motif counting algorithms and identify key areas for future research. Our analysis highlights the potential of integrating motif counting into LLMs via motif-aware retrieval-augmented generation, which enables more efficient and structured reasoning over graph-structured data. Additionally, we examine the scalability and efficiency challenges in large-scale motif discovery and identify opportunities for further optimization. Moreover, we emphasize the need for more effective motif counting in complex graphs by proposing new motif models and developing techniques that adapt to evolving network structures, including dynamic, temporal, and attributed graphs. The remainder of this paper is structured as follows. Section 2 introduces the preliminaries and essential concepts. Section 3 focuses on motifs in general graphs and the corresponding counting algorithms. In Section 4 , we examine motifs in bipartite graphs and their counting methods. Section 5 is dedicated to motifs in heterogeneous graphs, while Section 6 explores motifs in hypergraphs, both along with their respective counting algorithms. Finally, Section 7 provides a summary of the survey and discusses future research directions. Figure 1 . Outline of the Survey. 2. PRELIMINARIES In this paper, we focus on three fundamental types of graphs: general graphs, heterogeneous graphs, and hypergraphs. In addition, we explore bipartite graphs, a special form of heterogeneous graphs. In this section, we introduce the definitions of these graph models, laying the groundwork for the motif counting techniques discussed later. An unweighted undirected graph G is comprised of a set V of vertices and a set E of edges, where vertices represent entities and edges denote relationships between them. In this paper, we refer to this essential graph type as a general graph. Definition 2.0 (

Read the complete text