Transfer Learning for Latent Variable Network Models

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.

Why we believe our Algorithm 1 will work for expected node degree $\\tilde\\Theta(n^{1/2})$.

1. 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})$.

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

Why we believe our Algorithm 1 will not work for expected node degree $\Theta(\log(n))$.

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

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

Clarification of Figure 1.

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

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

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

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

We will rewrite the Figure caption in the revision to avoid confusion.

Typographical errors.

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

[1] Abbe, Emmanuel. "Community detection and stochastic block models: recent developments." Journal of Machine Learning Research 18.177 (2018): 1-86.

We sincerely thank the reviewer for their feedback and for assessing our paper to have high impact. We address their comments in detail below.

Clarification of relative versus absolute graph distances.

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

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

In the revision, we will rewrite line 105 to clarify this point.

What we mean by "the need for a different graph distance" in line 950.

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

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

We will clarify this point in the revision.

Why we select our graph distance.

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

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

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

We will include this point in the revision.

Writing clarity and typographical errors.

We will remove all uses of vague language and typographical errors in the revision.

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.

We test our algorithms on two real-world transfer tasks.

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

We perform experiments on the domains mentioned in the introduction (metabolic network estimation).

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

Comparisons against a new baseline adapted from Levin et al. (JMLR 2022).

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

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 compared to 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 [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].

• 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, 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:

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.

We address their feedback in detail below.

Relevance and applicability of latent variable models in real-world scenarios.

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

Relevance and applicability of the rankings assumption for biological networks.

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.

New ablation experiments in the global rebuttal validate our algorithms' error rates.

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

• Experiments include comparisons to a true oracle with access to full edge data from $Q$. See also the discussion in the next heading.

• Experiments include new comparisons to a proposed algorithm in the literature by Levin et al (JMLR 2022). See global rebuttal for a full description.

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

Oracle with $p = 0.0$ outperforms transfer algorithms in our new experiments.

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

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

The Oracle depends on $n_Q$ if $p > 0$.

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

We will clarify this point in the revision.

The Oracle performs much better on the Email-EU task with $p = 0.0$ than with $p=0.01$.

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

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

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

[1] Ren, Mingyang, et al. "Consistent estimation of the number of communities via regularized network embedding." Biometrics 79.3 (2023): 2404-2416.

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

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

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

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