Research on Graph-Level Anomaly Detection Based on Dual-View Graph-of-Graph Representation Learning

Academic Background

In today’s data-driven world, graphs, as a powerful data structure, are widely used in fields such as social network analysis, financial fraud detection, and bioinformatics. Graphs can effectively represent complex relational data, such as user relationships in social networks, fund flows in financial transactions, and atomic and chemical bond relationships in chemical molecules. However, with the widespread application of graph data, how to detect anomalous graph samples (Graph-Level Anomaly Detection, GLAD) from large-scale graph data has become an important research problem.

Existing GLAD methods typically rely on Graph Neural Networks (GNNs) to extract graph-level representations and perform anomaly detection based on these representations. However, the limitation of GNNs lies in their limited receptive field, which may fail to capture potential anomalous information within the graph. Additionally, existing methods often overlook the interactions between graphs, resulting in insufficient exploration of inter-graph anomalous patterns. To address these issues, this paper proposes a novel Dual-View Graph-of-Graph Representation Learning Network, combined with Graph Transformer technology, aiming to comprehensively explore anomalous information in graph data from both intra-graph and inter-graph perspectives.

Source of the Paper

This paper is co-authored by Wangyu Jin, Huifang Ma, and Yingyue Zhang from the College of Computer Science and Engineering, Northwest Normal University, China; Zhixin Li from the Key Laboratory of Education Blockchain and Intelligent Technology, Ministry of Education, Guangxi Normal University; and Liang Chang from the School of Computer Science and Information Security, Guilin University of Electronic Technology. The paper was published in 2025 in the journal Neural Networks, titled “Dual-View Graph-of-Graph Representation Learning with Graph Transformer for Graph-Level Anomaly Detection.”

Research Process

1. Graph Transformer-Enhanced Graph Embedding

To enhance the ability to mine intra-graph information, this paper proposes a graph embedding method based on Graph Transformer. This method combines the advantages of GNNs and Graph Transformer by introducing structural encoding to expand the receptive field of GNNs. The specific steps are as follows:

• GNNs Embedding: The Graph Isomorphism Network (GIN) is used as the GNNs encoder to generate preliminary node embeddings. GIN extracts node features through a Multi-Layer Perceptron (MLP) and neighborhood aggregation mechanisms.
• Transformer Embedding: Based on the traditional Transformer, random walk-based structural encoding is introduced to compute attention scores between nodes. Transformer embeddings are generated through a full-graph attention mechanism.
• Graph Embedding Fusion: The GNNs embeddings and Transformer embeddings are concatenated, and graph-level representations are generated through global average pooling.

2. Dual-View Graph-of-Graph Representation Learning

To explicitly capture inter-graph dependencies, this paper designs a Dual-View Graph-of-Graph Representation Learning module. This module constructs Graph-of-Graph (GoG) representations from both structural and attribute perspectives. The specific steps are as follows:

• Graph-of-Graph Construction: Based on topological similarity and attribute similarity, the Topology-based GoG and Feature-based GoG are constructed, respectively. Topological similarity is calculated using the shortest path kernel function, while attribute similarity is calculated using cosine similarity.
• Graph-of-Graph Propagation: Message propagation is performed on the constructed GoG structures, and GIN is used as the encoder to generate graph-level representations. By minimizing the approximation error between the two views, the consistency of graph representations is ensured.

3. Anomaly Scoring Module

To quantify the degree of anomaly for each graph, this paper designs an anomaly scoring mechanism based on reconstruction errors. The specific steps are as follows:

• Single-Graph Reconstruction Error: The graph’s structure and attribute information are reconstructed using a structural decoder and an attribute decoder, respectively, to compute the single-graph reconstruction error.
• Graph-of-Graph Reconstruction Error: Reconstruction is performed on the Topology-based GoG and Feature-based GoG to compute the Graph-of-Graph reconstruction error.
• Comprehensive Anomaly Score: By combining the single-graph reconstruction error and Graph-of-Graph reconstruction error, a comprehensive anomaly score is generated for final anomaly detection.

Main Results

Extensive experiments were conducted on multiple real-world datasets to validate the effectiveness of the proposed method. The experimental results show that the proposed method outperforms existing GLAD methods on most datasets in terms of the AUC (Area Under Curve) metric. The specific results are as follows:

• Effectiveness of Graph Transformer-Enhanced Embedding: By introducing the Graph Transformer, the receptive field of GNNs is significantly expanded, enhancing the ability to capture intra-graph anomalous information.
• Effectiveness of Dual-View Graph-of-Graph Representation Learning: By explicitly modeling inter-graph relationships, inter-graph anomalous patterns are effectively captured, improving the accuracy of anomaly detection.
• Effectiveness of Anomaly Scoring Mechanism: The anomaly scoring mechanism based on reconstruction errors provides a more comprehensive evaluation of the degree of anomaly, enhancing the robustness of detection.

Conclusion and Significance

This paper proposes a graph-level anomaly detection method based on Dual-View Graph-of-Graph Representation Learning, combined with Graph Transformer technology, to comprehensively explore anomalous information in graph data from both intra-graph and inter-graph perspectives. The method not only expands the receptive field of GNNs but also explicitly models inter-graph relationships, generating high-quality graph-level representations, thereby improving the performance of anomaly detection. This research provides a new approach to graph-level anomaly detection, with significant scientific value and practical application significance.

Research Highlights

1. Introduction of Graph Transformer: By combining Graph Transformer and GNNs, the receptive field of GNNs is significantly expanded, enhancing the ability to capture intra-graph anomalous information.
2. Dual-View Graph-of-Graph Representation Learning: By constructing Graph-of-Graph representations from both structural and attribute perspectives, inter-graph relationships are explicitly modeled, capturing inter-graph anomalous patterns.
3. Anomaly Scoring Mechanism Based on Reconstruction Errors: By performing single-graph and Graph-of-Graph reconstruction, a comprehensive anomaly score is generated, providing a more comprehensive evaluation of anomalies.

Other Valuable Information

The experimental results of this paper show that the proposed method performs excellently on multiple real-world datasets, especially on bioinformatics and social network datasets, where the accuracy of anomaly detection is significantly improved. Additionally, this paper provides a detailed analysis of the impact of different hyperparameters (such as the number of neighbors, control coefficient, and detection threshold) on model performance, offering guidance for parameter selection in practical applications.