Rethinking graph classification problem in presence of isomorphism
This paper addresses a fundamental flaw in graph classification research: the widespread presence of isomorphic graphs (structurally identical graphs, possibly with different vertex labels) in benchmark datasets. Such isomorphisms may result in misleading conclusions. For example, the relative ranking of the graph models can change substantially if isomorphic graphs are removed from the datasets.\N\NThe paper shows that explicitly incorporating the knowledge of isomorphism in the datasets can significantly boost the performance of any graph model. Additionally, the paper re-evaluates commonly used graph models on refined graph datasets and provides recommendations for designing new datasets and metrics for graph classification problems. In particular, the paper analyzes 54 popular graph classification datasets and finds that over 80\% of these datasets contain at least 10\% isomorphic graphs; some are entirely isomorphic. Many datasets have isomorphic graphs with conflicting labels, making them unsuitable for fair classification tasks. Additionally, the presence of isomorphic graphs in both training and test sets allows models to ``memorize structures, artificially boosting test accuracy by up to 5\%. When test sets are deduplicated (removing isomorphic duplicates), model accuracy typically drops, revealing the true generalization ability. More results are described in the introduction of the paper.\N\NIn summary, the paper reveals that isomorphic graphs are a pervasive and underappreciated problem in graph classification. The authors' analysis demonstrates that current benchmarks can mislead model evaluation, but also provides concrete steps to address the issue. This is practically important and relevant for chemistry, social networks, and beyond.
- A congruence theorem for trees
- A gentle introduction to deep learning for graphs
- An optimal lower bound on the number of variables for graph identification
- Graph isomorphism in quasipolynomial time (extended abstract)
- Graph kernels
- Graph kernels: a survey
- scientific article; zbMATH DE number 3575612 (Why is no real title available?)
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- On the combinatorial power of the Weisfeiler-Lehman algorithm
- Practical graph isomorphism. II.
- Propagation kernels: efficient graph kernels from propagated information
- Reconstructing Markov processes from independent and anonymous experiments
- The Vapnik-Chervonenkis dimension of graph and recursive neural networks
- Weisfeiler-Lehman graph kernels
This page was built for publication: Rethinking graph classification problem in presence of isomorphism
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7007326)
