Polynormer: Polynomial-Expressive Graph Transformer in Linear Time

Response to Reviewer uwZk

We thank the reviewer for the constructive feedback and insightful questions on our work. Here are our detailed responses to address the concerns: **C1: Polynomial expressivity of GTs and GNNs with nonlinear functions.** A1: Firstly, we would like to note that it is important to analyze the polynomial expressivity of prior graph models without nonlinear functions, as it emphasizes the need for the activation functions in those models to achieve reasonable accuracy. This highlights Polynormer’s advantage in polynomial expressivity, which allows Polynormer to achieve promising results without the use of activation functions. While integrating nonlinear functions into prior graph models implicitly represents a high-degree polynomial, the polynomial coefficients are fixed since those nonlinear functions are typically not learnable. As a result, these models still cannot be parametrized to adaptively learn a polynomial that consists of specific monomials. In contrast, Polynormer learns the high-degree polynomial with coefficients controlled by trainable attention scores, enabling it to expressively represent various polynomial functions. **C2: Do GTs have $\infty$-polynomial expressivity?** A2: While it is true that GTs with positional encoding are universal approximators, they require unbounded depth to achieve this property. In practice, however, GTs typically have fixed and small depths (e.g., 2~3) and thus do not have $\infty$-polynomial expressivity. **C3: Why modeling polynomial expressivity of graph models?** A3: Graph models essentially learn node representations by aggregating features from a set of nodes, which can be viewed as a multiset pooling problem with auxiliary information about the graph structure [Hua-NeurIPS22; Baek-ICLR21]. Thus, the polynomial expressivity measures how well a graph model incorporates the auxiliary structural information. For instance, given a node $i$ and its $1$-hop neighbors $j$ and $k$, a model A that learns $x_i+x_j+x_k+x_ix_jx_k$ is more expressive than a model B that only learns $x_i+x_j+x_k$, since A incorporates the third-degree monomial $x_ix_jx_k$ that captures third-order structures (either a triangle or a path formed by nodes $i$, $j$, $k$). **C4: More experiments to support linear complexity.** A4: Thanks for the suggestion. In our revision, we added the training time and memory usage of Polynormer on synthetic graphs with various sizes in Appendix J.1, which confirms that Polynormer has linear complexity with respect to the number of nodes/edges in a graph. Moreover, we further provide the complete profiling results of Polynormer and GT baselines in terms of training time and memory usage on three large graphs in Appendix J.2. The results showcase that Polynormer consistently ranks the top 3 fastest models with relatively low memory usage. This demonstrates the scalability advantage of Polynormer over prior GT models. **C5: Connection of Polynormer to WL-test expressivity.** A5: This is a great question. Indeed, it is interesting to see if Polynormer can be more powerful than 1-WL GNNs under the WL hierarchy. In response to this question, we have included Appendix K in our revision and made reference to it in Section 3.3 (marked in blue). Concretely, we show that by properly designing the weight matrix B in Equation 4, Polynormer can be more expressive than 1-WL GNNs. Initially, we set $B=\mathbf{1} \beta^T$ to build our Polynormer model. Note that the constant vector $\mathbf{1}$ here is essentially the eigenvector $v_1$ that corresponds to the smallest graph Laplacian eigenvalue. This motivates us to design $B = v_2 \beta^T$, where $v_2$ denotes the eigenvector corresponding to the second smallest (i.e., first non-trivial) Laplacian eigenvalue. To differentiate between these two choices of designing $B$, we denote the Polynormer of using $v_1$ and $v_2$ by Polynormer-v1 and Polynormer-v2, respectively. We then show that Polynormer-v2 is able to distinguish non-isomorphic graphs such as circular skip link graphs, which are known to be indistinguishable by the 1-WL test as well as 1-WL GNNs. Through empirical comparison of Polynormer-v2 with Polynormer-v1 in Table 8 (Appendix K), however, we observe similar accuracy achieved by both models on realistic node classification datasets. Hence, we implement Polynormer based on Polynormer-v1 in practice to avoid computing the Laplacian eigenvector, and leave the improvement of Polynormer-v2 to our future work. [Hua-NeurIPS22] Hua et al., “High-Order Pooling for Graph Neural Networks with Tensor Decomposition”, NeurIPS’22. \ [Baek-ICLR21] Baek et al., “Accurate Learning of Graph Representations with Graph Multiset Pooling”, ICLR’21.

Response to Reviewer D5Yt

We appreciate the positive comments and interesting considerations. Here are our detailed responses: **C1: Polynormer in other fields such as NLP.** A1: We agree with the reviewer that our approach could potentially be applied in other domains (e.g., NLP), although exploring such a direction is beyond the scope of this work. We believe that introducing a novel and powerful graph transformer is a significant contribution in its own right. **C2: Why and how polynomial expressivity improves performance.** A2: High polynomial expressivity indicates that the model is capable of learning high-order interactions among node features. For instance, given a node $i$ and its $1$-hop neighbors $j$ and $k$. Conventional GNNs capture first-order (linear) feature interactions such as $x_i, x_j, x_j+x_k$ during neighbor aggregation. In contrast, a polynomial-expressive model captures additional higher-order interactions such as $x_i^2x_j, x_ix_jx_k$, etc. Notably, the high-order interactions implicitly correspond to high-order graph structures (e.g., $x_ix_jx_k$ corresponds to either a triangle or a path formed by nodes $i, j, k$.), which are known to be crucial for many graph problems. **C3: Definition of polynomial degree.** A3: The polynomial degree refers to the highest degree among monomial terms in the polynomial. In this work, the degree of a monomial term represents the number of node features for the Hadamard product, as defined in Equation 10 (Appendix A).

Response to Reviewer HGJh

We thank the reviewer for the positive evaluation and valuable comments. Here are our detailed responses to address the concerns: **C1: Assumption on scalar node features.** A1: We would like to clarify that our proof makes no assumption about node features being scalars. Specifically, given a node feature matrix $X \in R^{n \times d}$, we first define a monomial term representing the Hadamard product of a series of $d$-dimensional node features $X_i \in R^d$, as illustrated in Equation 10 (Appendix A). Subsequently, we prove by induction in Equations 12 and 13 that Polynormer learns a polynomial which is a linear combination of the monomial terms defined in Equation 10. Thus, our proof considers high-dimensional node features. In our revision, we further highlight the shape of $X$ and $X_i$ in Appendix A (marked in blue) to indicate that our proof is not restricted to scalar node features. **C2: Runtime and memory usage on large graphs.** A2: Thanks for the suggestion. In our revision, we have added the complete profiling results of Polynormer and GT baselines in terms of training time and GPU memory usage on three large graphs in Appendix J.2, which we reference in Section 4.2 (marked in blue). The results showcase that Polynormer consistently ranks the top 3 fastest models with relatively low memory usage. This demonstrates the scalability advantage of Polynormer over prior GT models. Moreover, we also show the profiling results of Polynormer on synthetic graphs with various sizes in Appendix J.1, which confirms that Polynormer has linear complexity with respect to the number of nodes/edges in a graph.