Deep Graph-Level Orthogonal Hypersphere Compression for Anomaly Detection

Yunhe Zhang, Yan Sun, Jinyu Cai, Jicong Fan

TL;DR

Standard one-class deep anomaly detection models assume normal data packs tightly into a single solid hypersphere around a centroid, but high-dimensional geometry and empirical graph representations cause this assumption to fail. This paper introduces an orthogonal projection layer to enforce spherical (rather than elliptical) data representations, alongside a bi-hypersphere compression strategy that constrains normal graphs to a spherical shell (between two concentric boundaries), preventing false negatives caused by anomalies lurking near the center.

What Problem Does This Paper Address?

In graph-level anomaly detection (GAD), the goal is to identify abnormal whole graphs (such as anomalous molecular structures or unusual social network sub-communities) in an unsupervised, one-class setting where only normal graphs are available during training.

Deep one-class models (like Deep SVDD) typically pull normal data points toward a single hypersphere center, flagging samples outside a certain radius as anomalies. However, this approach faces two fundamental geometric issues in latent graph space:

  1. Ellipsoidal distortion: In practice, learned representations naturally stretch into hyperellipsoids rather than isotropic spheres, resulting in inaccurate boundary evaluations.
  2. The "soap-bubble" phenomenon: In high-dimensional spaces, Gaussian-distributed mass concentrates away from the center along a thin spherical shell (an effect well-known in high-dimensional probability). As a result, the region near the center of the learned hypersphere is largely empty of normal data. Anomalous graphs can easily map near the centroid and slip past standard hypersphere detectors undetected.

Methods

The authors propose two frameworks, moving from an orthogonalized baseline to a dual-boundary model:

  • Mutual Information Maximization Backbone: Uses a Graph Isomorphism Network (GIN) coupled with multi-layer perceptrons to maximize the Jensen-Shannon mutual information between local node-level substructures and global graph representations.
  • Deep Orthogonal Hypersphere Contraction (DOHSC):
  • Appends an Orthogonal Projection Layer (OPL) via Singular Value Decomposition ($U \Lambda V^\top = H$, setting $W = V_{k'} \Lambda_{k'}^{-1}$) equivalent to standardized PCA. This maps potentially distorted ellipsoidal latent embeddings into an isotropic hypersphere, matching the spherical boundary assumption.
  • Jointly minimizes the distance of normal graph embeddings to a fixed centroid $\tilde{c}$ alongside the mutual information objective.
  • Deep Orthogonal Bi-Hypersphere Compression ($\text{DO2HSC}$):
  • Extends the decision space to an annulus/spherical shell defined by an inner radius $r_{\min}$ and an outer radius $r_{\max}$ (initialized via the $\nu$ and $1-\nu$ distance quantiles).
  • Uses a novel hinge-style loss: $\max\{d_i, r_{\max}\} - \min\{d_i, r_{\min}\}$, forcing normal graphs into the interval $[r_{\min}, r_{\max}]$.
  • Samples are scored as $s_i = (d_i - r_{\max})(d_i - r_{\min})$; points inside the inner void or outside the outer sphere receive positive anomaly scores.

Datasets

The authors evaluated their methods across six real-world benchmark graph datasets:

  • Social Networks: COLLAB (scientific collaboration graphs), COX2 (cyclooxygenase-2 inhibitors / molecular structures, categorized under social/bio), and IMDB-Binary (actor/actress co-appearance).
  • Bioinformatics: MUTAG (mutagenic aromatic compounds), DD (protein structures), and ER_MD (molecular dynamics).

(Note: They also validated the method on the standard non-graph computer vision benchmark Fashion-MNIST in the appendix.)

Key Insights and Ideas

  • Anomalies can hide in plain sight near the center: Due to high-dimensional measure concentration, points drawn from a multivariate normal distribution rarely reside near the origin. The authors observed empirically that anomalous graphs often mapped close to the centroid $\tilde{c}$, where a single-radius hypersphere model automatically classified them as "normal."
  • Constraining data to a shell eliminates the dead zone: By penalizing samples that fall too close to the center ($d_i < r_{\min}$) as well as those too far ($d_i > r_{\max}$), $\text{DO2HSC}$ shields against "empty center" false negatives.
  • Orthogonalization avoids ad-hoc regularization: Instead of using soft penalties to encourage spherical distributions (which add finicky hyperparameters), calculating the projection directly via SVD enforces orthogonality and unit variance across latent dimensions in closed-form during forward passes.

Key Results

  • Graph Anomaly Detection: $\text{DO2HSC}$ achieved state-of-the-art AUC scores across most evaluated datasets, frequently outperforming baseline methods (such as OCGIN, GLocalKD, OCGTL, and graph kernels like WL and Shortest-Path + OC-SVM).
  • On MUTAG (Class 0 as normal), $\text{DO2HSC}$ attained 0.9089 AUC, compared to OCGTL (0.6570) and infoGraph+Deep SVDD (0.8805).
  • On ER_MD (Class 1 as normal), $\text{DO2HSC}$ achieved 0.7351 AUC vs. DOHSC's 0.5184 AUC (over a 20% absolute gain directly caused by eliminating the central dead zone where anomalies clustered).
  • On COLLAB (Class 1 as normal), DOHSC scored 0.9755 AUC and $\text{DO2HSC}$ scored 0.9153 AUC, vastly improving over GLocalKD (0.4330).
  • Ablations: Visualizations and quantitative tests confirmed that removing the orthogonal projection layer (OPL) degraded AUC significantly (e.g., on COX2 Class 0, $\text{DO2HSC}$ dropped from 0.7158 to 0.6281 without OPL).

Limitations and Future Work

  • Sensitivity to the Shell Margin ($\nu$): Setting the quantile parameter $\nu$ too high shrinks the interval between $r_{\min}$ and $r_{\max}$ (they converge when $\nu = 0.5$), deteriorating performance.
  • Computational Cost of Batch SVD: Recalculating the SVD for the orthogonal projector during training iterations adds computational overhead compared to plain neural network linear layers.
  • Hardware/Scalability Limits: The authors noted that large datasets (like DD) forced smaller batch sizes due to GPU memory constraints, which can affect representation stability in batch-dependent mutual information estimators.

Summary updated

Abstract

Graph-level anomaly detection aims to identify abnormal samples of a set of graphs in an unsupervised manner. It is non-trivial to find a reasonable decision boundary between normal data and anomalous data without using any anomalous data in the training stage, especially for data in graphs. This paper first proposes a novel deep graph-level anomaly detection model, which learns the graph representation with maximum mutual information between substructure features and global structure features while exploring a hypersphere anomaly decision boundary. The deep orthogonal projection layer is adopted to keep the training data distribution consistent with the decision hypersphere thus avoiding erroneous evaluations. We further propose projecting the normal data into the interval region between two co-centered hyperspheres, which makes the normal data distribution more compact and effectively overcomes the issue of outliers falling close to the center of the hypersphere. The numerical and visualization results on a few graph datasets demonstrate the effectiveness and superiority of our methods in comparison to many baselines and state-of-the-art.
BibTeX
@inproceedings{zhang2024deep,
  author = {Yunhe Zhang and Yan Sun and Jinyu Cai and Jicong Fan},
  title = {{Deep Graph-Level Orthogonal Hypersphere Compression for Anomaly Detection}},
  booktitle = {International Conference on Learning Representations},
  year = {2024},
  url = {https://openreview.net/forum?id=PnXBG6XxKL},
}
Figure