{"id":"9b7f2b24-eea7-487b-bae2-80ae56422bc1","arxiv_id":"2507.08328","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The authors propose the (k,g)-core model and two algorithms, EPA and BCA, for finding and decomposing cohesive subhypergraphs based on pair co-occurrence.","lead":"Hypergraphs describe group interactions, and this paper defines a (k,g)-core that keeps nodes repeatedly appearing together in hyperedges, with algorithms for computing and decomposing such cores. The work targets online retrieval of cohesive subgraphs for applications such as team formation and market basket analysis.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 2's while-true loop cannot terminate: T.size() never reaches 0 because every node, including those with zero g-neighbours, is inserted into a bucket, so BCA never returns.","rationale":"The reader's weakest assumption targets the termination of Algorithm 2, and the full-text pseudocode confirms it: the only break condition, T.size()==0, is unreachable because bucket T[0] is created for every node with zero g-neighbours. This is a load-bearing defect because the Bucket-based Coreness Algorithm is a main contribution and the source of the paper's strongest scalability claim (AMiner in ~260,000 seconds). Without a termination condition, the algorithm as written never outputs anything, so the claimed time complexity and experimental numbers are unsupported. I additionally verified that the defect is not a mere typo in the break condition: even if one added an external bound g <= g*, the algorithm still fails because removed nodes are never removed from their buckets, causing stale entries to be re-processed in later k-iterations and to double-decrement counts of surviving nodes; a concrete small example (v--w with w also connected to x,y,z) shows the (3,1)-core becomes empty incorrectly. Thus the reader's rejection is well-founded, and the verdict should remain REJECT. No code or executable artifacts are provided to contradict this reading, and the paper itself does not specify any alternative stopping rule, so the concern lands firmly on the central claim.","tokens_in":21121,"tokens_out":16921,"duration_ms":176847,"concrete_test":"Transcribe Algorithm 2 exactly and run it on any non-empty hypergraph, e.g., the 11-node example of Figure 1 or simply a single hyperedge {a,b}. The outer 'while true' loop will iterate indefinitely, with g increasing beyond the maximum pairwise support, because T.size() never becomes 0: every node, including nodes with zero g-neighbours, is placed into a bucket. This directly settles that the published pseudocode does not terminate and therefore cannot implement the claimed O(g*|e*|D) decomposition.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 2 (BCA) as published cannot terminate. The outer loop at line 2 is 'while true', and its only break is line 11, 'if T.size() = 0 then break'. But T is populated at lines 5-10 by inserting every node v into bucket T[C[v]], where C[v]=|N_g(v)| can be 0. Thus for any non-empty hypergraph, T[0] is non-empty and T.size() >= 1 for every g, including g beyond the maximum pairwise support. The loop therefore increments g forever, never breaks, and never reaches the deduplication and return statements (lines 35-36). The claimed O(g*|e*|D) time and the reported 260,000-second AMiner run imply an unstated stopping rule (e.g., g <= g*), which is absent from the pseudocode; as written, the algorithm does not implement the decomposition. A second, independent flaw compounds this: removed nodes are never deleted from their own buckets (only their g-neighbours are moved), so stale bucket entries are re-enqueued in later k-iterations and can double-decrement the g-neighbour counts of surviving nodes, yielding incorrect D[(k,g)] even if a g bound is added.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript defines the (k,g)-core of a hypergraph as the maximal set of nodes in which each node has at least k g-neighbours, where a g-neighbour is a node sharing at least g hyperedges with it. Two algorithms are presented: the Efficient Peeling Algorithm (EPA) for a fixed (k,g)-core, claimed to run in O(|e*|D) time and O(|V|) space, and the Bucket-based Coreness Algorithm (BCA) for decomposing the hypergraph into all (k,g)-cores, claimed to run in O(g*|e*|D) time and O(min(k*,g*)|V|) space. The evaluation compares the model with six baselines on real-world and synthetic hypergraphs and includes a frequent-itemset case study.","tokens_in":21328,"tokens_out":15046,"duration_ms":154795,"significance":"If correct, the (k,g)-core would be a valuable cohesive-subhypergraph model because it captures pairwise co-occurrence strength rather than only individual node degree and admits a hierarchical containment structure. I credit the authors with a clear formal definition, a plausible peeling logic in EPA, a genuine memory saving over the naive neighbour-set representation, and experiments run with fixed user-chosen defaults rather than parameters fitted to the findings; the attribution to the earlier CIKM paper is appropriate. However, the decomposition algorithm BCA is the paper's central second contribution, and as written it cannot terminate and its bucket bookkeeping is inconsistent; the accompanying space bound is also not achieved. The BCA experiments therefore cannot be reproduced or interpreted, and the paper's main claims are currently unsupported.","major_comments":[{"comment":"Algorithm 2's outer 'while true' loop is unexitable on every non-empty hypergraph. Each node v is inserted into T[C[v]] at lines 8-10, and C[v]=|N_g(v)| is non-negative, so T.size() is at least one for every g. In particular, when g exceeds the maximum pairwise support, every node has C[v]=0 and is placed in bucket 0; line 11 never fires, the inner loop removes all nodes while assigning D[(k,g)]←∅ for each k, and g is incremented indefinitely. No upper bound on g is stated in Section 4.2, so lines 35-36 and the return are unreachable. This invalidates the O(g*|e*|D) time claim and makes the Section 5 EQ6 results (Figure 13), including the reported 260,000-second AMiner run, non-reproducible without an unstated stopping rule.","section":"Algorithm 2, lines 2-12"},{"comment":"The bucket structure is not cleaned when nodes are enqueued or removed. Line 19 enqueues all nodes in T[j] without deleting them from T, and lines 30-32 explicitly add a just-decremented node w to T[C[w]] even when line 29 has just enqueued w because C[w]<k. Hence removed or already-queued nodes remain in T; in later k-iterations they are re-enqueued, their g-neighbour sets are recomputed against the shrunken H, and surviving nodes can receive additional spurious decrements at line 27. The guard VQ.contain(w) at line 25 only excludes nodes currently in the queue, not nodes that have already been processed, so duplicate decrements and incorrect D[(k,g)] entries occur even if a valid upper bound on g were added.","section":"Algorithm 2, lines 19-32"},{"comment":"The claimed O(min(k*,g*)|V|) space bound applies only to the deduplicated output D' of Algorithm 3. As published, Algorithm 2 accumulates D[(k,g)]←H for every (k,g) pair in the inner loop (line 33) and then passes this full collection to Algorithm 3, so the peak memory of the pipeline is Ω(k*g*|V|) in the worst case. The argument that each node has at most min(k*,g*) coreness values describes the final antichain of maximal pairs, not the intermediate dictionary that Algorithm 2 constructs before deduplication.","section":"Section 4.2, Space Complexity"}],"minor_comments":[{"comment":"The names in Definitions 4 and 5 appear swapped: Definition 4 fixes k and varies g, so it defines the maximum co-occurrence g for a given k, while Definition 5 fixes g and varies k; the labels k-coreness and g-coreness should be exchanged (or the definitions rewritten).","section":"Section 4.1"},{"comment":"The phrase 'the maximal (k,g) pairs' is imprecise because a node can have several incomparable maximal pairs, as Table 2b shows; the definition should be formalized in terms of the antichain of maximal elements of the downward-closed membership region.","section":"Definition 6"},{"comment":"T is initialized with buildBuckets() and then populated again in lines 8-10; clarify whether buildBuckets() returns an empty bucket collection or precomputed buckets, and remove the redundant initialization.","section":"Algorithm 2, line 4"},{"comment":"The loop over getKeys(T) breaks at the first key j≥k, which is only correct if getKeys returns keys in ascending order; this ordering requirement should be stated explicitly or the loop should filter keys below k without relying on order.","section":"Algorithm 2, lines 15-18"},{"comment":"The symbols k*, g*, and D are overloaded: k* and g* are used as maximum parameter values but are not defined before Table 4, and D denotes both the total degree sum in the complexity expressions and the decomposition map in Algorithm 2; distinct notation would avoid confusion.","section":"Table 4 and Section 4.2"}],"recommendation":"reject","confidential_remarks":"To the editor: BCA is not a minor presentation problem; the pseudocode cannot terminate and the space analysis is inconsistent with the algorithm's own data structures. A revision would require a new algorithm and re-running all BCA experiments, so I do not see this as a minor-revision fix. The abstract also promises an online indexing structure, but the body delivers a batch decomposition; if a revised version is considered, this mismatch should be addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The (k,g)-core model is prior work from the authors' CIKM 2023 short paper, and they say so plainly. The genuinely new pieces are the EPA peeling algorithm and the BCA decomposition. EPA looks sound to me: it tracks only g-neighbour counts, recomputes the neighbour map on deletion, and its O(|e*|D) time with O(|V|) space is a real improvement over the naive explicit-set version. The memory comparison in Appendix B is believable, and the experiments, while lacking code or data, at least cover a wide range of datasets.\n\nThe problem is BCA. Algorithm 2's outer loop is 'while true', and its only break is T.size() = 0. But T is populated with every node, including those with zero g-neighbours, so for any non-empty hypergraph T.size() >= 1 forever. The loop increments g and resets H to V each iteration, so it never reaches the deduplication and return. The reported 260,000-second AMiner run implies some unstated stopping rule, but the published pseudocode does not implement the claimed decomposition. There is also a second, independent bug: removed nodes are never taken out of their own buckets, so in later k-iterations they get re-enqueued and decrement the counts of surviving nodes twice. That corrupts D[(k,g)] even if a g-bound were added.\n\nThe space analysis has a similar problem. The paper claims O(min(k*,g*)|V|) space, but D stores a node set for every (k,g) pair before deduplication, which is O(k*g*|V|) in the worst case. They seem to be counting only the final coreness values, not the intermediate storage the algorithm actually uses.\n\nThe abstract promises an 'efficient indexing structure' for online retrieval, but no such structure appears anywhere in the body; the conclusion even lists a space-efficient indexing structure as future work. That is a mismatch between abstract and content.\n\nSo: the model is motivationally fine, EPA is worth keeping, but BCA—one of the two headline contributions—is broken in its current form. This is a fixable set of issues in principle, but as submitted the decomposition results are unsupported. I would not desk-reject; the underlying ideas deserve referee time. But I would expect major revision: fix the BCA termination condition, remove stale bucket entries, correct the space bound, and either add the indexing structure or drop that claim from the abstract. No code or data is provided, which makes the scalability claims harder to verify.","headline":"The EPA is a plausible memory-efficient peeling routine, but the BCA decomposition algorithm as written cannot terminate — the central new result doesn't hold up.","tokens_in":700,"tokens_out":1628,"would_cite":false,"duration_ms":50348,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C65","05C82","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that the $(k,g)$-core — the maximal node set in which every node has at least $k$ partners it co-occurs with in at least $g$ hyperedges — can be computed with a memory-lean peeling algorithm and decomposed into the full…","keywords":["hypergraph","(k,g)-core","cohesive subgraph","core decomposition","g-neighbour","support","peeling algorithm","bucket-based algorithm"],"falsifier":"Execute Algorithm 2 exactly as printed on any non-empty hypergraph, such as a single hyperedge $\\{a,b,c\\}$, and let the parameter $g$ exceed the largest support (for this graph, 1). The bucket table never becomes empty because every node is still placed in bucket 0, so the condition $T.size()=0$ at line 11 never fires and the outer loop never terminates; this directly contradicts the claimed $O(g^*|e^*|\\cdot D)$ completion time.","tokens_in":20905,"feed_emoji":"🕸️","tokens_out":8233,"duration_ms":89245,"temperature":0.7,"pith_summary":"The paper proposes the $(k,g)$-core, a cohesive-subhypergraph model in which a node must keep at least $k$ neighbours that appear with it in at least $g$ shared hyperedges (its $g$-neighbours). The central claim is that a peeling algorithm that stores only one count per node computes this core in $O(|e^*|\\cdot D)$ time and $O(|V|)$ space, where $D$ is the sum of node degrees and $|e^*|$ the largest hyperedge size, and that a bucket-based variant returns the whole hierarchy of $(k,g)$-cores in $O(g^*|e^*|\\cdot D)$ time. If correct, this gives practitioners an index that answers a query for the strongly co-occurring group at thresholds $k,g$ without re-traversing the hypergraph. The motivation is that degree-only cores admit members who rarely work together, whereas co-occurrence-based cores recover subgroups whose members repeatedly appear in the same hyperedges.","feed_headline":"Bucket-based algorithm returns every (k,g)-core","feed_subtitle":"Group-discovery index answers any co-occurrence threshold in near-linear time, tested on 27-million-node graphs","key_machinery":"The load-bearing object is the $(k,g)$-core of Definition 3, built from the support $s(u,v)$ — the number of hyperedges containing both $u$ and $v$ — and the induced $g$-neighbour set $N_g(v)$. The peeling invariant is that removing a node can reduce the $g$-neighbour count only of its current $g$-neighbours, so updates stay local; the bucket structure groups nodes by current count so the next nodes falling below $k$ are found without rescanning the whole hypergraph. This local-decrement property is what carries both the $O(|e^*|\\cdot D)$ time bound and the $O(|V|)$ memory bound.","core_discovery":"Definition 3 defines the $(k,g)$-core as the maximal set of nodes such that, inside the induced subhypergraph, each node has at least $k$ $g$-neighbours, where $g$-neighbours are nodes sharing at least $g$ hyperedges. The paper argues this object is unique and nested: increasing $k$ or $g$ only shrinks the core. EPA computes a single core by initialising each node's $g$-neighbour count, repeatedly removing nodes with count below $k$, and decrementing only the counts of their $g$-neighbours; because it stores counts rather than neighbour sets, it uses $O(|V|)$ space. BCA repeats this peeling under buckets indexed by count, for increasing $k$ within each $g$, then deduplicates overlapping cores to output each node's maximal $(k,g)$ pairs. The authors report that on the AMiner hypergraph with over 27 million nodes, BCA finished in about 260,000 seconds.","pith_inferences":["A practical implementation of BCA needs a missing stopping rule for $g$; the printed algorithm has no break once $g$ exceeds the maximum support, so the reported runtimes implicitly depend on a bound the pseudocode does not state.","Because cores shrink monotonically in both parameters, the full decomposition doubles as a parameter-free exploration index: a user could find the largest $k$ and $g$ at which a node or group survives without running a separate computation for each pair.","The same support-and-peel recipe should extend to weighted or temporal hypergraphs, where co-occurrence strength is a weighted or recency-discounted count, as long as removals still only decrement local neighbour counts.","The pair-based support definition may underweight groups whose cohesion is carried by larger joint memberships, such as a trio that always appears together but has low pairwise overlap, so a hyperedge-level overlap variant would be a natural testable extension."],"forward_implications":["For a fixed threshold pair $(k,g)$, EPA returns the unique maximal $(k,g)$-core in $O(|e^*|\\cdot D)$ time with $O(|V|)$ memory, so the earlier quadratic neighbour-pair storage is no longer needed.","BCA enumerates every $(k,g)$-core and, after deduplication, reports the maximal $(k,g)$ pairs per node in $O(g^*|e^*|\\cdot D)$ time, giving an index that answers online $(k,g)$ queries without traversing the hypergraph.","Containment means raising either threshold yields a subset of the current core, so the decomposition provides a monotone hierarchy of cohesion levels.","On the largest tested dataset (AMiner, over 27 million nodes), BCA completed in roughly 260,000 seconds, which the authors read as evidence the decomposition can scale to industry-size hypergraphs."],"supporting_citations":[{"why":"Prior short paper that introduced the $(k,g)$-core concept and the naive greedy algorithm this work extends.","marker":"[23]"},{"why":"Classic $O(m)$ core-decomposition algorithm whose bucket-peeling discipline BCA generalises to the two-parameter setting.","marker":"[4]"},{"why":"Supplies the nbr-$k$-core and $(k,d)$-core baselines and several real-world datasets used in the experiments.","marker":"[3]"},{"why":"Defines the $k$-hypercore, the first hypergraph core model and a baseline for cohesion comparison.","marker":"[26]"},{"why":"Defines the $(k,t)$-hypercore with fractional thresholds, another baseline model compared in the experiments.","marker":"[9]"},{"why":"Defines clique-core, a unipartite baseline obtained by converting hypergraphs to graphs.","marker":"[5]"},{"why":"Defines the $(\\alpha,\\beta)$-core, a bipartite baseline model used for comparison.","marker":"[14]"},{"why":"Provides the H-ABCD hypergraph generator used to create synthetic datasets for the scalability tests.","marker":"[22]"}],"fun_headline_variants":["Hypergraph cores on demand: fast index answers any (k,g)","Online (k,g)-core retrieval: index beats full traversal","Scalable (k,g)-core decomposition for 27M-node hypergraphs","Indexed peeling answers (k,g)-core queries in near-linear time","Every (k,g)-core at once: bucket-based peeling for hypergraphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The central claim rests on the assumption that the decomposition loop has a stopping point: the published pseudocode of Algorithm 2 has no condition that ends the search once $g$ exceeds the largest co-occurrence count, so without an unstated upper bound the algorithm runs forever rather than returning all $(k,g)$-cores.","fun_headline_variants_meta":{"raw":{"variants":["Hypergraph cores on demand: fast index answers any (k,g)","Online (k,g)-core retrieval: index beats full traversal","Scalable (k,g)-core decomposition for 27M-node hypergraphs","Indexed peeling answers (k,g)-core queries in near-linear time","Every (k,g)-core at once: bucket-based peeling for hypergraphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000946,"raw_usage":{"total_tokens":4009,"prompt_tokens":885,"completion_tokens":3124,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":501,"completion_tokens_details":{"reasoning_tokens":3029}},"tokens_in":501,"tokens_out":3124,"duration_ms":25230,"temperature":1.0,"reasoning_tokens":3029,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T18:24:33.729238+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Execute Algorithm 2 exactly as printed on any non-empty hypergraph, such as a single hyperedge $\\{a,b,c\\}$, and let the parameter $g$ exceed the largest support (for this graph, 1). The bucket table never becomes empty because every node is still placed in bucket 0, so the condition $T.size()=0$ at line 11 never fires and the outer loop never terminates; this directly contradicts the claimed $O(g^*|e^*|\\cdot D)$ completion time.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Prior short paper that introduced the $(k,g)$-core concept and the naive greedy algorithm this work extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the $k$-hypercore, the first hypergraph core model and a baseline for cohesion comparison."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the $(k,t)$-hypercore with fractional thresholds, another baseline model compared in the experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines clique-core, a unipartite baseline obtained by converting hypergraphs to graphs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the $(\\alpha,\\beta)$-core, a bipartite baseline model used for comparison."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the H-ABCD hypergraph generator used to create synthetic datasets for the scalability tests."}],"review_version":1}