UniGAD: Unifying Multi-level Graph Anomaly Detection

We are greatful for your helpful comments! Below are our responses.

Q1: How UniGAD avoid Redundant calculation

Prompt-based methods for handling multiple objects convert all objects into induced graphs during pre-processing. This approach results in the number of induced graphs to be processed equaling the sum of nodes, edges, and graphs, potentially reaching tens of millions in some datasets. Each induced graph contains numerous nodes, often appearing repeatedly across different induced graphs, leading to significant computational redundancy.

In contrast, UniGAD employs a more efficient approach. It first obtains the representation of each node through a pre-trained GNN encoder. Then, using a sampler and pooling architecture, it derives the embeddings for other levels of objects (edges/graphs). The framework optimizes the process by eliminating the need to generate and process numerous induced subgraphs, instead leveraging the original graph structure and minimizing repetitive calculations.

Q2: Minor Corrections

Thank you for bringing this to our attention. The caption of Tables 8 and 9 should be F1-macro. We will thoroughly examine the manuscript for any other minor inconsistencies.

Thank you for your valuable comments to our work! Below are our responses.

Q1: Modification of All-in-One and GraphPrompt

We would like to clarify that we did not alter the core methodologies of GraphPrompt and All-in-One. Our modifications were limited to the data preprocessing component to accommodate the simultaneous handling of multiple object types (node/edge or node/graph) within induced graphs. The original implementations of these methods support processing only one type of graph object at a time, either by handling one object type exclusively or by processing different types sequentially (i.e., one type for pre-training and another type for prompt tuning). They do not inherently support scenarios where multiple object types are input/output simultaneously.

Code Access: We have included the modified versions of All-in-One and GraphPrompt in our source code, which is accessible through the link provided in our manuscript for further reference and verification.

Q2: OOT issues for All-in-One and GraphPrompt

The time limitation mentioned refers specifically to the preprocess stage and prompt tuning stage. During the pre-training stage, both these methods and UniGAD use GraphMAE, and the time consumption is similar and short. The reasons for significant time consumption of All-in-One and GraphPrompt are:

• Large amount of induced graphs in pre-processing: The number of induced graphs becomes the sum of node and edge numbers rather than just the number of graphs. This results in tens of millions of induced k-hop subgraphs in some datasets, causing substantial pre-processing time.
• Large amount of training samples in prompt tuning: Although both methods are known for their fast prompt tuning, it only held for few-shot settings (e.g., 5 or 10 samples for tuning). However, we use the fully supervised setting and have much more training samples, which significantly increased the data required for tuning.
• Redundant computation: Induced graphs between neighboring nodes inevitably contain duplicated nodes. However, the prompt-based approach treats these duplicates as distinct nodes to be computed separately in different graphs, significantly increasing the computational load. In contrast, UniGAD employs a more efficient approach. It first obtains the representation of each node through a pre-trained GNN encoder. Then, using a sampler and pooling architecture, it derives the embeddings for other levels of objects (edges/graphs). The framework optimizes the process by eliminating the need to generate and process numerous induced subgraphs, instead leveraging the original graph structure and minimizing repetitive calculations.

To address the OOT issue, we employ faster GPUs, extended time limits to 2 days, and optimized the pre-processing code. The updated results are as follows:

We found that GraphPrompt can complete all datasets in our additional experiments, while All-in-One still fails to finish on the MNIST0/1 and T-Group datasets. This difference in performance can be attributed to their underlying mechanisms. Based on the All-in-One source code, the model must learn the token structure represented by pairwise relationships among tokens. It calculates the dot product between prompt tokens and input graph nodes to determine link establishment, which is computationally intensive. In contrast, GraphPrompt employs a simpler and faster approach, incorporating a learnable vector integrated into graph pooling through element-wise multiplication.

Q3: Time and space efficiency of UniGAD

Thank you for your suggestion. We have incorporated both time and space efficiency metrics into our evaluation, using the large-scale, real-world T-Group dataset (37,402 graphs, 93,367,082 edges, and 11,015,616 nodes). We used the same batch size for all models to ensure a fair comparison.

To provide a more straightforward comparison between single-task and multi-task baselines, we calculated the average, minimum, and maximum for combinations of single-task node-level and graph-level models, and compare these with multi-task models. The results, as shown in Figure 1(a) in the supplementary PDF, indicate that in terms of execution time, our method is slower than the combination of the fastest single-level models but faster than the average of the combination.

Regarding peak memory usage, Figure 1(b) demonstrates that graph-level models consume significantly more memory than node-level models. Our method maintains memory consumption comparable to node-level models and substantially lower than both graph-level GAD models and prompt-based methods.

W1: The discrepancy of scalar node feature in proofs and vector node feature in practice.

Thank you for highlighting this discrepancy. In theoretical derivations, we followed the established foundations of BWGNN and RQGNN, which consider single-dimensional features in their proofs. This simplification enhances mathematical tractability and facilitates clearer theoretical analysis. In fact, the primary focus of spectral graph theory and graph signal processing is on one-dimensional vectors.

However, we recognize that real-world scenarios typically involve multi-dimensional feature vectors. To address this, we developed two approaches:

• Pre-processing: Normalize all feature dimensions and then take the norm (1-norm in our case) to obtain a composite feature for each node, allowing us to identify the most anomalous nodes based on this comprehensive feature.
• Post-processing: Identify anomalous nodes in each feature dimension separately, and then take the union or combination of these node sets across all dimensions.

We implemented both methods in our code, and our early experiments showed similar results between the two approaches. For efficiency, we used the pre-processing approach in UniGAD. This method ensures that the computational complexity does not increase with the number of feature dimensions, making it more scalable for high-dimensional data. We will clarify this point in the manuscript to provide a more comprehensive understanding of the rationale behind our design choices.

W2. MRQSampler: DP or Recursive

The MRQSampler algorithm utilizes principles of dynamic programming (DP), which may not be immediately apparent and thus requires clarification. The key distinction between DP and recursive or divide-and-conquer approaches is the use of memoization, i.e., storing the results of subproblems to avoid redundant computations in future calculations.

In the MRQSampler, as described in Algorithm 1 (lines 18-29), the process incorporates a bottom-up calculation where the maximum $\Delta$ values of sub-trees are computed starting from the leaves up to the root. It is important to note that sub-trees not selected in initial iterations at lower levels might still be reconsidered in subsequent iterations at higher levels. Therefore, the maximum $\Delta$ for these sub-trees, referred to as 'inferior candidates' in the algorithm, could be computed and stored during their first evaluation. These stored values are then reused in later computations, which is a hallmark of DP.

To better illustrate this process, we restructure Algorithm 1 into the following two stages:

• Stage 1: Compute and store the maximum $\Delta$ for each sub-tree recursively, starting from the leaf nodes and moving upwards to the root. This stage has a computational complexity of $\mathcal{O}(N \log N)$.
• Stage 2: Initiate from the root node and iteratively select the sub-tree with the highest $\Delta$ from the available candidates, incorporating it into the resultant sub-graph until the $\Delta$ of the selected sub-tree exceeds the current RQ. As new sub-trees are added to the resultant set, their child sub-trees are also added to the pool of candidates. The complexity of this stage is $\mathcal{O}(N)$. Without memoization, this stage would necessitate recalculations of the maximum $\Delta$ for these sub-trees.

The implementation of memoization in the DP paradigm to store and reuse the results of sub-tasks effectively reduces redundant computations and optimizes the overall complexity of the algorithm to $\mathcal{O}(N \log N)$. We will make the necessary revisions to the manuscript to better explain this algorithm.

Q1. Time and memory efficiency for MRQSampler

Following your suggestion, we have conducted a comprehensive evaluation of both time and space efficiency on the large-scale, real-world T-Group dataset. In Figure 1(a), we have specifically highlighted the time consumption of the MRQSampler module separately from other parts of UniGAD, about 37% of the total time. The MRQSampler offers a key efficiency advantage: it requires only once computation to generate and record subgraphs, which can be reused across multiple trials without recalculation when tuning parameters. Besides, we find that k-hop subgraph sampling also takes a lot of time in the prompt-based method.

Moreover, the subgraph sampling process for different nodes can be parallelized, as each node's sampling is independent. This parallelization potential further enhances the scalability of our approach, particularly for large-scale graphs. We are actively working on optimizing MRQSampler for GPU acceleration but it presents some challenges. Currently, we offer a CPU-based parallel version of the code.

W3/Q2: Can UniGAD be Unsupervised?

OCGIN and OCGTL are widely used unsupervised graph-level GAD baselines, but some supervised methods also compared with them (e.g., GmapAD and RQGNN). We agree that such comparison is not rigor and will highlight this in our analysis.

UniGAD is also designed with label scarcity in mind. It focuses on scenarios with missing labels at different levels, exploring how labels from one level can compensate for another. While UniGAD requires labels, it exhibits zero-shot transferability---applying learned knowledge to unseen scenarios without requiring labels in a secific type.

Moreover, the MRQSampler can be considered as an independent module in our framework. It leverages the correlation between spectral domain Rayleigh quotients and anomaly degrees to identify the most anomalous subgraphs. Essentially, it functions as a graph algorithm that can theoretically identify the most anomalous node-centered subgraphs in an unsupervised manner. This characteristic makes the MRQSampler adaptable to other unsupervised methods beyond the scope of UniGAD. We view this as an area of independent interest and anticipate its potential applications in unsupervised GAD methods.

We greatly appreciate the reviewer’s thorough and constructive feedback on our paper.

Q1: AUPRC as a complementary metric

We acknowledge the importance of AUPRC as a complementary metric to AUROC and F1-macro, especially for anomaly detection with imbalanced labels. In light of your suggestion, we have now included AUPRC results in our evaluation. We show the all results in the supplementary PDF Table 1-4.

Based on the results, we observe that UniGAD's performance under the AUPRC metric aligns closely with its AUROC and Macro-F1 scores. UniGAD achieves state-of-the-art performance across nearly all scenarios.

Q2: Results on T-Finance, large-scale datasets, and edge prediction

We appreciate the reviewer's interest in high-degree and large-scale datasets. We've conducted additional experiments on the high-degree T-Finance dataset and highlighted our results on another large-scale dataset T-Group.

The above results on T-Finance indicate that UniGAD outperforms all baseline methods in both node-level and edge-level GAD tasks. Regarding two prompt-based multi-task approaches, GraphPrompt and All-in-One, the preprocessing phase proved to be excessively time-consuming and consume substantial memory, failing to complete within a 2-day timeframe. The primary reason for this inefficiency is the need to generate a distinct induced graph for each edge, which dramatically increases computational demands and memory usage on the high-degree T-Finance dataset.

Large-scale Dataset Performance Analysis: We highlight our results on the T-Finance (39,357 nodes, 21,222,543 edges) and T-Group dataset (37,402 graphs, 11,015,616 nodes, 93,367,082 edges) as reported in the manuscript. Our method demonstrated superior performance in both node-level, edge-level and graph-level anomaly detection on this large-scale, real-world dataset. It surpasses two recent powerful GAD baselines: the node-level method BWGNN and the graph-level method RQGNN. This highlights the versatility and effectiveness of our method across different levels of objects, particularly in handling large-scale scenarios.

Edge Prediction Results Analysis: For edge prediction, UniGAD achieves the best performance on 4 out of 7 datasets for AUROC and 6 out of 7 datasets on F1-macro. While our method is designed for a multi-task setting, the performance on a single level might be slightly compromised to ensure the model performs well across all tasks.

Q3: OOT and OOM under limited resources

We acknowledge the reviewer's concern about the OOM and OOT issues for some baselines on large graphs. We agree that the limit of 24GB GPU RAM and 1-day running time might be insufficient for these resource-intensive methods. To address this, we borrowed A800 80G GPUs for additional experiments during the rebuttal period and extended the time limit to 2 days.

For reference, the datasets having OOM and OOT issues are:

For prompt-based multi-task methods previously facing OOT issues, we employed faster GPUs, extended time limits, and optimized the pre-processing code. These improvements enabled GraphPrompt to complete experiments on all datasets except T-finance. However, All-in-One remained slower than GraphPrompt and failed to finish MNIST0/1 and T-Group within 2 days. This is because All-in-One requires learning token structures through pairwise relationships and calculating dot products between prompt tokens and input graph nodes, which is computationally intensive. In contrast, GraphPrompt simply incorporates a learnable vector into graph pooling via element-wise multiplication, enabling faster processing. The updated results are as follows:

Two graph-level anomaly detection methods, iGAD and GmapAD, initially encountered OOM issues. Using 80GB of GPU RAM, iGAD successfully ran on the MNIST0 and MNIST1 datasets. However, T-Group exceeded memory limits due to the large number of nodes per graph. We switched the processing to CPU, which was completed in 2 days. Conversely, GmapAD could operate within the 80GB memory limit on the A800 GPU but still timed out even with a 2-day limit. We discovered that the final SVM predictor in GmapAD becomes significantly slower with a large number of training samples.