Graph Neural Networks: Modeling Interactions Between Vertices Through Walk Index Analysis

Explore a one-hour lecture on Graph Neural Networks (GNNs) and their capacity to model vertex interactions, delivered by PhD candidate Noam Razin from Tel Aviv University. Dive into a theoretical analysis of GNNs' expressive power, focusing on how they model interactions between graph vertices through the concept of separation rank. Learn about the walk index, a crucial graph-theoretical characteristic that determines interaction modeling capabilities, and discover a novel edge sparsification algorithm called Walk Index Sparsification (WIS). Understand how WIS efficiently preserves GNNs' interaction modeling abilities while removing edges, demonstrating superior performance in prediction accuracy compared to alternative methods. The lecture, presented at HUJI Machine Learning Club, includes collaborative research findings with Tom Verbin and Nadav Cohen, offering valuable insights for those interested in deep learning theory and graph neural networks.