Rethinking graph classification problem in presence of isomorphism (Q7007326)

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.