Robust Certification for Laplace Learning on Geometric Graphs
This addresses the need for robust certification in security-critical domains, but it is incremental as it builds on existing defenses and focuses on a specific classifier.
The paper tackles the problem of certifying adversarial robustness for Graph Laplacian-based semi-supervised learning, providing the first theoretical certification that bounds the difference in classification accuracy before and after an attack, with numerical validation showing that leveraging existing defenses for k-nearest neighbor classifiers can improve robustness.
Graph Laplacian (GL)-based semi-supervised learning is one of the most used approaches for classifying nodes in a graph. Understanding and certifying the adversarial robustness of machine learning (ML) algorithms has attracted large amounts of attention from different research communities due to its crucial importance in many security-critical applied domains. There is great interest in the theoretical certification of adversarial robustness for popular ML algorithms. In this paper, we provide the first adversarial robust certification for the GL classifier. More precisely we quantitatively bound the difference in the classification accuracy of the GL classifier before and after an adversarial attack. Numerically, we validate our theoretical certification results and show that leveraging existing adversarial defenses for the $k$-nearest neighbor classifier can remarkably improve the robustness of the GL classifier.