Iteratively Refined Early Interaction Alignment for Subgraph Matching based Graph Retrieval

We thank the reviewer for their insightful review. The weaknesses raised in the review are addressed below.

The datasets used in the experiments are relatively small, with at most ~20 nodes.

In early experiments, we found relatively small size of query graphs to actually present more challenge to the learner. Given our distant supervision, there are a larger number of promising alignments between query and corpus graphs that may lead to the relevant supervision.

During the rebuttal, we performed experiments with graph pairs generated from the Cox2 dataset. Here, we considered 100 query graphs with $|V|\in[25,35]$, and 500 corpus graphs with $|V|\in[40,50]$. The following table shows the results.

We observe that our method EinsMatch (Edge) Lazy outperforms the baselines significantly. The node variant of our model is marginally outperformed by IsoNet (Node).

It would be interesting to see the transfer ability of the learned model across datasets, e.g. training on PTC and testing on AIDS, to see how the proposed model would handle such challenging but realistic scenarios.

During the rebuttal period, we performed experiments evaluating the transfer ability of the learned models across datasets. In particular, we chose the weights for each model trained using the AIDS and Mutag datasets respectively and evaluated them on all six datasets. The results are shown below. We observe that despite a zero-shot transfer from one of the datasets to all others, variants of EinsMatch show the best accuracy.

Models Trained on AIDS

Models Trained on Mutag

We thank the reviewer for their insightful feedback. The questions raised in the review are addressed below.

Any related work indicating early interaction is good?

The GMN paper itself provides some evidence: GMN-match (early cross-graph interaction) is slower but convincingly superior in terms of accuracy to GMN-embed (late interaction between whole-graph representations). Other domains provide strong supporting evidence [a,b]. E.g., in textual entailment (NLI) tasks [b], where we need to classify if sentence s1 implies sentence s2, late comparison of (say) transformer-based embeddings of the two sentences, computed separately, is convincingly beaten by injecting s1 concat s2 into a comparable transformer and fine-tuning a classification head for the NLI task.

[a] A. Lai and J. Hockenmaier. Learning to predict denotational probabilities for modeling entailment.

[b] Entailment as Few-Shot Learner. Sinong Wang, Han Fang, Madian Khabsa, Hanzi Mao, Hao Ma. arXiv:2104.14690v1

In line 124 $A _q\le PA _c P^{\top}$ is a bit confusing.

By $A _q\le PA _c P^{\top}$, we mean the constraint holds true for each entry, i.e., $A _q[u,v]\le (PA _c P^{\top})[u,v]$ for all u,v.

Suppose $A _q$ is the node-node adjacency matrix of the query graph and $A _c$ is the node-node adjacency matrix of the corpus graph. Suppose, we could find a permutation $P$ of the node numbering (i.e., rows and columns) of $A _c$, which is easily verified as $P A _c P^T$, then $G _q\subseteq G _c$ implies that every edge in $A _q$ will also be present in $P A _c P^T$. In other words, if $A _q[u,v]=1$ then $(P A _c P^T)[u,v]$ must also be 1. This leads to the stated inequality.

Eq 5: the sign of $\tau$

Yes, we indeed want to make the entropy of $P$ a bit higher as this allows us to convert the hard permutation matrix into a smooth doubly stochastic matrix. To gain basic intuition into this, consider the argmax to softmax conversion. The selection $\max _i a _i$, given a vector of real numbers $\vec{a}$, is rewritten as $\max _{\vec{z}\in \Delta} \vec{z} \cdot \vec{a}$, where $\Delta$ is the unit simplex ($\sum _i z _i =1$). Adding a maximizer of the entropy of $z$ readily yields the softmax function. Just like adding an entropy maximizer turns a vector of logits into a softmax distribution, adding an entropy maximizer turns a matrix of logits into a doubly stochastic soft permutation. For technical details, see Cuturi’s classic paper and related works [10, 26].

[10] M. Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26:2292–2300, 2013.

[26] G. Mena, D. Belanger, S. Linderman, and J. Snoek. Learning latent permutations with gumbel-sinkhorn networks. arXiv preprint arXiv:1802.08665, 2018.

What is the complexity of Sinkhorn Knopp algorithm and Gumbel Sinkhorn?

As mentioned in Appendix D.5, both these algorithms consist of some number of alternating row and column scalings. If the input matrix is $N\times N$, then each scaling takes $O(N^2)$ time. The number of scaling iterations is usually a small fixed constant (20 in our experiments).

Is the K-layer GNN in each round t shared?

Yes. We regard the same GNN as being trained after each refinement applied to the proposed (soft) permutation.

Any intuition why lazy updates works better?

Please refer to the global response.

why the work is not differentiable on nodes with different classes.

We meant that, at present, EinsMatch is not coded to account for node or edge labels. Our matching process is purely structural. If there are hard constraints that red nodes in the query graph can match only red nodes in the corpus graph, or there is an additional cost in the form of the difference in their degree of redness, we need to investigate if Sinkhorn-style updates will survive zeroing out parts of $P$. The problem seems complicated enough for a separate piece of work.

Is there other measure between the P and P*? I feel $Tr(P^\top P^*)$ does not capture all the information of the matrices.

Indeed, other measures like Frobenius distance $\Vert P-P^*\Vert _F$ may be used. In Figure B in global-rebuttal-pdf, we updated the histograms, which reveal similar observations as with the Trace metric. Note that $\Vert P-P^*\Vert _F ^2 = 2|V| - 2\, Tr(P^TP^*)$ if P and P* are both hard permutation matrices, but not necessarily the same if they are soft permutation matrices.

Also I am a little dubious about the time complexity of the P matrix update, in the experiments it is more expensive than the baseline GMN.

L716–L720 give an idea of the clock time needed to train EinsMatch variants. Appendix G.6 gives an idea of the inference times involved, particularly, contrasted against IsoNet (edge) — we find these times within the same order of magnitude (usually within 10% and 40% of each other). Figures 6 and 17 show that, at any fixed level of inference time investment, EinsMatch (lazy) has the most favorable MAP envelope.

Following table shows the time splits between GNN embedding computation and matrix P updates, in percentage of time spent performing that step.

These percentages don't add up to 100% because of contributions from other steps like node encoding and score computation. The summary is that yes, updating $P$ has a non-negligible but non-overwhelming cost, with the benefit of better accuracy.

As mentioned by the authors, the quality of the matching relies on the distance function.

We absolutely agree with you. The same is the case for matching passages, images, video and audio. Good distance function design, mirroring human judgment, is critical to applications.

We thank the reviewer for their constructive feedback. The questions raised in the review are addressed below.

ablation study (or a hyperparameter sensitivity study).. how did the authors tune hyperparameters?

We used hyperparameters from the code of IsoNet, which, thanks to the authors, also made the baseline implementations public. In IsoNet's code, the authors suggest that they already tuned the margin in the ranking loss and other hyperparameters for all the baselines. Hence, we used them as-is. We did tune the margin in the ranking loss of three baselines (EGSC, GREED, H2MN) which are not included in IsoNet codebase. More details are in line 703 onwards in Appendix F.4. We run all methods for an unlimited number of epochs, with the patience parameter 50, i.e., training is stopped only if the performance on the validation set does not improve for 50 epochs.

We would like to highlight that, for EinsMatch, we did not tune any hyperparameters beyond IsoNet. We performed a hyperparameter sensitivity study (not tuning) for $T$ and $K$, which shows that for wide ranges of $T$ and $K$, EinsMatch performs better than baselines. We report results for $T=3, K=5$ in the main table, because its running time is comparable to most baselines. Increasing $T$ and $K$ improves accuracy at more computation cost.

We did perform ablations on the node pair partner interaction component in Table 4 and the effect of lazy updates in Table 3 in the main paper. We write the results here.

The following table compares the performance of node partner interaction with EinsMatch, which involves node pair partner interaction. Node pair partner interaction consistently outperforms node partner interaction for both eager and lazy variants of EinsMatch (Node).

The following table compares the performance of the eager and lazy variants of EinsMatch (Node) and EinsMatch (Edge). Lazy multi-round updates consistently outperform eager multi-layer updates across all datasets, for both Node and Edge models.

We observe that our method, in the presence of the node pair partner interaction component, performs better and lazy update generally outperforms eager update.

applicability of the proposed approach to larger graph datasets.

In early experiments, we found relatively small size of query graphs to actually present more challenge to the learner. Given our distant supervision, there are a larger number of promising alignments between query and corpus graphs that may lead to the relevant supervision.

During the rebuttal, we performed experiments with graph pairs generated from the Cox2 dataset. Here, we considered 100 query graphs with $|V|\in[25,35]$, and 500 corpus graphs with $|V|\in[40,50]$. The following table shows the results.

We observe that our method EinsMatch (Edge) Lazy outperforms the baselines significantly. The node variant of our model is marginally outperformed by IsoNet (Node).

motivation and intuition behind lazy updates?

Please refer to the global response.

What do the multiple points with the same color in Figure 6 represent?

We vary rounds $T$ and layers $K$. Each point corresponds to a $(T,K)$ combination. The color, as the legend shows, corresponds to an algorithm family. The goal is to study the tradeoff between inference speed and ranking accuracy (MAP).

We thank the reviewer for their detailed and insightful review.

paper hard to follow...only one single figure

In the global rebuttal PDF, we include another diagram (Figure A) to distinguish between node-pair interaction (earlier work) vs node-pair partner interaction, and also contrast them with IsoNet. If our paper gets accepted, we will include this diagram in the paper.

contributions w.r.t. previous works.

Early interaction models are conventionally more powerful in other domains [a,b], yet in the context of subgraph retrieval, GMN (early interaction) is outperformed by IsoNet (late interaction).

[a] A. Lai and J. Hockenmaier. Learning to predict denotational probabilities for modeling entailment.

[b] Entailment as Few-Shot Learner. S Wang, H Fang, M Khabsa, H Mao, Hao Ma. arXiv:2104.14690v1

In this work, we build a new early interaction model, which addresses the limitations of prior work, also using lessons from IsoNet and GMN. Here, we further elaborate on our contributions.

1. GMN does not use any explicit alignment structure. They use a non-injective attention mechanism, which changes from layer to layer. In our work, we model inter-graph alignments as relaxed bijective permutation maps that are proposed, then $K$ layers of GNN score the proposal, leading to a refined proposal. Thus, the node embeddings of one graph become dependent on the paired graph, implementing early interaction. To the best of our knowledge, this is the first early interaction model for subgraph matching where proposed alignments and GNN layers help refine each other.
2. When we compute the message of node-pair $(u,v)$ in $G _q$, we also use $(u',v')$ in $G _c$ which match with $(u,v)$. Therefore, for $u\in G _q$, the node embedding $\mathbf{h} ^{(q)} _u$ not only depends on nodes in $G _c$ that align with $u$, but also on those nodes in $G _c$, which are aligned with the $\text{Nbr}(u)$ neighbors of $u$. In terms of a formal argument, we have: $\mathbf{h} ^{(q)} _u = f(\mathbf{h} ^{(q)} _u, \\{ \mathbf{h} ^{(q)} _v: v\in \text{Nbr}(u) \\}, \\{\mathbf{h} ^{(c)} _ {v'} : v' \in G _c \text{ aligns with some } v \in \text{Nbr}(u)\\})\ \ \ (1)$ Existing early interaction models like GMN do not capture signals from $\\{v' \in G _c \text{ aligns with some } v \in \text{Nbr}(u)\\}$, they only capture signal from $u' \in G _c$ that matches with $u$. Hence, in GMN, we have: $\mathbf{h} ^{(q)} _u = f(\mathbf{h} ^{(q)} _u, \\{\mathbf{h} ^{(q)} _v: v\in \text{Nbr}(u)\\}, \\{\mathbf{h} ^{(c)} _ {u'} : u' \in G _c \text{ aligns with } u\\})\ \ \ (2)$ As our experiments suggest, approach (1) gives better performance than (2). We provide a more detailed description of this in lines 146-161 in the main paper.
3. We propose two protocols for updating node embeddings and alignments (Lazy and Eager). In Lazy update, we first perform $K$ GNN runs followed by then one single alignment update and in Eager, we update the alignment in each of the $K$ message passing steps.

We will include these elaborations in the additional page, if our paper gets accepted.

how their approach side-steps oversmoothing? explain lines 333 — 336.

The usually symmetric and parameter-free aggregation of messages from a node’s neighbors is known to weaken graph representations computed by GNNs [c]. L334 points out that scaling $h(u’)$ with a relaxed (evolving) permutation $P[u,u’]$ breaks the symmetry and conjectures that this reduces the oversmoothing effect, through task-driven cross-attention between two graphs (as against self-attention in GAT [d]).

[c] A Survey on Oversmoothing in Graph Neural Networks; T. K. Rusch, M. M. Bronstein, S Mishra.

[d] Graph attention networks, P Veličković, G Cucurull, A Casanova, A Romero, P Liò, Y Bengio.

How does the computational complexity compare with that of IsoNet?

Let's consider three node models — IsoNet (Node), Eager EinsMatch (Node) and Lazy EinsMatch (Node) with $T$ rounds, each with $K$ propagation steps.

IsoNet (Node)

Initial node featurization takes $O(N)$ time. Node representation computation aggregates node embeddings over all neighbors, leading to complexity of $O(E)$ for each message passing step and computation of $P$ takes $O(N^2)$ time. The overall complexity for all the steps becomes $O(N^2+KE)$ where $K$ is the number of message passing steps.

Eager Multi-layer EinsMatch (Node)

1. Initial Node featurization takes $O(N)$ time
2. EinsMatch first computes intermediate embeddings $z$ (Eq. 33, Page 16), which admits complexity of $O(N)$ for each layer per node, since it computes $\sum _{u'\in V _c} h^{(c)} _{k}(u') **P** _{k}[u,u']$ for each node in each layer. The total complexity for $K$ steps is $O(KN^2)$.
3. Next we compute (Eq. 34) $h _{k+1}$ which gathers messages $z$ from all neighbors per node per layer. The total complexity contributed by this equation is $O(KE)$.
4. Next we update $P _k$ for each layer which has complexity of $O(KN^2)$.

Hence, the total complexity is $O(KN^2+KE+KN^2)=O(KN^2)$.

Lazy Multi-round EinsMatch (Node)

Here, the key difference from Eager version is that the doubly stochastic matrix $P _t$ from round $t$ is used to compute $z$ and the $K$-step-GNN runs in $T$ rounds. This increases the complexity of step 2 and 3 to $O(KTN^2+KTE)$. Matrix $P _t$ is updated a total of $T$ times, which changes the complexity of step 4 to $O(TN^2)$. Hence, the total complexity is $O(KTN^2+TN^2+KTE) = O(KTN^2)$.

Hence, complexity of IsoNet is $O(N^2+KE)$. EinsMatch-Eager has complexity $O(KN^2)$ and EinsMatch-Lazy has complexity $O(KTN^2)$. However, this increased complexity comes with the benefit of significant acuracy boost, as our experiments suggest.