Pith. sign in

REVIEW 3 major objections 3 minor 28 references

Historical Contingencies Steer the Topology of Randomly Assembled Graphs

T0 review · 3 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read A new random graph model, inspired by assembly theory, samples networks whose topological statistics are extreme outliers relative to their degree sequences.

desk verdict New generative model, solid descriptive result, but the historical-contingency claim rests on a control that fails to preserve degree sequences. read the letter →

arxiv 2507.00335 v2 pith:NKZS6DVN submitted 2025-07-01 physics.soc-ph nlin.AOphysics.chem-ph

Cole Mathis , Harrison B. Smith This is my paper · ORCID
classification physics.soc-phnlin.AOphysics.chem-ph PACS 89.75.Fb89.75.Hc
keywords randomgraphmodelassemblytheoryhistoricalcontingencydegreesequenceconfigurationnetworktopologygenerativedrugdiscovery
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 introduces a random graph model inspired by assembly theory: starting from a multiset of two small path graphs, at each step two graphs are chosen (one possibly biased toward the largest), some of their nodes are merged, and the result is added back to the multiset. The authors show that after 25 iterations the largest assembled graphs frequently land in the extreme tails of the distribution of four topological statistics—clustering coefficient, mean betweenness, diameter, and algebraic connectivity—computed from configuration-model random graphs with identical degree sequences. They further argue that this atypicality is steered by historical contingency: the specific sequence of merges within a trajectory determines which part of graph space is reached, and randomizing connectivity while preserving only node and edge counts eliminates the effect. The result matters because it provides a generative sampler that explores unusual regions of graph space, with stated applications in drug discovery and materials science.

What carries the argument

The central object is the graph assembly algorithm itself, a stochastic recursive merging process. It initializes a multiset with a path graph on two nodes and a path graph on three nodes. At each iteration it selects a left graph L and right graph R; L is chosen uniformly from the largest graphs with probability p, otherwise uniformly from the whole multiset, while R is always uniform. It then merges M randomly chosen node pairs, one node from each graph, combining their neighborhoods, removing parallel edges and self-loops, and returns the resulting simple graph to the multiset. The algorithm's historical contingency comes from the reuse of previously assembled graphs: once a graph is generated it becomes a possible component in future merges, so the particular trajectory of selections and merges is encoded in the final topology.

What would settle it

Recompute the Fig. 4 comparison with a control that preserves the degree sequence of each merged pair—for instance, by rewiring with configuration-model swaps at every step. If the original and degree-preserving control distributions still differ significantly, historical contingency is confirmed; if they match, the effect is explained by degree structure instead.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that a recursively generative process—repeatedly merging pairs of graphs from an ever-growing multiset—produces an ensemble whose members are often statistically exceptional relative to their degree sequences. Quantitatively, for 1000 assembled graphs compared against 1000 configuration-model controls each, a large fraction of assembled graphs had absolute Z-scores above 2 and above 4 for at least one topological measure, meaning that standard random-graph nulls would rarely produce such structures. The authors identify the cause as historical contingency: because early graphs persist in the multiset and can be reused, random fluctuations early in a trajectory become amplified and steer later graphs toward distinct, extreme topologies. They support this by showing that if the connectivity of the two graphs being merged is randomized at each step (preserving node and edge counts and connectedness), the distinct topological properties largely disappear.

Load-bearing premise

The load-bearing premise is that the difference between the original algorithm and the Fig. 4 control is caused by historical contingency; but the control randomizes each merged graph's connectivity while preserving only node and edge counts, so it also erases degree-sequence structure, and the measured difference could be due to that loss rather than to the order of assembly steps.

Editorial extensions

If this is right

  • The assembly sampler can generate graphs that are extreme outliers relative to their own degree sequences, offering a complementary null or generative model to Erdős–Rényi and configuration-model ensembles.
  • Tuning the bias parameter p and the merge range M controls both graph size and the diversity of accessible topologies, so the ensemble can be tailored to explore specific regions of graph space.
  • Because history steers the outcome, two trajectories that start identically and use the same parameters can converge to very different graphs, implying that trajectory-level (not just parameter-level) information controls the sampling.
  • The graph-level formalization extends earlier assembly-theory work on molecular assembly trees, so the same procedure can be applied to construct molecules or materials with rare, drug-like properties.

Reading between the lines

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

  • A strict test of the historical-contingency claim would need a control that preserves each merged graph's degree sequence while scrambling only the order of operations; the paper's Fig. 4 control also removes degree structure, so the causal role of history is not fully isolated.
  • The same algorithm with different initial graph multisets (e.g., triangles or stars) may generate families of ensembles with different extreme-tail behavior, turning the seed set into an additional design parameter.
  • The extreme atypicality of assembled graphs suggests that such graphs could serve as challenging nulls or anomaly probes for network science: any statistical test tuned to configuration-model expectations would classify them as non-random.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 3 minor

Summary. The paper introduces a random graph assembly process inspired by assembly theory. Starting from a multiset containing a two-node path and a three-node path, each iteration selects two graphs (with a bias parameter p for choosing from the largest graphs), merges a random number M of vertex pairs, and adds the resulting graph to the multiset. The authors generate trajectories of 25 iterations, focus on the largest graph in each trajectory, and compute global clustering coefficient, mean betweenness centrality, diameter, and algebraic connectivity. They compare these statistics to those of configuration-model graphs with identical degree sequences and report that assembled graphs frequently fall in extreme tails of the control distribution (Fig. 2). They then introduce two controls: a history-loss resampling (Fig. 3) and a connectivity-randomized control that preserves node count, edge count, and connectedness (Fig. 4). Based on these controls they conclude that historical contingencies during the generative process steer the topology of assembled graphs.

Significance. If the main claims hold, the paper contributes a new random-graph ensemble that is structurally distinct from Erdős-Rényi, Watts-Strogatz, Barabási-Albert, and Kronecker models, and it provides a concrete algorithmic bridge between assembly theory and graph sampling. The pseudocode and public code are strengths, and the Z-score protocol in Fig. 2 is a reproducible, falsifiable way to quantify atypicality relative to degree-sequence controls. The potential applications to chemical-space and material sampling make the questions worth pursuing. However, the causal claim about historical contingency is currently supported by a control that does not isolate history from degree-sequence effects, and the degree-sequence comparison has an asymmetry that needs correction; these issues affect load-bearing parts of the paper's central claims.

major comments (3)
  1. [Results, paragraph before Fig. 4; Fig. 4 caption] The connectivity-randomized control preserves only the number of nodes, the number of edges, and connectedness of the two selected graphs; it does not preserve their degree sequences, and therefore does not preserve the degree sequence of the merged graph. Since Fig. 2 demonstrates that degree sequence alone strongly constrains clustering, betweenness, diameter, and algebraic connectivity, the distributional differences between original and control in Fig. 4 could be fully explained by the control's altered degree sequences rather than by 'historical dependence of graph reuse.' The caption's claim that historical dependence is 'partially responsible' for the observed topological properties is therefore not uniquely supported by this experiment. A degree-preserving rewiring control (for example, double-edge swaps on L and R after selection, or a configuration-model resampling restricted to connected graphs) is necessary to separate the historical-reuse effect from the degree-sequence effect.
  2. [Results, Fig. 1C and Fig. 2; text on disconnected randomizations] The paper compares assembled graphs, which are connected by construction, to configuration-model graphs with identical degree sequences, but when the randomized graphs are disconnected it computes the statistics on the largest connected component. The largest connected component of a disconnected configuration-model graph does not have the degree sequence of the assembled graph, so the comparison is no longer between graphs with identical degree sequences. This asymmetry can bias all four Z-scores reported in Fig. 2 and undermines the quantitative support for the claim that assembled graphs are atypical relative to graphs with identical degree sequences. The atypicality claim should be evaluated against connected configuration-model graphs (for example, by conditioning on connectedness or by using a connected realization algorithm), or by treating disconnected graphs symmetrically.
  3. [Results, Fig. 3 and Conclusion] The history-loss experiment in Fig. 3 documents variation in mean degree as a function of how many final steps are resampled, but the paper's central topological claim concerns clustering, betweenness, diameter, and algebraic connectivity. Mean degree alone is a much weaker proxy for those properties, so Fig. 3 does not directly demonstrate that the exceptional topology of Fig. 2 depends on historical contingency. Since Fig. 4 is the only direct evidence connecting these topological properties to history, and that control is confounded as described above, the conclusion that 'the algorithm's historically contingent features drive these key properties' is currently under-supported. Directly tracking the four topological statistics in history-loss ensembles, or coupling a degree-preserving control with trajectory-level analysis, would close this gap.
minor comments (3)
  1. [Fig. 3 caption] The caption states that the cones indicate the maximum and minimum mean degree observed at each iteration, while the text says the intervals are the inter-quantile range between 1% and 99%; these descriptions should be reconciled.
  2. [Fig. 4] The text reports that the distributions of original and control graphs are 'all statistically significant,' but no test name, sample sizes, or p-values are given; please specify the significance testing procedure.
  3. [Appendix B] The appendix says the number of merges is 'at minimum the smaller of the two graphs' vertex counts,' but the algorithm caps the selected M at that smaller count; the wording should be corrected to 'at most.'

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the generative algorithm is not fitted to data, and the central atypicality and history-contingency claims are tested against independent randomized baselines.

full rationale

The paper introduces a stochastic generative algorithm with fixed initial graphs and explicit parameters (p, M, N); none of these are fitted to the reported topological statistics. The main claim, that assembled graphs are atypical relative to configuration-model graphs with identical degree sequences, is established by comparing algorithm outputs against an independently sampled null ensemble, not by construction. The degree sequences used for the configuration model are outputs of the generative process, so their relation to the observed statistics is empirical rather than definitional. The historical-contingency claim is probed with two controls: a history-loss resampling and a connectivity-randomized control; neither control is derived from the target conclusion. The Fig. 4 control preserves only node count, edge count, and connectedness rather than the degree sequence, which is a genuine confounding concern for the causal attribution of history, but this is a validity/sensitivity issue rather than circular reasoning. Self-citations appear as background references to assembly theory and prior molecular applications, and they do not carry the derivation of the paper's new results. There is no fitted parameter renamed as a prediction, no imported uniqueness theorem, and no result that reduces to its own assumptions.

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

The model has four hand-chosen parameters (p, M range, initial graph set, iteration count), none fitted to data. There are no invented entities. The central claim rests on the choice of these parameters and on the comparison to configuration-model nulls.

free parameters (4)
  • p = 0.5 in main results
    Probability of selecting the largest graph L from G_max; the paper notes higher p reduces diversity, so the atypicality result depends on this choice.
  • M (merge count range) = [1,3] in main results
    Upper bound of the uniformly sampled number of vertex merges per iteration; results are demonstrated for this range, and different ranges yield different mean degrees.
  • Initial graph set G = {P2, P3}
    The algorithm is initialized with a path graph of two nodes and a path graph of three nodes; the paper states future work could optimize this set, so results may depend on initialization.
  • N (iterations) = 25 for the main statistical analysis
    The topological properties are computed after 25 iterations; trajectory length affects the graph size and properties.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Historical Contingencies Steer the Topology of Randomly Assembled Graphs." pith.science (2026). https://pith.science/paper/NKZS6DVN

@misc{pith2026250700335,
  author       = {Pith},
  title        = {Pith review of: Historical Contingencies Steer the Topology of Randomly Assembled Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NKZS6DVN}},
  note         = {Machine review of arXiv:2507.00335}
}
read the original abstract

Graphs are used to represent and analyze data in domains as diverse as physics, biology, chemistry, planetary science, and the social sciences. Across domains, random graph models relate generative processes to expected graph properties, and allow for sampling from distinct ensembles. Here we introduce a new random graph model, inspired by assembly theory, and characterize the graphs it generates. We show that graphs generated using our method represent a diverse ensemble, characterized by a broad range of summary statistics, unexpected even in graphs with identical degree sequences. Finally we demonstrate that the distinct properties of these graphs are enabled by historical contingencies during the generative process. These results lay the foundation for further development of novel sampling methods based on assembly theory with applications to drug discovery and materials science.

Figures

Figures reproduced from arXiv: 2507.00335 by the authors.

Figure 1
Figure 1. FIG. 1 [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 3
Figure 3. FIG. 3 [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figure 4
Figure 4. FIG. 4 [PITH_FULL_IMAGE:figures/full_fig_p004_4.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 24 canonical work pages

  1. [1]

    Polya and R

    G. Polya and R. C. Read,Combinatorial enumeration of groups, graphs, and chemical compounds(Springer Sci- ence & Business Media, 2012)

    work page 2012

  2. [2]

    P. G. Polishchuk, T. I. Madzhidov, and A. Varnek, Esti- mation of the size of drug-like chemical space based on gdb-17 data, Journal of computer-aided molecular design 27, 675 (2013)

    work page 2013

  3. [3]

    Choubisa, J

    H. Choubisa, J. Abed, D. Mendoza, H. Matsumura, M. Sugimura, Z. Yao, Z. Wang, B. R. Sutherland, A. Aspuru-Guzik, and E. H. Sargent, Accelerated chemi- cal space search using a quantum-inspired cluster expan- sion approach, Matter6, 605 (2023)

    work page 2023

  4. [4]

    Restrepo, Chemical space: limits, evolution and mod- elling of an object bigger than our universal library, Dig- ital Discovery1, 568 (2022)

    G. Restrepo, Chemical space: limits, evolution and mod- elling of an object bigger than our universal library, Dig- ital Discovery1, 568 (2022)

    work page 2022

  5. [5]

    C. W. Coley, Defining and exploring chemical spaces, Trends in Chemistry3, 133 (2021)

    work page 2021

  6. [6]

    Shackel, Bertrand’s paradox and the principle of in- difference, Philosophy of Science74, 150 (2007)

    N. Shackel, Bertrand’s paradox and the principle of in- difference, Philosophy of Science74, 150 (2007)

    work page 2007

  7. [7]

    Erdos, A

    P. Erdos, A. R´ enyi,et al., On the evolution of random graphs, Publ. math. inst. hung. acad. sci5, 17 (1960)

    work page 1960

  8. [8]

    Albert and A.-L

    R. Albert and A.-L. Barab´ asi, Statistical mechanics of complex networks, Reviews of modern physics74, 47 (2002)

    work page 2002

Show all 28 references
  1. [9]

    C. P. Gomes, A. Sabharwal, and B. Selman, Near- uniform sampling of combinatorial spaces using xor con- straints, Advances In Neural Information Processing Sys- tems19(2006)

    2006

  2. [10]

    Aerts and M

    D. Aerts and M. S. de Bianchi, Solving the hard problem of bertrand’s paradox, Journal of Mathematical Physics 55(2014)

    2014

  3. [11]

    Newman,Networks(Oxford university press, 2018)

    M. Newman,Networks(Oxford university press, 2018)

    2018

  4. [12]

    M. E. Newman, D. J. Watts, and S. H. Strogatz, Ran- dom graph models of social networks, Proceedings of the national academy of sciences99, 2566 (2002)

    2002

  5. [13]

    Leskovec, D

    J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Falout- sos, and Z. Ghahramani, Kronecker graphs: an approach to modeling networks., Journal of Machine Learning Re- search11(2010)

    2010

  6. [14]

    Ravasz and A.-L

    E. Ravasz and A.-L. Barab´ asi, Hierarchical organiza- tion in complex networks, Physical review E67, 026112 (2003)

    2003

  7. [15]

    Sharma, D

    A. Sharma, D. Cz´ egel, M. Lachmann, C. P. Kempes, S. I. Walker, and L. Cronin, Assembly theory explains and quantifies selection and evolution, Nature622, 321 (2023)

    2023

  8. [16]

    S. M. Marshall, D. G. Moore, A. R. Murray, S. I. Walker, and L. Cronin, Formalising the pathways to life using assembly spaces, Entropy24, 884 (2022)

    2022

  9. [17]

    S. M. Marshall, C. Mathis, E. Carrick, G. Keenan, G. J. Cooper, H. Graham, M. Craven, P. S. Gromski, D. G. Moore, S. I. Walker,et al., Identifying molecules as biosignatures with assembly theory and mass spectrom- etry, Nature communications12, 3033 (2021)

    2021

  10. [18]

    Jirasek, A

    M. Jirasek, A. Sharma, J. R. Bame, S. H. M. Mehr, N. Bell, S. M. Marshall, C. Mathis, A. MacLeod, G. J. Cooper, M. Swart,et al., Investigating and quantifying molecular complexity using assembly theory and spec- troscopy, ACS Central Science10, 1054 (2024)

    2024

  11. [19]

    Kahana, A

    A. Kahana, A. MacLeod, H. Mehr, A. Sharma, E. Car- rick, M. Jirasek, S. Walker, and L. Cronin, Constructing the molecular tree of life using assembly theory and mass spectrometry, arXiv preprint arXiv:2408.09305 (2024)

    2024 arXiv

  12. [20]

    K. Y. Patarroyo, A. Sharma, I. Seet, I. Packmore, S. I. Walker, and L. Cronin, Quantifying the complex- ity of materials with assembly theory, arXiv preprint arXiv:2502.09750 (2025)

    2025 arXiv

  13. [21]

    Y. Liu, C. Mathis, M. D. Bajczyk, S. M. Marshall, L. Wilbraham, and L. Cronin, Exploring and mapping chemical space with molecular assembly trees, Science Advances7, eabj2465 (2021)

    2021

  14. [22]

    Pagel, A

    S. Pagel, A. Sharma, and L. Cronin, Mapping evolution of molecules across biochemistry with assembly theory, arXiv preprint arXiv:2409.05993 (2024)

    2024 arXiv

  15. [23]

    Harrison B Smith & Cole Mathis, AssemblingGraphs.jl: Generative model of graphs via at,https://github.com/ mathis-group/AssemblingGraphs.jl(2025), accessed: 2025-09-10

    2025

  16. [24]

    Fiedler, Algebraic connectivity of graphs, Czechoslo- vak mathematical journal23, 298 (1973)

    M. Fiedler, Algebraic connectivity of graphs, Czechoslo- vak mathematical journal23, 298 (1973)

    1973

  17. [25]

    J. O. Spiegel and J. D. Durrant, Autogrow4: an open- source genetic algorithm for de novo drug design and lead optimization, Journal of cheminformatics12, 1 (2020)

    2020

  18. [26]

    Verhellen and J

    J. Verhellen and J. Van den Abeele, Illuminating elite patches of chemical space, Chemical science11, 11485 (2020)

    2020

  19. [27]

    I. Seet, K. Y. Patarroyo, G. Siebert, S. I. Walker, and L. Cronin, Rapid computation of the assembly index of molecular graphs, arXiv preprint arXiv:2410.09100 (2024)

    2024 arXiv

  20. [28]

    Flamm, D

    C. Flamm, D. Merkle, and P. F. Stadler, Assembly in directed hypergraphs, arXiv preprint arXiv:2505.22826 (2025). 6 Appendix A: Graph Assembly Algorithm Details Algorithm 1:Graph Assembly Algorithm Data:p∈[0,1] (prob. of forcing largest graph selection),M∈N(desired node merges...

    2025 arXiv

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.