Mathematical Science Team Seminar(Talk by Matthieu Cordonnier, Université Grenoble Alpes).

This is an online seminar. Registration is required.
【Team】Mathematical Science Team
【Date】2025/January/15(Wed) 16:00-17:00(JST)
【Speaker】Matthieu Cordonnier, Université Grenoble Alpes

Title: Contribution to the theory of graph neural networks on large random graphs.

Abstract:
Graphs effectively represent various data types, such as molecules, epidemic propagation, or networks. Unlike Euclidean data like digital images, graph data comprises two components: the graph's irregular structure governing information flow and the node-specific data, termed the signal. Machine learning on graphs involves two tasks: graph-level tasks, focusing on global attributes (common for small graphs with available databases), and node-level tasks, like community detection, which are more relevant for large graphs (favoring direct methods like spectral clustering). Despite this distinction, models must utilize both the graph structure and the signal.
Graph neural networks (GNNs), specialized deep learning architectures, address graph data processing. A single GNN can handle graphs of varying sizes, transitioning from node to graph tasks with minimal changes. Through "message passing," GNNs exploit dual information by propagating node signals via the graph structure. However, GNN theory remains underexplored, with phenomena like untrained GNNs performing comparably to trained ones. Current theory, emphasizing combinatorial approaches and graph-level tasks, is less suited to large graphs and node-level tasks.
This work contributes to understanding GNNs for large graphs using a statistical approach. Large graphs and their signals are modeled via latent space random graphs, where nodes are drawn from an unknown space and connected by a kernel. Signals are sampled from functions on this space. The first contribution establishes that "message passing" GNNs on increasing random graphs converge to a continuous counterpart, transitioning between discrete and continuous realms. The second contribution proposes a new notion of expressivity for GNNs on large random graphs based on this convergence.