Homomorphism Counts as Structural Encodings for Graph Learning

We thank the Reviewer for the feedback and address their main concerns below:

It is thus unclear whether there is indeed a need for a new encoding in this setting since it does not lead to significance performance gains over the existing method.

Answer: We would like to emphasize that MoSE strictly generalizes RWSE. For practical applications, addressing task-specific use cases is important and MoSE is flexible enough to accommodate these changes, whereas other encoding methods (i.e. RWSE) cannot.

We provide an additional experiment where we evaluate the self-attention Graph Transformer (Dwivedi & Bresson, 2020) on the peptides-struct and peptides-func datasets to isolate the performance gain of MoSE vs RWSE. The empirical results support the benefits of MoSE which leads to substantial improvements over RWSE (please see our global response for the specific results).

Furthermore, we extend the ablation study of positional/structural encodings from GPS (Rampasek et al., 2022) with the CIFAR10 dataset, which again highlights the benefits of MoSE across different domains

I would thus suggest the authors report in the paper the pre-processing time for each one of the considered encodings. If the additional computational cost is high and given the marginal performance improvements it offers, why one would choose the proposed encoding over other encodings?

Answer: Computing the homomorphism counts for MoSE is highly parallelizable since the homomorphism from each pattern can be counted independently from one another. Empirically, it took only ~0.02 sec to compute MoSE for a given graph, whereas training various Transformer models on datasets such as QM9 took as long as 15-30 hours for a single run. Therefore, the time to compute MoSE is almost negligible overall. We thank the reviewer for this suggestion and will report the pre-processing time in our revised version.

Since MoSE generalizes popular encodings, we see it also as a way to trade off more compute to achieve a more informative (and thus ideally better performing and generalizing) encoding. This kind of adaptability is not possible in RWSE or other popular encodings.

The main difference between those works and this paper is that the learning models employed in this paper are Graph Transformers and not MPNNs. However, I doubt if this in enough for the paper to be considered novel.

Answer: We specifically study the power of homomorphism counts as a graph inductive bias in their own right, and we prove that MoSE strictly generalizes RWSE, which is a very popular encoding technique. Although our work is most closely related to Jin et al. 2024, their focus is on identifying which motif parameters should be used to reach a desired level of expressivity, whereas our focus is to study the expressivity of the homomorphism counts as a structural encoding technique themselves in comparison with existing encodings.

The authors choose to integrate the proposed encoding into Graph Transformers, but all the theoretical results presented in the paper hold for the encoding itself (no assumptions are made about the underlying model). Thus, Graph Transformers could be replaced with MPNNs, and all the results would still hold. I thus wonder why the authors chose to place that much focus of the paper on Graph Transformers.

Answer: Indeed, our results are actually more general than just for Graph Transformers. We focus our empirical results around Transformers because these models have been shown to work well empirically, and we wanted to isolate the performance of the encodings alone, without any confounding graph inductive bias being provided by message passing in MPNNs.

The proposed method relies on a finite set of fixed pattern graphs. One needs to choose the types of considered pattern graphs and this usually requires some domain knowledge. In case such knowledge is not available, what kind of patterns should be chosen?

Answer: We thank the reviewer for raising this point, and we highlight our approach for each of these cases:

1. Domain knowledge available: In this scenario, MoSE can be adapted to capture domain-specific patterns and guarantee a precise level of expressivity with respect to these patterns. This flexibility is not possible in existing encoding techniques, where certain patterns cannot be captured no matter how the encoding is parameterized.
2. No domain knowledge available: In this scenario, there is no reference point for expressivity that needs to be reached. Any finite set of features will fail to express some (infinitely many) functions. This makes every finite method equally bad in terms of achieving the right expressivity by pure luck when absolutely no knowledge is available. The framework of graph motif parameters in fact nicely determines which functions are not expressed by any finite set of homomorphism counts. In this case, we use all connected graphs up to $k$ vertices, since this is arguably the most neutral approach.

References:

Dwivedi & Bresson. A generalization of transformer networks to graphs. arXiv preprint arXiv:2012.09699, 2020.

Rampasek et al. Recipe for a general, powerful, scalable graph transformer. In NeurIPS, 2022.

Jin et al. Homomorphism Counts for Graph Neural Networks: All About That Basis. In ICML, 2024.

We thank the reviewer for their reply and their acknowledgment of the significant theoretical contribution of our work. We further address the outstanding concerns below:

In the empirical evaluation, the proposed encoding does not seem to bring any major improvements over the random walk structural encoding. It is thus not clear whether there is a need for a new encoding.

MoSE is an expressive encoding method that has explicit theoretical guarantees. Therefore, MoSE is a very strong alternative when the expressive power of RWSE is insufficient. For instance, in Figure 1, we show that RWSE cannot distinguish between two functional groups within a molecule. If the task at hand were to rely on such functional groups, our theoretical results show that RWSE cannot capture this information. This scenario is not unlikely in the real world, since functional groups play a key role in determining a molecule’s reactivity within certain settings. Practically speaking, MoSE is flexible enough to be adapted to domain-specific tasks, which is clearly not the case for RWSE. This finding is also supported experimentally on diverse datasets.

In addition, on Peptides-struct the proposed encoding is significantly outperformed by SAN+RWSE and Transformer+LapPE (results reported in the paper that introduced the Peptides dataset [1]), while on Peptides-func its performance is comparable with that of the two aforementioned models.

SAN (Kreuzer et al., 2021) is fundamentally a different model from GT (Dwivedi & Bresson, 2020), which accounts for the difference in performance. For a more fair comparison of RWSE vs MoSE, we refer the reviewer to our global response, where we present a direct comparison of GT+RWSE vs GT+MoSE. We select GT because it provides a “pure” comparison of RWSE vs MoSE as a graph inductive bias, since the standard self-attention GT model does not contain additional confounding graph inductive biases that other models may have (e.g. SAN incorporates Laplacian spectral information as well). It is a important future avenue to study the combination of different inductive biases and our paper will hopefully play a crucial role in those investigations.

From a practitioner's point of view, the proposed encoding is much more complex than the random walk structural encoding since some patterns need to be chosen. In case no domain knowledge available, the authors propose to use all connected graphs up to k vertices. This could incur significant additional computational costs if the input graphs are large and dense even though computation can be parallelized.

MoSE can distinguish all graphs that RWSE distinguishes by recovering the exact values of the RWSE vector by counting cycle homomorphisms with reciprocal degree weighting (detailed in the appendix). As such, RWSE is no more than a special case of MoSE that chooses cycles to be the patterns of interest. If the baseline performance of RWSE is a sufficient starting point, one can simply construct MoSE with cycles (to recover RWSE), and any additional “complexity” for capturing additional patterns can be done on a flexible task-specific basis. Furthermore, from a purely computational perspective, the bottleneck in training for large and dense graphs is due to the quadratic runtime complexity of Graph Transformers rather than the computation of the homomorphism counts for small $k$ (=size of the motifs).

The expressivity of the homomorphism counts has already been studied in [2] and [3]. I would suggest the authors better explain in the manuscript how this work is different from the above two studies.

The primary difference is that we study the strength of homomorphism counts in terms of positional/structural encoding. This is different than studying their power with MPNNs which themselves already include inductive bias. Our analysis also entails results which are not implied by any either [2,3], such as MoSE>RWSE, the associated limitations of RWSE, and how the use of MoSE in GTs compares to the expressive power of MPNNs. We thank the reviewer for their suggestion and will be sure to elaborate this further in the revised version of our paper.

References:

Kreuzer et al. Rethinking Graph Transformers with Spectral Attention. In NeurIPS, 2021.

Dwivedi & Bresson. A generalization of transformer networks to graphs. arXiv preprint arXiv:2012.09699, 2020.

We thank the reviewer for the constructive feedback and respond to the main points below:

The reader is assumed to know quite some details

Answer: We thank the reviewer for raising these points and will provide a more detailed explanation of our notion and discussion in the revised paper.

With all the molecular datasets considered, it would have been nice if the evaluation contained some baseline from the chemistry domain, to see how the model compares in realistic settings.

Answer: Our approach is general in that it can be used in conjunction with any model including those that are domain specific. However, since our work primarily focuses on studying the expressivity of positional/structural encodings, our evaluation is geared towards comparing MoSE to existing encoding methods. We think this is crucial for a fair comparison across different encoding techniques.

Regarding the QM9 experiment, I am computer scientist myself and cannot entirely judge the validity, but wanted to point out that some chemists have strong doubts about this kind of experiment:

Answer: As stated previously, our experiments are designed to provide a fair comparison of MoSE to other encoding techniques. Therefore, we default to common benchmarks within the GNN and graph community, which include the QM9 dataset. However, we acknowledge that this dataset may not be perfect and provide further experiments on additional datasets in our global response.

Maybe the authors can point out why they evaluate on only these datasets.

Answer: We originally focused on ZINC and QM9 due to the computational constraints of Graph Transformer (GT) models. Since GTs scale quadratically with the number of nodes in a graph, they are extremely resource intensive, which is why most current GT benchmarks are on molecular datasets.

Additionally, QM9 has 13 different tasks to regress over, whereas most other datasets only have one of two. Therefore, we believe that it is a much more robust dataset to evaluate against and it highlights the flexibility of MoSE to predict a range of properties.

However, we also provide additional experimental results in our global response which further show the performance of MoSE across different types of molecular datasets (PCQM4Mv2, peptides-func, peptides-struct) and different domains (CIFAR10, MNIST).

I've read through the rebuttals and the additional results are good for verification. Overall, I think my rating still reflects my overall impression of the submission.

I slightly disagree with the authors in that I think, if the paper focuses on chemistry datasets, then the evaluation should also be reasonable in this respect (but this doesn't need further discussion).

We sincerely thank Reviewer bcps for the review and positive feedback. We address your comments below:

although the MoSE is useful as studied, a concerning factor is of the computational complexity of getting the vectors. how does this compare experimentally?

Answer: Computing the homomorphism counts for MoSE is highly parallelizable since the homomorphism from each pattern can be counted independently from one another. Empirically, it took only ~0.02 sec to compute MoSE for a given graph, whereas training various Transformer models on datasets such as QM9 took as long as 15-30 hours for a single run. Therefore, the time to compute MoSE is almost negligible overall.

the utility of the propose structural encoding may be limited to addressing specific failure cases of prior SEs as indicated by the minor changes in experimental numbers.

Answer: We provide an additional experiment where we evaluate the self-attention Graph Transformer (Dwivedi & Bresson, 2020) on the peptides-struct and peptides-func datasets to isolate the performance gain of MoSE vs RWSE. The empirical results support the benefits of MoSE which leads to substantial improvements over RWSE (please see our global response for the specific results).

We also extend the ablation study of positional/structural encodings from GPS (Rampasek et al., 2022) with the CIFAR10 dataset, which again highlights the benefits of MoSE across different domains.

References:

Dwivedi & Bresson. A generalization of transformer networks to graphs. arXiv preprint arXiv:2012.09699, 2020.

Rampasek et al. Recipe for a general, powerful, scalable graph transformer. In NeurIPS, 2022.

Thank you for your review. We have addressed your questions and concerns here:

Although the paper shows that GRIT+MoSE outperforms GRIT+RRWP, a theoretical explanation (e.g., specific examples or proofs, similar to the RWSE discussion) would strengthen this claim

Answer: This is a good point, but unfortunately, it is difficult to directly compare encodings on individual nodes to encodings for node pairs. That being said, one can extend MoSE encodings naturally to pairs of vertices (by fixing two vertices in the pattern graphs). In that setting, our proofs that show that RWSE is simply a special case of MoSE also easily adapt to showing that RRWP is a special case of pair-wise MoSE (the patterns being paths with the same weighting scheme as for RWSE).

Additionally, more detailed discussion on when and why node-level structural encodings remain competitive despite SOTA GNNs' ability to process edge features and encodings would be beneficial.

Answer: Node-level structural encodings may sometimes provide more explicit information about graph structure than what can be captured by some GNNs (e.g., cycles cannot be detected by GNNs). Furthermore, in order to learn longer-range information, GNNs must go through several layers of message-passing, which may distort the graph signal and lead to information loss due to over-squashing (Alon & Yahav, 2021).

MoSE's evaluation is based on two molecular datasets, ZINC and QM9. While these datasets are standard in GNN benchmarking, limiting evaluation to these two datasets might be too restrictive.

Answer: We thank the reviewer for their suggestion and provide additional experimental results in our global response. These further show the performance of MoSE for additional molecular datasets (PCQM4Mv2, peptides-func, peptides-struct) and across different domains (CIFAR10, MNIST).

What are the time and space complexities for computing MoSE encodings? How does the empirical preprocessing time compare to RWSE, RRWP, and LapPE?

Answer: From a theoretical perspective, the complexity of MoSE is very intricate. With constant uniform weighting, counting homomorphisms from H to G is feasible in time $O(|G|^{tw(H)})$ where $tw(H)$ is the treewidth of H. It is known that this exponent cannot be substantially improved upon (Marx, 2007). The complexity of computing MoSE encodings thus fundamentally depends on the choice of patterns and their treewidth.

As we show in Proposition 5, RWSE is simply a limited special case of MoSE for one specific set of pattern graphs (cycles) and one specific weighting scheme ($w(v) = 1/degree(v)$). Cycles always have treewidth 2, and thus RWSE is always feasible in quadratic time.

Since MoSE generalizes popular encodings, we see it also as a way to trade off more compute to achieve a more informative (and thus ideally better performing and generalizing) encoding. This kind of adaptability is not possible in RWSE or other popular encodings.

For further details on the empirical processing time of MoSE and how its complexity compares to other encoding methods, please refer to our global response.

References:

Alon & Yahav. On the Bottleneck of Graph Neural Networks and Its Practical Implications. In ICLR, 2021.

Marx, D. Can you beat treewidth? In FOCS, 2007.

Thank you for your constructive feedback. We respond to your main points below:

The performance of MoSE may vary depending on the choice of motif graphs, requiring task-specific tuning to achieve optimal results.

Answer: The ability to customize MoSE to specific tasks is actually a benefit, since encodings such as RWSE are not able to accommodate such flexibility. Because MoSE strictly generalizes RWSE, the performance of MoSE will at the very least be equal to that of RWSE, with task-specific tuning only increasing the performance of MoSE.

If there is no obvious choice of motifs, we can construct MoSE using the set of all connected graphs up to $k$ vertices, which would allow us to capture a wide range of graph motif parameters. We show an example of this in our QM9 experiment, where it is unclear which motifs will help with which of the 13 properties. Therefore, MoSE is constructed using the homomorphism counts for the set of all connected graphs up to 5 vertices and the 6-cycle.

Calculating homomorphism counts for large and complex graphs could increase computational requirements, potentially limiting scalability for very large datasets.

Answer: In practice, for small $k$ (=size of the motifs), the bottleneck in training is due to the quadratic runtime complexity of Graph Transformers rather than the computation of the homomorphism counts. For further details on the complexity of MoSE, please also refer to our global response.

The theoretical analysis of the expressivity of homomorphism counts has been established and well-studied by recent works (e.g., Jin et al. 2024). It is not very clear what additional theoretical contribution this paper has.

Answer: Our work specifically studies the power of homomorphism counts as a graph inductive bias in their own right, and we prove that MoSE strictly generalizes RWSE, which is a very popular encoding technique. Although our work is closely related to Jin et al. 2024, their focus is on identifying which motif parameters should be used to reach a desired level of expressivity, whereas our focus is to study the expressivity of the homomorphism counts as a structural encoding technique themselves in comparison with existing encodings.

References:

Jin et al. Homomorphism Counts for Graph Neural Networks: All About That Basis. In ICML, 2024.

I appreciate the authors’ response which has addressed some of my concerns. Still, I don’t think using homomorphism counts as PE brings significant contributions given existing works on the expressivity of homomorphism counts. It would be more interesting if the transformer architecture itself could play a role in the analysis, while now it seems to be more of a restatement of established graph theory. But overall it’s a good paper and I recommend acceptance.