GFSE: A Foundational Model For Graph Structural Encoding

Thanks for your valuable feedback and positive comments. We address the potential concerns as follows.

Q1: The contribution of the proposed approach is unclear. It does not appear to be a graph foundation model, but a universal graph positional encoding method.

We agree that it may be more appropriate to frame this work as a universal structural encoding model. However, achieving a full-fledged GFM, capable of seamless adaptation across all domains, remains a significant challenge. In this work, we focus on a different but complementary goal—the exploration of universal structural patterns in graphs, which we believe are critical in developing a GFM. Our GFSE is not intended as an independent GFM, but rather as an assistant to enhance the structural awareness of graph models, whether train-from-scratch models or pre-trained GFMs. Rather than positioning our work as a full-fledged GFM for diverse graph tasks, the main contribution of the paper is to verify the effectiveness and potential of structural patterns in improving the generalizable representation of graph distributions.

[1]Towards Graph Foundation Models: A Survey and Beyond

Q2: The motivation for adopting a universal positional embedding is unclear.

We discuss the motivation of universal positional embedding in Line 49~53. The central idea is tied to the broader goal of developing a graph foundation model (GFM). To achieve this, it is essential to identify universal attributes—domain-agnostic features that can be applied across different graph domains. In this context, we draw inspiration from NLP, where the concept of tokens and contexts is foundational. Similarly, in graph learning, we observe that structural patterns (such as motifs, node connectivity, and graph topology) can also be shared and transferred across different graph domains. This insight motivates the design of a universal positional encoder—a component that captures these transferable structural patterns and makes them available to a wide variety of graph models.

Q3: The paper lacks evidence that the model pre-trained on one dataset (e.g., Dataset A) can be successfully transferred to another dataset (e.g., Dataset B) with strong performance.

We have indeed tested the generalizability of our GFSE in Table 3 and Table 4, where datasets like Arxiv, MNIST, and molecular datasets from the OGB benchmark were not part of the pre-training set. Despite this, our experiments show that GFSE consistently outperforms traditional PSE such as RWSE and LapPE. Furthermore, the GFSE outperforms GPSE, which was pre-trained specifically on a single dataset, highlighting the importance of cross-domain pre-training for improved generalizability to unseen datasets. We believe these results strongly support the claim that our GFSE is capable of transferring knowledge learned from one domain to another, and we will revise the manuscript to make this point clearer.

Q4: It would be interesting to see if this method significantly improves performance on link prediction tasks and on heterophilic graphs.

We kindly bring to your consideration that the experiments presented in Section 4.6 indeed focus on link prediction. Specifically, the downstream task we evaluate is the prediction of whether two items will be co-purchased in a recommendation system. The performance demonstrates the effectiveness of pre-trained PSE in providing structural patterns that are crucial for edge-level tasks.

Our current experiments are not limited to homophilic graphs, where molecular graphs also show a certain heterophilic level. Given the limited time during the rebuttal process, we were unable to include additional experiments on extremely heterophilic graphs. However, we plan to extend our evaluation to include these scenarios in future work and provide a more comprehensive analysis of the model’s capabilities.

Thanks for your valuable feedback and positive comments. We address the potential concerns as follows.

Q1: The claim of being "the first cross-domain graph structural encoder" ignores relevant prior work.

We would like to clarify that GFSE is the first cross-domain graph structural encoder that is supervised by multiple pre-training tasks. We kindly emphasize that the term "cross-domain" in our work refers to the model's ability to generate useful representations for graphs across different domains, without being limited to any specific type of graph data.

While GCC does propose cross-domain pre-training, it relies on a singular task, specifically graph contrastive learning, which leads to relatively coarse-grained embedding and suboptimal performance. In contrast, GraphMAE and other self-supervised methods focus on domain-specific encoders, such as those tailored for molecular graphs, which constrains their ability to generalize to different domains.

Our GFSE goes beyond these limitations by incorporating multiple pre-training tasks—including structure reconstruction and contrastive learning—which enables it to learn more comprehensive and transferable structural patterns across domains.

Q2: The "20.48% average improvement" appears selectively calculated.

The 20.48% improvement is strictly averaged across eight datasets from different domains. GFSE consistently outperforms the baseline models, especially compared to GPSE. The following table shows the improvement rate on different datasets achieved by GPSE and our GFSE, which shows the significance of our contribution.

It is important to note that the smaller improvements observed in some datasets (such as MNIST and PubMed) are due to these graphs relying less on structural information.

Q3: Limited Technical Novelty: The core architecture is largely borrowed from GPS with minimal modifications and the multi-task learning setup uses standard techniques.

While it is true that we draw inspiration from GPS and related works, we believe that the core innovation here is not simply in how these modifications are integrated to achieve theoretically proven powerful expressivity, but in how we leverage multi-task learning to capture universal structural patterns across diverse graph domains, which is a key distinguishing feature from GPS. Moreover, we would like to emphasize that the main contribution of our manuscript is an attempt to investigate the effectiveness of structural patterns as universal attributes for graph foundational modeling. It serves as an assistant to enhance the structural awareness of graph models, whether train-from-scratch models or pre-trained GFMs.

Q4: No comparison with recent advances in cross-domain graph pre-training

We indeed discuss the method in [13] in the Related Work (Line 116). The approach in [13] uses a singular pre-training task and a relatively simple GNN encoder, which results in suboptimal embedding quality. The method in [13] is not open-source yet. Therefore, we didn’t involve this approach as a baseline in this submission. We acknowledge that future work could benefit from a direct empirical evaluation of these models.

Q5: Missing analysis of task interactions shown to be crucial.

We have provided insights on task interactions in Section 4.7, where we analyze the impact of each pre-training task on the overall model performance. In this section, we demonstrate how different tasks contribute to the model’s ability to capture both local and global structural patterns. We also discuss the trade-offs between tasks and how they affect the quality of the learned representations.

Q6: Theoretical guarantees

While our expressiveness analysis shares some foundational elements with [15], we meaningfully extend these results to the random walk positional encoding. We acknowledge the challenges raised in [16] regarding our assumptions. However, it is important to highlight that [16] primarily focuses on local GNN-based architectures, which are fundamentally different from the global structural focus of our framework. Moreover, our theoretical findings are strongly supported by empirical results, which are not included in [16]. We would like to emphasize that while we borrow some insights from previous studies, we have adapted them to our global transformer architecture based on random walk positional encoding, highlighting the theoretical soundness and empirical validity of the proposed framework.

Thanks for your valuable feedback and positive comments. We address the potential concerns as follows.

Q1: The proposed model is not very novel.

While it is true that the GFSE incorporates concepts from existing techniques, the key novelty in the proposed architecture lies in how these components are integrated in a creative manner to achieve theoretically proven powerful expressivity, and how they address the challenge of cross-domain graph structure pre-training. We would like to emphasize that the main contribution of our manuscript is an attempt to investigate the effectiveness of structural patterns as universal attributes for graph foundational modeling. It serves as an assistant to enhance the structural awareness of graph models, whether train-from-scratch models or pre-trained GFMs.

Q2: How are the graphs from different domains encoded by the same encoder?

Here is some misunderstanding. We would like to clarify that GFSE only uses the graph structure as input, represented as random walk encoding in Equation (1). Once GFSE is pre-trained on the graph structure, the raw graph features can be augmented by the PSE generated by GFSE and processed by a downstream graph model, which is consequently trained on a certain dataset for task-specific capacity.

Q3: The baselines used for comparison are not up-to-date.

We follow the baseline setting in GPSE [1] for evaluation and select representative MPNN and graph transformer (i.e., GPS) as the base model. We are currently in the process of incorporating several state-of-the-art graph transformer models into our downstream evaluation, such as Nodeformer and GRIT. We will include the additional experiment results in our revised version accordingly.

[1] Graph Positional and Structural Encoder

Q4: It is recommended to also perform ablation studies on different pre-training domains or datasets.

Thanks for your suggestions. To address your concern, we have carefully analyzed the impact of the number of pre-training datasets on downstream performance, and the results are summarized in the above table (the base model is GPS). Our findings show a few key trends:

• Performance Tends to Decrease as Pre-training Datasets Are Reduced (1-3): As the number of pre-training datasets decreases, we observe a slight reduction in downstream performance, indicating that a more diverse range of pre-training data can help improve the robustness of the model. This trend shows that the model benefits from exposure to a broader variety of graph structures, enhancing its ability to generalize across different graph domains.
• Cross-domain Pre-training is Important (1,4): Additionally, we observe that when GFSE is pre-trained on a singular dataset (e.g., MolPCBA), the downstream performance is consistently lower than when the model is pre-trained on multiple domains. This suggests that cross-domain pre-training is a crucial factor for improving performance.

We will include complete experimental results in our revised version to verify the above conclusion.

Thanks for your valuable feedback and positive comments. We address the potential concerns as follows.

Q1: GFSE primarily appears to be a composite of existing methods. Addressing domain-specificity in graph pre-training, is not compellingly validated by the experiments.

While it is true that the GFSE incorporates some concepts from existing techniques, the key novelty lies in how these components are integrated to achieve theoretically proven powerful expressivity in a creative manner, and how they address the challenge of domain-specificity in graph pre-training. We kindly bring to your consideration that the main contribution of our manuscript is an attempt to investigate the effectiveness of structural patterns as universal attributes for graph foundational modeling. It serves as an assistant to enhance the structural awareness of graph models, whether train-from-scratch models or pre-trained GFMs. In experiments, the superiority of GFSE over GPSE, which is pre-trained on a specific dataset, verifies the benefit and importance of cross-domain pre-training.

Q2: The downstream evaluation in section 4.4 does not include comparisons with SOTA models.

Our GFSE is primarily positioned as a foundational structural encoder, we thereby have chosen to compare against traditional and pre-trained PSE. We include GPSE as a baseline, which is the most recent SOTA method for graph PSE. Additionally, we compare with other competitive PSE. GFSE has achieved larger performance improvements on average compared with GPSE (shown below), which shows the significance of our contribution. Please note that when the best performance approaches near-perfect scores for benchmark datasets, designing a generic PSE that results in a consistently better performance becomes extremely challenging. However, despite these challenges, GFSE has resulted in a performance gain that is higher than the performance gain of earlier studies.

The average performance gain of GPSE (ICML2024) and Ours on different datasets:

Q3: The experiments in section 4.3 lack detailed descriptions of hyperparameter tuning

Thanks for bringing this to our attention. We follow the GPS [1] framework to implement the base models, including GIN, Transformer and GPS. Specifically, the hyper-parameters of the Transformer (for triangle) and GPS (for Pattern and Cluster) are shown below. We use 2 linear layers in MLP and 6 message-passing layers in GIN. We will revise the manuscript accordingly to include more details about hyperparameter tuning.

[1] Recipe for a General, Powerful, Scalable Graph Transformer

Q4: Ablation studies comparing GFSE with GRIT’s RRWP.

To address your concern, we have conducted ablation studies comparing GFSE and RRWP on three datasets using both GateGCN and GPS, as shown in the table above, The results clearly demonstrate that GFSE consistently outperforms RRWP, particularly for base models that lack global graph structures, emphasizing the strengths of our approach:

• Our GFSE provides a more generalizable representation compared to RRWP, regardless of whether the model is based on a global transformer architecture or a local GNN architecture.
• The more significant improvement when combining GFSE with GateGCN can be attributed to the fact that GFSE incorporates global structural information, which complements the local message-passing used by GNNs like GateGCN.
• The embedding generated by GFSE is inherently derived from the insights of RRWP but is enhanced by the ability to incorporate more global structural awareness. This makes GFSE more flexible and capable of encoding universal structural patterns that are transferable across different domains. We will provide an additional comparison with RRWP in our revised version.

Thanks for your valuable feedback and positive comments. We address the potential concerns as follows.

Q1: The definition of ‘foundation model for graph structure encoding’ in the title remains unclear.

We define a graph foundation model (GFM) as "a model pretrained on extensive graph data, primed for adaptation across diverse downstream graph tasks.", which aligns with the concept proposed in the previous survey [1]. However, achieving a full-fledged GFM, capable of seamless adaptation across all domains, remains a significant challenge due to their heterogeneous features. In this work, we focus on a different but complementary goal—the exploration of universal structural patterns in graphs, which we believe are critical in developing a GFM. Our GFSE is not intended as an independent GFM, but rather as a foundational assistant to enhance the structural awareness of graph models, whether train-from-scratch models or pre-trained GFMs. Rather than positioning our work as a full-fledged GFM for diverse graph tasks, we aim to verify the effectiveness of structural patterns in improving the generic graph representation and its generalizability in cross-domain scenarios.

[1] Towards Graph Foundation Models: A Survey and Beyond

Q2: An evaluation without pre-training the GFSE is missing. The impact of the number of pre-training datasets on downstream performance is not shown. Is there a trend that shows better downstream performance as the number of pre-training datasets increases?

Thanks for your suggestions. To address your concern, we have carefully analyzed the impact of the number of pre-training datasets on downstream performance, and the results are shown in the above table (the base model is GPS). Our findings show a few key trends:

• Performance Tends to Decrease as Pre-training Datasets Are Reduced (1-3): As the number of pre-training datasets decreases, we observe a slight reduction in downstream performance, indicating that a more diverse range of pre-training data can help improve the robustness of the model.
• Pre-training is Crucial for Better Graph Representations (1, 4, 5): When comparing the performance of GFSE trained-from-scratch V.S. GFSE pre-trained on different datasets, we observe that pre-training leads to better downstream performance in most cases. This underscores the importance of pre-training for generating more expressive and beneficial graph representations.
• Cross-domain Pre-training is Important (1,4): Additionally, we observe that when GFSE is pre-trained on a singular dataset (e.g., MolPCBA), the downstream performance is consistently lower than when the model is pre-trained on multiple domains. This suggests that cross-domain pre-training is a crucial factor for improving performance.

We will include complete experimental results in our revised version to verify the above conclusion.

Q3: The experiments combining GFSE with LLMs should be compared against existing models that integrate LLMs with graphs.

We do compare our approach with GraphPEFT, one of the most recent SOTA models for text-attributed graphs, in Appendix F.2. Our GFSE consistently outperforms the version of GraphPEFT that skips the domain-specific pre-training step. Moreover, our model matches or even outperforms GraphPEFT which incorporates costly domain-specific pre-training. We acknowledge the benefit of evaluating against other models that integrate LLMs with graphs, and we are actively working on including more recent approaches in our revised version.

Thank you for your supplementary explanations and experiments during the rebuttal period, which addressed some of my concerns. I have raised my score to 6.

However, my main concern remains the proposed pretraining structural encoder method, which seems to overclaim as a “foundation model for graph structure encoding.” I suggest narrowing the scope to a more appropriate range, similar to methods like GPS or “Graph Neural Networks with Learnable Structural and Positional Representations.”

Additionally, if you claim this as a “foundation model for graph structure encoding,” it is essential to provide theoretical explanations about what transferable information the model learns and how this information enables broad improvements across diverse datasets. Furthermore, please clarify why the knowledge learned from these four tasks is sufficient to cover all transferable structural information. Why would adding more self-supervised tasks not further improve generalization?