A PCA approach for fast retrieval of structural patterns in attributed graphs

Attributed graph (AG) is a useful data structure for representing complex p atterns in a wide range of applications such as computer vision, image data base retrieval, and other knowledge representation tasks where similar or e xact corresponding structural patterns must be found. Existing methods for attributed graph matching (AGM) often suffer from the combinatorial problem whereby the execution cost for finding an exact or similar match is expone ntially related to the number of nodes the AG contains. In this paper, the square matching error of two AGs subject to permutations is approximately r elaxed to a square matching error of two AGs subject to orthogonal transfor mations. Hence, the principal component analysis (PCA) algorithm can be use d for the fast computation of the approximate matching error, with a consid erably reduced execution complexity. Experiments demonstrate that this meth od works well and is robust against noise and other simple types of transfo rmations.