This paper addresses the challenging problem of retrieval and matching of graph structured objects, and makes two key contributions. First, we demonstrate how Graph Neural Networks (GNN), which have emerged as an effective model for various supervised prediction problems defined on structured data, can be trained to produce embedding of graphs in vector spaces that enables efficient similarity reasoning. Second, we propose a novel Graph Matching Network model that, given a pair of graphs as input, computes a similarity score between them by jointly reasoning on the pair through a new cross-graph attention-based matching mechanism. We demonstrate the effectiveness of our models on different domains including the challenging problem of control-flow-graph based function similarity search that plays an important role in the detection of vulnerabilities in software systems. The experimental analysis demonstrates that our models are not only able to exploit structure in the context of similarity learning but they can also outperform domain-specific baseline systems that have been carefully hand-engineered for these problems.
The authors present two methods for learning a similarity score between pairs of graphs. They first is to use a shared GNN for each graph to produce independent graph embeddings on which a similarity score is computed. The authors improve this model using pairs of graphs as input and utilizing a cross-graph attention-mechanism in combination with graph convolution. The proposed approach is evaluated on synthetic and real world tasks. It is clearly shown that the proposed approach of cross-graph attention is useful for the given task (at the cost of extra computation).
A main contribution of the article is that ideas from graph matching are introduced to graph neural networks and it is clearly shown that this is beneficial. However, in my opinion the intuition, effect and limitations of the cross-graph attention mechanism should be described in more detail. I like the visualizations of the cross-graph attention, which gives the impression that the process converges to a bijection between the nodes. However, this is not the case for graphs with symmetries (automorphisms); consider, e.g., two star graphs. A discussion of such examples would be helpful and would make the concept of cross-graph attention clearer.
The experimental comparison is largely convincing. However, the proposed approach is motivated by graph matching and a connection to the graph edit distance is implied. However, in the experimental comparison graph kernels are used as baseline. I would like to suggest to also use a simple heuristics for the graph edit distance as a baseline (Riesen, Bunke. Approximate graph edit distance computation by means of bipartite graph matching. Image and Vision Computing, 27(7), 2009).
There are several other questions that have not been sufficiently addressed in the article.
* In Eq. 3, self-attention is used to compute graph level representations to "only focus on important nodes in the graph". How can this be reconciled with the idea of measuring similarities across the whole graph? Can you give more insights in how the attention coefficients vary for positive as well as negative examples? How much does the self-attention affects the performance of the model in contrast to mean or sum aggregation?
* Why do you chose the cross-graph similarity to be non-trainable? Might there be any benefits in doing so?
* The note on page 5 is misleading because two isomorphic graphs will lead to identical representations even if communication is not reduced to zero vectors (this happens neither theoretically nor in practice).
* Although theoretical complexity of the proposed approach is mentioned, how much slower is the proposed approach in practice? As similarity is computed for every pair of nodes across two graphs, the proposed approach, as you said, will not scale. In practice, how would one solve this problem given two very large graphs which do not fit into GPU memory? To what extent can sampling strategies be used (e.g., from GraphSAGE)? Some discussion on this would be very fruitful.
In summary, I think that this is an interesting article, which can be accepted for ICLR provided that the cross-graph attention mechanism is discussed in more detail.
Minor remarks:
* p3: The references provided for the graph edit distance in fact consider the (more specific) maximum common subgraph problem.