Understanding Isomorphism Bias in Graph Data Sets

Abstract

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.

19 pages, 5 figures, 8 tables

References in corpus (11)

• Fast Graph Representation Learning with PyTorch Geometric
• GNNExplainer: Generating Explanations for Graph Neural Networks
• Do ImageNet Classifiers Generalize to ImageNet?
• A Survey on Graph Kernels
• How Powerful are Graph Neural Networks?
• Graph Isomorphism in Quasipolynomial Time
• Graph Kernels: A Survey
• Learning molecular energies using localized graph kernels
• Semantic Redundancies in Image-Classification Datasets: The 10% You Don't Need
• Provably Powerful Graph Networks
• Stability and Generalization of Graph Convolutional Neural Networks

Cited by in corpus (7)

• Open Graph Benchmark: Datasets for Machine Learning on Graphs
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
• Rethinking pooling in graph neural networks
• On Graph Neural Networks versus Graph-Augmented MLPs
• Lossless Compression of Structured Convolutional Models via Lifting
• SimPool: Towards Topology Based Graph Pooling with Structural Similarity Features
• A Structural Feature-Based Approach for Comprehensive Graph Classification