  Graph edit distance / similarity is widely used in many tasks, such as graph
similarity search, binary function analysis, and graph clustering. However,
computing the exact graph edit distance (GED) or maximum common subgraph (MCS)
between two graphs is known to be NP-hard. In this paper, we propose the
hierarchical graph matching network (HGMN), which learns to compute graph
similarity from data. HGMN is motivated by the observation that two similar
graphs should also be similar when they are compressed into more compact
graphs. HGMN utilizes multiple stages of hierarchical clustering to organize a
graph into successively more compact graphs. At each stage, the earth mover
distance (EMD) is adopted to obtain a one-to-one mapping between the nodes in
two graphs (on which graph similarity is to be computed), and a correlation
matrix is also derived from the embeddings of the nodes in the two graphs. The
correlation matrices from all stages are used as input for a convolutional
neural network (CNN), which is trained to predict graph similarity by
minimizing the mean squared error (MSE). Experimental evaluation on 4 datasets
in different domains and 4 performance metrics shows that HGMN consistently
outperforms existing baselines in the accuracy of graph similarity
approximation.
