arXiv (Cornell University) · 2019 · 16 citations · 40 references
ComputingComputer ScienceData MiningFeature EngineeringMachine LearningDeep LearningGraph AlgorithmsGraph MiningGraph TheoryGraph-based LearningRepresentation LearningGraph ClassificationGraph IsomorphismGraph KernelsGraph Neural Network FeaturesGraph Neural NetworksGraph Representation LearningGraph Structure Learning
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.
40
Practical graph isomorphism, II
Brendan D. McKay, Adolfo Piperno · Journal of Symbolic Computation · 2013 · 1.6K citations
Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks
Christopher Morris, Martin Ritzert, Matthias Fey et al. · 2019 · 1.2K citations
Protein function prediction via graph kernels
Karsten Borgwardt, Cheng Soon Ong, Stefan Schönauer et al. · Computer applications in the biosciences · 2005 · 1.1K citations
Pinar Yanardag, S. V. N. Vishwanathan · 2015 · 1.1K citations