﻿ Maths of Planet Earth | Limitless Applications

A planet organized by humans

Published on September 26th, 2013 | by Emily Corbett

0

# Random Graph Prototypes for Biometric Graphs

In this project, we attempt to match graphs obtained from fingerprint scans by comparing how different each graph is against another set of graphs called prototype graphs. The graph is embedded into an n-dimensional vector space, where each axis represents the graph’s distance from each member of the prototype set. We refer to this space as the dissimilarity space. The intuition is if two graphs are similar (ie obtained from the same fingerprint), their dissimilarity against the set of prototype graphs will be similar too and thus they will be close in the dissimilarity space. The opposite should hold true too, that is two graphs obtained from different fingerprints won’t be close in the dissimilarity space. This method of comparing graphs has been shown to perform well by Reisen and Bunke (2010).

Their research demonstrated that prototype graphs must be chosen carefully to ensure success. They only used one algorithm, the graph edit distance, to measure how different each graph is from the prototype set. The graph edit distance is a function that assigns a cost to how many changes need to be applied to one graph to transform it into another. A large graph edit distance suggests that two graphs are very dissimilar and vice versa. We attempt to find out if randomly generated graphs are successful for use as prototype graphs, and use another method of measuring graph distance to compare graphs against the prototype set. We use the square root distance which assigns a score according to number of matched nodes, edges or both between two graphs.

By looking at the number of nodes, edges and the way positions of the nodes would occur in the set of fingerprint data, a set of randomly generated graphs that simulated the way fingerprint graphs look was generated for use as prototype graphs. Using a set of graphs obtained from fingerprints in previous research, the fingerprints were embedded into the dissimilarity space using the above graph distance measures. Various vector space distance measures, such as Euclidean distance and vector angular distance, were used to measure the distance in the dissimilarity space. The Euclidean distance is an extension of the Pythagoras theorem to higher dimensional space. The vector angular distance assigns a score to the angle between the two points in the dissimilarity space. A large angle suggests the two points have a great distance between them and vice versa.

Using a prototype set size of 200, this method did not offer a reliable way to separate between imposter and genuine matches. The graph edit distance, combined with the Euclidean distance, offered the best performance. The results are worse using smaller prototype set sizes. The results suggest that larger prototype set sizes such as 500-1000 may separate between genuine and imposter matches, but this process would require more powerful computers as the embedding is a computationally expensive exercise.

[subscribe2]