Preprint on structural graph classification
Our new work (with Youngjoo Seo & Nathanaël Perraudin) considers the discrimination capacity of aggregation functions—a key ingredient of graph neural networks, generalizing convolution and pooling.
Taking first a theoretical standpoint, we argue that the maximum capacity of aggregation functions cannot be achieved in the context of learning from finite samples (by deriving a curse-of-dimensionality type lower bound).
Inspired by our findings, we design a graph neural network for structural graph classification aiming, not to have the maximum discrimination power, but to learn discriminative graph representations that generalize well. This is achieved by introducing a new type of aggregation function having fewer parameters and by exploiting randomization in training in order to combat overfitting. These choices are shown to yield benefits in practice.
Modeling paths with graph neural networks
Jean-Baptiste Cordonnier and I worked on the problem of path inference: given a path prefix, i.e., a partially observed sequence of nodes in a graph, we aim to predict which nodes are in the missing suffix.
Extrapolating paths with graph neural networks (IJCAI 2019)
For more information, see this blog-post.
Review article on sampling techniques
Nicolas Tremblay and I recently dived into the very interesting literature of sampling methods for spectral clustering. Here is the (pre-print) of our labors:
Approximating Spectral Clustering via Sampling: a Review (under consideration as a chapter of the book “Sampling methods for machine learning“)
In it, we discuss a lot of cool techniques from numerical linear algebra and machine learning (such as Nystrom approximation, Random Fourier Features, Coresets, Landmarks, Sparsification), in addition to summarizing our recent discoveries with random graph filters and coarsening.
New work on graph reduction
I have been thinking for some time now on how can we reduce the size of a graph without significantly altering its basic properties. In my latest work, I present coarsening algorithms that preserve the spectrum of a graph as well as its community structure.
Graph reduction with spectral and cut guarantees (JMLR 2019)
A demonstration can be found in this blog-post.