Finally, we test the effect of filter graph distances in a graph classification task. We explore five different benchmark datasets: BZR [1]}, MUTAG [2]}, ENZYMES, PROTEIN [3]} and AIDS. From each dataset, we sample 100 graphs, use fGOT to align them and to compute normalised pairwise distances, and then perform a simple non-parametric 1-NN classification. We repeat this experiment 30 times and report the result in terms of the mean and standard deviation of the classification accuracy. We compare several variants of fGOT, emphasising the flexibility of the method and the benefits this flexibility can bring when comparing datasets of different nature. The filters in comparison are as follows: \(g_1(L) = \sqrt{L\dagger }\) , \(g_2(L) = L^2\) , \(g_3(L) = e^{-0.8 L}\) , \(g_4(L) = \sqrt{L\dagger } + L^2\) , \(g_5(L) = \sqrt{L\dagger } + e^{-0.8 L}\) , \(g_6(L) = L^2 + e^{-0.8 L}\) . These variants of fGOT are further compared to several state-of-the-art graph alignment algorithms: GW [4]}, [5]}, GA [6]}, IPFP [7]} and RRWM [8]}. As shown in Table REF , a high-pass filter (eg. \(g_2(L)\) ) will have a higher classification accuracy on a dataset with local changes, such as BZR. Conversely, a low-pass filter (eg. \(g_1(L), g_3(L)\) ) will perform better in a dataset with strong global differences, such as AIDS. This reinforces the value of the flexibility that fGOT offers, and allows us to choose the right distance criteria for our data.
Even in the more challenging task of 6-class classification (ENZYMES), the fGOT distances seem to be more relevant, even though we note that 1-NN classification is probably too simplistic to solve such difficult tasks. Finally, composite filters (\(g_4(L), g_5(L), g_6(L)\) ), covering both low and high frequencies, perform competitively on all observed datasets, suggesting their efficiency in retaining different captured effects. This makes them general enough to use on data for which we might not have a clear filter preference, or when we are unaware of the nature and properties of our graphs.
