Pith. sign in

REVIEW 2 major objections 4 minor 26 references

Revisiting the Graph Isomorphism Problem with Semidefinite Programming

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read The paper claims graph isomorphism can be decided by solving one semidefinite program and comparing its optimum with n-squared.

desk verdict Theorem 5's proof contains a false inference about nonzero coordinates and inner products, so the claimed polynomial-time graph isomorphism algorithm is unsupported. read the letter →

arxiv 1908.06320 v2 pith:45NSLHAJ submitted 2019-08-17 cs.DS cs.CC

Giannis Nikolentzos , Michalis Vazirgiannis This is my paper · ORCID
classification cs.DScs.CC MSC 05C6005C6968Q2590C22
keywords graphisomorphismsemidefiniteprogrammingcompatibilitycliquedetectionconvexrelaxationpolynomial-timealgorithmGrammatrix
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

This paper tries to establish that graph isomorphism can be solved in polynomial time by semidefinite programming. It builds the compatibility graph of two $n$-vertex graphs, where an $n$-clique corresponds exactly to an isomorphism, and formulates the clique test as an SDP. The claimed behavior of the SDP optimal value is $n^2$ when an $n$-clique exists and at most $n(n-1)$ when it does not, so a polynomial-time SDP solver with error below $1/2$ would decide isomorphism by rounding. If the claim is correct, it gives an exact SDP-based algorithm for a problem whose complexity status is open.

What carries the argument

The compatibility graph $G_c$ is an auxiliary graph whose vertices are pairs $(v,u)$ with $v\in V_1$, $u\in V_2$, with an edge between two pairs exactly when they agree on adjacency or non-adjacency; an $n$-clique in $G_c$ corresponds to an isomorphism between the two input graphs. The SDP (2) maximizes $\operatorname{trace}(JX)$ subject to $\operatorname{trace}(X)=n$, $X_{ij}=0$ on non-edges of $G_c$, $X_{ij}\le 1$ on edges, and $X\succeq 0$. Writing $X=UU^\top$, the partition structure of $G_c$ makes vectors inside each of the $n$ partitions orthogonal, so the objective becomes $n$ plus the sum of inner products of partition sums $w_1,\dots,w_n$; the claimed bounds $n^2$ and $n(n-1)$ come from bounding those inner products.

What would settle it

Run the SDP (2) on the compatibility graph of two non-isomorphic 4-vertex graphs; if any instance has an optimal value strictly greater than $n(n-1)=12$ while the graph contains no 4-clique, the central threshold claim is false. A targeted search can look for partition-sum vectors that share a coordinate in every part yet pairwise cancel, then check whether the induced Gram matrix satisfies the constraints with value above 12.

Watch

Extended reading notes

Core claim

The paper's central claim is that the semidefinite relaxation (2) has a sharp threshold for compatibility graphs. When the compatibility graph contains a clique of order $n$, the paper constructs an optimal solution whose objective value is exactly $n^2$: rank-one when there is one isomorphism, and higher-rank built from one coordinate per clique when several exist. When the compatibility graph contains no $n$-clique, the paper claims the optimal value is at most $n(n-1)$. The proof rewrites $\operatorname{trace}(JX)$ as $n$ plus pairwise inner products of $n$ partition-sum vectors, then applies an inner-product bound and the arithmetic-geometric mean inequality. The gap of $n$ between $n^2$ and $n(n-1)$ is what lets a solver with additive error under $1/2$ separate the two cases and answer the isomorphism question in polynomial time.

Load-bearing premise

The $n(n-1)$ upper bound depends on a premise that has not been established: that when the $n$ partition sums are pairwise proportional, one coordinate is nonzero in every partition and the resulting vertex pairs have nonzero pairwise dot products, which would force an $n$-clique; dot products add up and can cancel, so this need not follow.

Editorial extensions

If this is right

  • If the threshold holds, graph isomorphism would be in the class P, because the SDP is solvable in polynomial time to any fixed additive error and the gap between $n^2$ and $n(n-1)$ is $n$.
  • Every compatibility graph that arises from an isomorphism test would have an SDP relaxation with no gap: the SDP optimum exactly matches the presence or absence of an $n$-clique.
  • The constructed optimal solutions carry the isomorphism itself: a rank-one solution with $x_i=1$ on clique vertices gives the vertex mapping between the two graphs.
  • Any off-the-shelf SDP solver with an error guarantee would suffice for the decision step: solve, round, and compare with $n^2$.
  • The result would extend exact polynomial-time isomorphism testing beyond restricted graph classes such as planar graphs, bounded-degree graphs, and graphs of bounded eigenvalue multiplicity.

Reading between the lines

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

  • If the upper-bound proof is repaired, the same threshold idea would yield a certificate of non-isomorphism: a dual feasible solution valued near $n(n-1)$ would prove the graphs are not isomorphic, an open direction the paper itself names.
  • The compatibility-graph SDP may transfer to subgraph isomorphism or maximum common subgraph problems by changing the clique-size parameter and adjusting the threshold accordingly.
  • The partition-sum rewriting suggests a broader recipe: for any $n$-partite graph whose parts are internally non-adjacent, the presence of an $n$-clique might be certified by an SDP threshold of the same shape.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. This paper proposes a semidefinite programming (SDP) approach to the graph isomorphism problem. The authors use the known reduction from graph isomorphism to the problem of deciding whether the compatibility (association) graph of two n-vertex graphs contains an n-clique. They formulate clique existence as an SDP (problem (2)) obtained by dropping a rank constraint from a rank-1 formulation, and claim: (i) if an n-clique exists, the SDP optimum is exactly n^2 (Theorems 3 and 4); and (ii) if no n-clique exists, the SDP optimum is at most n(n-1) (Theorem 5). Since n(n-1) < n^2, comparing an approximate SDP value with n^2 would yield a polynomial-time exact isomorphism test. The rank-1 case (Theorem 3) is treated separately. The main contribution is the claimed upper bound for the non-clique case, which is the basis for the polynomial-time decision procedure.

Significance. If valid, the result would be a major breakthrough: a polynomial-time exact algorithm for graph isomorphism, a long-standing open problem. The reduction via compatibility graphs is standard (Levi's theorem), and the SDP relaxation is a natural and interesting formulation. The paper is self-contained, cites prior work appropriately, and does not fit any free parameters; the construction in Theorem 4 for the clique case is explicit and checkable. However, the proof of the key upper bound (Theorem 5) contains a false inference about inner products, so the central claim is not established. The claimed significance is therefore not supported by the current manuscript.

major comments (2)
  1. [§3.2, proof of Theorem 5] The proof infers that if the partition-sum vectors w_1,...,w_n all have a nonzero value in the same coordinate i, then there exist n vertex vectors (one from each partition) with a nonzero i-th component, and 'the inner product of every pair of these vectors is nonzero,' so the vertices form an n-clique. This inference is invalid: a shared nonzero coordinate does not imply a nonzero inner product, because inner products are sums over coordinates and can cancel (e.g., (1,1) and (1,-1)). Therefore the subsequent assertion that for each coordinate i at most n-1 of the w_j can have a nonzero value is unsupported, and the bound z_i ≤ (n-2)Σ_j (w^i_j)^2 in Eq. (9) does not follow. Since this bound is the step that yields trace(JX) ≤ n(n-1), Theorem 5 is not proved. The polynomial-time decision procedure at the end of Section 3.2, which relies on the gap between n(n-1) and n^2, is therefore not justified. This is a load-bearing gap in the central claim.
  2. [§3.2, proof of Theorem 5] The equality condition in the Cauchy-Schwarz step is stated as 'equality holds if and only if the n vectors w_1,...,w_n are pairwise linearly dependent.' This is imprecise: equality in ⟨w_i,w_j⟩ ≤ ||w_i|| ||w_j|| requires w_i and w_j to be nonnegative scalar multiples (or one to be zero), not merely linearly dependent, since a negative multiple would make the inner product negative and the inequality strict. The proof also does not discuss the case where some w_j = 0, in which the claim that all other vectors have a nonzero i-th component need not hold. These issues are secondary to the invalid inference above, but they are part of the same proof and would need to be corrected in any revision.
minor comments (4)
  1. [Section 3.2, Eq. (3) and similar expressions] The notation n + ⟨v_1,v_2⟩ + ... + ⟨v_m,v_{m-1}⟩ is ambiguous; it should be written explicitly as n + Σ_{i≠j} ⟨v_i,v_j⟩ to make clear that all ordered pairs are included.
  2. [Figure 2 caption] 'Fugure 2' is a typo for 'Figure 2'.
  3. [Abstract and introduction] The phrase 'rounding the optimal solution to the nearest integer' is inaccurate; the proposed procedure rounds the optimal value and compares it with n^2, and no rounding of the SDP solution matrix is described.
  4. [Section 2.3] This subsection appears unrelated to the main contribution and ends with an undeveloped remark about latin square graphs; the authors should either integrate it with the main development or remove it.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the paper's central SDP claim rests on a self-contained derivation chain, and its main flaw is an invalid inference, not a reduction to its own inputs.

full rationale

The derivation chain is self-contained and does not fit parameters or assume the target result. Theorem 1 proves the compatibility-graph/clique equivalence from Levi's construction rather than importing it as an unverified black box. The SDP relaxation in problem (2) is introduced with explicit constraints, and Lemma 3 derives the universal upper bound n^2 by Cauchy-Schwarz and AM-GM, independently of whether a clique exists. Theorem 4 constructs a feasible SDP solution achieving n^2 when an n-clique exists, and Theorem 5 attempts to prove the separation n(n-1) when no clique exists. The load-bearing step in Theorem 5 is the claim that if all partition-sum vectors share a nonzero coordinate in some component, then the corresponding selected vertex vectors have nonzero pairwise inner products, forcing an n-clique. That inference is mathematically false: two vectors can both have a nonzero coordinate in the same index and still have zero inner product due to cancellation. This is a concrete proof error that invalidates the claimed upper bound, but it is not circularity. No parameter is fitted from data, no prediction is merely a renamed input, no uniqueness theorem is imported from the authors' prior work, and no equation reduces to its own assumption by construction. Therefore the appropriate circularity score is 0.

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

The central claim rests on standard inequalities and the compatibility-graph equivalence, plus one ad hoc assumption in Theorem 5 that is not guaranteed by the SDP constraints. This assumption is load-bearing and is not supported by the proof.

assumptions (4)
  • standard math Cauchy-Schwarz and AM-GM inequalities are valid and apply to the partition-sum vectors w_i
    Used throughout Lemma 3 and Theorem 5 to bound the SDP objective; these are standard mathematical facts.
  • domain assumption The equivalence between graph isomorphism and an n-clique in the compatibility graph is correct
    Theorem 1 restates Levi's known result and serves as the basis of the SDP formulation. The paper provides a proof sketch but relies on prior literature for the construction.
  • standard math A PSD matrix X can be factored as X=UU^T with rows as vector representations, so constraints become inner products
    This is the standard Gram decomposition used in SDP vector programming and is invoked in Section 3.2.
  • ad hoc to paper In Theorem 5, if all partition sums w_i have a nonzero coefficient in the same coordinate, then the corresponding vertex vectors have nonzero pairwise inner products
    This is the contested inference in the proof of Theorem 5. It is not implied by the SDP constraints and is false in general because inner products can cancel across coordinates.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Revisiting the Graph Isomorphism Problem with Semidefinite Programming." pith.science (2026). https://pith.science/paper/45NSLHAJ

@misc{pith2026190806320,
  author       = {Pith},
  title        = {Pith review of: Revisiting the Graph Isomorphism Problem with Semidefinite Programming},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/45NSLHAJ}},
  note         = {Machine review of arXiv:1908.06320}
}
read the original abstract

It is well-known that the graph isomorphism problem can be posed as an equivalent problem of determining whether an auxiliary graph structure contains a clique of specific order. However, the algorithms that have been developed so far for this problem are either not efficient or not exact. In this paper, we present a new algorithm which solves this equivalent formulation via semidefinite programming. Specifically, we show that the problem of determining whether the auxiliary graph contains a clique of specific order can be formulated as a semidefinite programming problem, and can thus be (almost exactly) solved in polynomial time. Furthermore, we show that we can determine if the graph contains such a clique by rounding the optimal solution to the nearest integer. Our algorithm provides a significant complexity result in graph isomorphism testing, and also represents the first use of semidefinite programming for solving this problem.

Figures

Figures reproduced from arXiv: 1908.06320 by the authors.

Figure 1
Figure 1. Two graphs (top left and right) and their compatibility graph (bottom). [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. An optimal solution for the compatibility graph of Figure 1 (top). There are two [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 1
Figure 1. There are two cliques of order 3 in this graph. Therefore, we assign a 2-dimensional [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [1]

    M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., 1979

    work page 1979

  2. [2]

    Graph Isomorphism Is in the Low Hierarchy,

    U. Sch¨ oning, “Graph Isomorphism Is in the Low Hierarchy,” Journal of Computer and System Sciences, vol. 37, no. 3, pp. 312–323, 1988

    work page 1988

  3. [3]

    Canonical Labeling of Graphs,

    L. Babai and E. M. Luks, “Canonical Labeling of Graphs,” in Proceedings of the 15th Annual Symposium on Theory of Computing , pp. 171–183, 1983

    work page 1983

  4. [4]

    Graph Isomorphism Prob- lem,

    V. N. Zemlyachenko, N. M. Korneenko, and R. I. Tyshkevich, “Graph Isomorphism Prob- lem,” Journal of Soviet Mathematics , vol. 29, no. 4, pp. 1426–1481, 1985

    work page 1985

  5. [5]

    Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time,

    E. M. Luks, “Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time,” Journal of Computer and System Sciences , vol. 25, no. 1, pp. 42–65, 1982

    work page 1982

  6. [6]

    Graph Isomorphism in Quasipolynomial Time,

    L. Babai, “Graph Isomorphism in Quasipolynomial Time,” in Proceedings of the 48th An- nual ACM Symposium on Theory of Computing , pp. 684–697, 2016

    work page 2016

  7. [7]

    Linear Time Algorithm for Isomorphism of Planar Graphs,

    J. E. Hopcroft and J.-K. Wong, “Linear Time Algorithm for Isomorphism of Planar Graphs,” in Proceedings of the 6th Annual Symposium on Theory of Computing , pp. 172– 184, 1974

    work page 1974

  8. [8]

    Isomorphism of Graphs with Bounded Eigen- value Multiplicity,

    L. Babai, D. Y. Grigoryev, and D. M. Mount, “Isomorphism of Graphs with Bounded Eigen- value Multiplicity,” inProceedings of the 14th Annual Symposium on Theory of Computing, pp. 310–324, 1982

    work page 1982

Show all 26 references
  1. [9]

    Practical graph isomorphism, ii,

    B. D. McKay and A. Piperno, “Practical graph isomorphism, ii,” Journal of Symbolic Computation, vol. 60, pp. 94–112, 2014

    2014

  2. [10]

    Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs,

    T. Junttila and P. Kaski, “Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs,” in Proceedings of the 9th Workshop on Algorithm Engineering and Experiments, pp. 135–149, 2007. 13

    2007

  3. [11]

    Faster Symmetry Discovery using Sparsity of Symmetries,

    P. T. Darga, K. A. Sakallah, and I. L. Markov, “Faster Symmetry Discovery using Sparsity of Symmetries,” in Proceedings of the 45th Design Automation Conference , pp. 149–154, 2008

    2008

  4. [12]

    On convex relaxation of graph isomorphism,

    Y. Aflalo, A. Bronstein, and R. Kimmel, “On convex relaxation of graph isomorphism,” Proceedings of the National Academy of Sciences , vol. 112, no. 10, pp. 2942–2947, 2015

    2015

  5. [13]

    An O(n3l) primal interior point algorithm for convex quadratic programming,

    D. Goldfarb and S. Liu, “An O(n3l) primal interior point algorithm for convex quadratic programming,” Mathematical Programming, vol. 49, no. 1-3, pp. 325–340, 1990

    1990

  6. [14]

    Replicator Equations, Maximal Cliques, and Graph Isomorphism,

    M. Pelillo, “Replicator Equations, Maximal Cliques, and Graph Isomorphism,” in Advances in Neural Information Processing Systems , pp. 550–556, 1999

    1999

  7. [15]

    A note on the derivation of maximal common subgraphs of two directed or undirected graphs,

    G. Levi, “A note on the derivation of maximal common subgraphs of two directed or undirected graphs,” Calcolo, vol. 9, no. 4, p. 341, 1973

    1973

  8. [16]

    Subgraph isomorphism, matching relational structures and maximal cliques,

    H. G. Barrow and R. M. Burstall, “Subgraph isomorphism, matching relational structures and maximal cliques,” Information Processing Letters, vol. 4, no. 4, pp. 83–84, 1976

    1976

  9. [17]

    A clique problem equivalent to graph isomorphism,

    D. Kozen, “A clique problem equivalent to graph isomorphism,” ACM SIGACT News , vol. 10, no. 2, pp. 50–52, 1978

    1978

  10. [18]

    Enumerating all connected maximal common subgraphs in two graphs,

    I. Koch, “Enumerating all connected maximal common subgraphs in two graphs,” Theo- retical Computer Science, vol. 250, no. 1-2, pp. 1–30, 2001

    2001

  11. [19]

    Subgraph Matching Kernels for Attributed Graphs,

    N. Kriege and P. Mutzel, “Subgraph Matching Kernels for Attributed Graphs,” in Proceed- ings of the 29th International Coference on International Conference on Machine Learning, pp. 291–298, 2012

    2012

  12. [20]

    Gr¨ otschel, L

    M. Gr¨ otschel, L. Lov´ asz, and A. Schrijver,Geometric algorithms and combinatorial opti- mization, vol. 2. Springer Science & Business Media, 2012

    2012

  13. [21]

    Nesterov and A

    Y. Nesterov and A. Nemirovskii, Interior-point polynomial algorithms in convex program- ming, vol. 13. SIAM, 1994

    1994

  14. [22]

    The ellipsoid method and its consequences in combinatorial optimization,

    M. Gr¨ otschel, L. Lov´ asz, and A. Schrijver, “The ellipsoid method and its consequences in combinatorial optimization,” Combinatorica, vol. 1, no. 2, pp. 169–197, 1981

    1981

  15. [23]

    Semidefinite programming,

    L. Vandenberghe and S. Boyd, “Semidefinite programming,” SIAM review, vol. 38, no. 1, pp. 49–95, 1996

    1996

  16. [24]

    Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming,

    M. X. Goemans and D. P. Williamson, “Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming,” Journal of the ACM , vol. 42, no. 6, pp. 1115–1145, 1995

    1995

  17. [25]

    Finding dense subgraphs with semidefinite programming,

    A. Srivastav and K. Wolf, “Finding dense subgraphs with semidefinite programming,” in Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 181–191, 1998

    1998

  18. [26]

    Finding and certifying a large hidden clique in a semiran- dom graph,

    U. Feige and R. Krauthgamer, “Finding and certifying a large hidden clique in a semiran- dom graph,” Random Structures & Algorithms , vol. 16, no. 2, pp. 195–208, 2000. 14

    2000

Pith tools

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