SDM 25' Tutorial

Graph Neural Networks (GNNs) have achieved strong empirical success, yet their theoretical foundations remain fragmented. Early GNNs were rooted in spectral graph theory, while later models were developed from spatial (message-passing) perspectives, making direct comparisons difficult. This tutorial provides a concise theoretical overview of GNNs and introduces a unifying framework that bridges spectral and spatial approaches. By drawing on tools from approximation theory and graph analysis, we clarify the connections between these paradigms and offer insights for understanding and selecting GNN models.