{"id":"3bc09fb4-9f0b-4dbe-a05d-be10dd848319","arxiv_id":"2606.17732","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Two new sampling algorithms for four-cycle counting in graph streams achieve space bounds of \tilde O(κ m / sqrt(T)) in two passes (optimal for constant degeneracy) and a competitive one-pass version when cycles are not concentrated.","lead":"The paper presents two subgraph-sampling algorithms for (1+ε)-approximating four-cycle counts in arbitrary-order edge streams. A smart generalist might read it to see how degeneracy and cycle distribution affect memory use when analyzing massive networks.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"Reader's weakest assumption matches the only plausible point of failure for the space bound in the streaming model. Since the full text was not supplied for detailed verification of the sampling construction, no stronger or different concern can be raised.","tokens_in":1716,"tokens_out":280,"duration_ms":17005,"concrete_test":"Locate the two-pass algorithm description (likely §3) and check whether the data structures for sampling induced subgraphs and estimating inclusion probabilities fit inside the stated Õ(κ m / √T) space bound with no hidden per-edge or per-wedge storage; if they do, the space claim holds.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is a two-pass streaming algorithm achieving Õ(κ m / √T) space for (1+ε)-approximating 4-cycles while matching the Ω(m/√T) lower bound for constant κ. The reader's weakest assumption correctly flags the sampling implementation, but without access to the full proofs or pseudocode in this pass, no internal inconsistency or unsupported step can be isolated. The abstract states the space bound and optimality result directly; any gap would be in the (unseen) analysis of probability estimation or degeneracy-based sampling, but this is not yet demonstrably load-bearing.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","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.","tokens_in":1843,"tokens_out":408,"duration_ms":13899,"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.","major_comments":[],"minor_comments":[{"comment":"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).","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"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.","responses":[],"tokens_in":1260,"tokens_out":78,"duration_ms":11570,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The paper's main result is a two-pass algorithm that (1+ε)-approximates the number of 4-cycles in an arbitrary-order edge stream using Õ(κ m / √T) space. For constant-degeneracy graphs this matches the Ω(m/√T) lower bound up to lower-order factors. They also present a one-pass algorithm that stays accurate when 4-cycles are not heavily concentrated on individual nodes, edges, or wedges.\n\nWhat is new is the explicit dependence on degeneracy κ to improve the space bound over prior streaming work, along with the structural condition that enables the one-pass case. The experiments on real-world graphs show the two-pass version uses substantially less space than existing methods for the same accuracy and works on non-bipartite graphs.\n\nThe sampling of induced subgraphs is the core technique, and the abstract claims it fits inside the stated space. The one-pass version is limited to graphs where the distribution condition holds, which the authors note is common in social and collaboration networks but is not universal.\n\nThis is aimed at people working on streaming algorithms for graph statistics or degeneracy-based methods. A reader who needs practical space savings for cycle counting in streams would get concrete value from the bounds and the empirical comparison.\n\nThe matching lower bound and the reported space improvements are concrete enough that the paper deserves a serious referee.","headline":"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.","tokens_in":2270,"tokens_out":361,"would_cite":false,"duration_ms":21951,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"A two-pass streaming algorithm approximates four-cycles using space \tilde{O}(\\kappa m / \\sqrt{T}), matching lower bounds for constant-degeneracy graphs.","keywords":["four-cycle counting","graph streams","degeneracy","streaming algorithms","subgraph sampling","approximation algorithms","social networks"],"falsifier":"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.","tokens_in":2631,"feed_emoji":"📊","tokens_out":694,"duration_ms":22254,"temperature":0.7,"texified_at":"2026-08-05T21:09:30.131448+00:00","pith_summary":"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.","texify_model":"deepseek-v4-flash","texify_usage":{"total_tokens":2824,"prompt_tokens":480,"completion_tokens":2344,"prompt_tokens_details":{"cached_tokens":0},"prompt_cache_hit_tokens":0,"prompt_cache_miss_tokens":480,"completion_tokens_details":{"reasoning_tokens":1947}},"feed_headline":"Two-pass algorithm approximates four-cycles with O(κ m / sqrt(T)) space","feed_subtitle":"Matches known lower bound for constant-degeneracy graphs and stays accurate on real social networks.","key_machinery":"Induced-subgraph sampling performed in the streaming model, whose sample probabilities are bounded using a degeneracy ordering of the vertices.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["For any constant-degeneracy graph the space requirement simplifies to \tilde{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."],"fun_headline_variants":["Two-pass sampling approximates four-cycles in O(κ m / sqrt(T)) space","Induced subgraphs yield O(κ m / sqrt(T)) space for four-cycles","O(κ m / sqrt(T)) space bounds four-cycle approximation in streams","Two-pass algorithm matches lower bound for four-cycles at O(κ m / sqrt(T))","Low-degeneracy streams allow four-cycle counting in O(κ m / sqrt(T)) space"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Two-pass sampling approximates four-cycles in O(κ m / sqrt(T)) space","Induced subgraphs yield O(κ m / sqrt(T)) space for four-cycles","O(κ m / sqrt(T)) space bounds four-cycle approximation in streams","Two-pass algorithm matches lower bound for four-cycles at O(κ m / sqrt(T))","Low-degeneracy streams allow four-cycle counting in O(κ m / sqrt(T)) space"]},"model":"grok-4.3","cost_usd":0.00452,"raw_usage":{"total_tokens":2247,"prompt_tokens":663,"num_sources_used":0,"completion_tokens":112,"cost_in_usd_ticks":45199500,"prompt_tokens_details":{"text_tokens":663,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1472,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":663,"tokens_out":112,"duration_ms":12692,"temperature":1.0,"reasoning_tokens":1472,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-26T22:13:02.272945+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"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.","supporting_citations":[],"review_version":1}