Feature Expansion for Graph Neural Networks
Graph neural networks aim to learn representations for graph-structured data
and show impressive performance, particularly in node classification. Recently,
many methods have studied the representations of GNNs from the perspective of
optimization goals and spectral graph theory. However, the feature space that
dominates representation learning has not been systematically studied in graph
neural networks. In this paper, we propose to fill this gap by analyzing the
feature space of both spatial and spectral models. We decompose graph neural
networks into determined feature spaces and trainable weights, providing the
convenience of studying the feature space explicitly using matrix space
analysis. In particular, we theoretically find that the feature space tends to
be linearly correlated due to repeated aggregations. Motivated by these
findings, we propose 1) feature subspaces flattening and 2) structural
principal components to expand the feature space. Extensive experiments verify
the effectiveness of our proposed more comprehensive feature space, with
comparable inference time to the baseline, and demonstrate its efficient
convergence capability.
Jiaqi Sun, Lin Zhang, Guangyi Chen, Kun Zhang, Peng XU, Yujiu Yang
# Feature Expansion for Graph Neural Networks

###### Abstract

Graph neural networks aim to learn representations for graph-structured data and show impressive performance, particularly in node classification. Recently, many methods have studied the representations of GNNs from the perspective of optimization goals and spectral graph theory. However, the feature space that dominates representation learning has not been systematically studied in graph neural networks. In this paper, we propose to fill this gap by analyzing the feature space of both spatial and spectral models. We decompose graph neural networks into determined feature spaces and trainable weights, providing the convenience of studying the feature space explicitly using matrix space analysis. In particular, we theoretically find that the feature space tends to be linearly correlated due to repeated aggregations. In this case, the feature space is bounded by the poor representation of shared weights or the limited dimensionality of node attributes in existing models, leading to poor performance. Motivated by these findings, we propose 1) feature subspaces flattening and 2) structural principal components to expand the feature space. Extensive experiments verify the effectiveness of our proposed more comprehensive feature space, with comparable inference time to the baseline, and demonstrate its efficient convergence capability.

Machine Learning, Graph Neural Networks, Graph Neural Networks

## 1 Introduction

Graph Neural Networks (GNNs) have shown great potential in learning representations of graph-structured data, such as social networks, transportation networks, protein interaction networks, etc. (Fan et al., 2019; Wu et al., 2020; Khoshraffar and An, 2022). In this paper, we focus on node representation learning, which is one of the most important tasks in this line of research, where the key is to represent nodes in an informative and structure-aware way.

There are two different types of graph neural networks. One is spatial, which aggregates information from neighboring nodes and updates the representation of the central node. (Velickovic et al., 2018; Xu et al., 2018; Huang et al., 2020). The spectral type, on the other hand, treats the graph structure matrix, such as the Laplacian matrix, as a transformation for the nodes' attributes (signals) in the spectral domain (Defferrard et al., 2016; Chien et al., 2021; He et al., 2021, 2022). The aim is to develop flexible functions for the graph structure so that the signals of the nodes can fit the labels appropriately.

Recently, several perspectives for analyzing GNN representations have emerged, such as general optimization functions, denoising frameworks, and spectral graph theory (Zhu et al., 2021; Ma et al., 2021; Balcilar et al., 2021). However, as a determinant of representation learning, feature spaces have not been systematically studied for graph neural networks. In general representation learning, performance depends heavily on the construction of feature spaces with accessible data (Bengio et al., 2013).

In this paper, we propose to fill this gap and investigate the feature space for both spatial and spectral GNNs. Specifically, for theoretical investigations, we first abstract a linear approximation of the GNNs following the studies (Wu et al., 2019; Xu et al., 2018; Wang and Zhang, 2022). Then, we decompose the GNN components with and without parameters in the linear approximation, where the latter is considered as a feature space built by node attributes and graph structure (e.g., adjacency or Laplacian matrices), and the former denotes the learnable parameters to reweight the features.

Taking advantage of the convenience of decomposition, we examine the feature space of current models. Motivated by that GNNs are expected to fit arbitrary objective, a more comprehensive feature space reflects better representability without any assumption about the data distribution. However, we find theoretically that the feature subspaces of current GNNs are bounded by the weight-sharing mechanism and the limited dimensionality of the node attributes. In order to alleviate the above restrictions and expand the feature
space, we proposed _1) feature subspace flattening_ and _2) structural principal components_, respectively. Specifically, the former reweights all feature subspaces independently to obtain a fully expressed representation. The latter adds the principal components of graph structure matrices as a "complement" to the original feature space. It is emphasized that our proposal makes no assumptions about the graph or the target, which enjoys good generality. We perform extensive experiments on both homophilic and heterophilic datasets to demonstrate the superiority of the proposal.

Our contributions are listed below:

* Starting from representation learning, we provide the first study of the feature space formed in graph-structured data. Based on this view, we study typical spatial and spectral GNNs and identify two problems of existing GNNs caused by bounded feature spaces.
* We then propose two modifications: 1) feature subspace flattening and 2) structural principal components to expand the whole feature space.
* Extensive experiments are performed on homophilic and heterophilic datasets, and our proposal achieves significant improvements, e.g. an average accuracy increase of 32% on heterophilic graphs.

## 2 Preliminaries

In this paper, we focus on the undirected graph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\), along with its node attributes of \(\mathcal{V}\) as \(X\in\mathbb{R}^{n\times d}\) and adjacency matrix \(A\in\mathbb{R}^{n\times n}\) to present \(\mathcal{E}\). GNNs take the input of the node attributes and the adjacency matrix, and output the hidden node representations, as \(H=\mathtt{GNN}(X,A)\in\mathbb{R}^{n\times d}\). By default, we employ the cross-entropy loss function in the node classification task to minimize the difference between node label \(Y\) and the obtained representation as \(\mathcal{L}(H,Y)=-\sum_{i}Y_{i}\log\mathrm{softmax}(H_{i})\).

**Spatial GNNs (with non-parametric aggregation)** mostly fall into the message-passing paradigm. For any given node, it essentially aggregates features from its neighbors and updates the aggregated feature,

\[H_{i}^{(k+1)}=\sigma\left(f_{u}\left(H_{i}^{(k)},f_{a}\left(\hat{A}_{ij},H_{j }^{(k)};j\in\mathcal{N}_{i}\right)\right)\right), \tag{1}\]

where \(\sigma\left(\cdot\right)\) is a non-linear activation function, \(H^{(k)}\) indicates the hidden representation in \(k\)-th layer, \(f_{a}\) and \(f_{u}\) are the aggregation and updating functions (Balcilar et al., 2021), \(\hat{A}=(D+I)^{-1/2}(A+I)(D+I)^{-1/2}\) is the re-normalized adjacency matrix using the degree matrix \(D\), and \(\mathcal{N}_{i}\) denotes the \(1\)-hop neighbors.

Here, we provide two examples to specify this general expression. One is the vanilla GCN1 (Kipf Welling, 2017) that adopts the mean-aggregation and the average-update, whose formulation is:

Footnote 1: GCN (Kipf Welling, 2017) is also an instance of spectral GNNs, and here we categorize it into spatial type due to its critical role of bridging spectral GNNs to spatial interpretations.

\[H^{(k+1)}=\sigma\left(\hat{A}H^{(k)}W^{(k)}\right). \tag{2}\]

The second example shows a different update scheme with skip-connection (Xu et al., 2018; Li et al., 2019; Chen et al., 2020), which is defined as follows,

\[H^{(k+1)}=\sigma\left(\alpha^{(k)}H^{(0)}W_{0}^{(k)}+\hat{A}H^{(k)}W_{1}^{(k) }\right), \tag{3}\]

where \(\alpha^{(k)}\) controls the weight of each layer's skip-connection, \(W_{0}^{(k)},W_{1}^{(k)}\) are the transformation weights for the initial layer and the previous one, respectively.

**Spectral GNNs (polynomial-based)** originally employ the Graph Fourier transforms to get filters (Chung and Graham, 1997), such as using the eigendecomposition of the Laplacian matrix: \(\tilde{L}=I-\hat{A}=U\Lambda U^{T}\). In recent years, methods of this type have focused more on approximating arbitrary global filters using polynomials (Wang and Zhang, 2022; Zhu and Koniusz, 2020; He et al., 2021), which has shown superior performance and is written as

\[H=\sum_{k=0}^{K}\gamma^{(k)}P_{k}(\hat{L})\sigma(XW_{1})W_{2}, \tag{4}\]

where \(P_{k}(\cdot)\) donates a polynomial's \(k\)-order term; \(\gamma^{(k)}\) is the adaptive coefficients and \(W_{1},W_{2}\) are learnable parameters.

In this paper, we focus on the typical instances of the two types of graph neural networks, as indicated in the parentheses above. For spatial models, we focus on those with non-parametric aggregation, excluding learnable aggregation such as (Velickovic et al., 2018) in the analytical parts. Considering the spectral type, we focus on polynomial-based models, and other spectral filters are not included in this paper, e.g. (Levie et al., 2018; Thanou et al., 2014). It is worth noting that these cases dominate the state of the art, and we still include other methods in empirical comparisons.

**Primary observation.** From the review of GNN models, we can conclude that usually, the node attributes \(X\) and the graph structure matrices \(\hat{L}/\hat{A}\) are computed first and then some parameter matrices are applied to obtain the final node representation. Starting from this observation, in the following, we extract a linearly approximated framework including GNNs that first construct feature spaces and then apply parameters to reweight them to obtain node representations.
## 3 Analysis

To perform theoretical investigations of the feature space, we abstract a linear approximation of GNNs based on the success of linearisation attempts of Wu et al. (2019); Xu et al. (2018); Wang and Zhang (2022). Specifically, we provide a general formulation for the linear approximation of arbitrary graph neural networks. \(\overline{\mathfrak{G}\mathfrak{N}}(X,\hat{A})\) as:

\[H=\overline{\mathfrak{G}\mathfrak{N}}(X,\hat{A})=\sum_{t=0}^{T-1}\Phi_{t}(X, \hat{A})\Theta_{t}, \tag{5}\]

where \(\Phi_{t}(X,\hat{A})\in\mathbb{R}^{n\times d_{t}}\) is the non-parametric feature space constructing function that inputs the graph data (e.g., node attributes and graph structure) and outputs a feature subspace, \(\Theta\in\mathbb{R}^{d_{t}\times c}\) is the parameter space to reweight the corresponding feature subspace for each class \(c\), and \(T\) is a hyper-parameter of the number of the feature subspaces that the GNN contains. In general, in this linear approximation, a GNN model forms \(T\) feature subspaces, i.e., \(\Phi_{t}\), and outputs the addition of all the reweighted subspaces using the respective parameters \(\Theta_{t}\). Note that the (total) feature space is the union of the subspaces as \(\Phi=\{\Phi_{t}\}_{t=0,1,\cdots,T-1}\). Similarly, we have the (total) parameters \(\Theta=\{\Theta_{t}\}_{t=0,1,\cdots,T-1}\). Besides, the number of the subspaces \(T\) that a GNN model obtains is not parallel with its layer/order, for which we will provide some examples in the later revisiting subsection.

In the following, we will first identify the feature space \(\Phi\) and the parameters \(\Theta\) for existing GNNs. Then, from the perspective of the feature space, we analyze the common mode across different model lines. Finally, we investigate and summarize the problems behind this mode.

### Revisiting Existing Models

**Spatial GNNs (with non-parametric aggregation).** We first transform the recursive formula of spatial GNNs, e.g., (1), into an explicit formula, by iterating from the initial node attributes that \(H^{(0)}=X\) and ignoring the activation function. Following Section 2, we consider two examples of spatial GNNs: the vanilla GCN (Kipf and Welling, 2017) and the one with skip-connections (Xu et al., 2018).

The linear approximated explicit formula of a \(K\)-layer is:

\[H^{(K)}=\hat{A}^{K}X\prod_{i=0}^{K-1}W^{(i)}, \tag{6}\]

which forms single feature space \(\Phi_{0}=\hat{A}^{K}X\) and parameters \(\Theta_{0}=\prod_{i=0}^{K-1}W^{(i)}\) with \(T=1\). It is a perfect example that the number of GNN layers \(K\) is not identical to the number of the subspaces \(T\) a GNN forms. While (3) furthermore considers skip-connections, whose \(K\)-layer linear approximated explicit formula is formualted as:

\[\begin{split} H^{(K)}&=\sum_{i=0}^{K-1}\hat{A}^{i}X \alpha^{(K-1-i)}W_{0}^{(K-1-i)}\prod_{j=K-i}^{K-1}W_{1}^{(j)}\\ &+\hat{A}^{K}X\prod_{h=0}^{K-1}W_{1}^{(h)}.\end{split} \tag{7}\]

By this decomposition, this GCN with skip-connections consists of \(T=K+1\) feature subspaces. It forms each feature subspace as \(\Phi_{t}=\hat{A}^{t}X\). For the first \(T-1\) subspaces, the according respective parameters is denoted as \(\Theta_{t;t<T-1}=\alpha^{(K-1-t)}W_{0}^{(K-1-t)}\prod_{j=K-t}^{T-1}W_{1}^{(t)}\), and for for the last \(\Phi_{T}\), the parameter is \(\Theta_{T}=\prod_{h=0}^{T-1}W_{1}^{(h)}\). Please refer to Appendix A.1 for the derivation.

**Spectral GNNs (polynomial-based).** This type is specified by the explicit formula as (4). We remove the activation function, and obtain the linear approximation of a \(K\)-order

\begin{table}
\begin{tabular}{l l l} \hline \hline  & Original formula\({}^{*}\) & Linear approximation formulations \\ \hline GCN & \(H^{(k+1)}=\sigma\left(\hat{A}H^{(k)}W^{(k)}\right)\) & \(H^{(K)}=-\hat{A}^{K}X\prod_{h=0}^{K-1}W^{(i)}\) \\ (Kipf and Welling, 2017) & \(H^{(k+1)}=\sigma\left((\hat{A}^{(k)}I+\hat{A})H^{(k)}W_{0}^{(k)}\right)W_{1}^{ (k)}\) & \(H^{(k)}=-\sum_{h=0}^{K-1}\hat{A}^{K}\sum_{\{\alpha^{\prime},\alpha^{\prime}, \alpha^{\prime},\alpha^{\prime},\alpha^{\prime},\alpha^{\prime},\alpha^{\prime}, \alpha
spectral GNNs as:

\[H^{(K)}=\sum_{k=0}^{K}P_{k}(\hat{L})X\gamma^{(k)}W^{(0)}. \tag{8}\]

We put the learnable polynomial coefficient \(\gamma^{(k)}\) together with the parameter matrices. We also combine the shared parametric matrices in (4) as \(W^{(0)}=W_{1}W_{2}\). In this way, (8) forms \(T=K+1\) feature subspaces, each denoted as \(\Phi_{t}=P_{t}(\hat{L})X\), and the parameters used to reweight the respective subspaces are \(\Theta_{t}=W^{(0)}W^{(1)}\). See Appendix A.2 for further derivations.

In Table 1, we summarize typical instances of spatial and spectral methods, using different colors to distinguish the feature space \(\Phi\) (orange) and the parameters \(\Theta\) (blue). It shows that the proposed extracted view (5) can support most methods in both spatial and spectral domains.

### Analysis of the Feature Space

In this section, we first give a theoretical argument that the feature subspace of current GNNs obeys asymptotically linear correlation (see Proposition 3.1). Then, we find that the current weight-sharing mechanism weakens the expressiveness of the feature space when the strict linear correlation is satisfied (see Theorem 3.2). In the remainder, we analyze the case where the feature subspaces do not obey strict linear correlation. We find that the feature space is insufficient when the dimensionality of the node attributes is limited and no assumptions can be made about the feature construction (e.g., heterophily).

Table 1 shows that the feature space \(\Phi\) in spatial and spectral GNNs is formulated by the multiplication of graph structure matrices function and node attributes, e.g. \(\Phi_{k}=P_{k}(\hat{L})X\). We consider \(\hat{A}^{k}X\) to be the basic element for each feature subspace since other forms such as \(P_{k}(\hat{L})X\) and \(\hat{L}\) are all linear transformations of \(\hat{A}\). Given this, it can be concluded that the feature subspaces of GNNs are sequentially appended as the spatial layers or the spectral orders of GNNs increase, with the latter subspace being the result of applying the aggregation function to the former.

This monotonous construction of the feature space will lead to a high linear correlation between each feature subspace as presented in Proposition 3.1.

**Proposition 3.1**.: _(its proof can be found in Appendix A.3) Suppose the feature subspaces are constructed sequentially by \(\{\Phi_{t}=\hat{A}^{t}X\}_{t}\). As \(i\in\mathbb{Z}\) increases, the subspace \(\Phi_{t+i}\) gradually tends to be linearly correlated with \(\Phi_{t}\)._

To better understand the property of Proposition 3.1, we provide a quantitative demonstration using the feature space of GPRGNN (Chien et al., 2021) as an example. We measure the linear correlation of the appended \(k\)-th feature (sub)space with the previous ones by calculating the mutual correlation values:

\[E_{i}^{k}=\max_{j=0,\cdots,k-1}\mu(\hat{L}^{j}X,\hat{L}^{k}X_{.i}), \tag{9}\]

where \(i\) is the index of the column in \(\hat{L}^{k}X\), and \(\mu(M_{0},M_{1})=\max_{d_{u}\in M_{0},d_{v}\in M_{1}}\cos(d_{u},d_{v})\) is the mutual-coherence of two matrices, based on the cosine distance \(\cos\). In Figure 1, we visualize the distribution of \(\{E_{i}^{k}\}\) of all the columns with \(k=1,2,3,4\). It confirms that the linear correlation improves significantly with the number of subspaces. Therefore, both theoretical discussions and visualizations show a trend of increasingly linear correlations between feature subspaces with an increasing number of GNN layers/orders.

Since we are dealing with a gradually linear correlation, in the following we identify two questions about the current feature construction when this condition is strictly fulfilled or not, respectively.

**Issue 1: Constraint from the weight sharing mechanism.** From Table 1 we see that existing GNNs usually share parameter weights between different subspaces. Under the condition of linear correlation, we provide a direct argument that using the weight-sharing method limits the expressiveness of the feature space.

**Theorem 3.2**.: _(its proof can be found in Appendix A.4) Suppose \(\Phi_{a},\Phi_{b}\in\mathbb{R}^{n\times d}\) are two linearly correlated feature subspaces, i.e. there exists \(W_{a}\in\mathbb{R}^{d\times d}\) such that \(\Phi_{a}W_{a}=\Phi_{b}\), and suppose a matrix \(B\in\mathbb{R}^{n\times c}\), \(c<<d\). If \(B\) can be represented by using both subspaces with a common weight \(W_{B}\), i.e., \(\gamma_{a}\Phi_{a}W_{B}+\gamma_{b}\Phi_{b}W_{B}=B\) and \(\gamma_{a},\gamma_{b}\in\mathbb{R}\), then \(B\) can always be represented by only one subspace \(\Phi_{a}\), i.e., \(\Phi_{a}W_{B}^{\prime}=B\) and \(W_{B}^{\prime}\in\mathbb{R}^{d\times c}\)._

It shows an expressiveness bound of the feature subspaces when they are linearly correlated. While this linearly dependency can be used as redundancy and is widely used in

Figure 1: Distribution of the mutual correlation values between the later feature (sub)spaces to the previous total ones.
areas such as dictionary learning (Elad, 2010). In particular, an over-determined linear system can be relaxed to an under-determined one when linearly correlated columns are added to the regressor matrix, making it easier to optimize. However, the condition of this benefit is not met in existing GNNs due to the weight-sharing mechanism. In the next section, we propose a modification to break this constraint.

Issue 2: Constraint from limited dimensionality of node attributes.Proposition 3.1 clarifies the tendency of linear correlation between the feature subspaces, but in the first few, this property may not be strictly satisfied. It makes the weight-sharing not so flawed and also weakens the effectiveness of the corresponding modification. In the following, we give a discussion of the condition that the feature spaces are not necessarily linearly correlated, and we consider two limiting scenarios of the dimension \(d\) of the node attributes, since the respective discussions are strongly orthogonal.

First, if \(d\to n\), \(X\) itself is a sufficient feature space if \(X\) is sparse (e.g., bag-of-words features) or each column is linearly independent. Besides, the weight-sharing method sums different feature subspaces by learnable weights \(\gamma\) for each. As a result, the optimized sum promotes more of the subspaces that are closer to the labels. Therefore, the core is the assumptions of subspace construction (e.g., homophilic assumptions and hyperparameter search for aggregation functions) and more flexible polynomial functions (e.g., Chebyshev and Bernstein). They all have been widely studied, where the performance of weight-sharing methods is convincing, such as (Wang & Zhang, 2022).

On the other hand, when \(d<<n\), the node attributes \(X\) have a thin shape, making the regression system strictly over-determined. In addition, without any assumption about the feature space construction, there is hardly an exact solution, even when using linearly correlated copies to perform the expansion (which we will discuss in the next section). Therefore, compared to homophilic graphs, heterophilic graphs are a more severe case, especially since there is hardly any assumption about the feature space construction. For this situation, we propose the other modification below.

## 4 Proposed Method

Here, we first propose _1) feature subspace flattening_ for the detrimental condition caused by the weight-sharing mechanism given by Theorem 3.2 and Proposition 3.1. Then, to compensate for the second case when the dimensionality of the node attributes is limited, we propose _2) structural principal components_ to expand the original feature space.

### Modification 1: Feature Subspaces Flattening

For the first problem, we encourage each feature subspace to be independently expressed of each other in the model and weight them separately. Before giving supporting proof, we provide an illustration of this modification in Figure 2. The benefit of this proposal is given in the following.

**Theorem 4.1**.: _(its proof can be found in Appendix A.5) Suppose \(\Phi_{a},\Phi_{b}\in\mathbb{R}^{n\times d}\) are two linearly correlated feature subspaces, i.e., there exits \(W_{a}\in\mathbb{R}^{d\times d}\) such that \(\Phi_{a}W_{a}=\Phi_{b}\), and a matrix \(B\in\mathbb{R}^{d\times c}\), \(c<<d\). If \(B\) can be expressed by \(\Phi_{a}\), i.e., \(\Phi_{a}W_{B}=B\), then using both subspaces \(\Phi_{a}\) and \(\Phi_{b}\) independently, i.e., \(\Phi_{a}W_{a}+\Phi_{b}W_{b}=B\), the optimum is more easily achieved than a weight-sharing style._

It follows from this theorem that feature subspace flattening is more effective than weight-sharing methods when the feature subspaces tend to be linearly correlated. For further discussion on parameter matrices that are stacked (e.g., GCN), please refer to Appendix A.7, where the same conclusion is maintained.

### Modification 2: Structural Principal Components

Next, we consider the second issue that the dimension of the node attributes is limited. We propose to expand the whole feature space by introducing other feature subspaces.

There are two criteria that we consider. One is that the introduced feature subspace should be highly uncorrelated with the existing feature subspace, otherwise, according to the analysis in the previous section, it may not be the same as the previously proposed modification under this condition. The other is that the dimension of the introduced subspace should not be too large, otherwise noise might be included and the computational cost would also increase.

Considering this, for graph-structured data, there are two data matrices, i.e., node attributes and graph structure matrices, and the former has been explicitly exploited as one of the feature subspaces in most GNN models, as summarized

Figure 2: Architecture of our proposal
in Table 1. On the contrary, structure matrices are used only in combination with node attributes. Given these conditions, we propose to construct the expansion subspace using the truncated SVD of the structural matrix, called _structural principal components_ as modification 2. It naturally provides orthogonal subspaces, and the truncated form limits the dimension of the matrices. Thus, two criteria are met. Specifically, we extract the low-dimensional information for the graph structure to obtain its principal components:

\[S=\tilde{Q}\tilde{V};\hat{A}=QVR^{T}, \tag{10}\]

where \(\tilde{Q},\tilde{V}\) are the principal components and the corresponding singular values. Besides, we prove the effectiveness of this modification in the following theorem.

**Theorem 4.2**.: _(its proof can be found in Appendix A.6) Suppose the dimensionality of the node attributes is much smaller than the number of nodes, i.e., \(d<<n,X\in\mathbb{R}^{n\times d}\), and a \(z\)-truncated SVD of \(\hat{L}\), which satisfies \(||U_{z}S_{z}-\hat{L}||_{2}<\epsilon\), where \(\epsilon\) is a sufficiently small constant. Then the linear system \((\Phi_{k},U_{z}S_{z})W_{B}^{\prime}=B\) can achieve a miner error than the linear system \(\Phi_{k}W_{B}=B\)._

So far, we have introduced two modifications, and together they contribute to a new proposed GNN model called Feature Expanded Graph Neural Network (FE-GNN). It is shown in Figure 2 and formulated as follows,

\[H=\sum_{k=0}^{K}P_{k}(\hat{L})XW^{(k)}+SW_{s}. \tag{11}\]

It constructs the feature space in two ways. The first part inherits the polynomial-based GNNs and takes advantage of the multiplication of the polynomials of the structural matrix \(P_{k}(\hat{L})\) and the node attributes \(X\). Second, we use the principal components of the structural matrices to form another feature subspace \(S\). In addition, FE-GNN uses independent parameter matrices \(W^{(k)}\) and \(W_{s}\) to reweight each feature subspace to provide flexible reweighting.

In particular, the \(\Phi_{k}\) and \(S\) feature spaces can have unbalanced scales and lead to poor reweighting. Therefore, we add a column-wise normalization to ensure that each column of each feature subspace contributes equally to the whole feature space. Finally, to better verify the importance of the feature space view, our implementation is purely linear without any deep artifices such as activation functions or dropout except for the cross-entropy loss, while we obey the original implementation for the baselines and their non-linearity is preserved.

### Discussion

Our analysis and proposal make few assumptions about the distribution of node attributes, the graph structure, or even their relationships. Since the point view of the feature space is not an analysis method proposed specifically for graph structure data or GNNs, our investigations are more general and jump out of the limitations of other views. For example, graph denoising (Zhu et al., 2021) and spectral graph theory view (Balcilar et al., 2021) both ignore the property of node attributes, which is the key for our second proposal, and instead focus on the transformations of the structure matrices. We provide a more comprehensive comparison of related work in section 5.

In our proposed method, the first modification that flattens the feature subspace improves the effectiveness of each feature subspace, but the number of parameters must be higher because no parameter matrices are shared. In experiments, we surprisingly found relatively low training time costs compared to baselines. Furthermore, the second modification can be misinterpreted as an arbitrary addition of

\begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline \hline \multirow{2}{*}{Type} & \multirow{2}{*}{Baseline} & \multirow{2}{*}{Time (ms)} & \multicolumn{6}{c}{Homophilic graphs} & \multicolumn{6}{c}{Heterophilic graphs} \\ \cline{3-10}  & & & Cora & CiteSeer & PubMed & Computers & Photo & Squirrel & Chameleon & Actor \\ \hline \multirow{4}{*}{Spatial} & MLP & - & 76.70\(\pm\)0.15 & 76.67\(\pm\)0.28 & 85.11\(\pm\)0.26 & 82.62\(\pm\)0.21 & 84.16\(\pm\)0.13 & 37.86\(\pm\)0.39 & 57.83\(\pm\)0.31 & 38.99\(\pm\)0.17 \\  & GCN & 17.42\(\pm\)1.64 & 87.69\(\pm\)0.00 & 79.31\(\pm\)0.46 & 86.71\(\pm\)0.18 & 83.24\(\pm\)0.11 & 88.61\(\pm\)0.36 & 47.21\(\pm\)0.59 & 61.85\(\pm\)0.38 & 28.61\(\pm\)0.39 \\  & GAT & 18.06\(\pm\)1.18 & 88.07\(\pm\)0.41 & 80.80\(\pm\)0.25 & 86.69\(\pm\)0.14 & 82.86\(\pm\)0.35 & 90.84\(\pm\)0.22 & 33.40\(\pm\)0.16 & 51.82\(\pm\)1.33 & 33.48\(\pm\)0.35 \\  & GraphSAGE & 10.72\(\pm\)0.25 & 87.74\(\pm\)0.41 & 79.20\(\pm\)0.42 & 87.65\(\pm\)0.14 & 87.38\(\pm\)0.13 & 93.59\(\pm\)0.13 & 48.15\(\pm\)0.48 & 62.45\(\pm\)0.48 & 36.39\(\pm\)0.35 \\  & GCNII & 8.48\(\pm\)0.24 & 87.46\(\pm\)0.31 & 80.76\(\pm\)0.30 & 88.82\(\pm\)0.08 & 84.75\(\pm\)0.22 & 93.21\(\pm\)0.25 & 43.28\(\pm\)0.35 & 61.80\(\pm\)0.44 & 38.61\(\pm\)0.26 \\  & APPNP & 23.74\(\pm\)0.28 & 87.92\(\pm\)0.20 & 81.42\(\pm\)0.26 & 88.16\(\pm\)0.14 & 58.88\(\pm\)0.13 & 90.40\(\pm\)0.34 & 39.63\(\pm\)0.49 & 59.01\(\pm\)0.48 & 39.90\(\pm\)0.25 \\ \hline \multirow{4}{*}{Spectral} & ChebyNet & 20.26\(\pm\)1.63 & 87.17\(\pm\)0.19 & 77.97\(\pm\)0.36 & 89.04\(\pm\)0.08 & 87.92\(\pm\)0.13 & 94.58\(\pm\)0.11 & 44.55\(\pm\)0.28 & 64.06\(\pm\)0.47 & 25.55\(\pm\)1.67 \\  & GPGRNN & 23.55\(\pm\)1.35 & 87.97\(\pm\)0.24 & 78.57\(\pm\)0.31 & 89.11\(\pm\)0.08 & 86.07\(\pm\)0.14 & 93.99\(\pm\)0.11 & 43.56\(\pm\)0.22 & 63.67\(\pm\)0.34 & 36.93\(\pm\)0.26 \\  & BernNet & 36.88\(\pm\)0.44 & 87.66\(\pm\)0.26 & 79.34\(\pm\)0.32 & 89.33\(\pm\)0.27 & 88.66\(\pm\)0.08 & 94.03\(\pm\)0.08 & 44.47\(\pm\)0.39 & 63.07\(\pm\)0.43 & 36.89\(\pm\)0.30 \\ \hline \multirow{4}{*}{Unified} & GNN-LF & 52.77\(\pm\)4.50 & 88.12\(\pm\)0.06 & **83.66\(\pm\)0.06** & 87.79\(\pm\)0.05 & 87.63\(\pm\)0.05 & 93.79\(\pm\)0.06 & 39.03\(\pm\)0.08 & 59.84\(\pm\)0.09 & 41.97\(\pm\)0.06 \\  & GNN-HF & 53.28\(\pm\)4.51 & 88.47\(\pm\)0.09 & 83.56\(\pm\)0.10 & 87.83\(\pm\)0.10 & 86.94\(\pm\)0.06 & 93.89\(\pm\)0.10 & 39.01\(\pm\)0.51 & 63.90\(\pm\)0.11 & **42.47\(\pm\)0.07** \\  & ADA-UGNN & 14.36\(\pm\)0.27 & 88.92\(\pm\)0.11 & 79.34\(\pm\)0.09 & 90.08\(\pm\)0.05 & 89.56\(\pm\)0.09 & 94.66\(\pm\)0.07 & 44.58\(\pm\)0.16 & 59.25\(\pm\)0.16 & 41.38\(\pm\)0.12 \\ \cline{2-2} \cline{2-2} \cline{2-2} \cline{2-2} \cline{2-2} \cline{2-2} \cline{2-2} \cline{2-2} \cline{2-2} \cline{2-2} \cline{2-2} \cline{2-2} \cline{2-2} \cline{2-2} \cline{2-2} \cline{2-2} \cline{2-2} \cline{2-2} \cline{2-2} \cline{2-2} \cline{2-2} \cline{2-2} \cline{2-2} \cline{2-2}{2} \cline{2-2} \cline{2-2} \cline{2-2}{2-2} \cline{2-2} \cline{2-2} \cline{2-2}{2-2} \cline{2-2}{2-2} \cline{2-2} \cline{2-2}{2-2} \cline{2-2} \cline{2-2}{2-2} \cline{2-2}{2-2} \cline{2-2} \cline{2-2}{2-2} \cline{2-2} \cline{2-2-2
structural information. With this in mind, we will conduct additional experiments with other information extraction methods. Besides, in our approach, the aggregation process can be abstracted as preprocessing to further speed up the training process. We leave this as future work; in our experiments, aggregations are computed during each training session for a fair comparison.

Finally, it is worth noting that the linear approximation is adopted for the non-linear GNNs for the following reasons: 1) it allows us the convenience of a deeper view of the GNN models, 2) linearization is a quite normal setting in the theoretical analysis in general machine learning and deep learning analysis, since the non-linearity can hardly provide rigorous arguments (Wu et al., 2019; Maddox et al., 2021), and 3) the proposed model is fully consistent with the analytical view of linearity.

## 5 Other Related Work

Unified perspectives for GNNs.There have been several perspectives for studying GNNs representations. Balcilar et al. (2021) first bridge the spatial methods to the spectral ones, that they assign most of the spatial GNNs with their corresponding graph filters. More specifically, they begin with GNN models' convolution matrix and then summarize their frequency responses. Ma et al. (2021) regard the aggregation progress of GCN (Kipf and Welling, 2017), GAT (Velickovic et al., 2018), and APPNP (Klicpera et al., 2019) as graph signal denoising problem, which aims to recover a clean signal from an objective and a certain denoising regularization term. Given this, the authors consider generalize the smoothing regularization term to and propose ADA-UGNN. However, it also ignores the property of node attributes but focusing on the flexibility of the denoising functions. Zhu et al. (2021) give a more comprehensive summary of GNNs from an optimization view, which partly overlaps with (Ma et al., 2021)'s opinions of graph signal denoising. They propose GNN-LF/HF with adjustable objective that behaves as a low/high-pass filter.
hidden dimension) and discusses the correlation between the columns of the feature subspaces, while over-smoothing investigations usually focus on the row-wise perspective (i.e., node dimension) and consider the similarity of the output representations of the nodes. They are obviously different, and a further study of these two should also be an interesting future work.

## 6 Experiments

We evaluate FE-GNN2 on: (1) node classification results, (2) ablation studies, and (3) efficiency check.

Footnote 2: Our code is available at [https://github.com/sajqavril/Feature-Extension-Graph-Neural-Networks.git](https://github.com/sajqavril/Feature-Extension-Graph-Neural-Networks.git)

Dataset.We implement our experiments on homophilic datasets, i.e., Cora, CiteSeer, PubMed, Computers, and Photo (Yang et al., 2016; Shchur et al., 2018), and heterophilic Chameleon, Squirrel, and Actor (Rozemberczki et al., 2021; Pei et al., 2020). Among them, Chameleon and Squirrel are two cases that bear problem 2, i.e., limited dimension of node attributes and no homophilic assumptions to use. More details can be found in the appendix B.

Baselines.We compare a list of state-of-the-art GNN methods. For spatial GNNs we have GCN (Kipf and Welling, 2017), GAT (Velickovic et al., 2018), GraphSAGE (Hamilton et al., 2017), GCNII (Chen et al., 2020) and APPNP (Klicpera et al., 2019), where MLP is included as a special case. For spectral methods we take ChebyNet (Defferrard et al., 2016), GPRGNN (Chien et al., 2021) and BernNet (He et al., 2021). We also cover the recent unified models, ADA-UGNN (Ma et al., 2021) and GNN-LF/HF (Zhu et al., 2021). FE-GNN uses the Chebyshev or monomial polynomials to construct the feature space, and we refer to the corresponding versions as FE-GNN (C) and FE-GNN (M), respectively. Please refer to Appendix B.2 for more details on the implementation.

### Node Classification

We test on the node classification task with random 60%/20%/20% splits and summarize the results of 100 runs in Table 2, reporting the average accuracy with a 95% confidence interval. We observe that FE-GNN has almost the best performance on homophilic graphs. In particular, compared to the current SoTA method ADA-UGNN (Ma et al., 2021), which unifies the objectives in both spatial and spectral domains, our FE-GNN achieves a \(1.1\%\) accuracy improvement on average on 5 homophilic graph datasets. We attribute the superior performance of GNN-LF/HF on Citeseer to its complex hyperparameter tuning, where more fine-grained constraints of the parameters can be found, which we consider as future work in section 7. Furthermore, FE-GNN achieves on average \(32.0\%\) improvement on three heterophilic graph datasets than the GCN baseline. It is worth highlighting the huge margin of FE-GNN over others on Chameleon and Squirrel, where they perfectly fit our assumption of the second modification, i.e., heterophilic and limited dimensionality of node attributes. The results of the ablation studies are also consistent with this.

### Ablation Studies

We study the contribution of different components and hyperparameter effects in FE-GNN.

Does the feature flattening work?Yes.In Table 3, we compare our proposal with a weight-sharing (WS) instance where the principal components are retained. It shows that over an increasing number of feature subspaces, the flattening feature subspace is always observed better performance, which verifies the discussion of theorems 3.2 and 4.1.

When do structural principal components work?On limited node attributes and the heterophilic case.We evaluate FE-GNN on 5 datasets of both homophilic and heterophilic graphs in 3 different feature space constructions: including \(w/o\)\(S\), \(w/o\)\(P_{k}(\hat{L})X_{k=0}\), and \(w/o\)\(P_{k}(\hat{L})X_{k>0}\), which denote feature space constructions without graph structure, without note attributes, and without the combination of both. In the ablation results of Table 5, we found that \(w/o\)\(S\) works well on homophilic graphs, but fails on heterophilic ones (with limited node attribute dimension), while the other two work inversely. Meanwhile, \(w/\)\(S\) greatly improves the bounded cases, and these results confirm our original intention of proposing structural principal components. In addition, we provide other variants in Appendix B.3 that include structural information as an extension of our discussion in Section 4.3, and row-wise normalization in Appendix A.8, where our proposal is comparably effective.

What proportion of the truncated SVD is appropriate?94%.We use different ratios of singular vectors and values to construct \(S\), i.e., the top \(j\) singular values get \(r=\sum_{j=1}^{i}V_{jj}/\sum_{j=1}^{n}V_{jj}\) ratio of components. In Figure 6, we show the accuracy of CiteSeer and Chameleon as the ratio of singular values increases, where CiteSeer is robust to variation in the ratio, while Chameleon performs best

\begin{table}
\begin{tabular}{l c c c c} \hline \hline  & Cora & CiteSeer & Chameleon & Squirrel \\ \hline k=2 & \(89.15\pm_{0.86}\) & \(81.97\pm_{1.10}\) & \(73.41\pm_{1.40}\) & \(67.37\pm_{0.83}\) \\ k=2 (WS) & \(87.21\pm_{0.83}\) & \(73.89\pm_{0.72}\) & \(72.94\pm_{1.22}\) & \(66.01\pm_{1.31}\) \\ k=4 & \(88.56\pm_{0.81}\) & \(80.19\pm_{0.84}\) & \(73.23\pm_{1.56}\) & \(67.40\pm_{0.90}\) \\ k=4 (WS) & \(87.28\pm_{1.38}\) & \(77.72\pm_{0.86}\) & \(73.23\pm_{1.72}\) & \(66.43\pm_{1.72}\) \\ k=8 & \(88.92\pm_{0.88}\) & \(81.11\pm_{0.89}\) & \(73.85\pm_{1.52}\) & \(67.93\pm_{0.04}\) \\ k=8 (WS) & \(86.92\pm_{1.66}\) & \(77.32\pm_{0.33}\) & \(73.15\pm_{1.83}\) & \(66.63\pm_{2.38}\) \\ k=16 & \(88.26\pm_{1.4}\) & \(80.54\pm_{1.03}\) & \(73.88\pm_{1.53}\) & \(67.82\pm_{1.54}\) \\ k=16 (WS) & \(87.34\pm_{1.98}\) & \(78.60\pm_{0.70}\) & \(72.94\pm_{1.79}\) & \(66.65\pm_{2.15}\) \\ \hline \hline \end{tabular}
\end{table}
Table 3: Ablation study of 1) flattening feature subspaces
at \(r=94\%\). So we use 94% for further experiments. We provide more SVD results in the Appendix B.6.

**At what order is a polynomial sufficient? Around three.** We test a progressive order \(K\) of polynomials on Cora and Chameleon as shown in Figure 4. The performance in Cora increases from \(1\) to \(3\) and decreases slightly, while Chameleon shows only small changes. This suggests that order 3 is good enough to achieve near-optimal performance, which is also an advance by flattening the feature subspaces compared to deep GNNs. A more comprehensive comparison can be found in Appendix B.4.

**Is linearity sufficient for constructing features? Yes.** We apply the nonlinear activation function to FE-GNN and some deep learning training techniques, including Dropout (Agarap, 2018) and DropEdge (Rong et al., 2020), to verify the sufficiency of our linear implementation. In Figure 3, we show the corresponding performance with different drop ratios on four datasets, where both show worse performance when increasing the drop rate. Therefore, our linear construction is sufficient for FE-GNN. These results also argue for more attention to feature space construction to avoid over-application of deep artifices.

### Efficiency Check

Finally, we examine the efficiency of our proposal, including the training time cost and the truncated SVD time. In Table 2, we collect the training time per epoch (ms) for each method, which shows that FE-GNN behaves at a comparable time cost to other baselines, even though it bears more computational cost from the independent feature expression. Note that the time we report includes graph propagation for a fair comparison, although FE-GNN can reduce it further by constructing the feature space in a preprocessing manner. In Figure 5 we compare the convergence time for all methods and observe that FE-GNN consumes the minimum number of training epochs while achieving the highest accuracy, which exactly reveals the conclusion of easier optimization progress from Theorem 4.1. And in table 4, we show the training time and SVD time (as preprocessing), from which we find that the SVD time in the total training time is less than 10%, which confirms the applicability.

## 7 Conclusion

In this paper, we provide the feature space view to analyze GNNs, which separates the feature space and the parameters. Together, we provide a theoretical analysis of the existing feature space of GNNs and summarize two issues. We propose 1) feature subspace flattening and 2) structural principal components for these issues. Extensive experimental results verify their superiority.

LimitationsNonlinear cases are not included in our work and will be considered in future work. Also, the correlation between the subspaces should be studied more carefully beyond the linear correlation property; in a sense, the parameters can be further reduced by introducing reasonable constraints. Finally, more feature space construction methods should be discovered for future work.

## Acknowledgements

This work was partly supported by the National Key Research and Development Program of China (No. 2020YFB1708200), the "Graph Neural Network Project" of Ping An Technology (Shenzhen) Co., Ltd. and AMiner.Shenzhen SciBrain fund. This work was also supported in part by the NSF-Convergence Accelerator Track-D award #2134901, by the National Institutes of Health (NIH) under Contract R01HL159805, by grants from Apple Inc., KDDI Research, Quris AI, and IBT, and by generous gifts from Amazon, Microsoft Research, and Salesforce.

\begin{table}
\begin{tabular}{c c c c c c} \hline \hline  & Cora & CiteSeer & PhMed & Squirrel & Chameleon \\ \hline FE-GNN(C) & **89.45\(\pm\)0.22** & **81.96\(\pm\)33** & 89.87\(\pm\)0.09 & 67.82\(\pm\)0.25 & **73.33\(\pm\)0.8** \\ FE-GNN(M) & 89.09\(\pm\)0.22 & 81.76\(\pm\)0.13 & 89.93\(\pm\)0.23 & **67.90\(\pm\)0.23** & 73.26\(\pm\)0.38 \\ w/o norm & 86.23\(\pm\)1.06 & 79.23\(\pm\)1.08 & **90.27\(\pm\)0.06** & 40.74\(\pm\)1.06 & 68.25\(\pm\)1.04 \\ w/o \(S\) & 89.20\(\pm\)0.08 & 81.95\(\pm\)0.07 & 89.76\(\pm\)0.06 & 43.21\(\pm\)0.09 & 61.54\(\pm\)1.32 \\ w/o \(P_{\mathrm{L}}(\bar{L})X_{\mathrm{\geq 0}}\) & 71.10\(\pm\)1.74 & 74.38\(\pm\)1.01 & 86.61\(\pm\)0.05 & 67.90\(\pm\)0.06 & 73.35\(\pm\)1.21 \\ w/o \(P_{\mathrm{L}}(\bar{L})X_{\mathrm{\geq 0}}\) & 84.70\(\pm\)1.09 & 58.60\(\pm\)1.29 & 85.84\(\pm\)0.05 & 65.75\(\pm\)0.03 & 72.61\(\pm\)1.00 \\ \hline \hline \end{tabular}
\end{table}
Table 4: Time consumption of SVD

Figure 6: Sensitivity study of truncated SVD