Sample Complexity of Correlation Detection in the Gaussian Wigner Model
Authors: Dong Huang
Pengkun Yang
Venue: ICML 2025 poster (2025)
Keywords: Correlation detection
Gaussian Wigner model
graph sampling
sample complexity
induced subgraphs
efficient algorithm
Primary area: general_machine_learning->sequential_network_and_time_series_modeling
TL;DR: We present the optimal sample complexity for correlation detection in the Gaussian Wigner model.

Abstract: Correlation analysis is a fundamental step in uncovering meaningful insights from complex datasets. In this paper, we study the problem of detecting correlations between two random graphs following the Gaussian Wigner model with unlabeled vertices. Specifically, the task is formulated as a hypothesis testing problem: under the null hypothesis, the two graphs are independent, while under the alternative hypothesis, they are edge-correlated through a latent vertex permutation, yet maintain the same marginal distributions as under the null. We focus on the scenario where two induced subgraphs, each with a fixed number of vertices, are sampled. We determine the optimal rate for the sample size required for correlation detection, derived through an analysis of the conditional second moment. Additionally, we propose an efficient approximate algorithm that significantly reduces running time.

Sample Complexity of Correlation Detection in the Gaussian Wigner Model
Dong Huang' Pengkun Yang'
Abstract
two graphs represent the same object under different rotations (Berg et al., 2005; Mateus et al., 2008).
Correlation analysis is a fundamental step in uncovering meaningful insights from complex datasets. In this paper, we study the problem of de- tecting correlations between two random graphs following the Gaussian Wigner model with unla- beled vertices. Specifically, the task is formulated as hypothesis testing problem: under the null hypothesis, the two graphs are independent, while under the alternative hypothesis, they are edge- correlated through latent vertex permutation, yet maintain the same marginal distributions as under the null. We focus the scenario where two induced subgraphs, each with a fixed num- ber of vertices, are sampled. We determine the optimal rate for the sample size required for cor- relation detection, derived through an analysis of the conditional second moment. Additionally, we propose polynomial-time algorithm that signifi- cantly reduces running time.
natural language processing, each sentence can be represented as graph, where nodes correspond words phrases, and the weighted edges represent syntactic and semantic relationships (Hughes & Ram- age, 2007). The ontology alignment problem refers to uncovering the correlation between knowledge graphs that are in different languages (Haghighi et al., 2005).
In computational biology, protein- protein interactions (PPI) and their networks are crucial for all biological processes. Proteins can be regarded as vertices, and the interactions between them can formulated as weighted edges (Singh al., 2008; Vogelstein et al., 2015).
Following the hypothesis testing framework proposed in Barak et al. (2019), we formulate the graph correlation detection problem in Problem 1.1. For weighted graph G with vertex set V(G) and edge set E(G), the weight associated with each edge we is typically denoted as (G) for any u, v E (G).
1. Introduction
Problem 1.1. Let G₁ and G2 be weighted random graphs with vertex sets V(Gi), (G2) and edge sets E(G,), E(G2). Under the null hypothesis Ho. G₁ and G2 are independent; under the alternative hypothesis H1. there exists a correlation between E(G,) ) and E( (.)) Given G1 and G2, the goal to test Hg against Hi.
Understanding the correlation between datasets one of the most significant tasks in statistics. In many applications, the observations may not be the familiar vectors but rather graphs. Recently, there have been many studies on the problem of detecting graph correlation and recovering the alignments of two correlated graphs. This problem arises across various domains:
A variety of studies have extensively investigated detection problems. However, the previous studies typically required full observation of all edges in G2 and G2 for detection, which is impractical when the entire graph is unknown in certain scenarios. In such cases, graph sampling- -h pro- of sampling a subset of vertices and edges from the Sraph-becomes powerful approach for exploring graph structure. This technique has been widely used in various settings, as it allows for inference about the graph without needing full observation (Leskovec & Faloutsos, 2006; Hu & Lau, 2013). In fact, there are several motivations leading us to consider the graph sampling method:
In computer vision, 3-D shapes can be represented graphs, where nodes subregions and weighted edges represent adjacency relationships between dif- ferent regions. A fundamental task for pattern recog- nition and image processing is determining whether
'Department of Statistics and Data Science, Tsinghua University, Beijing, China. Correspondence to: Dong Huang <hd23 @ mails. tdinghua.cdu..mm, Pengkun Yang <yang- pengkun wwwt@@tttinnnnuuuuuuu edu.en>>.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Lack of data. In social network analysis. the entire network is often unavailable due API limitations.

---

Correlation Detection
As result, researchers typically select a subset of users from the network, which essentially constitutes sampling of vertices (Papagelis et al., 2011).
converges to 0 as n - 00:
2 r) ( n-
lim
0;
Testing costs. The Protein Interaction Network is common focus in biochemical research. However, ac- curately testing these interactions can be prohibitively expensive, As result, testing methods based on sam- pled graphs are often employed (Stumpf et al., 2005).
weak detection, if the sum of Type I and Type II errors is bounded away from as n - oc:
lim (P < + ( 7-000
<1.
Visualization. The original graph is sometimes too large to be displayed on a screen, and sampling a sub- graph provides a digestible representation, making it casier for visualization (Wu et al., 2016).
It is well-known that the minimal value of the sum of Type I and Type II emrrrs between P and Q is 1 - TV(P, 2) (see, e.g. Polyanskiy & Wu (2025, Theo- rem 7.7)). achieved by the likelihood ratio test, where TV @) = f ||Pd dQ] the total variation dis- tance between P and Q. Thus strong and weak de- tection equivalent to lim, (V Q) = and 20 (V,P, Q) > 0, respectively. We then establish the main results of correlation detection in the Gaussian Wigner model.
In this paper, we consider sampling induced subgraphs for testing Ho against Hi when given two random graphs G1 and G2 with [V( [V(2)] = n. We randomly sam- ple two induced subgraphs G1, G2 with vertices from G1 and 22, respectively. An induced subgraph of a graph is formed from a subset of the vertices of the graph, along with all the edges between them from the original graph. Specifi- cally, the sampling process for G1 and G2 is as follows: we first independently select vertex sets ((1 S V(G,) and V(G2) S (G2) with |V(G,)) = [V(G2)
Theorem 1.4. There exist universal constants C, such v log
that, for any < p < 1, if 2 T
[og(1/(1 (3 V VT..
8, and then retain the weighted edge between (G11) and V(G2) from
TV(P, Q) 2 0.9.
Moreover, if w((), TV TV 2) = - o(1)
the original graphs. We assume 8 S n throughout the paper.
Conversely, if <
n lo log(1/(1-p)) V Vn)
1.1. Main Results
In this subsection, we present the main results of the pa- per. Numerous graph models exist, with the Gaussian Wigner model being a prominent example (Ding et al., 2021; Fan et al., 2023), under which the weighted edges Bu (G) follow independent standard normals for any ver- tices u, v E (G). This paper focuses on the Gaussian Wigner model with vertex set size n. Under the null hypoth- esis Ho, G and G2 follow independent Gaussian Wigner model with vertices. Under the alternative hypothesis H1, G1 and G. follow the following correlated Gaussian Wigner model.
TV(P, Q) 0.1.
Moreover, 8f < o(1).
Cn log log(1/(1- or or o(n). TV (V, =
The proof of Theorem 1.4 is deferred to Appendix A. Theo- rem 1.4 implies that, for the hypothesis testing problem between Ho and Hi when sampling two induced sub- graphs, the optimal rate for the sample size is of the order
1/2 .bove this order, detection is pos-
n logn sible, while below it, detection is impossible. Specifically, p1]1 > n², the possibility condition requires >> in the above Theorem. However, we assume that the sample size S n. which indicates that there is no the- oretical guarantee on detection, even when we sample the entire graph. Indeed, it is shown in Wu et al. (2023) that the detection threshold on p in the fully correlation Gaussian Wigner model is p² x log Our results match the thresh- n
(lo((1(11p²)) V
Definition 1.2 (Correlated Gaussian Wigner model). Let denote a latent bijective mapping from (G1)) to ((22). We say that a pair of graphs (G,, G2) are correlated Gaus- sian Wigner graphs if each pair of weighted edges Bue (G₁)
when On log
1og(1/(1-p))
and Ba- (w))r(() (e)(( (G2) for any u, u E V(Gi) are correlated standard normals with correlation coefficient p E (0, 1).
Let Q and P denote the probability measures for the sam- pled subgraphs (G1, G2) under Ho and Hi, respectively. We then focus on the following two detection criteria.
olds established in the previous work up constant for the special case n.
Definition 1.3 (Strong and weak detection). We say a test- ing statistic T = (G1,, G2) with threshold achieves
The possibility results can serve as a criterion for successful correlation detection in practice. For example, in computa- tional biology, one may sample subgraphs to reduce testing costs, and the possibility results indicate when accurate
strong detection, if the sum of Type and Type II errors
2

---

Correlation Detection
detection remains feasible. Conversely, the impossibility results offer theoretical tool for privacy protection. For in- stance, in social network de-anonymization, they imply that no test can succeed under certain conditions, thus providing a theoretical guarantee of privacy for anonymized networks.
recovery and detection problems.
1.3. Contributions and Outlines
In this paper, we derive the optimal rate on sample size for correlation detection in the Gaussian Wigner model. Specifi- cally, we prove that the optimal sample complexity is of rate
1.2. Related Work
1/2
x Yo Io n
log(1/(1 p-1) Vn
We also propose a polynomial
Graph matching The problem of graph matching refers to finding a correspondence between the nodes of differ- ent graphs (Cactano et al., 2007; Livi & Rizzi, 2013). Re- cently, there have been many studies on the analysis of matching two correlated random graphs. In addition to the Gaussian Wigner model, another important model is the Erdös-Rényi model (Erdōs & Rényi, 1959), where the edge follows Bernoulli distribution instead of normal dis- tributioo. As shown in Cullina & Kiyavash (2016; 2017); Hall& & Massoulié (2023), some sufficient and necessary conditions for the matching problem in the Erdös-Rényi model were provided. The optimal rate for graph match- ing in the Erdös-Rény' model has been established in Wu et al. (2022), and the constant was sharpened by analyzing the densest subgraph in Ding & Du (2023). There are also many extensions on Gaussian Wigner model and correlated Erdós-Rényi graph model, including the inhomogeneous Erdös-Rényi model (Rácz& & Sridhar, 2023; Ding et al., 2023b), the partially correlated graphs model (Huang et al., 2024), the correlated stochastic block model (Chen al., 2024; 2025), the multiple correlated graphs model (Ameen & Hajek, 2024; 2025), and the correlated random geometric graphs model (Wang et al., 2022).
algorithm that significantly reduces computational cost.
In Sections 2 and 3, we prove the possibility results and impossibility results on sample size, respectively. Section 4 introduces our polynomial algorithm for correlation detec- tion. Then, we run some numerical experiments in Section 5 to verify the effectiveness for our algorithm proposed in Sec- tion 4. Finally, Section 6 offers further discussion and future research directions, and the appendices contain detailed proofs and additional experimental results.
2. Possibility Results
In this section, we prove the possibility results in Theo- rem 1.4 by analyzing the error probability P (T < <) + Q (T 2 r) under different regimes of p. which provides an upper bound for the optimal sample complexity. Given do- main subset S C V(G)) and an injective mapping S + V (G2). along with bivariate function f R x R + R, we define the f-siiilarity graph Hi as follows. The vertex set of Hi is V(H)) = V(Gi), and for each edge e, the weighted edge is defined as
(c = { (B(())) if E (2) otherwise
(I)
Efficient algorithms and computational hardness There are many algorithms on the correlation detection and graph matching problem, including percolation graph matching algorithm (Yartseva& & Grossglauser, 2013), subgraph match- ing algorithm (Barak et al., 2019), message- message-passing algo- rithm (Piccioli et al., 2022), and spectral algorithm (Fan et al., 2023), while some algorithms may be computationally inefficient. There are also many efficient algorithms, based on the different correlation coefficient, including Babai et al. (1980); Bollobás (1982); Dai et al. (2019); Ganassali & Massoulié (2020); Ding et al. (2021); Mao et al. (2023a); Ding & Li (2023); Mao et al. (2023b); Araya et al. (2024); Ding & Li (2024); Mao et al. (2024); Ganassali et al. (2024);
where T(e) denotes the edge T (u) for any edge = uv.
Let m A (1-r)s² for some constant e < 1, and denote n
Samm the set of injective mappings π S C ((2)) +
V (G2) with |S| = m. Let (H4) & LeEr(G,) Be (HL) define the sum of weighted edges in Hy. In fact, the quantity e (HL)) can be regarded as a similarity score between two graphs. Our test statistic takes the form
T(f) max e e7HL) max TES..m
Be (HH) (2) FES.,m CEB(G.)
Σ
Muratori & Semerjian (2024).
For simplicity, we write TT for T(f) when the choice of f is clear from the context. By the detection criteria in Defini- tion 1.3, it suffices to bound the Type I error (TT()) 2 r) and the Type II error P (T()) < <)) for some appropriate threshold r. In the following, we outline a general recipe to derive an upper bound for error probahilities.
The low-degree likelihood ratio (Hopkins & Steurer, 2017: Hopkins, 2018) has emerged as framework for studying computational hardness in nigh-dimensional statistical in- ference. It conjectures that polynomial-time algorithms succeed only in regimes where low-degree statistics suc- ceed. Based on the lew-degree conjecture, the recent work by Ding et al. (2023a); Mao et al. (2024) established suffi- cient conditions for computational hardness results on the
Type I error. Under the null hypothesis Ho. the sampled subgraphs G1 and G2 are independent. Given bivariate
3

---

Correlation Detection
function and a threshold 7, it should be noted that the distribution of the f f-similarity graph Hif follows the same distribution for any E Ss,m- Consequently, applying the union bound yields that
correlation. We derive concentration inequalities to ensure that (H exceeds the maximum spurious score aris- ing from stochastic fluctuations under the null, as shown in Propositions 2.2 and 2.3.
(T 2 r) S 1ssmll 10 (e (H4)= 2 27)
2.1. Detection by Maximal Overlap Estimator
We then bound the tail probability by a standard Chernoff bound Q (e (HZ) 2 7) I exp (-År) E [exp (^e (+
In this subsection, we use the test statistic (2) with f(x;, y) = ry for possibility results. Indeed, this estimator is equivalent to maximizing the overlap on induced subgraphs between G1 and G2. Specifically, we have the following Proposition.
See (14) in Appendix B. for more details.
Type II error: Under the alternative hypothesis Hi, recall that π denotes the latent bijective mapping from V(G,) to (G2)). For the induced subgraphs G1, G2 sampled from
Proposition 2.2. There exists a universal constant C1 > 0 such that, for any 0 p < and Cyn log
-(2) P.
s² 2
G1, Gg, we denote the set of common vertices as
S.- A (+G))(++) Tx- A (((())))VV))))
(3)
P(T (T
(4)
Proposition 2.2 provides a sufficient condition on strong detection for any 0 < p < 1. We refer readers to Ap- pendix B.I for the detailed proof. Since 1 TV(PP 2) S P < + QT 2 7). it achieves the optimal rate in Theorem 1.4 when p 1 2((1.. However, the rate is sub-optimal when p 1 o(1). In fact, 2 succeeds for detection when p 1 by comparing the difference between all edges. We will use new estimator in Subsection 2.2 to derive the optimal rate.
We note that the restriction of x² to S,- is bijective map- ping between S,- and T--,aa and thus SS..1 |. In our random sampling models, the vertices of G, and G2 are independent and identically sampled without replacement from the two graphs 1 and G2, which yields the following Lemma regarding the sizes of S.x- and T
Lemma 2.1. When randomly sampling vertex sets ((G)), (G2) from v(G1), (G2) with [V(G)) [V(G2)l the size of common vertex set in (3) follows Hypergeomelric distribution HG(n,,, 8)s. Specifically,
2.2. Detection by Minimal Mean-Squared Error Estimator
P PIS.. = t] ( (5=;)
(() n
for any t [s].
In this subsection, we use the test statistic (2) with f(x,)) y) = - -x) and focus on the scenario where p >>> e Indeed, this estimator is equivalent to minimizing the mean squared error between the induced subgraphs of size m in G1 and G2, respectively. Indeed, the expected mean-square 2)
We then establish the main ingredients for controlling the Type II error. Under the distribution P. given f and т,
error for correlated pair E (B.(G,) Bar (G2)) is
IT <T< [T <T, S. < m) (T < <T,1S,-12 2 m} -| < m] (T < t, S 2 m).
2(1 - p). while it stays bounded away from for an uncor- related pair. As a result, the choice of f effectively distin- guishes between Hy and H₂ under strong signal condition. We now state the following Proposition.
(5)
Since [] = Σ > m, the first event {|S,. < m} can be bounded by the concentration inequality for Hy- pergeometric distribution in Lemma D.3. For the second event, it can be bounded by P (T T||S | 22mmmm))) m). Under the event [|5x=1 Z m). there exists T. E Sa.m such that oh = nT" on its domain set dom ). The error proba- bility of the event (T < T, SS 2 m) can be bounded by P (( (nL- < IS. 2 m) We then use the concen-
Proposition 2.3. There exists a universal constant C2 > 0 such that, for any
6 -6
p 1 and = =2( 1),
if s2 2 C2 Tog (/(1111000 03) Vn).
log
< P(T<T)+ ( 5.1.
tration inequality bound the tail probability. See (17) for more details.
Moreover & = P (T <T) 2T =
2
We refer readers to Appendix B.2 for the detailed proof. Proposition 2.3 provides sufficient conditions on strong and weak detection when is close to 1. This result fills the gap for the optimal rate of s in Proposition 2.2 when p = -((). In view of Propositions 2.2 and 2.3, we note
The quamtity e(H.)) measures the similarity score of map- ping æ. Under the null hypothesis, e(?()) has a zero mean for all n, whereas under the alternative hypothesis, its mean with π o is strictly positive owing to the underlying
4

---

Correlation Detection
that p² = log (1/(1 - -) when 0 < p S 1 e- and log (1/(1- - p)) = log -2) when 6- < <
TV(P(G,, Gy), Q G2)) in this paper. By Tsybakov (2009, Equation 2.27), the total variation distance between P and Q can be upper bounded by the second moment:
1. Then, there exists a universal constant C 2 C1 VC2 such that
P TV () S Be
(e)-1
C 2 log 1/(1-p2)
if0 p 1 - if - <
-1.
(6)
log(1/(11 p)}
The likelihood ratio is defined as
We note that
C'n log 12
C "log V ni
in Proposition 2.2,
P(G1, G2) = G2) nd!
1 E
P(G,, G2/m) TES. Q(GI, G2)
and thus proving the possibility results in Theorem 1.4.
(7)
Remark 2.4. The possibility results can be extended to sub- Gaussian assumption on the weighted edges. The bound for the moment generating function holds under the sub- Gaussian assumption, and consequently, the Chernoff bound remains valid. See Remark B.1 for more details.
where S, denotes the set of mappings क V(G)) V ((2)) between two original graphs. Note that sometimes certain rare events under P can cause the unconditional sec- ond moment to explode, while TV (P, Q) remains bounded away from one. To circumvent such catastrophic events, we can compute the second moment conditional on such events.
Remark 2.5. In the previous work (Wu et al., 2023) on the correlated Gaussian Wigner model, the correlation exists over the entire graph. The maximal overlap estimator and the minimal mean-square error estimator over two graphs are equivalent since the sum of squares of the weighted edges is fixed. However, in our sampling model, the sum of squares of the weighted edges in the two subgraphs are random variables, and thus the two estimators dif- fer. Indeed, the Maximum Likelihood Estimator (MLE) is maxres..s...1 e (H4) with f(z, y) = =x²(<x² + + + 2pzy, where (x X pzy when p (2r x -(x y)² when p = 1 o(1). The choice of different estimators reflects the use of MLE under differ- ent regimes. See (31) in Appendix C.2 for details.
We consider the following event:
& E (GI ( (1 (1+
n
By Lemma 2.1, the size of common vertex set (z(V)G (G2)) follows hypergeometrii distribution HG(n, s, s) un- der P. In this paper, we define the conditional distribu- tion as P', G2, TT = P (G1, G2, =|E). By Lemma D.3, we have ( = o(1) when 8 = w (12/²)). Using TV(P, 2) S TV(P', @) o(11 and applying (6) on P' and Q yields that a sufficient condition for TV(P, Q) o(1) is
((1) and
3. Impossibility Results
2 E² = =1+ o(1). See (25) for more details.
In this section, we establish the impossibility results for the detection problem, which provides lower bound the optimal sample complexity. We first present an overview of the proof. Recall that S,-' and TT- are the sets of com- mon vertices defined in (3) and (4), respectively. Under our sampling model, there exists a latent mapping between Sy, and T,- under the hypothesis H1. When equipped with the additional knowledge of the common vertex sets, our problem can be reduced detection with full observations on smaller correlated Gaussian Wigner model, the detection threshold for which is established in Wu et al. (2023). As shown in Lemma 2.1, the size of S.- and Tx- follows a hy- pergeometric distribution. Using the concentration inequal- ity (36), the size of S,- satisfies | < (1 + +)E [|S with high probability. Therefore, the impossibility results from the previous work on full observations remain valid when the number of correlated nodes is substituted with (1 + E [|S=-I]- |]. However, such reduction only proves tight when the correlation is weak. We will establish the re- maining regimes by the conditional second moment method.
3.1. Weak correlation
In this subsection, we present the impossibility results for weak correlation regime where 0 < p² < -1/2.
Proposition 3.1. For any 0 < p² < n 1/2, /2,
if x2 S
n log n then TV(P, 2) = o(1). 2 2log(1/(1-pT))
We note that the total variation distance monotonically in- creases by the sample size s. In view of Proposition 3.1, we n logn
only need to tackle with the situation s2 2 3log(1(0177))
where = w (2) since p² < n 1/2 - Therefore, a suffi- cient condition for TV(P, Q) = o(1) is TV (P', Q) = o(1) by the triangle inequality. The proof of TV((', Q) = o(1) can be reduced to the lower bound in Wu et al. (2023) using data processing inequality when given the common vertex sets S,, and T... Under weak correlation, the bottleneck is detecting the existence of latent mapping ".. The de- tection is impossible even with the additional knowledge on the location of common vertices. The detailed proof of Proposition 3.1 deferred to Appendix B.3.
For notational simplicity, we use TV(P, Q) to denote
5

---

Correlation Detection
3.2. Strong correlation
Note that the sets from P and C are disjoint. Consequendl, for any P, P' E P and C, C' C. Lp, Ly L and Le are mutually independent. Furthermore, the expectations of Lp and Le can be derived from the following Lemma.
In this subsection, we present the impossibility results for strong correlation graphs where n 1/122 S p² < 1. Let ã be an independent copy of π. A key ingredient in the analysis of conditional second moment is the analysis of P.G, (alr) PPG,,
Lemma 3.3. For any PE P, C C, we have Eg (Lp) = 1 and Eg (Tc) 1-
(a) (2) We refer readers Appendix B.4 for the details.
By Lemma 3.3 and the joint independence between different paths and cycles, have
We then analyze the terms Gglx) and G.G.. Re-
G2)
G2)
call the common vertex sets S and T defined in (3) and (4), respectively. For any e & (5)) and e' & (5)), (e() and (G2) are independent under P. while under the null hypothesis distribution Q they are also independent. Therefore, the term G2) can be decomposed into II BE (8) ((Bc(G)), Br()) (G2)), where
P(G,, G2 P(G1, G2] Q G2)
Pali)
II Lp II Lo LPEP
II CEC
(
1
p2|c|
CEC
b) - P(S.(G))==B/())))G))))) for any a, R is the ratio of density functions. We note that there are comr- lations between (o² (S))
The cycles set C plays a key role in the analysis of condi- tional second moment. In order to analyze the properties of C in depth, for any π and म, we define the core set
(()
2 (Trr) and ("2), yielding that (2) are correlated. To deal with the correlation, our main idea is to decompose the edge sets into independent parts. To formally describe all correlation relationships, we use the correlated srrrelattd.fnntiooon functional digraph of two mappings π and मे between a pair of graphs introduced in Huang et al. (2024).
P(Gr.Ggla) and Pili.Cal
I A (x, #) ف Ucec UeEd U (10)
@GG..Ga)
where Vee) denotes the two vertices of edge e. Indeed, I' is the intersection set between V(G1) and all the vertices of edges in cycle set C. In fact, the quantity IIee (i-P relies significantly on I" We then show the following lemma on the properties of I".
Definition 3.2 (Correlated functional digraph). Let π and मे be two bijective mappings between V(G,) and ((22) and Sr. Tx, S4, be the sets of common vertex defined in (3) and (4). The correlated functional digraph of the functions t and क is constructed as follows. Let the vertex sets be (%) U (8x) ( We first add every edge e -> (e)
Lemma 3.4 (Properties of the core set). For I in (10) and any t S 8, we have
14, P = 1] S ( 2
1" = argmax
ICV(G))=(T)=(()
for e E (2)). and then merge each pair of nodes (e, F())
for e ($x) into one node.
We then propose the following Proposition. Proposition 3.5. For any n 1/2 -122 < p² 1, if 52 <
After merging all pairs of nodes, the degree of each vertex in the correlated functional digraph is at most two. There- fore, the connected components of the correlated functional digraph consist of paths and cycles. For example, for a path (e1, T(e)), .... ,e,, ((;)), where e1,-.. ,ey are edges in G1, have a(e2) (ee)), ... (ee)) = <(e--)); for cycle (eI, (e..),))....... ,6,, ((e)), we have a(e2)= = (e)),.... - (ej-1), = T(e)). By decom- posing the connected components, the analysis of edge sets is separated into independent parts. Let P and C denote the collections of vertex sets belonging to different connected paths and eycles, respectively. For any P and C' C, define e (G1, G2) (G.(),), (ate) (G2)) and
n log 8 (og(11111-p))) pay then TV (P, Q) o11)
The detailed proof of Proposition 3.5 is deferred to Ap- pendix B.4. In the proof, we apply the conditional second moment method with the conditional distribution P' P(-LE), where & is defined in (8). The analysis of the condi- tional second moment relies significantly on the decomposi- tion of cycles and paths of a correlated functional digraph. By Lemma 3.3, the conditional second moment can be re- duced to the calculation on cycles, while the vertex set induced by all cycles is exactly I Combining this with the properties of I" in Lemma 3.4, we finish the proof of Propo- sition 3.5. In fact, under the strong correlation condition, detecting n² is no longer the bottleneck. We instead use more delicate analysis based on the conditional second moment method.
Lp
II
(, G2)
II (GI, G2),
RE )PP
<E (E()))P
Le A
II
( G2)
II
(G,
By (36) in Lemma D.3, there exists C < _/4 such that, when s2 S CCn, we have TP [[SS.. = 0] 2 0.9, which implies
(e(Sr)nc
<E nC
6

---

Correlation Detection
that TV(P, 2 0.1. Specifically, when 8² =(n),
injection ny V3 + V(G2) as
P P[|S==1=0] 1 o(1), and thus TV (P; Q) = o(1)
Combining this with Propositions 3.1 and 3.5, we prove the impossibility results in Theorem 1.4.
arginax (VV.-V(Ga)) x iinjection
Σ cE(')
Be (H4))
(II)
Remark 3.6. The second moment under our induced sub- graph sampling model is equivalent to that on the vertex set induced by 1". When fixing 1", it is equal to the sec- ond moment of correlated Gaussian Wigner model with π : I' + (("). However, I' = I* (T, f) is a random variable of π π., and hence a more thorough analysis on I* needed, as shown in Lemma 3.4.
where H4, is the f f-smiilarity graph defined in (1). We then sort the values Ece(") 3e (H!,) in decreas- ing order and select the top N2 corresponding pairs
of (V,, m.). Without loss of generality, we assume that (V1, T1). ... (VN,, nN,) are the top N₂ pairs.
Find seeds. Given an integer K2, for any U S [N2] with |0| K2, let Vo - UjeuVV. We say U is compatible if for any u E Vv, Ty(D)'s are identical for all j E U such that v E Vi,. Let I(U) denote the indicator function of compatible set U. If = 1, we define ay as the union of Ty for any j E U. Specifically,
4. Algorithm
In this section, we present an efficient algorithm for de- tection. In Theorem 1.4, we show that the estimator (2) achieves the optimal sample complexity for correlation de- tection. However, the estimator requires searching over S.m. with time complexity (=)² m!, resulting in poor performance for large graphs. Next, we propose an efficient algorithm to approximate the estimator in (2).
To (v) (T( such that v E V,y. for any v E Vv.
The seed is then defined as
When the full observations of the graphs are given, there are many different efficient algorithms for detecting cor- relation and recovering graph matching. For instance, it is shown in Mao et al. (2023b; 2024) that counting trees is an efficient way to detect correlation and recover graph matching when the correlation coefficient/ >> va, where a x 0.338 is Otter's constant introduced in Otter (1948). The message-passeeeee paaagge-assinggggee algorithm (Piccioli et al., 2022; Ganas- sali et al., 2024) is also an efficient algorithm in the Erdös- Rényi model, which makes substantial use of the local tree structure. Another approach for graph matching is relaxing the original problem to a convex optimization problem (Fan et al., 2023). Additionally, there are approaches based on initial seeds (Mossel & Xu, 2020) and iterative methods (Ding& & Li, 2024) addressing this problem.
Be (H Te
Σ
To
argmax
(Wool)
No UU
(E("))
(12)
which maximize the average similarity score over U.
Iteratively construct mappings. Define the domain set and image set of Ty as S, and To, respectively, To C. V(G2).
Then, we have To : So C ((G)) Next, we iteratively extend the seed mapping by finding one vertex each from V(11) and ((G2) until |Sol = (Tul = m. Specifically, given To So + To. let
(Be
U1, U2 = argmax on evEV vES, (GaVTT
However, for the partial alignment problem and partial cor- relation detection problem, where only part of the original graphs are given, it becomes more challenging to find efficient algorithm. One approach is to use deep learning techniques (Jiang et al., 2022; Wang et al., 2023; Ratnayaka et al., 2024), while another way is to use low-degrea struc- tures, such as cliques or trees (Sharma et al., 2018). In this paper, we propose an algorithm that finds the initial seeds by matching the cliques, and then iteratively constructs the re- maining mapping. Three main components of our algorithm are outlined as follows.
Then, we add the new mapping 01 + U22 to To- This process is repeated iteratively, updating up un- til |Sol = m. Finally, we compute the test statistic Eee(") 3. (H4.)- )- Ho is rejected if the test statistic exceeds the given threshold т, otherwise Ho is ac- cepted.
The detailed algorithm is shown in Algorithm 1. Our algo- rithm comprises three main steps. In the first step, we select Nj vertex sets V1. VN, of size K₁ and search for injec- tions n; from V. to V (G2). which requires O(N In the second step, we search over all subsets U C [N2] with |0| = K2, which takes O(NK)) time. In the third step. we iteratively expand the mapping based on our seeds, which takes O(m2 8²) time. We typically choose N1 x K
Match the small cliques. Given two graphs G1, G2 and integers K1, N1, N2 and a bivariate function f. we first randomly pick N, vertex set Vi,'' VN, C ((G)) with [V = = [Vyl= = K1 and V22 * Vj, for any S i < j S N1. For any 1 S S Ni, define the
time.
7

---

Correlation Detection
and K₃ 2 3, and thus the overall time complexity of the algorithm is O(N ski + 2)
Algorithm 1 Clique-Basee -Based Detection Algorithm
1: Input:
Two graphs G1, G2 with s vertices, mapping size m, clique size K1, combining size Kg. number of cliques N1, number N2, threshold T.
Since only partial correspondence exists between the two graphs under H1, finding the true mapping is challenging. We first use small cliques of size K2 to trade accuracy for computational efficiency, although this often results in many incorrect mappings. To improve accuracy, we then test the compatibility of these small mappings and merge K2 of them to construct larger, more accurate mapping. This larger mapping is then used as a seed, and we iteratively enlarge it by adding one pair at time until the size reaches m. This approach significantly reduces the running time compared to directly matching the larger cliques.
2: Output: Detection result Ho or Hi.
3: Randomly select Ni vertices sets V; S. V(Gi) with
[V] = K1, for any i = 1.2,
4: For each V,, compute Ti according to (11). Then, sort the values Eee(") Se (H4, in descending or- der and select the top N2 corresponding pairs of (V), Without loss of generality, denote pairs as (Vi, (V,,, TNa).
5: Find the seed mapping To So S V(G1) + To S
V(G2) according to (12). while |Sol < m do for in E (G1)), and U2 E V(G2) do
As for the performance, a larger sample size leads to larger common vertex sets, and thus increases the number of correct mappings in Step 1. A larger K1 corresoonds to matching larger cliques in the first step. This increases
8: Compute Eveso I (Bmo Suzzo(o) (G2)).
9:
end for
the proportion of correct mappings within the N2 candidate pairs when K is below the size of common vertex sets. However, choosing Kj beyond this size introduces wrong mappings. Besides, in the second step, we search over all U F [N2] with |0'| K2 identify the seeds. While larger K2 imposes stricter matching criterion. choosing K2 beyond the number of available correct mappings from Step 1 will degrade performance.
10: Find the pair (2) for the maximal value of (ozno())(G))) and add Un +
Eves. f
U2 into To-
11:
end while
12: Compute Ene(") (5)0 Be (H..)) output Hi it exceeds T, otherwise output Ho.
The accuracy and rumning time depend on NN. .22, K1, and K2, and there is a trade-off between them: larger values of these parameters generally improve accuracy but increase the computational cost.
Type II error against the Type I error. We also compute the area under the curve (AUC), which can be interpreted as the probability that the test statistic is larger for a pair of correlated graphs than a pair of independent graphs
5. Numerical Experiments
In Figure 2, for each plot, fix 50, p = 0.98, K1
4, K2 3, N₁ = 10000, N₂ = 500, 6 0.01, and vary 8 E [10, 20, 30, 40, 50), with m = (1-c)a² We observe that as increases, the ROC curve is moving toward the upper left corner, and the AUC increases from 0.52 to 1, indicating improvement in the performance of our test statistic. Indeed, by Lemma 2.1, the cardinality of common set increases as increase, strengthening the signal and facilitating correlation detection.
In this section, we provide numerical results for Algorithm on synthetic data. To this end, we independently generate 100 pairs of graphs that follow the independent Gaussian Wigner model, and another 100 pairs that follow the corre- lated Gaussian Wigner model with correlation p.
Fix n 50, = 25,p p- 0.99, K1 = 4, K2 = 3, N1 = 10000, N2 = 500, and e = 0.01. Then, m = (1-6)+
n
12. In Figure 1, we plot the histogram of our approximated estimator Ee)(?)) Be (HL4)) defined in Algorithm 1. We see that the histograms under the independent model and the correlated model are well-separated. By picking an appro- priate threshold r, the proposed algorithm succeeds in cor- relation detection. We note that when Ki and K₂ = 1, Algorithm is equivalent to comparing the pairwise differ- ences of all edges, while approach with K₁ 4 and K₂ = 3 is more effective than this trivial method.
In Figure 3, for each plot, we fix n 50, s =40, K1 4, K2 3, N₁ = 10000, N₂ 500, 0.01, and vary P E (0.95, 0.96, 0.97, 0.98, 0.99), with m (1-c)s²
31. We observe that as increases, the ROC curve is moving toward the upper left corner, and the AUC increases from 0.55 to 1, indicating an improvement in the performance of our test statistic the correlation strengthens. It turns out that correlation detection improves as and p increase.
We also compare our method with the classical Graph Edit Distance (GED) (Sanfeliu & Fu, 1983), a widely used graph similarity measure. When n = 50, s = 30, and e = 0.01, the AUC values for the GED-based test at p = 0.98,
In order to compare our test statistic under different set- tings, we plot the Receiver Operating Characteristic (ROC) curves by varying the detection threshold and plotting the
8

---

Correlation Detection
Correlated dom graphs independent random graphs
Court
13
the0255 Accedd5
Test Statitic
mee03), a.C 88
mo-ase, 6.C-0.)
mc-050 ALC-0.7
mcc050 ALC-1.00
Figure 1. The histogram of the approximate Eee(")) Se (H4,) in Algorithm 1 over 100 pairs of graphs, where the blue represents the correlated Gaussian Wigner model, and the green one represents the independent graphs.
statistic
Fake Foctiue
Figure 3. Comparison for the ROC curve of approximate test
statistic for different correlation coefficients
are many problems to be further investigated:
Than Pestivve Rate
Extension Erdös-Rewt Rényi model. Most results in this paper be extended to the vrdōs-Rééní model. The key difference lies in the additional parameter control- ling the edge connection probability. For the possibility results, the estimator is similar to (2), with the bivariate function f selected via MLE under the Erdös-Rényi model. For the impossibility results, the reduction pro- cedure provides tight bounds when p -1((1) and a more delicate event is required for the conditional second moment analysis when n = which is similar to Proposition 3.5.
AUC-6.52
-0. AUC-0.12
1-30 AUC=0.92
5-40. AUC-0.97
5050. A0C-0000
Pocitive Rate
Figure 2. Comparison for the ROC curve of the approximate test statistic for different sample size s.
Theoretical analysis of the efficient algorithm. We have shown that the Algorithm performs well on syn- thetic data, while the theoretical guarantee remains an open problem. This guarantee can serve as an upper bound for the existence of a polynomial-time algorithm. Moreover, since the tree-counting- based method shows strong performance in the Erdös-Rényi model, it would be interesting to investigate whether it remains effec- tive in Gaussian networks.
10-5,1 10-7 are 0.53, 0.73, and 0.88, respectively. In contrast, our algorithm yields significantly higher AUCs of p are 0.92, 1, under the same settings. These results demonstrate the superior performance of our method in detecting correlation in the Gaussian Wigner model. We provide some additional experiments in Appendix E.
6. Future Directions and Discussions
This paper focuses detecting correlation in the Gaussian Wigner model by sampling two induced subgraphs from the original graphs. We determine the optimal rate on the sam- ple size for correlation detection. In comparison to detection problem on the fully correlated Gaussian Wigner model, the additional challenge arises from partial correlation when sampling subgraphs. We provide detailed analysis of the set when using the conditional second moment method to derive the impossibility results. We find that the condi- tional second moment can be reduced to the second moment on the core set. Additionally, we propose an efficient ap- proximate algorithm for correlation detection based on the clique mapping technique and iterative approach. There
Computational hardness. The low-degree conjec- ture has recently provided evidence of the computa- tional hardness on related problems (see, e.g., Hopkins (2018); Kunisky et al. (2019)). vestigate the computational hardness conditions with respect the sample size for the correlation detection problem using the low-degree conjecture.
of interest to in-
Other gruph models. The sample complexity for cor- relation detection remains unknown for many models (e.g., the stochastic block model, the graphon model). natural next step to explore whether our results can be extended to more general settings.

---

Correlation Detection
Acknowledgments
Chen, G., Ding, J., Gong, S., and Li, Z. A computa- tional transition for detecting correlated stochastic block models by low-degree polynomials. arXiv preprint 1xXXv:2409.00966 2024.
The authors thank all reviewers for their valuable comments and suggestions. P. Yang is supported in part by the National Key R&D Program of China 9224YF10015800
Chen, G., Ding, J., Gong, S., and Li, Z. Detecting correla- tion efficiently in stochastic block models: breaking ot- ter's threshold by counting decorated trees. arXiv preprint arXiv:2503.0644 2025.
Impact Statement
This paper addresses the sample complexity of the correla- tion detection problem in the Gaussian Wigner model, with implications for fields like social network analysis, biology, and natural language processing. By improving the ability to defect correlations in complex datasets, our work con- tributes to advancing the understanding of hidden structures in large-scale data. The proposed methods have the potential to enhance analytical capabilities across a range of appli- cations, enabling more accurate inferences in real-world contexts. To the best of our knowledge, there is no negative societal impact related this research.
Cullina, D. and Kiyavash, N. Improved achievability and converse bounds for Erdōs-Rényi graph matching. ACM SIGMETRICS performance evaluation review, 44(1):63- 72, 2016.
Cullina, D. and Kiyavash, N. Exact alignment recov- ery for correlated Erdös-Rényí graphs. arXiv preprint arXiv: 17X1v:7711.0683.. 2017.
Dai, O. E., Cullina, D., Kiyavash, N., and Grossglauser, M. Analysis of a canonical labeling algorithm for the alignment of correlated Frdōs-Rényí graphs. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3(2):122,, 2019.
References
Ameen, T. and Hajek, B. Robust graph matching when nodes corrupt. In Proceedings of the 41 Interna- fional Conference on Machine Learning, volume 235, pp- 1276-1305. PMLR, 2024.
Davis, P. Circulant Matrices. Wiley, 1979.
Ding, J. and Du, H. Matching recovery threshold for cor- related random graphs. The Annals of Statistics, 51(4): 1718-1743, 2023.
Ameen, T. and Hajek, B. Detecting correlation between multiple unlabeled gaussian networks. arXiv preprint arXiv:2504. 16279, 2025.
Ding. and Li, Z. polynomial time iterative algorithm for random graph matching with non-vanishing correlation. arXiv preprint arXiv:2306. 002666 2023.
Araya, E., Braun, G., and Tyagi, H. Seeded graph matching for the correlated gaussian wigner model via the projected power method. Journal of Machine Learning Research, 25(5):1-43, 2024.
Ding, J. and Li, Z. polynomial time iterative algorithm for matching gaussian matrices with non-vanishing corre- lation. Foundations of Computational Mathematics, pp.
Babai, L., Erdös, P., and Selkow, S. M. Random graph isomorphism. SlaM Journal computing, 9(3):628-635, 1980.
1-58, 2024.
Ding, J., Ma, Z., Wu, Y., and Xu, J. Efficient random graph matching via degree profiles. Probability Theory and Related Fields, 179:29-111 2021.
Barak, B., Chou, C.-N., Lei, 7., Schramm, T., and Sheng, Y. (Nearly) efficient algorithms for the graph matching prob- lem on correlated random graphs. Advances in Neural Information Processing Systems, 32, 2019.
Ding, J., Du, H., and Li, Z. Low-degree hardness of detec- tion for correlated Erdōs-Rény graphs. arXiv preprint arXiv: 2ll::3311.19311 2023a.
Berg, A. C., Berg, T. L., and Malik, J. Shape matching and object recognition using low distortion correspondences. In 2005 IEEE computer society conference on computer vision and pattern recognition (CVPR 005, volume 1, pp- 26-33. IEEE, 2005.
Ding, J., Fei, Y., and Wang, Y. Efficiently matching random inhomogeneous graphs via degree profiles. arXiv preprint arXiv:2310.0444 2023b.
Bollobás, B. Distinguishing vertices of random graphs. In
Erdōs, P. and Rényi, A. On random graphs I. Publicationes Mathematicae (Debrecen), 6:290-297, 1959.
Mathematics Studies, volume 62, pp. 33-49. Elsevier, 1982.
Fan, Z., Mao, C., Wu, Y., and Xu, J. Spectral graph match- ing and regularized quadratic relaxations I: The gaussian model. Foundations of Computational Mathematics, 23 (5):151115555 2023.
Caetano, S., Cheng, L., Le, Q. V., and Smola, J. Learn- ing graph matching. In 2007 IEEE 11th International Conference on Computer Vision, pp. 1-8, 2007.
10

---

Correlation Detection
Freeman, S. and Freeman, L. The Networkers Network: A Study the the Impact of a New Communications Medium Sociometric Structure. Social sciences research reports. School of Social Sciences University of California, 1979.
Jiang, Z., Rahmani, H., Angelov, P., Black, S., and Williams, B. M. Graph-context attention networks for size-varied deep graph matching. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2343-2352, 2022.
Ganassali, L. and Massoulié, L. sparse graph aligmment. Conference on Learning The- PMLR, 2020.
From tree matching to
Kunisky, D., Wein, A. S., and Bandeira, A. S. Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio. In ISAAC Congress (International Society for Analysis, its Applications and Computation), pp. 1 1-50. Springer, 2019.
ory, pp.
Ganassali, L., Massoulié, L.., and Semerjian, G. Statistical limits of correlation detection in trees. The Annals of Applied Probability, 34(4):3701-3734 2024.
Leskovec, and Faloutsos, C. Sampling from large graphs. In Proceedings of the 12th ACM SIGKDD international conference Knowledge discovery and data mining, pp. 631-636, 2006.
Ghosh, M. Exponential tail bounds for chisquared random variables. Journal of Statistical Theory and Practice, 15 (2):35, 2021.
Haghighi, A., Ng, A. Y., and Manning, C. Robust textual inference via graph matching. In Proceedings of Human Language Technology Conference and Conference Empirical Methods in Natural Language Processing, pp. 387-394, 2005.
Livi, L., and Rizzi, A. The graph matching problem. Pattern Analysis and Applications, 16:253-283, 2013.
Mao, C., Rudelson, M., and Tikhomirov, K. Exact matching of random graphs with constant correlation. Probability Theory and Related Fields, 186( (86(1-2)337-388)) 20222
2023a.
Hall, G. and Massoulié, L. Partial recovery in the graph alignment problem. Operations Research, 71(1):259-277 2023.
Mao, C., Wu, Y., Xu, J., and Yu, S. H. Random graph matching at otter's threshold via counting chandeliers. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pp. 1345-1356, 2023b.
Hanson, D. L. and Wright, F. T. A bound on tail probabili- ties for quadratic forms in independent random variables. The Annals of Mathematical Statistics, 1779 1971.
Mao, C., Wu, Y., Xu, J., and Yu, S. H. Testing network correlation efficiently via counting trees. The Annals of Statistics, 52(6):2433 2024.
Hoeffding, W. Probability inequalities for sums of bounded random variables. The collected works of Wassily Hoeffd- ing. pp. 409 426, 1994.
Mateus, D., Horaud, R., Knossow, D., Cuzzolin, F., and Boyer, E. Articulated shape matching using laplacian eigenfunctions and unsupervised point registration. In 2008 IEEE Conference on Computer Vision and Pattern Recognition, pp. 1-8. IEEE, 2008.
Hopkins, S. Statistical inference and the sum of squares method. PhD thesis, Cornell University, 2018.
Hopkins, S. B. and Steurer, D. Efficient bayesian estima- tion from few samples: community detection and related problems. In 2017 IEEE 58th Annual Symposium Foundations of Computer Science (FOCS), pp. 379-390. IEEE, 2017.
Mitzenmacher, M. and Upfal, E. Probability and computing: an introduction randomized algorithms and probabilis- tic analysis. Cambridge University Press, 2005. ISBN 978-0-521-83540-44
Mossel, E. and Xu, J. Seeded graph matching via large neighborhood statistics. Random Structures & Algo- rithms, 57(3):570-611, 2020..
Hu, and Lau, W. C. A survey and taxonomy of graph sampling. arXiv preprint arXiv:1305 5865, 2013.
Huang, D., Song, X., and Yang, P. information-theone thresholds for the alignments of partially correlated graphs. Conference on Learning Theory, pp. 2494- 2518. PMLR, 2024.
Muratori, A. and Semerjian, G. Faster algorithms for the alignment of sparse correlated Eédōs-Rényi random graphs. arXiv preprint arXiv:2405.0842) 2024.
Otter, The number of trees. Annals of Mathematics, pp. 583-599 1948.
Hughes, T. and Ramage, D. Lexical semantic relatedness with random graph walks. In Proceedings of the 2007 joint conference on empirical methods in natural lan- guage processing and computational natural language learning (EMNIP-CoNILL), pp. 581-589, 2007.
Papagelis, M., Das, G., and Koudas, N. Sampling online social networks. IEEE Transactions on knowledge and data engineering, 25(3):662-67) 2011.

---

Correlation Detection
Piccioli, G., Semerjian, G., Sicuro, G., and Zdeborová, L. Aligning random graphs with sub-tree similarity message-passing algorithm. Journal of Statistical Me- chanies: Theory and Experiment, 2022(6):063401, 2022.
Wu, Y., Cao, N., Archambault, D., Shen, Q., Qu, H., and Cui, W. Evaluation of graph sampling: A visualization perspective. IEEE transactions visualization and com- puter graphics, 23(1):401 (0():401-410,, 2016.
Polyanskiy, Y. and Wu, Y. Information theory: From coding to learning. Cambridge university press, 2025.
Wu, Y., Xu, J., and Yu, S. H. Setting the sharp recon- struction thresholds of random graph matching. IEEE Transactions Information Theory, 68(3):5311-54177, 2022.
Rácz, M. Z. and Sridhar. A. Matching correlated inhomoge- neous random graphs using the k-core estimator. In 2023 IEEE International Symposium on Information Theory (ISIT), pp. 2499-25044 IEEE, 2023.
Wu, Y., Xu, and Yu, S. H. Testing correlation of unlabeled random graphs. The Annals of Applied Probability, 33 (4):2519-2558) 2023.
Ratnayaka, G., Nichols, J., and Wang, Q. Optimal partial graph matching. arXiv preprint arXiv:2410. 16718, 2024.
Yartseva, L. and Grossglauser, percolation graph matching. In Proceedings of the first ACM conference on Online social networks, pp. 119-130, 2013.
the performance of
Sanfeliu, A. and Fu, K.-S. A distance measure between attributed relational graphs for pattern recognition. IEEE Transactions on Systems, Man, and Cybernetics, SMC-13 (3):353-366 1983.
Sharma, C., Nathani, D., and Kaul, M. Solving partial assignment problems using random clique complexes. In International Conference on Machine Learning, pp. 4586 4595. PMLR, 2018.
Singh, R., Xu, J., and Berger, B. Global alignment of multiple protein interaction networks with application to functional orthology detection. Proceedings of the National Academy of Sciences, 105(35):12763-12766 2008.
Stumpf, M. P., Wiuf, C., and May, R. M. Subnets of scale- free networks are not scale-free: sampling properties of networks. Proceedings of the National Academy of Sciences, 102(12):4221 4224, 2005.
Tsybakov, A. B. Introduction to Nonparametric Estimation. Springer Verlag, 2009.
Vogelstein, J. T., Conroy, J. M., Lyzinski, V., Podrazik, L. J., Kratzer, S. G., Harley, T., Fishkind, D. E., Vogelstein, R. J., and Priebe, C. E. Fast approximate quadratic pro- gramming for graph matching. PLOS ONE, 10(,):1-17, 2015.
Wang, H., Wu, Y., Xu, J., and Yolou, I. Random graph matching in geometric models: the case of complete graphs. In Conference on Learning Theory, pp. 3441- 3488. PMLR, 2022.
Wang, R., Guo, 7., Jiang, S., Yang, X., and Yan, J. Deep learning of partial graph matching via differentiable top-k. In Proceedings of the IEFF/CVF Conference on Com- puter Vision and Pattern Recognition, pp. 6272-6281, 2023.
12

---

Correlation Detection
A. Proof of Theorem 1.4
For the possibility results, by Propositions 2.2 and 2.3,
Cin log
0 D<psi-E
P
C2 log(I/(1-p)) Vn)
1 <
then TV (P, 2) S 0.1. Furthermore, if s² = (()), then TV(P, 2) o(1). Since log lox(1/(1-p2))
2 T S
p
(1---00) for any < p S
e - we obtain that (P, 2) S 0.1 when 8² 2 1-11-0-87
C2
nlog
Since
[o
(1((1/(1))))
1 + log(I/(Lto) (oR(1/(1-p))
I 2 for any 1 e < p < 1, it follows that when S² 2 =20
log(1/(1-pi) V m
n lolog
(og[1/(1pp]]
(V, < 0.1. Let T- V 2C2. Then, for 8² 2 C -1111/11--1] Vn)) we have TV (P, 2) S 0.1.
C₁
logn
For the impossibility results, by Propositions 3.1 and 3.5, if s² < (1og(1/(1-p))) p²]]" then TV (P. o(). According the concentration inequality (36) for the Hypergeometric distribution in Lemma D.3, there exists constant C' S $ such that, when 5² < Cn, we have TP [| 2 1] v 0.1, implying IP [|S.-1 = 0] 2 0.9 and thus TV (P, Q) s 0.1. Additionally, when
no
x² = o(n). we have TP [|S = 0] = - o(1), which implies TV (P, Q) = =()) Therefore, if 5² < C ( lo
[og(L1(1--p)) Vn).
then TV CP,PP.O 2) < 0.1. Moreover, s² < C the proof of Theorem 1.4.
ni log (og(1((1_pp)
V or s² o(n), we have TV (P, Q) = o(1). This concludes
B. Proof of Propositions
B.1. Proof of Proposition 2.2
We first upper bound QT 2 7) under the null hypothesis Ho by the Chernoff bound and union bound. For any X,Y Y i...
(00, 1) and A E (0, 1), we have
/
1
(- x² +3²
E [exp (AXY)]
exp (Nrr)) exp
drdy
2T
2
/
1
exp
1
(xx))
(I
Xy)²
exp
- 111-x33 --X219²) drdy
2nT
2
|
1
2²
1 (1 - X2)x²) (1==)))
exp
exp
dzdy VI- X
(13)
2m
2
Let A S. Recall that Sa,m denotes the set of injective mappings π S S V(G)) + V(G2) with |S| = m. For any
ESS, Sp,,. (Hf) Σ - A A₁ where (A,, B;) are independent and identically distributed pairs of standard normals with correlation coefficient p. Then, by the Chernoff bound,
2 (H 2 7| S exp 1-7) EE
exp (Ae (H4)
(14)
m
exp
(-AT) IE
exp (A),
exp
-\
m
m
log (1- (1)
2
2
2
2
(
0²
1
p²
1 m
exp
+
log
1
<
exp
(- 2
0²
(15)
4
2
12
where (a) is because EE [AA.B.]
1 for any 1 <i 5
(m)) (b) follows from log(1 - -x) 2 fo for x
o
00
x
Applying the union bound, we obtain that
2 (T 2 7) < S. 10 (HL) 2 -|
(a)
m
2
m! exp
1 2
m
0²
(b)
S exp
m log
1
en
12
1 m
0²
13

---

Correlation Detection
where (a) is because | = (m) m! and (15); (b) is because (m)! I sm (m)
[
and m
(1-c)=²
Consequently, when m 1-12 24(1 e)) log( we have 2 (7 2 7) S exp (-em log
en
o
p²
Ttc
We then upper bound P (T < T) under the alternative hypothesis Hi. We note that
(a) S P (1S m) + (T < 1S 2 m)
P (T <T)
(b)
x P (1S
< m) + (T 1S 1 m)
(c)
S P P(S
< <m) + (
(
< < 2 m
(16)
IA exp
222
+ exp (-(1) ( /²
+ exp
(-
m P
(17)
2n
2
4cf
2 2co
where (a) is because of (5); (b) follows from (T <, 1S 2 m) S P(T [2m]
P (T <
< |
m): (c) is
P(S.. 12m)
because under the event |S--| 2 m, there exists Tm E Sa,m such that Tm = n on its domain set dom(T ); (d) uses the concentration (37) for Hypergeometric distribution and the Hanson- Hanson-Wright inequality in Lemma D.1 with Mo (())
and 8 = exp (-(2)
Ica ). where eo the universal constant in Lemma D.1. Consequently, we obtain that T T) = (1) when m- 1 2 24(1+e) log Let C1 25. Then, have P (T < <)) QT 2 7) = o[) when
25 log as n becomes sufficiently large.
7
B.2. Proof of Proposition 2.3
We first upper bound (T 2 7) under the null hypothesis Ho. We note that for any X, Y Lid. N(O, 1) and À 0, we have
E exp
- (X (x)- - /
1
exp
x - y)
exp - 1 (x² + +
drdy
2
2T
/
1
X+1
A
2
(-22 2A 1
sp)
exp
1
A 1+1" 11
exp
2(A 2(A+1) 11
dxdy
2T 1
2
/
A 1
2A +
exp
2
exp
2(A + 1) 11²
dydz
(18)
2T
2
VI 2X
Let A 1 4(1-p) 2. Then, we have 1-2X 2(1-p) Since 1 - c < p < 1, we also have À > 0. Recall that S.mm denotes
the set of injective mappings π : S S VVG)) - V(2)) with |S| m. For any т E S. (HL) Σ 1/4 (A, - B))
where (A,, B,) are independent and identically distributed pairs of standard normals with correlation coefficient p. Then, by the Chernoff bound,
( (H+) 2 2) S exp (-Xr) E eep (Ae (H4))
(a)
exp
m ((z
2(( - p)) - log (1 + 22)
1
2
(m))
[
1
= cxp
2 - (1 -1-11
p) p1-p)
log
2
2
2(1 p)
(b)
log [1((1 p)) (m)
exp
(19)
3
2
where (a) follows from (18); (b) is because > - e implies that 2 - (1-p) log
(1 1 2(1-p)
I 1
o log
i-p)
3 log
p-p < - log I-p Then, applying the union bound yields that
1
m
Q 2 7) 4 S.m 2 ( 2 -| S exp mo (
log
3
1 1-p) p
14

---

Correlation Detection
where the last inequality is because [Samm we have (T 2 7) - exp (-em log
(m)
m!!
22
5
m Therefore, when m 1
6(1+r) log f
1og(1/(11p))
en
We then upper bound P (T 7) under the alternative hypothesis H1. By (16), we have that
(TT <T) < <m)
+
[
xx m
< T S > m)
m
I exp
+ exp
(1 - log 2)
2n
2
2
where the last inequality follows from (37) in Lemma D.3 and
1-p x² (()), and the concentration incquality for
chi-square distribution (34) in Lemma D.2. Since m (1-c)s² there exists a universal constant c > 0 such that, when
n
x 2 02, we have P (T <) < 0.05. Specifically, P (T <T) = =1) when s² #/n w(1). Since Q(T 2 r) = o(1) when r log
m- 1 2 6(1+e) log( m²)
there exists a universal constant C2 such that, when s² 2 C2
(1/(1/(11 (1-m) r)) Vn (T <
log(1/(1-m)
Q (T 2 r) < 0.1. Specifically, when /n/n- = (1), we have P (T < < = and thus (T <T) + Q T 2 = Remark B.I. The Gaussian assumption on the weighted edges for Be (G1) and Be (G2) in Propositions 2.2 and 2.3 can be extended to the sub- SabbGaussian assumption. The main ingredients of our proof in these two Propositions are the analysis of the tail bound for the Gaussian distribution. We compute the Moment Generating Function (MGF) and use a standard Chernoff bound to bound 2 (T 2 r). Indeed, if we relax the distribution assumption to a sub-Gaussian distribution, since the linear sum of sub-Gaussian random variables remains a sub-Gaussian random variable, the MGF in (18) can be approximated by E (exp (AXY)]
$ -ーーE for some constant C1 R. Since the product of uub-Gaussian random variables is a
sub-exponential random variable, the MGF in (18) can be approximated by EE eep (- (X (x- r S VT+og for some constant E IR. For P(T <T), the tail bound holds for sub-Gaussian as well.
B.3. Proof of Proposition 3.1
For any S (GG) and T S ((2) with |S| = (T), define
P GTT
II Qo Qo (B.(
II
Qo (B.()))
(20)
og (9)
og (
-T (T))
II Oo (G)(
2o (B.) (E)
II
(21)
where G[S] for any S S VG) denotes the induced subgraph with vertex set S of G; P denotes the distribution of two random graphs follow fully correlated Gaussian Wigner model; Qo denotes the standard normal distribution. Recall that S.,- = V(G1) n (m=)=² (VG))) and T π²" (V)) n (G2)). Indeed, P (G1, G2, S,T) denotes the distribution under PP when given S,- = 5 and T-- = T. Besides, Q (G1, S2 and Q (G1, G2) are the same distribution for any S C (G1), C (G2) with |S| -T'
Since P P(18)-
P(.E)
م P(IS P(|... 1- S and TV (Σ, APP. 2) S E,TV Q) when E, = 1, P(8)
2imo
P(8)
we obtain
((SS.. 1 TV (P (G, -)), ((),))
TV(P'(GI, 2(),
(22)
P(
For any 0 sis (1+e)s² and S C VGG),, C (G2)) with |S] = [ = i, by the data processing inequality (see, e.g.. Polyanskiy & Wu (2025, Section 3.5)), we have
TV (P (G1, G2 S 1). , QGI, G2) S S.
(23)
15

---

Correlation Detection
where the last equality follows from (20), (21) and the fact that (V & 2, @ 2) (X),,)) for any distributions X, Y, Z such that Z is independent with X and Y.
For the random graphs GS[ and G2 with S S VVGI), and |S| = [T], they follow the correlated Gaussian Wigner model with node set size |S] under P, while they are independent under Q. It follows from Wu et al. (2023, Theorem
1) that, when |s|
log S v 3/ر the total variation distance TV (P (Gi[S), G2(T)) Q [G][S), Ga(1)) = o(1). We then verify
the condition log [s] I p²
|s| 2 for any 0 - |S| < (I+c)s² In fact, since s² S 2 2 (1/((11111))) we have
log
|S| S (1 (1+c)s²
(1 + log
2 log (1/p²)
2 2log (1/(1 p2))
p²
where the last inequality follows from log (1/(1- - p²)) 2 p², 3 log (1/p²)
logn 2
< log (1/p²) and e < 1. Therefore, we obtain
|S] IST
pr. and thus
Tog(1/p" ++lppp22)++ (2
TV
= =(1)
for any S S with |S| |T| < [1tc)_ Combining this with (22) and (23), we conclude that
(1-1)²
P1S =1) i)
TV (P'',G (2) 2 G2)) <
(V 2 (G) G2))
(E)
P P188+11 1= i)
o(1) -0)= o
(())
Therefore,
(a) TV(P(G), 2(r, S
2(1,
(b) TV(P T), P' =P ((G1, G2, x) $ E) + TV (P' Gz), QG,, Gz)) = o1).
(24)
where (a) follows from the triangle inequality and (b) is derived by the data processing inequality (see, e.g., Polyanskiy &
Wu (2025, Section 3.5)).
B.4. Proof of Proposition 3.5
Recall that the conditional distribution is defined as
P' G2, P(G1, G2, T) (GG (1 o(1)) (Gi, G2, (G Ga.T)e8
D(E)
where the last inequality holds because -1))=1-0(1 By (6) and (24), we have the following sufficient condition for the impossibility results:
P'(GI, G2) @(G), Gz)
2
Be
=1+ TV Q) o(1) = TV(P, Q) o(1).
(25)
Recall the likelihood ratio in (7). To compute the conditional second moment, we introduce an independent copy ă of the latent permutation and express the square likelihood ratio as
( ((G),G2)
P'(G1, G2) 2
P(G1,Gylm) G2) L Gs.
[(G1, G2lmt Ex
(1+
Q(G,, Gz) GG,
P(G G2(x) P(G,, G2l Q(G1, Gz) ((G,,G,)
(1 +1)
16

---

Correlation Detection
Taking expectation for both sides under 2, the conditional second moment given by
(
P'(GG,
27 Q(G), G2)
Ggl1, P
ee
(1 + (
B
(a.. G2)
G2),,
Gel1,
[GG,,G2li
= + =1++
E
(c, G2. ( (G.G2.))
G2)
1 G2)
P(G G2 m) P(G G2
= I.C.C..riee
(26)
@ G2) _ G2)
where the last equality holds since & is independent with the edges in G1 and G2. Recall that / = (T, m) defined in (10). Since J' Ueec Used (V by the definition of I* we obtain that (22 Ecec |C| by counting the edges induced by the vertices in I* Combining this with (9) and (26), have that
(
('(G1,
27 )
P(G P(G, Q(G,, G2)
Ee
Q(G
(1 (1+ (1)) L*
@G G2)
= +1
(G G2AtE
II
p2|0
CEC
1017
$ <1+ (L)
(GG
II CEC
1
- p² 1
-11)/12))))
1
= (1 + oL
1- p2
where the inequality follows from +
(1=0))++()))
(1-p-=X1--7 S 1-02+0-1
0 for any 0 < < and
(1-p-)111pp
1. Since IP ||/*| = 1) < (+)
by Lemma 3.4 and [|]| S [V(G))) < (Lte)a" if if G2, T), (G), G2, π) E
we obtain
P'((),, G2) 2
1 17(11111)/2
Eg
2 + o(1)) (en.can)Ee
@(G1,
p1
a10b2
01022
1(1-1)/2
2r
1
t(t-1)/2
= +1+
P| =t]
$ (1 + o())
p²
7
1 - p²
(27)
8(t- 1(t-1)/2
Let 0,
(2)²
For any
(1+e)s² n
have
1-p²
(
0++1
2
22
52
(1 + s)s²
1 1-p²) )1-1))
exp
log
+
log
(28)
n
1
2²
n²
1 - p2
n2
Since 52 < 8log 1/((1p1)))))))))) we obtain
ni logn
(1 + e)s²
(1 + e) log
log
n
1 12
and
82
log n
)
(4)
1
llog
log
< log
log + log
n
8m log (1/ - (/(1)
2
8
17

---

Correlation Detection
where (a) is because log
1-p2 2 log 1-n-1yz
2 n n/12 Combining this with (28), we obtain that Rill
exp
(3-c) n
+ log
Iogn
S n2
1/4, Therefore, by (27),
(++)
P'( G2)
Ee
$ (1 + (())
(2)
t=
(++))22
(8)
1(t-1)/2
+ o11
= =11+)(1))
1 + o(1) 1/4
n
1- 1-p² p²
1 - 11/4
t=
which implies that TV(P,, = o(1) (25).
C. Proof of Lemmas
C.1. Proof of Lemma 2.1
Recall that [V(G:)) [V(22) and V(G1) S V(G.), S (G2)). For any π Sn note that the event (VV()) n ( with / [s] can be divided as:
Picking vertices in V(G,), (G22) respectively and constructing the mapping between picked vertices. We have (9) options for this step.
Mapping the remaining t vertices in V(G1) ((G2). We have (--i (s t)! options for this step.
Mapping ((G))VV(G)) to the remaining vertices in V(G2). We have (n s)! options for this step.
Then, for any S 8, we have that
(1) P[I((V))) -1) (?-)) (s- - t)! (n - 8)
(29)
n!
which indicates that the size of intersection set [=(V(G)) follows hypergeometric distribution HG(n, s) where Unif. S..
C.2. Proof of Lemma 3.3
For any P (e1, x(11), e2. ... .e.,, E P with =(e)) (((e),,..,;;E))) x(e--)), have that
$ Lp II (e, (e,))) II lle, F(e:)) = I[ (e,, (e,))) II lle, ((e-)))))))
= (())))((((())))))))) ... ee)
(30)
Under the distribution Q. it follows from (30) that Lp ((Bo, (B),(BI, Bz) ((Bx-1, Br) for some k and Bo, B,, BB Lid. No0,, 1). Recall that
P (G1) = (G2)) b)) 1
-p'(a" + b²) + 2pab
laa b)
exp
for any a. R. (31)
2 (G1 = a, (G2) -b) V1 Ø²
2(1 - p2)
Then,
Eo [pp Be [e(Bo, Bi)E(BI, Bz) B.).... -.BBBBBB1Bb Bx)]
(b2 + b2+ + 2pbrbe+1
1
(1- 222 |'. exp
exp Σ
dbp dd
( ((1 -
2(1 - p2)
2
Σ Ek-1 (b: pbl+1)² 1
02
(22))(++1)/2 ((1 22)) | exp
dbu ... ...bb 1,
2(1 - p²)
18

---

Correlation Detection
where the last equality holds since the transformation By B. Bu-pBeu1 for any 0 k 1 yields that Ee [Lp]
V1-p²
(27) .... .. fexp
b2
dbg ......l.. .... dbb 1.
For any C = (e1, (e)), : ej (ee)) E with #(e2) x(e)), ; = x(es-1) and #(e1) T(e)). we denote
eo Ej for notational simplicity. Then, we have that
Lc II (e, II ((e,)(e)))) = II ele (())) II (( ==1
==1
= =(1)) ... ((T(e)-1), ez ej), (())))))))))))
Then Le E(Bi, B2) 11 Bx) (B,, Bi) for 2j and Bi, ... Bx iid NO0, 1). Denote BR+1 Bi, we have that
BelLcl = Be [e( B2) Bx) B1)l --1
1t= p² (b) + bi41) + 2pb,br+1
exp
exp Σ
db
dbb
(2 - 02))
2(1 p²)
2
(2m(1 -2) /
k-1 (br - pbl+1)² 2t=0
exp
dbi ... ..dbk.
2(1 p2)
Let C, e Br pB++1 for any 1 s < k. Then
[C1. C2 Ck-1. Ck] = Jj [B1, B2, ... BB- BEl
where
1 -
0
0
0
p
0
0
1
...
0
and thus det (Jx) pt (see, e.g., Davis (1979, Section 3.2)). Then, we obtain that
Eg|Lel= = (2 - /2)) det (Jx) / /.. exp
Σ ot 2(1 p22)
1
/ex
deg dop 1 1 pt 1 - -
C.3. Proof of Lemma 3.4
Let A arggaa (V M. we first show that /' = 1* On the one hand, since rT(') = *(''), we have (12) = ((5) Recall that the connected components of the correlated functional digraph in Definition 3.2 consist of paths and cycles. For any path P P, we note that æ (PnV + (Pn ((r)), and thus ( ( (enV(G))) * (PDV(G:)) For any cycle e C, we note that (CnV(G.) (nnVIG))) Therefore, (1) C Ucec UsECnE(G,) e. By the definition of I", we obtain J' T" the other hand, for any C E C, since ग (VeeCnE(G,)))) = (Veecne(c,))) by the definition of cycle and C n for any C # #C' E we have that
(CDV(G))) and thus æ
(NV(G)))
t (UCEC UsECnE e) = # (UOec UsECn e).
Therefore, we have ग (Voec UsEC U) = (Woec UsEO UnEvte)nv(aL)t) which implies T(I") = =[(I). Since 1" S V(G1), by the definition of I'. we conclude that I" S P'. Therefore, we have Ie =
19

---

Correlation Detection
For any & 8, by the union bound, we obtain
P = 4 S PIAC V(G.), - (A) - - C
C V(G.)
S ()P(AC [4] ( =(A) C V(G2)
(32)
For any fixed set A S ( with |A| = t and π (AA) = =(A) S ((2)), we first choose set B C (G22) with B = t
and set π (A) #(A)= = B. There are (i) ways to choose B, and t! ways to map (TA) [(A) = B. For the remaining
vertices in V(G1), there are (n t)!² ways to map them under н and म. Therefore,
() | = t, (A) = # (A) S V(G2)] (t)
(n!)) adl t = -
2
(33)
7
s(s (-m 12 n(a- (mn-)+))
where the last inequality is due to the fact that (:) mni (i) 112 (1)
(1 - 1)1²
and for any i = 1,.. ,6-1, 1,
Combining this with (32), we obtain P ||| = t S (
D. Auxiliary Results
D.I. Concentration Inequalities for Gaussian
Lemma D.1 (Hanson- (Hanson-Wright inequality). Let X, Y E R" be standard Gaussian vectors such that the pairs (X4, Yi)
W/ (0) C: )) are independent for = 1,. n. Let Mo E Rax be any deterministic matrix. There exists some
universal constant co > 0 such that
TP P[xT M,Y -pr(MMo)) 2 co (1Molle/log(1//) 1|Moll log(1)))
Proof. Note that X M,Y = (xX +Y) Mo(x - - - 1) M - Y) and
E [XX Y) Mo(X + +Y] = (2 22 Tr) MM), E [(x- ( Y) Mo - Y)] 2p) Tr
By Hanson- Wright inequality (Hanson & Wright, 1971), there exists some universal constant Co such that
P (x+r) Mo(X + 2+24 2p
Co |I.olll v ||ooll (og()))))(1
Tr(
2 2
4
22
P (Y) Mo(x - Y) - 2p
Tr(Mo)
2 2
Co
(1.6lll v ||oll hogllloo((//// (1)))
1910
4
for any 5 > O. Consequently,
P
X MOY - pTH(M))) 2 (11 Tooool//lole 1og(1/8) V ||Moll2
< IP
7 (X +Y) MM +X)
2 2+2p Tr(Mo)
[| v || (o0g))))
4
2
(x M)TM6XX- - 2-2p Tr(Mo)
+ PP
v ||ooll ( log(1/))) 86.
4
2
D.2. Concentration Inequalities for Chi-Squared Distribution
Lemma D.2 (Chernoff's inequality for Chi-squared distribution). Suppose (n). Then, for any 8 > 0, we have
P > (1+ 8)m] < exp
(5 log (1 + 51)
(34)
2
P < (1 - 8)m] < exp
n
(-8 - log(1 - 6))
(35)
2
Proof. The results follow from Theorems and in Ghosh (2021).
20

---

Correlation Detection
D.3. Concentration Inequalities for Hypergeometric Distribution
Lemma D.3 (Concentration inequalities for Hypergeometric distribution). For yj
HG(nn 8, 8) and any have
P 1 (1 + E)s²
E²
2
S exp
Mexp
(36)
n
(2+ c)m
n
c)
228²
228
P
1 S
S exp
A exp
(37)
2n
112
Proof. Denote & Bin (s, a). by Theorem 4 in Hoeffding (1994), for any continuous and convex function f, we have
[ < [
We note the function f(x) exp (Ax) is continuous and convex for any À R. Therefore, have E (exp (An)) S E lexp (AE) for any À E R, and thus the Chernoff bound for remains valid for 1). Combining this with Theorems 4.4 and 4.5 in Mitzenmacher & Upfal (2005), we have
(1+ c)s²
exp (- E²
(1 - c)s²
E²3²
P
(T22+
(2+ + E)M
P
< exp
2n
By Hoeffding's inequallity (Hoeffding, 1994), we also have
c)+
223
(1 c)s2
2
S exp
(-n²²
P
1
I exp
n
n²
n12
Therefore, we finish the proof of Lemma D.3.
E. Additional Experiments
We provide simple illustration on how our algorithm can be applied on real dataset. We conduct an experiment on Freeman's EIES networks (Freeman & Freeman, 1979), a small dataset of 46 researchers, where edge weights represent communication strength at two time points. We apply our method to test for correlation between these two temporal networks. We examine how sample size affects privacy protection by analyzing the normalized similarity score, defined as the similarity score e(H{) divided by (*). Indeed, lower score suggests weaker correlation and greater support for the null hypothesis of independence.
We apply algorithm to the EIES dataset different sample sizes, 10, 20, 40 and compute the corresponding normalized similarity scores: -10066, -0.905, and -0.651. The scores increase with sample size, indicating stronger detected correlation. The lower scores at small sample sizes reflect failed correlation detection, quantifying the reduction in re-identification risk.
21


Reviews:
[{"review_id": "ONyOSOL7Al", "reviewer": "Reviewer_stro", "summary": "The paper studies the detection of correlations in pairs of graphs generated by the Gaussian Wigner model when only induced subgraphs are observed. It establishes nearly sharp sample complexity thresholds for successful detection via both possibility and impossibility results and introduces two estimators (one maximizing overlap and one based on mean-squared error) alongside an efficient clique-based algorithm. Synthetic experiments demonstrate promising separation between the null and alternative hypotheses.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable comments.\n\n**Q1: The impact of the parameters on runtime and performance.**\n\nThanks for the suggestion. We will add more discussions on this point after Algorithm 1. The time complexity is $O(N_1\\cdot s^{K_1}+N_2^{K_2})$ (see line 368, column 1). Hence, the runtime increases with $K_1$, $K_2$, and $s$. The performance improves with $s$; it initially improves with $K_1$ and $K_2$ but degrades when $K_1$ and $K_2$ become too large: \n\n- $s$: A larger sample size $s$ leads to larger common vertex sets (see line 133, column 2), and thus increases the number of correct mappings in Step 1.\n\n- $K_1$: A larger $K_1$ corresponds to matching larger cliques in the first step. This increases the proportion of correct mappings within the $N_2$ candidate pairs when $K_1$ is below the size of common vertex sets. However,  choosing $K_1$ beyond this size introduces wrong mappings.\n\n- $K_2$: In the second step, we search over all $U\\subseteq [N_2]$ with $|U| = K_2$ to identify the seeds. While a larger $K_2$ imposes a stricter matching criterion, choosing $K_2$ beyond the number of available correct mappings from Step 1 will degrade performance. \n\n**Q2: Additional explanatory details.**\n\nWe will add more explanatory details in Sections 2 and 3 including the following before the presentation of technical results: \n\n- Section 2: The quantity $\\mathsf{e}(\\mathcal{H}_\\pi^f)$ measures the similarity score of a mapping $\\pi$. \n\n1) Under the null hypothesis, $\\mathsf{e}(\\mathcal{H}^f_\\pi)$ has a zero mean for all $\\pi$, whereas under the alternative hypothesis, its mean with $\\pi=\\pi^*$ is strictly positive owing to the underlying correlation. \nWe derive concentration inequalities to ensure that $\\mathsf{e}(\\mathcal{H}^f_{\\pi^*})$ exceeds the maximum spurious score arising from stochastic fluctuations under the null, as shown in Propositions 2.2 and 2.3. \n\n2) The choice of two similarity scores is based on the maximum likelihood estimate with $f(x,y)=-\\rho^2(x^2+y^2)+2\\rho xy$, as discussed in Remark 2.5. \n\n3) Since vertices are sampled without replacement from the two graphs, the number of intersecting vertices follow a hypergeometric distribution, which is analyzed in Lemma 2.1. \n\n- Section 3: The key is to identify the bottleneck for distinguishing the two hypotheses.\n\n1) Under weak correlation, the bottleneck is detecting the existence of latent mapping $\\pi^*$. The detection is impossible even with the additional knowledge on the location of common vertices, as shown in Proposition 3.1.\n\n2) Under strong correlation, detecting $\\pi^*$ is no longer the bottleneck. We prove Proposition 3.5 by conditioning on a high probability event (8) on the number of intersecting vertices. One key step is the reduction to a subset $I^*$ of intersecting vertices, as discussed in Remark 3.6.", "claims_and_evidence": "### Main Claims:\n\n- Derivation of nearly sharp sample complexity thresholds for detecting correlation under induced subgraph sampling.\n\n- Presentation of two estimators tailored for different regimes.\n\n- Proposal of an efficient, clique-based approximation algorithm.\n\n### Evidence:\n\n- Theoretical results are supported by detailed proofs using the conditional second moment method and concentration inequalities.\n\n- Synthetic experiments (ROC curves, histograms) validate the method’s ability to distinguish between independent and correlated graphs.", "methods_and_evaluation_criteria": "- Use of induced subgraph sampling and rigorous probabilistic tools (e.g., Chernoff bounds, hypergeometric concentration).\n\n- A two-pronged estimation strategy (maximal overlap vs. mean-squared error) to handle various correlation regimes.\n\n- A novel, efficient algorithm for approximating the ideal estimator via clique-seeding and iterative matching.", "theoretical_claims": "I have not reviewed the proofs.", "experimental_designs_or_analyses": "- The synthetic experimental design is sound and well-conceived.\n\n- Performance is measured via ROC curves and histograms of the test statistic.", "relation_to_broader_scientific_literature": "The paper builds upon and extends recent work on graph matching and correlation detection in random graphs, particularly in the Gaussian Wigner model.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "### Strengths:\n\n- The paper makes theoretical contributions by deriving near-optimal detection thresholds.\n\n- Its blend of rigorous probabilistic analysis with an efficient algorithm is especially commendable.\n\n### Weaknesses:\n\n- The paper does not sufficiently explore how the key parameters (e.g., clique size $K_1$, combining size $K_2$, number of samples) affect the performance and running time of the algorithm. More discussion or analysis of these trade-offs would be valuable.\n\n- Some sections of the theoretical analysis could benefit from additional explanatory detail to ensure accessibility, particularly for readers less familiar with advanced probabilistic methods.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Please refer to my previous comments.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IKImtlMKXK", "reviewer": "Reviewer_vzDn", "summary": "This paper studies the problem of correlation detection in the Gaussian Wigner Model, formulating it as a hypothesis testing problem. The authors analyze the sample complexity required for correlation detection when only two induced subgraphs are observed. The main theoretical contribution is the derivation of the optimal sample size required for detection, based on a second-moment analysis. Additionally, the paper presents an efficient approximate algorithm for detecting correlation, which improves computational efficiency compared to brute-force approaches. The results provide insight into the statistical limits of graph correlation detection when only partial observations are available.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable comments.\n\n**Q1: Graph topology and structural noise.**\n\nThank you for the question. The graph topology and structural noise can be incorporated into our analytical framework. Particularly, most results in this paper can be extended to the Erdős–Rényi model. The key difference lies in the additional parameter $p$ controlling the edge connection probability.\n\n- Possibility results. The estimator is similar to equation (2), with the function $f$ selected via MLE under the Erdős–Rényi model. Both Type I and Type II errors can be controlled using the Chernoff bound for the binomial distributions in place of Gaussian. \n\n- Impossibility results. When the edge connecting probability satisfies $p = n^{-\\Omega(1)}$, the optimal results follow a reduction analogous to Proposition 3.1, leveraging existing lower bounds given the location of common vertices. However, such reduction does not yield tight bounds when $p = n^{-o(1)}$. In this regime, a more delicate event is required for the conditional second moment analysis similar to Proposition 3.5. Nevertheless, the reduction to the core set defined in (10) remains valid. \n\nWe are currently pursuing a complete resolution to this problem. \n\n**Q2: Essential references.**\n\nThank you for suggesting those references.\nThe partial recovery in Hall and Massoulié (2023) is relevant to correlation detection problem. This is cited in line 106, column 2.\nMessage-passing approaches in Piccioli, Semerjian, Sicuro and Zdeborová (2022) and  the Otter's constant in Ganassali, Massoulié and Semerjian (2024) are also related to our problem under the extension to the Erdős–Rényi model, especially in the analysis of efficient algorithms.\nWe will incorporate the citations and expand our discussion accordingly. \n\n\n**Q3: Runtime analysis.**\n\nThe time complexity is $O(N_1\\cdot s^{K_1}+N_2^{K_2})$ (see line 368, column 1). Our algorithm comprises three main steps. In the first step, we select $N_1$ vertex sets $V_1,\\cdots, V_{N_1}$ of size $K_1$ and search for injections $\\pi_i$ from $V_i$ to $V(G_2)$, which requires $O(N_1\\cdot s^{K_1})$ time. In the second step, we search over all subsets $U\\subseteq [N_2]$ with $|U| = K_2$, which takes $O(N_2^{K_2})$ time. In the third step, we iteratively expand the mapping based on our seeds, which takes $O(m^2 s^2)$ time. We typically choose $N_1\\asymp s^{K_1}$ and $K_1\\ge 3$, leading to an overall time complexity of $O(N_1\\cdot s^{K_1}+N_2^{K_2})$. For the trade-off between performance and runtime, please refer to our response to Q1 from Reviewer stro.", "claims_and_evidence": "The paper makes several claims about the optimal sample complexity needed to distinguish between independent and correlated Gaussian Wigner graphs. The results align well with previous work on full-graph correlation detection but extend them to subsampled settings, which has not been studied extensively before. However, a notable limitation is that the role of graph topology is largely absent from the analysis. While the authors assume a dense setting, real-world graphs often have sparse structures (e.g., Erdős–Rényi models), and it is unclear how their results generalize to such cases. Additionally, the paper does not account for structural noise, such as missing or spurious edges, which has been a key challenge in previous works on graph alignment.\n\nThe authors also introduce an approximate detection algorithm, which reduces the computational burden of exhaustive search. The empirical validation suggests that the method performs well on synthetic data, but a theoretical complexity analysis of the algorithm is missing, which would strengthen the practical relevance of the results.", "methods_and_evaluation_criteria": "The theoretical results are derived using standard tools in high-dimensional hypothesis testing, particularly likelihood ratio methods and second-moment analysis. The total variation distance (TV) is used as a measure of distinguishability, and the paper establishes strong and weak detection conditions for correlation inference. These methods are rigorous and align well with prior work in this field.\n\nHowever, there are some limitations:\n\nGraph topology is largely ignored – The analysis assumes a dense Gaussian Wigner model, but many real-world applications involve sparse graphs (such as Erdős–Rényi graphs). It would be useful to discuss whether the topology can be incorporated as additional weights.\nNo consideration of edge noise – In realistic settings, edges might be randomly missing or spurious. The results assume that the edge structure is perfectly known, which is a strong assumption.\nComparison with prior message-passing approaches is missing – The authors do not compare their method to existing graph alignment algorithms that use message passing (see appendix A in arXiv:2112.13079). It would be interesting to explore whether their algorithm could be extended to sparse settings using those techniques.\n\nThe empirical evaluation demonstrates the effectiveness of the detection algorithm, but it is limited to synthetic data with idealized conditions. Real-world datasets or at least non-Gaussian noise models could be considered to validate the robustness of the method.", "theoretical_claims": "The theoretical results appear correct and well-supported by derivations. The main contribution is the identification of the optimal sample complexity threshold for detecting correlation in subsampled Wigner graphs, which is consistent with previous results in the full-graph setting but extends them to the case of induced subgraphs. The use of the conditional second moment method is appropriate for establishing lower bounds on sample complexity.\n\nHowever, the assumption that graph structure does not affect correlation detection is somewhat counterintuitive. In previous work on graph alignment, including results by Semerjian and Massoulié (arXiv:2209.13723), the presence of tree-like structures was shown to have an impact on the detectability of correlation. The authors should clarify whether their results implicitly assume the graph is dense, or if the topology effects can be incorporated into the framework.", "experimental_designs_or_analyses": "The experiments focus on synthetic graphs generated from the Gaussian Wigner model, with varying correlation strengths and sample sizes. The results confirm the theoretical predictions.\n\nTthere are a few limitations: The graphs are fully observed apart from subsampling, meaning that they do not test settings where edges themselves are noisy or missing. There is no comparison to other detection methods. How does the proposed approach compare to existing graph matching techniques, such as those based on Otter’s constant for tree alignment? The runtime analysis of the algorithm is missing. The approximate algorithm is stated to be efficient, but there is no complexity bound or scalability analysis.", "relation_to_broader_scientific_literature": "The paper is connected to graph alignment and graph matching problems. There are strong similarities with prior work on Erdős–Rényi graph alignment, where matching thresholds have been studied extensively. However, the authors do not sufficiently acknowledge prior works that consider sparse graphs and topology effects. Specifically:\n\nThe results in Hall & Massoulié (2023) on partial graph alignment are relevant, as they consider detection under more general assumptions.\nThe role of Otter’s constant in graph alignment, as discussed in Semerjian and Massouli's work, should be acknowledged, as it might be relevant for understanding detectability limits in tree-like graphs.\nThe message-passing approach for weighted graphs from  arXiv:2112.13079 should be discussed as a potential extension for sparse settings.", "essential_references_not_discussed": "Essential References Not Discussed\n\n-arXiv:2112.13079 which discusses message-passing approaches for graph matching in weighted settings.\n-Hall & Massoulié (2023), which explores partial recovery in graph alignment under more general conditions.\n- Otter’s constant and tree alignment results from Semerjian and Massoullie work, which may have implications for detection thresholds.", "other_strengths_and_weaknesses": "Strengths:\n\nThe paper provides clear theoretical results on the sample complexity of correlation detection.\nThe use of induced subgraph sampling is novel and relevant for practical applications.\nThe proposed approximate algorithm reduces computational costs compared to brute-force methods.\nWeaknesses:\n\nGraph topology is ignored – The results assume a dense setting, which may not generalize to sparse graphs.\nNo analysis of edge noise – Real-world graphs often contain missing or spurious edges, which are not accounted for.\nNo comparison with prior message-passing methods – The paper does not discuss existing methods for weighted graph alignment.\nNo complexity analysis of the algorithm – The proposed algorithm is claimed to be efficient, but no formal runtime bounds are given.", "other_comments_or_suggestions": "The authors should clarify whether graph topology can be incorporated into their model.\nA discussion of how the results extend to Erdős–Rényi graphs would be useful.\nThe paper should cite Semerjian's work on Otter’s constant in graph alignment, as it may be relevant.\nA runtime analysis of the detection algorithm should be provided.", "questions_for_authors": "How does the method extend to sparse graphs, such as Erdős–Rényi models?\nCould the results change if edges were noisy or missing?\nHow does the proposed algorithm compare to message-passing approaches for graph alignment?\nCan Otter’s constant play a role in the detection threshold?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yLNZ6B8F5h", "reviewer": "Reviewer_uxiK", "summary": "This paper addresses the problem of detecting correlation between two random graphs generated from the Gaussian Wigner model. In particular, tha authors focus on the scenario where two induced subgraphs are sampled. It establishes the optimal sample complexity for correlation detection and proposes two test statistics. They introduce a fast approximate algorithm based on clique matching and iterative mapping extension, which improves computational efficiency. Finally, they confirm the effectiveness of the algorithm with numerical simulations.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback. We will add an overview of the paper and highlight the contributions in the introduction.", "claims_and_evidence": "All claims are supported by convincing evidence.", "methods_and_evaluation_criteria": "The methods are well-suited for this problem.", "theoretical_claims": "I have checked the proofs for the main theorem and the possibility results. I have no issues to discuss.", "experimental_designs_or_analyses": "I have no issues to discuss.", "relation_to_broader_scientific_literature": "The paper builds on the literature on correlation detection in the Gaussian Wigner model. While previous works focused on detection thresholds for fully observed graphs, this paper extends the results to the sampled subgraph case, using established techniques like the conditional second moment method. Moreover, it builds on existing work in graph and clique matching to propose an efficient algorithm.", "essential_references_not_discussed": "I’m not aware of any relevant references that have been omitted.", "other_strengths_and_weaknesses": "The paper addresses a relevant problem with applications in biological networks, natural language processing, and social network analysis. It benefits from a clear and well-structured presentation, rigorous and complete theoretical results, and convincing numerical simulations that support the claims. The authors provide a thorough discussion of related literature and clearly state the limitations of their work and potential future directions. I have not identified any major weaknesses.", "other_comments_or_suggestions": "I would suggest to include an overview of the paper's structure in the Introduction, providing a brief description of the topics covered in each section and highlighting all the contributions of the work.", "questions_for_authors": "I do not have any specific questions for the authors.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Uy5I4b4RDL", "reviewer": "Reviewer_1rVu", "summary": "The paper focuses on detecting correlations between a pair of random graphs, using the Gaussian Wigner model where edge weights are drawn from a Gaussian distribution. This is framed as hypothesis testing, determining whether the graphs are independent (null hypothesis) or edge-correlated (alternative hypothesis). In the latter case, each edges are generated from a Gaussian with correlation coefficient $\\rho$, then vertex labels are permuted. The study focuses on scenarios where induced subgraphs are sampled from the original graphs, which the authors motivate by the fact that (among other factors) graphs are often only possible to query via node sampling with an API. The authors derive the optimal rate for the sample size for correlation detection, and propose (but do not theoretically study) an efficient approximate algorithm to reduce running time. Numerical studies back up their theoretical claims.\n\n*Update after rebuttal*. Whilst I still have some reservations about the utility to ML researchers, this is a strong, well-written paper with nice mathematical contributions. I have raised my score to 'weak accept'.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable comments.\n\n**Q1: The correlation analysis between random graphs and its relation with modern machine learning.**\n\nThere are many papers on top machine learning conferences and journals addressing related problems. \nOur hypothesis testing problem is also known as graph similarity studied by (Barak, Chou, Lei et al., 2019, NeurIPS), which provides additional references and surveys on this topic.\nCorrelation analysis is also a natural first step towards the graph matching problem, which is studied by (Araya, Braun and Tyagi, 2024, JMLR), (Lyzinski, Fishkind and\nPriebe, 2014, JMLR), (Lyzinski, Fishkind, Fiori et al., 2015, TPAMI), (Racz and Sridhar, 2021, NeurIPS), (Gaudio, Racz, and Sridhar, 2022, COLT). \n\nThe algorithm in our paper can be used in various domains:\n\n- In NLP, nodes correspond to words or phrases, and the weighted edges represent syntactic and semantic relationships (Hughes and Ramage, 2007, EMNLP).\nThe algorithm can be used to test whether knowledge graphs from different languages are correlated. \n\n- In computational biology, proteins are the nodes, and the interactions between them are weighted edges (Singh, Xu, and Berger, 2008, PNAS).\nThe algorithm can be applied to test whether two protein networks are correlated.\n\n- In computer vision, nodes are subregions and weighted edges represent adjacency relationships between different regions (Berg, Berg, and Malik, 2005, CVPR).\nThe algorithm can be applied to test whether two graphs represent the same object. \n\nWe will add more discussions on those applications. \n\n**Q2: Extension to Erdős–Rényi model.**\n\nMost results in this paper can be extended to the Erdős–Rényi model. The key difference lies in the additional parameter $p$ controlling the edge connection probability. For the details on extending our possibility and impossibility results, please refer to our response to Q1 from Reviewer vzDn. We will add more discussions on this extension.\n\n**Q3: Baselines or benchmark datasets.**\n\nWe are not aware of any suitable benchmark datasets or publicly available baselines for comparison on the correlation detection problem in the Gaussian Wigner model.\nThere are established methods for graph distance and graph similarity such as classical graph edit distance (GED). Under the same numerical experiments, our algorithm achieves superior performance. When $n=50, s=30$, and $\\epsilon = 0.01$, the AUC values for the GED-based test at $\\rho = 0.98, 1-10^{-6}, 1-10^{-7}$ are $0.53, 0.73, 0.88$, respectively. In contrast, the AUC values in our algorithm for the same values of $\\rho$ are $0.92,1,1$. \nWe will add the comparison in our paper.", "claims_and_evidence": "The core claim, given in Thm 1.4, is a result for the optimal rate for the sample size s required for correlation detection in this model. It depends on the number of nodes and the correlation coefficient. The evidence seems convincing, and leads to specific conditions for the possibility and impossibility of detection. The authors also propose an efficient algorithm to approximate the estimator with lower time complexity, and Sec 5 gives strong empirical evidence that it works on synthetic data (the histograms are well-separated for the independent and correlated models). All claims made in the submission appear to be well-supported by evidence.", "methods_and_evaluation_criteria": "As described above, Sec 5 presents numerical experiments to verify the authors’ theoretical results. This involves generating 100 pairs of graphs with n=50 that are either independent or correlated, then plotting a histogram for the (approximated) estimator. The authors also compare the test statistic tinder different settings, plotting the ROC curves with varying detection threshold, recording the Type II error against the Type I error. They compute the AUC for different sample sizes s -- which naturally increases as s grows. \n\nThe authors do not compare to baselines or evaluate on benchmark datasets, but it’s not clear that this would make sense for the problem at hand.", "theoretical_claims": "I did not check the mathematical proofs in detail, but the claims seem reasonable.", "experimental_designs_or_analyses": "See above. The experimental designs make sense for the paper’s current scope -- namely, correlation detection for the Gaussian Wigner model.", "relation_to_broader_scientific_literature": "The paper tackles the problem of correlation detection between random graphs. It builds upon a broader literature on graph matching for correlated random graphs, including in the the Erdős-Rényi model (Cullina & Kiyavash (2016; 2017); Hall & Massoulie (2023)) where edges are Bernoulli (c.f. Gaussian) random variables. It specifically focuses on the graph sampling setting, where not all nodes are available (Leskovec & Faloutsos, 2006; Hu & Lau, 2013). I understand that this is a significant area of study in computational mathematics, but it is less clear to me that this will be of interest to researchers in machine learning.", "essential_references_not_discussed": "The references seem reasonable.", "other_strengths_and_weaknesses": "**Strengths**:\n- Clearly written paper with rigorous mathematical results and concrete algorithms. The authors convincingly demonstrate that this will be of interest to folks working on correlation analysis between graphs, and it seems likely that similar ideas will extend to random graph models beyond Wigner. \n- Efficient implementation that performs well in practice in numerical experiments.\n\n**Weaknesses**:\n- Whilst mathematically sophisticated and well-presented, it is unclear to me that this problem will be of interest to the audience at ICML.", "other_comments_or_suggestions": "Please see above and below.", "questions_for_authors": "- Can you provide convincing evidence that correlation analysis between random graphs is a problem of interest in the setting of modern machine learning? For instance, can you cite papers at top conferences addressing this problem, or demonstrate more concretely how your algorithms can be used in computational biology or NLP (lines 44 and 47)? I think it’s great to have high-calibre mathematical work at ML conferences (often lacking!), but it does need to be relevant to the community.\n- To what extent do you expect your results to generalise to other random graph models like Erdős–Rényi, and to what extent are they peculiar to Gaussian Wigner?\n\nIn my mind, the first question is the big one – I will be ready to raise my score if you can provide more evidence ML folks should care about this. Would a computational mathematics journal not be more suitable for your strong new results?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the fundamental limits of detecting correlation between low-rank signals in multiple independent instances of the spiked Gaussian Wigner model. It provides tight information-theoretic thresholds for detection and proposes a spectral method that is shown to be optimal in a significant parameter regime. Reviewers appreciated the clarity of the problem formulation, the rigor of the analysis, and the overall quality of exposition. The work fits well within the growing body of research on high-dimensional inference problems at the interface of statistics and theoretical machine learning.

While the paper is primarily theoretical, reviewers noted its potential relevance to multi-view or multi-modal learning problems in ML. The connections to broader applications could be made more explicit, and the practical interpretation of the thresholds might be further clarified. Nonetheless, the contribution is technically solid, the results are novel and precisely characterized, and the paper is well-executed. The submission is a strong fit for the theory track and deserves acceptance.
Decision: Accept (poster)