Can Edge Addition Be Safe and Effective? Adjacency-Centered Augmentation via Langevin and SDE Diffusion for Self-Supervised Graph Anomaly Detection

1 Introduction

Graph Anomaly Detection (GAD) aims to identify nodes in static graphs that deviate significantly from the majority in real-world information networks. Although such anomalies are typically rare, their detection is crucial due to the potential economic and social consequences. Representative examples include fraudulent users on online shopping platforms [Yu et al., 2024; Zhang et al., 2022], fake news on social media [Feng et al., 2025; Sun et al., 2025], spam on review-sharing platforms [Deng et al., 2022], and intruders in communication networks [Westphal et al., 2025]. With the increasing availability of graph-structured data and the rapid advancement of deep graph neural networks, GAD has attracted substantial research interest across multiple disciplines [Ma et al., 2025; Ma et al., 2021], and has become an important problem in both theoretical research and practical applications.

∗Corresponding author

Existing GAD methods are fundamentally challenged by the severe class imbalance between normal and anomalous nodes, which biases the learning process. Prior work addresses this issue through model design and data augmentation, with prevailing strategies relying on node feature masking, random edge dropping, and subgraph sampling, and recent extensions incorporating diffusion-based graph generators to enrich anomaly patterns. Despite these advances, edge addition or structural completion is rarely explored in GAD augmentation. The primary concern is that introducing new edges may contaminate anomaly-sensitive representations by creating spurious connections involving anomalous nodes, thereby degrading detection performance, as illustrated in Fig. 1(a).

However, as shown in Fig. 1(b) and (c), we empirically observe that carefully increasing edges among normal nodes consistently improves the performance of existing GAD models, with gains scaling approximately proportionally to the number of added edges. This suggests that guided edge addition preserving intra-community connectivity enhances feature aggregation among normal nodes while suppressing the influence of anomalous nodes. These results reveal an underexplored yet promising direction for graph augmentation and naturally raise the question of how to design a principled, label-free strategy for guided edge addition that reliably improves GAD.

To assess the feasibility of guided edge addition in real-world GAD scenarios, we revisit graph denoising and diffusion-based generative models from a spectral energy perspective and examine their applicability to anomaly detection. Leveraging the relationship between graph signal frequencies and anomalous connectivity patterns, we propose two adjacency-matrix-centered diffusion-based augmentation methods, LangGen and JointSDE. LangGen is a featureindependent, training-free approach based on Langevin dynamics, which integrates the Boltzmann distribution with the Rayleigh quotient to increase edge density while preserving low-frequency spectral energy, thereby strengthening intracommunity connectivity without model training. JointSDE, in contrast, formulates a joint feature-structure diffusion process via stochastic differential equations, where spectral graph principles guide the synchronized evolution of node features and the adjacency matrix. This joint diffusion gradually densifies graph structure while regularizing feature distributions, enabling the reconstruction of edge-augmented graphs whose structural and feature representations are jointly evolved and mutually consistent. Extensive experiments on multiple benchmarks with state-of-the-art GAD models demonstrate that both methods generate high-quality edge-augmented graphs with efficient computational and memory overhead, leading to consistent improvements in AUROC and AUPRC.

The contributions of this work are summarized as follows:

• To the best of our knowledge, this work is the first to explore edge addition as a graph augmentation strategy for graph anomaly detection, showing that carefully increasing edges among normal nodes can improve the performance of diverse GAD models.
• Two adjacency-matrix-centered, spectral-guided diffusion methods, LangGen and JointSDE, are proposed to generate high-quality edge-augmented graphs without label information.
• Extensive evaluations on seven state-of-the-art GAD models across twelve benchmark datasets validate the effectiveness, efficiency, and broad applicability of the proposed augmentation strategies.

2 RelatedWork

2.1 Graph Anomaly Detection

Graph anomaly detection aims to identify rare patterns that deviate from dominant graph structures or attributes [Ma et al., 2021; Pazho et al., 2023; Wang et al., 2025; Jin et al., 2024]. Early methods such as Radar [Li et al., 2017] and ANOMALOUS [Peng et al., 2018] detect anomalies via matrix factorization and residual analysis. Deep learningbased approaches, including DOMINANT [Ding et al., 2019], AnomalyDAE [Fan et al., 2020], and ComGA [Luo et al., 2022], detect anomalies via reconstruction errors in graph autoencoders, under the assumption that anomalous nodes are harder to faithfully reconstruct from learned normal patterns. Contrastive learning methods, such as CoLA [Liu et al., 2021], SL-GAD [Zheng et al., 2021], HUGE [Pan et al., 2025], and SAMCL [Hu et al., 2025], enhance detection by contrasting node- and subgraph-level representations. Recently, inspired by the observation that anomalies manifest distinctive spectral energy patterns [Tang et al., 2022], spectral-based GAD

has emerged as an active research direction [Gao et al., 2023; Dong et al., 2024; Xu et al., 2024; Zheng et al., 2025]. Representative methods such as UniGAD [Lin et al., 2024] leverage MRQ-based spectral sampling for multi-level detection, while SALAD [Ma et al., 2025] and ADA-GAD [He et al., 2024] mitigate anomaly interference in normal structure learning through loss reweighting or Rayleigh energy-based denoising. Despite these advances, existing GAD methods predominantly rely on limited and fixed augmentation strategies, such as node masking, feature perturbation, edge dropping, and subgraph sampling, while the potential of edge addition or structural completion remains unexplored.

2.2 DiffusionModel

Diffusion models [Ho et al., 2020; Song et al., 2021a; Song et al., 2021b] have recently emerged as powerful generative frameworks, achieving strong performance across image synthesis [Huang et al., 2025], time-series modeling [Yang et al., 2024], and other domains [Cao et al., 2024]. This success has motivated their extension to graph-structured data. DiGress [Vignac et al., 2023] introduces a discrete diffusion process that perturbs graph structures by stochastically modifying edges and node attributes, and learns an inverse transformation to recover clean graphs via node- and edge-level prediction. GDSS [Jo et al., 2022] formulates graph generation as a continuous-time diffusion process based on stochastic differential equations, demonstrating the effectiveness of whole-graph diffusion for molecular generation. Diffusion models have also been explored in graph anomaly detection. [Ma et al., 2024] generates node features via probabilistic denoising diffusion while keeping the adjacency matrix fixed, aiming to simulate anomalous perturbations. AGDiff [Cai et al., 2025] addresses graph-level anomaly detection by modeling the generation of abnormal graphs, and DiffGAD [Li et al., 2025] further integrates diffusion into the anomaly scoring mechanism. Despite progress, diffusion-based GAD methods remain conservative in structural modeling: some diffuse only node features without modifying connectivity, while others rely on feature-similarity-based adjacency reconstruction, which is fragile under distribution shifts. Moreover, general graph diffusion models neither explicitly model anomalies nor examine the co-evolution of edge density and feature diffusion, leaving principled edge addition in GAD largely unexplored.

3 Methodology

3.1 Preliminary and ProblemFormulation

Given an attributed graph G = (V, E,X), where V = {v1, . . . , vN} denotes the node set, E the edge set, and X ∈ RN×d the node feature matrix. Let A ∈ RN×N denote the adjacency matrix such that Aij = 1 if (vi, vj) ∈ E and Aij = 0 otherwise. The goal of self-supervised graph anomaly detection is to learn a function Fθ : G → RN that assigns each node an anomaly score quantifying its deviation from normal patterns.

3.2 Training-free Generation Approach: LangGen

Langevin Dynamics. Langevin dynamics [Song and Ermon, 2019] enables sampling from high-probability regions of a target distribution pθ(x) by iteratively combining gradientdriven updates with Gaussian noise:

where ϵ denotes the step size. The gradient term drives samples toward regions of high probability, while the injected noise promotes exploration and prevents premature convergence to poor local minima. In the continuous-time limit, this process asymptotically samples from the target distribution.

Boltzmann Distribution and Energy-Based Formulation. The Boltzmann distribution establishes a principled connection between energy functions and probability densities:

where Eθ(x) is a differentiable energy function. Under this formulation, the gradient of the log-density simplifies to

enabling efficient sampling by directly optimizing the energy landscape without explicitly evaluating or normalizing the probability density pθ(x).

Spectral Motivation for Graph Anomaly Detection. Recent studies [Tang et al., 2022] have shown that anomalies exhibit elevated high-frequency energy in the graph spectral domain, and such accumulated energy can be captured by the Rayleigh Quotient (RQ):

where, L = D - A denotes the combinatorial graph Laplacian, D is the degree matrix. Minimizing RQ promotes spectrally smooth structures while suppressing anomalous highfrequency patterns. By incorporating RQ into energy-based Langevin dynamics, the sampling process is explicitly guided toward spectrally coherent graph configurations. Notably, when the node feature matrix X is fixed during generation, energy optimization with respect to the adjacency matrix A directly governs structural evolution, marking a shift from conventional feature-generation paradigms to explicit edge generation. Under this setting, minimizing RQ favors the addition of structurally consistent edges among normal nodes rather than indiscriminate edge removal.

Energy Function Design. To enable gradient-based optimization over graph structure, we treat the adjacency matrix A as a diffusion variable and apply a continuous relaxation. Given an initial binary adjacency matrix A0, we first clamp entries to [ϵ, 1-ϵ] to avoid logit singularities (ϵ = 10-6 ), then compute

where sigm(·) is the sigmoid function and τt controls the relaxation temperature, allowing differentiable updates without introducing learnable parameters.

The total energy function is defined as

where Dens(A) = 2|E|/N 2 denotes graph density, ρtar is the target density, and λ· are trade-off coefficients. The density and smoothness terms prevent degenerate solutions and stabilize structural evolution.

Langevin Update and Annealing. The Langevin update for adjacency matrix generation is given by

where ϵ and σt follow annealing schedules to allow coarse exploration in early iterations and fine-grained refinement later. This process produces spectrally coherent, edge-augmented graphs without requiring any model training.

3.3 Feature-Structure Joint Diffustion: JointSDE

Joint Noising Process. The joint noising process characterizes the coupled degradation of node features and graph structure under a unified diffusion time scale, allowing structural uncertainty to adapt to the evolving feature geometry. As the diffusion time t increases, node features progressively lose discriminative information, while structural constraints are gradually relaxed, driving the system toward a highly stochastic state and providing diverse initial conditions for subsequent reverse refinement.

For continuous node features, we adopt a variancepreserving diffusion formulation [Song et al., 2021b] with the closed-form forward process

where α(t) ∈ (0, 1] controls signal preservation and σ(t) = √1 - α2 (t) denotes the noise scale. As t increases, Xt converges to an isotropic Gaussian.

For graph structure, we adopt a diffusion-inspired probabilistic relaxation that maps the discrete adjacency into timedependent edge probabilities Pij(t) ∈ (0, 1):

where P (0) ij is obtained from the clamped A0,ij via logit, τ(t) controls temperature, and sigm(·) is the sigmoid function. The final adjacency used for backbone training is binarized by thresholding at 0.5, with optional symmetry enforcement and self-loop handling.

The guidance term Sij(t) jointly encodes feature coherence and topological accessibility:

where Simij(t) = 12 (cos(xi(t), xj (t)) + 1) measures feature similarity under diffusion, and Reff(i, j; A0) = L+ii + L+jj - 2L+ij denotes the effective resistance distance derived from the pseudoinverse of the original Laplacian, capturing global multi-path connectivity. This formulation enables a tightly coupled noising process in which structural uncertainty is continuously modulated by the evolving feature state.

Joint Score Network. The joint score network models feature scores and structural uncertainty on the noisy graph Gt = (Xt,At) under a shared diffusion time t, enabling coordinated reverse-time refinement of node attributes and graph topology. A unified encoder fθ processes (Xt,At, t) with explicit time conditioning, where the time embedding is defined as

To capture global structural perturbations induced by structural noise, we construct the symmetric normalized Laplacian

and perform spectral decomposition Lt = ΦtΛtΦ⊤t . The first k low-frequency eigenvectors Φt,k provide spectral coordinates for each node. The initial node representation is given by

and updated through L layers of time-conditioned message passing:

where ˜ At = At+I and ˜Dt is the corresponding degree matrix. The final node representations are denoted by H = h(L) .

The feature score head predicts the denoising score SX = gfea(H) and is trained via denoising score matching:

where Z denotes standard Gaussian noise.

For structural denoising, we estimate edge existence likelihoods conditioned on the noisy graph as a tractable surrogate for reverse-time refinement. An edge-level representation is constructed as uij = [h(L) i ∥ h(L) j ∥ ϕ(t)], and the edge head outputs ˆ Aij = gedge(uij), with the objective

To preserve global geometry during reverse refinement, we introduce a low-frequency spectral regularization

where λgen k and λorig k denote the k-th eigenvalues of the symmetric normalized Laplacian of the generated and original graphs, respectively. The joint score network is trained by minimizing

enforcing consistency between feature-level score estimation and structure-level refinement under a shared latent representation.

Joint Sampling Process. Unlike conventional diffusion models that initialize sampling from pure Gaussian noise, JointSDE injects noise at a randomly sampled diffusion time t and performs partial reverse-time evolution. During sampling, node features are refined via a continuous-time reverse diffusion process, while graph structure evolves through a deterministic, feature-conditioned edge selection mechanism.

The reverse-time update of node features follows the VPSDE and is discretized using an Euler scheme:

where SX denotes the learned feature score function.

Structural refinement is performed deterministically at each step by retaining or pruning edges according to a featureconditioned priority score, avoiding the need to explicitly define a stochastic reverse process over discrete adjacency variables. For each edge (i, j), the structural importance score is defined as

where ˜ S(spec) ij = ∑K′ k=1 ωk (ϕk(i) - ϕk(j))2 , ˜ S(x) ij = sigm( x⊤i xj ∥xi∥ ∥xj ∥ ) . Here, ˜ S(spec) ij captures the contribution of an edge to low-frequency Laplacian components, with frequency-decaying weights ωk emphasizing global geometric stability, while ˜ S(x) ij measures local feature homophily. The degree-based regularizer ˜Dij = 1 di+dj+1 suppresses hubdominated structural bias.

Learned structural preferences are incorporated via the model-predicted edge retention probability

At each reverse step, the top Mt edges with the highest priority scores are retained:

where PMt (·) selects the Mt highest-scoring edges and Mt decreases monotonically as t → 0. Overall, the joint sampling process is summarized as

where Ψ denotes the coupled reverse-time operator combining stochastic feature refinement with spectrally guided deterministic structural evolution.

3.4 GAD Training with Synthetic Data

To enhance a given anomaly detector Fθ, we augment the original graph G with a set of generated graphs D = {G 1 , . . . , G |D| }. For LangGen, G i = {X,Ai } uses original node features with generated edges, whereas for JointSDE, G i = {Xi , Ai } generates both node features and edges. The detector is further optimized on both the original and generated graphs by minimizing

4 Experiments

In this section, we conduct extensive experiments to answer the following research questions: Q1: Can the proposed methods consistently improve state-of-the-art GAD models? Q2: How do individual components in the energy formulation and diffusion framework contribute to structure generation during sampling? Q3: How does the proposed approach compare with existing edge-based graph augmentation strategies? Q4: What is the computational efficiency of the proposed graph generation process? Q5: Does the proposed method preferentially promote edge formation among normal nodes?

4.1 Experimental Setup

Datasets. We evaluate our method on twelve widely used graph anomaly detection benchmarks, including six datasets with organic anomalies (Weibo, Reddit, Books, Enron, Disney, Facebook) and six with injected anomalies (Cora, Amazon, BlogCatalog, ACM, Citeseer, PubMed), with dataset statistics reported in Table 1 and originally collected from [Liu et al., 2024b; Liu et al., 2024c].

Baselines and Metrics. We compare against seven representative unsupervised or self-supervised GAD methods: DOMINANT[Ding et al., 2019], DONE[Bandyopadhyay et al., 2020], AnomalyDAE[Fan et al., 2020], CoLA[Liu et al., 2021], GADNR[Roy et al., 2024], BOURNE[Liu et al., 2024a], and CGADM[Wei et al., 2025]. Performance is evaluated using AUROC and AUPRC.

Implementation Details. LangGen performs training-free edge generation via energy-guided Langevin sampling with 1000 iterations. JointSDE adopts a diffusion-based framework with 1000 forward noising steps and 500 reverse denoising steps. For each graph, ten augmented graphs are generated. The number of edges in each generated graph is fixed to 150% of the original. Baselines are implemented using PyGOD[Liu et al., 2024b] or official code with default settings. Results are averaged over five runs. All experiments are conducted on a single NVIDIA RTX 4090 GPU.

4.2 Improvement on Anomaly Detection Performance (Q1)

Tables 3 and 2 summarize the performance changes of different detectors after incorporating additional generated graphs during training. Across six organic and six injected anomaly datasets, all evaluated baselines consistently achieve improvements in both AUROC and AUPRC, demonstrating that the proposed edge-augmentation-based strategy effectively enhances the discriminative capability of existing graph anomaly detection models. These gains are observed across diverse graph types, including citation, social, review, transaction, and email networks, indicating that the method generalizes well despite substantial differences in degree distributions, community structures, and edge semantics.

Across most experimental settings, the absolute improvements in AUROC are larger than those in AUPRC. This trend is consistent with the strengthened modeling of normal nodes induced by edge augmentation: by promoting more coherent connections among normal nodes, the detector more accurately captures their feature and structural distributions, reducing false positives and improving the true negative rate, which is more directly reflected by the ROC metric. In contrast, AUPRC emphasizes anomaly-focused precision-recall behavior under severe class imbalance, leading to comparatively smaller gains.

Notably, even for datasets with relatively dense original structures, such as Weibo, Facebook, and BlogCatalog, the proposed strategy yields substantial improvements, with AUROC gains of up to 30% and AUPRC gains of up to 10% in certain settings. This suggests that the benefits extend beyond trivial edge completion and are largely attributable to the spectrum-energy-guided edge diffusion mechanism, which reinforces plausible intra-community connections while suppressing noisy inter-community links, thereby facilitating clearer structural decision boundaries.

4.3 Ablation Study (Q2)

We conduct ablation studies to examine whether the energy formulation Eθ(X,A) in Eq. 6 effectively guides edge generation in LangGen and whether JointSDE captures the joint evolution of node features and graph structure. For LangGen, we remove or replace individual energy components, including density regularization (w/o dens), smoothness regularization (w/o smo), both terms (w/o d&s), and the Rayleigh Quotient, where the RQ-based energy is replaced by a readout-based alternative (w/o RQ). For JointSDE, we ablate generated features (w/o fea) or structure (w/o stru), edge priority components in Eq. 22 (w/o score, w/o spe), and the diffusion-based sampling strategy by directly sampling from Gaussian noise (w/o diff ).

We adopt CoLA as the backbone and report results in Table 4. For LangGen, removing any component consistently degrades performance, with w/o RQ yielding the weakest or even negative gains, underscoring the critical role of spectral energy in guiding meaningful edge addition, while density and smoothness terms further stabilize generation and improve robustness. For JointSDE, ablating either features or structure causes clear performance drops, confirming the necessity of joint feature-structure evolution. Although w/o fea underperforms the full model, it remains superior to CoLA due to the intermediate noising-denoising process. In contrast, w/o diff exhibits dataset-dependent behavior, and the comparison between w/o spe and w/o score shows that spectral guidance is essential for edge priority estimation, as learned scores alone fail to capture global structural evolution.

4.4 Edge Augmentation Comparison (Q3)

Table 5 compares our methods with random edge deletion and random edge addition, where both perturbation ratios are fixed at 10% following common practice; performance gains and degradations are highlighted in green and red, respectively.

Across datasets, both random edge deletion and random edge addition exhibit highly inconsistent behavior, improving performance on some datasets while degrading it on others, indicating that such heuristic perturbations fail to provide a stable inductive bias for graph anomaly detection and typically require dataset- and method-specific tuning.

In contrast, LangGen and JointSDE operate at a higher structural level and leverage spectral graph principles to guide edge evolution, yielding consistent and robust performance gains across datasets without extensive hyperparameter tuning, and thereby outperforming conventional edge-level augmentation strategies.

4.5 Computational Efficiency (Q4)

In LangGen, the dominant cost lies in computing the Rayleigh Quotient within the energy function, which can be optimized to O(|E|d) for a sparse graph with |E| edges and feature dimension d. In JointSDE, generation involves feature updates O(Nd), edge importance scoring, and spectral decomposition, where computing the top k eigenvectors contributes O(k|E|) and score network inference over sampled edges Esampled costs O(|Esampled|d). Table 6 reports the average generation time per graph across all datasets.

4.6 Qualitative Analysis (Q5)

To examine whether our proposed method effectively increases connectivity among normal nodes, we visualize results on the Disney dataset, which was selected for its small size to facilitate clear and intuitive analysis. As shown in Figure 3, both LangGen and JointSDE generate substantially more edges compared to the original graph, whereas the number of edges involving anomalous nodes remains minimal. This visualization qualitatively confirms that our approach preferentially reinforces connections between normal nodes, highlighting its targeted enhancement capability.

4.7 More Experiments

Detailed descriptions of the method and experiments, comparisons with other augmentation approaches, qualitative analyses, validation on million-scale graphs, and sensitivity studies of hyperparameters and initialization appear in the appendix.

5 Conclusion and FutureWork

This work demonstrates that moderate, principled edge addition can substantially improve graph anomaly detection, challenging the long-standing practice of relying on conservative edge dropping while deliberately avoiding edge addition. We introduce two self-supervised, spectrally guided augmentation approaches, in which graph structures are refined in a trainingfree manner via Langevin dynamics, or jointly evolved with node features through stochastic differential equations. Experiments on 12 benchmark datasets with 7 state-of-the-art GAD models show that the generated graphs consistently enrich connections among normal nodes while largely preserving anomalous structures. Future work will focus on reducing the number of hyperparameters and extending the framework to broader graph settings, including dynamic and structure-only graphs.

Acknowledgments

The works described in this paper are supported by The National Natural Science Foundation of China under Grant No. 62477015; Key Research and Development Program of Guangdong of China under Grant Nos. 2025B0101120004 and 2023B0303010004; The Innovation Team Project for Universities in Guangdong Province in China under Grant No. 2023KCXTD011.