REVIEW 3 major objections 5 minor 45 references
Uncovering High-Order Cohesive Structures: Efficient (k,g)-Core Computation and Decomposition for Large Hypergraphs
T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read 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…
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [Algorithm 2, lines 2-12] 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.
- [Algorithm 2, lines 19-32] 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 4.2, Space Complexity] 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.
minor comments (5)
- [Section 4.1] 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).
- [Definition 6] 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.
- [Algorithm 2, line 4] 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.
- [Algorithm 2, lines 15-18] 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.
- [Table 4 and Section 4.2] 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.
Circularity Check
No significant circularity: the (k,g)-core is formally defined in the paper, algorithms are constructive, and self-citations are attribution rather than load-bearing evidence.
full rationale
The paper's derivation chain is self-contained. Definitions 1-3 formally define support, g-neighbours, and the (k,g)-core; Properties 1-2 are immediate from the definition, and the paper says the proof is omitted because it follows directly. EPA and BCA are constructive algorithms with stated complexity analyses rather than fitted models. No parameter is fitted to the target result: the default k=5 and g=5 are user-chosen, and the experiments vary them as inputs. The citation [23] points to the authors' earlier CIKM paper that first introduced the (k,g)-core concept, but the present paper restates the full definition and explicitly discloses the extension, so the self-citation is prior attribution, not a load-bearing circular justification. The empirical BCA runtime claim on AMiner is a reported measurement, not a prediction derived from a fit. The reviewer-identified nontermination issue in Algorithm 2's while-true loop is a pseudocode correctness concern, not a circularity of the derivation. Overall, no claimed result reduces by construction to its inputs, and no uniqueness or ansatz is imported solely from the authors' prior work.
Assumptions & free parameters
assumptions (1)
- standard math Iterative removal of nodes with fewer than k remaining g-neighbours yields the unique maximal (k,g)-core.
Cite this review
Pith. "Pith review of Uncovering High-Order Cohesive Structures: Efficient (k,g)-Core Computation and Decomposition for Large Hypergraphs." pith.science (2026). https://pith.science/paper/ACVBTQET
@misc{pith2026250708328,
author = {Pith},
title = {Pith review of: Uncovering High-Order Cohesive Structures: Efficient (k,g)-Core Computation and Decomposition for Large Hypergraphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/ACVBTQET}},
note = {Machine review of arXiv:2507.08328}
}
read the original abstract
Hypergraphs, increasingly utilised to model complex and diverse relationships in modern networks, have gained significant attention for representing intricate higher-order interactions. Among various challenges, cohesive subgraph discovery is one of the fundamental problems and offers deep insights into these structures, yet the task of selecting appropriate parameters is an open question. To address this question, we aim to design an efficient indexing structure to retrieve cohesive subgraphs in an online manner. The main idea is to enable the discovery of corresponding structures within a reasonable time without the need for exhaustive graph traversals. Our method enables faster and more effective retrieval of cohesive structures, which supports decision-making in applications that require online analysis of large-scale hypergraphs. Through extensive experiments on real-world networks, we demonstrate the superiority of our proposed indexing technique.
Figures
Figures from the paper (11 more)
Reference graph
Works this paper leans on
-
[1]
Rakesh Agrawal, Ramakrishnan Srikant, et al. 1994. Fast algorithms for mining association rules. In Proceedings of the VLDB Endowment, V ol. 1215. Santiago, 487–499
work page 1994
-
[2]
Ilya Amburg, Nate Veldt, and Austin R. Benson. 2020. Clustering in graphs and hypergraphs with categorical edge labels. In Proceedings of the Web Conference
work page 2020
-
[3]
Naheed Anjum Arafat, Arijit Khan, Arpit Kumar Rai, and Bishwamittra Ghosh
-
[4]
Vladimir Batagelj and Matjaz Zaversnik. 2003. An o (m) algorithm for cores decomposition of networks. arXiv preprint cs/0310049 (2003)
arXiv 2003
-
[5]
Vladimir Batagelj and Matjaž Zaveršnik. 2011. Fast algorithms for determining (generalized) core groups in social networks. Advances in Data Analysis and Classification 5, 2 (2011), 129–145
work page 2011
-
[6]
Austin R Benson, Rediet Abebe, Michael T Schaub, Ali Jadbabaie, and Jon Kleinberg. 2018. Simplicial closure and higher-order link prediction. Proceedings of the National Academy of Sciences 115, 48 (2018), E11221–E11230
work page 2018
-
[7]
Austin R Benson, Ravi Kumar, and Andrew Tomkins. 2018. A discrete choice model for subset selection. In Proceedings of the ACM International Conference on Web Search and Data Mining. Association for Computing Machinery, New York, NY , United States, 37–45
work page 2018
-
[8]
Claude Berge. 1984. Hypergraphs: combinatorics of finite sets. V ol. 45. Elsevier
work page 1984
Show all 45 references
-
[9]
Fanchen Bu, Geon Lee, and Kijung Shin. 2023. Hypercore decomposition for non- fragile hyperedges: concepts, algorithms, observations, and applications. Data Mining and Knowledge Discovery 37, 6 (2023), 2389–2437
2023
-
[10]
Eunjoon Cho, Seth A Myers, and Jure Leskovec. 2011. Friendship and mobility: user movement in location-based social networks. In Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery, New York, NY , USA, 1082–1090
2011
-
[11]
Deming Chu, Fan Zhang, Xuemin Lin, Wenjie Zhang, Ying Zhang, Yinglong Xia, and Chenyi Zhang. 2020. Finding the best𝑘 in core decomposition: A time and space optimal solution. In IEEE International Conference on Data Engineering. 685–696
2020
-
[12]
Ural Gökay Çiçekli and ˙Inanç Kabasakal. 2021. Market basket analysis of basket data with demographics: a case study in e-retailing. Alphanumeric Journal 9, 1 (2021), 1–12
2021
-
[13]
Jonathan Cohen. 2008. Trusses: Cohesive subgraphs for social network analysis. National security agency technical report 16, 3.1 (2008), 1–29
2008
-
[14]
Danhao Ding, Hui Li, Zhipeng Huang, and Nikos Mamoulis. 2017. Efficient fault-tolerant group recommendation using alpha-beta-core. In Proceedings of the ACM International Conference on Information and Knowledge Management. Association for Computing Machinery, New York, NY , US...
2017
-
[15]
Yue Gao, Yifan Feng, Shuyi Ji, and Rongrong Ji. 2022. Hgnn+: General hyper- graph neural networks. IEEE Transactions on Pattern Analysis and Machine Intelligence 45, 3 (2022), 3181–3199
2022
-
[16]
Michelle Girvan and Mark EJ Newman. 2002. Community structure in social and biological networks. Proceedings of the national academy of sciences 99, 12 (2002), 7821–7826
2002
-
[17]
Priya Govindan, Chenghong Wang, Chumeng Xu, Hongyu Duan, and Sucheta Soundarajan. 2017. The k-peak decomposition: Mapping the global structure of graphs. In Proceedings of the 26th International Conference on World Wide Web. International World Wide Web Conferences Steering Co...
2017
-
[18]
Stephan Günnemann, Ines Färber, Sebastian Raubach, and Thomas Seidl. 2013. Spectral subspace clustering for graphs with feature vectors. InIEEE International Conference on Data Mining. IEEE, IEEE, 231–240
2013
-
[19]
Frank Harary and Robert Z Norman. 1953. Graph theory as a mathematical model in social science. (1953)
1953
-
[20]
Jin Huang, Rui Zhang, and Jeffrey Xu Yu. 2015. Scalable hypergraph learning and processing. In IEEE International Conference on Data Mining. IEEE Computer Society, Los Alamitos, CA, USA, 775–780
2015
-
[21]
William Jack, Adam Ray, and Tavneet Suri. 2013. Transaction networks: Evidence from mobile money in Kenya. American Economic Review 103, 3 (2013), 356– 361
2013
-
[22]
Bogumił Kami ´nski, Paweł Prałat, and François Théberge. 2023. Hypergraph Artificial Benchmark for Community Detection (h–ABCD). Journal of Complex Networks 11, 4 (2023)
2023
-
[23]
Dahee Kim, Junghoon Kim, Sungsu Lim, and Hyun Ji Jeong. 2023. Exploring Cohesive Subgraphs in Hypergraphs: The(𝑘,𝑔)-core Approach. In Proceedings of the ACM International Conference on Information and Knowledge Management. Association for Computing Machinery, New York, NY , US...
2023
-
[24]
Dahee Kim, Song Kim, Jeongseon Kim, Junghoon Kim, Kaiyu Feng, Sungsu Lim, and Jungeun Kim. 2024. Experimental Analysis and Evaluation of Cohesive Subgraph Discovery. Information Sciences 672 (2024), 120664
2024
-
[25]
Song Kim, Junghoon Kim, Susik Yoon, and Jungeun Kim. 2024. Flexi-clique: Exploring Flexible and Sub-linear Clique Structures. In Proceedings of the ACM International Conference on Information and Knowledge Management . 3832– 3836
2024
-
[26]
Ming Leng, Lingyu Sun, Ji-nian Bian, and Yuchun Ma. 2013. An o(m) algorithm for cores decomposition of undirected hypergraph. Journal of Chinese Computer Systems 34, 11 (2013), 2568–2573
2013
-
[27]
Cheng-Te Li and Man-Kwan Shan. 2010. Team formation for generalized tasks in expertise social networks. In IEEE second international conference on social computing. IEEE, 9–16
2010
-
[28]
Mengran Li, Yong Zhang, Xiaoyong Li, Yuchen Zhang, and Baocai Yin. 2023. Hypergraph transformer neural networks. ACM Transactions on Knowledge Discovery from Data 17, 5 (2023), 1–22
2023
-
[29]
Qingyuan Linghu, Fan Zhang, Xuemin Lin, Wenjie Zhang, and Ying Zhang. 2020. Global reinforcement of social networks: The anchored coreness problem. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 2211–2226. Uncovering High-Order Cohesive Struct...
2020
-
[30]
Fragkiskos D Malliaros, Christos Giatsidis, Apostolos N Papadopoulos, and Michalis Vazirgiannis. 2020. The core decomposition of networks: Theory, al- gorithms and applications. Proceedings of the VLDB Endowment 29, 1 (2020), 61–92
2020
-
[31]
Oliver Mason and Mark Verwoerd. 2007. Graph theory and networks in biology. IET systems biology 1, 2 (2007), 89–119
2007
-
[32]
Robert J Mokken et al. 1979. Cliques, clubs and clans. Quality & Quantity 13, 2 (1979), 161–173
1979
-
[33]
James Moody and Douglas R White. 2002. Social cohesion and embeddedness: A hierarchical conception of social groups. Sociological Methodology 68, 1 (2002), 365–368
2002
-
[34]
Jianmo Ni, Jiacheng Li, and Julian McAuley. 2019. Justifying Recommendations using Distantly-Labeled Reviews and Fine-Grained Aspects. In Proceedings of the Conference on Empirical Methods in Natural Language Processing and the International Joint Conference on Natural Languag...
2019
-
[35]
Saeed Salem, Rami Alroobi, Syed Ahmed, and Mohammad Hossain. 2012. Dis- covering maximal cohesive subgraphs and patterns from attributed biological networks. In IEEE International Conference on Bioinformatics and Biomedicine Workshops. IEEE, IEEE, 203–210
2012
-
[36]
Jeffri Prayitno Bangkit Saputra, Silvia Anggun Rahayu, and Taqwa Hariguna
-
[37]
Stephen B Seidman. 1983. Network structure and minimum degree. Social networks 5, 3 (1983), 269–287
1983
-
[38]
Journal of Applied Data Sciences 4, 1 (2023), 38–49
Market basket analysis using FP-growth algorithm to design marketing strategy by determining consumer purchasing patterns. Journal of Applied Data Sciences 4, 1 (2023), 38–49
2023
-
[39]
Tianhao Wang, Yong Zhang, Francis YL Chin, Hing-Fung Ting, Yung H Tsin, and Sheung-Hung Poon. 2015. A simple algorithm for finding all k-edge-connected components. PLOS One 10, 9 (2015), e0136264
2015
-
[40]
Yüksel Akay Ünvan. 2021. Market basket analysis with association rules. Com- munications in Statistics-Theory and Methods 50, 7 (2021), 1615–1628
2021
-
[41]
Barry Wellman. 1983. Network analysis: Some basic principles. Sociological theory (1983), 155–200
1983
-
[42]
Stanley Wasserman, Katherine Faust, et al. 1994. Social network analysis: Meth- ods and applications. Cambridge university press
1994
-
[43]
Fan Zhang, Qingyuan Linghu, Jiadong Xie, Kai Wang, Xuemin Lin, and Wenjie Zhang. 2023. Quantifying Node Importance over Network Structural Stability. In Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 3217–3228. Conference acronym ’XX, June 03–...
2023
-
[44]
Xin Xia, Hongzhi Yin, Junliang Yu, Qinyong Wang, Lizhen Cui, and Xiangliang Zhang. 2021. Self-supervised hypergraph convolutional networks for session- based recommendation. In Proceedings of the AAAI Conference on Artificial Intelligence, V ol. 35. 4503–4511
2021
-
[2023]
Proceedings of the VLDB Endowment 16, 9 (2023), 2061–2074
Neighborhood-Based Hypergraph Core Decomposition. Proceedings of the VLDB Endowment 16, 9 (2023), 2061–2074
2023
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.