Decouple Graph Neural Networks: Train Multiple Simple GNNs
  Simultaneously Instead of One
Graph neural networks (GNN) suffer from severe inefficiency. It is mainly
caused by the exponential growth of node dependency with the increase of
layers. It extremely limits the application of stochastic optimization
algorithms so that the training of GNN is usually time-consuming. To address
this problem, we propose to decouple a multi-layer GNN as multiple simple
modules for more efficient training, which is comprised of classical forward
training (FT)and designed backward training (BT). Under the proposed framework,
each module can be trained efficiently in FT by stochastic algorithms without
distortion of graph information owing to its simplicity. To avoid the only
unidirectional information delivery of FT and sufficiently train shallow
modules with the deeper ones, we develop a backward training mechanism that
makes the former modules perceive the latter modules. The backward training
introduces the reversed information delivery into the decoupled modules as well
as the forward information delivery. To investigate how the decoupling and
greedy training affect the representational capacity, we theoretically prove
that the error produced by linear modules will not accumulate on unsupervised
tasks in most cases. The theoretical and experimental results show that the
proposed framework is highly efficient with reasonable performance.
Hongyuan Zhang, Yanan Zhu, Xuelong Li
# Decouple Graph Neural Networks: Train Multiple Simple GNNs Simultaneously Instead of One

###### Abstract

Graph neural networks (GNN) suffer from severe inefficiency due to the exponential growth of node dependency with the increase of layers. It extremely limits the application of stochastic optimization algorithms so that the training of GNN is usually time-consuming. To address this problem, we propose to decouple a multi-layer GNN as multiple simple modules for more efficient training, which is comprised of classical _forward training_ (_FT_) and designed _backward training_ (_BT_). Under the proposed framework, each module can be trained efficiently in FT by stochastic algorithms without distortion of graph information owing to its simplicity. To avoid the only unidirectional information delivery of FT and sufficiently train shallow modules with the deeper ones, we develop a backward training mechanism that makes the former modules perceive the latter modules, inspired by the classical backward propagation algorithm. The backward training introduces the reversed information delivery into the decoupled modules as well as the forward information delivery. To investigate how the decoupling and greedy training affect the representational capacity, we theoretically prove that the error produced by linear modules will not accumulate on unsupervised tasks in most cases. The theoretical and experimental results show that the proposed framework is highly efficient with reasonable performance, which may deserve more investigation.

## 1 Introduction

In recent years, neural networks [1; 2], due to the impressive performance, have been extended to graph data, known as graph neural networks (GNN) [3]. As GNNs significantly improve the results of graph tasks, it has been extensively investigated from different aspects, such as graph convolution network (GCN) [4; 5], graph attention networks (GAT) [6; 7], spatial-temporal GNN (STGNN) [8], graph auto-encoder [9; 10], graph contrastive learning [11], _etc_.

Except for the variants that originate from different perspectives, an important topic is motivated by the well-known inefficiency of GNN. In classical neural networks [2], the optimization is usually based on stochastic algorithms with limited batch [12; 13] since samples are independent of each other. However, the aggregation-like operations defined in [14] result in the dependency of each node on its neighbors and the amount of dependent nodes for one node increases exponentially with the growth of layers, which results in the unexpected increases of batch size. Some works are proposed based on neighbor sampling [14; 15; 16; 17] and graph approximation [18] to limit the batch size, while some methods [19; 20] attempt to directly apply high-order graph operation and sacrifice the most non-linearity. The training stability is a problem for neighbor sampling methods [14; 15; 17] though VRGCN [16] has attempted to control the variance via improving sampling. Note that the required nodes may still grow (slowly) with the increase of depth. ClusterGCN [18] finds an approximate
graph with plenty of connected components so that the batch size is strictly upper-bounded. The major challenge of these methods is the information missing during sampling. The simplified methods [19; 20] are efficient but the limited non-linearity may be the bottleneck of these methods. These methods may incorporate the idea of GIN [21] to improve the capacity [20].

To apply stochastic optimization while retaining the exact graph structure, we propose a framework, namely stacked graph neural network (SGNN), which decouples a multi-layer GNN as multiple simple GNN modules and then trains them simultaneously rather than connecting them with the increase of the depth. Inspired by the backward propagation algorithm, we find that the main difference between stacked networks [22] and classical networks is _no training information propagated from the latter modules to the former ones_. The lack of backward information delivery may be the main reason of the performance limitation of stacked models. The contributions are concluded as: **(1)** We accordingly propose a backward training strategy to let the former modules receive the information from the final loss and latter modules, which leads to a cycled training framework to control bias and train shallow modules correctly. **(2)** Under this framework, a multi-layer GNN can be decoupled into multiple simple GNNs, named as separable GNNs in this paper, so that every training step could use the stochastic optimization without any samplings or changes on graph. Therefore, SGNN could take both non-linearity and high efficiency into account. **(3)** We investigate how the decoupling and greedy training affect the representational capacity of the linear SGNN. It is proved that the error would not accumulate in most cases when the final objective is graph reconstruction.

## 2 Background

**Graph Neural Networks** Aiming to extend convolution operation into graph, graph convolution became a hot topic [5; 23; 24] and graph convolution network (GCN) [4] has become an important baseline. By introducing self-attention techniques [25], graph attention networks (GAT) [6; 7] are proposed and applied to other applications [26; 27]. As [28] claimed that GNNs suffer from the over-smoothing problem, GALA [10] develops the graph sharpening and ResGCN [29] attempts to designs a deeper architecture. The theoretical works [28; 30; 31] have different views towards the depth of GNNs. Some works [28; 30] claimed that the expressive power of GNN decreases with the increase of layers, while the others argue that the assumptions in [30] may not hold and deeper GNNs have stronger power [31]. Moreover, some works [32; 21] investigate the expressive capability by showing the connection between Weisfeiler-Lehman test [33] and GNNs. Nevertheless, _most of them neglect the inefficiency problem of GNNs_.

Figure 1: Illustration of a stacked graph neural network decoupled from an \(L\)-layer GNN. To train each module individually, some loss (_e.g._, semi-supervised loss, unsupervised loss, contrastive loss) is required and it is denoted by \(\mathcal{L}_{FT}^{(t)}\). To let the shallow modules perceive the deeper ones, \(\mathcal{M}_{t}\) passes back the _expected_ input features to \(\mathcal{M}_{t-1}\) during the backward training. The divergence between the features output by \(\mathcal{M}_{t}\) and the expected features of \(\mathcal{M}_{t-1}\) formulates the BT loss \(\mathcal{L}_{BT}^{(t)}\).
**Efficient Graph Neural Networks** To accelerate the optimization through batch gradient descent to GNN without too much deviation, several models [14; 15; 16; 17] propose to sample data points according to graph topology. These models propose different sampling strategies to obtain stable results. GraphSAGE [14] produces a subgraph with limited neighbors for each node while FastGCN [15] samples fixed nodes for each layer with the importance sampling. The variance of sampling is further controlled in [16]. ClusterGCN [18] aims to generate an approximate graph with plenty of connected components so that each component can be used as a batch per step. SGC [19] simplifies GCN by setting all activations of middle layers as linear functions and SSGC [20] further improves it. In summary, _SGNN proposed in this paper retains the non-linearity and requires no node sampling or sub-graph sampling._ L2-GCN [34] attempts to extend the idea of the classical stacked auto-encoder into the popular GCN while DGL-GNN [35] further develops a parallel version. They both fail to train all GNN modules jointly but _SGNN firstly offers a novel framework to train them like training layers in a conventional neural network._

**Connections to Existing Models** Stacked Auto-Encoder (_SAE_) [22] is a model applied to the pre-training of neural networks. It trains the current two-layer auto-encoder [36] and then feeds the latent features output by the middle layer to the next auto-encoder. The model is often used as a pre-training model instead of a formal model. MGAE [37] is an extension of SAE and its fundamental module is graph auto-encoder [9]. The main difference compared with the proposed model is whether each module could be perceived by modules from both forward and backward directions. The stack paradigm is similar to the classical boosting models [38; 39; 40] while some works [41; 42] also investigated the boosting algorithm of neural networks. In recent years, some boosting GNN models [43; 44] are also developed. The most boosting algorithms (_e.g._, [41; 43]) aim to learn a prediction function gradually while the proposed SGNN aims to learn ideal embeddings gradually. Note that AdaGCN [44] is also trained gradually and the features are combined using AdaBoost [38]. More importantly, _all these boosting methods for GNNs are only trained forward and the backward training is missing_. Deep neural interface [45] proposes to decouple neural networks to asynchronously accelerate the computation of gradients. _The decoupling is an acceleration trick to compute the gradients of \(L\)-layer networks_, while SGNN proposed in this paper explicitly separates an \(L\)-layer GNN into \(L\) simple modules. In other words, _the ultimate goal of SGNN is not to optimize an \(L\)-layer GNN_.

## 3 Proposed Method

Motivated by SAE [22] and the fact that the simplified models [19; 20] are highly efficient for GNN, we therefore rethink the substantial difference between the stacked networks and multi-layer GNNs. To sum up, we attempt to answer the following two questions in this paper:

* _How to decouple a complex GNN into multiple simple GNNs and train them jointly?_
* _How does the decoupling affect the representational capacity and final performance?_

We will discuss the first question in this section and then elaborate on another one in Section 4.

### Preliminary

Each decoupled GNN model of the proposed model is named as a module and the \(t\)-th module is denoted by \(\mathcal{M}_{t}\) for simplicity. The vector and matrix are denoted by lower-case and upper-case letters in bold, respectively. \(\|\cdot\|\) represents the Frobenius norm. Given a graph, let \(\mathbf{A}\in\mathbb{R}^{n\times n}\) be adjacency matrix and \(\mathbf{X}\in\mathbb{R}^{n\times d}\) be node features. A typical GNN layer can be usually defined as

\[\mathbf{H}=f(\mathbf{A},\mathbf{X},\mathbf{W})=\varphi(\mathbf{P}\mathbf{X}\mathbf{W}), \tag{1}\]

where \(\mathbf{W}\) is projection coefficient and \(\mathbf{P}=\phi(\mathbf{A})\) is a function of \(\mathbf{A}\). When we discuss each individual module, we assume that \(\mathbf{W}\in\mathbb{R}^{d\times k}\) for simplicity. For example, GCN [4] defines \(\mathbf{P}\) as \(\mathbf{P}_{\rm GCN}=\mathbf{D}^{-\frac{1}{2}}(\mathbf{A}+\mathbf{I})\mathbf{D}^{-\frac{1}{2}}\) and \(\mathbf{D}\) is the degree matrix of \(\mathbf{A}+\mathbf{I}\). When multiple layers are integrated, the learned representation given by multiple GNN layers can be written as

\[\begin{split}\mathbf{H}&=f_{1}\circ f_{2}\circ\cdots \circ f_{L}(\mathbf{A},\mathbf{X},\mathbf{W}_{1},\ldots,\mathbf{W}_{L})\\ &=\varphi_{L}(\mathbf{P}\varphi_{L-1}(\cdots\varphi_{1}(\mathbf{P}\mathbf{X} \mathbf{W}_{1})\cdots)\mathbf{W}_{L}),\end{split} \tag{2}\]
where \(L\) is the amount of layers. Assume that the average number of neighbors is \(c\). To compute \(\mathbf{H}\), each sample will need \(\mathcal{O}(c^{L})\) extra samples. If the depth is large and the graph is connected, then all nodes have to be engaged to compute for one node. The uncontrolled batch size results in the time-consuming training. In vanilla GNNs, the computational complexity is \(\mathcal{O}(KL\|\mathbf{A}\|_{0}\sum_{i=0}^{m-1}d_{i}d_{i+1})\) on sparse graphs where \(K\) is the number of iterations and \(d_{i}\) is the dimension of \(\mathbf{W}_{i}\). For large-scale datasets, both time and space complexity are too expensive.

### Stacked Graph Neural Networks

Although the stacked networks usually have more parameters than multi-layer networks, which frequently indicates that the stacked networks may be more powerful, they only serve as a technique for pre-training. Specifically speaking, they simply transfer the representations learned by the current network to the next one but _no feedback is passed back_. It causes the invisibility of the succeeding modules and the final objective. As a result of the unreliability of the former modules, the stacked model is conventionally used as an unsupervised pre-training model.

Rethinking the learning process of a network, multiple layers are optimized simultaneously by gradient-based methods where the gradient is calculated by the well-known backward propagation algorithm [46]. The algorithm consists of forward propagation (FP) and backward propagation (BP). FP computes the required values for BP, which can be viewed as an information delivery process. Note that FP is similar to the training of the stacked networks. Specifically, transferring the output of the current module to the next one in the stacked network is like the computation of neurons layer by layer during FP. Inspired by this, we aim to design a BP-like training strategy, namely _backward training (BT)_, so that the former modules could be tuned according to the feedback. The core idea of our stacked graph neural network (SGNN) is shown in Figure 1.

#### 3.2.1 Separability: Crucial Concept for Efficiency

Before introducing SGNN in detail, we formally introduce the key concept and core motivation of how to accelerate GNN via SGNN.

**Definition 3.1**.: _If a GNN model can be formulated as \(f(\mathbf{A},\mathbf{X},\mathbf{W})=f_{1}(f_{0}(\mathbf{A},\mathbf{X}),\mathbf{W})\), then it is a separable GNN. If it can be further formulated as \(f(\mathbf{A},\mathbf{X},\mathbf{W})=f_{1}(f_{0}(\mathbf{A},\mathbf{X}),\mathbf{W})=g_{1}(\mathbf{A},g_{0}( \mathbf{X},\mathbf{W}))\), then it is a fully-separable GNN._

To keep simplicity, define the set of separable GNNs as \(\mathcal{F}_{k}=\{f:\mathbb{R}^{n\times n}\times\mathbb{R}^{n\times d}\times \mathbb{R}^{d\times k}\mapsto\mathbb{R}^{n\times k}|f(\mathbf{A},\mathbf{X},\mathbf{W})=f_ {1}(f_{0}(\mathbf{A},\mathbf{X}),\mathbf{W})\}\) and the set of fully-separable GNNs as \(\mathcal{F}_{k}^{*}=\{f:\mathbb{R}^{n\times n}\times\mathbb{R}^{n\times d} \times\mathbb{R}^{d\times k}\mapsto\mathbb{R}|f(\mathbf{A},\mathbf{X},\mathbf{W})=f_{1}(f_ {0}(\mathbf{A},\mathbf{X}),\mathbf{W})=g_{1}(\mathbf{A},g_{0}(\mathbf{X},\mathbf{W}))\}\). Note that most single-layer GNN models are fully-separable. For instance, SGC [19] is fully-separable where \(f_{0}(\mathbf{A},\mathbf{X})=\mathbf{P}^{m}\mathbf{X}\) and \(f_{1}(f_{0}(\mathbf{A},\mathbf{X}),\mathbf{W})=\varphi(f_{0}(\mathbf{A},\mathbf{X})\cdot\mathbf{W})\), while the single-layer GIN [3] is separable but not fully-separable since \(\mathbf{P}\cdot\mathrm{MLP}(\mathbf{X})\neq\mathrm{MLP}(\mathbf{P}\mathbf{X})\) usually holds. However, a single-layer GAT [6] is not separable since the graph operation is relevant to \(\mathbf{W}\).

_The separable property actually factorizes a GNN model to 2 parts, graph operation \(f_{0}\) and neural operation \(f_{1}\)._ Since all dependencies among nodes in GNNs are caused by the graph operation, one can compute \(\mathbf{X}^{\prime}=f_{0}(\mathbf{A},\mathbf{X})\) once (like **preprocessing**) in separable GNNs and then the GNN is converted into a typical network. After computing \(\mathbf{X}^{\prime}\), the information contained in graph has been passed into \(\mathbf{X}^{\prime}\) and the succeeding sampling would not affect the topology of graph. Therefore, we can obtain a highly efficient GNN model that can be optimized by SGD, provided that each module is separable. On the other hand, _the fully-separable condition is essential for the backward training to pass back the information over multiple modules_. Since most single-layer GNNs are separable but not fully-separable, we show how to revise separable GNNs to **introduce the fully-separability**.

Then, we formally clarify the core idea of SGNN by showing how to handle \(\mathbf{Q}\mathbf{I}\).

#### 3.2.2 Forward Training (FT)

_The first challenge_ is how to set the training objective for each module \(\mathcal{M}_{t}\). It is crucial to apply SGNN to both supervised and unsupervised scenes. Suppose that we have a separable GNN module \(\mathcal{M}\) and let \(\mathbf{H}=f(\mathbf{A},\mathbf{X},\mathbf{W})\) be the features learned by the separable GNN module. For the
unsupervised cases, if \(\mathcal{M}_{t}\) is a GAE, then the loss of FT is formulated as

\[\mathcal{L}_{FT}=\ell(\mathbf{A},\mathbf{X},\mathbf{H})=d(\mathbf{A},\kappa(\mathbf{H})), \tag{3}\]

where \(d(\cdot,\cdot)\) represents the metric function and \(\kappa:\mathbb{R}^{n\times k}\mapsto\mathbb{R}^{n\times n}\) is a mapping function. For instance, a simple loss introduced by [9] is \(d(\mathbf{A},\kappa(H))=KL(\mathbf{A}\|\sigma(\mathbf{H}\mathbf{H}^{T}))\) where \(\sigma(\cdot)\) is the sigmoid function, and \(KL(\cdot\|\cdot)\) is the Kullback-Leibler divergence. The other options include but not limited to symmetric content reconstruction [10] and graph contrastive learning [11]. For modules with supervision information, a projection matrix \(\mathbf{R}\in\mathbb{R}^{k\times c}\) is introduced to map the \(k\)-dimension embedding vector into soft labels with \(c\) classes. For the node classification, the loss can be simply set as

\[\mathcal{L}_{FT}=KL(\mathbf{Y}\|\text{softmax}(\mathbf{H}\mathbf{R})), \tag{4}\]

where \(\mathbf{Y}\in\mathbb{R}^{n\times c}\) is the supervision information for supervised tasks. Note that the above loss is equivalent to the classical softmax regression if \(\mathbf{H}\) is constant. The loss could also be link prediction, graph classification, _etc_. Although base modules can utilize diverse losses, we only discuss the situation that all modules use the same kind of loss in this paper for simplicity.

```
Input : Adjacency matrix \(\mathbf{A}\), feature matrix \(\mathbf{X}\), balance coefficient \(\eta\), the number of epochs \(K\), \(L\) separable GNN modules \(\{\mathcal{M}_{t}\}_{t=1}^{L}\), \(\mathbf{H}_{0}\leftarrow\mathbf{X}\). Output : Features output by \(\mathcal{M}_{L}\). for\(i=1,\ldots,K\)do  # Forward Train Stacked Graph Neural Networks for\(t=1,2,\ldots,L-1\)do  Feed the current features to \(\mathcal{M}_{t}\) and reset \(\mathbf{U}_{t}\): \(\mathbf{X}_{t}\leftarrow\mathbf{H}_{t-1}\), \(\mathbf{U}_{t}\leftarrow\mathbf{I}\).  if Train with only \(\mathcal{L}_{FT}\) at the first forward training \(\mathbf{X_{t}}^{\prime}=f_{0}^{(t)}(\mathbf{A},\mathbf{X}_{t})\)  # Preprocessing for mini-batch algorithms  Compute loss \(\mathcal{L}^{(t)}\leftarrow\mathcal{L}_{FT}^{(t)}\) if \(i==1\) else \(\mathcal{L}_{FT}^{(t)}+\eta\mathcal{L}_{BT}^{(t)}\)  Train \(\mathcal{M}_{t}\) by optimizing \(\min_{\mathbf{W}_{t}}\mathcal{L}^{(t)}\) based on mini-batch algorithms.  Obtain the features: \(\mathbf{H}_{t}\gets f_{1}^{(t)}(\mathbf{X_{t}}^{\prime},\mathbf{W}_{t})\). \(\mathbf{X}_{L}\leftarrow\mathbf{H}_{t}\), \(\mathbf{U}_{L}\leftarrow\mathbf{I}\), \(\mathbf{X}_{L}^{\prime}=f_{0}^{(L)}(\mathbf{A},X_{L})\).  Train \(\mathcal{M}_{L}\) by optimizing \(\min_{\mathbf{W}_{L},\mathbf{U}_{L}}\mathcal{L}_{FT}^{(L)}\) based on mini-batch algorithms. # Backward Train Stacked Graph Neural Networks for\(t=L-1,L-2,\ldots,1\)do  Compute the expected output feature of \(\mathcal{M}_{t}\): \(\mathbf{Z}_{t+1}\leftarrow(g_{0}^{*})_{t+1}(\mathbf{X}_{t+1},\mathbf{U}_{t+1})\).  Train \(\mathcal{M}_{t}\) by optimizing \(\min_{\mathbf{W}_{t},\mathbf{U}_{t}}\mathcal{L}_{FT}^{(t)}+\eta\mathcal{L}_{BT}^{(t)}\) based on mini-batch algorithms.
```

**Algorithm 1**Procedure of Stacked Graph Neural Networks Composed of \(L\) Modules

#### 3.2.3 Backward Training (BT)

_The second challenge_ is how to train multiple separable GNNs simultaneously in order to ensure performance. Roughly speaking, the gradients of all layers in neural networks are computed exactly due to the repeated delivery of information by FP and BP. _BP lets the shallow layers perceive the deep ones through the feedback, while the tail modules are invisible to the head ones in FT_. We accordingly design the backward training (**BT**) for SGNN. To achieve the reverse information delivery, a separable GNN layer is modified by **introducing the fully-separability**,

\[\begin{split}\mathbf{H}&=\hat{f}(\mathbf{A},\mathbf{X},\mathbf{W})= \hat{f}_{1}(\hat{f}_{0}(\mathbf{A},\mathbf{X}),\mathbf{W})\\ &=\hat{f}_{1}(f^{*}(\mathbf{A},\mathbf{X},\mathbf{U}),\mathbf{W}),\;\forall\hat{f} \in\mathcal{F}_{k},f^{*}\in\mathcal{F}_{d}^{*},\end{split} \tag{5}\]

where \(\mathbf{U}\in\mathbb{R}^{d\times d}\) and \(\mathbf{W}\in\mathbb{R}^{d\times k}\). Note that \(f^{*}(\mathbf{A},\mathbf{X},\mathbf{U})=g_{1}^{*}(\mathbf{A},g_{0}^{*}(\mathbf{X},\mathbf{U}))\). Clearly, if \(\mathbf{U}\) is fixed as a constant, then the modified layer is equivalent to the original separable GNN layer \(\hat{f}\). Denote \(\mathbf{Z}=g_{0}^{*}(\mathbf{X},\mathbf{U})\) and \(\mathbf{Z}\) is the _expected features_. Specifically, \(\mathbf{Z}_{t}\) is the learned feature during the backward training of \(\mathcal{M}_{t}\), and it is also the expected input of \(\mathcal{M}_{t}\), _i.e._, from \(\mathcal{M}_{t-1}\). In the forward training, the delivery of information is based on the learned features \(\mathbf{H}_{t}\), and \(\mathbf{Z}\) plays the similar role
in the backward training. The loss of backward training attempts to shrink the difference between the output feature \(\mathbf{H}_{t}\) of \(\mathcal{M}_{t}\) and expected input \(\mathbf{Z}_{t+1}\) of \(\mathcal{M}_{t+1}\),

\[\mathcal{L}_{BT}^{(t)}=d(\mathbf{H}_{t},\mathbf{Z}_{t+1})=d(f_{t}^{*}(\mathbf{A},\mathbf{X}_{t}, \mathbf{U}_{t}),\mathbf{Z}_{t+1}). \tag{6}\]

Note that \(\mathcal{L}_{BT}\) is only activated after the first forward training leading to the final loss of \(\mathcal{M}_{t}\) as

\[\mathcal{L}^{(t)}=\mathcal{L}_{FT}^{(t)}+\eta\mathcal{L}_{BT}^{(t)}, \tag{7}\]

and it is updated during each backward training. The introduction of \(\mathbf{Z}\) will not limit the application of stochastic optimization since the expected features can also be sampled at each iteration without restrictions. The procedure is summarized as Algorithm 1.

Remark that \(\mathbf{U}_{t}\) remains as the identity matrix during FT. This setting leads to each forward computation across \(L\) base modules being equivalent to a forward propagation \(L\)-layer GNN. In other words, an SGNN with \(L\) modules can be regarded as a decomposition of an \(L\)-layer GNN. One may concern that why not to learn \(\mathbf{U}_{t}\) and \(\mathbf{W}_{t}\) together in FT. In this case, we prefer to use \(\mathbf{U}_{t}\) only for learning the expected features of \(\mathcal{M}_{t+1}\) and the capability improvement from the co-learning \(\mathbf{U}_{t}\) in FT could also be implemented by \(\mathbf{W}\), which is equivalent to use GIN [21] as base modules.

### Complexity

As each base module is assumed as a separable GNN, both FT and BT of \(\mathcal{M}_{t}\) can be divided into two steps, the preprocessing step for graph operation and the training step for parameters learning. Denote the output dimension of \(\mathcal{M}_{t}\) as \(d_{t}\) and the dimension of original content feature as \(d_{0}=d\). The preprocessing to compute \(\mathbf{X}_{t}^{\prime}=f_{0}(\mathbf{A},\mathbf{X}_{t})\) requires \(\mathcal{O}(\|\mathbf{A}\|_{0}d_{t})\) cost. Suppose that each module is trained \(E\) iterations and the batch size is set as \(m\). Then the computation cost of the training step is \(\mathcal{O}(Emd_{t-1}d_{t})\). Note that only the GNN mapping is considered and the computation of the loss is ignored. Overall, the computational complexity of an SGNN with \(L\) modules is approximately \(\mathcal{O}(K\|\mathbf{A}\|_{0}\sum_{t=0}^{L-1}d_{t}+Em\sum_{t=1}^{L}d_{t-1}d_{t})\). Remark that the graph is only used once during every epoch and no sampling is processed on the graph such that the graph structure is completely retained which is unavailable in the existing fast GNNs. The coefficient of \(\|\mathbf{A}\|_{0}\) is only \(K\sum_{t=1}^{L-1}d_{t}\). The space complexity is only \(\mathcal{O}(\|\mathbf{A}\|_{0}+md_{t-1}d_{t})\). Therefore, the growth of graph scale will not affect the efficiency of SGNN. Due to the efficiency, all experiments can be conducted on a PC with an NVIDIA 1660 (6GB) and 16GB RAM.

## 4 Theoretical Analysis

To answer _Q2_ raised in the beginning of Section 3, we discuss the impact of the decoupling in this section. Intuitively speaking, if an \(L\)-layer GNN achieves satisfactory results, then there exists \(\{\mathbf{W}_{t}\}_{t=1}^{L}\) such that an SGNN with \(L\) modules could achieve the same results. However, each \(\mathcal{M}_{t}\) is trained greedily according to the forward training loss \(\mathcal{L}_{FT}\), while middle layers of a multi-layer GNN are trained according to the same objective. The major concern is whether the embedding learned by a greedy strategy leads to an irreversible deviation in the forward training.

In this section, we investigate the possible side effects on a specific SGNN comprised of unsupervised modules defined in Eq. (3) with linear activations. The conclusion is not apparent since simply setting \(\mathbf{W}\) as an identity matrix does not prove it for GNN due to the existence of \(\mathbf{P}\). Remark that a basic premise is that the previous module has achieved a reasonable result.

Given a linear separable-GNN module \(\mathcal{M}\) which is defined as \(\mathbf{H}=\mathbf{P}\mathbf{X}\mathbf{W}\in\mathbb{R}^{n\times k}\), suppose that the forward training uses the reconstruction error \(\|\mathbf{P}-\mathbf{H}\mathbf{H}^{T}\|\) as \(\mathcal{L}_{FT}\). We first introduce the matrix angle to better understand whether the preconditions of Theorem 4.1 are practicable.

**Definition 4.1**.: _Given two matrices \(\mathbf{B}_{1},\mathbf{B}_{2}\in\mathbb{R}^{n\times n}\), we define the matrix angle as \(\theta(\mathbf{B}_{1},\mathbf{B}_{2})=\arccos\langle\mathbf{B}_{1},\mathbf{B}_{2}\rangle/(\| \mathbf{B}_{1}\|\cdot\|\mathbf{B}_{2}\|)\)._

Before elaborating on theorems, we introduce the following assumption, which separates the discussions into two cases.

**Assumption 4.1**.: \(\mathbf{X}\mathbf{X}^{T}\) _does not share the same eigenspace with \(\mathbf{P}-\mathbf{X}\mathbf{X}^{T}\)._
Note that the above assumption is weak and frequently holds in most cases. For simplicity, \(\mathbf{U}_{r}\in\mathbb{R}^{n\times r}\) (\(r\in\mathbb{N}_{+}\)) is the eigenvectors associated with \(r\) leading eigenvalues. Under this assumption, we find that the error of \(\mathcal{M}\) is upper-bounded by \(\varepsilon\).

**Theorem 4.1**.: _Let \(\delta=1-\cos(\theta_{*}/2)\) and \(\theta_{*}=\theta((\mathbf{P}-\mathbf{X}\mathbf{X}^{T})\mathbf{Q},\mathbf{Q}(\mathbf{P}-\mathbf{X}\mathbf{X}^{T }))\) where \(\mathbf{Q}=\mathbf{U}_{o}\mathbf{U}_{o}^{T}-\mathbf{I}/2\) and \(o=\min(\operatorname{rank}(\mathbf{X}),k)\). Under Assumption 4.1, if \(\|\mathbf{P}-\mathbf{H}\mathbf{H}^{T}\|=\varepsilon\leq\mathcal{O}(\delta)\) and \(\sigma_{*}\leq\mathcal{O}(\sqrt{\delta})\) where \(\sigma_{*}\) is the \((o+1)\)-th largest singular value of \(\mathbf{X}\), then there exists \(\mathbf{W}\in\mathbb{R}^{d\times k}\) so that \(\|\mathbf{P}-\mathbf{H}\mathbf{H}^{T}\|\leq\varepsilon\). In other words, if \(\varepsilon\) is small enough, then \(\mathbf{H}\mathbf{H}^{T}\) could be a better approximation than \(\mathbf{X}\mathbf{X}^{T}\)._

Specially, if \(\operatorname{rank}(\mathbf{X})\leq k\) or \(k=d\), \(\sigma_{*}=0\) so that \(\sigma_{*}\leq\mathcal{O}(\sqrt{\delta})\) holds. From the above theorem, we claim that _the error through \(\mathcal{M}\) will not accumulate (i.e., bound by \(\varepsilon\))_ provided that the input \(\mathbf{X}\), the output of the previous modules, is well-trained. We further provide an upper-bound of error if Assumption 4.1 does not hold. The following theorem shows the increasing speed of error is at most linear with the tail singular-values.

**Theorem 4.2**.: _If Assumption 4.1 does not hold, then there exists \(\mathbf{W}\in\mathbb{R}^{d\times k}\) so that \(\|\mathbf{P}-\mathbf{H}\mathbf{H}^{T}\|\leq\varepsilon+\mathcal{O}(\sigma_{*}^{2})\)._

**Corollary 4.1**.: _Given an SGNN with \(L\) linear modules \(\{\mathcal{M}_{t}\}_{t=1}^{L}\) with \(\mathcal{L}_{FT}^{(t)}=\|\mathbf{P}-\mathbf{H}_{t}\mathbf{H}_{t}^{T}\|\), if \(\mathbf{P}-\mathbf{H}_{1}\mathbf{H}_{1}^{T}\) and \(\mathbf{H}_{1}\mathbf{H}_{1}^{T}\) share the same eigenspace, then \(\mathcal{L}_{FT}^{(L)}\leq\mathcal{L}_{FT}^{(1)}+\sum_{t=1}^{L-1}\mathcal{O}( \sigma_{*}^{2}(\mathbf{H}_{t}))\)._

Based on Theorem 4.2, we conclude that the residual would not accumulate rapidly when Assumption 4.1 does not hold. All proofs and more discussions are put in Section B-D.

## 5 Experiments

In this section, we conduct experiments to investigate _whether the performance of SGNN could approach the performance of the original \(L\)-layer GNN in a highly-efficient way_ and _what the impact of the non-linearity and flexibility brought by the decoupling is_. To sufficiently answer the above 2 problems, both node clustering and semi-supervised node classification are used. Due to the limitation of space, only 4 common datasets, including Cora, Citeseer, Pubmed [47], and Reddit [14]. Cora and Citeseer contain thousands of nodes. Pubmed has nearly 20 thousands nodes and Reddit contains more than 200 thousands nodes, which are middle-scale and large-scale datasets respectively. The details of four common datasets are shown in Table 1. More experiments on OGB datasets can be found in Section 5.4.

### Node Clustering

#### 5.1.1 Experimental Settings

We first testify the effectiveness of SGNN on the node clustering. We compare our method against 10 methods, including a baseline clustering model K-means, three GCN models without considering training efficiency (GAE [9], ARGA [48], MGAE [37]), and six fast GCN models with GAE-loss (GraphSAGE [14], FastGAE [15], ClusterGAE [18], AGC [49] (an unsupervised extension of SGC [19]), S\({}^{2}\)GC [20], and GAE-S\({}^{2}\)GC).

The used codes are based on the publicly released implementation. To ensure fairness, all multi-layer GNN models consist of two layers and SGNN is comprised of two modules. For models that could be trained by stochastic algorithms, the size of mini-batch is set as 128. The learning rate is set as 0.001 and the number of epochs is set as 100. We set the size first layer as 128 and the second layer

\begin{table}
\begin{tabular}{l c c c c c} \hline Dataset & Nodes & Edges & Classes & Features & Train / Val / Test Nodes \\ \hline \hline Cora & 2,708 & 5,429 & 7 & 1,433 & 140 / 500 / 1,000 \\ Citeseer & 3,327 & 4,732 & 6 & 3,703 & 120 / 500 / 1,000 \\ Pubmed & 19,717 & 44,338 & 3 & 500 & 60 / 500 / 1,000 \\ Reddit & 233K & 11.6M & 41 & 602 & 152K / 24K / 55K \\ \hline \end{tabular}
\end{table}
Table 1: Data Information
size as 64. In particular, when training every module of SGNN, 20% entries of the adjacency matrix are ignored. \(\mathbf{U}\) is initialized as an identity matrix, and \(\eta\) is set as \(10^{3}\) by default. The number of backward training is set as 5 or 10. To investigate the effectiveness of backward training, we report the experimental results with sufficient training for each module, which is denoted by SGNN-FT, while SGNN with the proposed backward training is represented by SGNN-BT. To study the performance of SGNN with different base models, we choose a fully-separable GNN, S\({}^{2}\)GC, as the base model and this method is marked as SGNN-S\({}^{2}\)GC. As S\({}^{2}\)GC does not use the GAE framework, we also added a competitor, namely GAE-S\({}^{2}\)GC, which uses S\({}^{2}\)GC as the encoder, to ensure fairness. For SGNN-S\({}^{2}\)GC and GAE-S\({}^{2}\)GC, all extra hyper-parameters are simply set according to the original paper of S\({}^{2}\)GC for both node clustering and node classification. We do not tune the hyper-parameters of S\({}^{2}\)GC manually. All methods are run five times and the average scores are recorded. The result are summarized in Table 2.

Figure 3: Visualization of SGNN comprised of 3 modules and 3-layer GCN on node classification. For SGNN, the output of \(\mathcal{M}_{3}\) is visualized. For GCN, the output of the final GCN-layer is visualized.

Figure 2: Performance and training efficiency of several scalable GNNs. The efficiency metric is computed by “Consuming Time / # Iterations”. The consuming time begins from loading data into RAM. The first line shows the result of node clustering and the second line is the result of node classification.
#### 5.1.2 Performance

From Table 2, we find that SGNN outperforms in most datasets. If the released codes could not run on Reddit due to out-of-memory (OOM), we put the notation "N/A" instead of results. In particular, SGNN-BT obtains good improvements on Reddit with high efficiency. Specifically speaking, it is about 8% higher than the well-known GraphSAGE. SGNN-FT performs above the average on some datasets. It usually outperforms GraphSAGE but fails to exceed SGC. Due to the deeper structure caused by multiple modules, the performance of SGNN excels the simple GAE. It also outperforms SGC due to more non-linearity brought by multiple modules. Note that S\({}^{2}\)GC and SGC are strong competitors, while SGNN can easily employ them as a base module since they are separable. From the ablation experiments, SGNN-BT works better than SGNN-FT, which indicates the necessity of the backward training.

We also investigate how the number of modules \(L\) affects the node clustering accuracy and the results averaged over 5 runs are reported in Table 5. To ensure fairness, we also show the performance of GAE with the same depth though deeper GCN and GAE usually return unsatisfied results. Note that the neurons of each layers are set as \([256,128,64,32,16,16,16]\), respectively. It is not hard to find that SGNN is robust to the depth compared with the conventional GNNs.

#### 5.1.3 Efficiency

Figure 2 shows the consuming time of several GNNs with higher efficiency on Pubmed and Reddit. Instead of neglecting the preprocessing operation, we measure the efficiency through a more rational

\begin{table}
\begin{tabular}{l c c c} \hline \hline Datasets & Cora & Citeseer & Pubmed \\ \hline \hline GAT & 83.0 \(\pm\) 0.7 & 72.5 \(\pm\) 0.7 & 79.0 \(\pm\) 0.3 \\ DGI & 82.3 \(\pm\) 0.6 & 71.8 \(\pm\) 0.7 & 76.8 \(\pm\) 0.6 \\ GCNII & **85.5 \(\pm\) 0.5** & 73.4 \(\pm\) 0.6 & **80.2 \(\pm\) 0.4** \\ FastGCN\({}^{\dagger}\) & 79.8 \(\pm\) 0.3 & 68.8 \(\pm\) 0.6 & 77.4 \(\pm\) 0.3 \\ GraphSAGE\({}^{\dagger}\) & 77.4 \(\pm\) 0.6 & 66.7 \(\pm\) 0.3 & 79.0 \(\pm\) 0.3 \\ Cluster-GCN\({}^{\dagger}\) & 65.3 \(\pm\) 3.9 & 57.7 \(\pm\) 2.3 & 71.5 \(\pm\) 1.9 \\ \hline GCN & 81.4 \(\pm\) 0.4 & 70.9 \(\pm\) 0.5 & 79.0 \(\pm\) 0.4 \\ SGC & 81.0 \(\pm\) 0.0 & 71.9 \(\pm\) 0.1 & 78.9 \(\pm\) 0.0 \\ SGNN-BT & 81.4 \(\pm\) 0.5 & 70.2 \(\pm\) 0.4 & 77.8 \(\pm\) 0.3 \\ \hline S\({}^{2}\)GC & 83.5 \(\pm\) 0.0 & **73.6 \(\pm\) 0.1** & **80.2 \(\pm\) 0.0** \\ SGNN-S\({}^{2}\)GC & 83.8 \(\pm\) 0.2 & 73.2 \(\pm\) 0.3 & **80.2 \(\pm\) 0.4** \\ \hline \hline \end{tabular} 
\begin{tabular}{l c c} \hline \hline Methods & Reddit \\ \hline \hline GAT & N/A \\ DGI & 94.0 \\ SAGE-mean & 95.0 \\ SAGE-GCN & 93.0 \\ FastGCN & 93.7 \\ Cluster-GCN & **96.6** \\ \hline GCN & N/A \\ SGC & 94.9 \\ SGNN-BT & 95.10 \(\pm\) 0.02 \\ \hline S\({}^{2}\)GC & 95.3 \\ SGNN-S\({}^{2}\)GC & 95.28 \(\pm\) 0.03 \\ \hline \hline \end{tabular}
\end{table}
Table 3: Test accuracy (%) of supervised SGNN averaged over 10 runs on 3 citation datasets

\begin{table}
\begin{tabular}{l|c c c c c c c} \hline \hline Datasets & \multicolumn{2}{c|}{Cora} & \multicolumn{2}{c|}{Citeseer} & \multicolumn{2}{c|}{PubMed} & \multicolumn{2}{c}{Reddit} \\  & ACC & NMI & ACC & NMI & ACC & NMI & ACC & NMI \\ \hline \hline K-Means & 0.4922 & 0.3210 & 0.5401 & 0.3054 & 0.5952 & 0.2780 & 0.1927 & 0.2349 \\ ARGA & 0.6400 & 0.4490 & 0.5730 & 0.3500 & 0.6807 & 0.2757 & N/A & N/A \\ MGAE & 0.6806 & 0.4892 & 0.6691 & 0.4158 & 0.5932 & 0.2957 & N/A & N/A \\ GraphSAGE & 0.6163 & 0.4826 & 0.5664 & 0.3425 & 0.5554 & 0.0943 & 0.6225 & 0.7291 \\ FastGAE & 0.3527 & 0.1553 & 0.2672 & 0.1178 & 0.4262 & 0.0442 & 0.1115 & 0.0715 \\ ClusterGAE & 0.4579 & 0.2261 & 0.4182 & 0.1767 & 0.3913 & 0.0001 & N/A & N/A \\ \hline GAE & 0.5960 & 0.4290 & 0.4080 & 0.1760 & 0.6861 & 0.2957 & N/A & N/A \\ AGC (SGC) & 0.6892 & 0.5368 & 0.6700 & 0.4113 & 0.6978 & 0.3159 & 0.5833 & 0.6894 \\ SGNN-FT & 0.6278 & 0.5075 & 0.6141 & 0.3776 & 0.6444 & 0.2312 & 0.5943 & 0.7156 \\ SGNN-BT & **0.7463** & **0.5546** & 0.6730 & 0.4159 & 0.6951 & **0.3337** & **0.7042** & **0.7601** \\ \hline S\({}^{2}\)GC & 0.6960 & 0.5471 & **0.6911** & **0.4287** & **0.7098** & 0.3321 & 0.7011 & 0.7509 \\ GAE-S\({}^{2}\)GC & 0.6976 & 0.5317 & 0.6435 & 0.3969 & 0.6528 & 0.2452 & 0.6272 & 0.7158 \\ SGNN-S\({}^{2}\)GC & 0.7223 & 0.5404 & 0.6822 & 0.4243 & 0.7084 & 0.3302 & 0.7023 & 0.7575 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Node clustering results
way. We record the totally consuming time after loading data into RAM and then divide the total number of updating parameters of GNNs. The measurement could reflect the real difference of diverse training techniques aiming to apply batch-based algorithms to GNN. It should be emphasized the reason why SGC is worse than SGNN regarding the consuming time. The key point is the different costs of their _preprocessing_ operation. For an \(L\)-order SGC, the computation cost of \(\mathbf{P}^{L}\mathbf{X}\) is at least \(\mathcal{O}(\|\mathbf{A}\|_{0}\,Ld)\) while SGNN with \(L\) first-order modules totally requires \(\mathcal{O}(\|\mathbf{A}\|_{0}\sum_{i=1}^{L}d_{i})\) for the same preprocessing operation. The metric also provides a fair comparison between SGC and other models since the stopping criteria are always different.

### Node Classification

#### 5.2.1 Experimental Setting

We also conduct experiments of semi-supervised classification on four datasets. The split of datasets follows [19] which is shown in Table 1. We compare SGNN against GCN [4], GAT [6], DGI [50], APPNP [51], L2-GCN [34] FastGCN [15], GraphSAGE [14], Cluster-GCN [18], SGC [19], GCNII [52], and S\({}^{2}\)GC [20]. Similarly, we testify SGNN with two different base models, namely SGNN-BT and SGNN-S\({}^{2}\)GC. For GraphSAGE, we use the mean operator by default and some notations are added if the extra operators are used. On citation networks, the learning rate is set as \(0.01\), while

Figure 4: Visualization of a trained SGNN comprised of 3 modules on node classification of Cora and Citeseer. The first line shows the visualization of Cora and the bottom line shows the visualization of Citeseer.

Figure 5: Visualization of a trained SGNN comprised of 3 modules on node clustering of Cora and Citeseer. The first line is visualization on Cora and the second line is visualization on Citeseer.
it is \(10^{-4}\) on Reddit. Since the nodes for training are less than 200 on citation networks, we use all training points in each iteration for all methods while we sample 256 points as a mini-batch for approaching expected features during backward training of SGNN. On Reddit, the batch size of all batch-based models is set as 512. We do not apply the early stopping criterion used in [4] and the max iteration follows the setting of SGC. The embedding dimensions of each module are the same as the setting in node clustering. For the sake of fairness, we report the results obtained by SGNN with two modules using first-order operation. The forward training loss is defined in Eq. (4). Moreover, all compared models share an identical implementation of their mini-batch iterators, loss function and neighborhood sampler (when applicable). The balance coefficient of \(\mathcal{L}_{FT}\) and \(\mathcal{L}_{BT}\) is set as \(1\) by default. We report the results averaged over 10 runs on citation datasets and 5 runs on Reddit in Table 3 and Table 4. The hyper-parameters are shared for different datasets which are optimized on Cora.

#### 5.2.2 Performance

The results of compared methods in Table 3 are taken from the corresponding papers. When the experimental results are missed, we run the publicly released codes and the corresponding records are superscripted by \(\dagger\). From Tables 3 and 4, we conclude that SGNN outperforms the models with neighbor sampling such as GraphSAGE, FastGCN, and ClusterGCN on citation networks and the performance of SGNN exceeds most models on Reddit. On simple citation networks, SGNN loses the least accuracy compared with other batch-based models, which is close to GCN. Owing to the separability of each module, the batch sampling requires no neighbor sampling and causes no loss of graph information. Note that we simply employ the single-layer GCN as the base modules in our experiments, while some high-order methods that obtain competitive results are also available for SGNN. Although some methods achieve preferable results, they either fail to run or obtain unsatisfactory results on large-scale datasets. Besides, we also show the comparison of efficiency on node classification task in Table 2.

Figure 6: t-SNE Visualization of the output of \(\mathcal{M}_{1}\) from a trained SGNN comprised of 3 modules on node classification of Citeseer.

Figure 7: Convergence curve of the _final loss_. The order of SGC is set as \(L\). The backward training significantly decreases the final loss and the non-linearity also plays an important role.
#### 5.2.3 Visualization to Show Impact of the Decoupling

In Figure 3, we visualize the output of a 3-module SGNN and a 3-layer GCN to directly show that _the decoupling would not cause the trivial features_, which corresponds to the theoretical conclusion in Section 4. To show the benefit of the non-linearity brought by SGNN and the backward training, the convergence curves of SGC, SGNN-FT, and SGNN-BT are shown in Figure 7. Note that the figure shows the variation of the _final loss_. In SGNN, the final loss is the loss of \(\mathcal{M}_{L}\), while it is the unique training loss in SGC. SGC with \(L\)-order graph operation is used. From this figure, we can conclude that: (1) The non-linearity does lead to a better loss value; (2) The backward training significantly decreases the loss. In summary, _the decoupling empirically does not cause the negative impact._

### Visualization

We also provide more visualizations in Figures 4 and 5. We run SGNN with 3 GNN modules and visualize the input and output of \(\mathcal{M}_{1}\), \(\mathcal{M}_{2}\), and \(\mathcal{M}_{3}\) through \(t\)-SNE on Cora and Citeseer, for node clustering and node classification. The purpose of these two figures is to empirically investigate _whether the decoupling would cause the accumulation of residuals and errors_. The experimental results support the theoretical results that are provided in Section 4. One may concern the impact of \(\eta\) (trade-off coefficient between \(\mathcal{L}_{FT}\) and \(\mathcal{L}_{B}T\)) on the performance. We testify SGNN with different \(\eta\) from \(\{10^{-5},10^{-3},10^{-1},10^{1},10^{3},10^{5}\}\) and find that \(\eta=10^{3}\)**usually leads to good results**. Accordingly, we only report results SGNN with \(\eta=10^{3}\) in this paper. Moreover, we show the impact of \(\eta\) to node clustering on Cora and Citeseer in Figure 8.

Moreover, we show the output of \(\mathcal{M}_{1}\) of different periods in Figure 6, in order to show the impact of the backward training. From the figure, we find that BT indeed affects the latent features, which is particularly apparent in Figure 6d.
It should be emphasized that we only use the simple single-layer GCN as the base module of SGNN. The performance can be further improved by incorporating different models such as GCNII, GIN, _etc._ In particular, we only tune hyper-parameters on Arxiv, and we simply report results of SGNN with settings from Reddit.

## 6 Conclusion and Future Works

In this paper, we propose the Stacked Graph Neural Networks (SGNN). We first decouple a multi-layer GNN into multiple simple GNNs, which is formally defined as separable GNNs in our paper to ensure the availability of batch-based optimization without loss of graph information. The bottleneck of the existing stacked models is that the information delivery is only unidirectional, and therefore a backward training mechanism is developed to make the former modules perceive the latter ones. We also theoretically prove that the residual of linear SGNN would not accumulate in most cases for unsupervised graph tasks. The theoretical and experimental results show that the proposed framework is more than an efficient method and it may deserve further investigation in the future. The theoretical analysis focuses on linear SGNN and the generalization bound is also not investigated in this paper. Therefore, they will be the core of our future work. Moreover, as \(\mathcal{L}_{FT}\) could be any losses, how to choose the most appropriate loss for each module will be also a crucial topic in our future works.
