{"id":"4ffe12b1-17bc-471a-afa0-7492b1700bf3","arxiv_id":"1908.06320","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The authors propose an SDP relaxation of the clique formulation of graph isomorphism and claim that its optimal value either reaches n^2 or falls to n(n-1), giving a polynomial-time test.","lead":"The paper claims a new polynomial-time semidefinite programming test for graph isomorphism based on cliques in a compatibility graph. The main theorem that would make the test exact depends on an unproven inference about vector representations.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5's upper bound rests on a false inference: shared nonzero coordinate does not imply nonzero inner product, so the n(n−1) separation from n^2 is unproved.","rationale":"The paper's algorithm hinges on Theorem 5: to decide isomorphism it needs a strict separation between the SDP value when an n-clique exists (n^2) and when none exists (claimed ≤ n(n−1)). The proof's only mechanism for the upper bound is the assertion that shared nonzero coordinate across all n partition-sum vectors forces pairwise adjacent vertices, hence an n-clique. This is algebraically false because an inner product is a sum and can cancel. Thus the proof does not rule out SDP values in (n(n−1), n^2) for non-isomorphic pairs. This is a load-bearing gap, not a stylistic issue. I agree with the reader's weakest_assumption. The correct parts (Lemma 2, Lemma 3, Theorem 4 for the positive direction) do not repair it. An exhaustive SDP search on small graphs would either exhibit a counterexample or suggest the theorem might be salvageable, but as written the result is unproven. Therefore the reader's REJECT verdict is unchanged.","tokens_in":12574,"tokens_out":23266,"duration_ms":261309,"concrete_test":"Solve problem (2) to high precision (e.g., with CVX/MOSEK) for all pairs of non-isomorphic graphs on n=3 and n=4 vertices, computing the compatibility graph of Section 2; check whether any no-clique instance has SDP optimum > n(n−1). A single such instance falsifies Theorem 5 and the algorithm. As a direct check of the disputed inference, also test the vector pattern v1=(1,1), v2=(1,-1) in two partitions: both coordinates are nonzero but the inner product is zero, so the claimed forced clique does not materialize.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In the proof of Theorem 5, after the Cauchy-Schwarz equality case, the authors argue that if w1,...,wn are pairwise linearly dependent and w1 has a nonzero i-th coordinate, then all n partitions contain a vertex whose vector has a nonzero i-th coordinate, and that \"the inner product of every pair of these vectors is nonzero,\" yielding an n-clique. This is false: inner products can cancel. For example, v1=(1,1) and v2=(1,-1) both have nonzero first coordinate yet ⟨v1,v2⟩=0. Therefore the conclusion that every coordinate has at most n−1 nonzero values among w1,...,wn does not follow, and the bound z_i ≤ (n−2)Σ(w^i_j)^2 in Eq. (9) is unsupported. Since the claimed gap between n(n−1) and n^2, and hence the polynomial-time decision procedure by comparing the SDP value with n^2, depends entirely on this step, the central claim is not established. Independently of whether the theorem happens to be true for compatibility graphs, the proof as written has a concrete invalid inference.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":12768,"tokens_out":22718,"duration_ms":205675,"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":[{"comment":"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.","section":"§3.2, proof of Theorem 5"},{"comment":"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.","section":"§3.2, proof of Theorem 5"}],"minor_comments":[{"comment":"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.","section":"Section 3.2, Eq. (3) and similar expressions"},{"comment":"'Fugure 2' is a typo for 'Figure 2'.","section":"Figure 2 caption"},{"comment":"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.","section":"Abstract and introduction"},{"comment":"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.","section":"Section 2.3"}],"recommendation":"reject","confidential_remarks":"The paper claims a major open problem has been solved, but the proof of the main upper bound (Theorem 5) contains a clear false inference about inner products and shared coordinates. This is not a local presentation issue; it invalidates the central decision procedure. I see no straightforward way to repair the proof without a substantially new idea, so rejection is appropriate unless the authors can supply a correct proof in a revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear Colleague,\n\nThe one-line summary: this paper proposes an SDP relaxation for graph isomorphism whose main separation theorem (Theorem 5) rests on a false inference, so the result is not established.\n\nThe SDP formulation itself is a natural relaxation of the standard clique formulation, and the paper correctly recalls the Levi/Kozen equivalence between isomorphism and finding an n-clique in the compatibility graph. The construction in Theorem 4, showing that an optimal value n^2 is achievable when n-cliques exist, is correct. What's missing is a valid proof that the SDP value is at most n(n-1) when no such clique exists.\n\nThe problem is in the proof of Theorem 5. The authors define w_i as the sum of the vertex vectors in partition i. Under the assumption that equality holds in the Cauchy-Schwarz chain, the w_i are pairwise linearly dependent. Then from shared nonzero coordinates they claim the corresponding vertex vectors have pairwise nonzero inner products, and hence form a clique. That is false: two vectors can both be nonzero in the same coordinate and still be orthogonal, as in (1,1) and (1,-1). So the existence of an n-clique does not follow. The subsequent bound on z_i, which relies on at least one zero coordinate per component, is therefore unsupported. Without that bound, there is no gap between n(n-1) and n^2, and the algorithm cannot decide isomorphism.\n\nThe paper also overstates novelty by calling itself the first SDP solution to GI, despite discussing the Lovász theta SDP in Section 2.3.\n\nI'd like to see the authors address this gap before taking the paper further. As written, the central claim is unsupported, and I would not recommend accepting it for publication.\n\nBest,\n[Your name]","headline":"Theorem 5's proof contains a false inference about nonzero coordinates and inner products, so the claimed polynomial-time graph isomorphism algorithm is unsupported.","tokens_in":13267,"tokens_out":5310,"would_cite":false,"duration_ms":50261,"reading_group":"no","serious_thinker":"yes","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C60","05C69","68Q25","90C22"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims graph isomorphism can be decided by solving one semidefinite program and comparing its optimum with n-squared.","keywords":["graph isomorphism","semidefinite programming","compatibility graph","clique detection","convex relaxation","polynomial-time algorithm","Gram matrix"],"falsifier":"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.","tokens_in":12363,"feed_emoji":"🧩","tokens_out":12843,"duration_ms":117637,"temperature":0.7,"pith_summary":"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.","feed_headline":"One SDP value can decide graph isomorphism","feed_subtitle":"An n-clique in the compatibility graph forces the SDP to n-squared; without one, the value drops to n(n−1).","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the compatibility-graph clique criterion that turns graph isomorphism into an $n$-clique test.","marker":"[15]"},{"why":"States the clique formulation of graph isomorphism, grounding the problem transformation.","marker":"[17]"},{"why":"Provides the polynomial-time interior-point algorithm used to solve the SDP to within any fixed additive error.","marker":"[21]"},{"why":"Gives strong duality for the SDP, used to justify the polynomial approximation step.","marker":"[23]"},{"why":"Earlier continuous-optimization heuristic for the same compatibility-graph clique problem, the baseline the paper compares against.","marker":"[14]"}],"fun_headline_variants":["SDP value gap solves graph isomorphism exactly","Sharp SDP threshold decides GI in polynomial time","First SDP solver for graph isomorphism","From clique to SDP: exact GI in polynomial time"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["SDP value gap solves graph isomorphism exactly","Sharp SDP threshold decides GI in polynomial time","First SDP solver for graph isomorphism","From clique to SDP: exact GI in polynomial time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000499,"raw_usage":{"total_tokens":2406,"prompt_tokens":868,"completion_tokens":1538,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":484,"completion_tokens_details":{"reasoning_tokens":1492}},"tokens_in":484,"tokens_out":1538,"duration_ms":10188,"temperature":1.0,"reasoning_tokens":1492,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:51:12.005511+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"A note on the derivation of maximal common subgraphs of two directed or undirected graphs,","cited_arxiv_id":null,"evidence_quote":"Supplies the compatibility-graph clique criterion that turns graph isomorphism into an $n$-clique test."},{"cited_title":"A clique problem equivalent to graph isomorphism,","cited_arxiv_id":null,"evidence_quote":"States the clique formulation of graph isomorphism, grounding the problem transformation."},{"cited_title":"Nesterov and A","cited_arxiv_id":null,"evidence_quote":"Provides the polynomial-time interior-point algorithm used to solve the SDP to within any fixed additive error."},{"cited_title":"Semidefinite programming,","cited_arxiv_id":null,"evidence_quote":"Gives strong duality for the SDP, used to justify the polynomial approximation step."},{"cited_title":"Replicator Equations, Maximal Cliques, and Graph Isomorphism,","cited_arxiv_id":null,"evidence_quote":"Earlier continuous-optimization heuristic for the same compatibility-graph clique problem, the baseline the paper compares against."}],"review_version":1}