Analysis of Complex Networks

6.5 Experimental Evaluation

Two different experiments are described in this section in order to demonstrate the feasibility of (suboptimal) GED for graph-based object classification. First, GED is computed with optimal and suboptimal methods. A comparison of the computation time and the classification accuracy using a nearest-neighbor classifier is carried out. In the second experiment the suboptimal GEDs as computed for the first experiment are used for the dissimilarity embedding graph kernel described in Section 6.4.3.

6.5.1 Optimal vs. Suboptimal Graph Edit Distance

In our experiments we divide each database into three disjoint subsets, viz. the training, the validation, and the test set. The elements of the training set are used as prototypes in the NN classifier. The validation set is used to determine the values of the meta parameters τ_node, which correspond to the cost of a node deletion or insertion, and τ_edge, which corresponds to the costs of an edge deletion or insertion. For all considered graph data sets node and edge labels are integer numbers, real numbers, real vectors, or strings, and the substitution cost of a pair of labels is given by a suitable distance measure (Euclidean distance or string edit distance [58]). Finally, the parameter pair that leads to the highest classification accuracy on the validation set is used on the independent test set to perform GED computation and NN classification.

We use three algorithms for GED computation, viz. Heuristic-A*, ...