| dc.description.abstract | We proposed singular value-based sensitivity analysis and self-similarity studies to compare graph-isomorphism algorithms.
The SimRank method is found to be an application of the power method and is not sensitive to noise in any direction. Therefore, it is not robust for 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 were experimented on the same undirected graph and checked for self-similarity with noise. None of the methods resulted in a difference in the similarity matrix proportional to the noise in the similarity matrix, except in the case of the largest singular vector. As expected, probabilistic methods are not robust to noise in any direction except for the largest singular vector. The addition of noise in the adjacency matrix causes the random walk (probabilistic algorithm) to 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 the case of full algebraic methods. So, the similarity between nodes changes drastically. Thus, probabilistic methods are ultra-sensitive to noise in most directions and do not result in a difference in the similarity matrix proportional to the noise.
Proposed full algebraic methods were experimented on the same undirected graph. Both methods are almost equally sensitive to noise in all directions and result in a difference in the similarity matrix proportional to the 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, the shortest paths matching method and the eigenvector matching method—result in differences in similarity scores proportional to the noise added in the adjacency matrix. Therefore, it is reliable to use full algebraic methods, which are robust and equally sensitive to noise in every direction. | |
