{"id":"db82f0ac-0617-4db7-80c3-e50cb48da879","arxiv_id":"2506.02825","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"OmniMatch provably and asymptotically perfectly aligns unseeded vertices across independent random dot product graphs using only a seed set and shared latent structure, with no edge correlation.","lead":"This paper introduces OmniMatch, an algorithm that uses a small set of known vertex correspondences (seeds) to align the remaining vertices across multiple graphs that share latent structure but have no edge-level correlation.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified.","rationale":"I read the proof line by line. Lemma 2.1's non-asymptotic bound is supported by a detailed perturbation argument in Appendix A.1; the constants and probability tails are consistent. The separation step uses Assumption 1(iii) correctly via a union bound over unseeded pairs, yielding the m^{d/2} u^2 log^{2d}(ms)/s^{d/2} term. The LAP step is valid because, for the relabeled cost matrix M, every diagonal entry is at most 2R and every off-diagonal entry is at least 8R; hence any non-identity permutation replaces at least one diagonal entry by a strictly larger off-diagonal entry in its row, making the identity the unique minimizer. The two failure probabilities combine to p = D'' m^{d/2} u^2 log^{2d}(ms)/s^{d/2} + D' m u / s^2, which tends to 0 for u = s^alpha with alpha < min(2, d/4). I found no internal inconsistency or missing proof step. The reader's conditional verdict is appropriate; the main soft spot is the mismatch between the theorem's assumptions and the simulation distribution, which reinforces the conditionality but does not call the central theorem into question.","tokens_in":22533,"tokens_out":25026,"duration_ms":243182,"concrete_test":"Compute the infimum of x^T y over the support of the Dirichlet(1_{d+1}) projection used in Section 3.1; if the infimum is 0 (as it is on the open simplex), then Assumption 1(i) is violated and the simulations should be reframed as heuristic evidence outside the theorem's hypotheses, or supplemented with runs from a distribution satisfying the assumption, such as a truncated Dirichlet with all coordinates bounded below by epsilon.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central proof of Theorem 2.1 is internally coherent: the OOS error bound (Lemma 2.1), the separation event (Eq. 9), and the row-wise dominance argument for the LAP all check out, and the rates u = s^alpha with alpha < min(2, d/4) follow correctly from the two union-bound terms. The reader's identification of Assumption 1(iii) as the key fragile premise is accurate: without a local-density bound, two unseeded vertices could have identical latent positions and be stochastically indistinguishable, so the claim would fail regardless of algorithm. This is an explicit hypothesis, not a hidden flaw. A secondary, non-correctness concern is that the Dirichlet-simplex distribution used in the Section 3.1 simulations does not satisfy Assumption 1(i) (no uniform delta > 0 lower bound on inner products), so the experiments do not directly exercise the theorem's hypotheses; this limits the scope of the empirical support but does not threaten the theorem's validity.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes OmniMatch, a seeded multiple-graph matching algorithm for Random Dot Product Graphs (RDPGs). The central theoretical result (Theorem 2.1) states that under Assumption 1 (a uniform δ-inner-product bound, full-rank second moment, and a local-density bound on the latent-position distribution F), if s seeds are observed and u = s^α unseeded vertices are to be matched, then for α < min(2, d/4) and fixed m, OmniMatch perfectly aligns all unseeded vertices across all m graphs with probability tending to 1, even though the graphs are conditionally independent given the shared latent positions (i.e., no edge correlation). The proof combines an Omnibus embedding bound for the seeded subgraph, a non-asymptotic least-squares out-of-sample embedding bound (Lemma 2.1, proved in Appendix A.1), a separation event for the unseeded latent positions (Eq. (9)), and a row-wise dominance argument showing the true permutation is the unique solution to each pairwise linear assignment problem. The paper also presents simulations, a shuffled graph hypothesis testing application, and real-data examples from connectomics and machine translation.","tokens_in":22645,"tokens_out":15785,"duration_ms":145853,"significance":"If the theorem is correct, it is a notable first: asymptotically perfect seeded graph matching in RDPGs without any edge correlation, relying instead on heterogeneity correlation induced by shared latent structure. The proof is internally coherent and makes the required assumptions explicit; the paper supplies its own non-asymptotic proof of the out-of-sample embedding bound, and code is provided. The result advances the theoretical understanding of when graph matching is possible beyond correlated Erdős–Rényi and stochastic blockmodel settings, and the shuffled-testing application is practically relevant. The main limitations are the strength of Assumption 1 (especially the uniform δ-inner-product bound and the local-density bound) and the fact that the simulation distribution used in Section 3.1 does not satisfy Assumption 1(i); neither issue undermines the theorem's validity, but they should be addressed in revision.","major_comments":[],"minor_comments":[{"comment":"The simulation model uses latent positions obtained by projecting a Dirichlet(1_{d+1}) random vector onto the first d coordinates, but this distribution does not satisfy Assumption 1(i): because the support includes points arbitrarily close to the simplex boundary, inf_{x,y in supp(F)} x^T y = 0 and no uniform δ > 0 exists. As a consequence, Figures 1–3 and the statement in Section 3.1 that the observed trends 'coincide with our theory' are not direct empirical confirmations of Theorem 2.1's hypotheses. Please either modify the simulation distribution to satisfy Assumption 1 (e.g., by truncating away from the boundary) or explicitly state that the simulations explore behavior outside the theorem's assumptions.","section":"Section 3.1"},{"comment":"The notation in the proof conflates observed positions with true vertex labels: v ∈ U is treated as a true label in Eqs. (8)–(11), whereas the cost matrix C^{(i,j)} in Algorithm 1 is indexed by positions in the observed graphs. The reindexing step using (Q^{(i)})^T C^{(i,j)} Q^{(j)} at the end of the proof is correct, but the earlier statements should clarify that \\hat{w}_{σ(i)}(v) denotes the out-of-sample embedding of true vertex v computed from graph i at its actual position σ(i)(v).","section":"Section 2.1, proof of Theorem 2.1"},{"comment":"In Eq. (9), the term '10dDd' should read '10^d D^d' (powers of d); the current typesetting makes the exponent unclear. Please also check that the factor C(u,2) is carried through consistently in the displayed inequality.","section":"Section 2.1, Eq. (9)"},{"comment":"The proof invokes Lemma 25 of [34] with probability 1 - D_2 n^{-2}; here the relevant sample size is s (the number of seeds), not n. The notation should be made consistent (n vs. s) throughout the appendix.","section":"Appendix A.1, proof of Lemma 2.1"},{"comment":"Step [v] of Algorithm 1 asks the user to solve the multidimensional assignment problem, whereas Theorem 2.1 is proved for the pairwise linear assignment problems in step [iv]. The relation between the two should be stated more explicitly, noting that the theorem guarantees the pairwise solutions are internally consistent with high probability, so MLAP can be replaced by the pairwise variant.","section":"Section 2, Algorithm 1"},{"comment":"The text contains a typo: 'lated positions' should be 'latent positions' in the sentence describing the alternative hypothesis noise. This appears both in Section 3.2 and in the caption of Figure 10.","section":"Sections 3.2 and Appendix B"}],"recommendation":"minor_revision","confidential_remarks":"The paper's central theorem is sound; the reader's concern about Assumption 1(iii) being fragile is valid but it is an explicit hypothesis, not a flaw. The only substantive issue I see is the mismatch between the simulation distribution and Assumption 1(i), which is local and fixable. The paper relies on [32] (coauthored by a co-author) for the OMNI embedding bound, but the out-of-sample result is from [34] (independent group) and the authors provide their own non-asymptotic proof, so there is no circularity concern. The paper is a solid contribution appropriate for a statistics/ML venue."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe main result is real. OmniMatch, using OMNI embedding of the seeded subgraph, out-of-sample least-squares embeddings, and a linear assignment problem, provably recovers the full matching for u = s^alpha unseeded vertices with alpha < min(2, d/4) even when the m graphs are independent given the latent positions. That is genuinely new: prior perfect-matching guarantees needed edge correlation, and prior no-correlation results only got o(n) error in graphon settings. For RDPGs this is the first asymptotic exactness result without edge correlation, and it works because heterogeneity correlation substitutes for edge correlation.\n\nThe proof is solid. Lemma 2.1 gives a uniform non-asymptotic bound on the OOS embedding error across u vertices and m graphs; they adapt the out-of-sample theorem of Levin et al. to get a non-asymptotic form with a union bound, which is the kind of detail that separates workable theory from hand-waving. The separation bound (Eq. 9) from Assumption 1(iii) and the row-wise dominance argument in the LAP cost matrix are clean. The probability bound with the two terms follows. The paper also correctly notes the constants may be large in d, and the rate degrades for larger d despite larger allowed alpha. Citation practice is fair: the OMNI bound is co-authored, but the OOS machinery is independent and they prove their own non-asymptotic version.\n\nSoft spots are real but minor. The simulations use the Dirichlet-simplex latent distribution, which violates Assumption 1(i): the delta-inner-product lower bound fails because latent positions can be arbitrarily close to orthogonal corners. The experiments therefore do not directly exercise the theorem's hypotheses. They show the algorithm works beyond the stated assumptions, which is fine, but it should be acknowledged. The testing-power experiments lack error bars and an oracle-alignment baseline, so it's hard to know how much of the power recovery is OmniMatch versus noise. Both are fixable in revision.\n\nThe real-data parts on connectomics and English-Zulu are useful illustrations, not the main event. I would be happy to referee this; it deserves a serious read and should be published after minor revision.","headline":"First proof of asymptotically perfect seeded graph matching without edge correlation in RDPGs, with a coherent argument; simulations don't match the theorem's assumptions but that's fixable.","tokens_in":23203,"tokens_out":2702,"would_cite":true,"duration_ms":27050,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80"],"pacs":[],"model":"deepseek-v4-flash","headline":"In random dot product graphs, OmniMatch perfectly matches all unseeded vertices across multiple networks with probability tending to one even when edges are independent across graphs.","keywords":["seeded graph matching","random dot product graphs","Omnibus embedding","out-of-sample embedding","linear assignment problem","no edge correlation","graph hypothesis testing","vertex misalignment"],"falsifier":"Simulate JRDPG graphs from a smooth, full-rank $F$ (for example the Dirichlet projection used in the paper) with $s = 100, 400, 1600$ seeds and $u = s^{1.5}$ unseeded vertices in $d = 10$, and record whether OmniMatch's LAP output is exactly the true permutation in every one of many trials; Theorem 2.1 predicts the failure probability tends to 0, so any visible non-vanishing failure rate would refute the claim. A sharper check is to estimate the separation event in Eq. 9: if $\\min_{v \\ne w} \\|X_v - X_w\\|$ frequently falls below $10D m^{1/2} \\log^2(ms)/\\sqrt{s}$, the proof's key condition fails.","tokens_in":22305,"feed_emoji":"🧩","tokens_out":8038,"duration_ms":76230,"temperature":0.7,"pith_summary":"This paper introduces OmniMatch, an algorithm for matching vertices across several networks when only a subset of correspondences, the seeds, is known in advance. In the Random Dot Product Graph model, where each vertex carries a latent vector in $\\mathbb{R}^d$ and edges are independent Bernoulli draws from inner products of those vectors, the paper proves that OmniMatch perfectly aligns every unseeded vertex across all networks with probability tending to 1, even though the edges of different networks are completely independent, so there is no edge correlation to anchor the match. The number of unseeded vertices that can be aligned grows like $s^\\alpha$ for $\\alpha < \\min(2, d/4)$, where $s$ is the number of seeds, as long as the latent-position distribution is spread out and full rank. This matters because most prior matching theory required correlated edges, while real network collections often have unaligned vertices and shared but uncorrelated structure. The paper also shows that the alignment step restores lost power in two-sample graph hypothesis tests after random shuffling of vertex labels, in simulations, connectomics data, and an English–Zulu sentence alignment task.","feed_headline":"Seeded graph matching goes perfect with zero edge correlation","feed_subtitle":"A joint-embedding algorithm aligns O(s^alpha) unseeded vertices using only shared latent structure, no edge correlation.","key_machinery":"The load-bearing mechanism is the pairing of a joint embedding with a separation bound. OmniMatch first applies the Omnibus Joint Embedding (OMNI) to the $m$ seeded induced subgraphs, producing a common latent-position estimate for the seeds; each unseeded vertex is then embedded out-of-sample by least squares against the seeded embedding. For each pair of graphs $(i,j)$ it forms the $u \\times u$ cost matrix $C^{(i,j)}_{v,w} = \\| \\hat{w}_{\\sigma(i)}(v) - \\hat{w}_{\\sigma(j)}(w) \\|$ and solves the linear assignment problem $\\arg\\min_{Q\\in\\Pi_u} \\operatorname{tr}(C^{(i,j)}Q)$. The theorem's probability bound comes from two events: all out-of-sample embeddings are within radius $O(m^{1/2}\\log(ms)/\\sqrt{s})$ of the true rotated latent position, and Assumption 1(iii) guarantees the unseeded latent positions are mutually separated by at least $10D m^{1/2}\\log^2(ms)/\\sqrt{s}$ with high probability. Because the within-vertex distances are smaller than the between-vertex distances by a constant factor, the true permutation is the unique LAP solution.","core_discovery":"On its own terms, the paper's central claim is Theorem 2.1: for a $d$-dimensional Joint Random Dot Product Graph with latent positions i.i.d. from a distribution $F$ satisfying Assumption 1 (inner products bounded away from 0 and 1, full-rank second moment, and a local density bound), OmniMatch with $s$ seeds and $u = s^\\alpha$ unseeded vertices, $\\alpha < \\min(2, d/4)$ and $m$ fixed, perfectly recovers every unseeded correspondence across all $m$ graphs simultaneously. The success probability is at least $1 - D'' m^{d/2} u^2 \\log^{2d}(ms) / s^{d/2} - D' m u / s^2$, which tends to 1 in the stated regime. The alignment is achieved by jointly embedding only the seeded vertices, embedding each unseeded vertex into that common space via least-squares out-of-sample extension, and then solving the linear assignment problem on pairwise embedded distances; the proof shows the true assignment is the unique minimizer because the embedding error is smaller than the typical distance between distinct latent positions.","pith_inferences":["Editorial inference: the local-separation assumption is not a technical convenience; if $F$ puts atoms or clusters at the same latent position, no embedding-based procedure can tell those vertices apart, suggesting an information-theoretic limit near the theorem's boundary.","Editorial inference: the proof's union bound over $u^2$ pairs is what sets the $\\alpha < d/4$ rate; sharper concentration for the embedded distances might push the rate toward $d/2$ without changing the algorithm.","Editorial inference: the same argument should carry over to generalized random dot product graphs and to latent-position graphons with smooth densities, since only the inner-product identifiability and local density bounds are used; the authors note the generalized-RDPG extension themselves.","Editorial inference: a direct testable extension is to vary the smoothness of $F$, for example by mixing a uniform component with a small point mass, and measure where OmniMatch's exact alignment rate breaks; the break should coincide with the separation event failing."],"forward_implications":["In the RDPG setting, perfect seeded matching no longer requires edge correlation: shared latent structure alone is enough when the latent positions are spread out and seeds are plentiful.","With $m$ and $d$ fixed, the algorithm aligns $u = s^\\alpha$ unseeded vertices for any $\\alpha < \\min(2, d/4)$, so the number of recoverable vertices grows polynomially in the number of seeds.","When $m = 2$ the alignment step is a linear assignment problem solvable in $O(u^3)$ time, and the paper shows that pairwise solutions compose consistently across more than two graphs with probability tending to 1.","Using OmniMatch as a preprocessing step before two-sample graph hypothesis tests recovers testing power lost when vertex labels are shuffled, and the same pipeline helps detect anomalous graphs in a collection and align connectome or parallel-sentence networks."],"supporting_citations":[{"why":"supplies the Omnibus joint embedding and the two-to-infinity row-wise error bound for the seeded subgraphs used in Lemma 1.1","marker":"[32]"},{"why":"supplies the least-squares out-of-sample embedding heuristic and the row-wise error bound for out-of-sample vertices used in Lemma 2.1","marker":"[34]"},{"why":"provides the matrix perturbation analysis (Theorem 5.3.1) that the appendix adapts to get the non-asymptotic out-of-sample error bound","marker":"[25]"},{"why":"defines heterogeneity correlation and alignment strength, the quantities that explain why matching can succeed with zero edge correlation","marker":"[21]"}],"fun_headline_variants":["Perfect seeded graph matching without any edge correlation","OmniMatch: perfect alignment of unseeded vertices from seeds","Seeds alone perfectly align graphs with no edge correlation","Joint embedding yields perfect seeded matching at scale","Perfect vertex recovery in seeded graphs without edge correlation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that latent positions are well spread out—no two unseeded vertices may have nearly identical latent vectors—because the local density bound is what guarantees the embedding errors are smaller than the gaps between distinct vertices.","fun_headline_variants_meta":{"raw":{"variants":["Perfect seeded graph matching without any edge correlation","OmniMatch: perfect alignment of unseeded vertices from seeds","Seeds alone perfectly align graphs with no edge correlation","Joint embedding yields perfect seeded matching at scale","Perfect vertex recovery in seeded graphs without edge correlation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000185,"raw_usage":{"total_tokens":1318,"prompt_tokens":937,"completion_tokens":381,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":553,"completion_tokens_details":{"reasoning_tokens":307}},"tokens_in":553,"tokens_out":381,"duration_ms":3765,"temperature":1.0,"reasoning_tokens":307,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T11:16:26.201777+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate JRDPG graphs from a smooth, full-rank $F$ (for example the Dirichlet projection used in the paper) with $s = 100, 400, 1600$ seeds and $u = s^{1.5}$ unseeded vertices in $d = 10$, and record whether OmniMatch's LAP output is exactly the true permutation in every one of many trials; Theorem 2.1 predicts the failure probability tends to 0, so any visible non-vanishing failure rate would refute the claim. A sharper check is to estimate the separation event in Eq. 9: if $\\min_{v \\ne w} \\|X_v - X_w\\|$ frequently falls below $10D m^{1/2} \\log^2(ms)/\\sqrt{s}$, the proof's key condition fails.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the least-squares out-of-sample embedding heuristic and the row-wise error bound for out-of-sample vertices used in Lemma 2.1"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the matrix perturbation analysis (Theorem 5.3.1) that the appendix adapts to get the non-asymptotic out-of-sample error bound"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"defines heterogeneity correlation and alignment strength, the quantities that explain why matching can succeed with zero edge correlation"}],"review_version":1}