Topology-Informed Graph Transformer

We thank the reviewer for providing helpful comments to our manuscript. Please find our responses to the weaknesses of the manuscript and questions pointed out by the reviewer.

• Weakness 2: We thank the reviewer for pointing out the issue. We added a condition that the graph G is a connected graph. Nevertheless, we would like to note that the given definition of biconnectivity of graphs, assuming G is connected, is correct. The vertex v and edge e of the graph G such that the number of components of G \ {v} and G \ {e} is greater than 1 correspond to a cut vertex and a cut edge of the graph G.
• Weakness 3: Theorem 3.2 shows that there exists a pair of graphs such that TIGT can distinguish whereas 3-WL cannot distinguish. The theorem does not claim that all graphs not distinguishable by 3-WL can be distinguished by TIGT. Hence, the current proof of Theorem 3.2 in the appendix of the manuscript is correct, because it presents a particula pair of graphs that 3-WL cannot distinguish whereas TIGT can.
• Weakness 1, Question 1: One prominent novelty of this work comes from obtaining an optimal balance among encapsulating the merits of Cy2C-GNNs in incorporating topological invariants of graph datasets, utilizing the advantages of Graph Transformers in effectively analyzing node and edge features of graph datasets, and sustaining the expressive power of GNNs even under increases in number of hidden layers. Our newly added implementations demonstrate that TIGT successfully implements the optimal balance of the aforementioned three conditions, whereas other GNNS or transformer architectures may not effectively satisfy all three conditions simultaneously.
• Question 2: The theoretical innovation of the paper focuses on the capability to incorporate cyclic substructures of graphs to graph transformers, and demonstrate how cyclic substructures are related to geometric properties of graphs analyzed from previous studies. We note that Cy2C-GNN does not incorporate cyclic substructure to graph transformers. As such, Theorem 3.1 and 3.2 demonstrates that cyclic substructures can be also incorporated into graph transformer architecture, the proof of which utilizes the theoretical results from Choi et al. (2023). The manuscript also proves new theoretical results which relates cyclic substructures of graphs with previously studied innate properties of graphs (graph biconnectivity), and analyzes limitations of previously studied techniques which utilize positional encoding of graph datasets. In particular, Theorem 3.3 utilizes Euler characteristics of graphs to show that biconnectivity of graphs can be detected from analyzing cyclic substructures of graphs. Theorem 3.4 utilizes geometric ergodicity of Markov chains (i.e. that the rate that a probability distribution converges to a stationary distribution of a Markov chain is comparable to the rate that a geometric sequence converges to a limit) to show potential limitations in attempting to distinguish geometric properties of graphs without directly utilizing the cyclic substructures of graphs.
• Question 3: The results obtained from Table 1 consist of accuracies in classifying graph datasets from CSL dataset. We note that the standard deviations are obtained from 4 runs of graph classification with different random seeds. The results from Table 1 show that TIGT is able to fully distinguish cyclic graph datasets presented in CSL dataset. For further information on implementation with CSL dataset, we added Table 7 and Appendix C.3 to the newly updated manuscript, along with supplementary submission which contains a configuration file along with sample experimental results. Using the configuration file, one can implement the graph classification using the code provided on GRIT Github repository. (Here, we set the edge and node features to be all equal to 1). Along with GRIT, we also implemented classifying CSL datasets using GAT and Cy2C-GNNs, the results of which can be observed from Table 1. We find that TIGT outperforms all the baseline models in encapsulating cyclic substructures of graphs in CSL datasets.

We thank the reviewer for pointing out constructive comments which helped us improve the manuscript. Please find our response to the weaknesses of the manuscript pointed out by the reviewer.

• Weakness 1: While we utilized the results from Choi et al. (2023) to prove the theoretical effectiveness in incorporating cyclic structures of graphs, one prominent novelty of this work comes from obtaining an optimal balance among encapsulating the merits of Cy2C-GNNs in incorporating topological invariants of graph datasets, utilizing the advantages of Graph Transformers in effectively analyzing node and edge features of graph datasets, and sustaining the expressive power of GNNs even under increases in number of hidden layers. Our newly added implementations demonstrate that TIGT successfully implements the optimal balance of the aforementioned three conditions. Furthermore, we also added new theoretical results which relates cyclic substructures of graphs with previously studied innate properties of graphs (graph biconnectivity), and analyzes limitations of previously studied techniques which utilize positional encoding of graph datasets.
• Weakness 2: The conditions on pairs of graphs indicated in Theorems 3.3 and 3.4 correspond to pairs of graphs that conventional GNN may not be able to distinguish as non-isomorphic pairs. In fact, if it is the case that any pairs of two graphs does not satisfy the conditions in Theorems 3.3 and 3.4, then conventional GNNs are able to distinguish two graphs as non-isomorphic. As an example, suppose G and H are two graphs whose number of nodes are different but the number of edges are identical. Then there exists a pair of nodes v of G and w of H such that the degree of v and degree of w are not equal to each other. This implies that the universal covers of G and H are not isomorphic, in particular at the nodes of the universal covers of G and H which, respectively, project to nodes v and w. Theorem 3.3 shows that biconnectivity of graphs can be detected from analyzing cyclic substructures of graphs, and Theorem 3.4 shows potential limitations in attempting to distinguish geometric properties of graphs without directly utilizing the cyclic substructures of graphs.
• Weakness 3: As the reviewer suggested, in Table 5 of the updated manuscript, we added a summary of cyclic substructures inherent in the graph datasets utilized in our experiments.
• Weakness 4: In Tables 1 through 4, we added new implementations of graph classifications and graph regressions by utilizing GATs and Cy2C-GNNs. The empirical results obtained in these tables demonstrate that TIGT outperforms both techniques in both classification and regression experiments. Unlike Cy2C-GNNs, TIGT effectively incorporates clique adjacency matrices, global attention layers, and graph information layers, the architectural design of which contributes to outperformance in graph classifications and regressions.
• Weakness 5: In Table 7, we added specifications of hyperparameters and computation time taken in classifying graph datasets from utilizing TIGT and baseline techniques.
• Weakness 6: We thank the reviewer for suggesting new references. We realized that the new references mostly focus on node classification of graph datasets, the results of which are difficult to make direct comparisons to TIGT which focuses primarily on graph classifications. Nevertheless, we added the new references to the introduction of the manuscript.

We thank the reviewer for kindly providing constructive feedbacks and comments to the manuscript. Please find our responses to some of the questions in the list provided below.

• Weakness 1: One prominent novelty of this work comes from obtaining an optimal balance among encapsulating the merits of Cy2C-GNNs in incorporating topological invariants of graph datasets, utilizing the advantages of Graph Transformers in effectively analyzing node and edge features of graph datasets, and sustaining the expressive power of GNNs even under increases in number of hidden layers. Our newly added implementations demonstrate that TIGT successfully implements the optimal balance of the aforementioned three conditions, whereas other GNNS or transformer architectures may not effectively satisfy all three conditions simultaneously.
• Question 1: In Table 1 of the updated manuscript, we added new comparisons of performances of TIGT to other baseline GNNs and transformers. In particular, we added new implementations of classifying graph datasets by utilizing GATs and Cy2C-GNNs. We observe that while Cy2C-GNN performs well with a single hidden layer, its performance in classifying graph datasets decreases as the number of layer increases. In addition, additional implementations demonstrate that GATs cannot effectively distinguish cyclic substructure of graph datasets.
• Weakness 2, Question 2: In Table 7, we added a comparison of the pre-processing computation time, computation time per epoch, and the number of hyperparameters utilized in classifying graph datasets by using Cy2C-GNNs, GPS+LapPE+RWSE, GRIT+RRWP, and TIGT. In Table 4, we also added the empiricial results obtained from Cy2C-GNNs with increased number of hyperparameters. While TIGT exhibits slightly increased computational costs and hyperparameters because it is comprised of various architectural components, we observe that TIGT exhibits meaningful performance boosts in graph classifications and regressions.