WL-Tree: a New Tool for Analyzing Graph Neural Networks

If you state "That this notion is equivalent with WL coloring is absolutely folklore and has been used in many papers for decades." Could you just point out one paper to support your statement? Thank you!

We will post a longer response later.

Thank you for your comments. We appreciate that you have seen our effort in getting a new perspective of graph structures behind GNNs.

--- [W1] Equations 3 and 5.

Equation 3 is the definition, and equation 5 is derived from equation 3. The idea of equation 5 is as follows: if i is the anchor of an anchored subgraph, then the anchored subgraph can be viewed as the union of 1) i and i's neighbors and 2) anchored subgraphs surrounding i's neighbors.

In the edge set of equation (4), we have $\\{(j, k) \in E: \mathrm{dist}(i, j) < \ell, \mathrm{dist}(i, k) \le \ell \\}$. A better writing should be $\\{(j, k) \in E: \mathrm{dist}(i, j) \le \ell, \mathrm{dist}(i, k) < \ell \\}$, which is consistent with our usage of $j$ in the node set. It means that: if $(j, k)$ is included in the edge set of $S_i^\ell$, then it must in a length-$\ell$ walk starting from $i$, then the distance between $i$ and one end needs to be less than $\ell$.

--- Page 4: For the function id(·) that maps a tree node to a node in an anchored graph, since a node in an anchored graph may appear multiple times in the tree, is it still a function?

It is a function since it may map multiple tree nodes (multiple appearances of a graph node) to a graph node.

--- [W2] Consider a counter-example, where G is a graph consisting of two triangles and H is a cycle of length 6. These two graphs cannot be distinguished by 1-WL, but would have different WL-trees proposed in the paper.

We will have the same WL tree, which has the following pattern: each node has two children.

--- [W3] It is unclear why the proposed WL-trees can provide a more fine-level analysis of the expressiveness of node representations learned by message-passing GNNs. In particular, the proposed WL-trees are not equivalent to 1-WL (see the above point [2]).

As we have shown in our work, a WL-tree is equivalent to a WL-color. We have clarified W2 as well. In this regard, our WL-trees provide a new way of analyzing graph structures behind node representations. It is easier to use because 1) it connects well with the original graph structure, and 2) it is easy to visualize.

--- [W4] In what kinds of scenarios will the proposed algorithm 1 be useful?

The algorithm is able to enumerate graph structures that give the same WL tree/color. When we want to analyze these structures, e.g. checking which structures a GNN cannot distinguish, then we can use the algorithm to do so. In fact, we use the algorithm to check how many graph structures can possibly be confused by GNNs in section 6.

--- [W5] For the section 6, what are the justifications for selecting CLIP and Nested GNN? There are a large number of GNN models developed in the literature. I don't see why these two particular GNN models are selected for analysis.

Because these two GNNs can be best explained by our WL-trees. We plan to examine the expressiveness of more GNNs in our future work.

--- [W6] Theorem 12 and Theorem 13 look confusing. Why is max used in Equation 8? Is the notation defined?

The max operation is taken over all possible colorings $\bar{c}$. It is from the CLIP-2 method -- we just formalize the method.

--- Also, the expressive power of Nested GNN goes beyond 1-WL, but the WL-trees proposed in the paper are claimed to be equivalent to 1-WL. So why does Theorem 13 state that there is a bijective mapping between WL-trees and their node embeddings calculated by Equation 10?

Both the two GNNs first color graph nodes with extra information (random colors or local message-passing) and then run a vanilla GNN to get node representations. So we can use our WL trees to quantify the abilities of their vanilla GNNs using extra node colors.

--- [W7] For the statement "A smaller count or conditional entropy means that the WL-tree can better identify a node’s surround structure", is any theoretical justification? Analysing GNN models using average counts of anchored subgraphs and the conditional entropy of anchored graphs look ad hoc.

The conditional entropy is computed from possible graph structures in the dataset that give the same WL-tree/color. If the conditional entropy is 0, it means that there is only one graph structure giving the WL tree/color. In our view, the analysis with an information quantity is reasonably because it tights to a GNN's ability in terms of distinguishing graph structures.

Thank you for seeing our effort in a formal analysis of GNN's expressive power. Below are answers to your questions.

1. "It is not clear to me why this difference is important and how it brings significant differences compared to existing understanding."

There are at least two benefits if we do not include the parent in the child. First, it is easier to discuss a node's WL color in a tree -- our formulation directly uses the original tree structure without adding new nodes. Second, it is easier to enumerate graph structures behind a WL color. With our formulation, we only need to merge some nodes to get a graph structure. If a node's parent is also included in the child list, then the situation is much more complex.

2. " Could you summarize what findings we can get from this new analysis tool?"

First, with the new tool, it is easier to discuss which graph nodes have the same color/node representations. For example, showing that a GNN with a fixed depth cannot distinguish a graph node from a particular tree node. Second, it is easier to explain how previous GNNs enhance node representations. Random node colors give a particular tree pattern (some nodes much take the same color), so that the graph structure can be separated from others that have the same WL color.

As we mentioned in our submission, this new tool is fundamentally no different from WL colors but it makes some analysis clearer, particularly when we can visualize examples with WL trees. As a comparison, it is more abstract to discuss WL colors and logic to reach the same conclusion.

3. Findings from our experiments

In our experiment, we use our new method to enumerate graph structures corresponding to a WL tree/color. We show that advanced GNN methods are able to eliminate a large number of possible graph structures by including extra node colors. But they do not do much better in terms of distinguishing graph structures in the dataset: a WL tree/color may correspond to many graph structures, but if only one of these structures is in the dataset, then it still can be distinguished by a vanilla GNN. Our experiment explains why we don't see a significant increase in performance when we use stronger GNNs on some datasets.