Transfer Learning for Latent Variable Network Models

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.

Strengths

- This paper was a joy to read. The problem of transfer-learning on graphs is well-motivated with real-world applications and the relevant literature is reviewed extensively. The reader is guided through each aspect of the problem; every definition feels motivated and mathematical statements are followed by intuition and illustrative examples. The paper is well organised, the writing is exemplary, and proofs are complete, accurate and clear. - This paper addresses a problem which is of great relevance to the machine-learning community, and yet provides what appears to be the first provably consistent algorithm for this problem. The proposed solution, is simple and elegant, and the derived high-probability tail bound and its proof provide a lens into the fundamentally important aspects of this problem. The lower bounds derived in Section 3 show the, despite the simplicity of the method, it is optimal (in the minimax sense) under the SBM, albeit under fairly strong signal-to-noise assumptions (see weaknesses). - The simulated and real data experiments in Section 4 are informative and demonstrate the effectiveness of the approach.

Weaknesses

- One weakness of this paper, is that their setup only considers graphs whose expected node degrees grow linearly in the number of nodes in the graph. In practice, many networks are sparse and it is common in the literature to consider asymptotic regimes in which expected node degrees grow sub-linearly. However, there is sufficient novelty in this paper that I don't see that this can be held against it. The authors claim in their conclusion that they believe their algorithm will work for when node degree are of the order $\Theta(n^{1/2})$, but not down to $\Theta(\log(n))$ (see Questions), but it is not clear *why* they believe this. - 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

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.

Rating

8

Confidence

5

Soundness

4

Presentation

4

Contribution

4

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.

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.

Strengths

This is a theoretical paper that addresses the transfer learning from source to target network in latent variable network models.

Weaknesses

1. Theorem 1.1 is an informal form of Theorem 2.2, it seems there is no need to repeat. 2. The authors repeatedly use the vague word "suitable", "suitably" in the paper. Many phrases (containing this word) need to be clarified.

Questions

In Page 3, line 105: the authors mentioned: relative, not absolute graph distances, it seems to me this is not defined.

Rating

7

Confidence

2

Soundness

3

Presentation

3

Contribution

3

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.

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.

Strengths

The paper is well-written. I particularly enjoyed the introductory sections that help motivate the work. I believe that the problem the authors tackle has value, as it stands mostly as a theoretical contribution. I am unfortunately unable to judge the strength of the contribution of this work as the submission is far from my area of research.

Weaknesses

The experimental part of the paper focuses on purely synthetic tasks. While I understand that, as the authors mention, they believe there aren't direct baselines or datasets for this, I still see this as a potential weakness. A way to greatly strengthen the work would be to have experiments on domains mentioned in the introduction (i.e. metabolic networks).

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?

Rating

6

Confidence

1

Soundness

2

Presentation

3

Contribution

2

Limitations

None that I am aware.

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.

Strengths

This work addresses the significant problem of learning graphs/networks from a small subset of edge data by leveraging knowledge from a source graph. This problem is fundamental and has numerous potential practical applications, such as in biological network estimation and social sciences. The paper considers a simple yet expressive mathematical model and presents key findings and supporting arguments clearly. Although primarily theoretical, the results are complemented by numerical experiments that substantiate the potential of the proposed approach.

Weaknesses

While this manuscript makes substantial contributions, there are some areas for improvement to enhance its impact: **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

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

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

This is primarily a theoretical work, and the authors discussed the potential limitations of the work and potential future research directions.

Response to the Authors' Rebuttal

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.