pith. sign in

arxiv: 2306.00893 · v3 · submitted 2023-06-01 · 💻 cs.DS

Efficient Temporal Butterfly Counting and Enumeration on Temporal Bipartite Graphs

Xinwei Cai , Xiangyu Ke , Kai Wang , Lu Chen , Tianming Zhang , Qing Liu , Yunjun Gao This is my paper

Pith reviewed 2026-05-24 08:28 UTC · model grok-4.3

classification 💻 cs.DS
keywords temporal bipartite graphsbutterfly countingtemporal motifsgraph enumerationdata structuresstreaming algorithmsparallel graph algorithms
0
0 comments X

The pith

A compact data structure and priority strategy reduce the time complexity of counting and enumerating temporal butterflies in bipartite graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops efficient algorithms for counting and enumerating temporal butterflies, which are 4-vertex bicliques whose edges appear in a specific order within a given duration on temporal bipartite graphs. It begins with a baseline adapted from static butterfly counting methods and then introduces an optimization framework that exploits an intrinsic property of temporal butterflies through a compact data structure and effective priority strategy. This approach is shown to achieve significantly lower time complexity while preserving space efficiency. The algorithms are further generalized to streaming data and multi-core parallel settings. Experiments on eleven large real-world datasets confirm improved efficiency and scalability for downstream uses such as fraud detection and community search.

Core claim

We devise a non-trivial baseline rooted in the state-of-the-art butterfly counting algorithm on static graphs, further explore the intrinsic property of the temporal butterfly, and develop a new optimization framework with a compact data structure and effective priority strategy. The time complexity is proved to be significantly reduced without compromising on space efficiency. In addition, we generalize our algorithms to practical streaming settings and multi-core computing architectures.

What carries the argument

The compact data structure paired with an effective priority strategy that leverages the intrinsic temporal ordering property of butterflies to optimize computation order and reduce redundant work.

If this is right

  • Counting and enumeration become feasible on much larger temporal bipartite graphs for applications including fraud detection, graph embedding, and community search.
  • The same correctness guarantees hold as the baseline while delivering lower time complexity.
  • Streaming extensions support incremental maintenance as new edges arrive without full recomputation.
  • Multi-core parallelization yields additional speedups on shared-memory architectures.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The priority strategy based on temporal order may transfer to efficient counting of other temporal bicliques or higher-order motifs.
  • Similar compact structures could reduce space-time trade-offs in related dynamic graph problems where edge timestamps constrain motif formation.
  • Controlled experiments on synthetic graphs with varying timestamp densities would isolate how much of the speedup comes from the priority ordering alone.

Load-bearing premise

The intrinsic property of the temporal butterfly permits the proposed data structure and priority strategy to achieve the stated complexity reduction while preserving correctness on all inputs.

What would settle it

A temporal bipartite graph on which the new algorithm either produces an incorrect butterfly count or shows no asymptotic time improvement over the static-graph baseline would falsify the central claim.

Figures

Figures reproduced from arXiv: 2306.00893 by Kai Wang, Lu Chen, Qing Liu, Tianming Zhang, Xiangyu Ke, Xinwei Cai, Yunjun Gao.

Figure 1
Figure 1. Figure 1: 6 types of non-isomorphic temporal butterfly. The [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A user-website network. Challenges. Although one can sacrifice the bipartite property and apply existing temporal motif counting and enumeration techniques to determine that of the 4-edge rectangle (then filter based on vertex type), existing techniques either fail since they only support up to 3- vertex, 3-edge temporal motifs [9, 18, 34, 35], or become extremely inefficient1 [21, 28, 34]. Moreover, exist… view at source ↗
Figure 3
Figure 3. Figure 3: All possible static butterflies while 𝑢 is the start￾vertex and the vertex priority follows 𝑝 1 𝑉 > 𝑝 2 𝑉 > 𝑝 3 𝑉 > 𝑝 4 𝑉 . Below we show the correctness and the complexity of TBC. Theorem 1. The TBC correctly solves the temporal butterfly count￾ing problem. Proof. TBC follow the principle of identifying static butterflies, verifying their status as temporal butterflies, and subsequently classifying their … view at source ↗
Figure 4
Figure 4. Figure 4: All possible temporal orderings of two tempo [PITH_FULL_IMAGE:figures/full_fig_p004_4.png] view at source ↗
Figure 6
Figure 6. Figure 6: Example for wedge type conversion. Two wedges [PITH_FULL_IMAGE:figures/full_fig_p005_6.png] view at source ↗
Figure 5
Figure 5. Figure 5: The wedge sets construct from Figure 2 while [PITH_FULL_IMAGE:figures/full_fig_p005_5.png] view at source ↗
Figure 7
Figure 7. Figure 7: Example for 𝐻𝑃. Complexity Analysis. • The time complexity of TBC+ is 𝑂( Í 𝑢∈𝑉 |𝑊 (𝑢)| (𝑙𝑜𝑔(|𝐸(𝑢)|) + 𝛼 𝑙𝑜𝑔( |𝑊 (𝑢) | 𝛼 ))), where 𝛼 is a coefficient between 1 and |𝑊 (𝑢)|. Proof. The main differences between TBC and TBC+ are in the counting phase. Recur() involves each wedge asymptotic participate 𝑙𝑜𝑔(|𝐸(𝑢)|) times in the SetCross(), where 𝐸(𝑢) is the number of wedge sets. Within SetCross(), wedges are tr… view at source ↗
Figure 8
Figure 8. Figure 8: A temporal bipartite graph containing two high [PITH_FULL_IMAGE:figures/full_fig_p008_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Example for 𝑇𝐴,𝑇𝑆. Complexity Analysis. • The time complexity of TBC++ is 𝑂( Í 𝑢∈𝑉 |𝑊 (𝑢)| (𝑙𝑜𝑔(|𝐸(𝑢)|) + 𝑙𝑜𝑔(|𝑊 (𝑢)|))). Proof. Note that, Delete(), Insert() and Query() are all run in 𝑂(𝑙𝑜𝑔(𝑛)), where n is the number of wedges in 𝑇𝐴/𝑇𝑆. Thus, the time complexity of TBC++ is proven. □ • The space complexity of TBC++ is 𝑂(|𝐸| + max𝑢∈𝑉 {|𝑊 (𝑢)|}. Proof. Although 𝑇𝑆 and 𝑇𝐴 require constant times the memory c… view at source ↗
Figure 10
Figure 10. Figure 10: A temporal bipartite graph stream. The intuitive idea is to count the number of temporal butterflies that contain the edge waiting update and modify the counts ac￾cordingly. In this context, we propose the STBC algorithm (detailed in Algorithm 7), a non-trivial extension from TBC++. The major changes are as follows: (1) While enumerating wedges, vertex prior￾ity becomes irrelevant as all butterflies induc… view at source ↗
Figure 11
Figure 11. Figure 11: Time and total counts on varying datasets. [PITH_FULL_IMAGE:figures/full_fig_p011_11.png] view at source ↗
Figure 13
Figure 13. Figure 13: Time on varying 𝛿. 2 0 2 1 2 2 2 3 2 4 (×10 days) 10 1 10 2 10 3 Memory (MB) (a) WN 2 0 2 1 2 2 2 3 2 4 (×10 days) 10 2 10 3 Memory (MB) (b) ER [PITH_FULL_IMAGE:figures/full_fig_p011_13.png] view at source ↗
Figure 15
Figure 15. Figure 15: Time on varying scale of |𝐸|. (and subsequently more arrays in 𝐻𝑃), and TBC+ will be affected greatly - it even runs out of time on WT dataset when 𝛿 = 160 days. The time cost gap between TBE+ and TBC+ widens as 𝛿 increases since the efficiency disparity between range traversal and the binary search becomes more noticeable with larger wedge sets. The memory cost over varying 𝛿 is presented in [PITH_FULL_… view at source ↗
Figure 16
Figure 16. Figure 16: Counts on varying 𝛿. Jiawei Han Jialu Liu Philip S. Yu Jingbo Shang Jialu Liu Jinbo Shang Jiawei Han TKDE18, 1825-1837 t1=1520179200 Synthesis Lectures ... t2=1505101322 arxiv, 1702.04457 t3=1487158421 SIGMOD15, 1729-1744 t4=1431619200 t1+1 t1+2 t2+1t2+2 t1+6 t2+3 t3+1t3+6 t3+2 t4+1 t4+2 t4+5 [PITH_FULL_IMAGE:figures/full_fig_p012_16.png] view at source ↗
Figure 18
Figure 18. Figure 18: Time on varying |𝑤𝑖𝑛𝑑𝑜𝑤|. 1% 5% 10% 25% |stride|/|window| 10 1 10 2 10 3 Time (s) (a) LF 1% 5% 10% 25% |stride|/|window| 10 3 10 4 10 5 Time (s) (b) WT [PITH_FULL_IMAGE:figures/full_fig_p013_18.png] view at source ↗
Figure 21
Figure 21. Figure 21: Time on varying 𝑝. 1×10 3 4×10 3 8×10 3 16×10 3 N W t 10 1 10 1 10 2 10 3 Time (s) 0 25 50 75 100 MAPE(%) sGrappTBC sGrappTBC + sGrappTBC + + relative error 1×10 3 4×10 3 8×10 3 16×10 3 N W t 10 1 10 0 10 1 10 2 Time (s) 0 25 50 75 100 MAPE(%) (a) WN 1×10 3 4×10 3 8×10 3 16×10 3 N W t 10 1 10 2 10 3 Time (s) 0 25 50 75 100 MAPE(%) (b) TW [PITH_FULL_IMAGE:figures/full_fig_p016_21.png] view at source ↗
Figure 22
Figure 22. Figure 22: Time on varying 𝑁𝑊 𝑡 . The time cost and relative error of our series of sGrapp algo￾rithms are depicted in [PITH_FULL_IMAGE:figures/full_fig_p016_22.png] view at source ↗
read the original abstract

Bipartite graphs characterize relationships between two different sets of entities, like actor-movie, user-item, and author-paper. The butterfly, a 4-vertices 4-edges (2,2)-biclique, is the simplest cohesive motif in a bipartite graph and is the fundamental component of higher-order substructures. Counting and enumerating the butterflies offer significant benefits across various applications, including fraud detection, graph embedding, and community search. While the corresponding motif, the triangle, in the unipartite graphs has been widely studied in both static and temporal settings, the extension of butterfly to temporal bipartite graphs remains unexplored. In this paper, we investigate the temporal butterfly counting and enumeration problem: count and enumerate the butterflies whose edges establish following a certain order within a given duration. Towards efficient computation, we devise a non-trivial baseline rooted in the state-of-the-art butterfly counting algorithm on static graphs, further, explore the intrinsic property of the temporal butterfly, and develop a new optimization framework with a compact data structure and effective priority strategy. The time complexity is proved to be significantly reduced without compromising on space efficiency. In addition, we generalize our algorithms to practical streaming settings and multi-core computing architectures. Our extensive experiments on 11 large-scale real-world datasets demonstrate the efficiency and scalability of our solutions.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper investigates counting and enumerating temporal butterflies (4-vertex 4-edge bicliques with temporally ordered edges within a duration) in temporal bipartite graphs. It presents a non-trivial baseline adapted from static butterfly counting, then an optimization framework using a compact data structure and priority strategy that exploits an intrinsic property of temporal butterflies. The authors claim this yields a proved significant reduction in time complexity while preserving space efficiency, with generalizations to streaming settings and multi-core architectures, supported by experiments on 11 large real-world datasets.

Significance. If the claimed complexity bounds and correctness hold, the work would provide the first dedicated efficient solution for temporal motif analysis in bipartite graphs, extending static methods and enabling applications such as fraud detection and community search in dynamic networks. The streaming and parallel extensions, along with the experimental scale, would strengthen its practical impact in temporal graph processing.

major comments (2)
  1. [Optimization framework (and associated complexity analysis)] The central efficiency claim rests on the 'intrinsic property of the temporal butterfly' enabling the compact data structure and priority strategy (abstract). The manuscript must supply the explicit definition of this property, the formal proof of the time-complexity reduction (including the exact asymptotic improvement over the baseline), and verification that correctness is preserved on all inputs; without these derivations the reduction cannot be confirmed.
  2. [Baseline algorithm section] The baseline algorithm is described as 'rooted in the state-of-the-art butterfly counting algorithm on static graphs.' The manuscript should include a precise statement of the baseline's time and space complexity on temporal inputs so that the claimed improvement can be directly compared.
minor comments (2)
  1. [Experiments] The abstract states experiments on '11 large-scale real-world datasets' but does not list the datasets or report per-dataset running times or speed-up ratios; these details should appear in the experimental section with clear tables.
  2. [Preliminaries] Notation for temporal edge ordering and the duration constraint should be introduced with a formal definition early in the paper to avoid ambiguity when describing the temporal butterfly.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive comments. We address each major comment below and will revise the manuscript to incorporate the requested clarifications and additions.

read point-by-point responses

  1. Referee: [Optimization framework (and associated complexity analysis)] The central efficiency claim rests on the 'intrinsic property of the temporal butterfly' enabling the compact data structure and priority strategy (abstract). The manuscript must supply the explicit definition of this property, the formal proof of the time-complexity reduction (including the exact asymptotic improvement over the baseline), and verification that correctness is preserved on all inputs; without these derivations the reduction cannot be confirmed.

    Authors: We agree that the manuscript would benefit from a more self-contained presentation. The intrinsic property (that the four edges of a temporal butterfly must appear in one of a small number of valid temporal orders within the given duration) is introduced in Section 4, and the complexity reduction is claimed in the abstract and proved in Theorem 4.1. However, to make the argument fully explicit, we will add a dedicated subsection that (i) states the property formally, (ii) gives the complete proof of the improved time bound together with the exact asymptotic improvement over the baseline, and (iii) includes a separate correctness argument showing that the compact data structure and priority strategy preserve all valid temporal butterflies on every input. These additions will appear in the revised version. revision: yes

  2. Referee: [Baseline algorithm section] The baseline algorithm is described as 'rooted in the state-of-the-art butterfly counting algorithm on static graphs.' The manuscript should include a precise statement of the baseline's time and space complexity on temporal inputs so that the claimed improvement can be directly compared.

    Authors: We will revise the baseline section to state explicitly the time and space complexity of the adapted static algorithm when run on temporal inputs (accounting for the additional temporal-order checks). This will enable a direct, side-by-side comparison with the complexity of the optimized framework. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper is an algorithmic contribution focused on developing a baseline algorithm, then optimizations via a compact data structure and priority strategy for temporal butterfly counting/enumeration. It claims a proof that time complexity is reduced based on an 'intrinsic property' of temporal butterflies, with extensions to streaming and multi-core settings. No equations, parameters, or results are presented that reduce by construction to fitted inputs, self-definitions, or self-citation chains. The derivation relies on standard complexity analysis and correctness arguments rather than any of the enumerated circular patterns. The contribution is self-contained against external benchmarks (real-world datasets and comparisons to prior static-graph methods).

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard graph-theoretic assumptions for bipartite graphs, temporal edge ordering, and biclique definitions; no free parameters, ad-hoc axioms, or new entities are introduced in the provided abstract.

axioms (1)
  • standard math Standard definitions and properties of bipartite graphs and temporal edge sequences hold.
    Invoked implicitly when extending static butterfly algorithms to the temporal case.

pith-pipeline@v0.9.0 · 5774 in / 1065 out tokens · 20687 ms · 2026-05-24T08:28:15.996372+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Counting Small Balanced (p,q)-bicliques in Signed Bipartite Graphs

    cs.DS 2026-05 unverdicted novelty 6.0

    BBVP, a vertex-based pruning algorithm, counts balanced (p,q)-bicliques in signed bipartite graphs with an average 636x speedup over the adapted SBCList++ baseline for p=q=3 on large real-world data.

Reference graph

Works this paper leans on

69 extracted references · 69 canonical work pages · cited by 1 Pith paper · 1 internal anchor

  1. [1]

    Nesreen K Ahmed, Jennifer Neville, Ryan A Rossi, Nick G Duffield, and Theodore L Willke. 2017. Graphlet decomposition: Framework, algorithms, and applications. KAIS 50, 3 (2017), 689–722

    work page 2017

  2. [2]

    Sinan G Aksoy, Tamara G Kolda, and Ali Pinar. 2017. Measuring and modeling bipartite graphs with community structure. Journal of Complex Networks 5, 4 (2017), 581–603

    work page 2017

  3. [3]

    Hanjo D Boekhout, Walter A Kosters, and Frank W Takes. 2019. Efficiently count- ing complex multilayer temporal motifs in large-scale networks. Computational Social Networks 6, 1 (2019), 1–34

    work page 2019

  4. [4]

    Marco Bressan, Flavio Chierichetti, Ravi Kumar, Stefano Leucci, and Alessandro Panconesi. 2017. Counting graphlets: Space vs time. In WSDM. 557–566

    work page 2017

  5. [5]

    Xiaoshuang Chen, Kai Wang, Xuemin Lin, Wenjie Zhang, Lu Qin, and Ying Zhang. 2021. Efficiently answering reachability and path queries on temporal bipartite graphs. Proceedings of the VLDB Endowment 14, 10 (2021), 1845–1858

    work page 2021

  6. [6]

    Aaron Clauset, Cosma Rohilla Shalizi, and Mark EJ Newman. 2009. Power-law distributions in empirical data. SIAM review 51, 4 (2009), 661–703

    work page 2009

  7. [7]

    Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein

    work page

  8. [8]

    MIT press

    Introduction to algorithms. MIT press

    work page

  9. [9]

    Stephen Eubank, Hasan Guclu, VS Anil Kumar, Madhav V Marathe, Aravind Srinivasan, Zoltan Toroczkai, and Nan Wang. 2004. Modelling disease outbreaks in realistic urban social networks. Nature 429, 6988 (2004), 180–184

    work page 2004

  10. [10]

    Zhongqiang Gao, Chuanqi Cheng, Yanwei Yu, Lei Cao, Chao Huang, and Junyu Dong. 2022. Scalable Motif Counting for Large-scale Temporal Graphs. In ICDE. 2656–2668

    work page 2022

  11. [11]

    Saket Gurukar, Sayan Ranu, and Balaraman Ravindran. 2015. Commit: A scalable approach to mining communication motifs from dynamic networks. In SIGMOD. 475–489

    work page 2015

  12. [12]

    Xiangnan He, Ming Gao, Min-Yen Kan, and Dingxian Wang. 2016. Birank: Towards ranking on bipartite graphs. TKDE 29, 1 (2016), 57–71

    work page 2016

  13. [13]

    Ralf Hinze et al. 1999. Constructing red-black trees. In W AAAPL, Vol. 99. 89–99

    work page 1999

  14. [14]

    Yu Hu, James Trousdale, Krešimir Josi’c, and Eric Shea-Brown. 2013. Motif statistics and spike correlations in neuronal networks. Journal of Statistical Mechanics: Theory and Experiment 2013, 03 (2013), P03012

    work page 2013

  15. [15]

    Junjie Huang, Huawei Shen, Qi Cao, Shuchang Tao, and Xueqi Cheng. 2021. Signed Bipartite Graph Neural Networks. In CIKM. 740–749

    work page 2021

  16. [16]

    Johannes Rude Jensen, Victor von Wachter, and Omri Ross. 2021. An introduc- tion to decentralized finance (defi). Complex Systems Informatics and Modeling Quarterly 26 (2021), 46–54

    work page 2021

  17. [17]

    Jyrki Katajainen, Tomi Pasanen, and Jukka Teuhola. 1996. Practical In-Place Mergesort. Nord. J. Comput. 3, 1 (1996), 27–40

    work page 1996

  18. [18]

    Bogyeong Kim, Kyoseung Koo, Undraa Enkhbat, and Bongki Moon. 2022. Den- Forest: Enabling Fast Deletion in Incremental Density-Based Clustering over Sliding Windows. In SIGMOD. 296–309

    work page 2022

  19. [19]

    Lauri Kovanen, Márton Karsai, Kimmo Kaski, János Kertész, and Jari Saramäki

    work page

  20. [20]

    Journal of Statistical Me- chanics: Theory and Experiment 2011, 11 (2011), P11005

    Temporal motifs in time-dependent networks. Journal of Statistical Me- chanics: Theory and Experiment 2011, 11 (2011), P11005

    work page 2011

  21. [21]

    Rundong Li, Pinghui Wang, Peng Jia, Xiangliang Zhang, Junzhou Zhao, Jing Tao, Ye Yuan, and Xiaohong Guan. 2021. Approximately counting butterflies in large bipartite graph streams. TKDE 34, 12 (2021), 5621–5635

    work page 2021

  22. [22]

    Yuchen Li, Zhengzhi Lou, Yu Shi, and Jiawei Han. 2018. Temporal motifs in heterogeneous information networks. In MLG Workshop@ KDD

    work page 2018

  23. [23]

    Youhuan Li, Lei Zou, M Tamer Özsu, and Dongyan Zhao. 2019. Time constrained continuous subgraph search over streaming graphs. In ICDE. 1082–1093

    work page 2019

  24. [24]

    Zhenyuan Li, Qi Alfred Chen, Runqing Yang, Yan Chen, and Wei Ruan. 2021. Threat detection and investigation with system-level provenance graphs: a survey. Computers & Security 106 (2021), 102282

    work page 2021

  25. [25]

    Boge Liu, Long Yuan, Xuemin Lin, Lu Qin, Wenjie Zhang, and Jingren Zhou

    work page

  26. [26]

    Efficient ( 𝛼, 𝛽)-core computation: An index-based approach. In WWW. 1130–1141

    work page

  27. [27]

    Paul Liu, Austin R Benson, and Moses Charikar. 2019. Sampling methods for counting temporal motifs. In WSDM. 294–302

    work page 2019

  28. [28]

    Penghang Liu, Valerio Guarrasi, and A Erdem Sariyuce. 2021. Temporal network motifs: Models, limitations, evaluation. TKDE 35, 1 (2021), 945–957

    work page 2021

  29. [29]

    Giorgio Locicero, Giovanni Micale, Alfredo Pulvirenti, and Alfredo Ferro. 2020. TemporalRI: A Subgraph Isomorphism Algorithm for Temporal Networks. In Complex Networks, Vol. 944. 675–687

    work page 2020

  30. [30]

    Giorgio Locicero, Giovanni Micale, Alfredo Pulvirenti, and Alfredo Ferro. 2021. TemporalRI: a subgraph isomorphism algorithm for temporal networks. In Pro- ceedings of the Ninth International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2020. 675–687

    work page 2021

  31. [31]

    Patrick Mackey, Katherine Porterfield, Erin Fitzhenry, Sutanay Choudhury, and George Chin. 2018. A chronological edge-driven approach to temporal subgraph isomorphism. In IEEE international conference on Big Data . 3972–3979

    work page 2018

  32. [32]

    Andrew McGregor. 2014. Graph stream algorithms: a survey. ACM SIGMOD Record 43, 1 (2014), 9–20

    work page 2014

  33. [33]

    Youshan Miao, Wentao Han, Kaiwei Li, Ming Wu, Fan Yang, Lidong Zhou, Vijayan Prabhakaran, Enhong Chen, and Wenguang Chen. 2015. Immortalgraph: A system for storage and analysis of temporal graphs. TOS 11, 3 (2015), 1–34

    work page 2015

  34. [34]

    Ron Milo, Shalev Itzkovitz, Nadav Kashtan, Reuven Levitt, Shai Shen-Orr, Inbal Ayzenshtat, Michal Sheffer, and Uri Alon. 2004. Superfamilies of evolved and designed networks. Science 303, 5663 (2004), 1538–1542

    work page 2004

  35. [35]

    Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. 2002. Network motifs: simple building blocks of complex networks. Science 298, 5594 (2002), 824–827

    work page 2002

  36. [36]

    J-P Onnela, Jari Saramäki, Jorkki Hyvönen, György Szabó, David Lazer, Kimmo Kaski, János Kertész, and A-L Barabási. 2007. Structure and tie strengths in mobile communication networks. Proceedings of the national academy of sciences 104, 18 (2007), 7332–7336

    work page 2007

  37. [37]

    Ashwin Paranjape, Austin R Benson, and Jure Leskovec. 2017. Motifs in temporal networks. In WSDM. 601–610

    work page 2017

  38. [38]

    Noujan Pashanasangi and C Seshadhri. 2021. Faster and generalized temporal triangle counting, via degeneracy ordering. In SIGKDD. 1319–1328

    work page 2021

  39. [39]

    Fabiola SF Pereira, Sandra de Amo, and João Gama. 2016. Evolving centralities in temporal graphs: a twitter network analysis. In MDM, Vol. 2. 43–48

    work page 2016

  40. [40]

    Ursula Redmond and Pádraig Cunningham. 2013. Temporal subgraph isomor- phism. In ASONAM. 1451–1452

    work page 2013

  41. [41]

    Pedro Ribeiro and Fernando Silva. 2014. Discovering colored network motifs. In Complex networks V. 107–118

    work page 2014

  42. [42]

    Seyed-Vahid Sanei-Mehri, Ahmet Erdem Sariyüce, and Srikanta Tirthapura. 2018. Butterfly Counting in Bipartite Networks. In SIGKDD. 2150–2159

    work page 2018

  43. [43]

    Seyed-Vahid Sanei-Mehri, Ahmet Erdem Sariyuce, and Srikanta Tirthapura. 2018. Butterfly counting in bipartite networks. In SIGKDD. 2150–2159

    work page 2018

  44. [44]

    Seyed-Vahid Sanei-Mehri, Yu Zhang, Ahmet Erdem Sariyüce, and Srikanta Tirtha- pura. 2019. FLEET: butterfly estimation from a bipartite graph stream. In CIKM. 1201–1210

    work page 2019

  45. [45]

    Ahmet Erdem Sarıyüce and Ali Pinar. 2018. Peeling bipartite networks for dense subgraph discovery. In WSDM. 504–512

    work page 2018

  46. [46]

    Ilie Sarpe and Fabio Vandin. 2021. OdeN: simultaneous approximation of multiple motif counts in large temporal networks. In CIKM. 1568–1577

    work page 2021

  47. [47]

    Comandur Seshadhri, Ali Pinar, and Tamara G Kolda. 2013. Triadic measures on graphs: The power of wedge sampling. In SDM. 10–18

    work page 2013

  48. [48]

    Aida Sheshbolouki and M Tamer Özsu. 2022. sGrapp: Butterfly approximation in streaming graphs. TKDD 16, 4 (2022), 1–43

    work page 2022

  49. [49]

    Jessica Shi and Julian Shun. 2022. Parallel algorithms for butterfly computations. In Massive Graph Analytics. 287–330

    work page 2022

  50. [50]

    Benjamin Steer, Felix Cuadrado, and Richard Clegg. 2020. Raphtory: Streaming analysis of distributed temporal graphs. Future Generation Computer Systems 102 (2020), 453–464

    work page 2020

  51. [51]

    Xiaoli Sun, Yusong Tan, Qingbo Wu, Jing Wang, and Changxiang Shen. 2019. New algorithms for counting temporal graph pattern. Symmetry 11, 10 (2019), 1188

    work page 2019

  52. [52]

    A Vazquez, R Dobrin, D Sergi, J-P Eckmann, Zoltan N Oltvai, and A-L Barabási

    work page

  53. [53]

    Proceedings of the National Academy of Sciences 101, 52 (2004), 17940–17945

    The topological relationship between the large-scale attributes and local interaction patterns of complex networks. Proceedings of the National Academy of Sciences 101, 52 (2004), 17940–17945

    work page 2004

  54. [54]

    Jun Wang, Arjen P De Vries, and Marcel JT Reinders. 2006. Unifying user-based and item-based collaborative filtering approaches by similarity fusion. In SIGIR. 501–508

    work page 2006

  55. [55]

    Jia Wang, Ada Wai-Chee Fu, and James Cheng. 2014. Rectangle counting in large bipartite graphs. In IEEE International Congress on Big Data . 17–24

    work page 2014

  56. [56]

    Jingjing Wang, Yanhao Wang, Wenjun Jiang, Yuchen Li, and Kian-Lee Tan. 2022. Efficient Sampling Algorithms for Approximate Motif Counting in Temporal Graph Streams. arXiv preprint arXiv:2211.12101 (2022)

    work page arXiv 2022

  57. [57]

    Kai Wang, Xuemin Lin, Lu Qin, Wenjie Zhang, and Ying Zhang. 2019. Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks.Proceedings of the VLDB Endowment 12, 10 (2019), 1139–1152

    work page 2019

  58. [58]

    Kai Wang, Xuemin Lin, Lu Qin, Wenjie Zhang, and Ying Zhang. 2020. Efficient bitruss decomposition for large-scale bipartite graphs. In ICDE. 661–672

    work page 2020

  59. [59]

    Kai Wang, Xuemin Lin, Lu Qin, Wenjie Zhang, and Ying Zhang. 2022. Accelerated butterfly counting with vertex priority on bipartite graphs. The VLDB Journal (2022), 1–25

    work page 2022

  60. [60]

    Kai Wang, Xuemin Lin, Lu Qin, Wenjie Zhang, and Ying Zhang. 2022. Towards efficient solutions of bitruss decomposition for large-scale bipartite graphs. The VLDB Journal 31, 2 (2022), 203–226

    work page 2022

  61. [61]

    Duncan J Watts and Steven H Strogatz. 1998. Collective dynamics of ‘small- world’networks. nature 393, 6684 (1998), 440–442

    work page 1998

  62. [62]

    Qingyu Xu, Feng Zhang, Zhiming Yao, Lv Lu, Xiaoyong Du, Dong Deng, and Bingsheng He. 2022. Efficient load-balanced butterfly counting on GPU. PVLDB 15, 11 (2022), 2450–2462

    work page 2022

  63. [63]

    Carl Yang, Mengxiong Liu, Vincent W Zheng, and Jiawei Han. 2018. Node, motif and subgraph: Leveraging network functional blocks through structural convolution. In ASONAM. 47–52

    work page 2018

  64. [64]

    Jianye Yang, Yun Peng, Dian Ouyang, Wenjie Zhang, Xuemin Lin, and Xiang Zhao. 2023. (p, q)-biclique counting and enumeration for large sparse bipartite graphs. The VLDB Journal (2023), 1–25

    work page 2023

  65. [65]

    Ömer Nebil Yaveroğlu, Noël Malod-Dognin, Darren Davis, Zoran Levnajic, Vuk Janjic, Rasa Karapandza, Aleksandar Stojmirovic, and Nataša Pržulj. 2014. Re- vealing the hidden language of complex networks. Scientific reports 4, 1 (2014), 1–9

    work page 2014

  66. [66]

    Na Zhang, Xuefeng Guan, Jun Cao, Xinglei Wang, and Huayi Wu. 2019. A hybrid traffic speed forecasting approach integrating wavelet transform and motif-based graph convolutional recurrent neural network. arXiv preprint arXiv:1904.06656 (2019)

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  67. [67]

    Alexander Zhou, Yue Wang, and Lei Chen. 2021. Butterfly counting on uncertain bipartite graphs. Proceedings of the VLDB Endowment 15, 2 (2021), 211–223

    work page 2021

  68. [68]

    Alexander Zhou, Yue Wang, and Lei Chen. 2023. Butterfly counting and bitruss decomposition on uncertain bipartite graphs. The VLDB Journal (2023), 1–24

    work page 2023

  69. [69]

    Tao Zhou, Jie Ren, Matúš Medo, and Yi-Cheng Zhang. 2007. Bipartite network projection and personal recommendation. Physical review E 76, 4 (2007), 046115. A STUDY ON APPROXIMATION In this section, we demonstrate that our algorithms can be seam- lessly integrated into state-of-the-art approximate techniques to support approximate temporal butterfly countin...

    work page 2007