Pith. sign in

REVIEW 4 minor 39 references

Four-Cycle Counting in Low-Degeneracy Graph Streams

T0 review · 0 major / 4 minor · reviewed 2026-06-26 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A two-pass streaming algorithm approximates four-cycles using space ilde{O}(\kappa m / \sqrt{T}), matching lower bounds for constant-degeneracy graphs.

desk verdict The paper gives a two-pass streaming algorithm for 4-cycle approximation that ties space to degeneracy and matches the known lower bound for constant-κ graphs, plus a conditional one-pass version. read the letter →

arxiv 2606.17732 v1 pith:NJBTDWWV submitted 2026-06-16 cs.DS

Sebastian Lüderssen , Stefan Neumann , Pan Peng This is my paper · ORCID
classification cs.DS
keywords four-cyclecountinggraphstreamsdegeneracystreamingalgorithmssubgraphsamplingapproximationsocialnetworks
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper develops sampling-based methods to $(1+\varepsilon)$-approximate the number of four-cycles in arbitrary-order edge streams. Its main algorithm runs in two passes and stores only $\tilde{O}(\kappa m / \sqrt{T})$ edges, where $\kappa$ is degeneracy, $m$ the edge count, and $T$ the four-cycle count. This quantity is shown to be tight for any constant $\kappa$ because it nearly matches the known $\Omega(m / \sqrt{T})$ lower bound. A companion one-pass procedure remains accurate when four-cycles are not concentrated on a few vertices, edges or wedges, a property the authors note is typical in sparse social and collaboration networks. Experiments on real streams confirm that both procedures use far less space than prior methods while meeting the target accuracy, including on non-bipartite graphs.

What carries the argument

Induced-subgraph sampling performed in the streaming model, whose sample probabilities are bounded using a degeneracy ordering of the vertices.

What would settle it

Construct a constant-degeneracy graph whose four-cycle count $T$ is known exactly, run the two-pass algorithm with the claimed space, and check whether the returned estimate is within $(1+\varepsilon)$ of $T$ with high probability.

Watch

Extended reading notes

Core claim

By sampling induced subgraphs during the stream, the two-pass procedure obtains an unbiased estimator for the four-cycle count whose variance is controlled by the degeneracy ordering; the resulting space bound is therefore $\tilde{O}(\kappa m / \sqrt{T})$ and becomes $\tilde{O}(m / \sqrt{T})$ whenever $\kappa$ is constant.

Load-bearing premise

The sampling procedure for induced subgraphs can be implemented in the streaming model while correctly estimating the required probabilities without extra space that would violate the stated bounds.

Editorial extensions

If this is right

  • For any constant-degeneracy graph the space requirement simplifies to ilde{O}(m / \sqrt{T}).
  • The bound is asymptotically optimal up to polylog factors.
  • The one-pass variant succeeds on graphs where four-cycles are distributed across many wedges rather than concentrated.
  • Both algorithms remain correct on non-bipartite inputs such as social networks.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same sampling template could be reused for other constant-size subgraphs whose counts admit similar variance bounds under degeneracy.
  • If degeneracy can be maintained dynamically, the two-pass method might adapt to fully dynamic streams with comparable space.
  • On graphs whose degeneracy grows with m the space saving disappears, suggesting a natural threshold where one would switch to different techniques.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper studies (1+ε)-approximation of the number of 4-cycles in arbitrary-order edge streams. It presents a two-pass sampling-based algorithm using Õ(κ m / √T) space (κ = degeneracy, m = edges, T = 4-cycles) that matches the Ω(m/√T) lower bound up to lower-order terms for constant κ, plus a one-pass algorithm that works when 4-cycles are not highly concentrated on nodes/edges/wedges. Both are evaluated experimentally on real-world graphs, with the two-pass version outperforming prior methods.

Significance. If the space bounds and optimality claims hold, the work advances subgraph counting in the streaming model by giving near-optimal space for low-degeneracy graphs (common in social/collaboration networks) and a practical one-pass variant; the explicit matching to a known lower bound and experimental results on non-bipartite graphs are strengths.

minor comments (4)
  1. The abstract and introduction should explicitly state the precise sampling probabilities and how they are estimated in one or two passes without exceeding the space bound (cf. the weakest assumption noted in the reader's report).
  2. Clarify the definition of degeneracy κ used in the space bound and confirm it is the standard core-number definition; add a short paragraph relating it to arboricity or maximum core number.
  3. In the experimental section, report the observed concentration of 4-cycles (e.g., fraction per wedge) for each dataset to substantiate when the one-pass algorithm is expected to succeed.
  4. Add a brief comparison table of space usage versus prior streaming 4-cycle algorithms (e.g., those based on wedge sampling) on the same datasets.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary and recommendation of minor revision. We appreciate the recognition that our two-pass algorithm matches the known lower bound up to lower-order terms for constant degeneracy and that the one-pass variant is practical for common real-world graphs. No major comments were raised in the report.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity detected

full rationale

The paper's central claims consist of a two-pass streaming algorithm achieving Õ(κ m / √T) space for (1+ε)-approximating 4-cycles and a one-pass variant under additional structural assumptions, with the space bound expressed directly in terms of observable graph quantities (m, T, κ) and matched to an external known lower bound Ω(m/√T). No self-definitional reductions, fitted parameters renamed as predictions, or load-bearing self-citations appear in the provided abstract or claims; the derivation is self-contained against external benchmarks and does not reduce to its own inputs by construction.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

Based solely on the abstract; the work relies on standard probabilistic sampling arguments and the definition of graph degeneracy from prior literature. No new entities or fitted constants are introduced in the provided text.

assumptions (1)
  • standard math Standard concentration bounds (e.g., Chernoff or similar) apply to the induced-subgraph sampling estimator.
    Implicit foundation for any sampling-based approximation algorithm.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Four-Cycle Counting in Low-Degeneracy Graph Streams." pith.science (2026). https://pith.science/paper/NJBTDWWV

@misc{pith2026260617732,
  author       = {Pith},
  title        = {Pith review of: Four-Cycle Counting in Low-Degeneracy Graph Streams},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NJBTDWWV}},
  note         = {Machine review of arXiv:2606.17732}
}
abstract

We study the problem of $(1+\varepsilon)$-approximating the number of four-cycles in graphs given as arbitrary order edge streams. We propose two new algorithms based on sampling induced subgraphs. Our first contribution is a two-pass algorithm that uses $\widetilde{O}(\kappa m / \sqrt{T})$ space, where $m$ is the number of edges, $T$ is the number of four-cycles, and $\kappa$ is the graph's degeneracy. This algorithm improves upon existing theoretical bounds and is provably optimal for constant-degeneracy graphs, matching the known $\Omega(m/\sqrt{T})$ lower bound up to lower-order factors. Our second contribution is a one-pass algorithm that remains accurate when four-cycles are not highly concentrated around individual nodes, edges, or wedges; this structural property is common in sparse social and collaboration networks. We evaluate both algorithms on a variety of real-world graph streams. The two-pass algorithm consistently outperforms state-of-the-art methods, using substantially less space to achieve a desired accuracy. The one-pass algorithm is competitive when four-cycles are evenly distributed, matching our theoretical analysis. Unlike several recent works, our algorithms perform well even on non-bipartite graphs such as social networks.

Figures

Figures reproduced from arXiv: 2606.17732 by the authors.

Figure 1
Figure 1. Comparison of the algorithms’ running times on [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Relative error of the algorithms as a function of [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
Figure 3
Figure 3. Variance of the relative error of the algorithms on selected instances. Based on 100 estimates, the box spans from the [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Fraction |𝑆 |/|𝐺[𝑉𝑆 ] | of sampled edges over induced edges when running EIS on selected instances. For large graph sample sizes, EIS spends a lot more space on storing 𝐺[𝑉𝑆 ] compared to 𝑆, making the estimator less powerful. (2) On some instances EIS exhibits a large…
Figure 5
Figure 5. Figure 5: Sensitivity analysis of EISm on the parameter 𝑠. Increasing 𝑠 reduces the variance on most instances, as expected. On the very sparse dblp network increasing 𝑠 yields worse results, as explained in Section C.4. of the resulting estimates with EIS [PITH_FULL_IMAGE:figu…
Figure 6
Figure 6. Figure 6: Runtime Breakdown for EIS on selected instances for two values of #stored edges. For each network, we show the relative time spent during the first pass, the second pass and the postprocessing using ColoredChibaNishizeki [PITH_FULL_IMAGE:figures/full_fig_p016_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

39 extracted references · 4 canonical work pages

  1. [1]

    Link prediction via higher-order motif features

    Ghadeer Abuoda, Gianmarco De Francisci Morales, and Ashraf Aboulnaga. Link prediction via higher-order motif features. InECML/PKDD (1), volume 11906 of Lecture Notes in Computer Science, pages 412–429. Springer, 2019

    2019

  2. [2]

    Ahmed, Jennifer Neville, and Ramana Rao Kompella

    Nesreen K. Ahmed, Jennifer Neville, and Ramana Rao Kompella. Network sampling: From static to streaming graphs.ACM Trans. Knowl. Discov. Data, 8 (2):7:1–7:56, 2013

    2013

  3. [3]

    The space complexity of approxi- mating the frequency moments.J

    Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approxi- mating the frequency moments.J. Comput. Syst. Sci., 58(1):137–147, 1999

    1999

  4. [4]

    A simple sublinear-time algorithm for counting arbitrary subgraphs via edge sampling

    Sepehr Assadi, Michael Kapralov, and Sanjeev Khanna. A simple sublinear-time algorithm for counting arbitrary subgraphs via edge sampling. InITCS, volume 124 ofLIPIcs, pages 6:1–6:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019

    2019

  5. [5]

    Bera and Amit Chakrabarti

    Suman K. Bera and Amit Chakrabarti. Towards tighter space bounds for counting triangles and other substructures in graph streams. InSTACS, volume 66 ofLIPIcs, pages 11:1–11:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017

    2017

  6. [6]

    Bera and C

    Suman K. Bera and C. Seshadhri. How the degeneracy helps for triangle counting in graph streams. InPODS, pages 457–467. ACM, 2020

    2020

  7. [7]

    Mining large networks with subgraph counting

    Ilaria Bordino, Debora Donato, Aristides Gionis, and Stefano Leonardi. Mining large networks with subgraph counting. InICDM, pages 737–742. IEEE Computer Society, 2008

    2008

  8. [8]

    How hard is counting triangles in the streaming model? InICALP (1), volume 7965 ofLecture Notes in Computer Science, pages 244–254

    Vladimir Braverman, Rafail Ostrovsky, and Dan Vilenchik. How hard is counting triangles in the streaming model? InICALP (1), volume 7965 ofLecture Notes in Computer Science, pages 244–254. Springer, 2013

    2013

Show all 39 references
  1. [9]

    Larry Carter and Mark N. Wegman. Universal classes of hash functions.J. Comput. Syst. Sci., 18(2):143–154, 1979. Sebastian Lüderssen, Stefan Neumann, & Pan Peng

    1979

  2. [10]

    Stars, holes, or paths across your facebook friends: A graphlet-based characterization of many networks.Netw

    Raphaël Charbey and Christophe Prieur. Stars, holes, or paths across your facebook friends: A graphlet-based characterization of many networks.Netw. Sci., 7(4):476–497, 2019

    2019

  3. [11]

    Arboricity and subgraph listing algorithms

    Norishige Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms. SIAM J. Comput., 14(1):210–223, 1985

    1985

  4. [12]

    Listing all maximal cliques in large sparse real-world graphs.ACM J

    David Eppstein, Maarten Löffler, and Darren Strash. Listing all maximal cliques in large sparse real-world graphs.ACM J. Exp. Algorithmics, 18, 2013

    2013

  5. [13]

    Approximately counting subgraphs in data streams

    Hendrik Fichtenberger and Pan Peng. Approximately counting subgraphs in data streams. InPODS, pages 413–425. ACM, 2022

    2022

  6. [14]

    An optimal algorithm for triangle counting in the stream

    Rajesh Jayaram and John Kallaugher. An optimal algorithm for triangle counting in the stream. InAPPROX-RANDOM, volume 207 ofLIPIcs, pages 11:1–11:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021

    2021

  7. [15]

    The complexity of counting cycles in the adjacency list streaming model

    John Kallaugher, Andrew McGregor, Eric Price, and Sofya Vorotnikova. The complexity of counting cycles in the adjacency list streaming model. InPODS, pages 119–133. ACM, 2019

    2019

  8. [16]

    KONECT: the Koblenz network collection

    Jérôme Kunegis. KONECT: the Koblenz network collection. InWWW (Com- panion Volume), pages 1343–1350. International World Wide Web Conferences Steering Committee / ACM, 2013

    2013

  9. [17]

    Understanding money trails of suspicious activities in a cryptocurrency-based blockchain.CoRR, abs/2108.11818, 2021

    Banwari Lal, Rachit Agarwal, and Sandeep Kumar Shukla. Understanding money trails of suspicious activities in a cryptocurrency-based blockchain.CoRR, abs/2108.11818, 2021

    2021

  10. [18]

    Approximately counting butterflies in large bipartite graph streams.IEEE Trans

    Rundong Li, Pinghui Wang, Peng Jia, Xiangliang Zhang, Junzhou Zhao, Jing Tao, Ye Yuan, and Xiaohong Guan. Approximately counting butterflies in large bipartite graph streams.IEEE Trans. Knowl. Data Eng., 34(12):5621–5635, 2022

    2022

  11. [19]

    MASCOT: memory-efficient and accurate sampling for counting local triangles in graph streams

    Yongsub Lim and U Kang. MASCOT: memory-efficient and accurate sampling for counting local triangles in graph streams. InKDD, pages 685–694. ACM, 2015

    2015

  12. [20]

    Lind, Marta C

    Pedro G. Lind, Marta C. Gonzalez, and Hans J. Herrmann. Cycles and clustering in bipartite networks.Phys. Rev. E Stat. Nonlin. Soft Matter Phys., 72(5):056127, 2005

    2005

  13. [21]

    Four- Cycle Counting in Low-Degeneracy Graph Streams

    Sebastian Lüderssen, Stefan Neumann, and Pan Peng. Code for the paper “Four- Cycle Counting in Low-Degeneracy Graph Streams”. https://doi.org/10.5281/ zenodo.18089153, 2026

    2026

  14. [22]

    Near-optimal four-cycle counting in graph streams

    Sebastian Lüderssen, Stefan Neumann, and Pan Peng. Near-optimal four-cycle counting in graph streams. InSODA, pages 4285–4326. SIAM, 2026

    2026

  15. [23]

    Triangle and four cycle counting in the data stream model

    Andrew McGregor and Sofya Vorotnikova. Triangle and four cycle counting in the data stream model. InPODS, pages 445–456. ACM, 2020

    2020

  16. [24]

    Andrew McGregor, Sofya Vorotnikova, and Hoa T. Vu. Better algorithms for counting triangles in data streams. InPODS, pages 401–411. ACM, 2016

    2016

  17. [25]

    Counting butterflies over streaming bipartite graphs with duplicate edges.CoRR, abs/2412.11488, 2024

    Lingkai Meng, Long Yuan, Xuemin Lin, Chengjie Li, Kai Wang, and Wenjie Zhang. Counting butterflies over streaming bipartite graphs with duplicate edges.CoRR, abs/2412.11488, 2024

    2024 arXiv

  18. [26]

    Social network analytics for super- vised fraud detection in insurance.CoRR, abs/2009.08313, 2020

    María Óskarsdóttir, Waqas Ahmed, Katrien Antonio, Bart Baesens, Rémi Dendievel, Tom Donas, and Tom Reynkens. Social network analytics for super- vised fraud detection in insurance.CoRR, abs/2009.08313, 2020

    2009

  19. [27]

    Counting butterflies in fully dynamic bipartite graph streams

    Serafeim Papadias, Zoi Kaoudi, Varun Pandey, Jorge-Arnulfo Quiané-Ruiz, and Volker Markl. Counting butterflies in fully dynamic bipartite graph streams. In ICDE, pages 2917–2930. IEEE, 2024

    2024

  20. [28]

    Rossi and Nesreen K

    Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. InAAAI, 2015. URL http: //networkrepository.com

    2015

  21. [29]

    Kleinberg, and Aneesh Sharma

    Rahmtin Rotabi, Krishna Kamath, Jon M. Kleinberg, and Aneesh Sharma. De- tecting strong ties using network motifs. InWWW (Companion Volume), pages 983–992. ACM, 2017

    2017

  22. [30]

    FLEET: butterfly estimation from a bipartite graph stream

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

    2019

  23. [31]

    Tracking the trackers: A large-scale analysis of embedded web trackers

    Sebastian Schelter and Jérôme Kunegis. Tracking the trackers: A large-scale analysis of embedded web trackers. InICWSM, pages 679–682. AAAI Press, 2016

    2016

  24. [32]

    Tamer Özsu

    Aida Sheshbolouki and M. Tamer Özsu. sgrapp: Butterfly approximation in streaming graphs.ACM Trans. Knowl. Discov. Data, 16(4):76:1–76:43, 2022

    2022

  25. [33]

    Patterns and anomalies in k-cores of real-world graphs with applications.Knowl

    Kijung Shin, Tina Eliassi-Rad, and Christos Faloutsos. Patterns and anomalies in k-cores of real-world graphs with applications.Knowl. Inf. Syst., 54(3):677–710, 2018

    2018

  26. [34]

    Lee, Yanick Charette, George Iosifidis, and Nicholas A

    Shivkumar Vishnempet Shridhar, Selena T. Lee, Yanick Charette, George Iosifidis, and Nicholas A. Christakis. Network-cycle motif participation is associated with individual and collective wealth in Honduran villages.Scientific Reports, 15(1): 27680, 2025

    2025

  27. [35]

    Motifs in brain networks.PLoS Biology, 2(11):e369, 2004

    Olaf Sporns and Rolf Kötter. Motifs in brain networks.PLoS Biology, 2(11):e369, 2004

    2004

  28. [36]

    Trièst: Counting local and global triangles in fully-dynamic streams with fixed memory size

    Lorenzo De Stefani, Alessandro Epasto, Matteo Riondato, and Eli Upfal. Trièst: Counting local and global triangles in fully-dynamic streams with fixed memory size. InKDD, pages 825–834. ACM, 2016

    2016

  29. [37]

    FABLE: approximate butterfly counting in bipartite graph stream with duplicate edges

    Guozhang Sun, Yuhai Zhao, and Yuan Li. FABLE: approximate butterfly counting in bipartite graph stream with duplicate edges. InCIKM, pages 2158–2167. ACM, 2024

    2024

  30. [38]

    Random sampling with a reservoir.ACM Trans

    Jeffrey Scott Vitter. Random sampling with a reservoir.ACM Trans. Math. Softw., 11(1):37–57, 1985

    1985

  31. [39]

    Improved 3-pass algorithm for counting 4-cycles in arbitrary order streaming.CoRR, abs/2007.13466, 2020

    Sofya Vorotnikova. Improved 3-pass algorithm for counting 4-cycles in arbitrary order streaming.CoRR, abs/2007.13466, 2020. Four-Cycle Counting in Low-Degeneracy Graph Streams A Omitted content from Section 3 We present missing content from Section 3. Algorithm A.1 presents th...

    2007

Pith tools

Reviewed June 26, 2026 · model on record in the stance chip above.