Transfer Learning for Latent Variable Network Models

Authors: akhil  jalan
arya  mazumdar
soumendu sundar mukherjee
purnamrita  sarkar
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 03:24:34

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.

Main paper: 
 introduction: 
 Within machine learning and statistics, the paradigm of transfer learning describes a setup where data from a source distribution P is exploited to improve estimation of a target distribution Q for which a small amount of data is available. Transfer learning is quite well-studied in learning theory, starting with works such as Ben-David et al. (2006) ; Cortes et al. (2008) ; Crammer et al. (2008) , and at the same time has found applications in areas such as computer vision (Tzeng et al., 2017a) and speech recognition (Huang et al., 2013) . A fairly large body of work in 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 Pu, 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 × n edge probability matrix for the source P and only a n Q × n Q submatrix of Q for n Q ≪ n. We would like to estimate the full n × 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 is a natural extension of the transfer learning problem in classification/regression to a network context. However, it is to be noted that network transfer is a 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, we 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., 2020) and biological network estimation more broadly (Fan et al., 2019; Li et al., 2022) typically assume that some edges are observed for every node in the target network. One exception is Kshirsagar et al. (2013) , who leverage side information for host-pathogen protein interaction networks. For the case of metabolic networks, determining interactions in vivo1 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 to fix a 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 a large class of models whose edge probabilities 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 et al., 2002; Hoff, 2007; Handcock et al., 2007; Holland et al., 1983; Rubin-Delanchy et al., 2022; Airoldi et al., 2008) . 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; Hoover, 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 x 1 , . . . , x n ∈ X ⊂ R d and unknown function f Q : X × X → [0, 1] where X is a compact set and d an arbitrary fixed dimension, the edge probabilities are:EQUATIONTypically, in network estimation, one observes adjacency matrix {A ij } distributed as {Bernoulli(Q ij )}, and either has to learn x i or directly estimate f Q . There has been much work in the statistics community on estimating x i for specific models (usually up to rotation). For stochastic block models, see the excellent survey in Abbe (2017) .Estimating f Q can be done with some additional assumptions (Chatterjee, 2015) . When f Q has appropriate smoothness properties, one can estimate it 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 f Q on n Q 2 pairs of nodes, for a uniformly random subset of variables S ⊂ {1, 2, . . . , n}. We assume S is vanishingly small, so n Q := |S| = o(n).Absent additional information, we cannot hope to achieve o(1) mean-squared error. To see this, suppose f Q is a stochastic block model with 2 communities of equal size. For a node i ̸ ∈ S, no edges incident to i are observed, so its community cannot be learned. Since n Q ≪ 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 A P ∈ {0, 1} n×n and target data A Q ∈ {0, 1} n Q ×n Q coming from an appropriate pair (f P , f Q ) of latent variable models, outputs Q ∈ R n×n such thatP 1 n 2 ∥Q -Q∥ 2 F ≤ o(1) ≥ 1 -o(1).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 (f P , f Q ) such that for all x, y ∈ X , the difference (f P (x, y) -f Q (x, y)) is small. For example, Cai and Pu (2024) study transfer learning for nonparametric regression when f P -f Q is close to a polynomial in x, y. But, requiring f P -f Q to be pointwise small does not capture a broad class of pairs in the network setting. For example, if , i ̸ = j, we define the graph distance between them as follows:f P = αf Q . Then f P -f Q = (α -1)f Q can be far from all polynomials if f Q is, e.g.d P (i, j) := ∥(e i -e j ) T P 2 (I -e i e T i -e j e T j )∥ 2 2, where e i , e j ∈ R n 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 f P , f Q 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 x 1 , . . . , x n of interest. The hope is that the proximity in graph distance reflects the proximity in latent positions. Definition 1.3 (Rankings Assumption at Quantile h n ). Let (P, Q) be a pair of graphs evaluated on n latent positions. We say (P, Q) satisfy the rankings assumption at quantile h n ≤ 1 if there exists constant C > 0 such that for all i ∈ [n] and all j ̸ = i, if j belongs to the bottom h n -quantile of d P (i, •), then j belongs to the bottom Ch n -quantile of d Q (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 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.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, j ∈ [n], if e.g. d P (i, j) < 100 then d Q (i, j) < C • 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.Finally, to illustrate Definition 1.3, consider stochastic block models f P , f Q with k P ≥ k Q communities respectively. If nodes i, j are in the same communities then P e i = P e j , so d P (i, j) = 0. We require that j minimizes d Q (i, •). This occurs if and only if d Q (i, j) = 0. Hence if i, j belong to the same community in P , they are in the same community in Q. Note that the converse is not necessary; we could have Q with 1 community and P with arbitrarily many communities.With the relationship between the source and target defined by the rankings assumption, our contributions are as follows.(1) Algorithm for Latent Variable Models. We provide an efficient Algorithm 1 for latent variable models with Hölder-smooth f P , f Q . The benefit of this algorithm is that it does not assume a parametric form of f P and f Q . We prove a guarantee on its error in Theorem 2.3.(2) Minimax Rates. We prove a 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 on Real-World Data. We test both of our algorithms on real-world metabolic networks and dynamic email networks, as well as synthetic data (Section 4).All proofs are deferred to the Appendix.Transfer learning has recently drawn a lot of interest both in applied and theoretical communities. The notion of transferring knowledge from one domain with a lot of data to another with less available data has seen applications in epidemiology Apostolopoulos and Bessiana (2020), computer vision Long et al. (2015) ; Tzeng et al. (2017b) ; Huh et al. (2016) ; Donahue et al. (2014) ; Neyshabur et al. (2020) , natural language processing Daumé (2007) , etc. For a comprehensive survey see Zhuang 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) ; Tripuraneni et al. (2020) ; Agarwal et 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 a source network to do link prediction in a target network. Lee et al. (2017) proposes a deep learning framework for graph-structured 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. (2021) 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 a graph neural network for transfer based on an ego-graph-based loss function. Learning from observations of the full network and additional information from a game played on the network Leng et 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 Cao et al. (2010) do joint link prediction on a collection of networks with the same link function but different parameters.E[Pij] = E[Qij].Another line of related but different work deals with multiplex networks (Lee et al., 2014 (Lee et al., , 2015;; Iacovacci and Bianconi, 2016; Cozzo et al., 2018) and dynamic networks Sarkar and Moore (2005) ; Kim et al. (2018) ; Sewell and Chen (2015) ; Sarkar et al. (2012) ; Chang et al. (2024) ; Wang et 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, 2017a) or oracle access to the latent structure (Mazumdar and Saha, 2017b) .Notation. We use lowercase letters a, b, c to denote (real) scalars, boldface x, y, z to denote vectors, and uppercase A, B, C to denote matrices. Let a∨b := max{a, b} and a∧b := min{a, b}. For integer n > 0, let [n] := {1, 2, . . . , n}. For a subset S ⊂ [n] and A ∈ R n×n , let A[S, S] ∈ R |S|×|S| be the principal submatrix with row and column indices in S. We denote the ℓ 2 vector norm as ∥x∥ = ∥x∥ 2 , dot product as ⟨x, y⟩, and Frobenius norm as ∥A∥ = ∥A∥ F . For functions f, g : N → R we let f ≲ g denote f = O(g) and f ≳ g denote f = Ω(g). All asymptotics O(•), o(•), Ω(•), ω(•) are with respect to n Q unless specified otherwise. 
estimating latent variable models with rankings: 
 In this section, we present a computationally efficient transfer learning algorithm for latent variable models. Algorithm 1 learns the local structure of P based on graph distances (Definition 1.2). For Algorithm 1 Q-Estimation for Latent Variable Models 1: Input:A P ∈ {0, 1} n×n , A Q ∈ {0, 1} n Q ×n Q , S ⊂ [n] s.t. |S| = n Q . 2: Initialize Q ∈ R n×nto be all zeroes. 3: For all i, all j ̸ = i, compute graph distances:d A P (i, j) := ∥(e i -e j ) T (A P ) 2 (I -e i e Ti -e j e T j )∥ 2 2 .4: Fix a bandwidth h ∈ (0, 1) based on n, n Q . 5: for i = 1 to n do 6:Let T A P i (h) ⊂ S be bottom h-quantile of S with respect to d A P (i, •).if i ∈ S then 8:UpdateT A P i (h) ← T A P i (h) ∪ {i}. 9:end if 10: end for 11: for i = 2 to n do 12:for 1 ≤ j < i do 13:Compute Q ij = Q ji by averaging:Q ij := 1 T A P i (h) T A P j (h) r∈T A P i (h) s∈T A P j (h)A Q;rs .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 d P (i, •). For most nodes i, j ∈ [n], none of the edges incident to i or j are observed in Q. Therefore, we estimate Q ij by using the edge information about nodes r, s ∈ S such that d P (i, r) and d P (j, s) are small. Formally, we consider a model as in Eq. (1) with a compact latent space X ⊂ R d and latent variables sampled i.i.d. from the normalized Lebesgue measure on X . We set X = [0, 1] d without loss of generality and assume that functions f : X × X → [0, 1] are α-Hölder-smooth. Definition 2.1. Let f : X × X → R and α > 0. We say f is α-Hölder-smooth if there exists C α > 0 such that for all x, x ′ , y ∈ X ,κ∈N d : i κi=⌊α⌋ ∂ i κi f ∂ κ1 x1 • • • ∂ κ d x d (x, y) - ∂ i κi f ∂ κ1 x1 • • • ∂ κ d x d (x ′ , y) ≤ C α ∥x -x ′ ∥ α∧1 2 .To exclude degenerate cases where a node may not have enough neighbors in latent space, we require the following assumption. Assumption 2.2 (Assumption 3.2 of Mao et al. (2021) ). Let G be a graph on x 1 , . . . , x n . There exist c 2 > c 1 > 0 and ∆ n = o(1) such that for all x i , x j ,c 1 ∥x i -x j ∥ α∧1 -∆ n ≤ 1 n 3 d G (i, j) ≤ c 2 ∥x i -x j ∥ α∧1 .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 1 below.Theorem 2.3. Let Q be as in Algorithm 1. Let f P be α-Hölder-smooth and f Q be β-Höldersmooth for β ≥ α > 0, and let c be an absolute constant. Suppose (P, Q) satisfy Definition 1.3 ath n = c log n Q n Q and P satisfies Assumption 2.2 with ∆ n = O(( log n n Q ) 1 2 ∨ α∧1 d ).Then there exists an absolute constant C > 0 such thatP 1 n 2 ∥ Q -Q∥ 2 F ≲ d 2 β∧1 2 log n n Q β∧1 2d ≥ 1 -n -C Q .To parse Theorem 2.3, consider the effect of various parameter choices. First, observe that our upper bound scales quite slowly with n.Even if n is superpolynomial in n Q , e.g. n = n log n Q Q , then log n = O((log n Q ) 2 ) = n o(1)Q , so the overall effect on the error is dominated by the n Q term. Second, the bound is worse in large dimensions, and scales exponentially in 1 d . This kind of scaling also occurs in minimax lower bounds for nonparametric regression (Tsybakov, 2009) , and upper bounds for smooth graphon estimation (Xu, 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 an open problem. Finally notice that a greater smoothness β results in a 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, we will show matching lower and upper bounds for a very structured class of latent variable models, namely, Stochastic Block Models (SBMs). Definition 3.1 (SBM). Let P ∈ [0, 1] n×n . We say P is an (n, k)-SBM if there exist B ∈ [0, 1] k×k and z : [n] → [k] such that for all i, j, P ij = B z(i)z(j) . We refer to z -1 ({j}) as community j ∈[k].We first state a minimax lower bound, proved via Fano's method. Theorem 3.2 (Minimax Lower Bound for SBMs). Let k P ≥ k Q ≥ 1 with k Q dividing k P . Let F be the family of pairs (P, Q) where P is an (n, k P )-SBM, Q is an (n, k Q )-SBM, and (P, Q) satisfy Definition 1.3 at h n = 1/k P . Moreover, suppose S ⊂ [n] is restricted to contain an equal number of nodes from communities 1, 2, . . . , k P of P . Then the minimax rate of estimation is:inf Q∈[0,1] n×n sup (P,Q)∈F E 1 n 2 ∥ Q -Q∥ 2 F ≳ k 2 Q n 2 Q .Note that Definition 1.3 at h n = 1/k P implies that the true community structure of Q coarsens that of P . The condition that k Q divides k P is merely a 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 mollifiers (Gao et al., 2015) . Therefore, we expect that Theorem 3.2 can also be extended to the 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 a minimax lower bound oflog k Q n Qin the regime where the error of recovering the true clustering z dominates. This matches the rate of Gao et al. (2015) , but for estimating all n 2 entries of Q, rather than just the n 2 Q observed entries.Theorem 3.2 suggests that a very simple algorithm might achieve the minimax rate. Namely, use both A P , A Q to learn communities, and then use only A Q to learn inter-community edge probabilities. If (P, Q) are in 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 error rate in the weak consistency regime. To this end, we define the signal-to-noise ratio of an SBM with parameter B ∈ [0, 1] k×k as follows:s := p -q p(1 -q) , where p = min i B ii , q = max i̸ =j B ij . Proposition 3.4 (Error Rate of Algorithm 2). Suppose P, Q ∈ [0, 1] n×n are (n, k P ), (n, k Q )- SBMs with minimum community sizes n (P ) min , n (Q)min respectively. Suppose also that (P, Q) satisfyAlgorithm 2 Q-Estimation for Stochastic Block Models 1: Input: A P ∈ {0, 1} n×n , A Q ∈ {0, 1} n Q ×n Q , S ⊂ [n] s.t. |S| = n Q . 2: Estimate clusterings Z P ∈ {0, 1} n×k P , Z Q ∈ {0, 1} n Q ×k Q using Chen et al. (2014) on A P , A Q respectively. 3: Let W Q ∈ R k Q ×k Q be diagonal with W Q;ii = (1 T Z Q e i ) -1 . 4: Initialize Π ∈ {0, 1} k P ×k Q to be all zeroes. 5: for i ∈ S do 6: Let j P ∈ [k P ], j Q ∈ [k Q ] be the unique column indices at which row i of Z P , Z Q respectively are nonzero. 7: Let Π j P ,j Q = 1. 8: end for 9: Let B Q ∈ [0, 1] k Q ×k Q be the block-average: B Q = W Q Z T Q A Q Z Q W Q . 10: return Q := Z P Π B Q Π T Z T P . Definition 1.3 at h n = n (P )min /n. Then if the signal-to-noise ratios are such that:s P ≥ C( √ n n (P ) min ∨ log 2 (n) n (P ) min ) and s Q ≥ C( √ n Q n min (Q) ∨ log 2 (n Q ) n (Q) min ) for large enough constant C > 0, Algorithm 2 returns Q such that P 1 n 2 ∥ Q -Q∥ 2 F ≲ k 2 Q log(n (Q) min ) n 2 Q ≥ 1 -O 1 n Q . 
experiments: 
 In this section, we test Algorithm 1 against several classes of simulated and real-world networks. Weuse quantile cutoff of h n = log n Q n Q for Algorithm 1 in all experiments. 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 1.(1) Algorithm 2.Given A P ∈ {0, 1} n×n , A Q ∈ {0, 1} n Q ×n Q , let k P = ⌈ √ n⌉, k Q = √ n Q . Compute spectral clusterings Z P , Z Q with k P , k Q clusters respectively. Let J S ∈ {0, 1} n Q ×n is such that J S;ij = 1 if and only if i = j and i ∈ S. The projection Π ∈ R k P ×k Q solves the least- squares problem min Π∈R k P ×k Q ∥J S Z P Π -Z Q ∥ 2 F .We compute the Π differently from steps 4-7 in Algorithm 2 to account for cases where Q is not a true coarsening of P . When Q is a true coarsening of P , this reduces to the procedure in steps 4-7. Given Z P , Π we return Q as in Algorithm 2.(2) Oracle. Suppose that an oracle can access data for Q on all n ≫ n Q nodes as follows. Fix an error probability p ∈ (0, 1). The oracle is given symmetric A ′ Q ∈ {0, 1} n×n with independent entries following a mixture distribution. For all i, j ∈[n] with i < j let X ij ∼ Bernoulli(p) and Y ij ∼ Bernoulli(Q(x i , x j )). Then: A ′ Q;ij = 1 i∈S,j∈S Y ij + (1 -1 i∈S,j∈S )((1 -X ij )Y ij + X ij (1 -Y ij )).Given A ′ Q , the oracle returns the estimate from Universal Singular Value Thresholding on A ′ Q Chatterjee (2015) . As p → 0, the error will approach O(n-2β2β+d ) for a β-smooth network on on d-dimensional latent variables (Xu, 2018) , so the oracle will outperform any transfer algorithm. Simulations. We first test on several classes of simulated networks. For n Q = 50, n = 200, we run 50 independent trials for each setting. We report results for each setting in Table 1 , and visualize estimates for stylized examples in Figure 1 .At a glance, Figure 1 shows that Algorithms 1 and 2 both work well on Stochastic Block Models (first row), that only Algorithm 1 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 f γ (x, y) =x γ +y γ 2where P, Q have different γ. We denote this the γ-Smooth Graphon.Mixed-Membership Stochastic Block Model. Set k P = ⌊ √ n⌋, k Q = √ n Q . The latent space X is the probability simplex X = ∆ k P := {x ∈ [0, 1] k P : i x i = 1} ⊂ R k P .The latent variables x 1 , . . . , x n are iid-Dirichlet distributed with equal weights 1 k P , . . . , 1 k P . ThenP ij = x T i B P x j and Q ij = Π(x i ) T B Q Π(x j ), for connectivity matrices B P ∈ [0, 1] k P ×k P , B Q ∈ [0, 1] k Q ×k Q , and projection Π : ∆ k P → ∆ k Q for a fixed subset of [k P ]. For parameters a, b, ϵ ∈ [0, 1] we generate B ∈ [0, 1] k×k by sampling E ∈ Uniform(-ϵ, ϵ) k×k and set B = clip((a -b)I + b11 T + E, 0, 1).We call this Noisy-MMSB(a, b, ϵ).Latent Distance Model. The latent space is the unit sphereX = S d-1 ⊂ R d . For scale parameter s > 0, we call f s (x, y) = exp(-s∥x -y∥ 2 ) the R d -Latent(s) model.Discussion. When the latent dimension is larger than 1 (the Noisy MMSB and Latent Variable Models), our Algorithm 1 is better than both Algorithm 2 and the Oracle with p = 0.1. Note that Algorithms 1 and 2 usen 2 Q n 2 ≈ 0.06 unbiased edge observations from Q, while the Oracle with p = 0.1 observes (1 -p) n 2 -n 2 Q n 2≈ 0.9 unbiased edge observations in expectation.Real-World Data. Next, we test on two classes of real-world networks. We summarize our dataset characteristics in Table 2 . See Appendix C for further details. 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) . In the left half of Figure 2 , we compare two choices of source organism in estimating the network for BiGG model iJN1463 (Pseudomonas putida). For a good choice of source, Algorithm 1 is competitive with the Oracle at p = 0.1. Additional Experiments and Baseline. In Appendix B.1, we present additional ablation experiments that test the dependence of Algorithms 1 and 2 on all relevant parameters. We compare their performance to the Oracle baseline with p = 0.0 (the non-transfer setting), and an additional baseline adapted from Levin et al. (2022) . 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.  
conclusion: 
 In this paper, we study transfer learning for network estimation in latent variable models. We show that there exists an efficient Algorithm 1 that achieves vanishing error even when n ≥ nω(1)Q , and a simpler Algorithm 2 for SBMs that achieves the minimax rate.There are several interesting directions for future work.First, we believe that Algorithm 1 works for moderately sparse networks with population edge density Ω( 1 √ n ). This is because the concentration of empirical graph distance (Algorithm 1 line 3) requires expected edge density Ω(n -1/2 ) Mao et al. (2021) . It would be interesting to see if a similar approach can work for edge density Ω( log n n ). For example, in the aforementioned paper it is shown that a variation of the graph distance of Definition 1.2 concentrates at expected edge density Ω(n -2/3 ). While is this still far from the Ω( log n n ) regime, it suggests that variations on the graph distance might ensure our Algorithm 1 works for sparser graphs.Second, the case of multiple sources is also interesting. We have focused on the case of one source distribution, as in Cai and Wei (2021) ; Cai and Pu (2024) , but expect that our algorithms can be extended to multiple sources as long as they satisfy Definition 1.3.Question: Does the paper provide open access to the data and code, with sufficient instructions 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 NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark). • The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips.cc/public/guides/CodeSubmissionPolicy) 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.• The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a 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) is recommended, but including URLs to data and code is permitted. 6. Experimental Setting/Details Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to 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 1 in Section 4. Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: For each experiment we run 50 independent trials. We report ±2 standard deviations for the mean-squared error in Table 1 , 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, confidence intervals, or statistical significance tests, at 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 or the standard error of the mean. • It 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 a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [Yes]Justification: As described in Appendix C, we run all experiments on a personal Linux machine with 378GB of CPU/RAM. The total compute time across all results in the paper was less than 2 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, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs 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 it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: We conform with the NeurIPS Code of Ethics with regards to 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 circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This paper presents work whose goal is to advance the field of Machine Learning through foundational research. There are many possible societal consequences of our work, none which we feel must be specifically highlighted here.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. 
 
 Appendix: A.1 Preliminaries Recall Hoeffding's inequality.Lemma A.1 (Hoeffding (1994) ). Let X 1 , . . . , X n be independent random variables such thata i ≤ X i ≤ b i almost surely for all i ∈ [n]. Then P n i=1 (X i -E[Xi]) ≥ t ≤ 2 exp -2t 2 n i=1 (b i -a i ) 2.We also need Bernstein's inequality.Lemma A.2 (Bernstein's Inequality). Let X 1 , . . . , X n be independent mean-zero random variables with |X i | ≤ 1 for all i and n ≥ 5.Then P 1 n n i=1 X i ≥ t ≤ 2 exp -nt 2 2(1 + t 3 ) ≤ 2 exp - nt 2 4 .A.2 Proof of Theorem 2.3Throughout this section, let X = [0, 1] d and µ : X → [0, 1] be the normalized Lebesgue measure.We require the following Lemmata.Lemma A.3. Let υ ∈ (0, 1) and µ : X → [0, 1] be the normalized Lebesgue measure. Then for allx ∈ X , µ(Ball(x, 2υ) ∩ X ) ≥ µ(Ball(0, υ) ∩ X ).Proof. Recall X = [0, 1] d . Fix x ∈ X , υ > 0. Note that µ(Ball(x, υ) ∩ X ) is smallest when x is a vertex of the hypercube; therefore take x ∈ {0, 1} d without loss of generality. Then, note that for each z ∈ Ball(x, υ) ∩ X , we can find (2 d -1) other points z ′ ∈ Ball(x, υ) \ X by reflecting subsets of coordinates of z about x. There are 2 d -1 such nonempty subsets of coordinates. This shows that µ(Ball(x, υ) ∩ X ) ≥ µ(Ball(x, υ))/2 d for all x. Since µ(Ball(x, υ)) ≍ υ d , the conclusion follows.We will repeatedly make use of the concentration of latent positions.Lemma A.4 (Latent Concentration). Let X = [0, 1] d and µ denote the normalized Lebesgue measure on X . Suppose x 1 , . . . , x n ∼ X are sampled iid and uniformly at random from µ. Fix some T ⊂ X such that µ(T ) = v. ThenP vn -|{j ∈ [n] : x j ∈ T }| ≥ 10 log n n ≤ n -10 .Proof. Let X i be an indicator variable that equals 1 if x i ∈ T and zero otherwise. Notice the X i are iid and bounded within [0, 1]. Moreover, i E[Xi] = nµ(T ). Therefore by Hoeffding's inequality, for any t > 0,P[|vn -|{j ∈ [n] : x j ∈ T }|| ≥ t] ≤ 2 exp -2t 2 n .Setting t = 10 log n n gives the result.Corollary A.5. Let ϵ > 0. For i ∈ [n] let ϵ ′ i > 0 be ϵ ′ i := sup{υ > 0 : µ(Ball(x i , υ) ∩ X ) ≤ ϵ. Let T i := Ball(x i , ϵ ′ i ) ∩ X . Let u i (S) := |{j ∈ S : x j ∈ T i }| denote the number of members of S landing in T i . Then P ∀i ∈ [n] : |u i (S) -n Q ϵ| ≤ 10 log n n Q ≥ 1 -n -8 .Proof. Notice that each T i has Lebesgue measure ϵ by definition. Therefore E[ui(S)] = n Q ϵ. Since S has n Q members, setting t = 10 log n n Q in the statement of Lemma A.4 and taking a union bound over all i ∈ [n] gives the conclusion.We will decompose the error of Algorithm 1 into two parts.Proposition A.6. Let Q ∈ [0, 1] n×n be the estimator from Algorithm 1. Then1 n 2 ∥Q -Q∥ 2 F ≤ 2 n 2 i,j∈[n] (J S (i, j) + J B (i, j)),where J S , J B are the smoothing and Bernoulli errors respectively:J S (i, j) := 1 |T i | 2 |T j | 2 r∈Ti,s∈Tj Q ij -Q rs 2 ; J B (i, j) := 1 |T i | 2 |T j | 2 r∈Ti,s∈Tj Q rs -A Q;rs 2 .Controlling the Bernoulli errors is relatively straightforward.Proposition A.7. Let h be the bandwidth of Algorithm 1. The Bernoulli error is at most O( log n m ) with probability ≥ 1 -n -8 , where m = h 2 n 2 Q .Proof. Fix i, j ∈ [n]. We will bound the maximum Bernoulli error J S (i, j) over i, j, which suffices to bound the average. Let m = |T i | |T j |. We want to bound:1 |T i | |T j | r∈Ti,s∈Tj (Q rs -A Q;rs ) 2 .Notice each summand is bounded within ± 1 m . Bernstein's inequality gives:P 1 |T i | |T j | r∈Ti,s∈Tj Q rs -A Q;rs 2 ≥ t 2 ≤ 2 exp(-0.5t 2 m).Setting t = C log n m for large enough C = O(1), a union bound tells us that with probability ≥ 1 -n -8 , the Bernoulli error is bounded by t 2 .Corollary A.8. The Bernoulli error is at most O(log n Q n Q ) with probability ≥ 1 -n -4 Q .The rest of this section is devoted to bounded the smoothing errors J S (i, j).We claim that if nodes are close in the latent space then they are close in graph distance.Proposition A.9. Suppose that ∥xi -x r ∥ ≤ ϵ and Q is β-smooth. Then d Q (i, r) ≤ C 2 β n 3 ϵ 2(β∧1) .Proof. We the use smoothness of Q. By definition there exists β∧1) .C β > 0 such that Q ki -Q kr ≤ C β ∥x i -x r ∥ β∧1 . Therefore, d Q (i, r) = ℓ̸ =i,r (Q 2 ) ℓi -(Q 2 ) ℓr 2 = ℓ̸ =i,r k∈[n] Q ℓk (Q ki -Q kr ) 2 ≤ ℓ̸ =i,r k∈[n] Q 2 ℓk C 2 β ϵ 2(β∧1) ≤ n 3 C 2 β ϵ 2(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 ( 2018)). The volume of a ball of radius r > 0 in R d is√ π d Γ(d/2+1) r d , where Γ(•) is the Γ function. Proposition A.11. Let C d = (Γ( d 2 + 1)) 1/d . Let C 0 , C ′ be constants. If υ n ≥ C • C d ( log n n Q ) 1/d for large enough constant C > 0, and g n = C 0 C 2 β n 2 (υ n ) 2(β∧1) , then with probability ≥ 1 -n -6 for all i ∈ [n] the neighborhood size is |{r : d Q (i, r) ≤ g n }| ≥ C ′ n Q log n n Q .Proof. Fix i ∈ [n] and υ n > 0. Let ϵ i denote the Lebesgue measure of Ball(x i , υ n ) ∩ X . By Lemma A.3 and Lemma A.10, for all i, ϵ i ≥ (√ πυn 2C d ) d = ( 0.5 √ πυn C d ) d . Let ϵ = min i∈[n] ϵ i .By Corollary A.5, with probability ≥ 1 -n -8 , there are n Q ϵ -C log n n Q members j of S such that ∥x i -x j ∥ ≤ υ n . A union bound over i gives the result simultaneously for all i with probability ≥ 1 -n -6 . From Proposition A.9, it follows that for all i ∈ [n],{r ∈ S : d Q (i, r) ≤ C 2 β n 2 (2υ ′ n ) 2(β∧1) } ≥ n Q ϵ -10 log n n Q . Choosing υ n ≥ C • C d ( log n n Q ) 1 2dfor large enough C > 0 gives the conclusion.Next, we show that the empirical graph distance concentrates to the population distance.Proposition A.12. For any arbitrary symmetric P ∈ [0, 1] n×n , we have, for all i, j simultaneously with probability at least ≥ 1 -O(n -8 ), that|d A P (i, j) -d P (i, j)| ≤ O(n 2 log n) + O(n 2.5 log n).Proof. Fix i, j. Let C ij := (A 2 P ) ij . By Mao et al. (2021) A.1, we have C ij = (P 2 ) ij + t ij for an error term t ij such that P[∀i, j :|t ij | ≤ 10 √ n log n] ≥ 1 -n -10 . Then, |d A P (i, j) -d P (i, j)| = ℓ̸ =i,j (C iℓ -C jℓ ) 2 -((P 2 ) iℓ -(P 2 ) jℓ ) 2 = ℓ̸ =i,j (t iℓ + t jℓ ) 2 + 2(t iℓ + t jℓ )((P 2 ) iℓ -(P 2 ) jℓ ) ≤ O(n 2 log n) + O n log n ℓ̸ =i,j (P 2 ) iℓ -(P 2 ) jℓ .Finally, notice that all entries of P 2 are of size O(n), so the conclusion follows.Finally, we will show that taking the restriction of the graph distance T P i to nodes in S ⊂ [n] does not incur too much error.Proposition A.13. Suppose n = n O(1) Q . Then there exists a constant C such that if h 0 ≥ C log n n Q + ∆ n , then for all i, r simultaneously, r ∈ T A P i (h 0 ) implies r ∈ T P i (h 2 ) for some h 2 = O(h) with probability ≥ 1 -O(n -5 ).Proof. Let us introduce the notation T P,S i (h) to denote the bottom h-quantile of {d P (i, j) : j ∈ S}. In this notation, T A P i (h) := T A P ,S i (h) since we restrict the quantile to nodes in S. From Proposition A.12 and Assumption 2.2, we know that ifn ≥ n Q then for h 0 ≤ h 1 -20 log n n -∆ n we have T A P i (h 0 ) ⊆ T P,S i (h 1 ) simultaneously for all i ∈ [n] with probability ≥ 1 -O(n -8). It remains to compare T P,S i (h 1 ) with T P i (h 2 ) for some h 2 .We claim that if h 2 ≥ 30log n Q n Q then P[∀i T P i ∩ S ≥ h 2 n Q -3 n Q log n Q ] ≥ 1 -O(n -2 Q ).To see this, fix i ∈ [n] and consider T P i (h 2 ). For j ∈ S, let X j be the indicator variable:X j = 1 if j ∈ T P i (h 2 ), 0 otherwise. Notice that T P i (h 2 ) ∩ S = j∈S X j . By Hoeffding's inequality, since E[ j∈S X j ] = h 2 n Q and |X j -h 2 | ≤ 1for all j, we haveP T P i (h 2 ) ∩ S -h 2 n Q ≥ 3 n Q log n ≤ 2 exp - 6n 2 Q log n n 2 Q ≤ 2n -6 .Taking a union bound over all i ∈ [n] shows the claim holds with probability ≥ 1 -O(n -5 ).1 ≤ h 2 -3.1 log n n Q then j ∈ T P,S i (h 1 ) implies j ∈ T P i (h 2 ).The conclusion follows with C = 24 log n log n Q = O(1).The ranking condition (Definition 1.3) then allows us to translate between graph distances in A P and Q.Corollary A.14. Suppose that Definition 1.3 holds for (P, Q) ath n = c log n Q n Q + ∆ n , for large enough constant c > 0. Suppose n Q ≤ n ≤ n O(1) Q . Then for h > h n and r ∈ T A P i (h), it follows that r ∈ T Q i (h 3 ) for some h 3 = O(h).The statement holds simultaneously for all i, r with probability ≥ 1 -O(n -5 ).We will decompose smoothing error into a sum of two terms called E S,1 and E S,2 . The control of E S,1 is relatively straightforward. Lemma A.15. The total smoothing error can be bounded with two terms:2 n 2 i,j∈[n] J S (i, j) ≤ E S,1 + E S,2 , where E S,1 := C n max j∈[n],s∈Tj∥Q(e j -e s )∥ 2 2 ;E S,2 := 4 n 2 i∈[n] 1 |T i | E r∈Ti j∈[n] s∈Tj (Q rj -Q rs ) 2 .Proof. Note that2 n 2 i,j∈[n] J S (i, j) = 2 n 2 i,j∈[n]1|T i | 2 |T j | 2 E r∈Ti,s∈Tj Q ij -Q rs 2 ≤ 2 n i∈[n] 1 n |T i | j∈[n] 2 |T j | E r∈Ti,s∈Tj (Q ij -Q rj ) 2 + (Q rj -Q rs ) 2 = 4 n i∈[n] 1 n |T i | E j 1 |T j | r∈Ti (Q ij -Q rj ) 2 + r∈Ti s∈Tj (Q rj -Q rs ) 2 .The second inner summand is precise E S,2 . For E S,1 , notice that|T i | = |T j | = h(n Q -1) by definition. Therefore j 1 |T j | r∈Ti (Q ij -Q rj ) 2 = 1 h(n Q -1) r∈Ti j (Q ij -Q rj ) 2 ≤ 2 max r∈Ti ∥(e i -e r ) T Q∥ 2 2 .We can now bound E S,1 in terms of graph distances. Lemma A.16. The smoothing error term E S,1 can be bounded as follows:E S,1 ≤ 2 n max i∈[n],r∈Ti d Q (i, r) + 2c √ nfor some constant c > 0.Proof. Fix i ∈ [n] and r ∈ T i . We have∥Q(e i -e r )∥ 2 2 ≤ ∥e i -e r ∥ 2 ∥Q T Q(e i -e r )∥ 2 ≤ 2∥Q 2 (e i -e r )∥ 2 .Now we will pass to graph distances. Let e ab := ((Q 2 ) aa -(Q 2 ) ab ) 2 for a, b ∈ [n]. Notice that ∥Q 2 (e i -e r )∥ 2 = d Q (i,n = C log n n Q , for a constant C = O(1), then the smoothing error E S,1 is at mostE S,1 ≤ C 2 C β∧1 d log n Q n Q β∧1 dfor some C 2 = O(1), with probability ≥ 1 -O(n -6 ).Proof. Fix i ∈ [n] and r ∈ T A P i (h n ). By Corollary A.14, if h n ≥ C log n n Q + ∆ n for a large enough constant C > 0, then there exists constant C 2 > 0 such that the following holds. With probability ≥ 1 -O(n -5 ), for all i ∈ [n] and r ∈ S, r ∈ T Q i (C 2 h n ), Let υ n = CC d ( log n n Q ) 1/(i, r) ≤ C 0 C 2 β n 2 (υ n ) 2(β∧1) has size at least C 2 n Q log nn Q .The statement holds for all i simultaneously with probability at least 1 -O(n -6 ). Therefore for all i ∈ [n] and r ∈ T A P i (h n ), we have 1), with probability ≥ 1 -O(n -6 ). By Lemma A.16 we conclude that E S,1 is bounded by 2υ β∧1 n + 2 √ n with the same probability.d Q (i, r) ≤ C 0 C 2 β n 2 (υ n ) 2(β∧1) for some C 0 , C β = O(In this section, we show that the second smoothing error can be controlled in terms of E S,1 . We will need to track the following quantity. Definition A.18 (Membership Count). For r ∈ S and bandwidth h, distance cutoff ϵ, the Pneighborhood count of r is ψ P (r) := {j ∈ [n] : r ∈ T P j (h, ϵ)} .In words, ψ P (r) counts the number of nodes j ∈ [n] such that r lands in the neighborhood of j in our algorithm. While we know that T P j (h) ≤ hn Q 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 r lands in T P j (h) for all j. We will show that there can be no such hub node. Supposing that we can control of the empirical count ψ A P , we show that the smoothing error can be bounded. Proposition A.19. Let h n be the bandwidth. ThenE S,2 ≤ O E S,1 h n n • max r∈[n](ψ A P (r)).Proof. Rearranging terms, we haveE S,2 = 1 n 2 h 2 n 2 Q i,j∈[n],r∈Ti,s∈Tj (Q rj -Q rs ) 2 = 1 n 2 h 2 n 2 Q r∈S ψ A P (r) j,s (Q rj -Q rs ) 2 = n Q n 2 h 2 n 2 Q E r∈S ψ A P (r) j,s (Q rj -Q rs ) 2 = n Q n 2 h 2 n 2 Q E r∈[n] ψ A P (r) j,s (Q rj -Q rs ) 2 ,where the last step follows because j, s do not depend on i, r and because S ⊂ [n] is chosen uniformly at random. Now, we will control the expectation by passing to a row sum, which is handled by E S,1 .ψ A P (r) j,s (Q rj -Q rs ) 2 ≤ max r∈[n] ψ A P (r) n • j∈[n] s∈Tj∥Q(e j -e s )∥ 2 2 .Recall thatn 2 n Q h n E S,1 = Ω j∈[n] s∈Tj∥Q(e j -e s )∥ 2 2 . Hence we conclude thatE S,2 ≤ O E S,1 h n n • max r∈[n](ψ A P (r)).We therefore must show that max r∈S ψ A P (r) ≤ O(hn) with high probability.Proposition A.20 (Population Version). Suppose Assumption 2.2 holds for P with c 1 < c 2 and∆ n = O(( log n n Q ) 1 2 ∨ α∧1 d ). Then if h ≤ C log n n Q for large enough constant C > 0, then we have max r∈S ψ P (r) ≤ O(hn) with probability at least 1 -O(n -8 Q ).Proof. Fix r ∈ S. Let C d be as in Proposition A.11.Suppose that ϵ = C d (C + 10)log n Q n Q 1/d and h = C log n Q n Q. Now, we will claim that for large enough constant c > 0, that ψ P (r) is at most the size of Ball(x r , cϵ) ∩ {x 1 , . . . , x n }.Suppose that c > 0 is a large enough constant. Now suppose that x j is such that ∥x j -x r ∥ ≥ cϵ. We can lower bound the graph distance using Assumption 2.2, as:d P (r, j) := ∥(e r -e j ) T P 2 (I -e r e T r -e j e T j )∥ 2 2 ≥ c 1 n 3 (cϵ) 2(α∧1) -n 3 ∆ n .On the other hand, suppose that i ∈ S is such that ∥x i -x j ∥ ≤ ϵ. Then d P (i, j) ≤ C 2 α n 3 ϵ 2(α∧1) by Proposition A.9. Therefore since ϵ = C d (C + 10) α∧1) .log n Q n Q 1/d and ∆ n = O(( log n n Q ) 1 2 ∨ α∧1 d ), for large enough c 1 > 0 we have d P (r, j) := ∥(e r -e j ) T P 2 (I -e r e T r -e j e T j )∥ 2 2 ≥ c 1 2 n 3 (cϵ) 2(Then, if we choose c > 0 such that c 2(α∧1) > 2C 2 α c1 , then d P (i, j) < d P (r, j). Next, from our choices of h, ϵ, by Corollary A.5, simultaneously for all i ∈ [n] there are at least hn Q nodes in S that have distance ≤ ϵ in latent space from x i , with probablity ≥ 1 -O(n -6 Q ). Therefore, if x r ̸ ∈ Ball(x j , cϵ) ∩ {x 1 , . . . , x n } then r ̸ ∈ T P j (h). This implies that ψ P (r) ≤ |{Ball(x r , 2cϵ) ∩ {x 1 , . . . , x n }|. We can bound the size of this ball with Lemma A.4. Notice the Lebesgue measure of Ball(x r , 2cϵ) ∩ [0, 1] is at most ( 4cϵ C d ) d . Therefore, since x i are chosen iid from the Lebesgue measure on X , with probability at least ≥ 1 -O(n -10 Q ), we have1 n |Ball(x r , 2cϵ) ∩ {x 1 , . . . , x n }| ≤ 2cϵ + 10 log n n .The right-hand side is bounded by O(h) if n ≥ n Q . Taking a union bound over all r ∈ S gives the conclusion.We conclude with the desired upper bound.Proposition A.21 (Bound on ψ A P (r)). Suppose Assumption 2.2 holds for P with c 1 < c 2 and∆ n = O(( log n n Q ) 1 2 ∨ α∧1 d ). Then if h ≤ C 0 log n Q n Qfor small enough constant C 0 , then we havemax r∈S ψ A P (r) ≤ O(hn) with probability at least 1 -O(n -8 Q ).Proof. By Proposition A.12, with probability at least 1 -O(n -8 Q ), we have for all r ∈ S, j ∈ [n] simultaneously thatd A P (r, j) ≥ d P (r, j) -O(n 2.5 log n) ≥ (1 -O( 1 √ n ))d P (r, j).Similarly,d A P (r, j) ≤ (1 + O( 1 √ n ))d P (r, j). We conclude that ψ A P (r) ≤ 2ψ P (r) = O(hn) with probability ≥ 1 -O(n -8 Q ).We can bound C d := Γ( d 2 + 1) ) with probability at least 1 -O(n -8 Q ). Therefore by Proposition A.17,P E S,1 + E S,2 ≤ O C β∧1 d log n n Q β∧1 2d ≥ 1 -O(n -6 Q ).By O( log n Q n Q ) with probability ≥ 1 -O(n -4 Q ).Applying a union bound over the two kinds of error and Lemma A.15 gives the result.Recall the Gilbert-Varshamov code (Guruswami et al., 2019). Theorem A.23 (Gilbert-Varshamov) . Let q ≥ 2 be a prime power. For 0 < ϵ < q-1 q there exists an ϵ-balanced code C ⊂ F n q with rate Ω(ϵ 2 n).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, (D, d) a pseudo-metric space, and θ : P → D a map that extracts the parameters of interest. For a distinguished P ∈ P, let X ∼ P be the data and θ := θ(X) be an estimator for θ(P ).Let r ≥ 2 and P r ⊂ P be a finite hypothesis class of size r. Let α r , β r > 0 be such that for all i ̸ = j, and all P i , P j ∈ P r , d(θ(P i ), θ(P j )) ≥ α r ; KL(P i , P j ) ≤ β r .Thenmax j∈[r] E Pj [d( θ(X), θ(P j ))] ≥ α r 2 1 - β r + log 2 log r .Definition A.25 (Relative Hamming Distance). For x, y ∈ {0, 1} m , we define their relative Hamming distance as follows:d H (x, y) := 1 m |{i ∈ [m] : x i ̸ = y i }| .We will need the following construction of coupled codes. Proposition A.26. Let m P , m Q ≥ 2 and m Q divide m P . There exists a code C ⊂ {0, 1} m P and a projection map Π : {0, Proof of Theorem 3.2. Let m P = n 2 , m Q = n Q 2 , and m = m P . Let C ⊂ {0, 1} m P be the code and Π : {0, 1} m P → {0, 1} m Q the projection map of Prop A.26. For each w ∈ C, we construct a pair of SBMs P w , Q w ∈ R n×n as follows.1} m P → {0, 1} m Q such that if C ′ = {Π(w) : w ∈ C} then C ′ isEach P w , Q w is a stochastic block model with k P , k Q classes respectively. All the P w share the same community structure, namely the lexicographic assignment where nodes 1, 2, . . . , n k P are assigned to community 1, and so on. Similarly all the Q w share the same lexicographic community structure with nodes 1, 2, . . . , n k Q assigned to community 1, and so on. Therefore, there are fixedZ P ∈ {0, 1} n×k P , Z Q ∈ {0, 1} n×k Q , such that for all w ∈ C, there exist A w ∈ R k P ×k P , B w ∈ R k Q ×k Q with P w = Z P A w Z T P , Q w = Z Q B w Z T Q .The A w , B w are defined as follows. Let i, j ∈ [k P ] and i ′ , j ′ ∈ [k Q ] be such that i < j and i ′ < j ′ . Since m P = k P 2 and m Q = k Q 2 , we can identify (i, j) and (i ′ , j ′ ) with indices of [m P ], [m Q ] respectively. Then for fixed δ P , δ Q > 0, the edge connectivity probabilities areA w (i, j) = A w (j, i) := 1/2 if w ij = 0, 1/2 + δ P if w ij = 1; B w (i ′ , j ′ ) = B w (j ′ , i ′ ) := 1/2 if Π(w) i ′ j ′ = 0, 1/2 + δ Q if Π(w) i ′ j ′ = 1.We can set the diagonals of A w , B w to be 1/2 as well.Next, let P r be a family of r = |C| probability measures. For fixed w ∈ C, the corresponding measure is the distribution over data(A P , A Q ) ∈ {0, 1} n×n × {0, 1} n Q ×n Q sampled from (P w , Q w [S, S]).Note that we restrict S to be a fixed subset of [n] .Next, let θ((P w , Q w )) := Q w , and let d(θ((P w , Q w )), θ((P w ′ , Q w ′ ))) := 1 n ∥Q w -Q w ′ ∥ F .We will show that for all w, w ′ ∈ C with w ̸ = w ′ , KL((P w , Q w ), (P w ′ , Q w ′ )) ≤ KL(P w , P w′ ) + KL(Q w , Q w ′ ) ≤ O(n 2 δ 2 P + n 2 Q δ 2 Q ) =: β, d((P w , Q w ), (P w ′ , Q w ′ )) := 1 n ∥Q w -Q w ′ ∥ F ≥ Ω(δ Q ) =: α.For the β claim, by Proposition 4.2 of Gao et al. (2015) , if δ P , δ Q ∈ (0, 1/4), we haveKL((P w , Q w ), (P w ′ , Q w ′ )) ≤ KL(P w , P w ′ ) + KL(Q w , Q w ′ ) ≲ i,j∈[n] (P w (i, j) -P w ′ (i, j)) 2 + (Q w (i, j) -Q w ′ (i, j)) 2 . Next, notice that A w (i, j) ̸ = A w ′ (i, j) if and only if w ij ̸ = w ′ ij . Then for distinct w, w ′ ∈ C, we have d H (w, w ′ ) = Ω(m P ), so i,j∈[n] (P w (i, j) -P w ′ (i, j)) 2 ≲ δ 2 P n 2 k 2 P d H (w, w ′ ) k P 2 ≲ δ 2 P n 2 .The bound for Q w is similar, so this verifies the β claim.Similarly, for the α claim, notice that 1 n ∥Q w -Q w ′ ∥ F ≳ 1 k Q δ 2 Q d H (Π(w), Π(w ′ )) ≥ δ Q k Q d H (Π(w), Π(w ′ )). By Prop A.26, d H (Π(w), Π(w ′ )) = Ω(m Q ) = Ω(k 2 Q ). Therefore α ≤ Ω(δ Q ). Next,Q sup w 1 n ∥ Q -Q w ∥ F ≳ α 1 - β + log 2 0.1 k Q 2 ≥ δ Q 1 - 30n 2 δ 2 P k 2 Q - 30n 2 Q δ 2 Q k 2 Q -o(1) .If we choose δ P = 0.01(k Q n ) and δ Q = 0.01 k Q n Q , then inf Q sup w 1 n 2 ∥ Q -Q w ∥ 2 F ≳ δ 2 Q ≳ k 2 Q n 2 Q . Note that k Q ≤ n Q ≤ n, so δ P , δ Q ∈ (0, 1/4) as desired. Proposition A.27. If h n = min{ 1 k P , 1 k Q } then for all w ∈ C, the pair (P w , Q w ) satisfies Defn 1.3 at h n .Proof. Consider h = h n and some node i ∈ [n]. Suppose that j ̸ = i is in the same P w -community as i, and that ℓ ̸ = i is in a different community. Then notice that d Pw (i, ℓ) ≥ d Pw (i, j). Therefore j ∈ T Pw i (h). Moreover, since h ≤ 1 k P and since the nodes of S ⊂ [n] are equidistributed among the communities 1, 2, . . . , k P , it follows that all members of T Pw i (h) must belong to the same P w -community as i.Therefore, since the communities of Q w are a coarsening of the communities of P w , j ∈ T Qw i( 1 k Q ). Since h ≤ 1k Q , we are done.In this section, we prove a minimax lower bound in the clustering regime for stochastic block models. Theorem A.28. Let Π denote the parameter space of pairs of SBMs (P, Q) on n nodes with k P , k Q communities respectively, such that the cluster structure of Q is a coarsening the cluster structure of P . Then infQ sup (P,Q)∈Π E[ 1 n 2 ∥ Q -Q i ∥ 2 F ] ≳ log k Q n Q .Proof. Let H m ∈ [0, 1] m×m be the Hadamard matrix of order m modified to replace all entries -1 with 0. If m is not a power of two, let H m be defined as follows. Let ℓ = ⌊log 2 m⌋ and let H m ′ ∈ R m/2×m/2 contain H 2 ℓ-1 on its top left block and zeroes elsewhere. LetH m = 00 T H m ′ H T m ′ 00 T .Notice that at most 7 8 fraction of the entries of H m are zero-padded, for any m. Now, letB P = 1 2 11 T + δ P H k P and B Q = 1 2 11 T + δ Q H k Q for some δ P , δ Q ∈ (0, 1/4) to be chosen later. We will define two families of matrices indexed by a finite set T . For i ∈ T , there are some Z i ∈ {0, 1} n×k P and Y i ∈ {0, 1} n×k Q to be specified later. ThenP i = Z i B P Z T i , Q i = Y i B Q Y T i . Now, we define Y i as follows. Let Z n,k Q denote the set of balanced clusterings z : [n] → [k Q ] such that for all i, j ∈ [k Q ], z -1 ({i}) = z -1 ({j}) . Let Z ⊂ Z n,k Q select the z such that for all j ≤ k Q /2, z -1 (j) = { n(j-1) k Q , . . . , nj k Q }.Define a distance on Z as follows. For y, y ′ ∈ Z let Y, Y ′ ∈ {0, 1} n×k Q be the corresponding cluster matrices and let d(y, y Gao et al. (2015) , there exists a packing T 0 ⊂ Z with respect to d such that for all y, y ′ ∈ T 0 , we have |{j : y ′ (j) ̸ = y(j)}| ≥ n/6. Moreover, log |T 0 | ≥ 1 12 n log k Q . Set T = T 0 . For any y i ∈ T 0 , let Y i ∈ {0, 1} n×k Q be the corresponding cluster matrix and then′ ) := 1 n ∥Y B Q Y T - Y ′ B Q (Y ′ ) T ∥ F . By Theorem 2.2 ofQ i = Y i B Q Y T i . Now, to define Z i , take a ∈ [k Q ] and partition y -1 i ({a}) ⊂ [n] into k P /k Q equally sized communities in a uniformly random way. Number these 1, . . . , k P k Q .In this way, we split community 1 of y i into communities 1, . . . , k P k Q of z i , and so on. Define Z i to be the matrix corresponding to z i . Notice that Z i , Y i are both balanced clusterings and that the clustering Y i coarsens that of Z i . Therefore (P i , Q i ) are a pair of heterogeneous symmetric SBMs satisfying Definition 1.3 at h = 1/k Q .Next, we apply Fano's Inequality (Theorem A.24) Gao et al. (2015) gives. Recall log |T | ≥ 1 12 n log k Q . Now, for i, j ∈ T distinct, Prop 4.2 ofD KL ((P i , Q i ), (P j , Q j )) ≤ D KL (P i , P j ) + D KL (Q i , Q j ) ≤ O(n 2 δ 2 P + n 2 Q δ 2 Q ) =: γ 1 .Finally, we can bound:1 n 2 ∥Q i -Q i ′ ∥ 2 F ≥ 1 n 2 n/2<j≤n n k Q ∥(e yi(j) -e y ′ i (j) )B Q ∥ 2 ≥ c 0 δ 2 Q =: γ 2 2 ,where c 0 > 1 is some constant. This follows because there are a constant fraction of j > n/2 such that y i (j) ̸ = y ′ i (j), and any two rows of the Hadamard matrix differ on half their entries. Now, setδ 2 Q = n Q log k Q 10n 2 Q and δ 2 P = log k Q 10n 2 . Since n ≥ n Q , we conclude that inf Q sup i∈T E 1 n 2 ∥ Q -Q i ∥ 2 F ≳ γ 2 2 1 - γ 1 + log 2 (1/12)n log k Q ≳ log k Q n Q .A.5 Proof of Proposition 3.4We first argue that Algorithm 2 perfectly recovers Z P , Z Q with high probability.Theorem A.29 (Implicit in Chen et al. (2014) ). Let M = ZBZ T be an (n, n min , s)-HSBM. Then there exists absolute constant C > 0 such that the Algorithm of Chen et al. ( 2014) can recover Z, up to permutation, with zero error with probability≥ 1 -O(n -8 ) if s ≥ C √ n n min ∨ log 2 (n) √ n min .Proof. The algorithm of Chen et al. (2014) returns a matrix Y ∈ {0, 1} n×n such that Y ij = 1 if and only if i, j are in the same community, with probability ≥ 1 -O(n -8 ). Therefore, to construct a clustering from Y , simply assign the cluster of node 1 to all j ∈ [n] such that Y 1j = 1, and so on. This returns the true Z ∈ {0, 1} n×k up to permutation with probability ≥ 1 -O(n -8 ). Note that k is correctly chosen because Y is equal to a block-diagonal matrix of ones up to permutation, with k blocks.Theorem A.29 implies the following.Proposition A.30. Let Z P , Z Q be as in Algorithm 2. Let s P , s Q be the signal to noise ratios of P, Q respectively. If s P , s Q satisfy the conditions of Theorem A.29 with respect to (n, nmin and (n Q , n (Q) min ) respectively, then then with probability ≥ 1 -O(n -8 Q ), there are permutation matricesU P ∈ {0, 1} k P ×k P , U Q ∈ {0, 1} k Q ×k Q such that Z P = Z P U P and Z Q = Z Q U Q .Next, we want to recover the clustering of Q on all n nodes, not just the n Q nodes that we observe in A Q . This is given by the following.Proposition A.31. 1. If h n = 1/k P and k Q ≤ k P then there exists a unique Π ∈ {0, 1} k P ×k Q such that Z P Π contains the Q-clustering of all nodes in [n]. Let Z Q := Z P Π.2. Let Π be as in Algorithm 2 and U P , U Q be as in Proposition A.30. Then with probability1-O( 1 n Q ), Z P U P Π = Z Q U Q .Proof. Part (1) follows immediately from the SBM structure of P, Q and definition of Definition 1.3.For Part (2), first notice that by Proposition A.30, with probability at least1 -O( 1 n Q ), Algorithm 2 returns the true clusterings Z P = Z P ∈ {0, 1} n×k P and Z Q = Z Q ∈ {0, 1} n Q ×k Q , up to permuta- tion.Now, Algorithm 2 simply takes unions of the clusters of Z P to learn Π. Therefore, let V : R n → R n Q project onto coordinates in S. Then V Z P Π = Z Q . Moreover, by Proposition A.30,Z P = Z P U P and Z Q = Z Q U Q . Hence V Z P U P Π = V Z Q U Q .To remove dependence on V , we need to argue that each Q-cluster has a reprensentatve in S.Let E be the event that at least one Q-cluster has no representative in S. For a fixed j ∈[k Q ], cluster j has no representative in S with probability ≤ 1 - n (Q) min n Q n Q . A union bound implies that P[E] ≤ k Q 1 - n (Q) min n Q n Q ≤ k Q exp(-n (Q) min ) ≤ O(n -1 Q ).The last inequality holds because the condition of Theorem A.29 implies that n(Q) min ≥ Ω( √ n Q ) and k Q ≤ n Q n (Q) min.Finally, we proceed by conditioning on ¬E. Since Z P = Z P U P , we know that for all i ∈ S, the unique j P ∈ [k P ] such that row i, column j P of Z P is nonzero contains its true P -community up toU P . Similarly since Z Q = Z Q U Q , the the unique j Q ∈ [k Q ] such that row i, column j Q of Z P is nonzero contains its true Q-community up to U Q .Therefore the nodes in community j P in P are in community j Q in Q. So, up to permutations U P and U Q , we have Π j P ,j Q = 1. Since we condition on ¬E, each cluster of Q has at least one representative in S, so each columns of Π is nonzero. We conclude thatZ P U P Π = Z Q U Q with probability at least 1 -O(n -1 Q ).We are ready to give the overall error of Proposition 2.Proposition A.32. Suppose thatZ P = Z P , Π = Π in Algorithm 2. Then with probability ≥ 1 -O( 1 n Q ), Algorithm 2 returns a Q ∈ [0, 1] n×n such that 1 n 2 ∥ Q -Q∥ 2 F ≲ k 2 Q log(n (Q) min ) n 2 Q . Proof. By Proposition A.31, with probability ≥ 1 -O( 1 n Q ), we have Z P = Z P U P , Z Q = Z Q U Q , and Z Q U Q = Z P U P Π.We proceed by conditioning on these events.Next, let W Q ∈ R k Q ×k Q be the population version of W Q with W Q;ii = (1 T Z Q e i ) -1 . Then since Z Q = Z Q U Q we have W Q = U T Q W Q U Q . Hence Q = (Z P U P Π)(U T Q W Q U T Q )(Z Q U Q ) T A Q (Z Q U Q )(U T Q W Q U Q )(Z P U P Π) T = Z Q (W Q Z T Q A Q Z Q W Q ) Z T Q . Next, let z Q : [n] → [k Q ] be the ground truth clustering map given by Z Q ∈ {0, 1} n×k Q . Let B Q be defined analogously to B Q in Algorithm 2, but using W Q , Z Q , E[AQ] in place of W Q , Z Q , A Q . Let m i := W -1 Q;ii be the the number of nodes in S belong to community i, and let n i be the the number of nodes in [n] belonging to community i of Q. Then the error of Algorithm 2 is then1 n 2 ∥ Z Q ( B Q -B Q ) Z T Q ∥ 2 F = 1 n 2 i,j∈[k Q ] n i n j r∈z -1 Q ({i})∩S s∈z -1 Q ({j})∩S B Q;ij -A Q;rs m i m j 2 = 1 n 2 i,j∈[k Q ] n i n j m 2 i m 2 j r∈z -1 Q ({i})∩S s∈z -1 Q ({j})∩S B Q;ij -A Q;rs 2 . Next, fix i, j ∈ [k Q ] and let X ij = r∈z -1 Q ({i})∩S s∈z -1 Q ({j})∩S B Q;ij -A Q;rs .If we condition on the clusterings of P, Q being correct then E[BQ;ij -A Q;rs ] = 0. Therefore by Hoeffding's inequality,P(Xij ≥ t 2 ) ≤ 2 exp - 2t 2 m i m j .Setting t 2 = 10 log(m i m j )m i m j implies that with probability at least 1 -k 2 Q min i (m i ) -20 , that the overall error is1 n 2 ∥ Q -Q∥ 2 F ≤ 1 n 2 i,j∈[k Q ] 10 log(m i m j )n i n j m i m j .Finally, note that there exists a constant c 0 > 0 such that for all i ∈[k Q ], m i ≥ c 0 √ n Q and n i ≥ c 0 √ n,by assumption. Note that each m i is a random quantity depending on the choice ofS ⊂ [n] such that E[mi] = n Q n n i .i ∈ [k Q ] imply that that with probability at least ≥ 1 -O(n -8 Q ) that m i ≥ E[mi] -10 log n Q ≥ Ω(E[m i ]). We conclude that 1 n 2 ∥ Q -Q∥ 2 F ≤ O 1 n 2 Q i,j∈[k Q ] 10 log(m i m j ) ≤ O k 2 Q log(n (Q) min ) n Q .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) .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 true for us, we instead compute the following modified MLE based on their estimator from Section 3.3 of Levin et al. (2022) .Q ij = w P w P +w Q A P ;ij + w Q w P +w Q A Q;ij if i, j ∈ S, A P ;ij otherwise.Here 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 Q from Q Chatterjee (2015).Oracle with p = 0.0. In addition to testing the new baseline from Levin et al. (2022) , we also test the Oracle baseline with p = 0.0. As noted in Section 4, 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 n Q does not matter because edges incident to nodes outside of S never get flipped. The Oracle error for β-smooth graphons on d-dimensional latent variables will therefore be O(n -2β 2β+d ) Xu ( 2018), which is less than the error bound of Theorem 2.3. Indeed, we will find that the Oracle our transfer algorithms in the regimes where its theoretical upper bound is better than our theoretical upper bounds.Next, we describe the experimental results. For both experiments, the intra-community edge probabilities are 0.2, 0.9 for P, Q respectively, while the inter-community edge probabilities are 0.1, 0.8 respectively. Points are 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 1 n 2 || Q -Q|| 2 F of both our algorithms' Q and the oracle's Q, Levin et al. (2022) only give theoretical guarantees on the spectral norm || Q -Q|| 2 for their estimator Q. Analyzing the stronger metric of mean-squared error would require different techniques than their paper.In this section, we present additional link prediction experiments on the EMAIL-EU and BIGG MODELS datasets. Unlike Section 4, we tune the sparsity estimate ρ ∈ (0, 1) used in the Universal Singular Value Thresholding step of the Oracle baseline. In particular, we set ρ ∈ (0, 1) to be the mean of the entries of the ground truth target matrix Q ∈ [0, 1] n×n . Note that this value is inaccessible to other algorithms since it requires knowing all the edges of Q.Figures 7 and 8 show the performance of our Algorithms on the EMAIL-EU dataset, and Figures 5 and 6 for the BIGG MODELS dataset. As in the mean-squared error setting (Figure 2 ), we find that Algorithm 1 outperforms 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 8 for the same source but different targets, and Figure 5 shows better performance than Figure 6 for the same target but different sources.In this section, we give further details on the experiments of Section 4.Compute Environment. We run all experiments on 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 (n, 4)-SBM with 0.8 on the diagonal and 0.2 on the off-diagonal of B ∈ R 4×4 . The target is an (n, 2)-SBM with 0.9 on the diagonal and 0.1 on the off-diagonal of B ∈ R 2×2 . For the second and third rows, the source function is Q(x, y) = 1+sin(π(1+3(x+y-1)))(modified from Zhang et al. (2017) ). The sources are P (x, y) = 1 -Q(x, y) and P (x, y) = Q(ϕ(x), y), where ϕ(x) = 0.5 + |x -0.5| if x < 0.5, and 0.5 -|x -0.5| otherwise.Metabolic Networks. We access metabolic models from King et al. (2016) at http://bigg.ucsd. edu. To construct a reasonable set of shared metabolites across the networks, we take the intersection of the node sets for the following BiGG models: iCHOv1, IJN1463, iMM1415, iPC815, iRC1080, (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.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.38th Conference on Neural Information Processing Systems (NeurIPS 2024).In the organism, as opposed to in vitro (in the lab).In fact,Cai and Pu (2024) highlight this exact setting as a direction for future work. 


Decision: There is consensus that this submission should be accepted.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: While this manuscript makes substantial contributions, there are some areas for improvement to enhance its impact:

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

**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.
questions: 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?

2. 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$? 

*Minor suggestions/typos:*
- Line 71:  The order of $|S|$ and $n_Q$ should be swapped, i.e., $n_Q := |S| = o(n)$.
- Lines 102 - 104: The quantifier for $i$ seems missing, e.g., "... *for $i$,* and for all $j \neq i$ ..."
- Line 111: Something should be off here.
- 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$, ..."
- Lines 238 - 239: It seems a line break is needed before "(1) Algorithm 2."
- Lines 244 - 245: This line break should be removed.
- Section 4: Please use $p_{flip}$ instead of $p$ for consistency (or vice versa).
limitations: limitations: This is primarily a theoretical work, and the authors discussed the potential limitations of the work and potential future research directions.
paper_summary: paper_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.  

The authors propose an algorithm with vanishing error under certain conditions and a more simple algorithm for the special case of stochastic block models.
strength_weakness: strength_weakness: 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.

A way to greatly strengthen the work would be to have experiments on domains mentioned in the introduction (i.e. metabolic networks).
questions: 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. 

Would the authors be able to provide experiments on a real-world task -- or if not provide a justification?
limitations: limitations: None that I am aware.
paper_summary: paper_summary: In this paper, the authors address two topics  in random network/graph models:
1. 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.
2. It also proves a minimax lower bound for Stochastic Block Models and show that a simple algorithm achieves this rate.
strength_weakness: strength_weakness: 1. Theorem 1.1 is an informal form of Theorem 2.2, it seems there is no need to repeat.
2. The authors repeatedly use the vague word "suitable", "suitably" in the paper. Many phrases (containing this word) need to be clarified.
questions: questions: In Page 3, line 105: the authors mentioned: relative, not absolute graph distances,  it seems to me this is not defined.
limitations: 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 ..."
. 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.
paper_summary: paper_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.

$$
P_{ij} = f_P(x_i,x_j),\qquad Q_{ij} = f_Q(x_i, x_j)
$$

where  $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.

In 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).

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

In Section 4, Algorithms 1 and 2 are compared with an oracle method on a selection of simulated and real-world datasets.

Complete proofs of all theoretical results are provided in the appendix.
strength_weakness: strength_weakness: - 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. 
- 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.
questions: 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.

**Typos:**
- 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?
- The first letter on line 111 should be capitalised.
limitations: 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.

Comments: title: Response to the Authors' Rebuttal
comment: Dear reviewer BaBd,
Thank you very much for your support.
Dear reviewer TFsn,
Thank you very much for your encouraging words and your strong support. We will include additional discussion on concentration of graph distances in the revision.
Dear reviewer ajJ3,
Thank you very much for taking our rebuttal into account and for raising your score. We will incorporate the new experiments and additional explanations into the revision.
I thank the authors for addressing my questions and concerns.  I trust that the authors will incorporate the new experiment and additional explanations into their revision.  With that understanding, I am inclined to raise my rating to a 7.
I thank the authors for their response and I continue for strongly support this paper.

The discussion on the concentration of different graph distances is very interesting and I would welcome seeing it in the paper. This work could motivate others to develop graph distances which work at lower sparsity levels.
Thank you for your response! I read your rebuttal and other reviewers comments and still want to keep my rating as  7: Accept.
Dear reviewer VhmF,

Thank you very much for taking our rebuttal into account and for raising your score.
I thank the authors for the detailed response. After having read the discussions with the other reviewers, I would like to increase my score to a 6.