# Enhanced Graph Autoencoder for Graph Anomaly Detection Using Subgraph Information
## 3 Proposed Method
### Subgraph Preprocessing Stage  
Recent studies [26; 27; 36; 37; 38; 39; 40] have demonstrated the effectiveness of incorporating subgraph information around nodes into the embedding encoding process. Experimental results from such studies have shown significant improvements in various learning tasks, including graph classification, link prediction, and substructure counting. In this work, the methodology parallels the strategy outlined in [36], involving the extraction and utilization of complete k-hop subgraphs around each node in the graph. This approach enables the model to aggregate subgraph-level information, producing enhanced node representations for subsequent learning tasks. This stands in contrast to the designs in [26; 27], which utilized random-walk subgraphs. Figure 1: Overall architecture of the proposed framework. In a given attributed graph \(G=(V,E,\mathbf{X})\), the k-hop subgraph centered around a source node \(v_{i}\in V\) is denoted as \(G^{k}\left(v_{i}\right)=(V_{v_{i}}^{k},\,E_{v_{i}}^{k},\,\mathbf{X}_{v_{i}}^{k})\), where \(V_{v_{i}}^{k}\subseteq V\) and \(E_{v_{i}}^{k}\subseteq E\). \(V_{v_{i}}^{k}\) consists of all nodes \(u\in V\) such that the shortest path between \(u\) and source node \(v_{i}\) has length \(l\), where \(l\leq k\in\mathbb{N}\), and \(\mathbf{X}_{v_{i}}^{k}\) includes the node features for every node in the k-hop subgraph \(G^{k}\left(v_{i}\right)\). Given the attributed graph \(G=(V,E,\mathbf{X})\) with \(n\) nodes and the setting of \(k\), each node in the graph is treated as the source node to extract the k-hop subgraph around it, yielding \(G^{k}\left(v_{i}\right)=(V_{v_{i}}^{k},\,E_{v_{i}}^{k},\,\mathbf{X}_{v_{i}}^{k})\) for each node \(v_{i}\in V\). The subgraph topology can be represented by the adjacency matrix \(\mathbf{A}_{V_{v_{i}}^{k}}\). During the subgraph preprocessing stage, the goal is to generate enhanced node embeddings and a node-subgraph similarity matrix as input for the two encoders in the next stage. To mitigate interference induced by the absolute positions of nodes in the vector space, Ref. [36] introduced a subgraph centralization strategy. This strategy involves translating each subgraph to the same extent, with the source node in each subgraph moved to the origin. Here, the same centralization operation is applied to each subgraph. For each subgraph \(G^{k}\left(v_{i}\right)\) with subgraph attribute matrix \(\mathbf{X}_{v_{i}}^{k}\) and source node attribute \(\mathbf{X}_{i}\), the source node attribute \(\mathbf{X}_{i}\) is subtracted from each row in \(\mathbf{X}_{v_{i}}^{k}\) to create the centralized subgraph node features \(\widetilde{\mathbf{X}_{v_{i}}^{k}}\), therefore ensuring that the source node featured in \(\widetilde{\mathbf{X}_{v_{i}}^{k}}\) is translated to the origin. Instead of employing the Weisfeiler-Lehman method [41] to embed the subgraph, as was performed in [36], a subgraph-level topological approach is adopted in this work: a subgraph aggregation process followed by a pooling operation. This approach empowers the framework to capture the topological information of subgraphs and generate enhanced node embeddings. Let \(\mathbf{D}_{V_{v_{i}}^{k}}\) denote the degree matrix of the subgraph adjacency matrix \(\mathbf{A}_{V_{v_{i}}^{k}}\). Then, the embedding process for the subgraph centered around node \(v_{i}\) to generate the enhanced node embedding vector \(\hat{\mathbf{x}}_{v_{i}}\) is computed as follows:  
\[\hat{\mathbf{x}}_{v_{i}}=MeanPooling(\mathbf{D}_{V_{v_{i}}^{k}}^{-1}\mathbf{A}_{V_{v_{i} }^{k}}\,\,\widetilde{\mathbf{X}_{v_{i}}^{k}}) \tag{1}\]  
or  
\[\hat{\mathbf{x}}_{v_{i}}=\,\,[\mathbf{X}_{i},\,\,MeanPooling(\mathbf{D}_{V_{v_{i}}^{k}} ^{-1}\mathbf{A}_{V_{v_{i}}^{k}}\,\,\widetilde{\mathbf{X}_{v_{i}}^{k}})] \tag{2}\]  
where \([\cdot]\) denotes concatenation. The embedding-enhanced attribute matrix is then denoted as \(\hat{\mathbf{X}}\).