Title: Significance of Side Information in the Graph Matching Problem,
Abstract: Percolation based graph matching algorithms rely on the availability of seed
vertex pairs as side information to efficiently match users across networks.
Although such algorithms work well in practice, there are other types of side
information available which are potentially useful to an attacker. In this
paper, we consider the problem of matching two correlated graphs when an
attacker has access to side information, either in the form of community labels
or an imperfect initial matching. In the former case, we propose a naive graph
matching algorithm by introducing the community degree vectors which harness
the information from community labels in an efficient manner. Furthermore, we
analyze a variant of the basic percolation algorithm proposed in literature for
graphs with community structure. In the latter case, we propose a novel
percolation algorithm with two thresholds which uses an imperfect matching as
input to match correlated graphs.
We evaluate the proposed algorithms on synthetic as well as real world
datasets using various experiments. The experimental results demonstrate the
importance of communities as side information especially when the number of
seeds is small and the networks are weakly correlated.