REVIEW 3 major objections 5 minor 2 cited by
Exploring the Non-uniqueness of Node Co-occurrence Matrices of Hypergraphs
T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read The paper claims that the node co-occurrence projection of a hypergraph is usually non-unique—many distinct hypergraphs, called twins, share the same projection—and that the complete set of twins can be enumerated by a factor-graph tree…
desk verdict TwinSearch is a genuinely new enumeration tool for a known problem, but the printed pseudocode's residual-variable error breaks completeness; the paper deserves review with corrections. 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 carrying object is the factor graph of the projection: a bipartite graph whose one side contains one node per nonzero pair $(u,v)$ in $W$ and whose other side contains one node per clique of any size in $W$, with an edge from a pair-node to a clique-node when the pair is contained in the clique. Each subgraph of the factor graph corresponds to a partial hypergraph, and a hypergraph consistent with $W$ is a subgraph in which every pair-node has exactly $W_{uv}$ incident clique-nodes. TwinSearch is a tree search over such subgraphs, always choosing an unsatisfied pair with residual $R = W - W'$ and extending by combinations of cliques from its adjacency list; constraints such as $k$-uniformity are encoded by pruning the clique side. The tree's worst-case width at a pair $e$ is the binomial coefficient $\binom{|\eta_e|}{W_e}$, giving a worst-case tree size bound of the product over pairs, and every partial hypergraph is claimed to be reachable exactly once, which is what makes the enumeration complete and parallelizable.
What would settle it
Run TwinSearch on every projection from $G_3(6,m)$ and compare its output with a brute-force enumeration of all simple hypergraphs on six nodes: any projection whose returned twin set omits a valid hypergraph, or includes one whose projection differs, would refute the completeness claim. A sharper test is the printed Algorithm 1 directly: its line 17 replaces the residual $R_e$ with $W'_e$ when choosing combination sizes, so an implementation that follows the pseudocode literally should fail on small inputs, and a corrected implementation must be verified against brute force before the numerical results can be taken as exhaustive.
Extended reading notes
Core claim
The core claim is that the labeled node co-occurrence projection of a hypergraph is typically not invertible, and that the full preimage—the set of twin hypergraphs—can be computed, not just sampled. Concretely, for every projection $W$ the paper defines the twin set as all simple hypergraphs whose co-occurrence matrix equals $W$, with refinements fixing the number of hyperedges $m$, the hyperedge size distribution (e.g., $k$-uniformity), or the diagonal hyperdegrees. TwinSearch enumerates this set by representing $W$ as a factor graph and searching over subgraphs whose edge-node degrees reproduce $W$, and the paper reports exhaustive results for the random model $G_3(6,m)$: 3-uniform twins exceed the number of projections by up to 15% around $m = 10$, and non-uniform twins are orders of magnitude more numerous and more diverse in size distribution and isomorphism class. The numerical study also shows that pairs of Gram Mates appear among twins and that even after fixing $m$ and the diagonal, hundreds of hypergraphs can remain, so the projection alone does not determine the higher-order interaction structure.
Load-bearing premise
The load-bearing premise is that the factor-graph tree search is complete and duplicate-free—every hypergraph that realizes $W$ is reached as a leaf and no partial hypergraph is missed—yet the paper asserts rather than proves this, and the printed pseudocode conflicts with the description at the step where the next combinations are chosen, so the correctness of the implementation is an assumption, not a demonstrated fact.
Editorial extensions
If this is right
- For 3-uniform hypergraphs on six nodes, projections are unique outside the range roughly $m = 4$ to $17$ and non-unique inside it, with twins peaking at 15% above the number of projections around $m = 10$.
- Allowing hyperedges of any size magnifies non-uniqueness enormously: twin sets contain many hyperedge size distributions and isomorphism classes, and the number of non-uniform twins grows monotonically with $m$.
- For $k$-uniform hypergraphs the diagonal of the projection is redundant—hyperdegrees are fixed by the off-diagonal entries—but for non-uniform twins the diagonal carries information and helps refine the twin set.
- Enforcing the input's number of hyperedges or hyperdegree distribution shrinks but does not eliminate ambiguity; even with both $m$ and the diagonal fixed, no $G_3(6,m)$ projection had more than 100 twins.
- Both the worst-case search-tree size and the clique-approximation overcount are positively rank-correlated with true twin counts, so they can serve as rough, enumeration-free indicators of ambiguity.
Reading between the lines
- A cheap consequence not pursued in the paper: because worst-case tree size correlates with twin counts, practitioners could score any projected matrix with that formula before deciding whether projection-based analysis is safe; the paper stops short of endorsing this as a predictive measure.
- The non-uniform twin explosion suggests that any workflow that only records pairwise weights is implicitly averaging over very different higher-order structures; storing the line graph or a tensor alongside $W$ would remove much of this ambiguity, as the authors hint via Gram Mates.
- A testable extension: run the same exhaustive analysis on $G_k(n,m)$ for $n = 7, 8$ with brute-force verification; if non-uniform twin counts still dwarf uniform ones, the qualitative conclusion likely transfers to real interaction data.
- For dynamics, the paper's enumeration makes it possible to directly compare synchronization or epidemic outcomes across all twins of one $W$; the authors cite evidence that dynamics differ, and the natural next experiment is to identify which twin properties drive the difference.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the non-uniqueness of labeled node co-occurrence projections of simple hypergraphs: different hypergraphs can yield the same weighted pairwise projection matrix. The authors define the set of 'twin' hypergraphs realizing a given projection and introduce TwinSearch, a factor-graph-based tree-search algorithm intended to enumerate this entire set under optional constraints such as a fixed number of hyperedges or k-uniformity. They apply the algorithm to projections of hypergraphs from a modified G_k(n,m) ensemble, exhaustively for n=6 and m up to 20, and report that non-uniqueness is concentrated at intermediate hyperedge densities (roughly m=4..17 for 3-uniform twins, peaking around m=10), that non-uniform twins vastly outnumber k-uniform ones, and that the number of Gram-mate pairs grows with m. They also propose a combinatorial 'clique approximation' for the number of twins and show via Kendall rank correlations that both this approximation and the worst-case tree size correlate with the observed twin counts without being fully predictive. The paper positions this as a framework for assessing the information loss inherent in projecting hypergraphs to pairwise networks.
Significance. If the completeness of the enumeration can be established, the paper makes a useful contribution: it provides an explicit algorithmic tool for a problem that is usually only addressed heuristically, gives an exhaustive catalogue for small parameters that supports the qualitative conclusion that non-uniqueness peaks at intermediate density, and quantitatively demonstrates that simple combinatorial upper bounds overcount by orders of magnitude while still retaining rank correlation with the true twin counts. The connection to Gram Mates and the use of hypergraph dissimilarity measures within twin sets are likely to be of independent interest. The paper is also commendably honest about the limitations of the exhaustive approach and about the fact that no single projection-only statistic fully predicts twin-set size. However, the central algorithmic claim is currently not backed by a proof, and the printed pseudocode is internally inconsistent, so independent verification of the reported counts is not possible with the information given.
major comments (3)
- [Algorithm 1, line 17; Section 2] The expansion step in the pseudocode draws combinations of size W'_e from the available clique-neighbor set η'_e, but the residual requirement for edge e is R_e = W_e − W'_e as defined on line 11. If W'_e = 0 the algorithm pushes empty additions and can loop without progress; in general it can over- or under-cover edge e, so valid completions can be missed and the claimed completeness cannot hold. The surrounding text repeats this confusion when it says to 'choose another edge-node e with positive W'_e' rather than one with R_e > 0. Please replace W'_e by R_e in line 17 and in the corresponding sentence, and provide a corrected pseudocode.
- [Section 2, completeness argument] The paper asserts that TwinSearch returns 'all simple hypergraphs' and that 'every partial hypergraph in the search is guaranteed to be unique,' but no proof is given. The load-bearing claim is that every valid twin is reachable as a leaf of the search; this requires an induction showing that any hypergraph satisfying W (and the chosen constraints) can be obtained by successively satisfying residual edges via the combination step, and that the constraint-handling (fixed m, k-uniformity, diagonal matching) does not prune valid solutions. Please add a formal correctness proof for the corrected algorithm, including a statement of the invariant maintained at each search node.
- [Section 2, uniqueness of partial hypergraphs; Eq. (1)] The claim that each partial hypergraph is considered exactly once is doubtful: the same partial set of clique-nodes can be assembled through different edge-satisfaction orders, so duplicate expansions can occur unless the search enforces a canonical order or uses memoization. If duplicates are possible, the stated worst-case tree size O(∏_e binom(|η_e|, W_e)) is not necessarily a bound on the number of search nodes, and the parallelization statement that 'each descendant is independent from all others' requires qualification. Please clarify whether the search state is the set of chosen cliques or an ordered sequence, and how duplicates are avoided.
minor comments (5)
- [Code availability, Reference [20]] The GitHub URL in Reference [20] contains a space ('twin search/') and the availability statement says the code 'will be made available,' so the exhaustive G3(6,m) counts cannot currently be independently checked. Please provide a working link or a supplementary archive with the implementation.
- [Throughout, equation numbering] The text refers to 'Equation 3.1' and 'Eq. 2.2' but equations are not numbered in the manuscript; please assign numbers to the displayed equations and update the cross-references.
- [Section 3.3, model definition] The ensemble G3(6,m) is used throughout but is only informally described in Section 3.3; please give a formal definition at first use, including the minimum-hyperdegree constraint and the notation for general G_k(n,m).
- [Figure 4(f) caption] The caption notes that the vertical axis is cut off in log scale due to 0s corresponding to sub-millisecond runtimes; this is confusing because a log axis cannot display 0. Please clarify how zero or sub-millisecond values are handled, for example by jitter or by excluding them.
- [Section 3.1, Eq. (2)] Equation (2) is called the 'clique approximation' and is referenced as 'Equation 3.1,' but the displayed formula is unnumbered and the notation M_k is used without a formal definition of the hyperedge size distribution; please define M_k and number the equation.
Circularity Check
No significant circularity: the enumeration, upper bounds, and correlations are derived from the paper's own definitions and enumeration data rather than being fitted or self-referential; the pseudocode inconsistency is a correctness issue, not a circular reduction.
full rationale
TwinSearch's acceptance criterion (Algorithm 1, lines 10-13) is that the residual R = W - W' is zero, so every reported twin is, by construction, a hypergraph whose projection equals the input; this is the definition of the target set (Definition 1.2), not a predicted result. The clique approximation (Eq. 3.1) is explicitly shown to overcount, with the paper's own Fig. 2 demonstrating a hypergraph counted by the binomial that does not match W, and it is validated against actual twin counts rather than used to define them. The worst-case tree-size bound (Eq. 2.2) is computed directly from W and compared empirically using Kendall's tau; no parameter is fitted to force the correlation, and the paper explicitly disclaims finding a single predictive measure. The only self-citations are background references to the authors' prior hypergraph random-walk papers ([8], [9]) and their own GitHub repository [20], none of which carries a load-bearing argument. The serious weakness is non-circular: Algorithm 1 line 17 as printed uses W'_e where the residual R_e is required, and the asserted completeness of the search is not proved; these are correctness and reproducibility defects. The code availability statement says the implementation 'will be made available,' so the reported G3(6,m) counts cannot yet be independently checked, which also bears on reproducibility rather than circularity.
Assumptions & free parameters
assumptions (4)
- standard math Every hyperedge of any twin is a clique in the binarized projection graph, so the factor graph of all cliques contains all possible hyperedges.
- ad hoc to paper TwinSearch's search over degree-constrained factor-graph subgraphs visits every relevant subgraph without missing solutions.
- domain assumption The G_k(n,m) random hypergraph model with singleton rejection is a meaningful testbed for projection non-uniqueness.
- standard math Hypergraph isomorphism can be decided by graph isomorphism on bipartite incidence representations.
Cite this review
Pith. "Pith review of Exploring the Non-uniqueness of Node Co-occurrence Matrices of Hypergraphs." pith.science (2026). https://pith.science/paper/IPZXA5CT
@misc{pith2026250601479,
author = {Pith},
title = {Pith review of: Exploring the Non-uniqueness of Node Co-occurrence Matrices of Hypergraphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/IPZXA5CT}},
note = {Machine review of arXiv:2506.01479}
}
read the original abstract
Hypergraphs extend traditional networks by capturing multi-way or group interactions. Given the complexity of hypergraph data and the wide range of methodology available for pairwise network analysis, hypergraph data is often projected onto a weighted and undirected network. The simplest of these projections, often referred to as a node co-occurrence matrix, is known to be non-unique, as distinct non-isomorphic hypergraphs can produce the same weighted adjacency matrix. This non-uniqueness raises important questions about the structural information lost during the projection and how to efficiently quantify the complexity of the original hypergraph. Here we develop a search algorithm to identify all hypergraphs corresponding to a given projection, analyze its runtime, and explore its parallelisability. Applying this algorithm to projections derived from a random hypergraph model, we characterize conditions under which projections are non-unique. Our findings provide a new framework and set of computational tools to investigate projections of hypergraphs.
Forward citations
Cited by 2 Pith papers
-
The Informational Cost of Structure: Representational Complexity in Networked Dynamical Systems
Representational Complexity is the excess description length of any structure-plus-rule model over Kolmogorov complexity of the dynamics; graphs and hypergraphs are informationally equivalent only under explicit recov...
-
Information theory for hypergraph similarity
A normalized mutual information framework defines hypergraph similarity scores that capture within-order, cross-order, and coarse-grained structural overlap without tunable parameters.
Reference graph
Works this paper leans on
-
[1]
Higher-Order Dissimilar- ity Measures for Hypergraph Comparison
Cosimo Agostinelli, Marco Mancastroppa, and Alain Barrat. Higher-Order Dissimilar- ity Measures for Hypergraph Comparison. Mar. 2025. doi: 10.48550/arXiv.2503.16959. arXiv: 2503.16959 [physics]
-
[2]
Scalable Tensor Methods for Nonuniform Hypergraphs
Sinan G. Aksoy, Ilya Amburg, and Stephen J. Young. “Scalable Tensor Methods for Nonuniform Hypergraphs”. In: SIAM Jour- nal on Mathematics of Data Science 6.2 (June 2024), pp. 481–503. issn: 2577-0187. doi: 10.1137/23M1584472
-
[3]
Hypernetwork Sci- ence via High-Order Hypergraph Walks
Sinan G. Aksoy et al. “Hypernetwork Sci- ence via High-Order Hypergraph Walks”. In: EPJ Data Science9.1 (Dec. 2020), p. 16. issn: 2193-1127. doi: 10 . 1140 / epjds / s13688-020-00231-0
work page 2020
-
[4]
An Information-Theoretic, All-Scales Approach to Comparing Networks
James P. Bagrow and Erik M. Bollt. “An Information-Theoretic, All-Scales Approach to Comparing Networks”. In: Applied Net- work Science 4.1 (Dec. 2019). doi: 10.1007/ s41109-019-0156-x
work page 2019
-
[5]
On the Spectrum of Hypergraphs
Anirban Banerjee. “On the Spectrum of Hypergraphs”. In: Linear Algebra and its Applications 614 (Apr. 2021), pp. 82–110. issn: 00243795. doi: 10.1016/j.laa.2020.01. 012
-
[6]
Networks beyond Pairwise Interactions: Structure and Dy- namics
Federico Battiston et al. “Networks beyond Pairwise Interactions: Structure and Dy- namics”. In: Physics Reports 874 (2020), pp. 1–92. doi: 10.1016/j.physrep.2020.05. 004
-
[7]
Network Sim- ilarity via Multiple Social Theories
Michele Berlingerio et al. “Network Sim- ilarity via Multiple Social Theories”. In: Proceedings of the 2013 IEEE/ACM Inter- national Conference on Advances in Social Networks Analysis and Mining. Niagara On- tario Canada: ACM, Aug. 2013, pp. 1439–
work page 2013
-
[8]
Random Walks and Com- munity Detection in Hypergraphs
Timoteo Carletti, Duccio Fanelli, and Re- naud Lambiotte. “Random Walks and Com- munity Detection in Hypergraphs”. In: Journal of Physics: Complexity 2.1 (June 2021), p. 015011. doi: 10.1088/2632-072X/ abe27e
Show all 28 references
-
[9]
Random Walks on Hypergraphs
Timoteo Carletti et al. “Random Walks on Hypergraphs”. In: Physical Review E101.2 17 (Feb. 2020), p. 022308. issn: 2470-0045, 2470-0053. doi: 10 . 1103 / PhysRevE . 101 . 022308
2020
-
[10]
The Dual- Projection Approach for Two-Mode Net- works
M.G. Everett and S.P. Borgatti. “The Dual- Projection Approach for Two-Mode Net- works”. In: Social Networks 35.2 (May 2013), pp. 204–210. issn: 03788733. doi: 10. 1016/j.socnet.2012.05.004
2013
-
[11]
Phase Transitions and Stability of Dynamical Processes on Hypergraphs
Guilherme Ferraz De Arruda, Michele Tiz- zani, and Yamir Moreno. “Phase Transitions and Stability of Dynamical Processes on Hypergraphs”. In: Communications Physics 4.1 (Feb. 2021), p. 24. issn: 2399-3650. doi: 10.1038/s42005-021-00525-3
2021 doi
-
[12]
Higher-Order Correla- tions Reveal Complex Memory in Temporal Hypergraphs
Luca Gallo et al. “Higher-Order Correla- tions Reveal Complex Memory in Temporal Hypergraphs”. In: Nature Communications 15.1 (June 2024), p. 4754. issn: 2041-1723. doi: 10.1038/s41467-024-48578-6
2024 doi
-
[13]
Exploring Network Struc- ture, Dynamics, and Function using Net- workX
Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. “Exploring Network Struc- ture, Dynamics, and Function using Net- workX”. In: Proceedings of the 7th Python in Science Conference. Ed. by Ga¨ el Varo- quaux, Travis Vaught, and Jarrod Millman. Pasadena, CA USA, 2008, pp. 11–15
2008
-
[14]
Array program- ming with NumPy
Charles R. Harris et al. “Array program- ming with NumPy”. In: Nature 585.7825 (Sept. 2020), pp. 357–362. doi: 10 . 1038 / s41586-020-2649-2
2020
-
[15]
Network Compari- son and the Within-Ensemble Graph Dis- tance
Harrison Hartle et al. “Network Compari- son and the Within-Ensemble Graph Dis- tance”. In: Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 476.2243 (Nov. 2020), p. 20190744. doi: 10.1098/rspa.2019.0744
2020
-
[16]
Matplotlib: A 2D graphics environment
J. D. Hunter. “Matplotlib: A 2D graphics environment”. In: Computing in Science & Engineering 9.3 (2007), pp. 90–95. doi: 10. 1109/MCSE.2007.55
2007
-
[17]
Gram Mates, Sign Changes in Singular Values, and Isomorphism
Sooyeong Kim and Steve Kirkland. Gram Mates, Sign Changes in Singular Values, and Isomorphism. Apr. 2023. arXiv: 2304 . 07868 [math]
2023
-
[18]
Two-Mode Networks Ex- hibiting Data Loss
Steve Kirkland. “Two-Mode Networks Ex- hibiting Data Loss”. In: Journal of Com- plex Networks 6.2 (Apr. 2018), pp. 297–316. issn: 2051-1310, 2051-1329. doi: 10 . 1093 / comnet/cnx039
2018
-
[19]
XGI: A Python package for higher-order interaction net- works
Nicholas W. Landry et al. “XGI: A Python package for higher-order interaction net- works”. In: Journal of Open Source Software 8.85 (May 2023), p. 5162. doi: 10 . 21105 / joss.05162
2023
-
[20]
TwinSearch GitHub Repository
Timothy LaRock. TwinSearch GitHub Repository. 2025. url: https://github.com/ tlarock/twin search/
2025
-
[21]
May 2018
Xavier Ouvrard, Jean-Marie Le Goff, and St´ ephane Marchand-Maillet.Adjacency and Tensor Representation in General Hyper- graphs Part 1: E-Adjacency Tensor Uni- formisation Using Homogeneous Polynomi- als. May 2018. arXiv: 1712 . 08189 [cs, math]
2018
-
[22]
Explainable Hyperlink Prediction: A Hypergraph Edit Distance- Based Approach
Hongchao Qin et al. “Explainable Hyperlink Prediction: A Hypergraph Edit Distance- Based Approach”. In: 2023 IEEE 39th In- ternational Conference on Data Engineer- ing (ICDE). Anaheim, CA, USA: IEEE, Apr. 2023, pp. 245–257. doi: 10 . 1109 / ICDE55515.2023.00386
2023
-
[23]
Anastasiya Salova and Raissa M. D’Souza. Analyzing States beyond Full Synchroniza- tion on Hypergraphs Requires Methods be- yond Projected Networks. July 2021. arXiv: 2107.13712 [cond-mat, physics:nlin]
2021 arXiv
-
[24]
Distances in Higher-Order Networks and the Metric Structure of Hypergraphs
Ekaterina Vasilyeva et al. “Distances in Higher-Order Networks and the Metric Structure of Hypergraphs”. en. In: Entropy 25.6 (June 2023), p. 923. doi: 10 . 3390 / e25060923
2023
-
[25]
SciPy 1.0: Funda- mental Algorithms for Scientific Computing in Python
Pauli Virtanen et al. “SciPy 1.0: Funda- mental Algorithms for Scientific Computing in Python”. In: Nature Methods 17 (2020), pp. 261–272. doi: 10.1038/s41592-019-0686- 2
2020 doi
-
[26]
From Graphs to Hypergraphs: Hypergraph Projec- tion and Its Remediation
Yanbang Wang and Jon Kleinberg. From Graphs to Hypergraphs: Hypergraph Projec- tion and Its Remediation. Jan. 2024. arXiv: 2401.08519 [cs]
2024 arXiv
-
[27]
Hypergraph Reconstruc- tion from Network Data
Jean-Gabriel Young, Giovanni Petri, and Tiago P. Peixoto. “Hypergraph Reconstruc- tion from Network Data”. In: Communica- tions Physics 4.1 (Dec. 2021), p. 135. issn: 2399-3650. doi: 10.1038/s42005-021-00637- w. 18 A Rank Correlation Coefficients In Table 1, we show for each v...
2021 doi
-
[1440]
doi: 10.1145/2492517.2492582
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.