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. This prevents fair competition of the algorithms and raises a question of the validity of the obtained results. 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. Recently there has been an increasing interest in the development of machine learning models that operate on graph structured data. Such models have found applications in chemoinformatics (Ralaivola et al. (2005) ; Rupp & Schneider (2010) ; Ferré et al. (2017) ) and bioinformatics (Borgwardt et al. (2005) ; Kundu et al. (2013) ), neuroscience (Sharaev et al. (2018) ; Jie et al. (2016) ; Wang et al. (2016) ), computer vision (Stumm et al. (2016) ) and system security (Li et al. (2016) ), natural language processing (Glavaš &Šnajder (2013) ), and others (Kriege et al. (2019) ; Nikolentzos et al. (2019) ). One of the popular tasks that encompasses these applications is graph classification problem for which many graph kernels and graph neural networks have been developed. One of the implicit assumptions that many practitioners adhere to is that models that can distinguish isomorphic instances from non-isomorphic ones possess higher expressiveness in classification problem and hence much efforts have been devoted to incorporate efficient graph isomorphism methods into the classification models. As the problem of computing complete graph invariant is GI-hard (Gärtner et al. (2003) ), for which no known polynomial-time algorithm exists, other heuristics have been proposed as a proxy for deciding whether two graphs are isomorphic. Indeed, from the early days topological descriptors such Wiener index (Wiener (1947a; b) ) attempted to find a single number that uniquely identifies a graph. Later, graph kernels that model pairwise similarities between graphs utilized theoretical developments in graph isomorphism literature. For example, graphlet kernel (Shervashidze et al. (2009) ) is based on the Kelly conjecture (see also Kelly (1957) ), anonymous walk kernel ) derives insights from the reconstruction properties of anonymous experiments (see also Micali & Allen Zhu (2016) ), and WL kernel (Shervashidze et al. (2011a) ) is based on an efficient graph isomorphism algorithm. For sufficiently large k, kdimensional WL algorithm includes all combinatorial properties of a graph (Cai et al. (1992a) ), so one may hope its power is enough for the data set at hand. Since only for k = Ω(n) WL algorithm is guaranteed to distinguish all graphs (for which the running time becomes exponential; see also Fürer (2017) ), in the general case WL algorithm can be used only as a strong baseline for graph isomorphism. In similar fashion, graph neural networks exploit graph isomorphism algorithms and have been shown to be as powerful as k-dimensional WL algorithm (see for example Maron et al. (2019) ; Xu et al. (2018) ; ). Experimental evaluation reveals that models based on the theoretical constructions with high combinatorial power such as WL algorithm performs better than the models without them such as Vertex histogram kernel (Vishwanathan et al. (2010) ) on a commonly used data sets. This could add additional bias to results of comparison of classification algorithms since the models could simply apply a graph isomorphism method (or an efficient approximation) to determine a target label at the inference time. However, purely judging on the accuracy of the algorithms in such cases would imply an unfair comparison between the methods as it does not measure correctly generalization ability of the models on the new test instances. As we discover, indeed many of the data sets used in graph classification have isomorphic instances so much that in some of them the fraction of the unique non-repeating graphs is as low as 20% of the total size. This challenges previous experimental results and requires understanding of how influential isomorphic instances on the final performance of the models. Our contributions are: • We analyze the quality of 54 graph data sets which are used ubiquitously in graph classification comparison. Our findings suggest that in the most of the data sets there are isomorphic graphs and their proportion varies from as much as 100% to 0%. Surprisingly, we also found that there are isomorphic instances that have different target labels suggesting they are not suitable for learning a classifier at all. • We investigate the causes of isomorphic graphs and show that node and edge labels are important to identify isomorphic graphs. Other causes include numerical attributes of nodes and edges as well as the sizes of the data set. • We express an upper bound for the generalization gap through the Radamacher complexity of a classifier and the number of isomorphic graphs in a data set. This bound presents theoretical evidence on how weightning of each graph in the training influences classification accuracy. • We evaluate a classification model's performance on isomorphic instances and show that even strong models do not achieve optimal accuracy even if the instances have been seen at the training time. Hence we show a model-agnostic way to artificially increase performance on several widely used data sets. • We open-source new cleaned data sets that contain only non-isomorphic instances with no noisy target labels. We give a set of recommendations regarding applying new models that work with graph structured data. In this work we study isomorphism bias of the classification models in graph structured data that originates from substantial amount of isomorphic graphs in the data sets. We analyzed 54 graph data sets and provide the reasons for it as well as a set of rules to avoid unfair comparison of the models. We theoretically characterized the influence of isomorphism bias on the graph classification performance by providing an upper bound on the generalization gap. We showed that in the current data sets any model can memorize the correct answers from the training set and we open-source new clean data sets where such problems do not appear. A STATISTICS FOR ORIGINAL DATA SETS
Many graph classification data sets have duplicates, thus raising questions about generalization abilities and fair comparison of the models.  The authors discuss isomorphism bias in graph datasets, the overfitting effect in learning networks whenever graph isomorphism features are incorporated within the model, theoretically analogous to data leakage effects.