mlsanityData to 7 Oct 2026

Scalable Verification of GNN-based Job Schedulers

arXiv 2203.03153 ↗First posted 7 Mar 2022cs.AIcited by 18

Not on the map. Why?

Abstract (arXiv)

Recently, Graph Neural Networks (GNNs) have been applied for scheduling jobs over clusters, achieving better performance than hand-crafted heuristics. Despite their impressive performance, concerns remain over whether these GNN-based job schedulers meet users' expectations about other important properties, such as strategy-proofness, sharing incentive, and stability. In this work, we consider formal verification of GNN-based job schedulers. We address several domain-specific challenges such as networks that are deeper and specifications that are richer than those encountered when verifying image and NLP classifiers. We develop vegas, the first general framework for verifying both single-step and multi-step properties of these schedulers based on carefully designed algorithms that combine abstractions, refinements, solvers, and proof transfer. Our experimental results show that vegas achieves significant speed-up when verifying important properties of a state-of-the-art GNN-based scheduler compared to previous methods.

Key facts. Cited by 18 papers in the map (data through 7 Oct 2026). Builds on 45 of its 77 references that are in the map. First posted on arXiv 7 Mar 2022.

Builds on

45 of 77 references.

References · 45

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2013Intriguing properties of neural networkscited by 5,114
  3. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  4. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  5. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,133
  6. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 751
  7. 2017Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networkscited by 739
  8. 2017Provable defenses against adversarial examples via the convex outer adversarial polytopecited by 564
  9. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
  10. 2018Efficient Neural Network Robustness Certification with General Activation Functionscited by 439
  11. 2016Learning Convolutional Neural Networks for Graphscited by 314
  12. 2016Safety Verification of Deep Neural Networkscited by 262
33 more
  1. 2019Adversarial Attacks on Graph Neural Networks via Meta Learningcited by 261
  2. 2018Towards Fast Computation of Certified Robustness for ReLU Networkscited by 254
  3. 2017Formal Verification of Piece-Wise Linear Feed-Forward Neural Networkscited by 241
  4. 2018Formal Security Analysis of Neural Networks using Symbolic Intervalscited by 185
  5. 2020Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifierscited by 183
  6. 2018Semidefinite relaxations for certifying robustness to adversarial examplescited by 178
  7. 2018Efficient Formal Safety Analysis of Neural Networkscited by 165
  8. 2019Branch and Bound for Piecewise Linear Neural Network Verificationcited by 138
  9. 2018Learning Scheduling Algorithms for Data Processing Clusterscited by 133
  10. 2019A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networkscited by 124
  11. 2017Output Reachable Set Estimation and Verification for Multi-Layer Neural Networkscited by 79
  12. 2020Towards More Practical Adversarial Attacks on Graph Neural Networkscited by 76
  13. 2020Verification of Deep Convolutional Neural Networks Using ImageStarscited by 75
  14. 2021Lyapunov-stable neural-network controlcited by 66
  15. 2019Certifiable Robustness to Graph Perturbationscited by 62
  16. 2020Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbationcited by 57
  17. 2021Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learningcited by 52
  18. 2018CNN-Cert: An Efficient Framework for Certifying Robustness of Convolutional Neural Networkscited by 50
  19. 2020The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verificationcited by 50
  20. 2019Neural Network Branching for Neural Network Verificationcited by 45
  21. 2020Scaling Polyhedral Neural Network Verification on GPUscited by 43
  22. 2019Perfectly Parallel Fairness Certification of Neural Networkscited by 42
  23. 2018Formal Verification of Neural Network Controlled Autonomous Systemscited by 41
  24. 2019Optimization and Abstraction: A Synergistic Approach for Analyzing Neural Network Robustnesscited by 40
  25. 2019Fastened CROWN: Tightened Neural Network Robustness Certificatescited by 39
  26. 2020Parallelization Techniques for Verifying Neural Networkscited by 36
  27. 2020Reachable Polyhedral Marching (RPM): A Safety Verification Algorithm for Robotic Systems with Deep Neural Network Componentscited by 36
  28. 2021Towards Scalable Verification of Deep Reinforcement Learningcited by 33
  29. 2020Improving Neural Network Verification through Spurious Region Guided Refinementcited by 30
  30. 2017Deep Neural Networks as 0-1 Mixed Integer Linear Programs: A Feasibility Studycited by 25
  31. 2020Fast Geometric Projections for Local Robustness Certificationcited by 21
  32. 2020Scalable Polyhedral Verification of Recurrent Neural Networkscited by 20
  33. 2020Online Learning Demands in Max-min Fairnesscited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 4; 2023: 1; 2024: 5; 2025: 1; 2026: 7.

18 papers.

Sort:

By area:

  1. 2024Marabou 2.0: A Versatile Formal Analyzer of Neural Networkscited by 81
  2. 2022The Third International Verification of Neural Networks Competition (VNN-COMP 2022): Summary and Resultscited by 39
  3. 2022VeriX: Towards Verified Explainability of Deep Neural Networkscited by 30
  4. 2023Provably Bounding Neural Network Preimagescited by 28
  5. 2022Toward Certified Robustness Against Real-World Distribution Shiftscited by 16
  6. 2024Verifying message-passing neural networks via topology-based bounds tighteningcited by 10
  7. 2024Formal Verification of Graph Convolutional Networks with Uncertain Node Features and Uncertain Graph Structurecited by 8
  8. 2022A Scalable, Interpretable, Verifiable & Differentiable Logic Gate Convolutional Neural Network Architecture From Truth Tablescited by 4
  9. 2024AutoSpec: Automated Generation of Neural Network Specificationscited by 2
  10. 2025Bridging Efficiency and Safety: Formal Verification of Neural Networks with Early Exitscited by 1
  11. 2026The FABRIC Strategy for Verifying Neural Feedback Systemscited by 1
  12. 2024Specification Generation for Neural Networks in Systemscited by 0
6 more
  1. 2026The Luna Bound Propagator for Formal Analysis of Neural Networkscited by 0
  2. 2026Analyzing Symbolic Properties for DRL Agents in Systems and Networkingcited by 0
  3. 2026Towards Verified and Targeted Explanations through Formal Methodscited by 0
  4. 2026Neural Network Verification using Partial Multi-Neuron Relaxationcited by 0
  5. 2026NNV3: Expanding Neural Network Verification to New Architectures and Domainscited by 0
  6. 2026Reachability-Based Formal Verification of Graph Neural Networks with Node and Edge Featurescited by 0