1. Although the authors derive PAC-Bayesian bound for GNNs in the transductive setting and show how the interplay between training and testing sets influences the generalization ability, I fail to see the strong connection between the theoretical analysis and the proposed method. The proposed method seems to simply adopt the idea of the self-attention mechanism from the transformer and apply it to the graph. It's not clear to me how the proposed method enhances the generalization for the distant nodes.
2. My major concern about the proposed method is the graph partition as partitioning the graph usually leads to information loss. Though node2vec is used for positional encoding purposes, it only encodes the local topological structure, and it cannot compensate for the lost information between different subgraphs. Based on algorithm 1 in Appendix E, there is no information exchange between different subgraphs. The nodes in a subgraph can only receive the information from other nodes within this subgraph and these nodes are isolated from the nodes from other subgraphs. The performance seems to highly depend on the quality of the graph partition algorithms. However, it's unclear whether different graph partitions will influence the performance of the proposed method or not.
3. Some experimental setups are not quite clear. See questions below.
1. Although the authors derive PAC-Bayesian bound for GNNs in the transductive setting and show how the interplay between training and testing sets influences the generalization ability, I fail to see the strong connection between the theoretical analysis and the proposed method. The proposed method seems to simply adopt the idea of the self-attention mechanism from the transformer and apply it to the graph. It's not clear to me how the proposed method enhances the generalization for the distant nodes.