Transfer Learning for Latent Variable Network Models
Authors: Akhil Jalan
Arya Mazumdar
Soumendu Sundar Mukherjee
Purnamrita Sarkar
Venue: NeurIPS 2024 poster (2024)
Keywords: Transfer learning
network estimation
latent variable models
Primary area: learning_theory
TL;DR: Transfer learning gets vanishing reconstruction error on the entire target network given o(1) fraction of the target nodes

Abstract: We study transfer learning for estimation in latent variable network models. In our setting, the conditional edge probability matrices given the latent variables are represented by $P$ for the source and $Q$ for the target. We wish to estimate $Q$ given two kinds of data: (1) edge data from a subgraph induced by an $o(1)$ fraction of the nodes of $Q$, and (2) edge data from all of $P$. If the source $P$ has no relation to the target $Q$, the estimation error must be $\Omega(1)$. However, we show that if the latent variables are shared, then vanishing error is possible. We give an efficient algorithm that utilizes the ordering of a suitably defined graph distance. Our algorithm achieves $o(1)$ error and does not assume a parametric form on the source or target networks. Next, for the specific case of Stochastic Block Models we prove a minimax lower bound and show that a simple algorithm achieves this rate. Finally, we empirically demonstrate our algorithm's use on real-world and simulated graph transfer problems.

Transfer Learning for Latent Variable Network Models
Akhil Jalan
Arya Mazumdar
Department of Computer Science UT Austin jkhiljjalanuueexs.. edu
Hahcooğlu Data Science Institute & Dept of CSE UC San Diego arya@ucsd. edu
Soumendu Sundar Mukherjee Statistics and Mathematics Unit (SMU) Indian Statistical Institute, Kolkata samukherjee@isccaa in
Purnamrita Sarkar
Department of Statisties and Data Sciences
UT Austin
purna.sarkar@austtau wtt.iiiinntteeseeeeeeeeeeee utexas. edu
Abstract
We study transfer learning for estimation in latent variable network models. In our setting, the conditional edge probability matrices given the latent variables represented by P for the source and Q for the target. We wish estimate Q given two kinds data: (1) edge data from a subgraph induced by an o(1) fraction of the nodes of Q, and (2) edge data from all of P. If the source P has no relation to the target Q, the estimation етrоr must be ((1). However, we show that if the latent variables are shared, then vanishing error is possible. We give an efficient algorithm that utilizes the ordering of a suitably defined graph distance. Our algorithm achieves o(1) error and does not assume parametric form on the source or target networks. Next, for the specific case of Stochastic Block Models we prove minimax lower bound and show that simple algorithm achieves this rate. Finally, we empirically demonstrate our algorithm's 's use on real-world and simulated network estimation problems.
Introduction
Within machine learning and statistics, the paradigm of transfer learning describes a setup where data from a source distribution exploited to improve estimation of target distribution Q for which small amount of data is available. Transfer learning is quite well-studied in learning theory, starting with works such as -Ben-Davil et al. (2006); Cortes et al. (2008); Crammer al. (2008), and the same time has found applications in areas such as computer vision (Tzeng et al. 2017a) and speech recognition (Huang al.) 2013). fairly large body of work transfer learning considers different types of relations that may exist between P and Q, for example. Mansour et al. (2009); Hanneke and Kpotufe (2019 2022). with emphasis on model selection, multitask learning and domain adaptation. On the other hand, optimal nonparametric rates for transfer learning have very recently been studied, both for regression and classification problems (Cai and Wei 2021 Cai and Pul 2024).
In this paper, we study transfer learning in the context of random network/graph models. In our setting, we observe Bernoulli samples from the full n edge probability matrix for the source and only no X no submatrix of Q for ni & n. We would like to estimate the full X n probability matrix Q, using the full source data and limited target data, i.e., we are interested in the task of estimating Q in the partially observed target network, utilizing information from the fully observed source network. This a natural extension of the transfer learning problem in classification/reersssooo
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

to network context. However, it is to be noted that network transfer is genuinely different problem owing to the presence of edge correlations.
While transfer learning in graphs seems to be a fundamental enough problem to warrant attention by itself, are also motivated by potential applications. For example, metabolic networks model the chemical interactions related to the release and utilization of energy within an organism (Christensen
and Nielsen 2000). Existing algorithms for metabolic network estimation (Sen et al.
2018 Baranwal
et al,) (0200) and biological network estimation more broadly (Fan et al. 2019
Li ct al. 2022)
typically assume that some edges are observed for every node in the target network. One exception
is Kshhrsaaarrr et al. (2013), who leverage side information for host-pane cast-pathogen protein interaction
networks. For the case of metabolic networks, determining interactions in vivd requires metabolite balancing and labeling experiments, so only the edges whose endpoints are both incident to the
experimentally chosen metabolites are observed (Christensen and Nielsen 2000). For a non-model organism, the experimentally tested metabolites may be a small fraction of all metabolites believed to affect metabolism. However, data for a larger set of metabolites might be available for a model organism.
To study transfer learning on networks, one needs fix general enough class of networks that is appropriate for the applications (such as the biological networks mentioned above) and also suitable to capture the transfer phenomenon. The latent variable models defined below appear to be a natural candidate for that.
Latent Variable Models. Latent variable network models consist of large class of models whose edge prohabilities are governed by the latent positions of nodes. This includes latent distance models,
stochastic block models, random dot product graphs and mixed membership block models (Hoff
itt atall,2000 Hofi ( Handcook et al. 2007 Holland et al., 1983
et al. 2022
Airoldi al., 20008). They can also be unified under graph limits or graphons (Lovász] 2012 Bickel
and Chen 2009), which provide a natural representation of vertex exchangeable graphs (Aldous
1981 1979). In addition to their theoretical breadth and usefulness, latent variable models
are relevant and applicable to real-world settings such as neuroscience Ren et al. (2023). ecology
Trifonova et al. (2015), international relations Cao and Ward (2014), political pscyhology Barberá et al. (2015). and education research Sweet et al. (2013).
For unseen latent variables 21.-... Fn E X C Rd and unknown function fo : X' X - [0 where X' is a compact set and d an arbitrary fixed dimension, the edge probabilities are:
Qij (xx,,,,),,
(1)
Typically, in network estimation, one observes adjacency matrix {Ag} distributed as [BernoulliQ2s)] }. and either has to learn æ; or directly estimate fo. There has been much work in the statistics community on estimating æ; for specific models (usually up to rotation). For stochastic block models, see the excellent survey in Abbe (217)).
Estimating Sq can be done with some additional assumptions (Chatterjee 2015). When fQ has appropriate smoothness properties, one can estimate by a histogram approximation (Olhede and Wolfe 2014: Chan and Airoldi 2014). This setting has also been compared to nonparametric regression with an unknown design (Gao et al. (2015). Methods for network estimation include Universal Singular Value Thresholding (Chatterjee 2015 Xu 2018), combinatorial optimization (Gao
et al. 2015 Klopp et al., 2017). and neighborhood smoothing (Zhang et al. 2017 Mukherjee and
Chakrabarti 2019).
Transfer Learning on Networks. We wish to estimate the target network Q. However, we only observe fo on ("²) pairs of nodes, for a uniformly random subset of variables S c (1,2....,,)) We assume S is vanishingly small, so ni == SS| o(r).
Absent additional information, we cannot hope achieve o(1) mean-squared error. To see this, suppose fq is stochastic block model with 2 communities of equal size. For a node i g S, no edges incident to are observed, so its community cannot be learned. Since no < n. we will attain ((1) error overall. To attain error o(1), we hope to leverage transfer learning from a source P if available. In fact, we give an efficient algorithm to achieve o(1) error, formally stated in Section 2
Theorem 1.1 (Theorem 2.3] Informal). There exists an efficient algorithm such that, if given source data Ap f0, 1 and target data AQ E {0, 1 no coming from an appropriate pair fQ)
In the organism, opposed to in vitro (in the lab).

---

of latent variable models, outputs Q E R such that
I
QQ Q1 s o())
2 21-
There must be a relationship between P and Q for them to be an appropriate pair for transfer learning. We formalize this relationship below.
Relationship Between Source and Target. It is natural to consider pairs (fr: such that for all y E X, the difference (fr y) (x. y)) is small. For example, Cai and Pu (2024) study transfer learning for nonparametric regression when fp fo is close to polynomial in æ y. But, requiring fP fo to be pointwise small does not capture broad class of pairs in the network setting. For example, if fP = asq. Then fp So = (a- f) can be far from all polynomials fo is, e.g. a smoothh graphon P However, under the network model, this means Ap and Ag are stochastically identical modulo one being times denser than the other.
We will therefore consider pairs fQ) that are close in some measure of local graph structure. With this in mind, we use a graph distance introduced in Mao et al. (2021) for a different inference problem.
Definition 1.2 (Graph Distance). Let P E [0, 1j be the probability matrix of graph. For i,j i + j. we define the graph distance between them as follows:
dr(i,j) lI(e: e,) P2 e.e, - =22
where e,, e, R are standard basis vectors.
Intuitively, this first computes the matrix p2 of common neighbors, and then computes the distance between two rows of the same (ignoring the diagonal elements). We will require that fP. fq satisfy a local similarity condition on the relative rankings of nodes with respect to this graph distance. Since we only estimate the probability matrix of Q, the condition is on the latent variables .1....,2, of interest. The hope is that the proximity in graph distance reflects the proximity in latent positions.
Definition 1.3 (Rankings Assumption at Quantile hn)) Let (P.Q) be a pair of graphs evaluated on latent positions. We say (P, Q) satisfy the rankings assumption at quantile hy S 1 if there exists constant C such that for all E [n] and all j * i, i belongs to the bottom hy -uquntiee of dp(ī,-) -). then j belongs the bottom Chantquatile of do(i.-).
To further motivate Definition 1.3 recall our motivating example of biological network estimation. Previous works require some form of similarity between networks to enable transfer transferSen et al. (2018); Fan et al. 2019); Baranwal al, (2020). For example, Kshirsagar al. (2013) require a commonality hypothesis: if pathogens A, B target the same neighborhoods in a protein interaction network, one can transfer from A to B. Our rankings assumption similarly posits that to transfer knowledge from to B, A and B have similar 2-hop neighborhood structures.
Note that Definition 1.3 involves quantiles of graph distances; therefore it is a relative condition, because it depends on a rank-ordering within both graphs P. Q before comparison. On the other hand, an absolute condition would require that for nodes i, E [n]. if e.g. dp(i,j) 100 then do (i. < C- 100. Our condition is more flexible and will hold for larger set of graph pairs (P, Q), such as pairs where one graph is much more dense than the other.
Finally, to illustrate Definition 1.3 consider stochastic block models fr, fo with kp 2 kg commu- nities respectively. If nodes i.J are in the same communities then Pe; = Pej, so de(i, require that minimizes dg (i, -). This occurs if and only if (i. = 0. Hence if i, belong to the same community in P. they in the same community Q. Note that the converse is not necessary; we could have Q with 1 community and P with arbitrarily many communities.
0. We
With the relationship between the source and target defined by the rankings assumption, contribu- tions are as follows.
(1) Algorithm for Latent Variable Models. We provide an efficient Algorithm T for latent variable models with Hölder-smooth fr. fq- The benefit of this algorithm is that does not assume a parametric form of fr and fq- We prove a guarantee on its error in Theorem 2.3
In fact. Cai and Pu 2024 highlight this exact setting as direction for future work.
3

---

(2) Minimax Rates. We prove minimax lower bound for Stochastic Block Models (SBMs) in Theorem 3.2 Moreover, we provide a simple Algorithm 2 that attains the minimax rate for this class (Proposition 3.4)
(3) Experimental Results Real-World Data. metabolic networks and dynamic email networks, as well as synthetic data (Section
We test both of our algorithms on real-world
All proof' are deferred to the Appendix.
1.1 Other Related work
Transfer learning has recently drawn lot of interest both in applied and theoretical communities. The
notion of transferring knowledge from one domain with lot of data to another with less available data has seen applications in epidemiology
www.anooogyyyooollloppooooo Apostolopoulos and Bessianal (2020), computer vision Long
et al. 2013): zeng et al. (2017b) Huuh et al. (2016): Donahue et al. (2014); Neyshabur et al. (2020)
natural language processing Daumé , etc. For comprehensive survey see ZZuanng et al. 2019
Weiss et al. (2016); Kim et al. (2022). Recently, there have also been advances in the theory of
transfer learning Yang et al. (2013); Tripuranei et al. (2020); Aggawal al. (2023): Cai and Wei
(2021) Cai and Pu (2024); Cody and Beling (2023).
In the context of networks, transfer learning is particularly useful since labeled data is typically hard to obtain. Tang et al. (2016) develop an algorithmic framework to transfer knowledge obtained using available labeled connections from source network to do link prediction
target network. [ee it al. (2017) proposes deep learning framework for graph- structurdd data that incorporates transfer learning. They transfer geometric information from the source domain to enhance performance on related tasks in a target domain without the need for extensive new data or model training. The SGDA method Qiao et al. 2023) introduce adaptive shift parameters to mitigate domain shifts and propose pseudo-labeling of unlabeled nodes to alleviate label scarcity. (Zou et al. (202T) proposes to transfer features from the previous network to the next one in the dynamic community detection problem. [Simchowitz et al. (2023) work on combinatorial distribution shift for matrix completion, where only some rows and columns are given. A similar setting is used for link prediction in egocentrically sampled networks in Wu et al. (2018). Zhu et al. (2021) train graph neural network for transfer based on an ego-graph-bart
loss function. Learning from observations of the full network and additional information from game played on the network Leng al. (2020); Rossi et al. (2022). Wu et al. (2024) study graph transfer learning for node regression in the Gaussian process setting, where the source and target networks are fully observed.
Levin et al. (2022) proposes an inference method from multiple networks all with the same mean but different variances. While our work is related, we do not assume E[P;y] = [[[uy]- Cao et al. (2010) do joint link prediction on a collection of networks with the same link function but different parameters.
Another line of related but different work deals with multiplex networks (Lee et al.; 2014 2015
lacovacci and Bianconi 2016 Cozzo et al. 2018) and dynamic networks Sarkar and Moore (2055) ;
Kim et al. (2018); Sewell and Chen (015): ,; Sarkar al. (2012): Chang et al. (2024)/Wang Wang al. (2023). )
One can think of transfer learning in clustering as clustering with side information. Prior works
consider stochastic block models with noisy label information (Mossel and Xu 2016 Mazumdar and
Saha 201 7a) or oracle access to the latent structure (Mazumdar and Saha (017b).
Notation. We use lowercase letters o, b, c denote (real) scalars, boldface a. y. denote vectors, and uppercase A, B, C' to denote matrices, Let aVb == max(a, b) and a/b == min b). For integer n > 0, let [n] == {1, (1,2,..., n1). For a subset S C [m] and A E RRxx, let A A|S,S] < RR|SS be the principal submatrix with row and column indices in S. We denote the Eg vector norm || = ||m||2-
dot product as (xt y), and Frobenius norm as |||]] = ||A|| For functions f.g N + IR we let S. g denote = O(g) and Z g denote f = ((g)). All asymptotics OC-), ((), S0)), w-) are with
respect to no unless specified otherwise.
2 Estimating Latent Variable Models with Rankings
In this section, we present computationally efficient transfer learning algorithm for latent variable models. Algorithm [leams the local structure of P based on graph distances (Definition I.2). For

---

Algorithm Q E-Esimmation for Latent Variable Models
1: Input: Ap E {0, (0,1)=x", Aq {0, 100,1,e
x , C [n] s.t. |S| nQQ.
2: Initialize Q R=x" be all zeroes.
3: For all i, all # i, compute graph distances:
dAp (i.j) = (l(e -x)- - ege
4: Fix bandwidth (0, 1) based on 71, nQQ
5:
for i= 1 to do
6:
Let (h)) S be bottom h-quaatile of S with respect to d (),
7:
if S then
8:
Update T: (h) T: (h)
9: end if
end for
11:
for = 2 to do
for 1 J < do
Compute Qú = Q3 by averaging:
Qis [ (()))
1
Σ
Σ
Aqirs
rET," (l) sET," "
14: end for
15: end for
16: Return Q
each node i of P. it ranks the nodes in S with respect to the graph distance di( For most nodes i [ni, none of the edges incident or j are observed in Q. Therefore, we estimate Qiy by using the edge information about nodes r, E S such that dp r) and dp(j, s) are small.
Formally, we consider a model as in Eq. [ with compact latent space C IRd and latent variables sampled i.i.d. from the normalized Lebesgue measure on X. We set X' [0, 1]4 without loss of generality and assume that functions f X X + [0, are a-Holder-smooth.
Definition 2.1. Let f X x X' + R and a > O. We say f is a- H-Hölder-smooth if there exists Ca > 0
such that for all x, x', y E X.
gE. f
a. Ms
Σ
x y)
(a' v) S Call =x IgAl
0 ... Ond
0
0
KEN E,
To exclude degenerate cases where a node may not have enough neighbors in latent space, require the following assumption.
Assumption 2.2 (Assumption 3.2 of Mao et al. (2021) ). Let G be graph æ...... Fn- There exist 02 > C1 > 0 and An = o(1) such that for all x;, Tjj.
1 J dall,,) 02||a, æz [
|a:;
2,,1aan A.
The second inequality follows directly from Hölder-smoothness, and the first is shown to hold for e.g.
Generalized Random Dot Product Graphs, among others (Mao et al. 2021).
We establish the rate of estimation for Algorithm below.
Theorem 2.3. Let Q be as in Algorithum Let fe be a-Hölder-smooth and fo be 3-Hölder- smooth for hn cv absolute constant C such that
>> O, and let c be an absolute constant. Suppose (P, Q) satisfy Definition 1.3 at
log na and P satisfies Assumption no
2.2 with A, O((
[ng v 241
Then there exists
nq
S61 T
#x1 2N
d
log
P
Q
Q12
<
2 1 11-10
no C
no
5

---

To parse Theorem 2.3 consider the effect of various parameter choices. First, observe that our log ai then
upper bound scales quite slowly with Even if is superpolynomial in nig. e.g. no log n ((log n²)²) n
o(1) so the overall effect on the error is dominated by the no term.
Second, the bound is worse in large dimensions, and scales exponentially in 3. This kind of scaling also occurs in minimax lower bounds for nonparametric regression (Tsybakov 2009), and upper bounds for smooth graphon estimation (Xul 2018). However, we caution that nonparametric regression can be quite different from network estimation; it would be very interesting to know the dependence of dimension on minimax lower bounds for network estimation, but to the best of our knowledge this is open problem. Finally notice that greater smoothness 3 results in smaller
error, up to = 1, exactly as in (Gao et al. 2015; Klopp et al. 2017 Xu 2018
Minimax Rates for Stochastic Block Models
In this section, will show matching lower and upper bounds for very structured class of latent variable models, namely, Stochastic Block Models (SBMs).
Definition 3.1 (SBM). Let P E [0, 1mxxn_ We say P is an (n, k)-SBM if there exist B E [o, 1] 1| and 2 [m] [k] such that for all i. P.j B=(()=()) We refer to 2- ({5)) community E [k].
We first state a minimax lower bound, proved via Fano's method.
Theorem 3.2 (Minimax Lower Bound for SBMs). Let kp 2 ki with li dividing kp. Let F be the family of pairs (P. Q) where P is (n, -SBM, Q is an (n, -SB, and (P, Q) satisfy Definition at at hn = 1/kp. Moreover, suppose C [n] is restricted to contain an equal number of nodes from communities 1, 1,2, ........p. kpp of P. Then the minimax rate of estimation is:
2
inf sup E @ej0.1]axn (P.Q)EF
Q2 - Q11
QQQ
Note that Definition 1.3 at h, - 1/kp implies that the true community structure of coarsens that of P. The condition that kig divides kp is merely technical one that we assume for simplicity.
We remark that minimax lower bounds for smooth graphon estimation are established by first showing lower bounds for SBMs, and then constructing a graphon with the same block structure using smooth expect that Theorem 3.2 can also be extended to the
mollifiers (Gao et al., 2015). Therefore, graphon setting, using the same techniques. However, sharp lower bounds for other classes such as
Random Dot Product Graphs will likely require different techniques (Xie and Xu 2020 Yan and
Levin 2023).
Remark 3.3 (Clustering Regime). In Appendix A.4 we also prove minimax lower bound of log kq
na
in the regime where the error of recovering the true clustering dominates. This matches the rate of
Gao et al. 2015), but for estimating all n² entries of Q, rather than just the ni observed entries.
Theorem suggests that a very simple algorithm might achieve the minimax rate. Namely, use both Ap, Aq to learn communities, and then use only AQ to learn inter-community edge probabilities. If (P,Q) are the nonparametric regime where regression error dominates clustering error (called the weak consistency or almost exact recovery regime), then the overall error will hopefully match the minimax rate.
We formalize this approach in Algorithm 2, and prove that it does achieve the minimax eтrоr rate in the weak consistency regime. To this end, we define the signal-to-noiss ratio of an SBM with parameter B E [0, k as follows:
9 vp(1 ②)
where p = min; Bic q maxi4j Bij- Proposition 3.4 (Error Rate of Algorithm 2
Suppose P. [0, 1p are (n, (n,kr), (n, kQ)-
SBMs with minimum community sizes n n mini respectively. Suppose also that (P, Q) satisfy
(Q)

---

Algorithm 2 Q Q-Esimmation for Stochastic Block Models
1: Input: Ap E {0, 1 AQ {0, 1 C [n] s.t. |S| =QQ
2: Estimate clusterings Zp [0,1)=xkr, Zq E {0, 1 x using Chen et al. (2014) on Ap, Aq
respectively.
3: Let We R be diagonal with
Wo = (1 Zoe
4: Initialize î E {0, 12 to zeroes.
5: for E S do
6: je E [kp]. E [kt] be the unique column indices at whichrow of 2p, Za respectively
nonzero.
7: Let lijr.ja
8: end for
9: Let BQ E [0, 11kkxxke be the block-average:
Bq = Wo
return @: 2plIBo 11
Definition 1.3 hn minn/
(P) n.
Then if the signal-to-noise ratios are such that: sp
C(-VR
C² 1.
log (m)
and sQ 2 0( gg
log" (mg] for large enough constant C > 0, A.Agorithmm
returns Q
min(()) (2)
(Q)
such that
log(n (2)
Q
Q1 S
Q
0 )
n2
n
nQ
4 Experiments
In this section, Algorithm against several classes of simulated and real-world networks. We quantile cutoff of hn
Iog ng for Algorithm in all experiments. nq
Baselines. To the best of our knowledge, our exact transfer formulation has not been considered before in the literature. Therefore, we implement two algorithms as alternatives to Algorithm D
(1) Algorithm Given Ar 1)mm,, Aq {0,1)*o xna, let kp [/ Compute spectral clusterings 2p, Za with kp, ky clusters respectively. Let Jg E (0.1)m is such that Jsúúj if and only if j and S. The projection îî R solves the least- squares problem m || 2 2g 1| We compute the îī differently from steps 4-7 in Algorithm to account for cases where Q not coarsening of P. When Q is true coarsening of this reduces the procedure in steps 4-7. Given 2p, we return Q as in Algorithm 2
[vno]=
(2) Oracle. Suppose that an oracle can access data for Q on all n > no nodes as follows. Fix probability p (0, 1). The oracle is given symmetric A/2 {0, 1) jaxn with independent entries following mixture distribution. For all i, [n] with let X Bernoull(p)) and Yij ~ Bernoulli( Q (x; æ;)). Then:
Alass LEsJeSYY +(1 LEE.EES))))) (11-),) + X1
Y,)))
Given A/g, the oracle returns the estimate from Universal Singular Value Thresholding on Alp Chatterjee 2015). As p > the error will approach ( for 3-smooth network on on d-dimensional latent variables [Xu 2018), so the oracle will outperform any transfer algorithm.
7

---

Source
Target
Alg. !
Alg.
Oracle
Oracle
Oracle
(p = 0.1)
(p = 0.3)
(p = 0.5)
Noisy-
Noisy-
0.7473
1.3761 +
0,9556 +
2.2568 +
4.2212 +
MMSB
MMSB
0.0648
1.1586
0.0633
0.3107
0.2825
(0.7, 0.3, 0.01)
(0.9, 0.1, 0.01)
0.1-Smooth
S.5-Shoth
1.7656
4.5033 + 1.5613
0.5016 =
2.4423
5.7774 + 0.7126
Graphon
Graphon
0.7494
0.0562
0.4574
I
R Latent(1.0)
0.5744
1.1773 +
0.7715
2.1822
4.3335
+ 0.3476
L2tent(2.5)
0.1086
1.0481
0.0456
0.2741
Table I: Comparison of different algorithms on simulated networks. Each cell reports ğ + 26 of the mean-squared error over 50 independent trials. Error numbers are all scaled by 1e2 for case of reading. Bold: Best algorithm. Emphasis: Second-best algorithm.
Simulations. We first test on several classes of simulated networks. For no = 50, 200, we run 50 independent trials for each setting. We report results for each setting in Table [ and visualize estimates for stylized examples in Figure
At a glance, Figure shows that Algorithms and 2 both work well on Stochastic Block Models (first row), that only Algorithm works well on graphons (second and third rows), and that the Oracle performs well in all cases.
Smooth Graphons. The latent space is X' = [0, 1]. We consider graphons of the form (3 =
+" where P. Q have different y. We denote this the 7-Smooth Graphon.
Mixed-Membersshe Stochastic Block Model. Set ky [v k mmo] The latent space X the probability simplex X AAp far [0, 1)r >; 24 = R&r The latent variables
21, -1..... Fy iid-Dirichlet distributed with equal weights kp
Then P.j a!. Bræz and
Qi = (Tx;;)) ) (a;)( for connectivity matrices Bp E [0, 1 Bo E [0, 10. xke, and projection II Akp Dig for fixed subset of [kp]] For parameters a, a, E [0, 1] generate B E j0, 1] 1 by sampling E E Uniform(-c, c jxk and set clip((a - b)] + b11 E, 1). We call this Noisy-MMSB(C (a, b, c).
Latent Distance Model. The latent space is the unit sphere X = Sd-1 c Rd For scale parameter 0, we call fa y) exp(-s|p
y112) the (Lttnntet(s) model.
Discussion. When the latent dimension is larger than (the Noisy MMSB and Latent Variable Models), our Algorithm is better than both Algorithm| 2 and the Oracle with
0.1. Note that 0.06 unbiased edge observations from Q, while the Oracle with
Algorithms and
use
p 0.1 observes (1
0.9 unbiased edge observations in expectation.
World Data. Next, we test on two classes of real-world networks. We summarize our dataset characteristics in Table See Appendix [ for further details.
Table 2: Dataset Characteristics
Name
n
Median Degree
Type
BiGG Model iWFL1372
251
15.00
Source
BiGG Model iPC815
251
12.00
Source
BiGG Model iJN1463
251
14.00
Target
EMAIL-EU Days 1-80
1005
6.92
Source
EMAIL-EE EU Days 81-160
1005
7.35
Target
EMAIL-EU Days 561-640
1005
7.66
Target
Transfer Across Species in Metabolic Networks. For a fixed organism, metabolic network has node for each metabolite, and an edge exists if and only if two metabolites co-occur in a metabolic

---

Source
Algorithm 1
Algorithm 2
Oracle (p 0.1)
1.0
0.5
0.0
1.0
0.5
0.0
1.0
0.5
0.0
Figure 1: Comparison algorithms on three source-target pairs (n = 2000, no = 500). Each row corresponds different source/target pair (P, Q). For fixed row, the upper triangular part columns 2, 3, 4 corresponds Q for a different algorithm. The upper triangular part of column shows the true P. The lower triangular part of columns 1, 2, 3, and 4 is identical for a fixed row, and shows true Q. each heatmap, the lower triangle the target Q. Algorithm performs best when (P, Q) are SBMs (top), while Algorithm iis better for smooth graphons (2nd and 3rd rows).
reaction in that organism. We obtain the unweighted metabolic networks for multiple gram-negative bacteria from the BiGG genome-scale metabolic model dataset (King et al. 2016 Norsigian et al.) 2020). the left half Figure 2 we compare two choices source organism in estimating the network for BiGG model 463 (Pseudomonas putida). For good choice of source, Algorithm
competitive with the Oracle at p = 0.1.
Transfer Across Time in the Email Interaction Networks. We use the EMAIL- EUU interaction network between 1005 members of a European research institution across 803 days Leskoved
and Krevl (2014): Paranjape et al. (2017). The source graph Ap is the network from day 1 to z 80 (1, (0). Figure we simulate transfer with targets [81, 160) (left) and [561, 640) (right). We visualize results for arbitrary target periods; similar results hold for other targets. Unlike metabolic networks, Algorithm has comparable performance to both our Algorithm aad the oracle algorithm with (0.01, 0.05 Compared to the metabolic networks, this indicates that the email interaction networks are relatively well-approximated by SBMs, although Algorithm T is still the best.
Additional Experiments and Baseline. In Appendix B.1 present additional ablation experiments that test the dependence of Algorithms [ and 2 on all relevant parameters. We compare their performance to the Oracle baseline with 0.0 (the non-transfer setting). and an additional baseline adapted from Levin et al. (022).. We find that our Algorithms outperform this new baseline but are worse than the Oracle with p = 0.0, as expected. Further, in Appendix B.2 we test our Algorithms and original baselines on a link prediction task in the setting of Figure 2 We find that the relative
accuracy of the methods for link prediction is qualitatively similar to that of Figure 2 and the Oracle performs even better with sparsity tuning.

---

Ag.
p Motabolic Networks
Email Networks
8
8x10
2x10
2x10
MGE d.o Baal))
10"
4x10
7x100
7x110
100
150
202
-30
200
20
60
80
with 251
Ply With 251
With i 1005
with 0 1005
Figure 2: Results of network estimation real-world data. Shaded regions denote [1.99] percentile outcomes from 50 trials.
Left half. Estimating metabolic network of iJN1463 (Pseudomonas putida) with source IWFL13722 (Escherichia coli W) leftmost, and source iPC815 (Yersinia pestis) second-left. Right half. Using source data from days 1 80 of EMAIL-EU estimate target days 81 160 (third-left) and target days 561 - 640 (rightmost). Note that we use smaller values of p for the Oracle in EMAIL-EU.
Conclusion
In this paper, we study transfer learning for network estimation in latent variable models. We show that there exists an efficient Algorithm that achieves vanishing error even when nQ simpler Algorithm 2 for SBMs that achieves the minimax rate.
w(1) and
There are several interesting directions for future work.
First, we believe that Algorithm Q( ).) This is because the concentration of empirical graph distance (Algorithm line 3) requires
I works for moderately sparse networks with population edge density
expected edge density f2(n- 1122 Mao et al. (2021) It would interesting to see if a similar approach can work for edge density D( log For example, in the aforementioned paper it shown that a
variation of the graph distance of Definition 1.2 concentrates at expected edge density (233).
While is this still far from the ?2( log regime, suggests that variations the graph distance might ensure our Algorithm|] [ works for sparser graphs.
a
Second, the case of multiple sources is also interesting. We have focused on the case of one source distribution, as in Cai and Weil (202T): Cai and Pu (2024), but expect that our algorithms can be extended to multiple sources long they satisfy Definition I.3
Acknowledgments and Disclosure of Funding
thank the anonymous reviewers for their valuable feedback.
AJ and PS gratefully acknowledge NSF grants 2217069, 2019844, and DMS 2109155.
AM was supported by NSF awards 2217058 and 2133484.
SSM was partially supported by an INSPIRE research grant (DST/INSPIE//0//008800001 from the Dept. of Science and Technology, Govt. of India and a Start-Up Grant from Indian Statistical Institute.
References
Abbe. E. (2017). Community detection and stochastic block models. 1rX.
arXiv preprint
Agarwal, A., Song, Y.. Sun, W., Wang, K., Wang. M., and Zhang, (2023). Provable benefits of representational transfer in reinforcement learning. In Neu, G. and Rosasco, L., editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 2114-2187, PMLR
10

---

Airoldi, E. M., Blei, D. M., Fienberg, S. E., and Xing, E. P. (2008). Mixed membership stochastic blockmodels. Journal of Machine Learning Research, 9:1981-2014.
Aldous, D. J. (1981). Representations for partially exchangeable arrays of random variables. Journal of Mullivariate Analysis, 11:581-598.
Apostolopoulos, I. D. and Bessiana, T. (2020). Covid-19: automatic detection from x-ray images utilizing transfer learning with convolutional neural networks. Physical and Engineering Sciences in Medicine, 43:635 640.
Baranwal, M., Magner, A., Elvati, P., Saldinger, J., Violi, A., and Hero, A. O. (2020), A deep learning architecture for metabolic pathway prediction. Bioinformatics, 36(8):2547-2553.
Barberá, P., Jost, J. T., Nagler, J., Tucker, J. A., and Bonneau, R. (2015). Tweeting from left to right: Is online political communication more than an echo chamber? Psychological science, 26(10):131-1142.
Ben-David, S., Blitzer, J., Crammer, K., and Pereira, F. (2006). Analysis of representations for domain adaptation. Advances in neural information processing systems, 19.
Bickel, J. and Chen, A. (2009). A nonparametric view network models and newman-gin girvan and other modularities. Proceedings of the National Academy of Sciences, 106(50):2108-211)
Cai. T. T. and Pu, (2024). Transfer learning for nonparametric regression: Non-asymptotic minimax analysis and adaptive procedure. arXiv preprint arXiv:2401.12272
Cai, T. T. and Wei, H. (2021). Transfer learning for nonparametric classification: Minimax rate and adaptive classifier. The Annals of Statistics, 49(1).
Cao, B., Liu, N. N., and Yang, Q. (2010). Transfer learning for collective link prediction in multiple heterogenous domains. In Proceedings of the 27th international conference on machine learning (ICML-10), pages 159-166. Citeseer.
Cao, X. and Ward, M. D. (2014). Do democracies attract portfolio investment? transnational portfolio investments modeled as dynamic network. International Interactions, 40(2):216-245.
Chan, S. and Airoldi, E. (2014), A consistent histogram estimator for exchangeable graph models. In International Conference on Machine Learning, pages 208-216. PMLR.
Chang, S., Koehler, F., Qu, Z., Leskovec, J., and Ugander, J. (2024). Inferring dynamic networks from marginals with iterative proportional fitting. arXiv preprint arXiv:2402.
Chatterjee. S. (2015). Matrix estimation by universal singular value thresholding. The Annals of Statistics, pages 177-214.
Chen, Y., Sanghavi, S., and Xu, H. (2014). Improved graph clustering. IEEE Transactions on Information Theory, 60(10))6440-6455
Christensen, B. and Niclsen, J. (2000). Metabolic Network Analysis, pages 209-231. Springer Berlin Heidelberg, Berlin, Heidelberg.
Cody, T. and Beling, P. A. (2023). A systems theory of transfer learning. IEEE Systems Journal, 17(1):26-37.
Cortes, C., Mohri, M., Riley, M., and Rostamizadeh, A. (2008). Sample selection bias correction theory. In International conference on algorithmic learning theory, pages 38-53. Springer.
Cozzo, E., De Arruda, G. F., Rodrigues, F. A., and Moreno, Y. (2018). Multiplex networks: basic formalism and structural properties, volume 10. Springer.
Crammer, K., Kearns, M., and Wortman, J. (2008). Learning from multiple sources. Journal of Machine Learning Research, 98)).
Daumé, H. (2007). Frustratingly easy domain adaptation. ArXiv, abs/0907.1815.

---

Donahue, J., Jia, Y., Vinyals, O.. Hoffman, J., Zhang, N., Tzeng, E., and Darrell, T. (2014). Decaf: A deep convolutional activation feature for genenic visual recognition. In Xing, E. P. and Jebara. T., editors, Proceedings of the s1 International Conference Machine Learning. volume 32 of Proceedings of Machine Learning Research, pages 647-655, Bejing, China. PMIR.
Fan, J.. Cannistra, A., Fried, I. Lim, I., Schaffner, T., Crovella, M., Hescott, B., and Leiserson, M. D. (2019). Functional protein representations from biological networks enable diverse cross-species inference. Nucleic acids research, 47(9):e51-e5))
Gao, C., Lu. Y., and Zhou, H. H. (2015). Rate-optimal graphon estimation. The Annals of Statistics, pages 2624-2652.
Guruswami, V., Rudra, A., and Sudan, M. (2019). Essential coding theory.
Handcock, M. S., Raftery, A. E., and Tantrum, J. M. (2007). Model-based clustering for social networks. Journal of the Royal Statistical Society: Series A (Statistics in Society), 170(2):301-354
Hanneke, S. and Kpotufe, (2019).
value of target data transfer learning. Advances in Neural Information Processing Systems, 32.
Hanneke, and Kpotufe, (2022). no-free-lunch theorem for multitask learning. The Annals of Statistics, 50(6):3119-3144
Hoeffding, W. (1994). Probability inequalities for sums of bounded random variables. The collected works of Wassily Hoeffding, pages 409-426,
Hoff, P. (2007). Modeling homophily and stochastic equivalence in symmetric relational data. Advances in neural information processing systems, 20.
Hoff, P. D., Raftery, A. E., and Handeock, M. S. (2002). Latent Space Approaches Social Network Analysis. Journal of the American Statistical Association, 199460)
Holland, P. W., Laskey, K. B., and Leinhardt, S. (1983). Stochastic blockmodels: First steps. Social Networks, 5(2):109
Hoover, D. N. (1979). Relations probability spaces arrays of random variables. Institute for Advanced St.
Huang, J.-T., Li, J., Yu, D., Deng, L., and Gong, Y. (2013). Cross-language knowledge transfer using multilingual deep neural network with shared hidden layers. 2013 IEEE international conference on acoustics, speech and signal processing, pages 7304-7308. IEBE.
Huh, M., Agrawal, P., and Efros, A. A. (2016). What makes imagenet good for transfer learning? arXiv preprint arXiv: /608.0/608.080 04614.
lacovacci, J. and Bianconi, G. (2016). Extracting information from multiplex networks. Chaos: An Interdisciplinary Journal of Nonlinear Science, 26(6).
Kim, B., Lee, K. H., Xue, L., and Niu, X. (2018). review of dynamic network models with latent variables. Statistics Surveys, 12(none): 135.
Kim, H., Cosa-Linan, A., Santhanam, N., and al. (2022). Transfer learning for medical image classification: a literature review. BMC Medical Imaging, 22(1):69.
King, Z. A., Lu, J.. Dräger, A., Miller, P., Federowicz, S., Lerman, J. A., Ebrahim, A., Palsson, B. O., and Lewis, N. E. (2016). Bigg models: A platform for integrating, standardizing and sharing genome-scale models. Nucleic acids research, 44(D1):D515-D55 D522..
Klopp, O., Tsybakov, A. B., and Verzelen, N. (2017). Oracle inequalities for network models and sparse graphon estimation. Annals of Statistics, 45(1):316
Kshirsagar, M., Carbonell, J., and Mlein-Seetharaman, J. (2013). Multitask learning for host-pathogen protein interactions. Bioinformatics, 29(13):2217-1226
12

---

Lee, J.. Kim, H., Lee, J., and Yoon, S. (2017). Transfer learning for deep learning on structured data. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 31.
Lee, K.-M., Kim, J. Y., Lee, S., and Goh, K.-I. (2014). Multiplex networks. Networks of networks:
The last frontier of complexity, pages 53-72.
Lee, K.-M., Min, B., and Goh, K.-I. (2015). Towards real-world complexity: an introduction to multiplex networks. The European Physical Journal 88:1-20.
Leng, Y., Dong, X., Wu, J., and Pentland, A. (2020). Learning quadratic games on networks. In International Conference Machine Learning, pages 5820-5830. PMLR.
Leskovec, J. and Krevl, A. (2014). SNAP Datasets: Stanford large network dataset collection. http://snap. stanford... edu/data
Levin, K., Lodhia, A., and Levina, (2022). Recovering shared structure from multiple networks with unknown edge distributions. Journal of machine learning research, 23(3):1-48.
Li, L., Dannenfelser, R., Zhu, Y., Hejduk, N., Segarra, S., and Yao, V. (2022). Joint embedding of biological networks for cross-species functional alignment. bioRxiv, pages 2022-01.
Long, J., Shelhamer, E., and Darrell, T. (2015). Fully convolutional networks for semantic segmenta- tion. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3431-3440
Lovász, L. (2012). Large Networks and Graph Limits., volume 60 of Colloquium Publications. American Mathematical Society.
Mansour, Y., Mohri, M., and Rostamizadeh, A. (2009). Domain adaptation: Learning bounds and algorithms. arXiv preprint arXiv:0902.3430.
Mao, X., Chakrabarti, D., and Sarkar, P. (2021). Consistent nonparametric methods for network assisted covariate estimation. In International Conference Machine Learning, pages 7435-7446. PMLR.
Mazumdar, A. and Saha, B. (2017a). Clustering with noisy queries. Advances in Neural Information Processing Systems, 30.
Mazumdar, A. and Saha, B. (2017b). Query complexity of clustering with side information. Advances in Neural Information Processing Systems, 30.
Mossel, E. and Xu, J. (2016). Local algorithms for block models with side information. In Proceedings of the 2016 ACM Conference on Innovations Theoretical Computer Science, pages 71-80.
Mukherjee, S. S. and Chakrabarti, S. (2019). Graphon estimation from partially observed network data. arXiv preprint urXiv:1906.0000 00494..
Neyshabur, B., Sedghi, H., and Zhang, C. (2020). What is being transferred in transfer learning? In Larochelle, H., Ranzato, M., Hadsell, R.. Balcan, M., and Lin, H. editors, Advances in Neural Information Processing Systems, volume 33, pages 512-523, Curran Associates, Inc.
Norsigian, C. J., Pusarla, N., McConn, J. I.., Yurkovich, J. T., Dräger, A., Palsson, B. O., and King, Z. (2020). Bigg models 2020: multi-strain genome-scale models and expansion across the phylogenetic tree. Nucleic acids research, 48(D1):D402-4466
Othede, S. C. and Wolfe, P. J. (2014). Network histograms and universality of blockmodel approxi- mation. Proceedings of the National Academy of Sciences, 111(41):47222--777)
Paranjape, A., Benson, A. R., and Leskovee, J. (2017). Motifs in temporal networks. Proceedings of the tenth ACM international conference web search and data mining, pages 601-610.
Qiao, 7.,, Luo, X., Xiao, M., Dong, H., Zhou, Y., and Xiong, (2023). Semi-supervised domain adaptation in graph transfer learning. ArXiv, abs/2309.10773.
13

---

Ren, M., Zhang, S., and Wang, J. (2023). Consistent estimation of the number of communities via regularized network embedding. Biometries, 79(3):2404-244 2416.
Rossi, E., Monti, F., Leng, Y., Bronstein, M., and Dong, X. (2022). Learning to infer structures of network games. In International Conference Machine Learning, pages 18809-18827. PMLR.
Rubin-Delanchy, P., Cape, J., Tang, M., and Priebe, C. E. (2022). A statistical interpretation of spectral embedding: the generalised random dot product graph. Journal of the Royal Statistical Society Series B: Statistical Methodology,
Sarkar, P. Chakrabarti, D., and Jordan, M. I. (2012). Nonparametric link prediction in dynamic networks. In Proceedings of the 29th International Coference on International Conference on Machine Learning, ICML' 12, page 1897-1904, Madison, WI, USA. Omnipress.
Sarkar, P. and Moore, (2005). Dynamic social network analysis using latent space models. In Weiss, Y., Schölkopf, B., and Platt, J., editors, Advances in Neural Information Processing Systems, volume 18. MIT Press.
Sen. R., Tagore, S., and De, R. K. (2018). Asapp: Architectural similarity-bart automated pathway prediction system and its application in host-pathogen interactions. IEEE/ACM Transactions Computaaiional Biology and Bioinformatics, 17(2):006-515.
Sewell, D. K. and Chen, Y. (2015). Latent space models for dynamic networks. Journal of the american statistical association, 1106512):166--6557
Simchowitz, M., Gupta, A., and Zhang, K. (2023). Tackling combinatorial distribution shift: matrix completion perspective. In Neu, G. and Rosasco, L.,, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 Proceedings of Muchine Learning Research, pages 3356-3468. PMLR.
Sweet, T. M., Thomas, A. C., and Junker, B. W. (2013). Hierarchical network models for education research: Hierarchical latent space models. Journal of Educational and Behavioral Statistics, 38(3):295-318.
Tang, J., Lou, T., Kleinberg, J., and Wu, S. (2016). Transfer learning infer social ties across heterogeneous networks. ACM Trans. Inf. Syst., 34(2).
Trifonova, N., Kenny, A., Maxwell, D., Duplisea, D., Fernandes, J., and Tucker, A. (2015). Spatio- temporal bayesian network models with latent variables for revealing trophic dynamics and functional networks in fisheries ecology. Ecological Informatics, 30: 50:142-158.
Tripuraneni, N., Jordan, M. I., and Jin, C. (2020). On the theory of transfer learning: the importance of task diversity. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20, Red Hook, NY, USA. Curran Associates Inc.
Tsybakov, A. B. (2009). Introduction Nonparametric Estimation. Springer series in statistics. Springer, Dordrecht.
Tzeng, E., Hoffman, J.. Saenko, K., and Darrell, T. (2017a). Adversarial discriminative domain adaptation. Proceedings of the IEEE conference on computer vision and pattern recognition. pages 7167-7176.
Tzeng, E., Hoffman, J.. Saenko, K., and Darrell, T. (2017b). Adversarial discriminative domain adaptation. 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 2962-2971.
Vershynin, R. (2018). High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press.
Wang, H., Mao, Y., Sun, J., Zhang, S., Fan, Y., and Zhou, D. (2023). Dynamic transfer learning across graphs. arXiv preprint arXiv:2305. 00664.
Weiss, K. R., Khoshgoftaar, M., and Wang, (2016). survey of transfer learning. Journal of Big Data, 3:1-40.
14

---

Wu, J.. Ainsworth, L., Leakey, A., Wang, H., and He, J. (2024). Graph-structured gaussian processes for transferable graph learning. Advances in Neural Information Processing Systems, 36.
Wu, Y.J., Levina, E., and Zhu, (2018). Link prediction for egocentrically sampled networks. Journal of Computational and Graphical Statistics, 32: 1296 1319.
Xie, F. and Xu, Y. (2020). Optimal bayesian estimation for random dot product graphs. Biometrika, 107(4):875-88.
Xu, (2018). Rates convergence of spectral methods for graphon estimation. In International Conference on Machine Learning, pages 5433-5442. PMLR.
Yan, and Levin, (2023). Minimax rates for latent position estimation in the generalized random dot product graph. arXiv preprint 2rX11:2300.01142.
Yang, L., Hanneke, S., and Carbonell, J. (2013). A theory of transfer learning with applications to active learning. Machine learning, 90:161-189.
Yu, B. (1997). Assouad, fano, and cam. In Festschrift for Lucien Le Cam: research papers in probability and statistics, pages 423 435. 4 Springer.
Zhang. Y., Levina, E., and Zhu, J. (2017). Estimating network edge probabilities by neighbourhood smoothing. Biometrika, 104(4):771-783.
Zhu, Q. Yang, C., Xu, Y., Wang, H., Zhang, C., and Han, J. (2021). Transfer learning of graph neural networks with ego-graph information maximization. Advances Neural Information Processing Systems, 34:1766-1779)
Zhuang, F. Qi Z., Duan, K., Xi, D., Zhu, Y., Zhu, H., Xiong, H., and He, Q. (2019). A comprehensive survey on transfer learning. Proceedings of the IEEE, 109:43-76.
Zou, J., Lin, F,, Gao, S., Deng, G., Zeng, W., and Alterovitz, G. (2021). Transfer learning based multi- objective genetic algorithm for dynamic community detection, arXiv preprint arXiv:2109. 151366
15

---

A Proofs
A.1 Preliminaries
Recall Hoeffding's inequality.
Lemma A.1 (Hoeftding (1944). Let XI,..., be independent random variables such that
S X; S by almost surely for all i E 'n]. Then
-11
Σ (x, E(X.)) 2 s 2exp
R (b; a;)
also need Bernstein's 's inequality.
Lemma A.2 (Bernstein's 's Inequality), Let Xi...., Xn be independent mean-zer random variables with X, for all and 5. Then
2((1 11) ) $ 2exp
-nt?
(-
(- nt?
P
X 2
s
2exp
A.2 Proof of Theorem
2.3
Throughout this section, let X' 11 and n:: X - [0, 1] be the normalized Lebesgue measure.
We require the following Lemmata.
Lemma A.3. Let E (0, 1) and μ (0, be the normalized Lebesgue measure. Then for all ((Ball(z,2u) nx) v() n.2).
x E X,
Proof. Recall = [0, Fix X, U. Note that ((Ball(æ,, v) X) is smallest when æ is vertex of the hypereube; therefore take x (0, 1]d without loss of generality. Then, note that for each z E Ball(æ, v) nX, we find (2 1) other points z' E Ball(æ, v) \ X by reflecting subsets of coordinates of about æ. There are 2d 1 such nonempty subsets of coordinates. This shows
that yu( (Ball( v) n X) 2 ((Bll(( a. 22) for all æ. Since ((Ball(ær, u)) = vd, the conclusion follows.
We will repeatedly make use of the concentration of latent positions.
Lemma A.4 (Latent Concentration). Let X' [o, 1]d and μ denote the normalized Lebesgue measure on X. Suppose 21..... In ~ X are sampled iid and uniformly at random from μ.. Fix some T C X such that ((T) v. Then
log n
P
on - Ki in] x, ETII 2 10
S n -110
Proof. Let X; be an indicator variable that equals if E T and zero otherwise. Notice the X; are iid and bounded within [0, 1]. Moreover, Σ, E X = (T)) Therefore by Hoeffding's inequality, for any / > 0.
22t
PP[unn [m] : TTI 2 t $ 2 exx
Setting t = 1 Jog gives the result.
16

---

Corollary A.5. Lete O. For i E [n] let c > 0 be o = supfu > 0: [ v) nx) S c.
Let T; == Ball(a,, <) R. Let (S) Kj E : xy Ti denote the number of members of
landing in Tg Then
log n nq 2 21-11 -
P Vie : (u(()) nool & 1
Proof. Notice that each T; has Lebesgue measure by definition. Therefore [[], ngc. Since has ni members, setting 1 logn over all E [n]] gives the conclusion.
in the statement of Lemma A.4 A.4 and taking union bound nq
We will decompose the error of Algorithm[ parts.
Proposition A.6. Let Q E [0, 1|aXn be the estimator from Algorithm Then
1 n QQ - Q
Σ (Js(i.)) + Jn(i,)))
(.E(()
where Js. JB are the smoothing and Bernoulli errors respectively:
2 Qi Qrs
Js(i.))
[T. !T,1
rEZ;,sET)
2
Jn(i.)) = | 2 |r,
Σ PET;
Drs Aqurs
Controlling the Bernoulli errors is relatively straightforward.
Proposition A.7. Let h be the bundwidth of Algorithm The Bernoulli error is at most O with probability 2 1 - n where m n²
log m
Proof. Fix j [m]. We will bound the maximum Bernoulii error Js(i.j) over i.j, which suffices to bound the average. Let m = [Tp] [Tyl. We want to bound:
Σ
(Qra AQuss)
[T)
rET;,eET;
Notice each summand is bounded within + m
+
Bernstein's inequality gives:
P [
1
Σ
Qr+ AQura) 82 < 2exp(-0.5t
[T.
[Tg
rET,,STT
Setting CV loga for large enough C O(1), a union bound tells that with probability
m -8, the Bernoulli error is bounded by t?.
Corollary A.8. The Bernoulli error is at most O log n4
with probability 2
TiQ -4
ng
The rest of this section is devoted bounded the smoothing errors (i.i..).
17

---

A.2.1 Latent Distance to Graph Distance
We claim that if nodes are close in the latent space then they are close in graph distance. Proposition A.9. Suppose that ||= æz and Q is B-smooth. Then do(i,r) (3
Proof. We the smoothness of Q. By definition there exists C3 0 such that Qks Qkr S CBllæ x, |eeel Therefore,
do(i,r)=
Σ
109) (r9)
tirr
Qu1(Qs: - QQm)) )²
Σ tirr kE(N)
Σ
Pi Q3e
1Fi, KE|N]
n C2e ((BAL)
We can now bound the minimum sizes of the neighborhoods using the concentration of latent positions and the smoothness of the graphon.
Lemma A.10 Vershynin (0118). The volume of ball of radius r > O in Rd is
Vnd r(d/241)" r" where
I(+) is the I function.
Proposition A.11. Let C. (T(ş + 1)) Let Co. C" be constants. uf 2 C Caly for large enough constant > 0, and gn. Co (v,)2(811), then with probability 2 1 -6 for all i E [n] the neighhorhood size is do(i, S gn 11 2 C'noy log
loRn )1/d
ne
Proof. Fix i E [n]] and Un > 0. Let 6; denote the Lebesgue measure of Ball( v.)) n X. By (0.5//mm
Lemma A.3 and Lemma A.10 for all i, 6 2Cas
(
y Let min.e[n] 44-
Ca
By Corollary
members j of S such that < Un- A union bound over i gives the result simultaneously for all i with probability
A.5
with probability 2 1 - n there are niee
C
log
nn
| Øt
6
From Proposition
A.9 it follows that for all i E [n).
log n nQ
(re S: do(i,r) s
2 nge 10,
Choosing Un 2 C Ca(( log ng
मे for large enough C > 0 gives the conclusion.
A.2.2 Graph Distance Concentration
Next, we show that the empirical graph distance concentrates to the population distance.
Proposition A.12. For any arbitrary symmetric P E [0, 1|,,,, we have, for all i, simultaneously with probability at least 2 1 - O(n 8), that
Id (i. dr(i,j) < Onn2n(1n10)) log n) + O Vlogn) n).
18

---

Proof. Fix i.j. Let Ciy == (Ap)ay- By Mao et al.
2021 A.1, we have Ci₁ = (P²):s + Eg for an
eπror term by such that P [tty I 10 n log n
2 n Then.
Id dp((.j)l= =
Σ
((Cs (Cp))-jjo)+ --o))- ((P)) - (P²))
Σ tii
(tie + tzt)² 2(1ie tze)(( - (12))e)
< O log n) +0 (VVnlgg ((P2) - (P2)
Finally, notice that all entries of p2 are of size Onn) so the conclusion follows.
Finally, we will show that taking the restriction of the graph distance T." to nodes in C [n]] does not incur too much error
O(1) Then there exists a constant C such that if ho 2 2C Tog
Proposition A.13. Suppose nQQ
ng
A., then for all i,r simultaneously, r E TAAP (ho) implies E T." (h2) for some h2 ((h) with probubility 2 On.-)).
Proof. Let us introduce the notation T... (h) to denote the bottom h-quantile of [dp(i,]) j E S}. In this notation, T:rr (h) = Ap (h) since we restrict the quantile to nodes in S. From
Proposition A.12 and Assumption 2.2 we know that if 2 ng then for ho S h1 20 log An we have T: (ho) S T.P.s (h1) simultaneously for remains to compare T.P (h1) with T." (h2) for some h2.
"
[n]] with probability 2 O(n $).
We claim that l22 2 30
log no then p|v TTP ns| 2 l2nQ - 3 nq log no) 2 1 11-00 ((1a²). To
ng
see this, fix E [n]] and consider (h2). For j S, let X2 be the indicator variable:
{
E
X,
otherwise.
Notice that (h2) ns| =jees Xj. By Hoeffding's inequality, since EE X,] = h2ng and (h2)
|X /2/ < for all j. we have
|| (he) hamo 3//n logn 2exp (- 6 log n n
< 2n -6
Taking a union bound over all i E [n] shows the claim holds with probability Therefore we set h2 < h2 3.1
2 O(n
/ /log then j E T. implies j j (h2)) no
The conclusion follows with C 24
log r log
O())
The ranking condition (Definition 1.3 then allows us to translate between graph distances in Ap and Q.
Corollary A.14. Suppose that Definition 1.3 holds for (P, at ht, =cV log Bi no enough constant e > 0. Suppose no S n S nQ O()) Then for >> hn and r E T.AP (h), it follows that r E T. (T.((h)) (ha) for some hy = Ohh). The statement holds simultaneously for all i, with probability
+ Ano for large
> 1 -1 10n0nn O).
19

---

A.2.3 Control of Smoothing Error
We will decompose smoothing error into sum of two terms called Es,1 and Es,2- The control of Es,1 relatively straightforward.
Lemma A.15. The total smoothing error can be bounded with two terms:
2
Js(i, S Es, Es,2,
112
where
C
Es,1 =
max *ET
[Q((e ex)1
n.
Es.2 ==
E
Σ
Σ
(Orj - Qra)?
n
T
iE m]
+ET: jE[n] SET,
Proof. Note that
2
Js(i,
Σ
E
Σ
Qij -Crs)
Prs) )
n
n
T:
2
TT 2
A.jE(n)
rETT,
2
1
2
Σ
(Qis -Qr)) + +Qri Qra)²
71
n
|T:
[Tp
iE|n]
jE(m)
PET,,NET,
4
(Qu Qry)² Σ Σ (Orj Qre)²) }
Σ
T
rET:
rET, sET,
The second inner summand precise Es,,. For És,1, notice that [Til = [Til = 1(nQ - 1) by definition. Therefore
Σ T
Σ (Qu - Qr,)²= h(nq - 1) PET: rET:
ΣΣ 0,,)² max
(I(e= @1) L
rEf,
We can now bound Es,1 in terms of graph distances.
Lemma A.16. The smoothing error term Es,1 can be bounded as follows:
Es.1 S
2 max TETT)
dol(ir)) + Vn
2c
for some constant с O.
Proof. Fix i E [n] and r E T,. We have
[[Q(e, - -0) s |le, - e,1221100 Doolall00Q((e--- - e,)12
$ <e -4,1l2
Now will pass graph distances. Let Cab ((Q2) aat) for a, b [n]. Notice that [[Q -,)ll2 = / ddg (i,r) + Gir Cyi. Moreover, v /eir + eri S 2/7 since the entries of Q2 individually bounded by (n). The conclusion follows.
Li
Proposition A.17. Suppose An O(v
log
Let Ca be the constant of Proposition A.11 Then if
ng
the bandwidth of Algorithm is hn C Fs,11 is at most
Log
for constant C O(1), then the smoothing error
ni
log nQ no
Es1 C20.811
for some C2 O1),, with probability 2 1- O(n
20

---

Proof. Fix E [n] and (TAn(hn)) (hn)). By Corollary A.14 hn 2 C. log An for large enough
constant C > 0, then there exists constant C2 > 0 such that the following holds. With probability 2 O for all [n] and 8, r E T,0 (C2h,).
Let Un CCaly
log 1/d for Ca as in Proposition A.11 and C > large enough constant. Then n0
by Proposition A.11 the of 8 such that (i, S Co (v,) ((((1)) has size at least The statement holds for all simultaneously with probability at least - Onn-9)
Canay
log
Therefore for all i [n) and E TTAP (ha), have
do(i,r) S
(2(31))
for some Co: C3 = 0(1), with probability 2 1 - (n By Lemma A.16 we conclude that Es,1 bounded by 20 2 with the same probability.
A.2.4 Control of the Second Smoothing Error
In this section, we show that the second smoothing error can be controlled in terms of Es, We will need track the following quantity.
Definition A.18 (Membership Count). For E S and bandwidth h, distance cutoff the P- neighborhood count of r is (p((r) = [ [n] : e (h, e)
In words, (r) counts the number of nodes j E [n] such that lands the neighborhood of in our algorithm. While know that (T) S hmq always, simply applying the pigeonhole principle gives too weak of a bound on membership counts. The base case is that there may be a "hub" node lands in 7." (h) for all We will show that there can be no such hub node.
Supposing that we can control of the empirical count Ap we show that the smoothing error can be bounded.
Proposition A.19, Let hn be the bandwidth. Then
Es,1 hnn
Es.2 S0
max( (r)). rE(m]
Proof. Rearranging terms, we have
Esa n2l1222g
1
Σ
(Qrj Qrs)²
rET,
Σ
WAP (r)
((ri Qra)²
n2212nn rES
Jis
nQ
E rES
(Ap
E(Ori Qr.)²
n2h2nzz
1.8
nQ
E rE[m]
Ap
E(rr -ra))
n
T
3,8
where the last step follows because j, do not depend on i, and because S C [ni] is chosen uniformly random. Now, will control the expectation by passing
sum, which is handled by Es,1-
E relm]
AA (r) Σ (2rs - 2ro)²
S max re(n]
Σ Σ jE(mi
[Q(e, - e.)
71
3.8
SET,
Recall that n² n2 Ω
Σ E
[1Q(e, e3)1
Hence we conclude that
jElnl NET;
Es.1
Es.2 S 50
-mx Ap (r)). rE(n)
hn
21

---

We therefore must show that max VAr (r) I (hm) with high probability. rES
Proposition A.20 (Population Version). Suppose Assumption 2.2 holds for P with e₁ < c2 and
An -O(( [os / Then if S CV Jogn for large enough constant C then we have ng
na
max ()((r & (hm) with probability at least - O(" re8
1/d
Proof. Fix r E S. Let Ca be as in Proposition A.11 Suppose that c = Ca(C + 10)
log nq ng
and
h CV log logne na Now, we will claim that for large enough constant > 0, that ( is at most the na size of Ball(x,, cc) n (.1,...,, Z.
Suppose that > O is large enough constant. Now suppose that æy is such that || ærll 2 cc. can lower bound the graph distance using Assumption 2.2 as:
dp(r.)) |I(e, e,) e,e,
e 1 enn (ec)
( 2()
An
On the other hand, suppose that i S is such that ||æ;; - æzl c. Then dp(i,j) Can (((n1)
log /logne 1/d
by Proposition A.9 Therefore since Ca(C + +10
and An 0(( 0((2080))) ) vv for ng
large enough C 0 we have
dr(r,)) |1(,,- ez, = e,ey -0cc)c n² (ec)) (cc)2(an1)
Then, if we choose > 0 such that (((a1))
202 then d < dr(r,j).
A.5 simultaneously for all i E [n)] there are at least hiq Next, from our choices of h, c, by Corollary
nodes in S that have distance < in latent space from with probablity 2 1 1
Therefore, if 2r & Bal cc) n (æi,..., Fn then r (h). This implies that shr(r) S [Ball( 2ce) n (æI...., x. We can bound the size of this ball with Lemma A.4 Notice the Lebesgue measure of Ball( 2ce) n [0, 1] is at most (Ace )d. Therefore, since æ; are chosen iid from the Lebesgue measure on X, with probability at least 2 On 10), we have
1 Ball( 2ce) n fæ1..... xn 2cr + 100 n
log
n
The right-hand side is bounded by O(h) if no. Taking a union bound over all r E S gives the conclusion.
We conclude with the desired upper bound.
Proposition A.21 (Bound on A (r)). Suppose Assumption 2.2 holds for with ei < 02 and A, =0(( Jog Hv=a)). ). Then if S Cov/ log no for small enough constant Co, then we have no
TiQ max v (r) < O(h) with probability at least 1 ((
Proof. By Proposition A.12 with probability at least 1 - O(n="), we have for all E S, [n] simultaneously that
(An(r.)) 2 dp(r. 0 Vlogn)
2 0( (1
Similarly, (r.)) < (1+ (1+0 )dr((,.)) We conclude that (r) s (v)(() O(hn) with
probability 1 -((p.))
22

---

A.2.5 Overall Error
We can bound Ca = r(2 + 1)1/d with the elementary inequality.
Lemma A.22. Let Ca == r(g + 1) Then Ca S dd/2.
Proof of Theorem 2.3
By Proposition A.21 and Prop A. 19
we have that Es,1 S ((E,1) with
probability least 1 O(ra"). Therefore by Proposition A.17
2Ai 22
P Es.1 + Es,2 o 0
log n nQ
CaAI
2 1 - 2(
By Lemma A.22
Ca S dd22. Finally, by Corollary
A.8 the Bernoulli error is bounded by
O
log nQ
with probability 2 O( Applying union bound over the two kinds of error
and Lemma A.15 gives the result.
A.3 Proof of Theorem 3.2
Recall the Gilbert- Varshamov code (Guruswami al. 2019).
Theorem A.23 (GilbertVVrshammov)
Varshamov). Let 2 be prime power. For 0 < there exists
e-balanced code C C F with rate ()(2nn).
We will use the following version of Fano's inequality.
Theorem A.24 (Generalized Fano Method, Yu (1997)) Let P be a family of probability measures, map that extracts the parameters of interest. For
(D, d) a pseudo-metric space, and P distinguished P E P, let X ~ P be the data and 0 = 0(X) be estimator for O(P).
Let 2 2 and P, C C be a finite hypothesis class of size Let or Br >> O be such that for all i and all P., Pj E P..
(O(P.), 2 azi KL(P,, P5) B,.
Then
max Er, [d((()))(P3)) 1 B, + log 2 jE(r]
log r
Definition A.25 (Relative Hamming Distance). For x. y E {0, 10", m we define their relative Ham- ming distance as follows:
d (x, y) = Hi [m] : # vill.
We will need the following construction of coupled codes.
Proposition A.26. Let mp, mQ 2 2 and mQ divide mp, There exists a code C. {0, 1m and
projection map 11 {0, mpmp + {0, 1mm such that if C" {ll(w) E C} then O' is code
with relative Hamming distance 2(1). Moreover, |C| = CC' > 20.1mg
Throughout the proof, will identify the community assignment function [n] [k] of SBM (Definition 3.1 with the matrix Z E {0, 1) jank where Zij = 1 if and only if =(i)
Proof. Begin with a Gilbert- Varbbrr- code B C {0, 11me as in Theorem A.23 We can "lift" B
] code on (0, 1 mm simply by concatenation. If w B, then the corresponding w' E C just
w' = (w, w...., w) E {0, 1 Jimp. Let II; : {0, 1 + {0, 1mmm simply select the first mQ bits of word. It clear that
(Il(w) w E CJ, so are done.
Now are ready to prove Theorem 3.2
23

---

Proof of Theorem 3.2 Let mp (2). ma (m2) and m mp. Let C' C {0, 1mmp be the code and IT : {0. 1 {0. 1 jime the projection map of Prop A.26 For each w E C, we construct a pair of SBMs Pw, Qw E _2=x" follows.
Each Pw: Qu a stochastic block model with kp, ko classes respectively. All the Par share the same assigned to
community structure, namely the lexicographic assignment where nodes 1,2,..., community and on. Similarly all the Qu share the same lexicographic community structure with nodes 1, 1..,.... ko {0, 1 1)=x6p, Zq E {0, 1] jaxka, such that for all w C, there exist Aw RRPxEP, Bw R&q xkg with
x assigned to community 1, and so on. Therefore, there are fixed Zp e
Pw ZpA 4pp Qu Zo Brr L22
The Aw, Bw are defined as follows. i E [Kp] and j² E [Ko] be such that < and i' < Since mp (tr)) and mQ (k2), we can identify (i.j) and (i) with indices of [mp], [mq] respectively. Then for fixed 8p, ôQ > 0, the edge connectivity probabilities are
1/2 (1, = Aw(j.i)
if waj 0,
1122 + 8p if Wij = 1;
Bi B') = [1/2 if f(w)ey O,
0/ ll 1.
We can set the diagonals of Aw, Bw to be 1/2 as well.
Next, let P. be family of |C| probability measures. For fixed w E C, the corresponding measure the distribution over data (Ap, Aq) E {0, 1,mXa x (0, 11m1xnn sampled from (Pw. Qu (S, S]). Note that we restrict S to be fixed subset of [n]]
Next, let ((ww Qw)) Q and let d(O((Pw, Qw)), ((P)), Qw = 1 1 -ow ll.. We will show that for all w, w/ with & w',
KL((Pws Qw), (Pw's Qw < KL Pwr) KL(Q Qwi)
$ 0(n28 + 0z)
B
d((Pu, (Pw, = - 11 - Qw
2 ((62)
=.
For the 3 claim, by Proposition 4.2 of Gao et al. 20155). if 6 dQ E (0, 1/41, we have
KL((Pan Qw), (Par, Qw)) < KL(P,m.. m: Pw)) + KL(Q Qur)
S
Σ (i, Pwr (w. (2,5))² + (i.
Next, notice that (i. + Awd (i,5) if and only if wij # w/y. Then for distinct w, w' E C, have du (. w') = ((mp), so
n² Pw S88 du (w, w²)
kp
Σ A.j
I spo2
kR
2
The bound for Qu is similar, so this verifies the claim.
Similarly, for the a claim, notice that
1 v B (dd)(((w) (T(w), ((w")) 2
8Q (T[w), M(w").
1 Qw 1. 2 ki n
ko
24

---

By Prop A.26 dæ (T) (w)) Q(mm) = (2(k)). Therefore a - (((2)).
Next, by Prop A.27 the pair (Pw, Qw) satisfies Definition 1.3 for all to E C. Moreover, log |C| 2
0.1mq by Prop A.26
Combining these results, by Theorem A.24 the overall lower bound is
inf sup
-1
Qwwlu 2 -QQ-Qule
3 + log
Q w
0.1 0.1(
30m203 k2
30m 0
8Q
o(1)
22
QQ
If we choose 8p 0.01( [2) and dạ
0.01
kiz then na
1
inf sup
12 i m n²
Qw 1 2 62
niQ
Note that kq S no n, so ôp, (0,1/4) as desired.
Proposition A.27. If h = min + Fg then for all w C, the pair (Pws Qw) satisfies Defn at hn-
1.3
Proof. Consider h hn and some node E [n]. Suppose that * is in the same Pw- Po-mommunityy as i, and that f # is in a different community. Then notice that dp, (i, f) 2 dp, (i,j). Therefore j E TTP(()). Moreover, since h S I and since the nodes of S C [m]] are equidistributed among kp the communities 1, 1.2...., kp, follows that all members of T..= (h) must belong to the same P. community .2....,pp,
Therefore, since the communities of Qw are coarsening of the communities of Pu. I (Fe ).). Since h < 1. we are done. key
A.4 SBM Clustering Error
In this section, we prove a minimax lower bound in the clustering regime for stochastic block models. Theorem A.28. Let II denote the parameter space of pairs of SBMs (P, Q) on n nodes with kp, kg communities respectively, such that the cluster structure of Q is coarsening the cluster structure of
P. Then
1 E. B
log kQ nQ
inf sup (P.Q)en n²
-12-111
Proof. Let Hm E J0, mm be the Hadamard matrix of order m modified to replace all entries with m not power of two, Hm be defined as follows. Let é [log2 m| and let Hm E Rm/2xm//2 contain Hz1-1 on its top left block and zeroes elsewhere. Let
T0OT HT.
H
Hm
00
Notice that at most 3 fraction of the entries of Hm are zero-padded, for any Now, let Bp
111T + Hpp and BQ 1 T Hg for some 8p, åQ E (0, 1/4) be chosen later.
We will define two families matrices indexed by a finite set T. For T, there are some Z, E (0, 1aakk and Y, E {0, 1pnnkq to be specified later. Then
P. LBB2
Q, = Y,
25

---

Now, we define Y as follows. Let kg denote the set of balanced clusterings 2 [n] + [kol such that for all i.j E [ko]. 1a ((i))
((i)) Let Z C Zn select the 2 such that for Define distance Z as follows. For y. V E Z let Y, E {0, 1 be the corresponding cluster matrices and let d(y. y/) = n "
all j I f2/2,,=
{ n(j-1)
RQ
(Y") [[. By Theorem 2.2 of Gao al. (2015), there exists packing To C with respect to such that for all y, y E To. we have Hj : (1) * v())} 2 n/6. Moreover, log [To] 2 12 n log kq-
Set T = =To- For any yi E To. let Y E {0, 1) xe be the corresponding cluster matrix and then
Q: Y,DYY,"
Now, to define Z, take [ko] and partition y4 ({a)) C [nx] into kp/kq equally sized communities in uniformly random way. Number these ....., kc In this way, we split community 1 of y into ke
communities 1,... e of 24. and so on. Define Z, to be the matrix corresponding to 2,. Notice that ky
Zi Yú are both balanced clusterings and that the clustering Y; coarsens that of Z. Therefore (P,, Qi) pair of heterogeneous symmetric SBMs satisfying Definition 1.3 at h 1/kq.
Next, we apply Fano's 's Inequality (Theorem A.24 Recall log [T] 12 log ko. Now, for i,j E distinct, Prop 4.2 Gao et al. (2015) gives
DxL((P, Q.), (P), 2,)) S DkI(P.,)) + DKz(Q; Q,) O(2283 nz0z) =: n.
Finally, we can bound:
11: Q2 n
1
1
Σ
[((e,,)) - -cg())
π²
kQ
n/2<jšn
2002
=: 72
2
where > 1 is some constant. This follows because there are a constant fraction of > n/2 such that yi(5) + vi),), and any two rows of the Hadamard matrix differ on half their entries.
Now, set 83- 10mg
log kg and op
log kg 1on
Since n 2 nq. we conclude that
71 + log 2
inf sup E
@ --ill?
2 72
@ TE
(1/12)n log KQ
log Kq
nQ
A.5 Proof of Proposition 3.4
We first argue that Algorithm perfectly recovers Zp, Zo with high probability.
Theorem A.29 (Implicit in Chen et al. 2014)). Let M = 2BZ be an (n, Rimin 8)-HSBM. Then there exists absolute constant C > O such that the Algorithm Chen al. (2014) can recover Z, up to permutation, with zero error with probability 2 1 O(n 8)
VTi Amin
log (n)
C
v Vumin
Proof. The algorithm of Chen et al. 2014) returns matrix Y E [0,1]mxx such that Yı₃ if and only if i,j are in the same community, with probability 2 1 O(n-8). Therefore, to construct clustering from Y. simply assign the cluster of node 1 to all j E [n] such that Yı, = 1, and so on. This returns the true E {0, 1] jnnk up to permutation with probability 2 1 - Onn Note that is correctly chosen because Y is equal to block-diagonal matrix of ones up to permutation, with k blocks.
Theorem A.29 implies the following.
26

---

Proposition A.30. Let Zp, Zo be as in Algorithm Let sp, sQ be the signal to noise ratios of (P)
P. Q.Q respectively. sp,,,0 satisfy the conditions of Theorem A.29 with respect to (n, min and (nq. (nq:" m respectively, then then with probability 2 1 O ). there permatation matrices Up E {0. (0.1)kp Uq E (0. 1 such that Zr 7pUr and Z ZqUa.
Next, we want to recover the clustering of Q on all nodes, not just the nq nodes that we observe in Aq. This given by the following.
Proposition A.31. 1. If h 1/kp and kq S kp then there exists unique II {0, 1 xxpg such that plll contains the Q-clustering of all nodes in [n]. Let Zo = ZpIL.
Let be as in Algorithm 2 and Up, Uq be as in Proposition A.30 Then with probability 1-0 (1rg))
ZpUp ZqUq-
Proof. Part (1) follows immediately from the SBM structure of P, and definition of Definition
13
For Part (2), first notice that by Proposition A.30 with probability at least 1 - (+g)), Algorithm
returns the true clusterings 7p = Zp E {0, 1) 1xkk and Zo = Zo E xkg, up to permuta- tion.
Now, Algorithm @ project onto coordinates in S. Then V² = Zq. Moreover, by Proposition A.30 Zp = ZpUP and Zo Zo Hence VZpUppl p1l that each Q-cluster has reprensentatve in
simply takes unions of the clusters of Zp to learn îT. Therefore, let V R + Rne
V VZQUq. To remove dependence on V, we need to argue
Let E' be the event that at least one Q-cluster has no representative in S. For fixed j E [Kq]], cluster j has representative in S with probability <
(1
(Q)
ng
A union bound implies that
no
(Q)
ne
P < lQ
11. mini nQ
< li exp(- (-n min)
I O(ma").
The last incquality holds because the condition of Theorem A.29 implies that n 2 (((TT)) and ng T
kQ
min
Finally, we proceed by conditioning on E. Since 2p = ZpUp, we know that for all i E S, the unique jp [kp] such that row i, column jp of Zp is nonzero contains its true P-community up to Up. Similarly since Ża = Zql'q. the the unique jo E [kq] such that row i, column jo of Zp is nonzero contains its true Q-community up to UQ. Therefore the nodes in community jp in P are in community jQ in Q. So, up to permutations Up and UQ, we have Iljr.jo = 1. Since we condition on -E, each cluster of Q has at least one representative in S, each columns of IT is nonzero. We conclude that p ZQUq with probability at least 0(1²')
We are ready to give the overall error of Proposition 2
Proposition A.32. Suppose that 2p Zp, ñ = II in Algorithm 2
Then with probability >
1 - 1-0(2)) (,), Algorithm returns a Q E [0, 1) 1 such that
1.2 log(n (
1 21 2 n
n
Proof. By Proposition A.31 with probability 21 21-0(1)) ()) we have 2p = ZpUp. Zg = ZoUQ.
and Žoliq Pll We proceed by conditioning these events.
27

---

Next, let WQ E R be the population version of WQ with WQ:: = =11 Zoe,) )
-! Then since
Zq= ZaU0 we have We U2Q Hence
Q Zab.auuccccccaaaaaaaaaaaaaeeaaea ZZe(Wo ZZQ(WoZgAgZaWo
Next, let =Q [r]] - [kq] be the ground truth clustering map given by Zo E {0, 10,1)=xka, Let BQ be defined analogously BQ in Algorithm 2 but using Wi,, 10,, B[Aq] in place of W 2o2 Aq. Let my : W Qui be the the number of nodes belong to community i, and let n,be the the number of nodes in |n] belonging community of Q. Then the error of Algorithm 2 is then
n BB 21
1 n²
Σ (kj
BQ - Aquis )
Ryy
mmmj
rERQ ((i))n =E=q (6H)s
ni7ly
BQ Aqira
m
i.jE[oo
rEtg (()))ns SEeo (1)))s
Next, fix j [ko] and let
Xy
Σ
BQ
AQure-
rE (ti)ns SEAO (())ss
we condition on the clusterings of P,Q being correct then E B[Bqw - Aqurel = 0. Therefore by Hoeffding's 's inequality,
P(Xij 2 2 s 2cxp (-
212
m.my
Setting 1 = 10 log(m:,))mmm, implies that with probability at least 1 k2 min(m:)-2) that the
overall error is
- _ Q1
10 logg(mmm))nm,
m.mj
Finally, note that there exists constant cp > 0 such that for all i E [kq], m, 2 co /nq and the choice of
n, 2 Civni by assumption. Note that each m; is random quantity depending
S [n]] such that E/m,] = ne n; Hoeffding inequality and a union bound over all i E [kq] imply
that that with probability at least 2 1 - O(n²²) that m: 2 Bfma] 10 log nQ 2 R(B(m:)) We
conclude that
Q -Q12
0
Σ
10 10log(m.m,)
nQ s.jERoll
h3 log min
S 0
nQ
B Additional Experiments
B.1
Ablation Experiments
In this section, we discuss additional experiments that quantify the dependence of our algorithms on all relevant parameters. Our experiments also include a new baseline adapted from the estimator of Levin et al. (2022).
28

---

Description of New Baseline, Levin et al. (2022) assumes that full edge data from both P and Q are observed, and P Q. Since this is not for us, instead compute the following modified MLE based on their estimator from Section 3.3 of Levin et al. (022).
mp A Apăi wptwn Aqui up wwgting
if
Φ =
Apи.
otherwise.
Here wp, uQ computed as in their paper, based estimated sub sub-gamma parameters of the noise for Ap, Aq. Akin to their adjacency spectral embedding, which assumes known rank of Q, we use Universal Singular Value Thresholding to obtain Q from Q Chatterjee (2015).
Oracle with = 0.0. In addition to testing the new baseline from Levin et al. (002), we also test the Oracle baseline with p 0.0. As noted in Section this corresponds to the non-transfer setting where all edges from the target graph Q are observed. Note that in this case, the value of no does not matter because edges incident to nodes outside of 5 never get flipped. The Oracle error for B-smooth 28
Xu (2088), which less than the error bound of Theorem 2.3 Indeed, will find that the Oracle transfer algorithms in the regimes where its theoretical upper bound is better than our theoretical upper bounds.
graphons on d-dimensional latent variables will therefore be (
Next, we describe the experimental results.
Figure tests Algorithm for general latent variable models. The error (Theorem 2.3 depends the smoothness 3 of the target graph, the number of observed target nodes niQ, and the dimension of the latent variables d.
Figure tests Algorithm for Stochastic Block Models. The error (Proposition 3.4 depends on the number of communities li in the target graph, and the number of observed target nodes n-Q Note that Proposition 3.4/also depends logarithmically on the minimum community size of Q, but this is less significant.
Baseline (Levin
Ale.
(Thvm 2.25
Graphons, Varying Smoothness 8
Graphons, Varying Oig
Graphons, Varying Dimension d
10a
USE
10-2
10-
0.2
0..6 0.8
0
50 100 150 200
Figure 3: Testing parameters of Algorithm (Transfer for Latent Variable Models). For most parameter settings, our method is better than the baseline and worse than the Oracle. Left: Testing Hölder-smoothness of ʃq with n 200, nQ 25, d = 1. All methods improve as 2 with a = 0.01 and varying.
++1 Here fr(z,8) y) = #" fo y) = =d -v"
Middle: Testing number of observed target nodes no with
200, d 1. Here fr(x, y)
x= +²+ with a 0.01, 0.1. Note that the oracle does not depend on no because it observes the full adjacency matrix Aq 1)
x" +" 2 f0(x.v)
Right: Testing dimension d of latent positions ....... Fn E [0, 1jd (i.i.d. Lebesgue) with = 200, nQ = 25. Here fr (r. y) = exp(-6ila: y1|2) and fo y) = exp( .1 y1l).
Points are the median MSE across 50 trials, with with [5, 95) percentile outcomes shaded.
29

---

Stochastic Block Models, n 200. Varying nio
Stochastic Block Models, n 200, Varving Ko.
10
10--
Figure 4: Testing parameters of Algorithm 2 (Transfer for SBMs). For most parameter settings,
method is better than the baseline and worse than the Oracle.
Left: 200, p 12, kq 6. Note that the oracle does not depend no because it observes the full adjacency matrix Aq E {0, 1j
Right: л 200, ni = 25, kp 2kQ-
For both experiments, the intra-community edge probabilities are 0.2, 0.9 for P. respectively, while the inter-community edge probabilities 0.1, 0.8 respectively, Points the median MSE across 50 trials, with with [5, 95] percentile outcomes shaded.
Note that while we can plot theoretical guarantees for the mean squared error 11 - Q of both algorithms' @ and the oracle's Q Levin et al. (022)) only give theoretical guarantees the spectral norm || Ql1 for their estimator Q. Analyzing the stronger metric of mean-squared error would require different techniques than their paper.
B.2 Link Prediction Experiments
In this section, present additional link prediction experiments the EMAIL-EU and BIGG MODELS datasets. Unlike Section we tune the sparsity estimate ñ E (0, 1) used in the Universal Singular Value Thresholding step of the Oracle baseline. In particular,
set E (0, 1) to be the mean of the entries of the ground truth target matrix Q E [0, 1xxn Note that this value is inaccessible to other algorithms since requires knowing all the edges of Q.
Figures 7 8 the performance of our Algorithms on the EMAIL-EU dataset, and Figures and for the BIGG MODELS dataset. As in the mean-squared emro setting (Figure 2). we find that Algorithm 2 and that the Oracle baseline outperforms both for small p. Moreover, we find that the choice of source & target affects the performance of both of our algorithms. Hence Figure 7 shows better performance than Figure for the same source but different targets, and Figure shows better performance than Figure for the same target but different sources.
C Experimental Details
In this section, we give further details on the experiments of Section Compute Environment. We run all experiments a personal Linux machine with 378GB of CPU/RAM. The total compute time across all results in the paper was less than 2 hours.
Functions for Figure 1 For the top row, the source is an (ni, 4)-SBM with 0.8 on the diagonal and on the off-diagonal of B E R4X44 The target is an (n, 2)-SBM with 0.9 on the diagonal and 0.1 on the off-diagonal of B e 2
30

---

Metabolic Network Link Prediction (Source (WFL1372)
0.9
Algorithm
Algorithm
0.8
Oracle (p=0.0)
AUROC
Oracle (p=0.1)
Oracle (p=0.2)
0.7
Oracle (p=0.3)
0.6
0.5
ng
Figure 5: Link prediction results with the metabolic network of BiGG model iWFL1372 (Escherichia coli W) as the source and iJN1463 (Pseudomonas putida) the target. Shaded regions denote [5, 95] percentile outcomes from 50 independent trials.
Metabolic Network Link Prediction (Source iPC815)
0.9
Algorithm 1
Algorithm 2
0.8
Oracle (p=0.0)
AUROC
Oracle (p=0.1)
Oracle (p-0.2)
0.7
Oracle (p-0.3)
0.6
0.5
25
50
75
100
125 ng
150
175
200
Figure 6: Link prediction results with the metabolic network of BiGG model iPC815 (Yersinia pestis) the source and iJN1463 (Pseudomonas pufida) the target. Shaded regions denote (5, 95) percentile outcomes from 50 independent trials.
Email-EU Link Prediction (Target Days 81-160)
Algorithm
0.9
Algorithm
Oracle (p=0.0)
AUROC
0.8
Oracle (p=0.1)
Oracle (p=0.2)
0.7
Oracle (p=0.2)
0.5
100
150
200
250
300
350
400
ng
Figure 7: Link prediction results with Days 1-80 of EMAIL-EU the source, and Days 81-160 as larget. Shaded regions denote [5, 95] percentile outcomes from 50 independent trials.
For the second and third rows, the source function is Q( () (1 (modified from Zhang al. (017 ). The sources are P(x, y) = 1 Q( y) and P(z,y) v) Q()(z) v), where
σ(z) 0.5 T 0.5 if x 0.5, and 0.5 - | 0.5| otherwise.
Metabolic Networks. We access metabolic models from King et al. (016) at
ucsd
edu To construct reasonable set of shared metabolites across the networks, we take the intersection of the node sets for the following BiGG models: iCHOvl, IJN1663, iMM1415, iPC815, iRC1080,
31

---

Email-EU Link Prediction (Target Days 561-640)
Algorithm
0.9
Algorithm:
Oracle (p=0.0)
0.8
AUROC
Oracle (p=0.1)
Oracle (p=0.2)
0.7
Oracle (p=0.2)
0.6
150
200
250
300
ng
Figure 8: Link prediction results with Days 1-80 of EMAIL-EU the source, and Days 561-640 as target. Shaded regions denote [5, 95] percentile outcomes from 50 independent trials.
iSDY 1059, iSFxv1177 172. 1YL1228, iYS1720, and Recon3D. We obtain a that are present in all of the listed models.
251 metabolites
The resulting networks undirected, unweighted graphs 251 nodes. We construct the matrix Ap E {0, 1 j for species P by setting Ap;w0 = 1 if and only if a and v co-occur in a metabolic reaction in the BiGG model for P.
EMAIL-EU. We use the "email-EUU-oor--empppall dataset at https://sssatt stanf ord edu/ data/emaill Eu- core- temporal html as introduced in Paranjape et al.) (2017). Note that do not perform any node preprocessing, so we use all n = 1005 nodes present in the data, as opposed to Leskovec and Krevl (2014); Paranjape et al. (2017) who only 986 nodes.
Data consist of triples (u, v, where u, u are anonymized individuals and >>> is timestamp. We split the data into 10 bins based on equally spaced timestamp percentiles. For simplicity we refer to these time periods as consisting of days each Section 4 but technically there are 803 days total. The network at time period l consists of an unweighted undirected graph with adjacency matrix entry Aue = 1 and only (u, v, t) or (v, f, u) occurred the data for an appropriate timestamp
Hyperparameters. We do not tune any hyperparameters. For Algorithm of ltn
we use the quantile cutoff
lognn in all experiments. no
32

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA]-
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1 (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include it (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked While "[Yes] " is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providded a proper justification is given (e.g., "error bars expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
the checklist one of the factors in their evaluation.
reported because it would be too computationally
"[No] " or "[NA] is not grounds for rejection. While the questions are phrased acknowledge that the true answer often more nuanced, so please just use your best, judgment and write justification elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We discuss our main contributions in the abstract and introduction, and then develop them in the main body of the paper. Specifically, we point out Algorithm I and Algorithm 2 the upper bounds from Theorem [2.] and Proposition 3.4 and the lower bound
Theorem 3.2 Finally, Section shows experimental results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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 to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
33

---

Answer: [Yes]
Justification: We discuss the limitation of lacking minimax lower bound for network estimation in d-dimensions after Theorem 2.3 the need for a different graph distance for graphs with sparsity O jog in the Conclusion, and adapting to multiple source distributions R
in the Conclusion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors 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 sell--pecification 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 with few runs. In general, empirical results often depend on implicit assumptions, which should be 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 to 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 fairness.
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 It acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an 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
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We give self-containee theoretical statements with definitions and assumptions in the main body, and full proofs for all claims in Appendix
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated 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
Question: 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)?
34

---

Answer: [Yes]
Justification: We give experimental details Section and give further details on our exact data preparation methods in Appendix C
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 to 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 is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a 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) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model is limited in some way (e.g.. registered users), but it should be possible for other researchers to have some path to 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; We submit our code as a supplementary zip file in accordance with the NeurIPS code and data submission guidelines.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cc.
quuides/CooeSuumisstt
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new 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! http://eeeeeeeeeeeueeeeeoooooooo
//nips //npps.ccppubaai wttp:cccppppccc/tettette.ec.cclt httppppllliluupp/peloeeeeeeeeeee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
35

---

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 as much information as possible in supplemental material (appended to 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 (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes)
Justification: We describe our choices of source and target network, the network sizes and degrees, and the single hyperparameter (quantile cutoff) for Algorithm D in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: For each experiment we run 50 independent trials. We report #2 standard deviations for the mean-squared error in Table I and [1, 99] percentile errors in Figure 2
Guidelines:
The answer NA means that the paper does not include experiments.
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 are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run 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).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one 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 range (e.g. negative eтror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
36

---

Justification: As described in Appendix C we run all experiments on personal Linux machine with 378GB of CPU/RAM. The total compute time across all results in the paper was less than hours.
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, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as 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 the paper conform, in every respect, with the NeurlPS Code of Ethics stttps://neurii http.//pb........cccccceeeeeaea.
Answer: [Yes]
Justification: We conform with the NeurIPS Code of Ethics with regards potential harms caused by the research process, societal impact, and impact mitigation measures. Moreover, we have anonymized our code and manuscript.
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 cireumstances 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 societal impacts and negative societal impacts of the work performed?
Answer: [NA]
This paper presents work whose goal is to advance the field Machine Learning through foundational research. There are many possible societal consequences of our work, none which we feel must be specifically highlighted here.
Justification:
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 negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploommett 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
37

---

If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: We not release data or models that have high risk for misuse. We use only publicly available data from the academic literature.
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 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: We credit the authors of the BiGG metabolic models dataset (King et al. 2016 Norsigian et al., 2020) and the EMAIL-EU dataset (Leskovec and Krev] 2014 Paranjape
et al. 2017). Both datasets are publicly released for academic research.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, 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, pawerssipppswiiiieea. thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is 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: [NA]
Justification: We do not release new assets. See Appendix C for the exact details regarding our use of existing datasets and assets.
38

---

Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the datasct/code/model 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 is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. 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:
We do not perform any crowdsourcing or research on human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS 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]
Justification: do not perform any research on living subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 to the NeurIPS 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.
39


Reviews:
[{"review_id": "20FQcbqCAj", "reviewer": "Reviewer_ajJ3", "summary": "This paper investigates transfer learning in the context of estimating latent variable network models.  Specifically, the goal is to estimate the edge probability matrix $Q$ of the target graph using (1) edge data from a source graph $P$ given by its adjacency matrix, and (2) edge data from a vanishingly small subgraph of $Q$ that consists of an $o(1)$ fraction of the nodes in $Q$. The authors propose a transfer learning algorithm (Algorithm 1), which is based on matching quantiles, and demonstrate that it is possible to accurately estimate $Q$ if $P$ and $Q have similar quantile/ranking profiles (per Definition 1.3) and smooth latent variable representations (Assumption 2.1).  Furthermore, in Section 3, the authors focus on Stochastic Block Models, stating the minimax rate under the setup and providing an estimation algorithm (Algorithm 2) that achieves this rate (Proposition 3.4).  The proposed algorithms are then tested with numerical experiments on synthetic and real-world datasets.", "questions": "1. Based on the description of the Oracle algorithm in lines 246-252, it seems that its performance should be independent of $n_Q$. However, in Figure 2, the Oracle algorithm's performance appears to improve as $n_Q$ ​increases in the first two plots. Could the authors clarify if there is something I am missing?\n\n2. For the Email networks, Algorithm 1 seems to outperform the Oracle (with $p=0.01$ and $p=0.05$). Can the authors provide any insights on how a transfer learning algorithm (i.e., Algorithm 1) can outperform an Oracle algorithm that has full access to the edge data from $Q$? \n\n*Minor suggestions/typos:*\n- Line 71:  The order of $|S|$ and $n_Q$ should be swapped, i.e., $n_Q := |S| = o(n)$.\n- Lines 102 - 104: The quantifier for $i$ seems missing, e.g., \"... *for $i$,* and for all $j \\neq i$ ...\"\n- Line 111: Something should be off here.\n- Lines 183 - 184: In the second sentence of Theorem 2.2, it is unclear which parameter corresponds to which function.  I would suggest the authors write for example \"Let $f_P$ be $\\alpha$-H\\\"older-smooth and $f_Q$ be $\\beta$-H\\\"older-smooth for $\\beta \\geq \\alpha > 0$, ...\"\n- Lines 238 - 239: It seems a line break is needed before \"(1) Algorithm 2.\"\n- Lines 244 - 245: This line break should be removed.\n- Section 4: Please use $p_{flip}$ instead of $p$ for consistency (or vice versa).", "limitations": "This is primarily a theoretical work, and the authors discussed the potential limitations of the work and potential future research directions.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This work addresses the significant problem of learning graphs/networks from a small subset of edge data by leveraging knowledge from a source graph. This problem is fundamental and has numerous potential practical applications, such as in biological network estimation and social sciences. The paper considers a simple yet expressive mathematical model and presents key findings and supporting arguments clearly. Although primarily theoretical, the results are complemented by numerical experiments that substantiate the potential of the proposed approach.", "weaknesses": "While this manuscript makes substantial contributions, there are some areas for improvement to enhance its impact:\n\n**1. Model Assumptions:** The models and assumptions in this work —- latent variable models, H\\”older smoothness of the latent functions, and the ranking assumptions between source $P$ and target $Q$ —- are quite standard in theoretical literature. Nevertheless, including in-depth discussions and ablation studies to examine their relevance and applicability in real-world scenarios would help motivate and convince practically oriented readers.\n\n**2. Further Numerical Experiments:** Additional numerical experiments to verify and examine the theoretical results (Theorem 2.2 and Proposition 3.4) would be valuable. This would help validate whether the expected dependence on parameters such as $d, \\beta, n_Q$ are sharp or not. Additionally, comparing the performance of the proposed transfer learning algorithms against a true oracle with direct access to the full edge data from $Q$ (which would correspond to what the authors call “oracle” with $p_{flip} = 0$) would properly quantify the cost of transfer and evaluate the effectiveness of the proposed algorithms.  It would also be beneficial to compare the proposed algorithms to other existing algorithms in the literature to highlight the claimed advantages of the proposals.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for highlighting the fundamental nature of our problem, and its numerous potential practical applications. We will fix all typographical errors in the revision. \n\nWe address their feedback in detail below. \n\n### **Relevance and applicability of latent variable models in real-world scenarios**.\n\nLatent variable models are widely used in applied fields such as neuroscience [1], ecology [2], international relations [3], political pscyhology [4], and education research [5]. To help motivate practically oriented readers, we will include more in-depth discussion of these applications in the revision. \n\n### **Relevance and applicability of the rankings assumption for biological networks.** \n\nPrevious works require some form of similarity between networks to enable transfer (Sen et al. 2018, Fan et al. 2019, Baranwal et al. 2020). For example, Kshirsagar et al. 2013 require a _commonality hypothesis_: if pathogens A, B target the same neighborhoods in a protein interaction network, one can transfer from A to B. Our rankings assumption similarly posits that to transfer knowledge from A to B, A and B have similar 2-hop neighborhood structures. \n\n### **New ablation experiments in the global rebuttal validate our algorithms' error rates.** \n\nWe test dependence of Algorithm 1 on $n_Q, d, \\beta$ and Algorithm 2 on $n_Q, k_Q$. See the global rebuttal and the attached PDF. \n\n* Experiments include comparisons to a true oracle with access to full edge data from $Q$. See also the discussion in the next heading. \n\n* Experiments include new comparisons to a proposed algorithm in the literature by Levin et al (JMLR 2022). See global rebuttal for a full description. \n\n* Performance of Algorithm 1 and Algorithm 2 both match the trend lines given by theoretical upper bounds (Theorem 2.2 and Proposition 3.4 respectively). Note that we plot theoretical upper bounds assuming each one has a constant of $1.0$, but these  are likely to be larger. \n\n### **Oracle with $p = 0.0$ outperforms transfer algorithms in our new experiments.**\n\nAn oracle with $p = 0.0$ corresponds to a non-transfer setting where all edges from the target graph $Q$ are observed. Note that in this case, the value of $n_Q$ does not matter because edges incident to nodes outside of $S$ never get flipped. In lines 251-252, we noted that when $p=0.0$, the Oracle error for $\\beta$-smooth graphons on $d$-dimensional latent variables will be $O(n^{-\\frac{2 \\beta}{2\\beta + d}})$ (Xu 2018), which is less than the error bound of Theorem 2.2. \n\nIn our new experiments we implement this oracle and indeed find that it outperforms our transfer algorithms in the regimes where its theoretical upper bound is better than our theoretical upper bounds. In particular, our upper bounds scale with $n_Q$, rather than $n$, so for $n_Q \\ll n$ transfer should generally be worse. Note that for our Algorithm 1 and for this version of the oracle, lower bounds are unknown (see our discussion in lines 193-196). Still, these experimental results should help quantify the cost of transfer and evaluate the effectiveness of our proposed algorithms.\n\n### **The Oracle depends on $n_Q$ if $p > 0$.** \n\nFollowing the equation below line 249, the oracle observes the unbiased $Y_{ij} \\sim Bernoulli(Q(x_i, x_j))$ if $i, j \\in S$ are both part of the set of observed target nodes $S$ such that $\\lvert S \\rvert = n_Q$. If $i \\not \\in S$ or $j \\not \\in S$ then the oracle observes a possibly flipped version of $Y_{ij}$ when $p > 0$. Therefore as $n_Q$ grows, the oracle should improve, because none of the nodes in $S$ can be flipped. \n\nWe will clarify this point in the revision. \n\n### **The Oracle performs much better on the Email-EU task with $p = 0.0$ than with $p=0.01$.**\n\nRerunning our Email-EU experiment with a flip probability of $p=0.0$, and comparing to our existing results from Figure 2, we have the following. We use ($\\dagger$) to denote a new experiment. \n\n| $n_Q$  | Method | Target  | MSE (Median, 50 Trials)    |\n---- | ---- | ---- | ---- | \n| 20  | Oracle, $p=0.0$ ($\\dagger$)    | Email-EU Days 81-160      | 0.003797 |\n| 20  | Oracle, $p=0.01$    | Email-EU Days 81-160      | 0.007312 |\n| 20  | Our Alg. 1 | Email-EU Days 81-160      | 0.007240 |\n| 20  | Oracle, $p=0.0$ ($\\dagger$)  | Email-EU Days 561-640      | 0.004100 |\n| 20  | Oracle, $p=0.01$    | Email-EU Days 561-640      | 0.007620 |\n| 20  | Our Alg. 1 | Email-EU Days 561-640      | 0.007591 |\n\nFor this dataset, a flip probability of $p = 0.0$ versus $p = 0.01$ makes a substantial difference. Note that all MSE values on the right-hand side of Figure 2 are within $[0.007, 0.008]$, whereas the Oracle with $p=0.0$ has MSE $\\approx 0.04$. Note that the Oracle with $p=0.0$ does not depend on $n_Q$ since it access the full, unbiased edge data from $Q$. \n\nWe believe this difference is because the email networks in Figure 2 are quite sparse, with median degree $\\leq 0.007n$ (see Table 2). Therefore even introducing a $0.01$ probability of edge flips makes the Oracle substantially worse on these networks.\n\n[1] Ren, Mingyang, et al. \"Consistent estimation of the number of communities via regularized network embedding.\" Biometrics 79.3 (2023): 2404-2416.\n\n[2] Trifonova, Neda, et al. \"Spatio-temporal Bayesian network models with latent variables for revealing trophic dynamics and functional networks in fisheries ecology.\" Ecological Informatics 30 (2015): 142-158. \n\n[3] Cao, Xun, and Michael D. Ward. \"Do democracies attract portfolio investment? Transnational portfolio investments modeled as dynamic network.\" International Interactions 40.2 (2014): 216-245.\n\n[4] Barberá, Pablo, et al. \"Tweeting from left to right: Is online political communication more than an echo chamber?.\" Psychological science 26.10 (2015): 1531-1542.\n\n[5] Sweet, Tracy M., et al. \"Hierarchical network models for education research: Hierarchical latent space models.\" Journal of Educational and Behavioral Statistics 38.3 (2013): 295-318.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JGZOO4EmE6", "reviewer": "Reviewer_VhmF", "summary": "The work explores transfer learning in latent variable network models. In particular the work focuses on the setting of observing samples from an n x n probability matrix from a source P and a submatrix of the adjacency of a target Q. The goal is then to estimate Q, using information from P.  \n\nThe authors propose an algorithm with vanishing error under certain conditions and a more simple algorithm for the special case of stochastic block models.", "questions": "Would the authors be able to explain why they think there are no direct baselines? I am not familiar with the surrounding literature, but the problem of estimating a full matrix from a sub-matrix should be a well-studied area. It might be useful to include baselines that do this, even if they are not operating in the transfer learning regime. \n\nWould the authors be able to provide experiments on a real-world task -- or if not provide a justification?", "limitations": "None that I am aware.", "rating": 6, "confidence": 1, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written. I particularly enjoyed the introductory sections that help motivate the work. I believe that the problem the authors tackle has value, as it stands mostly as a theoretical contribution. \n\nI am unfortunately unable to judge the strength of the contribution of this work as the submission is far from my area of research.", "weaknesses": "The experimental part of the paper focuses on purely synthetic tasks. While I understand that, as the authors mention, they believe there aren't direct baselines or datasets for this, I still see this as a potential weakness.\n\nA way to greatly strengthen the work would be to have experiments on domains mentioned in the introduction (i.e. metabolic networks).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for highlighting the quality of our writing and the value of the problem we tackle. We address their comments in detail below. \n\n### **We test our algorithms on two real-world transfer tasks.**\n\nIn Section 4, lines 271-287, we test our algorithms on two real-world transfer tasks, using the BiGG dataset from the biological networks literature (King et al. 2016) and the Email-EU dataset from the social networks literature (Leskovec and Krevl 2014). \n\n### **We perform experiments on the domains mentioned in the introduction (metabolic network estimation).**\n\nIn Section 4, lines 273-279, we use our algorithms to estimate the metabolic network of _Pseudomonas putida_, a gram-negative bacterium that is studied for its applications to industrial biocatalysis [1] and bioremediation [2]. The full metabolic network for _Pseudomonas putida_ is not known [3]. We use our transfer learning algorithms to estimate its metabolic network for different choices of source organism (Figure 2, left). For a good choice of source organism, our Algorithm 1 achieves mean-squared error comparable to the Oracle with flip probability $p=0.1$.\n\n### **Comparisons against a new baseline adapted from Levin et al. (JMLR 2022).** \n\nIn the global rebuttal, we implement a new baseline transfer method from the literature to compare against our algorithms. See the global rebuttal and attached PDF for results. At a high level, our algorithm is better in most parameter regimes that we test, which we will discuss more below. \n\nWe introduce a new model of transfer learning on networks (lines 69-71). To our knowledge, there are no published algorithms with provable guarantees that can be directly applied to our setting. Two key differences of our setting compared to existing works are: \n* _No node data for most nodes in the target network $Q$_. Most works on transfer learning for graphs assume access to some edge data for every node in the target graph (Wang et al. 2018, Levin et al. 2022). Similarly, matrix completion papers typically assume that at least one entry from each row/column of the target matrix is observed (Chatterjee 2015, Simchowitz et al. 2023 and references therein), or otherwise assume low rank/nuclear norm (see [2] and references therein). In our setting, we only observe an $n_Q \\times n_Q$ subgraph for $n_Q \\ll n$. Hence for most target nodes we observe none of their edges. This is comparable to the MNAR (Missing Not at Random) model in matrix completion [3]. \n\n* _No node labels in any network_. We consider a latent variable model in which the relevant features of nodes are not observed. This excludes approaches that rely on observed node labels or features (Tang et al. 2016, Zou et al. 2021, Qiao et al. 2023, Wu et al. 2024). \n\nNevertheless, for the sake of comparison we implement a new baseline based on a modification of Levin et al. [1]. Specifically, we modify the estimator from their Section 3.3. Their method assumes that full edge data from both P and Q are observed, and that they have the same expectation ($P = Q$). Since this is not true for us, we instead compute the modified MLE: \n\n$$\\tilde Q_{ij} = \\begin{cases}\n\\frac{w_P}{w_P + w_Q} A_{P;ij} + \\frac{w_Q}{w_P + w_Q} A_{Q;ij} & i, j \\in S \\\\\\\\\nA_{P;ij} & \\\\text{otherwise}\n\\end{cases}$$\n\nWhere the weights $w_P, w_Q$ are computed as in their paper, based on estimated sub-gamma parameters of the noise for $A_P, A_Q$. This is the only modification we make to their algorithm. \n\nNote that Levin et al. only give theoretical guarantees on the spectral norm $\\|| \\hat Q - Q \\||_2$ of their estimator $\\hat Q$. Analyzing the stronger metric of mean-squared error $\\frac{1}{n^2} \\|| \\hat Q - Q \\||_F^2$ would require different techniques than their paper. \n\n### **Matrix completion without transfer should perform poorly in our setting.**\n\nIn our setting, we only observe target data on an $n_Q \\times n_Q$ submatrix of the adjacency matrix, for $n_Q \\ll n$. To apply a matrix completion algorithm, we can certainly zero-pad the target data to obtain some $A_Q \\in \\\\{0,1\\\\}^{n \\times n}$, and apply a standard matrix completion algorithm to this $A_Q$. However, in this case the matrix $A_Q$ would have mostly all-zeroes rows and columns, corresponding to nodes $i \\not \\in S$. Up to permutation, the zero-padded input matrix would have block structure: \n\n$$A_Q = \\begin{bmatrix} A_Q[S, S] & 0 \\\\\\\\ 0 & 0 \\end{bmatrix}$$\n\nWhere $A_Q[S, S] \\in \\\\{0,1\\\\}^{n_Q \\times n_Q}$ contains the observed target data. Note that $n_Q \\ll n$ so the matrix is almost all zeroes. \n\nTherefore, any left/right singular vector of $A_Q$ will be of the form $v = \\begin{bmatrix} v_S \\\\\\\\ 0 \\end{bmatrix}$, where $v_S \\in \\mathbb{R}^{n_Q}$ is a singular vector of $A_S[S,S]$. The singular vectors will contain no information outside of $S$, and therefore the matrix completion algorithm will do poorly. \n\n[1] Nikel, Pablo I., and Víctor de Lorenzo. \"Pseudomonas putida as a functional chassis for industrial biocatalysis: from native biochemistry to trans-metabolism.\" Metabolic engineering 50 (2018): 142-155.\n\n[2] Ward, Patrick G., et al. \"A two step chemo-biotechnological conversion of polystyrene to a biodegradable thermoplastic.\" Environmental science & technology 40.7 (2006): 2433-2437.\n\n[3] Yuan, Qianqian, et al. \"Pathway-consensus approach to metabolic network reconstruction for Pseudomonas putida KT2440 by systematic comparison of published models.\" PloS one 12.1 (2017): e0169437.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6meeQvwp9N", "reviewer": "Reviewer_BaBd", "summary": "In this paper, the authors address two topics  in random network/graph models:\n1. The transfer learning in latent variable network models. It proposed estimate of the distribution of target network from source network using a defined graph distance.\n2. It also proves a minimax lower bound for Stochastic Block Models and show that a simple algorithm achieves this rate.", "questions": "In Page 3, line 105: the authors mentioned: relative, not absolute graph distances,  it seems to me this is not defined.", "limitations": "In the authors' reply to the question set, in line 950, the authors mentioned that they discussed  \"the need for a different graph distance ...\"\n. It will benefit the readers if the authors explain further in this paper on the selection of of the distance, an explain why they prefer this graph distance that they are currently using.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is a theoretical paper that addresses the transfer learning from source to target network in latent variable network models.", "weaknesses": "1. Theorem 1.1 is an informal form of Theorem 2.2, it seems there is no need to repeat.\n2. The authors repeatedly use the vague word \"suitable\", \"suitably\" in the paper. Many phrases (containing this word) need to be clarified.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their feedback and for assessing our paper to have high impact. We address their comments in detail below. \n\n### **Clarification of relative versus absolute graph distances.**\n\nOn line 105, we note that our rankings assumption (Definition 1.3) concerns relative, not absolute graph distances. The reviewer is right to point out that the terms \"relative\" and \"absolute\" can be clarified. \n\nOur point is that Definition 1.3 involves quantiles of graph distances. This is a \"relative\" condition, because it depends on a rank-ordering within both graphs $P, Q$ before comparison. On the other hand, an \"absolute\" condition would require that for nodes $i, j \\in [n]$, if e.g. $d_P(i,j) < 100$ then $d_Q(i,j) < C \\cdot 100$. Our condition is more flexible and will hold for a larger set of graph pairs $(P, Q)$, such as pairs where one graph is much more dense than the other. \n\nIn the revision, we will rewrite line 105 to clarify this point.\n\n### **What we mean by \"the need for a different graph distance\" in line 950.**\n\nIn line 950 we mention our discussion of extending to sparse graphs in the Conclusion (lines 292-295). The concentration of the empirical graph distance (Algorithm 1, line 3) requires expected degree $\\tilde\\Omega(n^{1/2})$ (Mao et al. 2021). In the same paper, they show that a modification of this graph distance concentrates when expected degree is $\\tilde\\Omega(n^{1/3})$. \n\nWhile this is still far from the $\\Theta(\\log n)$ degree regime, it suggests that variations on the graph distance might ensure our Algorithm 1 works for sparser graphs. \n\nWe will clarify this point in the revision. \n\n### **Why we select our graph distance.** \n\nWe use the common neighbors graph distance (Definition 1.2) to capture local graph structure, as discussed in lines 90-100. Other graph distances have been used in the literature as well (Zhang et al. 2017, Mukherjee and Chakrabarti 2019, Mao et al. 2021).\n\nThe reason we use this specific graph distance is technical. We upper-bound part of the smoothing error of Algorithm 1 in terms of the common neighbors graph distance (section A.2.3). Roughly speaking, there is a relationship between the $\\ell_2$ (Euclidean) distance between rows of the common neighbors matrix $Q^2$ (coming from our graph distance), and the $\\ell_2$ distance between rows of $\\hat Q - Q$ (coming from the mean-squared error $\\frac{1}{n^2} \\|| \\hat Q - Q \\||_F^2$).  See Lemma A.17, lines 641-646, for a precise statement. \n\nTo minimize mean-squared error, we use a graph distance based on $\\ell_2$ distance. Previous works indicate that bounding other kinds of error, such as $\\|| \\hat Q - Q \\||_{2 \\to \\infty}$ (Zhang et al. 2017), require graph distances tailored for those errors. \n\nWe will include this point in the revision. \n\n### **Writing clarity and typographical errors.** \n\nWe will remove all uses of vague language and typographical errors in the revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nZIDBYdZ1F", "reviewer": "Reviewer_TFsn", "summary": "This paper studies the problem of transfer learning for estimating the edge probabilities of random graphs under latent position models. In particular, given a fully observed graph on $n$ nodes generated from an independent-edge random graph model, with edge probabilty matrix $P$, and an $n_Q \\times n_Q$ submatrix of a graph generated from an independent-edge random graph with edge probability matrix $Q$, the authors consider the task of estimating $Q$, by leveraging information from both graphs. In order for transfer learning to be possible, the underlying graph models must share some structure. The authors assume that both $P$ and $Q$ are given by latent positions models, i.e.\n\n$$\nP_{ij} = f_P(x_i,x_j),\\qquad Q_{ij} = f_Q(x_i, x_j)\n$$\n\nwhere  $x_1,\\ldots,x_n \\in \\mathcal{X} \\subset \\R^d$ are a common set of latent positions, drawn i.i.d. from a uniform distribution on $\\mathcal{X}$, and that $f_P, f_Q$ are $\\alpha$​-Hölder-smooth symmetric functions. The authors quantify the similarity between two nodes in a graph model using an interpretable distance based on their expected number of common neighbours (Definition 1.2), and measure the distance between two graph models on the same node set by comparing the ranks of these distances for each node in the graphs.\n\nIn Section 2, a simple algorithm (Algorithm 1) is proposed which estimates $Q_{ij}$ by averaging entries of $A_Q$ which are similar in terms of graph distance to $(i,j)$ in $A_P$, and under some reasonable conditions, a high-probability tail bound from the Frobenius norm difference between $\\hat Q$ and $Q$ is dervived (Theorem 2.2).\n\nIn Section 3, information theoretic lower bounds for the problem are derived under the special case that $A_P$ and $A_Q$ are stochastic block model (SBM) graphs (Theorem 3.2), which are proved using Fano's lemma. An alternative algorithm (Algorithm 2) for estimating $Q$ under the SBM modelling assumption is proposed, based on the same ideas as Algorithm 1, and a high-probability tail bound (Proposition 3.4), analagous to Theorem 2.2, is derived which matches the information-theoretic lower bound up to a log factor.\n\nIn Section 4, Algorithms 1 and 2 are compared with an oracle method on a selection of simulated and real-world datasets.\n\nComplete proofs of all theoretical results are provided in the appendix.", "questions": "My only questions to the authors relate to addressing to points raised in the Weaknesses section. I should mention that the first point is a curiosity and I believe it is only the second point that needs addressing before this work is ready for publication.\n\n**Typos:**\n- I believe there is a typo in the conclusion, and that the big-Os relating to edge densities should be big-$\\Omega$s. Is this correct?\n- The first letter on line 111 should be capitalised.", "limitations": "The authors are upfront the main limitations of their work, although I think it would be helpful to mention the first weakness I mention explicitly.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- This paper was a joy to read. The problem of transfer-learning on graphs is well-motivated with real-world applications and the relevant literature is reviewed extensively. The reader is guided through each aspect of the problem; every definition feels motivated and mathematical statements are followed by intuition and illustrative examples. The paper is well organised, the writing is exemplary, and proofs are complete, accurate and clear.\n\n- This paper addresses a problem which is of great relevance to the machine-learning community, and yet provides what appears to be the first provably consistent algorithm for this problem. The proposed solution, is simple and elegant, and the derived high-probability tail bound and its proof provide a lens into the fundamentally important aspects of this problem. The lower bounds derived in Section 3 show the, despite the simplicity of the method, it is optimal (in the minimax sense) under the SBM, albeit under fairly strong signal-to-noise assumptions (see weaknesses).\n\n- The simulated and real data experiments in Section 4 are informative and demonstrate the effectiveness of the approach.", "weaknesses": "- One weakness of this paper, is that their setup only considers graphs whose expected node degrees grow linearly in the number of nodes in the graph. In practice, many networks are sparse and it is common in the literature to consider asymptotic regimes in which expected node degrees grow sub-linearly. However, there is sufficient novelty in this paper that I don't see that this can be held against it. The authors claim in their conclusion that they believe their algorithm will work for when node degree are of the order $\\Theta(n^{1/2})$, but not down to $\\Theta(\\log(n))$ (see Questions), but it is not clear *why* they believe this. \n- It is not clear to me what is being shown in Figure 1. I was left quite confused. Some additional explanation here would be helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their very encouraging comments concerning the novelty of our theoretical guarantees, the great relevance of the problem we consider, and the quality of our writing. We address their comments in detail below. \n\n### **Why we believe our Algorithm 1 will work for expected node degree $\\\\tilde\\\\Theta(n^{1/2})$.**\n\n1) _Graph distance concentration_. The proof of Theorem 2.2 requires that the empirical graph distance we use in Algorithm 1 concentrates around the population graph distance (Proposition A.13, line 602). We show that the concentration is strong enough for our purposes when the expected node degree grows linearly in the number of nodes. However, the common neighbors metric has also been used for network-assisted covariate estimation (Mao et. al. 2021) with expected node degree $\\\\tilde\\\\Omega(n^{1/2})$. Therefore, we expect that the analysis of Algorithm 1 would still go through for expected node degree $\\\\tilde\\\\Theta(n^{1/2})$. \n\n2) _Empirical results on sparse real-world graphs_. We test our Algorithm 1 on sparse real-world graphs in Section 4, lines 271-287. The metabolic networks have median node degree $\\approx 0.06 n$ and the email networks have median node degree $\\approx 0.007 n$ (see Table 2). The performance of Algorithm 1 on these graphs suggests that the assumption of $\\Theta(n)$ node degree is perhaps not necessary. \n\n### **Why we believe our Algorithm 1 will not work for expected node degree $\\Theta(\\log(n))$.**\n\nFor expected degree $o(n^{1/2})$, the common neighbors graph distance (Definition 1.2) fails to concentrate. However, one can modify the common neighbors distance so that it concentrates for expected node degree $\\\\tilde\\\\Omega(n^{1/3})$ (Mao et al. 2021). While this is still far from the $\\Theta(\\log(n))$ regime, it suggests that variations on the graph distance might ensure our Algorithm 1 works for sparser graphs.\n\nNote that for a Stochastic Block Model with two communities, there are information theoretic limitations to exact recovery when the expected node degree of the SBM is $o(\\\\log n)$ (see [1], Theorem 13). Latent variable models are much more general than SBMs, so it is unlikely that we can give a consistent algorithm for expected node degree $o(\\\\log n)$ in our setting. \n\n### **Clarification of Figure 1.**\n\nThe intention of Figure 1 is to give a visual idea of the inputs and outputs for the Algorithms we consider in our paper. It is styled after a similar figure in Zhang et al. (Biometrika, 2017).\n\nThe Figure intends to show, at a glance, that Algorithms 1 and 2 both work well on Stochastic Block Models, that only Algorithm 1 works well on graphons, and that the Oracle performs well in all cases. \n\nTo clarify, each row of the figure corresponds to a different source/target pair $(P, Q)$. For a fixed row, the upper triangular part on columns 2, 3, 4 corresponds a $\\hat Q$ for a different algorithm. The upper triangular part of column 1 shows the true $P$. The lower triangular part of columns 1, 2, 3, and 4 is identical for a fixed row, and shows the true $Q$. \n\nFor example, the first row of Figure 1 shows a pair $(P, Q)$ of Stochastic Block Models. From the left-most cell, we can see that $Q$ has $2$ communities while $P$ has $4$. The upper triangles of columns 2, 3, 4 show  $\\hat Q$ for Algorithms 1, 2 and the Oracle respectively. The lower triangles in columns 1, 2, 3, 4 are all the same, and show the true edge probability matrix $Q$. Each cell displays the true $Q$ in the lower triangle for comparison. \n\nWe will rewrite the Figure caption in the revision to avoid confusion. \n\n### **Typographical errors.**\n\nThe reviewer is correct that the occurrences of $O(\\cdot)$ should be replaced with $\\Omega(\\cdot)$ in the Conclusion, lines 293 and 294. We will fix this and all other typographical errors in the revision. \n\n[1] Abbe, Emmanuel. \"Community detection and stochastic block models: recent developments.\" Journal of Machine Learning Research 18.177 (2018): 1-86.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely thank all the reviewers for their encouraging comments and for acknowledging the significance of our work. We will fix all typographical errors in the revision. 

In this global rebuttal, we will mainly discuss the new experiments, attached as PDF. 

### **New experiments quantify the dependence of Algorithms 1 and 2 on all parameters [Reviewer ajJ3].** 

Each experiment tests the dependence of one of our algorithms on a particular parameter (see the attached PDF).

Algorithm 1 is for general latent variable models. The error (Theorem 2.2) depends on the smoothness $\beta$ of the target graph, the number of observed target nodes $n_Q$, and the dimension of the latent variables $d$. 

Algorithm 2 is for Stochastic Block Models. The error (Proposition 3.4) depends on the number of communities $k_Q$ in the target graph, and the number of observed target nodes $n_Q$. Note that Proposition 3.4 also depends logarithmically on the minimum community size of $Q$, but this is less significant. 

### **Comparisons against a new baseline adapted from Levin et al. (JMLR 2022) [Reviewers ajJ3 and VhmF].** 

We introduce a new model of transfer learning on networks (lines 69-71). To our knowledge, there are no published algorithms with provable guarantees that can be directly applied to our setting. Two key differences of our setting with existing works are: 
* _No node data for most nodes in the target network $Q$_. Most works on transfer learning for graphs assume access to some edge data for every node in the target graph (Wang et al. 2018, Levin et al. 2022). Similarly, matrix completion papers typically assume that at least one entry from each row/column of the target matrix is observed (Chatterjee 2015, Simchowitz et al. 2023 and references therein), or otherwise assume low rank/nuclear norm (see [1] and references therein). In our setting, we only observe an $n_Q \times n_Q$ subgraph for $n_Q \ll n$. Hence for most target nodes we observe none of their edges. This is comparable to the MNAR (Missing Not at Random) model in matrix completion [2]. 

* _No node labels in any network_. We consider a latent variable model in which the relevant features of nodes are not observed. This excludes approaches that rely on observed node labels or features (Tang et al. 2016, Zou et al. 2021, Qiao et al. 2023, Wu et al. 2024). 

Nevertheless, we implement a new baseline based on a modification of the estimator in Section 3.3 of Levin et al., 2021. They assume that full edge data from both P and Q are observed, and $P=Q$. Since this is not true for us, we instead compute the modified MLE: 

$$\tilde Q_{ij} = \begin{cases}
\frac{w_P}{w_P + w_Q} A_{P;ij} + \frac{w_Q}{w_P + w_Q} A_{Q;ij} & i, j \in S \\\\
A_{P;ij} & \\text{otherwise}
\end{cases}$$

Where $w_P, w_Q$ are computed as in their paper, based on estimated sub-gamma parameters of the noise for $A_P, A_Q$. Akin to their adjacency spectral embedding, which assumes known rank of $Q$, we use Universal Singular Value Thresholding to obtain $\hat Q$ from $\tilde Q$.

Note that while we can plot theoretical guarantees for the mean squared error $\frac{1}{n^2} \|| \hat Q - Q \||_F^2$ of both our algorithms' $\hat Q$ and the oracle's $\hat Q$, Levin et al. only give theoretical guarantees on the spectral norm $\|| \hat Q - Q \||_2$ for their estimator $\hat Q$. Analyzing the stronger metric of mean-squared error would require different techniques than their paper. 

### **Comparisons against the Oracle with $p = 0.0$ [Reviewer ajJ3].**

As suggested by reviewer ajJ3, we compare against the Oracle with flip probability $p = 0.0$. This corresponds to a non-transfer setting in which full data from the target graph $Q$ are observed. In this case, the value of $n_Q$ does not matter since edges incident to nodes outside of $S$ never get flipped. In lines 251-252, we note that such an oracle should be better than Algorithm 1 for smooth graphons. This is supported by our experiments. 

### **Takeaways from our new experiments (see attached PDF) [Reviewers ajJ3 and VhmF].**

Our main takeaway is that the performance of Algorithms 1 and 2 matches the trend of our theoretical upper bounds (modulo constants). These validate our analyses and show the applicability of our methods in a wide variety of regimes, complementing our existing experiments on real-world data. 

By comparing against the Oracle with full edge data from $Q$, we help quantify the cost of transfer. As we would expect, the Oracle with $p = 0$ consistently attains lower mean-squared error than our Algorithms. This is to be expected because our transfer algorithms do not access the full target data from $Q$. 

The baseline adapted from Levin et al. is worse than our Algorithms. This is not surprising because it is not designed for a setting in which $P \neq Q$ and a vanishing fraction of $Q$ is observed. 

### **Clarifying the effect of sparsity on the choice of graph distance [Reviewers BaBd and TFsn].**

We use the common neighbors graph distance (Definition 1.2) to capture local graph structure in Algorithm 1. Other graph distances have been used in the literature as well (Zhang et al. 2017, Mukherjee and Chakrabarti 2019, Mao et al. 2021), but ours is useful for technical reasons (see response to Reviewer BaBd). 

For expected degree $\tilde o(n^{1/2})$, our graph distance (Definition 1.2) fails to concentrate (Mao et al. 2021). However, the same authors show that a modified common neighbors concentrates for expected degree $\tilde \Omega(n^{1/3})$. This suggests that variations on the graph distance might ensure our Algorithm 1 works for sparser graphs.

[1] Xiang, Yunhua, et al. "On the optimality of nuclear-norm-based matrix completion for problems with smooth non-linear structure." JMLR 2023.

[2] Ma, Wei, and George H. Chen. "Missing not at random in matrix completion: The effectiveness of estimating missingness probabilities under a low nuclear norm assumption." NeurIPS 2019.

Meta-review: There is consensus that this submission should be accepted.
Decision: Accept (poster)