Addressing Noise and Efficiency Issues in Graph-Based Machine Learning
  Models From the Perspective of Adversarial Attack
Yongyu Wang
Given that no existing graph construction method can generate a perfect graph
for a given dataset, graph-based algorithms are invariably affected by the
plethora of redundant and erroneous edges present within the constructed
graphs. In this paper, we propose treating these noisy edges as adversarial
attack and use a spectral adversarial robustness evaluation method to diminish
the impact of noisy edges on the performance of graph algorithms. Our method
identifies those points that are less vulnerable to noisy edges and leverages
only these robust points to perform graph-based algorithms. Our experiments
with spectral clustering, one of the most representative and widely utilized
graph algorithms, reveal that our methodology not only substantially elevates
the precision of the algorithm but also greatly accelerates its computational
efficiency by leveraging only a select number of robust data points.