Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning

Summary

The paper introduces the $r$-loopy Weisfeiler-Leman ($r$-$l$WL) test, an innovative hierarchy of graph isomorphism tests, and the corresponding GNN framework, $r$-$l$MPNN. This new approach extends the counting capabilities of previous algorithms, specifically allowing the counting of cycles up to length $r+2$ and homomorphisms of cactus graphs. Empirical validation demonstrates the expressiveness and performance of $r$-$l$MPNN on both synthetic and real-world datasets.

Strengths

The paper's strengths are rooted in its originality, introducing a novel algorithm ($r$-$l$WL) and corresponding GNNs ($r$-$l$GIN) that significantly enhance the expressivity of graph neural networks. These contributions are supported by rigorous theoretical proofs and empirical validation. Specifically, $r$-$l$WL demonstrates the ability to count cycles up to length $r+2$ and homomorphisms of cactus graphs, substantiated with detailed mathematical proofs. The experiments use several synthetic datasets to validate the counting power and expressiveness of $r$-$l$MPNN effectively. Furthermore, the paper contextualizes its contributions within prior work, highlighting the limitations of existing methods and demonstrating how $r$-$l$WL and $r$-$l$MPNN address these gaps. Overall, the claims are well-supported by theoretical proofs and empirical results, indicating a clear improvement over existing methods.

Weaknesses

Some of the mathematical proofs are complex and may be difficult for readers without a strong background in graph theory and GNNs. Providing additional intuitive explanations or examples could improve accessibility. While the empirical validation is strong, it could be expanded to include a broader range of real-world datasets to further demonstrate the robustness and generalizability of the approach.

Questions

The paper is generally well-written and clear, although some sections could benefit from additional explanations or examples to aid understanding. I have a few questions: 1. How does the computational complexity of $r$-$l$WL compared to existing higher-order WL variants like $3$-WL in practice, especially when dealing with large and dense graphs? 2. What are the limitations of $r$-$l$WL in terms of scalability and memory usage, particularly when applied to real-world datasets with varying degrees of sparsity? 3. In Table 1, why didn't your method perform well on the Extension (100) and CFI (100) datasets compared to 3-WL and PPGN?

Rating

8

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

The authors have addressed the limitations related to the complexity of higher-order GNNs and the scalability issues associated with $k$-WL. However, a more detailed discussion on the limitations of $r$-$l$WL in terms of computational overhead and potential impact on large-scale applications would be beneficial.

Summary

The paper proposed a hierarchy of graph isomorphism tests and a corresponding GNN framework, $r$-$\ell$-MPNN while showing the ability to count homomorphisms of cactus graphs.

Strengths

The strengths of the paper are: * The ability to count homomorphisms of cactus graphs without any additional explicit substructure counts. * Scalability towards large datasets, especially when the graphs are sparse for these datasets. * The paper is well-written and easy to understand.

Weaknesses

The weaknesses of the paper is that while the paper is well written, there are some terms undefined, or unexplained such as HASH; see the first question in the following section.

Questions

1) What is the HASH function? do you have an example of such a function? 2) Can you add tables concerning the times of your method compared to other methods? 3) What is the motivation behind using $r=5$ in the experiments? would any $r>5$ result in worse results or simply better results by small significance on the expense of might higher time?

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors have adequately addressed the limitations.

Summary

In this paper, the authors propose a loopy version of the Weisfeiler-Lehman (WL) algorithm. This version utilizes an extended notion of neighborhood, incorporating paths between standard neighboring vertices to update vertex coloring. By parameterizing the length $r$ of these paths, we obtain $r$-$l$WL. The results include a hierarchy for $r$-$l$WL based on $r$ and a comparison with $k$-WL. The most technical result is that $r$-$l$WL is expressive enough to determine homomorphism counts of $(r+2)$-cactus graphs. Experiments show that $r$-$l$WL is competitive in detecting substructures.

Strengths

**S1 Interesting Idea:** The inclusion of paths in the neighborhood is an elegant and innovative way of extracting local information around a vertex. This approach allows for rigorous theoretical analysis and captures cactus graphs, which is a significant advantage. **S2 Experiments:** The authors empirically demonstrate that the neural version of $r$-$l$WL captures crucial information for graph learning tasks. **S3 Capturing Cacti:** The most technically involved proof shows that cactus graphs, or at least their homomorphism counts, can be captured. This is a noteworthy result.

Weaknesses

**W1 Capturing Cacti:** The motivation for focusing on cactus graphs is unclear. The authors should better justify why this class of graphs is interesting and relevant, and provide examples in the main paper. **W2 Insufficient Comparison with Subgraph GNNs:** The paper mentions that subgraph GNNs are bounded by $3$-WL, but there are subgraph GNNs beyond $3$-WL, such as $k$-OSAN s (ordered subgraph aggregation networks, Qian et al.), which can capture features that $k$-WL cannot and are bounded by $(k+1)$-WL. The paper overlooks this line of work and lacks comparison with $k$-OSANs, both empirically and theoretically. For example, specifying paths of length $r$ and a central node requires special subgraphs of size $r+1$ (the path plus central node), suggesting that $r$-$l$WL may be included in $(r+1)$-OSAN? This could imply that some results stem from $k$-OSAN properties. A more detailed comparison is needed. **W3 Experimental Comparison:** The experiments do not seem to include any subgraph GNNs that capture properties beyond 3-WL. The authors should make more clear what are the capabilities of the methods with which they compare. **W4 Unlabeled Graphs:** The paper does not address vertex labels. Can the approach be generalized to vertex labels? Additionally, $c^{(0)}$ in section 3.2 is undefined. Minor Comments: The authors sometimes use obscure references. For instance: - line 71: Do you mean Tinhofer or Dvorak? - line 96: Why refer to Dimitrov 2023 for the notion of graph invariant, which has existed for ages?

Questions

Please comment on **W1**, **W2** and **W3**.

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

This has been addressed in a satisfactory way by the authors.

Summary

This introduce $r$-loopy Weisfeiler-Leman, a new hierarchy of graph isomorphism test and a corresponding GNN framework. It achieves good cycle counting power and surpuss $k$-WL in some cases. The power of r-lWL is examined in various synthetic and real-world datasets.

Strengths

1. Strong theoretic results with concrete proof. 2. The algorithm is local with good expressivity.

Weaknesses

1. More datasets [1, 2] can be included to evaluate expressivity, especially long range expressivity. [1] Vijay Prakash Dwivedi, Ladislav Rampásek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, Dominique Beaini: Long Range Graph Benchmark. NeurIPS 2022. [2] Yanbo Wang, Muhan Zhang. Towards Better Evaluation of GNN Expressiveness with BREC Dataset. arxiv/abs/2304.07702

Questions

1. For any pair of non-isomorphic graph, can $r$-lwl differentiate them with large enough $r$? (similar that $k$-WL can solve graph isomorphism problem for graph of node less than $k$).

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes

Good rebuttal

I have read the rebuttal and I am pleased with the responses. I would indeed appreciate if the case for cactus graphs is made stronger in the paper, as is explained here in the rebuttal. Moreover, the connection with subgraph GNNs, whether OSANs or other, should be explored or at least discussed briefly in related work. Based on the rebuttal and I am happy to accept the paper and to raise my score. The paper I referred to is "On recognizing graphs by numbers of homomorphisms by Zdeněk Dvořák.

Good rebuttal

The authors satisfactorily addressed my questions. However, I have kept my score, increasing my confidence to 4 in light of the authors' answers.

Satisfied with the answers

Thank you to the authors for addressing my comments and for their thoughtful responses to the other reviewers' feedback. I continue to believe this is a good paper and will maintain my score.