Graph Learning Meets Theoretical Computer Science 2025
2025-08-11..2025-08-15
Berkeley, United States
[Dynamic Graphs and Algorithm Design (Simons Institute, 2023), Foundations of Machine Learning Boot Camp 2017, Frontiers of Deep Learning 2019, Modern Paradigms in Generalization Boot Camp 2024, Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020), Foundations of Data Science Boot Camp 2018]
who it's for
graph learning researchers, theoretical computer scientists, machine learning researchers, geometric deep learning researchers, optimization and algorithm designers, statistical learning theorists
topics
message-passing GNNs vs k-WL nets; subgraph GNNs (node-rooted bags); graph transformers and attention scaling; graphons and cut distance convergence; homomorphism counts and indistinguishability; equivariance via irreducible representations; local graph limits and sampling GNNs; size (OOD) generalization and algorithmic alignment; Szemeredi regularity lemma for graphs; VC and Rademacher bounds for GNNs; universality of DeepSet/PointNet variants; multisets-to-vectors mappings
| title | author | length |
|---|---|---|
| Boot Camp on Graph Learning | Ameya Velingker, Haggai Maron, Christopher Morris | 01h 39m |
Half-day boot camp lays out concrete tradeoffs: message‑passing GNNs run in O(nodes+edges) but provably match 1‑WL and miss many cycle/subgraph distinctions… | ||
| Boot camp on invariances in graph learning | Nadav Dym, Risi Condor, Hannah Lawrence | 01h 29m |
Equivariance work focuses on concrete constraints and recipes: use representation theory, irreducible representations and Schur’s lemma to force linear layers… | ||
| Boot camp on graphons for graph learning | Luana Rubini Ruiz | 01h 28m |
Introduces graphons rigorously, defines homomorphism density and cut distance, proves graphs sampled from a graphon converge in cut distance, and builds… | ||
| Boot camp on graph foundations models | Mikhail Galkin | 01h 16m |
Claims that pretrained graph models give real transfer: a relation-graph encoder + labeling tricks (NBFNet, motif hierarchy) yields zero-shot link prediction… | ||
| Boot camp on logic and graph learning | Pablo Barcelo | 01h 30m |
Boot camp defines node-colored graphs, fixes GNNs that use sum aggregation with bias and one-hot inputs, and gives precise expressiveness claims: node-level… | ||
| Homomorphism Indistinguishability | Tim Seppelt | 58m |
Survey of concrete claims and tools: homomorphism counts from trees coincide with indistinguishability by message‑passing GNNs; counts from cycles recover… | ||
| Lightning Talks | YUXIN MA | 58m |
Models that accept variable sizes generalize across sizes only when two concrete conditions hold: task-model alignment (the target function is uniformly… | ||
| A Local Graph Limits Perspective on Sampling-Based GNNs | Yeganeh Alimohammadi | 39m |
Uses the Benjamini–Schramm limits framework to prove that, under mild assumptions (local samplers, Lipschitz loss), parameters trained on many small fixed‑size… | ||
| Graph Machine Learning & Random Graph Models | Samuel Vaiter | 54m |
Describes a random geometric latent-space model with bounded, piecewise-Lipschitz kernel and lower-bounded degree on a compact metric space, uses a sampling… | ||
| Boot camp on generalization theory for graph learning | Antonios Vasileiou, Thien Le | 01h 40m |
VC bounds tie capacity to combinatorial expressivity, provably equating VC dimension to the number of 1WL equivalence classes for MPNNs on n‑node graphs… | ||
| Szemerédi Regularity Lemma in Graph Machine Learning | Ron Levie | 54m |
Uses the weak Szemerédi regularity lemma to map graphs with node features into graphons and define a cut distance metric that makes the space compact, yields… | ||
| Size (OOD) Generalization of Neural Models via Algorithmic Alignment | Yusu Wang | 59m |
Claims a provable path to size generalization: combining algorithmic alignment with L0 sparsity and a carefully curated small training set yields provable… | ||
| Toward Universal Graph Representations: Foundations and Frontiers of Graph Foundation Models | Bruno Riberio | 01h 01m |
Proposes concrete recipe: create holographic node representations via an expansion map that breaks symmetries (Lanczos-style or GNN-initialized perturbations)… | ||
| Machine learning on point clouds and other varying-size objects | Soledad Villar | 52m |
Defines a new invariant model on point clouds built from Gram-matrix invariants (diagonals, off‑diagonals plus one explicit polynomial f) and proves those… | ||
| Boot camp on CO and graph learning | Andrea Lodi | 01h 32m |
Claims that graph neural networks speed up mixed integer linear programming by imitating strong branching on variables using a bipartite graph representation… | ||
| ML for discrete optimization: Theoretical foundations | Ellen Vitercik | 01h 01m |
Presents two concrete methods with proofs and experiments: a GNN pipeline called MAGNOLIA trains on exponential-time marginal value-to-go labels from tiny… | ||
| Exact Performance Verification of First‑Order Methods in Parametric Convex Optimization | Bartolomeo Stellato | 59m |
A computational framework quantifies finite‑iteration performance of first‑order methods for parametric convex problems by modeling algorithms as fixed‑length… | ||
| Understanding ReLU Networks Through Graph Problems and Polyhedra | Christoph Hertrich | 01h 03m |
Shows exact representability results: continuous piecewise‑linear functions equal maxima of affine pieces via Wang and Sun, so ReLU nets need only log2 depth… | ||
| Recent trends in combinatorial optimization augmented machine learning: A graph learning perspective | Axel Parmentier | 47m |
Describes embedding graph neural networks with a combinatorial optimization layer that predicts arc weights or customer prices and then decodes with MILP or… | ||
| Bootcamp on geometry and graph learning | Anthea Monod | 01h 34m |
Bootcamp surveys concrete math-for-ML results and working code: a Berkovich analytification / polydisc approach gives path-connected non‑Archimedean embeddings… | ||
| Higher order graph neural networks with P-tensors | Risi Kondor | 01h 10m |
Introduces P-tensors as a formalism that enforces permutation equivariance for higher‑order message passing and extends to Schur‑nets to expose local… | ||
| Mathematical connections of some local-to-global expressivity results over geometric graphs and... | Mircea Petrache | 01h 03m |
Claim: running geometric 1-WL on the complete distance graph reconstructs planar point clouds up to isometry after three rounds in 2D by using… | ||
| Mapping multisets to vectors | Nadav Dym | 01h 01m |
Shows that sum/mean/max pooling with piecewise‑linear nets cannot be reliably injective on continuous features, while analytic (non‑polynomial) activations… | ||
| Wrap up and reflection talk | Mathias Niepert | 56m |
Argues that machine learning replaces weeks‑long DFT for small (hundreds of atoms) quantum simulations by training ML interatomic potentials on expensive force… | ||
| nothing matches | ||