What graph neural networks cannot learn
My recent work studies the capacity limits of graph neural networks (GNN) falling in the message-passing framework of Gilmer et al.
Two main results are derived:
- First, GNN are shown to be Turing universal under sufficient conditions on their construction.
- Second, it is discovered that GNN can lose a significant portion of their power when their depth and width is restricted.
The proposed impossibility statements concern an array of decision, optimization, and estimation problems involving graphs (e.g., does my graph contain a cycle, estimate the diameter, or identify the minimum cut). Strikingly, several of these problems are deemed impossible unless the product of a GNN’s depth and width exceeds the graph size; this dependence remains significant even for tasks that appear simple or when considering approximation.
The discrimination capacity of graph neural network layers
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.
Graph reduction and coarsening
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.