  In the past few years, graph neural networks (GNNs) have become the de facto
model of choice for graph classification. While, from the theoretical
viewpoint, most GNNs can operate on graphs of any size, it is empirically
observed that their classification performance degrades when they are applied
on graphs with sizes that differ from those in the training data. Previous
works have tried to tackle this issue in graph classification by providing the
model with inductive biases derived from assumptions on the generative process
of the graphs, or by requiring access to graphs from the test domain. The first
strategy is tied to the quality of the assumptions made for the generative
process, and requires the use of specific models designed after the explicit
definition of the generative process of the data, leaving open the question of
how to improve the performance of generic GNN models in general settings. On
the other hand, the second strategy can be applied to any GNN, but requires
access to information that is not always easy to obtain. In this work we
consider the scenario in which we only have access to the training data, and we
propose a regularization strategy that can be applied to any GNN to improve its
generalization capabilities from smaller to larger graphs without requiring
access to the test data. Our regularization is based on the idea of simulating
a shift in the size of the training graphs using coarsening techniques, and
enforcing the model to be robust to such a shift. Experimental results on
standard datasets show that popular GNN models, trained on the 50% smallest
graphs in the dataset and tested on the 10% largest graphs, obtain performance
improvements of up to 30% when trained with our regularization strategy.
