Abstract:
Graph neural networks (GNNs) are effective at learning representations from network data but face challenges with large graphs, which lack the Euclidean structure of time-series and image data. However, graphs have limits, such as the graphon—a bounded symmetric kernel that serves as both a random graph model and a limit object for a convergent sequence of graphs. Graphs sampled from a graphon almost surely share structural properties in the limit; this implies that graphons describe families of similar graphs and, as formalized in Ruiz et al. (2020), that GNNs running inference on graphs associated with the same graphon yields similar results, a property known as transferability. In this presentation, we introduce two algorithms that utilize GNNs’ transferability to enhance learning on large-scale graphs, building upon the Ruiz et al. (2020) result. The first is an optimization algorithm that exploits the convergence of a graph sequence to efficiently run gradient descent on large graphs. The second is a sampling algorithm based on an extension of the sampling theory of Paley-Wiener spaces to graphons. We demonstrate that these algorithms improve empirical performance in applications such as decentralized control of multi-agent systems and malware detection in software function call graphs.
Bio:
Luana Ruiz received the Ph.D. degree in electrical engineering from the University of Pennsylvania in 2022, and the M.Eng. and B.Eng. double degree in electrical engineering from the École Supérieure d’Electricité and the University of São Paulo in 2017. She is an Assistant Professor with the Department of Applied Mathematics and Statistics and the MINDS and DSAI Institutes at Johns Hopkins University, as well as the Electrical and Computer Engineering and Computer Science departments (by courtesy). Luana’s work focuses on large-scale graph information processing and graph neural network architectures. She was awarded an Eiffel Excellence scholarship from the French Ministry for Europe and Foreign Affairs between 2013 and 2015; nominated an iREDEFINE fellow in 2019, a MIT EECS Rising Star in 2021, a Simons Research Fellow in 2022, and a METEOR fellow in 2023; and received best student paper awards at the 27th and 29th European Signal Processing Conferences. Luana is currently a member of the Machine Learning for Signal Processing Technical Committee of the IEEE Signal Processing Society.
Discovery Building, Orchard View Room
Johns Hopkins University, Luana Ruiz