Graph matching applications in high level information fusion
Sambhoos, Kedar P
MetadataShow full item record
The intent of this research is to show the progression of Level 2/3 fusion capabilities through a new class of models and algorithms in graph matching. The problem today is often not lack of data, but instead, lack of information and data overload. Graph matching algorithms help us solve this problem by identifying meaningful patterns in voluminous amounts of data to provide information. In this research we investigated the classical graph matching technique of subgraph isomorphism. The inexact graph matching is used to identify meaningful patterns in voluminous amounts of data. This heuristic is based on the popular branch-and-bound technique with constraints on breadth and depth. A complete implementation of a heuristic approach (since the problem under consideration is NP-hard) using an inexact isomorphism technique has been used. The heuristic approach is called Tru ncated S earch T ree algorithm ( TruST ), where the state space of the problem is constrained using breath and depth control parameters. The breath and depth control parameters are then studied using design of experiment based inferential statistics. To reduce the dimensionality of the matches found, the results are grouped using a clustering algorithm. The K-means clustering algorithm is used in this research which requires distances to be measured between two different graphs. To determine the similarity between a pair of matched subgraphs a novel hypercube distance measure is used. Hypercube distance is based on the concept of mutual subsethood, which measures the degree to which a graph is similar to another graph. This measure is then compared with a relatively new fuzzy Hamming distance measure. Fuzzy Hamming distance measure is the (fuzzy) number of components along which the two graphs are different. To identify the important nodes and links in the data graph, the clustered subgraphs are then fused together. The aggregation helps reduce the analysts area of concentration to a small region of the data graph. The subgraph matches and the aggregated results represent the information found for the given pattern in the data graph. This information is limited just to the pattern and hence won't represent anything more. But in most of the situations there is a need to find more information than is available in a pattern. Patterns act as a starting point to find something within a network. So, to find the information represented by a subgraph match within a given data graph we calculate the neighborhood structure. Here, we present a measure of neighborhood value which is based on the connectivity and closeness of periphery nodes. The neighborhood score is used to calculate the neighborhood structure of subgraph match and the aggregated clusters. Later aggregating all the neighborhood scores for a subgraph match, we rank the matches. Finally, a software implementation of the procedure is being completed with very encouraging numerical results.