Holographic Node Representations: Pre-training Task-Agnostic Node Embeddings

We are grateful to the reviewer for the detailed and constructive feedback, and we appreciate the recognition of our theoretical justifications alongside the extensive empirical analysis. We proceed by answering each comment in the following.

Q1: As the very first definition of the paper, Structural Representation is not very clear. For example, in line 107, 'order r' is confusing, since it was previously defined as the cardinality of a node subset S. And the explanations for the subscript $S$, $\pi \circ$, and permutation matrices are missing from the definitional formulation. how do I understand the output format of the function f, which is not clear to me? Do the last r rows of the output matrix repeat some r rows of the previous n rows?

A1: It is indeed correct that by order r we mean the cardinality of the set of nodes involved in the predictions. In Line 107, we define a function $f$ that returns structural representations of order r as the function that returns representations for all possible subsets of $r$ nodes, namely $\binom{n}{r}$, such that the representations for isomorphic node sets are the same. Therefore, the output of $f$ is a matrix where each row is the representation of a node set, and rows corresponding to isomorphic node sets are the same. Then, as we discuss in the Notation paragraph, the subscript $S$ is used to access the representation of the node set $S$, i.e., $f(\mathbf{A}, \mathbf{X})_S$ indicates that we access the row corresponding to $S$.

Q2: The same question appears in the formulation of the reduction map: where is the input of r for the corresponding output matrix in equation (3)?

A2: The reduction map is task-order specific, meaning there is a distinct reduction map for each task order $r$. For a task of order $r$, the reduction map returns representations for all possible sets of $r$ nodes, and therefore the output is a matrix with $\binom{n}{r}$ rows. Each time we adapt to a new task, we create a corresponding reduction map that matches the task order and learn it on that task. The reduction map is lightweight, which ensures efficiency despite handling multiple task-specific reduction maps.

Q3: What kind of task-agnostic information can we store in node embeddings? This is because the analogy between pre-training for word embeddings and node embeddings is not perfectly aligned across different graphs. If the scenario we're focusing on in this paper is the nodes from the same graph, then it's necessary to make this point very clear.

A3: In this paper, we focus on storing task-agnostic information in node embeddings, and we focus on nodes from graphs within the same dataset. In other words, our current work specifically addresses generalization across different tasks on the same dataset, rather than across datasets. We have further added this point in the revised manuscript to make our focus on within-dataset task-generalization clearer. We believe that generalizing to different tasks in different datasets (potentially differing in the input node and edge features) represents an interesting and challenging direction, which we are happy to explore in future research.

Q4: It is confusing to me that in the real world, most of the graphs come with node-level distinctive features, which is fed in V1, for this purpose, how significant is the necessity of breaking symmetry technique to distinguish structurally isomorphic nodes?

A4: This is an interesting question and we thank you for bringing this up. While it is true that real-world datasets often include node features that reduce the number of isomorphisms, symmetry breaking still provides important benefits. It facilitates counting substructures and facilitates function approximation by making node embeddings more diverse and well-separated, which improves classifier performance. This can be seen from the fact that, while most graph-classification datasets contain graphs that can be distinguished by standard MPNNs, expressive GNNs (which break symmetries) perform significantly better on these datasets (Cotta et al., 2021). Similarly, in link prediction datasets that include discriminative node features, expressive structural representations (of order 2), obtained by breaking symmetries, tend to outperform other methods (Zhang et al., 2021).

Q5: Why not preserve all symmetries in the first place, but fuse them without bias, and then follow the same idea of the current design of the reduction map?

A5: Thank you for this great question. Preserving all symmetries upfront in a node embedding would imply encoding every possible symmetry. However, Proposition 2.3 shows that no single node embedding model can return node embeddings encoding all the necessary symmetries for two different tasks. Holographic node representations address this limitation by first creating symmetry-free representations, which can then be adapted to include the task-specific symmetries.

We are glad the reviewer appreciated our proposed approach and recognized our thorough analysis of HoloGNN from the perspective of canonical eigenvectors. Your review raised an interesting point of discussion, which we address below.

Q1: Does the authors regard the HoloGNN as a pretraining approach? My major concern is about the 'pretraining' term used in the work, as it is biased from the widely accepted perspective, which usually refers to an unsupervised task.

A1: We acknowledge that the term “pre-training” often implies unsupervised learning, particularly in natural language processing and computer vision. However, in graph machine learning, the concept of pre-training is arguably less established, and there is no prevailing unsupervised pre-training task. Our work does not introduce a new pre-training task; rather, HoloGNN is a novel architecture suitable for pre-training. This means it can integrate with any existing pre-training task, whether unsupervised or supervised. For instance, HoloGNN can be paired with unsupervised techniques such as masking edges and predicting them, as done in the Cora dataset in Figure 3.

Furthermore, as noted in the paper recommended by the reviewer [1], supervised pre-training remains relevant and effective, especially in domains like molecular prediction. Table 1 of the cited work demonstrates that graph-level supervision is necessary for strong downstream performance of a standard GNN model. We speculate that one reason for the absence of a dominant graph ML pre-training paradigm may be the lack of architectures designed to support a variety of tasks, and HoloGNN opens up new avenues for re-evaluating both supervised and unsupervised pre-training tasks in graph ML.

Additionally, we want to clarify that our evaluation is not limited to a single downstream task. For example, in the MovieLens experiments, we pretrain HoloGNN on one task and adapt it to three different downstream tasks, with detailed results presented in Table 3 in Appendix E.1 and aggregated results in Figure 3 in the main paper. This setup demonstrates that HoloGNN can be effectively pre-trained on one task and adapted to multiple downstream tasks.

We feel that this choice of terminology accurately reflects the value proposition of HoloGNN and is a useful key-word for helping readers interested in pre-training GNNs to find our work. However, if you see this as source of confusion for the wider audience, then we propose to fix it by changing the title from

“Holographic Node Representations: Pre-Training Task-Agnostic Node Embeddings”

to

“Holographic Node Representations: Task-Agnostic Node Embeddings”

Given this discussion, please do let us know how you would like to proceed and we will gladly make adjustments as needed, including adding a discussion to the paper for further clarity.

We greatly appreciate the reviewer’s detailed feedback. We are pleased to notice you have found our approach novel and interesting. Your review raised a number of important points we would like to clarify.

Q1: There is no justification for Property (1) and Property (2).

A1: Properties (1) and (2) are essential to ensuring that holographic node representations can be trained in a task-order agnostic way, whilst still being able to map representations back to order-specific representations during test time. Specifically Property (1) guarantees final task-specific representations are structural of order $r$; and Property (2) ensures that the output of the expansion map consists of $T$ positional, and thus symmetry-free, representations, which are necessary for task-general node representations due to the impossibility result from Proposition 2.3. We include a discussion of these points in Section 3.1, but appreciate the feedback that this is not yet made sufficiently clear. We have revised the manuscript to further emphasize and clarify these points as they are a crucial conceptual pivot point of the paper.

Q2: Section 4.1 is difficult to follow as it lacks sufficient details on the node-breaking selectors. More elaborations about node-breaking selectors and why these selectos are needed in the expansion map should be provided to enhance clarity.

A2: Thank you for the feedback, we have incorporated this into the manuscript by giving an intuitive description of the role of breaking selectors.

In a nutshell the main idea is: 1) in order to learn task-general representations the expansion map must not have any permutation symmetries; 2) to achieve this, we “break” symmetries by perturbing the features of nodes and then feeding this through a typical structural model like a GNN; 3) but crucially this breaking cannot be done arbitrarily since otherwise there is no way to re-introduce task-specific permutation symmetries in the reduction map (i.e., no holographic node representation); so 4) in Definition 4.1 we give a set of properties for the breaking selectors that guarantees we obtain holographic node representations (Theorem 4.4).

Q3: Complexity analyses should be provided to understand the additional computational cost introduced by these algorithms and to clarify whether the parallel breaking algorithm can effectively reduce the cost.

A3: This is an excellent point and we are grateful for this good idea to improve our paper. We have added the following discussion to the revised manuscript.

The complexity of the two algorithms is determined by the complexity of $f_t$ (for sequential breaking) and $f_\lambda$ (for parallel breaking). Suppose $f_t$ and $f_\lambda$ are Message Passing Neural Networks, which have linear complexity in the number of nodes $n$ and edges $m$, $\mathcal{O}(n + m)$, where the feature dimension $d$ is considered constant. Since both sequential and parallel breaking perform $T$ calls to the corresponding MPNNs, each time by passing a new breaking node, the complexity is $\mathcal{O}(T(n + m))$ in both cases. Note that in our experiments $T \ll n$ and $T \ll m$. For instance, in the Pubmed dataset $T=8$, $n=19717$, $m=88648$. In the parallel breaking algorithm, all $T$ calls can be done in parallel, because each breaking is applied to $\mathbf{V_1}$, and $f_\lambda$ does not take all prior embeddings.

Q4: The paper lacks discussions and comparisons with the graph transformer models. What are the advantages of the proposed HoloGNN model compared with graph transformer models?

A4: Graph transformers rely on positional encodings, which make their learned representations inherently positional. As discussed in Section 2, such positional representations are task-order specific. This task-order specificity makes graph transformers unsuitable for pre-training a single model that can generate flexible representations capable of adapting to tasks of varying orders. In contrast, HoloGNN focuses on producing task-agnostic, symmetry-free representations that can efficiently adapt to different task orders. Nonetheless, we appreciate the suggestion and we have added a comparison with GPS (Rampasek et al., 2022) on Cora. While GPS performs well when adapted to Link Prediction, it suffers a dramatic performance drop of 41.5% when pre-trained on Link Prediction and adapted to Node Classification, while HoloGNN results in a performance drop of only around 1%.

We thank the Reviewer for the prompt reply. We address the remaining concerns in the following:

I would like to clarify that my concern lies in the lack of theoretical proof demonstrating that these two properties hold.

We would like to clarify that Theorem 4.2 shows that single node breakings result in Property (2) to hold and Theorem 4.4 shows that our reduction maps satisfy Property (1). We thank you for this question and we will clarify this point further in the next revision.

The proposed model can only generalise across different tasks on the same dataset.

Overwhelmingly, graph learning focuses on training and testing on the same dataset, e.g., [1,2,3]. Extending generalization beyond a single dataset remains one of the most critical open challenges in graph machine learning. For example, the community currently lacks clear guidelines on pairing datasets for effective transferability, though there are promising results in specific domains such as biological graphs [4]. Moreover, the diverse node and edge feature spaces across graph datasets pose additional challenges for designing models capable of transferability. We believe that, while important, trying to answer this broad open problem would distract the reader from our contribution, which introduces representations capable of adapting to different tasks. We will clarify this perspective in the revised version.

The results in Figure 3 show that the performance of HoloGNN pre-trained on task1 and then transferred (which do include fine-tuning) to task2 on the same dataset is worse than directly training on task2.

Similarly to LLMs and pre-trained vision settings, a pre-trained model will likely underperform a task-specific model trained on that task with sufficient data. This is why neither HoloGNN nor any other model is expected to perform better when adapted than when directly trained on the task with ample data. However, the advantage of pre-trained models is a much lower compute-time to solve a new task. This advantage is particularly pronounced given that training on a different order task may require completely changing the GNN backbone to accommodate the task’s distinct symmetries. In contrast, HoloGNN enables the same embeddings to be adapted across multiple tasks without the need for redesigning the architecture for each new task.

Experimentally, HoloGNN shows more consistent performance and thus smaller performance loss than any other baseline across all datasets and tasks. While multiple models perform comparably on the pre-training task, HoloGNN perform significantly better when adapted to solve a new task (e.g., 1.5% drop of HoloGNN vs 9% drop of GCN in Figure 3 on Cora when adapted to node classification, where the lower the drop the better).

We hope this addresses the Reviewer’s concerns and appreciate the opportunity to clarify these points further.

[1] Kipf and Welling 2017. Semi-supervised classification with graph convolutional networks.

[2] Xu et al. 2019. How powerful are graph neural networks?

[3] Rampášek et al., 2022. Recipe for a General, Powerful, Scalable Graph Transformer.

[4] Huang et al., 2023. Learning to Group Auxiliary Datasets for Molecule.

Dear Reviewer,

Thank you once again for your thoughtful feedback. Since the rebuttal period is coming to an end, we wanted to follow up to ensure that our responses have addressed your concerns.

While the experiments in the paper use all available data in common datasets and demonstrate that HoloGNN performs consistently across tasks, we conducted an additional experiment showing that pre-training on a different task benefits performance when target task data is limited.

Our new experiment, presented in the table below, demonstrates that:

1. When sufficient data is available, a task-specific model trained directly on that task outperforms a pre-trained model.
2. When data is scarce, pre-training on a different task yields better performance than direct training on the limited data.

Specifically, we evaluated performance on the CORA node classification task with only 40% of the data available for training on such a task. Under these conditions, models pre-trained on link prediction (with more data) showed superior performance compared to models trained directly on node classification with the limited data. However, as noted previously, even if pre-trained models do not outperform task-specific models when the latter are trained with sufficient data, their advantage lies in significantly lower compute-time for solving new tasks. Notably, HoloGNN consistently outperforms all other models when adapted to new tasks.

We hope this additional experiment clarifies our answer. If these points address your concerns, we would greatly appreciate it if you could consider revisiting your score.

We are pleased that the reviewer found our research question interesting, appreciated the novelty of our proposed approach, and found the paper to be well-written. We address the question in detail below.

Q1: It would be better if the paper included experimental results on graph classification.

A1: Following your suggestion, we conducted an additional experiment on the molhiv dataset from the OGB benchmark, which is designed for graph classification (an order-n task). We created a link prediction task (an order-2 task) on the dataset and evaluated the performance of both GCN and HoloGNN under two scenarios: first, when the models were pre-trained and tested directly on the graph classification task, and second, when the models were pre-trained on the link prediction task and then adapted to the graph classification task.

The results are reported on the table below. HoloGNN demonstrates significantly more consistent performance than GCN. In particular, the difference in performance between HoloGNN when trained on graph classification (78.19%) and its performance when pre-trained on link prediction and adapted to graph classification (76.43%) results in a performance drop of 1.76%, while GCN suffers a more pronounced drop of 5.77%. These results further underscore the capabilities of holographic node representations, which can be pre-trained on tasks of any order and then effectively adapted to solve tasks of different orders.

Thank you for the clarification and additional experimental results.