Abstract: Graph similarity computation is one of the core operations in many graph related tasks such as graph similarity search, graph classification, graph clustering, etc. Since computing the exact distance/similarity between two graphs is typically NP-hard, based on the neural network, an Adaptive Structure Aware Pooling graph Matching Network (ASAPMM) model is proposed. ASAPMN calculates the similarity between any pair of graph structures in an end-to-end way. In particular, ASAPMN utilizes a novel self-attention network along with a modified GNN formulation to capture the importance of each node in a given graph. It also learns a sparse soft cluster assignment for nodes at each layer to effectively pool the subgraphs to form the pooled graph. On the pooled graph pairs, a node-graph match- ing network is used to effectively learn cross-level interactions between each node of one graph and the other whole graph. Comprehensive experiments on four public datasets empirically demonstrate that our proposed model can outperform state-of-the-art baselines with different gains for graph-graph classification and regression tasks. 

Key words: graph similarity computation, graph pooling, graph matching, attention mechanism