Graph Neural Networks: Mathematical Foundations and Algorithmic Frameworks

Abstract

Graph neural networks (GNNs) extend deep learning to data supported on graph-structured domains. Motivated by problems in chemistry, social networks, recommender systems and relational reasoning, GNN architectures have matured into a rigorous subfield combining graph theory, spectral analysis and approximation theory. This paper offers a mathematical review of GNN foundations. We begin with spectral formulations based on the graph Laplacian, derive the message-passing neural network framework, and survey expressive-power results including the equivalence of 1-WL colour refinement and standard message-passing. Representative architectures GCN, GraphSAGE, GAT, and GIN are compared on citation-network benchmarks. The paper closes with a discussion of over-smoothing, long-range dependency, and recent higher-order extensions.