Graph Transformers Get the GIST: Graph Invariant Structural Trait for Refined Graph Encoding

[W1 - The theoretical analysis lacks clarity in terms of its practical implications for model improvements]

In Section 4, we present a theoretical analysis showing that GIST is invariant under graph isomorphism. This means GIST consistently captures the true structure of a graph, regardless of how its nodes are ordered. As a result, when used with a graph transformer, GIST prevents node ordering from influencing the model’s behavior.

While the vanilla attention mechanism without positional encoding is also insensitive to node order, incorporating traditional sequential position encodings reintroduces order sensitivity as clearly stated in Graphormer by Ying et al., NeuRIPS 2021. This highlights the need for an attention bias like GIST that both encodes structural information and preserves invariance to node permutations.

[W2 - Datasets are not large-enough]

First, we would like to note our work mainly focus on graph classification task, and highlight a potential discrepancy in the definition of a "large-scale graph classification dataset." According to multiple recent works on graph transformers, the ZINC-full dataset (250K graphs) is widely regarded as a "large-scale" benchmark for graph classification and is one of the most commonly used datasets in this context. Here is supporting evidence:

• GRIT by Ma et al., ICML 2023, a widely recognized SOTA graph transformer, states: "We also conduct experiments on the larger datasets ZINC-full graphs (~250,000 graphs),"
• FragNet by Wollschlager et al., ICML 2024, a recent SOTA GNN-based method, explicitly refers to ZINC as a "large-scale molecular benchmark."
• The HDSE baseline by Luo et al., NeuRIPS 2024, which was suggested by the reviewer, claims to apply "HDSE to large-scale graphs." However, their largest graph-level task is the Peptides dataset (~15K graphs), and they do not include ZINC-full in their experiments.

We also surveyed recent graph transformer and graph-level works from ICML 2024, and to the best of our knowledge, none of them included experiments on graph classification datasets larger than ZINC-full. Given this context, we believe our choice of dataset is consistent with standard practices in the field.

Nevertheless, we here provide additional experiment on PCQM4Mv2, one of the largest-scale graph regression benchmark of 3.7M graphs, from widely adopted OGB challenge in Table 1. Due to time constraints and the large size of PCQM4Mv2, GIST's training has not yet fully converged. Nevertheless, the current results already surpass many baselines, and we anticipate even stronger performance as training continues over the next few days. We also provide experiment results one two node classification datasets to showcase the applicability of our proposed method to different graph tasks.

Table 1: Performance of GIST on Cluster, Pattern, and PCQM4Mv2 datasets.

[W3 - Essential discussion of related work, HDSE]

We thank the reviewer for their meticulous review of our work and agree that HDSE follows a similar trajectory in capturing substructures within graphs. However, we would like to highlight that HDSE's structural bias, Graph Hierarchy Distance, differs from our proposed bias, Graph Invariant Structural Trait (GIST). While both approaches enhance graph transformers, GIST consistently outperforms HDSE across various datasets (Table 2). We attribute this to GIST’s ability to capture higher-order structural relationships through the information exchange point, as discussed in Observation 2 of the Motivation section. We will make sure to incorporate this discussion into the final version of our paper.

Table 2: Performance comparison of GIST vs. HDSE

[W4 - Visualization for experimental results]

Our tables and color-coded rankings (top-1,2,3) follow standard practices in the field—including the HDSE baseline suggested by the reviewer.

Since the suggestion "The experimental results could be supplemented with visual examples" is broad, we are unsure what specific visualization is desired. If the reviewer means bar charts, we are happy to provide them—otherwise, please clarify, and we will accommodate accordingly.

We hope our rebuttal clarifies concerns on dataset scale, related work, and results. We’ve added PCQM4Mv2 experiments to demonstrate scalability and are open to further experiments or visualizations as needed. Given these improvements, may we kindly ask the reviewer to reconsider our contributions and rating?

[W1 - Exra overhead cost of GIST computation]: Sure. Here are an analysis of GIST computation overhead cost and training efficiency of our proposed method.

We kindly direct them to our new analysis on the one-time pre-computation overhead of GIST features and the overall training efficiency of GIST in our response to W2 of reviewer L3nR. We would like to emphasize that GIST computation incurs only a one-time cost at the beginning, and this overhead is minimal. We also provide experimental results of GIST on PCQM4Mv2 (~3.7M graphs), one of the largest graph-level challenges in the community, to further reinforce its scalability and efficiency in our response to W2 of reviewer 1uvt.

[W2 - Typo. Figure 1 could be difficult to interpret.]: May we kindly ask which part of Figure 1 is confusing the reviewer? In the mean time, we elaborate Figure 1 again here.

We thank the reviewer for their careful reading of our paper. We will clarify any ambiguous technical terms in the final version. Regarding the specific points raised:

1. The statement "Each node has d_n associated node features" is intended to mean "Each node has d_n-dimensional associated node features," which we specify mathematically as "$x_v \in \mathbb{R}^{d_n}$". We will make this and related definitions clearer in the final version.
2. Since we have provided a 13-line explanation in the caption of Figure 1 and further details in the Motivation section (Observation 1), may we kindly ask the reviewer to specify which part is unclear so that we can provide a more precise clarification?
3. While reiterating the purpose of Figure 1 poses a risk of redundancy, we are happy to elaborate again here: Using the same graph, subfigure 1a illustrates a part of the 4-hop GIST features for two nodes $(u, v_1)$ that belong to the same substructure. In contrast, subfigure 1b depicts a part of the 4-hop GIST features for two nodes $(u, v_2)$ that belong to different substructures. The GIST feature is a tensor where each cell $(k_u, k_v)$ encodes the number of nodes in the neighborhood that are exactly $k_u$ hops from node $u$ and $k_v$ hops from node $v$. This comparison highlights how GIST features enable the transformer to distinguish nodes belonging to different substructures within the same graph, guiding the attention mechanism to differentiate node pairs more effectively. Please refer to our Observation 1 in Motivation section for a more detailed discussion. We hope this clarifies the reviewer’s concerns regarding Figure 1.

[Sec 3.3 clarification]

We further elaborate on the theoretical complexity of exact GIST feature computation, which we addressed in Section 3.3 by introducing an efficient estimation algorithm using MinHash and HyperLogLog. For empirical validation of the algorithm's efficiency, please refer to our response to W2 of reviewer L3nR for detailed results.

A naive approach to compute the exact number of nodes in the $(k_u, k_v)$-neighborhood intersection for a node pair $(u,v)$, denoted as $C_{k_u,k_v}(u,v)$, follows the pseudocode below:

counts = 0
FOR x_u in N_ku(u) do
    FOR x_v in N_kv(v) do
        if x_u == x_v do
            counts += 1
RETURN counts

Time Complexity Analysis:

1. The worst case (e.g., a fully connected graph) results in a worst-case complexity of $O(n^2)$ for computing a single $C_{k_u,k_v}(u,v)$.
2. Since GIST requires computing $k^2$ such values per node pair $(u,v)$, the complexity increases to $O(k^2 n^2)$ per node pair.
3. Given that a graph $G$ with $n$ nodes has $n^2$ node pairs, the total complexity becomes $O(k^2 n^4)$ for exact GIST computation, which is impractical for a large number of graphs.

To overcome this infeasibility, we propose a low-complexity estimation algorithm (Algorithm 1 of our paper) to approximate GIST features efficiently. We highlight that the naive $O(n^2)$ approach to compute the exact number of nodes in the $(k_u, k_v)$-neighborhood intersection for a node pair $(u,v)$ can be efficiently estimated in constant time $O(1)$ using Algorithm 1. With that, we eliminate the $O(n^2)$ bottleneck from the overall complexity. As a result, the final time complexity for computing GIST features across the entire graph is reduced to $O(k^2 n^2)$, making our method significantly more scalable for a large number of graphs.

We hope the additional results and discussion provide the reviewer with a clearer understanding of the mechanism behind our proposed method. Given these clarifications and improvements, we kindly ask the reviewer to consider whether our contributions warrant a higher rating.

[W1 - The novelty of this paper is somewhat limited, since the general idea to add structural bias to the attention mechanism is not very novel.]: Our novelty lies in the GIST features, which offer a more effective way to encode structural information.

We agree with the reviewer that adding structural bias to attention is not a new problem in graph transformers. However, it remains a central and unresolved challenge to determine which structural bias effectively captures complex graph structures, hence improving graph transformers. Prior works have proposed various biases, such as shortest path in Graphormer or RRWP in GRIT, yet none have successfully captured both substructures and the higher-order interactions between them, as we pointed out in our Motivation section. These two aspects are crucial for learning effective graph representations, as highlighted in FragNet. To the best of our knowledge, our work is the first to address both challenges, providing novel structural representations for effective graph representation learning in graph transformers, evidenced with our outstanding performance result.

[W2, W3 - Insufficient experiments on ablation study and efficiency]: Sure, here are 3 more ablation studies, training efficiency analysis, and GIST computation overhead report across 3 different datasets.

We thank the reviewer for raising this question. To address it, we provide the results across three datasets:

1. We present ablation studies on different $k$-hops (Table 1), different numbers of MinHash functions (Table 2), and different values of HyperLogLog’s $p$ (Table 3). Overall, GIST demonstrates robustness across various hyperparameter settings. We would like to note that higher values of HyperLogLog’s $p$ and a greater number of MinHash functions reduce the error in estimating $k$-hop intersection cardinality, leading to improved performance of GIST. This trend is consistently reflected in the tables.
2. We present an efficiency experiment on training time (Table 4), which shows that GIST's training time is comparable to or even lower than other graph transformers. Notably, our method does not require extensive pretraining like other pretrained graph models, yet it outperforms most of them on MoleculeNet benchmarks, as demonstrated in Table 5 of our paper.
3. An analysis of the one-time computation overhead of GIST features (Table 4). We would like to emphasize that GIST computation incurs only a one-time cost at the beginning, and this overhead is minimal. As highlighted in Section 3.3, we use an efficient estimation algorithm of GIST features using MinHash and HyperLogLog, allowing us to approximate the $k$-hop substructure intersection with a constant number of operations. Theoretically and empirically (Table 4), this design ensures that our method remains computationally efficient while preserving the effectiveness of structural representation.

Table 1: Ablation study on different values of $k$-hops

Table 2: Ablation study on different numbers of MinHash functions

Table 3: Ablation study on HyperLogLog data structure with different values of p

Table 4: One-time pre-computation and Training time of GIST (hour:min)

Table 5: Performance of GIST + RRWP

[W4 - Typo]

We thank the reviewer for carefully reading our paper. We will correct the typo in L204 and ensure consistent usage of "graph transformers" throughout the paper.

We hope the additional results and discussion can help the reviewer better understand the mechanism of our proposed method, and maybe warrent us a higher rating.

We thank the reviewer for the detailed feedback. Given the 5k char limitation and 8 distinct questions raised by the reviewer, unfortunately many of our responses will be condensed and citing other replies. Should the reviewer be interested in an elaboration in any particular response, please let us know and we will be more than happy to accomodate.

[W1 - How to guarantee the method can aggregate diverse substructures information]

GIST encodes $k$-hop substructures between node pairs (Definition 3.2), enabling a broad representation of substructural relationships through all-to-all comparisons.

When integrated with graph transformers, GIST’s all-to-all substructure information enhances the attention mechanism. Specifically, with GIST, each node’s embedding is updated by incorporating structural interactions with every other node, allowing for a more structure-aware aggregation of representations. This facilitates effective propagation of structural patterns across the graph.

As shown in Figure 1, GIST helps differentiate substructures, guiding diverse attention aggregation—a capability further visualized in Figure 2 with learned GIST features on ZINC.

[W2 - How to theoretically verify the proposed method could be more expressive than other methods]

It is difficult to rigorously prove that one graph feature is universally more expressive than another. For instance, Proposition 3.2 in GRIT shows that GD-WL with RRWP is at least as expressive as GD-WL with SPD and highlights a special case where RRWP outperforms SPD. However, this does not imply that RRWP is strictly superior across all scenarios—only in rare, impractical graph structures.

This underscores a broader issue: theoretical arguments on graph feature expressiveness often lack generality and rigor, even in existing works. Thus, we prioritize empirical analysis to assess practical effectiveness, a stance acknowledged by reviewers e5VJ and 1uvt.

[W3 - Datasets are not large enough]

Please refer to W2 in our response to reviewer 1uvt for a detailed discussion on large-scale datasets.

[W4 - Importance of structural-invariance in GIST]

We refer reviewer nG8X to our detailed discussion on the importance of structural-invariance in GIST in our response to W1 of reviewer 1uvt.

[W5 - Hyperparameter sensitivity analysis]

We direct the reviewer to our new ablation studies in our response to W2 of reviewer L3nR.

[W6 - Combination with other structural encoding]

We have already explored the combination of GIST with RRWP and SPD previously, but neither improved performance. Here, we present one result on GIST + RRWP, where RRWP is concatenated with GIST as a structural bias:

$[x \| y] \in \mathbb{R}^{k^2 + 2k + \text{steps}}$

As shown in Table 5 in our response to reviewer L3nR, GIST alone outperforms the combination. While both encode structural information, GIST has been shown empirically to be a stronger structural bias. Thus, incorporating RRWP may introduce noise into GIST’s learning process, leading to a slight drop in transformer performance.

[W7,W8 - Application to GraphLLM, GFM, node- and link-level]

We are not too sure whether the reviewer is expecting some Yes/No answers or is actually requesting us to do it. In short, the answers to these questions are generally a "Yes, GIST has the potential to extend to [x]"; but, respectfully, we believe it can be fairly argued that such applications are clearly out of scope. This is evident by the fact that most established prior works on graph transformers — such as GRIT, HDSE, and Subgraphormer — do not explore such extensions like GLLM/GFM.

The underlying reason is such an extension would very much deserve a paper of its own, potentially requiring extensive pre-training and pipeline efforts and being mindful of typical GFM challenges like dim mismatches and hyperspace misalignments (Galkin et al., ICML 2024), making such explorations worthy of their own research and it is impossible to complete during rebuttal period. What we can provide, is GIST outperformed pre-trained graph models, as showcased in Table 5 in our paper.

On the task end, our method primarily targets graph classification as clearly stated in various places of our writing. While we appreciate the reviewer’s suggestion for other graph tasks, we must note there are countless research focusing solely on graph classification advancement, and contribution in this regard is well-recognized.

Still, to showcase generalizability, we present results on two node-level datasets and one large-scale graph regression task (see Table 1 in W2 of our response to reviewer 1uvt). We hope this additional evidence will prompt the reviewer to reconsider the assessment.