# Robust Certification for Laplace Learning on Geometric Graphs

arXiv: https://arxiv.org/abs/2104.10837 · HTML: https://mlsanity.com/paper/2104.10837/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 44 references that are in the map.
- First posted on arXiv 22 Apr 2021.

## Builds on (most cited first, 18 of 18)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Practical Black-Box Attacks against Machine Learning](https://mlsanity.com/paper/1602.02697/) (2016)
- [Threat of Adversarial Attacks on Deep Learning in Computer Vision: A Survey](https://mlsanity.com/paper/1801.00553/) (2018)
- [Unlabeled Data Improves Adversarial Robustness](https://mlsanity.com/paper/1905.13736/) (2019)
- [Error estimates for spectral convergence of the graph Laplacian on random geometric graphs towards the Laplace--Beltrami operator](https://mlsanity.com/paper/1801.10108/) (2018)
- [Analysis of p-Laplacian Regularization in Semi-Supervised Learning](https://mlsanity.com/paper/1707.06213/) (2017)
- [Analyzing the Robustness of Nearest Neighbors to Adversarial Examples](https://mlsanity.com/paper/1706.03922/) (2017)
- [A variational approach to the consistency of spectral clustering](https://mlsanity.com/paper/1508.01928/) (2015)
- [The game theoretic p-Laplacian and semi-supervised learning with few labels](https://mlsanity.com/paper/1711.10144/) (2017)
- [Properly-weighted graph Laplacian for semi-supervised learning](https://mlsanity.com/paper/1810.04351/) (2018)
- [ResNets Ensemble via the Feynman-Kac Formalism to Improve Natural and Robust Accuracies](https://mlsanity.com/paper/1811.10745/) (2018)
- [Rates of Convergence for Laplacian Semi-Supervised Learning with Low Labeling Rates](https://mlsanity.com/paper/2006.02765/) (2020)
- [Asymptotic behavior of ℓp-based Laplacian regularization in semi-supervised learning](https://mlsanity.com/paper/1603.00564/) (2016)
- [Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data](https://mlsanity.com/paper/1710.10364/) (2017)
- [From graph cuts to isoperimetric inequalities: Convergence rates of Cheeger cuts on data clouds](https://mlsanity.com/paper/2004.09304/) (2020)
- [Graph Interpolating Activation Improves Both Natural and Robust Accuracies in Data-Efficient Deep Learning](https://mlsanity.com/paper/1907.06800/) (2019)

## Built on by (most cited first, 1 of 1)

- [On the regularized risk of distributionally robust learning over deep neural networks](https://mlsanity.com/paper/2109.06294/) (2021)

## Abstract (arXiv)

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.