Graph as Point Set

We are grateful for Reviewer 8zdN's comprehensive feedback and have addressed their concerns as follows:

1. W1-1: Lack of clarity: there are some (minor) issues with notation (for instance, $Z$ is used both as a matrix and as a permutation-equivariant function),

We appreciate this observation. To resolve this confusion, we have changed the notation from $Z$ to $\mathcal{Z}$ in our revised manuscript.

2. W1-2: but the overall description of the method should be clarified. I needed multiple reads to understand just how a graph is transformed and, moreover, understand the algorithmic details of this transformation. An overview figure or a brief summary would be immensely helpful here.

To aid in understanding, Figure 1 provides a comprehensive overview of our method. Additionally, Figure 3 in Appendix G summarizes our Point Set Transformer (PST), which we hope will further clarify our approach.

3. W2 Lack of experimental depth: given the strong claims made in the paper concerning a new state of the art, a much more detailed experimental setup is required. In particular, a comparison of the different models in terms of the number of parameters (of the model itself) and the number of hyperparameters is required. Given recent work on improvements in the LRGB data set [1], which are only contingent on hyperparameter tuning, a more detailed explanation of the setup and the comparison is required.

Thank you for the insightful comment. We have updated our manuscript to include more comprehensive experimental details, as you suggested. The updates are reflected in Appendix E, where we provide information about both the number of parameters in the models and the hyperparameters used in our experiments.

1. Parameter Budget Across Datasets:

   • For the zinc, zinc-full, and pascalvoc-sp datasets, we adhered to the baseline parameter budget constraint of approximately 500k parameters.
   • On the peptide-func and peptide-struct datasets, we mistakenly doubled the number of parameters. This occurred because our PST employs two sets of parameters (one for scalar and one for vector), which resulted in twice the parameters with the same hidden dimension and number of transformer layers. We are currently conducting experiments with our PST with smaller hidden dimension and baseline with larger hidden dimensions for these datasets. The results are as followings. Compared with representative graph transformers, our PST performs worse than baselines with parameter 500 K. However, when the PST is scaled to 1M parameters, its performance becomes comparable to, or even surpasses, that of other baseline models like Graph-MLPMixer and GraphGPS. Therefore, our PST can still outperforms baselines with the same parameter budget 1M, and our method is effective on the two datasets. | | peptide-func | peptide-struct | | --- | --- | --- | | #param=500K | | | | Graph-MLPMixer | $0.6970_{\pm0.0080}$ | $0.2475_{\pm0.0015}$ | | GraphGPS | $0.6535_{\pm0.0041}$ | $0.2500_{\pm0.0005}$ | | PST | $0.6344_{\pm0.0041}$ | $0.2543_{\pm 0.0014}$ | | #param=1M | | | | Graph-MLPMixer | $0.7004_{\pm 0.0040}$ | $0.2503_{\pm 0.0031}$ | | GraphGPS | $0.6561_{\pm 0.0027}$ | $0.2557_{\pm 0.0010}$ | | PST | $0.6984_{\pm0.0051}$ | $\mathbf{0.2470_{\pm 0.0015}}$ |
   • Other datasets we explored do not have explicit parameter constraints, and it's worth noting that our PST has fewer parameters compared to representative baselines in these cases.

2. Hyperparameter Configuration:

   • Our experiments involved tuning seven hyperparameters: depth (4, 8), hidden dimension (64, 256), learning rate (0.0001, 0.003), number of warmup epochs (0, 40), number of cosine annealing epochs (1, 20), magnitude of Gaussian noise added to input (1e-6, 1e-4), and weight decay (1e-6, 1e-1).
   • We observed that [1] also used seven hyperparameters in their setup.
   • Batch size was determined based on GPU memory constraints and was not a parameter that we optimized.

[1] Jan Tönshoff et al. Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark. https://arxiv.org/pdf/2309.00367.pdf

4. W3 Table 1 is hard to read and understand at first glance. Please either highlight the best/second-best method or refrain from highlighting altogether. Also, why are there no standard deviations for the other methods?

In the revised manuscript, we have clarified that highlighting in Table 1 indicates models capable of counting the corresponding substructure (test loss < 10 units). This is now explicitly stated for better understanding. As for the lack of standard deviations in other methods, those results are directly sourced from their original papers, which did not provide standard deviations.

• W1-3 After the graph-to-set conversion, how are edge features such as bond types in molecular graphs incorporated into PST?

We will make it more clear in Appendix F in revision. On the ZINC dataset, where edge features are scalar (representing bond types), these are directly considered in the adjacency and Laplacian matrices. For datasets with multi-dimensional edge features, where the adjacency matrix is represented as $A\in \mathbb{R}^{n\times n\times d}$, a theoretical approach is to decompose each channel separately, resulting in coordinates with $d$ channels $Q\in \mathbb{R}^{n\times m\times d}$. However, due to efficiency concerns, we first decompose the adjacency matrix without edge features to obtain coordinates $Q\in \mathbb{R}^{n\times m}$, then compute $A^{(i)}Q$ for each channel $i$ to generate the corresponding channel of the coordinates.

• W2 Another small concern is the computational cost due to use of symmetric rank decomposition. The paper mentions that each layer in PST runs in $O(n^2r)$-time and $O(n^2+nr)$-space, which can be costly if $n$ is large and $r$ must increase proportionally to $n$ in order to cover sufficient connectivity information. Table 10 in the Appendix shows runtime/memory consumption on ZINC, but since ZINC is consisted of fairly small graphs (~23.2 nodes per graph), it is unclear whether PST is scalable to large graphs (e.g. Long Range Graph Benchmark) as well. Could the authors elaborate on this?

The scalability of our approach on large graphs, such as those in the Long Range Graph Benchmark (LRGB), is indeed a challenge. For example, on the Pascal-VOC SP dataset with ~400 nodes per graph, we limited the batch size to 6 and compare it with other GNNs. The results are as follows. We will include these results in Appendix I of our revised manuscript. To address scalability, we are exploring methods like linear transformers or sparse transformers for future enhancements of PST.

• Q1: Does the proposed graph-to-set conversion have any implications on graph generation [A, B, C] as well? Considering that the mapping is a bijection, being able to generate graphs via set generation would be another interesting direction, and any comments could further support the significance of the paper.

Indeed, our graph-to-set conversion offers exciting prospects for graph generation. An orthogonal-transformation-equivariant diffusion model could generate node coordinates, from which the graph structure can be recovered. This approach aligns with techniques in molecule generation, where graphs represent atomic interconnections in 3D space. For instance, [1] utilizes an O(3)-invariant diffusion model for generating atomic coordinates. Our method can extend this idea to a broader range of graphs beyond molecules.

[1] Emiel Hoogeboom et al. Equivariant Diffusion for Molecule Generation in 3D. ICML 2022.

6. Q2 Typo in end of Subsection 7.1: "(Theorem 6 and Theorem 6)" -> "(Theorem 6 and Theorem 7)"

We appreciate this catch and have corrected the typo in the revised manuscript.

We are thankful for Reviewer knXN's comprehensive feedback and address their concerns as follows:

• W1-1: For each experiment, how is the rank $r$ chosen? Is it chosen via hyperparameter tuning? For larger graphs, it seems choosing a small $r$ will result in loss of information on the connectivity of the input graph. How is it that PST still performs well on Long Range Graph Benchmark despite this potential loss of information?

In our approach, $r$ is not a hyperparameter but the intrinsic rank of the decomposed matrix, depending solely on the data. This means there is no information loss associated with the choice of $r$.

• W1-2: For the experiments, which matrix was used to generate the generalized coordinates? The adjacency matrix, or normalized adjacency, or some other matrix? The beginning of Section 4 briefly seems to mention that the method mainly uses the adjacency matrix, but this is not clear from the experimental section. Furthermore, an ablation study on which adjacency matrix works well with PST could be another interesting direction that provides further guidance.

We clarify that various matrices, including the adjacency matrix, normalized adjacency, and Laplacian matrix, are theoretically viable for generating generalized coordinates. In our experiments, we primarily use the Laplacian matrix. This will be made clearer in our revised manuscript.

We have added an ablation study on the choice of matrix for decomposition in the QM9 dataset. The results, displayed in the table below, compare PST variants using different matrices for decomposition against DF, our strongest baseline on the QM9 dataset. The similar performance across PST-Laplacian, PST-Adjacency, and PST-Normalized Adjacency illustrates that our method's effectiveness is not heavily dependent on the specific matrix chosen for decomposition.

Thank you authors for your commitment into sharing the rebuttal with additional results and clarifications.

As shown in the runtime/memory measurements, scaling PST to large networks certainly seems to be a challenge, yet I agree with the authors that this can be addressed in the near future as there exist many approaches designed for making Transformers more efficient.

After reading other reviewers' comments (as well as authors' respective responses), I still think incorporating SRD and an orthogonal transformation-invariant architecture such as PST for graph encoding is a neat approach towards maintaining symmetry under differences in eigenspaces, and the empirical results clearly show its effectiveness.

All of my concerns have been addressed, and thus I retain my score as accept.

We are grateful for Reviewer WPLr's comprehensive feedback and address their concerns as follows:

• W1: One notable weakness in the paper is the tendency to overstate the novelty of certain ideas without providing adequate justification. While the paper introduces a unique method of achieving this transformation through Symmetric Rank Decomposition (SRD), it does not sufficiently acknowledge that the idea of treating graphs as sets of nodes is not entirely novel in the context of graph neural networks. Many existing graph neural network models, including graph transformers, do employ the idea of viewing graphs as sets of nodes for processing. They use various techniques, including positional encodings, to capture and leverage the graph's structural information. While the paper rightfully introduces SRD as a different method for this transformation, it should clarify why this particular approach is advantageous or provides a significant improvement over existing methods. This would help readers understand the specific contributions and benefits of the proposed approach more clearly.

Though we agree that existing graph transformers and ordinary GNNs also encode the nodes, we respectfully argue that our assertion of a "paradigm shift" is not an overstatement. Our innovation is not merely SRD but an entirely different architecture. Existing models still perceive nodes as interconnected, relying on adjacency matrices or their variants, such as random walk matrices, for input. Our approach represents a significant divergence from this norm. By converting graphs to sets of independent nodes and utilizing a set encoder without adjacency inputs, we shift the paradigm from encoding adjacency matrices to crafting set encoders for independent nodes. This paradigm shift, which completely gives up adjacency input, enables a novel model design space too. For example, message passing or attention matrix with adjacency information as relative positional encoding is no longer needed---a set encoder over independent points is enough.

The paradigm shift is rooted in a fundamental difference between SRD and eigendecomposition (EVD), which is commonly used in prior works. As explicated in our Proposition 1, the symmetric rank decomposition (SRD) of a matrix is uniquely determined up to an orthogonal transformation of the entire coordinate system. In contrast, as elucidated in Section 2 of [1], EVD is uniquely determined up to orthogonal transformations within each eigenspace. This fundamental difference allows SRD-based models to effortlessly maintain symmetry (yielding consistent predictions for isomorphic graphs), while EVD-based methods must address each eigenspace individually, making existing EVD-based methods such as [1] hardly work on graph-level tasks where eigenspaces differ between graphs. In essence, SRD leads to a practical bijective conversion of graph problems into set problems where a unified set learner can be applied to different graphs, a property which is not achievable by existing EVD methods.

Furthermore, our method distinctively maintains invariance, producing identical predictions for isomorphic graphs, a feature not consistently achieved by most existing positional encoding methods, such as direct utilization of eigenvectors [2]. This attribute enhances the generalization capabilities of our model.

• W2 & W3: Given the above point, the experiment part should also include the performance of [1] and do a comparison, but it's missing. Another recent graph transformer is missing [2] which seems to have better performance.

We thank the reviewer for these constructive suggestions. In response, we have updated our manuscript to include these comparisons.

Comparison with [1]: Our PST demonstrates a substantial improvement over [1], with a notable 30% margin in performance on both the ZINC and ZINC-full datasets.

Comparison with [2]: Our PST shows competitive performance relative to [2]. On the ZINC dataset, [2] marginally surpasses our model by 9%. However, our PST excels on the larger ZINC-full dataset, outperforming [2] by 33%. Both models achieve nearly identical results on the LRGB datasets.

References:

[1] Sign and Basis Invariant Networks for Spectral Graph Representation Learning, Lim et al., ICLR 2023.

[2] Graph Inductive Biases in Transformers without Message Passing, ICML 2023.

[3] Benchmarking Graph Neural Networks, JMLR 2023.

We appreciate the detailed feedback from reviewer h4E8 and address their concerns as follows:

• W1-1: This paper exaggerates its contributions: this paper claims that the proposed model is a "paradigm shift", but the use of symmetric rank decomposition is actually not much different from existing positional encodings based on eigendecomposition.

Thank you for the valuable comment. We respectfully argue that our assertion of a "paradigm shift" is not an overstatement. Below are detailed reasons.

Distinct Properties of SRD and EVD: As explicated in our Proposition 1, the symmetric rank decomposition (SRD) of a matrix is uniquely determined up to an orthogonal transformation of the entire coordinate system. In contrast, as elucidated in Section 2 of [1], eigendecomposition (EVD) is uniquely determined up to orthogonal transformations within each eigenspace. This fundamental difference allows SRD-based models to effortlessly maintain symmetry (yielding consistent predictions for isomorphic graphs), while EVD-based methods must address each eigenspace individually, making existing EVD-based methods such as [1] hardly work on graph-level tasks where eigenspaces differ between graphs. In essence, SRD leads to a practical bijective conversion of graph problems into set problems where a unified set learner can be applied to different graphs, a property which is not achievable by existing EVD methods.

Paradigm Shift: Owing to this property difference, our model represents a significant departure from existing methods. Contrary to positional encoding methods that require GNNs with inter-node edges as input (even Graph Transformers still use adjacency matrices or their variants), our approach converts the graph into a set of independent nodes and employs a set encoder without adjacency inputs. This shift from encoding adjacency matrices of interconnected nodes to using set encoders for independent nodes, devoid of edge information, signifies a major deviation from traditional methodologies. This paradigm shift, which completely gives up adjacency input, enables a novel model design space too. For example, message passing or attention matrix with adjacency information as relative positional encoding is no longer needed---a set encoder over independent points is enough.

Maintaining Invariance: Our method distinctively maintains invariance, producing identical predictions for isomorphic graphs, a feature not consistently achieved by most existing positional encoding methods, such as direct utilization of eigenvectors [3]. This attribute enhances the generalization capabilities of our model.

• W1-2: Also, the invariance to orthogonal transformations of positional encoding is discussed and addressed by several related papers (e.g., [1]). I don't think the proposed model is significantly different.

We agree that both our work and [1] address the concept of invariance to orthogonal transformations. Nevertheless, there are significant differences between the two approaches, encompassing the fundamental properties of the two decompositions, the resulting invariance, the architectural designs, and the overarching paradigms.

Nature of Orthogonal Transformations: Although both works refer to orthogonal transformations, the contexts in which they are applied differ markedly. In our approach using symmetric rank decomposition (SRD), the orthogonal transformation is applied to the entire coordinate system. In contrast, the orthogonal transformation in the eigendecomposition (EVD) used in [1] is specific to each eigenspace.

Addressing Orthogonal Invariance: This fundamental distinction in decomposition means that [1] cannot completely solve the issue of orthogonal invariance. Our model can directly integrate an invariant set encoder with the coordinates generated by our SRD. Conversely, [1] is compelled to address each eigenspace individually, resulting in an architecture (BasisNet) that is only applicable to graphs with a fixed number of multiple eigenvalues. This limitation is impractical for graph tasks with varying numbers of multiple eigenvalues. For real-world datasets, [1] is forced to compromise on orthogonal invariance by assuming a uniform multiplicity of 1 for all eigenvalues, as seen in SignNet.

Divergent Network Structures: The above difference also leads to distinct network structures. SignNet and BasisNet in [1] require specialized blocks like invariant graph networks and address eigenvectors in each eigenspace separately. In contrast, our Point Set Transformer (PST) more closely resembles a conventional transformer. In fact, our paradigm only requires a set encoder invariant to orthogonal transformations, thus enabling very flexible model choices not limited to the transformer which we implement in this paper.

Thank you for your thoughtful feedback and for considering our response. We appreciate your acknowledgment of the improvements our proposed methodology brings over existing approaches. However, we would like to further clarify why we believe our work constitutes a "paradigm shift" in the context of graph transformers.

• First, we would like to point out that While it is true that existing graph transformers utilize positional encodings to capture graph structure, they typically still rely on the adjacency input. Specifically,

1. Grit [1] and graphit [8] uses random walk matrix (normalized adjacency matrix) as relative positional encoding.
2. Vanilla Graph Transformer [6], Graphormer [2] and SAN [3] uses adjacency matrix as relative positional encoding. [2]'s ablation shows that adjacency is crucial.
3. GPS [4], Exphormer [5], higher-order transformer [7], Graph Vit/MLP-Mixer [9] even directly incorporating message passing block which use adjacency matrix to guide message passing between node.

Therefore, our method without adjacency input differs from existing models in architecture significantly.

• We emphasize that this architecture distinction is not just a minor improvement but a substantial departure from the prevailing approach. By doing so, we enable a different design space for GNN, where set encoders can be applied to graph tasks easily, opening up opportunities for novel applications and addressing potential limitations associated with adjacency-based methods. For example, we can also employ set encoders other than transformer like deepset, as demonstrated in our response to Reviewer 8dzn's

In summary, we believe that our work, using set encoder without adjacency input for graph task, represents a significant paradigm shift, and we hope that you will reconsider our claim in light of this explanation. We value your perspective and look forward to any further discussion or feedback you may have.

Best, Authors.

[1] Liheng Ma et al. Graph Inductive Biases in Transformers without Message Passing. ICML 2023.

[2] Chengxuan Ying et al. Do Transformers Really Perform Badly for Graph Representation? NeurIPS 2021.

[3] Devin Kreuzer et al. Rethinking Graph Transformers with Spectral Attention. NeuIPS 2021.

[4] Ladislav Rampásek et al. Recipe for a General, Powerful, Scalable Graph Transformer. NeurIPS 2022

[5] Hamed Shirzad et al. Exphormer: Sparse Transformers for Graphs. ICML 2023.

[6] Vijay Prakash Dwivedi, Xavier Bresson. A Generalization of Transformer Networks to Graphs. https://arxiv.org/abs/2012.09699.

[7] Jinwoo Kim et al. Transformers Generalize DeepSets and Can be Extended to Graphs and Hypergraphs. NeurIPS, 2021.

[8] Gregoire Mialon et al, GraphiT: Encoding Graph Structure in Transformers. arXiv/2106.05667.

[9] Xiaoxin He et al. A Generalization of ViT/MLP-Mixer to Graphs. ICML 2023.

Dear Reviewers,

We sincerely appreciate your dedicated time and effort in reviewing our paper. As the discussion stage is rapidly coming to a close, we kindly request your prompt attention to our rebuttal. Your valuable insights and feedback are integral to ensuring a fair and comprehensive evaluation of our paper.

We eagerly anticipate your continued input on our work. If you still have any lingering questions or unresolved concerns, please don't hesitate to reach out. We are more than willing to provide further clarification and address any issues that may arise.

Thank you once again for your invaluable contributions to the review process.

Many thanks, Authors