Size Generalization of Graph Neural Networks on Biological Data:
  Insights and Practices from the Spectral Perspective
We investigate size-induced distribution shifts in graphs and assess their
impact on the ability of graph neural networks (GNNs) to generalize to larger
graphs relative to the training data. Existing literature presents conflicting
conclusions on GNNs' size generalizability, primarily due to disparities in
application domains and underlying assumptions concerning size-induced
distribution shifts. Motivated by this, we take a data-driven approach: we
focus on real biological datasets and seek to characterize the types of
size-induced distribution shifts. Diverging from prior approaches, we adopt a
spectral perspective and identify that spectrum differences induced by size are
related to differences in subgraph patterns (e.g., average cycle lengths).
While previous studies have identified that the inability of GNNs in capturing
subgraph information negatively impacts their in-distribution generalization,
our findings further show that this decline is more pronounced when evaluating
on larger test graphs not encountered during training. Based on these spectral
insights, we introduce a simple yet effective model-agnostic strategy, which
makes GNNs aware of these important subgraph patterns to enhance their size
generalizability. Our empirical results reveal that our proposed
size-insensitive attention strategy substantially enhances graph classification
performance on large test graphs, which are 2-10 times larger than the training
graphs, resulting in an improvement in F1 scores by up to 8%.
Gaotang Li, Danai Koutra, Yujun Yan
Size Generalizability of Graph Neural Networks on Biological Data: Insights and Practices from the Spectral Perspective

###### Abstract

We investigate the question of whether the knowledge learned by graph neural networks (GNNs) from small graphs is generalizable to large graphs in the same domain. Prior works suggest that the distribution shift, particularly in the degree distribution, between graphs of different sizes can lead to performance degradation in the graph classification task. However, this may not be the case for biological datasets where the degrees are bounded and the distribution shift of degrees is small. Even with little degree distribution shift, our observations show that GNNs' performance on larger graphs from the same datasets still degrades, suggesting other causes. In fact, there has been a lack of exploration in real datasets to understand the types and properties of distribution shifts caused by various graph sizes. Furthermore, previous analyses of size generalizability mostly focus on the spatial domain. To fill these gaps, we take the spectral perspective and study the size generalizability of GNNs on biological data. We identify a distribution shift between small and large graphs in the eigenvalues of the normalized Laplacian/adjacency matrix, indicating a difference in the global node connectivity, which is found to be correlated with the node closeness centrality. We further find that despite of the variations in global connectivity, graphs of different sizes share similar local connectivity, which can be utilized to improve the size generalizability of GNNs. Based on our spectral insights and empirical observations, we propose a model-agnostic strategy, SIA, which uses size-irrelevant local structural features, i.e., the local closeness centrality of a node, to guide the learning process. Our empirical results demonstrate that our strategy improves the graph classification performance of various GNNs on small and large graphs when training with only small graphs.

## 1 Introduction

We focus on the size generalizability of graph neural networks on biological data. While numerous GNNs [17; 27; 13; 38; 34; 19] have exhibited exceptional performance in graph classification tasks and can handle graphs of varying size, there has been inadequate research into the ability of GNNs to generalize effectively from small to large graphs. Size generalizability is a critical concern in various fields. For instance, in graph algorithmic reasoning, neural networks (NN) learn complex
algorithms from small graph examples and generalize that reasoning to larger graphs, as obtaining exact solutions for larger graphs is challenging. In the biological domain, datasets can vary in graph size, from small atom-based structures to large compounds with thousands of atoms. It is important to assess if the learned knowledge is influenced by graph size, as size-dependent information could adversely affect performance when using pre-training strategies [15].

Many prior works [36; 7; 5] have observed performance degradation when there exists a size shift between the training and test data. However, it remains unclear: what structural properties will change with the graph size? The answer to this question depends on the data domain. For instance, local degree patterns in social networks may vary with graph size [36] while the node degrees in biological networks are bounded and the difference in degree distributions between small and large graphs is small (Section 5.2). Additionally, the global connectivity of nodes in biological graphs may change with the graph size. Many prior works [7; 5; 35], however, lack sufficient exploration and verification on real datasets to understand the types and properties of distribution shifts caused by various graph sizes. Thus, it is unclear what distribution shifts they target at and what data domain their methods can improve the size generalizability on. In this paper, we obtain two important observations from biological data: (1) the eigenvalue distributions, obtained from the normalized Laplacian/adjacency matrix, vary with the graph size. The differences in the eigenvalue distributions reflect the variations in the global connectivity of the nodes, which are associated with the node closeness centrality; and (2) graphs with different sizes have similar distributions of local node connectivity, which can be measured by the local closeness centrality computed from the subgraphs induced from local neighborhoods. We use these observations to guide our design of a Size-Insensitive Attention (SIA) strategy, which is model agnostic and helps improve the size generalizability of many GNN models.

Furthermore, most analyses in prior works [36; 7; 5] focus on the spatial domain. In this paper, we take the spectral perspective to understand why GNNs can be sensitive to size shift, and use the insights from the spectral domain to understand what structural properties change with the graph size. In sum, our paper makes the following contributions:

* **New Observations.** We identify the types and properties of distribution shifts caused by various graph sizes in biological networks.
* **Spectral Analyses.** Unlike prior works in size generalizability, we take the spectral perspective and use the spectral insights to analyze the structural change with the graph size.
* **Model Agnostic Strategy.** Based on our spectral insights and empirical observations, we propose a model agnostic strategy, SIA, which uses size-irrelevant local structural features, i.e., the local closeness centrality of a node, to guide the learning process.

## 2 Notations and Preliminaries

In this section, we introduce the definitions and notations that are used throughout the paper. Let \(\mathcal{G}(\mathcal{V},\mathcal{E})\) be an undirected and unweighted graph with \(N\) nodes, where \(\mathcal{V}\) denotes the node set, and \(\mathcal{E}\) denotes the edge set. The \(h\)-hop neighborhood of a node \(v_{i}\) is defined as the set of all nodes that are at a distance of \(h\) or less from the node \(v_{i}\): \(\mathcal{N}_{i}^{h}=\{v_{j}|\mathtt{dist}(v_{j},v_{i})\leq h\}\). We use \(\mathbf{A}\) to represent the adjacency matrix of the graph, \(\mathbf{D}\) to represent the degree matrix whose \(i\)th diagonal element is the degree of node \(v_{i}\).

### Closeness Centrality

**Global Closeness Centrality.** Global closeness centrality [3] of a node \(v_{i}\) measures how long it will take information to spread from \(v_{i}\) to other nodes in the network. It is calculated as the reciprocal of the average length of the shortest paths between \(v_{i}\) and all other nodes in the graph. To account for graphs with more than one connected component, we adopt the following closeness definition in [26]:

\[C(v_{i})=\frac{n-1}{N-1}\frac{n-1}{\sum_{j=1}^{n-1}\mathtt{dist}(v_{i},v_{j})},\]

where \(n\) is the number of reachable nodes from \(v_{i}\).

\(h\)**-hop Closeness Centrality.**\(h\)-hop closeness centrality is a variant of closeness centrality proposed in this paper, which aims to capture the local connectivity of the nodes. It is computed using the
subgraphs induced from \(h\)-hop neighborhood of the node \(v_{i}\):

\[C^{(h)}(v_{i})=\frac{|\mathcal{N}_{i}^{h}|-1}{\sum_{v_{j}\in\mathcal{N}_{i}^{h},v _{j}\neq v_{i}}\mathtt{dist}(v_{i},v_{j})}\]

### Graph Learning Task

In this paper, we focus on the graph classification task, where each node \(v_{i}\) is associated with a feature vector \(\mathbf{x}_{i}^{(0)}\), and the feature matrix \(\mathbf{X}^{(0)}\) is constructed by arranging the node feature vectors as rows. When using a GNN for the graph classification task, we further denote the node representation matrix at the \(l\)-th layer as \(\mathbf{X}^{(l)}\), and the representation of node \(v_{i}\) as \(\mathbf{x}_{i}^{(l)}\).

**Supervised Graph Classification.** Each graph \(\mathcal{G}_{i}\) is associated with a ground truth label \(y_{i}^{\mathcal{G}}\) sampled from a label set \(\hat{\mathcal{L}}\). Given a subset of labeled graphs (from a label set \(\hat{\mathcal{L}}\)), the goal is to learn a mapping \(f^{\mathcal{G}}:(\mathbf{A},\mathbf{X}^{(0)})_{i}\mapsto y_{i}^{\mathcal{G}}\) between each graph \(\mathcal{G}_{i}\) and its ground truth label \(y_{i}^{\mathcal{G}}\in\hat{\mathcal{L}}\). The graph classification loss is given by \(L=\frac{1}{|\mathcal{G}_{\text{train}}|}\sum_{\mathcal{G}_{i}\in\mathcal{G}_{ \text{train}}}\mathtt{CrossEntropy}\) (\(\mathbf{x}^{\mathcal{G}_{i}}\), \(y_{i}^{\mathcal{G}}\)), where \(\mathcal{G}_{\text{train}}\) is the training graph set and \(\mathbf{x}^{\mathcal{G}_{i}}\) is the representation of graph \(\mathcal{G}_{i}\).

### Graph Neural Networks for Graph Classification

GNNs can be designed from either the spatial perspective or the spectral perspective. Despite the difference in the design perspectives, a recent work [1] has shown that spectral GNNs and spatial GNNs are related and that spectral analysis of GNNs' behavior can provide a complementary point of view to understand GNNs in general.

**Spatial Perspective.** Many GNNs [17; 31; 27; 13] use the message passing framework [12], which is consisted of three steps: neighborhood propagation and aggregation, combination and global pooling. The node representations at \(l\)-th layer are given by: \(\mathbf{x}_{i}^{(l+1)}=\mathtt{Combine}(\mathtt{Aggregate}(\mathbf{x}_{j}^{(l) },v_{j}\in\mathcal{N}_{i}^{1},v_{j}\neq v_{i}),\mathbf{x}_{i}^{(l)})\), where the function Aggregate can be \(\mathtt{Sum}\)[31], Average[17], or other learned aggregating functions [27]; and the function Combine can be \(\mathtt{Concat}\)[13] or \(\mathtt{Average}\)[17]. The graph representation is obtained from the node representations at the last layer: \(\mathbf{x}^{\prime\prime}=\mathtt{Pooling}\) (\(\{\mathbf{x}_{i}^{(\text{Last})}\}\)), where the \(\mathtt{Pooling}\) function is performed on the set of all the node representations, and it can be \(\mathtt{Global\_mean}\) or \(\mathtt{Global\_max}\) or other more complex pooling functions [37; 18].

**Spectral Perspective.** Spectral GNNs [6; 11; 21] utilize the spectral properties of a propagation matrix \(\mathbf{T}\) to perform the graph classification. The propagation matrix \(\mathbf{T}\) is usually a function of the adjacency matrix \(\mathbf{A}\), such as the normalized adjacency matrix \(\mathbf{T}=(\mathbf{D}+\mathbf{I})^{-1/2}(\mathbf{A}+\mathbf{I})(\mathbf{D}+ \mathbf{I})^{-1/2}\), or the normalized graph Laplacian matrix \(\mathbf{T}=\mathbf{I}-\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}\). We consider an undirected graph with a real and symmetric adjacency matrix. Consequently, the propagation matrix \(\mathbf{T}\) is also real and symmetric. Then we can perform the eigendecomposition on the propagation matrix \(\mathbf{T}\): \(\mathbf{T}=\mathbf{U}\mathbf{A}\mathbf{U}^{T}\), where \(\mathbf{U}\) is an orthogonal matrix whose columns \(\mathbf{U}_{i}\) are orthonormal and are the eigenvectors of \(\mathbf{T}\); \(\mathbf{\Lambda}\) is a matrix whose diagonal elements are the eigenvalues of \(\mathbf{T}\), sorted from large to small by their absolute values. The set of eigenvectors \(\{\mathbf{U}_{i}\}\) form the orthonormal basis of \(\mathbb{R}^{n}\). The goal of a spectral GNN is to learn a proper spectral filter: \(f(\mathbf{\Lambda})=c_{0}\mathbf{I}+c_{1}\mathbf{\Lambda}+c_{2}\mathbf{ \Lambda}^{2}+\cdots+c_{i}\mathbf{\Lambda}^{i}+\cdots\), where \(c_{i}\) are the learnable coefficients. The convolution at each layer can be viewed as or is equivalent to: \(\mathbf{X}^{(l+1)}=\sigma(\mathbf{U}f(\mathbf{\Lambda})\mathbf{U}^{T}\mathbf{X }^{(l)}\mathbf{W}^{(l)})\), where \(\mathbf{W}^{(l)}\) is a learnable weight matrix, and \(\sigma(\cdot)\) is a nonlinear function (e.g., ReLU). Similar to the spatial GNNs, a global pooling is performed after the last convolution layer to obtain a graph representation for the graph classification task.

## 3 Size Generalizability from the Spectral Perspective

In this section, we take a spectral perspective to analyze the factors that affect the size generalizability of a GNN. At a high level, we study how the graph representation correlates with the graph size.

The output of a GNN at the \((l+1)\)-th layer is given by: \(\mathbf{X}^{(l+1)}=\sigma(\mathbf{U}f(\mathbf{\Lambda})\mathbf{U}^{T}\mathbf{ X}^{(l)}\mathbf{W}^{(l)})\) (Section 2). To ease our analysis, we rewrite \(\mathbf{U}\), \(\mathbf{\Lambda}\) and \(\mathbf{X}^{(l)}\) as: \(\mathbf{U}=[\mathbf{U}_{1},\mathbf{U}_{2},\cdots,\mathbf{U}_{N}]\), \(\mathbf{\Lambda}=\mathtt{Diag}([\lambda_{1},\lambda_{2},\cdots,\lambda_{N}])\), and \(\mathbf{X}^{(l)}=[\mathbf{X}_{1}^{(l)},\mathbf{X}_{2}^{(l)},\cdots,\mathbf{X}_ {D}^{(l)}]\), respectively. \(\mathbf{U}_{i}\) is the \(i\)-th column
vector of \(\mathbf{U}\), \(\lambda_{i}\) is the \(i\)-th largest eigenvalue, \(\texttt{Diag}(\cdot)\) creates a matrix with the vector as its diagonal elements, \(\mathbf{X}_{i}^{(l)}\) is the \(i\)-th column vector of \(\mathbf{X}^{(l)}\), and \(D\) is the feature dimension at the \(l\)-th layer.

\[\begin{split}\mathbf{X}^{(l+1)}&=\sigma([\mathbf{ U}_{1},\mathbf{U}_{2},\cdots,\mathbf{U}_{N}]\cdot\texttt{Diag}([f(\lambda_{1}),f( \lambda_{2}),\cdots,f(\lambda_{N})])\cdot([\mathbf{U}_{1},\mathbf{U}_{2}, \cdots,\mathbf{U}_{N}])^{T}\\ &\cdot[\mathbf{X}_{1}^{(l)},\mathbf{X}_{2}^{(l)},\cdots,\mathbf{ X}_{D}^{(l)}]\cdot\mathbf{W}^{(l)}\\ &=\sigma([f(\lambda_{1})\mathbf{U}_{1},f(\lambda_{2})\mathbf{U}_ {2},\cdots,f(\lambda_{N})\mathbf{U}_{N}]\cdot([\mathbf{U}_{1},\mathbf{U}_{2}, \cdots,\mathbf{U}_{N}])^{T}\\ &\cdot[\mathbf{X}_{1}^{(l)},\mathbf{X}_{2}^{(l)},\cdots,\mathbf{ X}_{D}^{(l)}]\cdot\mathbf{W}^{(l)}.\end{split} \tag{1}\]

Since \(\{\mathbf{U}_{i}:i=1,\cdots,N\}\) are the orthonormal basis of \(\mathbb{R}^{N}\), \(\mathbf{X}_{i}^{(l)}\) can be expressed as a linear combination of \(\{\mathbf{U}_{i}\}\). Thus, suppose \(\mathbf{X}_{i}^{(l)}=\sum_{j=1,2,\cdots,N}\alpha_{j}^{i}\mathbf{U}_{j}\), then Equation 1 can be rewritten as:

\[\begin{split}\mathbf{X}^{(l+1)}&=\sigma([f(\lambda_ {1})\mathbf{U}_{1},f(\lambda_{2})\mathbf{U}_{2},\cdots,f(\lambda_{N})\mathbf{ U}_{N}]\cdot([\mathbf{U}_{1},\mathbf{U}_{2},\cdots,\mathbf{U}_{N}])^{T}\\ &\cdot[\sum_{j=1,2,\cdots,N}\alpha_{j}^{1}\mathbf{U}_{j},\cdots, \sum_{j=1,2,\cdots,N}\alpha_{j}^{i}\mathbf{U}_{j},\cdots]\cdot\mathbf{W}^{(l )})\\ &=\sigma\left([f(\lambda_{1})\mathbf{U}_{1},f(\lambda_{2})\mathbf{ U}_{2},\cdots,f(\lambda_{N})\mathbf{U}_{N}]\cdot\begin{bmatrix}\alpha_{1}^{1}& \alpha_{1}^{2}&\cdots&\alpha_{1}^{D}\\ \alpha_{1}^{2}&\alpha_{2}^{2}&\cdots&\alpha_{2}^{D}\\ \cdots&\cdots&\cdots&\cdots\\ \alpha_{N}^{1}&\alpha_{N}^{2}&\cdots&\alpha_{N}^{D}\end{bmatrix}\cdot\mathbf{W }^{(l)}\right)\\ &=\sigma([\sum_{j=1,\cdots,N}f(\lambda_{j})\alpha_{j}^{1}\mathbf{U}_{j}, \sum_{j=1,\cdots,N}f(\lambda_{j})\alpha_{j}^{2}\mathbf{U}_{j},\cdots,\sum_{j=1,\cdots,N}f(\lambda_{j})\alpha_{j}^{D}\mathbf{U}_{j}]\cdot\mathbf{W}^{(l)}). \end{split} \tag{2}\]

We know that \(\alpha_{j}^{i}=\mathbf{U}_{j}^{T}\cdot\mathbf{X}_{i}^{(l)}=\texttt{COSINE}( \mathbf{U}_{j},\mathbf{X}_{i}^{(l)})\cdot\|\mathbf{X}_{i}^{(l)}\|_{2}=\texttt {COSINE}(\mathbf{U}_{j},\mathbf{X}_{i}^{(l)})\cdot\frac{\|\mathbf{X}_{i}^{(l) }\|_{2}}{\sqrt{N}}\cdot\sqrt{N}\). Then Equation 2 can be rewritten as:

\[\begin{split}\mathbf{X}^{(l+1)}&=\sigma([\sum_{j=1, \cdots,N}f(\lambda_{j})\texttt{COSINE}(\mathbf{U}_{j},\mathbf{X}_{1}^{(l)}) \cdot\frac{\|\mathbf{X}_{1}^{(l)}\|_{2}}{\sqrt{N}}\cdot(\sqrt{N}\cdot\mathbf{U }_{j}),\\ &\cdots,\sum_{j=1,\cdots,N}f(\lambda_{j})\texttt{COSINE}(\mathbf{ U}_{j},\mathbf{X}_{D}^{(l)})\cdot\frac{\|\mathbf{X}_{D}^{(l)}\|_{2}}{\sqrt{N}} \cdot(\sqrt{N}\cdot\mathbf{U}_{j})]\cdot\mathbf{W}^{(l)}).\end{split} \tag{3}\]

The final graph representation is obtained through a global pooling (Section 2), where a set function is applied to each feature dimension. To ensure that the graph representation is irrelevant to the graph size, it is crucial for each column of \(\mathbf{X}^{(l+1)}\) to be unaffected by the size. If the distributions of eigenvalues (\(\lambda_{j}\)) and scaled eigenvectors (\(\sqrt{N}\cdot\mathbf{U}_{j}\)), as well as the scalar \(\frac{\|\mathbf{X}_{i}^{(l)}\|_{2}}{\sqrt{N}}\), are uncorrelated with the graph size, then the graph representation will be size-invariant. It is worth noting that \(\mathbf{X}_{i}^{(l)}\) contains \(N\) elements and its 2-norm scales with \(\sqrt{N}\); and \(\|\mathbf{U}_{j}\|_{2}=1\) and its elements diminish with \(\sqrt{N}\). Hence, we account for the scaling factor \(\sqrt{N}\) in both terms. However, as demonstrated in Section 5.2 and appendix D, the distributions of eigenvalues and scaled eigenvectors in real biological graphs are influenced by the graph size. This poses a challenge for the size generalization of GNNs. Importantly, the difference in eigenvalue distributions cannot be attributed to the value range [4], as the eigenvalues of a normalized Laplacian matrix and adjacency matrix are constrained within the intervals [0,2] and [-1,1] respectively.

## 4 Methodology

Before presenting our method, we highlight two observations discovered in biological networks, which will be thoroughly explained in Section 5. These observations serve as the motivation behind our development of a size-insensitive attention mechanism.

* **Observation 1**: The differences in the eigenvalue distributions reflect the variations in the global connectivity of the nodes, which are associated with the node closeness centrality.
* **Observation 2**: Graphs with different sizes have similar distributions of local node connectivity, which can be measured by the local closeness centrality computed from the subgraphs induced from local neighborhoods.

Motivated by Observation 2, our design aims at improving size generalizability by incorporating size-insensitive local structural features. Intuitively, we aim to utilize these structural features to filter out the nodes that increase in quantity with the graph size but are less relevant to the labels. Attention is a suitable mechanism in our setting as it can filter out irrelevant information [18] and be integrated with structural features. However, as noted in [28; 33], attention weights gradually lose fidelity with larger graphs. Therefore, our design focuses on two main challenges: (1) designing size-insensitive local structural features and (2) reducing the impact of graph size on the attention weights.

**Structural Feature Design.** Inspired by Observation 2, we use local closeness centrality as the node features. In more detail, we compute the local closeness centrality of a node \(v_{i}\) from its \(h\)-hop neighborhoods \(\mathcal{N}_{i}^{h}\), where \(h\) is the largest neighborhood size to maintain size-insensitivity (Section 5.4). To enrich the features [10], we further compute the maximum, minimum, average, and standard deviation of \(h\)-hop closeness for the nodes in \(v_{i}\)'s immediate neighborhood. In this way, for each node \(v_{i}\), we manually construct a 5-dimensional feature vector \(\mathbf{c}_{i}\) such that

\[\mathbf{c}_{i}=[C^{h}(v_{i}),\mathtt{max}(\{C^{h}(v_{j})\}),\mathtt{min}(\{C^ {h}(v_{j})\}),\mathtt{avg}(\{C^{h}(v_{j})\}),\mathtt{std}(\{C^{h}(v_{j})\})] ^{\top},v_{j}\in\mathcal{N}_{i}^{1} \tag{4}\]

**Size-insensitive Structural Attention.** We use the structural feature matrix \(\mathbf{C}=[\mathbf{c}_{1},\ldots,\mathbf{c}_{N}],\mathbf{c}_{i}\in\mathbb{R} ^{5}\) for attention. However, attention weights often diminish with increasing graph size due to the utilization of \(\mathtt{Softmax}\). To address this issue, we propose scaling the attention weights by the graph size and employing \(\mathtt{Global\_max}\) as the global pooling operation to mitigate the impact of graph size. Mathematically, our final graph representation is given by:

\[\mathbf{k}=\mathtt{Softmax}(\mathbf{w}_{A}^{\top}\mathbf{C})\cdot N,\quad \mathbf{x}^{\mathcal{G}}=\mathtt{Global\_max}(\mathtt{Diag}(\mathbf{k})\cdot \mathbf{X}^{(\text{Last})}) \tag{5}\]

where \(\mathbf{w}_{A}^{\top}\) is a learnable vector, and \(\mathtt{Diag}(\cdot)\) creates a diagonal matrix using the vector as its elements.

We perform a comprehensive ablation study on Appendix F to showcase the effectiveness of our feature selection. Our findings reveal that local closeness alone can enhance size generalizability to some extent. However, when incorporating more enriched features, the improvements become more consistent and pronounced.

## 5 Experiments

### Overview of the Experimental Setup

In our experiments, we use three pre-processed biological datasets (BBBP, BACE, and PROTEINS) from the Open Graph Benchmark [16] and TuDataset [23] to perform graph classification. More details about the datasets are provided in Appendix A.

Data Preprocessing and Important Training DetailsIn order to analyze size generalizability, we have four splits for each dataset: train, validation, small_test, and large_test, where large_test contains graphs with significantly larger sizes. We generate the splits as follows. First, we sort the samples in the dataset by their size. Next, We take the train, validation, and small_test split from the 50% smallest graphs in the dataset. An intuitive way of getting the large_split is to take the top k largest graphs. However, doing so would result in severe label skewness (class imbalances) between the small_test and the large_test as demonstrated by Table 4 in Appendix B. To avoid such a severe distribution shift, we select the same number of graphs per class as in the small_test subset, starting from the largest graph within each class. In this way, we ensure the label distribution between small_test and large_test is the same. Nevertheless, the smallest 50% samples still have significant **class imbalance**. To address this issue, we use upsampling during training throughout the experiments, and we use **F1** as the metric to measure the model performance. More details about data preprocessing, hyperparameters, and training can be found in Appendix B and Appendix C.
### Dependence of Structural Properties on Graph Size

In this subsection, we aim to address the question: "What structural properties change with the graph size?" To explore this, we focus on two structural properties of the graphs: degree distribution and eigenvalue distribution. We present their relationship with the graph size in Figure 1.

Figure 1 illustrates the pairwise distances of the graphs arranged in ascending order of size, where the distances are calculated using the Wasserstein distance [29]. We measure the empirical distributions of degrees (Figure 0(a)) and eigenvalues (Figure 0(b)), respectively, to compute these distances. The eigenvalues are obtained from the normalized adjacency matrix as suggested in [17]: \(\mathbf{T}=(\mathbf{D}+\mathbf{I})^{-1/2}(\mathbf{A}+\mathbf{I})(\mathbf{D}+ \mathbf{I})^{-1/2}\). We have similar observations for normalized Laplacian matrix. Note that the eigenvalues do not scale with the graph size, and they are bounded between [-1,1]. Dark blue represents a small distance (high similarity) while light red represents a large distance (low similarity). We find that Figure 0(a) does not have a clear pattern and thus the graph distance measured by degree distributions does not show a clear correlation with the graph size. In contrast, there is a wide blue band along the diagonal in the three subplots in Figure 0(b), corresponding to the three datasets in our analysis. This indicates that graphs of similar sizes have more similar eigenvalue distributions than graphs of different sizes. It suggests a strong correlation between the eigenvalue distributions and the graph size. To verify the analysis quantitatively, we compute the distance of graphs with similar sizes and graphs of different sizes in Table 1. Graphs of similar sizes include 20

\begin{table}
\begin{tabular}{l|c c c|c c c} \hline \hline \multicolumn{5}{c}{**Degree Distribution Difference**} & \multicolumn{5}{c}{**Eigenvalue Distribution Difference**} \\ \hline
**Datasets** & **Different sizes** & **Similar sizes** & **Relative difference** & **Different sizes** & **Similar sizes** & **Relative difference** \\ \hline
**BBBP** & 0.039 & 0.035 & 12.1\% & 0.281 & 0.091 & 209\% \\
**BACE** & 0.027 & 0.024 & 14.7\% & 0.204 & 0.073 & 177\% \\
**PROTEINS** & 0.047 & 0.041 & 14.8\% & 0.379 & 0.130 & 192\% \\ \hline \hline \end{tabular}
\end{table}
Table 1: Average Wasserstein distance between graphs of similar sizes and graphs of different sizes based on **degree** and **eigenvalue** distributions, respectively. The relative difference is computed by the difference of the Wasserstein distance normalized by the Wasserstein distance of similar graphs.

Figure 1: Graph distance is quantified using the Wasserstein distance for degree (a) and eigenvalue (b) distributions, respectively. Graphs are sorted from small to large, and the (i,j)-th pixel in the plot represents the distance between the i-th and j-th graphs. Dark blue represents a small distance (high similarity), while light red represents a large distance (low similarity). We find that **degree distributions do not show a clear correlation with the graph size** and **eigenvalue distributions show a strong correlation with the graph size**.
graphs whose size is closest to the graph of interest, and graphs of different sizes are the remaining graphs. From the table, we find that (1) the Wasserstein distance of degree distributions between the graphs of different sizes are slightly larger (around 15%) than the distance between graphs of similar sizes; and (2) the Wasserstein distance of eigenvalue distributions between the graphs of different sizes are significantly larger than the distance between graphs of similar sizes. This implies that the discrepancy of degree distributions is not the main challenge to the size generalizability of GNNs on real biological graphs. Furthermore, based on the results and the analysis in Section 3, the correlation between the eigenvalue distributions and the graph size results in the correlation of the final graph representation and the graph size, which prevents GNNs from generalizing over different sizes.

### Observation 1

In this subsection, we present our first observation that the discrepancies of the eigenvalue distributions reflect the differences of global connectivity of the nodes, which are correlated with the node closeness centrality. Our intuition is that the structural connectivity of the graph is often related to the eigenvalues of the normalized Laplacian matrix. For example, the algebraic multiplicity of eigenvalue 0 represents the number of connected components in the graph [9]; the cheeger constant [8], which measures the "bottle neck" of the graph, is related to the spectral gap of the graph. To analyze their relationship, we compute the empirical distribution of node closeness centrality for each graph (Section 2) as an indicator of global node connectivity and examine its correlation with the eigenvalue distribution. To elaborate, we randomly select 200 pairs of graphs. Each pair of graphs yields two distances: one calculated from the eigenvalue distributions and the other from the closeness distributions. We then map each graph pair to a point whose coordinates represent the two distances. The scatter plots for three datasets are depicted in Figure 2. The \(x\)-axis represents the closeness distance, and the \(y\)-axis represents the eigenvalue distance. We find that there is a clear correlation between the two variables in all the plots we draw. To verify it quantitatively, we compute the Pearson correlation between the two distances, and the result is presented in Figure 2. To conclude, the closeness distribution is highly or moderately correlated with the eigenvalue distributions in real-world biological datasets.

### Observation 2

In this subsection, we present our second observation that graphs with different sizes have similar distributions of local node connectivity. We measure the local node connectivity by computing the closeness of a node in its local neighborhoods. In the following analysis, we use the BACE dataset as an example, and similar analyses are conducted for the other two datasets in Appendix E.

Following the same procedures in Section 5.2, Figure 3 shows the distances of sorted graphs, where the distance is measured by the Wasserstein distance between the empirical distributions of \(h\)-hop local closeness. We can see that in the two-hop and three-hop plots, small and large graphs share similar distributions of local closeness. In contrast, there is a clear wide blue band along the diagonal in the four-hop plot, indicating that the graph distance measured by four-hop local closeness correlates with the graph size. To verify the analysis quantitatively, we compute the distance of graphs of similar sizes and graphs of different sizes in Table 2. We follow the same definitions in Section 5.2. We

Figure 2: Correlation between the distances measured by eigenvalue distributions and closeness distributions on BBBP, BACE, and PROTEINS datasets. The closeness distribution is highly or moderately correlated with the eigenvalue distribution.
observe that the relative difference between graphs of similar sizes and graphs of different sizes are relatively small for two-hop and three-hop local closeness, but becomes significant for four-hop local closeness. This quantitative result verifies the plot shown in Figure 3. We thus conclude that three-hop is the maximum neighborhood size in the BACE dataset that preserves the size-insensitivity of the local closeness features. As a consequence, we choose \(h=3\) for BACE.

\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Number of Hops** & **Different sizes** & **Similar sizes** & **Relative Difference** \\ \hline
**2-hop** & 0.314 & 0.268 & 17.1\% \\
**3-hop** & 0.368 & 0.265 & 38.5\% \\
**4-hop** & 0.387 & 0.201 & 92.2\% \\ \hline \hline \end{tabular}
\end{table}
Table 2: Average Wasserstein distance between graphs of similar sizes and graphs of different sizes based on **h-hop local closeness** for BACE. The relative difference is computed by the difference of the average Wasserstein distance normalized by the average Wasserstein distance of similar graphs.

\begin{table}
\begin{tabular}{l|c c|c c|c c} \hline \hline \multicolumn{2}{c}{**Datasets**} & \multicolumn{2}{c}{**BBBP**} & \multicolumn{2}{c}{**BACE**} & \multicolumn{2}{c}{**PROTEINS**} \\ \hline
**Models** & **Small** & **Large** & **Small** & **Large** & **Small** & **Large** \\ \hline
**MLP** & \(92.66\pm_{172}\) & \(58.39\pm_{4.63}\) & \(61.75\pm_{4.64}\) & \(21.18\pm_{9.68}\) & \(36.15\pm_{2.28}\) & \(21.55\pm_{1.34}\) \\
**MLP+SAGPool (threshold)** & \(88.3\pm_{2.84}\) & \(59.02\pm_{17.70}\) & \(61.03\pm_{2.38}\) & \(40.66\pm_{4.81}\) & \(67.78\pm_{7.11}\) & \(13.04\pm_{5.02}\) \\
**MLP+SIA** & \(91.07\pm_{0.88}\) & \(59.43\pm_{3.0}\) & \(64.48\pm_{12.22}\) & \(31.36\pm_{15.19}\) & \(45.02\pm_{8.18}\) & \(36.42\pm_{13.83}\) \\ \hline
**GCN** & \(90.66\pm_{1.28}\) & \(64.45\pm_{1.38}\) & \(64.52\pm_{2.57}\) & \(27.08\pm_{13.66}\) & \(72.35\pm_{2.58}\) & \(40.49\pm_{3.22}\) \\
**GCN+SAGPool (threshold)** & \(88.51\pm_{2.94}\) & \(66.46\pm_{16.11}\) & \(52.94\pm_{7.99}\) & \(47.87\pm_{7.6}\) & \(60.75\pm_{3.09}\) & \(5.98\pm_{3.26}\) \\
**GCN+SIA** & \(91.53\pm_{1.57}\) & \(71.84\pm_{5.33}\) & \(66.46\pm_{2.63}\) & \(51.96\pm_{3.47}\) & \(71.5\pm_{1.09}\) & \(37.86\pm_{3.06}\) \\ \hline
**GNN** & \(90.24\pm_{1.8}\) & \(67.27\pm_{1.59}\) & \(56.28\pm_{1.35}\) & \(22.97\pm_{9.45}\) & \(73.73\pm_{1.85}\) & \(45.19\pm_{15.07}\) \\
**GIN+SAGPool (threshold)** & \(89.95\pm_{2.32}\) & \(67.47\pm_{1.52}\) & \(58.52\pm_{1.66}\) & \(16.71\pm_{1.19}\) & \(65.38\pm_{1.48}\) & \(25.77\pm_{12.54}\) \\
**GNN+SIA** & \(90.48\pm_{2.28}\) & \(70.01\pm_{9.90}\) & \(56.72\pm_{1.36}\) & \(250.65\pm_{2.55}\) & \(72.89\pm_{1.8}\) & \(47.68\pm_{6.04}\) \\ \hline
**GAT** & \(92.66\pm_{0.73}\) & \(68.37\pm_{4.87}\) & \(70.14\pm_{4.65}\) & \(42.94\pm_{4.4}\) & \(72.94\pm_{2.77}\) & \(42.32\pm_{5.93}\) \\
**GAT+SAGPool (threshold)** & \(89.9\pm_{2.15}\) & \(45.74\pm_{19.36}\) & \(66.1\pm_{1.64}\) & \(38.54\pm_{15.45}\) & \(59.89\pm_{4.53}\) & \(10.6\pm_{5.34}\) \\
**GAT+SIA** & \(93.56\pm_{0.74}\) & \(68.76\pm_{2.38}\) & \(69.43\pm_{5.02}\) & \(44.59\pm_{9.25}\) & \(75.01\pm_{2.95}\) & \(51.19\pm_{5.02}\) \\ \hline
**FAGCN** & \(90.63\pm_{2.56}\) & \(60.7\pm_{4.01}\) & \(55.77\pm_{4.72}\) & \(21.0\pm_{1.85}\) & \(68.38\pm_{3.99}\) & \(46.81\pm_{8.08}\) \\
**FAGCN+SAGPool (threshold)** & \(83.08\pm_{2.46}\) & \(58.47\pm_{17.34}\) & \(58.78\pm_{4.28}\) & \(33.99\pm_{4.97}\) & \(63.41\pm_{9.85}\) & \(50.09\pm_{16.49}\) \\
**FAGCN+SIA** & \(92.01\pm_{1.5}\) & \(70.23\pm_{15.87}\) & \(60.84\pm_{5.38}\) & \(29.25\pm_{1.18}\) & \(68.38\pm_{3.07}\) & \(49.5\pm_{4.42}\) \\ \hline
**GNNML3** & \(91.52\pm_{1.76}\) & \(59.13\pm_{2.82}\) & \(61.95\pm_{6.95}\) & \(18.01\pm_{1.22}\) & \(69.66\pm_{4.48}\) & \(34.69\pm_{5.36}\) \\
**GNNML3+SAGPool (threshold)** & \(87.59\pm_{2.9}\) & \(47.5\pm_{13.57}\) & \(57.21\pm_{1.67}\) & \(35.88\pm_{2.14}\) & \(54.85\pm_{9.96}\) & \(24.79\pm_{3.19}\) \\
**GNNML3+SIA** & \(93.04\pm_{9.01}\) & \(65.4\pm_{4.81}\) & \(62.06\pm_{3.48}\) & \(40.06\pm_{2.76}\) & \(72.14\pm_{2.29}\) & \(52.93\pm_{2.78}\) \\ \hline \hline \end{tabular}
\end{table}
Table 3: Size generalizability evaluated by the graph classification performance on small test graphs and large test graphs. The performance is reported by the average F1 scores and its standard deviation. **+SAGPool (threshold)** means that we apply the thresholded SAG pooling [18, 20] to that model. **+SIA** means that we apply our proposed Size-Insensitive Attention to that model. Highest performance among different models is highlighted in orange.

Figure 3: Graph distance based on h-hop local closeness for BACE (left to right: h=2, h=3, and h=4). Graphs are sorted from small to large and we follow the same procedures as Figure 2. Small-hop (two-hop and three-hop) local closeness does not exhibit a clear dependence on graph size.
### Effectiveness of Proposed Strategy

In this subsection, we examine the effectiveness of SIA.

BaselinesWe consider six neural network models. Each model consists of three layers, with a global max pooling layer employed in the final layer. The baseline models are: Multilayer Perceptron (MLP), GCN [17], GAT [27], GIN [31], FAGCN [6], and GNNML3 [2]. We also consider thresholded SAG pooling[18; 20] as a baseline strategy to be combined with the baseline models. **Upon paper acceptance, we will release the code for SIA.**

Main ResultsTable 3 displays the average and standard deviation of F1 scores assessed on small and large test sets for various models utilizing different strategies. The evaluation is conducted on the BBBP, BACE, and PROTEINS datasets. The highest performance in small and large test sets is highlighted in orange. Our observations are as follows: firstly, in comparison to the original pooling method, SIA consistently enhances performance on the large test set, with minimal exceptions, resulting in performance boosts of up to 22%. Secondly, the improved generalizability of SIA does not come at the expense of performance degradation on the small test set. In fact, SIA outperforms the baselines in more than half of the cases for small test sets and yields comparable results in the remaining cases. These findings demonstrate that SIA is model agnostic and effectively improves the size generalizability of GNNs.

## 6 Related Work

**Size-generalizable Neural Networks for Graph Data.** Size-generalizable neural networks for graph data were firstly studied in various application areas. In the field of algorithmic reasoning, [33; 28] discovered that neural networks are capable of generalizing effectively to larger graphs than the ones used during training, provided that the attention weights are properly supervised. In the field of physical simulation, [24] presented a model to simulate complex physical domains, which can generalize from single-timestep predictions with thousands of particles during training, to different initial conditions, thousands of timesteps, and at least an order of magnitude more particles at test time. Later, more works on the fundamental understanding of GNN's size generalizability were proposed. [18] found that using attention with proper thresholding can improve the size generalizability of GNNs. [36] argued that GNNs' performance degradation on larger graphs can be attributed to the changes in the local degree patterns. As a result, they proposed two domain adaptation strategies to improve generalizability to larger graphs. [7] simulated a size shift in the training graphs via graph coarsening, and proposed a regularization that makes the model robust to the shift. [5] used a causal model to learn approximately invariant representations that better extrapolate between train and test data. [35] studied out-of-distribution in general, and introduced an environment inference model to identify the latent factors that impact data generation from different distributions in a fully data-driven manner. Prior works have not utilized spectral analyses, and many do not specify how variations in graph size affect structural properties.

**Graph Neural Networks with Structural Attention.** Previous works have also explicitly used the structural features in their attention mechanisms for various purposes. [19; 25; 22] used structural attention to improve GNNs' in-distribution generalization in the node/graph classification tasks. [14] incorporated structural information into the embedding learning process for heterogeneous networks, while [32] leveraged degree information to enhance GNNs' performance on heterophilous graphs. In contrast, we use structural attention to improve the size generalizability of GNNs.

## 7 Conclusion

We investigate the size generalizability of GNNs on biological data. We observe a distribution shift in the eigenvalues of the normalized Laplacian/adjacency matrix between small and large graphs, which indicates the differences in the global node connectivity associated with the node closeness centrality. We further observe that graphs of different sizes share similar local connectivity, which can be leveraged to improve size generalizability. Based on the spectral insights and observations from real biological datasets, we propose a model-agnostic strategy, SIA, that utilizes size-irrelevant local structural features to guide learning. Our approach improves the graph classification performance of
various GNNs on small and large graphs, indicating the potential for more effective use of GNNs in real-world applications.
