Swiss Ai Research Overview Platform

HORD GNN: Higher-Order Relations and Dynamics in Graph Neural Networks

Complex biological, man-made systems and social relationships can be formalized as graphs (networks), with graphs being rich representations accounting for both structural and functional dependencies (edges, links) that exist among entities (nodes) and compose the networked system. Within this vast application framework, machine learning tools can be applied, boosted by the availability of large -and heterogeneous- data streams and unprecedented computational capabilities. By making explicit functional dependencies existing among entities as well as assigning mixed numerical and categorical information to nodes and edges, we take full advantage of prior knowledge about the problem as relational inductive biases. As proven by the literature, this setup becomes beneficial to the inference engine addressing the application needs, in terms of both accuracy and efficiency. It follows that machine learning architectures have evolved and have been suitably extended to deal with sequences of graphs, though most of the current research has focused on independent graphs drawn from the same probability distribution (i.i.d.) with a fixed set of nodes and a known topology defined by binary relations. Not rarely, these amenable hypotheses are inadequate in complex biological setups and man-made systems where functional dependencies among the different entities are latent and change over time. Extension to general high-order time-evolving interactions in terms of spatiotemporal dynamics (e.g., those associated with epidemic diffusions) or to instances where dependencies are latent and must be discovered from data (like those modeling particle collision jets) urge for major research attention. As such, addressing these two aspects represents the major goals of this proposed HORD GNN project. More in detail, the project objective is twofold and will result in three research lines. The first objective aims at overcoming the assumption that relations and interactions are fully observable, i.e., that the graph is known a priori. This pushes the research to consider (research line 1) advanced hypergraph-based representations and methods proposed to account for high-order latent relations. Suitable data representations and graph learning algorithms based on hypergraphs will be investigated. Then, the focus will be on the definition of a statistically sound processing framework, ultimately leading to grounded, effective, and efficient methods. Within this research line, we will also address embedding techniques with algorithmic relational inductive biases to map hypergraphs into vector embeddings that allow reconstructing the underlying graph representation whenever needed in the processing pipeline. A reference, high societal impact, application on power consumption forecasting in smart power grids will be considered, with a graph learning methodology to exploit latent dependencies among consumption patterns in the grid. The second objective focuses on accounting for the temporal aspect with graph state-space models where the state of a dynamical system is represented in the form of a (hyper)graph. Within this frame, research line 2 aims at advancing the state of the art to produce predictive models where states and -optionally- inputs are (hyper)graphs either given by the application or learned from spatiotemporal relations observed in the data. This research requests extension and redefinition of mathematical operators -standard for vector data-, but no counterpart exists for graphs dealing with multiplex and hypergraph structures, ultimately leading to Graph Kolmogorov-Wiener filters, Graph Kalman Filters, and suitable extensions to nonlinear graph predictive models. A reference application involves the study of macroscopic brain dynamics through EEG signals. Research line 3 covers aspects of both objectives from a different perspective and aims at providing a novel Reinforcement Learning framework for learning composable policies to solve control problems in Markov Decision Processes where states, and eventually policies, are represented as (hyper)graphs capturing the structure of the system at different abstraction levels. We will study the expressive power and transferability of graph representations in this context, both in terms of value function approximation and policy learning. Then, we will exploit the compositionality of graph representations to design a novel algorithmic framework for hierarchical reinforcement learning where systems will be represented as multilayered graphs of interacting sub-modules. The proper hierarchy (graph) of controllers can be fixed by the designer or, again, learned to maximize reward accumulation. Finally, we will address the setting where the structure of the system under analysis can change over time. The reference application involves control of physical systems such as musculoskeletal models in the Learning to run competitions and the ones in the DeepMind control suite. I strongly believe that the proposed research plan will produce groundbreaking results, hence advancing this field to an unprecedented level by providing theoretical results and grounding methodological achievements; open-source Python libraries will be provided to permit entrepreneurs, practitioners, and researchers to take full advantage of public research outcomes.

**Last updated:**20.02.2023