Pith. sign in

REVIEW 6 minor 78 references

Asymptotically perfect seeded graph matching without edge correlation (and applications to inference)

T0 review · 0 major / 6 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 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.

desk verdict 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. read the letter →

arxiv 2506.02825 v2 pith:KEFGIWI2 submitted 2025-06-03 stat.ML cs.LG

Tong Qi , Vera Andersson , Peter Viechnicki , Vince Lyzinski This is my paper
classification stat.MLcs.LG MSC 05C80
keywords seededgraphmatchingrandomdotproductgraphsOmnibusembeddingout-of-samplelinearassignmentproblemnoedgecorrelationhypothesistestingvertexmisalignment
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 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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
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

0 major / 6 minor

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.

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.

minor comments (6)
  1. [Section 3.1] 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.
  2. [Section 2.1, proof of Theorem 2.1] 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).
  3. [Section 2.1, Eq. (9)] 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.
  4. [Appendix A.1, proof of Lemma 2.1] 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.
  5. [Section 2, Algorithm 1] 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.
  6. [Sections 3.2 and Appendix B] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the perfect-matching theorem follows from explicit latent-position assumptions and independent or carefully adapted embedding bounds, not from a fitted parameter or self-referential definition.

full rationale

The derivation chain for Theorem 2.1 is self-contained in the relevant sense. The proof combines Lemma 2.1's out-of-sample embedding concentration bound (Eqs. 7-8) with the Assumption 1(iii) separation event (Eq. 9) to show that, after a suitable rotation, each unseeded vertex's embedded copies across graphs lie within a small ball while different vertices' balls are well separated (Eqs. 10-11). The diagonal/off-diagonal dominance of the LAP cost matrix then forces the identity matching, which is a direct mathematical consequence rather than an equivalence with the theorem's conclusion. Lemma 2.1 is proved in Appendix A.1 from Theorem A.1 and follows the independent JMLR result of Levin et al. [34]; the paper explicitly supplies the non-asymptotic adaptation ('does require some nontrivial work; for the proof of the result, see Appendix A.1'). The OMNI embedding bound in Lemma 1.1 is cited from [32], which includes a co-author, but it is a general spectral-embedding consistency statement with stated assumptions that do not include the target result; it is not fitted to this paper's data and does not by itself assert that graph matching is possible. No parameter is fitted to a subset of data and then renamed as a prediction, and no uniqueness theorem from the authors' prior work is invoked to forbid alternatives. The Dirichlet-simplex simulations in Section 3.1 likely do not satisfy the delta-inner-product part of Assumption 1, which limits how directly the experiments exercise the theorem's hypotheses, but a gap between simulations and assumptions is a scope concern, not circularity.

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

The central claim rests on the JRDPG model, Assumption 1 (especially the local density bound iii), and external spectral embedding lemmas. The local density bound is the most fragile premise because it directly controls the separation of unseeded latent positions, which is what makes the assignment problem solvable. The paper does not introduce any new physical or mathematical entities.

assumptions (7)
  • domain assumption The observed graphs are generated as a Joint RDPG with shared latent positions X and conditionally independent edges given X (Definition 1.1).
    This defines the no-edge-correlation setting and is the model under which all theory is developed. The shared latent positions provide the heterogeneity correlation that drives the matching.
  • domain assumption Assumption 1(i): delta-inner product property, i.e., there is delta > 0 such that delta <= x^T y <= 1 - delta for all x,y in supp(F).
    Ensures edge probabilities are bounded away from 0 and 1, used in the out-of-sample embedding proof (e.g., Hoeffding bounds, non-zero vertex degrees).
  • domain assumption Assumption 1(ii): E(YY^T) has rank d for Y ~ F.
    Needed for identifiability of latent positions and for the spectral embedding bound in Lemma A.1 to hold with spectral gap.
  • domain assumption Assumption 1(iii): there exists c_d > 0 such that P_F(X in B_r(x)) <= c_d r^d for all x.
    Load-bearing for Eq. (9): it bounds the probability that two unseeded latent positions are close, enabling the separation argument. Without this, the perfect-matching guarantee can fail.
  • domain assumption Lemma 1.1 from [32] (OMNI embedding 2-to-infinity bound), stated in Eq. (2).
    External result on joint embedding consistency used as a black box. It provides the uniform error rate for the seed-induced Omnibus embedding.
  • domain assumption Lemma 25 from [34] (angle bound cos(theta) >= gamma) used in the proof of Lemma 2.1.
    External result on the angle between the residual vector and the column space of the latent position matrix, needed to bound the OOS embedding error in Appendix A.1.
  • domain assumption The seed vertices S = {1,...,s} are correctly aligned across all graphs and their induced subgraphs are RDPG with i.i.d. latent positions from F.
    This is the seeded matching setup; the algorithm and theory assume seed correspondences are known and error-free.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Asymptotically perfect seeded graph matching without edge correlation (and applications to inference)." pith.science (2026). https://pith.science/paper/KEFGIWI2

@misc{pith2026250602825,
  author       = {Pith},
  title        = {Pith review of: Asymptotically perfect seeded graph matching without edge correlation (and applications to inference)},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KEFGIWI2}},
  note         = {Machine review of arXiv:2506.02825}
}
abstract

We present the OmniMatch algorithm for seeded multiple graph matching. In the setting of $d$-dimensional Random Dot Product Graphs (RDPG), we prove that under mild assumptions, OmniMatch with $s$ seeds asymptotically and efficiently perfectly aligns $O(s^{\alpha})$ unseeded vertices -- for $\alpha<2\wedge d/4$ -- across multiple networks even in the presence of no edge correlation. We demonstrate the effectiveness of our algorithm across numerous simulations and in the context of shuffled graph hypothesis testing. In the shuffled testing setting, testing power is lost due to the misalignment/shuffling of vertices across graphs, and we demonstrate the capacity of OmniMatch to correct for misaligned vertices prior to testing and hence recover the lost testing power. We further demonstrate the algorithm on a pair of data examples from connectomics and machine translation.

Figures

Figures reproduced from arXiv: 2506.02825 by the authors.

Figure 1
Figure 1. The proportion of correctly unshuffled vertices for [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗
Figure 2
Figure 2. The proportion of correctly unshuffled vertices for [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
Figure 3
Figure 3. Graph matching accuracies on the graph with [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Pairwise distances among 10 RDPG with n = 500 nodes and u = 120 (top) or u = 400 (bottom) shuffled vertices using OmniMatch. The noise with err = 0.05 is added to 80 randomly selected vertices in one randomly chosen graph. The left panels show pairwise distances comput…
Figure 5
Figure 5. Figure 5: Statistical power for two-sample graph hypothesis testing under node shuffling. Each [PITH_FULL_IMAGE:figures/full_fig_p017_5.png]
Figure 6
Figure 6. Figure 6: Pairwise distance heatmaps among 100 brain scans. A total of 10 subjects, each with 10 [PITH_FULL_IMAGE:figures/full_fig_p019_6.png]
Figure 7
Figure 7. Figure 7: Graph matching accuracies for both LAP and [PITH_FULL_IMAGE:figures/full_fig_p020_7.png]
Figure 8
Figure 8. Figure 8: The proportion of correctly unshuffled vertices for [PITH_FULL_IMAGE:figures/full_fig_p033_8.png]
Figure 9
Figure 9. Figure 9: Precision plots for the proportion of correctly unshuffled vertices with [PITH_FULL_IMAGE:figures/full_fig_p034_9.png]
Figure 10
Figure 10. Figure 10: Statistical power for two-sample graph hypothesis testing under node shuffling. Each [PITH_FULL_IMAGE:figures/full_fig_p035_10.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

78 extracted references · 71 canonical work pages

  1. [1]

    On Two Distinct Sources of Nonidentifiability in Latent Position Random Graph Models

    J. Agterberg, M. Tang, and C. E. Priebe. On two distinct sources of nonidentifiability in latent position random graph models. arXiv preprint arXiv:2003.14250 , 2020

    work page Pith review arXiv 2003

  2. [2]

    Statistical inference for low-rank tensors: Het- eroskedasticity, subgaussianity, and applications

    Joshua Agterberg and Anru Zhang. Statistical inference for low-rank tensors: Het- eroskedasticity, subgaussianity, and applications. arXiv preprint arXiv:2410.06381 , 2024. 21

    arXiv 2024

  3. [3]

    A. A. Alyakin, J. Agterberg, H. S. Helm, and C. E. Priebe. Correcting a nonparametric two-sample graph hypothesis test for graphs with different numbers of vertices with applications to connectomics. Applied Network Science , 9(1):1, 2024

    work page 2024

  4. [4]

    Arroyo, A

    J. Arroyo, A. Athreya, J. Cape, G. Chen, Priebe C. E., and J. T. Vogelstein. Inference for multiple heterogeneous networks with a common invariant subspace.Journ. of Mach. Learn. Res., 22:1–49, 2021

    work page 2021

  5. [5]

    Asta and C

    D. Asta and C. R. Shalizi. Geometric network comparison. In M. Meila and T. Haskes, editors, Proc. of the 31st Conf. on Uncertainty in Artificial Intelligence , pages 102–110, 2015

    work page 2015

  6. [6]

    Athreya, D

    A. Athreya, D. E. Fishkind, K. Levin, , V. Lyzinski, Y. Park, Y. Qin, D. L. Sussman, M. Tang, J. T. Vogelstein, and C. E. Priebe. Statistical inference on random dot product graphs: a survey. Journal of Machine Learning Research , 18, 2018

    work page 2018

  7. [7]

    Marta Ba˜ n´ on, Pinzhen Chen, Barry Haddow, Kenneth Heafield, Hieu Hoang, Miquel Espl` a-Gomis, Mikel L. Forcada, Amir Kamran, Faheem Kirefu, Philipp Koehn, Sergio Ortiz Rojas, Leopoldo Pla Sempere, Gema Ram ´ ırez-S´ anchez, Elsa Sarr ´ ıas, Marek Str- elec, Brian Thompson, William Waites, Dion Wiggins, and Jaume Zaragoza. ParaCrawl: Web-scale acquisiti...

    work page 2020

  8. [8]

    Barak, C

    B. Barak, C. Chou, Z. Lei, T. Schramm, and Y. Sheng. (nearly) efficient algorithms for the graph matching problem on correlated random graphs. Adv. in Neural Infor. Proc. Sys., 32:9190–9198, 2019

    work page 2019

Show all 78 references
  1. [9]

    Bento and S

    J. Bento and S. Ioannidis. A family of tractable graph distances. In Proceedings of the 2018 SIAM International Conference on Data Mining , pages 333–341. SIAM, 2018

    2018

  2. [10]

    Chatterjee

    S. Chatterjee. Matrix estimation by universal singular value thresholding. The Annals of Statistics , 43:177–214, 2014

    2014

  3. [11]

    Estimating graph dimension with cross-validated eigenvalues

    Fan Chen, Sebastien Roch, Karl Rohe, and Shuqi Yu. Estimating graph dimension with cross-validated eigenvalues. arXiv preprint arXiv:2108.03336 , 2021

    2021

  4. [12]

    Chung, R

    J. Chung, R. Lawrence, A. Loftus, D. Pisner, G. Kiar, E. W. Bridgeford, W. G. Roncal, Consortium for Reliability, Reproducibility (CoRR), V. Chandrashekhar, D. Mhem- bere, et al. A low-resource reliable pipeline to democratize multi-modal connectome estimation and analysis. bi...

    2021

  5. [13]

    Conte, P

    D. Conte, P. Foggia, C. Sansone, and M. Vento. Thirty years of graph matching in pattern recognition. Int. journal of pattern recognition and artificial intelligence , 18(03):265–298, 2004. 22

    2004

  6. [14]

    Cullina and N

    D. Cullina and N. Kiyavash. Improved achievability and converse bounds for erdos-r´ enyi graph matching. ACM SIGMETRICS Performance Evaluation Review , 44(1):63–72, 2016

    2016

  7. [15]

    Cullina and N

    D. Cullina and N. Kiyavash. Exact alignment recovery for correlated erdos renyi graphs. arXiv preprint arXiv:1711.06783 , 2017

    2017 arXiv

  8. [16]

    Hypothesis testing for equality of latent positions in random graphs

    Xinjie Du and Minh Tang. Hypothesis testing for equality of latent positions in random graphs. Bernoulli, 29(4):3221–3254, 2023

    2023

  9. [17]

    Fifty years of graph match- ing, network alignment and network comparison

    Frank Emmert-Streib, Matthias Dehmer, and Yongtang Shi. Fifty years of graph match- ing, network alignment and network comparison. Information sciences , 346:180–197, 2016

    2016

  10. [18]

    Z. Fan, C. Mao, Y. Wu, and J. Xu. Spectral graph matching and regularized quadratic relaxations: Algorithm and theory. In Int. Conf. on Machine Learning , pages 2985–

  11. [19]

    Functional connectome fingerprinting: identifying individuals using patterns of brain connectivity

    Emily S Finn, Xilin Shen, Dustin Scheinost, Monica D Rosenberg, Jessica Huang, Mar- vin M Chun, Xenophon Papademetris, and R Todd Constable. Functional connectome fingerprinting: identifying individuals using patterns of brain connectivity. Nature neu- roscience, 18(11):1664–1...

    2015

  12. [20]

    D. E. Fishkind, S. Adali, H. G. Patsolic, L. Meng, D. Singh, V. Lyzinski, and C. E. Priebe. Seeded graph matching. Pattern recognition, 87:203–215, 2019

    2019

  13. [21]

    D. E. Fishkind, L. Meng, A. Sun, C. E. Priebe, and V. Lyzinski. Alignment strength and correlation for graphs. Pattern Recognition Letters, 125:295–302, 2019

    2019

  14. [22]

    D. E. Fishkind, F. Parker, H. Sawczuk, L. Meng, E. Bridgeford, A. Athreya, C. Priebe, and V. Lyzinski. The phantom alignment strength conjecture: practical use of graph matching alignment strength to indicate a meaningful graph match. Applied Network Science, 6(1):1–27, 2021

    2021

  15. [23]

    Two-sample hypothesis testing for inhomogeneous random graphs

    Debarghya Ghoshdastidar, Maurilio Gutzeit, Alexandra Carpentier, and Ulrike Von Luxburg. Two-sample hypothesis testing for inhomogeneous random graphs. The Annals of Statistics , 48(4):2208–2229, 2020

    2020

  16. [24]

    Practical methods for graph two- sample testing

    Debarghya Ghoshdastidar and Ulrike Von Luxburg. Practical methods for graph two- sample testing. Advances in Neural Information Processing Systems , 31, 2018

    2018

  17. [25]

    G. H. Golub and C. F. Van Loan. Matrix computations. JHU press, 2013

    2013

  18. [26]

    N. A. Heard, D. J. Weston, K. Platanioti, and D. J. Hand. Bayesian anomaly detection methods for social networks. Annals of Applied Statistics , 4:645–662, 2010

    2010

  19. [27]

    P. D. Hoff, A. E. Raftery, and M. S. Handcock. Latent space approaches to social network analysis. Journal of the American Statistical Association , 97(460):1090–1098, 2002. 23

    2002

  20. [28]

    Community detection on mixture multi-layer networks via regularized tensor decomposition

    Bing-Yi Jing, Ting Li, Zhongyuan Lyu, and Dong Xia. Community detection on mixture multi-layer networks via regularized tensor decomposition. arXiv preprint arXiv:2002.04457, 2020

    2002 arXiv

  21. [29]

    Josephs, W

    N. Josephs, W. Li, and E. D. Kolaczyk. Network recovery from unlabeled noisy samples. In 2021 55th Asilomar Conference on Signals, Systems, and Computers , pages 1268–

    2021

  22. [30]

    E. D. Kolaczyk, L. Lin, S. Rosenberg, J. Walters, and J. Xu. Averages of unlabeled networks: Geometric characterization and asymptotic behavior. Ann. Statist. 48(1): 514-538, 2020

    2020

  23. [31]

    H. W. Kuhn. The Hungarian method for the assignment problem. Naval Research Logistic Quarterly, 2:83–97, 1955

    1955

  24. [32]

    Levin, A

    K. Levin, A. Athreya, M. Tang, V. Lyzinski, Y. Park, and C. E. Priebe. A central limit theorem for an omnibus embedding of multiple random graphs and implications for multiscale network inference. arXiv preprint arXiv:1705.09355 , 2017

    2017 arXiv

  25. [33]

    Levin and E

    K. Levin and E. Levina. Bootstrapping networks with latent space structure. Electronic Journal of Statistics , 19(1):745–791, 2025

    2025

  26. [34]

    K. D. Levin, F. Roosta, M. Tang, M. W. Mahoney, and C. E. Priebe. Limit theorems for out-of-sample extensions of the adjacency and laplacian spectral embeddings. Journal of Machine Learning Research, 22(194):1–59, 2021

    2021

  27. [35]

    Lyzinski

    V. Lyzinski. Information recovery in shuffled graphs via graph matching. IEEE Trans- actions on Information Theory , 64(5):3254–3273, 2018

    2018

  28. [36]

    Lyzinski, D.E

    V. Lyzinski, D.E. Fishkind, and C.E. Priebe. Seeded graph matching for correlated Erd¨ os-R´ enyi graphs.Journ. of Mach. Learn. Res. , 15:3513–3540, 2014

    2014

  29. [37]

    Lyzinski, D

    V. Lyzinski, D. L. Sussman, M. Tang, A. Athreya, and C. E. Priebe. Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding. Electronic Journal of Statistics , 8:2905–2922, 2014

    2014

  30. [38]

    Seeded graph matching via joint optimization of fidelity and commensurability

    Vince Lyzinski, Sancar Adali, Joshua T Vogelstein, Youngser Park, and Carey E Priebe. Seeded graph matching via joint optimization of fidelity and commensurability. stat, 1050:16, 2014

    2014

  31. [39]

    Random graph matching at otter’s threshold via counting chandeliers

    Cheng Mao, Yihong Wu, Jiaming Xu, and Sophie H Yu. Random graph matching at otter’s threshold via counting chandeliers. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages 1345–1356, 2023

    2023

  32. [40]

    Bilin- gual lexicon induction for low-resource languages using graph matching via optimal transport

    Kelly Marchisio, Ali Saad-Eldin, Kevin Duh, Carey Priebe, and Philipp Koehn. Bilin- gual lexicon induction for low-resource languages using graph matching via optimal transport. In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang, editors, Proceedings of the 2022 Conference on ...

    2022

  33. [41]

    Mossel and J

    E. Mossel and J. Xu. Seeded graph matching via large neighborhood statistics. Random Structures & Algorithms , 57(3):570–611, 2020

    2020

  34. [42]

    Random graph models of social networks

    Mark EJ Newman, Duncan J Watts, and Steven H Strogatz. Random graph models of social networks. Proceedings of the national academy of sciences, 99(suppl 1):2566–2572, 2002

    2002

  35. [43]

    D. M. Nguyen, Hoai A. Le T., and T. Pham Dinh. Solving the multidimensional assignment problem by a cross-entropy method.Journal of Combinatorial Optimization, 27:808–823, 2014

    2014

  36. [44]

    Sparse subspace clustering in diverse multiplex network model

    Majid Noroozi and Marianna Pensky. Sparse subspace clustering in diverse multiplex network model. Journal of Multivariate Analysis , 203:105333, 2024

    2024

  37. [45]

    Nomic embed: Training a reproducible long context text embedder

    Zach Nussbaum, John X Morris, Brandon Duderstadt, and Andriy Mulyar. Nomic embed: Training a reproducible long context text embedder. arXiv preprint arXiv:2402.01613, 2024

    2024 arXiv

  38. [46]

    S. J. Pan and Q. Yang. A survey on transfer learning. IEEE Trans. Know. and Data Eng., 22(10):1345–1359, 2010

    2010

  39. [47]

    Pantazis, A

    K. Pantazis, A. Athreya, J. Arroyo, W. N. Frost, E. S. Hill, and V. Lyzinski. The importance of being correlated: Implications of dependence in joint spectral inference across multiple networks. Journal of Machine Learning Research , 23(141):1–77, 2022

    2022

  40. [48]

    Spectral clustering in the dynamic stochastic block model

    Marianna Pensky and Teng Zhang. Spectral clustering in the dynamic stochastic block model. Electron. J. Statist. , 13(1):678–709, 2019

    2019

  41. [49]

    C. E. Priebe, Y. Park, J. T. Vogelstein, J. M. Conroy, V. Lyzinski, M. Tang, A. Athreya, J. Cape, and E. Bridgeford. On a two-truths phenomenon in spectral graph clustering. Proceedings of the National Academy of Sciences , 116(13):5995–6000, 2019

    2019

  42. [50]

    Racz and A

    M. Racz and A. Sridhar. Correlated stochastic block models: Exact graph matching with applications to recovering communities. Adv. in Neural Infor. Proc. Sys., 34, 2021

    2021

  43. [51]

    Matching correlated inhomogeneous random graphs using the k-core estimator

    Mikl´ os Z R´ acz and Anirudh Sridhar. Matching correlated inhomogeneous random graphs using the k-core estimator. In 2023 IEEE International Symposium on Informa- tion Theory (ISIT) , pages 2499–2504. IEEE, 2023

    2023

  44. [52]

    Network classification with applications to brain connectomics

    Jes´ us D Arroyo Reli´ on, Daniel Kessler, Elizaveta Levina, and Stephan F Taylor. Network classification with applications to brain connectomics. The annals of applied statistics , 13(3):1648, 2019

    2019

  45. [53]

    K. Rohe, S. Chatterjee, and B. Yu. Spectral clustering and the high-dimensional stochas- tic blockmodel. Annals of Statistics , 39:1878–1915, 2011

    1915

  46. [54]

    W. G. Roncal, Z. H. Koterba, D. Mhembere, D. M. Kleissas, J. T. Vogelstein, R. Burns, A. R. Bowles, D. K. Donavos, S. Ryman, R. E. Jung, et al. Migraine: Mri graph reliability analysis and inference for connectomics. In 2013 IEEE global conference on signal and information pro...

    2013

  47. [55]

    Rubin-Delanchy, J

    P. Rubin-Delanchy, J. Cape, M. Tang, and C. E. Priebe. A statistical interpretation of spectral embedding: the generalised random dot product graph. Journal of the Royal Statistical Society Series B: Statistical Methodology , 84(4):1446–1473, 2022

    2022

  48. [56]

    Saxena and V

    A. Saxena and V. Lyzinski. Lost in the shuffle: Testing power in the presence of errorful network vertex labels. Computational Statistics & Data Analysis , 204:108091, 2025

    2025

  49. [57]

    D. L. Sussman, M. Tang, D. E. Fishkind, and C. E. Priebe. A consistent adjacency spectral embedding for stochastic blockmodel graphs. Journ. of the American Statistical Association, 107(499):1119–1128, 2012

    2012

  50. [58]

    M. Tang, A. Athreya, D. L. Sussman, V. Lyzinski, Y. Park, and C. E. Priebe. A semiparametric two-sample hypothesis testing problem for random dot product graphs. Journal of Computational and Graphical Statistics , 26:344–354, 2017

    2017

  51. [59]

    M. Tang, A. Athreya, D. L. Sussman, V. Lyzinski, and C. E. Priebe. A nonparamet- ric two-sample hypothesis testing problem for random dot product graphs. Bernoulli, 23:1599–1630, 2017

    2017

  52. [60]

    M. Tang, D. L. Sussman, and C. E. Priebe. Universally consistent vertex classification for latent position graphs. Annals of Statistics , 41:1406 – 1430, 2013

    2013

  53. [61]

    A nonparametric two-sample hypothesis testing problem for random graphs

    Minh Tang, Avanti Athreya, Daniel L Sussman, Vince Lyzinski, and Carey E Priebe. A nonparametric two-sample hypothesis testing problem for random graphs. Bernoulli 23(3): 1599-1630 , 2017

    2017

  54. [62]

    OPUS – parallel corpora for everyone

    J¨ org Tiedemann. OPUS – parallel corpora for everyone. In Proceedings of the 19th Annual Conference of the European Association for Machine Translation: Projects/Products, Riga, Latvia, May 30–June 1 2016. Baltic Journal of Modern Com- puting

    2016

  55. [63]

    J. T. Vogelstein, J. M. Conroy, V. Lyzinski, L. J. Podrazik, S. G. Kratzer, E. T. Harley, D. E. Fishkind, R. J. Vogelstein, and C. E. Priebe. Fast approximate quadratic pro- gramming for large (brain) graph matching. PLoS One, 2015

    2015

  56. [64]

    J. T. Vogelstein and C. E. Priebe. Shuffled graph classification: Theory and connectome applications. Journ. of Classification , 32(1):3–20, 2015

    2015

  57. [65]

    Random graph matching in geometric models: the case of complete graphs

    Haoyu Wang, Yihong Wu, Jiaming Xu, and Israel Yolou. Random graph matching in geometric models: the case of complete graphs. In Conference on Learning Theory , pages 3441–3488. PMLR, 2022

    2022

  58. [66]

    S. Wang, J. Arroyo, J. T. Vogelstein, and C. E. Priebe. Joint embedding of graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence , 2019

    2019

  59. [67]

    Wasserman and K

    S. Wasserman and K. Faust. Social network analysis: Methods and applications . Cam- bridge university press, 1994. 26

    1994

  60. [68]

    Y. Wu, J. Xu, and S. H. Yu. Settling the sharp reconstruction thresholds of random graph matching. IEEE Trans. Info. Theory , 68(8), 2022

    2022

  61. [69]

    J. Yan, X. Yin, W. Lin, C. Deng, H. Zha, and X. Yang. A short survey of recent advances in graph matching. In Proc. of the 2016 ACM on Int. Conf. on Multimedia Retrieval, pages 167–174. ACM, 2016

    2016

  62. [70]

    Young and E

    S. Young and E. Scheinerman. Random dot product graph models for social networks. In Proceedings of the 5th international conference on algorithms and models for the web-graph, pages 138–149, 2007

    2007

  63. [71]

    A practical two-sample test for weighted random graphs

    Mingao Yuan and Qian Wen. A practical two-sample test for weighted random graphs. Journal of Applied Statistics , 50(3):495–511, 2023

    2023

  64. [72]

    Zhang and D

    A. Zhang and D. Xia. Tensor svd: Statistical and computational limits. IEEE Trans- actions on Information Theory , 64(11):7311–7338, 2018

    2018

  65. [73]

    Cross: Efficient low-rank tensor completion

    Anru Zhang. Cross: Efficient low-rank tensor completion. The Annals of Statistics , 47(2):936–964, 2019

    2019

  66. [74]

    Y. Zhang. Consistent polynomial-time unseeded graph matching for lipschitz graphons. arXiv preprint arXiv:1807.11027 , 2018

    2018 arXiv

  67. [75]

    Y. Zhang. Unseeded low-rank graph matching by transform-based unsupervised point registration. arXiv preprint arXiv:1807.04680 , 2018

    2018 arXiv

  68. [76]

    Zheng and M

    R. Zheng and M. Tang. Limit results for distributed estimation of invariant subspaces in multiple networks inference and pca. arXiv preprint arXiv:2206.04306 , 2022

    2022

  69. [77]

    Zhu and A

    M. Zhu and A. Ghodsi. Automatic dimensionality selection from the scree plot via the use of profile likelihood. Computational Statistics & Data Analysis , 51(2):918–930, 2006

    2006

  70. [78]

    A survey on application of knowledge graph

    Xiaohan Zou. A survey on application of knowledge graph. In Journal of Physics: Conference Series, volume 1487, page 012016. IOP Publishing, 2020. 27 A Proofs of main results Herein we collect the proofs of the main results in this work. Below, we shall use the following notat...

    2020

Pith tools

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