\section{Main Theoretical Results}
	

	
	Theorems 1 and 2 state our major results about the GNN model  for regression  and binary classification, respectively. Before formally presenting the results, we first summarize the key findings as follows. 
	
	\textbf{1. Zero generalization error of the learned model.} Algorithm ~\ref{Alg} can return $\bfW^*$ exactly for   regression (see \eqref{eqn: linear_convergence_lr})   and approximately for binary classification (see \eqref{eqn: linear_convergence2_cl}). 
	Specifically, since $\bfW^*$ is {often} not  a solution to \eqref{eqn: classification}, 
	Algorithm~\ref{Alg} returns a critical point $\widehat{\bfW}$ that is sufficiently close to $\bfW^*$, and the distance decreases with respect to the number of samples in the order of $\sqrt{1/|\Omega|}$. 
	Thus, with a sufficient number of samples, $\widehat{\bfW}$ {will be close to $\bfW^*$ and}  achieves a zero generalization error approximately for binary classification.  Algorithm~\ref{Alg} always returns $\bfW^*$ exactly for   regression, a zero \textcolor{black}{generalization} error is thus achieved.
	
	


\textbf{2. 	Fast linear convergence of  Algorithm~\ref{Alg}.}  Algorithm~\ref{Alg} is proved to converge linearly to $\bfW^*$ for regression and $\widehat{\bfW}$ for classification, as shown in \eqref{eqn: linear_convergence_lr} and \eqref{eqn:converge2}. That means the distance of the estimate during the iterations to $\bfW^*$ (or $\widehat{\bfW}$) decays exponentially. Moreover,  Algorithm~\ref{Alg} converges faster than the vanilla GD. The rate of convergence is $1-\Theta\big(\frac{1}{\sqrt{K}}\big)$
for regression
\footnote{$f(d)=O(g(d))$ means that if for some constant $C>0$,  $f(d)\leq Cg(d)$ holds when $d$ is sufficiently large.   $f(d)=\Theta(g(d))$ means that   for some constants $c>0$ and $C>0$,  $cg(d)\leq f(d)\leq Cg(d)$ holds when $d$ is sufficiently large.}
and $1-\Theta\big(\frac{1}{K}\big)$ for classification, where $K$ is the number of filters in the hidden layer. In comparison, the convergence rates of GD are $1-\Theta\big(\frac{1}{K}\big)$ and $1-\Theta\big(\frac{1}{K^2}\big)$, respectively. Note that a smaller value of the rate of convergence corresponds to faster convergence. 
 We remark that this is the first theoretical guarantee of  AGD methods for learning GNNs. 

 
	
	
\textbf{3. Sample complexity analysis.} $\bfW^*$ can be estimated exactly for regression and approximately for classification, provided that the number of  samples is in the order of $(1+\delta^2) \textrm{poly}(\sigma_1(\bfA), K) d\log N\log(1/\varepsilon)$, as shown in \eqref{eqn: sample_complexity_lr} and \eqref{eqn: sample_complexity_cl}, where $\varepsilon$ is the desired estimation error tolerance. $\bfW^*$ has $Kd$ parameters,  where $K$ is the number of nodes in the hidden layer, and $d$ is the feature dimension.  Our sample complexity is order-wise optimal with respect to $d$  and  only logarithmic with respect to the total number of features $N$. 

{We further show that} the sample complexity is also positively   associated  with $\sigma_1(\bfA)$ and $\delta$.  That characterizes the relationship between the sample complexity and graph structural properties.  From Lemma \ref{Lemma: sigma_1}, we know that given $\delta$, $\sigma_1(\bfA)$ is positively correlated with the average node degree $\delta_{\text{ave}}$. Thus, the required number of samples increases when the maximum and average degrees of the graph increase. That coincides with the intuition that more edges in the graph corresponds to the stronger dependence of the labels on neighboring features, {thus requiring} more samples to learn these dependencies. Our sample complexity quantifies this intuition explicitly. 
 
Note that the graph structure affects this bound only through $\sigma_1(\bfA)$ and $\delta$. Different graph structures may require a similar number of samples to estimate $\bfW^*$, as long as they have similar $\sigma_1(\bfA)$ and $\delta$. We will verify this property on different graphs numerically in Figure~\ref{Figure: N_vs_graph}.
  
        \begin{lemma}\label{Lemma: sigma_1}
 	Give an un-directed graph $\mathcal{G}=\{\mathcal{V}, \mathcal{E} \}$ and the   normalized adjacency matrix $\bfA$ as defined in Section \ref{Section: pf_1}, 
 	the largest singular value $\sigma_1(\bfA)$ of $\bfA$ satisfies
		\begin{equation}
			\frac{ 1+\delta_{\textrm{ave}} }{1+ \delta_{\max} } \le \sigma_1(\bfA)\le 1, 
		\end{equation}
 		where $\delta_{\text{ave}}$ and $\delta$ are the average and maximum node degree, respectively. 
 		
	\end{lemma}
	
 
 \subsection{Formal theoretical guarantees}\label{sec:theorem}
	To formally present the results, some parameters in the results are defined as follows. $\sigma_j(\bfW^*)$ ($j\in [N]$) is the $j$-th singular value of $\bfW^*$. $\kappa=\sigma_1(\bfW^*)/\sigma_K(\bfW^*)$ is the conditional number of $\bfW^*$. 
	$\gamma$ is defined as $\prod_{j=1}^K\sigma_j(\bfW^*)/\sigma_K(\bfW^*)$. For a fixed $\bfW^*$, both $\gamma$ and $\kappa$ can be viewed as constants and do not affect the order-wise analysis.


 
	\begin{theorem}\label{Thm: major_thm_lr}
		(Regression) Let $\{ \bfW^{(t)} \}_{t=1}^T$ be the sequence generated by  Algorithm \ref{Alg} to solve \eqref{eqn:linear_regression} with $\eta= {K}/{(8\sigma_1^2(\bfA))}$. 
		Suppose the number of samples satisfies 
		\begin{equation}\label{eqn: sample_complexity_lr}
			|\Omega|\ge C_1\varepsilon_0^{-2} \kappa^9\gamma^2 { (1+\delta^2)\sigma_1^4(\bfA)} K^8 d\log N \log(1/\varepsilon)
		\end{equation} 
		for some constants $C_1>0$ and $\varepsilon_0\in(0,\frac{1}{2})$. Then $\{ \bfW^{(t)} \}_{t=1}^{T}$ converges linearly to $\bfW^*$ with probability at least $\textcolor{black}{1-K^2T}\cdot N^{-10}$ as  
		\begin{equation}\label{eqn: linear_convergence_lr}
		\begin{gathered}
		\|	\W[t]-\bfW^*\|_2
		\le\nu(\beta)^t\|	\W[0]-\bfW^*\|_2, and\\
		\|	\W[T]-\bfW^*\|_2
		\le \varepsilon \|\bfW^* \|_2 
		
		\end{gathered}
		\end{equation}


		where $\nu(\beta)$ is the  rate of convergence that depends on $\beta$.
		Moreover, we have
		\begin{equation}\label{eqn: accelerated_rate_lr}
		\nu(\beta)< \nu(0) \text{\quad for some small nonzero } \beta.
		\end{equation} 
		Specifically, let $\beta^* = \Big(1-\sqrt{\frac{1-\varepsilon_0}{88\kappa^2 \gamma }}\Big)^2$, we have
		\begin{equation}\label{eqn:rate}
		\begin{gathered}
		 \nu(0)\ge 1-\frac{1-\varepsilon_0}{{88\kappa^2 \gamma K}},
		\nu(\beta^*)= 1-\frac{1-\varepsilon_0}{\sqrt{88\kappa^2 \gamma  K}}.	
		\end{gathered}
		\end{equation}
	\end{theorem}
 
 
	\begin{theorem}\label{Thm: major_thm_cl}
	(Classification)	Let $\{ \bfW^{(t)} \}_{t=1}^T$ be the sequence generated by Algorithm \ref{Alg} to solve \eqref{eqn: classification} with $\eta= {1}/{(2\sigma_1^2(\bfA))}$. 
		Suppose the number of samples satisfies 
		\begin{equation}\label{eqn: sample_complexity_cl}
		|\Omega|\ge C_2\varepsilon_0^{-2}(1+\delta^2)\kappa^8\gamma^2 \sigma_1^4(\bfA)K^8d\log N \log(1/\varepsilon)
		\end{equation} 
		for some positive constants $C_2$ and $\varepsilon_0\in(0,1)$. Then, let $\widehat{\bfW}$ be the nearest critical point of  \eqref{eqn: classification} to $\bfW^*$, we have that $\{ \bfW^{(t)} \}_{t=1}^{T}$ converges linearly to $\widehat{\bfW}$ with probability at least \textcolor{black}{$1-K^2T\cdot N^{-10}$} as  
		\begin{equation}\label{eqn:converge2}
		\begin{gathered}
		\|\bfW^{(t)} -\widehat{\bfW} \|_2 \le \nu(\beta)^t\|\bfW^{(0)} -\widehat{\bfW}\|_2, \textrm{ and }\\
		\|\bfW^{(T)} -\widehat{\bfW} \|_2 \le \varepsilon\|\bfW^{(0)} -\widehat{\bfW}\|_2.
		\end{gathered}
		\end{equation}
		The distance between $\widehat{\bfW}$ and $\bfW^*$ is bounded by
		\begin{equation} \label{eqn: linear_convergence2_cl}
		\| \widehat{\bfW} -\bfW^*  \|_2 \le C_3(1-\varepsilon_0)^{-1}\kappa^2 \gamma K \sqrt{\frac{(1+\delta^2)d\log N}{|\Omega|}},
		\end{equation}


		where $\nu(\beta)$ is the rate of convergence   that depends on $\beta$, and $C_3$ is some positive constant.
		Moreover, we have
		\begin{equation}\label{eqn: accelerated_rate_cl}
		\nu(\beta)< \nu(0) \text{\quad for some small nonzero } \beta,
		\end{equation} 
		Specifically, let $\beta^* = \Big(1-\sqrt{\frac{1-\varepsilon_0}{11\kappa^2\gamma K^2}}\Big)^2$, we have
		\begin{equation}\label{eqn: accelerated_rate1_cl}
		\begin{gathered}
		\nu(0)= 1-\frac{1-\varepsilon_0}{11\kappa^2\gamma K^2},
		\nu(\beta^*)= 1-\sqrt{\frac{1-\varepsilon_0}{11\kappa^2\gamma K^2}}.	
		\end{gathered}
		\end{equation}
	\end{theorem}

 
\subsection{Comparison with existing works}
 
Only \cite{VZ19,DHPSWX19} analyze the generalization error of one-hidden-layer GNNs in regression problems, while there is no existing work about the generalization error in classification problems. \cite{VZ19,DHPSWX19} show that the difference between the risks in the testing data and the training data
decreases in the order of $1/\sqrt{|\Omega|}$ as the sample size increases.  The GNN model in \cite{VZ19} only has one filter in the hidden layer, i.e., $K=1$, and the loss function is required to be a smooth function, excluding ReLU. Ref.~\cite{DHPSWX19} only considers infinitely wide GNNs.  In contrast, $\bfW^*$  returned by Algorithm\ref{Alg} can achieve zero risks for both training data and testing data in regression problems. Our results apply to an arbitrary number of filters and the ReLU activation function. 
 Moreover, this paper is the first work that characterizes the \textcolor{black}{generalization} error of GNNs for binary classification. 

 

When $\delta$ is zero, our model reduces to one-hidden-layer NNs, and the corresponding sample complexity is $O\Big( \textrm{poly}(K) d\log N\log(1/\varepsilon)\Big)$. Our results are at least comparable to, if not better than, the state-of-art theoretical guarantees \textcolor{black}{that from the prespective of model estimation} for NNs. 
For example, \cite{ZSJB17} considers   one-hidden-layer NNs for regression  and proves the linear convergence of their algorithm to the ground-truth model parameters. The sample complexity of ~\cite{ZSJB17} is also linear in  $d$, but the activation function must be smooth. \cite{ZYWG18} considers one-hidden-layer 
NNs with the ReLU  activation function for regression, but the algorithm cannot converge to the ground-truth parameters exactly but up to a statistical error.  Our result in Theorem \ref{Thm: major_thm_lr} applies to the nonsmooth ReLU function and can recover $\bfW^*$ exactly.
   \cite{FCL19} considers   one-hidden-layer NNs for classification and proves linear convergence of their algorithm to a critical point sufficiently close to   $\bfW^*$ with the distance bounded by   $O(\sqrt{1/|\Omega|})$. The convergence rate in \cite{FCL19} is $1-\Theta({1}/{K^2})$, while Algorithm~\ref{Alg} has a faster convergence   rate of $1-\Theta({1}/{K})$.
{"config": "arxiv", "file": "2006.14117/Theorem_MW.tex"}