Some Algebraic Aspects Of Graph Similarity Algorithms

Abstract

We proposed singular values-based sensitivity analysis and self-similarity studies to compare graph-isomorphism algorithms. SimRank method is found to be an application of power method and is not sensitive to noise in any direction. So it is not robust to use. The node matching procedure can be applied to pairs of isomorphic graphs to generate self-similarity matrices; in exploratory tests, an isomorphic mapping is almost always among the maximum weight matches. Probabilistic methods are experimented on the same undirected graph and checked self-similarity with noise: None of the methods results in a difference of similarity matrix proportional to noise in the similarity matrix except in case of largest singular vector. As expected, probabilistic methods are not robust to noise in any direction except for largest singular vector. An addition of noise in adjacency matrix makes random walk (probabilistic algorithm) select the higher weighted edge, changing the sequence of nodes on the paths. In turn, it does not take the whole graph structure into account as in case of full algebraic methods. So the similarity between nodes changes drastically. So, probabilistic methods are ultra-sensitive to noise in most of the directions and do not result in difference of similarity matrix proportional to noise. Proposed full algebraic methods are experimented on same undirected graph: Both the methods are almost equally sensitive to noise in all directions and result in difference of similarity matrix proportional to noise. On the other hand, full algebraic methods take into account the whole graph structure and are equally sensitive to noise in every direction and are robust. Both the proposed methods namely shortest paths matching method and the eigenvector matching method result in difference of similarity scores proportional to noise added in the adjacency matrix. So, it is reliable to use full algebraic methods which are robust and equally sensitive to noise in every direction.