Robust Certification for Laplace Learning on Geometric Graphs
Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference, PMLR 145:896-920, 2022.
Graph Laplacian (GL)-based semi-supervised learning is one of the most used approaches for clas- sifying nodes in a graph. Understanding and certifying the adversarial robustness of machine learn- ing (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 quanti- tatively 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 lever- aging existing adversarial defenses for the k-nearest neighbor classifier can remarkably improve the robustness of the GL classifier.