Subgraph-Based Networks for Expressive, Efficient, and Domain-Independent Graph Learning

Explore a conference talk on subgraph-based networks for expressive, efficient, and domain-independent graph learning. Delve into the intricacies of machine learning and signal processing on graphs, presented by Haggai Maron at the Centre International de Rencontres Mathématiques in Marseille, France. Learn about message passing neural networks, color refinement, and the limitations of MPNNs in expressivity. Discover the concept of Equivariant Subgraph Aggregation Networks (ESAN) and how they address expressivity issues. Examine the principles of equivariance, symmetry in sets of subgraphs, and the application of Deep Sets for Symmetric Elements. Investigate subgraph selection policies, stochastic subgraph sampling, and design choices that impact expressivity. Gain insights into experiments conducted and explore Invariant Graph Networks (IGNs) and symmetries of node-based policies. Access this 50-minute talk through CIRM's Audiovisual Mathematics Library, featuring chapter markers, keywords, and enriched content for an enhanced learning experience.

Intro
Learning on graphs
Setup
Message passing Neural Networks
Color refinement (CR)
MPNNs have limited expressivity
Why expressivity matters?
Sets of subgraphs: example
Equivariant Subgraph Aggregation Networks (ESAN)
Equivariance as a design principle
Symmetry for sets of subgraphs
Detour: Deep Sets for Symmetric Elements
Equivariant layer
Subpraph selection policies
Stochastic subgraph sampling
Design choices and expressivity
Experiments
Detour: Invariant Graph Networks (IGNs)
Symmetries of node-based policies