Pith. sign in

REVIEW 4 major objections 5 minor 43 references

SDP bounds on the stability number via ADMM and intermediate levels of the Lasserre hierarchy

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read Here the authors try to make the Lasserre hierarchy practical for the stability number, an NP-hard graph invariant, by solving its semidefinite relaxations with the alternating direction method of multipliers (ADMM).

desk verdict A sound ADMM pipeline for Lasserre stable-set bounds that delivers a real computational advance, but whose strongest empirical claims rest on a benchmark-tuned basis heuristic and no released code. read the letter →

arxiv 2506.08648 v1 pith:QFUXOKBG submitted 2025-06-10 math.OC

Lennart Sinjorgo , Renata Sotirov , Juan C. Vera This is my paper
classification math.OC MSC 90C2290C2705C69
keywords stabilitynumbersemidefiniteprogrammingLasserrehierarchyalternatingdirectionmethodofmultipliersthetafunctionbasisselectionexactsubgraphsumsquares
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 claims that ADMM can make Lasserre-hierarchy semidefinite bounds on the stability number of graphs practical, even though these SDPs are usually too large for interior-point methods. The authors compute either the full second level of the hierarchy or an intermediate level between one and two, for graphs up to 300 vertices, usually within one hour. The intermediate level is chosen by solving the theta SDP and adding the non-edge monomials with the largest optimal entries to the degree-one basis, and the same theta solution warm-starts the ADMM so the first bound equals the theta bound. On the tested graphs these SDP-Lasserre bounds are competitive with two of the strongest existing SDP approaches, and on several graphs the paper reports the strongest known SDP bounds on the stability number.

What carries the argument

The engine is the truncated sum-of-squares relaxation $\alpha_\mathcal{B}(G)$: one requires $\mu - \sum_i x_i$ to be a sum of squares modulo the ideal generated by $x_i^2 - x_i$ and $x_i x_j$ for edges, using only monomials from a basis $\mathcal{B}$. For bases between levels 1 and 2, $\mathcal{B}$ consists of all singletons plus selected non-edge pairs, and the relaxation becomes an SDP with a positive semidefinite matrix of order $|\mathcal{B}|$ and one linear inequality per stable-set monomial. The ADMM alternates a projection onto the PSD cone, done by single-precision eigenvalue decomposition, with closed-form projections onto half-spaces; a lemma converts any PSD iterate into a certified upper bound. Basis selection and warm start both use an optimal solution $Z^*$ of the $\theta$ SDP: non-edges with the largest $Z^*_{i,j}$ enter the basis, and the $\theta$ primal and dual solutions seed the first ADMM iterates.

What would settle it

Pick a graph family not represented in the paper's tables, such as random graphs on 250 vertices at edge probability $p=0.02$, and run the stated method with basis size 2500 and the one-hour limit. If the rounded-down SDP-Lasserre bound is consistently weaker than the exact subgraph hierarchy or BOUND 2 on those graphs, the theta-largest basis selection rule is the limiting factor rather than the ADMM itself.

Watch

Extended reading notes

Core claim

The central claim is that the Lasserre hierarchy, often considered too large for practical computation, becomes usable when its SDPs are solved by ADMM instead of interior-point methods. The paper defines the relaxation $\alpha_\mathcal{B}(G)$ for any monomial basis $\mathcal{B}$ containing all degree-zero and degree-one monomials, proves that every PSD matrix produced by the ADMM yields a valid upper bound on $\alpha(G)$ (Lemma 3), and specifies how to choose $\mathcal{B}$: solve the $\theta$ SDP, then add the non-edges $\{i,j\}$ with the largest optimal entries $Z^*_{i,j}$. With basis size capped at 2500, this gives the full second Lasserre level for small graphs and intermediate levels between 1 and 2 for larger ones, up to 300 vertices. Across the tested evil, random, near-regular, and structured graphs, the SDP-Lasserre bounds improve on the $\theta$ bound, frequently round down to the true stability number, and beat the exact subgraph hierarchy bounds on most of the random and near-regular graphs.

Load-bearing premise

The load-bearing premise is that the non-edges with the largest entries in an optimal theta solution are the right degree-two monomials for a strong intermediate Lasserre bound; this heuristic is supported only by preliminary experiments on the same benchmark graphs, so if it underperforms on other graphs the reported bounds stay valid but lose their competitive edge.

Editorial extensions

If this is right

  • Intermediate Lasserre levels between 1 and 2 can be solved in practice, so the full second level is not necessary for strong stable-set bounds on the tested graphs.
  • Rounding the SDP-Lasserre bound down to an integer often certifies the true stability number, closing gaps that other SDP bounds leave open.
  • The method handles graphs where interior-point solvers cannot even store the constraint matrix, because the ADMM needs memory proportional to the PSD variable order, not to the number of constraints.
  • Single-precision eigenvalue decompositions cut runtime roughly in half on tested graphs while changing the bound by at most a few hundredths, making lower precision a viable default.
  • Because every ADMM iterate is a valid upper bound, the algorithm can be stopped early and still return a certificate for $\alpha(G)$.

Reading between the lines

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

  • A natural stress test is to run the theta-largest basis rule on new graph families; the authors themselves note that their selection method is not yet suited to highly symmetric graphs, so failure there would point to a fixable heuristic rather than to the ADMM or the hierarchy.
  • The anytime-correctness property suggests the method could serve as a warm-startable bound inside branch-and-bound or branch-and-cut algorithms for maximum clique and related problems, trading time against bound strength continuously.
  • If the basis selection problem were solved, the same ADMM machinery would transfer to other 0-1 polynomial optimization problems requiring Lasserre-style SDP bounds.
  • Since the PSD projection is the bottleneck and single precision suffices, faster or approximate eigensolvers could extend the approach to higher levels or to graphs with far more than 300 vertices.
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

4 major / 5 minor

Summary. The paper proposes an ADMM-based solver for SDP relaxations of the stable set problem coming from the Lasserre hierarchy, at level 2 or at intermediate levels between 1 and 2. For intermediate levels, the paper introduces a basis-selection rule that uses an optimal Lovász theta solution to choose which degree-2 monomials to add, and it uses the same solution to warm-start the ADMM. The authors prove that every PSD matrix produced by the ADMM yields a valid upper bound on the stability number, and they report extensive computational results on evil, random, near-regular, DIMACS-derived, and SageMath graphs, comparing against BOUND 2 and ESH bounds.

Significance. If the computational claims are fully supported, the paper would be a valuable practical contribution: it would show that first-order ADMM methods can handle intermediate Lasserre relaxations with PSD matrices of order up to 2500 and hundreds of thousands of constraints, giving bounds competitive with the best existing SDP-based approaches. The theoretical core is sound: Lemma 3 gives a clean certificate of a valid upper bound from any PSD matrix, Lemma 2 provides an exact projection formula, and Lemma 1 correctly reduces the basis to stable-set monomials. The paper does not ship code or data, so the numerical claims cannot currently be verified or reused, and the global phrasing of the main empirical claim is not supported by the tables in the paper.

major comments (4)
  1. [§4.1 and §5.3] The basis-selection rule—take the s-(1+n) non-edges with largest entries Z*_{i,j} of an optimal theta solution—is justified only by 'Preliminary numerical experiments' run on the same families used in Section 5.3, with no held-out graphs, no ablation, and no theoretical argument. Since the central claim that the approach yields the strongest known SDP bounds depends on this heuristic selecting monomials that actually tighten the bound, the paper should either validate the rule on independent benchmark families not used during its design, or replace the global claim by a statement limited to the tested graphs.
  2. [Tables 4 and 6] The abstract and Section 6 state that the approach provides 'best-known' or 'strongest known' SDP bounds, but Tables 4 and 6 contain several instances where SDP-Lasserre is strictly worse than BOUND 2 or ESH: in Table 6, rand_n200_p002 gives 95.778 versus 95.043 for BOUND 2, rand_n200_p005 gives 67.355 versus 65.544, and rand_n200_p003 gives 82.425 versus 81.079; further examples appear in Table 4. The claim should be restricted to the subset of graphs where the comparison actually holds, and the text should quantify how often SDP-Lasserre improves, ties, or loses against the competing bounds.
  3. [Section 5 and Availability] The computational contribution is not reproducible as submitted: no code is released, the random and near-regular instances are only described as being 'the same as in [34]', and the MATLAB implementation details beyond parameter values are not specified. Since the paper's main evidence is empirical, I ask for release of code and benchmark data, or at least a complete list of all instances with parameters, seeds, and instance files.
  4. [§5.1 and Lemma 3] Lemma 3 certifies v(X^ell) as an upper bound only for matrices X^ell that are exactly PSD. The single-precision ADMM of Section 5.1 computes the projection (13) via a single-precision eigenvalue decomposition, so rounding errors can produce matrices X^ell that are slightly indefinite; the reported values would then not be certified upper bounds. The authors should either report the maximum PSD violation and verify that Lemma 3 still applies, or apply the certificate in double precision to the single-precision iterates.
minor comments (5)
  1. [§5.3.1] The sentence 'The clique problem on a graphGis equivalent to to the stable set problem on the complement graph ofG' contains a duplicated 'to'.
  2. [Figure 1] The x-axis of Figure 1 is labeled in minutes while the text says the bound is recorded every 10 seconds; the caption or axis label should be made consistent.
  3. [Table 5] The header 'New Old [14]' is ambiguous; please spell out which columns are the new bounds and which are taken from [14].
  4. [Availability of data and materials] The statement that all graphs are 'available online, or on request' should be replaced with concrete repositories or DOIs for each benchmark family, including the random and near-regular graphs used in Tables 4–6.
  5. [Reference [18]] Reference [18] contains a typo: 'Department' should read 'Department'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the ADMM solves an independent SDP and the theta-based basis selection does not make the resulting bounds depend on the claimed output.

full rationale

The paper's derivation is self-contained rather than circular. The bound alpha_B(G) is defined as an SDP in Eq. (7), and the ADMM in Eq. (11) solves that SDP directly; Lemma 3 then certifies that every PSD iterate yields a valid upper bound on alpha(G). The Lovasz theta solution Z* is used only to select degree-two monomials and to warm-start the iterates, and the paper explicitly notes that the returned bound is valid regardless of the heuristic. No equation reduces by construction to a fitted quantity or to the claimed result. The only self-citation, [40], appears as background for ADMM usage and is not load-bearing. The basis-selection heuristic is tuned on the same benchmark families, and Section 6 concedes that it is not suited to exploit symmetry and can be improved on highly symmetric graphs; this is a generalization and robustness concern about the empirical 'best-known bounds' claim, not a circularity in the mathematical derivation.

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

The central claim rests on standard Lasserre/SOS theory and standard ADMM convergence results; no new entities are introduced. The free parameters are algorithm hyperparameters and the basis size cap, all chosen by hand. The main unproven load-bearing assumption is the theta-guided basis selection heuristic.

free parameters (5)
  • basis size cap s = 2500
    Section 5.3 sets s=2500 to keep PSD order manageable so ADMM converges within one hour on most graphs.
  • ADMM penalty parameter rho = (4/5)*sqrt(|B|)
    Section 5 heuristic choice; affects convergence speed and stopping tolerance.
  • ADMM stepsize nu = 3/2
    Section 5, within theoretical convergence range (0, (1+sqrt(5))/2) from [11].
  • stagnation threshold K_stag = 150 (500 in Table 5)
    Stopping criterion (20); K_stag=150 for most tables, 500 for reruns.
  • convergence tolerance epsilon = 1e-4
    Stopping condition (19) threshold.
assumptions (4)
  • domain assumption The Lasserre hierarchy relaxations alpha_B(G) are valid upper bounds on alpha(G) for any basis B, and level 1 equals the Lovasz theta function.
    Standard results cited to [21, 23, 33]; used to justify the bounding framework.
  • standard math The ADMM converges for the convex SDP (7) with O(1/ell) ergodic rate when nu is in (0, (1+sqrt(5))/2).
    Cited to [17,11]; assumed to hold for this specific SDP.
  • standard math The polynomial ideal I_G encodes stable sets, so nonnegative polynomials over S_G are SOS modulo I_G.
    Standard SOS/positive polynomial theory, cited to [33,22].
  • domain assumption The benchmark suite from [12,13,14,34] is representative of the state of the art for SDP bounds on stability number.
    Underlies the 'best-known bounds' claim.

how reviews work

0 comments
Cite this review

Pith. "Pith review of SDP bounds on the stability number via ADMM and intermediate levels of the Lasserre hierarchy." pith.science (2026). https://pith.science/paper/QFUXOKBG

@misc{pith2026250608648,
  author       = {Pith},
  title        = {Pith review of: SDP bounds on the stability number via ADMM and intermediate levels of the Lasserre hierarchy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QFUXOKBG}},
  note         = {Machine review of arXiv:2506.08648}
}
read the original abstract

We consider the Lasserre hierarchy for computing bounds on the stability number of graphs. The semidefinite programs (SDPs) arising from this hierarchy involve large matrix variables and many linear constraints, which makes them difficult to solve using interior-point methods. We propose solving these SDPs using the alternating direction method of multipliers (ADMM). When the second level of the Lasserre hierarchy for a given graph is intractable for the ADMM, we consider an intermediate-level relaxation of the hierarchy. To warm-start the ADMM, we use an optimal solution from the first level of the Lasserre hierarchy, which is equivalent to the well-known Lov\'asz theta function. Additionally, we use this solution to determine which degree two monomials to add in the Lasserre hierarchy relaxation to obtain an intermediate level between 1 and 2. Computational results demonstrate that our approach yields strong bounds on the stability number, which are computable within reasonable running times. We provide the best-known bounds on the stability number of various graphs from the literature.

Figures

Figures reproduced from arXiv: 2506.08648 by the authors.

Figure 1
Figure 1. Comparison of upper bounds for evil-N184-p98-myc23x8, n = 184, α(G) = 16, s = 2500. computed BOUND 2 on the same machine we used to compute the SDP-Lasserre bounds2 . Additional details regarding BOUND 2 can be found in [34, Sect. 4.1]. The columns ‘GapClsd’ (for gap closed) under SDP-Lasserre and BOUND 2 report the fraction ϑ(G)−f ∗ ϑ(G)−α(G) rounded down to the first digit, where f ∗ equals the value of the corres… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

43 extracted references · 41 canonical work pages

  1. [40]

    Sinjorgo and R

    L. Sinjorgo and R. Sotirov. On solving MAX-SAT using sum of squares.INFORMS Journal on Computing, 36(2):417–433, 2024

    work page 2024

  2. [34]

    Pucher and F

    D. Pucher and F. Rendl. Practical experience with stable set and coloring relaxations.arXiv preprint arXiv:2401.17069v2, 2024

    arXiv 2024

  3. [1]

    Ahierarchyofsubgraphprojection-basedsemidef- inite relaxations for some NP-hard graph optimization problems.INFOR: Information Systems and Operational Research, 53(1):40–48, 2015

    E.Adams, M.F.Anjos, F.Rendl, andA.Wiegele. Ahierarchyofsubgraphprojection-basedsemidef- inite relaxations for some NP-hard graph optimization problems.INFOR: Information Systems and Operational Research, 53(1):40–48, 2015

    work page 2015

  4. [2]

    Alizadeh.Combinatorial optimization with interior point methods and semidefinite matrices

    F. Alizadeh.Combinatorial optimization with interior point methods and semidefinite matrices. PhD thesis, University of Minnesota, Minneapolis, USA, 1991

    work page 1991

  5. [3]

    M. F. Anjos. An improved semidefinite programming relaxation for the satisfiability problem. Mathematical Programming, 102:589–608, 2005

    work page 2005

  6. [4]

    Balas and J

    E. Balas and J. Xue. Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring.Algorithmica, 15(5):397–412, 1996

    work page 1996

  7. [5]

    S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers.Foundations and Trends®in Machine learning, 3(1):1–122, 2011

    2011

  8. [6]

    Houseofgraphs: adatabaseofinteresting graphs.Discrete Applied Mathematics, 161(1-2):311–314, 2013

    G.Brinkmann, K.Coolsaet, J.Goedgebeur, andH.Mélot. Houseofgraphs: adatabaseofinteresting graphs.Discrete Applied Mathematics, 161(1-2):311–314, 2013

    work page 2013

Show all 43 references
  1. [7]

    J. S. Campos, R. Misener, and P. Parpas. Partial Lasserre relaxation for sparse max-cut.Optimiza- tion and Engineering, 24:1983–2004, 2023

    1983

  2. [8]

    Chen, J.-B

    T. Chen, J.-B. Lasserre, V. Magron, and E. Pauwels. A sublevel moment-SOS hierarchy for poly- nomial optimization.Computational Optimization and Applications, 81(1):31–66, 2022

    2022

  3. [9]

    de Klerk

    E. de Klerk. Exploiting special structure in semidefinite programming: A survey of theory and applications.European Journal of Operational Research, 201:1–10, 2010

    2010

  4. [10]

    Dukanovic and F

    I. Dukanovic and F. Rendl. Semidefinite programming relaxations for graph coloring and maximal clique problems.Mathematical Programming, 109(2):345–365, 2007

    2007

  5. [11]

    Fortin and R

    M. Fortin and R. Glowinski. On decomposition-coordination methods using an augmented La- grangian. In M. Fortin and R. Glowinski, editors,Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems, volume 15, pages 97–146. Elsevier, 1983

    1983

  6. [12]

    E. Gaar. On different versions of the exact subgraph hierarchy for the stable set problem.Discrete Applied Mathematics, 356:52–70, 2024. 15

    2024

  7. [13]

    Gaar and F

    E. Gaar and F. Rendl. A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring.Mathematical Programming, 183(1):283–308, 2020

    2020

  8. [14]

    E. Gaar, M. Siebenhofer, and A. Wiegele. An SDP-based approach for computing the stability number of a graph.Mathematical Methods of Operations Research, 95(1):141–161, 2022

    2022

  9. [15]

    Gouveia, P

    J. Gouveia, P. A. Parrilo, and R. R. Thomas. Theta bodies for polynomial ideals.SIAM Journal on Optimization, 20(4):2097–2118, 2010

    2010

  10. [16]

    Gruber and F

    G. Gruber and F. Rendl. Computational experience with stable set relaxations.SIAM Journal on Optimization, 13(4):1014–1028, 2003

    2003

  11. [17]

    B. He, F. Ma, and X. Yuan. Convergence study on the symmetric version of ADMM with larger step sizes.SIAM Journal on Imaging Sciences, 9(3):1467–1501, 2016

    2016

  12. [18]

    I. D. Ivanov and E. de Klerk and. Parallel implementation of a semidefinite programming solver based on CSDP on a distributed memory cluster.Optimization Methods and Software, 25(3):405– 420, 2010

    2010

  13. [19]

    W. Karush. Minima of functions of several variables with inequalities as side constraints.MSc. Thesis. Deptartment of Mathematics, University of Chicago, Chicago, Illinois, 1939

    1939

  14. [20]

    H. W. Kuhn and A. W. Tucker. Nonlinear programming. InBerkeley Symposium on Mathematical Statistics and Probability, pages 481–492. Springer, 1951

    1951

  15. [21]

    J. B. Lasserre. Global optimization with polynomials and the problem of moments.SIAM Journal on Optimization, 11(3):796–817, 2001

    2001

  16. [22]

    J. B. Lasserre.Moments, positive polynomials and their applications, volume 1. World Scientific, 2009

    2009

  17. [23]

    M. Laurent. A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0–1 programming.Mathematics of Operations Research, 28(3):470–496, 2003

    2003

  18. [24]

    M. Laurent. Semidefinite representations for finite varieties.Mathematical Programming, 109(1): 1–26, 2007

    2007

  19. [25]

    M. Laurent. Sums of squares, moment matrices and optimization over polynomials. InEmerging Applications of Algebraic Geometry, pages 157–270. Springer, 2009

    2009

  20. [26]

    L. Lovász. On the Shannon capacity of a graph.IEEE Transactions on Information theory, 25(1): 1–7, 1979

    1979

  21. [27]

    Lovász and A

    L. Lovász and A. Schrijver. Cones of matrices and set-functions and 0–1 optimization.SIAM Journal on Optimization, 1(2):166–190, 1991

    1991

  22. [28]

    Madani, A

    R. Madani, A. Kalbat, and J. Lavaei. ADMM for sparse semidefinite programming with applications to optimal power flow problem. In2015 54th IEEE Conference on Decision and Control (CDC), pages 5932–5939. IEEE, 2015

    2015

  23. [29]

    R. D. C. Monteiro and P. Zanjácomo. Implementation of primal-dual methods for semidefinite programming based on Monteiro and Tsuchiya newton directions and their variants.Optimization Methods and Software, 11(1-4):91–140, 1999

    1999

  24. [30]

    Version 10.1., 2024

    MOSEK ApS.The MOSEK optimization toolbox for MATLAB manual. Version 10.1., 2024. URL http://docs.mosek.com/latest/toolbox/index.html

    2024

  25. [31]

    Nesterov and A

    Y. Nesterov and A. Nemirovskii. Interior point polynomial algorithms in convex programming. In SIAM Studies in Applied Mathematics. SIAM, Philadelphia, USA, Vol. 13, 1994

    1994

  26. [32]

    D. E. Oliveira, H. Wolkowicz, and Y. Xu. ADMM for the SDP relaxation of the QAP.Mathematical Programming Computation, 10(4):631–658, 2018

    2018

  27. [33]

    P. A. Parrilo. An explicit construction of distinguished representations of polynomials nonnegative over finite sets.Preprint, ETH, Zürich, 2002. 16

    2002

  28. [35]

    Raghavendra and B

    P. Raghavendra and B. Weitz. On the bit complexity of sum-of-squares proofs. In I. Chatzigian- nakis, P. Indyk, F. Kuhn, and A. Muscholl, editors,44th International Colloquium on Automata, Languages, and Programming, volume 80 ofLIPIcs, pages 80:1–80:13. Schloss Dagstuhl – Lei...

    2017

  29. [36]

    Rontsis, P

    N. Rontsis, P. Goulart, and Y. Nakatsukasa. Efficient semidefinite programming with approximate ADMM.Journal of Optimization Theory and Applications, 192:292–320, 2022

    2022

  30. [37]

    Schrijver

    A. Schrijver. A comparison of the Delsarte and Lovász bounds.IEEE Transactions on Information Theory, 25(4):425–429, 1979

    1979

  31. [38]

    H. D. Sherali and W. P. Adams. A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems.SIAM Journal on Discrete Mathematics, 3(3): 411–430, 1990

    1990

  32. [39]

    Silvestri

    F. Silvestri. Spectrahedral relaxations of the stable set polytope using induced subgraphs. Master’s thesis, Universität Heidelberg, 2013

    2013

  33. [41]

    Szabó and B

    S. Szabó and B. Zaválnij. Benchmark problems for exhaustive exact maximum clique search algo- rithms.Informatica, 43(2):177–186, 2019

    2019

  34. [42]

    https://www.sagemath.org

    The Sage Developers.SageMath, the Sage Mathematics Software System (Version 10.5), 2025. https://www.sagemath.org

    2025

  35. [43]

    van Maaren, L

    H. van Maaren, L. van Norden, and M. J. Heule. Sums of squares based approximation algorithms for MAX-SAT.Discrete Applied Mathematics, 156(10):1754–1779, 2008. 17

    2008

Pith tools

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