O'Reilly logo

Analysis of Complex Networks by Frank Emmert-Streib, Matthias Dehmer

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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*, ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required