Luana Ruiz, University of Pennsylvania: “Machine Learning on Large-Scale Graphs”

Position: PhD Candidate

Current Institution: University of Pennsylvania

Abstract: Machine Learning on Large-Scale Graphs

GNNs are successful at learning representations from most types of network data but suffer from limitations in large graphs. Challenges arise in the design of the learning architecture—since GNNs are parametrized by some matrix representation which can be hard to acquire when the network is large—and because in many GNN architectures graph operations are defined through spectral convolutions—which require the computation of the graph spectrum through a costly eigendecomposition. Yet large graphs can often be identified as being similar to each other in the sense that they share structural properties. We can thus expect that processing data supported on such graphs should yield similar results which would mitigate the challenge of large size since we could then design GNNs for small graphs and transfer them to larger ones. In my research I formalize this intuition and show that transferability across graphs is possible when the graphs belong to the same family each family being identified by a graphon W(x y) which describes a class of stochastic graphs with similar shape. One can think of the arguments (x y) as the labels of a pair of nodes and of W(x y) which is upper bounded by one as the probability of an edge between x and y. This yields a notion of a graph sampled from a graphon or equivalently a notion of a limit as the number of nodes in the sampled graph grows. Graphs sampled from a graphon almost surely share properties in the limit such as homomorphism densities. This implies that graphons identify families of networks that are similar in the sense that the density of certain motifs is preserved motivating the study of information processing on graphons as a way to enable information processing on large graphs.


Luana received the B.Sc. degree in electrical engineering from the University of Sao Paulo Brazil and the M.Sc. degree in electrical engineering from the Ecole Superieure d’Electricite (now CentraleSupelec) France in 2017. She is currently a Ph.D. candidate with the Department of Electrical and Systems Engineering advised by Prof. Alejandro Ribeiro. Her research interests are in the fields of graph signal processing and machine learning over network data. She was awarded an Eiffel Excellence scholarship from the French Ministry for Europe and Foreign Affairs between 2013 and 2015 and in 2019 received a best student paper award at the 27th European Signal Processing Conference.