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

2024/01/28 by Wang, Yongyu, Zhuang, Xiaotian
#Computer Vision and Pattern Recognition (cs.CV) #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2401.15615

Abstract

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.

Related

• Adversarial-Robustness-Guided Graph Pruning
• Adversarial contamination of networks in the setting of vertex nomination: a new trimming method
• Graph Robustness Benchmark: Benchmarking the Adversarial Robustness of Graph Machine Learning
• Spectrally unstable nodes drive reliability failures in graph learning
• Certified Robustness of Graph Classification against Topology Attack with Randomized Smoothing