Robust Certification for Laplace Learning on Geometric Graphs

Matthew Thorpe, Bao Wang
Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference, PMLR 145:896-920, 2022.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v145-thorpe22a, title = {Robust Certification for Laplace Learning on Geometric Graphs}, author = {Thorpe, Matthew and Wang, Bao}, booktitle = {Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference}, pages = {896--920}, year = {2022}, editor = {Bruna, Joan and Hesthaven, Jan and Zdeborova, Lenka}, volume = {145}, series = {Proceedings of Machine Learning Research}, month = {16--19 Aug}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v145/thorpe22a/thorpe22a.pdf}, url = {https://proceedings.mlr.press/v145/thorpe22a.html}, abstract = {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. } }
Endnote
%0 Conference Paper %T Robust Certification for Laplace Learning on Geometric Graphs %A Matthew Thorpe %A Bao Wang %B Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference %C Proceedings of Machine Learning Research %D 2022 %E Joan Bruna %E Jan Hesthaven %E Lenka Zdeborova %F pmlr-v145-thorpe22a %I PMLR %P 896--920 %U https://proceedings.mlr.press/v145/thorpe22a.html %V 145 %X 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.
APA
Thorpe, M. & Wang, B.. (2022). Robust Certification for Laplace Learning on Geometric Graphs. Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference, in Proceedings of Machine Learning Research 145:896-920 Available from https://proceedings.mlr.press/v145/thorpe22a.html.

Related Material