Understanding Isomorphism Bias in Graph Data Sets
This addresses a critical problem for machine learning practitioners in graph analysis by revealing biases that undermine fair algorithm comparison and result validity, making it an incremental but important contribution.
The paper identified that many graph classification datasets contain repeating instances, leading to isomorphism bias where models artificially inflate accuracy by memorizing training data, and they analyzed 54 datasets to expose this issue and provided recommendations and new datasets.
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.