Learning Efficient Positional Encodings with Graph Neural Networks

Authors: Charilaos Kanatsoulis, Evelyn Choi, Stefanie Jegelka, Jure Leskovec, Alejandro Ribeiro
Primary area: learning on graphs and other geometries & topologies
Keywords: positional encodings, graph neural networks, graph transformers

Abstract:
Positional encodings (PEs) are essential for effective graph representation learning because they provide position awareness in inherently position-agnostic transformer architectures and increase the expressive capacity of Graph Neural Networks (GNNs). However, designing powerful and efficient PEs for graphs poses significant challenges due to the absence of canonical node ordering and the scale of the graph. In this work, we identify four key properties that graph PEs should satisfy: stability, expressive power, scalability, and genericness. We find that existing eigenvector-based PE methods often fall short of jointly satisfying these criteria. To address this gap, we introduce PEARL, a novel framework of learnable PEs for graphs. Our primary insight is that message-passing GNNs function as nonlinear mappings of eigenvectors, enabling the design of GNN architectures for generating powerful and efficient PEs. A crucial challenge lies in initializing node features in a manner that is both expressive and permutation equivariant. We tackle this by initializing GNNs with random node inputs or standard basis vectors, thereby unlocking the expressive power of message-passing operations, while employing statistical pooling functions to maintain permutation equivariance. Our analysis demonstrates that PEARL approximates equivariant functions of eigenvectors with linear complexity, while rigorously establishing its stability and high expressive power. Experimental evaluations show that PEARL outperforms lightweight versions of eigenvector-based PEs and achieves comparable performance to full eigenvector-based PEs, but with one or two orders of magnitude lower complexity. Our code is available at https://github.com/ehejin/Pearl-PE.

Decision: accept (poster)
Reviewer scores: 3, 6, 6, 3, 6

Reviews and discussion:
<thread>
creation date:
1730537177505

thread_type:
official_review

<thread_object>
creator: reviewer_8uld

<content>
summary:
The paper deals with learning effective positional encodings for graph structures to be used in conjunction with graph neural networks. Previously, eigenvectors and random features  have been used for such posiitonal encodings. In this paper, the authors first observe that the message passing GNNs are akin to non-linear functions of eighenvectors and therefore can be used to learn positional encodings which can function similarly to eigenvector-based positional encodings. Following this observation, they propose PEARL, a GNN based approach which takes in random feature inputs on the graph (without accompanying node-features) and learns to output encodings which can be interpreted as positional encodings. To preserve permutation invariance upto the expectation, they use multiple IID samples and aggregate with equivarient sample statistics. The authors show that such a approach preserves  stability, improves expressive power, scalability, and genericness. Experiments are presented to validate the approach.

strengths:
1. The paper addresses an important problem of learning positional encodings on graphs
1. The approach of learning PEs as outputs of GNN with random feature inputs on the graph is well-motivated with the observation discussed that GNNs are non-linear functions of eigenvectors of graph shift operators.
1. The paper is well-written and presentation is good.

weaknesses:
1. Essentially, the outputs of GNNs on random input features are taken as positional encodings. However, there are no loss functions to bias learning towards such functions. While it is clear the random inputs along with GNN message passing, can encode the relative positional information and the supporting evidence that GNNs compute non-linear maps of eigenvectors of adjacency/laplacians, further regularizing loss functions may be able to make the learning encodings better. One example is enforcing the encodings of each node to be orthogonal to other encodings.
1. It is not clear to me why eigenvectors need to be used in place of random features for smaller sized graphs. Empirical results to show the difference between eigenvector inputs and random inputs for smaller sized graphs would be beneficial.
1. Important works are missing in related work and comparison experiments. In experiments, Random GNN [1] and PF-GNN [2] are not compared, which are highly related to using randomization to improve expressive power and in a way, compute positional encodings. 
1. The paper claims that the proposed approach is more expressive. Then empirical results showing it is needed. For example, identifying graphs  not identifiable by GNNs would be useful. A comparison with random GNN[1] and PFGNN[2] would be beneficial in this respect.


### References:

\[1\] $~$  Sato, Ryoma, Makoto Yamada, and Hisashi Kashima. "Random features strengthen graph neural networks." Proceedings of the 2021 SIAM international conference on data mining (SDM). Society for Industrial and Applied Mathematics, 2021.

\[2\] $~$ Dupty, Mohammed Haroon, Yanfei Dong, and Wee Sun Lee. "PF-GNN: Differentiable particle filtering based approximation of universal graph representations." arXiv preprint arXiv:2401.17752 (2024).

questions:
Please see weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730545811242

thread_type:
official_review

<thread_object>
creator: reviewer_kvqz

<content>
summary:
This work proposes PEARL, using the output of Message Passing Neural Network (MPNN) with noise/basis node feature as input for PE. PEARL's stability, sample complexity, and expressivity are further analysis. Experiments illustrates that PEARL achieves good performance in graph tasks.

strengths:
1. Good performance on ZINC dataset.
2. Detailed analysis of R-PEARL.

weaknesses:
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.
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 eigenvectors. Therefore, the justification for choosing MPNNs as eigenvalue function over other graph models is not evident.
3. While the expectation of R-PEARL is equivariant, the actual R-PEARL method is not, due to the involvement of noise.
4. 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 $\beta$. Considering $\beta$ as a constant is problematic because large social networks often contain nodes with high degrees, which would require more samples for accurate representation.
5. Most theoretical results (Theorem 4.3, Proposition 4.1, 4.2, 4.3) are direct corollories of previous conclusions.
6. The experimental section is limited to four datasets. To strengthen the validity of the results, additional datasets should be included as in [1].
7. 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].


[1] Xiaoxin He, Bryan Hooi, Thomas Laurent, Adam Perold, Yann LeCun, Xavier Bresson: A Generalization of ViT/MLP-Mixer to Graphs. ICML 2023
[2] Ladislav Rampásek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, Dominique Beaini: Recipe for a General, Powerful, Scalable Graph Transformer. NeurIPS 2022

questions:
Please refer to Weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730611959124

thread_type:
official_review

<thread_object>
creator: reviewer_ev2c

<content>
summary:
Beforehand, I want to say that I am not familiar with this topic.

The paper introduces PEARL, a novel framework for learnable positional encodings (PEs) in graph representation learning. It addresses the limitations of eigenvector-based methods by leveraging message-passing Graph Neural Networks (GNNs) to compute efficient and expressive PEs. The authors propose initializing node attributes with random or basis vectors to ensure both expressiveness and permutation equivariance. The framework is validated through comprehensive theoretical analysis and empirical evaluation, showing significant improvements in scalability and performance compared to existing methods.

strengths:
1. Innovative Approach: The use of message-passing GNNs as nonlinear mappings of eigenvectors is a novel contribution, enabling efficient computation of PEs.
2. Comprehensive Analysis: The paper rigorously proves the stability, expressiveness, and computational efficiency of PEARL.
3. Empirical Validation: Experimental results demonstrate that PEARL outperforms traditional methods on various graph classification and regression tasks while maintaining lower computational complexity.
4. Scalability: The framework is designed to handle large graphs efficiently, addressing a critical limitation of eigenvector-based methods.
5. Theoretical Contributions: The analysis of sample complexity and stability provides a solid foundation for the proposed approach.

weaknesses:
1. Limited Discussion on Practical Implications: While the theoretical and empirical results are robust, the paper could benefit from a deeper discussion on the practical applications of PEARL in real-world scenarios.
2. Complexity of Understanding: The mathematical depth and complexity might pose a barrier to readers unfamiliar with the intricacies of GNNs and spectral graph theory.
3. Comparative Baselines: Although the paper includes several baselines, additional comparisons with more recent or diverse methods could strengthen the empirical validation.
4. Ablation Studies: While ablation studies are presented, further exploration of the impact of different initialization strategies and pooling functions on performance could provide more insights.

questions:
The paper introduces PEARL as a scalable and efficient alternative to eigenvector-based positional encodings. While the theoretical advantages are well articulated, can the authors provide more detailed insights or case studies on how PEARL performs in real-world applications or large-scale industrial settings? Specifically, what types of graphs or domains would benefit the most from the proposed method, and are there any observed limitations in practical deployments?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730672570211

thread_type:
official_review

<thread_object>
creator: reviewer_bgao

<content>
summary:
This work aims to propose a new framework for graph positional encoding that is expressive, scalable, stable and generalizable. The proposed framework generates positional encoding as aggregated outputs of GNNs with random or basis inputs, which is then fed into downstream GNNs for performance evaluation. The proposed framework is accompanied with theoretical arguments and empirical verification on graph regression and classification tasks.

strengths:
1. Good motivations: the topic of graph positional encoding is a significant direction, which requires sufficiency, efficiency and easiness for generalization.
2. The proposed method is easy for plug-in: it proposes positional encodings as aggregation of GNNs' outputs with random/basis inputs, which are quite simple with standard implementation.
3. The empirical performance of the proposed method is comparable with SPE methods in Table 2, but it is much more efficient than SPE in Table 1 for larger graphs.
4. Different choices of input with random or basis are good with a consideration of different scales of problems, with the sample size of random inputs examined in Figure 2.

weaknesses:
Major:
1. 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.
2. 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.
3. 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.
4. in line 397, a 9-layer MPNN is used for experiments, which is relatively deep in the practice of GNNs. Could you please reveal how depth will impact the empirical results? Meanwhile, such a deep method with random inputs is quite similar to power iterations for eigenvalues, so some discussion between these might be helpful.

Minor: 
1. in line 133-134, the definition of $F_{l-1}$ is not clearly stated, and it should be $F_l$ for $X^{(l)}$.
2. in line 293, it seems to be ''a consequence of Prop 4.1'' instead of 4.2

questions:
Please see the above major concerns.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730720879449

thread_type:
official_review

<thread_object>
creator: reviewer_j67b

<content>
summary:
The authors propose learning positional encodings by using spectral graph filters in the initial layers. They argue that this approach corresponds to learning non-linear functions of the eigenvectors. The spectral GNN is applied to the input graph without using node features; instead, random features are added to the nodes. Although this breaks permutation equivariance, the authors argue that using a sufficient number of samples and specific aggregation functions preserves permutation equivariance. The authors argue that this method is expressive, scalable and stable.

strengths:
- Most other methods based on eigenvectors require computing the eigenbasis, leading to problems on large graphs. In contrast, the authors argue for a worst-case $N^2$ forward complexity without high preprocessing-complexity.
- The experimental results appear promising.

weaknesses:
- 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.
- The theoretical results often seem incorrect or lack necessary details. Additionally, many of the results appear to be summaries of theoretical findings from related works. Specific examples are provided in the questions section.
- While the method is more expressive than the 1-WL test, this is not surprising. You can basically do anything to increase beyond 1-WL. For instance, simply adding the number of connected components as a feature would make the model more expressive than 1-WL. It would be beneficial to include quantitative results, such as whether the method is weaker than the 2-FWL test, and to compare it with other methods that have proven counting properties for example.
- A more significant issue is that, although the method is more expressive, it also breaks permutation symmetry. It is well known that adding unique node identifiers can make a model universal but breaks permutation symmetry. 
- In Section 5, it is unclear what is meant by having a basis as an input. Additionally, Remark 5.1 is incorrect. In Huang et al., the $\alpha_i$ are always analytic and are sequence-to-sequence mappings, whereas in this work, they are always real-valued mappings that operate on each eigenvector independently. This makes the approach less expressive, at least in the frequency domain.

questions:
- Equation (3) does not accurately represent all possible MPNNs, even when restricting $g$ to be an MLP and $f$ to result from multiplication with a GSO. Specifically, using an MLP from $\mathbb{R}^k$ to $\mathbb{R}^k$ does not trivially extend to a graph signal of dimension $\mathbb{R}^{n \times h}$. It seems that the authors are actually performing matrix multiplications from the right with learnable matrices, and using more than one. Similarly, in Proposition 3.1, the representation in Equation (12) is assumed before the proof begins, which is actually what the authors aim to prove.
- In Proposition 4.3, what is the variable $m$ summing over? The entire proposition lacks clarity, and it appears there is no novelty compared to the existing results from Gama et al.
- The authors claim that Equation (6) is permutation equivariant, which does not seem to be correct. It is only equivariant in expectation, similar to the random positional encodings introduced by Sato et al. (2020).
- What are the contributions to the stability and expressivity analysis? It seems that older results are merely being reused.
- Did the authors follow the standard experimental setup? For example, in the ZINC dataset, it is customary to use a parameter budget of 500K parameters.
- The authors argued that their method is more scalable. Could you a) test on larger graphs, and b) measure the improved speed?

## Additional Comment:

The primary novelty appears to be the use of random features as input for learning positional encodings, instead of typically using eigenvectors. It appears that PEARL is a specific variant of SPE where the equivariant sequence-to-sequence function is replaced by a point-wise function applied to eigenvalues. This point-wise function is simply a learnable polynomial, offering the clear advantage of not requiring eigen decomposition, thus making it faster and more memory-efficient. However, it is unclear whether this approach improves or decreases expressivity or leads to better stability or generalization bounds. 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. Finally, I want to direct the authors to "Spatio-Spectral Graph Neural Networks" by Geisler et al., which also uses spectral and spatial layers in GNNs.

Recommendation:
I recommend rejecting the paper in its current form and suggest that the authors improve the clarity of the manuscript (in terms of novely and also writing) and better integrate it into the existing literature.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732525246818

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Updated manuscript

comment:
We would like to sincerely thank all reviewers for their thoughtful feedback and for appreciating the contributions of our work. We have carefully addressed all the reviewers' concerns and clarified misconceptions about our approach. Each response includes a summary to refresh the key aspects of our work, followed by detailed replies to each comment. We would also greatly appreciate the opportunity to engage further in a constructive scientific discussion.

### Summary of Revisions:

We have made several updates to the manuscript, with the most significant improvements outlined below:

-   **Universal Approximation Result**: We prove that PEARL is a universal approximator of basis-invariant functions. This new result provides substantial insights into the expressivity of the proposed PE framework. In summary, we establish that PEARL is a **generic** positional encoding framework that is **jointly expressive, stable, generalizable, and scalable**. To the best of our knowledge, this is the first PE method to satisfy all these properties simultaneously.
    
-   **Additional Experiments**: We have conducted experiments on three additional tasks—**Rel-stack user-post-comment prediction**, **Rel-stack post-post-related prediction**, and **CSL**:
    
    -   The **Rel-stack tasks** involve large-scale link prediction on the Stack Exchange Q&A Website Database, modeled as a temporal-heterogeneous graph with approximately 38 million nodes. PEARL achieves state-of-the-art performance, demonstrating its effectiveness in real-world applications and its scalability to very large graphs.
    -   On the **CSL benchmark**, which tests graph isomorphism capabilities, PEARL achieves **100% classification accuracy**.

Overall, **PEARL has now been evaluated across 10 different tasks spanning 5 distinct graph types**:

1.  **Molecular Graphs**:
    -   LogP prediction on ZINC
    -   Binding affinity prediction on DrugOOD (3 tasks)
2. **Long-range Molecular Graphs**
    - Multi-label graph regression based on the 3D structure of the peptides
3.  **Social Networks**:
    -   Subreddit classification on REDDIT-BINARY
    -   Subreddit classification on REDDIT-MULTI5K
4.  **Relational Databases**:
    -   Post-post-related recommendation on Stack Exchange
    -   User-post-comment recommendation on Stack Exchange
5.  **Synthetic Graphs**:
    -   Graph classification on CSL

Across all tasks, the results consistently demonstrate that PEARL outperforms baseline methods and, in a few instances, just achieves performance on par with the best-performing approaches. Notably, in many instances, PEARL achieves these results with significantly lower computational and memory complexity, further showcasing its efficiency and practicality. We also include several additional ablation studies and runtime comparisons in the revised manuscript.
</content>
</thread_object>

</thread>


Metareview:
metareview:
Summary: This paper proposes a new way to incorporate positional encodings (or node-wise features) via pooling function. Two types of encodings, i.e., eigenvectors and random features, are considered. The authors also prove their method is universal assuming proper parameterization of the pooling function and neural networks. 

Strength: This paper proposes a simple approach that consistently improves the performance of GNNs (at the cost of additional comparison). The performance improvement is consistent across the considered benchmarks.
 
Weakness: Theorem 3.1 lacks strong connection to rest of the ideas in the work. In the end, the proposed architecture is ensemble of GNNs over randomized features, similar to Equivariant Subgraph Aggregation Networks. An empirical comparison to neural network ensembles with similar inference complexity (not parameter complexity) would have been nice. 

Overall, I recommend acceptance for this work.