Homomorphism Counts as Structural Encodings for Graph Learning

Authors: Linus Bao, Emily Jin, Michael M. Bronstein, Ismail Ilkan Ceylan, Matthias Lanzinger
Primary area: learning on graphs and other geometries & topologies
Keywords: graph transformers, structural encodings, homomorphism counts, expressivity

Abstract:
Graph Transformers are popular neural networks that extend the well-known Transformer architecture to the graph domain. These architectures operate by applying self-attention on graph nodes and incorporating graph structure through the use of positional encodings (e.g., Laplacian positional encoding) or structural encodings (e.g., random-walk structural encoding). The quality of such encodings is critical, since they provide the necessary \emph{graph inductive biases} to condition the model on graph structure. In this work, we propose \emph{motif structural encoding} (MoSE) as a flexible and powerful structural encoding framework based on counting graph homomorphisms. Theoretically, we compare the expressive power of MoSE to random-walk structural encoding and relate both encodings to the expressive power of standard message passing neural networks. Empirically, we observe that MoSE outperforms other well-known positional and structural encodings across a range of architectures, and it achieves state-of-the-art performance on a widely studied molecular property prediction dataset.

Decision: accept (poster)
Reviewer scores: 6, 8, 8, 6, 6

Reviews and discussion:
<thread>
creation date:
1730153339860

thread_type:
official_review

<thread_object>
creator: reviewer_anpu

<content>
summary:
Graph Transformers apply self-attention on graph nodes and to capture the graph structure, they use positional or structural encodings. This paper proposes to use homomorphism count vectors as the employed structural encoding. The authors show that homomorphism counts are more expressive than the commonly used random walk structural encoding. The proposed encoding is evaluated on two molecular property prediction datasets (ZINC-12k and QM9), and also on a synthetic dataset. The results demonstrate that the proposed encoding outperforms other well-known positional and structural encodings across a range of architectures.

strengths:
- The proposed structural encoding seems to better capture the graph structure than other enocodings since it outperforms the baseline encodings (including the commonly used random walk structural encoding) on all considered datasets.

- Besides the empirical results, the paper makes a substantial theoretical contribution since it is shown that the proposed encoding is strictly more expressive than the random walk structural encoding.

- The paper is dense in some parts, but overall it is very well-written and the presentation is clear.

weaknesses:
- Even though the proposed encoding outperforms the random walk structural encoding, the reported results are not very convincing. On most datasets, the difference in performance between the random walk structural encoding and the proposed encoding is very small. On QM9, the random walk structural encoding even outperforms the proposed encoding for some targets. 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.

- The complexity of computing the proposed encoding is not discussed in the paper, but I would expect that the time required to compute this encoding is significantly higher than the one required to compute the random walk structural encoding. In my understanding, the running time depends on the pattern graph family $\mathcal{G}$. 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?

- One of my main concerns with this paper is regarding the novelty of the work. Clearly this is not the first paper to use homomorphism counts in the field of graph machine learning. Several previous works which are discussed in section 2 in the paper have annotated nodes with homomorphism counts. 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.

- 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.

questions:
- 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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730411025643

thread_type:
official_review

<thread_object>
creator: reviewer_7pey

<content>
summary:
The paper introduces a novel positional encoding (PE) for graph transformers based on homomorphism counts and explains it's expressivity in terms of k-WL and the comparison to the random-walk positional encoding. The model is evaluated with two different graph transformers as base models and, over molecule and synthetic data, it shows some improvements.

strengths:
- The research topic makes sense given the recent insights of using homomorphisms in MPNNs.
- The paper is well-structured
- The synthetic data experiment is interesting, and the authors consider two different transformers as base models
- The model seems to achieve good improvements generally (the number of evidence seems a bit low)

weaknesses:
- The paper is sometimes annoying to read:
     - The reader is assumed to know quite some details (e.g., 
W/o knowing the details of RWSE, you don't get the introductory example; the tables mention models like GSN and CIN, which are never explained; oblivious k-WL; l.232 how does GRIT deviate from this? What is Spasm(C7∪C8)?)
     - The expressivity analysis is interesting but it would have been nice if the papers would have provided some ideas about the proofs, to better get to know the nature of the PE.

- 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.
- 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:
"While I appreciate that some claim a 1D representation like SMILES can capture some component of a 3D structure, predicting a property of one molecular conformation from a SMILES doesn’t make much sense. "
https://practicalcheminformatics.blogspot.com/2023/08/we-need-better-benchmarks-for-machine.html

- Beyond that, there's only Zinc12k, which is a bit of a low number of datasets for evaluation

Smaller comments:
- typo: alternative olibious k-WL
- l. 296 "f a graph in G." Is this \mathcal{G} ?
- FYI There's a recent related work: Deep Homomorphism Networks
https://neurips.cc/virtual/2024/poster/95659

questions:
Maybe the authors can point out why they evaluate on only these datasets.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730586576680

thread_type:
official_review

<thread_object>
creator: reviewer_bcps

<content>
summary:
This paper studies the topic of positional/structural encodings for graph learning which are typically influential in Graph Transformers since these incorporate the graph inductive biases coming from the adjacency matrix as its often not directly used during the self attention computation. The paper investigates the expressivity of one of such encodings, the random walk based structural encoding (RWSE), and address their shortcomings by proposing a homomorphism count based structural encoding called MoSE, which are claimed powerful than the RWSE. The content of the paper presents the characteristics brought by MoSE, also using example illustrations where RWSE may fail, and demonstrates in details their performance advantages on molecular datasets as well as one synthetic dataset of random graphs.

strengths:
- the paper is a beautiful read on the limitations of existing RW structural encoding for graph transformers, and how the proposed homomorphism count based SE can address it.
- although the paper does not present a sophisticated new model, the presented SE is carefully studied, and experiments show the advantage (although marginal) brought by MoSE over existing methods in GTs.
- the comparison section of RWSE and MoSE is insightful and shows RWSE is strictly weaker than MoSE, which is reflected in the experimental results, as well as one of the ZINC illustrations.
- the proposed structural encoding has no limitations of LapPE such as sign ambiguity

weaknesses:
- although the MoSE is useful as studied, a concerning factor is of the computational complexity of getting the vectors. how does this compare experimentally?
- 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.

questions:
included with weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730701367024

thread_type:
official_review

<thread_object>
creator: reviewer_yacd

<content>
summary:
The paper introduces MoSE, a graph structural encoding based on homomorphism counts. The authors present theoretical arguments suggesting that MoSE has greater expressive power than RWSE and demonstrate competitive empirical performance when integrated with GTs.

strengths:
1. The experiments supports the claim that MoSE improves performance on molecular property prediction tasks.
2. The theoretical arguments provide a plausible explanation for the observed performance gains.
3. The paper is well-organized and easy to follow.

weaknesses:
1. The paper focuses on comparing MoSE with RWSE, justified by RWSE's empirical success. However, several recent graph transformers, such as GRIT, can incorporate edge features and encodings. RRWP, as proposed in the GRIT paper, builds on RWSE by incorporating non-diagonal terms and achieves both greater theoretical expressiveness and empirical performance improvements over RWSE. 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. 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.
2. 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.
    - If the paper's primary aim is to propose an encoding specifically for molecular property prediction (as supported by Example 1, which is plausible), evaluation across additional molecular datasets, such as [PCQM4M](https://pytorch-geometric.readthedocs.io/en/2.5.2/generated/torch_geometric.datasets.PCQM4Mv2.html#torch_geometric.datasets.PCQM4Mv2), [Peptides-struct](https://pytorch-geometric.readthedocs.io/en/2.5.2/generated/torch_geometric.datasets.LRGBDataset.html#torch_geometric.datasets.LRGBDataset), [Peptides-func](https://pytorch-geometric.readthedocs.io/en/2.5.2/generated/torch_geometric.datasets.LRGBDataset.html#torch_geometric.datasets.LRGBDataset), and [AQSOL](https://pytorch-geometric.readthedocs.io/en/2.5.2/generated/torch_geometric.datasets.AQSOL.html#torch_geometric.datasets.AQSOL), could reinforce the validity of MoSE within this domain. Furthermore, clarifying this scope within the paper—by showing that the phenomena in Example 1 generalize across molecular property tasks—would align well with the empirical objectives. My overall rating assumes this as the paper’s main focus.
    - Conversely, if the goal is to propose a general-purpose graph encoding, then broader evaluation across datasets from other domains is necessary. Evaluating MoSE beyond molecular property datasets would better support a general claim. In this case, datasets from [GNN Benchmark Datasets](https://pytorch-geometric.readthedocs.io/en/2.4.0/generated/torch_geometric.datasets.GNNBenchmarkDataset.html) beyond ZINC can help validate MoSE's general applicability.

questions:
What are the time and space complexities for computing MoSE encodings? How does the empirical preprocessing time compare to RWSE, RRWP, and LapPE?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730719353073

thread_type:
official_review

<thread_object>
creator: reviewer_mzsj

<content>
summary:
The paper proposes Motif Structural Encoding (MoSE), a novel structural encoding method based on homomorphism counts for graph learning tasks. MoSE leverages homomorphism counts to represent graph structure effectively, aiming to surpass limitations found in common positional and structural encodings such as Random Walk Structural Encoding (RWSE). Theoretically, MoSE demonstrates enhanced expressiveness compared to RWSE and is shown to be independent of the Weisfeiler-Leman (WL) hierarchy, thus providing a broader graph representation power. The paper provides empirical validation, showing that MoSE achieves superior results over other encoding methods on various datasets, including molecular property prediction on ZINC and QM9.

strengths:
- MoSE’s homomorphism count-based encoding enhances expressiveness beyond RWSE and aligns well with complex graph structures, as it provides unique structural insights through flexible motif selection.
- The paper rigorously compares MoSE to established methods and relates its expressiveness to the WL hierarchy, grounding its effectiveness in theoretical proofs.
- MoSE achieves state-of-the-art results on benchmarks, showcasing its applicability and effectiveness in both real-world and synthetic datasets, particularly in molecular graph prediction tasks.

weaknesses:
- The performance of MoSE may vary depending on the choice of motif graphs, requiring task-specific tuning to achieve optimal results.
- Calculating homomorphism counts for large and complex graphs could increase computational requirements, potentially limiting scalability for very large datasets.
- 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.

questions:
Please see Weaknesses
</content>
</thread_object>

</thread>
<thread>
creation date:
1732214784858

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Response

comment:
We thank the reviewers for their comments and address each remark in detail in our individual responses. We also include further experimental results and complexity details here.

**Additional experimental results:**
1. We extend the comparison of different positional/structural encodings from GPS (Rampasek et al., 2022) with the PCQM4Mv2-subset and CIFAR10 datasets:


| Encoding     | PCQM4Mv2-subset (MAE $\downarrow$)| CIFAR10 (Acc $\uparrow$)|
| --------     | :--------: | :--------: |
| *none*       | 0.1355   | 71.49    |
| PEG-LapEig   | 0.1209   | 72.10    |
| LapPE        | 0.1201   | 72.31    |
| SignNet-MLP  | 0.1158   | 71.74    |
| SignNet-DeepSets |0.1144| 72.37    |
| RWSE         | 0.1159   | 71.96    |
| **MoSE (ours)**  | **0.1133** | **73.50**    |

2. 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:

|          | Peptides-struct (MAE $\downarrow$) | Peptides-func (AP $\uparrow$) |
| -------- | :--------: | :--------: |
| GT+RWSE  | $0.344 \pm \tiny0.009$     | $62.52 \pm \tiny1.15$     |
| **GT+MoSE (ours)** | $\mathbf{0.318 \pm \tiny0.010}$ | $\mathbf{63.49 \pm \tiny1.13}$ |


3. Due to the encouraging results from GPS+MoSE on the CIFAR10 image dataset, we ran an additional experiment on MNIST, which is another standard GNN dataset:


| Model    | MNIST (Acc $\uparrow$) |
| -------- | :--------: |
| EGT      | $98.173 \pm \tiny0.087$     |
| GPS+LaPE | $98.051 \pm \tiny0.126$     |
| GRIT     | $98.108 \pm \tiny0.111$     |
| **GPS+MoSE (ours)** | $\mathbf{98.198 \pm \tiny0.002}$ |


These additional experiments further validate the benefit of using MoSE and support the  theoretical findings of our paper. We thank the reviewers for their pointers which helped us to improve the paper.



**Complexity of computing MoSE encodings:**

Practically, computing the homomorphism counts for MoSE is highly parallelizable since the homomorphisms from each pattern can be counted independently from one another. In our experiments, computing the MoSE encodings took only **~0.02 sec** per graph. By contrast, training various Transformer models on datasets such as QM9 took between **15-30 hours** for a single run. Therefore, the time to compute MoSE is almost negligible overall. 

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. However, RWSE cannot capture other treewidth 2 motifs that MoSE can accommodate for essentially the same cost.

We will include these experiments and an explicit discussion on complexity in the revised version of our paper, and thank the reviewers again for these very helpful suggestions.


References:

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

Marx, D. Can you beat treewidth? In *FOCS*, 2007.
</content>
</thread_object>

</thread>


Metareview:
metareview:
(a) The paper proposes Motif Structural Encoding (MoSE), a novel structural encoding method for graph learning. It shows MoSE has greater expressive power than Random Walk Structural Encoding (RWSE) and is independent of the Weisfeiler-Lehman (WL) hierarchy. Empirically, MoSE outperforms other encodings on various datasets, especially in molecular property prediction.

(b) Strengths: 
Theoretically, MoSE's expressiveness is rigorously analyzed and compared with RWSE, providing a solid theoretical foundation. 
Empirically, it achieves state-of-the-art results on benchmarks, validating its effectiveness.
The paper is well-structured and the presentation is clear, facilitating understanding.

(c) Weaknesses: 
MoSE's performance may depend on motif graph choice, requiring task-specific tuning.
The theoretical contribution regarding homomorphism counts' expressivity may not be highly novel compared to some recent works.

(d) Reasons for acceptance: 
Despite the weaknesses, the paper makes a significant contribution. The proposed MoSE is a powerful encoding technique with clear theoretical and empirical advantages over existing methods. The authors addressed reviewers' concerns well, providing additional experiments and explanations. For example, they showed the negligible computational time for MoSE compared to training time, and demonstrated its flexibility in different scenarios. The overall quality of the paper, in terms of scientific content and presentation, justifies its acceptance.