What Improves the Generalization of Graph Transformer? A Theoretical Dive into Self-attention and Positional Encoding

We thank the reviewer for taking the time to evaluate our manuscript and provide valuable suggestions. Our responses are as follows.

Q1: “It is unclear how the generalization obtained for GCNs differs from the existing ones using e.g., Rademacher complexity, algorithmic stability, and/or PAC-Bayesian. Comparisons or discussions should have been provided to make this clearer.”

A1: Thank you for the question. First, our studied problem is different from the listed existing works. Rademacher complexity [Garg et al.], algorithmic stability [Verma & Zhang], and PAC-Bayesian [Liao et. al.] only focus on the generalization gap, which is the difference between the empirical risk and the population risk function, for a given GCN model with arbitrary parameters and the number of layers [Liao et. al.]. They do not discuss how to train a model to achieve a small training loss. In contrast, our framework involves the convergence analysis of GCN/Graph Transformers using SGD on a class of target functions and the generalization gap with the trained model. The zero generalization we achieve is zero population risk, which means the learned model from the training is guaranteed to have the desired generalization on the testing data.

We have included such discussions in the revision in Appendix E.6.

Liao et al. “A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks. ”ICLR 2021.

Verma & Zhang. “Stability and Generalization of Graph Convolutional Neural Networks. ”KDD 2019.

Garg et al. “ Generalization and representational limits of graph neural networks. ”ICML 2020.

Q2: “Given that graph transformers can be represented as GNNs, is it possible to employ existing generalization analysis of GNNs to investigate graph transformer? Why is the proposed analytical framework more suitable for graph transformer compared with the existing ones?”

A2: This is a great question. For your first question, the answer is yes, and we can use existing generalization analysis of GNNs to study Graph Transformers, but with limitations. As discussed in A1, applying existing techniques, such as Rademacher complexity, algorithmic stability, and PAC-Bayesian could derive a generalization gap based on the bounded norm of the model weights, node features, and Lipstchitz constant of the network. Other existing generalization analyses of GNNs include model estimation [Zhang et al., 2020] and NTK [Du et al., 2019]. However, these methods have intrinsic limitations even if they are extended to study Graph Transformers. For Rademacher complexity, algorithmic stability, and PAC-Bayesian, they do not discuss how to train a model to achieve a small generalization gap. For the model recovery framework, they require a tensor initialization to locate the initial parameter close to the ground truth weight. For NTK, they need an impractical condition of an extremely overparameterized network to linearize the model around the random initialization, and such linearization does not explain the practical success of nonlinear neural networks.

Therefore, for your second question, the reason is that our proposed analytical framework can investigate the training dynamics by quantifying the feature growth per iteration for attention-based networks. With such a framework, we are able to theoretically characterize the mechanism that (1) the self-attention layer converges to a sparse attention map that promotes learning class-relevant features (Lemma 1). This leads to a better sample complexity and generalization performance for Graph Transformers compared to GCNs for some graph datasets (Theorem 4.2). (2) The positional encoding attracts attention to the core neighborhood (Lemma 2), which explains the superiority of training with positional encoding over without positional encoding when nodes are properly sampled (Theorem 4.3).

We have added such discussion in the revision in Appendix E.6. We also compare our framework and existing works on generalization analysis of other Transformers. Our new contribution is that we consider graph structure and trainable positional encoding in the problem formulation and provide the training dynamics and generalization analysis on this more challenging model.

Zhang et al. “Fast learning of graph neural networks with guaranteed generalizability: one-hidden-layer case”, ICML 2020.

Du et al., “Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels”, Neurips 2019.

We thank the reviewer for taking the time to evaluate our manuscript and provide valuable suggestions. Our responses are as follows.

Q1 ([W1] part 1 by the reviewer): "Does the assumption hold for heterophilic networks as well? Performing similar analyses on additional networks such as Actor and PascalVOC-SP-1G used in Section 5.2 would provide further support towards verifying this assumption.”

A1: Thank you for this question and the suggestions. We would like to clarify that our Assumption 1 can be met by some heterophilous and long-range graph datasets. We also want to illustrate that our formulation of the core neighborhood is different from homophily, heterophily, and long-range dependency. Homophily and heterophily are defined by the fraction of edges that connect nodes from the same class. If such fraction is close to $1$, then it is a homophilous graph. Otherwise, it is a heterophilous graph. Long range graphs are graphs where long-range information is needed for the learning tasks. Our definition of the core neighborhood is the neighborhood where the average winning margin between class-relevant and confusion nodes is the largest.

We performed similar experiments on PubMed (homophilous graph), Actor (heterophilous graph), and PascalVOC-SP-1G (long range graph) in Section A.1 (It is Section E.1 in the first version). The experiments include (1) the existence of discriminative nodes for each dataset (2) probing the core distance and justifying that the winning margin on the core distance $\Delta_n(z_m)>0$ (Assumption 1).

To show the existence of discriminative nodes, we first generate Figures 10, 11, 12, and 13 on Cora, PubMed, Actor, and PascalVOC-SP-1G to illustrate that node features of each class can be represented in a low dimension. Then, we use the averaged low-dimensional representation of nodes in each class to identify one discriminative pattern for each class. Tables 2, 3, 4, and 5 indicate that high fractions of nodes are close to each discriminative pattern, which verifies the assumption on the discriminative/non-discriminative nodes.

To investigate the core distance of each dataset, we compute the fraction of nodes of which the label is aligned with the majority vote of the discriminative nodes in the distance-$z$ neighborhood. To extend the definition from binary classification in our formulation to multi-classification tasks, we use the average number of confusion nodes per class in the distance-$z$ neighborhood as $|\mathcal{D}\_{hash}^n\cap\mathcal{N}_z^n|$ ("hash" stands for #), the number of confusion nodes in the distance-$z$ neighborhood of node $n$. Figure 14 shows the value of normalized $\bar{\Delta}(z)$ for $z=1,2,\cdots,12$, where $\bar{\Delta}(z)$ is divided by $|\mathcal{N}_z^n|$ to control the gap of different numbers of nodes in different neighborhoods. The empirical result indicates that the core distances of the four datasets are all 1 given the largest $\bar{\Delta}(z)$ at $z=1$.

We also find the difference of $\bar{\Delta}(z)$ value in distance-$z$ neighborhoods with different graph properties. (1) For the heterophilous graph Actor, the difference between different $\bar{\Delta}(z)$ is very small. (2) For the long-range graph PascalVOC-SP-1G, the value of $\bar{\Delta}(z)$ when $z=12$ is also remarkable. (3) for the homophilous graph PubMed and Cora, the value of $\bar{\Delta}(z)$ when $z=1$ is much larger than the value of $\bar{\Delta}(z)$ when $z$ is large. These show the difference between the four datasets.

We then compute the fraction of nodes that satisfy the winning majority vote, i.e., $\Delta_n(z)>0$. Table 6 shows that at least 85% nodes of the whole graph satisfy that the majority vote wins, which verifies Assumption 1.

Thank you authors for your commitment into preparing the response. The revision clarifies most of my concerns on whether the assumptions made actually hold for real-world graphs, and also provides a clearer picture of the theoretical contributions. After further consideration, I believe the work makes significant contributions towards characterizing the generalizability of graph Transformers, and thus I raise my score to an accept.

We thank the reviewer for taking the time to evaluate our manuscript and provide valuable suggestions. Our responses are as follows.

Q1: “In the introduction, what are nodes with discriminative patterns, non-discriminative patterns, and core neighborhoods?”

A1: We first apologize for the confusion by this sentence. The definition of discriminative patterns is introduced at the beginning of Section 4.2. We assign each node of the graph a pattern $\mu_j, j=1,2,\cdots, M$ with a noise. The nodes of $\mu_1$ or $\mu_2$ are discriminative nodes, while nodes of $\mu_j, 3\leq j\leq M$ are non-discriminative nodes. We assume the existence of a distance-z neighborhood where the ground truth label of every node is decided by such neighborhood. The node is class 1 if there are more nodes with $\mu_1$ patterns than that with $\mu_2$ patterns in the distance-z neighborhood, and the node is class 2 if there are more nodes with $\mu_2$ patterns than that with $\mu_1$ patterns. Such a neighborhood is called the core neighborhood.

For the referred sentence in the Introduction section, to make the presentation concise, we have revised it to “**We focus on a semi-supervised binary node classification problem on structured graph data, where each node feature corresponds to either a discriminative or a non-discriminative pattern, and each ground truth node label is determined by the dominate discriminative pattern in the core neighborhood. **”

Q2: “It seems to be common knowledge that a smaller fraction of erroneous labels, and smaller errors in the initial model mentioned in the paper affect performance, and there doesn't seem to be a strong incentive to adopt a theory to analyze the mechanism in depth.”

A2: Thank you for raising this question. We realize this statement can be confusing. What we should have meant is that this paper provides a formal theoretical characterization of how these factors affect generalization quantitatively. We show that our sample complexity bound in equation 9 is proportional to $1/\gamma_d^2$ and $(1-\epsilon_S)^2$ where $\gamma_d$ is the fraction of discriminative nodes, and $\epsilon_S$ is the confusion rate. This indicates that the graphs with a larger fraction of discriminative nodes or a clearer-cutting vote among discriminative nodes can have a better generalization performance. When $\gamma_d$ is close to 0 and $\epsilon_S$ is close to $1/2$, i.e., the winning margin of the majority vote in the core neighborhood is small, the sample complexity bound proportional to $1/(\gamma_d-(\sigma+\tau))^2$ is large, which means the generalization is sensitive to the error in the initial model. A good pre-trained model is desired in this case. Our result also characterizes that the fraction of erroneous labels $p$ makes the sample complexity and the required number of iterations increase rapidly in an order of $(1-2p)^{-1/2}$ when $p$ is very close to $1/2$.

To address such concern, we have revised the related sentences in the abstract as “This paper provides the quantitative characterization of the sample complexity and number of iterations for convergence dependent on the fraction of discriminative nodes, the dominant patterns, the fraction of erroneous labels, and the initial model errors. “

Thank you for the evaluation. Our responses are as follows.

Q1: it is assumed that the dataset is balanced, i.e., the gap between the numbers of positive and negative labels is at most $O(\sqrt{N})$. I can hardly believe this will always happen for useful practical scenarios, and existing theoretical results for transductive learning, such as [1-2] (just name a few), do not require such an assumption.

A1: We would like to clarify that this assumption serves as a commonly used assumption in the optimization and generalization analysis of neural networks [Shi et al., 2022, Brutzkus et al., 2022, Karp et al., 2021, Li et al., 2023] using the feature learning framework. This condition is also assumed in a recent work [Zhang et al., 2023] in ICLR 2023 on GNN training using feature learning analysis. These are published works on top ML/AI conferences in the last three years. Note that $O(\sqrt{N})$ could be in practical datasets. Table 9 shows that for Cora and Actor, this condition holds since the largest gap between the average number of nodes and the number of any class of nodes is smaller than $O(\sqrt{N})$, where we choose $O(\sqrt{N})=10\sqrt{N}$.

Second, the references [1,2] focus on a different problem from ours. [1,2] only study the generalization gap, which is the difference between the empirical risk and the population risk function. They do not discuss how to train a model to achieve a small training loss, and thus needs fewer assumptions. In contrast, our framework involves not only the generalization gap but also an extra convergence analysis of GCN/Graph Transformers using SGD and Hinge loss on a class of target functions. The zero generalization we achieve is zero population risk, which means the learned model from the SGD training is guaranteed to have the desired generalization on the testing data. Our assumption of a balanced dataset is used for the optimization analysis of Graph Transformers. We added [1,2] in Appendix E.6 for a comparison in our revision.

Third, in our manuscript, we always say that our generalization analysis holds with our data model. For example, in the Abstract, we state “Focusing on a graph data model with discriminative nodes that determine node labels and non-discriminative nodes that are class-irrelevant, we characterize the sample complexity …”; in the Introduction, we state “We focus on a semi-supervised binary node classification problem on structured graph data, where each node feature corresponds to either a discriminative or a non-discriminative pattern, and each ground truth node label is determined by the dominant discriminative pattern in the core neighborhood.”

Brutzkus et al., “An Optimization and Generalization Analysis for Max-Pooling Networks ”, UAI 2020.

Karp et al., “Local Signal Adaptivity: Provable Feature Learning in Neural Networks Beyond Kernels”, Neurips 2022

Shi et al., “A theoretical analysis on feature learning in neural networks: Emergence from inputs and advantage over fixed features”, ICLR 2022.

Li et al., “A theoretical understanding of shallow vision transformers: Learning, generalization, and sample complexity”, ICLR 2023.

Zhang et al., “Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networks”, ICLR 2023.