Network two-sample test for block models
Authors: Chung Kyong Nguen
Arash A. Amini
OSCAR HERNAN MADRID PADILLA
Venue: NeurIPS 2025 poster ()
Keywords: Stochastic block model
SBM
two-sample test
spectral graph matching
Primary area: theory
TL;DR: A consistent scalable two-sample test for unlabeled networks based on spectral matching.

Abstract: We consider the two-sample testing problem for networks, where the goal is to determine whether two sets of networks originated from the same stochastic model. Assuming no vertex correspondence and allowing for different numbers of nodes, we address a fundamental network testing problem that goes beyond simple adjacency matrix comparisons. We adopt the stochastic block model (SBM) for network distributions, due to their interpretability and the potential to approximate more general models. The lack of meaningful node labels and vertex correspondence translate to a graph matching challenge when developing a test for SBMs.
We introduce an efficient algorithm to match estimated network parameters, allowing us to properly combine and contrast information within and across samples, leading to a powerful test. We show that the matching algorithm, and the overall test are consistent, under mild conditions on the sparsity of the networks and the sample sizes, and derive a chi-squared asymptotic null distribution for the test.
Through a mixture of theoretical insights and empirical validations, including experiments with both synthetic and real-world data, this study advances robust statistical inference for complex network data.

Network two-sample test for block models
Chung Nguen Oscar Madrid-Padilla Arash A. Amini
Department of Statisties
University of California, Los Angeles
California, CA 90024
{cnguen1, oscar madrid, aaamini)@stat. wcla.ecliee
Abstract
We consider the two-sample testing problem for networks, where the goal is to determine whether sets of networks originated from the stochastic model. Assuming no vertex correspondence and allowing for different numbers of nodes, we address fundamental network testing problem that goes beyond simple adja- cency matrix comparisons. We adopt the stochastic block model (SBM) for network distributions, due to their interpretability and the potential approximate more general models. The lack of meaningful node labels and vertex correspondence translate graph matching challenge when developing a test for SBMs. We introduce an efficient algorithm to match estimated network parameters, allow- ing us to properly combine and contrast information within and across samples, leading to powerful test. We show that the matching algorithm, and the overall test are consistent, under mild conditions on the sparsity of the networks and the sample sizes, and derive chi-squared asymptotic null distribution for the test. Through a mixture of theoretical insights and empirical validations, including experiments with both synthetic and real-world data, this study advances robust statistical inference for complex network data.
Introduction
Network data is pervasive across various fields, including transportation 7 trading
5 social
networks [1] [1], neuroscience [32 31 6 30), ecology [35] and politics 4 among others. To address the diverse needs of these applications, recent statistical methods have emerged handle scenarios where multiple networks are observed [22
19 3]. In this paper, consider the problem of testing whether two sets of networks have been generated from the same probability model. Specifically, in network two-sample testing, we are given two collections of graphs {GI1...,, GIN, and { (G......, G2Nz} generated as Grt ~ F, for r E {1,2), t E [N,] == .N....,,,,, and would like to test
28
Ho Fi F2 against H1 : F2.
(1)
We approach the two-sample testing problem in (1) without requiring the existence of vertex corre- spondence. This means that the nodes in different networks are unlabeled, and as a consequence, the ith node in the /th network of the rth sample has direct correspondence meaning in any of the other networks. Additionally, is possible for the number of nodes, denoted as nyyt. to vary across different networks. As such, the problem immediately reducible to testing the distributions of collection of adjacency matrices.
studying is truly network testing problem, and not
To further elaborate the subtlety of graph versus matrix testing, consider the adjacency matrices Art E {0, 1 1i__.=eX,,,, associated with each graph Gye for E {1,2} and t E [N,], by fixing particular node labeling for each graph. Then, graph-level distribution F, induces distributions the adjacency matrices Aue, E [N1] However, these distributions are not directly comparable since the
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

dimensions of {Aur could be different. Even if the dimensions are the same (i.e., graphs {G1e] all have the same number of nodes), the distributions of {A1.] depend on the particular labelings chosen for each graph. Changing the labelings, will change the distributions of (Ate). although we want to treat all such distributions as the same. In other words, when testing the equality of distributions of the adjacency matrices, the formulation must account for equality up to relabeling of the nodes, and disregard the potential size mismatches, to truly test at the level of graph distributions.
The absence of vertex correspondence introduces a fundamental challenge that elevates this problem beyond simple matrix comparisons, In fact, the unlabeled two-sample testing problem subsumes the classic graph isomorphism problem as a special case. If we consider samples of size N1 NN₂ = 1 where the generating distributions are point masses on two fixed graphs. G1 and G2, the two-sample test reduces to deciding if G₁ is isomorphic to G2. Our problem can thus be seen as a "noisy" or statistical version of graph isomorphism, where we must determine two distributions on graphs are equivalent up to permutation.
To model the distribution of the adjacency matrices, we adopt the stochastic block model (SBM) framework (17] as foundational structure. The SBM is one of the most commonly used models in the literature, valued not only for its simplicity and interpretability but also for its role as universal approximator. It is effectively the network equivalent of histogram [29]; an SBM with a sufficiently large number of communities, K, can form a step-function approximation to an arbitrary graphon in the L sense [4].
This capability positions our method as a "bin-then-test" strategy, which is analogous classic non-parametric approaches like Pearson's 's chi-squared test, where continuous data is binned to form contingency tables. This perspective makes the SBM natural and powerful starting point, providing a flexible, non-parametric framework for the two-sample testing of networks.
In this work, we assume that the adjacency matrices are generated from SBM distributions. In 1 Xrrt is generated as follows. First, we draw a vector particular, an adjacency matrix Arr E (0, 1] Brt of random community labels 2rt = (Zrt1...... Eytn) E [K]" with entries that are independent draws from categorical distribution with parameter क, = ( TrK), ), where मe > 0 for all / and Et= Tel = 1. Here, K is the number of communities. Then, given the labels 2yt, the entries of Art. below the diagonal, are independently drawn as
(Ar))s Zrt Ber((B,) seay):
<<> j.
where B, E [o, 1][X is a symmetric matrix of probabilities. We assume the networks to be undirected, with no self-loops, hence A, is extended to symmetric matrix with zero diagonal entries. Throughout, we write Art ~ SBM,.. (B,, TT)) for A,t generated as described above. We often suppress the dependence on n,r and simply write Art (BM,B,,r T.).
Given A,z ~ SBM Br, Jr), the network testing problem I is equivalent to the following
[ Ho : AP Πk, B1 = PB and H VP e Ik. B, PB or
T1 Pm2
(2)
T PT2
where II is the set of K x K permutation matrices. The inclusion of permutation matrices P in related the subtlety of testing unlabeled network models. The fact that there no pre-defined node label or vertex correspondence across networks leads to the meaninglessness of community labels in SBM. Consequently, demanding that B₁ = B2 under the null hypothesis is not meaningful. Put another way, SBM parameters (B,, m,) are only identifiable up permutation; see (4)
Before proceeding, we generalize the problem slightly. In (2), the null hypothesis is rejected if the class proportions म, differ modulo permutation. Given the SBM labels, this scenario is straightforward test by estimating and sorting class proportions remove permutation ambiguity. To avoid this relatively trivial case, we treat the class proportions as nuisance parameters. This choice also practical, as communities are typically defined by connectivity patterns rather than relative sizes. Additionally, differences in class proportions म, can sometimes be transferred to connectivity matrices B, via community refinement (see Appendix C.I the supplementary material). With these considerations in mind, we focus on the following formulation for the remainder of the paper: Given Art SBM Br, Nyt), we test
Ho: 3P Ik.
B PB,PT
Hy: VP E lk,,
B, + PB.PT.
2

---

Note that here, the class proportions Tye are allowed to vary across networks without violating the null hypothesis.
To develop a test for (3). it is essential to address the significant challenge posed by the fact that matrices B, only identifiable up permutations. A potential approach to constructing test statistic is to estimate the community labels for each network, using any of the many existing approaches (for instance [4)) Subsequently, one can proceed estimate B, by computing block averages of the adjacency matrices, based on these labels. However, the challenge lies in how to effectively combine, and compare, the estimates from different networks when vertex correspondence is not assumed. This becomes particularly daunting, as matching estimated labels across different networks boils down to searching over the space of permutations II,, which has K! elements, non-trivial task even for moderate values of K. It is worth noting that this matching challenge exists even if we observe a single network for each of the two samples, since one has to properly match the communities of the two networks to be able to compare the connectivity matrices B1 and B2.
1.1 Summary of results
In this paper, tackle the core challenges of unlabeled network comparison by developing practical and senreticalll-groundee two-sample test. Our main contributions are:
An Efficient and Consistent Matching Algorithm. We introduce computationally efficient spec- tral matching algorithm solve the fundamental problem of aligning estimated SBM parameters. We prove that this algorithm consistently recovers the correct alignment under standard spectral conditions on the underlying connectivity matrices (formally, the (7, -f-friendly property).
A Rigorous Characterization of the Test Statistic. We establish the key theoretical properties of our test. Under the null hypothesis, we prove that our statistic converges to a X distribution under mild conditions on network sparsity (average degree V/, = S2 nt)) and sample size. This provides a practical foundation for accurate p-value calculation.
Proof of Consistency and Power. Under the alternative hypothesis, show that the test is consistent and powerful. The test statistic grows at a rate of ()(N) demonstrating that its power increases with both the number of networks (N) and their average degree (V₂)).
A Scalable and Empirically Validated Test. We provide a practical, computationally efficient algorithm for the two-sample test, whose scalability stands in contrast to computationally prohibitive methods like subgraph counting. We demonstrate its superior performance and robustness on wide range of synthetic data, real-world networks, and non-SBM models, including graphons and RDPGs.
1.2 Related work
Two-sample testing for labeled networks with known vertex correspondence has been well studied in the literature. Notable efforts in the labeled case include the following: [16], where the authors develop test based the geometric characterization of the space of the graph Laplacians. [15]
consider the problem from a minimax testing perspective, focusing on the theoretical characterization
of the minimax separation with respect to the number of networks and the number of nodes. (25
develop a test based on an omnibus embedding of multiple networks into a single space. 88
develop spectral- apestral-based test statistic that has asymptotic Tracy-Widome law under null. [18
introduce a novel approach to testing degree corrected stochastic block models based on interlacing balance measure.
Existing literature on testing [ with unlabeled networks with no vertex correspondence is limited, but there have been notable efforts. For instance, [22) develop geometric and statistical framework for making inferences about populations of unlabeled networks. [37] introduce a two-sample test for random dot product graphs based on estimating the maximum mean discrepancy between the latent positions. (77 develop a two-sample test, based on subgraph counts, and characterize the null distribution under graphon model. While not designed for testing, two algorithms described in 28 solve a closely related problem of clustering network-value data.
As discussed earlier, the construction of our test relies on the subroutine that matches the estimated connectivity matrices of two networks. This type of problem known as weighted graph matching and can be formulated as quadratic assignment problem (QAP) which is NP-hard. One of the
3

---

standard techniques is to relax the constraint set of permutation matrices to its convex hull 226 39 or the set of orthogonal matrices [13], and then "round" the solution the set permutation matrices. (88 proposes to solve the weighted matching by solving linear assignment problem on matrix derived from eigenvectors of the adjaceney matrices of the two graphs. [12] show exact recovery of
the permutation with high probability for the Gaussian Wigner model. The idea of our main matching algorithm is mentioned in passing in [36 Section 39.4] in the context of testing isomorphism two graphs, and is attributed to (24).
2 Matching Methodology
In this section, we begin by describing the challenges associated with the matching problem, specifi- cally the task of aligning two matrices, B1 and B2, by relabeling the communities. Subsequently, we introduce our proposed matching algorithm, which is at the heart of our test construction.
2.1 Matching challenge
From a statistical perspective, the challenge in testing samples from SBM(B, x) is that the parameters (B, r) are identifiable only up to permutations. That is, for any permutation matrix
SBM(B, x) SBB((BPTT.. PP)
as distributions. To illustrate the challenge more clearly, consider observing the two-sample problem with only two adjacency matrices
A1 ~ SBM(B1.
A2 SBM(B2,
Assume that the null hypothesis holds, where we can assume B2 = B,. To devise a test, a natural first step is to fit an SBM to A,, using any consistent community detection algorithm, to obtain the labels, from which we construct estimate B, B(A,) of B,, for 1,2. The operator B a shorthand for the procedure that produces such estimate, the details of which are discussed in Section Even though B₁ B2, in general, will have
BB ~ P B PT
for some permuation matrix P E IT, since in each case the communities will be estimated in an unknown (arbitrary) order. There is no way a priori to guarantee the same order estimated communities in the cases. This is manifestation of the permutation ambiguity in (4) To simplify future discussions, let us introduce the following notation for exact matching:
B
B2
-
B₂ = P B3 P-T
(5)
The above discussion shows that two-sample testing for SBMs requires solving the following subproblem:
Problem Assume that B1 E B2 for B1, B2 E [0, K The noisy graph isomorphism (or graph matching) problem is to recover matching permutation p* E II between B₁ and B2, using only noisy observations B, B, for 1,2.
As alluded in Section 1.2 this problem is in general hard. particular, finding an optimal matching in Frobenius norm reduces to solving quadratic assignment problem (QAP), which is NP-hard in general.
2.2 Spectral matching
For a large class of weighted networks, we can avoid solving a QAP to recover a matching. The core idea is that if connectivity matrix has unique spectral signature, its eigenvalue decomposition (EVD) contains the information needed to recover any permutation. The following lemma makes this precise.
Lemma 2.1. Consider two K x K symmetric matrices B₁ and B3 with EVDs given by B, = Q, for r = 1, 2. If the eigenvalues of Bi distinct, then permutation matrix p satisfies By P' B, P.T if and only if there exists a diagonal sign matrix S such that:
A2 = A
(6)
Q2 P*
(7)

---

Algorithm Spectral Matching: M( - B₂)
Input: Estimated connectivity matrices B1, B2
Output: Estimated sign matrix S, estimated permutation matrix P for 1,2 do
2: Perform EVD on B, obtain B, = Q,A.
3: end for
4: Recover the diagonal signs S, = ( 1) 1]/ 1|:) and set 3 diag((S)).
5: Recover the permutation matrix as P = LA,(Q
6: return S, P.
This result provides a direct algebraic path to finding P To ensure this process is robust against the noise present in estimates B,, require slightly stronger condition that the eigenvalues not just distinct, but well-separated. This, along with technical condition ensuring that no eigenvector is orthogonal to the all-ones vector, guarantees that the matching permutation Pa unique and that our spectral approach is stable. We formalize these combined requirements as the "(n, O)-friendly" property in Appendix A.I
Our proposed spectral matching algorithm, based on Lemma 2. is outlined in Algorithm | relies on solving the linear assignment problem (LAP), defined for a K K matrix Q as:
LAP(Q) == argmax (r(PQ).
(8)
PEll
The LAP can be solved efficiently, for example, by the Hungarian algorithm
23
The intuition behind Algorithm D follows directly from Lemma 2.1 From 7 we can left-multiply by 1 to get 1dd Q2
P*QIS" Since 1 p 1", this simplifies to Q₂ 2 S' This gives us a way to recover the unknown signs: S = [Q_ 1):/(QTT 1|, The aforementioned condition that eigenvectors are orthogonal the all-ones vector ensures the denominator [Q] 1], non-zero. making this step well-defined For robustness in the noisy case, we only take the sign of this ratio, which is exactly Step of the algorithm.
Once the sign matrix Š S* known, can rearrange 7 isolate the permutation matrix: P = Q2S ST In the noisy setting with estimates Qr, the product Q will be a noisy version of Pt We find the closest valid permutation matrix by projecting it onto the set IT,, which can be done by solving the LAP:
argmin 11 S1 argmax (T = LAP(QISO.)
PеTx
Р
This is precisely Step 4 of the algorithm. In the sequel, we write M( + B2) to denote the permutation matrix P returned.
Remark 2.1 (Computational Complexity). A key advantage of our spectral matching approach is its computational efficiency. The complexity of Algorithm i dominated by the EVD and the LAP solution. The LAP on K K matrix can be solved (K33) time using the Hungarian algorithm. This cost depends only on the number of communities K, not the number of nodes n. In practice, the matching step extremely fast, making our overall test scalable to very large networks.
3
Test construction
We are now ready to describe our main algorithm for constructing an SBM two-sample test. The first step is to estimate the connectivity matrix B for each observed network. Given an adjacency matrix A and a vector of estimated community labels ž E []]" (obtained from an algorithm like
spectral clustering and block-count operator C:
4 Bayesian community detection 35 ), we define the block-sum operator S
[8(A,
Σ =, i,j
(9)
= (z()) 1 = =
(10)
5

---

Algorithm 2 SBM Two-Sample Test (SBM-TS)
Input: Adjacency matrices Art and initial label estimates 2(0) for t [N,] and 1,
Output: Two-sample test statistic T..
Match to the first network within each sample r:
1: for = 2, , .Nr and r 1,2 do
2:
Set ž, = 0rt Eys for independent random permutation dyt-
3:
Set S = =((Art, 2rt) and mit = C(2rt).
4: Set By Sye Ø m,z.
5: Set Prr = MM( + B.)).
6: end for
Find the global matching permutation:
7: Set B, = N. Et= Br. PrT for r = 1,2.
8: Set P MM + BB))
Align the sums and counts, across all samples, form aggregate estimates:
9: Set S, = Σm= PreSrt PiT and mn = Ei Prt myt Prt for r = 1,2.
10: Set 5%2 PS and ml Pmn PT.
SIMe + S2ze and set 02 = BRe(1 - Bee).
11: Let B = (Bxe) where Ber Mike + mizxe
12: Let B(1) S1 2 mi and (22) = S/ @ m²g
(Stronger estimates)
13: Let hike be the harmonic mean of mike and mize and form the test statistic:
Tn Tuge
[B -B
(11)
20
ESF
where (=(2) = Ei= 1(2; k). Both operators produce K K matrix. The estimate of
the connectivity matrix is then B(A, S(A, Ø C(z), where Ø is elementwise division. For diagonal blocks (k &) double-counting occurs in both the numerator and denominator which can be avoided, for computational efficiency, by restricting the sums to <.
3.1 Main algorithm
Our testing procedure, detailed in Algorithm 2 unfolds three main stages. First, enable aggregation, we align all networks within each sample to common reference (c.g. the first network). Second, with the intra-sample alignments complete, we compute an average connectivity matrix for each sample and perform a single global match between the two samples. Finally, with all networks aligned a common orientation, we aggregate the block-level edge counts across networks to form powerful, low-variance estimates of the connectivity matrices and construct the final chi- chi-squared test statistic.
To understand the form of the final statistic, consider an idealized scenario where all matchings perfect and the community labels are known. Under the null hypothesis (B₁ BB B), the aggregate edge counts Syke would follow Binomial distributions, and by the CLT, the estimates B
and ( are approximately independent normal variables: D(r) & N(Br, oeemmRR)) for 1, 2. where of+ (1 B&t) is the common Bernoulli variance and myke are the total block pair counts each sample. The standardized difference of these two estimates is
V (2ee ((2)) N(
where lige is the harmonic mean of mike and mzkee. Squaring this quantity, see that each term in our test statistic (II) is an estimate of this squared standard normal variable. This provides the core intuition why T, will converge to Xk(411//2 distribution, a result formalize in Section

---

Remark 3.1 (Algorithmic Refinements). Two details in Algorithm 2 warrant mention. First, the final constructed by pooling edge counts before dividing. This produces lower-variance estimate than averaging the individual B,t's 's. Second, the randomization of labels in is a technical device to ensure the estimated matchings are statistically independent of the data, which simplifies the theoretical analysis (see Lemma in the appendix).
estimates B (Step 12
4 Theory
In this section, we present the main theoretical guarantees for our proposed test. For clarity and accessibilityy we state our key results-de tte asymptotic null distribution and the consistency of the lest-under simplified set of assumptions. Thesse assumptions presume the use of a community detection algorithm with a near-optimal misclassification rate, which achievable in the sparse regimes we consider (e.g., 42).. This allows us to express the conditions directly in terms of fundamental network parameters like the average expected degree V,. We provide more general, finite-sample versions of these theorems, which hold for any community detection algorithm via its misclassification rate, Appendix
4.1 Matching Consistency
Our test relies on the ability of the spectral matching algorithm to correctly align the estimated SBM parameters. The following result provides an informal guarantee, with the formal statement deferred to Theorem I in the appendix.
Theorem 4.1 (Matching Consistency, Informal), If the underlying connectivity matrices B, have distinet eigenvalues and their eigenvectors are orthogonal the all-ones vector (i.e., they are "friendly" per Definition A.1 in the appendix), our spectral matching algorithm (Algorithm consistently recovers the correct permutation between them from noisy estimates B,, provided the estimation error is sufficiently small.
4.2 Asymptotic Guarantees for the Test
We now present the main results for our two-sample test statistic, T.. We begin with its limiting distribution under the null hypothesis.
Theorem 4.2 (Null Distribution). Assume that Algorithm i applied to two SBM samples with the same connectivity matrix B (v./n) B for fixed K K matrix B Assume that:
(i) B has distinct eigenvalues, and no eigenvector of sums to zero
(ii) The number networks in each sample grows at most polynomially the number of nodes n1, i.e., N max N2) O(n²) for
0.
(iii) The average expected degree grows least logarithmically with the network size, i.e., V, = 2(log n).
Then, the test statistic f, converges in distribution to chi-squared distribution:
T, X
Next, show that the test is consistent under the alternative hypothesis, meaning its power ap- proaches one as the network size grows.
Theorem 4.3 (Consistency). Assume that Algorithm 2 is applied to two SBM samples with different connectivity matrices B, (vr/n) for 1, 2, such that 3 is not permutation of B3. Under the same conditions on the cigenvalues/eigenveete and assuming the average expected degree in + the test is consistent. Specifically, with probability approaching I,
B and the growth of N, as Theorem 4.2
T, 2NN
where N max (Ni, N2). This ensures that for any fixed significance level, the power of the test approaches +
7

---

Remark 4.4 (On the Sparsity Condition). One might intuitively expect that aggregating N networks could weaken the sparsity requirement of vn, n)) However, this fundamental dependence on log n persists even for large N. To see why, consider sample of N networks of size n. This can be viewed as single, large, block-diagonal adjacency matrix of size n.N x nN,, where the off-diagonal blocks corresponding to inter-network connections are unobserved. For a single, fully observed network of size n., established results for tasks like community detection require the average degree to scale as ([log(n (nN) O(log + log N). Since our problem has less information (due to the missing off-diagonal blocks), the requirement on the log n term cannot be removed by increasing N.
Remark 4.5 (Practicality of the Sparsity Condition). It is important to note that the condition P/ 2lolg n)) still describes very sparse graph regime. For instance, if the average degree grows as log n. adding one million nodes to a network would only increase the average degree by approximately log(10%)
14. As demonstrate empirically in Appendix C.2 the average degree in many real-world networks grows even faster than logarithmically with network size, suggesting this assumption is mild in practice.
Experimental results
In this section, we provide experimental results on real and simulated networks and compare our proposed test two existing approaches. The code for reproducing all experiments in this section is publicly available at hattps://githin com/ aaaaaai/mbmmm-mmaaaaaaaaaaaaa
5.1 On Model Misspecification and the Choice of K
A key motivation for our SBM-based test is its applicability beyond the strict SBM setting. Because SBMs can approximate general smooth graphons with arbitrary precision by increasing the number of communities K, our test provides a robust method for non- non-parametric network comparison. Our experiments on data from graphon and RDPG models (Subscctions 5.. and (5.4 provide strong empirical evidence for this robustness.
Theoretical Guidance on the Range of K for Graphons. While full theoretical analysis under a general graphon model is beyond our scope, we can construct a semi-rigorous argument by combining our test statistic's structure with recent oracle inequalities for graphon estimation (21]. This analysis, detailed in Appendix CC3] shows that the power of the test depends on balancing three competing factors: (i) the model approximation eтror (bias), which decreases as K grows; (ii) two sources of
statistical estimation error (variance), which increase with K. For the test be consistent, all three error terms must vanish relative to the signal strength. This leads to a sufficient set of conditions on the growth K: K 00, while K2 =²=o(nw,)) and log K = o(vx)-
These conditions provide valuable theoretical guidance: K should grow with the network size to ensure the SBM a good approximation, but this growth is limited by the network's 's size and sparsity. This leaves wide and practical range for choosing K.
Practical Selection of K. In practice, where the optimal K is unknown, we propose data-driven procedure akin parametric bootstrap to select value that maximizes test power for given problem scale:
(i) For a candidate Ko (e.g., Ko 10), fit Ko-SBM to one sample, yielding estimates (B, R).
(ii) Create a synthetic alternative by perturbing the estimate: Bat: B Noise.
(iii) For a range of values K e [2, Kmxx), generate many synthetic datasets under Ho (B, B) and H₁ : (B, Bate).
(iv) For each K, calculate the Area Under the ROC Curve (AUC) of our test in distinguishing these synthetic samples.
Select the K that yields the highest AUC.
In our experiments, this procedure proved effective. For instance, in the graphon experiment of Section 5.5 correctly suggested small value of K = 2.
8

---

Table 1: Mean AUC-ROC for various methods for the general SBM experiment.
K
2
3
15
20
SBM-TS
0.95
0.91
0.83
0.81
ASE
0.62
0.54
0.49
0.48
NCLM
0.70
0.64
0.50
0.50
5.2
Competing methods
We benchmark our method by comparing it against the two test from the literature: (1) Network
Clustering based on Log Moments (NCLM) (28] and (2) the Maximum Mean Discrepancy of the Adjacency Spectral Embeddings (ASE-MMD) 37 Whilst these two methods were not originally designed for two-sample testing (NCLM is clustering algorithm for networks and ASE-MMD is designed for sample size 1), there is natural way extend them into this setting. See section D.1 of supplementary material for a more detailed discussion.
5.3 General SBM with random B
We generate 50 instances of the testing problem Bi B2 = pB(() versus (Bi, B2) = (pB(), pB where (+) is symmetric matrix whose entries are drawn from U(0.2, 0.7) and B.") = B(() + M
such that M has entries (O, e²) subject to symmetry. We set the sample sizes to N, = 100, the number of vertices to nht = 10000, the noise level to E = 0.05, and sparsity factor to 0.1.
From Table 1 can that SBM-TS exhibits superior performance over the competitors, but its performance somewhat deteriorates as K increases. The primary reason is that significantly increasing K makes it more challenging satisfy the approximate matching condition (14p. Nonetheless, the median area under the ROC curve (AUC) for K {15, 20} } is 0.89 and 0.87 respectively, which shows the strong performance of our proposed test the cases where (14) holds.
5.4 Random dot product graphs
We consider two experiments around the two sample testing problem
Ho : A, A' ~ RDPG, (F, against
H1 A ~ RDPG, (F, p), A' ~ RDPG,, (F',
We set the number of vertices to n 10000 and the sparsity parameter = 0.15. For Experiment 1,
we take F F1 = N(0, Σ) and F' (o, I2) where
3 For Experiment 2, F2 =
OΣOT) while = (0, I2) as in Experiment 1. Here, F2 mixture of two Gaussian distributions and O = (-) ()) Due to the invariance of the RDPG to an orthogonal transformation, the two experiments equivalent.
NO, Σ)
Figure Ic summarizes the results, comparing the performance of SBM-TS to ASE-MMD. While SBM-TS essentially exhibits the ROC of the perfect test, ASE-MMD shows poor performance. The reason is that, as proposed in 377. ASE-MMD does not have a matching mechanism to account for the potential orthogonal transformation mismatch between the estimated latent positions for A and A' under null. This defect is present in the original paper (37] as can be seen from the presence the orthogonal matrix W. nm in the asymptotic null limit of the statistic in Theorem 5 of (37).
5.5 Graphon
Consider the two-sample testing problem
Ho : A, A' ~ Graphon(pW)). against
H1 : A Graphon(pWW) A' Graphon(p
where p is sparsity factor. We take ( 02) [ (uf + vg + von U the graphon from (2] and let Wa, be the following perturbation of W.
Wa,l v2) = W 0.) + 1f fu, [0.5 0,5. 8

---

In this experiment, we let E 0.05, 6 = 0.2. For general graphon, spectral clustering does not provide good SBM fit. To fit proper K-SBM, we use Bayesian community detection algorithm R5) The algorithm of Section 5.1 suggests K = 2 as the optimal choice and we set d = K for ASE-MMD. Figure If ifllustrates the resulting ROCs for two cases of (n, p), namely, (10 0.5) and (10*, 0.05), showing a clear advantage for SBM-TS against the ASE-MMD.
E..
F
(a) F1
(b) F2
(d) 1000, p 0.5
(c) n 10000, p 0.05
(c) RDPG experiments
(f) Graphon experiments
Figure I: ROC curves for the RDPG and Graphon experiments
5.6 COLLAB dataset
The COLLAB dataset is scientific collaboration dataset first introduced in [40]. This dataset contains 5000 networks derived from public collaboration data in three scientific fields: C1) High energy Physics, C2) Condensed Matter Physics, and C3) Astrophysics. Each graph corresponds to ego-network of a researcher and is labeled by their primary field of research. We consider two-sample testing problems of the form (T with N1 = N2 = m; the two samples under null will be drawn at random (without replacement) both from class C,, and under the alternative from classes C, and C; for + j. Two choices of m {5, 10} and several choices of (i, j) are considered, as detained in Figure where the resulting ROCs are plotted. One observes that SBM-TS has superior or comparable performance to the competing methods in distinguishing the two classes in each case.
Discussion
We have introduced practical and theoretically grouunde framework for the two-sample testing of unlabeled networks, addressing the core challenge of permutation invariance with a scalable spectral matching algorithm.
Our approach inherently modular, separating the problem into matching stage and a testing stage. This structure opens several avenues for future work. For instance, while our current method solves the matching problem in two sequential steps, one could explore alternative optimization strategies, such alternating minimization the most informative eigenvectors instead of full matrices are another option.
permutations and signs. Low-rank approaches that match only
The choice of the stochastic block model was motivated by its ability to approximate more general network models. Our experiments successfully demonstrated that our test a robust and practical option for non-SBMs, such as those from graphon distributions. A key theoretical next step is to extend our analysis provide formal guarantees for the test under this broader class of models, solidifying the connection between SBM-based testing and nonpparametric network analysis.
-.0
(a) m 5, Cl vs. C3.
(b) m = 5, C2 vs C3.
(c) m
10, CI vs C3.
(d) m = 10, C2 vs C3.
Figure 2: ROC curves for the COLLAB dataset.
10

---

Acknowledgments
This material is based upon work supported by the National Science Foundation under Award No. 1945667.
References
[1] Y. Aflalo, A. Bronstein, and R. Kimmel. On convex relaxation of graph isomorphism. Pro-
ceedings of the National Academy of Sciences, 12(110):942222413) 2015. doi: 10. 1073paass 1401651112. URL/https //ww www..ppaa..... www./org///ooooooooooooooooooott htt:/dii/abbat aat//0.s//////00/ 10w3/007....... 10111/00000////.....11111111 1401651112
[2] E. M. Airoldi, T. B. Costa, and H. Chan. Stochastic blockmodel approximation of a graphon: Theory and consistent estimation. Advances in Neural Information Processing Systems, 26, 2013.
[3] A. Amini, M. Paez, and L. Lin. Hierarchical stochastic block model for community detection in multiplex networks. Bayesian Analysis, 19(1):319-3435 2024.
[4] A. A. Amini, Chen, Bickel, and E. Levina. -ieudo- methods for community detection in large sparse networks. Annals of Statistics, pages 1-27, 2013.
[5] M. Barigozzi, G. Fagiolo, and D. Garlaschelli. Multinetwork of international trade: A commodiy-speciffe analysis. Physical Review E, 814)):44114 2010.
[6] U. Braun, A. Harneit, G. Pergola, T. Menara, A. Schäfer, R. F. Betzel, 7. Zang, J. I. Schweiger,
X. Zhang, Schwarz, et al. Brain network dynamics during working memory are modulated
by dopamine and diminished in schizophrenia. Nature communications, 12(1):3478, 2021.
[7] A. Cardillo, J. GardzeGs, M. Zanin, M. Romance, D. Papo, F. d. Pozo, and S. Boccaletti. Emergence of network features from multiplexity. Scientific reports, 3(1):1344, 2013.
[8] I.. Chen, N. Josephs, I.. Lin, J. Zhou, and E. D. Kolaczyk. A spectral-based framework for hypothesis testing populations of networks, 2020.
[9] I.. Chen, J. Zhou, and I.. Lin. Hypothesis testing for populations of networks, 2021.
[10] L. H. Y. Chen, L. Goldstein, and Q.-.. Shao. Normal Approximation by Stein's 's Method. URL htttps://openiibraary wwwppppewwwaaaarrrrrrrrrroooeo org/books/ Ba0e://4M//oraaaama Normal http://oooaaaaaaaaaa0ae App.omaanoppooooitiooooo..o ba_nt____S_iit___ s_ Method
Springer, 2010. ISBN 9783642150074 0L37140834M/
[1]] N. Eagle and A. Pentland. Reality mining: sensing complex social systems. Personal and ubiquitous computing, 10:255-268. 2006.
[12] Z. Fan, C. Mao, Y. Wu, and J. Xu. Spectral graph matching and regularized quadratic relaxations: Algorithm and theory. In H. D. and A. Singh, editors, Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 2985-2995. PMLR, 13-18 Jul 2020. hatttps://ppoceedinggg mlr press/v119/ fan20a html
[13] S. Feizi, G. Quon, M. Recamonde-Mendoza, M. Médard, M. Kellis, and A. Jadbabaic. Spectral alignment of graphs. IEEE Transactions on Network Science and Engineering, 7(3):1182-119)
2020. doi: 10. (19/TNSE.20199299333
[14] C. Gao, Y. Lu, and H. H. Zhou. Rate-optimal graphon estimation. Annals of Statistics, 43(6): 2624 2244-2652,20 2015.
[15) D. Ghoshdastidar, M. Gutzeit, A. Carpentier, and U. von Luxburg. Two-sample hypothesis testing for inhomogenous random graphs. Annals of Statistics, 48(4):2208-22) 2229, 2020.
[16] C. E. Ginestet, Li, P. Balachandran, S. Rosenherg, and E. D. Kolaczyk. Hypothesis testing for network data in functional neuroimaging. Annals of Applied Statistics, 11(2):725 - 750, 2017. doi: 6-44//16AA0 6-0AA11055 URL https: http://di..rr/////
[17] P. W. Holland, K. B. Laskey, and S. Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109-133 1983.
[18] J. Jin, 7. T. Ke, S. Luo, and Y. Ma. Optimal network pairwise comparison. Journal of the 2025.
American Statistical Association,
[19] N. Josephs, A. A. Amini, M. Paez, and I.. Lin. Nested stochastic block model for simultaneously clustering networks and nodes. arXiv preprint arXiv:2307.09220. 2023.

---

[20] R. W. Keener. Theoretical Statistics: Topics for a Core Course. Springer Texts in Statistics. Springer, New York, 2010. ISBN 9780387938387.
[21] O. Klopp, A. B. Tsybakov, and N. Verzelen. Oracle inequalities for network models and sparse graphon estimation. The Annals of Statistics, 45(1):316 -354, 2017. doi: 10.1214/16-ASS14 lnttps/////doi org///g/// 10. 1211/111100114400
[22] E. Kolaczyk, L. Lin, S. Rosenberg. J. Xu, and J. Walters. Averages of unlabeled networks: Geometric characterization and asymptotic behavior, 2019.
[23] H. W. Kuhn. The Hungarian Method for the Assignment Problem. Naval Research Logistics Quarterly, 2(1-2):83 97, March 1955, doi: 10.
[24] T. Leighton and G. I. Miller. Certificates for graphs with distinct eigen values. Orginal Manuscript, 1979.
[25] K. Levin, A. Athreya, M. Tang, V. Lyzinski, Y. Park, and C. E. Priehe. central limit theorem for an omnibus embedding of multiple random graphs and implications for multiscale network inference. arXiv preprint arXiv: 7777005035555 2017.
[26] V. Lyzinski, D. E. Fishkind, M. Fiori, J. T. Vogelstein, C. E. Priebe, and G. Sapiro. Graph matching: Relax at your own risk. IEEE Transactions on Pattern Analysis and Machine Intelligence,388l 38(1))60-73, 2016. doi: 10. 10.110/TPAM1200152444444
[27] P.-A. G. Maugis, S. C. Olhede, C. E. Priebe, and J. Wolfe. Testing for equivalence of network distribution using subgraph counts. Journal of Computtaionall and Graphical Statistics, 29 (3):455 apr 2020. doi: 10. 1080/10618600.000 20..20000....08.....11
1080/2F10618600 2020 1736085
[28] S. S. Mukherjee, P. Sarkar, and L. Lin. On clustering network-valued data. Advances in Neural Information Processing Systems, 30, 2017.
[29] S. C. Olhede and P. J. Wolfe. Network histograms and universality of blockmodel approximation. Proceedings of the National Academy of Sciences, 1 (1(41):14722-147: 2014.
[30] O. H. M. Padilla, Y. Yu, and C. E. Pricbe. Change point localization in dependent dynamic nonparametric random dot product graphs. Journal of Machine Learning Research, 23(1): 10661-10719, 2022.
[31] Y. Park, H. Wang. T. Nöbauer, A. Vaziri, and C. E. Priebe. Anomaly detection on whole-brain functional imaging of neuronal activity using graph scan statistics. Neuron, 2(3,000):4-000, 2015.
[32] R. Prevedel, Y.-G. Yoon, M. Hoffmann, N. Pak, G. Wetzstein, S. Kato, T. Schrödel, R. Raskar, M. Zimmer, E. S. Boyden, et al. Simultaneous whole-animal 3d imaging of neuronal activity using light-field microscopy. Nature methods, 11(7):727-730, 2014.
[33] N. Ross. Fundamentals of Stein's method. Probability Surveys, 8(none):210 293, 2011. doi: 10.1214/11-PS188. uttpttss: org/ 10. 1214111111111
[34] D. Schoch. networkdata: Repository of Network Datasets (v0.1.14), 2022. URL https
//doi.org/// 00l.002211222ooooo 7189928
[35] L. Shen, A. Amini, N. Josephs, and L. Lin. Bayesian community detection for networks with covariates. arXiv preprint arXiv:2203.02000 2022.
[36] D. Spielman. Spectral and Algebraic Gruph Theory. 2019.
[37] M. Tang, D. Sussman, V. Lyzinski. and C. Priebe. A nonparametric two-sample hypothesis testing problem for random graphs. Bernoulli Journal, 23(3):1599-1630, 2017.
[38] S. Umeyama. An eigendecomposition approach weighted graph matching problems. IEEE Transactions on Pattern Analysis and Machine Intelligence, 10(5):695 703, 1988. doi: 10. 10.1 34.6778.
[39] T. Vogelstein, M. Conroy, V. Lyzinski, J. Podrazik, G. Kratzer, E. T. Harley, D. Fishkind, R. J. Vogelstein, and C. E. Priebe. Fast approximate quadratic programming for graph matching. PLOS ONE, 10(4):1-17, 04 2015. doi: 10. w 0120000 URI. https: //doi. org/10. 1371/journal. pone. 0121002
12

---

[40] P. Yanardag and S. Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '15. page 1365-1374, New York, NY. USA, 2015. Association for Computing Machinery. ISBN 9781450336642. doi: 10.145/2783258.28844477
URL htttps://doi.org/uue
2783258 2763258.2783417
[41] Y. Yu, O. H. M. Padilla, D. Wang, and A. Rinaldo. Optimal network online change point localisation. arXiv preprint arXiv:2101.05477 2021.
[42] A. Y. Zhang and H. H. Zhou. Minimax rates of community detection in stochastic block models. The Annals of Statistics, 4465)2225--2280, 2016.
A Full Theoretical Statements
This section provides the formal definitions and the complete versions of the theoretical results presented in Section 4 We follow top-down approach, beginning with the general theorems expressed via the misclassification rate (Tier 2), then presenting the full sinite-sample bounds from which they are derived (Tier 3), and finally providing the complete proofs.
A.1 Formal Definition and Matching Guarantee
We begin with the formal definition of an (17, 0)-rriendly matrix, which is key condition for our spectral matching algorithm.
Definition A.1 (17,, f)-friendly). Let B E [0, 1K be symmetric matrix with eigenvalue decom-
position B =- Augugg We call B (1), O0-friedllyyy if:
min ISKHiSK
DAe
del > 77
(Eigenvalue Separation)
(12)
min kE[K]
9 1 >
(Eigenvector Condition)
(13)
We consider connectivity matrices B, and B3 that are (0, (0, -))ffiendly. Recall our shorthand notation for an exact matching, introduced in (47). Similarly, it is helpful to introduce the following graphical mnemonic for approximate matching:
B
L
B2
=
| - PB, |F S
(14)
2/2K
Then, we have following guarantee for the matching algorithm:
Theorem A.1 (Matching Consistency). Suppose that B₁ and Bg are x connectivity matrices that are (8, f)-frriedlly with 0 < AVK' and with EVDs given by B, Q,AQ,, 1, 2. Moreover,
assume B1 _ B2 for some permutation matrix p For 1, let B, be estimate of B, satisfying
B, Lig B,
(15)
for permutation matrices P,. Let Q2, Q2, S and P be as defined in Algorithm 1 and let
S, argmin |Q, Pl r= se**
(16)
where VK is the set of K x K diagonal sign matrices. Then, the following holds:
(a) Sign recovery: S š = S,S* S, with S* as in Lemma 2.1
(b) Permutation recovery: LAP(Q, = [P} where := P. P*P, and
- PT PT | S Σ BB - P.B.
(17)
Remark A.2. One can also ask whether our matching algorithm is self-consistent? That is, if we reverse the order of the B, and B2, do get permutations that transposes of each other? The
13

---

B
Pi > B1
P
pr
B2 -
B2
P2
Figure 3: Schematic diagram of permutation recovery in Theorem A.1
The solid and dashed straight arrows correspond to exact and approximate match. The bent arrow represents an application of the matching algorithm M.
answer is yes. Notice that if reverse the order of B1 and B2, the sign matrix $ does not change. Moreover,
B1 - B2 implics Bg (P")
BT. Hence, LAP(Q25Q]) = { where P P2=
Intuituon behind Theorem A.1 To gain a deeper understanding of why our target permutation matrix P. P Pt, let analyze Figure Within this illustration, each edge symbolizes matching between matrices based on both the direction of the edge and the permutation matrix associated with it. To clarify the nature of these matchings,
different types of arrows:
1. Dashed straight arrows represent approximate matching. For instance, the top edge corre- sponds to B₁ _ B1, following the notation from Equation 14)
2. In contrast, the solid straight solid arrow signifies exact matching corresponding to B P' B2, with the notation from
Considering that the inverse of permutation matrix is its transpose, we can trace the path from B to B2 in Figure 3 We start from B1, progress through B1, then B2, and finally arrive at B2. The permutation matrices associated with this path are P1, P and P3 (the inverse of P2). By multiplying these matrices together, obtain the desired permutation matrix, which is P. p*Pt
A.2 General Results via Misclassification Rate (Tier 2)
The simplified theorems in the main paper (Theorems and are direct consequences of the more general results presented here. These theorems are applicable to any community detection algorithm, with their conditions expressed in terms of the algorithm's 's misclassiffcation rate, غ max,, Mis( 2,1). In what follows, N Na))
Theorem A.3 (Null Distribution, Tier 2). Assume Algorithm 2 is applied to two SBM samples generated from B (va/n) 3 for fixed 8 The null distribution T, + Xk( holds if:
(i) Bd has distinct eigenvalues and no eigenvector of it sums to zero.
iii) The number of networks grows at most polynomially: N o(n²) for some 0.
(iii) The misclassification rate satisfies both:
Vunl E (p))
E C. 3/22 for some constant C = C(B)).
Theorem A.4 (Consistency, Tier 2). Assume Algorithm 2 is applied to two SBM samples from B (u,/n)BB and Bg = (2x/n)BB. The test is consistent, with f, {(Nv2), if:
(i Bf and PT.PTT different for any permutation matrix P.
14

---

iii The misclassification rate satisfies both:
= op),
E CK- for some constant C- C(B). ([B...B) B.).
Remark A.5 (Connecting Tiers). The Tier results the main paper follow from the theorems above. Near-optimal community detection algorithms [42 can achieve غ = O exp(-cv,/ K)) Taking Vn = C log n for a sufficiently large C, this rate is small enough to satisfy all conditions on in Theorems A.3 and for sufficiently large (assuming K is fixed). Note that in the main paper, we stated = (n²) while here N = o(n²), noting that the former implics the latter by taking say a/2 for any O. The next section details how these Tier 2 conditions are, in turn, derived from our full finite-sample analysis.
A.3 Complete Finite-Sample Bounds (Tier 3)
The Tier 2 results presented above are convenient simplifications of our full, non-asymptotic technical bounds (Tier 3). We state these full bounds below and explain how the Tier conditions arise from them.
We make the following "sparsity" and "size" assumptions
Vn - Bug 5 C1
(18)
n S Net S C2n
(19)
for all k, f [K] and [Nrl.r 1,2. We also write Ty. P(rrtt = k). recalling that we are under the null, and set Tiin ming Tk.
Let us fix some K. E (0, 1) and and let 1/
1/(TTmmn)) where x 1 K.. For any N, let
a log
8(N)
(20)
Nnv,
For convenience, we assume that (n is large enough so that)
log n
K² Miin
8(1) $ 1
(21)
3a
Moreover, define
Yn (36338 - o(()) where E:= max Mis(2rt; 2xt). te [N.]
1,2
Theorem A.6 (Null distribution, Tier 3). Fix K and assume that Algorithm 2 is applied to two SBM samples, with sizes satisfying (19). and the same connectivity matrix satisfying (18) and
[B] max 0.99. Moreover, suppose that B is (17 0) friendly and with probability o(1),
Vn
In S min e
1
n
(22)
n
5VK
2V2K
Let N max NN, N and assume that for some & E (0, 1) and a > 0 and e > 0, we have
(1), VNV,nē (p()), Nu. + c0, N = o(n²),
and min(N1, N2} 2 cN. Then, for T., the output of Algorithm we have
t, XK(K413/2
Derivation of Tier from Tier 3 (Null): The conditions in Theorem A.3 ensure that the premises
of Theorem A.6 hold. Specifically, since we always have 5(1) = o(1), the condition Yn = o, (1) is satisfied if E = (1). Assuming B (vw/n) BB and Bo has distinct eigenvalues, with no eigenvector that orthogonal the all-ones vector, B will be ((2, /n) mo. ffr-frie for some constants 8 > 0 and n/u > 0. As result condition 22 holds if The I min(fo, 5/R
1 7p
2/2K'
15

---

and since Yhu x E, the condition holds if v K K-3/ The condition Vu . = (1)) slightly stronger restatement of the vN = (p(1) requirement, using N = o(n"), ). Condition Nu, - oo trivially holds given Vn = 22loog n).
(1) is
Next, we show that the test is consistent, the sense that Tr -> oc under the alternative hypothesis that the two SBMs are different. For two K K matrices B1, B2, consider the pseudometric
dF (Br, B2) min |B2 PB, Le,
(23)
PEllx
where K is the set of K x K permutation matrices.
Theorem A.7 (Consistency, Tier 3). Assume that Algorithm 2 applied to two SBM samples, with sizes satisfying (9)., and connectivity matrices B1 and B2 satisfying (18.. For 1, let
&. = C1 (40,3 (N
and assume that
d (B1, B2)
12K max & S r=1.2
(24)
Vn/n
Moreover, let let 9 be the event that the same constants in (18). Then, with probability at least 19N K2 P(G)),
22 holds. and assume that 4 < 1. Here, C1 and C2 are
2n 12,32
Tn
dF B2)
Derivation of Tier 2 from Tier 3 (Consistency)): The premise of Theorem A.7 is dominated by the misclassification rate through the term ε,. we assume Op (1) as in Theorem A.4 then &, Since d B2)/ (nn/n) d B1, BB) 0 is a constant under the alternative, the condition
holds for large guaranteeing consistency. It follows that F,
Nv du By) ((N2)).
B Proofs of the main results
B.1
Notation
We often consider one-to-one correspondence between permutations matrices P RR K and permutations σ on the set [K] == {1...., K}. The correspondence a ト Po is defined by the following identity: (Pau); = (o(() for all e E R follows that (PTT),, v); = 00-1(()- It also helpful to note that [Pali- = (0 and [P. = [Pa]]. = Co(j)- This implies that B is K K matrix, [PBPP]]
Bo()) The linear assignment problem is often written as max, Σ Bio(()- The cost function in this case is equivalent to tr(PPT). This follows by noting [BP.] lij Bi, Ca(s) = B),
Let P and Q be matrices with associated permutations a and 7 respectively. Notice that a o r the permutation associated with QP, since (QPv): (Pv)r() vo(r())))
For p E [1, 00) and a n x m matrix A, the l, + lp operator norm of a matrix A = (atz) ) is |||| == sup foll |r ||=|pp- In the special cases p 0o, we have |A] max, E, (ii and |||]|o = max, Σ, lasyl. We also write || max;,j AAiy-
[K]", we write d=(2,3) Σd 1(2, # 2,} for their Hamming dis- tance, dNH(2, 8) = d=(2, /)/n for their the normalized Hamming distance, and Mis(2, 8) = milloely (2 2 σ) for the corresponding misclassification rate.
For label vectors 2,
B.2 Proof of Theorem A.I (Matching Consistency)
Recall that |A] = max,y Ayyl We need the following lemma on the perturbation of the LAP problem:
Lemma B.1. We have LAP(I + A) {1} as long || 1/2.
16

---

Since B1 and B2 are similar matrices, they have the same eigenvalues. If the EVD of B1 is B QiAQI then the EVD of B2 can written as B2 Q2AQ² By Lemma 2.1
Q==
(25)
for some sign matrix S
First, we show assertion (a). Let A, = P,Q,S, - Qr, so that 2r = P. + -r) and
1 =- S, + (
using P,1 Then, (º_ 1]x = (Q, + TT. where Qreck and D are the k-th columns of Q, and A,. From the definition of SER.
1 1k sign Q A. 02 + +2
S& sign
SI,ARS2AR
(26)
[22 1]k
From 25 follows that Ske = sign (00g((1011 1]/101/
Then, to show SuA Sh
suffices to show that
K rk = 1
1Q = Σ Orik
(27)
for r = 1,2. Since B, are (0, n))-fiiendly we have Σø= Qrial 2 0 and so it is enough to show that Σ5= Ár.Nl $ | < 0.
The noise matrices Å, controlled by the Davis- theorem,
A = 11Qr,nk Pr
2
<
BB, - P.B.P.P P, ||F.
1
Then, using assumption (15
2V2K On S 0,
| S VKIJ 2212 S
(28)
2 /2
proving assertion (a). Note also that have shown
| 111 max
A *k || S 8.
(29)
Next, we prove LAP(), = (P). Using 25 and the definitions of A,, we have
Q2 P3 (Q2 + S2)
(P' + +2)
(P Å,SS + Σ2)S
= =P.TP'PQ - - P' S, + P.T SnS,
-QQŠ +A
where we let A = P2 P. 3,5* S2 + PTT SzS2. We can then write
Q,
(30)
where 4. = PQ, It then enough to study
LAP(PT(I (I+ Ao)) = LAP(I + +a)
where the equality follows by change-of- variialle argument. The result follows from Lemma B. show ||Aollo x 1/2.
17

---

We note that for permutation and sign matrices, both || loc and |la are equal to 1. Using the submultiplicative property of pp for p 1, 2, we have
|x ||||| < | + | < 20
where we have used 229 Then,
| 2 1Q1111=011 A
/ 11 S 20 21
Since @ has unit-norm rows, that is, 1|Q1, = for all k we obtain
1/ t max S VK.
Putting the pieces together
A & 11 s 20VK < <1/2
where the last inequality is by assumption. This proves T.AP(Q = (P).
To prove the inequality part (b), let D, == B, P.B.P.T. Pt B, p-T gives
Then, some algebra, using B₂
PB, PT P' PTT
- DP) Ps2
=P:P"B,P''P, Pg P pr Dj PtT
-2P Pp P2
=2T + B2 - P. p* D p P2.
and
[PB - B2IF < IP DzP2 P2 pr PT Dj P PalF S D F + D2]|F
The proof is complete.
B.3 Proof of Theorem A.6 (Null distribution, Tier 3)
B (17, -f-ieeddlly, then it is (n, Offrrnndly with min (VR) ). For simplicity, let us
redefine be 8', that B is (1760) f)-friendly with 4VK" Let D be the event that (22) holds. After redefinition, ' is equivalent to
Un On
mn <
(31)
n
2/2K"
and by assumption, have P(D) 1 o(1) Let B be some (a priori) fixed version of the connectivity matrix for each of the two groups = 1,2. By Proposition F.3 and the union bound, there is event A with
P(A) S 3N, K KN_ x² nmm
and permutation matrices P., ITx such that on A DD:
On 2/2K
P..PB..PPPT llll I C1 5633 E,t + 8(2)
In <
for all t E [N,] and r 1,2, where ē.. = Mis(zre, Zrc). This implies that
AnD & (Bre Pu,, B for all t I,..., Nr, 1,2
According to Lemma E.3 assume that, in the above, Pro is independent of everything else.
18

---

B
P
IK
B₂1
P
Dr
Br1
Pr1
Br
Br1
Tx -_---- B,
Pre
IK
Prt
IK
Prt
Ik
Brt
> B
Byt
B
Brt
B,
Prt
Prt
Prt
(a) Step
(b) Simplification by introducing B, (c) After conditioning Br
Figure 4: Matching to network in group r. Here, > the bottom level. Bent arrow is an application of the matching algorithm MM. The edges can be reversed in which case the permutation matrix should be replaced with its transpose. Left-side quantities are random, while right-side quantities are deterministic. Dashed and solid arrows correspond approximate and exact matching, respectively. See the discussion at the end of Section for more details on the nature these diagrams.
Figure illustrates the "matching- torccinngttt-ist"" step St the algorithm. As this diagram shows, by Theorem A.1 on event &g, we have P.T = P.T Ix Pri that is,
Eg C 3
PPr. P.T....
To simplify, let us define B, = PT Br P. Pri, that is, r1
FT. B,
B
Note that B, random version of the true B,, due to the randomness of Pri, although, it is independent of everything else. Then, little algebra shows that on & O E22,
Br, Pass Br
for all t E [Nr] and r 1. Figure 4b illustrates the above inequality (the red path). Now, since B,, 1,2 independent of everything else, argument as if they were deterministic. The resulting diagram is shown in Figure 4e the effect is as we assumed Pri I and B, B The above conditioning argument shows that we can do this without loss of generality.
condition them and continue with the
From now on, we work on (AnD) NE = AnD (by the above argument), on which we have Pr. = Prt as discussed above. Then, from the definition of B, in step we note
B, N Σ Pr B.).
On Eg the - || of each term on the RHS is bounded by 0n/(2v2K) and since a norm a convex function, the same holds for the LHS. That is,
B, 1x B
(32)
for = 1,2. Since we are under the null, there is permutation P such that Bg - By Combining with 32)
p
Theoreh A.I with Pt P2 = IK and the roles of B1 and Bg switched
conclude that P = pa in step
Remark B.I. We could have assumed B3 B5 in the above argument, since we are under the null. However, when passing B,, 1,2 could lose the equality among B, and B., (due to Pri, = 1,2 potentially being different). Hence, we not gain anything by making the assumption B = B3.
19

---

Remark B.2. Everything to and including (32 holds under the alternative B₁ # B2 as well. This will be used in the proof of Theorem A.7
The following arguments all on A. Let Stt S(Are, 2re), mptt C(Art, 2re) and
Sr S E1 Sre
B
mr == Ere mre
m,
Since Pre Pre, we have
E, PriSePT PT My E, Premir PT
S,
where S, and mn are as defined step 9 Let N max N1, N2). Then, from Proposition F.4 and union bound on r = 1,2, 2, there is an event B1 with
P(B)) S 2(C2N 2K") 2N x² n3min/3
(33)
such that on B1, we have
fm, Brllmax I 40 103 kag
(34)
n1
where ē = max,, Ert. Also, since 5 = Ps, we have 8 pt PrT and mlg Moreover, from Proposition F.4 on B1,
P pm P+T
[B, Br max S Ci Un g(N S Ci Un
(35)
n
n
since (N.)) < 50 < 1. Using || |max S Civa/ / and triangle inequality, we have
S Va
|
Ilmax
Un
(36)
where we have treated C1, C2 and 8 constants and absorbed them into S symbol; this will do from time to time in the rest of the proof.
Next, we have || P.im,e PT Imax S n, Ert. It follows that
|m m S 6,3 Σ n n Ere S 6C,
(37)
where m, = Ee Mys. Let ml = Pm Then, the same bound as above holds for ||mL mbllmax- Let h be the elementwise harmonic mean of my and m/- Since hn is the elementwise harmonic mean of f and míz we have
Fmlmaxx S 12C,52Nn'
(38)
where N [,, N2). Since is elementwise the harmonic mean of my, 1,2, we have
min hae 2 min [mr]ke 2 cNNn//(233 k.E
(39)
k.e.r
The factor 2 is for handling the case ==6 l. Controlling Note that
3 + PM S2
Since B1 P*B,P=T, this essentially an estimator like B in Proposition F44 based on an
independent sample of size No. ;= Ni N2 from SBM(BI, r). It follows from Proposition that there is an event B3 with
P(BS) I (C2N, + 22 + N Ke notuna /3
(40)
20

---

such that on B2, we have
B B1 mmax S C1 Un (40 + o/N+))
Vn nn
n
where the second inequality is by N(, < (1))
Let = (o where of (ike - BIke). The function f(x) x=1 -x) has derivative satisfying
[f((x)) 1 for [0, 11, hence f 1-Lipschitz there implying
1 - o² I'mlmax I |I B1 Ilaax
Since /n/n S Bike S 0.99, we have The 2 0.01vn/n nn. Ignoring constants, we have shown
B Billmax S
Vn mn
1602 02 mmaxxxxx S n
Yas
min
T V/2 n
n
R.P.
High probability event. Let B B1 n B2. Then, the event An B has high probability. Indeed, have
P(A) S 3N K2 + KN+E 23nmm///3
P(B") S 3(C2N, + )m +3N Ke Ke- Nommm//
Using union bound and further bounding C2N + 2K S 4C2N, K2 and - n S 5n=0 (by assumption (2). we obtain
P B & 19 K2n
(41)
which goes to zero under the assumption N_ K2n - o(1)
Controlling T.. Define
S
S
3
D =
D
m1
ml
mi
Vh
È = 20
D. E:
D
V20
where = STT' and ml = P* Px Note also that S./m, = B,. Let K(K + 1)/2. For the rest of the proof, we treat the above matrices as vectors in IR by considering only the elements on and above the diagonal, in particular order (say rowwise).
We have T,
|1 on An B and since P(AnB) cod;
o(1), is enough to establish
E = (N(0, 19d; see 20 Theorem 9.15]. Clearly,
Vh a E à
Vn
Vh
(Ō DD.
(42)
Vh á 20
From 34
with high probability, we have that
h
VNn Vn = / NNva (vn/n)1/2 n
mmm S
(43)
22
Next we have
0²
1102 021 |
(un/n) %n vn/n
1
Ø2
mink,e 2h.
max
hence
a1ō = la 1,)
(44)
Similarly,
17 1h- hllmma ming, hag
Nn?e Nn? <
14
max
and hence
11 =
1.
(45)
21

---

Lemma B.2. E = (Vh/(V2o)) (O) 1)) &d under the assumptions of Theorem A.6
Proof. See Section E.1
Therefore, from 42
45
Lemma B.2, and Slutsky's theorem, we obtain that E + (N(
provided that v N
(1). The proof is complete.
B.4 Proof of Theorem A.7 (Consistency, Tier 3)
We will follow the notation and argument in the proof of Theorem A.6 there, we have correct matching Pr: Pre-where Prt is as defined in the proof of Theorem A.6 and (34) and (35) hold. Since G C DD all the above also holds on A g n B. This is the event we will work
On event A n D n B defined
The inequalities
34 and (35) give
m), B, max Oi
Vn (40 5(.-)) Er 1,2.
n
Since, S//m//2 /( m PT, also have
ml(5g/b)) PB,PT max S Vn
Using + b c)² 33aa² 6² 2²), we obtain
((8//mm) (S2/mb))l 2 3 [|B1 - PB2P 1T 112
1(5i/mm1) -B113 (5/g/m6))) PB. PT
IV 3 min |Bi PB2PT 13 2K2
1/
max EZ 1,2
n
min
- - P
6
by assumption 24
Next, we note that (37) holds this case. Let m² Pm, PT and let be
the elementwise harmonic mean of m2 and m/. Then, both (38) and (39) hold, irrespective of the specific P. On G, we have 4 < which, combined with the latter two inequalities, yields
min hs 2 Nnnnnn/C 1(482). kt
Also The = =Bxe(1 - Bre) S 1/4. Then,
f Nn Vn2/(4
- -(5
(46)
2.
Putting the pieces together, we have the desired inequality on (A n B) n G. Combined with the probability bound (41) for (An B3), the proof is complete.
B.5 Proof of Lemma 2.1
We restate the lemma here with the extra uniqueness clause added.
Lemma B.3. Consider two K x K matrices B and B₂ with EVDs given by B, Q,AQT r= 1,2, for some diagonal matrix A with distinct diagonal entries. Then, a permutation matrix pa satisfies
B B2
(47)
and only if there exists a diagonal sign matrix St, such that
Q2 P==
(48)
Moreover if B, is (0,m) m) friendly, then there is most one P satisfying 47
22

---

Proof. Since P*Q1 Q1 is an orthogonal matrix, by absorbing P into Q1 and redefining Q1, we can assume P I. without loss of generality. The problem reduces to showing that (*) Q2AQu QA iff there is sign matrix 5 such that Q2 1 Let Q Q Q1 and note that Q is an orthogonal matrix. Multiplying (*) on the left and right by Q3 and Q2. the problem reduces to showing that (**) QAQ" for an orthogonal matrix Q and diagonal matrix A iff Q is a diagonal sign matrix (i.e., Q S*).
Assume (**) holds, the other direction being trivial. Note that changing A to A + ad does not change (**), hence we can shift the diagonal entries of A arbitrarily. Let A diag(Ax). Since (At) are distinct, we can shift them so that X1 < 0 and A > 0 for k 2 2. From (**), looking at the first
entries of the two sides, X1 Σx>1 0 Ag. hence
(1 Qi))
Σ PIA
Every term on the RHS is non-negative. It follows that every term has to be zero, implying Qi = 1 and Qıx for 2. This proves the assertion for the first row of Q. Repeating the argument for the other rows, the result follows.
Next, we prove the uniqueness. Suppose that there exist permutation matrices and such that PB, pT B2 PB, By the argument above, there exist sign matrices S and S such that PQ.S Q2, = PQ.S. Hence,
Q== p" PQiSS.
The problem then reduces showing that if PQ5 where Q is orthogonal matrix, P permutation matrix and S a sign matrix, then P = 1. If S = (the trivial sign matrix), then P = QQ" I. So assume S f I and + I. Then, there is j such that PQ..j - hence,
12Q., PQQ.. -
where 1 the all-ones vector. This gives 1²Q... = 0, contradicting friendliness of Bi. The proof is complete.
C
Additional Discussion
C.1
Class proportions and community refinements
Consider the following example to illustrate how class-proportion differences can be absorbed into refined community structures. Suppose we start with SBMs with equal connectivity matrices but differing class proportions:
0.4 0.1)
バ (0.5, 0.5), T2 = (0.4,0.6). B
0.1 0.3)
To eliminate the discrepancy in proportions, refine each community into two sub-communities, effectively doubling the number of communities. Specifically, for क we split its first community into sub-communities of proportions (0.4, 0.1) and its second community into (0.1, 0.4), so that the total proportions of the four new sub-communities become (0.4, 0.1, 0.1, 0.4). For π2, we retain its original first community (proportion 0.4), and split its second community (proportion 0.6) into three caaboommmuiticss of sizes 0.1, 0.1, 0.4. These four new sub-communitics also have overall proportions (0.4, 0.1, 0.1, 0.4). Hence the refined SBMs now have the same class proportions:
म = मं = (0.4, 0.1, 0.1, 0.4).
However, the connectivity matrices enlarge to reflect the finer partition:
00.4
0.4
0.1
0.1
00.4
0.1
0.1
0.1
0.4
0.4
0.1
0.1
0.1
0.3
0.3
0.3
B
B₂
0.1
0.1
0.3
0.3
0.1
0.3
0.3
0.3
0.1
0.1
0.3
0.3
0.1
0.3
0.3
0.3/
Note that class-proportion differences vanish (since मं = m2), but the matrices B, and B3 now differ
explicitly. This clarifies that proportion differences can equivalently be represented as connectivity differences through community refinement, motivating our focus on testing differences in B, modulo permutations while treating class proportions nuisance parameters.
23

---

C.2 Empirical Analysis of Average Degree Growth
To support the claim in Remark 4.5 that the Vn (logg condition mild in practice, we analyzed the average degree growth in several worldworld network datasets from the Py PyTorch Geometric library. We sampled subgraphs of increasing size from each dataset and computed the ratio of the average degree to log As shown in T this ratio tends to grow with n, indicating that the average degree in these networks grows faster than log n. Qualitatively similar behavior is observed across other datasets (amazon-pin) photoo wikics, corafull, coauthor-cs, and planetoid-coraa
Table 2:
Average degree vs. size for subsets of the Amazon Computers datasct. The final column shows that the average degree grows faster than log
Dataset
n
n/ /Muutal
avg wvg_degree
avg wvg_degree log n
umazon-computers
138
0.01
0,435
0.088
amazon-computers
276
0.02
0.623
0.111
amazon-computers
688
0.05
1.674
0.256
amazon-computers
1376
0.1
3.078
0.426
amazon-computers
2751
0.2
6,057
0.765
amazon-computers
6876
0.5
17.121
1.938
amazon-computers
13752
1.0
35.756
3.752
Implementation. The experiment was implemented in a lightweight PyTorch Geometric script lavg_degree__t tables tables_min. miimminn..p.. provided in the supplementary material for reproducibility.) which randomly subsamples nodes, constructs the induced subgraph, and computes the mean degree via torch_ torch_geome geometriiiiieeee wtuls. degree. We fix random seed for reproducibility and report average values over multiple fractions n/Pooul E (0.01, 0.02, 0.05, 0.1, 0.2, 0.5, 1.0).
C.3 Derivation of the Permissible Range of K for Graphons
This section provides the semi-rigorous derivation for the permissible range of when applying our test to general graphon models, summarized in Section 5.1
aim to find conditions on K that ensure our test has power when the underlying data comes from two different 8-smooth graphons, fi and f2. The argument combines oracle inequalities from [2] with the structure of our lest statistic. We apply their results with P.. = V2/nn and nig = n/K.
Let θ = (0iz) E [0, 1| be the matrix of connection probabilities, or "discrete graphon." where O E[A,y] Let θ be its K-block estimate based the observed adjacency matrix A, and let Ô be the best K-block approximation of O. By Proposition 2.1 of [21], the expected squared Frobenius error of the estimate bounded:
θ O1 S |0 - Ô1E + (n K + K3)(",
Un
K log K
+
n
Furthermore, for 3-soooth graphon, Proposition 2.5 of (1 bounds the approximation error:
||0 6 n² K 29 v K-
Assuming Vn 2 K log K, the estimation error bound simplifies to:
El - 0 - - v 20 + (n K + x2) Un
レズ K 28 v. log K + U, K2
An,K-
Now, consider the alternative hypothesis where we have discrete graphons, O and 2z. Ignoring the permutation matching step for simplicity (i.c., assuming identity permutation), our test statistic T, is proportional the squared difference of the estimated block models. This is, in turn, related to the squared difference of the estimated discrete graphons:
f N
i
Br 11ô, -6,12.
2
24

---

Using a triangle inequality, we can bound this difference:
1 2
1 -1110 - - 1ô,
-1 -1122 121
The true difference is ||0, θ = ( f2ll - f2 f2ll The two estimation
error terms are of order n, For the test to have power, the signal term must dominate the error terms. This leads the condition:
11 - S2lli> > An,K-
Dividing by v require Ank 011) This yields the final condition:
log K
K² = o())
K 29
1/2 7V/
sufficient of conditions for this hold K + oo (to handle the first term), while log K o(v)) (for the second term) and ~ = o(Nr,) (for the third term). These also ensure the earlier assumption Vn Z K log K. This provides the justification for the claims made in the main text.
D Additional experiments
Here, we provide more details of the experimental setup and report on more experiments. All experiments were conducted on an internal computing cluster with Intel(R) Xeon(R) Platinum 8160 CPUs (48 cores, 2.10GHz).
D.1 Competing methods
In this section, we describe the competing methods used in the experiments in the main text and below. Some of them were not originally designed for two-sampling testing, but have a natural extension this setting which outline below. Throughout this section, and "adjacency matrix" interchangeably. since the resulting distance measures between adjacency matrices will be invariant to node permutations.
the terms "network"
To measure a distance between two adjacency matrices, NCLM constructs a feature vector for each graph based on its so-called log- moments. To be more precise, [28] considers the k-th graph moment of a matrix A, my (A) = [AA/))*], which is the normalized count of closed walks of length k. The feature vector for an adjacency matrix A is then defined
g. (A) == (A), j E [J])
where J is some positive integer. The test statistic for comparing two adjacency matrices A₁ and Ag naturally given as the fi-distance between the feature vectors of the two graphs:
dNCLM(A1, A2) = (A1) Is |5 (A2)
Our experiments, reported in Appendix[Da suggest that a larger value of / improves performance. However, increasing J quickly increases the computation cost. In the results to follow, we have chosen 20 which provides a reasonable balance between performance and cost.
To form a distance between two adjacency matrices, ASE-MMD first computes the so-called adjacency spectral embedding (ASE) for each matrix. For an adjacency matrix A, consider |A| = (A A)1/2
and let |A| Σn ===1 eigenvalues and [u;) j the corresponding orthonormal basis of eigenvectors. Then, the adjacency
\u be its sigen-decomposition where A₁ 2 ... 2 An 2 0 are the
spectral embedding of A E (0, jax into B is
X = UAVSA SAAARR Rad
(49)
where SA = dlag(Ai, A2, .,, Aa) and UA is n x d matrix whose columns are #1, W2,... Ug. The rows of (A) define an empirical distribution Px(A) := Er= (x.(() where 8, is the point mass as ASE-MDD then measures the distance between two adjacency matrices Ai and Ag as the maximum mean discrepancy of the corresponding empirical distributions:
dASE-MMD (Ai, A2) MMD(P P
25

---

The MMD relies positive definite kernel function K R2 x R2 + R. Letting X = ((1)) and Y ((2)), one has
MMD X P+)
n(n Σ
kc xx
Σ k (N (x)) 2
n(n Σ EYyssny
In experiments reported here, we consider a Gaussian kernel and use random Fourier features to approximate the MMD. The bandwidth is set to be o² = 1. Additional experiments, reported in Appendix D.5. show that the results are not sensitive to the choice bandwidth.
Adapting to multiple samples. Next, we describe how we adapt the test statistics to the cases where the sample size greater than 1. Any measure of dissimilarity, d):;), between two networks, can be generalized to the two-sample case, by averaging the dissimilarity of pairs of networks from different samples. More specifically, given the two samples Are, E [N,] for 1,2, we have the
two-sample test statistic NIN; Σm E. Air, A2s)
note on network generation. Throughout the experiments, we replace Bernoulli variables with clipped version. In particular, write X Ber(p) for p E to denote X 1(U < p} for some U [0, 1]. When p [0, 1]. Ber(p) Ber(p), but otherwise Ber(p) naturally clipped either or 1. When we write SBM B, T) in experiments, is based on (er generation.
D.2 Simple 2-SBM
Our first simulation reproduces the experiment from 37 on 2-SBM. In particular, consider testing Ho A, A' SBM(Bo. т) versus H1 A SB,(Bo. T), A' SBM(B,, T), where
0.5
0.2
B
(50)
0.2
0.5 +E
and π = (0.4, 0.6). Note that each sample contains a single adjacency matrix. consider vertex sizes {100, 200, 500, 1000) and noise levels f0.01, 0.02, 0.05, 0.1) and evaluate the power of the our SBMTS using 1000 Monte-Carke replications. 3 summarizes the results alongside the power estimates for ASE-MMD reported in (37. The results clearly show the superior performance of SBMTS along both dimensions (n, e).
Table 3: Power estimates for ASE and SBM-TS for simple 2-block SBM experiment.
6 0.01
$ 0.02
0.05
= 0.1
SBM-TS
ASE
SBM-TS
ASE
SBM-TS
ASE
SBM-TS
ASE
0.047
0.161
0.06
0.776
0.09
0.27
200
0.15
0.599
0.09
0.17
1
0.83
500
0.785
1
0.01
0.43
1
1000
0.14
1
1
1
1
D.3 SW-GOT dataset
The Star Wars (SW)-Game of Thrones (GOT) dataset [34] is derived from popular films and television series. We consider 13 networks: six from the original and sequel SW trilogies, and seven from each of the GOT series. each graph, vertices correspond to characters and edges indicate whether two characters share scene. Let us denote the SW and GOT networks class C₁ and C2, respectively. The set of characters for both classes overlap across multiple networks, but no vertex correspondence utilized because network vertices unlabeled and each network has different number of vertices. Sample graphs from this dataset are shown in Figure I0 Appendix D.7 D.7
Similar to the COLLAB dataset, we consider two sample testing problem for distinguishing null of (C1, C1) vs. an alternative of C2), The resulting ROCs are shown Figure showing significant advantage for SBM-TS compared to the competitors.
26

---

1.00
0.75
TPR
ASF
NCLM SEM-TS
0.00
0.00
0.25
0.50 FPR
0.75
1.00
Figure 5: ROC for the SW-GOT dataset.
D.4 ROC plots for general SBM with random B
TigureBoshowe the mean ROC curves for the experiment in Section 5.3 The different plots correspond to different values of K. We refer Section [.3 for the detailed description of the experiments, where summary of these curves via their "area under the curve (AUC)" was provided in Table [
100
100
0.75-
75
7PR
0.10
0.25-
ASE
ASE
NCLM
NCLM
SSM-test
SBM-test
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.
1.00
FPR
(a) K 2, mean AUC 0.95.
(b) K 3, AUC = 0.91.
1.00
1.00
ASE NCLM SAM-tes!
NCLM
SSM-test
(c) 15, mean AUC 0.83.
(d) K 20, mean AUC 0.81.
Figure 6: ROC curves for the three methods (SBM-TS, MMD of ASE, and test statistic based on NCLM) averaged over 50 different experiments.
D.5 Bandwidth of ASE-MMD
We have conducted additional experiments in the same setting of Section 5.3 that is, general SBM with random B to determine the effect of bandwidth on the performance of ASE-MMD, The results
27

---

are summarized in Figure 7 One observes that the bandwidth does not have significant bearing on the power of the ASE-MMD test, with ROCs remaining almost the same across the range of x² E +00.01, 0.1, 1, 10, 100).
0.75
0.75
12
TPR
0.50
0.00
001
0.01
0.25
0.1
0.25
0.1
0.00
0.25
0.50
0.75
1.0
0.00
0.75
0.50
0.75
100
FPR
FPR
(a) K =
(b) K = 3
1.00
1.00
0.75
0.75
TPR
0.50
0.50
0.01
0.01
0.1
0.1
0.00
0.2
035
0.75
100
0.00
0.2b
050
0.6b
1.00
FPR
FPR
(c) K 15
(d) K 20
Figure 7: ROC curves for different choices of the bandwidth o² in the experiment with general B.
D.6 Number of Log Moments for NCLM
We have performed additional experiments in the same setting of Section 5.3 that is, general SBM with random B determine the effect of the number J of log-moments
the performance of NCLM. The results are summarized in Figure g The general trend is that higher J improves performance with J 20 (the maximum considered) producing the best results. We also note that this is mainly for small values of K, while for larger E (15, 20) the test is powerless regradless of the value J.
D.7 Sample graphs for real-world data
Example of graphs from the COLLAB dataset shown in Figure 9
D.8 Empirical runtime of Algorithm 1 With Respect To K
We investigate the mean runtime of Algorithm 1 function of the block dimension K. For varying values of K, we generate a random K symmetric matrix B, and random permutation Bg PBP and apply Algorithm The results are summarized in Table
28

---

1.00
1.00
0.75
0.75
TPR
0.50
0.25
O
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
FPR
FPR
(a) K
(b) K 3
1.00
1.00
TPR
0.00
050
1.00
(c) K 15
(d) K 20
Figure 8: ROC curves for different choices of the number of log-moments in the experiment with general B.
Figure 9: Sample graphs from the COLLAB dataset: High Energy Physies (left), Condensed Matter Physics (middle) and Astrophysics (right).
E Proofs auxiliary results
E.1 Proof of Lemma
Recall that the I Wasserstein distance between the distributions of two random variables Y and Z can be expressed as
dw, (Y,2)=
sup [E[M(Y)] - E(L(Z)]] h: [|A] L1
Table 4: Mean runtimes (ms) matching (B1, B2) selected values K.
K =
2
K = 10
K = 20
K = 50
K = 100
Mean runtime (ms)
0.6836
1.0366
1.3055
3.0415
8.3679
29

---

Figure 10: Sample graphs from the movic/tcevisiion dataset: Class 1 (left) and Class (right)
where ranges over all 1-Lipschitz functions h R + R, that is, h that satisfy for all x,y y E R. See [10] Chapter 4] or [3
S 1x-y/
Lemma B.2 follows form the following results:
Proposition E.1. Let $ Bin(nz,) p) with p I 1/2 and let 1 q == p. Let C S 0.4785 be the constant in the Berry-Esseen bound. Then,
p)
where o = vpg and
C
sup IP(W S <x) +(xx) - æER
(51)
Vnp/2
1
sup S1
(52)
npp/2
where Z N(0, 1).
Proof. We can write S = E B, where B, are i.i.d. Bernoulli(p) variables. Let X; (B: - p)/o be the standardized versions and note that W vā E X₁. Berry- -esre-Esseen bound gives
sup PP(W < x)) (xx) s EIX1 RER
3
Vn and Corollary 4.1 of 100 page 67] gives dwi (W,Z) < 1
We have
v/
1
El|B - pp p²q + q²p
1² + q²
(p + 9)2
x
σ3
3/2
Vpq
Vp/2
which gives the desired inequalities.
Lemma E.1. Suppose that for r E (1.2) and / E [N,] the symmetric matrices Art
(0, 1 1 are independent with independent entries on and above diagonal that satisfy (An))s Ber(B B (B()))) where Z,e [K] Prt is deterministic. Let
N. m, Σ C(rr, t=1
S. = Σ S(Ars, 2rt),
and for all k, E [K], let one / BBe(1 Bke) and
Viuué (S1)ae
(S2)ke
Exe
(53)
V20ke
MIkE
m2kK
where mas is the harmonic mean of (m1)Rε and (mz)xe. Assume that m2ke CITRiRE for some C1 > 0. Then
sup
P(Eke - P & C /
( +
BER
Vn
Vizzee
where C' > 0 is constant dependent C₁ and Z 10.
30

---

Proof. Let Tbl
V BRI(1
BRd).
First, notice that by Proposition E.
it holds that
Sykt
C
sup =
Bul
S x
2(x)
Okl
Myri
/mrnyua/n
for some constant C > 0, and for r = 1,2. Hence,
Viaat V20H
Syk
2(V
2m
C
sup
<x)
(x
5
(54)
#ER
Myrk
mike
V20k
Define the random variables
Vinge
Srkt
X,
r= 1,2,
V2
myki
and consider two independent random variable Y1 and Y2 with
Y VineBue V20kee
mike
2m
Notice that Y1 Y2 ~ N(O, 1). Let F'z denote the CDF of random variable Z. Then, we can rewrite (54)
C
sup sER
Fxx, ( (x)
Fr
S
(55)
For any x, 22 E R. we have
P(x1 X2 S x X2 = x2) P(Xi s x = x2),
by independence of X1 and X2. Fix R. Since P(Xi X2 Sx) = X2 S x X2)). it follows that
IP(
X2 - P(Y - Y/2 S +x) |[|xx, (2 + X2)] E[Fy, (I Y2)]
|F[Fx, (x + X2)] Fl X2) + F(Fy (x+ ElFr, (x Y2)]
S Ex| (x + X2) Fy, (x X2) + (x X2) 1--E- (a Y2)l
C
+ [E()(22) E(((12)]
where we have defined h(2) = Pry (x + z). Since
| S |11'1100 = 2m2z
||
Tike
M2kkl
1
22m" S vI+c V2T
=:
miki
by assumption. Then, from Proposition
E.1 [ETh(X2) E(b(()))))) 02// Vmauun/n
P( X2 <2)
P(Y Y2 $25))
Vminua/n +
v M
which gives the desired result.
Let I(R) be the of indicator functions of half-intervals, that is,
I(R) = (t + 1(t x) : Lemma E.2. Consider random variables X E [K] and Y, and assume that (Xni, i E [K] are independent conditional on Y,, In addition, we have
sup (
E (Xx.)) Y.) F[[())] 1YY, E An) I Ens i [K]
for some sequence of events A, and deterministic sequence of En and some random variable ~ μ. Assume that E, + 0 and P(Y, E A + as + so. Then (Xui.... Xnk) SK
31

---

Proof. Let Z, E [K] be ii.d. draws from μs. It is enough to show that
E II (
E ((ZA))
= II [()(Z.)]
(56)
1=1
for any collection of fi..... fK E (IR).
Let us fix one such collection and, for simplicity, write W,, = II (((nn)) and C II. (()(())) We want to show E[W,,] + C. From the assumption, it follows that
(X)( Yn - E[f((z)) S c, + 2 1(Y, E A.)) By conditional independence, W, Y,] bil < K max, aa bıl. which holds if a; b, E [-11,] for all i, we have
(l)( Y.)-- Then, using II] 04
B[ Yn] -cl < Kεn + 2K 1(Y, E A.
Then, we have
WW C W, Y, -
S EW, n. Y.]} C| S Ken 2KP(Y, E Aº).
Letting + oc, the desired result follows from the assumptions.
Proof of Lemma B.2 Let = = (Ert, E [N,,,r= 1,2). Let Let M(c1) (=: maxe S cemine). By
Lemma we have
n (VmJRe E ((Eee))) |2] E[h(2)]| 1/2 M(a)) = =Cady Vn Vmike"
sup AET(R)
(57)
v
M22k
where Eur as defined in 53 Z N(0, 1) and C(ci) is some constant dependent on et. Let kj. and consider the event
Brsk = > n (Zrr)
An = min neck 2 m/33 VE [N]]. [NI]. r.k
Then on An, we have mykk 2 cN see also 39
We also have P(A%) = o(1) under the
assumptions of Theorem by the same argument that controls & in Proposition F.4 Moreover, assuming N₂ S Ni-without loss of generality- on An, we have
M2kE
N2(C2n)²
Njn2/32 33802
Mike
where we have used the size assumption 19) That is, A, c ( M(PCM)) Taking ci = C3C in 57) and multiplying both sides of the inequality by IA., obtain
23 23C(BPC2)
1
sup [T((EE)) 2] ETh(2)]] 1A.. S Ve REI(R)
VNnvp
Since {Eve} are independent given the result now follows from Lemma
E.2 given Nnv, + co.
E.2
Proof of Lemma
For P E Ig, let
J((P) = (i Pa 0},
J2(P) ((i.j) P.j # i # j):
and note that + (Jz(P) = K for any P E II, By assumption A < 1/2, and hence
+ A# > 1/2 for ((P)
A < 1/2 for (1.5) E J2().
32

---

We also have
Σ (L + Pu)
Σ (1+ + Σ Ag..
:EJ((P)
(H.))
Let P * I, so that both (P) and [K] \ (P) are nonempty. Then,
tr(1 + - (1+
E (1+ E Dij
SE(K]W)(
(1.))J((P)
(K- (P(()) - - O,
showing that identity is the unique optimal solution.
E.3
Randomization
Let (eIx( denote the uniform distribution on the set of permutation matrices II
Lemma E.3 (Randomization). Assume that there a permutation matrix Cyz = Cre (Arz) potentially dependent on the adjacency matrix Arr such that
Bit Cet By
where B,, = S(Ari, ) O C((()) Let Brd be constructed as in step step 4 Then,
Byd Ris, Brt
(58)
where Prt U(TTx) independent of Art (and hence Brc).
Proof. Notice that by construction By Ure BUT with Ur+ U(Tx). Let Prt CrUTT T.. Then, Cr Br CT,, = Prt Brc P.T and (58) follows. remains to show independence of P.. and its uniform distribution. Indeed, let Po E IT and An E {0, jxxx,, We have (showing the dependence of Crt on Ar explicitly)
P(Pn = Po. Art = Ao) = P(U,t = PT Cri(Ar)) Ars = Ao) P(U, P. Cro(o)) Art AA)
P(Unt PP Cro(A)) P(Are = Ao)
1 P(Art = Ao)
where the third line is by the independence of Ur: and Art and the fourth line since U. ~ UIIx). The above shows that the joint distribution factorizes as uniform distribution for P.t and original (marginal) distribution for A,e, which proves the claim.
F Consistency of connectivity matrix estimation
Given an n X n adjacency matrix A, we apply a community detection algorithm to obtain label vector 2 (. 2n) E [K]" Let dyh be the normalized Hamming distance, that is, dNH(2, 2) du(2, 2)/n where (2, Σ 1/2 # 2 the Hamming distance.
Remark F.1. In the proof of consistency below. our results are given terms of || max where E here is a K x K matrix placeholder for different matrices as given in Propositions F3 and F44 However, to simplify the proofs below, when computing upper bounds for || max
max,.eE(1.....' (E we focus the case l: & f and omit the case k= = l as it is similar. The only difference dealing with l & that the constants would need be inflated.
We repeated use the following result, which follows for example from Bernstein's 's inequality:
33

---

Proposition F2. Suppose that S = =E
i=1 X; where X, Ber(p;) independently for E [n].
Assume that max; p; p. Then, for all [0. 1].
p p(p - 6p) 5e-5npp/3
and the same inequality holds for P(p -0- 6p).
Proof. By Bernstein inequality, using XX; Pil - 1, for any a > O, we have
nu
- E[S] 2 nu) S exp
20 2u/3
where x² = 1/2 2i var(X;). We have の² s and E|S]
S np. Setting óp, we have
nd²p²
P(S np 2 òmp) S eexp
2p + 20p/3
8²2
=xxp
2 26/3 np)) S eexp(-38mmp
where the last inequality uses 8 < 1. Replacing 3/8 with 1/3 gives a further upper bound.
Let us write (A, SBM,, [B, T) for an n-node draw from a Bayesian SBM, with connectivity B and class prior x.
Proposition F.3. Assume that (A, 2) ~ SBM,, x) with B satisfying 18) Let 5 = 2(,, $
3) and C(2), m- C(2). Set
B B(A, 2) = S/m,
B = B(A, 2) S/m.
Fix 10 and 0, and let 3 1 (K(Tmim)) with
K. and define
3 log n
8n =
n2/n
Assume that 6n I and 1n 2 3(1 + a) log For llk, let dsH(2, o 2). Then, with
probability least 1 3 a Ke -e-x"= m /3 for all Ilx such that 128)=(a) 1
Un |P..PP - max 32.
=(()),
(59)
n
C1 Un Sn.
| B max
(60)
n
|| - P.SPP Ima < 80,3 no),(o))
(61)
ml P. P!
mmx 63 n²=(o))
(62)
min mae 2 n²² 12. k,t
(63)
By redefining E to be I, one gets Pa BP in place of B. Thus, without loss of generality, we can assume to be the identity permutation. Let
of Proposition F3
(z = Σ 11 11
1{ = k}}, dn(z, Σ 12 2z}
so that Ee d)( = 2d (z, 2). This can verified by writing
1122 = k}} 1( = k}} = 1f2; = k; 2, * k}
1f + k, =k)-
Let n = ΣE 1 (2, = k)) and 75 >' ( = A: and note that |n4 - 7i $ dx(2, Let us
also write
du (2, 2)
p max
(64)
k T1k
34

---

and note that (ft/nz)) - S p.
Let us consider some events. First, consider event
Eg = max Σ Ais S 1n
(65)
Applying Proposition F2 conditioned on with p Civn//n and then taking expectation of both sides to remove the conditioning, we have
P
Σ Au CPna(1+ S se-uCcuoa3.
Take 1/vC1. Then, P(E by union bound and assumption / 2 (1 + alloogo
Next, note that P(n= I (1 (1-k) k))=k) I exp(-ná2on n /3) for N E (0, 1). by Proposition F2 the event
Consider
ε =
min n 2 n//3
kk=l...KK
where 1/3 = Kmmn Then, by union bound P(Ef) S K exp( (opp--""nTmmn?? On E
(2,
2d (2,
max
2,
(66)
Thg:
Next, we apply Proposition
F2 conditioned on 2, to get
P( Buz Bael 2 5, Bae 2z) 18,
s 2e SueneeBull 18,
I 2e
where we have used the lower bound in [8] Take 8% 3 log n/ (nV,) and let
& Ba Beel S Bee for all k l E }
(67)
Then, by union bound, P(E n Eg) - P( & s -0 We will work on &g n & and note that
(EENEEEEN 2 1- - P(E)) P(ET) P(E nEg)
Note that on E2,
max Bu Beel < 6n Crun/n,
(68)
max Bue S 20/vn/n 6,E
(69)
using the upper bound in 18 and assumption on < 1. This proves (60
Now, let us establish 61 We have
Ske
Skel S Σ Atj 112 k, 2) 1[2 k 2g = E]}-
i.j
Adding and subtracting 1(2 = k. 2j = {} and expanding by triangle inequality, we get SSke - Ssel S T2: + T22 where
Ta1 =
1.
T22 =
Σ
Consider T22 first. We have
Ton Σ 14 = 118 = = f) 162, 01)
( -1)- -
< 20 d2(2)
35

---

on Eg. Similarly, T21 S 20 dx(2, 2) on Eg. Then,
Ske - Skel - 20 (ne + ms)p - 4C using ny I n for all k. Combined with (66), this proves (61).
(70)
Let us define B' ===3 S/m. For le + we have mie mgme. Then, on E
Skt Skel
Biee Blell
S 2nnnnn (nk" + n =n - 4 V/
T4
using ny 2 n/B for all k. By (69)
on E2, we also have
B S 201 Un (1 23p) s 401
Vn
n
assuming 23p - 1. Next we note that
Moke
1|
1 S 3p.
migt
Assuming that 3p < 1/2, letting x = mage Dise/mmee we have It follows that on E2
x S 33p 1/2, hence |1 11-x" 11-2-111
11 S 6p.
See
BBee BLel =
1
Mik
< Blee 6p S 24C1 Un
mke
Mike
By triangle inequality
[B B max 5 B B'll mmlx + +1IB² B max
S 24C1 Pn
Un n
P + +C,3
n
28C1 Pn Bp S
n
using 3 2 1 (we are weakening the constants in favor of simpler expression).
For 62 we have |[m mlkel S ngnel with 666 proves the claim.
Rgãe mgme
1 S n²3p. Putting the pieces together combined
F1
Multi-network extension
Proposition F.4. Assume that (Ac, SBMn, (B, fort [N], where B satisfies [8 and ne satisfy
ns 14 S C2n.
(71)
Let St = S(A,, 21, S, = S(A,, 2,) and m. = C(z), m C(2)). For (at) E IT&N set
B(o)= E, PoP.SpPP''
B B:= E. St
ex(o) = dNH( 2x)
Σ. Po
Σ, m4
where we interpret the division matrices as elementwise.
Fix K E 10 and a > 0, let B (/(TTmia) with R = - k, and define
8, a logn
Nnw,
Assume that 6n < 1 and v, 2 3(1+a) log Then, with probability at least 1 (C22V+22K")
Ke
"Ken"" - R we have, for all (a.) E I for which max, c,(a) < 1/(253).
[i)()) Bllmax < 40 C1,33 Vn
(72)
| Bllmaxx
< C1 V/ 8n.
(73)
|| Pa, St PT. mmax
< 881 vnnu (t)))
(74)
[m Pa, mr oi |lmax
< 6, n c)()),
(75)
min [me]ke 8.
n for all t (N)
(76)
36

---

where 3 = 1/ with R =
Note that n, here is deterministic (size of the f-th network) and different from ng in the proof of Proposition R3
Proof. By redefining & to be or, (2r), . we can assume, without loss of generality, that or is the identity permutation (and hence Po. Ix) for all t. Note that none of the events we consider below depend on Ø, hence the result indeed holds for all a simultaneously.
First, consider event
Eo
max JE(
ElAdls S2C1C2un ==1
(77)
Applying Proposition F.2 conditioned on 25, with p Cjun/n and nop I C2C and then taking expectation both sides to remove the conditioning, we have
P Aaly 2 C1C2pa(1 Se-10.0amm3
Take 1/v0//2 S Then, by union bound and assumption v,/3 2 (1 + ax) log n, we have P(E S C2Nn
Next, let Aikk E 1((x); = k). the (true) number nodes in community lt in network By have P(nek kTTTTe)) S exp(-x²mexee for (0, 1). Consider the event
Proposition F22 defined as
& = min nuk 2 n/B, Vt E [ k==I...K
where B = 1/(ft/ with R = K. Then, by union bound and using n, 2 n,
P(E S NK exp(=x" 20 /3).
By the argument in the proof of Proposition F.3 and letting dNu(2 2t), have En E
| - Sellmax & 8,, ||m, me mmax < 6,nfEr,
[milke 2 n
(78)
Let us now control B = (2 St)/EE m²). Conditioned on 24, we have
E, Silke Bin((x: miles, BRt).
Also note that, for k: o we have 1Σ, melke E, MeaTee 2 E. 2 Nn²/8² on E,. Then,
applying Proposition F22 conditioned 2t. we get
P([ Beel 2 BRe (2))
18,
_ 2e E Bue 18
I 6, 1 (v,
where we have used the lower bound in
18) Take 82
3 log n (Nnw.) and let
& Bar
Bell S on Bes for all k, l }
(79)
Then, by union bound, P( n Eg) < (1) < n We will work on En n E n & and note that
Pl n > 1 - P(ET) - P(ET) P(E E
Note that on Eg.
max Byg - Biel S 8n CiVn/n, k,t
(80)
max Bug S 2C1vn/n hi
(81)
37

---

using the upper bound in (8] and assumption 6, S 1. This proves (60)
Next we control the deviation B B. Treating division (and taking absolute values) of matrices as element-wise,
E. E. + E, St)
+ b mi my + E, me) c d
Σ, m4
Σ
We then have
b
(a/c) + (b/c) - (a/c) -1 (0/0))(0/0)((/)) 1 (d/c)
((b/c) - (d/c)
c+ d
(d/c)/
1- ld/c
Let max, Et. Then, have
E. - Selkel (a)
E, n,tt Enn
lb/clael -
80,8'v, Un
E.(mela he
Σ, nz
80, 03 Un E, n4tt
881 80,,33
Σ. n4
where (a) is by (78) and (b) uses assumption n, 2 n. Similarly, we have [[d/c]kel S 63 Note that
a/c- B hence elementwise in [0, 2C1 on &g. Assuming that 80 - 1/2, we have,
(b/c) (a/c)(d/c) lb/c + (a/c)ld/c) - 400 "
1 ld/cl
(where the final inequality means every element of the LHS is S RHS). That is, we have shown
Σ, St E,S, Σ, m
E, m S 40 nn e.
This proves
72 and finishes the proof.
38

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, the main claims made in the abstract and introduction accurately reflect the paper's s contributions and scope. The work delivers its promises by providing consistent and powerful two-sample test under the stochastic block model, along with theoretical guarantees and empirical validation.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The discussion of the strength of the assumptions for the main results is included in the remarks in the supplementary materials.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
39

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The main results and auxiliary lemmas have complete proofs that are provided in the supplementary materials. We also provide meaningful discussion on the underlying set of assumptions.
Guidelines:
The answer NA means that the paper does not include theoretical results,
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The experiments section and the corresponding sections of supplementary material provide a clear description of the setup.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
40

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Yes, the paper provides open access to both the code and data, along with sufficient instructions to enable faithful reproduction of the main experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
public/guidess httpi///uuuiee/oooeuuuinsssssss onooiicyl)yy for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips. wwwbblic/guids///eeeoo
setbbbmmsssonnii ssionpolicy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: The experiments in section 5 as well as in the supplementary material are provided with complete details sufficient reproduce the results.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The experiment section gives clear description of the factors of variability as well as the methods of calculation of the statistical significance of the tests.
Guidelines:
The answer NA means that the paper does not include experiments.
41

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eπror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
The paper indicates the characteristic of the technical cluster used for the experiments.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental rums well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httttp/://oorrpps..cc///bb//beia
Answer: [Yes]
Justification: Yes, the research conducted in this paper conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [No]
42

---

Justification: No, the paper does not explicitly discuss potential positive or negative societal impacts of the work. The focus on methodological and theoretical contributions to network inference, without specific commentary on how the techniques might influence or be applied in societal contexts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negatíve societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging. and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
The datasets are both credited in the reference section.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
43

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, pwwpsssipppsseeeee thcode com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Yes, the paper introduces new algorithm for two-sample testing on networks, and the accompanying implementation is given in the supplementary material. The attached files include implementations for all the tests ensuring reproducibility.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
supplemental material is fine, but if the main contribu-
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
44

---

Justification:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
Declaration LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (btrge///oorrrggccc////offeeerrp for what should or should not be described.
45


Reviews:
[{"review_id": "5xmGFd3IPa", "reviewer": "Reviewer_EKux", "summary": "This paper studies a 2-sample network testing problem: Each sample contains a few networks drawn from SBMs with the same $K\\times K$ matrix $B$ but possibly different number of nodes, and there is no node correspondence among these networks. The null hypothesis is that the matrices $B_1$ and $B_2$ for two samples are the same subject to a permutation. A chi-square test statistic is proposed. It first alines all networks within each sample by permutation, then searches for a community permutation to align the two samples, and finally constructs a chi-square test. Theoretical properties of the test statistic under both the null and alternative hypotheses are provided.", "questions": "If my understanding correctly, your proof of theory relies on that the permutation matrices find to aline the estimated communities within and between two samples need to be \"exactly correct\" with probability tending to $1$. There are $O(N_1+N_2)$ number of permutation matrices. Assuming all of them being correct is almost unrealistic in practice. Does your statistic work when a small number of these permutation matrices are incorrect?", "limitations": "While I appreciate the clear writing and the theoretical results in this paper, I think it has some significant limitation. \n\n1. It lacks evidence that this testing problem is practically meaningful: The authors assume that the networks are from SBM. But this model is too ideal to fit many real networks. In practice, the lack-of-fit effect of SBM will most likely dominate the two-sample difference, making the testing problem meaningless. Other models such as the degree-corrected SBM (DCSBM) will be more realistic, but the current test cannot be extended to DCSBM. \n\n2. I doubt that the method works in practice. The algorithm requires finding $O(N_1+N_2)$ number of $K\\times K$ permutation matrices. The theory is susceptible to getting the correct permutation matrices for all of them (or the majority of them). However, when this happens, it actually means that the individual network are dense enough (e.g., $n\\nu_n\\to\\infty$). This is a strong-signal case, making the testing problem less interesting. When we have multiple networks in one sample, we hope that only $Nn\\nu_n\\to\\infty$ is required. Under this conditions, it is impossible to guarantee that most of those $O(N_1+N_2)$ permutation matrices are correct. \n\n3. There is not much technical novelty in this work. The analysis is pretty straightforward given the existing works (such as [3,4]). \n\n4. The paper misses some relevant reference on 2-sample network testing, such as Jin et al. (2024) Optimal network pairwise comparison.", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "This paper contains both theoretical results and numerical results. Writing is very clear and easy to digest.", "was_revised": true, "final_justification": "I suggest the authors to incorporate some of their rebuttal into the revision, particularly the large-SBM approximation to DCBM and the reason why $N\\to\\infty$ does not weaken the sparsity requirement.", "rebuttal": "> .... Does your statistic work when a small number of these permutation matrices are incorrect?\n\nIt degrades gracefully if a small fraction of permutations are not correctly recovered as it just adds a bit more noise to the already noisy estimate of the $B$. The test is designed to handle noisy estimates. We have more to say about permutation recovery below (in short, failure probability is exponentially small in a wide regime).\n\n> 1. It lacks evidence that this testing problem is practically meaningful: The authors assume that the networks are from SBM ... \n\nWe respectfully disagree that the stochastic block model (SBM) is “too ideal” to capture real-world networks. An SBM with a sufficiently large number of communities is a histogram-type, step-function approximation to an arbitrary graphon and is therefore a universal approximator in $L^{2}$ (see, e.g., [4], [5]; see also the rate-optimal results in [6]). By allowing $K$ to grow, one can, in particular, approximate a degree-corrected SBM (DCSBM) simply by subdividing each community into high- and low-degree sub-blocks. In practice, the apparent lack of fit usually stems from using an **underspecified** SBM with a small $K$, not from a fundamental limitation of the model class.  \n\nAs we point out below (under *“our conditions are mild”*), we place **no hard limit on $K$**—our theory accommodates arbitrarily large $K$. Please also see our experiments in Sections 5.3 and 5.4, where we generate data from a smooth graphon and a random dot-product graph (RDPG). In particular, our test outperforms a spectral test specifically designed for the RDPG.  \n\nThis **histogramisation** strategy is entirely in line with classical non-parametric testing: discretising (binning) continuous data to create contingency tables is the underlying principle behind Pearson’s chi-squared goodness-of-fit test [1] and its classical treatments [2, 3]. Recent work shows that the same **bin-then-test** idea remains state-of-the-art: for example, the minimax-optimal conditional-independence test of Neykov, Balakrishnan & Wasserman [7] and the multiscale Fisher’s independence test of Gorsky & Ma [8]. Our use of a large-$K$ SBM plays the same role for network models, providing a flexible partition of the sample space on which to build a two-sample test. \n\nThat said, if one prefers to model degree heterogeneity explicitly, our procedure extends naturally to the DCSBM. When the block-connectivity matrix $B$ can be consistently estimated, the node-specific degree parameters $\\theta_i$ can be treated as nuisance parameters—much like the class proportions $\\pi$. In this sense, our method naturally carries over to settings with degree heterogeneity, and the SBM framework serves as a tractable starting point for developing and analysing such tests.  \n\n---\n\n### References  \n\n[1] Pearson, K. (1900). On the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be reasonably supposed to have arisen from chance. Philosophical Magazine, 50, 157–175.  \n\n[2] Lehmann, E. L., & Romano, J. P. (2005). Testing Statistical Hypotheses (3rd ed.). Springer.  \n\n[3] Cochran, W. G. (1952). The χ² test of goodness of fit. Annals of Mathematical Statistics, 23(3), 315–345.  \n\n[4] Wolfe, P. J., & Olhede, S. C. (2013). Non-parametric graphon estimation.  \n\n[5] Orbanz, P., & Roy, D. M. (2015). Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures. IEEE Transactions on Pattern Analysis and Machine Intelligence, 37(2), 437–461.\n\n[6] Gao, C., Lu, Y., & Zhou, H. H. (2015). Rate-optimal graphon estimation. Annals of Statistics, 43(2), 762–785.  \n\n[7] Neykov, M., Balakrishnan, S., & Wasserman, L. (2021). Minimax optimal conditional independence testing. Annals of Statistics, 49(4), 2151–2177.  \n\n[8] Gorsky, S., & Ma, L. (2022). Multi-scale Fisher’s independence test for multivariate dependence. Biometrika, 109(3), 605–628.\n\n> 2. I doubt that the method works in practice ...\n\nWe would like to clarify that the matching consistency result does not rely on the networks being dense. The result is based on inequality (13), which can be written as\n$$\n\\| \\hat{B} - PBP^{\\top} \\|_F \\leq \\frac{\\eta \\theta}{2\\sqrt{2}K}.\n$$\nBoth sides of this bound scale with $\\nu_n/n$, so the guarantee does not depend on the sparsity level $\\nu_n$. Instead, successful matching fundamentally requires that the matrices satisfy the $(\\eta,\\theta)$-friendly condition. This condition, rather than the networks being dense, is the key driver of matching consistency in our theory. \n\nAs suggested by reviewer oPrG, we plan to simplify the statement of the conditions.  All we need are\n\n1. $N= \\max(N_1, N_2)$ grows at most polynomially in $n$,\n2. the average degree satisfies $\\nu_n = \\Omega(\\log n)$, and\n3. $B$ has a simple spectrum and no eigenvector summing to zero.\nThese are mild in practice. For your reference under the heading (**Our conditions are really mild**) we outline in detail how the conditions can be simplified.\n\nRegarding your comment:\n\n> We hope that only $n N\\nu_n \\rightarrow \\infty$ is required. \n\nThis is exactly what we require and not $n \\nu_ n \\to \\infty$ (see the displayed equation in the statement of Theorem 2). Even if we required the latter, this is no dense regime. Since $\\nu_n$ is an **average degree**, even the ultra-sparse case $\\nu_n=\\Theta(1)$ meets this condition;  the condition $n N\\nu_n \\rightarrow \\infty$ is essentially always satisfied and we will remove it in the revision.\n\nRegarding your concern that matchings fail when $N_1, N_2$  grow, we have shown that **the probability of matching failure is exponentially low**; hence the probability of missing just one is still low, when $N_1, N_2 = O(n^{\\alpha})$. Thus, we can allow a polynomial growth of the number of samples in the network size, which is very reasonable in practice. \n\nIt is worth noting that in many interesting cases $N_1 = N_2 = 1$, that is, we are attempting to decide if two large networks are from the same distribution. This case alone is the focus of the majority of the work in the field. \n\n## Our conditions are really mild\n\nPer suggestions by multiple reviewer, we will simplify our conditions as outlined below. This allows us to reduce then two essentially two or three mild conditions in each case.\n\nHere is how we can simplify the conditions for theorem 2. Assume $B = (\\nu_n / n) B^0$ for a fixed $B^0$. Then the conditions for theorem 2 are:\n1.  $B^0$ has distinct eigenvalues and no eigenvector of it sums to zero.\n2.  $N = O(n^\\alpha)$ for some $\\alpha \\ge 0$.\n3.  $\\sqrt{\\nu_n n^{1+\\alpha}} \\cdot \\widetilde{\\varepsilon} = o_p(1)$.\n4.  $\\widetilde{\\varepsilon} \\le C K^{-3/2}$ for some constant $C = C(B^0)$ that only depends on $B^0$.\n\nCondition 1 is equivalent to $B^0$ being $(\\theta^0,\\eta^0)$-friendly for some values of these parameters, but is clearer now. Condition 2 ensures all matchings are recovered and just requires the number of networks to grow at most polynomially in the network size $n$ (a very mild condition). The last two conditions are about the misclassification rate of the community detection algorithm; per the work of Zhang and Zhou [1], it is possible to achieve $\\widetilde{\\varepsilon} = N \\exp( - c \\nu_n / K)$, where $c = c(B^0, \\pi)$ only depends on $B^0$ and class proportions. No matter how large $K$ is, Condition 4 is satisfied as long as $\\nu_n \\to \\infty$. Condition 3 is also satisfied if $\\nu_n \\ge C_2 \\log n$ for a sufficiently large $C_2$ (for example, $C_2 = K (2+2\\alpha) / c$).\n\nSo all in all, for an arbitrarily large $K$ and $\\alpha$, there is a constant $C_2 = C_2(K, \\alpha)$ such that if $N = O(n^{\\alpha})$ and $\\nu_n \\ge C_2 \\log n$, then the null distribution in theorem 2 holds. Note that we only need the expected degree to grow logarithmically in $n$.\n\nAs for Theorem 3, let us again assume $B_1 = (\\nu_n /n) B_1^0$ and $B_2 = (\\nu_n / n) B_2^0$. Assume that:\n1.  $B_1^0$ and $P B_2^0 P^T$ are different for any permutation matrix $P$.\n2.  $\\widetilde{\\varepsilon} = o_p(1)$.\nThen, under the alternative, with probability $1-o(1)$ we have $\\widehat{T_n} = \\Omega(N \\nu_n^2)$. As per the above argument, a condition like $\\nu_n \\ge C_2 \\log n$ is enough to guarantee item 2.\n\nWe plan to rewrite the theorems in this simplified form and move the more elaborate, finite-sample-flavored versions to the supplement, with a discussion of how they reduce to these cases.\n\n[1] A. Y. Zhang and H. H. Zhou. Minimax rates of community detection in stochastic block models.\nAnnals of Statistics, 44(5):2252–2280, 2016.\n\n> 3. There is not much technical novelty in this work. The analysis is pretty straightforward given the existing works (such as [3,4]).\n\nWe respectfully disagree. First, [3] does not provide any theoretical results. Second, [4] focuses on the consistency of the labels, whereas the problem of estimating the labels is not the focus of our paper. Our work instead begins by addressing the fundamental question of identifiability for the testing problem and then develops a computationally efficient matching algorithm. Building on this algorithm, we design a novel two-sample test, accompanied by a thorough characterization of the test statistic under the null hypothesis and a proof of its consistency under the alternative. These theoretical results, developed entirely from scratch, provide rigorous support for our empirical findings and further validate the usefulness of the proposed test.\n\n> 4. The paper misses some relevant reference on 2-sample network testing, such as Jin et al. (2024) Optimal network pairwise comparison.\n\nWe thank the reviewer for pointing out this relevant work. We will add a citation to Jin et.al.(2024), “Optimal network pairwise comparison” in the related work section and discuss how it relates to our setting in the final version."}, {"review_id": "BYx89sOKiC", "reviewer": "Reviewer_9DE8", "summary": "The author(s) propose a two sample testing problem for a number of networks where vertex correspondence is not needed and the number of nodes may vary. The proposed test statistic consists of two separate steps -(a). matching step which finds an approximate matching between a pair of connectivity matrices and (b) constructing a discrepancy measure between the two matched connectivity matrices. The theoretical results how the asymptotic distribution and the consistency of the test statistic. The proposed testing procedure shows superior performance over its competitors in the simulated and the real data examples.", "questions": "Overall, I think the paper bring an important contribution to the network literature in terms of doing statistical inference therein. I think there are definitely some novel elements especially, the construction of the test statistic based on the matching step in algorithm . I have the following queries for the author(s).\n\n1. It would be good to see the scalability of Algorithm 1  in some experiments by varying the network size.\n2. Some explanation or interpretation of the assumptions used in Theorem 1 and Theorem 2 would be useful for the readers.\n3. It would be good to see the difficulty of the testing problem by varying the noise level $\\epsilon$.\n4.  Is it possible to improve R.H.S of equation (16) by having the minimum of the two Frobenius norms rather than the sum?\n5. As I mentioned in the weakness, some discussion about how different community detection algorithms affect the final test-statistic would be good.\n\nOne minor point I could not see section C.3 or F.5. I assume this is in the appendix but I could not see it when I downloaded your paper from the NeurIPS site.", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "strengths:\n\n1. Rigorously explaining the fundamental difference between two sample network testing problem between labelled and unlabelled networks\n2. Clearly motivating and describing the importance of the problem along with the challenges\n3. The first step in the test-statistic construction i.e. estimating the permutation matrix $\\hat{P}$ via solving an LAP from noisy observations is clearly described and has lots of merits as this tries to solve a novel and difficult problem.\n4. Theoretical results on the asymptotic distribution of the test statistic and the consistency has been proved with careful arguments  and involve novel proof techniques.\n5. Sufficient evidence showing superior performance of the proposed test statistic on different types of simulated data and on the real world network data as well.\n\nweakness:\n\n1. Experiments do not show the scalability of the spectral matching algorithm 1 with the network size\n2. There were not much discussion in terms of how different community detection algorithms affect the final test statistic.\n3. The theoretical section lacked enough interpretation or explanation on the assumptions used in Theorem 1 and Theorem 2 respectively.", "was_revised": true, "final_justification": "I think the final round of clarifications provided by the author made their contribution clearer. They have addressed most of the reviewers' queries with detailed theoretical explanations and examples.\n\nI am happy to raise the rating to \"Accept\".", "rebuttal": "> It would be good to see the scalability of Algorithm 1 in some experiments by varying the network size.\n\nAlgorithm 1 is designed for matching two $K \\times K$ connectivity matrices. As such, its computational complexity depends only on $K$ and is independent of the overall network size $n$.\n\nIf you meant scalability as a function of $K$, here is a table demonstrating such result:\n\n|               | **K = 2** | **K = 10** | **K = 20** | **K = 50** | **K = 100** |\n|---------------|-----------|------------|------------|------------|-------------|\n| Mean runtime (ms) | 0.6836 | 1.0366 | 1.3055 | 3.0415 | 8.3679 |\n\n*Table : Mean runtimes (ms) of `matching(B1, B2)` for selected values of K.*\n\n\n> It would be good to see the difficulty of the testing problem by varying the noise level.\n\nSection C.1 includes an experiment on a simple 2‑SBM where we vary both the noise level and the network size to illustrate the difficulty of the testing problem.\n\n> Some explanation or interpretation of the assumptions used in Theorem 1 and Theorem 2 would be useful for the readers.\n\nThanks for the comment. We plan to simplify the conditions greatly as is outlined below in detail.\n\n---\n\n## Our conditions are really mild\n\nPer suggestions by multiple reviewers, we will simplify our conditions as outlined below. This allows us to reduce then two essentially two or three mild conditions in each case.\n\nHere is how we can simplify the conditions for theorem 2. Assume $B = (\\nu_n / n) B^0$ for a fixed $B^0$. Then the conditions for theorem 2 are:\n1.  $B^0$ has distinct eigenvalues and no eigenvector of it sums to zero.\n2.  $N = O(n^\\alpha)$ for some $\\alpha \\ge 0$.\n3.  $\\sqrt{\\nu_n n^{1+\\alpha}} \\cdot \\widetilde{\\varepsilon} = o_p(1)$.\n4.  $\\widetilde{\\varepsilon} \\le C K^{-3/2}$ for some constant $C = C(B^0)$ that only depends on $B^0$.\n\nCondition 1 is equivalent to $B^0$ being $(\\theta^0,\\eta^0)$-friendly for some values of these parameters, but is clearer now. Condition 2 ensures all matchings are recovered and just requires the number of networks to grow at most polynomially in the network size $n$ (a very mild condition). The last two conditions are about the misclassification rate of the community detection algorithm; per the work of Zhang and Zhou [1], it is possible to achieve $\\widetilde{\\varepsilon} = N \\exp( - c \\nu_n / K)$, where $c = c(B^0, \\pi)$ only depends on $B^0$ and class proportions. No matter how large $K$ is, Condition 4 is satisfied as long as $\\nu_n \\to \\infty$. Condition 3 is also satisfied if $\\nu_n \\ge C_2 \\log n$ for a sufficiently large $C_2$ (for example, $C_2 = K (2+2\\alpha) / c$).\n\nSo all in all, for an arbitrarily large $K$ and $\\alpha$, there is a constant $C_2 = C_2(K, \\alpha)$ such that if $N = O(n^{\\alpha})$ and $\\nu_n \\ge C_2 \\log n$, then the null distribution in theorem 2 holds. Note that we only need the expected degree to grow logarithmically in $n$.\n\nAs for Theorem 3, let us again assume $B_1 = (\\nu_n /n) B_1^0$ and $B_2 = (\\nu_n / n) B_2^0$. Assume that:\n1.  $B_1^0$ and $P B_2^0 P^T$ are different for any permutation matrix $P$.\n2.  $\\widetilde{\\varepsilon} = o_p(1)$.\nThen, under the alternative, with probability $1-o(1)$ we have $\\widehat{T_n} = \\Omega(N \\nu_n^2)$. As per the above argument, a condition like $\\nu_n \\ge C_2 \\log n$ is enough to guarantee item 2.\n\nWe plan to rewrite the theorems in this simplified form and move the more elaborate, finite-sample-flavored versions to the supplement, with a discussion of how they reduce to these cases.\n\n[1] A. Y. Zhang and H. H. Zhou. Minimax rates of community detection in stochastic block models.\nAnnals of Statistics, 44(5):2252–2280, 2016.\n\n---\n\n> Is it possible to improve R.H.S of equation (16) by having the minimum of the two Frobenius norms rather than the sum?\n\nIt is probably not possible to improve the right-hand side of equation (16) by replacing the sum with the minimum of the two Frobenius norms. Even if such an improvement were achievable, it would amount to only a constant factor improvement, which is not significant in the overall analysis.\n\n> As I mentioned in the weakness, some discussion about how different community detection algorithms affect the final test-statistic would be good.\n\nThanks for the suggestion. In theory, the only effect of the community detection algorithms is via the misclassification rate in the statements of the theorems. In practice, however, different algorithms may perform better in different settings. For example, in our graphon experiments we used a Bayesian community detection method instead of spectral clustering and observed improved performance: the popular spectral clustering for fitting SBM seems to fail when the underlying model itself is not SBM; however a proper SBM fitting algorithm like Bayesian Gibbs sampler manages to estimate the best approximating SBM to the graphon. This is briefly noted on Line 283. We will expand the discussion on different detection algorithms in the final version of the paper.\n\n> One minor point I could not see section C.3 or F.5. I assume this is in the appendix but I could not see it when I downloaded your paper from the NeurIPS site.\n\nWe apologize for the confusion caused by incorrect numbering in the supplementary material. The content referred to as Section C.3 is actually Section D on page 4, and Lemma F.5 corresponds to Lemma I.5 on page 24. We will correct these references in the final version to avoid further confusion."}, {"review_id": "l5WHZfnTUa", "reviewer": "Reviewer_YcXS", "summary": "The paper studies the two-sample test for the stochastic block model (SBM), where the goal is to determine whether two sets of networks come from the same SBM (i.e., the parameters of the SBM underlying the two sets of networks are the same) or not. The paper focuses on the scenario where nodes have no labels and therefore cannot be matched in different networks/sets. The paper proposes a novel test based on a spectral matching algorithm to recover the mapping between nodes in two networks from noisy observations from the same SBM (i.e., under the null hypothesis). The paper proves that the matching algorithm is consistent, and that under some assumptions the test statistic defined in the paper follows a chi-square distribution.  It also shows that the test correctly identifies two networks as coming from different SBMs under some conditions. The paper presents an experimental evaluation on synthetic and real data.", "questions": "Is the correct value of K required by the proposed method? If so, the experimental evaluation could explore the results (e.g., false positives, false negatives, etc.) when the incorrect value of K is used.\n\nHow does the method perform in practice when the proportions of nodes in the same community are extremely different?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "STRENGHTS\nThe two-sample test for the stochastic block model without node labels is interesting and non-trivial.\n\nThe theoretical results in the paper are interesting and somehow comprehensive, addressing both the limiting distribution under the null hypothesis and the power of the proposed.\n\nThe paper is mostly well written.\n\nWEAKNESSES\n\nThe paper does not consider an arbitrary SBM, but an SMB where nodes are placed in communities i.i.d. according to some probability distribution, that somehow places some additional structure on the problem (compared to an arbitrary SBM).  Also, in the final formulation of the problem, the proportion of communities could be very different under the null hypothesis: when the proportions are very different, it seems strange to say that the underlying SBM is the same. \n\nThe method seems to require the number K of communities in the underlying SBM, or, equivalently, that the SBM inference algorithms used by the test detect the correct value of K. This seems very unrealistic.\n\nWhile the paper is mostly well written, in the technical part some quantities are not defined. For example, in the summary of results, N and n are used but not defined. Also, in 4.2, C_1 and C_2 are not defined, N is used before it is defined, and the same for some other symbols.\n\nThe restrictions required by the theoretical results seem stringent. For example, the fact that communities are “sparse” may be violated in practice. \n\nThe experimental results could be expanded.\n\nIn the supplement, there is a section “C.6 Sample graphs for real-world data “ with no content.", "was_revised": true, "final_justification": "Considering the rebuttal and the discussion with the authors, their comments answer some of my questions in a satisfactory manner, so overall my score is positive, with reasons to accept outweighing the reasons to reject. However, there are two aspects that are still not entirely addressed, which is why my score is borderline accept. The first one is the need to know the correct value of $K$. While it is true that a SBM with a larger $K$ subsumes models with fewer communities as special cases, this is not practical in any way; also, current methods to estimate $K$, while consistent, may not converge with the sample sizes of interests. The second one is given by the conditions required by the theoretical results. As highlighted also by other reviewers, the conditions are not as mild as argued in the rebuttal.", "rebuttal": "> The paper does not consider an arbitrary SBM, but an SBM where nodes are placed in communities i.i.d. according to some probability distribution, ...\n\nWe understand the concern that when community proportions differ greatly, it may seem inconsistent to consider the underlying SBM as the same. As explained in lines 64–70, we treat class proportions as nuisance parameters to avoid this trivial case. This approach is justified because communities are typically defined by their connectivity patterns rather than their relative sizes, and differences in proportions can often be absorbed into the connectivity matrices via community refinement (as detailed in Appendix G in the supplement). Furthermore, if one wishes to explicitly test for differences in class proportions, it is straightforward to perform an initial separate test comparing the multinomial distributions of the estimated class proportions $\\pi$. Finally, we are not assuming i.i.d sampling of the labels; they can be arbitrary. All we require is that the class proportions remain of the same order in the limit.\n\n> The method seems to require the number $K$ of communities in the underlying SBM, or, equivalently, that the SBM inference algorithms used by the test detect the correct value of $K$. This seems very unrealistic.\n\nWe acknowledge the concern about needing the true number of communities, $K$.  In practice, one can leverage existing consistent estimators for $K$ in SBMs [1, 2], and our Appendix outlines a data-driven procedure for selecting $K$.  Even without such estimators, one may simply choose $K$ large enough: an SBM with a larger $K$ subsumes models with fewer communities as special cases.\n\n --- \n \n[1] Ma, Shujie, Su, Liangjun, and Zhang, Yichong (2021).\n    Determining the number of communities in degree-corrected stochastic block models.\n    Journal of Machine Learning Research, 22(69):1–63.\n\n[2] Le, Can M. and Levina, Elizaveta (2022).\n    Estimating the number of communities by spectral methods.\n    Electronic Journal of Statistics, 16(1):3315–3342.\n\n> While the paper is mostly well written, in the technical part some quantities are not defined. For example, in the summary of results, N and n are used but not defined. Also, in 4.2, $C_1$ and $C_2$ are not defined, N is used before it is defined, and the same for some other symbols.\n\nThank you for your comment! We have carefully revised the manuscript to address this, and the final version will include all necessary definitions with complete clarity. \n\n> The restrictions required by the theoretical results seem stringent. For example, the fact that communities are “sparse” may be violated in practice.\n\nWe do not require the communities to be sparse; our theory allows for dense models perfectly fine. In response to suggestions from the reviewers, we plan to simplify the statement of our conditions, as outlined below in details. To our knowledge, the resulting assumptions are among the mildest in the literature.\n\n---\n\n## Our conditions are really mild\n\nPer suggestions by multiple reviewers, we will simplify our conditions as outlined below. This allows us to reduce then two essentially two or three mild conditions in each case.\n\nHere is how we can simplify the conditions for theorem 2. Assume $B = (\\nu_n / n) B^0$ for a fixed $B^0$. Then the conditions for theorem 2 are:\n1.  $B^0$ has distinct eigenvalues and no eigenvector of it sums to zero.\n2.  $N = O(n^\\alpha)$ for some $\\alpha \\ge 0$.\n3.  $\\sqrt{\\nu_n n^{1+\\alpha}} \\cdot \\widetilde{\\varepsilon} = o_p(1)$.\n4.  $\\widetilde{\\varepsilon} \\le C K^{-3/2}$ for some constant $C = C(B^0)$ that only depends on $B^0$.\n\nCondition 1 is equivalent to $B^0$ being $(\\theta^0,\\eta^0)$-friendly for some values of these parameters, but is clearer now. Condition 2 ensures all matchings are recovered and just requires the number of networks to grow at most polynomially in the network size $n$ (a very mild condition). The last two conditions are about the misclassification rate of the community detection algorithm; per the work of Zhang and Zhou [1], it is possible to achieve $\\widetilde{\\varepsilon} = N \\exp( - c \\nu_n / K)$, where $c = c(B^0, \\pi)$ only depends on $B^0$ and class proportions. No matter how large $K$ is, Condition 4 is satisfied as long as $\\nu_n \\to \\infty$. Condition 3 is also satisfied if $\\nu_n \\ge C_2 \\log n$ for a sufficiently large $C_2$ (for example, $C_2 = K (2+2\\alpha) / c$).\n\nSo all in all, for an arbitrarily large $K$ and $\\alpha$, there is a constant $C_2 = C_2(K, \\alpha)$ such that if $N = O(n^{\\alpha})$ and $\\nu_n \\ge C_2 \\log n$, then the null distribution in theorem 2 holds. Note that we only need the expected degree to grow logarithmically in $n$.\n\nAs for Theorem 3, let us again assume $B_1 = (\\nu_n /n) B_1^0$ and $B_2 = (\\nu_n / n) B_2^0$. Assume that:\n1.  $B_1^0$ and $P B_2^0 P^T$ are different for any permutation matrix $P$.\n2.  $\\widetilde{\\varepsilon} = o_p(1)$.\nThen, under the alternative, with probability $1-o(1)$ we have $\\widehat{T_n} = \\Omega(N \\nu_n^2)$. As per the above argument, a condition like $\\nu_n \\ge C_2 \\log n$ is enough to guarantee item 2.\n\nWe plan to rewrite the theorems in this simplified form and move the more elaborate, finite-sample-flavored versions to the supplement, with a discussion of how they reduce to these cases.\n\n[1] A. Y. Zhang and H. H. Zhou. Minimax rates of community detection in stochastic block models.\nAnnals of Statistics, 44(5):2252–2280, 2016.\n---\n\n> The experimental results could be expanded.\n\nWe believe the current experimental section is already comprehensive, with additional results on random dot product graphs, graphons, a 2-SBM with varying parameter, and an additional real-world dataset in the supplement. The experiments also already vary noise levels, sparsity, and network size. If there are specific types of scenarios you would like to see, we would be happy to consider them.\n\n> In the supplement, there is a section “C.6 Sample graphs for real-world data “ with no content.\n\nWe apologize for the confusion. The content corresponding to Section C.6 (“Sample graphs for real-world data”) is indeed included as Figures 5 and 6 on pages 6 and 7 of the supplementary material. We will make this clearer in the final version."}, {"review_id": "In2Kzt2RFQ", "reviewer": "Reviewer_oPrG", "summary": "The paper proposes a hypothesis testing approach to determine whether two sequences of graphs are generated from an SBM with the same set of parameters. The approach consists of two separate modules: a spectral-based component to address the lack of labels, and a component of a statistical test. In general, the main ideas are clearly presented, which makes the approach convincing.", "questions": "See \"Strengths And Weaknesses\".", "limitations": "No. There are some discussions of limitations in \"Conclusion\", however, the discussion is not thorough.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The paper is well-organized, and key ideas are well-explained. Sufficient theoretical justifications are provided, and thus the proposed approach is convincing. However, I still have a few concerns.  \n1. Motivation: I think the authors should give a more convincing argument regarding why the problem itself (including the assumptions, such as using SBM to generate the graph sequences) is important in practice. Though the paper has studied the real dataset COLLAB, it serves to verify the effectiveness of the algorithm. It is unclear to me the practical use of testing whether two sequences of graphs from COLLAB are from the same distribution. The authors are not required to perform any additional numerical study, but they should describe scenarios where the problem is important. \n2. SBM: The paper focuses on graphs generated from SBM. It is indeed true that SBM can approximate graphs sampled from graphons, but provided the number of blocks becomes arbitrarily large. Therefore, I think considering SBM is somehow restricted. Please discuss.\n3. Spectral-based matching: Spectral-based matching is not a new idea (e.g., [1-3]), though it may not have been directly applied to the problem studied in the paper. The authors should thoroughly discuss existing works on spectral-based graph matching.  \n4. Theoretical results: I think the theoretical results are not particularly instructive in their current form. For example, quantities such as $\\gamma_n, \\xi_r$ seem to come from nowhere and are hard to understand. It is unclear how to verify the validity of the complicated conditions of the theorems, and assess whether those numerical bounds are useful or not. The $(\\theta, \\eta)$-friendly condition in Definition 2.1 should be a key condition. However, its motivation is unclear, and how should one verify the condition given a sequence of graphs?\n5. Proofreading: It seems that the authors haven't carefully proofread the paper. For example, eq. (60) in line 169 and eq. (59) in line 205 are missing. In line 230 (Remark 4.1), \"more details\" are not in C.3 (seems they are in D). \n\nBased on the above, I give a Rating of 3. However, I may change my assessment and the rating based on the rebuttal.\n\n[1] https://arxiv.org/pdf/1602.04181\n\n[2] http://www.stat.yale.edu/~yw562/teaching/684/GM-grampa.pdf  (presentation slides)\n\n[3] https://arxiv.org/pdf/2306.15747", "was_revised": true, "final_justification": "The authors have resolved most of my concerns in their rebuttal, and hence, I raise my score to 4. The paper offers a solid theoretical foundation, and I look forward to seeing its practical value demonstrated in future work.", "rebuttal": "> 1. Motivation: ...\n\nThe use of the COLLAB data was for illustration and mainly due to its having a clear \"ground truth.\" We have another example in the supplement (a movie dataset which perhaps bears a similar criticism). The actual two-sample testing problem is widely applicable across the sciences, as we outline in the global response. In choosing the datasets, we were constrained by the limited availability of data with ground truth.\n\nRegarding the SBM, as you point out, SBMs can approximate general graphons, and that is perhaps a good enough justification. We have provided a thorough defense of SBM, and the idea of bin-and-test, in response to Reviewer EKux, which we avoid repeating due to the space constraint. \n\nAs for concrete scenarios, below we provide a long list where two-sample network testing appears.\n\n---\n\n## Concrete applications of vertex-agnostic two-sample network tests\n*(Most reduce to $N_1=N_2=1$: one large graph vs another, no common labels.)*\n\n- **Clinical connectomics.** Compare functional or structural brain graphs of patients (e.g., Alzheimer’s, ASD) with healthy controls. Individual-specific parcellations make node correspondence impossible; detecting a distributional shift quantifies disease-related rewiring. *Bullmore & Sporns 2009; Zalesky, Fornito & Bullmore 2012*\n\n- **Protein / gene interaction.** Condition-specific interactomes—healthy vs tumour tissue, or two species—share only a subset of molecules. A label-free test spots pathway-level dysregulation or evolutionary divergence. *Menche et al. 2015; Pavlopoulos et al. 2011*\n\n- **Single-cell omics trajectories.** Cell–cell similarity graphs built separately for treatment and control arms trace developmental manifolds. Each run samples different cells, so matching is futile; the test asks whether the underlying trajectories differ. *Saelens, Cannoodt & Saeys 2019; Townes & Irizarry 2020*\n\n- **Ecological food-webs.** Predator–prey networks from protected reefs vs disturbed sites share few species due to turnover. Testing highlights ecosystem change beyond simple diversity counts. *Tylianakis & Morris 2017; Mougi & Kondoh 2012*\n\n- **Inter-bank lending.** Daily transaction graphs before vs after a policy shock (or calm vs crisis) have banks entering, exiting, or anonymised. Detecting a distributional shift is crucial for systemic-risk surveillance. *Bargigli et al. 2015; Squartini, van Lelyveld & Garlaschelli 2013*\n\n- **Online information diffusion.** Retweet graphs of a suspected misinformation campaign are compared with baseline news spread. Disposable or hashed accounts preclude alignment; a two-sample test flags coordinated manipulation. *Vosoughi, Roy & Aral 2018; Yang, Ferrara & Menczer 2021*\n\n- **Cyber-security flow graphs.** Current network-flow graph vs historical baseline under dynamic IPs and NAT. Vertex-free testing raises real-time intrusion alarms. *Heard et al. 2010; Irofti, Pătrașcu & Hîji 2022*\n\n- **Development-econ field trials.** Social networks from treatment vs control villages are disjoint. A two-sample test quantifies how the intervention reshaped interaction patterns. *Paluck, Shepherd & Aronow 2016; Cai, de Janvry & Sadoulet 2021*\n\nThese diverse cases show that deciding whether two network samples share the same generating law is a core statistical task across science, finance, security, and policy.\n\n----\n\n> 2. SBM: ...\n\nSBMs indeed can approximate graphs sampled from nearly arbitrary $L^2$ graphons by increasing the number of blocks. The key is that we **can allow** for an arbitrarily large number of blocks. There is no hard constraint on $K$ in our results (as we outline below). The only implicit condition on $K$ is what is required for the consistency of community detection algorithms, which imposes a very mild condition.\n\nWe will clarify this in our response to your comment on simplifying the conditions.\n\nWe also note that we have conducted experiments on graphon-based and random dot product graph (RDPG) models. These results demonstrate that our test remains robust and performs well even when the data are generated from more general distributions, suggesting that our method has strong potential for broader applicability beyond the SBM setting.\n\n> 3. Spectral-based matching: ...\n\n-   There is indeed a significant literature on spectral matching, and we did discuss several closely related works in this line in Section 1.2 [1, 11, 12, 20, 22, 30, 32, 33]. Thanks for pointing to additional references; we will add them to the discussion.\n-   It is worth noting that despite the vast literature, very few papers prove statistical consistency of these algorithms under a stochastic graph model, a contribution which we make to this literature.\n\n> Theoretical results ...\n\nThank you for your suggestion. We agree and plan to simplify the conditions, in particular to emphasize that the conditions are not restrictive and that we can allow an arbitrarily large $K$. What we require is very mild. The presence of $\\gamma_n$ and $\\delta_n^{(N_r)}$ was due to the desire to preserve the finite-sample nature of our results and to aid in reading the proof, which we now realize is perhaps distracting.\n\nFor example, the second term in $\\gamma_n$ always goes to zero, so instead of $\\gamma_n = o_p(1)$, we just need to state that $\\widetilde{\\varepsilon} = o_p(1)$, i.e., the misclassification rate goes to zero. As for $\\delta_n^{(N_r)}$, we apologize for its being missing from the main text; it is\n$$\n\\delta_n^{(N_r)} = \\sqrt{\\frac{3 \\beta^2 \\alpha \\log n}{N_r n \\nu_n}},\n$$\na quantity essentially the same as the second term in $\\gamma_n$ which always goes to zero (no condition needed). We always have $N n \\nu_n$ going to infinity at least as fast as $n$, since $N \\ge 1$ and $\\nu_n = \\Omega(1)$.\n\nBelow we outline in detail how we can greatly simplify the conditions.\n\n---\n\n## Our conditions are really mild\n\nPer suggestions by multiple reviewers, we will simplify our conditions as outlined below. This allows us to reduce then two essentially two or three mild conditions in each case.\n\nHere is how we can simplify the conditions for theorem 2. Assume $B = (\\nu_n / n) B^0$ for a fixed $B^0$. Then the conditions for theorem 2 are:\n1.  $B^0$ has distinct eigenvalues and no eigenvector of it sums to zero.\n2.  $N = O(n^\\alpha)$ for some $\\alpha \\ge 0$.\n3.  $\\sqrt{\\nu_n n^{1+\\alpha}} \\cdot \\widetilde{\\varepsilon} = o_p(1)$.\n4.  $\\widetilde{\\varepsilon} \\le C K^{-3/2}$ for some constant $C = C(B^0)$ that only depends on $B^0$.\n\nCondition 1 is equivalent to $B^0$ being $(\\theta^0,\\eta^0)$-friendly for some values of these parameters, but is clearer now. Condition 2 ensures all matchings are recovered and just requires the number of networks to grow at most polynomially in the network size $n$ (a very mild condition). The last two conditions are about the misclassification rate of the community detection algorithm; per the work of Zhang and Zhou [1], it is possible to achieve $\\widetilde{\\varepsilon} = N \\exp( - c \\nu_n / K)$, where $c = c(B^0, \\pi)$ only depends on $B^0$ and class proportions. No matter how large $K$ is, Condition 4 is satisfied as long as $\\nu_n \\to \\infty$. Condition 3 is also satisfied if $\\nu_n \\ge C_2 \\log n$ for a sufficiently large $C_2$ (for example, $C_2 = K (2+2\\alpha) / c$).\n\nSo all in all, for an arbitrarily large $K$ and $\\alpha$, there is a constant $C_2 = C_2(K, \\alpha)$ such that if $N = O(n^{\\alpha})$ and $\\nu_n \\ge C_2 \\log n$, then the null distribution in theorem 2 holds. Note that we only need the expected degree to grow logarithmically in $n$.\n\nAs for Theorem 3, let us again assume $B_1 = (\\nu_n /n) B_1^0$ and $B_2 = (\\nu_n / n) B_2^0$. Assume that:\n1.  $B_1^0$ and $P B_2^0 P^T$ are different for any permutation matrix $P$.\n2.  $\\widetilde{\\varepsilon} = o_p(1)$.\nThen, under the alternative, with probability $1-o(1)$ we have $\\widehat{T_n} = \\Omega(N \\nu_n^2)$. As per the above argument, a condition like $\\nu_n \\ge C_2 \\log n$ is enough to guarantee item 2.\n\nWe plan to rewrite the theorems in this simplified form and move the more elaborate, finite-sample-flavored versions to the supplement, with a discussion of how they reduce to these cases.\n\n[1] A. Y. Zhang and H. H. Zhou. Minimax rates of community detection in stochastic block models.\nAnnals of Statistics, 44(5):2252–2280, 2016.\n\n---\n\n> ... Definition 2.1 ...\n\nDefinition 2.1 has appeared in the spectral graph matching literature, so we did not elaborate. The motivation becomes clear in the proof of theorem 1. Regarding its verification, it is like any other assumption about true parameters in theoretical work (we never observe the true parameters). We can, however, verify it on our estimates of $B$ as a surrogate (albeit an imperfect solution).\n\nThe condition is essentially saying that there is no multiplicity in the eigenvalues of $B$ and that no eigenvector has entries that sum to zero. This is almost certainly true for a randomly generated $B$, and hence is most likely true in practice.\n\n> Proofreading: ...\n\nWe apologize for the oversight. The equations referred to as (59) and (60) are indeed included in the appendix, and we will make the cross-references clearer in the main text. Similarly, the mention of “more details” in Remark 4.1 should refer to Section D rather than C.3. We will correct these references and will thoroughly proofread the revised manuscript."}]

Author rebuttal:

Meta-review: This is a well written paper that found favor with the reviewers. There is room for improvement, and I hope the authors will take advantage of the excellent reviews before the camera ready deadline to follow up on some of the suggestions.
Decision: Accept (poster)