WILTing Trees: Interpreting the Distance Between MPNN Embeddings

Thank you for taking the time to review and comment on our paper. We clarify our contribution and answer your question below.

---

The paper lacks novelty, as it presents neither a new analysis nor the introduction of a new network.

We respectfully disagree. The proposed WILT generalizes both WLOA distances by Kriege et al (2016) and WWL distances by Togninalli et al (2019). It introduces weights to these distances and presents a novel way to train these weights. Up to our knowledge, WLOA and WWL distances have so far only been presented and used without tunable weights, i.e., as structural distances. Our proposal now allows to fit them to target data.

In terms of analysis, we experimentally investigate what the $d_{MPNN}$ of trained MPNNs looks like. We clarifiy that MPNNs are trained in a way that $d_{MPNN}$ respects the task-relevant functional distance $d_{func}$ rather than the task-irrelevant structural distance $d_{struc}$. In addition, by fitting the WILT distance $d_{WILT}$ to $d_{MPNN}$, we identified Weisfeiler Leman subgraphs (colors) that determine $d_{MPNN}$, providing new insights into $d_{MPNN}$.

Please read the official comment to all reviewers, where we clarify our contributions.

Specifically, Definition 4 (Evaluation Criterion for Alignment Between dMPNN and dfunc) doesn't capture any alignment between MPNN and func.

In Definition 4, $A_k(G)$ and $B_k(G)$ measure the average functional distance between $G$ and its neighbors/non-neighbors in the embedding space, respectively. Therefore, $A_k(G) < B_k(G)$ means that graphs functionally similar to $G$ tend to be embedded closer to $G$ than functionally dissimilar graphs. Therefore, the larger $ALI_k$ is, the more we say that $d_{MPNN}$ is aligned with $d_{func}$. This measure is related to the performance of a k-Nearest-Neighbor model on $d_{MPNN}$.

While the ratio of two distances is commonly used to measure the correspondence between them, there are two reasons why we don't use it in Definition 4.

1. When the task is graph classification, $d_{func}$ is a binary function that returns 1 if two graphs belong to the same class, otherwise 0. Thus, it is unreasonable to expect the exact match of real-valued $d_{MPNN}$ and binary $d_{func}$.
2. Even when the task is graph regression, it is natural to expect that the scale(min/max) of $d_{MPNN}$ and that of $d_{func}$ are different. We can think of normalizing them and measuring the ratio, but for consistency with the classification case, we don't use such a metric.

---

Thank you again for your review and comments. We hope our explanation addresses your concerns. Please let us know if you have any further questions.

We thank you for your thorough review and valuable questions about the connection between [1] and our work. Below are the answers to your two questions.

---

Q1: most of their contributions overlap with prior work [1], which proved that MPNNs have the same expressive power as the 1-Weisfeiler-Lehman (1-WL).

While the distance functions introduced in [1] are related to our work, there are important differences that make their framework difficult to apply in our context. [1] proposes task-irrelevant structural distance measures that are small for graphs $G, H$ if and only if all MPNNs compute representations for $G,H$ that are close. In contrast, our analysis focuses on how $d_{MPNN}$ of a single MPNN captures the task-relevant functional distance of grpahs. Moreover, [1] deals only with dense graphs, while our method works with practical sparse graphs.

Q2: Could you please add [1] to the experiments as well?

In addition to the above difference, the time complexity of graph distances proposed in [1] seems to be O($n^5 \log n$)~O($n^7$), which is too demanding in practice. Nevertheless, we are currently looking for a way to include their distances in our experiments, since there is a connection between [1] and our study.

---

Thank you again for your valuable feedback. Please also read to our official comment to all reviewers, where we clarify our contributions. Please let us know if you have any more suggestions or questions.

We thank you for your thorough review and valuable suggestions. We address each weakness and question below.

---

W1~W3: Hard to follow organization, unclear motivation, limited contributions.

We have explained the motivation, logical flow, and our contributions in the official comment to all reviewers. We will post the updated paper next week, where we will clarify the importance of answering Q1-Q5, and discuss the theory and algorithm of WILT in detail in the main text, which is currently in Appendix B.

Q1: Is MPNN interpretability the main practical motivation of WILTing distance? (a) If so, why not compare the important subgraphs identified from WILTing distance with other GNN interpretability tools (e.g. [1],[2]). What are the additional insights or advantages from using WILTing distance over existing interpretability tools?

Yes, we introduce the WILTing distance for interpreting MPNNs. However, the motivation of our work and the previous studies such as [1, 2] are quite different. Our goal is to understand the entire metric structure $d_{MPNN}$ by identifying Weisfeiler Leman subgraphs that determine $d_{MPNN}$. On the other hand, [1, 2] aim to find an instance-level explanation for the prediction of one input graph. This difference in global-level/distance vs instance-level/prediction makes it difficult to compare our method with [1, 2]. To the best of our knowledge, this is the first work to analyze entire $d_{MPNN}$ in terms of WL subgraphs, and provides new insights such as:

• $d_{MPNN}$ is determined by only a small fraction(~5%) of the entire set of Weisfeiler Leman (WL) colors.
• The identified WL colors are also known to be important by domain experts.

Q2: Expressivity of WILTing distance (Appendix B.4): The authors define using the binary notion of expressivity in terms of distinguishing non-isomorphic graphs. However, recent works in [3], [4] have proposed a fine-grained, continuous notion of WL distances […] Can the authors justify their definition and comment on the expressivity of WILTing distance compared to the continuous WL distance?

While the distance functions introduced in [3,4] are related to our work, there are important differences that make these frameworks difficult to apply in our context. [4] proposes structural distances $d, d’$ that are small for graphs $G, H$ if and only if all MPNNs compute representations for $G,H$ that are close. Our analysis focuses on a single MPNN and its resulting distance $d_{MPNN}$, which is not covered by their analysis. In particular, if $d_{MPNN}$ is small, $d, d’$ may be large. The WL-distance proposed in [3], again is a structural metric and can not be adapted to analyze a given MPNN.

Regarding relaxation of expressivity, [3, Prop 3.3] shows similar results than we do: Their $d_{WL}(G,H) = 0 \Leftrightarrow G,H$ are WL-distinguishable. In this (binary) sense, $d_{WILT}$ is as expressive as $d_{WL}$, if the same initial node labels are used. [3] proposes to use their distance function as a relaxation of expressivity. Alternatively, our $d_{WILT}$ can be used in the same way. However, a quantitative analysis of the similarities between $d_{WL}$ and $d_{WILT}$ is beyond the scope of this work.

Q3: Relationship between WILTing distance and Tree Mover Distance [5]: […]. Intuitively, WILTing distance seems very similar to the Tree Mover Distance [5]: Can the authors compare them?

Both the WILTing distance $d_{WILT}$ and the Tree Mover's Distance $d_{TMD}$ are optimal transport distances between multisets of Wesifeiler Leman (WL) subgraphs. The difference lies in how they define the ground metric (cost) between each pair of WL subgraphs: $d_{WILT}$ adopts the shortest path length on WILT, while the $d_{TMD}$ uses recursive optimal transport of WL subgraphs (Definition 4 in [5]). As a result:

• $d_{WILT}$ can be computed in O($|V|$), while $d_{TMD}$ requires O($|V|^3 \log|V|$).
• $d_{WILT}$ has tunable edge parameters, while $d_{TMD}$ does not. So, $d_{WILT}$ is suitable for approximating $d_{MPNN}$.
• In terms of binary expressive power, $d_{WILT}$ (dummy normalization) = $d_{TMD}$ = 1-WL test

One advantage of $d_{TMD}$ is that it can handle continuous node festures, while $d_{WILT}$ cannot. But understanding $d_{MPNN}$ of graphs with continuous node features is beyond the scope of this study.

---

Thank you again for your valuable feedback, which helps us improve the clarity and contribution of our work. We hope our explanation clearly addresses your concerns and questions. Please let us know if you have any more questions or suggestions.

We thank the reviewer for their thorough review, acknowledging our contributions, and voting to accept our paper. We address each weakness and question individually below.

---

W1: The experiments are conducted on specific datasets; it would be beneficial to see more diverse real-world applications to assess generalizability.

We are currently running experiments on the non-molecular IMDB dataset and will report the results next week.

W2: The answers to the questions asked are pretty obvious beforehand. The structural distances that stem from non-trainable graph kernels have nothing to do with the task, therefore it is unreasonable to assume that an MPNN (before or after training) would be highly correlated (Q2, Q3) . The same goes for Q4, Q5, where the functional distance encodes the target, and is therefore what the MPNN is optimized for. While it is not inherently bad to ask questions that one expects the answer to, these questions, though many, create little new insight.

While the analyses of $d_{MPNN}$ in Sections 3 and 4 may seem obvious, they offer different insights than previous studies on $d_{MPNN}$. In short, we found that the alignment between $d_{MPNN}$ and $d_{func}$ is more important to MPNN performance than the alignment between $d_{MPNN}$ and $d_{struc}$, which has been studied in previous works. However, we acknowledge your concerns and change the flow of the paper to spend less space on this analysis. We will move most of the content of Section 3 to appendix, and use the remaining space to explain in detail the theory and algorithm of WILT.

W3: The algorithm for learning the WILT weight is only discussed in the appendix.

We will include the explanation of the algorithm in the main text in the updated paper.

Q1: How expressive is WILT? It implies a hyperbolic distance between colors, so intuitively, it should be weaker than MPNNs?

In terms of binary expressive power, WILT is more expressive than MPNN:

• MPNN (mean pooling) $\le$ WILT (size normalization) (Theorem 4)
• MPNN (sum pooling) $\le$ WILT (dummy normalization) (Theorem 5)

However, when it comes to how much different distance structure each distance can learn, it is expected that $d_{MPNN}$ can express more diverse distance structures than $d_{WILT}$. This is because $d_{WILT}$ is limited to an optimal transport on a tree of WL-colors, while an MPNN can place any WL-color in a d-dimensional Euclidean space. In practice, however, we have found that $d_{WILT}$ is expressive enough to model $d_{MPNN}$ (Section 6). Moreover, this restriction allows for the fast computation and interpretation of $d_{WILT}$ (Proposition 1).

Q2: How long does learning the WILT weights take?

In general, training is very efficient because the graph distance $d_{WILT}(G, H)$ can be computed via a weighted Manhattan distance on suitable, precomputed vector embeddings of graphs, i.e., via tensor operations. We will include the practical running time in the appendix.

Q3: Famously WL is extremely sensitive to noise in the graph structure. Does WILT handle structural noise and/or feature noise well?

This is actually a very interesting question, that we did not consider, yet. Intuitively, WILT is more robust to structure/feature noise the than WL test, because WILT can adjust edge weights to account for such noise. The robustness to noise is beyond the scope of our current paper, but we will mention it as a future work.

---

Thank you again for your insightful feedback. Please let us know if you have any further questions.

We thank you for your thorough review and valuable suggestions. We hope the points below adequately address your questions.

---

W1: Lack of high-level intuition, guidance.

We have explained the motivation, logical flow, and our contributions in the official comment to all reviewers. We will post the updated paper next week, where we will clarify the motivation and logical flow, and add more intuitive explanations.

W2, Q3: Comparison to recent interpretability approaches in graph learning, such as methods that use attention mechanisms or explainable subgraph extraction

Although we introduce the WILTing distance for interpreting MPNNs, the motivation of our work and the previous interpretation methods are quite different. Our goal is to understand the entire metric structure $d_{MPNN}$ by identifying Weisfeiler Leman subgraphs that determine $d_{MPNN}$. On the other hand, previous studies aim to find an instance-level explanation for the prediction of one input graph. This is true for both subgraph extraction methods and attention analysis methods. This difference in global-level/distance vs instance-level/prediction makes it difficult to compare our method with previous interpretation methods. To the best of our knowledge, this is the first work to analyze entire $d_{MPNN}$ in terms of WL subgraphs, and provides new insights such as:

• $d_{MPNN}$ is determined by only a small fraction(~5%) of the entire set of Weisfeiler Leman (WL) colors.
• The identified WL colors are also known to be important by domain experts.

W3, Q3: The empirical validation on other types of graphs (e.g., social networks, knowledge graphs, molecular interaction networks)

We are currently running experiments on the non-molecular IMDB dataset and will report the results next week. It should be noted that our WILTing distance is designed to analyze the distance between graph embeddings. Therefore, very large networks such as social networks, where the main focus is on node prediction/embedding are beyond the scope of this work.

W4, Q1: Have the authors considered adapting WILT to higher-order Weisfeiler Leman test? Some deeper reflections on this would be beneficial.

Theoretically, it is straightforward to extend WILT to a higher-order WL test. We can build a WILT from the results of the higher-order WL test in exactly the same way as in the 1-WL case, whenever the higher-order test results in a hierarchy of labels (which all ‘generalized WL-tests’ that we are aware of do). That is: generalized WL-tests update labels (not necessarily of nodes, but of higher order objects such as cell complexes, or sets of nodes, …) iteratively. Each label in iteration $t$ has a unique parent label in iteration $t-1$. The WILT on such a generalized hierarchy has the same expressivity as the hierarchy itself. Our proofs in the appendix hold in these cases, as well.

In future studies, it would be interesting to analyze higher-order variants of MPNNs by WILT with corresponding expressiveness. However, there may be a practical difficulty, since the number of trainable edge weights is expected to be increase with increasing order.

Q4: Can WILT work with incomplete graphs at all? What about directed graphs?

What do you mean by "incomplete graphs"? If you mean a graph with non-adjacent node pairs, the answer is yes. WILT makes no assumptions about the topological structure of graphs. If you mean missing node or edge labels, one way would be to impute the missing labels using some separate technique.

The extension to directed graphs is easy. All you need to do is run the corresponding variant of the WL test when building WILT, which updates the color of node $v$ only based on the colors of $u$ with an edge $u \to v$.

---

Thank you again for your feedback, which helps us clarify our contributions. In addition, your questions let us consider extending our work to higher-order MPNNs and broader types of graphs. Please let us know if you have any further questions or suggestions, and we will be happy to answer them.

Dear reviewers, we are sorry to have kept you waiting. We have uploaded an updated version of our paper. Here are the main updates.

• Clarify the motivation and research question in the Abstract and Introduction section.
• Move the analyses of the alignment between $d_{MPNN}$ and task-irrelevant $d_{struc}$ to Appendix E.
• Add examples of how to compute the two types of normalized $d_{WILT}$ in Section 4.3.
• Add the distillation algorithm to Algorithm 1 in Section 4.4.
• Analyze the expressiveness of $d_{WILT}$ in Section 4.5.
• Add experimental results on IMDB-BINARY and COLLAB datasets to Appendix D and E.
• Add experimental results on IMDB-BINARY to Appendix F (experiments on COLLAB are in progress).

If you still find something unclear, or have further questions, please do not hesitate to ask.