# Balanced Edge Pruning for Graph Anomaly Detection with Noisy Labels

arXiv: https://arxiv.org/abs/2407.05934 · HTML: https://mlsanity.com/paper/2407.05934/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 35 of its 48 references that are in the map.
- First posted on arXiv 8 Jul 2024.

## Builds on (most cited first, 30 of 35)

- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Adversarial Attack on Graph Structured Data](https://mlsanity.com/paper/1806.02371/) (2018)
- [Deep Semi-Supervised Anomaly Detection](https://mlsanity.com/paper/1906.02694/) (2019)
- [Enhancing Graph Neural Network-based Fraud Detectors against Camouflaged Fraudsters](https://mlsanity.com/paper/2008.08692/) (2020)
- [A Comprehensive Survey on Graph Anomaly Detection with Deep Learning](https://mlsanity.com/paper/2106.07178/) (2021)
- [Rethinking Graph Neural Networks for Anomaly Detection](https://mlsanity.com/paper/2205.15508/) (2022)
- [Graph Prototypical Networks for Few-shot Learning on Attributed Networks](https://mlsanity.com/paper/2006.12739/) (2020)
- [AnomalyDAE: Dual autoencoder for anomaly detection on attributed networks](https://mlsanity.com/paper/2002.03665/) (2020)
- [NRGNN: Learning a Label Noise-Resistant Graph Neural Network on Sparsely and Noisily Labeled Graphs](https://mlsanity.com/paper/2106.04714/) (2021)
- [Few-shot Network Anomaly Detection via Cross-network Meta-learning](https://mlsanity.com/paper/2102.11165/) (2021)
- [GADBench: Revisiting and Benchmarking Supervised Graph Anomaly Detection](https://mlsanity.com/paper/2306.12251/) (2023)
- [Graph Anomaly Detection via Multi-Scale Contrastive Learning Networks with Augmented View](https://mlsanity.com/paper/2212.00535/) (2022)
- [Truncated Affinity Maximization: One-class Homophily Modeling for Graph Anomaly Detection](https://mlsanity.com/paper/2306.00006/) (2023)
- [Towards Self-Interpretable Graph-Level Anomaly Detection](https://mlsanity.com/paper/2310.16520/) (2023)
- [Reinforced Causal Explainer for Graph Neural Networks](https://mlsanity.com/paper/2204.11028/) (2022)
- [Alleviating Structural Distribution Shift in Graph Anomaly Detection](https://mlsanity.com/paper/2401.14155/) (2024)
- [Cross-Domain Graph Anomaly Detection via Anomaly-aware Contrastive Alignment](https://mlsanity.com/paper/2212.01096/) (2022)
- [Weak Supervision for Fake News Detection via Reinforcement Learning](https://mlsanity.com/paper/1912.12520/) (2019)
- [Challenges and Opportunities in Deep Reinforcement Learning with Graph Neural Networks: A Comprehensive review of Algorithms and Applications](https://mlsanity.com/paper/2206.07922/) (2022)
- [Robust Training of Graph Neural Networks via Noise Governance](https://mlsanity.com/paper/2211.06614/) (2022)
- [Causal Understanding of Fake News Dissemination on Social Media](https://mlsanity.com/paper/2010.10580/) (2020)
- [Learning Strong Graph Neural Networks with Weak Information](https://mlsanity.com/paper/2305.18457/) (2023)
- [Weakly Supervised Anomaly Detection: A Survey](https://mlsanity.com/paper/2302.04549/) (2023)
- [Entity Alignment with Noisy Annotations from Large Language Models](https://mlsanity.com/paper/2405.16806/) (2024)
- [Noise-robust Graph Learning by Estimating and Leveraging Pairwise Interactions](https://mlsanity.com/paper/2106.07451/) (2021)
- [Reinforcement learning on graphs: A survey](https://mlsanity.com/paper/2204.06127/) (2022)
- [GraphSR: A Data Augmentation Algorithm for Imbalanced Node Classification](https://mlsanity.com/paper/2302.12814/) (2023)
- [Modality-Aware Integration with Large Language Models for Knowledge-based Visual Question Answering](https://mlsanity.com/paper/2402.12728/) (2024)
- [ADMoE: Anomaly Detection with Mixture-of-Experts from Noisy Labels](https://mlsanity.com/paper/2208.11290/) (2022)
- [Relevance-Aware Anomalous Users Detection in Social Network via Graph Neural Network](https://mlsanity.com/paper/2104.06095/) (2021)

## Abstract (arXiv)

Graph anomaly detection (GAD) is widely applied in many areas, such as financial fraud detection and social spammer detection. Anomalous nodes in the graph not only impact their own communities but also create a ripple effect on neighbors throughout the graph structure. Detecting anomalous nodes in complex graphs has been a challenging task. While existing GAD methods assume all labels are correct, real-world scenarios often involve inaccurate annotations. These noisy labels can severely degrade GAD performance because, with anomalies representing a minority class, even a small number of mislabeled instances can disproportionately interfere with detection models. Cutting edges to mitigate the negative effects of noisy labels is a good option; however, it has both positive and negative influences and also presents an issue of weak supervision. To perform effective GAD with noisy labels, we propose REinforced Graph Anomaly Detector (REGAD) by pruning the edges of candidate nodes potentially with mistaken labels. Moreover, we design the performance feedback based on strategically crafted confident labels to guide the cutting process, ensuring optimal results. Specifically, REGAD contains two novel components. (i) A tailored policy network, which involves two-step actions to remove negative effect propagation step by step. (ii) A policy-in-the-loop mechanism to identify suitable edge removal strategies that control the propagation of noise on the graph and estimate the updated structure to obtain reliable pseudo labels iteratively. Experiments on three real-world datasets demonstrate that REGAD outperforms all baselines under different noisy ratios.