Dottorato in DATA SCIENCE

Titolo della tesi: Topological Neural Networks: Mitigating the Bottlenecks of Graph Neural Networks via Higher-Order Interactions

The irreducible complexity of natural phenomena has led Graph Neural Networks to be employed as a standard model to perform representation learning tasks on graph-structured data. While their capacity to capture local and global patterns is remarkable, the implications associated with long-range and higher-order dependencies pose considerable challenges to such models. This work addresses these challenges by starting with the identification of the aspects that negatively impact the performance of graph neural networks in learning representations of events that strongly depend on long-range interactions. In particular, when graph neural networks require to aggregate messages among distant nodes, the message passing scheme performs an over-squashing of an exponentially growing amount of information into static vectors. It is important to notice that for some classes of graphs (i.e., path, tree, grid, ring, and ladder) the underlying connectivity allows messages to travel along edges without encountering significant interference from other paths, thus reducing the growth of information to be linear in the number of messages exchanged. When the underlying graph does not fall into the aforementioned categories, oversquashing arises because the propagation of information happens between nodes that are connected through edges, which induces a computational graph mirroring nodes’ connectivity. This phenomenon causes nodes to become insensitive to information sent from remote parts of the graph. To offer a new perspective for designing architectures that mitigate such bottlenecks, a unified theoretical framework reveals the impact of network’s width, depth, and graph topology on the over-squashing phenomena in message-passing neural networks. The thesis then drifts towards the exploitation of higher-order interactions via Topological Neural Networks. With a multi-relational inductive bias, topological neural networks propagate messages through higher-dimensional structures, effectively providing shortcuts or additional routes for information flow. With this construction, the underlying computational graph is no longer coupled with the input graph structure, thus mitigating the aforementioned bottlenecks while accounting also for higher-order interactions. Inspired by the masked self-attention mechanism developed in Graph Attention Networks alongside the rich connectivity provided by simplicial and cell complexes, two distinct attentional architectures are proposed: Simplicial Attention Networks and Cell Attention Networks. The rationale behind these architecture is to leverage the extended notion of neighbourhoods provided by the particular arrangement of groups of nodes within a simplicial or cell complex. In particular, these topological attention networks exploit the upper and lower adjacencies of the underlying complex to design anisotropic aggregations able to measure the importance of the information coming from different regions of the domain. By doing so, they capture dependencies that conventional Graph Neural Networks might miss. Finally, a communication scheme between higher-order structures is introduced with Enhanced Cellular Isomorphism Networks, which augment topological message passing schemes by letting all the cells of a cell complex receive messages from their lower neighbourhood. This upgrade enables direct interactions among node groups within a cell complex, specifically arranged in ring-like structures. This augmented scheme offers more comprehensive representation of higher-order and long-range interactions, demonstrating very high performance on large-scale and long-range benchmarks.