# Transfer Learning Under High-Dimensional Graph Convolutional Regression
Model for Node Classification

Jiachen Chen1 Danyang Huang2 Liyuan Wang2 Kathryn L. Lunetta1
Debarghya Mukherjee1 Huimin Cheng111footnotemark: 1
1Boston University 2Renmin University of China
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
Corresponding authors.

###### Abstract

Node classification is a fundamental task, but obtaining node classification
labels can be challenging and expensive in many real-world scenarios. Transfer
learning has emerged as a promising solution to address this challenge by
leveraging knowledge from source domains to enhance learning in a target
domain. Existing transfer learning methods for node classification primarily
focus on integrating Graph Convolutional Networks (GCNs) with various transfer
learning techniques. While these approaches have shown promising results, they
often suffer from a lack of theoretical guarantees, restrictive conditions,
and high sensitivity to hyperparameter choices. To overcome these limitations,
we propose a Graph Convolutional Multinomial Logistic Regression (GCR) model
and a transfer learning method based on the GCR model, called Trans-GCR. We
provide theoretical guarantees of the estimate obtained under GCR model in
high-dimensional settings. Moreover, Trans-GCR demonstrates superior empirical
performance, has a low computational cost, and requires fewer hyperparameters
than existing methods.

##  1 Introduction

Network (a.k.a graph) data is ubiquitous in various domains, including social
networks [1], citation networks [2], and biological networks [3, 4]. A
fundamental task in network analysis is node classification [5], which aims to
predict the class labels of a node based on its own features and its
neighboring nodes’ features. Usually, the node features are high-dimensional
[6]. Thus, we focus on high-dimensional settings in this paper. Nevertheless,
obtaining node classification labels can be challenging and expensive in many
real-world scenarios [7]. For example, classifying genes into disease
categories using a gene-gene interaction network faces a scarcity of disease
labels, as experimentally annotating genes is expensive and limited [8].

To address the challenge of limited labeled data, transfer learning, which
uses knowledge from source domains to enhance learning in a target domain, has
emerged as a promising solution [7]. Continuing the aforementioned example,
despite the scarcity of disease labels, abundant functional annotations of
genes exist in curated databases like KEGG pathways [9]. In the existing
literature, various transfer learning methods based on Graph Convolutional
Networks (GCNs) [10, 11, 12, 13] have been proposed to enhance node
classification accuracy. These GCN-based transfer learning methods can be
broadly summarized into three main areas.

First, pre-training and fine-tuning approaches [14, 15, 16, 17, 18, 19], which
usually pre-train a GCN on a large-scale dataset to learn transferable
representations and then fine-tune the pre-trained model on a target task.
While effective, these methods usually lack theoretical guarantees. Second,
theoretical transferability analysis. Researchers have investigated the
theoretical transferability properties of GCNs for graphs sampled from the
same underlying space or graphon model [20, 21, 22, 23]. Despite valuable
theoretical insights, they often assume that the source and target domain are
drawn from exactly the same underlying model, which usually does not hold in
practical scenarios where domain shifts occur. Third, to address the domain
shifts challenge, various domain adaptation techniques have been proposed,
such as unsupervised adaptation [24], local structure transfer [25],
adversarial domain alignment [7], and noise-resistant transfer [26]. Despite
promising results, they often lack theoretical guarantees or can be sensitive
to hyperparameter choices. In summary, existing methods suffer from a lack of
theoretical guarantees, restrictive conditions, and high sensitivity to
hyperparameters.

To address these limitations, we propose a novel statistical transfer learning
framework based on a Graph Convolutional Multinomial Logistic Regression (GCR)
model. The GCR model assumes that the classification label depends on the
graph-aggregated node features (obtained through multiple graph aggregation
layers), followed by a multinomial logistic regression model. Our proposed GCR
model is motivated by the observation in [27], which suggests that removing
nonlinear activation functions (e.g., ReLU) in GCN’s hidden layers achieves
comparable performance to the original GCN architecture. Under the GCR model,
we develop a two-step transfer learning method Trans-GCR. Specifically, we let
$\bm{\beta}^{s}$ and $\bm{\beta}^{t}=\bm{\beta}^{s}+\delta$ denote the GCR’s
high-dimensional sparse model parameters in source and target data
respectively, where $\delta$ measures the domain shift. In the first step, we
obtain the estimate of source domain parameters, denoted as
$\hat{\bm{\beta}}^{s}$, by minimizing the $l_{1}$-regularized negative
likelihood function of the GCR model using source data. In the second step, we
estimate the shift term $\delta$ by substituting $\bm{\beta}^{t}$ with
$\hat{\bm{\beta}}^{s}+\delta$ in the GCR negative likelihood function and
minimizing it using the target data. This step leverages the knowledge learned
from $\hat{\bm{\beta}}^{s}$. Finally, our estimate of the target domain
parameters is given by
$\hat{\bm{\beta}}^{t}=\hat{\bm{\beta}}^{s}+\hat{\delta}$.

Our method enjoys the following advantages: (1) We demonstrate through
extensive empirical studies that our proposed method achieves superior or
comparable performance compared with existing complicated GCN-based transfer
learning approaches for node classification. (2) We provide theoretical
guarantees of the estimate obtained under our proposed GCR model in high-
dimensional settings under mild conditions. (3) By leveraging the simplified
model GCR, our method involves fewer parameters to be trained than more
complex GCN-based models, resulting in reduced computational cost. (4) Our
framework has only two hyperparameters, i.e., the number of graph aggregation
layers and the $l_{1}-$norm penalty strength.

##  2 Graph Convolutional Regression Model

A graph with $n$ nodes is represented by an adjacency matrix
$\mathbf{A}=(\mathbf{A}_{ij})\in\\{0,1\\}^{n\times n}$, $i,j=1,\ldots,n$,
where $\mathbf{A}_{ij}=1$ if there is an edge between nodes $i$ and $j$, and
$\mathbf{A}_{ij}=0$ otherwise. We only consider a graph with no self-loops, so
all diagonal entries of $\mathbf{A}$ are 0. In addition, each node is
associated with a $d$-dimensional covariates and a $C$-dimensional one-hot
class label. The entire covariate matrix is $\mathbf{X}\in\mathbb{R}^{n\times
d}$, and the entire classification label matrix is
$\mathbf{Y}\in\\{0,1\\}^{n\times C}$. Node classification aims to predict
$\mathbf{Y}$ based on $\mathbf{X}$ and $\mathbf{A}$. The normalized adjacency
matrix is

$\mathbf{S}=\tilde{\mathbf{D}}^{-\frac{1}{2}}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-\frac{1}{2}},\mbox{
where }\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}_{n},$ (2.1)

where $\mathbf{I}_{n}$ is an $n\times n$ identity matrix, $\tilde{\mathbf{A}}$
denote the adjacency matrix with added self-connections. Here,
$\tilde{\mathbf{D}}$ is the degree matrix of $\tilde{\mathbf{A}}$, with
diagonal entry $\tilde{\mathbf{D}}_{ii}$ representing the degree of node $i$,
and all off-diagonal elements being zero.

###  2.1 Related Work: Graph Convolutional Networks

GCNs and their variants have gained increasing popularity for node
classification tasks [6, 13]. Among these variants, Simple Graph Convolution
(SGC) [27] is a popular and powerful simplified variant of GCNs. The main idea
behind SGC is to remove the nonlinear activation functions in the hidden
layers of a GCN and only keep the softmax activation in the final layer to
obtain probabilistic outputs. An $M$-layer SGC trains a classifier
$\hat{\mathbf{Y}}=\mbox{Softmax}(\mathbf{S}^{M}\mathbf{X}\hat{\bm{\beta}})$,
where $\hat{\bm{\beta}}\in\mathbb{R}^{d\times C}$ is the learned weight
matrix. SGC enjoys the following advantages: (1) SGC reduces model complexity
and computational burden, making SGC more efficient and scalable. (2) SGC has
only one hyperparameter, the number of layers $M$, reducing tuning complexity
and hyperparameter sensitivity and thus preventing overfitting. (3) Despite
the simplicity, extensive experiments have shown that SGC maintains
competitive or even slightly better performance than GCN [27].

###  2.2 High-Dimensional Graph Convolutional Multinomial Logistic Regression
Model

Motivated by the success of SGC, we propose the GCR model to model the
relationship between $\mathbf{Y}$, $\mathbf{X}$, and $\mathbf{A}$. GCR assumes
that the classification labels are not only affected by their own, but also
their neighbors’ features based on the graph structure captured by the
adjacency matrix. Usually, a normalized adjacency matrix is used; a common
choice is $\mathbf{S}$ in Eq. 2.1. In what follows, we present the GCR model
using $\mathbf{S}$. In GCR, there is a vector of coefficients
$\bm{\beta}_{c}=(\bm{\beta}_{1c},\ldots,\bm{\beta}_{dc})^{T}$ for each
category $c=1,\ldots,C$. To ensure the identifiability of $\bm{\beta}_{c}$, we
take the last category as the reference category, i.e.,
$\bm{\beta}_{C}=\textbf{0}_{d}$. In GCR model, given predictors $\mathbf{X}$
and $\mathbf{A}$, for each node $i=1\ldots,n$, the probability of node $i$’s
classification label $\mathbf{Y}_{i}$ belonging to category $c$ is

$\textstyle\mathbf{P}_{ic}=\mathbb{P}(\mathbf{Y}_{i}=c|\mathbf{X},\mathbf{A})=\frac{{\sf
exp}^{\sum_{j=1}^{n}\mathbf{S}^{M}_{ij}\mathbf{X}_{j}\bm{\beta}_{c}}}{1+\sum_{c=1}^{C-1}{\sf
exp}^{\sum_{j=1}^{n}\mathbf{S}^{M}_{ij}\mathbf{X}_{j}\bm{\beta}_{c}}},c=1,\ldots,C,$
(2.2)

where $\mathbf{X}_{j}=(\mathbf{X}_{j1},\ldots,\mathbf{X}_{jd})$ is the $j$th
row of $\mathbf{X}$, $\mathbf{S}^{M}_{ij}$ is the $(i,j)$th element in
$\mathbf{S}^{M}$, $\mathbf{S}$ is defined in Eq. 2.1, and $M$ is the number of
convolution layer. The sum $\sum_{j=1}^{n}\mathbf{S}^{M}_{ij}\mathbf{X}_{j}$
aggregates neighboring nodal features, encouraging neighboring nodes to have
similar aggregated features, thus having similar classification labels. A
larger value of $M$ enables the model to capture higher-order neighborhood
dependencies. In the high-dimensional setting, where $d$ can be larger than
$n$, we assume $\bm{\beta}_{c}$ to be sparse such that the number of nonzero
elements of $\bm{\beta}_{c}$, denoted by $s<<d$.

Parameter estimation.  Given observed data
$(\mathbf{A},\mathbf{X},\mathbf{Y})$, the parameter estimate
$\hat{\bm{\beta}}=(\hat{\bm{\beta}_{1}},\ldots,\hat{\bm{\beta}}_{C-1})$ is
obtained by minimizing the following negative log-likelihood with $l_{1}$
regularization,
$l(\bm{\beta};\mathbf{Y},\mathbf{X},\mathbf{A})=-\sum_{i=1}^{n}\sum_{c=1}^{C}(\mathbf{Y}_{ic}\log\mathbf{P}_{ic}+(1-\mathbf{Y}_{ic})\log(1-\mathbf{P}_{ic}))+\lambda\sum_{c=1}^{C-1}||\bm{\beta}_{c}||_{1},$
where $\mathbf{P}_{ic}$ is defined in Eq. 2.2, $\bm{\beta}_{c}$ is the $c$th
column of $\bm{\beta}$, $||\cdot||_{1}$ is the $l_{1}-$norm, $\lambda\geq 0$
is a regularization hyperparameter controlling the trade-off between the log-
likelihood and the penalty. $l(\bm{\beta};\mathbf{Y},\mathbf{X},\mathbf{A})$
can be further simplified as

$\textstyle
l(\bm{\beta};\mathbf{Y},\mathbf{X},\mathbf{A})=-\sum_{i=1}^{n}\sum_{c=1}^{C}(\mathbf{Y}_{ic}(\sum_{j=1}^{n}\mathbf{S}_{ij}^{M}\mathbf{X}_{j})\bm{\beta}_{c}-\log(1+e^{\sum_{j=1}^{n}\mathbf{S}_{ij}^{M}\mathbf{X}_{j}\bm{\beta}_{c}}))+\lambda\sum_{c=1}^{C-1}||\bm{\beta}_{c}||_{1}$
(2.3)

To minimize Eq. 2.3, we use the standard coordinate descent algorithm [28],
which iteratively minimizes the objective function with respect to each
coordinate of $\bm{\beta}$, while keeping the others fixed.

##  3 Transfer Learning

In this paper, we consider the following transfer learning problem. Let
$(\mathbf{A}^{(0)},\mathbf{X}^{(0)},\mathbf{Y}^{(0)})$ denote the target data,
where $\mathbf{A}^{(0)}\in\\{0,1\\}^{n_{0}\times n_{0}}$,
$\mathbf{X}^{(0)}\in\mathbb{R}^{n_{0}\times d}$,
$\mathbf{Y}^{(0)}\in\\{0,1\\}^{n_{0}\times C}$. Let
$\bm{\beta}^{(0)}=(\bm{\beta}_{1}^{(0)},\ldots,\bm{\beta}_{C-1}^{(0)})\in\mathbb{R}^{d\times(C-1)}$
denote the true coefficient matrix associated with target data under GCR
model. Let $(\mathbf{A}^{(k)},\mathbf{X}^{(k)},\mathbf{Y}^{(k)})$ denote the
$k$th source data, $k=1,\ldots,K$, where
$\mathbf{A}^{(k)}\in\\{0,1\\}^{n_{k}\times n_{k}}$,
$\mathbf{X}^{(k)}\in\mathbb{R}^{n_{k}\times d}$,
$\mathbf{Y}^{(k)}\in\\{0,1\\}^{n_{k}\times C}$. Let
$\bm{\beta}^{(k)}=(\bm{\beta}_{1}^{(k)},\ldots,\bm{\beta}_{C-1}^{(k)})\in\mathbb{R}^{d\times(C-1)}$
denote the true coefficient matrix associated with the $k$th source data.

The difference between the $k$th source domain’s coefficient and the target
domain’s coefficient is $\delta^{(k)}=\bm{\beta}^{(0)}-\bm{\beta}^{(k)}$. Let
$(C-1)^{-1}\sum_{c=1}^{C-1}||\delta_{c}^{(k)}||_{1}$ measure the domain shift
level of the $k$th source data, where $\delta_{c}^{(k)}$ is the $c$th column
of $\delta^{(k)}$. A source sample is defined as $h-$level transferable if its
domain shift level is lower than a threshold $h$. The set of $h-$level
transferable source data is
$\mathcal{A}_{h}=\\{k:(C-1)^{-1}\sum_{c=1}^{C-1}||\delta_{c}^{(k)}||_{1}\leq
h\\}$. To ensure that transferring sources within the set $\mathcal{A}_{h}$ is
beneficial, $h$ should be reasonably small. In the subsequent sections, we
will abbreviate the notation $\mathcal{A}_{h}$ as $\mathcal{A}$ for brevity
without special emphasis.

###  3.1 Transfer Learning When the Transferable Source Set is Known

In this subsection, we present a transfer learning method under GCR
(abbreviated as Trans-GCR) for the node classification task when the
transferable source set $\mathcal{A}$ is known, i.e., we have prior knowledge
of which source data to utilize. Our method Trans-GCR is motivated by the
transfer learning literature in the conventional regression model (without
considering graph structure) [29, 30, 31]. Figure 1 shows the workflow of
Trans-GCR, which works in the following steps. We first preprocess
$\mathbf{A}^{(k)}$ to obtain the normalized adjacency matrices
$\mathbf{S}^{(k)}$, $k\in\\{0,\mathcal{A}\\}$.

Source sample pooling. We then pooled all source domain data in $\mathcal{A}$
into a single source sample with pooled normalized adjacency matrix
$\mathbf{S}^{\mathcal{A}}\in\mathbb{R}^{n_{\mathcal{A}}\times
n_{\mathcal{A}}}$, node features
$\mathbf{X}^{\mathcal{A}}\in\mathbb{R}^{n_{\mathcal{A}}\times d}$, and labels
$\mathbf{Y}^{\mathcal{\mathcal{A}}}\in\\{0,1\\}^{n_{\mathcal{A}}\times C}$,
where $n_{\mathcal{A}}=\sum_{k\in\mathcal{A}}n_{k}$.
$\mathbf{S}^{\mathcal{A}}$ has a block structure with diagonal blocks
corresponding to the individual $\mathbf{S}^{(k)}$ matrices,
$k\in\mathcal{A}$. The pooled node features $\mathbf{X}^{\mathcal{A}}$ and
labels $\mathbf{Y}^{\mathcal{A}}$ are obtained by concatenating the respective
$\mathbf{X}^{(k)}$ and $\mathbf{Y}^{(k)}$ matrices row-wise,
$k\in\mathcal{A}$. The rationale behind pooling the source samples in
$\mathcal{A}$ together is as follows. Since the source domains in
$\mathcal{A}$ are assumed to be similar to the target domain, with only small
domain shifts, this naturally implies that the source domains in $\mathcal{A}$
have similar underlying model parameters. By pooling the source samples, the
algorithm gains access to a larger effective sample size from the same
distribution, which leads to a more accurate and stable estimate.

Source domain parameter estimation. Let $\bm{\beta}^{\mathcal{A}}$ denote the
latent parameter in GCR that are used to generate
$(\mathbf{Y}^{\mathcal{A}})$. To obtain $\hat{\bm{\beta}}^{\mathcal{A}}$, we
minimize the aforementioned negative log-likelihood with $l_{1}-$norm penalty
in Eq. 2.3 using the pooled source samples. Domain shift estimation. Let
$\delta^{\mathcal{A}}$ denote the difference between the pooled source
parameters $\bm{\beta}^{\mathcal{A}}$ and the target domain parameters
$\bm{\beta}^{(0)}$, i.e.,
$\bm{\beta}^{(0)}=\bm{\beta}^{\mathcal{A}}+\delta^{\mathcal{A}}$. We then
estimate $\delta^{\mathcal{A}}$ by minimizing the following loss function,
which essentially replaces $\bm{\beta}^{(0)}$ with
$\hat{\bm{\beta}}^{\mathcal{A}}+\delta^{\mathcal{A}}$ in the likelihood
function of GCR model using the target data,

$\textstyle-\sum\limits_{i=1}^{n_{0}}\sum_{c=1}^{C}[\mathbf{Y}^{(0)}_{ic}(\sum\limits_{j=1}^{n_{0}}s_{ij}\mathbf{X}^{(0)}_{j})(\hat{\bm{\beta}}_{c}^{\mathcal{A}}+\delta_{c}^{\mathcal{A}})-\psi(\sum\limits_{j=1}^{n_{0}}s_{ij}\mathbf{X}^{(0)}_{j}(\hat{\bm{\beta}}_{c}^{\mathcal{A}}+\delta_{c}^{\mathcal{A}}))]+\lambda\sum\limits_{c=1}^{C-1}||\hat{\bm{\beta}}_{c}^{\mathcal{A}}+\delta_{c}^{\mathcal{A}}||_{1},$
(3.1)

where $\psi(x)=\log{(1+e^{x})},s_{ij}$ is the $(i,j)$th element of
$(\mathbf{S}^{(0)})^{M}$, $\hat{\bm{\beta}}_{c}^{\mathcal{A}}$ and
$\delta_{c}^{\mathcal{A}}$ are the $c$th column of
$\hat{\bm{\beta}}^{\mathcal{A}}$ and $\delta^{\mathcal{A}}$, respectively.
This reformulation transforms the unknown parameter from $\bm{\beta}^{(0)}$ to
$\delta^{\mathcal{A}}$. Finally, the target domain parameter estimate is
$\hat{\bm{\beta}}^{(0)}=\hat{\bm{\beta}}^{\mathcal{A}}+\hat{\delta}^{\mathcal{A}}$,
combining the estimated source domain parameters and the learned domain shift.

We summarize our procedure in Algorithm 1 in Appendix F, which involves two
hyperparameters: the graph convolution layers $M$ and the $l_{1}-$norm penalty
strength $\lambda$. When implementing Trans-GCR, we apply cross-validation
procedures to select these hyperparameters.

Figure 1: Workflow of Trans-GCR. We first pool all source domains to get an
estimate $\hat{\bm{\beta}}^{\mathcal{A}}$. We then use target data and the
knowledge from $\hat{\bm{\beta}}^{\mathcal{A}}$ to estimate domain shift
$\hat{\delta}^{\mathcal{A}}$. The final estimate for the target data is
$\hat{\bm{\beta}}^{(0)}=\hat{\bm{\beta}}^{\mathcal{A}}+\hat{\delta}^{\mathcal{A}}$.

###  3.2 Transferable Source Detection

In section 3.1, we presented a method when the transferable set $\mathcal{A}$
is known. Nevertheless, in real applications, such prior knowledge might be
unavailable. When the source domain differs significantly from the target
domain, negative transfer can occur, leading to decreased performance on the
target task [30, 31]. To address this issue, we propose a data-driven cross-
validation approach to select the transferable set $\mathcal{A}$
automatically.

Our method begins by partitioning nodes in the target data into $V$ folds,
i.e., $s_{1},\ldots,s_{V}$. For each fold $v$, the labels of nodes in $s_{v}$
in the target data (denoted as $\mathbf{Y}_{s_{v}}^{(0)}$) are held out as the
testing target data, while the labels in the remaining folds
$\mathbf{Y}_{-s_{v}}^{(0)}$ serve as the training target data. We then apply
the transfer learning Algorithm 1 using the $k$th source data
$\\{\mathbf{A}^{(k)},\mathbf{X}^{(k)},\mathbf{Y}^{(k)}\\}$ and training target
data $\\{\mathbf{A}^{(0)},\mathbf{X}^{(0)},\mathbf{Y}_{-s_{v}}^{(0)}\\}$ to
obtain the estimate $\hat{\bm{\beta}}_{vk}^{(0)}$ for the target data. Note
that we use the entire network structure of the target data $\mathbf{A}^{(0)}$
and all node covariates $\mathbf{X}^{(0)}$ to obtain aggregated features.
However, we only use the classification labels of the training nodes
$\mathbf{Y}_{-s_{v}}^{(0)}$ when minimizing the negative log-likelihood in Eq.
2.3 during the estimation process.

Using the model estimate $\hat{\bm{\beta}}_{vk}^{(0)}$, we predict labels for
the testing nodes in the target data, calculating
$\hat{\mathbb{P}}(\mathbf{Y}_{i}^{(0)}=c)$, $i\in s_{v}$. The model’s
performance is assessed through the negative log-likelihood,
$\mbox{NL}_{v}^{(k)}=-\sum_{i\in
s_{v}}\sum_{c=1}^{C}(\mathbf{Y}^{(0)}_{ic}\log\hat{\mathbb{P}}(\mathbf{Y}^{(0)}_{i}=c)+(1-\mathbf{Y}^{(0)}_{ic})\log(1-\hat{\mathbb{P}}(\mathbf{Y}^{(0)}_{i}=c))$.
We then average $\mbox{NL}_{v}^{(k)}$ across all $V$ folds, yielding
$\mbox{NL}^{(k)}=V^{-1}\sum_{v=1}^{V}\mbox{NL}_{v}^{(k)}$. A lower score of
$\mbox{NL}^{(k)}$ indicates higher transferability of the $k$th source data.
We rank the $K$ sources by their corresponding $\mbox{NL}^{(k)}$ values and
select the top $L$ sources with the lowest scores as the estimated
transferable set $\hat{\mathcal{A}}$, where $L$ is a user-defined
hyperparameter specifying the number of source data to include. We summarize
our procedure in Algorithm 2 in the Appendix F.

##  4 Theoretical Properties

In this section, we present our main theoretical results. Recall that in this
paper, we proposed a GCR model to account for the network dependency between
observations, and a transfer learning method Trans-GCR to promote the
estimation of the target data utilizing knowledge from source data.
Establishing theoretical guarantees for the GCR model under network dependency
alone is extremely challenging as our data i) is high-dimensional (i.e., the
number of covariates can be much larger than the number of samples) and ii)
admits a network dependency among the observations. This dependency prevents
the application of standard concentration results, valid only for i.i.d. data.
Consequently, a careful mathematical analysis is necessary. In this paper, we
take a step towards that goal by rigorously analyzing the theoretical
properties of $\hat{\bm{\beta}}$ obtained by minimizing the loss function in
Eq. 2.2 when $\mathbf{A}$ is generated from an Erdős–Rényi (ER) random graph
model with parameter $p$, $M=1$ (i.e., one convolutional layer), given
observed data $(\mathbf{A},\mathbf{X},\mathbf{Y})$. For simplicity and ease of
presentation, this section focuses on results for the case where $C=2$
corresponds to a two-class classification problem. Nevertheless, our
theoretical results can be easily generalized to the multiclass cases. Under
ER model, the expected degree of each node is $np$. In what follows, we build
theoretical guarantees under the normalized adjacency matrix
$\mathbf{A}\mathbf{X}/\sqrt{np}$. To ease presentations, we let
$\mathbf{Z}=(\mathbf{A}\mathbf{X})/\sqrt{np}$ (replace $p$ by $\hat{p}$ when
uknown). We would like to highlight that rows of $\mathbf{Z}$ are not
independent. Let $\|{\bm{\beta}}^{(0)}\|_{0}=s$ for some $s\ll d$. The
estimate $\hat{\bm{\beta}}$ is obtained by minimizing the loss function in Eq.
2.2, which can further rewritten using $\mathbf{Z}$, as shown below,

$\textstyle\hat{\bm{\beta}}={\arg\min}_{\bm{\beta}}\left\\{-\sum_{i=1}^{n}\left[\mathbf{Y}_{i}\mathbf{Z}_{i}^{\top}\bm{\beta}-\log{(1+{\sf
exp}{(\mathbf{Z}_{i}^{\top}\bm{\beta})})}\right]+\lambda\|\bm{\beta}\|_{1}\right\\},$
(4.1)

where $\mathbf{Z}_{i}$ is the $i$th row of $\mathbf{Z}$. The key difference
between our analysis of $\hat{\bm{\beta}}$ and that of a standard high
dimensional generalized linear model (e.g., [32]) is precisely the dependence
among observations. Below, we present the assumptions required to establish
the theoretical guarantees of our penalized estimator $\hat{\bm{\beta}}$:

######  Assumption 4.1.

We assume $\mathbf{X}_{i}$’s are generated independently from a sub-gaussian
distribution with parameter $\sigma_{\mathbf{X}}$, i.e., $\mathbb{E}[{\sf
exp}{(\lambda a^{\top}\mathbf{X}_{i})}]\leq{\sf
exp}{(\lambda^{2}\sigma_{\mathbf{X}}^{2}/2)}$ for all $\lambda\in{\mathbb{R}}$
and for all $a\in S^{p-1}$. Let $\Sigma_{\mathbf{X}}$ be the covariance matrix
of $\mathbf{X}_{i}$. Assume that
$\lambda_{\min}(\Sigma_{\mathbf{X}})\geq\kappa_{l}>0$ and
$\max_{j}\Sigma_{\mathbf{X},jj}\leq\sigma_{+}$ for some constant
$(\kappa_{l},\sigma_{+})$.

######  Assumption 4.2 (Network connectivity).

The network connectivity parameter $p$ of the Erdős–Rényi random graph
$\mathbf{A}$ satisfies $(np)/\log{n}\to\infty$, and $p\log{d}\to 0$ as
$n\rightarrow\infty$.

######  Assumption 4.3 (Sparsity).

The sparsity parameter $s$ of ${\bm{\beta}}^{(0)}$ satisfies: $\textstyle
s\frac{\log^{2}{d}}{n}\frac{(1-2p)}{4p\log{\left((1-p)/p\right)}}=o(1)$.

All three assumptions above are quite standard in the literature on the
analysis of high-dimensional linear and generalized linear models. Assumption
4.1 requires the covariates to be sub-gaussian, a ubiquitous assumption, which
is often needed to deal with ultra-dimensional setup (i.e., $d$ can be as
large as $e^{n^{\gamma}}$ for some $\gamma<1$) (see Chapter 6 of [33] for
details). One may relax this assumption as the cost of the trade-off between
$d$ and $n$; the thicker the tail of $\mathbf{X}$, the more stringent
condition is needed on $d$ for estimation, or one may use robust loss function
([34]). Assumption 4.2 is also a standard assumption in the literature of
network estimation, which merely assumes $p$ to be (slightly) larger than
$n^{-1}$ in order [35]. As for Assumption 4.3, in standard i.i.d. setup we
require $s\log{d}/n\to 0$. However, here, our condition is slightly different;
we have an additional factor involving a factor of $p$. Whether this
dependence is optimal is out of the scope of this paper. Given these
assumptions, we are now ready to state our main theorem:

######  Theorem 4.4.

Under Assumption 4.1-4.3, the $\ell_{1}$-penalized estimator
$\hat{\bm{\beta}}$ obtained in (4.1) satisfies;

$\textstyle\|\hat{\bm{\beta}}-{\bm{\beta}}^{(0)}\|_{2}^{2}\leq
c\frac{s\log{d}}{n}$

for some constant $c>0$ with probability $1-g(n,p,d)$, where $g(n,p,d)$ goes
to $0$ as $n\rightarrow\infty$, mentioned explicitly in the proof.

The proof of the theorem is deferred to the Appendix. One of the main
technical challenges lies in establishing a condition equivalent to the
standard restricted strong convexity (RSC) or restricted eigenvalue (RE)
condition in the presence of network dependency. This task is difficult even
in an i.i.d. setup; see [36, 37, 38, 39] for related references. The modified
RSC condition is presented in Lemma B.1, which is of independent interest.

######  Remark 4.5.

It may seem surprising that the convergence rate of $\hat{\bm{\beta}}$, as
established in Theorem 4.4 does not depend on $p$. This is precisely because
we have appropriately scaled $\mathbf{Z}=(\mathbf{A}\mathbf{X})/\sqrt{np}$ by
$p$. If we change the scale, i.e., say we use symmetric normalized Laplacian
$\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}$, then the effective calling
would be $\mathbf{Z}=(\mathbf{A}\mathbf{X})/np$. In that case, the estimation
rate of $\hat{\bm{\beta}}$ would depend on $p$, and this dependence can be
easily quantified by carefully tracking the steps of our proof. However, as
this involves technical algebra without adding further insight, we refrain
from pursuing it here.

######  Remark 4.6.

Our theorem precisely quantifies the estimation rate of $\bm{\beta}^{(0)}$ in
a single domain, which can be viewed as the estimation rate using only data
from the target domain. Recently, estimating $\bm{\beta}^{(0)}$ using related
source samples under the high-dimensional generalized linear model setup has
been explored by [31, 40]. As previously mentioned, extending these ideas to
incorporate network dependency is quite challenging. However, we have
conjectured an estimation rate for $\bm{\beta}^{(0)}$ obtained using Trans-
GCR. See Appendix D for details.

######  Remark 4.7.

Although in our theory we have assumed all the entries of $\mathbf{A}$ are
generated independently from ${\sf Ber}(p)$, Theorem 4.4 continues to hold
under the self-loop (resp. no self-loop), i.e. if we set $\mathbf{A}_{ii}=1$
(resp. $\mathbf{A}_{ii}=0$) and generate off-diagonal elements from ${\sf
Ber}(p)$, with different constant $c^{\prime}$ instead of $c$. In the proof,
we have pointed out the required modifications precisely to adapt proof when
i) we have self-loop, and ii) $p$ is unknown and estimated from the data.

##  5 Simulation Studies

Simulation setup. For the $k$th dataset, we generate simulation data in the
following steps. We first generate node features
$\mathbf{X}^{(k)}\in\mathbb{R}^{n_{k}\times d}$ from i.i.d. Gaussian with mean
zero and identity covariance matrix. We then generate adjacency matrix
$\mathbf{A}^{(k)}\in\\{0,1\\}^{n_{k}\times n_{k}}$ using the ER random graph
model with parameter $p_{k}$. We then generate a $C$-classes response
$\mathbf{Y}^{(k)}\in\\{0,1\\}^{n_{k}\times C}$ using Eq. 2.2 with $M=1$.

In this simulation, we consider a three-classes outcome, i.e., $C=3$. For the
target data, we set the target sample size $n_{0}=200$. We consider high-
dimensional sparse node covariates, where the number of covariates is $d=500$,
and the number of non-zero covariates in $\bm{\beta}_{c}^{(0)}$ is $s=50$. We
set non-zero model coefficients for the first $s$ covariates, i.e.,
$\bm{\beta}_{1}^{(0)}=(0.4\cdot\textbf{1}_{s},\textbf{0}_{d-s})$,
$\bm{\beta}_{2}^{(0)}=(0.5\cdot\textbf{1}_{s},\textbf{0}_{d-s})$, where
$\textbf{1}_{s}$ has all $s$ elements 1 and $\textbf{0}_{d-s}$ has all $d-s$
elements 0. For the $k$th source data, we set
$\bm{\beta}_{1}^{(k)}=\bm{\beta}_{1}^{(0)}-(h_{k}\cdot\textbf{1}_{s},\textbf{0}_{d-s})$,
$\bm{\beta}_{2}^{(k)}=\bm{\beta}_{2}^{(0)}+(h_{k}\cdot\textbf{1}_{s},\textbf{0}_{d-s})$,
$k=1,\ldots,K$. For the first five sources, we set $h_{k}=h$ where $h$ is a
small value and consider varying $h$ to study its effect. For the subsequent
sources, $h_{k}$ is set to be a large value, i.e., 10. We regard the first
five sources as transferable datasets, that is,
$\mathcal{A}=\\{1,\ldots,5\\}$, and view the remaining sources as non-
transferable datasets. We set the source sample sizes as the same value, i.e.,
$n_{1}=\ldots=n_{K}=n$.

Evaluation metric and baselines. We evaluate the performance by calculating
the mean squared estimation errors (MSE) between the estimated coefficients
and the true target coefficient, i.e.,
$\mbox{MSE}=\frac{1}{2d}(||\hat{\bm{\beta}}_{1}^{(0)}-\bm{\beta}_{1}^{(0)}||_{F}^{2}+||\hat{\bm{\beta}}_{2}^{(0)}-\bm{\beta}_{2}^{(0)}||_{F}^{2})$.
All experiments are replicated 100 times to calculate the averaged MSE. We
compare our method Trans-GCR with two baselines: (1) GCR which uses target
data only, and (2) Naive transfer learning (Naive TL), which pools the source
and target data together in a brute-force way and trains a single model on the
combined dataset to obtain an estimation.

Note that additional simulation results can be found in Appendix E.1.
Specifically, in Figures S1 and S2, we also show our method’s superior
performance when the target network is generated by other random graph models,
including stochastic block model (SBM) and graphon models. In Figure S3, we
also show our method’s superior performance with multiple convolution layers,
$M=2$.

###  5.1 Simulation Results When the Transferable Source Set is Known

We first show results when $\mathcal{A}=\\{1,\ldots,5\\}$ is known, i.e., we
will only use the first five source data to perform transfer learning.

Asymptotic performance. To investigate the asymptotic performance of the
Trans-GCR method, we vary the sample size of source data
$n\in\\{100,\ldots,1000\\}$ while fixing source-target domain shift $h=1$,
fixing the ER edge probability in the target data and source data
$p_{0}=\ldots=p_{5}=0.05$. Figure 3(a) shows that our method Trans-GCR
demonstrates a marked decrease in MSE as the source data sample size
increases. Naive TL also shows a decreasing MSE trend but at a significantly
higher error rate compared with Trans-GCR. In contrast, the GCR method has the
highest MSE across all source sample sizes and remains unchanged since it does
not utilize source data information.

Effect of source-target domain shift. To investigate the impact of $h$, we
vary $h\in\\{1,\ldots,10\\}$, while fixing source sample size $n=600$, and
fixing the ER edge probability $p_{0}=\ldots=p_{5}=0.05$. Figure 3(b) reveals
that the MSE of Trans-GCR and Naive TL increases gradually as the source-
target domain shift grows, which is expected since a larger shift implies
reduced transferability between source and target domains. When $h$ increases
to 10, the advantage of transfer learning disappears.

Effect of source-target network density discrepancy. To investigate the impact
of the network density difference between the source and target networks, we
vary the ER edge probability in the source data
$p_{1}=\ldots=p_{5}\in\\{0.01,\ldots,0.1\\}$ while fixing the ER edge
probability in the target data as 0.05, and fixing $n=600$, $h=1$. Figure 3(c)
reveals that both Trans-GCR and Naive TL show a slight U-shape trend, with the
best results achieved when the source and target network densities are
similar. As the density difference increases in either direction, the
performance degrades. While network density discrepancies can impact the
performance of transfer learning approaches, Trans-GCR demonstrates strong
robustness in handling these differences, consistently outperforming GCR and
Naive TL across the range of density variations tested.

Figure 2:  AUC for detecting transferable sources.

Effect of source-target network distribution discrepancy. To investigate the
impact of distribution discrepancy between source and target networks, we
consider a scenario where the target network is generated from the ER model
with parameter 0.05 while the source networks are generated from a balanced
two-block SBM. In the SBM, we fix the between-community connection probability
as 0.05 and the vary within-community probability from 0.05 to 0.14. When the
within-community probability is 0.05, the SBM becomes identical to the
ER(0.05) model used for the target network. We fix the source sample size
$n=600$, and source-target domain shift $h=1$. Figure 3(d) shows that the MSE
of the Trans-GCR method slightly increases as the distribution discrepancy
increases. In contrast, the MSE of Naive TL shows a clear upward trend.

Figure 3: Performance comparison (MSE) of Trans-GCR (red), GCR (black), Naive
TL (blue) across varying (a) Source sample size, (b) Source-target gap $h$,
(c) Source network density (0.05 means identical densities) (d) Source network
within-community probability (higher value means more discrepancy).

###  5.2 Trasnferable Source Detection Results

Given $K$ source domains, we apply Algorithm 2 to obtain the transferability
score for each source domain. Here, we use a three-fold cross-validation. To
assess the effectiveness of these scores in identifying transferable sources,
we treat the task as a binary classification problem and compute the AUC (area
under the ROC curve). A higher AUC indicates better performance in
distinguishing transferable and non-transferable sources based on the
transferability scores. Following the aforementioned setting, the first five
source domains are defined as transferable. We vary the number of total
candidate source domains $K$ from 6 to 10, while fixing ER edge probability
$p_{0}=\ldots=p_{K}=0.05$, and source data sample size $n=600$. Figure 2 shows
that as $K$ increases, indicating a more challenging detection task, the AUC
slightly decreases. Despite this, the AUC consistently remains above 0.9,
showcasing the method’s robustness and accuracy in identifying transferable
source domains.

##  6 Real Data Experiments

Data description. We conduct experiments on three widely-used real-world
citation networks [41, 42]: (1) DBLPv7 (abbreviated as D), containing 5484
nodes and 8130 edges, extracted from the DBLP database; (2) Citationv1
(abbreviated as C), containing 8935 nodes and 15113 edges, obtained from the
Microsoft Academic Graph database; (3) ACMv9 (abbreviated as A), containing
9360 nodes and 15602 edges, derived from the ACM digital library. In these
networks, each node represents a paper, and the adjacency matrix $\mathbf{A}$
encodes the citation relationships between papers. The bag-of-words attribute
vectors $\mathbf{X}$ are derived from keywords extracted from paper titles,
with a combined vocabulary of 6775 unique attributes across all networks.
Thus, the feature dimension of $\mathbf{X}$ is 6775.

Figure 4:  Averaged computational time (seconds) of different methods.

Each paper is associated with a label belonging to one of these five classes:
Databases, Artificial Intelligence, Computer Vision, Information Security, and
Networking.

Transfer learning tasks. To evaluate the effectiveness of our method Trans-
GCR, we conduct nine transfer learning tasks between different source and
target: (1) C $\rightarrow$ D, (2) A $\rightarrow$ D, (3) C & A $\rightarrow$
D, (4) D $\rightarrow$ C, (5) A $\rightarrow$ C, (6) D & A $\rightarrow$ C,
(7) D $\rightarrow$ A, (8) C $\rightarrow$ A, and (9) D & C $\rightarrow$ A.

Baselines. We compare our proposed method with several baselines: (1) AdaGCN
[7], which is a GCN-based domain adaption method, and Naive TL methods based
on (2) our proposed GCR model, and GCN-related methods, including (3) Node2vec
[43], (4) GraphSAGE [6], (5) GCN [13], (6) APPNP [44], (7) attri2vec [45], (8)
SGC [27], and (9) GAT [46]. Recall that Naive TL refers to pooling the source
and target data together in a brute-force way and training a single model on
the combined dataset. We used the default hyperparameter settings provided in
the original implementations for the baseline methods.

Evaluation. We evaluate the performance of our Trans-GCR method using two
standard metrics: micro-F1 and macro-F1 scores [7]. These metrics assess the
model’s predictions on the testing subset of the target data. All experiments
are replicated 10 times.

Our evaluation aims to answer three key questions: (1) How does the
performance of our Trans-GCR method compare with other baseline methods, given
the fixed training rate? (2) How does the computational time of our Trans-GCR
method compare with other baseline methods? (3) How does the training rate of
the source and target networks affect the performance of Trans-GCR? Here, the
training rate of a network refers to the proportion of nodes whose labels were
utilized for training the model.

Results. (1) Performance comparison with fixed training rate. Table 1 shows
the averaged micro-F1 when a 75% source training and a 3% target training
rate. Macro-F1 scores and standard deviation results are reported in Tables S2
and S3. The results demonstrate that Trans-GCR consistently outperforms the
baseline methods across all tasks. AdaGCN generally performs better than naive
TL methods, indicating the advantages of domain adaptation. However, despite
AdaGCN’s good performance, it suffers from high computational costs, which we
will discuss later. Notably, Trans-GCR performs better with two source domains
(e.g., C & A $\rightarrow$ D) than with one (e.g., C $\rightarrow$ D). This
suggests that Trans-GCR effectively leverages complementary information from
multiple source domains, enhancing transfer learning performance on the target
task. (2) Computational time. Figure 4 shows that Trans-GCR has significantly
lower computational time than AdaGCN, demonstrating its efficiency.

Figure 5:  (a) Varying source training rates (b) Varying target training
rates.

(3) Effect of training rate. Figure 5(a) shows the micro-F1 for the transfer
learning tasks D $\rightarrow$ C, as the source training rate increases from
1% to 90%, while the target rate is fixed at 3%. Figure 5(b) depicts the
micro-F1 results as the target training rate increases from 1% to 10%, while
fixing the source training rate at 75%. As we can see, our proposed method
Trans-GCR consistently outperforms AdaGCN across all different source training
rates and target training rates, while increasing rates leads to improved
performance of our method. Results on other transfer learning tasks, leading
to similar conclusions, are shown in Appendix E.2.

Table 1: Averaged Micro F1 score (%) of various methods, over 10 replicates,
with source training rate fixed at 0.75 and target training rate fixed at
0.03.

Target | Source | Trans-GCR | GCR | AdaGCN | node2vec | GraphSAGE | GCN | APPNP | attri2vec | SGC | GAT
---|---|---|---|---|---|---|---|---|---|---|---
D | C | 76.53 | 72.30 | 74.42 | 66.55 | 69.78 | 71.59 | 73.10 | 67.64 | 72.12 | 71.74
A | 75.16 | 69.75 | 74.52 | 56.66 | 65.82 | 69.12 | 68.23 | 63.15 | 68.64 | 67.34
C&A | 76.61 | 70.09 | 73.93 | 52.09 | 56.22 | 63.97 | 70.31 | 65.75 | 71.31 | 62.48
C | D | 78.99 | 72.82 | 77.40 | 62.34 | 69.63 | 72.64 | 75.26 | 73.33 | 75.06 | 73.17
A | 80.37 | 77.16 | 79.29 | 63.17 | 70.64 | 73.85 | 75.86 | 69.91 | 76.73 | 73.39
D&A | 80.58 | 77.23 | 78.91 | 50.93 | 60.77 | 70.53 | 74.81 | 71.85 | 77.31 | 68.83
A | D | 72.61 | 69.54 | 72.35 | 54.36 | 62.59 | 66.87 | 66.56 | 62.92 | 65.55 | 66.67
C | 73.56 | 71.17 | 73.32 | 61.53 | 65.20 | 66.10 | 66.45 | 64.23 | 71.26 | 67.79
D&C | 73.78 | 71.32 | 73.26 | 49.27 | 57.11 | 63.19 | 64.81 | 63.42 | 70.18 | 62.69

##  7 Discussion

In this paper, we introduce the GCR model to capture the relationship between
node classification labels ($\mathbf{Y}$), network structure ($\mathbf{A}$),
and node covariates ( $\mathbf{X}$). We then propose Trans-GCR, a transfer
learning method that enhances estimation in the target domain using knowledge
from the source domain. Despite its strong empirical performance and
theoretical benefits, our method has limitations that need further research.
Firstly, our theoretical results are limited to the ER random graph model.
While we show empirical success with other models like SBM and graphon,
theoretical validation for these models is still needed. Secondly, the GCR
model assumes a linear relationship between graph convolutional features and
the log odds ratio; extending this to nonlinear models would be valuable.
Thirdly, our source detection algorithm only provides a transferability score,
and developing a hypothesis testing method for source domain transferability
would be useful. Lastly, our algorithm currently transfers only point
estimations of model parameters, and extending it to include confidence
interval estimation would provide a measure of uncertainty.

## References

  * Barabási [2013] Albert-László Barabási.  Network science.  _Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences_ , 371(1987):20120375, 2013.
  * Ji et al. [2022] Pengsheng Ji, Jiashun Jin, Zheng Tracy Ke, and Wanshan Li.  Co-citation and co-authorship networks of statisticians.  _Journal of Business & Economic Statistics_, 40(2):469–485, 2022.
  * Zitnik et al. [2018] Marinka Zitnik, Monica Agrawal, and Jure Leskovec.  Modeling polypharmacy side effects with graph convolutional networks.  _Bioinformatics_ , 34(13):i457–i466, 2018.
  * Han et al. [2019] Peng Han, Peng Yang, Peilin Zhao, Shuo Shang, Yong Liu, Jiayu Zhou, Xin Gao, and Panos Kalnis.  Gcn-mf: disease-gene association identification by graph convolutional networks and matrix factorization.  In _Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining_, pages 705–713, 2019.
  * Kipf and Welling [2016] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ , 2016.
  * Hamilton et al. [2017] Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  _Advances in neural information processing systems_ , 30, 2017.
  * Dai et al. [2022] Quanyu Dai, Xiao-Ming Wu, Jiaren Xiao, Xiao Shen, and Dan Wang.  Graph transfer learning via adversarial domain adaptation with graph convolution.  _IEEE Transactions on Knowledge and Data Engineering_ , 35(5):4908–4922, 2022.
  * Guney et al. [2016] Emre Guney, Jörg Menche, Marc Vidal, and Albert-László Barábasi.  Network-based in silico drug efficacy screening.  _Nature communications_ , 7(1):10331, 2016.
  * Kanehisa et al. [2012] Minoru Kanehisa, Susumu Goto, Yoko Sato, Miho Furumichi, and Mao Tanabe.  Kegg for integration and interpretation of large-scale molecular data sets.  _Nucleic acids research_ , 40(D1):D109–D114, 2012.
  * Sperduti and Starita [1997] Alessandro Sperduti and Antonina Starita.  Supervised neural networks for the classification of structures.  _IEEE Transactions on Neural Networks_ , 8(3):714–735, 1997.
  * Bruna et al. [2014] Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann Lecun.  Spectral networks and locally connected networks on graphs.  _In International Conference on Learning Representations (ICLR2014), CBLS_ , 2014.
  * Defferrard et al. [2016] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst.  Convolutional neural networks on graphs with fast localized spectral filtering.  _Advances in neural information processing systems_ , 29:3844–3852, 2016.
  * Kipf and Welling [2017] Thomas N. Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  _International Conference on Learning Representations (ICLR)_ , 2017.
  * Hu et al. [2019a] Ziniu Hu, Changjun Fan, Ting Chen, Kai-Wei Chang, and Yizhou Sun.  Pre-training graph neural networks for generic structural feature extraction.  _arXiv preprint arXiv:1905.13728_ , 2019a.
  * Hu et al. [2019b] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec.  Strategies for pre-training graph neural networks.  _arXiv preprint arXiv:1905.12265_ , 2019b.
  * Lu et al. [2021] Yuanfu Lu, Xunqiang Jiang, Yuan Fang, and Chuan Shi.  Learning to pre-train graph neural networks.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 35, pages 4276–4284, 2021.
  * Yang et al. [2022] Yaming Yang, Ziyu Guan, Zhe Wang, Wei Zhao, Cai Xu, Weigang Lu, and Jianbin Huang.  Self-supervised heterogeneous graph pre-training based on structural clustering.  _Advances in Neural Information Processing Systems_ , 35:16962–16974, 2022.
  * Kooverjee et al. [2022] Nishai Kooverjee, Steven James, and Terence Van Zyl.  Investigating transfer learning in graph neural networks.  _Electronics_ , 11(8):1202, 2022.
  * Xu et al. [2023] Jiarong Xu, Renhong Huang, Xin Jiang, Yuxuan Cao, Carl Yang, Chunping Wang, and Yang Yang.  Better with less: A data-active perspective on pre-training graph neural networks.  _Advances in Neural Information Processing Systems_ , 36:56946–56978, 2023.
  * Nilsson and Bresson [2020] Axel Nilsson and Xavier Bresson.  An experimental study of the transferability of spectral graph networks.  _arXiv preprint arXiv:2012.10258_ , 2020.
  * Ruiz et al. [2020] Luana Ruiz, Luiz Chamon, and Alejandro Ribeiro.  Graphon neural networks and the transferability of graph neural networks.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Levie et al. [2021] Ron Levie, Wei Huang, Lorenzo Bucci, Michael Bronstein, and Gitta Kutyniok.  Transferability of spectral graph convolutional neural networks.  _Journal of Machine Learning Research_ , 22(272):1–59, 2021.
  * Ruiz et al. [2023] Luana Ruiz, Luiz FO Chamon, and Alejandro Ribeiro.  Transferability properties of graph neural networks.  _IEEE Transactions on Signal Processing_ , 2023.
  * Wu et al. [2020] Man Wu, Shirui Pan, Chuan Zhou, Xiaojun Chang, and Xingquan Zhu.  Unsupervised domain adaptive graph convolutional networks.  In _Proceedings of The Web Conference 2020_ , pages 1457–1467, 2020.
  * Zhu et al. [2021] Qi Zhu, Carl Yang, Yidan Xu, Haonan Wang, Chao Zhang, and Jiawei Han.  Transfer learning of graph neural networks with ego-graph information maximization.  _Advances in Neural Information Processing Systems_ , 34:1766–1779, 2021.
  * Yuan et al. [2023] Jingyang Yuan, Xiao Luo, Yifang Qin, Zhengyang Mao, Wei Ju, and Ming Zhang.  Alex: Towards effective graph transfer learning with noisy labels.  In _Proceedings of the 31st ACM international conference on multimedia_ , pages 3647–3656, 2023.
  * Wu et al. [2019] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger.  Simplifying graph convolutional networks.  In _International conference on machine learning_ , pages 6861–6871. PMLR, 2019.
  * Wright [2015] Stephen J Wright.  Coordinate descent algorithms.  _Mathematical programming_ , 151(1):3–34, 2015.
  * Bastani [2018] Hamsa Bastani.  Predicting with proxies: Transfer learning in high dimension.  _arXiv preprint arXiv:1812.11097_ , 2018.
  * Li et al. [2022] Sai Li, T Tony Cai, and Hongzhe Li.  Transfer learning for high-dimensional linear regression: Prediction, estimation and minimax optimality.  _Journal of the Royal Statistical Society Series B: Statistical Methodology_ , 84(1):149–173, 2022.
  * Tian and Feng [2023] Ye Tian and Yang Feng.  Transfer learning under high-dimensional generalized linear models.  _Journal of the American Statistical Association_ , 118(544):2684–2697, 2023.
  * Van de Geer et al. [2014] Sara Van de Geer, Peter Bühlmann, Ya’acov Ritov, and Ruben Dezeure.  On asymptotically optimal confidence regions and tests for high-dimensional models.  2014\.
  * Bühlmann and Van De Geer [2011] Peter Bühlmann and Sara Van De Geer.  _Statistics for high-dimensional data: methods, theory and applications_.  Springer Science & Business Media, 2011.
  * Goldsmith [2015] Aaron Seth Goldsmith.  _LASSO Asymptotics For Heavy Tailed Errors_.  PhD thesis, 2015.
  * LEI and RINALDO [2015] JING LEI and ALESSANDRO RINALDO.  Consistency of spectral clustering in stochastic block models.  _The Annals of Statistics_ , 43(1):215–237, 2015.
  * Raskutti et al. [2010] Garvesh Raskutti, Martin J Wainwright, and Bin Yu.  Restricted eigenvalue properties for correlated gaussian designs.  _The Journal of Machine Learning Research_ , 11:2241–2259, 2010.
  * Zhou [2009] Shuheng Zhou.  Restricted eigenvalue conditions on subgaussian random matrices.  _arXiv preprint arXiv:0912.4045_ , 2009.
  * Rudelson and Zhou [2012] Mark Rudelson and Shuheng Zhou.  Reconstruction from anisotropic random measurements.  In _Conference on Learning Theory_ , pages 10–1. JMLR Workshop and Conference Proceedings, 2012.
  * Negahban et al. [2009] Sahand Negahban, Bin Yu, Martin J Wainwright, and Pradeep Ravikumar.  A unified framework for high-dimensional analysis of $m$-estimators with decomposable regularizers.  _Advances in neural information processing systems_ , 22, 2009.
  * Li et al. [2023] Sai Li, Linjun Zhang, T Tony Cai, and Hongzhe Li.  Estimation and inference for high-dimensional generalized linear models with knowledge transfer.  _Journal of the American Statistical Association_ , pages 1–12, 2023.
  * Tang et al. [2008] Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su.  Arnetminer: extraction and mining of academic social networks.  In _Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 990–998, 2008.
  * Shen et al. [2020] Xiao Shen, Quanyu Dai, Sitong Mao, Fu-lai Chung, and Kup-Sze Choi.  Network together: Node classification via cross-network deep network embedding.  _IEEE Transactions on Neural Networks and Learning Systems_ , 32(5):1935–1948, 2020.
  * Grover and Leskovec [2016] Aditya Grover and Jure Leskovec.  node2vec: Scalable feature learning for networks.  In _Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 855–864, 2016.
  * Gasteiger et al. [2018] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann.  Predict then propagate: Graph neural networks meet personalized pagerank.  In _International Conference on Learning Representations_ , 2018.
  * Zhang et al. [2019] Daokun Zhang, Jie Yin, Xingquan Zhu, and Chengqi Zhang.  Attributed network embedding via subspace discovery.  _Data Mining and Knowledge Discovery_ , 33:1953–1980, 2019.
  * Velickovic et al. [2017] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, Yoshua Bengio, et al.  Graph attention networks.  _stat_ , 1050(20):10–48550, 2017.
  * Boucheron et al. [2003] Stéphane Boucheron, Gábor Lugosi, and Olivier Bousquet.  Concentration inequalities.  In _Summer school on machine learning_ , pages 208–240. Springer, 2003.
  * Ostrovsky and Sirota [2014] Eugene Ostrovsky and Leonid Sirota.  Exact value for subgaussian norm of centered indicator random variable.  _arXiv preprint arXiv:1405.6749_ , 2014.
  * Honorio and Jaakkola [2014] Jean Honorio and Tommi Jaakkola.  Tight bounds for the expected risk of linear classifiers and pac-bayes finite-sample guarantees.  In _Artificial Intelligence and Statistics_ , pages 384–392. PMLR, 2014.
  * Wainwright [2019] Martin J Wainwright.  _High-dimensional statistics: A non-asymptotic viewpoint_ , volume 48.  Cambridge university press, 2019.
  * Bandeira and Van Handel [2016] Afonso S Bandeira and Ramon Van Handel.  Sharp nonasymptotic bounds on the norm of random matrices with independent entries.  2016\.
  * McCullagh [2019] Peter McCullagh.  _Generalized linear models_.  Routledge, 2019.
  * Plan and Vershynin [2013] Yaniv Plan and Roman Vershynin.  One-bit compressed sensing by linear programming.  _Communications on pure and Applied Mathematics_ , 66(8):1275–1297, 2013.
  * Mendelson et al. [2008] Shahar Mendelson, Alain Pajor, and Nicole Tomczak-Jaegermann.  Uniform uncertainty principle for bernoulli and subgaussian ensembles.  _Constructive Approximation_ , 28:277–289, 2008.

In this Appendix, we show (1) the notation table to briefly summarize
important notations in this manuscript, (2) proofs of theoretical guarantees,
(3) additional experimental results, and (4) pseudo code of algorithms.

##  Appendix A Notation Table

We present the detailed expressions of notations widely used in the proposed
model and algorithm in Table S1.

Table S1: Notations Notations | Description
---|---
$n$ | number of nodes in entire network
$\mathbf{A}\in\\{0,1\\}^{n\times n}$ | adjacency matrix of entire network without self-loops
$d$ | number of covariates
$\mathbf{X}\in\mathbb{R}^{n\times d}$ | entire covariate matrix
$C$ | number of classes
$\mathbf{Y}\in\\{0,1\\}^{n\times C}$ | entire classification label matrix
$\tilde{\mathbf{A}}$ | adjacency matrix of entire network with added self-connections
$\tilde{\mathbf{D}}$ | degree matrix of $\tilde{\mathbf{A}}$
$\mathbf{S}$ | normalized adjacency matrix of $\tilde{\mathbf{A}}$
$n_{0}$ | target domain sample size
$\mathbf{A}^{(0)}\in\\{0,1\\}^{n_{0}\times n_{0}}$ | adjacency matrix of target network
$\mathbf{X}^{(0)}\in\mathbb{R}^{n_{0}\times d}$ | covariate matrix of target domain
$\mathbf{Y}^{(0)}\in\\{0,1\\}^{n_{0}\times C}$ | classification label matrix of target domain
$\bm{\beta}^{(0)}\in\mathbb{R}^{d\times(C-1)}$ | true coefficient matrix associated with target domain under GCR
$n_{k}$ | the $k$th source domain sample size
$\mathbf{A}^{(k)}\in\\{0,1\\}^{n_{k}\times n_{k}}$ | adjacency matrix of the $k$th source network
$\mathbf{X}^{(k)}\in\mathbb{R}^{n_{k}\times d}$ | covariate matrix of the $k$th source domain
$\mathbf{Y}^{(k)}\in\\{0,1\\}^{n_{k}\times C}$ | classification label matrix of the $k$th source domain
$\bm{\beta}^{(k)}\in\mathbb{R}^{d\times(C-1)}$ | true coefficient matrix associated with $k$th source domain under GCR
$\delta^{(k)}$ | difference between the $k$th source and the target domain’s coefficient
$\mathcal{A}_{h}$ | the set of $h-$level transferable source data, abbreviated as $\mathcal{A}$ for brevity
$p_{0}$ | parameter of Erdős–Rényi (ER) random graph model for target domain
$p_{k}$ | parameter of ER random graph model for the $k$th source domain
$\mathbf{A}^{\mathcal{A}}$ | pooled adjacency matrix
$\mathbf{X}^{\mathcal{A}}$ | pooled covariate matrix
$\mathbf{Y}^{\mathcal{A}}$ | pooled label matrix
$n^{\mathcal{A}}$ | sample size in the pooled sample
$\bm{\beta}^{\mathcal{A}}$ | true underlying parameter related to the pooled sample $(\mathbf{A}^{\mathcal{A}},\mathbf{X}^{\mathcal{A}},\mathbf{Y}^{\mathcal{A}})$
$\hat{\bm{\beta}}^{(0)}$ | estimate for $\bm{\beta}^{(0)}$ obtained using our algorithms

##  Appendix B Proof of Theorem 4.4

For notational simplicity, define $\psi(x)=\log{(1+e^{x})}$. Recall that our
loss function is negative log-likelihood:

$L_{n}({\bm{\beta}})=\frac{1}{n}\sum_{i}\left\\{-{\mathbf{Y}}_{i}{\mathbf{Z}}_{i}^{\top}{\bm{\beta}}+\phi({\mathbf{Z}}_{i}^{\top}{\bm{\beta}})\right\\}\,,$

and our estimator is:

$\hat{\bm{\beta}}={\arg\min}_{{\bm{\beta}}}\left[L_{n}({\bm{\beta}})+\lambda\|{\bm{\beta}}\|_{1}\right]\,.$

Furthermore, define the Bregman divergence $\delta L_{n}({\bm{\beta}})$ as:

$\delta
L_{n}({\bm{\beta}})=L_{n}({\bm{\beta}})-L_{n}({\bm{\beta}}^{(0)})-\langle{\bm{\beta}}-{\bm{\beta}}^{(0)},\nabla
L_{n}({\bm{\beta}}^{(0)})\rangle\,.$ (B.1)

As $L_{n}(\cdot)$ is a convex loss function, it is immediate that $\delta
L_{n}({\bm{\beta}})\geq 0$ for all ${\bm{\beta}}\in{\mathbb{R}}$. Furthermore,
define $\hat{v}=\hat{\bm{\beta}}-{\bm{\beta}}^{(0)}$ and the penalized excess
risk function $R_{n}$ as:

$R_{n}(v)=L_{n}({\bm{\beta}}^{(0)}+v)+\lambda\|{\bm{\beta}}^{(0)}+v\|_{1}-L_{n}({\bm{\beta}}^{(0)})-\lambda\|{\bm{\beta}}^{(0)}\|_{1}\,.$

As both the loss and penalty functions are convex, $R_{n}(\cdot)$ is a convex
function. Furthermore, as $\hat{\bm{\beta}}$ minimizes the penalized loss
function, we have:

$R_{n}(\hat{v})\leq 0,\text{ or equivalently
}L_{n}(\hat{\bm{\beta}})+\lambda\|\hat{\bm{\beta}}\|_{1}\leq
L_{n}({\bm{\beta}}^{(0)})+\lambda\|{\bm{\beta}}^{(0)}\|_{1}\,.$ (B.2)

Recall that we need to show
$\|\hat{v}\|_{2}^{2}=\|\hat{\bm{\beta}}-{\bm{\beta}}^{(0)}\|_{2}^{2}\leq
C(s\log{d})/n$. We prove this by reductio ad absurdum. As $s=o(\log{d}/n)$, we
know $C(s\log{d})/n<1$. Suppose that the claim of the theorem is not true.
Then there exists $t\in(0,1)$ such that
$C(s\log{d})/n<\|t\hat{v}\|_{2}^{2}\leq 1$. Call $t\hat{v}=\tilde{v}$. By the
convexity of $R_{n}(\cdot)$ we have:

$R_{n}(\tilde{v})=R_{n}(t\hat{v})=R_{n}(t\hat{v}+(1-t)0)\leq
t\underbrace{R_{n}(\hat{v})}_{\leq 0}+(1-t)\underbrace{R_{n}(0)}_{=0}\leq
0\,.$

The above chain of inequalities provides an immediate upper bound on
$R_{n}(\tilde{v})$. For the lower bound, we use Bregman divergence:

$\displaystyle 0\geq R_{n}(\tilde{v})$
$\displaystyle=L_{n}({\bm{\beta}}^{(0)}+\tilde{v})+\lambda\|{\bm{\beta}}^{(0)}+\tilde{v}\|_{1}-L_{n}({\bm{\beta}}^{(0)})-\lambda\|{\bm{\beta}}^{(0)}\|_{1}$
$\displaystyle=\langle\tilde{v},\nabla L_{n}({\bm{\beta}}^{(0)})\rangle+\delta
L_{n}(\tilde{v})+\lambda\|{\bm{\beta}}^{(0)}+\tilde{v}\|_{1}-\lambda\|{\bm{\beta}}^{(0)}\|_{1}$
$\displaystyle\geq\delta L_{n}(\tilde{v})-\|\nabla
L_{n}({\bm{\beta}}^{(0)})\|_{\infty}\|\tilde{v}\|_{1}+\lambda\|{\bm{\beta}}^{(0)}+\tilde{v}\|_{1}-\lambda\|{\bm{\beta}}^{(0)}\|_{1}$

Therefore, we have:

$\displaystyle\delta
L_{n}(\tilde{v})+\lambda\|{\bm{\beta}}^{(0)}+\tilde{v}\|_{1}\leq\|\nabla
L_{n}({\bm{\beta}}^{(0)})\|_{\infty}\|\tilde{v}\|_{1}+\lambda\|{\bm{\beta}}^{(0)}\|_{1}\,.$

Now suppose we choose $\lambda$ such that $\|\nabla
L_{n}({\bm{\beta}}^{(0)})\|_{\infty}\leq\lambda/2$ with high probability. We
will specify the choice of $\lambda$ later in the proof. Under this choice we
have:

$\displaystyle\delta
L_{n}(\tilde{v})+\lambda\|{\bm{\beta}}^{(0)}+\tilde{v}\|_{1}\leq\frac{\lambda}{2}\|\tilde{v}\|_{1}+\lambda\|{\bm{\beta}}^{(0)}\|_{1}$
$\displaystyle\implies$ $\displaystyle\delta
L_{n}(\tilde{v})+\lambda\|\tilde{v}_{S^{c}}\|_{1}\leq\frac{3\lambda}{2}\|\tilde{v}_{S}\|_{1}\,.$
(B.3)

As $\delta L_{n}(\tilde{v})\geq 0$, we further have
$\|\tilde{v}_{S^{c}}\|_{1}\leq 3\|\tilde{v}_{S}\|_{1}$, i.e.
$\tilde{v}\in\mathcal{C}(s,3)$, where $\mathcal{C}(s,\alpha)$ is defined as:

$\mathcal{C}(s,\alpha)=\left\\{v\in{\mathbb{R}}^{p}:\|v_{S^{c}}\|_{1}\leq\alpha\|v_{S}\|_{1},\text{
for some }S\text{ with }|S|=s\right\\}\,.$

We next present a lemma, which establishes a lower bound on $\delta
L_{n}(\cdot)$ with high probability:

######  Lemma B.1.

Under Assumptions 1 and 2, there exists some positive constants $\kappa_{l}$
and $C_{4}$ such that,

$\delta L_{n}(u)\geq
L_{\psi}(T)\|u\|_{2}^{2}\left\\{\kappa_{l}-\left(C_{4}\log{d}\sqrt{\frac{\Psi(p)}{n}}\right)\frac{\|u\|_{1}}{\|u\|_{2}}\right\\},\
\ \forall\ \|u\|_{2}\leq 1\,.$

with probability at least $1-({\sf
exp}{\left(\frac{1}{2}\log{d}+1-c_{4}\log^{2}{d}\Psi(p)\right)}+2{\sf
exp}{\left(1-(c_{1}-3/2)\log{d}\right)}+2{\sf
exp}{\left(\frac{3}{2}\log{d}+1-c_{2}n\right)})$, where

$\Psi(p)=\frac{1-2p}{4p\log{((1-p)/p)}}\,,$

and $L_{\psi}(T)$ is a constant, same as in the proof of Proposition 2 of
[39].

We defer the proof the lemme to the end to maintain the flow. Consider the
event when the upper bound of Lemma B.1 holds. As by definition
$\|\tilde{v}\|_{2}\leq 1$, applying Lemma B.1 on $\tilde{v}$ yields:

$\delta L_{n}(\tilde{v})\geq
L_{\psi}(T)\kappa_{l}\|\tilde{v}\|_{2}^{2}-L_{\psi}(T)\left(C_{4}\log{d}\sqrt{\frac{\Psi(p)}{n}}\right)\|\tilde{v}\|_{1}\|\tilde{v}\|_{2}\,.$

Using this lower bound on the Bregman divergence in equation (B), we have:

$\displaystyle
L_{\psi}(T)\kappa_{l}\|\tilde{v}\|_{2}^{2}+\lambda\|\tilde{v}_{S^{c}}\|_{1}$
$\displaystyle\leq\frac{3\lambda}{2}\|\tilde{v}_{S}\|_{1}+L_{\psi}(T)\left(C_{4}\log{d}\sqrt{\frac{\Psi(p)}{n}}\right)\|\tilde{v}\|_{1}\|\tilde{v}\|_{2}$
$\displaystyle\leq\frac{3\lambda\sqrt{s}}{2}\|\tilde{v}_{S}\|_{2}+L_{\psi}(T)\left(C_{4}\log{d}\sqrt{\frac{\Psi(p)}{n}}\right)(\|\tilde{v}_{S}\|_{1}+\|\tilde{v}_{S^{c}}\|_{1})\|\tilde{v}\|_{2}$
$\displaystyle\leq\frac{9}{8L_{\psi}(T)\kappa_{l}}s\lambda^{2}+\frac{L_{\psi}(T)\kappa_{l}}{2}\|\tilde{v}_{S}\|_{2}+4L_{\psi}(T)\left(C_{4}\log{d}\sqrt{\frac{\Psi(p)}{n}}\right)(\|\tilde{v}_{S}\|_{1})\|\tilde{v}\|_{2}\,.$

Changing sides we have:

$\displaystyle\frac{L_{\psi}(T)\kappa_{l}}{2}\|\tilde{v}\|_{2}^{2}+\lambda\|\tilde{v}_{S^{c}}\|_{1}$
$\displaystyle\leq\frac{9}{8L_{\psi}(T)\kappa_{l}}s\lambda^{2}+4L_{\psi}(T)\left(C_{4}\log{d}\sqrt{\frac{\Psi(p)}{n}}\right)(\|\tilde{v}_{S}\|_{1})\|\tilde{v}\|_{2}$
$\displaystyle\leq\frac{9}{8L_{\psi}(T)\kappa_{l}}s\lambda^{2}+4L_{\psi}(T)\sqrt{s}\left(C_{4}\log{d}\sqrt{\frac{\Psi(p)}{n}}\right)\|\tilde{v}\|^{2}_{2}$

As under Assumption 4.3, we have $s\log{d}=o_{p}(\sqrt{n/\Psi(p)})$,
eventually it will be smaller than $L_{\psi}(T)\kappa_{l}/4$. Therefore, we
have:

$\frac{1}{4}L_{\psi}(T)\kappa_{l}\|\tilde{v}\|_{2}^{2}+\lambda\|\tilde{v}_{S^{c}}\|_{1}\leq\frac{9}{8L_{\psi}(T)\kappa_{l}}s\lambda^{2}\implies\|\tilde{v}\|_{2}^{2}\leq\frac{9}{2L^{2}_{\psi}(T)\kappa^{2}_{l}}s\lambda^{2}\,.$
(B.4)

If we can show that a proper choice of $\lambda$ is $C_{2}\sqrt{\log{d}/n}$,
then we are done as in that we have:

$\|\tilde{v}\|_{2}^{2}\leq\frac{9C_{2}}{2L^{2}_{\psi}(T)\kappa^{2}_{l}}\frac{s\log{d}}{n}\triangleq
C\frac{s\log{d}}{n}$

which contradicts the assumption that $\|\tilde{v}\|_{2}>C\sqrt{s\log{d}/n}$.
This will complete the proof. In the following lemma, we show that, indeed
$C_{2}\sqrt{\log{d}/n}$ is a valid choice for $\lambda$:

######  Lemma B.2.

Under Assumption 4.1, there are universal positive constants
$(c_{1},c_{2},c_{3})$ such that

$\|\nabla
L_{n}({\bm{\beta}}^{(0)})\|_{\infty}=\left\|\frac{1}{n}\sum_{i=1}^{n}{\mathbf{Z}}_{i}\left\\{{\mathbf{Y}}_{i}-\psi^{\prime}({\mathbf{Z}}_{i}^{\top}{\bm{\beta}}^{(0)})\right\\}\right\|_{\infty}\leq
C\sqrt{\frac{\log d}{n}}\,,$

with probability $1-c_{1}\left(d^{-c_{2}}+n^{-1}+e^{\log{n}-np/c_{3}}\right)$.

Therefore, under the above lemma, we replace $\lambda$ by $C\sqrt{\log{d}/n}$
in equation (B.4) we complete the proof. Proof of Lemma B.1 and Lemma B.2 can
be found in Appendix C

##  Appendix C Proof of Additional Lemmas

###  C.1 Proof of Lemma B.1

The proof of Lemma B.1 follows the basic structure of the proof of Proposition
2 of [39]. However, suitable modifications are necessary to incorporate
network dependency. We first state Proposition 2 of [39] here for the
convenience of the readers:

######  Proposition C.1 (Proposition 2 of [39]).

Consider the logistic loss (negative log-likelihood) function:

$L_{n}({\bm{\beta}})=\frac{1}{n}\sum_{i}\left\\{-{\mathbf{Y}}_{i}{\mathbf{Z}}_{i}^{\top}{\bm{\beta}}+\log{(1+e^{{\mathbf{Z}}_{i}^{\top}{\bm{\beta}}})}\right\\}$

Define the Bregman divergence of $L_{n}$ as follows:

$\delta L_{n}(u)=L_{n}({\bm{\beta}}^{*}+u)-L_{n}({\bm{\beta}}^{*})-\langle
u,\nabla
L_{n}({\bm{\beta}}^{*})\rangle=\frac{1}{n}\sum_{i}\psi^{\prime\prime}({\mathbf{Z}}_{i}^{\top}{\bm{\beta}}^{*}+v{\mathbf{Z}}_{i}^{\top}u)({\mathbf{Z}}_{i}^{\top}u)^{2}\,.$

where $\psi(x)=\log{(1+e^{x})}$. Then we have:

$\delta
L_{n}(u)\geq\kappa_{1}\|u\|_{2}\left\\{\|u\|_{2}-\kappa_{2}\sqrt{\frac{\log{d}}{n}}\|u\|_{1}\right\\}\
\ \forall\ \ \|u\|_{2}\leq 1$

with probability at least $1-c_{1}e^{-c_{2}n}$ for some constant
$\kappa_{1},\kappa_{2}$.

However, in their proof, the authors heavily used that ${\mathbf{Z}}_{i}$’s
are i.i.d., which is not longer true in our situation, as ${\mathbf{Z}}_{i}$’s
the rows of $\mathbf{A}\mathbf{X}/\sqrt{np}$. Below, we highlight the
modification of the steps that are needed for the proof:

Modification 1:  We first need to show that there exists some constant
$\kappa_{l}$ (not depending on $(n,p,d)$) such that

$v^{\top}\mathbb{E}\left[\frac{1}{n}\sum_{i}{\mathbf{Z}}_{i}^{\top}{\mathbf{Z}}_{i}\right]v=v^{\top}\left(\frac{1}{n^{2}p}\mathbb{E}[{\mathbf{X}}^{\top}{\mathbf{A}}^{\top}{\mathbf{A}}{\mathbf{X}}]\right)v\geq\kappa_{l}\|v\|_{2}^{2}$

for all $v\in{\mathbb{R}}^{d}$. It is easy to see that
$\mathbb{E}[\mathbf{X}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{X}]/(n^{2}p)=\Sigma_{X}$.
Therefore, as long as we assume that
$\lambda_{\min}(\Sigma_{X})\geq\kappa_{l}$, we are done. The lower bound on
the minimum eigenvalue of $\Sigma_{X}$ follows from Assumption 4.1.

######  Remark C.2.

Suppose we do not know $p$. Then, we can estimate it from separate data (by
data splitting) independent of current data. An application of Hoeffding’s
inequality yields:

$\mathbb{P}\left(|\hat{p}-p|\geq t/n\right)\leq Ce^{-ct^{2}}\,.$

Taking $t=np$ and $t=np/2$ (which goes to infinity as per Assumption 4.2), we
have:

$\mathbb{P}(p/2\leq\hat{p}\leq 2p)\geq 1-C_{1}e^{-cn^{2}p^{2}}\uparrow 1\,.$

Therefore, we can perform the entire analysis conditioning on this event.

######  Remark C.3.

As per Remark C.2, if we condition on the event $\hat{p}\leq 2p$, then we have
on that event:

$v^{\top}\mathbb{E}\left[\left(\frac{1}{n^{2}\hat{p}}\mathbb{E}[\mathbf{X}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{X}]\right)\right]v\geq\frac{\kappa_{l}}{2}\|v\|_{2}^{2}\,.$

Furthermore, if we add self-loop, it is easy to see that

$\mathbb{E}[\mathbf{X}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{X}]=\left(1-\frac{1-p}{np}\right)\Sigma_{X}$

As the constant goes to $1$ as $n\uparrow\infty$, we have:

$v^{\top}\mathbb{E}\left[\left(\frac{1}{n^{2}\hat{p}}\mathbb{E}[\mathbf{X}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{X}]\right)\right]v\geq\frac{\kappa_{l}}{4}\|v\|^{2}\
\ \forall\ \ \text{large }n\,.$

Modification 2:  To conclude equation (72) of [39], we need i) an upper bound
on $\mathbb{E}[(u^{\top}{\mathbf{Z}}_{i})^{4}]$ and ii) a tail bound
$\mathbb{P}(|u^{\top}{\mathbf{Z}}_{i}|\geq t)$. Getting the tail bound is
easy, as we can apply the Cauchy-Schwarz inequality:

$\mathbb{P}(|u^{\top}{\mathbf{Z}}_{i}|\geq
t)\leq\frac{\mathbb{E}[(u^{\top}{\mathbf{Z}}_{i})^{2}]}{t^{2}}\leq\frac{\lambda_{\max}(\Sigma_{X})}{t^{2}}\,.$

Now we need to bound the fourth moment (in fact, any $2+\delta$ moment is
sufficient):

$\displaystyle\mathbb{E}[(u^{\top}{\mathbf{Z}}_{i})^{4}]$
$\displaystyle=\mathbb{E}\left[\left(\frac{1}{\sqrt{np}}\sum_{j=1}^{n}a_{ij}({\mathbf{X}}_{j}^{\top}u)\right)^{4}\right]$
$\displaystyle=\mathbb{E}\left[\left(\frac{1}{\sqrt{np}}\sum_{j=1}^{n}(a_{ij}-p+p)({\mathbf{X}}_{j}^{\top}u)\right)^{4}\right]$
$\displaystyle\leq
8\left\\{\mathbb{E}\left[\left(\frac{1}{\sqrt{np}}\sum_{j=1}^{n}(a_{ij}-p)({\mathbf{X}}_{j}^{\top}u)\right)^{4}\right]+\mathbb{E}\left[\left(\frac{\sqrt{p}}{\sqrt{n}}\sum_{j=1}^{n}({\mathbf{X}}_{j}^{\top}u)\right)^{4}\right]\right\\}$
$\displaystyle=8\left\\{\frac{1}{n^{2}}\sum_{j}\mathbb{E}\left[\left(\frac{a_{ij}-p}{\sqrt{p}}\right)^{4}({\mathbf{X}}_{j}^{\top}u)^{4}\right]+\frac{1}{n^{2}}\sum_{j\neq
j^{\prime}}\mathbb{E}\left[\left(\frac{a_{ij}-p}{\sqrt{p}}\right)^{2}({\mathbf{X}}_{j}^{\top}u)^{2}\right]\mathbb{E}\left[\left(\frac{a_{ij}-p}{\sqrt{p}}\right)^{2}({\mathbf{X}}_{j}^{\top}u)^{2}\right]\right.$
$\displaystyle\hskip
100.00015pt\left.+p^{2}\frac{1}{n^{2}}\sum_{j}\mathbb{E}[({\mathbf{X}}_{j}^{\top}u)^{4}]+p^{2}\frac{1}{n^{2}}\sum_{j\neq
j^{\prime}}\mathbb{E}[({\mathbf{X}}_{j}^{\top}u)^{2}]\mathbb{E}[({\mathbf{X}}_{j^{\prime}}^{\top}u)^{2}]\right\\}$
$\displaystyle\leq\left\\{\frac{1}{np}\mathbb{E}[({\mathbf{X}}^{\top}u)^{4}]+\left(\mathbb{E}[({\mathbf{X}}^{\top}u)^{2}\right)^{2}+\frac{p^{2}}{n}\mathbb{E}[({\mathbf{X}}^{\top}u)^{4}]+p^{2}\left(\mathbb{E}[({\mathbf{X}}^{\top}u)^{2}\right)^{2}\right\\}$

which is finite as $\mathbb{E}[({\mathbf{X}}^{\top}u)^{4}]$ is finite
($\mathbf{X}$ is sub-gaussian) and $np\uparrow\infty$.

######  Remark C.4.

If $p$ is unknown, then we can modify the first step by conditioning on the
event $\hat{p}\geq p/2$ and have:

$\mathbb{E}\left[\left(\frac{1}{\sqrt{n\hat{p}}}\sum_{j=1}^{n}a_{ij}({\mathbf{X}}_{j}^{\top}u)\right)^{4}\right]\leq
4\mathbb{E}\left[\left(\frac{1}{\sqrt{np}}\sum_{j=1}^{n}a_{ij}({\mathbf{X}}_{j}^{\top}u)\right)^{4}\right]$

The rest of the proof will remain the same. Furthermore, if we add self-loop,
then we have to single the term $a_{ii}({\mathbf{X}}_{i}^{\top}u)^{2}$ out as
now $a_{ii}=1$. However, it will add another term of other $1/(n^{2}p^{2})$ to
the above bound, which is asymptotically negligible.

Modification 3: We next show an analog of equation (76) of [39]. Following the
notations of [39], define a random process $Z(t)$ as:

$Z(t)=\sup_{u\in\mathbb{S}_{2}(1)\cap\mathbb{B}_{1}(t)}\left|\frac{1}{n}\sum_{i=1}^{n}\left\\{g_{u}({\mathbf{Z}}_{i})-\mathbb{E}[g_{u}({\mathbf{Z}}_{i})]\right\\}\right|\triangleq
F_{t}(Z_{1},\dots,Z_{n})\,.$

We will apply bounded difference inequality (Theorem 6.2 of [47]). Note that
conditional of $\mathbf{X}$, ${\mathbf{Z}}_{i}$’s are independent random
vectors. Furthermore, for any $1\leq i\leq n$ and for any
$Z^{\prime}_{i}\neq{\mathbf{Z}}_{i}$:

$\displaystyle
F_{t}(Z_{1},\dots,Z_{i-1},{\mathbf{Z}}_{i},\dots,Z_{n})-F_{t}(Z_{1},\dots,Z_{i-1},Z^{\prime}_{i},\dots,Z_{n})$
$\displaystyle\leq\frac{1}{n}\sup_{u\in\mathbb{S}_{2}(1)\cap\mathbb{S}_{1}(t)}\left|g_{u}(Z^{\prime}_{i})-\mathbb{E}[g_{u}(Z^{\prime}_{i})]\right|\leq\frac{\tau^{2}}{2n}\hskip
7.22743pt[\because g_{u}(\cdot)\leq\tau^{2}/4].$

Therefore, by bounded difference inequality:

$\mathbb{P}\left(Z(t)\geq\mathbb{E}[Z(t)\mid\mathbf{X}]+t\mid{\mathbf{X}}\right)\leq{\sf
exp}{\left(-\frac{8nt^{2}}{\tau^{4}}\right)}$

As the right-hand side does not depend on the value of $\mathbf{X}$, we can
further conclude the following by taking expectations with respect to
$\mathbf{X}$ on both sides:

$\mathbb{P}\left(Z(t)\geq\mathbb{E}[Z(t)\mid\mathbf{X}]+t\right)\leq{\sf
exp}{\left(-\frac{8nt^{2}}{\tau^{4}}\right)}\,.$ (C.1)

Next, using symmetrization and Rademacher complexity bounds, we bound
$\mathbb{E}[Z(t)\mid\mathbf{X}]$. For notational simplicity let us define:

$\displaystyle V_{n}$ $\displaystyle=\max_{1\leq j\leq
p}\left|\frac{1}{\sqrt{n}}\sum_{k=1}^{n}{\mathbf{X}}_{kj}\right|$
$\displaystyle\Gamma_{n}$ $\displaystyle=\max_{1\leq j\leq
d}\frac{1}{n}\sum_{k=1}^{n}{\mathbf{X}}_{kj}^{2}\,.$

Now, as we have already pointed out, conditional on $\mathbf{X}$,
${\mathbf{Z}}_{i}$’s are i.i.d. random vectors. Therefore, the symmetrization
argument holds, and following the same line of argument as of [39], we can
conclude an analog of their equation (78):

$\displaystyle\mathbb{E}[Z(t)\mid\mathbf{X}]$ $\displaystyle\leq
8K_{3}t\mathbb{E}_{{\epsilon},Z}\left[\max_{1\leq j\leq
d}\left|\frac{1}{n}\sum_{i=1}^{n}{\epsilon}_{i}{\mathbf{Z}}_{ij}\mathds{1}_{|{\mathbf{Z}}_{i}^{\top}{\bm{\beta}}_{*}|\leq
T}\right|\mid\mathbf{X}\right]$
$\displaystyle=\frac{8K_{3}t}{\sqrt{n}}\mathbb{E}_{\mathbf{Z}\mid\mathbf{X}}\left[\mathbb{E}_{{\epsilon}\mid\mathbf{Z},\mathbf{X}}\left[\max_{1\leq
j\leq
d}\left|\frac{1}{\sqrt{n}}\sum_{i=1}^{n}{\epsilon}_{i}{\mathbf{Z}}_{ij}\mathds{1}_{|{\mathbf{Z}}_{i}^{\top}{\bm{\beta}}_{*}|\leq
T}\right|\right]\right]$

First, observe that $\\{{\epsilon}_{1},\dots,{\epsilon}_{n}\\}$ are Rademacher
random variables (which are also subgaussian with sub-gaussian constant being
1), and therefore, conditionally on $\mathbf{Z}$,

$\frac{1}{\sqrt{n}}\sum_{i=1}^{n}{\epsilon}_{i}{\mathbf{Z}}_{ij}\mathds{1}_{|{\mathbf{Z}}_{i}^{\top}{\bm{\beta}}_{*}|\leq
T}\text{ is subgaussian with norm
}\sqrt{\frac{1}{n}\sum_{i=1}^{n}{\mathbf{Z}}^{2}_{ij}\mathds{1}_{|{\mathbf{Z}}_{i}^{\top}{\bm{\beta}}_{*}|\leq
T}}\leq\sqrt{\frac{1}{n}\sum_{i=1}^{n}{\mathbf{Z}}^{2}_{ij}}\,.$

Therefore, from standard probability tail bound calculation, we have:

$\mathbb{E}_{{\epsilon}\mid\mathbf{Z},\mathbf{X}}\left[\max_{1\leq j\leq
d}\left|\frac{1}{\sqrt{n}}\sum_{i=1}^{n}{\epsilon}_{i}{\mathbf{Z}}_{ij}\mathds{1}_{|{\mathbf{Z}}_{i}^{\top}{\bm{\beta}}_{*}|\leq
T}\right|\right]\leq\sqrt{2\log{d}}\max_{1\leq j\leq
d}\sqrt{\frac{1}{n}\sum_{i=1}^{n}{\mathbf{Z}}^{2}_{ij}}\,.$

Therefore, we have:

$\mathbb{E}[Z(t)\mid\mathbf{X}]\leq
8\sqrt{2}K_{3}t\sqrt{\frac{\log{d}}{n}}\mathbb{E}\left[\max_{1\leq j\leq
d}\sqrt{\frac{1}{n}\sum_{i=1}^{n}{\mathbf{Z}}^{2}_{ij}}\mid\mathbf{X}\right]$
(C.2)

Recall that by define
${\mathbf{Z}}_{ij}=(\sum_{k}A_{ik}{\mathbf{X}}_{kj})/\sqrt{np}$, which is not
centered conditional on $\mathbf{X}$. Therefore we first center it:

${Z}_{ij}=\frac{1}{\sqrt{np}}\sum_{k}A_{ik}{\mathbf{X}}_{kj}=\frac{1}{\sqrt{np}}\sum_{k}(A_{ik}-p){\mathbf{X}}_{kj}+\sqrt{\frac{p}{n}}\sum_{k}{\mathbf{X}}_{kj}\triangleq\bar{\mathbf{Z}}_{ij}+\sqrt{\frac{p}{n}}\sum_{k}{\mathbf{X}}_{kj}\,.$

Using this we have:

$\displaystyle\mathbb{E}\left[\max_{1\leq j\leq
d}\sqrt{\frac{1}{n}\sum_{i=1}^{n}{\mathbf{Z}}^{2}_{ij}}\mid\mathbf{X}\right]$
$\displaystyle\leq\mathbb{E}\left[\max_{1\leq j\leq
d}\sqrt{\frac{1}{n}\sum_{i=1}^{n}\bar{\mathbf{Z}}^{2}_{ij}}\mid\mathbf{X}\right]+\sqrt{p}\max_{1\leq
j\leq d}\left|\frac{1}{\sqrt{n}}\sum_{k}{\mathbf{X}}_{kj}\right|$
$\displaystyle=\mathbb{E}\left[\max_{1\leq j\leq
d}\sqrt{\frac{1}{n}\sum_{i=1}^{n}\bar{\mathbf{Z}}^{2}_{ij}}\mid\mathbf{X}\right]+\sqrt{p}V_{n}$
$\displaystyle\leq\sqrt{\mathbb{E}\left[\max_{1\leq j\leq
d}\frac{1}{n}\sum_{i=1}^{n}\bar{\mathbf{Z}}^{2}_{ij}\mid\mathbf{X}\right]}+\sqrt{p}V_{n}\,.$
(C.3)

######  Remark C.5.

If we have $\hat{p}$, then again, at the bound in equation (C.3), we have an
additional factor of $\sqrt{2}$ for replacing $\hat{p}$ by $p$.

We next establish an upper bound on the conditional expectation of the maximum
of the mean of $\bar{\mathbf{Z}}_{ij}^{2}$. We first claim that
$\bar{\mathbf{Z}}_{ij}$ is a SG($\sigma_{j})$ random variable with the value
of $\sigma_{j}$ defined in equation (C.4) below. To see this, first note that,
from Theorem 2.1 of [48], we know $(A_{ik}-p)$ is SG($\sqrt{2}Q(p)$).
Therefore, we have:

$\bar{Z}_{ij}=\frac{1}{\sqrt{np}}\sum_{k}(A_{ik}-p){\mathbf{X}}_{kj}\in\mathrm{SG}\left(\sqrt{\frac{2Q^{2}(p)}{p}\frac{1}{n}\sum_{k}{\mathbf{X}}_{kj}^{2}}\right)\triangleq\mathrm{SG}(\sigma_{j})\,.$
(C.4)

######  Remark C.6.

The same sub-gaussian bound continues to hold even under self-loop as $(1-p)$
is sub-gaussian with constant $\leq 2Q^{2}(p)$.

Let $\mu_{j}=\mathbb{E}[\bar{\mathbf{Z}}^{2}_{ij}|\mathbf{X}]$. Then, by
equation (37) of [49], we know $\bar{\mathbf{Z}}^{2}_{ij}-\mu_{j}$ is a sub-
exponential random variable, in particular:

$\bar{\mathbf{Z}}^{2}_{ij}-\mu_{j}\in\mathrm{SE}\left(\sqrt{32}\sigma_{j},4\sigma_{j}^{2}\right)\,.$

Hence we have, by equation (2.18) of [50] (we use the version for the two-
sided bound here):

$\mathbb{P}\left(\left|\frac{1}{n}\sum_{i=1}^{n}\left(\bar{\mathbf{Z}}_{ij}^{2}-\mu_{j}\right)\right|\geq
t\right)\leq{\sf
exp}{\left(-\frac{1}{8\sigma_{j}^{2}}\min\left\\{\frac{nt^{2}}{8},nt\right\\}\right)}\,.$
(C.5)

Going back to (C.3), we have:

$\displaystyle\mathbb{E}\left[\max_{1\leq j\leq
d}\frac{1}{n}\sum_{i=1}^{n}\bar{\mathbf{Z}}^{2}_{ij}\mid\mathbf{X}\right]$
$\displaystyle=\mathbb{E}\left[\max_{1\leq j\leq
d}\left\\{\left(\frac{1}{n}\sum_{i=1}^{n}(\bar{\mathbf{Z}}^{2}_{ij}-\mu_{j})\right)+\mu_{j}\right\\}\mid\mathbf{X}\right]$
$\displaystyle\leq\mathbb{E}\left[\max_{1\leq j\leq
d}\left|\frac{1}{n}\sum_{i=1}^{n}(\bar{\mathbf{Z}}^{2}_{ij}-\mu_{j})\right|\mid\mathbf{X}\right]+\max_{1\leq
j\leq d}\mu_{j}$

Now, bound the first term using the concentration inequality (C.5). Towards
that end, define $\sigma_{*}=\max_{j}\sigma_{j}$ and observe that
$\sigma_{*}=\sqrt{2Q^{2}(p)/p}\sqrt{\Gamma_{n}}$.

$\displaystyle\mathbb{E}\left[\max_{1\leq j\leq
d}\left|\frac{1}{n}\sum_{i=1}^{n}(\bar{\mathbf{Z}}^{2}_{ij}-\mu_{j})\right|\mid\mathbf{X}\right]\leq
8\max\\{\sigma_{*}\sqrt{\log{d}},\sigma_{*}^{2}\log{d}\\}\,.$

Furthermore, observe that:

$\displaystyle\mu_{j}=\mathbb{E}[\bar{\mathbf{Z}}_{ij}^{2}\mid\mathbf{X}]$
$\displaystyle=\mathbb{E}\left[\left(\frac{1}{\sqrt{np}}\sum_{k}(A_{ik}-p)X_{kj}\right)^{2}\mid\mathbf{X}\right]=(1-p)\frac{1}{n}\sum_{k}X^{2}_{kj}\,,$

which implies, $\max_{1\leq j\leq d}\mu_{j}=(1-p)\Gamma_{n}$. Using these
bounds in equation (C.3), we have:

$\mathbb{E}\left[\max_{1\leq j\leq
d}\sqrt{\frac{1}{n}\sum_{i=1}^{n}{\mathbf{Z}}^{2}_{ij}}\mid\mathbf{X}\right]\leq\sqrt{\max\\{\sigma_{*}\sqrt{\log{d}},\sigma_{*}^{2}\log{d}\\}+(1-p)\Gamma_{n}}+\sqrt{p}V_{n}$
(C.6)

######  Remark C.7.

Here also the constant will change by an additional factor of $\sqrt{2}$, see
Remark C.5.

This, along, with equation (C.2),yields:

$\displaystyle\mathbb{E}[Z(t)\mid\mathbf{X}]$ $\displaystyle\leq
Ct\sqrt{\frac{\log{d}}{n}}\left(\sqrt{\max\\{\sigma_{*}\sqrt{\log{d}},\sigma_{*}^{2}\log{d}\\}+(1-p)\Gamma_{n}}+\sqrt{p}V_{n}\right)$
$\displaystyle\triangleq Ct\sqrt{\frac{\log{d}}{n}}g(\mathbf{X},p,d)\,.$ (C.7)

Using this in the inequality (C.1) yields:

$\mathbb{P}\left(Z(t)\geq
Ct\sqrt{\frac{\log{d}}{n}}g(\mathbf{X},p,d)+y\right)\leq{\sf
exp}{\left(-\frac{8ny^{2}}{\tau^{4}}\right)}\,.$ (C.8)

We next provide an upper bound for $g(\mathbf{X},p,d)$ term. Note that in the
expression of $g(\mathbf{X},p,d)$, there are two key terms:
$\Gamma_{n},V_{n}$. Therefore, if we can obtain an upper bound on them
individually, we can obtain an upper bound on $g(\mathbf{X},p,d)$. We start
with $V_{n}$; for any fixed $j$, ${\mathbf{X}}_{kj}$’s are i.i.d sub-gaussian
random variable with constant $\sigma^{2}_{X}$. Therefore, we have:

$\mathbb{P}\left(\left|\frac{1}{\sqrt{n}}\sum_{k=1}^{n}{\mathbf{X}}_{kj}\right|\geq
t\right)\leq 2e^{-\frac{t^{2}}{2\sigma^{2}_{X}}}$

As a consequence, by union bound:

$\mathbb{P}(V_{n}\geq
t)=\mathbb{P}\left(\max_{j}\left|\frac{1}{\sqrt{n}}\sum_{k=1}^{n}{\mathbf{X}}_{kj}\right|\geq
t\right)\leq 2e^{\log{d}-\frac{t^{2}}{2\sigma^{2}_{X}}}$

Therefore, choosing $t=\sigma_{X}\sqrt{2c_{1}\log{d}}$ (where $c_{1}\geq 2$),
we have:

$V_{n}\leq\sigma_{X}\sqrt{2c_{1}\log{d}})\ \ \text{with probability }\geq
1-2{\sf exp}{\left(-(c_{1}-1)\log{d}\right)}\,.$ (C.9)

Call this event $\Omega_{n,{\mathbf{X}},1}$. Our next target is $\Gamma_{n}$
which can be further upper bounded by:

$\Gamma_{n}=\max_{j}\frac{1}{n}\sum_{k=1}^{n}{\mathbf{X}}_{kj}^{2}\leq\max_{j}\frac{1}{n}\sum_{k=1}^{n}({\mathbf{X}}_{kj}^{2}-\Sigma_{X,jj})+\max_{j}\Sigma_{X,jj}\triangleq\bar{\Gamma}_{n}+\max_{j}\Sigma_{X,jj}\,.$

As we have assumed $\max_{j}\Sigma_{X,jj}\leq C_{1}$ for some constant
$C_{1}$, we need to bound $\bar{\Gamma}_{n}$. Here, we also use the fact that
${\mathbf{X}}_{jk}^{2}-\Sigma_{X,jj}\in\mathrm{SE}(\sqrt{32}\sigma_{X},4\sigma_{X}^{2})$.
Therefore, by equation (2.18) of [50] we have:

$\mathbb{P}\left(\left|\frac{1}{n}\sum_{k=1}^{n}({\mathbf{X}}_{kj}^{2}-\Sigma_{X,jj})\right|\geq
t\right)\leq 2{\sf
exp}{\left(-\frac{n}{8\sigma^{2}_{X}}\min\left\\{\frac{t^{2}}{8},t\right\\}\right)}$

Therefore, by union bound:

$\mathbb{P}\left(\max_{1\leq j\leq
d}\left|\frac{1}{n}\sum_{k=1}^{n}({\mathbf{X}}_{kj}^{2}-\Sigma_{X,jj})\right|\geq
t\right)\leq 2{\sf
exp}{\left(\log{d}-\frac{n}{8\sigma^{2}_{X}}\min\left\\{\frac{t^{2}}{8},t\right\\}\right)}$

Choosing $t=\max_{j}\Sigma_{X,jj}$, we have:

$\Gamma_{n}\leq 2\max_{j}\Sigma_{X,jj}\leq 2C_{1}\ \ \text{with probability
}\geq 1-2{\sf exp}{\left(\log{d}-c_{2}n\right)}\,.$ (C.10)

Call this event $\Omega_{n,{\mathbf{X}},2}$. Now, going back to the definition
of $g(\mathbf{X},p,d)$ in equation (C.1), we first note that, on the event
$\Omega_{n,{\mathbf{X}},1}\cap\Omega_{n,{\mathbf{X}},2}$:

$\sigma_{*}=\sqrt{\frac{2Q^{2}(p)}{p}\Gamma_{n}}\leq
2\sqrt{\frac{C_{1}Q^{2}(p)}{p}}\triangleq 2\sqrt{C_{1}\Psi(p)}\,.$

It is immediate from the definition of $Q(p)$ that $\Psi(p)\sim
1/(-4p\log{p})$ for $p$ close to $0$. Therefore for all small $p$ and large
$d$, $\sigma_{*}^{2}\log{d}\geq 1$ and consequently
$\max\\{\sigma_{*}\sqrt{\log{d}},\sigma_{*}^{2}\log{d}\\}=\sigma_{*}^{2}\log{d}$.
Hence, we have on the event
$\Omega_{n,{\mathbf{X}},1}\cap\Omega_{n,{\mathbf{X}},2}$:

$g(\mathbf{X},p,d)\leq
C_{2}\sqrt{\Psi(p)\log{d}}+2C_{1}+\sigma_{X}\sqrt{2c_{1}p\log{d}}\,.$

It is immediate that the dominating term is the first term, which implies:

$g(\mathbf{X},p,d)\leq 3C_{2}\sqrt{\Psi(p)\log{d}}\,.$

We now use this bound in equation (C.1). Note that:

$\displaystyle\mathbb{P}\left(Z(t)\geq\mathbb{E}[Z(t)\mid\mathbf{X}]+y\right)$
$\displaystyle\geq\mathbb{P}\left(Z(t)\geq\mathbb{E}[Z(t)\mid\mathbf{X}]+y,\Omega_{n,{\mathbf{X}},1}\cap\Omega_{n,{\mathbf{X}},2}\right)$
$\displaystyle\geq\mathbb{P}\left(Z(t)\geq
3CC_{2}t\log{d}\sqrt{\frac{\Psi(p)}{n}}+y,\Omega_{n,{\mathbf{X}},1}\cap\Omega_{n,{\mathbf{X}},2}\right)$
$\displaystyle\geq\mathbb{P}\left(Z(t)\geq
3CC_{2}t\log{d}\sqrt{\frac{\Psi(p)}{n}}+y\right)+\mathbb{P}(\Omega_{n,{\mathbf{X}},1}\cap\Omega_{n,{\mathbf{X}},2})-1$

Therefore,

$\displaystyle\mathbb{P}\left(Z(t)\geq
3CC_{2}t\log{d}\sqrt{\frac{\Psi(p)}{n}}+y\right)$ $\displaystyle\leq{\sf
exp}{\left(-\frac{8ny^{2}}{\tau^{4}}\right)}+\mathbb{P}((\Omega_{n,{\mathbf{X}},1}\cap\Omega_{n,{\mathbf{X}},2})^{c})$
$\displaystyle\leq{\sf exp}{\left(-\frac{8ny^{2}}{\tau^{4}}\right)}+2{\sf
exp}{\left(-(c_{1}-1)\log{d}\right)}+2{\sf
exp}{\left(\log{d}-c_{2}n\right)}\,.$ (C.11)

Choosing $y=C_{3}t\log{d}\sqrt{\Psi(p)/n}$, we have:

$\displaystyle\mathbb{P}\left(Z(t)\geq
3CC_{2}t\log{d}\sqrt{\frac{\Psi(p)}{n}}+C_{3}t\log{d}\sqrt{\frac{\Psi(p)}{n}}\right)$
$\displaystyle\leq{\sf
exp}{\left(-\frac{8C_{3}^{2}t^{2}\log^{2}{d}\Psi(p)}{\tau^{4}}\right)}+2{\sf
exp}{\left(-(c_{1}-1)\log{d}\right)}+2{\sf
exp}{\left(\log{d}-c_{2}n\right)}\,.$ (C.12)

Modification 4: Our last modification, not modification per se, but an
application of peeling argument. Infact we want an upper bound on the event
$\mathcal{E}$ defined as:

$\mathcal{E}=\left\\{Z(t)\geq
3eCC_{2}t\log{d}\sqrt{\frac{\Psi(p)}{n}}+C_{3}et\log{d}\sqrt{\frac{\Psi(p)}{n}}\
\text{ for some }t\in[1,\sqrt{d}]\right\\}\,.$

Note that $t$ denotes the $\ell_{1}$ norm of a a vector $u$ such that
$\|u\|_{2}=1$. Therefore, $t\in[1,\sqrt{d}]$. Also recall that $Z(t)$ is the
suprema of the empirical process over all vectors $u$ such that $\|u\|_{2}=1$
and $\|u\|_{1}\leq t$. In peeling, we write $\mathcal{E}$ as union of disjoint
events. Define $\mathcal{E}_{j}$ as:

$\mathcal{E}_{j}=\left\\{Z(t)\geq
3eCC_{2}t\log{d}\sqrt{\frac{\Psi(p)}{n}}+C_{3}et\log{d}\sqrt{\frac{\Psi(p)}{n}}\
\text{ for some }t\in[\sqrt{d}/e^{j},\sqrt{d}/e^{j-1}]\right\\}\,.$

Therefore,

$\mathcal{E}\subseteq\cup_{j=1}^{\lceil\frac{1}{2}\log{d}\rceil}\mathcal{E}_{j}\implies\mathbb{P}(\mathcal{E})\leq\sum_{j=1}^{\lceil\frac{1}{2}\log{d}\rceil}\mathbb{P}(\mathcal{E}_{j})\,.$

Now observe that, for any $t\in[\sqrt{d}/e^{j},\sqrt{d}/e^{j-1}]$, we have
$Z(t)\leq Z(\sqrt{d}/e^{j-1})$ and also

$\displaystyle
3eCC_{2}t\log{d}\sqrt{\frac{\Psi(p)}{n}}+C_{3}et\log{d}\sqrt{\frac{\Psi(p)}{n}}$
$\displaystyle\geq
3eCC_{2}\frac{\sqrt{d}}{e^{j}}\log{d}\sqrt{\frac{\Psi(p)}{n}}+C_{3}e\frac{\sqrt{d}}{e^{j}}\log{d}\sqrt{\frac{\Psi(p)}{n}}$
$\displaystyle\geq
3CC_{2}\frac{\sqrt{d}}{e^{j-1}}\log{d}\sqrt{\frac{\Psi(p)}{n}}+C_{3}\frac{\sqrt{d}}{e^{j-1}}\log{d}\sqrt{\frac{\Psi(p)}{n}}\,.$

Therefore:

$\displaystyle\mathbb{P}(\mathcal{E}_{j})$
$\displaystyle\leq\mathbb{P}\left(Z\left(\frac{\sqrt{d}}{e^{j-1}}\right)\geq
3CC_{2}\frac{\sqrt{d}}{e^{j-1}}\log{d}\sqrt{\frac{\Psi(p)}{n}}+C_{3}\frac{\sqrt{d}}{e^{j-1}}\log{d}\sqrt{\frac{\Psi(p)}{n}}\right)$
$\displaystyle\leq{\sf
exp}{\left(-\frac{8C_{3}^{2}d\log^{2}{d}\Psi(p)}{e^{2j-2}\tau^{4}}\right)}+2{\sf
exp}{\left(-(c_{1}-1)\log{d}\right)}+2{\sf exp}{\left(\log{d}-c_{2}n\right)}$
$\displaystyle\leq{\sf exp}{\left(-c_{4}\log^{2}{d}\Psi(p)\right)}+2{\sf
exp}{\left(-(c_{1}-1)\log{d}\right)}+2{\sf exp}{\left(\log{d}-c_{2}n\right)}$

Hence:

$\mathbb{P}(\mathcal{E})\leq{\sf
exp}{\left(\frac{1}{2}\log{d}+1-c_{4}\log^{2}{d}\Psi(p)\right)}+2{\sf
exp}{\left(1-(c_{1}-3/2)\log{d}\right)}+2{\sf
exp}{\left(\frac{3}{2}\log{d}+1-c_{2}n\right)}\,.$

On the event $\mathcal{E}^{c}$ (which is a high probability event):

$Z(t)\leq
3eCC_{2}t\log{d}\sqrt{\frac{\Psi(p)}{n}}+C_{3}et\log{d}\sqrt{\frac{\Psi(p)}{n}}\
\text{ for all }t\in[1,\sqrt{d}]\,.$

Now let us conclude with the entire roadmap of the proof. First, following the
same line of argument as of [39] we show that

$\displaystyle\delta L_{n}(u)$ $\displaystyle\geq
L_{\psi}(T)\frac{1}{n}\sum_{i}\phi_{\tau}\left((u^{\top}{\mathbf{Z}}_{i})^{2}\mathds{1}_{|{\mathbf{Z}}_{i}^{\top}{\bm{\beta}}_{*}|\leq
T}\right)$
$\displaystyle=L_{\psi}(T)\|u\|^{2}\frac{1}{n}\sum_{i}\phi_{\tau}\left(\left(u^{\top}{\mathbf{Z}}_{i}/\|u\|\right)^{2}\mathds{1}_{|{\mathbf{Z}}_{i}^{\top}{\bm{\beta}}_{*}|\leq
T}\right)$ $\displaystyle=L_{\psi}(T)\|u\|^{2}\mathbb{P}_{n}(g_{u/\|u\|}(Z))$
$\displaystyle=L_{\psi}(T)\|u\|_{2}^{2}\left\\{P(g_{u/\|u\|}(Z))+(\mathbb{P}_{n}-P)g_{u/\|u\|}(Z)\right\\}$

We have proved in Modification 1 that $P(g_{u/\|u\|}(Z))\geq\kappa_{l}$.
Therefore,

$\delta L_{n}(u)\geq
L_{\psi}(T)\|u\|_{2}^{2}\left\\{\kappa_{l}+(\mathbb{P}_{n}-P)g_{u/\|u\|}(Z)\right\\}$

Now for any $u$,

$\displaystyle(\mathbb{P}_{n}-P)g_{u/\|u\|}(Z)$ $\displaystyle\leq
Z\left(\left\|\frac{u}{\|u\|_{2}}\right\|_{1}\right)$
$\displaystyle\leq\left(3eCC_{2}\log{d}\sqrt{\frac{\Psi(p)}{n}}+C_{3}e\log{d}\sqrt{\frac{\Psi(p)}{n}}\right)\frac{\|u\|_{1}}{\|u\|_{2}}\,.$

Hence, we conclude that:

$\delta L_{n}(u)\geq
L_{\psi}(T)\|u\|_{2}^{2}\left\\{\kappa_{l}-\left(C_{4}\log{d}\sqrt{\frac{\Psi(p)}{n}}\right)\frac{\|u\|_{1}}{\|u\|_{2}}\right\\}\,.$

###  C.2 Proof of Lemma B.2

Recall that we have:

$\nabla
L_{n}({\bm{\beta}}^{(0)})=\frac{1}{n}\sum_{i}{\mathbf{Z}}_{i}\left\\{{\mathbf{Y}}_{i}-\psi^{\prime}({\mathbf{Z}}_{i}^{\top}{\bm{\beta}}^{(0)})\right\\}\,.$

Now consider the $j^{th}$ element of $\nabla L_{n}({\bm{\beta}}^{(0)})$, i.e.,

$\nabla
L_{n}({\bm{\beta}}^{(0)})_{j}-\frac{1}{n}\sum_{i}{\mathbf{Z}}_{ij}\left\\{{\mathbf{Y}}_{i}-\psi^{\prime}({\mathbf{Z}}_{i}^{\top}{\bm{\beta}}^{(0)})\right\\}\,.$

First, we show that conditional on $Z_{1j},\dots,Z_{nj}$, the terms are mean
$0$ (which is true from the definition of ${\mathbf{Y}}_{i}$), independent
subgaussian random variable. The subgaussianity follows from the fact that:

$\left\|\sum_{i}{\mathbf{Z}}_{ij}\left\\{{\mathbf{Y}}_{i}-\psi^{\prime}({\mathbf{Z}}_{i}^{\top}{\bm{\beta}}^{(0)})\right\\}\right\|_{\psi_{2}}^{2}\leq
C\sum_{i}{\mathbf{Z}}_{ij}^{2}\|{\mathbf{Y}}_{i}-\psi^{\prime}({\mathbf{Z}}_{i}^{\top}{\bm{\beta}}^{(0)})\|_{\psi_{2}}^{2}\leq
C\sum_{i}{\mathbf{Z}}_{ij}^{2}\,.$

Here $C$ is some absolute constant. Therefore, we have:

$\textstyle\mathbb{P}\left(\max_{1\leq j\leq
d}\left|\frac{1}{\sqrt{n}}\sum_{i}{\mathbf{Z}}_{ij}\left\\{{\mathbf{Y}}_{i}-\psi^{\prime}({\mathbf{Z}}_{i}^{\top}{\bm{\beta}}^{(0)})\right\\}\right|\geq
t\mid\mathbf{Z}\right)\leq c_{1}{\sf
exp}{\left(\log{d}-c_{2}\frac{t^{2}}{\max_{1\leq j\leq
d}\frac{1}{n}\sum_{i=1}^{n}{\mathbf{Z}}_{ij}^{2}}\right)}$ (C.13)

We next bound the term in the tail bound $\max_{1\leq j\leq
d}(\sum_{i=1}^{n}{\mathbf{Z}}_{ij}^{2})/n$. Towards that end, first observe
that:

$\displaystyle\max_{1\leq j\leq
d}\frac{1}{n}\sum_{i=1}^{n}{\mathbf{Z}}_{ij}^{2}=\max_{1\leq j\leq
d}\frac{1}{n}\mathbf{Z}_{*j}^{\top}\mathbf{Z}_{*j}$ $\displaystyle=\max_{1\leq
j\leq
d}\frac{1}{n^{2}p}e_{j}^{\top}\mathbf{X}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{X}e_{j}$
$\displaystyle=\max_{1\leq j\leq
d}\frac{1}{n}e_{j}^{\top}\mathbf{X}\left(\frac{\mathbf{A}^{\top}\mathbf{A}}{np}\right)\mathbf{X}^{\top}e_{j}\,.$

######  Remark C.8.

If $p$ is unknown, i.e., we have $\hat{p}$, then, conditional on the event
$p/2\leq\hat{p}\leq 2p$, the above equality will be replaced by an inequality
with an additional factor of $2$.

As we know
$\mathbb{E}[\mathbf{X}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{X}]/(n^{2}p)=\Sigma_{X}$
and if we define $\sigma_{+}=\max_{j}\Sigma_{X,jj}$, we have:

$\max_{1\leq j\leq
d}\frac{1}{n}\sum_{i=1}^{n}{\mathbf{Z}}_{ij}^{2}\leq\max_{1\leq j\leq
d}\left[\frac{1}{n}e_{j}^{\top}\mathbf{X}\left(\frac{\mathbf{A}^{\top}\mathbf{A}}{np}\right)\mathbf{X}^{\top}e_{j}-\Sigma_{X,jj}\right]+\sigma_{+}\,.$

From Hanson-Wright inequality, we have for any matrix $\mathbf{Q}$
(independent of ${\mathbf{X}}$):

$\mathbb{P}\left(\max_{1\leq j\leq
d}\left|\mathbf{X}_{*j}^{\top}\mathbf{Q}\mathbf{X}_{*j}-\mathbb{E}[\mathbf{X}_{*j}^{\top}\mathbf{Q}\mathbf{X}_{*j}]\right|\geq
t\right)\leq{\sf
exp}\left(-c\min\Big{(}\frac{t^{2}}{\kappa_{u}^{4}\|\mathbf{Q}\|_{\mathrm{F}}^{2}},\frac{t}{\kappa_{u}^{2}\|\mathbf{Q}\|_{2}}\Big{)}\right)\,.$

Here $\mathbf{Q}=(\mathbf{A}^{\top}\mathbf{A})/n^{2}p$. We use some
concentration results on $\mathbf{Q}$ in the rest of the proof. For notational
convenience, set $\tilde{\mathbf{A}}=\mathbf{A}/\sqrt{np}$. We have the
following concentration bound:

######  Lemma C.9.

For the Frobenous norm, we have with probability $\geq 1-n^{-1}$:

$\|\tilde{\mathbf{A}}^{\top}\tilde{\mathbf{A}}\|_{F}^{2}\leq\mathbb{E}[\|\tilde{\mathbf{A}}^{\top}\tilde{\mathbf{A}}\|_{F}^{2}]+n+n^{2}p^{2}\leq
2(n+n^{2}p^{2})\,.$

For the operator norm, we have with probability $\geq
1-e^{\log{n}-\frac{np}{c}}$:

$\|\tilde{\mathbf{A}}-\mathbb{E}[\tilde{\mathbf{A}}]\|_{\rm op}\leq
1+3\sqrt{2}\implies\|\tilde{\mathbf{A}}\|_{\rm op}\leq 2\sqrt{np}\,.$

######  Remark C.10.

This lemma remains the same for the self-loop.

First, assume the above lemma is true, and consider the event so that the
upper bound holds. Call that event $\mathcal{E}$. On this event we have:

$\mathbb{P}\left(\max_{1\leq j\leq
d}\frac{1}{n}\left|\mathbf{X}_{*j}^{\top}\mathbf{Q}\mathbf{X}_{*j}-\mathbb{E}[\mathbf{X}_{*j}^{\top}\mathbf{Q}\mathbf{X}_{*j}]\right|\geq
t\mid\mathcal{E}\right)\leq{\sf
exp}\left(\log{d}-c\min\Big{(}\frac{n^{2}t^{2}}{2\kappa_{u}^{4}(n+n^{2}p^{2})},\frac{t}{2\kappa_{u}^{2}p}\Big{)}\right)\,.$

Choosing

$t=K\max\left\\{\sqrt{\frac{\log{d}}{n}+p^{2}\log{d}},p\log{d}\right\\}$

we conclude:

$\max_{1\leq j\leq
d}\frac{1}{n}\left|\mathbf{X}_{*j}^{\top}\mathbf{Q}\mathbf{X}_{*j}-\mathbb{E}[\mathbf{X}_{*j}^{\top}\mathbf{Q}\mathbf{X}_{*j}]\right|\leq
K\max\left\\{\sqrt{\frac{\log{d}}{n}+p^{2}\log{d}},p\log{d}\right\\}\leq
K\max\left\\{\sqrt{\frac{\log{d}}{n}},p\log{d}\right\\}\,.$

Therefore, we have

$\max_{1\leq j\leq
d}\frac{1}{n}\sum_{i=1}^{n}{\mathbf{Z}}_{ij}^{2}\leq\sigma_{+}+K\max\left\\{\sqrt{\frac{\log{d}}{n}},p\log{d}\right\\}\leq
2\sigma_{+}$

with probability $\geq 1-n^{-1}-e^{\log{n}-\frac{np}{c}}$. Call this event
$\mathcal{E}_{1}$. Therefore, we have:

$\displaystyle\mathbb{P}\left(\max_{1\leq j\leq
d}\left|\frac{1}{\sqrt{n}}\sum_{i}{\mathbf{Z}}_{ij}\left\\{{\mathbf{Y}}_{i}-\psi^{\prime}({\mathbf{Z}}_{i}^{\top}{\bm{\beta}}^{(0)})\right\\}\right|\geq
t\right)$ $\displaystyle\leq\mathbb{P}\left(\max_{1\leq j\leq
d}\left|\frac{1}{\sqrt{n}}\sum_{i}{\mathbf{Z}}_{ij}\left\\{{\mathbf{Y}}_{i}-\psi^{\prime}({\mathbf{Z}}_{i}^{\top}{\bm{\beta}}^{(0)})\right\\}\right|\geq
t\mid\mathbf{Z}\in\mathcal{E}_{1}\right)+\mathbb{P}(\mathcal{E}_{1}^{c})$
$\displaystyle\leq c_{1}{\sf
exp}{\left(\log{d}-\frac{c_{2}t^{2}}{2\sigma_{+}}\right)}+\frac{1}{n}+{\sf
exp}{\left(\log{n}-\frac{np}{c}\right)}\,.$

Choosing $t=K\sqrt{\log{d}}$ we complete the proof.

###  C.3 Proof of Lemma C.9

Upper bound on $\|\tilde{\mathbf{A}}\|_{\operatorname{op}}$:  To establish a
bound on $\|\tilde{\mathbf{A}}\|_{\operatorname{op}}$, we first center it:

$\|\tilde{\mathbf{A}}\|_{\operatorname{op}}=\|\tilde{\mathbf{A}}-\mathbb{E}[\tilde{\mathbf{A}}]\|_{\operatorname{op}}+\|\mathbb{E}[\tilde{\mathbf{A}}]\|_{\operatorname{op}}\,.$

A bound on $\|\mathbb{E}[\tilde{\mathbf{A}}]\|_{\operatorname{op}}$ directly
follows from the definition:

$\|\mathbb{E}[\tilde{\mathbf{A}}]\|_{\operatorname{op}}=\frac{1}{\sqrt{np}}\|\mathbb{E}[\mathbf{A}]\|_{\operatorname{op}}=\frac{1}{\sqrt{np}}\|p(\mathbf{1}\mathbf{1}^{\top}-I)\|_{\operatorname{op}}\leq\sqrt{np}\,.$
(C.14)

Now we bound
$\|\tilde{\mathbf{A}}-\mathbb{E}[\tilde{\mathbf{A}}]\|_{\operatorname{op}}$.
As $\tilde{\mathbf{A}}=\mathbf{A}/\sqrt{np}$, it is enough to bound
$\|\mathbf{A}-\mathbb{E}[\mathbf{A}]\|_{\operatorname{op}}$. Using Corollary
3.12 and Remark 3.13 of [51] (with $\epsilon=1/2$), which implies:

$\mathbb{P}\left(\|\mathbf{A}-\mathbb{E}[\mathbf{A}]\|_{\operatorname{op}}\geq
3\sqrt{2}\tilde{\sigma}+t\right)\leq
e^{\log{n}-\frac{t^{2}}{c\sigma_{*}^{2}}}$

where

$\tilde{\sigma}=\max_{i}\sqrt{\sum_{j}\operatorname{Var}(\tilde{\mathbf{A}}_{ij})}=\sqrt{np(1-p)}\leq\sqrt{np},\
\ \sigma_{*}=\max_{i,j}|\mathbf{A}_{ij}|\leq 1\,.$

Therefore, we obtain:

$\mathbb{P}\left(\|\mathbf{A}-\mathbb{E}[\mathbf{A}]\|_{\operatorname{op}}\geq
3\sqrt{2}\sqrt{np}+t\right)\leq e^{\log{n}-\frac{t^{2}}{c}}$

Taking $t=\sqrt{np}$, we get:

$\mathbb{P}\left(\|\mathbf{A}-\mathbb{E}[\mathbf{A}]\|_{\operatorname{op}}\geq(1+3\sqrt{2})\sqrt{np}\right)\leq
e^{\log{n}-\frac{np}{c}}$

As $\tilde{\mathbf{A}}=\mathbf{A}/\sqrt{np}$, we have:

$\mathbb{P}\left(\|\tilde{\mathbf{A}}-\mathbb{E}[\tilde{\mathbf{A}}]\|_{\operatorname{op}}\geq(1+3\sqrt{2})\right)\leq
e^{\log{n}-\frac{np}{c}}$ (C.15)

Combining the bound on equation (C.14) and (C.15) we have with probability
$\geq 1-e^{\log{n}-\frac{np}{c}}$:

$\|\tilde{\mathbf{A}}\|_{\operatorname{op}}\leq\sqrt{np}+(1+3\sqrt{2})\leq
2\sqrt{np}\,.$ (C.16)

Finding a bound on $\|\tilde{\mathbf{A}}^{\top}\tilde{\mathbf{A}}\|_{F}^{2}$:
As before, we first find the expected value of
$\|\tilde{\mathbf{A}}^{\top}\tilde{\mathbf{A}}\|_{F}^{2}$. For any $1\leq
i\neq j\leq n$:

$\displaystyle\mathbb{E}[(\tilde{\mathbf{A}}^{\top}\tilde{\mathbf{A}})_{ij}^{2}]=\frac{1}{n^{2}p^{2}}\mathbb{E}[(\mathbf{A}^{\top}\mathbf{A})_{ij}^{2}]$
$\displaystyle=\frac{1}{n^{2}p^{2}}\mathbb{E}\left[\left(\sum_{k=1}^{n}\mathbf{A}_{ki}\mathbf{A}_{kj}\right)^{2}\right]$
$\displaystyle=\frac{1}{n^{2}p^{2}}\left(\sum_{k=1}^{n}\mathbb{E}[(\mathbf{A}_{ki}\mathbf{A}_{kj})^{2}]+\sum_{k\neq
l}\mathbb{E}[(\mathbf{A}_{ki}\mathbf{A}_{kj})(\mathbf{A}_{li}\mathbf{A}_{lj})]\right)$
$\displaystyle\leq\frac{1}{n^{2}p^{2}}(np^{2}+n^{2}p^{4})=\frac{1}{n}+p^{2}\,.$

Now for $1\leq i=j\leq n$:

$\displaystyle\mathbb{E}[(\tilde{\mathbf{A}}^{\top}\tilde{\mathbf{A}})_{ii}^{2}]$
$\displaystyle=\frac{1}{n^{2}p^{2}}\mathbb{E}\left[\left(\sum_{k=1}^{n}\mathbf{A}^{2}_{ki}\right)^{2}\right]$
$\displaystyle=\frac{1}{n^{2}p^{2}}\left(\sum_{k}\mathbb{E}[\mathbf{A}^{4}_{ki}]+\sum_{k\neq
l}\mathbb{E}[\mathbf{A}_{ki}^{2}\mathbf{A}_{li}^{2}]\right)$
$\displaystyle\leq\frac{1}{n^{2}p^{2}}(np+n^{2}p^{2})=\frac{1}{np}+1\,.$

Therefore, we have:

$\displaystyle\mathbb{E}[\|\tilde{\mathbf{A}}^{\top}\tilde{\mathbf{A}}\|_{F}^{2}]$
$\displaystyle=\sum_{i}\mathbb{E}[(\tilde{\mathbf{A}}^{\top}\tilde{\mathbf{A}})_{ii}^{2}]+\sum_{i\neq
j}\mathbb{E}[(\tilde{\mathbf{A}}^{\top}\tilde{\mathbf{A}})_{ij}^{2}]$
$\displaystyle\leq
n\left(\frac{1}{np}+1\right)+n^{2}\left(\frac{1}{n}+p^{2}\right)$
$\displaystyle\leq n+\frac{1}{p}+n^{2}p^{2}\leq n+n^{2}p^{2}\,.$

The last inequality follows from $p\geq n^{-1}$. Next, we establish a bound on
the variance:

$\displaystyle\operatorname{Var}\left(\|\tilde{\mathbf{A}}^{\top}\tilde{\mathbf{A}}\|_{F}^{2}\right)$
$\displaystyle=\frac{1}{n^{4}p^{4}}\operatorname{Var}(\|\mathbf{A}^{\top}\mathbf{A}\|_{F}^{2})$
$\displaystyle=\frac{1}{n^{4}p^{4}}\operatorname{Var}\left(\sum_{i,j}(\mathbf{A}^{\top}\mathbf{A})^{2}_{i,j}\right)$
$\displaystyle=\frac{1}{n^{4}p^{4}}\left[\sum_{i,j}\operatorname{Var}\left((\mathbf{A}^{\top}\mathbf{A})^{2}_{i,j}\right)+\sum_{(i,j)\neq(k,l)}\operatorname{Cov}((\mathbf{A}^{\top}\mathbf{A})^{2}_{i,j},(\mathbf{A}^{\top}\mathbf{A})^{2}_{k,l})\right]$
$\displaystyle\triangleq\frac{1}{n^{4}p^{4}}(T_{1}+T_{2})\,.$

We bound $T_{1}$ and $T_{2}$ separately. For that, we use some basic bounds on
the raw moments of a binomial random variable; if
$X\sim\operatorname{Ber}(n,p)$, then $\mathbb{E}[X^{k}]\leq Cn^{k}p^{k}$ for
all $k\in\\{1,2,3,4\\}$, for some universal constant $C$ as long as
$np\uparrow\infty$. Observe that
$({\mathbf{A}}^{\top}{\mathbf{A}})_{ii}\sim\operatorname{Ber}(n-1,p)$ and
$({\mathbf{A}}^{\top}{\mathbf{A}})_{ij}\sim\operatorname{Ber}(n-2,p^{2})$ for
$i\neq j$. For $T_{1}$ we have:

$\displaystyle\sum_{i,j}\operatorname{Var}\left((\mathbf{A}^{\top}\mathbf{A})^{2}_{i,j}\right)$
$\displaystyle=\sum_{i=1}^{n}\operatorname{Var}\left((\mathbf{A}^{\top}\mathbf{A})^{2}_{ii}\right)+\sum_{i\neq
j}\operatorname{Var}\left((\mathbf{A}^{\top}\mathbf{A})^{2}_{ij}\right)$
$\displaystyle\leq\sum_{i}\mathbb{E}[(\mathbf{A}^{\top}\mathbf{A})^{4}_{ii}]+\sum_{i\neq
j}\mathbb{E}[(\mathbf{A}^{\top}\mathbf{A})^{4}_{ij}]$ $\displaystyle\leq
C(n^{5}p^{4}+n^{6}p^{8})\,.$

Next, we bound $T_{2}$, i.e., the covariance term. Note that if $(i,j,k,l)$
all are distinct, then covariance is $0$ as the terms are independent.
Therefore, we only consider the cases when there are three or two distinct
indices. We first deal with the terms of two distinct indices, i.e.,
$\operatorname{Cov}(({\mathbf{A}}^{\top}{\mathbf{A}})^{2}_{ii},({\mathbf{A}}^{\top}{\mathbf{A}})^{2}_{ij})$
where $i\neq j$. There are almost $n^{2}$ many terms of this form. For each of
these types of terms:

$\displaystyle\operatorname{Cov}((\mathbf{A}^{\top}\mathbf{A})^{2}_{ii},(\mathbf{A}^{\top}\mathbf{A})^{2}_{ij})$
$\displaystyle=\mathbb{E}\left[(\mathbf{A}^{\top}\mathbf{A})^{2}_{ii}(\mathbf{A}^{\top}\mathbf{A})^{2}_{ij}\right]-\mathbb{E}\left[(\mathbf{A}^{\top}\mathbf{A})^{2}_{ii}\right]\mathbb{E}\left[(\mathbf{A}^{\top}\mathbf{A})^{2}_{ij}\right]$
$\displaystyle\leq\mathbb{E}\left[(\mathbf{A}^{\top}\mathbf{A})^{2}_{ii}(\mathbf{A}^{\top}\mathbf{A})^{2}_{ij}\right]$
$\displaystyle=\mathbb{E}\left[\left(\sum_{k,k^{\prime}=1}^{n}\mathbf{A}^{2}_{ki}\mathbf{A}_{k^{\prime}i}\mathbf{A}_{k^{\prime}j}\right)^{2}\right]$
$\displaystyle=\mathbb{E}\left[\left(\sum_{k}\mathbf{A}^{3}_{ki}\mathbf{A}_{kj}+\sum_{k\neq
k^{\prime}}\mathbf{A}^{2}_{ki}\mathbf{A}_{k^{\prime}i}\mathbf{A}_{k^{\prime}j}\right)^{2}\right]$
$\displaystyle=\mathbb{E}\left[\left(\sum_{k}\mathbf{A}_{ki}\mathbf{A}_{kj}+\sum_{k\neq
k^{\prime}}\mathbf{A}_{ki}\mathbf{A}_{k^{\prime}i}\mathbf{A}_{k^{\prime}j}\right)^{2}\right]$
$\displaystyle\leq
2\left(\mathbb{E}\left[\left(\sum_{k}\mathbf{A}_{ki}\mathbf{A}_{kj}\right)^{2}\right]+\mathbb{E}\left[\left(\sum_{k\neq
k^{\prime}}\mathbf{A}_{ki}\mathbf{A}_{k^{\prime}i}\mathbf{A}_{k^{\prime}j}\right)^{2}\right]\right)$
$\displaystyle\leq 2C(n^{2}p^{4}+n^{4}p^{6})\,.$

Therefore, we have:

$\sum_{i\neq
j}\operatorname{Cov}(({\mathbf{A}}^{\top}{\mathbf{A}})^{2}_{ii},({\mathbf{A}}^{\top}{\mathbf{A}})^{2}_{ij})\leq
2C(n^{4}p^{4}+n^{6}p^{6})\,.$ (C.17)

Next, we bound the covariance terms of the form
$\operatorname{Cov}(({\mathbf{A}}^{\top}{\mathbf{A}})^{2}_{ij},({\mathbf{A}}^{\top}{\mathbf{A}})^{2}_{jk})$,
i.e. two terms share an index with $i\neq j\neq k$. There are almost $n^{3}$
such terms. For each term:

$\displaystyle\operatorname{Cov}((\mathbf{A}^{\top}\mathbf{A})^{2}_{ij},(\mathbf{A}^{\top}\mathbf{A})^{2}_{jk})$
$\displaystyle\leq\mathbb{E}\left[(\mathbf{A}^{\top}\mathbf{A})^{2}_{ij}(\mathbf{A}^{\top}\mathbf{A})^{2}_{jk}\right]$
$\displaystyle=\mathbb{E}\left[\left(\sum_{l,l^{\prime}}\mathbf{A}_{li}\mathbf{A}_{lj}\mathbf{A}_{l^{\prime}i}\mathbf{A}_{l^{\prime}k}\right)^{2}\right]$
$\displaystyle=\mathbb{E}\left[\left(\sum_{l}\mathbf{A}^{2}_{li}\mathbf{A}_{lj}\mathbf{A}_{lk}+\sum_{l\neq
l^{\prime}}\mathbf{A}_{li}\mathbf{A}_{lj}\mathbf{A}_{l^{\prime}i}\mathbf{A}_{l^{\prime}k}\right)^{2}\right]$
$\displaystyle=\mathbb{E}\left[\left(\sum_{l}\mathbf{A}_{li}\mathbf{A}_{lj}\mathbf{A}_{lk}+\sum_{l\neq
l^{\prime}}\mathbf{A}_{li}\mathbf{A}_{lj}\mathbf{A}_{l^{\prime}i}\mathbf{A}_{l^{\prime}k}\right)^{2}\right]$
$\displaystyle=2\left(\mathbb{E}\left[\left(\sum_{l}\mathbf{A}_{li}\mathbf{A}_{lj}\mathbf{A}_{lk}\right)^{2}\right]+\mathbb{E}\left[\left(\sum_{l\neq
l^{\prime}}\mathbf{A}_{li}\mathbf{A}_{lj}\mathbf{A}_{l^{\prime}i}\mathbf{A}_{l^{\prime}k}\right)^{2}\right]\right)$
$\displaystyle\leq 2C(n^{2}p^{6}+n^{4}p^{8})\,.$

As there are almost $n^{3}$ such terms, we have:

$\sum_{i\neq j\neq
k}\operatorname{Cov}((\mathbf{A}^{\top}\mathbf{A})^{2}_{ij},(\mathbf{A}^{\top}\mathbf{A})^{2}_{jk})\leq
2C(n^{5}p^{6}+n^{7}p^{8})$ (C.18)

Therefore, combining (C.17) and (C.18), we have:

$T_{2}\leq C_{1}\left(n^{4}p^{4}+n^{6}p^{6}+n^{5}p^{6}+n^{7}p^{8}\right)\,.$

Combining the bounds on the variance and the covariance term, we conclude:

$\operatorname{Var}(\|\mathbf{A}^{\top}\mathbf{A}\|_{F}^{2})\leq
C_{2}(n^{5}p^{4}+n^{6}p^{8}+n^{4}p^{4}+n^{6}p^{6}+n^{5}p^{6}+n^{7}p^{8})\leq
C_{3}(n^{5}p^{4}+n^{6}p^{6}+n^{7}p^{8})\,.$

Here the last equality follows from the fact that $n^{5}p^{4}\geq n^{4}p^{4}$,
$n^{6}p^{6}\geq n^{6}p^{8}$ and $n^{6}p^{6}\geq n^{4}p^{4}$ (as $np\geq 1$).
As a consequence, we have:

$\operatorname{Var}(\|\tilde{\mathbf{A}}^{\top}\tilde{\mathbf{A}}\|_{F}^{2})=\frac{1}{n^{4}p^{4}}\operatorname{Var}(\|\mathbf{A}^{\top}\mathbf{A}\|_{F}^{2})\leq
C_{3}(n+n^{2}p^{2}+n^{3}p^{4})\,.$

The last step involves an application of Chebychev’s inequality:

$\mathbb{P}\left(\|\tilde{\mathbf{A}}^{\top}\tilde{\mathbf{A}}\|_{F}^{2}-\mathbb{E}[\|\tilde{\mathbf{A}}^{\top}\tilde{\mathbf{A}}\|_{F}^{2}]\geq
t\right)\leq\frac{\operatorname{Var}(\|\tilde{\mathbf{A}}^{\top}\tilde{\mathbf{A}}\|_{F}^{2})}{t^{2}}\,.$

Taking $t=n+n^{2}p^{2}$, we have:

$\displaystyle\mathbb{P}\left(\|\tilde{\mathbf{A}}^{\top}\tilde{\mathbf{A}}\|_{F}^{2}-\mathbb{E}[\|\tilde{\mathbf{A}}^{\top}\tilde{\mathbf{A}}\|_{F}^{2}]\geq
n+n^{2}p^{2}\right)\leq\frac{\operatorname{Var}(\|\tilde{\mathbf{A}}^{\top}\tilde{\mathbf{A}}\|_{F}^{2})}{(n+n^{2}p^{2})^{2}}\leq
C_{3}\frac{n(1+np^{2}+n^{2}p^{4})}{n^{2}(1+2np^{2}+n^{2}p^{4})}\leq\frac{C_{3}}{n}\,.$

Therefore, with probability $\geq 1-n^{-1}$:

$\|\tilde{\mathbf{A}}^{\top}\tilde{\mathbf{A}}\|_{F}^{2}\leq\mathbb{E}[\|\tilde{\mathbf{A}}^{\top}\tilde{\mathbf{A}}\|_{F}^{2}]+n+n^{2}p^{2}\leq
2(n+n^{2}p^{2})\,.$

##  Appendix D Extension of Theorem 4.4 under multiple source

In Theorem 4.4, we have established the convergence guarantee of $\hat{\beta}$
on a domain under network dependency. This section presents some ideas for
extending our analysis when we have data from multiple related source domains.
We have conjectured a theorem (Theorem D.10) and lay down the steps needed to
prove it. There is one conjecture (Conjecture D.8), which, if true, will lead
to a complete proof of the theorem.

We start a simple setting with one source domain $\mathcal{A}$ and one target
domain. Consider the transfer learning setup, in which we have $n_{1}$
observations from the source domain and $n_{0}$ observations from the target
domain. We assume that $p_{0}=p_{1}=p$. Define
$\mathbf{Z}=(\mathbf{A}\mathbf{X})/\sqrt{np}\in{\mathbb{R}}^{n\times d}$, and
${\mathbf{Z}}_{i}$ is the $i$th row of $\mathbf{Z}$. Given the logistic
regression, the inverse link function [52] for logit link is
$\psi^{\prime}(u)=\mathrm{logistic}(u)$, where $\psi(u)=\log(1+e^{u})$. The
method is similar to the proposed method, i.e., we have a two-step estimator:

  1. 1.

Step 1: First estimate $\hat{\bm{\beta}}^{\mathcal{A}}$ as:

$\hat{\bm{\beta}}^{\mathcal{A}}={\arg\min}_{\bm{\beta}}\
-\frac{1}{n_{\mathcal{A}}+n_{0}}\sum_{k\in\\{0,\mathcal{A}\\}}\left\\{(\mathbf{Y}^{(k)})^{\top}\mathbf{Z}^{(k)}\bm{\beta}-\log{(1+e^{\mathbf{Z}_{i}^{\top}\bm{\beta}})}\right\\}+\lambda_{{\bm{\beta}}}\left\|\bm{\beta}\right\|_{1}$

  2. 2.

Step 2: Then estimate the correction $\hat{\delta}^{\mathcal{A}}$ only based
on the target observations:

$\hat{\bm{\delta}}^{\mathcal{A}}={\arg\min}_{\bm{\delta}}\
-\frac{1}{n_{0}}\left\\{(\mathbf{Y}^{(0)})^{\top}\mathbf{Z}^{(0)}(\hat{\bm{\beta}}^{\mathcal{A}}+\bm{\delta})-\log{(1+e^{\mathbf{Z}^{\top}(\hat{\bm{\beta}}^{\mathcal{A}}+\bm{\delta})})}\right\\}+\lambda_{\delta}\left\|\bm{\delta}\right\|_{1}\,.$

Our final estimator for the target coefficient $\bm{\beta}^{(0)}$ is
$\hat{\bm{\beta}}^{(0)}=\hat{\bm{\beta}}^{\mathcal{A}}+\hat{\bm{\delta}}^{\mathcal{A}}$.
We must extend Theorem 1 of [31] to handle the network dependency. There are
two key steps in the proof: i) to establish the rate of convergence of
$\hat{\bm{\beta}}^{\mathcal{A}}$ (which is the estimator of
$\bm{\beta}^{\mathcal{A}}$ obtained by combining all the observations from
both the set of transferable source $\mathcal{A}$ and the target domain, and
ii) then establish the rate of convergence of the $\bm{\beta}^{(0)}$ is
$\hat{\bm{\beta}}^{(0)}=\hat{\bm{\beta}}^{\mathcal{A}}+\hat{\bm{\delta}}^{\mathcal{A}}$,
where $\hat{\bm{\delta}}^{\mathcal{A}}$ is obtained using only the target
observations.

We will use bolded $\bm{\psi}^{\prime}$ hereafter to denote the vector with
each component from the scalar function $\psi^{\prime}$ with corresponding
variables. Define
$\hat{\bm{u}}^{\mathcal{A}}=\hat{\bm{\beta}}^{\mathcal{A}}-\bm{\beta}^{\mathcal{A}}$,
$\mathcal{D}=\left\\{\left(\bm{\mathbf{Z}}^{(k)},\mathbf{Y}^{(k)}\right)\right\\}_{k\in\\{0,\mathcal{A}\\}}$,
and $L(\bm{\beta},\mathcal{D})$ is the negative log likelihood on the combined
sample $\mathcal{D}$:

$\displaystyle L(\bm{\beta},\mathcal{D})$
$\displaystyle=-\frac{1}{n_{\mathcal{A}}+n_{0}}\sum_{k\in\\{0,\mathcal{A}\\}}\left(\mathbf{Y}^{(k)}\right)^{T}\mathbf{Z}^{(k)}\bm{\beta}+\frac{1}{n_{\mathcal{A}}+n_{0}}\sum_{k\in\\{0,\mathcal{A}\\}}\sum_{i=1}^{n_{k}}\psi\left(\bm{\beta}^{T}\mathbf{Z}_{i}^{(k)}\right)$
$\displaystyle\nabla L(\bm{\beta},\mathcal{D})$
$\displaystyle=-\frac{1}{n_{\mathcal{A}}+n_{0}}\sum_{k\in\\{0,\mathcal{A}\\}}\left(\mathbf{Z}^{(k)}\right)^{T}\mathbf{Y}^{(k)}+\frac{1}{n_{\mathcal{A}}+n_{0}}\sum_{k\in\\{0,\mathcal{A}\\}}\left(\mathbf{Z}^{(k)}\right)^{T}\bm{\psi}^{\prime}\left(\bm{\beta}^{T}\mathbf{Z}_{i}^{(k)}\right)$
$\displaystyle\delta L(\bm{u},\mathcal{D})$
$\displaystyle={L}\left(\bm{\beta}^{\mathcal{A}}+\bm{u},\mathcal{D}\right)-L\left(\bm{\beta}^{\mathcal{A}}\right)-\nabla
L\left(\bm{\beta}^{\mathcal{A}}\right)^{T}\bm{u}.$

We present useful assumptions and lemmas first.

######  Assumption D.1.

(SubGaussian Assumption.) For any
$\bm{a}\in\mathbb{R}^{p},\bm{a}^{T}\mathbf{X}^{(k)}$ are
$\kappa_{u}\|\bm{a}\|_{2}^{2}$-subGaussian variables with zero mean for all
$k\in\\{0,\mathcal{A}\\}$, where $\kappa_{u}$ is a positive constant.

######  Assumption D.2.

(Positive Definite Covariance Assumption.) Denote the covariance matrix of
$\mathbf{X}^{(k)}$ as $\bm{\Sigma}^{(k)}_{\mathbf{X}}$,
$k\in\\{0,\mathcal{A}\\}$, we require that
$\lambda_{\min}\left(\bm{\Sigma}^{(k)}_{\mathbf{X}}\right)\geq\kappa_{l}>0$,
where $\kappa_{l}$ is a positive constant.

######  Assumption D.3.

(Connectivity Bound of Network.) $p_{k}>\frac{\log n_{k}}{n_{k}}$,
$k\in\\{0,\mathcal{A}\\}$.

######  Assumption D.4.

Denote

$\widetilde{\bm{\Sigma}}_{h}=\sum_{k\in\\{0,\mathcal{A}\\}}\alpha_{k}\mathbb{E}\left[\bm{\mathbf{S}}^{(k)}\left(\bm{\mathbf{S}}^{(k)}\right)^{T}\int_{0}^{1}\psi^{\prime\prime}\left(\left(\bm{\mathbf{S}}^{(k)}\right)^{T}\bm{\beta}^{(0)}+t\left(\bm{\mathbf{S}}^{(k)}\right)^{T}\left(\bm{\beta}^{\mathcal{A}}-\bm{\beta}^{(0)}\right)\right)dt\right]$

and
$\widetilde{\bm{\Sigma}}_{h}^{(k)}=\mathbb{E}\left[\int_{0}^{1}\psi^{\prime\prime}\left(\left(\bm{\mathbf{S}}^{(k)}\right)^{T}\bm{\beta^{(0)}}+t\left(\bm{\mathbf{Z}}^{(k)}\right)^{T}\left({\bm{\beta}}^{(k)}-\bm{\beta^{(0)}}\right)\right)dt\cdot\bm{\mathbf{S}}^{(k)}\left(\bm{\mathbf{S}}^{(k)}\right)^{T}\right]$.
It holds that
$\sup_{k\in\\{0,\mathcal{A}\\}}\left\|\widetilde{\bm{\Sigma}}_{h}^{-1}\widetilde{\bm{\Sigma}}_{h}^{(k)}\right\|_{1}<\infty$.

######  Lemma D.5.

Under Assumptions D.1 and D.4,

$\left\|{\bm{\delta}}^{\mathcal{A}}\right\|_{1}=\left\|\bm{\beta}^{\mathcal{A}}-\bm{\beta}^{(0)}\right\|_{1}\leq
C_{l}h$

where ${\bm{\beta}}^{\mathcal{A}}$ is the true coefficient of Step 1,
$\bm{\delta}^{\mathcal{A}}$ is the true coefficient of Step 2, and
$\bm{\beta}^{(0)}$ is the true coefficient of target domain. And
$C_{l}:=\sup_{k\in\mathcal{T}\cup\mathcal{A}}\left\|\widetilde{\bm{\Sigma}}_{h}^{-1}\widetilde{\bm{\Sigma}}_{h}^{(k)}\right\|_{1}<\infty$.

######  Lemma D.6.

Under Assumptions D.1 and D.2, there exists some positive constants
$\kappa_{l}$ and $C_{4}$ such that,

$\delta L(\bm{u},\mathcal{D})\geq
L_{\psi}(T)\|\bm{u}\|_{2}^{2}\left\\{\kappa_{l}-\left(C_{4}\log{d}\sqrt{\frac{\Psi(p)}{n}}\right)\frac{\|\bm{u}\|_{1}}{\|\bm{u}\|_{2}}\right\\}$

with probability at least $1-({\sf
exp}{\left(\frac{1}{2}\log{d}+1-c_{4}\log^{2}{d}\Psi(p)\right)}+2{\sf
exp}{\left(1-(c_{1}-3/2)\log{d}\right)}+2{\sf
exp}{\left(\frac{3}{2}\log{d}+1-c_{2}n\right)})$, where $T$ is some constant,
$L_{\psi}(T)=\min\limits_{u\leq|2T|}{\psi^{{\prime}{\prime}}(u)}$, and
$\Psi(p)\sim 1/(-4p\log{p})$.

######  Lemma D.7.

Under Assumption D.1, there are universal positive constants
$(c_{6},c_{7},c_{8})$ such that

$\frac{1}{n_{\mathcal{A}}+n_{0}}\left\|\sum_{k\in\\{0,\mathcal{A}\\}}\left(\mathbf{Z}^{(k)}\right)^{T}\left[\mathbf{Y}^{(k)}-\bm{\psi}^{\prime}\left(\mathbf{Z}^{(k)}\bm{\beta}^{(k)}\right)\right]\right\|_{\infty}\lesssim\sqrt{\frac{\log
d}{n_{\mathcal{A}}+n_{0}}}$

with probability
$1-(c_{6}\left(d^{-c_{7}}+\sum_{k}n_{k}^{-1}+\sum_{k}e^{\log{n_{k}}-n_{k}p_{k}/c_{8}}\right))$.

######  Conjecture D.8.

Under Assumption D.1, there are universal positive constants
$(c_{9},c_{10},c_{11})$ such that

$\frac{1}{n_{\mathcal{A}}+n_{0}}\left\|\sum_{k\in\\{0,\mathcal{A}\\}}\left(\mathbf{Z}^{(k)}\right)^{T}\left[\bm{\psi}^{\prime}\left(\mathbf{Z}^{(k)}\bm{\beta}^{(k)}\right)-\bm{\psi}^{\prime}\left(\mathbf{Z}^{(k)}\bm{\beta}^{\mathcal{A}}\right)\right]\right\|_{\infty}\lesssim\sqrt{\frac{\log
d}{n_{\mathcal{A}}+n_{0}}}$

with probability $1-c_{9}d^{-c_{10}}+{\sf
exp}\left[-c_{11}\left(n_{\mathcal{A}}+n_{0}\right)\right]$.

######  Lemma D.9.

With high probability of at least
$1-d^{-\tilde{K}}-n^{-1}-e^{\log{n}-\frac{np}{c}}$, where $\tilde{K}$ and $c$
are some constants, there exists some constant $C$ such that:

$\frac{\|\mathbf{A}\mathbf{X}\mathbf{v}\|_{2}^{2}}{n^{2}p\|\mathbf{v}\|_{2}^{2}}=\frac{\mathbf{v}^{\top}\mathbf{X}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{X}\mathbf{v}}{n^{2}p\|\mathbf{v}\|_{2}^{2}}\leq
C\qquad\forall\
\mathbf{v}:\|\mathbf{v}_{S^{c}}\|_{1}\leq\kappa\|\mathbf{v}_{S}\|_{1}\,.$

######  Theorem D.10.

(Convergence rate of Trans-GCR). Under Assumptions D.1, D.2, D.3, D.4, suppose
$h\ll\sqrt{\frac{n_{0}}{\log d}},h\leq c\sqrt{s},n_{0}\geq c\log d$ and
$n_{\mathcal{A}}\geq$ $cs\log d$, where $c>0$ is a constant, we have

$\begin{array}[]{r}\sup_{\xi\in\Xi(s,h)}\mathbb{P}\left(\|\hat{\bm{\beta}}^{(0)}-\bm{\beta}^{(0)}\|_{2}\lesssim
h\log{d}\sqrt{\frac{\Psi(p)}{n_{\mathcal{A}}+n_{0}}}+\sqrt{\frac{s\log
d}{n_{\mathcal{A}}+n_{0}}}+\left(\frac{\log
d}{n_{\mathcal{A}}+n_{0}}\right)^{1/4}\sqrt{h}\right)\geq
1-n_{0}^{-1}\par\end{array}$

###  D.1 Proof of Lemma D.5

By definition in (D.1),

$\sum_{k\in\\{0,\mathcal{A}\\}}\alpha_{k}\mathbb{E}\left\\{\left[\psi^{\prime}\left(\left({\bm{\beta}}^{\mathcal{A}}\right)^{T}\mathbf{Z}^{(k)}\right)-\psi^{\prime}\left(\left({\bm{\beta}}^{(k)}\right)^{T}{\mathbf{Z}}^{(k)}\right)\right]{\mathbf{Z}}^{(k)}\right\\}=\mathbf{0}_{p}$

which implies

$\displaystyle\sum_{k\in\\{0,\mathcal{A}\\}}\alpha_{k}\mathbb{E}\left\\{\left[\psi^{\prime}\left(\left(\bm{\beta}^{\mathcal{A}}\right)^{T}\mathbf{Z}^{(k)}\right)-\psi^{\prime}\left(\left({\bm{\beta}}^{(0)}\right)^{T}\mathbf{Z}^{(k)}\right)\right]\mathbf{Z}^{(k)}\right\\}$
$\displaystyle=$
$\displaystyle\sum_{k\in\\{0,\mathcal{A}\\}}\alpha_{k}\mathbb{E}\left\\{\left[\psi^{\prime}\left(\left(\bm{\beta}^{(k)}\right)^{T}\mathbf{Z}^{(k)}\right)-\psi^{\prime}\left(\left(\bm{\beta}^{(0)}\right)^{T}\mathbf{Z}^{(k)}\right)\right]\mathbf{Z}^{(k)}\right\\}$

By Taylor expansion,

$\displaystyle\sum_{k\in\\{0,\mathcal{A}\\}}\alpha_{k}\mathbb{E}\left[\int_{0}^{1}\psi^{\prime\prime}\left(\left(\bm{\beta}^{\mathcal{A}}\right)^{T}{\mathbf{Z}}^{(k)}+t\left(\bm{\beta}^{\mathcal{A}}-\bm{\beta}^{(0)}\right)^{T}\mathbf{Z}^{(k)}\right)\mathbf{Z}^{(k)}\left(\mathbf{Z}^{(k)}\right)^{T}\right]\left(\bm{\beta}^{\mathcal{A}}-\bm{\beta}^{(0)}\right)$
$\displaystyle=$
$\displaystyle\sum_{k\in\\{0,\mathcal{A}\\}}\alpha_{k}\mathbb{E}\left[\int_{0}^{1}\psi^{\prime\prime}\left(\left(\bm{\beta}^{(k)}\right)^{T}{\mathbf{Z}}^{(k)}+t\left(\bm{\beta}^{(k)}-\bm{\beta}^{(0)}\right)^{T}\mathbf{Z}^{(k)}\right)\mathbf{Z}^{(k)}\left(\mathbf{Z}^{(k)}\right)^{T}\right]\left(\bm{\beta}^{(k)}-\bm{\beta}^{(0)}\right)$

Therefore, by Assumption D.4,
$\left\|\bm{\beta}^{\mathcal{A}}-\bm{\beta}^{(0)}\right\|_{1}\leq\sum_{k\in\mathcal{A}}\alpha_{k}\left\|\widetilde{\bm{\Sigma}}_{h}^{-1}\widetilde{\bm{\Sigma}}_{h}^{(k)}\right\|_{1}\cdot\left\|\bm{\beta}^{(k)}-\bm{\beta}^{(0)}\right\|_{1}\leq
C_{l}h$.

###  D.2 Proof of Lemma D.6

See proof of Lemma B.1.

###  D.3 Proof of Lemma D.7

Here, we define $\mathbf{B}_{i}$ as the $i$-th row of matrix $\mathbf{B}$, and
$\mathbf{B}_{(j)}$ as the $j$-th column of matrix $\mathbf{B}$. For a fixed
index $j\in\\{1,2,\ldots,p\\}$, we denote
$R_{ij}^{(k)}:=\mathbf{Z}_{ij}^{(k)}\left(Y_{i}^{(k)}-\psi^{\prime}\left(\left\langle{\bm{\beta}}^{(k)},\mathbf{Z}_{i}^{(k)}\right\rangle\right)\right)$,
and the $j$-th element of
$\left(\mathbf{Z}^{(k)}\right)^{T}\left[\mathbf{Y}^{(k)}-\bm{\psi}^{\prime}\left(\mathbf{Z}^{(k)}\bm{\beta}^{(k)}\right)\right]$
can be written as $\sum_{i=1}^{n_{k}}R_{ij}^{(k)}$. Given the condition
$\left\\{\mathbf{Z}_{i}^{(k)}\right\\}_{i=1}^{n_{k}}$ , $y_{i}^{(k)}$ follow a
Bernoulli distribution with parameter $\frac{{\sf
exp}\left(\left\langle\bm{\beta}^{(k)},\mathbf{Z}_{i}^{(k)}\right\rangle\right)}{1+{\sf
exp}\left(\left\langle\bm{\beta}^{(k)},\mathbf{Z}_{i}^{(k)}\right\rangle\right)}$.
For any $t\in\mathbb{R}$, we compute

$\displaystyle\log\mathbb{E}\left[{\sf
exp}\left(tR_{ij}^{(k)}\right)\mid\mathbf{Z}_{i}^{(k)}\right]$
$\displaystyle=\log\left\\{\mathbb{E}\left[{\sf
exp}\left(t\mathbf{Z}_{ij}^{(k)}Y_{i}^{(k)}\right)\mid\mathbf{Z}_{i}^{(k)}\right]{\sf
exp}\left(-t\mathbf{Z}_{ij}^{(k)}\psi^{\prime}\left(\left\langle\bm{\beta}^{(k)},\mathbf{Z}_{i}^{(k)}\right\rangle\right)\right)\right\\}$
$\displaystyle=\psi\left(t\mathbf{Z}_{ij}^{(k)}+\left\langle\bm{\beta}^{(k)},\mathbf{Z}_{i}^{(k)}\right\rangle\right)-\psi\left(\left\langle\bm{\beta}^{(k)},\mathbf{Z}_{i}^{(k)}\right\rangle\right)-t{\mathbf{Z}}_{ij}^{(k)}\psi^{\prime}\left(\left\langle\bm{\beta}^{(k)},\mathbf{Z}_{i}^{(k)}\right\rangle\right)$

By second-order Taylor series expansion, we have

$\log\mathbb{E}\left[{\sf
exp}\left(tR_{ij}^{(k)}\right)\mid\mathbf{Z}_{i}^{(k)}\right]=\frac{t^{2}}{2}\mathbf{Z}_{ij}^{2}\psi^{\prime\prime}\left(\left\langle\bm{\beta}^{(k)},\mathbf{Z}_{i}^{(k)}\right\rangle+v_{i}t\mathbf{Z}_{ij}^{(k)}\right)\quad\text{
for some }v_{i}\in[0,1]$

Since this upper bound holds for each $i=1,2,\ldots,n_{k}$, we have shown that

$\sum_{i=1}^{n_{k}}\log\mathbb{E}\left[{\sf
exp}\left(tR_{ij}^{(k)}\right)\mid\mathbf{Z}_{i}^{(k)}\right]\leq\frac{t^{2}}{2}\left\\{\sum_{i=1}^{n_{k}}\left(\mathbf{Z}_{ij}^{(k)}\right)^{2}\psi^{\prime\prime}\left(\left\langle\bm{\beta}^{(k)},\mathbf{Z}_{i}^{(k)}\right\rangle+v_{i}t\mathbf{Z}_{ij}^{(k)}\right)\right\\}$

For the link function $\psi(x)=\log\left\\{1+{\sf
exp}\left(x\right)\right\\}$, it is easy to know that its second derivative
$\psi^{\prime\prime}(x)={\sf exp}\left(x\right)/\left(1+{\sf
exp}\left(x\right)\right)^{2}$ takes values between 0 and 1, therefore the
aforementioned equation can be simply bounded by an upper bound:

$\sum_{i=1}^{n_{k}}\log\mathbb{E}\left[{\sf
exp}\left(tR_{ij}^{(k)}\right)\mid\mathbf{Z}_{i}^{(k)}\right]\leq\frac{t^{2}}{2}\sum_{i=1}^{n_{k}}\left(\mathbf{Z}_{ij}^{(k)}\right)^{2}$

and

$\sum_{k\in\\{0,\mathcal{A}\\}}\sum_{i=1}^{n_{k}}\log\mathbb{E}\left[{\sf
exp}\left(tR_{ij}^{(k)}\right)\mid\mathbf{Z}_{i}^{(k)}\right]\leq\frac{t^{2}}{2}\sum_{k\in\\{0,\mathcal{A}\\}}\sum_{i=1}^{n_{k}}\left(\mathbf{Z}_{ij}^{(k)}\right)^{2}$

To control
$\sum_{k\in\\{0,\mathcal{A}\\}}\sum_{i=1}^{n_{k}}\left(\mathbf{Z}_{ij}^{(k)}\right)^{2}$,
it is easy to observe that it is a kind of quadratic forms respect to
$\mathbf{X}^{(k)}_{(j)}$ so we will use Hanson-Wright inequality:

$\displaystyle\sum_{k\in\\{0,\mathcal{A}\\}}\sum_{i=1}^{n_{k}}\left(\mathbf{Z}_{ij}^{(k)}\right)^{2}$
$\displaystyle=$
$\displaystyle\sum_{k\in\\{0,\mathcal{A}\\}}{\mathbf{Z}_{(j)}^{(k)}}^{T}\mathbf{Z}_{(j)}^{(k)}$
$\displaystyle=$
$\displaystyle\sum_{k\in\\{0,\mathcal{A}\\}}\left(\widetilde{\mathbf{A}}^{(k)}\mathbf{X}_{(j)}^{(k)}\right)^{T}\widetilde{\mathbf{A}}^{(k)}\mathbf{X}_{(j)}^{(k)}$
$\displaystyle\stackrel{{\scriptstyle\triangle}}{{=}}$
$\displaystyle\sum_{k\in\\{0,\mathcal{A}\\}}{\mathbf{X}_{(j)}^{(k)}}^{T}\mathbf{Q}^{(k)}\mathbf{X}_{(j)}^{(k)}$
$\displaystyle=$
$\displaystyle{\mathbf{X}_{(j)}}^{T}\mathbf{Q}\mathbf{X}_{(j)}$

where $\mathbf{X}_{(j)}\in\mathbb{R}^{(n_{\mathcal{A}}+n_{0})}$ represents the
vector obtained by vertically concatenating $\mathbf{X}_{(j)}^{(k)}$, and
$\mathbf{Q}\in\mathbb{R}^{(n_{\mathcal{A}}+n_{0})\times(n_{\mathcal{A}}+n_{0})}$
represents the block diagonal matrix with diagonal elements
$\mathbf{Q}^{(k)}$. Hanson-Wright inequality tell us:

$\displaystyle\mathbb{P}\left\\{\left|{\mathbf{X}_{(j)}}^{T}\mathbf{Q}\mathbf{X}_{(j)}-\mathrm{E}\left[{\mathbf{X}_{(j)}}^{T}\mathbf{Q}\mathbf{X}_{(j)}\right]\right|>t\right\\}$
$\displaystyle\leq$ $\displaystyle 2{\sf
exp}\Big{[}-c\min\Big{(}\frac{t^{2}}{\kappa_{u}^{4}\|\mathbf{Q}\|_{\mathrm{F}}^{2}},\frac{t}{\kappa_{u}^{2}\|\mathbf{Q}\|_{2}}\Big{)}\Big{]}$

In our article on linear regression, we have already proven that

$\displaystyle\|\mathbf{Q}\|_{F}^{2}=\sum_{k\in\\{0,\mathcal{A}\\}}\|\mathbf{Q}^{(k)}\|_{F}^{2}\leq\sum_{k\in\\{0,\mathcal{A}\\}}2(n_{k}+(n_{k}p_{k})^{2})$
$\displaystyle\|\mathbf{Q}\|_{2}=\max_{k\in\\{0,\mathcal{A}\\}}\|\mathbf{Q}^{(k)}\|_{2}\leq
4\max_{k\in\\{0,\mathcal{A}\\}}\left\\{n_{k}p_{k}\right\\}$

with high probability
$1-\sum_{k}n_{k}^{-1}-\sum_{k}e^{\log{n_{k}}-\frac{n_{k}p_{k}}{c}}$ converge
to 1, and
$\mathrm{E}\left[{\mathbf{X}_{(j)}}^{T}\mathbf{Q}\mathbf{X}_{(j)}\right]=\sigma_{jj}^{2}\left(n_{\mathcal{A}}+n_{0}\right)$

So we have the tail bound

$\displaystyle\mathbb{P}\left[\frac{1}{n_{\mathcal{A}}+n_{0}}\sum_{k\in\\{0,\mathcal{A}\\}}\sum_{i=1}^{n_{k}}\left(\mathbf{Z}_{ij}^{(k)}\right)^{2}\geq
C\right]$ $\displaystyle\leq$ $\displaystyle 2{\sf
exp}(-\frac{n_{\mathcal{A}}+n_{0}}{2})+\sum_{k}n_{k}^{-1}+\sum_{k}e^{\log{n_{k}}-\frac{n_{k}p_{k}}{c}}$

Define the event
$\mathcal{E}=\left\\{\max_{j=1,\ldots,p}\frac{1}{n_{\mathcal{A}}+n_{0}}\sum_{k\in\\{0,\mathcal{A}\\}}\sum_{i=1}^{n_{k}}\left(\mathbf{Z}_{ij}^{(k)}\right)^{2}\leq
C\right\\}$, we have

$\displaystyle\mathbb{P}\left[\mathcal{E}^{c}\right]$ $\displaystyle\leq 2{\sf
exp}\left(-\frac{n_{\mathcal{A}}+n_{0}}{2}+\log
d\right)+\sum_{k}n_{k}^{-1}+\sum_{k}e^{\log{n_{k}}-\frac{n_{k}p_{k}}{c}}$
$\displaystyle\leq$ $\displaystyle 2{\sf
exp}(-c\left(n_{\mathcal{A}}+n_{0})\right)+\sum_{k}n_{k}^{-1}+\sum_{k}e^{\log{n_{k}}-\frac{n_{k}p_{k}}{c}}$

where we have used the fact that $n_{\mathcal{A}}\gg\log d$.

Given that $\left\\{\mathbf{Z}_{i}^{(k)}\right\\}\in\mathcal{E}$, using the
independence between $R_{ij}^{(k)}$ given $\mathbf{Z}_{i}^{(k)}$, we have

$\displaystyle\frac{1}{n_{\mathcal{A}}+n_{0}}\sum_{k\in\\{0,\mathcal{A}\\}}\sum_{i=1}^{n_{k}}\log\mathbb{E}\left[{\sf
exp}\left(tR_{ij}^{(k)}\right)\mid\mathbf{Z}_{i}^{(k)}\right]$
$\displaystyle=$
$\displaystyle\frac{1}{n_{\mathcal{A}}+n_{0}}\sum_{k\in\\{0,\mathcal{A}\\}}\sum_{i=1}^{n_{k}}\mathbb{E}\left[tR_{ij}^{(k)}\mid\mathbf{Z}_{i}^{(k)}\right]$
$\displaystyle\leq$ $\displaystyle ct^{2}\quad\text{ for each }j=1,2,\ldots,d$

By the Chernoff bound, we obtain

$\mathbb{P}\left[\left|\frac{1}{n_{\mathcal{A}}+n_{0}}\sum_{k\in\\{0,\mathcal{A}\\}}\sum_{i=1}^{n_{k}}R_{ij}^{(k)}\right|\geq\delta\mid\mathbf{Z}_{i}\right]\leq
2{\sf exp}\left(-c(n_{\mathcal{A}}+n_{0})\delta^{2}\right)$

Combining this bound with the union bound yields

$\mathbb{P}\left[\max_{j=1,\ldots,d}\left|\frac{1}{n_{\mathcal{A}}+n_{0}}\sum_{k\in\\{0,\mathcal{A}\\}}\sum_{i=1}^{n_{k}}R_{ij}^{(k)}\right|\geq
t\mid\mathcal{E}\right]\leq 2{\sf
exp}\left(-c(n_{\mathcal{A}}+n_{0})t^{2}+\log d\right)$

Setting $t=c\sqrt{\frac{\log d}{n_{\mathcal{A}}+n_{0}}}$, and putting together
the pieces yields

$\displaystyle\mathbb{P}\left[\max_{j=1,\ldots,d}\left|\frac{1}{n_{\mathcal{A}}+n_{0}}\sum_{k\in\\{0,\mathcal{A}\\}}\sum_{i=1}^{n_{k}}R_{ij}^{(k)}\right|\geq
c\sqrt{\frac{\log d}{n_{\mathcal{A}}+n_{0}}}\right]$ $\displaystyle\leq$
$\displaystyle\mathbb{P}\left[\mathcal{E}^{c}\right]+\mathbb{P}\left[\max_{j=1,\ldots,d}\left|\frac{1}{n_{\mathcal{A}}+n_{0}}\sum_{k\in\\{0,\mathcal{A}\\}}\sum_{i=1}^{n_{k}}R_{ij}^{(k)}\right|\geq
t\mid\mathcal{E}\right]$ $\displaystyle\leq$ $\displaystyle
c_{6}d^{-c_{7}}+\sum_{k}n_{k}^{-1}+\sum_{k}e^{\log{n_{k}}-\frac{n_{k}p_{k}}{c_{8}}}$

###  D.4 Proof of Lemma D.9

In this section, we prove that with high probability, there exists some
constant $c_{12}$ such that:

$\frac{\|\mathbf{Z}\mathbf{v}\|_{2}^{2}}{n\|\mathbf{v}\|_{2}^{2}}=\frac{\|\mathbf{A}\mathbf{X}\mathbf{v}\|_{2}^{2}}{n^{2}p\|\mathbf{v}\|_{2}^{2}}=\frac{\mathbf{v}^{\top}\mathbf{X}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{X}\mathbf{v}}{n^{2}p\|\mathbf{v}\|_{2}^{2}}\leq
c_{12}\ \forall\
\mathbf{v}:\|\mathbf{v}_{S^{c}}\|_{1}\leq\kappa\|\mathbf{v}_{S}\|_{1}\,.$

Using our previous notation, we define
$\mathbf{Z}=(\mathbf{A}\mathbf{X})/\sqrt{np}$. Define events
$\Omega_{n,1}=\left\\{\|\mathbf{A}^{\top}\mathbf{A}\|_{\operatorname{op}}/np\leq
4np\right\\}$ and
$\Omega_{n,2}=\left\\{\|\mathbf{A}^{\top}\mathbf{A}\|_{F}^{2}/np\leq
2(n+n^{2}p^{2})\right\\}$

Therefore, we have:

$\displaystyle\mathbb{P}\left(\left\|\frac{(\mathbf{X}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{X})}{n^{2}p}-\Sigma_{X}\left(1-\frac{1}{n}\right)\right\|_{\infty}\geq
t\right)$
$\displaystyle\leq\mathbb{P}\left(\left\|\frac{(\mathbf{X}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{X})}{n^{2}p}-\Sigma_{X}\left(1-\frac{1}{n}\right)\right\|_{\infty}\geq
t\mid\mathbf{A}\in\Omega_{n,1}\cap\Omega_{n,2}\right)+\mathbb{P}(\mathbf{A}\in(\Omega_{n,1}\cap\Omega_{n,2})^{c})$
$\displaystyle\leq 2{\sf
exp}{\left(2\log{d}-c^{\prime}\min\left(\frac{n^{2}t^{2}}{n+n^{2}p^{2}},\frac{t}{p}\right)\right)}+e^{\log{n}-\frac{np}{c}}+\frac{1}{n}\,.$

The last step comes from Hanson Wright inequality.

Therefore, choosing

$t=K\max\left\\{\sqrt{\frac{\log{d}}{n}+p^{2}\log{d}},p\log{d}\right\\}$

we conclude:

$\boxed{\left\|\frac{(\mathbf{X}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{X})}{n^{2}p}-\Sigma_{X}\left(1-\frac{1}{n}\right)\right\|_{\infty}\leq
K\max\left\\{\sqrt{\frac{\log{d}}{n}+p^{2}\log{d}},p\log{d}\right\\}\leq
K\max\left\\{\sqrt{\frac{\log{d}}{n}},p\log{d}\right\\}\,.}$

which means

$\left\|\frac{\mathbf{X}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{X}}{n^{2}p}-\Sigma_{X}\right\|_{\infty}\leq
K\max\left\\{\sqrt{\frac{\log{d}}{n}},p\log{d}\right\\}\triangleq\epsilon_{n}\,.$

with probability $\geq 1-d^{-\tilde{K}}-n^{-1}-e^{\log{n}-\frac{np}{c}}$ for
some constant $c$ and $\tilde{K}$.

Using this, we have:

$\displaystyle\frac{\mathbf{v}^{\top}\mathbf{Z}^{\top}\mathbf{Z}\mathbf{v}}{n\|\mathbf{v}\|^{2}}$
$\displaystyle=\frac{\mathbf{v}^{\top}\Sigma_{X}\mathbf{v}}{\|\mathbf{v}\|^{2}}+\frac{\mathbf{v}^{\top}(\mathbf{Z}^{\top}\mathbf{Z}/n-\Sigma_{Z})\mathbf{v}}{\|\mathbf{v}\|^{2}}$
$\displaystyle\leq\lambda_{\max}(\Sigma_{X})+\left\|\frac{\mathbf{Z}^{\top}\mathbf{Z}}{n}-\Sigma_{X}\right\|_{\infty}\frac{\|\mathbf{v}\|_{1}^{2}}{\|\mathbf{v}\|^{2}_{2}}$
$\displaystyle\leq\lambda_{\max}(\Sigma_{X})+\epsilon_{n}\frac{(1+\kappa)^{2}s\|\mathbf{v}\|_{2}^{2}}{\|\mathbf{v}\|_{2}^{2}}$
$\displaystyle\leq\lambda_{\max}(\Sigma_{X})+(1+\kappa)^{2}s\epsilon_{n}\,.$

Here the penultimate inequality follows from the fact:

$\|\mathbf{v}\|_{1}=\|\mathbf{v}_{S}\|_{1}+\|\mathbf{v}_{S^{c}}\|_{1}\leq(1+k)\|\mathbf{v}_{S}\|_{1}\leq(1+k)\sqrt{s}\|\mathbf{v}_{S}\|_{2}\,.$

Hence as soon as we assume $s\epsilon_{n}$ is bounded or goes to $0$ we are
good.

###  D.5 Proof of Theorem D.10

We follow the proof of Theorem 1 in [31] and extend and modify the results to
allow for network dependency. Notice that we assume both source and target
domains share the same ER graph probability, denoted as $p$.

Step 1:

Step 1 aims to solve the following equation w.r.t.
${\bm{\beta}}\in\mathbb{R}^{d}$ :

$\sum_{k\in\\{0,\mathcal{A}\\}}\left[\left(\bm{\mathbf{Z}}^{(k)}\right)^{T}\bm{\mathbf{Y}}^{(k)}-\sum_{i=1}^{n_{k}}\psi^{\prime}\left({\bm{\beta}}^{T}\bm{\mathbf{Z}}_{i}^{(k)}\right)\bm{\mathbf{Z}}_{i}^{(k)}\right]=\mathbf{0}_{p}$

converging to its population version’s solution under certain conditions with
$\alpha_{k}=\frac{n_{k}}{n_{\mathcal{A}}+n_{0}}$:

$\sum_{k\in\\{0,\mathcal{A}\\}}\alpha_{k}\mathbb{E}\left\\{\left[\psi^{\prime}\left(\left({\bm{\beta}}^{\mathcal{A}}\right)^{T}\mathbf{Z}^{(k)}\right)-\psi^{\prime}\left(\left({\bm{\beta}}^{(k)}\right)^{T}{\mathbf{Z}}^{(k)}\right)\right]\bm{\mathbf{Z}}^{(k)}\right\\}=\mathbf{0}_{p}$
(D.1)

As we define before,
$\hat{\bm{u}}^{\mathcal{A}}=\hat{\bm{\beta}}^{\mathcal{A}}-{\bm{\beta}}^{\mathcal{A}}$
and
$\mathcal{D}=\left\\{\left(\bm{\mathbf{Z}}^{(k)},\mathbf{Y}^{(k)}\right)\right\\}_{k\in\\{0,\mathcal{A}\\}}$.
Firstly, we claim that when $\lambda_{{{\bm{\beta}}}}\geq 2\left\|\nabla
L\left({\bm{\beta}}^{\mathcal{A}},\mathcal{D}\right)\right\|_{\infty}$, it
holds that with probability of at least $1-({\sf
exp}{\left(\frac{1}{2}\log{d}+1-c_{4}\log^{2}{d}\Psi(p)\right)}+2{\sf
exp}{\left(1-(c_{1}-3/2)\log{d}\right)}+2{\sf
exp}{\left(\frac{3}{2}\log{d}+1-c_{2}n\right)})$ that

$\left\|\hat{{\bm{u}}}^{\mathcal{A}}\right\|_{2}\leq
8\frac{C_{4}}{\kappa_{l}}C_{l}h\log{d}\sqrt{\frac{\Psi(p)}{n_{\mathcal{A}}+n_{0}}}+3\frac{\sqrt{s}}{\kappa_{1}}\lambda_{{\omega}}+2\sqrt{\frac{C_{l}}{\kappa_{1}}h\lambda_{{\omega}}}$
(D.2)

According to the definition of $\hat{{\omega}}^{\mathcal{A}}$, Hölder
inequality and Lemma 1, we will have

$\displaystyle\delta\hat{L}\left(\hat{{\bm{u}}}^{\mathcal{A}},\mathcal{D}\right)$
$\displaystyle\leq\lambda_{{{\bm{\beta}}}}\left(\left\|{\bm{\beta}}_{S}^{\mathcal{A}}\right\|_{1}+\left\|{\bm{\beta}}_{S^{c}}^{\mathcal{A}}\right\|_{1}\right)-\lambda_{{{\bm{\beta}}}}\left(\left\|\hat{{\bm{\beta}}}_{S}^{\mathcal{A}}\right\|_{1}+\left\|\hat{{\bm{\beta}}}_{S^{c}}^{\mathcal{A}}\right\|_{1}\right)+\nabla\hat{L}({\bm{\beta}}^{\mathcal{A}},\mathcal{D})^{T}\hat{{\bm{u}}}^{\mathcal{A}}$