# Mitigating the Impact of Noisy Edges on Graph-Based Algorithms via Adversarial Robustness Evaluation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 29 references that are in the map.
- First posted on arXiv 28 Jan 2024.

## Builds on (most cited first, 13 of 13)

- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [DeepFool: a simple and accurate method to fool deep neural networks](https://mlsanity.com/paper/1511.04599/) (2015)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Deep Neural Networks are Easily Fooled: High Confidence Predictions for Unrecognizable Images](https://mlsanity.com/paper/1412.1897/) (2014)
- [Detecting Adversarial Samples from Artifacts](https://mlsanity.com/paper/1703.00410/) (2017)
- [On Detecting Adversarial Perturbations](https://mlsanity.com/paper/1702.04267/) (2017)
- [Evaluating the Robustness of Neural Networks: An Extreme Value Theory Approach](https://mlsanity.com/paper/1801.10578/) (2018)
- [Analysis of classifiers' robustness to adversarial perturbations](https://mlsanity.com/paper/1502.02590/) (2015)
- [Adv-BNN: Improved Adversarial Defense through Robust Bayesian Neural Network](https://mlsanity.com/paper/1810.01279/) (2018)
- [ML-LOO: Detecting Adversarial Examples with Feature Attribution](https://mlsanity.com/paper/1906.03499/) (2019)
- [Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple](https://mlsanity.com/paper/1605.02353/) (2016)
- [SPADE: A Spectral Method for Black-Box Adversarial Robustness Evaluation](https://mlsanity.com/paper/2102.03716/) (2021)
- [Towards Scalable Spectral Clustering via Spectrum-Preserving Sparsification](https://mlsanity.com/paper/1710.04584/) (2017)

## Abstract (arXiv)

Given that no existing graph construction method can generate a perfect graph for a given dataset, graph-based algorithms are often affected by redundant and erroneous edges present within the constructed graphs. In this paper, we view these noisy edges as adversarial attack and propose to use a spectral adversarial robustness evaluation method to mitigate the impact of noisy edges on the performance of graph-based algorithms. Our method identifies the points that are less vulnerable to noisy edges and leverages only these robust points to perform graph-based algorithms. Our experiments demonstrate that our methodology is highly effective and outperforms state-of-the-art denoising methods by a large margin.