Finding graph medians using graph embedding techniques

Graph theory applications are frequently used in image processing, computer vision, bioinformatics, data mining and artificial intelligence related works. On the other hand, representing objects with graphs and matching the images are important part of object recognitions applications. In most of sample image data, images have a lot of noise caused by natural conditions and the error levels in the final results are high. When each image is represented by a graph, matching problem inherently turns to be the same as graph comparison. Since the amount of data is huge and the graph comparison is costly, approximation algorithms are used to decrease the total cost. To compare the given graphs, for each group of graphs, a representative is selected. It is anticipated that, comparing the graph only with the representative graphs gives faster results and the results are tolerably close to the exact truth. In the previous works, to compare the graphs, mapping of each graph in the graph space into a vector in the vector space and then working on the vector space with minimum cost is used. In this work, for each data class we have, each graph in the set is mapped to geometric space by using isomorphic l_1 norm (Manhattan Distance metric), so that, the data lose is minimum. Consequently, the cost of finding the representative graph is decreased and the data lose is kept at the minimum by using Caterpillar Decomposition technique. Differently from the previous works, each point in the geometric space represents a node in the graph. Thus, the data lose is lowered. In the vector space, K-Means Algorithm is used to find the representative graph. To compare the representative points set with the graphs, 25 different distance metric calculations of Hausdorff Distance Algorithm is used. This working mechanism makes it possible to have faster results with minimum error level.