Pith. sign in

REVIEW 1 major objections 5 minor 42 references

Markov and lattice bases for Forman-Ricci curvature of graphs

T0 review · 1 major / 5 minor · reviewed 2026-08-04 · deepseek-v4-flash

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

Pith's one-line read This paper proves that minimal rewiring moves for graphs with fixed degree and Forman-Ricci curvature sequences necessarily grow quadratically in size, and supplies a cheap lattice basis for sampling.

desk verdict Correct quadratic lower bound and a clean degree-3 lattice basis; the odd-Δ transfer is unproved but valid, and the RL claims run ahead of the table. read the letter →

arxiv 2608.01929 v1 pith:GTRAMWEN submitted 2026-08-03 math.CO cs.DMphysics.soc-ph

Jane Ivy Coons , Giulio Zucal This is my paper
classification math.COcs.DMphysics.soc-ph MSC 13P1005C07
keywords Forman-RiccicurvatureMarkovbasesGraverLawrenceliftingjointdegreematrixtoricidealslatticenetworkgeometry
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 studies the moves needed to walk between all simple graphs that share the same vertex-degree sequence and the same Forman-Ricci curvature frequencies. It shows that any minimal Markov basis for this problem must contain moves whose size (degree, the total weight moved) grows at least quadratically in the maximum degree Delta, by constructing explicit primitive moves that attain that growth. Since this rules out any compact description of the complete Markov basis, the authors give an explicit lattice basis made only of degree-three moves, so every move is an integer combination of cheap moves. They then show that an actor-critic reinforcement-learning sampler can use this lattice basis to explore fibers for graphs with larger maximum degrees than exact algebraic methods can reach. A sympathetic reader would care because Markov bases were the main bottleneck for sampling null graphs with prescribed curvatures.

What carries the argument

The central object is the matrix B_Delta, whose rows encode, for each vertex degree and each curvature value (endpoint degree sum), the counts of a graph's joint degree matrix; vectors in its kernel are exactly the candidate rewiring moves. The paper works with the Lawrence lifting Lambda(B_Delta), the standard slack-variable extension that restricts moves to those realizable by simple graphs. The key structural fact is that the unique minimal Markov basis of a Lawrence lifting coincides with the Graver basis of the original matrix, so finding indispensable moves reduces to finding primitive moves of B_Delta. The paper's explicit move u_Delta (Equation 5, with parity-dependent coefficients a

What would settle it

For Delta=7 (or any odd Delta>=7), compute the Graver basis (the set of all primitive moves) of B_Delta with exact symbolic algebra and compare the largest degree of a primitive move with 2(floor(Delta/2)-1)^2+1; if the maximum degree is smaller, the odd-Delta part of the theorem is false.

Watch

Extended reading notes

Core claim

The central claim is that the algebraic complexity of sampling is unavoidably high: Theorem 3.5 constructs, for every Delta >= 4, a primitive move u_Delta in the kernel of B_Delta of degree 2(floor(Delta/2)-1)^2+1, and Corollary 3.6 lifts it to an indispensable move of degree 4(floor(Delta/2)-1)^2+2 in the unique minimal Markov basis of the Lawrence lifting Lambda(B_Delta). This makes the degree of indispensable moves quadratic in the maximum degree. Balanced against that, Theorem 4.6 gives a lattice basis for B_Delta consisting entirely of degree-three moves b_ijkl, so the paper provides both a negative complexity result and a practical positive construction. On the experimental side, the a

Load-bearing premise

The quadratic lower bound for odd maximum degrees depends on the paper's unproved assertion that a primitive move for B_{Delta-1} is automatically primitive for B_Delta; if that transfer fails, the bound is only established for even Delta.

Editorial extensions

If this is right

  • Every minimal Markov basis for Lambda(B_Delta) must contain an indispensable move of degree at least 4(floor(Delta/2)-1)^2+2, so exact symbolic computation of the basis from scratch becomes infeasible as Delta grows.
  • Because the primitive move u_Delta has degree quadratic in Delta, any complete listing of primitive moves for B_Delta—and hence of Graver basis elements—must include moves that large; compact closed-form descriptions of the full Markov basis are out of reach.
  • The degree-three moves b_ijkl generate the entire integer kernel of B_Delta as a lattice, so every Markov move can be written as an integer linear combination of moves of degree three; this gives a practical building block for sampling algorithms.
  • The reinforcement-learning actor-critic sampler, using the lattice basis as its action set, can explore fibers for graphs with maximum degree up to 39, including dense joint degree matrices, in cases where exact algebraic basis computation does not terminate.
  • The number of sampled states produced by the RL sampler is a guaranteed lower bound for the size of the fiber, not an exact count.

Reading between the lines

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

  • The quadratic lower bound concerns indispensable moves of the minimal Markov basis; it does not by itself imply that individual fibers need moves of that size. One could test whether fiber-specific move sets of bounded degree connect typical fibers, which would soften the practical bottleneck.
  • The odd-Delta half of the main lower bound rests on an asserted transfer of primitivity from B_{Delta-1} to B_Delta that the paper does not prove; a direct check for Delta=7 or 9 would either close the gap or expose a counterexample.
  • The lattice-basis construction may generalize: any edge statistic defined by sums of endpoint degrees yields the same kind of column-sum constraints, so the same degree-three triangular moves could provide lattice bases for other pairs of degree/statistic constraints.
  • Since the RL sampler returns only lower bounds, one could compare its discovered fiber size with the exact fiber size for small Delta; agreement would indicate that learned moves capture the fiber, while disagreement would quantify the sampling gap.
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

1 major / 5 minor

Summary. The paper studies the integer kernel of the matrix B_Δ that encodes degree and Forman–Ricci curvature frequency constraints on the joint degree matrix of a simple graph, and of its Lawrence lifting Λ(B_Δ). The main theoretical results are: (i) for every Δ ≥ 4 there exists a primitive Markov move for B_Δ of degree 2(⌊Δ/2⌋ − 1)^2 + 1, so the unique minimal Markov basis of Λ(B_Δ) contains moves whose degree grows quadratically in Δ (Theorem 3.5 and Corollary 3.6); and (ii) a lattice basis for ker B_Δ consisting of explicit degree-three moves b_{ijkℓ}, obtained as a triangular subset of all degree-three moves (Theorem 4.6). The paper also applies the actor-critic fiber sampler of Gvozdanovic and Petrovic to explore JDMs of moderate-size graphs.

Significance. If correct, the quadratic degree growth is a meaningful complexity result: it explains and quantifies the computational difficulty of computing Markov bases for the curvature-and-degree constrained graph sampling problem introduced by Roost et al. The explicit lattice basis of degree-three moves is a useful constructive complement, since a full Markov basis seems out of reach. The even-Δ construction in Section 3 is detailed and self-contained, and the lattice-basis construction is explicit and verifiable. The odd-Δ transfer in Theorem 3.5 is true but is presently asserted without proof; this is a gap in presentation rather than a counterexample to the claim. The reinforcement-learning experiments are exploratory and provide reproducible code, but they do not sharply benchmark the method against exact algebraic sampling.

major comments (1)
  1. [Theorem 3.5] The odd-Δ case rests on the assertion that 'the primitive moves of A_{Δ−1} are also primitive moves for B_Δ' (with A presumably meaning B). This is load-bearing for all odd Δ, since the quadratic lower bound otherwise holds only for even Δ. The statement is correct: u_{Δ−1} is supported only on pairs from {1, . . . , Δ−1}; if v ∈ ker(B_Δ) with 0 ≤ v+ ≤ u+ and 0 ≤ v− ≤ u−, then v is supported on the same pairs, the degree-Δ row and the curvature rows 2Δ−1 and 2Δ of B_Δ vanish identically on such columns, and the remaining rows coincide with B_{Δ−1}. Hence v would contradict primitivity of u_{Δ−1} in B_{Δ−1}. Please add this one-paragraph proof (and fix the A/B notation).
minor comments (5)
  1. [Theorem 3.5 proof] 'A_4' and 'A_{Δ−1}' should be 'B_4' and 'B_{Δ−1}'. Also, 'the unique minimal Markov move for B_4' would be clearer as 'the unique, up to sign, primitive move for B_4'.
  2. [Proposition 4.2] The equation 'rank(Λ(B_Δ)) = ... = d−2' uses d without defining it in this paper. Since the preceding text uses d for the number of rows in Definition 2.9 and for other quantities elsewhere, please define d explicitly (or remove the 'd−2' equality).
  3. [Proposition 4.4] The classification of all degree-three moves is terse, and the 'without loss of generality' step in the proof does not explicitly address diagonal pairs (e.g., e_{jj}) or repeated indices. The selected lattice basis is proved independently by the triangular submatrix in Theorem 4.6, but the classification claim would benefit from a more careful argument or a reference.
  4. [Section 5, edge-count bound] In the displayed inequality, |E(G)| = 1/2(Σ_{a,b} J_ab + Σ_a J_aa) equals Σ_{a≤b} J_ab by symmetry, so the '≥' should be '='. If the intended bound is on the lifted move degree, please state that explicitly.
  5. [Table 1] Several rows report only 1 sampled state, which suggests the RL method found no moves in those runs. This is consistent with the stated lower-bound interpretation, but the narrative that the method 'performs well' should be tempered, or additional runs/metrics should be reported.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the quadratic degree lower bound is a self-contained construction; the sole self-citation is not load-bearing.

full rationale

The central claim (Theorem 3.5) is derived by an explicit combinatorial construction of u_Δ, with Lemmas 3.2–3.3 proving that u_Δ lies in ker(B_Δ) and is primitive; no parameter is fitted to the target degree and no target quantity is assumed. The use of Sturmfels' theorem [38] on Lawrence liftings and the Diaconis–Sturmfels framework is external support, and Corollary 3.6 is a direct application of that theorem. The only shared-authority citation is [29, Prop. 4.12], used to compute rank(B_Δ) for the lattice-basis result in Section 4; this rank formula is prior work, not an assumption of the theorem being proved, and the quadratic lower bound does not rely on it. One passage in the proof of Theorem 3.5 asserts without proof that primitive moves of B_{Δ−1} transfer to B_Δ; this is an omitted proof, not a circular step, and the transfer is valid because any divisor of u_{Δ−1} in ker(B_Δ) uses no index Δ, so the extra rows of B_Δ vanish and the remaining rows coincide with those of B_{Δ−1}. The lattice basis construction is likewise explicit and checked by triangularity. No fitted input is relabeled as a prediction, and no known result is merely renamed.

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

The paper introduces no fitted constants or new physical entities. Its constructions (u_Delta, b_ijkell) are explicit and parameter-free. All axioms are either standard algebraic statistics theorems or characterization results imported from [36] and [29].

assumptions (5)
  • standard math Fundamental Theorem of Markov Bases (Diaconis-Sturmfels 1998) linking Markov bases to toric ideal generators
    Invoked in Section 2.2 (Theorem 2.10) as the foundation for defining Markov bases and their computation.
  • standard math Sturmfels' Theorem 7.1: the unique minimal Markov basis of a Lawrence lifting equals its Graver basis
    Used in Theorem 2.15 and Corollary 3.6 to identify indispensable moves with lifts of primitive moves of B_Delta.
  • domain assumption Stanton-Pinar characterization of joint degree matrices (Theorem 2.8)
    Taken from [36]; defines realizability of matrices as JDMs of simple graphs and underpins the Lawrence-lifting fiber construction.
  • domain assumption Rank formula for B_Delta from Roost et al. (Prop 4.2 [29])
    Used in Section 4 to state the kernel dimension and confirm the lattice basis size (C(Delta-2,2)).
  • domain assumption Standing assumption that graphs have no isolated vertices (deg(v) >= 1)
    Stated in Section 2; the JDM encoding and degree frequency formula are only set up for graphs without isolated vertices.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Markov and lattice bases for Forman-Ricci curvature of graphs." pith.science (2026). https://pith.science/paper/GTRAMWEN

@misc{pith2026260801929,
  author       = {Pith},
  title        = {Pith review of: Markov and lattice bases for Forman-Ricci curvature of graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GTRAMWEN}},
  note         = {Machine review of arXiv:2608.01929}
}
read the original abstract

Discrete Forman-Ricci curvature is a quantity associated to each edge of a graph that describes its local geometry. It has proven to be a useful tool in network analysis in a variety of applications. Recent work by Roost et al.\ (2024) proposed the use of Markov bases to sample from the space of graphs with prescribed vertex degrees and curvatures. In the present work, we further develop the algebraic and combinatorial theory of these Markov bases. We show that the degree of an indispensable Markov move grows at least quadratically in the maximum degree of the graph. In light of this result, a compact description of all Markov basis elements seems unattainable at present. Instead, we find a lattice basis for this problem using only degree three Markov moves, which allows us to employ recently-developed reinforcement learning methods for finding Markov moves that can be applied to a specific graph.

Figures

Figures reproduced from arXiv: 2608.01929 by the authors.

Figure 1
Figure 1. Forman–Ricci curvature values F(e) on the edges of a graph. Example 2.5. Consider our running example graph depicted in [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. A transposition replacing edges {u, x} and {v, y} with {u, y} and {v, x}. Theorem 2.8 ( [36, Thm. 4.2]). A symmetric matrix J ∈ N ∆×∆ is the joint degree matrix of a simple graph if and only if, for all distinct a, b ∈ {1, . . . , ∆}, the following conditions hold: (i) |Va| = 1 a X ∆ c=1 Jac + Jaa is an integer; (ii) Jab ≤ |Va| · |Vb|; (iii) Jaa ≤ [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. The Markov move m applied to a graph. n columns. The lift of x u + − x u− to IΛ(A) is the binomial x u + y u− − x u− y u + . On the level of integer vectors, this says that u + − u − is primitive for A if and only if the move  u + u −  −  u − u +  (4) is primitive for Λ(A). It is not difficult to check that all binomials in IΛ(A) are lifts of binomials in IA and that a binomial in IA is primitive if and only if … view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

42 extracted references · 3 linked inside Pith

  1. [1]

    S. Aoki, H. Hara, and A. Takemura.Markov bases in algebraic statistics, volume 199. Springer Science & Business Media, 2012. 6, 13

    2012

  2. [2]

    Bakry, I

    D. Bakry, I. Gentil, and M. Ledoux.Analysis and Geometry of Markov Diffusion Operators. Grundlehren der mathematischen Wissenschaften. Springer, Cham, 2013. 2

    2013

  3. [3]

    Bauer, J

    F. Bauer, J. Jost, and S. Liu. Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator.Math. Res. Lett., 19(6):1185–1205, 2012. 2

    2012

  4. [4]

    J. A. De Loera and S. Onn. Markov bases of three-way tables are arbitrarily complicated. Journal of Symbolic Computation, 41(2):173–181, 2006. 2

    2006

  5. [5]

    Devriendt and R

    K. Devriendt and R. Lambiotte. Discrete curvature on graphs from the effective resistance. Journal of Physics: Complexity, 3(2):025008, 2022. 2

    2022

  6. [6]

    Devriendt, A

    K. Devriendt, A. Ottolini, and S. Steinerberger. Graph curvature via resistance distance. Discrete Applied Mathematics, 348:68–78, 2024. 2

    2024

  7. [7]

    Diaconis, R

    P. Diaconis, R. Graham, and S. P. Holmes. Statistical problems involving permutations with restricted positions.Lecture notes-monograph series, 36:195–222, 2001. 5

    2001

  8. [8]

    Diaconis and B

    P. Diaconis and B. Sturmfels. Algebraic algorithms for sampling from conditional distribu- tions.The Annals of Statistics, 26(1):363–397, 1998. 5, 6

    1998

Show all 42 references
  1. [9]

    A. Dobra. Dynamic markov bases.Journal of Computational and Graphical Statistics, 21(2):496–517, 2012. 15

    2012

  2. [10]

    M. Eidi, A. Farzam, W. Leal, A. Samal, and J. Jost. Edge-based analysis of networks: curvatures of graphs and hypergraphs.Theory in Biosciences, 139:337 – 348, 2020. 2

    2020

  3. [11]

    Erbar and J

    M. Erbar and J. Maas. Ricci curvature of finite Markov chains via convexity of the entropy. Archive for rational mechanics and analysis, 206(3):997–1038, 2012. 2

    2012

  4. [12]

    R. F. and M. Rogantin. Markov chains on the reference set of contingency tables with upper bounds.Metron, 65(1):35–51, 2007. 7 17

    2007

  5. [13]

    Fesser, S

    L. Fesser, S. S. de Haro Iv´ a˜ nez, K. Devriendt, M. Weber, and R. Lambiotte. Augmen- tations of Forman’s Ricci curvature and their applications in community detection, 2023. arXiv:2306.06474 [math.CO]. 2

    2023 arXiv

  6. [14]

    Fesser and M

    L. Fesser and M. Weber. Mitigating over-smoothing and over-squashing using augmenta- tions of forman-ricci curvature. InLearning on Graphs Conference, pages 1–19. PMLR,

  7. [15]

    R. Forman. Bochner’s method for cell complexes and combinatorial Ricci curvature.Dis- crete & Computational Geometry, 29:323–374, 2003. 1, 2, 3

    2003

  8. [16]

    J. A. D. F´ elix Almendra-Hern´ andez and S. Petrovi´ c. Markov bases: A 25 year update. Journal of the American Statistical Association, pages 1–32, 2024. 6

    2024

  9. [17]

    D. R. Grayson and M. E. Stillman. Macaulay2, a software system for research in algebraic geometry. Available athttp://www2.macaulay2.com. 6

  10. [18]

    Gvozdanovic and S

    I. Gvozdanovic and S. Petrovic. Learning to sample fibers for goodness-of-fit testing.Alge- braic Statistics, 17:33–73, 01 2026. 2, 13, 15, 16

    2026

  11. [19]

    Jost and S

    J. Jost and S. Liu. Ollivier’s Ricci curvature, local clustering and curvature-dimension inequalities on graphs.Discrete & Computational Geometry, 51(2):300–322, 2014. 2

    2014

  12. [20]

    Y. Lin, L. Lu, and S.-T. Yau. Ricci curvature of graphs.Tohoku Mathematical Journal, 63(4):605 – 627, 2011. 2

    2011

  13. [21]

    Lin and S.-T

    Y. Lin and S.-T. Yau. Ricci curvature and eigenvalue estimate on locally finite graphs. Mathematical research letters, 17(2):343–356, 2010. 2

    2010

  14. [22]

    S. Liu, F. M¨ unch, and N. Peyerimhoff. Bakry– ´Emery curvature and diameter bounds on graphs.Calculus of variations and partial differential equations, 57(2):1–9, 2018. 2

    2018

  15. [23]

    J. A. D. Loera, J. Eddy, S. J. Robertson, and J. A. Samper. Discrete curvatures and convex polytopes, 2025, arxiv:2510.11894 [math.CO]. 2

    2025

  16. [24]

    Loisel and P

    B. Loisel and P. Romon. Ricci curvature on polyhedral surfaces via optimal transportation. Axioms, 3(1):119–139, 2014. 2

    2014

  17. [25]

    C. Ni, Y. Lin, F. Luo, and J. Gao. Community detection on networks with Ricci flow. Scientific Reports, 9:9984, 2019. 2

    2019

  18. [26]

    Ollivier

    Y. Ollivier. Ricci curvature of metric spaces.Comptes Rendus Mathematique, 345(11):643– 646, 2007. 2

    2007

  19. [27]

    Ollivier

    Y. Ollivier. A survey of Ricci curvature for metric spaces and Markov chains. InProbabilistic approach to geometry, volume 57, pages 343–382. Mathematical Society of Japan, 2010. 2

    2010

  20. [28]

    Rapallo and R

    F. Rapallo and R. Yoshida. Markov bases and subbases for bounded contingency tables. Annals of the Institute of Statistical Mathematics, 62(4):785–805, 2010. 7

    2010

  21. [29]

    Roost, K

    M. Roost, K. Devriendt, G. Zucal, and J. Jost. Exploring the space of graphs with fixed discrete curvatures.Journal of Physics: Complexity, 5(3):035011, 2024. 2, 3, 5, 7, 13

    2024

  22. [30]

    J. Salez. Cutoff for non-negatively curved Markov chains.Journal of the European Mathe- matical Society, 26(11):4375–4392, 2023. 2

    2023

  23. [31]

    J. Salez. Spectral gap and curvature of monotone Markov chains.The Annals of Probability, 52(3):1153–1161, 2024. 2 18

    2024

  24. [32]

    J. Salez. Modern aspects of Markov chains: entropy, curvature and the cutoff phenomenon, 2025, arxiv2508.21055. 2

    2025 arXiv

  25. [33]

    Samal, H

    A. Samal, H. K. Pharasi, S. J. Ramaia, H. Kannan, E. Saucan, J. Jost, and A. Chakraborti. Network geometry and market instability.Royal Society Open Science, 8(2):201734, 2021. 2

    2021

  26. [34]

    Sandhu, T

    R. Sandhu, T. Georgiou, E. Reznik, L. Zhu, I. Kolesov, Y. S ¸enbabao˘ glu, and A. Tannen- baum. Graph curvature for differentiating cancer networks.Scientific Reports, 5:12323,

  27. [35]

    Schrijver.Theory of linear and integer programming

    A. Schrijver.Theory of linear and integer programming. John Wiley & Sons, 1998. 9

    1998

  28. [36]

    Stanton and A

    I. Stanton and A. Pinar. Constructing and sampling graphs with a prescribed joint degree distribution.ACM J. Exp. Algorithmics, 17, 2012. 4, 5

    2012

  29. [37]

    Steinerberger

    S. Steinerberger. Curvature on graphs via equilibrium measures.Journal of Graph Theory, 103(3):415–436, 2023. 2

    2023

  30. [38]

    Sturmfels.Grobner bases and convex polytopes, volume 8

    B. Sturmfels.Grobner bases and convex polytopes, volume 8. American Mathematical Soc.,

  31. [39]

    Y. Tian, Z. Lubberts, and M. Weber. Curvature-based clustering on graphs.Journal of Machine Learning Research, 26(52):1–67, 2025. 2

    2025

  32. [40]

    Topping, F

    J. Topping, F. D. Giovanni, B. P. Chamberlain, X. Dong, and M. M. Bronstein. Under- standing over-squashing and bottlenecks on graphs via curvature, 2022. arXiv:2111.14522 [stat.ML]. 2

    2022 arXiv

  33. [41]

    Van Der Hofstad.Random graphs and complex networks, volume 1

    R. Van Der Hofstad.Random graphs and complex networks, volume 1. Cambridge university press, 2017. 16

    2017

  34. [42]

    W. W. Zachary. An information flow model for conflict and fission in small groups.Journal of anthropological research, 33(4):452–473, 1977. 16 19

    1977

Pith tools

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