Wide Graph Neural Network
Authors: Jiaqi Sun
Lin Zhang
Guangyi Chen
Kun Zhang
Peng XU
Yujiu Yang
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph neural networks
represenation learning
dictionary learning

Abstract: Usually, graph neural networks (GNNs) suffer from several problems, e.g., over-smoothing (in the spatial domain), poor flexibility (in the spectral domain), and low performance on heterophily (in both domains). In this paper, we provide a new GNN framework, called Wide Graph Neural Networks (WGNN) to solve these problems. It is motivated by our proposed unified view of GNNs from the perspective of dictionary learning. In light of this view, we formulate the graph learning in GNNs as learning representations from the dictionaries, where the fixed graph information is regarded as the dictionary and the trainable parameters are representations. Then, the dictionaries of spatial GNNs encode the adjacency matrix multiplication, while spectral ones sum its polynomials. Differently, WGNN directly concatenates all polynomials as the dictionary, where each polynomial is a sub-dictionary. Beyond polynomials, WGNN allows sub-dictionaries with an arbitrary size, for instance, the principal components of the adjacency matrix. This wide concatenation structure enjoys the great capability of avoiding over-smoothing and promoting flexibility, while the supplement of principal components can significantly improve the representation of heterophilic graphs. We provide a detailed theoretical analysis and conduct extensive experiments on eight datasets to demonstrate the superiority of the proposed WGNN. 

Under review as a conference paper at ICLR 2023
WIDE GRAPH NEURAL NETWORK
Anonymous authors
Paper under double-blind review
ABSTRACT
Graph Neural Networks from the spatial and the spectral domains often suffer from the following problems: over-smoothing, poor flexibility, and low perfor- mance on heterophily. In this paper, we provide a unified view of GNNs from the matrix space analysis perspective to identify potential reasons for these prob- lems and propose new GNN framework to address them, called Wide Graph Neural Network (WGNN). We formulate GNNs as two components: one is for constructing non-parametric feature space, and the other is for learning the pa- rameters to re-weight the feature space. For instance, spatial GNNs encode the adjacency matrix multiplication as the feature space and stack layers to re-weight it, and spectral ones sum the polynomials to build the feature space and learn shared model weights. Instead, WGNN constructs the space by concatenating all polynomials and re-weights them individually. This mechanism reduces the un- necessary constraints the feature space due the concatenation, which avoids over-smoothing and allows independent parameters for better flexibility. Beyond the parameter independence property, WGNN enjoys further flexibility in adding matrices with arbitrary columns. For instance, by taking the principal components of the adjacency matrix, we can significantly improve the representation of het- erophilic graphs. We provide a detailed theoretical analysis and conduct extensive experiments on eight datasets to show the superiority of the proposed WGNN.
INTRODUCTION
Graph neural networks (GNNs) have demon- strated their great potential in representation learning for graph-structured data, such as so- cial networks, transportation networks, pro- tein interaction networks, and chemical struc- tures (Fan et al., [219 Wu et al. [2020] [Zheng let al.) 2022). Despite the success, existing GNNs still suffer some issues in the following. Firstly, the spatial GNNs aggregate the infor- mation from the connected nodes, resulting in the well-known over-smoothing (Cai & Wang 2020). Secondly, the spatial models assume that the features of connected nodes are simi- lar; however, this assumption does not hold in heterophilic graphs (Zheng et al. (022). Thirdly, the spectral GNNs use polynomials to approach arbitrary graph filters (He et al.) 2021 Klicpera et al.) (019) Defferrard et al. 2016). In the absence of layer stacking, the spectral GNNs are exempt from the issue of smoothho However, these spectral GNNs still perform poorly on heterophilic graphs since each polynomial term also shares the same assumption of similarity in neighbors. In addition, spectral methods share the parameters less flexible architecture. To better understand the problems
#=
Σ, spico
Chit spece
P24
PM
Spatial GNN
Spectral GNN
WGNN
Figure 1: WGNN compared with current GNNs
for each polynomial term, leading in both spatial and spectral domains, efforts exist that integrate GNNs, e,g., from the perspective of optimization objectives (Ma al. | Zhu et al. 2021). However, they focus on summarizing general formulas while lacking a clear explanation of the problems.
'The implementation of WGNN is available at
www./o/m/vvveee..ooo 1erss
1A6VWi was.:

---

Under review as a conference paper at ICLR 2023
In this paper, propose a unified view for both spectral and spatial GNNs from the matrix space analysis point of view to investigate possible reasons for these problems and contribute a new way to address them. Specifically, for the sake of theoretical investigations, we first abstract linear approximation of the GNNs following Wu et al. (0119)); Xu et al. (2018a). Then, as shown in the mathematical formulation and implementation structure of Figurell | decompose the components with and without parameters in the linear approximation, where the latter is regarded as a feature space built by node attributes and graph structure (c.g., adjacency or Laplacian matrices), and the former denotes the learnable parameters to re-weight the features. Consider spatial GNNs that 1) build the feature space by taking the power of the adjacency matrix, and 2) form the parameter space by taking the product of the weight matrices. For spectral GNNs, they sum the polynomials to compose the feature space and share the parameter for each. Based on this view, we can identify the reasons for issues in GNNs. When forming the feature space by powers of adjacency matrices, we find that over-smoothing is due to feature space compression. The parameter-sharin manner of spectral GNNs limits the flexibility of their architectures. Besides, the common issue of poor performance in heterophilic graphs is caused by the construction of each feature sub-space that embodies the similarity of neighboring nodes in both methods.
The primary contribution of this work is a wide architecture of GNNs named Wide Graph Neural Networks (WGNN), whose basic architecture shown in Figure [ In partieular, it constructs the feature space by concatenating the polynomial terms of the adjacency matrix. This concatenation avoids space compression caused by powers in the spatial domain and alleviates the over-smoothing problem. To account for the feature space with multiple polynomial terms, the WGNN re-weights each one with an independent parameter matrix. Unlike spectral GNNs, which use a single param- eter matrix for all polynomial terms, our WGNN has better flexibility by allowing different param- eters for each. WGNN architectures also enjoy augmenting the feature space with arbitrary width of matrices. With this characteristic, we can improve the performance on heterophilic graphs by adding principal components of the adjacency matrix. This augmentation reduces the dependency of the feature space the similarity of adjacent nodes since the principal components only tract the graph structure. Comprehensive experiments on both homophilic and heterophilic datasets demonstrate the superiority of WGNN.
Contributions. (1) We provide a unified view of both spatial and spectral GNNs, which formu- lates GNNs as the framework of jointly constructing the feature space and learning the parameters to re- re-weight. (2) We propose a new architecture, WGNN, which avoids over- wwrr-smot,inng enjoys flex- ibility, alleviates heterophily problems, and provide a detailed theoretical analysis. (3) We conduct experiments on homophilic and heterophilic datasets and achieve significant improvements, e.g., an average accuracy increase of 32% on heterophilic graphs
2 PRELIMINARIES
In this paper, we focus on the undirected graph g = (V,E), along with its node attributes of V as X E Raxd and adjacency matrix A E RR to present E. GNNs take the input of the node attributes and the adjacency matrix, and output the hidden node representations, as H = GNN(X, A) E Ruxd, By default, we employ the cross-entropy loss function in the node clas- sification task to minimize the difference between node label Y and the obtained representation as Y) = Σ, Y, log softmax H.)).
2.1 SPATIAL AND SPECTRAL GNNs
Spatial GNNs mostly fall into the message-passing paradigm. For any given node, it essentially aggregates features from its neighbors and updates the aggregated feature,
n((+11 a (upd (n! agg (A,,,1, e ()))
(1)
where a (-) is a non-linear activation function, (A) indicates the hidden representation in k-th layer, agg and upd are the aggregation and updating functions (Balcilar et al. 2021). Á (D +
1/ + () + -1/2 is the re-normalized adjacency matrix using the degree matrix D, and (-) denotes the 1-hop neighbors.
Here, provide two examples to specify this general expression. One is the vanilla GCN (Kipf & Welling 2017) that adopts the mean meen-aggreegttio and the average-update, as shown in the left part of Figure I Its formulation is:
2

---

Under review as a conference paper at ICLR 2023
H(++)) =o (AH =
The second example shows different update scheme with skip-connection (Xu et al. 2018a Li et al. 2019 Chen et al., 2020b), which is defined as follows,
H(++)) (o (+) (((HHHHW H( A
are the transformation where (8) controls the weight of each layer's skip-connection, W(th W(A weights for the initial layer and the previous one, respectively.
Spectral GNNs originally employ the Graph Fourier transforms to get filters (Chung & Graham 1997.. such using the eigendecomposition of the Laplacian matrix: L - In recent years, methods of this type have focused more on approximating arbitrary global filters
U
using polynomials (Wang & Zhang 2022 Zhu & Koniusz 2020 He et al. 202T), which has shown
superior performance and is written as
K
H (0) Px(L))(XW:)W,
(4)
k==
where (.) donates polynomial's k-order term; (8) is the adaptive coefficients and Wi, W2 learnalle parameters. In Figure [ spectral filters are not included in this paper, such as Levie et al. (2018): Thanou et al. (2014).
we replace W, W2 with W()) Note that some instances of
2.2 CHALLENGING ISSUES
Over-smoothing: In spatial GNNs, when stacking layers deep enough, the representations of connected nodes tend to be the same. Unlike deep models with tens of layers, GNNs often have only a few layers, for which there exists relievers such as DropEdge Rong et al. (2020) and the skip-connection scheme (Li et al. 2019 Xu et al. 2018b Chen et al.) 2020b) while having limited effect. Recent research shows that over-smoothing is the result of low-pass filters from spectral perspective (Wu et al. 2019b He et al.) (021).
Homophily and heterophily: Homophily and heterophily are the concepts of differentiating whether connected nodes share the same labels. According to the definition of h [Y; (i,5) E /|E| (Zhu et al., (2020), we consider graph with larger h as more likely to be homophilic, otherwise heterophilic. GNNs were designed for homophilic graphs, making them un- able to deal with heterophilic ones, sometimes even worse than MLPs (Zheng et al. 2022).
Poor flexibility: In spectral GNNs, all polynomial terms share the same parameter matrix due to the concentration on updating the coefficients only, as shown in Figure This learning mechanism, unlike spatial GNNs, form another weight matrix to the next feature subspace by layer- layer-wise multiplications, resulting in the feature matrices of spectral methods being linearly correlated.
METHODS
We propose unified view with a decomposition of the feature space and the parameters in GNNs. The primary motivation for the view is we consider the potential connections among the issues how they use the graph data, i.e., the construction of the feature space. To conduct theoretical investigations of the feature space, we abstract a linear approximation of GNNs based on the success of linearization attempts Wu al. (2019a); Xu et al. (2018a). Specifically, we offer an overall formulation of linear approximation of arbitrary graph neural networks. GNN A) as:
= GNN (CNN(XA)) = T-1
Σ O,(X,
(5)
where &, A) E Raad, is the con-aaraetriic feature space constructing function that inputs the graph data (e.g., node attributes and graph structure) and outputs a feature subspace, θ E IR4 the parameter space to re-weight the corresponding feature subspace for each class c, and T' is hyper- prree--prameter of the number of the feature sub-spaces that the GNN contains. In general, this linear approximation. GNN model forms K feature sub-spaces, i..., b, and outputs the addition of all the re-ihithted sub-spaces using the respective parameters θ, Note that the (total) feature space is the union of the sub-spaces & ( T-1. Similarly, we have the (total) parameters
3

---

Under review as a conference paper at ICLR 2023
- -010))=01,.-.1 Besides, the number of the subspaces T that GNN model obtains is not parallel with its layer/order, for which we will provide some examples in Section 3.1
In what follows, will first identify the feature space & and the parameters θ for the existing GNNs. Then, leveraging the linear approximation, we will introduce our proposed wide-form GNN architecture called WGNN. Lastly, will theoretically analyze the reasons behind the failures of existing GNNs, e.g., over-smoothing and poor performance heterophily, and conclude the superiority of WGNN.
3.1 REVISITING SPATIAL AND SPECTRAL GNNS
Spatial GNNs. We first transform the recursive formula of spatial GNNs, e.g., equation || to an explicit formula, by iterating from the initial node attributes that H (0) = and ignoring the activa- tion function. Following Section 2 consider two examples of spatial GNNs: vanilla GCN (Kipl
& Welling 2017) and the one with skip-connections (Xu al. 2018a).
The linear approximated explicit formula of K K-layer GCN is written as:
H(K) A X
W
(6)
==0
which forms single feature space o = Λ X and parameters On = While equation 3 furthermore considers skip-comnections, whose K-layer linear approximated ex- plicit formula is formualted as:
w with 7 = 1.
K Σ
K-1 II
K + A
((K)_
wiO) j-K-i
A=
By this decomposition, this GCN with skip-connections consists of K+1 feature sub-spaces. It forms each feature sub-space as D A' X. For the first 7 sub-spaces, the according respective parameters denoted as O1æTT-1 = a ( - W(O, and for for the last Qr,
the parameter is OT II [(()) Please refer to the appendix A.1 for the derivation.
Spectral GNNs. Spectral GNNs are specified by the explicit formula equation We remove the activation function, and obtain the linear approximation of a K-order spectral GNNs as:
H(K) Σ (1)
(8)
K=
We put the learnable polynomial coefficient 7 (8) together with the parameter matrices. Also, we combine the shared parametric matrices in equation as W70) = W.W. In this way, equation forms T = K + 1 feature sub-spaces, where each sub-space is denoted as 4, = P.(L)X, and the parameters utilized to re-weight the respective sub-spaces are θ, = ('00
Primary analysis. In Table we summarize more instances of spatial and spectral methods, with different colors to distinguish the feature space & (orange) and parameters θ (blue). It demonstrates that the proposed uniform view can support most of the methods both spatial and spectral domains. Due to the page limits, we put the example of GCNI/Chen et al. (2020)) and ARMA Bianchi el al.) (02T) in Appendix C.8 Compared the general formulation of re- seiiggitting feature sub-spaces, e.g., equation 5 existing GNNs prohibit constraints on both the feature space and the parameter space. We can observe that the feature space of spatial GNNs always constrained by the power of the adjacent matrix, which is potentially related to the over-smoothing problems. Most of the parameters & spectral GNNs are shared for different sub-spaces, which limits the flexibility of adequately re-weighting for each sub-space. Besides, the feature space & in both spatial and spectral GNNs is formulated by multiplication of structural matrices function and node attributes (e.g., 2 P& (L) This multiplication to the node attributes X e I xd demands the feature sub-spaces to obtain d columns, which prevents the feature matrices with other shapes.
4

---

Under review as a conference paper at ICLR 2023
Table 1: The feature space and parameters of the linear approximation for GNN models.
Original Foumula"
Linzur apgecsination feemulation
& Welling
1/ a (artana))
1100 XXI 9aa
GEN
Xa
2018a
1100 a f1ee a Auuergg))) o7""
(10) El A A ae
ol D, whapp HM Ei - of Elid - o1
APPNP
Kliopars clal
2019
ChebyNer
Defferand et
2010
1f EL. Podlaiii
n00 - E P100)X10
2011
BemMett
Ho ct
2021
8 Eihn (2)" 1:
100 = 5.h 11--
(Uhrs)
2 Pol:: Swo1d
2 P.0 20/00 s,000
Without specification 11
X. denoees Chebysher palsnomial 1.
2xP--1
3.2 OUR PROPOSAL: WIDE GRAPH NEURAL NETWORK
Given the observations in the last part, we propose Wide Graph Neural Network, a generalized framework of GNNs that relaxes the constraints as formulated in the following.
H Σ Pa(l)
Σ s,w 1=
It constructs the feature space in two-fold way. The first part inherits the previous GNNs, that the same size of the feature sub-spaces is formed by the multiplication of the polynomi- als of the structural matrix Pa( and the node attributes X. Secondly, we allow the feature sub-spaces Sj with an arbitrary number of the columns, instead of the same columns with X. Beyond these, WGNN utilizes independent parameters matrices W*()) and W() to re-weight each feature sub-spaces to provide flexible re-weighting. To sum up. WGNN forms the feature space of T = K + J sub-spaces, denoted as 4; Ps (f.)x E Raxd similar to GNNs', and @ = S, E R.nxd the additional part with arbitrary columns ones, which compose the total feature space &- = ( K- o2, Respectively, O₂ E Rdxe and O₃ E Rd; xc re-weight them with respect to the objective.
In general, Sj could be any transformation of node features X, graph structure A, or both of them. The feature spaces 4 (L)x Randd provides the usage of the node features X only, e.g. k = 0, and both of node attributes and graph structure, e.g. k >> O. Besides, using node features leads to the dependency of the adjacent nodes' similarity and is parallel the heterophily problem. In WGNN, we break this dependency and form Sj by using the graph structure only. To extract the low-dimension information for the graph structure, we deploy truncated SVD to get its principal components as follows:
S A=
(10)
where denotes that we only use single S,, e.g., = 1. Throughout the remaining context, we stick to truncated SVD as a case for WGNN and delve into it accordingly. In addtion, the empirical results of other transformation functions are given in Appendix Notably, the feature space &x and S may have imbalanced scales and cause poor weiieightnng. We, therefore, add column- wise normalization to ensure each column equally contributes to the whole feature space.
3.3 THEORETICAL ANALYSIS
In this part, analyze the feature space that different GNNs formed to explain the challenges of ovorssmgg and poor performance on heterophilic graphs.
Over-smoothing, The over-smoothing problem occurs when stacking deep GNN layers. We de- scribe this phenomenon by the compression of the column span of the feature space. is de- fined as all the possible column-wise linear combinations of the matrix's columns and denoted as Span )) = {-; a, ";;; a; E R]. We provide Theorem 3.1 to interpret the cause of this issue.
Theorem 3.1. The span of the feature space t A X will be shrunk gradually with the increase of k, which leads to the over-smoothing problem.
Let us first look at the feature space of K-layer vanilla GCN,
A x = (I k U(I - AYT X;
[0,
5

---

Under review as a conference paper at ICLR 2023
(A)
6.94
Modes overtg oistarcc MADAIOA
1-th feature
(b)
Codine smileryy 20 fobd spaces
Homszhlly matrrpp
8.00
space
0-4
600
0.32
34th feature space
th Teature Sotrrcpppac
20
A1
Number the Syyers
Feature Space Index
Figure 2: Visualization of the analysis. (a) collects the distribution of the eigenvalues with increasing powers the adjacency matrix. shifts to zero gradually, which compresses the feature space leads to decreasing the diversity of all the nodes' features, measured by MADetobal Mapelebal (Chen et al. 2020a).. (b) shows the similarity between the later feature space to the previous total improves greatly, leading to marginal extension of the space. (c) compares the similarity of different feature spaces' distances to the labels, where the heterophilic case obtains greater distance and our proposed S can reduce the distance.
It is linear combination of U(T AY using U X, and (I - A)' re-weights U in column-wise. Since A E [0, 2|2, we have (7 - A) E [-1.1]". Along with the increase of K, the weights of some U' columns will approach zero shrink Span(U(L A)'), because
Span (A* X) = Span(U(I -) 1 x) C. Span(U(I
Figure 2 a(a) demonstrates this phenomenon since the distribution of the eigenvalues shifts zero with increasing layers while the similarity of the combination Á X greatly enhances. In this way, over-smoothing occurs due to the limited column span of the feature space that compresses the representations. To alleviate this issue, some modified GNNs using skip-connections that form the feature space as {A* JR=0, that joints successive layer's spaces, that
Span(lA* f== .K) Span(A x) Span(A' (A' X) U ... Span(A*
will not be influenced by the compression of later components, e.g., Span Å K X). and therefore avoids over-smoothing. Similar conclusion can be derived by the feature space of spectral type that forms (ī.* (,*X)x=o,,1... K. Following this, we can understand the performance bottleneck with increasing layers by the similarity of the introduced feature space from later spatial layers / spectral orders the previous ones. Here, we provide quantitative analysis to better describe the property. For this purpose, we take the feature space of spectral GNN (Chien et al.) (22TT) as an example, i.e, X .4 and measure the linear correlation of the appended k-th feature space to the previous ones by calculating the mutual-correlation values:
E
m ixx.))
max
j=0,- 1-1
where i is the index of the column in X and ((Mo, M2) maxd, M.o.d. cos(du, d,) is the mutual-coherence of two matrices, based on the cosine distance cos. In Figure (2b),, we visualize the distribution of (EA) } of all the columns with k 1, 2, 3, 4. It confirms the great improvement of the linear correlation, which results in little expansion of the feature space. Therefore, increasing hardly enhance performance. Although some studies explain
spectral orders or spatial layers
the over-smoothing problem, e.g., Huang et al.) y Oono & Suzuki (201): Cai & Wangl (2020). Our perspective differs from them in the view concept; please refer the comparison we provide in Appendix B.3
Poor performance in heterophily. The majority of GNNs' performance on heterophilic graphs is much worse than on homophilic graphs. To understand this issue from the perspective of matrix space analysis, we study the linear correlation the feature space to the label space. We provide an empirical analysis of the distribution following mutual-coherence values in Figure
1 E
c -
where we randomly sample 60% rows to mimic the training set denoted as T, and report the mean with variance. is the dimension of the matrix of the one-hot node labels, i.e., Y Baxe, It

---

Under review as a conference paper at ICLR 2023
shows the distance between the feature space and the label space on homophilic graphs is much higher than in the heterophilic scenario, which leads to poorer performance in the heterophily case. Besides, we append theoretical explanation from the feature space only, by Theorem [A.] that the mutual-coherence of the heterophiliic feature space, i.e,, p( ), is higher than the homophilic ones.
WGNN compared to spatial and spectral GNNs. Our WGNN provides a new way of dealing with graph data, where both graph structures and node attributes are regarded as the input cues to construct feature spaces. In this way. the complex multiplicative design between the graph structure and node attributes can be avoided and the constraints of feature space are relaxed, which contributes to better model flexibility and generalizability on the heterophilic graph.
From the feature space construction perspective, WGNN utilizes all the sub-spaces from (X).. Compared with the spatial GNNs, the feature space of our WGNN is more flexible as Span( )==,,,...... .K) C Span( (P (L) k= .....)). since it builds the space using all the polynomial terms while spatial GNNs only takes the highest ordered term. This property helps WGNN avoid the over-smoothing problem. Besides, we append a sub-space S to the feature space of WGNN, which is built with the graph structure only. Without using the node attributes, this sub-space is closer to the label space than others that are highly dependent nodes' similarity, and achieve better performance on the heterophilic graphs. As shown in Figure _c),, we demonstrate that the sub-space S helps the feature space approach labels, especially for heterophilic graphs.
From the view of parameters, compared with spectral GNNs, WGNN relaxes all the constraints on the parameters and allows re-weight the feature space independently. In Appendix [A.4, we supply the demonstration of the parameters constraints within previous GNNs. It tells that the constraints on parameters (W()) limit the span of the weighted feature space (see Theorem A.2
4 EXPERIMENTS
We evaluate the proposed WGNN on the following aspects: (1) node classification results, (2) ro- bustness on the challenging issues, (3) ablation studies.
Dataset. We implement our experiments on homophilic datsets, i.c., Cora, CiteSeer, PubMed, Computers, and Photo (Yang et al. 2016, Shehur et al. 2018), and heterophilic Chameleon, Squirrel
and Actor (Rozemberczki et al. 2021 Pei et al. 2020 More details are provided in Appendix C
Baselines. We compare a list of ofate-of-the-art GNN methods. For spatial GNNs, we have
GCN (Kipf & Welling, 2017). GAT (Velickovic al. 2018), GraphSAGE (Hamilton et al.) 2017).
GCNII (Chen et al. 2020b) and APPNP (Kliepera et al. 2019), where MLP is included as a partic- ular case. For spectrals, we take ChebyNet (Defferrard et al. 2016), GPRGNN (Chien et al. 2021
and BernNet (He et al. 2021). Besides, we cover the recent unified models, ADA-UGNN (Ma et al.
2021) and GNN-LF/HF (Zhu et al. (02T). WGNN employs the Chebyshev or Monomial polynomi- als to construct feature space, and we name the corresponding version as WGNN-C and WGNN-M, respectively. Please refer to Appendix C.3 for more details about the implementation.
Table 2: Overall Performance of Wide Graph Neural Networks (WGNN)
Homophilic graphs
Heterophilic graphs
Type
Baseline
Time (ms)
Com
CiteSeer
PuhMed
Computers
Photo
Squirre
Chameloon
Actor
MI.P
16.70
76.67_am
85.11 poss
82.62,na
37 37.86_u 14.16
57.83
1819
GCN
17:42:14
87 69
79.31
86.71 20.
83.24.mm
88.61
47.21
61.85
28.61
Sputial
GraphSAGE
87. 87.74gm 10.72
18.06_1.8
88.07
79.20_e.m
80.80 am
87.65 i0
86.69
87,38
82.86 uaas
23
20.4
48. 15
33.40,mm1
62.45
11.82
33.48
36.39
GCNII
8,48
87.464403
80. 30.76=030
88. 82
2427
93,21
43.28
61.
61.80g044
38.61
APPNP
23,74
87 87.922003
$1.42at22
88, 16
85 2811
90,40
39.63304
29.01
39. 39,90
Cheby Net
20 20.26-1u
87.17 17.17
77.97
89 20.044aace
87.92
94, 94.58
44 44.55
64.064247
25.55
Spectral
GPRGNN
23.55
87 87.97
78.57
86.07 2014
93.99
13.66:u22
63.67
26,93
BerNNett
36.88 jesi
87.66
79,34_
89.33 paon
66.66661 poos
94.03 Lose
41.57
63.07
36.89
GNN-LP
52.77
124405
83.66-200
87.79
87.6 87.632005
93.79
39.03
39.84g20
41.97=30
GNN-HF
53,28
88.474009
83.56=5.10
87.83
$6.9 26.94-000
93.89=a110
39.01
63.90aa11
42.47
Unified
ADA-UGNN
14.36,c21
88.9 88.92
79.34_gm
90.08 jass
89.56 poni
94.66
44.58 juss
59.25 po1s
41.38,a12
WGNN-C
15
89.45
81. 81,96
90.27
90.79 2ans
95,362214
67. 67.82,a25
73.33:a15
40.54
WGNN-M
14.61032
89.09 11:37
$1.76,.oo
89.93 10:3
90.60
95.45 a.15
67.90
73.26
40.91,ame
7

---

Under review as a conference paper at ICLR 2023
4.1 NODE CLASSIFICATION
We test transductive node classification task with random 60%/20%/20% splits and summarize the results 100 runs in T reporting the average accuracy with a 95% confidence interval. We observe that WGNN has almost the best performance on homophilie graphs. Particularly, compared with the current SoTA method ADA-UGNN (Ma et al. (021) which unifies the objectives in both spatial and spectral domains, our WGNN achieves 1.1 % accuracy improvement on average of homophilic graphs datasets. Besides, WGNN obtains 32.0% improvement on average of three heterophilic graphs datasets than the GCN baseline. The excellent performance on both homophilic and heterophilic graphs indicates the potential of WGNN.
4.2 ROBUSTNESS ON THE CHALLENGING ISSUES
Over-smoothing. We evaluate WGNN with different numbers of feature sub-space K on the Cora (homophilie) and Chameleon datasets (heterophilic). Figure indicates that the performance of WGNN will not drop as extending feature space. It is because our concatenating polynomials of adjacent matrices avoids the compression of feature space.
Heterophilic graphs. As shown in Table and Section 4.1 WGNN greatly alleviates the prob- lem of heterophily by supplementing the feature space with only the graph structure to reduce the dependency on nodes' similarity.
Table 3: Ablation study of the components in WGNN
Cora
CiteSeer
PubMed
Squirrel
Chamelcon
WGNN-C WGNN-M
89.45
81.96
89.87 =0.49
73.33 67.82+..6
89.09
81.764a23
89.93
73. 73.26 67.90=a.23
w/o norm w/o S
86.23+143
79.3220.5
90.27=a.49
64.70=1.10
68. 68.25+164
89.20
81.952087
89.76 39.76.20.4
43.21 99
61.54
w/o ( 11.10
74.38
86.61 26.51
67.90 g0.
73.35
w/o Pk X
84.70+1a5
58.60
85.84_n.45
65.75
72.61
4.3 ABLATION STUDIES
In this subsection, we study the contribution of different components in WGNN and answer the following questions.
How does each sub-space affect, e.g,, Pa (L) and S? Pa(L) and respectively matter on homophilic and heterophilic graphs. We evaluate WGNN on 5 datasets of both homophilic and heterophilic graphs in different feature space constructions: including w/o S, w/o Ps (b=X and w/o Pa (L)X which respectively denote building the feature spaces without graph structure, without note attributes, and without the combination of them. In the ablation results of Table 3 we found that w/o works well on homophilic graphs but fails on heterophilic ones, while the other two work oppositely.
Does the column-wise normalization matter? matters when the node scale is not huge. As shown in Table we find column- wise normalization works well in most cases, except for PubMed. may be because the large node scale PubMed causes the tiny value of normalized feature space.
On what ratio of the truncated SVD is adequate? 94% We conduct an experiment using dif- ferent ratios of singular vectors and values to construct i.e., the top j singular values obtains
1.0
5.22
0.74
Test Accuracy
Cumulative singulr
Avcursoy
0.8
-3.00
0..5
WCNN
GPECKN
0.4
SCN
Chubiitt
GAT
cux-iraa
9.2
trecksAcE
USN
0.5
Bemtiit
0.a
1000
2010
30.00
3.78
502
1000
2000
0.58
Training Epoch
Singular
index
Figure 3: Convergence curve
Figure 4: Sensitivity study of truncated SVD
8

---

Under review as a conference paper at ICLR 2023
Ab lation Study of
Dropout=RelU
DropEdge
6.02
0.0
6.44
Ore
0.0
Duarsion
Teas
0.4
0.2
'slyneriial order Karr.
0.0
51
5.2
0.3
Drop Rate
0.4
05
0.5
0.7
0.5
0.5
0.1
0.3
0.5
Drop Rate
0.7
0.9
1-02
1-e3
Cara
CleSect
Prodo
Saaid
Figure 5: Ablation study of
Figure 6: Analysis of the deep artifices on WGNN.
r r= E Vyy/i= Vis ratio of the components. In Figure 4 we report the test accuracy with re- spect to increasing ratios of singular values on CiteSeer and Chameleon, where CiteSeer is robust to the variation of the ratio, while Chameleon shows the best performance at ratio 94%. Thus, we use 94% for other experiments. We offer more interpretation of the SVD results in Appendix C.7
On what order polynomial is sufficient? Three We test progressive order K of the polyno- mials on Cora and Chameleon demonstrated Figure The performance in Cora rises from to 3 and decreases in slight tendency, while Chameleon has minor changes. It suggests that order is good enough to achieve nearly optimal performance. Please refer to Appendix C.5 for more results.
Are dropout (Agarap, 2018) and DropEdge (Rong al. 2020) help? No. We respectively in- tegrate "dropout+ReLU" and DropEdge into WGNN and show the corresponding performance with different drop ratios on four datasets Figure 6 Unfortunately, both of them show worse perfor- mance when increasing the drop rate. It may be because these regularization tricks break the graph structure. Besides, the results also advocate for more attention on the feature space construction, preventing over-applying deep artifices.
we collect the training time per epoch (ms) for each method, which shows that WGNN behaves at a compa- rable time cost to other baselines, such as GCN (Kipf & Welling, 2017). Note that the time we report includes the graph propagation for fair comparison, though WGNN can further reduce by constructing the feature space in a pre- pre-processing manner. This advantage comes from the lower- ordered polynomial feature space and much simpler computation in feed-forward. Please refer to Appendix C33 for more details on the optimal architectures for the baselines. In Figure 3 we com- pare the convergence time for all methods and observe that WGNN consumes the minimum number of training epochs while achieving the highest accuracy.
Is WGNN easy to train? Comparably, yes, and WGNN converges f'ast. In Table 2
Is the SVD applicable in practice? Yes. In Table preprocessing), and their ratio of WGNN. We find the rate of SVD time in whole training time is lower than 10%, which confirms the WGNN's applicability.
show training time, SVD time (as
Table 4: Time consumption of SVD
Cora
CiteSeer
Chameleon
Squirrel
Actor
Training time (ms)
4000.01 52.23
4100346 + 133.77
2818.21 81.87
6096 403.95
6074.39 + 547.34
SVD time (ms)
3.88 + 0.08
8.76 0.05
61.80 + 0.21
432. 122.3345 0.70
3.99 0.02
of epochs
252
252
252
SVD time Training time (%x
0.097
0.21
5 CONCLUSIONS, LIMITATIONS, AND FUTURE RESEARCH
In this paper, we provide unified view to analyze GNNs, which separates the feature space and pa- rameters using a linear approximation. Together, we provide a theoretical analysis of existing chal- lenges under the setting of feature space or parameter space. To address these challenges, we pro- pose a flexible architecture that relaxes all constraints, called Wide Graph Neural Network (WGNN). Comprchensive experiments are conducted to verify its superiority.
Limitations and future research. More general nonlinear cases are not included in our work, such GAT /Velickovic et al. 2018), GateGNN (Bresson & Laurent 2017), and will be considered in future work. The mechanism between the feature space and the respective parameters is worth more effort to optimize; in way, the parameters in the WGNN can be further reduced by introducing reasonable constraints. Finally, since WGNN adopts the same graph structure as node attributes as graph data, more feature space construction methods should be discovered in the future.

---

Under review as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
The code used in our experiments is provided in the supplementary material. For the data sets used in the experiments, comprehensive description is given in Appendix
REFERENCES
Abien Fred Agarap. Deep learning using rectified linear units (relu). arXiv:1803.0837. 2018.
arXiv preprint
Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. Analyzing the expressive power of graph neural networks in spectral perspective. In 9th International Conference Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Graph neural networks with convolutional arma filters. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
Xavier Bresson and Thomas Laurent. arXiv:1711.07553, 2017.
Residual
gated
graph convnets.
arXiv preprint
Chen Cai and Yusu Wang. note on over-smoothing for graph neural networks. arXiv preprint arXiv:2006. 13318, 2020.
Deli Chen, Yankai Lin, Wei Li. Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over- smoothing problem for graph neural networks from the topological view. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pp. 3438 3445, 2020a.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph con- volutional networks. In International Conference on Machine Learning, pp. 1725-1735. PMLR, 2020b.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovie. Adaptive universal generalized pagerank graph neural network. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
Fan RK Chung and Fan Chung Graham. Spectral graph theory. Number 92. American Mathematical Soc., 1997.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The world wide web conference, pp. 417-426, 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Mingguo He, Zhewei Wei, Hongteng Xu, et al. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. Advances in Neural Information Processing Systems, 34, 2021.
Xiangnan He, Kuan Deng, Xiang Wang. Yan Li, Yongdong Zhang, and Meng Wang. Lightgen: Simplifying and powering graph convolution network for recommendation. In Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, pp. 2020.
Kenneth Hoffman and Ray A. Kunze. Linear Algebra. PHI Learning, second edition, 2004. ISBN 8120302702.
Wenbing Huang, Yu Rong, Tingyang Xu, Fuchun Sun, and Junzhou Huang. Tackling over- smoothing for general graph convolutional networks. arXiv preprint arXiv:2008.098864 2020.
10

---

Under review as a conference paper at ICLR 2023
Thomas N. Kipf and Max Welling. Semi- Semi-supervised classification with graph convolutional net- works. 5th International Conference on Learning Representations. ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
Ron Levie, Federico Monti, Xavier Bresson, and Michael M Bronstein. Cayleynets: Graph con- volutional neural networks with complex rational spectral filters. IEEE Transactions on Signal Processing, 67(1):97-109, 2018.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? In Proceedings of the IEEF/CVF international conference on computer vision, pp- 9267-9276, 2019.
Yao Ma, Xiaorui Liu, Tong Zhao, Yozen Liu, Jiliang Tang, and Neil Shah. A unified view on graph neural networks as graph signal denoising. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 1202-1211, 2021.
Sunil Kumar Maurya, Xin Liu, and Tsuyoshi Murata. Simplifying approach to node classification in graph neural networks. arXiv preprint arXiv:2111.06743 2021.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node 2019. 2019.
classification. arXiv preprint
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05288 2020.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. 8th International Conference on Learning Rep- resentations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael Bronstein, and Fed- crico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004.1 7:15, 2020.
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Nenworks, 9())cnab014, 2021.
Chuanqiang Shan, Huiyun Jiao, and Jie Fu. Towards representation identical crivacy-presenvee graph neural network via split learning. arXiv preprint arXiv:2107.055)) 2021.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: /8/ / 1.05868, 2018
Dorina Thanou, David I. Shuman, and Pascal Frossard. Learning parametric dictionaries for sig- nals on graphs. IEEE Trans. Signal Process. (2( 3862, 2014. doi: 10. 109//S//S4.2 2332441. URL
11000.119999990 -tD.PP.22000 2014 2332441
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings, 2018.
Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. In International Conference on Machine Learning, 2022.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinherger. Sim- plifying graph convolutional networks. In International conference on machine learning, pp- 6861-6877 PMLR, 2019a.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International conference on machine learning. pp- 6861-6871. PMLR, 2019b.
11

---

Under review as a conference paper at ICLR 2023
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4-22) 24, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In International Conference on Learning Representations, 2018a.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning, pp. 5453-5462. PMLR, 2018b.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pp. 40-48. PMLR, 2016.
Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip S Yu. Graph neural networks for graphs with heterophily: A survey, arXiv preprint arXiv:2202.07082 2022.
Hao Zhu and Piotr Koniusz. Simple spectral graph convolution. In International Conference on Learning Representations, 2020.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33:7793-7888 770044 2020.
Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui. Interpreting and unifying graph neural networks with an optimization framework. In Proceedings of the Web Conference 2021, pp. 1215-1226, 2021.
12

---

Under review as a conference paper at ICLR 2023
Appendix
CONTENTS
Introduction
2
Preliminaries
2.1
Spatial and Spectral GNNs
2.2
Challenging issues
3
Methods
3.1
Revisiting spatial and spectral GNNs
3.2
Our proposal: Wide Graph Neural Network
3.3
Theoretical analysis
4
Experiments
Node classification
4,2
Robustness the challenging issues
8
Ablation studies
5
Conclusions, limitations, and future research
Proofs
14
A.I
Derivation of equation 7
14
A.2
The column- normalization in current GNNs
14
A.3
Explaining heterophily from the perspective of feature space
14
A.4 4.4
Parameters constraints in previous GNNs
15
Related work
17
B.1 Efforts on unifying separate GNNs
17
B2 Shallow models
17
B.3 Other analytical views of over- wer-smoothing
18
Experimental settings
18
Dataset details
18
Details about optimization and reported results
19
Searching space for baselines hyper-parameters
19
Other transformations for compacting the graph structure information
20
Results of WGNN using different polynomial orders
21
C.6
A Deeper Study smoothig
C.7 More comprehensive study of SVD
21
13

---

Monomial polynomial Under review as a conference paper at ICLR 2023
C.8 Feature space and parameters for more GNN models
22
A PROOFS
A.1 DERIVATION OF EQUATION 7
Iterate equation 3 from ( X, we have
( X
(11)
n (0) XW Áx
(12)
((2) = ( ('W(' + (o) XW w + d w(
(13)
H(3) (2) (2) (W) + taa X w(2)
(14)
+ A'a w/
(15)
(16)
Identify the rule of the iteration, we obtain
1-1
H
H = Σ 0
(K)
+
A'x
II w(t)
(17)
1=0
h=0
where 6/0) calculate by:
8, (a (1-)
A (1-10)
II w j=(=)
(18)
We apply equation 18 on equation 17 and put (k-1-1) back to the learnable parameters W (-(h---))
and the result of equation is achieved.
A.2 THE COLUMN- WISE NORMALIZATION IN CURRENT GNNS
Here, we include some 10-ordered polynomial functions, see the different column-wise nor- malization response from these models. Column-wiss normalization are defined as enforcing [|F,112 1, where we take as the concatenation of the feature space. We extend this to an arbitrary l times of F21l2 1, i.e., F. ll = k, which equals to measure the extent of the consis- tency of each ||F,l Therefore, we report the standard variance of [I| ||2; = 1,2, ...) ), and the smaller value suggests greater response of column-wise normalization.
Table 5: The column-wise normalization response for different polyonmials on Cora
ChebyShev polynomial
Bernstein polynomial
Cora
3.8246
4.7044e-06
0.4947
CiteSeer
34.6432
0.0023
24.4 24.4430
Chameleon 660.4274
0.7308
1039.2469
Squirrel
245.6538
0.7063
700.9365
Chebshev, Bernstein and Monomial polynomials are compared in Table 5
Bernstein polynomial
produces the least variance, suggesting encourages the most atomicity compared to other polyno- mials. This observation aligns with the narrative in the original paper of BernNet He et al. (2021) where the authors claim the Bernstein polynomial more numerically stable than other polynomial functions.
A.3 EXPLAINING HETEROPHILLY FROM THE PERSPECTIVE OF FEATURE SPACE
Theorem A.1. The mutual-coherent of the heterophilic feature space, i.e., u(LX), higher than the homophilic ones.
14

---

Under review as a conference paper at ICLR 2023
Proof. In binary classification task, assume the node features be draw from two separate p-dimensional multivariate Gaussian distribution Du = N ( Eo) and D1 = N Σ1), cor- responding to class Co and e₁. Σn. 2j are both diagonal, ie.., for all ú, # dimensions independent. The node features are equally sampled from the two distributions, X = { Ru ~ Do U ( The Di), } where each includes samples. Without loss of generality, suppose two columns from X that dj 1 dj. Equivalently, this leads to:
df dj
E FusJFa +
Σ DnrD1
Fut
(19)
nF((Do Doj) + nF((D;:);)) nE(Doi (((a))) + (E(D):))(()))
(20)
(21)
alPosMos + p2:/115)
(22)
O.
(23)
Note that for obtaining (64), we use the law of large numbers, e.g., E = A. So far, we have a equation MooMoi + Phipi from this orthogonality, which is the only equation that our assumptions hold.
Next, examine the effect of L. def d,. L is employed by left-hand side multiplication, which equals to row-wise transformation of d; and dj. We consider two extreme cases of homophily and heterophily, respectively.
Firstly, for homophily, L only acts with the nodes that from the same class, For simplicity, if each transformation is averaged, i.c., Lij row-wise normalized, Do and Dj remain the same. Therefore, the orthogonal relation remains.
Secondly, L combines the nodes that from different classes in heterophily, this situation, Do and Dj shift to D/= = N 1oi, Eo + Σn) and Dj = N( po: Eo + Ez). Here, we rewrite the alignment from (65):
d nE(Do:)E((o)) nE(P)))))))))) =
(24)
n(Hos - 1111) (M4) - m11) + n(H1e moi) - Mos))
(25)
2n(Moi M1)) M1j)
(26)
2n(Houtoas + (1iH11g) - 2m (mool1 + pisHos)
(27)
-2m(Hus/11 M1sMoj).
(28)
Based on this, the condition of orthogonality will not be held because Mostii + PiaMoj not equal to zero.
To sum up, heterophily breaks the limiting orthogonal condition, while homophily does not. Ex- tensively, the LX columns are more easily to be mixed in row-wise, losing their distinctiveness mutually. In other words, increases the nutual-ccherema of LX, for the definition below.
Definition A.1. The mutual-coherence of matrix A E R is the maximal inner product between columns from these two bases,
m(A) = max 10 az/.
(29)
15t,5n
where each column is normalized as |la,|12 = 1, in
Based on this analysis and definition, we find that the mutual-coherence of the feature space in heterophilic graph, e.g., LX, is more likely greater than that of homophilic one. As a consequence, this phenomena will be superimposed in the overall feature space F [[[Px(L)X; 0, K} to undermine the power of the feature space.
A.4 PARAMETERS CONSTRAINTS IN PREVIOUS GNNS
Theorem A.2. The span of the feature space o = A will be shrunk gradually with the increase of k, which leads the ovor-sngg problem.
15

---

Under review as a conference paper at ICLR 2023
Proof. We summarize the constraints W in current GNNs the following: i) in the case of MLP-based implementation He et al. (2200) all layers share the same W, which forces the layer- wise representation parameters into single matrix; and ii) in the case of layer-wise W Kipf & Welling 2017) Li et al. (2019), each Wk+1 is built upon its previous one, i.e, WK+1 = I W,- We extract the ideas of these constraints into the following example. Suppose a linearly correlated feature space U (dg, (.o.dd,Agde Agdn, A did,, where do 1 di d2 R E Span(do. d1} need to be recovered by the elements in U"
We deploy the aforementioned two types constraint on the undecided variables by, bn, b2, and by: i) by bo. by b1 and ii) b2 = pdo. by مفبر where μ is trainable scalar. They align with the graph neural networks. We begin by discussing these two cases.
Representing x in the first case, yields:
bodo + bidı + boAado b1
(30)
= = to)bodd + (1 + A1)61d1.
(31)
Using the unique representation theorem Hoffman & Kunze (2004). we have (1 + Aa)bo = ag and (1 λ1)bi a1. Put it in matrix multiplication format:
bo
11
0
Au
0
b1
au
010
0
A1
bo
a
(32)
bi
which produces:
(1+ 1 X1
(bo
app
(33)
(i
a1
holds the closed form that bp [1+
on
b1 = (I+A1)'
81
Then, we represent x in the second case:
x bodo + bidi + pbo + μu1 d1b1
(34)
(1 + booo + (1 +1+ pd1)bid1,
(35)
which produces (1+pAg)bb ag and (1+ (1+1)1)6 a1 Formulate them in a matrix multiplication:
bo
1
(
0 Ao
0
bi
an a1
A
pubo
=
(36)
pb1
This under-determined system and gives bo (1++Aa)
bi
[1+MAr) b2
p0g
and
[I+pAa]*
b3 [T+AA)]
We look into the values of by to get the expressivity of the base D. Given the extreme case where Ag + O, the appended Ågdo is constrained while the original one keeps expressing. On the contrary, when Ao
the original base do is constrained by [T=Aa] or [1+ while the appended one expresses. Besides, for the second case, when μ 0, the corresponding bases limited by
by, by + O. Consequently, both cases lead to partial expression of the feature spaces.
Finally, comparing these two cases, i.c.. (59) and (62) (55), we find that they merely restrict the parameter space of (bo, b1, b2, bz)" by either sharing the values of each other or enforcing their linear dependence. Therefore, restricting the parameter space in these two cases leads to partial expression of the feature spaces. This proof is completed.
In the following, we provide the norm of the learned parameter matrix respect to each column of the feature space, shown in Figure 7 We find that existing GNNs' parameters are limited leaving significant part of feature space unexplored. Differently. WGNN abandons all the constraints of the parameters and allows all the columns to be re-weighted.
16

---

Under review as a conference paper at ICLR 2023
Responoe
LightGCN
Desporte
GPRGNN
0.00
0.00
WGNN[Ours)
Wesppooos
0.05
Subdictonary 1 Subdictionary Subdictioary
Subdictionary
Figure 7: We present expression the feature space. Y-axis marks the respective norm of parameters, i.c., [Wl of each F.,, and x-axis shows the index the features spaces from different spatial layers or spectral orders. WGNN relaxes the constraint on the parameters, leading to full expression on the feature space.
B RELATED WORK
B. EFFORTS ON UNIPYING SEPARATE GNNS
Balcilar et al. (202T) 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. For example, GCN (Kipf Welling 2017) obtains the convolution matrix of ò 1/2 AD- -122 leads to the filter of &GON (A) Ro
1 Xp/ (p 1). This work causes attention to the unified perspective viewing GNNs, though they
fail to explain the existing progress and issues in spectral view.
Ma et al. (2021) regard the aggregation progress of GCN (Kipf & Welling 2017), GAT (Velickovic
et al. 2018), and APPNP (Klicpera et al. 2019) as graph signal denoising problem, which aims to recover clean signal H from min H X +c tr H I.H). Given this, the authors consider
generalize the smoothing regularization term to Eiev C./2 |H. H,/ /d, and propose ADA-UGNN. However, it also lacks the understanding over-smoothing or heterophily.
Zhu et al. (2021) give more comprehensive summary of GNNs from optimization view, which partly overlaps with Ma al. (202T)'s s opinions graph signal denoising. Based on their conclusion, they propose GNN-LF/HF with parameters adjusting the corresponding objective, e.g., GNN-LF approaches minH ( x) + (1/a- 1) tr [1"LH] and behaves as a low-pass filter. They attribute over-smog to the absence of original features and overcome this issue in their proposal; however, heterophily is untouched either.
In general, these integrated perspectives lack the explanation of the issues, but focus on general formulas.
B.2 SHALLOW MODELS
Rossi et al. 2020) practices to device the aggregation a pre-processing way, which is similar our idea of feature space construction. However, they focus large-scale scenarios by removing sampling and aggregation operations from the training.
SIGN
FSGNN (Maurya et al. 2021 implements feature selection on GNNs, similar to feature sub-space selection. Nevertheless, it combines all the sub-spaces by one linear transformation, which under- mines the ability to understand the contribution of each part.
17

---

Under review as a conference paper at ICLR 2023
These shallow models empirically approaches the idea of feature space, since they will not per- form better on in deep models. Besides, concatenation is also an instance of the feature space concept. which is adopted by many spatial GNNs. In our view, these observations and modifications are are framed as a method to expand the feature space.
B.3 OTHER ANALYTICAL VIEWS OVER- SMOOTHING
As we mentioned in Section B that several works exist explaining over-smoothing problems (in- cluding those you mentioned). However, the view concept of our perspective, i.c., matrix space analysis, is different from the existing ones. Oono Suzuki (2019) propose one of the most ac- cepted views, which is later followed by some literature Huang et al. (2020); [Shan et al. (202T) They assumes stable point of node feature made by the node degrees and proposes that whatever the initial node features are, some nodes will converge to the stable degree feature, with the layer going infinitely, which is depending on the node's corresponding eigenvalue. given feature on the top of node-degree and converges to 0 when sλ < 1. For concise, let us call it degree-vien It analyzes from the row-wise perspective of the feature space. And some studies are also from row-wise aspect by measuring the global Dirichlet energy of the node features Cai & Wang (2020)
details, the prove
that (X S (sA)'d where d d (X(9) is the distance
Differently, our view starts from the column-wise of the feature space by comparing the (column) span of the feature space that extended. In particular, we factorize the feature space, for example, L'X, the bases (column-wist composed by the eigenvector matrix U (of L). Each column is re- re-weighted by the corresponding eigenvalue A then expressed by the static weight matrix U X. Therefore, we consider the feature space spanned by the columns of UA* using the weight matrix U X, which is different from the node/row perspective from the degree view.
Moreover, our view can potentially explain the inferior performance on heterophilic datasets than on homophilic ones. By Thm B. we can see the mutual coherence of the feature matrix (e.g., LX) is higher in heterophilic settings, leading to shrunk feature space.
C EXPERIMENTAL SETTINGS
C.I DATASET DETAILS
The datasets are concluded in Table with licenses. monly used homophilic citation networks Yang al. 6) Computers and Photo are homophilic co-bought networks from Amazon Shchur et al. (2018). For heterophilic datasets, we utilize hy- perlinked networks Squirrel and Chameleon from Pei et al. 2020), and Actor, subgraph from the film-din comm-director-ccae actor network Rozemberezki et al. 2021p. PyC are employed to get these data. Each datasets split into three parts using random selection: 60% the training set. 20% the vali-
Cora, CiteSeer, and PubMed are com-
dation set, and 20% as the test set. We set these datasets to undirected graphs as we assumed in the Preliminaries.
Table 6: Statistics of Datasets
Cora
CiteSeer
PubMed
Computers
Photo
Squirrel
Chameleon
Actor
[V
2,708
3,327
19,717
13.752
7,650
5,201
2,277
7,600
5,278
4,552
44,338
245,861
119,081
217,073
36,101
30,019
h(g)
0.81
0.74
0.80
0.78
0.83
0.22
0.23
0.22
d(g)
1.95
1.37
2.25
17.88
15.57
41.74
15.85
3.95
"Chameleon, Squirrel: http://ahhccoooeeeeeeeeeoeceeo/e
'Cora, CiteSeer, PubMed, Actor: http:///tewwwkkkppppsoeeoooooppp
*Computers, Photo: http:///hhhlonoooooog//oocooo//e
18

---

Under review as a conference paper at ICLR 2023
C.2 DETAILS ABOUT OPTIMIZATION AND REPORTED RESULTS
We report the average accuracy (micro Fl score) in the classification task with a 95% confidence interval in all the tables and figures. For each result, run 100 times 10 random seeds. Besides, we present the standard variance of Table 2 the Table 7 followed:
Table 7: Overall performance of WGNN compared to the baselines with reporting the standard variance.
Cora
CiteSeer
PubMed
Computers
Photo
Squirrel
Chameleon
Actor
MLP
76.70
76.67_0.0
85. g0.1
82.62
84.16ga4s
37.86
27.83
38. 28.9
GCN
87.69 11.9
79.3 11.0
86.7 10.0
83 24 10.2
88.61 11.6
47.21
61.85
28.61
GAT
88.07 1:44
80.80_o.9
86.69 10.43
82. 122
90.84_1.12
33.401459
$1.82
33.48
GraphSAGE
87. 87.74
79.20 1.44
87.65 87,65 =0.51
87. 87.38
93.59=007
48. 48.15+159
62.45
36.39
GCNII
87.46
80.76-1.05
20.82
84. 40.75
93.21
43,28
61.80
38.61
APPNP
87.92
81.42_0:05
88.16
85. 88
90.40.21.20
39.63
1..0
39,90+038
ChehNet
87.17
77.97
89.04.0042
87.921005
94.58
44.55
64.06
25.55
GPRGNN
87.97 17771.25
78.57 -8.57_1..6
89.1 10.44
86.07 10.71
93,99
43.6611.2
63.67
36.931130
BernNet
1..6
79. 1..6
89.33
88. 66.4.444
94,03
44.57
63.07
36.89
GNN-LF
88. 20.06
83.66-4.06
87.79
87. 87.63
93.79=a0s
39.03+ans
59.84
41.97-aas
GNN-HF
88.47 :0.00
83. 33,56-0.10
87.83
86 36.944006
93.89-a01
39.01+a51
63.90go.11
42.47
ADA-UGNN
88.9220.11
79.34_00.0
90.08 20.05
89.56g009
94.662am
44.58
59.25
41.38
WGNN-C
89,45
81.96_1.18
89.87.004
90,79
95,36
67.82
73.33
40,54
WGNN-M
89.09 11.22
81.76_1.17
89.93
90.60
95.45
67.90
73.26
40.91
w/o norm
86.23
79.32_0.78
90,27
89.43
94,94
64, (4.70
68.25-230
37.46
w/o S
g..20
81.95_1.16
89.76.0.65
89. 89.10
94.56.a077
43.21
61.544212
40.89
wfo Ps
71.10-241
74.38-20056
86.61 20.75
89.58.20.5
94.90.a04
67.90.
73.35.1.
38.444101
w/o Po
84.70
58.60
85.84
90.022a032
92.92.a72
65.75
72.61
25.89
We employ Adam for optimization and set the early stopping criteria as warmup pluses patience of 200 for maximum of 100 epochs. We conduct all the experiments on the machine with NVIDIA 3090 GPU (24G) and Intel(R) Xcon(R) Platinum 8260L CPU 2.30GHz.
C.3 SEARCHING SPACE FOR BASELINES HYPER-PAR
For WGNN, we turn the following hyper-parameter by the grid search.
Learning rate: {0.01, 0.05, 0.1}
Weight decay: (0.0005, 0.001, 0.005, 0.01, 0.02, 0.05}
S for homophilic graphs: {0, 50, 100, 200, 500, 1000, 2000}
S) for heterophilic graphs: (500, 600, 700, 800, 900, 1000, 1500, 2000}
Suggested |S]: the whole hundred from the 94% singular values
Hidden size: 64
Ranks & of the polynomial (L)::: 2,
Table 8: The universally used hyper-parameters for WGNN.
weight decay
[S]
hidden
k
Cora
0.01
0.01
64
3
CiteSeer
0.01
0.02
100
64
I
PubMed
0.01
0.005
100
64
3
Computers
0.01
0.0005
1000
64
3
Photo
0.01
0.0005
500
64
3
Squirrel
0.01
0.001
2000
64
3
Chameleon
0.01
0.0005
700
64
3
Actor
0.01
0.001
10
64
0
19

---

Under review as a conference paper at ICLR 2023
Table 9: The turned hyper-parameters for the baselines.
weight decay
dropout
bidden
layerstanks
others
MLP
(0.01,0.05
0.0005
(0.5, 0.6, 0.8)
64
GCN
(0.01, 0.05)
0.0005
{0.5. 0.6. 0.8)
64
[2.3)
GAT
(0.01. 0.05
0.0008
(0.5. 0.6, 0.8
64
[2,3]
Ronda: (18)
GraphSAGE
(0.01.0.05 0.05
0.0005
(0.500g 0.6, 0.8)
64
[2.3]
GUNI
(0.01, 0.05)
0.0005
0.5
[2.4.00)
0,001,00,00,0000
APPNP
(0.01,0.05)
0.0005
0.5
64
(2.3.4.588)
ChebNet
10.005.
0.0005
0.21.
GPRGNN
(0.005, 0.01, 0.05)
{0.0, 0.0005)
0..1,
64
10
prop (0.00000000000.00.000000...
BemNet
(0.005,
0.05)
{0.0. 0.0005)
0.2, 0.5)
prop.ir:(0.0 0.1. 0.2, 0.5, 0.6, 0.9)
ADA-GNN
(0.05, 0.01)
(0.0005, 0.00005)
(0.200.5.0.8)
64
(2,5.10)
a. (0.1. 0.2. 19.19919.29;
GNN-LE
0.01
0.005
0.5
0.9)
GNN-HE
0.01
0.005
0,5
64
10
0, [0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.8. 0.9)
Table represents the syper-pprammters searched for the baselines used in experiments. We prioritize their original released code repository, and the ranges of turning parameters are according their papers.
MLP, GCN, GAT GraphSAGE, APPNP, GCNII implemented with PyG.
ChebNet implemented according the code style BernNe//GPRGNN.
GPRGNN is implemented according to its original code repository.
BernNet is implemented according to its original code repository.
ADA-UGNN is implemented according its original code repository.
GNN-HF/LF are implemented according to its original code repository.
10
C.4 OTHER TRANSFORMATIONS FOR COMPACTING THE GRAPH STRUCTURE INFORMATION
We append other possible transformations to extract compacted information from the normalized adjacency matrix Å. In details, we compared:
KernelPCA: PCA method using non-linear kernel, where radial basis function (RBF) is used.
FastICA: fast version of independent components analysis, which a linear method.
IsoMap: nonlinear dimensionality reduction method based on spectral theory.
All of them can be easily implemented by sklearn package. As shown Table TO our chosen truncated-SVD has comparable performance and we stick with this to make further analysis in the main text.
Cora
CiteSeer
Chameleon
Squirrel
Photo
None
89.20 0.93
81.95 + 0.87
61.54 = 1.52
43.21 t 0.99
Truncated-SVP (Ours)
89.45 + 0.22
81.96
0.23
73.33 0.35
67.90 0.23
95.45 0.15
KemelPCA (non-lincar)
88.61 + 0.82
81.99
1 1.11
73.66 = 1.45
68.79
1.13
95.36 0.51
FastICA (lincar)
88.77 + 1.09
81.92 1.00
73.32 = 1.37
68. 12 0.97
95.30 + 0.22
IsoMap (non-lincar)
88.54 + 0.86
82.07 = 1.15
67.00 = 1.54
54.47 0.87
94.88 0.34
Table 10: Comparing the transformations in compacting the normalized adjacency matrix
hhups://ghhbb.ommyyyeeee/yyoror geomerric
20

---

Under review as a conference paper at ICLR 2023
C.5 RESULTS OF WGNN USING DIFFERENT POLYNOMIAL ORDERS
In the main text, we implement the polynomial order K within the range of three based on the empirical observations, e.g., Figure Here, we provide more comprehensive results for different choices of K.
Table
11 indicates that we may find better K wider range, while the improvement possibly marginal.
K
7
Cora
89.60 + 0.30
89.44 = 0.25
89.52 + 0.26
89.35
+ 0.24
89.34
0.22
89.08 1 0.25
CiteSeer
80.66 + 1.09
81.15 + 1.06
81.11
+ 0.89
80.83
+ 1.07
80.54 1.03
80.10 1.02
Computers
91.01 + 0.46
90.90
0.51
90.98 + 0.42
90.77 00.77:1000 0.39
90.82 0.41
90.45 1 0.32
Chameleon
T3.42 + 0.40
73.69
0.43
73.62
1 0.43
73.68
0.42
73.80 0.39
73.75 1 0.38
Squirrel
68.26 + 0.78
68.41 0.88
68.55
+ 0.82
68.83 + 0.68
68.92 = 0.76
69.06 + 0.93
Table 11: Comparison of different K within 10
C.6 A DEEPER STUDY OF OVER- AVER-SMOOTHINS
In this section, we append a more concrete study of over-smoothing problem. Specifically, we test WGNN with K (10, 20, 30, 40, 50, 60, 70, 80} and compare with a representative method GCNII that overcomes over-smoothing. The results of Table verify the effectiveness of WGNN on avoid- ing over-smoothing which expresses superior capability as Residual Connection and DropEdge and including Dropout,
achieve comparable results with GCNIL. Note that all the DropEdge, a, for SkipConnection and GCNII searched within (0.2, 0.8}.
C.7 MORE COMPREHENSIVE STUDY SVD
In the main test, append the results CiteSeer and Squirrel to better verify the importance of principal components of extracting information from adjacency matrix into SJ- As shown in the Figure X below, both 1) have a more smoothing distribution of the singular values and 2) the information from graph structure is less important as the node features and their interaction, therefore, the change of the performance is more stable with introducing more principal components. On the other hand, Chameleon and Squirrel 1) have more centralized distribution of the singular values and 2) graph structure is more important information, resulting an tendency of the performance that increases first and then decrease. In general, we can achieve a satisfying results on both kind of datasets when 94% principal components are inclusive.
find the precisely results
shared in Section 4 Cora and CiteSeer
Here, we offer more intuition about using principal components. The principal components project and summarize larger correlated variables into smaller and more easily interpretable axes of vari- ation. It is ideal for S, to embody the graph structure information from adjacency matrix, because the adjacency matrix is sparse and high-diiennioonl but each nodes are topologically correlated. However, the different components need to be distinct from each other to be interpretable otherwise they only represent random directions, which leads to noise.
Garedee Snsetare Seeeea
3.0
Coro
Clecoer
0.00
Chamsleon
Squiral
0.8
06-
0.00
0 8.700
075
0.00
0.05
0.6
0..5
0.4
032
1.76
+.50
02.
0.72
0.000
0..05
1000
2000
0
1000
2000
3000
1000
2000
2000
4000
Singular Vilu Irdex
Singular Value Index
Singular Vilue Incles
Singula Value Indec
Figure 8: More results of SVD
21

---

Under review as a conference paper at ICLR 2023
Table 12: Studying Ovor-smog on WGNN, DropEdge, SkipConnection, and GCNII
Chameleon
Squirrel
Cora
SkipConnection
SkipCon Connectton
SkipC CkipCommt oonnection
SkipC SkipCommede ConCocctiion
DropEdge
DropEdge
DropEdge
GCNII
WGNN
GCNII
WGNN
GCNI
WGNN
K
42.27 +0.50
42.27 + 0.50
27.95 + 0.98
68. + 0.50
60 00.50- 1 0. 0..55
60.5 50.50-1 0.
30.67
74.02-4
74.00
1.88 F
63
4 2.03
+
11
1.000
1.44
0..50
1
38
41.33
41 11.39 -
28.42
T 22.71
87,80 08
+ 1.998
0.30
1.
- 13550
12
T
TT
111
T 00
T
08 11 11 201
+ 10000
20
11
90 1
80 L
23
0F
0F
52
$1.50
11.90
27.80
92 SS
1 17 1072
9172 F 00/25
DF F 163180
8L + 86
201 F 09 88
1910 T D94
090
0%
11000
9F 3
055
10000 11100
+ 92288
50 T. 91 59
9183
18TH
81TH
19:1 F 20030
19 + 88
69'0 80'88
OF
OF
155
11
80
22
OF'O T. 57'06
98 T 29
8T
14 - 02'88
0 28
C0' 19
220 86
04
= 22833
9002
-
F
18
000+0000
850
05
09'0
88
1900
220
04
10
10
- 06:00
T. 08 38
T. 08 98
T 26
33 + 2.'88
0 + 00'88
7.'0 16109
89' + 26 88
-
09
1XX
0.1
300
380
1//
1910 = 08500
1550 = 15:08
NUT = 02188
00 + 29
T. 96 84
T 85
89
T 12
177 T 18
1 18
70'0 + 18'98
04 2 1 62
02 + 86 28
O0
090
60
28 1
0.'0 = 90'00
F' = 910 00000
86'0 + (1 20
01 90
19'0 09 89
0.'1 T. 09 89
10' T T9 T6
STT T 40
8T.0 F 91' 88
I'L FLLF-0E 68 988
9'8 + SF 9R
4.'0 + 22 38
02: +
08
C.8 FEATURE SPACE AND PARAMETERS FOR MORE GNN MODELS
Here, we present Table D in a more friendly way (with a larger scale and rotated 90 degrees), with adding GCNIICCen al. 2020b).
22

---

Under review as a conference paper at ICLR 2023
Table 13: Feature Space and Parameters for More GNN Models
** TTy (z) denotes Chebyshev polynomial P.(e) =1, - = R.)) 2 P
WONN (Ours)
BernNet 2021
GPRONN Chien et 2021
Cheby Defferrurd et ml. 2016 T>
APPNP Kliepera
ARMA
GCNI Chen
GiN Xu al
GCN Kipf & Wetting 2017
Without specification, FF = X.
Biuchhi et al.
20 8a
20206
2019
2011
H = S PuL)xIIM + SwW
H ==> 2n A (222 Ly (X
II = De of
+aatin (910) = ( jWa 11 D XXii)
1100331 (1 oorzi
H00 afHii Mow XWW)
mo0n a ((( oelii oo oold
(00+0 =a (600)) +
H((+3) =o (
Original formula""
A )
(() loee + Sommgee Sarean
H = >> p + syma
1000 - (2) -x-B
IENN) Σ 2
1100 > p.())
(18) = EE Al +
11153) - Les
HO0 = Eee A X
H00 = A XIXX 10:0
Linest Linesraapae ap upproociatiin formulation
(0 a dgt (nttmmn (i I% T i 1h orr
+EE off - 2
(
23


Reviews:
[{"review_id": "wVWSEDT8J-", "reviewer": "Reviewer_Hwom", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This article introduces wide graph neural networks (WGNNs). The structure of WGNNs is inspired by an analysis of oversmoothing in linear GNNs. Experiments are presented in which WGNNs achieve SOTA in several benchmark tasks, especially in the setting of heterphilic graphs.", "summary_of_the_review": "This article proposes wide graph neural networks (WGNNs), which are linear classifiers over features given by polynomials in the graph adjacency matrix and its individual singular vectors. Somewhat surprisingly, WGNNs achieve SOTA on a range of homophilic and heterophilic benchmark tasks, achieving especially impressive gains on the heterophilic tasks. While the authors use a significantly simplified analysis of linear GNNs to motivation WGNNs, I did found their analysis to lack in novelty and not be related to WGNNs directly. ", "strength_and_weaknesses": "Strengths:\n\nIn my view, the main strengths of this article are the empirics:\n- the experimental validation that WGNNs achieve SOTA on Cora, Citeseer, PubMed, and a range of other standard tasks is impressive\n- I found the ablation studies to be useful, especially how high order a polynomial to use and the how much of the signal to keep in the SVD. \n- I found it interesting that logistic regression on top of frozen features (the polynomials P_k and the singular vectors/values of the normalized adjacency matrix) in WGNNs outperforms deep neural networks of various kinds. This fact is also kind of a weakness of this paper (see below).\n\nWeaknesses:\n\nIn my view, the main weaknesses are in the conceptual framing, the theory, and connecting the theory to the empirics:\n\n- I don’t think it’s really fair to call WGNNs neural networks. After all, they are just logistic regression on top of frozen features (the polynomials P_k and the singular vectors/values of the normalized adjacency matrix). As mentioned above, I found the fact that these simple models work so well to be surprising. But it is also somewhat incongruous with the rest of the paper. Namely, the way I read this paper is that actually on many graph-based tasks it is better to just use hand-crafted or at least pre-computed features. This doesn’t seem to have much relation to the discussion of GCNs and oversmoothing in the first few sections.\n- Overall, the theory in this article is weak:\n    - Theory is done only for linear networks\n    - Theory does not cover many other kinds of commonly used architectures such as residual GNNs and things like GCNii, which provably alleviate oversmoothing. \n    - No theoretical analysis directly for WGNNs is provided\n    - The main theory result, Theorem 3.1, has been proved many times in various contexts. For example:\n        - See appendix B.3 in Huang, Wei, et al. \"Towards Deepening Graph Neural Networks: A GNTK-based Optimization Perspective.\" arXiv preprint arXiv:2103.03113 (2021).\n        - See Lemma 3.1 in Cai, Chen, and Yusu Wang. \"A note on over-smoothing for graph neural networks.\" arXiv preprint arXiv:2006.13318 (2020).\n        - See Theorem 2 in Huang, Wenbing, et al. \"Tackling over-smoothing for general graph convolutional networks.\" arXiv preprint arXiv:2008.09864 (2020).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "seMfw4eVUK", "reviewer": "Reviewer_KH5p", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents Wide Graph Neural Networks, a class of polynomial graph neural networks (GNNs) with an additional learnable term acting on the principal eigenvectors of the adjacency matrix.\n\nThe paper attempts to study and unify the literature on GNNs to highlight the limitations of previous methods, aiming to solve the issue of oversmoothing and to improve classification performance on heterophilic graphs. ", "summary_of_the_review": "The paper has significant flaws and contains mistakes, the novelty is very limited, and the results do not seem to be reproducible (using the authors' code). \n\nI recommend the paper is rejected. ", "strength_and_weaknesses": "**Strengths**: \n- The paper is easy to read.\n- The authors report good performance on five benchmarks with homophilic graphs and 2 benchmarks with heterophilic graphs (although please see below for reproducibility issues).\n\n**Weaknesses**: \n- The definition of spectral GNNs given by the authors is incorrect, since not all spectral GNNs need to eigendecompose the Laplacian and not all of them use polynomial filters. Also, Equations (4) and (8) do not describe the typical polynomial filter. This is particularly concerning since this definition (and its supposed limitations) is one of the main premises of the paper, which is therefore built on false assumptions. \n  I would also point out that GCN is not significantly different from ChebyNets, so they are definitely not representatives of two different classes of GNNs. \n- Oversmoothing is a problem that has been studied very in depth in GNN literature, to the point where it can be considered essentially solved. People have been training very deep GNNs for years now, using techniques like skip connections, adaptive information propagation, edge/node drop, and weight tying. \n- The authors claim that solving oversmoothing is still needed to train GNNs hundreds of layers deep, but then only test models with up to 10 layers (which, as I said above, is not a complicated feat to achieve). \n- Since, by construction, Equation 5 only works for non-parametric transformations of the graph, all GNNs that have learnable edge-dependent message functions cannot be modeled by the proposed method. Some of these, like Graph Attention Networks and Edge-conditioned Convolutions, are quite significant. This limitation is not due to \"nonlinearity\" (as claimed in the conclusions). \n  Also, Equation 5 is far from a unification of spectral and spatial methods, but rather a compact way of writing polynomial filters. \n- The main proposal of Equation (9) is to use a polynomial filter and to add a term consisting of learnable linear projections of the first few eigenvectors of the adjacency matrix, which is both not novel and very expensive (quadratic in the number of nodes). \n- While one of the main goals of the paper is to solve oversmoothing, the experiments only show minor improvements on very standard datasets (Cora, Citeser, and Pubmed) with no concrete study of oversmoothing. \n- There is no reason why the proposed design would, a priori, have better performance on heterophilic graphs. The theoretical analysis on page 6 also does not justify why the proposed method should work better.  The method is still essentially a polynomial filter, so I don't see why it would outperform all other methods by this much on Squirrel and Chameleon. \n  For this reason, I took the liberty of running the code provided in the supplementary material by the authors, using the `--poly` flag to test different methods. As expected, all methods I have tried (GPR, Cheby, GCN, and the authors') achieve an accuracy above 73 on Chameleon. Please let me know if I have misused the code in some way or if I misunderstood something.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "YvyfmzgUmo", "reviewer": "Reviewer_Uh1P", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a unified view for both spectral and spatial GNNs from the matrix space analysis perspective to investigate possible reasons for over-smoothing, poor flexibility, and low performance on heterophily. They propose a new GNN framework, namely, Wide Graph Neural Network (WGNN), to address these issues. WGNN consists of two components: one is for constructing a non-parametric feature space, and the other is for learning the parameters to re-weight the feature space. ", "summary_of_the_review": "The proposed Wide Graph Neural Network (WGNN) is novel. Experimental results on several graph datasets show the superiority of WGNN comparing with the baselines. The authors provide detailed theoretical analysis on how WGNN can help address the issues of over-smoothing, poor flexibility, and low performance on heterophilic data. I would also like to see the authors' response to my questions \nraised in the cons above during the rebuttal period.", "strength_and_weaknesses": "Pros:\n\n1. The proposed Wide Graph Neural Network (WGNN) is novel. It is an interesting idea to decompose the components in spectral and spatial GNNs into a non-parametric feature space and a parameter space to re-weight the corresponding feature subspace. \n\n2. The authors provide detailed theoretical analysis to explain over-smoothing and poor performance on heterophilic graphs. Unlike spectral GNNs, which use a single parameter matrix for all polynomial terms, WGNN has better flexibility by allowing different parameters for each term. \n\n3. Experimental results on eight datasets (including both homophilic and heterophilic) show that the proposed WGNN outperforms several baselines in terms of node classification accuracy. \n\nCons:\n\n1. In the ablation study, the nearly optimal value for the order K of the polynomials is 3 (based on the Cora and Chameleon datasets). This value is also the number of feature sub-spaces. I find it a bit difficult to understand that the optimal number of feature subspaces in WGNN could be a fixed value for different types of graph data and applications. \n\n2. It would be great if the authors can provide more explanations on why principal components of the adjacency matrix (i.e., low dimensional information for the graph structure) is used to form the subspace $S_j$. As mentioned in the paper, $S_j$ could be any transformation of the adjacency matrix. I'm wondering the classification performance with other types of transformations. \n\n3. What is the total number of parameters in WGNN, comparing with spectral and spatial GNNs? As discussed in the conclusion, the parameters in WGNN can be further reduced by introducing additional constraints and assumptions. \n\n4. Among all the datasets, WGNN does not outperform GNN-LF and GNN-HF on CiteSeer data. It would be great if the authors can provide some insights on this. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "HnrF8DZCN9T", "reviewer": "Reviewer_HybF", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper propose a new GNN model, namely wide graph neural network (WGNN), to address the problems existing in spatial and spectral GNNs, including *over-smoothing*, *homophily and heterophily*, and *poor flexibility*. ", "summary_of_the_review": "I'd like to update my score during the discussion period if my concerns could be well addressed.", "strength_and_weaknesses": "### Strength\n\n- The paper is well-organized and easy to follow.  \n- The experimental results are satisfactory, especially on heterophilic graphs. The presentation of experiments is quite good. \n\n### Weakness\n\n- The theoretical analysis and conclusion provided in this paper seem not new. Some existing works have rigorously investigated the over-smoothing caused by high-order graph operations, including but not limited to [1] [2]. \n- The discussion of \"poor flexibility\" of spectral GNNs is unconvincing. The authors claimed that the poor flexibility is caused by the limited size of parameters for $P_k(L)$. One can increase the number of these parameters, $\\gamma$, similar to GCN (proposed by Kipf&Welling). I agree that both spatial and spectral methods cannot handle the heterophilic cases, but the poor flexibility of spectral methods may be unconvincing in my opinion. \n- How is the time cost per epoch computed? Does it contain the time to compute $\\Phi_t$? Since the insufficiency problem of GNNs is actually caused by the graph operations, it may be unconvincing to only report the time of each epoch during BP. \n- I'm not persuaded by the motivation of $S_j$. Why is the \"dimensionality reduction\" needed for GNNs?\n\n(Minor)\n\n- In Figure 1-middle, the authors may misuse $\\gamma$, which seems to be $\\theta$ in the top formulation. \n- At the bottom of Page-3, the authors claim \"a GNN model forms *K* feature sub-spaces\". Does $K$ mean $T$? After reading Sections 2 and 3, $K/k$ and $T/t$ are pretty confusing and ambiguous though I may get the meaning in most cases. \n\n[1] Kenta Oono and Taiji Suzuki, Graph neural networks exponentially lose expressive power for node classification, ICLR, 2020. \n[2] Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi, On provable benefits of depth in training graph convolutional networks, NeurIPS, 2021.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject