31.07.2025

Teaser image to From Vulnerable to Verified: Exact Certificates Shield Models from Label‑Flipping

From Vulnerable to Verified: Exact Certificates Shield Models From Label‑Flipping

MCML Research Insight - With Lukas Gosch, Stephan Günnemann and Debarghya Ghoshdastidar

Machine‑learning models can be undermined before training even starts. By silently altering a small share of training labels - marking “spam” as “not‑spam,” for instance - an attacker can cut accuracy by double‑digit percentages.

The paper “Exact Certification of (Graph) Neural Networks Against Label Poisoning” by MCML Junior Member Lukas Gosch, PIs Stephan Günnemann and Debarghya Ghoshdastidar and collaborator Mahalakshmi Sabanayagam, introduces the first exact guarantees that a neural network will remain stable under a prescribed number of label flips. Although demonstrated on graph‑neural networks (GNNs), the method applies to any sufficiently wide neural network.


How the Certification Works

Illustration of the label-flipping certificate

Figure 1: Illustration of the label-flipping certificate

  • Neural‑tangent view. In the wide‑network limit, training behaves like a support‑vector machine using the network’s neural tangent kernel (NTK).
  • Single‑level reformulation. Substituting this NTK model allows to convert the attacker‑versus‑learner game for certification into one optimization problem.
  • Mixed‑integer linear program. That problem is expressed as a mixed‑integer linear program whose solution yields (i) sample‑wise certificates for individual test nodes and (ii) collective certificates for the entire test set.

What Experiments Show

Certified ratios

Figure 2: Certified ratios (the share of test‑set predictions that the certificate proves cannot be overturned even if an attacker flips up to a fraction of the training labels) of selected architectures as calculated with the sample-wise and collective certificate on the Cora-MLb dataset.

  • No universal best architecture. The most robust GNN depends on the data set.
  • Design choices matter. Linear activations improve robustness, while deeper architectures often weaken it.
  • A robustness plateau. Collective certificates reveal a flattening of vulnerability at medium attack budgets - an effect not noted before (see Figure 2).

«Machine learning models are highly vulnerable to label flipping, i.e., the adversarial modification (poisoning) of training labels to compromise performance.»


Lukas Gosch et al.

MCML Junior Members

Practical Implications

Because the approach relies only on the NTK, it extends to standard (non‑graph) wide neural networks, giving practitioners the first provable defence against label poisoning in deep learning.


«There is no silver bullet: robustness hierarchies of GNNs are strongly data dependent.»


Lukas Gosch et al.

MCML Junior Members

Key Takeaway

Exact certification shifts robustness from a best‑effort practice to a provable property. For anyone concerned about poisoned training data, this work provides a clear path toward verifiably trustworthy machine‑learning models.


Interested in Exploring Further?

Published as a spotlight presentation at at the A* conference ICLR 2025, you can explore the full paper—including proofs, algorithmic details, and additional experiments—and find the open-source code on GitHub.

A* Conference
M. Sabanayagam • L. Gosch • S. Günnemann • D. Ghoshdastidar
Exact Certification of (Graph) Neural Networks Against Label Poisoning.
ICLR 2025 - 13th International Conference on Learning Representations. Singapore, Apr 24-28, 2025. Spotlight Presentation. URL GitHub

Share Your Research!


Get in touch with us!

Are you an MCML Junior Member and interested in showcasing your research on our blog?

We’re happy to feature your work—get in touch with us to present your paper.

#blog #research #guennemann

Related

Link to Enkelejda Kasneci: The Real Value of AI in Education Is More Time for Humans

17.11.2026

Enkelejda Kasneci: The Real Value of AI in Education Is More Time for Humans

Enkelejda Kasneci explores how AI can provide personalized learning support while keeping human interaction and student agency at the center.

Read more
Link to One Toolbox for Many Kinds of Uncertainty

12.11.2026

One Toolbox for Many Kinds of Uncertainty

MCML researchers introduce probly, a unified Python package for uncertainty-aware machine learning, presented orally at NeurIPS 2026.

Read more
Link to Outstanding Paper Award at EMNLP 2026 for Work on Accent Bias in Audio Language Models

09.11.2026

Outstanding Paper Award at EMNLP 2026 for Work on Accent Bias in Audio Language Models

A paper co-authored by MCML PI Valentin Hofmann on accent bias in audio language models won an Outstanding Paper Award at EMNLP 2026.

Read more
Link to Best Thesis Award for Sohir Maskey

06.11.2026

Best Thesis Award for Sohir Maskey

Former MCML Junior Member Sohir Maskey received the Best Thesis Award of the DFG Priority Programme 2298 for his PhD on graph neural networks.

Read more
Tiny logo
Link to MCML at CIKM 2026

06.11.2026

MCML at CIKM 2026

MCML researchers are represented with 1 paper at CIKM 2026.

Read more
Back to Top