Information propagation dynamics in Deep Graph Networks

Graphs are a highly expressive abstraction for modeling entities and their relations, such as molecular structures, social networks, and traffic networks. Deep Graph Networks (DGNs) have recently emerged as a family of deep learning models that can effectively process and learn such structured information. However, learning effective information propagation patterns within DGNs remains a critical challenge that heavily influences the model capabilities, both in the static domain and in the temporal domain (where features and/or topology evolve). This thesis investigates the dynamics of information propagation within DGNs for static and dynamic graphs, focusing on their design as dynamical systems. With the aim of fostering research in this domain, at first, we review the principles underlying DGNs and their limitations in information propagation, followed by a survey of recent advantages in learning both temporal and spatial information, providing a fair performance comparison among the most popular proposed approaches. The main challenge addressed in this thesis is the limited ability of DGNs to propagate and preserve long-term dependencies between nodes. To tackle this problem, we design principled approaches bridging non-dissipative dynamical systems with DGNs. We leverage properties of global and local non-dissipativity in both temporal and static domain, enabling maintaining a constant information flow rate between nodes. We first exploit dynamical systems with antisymmetric constraints on both spatial and weight domains to achieve graph- and node-wise non-dissipativity. Then, we introduce a DGN that exploits port-Hamiltonian dynamics, thus defining a new message-passing scheme that balances non-dissipative long-range propagation and non-conservative behaviors. We then tackle the task of learning complex spatio-temporal patterns from irregular and sparsely sampled data. Throughout this work, we provide theoretical and empirical evidence to demonstrate the effectiveness of our proposed architectures. In summary, this thesis provides a comprehensive exploration of the intersection between graphs, deep learning, and dynamical systems, providing insights and advancements for the field of graph representation learning and paving the way for more effective and versatile graph-based learning models.