Temporal Graph Processing and Pooling in Graph Neural Networks

Graph Neural Networks (GNNs) have emerged as a superior technique for handling graph-based data, outperforming traditional methods in a multitude of domains. Indeed, the unique, non-Euclidean structure of graph data introduces specific challenges that complicate the use of standard neural network methodologies. This thesis tackles two important issues: the integration of temporal dynamics into graph structures and the reduction of dimensionality necessary for developing truly deep neural architectures. The first part of this thesis presents a thorough review and taxonomy of existing Graph Neural Network models that handle temporal graphs, detailing their applications in various real-world scenarios. Additionally, it presents a universal approximation theorem for a specific class of temporal GNNs. The second part delves into strategies for graph dimensionality reduction via hierarchical pooling methods. This exploration includes an analysis of how these pooling operators affect the overall expressive power of GNNs. In particular, sufficient conditions for the pooling operator to maintain and even enhance the expressive power of GNNs are presented. By addressing these advanced concepts, the thesis aims to deepen the understanding of GNN optimization for dynamic and complex graph-based applications, setting a foundation for future research and application improvements in the field.