Mitigating the Impact of Noisy Edges on Graph-Based Algorithms via Adversarial Robustness Evaluation
This addresses the issue of noisy edges degrading performance in graph-based algorithms for researchers and practitioners, representing an incremental improvement over existing denoising methods.
The paper tackles the problem of noisy edges in constructed graphs affecting graph-based algorithms by viewing them as adversarial attacks and using a spectral adversarial robustness evaluation method to identify and leverage robust points, resulting in outperforming state-of-the-art denoising methods by a large margin.
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.