Understanding Isomorphism Bias in Graph Data Sets 
Authors: Ivanov Sergey
Sviridov Sergey
Evgeny Burnaev
Venue:  (2020)
Keywords: graph classification
data sets
graph representation learning

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. 

Under review as a conference paper at ICLR 2020
UNDERSTANDING ISOMORPHISM BIAS IN GRAPH DATA SETS
Anonymous authors Paper under double-blind review
ABSTRACT
In recent years there has been 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-ar models was that incorporating graph isomorphism features into the architecture leads to better empirical perfor- mance. 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 the models by memorizing target information from the training set. The problem does not vanish even in consider- ation of node labels. This prevents fair competition of the algorithms and raises question of the validity of the obtained results. First, we characterize this ef- feet theoretically by reducing the graph classification to a weighted classification problem and estimating the corresponding generalization gap. Then we analyze 54 data sets, previously extensively used for graph-related tasks, on the existence of isomorphism bias, give set of recommendations to machine learning prac- titioners to properly set up their models, and open source new data sets for the future experiments.
INTRODUCTION
Recently there has been an increasing interest in the development of machine learning models that operate on graph structured data. Such models have found applications in chemoinformatics
(Ralaivola et al. (2005); Rupp & Schneider (2010); Ferré al. (017)) and bioinformatics (Borg-
wardt et al. (2005) y Kundu et (2013)) neuroscience (Sharaev et al. 2208 (018); [ie el. (2016); Wang
ctt al. (2016). ) computer vision (Stumm et al. (2016)) and system security (Li et al. (2016)) natu-
ral language processing (Glavaš& Snajder (2013), and others <Kriege et al. (2019): Nikolentzos
al. (2019)). One of the popular tasks that encompasses these applications is graph classification problem for which many graph kernels and graph neural networks have been developed.
One of the implicit assumptions that many practitioners adhere to is that models that can distin- guish isomorphic instances from non-isomorphic ones possess higher expressiveness in classifica- tion problem and hence much efforts have been devoted incorporate efficient graph isomorphism methods into the classification models. As the problem of computing complete graph invariant is GI-hard (Gärtner al. (003)), for which no known polynomial time algorithm exists, other heuris- tics have been proposed as a proxy for deciding whether two graphs are isomorphic. Indeed, from the early days topological descriptors such Wiener index (Wiener) (1947a b)) attempted find single number that uniquely identifies a graph. Later, graph kernels that model pairwise similarities between graphs utilized theoretical developments in graph isomorphism literature. For example, graphlet kernel (Shervashidze et al.] (2009) is based on the Kelly conjecture (see also Kelly 1957)) ) anonymous walk kernel (Ivanov Burnaev (2018) derives insights from the reconstruction proper- ties of anonymous experiments (see also Micali & Allen Zhu (2016)). and WL kernel (Shervashidze et al. (201 lab) is based on an efficient graph isomorphism algorithm. For sufficiently large k, k- dimensional WL algorithm includes all combinatorial properties of a graph (Cai et al. (1992a)). so one may hope its power is enough for the data set at hand. Since only for & = 2(n) WL algorithm is guaranteed to distinguish all graphs (for which the rumning time becomes exponential; see also Fürer (2017)), in the general case WL algorithm can be used only as a strong bascline for graph isomorphism. In similar fashion, graph neural networks exploit graph isomorphism algorithms and

---

Under review as a conference paper at ICLR 2020
have been shown to be powerful as k-dimensional WL algorithm (see for example Maron et al. (2019); Xu et al. (2018); Morris et al. (2019)).
Experimental evaluation reveals that models based the theoretical constructions with high com- binatorial power such as WL algorithm performs better than the models without them such as Vertex histogram kernel (Vishwanathan et al. (2010)) commonly used data sets. This could add addi- tional bias to results of comparison of classification algorithms since the models could simply apply graph isomorphism method (or an efficient approximation) determine target label the infer- ence time. However, purely judging on the accuracy of the algorithms in such cases would imply an unfair comparison between the methods as it does not measure correctly generalization ability of the models on the new test instances. As we discover, indeed many of the data sets used in graph classification have isomorphic instances so much that in some of them the fraction of the unique non-repeating graphs is as low as 20% of the total size. This challenges previous experimental re- sults and requires understanding of how influential isomorphic instances on the final performance of the models. Our contributions are:
We analyze the quality of 54 graph data sets which are used ubiquitously in graph classifica- tion comparison. Our findings suggest that the most of the data sets there are isomorphic graphs and their proportion varies from much as 100% to 0%. Surprisingly, we also found that there are isomorphic instances that have different target labels suggesting they are not suitable for learning a classifier at all.
We investigate the causes of isomorphic graphs and show that node and edge labels are important identify isomorphic graphs. Other causes include numerical attributes of nodes and edges as well as the sizes of the data set.
We express an upper bound for the generalization gap through the Radamacher complexity of classifier and the number of isomorphic graphs data set. This bound presents the- oretical evidence on how weightning of each graph in the training influences classification accuracy.
We evaluate classification model's performance isomorphic instances and show that even strong models do not achieve optimal accuracy even if the instances have been seen at the training time. Hence we show a model-agnostic way to artificially increase performance on several widely used data sets.
We open-source new cleaned data sets that contain only non-isomorphic instances with no noisy target labels. We give of recommendations regarding applying new models that work with graph structured data.
2 RELATED WORK
Measuring quality of data sets. similar issue of duplicates instances in commonly used data sets was recently discovered in computer vision domain. Recht et al. (201)); Barz & Denzler (201);; Birodkar et al. (2019) discover that image data sets CIFAR and ImageNet contain at least 10% of the duplicate images in the test test invalidating previous performance and questioning generalization abilities of previous successful architectures. In particular, evaluating the models in new test sets shows a drop of accuracy by as much as 15% (Recht et al. 2019), which is explained by models' incapability to generalize to unseen slightly "harder" instances than in the original test sets. In graph domain, fresh look into understanding of expressiveness of graph kernels and the quality of data sets has been considered in Kriege et al. (2019), where an extensive comparison of existing graph kernels is done and a few insights about models' behavior are suggested. In contrast, we conduct broader study of isomorphism metrics, revealing all isomorphism pairs in proposed 54 data sets, and propose new cleaned data. Additionally we also consider graph neural network performance and argue that current data sets present isomorphism bias which can artificially boost evaluation metrics in model-agnostic way.
Explaining performance of graph models. Graph kernels (Kriege et al. (2019) and graph neural networks (Wu et al. (2019) are two competing paradigms for designing graph representations and solving graph classification and have significantly advanced empirical results due to more efficient algorithms, incorporating graph invariance into the models, and end-to-end training. Several papers have tried to justify performance of different families of methods by studying different statistical
2

---

Under review as a conference paper at ICLR 2020
properties. For example, in Ying al. (2019) by maximizing mutual information between explana- tion variables and predicted label distribution, the model is trained to return a small subgraph and the graph-specific attributes that are the most influential on the decision made by GNN, which allows inspection of single- and multi-level predictions in an agnostic manner for GNNs. In another work (Scarselli al. 2018)), the VC dimension of GNNs models has been shown to grow Ogp'N2), where p is the number of network parameters and N is the number of nodes in a graph, which is comparable RNN models. Furthermore, stability and generalization properties of convolutional GNNs have been shown to depend on the largest eigenvalue of the graph filter and therefore are attained for properly normalized graph convolutions such as symmetric normalized graph Laplacian [Verma& & Zhang] (2019)). Finally, expressivity of graph kernels has been studied from statistical learning theory (Oneto et al. (2077b) and property testing (Kriege al. (20T8b)), showing that graph kernels can capture certain graph properties such planarity, girth, and chromatic number Johansson et al. (2014)). Our approach is complementary to all of the above as we analyze the data sets used in experiments have any effect the final performance.
PRELIMINARIES
In this work analyze 54 graph data sets from Kersting et al. (2016) that commonly used in graph classification task. Examples of popular graph data sets are presented in Table and statistics of all 54 data sets can be found in Table [] see Section A in the appendix. All data sets represent a collection of graphs and accompanying categorical label for each graph in the data sets. Some data sets also include node and/or edge labels that graph classification methods can use improve the scoring. Most of the data sets come either from biological domain or from social network domain. Biological data sets such as MUTAG, ENZYMES, PROTEINS are graphs that represent small large molecules, where edges of the graphs are chemical bonds spatial proximity between different atoms. Graph labels in these cases encode different properties like toxicity. In social data sets such IMDB-BINARY, REDDIT-MULTISKK COLLAB the nodes represent people and edges are relationships in movies, discussion threads, or citation network respectively. Labels in these cases denote the type of interaction like the genre of the movie/thread For completeness we also include synthetic data sets SYNTHETIC (Morris et al. (2016) that have continuous attributes and computer vision data sets MSRC (Neumann et al. (2016)), where images are encoded as graphs. The origin of all data sets can be found in the Table
research subfield.
Table 1: Example of graph data sets. N is the number of graphs, C' is the number of different classes. Avg. Nodes and Avg. Edges is the average number of nodes and edges. N.L. and E.L indicate if the graphs in a data set contain node or edge labels.
data set
Type
N
C
Avg. Nodes
Avg. Edges
N.L.
E.L.
MUTAG
Molecular
188
2
17.93
19.79
+
+
ENZYMES
Molecular
600
32.63
62.14
+
PROTEINS
Molecular
1113
2
39.06
72.82
IMDB-BINALE
Social
1000
2
19.77
96,53
REDDIT-MULTI-SK
Social
4999
508.52
594.87
COLLAB
Social
5000
3
74.49
2457.78
SYNTHETIC
Synthetic
300
2
100
196
Synthie
Synthetic
400
95
172.93
MSRC 21C
Vision
209
20
40.28
96.6
MSRC_9
Vision
221
8
40.58
97.94
+
Graph isomorphism. Isomorphism between two graphs G (Vi, F1) and G2 = (V2, F2) is a bijective function Φ V1 + V22 such that any edge (u, E Ej if and only if (Ø(u), Φ(v)) Eg. Graph isomorphism problem asks such function exists for given two graphs G and G2. We denote isomorphic graphs G 2 G2. The problem has efficient algorithms in IP for certain classes of graphs such as planar or bounded-degre graphs (Hopcroft & Wong (1974); Luks (1980), but in the general case admits only guasi-polynome algorithm (Babai (2015)). In practice many GI solvers are based on iatiiiddaaizztiio-reffeeem paradigm (Mckay & Piperno (2014)), which for each graph iteratively updates permutation of the nodes such that the resulted permutations of two
3

---

Under review as a conference paper at ICLR 2020
graphs are identical if an only if they are isomorphic. Importantly, while finding such canonical permutation of a graph is at least as hard as solving GI problem, state-of state-of-the-ar solvers tackle majority of pairs of graphs efficiently, only taking exponential time on the specific hard instances of graphs that possess highly symmetrical structures (Cai et al. (1992h).
IDENTIFYING ISOMORPHISM IN DATA SETS
To distinguish between different isomorphic graphs inside data orbits:
the notion of graph
Definition 4.1 (Graph orbit). Let D {G,, yt Ji _ be data of graphs and target labels. For graph G; let a set O; {Gx} be set of all isomorphic graphs in D to G,, including G, We call o, the orbit of graph G3 in D. The cardinality of the orbit is called orbil size. An orbit with size one is called trivial.
In data set with no isomorphic graphs, the number of orbits equals to the number of graphs in data set, N. Hence, the more orbits a data set, the "cleaner" is. Note however that the distribution of orbit sizes in two different data sets vary even if they have the same number of orbits. Therefore, we look at additional metrics that describe the data set.
I. aggregated number of graphs that belong to orbit of size greater than one, i.c. those graphs that isomorphic counterparts in a data set;
I, %, proportion of isomorphic graphs to the total data size, i.e. :;
IP, %, proportion of isomorphic pairs to the total number of graph pairs in a data set ((N-1))
If consider target labels of graphs in data set D (G,, N between the labels two isomorphic data set. If G, = G2 and y1 * V2. then we call graphs mismatched. Note that if there is more than one target label in orbit o, then all graphs in this orbit are mismatched. To obtain isomorphic graphs, we run nauty algorithm (Mekay & Piperno 2014) on all possible pairs of graphs in data set. We substantially reduce the number of calls between the graphs by verifying that pair has the same number of nodes and edges before the call.
also measure agreement
The metrics are presented in Table for top-10 data sets and in Tsbee the appendix) for all data sets. The graphs in Table sorted by the proportion of isomorphic graphs 7%. The results for the first Top-10 10 data sets are somewhat surprising: almost all graphs in the selected data sets have other isomorphic graphs. If we look at all data sets in Table we see that the proportion of isomorphic graphs in the data sets varies from 100% to 0%. However, more than 80% of the analyzed data sets have at least 10% of the graphs in a non-trivial orbit.
Table 2: Isomorphic metrics for Top-10 data sets based on the proportion of isomorphic graphs 1%. I P% is the proportion of isomorphic pairs of graphs, Mismatched % is the proportion of mismatched labels.
data set
Size, N
Num. orbits
Iso. graphs,
1%
IP%
Mismatched %
SYNTHETIC
300
2
300
100
100
100
Cuneiform
267
267
100
20.46
100
Letter-low
2250
32
2245
99.78
8.72
96.22
DHFR MD
393
25
392
99.75
6.87
94.91
COIL-RAG
3900
3890
99.74
25.22
99.31
COX2 MD
303
13
301
99.34
11.83
98.68
ER ER.MD MD
446
31
442
99.1
5.57
82.74
Fingerprint
2800
2774
99.07
16.86
89.29
BZR MD
306
22
303
99.02
7.16
95.75
Letter-med
2250
39
2226
98.93
8.05
92.93
Another surprising observation is that the proportion of mismatched graphs is significant, ranging from 100% 0%. This clearly indicates that such graphs not suitable for graph classification
4

---

Under review as a conference paper at ICLR 2020
and require additional information to distinguish the models. We analyze the reasons for this in the next section.
Also, the distribution of orbit sizes vary significantly across the data sets. In Figure I we plot distribution orbit sizes for several examples data sets (and distributions for other data sets can be found in Appendix C For example, for IMDB-BINARY BINARY data set the number of orbits of small sizes, e.g. two or three, goes to 100, which indicate prevalence of pairs isomorphic graphs that are non-isomorphic the rest. However, for Letter-med data there are many orbits of sizes more than 100, while small orbits are not that common. In this case, the graphs in this data set are equivalent lot of other graphs, which may have substantial effect on the corresponding metrics. While the orbit distribution changes from one data set to another, it is clear that in many situations there are isomorphic graphs that can affect training procedure by effectively increasing the weights for the corresponding graphs, change performance on the test by validating on the already seen instances, and by confusing the model by utilizing different target labels for aeolooically-equivlleee graphs. We analyze the reasons for it further.
IMDB-BINARY
Letter-med
COLLAB
no-labels
25
no-labels
no-labels
Number of orbits
125
80
20
100
60
15
75
40
10
50
20
25
%
0
20
40
100
200
300
50
100
Orbit size
Orbit size
Orbit size
Figure 1: Examples of distributions of orbit sizes without considering labels.
EXPLAINING ISOMORPHISM
Meta-information about graphs. In addition to the topology of a graph, many data sets also in- clude meta information about nodes and/or edges. Out of 54 analyzed data sets there are 40 that additionally include node features and 25 that include edge features. For example, in Synthetic data set all graphs are topologically identical but the nodes are endowed with normally distributed scalar attributes and in DHFR MD edges are attributed with distances and labeled according to a chemical bond type. Alternatively, some graphs can have parallel edges which is equivalent have a corresponding weight on the edges. Thus some data sets include node/edge categorical features (labels) and numerical features (attributes), which leads better distinction between the graphs and therefore their corresponding labels.
To see this, we rerun our previous analysis but now include the node labels, if any, when comput- ing isomorphism between graphs. Consider a tuple (G, l). where G is graph and / : V(G) + is a k-labeling of G. In this case of node labse-ngg graph isomorphism from graph (G1, 21) to graph (G2, 12) we seek an isomorphism function & V(G)) + V(G2) such that (v)) = (2(()())).
(1, (1.2..... .b} ......,)
Tables 3 and 7 (see the appendix) show the number of isomorphic graphs after considering node labels. While for the first six data sets the proportion isomorphic graphs has not changed much, it is clearly the case for the remaining data sets. In particular, almost 90% of the analyzed data sets include less than 20% of isomorphic graphs. Also, the number of mismatched graphs significantly decreases after considering node labels. For example, for MUTAG data the proportion of iso- morphic graphs went down from 42.02% to 19.15% and the proportion of mismatched graphs from 6.91% % to 0%.
5

---

Under review as a conference paper at ICLR 2020
Table 3: Isomorphic metrics with node labels for Top-10 data based the proportion of iso- morphic graphs 1%. 1P% is the proportion of isomorphic pairs of graphs, Mismatched % is the proportion of mismatched labels.
data set
Size, N
Num. orbits
Iso. graphs,
1%
1P%
Mismatched
SYNTHETIC
300
2
300
100
100
100
Cuneiform
267
267
100
20.46
100
DHFR MD
393
25
392
99.75
6.87
94.91
COX2_M
303
13
301
99.34
11.83
98.68
ER MD
446
31
442
99.1
5.57
82.74
BZR MD
306
22
303
99.02
7.16
95.75
MUTAG
188
17
36
19.15
0.14
0
PTC.EM FM
349
54
15.47
0.08
10.89
PTC.MM
336
22
50
14.88
0.07
7.74
DHFR
756
39
98
12.96
0.04
3.97
Likewise, the orbit size distribution also changes significantly after considering node labels. Figure 2 shows changed distribution of orbits with and without considering node labels. For majority of data sets large orbits vanish and the number of small orbits is substantially decreased label-preserving graph isomorphism setting. This indicates of the reasons for presence of many isomorphic graphs in the data sets, which implies that including node/edge labels/attributes can be important for graph classification models.
MUTAG
PROTEINS
DHFR MD
20
wo-labels
wa-labels
wo-labels
Number of orbits
node-labels
node-labels
node-labels
15
10
10
5
02
10
20
20
40
Orbit size
Orbit size
Orbit size
Figure 2: Examples of distributions of orbit sizes with node labels.
Sizes of the data sets. Another reason for having isomorphism in a data set the sizes of graphs, which could be too small on average to lead diversity in data set. In general, the number of non-isomorphic graphs with n vertices and m edges can be computed using Polya enumeration the- ory and grows very fast. For example, for a graph with 15 nodes and 15 edges, there 2,632,420 non-isomorphic graphs. Nevertheless, specifics of the origin of the data set may affect possible con- figurations that graphs have (c.g. structure of chemical compounds for actors in IMDB-B IMDB-BINARY) and thus smaller graphs may tend to be close to isomorphic structures. On the other hand, five data sets with the average number of nodes greater than 100 have very low or zero proportion of isomorphic graphs. Hence, the average size of the graphs directly impacts the possible structure the data set and thus data sets with larger graphs tend to more diverse. We next analyze the consequences of the isomorphic graphs on classification methods.
COX2_MD or ego-networks
iSOMORPHIC GRAPHS AND WEIGHTED CLASSIFICATION
We denote by

---

Under review as a conference paper at ICLR 2020
F C y a class of binary classifiers with input space X and output space Y {-1,+1}.
IP distribution on X Y.
prior probability of positive class, i.e. P= TT w|y==1 + (1 x1)pp=====>>
= ((r ) training sample, z; E X, yr Y. our case I; E are graphs Gi. see notations in section
We consider zero-one loss function l(). y) Igzy. Let us assume that classifiers from F can detect which graphs in D are isomorphic. E.g. classifiers based on Weisfeiler-Lehman graph kernels (see Shervashidze et al. (201Ta)) are capable to do it for majority of graphs. In such case the empirical risk (p((f(=), set non-isomorphic graphs, "y 2 is equal to the number of graphs the initial sample D isomorphic to the graph zy (we count z, well).
N Σソ= 15:-1(65 ((f())) reduces to N ΣjEu Uf (xz)), (eng),y)) yÿ), where is an index
Thus under such assumptions the graph classification problem with the training data set, contain- ing isomorphic graphs, can be interpreted as a classification problem with weighted loss. Let us introduce general notations for this problem. We define some (fixed) measurable weighting func- tion u: (X Y)- + (0, +oo). Then the theoretical risk is equal Ex((f()), y) and the weighted empirical risk equal to Epu(a,, Epu(z,)) y) = N
EN u(a; yi v)) (x))) y:). We would like to derive an upper bound for the excess risk sup (x))((()).v)) v) - EDu(E, (x))))))))) y)), i.e. we would like to quantify an upper bound for a generalization gap. We optimize the weighted empirical risk when training classifier and measure its accuracy using non-weighted theoretical risk.
There are some results about classification performance with a weighted loss. E.g. DDprett & Koda 2001) bayesian framework for imbalanced classification with weighted risk is proposed. Scott 2012) investigated the calibration of asymmetric surrogate losses. Natarajan et al. (2018) con- sidered the case of cost-sensitive learning with noisy labels. However, the best of our knowledge, there is no studied upper bound for the excess risk with explicit dependence on the class imbalance and the weighting scheme that quantifies the influence on the overall classification performance. We show this result next.
To derive explicit expressions we some additional modeling asumption, namely, consider u(z, v) = (1+ 9+ (w)))(y==11) + (1 + g- [y==-) for some non-negative weighting functions
g+ (w) and g- (w) of the weight value w 2 0. E.g. we can use g+ (w) = w and g- (w) = 1 /ww.
Theorem 6.1. With probability 1 5, 8.8 for D paN the excess risk is upper bounded by
sup JeF
I (g+ (w) g- (w) - -)) +
Rx((F) + (2 + g+ + (w)) v (log 8 (22))
(I)
where RN is a Rademacher complexity of the function class F.
Let us note that the Rademacher complexity of the function class F, defined by graph kernel, was studied e.g. in Oneto et al. (2018), Oneto et al. (2017a).
From equation D it follows that by tuning the weight parameter tighter, namely collecting the terms with w in the RHS of equation we solve
make the upper bound
(w) 3TT ((ogg)-)/((2N)) (w) (3(1 ((11-) π) + (logg-1))/10 (2/(2))) min.
In case set 9 (w) and gww) 1/w, the optimal weight Wopt
3(1-))+a
3x tx
where aN = log 5 I 2N
R for N >>>>> 1. For such optimal Wopt the RHS of equation
has the form
6 m - + Rx)(F + ONN (2+ (=11-
Thus get theoretical evidence on how the weighting influences the classification accuracy: e.g. in the imbalanced case (when π se or म ss 1) selecting the weight optimally we reduce the gener- alization gap almost to zero for N >>> 1; the same time, not optimal weight can lead to overfitting.

---

Under review as a conference paper at ICLR 2020
As we already discussed, under some mild modeling assumptions the graph classification problem with isomorphic graphs in the training data set can be interpreted as the classification problem with weighted loss. Therefore the obtained estimate provides additional evidence on negative effect of the isomorphic graphs when solving the graph classification problems: the presence of isomorphic graphs in the training data could have the same negative effect as not optimal weight value for the classification with a weighted loss function.
7 INFLUENCE OF ISOMORPHISM BIAS: EMPIRICAL RESULTS
To understand the impact of isomorphic graphs in the data set on the final metric we consider sepa- rately the results two subparts of the data set. In partieular, let traain and Yeest be train and test splits of a data set. Let H; E Yesst be a graph such that there exists an isomorphic graph G; E Ytroin in the train data set. Let (Yiso) be set of all such graphs H; for which there exists isomorphic graph G; in Y Ytrain- Note that the graphs in {Yioo] are not necessarily isomorphic. We denote by nnw the test graphs that do not have isomorphic copies in the train data set, i.c. Ynew Yeess' \ Yiso- If we want to test generalization of classification models, we need to test it on new instances of the data sets and therefore at least consider Y Ynew instead of Yeest- One question regarding the perfor- mance of the models on this new test set Y Yew is whether the performance on it will be lower than on the original test set Yeett- As we show below answer to this question solely depends on the accuracy of the model on isomorphic instances is
Consider graph classification model that evaluated on normalized accuracy over a data set Y:
Σ
acc(G;)
ace(Y) = GEY
(2)
Y
where aCc(G) equals to one if the model predicts the label of G; correctly, and zero otherwise.
|Y| 0, then we consider aCc(Y) O. We can see that the accuracy on the test data set can be
written as the sum of two terms:
Σ (C)
Σ
Gcc(G)
+ Σ acc(G)
GEYie
GEYneW
GEY...
acc(Yrest)
|Yeest
Ytest
(3)
Ynew
Yiso
acc aCo(Ynew)
+
acc(Yiso).
\teat]
Ytest
Equation 3 decomposes accuracy on the original data set as the weighted sum of two accuracies on the set of new test instances Ynew and a set of the instances Yiso already appeared in the train set and therefore available to the model. We call the term acc(Y:so) as isomorphism bias, which corresponds to the accuracy of the model on the isomorphic test instances. As we will see next, the accuracy of the model on the new set Y will be less if only if the model performs better on the isomorphic set Yioo!
Claim 7.1. Let Yrest Ynew U Yisa. Ynew 0 YEso Ø and YiSo * 2, where YISo Ytrain- Then for any classification model accuracy on the new test instances Ynew is smaller than on the test set Yreat if and only if it is smaller than accuracy on the isomorphic test instances Yisos i.e.:
acc(Ytest) acc(Ynew)
+> acc(Ytso) > acc(Ynew)
The equation 4 givees definite answer with the possible performance of the model on new test set. If the model performs well on isomorphic instances Y.So, then will falsely increase performance on Yeest in comparison to Ynew- Conversely, if the model performs poorly on the instances that appeared in the training set, then removing them from the test set and evaluating the model purely on Ynew will demonstrate higher accuracy. There are two reasons for the model to misclassify isomorphic instances Yiso: (i) the instances contain target labels that are different than those that it has seen,
show in Table 2 the percentage of mismatched labels be high in some data
We provide the proof of Claim 7.1 and Claim 7.2 Appendix and
8

---

Under review as a conference paper at ICLR 2020
Table 4: Mean classification accuracy for test sets Yest and Yo (in brackets) in 10-fold cross- validation. Top-1 result in bold.
MUTAG
IMDB-B
IMDB-M
COX2
AIDS
PROTEINS
NN
0.829 (0.840)
0.737 (0.733)
0,501 (0.488)
0.82 (0.872)
0.996 (0.998)
0.737 (0.834)
NN-PH
0.867 (1.000)
0.756 (1.000)
0,522 (1.000)
0.838 (1.000)
0.996 (1.000)
0.742 (1.000)
NN-P
0.856 (0.847)
0.737 (0.731)
0.499 (0.486)
0.795 (0.83)
0.996 (0.999)
0.729 (0.709)
WL
0.862 (0.867)
0.734 (0,990)
0.502 (0.953)
0,800 (0.974)
0.993 (0.999)
0.747 (0.950)
WL-PH
0.907 (1.000)
0.736 (1.000)
(5.040..000
0.810 (1.00)
0.994 (1.000)
0.749 (1.000)
WL-P
0.870 (0.838)
0.724 (0.715)
0,495 (0.487)
0.794 (0.844)
0.994 (0.999)
0.740 (0.742)
V
0.836 (0.902)
0.707 (0.820)
0.503 (0.732)
0,781 (0.966)
0.994 (0.997)
0.726 (0.946)
V-PH
0.859 (1.000)
0.750 (1.000)
0.517 (1.000)
0.794 (1.000)
0.996 (1.000)
0.729 (1. (0000)
V-P
0.827 (0.844)
0.724 (0.728)
0.496 (0.481)
0.768 (0.852)
0.996 (0.999)
0.719 (0.741)
sets; or (ii) the model is not expressive enough to map the structure the graphs to the target label correctly.
Crucially, while Ynow tests generalization capabilities of the models, on Yiso the models can explic- itly or implicitly memorize the right labels from the training. We describe model-agnostic way to guarantee increase classification performance if Ys * O.
Let G G such that G E Yiso and G E Ytrain- Note that there can be multiple isomorphic graphs (G.) C Yirain. If for any G Yiso all target labels of the orbit of G are the same we call the set Viso as homogeneous. Consider a classification model M that maps each graph G its label (()). We define a peering model M such that for each G Yio it outputs the target label I(G). Then the accuracy of the model M is at least the accuracy of the original model M.
Claim 7.2. Let Ytest = Ynew U Yiso. Ynew n Yiso Ø. If Yiso is homogeneous, then the accuracy on Yrest of a classification model M is at most as the accuracy of its peering model M, i.e.:
M (Yres) S acc . (Ytest).
Claim 7.2 establishes way to increase performance only for homogeneous Yiso- If there are noisy labels in the training set and hence the set not homogeneous, the model cannot guarantee the right target label for these instances. Nonetheless, one can select a heuristic such majority vote among the training isomorphic instances to select a proper label at the testing time.
In experiments, we compare neural network model (NN) (Xu et al., 2018) with graph kernels, Weisfeiler- (WL) (Shervashidze et al. 201 and vertex histogram (V) (Sugiyama & Borg- wardi 2015). For each model we consider two modifications: one for peering model on homoge- neous iso (e.g. NN-PH) and one for peering model on all Y:so (e.g. NN-P). We show accuracy on Ylest and on Yiso (in brackets) in Table Experimentation details can be found in Appendix G
From Table we can conclude that peering model on homogeneous data is always the top performer.
This is aligned with the result of Claim 7.2 which guarantees that acc(Y.so) 1, but it is an interesting observation if we compare it to the peering model on all isomorphic instances Yiso (-P models). Moreover, the latter model often loses even to the original model, where information from the train set is explicitly taken into the test set. This can be explained by the noisy target labels in the orbits of isomorphic graphs, as can be seen both from the statistics for these datasets (Table 6) and accuracy measured just on isomorphic instances Yi.o. These results show that due to the presence of isomorphism bias performance of any classification model can be overestimated by as much as 5% of accuracy on these datasets and hence future comparison of classification models should be estimated on Y Ynew instead. These observations conforms with our theoretical findings and conclusions in Section 6
7.1 GENERAL RECOMMENDATIONS
In order to avoid measuring performance over the wrong test sets, we provide a set of recommenda- tions that will guarantee measuring the right metrics for the models.
9

---

Under review as a conference paper at ICLR 2020
We open-source new, "clean" data sets that do not include isomorphic instances that in Table g To tackle this problem the future, we propose to use clean versions of the data set for which isomorphism bias vanishes. For each data set consider the found graph orbits and keep only one graph from each orbit if and only if the graphs in the orbit have the same label. If the orbit contains more than one label, classification model can do little to predict a correct label at the inference time and hence we remove such orbit completely. In this case, for new data set Yiso to implicitly memorize the labels from the training set. We consider the data set orbits that do not account for neither node nor edge labels because the remaining graphs are not isomorphic based purely on graph topology.
and hence it prevents the models
Incorporating node and edge features into the models may be necessary to distinguish the graphs. As we have seen, just using node labels can reduce the number of isomorphic graphs significantly and many data sets provide additional information to distinguish the models at full scope.
Verification of the models on bigger graphs in general is more challenging due to the sheer number of non-isomorphic graphs. For example, data sets related REDDIT or DD in- clude number of big graphs for classification.
CONCLUSION
In this work study isomorphism bias of the classification models in graph structured data that originates from substantial amount of isomorphic graphs in the data sets. We analyzed 54 graph data sets and provide the reasons for as well as a set of rules avoid unfair comparison of the models. We theoretically characterized the influence of isomorphism bias on the graph classification performance by providing an upper bound on the generalization gap. We showed that in the current data sets any model can memorize the correct answers from the training set and we open-source new clean data sets where such problems do not appear.
REFERENCES
László Babai. Graph isomorphism in quasipolynomial time. CoRR, abs/ abs/1512.03547, 2015. URL httt:://ariis org/ abs /et./111..00000.
Bjöm Barz and Joachim Denzler. Do train test data? purging cifar of near-duplicates. arXiv preprint arXiv:1902.00423, 2019.
Vighnesh Birodkar, Hossein Mobahi, and Samy Bengio. Semantic redundancies in image- classification datasets: The 10% you don't need. arXiv preprint arXiv: 1409, 2019.
Karsten M Borgwardt, Cheng Soon Ong. Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(suppl 1): i47-i56, 2005.
Jin- Yi Cai, Martin Fürer, and Neil Immerman. optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-41) 1992a.
Jin-yi Cai, Martin Fürer,, and Neil Immerman. An optimal lower bound on the number of variables for graph identifications. Combinatorica, 1992b.
Tox21 Data Challenge. Tox21 data challenge 2014, 2014. URL htttss://tripoot nih. niw.govv/ Fox21/challeene//Cae
jsp
Georges Dupret and Masato Koda. Bootstrap re-sampling for unbalanced data in supervised learn- ing. European Journal of Operational Research, 134(1):141 156, 2001.
Aasa Feragen, Niklas Kasenburg, Jens Petersen, Marleen de Bruijne, and Karsten Borgwardt. Scal- able kernels for graphs with continuous attributes. In Advances Neural Information Processing Systems, pp. 216-224, 2013.
10

---

Under review as a conference paper at ICLR 2020
Grégoire Ferré, Terry Haut, and Kipton Barros. Learning molecular energies using localized graph kernels. The Journal of chemical physics, (46(11):11400) 2017.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning on Graphs and Manifolds, 2019.
Martin Fürer. On the combinatorial power of the weisfeiler-lehman algorithm. In International Conference on Algorithms and Complexity, pp. 260-271. Springer, 2017.
Thomas Gärtner, Peter Flach, and Stefan Wrobel. On graph kernels: Hardness results and efficient alternatives. In Learning theory and kernel machines, pp. 129-143. Springer, 2003.
Goran Glavaš and Jan Snajder. Event-centered information retrieval using kernels event graphs. In Proceedings of TexxGraphs-8 Graph basph-baseddae Methods for Natural Language Processing, pp. 1-5, 2013.
Hopcroft and Wong. Linear time algorithm for isomorphism of planar graphs (preliminary report). In Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, STOC '74, 1974.
Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings. Proceedings of the 35th International Conference Machine Learning (ICML), 2018.
Biao Jie, Mingxia Liu, Xi Jiang, and Daoqiang Zhang. Sub-network based kernels for brain net- work classification. In Proceedings of the 7th ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics, pp. 622-629. ACM, 2016.
Fredrik Johansson, Vinay Jethava, Devdatt Dubhashi, and Chiranjib Bhattacharyya. Global graph kemelss using geometric embeddings. In Proceedings of the 31st International Conference on Machine Learning. ICML 2014. Beijing, China, 21-26 June 2014. 2014.
Paul J. Kelly, congruence theorem for trees. Pacific J. Math., 7(1):961-968, 1957. URL https: //projecteeuclid orq: 443/ htt.m//11104433..
Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann. Bench- mark data sets for graph kernels, 2016. UR./nttp::/grrppkeenne...
tu dortmund.
Nils Kriege and Petra Mutzel. Subgraph matching kernels for attributed graphs. arXiv preprint arXiv: 12X6::/006.6440 6483, 2012.
Nils M Kriege, Matthias Fey, Denis Fisseler, Petra Mutzel, and Frank Weichert. Recognizing cuneiform signs using graph based methods. arXiv preprint arXiv:1802.05900 2018a.
Nils M Kriege, Christopher Morris, Anja Rey, and Christian Sohler. A property testing framework for the theoretical expressivity of graph kernels. In IJCAI, pp. 2348-2354, 2018b.
Nils M Kriege, Fredrik D Johansson, and Christopher Morris. A survey on graph kernels. arXiv preprint 190. 2019.
Kousik Kundu, Fabrizio Costa, and Rolf Backofen. A graph kernel approach for alignment- free peptide interaction prediction with an application human sh3 domains. Bioinformatics, 29(13):i335-134 2013.
Wenchao Li, Hassen Saidi, Huascar Sanchez, Martin Schäf, and Pascal Schweitzer. Detecting sim- ilar programs via the weisfeiler-leman graph kernel. In International Conference on Software Reuse, pp. 315-330. Springer, 2016.
Eugene M. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial time. In Proceedings of the 1 Annual Symposium on Foundations of Computer Science, SFCS '80, 1980.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. arXiv preprint arXiv: arXiv:/905.1 /136,, 2019.

---

Under review as a conference paper at ICLR 2020
Brendan D. Mckay and Adolfo Piperno. Practical graph isomorphism, ii. J. Symb. Comput., 2014.
Silvio Micali and Zeyuan Allen Zhu. Reconstructing markov processes from independent and anonymous experiments. Discrete Applied Mathematics, 200:108 100:108-122, 2016.
Mchryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. The MIT Press, 2012. ISBN 026201 9780262018258.
Christopher Morris, Nils M Kriege, Kristian Kersting, and Petra Mutzel. Faster kernels for graphs with continuous attributes via hashing. 2016 IEEE 16th International Conference on Data Mining (ICDM), pp. 1095-1100. IEEE, 2016.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4602-4609, 2019.
Nagarajan Natarajan, Inderjit S. Dhillon, Pradeep Ravikumar, and Ambuj Tewari. Cost-sensitive learning with noisy labels. Journal of Machine Learning Research, 18(155):133,, 2018.
Marion Neumann, Roman Garnett, Christian Bauckhage, and Kristian Kersting. Propagation ker- nels: efficient graph kernels from propagated information. Machine Learning, (02(2):209-245 2016.
Giannis Nikolentzos, Giannis Siglidis, and Michalis Vazirgiannis. Graph kernels: A survey. arXiv preprint arXiv: 12218, 2019.
L. Oneto, N. Navarin, M. Donini, S. Ridella, A. Sperduti, F. Aiolli, and D. Anguita. Learning with kernels: A local rademacher complexity-based analysis with application graph kernels. IEEE Transactions on Neural Networks and Learning Systems, 29(10):460-46671 2018.
Luca Oneto, Nicol Navarin, Michele Donini, Alessandro Sperduti, Fabio Aiolli, and Davide An- guita. Measuring the expressivity of graph kernels through statistical learning theory. Neurocom- pul., 268(C):4-16, 2017a.
Luca Oneto, Nicolò Navarin, Michele Donini, Alessandro Sperduti, Fabio Aiolli, and Davide An- guita. Measuring the expressivity of graph kernels through statistical learning theory. Neurocom- puting, 268:4-16, 2017b.
Francesco Orsini, Paolo Frasconi, and Luc De Raedt. Graph invariant kernels. In Twenty-Fourt International Joint Conference on Artificial Intelligence, 2015.
Shirui Pan. A repository of benchmark graph datasets for graph classification, 2018. URL https: 7 crithub..com//hhrruuaana/// httpaa/aaggrppppc_aattettess
Liva Ralaivola, Sanjay Swamidass, Hiroto Saigo, and Pierre Baldi. Graph kernels for chemical informatics. Neural networks, 109311093 2005.
Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do imagenet classifiers generalize to imagenet? arXiv preprint arXiv: /902. 10011 2019.
Kaspar Riesen and Horst Bunke. lam graph database repository for graph based pattern recognition and machine learning. In Joint IAPR International Workshops Statistical Techniques in Pat- tern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR), pp. 287-297. Springer, 2008.
Matthias Rupp and Gisbert Schneider. Graph kernels for molecular similarity. Molecular Informat- ics, 29(4):266-2) 273, 2010.
Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The vapnik-chervonentee dimension of graph and recursive neural networks. Neural Networks, 108:248-255 2018.
Clayton Scott. Calibrated asymmetric surrogate losses. Electron. J. Statist., 6:958-999 1958-992,11 2012.
12

---

Under review as a conference paper at ICLR 2020
Maksim Sharaev, Alexey Artemov, Ekaterina Kondrateva, Sergei Ivanov, Svetlana Sushchinskaya, Alexander Bernstein, Andrzej Cichocki, and Evgeny Burnaev. Learning connectivity patterns via graph kernels for fmrri-based depression diagnostics. In 2018 IEEE International Conference Data Mining Workshops (ICDMW), pp. 308-314. IEEE, 2018.
Nino Shervashidze, S. V.N. Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten M. Borgwardt. Efficient graphlet kemells for large graph comparison. Proceedings of Twelfth International Conference on Artificial Intelligence and Statistics, AISTATS 2009, Clearwater Beach, Florida, USA, April 16-18, 2009, pp. 488 495, 2009.
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten Borg- wardt. Weisfeiler-lhman graph kernels. Journal of Machine Learning Research, 12(Sep):2539- 2561, 201
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mchlhorn, and Karsten M. Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12:2539-
2011b.
Elena Stumm, Christopher Mei, Simon Lacroix, Juan Nieto, Marco Hutter, and Roland Siegwart. Robust visual place recognition with graph kernels. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 4535-4544 2016.
Mahito Sugiyama and Karsten Borgwardt. Halting in random walk kernels. In Advances in neural information processing systems, pp. 1639-1647, 2015.
Jeffrey Sutherland, Lee A O'brien, and Donald F Weaver. Spline-fitting with genetic algorithm: A method for developing classification structure- activity relationships. Journal of chemical in- formation and computer sciences, (3(6))1906-191) 2003.
Saurabh Verma and Zhi-Li Zhang. Stability and generalization of graph convolutional neural net- works. arXiv preprint arXiv: 1905.000001004 2019.
N. Vishwanathan, Nicol N. Schraudolph, Risi Kondor, and Karsten M. Borgwardt. Graph kernels. J. Mach. Learn. Res., 1 11:1201-1242 August 2010. ISSN 1532-4435.
Jianja Wang, Richard C Wilson, and Edwin Hancock. fmri activation network analysis using bose-einstein entropy. In Joint IAPR International Workshops on Statistical Techniques in Pat- tern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR), pp. 218-228. Springer, 2016.
Harry Wiener. Correlation of heats of isomerization, and differences in heats of vaporization of isomers, among the paraffin hydrocarbons. Journal of the American Chemical Sociery, 69(1)): 2636-2638 1947a.
Harry Wiener. Influence of interatomic forces on paraffin properties. The Journal of Chemical Physics, 1561066766776, 1947b.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip $ Yu. A comprehensive survey on graph neural networks. arXiv preprint 0rXiv:/901.0056. 2019.
Keyulu Xu, Weihua Hu. Jure Leskovee, and Stefanic Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: arXiv:1810.00820 2018.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1365-1374. ACM, 2015.
Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zimik, and Jure Leskovec. Gan explainer: A tool for post-hoc explanation of graph neural networks. arXiv preprint /903: 2019.
13

---

Under review as a conference paper at ICLR 2020
A STATISTICS FOR ORIGINAL DATA SETS
Table All original graph data sets. N is the number graphs, C' number of different classes. Avg. Nodes and Avg. Edges is the average number of nodes and edges. N.L. and E.L. indicate if the graphs in a data set contain node or edge labels.
Type
Avg.
Avg. Edges
FIRSTMM DB
Molecular
1377.27
3074.1
Neurnam et 2016
OHSU
Molecular
79
2
82.01
199.66
Pan
KKI
Molecular
83
2
26.96
48.42
+
Fan 2018
Peking_1
Molocular
83
39.31
77.35
+
Pan 20018
MUTAG
Molecular
188
2
17.93
19.79
Brigge & Muizel
2012
MSRC 21C
Vision
209
20
40.28
96.6
+
Ncumaino ct a.
2010
MSRC_9
97.94
Neumann
Cunciform
Molecular
267
21.27
44.8
Kriee
SYNTHETIC
Symtheti
300
100
Ponggon ct 2013
COX2 MD
Molecular
335.12
Krigge
MD
Molecular
306
21.3
225.06
Kriege & Mutzel
2012
PTC MM
Molecular
336
13.97
14.32
Kriege & Muliel
201
PIC.MR
Molecular
14.29
14.69
PTC_FM
Molecular
349
2
14.11
14.48
Kriepe & Multzel
2012
FTC.FR
Molecular
351
14.56
15
Kriege & Mutiell
2012
DHIR_MD
Molecular
393
23.87
283.01
8 Mutiel
Synthie
Symbetic
400
4
95
172.93
Mormi et sb 2016
BZK
Molecular
33.75
38.30
Sutherland et 2003
ER MD
Molecular
446
2
21.33
234.85
& Muizel
COX2
Molocular
467
41.22
43.45
Sutberland ct 2005
MSRC 21
Vision
563
77.52
198.32
Neumann al.
2016
ENZYMES
Molecular
600
32.63
62.14
Borgwardl ct al:
2001
BINARY
Yamardan
PROTEINS
Molecular
1113
39.06
72.82
Borgwardi al. 2005
DD
Molecular
1178
2
284.32
713.66
Shervashiäze et ml 201 la
IMDB-MULTI
Social
1300
13
65.34
Yanardag Vishwanathan
AIDS
Molecular
2000
2
15.69
16.2
Riesen & Bunke 2008
REDDIT-BINARY
Social
2000
2
429.63
497.75
Yanardag Vishwanat
2015
Letler
Molecular
2250
4.67
4.5
Riesen
Letter-low
Molecular
2250
15
4.68
3.13
Kiesen & Bunse
2008
Letter-med
Molccular
2250
4.5
Riesen & Bunke
2008
Fingerpeint
Molecular
2800
4
5.42
4.42
Riesen Hunks
COIL-DEL
Molocular
3000
100
21.54
54.24
Riesen & Bunke
2008
3900
Bunke
NCHI
Molecular
4110
2
29.87
32.3
Shervashudze et
NCT1O9
Molecular
4127
29.68
32.13
Shervashiize et
211
FRANKENSTEIN
Molecular
4337
16.9
17.88
Mutagenicity
Molecular
4337
30.32
30.77
Riesen & Bunke
2008
MUL.IIS
Social
4999
5
508.52
594.87
Yanardag Vishwanathan
2015
COLLAB
Social
5000
74,49
2457.78
Yanardag
Tox21_A ARE
Molecular
7167
2
16.28
16.52
Challenge
2014
Tox2] Laromaaase
Moleculat
7226
17.3
17.79
Challenge
2014
Tox2] [OX21_MMP' MMP
Molecular
7320
2
17.49
17.83
Challenge
Tox21 ER
Molecular
7697
2
17.58
17.94
Challeng
2014
Tox2I_HSI
Molccular
8150
17.04
Challenge
Tox21 AHR
Molecular
8169
2
18.09
18.5
Challenge
[ox2] Box21_PPAME PPAR-gamma
Molecular
8184
17.23
17.55
Challenge
201
__R LBD
8599
Challenge
Tox2]
Molecular
8634
2
17.79
18.19
Challenge
3014
[ox2]_RR ER_
Molecular
8753
18.06
18.47
Challenge
A11
ATADS
Molecular
9091
2
Challenge
Tox2] AR
Molecular
9362
2
18.39
18.34
Challenge
011
REDDIT 12K
Social
11929
391.41
456.89
Yanardag & Vishwanathan
2015
14

---

Under review as a conference paper at ICLR 2020
B ISOMORPHISM METRICS FOR ALL DATA SETS
Table 6: Isomorphic metrics for all data sets. Sorting is based on the proportion of isomorphic
graphs 1% Num. orbits the number of non-trivial orbits. 1P% is the proportion of isomorphic pairs of graphs, Mismatched % is the proportion of mismatched labels.
data set
Size,
Num. orbits
Iso. graphs,
7%
1P%
Mismatched %
SYNTHETIC
300
2
300
100
100
100
Cuncitorm
267
8
267
100
20.46
100
Letter-lww
2250
32
2245
99.78
8.72
96.22
DHFR_MD
393
25
392
99.75
6.87
94.91
COIL-RAG
3900
20
3890)
99.74
25.22
99.31
COX2 MD
303
301
99.34
11.83
98.68
ER_MD
446
442
99.1
5.57
82.74
Fingerprint
2800
69
2774
99.07
16.86
89.29
B2R_MD
306
22
303
99.02
7.16
95.75
Letter-med
2250
39
2226
98.93
8.05
92.93
Letter-high
2250
2200
97.78
3.67
95.91
IMDB-MULTI
1500
1212
80.8
6.39
74.67
TTAD5
9091
1461
6167
67.84
0.09
9.15
Tox21 PPAR-gamma
8184
1265
5513
67.36
0.1
7.77
Tox21 AR
9362
1519
6295
67.24
0.08
8
Tox21 p53
8634
1345
5800
67.18
0.09
11.28
Tox21 AR-LBD
8599
1354
5766
67.05
0.09
6.88
Tox21 MMP
7320
T138
4875
66.6
0.1
18.76
Tox21 I HSE
8150
1218
5425
66.56
0.1
18.02
Tox21 ER LBD
8753
1375
5791
66.16
0.09
12.41
Tox21 ER
7697
1203
5078
65.97
0.09
27.32
Tox21_ AHR
8169
1299
5377
65.82
0.09
15.61
Tox21 aromatase
7226
1084
4727
65.42
0.1
5.07
Tox21ARE
7167
1047
4682
65.33
0.11
26.45
AIDS
2000
371
1259
62.95
0.13
0.35
COX2
467
76
283
60.6
0.6
20.36
IMDE-BINARY BINARY
1000
117
579
57.9
0.67
31.8
FRANKENSTEIN
4337
574
2230
51.42
0.09
30.87
MUTAG
188
31
79
42.02
0.49
6.91
BZR
405
165
40.74
0.6
8.89
PTС
39.29
0.46
23.21
PTC MR
344
40
125
36.34
0.41
25
PTC.FM
349
39
124
35.53
0.39
23.5
DHFR
756
89
250
33.07
0.14
9.13
PTC.RR
351
36
116
33.05
0.37
20.51
Mutagenicity
4337
397
1274
29.38
0.03
13.1
COLLAB
5000
1077
21.54
0.11
COIL-DEL
3900
155
796
20.41
0.06
18.56
PROTEINS
1113
35
151
13.57
0.1
9.07
NCII
4110
225
523
12.73
0.01
1.7
NCI109
4127
222
519
12.58
0.01
1.7
ENZYMES
600
6
10
1.67
0
REDDIT-BINARY BINARY
2000
REDDIT-MULTI-IZK
11929
8
0.14
FIRSTMM DB
41
OHSU
79
O
KKI
83
Peking I
MSRC 21C
209
MSRC_9
221
Synthie
400
0
0
0
21
563
0
DD
1178
0
REDDITMULTTSSK
4999
15

---

Under review as a conference paper at ICLR 2020
C ORBIT SIZE DISTRIBUTION FOR ALL DATA SETS
In the plots 3 the sizes of orbits are presented for each data set. Empty plots correspond to data sets with no isomorphic graphs. Plots with just wo-labels correspond cases when there are no node labels available for the graphs in a data set.
FIRSTMM DB
OHSU
KKI
Number of orbits
wo-iabels latel
wo-labels
wo-ldbwb lab
node- lade--abels
Peking_1
MUTAG
MSRC 21C
Number of orbits
=>- abols
20
wo labels
we label
noce labes
nod: tabels
node tob
15
10
0 2
0
MSRC_9 9
Cuneiform
SYNTHETIC
Number of orbits
bbtls mode-lsbels
2.0
1.00
node-labels
nod Lallleaal
1.5
0.75
1.0
0.50
0.5
0.25
0.0g
60
80
0.
0.099.50
299.75
300.00
300.25 300.50
COX2 MD
BZR MD
PTC MM
Number orbits
labels
3.
20
2
10
1.
10
10
30
0
10
PTC MR
PTC_ FM
PRC
Number of orbits
WC- abels nade-labelk
wD label
wo-ibbel nadelabels
20
20
mode-lnbels
15
10
10
10
2
10
0
8
10
DHFR MD
Synthie
BZR
30
Number of orbits
mo-isbels
nec-ubbll
wo-lebek nodelabele
6.
node-labe's
20
2
10
30 Orbit size
20
40
0
10 Orbit size
15
Orbit size
Figure 3: Distribution of orbits sizes. wo-labels correspond isomorphism without considering the labels. node-labels correspond to isomorphism that considers node labels. Part-1.
16

---

Under review as a conference paper at ICLR 2020
ER MD
COX2
MSRC 21
Number of orbits
10.0
Wo-
wo-kibels
wo-labels
node labels
40
node-labels
node: label
30
0
20
10
0.0
10
20
30
40
10
15
ENZYMES
DHFR
IMDB-BINARY
Number of orbits
wo-label
bbbls
no- po-labeb
80
4
60
60
40
20
9.50
1.75
2.00 PROTEINS
2.25
2.50
2.5
5,0
7.5
10.0
12.5
0
10
30
40
DD
IMDB-MULTI
Number of orbits
wD labeb
we babls
no labeb
20
lablls
node-labels
15
10
%
100 Letter-high
200
300
AIDS
HEDDIT-BINARY
Number of orbits
300
no-labels
labeb
nade-labels
1.5
200
1.0
100
0.5
20
To
15
20
25
0.2.50
1.75
2.00
2.25
2.50
50
100
150
200
Letter-low
Letter-med
Fingerprint
Number of orbits
no-labels
no-labels
60
no- no-labebs
15
10
10
20
%
0g
1o0
00
1000
COIL-DEL
COIL-RAG
NCI1
Number of orbits
100
150
node-labels
100
50
10
20
30
0
500
1000
1500
0
2
4
8
10
Orbit size
Orbit size
Orbit size
Figure 4: Distribution of orbits sizes. Part-2.
17

---

Under review as a conference paper at ICLR 2020
NC
FRANKENSTEIN
Mutagenicity
Number of orbits
wo-labels node-labels
nollabels
wo labds
150
300
node-labels
400
100
200
100
2
REDDIT-MULTI-SK
COLLAB
Tox21. ARE
Number of orbits Number of orbits Number of orbits
no-labels
wo-tabels node-labels
800
100
600
400
200
0
25
50
75 MMP
100
9
20
40
60
Tox21 aromatase
Tox21
Tox21 ER
1000
wo-labels
1000
wo-bbels node-labels
1000
wo-labels node-labels
node-labels
750
750
500
500
500
250
250
%
40
%
60
%
20
Tox21 HSE
Tox21 AHR
Tox21 PPAR-gamma
wollabels node-labels
labels
1000
node-labels
1000
node-labels
750
750
500
500
500
250
250
20
40
60
0
20
40
60
20~
20
70"
60
Tox21
AR-LBD
Tox21 pp3
Tox21 ER LBD
Number of orbits
wo-labels
we-bbee no-bbels
wo-labals
1000
node-labels
1000
node-lbbels
1000
node-labels
500
500
500
0
20
40
%
40 Tox21 1
%
20
40
Tox21_ATAN ATAD5
REDDIT-MULTI 12K
Number of orbits
labels node-labels
lablls node-labels
labels
1000
500
0
20
40
60
%
20
40
60
2.0
2.5
3.0
3.5
4.0
Orbit size
Orbit size
Orbit size
Figure 5: Distribution of orbits sizes. Part-3.
18

---

Under review as a conference paper at ICLR 2020
D ISOMORPHISM METRICS FOR DATA SETS WITH NODE LABELS
Table 7: Isomorphic metrics for data sets with node labels. Sorting is based on the proportion of isomorphic graphs 1%. Num. orbits is the number of non-trivial orbits. IP% is the proportion of isomorphic pairs of graphs, Mismatched % the proportion of mismatched labels. Table does not include data sets with node labels.
data set
Size, N
Num. orbits
Iso. graphs,
1%
17%
Mismatched %
SYNTHETIC
300
300
100
100
100
Cuneiform
267
8
267
100
20.46
100
DHFR MD
393
392
99.75
6.87
94.91
COX2MMD
303
13
301
99.34
11.83
98.68
ER MD
446
442
99.1
5.57
82.74
BZR.M. MD
306
22
303
99.02
7.16
95.75
MUTAG
188
36
19.15
0.14
PTC_FM
349
22
54
15.47
0.08
10.89
PTC.MM
336
50
14.88
0.07
7.74
DHFR
756
39
98
12.96
0.04
3.97
PTC.ER
351
43
12.25
0.05
6.27
PTC.MR
344
19
41
11.92
0.05
6.4
Tox21 ARE
7167
228
820
11.44
0.01
3.91
Tox21 HSE
8150
250
919
11.28
0.01
2.25
Tox21 aromatase
7226
223
805
11.14
0.01
0.77
Tox21 .p53
8634
258
946
10.96
0.01
1.83
Tox21 ER
7697
231
840
10.91
0.01
2.4
COX2
467
25
50
10.71
0.03
1.07
Tox21 PPAR-gamma
8184
227
869
10.62
0.01
0.76
Tox21 MMP
7320
204
770
10.52
0.01
2.19
Tox21 LBD
8753
255
913
10.43
0.01
1.28
Tox21 _R
9362
265
965
10.31
0.01
0.68
Tox21 ATADS
9091
255
924
10.16
0.01
1.04
8599
238
871
10.13
0.01
0.7
BZR
405
16
40
9.88
0.06
0.99
Tox21AAHR
8169
224
795
9.73
0.01
2.07
PROTEINS
1113
21
74
6.65
0.03
2.61
AIDS
2000
22
54
2.7
Mutagenicity
4337
31
75
1.73
0.92
NCII
4110
17
0.41
0.05
ENZYMES
600
2
2
0.33
NCI109
4127
12
0.29
0.05
FIRSTMM
41
0
OHSU
79
KKI
83
Peking
85
MSRC 21C
209
0
0
MSRC
221
MSRC 21
563
0
0
1178
19

---

Under review as a conference paper at ICLR 2020
E
PROOF OF CLAIM 7.1
Proof. From the equation 3 we have:
YYnw acc new) +
Yisol aCc(Y(so) > acc(Y(so) =
aCc(())st)=
seeee
Yeert
new acc( acc(Ynew) [eeel acc Yioo) > aco(Ynew)
Yisol
(Yco))
(est
PROOF OF CLAIM 7.2
Proof. From the definition of the peering model we have:
acc (Ynew) acc 57 (Ynew)
acc (Yis)) S acc (Yiso) = 1
Substituting these into the equation we have: (Ytest) S ac (Y
G EXPERIMENTATION DETAILS
NN model is from Xu et al. 2018) and evaluate it on the data sets from WyTorhh-Goomete (Fey & Lenssen 2019). For each data set we perform 10-fold cross-validation such that each fold evalu- ated 10% of hold-out instances Ytest- For each fold train the model for 350 epochs selecting the final model with the best performance on the validation set (20% from hold-out trained split) all epochs. Additionally we found that for small data set performance during the first epochs can be unstable on the validation set and thus we select our model only after the first 50 epochs. The final model evaluated on the test instances and corresponds NN in the experiments. Peering models NN-PH and NN-P are obtained from NN by replicating the target labels for homogeneous Yiso and non-homogeneous Yiso respectively. Weisfeiler-Lehmaal and Vertex histogram kernels are taken from the code of Sugiyama & Borgwardt (2015). We selected the height of subtree h = 5 for WL kernel. We train an SVM model selecting C' parameter from the range [0.001, 0.01, 0.1, 1, 10).
20

---

Under review as a conference paper at ICLR 2020
H
NEW DATA SETS
Table 8: Statistics for new clean data sets, Retention is the proportion of graphs remaining after cleaning procedure. Min. Class and Max. Class minimum and maximum number of graphs in class. Sorted by retention.
Data set
Retention,
Avg. Nodes
Avg.
Edges
Classes
Min. Class
Max. Class
SYNTHETIC
0
0
0
0
Cunciform
0
0
0
0
0
COIL-RAG
13
0.33
5.77
9.62
7
5
Letter-low
12
0.53
7.17
5.42
5
COX2_MB MD
0.99
30.33
467
2
DHFR_M MD
1.02
25.25
366.25
Letter-med
29
1.29
6,83
5,66
8
10
Fingerprint
51
1.82
14.45
13.12
40
BZR_MD
1.96
14.17
130.17
2
Letter-high
60
2.67
7.03
7.23
32
ER_DD
3.14
18.07
227.36
2
13
IMDB-MULTI
321
21.4
22.35
249.46
85
144
Tox21 ARE
3302
46.07
20.96
21.86
602
2700
Tox21 ER
3560
46.25
22.24
23.29
419
3141
Tox21 MMP
3405
46.52
22.4
23.43
2
618
2787
Tox21 HSE
3814
46.8
21.29
22.28
207
3607
Tox21 p53
4088
47.35
22.62
23.72
3797
Tox21 PPAR-gamma
3877
47.37
21.91
22.91
120
3757
Tox21 ATADS
4312
47.43
22.52
23.61
168
4144
Tox21 AR-LBD
4134
48.08
22.41
23.48
150
3984
Tox21_AM
4506
48.13
22.93
24.05
189
4317
Tox21 LAHR
3935
48.17
22.88
23,98
3445
Tox21 LBD
4224
48.26
22.69
23,8
193
4031
Tox21 aromatase
3524
48.77
22.24
23,22
3290
AMDB-BINARY
493
24.08
221.96
232
COX2
237
50.75
42.14
44.43
68
169
AIDS
1110
55.5
18.22
19.1
FRANKENSTEIN
2448
56.44
20.78
22.35
1020
1428
PTC MM
226
67.26
17.04
17.74
77
149
BZR
276
68.15
36.25
38.81
72
PTC MR
235
68.31
17.23
17.97
96
139
FM
242
69.34
16.96
17.66
85
137
MUTAG
135
71.81
18.85
20.84
42
93
PRC_FR
253
72.08
17.11
17.86
86
DHER
578
76.46
43.37
45.53
373
Mutagenicity
3335
76.9
32.96
34,16
1484
1851
COIL-DEL
3133
80.33
25.05
64.26
98
39
COLLAB
4064
81.28
76.94
4667.92
3
770
2289
PROTEINS
975
87.6
43.41
81.04
2
343
632
NC11
3785
92.09
29.84
32.37
2
1781
2004
NC1109
3801
92.1
29.66
32.22
2
1801
2000
ENZYMES
595
99.17
32.48
62.17
6
98
100
REDDIT-BINARY
1998
99.9
430.04
996.488
2
998
1000
REDDIT-MULTT-12K
11917
99.9
391.79
914.68
11
513
2586
FIRSTMM DB
41
100
1377.27
3073.93
11
6
OHSU
79
100
82.01
199.66
2
35
44
KKI
83
100
26.96
48.42
37
46
Peking
85
100
39.31
77.35
2
36
49
MSRC 21C
209
100
40.28
96.6
17
29
MSRC
221
100
40.58
97.94
8
19
30
Synthie
400
100
91.6
202. 18
4
90
110
MSRC 21
563
100
77.32
198.32
20
10
34
DD
1178
100
284.32
715.66
2
487
691
REDDIT-UUTT-SK
4999
100
508.51
1189.75
5
999
1000
21

---

Under review as a conference paper at ICLR 2020
1 PROOF OF THEOREM 6.1
Proof. Let us prove T'eorrm 6.1 We denote by L = {(x,8) - L(f(x), E F) composite
loss class. For any L E L we get that
EpL EDuL = EpL EpuL EpuL - EDuL v
S Ep L] + (BpuL- EDuL).
(5)
Since any L E C is bounded from above by 1 for the first term in equation
we obtain
Ep u) - (eg-(w))(y=+))) + Eyg- (w)
9+ (w)T + g- (w) x).
Thanks to McDiarmid'd concentration inequality Mohri et al.
2012). applied to the function class get the upper bound on the
Cu {uL L E L}, with probability 8, for D p
excess risk
sup(EEul. - EDUL) - (R.( + max ((1 + g+ (w)),, + (1 (log & LEC
2R + (2 (2+ (w)) (log 8))
Let us find relation between R2 (L,) and Rv Here denote by 2; pair 2; (It, (1). By the definition (see Mohri et al. (2012) the empirical Rademacher complexity
N
RD((.))
1 = = E. sup
Σ
o (())
N
LEC
i=1
o,L(Z)) (+(
Eg sup Σ o,L(Zz) + g-(w)
Bg sup L.C.
Eg sup Σ
ocL(Zi) S
N
LEC 1:g1=11
N
LER 1yp=-1
( + (4) E, sup
Σ
o,L(2s)
+ 9- w
E sup Σ
a,L((z)).
N
LEC E:g
N
LEL k:ys
Since we use the zero-one loss, then
ES sup LEC iW=+1
Σ
( +1}, B sup Σ LEE fy==-1
o;L(2i) S # v -1.
The Rademacher complexity
(C,) Ro((.) S EDapx [Ro(C) + (+(w)
#(i: y/s +1}+
N
9- (w) +
# (i: :4:::-4 = -13 Rx((f) + (w) + (w) T).
N
Using the fact that (x) Rxx substituting inequalities 6 and 8 into equation
we get
that
sup SEF
v))
y) v)(([()),w)) < (g+ (w) g- (w)(1 - T)) +
+ (2 + (w)) / (log d
22


Reviews:
[{"review_id": "SklrAvRctS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors discuss here the problem of isomorphism bias in graph dataset, i.e. the overfitting effect in learning networks whenever graph isomorphism features are incorporated within the model. This is a bias which jeopardises the validity and the reproducibility of several studies, and it is theoretically analogous to data leakage effects.\nThe authors fairly discuss the problem in the introduction, with a good coverage of the related literature; the background theory is reasonably discussed, although is not very deep. The experimental part is extensive and well described, and it shows the overfitting effect very clearly. However, the novelty of the work is limited, and also the proposed solutions cannot be claimed as superior to other approaches, due to the small improvement in accuracy.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "SJlFHnO6cr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work probes graph classification datasets for isomorphism bias. They find substantial amount of bias in some datasets and show that they suffer from data leakage. They further perform a more fine-grained evaluation taking into consideration the node/edge types which reduce the perceived effects. They also provide some recommendations for measuring the 'right metrics' and release clean versions of the considered datasets.\n\nStrengths:\n- The methodology is rigorous and the datasets considered is extensive\n- The paper is well written\n\nConcerns:\n- Isomorphism is not necessarily a bad thing in graph classification tasks. Especially in chemistry where a bond decides if a compound is poisonous or not. Also, as the authors themselves mention, taking node/edge labels decrease the isomorphism in most datasets.\n- The results and recommendations presented in the paper are intuitive and somewhat trivial\n- I am not sure if ICLR is the right venue for this work", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "SJeT-mmc5S", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents three contributions: (a) the observation that there’s train-to-test leakage in many graph classification datasets (under isomorphism equivalence), (b) what appears to be a theoretically motivated way of improving scores on such datasets, by focusing on solving the examples that are isomorphic with training instances, and (c) a recommendation to remove such leakage from test sets. I don’t think the paper meets the ICLR bar. While (a) is very interesting, and an important contribution, (b) and (c) are contradictory. The recommendation (c) is a bit of a no-brainer, and Property 6.1 and Theorem 6.1, providing the substance of (b), are near-trivial. \n\nMissing reference: Bordes et al. (2013) and Toutanova et al. (2015) show there’s train-to-test leakage (under isomorphism equivalence) in the FB15K dataset. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}, {"review_id": "BJxu9Rwn9S", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper is concerned with the presence of isomorphism bias in commonly used graph learning benchmarks. In particular, the paper analyzes the amount of isomorphic graphs in 54 graph datasets and evaluates the performance of three graph classification methods under two isomorphism settings.\n\nCareful analyses of commonly used benchmarks can be important contributions that provide new insights into the performance of state-of-the-art models. The present paper's results on graph isomorphism properties can indeed be valuable for the ablation of models and testing their performance with regard to this property. I also found the relatively high label disagreements on some datasets (even under stronger isomorphism constraints) to be a surprising and useful result.\n\nHowever, the main assumption of the paper -- which equates the quality of a graph learning benchmark with the amount of isomorphic graphs that it contains, i.e., the lower the better -- seems questionable.\n\nThe paper argues that isomorphic graphs are akin to duplicate images in computer vision and should be removed from a dataset. While completely identical graphs are certainly problematic, the case seems different for isomorphic graphs. In the latter, a learning method is required to identify the correct bijection form V_1 to V_2 which is a non-trivial task. Testing on isomorphic graphs evaluates the ability of a model to infer these equivalence classes from data which is an important property. Moreover, being able to capture the equivalence relation can be important for various graph learning tasks, e.g., to facilitate that two topologically equivalent graphs are be classified similarly.  Going back to the computer vision analogy: it seems a more adequate comparison for graph isomorphism would be translation and scale invariance which are certainly desirable properties for CV models.\n\nIn addition, the dataset analysis could also be improved. For instance, the SYNTHETIC dataset includes continuous node attributes that are essential for classification and make the graphs non-isomorphic (when considering, for instance, each attribute vector as a unique node label). However, the attributes are not considered in the analysis what leads to a large number of isomorphic graphs. On a side note: the paper also incorrectly attributes the SYNTHETIC dataset to (Morris et al, 2016), but it is in fact from [1]. The synthetic dataset of Morris et al (SYNTHIE) does not consist of isomorphic graphs, while the SYNTHETIC dataset of [1] does so intentionally.\n\nThe results of Section 5 seem also not very surprising: After removing node labels, it is expected that the number of isomorphic graphs increases since a discriminating feature has been removed. Moreover, when accounting for node labels, many standard benchmarks seem to consist of significantly less isomorphic and mismatched graphs (as can be seen in the appendix).\n\nSince graph isomorphism != graph identity, the assumption Y_iso \\sub Y_train in Property 6 seems also not appropriate. The results of Theorem 6.1 on the other hand seems straightforward and would hold for any classification task for which the true label for an equivalence class of instances is known.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Thanks to reviewers and authors for an interesting discussion. It seems the central question is whether learning to identify correct bijections should be part of graph classification problems, or whether this leads to bias and overfitting. Reviews are generally negative, putting this in the lower third of the submissions. The paper, however, inspired an interesting discussion, and I would encourage the authors to continue this line of work, addressing the question of bias and overfitting more directly, possibly going beyond dataset evaluation and, for example, thinking about how to evaluate whether training on non-isomorphic graphs leads to better off-training set generalization.
Decision: Reject