This page is under construction...

Algorithm for Structural Graph Matching Via Basis Graphs The Basis-Graph approach uses small graphs to characterize the structure of input 'data graphs'. (The Basis-Graph approach is new and this page is still under construction). The image on the left is an example of a Basis Graph. It is rooted at the green (zero) node.

To describe the local structure of a data graph, a Basis-Graph is rooted at a given node and then placed onto the graph in a depth-first manner. This placement is subject to the constraints of the structure of the Basis-Graph and the data graph. The AVI file (above right) illustrates the placement process. The placement process requires an amount of computational effort bounded by N^V (worst-case), for an N-node data graph and a V-node Basis-Graph. Basis-Graphs with 4-6 nodes have been used in current studies, with data graphs up to 50-100 nodes. After enumerating possible positions for a Basis-Graph, instances of the Basis-Graph are overlayed onto the data graph. Instances do not overlap. Nodes of the Basis-Graph instances are placed in the order of most commonly occuring positions that were recorded during the depth-first placement. Ties halt placement and instances may be partial.

The highlighted portion of the above graph describes a local neighborhood, rooted at the green node. The neighborhood is the induced subgraph of all the data graph nodes touched by instances of the Basis Graph nodes and is invariant with respect to node order. Subsequent processing with the Basis-Graph method describes local graph structure using this type of neighborhood. This serves as a means to establish similarity between the nodes of two data graphs.

The Basis-Graph Algorithm has been developed by: