Towards Multiple Missing Values-resistant Unsupervised Graph Anomaly Detection

AI summary

Overview

• Research area: Unsupervised graph anomaly detection (GAD), specifically the setting where node attributes and graph edges are missing at the same time.
• Technical level: Advanced. The paper assumes familiarity with graph neural networks, autoencoders, contrastive learning, optimal-transport/Sinkhorn divergence, and hyperspherical latent priors.
• Scope: The paper proposes M²V-UGAD, a framework that imputes missing attributes and missing edges through separate pathways, fuses them in a shared latent space, and generates pseudo-anomalies to counteract imputation bias, evaluated against five unsupervised GAD baselines paired with five imputers on seven public benchmarks.

What This Paper Is About

Most unsupervised graph anomaly detectors assume the input graph is complete, with a full node attribute matrix and a full adjacency matrix. In practice attributes are lost through privacy redaction or collection errors and edges go unrecorded when new nodes arrive, and the standard fix of imputing the data first can "repair" rare anomalous nodes so they look normal. The paper's goal is to detect anomalous nodes directly from an incomplete graph without letting errors from the attribute view contaminate the structure view, and without letting imputation bias erase the anomaly signal.

Key Contributions

1. A new problem setting. The authors state they are the first to investigate unsupervised GAD where both node attributes and the underlying topology are incomplete, rather than assuming a complete graph or handling only one missing view.

2. Dual-pathway imputation with hyperspherical fusion. Attribute imputation is handled by an MLP imputer and structure recovery by deterministic Personalized PageRank diffusion, so the two views cannot propagate errors into each other. The reconstructed views are fused by a lightweight GCN in a shared latent space and regularized toward a truncated hyperspherical Gaussian via Sinkhorn divergence, with an additional decoder reconstructing node attributes to preserve attribute–structure semantics.

3. Graph pseudo-anomaly generation. Latent codes are sampled from a ring-shaped shell just outside the normal region and decoded into realistic pseudo-anomaly node features plus a self-contained subgraph, to counteract imputation bias under anomaly scarcity and sharpen the decision boundary using a mixed Sinkhorn objective.

4. Empirical validation. Experiments on seven public benchmarks show M²V-UGAD outperforming existing unsupervised GAD methods across varying missing rates.

Main Findings

• Highest AUROC under 30% missingness. At a 30% missing rate, M²V-UGAD achieved the best AUROC in every reported column of Table 1 across all five imputation methods. Under the GAIN imputer it scored 0.93 ± 0.02 on Cora, 0.92 ± 0.02 on Citeseer, 0.63 ± 0.02 on Books, 0.81 ± 0.05 on Disney, 0.93 ± 0.01 on Flickr, 0.92 ± 0.01 on ACM, and 0.58 ± 0.02 on Reddit.

• Stability across missing rates. On Cora, M²V-UGAD scored 0.93 ± 0.01, 0.93 ± 0.02, 0.93 ± 0.02, 0.92 ± 0.01, and 0.92 ± 0.01 at 10%, 20%, 30%, 40%, and 50% missing rates respectively. The best baseline on Cora, ADA-GAD, declined from 0.86 ± 0.01 at 10% to 0.77 ± 0.01 at 50% under MissForest.

• Baseline failure modes. Mean Filling, MissForest and GAIN treat nodes independently and ignore structural relationships, producing large imputation errors under severe incompleteness. GAE and ASD-VAE use topology but assume observed structure is complete and reliable, so missing edges introduce structural noise and disrupt message passing. ADA-GAD partially mitigates imputation error through anomaly-denoised pretraining, but its fine-tuning runs on the fully imputed graph, so anomalies already smoothed into normal patterns cannot be rescued.

• Ablation on losses. Removing the imputation loss L_feat or the reconstruction loss L_recon caused a moderate AUROC decline of approximately 2–4% on most datasets (Cora, Citeseer, Books, Disney at 30% missingness).

• Ablation on pathways. Dropping the feature-imputation branch lowered AUROC by roughly 3% to 10%. Discarding the structure-reconstruction path caused the steeper of the two degradations, roughly 10% to 30%.

• Pseudo-anomalies matter most. Disabling pseudo-anomaly generation slashed AUROC by roughly 10% to 35% across all datasets, the largest single drop in the ablation study.

• Hyperparameter robustness. AUROC peaked for the imputation loss weight α in the range 0.001 ≤ α ≤ 0.01; α = 0.0001 under-trained the feature imputer (a slight drop on Disney), and α > 0.01 shifted optimization away from the latent objectives with a clear decline on all datasets. Raising the reconstruction loss weight λ from 0.001 to 1 produced a monotonic but mild downward trend, with a small dip also at 0.0001. Most datasets were almost insensitive to the pseudo-anomaly ratio η within 0.1 ≤ η ≤ 0.5, though Disney declined gradually as η grew; the paper suggests a moderate ratio of roughly 0.1 to 0.3. Latent-sphere radius r between 6 and 8 left AUROC virtually unchanged, and r = 10 caused only a mild decrease (below two percentage points) on Books and Disney.

• Visualization separation. In t-SNE embeddings on Cora with 30% missing rate using GAIN as the imputer, anomalies were entangled with normal nodes for COLA, PREM, GRADATE, ADA-GAD and DiffGAD, while M²V-UGAD showed a clear distinction.

Methodology in Plain English

The input is an attributed graph where some node attributes and some edges are missing; the missing entries are zero-filled and tracked by masks. The framework works in two stages.

First, two imputers run independently. An MLP reconstructs missing node attributes using only the observed attribute values and its mask, trained with a mean squared error loss between observed entries and their reconstructions. Separately, deterministic Personalized PageRank diffusion runs over the observed adjacency to spread relationships beyond immediate neighbors, and the diffused matrix is added to the observed adjacency to produce a denser surrogate structure. Keeping these two paths apart is the mechanism that stops an error in one view from contaminating the other.

Second, the two reconstructed views are fed into a small GCN that produces a single latent embedding per node. A Sinkhorn divergence aligns the cloud of embeddings to a truncated Gaussian prior on a ball of radius r, which compacts normal nodes into an inner region and implicitly reserves the exterior for anomalies; the authors argue this global distribution matching avoids the trivial collapse that point-to-center objectives such as SVDD can produce. A two-layer MLP decoder also reconstructs node attributes from the latent embeddings, keeping fine-grained semantics in the latent space.

To counter imputation bias, the model samples latent vectors from an annular shell defined by r_a < ||z||₂ < r_b, with r_a = 1.2r and r_b = 2r fixed for all experiments. These vectors are decoded back into feature space and given an internal topology: pairwise cosine similarities among the decoded features are row-wise min-max normalized and binarized at τ_a = 0.5, producing a pseudo-anomaly adjacency that is placed into a block-diagonal augmented graph alongside the real graph, disconnected from real nodes. Training has a pre-training stage on the original incomplete graph and a fine-tuning stage on the augmented graph, the latter using a mixed Sinkhorn loss that pulls pseudo-anomaly embeddings toward the outer shell while keeping normals inside radius r. At inference each node's anomaly score is simply the L2 norm of its latent embedding, and nodes are ranked from highest score downward.

Why This Matters

• Research impact: The paper reframes unsupervised GAD around realistic incomplete graphs rather than the idealized complete-graph assumption, and identifies imputation bias (an imputer trained on majority-normal data restoring anomalies as normal) and cross-view interference as distinct failure modes that a two-stage impute-then-detect pipeline cannot fix.

• Real-world applications mentioned in the paper:

  • Social networks, where spam accounts frequently coalesce into unusually dense connectivity clusters.
  • Financial transaction systems and e-commerce platforms, where collusive users may inflate or deflate item ratings to manipulate ranking algorithms.
  • Biological interaction networks.
  • Any deployment where attributes are redacted for privacy or lost in acquisition, and where edges go unrecorded because new nodes arrive or interactions are not logged.

• Industry relevance: Because the method does not require labels and tolerates missingness in both views simultaneously, it suits production settings where annotation is impractical and data collection is inherently lossy. The paper reports that performance is relatively insensitive to its hyperparameters across roughly two orders of magnitude for λ and across a range of α, η and r, which lowers the tuning burden for deployment.

Future Directions

• Understanding the remaining weak spot. Reddit was the hardest dataset for M²V-UGAD, with AUROC of 0.58 ± 0.02 under GAIN, far below its scores on Cora, Citeseer, Flickr and ACM. What property of graphs like Reddit limits the approach is not resolved in the paper.

• Reducing sensitivity on small graphs. Disney showed a gradual decline as the pseudo-anomaly ratio η grew, which the authors attribute to an excessive synthetic set diluting the decision boundary on very small graphs. Adaptive rather than fixed pseudo-anomaly sampling is a natural follow-up.

• Removing fixed thresholds. The shell bounds r_a = 1.2r and r_b = 2r and the binarization threshold τ_a = 0.5 are set as constants for all experiments. Whether these can be learned or selected per graph is unaddressed.

• Broadening the evaluation. The study uses seven benchmarks, four of which rely on injected anomalies following the CoLA protocol, and reports AUROC only, averaged over 5 independent runs. Other anomaly types, domains, and metrics are left open.

Target Audience

Researchers and graduate students working on graph anomaly detection, graph representation learning, or learning with incomplete graph data will find the core contribution most relevant, since the framework sits at the intersection of graph imputation and unsupervised detection. Practitioners in fraud detection, trust-and-safety, recommendation integrity, and bioinformatics will benefit from the robustness results under varying missing rates. Readers need a working knowledge of GNNs, autoencoders, and distribution-matching objectives; the paper reports results in AUROC and comparison tables rather than presenting itself as an introductory text.

Authors’ abstract

Unsupervised graph anomaly detection (GAD) has received increasing attention in recent years, which aims to identify data anomalous patterns utilizing only unlabeled node information from graph-structured data. However, prevailing unsupervised GAD methods typically presuppose complete node attributes and structure information, a condition hardly satisfied in real-world scenarios owing to privacy, collection errors or dynamic node arrivals. Existing standard imputation schemes risk "repairing" rare anomalous nodes so that they appear normal, thereby introducing imputation bias into the detection process. In addition, when both node attributes and edges are missing simultaneously, estimation errors in one view can contaminate the other, causing cross-view interference that further undermines the detection performance. To overcome these challenges, we propose M$^2$V-UGAD, a multiple missing values-resistant unsupervised GAD framework on incomplete graphs. Specifically, a dual-pathway encoder is first proposed to independently reconstruct missing node attributes and graph structure, thereby preventing errors in one view from propagating to the other. The two pathways are then fused and regularized in a joint latent space so that normals occupy a compact inner manifold while anomalies reside on an outer shell. Lastly, to mitigate imputation bias, we sample latent codes just outside the normal region and decode them into realistic node features and subgraphs, providing hard negative examples that sharpen the decision boundary. Experiments on seven public benchmarks demonstrate that M$^2$V-UGAD consistently outperforms existing unsupervised GAD methods across varying missing rates.