On the Expressive Power of Sparse Geometric MPNNs

New version and answers

**Weakness 1:** Considering generic geometric graphs only rather than all geometric graphs significantly weakens the significance of theoretic results. Though degenerated cases are rare, they can affect model's performance on generic graphs as neural networks are smooth. The inclusion of high-order irreducible representations solves these cases and boosts performance significantly.[1, 2] **Answer 1:** We agree that the generic assumption is a strong assumption. Nonetheless, our model demonstrates substantial improvements across three benchmarks in real-world tasks, even in comparison to methods that use high-order irreducible representations like GemNet (see Table 2 in our submission), indicating that our analysis holds practical relevance. We believe this is due to the fact that these datasets do not exhibit many symmetries, as shown by the fact that they do not have many repeated norms. See Table 8 of the revised version of our submission for the details. For more challenging problems with many symmetries, stronger methods may be advisable. **Weakness 2:** Previous work also considers expressivity on geometric graph without assuming fully connection. [3] proves in that in non-degenerated cases, MPNN with equivariant feature can distinguish connected graphs, while MPNN with invariant features only cannot. **Answer 2:** Thanks for suggesting this reference. We have added it to the Related Work section of the paper. **Weakness 3** Experiment should includes graph force field tasks on qm9 and md17 as previous works [2]. **Answer 3** Thanks for the suggestion. Our paper includes promising results on three molecular property prediction tasks and several synthetic datasets. We think this is sufficient to prove the validity of our results, but we will be happy to look into these applications in future work.

New version and midification

**Weakness:** Although I understand that the assumption of genericity makes the analysis tractable, this remains a significant limitation. Real-world geometric graphs, particularly in the chemical domain, can exhibit lots of symmetries that cannot be overlooked. **Answer:** You raise a valid point. Our response is divided into three parts. Firstly, this assumption is essential for distinguishing all connected graphs, as distinguishing all geometric graphs entails separating all graphs, which is a challenging problem with no known polynomial time algorithm (graph isomorphism). Secondly, from a practical perspective, our results on real-world chemical property benchmarks demonstrate substantial improvements across at least four datasets. Thus, the theoretical advantage in the generic setup also benefits practical applications in real-world contexts. Lastly, the fact that the genericity assumption is rather strong highlights the shortcoming of invariant models which in some settings fail *even for generic graphs*. **Question**: Did you conduct experiments on how EGenNet compares to the other benchmarks on non-generic geometric graphs? A step towards this could be looking at the levels of symmetry that the graphs in the chemical dataset exhibit (i.e., distances between nodes or graph automorphisms), and analyzing the performance of EGenNet vs. the other benchmarks on such graphs. **Answer**: Thank you for your suggestion. To test this, we have checked the number of repeated norms in the datasets we used in the paper, and found that for the most part these norms are distinct (with a reasonable threshold). We added these results in Table 8 in the revised version. **Question**: In section 5.1, the EGenNet architecture comes a bit out of nowhere. Perhaps, a paragraph with an intuitive explanation why the update step is defined as it is in equation 5 and how it relates to maximal expressivity would add to the overall understanding of the method. **Answer**: Regarding your suggestion, we have incorporated more intuitive explanations of the model in the uploaded version. **Question**: The results for chemical property prediction could be discussed in more detail. Specifically, a further analysis of the number of parameters or training runtimes of the different models compared in Table 2 would be interesting to see. **Answer**: Thanks for the suggestion, In the appendix, we included a table(7) detailing the running times of each model on the 12-chain dataset while all models exhibit a 128-dimensional feature. We show that our model is comparable with the best models and much faster than other models like dimenet and spherenet with same hidden dimension. **Question**: There are lots of presentation issues in the script that should be fixed, e.g., inconsistent usage of \citep/\citet, misalignment of tables (Table 2, Table 4, Table 5, Table 6), inconsistent caption alignment, Table 6 seeming to be a screenshot from its original source, or "todo" comments (line 451). **Answer:** All presentation issues have been addressed and corrected in the updated version. Thank you once again for the helpful feedback.

Our answer to your requests

**Weakness:** I find the connection of generic matrices with the use cases of graphs complicated. The authors do not show a clear motivation on defining expressivity over generic spaces for the use over graphs. Can the authors motivate better the analysis over generic spaces? What happens in the non-genericity direction? **Answer:** We believe these issues are discussed extensively in the introduction, mostly in the paragraphs leading to Question 1. We will summarize the discussion: geometric graphs are graphs which have continuous 3D node features. They arise in many applications, e.g., as models for molecules. GNNs which are complete when considering all geometric graphs, discussed in [1],[2] require a unrealisticially high computational complexity of n^4. This motivates the problem of considering graphs with ‘generic’ 3D coordinates: almost all graphs, in the Lebesgue sense, are generic, and when restricting to such graphs simple models with linear to quadradic complexity (see next question) are sufficient, as we show here. **Weakness:** The tradeoff between efficiency and expressiveness is confusing. It seems that still if we want to achieve maximal expressiveness leads to quadratic complexity (G.2 Section), not having a clear understanding of the expressivity loss, once we set \( C < 2Nd + 1 \). **Answer:** You are right. According to the analysis presented in the paper, the worst-case complexity is indeed quadratic. This is still much more efficient than provably complete models which have n^4 complexity, as described in [1]. We would also like to point out that mathematical complexity and approximation bounds are often unrealistically high. As researchers in this field for several years, we actually regard both the n^4 complexity in [1] and the n^2 complexity here as significantly good bounds. For comparison of much higher bounds for arguably simpler problems see for example [3]. Finally, we note that our analysis could easily be extended to show that, under the common ‘manifold hypothesis’, which states that the data comes from a low k dimensional manifold, only C=O(k) channels will suffice for generic completeness. In this case, the complexity would be truly linear. We have avoided going into these details in the paper, since, as the reviewers have noted, this paper is already mathematically involved. **Weakness:** The theoretical analysis is hard to follow. There are a lot of typos, and inconsistencies. There are forgotten TODOs in the main text (check Section 6.2), and elements of the paper are not even visible (for example Table 5 does not fit the page). **Answer:** Regarding typos and other writing issues, we have updated them. If the theoretical analysis is difficult to follow in certain sections, please let us know which parts are challenging, and we will clarify them accordingly. [1] Hordan, Snir, et al. "Complete neural networks for Euclidean graphs." AAAI 2024), [2]- Delle Rose, Valentino, et al. "Three iterations of (d−1)-WL test distinguish non-isometric clouds of d-dimensional points." Advances in Neural Information Processing Systems 36 (2024) [3] Polynomial Width is Sufficient for Set Representation with High Dimensional Features. Wang et al. ICLR 2024

Our answer to all your requests

All our modifications were added in blue. **Weaknesses 1:** I have two major concerns regarding the submitted work. Incomplete Submission: The paper contains 'TODO' placeholders and formatting issues, indicating it is an unfinished draft. This severely hinders the ability to conduct a thorough and fair review and compromises the integrity of the review process and the conference's high standards. Additionally, these issues distract from the paper’s overall clarity and presentation, which could lead to misunderstandings of the proposed ideas and results. **Answer 1:** You are absolutely correct, the paper did indeed contain a (single) TODO placeholder and had some formatting issue. We apologize for the oversight. In the new version we uploaded, all of these issues have been addressed as per your feedback. Aside from these issues, we believe the paper is well-written and in solid form. In fact, we have finished this paper early, had carefully rewritten it several times, and have received feedback from several peers regarding our work. The missed TODO remark was aimed to fix one of these remarks. We again apologize for the oversight but would like to stress that a lot of work was put into this submission, and it is not an “unfinished draft”. **Weakness 2**: Lack of Consistency and Discussion in Empirical Results: The empirical results lack completeness and coherence… A more thorough discussion and clear presentation of results are necessary to support the paper's claims. **Answer 2:** Thank you for your remark. In the new submission, the empirical results section has been updated, with the objectives and findings explicitly explained for each section of experiments; please take a look. We have added our objectives for the experiments and clearly explained the results obtained. **Questions:** Below is a partial list of incomplete work: The paper is not formatted to the ICLR standard, e.g., it is missing the header "Under review as a conference paper at ICLR 2025." The inline citation format is incorrect. Section 6.2 contains a "TODO" placeholder. The second paragraph of Section 5 contains two egregiously run-on sentences. Tables 2, 4, 5, and 6 extend beyond the page margins, with Table 5 exceeding the page to the point where the results are unreadable. Table 4 uses an incorrect title for the model, referring to it as GenNet. **Answer :** All table, template, and formatting issues have been resolved in the updated version. Thanks again. **Questions (theoretical):** The definition of "identifies" appears to be equivalent to the definition of a complete invariant function F. Per Section 1 and Appendix B: "The main text discussed how generic completeness can be achieved using I-GGNN when the graph is globally rigid." Is there a reason that the terminology of completeness that appears in the introduction and appendix is dropped in the definitions of Section 2 in favor of "identifies"? Maintaining consistent terminology would significantly enhance clarity **Answer:** The term ‘complete’ is a somewhat informal term used in the literature. We do not define it here. The term identifies has a precise mathematical definition. Roughly, though, a model is complete if it identifies all graphs. We added a comment to this affect in the new version of the paper (page 4) **Question:** The cutoff in Table 5 and inconsistencies between Table 6 and Table 3 make it difficult to interpret the significance of the reported results. Could the authors please explain the discrepancies between the tables **Answer:** Regarding the tables, I believe you are referring to Tables 2 and 6. In Table 2, we show the best seed, while in Table 6, we present the average overall seeds. The same two tables were presented in the paper introducing this dataset (Zhu et al. 2024). **Question:** In Kraken BurL and BDE, it appears that EGenNet significantly outperforms the previous state of the art, especially for BDE. Could the authors provide an explanation for why this major improvement occurs for the BDE dataset? **. **Answer:** We conjecture this is because these datasets are ‘close to being generic’. To check this conjecture, we checked the norms of atoms in the centralized molecules of the dataset to see if they were repetitive or not. We found that the molecules contain a very small percentage of repeated norms, confirming our conjecture. These results were added to our revised submission in Table 8.