LeRP Algorithm for Determining Subgraph Isomorphism The 'LeRP' algorithm determines subgraph isomorphism for attributed graphs based on counts of Length-R Paths. The algorithm provides a good approximation to the maximal isomorphic subgraph. The paradigm associated with the LeRP algorithm differs fundamentally from other approaches. When comparing structural similarity it uses a neighborhood of nodes, which varies in size dynamically. This approach provides sufficient evidence of similarity to permit LeRP to form a node-to-node mapping in just a few iterations. LeRP requires polynomial effort for each of these iterations. And, just three iterations were used for all of the 32,000 simulated trials reported. Results from an image registration application are also presented. We demonstrate that LeRP does not need a high dynamic range of coloring to perform well. For example, LeRP can input 50-node and 100-node graphs that contain a common 50-node subgraph, and then compute a matching subgraph having 49.74 +/- 0.46 nodes (mean +/- one standard deviation). This takes from 0.4 to 0.5 seconds on a standard workstation. In this example, 100 trials were evaluated and graphs had discrete coloring with a dynamic range of 4 (for nodes and edges). Results from an image registration application are also available. A more extensive discussion is also available, as are comparisons and some background information on similar techniques. Test Results from LeRP The effect of structural errors on the number of nodes remaining in a matched subgraph is presented below. Contour lines show the percentage of nodes in the matched subgraph. The horizontal axis gives the percentage of nodes that were removed from one of the two input graphs (along with incident edges).

Contour plot giving percentage of nodes that remain in matched subgraph. Results are very near maximal in size, even with a very modest dynamic range of coloring. Plot summarizes 9600 trials of 100 node graphs. Color values are discrete. Model A graphs were used with a 10% probability of an edge. The '90' contour line represents an ideal result. This shows that when 10% of the nodes were dropped, 90% remained in the match. Because the line is completely vertical, it means that node and edge coloring was not necessary in order to maintain the 90% match. Examining the plot, when 20% of the nodes are removed some coloring is needed to aide the matching process. In this case a dynamic range of two is needed - that's NOT MUCH! Trials with 30-50% corruption need a dynamic range of approximately three. The above results are considered to be quite good. These indicate that *very little* coloring is needed in order to obtain near-maximal matching performance.

These results indicate a low reliance on graph coloring !

The LeRP Algorithm has been developed by: