# A Scalable Deep Network for Graph Clustering
## 3 The Proposed Method
### Quasi-GNN Module
#### 3.3.2 Linear Propagation Module  
We first briefly review the message passing algorithm of traditional GCNs. A traditional two-layer GCN model can be defined as  
\[\mathbf{Z}_{GCN}=Softmax(\hat{\mathbf{A}}ReLu(\hat{\mathbf{A}}\mathbf{X} \mathbf{W}_{0})\mathbf{W}_{1}), \tag{7}\]  
where \(\hat{\mathbf{A}}=\bar{\mathbf{D}}^{r-1}\hat{\mathbf{A}}\bar{\mathbf{D}}^{-r}\), \(\hat{\mathbf{A}}\) is the normalized adjacency matrix, by setting \(r=1\) or \(0.5\), we can obtain different regularization methods, such as \(\hat{\mathbf{A}}\bar{\mathbf{D}}^{-1}\), \(\bar{\mathbf{D}}^{-\frac{1}{2}}\hat{\mathbf{A}}\bar{\mathbf{D}}^{-\frac{1}{2}}\), and \(\bar{\mathbf{D}}^{-1}\bar{\mathbf{A}}\). The predicted labels is \(\mathbf{Z}_{GCN}\). In a traditional two-layer GCN model, the calculation of each layer depends on the calculation result of the previous layer. Limited by this calculation method, the computational costs of the traditional GNN models increase exponentially. It is difficult to expand the model depth and the neighborhood range together for their orthogonal relationship. According to [PERSON] et al. (2018), the influence score of sample \(x\) on \(y\) in GNN can be defined as  
\[I(x,y)=\sum_{i}\sum_{j}\frac{\partial\mathbf{Z}_{yi}}{\partial\mathbf{X}_{xj}}. \tag{8}\]  
In the \(k\)-layers GNN, \(I(x,y)\propto P_{rw^{\prime}}(x\to y,k)\), where \(P_{rw^{\prime}}(x\to y,k)\) is the random walk distribution after fine-tuning. When \(k\rightarrow\infty\), if the graph is irreducible and aperiodic, the value will approach a stable distribution independent of \(x\) (i.e., the same amount of influence scaling), which indicates that the influence of the \(x\) on the \(y\) at this time will eventually be independent of the local graph structure. Assuming that this stable distribution is \(\pi_{lim}\), we can calculate the distribution by the following formula  
\[\pi_{lim}=\hat{\mathbf{A}}\pi_{lim}. \tag{9}\]  
Obviously, the result is related to the structure of the whole graph and has no relation to the starting point of the random walk, which means that we finally consider the information of the whole graph and ignore the nodes themselves. In addition, the original pagerank also adopts this calculation method to obtain the full graph structure.  
\[\pi_{pr}=\mathbf{A}_{rw}\pi_{pr}\qquad\mathbf{A}_{rw}=\mathbf{A}\mathbf{D}^{- 1}. \tag{10}\]  
Based on this, we can adopt a variant of pagerank (i.e., personalized pagerank) to reconsider the root node. Assuming that \(\mathbf{i}_{x}\) is the indicator vector of node \(x\), its vector representation after multiple propagations can be defined as  
\[\pi_{ppr}(\mathbf{i}_{x})=(1-\alpha)\hat{\mathbf{A}}\pi_{ppr}(\mathbf{i}_{x} )+\alpha\mathbf{i}_{x}, \tag{11}\]  
where \(\alpha\) is the transmission probability, \(\alpha\in[0,1]\), \(\hat{\mathbf{A}}\) is the normalized adjacency matrix. In this way, we can obtain an approximate post-propagation matrix with respect to the entire graph data  
\[\mathbf{M}^{(0)}=\mathbf{T}=g(X), \tag{12}\]  
\[\mathbf{M}^{(k+1)}=(1-\alpha)\hat{\mathbf{A}}\mathbf{M}^{(k)}+\alpha\mathbf{T}, \tag{13}\]  
where \(\mathbf{M}^{(k)}\) is the result of the \(k\)-th propagation, \(\mathbf{T}\) is the embedding obtained by the linear encoder. Therefore, we can deduce the final embeddings \(\mathbf{Z}\) by combining the intermediate embeddings \(\mathbf{H}\) in the Seciton 3.3.1.  
\[\mathbf{M}^{(0)}=\hat{\mathbf{H}}=\mathbf{H}^{(L)}, \tag{14}\]\[\mathbf{M}^{(k+1)}=(1-\alpha)\mathbf{\hat{A}M}^{(k)}+\alpha\mathbf{\hat{H}}. \tag{15}\]  
The last layer of the linear propagation module is the multi-classification function of the softmax function  
\[\mathbf{Z}=Softmax(\mathbf{M}^{(K)})=Softmax((1-\alpha)\mathbf{\hat{A}M}^{(K)}+ \alpha\mathbf{\hat{H}}). \tag{16}\]  
As a result, \(\mathbf{z}_{ij}\in\mathbf{Z}\) indicates the probability that a node \(v_{i}\) belongs to the cluster \(j\). Moreover, we can consider \(\mathbf{Z}\) as a kind of aggregation class distribution.