Lecture Notes on Verifying Graph Neural Networks

Basic Information

• Paper ID: 2510.11617
• Title: Lecture Notes on Verifying Graph Neural Networks
• Author: François Schwarzentruber (ENS de Lyon)
• Classification: cs.LO (Logic in Computer Science), cs.LG (Machine Learning)
• Publication Date: October 14, 2025
• Paper Link: https://arxiv.org/abs/2510.11617

Abstract

These lecture notes first review the connections between graph neural networks, the Weisfeiler-Lehman test, first-order logic, graded modal logic, and other logical systems. Subsequently, a modal logic is proposed in which counting modalities appear in linear inequalities to address graph neural network verification tasks. An algorithm for the satisfiability problem of this logic is described, inspired by tableau methods from traditional modal logic and extended with reasoning over quantifier-free fragments of Boolean algebra and Presburger arithmetic.

Research Background and Motivation

Problem Context

Graph neural networks (GNNs) have been widely applied in social network recommendations, knowledge graphs, chemical molecular analysis, drug discovery, and numerous other domains. However, the verification of GNNs faces significant challenges:

1. Expressiveness Limitations: The expressiveness of GNNs is constrained by the 1-WL (Weisfeiler-Lehman) test, making it impossible to distinguish certain non-isomorphic graphs
2. Verification Task Complexity: The need to verify whether GNNs satisfy specific specifications, such as safety and correctness properties
3. Insufficient Theoretical Foundation: Lack of systematic logical frameworks to describe and verify GNN behavior

Research Motivation

• Practical Requirements: In safety-critical applications, ensuring the reliability and correctness of GNNs is essential
• Theoretical Gaps: Existing verification methods lack a unified logical theoretical foundation
• Technical Challenges: Handling aggregation operations and counting constraints in GNNs

Core Contributions

1. Establishing Theoretical Connections: Systematically elucidates the deep connections between GNNs, the Weisfeiler-Lehman test, and logical systems (FO, FOC, GML)
2. Proposing K# Logic: Designs a novel modal logic K# capable of expressing counting and aggregation operations in GNNs
3. Algorithm Design: Develops a PSPACE algorithm for the satisfiability problem of K# logic, based on tableau methods and QFBAPA reasoning
4. Complexity Analysis: Establishes computational complexity bounds for GNN verification problems under different activation functions
5. Practical Framework: Provides a complete framework for reducing GNN verification tasks to logical satisfiability problems

Methodology Details

Task Definition

The core tasks of GNN verification include:

• Satisfiability: Given a GNN N, does there exist an input that produces a positive output?
• Specification Verification: Does the GNN satisfy a given logical specification φ?
• Equivalence Checking: Are two GNNs equivalent on all inputs?

K# Logic Architecture

Syntax Definition

φ ::= p | ¬φ | φ ∨ φ | ξ ≥ 0
ξ ::= c | 1φ | #φ | ξ + ξ | c × ξ

Semantic Definition

• 1φ: Evaluates to 1 if φ is true, 0 otherwise
• #φ: Counts the number of successor nodes satisfying φ
• Linear Expressions: Support addition and scalar multiplication

Key Features

1. Expressiveness: K# logic contains graded modal logic (GML) as a subset
2. Correspondence: Admits polynomial-time bidirectional translation with truncReLU-GNNs
3. Counting Constraints: Capable of expressing complex counting relationships and aggregation operations

GNN-K# Correspondence

From K# to GNN

tr(xi = 1) = xi
tr(¬φ) = 1 - truncReLU(tr(φ))
tr(φ ∧ ψ) = truncReLU(tr(φ) + tr(ψ) - 1)
tr(#φ) = agg(tr(φ))

From GNN to K#

tr'(truncReLU(ϑ)) = 1tr'(ϑ)≥1
tr'(agg(ϑ)) = #(tr'(ϑ) ≥ 1)

Satisfiability Algorithm

QFBAPA Foundation

Employs quantifier-free Boolean algebra and Presburger arithmetic (QFBAPA) to handle counting constraints:

• Venn Diagram Technique: Transforms set expressions into region variables
• Carathéodory Bound: Proves that only polynomial-sized numbers of non-zero regions need be considered
• NP Complexity: QFBAPA satisfiability problem lies within NP

K# Tableau Algorithm

procedure satK#(Γ)
  Process Boolean rules and 1φ constructions
  Extract linear inequality constraints S
  Guess non-zero regions B ⊆ {0,1}d, |B| ≤ 2d log₂(4d)
  Replace #ψᵢ with ∑ρ∈B|ρᵢ=1 sρ
  Check QFPA satisfiability
  Recursively verify each region

Experimental Setup

Theoretical Verification

The paper primarily conducts theoretical analysis through constructive proofs to verify:

1. Correctness: Algorithm correctness and completeness
2. Complexity: Time and space complexity bounds
3. Expressiveness: Expressiveness relationships among different logical fragments

Complexity Results

Experimental Results

Main Theoretical Results

Expressiveness Relationships

• cr(G,u) = cr(G',u') ⟺ G,u and G',u' satisfy the same GML formulas
• GML ⊆ K# ⊆ FOC₂
• K# is strictly stronger than FO

Complexity Bounds

1. K# Satisfiability: PSPACE-complete
2. truncReLU-GNN Verification: PSPACE-complete
3. ReLU-GNN Verification: NEXPTIME-complete
4. Global Readout: Leads to undecidability (undirected graph case)

Algorithm Efficiency

• Space Complexity: Polynomial space
• Region Count: At most 2d log₂(4d) non-zero regions
• Translation Overhead: Polynomial time (integer weight case)

Technical Insights

Weisfeiler-Lehman Connection

• Color refinement algorithms capture the essential computational patterns of GNNs
• The k-WL hierarchy corresponds to the expressiveness of different-order GNNs
• Modal logic provides a natural language for describing this hierarchical structure

Counting Constraint Handling

• QFBAPA provides an effective framework for processing aggregation operations
• Venn diagram techniques simplify complex counting constraints to linear programming
• Carathéodory bounds ensure polynomial space complexity of the algorithm

Related Work

GNN Theoretical Foundations

• Expressiveness: Xu et al. (2019), Morris et al. (2019) established connections between GNNs and WL tests
• Logical Characterization: Barceló et al. (2020) first established correspondences between GNNs and logic
• Verification Methods: Benedikt et al. (2024) proposed decision procedures but lacked a unified framework

Modal Logic Verification

• Traditional Methods: Decision procedures for modal logic based on tableau methods
• Counting Extensions: Satisfiability algorithms for graded modal logic
• Complexity Theory: Complexity analysis of various modal logic fragments

Neural Network Verification

• SMT Methods: Using SMT solvers to verify neural network properties
• Abstract Interpretation: Analyzing network behavior through abstract domains
• Symbolic Execution: Symbolically exploring network execution paths

Conclusions and Discussion

Main Conclusions

1. Theoretical Unification: Establishes a unified theoretical framework connecting GNNs, WL tests, and logical systems
2. Algorithmic Contributions: Provides effective algorithms for GNN verification with optimal complexity
3. Expressiveness: K# logic precisely captures the computational power of truncReLU-GNNs
4. Complexity Separation: Different activation functions lead to significantly different verification complexities

Limitations

1. Activation Function Restrictions: Main results focus on truncReLU; ReLU cases are more complex
2. Quantification Issues: Rational number weights require exponentially large common denominators
3. Implementation Complexity: Practical implementation of algorithms still faces efficiency challenges
4. Application Scope: Primarily targets node classification tasks; graph-level tasks require additional considerations

Future Directions

1. Extending Activation Functions: Investigating verification methods for more general activation functions
2. Algorithm Optimization: Improving practical performance and scalability of algorithms
3. Tool Development: Developing practical GNN verification tools
4. Application Extension: Extending to more GNN architectures and task types

In-Depth Evaluation

Strengths

1. Theoretical Depth: Establishes profound theoretical connections, filling important theoretical gaps
2. Methodological Innovation: The design of K# logic cleverly balances expressiveness and decidability
3. Algorithm Elegance: The combination of tableau methods and QFBAPA is both natural and efficient
4. Complete Results: Provides comprehensive complexity analysis and correspondence proofs
5. Educational Value: As lecture notes, the structure is clear and suitable for learning and teaching

Weaknesses

1. Missing Experimental Validation: Lacks practical experimental verification and performance evaluation
2. Implementation Details: Insufficient discussion of specific implementation and optimization strategies
3. Application Cases: Lacks concrete application scenarios and case studies
4. Tool Support: No provision of available verification tools or prototype systems

Impact

1. Theoretical Contribution: Establishes a solid theoretical foundation for GNN verification research
2. Methodological Inspiration: Provides important methodological guidance for subsequent research
3. Educational Value: As excellent teaching material, contributes to talent cultivation in the field
4. Practical Prospects: Although theoretically strong, points the direction for practical tool development

Applicable Scenarios

1. Safety-Critical Systems: GNN applications requiring rigorous verification
2. Theoretical Research: Theoretical analysis of GNN expressiveness and complexity
3. Teaching and Training: Teaching of graph neural networks and logical verification
4. Tool Development: Theoretical foundation for GNN verification tools

References

The paper cites 65 important references, covering:

• GNN theoretical foundations (Grohe 2021, Barceló et al. 2020)
• Weisfeiler-Lehman test (Morris et al. 2019, Xu et al. 2019)
• Modal logic (Blackburn et al. 2001, Tobies 1999)
• Complexity theory (Grädel et al. 1997, Kuncak and Rinard 2007)
• Neural network verification (Benedikt et al. 2024, Haase and Zetzsche 2019)

Overall Assessment: This is an excellent paper that combines theoretical depth with educational value. It not only addresses important theoretical problems in GNN verification but also establishes a solid foundation for subsequent research and practical applications. While lacking experimental validation, the significance of its theoretical contributions is undeniable.