Robust Certification for Laplace Learning on Geometric Graphs

2021-04-22 · Matthew Thorpe, Bao Wang

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.

📄 PDF Abstract BibTeX arXiv:2104.10837

Code (0)

등록된 구현이 없습니다.

Tasks

Adversarial Attack Adversarial Robustness

Laplace-Bridged Randomized Smoothing for Fast Certified Robustness

2026-04-27 · Miao Lin, MD Saifur Rahman Mazumder, Feng Yu, Daniel Takabi 외 arxiv

Randomized Smoothing (RS) offers formal $\ell_2$ guarantees for arbitrary base classifiers but faces two key practical bottlenecks: (i) it often relies on noise-augmented training to achieve nontrivial certificates, whic…

Error estimates for spectral convergence of the graph Laplacian on random geometric graphs towards the Laplace--Beltrami operator

2018-01-30 · Nicolas Garcia Trillos, Moritz Gerlach, Matthias Hein, Dejan Slepcev

We study the convergence of the graph Laplacian of a random geometric graph generated by an i.i.d. sample from a $m$-dimensional submanifold $M$ in $R^d$ as the sample size $n$ increases and the neighborhood size $h$ ten…

Analysis and algorithms for $\ell_p$-based semi-supervised learning on graphs

2019-01-15 · Mauricio Flores, Jeff Calder, Gilad Lerman

This paper addresses theory and applications of $\ell_p$-based Laplacian regularization in semi-supervised learning. The graph $p$-Laplacian for $p>2$ has been proposed recently as a replacement for the standard ($p=2$) …

General Classification

Geometric Graph Filters and Neural Networks: Limit Properties and Discriminability Trade-offs

2023-05-29 · Zhiyang Wang, Luana Ruiz, Alejandro Ribeiro

This paper studies the relationship between a graph neural network (GNN) and a manifold neural network (MNN) when the graph is constructed from a set of points sampled from the manifold, thus encoding geometric informati…

Graph Neural Network Point Cloud Classification

From random walks to distances on unweighted graphs

2015-11-02 · NeurIPS 2015 12 · Tatsunori B. Hashimoto, Yi Sun, Tommi S. Jaakkola

Large unweighted directed graphs are commonly used to capture relations between entities. A fundamental problem in the analysis of such networks is to properly define the similarity or dissimilarity between any two verti…

Clustering