Modeling Interactions Between Vertices in Graph Neural Networks

Explore a comprehensive lecture on the expressive power of Graph Neural Networks (GNNs) in modeling interactions between vertices. Delve into the formal characterization of GNNs' ability to model interactions, focusing on the concept of separation rank and the newly introduced walk index. Learn about the theoretical analysis of GNN architectures and their empirical validation using ReLU activation functions. Discover a novel edge sparsification algorithm, Walk Index Sparsification (WIS), designed to preserve GNNs' interaction modeling capabilities while removing input edges. Gain insights into the potential for improving GNNs through theoretical analysis of modeled interactions, and engage with Q&A sessions for deeper understanding.

- Intro
- Expressivity in Graph Neural Networks GNNs
- Overview of Contributions
- Theory: Formalizing Interaction via Separation Rank
- Theory: Analyzed GNN Architecture
- Theory: Characterizing Strength of Modeled Interaction
- Empirical Demonstration on GNNs with ReLU
- Q+A
- Comparison of Edge Sparsification Methods
- Conclusion
- Q+A