### 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.

Discriminative structural graph classification

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*.