In recent years there has been a rapid increase in classification methods on graph structured data. Both in graph kernels and graph neural networks, one of the implicit assumptions of successful state-of-the-art models was that incorporating graph isomorphism features into the architecture leads to better empirical performance. However, as we discover in this work, commonly used data sets for graph classification have repeating instances which cause the problem of isomorphism bias, i.e. artificially increasing the accuracy of the models by memorizing target information from the training set. The problem does not vanish even in consideration of node labels. This prevents fair competition of the algorithms and raises a question of the validity of the obtained results. First, we characterize this effect theoretically by reducing the graph classification to a weighted classification problem and estimating the corresponding generalization gap. Then we analyze 54 data sets, previously extensively used for graph-related tasks, on the existence of isomorphism bias, give a set of recommendations to machine learning practitioners to properly set up their models, and open source new data sets for the future experiments.
The paper is concerned with the presence of isomorphism bias in commonly used graph learning benchmarks. In particular, the paper analyzes the amount of isomorphic graphs in 54 graph datasets and evaluates the performance of three graph classification methods under two isomorphism settings.
Careful analyses of commonly used benchmarks can be important contributions that provide new insights into the performance of state-of-the-art models. The present paper's results on graph isomorphism properties can indeed be valuable for the ablation of models and testing their performance with regard to this property. I also found the relatively high label disagreements on some datasets (even under stronger isomorphism constraints) to be a surprising and useful result.
However, the main assumption of the paper -- which equates the quality of a graph learning benchmark with the amount of isomorphic graphs that it contains, i.e., the lower the better -- seems questionable.
The paper argues that isomorphic graphs are akin to duplicate images in computer vision and should be removed from a dataset. While completely identical graphs are certainly problematic, the case seems different for isomorphic graphs. In the latter, a learning method is required to identify the correct bijection form V_1 to V_2 which is a non-trivial task. Testing on isomorphic graphs evaluates the ability of a model to infer these equivalence classes from data which is an important property. Moreover, being able to capture the equivalence relation can be important for various graph learning tasks, e.g., to facilitate that two topologically equivalent graphs are be classified similarly.  Going back to the computer vision analogy: it seems a more adequate comparison for graph isomorphism would be translation and scale invariance which are certainly desirable properties for CV models.
In addition, the dataset analysis could also be improved. For instance, the SYNTHETIC dataset includes continuous node attributes that are essential for classification and make the graphs non-isomorphic (when considering, for instance, each attribute vector as a unique node label). However, the attributes are not considered in the analysis what leads to a large number of isomorphic graphs. On a side note: the paper also incorrectly attributes the SYNTHETIC dataset to (Morris et al, 2016), but it is in fact from [1]. The synthetic dataset of Morris et al (SYNTHIE) does not consist of isomorphic graphs, while the SYNTHETIC dataset of [1] does so intentionally.
The results of Section 5 seem also not very surprising: After removing node labels, it is expected that the number of isomorphic graphs increases since a discriminating feature has been removed. Moreover, when accounting for node labels, many standard benchmarks seem to consist of significantly less isomorphic and mismatched graphs (as can be seen in the appendix).
Since graph isomorphism != graph identity, the assumption Y_iso \sub Y_train in Property 6 seems also not appropriate. The results of Theorem 6.1 on the other hand seems straightforward and would hold for any classification task for which the true label for an equivalence class of instances is known.