# Enhanced Graph Autoencoder for Graph Anomaly Detection Using Subgraph Information
## 3 Proposed Method
### Overall Model Framework  
In this subsection, the proposed framework is presented in detail, and the overall pipeline is illustrated in Figure 1 below. As shown in the figure, the model consists of several fundamental components:  
1. The subgraph preprocessing stage, which extracts k-hop subgraphs for each node in the graph to generate enhanced embeddings and the node-subgraph similarity matrix seamlessly.
2. The attributed network encoding stage, where two graph encoders (GCNs) are utilized, one with the original adjacency matrix and one with the node-subgraph similarity matrix, to encode the enhanced node embeddings generated in stage (1) for parallel representation learning. Then, the two encoded embeddings are concatenated together and passed through a fully connected layer to obtain the final hidden embeddings.  
\begin{table}
\begin{tabular}{c c} \hline \hline
**Notation** & **Description** \\ \hline n & Number of nodes in the graph. \\ \hline d & Attribute dimension. \\ \hline G & Attributed graph. \\ \hline V = [v\({}_{1}\), v\({}_{2}\),..., v\({}_{n}\)] & Set of n nodes in the graph. \\ \hline E & Set of m edges in the graph. \\ \hline \(\textbf{X}\in\ \mathbb{R}^{n\times d}\) & Attribute matrix for nodes in the graph. \\ \hline \(\textbf{X}_{i}\in\ \mathbb{R}^{d}\) & Attribute information for node v\({}_{i}\) \\ \hline \(\textbf{A}\in\ \mathbb{R}^{n\times n}\) & Adjacency matrix of the graph. \\ \hline \(\textbf{I}\) & Identity matrix. \\ \hline \(\left\|\cdot\right\|_{\textbf{F}}\) & Frobenius Norm. \(\left\|\textbf{A}\right\|_{\textbf{F}}=\sqrt{\sum_{i=1}^{m}\sum_{j=1}^{n} \left|\textbf{a}_{ij}\right|^{2}}\) for \(a_{i,j}\) as elements in \(\textbf{A}\in\mathbb{R}^{m\times n}\). \\ \hline \hline \end{tabular}
\end{table}
Table 1: Notations.  
3. The attribute and structure decoding stage, where dedicated GCNs reconstruct the original node attributes with the learned node embeddings, together with a simple graph structure learning layer that reconstructs the graph topology from the learned hidden node embeddings. 4. The anomaly scoring stage, which, after training, utilizes node neighborhood selection to optimize the reconstructed adjacency matrix, assigns anomaly scores to nodes in the graph based on the combined reconstruction errors, and ranks them accordingly.  
During the subgraph preprocessing stage, k-hop subgraphs centered around each node (marked red in Figure 1) in the graph are extracted. These extracted subgraphs are then employed simultaneously to generate enhanced node embeddings and the node-subgraph similarity matrix used in the next stage. Subgraph centralization, followed by aggregation and pooling operations, is utilized for enhanced node embedding generation. Meanwhile, similar aggregation and pooling strategies are applied to the un-centralized subgraphs to update embeddings and compute the node-subgraph similarity matrix. In the attributed network encoding, two GCN-based encoders work in parallel to embed node information from two different views: one with the original adjacency matrix and another with the node-subgraph similarity matrix. Then, the embedded representations from these two views are concatenated together to generate the final hidden embeddings through an additional fully connected layer. With the generated final hidden embeddings, in the attribute and structure decoding stage, a GCN-based decoder is employed to reconstruct the attributes, and a graph structure learning layer is utilized to reconstruct the graph topology. The weighted sum of the attribute reconstruction error and structure reconstruction error is utilized as the loss for training.