Seminar in Artificial Intelligence - Theoretical Aspects of Machine Learning

Motivation: Ability to learn logically definable concepts from labelled data is a theoretical model of Machine Learning which is explainable by design, and integrates ideas from both logic (especially finite model theory) and PAC Learning.

Overview:

• Shai Ben-David and Shai Shalev-Shwartz. Understanding Machine Learning. Chapter 2,3
• Shai Ben-David Lectures. (youtube-link) Lecture 1,2,3

Papers and topics:

• Kaifu Wang, Efthymia Tsamoura, Dan Roth. On learning latent models with multi-instance weak supervision. Neurips 2024
• Sam Adam-Day, Theodor Mihai Iliant, İsmail İlkan Ceylan. Zero-One Laws of Graph Neural Networks. 2024
• Sam Adam-Day, Michael Benedikt, İsmail İlkan Ceylan, Ben Finkelshtein. Graph neural network outputs are almost surely asymptotically constant. 2024
• Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, Jure Leskovec. GNNExplainer: Generating Explanations for Graph Neural Networks. 2019

Motivation: In active learning, the learning algorithm is allowed to select the data points it wants to see labelled, for example, where it is most uncertain. The goal is to reduce the labelling effort. This is useful in applications where unlabelled data is abundant, yet labels are scarce, such as node classification in social networks, drug discovery, and autonomous driving.

Overview:

• chapter 1 “Automating inquiry” of Burr Settles’ “Active learning” book, 2012.
• introduction and recent research: Rob Nowak and Steve Hanneke - ICML 2019 tutorial (youtube-link)

Papers and topics:

• active learning with comparison queries (Kane, D. M., Lovett, S., Moran, S., & Zhang, J. “Active classification with comparison queries.” FOCS 2017)
• sample complexity in active learning (Maria-Florina Balcan, Steve Hanneke, and Jennifer Wortman Vaughan “The true sample complexity of active learning.” Machine Learning 2010)
• bounded memory active learning (M. Hopkins, D. Kane, S. Lovett & M. Moshkovitz. “Bounded memory active learning through enriched queries.” COLT 2021)
• generalization error bounds (Vincent Menden, Yahya Saleh, and Armin Iske: Bounds on the Generalization Error in Active Learning, arXiv, 2024)

Motivation
Graphons serve as limit objects for large graphs, providing a geometric view of networks. Distances between graphons let us formalize graph convergence, quantify similarity, and study stability of statistics and algorithms. Understanding these metrics is key for estimation, privacy, and learning on graphs.

Overview

• Lovász, Large Networks and Graph Limits (PDF)
• Janson, Graphons, cut norm and distance (PDF)

Papers and topics

• Ron Levie. A graphon-signal analysis of graph neural networks. NeurIPS, 2023
• Daniel Herbst, Stefanie Jegelka. Higher-Order Graphon Neural Networks: Approximation and Cut Distance. ICLR, 2025
• Chen, Ding, d’Orsi, Hua, Liu, Steurer. Private Graphon Estimation via Sum-of-Squares. ACM Symposium on Theory of Computing, 2024
• Abraham, Delmas, Weibel. Probability-graphons: Limits of large dense weighted graphs. ArXiV, 2025
• Ben Finkelshtein, İsmail İlkan Ceylan, Michael Bronstein, Ron Levie. Learning on Large Graphs using Intersecting Communities. NeurIPS, 2024
• Borgs, Christian, Jennifer Chayes, and Adam Smith. Private graphon estimation for sparse graphs. NeurIPS, 2015.

Motivation: Many datastructures have an innate structure that our neural networks should respect. For example the output of a graph neural networks should not change if we permute the vertices (permutation equivariance/invariance).

Overview:

• chapter 8 “equivariant neural networks” of “Deep learning for molecules and materials” by Andrew D. White, 2021. (pdf).
• introduction to equivariance: Taco Cohen and Risi Kondor - Neurips 2020 Tutorial (first half) (slideslive-link)

Papers and topics:

• neural network that can learn on sets (Zaheer, et al. “Deep sets.” NeurIPS 2017)
• learning equivariance from data (Zhou, et al. “Meta-learning symmetries by reparameterization.” ICLR 2021)

Motivation: The family of Graph Neural Differential Equations (GNDEs) extends GNNs to the continuous regime. GNDEs are generally expected to be better at capturing long-range dependencies and fine-grained dynamics in comparison to message-passing GNNs.

Overview:

• Neural (graph) ODEs: Chen, Ricky TQ, et al. “Neural ordinary differential equations.” Advances in neural information processing systems 31 (2018).
• Poli, Michael, et al. “Graph neural ordinary differential equations.” arXiv preprint arXiv:1911.07532 (2019).

Papers and topics:

• Graph Neural diffusion: Chamberlain, Ben, et al. “Grand: Graph Neural Diffusion.” International Conference on Machine Learning. PMLR, 2021.
• GNNs and heat equation: Di Giovanni, Francesco, et al. “Graph Neural Networks as Gradient Flows: understanding graph convolutions via energy.”, TMLR, 2022.
• Graphs and network dynamics: Bick, Christian, and Davide Sclosa. “Dynamical systems on graph limits and their symmetries.” Journal of Dynamics and Differential Equations, 2024.
• Learning on graphs with damped oscillators: Rusch, T. Konstantin, et al. “Graph-coupled oscillator networks.” International Conference on Machine Learning. PMLR, 2022.

Motivation: Machine learning has become a cornerstone of automated synthesis planning in organic chemistry. A key step in this process is reaction prediction. Over the past 15 years, numerous models and architectures (template-based, GNNs, transformers, …) have been developed to address this complex task. Yet, reaction prediction can refer to a range of distinct modeling tasks—such as predicting products, assessing feasibility, or classifying mechanisms. Comparing existing models is often non-trivial, as their assumptions and objectives vary and the boundaries between prediction tasks are often unclear. For instance, a model trained for product prediction may also be applied to assess reaction feasibility. This motivates the exploration of a formal framework that clarifies the relationships between different modeling approaches.

Papers:

• Marwin H. S. Segler, Mike Preuss, and Mark P. Waller. 2018. Planning chemical syntheses with deep neural networks and symbolic AI. Nature 555, 7698 (March 2018)
• Shuan Chen and Yousung Jung. 2022. A generalized-template-based graph neural network for accurate organic reactivity prediction. Nature Machine Intelligence 4, 9 (September 2022)
• Zhengkai Tu and Connor W. Coley. 2022. Permutation Invariant Graph-to-Sequence Model for Template-Free Retrosynthesis and Reaction Prediction. Journal of Chemical Information and Modeling 62, 15 (August 2022)

Motivation: Graphs are a very general structure and can be applied to many areas: molecules and developing medicine, geographical maps, spread of diseases. They can be used to model physical systems and solve partial differential equations. Even images and text can be seen as a special case of graphs. Thus it makes sense to develop neural networks that can work with graphs. GNNs have strong connections to many classical computer science topics (algorithmics, logic, …) while also making use of neural networks. This means that work on GNN can be very theoretical, applied or anything in between.

Overview:

• Veličković, Everything is connected: Graph neural networks, Current Opinion in Structural Biology, 2023
• Sanchez-Lengeling et al., A Gentle Introduction to Graph Neural Networks, distill.pub 2021
• Veličković, Intro to graph neural networks (ML Tech Talks), YouTube, 2021

Papers:

Note: For very long papers we do not expect you to read the entire appendix.

• Baranwal et al., Optimality of Message-Passing Architectures for Sparse Graphs, NeurIPS, 2023
• Zhou et al., Distance-Restricted Folklore Weisfeiler-Leman GNNs with Provable Cycle Counting Power, NeurIPS, 2023
• Zahng et al., A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests, ICML, 2023
• Zhang et al., Rethinking the Expressive Power of GNNs via Graph Biconnectivity, ICLR, 2023
• Lim et al., Sign and Basis Invariant Networks for Spectral Graph Representation Learning, ICLR, 2023
• Huang et al., You Can Have Better Graph Neural Networks by Not Training Weights at All: Finding Untrained GNNs Tickets, LoG, 2022
• Nils M. Kriege, Weisfeiler and leman go walking: Random walk kernels revisited, NeurIPS, 2022
• Zhang et al., Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness, ICLR, 2024
• Franks et al., Weisfeiler-Leman at the margin: When more expressivity matters, arXiv, 2024

Overview:

• Neurosymbolic AI: The 3rd Wave, 2020 (A. Garcez, L. Lamb)
• Neural-Symbolic Cognitive Reasoning, 2009 (A. Garcez, L. Lamb)

Papers and topics:

• find your own topic :) (a starting point can be the survey from L. De Raedt, S. Dumancic, R. Manhaeve, G. Marra. “From Statistical Relational to Neuro-Symbolic Artificial Intelligence”, 2020)
• SAT solving using deep learning
  • D. Selsam, M. Lamm, B. Bünz, P. Liang, D. Dill, L. de Moura. “Learning a SAT Solver from Single-Bit Supervision”, 2019
  • V. Kurin, S. Godil, S. Whiteson, B. Catanzaro. “Improving SAT Solver Heuristics with Graph Networks and Reinforcement Learning”, 2019
  • J. You, H. Wu, C. Barrett, R. Ramanujan, J. Leskovec. “G2SAT: Learning to Generate SAT Formulas”, 2019

Motivation: Regulatory AI explores how technical systems can support accountability, transparency, and compliance in machine learning. The goal is to design models and data pipelines that can be audited, constrained, or certified: turning legal and ethical requirements into computable properties. This connects ML research on robustness, interpretability, and verification with questions of governance and oversight.

Overview:

• Montreal AI Ethics Institute “Series on the regulatory landscape of AI”. (montrealethics.ai)
• NeurIPS 2024 RegML Workshop “Regulatable ML: Towards Bridging the Gaps between Machine Learning Research and Regulations”. (neurips.cc)
• DeepMind blog: “Exploring institutions for global AI governance”, 2023.
  (deepmind.google)

Papers and topics:

• data governance frameworks for frontier AI models (Hausenloy, J., McClements, M. & Thakur, P. “Towards Data Governance of Frontier AI Models.” NeurIPS RegML 2024)
• algorithmic auditing and accountability frameworks (Raji, I. D., Smart, A., White, R., Mitchell, M., Gebru, T. et al. “Closing the AI Accountability Gap: Defining an End-to-End Framework for Internal Algorithmic Auditing.” FAccT 2020)
• tight theoretical bounds on deletion capacity via differential privacy (Huang Y. & Canonne C. L. “Tight Bounds for Machine Unlearning via Differential Privacy.” NeurIPS 2023)
• injecting legal constraints into neural networks (Yang, Z. et al. “Injecting Logical Constraints into Neural Networks via Straight-Through Estimators.” ICML 2022)
• data governance concerns for generative AI systems (Aaronson SA. “Data Disquiet: Concerns about the Governance of Data for Generative AI.” CIGI 2024)