Learning Efficient Positional Encodings with Graph Neural Networks

We thank the reviewer for appreciating our work and providing valuable feedback. The reviewer’s concerns can be summarized into the following key questions:

1. Does our method require additional regularizers to achieve its objectives?
2. How do random features compare to eigenvectors when they initialize node embeddings?
3. How does our method compare to Random GNN [1] and PF-GNN [2]?
4. How does our method empirically perform in identifying graphs that are not distinguishable by 1-WL GNNs?

Our short answers are as follows:

A1:
Our framework does not inherently require additional regularizers, which could introduce unnecessary bias and complexity, potentially affecting its generality and scalability. The universality theorem (included in the revised manuscript) and expressivity/generalizability results, supported by empirical evidence, validate this claim.

A2:
GNNs initialized with random features, as in the proposed R-PEARL, demonstrate both theoretical and empirical advantages over eigenvector-based GNNs, but only when equivariance is preserved. R-PEARL offers an elegant and effective solution in this regard. However, when equivariance is violated, as in Random GNN, eigenvector-based GNNs exhibit better performance.

A3:
We have already included comparisons with Random GNN in the original manuscript. Random GNN, being non-equivariant, is significantly outperformed by our proposed framework. Furthermore, our method achieves nearly twice the performance of PF-GNN in the logP prediction task on ZINC. However, it is worth noting that this comparison may not be entirely fair, as PF-GNN is primarily a backbone GNN and could also benefit from the enhancements proposed in our framework.

A4:
We added experiments using the CSL dataset, which serves as a gold standard for graph isomorphism benchmarks. Our framework achieves 100% classification accuracy, demonstrating its strong empirical capability in identifying graphs not distinguishable by 1-WL GNNs.

Detailed responses to these points are provided below.

We thank the reviewer for their valuable input. The main concerns of the reviewer can be summarized into the following points:

1. The reviewer requests further clarification regarding the rationale for using message-passing GNNs as the foundation for graph positional encodings (PEs).
2. The reviewer asks about the impact of noise on the permutation equivariance properties of our R-PEARL framework.
3. The reviewer expresses concerns about the sample complexity of R-PEARL and its dependence on node degrees.
4. The reviewer mentions that Theorem 4.3, as well as Propositions 4.1, 4.2, and 4.3, are direct corollaries of previously established results.
5. The reviewer requests additional experiments to further demonstrate the effectiveness of our proposed approach.

Our short answers are as follows:

A1:
To address this point we refer the reviewer to the motivation of our work. In the introduction we mention that our work is motivated by the following question. Can we learn generic PEs that are simultaneously expressive, stable, and scalable? Throughout the paper we explain that the proposed GNN-based PEs are indeed capable to to provide an affirmative answer. On the contrary, other PE methods, such as random PEs, eigenbased PEs, and structural PEs fail to jointly satisfy these properties. In a nutshell, random PEs are not stable and generalizable, eigenbased PEs cannot be simultaneously scalable and stable, and strucutral PEs add bias and complexity to our models.

To address this point, we refer the reviewer to the motivation outlined in the introduction of our work. Specifically, our study is guided by the following question: Can we design generic PEs that are simultaneously expressive, stable, and scalable?

In the manuscript, we systematically establish that the proposed GNN-based PEs effectively provide an affirmative answer to this question. In contrast, alternative PE methods fail to simultaneously fulfill these essential criteria. Specifically:

• Random PEs lack both stability and generalizability.
• Eigen-based PEs have an inherent trade-off between stability and scalability.
• Structural PEs introduce bias and in certain cases increase the overall complexity of the model.

These limitations underscore the advantages of our approach, which successfully addresses the trade-offs encountered by existing methods.

A2:
We emphasize that noise does not affect B-PEARL, it only plays a role in R-PEARL. However, it is crucial to highlight that R-PEARL is not merely equivariant in expectation; it serves as an unbiased estimator of the expectation. This distinction implies that, with a sufficient number of samples—as theoretically established in Theorem 3.1—R-PEARL achieves practical equivariance.

To empirically substantiate this claim, we measured the relative difference in the R-PEARL positional encodings generated for each node across multiple runs. The results demonstrate that the variability introduced by noise is negligible compared to the inherent differences in node features. This observation supports our claim that R-PEARL is effectively equivariant in real-world applications.

A3: This is a subtle point that requires a detailed explanation. In summary, the sample complexity of our method is independent of the graph size or node degrees when the message-passing mechanism is based on normalized graph shift operators (GSOs), such as normalized adjacency, Laplacian, or random walk matrices. Notably, this is the implementation we used in practice.

Even in scenarios where the message-passing mechanism resembles classical adjacency or Laplacian operators, the incorporation of batch normalization or layer normalization significantly mitigates variance, rendering it practically independent—or only slightly dependent—on the graph size. This ensures robustness and scalability of R-PEARL in real-world applications.

A4:
While Propositions 4.1, 4.2, and 4.3 are indeed direct corollaries of previous results, and we have renamed them as such in the revised manuscript, we do not see why this should be considered a limitation. Our contribution does not merely analyzes the stability or expressivity of an existing architecture but instead introduces a novel PE framework. Since our architecture is a GNN, it is unavoidable to inherit some properties from existing work. Note, however, that Theorem 4.3 represents original work, is not a direct corollary of any prior conclusions. To add further novelty to the expressivity analysis of our work we prove that PEARL is a universal approximator of basis invariant functions.

Thank you for the detail response. However, my concerns are not solved, so I keep my score to reject. Why my concerns maintain is detailed as follows.

1. The abstract states that this work investigates positional encodings (PEs) for graphs based on four key criteria: stability, expressive power, scalability, and genericness. However, the focus is primarily on eigenvector-based PE, and the analysis is limited to the authors' proposed method, R-PEARL, regarding these criteria. A more comprehensive theoretical analysis and comparison with other PEs are needed.

The authors add some discussion, but what I expect is a quantitive comparison. For example, the sample complexity comparison between R-PEARL and random PE, and the expressivity comparison between B-PEARL and structural PE.

2. The rationale behind using Message Passing Neural Networks (MPNNs) to generate PEs is not clearly explained. Proposition 3.1 appears to be trivial, as graphs (represented by adjacency matrices and node features) can be bijectively mapped to eigenvectors, eigenvalues, and node features. Consequently, all graph functions, including PEs, can be seen as functions of eigenvectors when parameters include both eigenvalues and node feature. Therefore, the justification for choosing MPNNs as eigenvalue function over other graph models is not evident.

Authors agreed that Proposition 3.1 is trivial. MPNN may have many advantages, but Proposition 3.1 is not persuative and can be removed.

3. Theorem 4.3 and the claim that "our proposed PE framework is well-suited for large-scale graphs" are questionable. The proof of Theorem 4.3, specifically Formula (45), includes the maximum degree of the graph, which is latter included in β. Considering β as a constant is problematic because large social networks often contain nodes with high degrees, which would require more samples for accurate representation.

Authors said by normalization, $\beta$ can be small for even graph with large node degree. But with normalization, both signal and the noise can be scaled to be small, so a smaller error bound \epsilon in Equation 9 is needed. A more systematic way is to compute signal to noise ratio.

4. Most theoretical results (Theorem 4.3, Proposition 4.1, 4.2, 4.3) are direct corollaries of previous conclusions.

Authors agreed that Proposition 4.1, 4.2, 4.3 are direct corollaries of previous conclusions. We still consider that Theorem 4.3 as a direct corollary, which only computes the Lipschitz constant of GNN and applies the conclusion of Lipschitz functions' sample complexity in the original proof. Currently, the proof the Theorem 4.3 is missing.

The newly added Theorem (PEARL is a universal approximator of basis invariant functions) is also doubtful. In line 907-909 of the proof, basisnet need g with universal expressivity for universality of the whole model, but PEARL uses only MPNN. Moreover, the Theorem assume the model exists for each fixed set of eigenvalue, but in practice, we need one model to work for all eigenvalue sets as the input graph changes.

5. The experimental section is limited to four datasets. To strengthen the validity of the results, additional datasets should be included as in [1].

Only one smallest synthetic dataset CSL in [1] is added. Commonly used datasets like long range graph benchmark and ogbg-molhiv in [1] are ignored. Please add them.

6. The PE is used in conjunction with a GNN backbone, but the backbone for PEARL appears to be fixed across all experiments. To demonstrate the broad applicability and ensure a fair comparison among different PEs, experiments on PEs with different GNN backbones should be added, as recommended in [2].

Up to now, ablation study on GNN backbone is not added.

Authors agreed that Proposition 4.1, 4.2, 4.3 are direct corollaries of previous conclusions. We still consider that Theorem 4.3 as a direct corollary, which only computes the Lipschitz constant of GNN and applies the conclusion of Lipschitz functions' sample complexity in the original proof. Currently, the proof the Theorem 4.3 is missing.

We would like to kindly point out that the proof of Theorem 4.3 is not missing; it has been included in the Appendix in all versions of our manuscript. We respectfully note that it is unclear how the reviewer could evaluate our proof without being aware that it is already part of the manuscript.

The newly added Theorem (PEARL is a universal approximator of basis invariant functions) is also doubtful. In line 907-909 of the proof, basisnet need g with universal expressivity for universality of the whole model, but PEARL uses only MPNN.

We also employ an equivariant pooling function without imposing any additional restrictions. For further details, we kindly refer the reviewer to line 208 of the first version of the revised manuscript: "design an equivariant pooling function $\rho$ to generate the final PE for each node". The only requirement for $\rho$ is that it be equivariant. We have updated the manuscript to clarify this point further: "To address this, we design an equivariant function $\rho$, that involves a pooling operation over the independent outputs $\{\mathbf{P}^{(m)}\}_{m=1}^M$, to generate the final PE for each node."

In the proof we also mention:

We can choose $\rho$ to operate on each feature independently i.e.,

$\mathbf{Y}=\rho\left(g^{(1)}\left(\mathbf{V_{\mu_1}}\mathbf{V_{\mu_1}}^T\right),\dots,g^{(q)}\left(\mathbf{V_{\mu_q}}\mathbf{V_{\mu_q}}^T\right)\right),$

where $g^{(i)}$ is universally approximating permutation equivariant or invariant function, e.g., high-order tensor IGN.

Moreover, the Theorem assume the model exists for each fixed set of eigenvalue, but in practice, we need one model to work for all eigenvalue sets as the input graph changes.

Universality is an existence claim, different than generalizability. G can model any possible set of input graphs as disconnected components. Then the GSO will have a block diagonal form and each block will be the GSO of each graph. The rest of the proof is exactly the same. We add this note to the manuscript.

5. The experimental section is limited to four datasets. To strengthen the validity of the results, additional datasets should be included as in [1].

Only one smallest synthetic dataset CSL in [1] is added. Commonly used datasets like long range graph benchmark and ogbg-molhiv in [1] are ignored. Please add them.

We have added experiments on the peptide-structure dataset. Overall, PEARL is tested across 10 (9 real-world, 1 synthetic) diverse tasks spanning 5 distinct graph types. We firmly believe that this represents an objectively sufficient experimental setup for testing any graph ML framework. For your reference [1] is tested on 7 real-world task, without any large graphs.

Table: Test MAE on the Peptides-struct dataset.
B-PEARL achieves the second-best performance, behind Graph ViT, within a $500$k parameter budget. Graph ViT utilizes additional random walk information, while B-\method~learns this information via training.

6. The PE is used in conjunction with a GNN backbone, but the backbone for PEARL appears to be fixed across all experiments. To demonstrate the broad applicability and ensure a fair comparison among different PEs, experiments on PEs with different GNN backbones should be added, as recommended in [2].

Up to now, ablation study on GNN backbone is not added.

These ablation study has now been added to the manuscript along with other ablation studies.

Table: Test MAE of PEARL with different backbones within a 500k parameter budget.

We conduct additional base model ablations, using PNA, GatedGCN and GINE on the ZINC dataset. PEARL demonstrates strong performance across various backbones, while consistently outperforming equivalent SignNet models with the same backbones.

We thank the reviewer for appreciating our work and for their valuable feedback. The primary concerns raised by the reviewer are: (i) incorporating experiments on industrial tasks to evaluate our approach, and (ii) performing additional ablation studies.

Regarding (i), we further emphasize the industrial applicability of our approach in real-world scenarios. To this end, we evaluate the performance of PEARL on large-scale recommendation tasks using the Stack Exchange Q&A Website Database. Specifically, we utilize the rel-stack dataset, a temporal and heterogeneous graph comprising approximately 38 million nodes. We consider two distinct industrial settings:

• User-Post-Comment Prediction: Predicting a list of existing posts that a user will comment on within the next two years.

• Post-Post-Related Prediction: Predicting a list of existing posts that users will link to a given post within the next two years. Notably, PEARL achieves state-of-the-art performance in this large-scale setting, further underscoring its scalability and effectiveness in practical applications.

In response to (ii), we have incorporated additional ablation studies into the revised manuscript. Specifically, we analyze the effects of varying the number of layers, model sizes, and the choice of K in the first layer. Furthermore, we provide runtime comparisons to deliver a comprehensive evaluation of the method's performance and computational efficiency.

We thank the reviewer for their valuable input. The main concerns of the reviewer can be summarized into the following points:

1. The reviewer argues that PEARL violates permution equivariance, since it uses unique identifiers to initialize the node attributes.
2. The reviewer claims that our expressivity results are not surprising, since one can basically do anything to increase expressivity beyond 1-WL, e.g., adding the number of connected components. The reviewer also argues that our work is not as expressive as SPE in Huang et al. ?
3. The reviewer is questioning the contribution of our work in terms of stability analysis, and wonders how it compares the stability properties of other methods.
4. The reviewer is asking for additional experiments with larger graphs to showcase the scalability of our approach.

Our short answers are as follows:

A1:
The reviewer's arguments may stem from a misunderstandings regarding a key component of our architecture. We kindly draw the reviewer's attention to the pooling function $\rho$ in Equations (5), (6), and (10), which might have been missed. The pooling function $\rho$ ensures that our model remains permutation equivariant, even while utilizing unique node identifiers. Given the reviewer's concern about this aspect, we hope our explanation clarifies the matter and encourages the reviewer to reassess their evaluation in light of this information.

A2:

The reviewer is correct that surpassing the limitations of 1-WL is conceptually straightforward. As mentioned, this can be achieved, for example, by simply adding the number of connected components as a feature. However, this observation highlights a critical point: to surpass 1-WL expressivity, most approaches rely on a non-neural algorithm to provide additional knowledge to the GNN, e.g., count the number of connected components and add them to the GNN as extra features.

In contrast, our work does not introduce any additional bias or external features. We enhance the expressivity of equivariant message-passing GNNs without relying on extra features or complex operations. This represents a significant departure from prior approaches, as we achieve this increased expressivity solely within the framework of a message-passing GNN architecture. This is important, since we can achieve increased expressivity while maintaining genericness, low computational complexity and stability.

In the revised manuscript we prove that PEARL is a universal approximator of basis invariant functions.

Theorem [Basis Universality]
Let $\mathcal{G}$ be a graph with GSO $\mathbf{S} = \mathbf{V} \mathbf{\Lambda} \mathbf{V}^T$, and $f$ be a continuous function such that $f(\mathbf{V}) = f(\mathbf{V} \mathbf{Q})$, $\mathbf{Q} \in \mathcal{O}\left({diag}\left(\mathbf{\Lambda}\right)\right)$, for any eigenvalues $\mathbf{\Lambda}$. Then there exist GNN $\Phi$ and a continuous pooling function $\rho$, such that:

The above Theorem adds novelty to the expressivity analysis of our work and shows that PEARL is as expressive as SPE in Huang et al. in the frequency domain.

A3:
The reviewers point is based on the fact that the stability properties of PEARL are directly inhereted by the stability of GNNs. While the stability properties are derived as corollaries of GNN stability, we do not see why this should be considered a limitation. Our contribution does not merely analyzes the stability an existing architecture but instead introduces a novel PE framework. Since our architecture is a GNN, it is unavoidable to inherit the stability properties from existing work. However, these foundational results reinforce the theoretical validity of our framework and enable us to extend and apply them in innovative ways. A direct comparison of the stability bounds of our approach with those of SPE further highlights the advantages of our framework. Specifically:

• The stability bound of SPE scales linearly with the graph size.
• In contrast, the stability bound of PEARL scales only with the square root of the graph size.

This significant difference provides PEARL with a substantial stability advantage over SPE, especially for larger graphs.

The paper is not well-integrated into the existing literature. It is unclear what advantages it offers compared to other methods that count cycles. Although related work is mentioned, the authors do not clearly differentiate their approach or highlight their novel contributions.

We thank the reviewer for their comment. Regarding methods that count cycles the contribution of our work is fourfold:

1. Performance: Our work appears to outperform methods than explicitly count cycles even in molecular datasets where it is well known that 5-node and 6-node cycles are the most important ones
2. Expressivity: PEARL is not limited to pre-defined motifs, such as cycles or cliques. It can compute other potentially important substructures, such as dense subgraphs, chordal cycles, or combinations of motifs, that explicit counting methods might omit simply because they are not pre-specified. Notably, the number of possible motifs in a graph grows combinatorially, highlighting the flexibility and breadth of PEARL.
3. Complexity: Explicitly counting high-order motifs, especially at the node level, can be computationally expensive. PEARL bypasses this challenge by learning to capture these structures implicitly, making it more scalable to large and complex graphs.
4. Bias: Predetermining which motifs to count introduces bias into the model. For example, molecular graphs often benefit from detecting cycles, while social networks emphasize cliques or dense subgraphs. PEARL is task-agnostic and allows the data to guide which motifs are most relevant, adapting to the specific requirements of the application. On the flip side, when the training data have small sizes, learning can benefit by specific biases that structural PEs admit.

We add this discussion and clarify our contribution in the revised manuscript.

The theoretical results often seem incorrect or lack necessary details.

As we explain in our upcoming answers none of our results are incorrect and there might be a misunderstanding from the reviewer's side. We kindly ask the reviewer to re-assess their evaluation which we believe is due to a misunderstanding. We thank the reviewer for pinpointing some details which could be useful to be present in the theorems. We have added them in the revised manuscript

Additionally, many of the results appear to be summaries of theoretical findings from related works.

While the stability properties and some expressivity results are derived as corollaries of related work, we do not see why this should be considered a limitation. Our contribution does not merely analyzes the stability or expressivity of an existing architecture but instead introduces a novel PE framework. Since our architecture is a GNN, it is unavoidable to inherit some properties from existing work. However, these foundational results reinforce the theoretical validity of our framework and enable us to extend and apply them in innovative ways.

We would also like to highlight two key theoretical contributions of our work: our sample complexity analysis, which was omitted from this discussion, and the newly included Basis Universality Theorem, which has been added to the revised version.

However, it is unclear whether this approach improves or decreases expressivity or leads to better stability or generalization bounds.

Our new expressivity results demonstrate that PEARL is at least as expressive as SPE. Furthermore, PEARL exhibits a lower stability bound that scales sublinearly with graph size, in contrast to the linear scaling of SPE.

This significant difference in stability bounds suggests that PEARL might have better generalization properties compared to SPE, making it a more robust and scalable framework for a variety of graph-based tasks.

Notably, the out-of-distribution (OOD) generalization in the experiments appears to be better for the SPE positional encodings. However, it is not clear why since SPEs are also stable.

We believe the reviewer is referring to the DrugOOD experiments, which explicitly assess out-of-distribution (OOD) generalization. In the revised manuscript, we have included experiments with B-PEARL that demonstrate a significant advantage of B-PEARL over SPE in terms of size generalization. This improvement is likely due to the linear scaling of SPE with graph size, compared to the square-root scaling of PEARL, which provides better size generalization capabilities. The results can be found below:

Table: AUROC Results (5 Random Seeds) on DrugOOD

Dear Authors,

Thank you for addressing my questions. The experimental results presented in your manuscript are promising, and I appreciate that your approach is distinct from prior work, offering advantages such as scalability and potentially greater stability in terms of generalization. By introducing less complexity compared to methods like SPE, your method shows practical utility.

However, there are significant issues with the theoretical formulations, proofs, and the overall scope of the work. First, the claim that your method is permutation equivariant because it takes the empirical mean of random variables (all with the same expectation) is incorrect. Augmenting graphs with random node features is a known technique that inherently breaks permutation equivariance but achieves universality. This phenomenon is not surprising and is analogous to applying an MLP (or any universal architecture) to the flattened adjacency matrix. While this achieves universality, allowing the method to separate all graphs, it sacrifices permutation equivariance in the process.

Section 3 and Proposition 3.1 also present significant issues. Many notations are undefined, making the section difficult to understand. For example, in Proposition 3.1, you use $\mathrm{MLP}$ in the formulation of the result, but the proof indicates that $\mathrm{MLP}$ corresponds to the update function $g^{(l)}$ of a layer. This interpretation is problematic due to dimensional inconsistencies. According to your manuscript, $\mathrm{MLP}$ operates on each node independently to maintain permutation equivariance, mapping from $\mathbb{R}^{F_l}$ to $\mathbb{R}^{F_{l+1}}$. Applying $\mathrm{MLP}$ to $\mathbf{V} \in \mathbb{R}^{n \times n}$ is therefore invalid. The proof, as written, does not appear correct.

Similar issues arise in Theorem 3.1. For example, Equation 29 claims that $X^{(K)}[:, :, f] \in \mathbb{R}^{n \times n}$, which is clearly incorrect. These errors undermine the credibility of the theoretical results and need to be addressed comprehensively.

Beyond these specific issues, the manuscript overall suffers from a lack of rigor in its use of notation and definitions, which makes the theoretical results difficult to understand. Every notation must be clearly defined, and all results and proofs need thorough verification to ensure correctness and clarity.

While the experimental results and scalability of your approach are promising, the theoretical contributions are incremental and currently marred by significant issues in rigor and correctness. This is not inherently problematic for publication at ICLR, provided these concerns are addressed. However, I strongly recommend another round of revisions where the authors carefully verify all theoretical results and proofs and improve the overall clarity of the manuscript.

For these reasons, I maintain my recommendation for rejection at this stage, with the hope that the authors will submit an improved and rigorously verified version in the future.

Similar issues arise in Theorem 3.1. For example, Equation 29 claims that $X^K [:,:,f]∈R^{N×N}$, which is clearly incorrect. These errors undermine the credibility of the theoretical results and need to be addressed comprehensively.

We thank the reviewer for their comment. To clarify, there is no inaccuracy here, only a slight abuse of notation. We have updated $X^K [:,:,f]$ to $X^K [:,f,:]$ and have provided additional details for clarity. The text now reads:

Since we independently feed $\mathbf{e}_1,\dots, \mathbf{e}_N$ to the PEARL architecture, we will have $N$ output samples for each output feature, i.e., $N$ samples for $\mathbf{X}^{(K)}[:,f]$. We will represent the $m-$th sample as $\mathbf{X}^{(K)}[:,f,m]$ and for the $f-$th output feature will have the following samples:

$\mathbf{X}^{(K)}[:,f,:]=[\mathbf{V_{\mu_f}}\mathbf{V_{\mu_f}}^T\mathbf{e}^1,\dots, \mathbf{V_{\mu_f}}\mathbf{V_{\mu_f}}^T\mathbf{e}^N]=\mathbf{V_{\mu_f}}\mathbf{V_{\mu_f}}^T$

Beyond these specific issues, the manuscript overall suffers from a lack of rigor in its use of notation and definitions, which makes the theoretical results difficult to understand. Every notation must be clearly defined, and all results and proofs need thorough verification to ensure correctness and clarity.

We appreciate the reviewer’s feedback and would greatly value more specific suggestions or detailed comments to help us improve the quality of our paper.

Section 3 and Proposition 3.1 also present significant issues. Many notations are undefined, making the section difficult to understand. For example, in Proposition 3.1, you use MLP in the formulation of the result, but the proof indicates that MLP corresponds to the update function g(l) of a layer. This interpretation is problematic due to dimensional inconsistencies. According to your manuscript, MLP operates on each node independently to maintain permutation equivariance, mapping from $\mathbb{R}^{F_l}$ to $\mathbb{R}^{F_{l+1}}$. Applying MLP to $\mathbf{V}\in\mathbb{R}^{n×n}$ is therefore invalid. The proof, as written, does not appear correct.

This is an interesting point raised by the reviewer. A GNN layer is a function $g\circ f : \left(\mathcal{G},\mathbb{R}^{F_{l-1}}\right)\rightarrow \mathbb{R}^{F_l}$, where $\mathcal{G}$ represents a graph with $N$ nodes ($N$ can be arbitrary). Let $f$ be one of the functions in Eq. (2) and $g$ be a multi-layer perceptron. According to Eq. (3) the degrees of freedom in the first perceptron layer are $K F_l F_{l-1}$.

According to Proposition 3.1, the update for node $v$, is still a mapping $g\circ f : \left(\mathcal{G},\mathbb{R}^{F_{l-1}}\right)\rightarrow \mathbb{R}^{F_l}$ and $g\circ f$ can be interpreted as a nonlinear function of eigenvectors

$\mathbf{x}_v^{(l)} =`MLP`\left(\mathbf{v}^{(v)}\right)=`MLP`^{(-1)}\left(\sigma\left(\mathbf{W}^T\mathbf{v}^{(v)}\right)\right),~\mathbf{v}^{(v)}=\mathbf{V}[v,:]^T$

The degrees of freedom in the first MLP layer are $K F_l F_{l-1}$, since $\mathbf{W}[n,f]$ are not independent but they are themselves functions of node attributes and graph, i.e., $\mathbf{W}[n,f] : \left(\mathcal{G},\mathbb{R}^{F_{l-1}}\right)\rightarrow \mathbb{R}^{1}$. So the claim of Proposition 3.1 is not that a GNN layer just takes $\mathbf{v}^{(v)}$ as an input and applies a $\mathbb{R}^{N}\rightarrow \mathbb{R}^{F_l}$ mapping to it. Instead the claim is that the $\left(\mathcal{G},\mathbb{R}^{F_{l-1}}\right)\rightarrow \mathbb{R}^{F_l}$ GNN layer mapping can be viewed as a $\left(\mathbf{V},\mathbf{\Lambda},\mathbb{R}^{F_{l-1}}\right)\rightarrow \mathbb{R}^{F_l}$ mapping and the whole operation can be interpreted as a nonlinear mapping of the $v-$th row of the eigenvector matrix $\mathbf{V}[v,:]^T$, but the weights of this mapping are dependent with $K F_l F_{l-1}$ degrees of freedom.

We updated Proposition 3.1 and added additional discussion that now read:

Proposition: GNNs as Nonlinear Functions of Eigenvectors

A GNN defined in Eq. (1) with $f^{(l)}$ being one of the functions in Eq. (2) and $g^{(l)}$ being a multi-layer perceptron, operates as a nonlinear function of the GSO eigenvectors, i.e., $\mathbf{x}_v^{(l)} = `MLP`\left(\mathbf{v}^{(v)}\right),~\mathbf{v}^{(v)}=\mathbf{V}[v,:]^T$.

The trainable parameters of the first MLP layer are not independent but depend on the eigenvalues $\{\lambda_n\}_{n=1}^N$, eigenvectors $\mathbf{v}_n$ $n=1,\dots,N$ of the GSO, and the node features $\mathbf{X}$ of the graph:

$\mathbf{x}_v^{(l)} = `MLP`\left(\mathbf{v}^{(v)}\right) = `MLP`^{(-1)}\left(\sigma\left(\mathbf{W}^T\mathbf{v}^{(v)}\right)\right)$

$\mathbf{W}[n, f] = \sum_{i=1}^{F_{l-1}}\sum_{k=0}^{K-1}\lambda_n^k\mathbf{H}_k^{(l)}[i,f]\langle \mathbf{\alpha}_n, \mathbf{X}^{(l-1)}[:,i]\rangle,$

where $\mathbf{\alpha}_n = \mathbf{v}_n$ when the GSO is symmetric, and $\mathbf{\alpha}_n = \mathbf{V}^{-1}[n,:]$ when it is not. $MLP^{(-1)}$ denotes all the layers of the $`MLP`$ except the first layer.

The proof is provided in Appendix A. According to Proposition 1, the update for node $v$, which is a function $g \circ f : \mathbb{R}^{F_{l-1}} \rightarrow \mathbb{R}^{F_l}$, can be viewed as a function $`MLP` : \mathbb{R}^N \rightarrow \mathbb{R}^{F_l}$ operating on $\mathbf{V}[v,:]$. The degrees of freedom in the first layer of $`MLP`$ are $K F_l F_{l-1}$ (as described in Eq. (3)), and not $F_l N$, which would have been the case for independent weights $\mathbf{W}$.

The proof is provided in Appendix B. \blue{According to Proposition 3.1, the update for node $v$, defined by the function $g \circ f : \left(\mathcal{G},\mathbb{R}^{F_{l-1}}\right) \rightarrow \mathbb{R}^{F_l}$, can be interpreted as a nonlinear mapping $`MLP`$ applied to $\mathbf{V}[v, :]$, but the weights of the first layer of this mapping are also mappings, i.e., $\mathbf{W}[n,f] : \left(\mathcal{G},\mathbb{R}^{F_{l-1}}\right)\rightarrow \mathbb{R}^{1}$. The degrees of freedom in the first layer of $`MLP`$ are $K F_l F_{l-1}$ (as described in Eq. (5), rather than $F_l N$, which would be the case for independent weights $\mathbf{W}$. Furthermore, the dot product $\langle \mathbf{\alpha}_n, \mathbf{X}^{(l-1)}[:, i] \rangle$ depends on the eigenvectors and, for the update of node $v$, it only involves the components $\mathbf{X}^{(l-1)}[u, i],~u\in\mathcal{N}_v$.

First, the claim that your method is permutation equivariant because it takes the empirical mean of random variables (all with the same expectation) is incorrect.

In PEARL, we draw $M$ samples of a random vector $\mathbf{q}$ to initialize the node attributes. Since this random vector is processed using an equivariant GNN $\Phi(\mathcal{G}, \cdot)$, the resulting distribution of $\Phi(\mathcal{G}, \mathbf{q})$ is permutation equivariant. Consequently, the expected value $\mathbb{E}\left[\Phi(\mathcal{G}, \mathbf{q})\right]$ is also permutation equivariant.

According to the law of large numbers and concentration inequalities, the empirical mean approximates the true mean with arbitrary accuracy, where the level of accuracy depends on the number of samples. R-PEARL computes the empirical mean $\hat{\mathbb{E}}\left[\Phi(\mathcal{G}, \mathbf{q})\right]$, enabling it to approximate $\mathbb{E}\left[\Phi(\mathcal{G}, \mathbf{q})\right]$ with high precision. In essence, R-PEARL achieves equivariance with increasing accuracy as the number of samples $M$ grows.

The equivariance of R-PEARL depends on the number of samples $M$, with Theorem 4.3 providing a bound on the number required to achieve a specified accuracy. For very small sample sizes, R-PEARL is not equivariant; however, in practice, a modest number of samples (50–200) is sufficient to render it effectively equivariant. This is evident in our experiments. In Tables 1 and 2, the "GIN + rand id" model corresponds to R-PEARL with a single sample, which is not equivariant. We observe that "GIN + rand id" performs significantly worse—more than four times worse in logP prediction for molecular graphs—compared to R-PEARL.

We have added this discussion in the revised manuscript

To further validate this empirically, we measured the effect of randomness on the output of R-PEARL for graphs in the ZINC dataset. Specifically, we conducted five independent runs of R-PEARL, each with 100 samples and different random seeds. To evaluate consistency, we calculated the relative difference between the PEs generated for each node across these runs, defined as

$d_{ij}=\frac{|\mathbf{P}[\text{run}_i]-\mathbf{P}[\text{run}_j]|}{|\mathbf{P}[\text{run}_i]|}$.

Our findings revealed that $d_{ij}$ was consistently on the order of $10^{-2}$, while the difference in PEs between different nodes within the same run was on the order of $10^{-1}$.

These results demonstrate that the variability introduced by randomness is negligible compared to the inherent differences in node features, supporting our claim that R-PEARL is practically equivariant in real-world applications.

Augmenting graphs with random node features is a known technique that inherently breaks permutation equivariance but achieves universality. This phenomenon is not surprising and is analogous to applying an MLP (or any universal architecture) to the flattened adjacency matrix. While this achieves universality, allowing the method to separate all graphs, it sacrifices permutation equivariance in the process.

We completely agree with the reviewer. However, this is not how PEARL operates or how we establish universality in our work. The proof of the universality theorem does not involve randomness or rely on random samples. Instead, the initial node encodings are constructed using standard basis vectors. This approach ensures that universality is achieved deterministically while maintaining equivariance.

We thank the reviewer for their prompt response and the opportunity to engage in a constructive and meaningful discussion. We greatly appreciate the reviewer’s recognition of the experimental results and the novelty of our approach, as well as their acknowledgment of the scalability, stability, and practical utility of our method.

The reviewer raised three primary concerns regarding our work:

1. The permutation equivariance of our approach.
2. The ability to achieve both universality and equivariance simultaneously.
3. The clarity of Theorem 3.1 and Proposition 3.2.

We provide a brief summary of our responses below, followed by more detailed explanations.

Summary of Responses (TL;DR)

A1: The general PEARL framework is introduced in Section 3.2, and we propose two practical implementations:

• R-PEARL (Section 4), which uses $M$ random samples to initialize node attributes.
• B-PEARL (Section 5), which uses the $N$ standard basis vectors to initialize node attributes.

B-PEARL is deterministically equivariant and universal. R-PEARL, as an empirical expectation, can approximate the true expectation with arbitrary accuracy. Theorem 4.3 provides a bound on the number of samples required as a function of accuracy. While the expectation itself is equivariant, R-PEARL is approximately equivariant with increasing accuracy as the number of samples grows. For a very small number of samples, R-PEARL is not equivariant; however, in practice, sufficient samples (20-200 for any graph size) render it effectively equivariant.

A2: The proof of the universality theorem does not rely on randomness or random samples. Instead, the initial node encodings use standard basis vectors. Thus, universality is achieved deterministically, while preserving equivariance.

A3: We have revised the manuscript to enhance the clarity and presentation of Proposition 3.2 and the proof of Theorem 3.1.

We look forward to further feedback from the reviewer and hope our clarifications address their concerns.

I would like to make a quick remark: Any analytic function f:R→R of individual eigenvalues is inherently a permutation equivariant Lipschitz continuous function $f~:R^n→R^n$ over the entire spectrum of eigenvalues by setting $f(x1,…,xn):=(f(x1),…,f(xn))$. Consequently, this suggests that your formulation is less general than the SPE approach proposed by Huang et al. To see that SPE is strictly more general: The permutation equivariant function $(x1,x2)\rightarrow(x1+x2,x1+x2)$ can not be realized by any function acting separately on each entry.

We agree with the reviewer that an analytic function $a^{(1)}:R→R$ of individual eigenvalues is less general than a function $a^{(2)}:R^n→R^n$ jointly operating on the whole spectrum. However, this does nor necessarily mean that

$f_1= \rho_1\circ a^{(1)}=\rho_1\left(\left[\mathbf{V}\text{diag}\left(\alpha^{(1)}_1\left(\mathbf{\Lambda}\right)\right)\mathbf{V}^T,\dots,\mathbf{V}\text{diag}\left(\alpha^{(1)}_F\left(\mathbf{\Lambda}\right)\right)\mathbf{V}^T\right]\right),$

is less general than

$f_2= \rho_2\circ a^{(2)}=\rho_1\left(\left[\mathbf{V}\text{diag}\left(\alpha_1^{(2)}\left(\mathbf{\Lambda}\right)\right)\mathbf{V}^T,\dots,\mathbf{V}\text{diag}\left(\alpha_F^{(2)}\left(\mathbf{\Lambda}\right)\right)\mathbf{V}^T\right]\right)$.

The interesting question is how general are $f_1= \rho_1\circ a^{(1)}$ and $f_2= \rho_2\circ a^{(2)}$. $f_1$ and $f_2$ are functions operating on a basis $\mathbf{V}$ and for $f_1$ and $f_2$ to be universal, what matters is how distinctive $\alpha^{(1)}$ or $\alpha^{(2)}$ are, not how expressive. Having said that we can also view $f_1$ and $f_2$ as invariant functions at the graph level and in that case we would be interested in testing whether $f_1$ and $f_2$ are univarsal functions of eigenvalues. To that end we prove that PEARL or SPE with analytical functions of individual eigenvalues $a_i^{(1)}:R→R$, are universal functions of eigenvalues.

The proof can be found in Appendix D of the revised manuscript.

Dear Reviewer J67b,

Thank you for acknowledging that we have addressed your other concerns. Regarding your final concern, we would like to point out a key misunderstanding on your comment that seems to be causing confusion about our work.

A function can have non permutation equivariant inputs, yet produce a permutation equivariant output. For instance, SPE (Huang et al.), SignNet (Lim et al.), and BasisNet (Lim et al.) take as inputs the Laplacian eigenvectors, which are not permutation equivariant due to sign and basis ambiguities, but transform them into permutation-equivariant node features. Our approach follows a similar principle.

In the case of B-PEARL, the inputs are standard basis vectors, and the PEARL mechanism subsequently transforms them into equivariant node features. This is distinct from merely augmenting the output with standard basis vectors, which would not be permutation-equivariant. In simple words, the average of standard basis vectors is permutation-equivariant, as is the average of GNN outputs when the nodes are initialized with standard basis vectors.

Furthermore, our proposed PEARL—like SPE and BasisNet—is not a universal approximator of arbitrary graph functions. Rather, it is a universal approximator for any functions that satisfy $f(\mathbf{V})=f(\mathbf{VQ})$, i.e., basis-equivariant or invariant functions, as explained in Theorem 3.1 and reiterated in our previous responses. Please see Appendix C in the revised manuscript that proves how PEAL jointly achieves basis universality and equivariance.

We hope this clarification resolves your last concern and look forward to your response.

in line 60 of introduction, the paper argues '' stability is particularly crucial for out-of-distribution generalization'', which is one of the main motivations for this work. However, such a benefit of size generalization is not provided with enough evidence in this work. Actually in Table 3, the OOD-size performance is not improved by stable methods like SPE and the proposed R-PEARL.

The reviewer is raising an interesting point. Stability is indeed important in out-of-distribution (OOD) generalization on Scaffold and size.and the benefit is clear in Table 3, especially when it . We include Table 3 with additional experiments with B-PEARL to facilitate the discussion.

The reviewer raises an very interesting point. The importance of stability for out-of-distribution (OOD) generalization is theoretically established, and the benefit of stable methods is shown in Table 3, particularly on Scaffold OOD and Size OOD. To facilitate this discussion, we have included Table 3, with additional experiments with B-PEARL that have been added in the revised manuscript.

Table: AUROC Results (5 Random Seeds) on DrugOOD

The least stable methods in Table 3 are SignNet and BasisNet. We observe that B-PEARL improves the OOD-Test AUC by 9.5% compared to BasisNet and 3.8% compared to SignNet in size OOD generalization. Similarly, B-PEARL achieves a 4.6% improvement in OOD-Test AUC over both SignNet and BasisNet in Scaffold OOD generalization.

A comparable trend is observed when comparing the stable SPE with SignNet and BasisNet. Furthermore, B-PEARL demonstrates an advantage over SPE in size generalization. This improvement is likely attributed to the linear scaling of SPE's stability bound with graph size, compared to the square-root scaling of PEARL's stability bound, which enhances its size generalization capabilities.

A key assumption is missing in proposition 3.1: GSO S is required to be symmetric if we want to use the decomposition in line 105. So the random walk matrix in Eq(2) does not satisfy this condition.

We thank the reviewer for catching this. We have adjusted Proposition 3.1 to include non-symmetric GSO. Proposition 3.1 now reads:

Proposition: GNNs are Nonlinear Functions of Eigenvectors

A GNN defined in Eq. (1) with $f^{(l)}$ being one of the functions in Eq. (2) and $g^{(l)}$ being an MLP, is a nonlinear function of the GSO eigenvectors, i.e., $\mathbf{X}^{(l)} = `MLP`\left(\mathbf{V}\right)$. The trainable parameters of the first MLP layer are not independent but depend on the eigenvalues {$\lambda_n$}$_{n=1}^N$ and eigenvectors $\mathbf{v_n}$, $n=1,\dots,N$ of the GSO, as well as the initial node features $\mathbf{X}$ of the graph:

$\mathbf{X}^{(l)} = `MLP`\left(\mathbf{V}\right) = `MLP`^{(-1)}\left(\sigma\left(\mathbf{V} \mathbf{W}\right)\right)$,

$\mathbf{W}\left[n, f\right] = \sum_{i=1}^{F_{l-1}}\sum_{k=0}^{K-1}\lambda_n^k\mathbf{H}_k^{(l)}[i,f]\langle \mathbf{\alpha}_n, \mathbf{X}^{(l-1)}\left[:,i\right]\rangle$,

where $\mathbf{\alpha}_n = \mathbf{v}_n$ when the GSO is symmetric, and $\mathbf{\alpha}_n = \mathbf{V}^{-1}[n,:]$ when it is not. $`MLP`^{(-1)}$ denotes all the layers of the $`MLP`$ except the first layer.

in line 463, it might be a little sudden to claim ''SPE can be efficiently implemented by B-PEARL with lower computational and memory complexity'': the argument seems coming from the comparison of numbers in Table 2. Although the numbers of SPE and the proposed methods are close, it would be better to conduct more careful analysis to provide such a ''subset'' or ''equivalence'' relationship between the methods, or refer to remark 5.1 for theoretical insights.

We thank the reviewer for their comment. We agree and have now removed this comment from the revised manuscript.

We sincerely thank the reviewer for their thoughtful feedback and for recognizing the contributions of our work. The reviewer raises two primary concerns: (i) the out-of-distribution (OOD) generalization performance of our method compared to less stable methods, and (ii) the impact of the number of layers on performance.

To address (i), we conducted additional experiments with B-PEARL and compared its OOD-Test AUC to that of less stable methods such as SignNet and BasisNet. The results show that B-PEARL improves OOD-Test AUC by 9.5% over BasisNet and 3.8% over SignNet in size OOD generalization. Similarly, B-PEARL achieves a 4.6% improvement in OOD-Test AUC over both SignNet and BasisNet in Scaffold OOD generalization.

To address (ii), we performed an ablation study by varying the number of layers in B-PEARL. Our findings indicate that while B-PEARL is robust to changes in the number of layers, and its performance benefits from the use of multiple layers compared to fewer layers.

Basis Universality of PEARL

To further strengthen the theoretical analysis of our approach we prove, in the revised manuscript, that PEARL is a universal approximator of basis invariant functions. The details are presented below.

Theorem [Basis Universality]
Let $\mathcal{G}$ be a graph with GSO $\mathbf{S} = \mathbf{V} \mathbf{\Lambda} \mathbf{V}^T$, and $f$ be a continuous function such that $f(\mathbf{V}) = f(\mathbf{V} \mathbf{Q})$, $\mathbf{Q} \in \mathcal{O}\left({diag}\left(\mathbf{\Lambda}\right)\right)$, for any eigenvalues $\mathbf{\Lambda}$. Then there exist GNN $\Phi$ and a continuous pooling function $\rho$, such that:

Large-Scale Prediction on RelBench

To further empasize the scalability and effectiveness of our approach we test the performance of the proposed PEARL on large-scale link prediction for Stack Exchange Q&A Website Database. To that end we utilize the rel-stack dataset for the relational deep learning benchmak (RelBench) [2]. Rel-stack is a temporal and heterogeneous graph with approximately 38 million nodes. We consider two different tasks; i) user-post-comment, where we predict a list of existing posts that a user will comment in the next two years, and ii) post-post-related, where we predict a list of existing posts that users will link a given post to in the next two years. The results for the two tasks can be found in the following table.

Table: Validation and Test Mean Average Precision (MAP) on Large-Scale RelBench Recommendation Tasks

PEARL achieves an 11% improvement over the backbone model with no PE on the user-post-comment task and a 2% improvement on the post-post-related* task.

The backbone model for this RelBench task a heterogeneous identity-aware GNN and all methods are trained with batch size $20$. From the above table we observe that PEARL has an 11% benefit over the identity aware backbone model with no PE on the user-post-comment task and a 2% benefit on the post-post-related task. PEARL works similarly to SignNet-8S but with lower complexity and, and similarly to SignNet-8L on the user-post-comment task, but 5% better than SignNet-8L on the post-post-related task. SPE could not be included in the comparisons due to it's cubic computational complexity and quadratic memory complexity.

[2] Robinson, J., Ranjan, R., Hu, W., Huang, K., Han, J., Dobles, A., Fey, M., Lenssen, J.E., Yuan, Y., Zhang, Z. and He, X., RelBench: A Benchmark for Deep Learning on Relational Databases. In The Thirty-eight Conference on Neural Information Processing Systems Datasets and Benchmarks Track.