Further Response and New Results on Basis Invariance
Thanks for your reply and the new comments! We are very glad to hear that your concerns are addressed. We will address your remaining points below.
---
**Q1.** Presentation issue.
> The current presentation, particularly the introduction, is not as beautiful as it goes like "MAP has all (like Table 1), also outperforms the existing ones". Instead, I feel the authors need to write reservations about the discussion above. [And more suggestions…]
>
**A1.** Thanks for your detailed and valuable suggestions! We totally agree that we can rephrase the words to present MAP’s properties more precisely. We will tune down the claims here to make them more explicit. And as you suggested, we will mention 1) MAP achieved comparable performance but with much better efficiency; 2) the basis part of MAP is less influential on real-world data due to the small portion of basis ambiguity.
---
**Q2.** Finding real application where basis matters.
> Since improvement from BasisNet to MAP is enormous, almost like impractical to practical, I recommend the authors find datasets where the basis ambiguity really matters. Even the synthetic data will help, but ideally, it'll be nice if "the specific domains and model choices," as mentioned in the previous discussion, are provided.
>
**A2.** Thank you for your insightful feedback. Firstly, we'd like to emphasize that the primary contribution of our work is indeed the MAP-sign. Its effective performance on real-world data is demonstrative of this. The capability of MAP to address basis invariance is, in many ways, an added advantage rather than the core contribution.
Nevertheless, we understand and appreciate your point that it will be nicer to see the advantages of MAP on addressing basis ambiguity, compared to RandSign and SignNet.
To address this, we undertook further research. As mentioned in our paper, real-world graphs mostly exhibit a maximum of 10% basis ambiguity. Up to this point, we've not identified a suitable real-world dataset. In Appendix G, we've highlighted that the probability of basis ambiguity approaches 0 on random graphs as $n\to \infty.$ Therefore, **basis ambiguity primarily exists in small and highly symmetric graphs**. Given this, and in line with common practices for expressive GNNs, we decided to utilize synthetic hard examples to test the efficacy of our proposed method.
**Synthetic Experiment.** We used Graph Isomorphic Testing, a traditional graph task. Our focus was on 10 non-isomorphic random weighted graphs ($G_1,\dots,G_{10}$), all exhibiting basis ambiguity issues (with the first three eigenvectors belonging to the same eigenspace). We sampled 20 instances for each graph, introducing different permutations and basis choices for the initial eigenspace. The dataset was then split into a 9:1 ratio for training and testing, respectively. The task was a 10-way classification, where the aim was to determine the isomorphism of a given graph to one of the 10 original graphs. The model was given the first 3 eigenvectors as input (i.e. $k=3$). The results were averaged over 4 different runs.
*Test accuracy of the synthetic graph isomorphic testing task with DeepSets using different PEs*
| PE | Accuracy |
| --- | --- |
| LapPE | 0.11 ± 0.08 |
| LapPE + RandSign | 0.10 ± 0.09 |
| LapPE + SignNet | 0.10 ± 0.03 |
| LapPE + MAP | **0.84 ± 0.21** |
**Results.** As evident from the results, approaches that address sign ambiguity (like RandSign and SignNet) cannot obtain nontrivial performance on this task. Conversely, MAP shows commendable performance. The 84% accuracy, although impressive, indicates potential avenues for further enhancement. We believe this synthetic task could also serve as a valuable benchmark for future studies addressing basis invariance through canonization.
---
Hope the above clarification and additional experiments could ease your concerns. We are happy to take your further questions!