Connecting Graph Convolution and Graph PCA
Authors: Lingxiao Zhao
Leman Akoglu
Venue: ICLR 2022 Submitted (2022)
Keywords: Graph Convolutional Network
graph regularization
GNN initialization
graph-based PCA

Abstract: Graph convolution operator of the GCN model is originally motivated from a localized first-order approximation of spectral graph convolutions. This work stands on a different view; establishing a mathematical connection between graph convolution and graph-regularized PCA (GPCA). Based on this connection, the GCN architecture, shaped by stacking graph convolution layers, shares a close relationship with stacking GPCA. We empirically demonstrate that the unsupervised embeddings by GPCA paired with a 1- or 2-layer MLP achieves similar or even better performance than many sophisticated baselines on semi-supervised node classification tasks across five datasets including Open Graph Benchmark. This suggests that the prowess of graph convolution is driven by graph based regularization. In addition, we extend GPCA to the (semi-)supervised setting and show that it is equivalent to GPCA on a graph extended with “ghost” edges between nodes of the same label. Finally, we capitalize on the discovered relationship to design an effective initialization strategy based on stacking GPCA, enabling GCN to converge faster and achieve robust performance at large number of layers.

Under review as a conference paper at ICLR 2022
CONNECTING GRAPH CONVOLUTION & GRAPH PCA
Anonymous authors
Paper under double-blind review
ABSTRACT
Graph convolution operator of the GCN model is originally motivated from a localized first-order approximation of spectral graph convolutions. This work stands on different view; establishing mathematical connection between graph convolution and graph-regularized PCA (GPCA). Based on this connection, the GCN architecture, shaped by stacking graph convolution layers, shares a close rela- tionship with stacking GPCA. We empirically demonstrate that the unsupervised embeddings by GPCA paired with a 1- or 2-layer MLP achieves similar or even better performance than many sophisticated baselines semi-supervised node classification tasks across five datasets including Open Graph Benchmark. This suggests that the prowess of graph convolution is driven by graph based regular- ization. In addition, we extend GPCA to the that it is equivalent GPCA on graph extended with "ghost" edges between nodes of the same label. Finally, we capitalize on the discovered relationship to design an effective initialization strategy based on stacking GPCA, enabling GCN to converge faster and achieve robust performance at large number of layers.
setting and show
INTRODUCTION
Graph neural networks (GNNs) are neural networks designed for the graph domain. Since the breakthrough of GCN (Kipf& & Welling 2017). which notably improved performance on the semi- supervised node classification problem, many GNN variants have been proposed: including GAT (Veličković et al. 2018), GraphSAGE (Hamilton et al. 2017), DGI (Veličković et al. 2019). GIN
(Xu et al. 2019). PPNP and APPNP (Klicpera et al., 2019). to name few.
Despite the empirical successes of GNNs in both node-level and graph-level tasks, they remain not well understood due to limited systematic and theoretical analysis of GNNs. For example, researchers have found that GNNs, unlike their non-graph counterparts, suffer from performance degradation with increasing depth, their expressive power decaying exponentially in number of layers (Oono & Suzuki 2020). Such behavior is only partially explained by the oversmoothing phenomenon (Li et al. 2018: Zhao & Akoglu 2020). Another surprising observation shows that a Simplified Graph Convolution model, named SGC (Wu et al. 2201), achieve similar performance to various more complex GNNs on a variety of node classification tasks. Moreover, a simple baseline that does not utilize the graph structure altogether performs similar state-of-the-art GNNs graph classification
tasks (Errica et al. 2020). These observations call attention to studies for a better understanding of
GNNs (NT & Machara 2019 Morris al. 2019 Xu al., 2019 Oono & Suzuki 2020 Loukas
2020 Sriiivaaan & Ribeiro 2020). (See Sec. 2 for more on understanding GNNs.)
Toward systematic analysis and better understanding of GNNs, we establish connection between the graph convolution operator of GCN (and PPNP) and Graph-regularizedd PCA (GPCA) (Zhang & Zhao 2012). and show the similarity between GCN and stacking GPCA. This connection provides deeper understanding of GCN's power and limitation. Empirically, we also find that GPCA performance matches that of many GNN baselines on benchmark semi-supervised node classification tasks. We argue that the simple GPCA should be a strong baseline in future. What is more, the unsupervised stacking GPCA can be viewed as "unsupervised GCN" and provides a straightforward, yet systematic way to initialize GCN training. We summarize contributions follows:
We establish the connection between the graph convolution operator of GCN (also PPNP) and the closed-fom -oorfom solution of rrguaizeg PCA (GPCA) formulation. We demonstrate that a simple graph-regularize, PCA paired with or 2-layer MIP can achieve similar even better results than state-of-the-art GNN baselines over
Connection between Graph Convolution and GPCA:

---

Under review as a conference paper at ICLR 2022
several benchmark datasets. We further extend GPCA to (semi-)supervine setting which can generate embeddings using information of labels, which yields better performance on 3 out of 5 datasets. The outstanding performance of simple GPCA supports that the prowess of GCN on node classification task comes from graph based regularization. This motivates the study and design of other graph regularization techniques in the future.
New Stacking GPCA model: Capitalizing on the connection between GPCA and graph convolution, we design new GNN model called GPCANET shaped by (1) stacking multiple GPCA layers and nonlinear transformations, and (2) fine-tuning end-to-end via supervised training. GPCANET is generalized GCN model with adjustable hyperparameters that control the strength of graph regularization of each layer. We show that with stronger regularization, we can train GPCANET with fewer (1-3) layers and achieve comparable performance to much deeper GCNs.
GPCANET:
First initialization strategy for GNNs: Capitalizing on the connection between GCN and GP- CANET, we design a new strategy to initialize GCN training based on stacking GPCA, outperforming the popular Xaiver initialization (Glorot& & Bengio, 2010). We show that the GPCANET-imttialzaatne is extremely effective for training deeper GCNs, that significantly improves the convergence speed, performance, and robustness. Notably, GPCANET-imiiiaizzaton is general-purpose and also applies to other GNNs. To our knowledge, it is the first initialization method specifically designed for GNNs.
We open-source code at
All datasets are public-domain.
RELATED WORK
Understanding GNNs. Our work concerns learning on a single graph, hence we limit discussion of related work to node-level GNNs. GCN's graph convolution is originally motivated from the approximation of graph filters in graph signal processing (Kipf & Welling 2017). NT & Maehara (2019) show that graph convolution only performs low-pass filtering original feature vectors, and also state a connection between graph filtering and Laplacian regularized least squares. Motivated by the oversmoothing phenomenon of graph convolution, Oono & Suzuki (2020) theoretically prove that GCN can only preserve information of node degrees and connected components when the number of layers goes infinity, under some conditions of GCN weights. Recently several papers revisited
the connection of graph convolution to graph-regularized optimization problem (Li et al., 2019 Ma
al. 2020 Pan et al. 2021 Zhao & Akoglu 2020 Zhu et al., 2021), which is originally discussed
in graph signal processing Shuman et al. 2013). More specifically, both Ma et al. (2020) and
Zhu et al. (202T) relate graph-regularization optimization to several GNNs such as GCN (Kipf &
Welling 2017), APPNP (Klicpera et al. 2019), and GAT (Veličković et al. 2018). However, all previous work study these connections while ignoring the learnable parameters, which are essential for high-performance deep learning, Our work differs from these by establishing stronger and closer connection to graph-regularized PCA that also takes learnable parameters into account.
Graph-regularized PCA. PCA and its variants are standard linear dimensionality reduction ap- PCA (Jiang
proaches. Several work extend PCA to graph-structured data, such as ct al. 2013) and Ganifold-regularinn Matrix Factorization (Zhang & Zhao 2012). For other variants, see Shahid et al. (016).
Stacking Models and Deep Learning. The connection between CNN and stacking PCA has been explored in PCANet (Chan et al. 2013). which demonstrated that the (unsupervised) simple stacking PCA works well supervised CNN over a large variety of vision tasks. The original PCANet is
shallow and does not have nonlinear transformations, while PCANet+ (Low et al. (017)) overcomes these limitations and pushes the architecture much deeper. The idea of layerwise stacking for feature extraction is not new and was empirically observed to exhibit better representation ability in terms of classification. For a comprehensive review, we refer Bengio et al. (2013).
Initialization. Traditionally, neural networks (NNs) were initialized with random weights generated from Gaussian distribution with zero mean and small standard deviation (Krizhevsky et al., 2012). As training deeper NNs became extremely difficult due to vanishing gradient and activation functions, Glorot & Bengio (2010) provided a specific weight initialization formula, named Xavier initialization, based on variance analysis without considering activation function. Xavier initialization is widely used for any type of NN even today, and it is the main initialization strategy used for GNNs. Later, He et al.
(2015) adapted Xavier initialization to ReLU activation by considering multiplier. Taking another
2

---

Under review as a conference paper at ICLR 2022
direction, Saxe al. (2013) analyzed the dynamics of training deep NNs and proposed random orthonormal initialization. Mishkin & Matas (2015) further improved orthonormal initialization for batch normalization (lofte & Szegedy] (2015) Different from these iata-indeppnneet approaches, others (Krähenbühl et al.) 2016; (Serret et al. 2017 Wagner et al., 2013) have employed data- dependent techniques, like PCA, to initialize deep NNs. Although initialization has been widely studied for general NNs, no specific initialization has been proposed for GNNs. In this work, we propose a data-driven initialization technique (based on GPCA), specific to GNNs for the first time.
GRAPH CONVOLUTION AND GPCA
3.1 GRAPH CONVOLUTION
Consider a node-attributed input graph G = X) with = n nodes and |E] m edges, where X E Rgxd denotes the node feature matrix with d features. Broadly, graph convolution operation convolves the features (or representations) over the graph structure.
GCN. Similar to other neural networks stacked with repeated layers, GCN contains multiple graph convolution layers each of which is followed by nonlinear activation. Let (()) be the (-th hidden layer representation, then, each GCN layer performs
(1+1) o (As (1) W())
(I)
where Asym (A+1-D- denotes the n symmetrically normalized adjacency matrix with self-loops, D is the diagonal degree matrix where D; = 1+ ビー= A., W(O depicts the 1-th layer parameters (to be learned), and is the nonlinear activation function. Formally, graph convolution is parameterized with W and maps an input X to new representation Z as
7 A
PPNP. For PPNP (liicpeaa et al. 2019). the features are first transformed by an MLP before convolving the graph. Formally, the operation is revised as
== (((1-))A_g.))
MLP (X) (l= ML)
I= L) where we replace j with (1 L. := and W depicts the learnalle MI.P parameters. As matrix inverse is expensive, an approximate version called APPNP that employs the power method (Golub & Van Loan 1989) is often used in practice.
Asym denotes the normalized graph Laplacian,
3.2 GRAPH-REGULARIZER PCA (GPCA)
As stated by [Bnniio al. 2 "Although depth is an important part of the story, many other priors are interesting and can be conveniently captured when the problem is cast as one of learning a representation." GPCA is one such representation learning technique with a graph-based prior.
Standard PCA learns k-dimensional projections Z E BRnk of feature matrix X E RRaxd aiming to
minimize the reconstruction error
||X - ZWT
(4)
subject W E d being an orthonormal basis. GPCA extends this formalism to graph-structured data by additionally assuming either smoothing bases (Tiang et al. 2013) or smoothing projections (Zhang & Zhao 2012) over the graph. this work we consider the latter case where low-dimensional
projections are smooth over the input graph G, where Ī= Asym denotes its normalized Laplacian matrix. The objective formulation of GPCA is then given
min Z,W
X II + a Tr(Z' LZ)
s.t. W =I
(5)
where a is a hyperparameter that balances reconstruction error and the variation of the projections the graph. Note that the first part of Eq. equation 5 along with the constraint, corresponds to the objective of the original PCA, while the second part is a graph regularization term that aims to "smooth" the learned representations Z over the graph structure. As such, GPCA becomes the standard PCA when a = 0.
Similar to PCA, the problem 5 is non-convex but has a closed-form solution (Zhang & Zhao 2012). Surprisingly, as we show, it has close connection with the graph convolution formulation in Eq. equation 2 In the following, we give the GPCA solution and then detail its connection to graph convolution.
3

---

Under review as a conference paper at ICLR 2022
Theorem 3.1. GPCA with formulation shown in ( has the optimal solution (Z*, W*) following W = (W1, W2...., Wk)
Z" = (1 + aaL-'XW" and
(6)
where W1, ..,, We are the eigenvectors of X" (I+a)) corresponding to the largest k eigenvalues.
Proof. The proof can be found in Appendix. A.1
3.3 CONNECTION BETWERN GCN AND GPCA
Let $ + al.. The normalized Laplacian matrix i. has absolute eigenvalues bounded by 1, thus, all its positive powers have bounded operator norm. When S 1, - can be decomposed into The first-order truncated form (i.e.
Taylor series as (I + aL)- approximation) of the series
aL + (-a)'L' + +....
(1 a ~ 1 - aL (1 a) + aAAmm
When a the first-order approximation of Z" in Theorem 3.1 follows
(8) The (approximate) solution to GPCA in Eq. equation 8 matches the form of graph convolution operation in Eq. equation 2 with W* plugged in as the eigenvectors of the matrix x -- X. In other words, there exists some parameter W with which GCN becomes the first-order approximation of GPCA.
Z ~ Aym
To reiterate, key contribution of this work is to show that the graph convolution operation in GCN can be viewed as the first-order approximation of GPCA with a = with a learnable W. Put differently, the first-order approximation of (unsupervised) GPCA with = 1 can be viewed graph convolution with a fixed, data-driven W. In other words, Notably, for a < 1, Eq. equation| 7 shows the connection between GPCA and graph convolution equipped with 1-step (scaled) residual connection.
3.4 CONNECTION BETWEEN PPNP AND GPCA
Replacing the MLP in Eq. equation with single linear layer without activation results in Z =
aT. XW, which has exactly the same formulation the solution Z" in Theorem 3.1 Eq. equation The connection states that the graph convolution in PPNP can be viewed as the GPCA CA solution with a Iearnable W. Interestingly, the empirical performance improvement of PPNP over GCN (see Table 2 in Klicpera et al. (2019)) may be explained through these connections that they have to GPCA; where PPNP relates to the exact solution of GPCA while GCN is related to its (first-order) approximation.
3.5 SUPERVISED GPCA
The standard GPCA problem in (5) is unsupervised. Motiviated from LDA (Balakrishnama & Ganapathiraju 1998) and PL. (Geladi & Kowalski] 1986), in this section we show how to extend to the supervised setting, by learning embeddings that not only (1) provide good reconstruction and (2) vary smoothly over the graph structure, but also (3) highly correlate with the response variable(s). For simplicity of presentation, let z E Rd be a 1-d embedding and Y denote the response matrix (in the general case of multiple responses). We write the additional, i.e. (3)rd objective above, as
[Corr(Y,2) 2)}² [corr(Y, 2)] var(z) = max z TYY
max
The form of equation 9 (See Appendix. A.3) and the variance-mant maximizing term var(z) are for mathematical convenience. Despite agnostic to labels, including var(z) is intuitive since an implicit objective of data projection (embedding) is to ensure that inherent variation in data is captured as much as possible. In general, we would aim to maximize the trace of ZTYYT Z for multi-dimennionnl embeddings.
Interpretation. For semi-supervised node classification with classes, let L C V denote the set of labeled nodes. For this task, Y E {0, 1) 1 would encode the node labels where the w-th row of Y, denoted Y,, depicts the one-hot encoded label for each L. For E V with unknown labels, Y, = 0, set as the o-dimensional all- zerz vector. Then, (YY )ay is simply equal to when
For the optimization to he well-posed, constraints on are required, omitted for simplicity of presentation.
4

---

Under review as a conference paper at ICLR 2022
nodes and share the same label, and otherwise 0 (either because they have different labels or labels are unknown). This term simply enforces the representations Z, and Zj of two same-labeled nodes to be similar.
sense, YY" adds "ghost" edges between the same-label nodes, further guiding the smoothness of their representations over this extended graph structure. We remark that earlier work (Gallagher et al. 2008) has heuristically introduced edges between same-label nodes to enhance given graph for the node classification task. In this work, we have derived the theoretical underpinning for this strategy.
Supervised formulation. We have shown that requiring the embeddings to correlate with the known labels can be interpreted as additional smoothing over "ghost" edges hetween the same-label nodes in the graph. As such, we extend the GPCA problem in (5) to the jupirisuuere setting as
min Z.W
||X - ZW
LspeZ)
s.t. WTW =
(10)
where Lape = -- Aspe. Agr = (1- 3) + +B
(11)
In Eq. equation [T] B is an additional hyperparameter for trading-off the graph-based regularization (i.e. smoothing) due to the actual input graph edges versus the ones introduced through YY" between the nodes of the same label, and D is the diagonal matrix with Das = -E==(Y> (YY"") kyy
Theorem 3.2. Supervised GPCA, as shown in (10) has the optimal solution WW" W
Z = (I + - XW", and W = (W1, W2, Wx)
(12)
where WI...., We are the top eigenvectors of the matrix X² + agg - equivalently ((1+ a)I - aa1 -3) Aym + a3D DYY X, corresponding to the largest eigenvalues.
Proof. The proof is similar to that of Theorem 3.1
3.6 APPROXIMATION AND COMPLEXITY ANALYSIS
According to formulations in Theorems 3.1 and 3.2 obtaining Z' nR and W W*ERdxk requires two demanding computations (1) the inverse of 4 (7 + aL) E Raxn in the supervised case
&. (1 Loyr: and (2) top ls eigenvectors the matrix X x- gdxd Eigen-decomposition takes (dd) (Pan & Chen 1999), which is scalable as is usually small. Computing matrix inverse, on the other hand, can take (n²)) and require O(n²) memory, which would be infeasible for very large graphs.
To reduce computation and memory complexity, we instead approximately compute F ;= === X, which is a common term for both Z and W We can equivalently write
(L+ = F + oF a PF X
F 1
PF
I+a X
for P = Asmm in the unsupervised case and P = (1 3) Aym + 3DD B when supervised.
Then, can iteratively (with total T iterations) the power method (Golub & Van Loan 1989) to compute F as
F(++) a PF() +
(13)
I+a where E {O. T3 depicts the iteration and ((0) Rnxd is initialized as X (or randomly). For the supervised case, (() is computed through a series of (from right to left) matrix-matrix products. This avoids the explicit construction of matrix yYT in memory. Overall, solving for F takes O(T(m + r2)d where is the number of edges in the graph. The supervised case has additional term ([])) with c being the number of classes and L < n be the number of labeled nodes, which can also be upper-bounde by (T  n)d) when treating
1+a
constant.
Having solved for F, we perform the matrix matrix-matrix matrix product Z = FW" in O(ndk) and then the cigen-decomposition of X in Odd ndf) O(nd)) (for 2 d). Assuming O(d) O(k), overall complexity for computing the 1-layer GPCA is given as O + Tnd + ndd), which is linear in the number of nodes and edges. Note that empirically we found 5 < T S 10 to be sufficient.
5

---

Under review as a conference paper at ICLR 2022
Algorithm I GPCANET Forward Pass and Pre-training
1: Input: graph G = E, GPCA hyper-parameler(s)) a (and 3 if supervised, 3 = 0 otherwise), flayers
L. hidden layer sizes {dz.-. dz h. activation function a(-). #approximation steps T
2: Output: pre-set layer-wise parameters {W()), ,..., ,..,,,.()))))
3: Initialize H7(0 := X
4: for = 1 to I do
5: Center H by subtracting mean of row vectors
6: F <- (1!-1)
7:
for ( = 1 To
8:
PF + (1 -8) +D
9:
F' <- 14oPF FF Ita H (1-1)
end for
W top di eigenvectors of ((() F
11:
12: H + (FFW()
13: end for
4
GPCANET: A STACKING GPCA MODEL
4.1 GPCANET
Thus far, we drew a connection between the geometrically motivated, manifold-base GPCA and the graph convolution operation of deep NN based GCN. Next we leverage this connection to design new model called GPCANET that takes advantage of the relative strengths of each paradigm; namely, GPCA's ability capture data variation and structure, and GCN's ability to capture multiple levels of abstraction (i.e. high-level concepts) through stacked layers and non-linearity.
In nustshell, GPCANET is stacking of multiple (unsupervised or supervised) GPCA layers and nonlinear transformations, which shares the same architecture as a multi-layer GCN. It consists of two main stages: (1) Pre-training, which initializes the layer-wise parameters through closed-form GPCA solutions, and (2) End-to-end-training which refines these parameters through end-to-end gradient-based minimization of global supervised loss criterion at the output layer.
We remark that GPCANET not the same as GCN, as each layer uses the formulation in Thm.s 3.1 and 3.2 (with approximation shown in Sec. 3.6). In fact, when 1 and 3 = 0, GPCANET is the GCN model initialized with GPCANET-initiaizaze other words, GPCANET is generalized GCN model with additional hyperparameters, and B controlling the strength of graph regularization based on the existing or "ghost" edges, respectively,
which we discuss more in Sec. 4.2 In
Forward Pass and Pre-training stage. During pre-training, weights of the 1-th layer, denoted as ( E Rd 1xd, pre-set (i.e. initialized) as the leading d, eigenvectors of the matrix (111)) Φ- -- where (!-1) is the representation as output by the (1 1)-th layer (with H == X). and oa can be the unsupervised (I) or the supervised (I + Lspp). The pre-training stage takes a single forward pass. Algo. [ shows both forward pass during wat-tto-nn--taaniiin and the pre-training procedure, where line 11 in blue is step used only for pre-training.
Additional treatment for ReLU:
Nonlinear transformations like ReLU improves model capacity, however at pre-training stage, it causes information loss as all negative values are truncated to 0. This hinders the advantage of using the leading di eigenvectors to initialize the weights so as to convey maximum variance (i.e. information) to the next layers. To address this issue, we instead use the 14/2
leading di /2 eigenvectors ( and their negatives w. dx/2 ) to initialize W(),, Empirically we observe this always improves performance when using ReLU activation.
End-to-end training stage. Pre-training can be seen as an information presoorvnneeeeingge initialization, as compared to uninformative random initialization, after which we refine the layer-wise parameters via gradient-bart based optimization w.r.t. a supervised loss criterion at the output layer. Specifically for semi semi-supervised node classification, we perform an end-to-end training w.r.t. the cross-entropy loss on the labeled nodes. All parameters are updated jointly through backpropagation during this stage, with forward computation shown in Algo A (excluding line 11).
II (1) is greater than the number of eigenvectors, all eigenvectors are used, with additional vectors generated from random projection of eigenvectors.

---

Under review as a conference paper at ICLR 2022
4.2 GPCANET-INITTALIZATION FOR GCN
When set L, 3 0. and approximate the matrix inverse (1 + aL) via first-order truncated Taylor expansion as shown in Eq. equation 7. GPCANET has the same architecture with GCN. As such, we use the pre-training stage of GPCANET to initialize GCN with only minor modification. Specifically, we replace lines through 10 in Algo. Wiih the following single line:
F F+ Asym/11(-1)
(14)
The modified initialization for GCN and is driven by the mathematical connection between GPCANET and GCN that we established. We expect that adapting it for other GNNs is also possible although we do not pursue this direction here.
5 EXPERIMENTS
In this section we design extensive experiments to answer the following questions. (Q1) How does the simple, unsupervised and shallow GPCA compare its multi-layer extension GPCANET, as well as to existing GNNs? (Q2) How does our extended, superviee GPCA compare to the original, unsupervised GPCA? (Q3) Does GPCANET DiCCAAETiiiitillizatinnn improve GCN accuracy and robustness?
5.1 EXPERIMENTAL SETUP
Datasets. We focus on semi-supervised node classification (SSNC) and use 5 benchmark datasets: First three, CORA, CITESEER, PUBMED (Sen et al. 2008), are relatively small (2K' to 10K nodes) but widely-used citation graphs. For these we use the data splits in Kipf & Welling (2017). The others, ARXTV and PRODUCTS, are newest and much larger (100K' to 2000 node classification benchmarks from Open Graph Benchmark (Hu et al. 2020), for which we use the official data splits. Data statistics can be found in Appendix. A.4 Baselines.
We compare (unsupervised & semi-supervised) GPCA and GPCANET state-of-the-an (SOTA) GNNs, including GCN (Kipf & Welling 2017). APPNP (Klicpera et al. 2019), GAT (Veličković et al. 2018), and GraphSAGE (G-SAGE) (Hamilton et al. [017]]
Model configuration and training. For each dataset, we define a separate pool of values for the hyperparameters (HPs): learning rate, weight decay, number of layers, hidden size, dropout rate, and regularization trade-off terms a, B. For fair comparison, all models share the same HP pools during training. See Appendix.
A.5 for HP configurations and other details.
5.2 Q1: PERFORMANCE OF (UNSUPERVISED) GPCA AND GPCANET
GPCA. Having proved the mathematical connection between GPCA, GCN, and PPNP, we expect unsupervised GPCA (3 = 0) to generate comparable representations. We perform GPCA with different a E (1, 5, 10, 20, 50} (Appendix. T to obtain node representations and pass those to a o- 2-yer MIP. We compare to GCN, APPNP, as well as other GNNs; GAT and G-SAGE.
The performance results are given in Table Due to the scale of the largest two datasets, ARXIV and PRODUCTS, we list the reported performance at OGB-leaderboard (depicted by ") for G-SAGE on both datasets, and that of (Cluster-) )ATT on PRODUCTS.
We find that the simple 1-layer GPCA paired with MLP performs consistently better than the multi- layer GCN model across all 5 datasets. GPCA's performance is also comparable to or better than other SOTA GNNs. This is quite notable, given that GPCA is not only shallow but also unsupervised, whereas all other baselines are trained end-to-end, and with the exception of APPNP, they exhibit multi-layer architecture. By carefully looking at the performance of GPCA with varying a (see Appendix. A.6). we find that different datasets have different best selected a" (in Table | top to bottom: a* = (50,55 5, 10, 20, 20)) but in general a relatively larger a (compared graph convolution of GCN that is equivalent to a = 1) is preferable for all datasets. Larger implies stronger graph- regularization on the representations. The outstanding performance of the simple GPCA empirically confirms that the power of GNNs on the SSNC problem is mainly driven by graph regularization.
GPCANET. Compared to the 1-layer GPCA, GPCANET has a deeper architecture along with nonlinear activation function. Moreover, it employs hyperparameter a at every layer to control the degree of graph regularization. As each graph convolution has fixed level of graph regularization, one may hypothesize that increasing the number of layers (L) corresponds to increasing the degree
7

---

Under review as a conference paper at ICLR 2022
Table 1: Comparison btwn. unsupervised GPCA (3 0). GPCANET, and existing (supervised) SOTA GNNs on 5 datasets, w.r.t. mean test accuracy and standard deviation (in parentheses) over different seeds. Those marked with are reported values at the BGB-leeadrboord Highest mean performance is in bold and the second highest is underlined.
GPCA
GPCANET
GCN
APPNP
GAT
G-SAGE
CORA
81.10 (0.00)
80.64 (0.33)
80.62 (0.90)
81.35 (0.18)
79.27 (0.50)
81.48 (0.83)
CITESEER
71.80
(0.75)
71.36 (0.21)
71.25 (0.05)
70.33 (0.75)
69.65 (0.59)
71.20 (0.92)
PUBMED
78.78
(0.36)
78.52 (0.17)
78.42 (0.25)
78.95 (0.36)
78.23 (0.54)
77.78 (0.29)
ARXIV
71.86
(0.18)
72.20 (0.15)
70.64 (0.17) 70.55 (0.27)
71.11 (0.11) 71.49"(0.277
PRODUCTS
79.23 (0.14)
80.05 (0.29)
77.90 (0.33)
77.96 (0.34)
79.23" 79.23"(0.78)
78.29" (0.16)
of graph regularization. We empirically test this hypothesis using GPCANET, by varying both L. (2
to 10) and a (0.1 to 10) to show their connection (hidden size fixed as 128). The result is shown in Figure [ The diagonal pattern (in dark blue) empirically suggests that increasing the number of layers has the same effect as increasing graph regularization via a.
The corresponding interaction between and number of layers suggests that we can train a GPCANET with fewer number of layers yet achieve similar regularization by increasing Such a shallow model that in fact behaves like deep one has the advantage of less memory requirement and faster training due to fewer parameters.
0.08
0.77
0.8
0.73
Lagers
0:73
0.01
3.81
0:76
0.7
0.74
0.81
081
0.73
0.64
To this end, we train 1 1-3-layer GPCANET with varying (higher a's for fewer layers, see Appendix. [A.7). and select the best a and number of layers using validation set. We report test set performance in Table | We do not observe much im- provement by GPCANET over other models on smaller datasets CORA, CITESEER, MUBMED, but notable gains on the larger ARXIV and PRODUCTS. As such, GPCANET enables shal- low model training via tunable hyperparameter a, achieving comparable or better performance.
0.78
0.8
0.1
0.5
1.0
5.0
10.0
Appil
Figure 1: GPCANET performance (avg. over 5 seeds) with varying number of layers (L) and on CORA. Increasing
has similar effect as increasing Results also hold for the other datasets.
5.3
Q2: UNUUPEPERVD VS. SEMI-SUPERVISE GPCA
The representations generated by unsupervised GPCA does not use any label information from training data. In this work, we have extended GPCA to (semi-)supervised setting with an additional HP, namely B E [0, 1] that trades-off graph regularization due to the actual input graph edges versus the "ghost" ones added through YY".. Overlitting can hurt performance when 3 is too large or when there a distribution shift between the training and test sets. For ARXIV and PRODUCTS, we empirically observe that B > 0 always degrades performance, possibly because of the distribution difference between the training and test sets as described in OGB (Hu et al. 2020). Therefore we only study the effect of B CORA, CITESBER and PUBMED. The pool for 0 {0.1, 0.2).
Table 2: Comparison btwn. Supervised (S-)GPCA (3>0) and Unsupervised (U-)GPCA (8=0), w.r.t. mean test aceuracy and standard deviation (in parentheses) over 5 different seeds. Also shown (bottom row) is the performance by the best method in Table T Highest mean performance is highlighted in bold.
Results are shown in Table 2 where (ALII 8>00) depicts the se- lected configuration for which S- GPCA achieves highest valida- tion accuracy. The performance of the best method in Table []] respectively of G-SAGE, (unsu- pervised) GPCA, and APPNP, is also shown for comparison. Notably, supervised GPCA pro- vides slight gain over unsuper- vised GPCA across all datasets, which also improves over the competing baseline methods.
CoRA
CiTeSEeR
PUBMED
U-GPCA
81.10 (0.00) 71.80 (0.75) 78.78 (0.36)
S-GPCA (ALL 8>0)
81.17 (0.27) 73.20 (0.71) 79.40 (0.69)
S-GPCA 8=0.1
81.17 (0.27) 72.07 (0.37) 79.40 (0.69)
S-GPCA 3-0.2
81.90 (0.00) 73.20 (0.71) 78.73 (0.59)
TABLE
BEST
81.48 (0.83) 71.80 (0.75) 78.95 (0.36)
8

---

Under review as a conference paper at ICLR 2022
5.4 Q3: GPCANET-INITTALIZATTOO FOR GCN
Finally, we evaluate the effectiveness of and robustmess under different model sizes, i.. number of layers L number of training parameters. For comparison, Xavier initialization (Glorot & Bengio 2010) is also used to initialize GCN.
for GCN in terms of performance
Table 3: Test set performance of GCN with Xaiver- versus GPCANET-iiitiaizzatonn w.r.t. varying number of layers (L) across all datasets. Each reported value is based on the best se- lected configuration on validation data. GPCANET-init. enables higher performance that is also stable with increasing depth.
We report the test set perfor- mance (averaged over 5 seeds) of the GCN model using both initializations in Table 3 The results show that GPCANET- initialization tends to outper- form the widely-used Xavier initialization. The improve- ment grows with increasing num- ber of layers, which is sig- nificant at large depths. No- tably, GCN with GPCANET- initialization exhibits stable per- formance across all layers.
DATASET
L=2
L=3
L=5
L=10
10
L=15
CORA SAIVER-INIT 80.62
80.62
79.40
76.37
66.07
CORA GPCANET-INIL
81.67
79.50
80.90
79.82
78.00
CITESEER XAIVER-INIT
71.25
70.15
71.10
61.90
57.40
CITESEER GPCANET-INIT
71.27
69.27
70.15
68.67
67.87
PUBMED XAIVER-INIT
78.42
77.90
77.07
77.00
45.80
PUBMED GPCANET-INIT
78.05
77.25
78.07
77.80
78.03
ARXIV XAIVER-INIT
69.61
70.64
70.33
68.32
61.68
ARXIV GPCANET-INIT
69.76
70.72
70.52
69.77
66.28
Besides looking at the av- fur-
erage performance, ther study whether GPCANET- initialization improves the train- ing robustness, by reducing performance variation across different seeds. To this end, we first choose the best configuration for each initialization method based on validation performance, and train the GCN model with the chosen configuration using 100 random seeds.
PRODUCTS XAIVER- INIT
77.90
78.65
78.08
76.27
74.70
PRODUCTS GPCANET-INI
78.13
78.71
78.22
77.47
75.90
In Figure we present the histogram of test set accuracy over 100 runs with different seeds for ARXIV. (For re- sults on other datasets, see Ap- pendix. A For both 2-layer and 15-lr GCN, GPCANET- initialization not only outper- forms Xavier-initialization w.r.t. average performance, but also in terms of robustness, achiev- ing much lower performance variation and few bad outliers, especially for deeper GCN. As such, it acts as a strong data-driven prior, facilitating the training of numerous parameters across many layers by identifying a promising region of the parameter space from which supervised fine-tuning is initiated.
Aniv, Layer GCN
Arxiv, 15 Layer GCN
GPCANst-iIE
12-
GPGANuS-ini Kavier Init
Xoster Init
Couns
Counts
2
65.4
63.6
69.8
70.0
54
50
60
62
62
05
68
Tist sccuracy
Test accuracy
Figure 2: Comparison between Xavier-init. and GPCANET-inie in terms of test accuracy robustness over 100 seeds on ARXIV. GPCANET-init. enables robust training especially at larger depth.
6 CONCLUSION
In this work we have (1) discovered mathematical connection between GPCA and graph convolution of GCN and PPNP; (2) extended GPCA to the nepii-)supervised setting: (3) proposed GPCANET, by stacking GPCA and nonlinear activation, which is a generalized GCN model with an additional hyperparameter to control the degree of graph regularization, and (4) introduced the GPCANET- initialization based on the established connection. Accordingly, we designed extensive experiments demonstrating that (i) the unsupervised shallow GPCA achieves comparable or better performance than GCN, APPNP, well as other modern GNNs which suggests that graph convolution's 's power is mainly driven by graph regularization; (ii) semi-supervised GPCA helps improve performance and should be powerful yet simple baseline in future research; (i81) GPCANET enables the training of shallow models with competitive performance via increasing the degree of graph regularization at each layer, with reduced memory and training time cost; and finally (iv) APPCANE-imitializatee acts as a strong
prior for GCN training, enabling robust performance. Our methodological contributions 3) & 4) above) capitalize on the discovery of our theoretical findings 1) & 2) ). shedding new light toward a better understanding and design of GNNs.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Suresh Balakrishnama and Aravind Ganapathiraju. Linear discriminant analysis-a brief tutorial. Institute for Signal and information Processing, 18(1998):1-8, 1998.
Y. Bengio, A. Courville, and P. Vincent. Representation learning: A review and perspectives. IEFE Transactions on Pattern Analysis and Machine Intelligence, 1598):1798-1888, August 2013. ISSN 0162-8828. doi: 10. 11119/9TAMII200
h http: htt.::://eeexxploree feee.org. document/6472233 Zu bearbeitendes Review.
Tsung-Har Chan, Kui Jia, Shenghua Gao, Jiwen Lu, Zinan Zeng, and Ma. PCANet: simple deep learning baseline for image classification? IEEE Transactions Image Processing, 24(12): 5017-5032, 2015.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 257-266, 2019.
Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. fair comparison of graph neural networks for graph classification. In International Conference Learning Representations (ICLR), 2020. URL https: /ttps////peeeeee.eeeeooom net.:/twwwwweeeeeeeeeee.ee.eee forttt/foummmmmmm - 6NFPB
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Brian Gallagher, Hanghang Tong, Tina Eliassi-Rad, and Christos Faloutsos. Using ghost edges for classification in sparsely labeled networks. In International Conference Knowledge Discovery & Data Mining, pp. 264-264, ACM, 2008, URL http:///b/l
uni trier.riee. de/ conf/
kdd/kdd2008 htt.:httmlmlalaaacccmmmc 4aalagheeeel
Paul Geladi and Bruce R Kowalski. Partial least-squares regression: tutorial. Analytica chimica acta, 185:1-17, 1986.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the 13th International Conference on Artificial Intelligence and Statistics, pp. 249-256, 2010.
G.H. Golub and C.F. Van Loan. Matrix Computations. Johns Hopkins University Press, 1989.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs In Advances in neural information processing systems, pp. 1024-1034, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance imagenet classification. In Proceedings of the IEEE international Conference on Computer Vision, pp. 1026-1034, 2015.
Weihua Hu, Matthias Fey, Marinka Zitikk Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.006 000807 2020.
Sergey Ioffe and Christian Szegedy. Batch normalization:
Accelerating deep network training by reducing internal covariate shift. International Conference on Machine Learning, pp. 448-456 PMLR, 2015.
Bo Jiang, Chris Ding, Bio Luo, and Jin Tang. Graph-laplacian PCA: Closed-form solution and robustness. Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pp. 3492-3498, 2013.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations (ICLR), 2017.
10

---

Under review as a conference paper at ICLR 2022
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations (ICLR), 2019.
Philipp Krähenbühl, Carl Doersch, Jeff Donahue, and Trevor Darrell. Data-dependent initializations of convolutional neural networks. In International Conference on Learning Representations (ICLR), 2016.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convolu- tional neural networks. In Advances in Neural Information Processing Systems, pp. 1097-1105, 2012.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Qimai Li, Xiao-Ming Wu, Han Liu, Xiaotong Zhang, and Zhichao Guan. Label efficient semi- supervised learning via graph filtering. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 9582-9591, 2019.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. International Conference on Learning Representations, 2020. httttt:://oppeeeeeeeeeee
net forum?
id=B1 111111bb4wwww
Cheng-Yeu Yaw Low, Andrew Beng-Jin Teoh, and Kar-Ann Toh. Stacking PCANet+: An overly simplified convnets baseline for face recognition. IEEE Signal Processing Letters, 24(1 24811):1511-1555, 2017.
Yao Ma, Xiaorui Liu, Tong Zhao, Yozen Liu, Jiliang Tang, and Neil Shah. A unified view graph neural networks as graph signal denoising. arXiv preprint arXiv:20/0.0/777, 2020.
Dmytro Mishkin and Jiri Matas. All you need is a good init. arXiv preprint arXiv: 2015.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4602-4609, 2019.
Hoang NT and Takanori Machara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint arXiv: 1905. 2019.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations (ICLR), 2020. URL
http::s://ppeerevieeee net/ Forum?id=S1 d02FFPr
Victor Y Pan and Zhao Q Chen. The complexity of the matrix eigenproblem. In Proceedings of the 31th annual ACM Cymposium on Theory of Computing, pp. 507-516, 1999.
Xuran Pan, Shiji Song, and Gao Huang. A unified framework for convolution-basee graph neural networks, 2021. URL
Andrew M Saxe, James L McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. arXiv preprint arXiv:1312.6120 2013.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-9)) 93, 2008
Mathias Seuret, Michele Alberti, Mareus Liwicki, and Rolf Ingold. Pca-initialized deep neural networks applied to document image analysis. In 2017 14th IAPR International Conference on Document Analysis and Recognition, volume 1, pp. 882. IEEE, 2017.
Nauman Shahid, Nathanael Perraudin, Vassilis Kalofolias, Gilles Puy. and Pierre Vandergheynst. Fast robust PCA on graphs. IEEE Journal of Selected Topics in Signal Processing, 10(4):740-756 2016.
David I Shuman, Sumil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing on graphs: Extending high- high-dimensional data analysis to networks and other irregular domains. IEFE Signal Processing magazine, 30(3):83-98, 2013.
11

---

Under review as a conference paper at ICLR 2022
Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. In International Conference on Learning Repre- sentations, 2020. URL /tt.:ttpss//peeeveeee.....t / hrtp://ww..e...ruuuuuooooo//////
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. In International Conference on Learning Representations (ICLR), 2018.
Petar Veličković, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In International Conference on Learning Representations (ICLR), 2019. URL https: /ww.etteeee.peerrriii........ee http://reeeee..teetooorrnnnooooe
iAcKQ
Raimar Wagner, Markus Thom, Roland Schweiger, Günther Palm, and Albrecht Rothermel. Learning convolutional neural networks from few samples. In The 2013 International Joint Conference Neural Networks (JJCNN, pp. 1-7. IEEE, 2013.
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, 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In International Conference on Learning Representations (ICLR), 2019. URL https
//openreview. net htt.:neeeooouur..rrrG6666.....
Zhenyue Zhang and Keke Zhao. Low-rank matrix approximation with manifold regularization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35()):17771129, 2012.
Lingxiao Zhao and Leman Akoglu. Paimorr: Tackling oversmoothing in gnns. In International
Conference on Learning Representations (ICLR), 2020. /ttp:/ttts////oeerrevett
Forum?id=rken 1TtwB.
Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui. Interpreting and unifying graph neural networks with an optimization framework. arXiv preprint arXiv:2101.11859 2021.
12

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A.1 PROOF OF THROREM 3.1
Proof. We give the proof in two steps.
Step 1: For fixed W, Solve optimal Z" function of W: When fixing W as constant, the problem becomes quadratic and convex. There is a unique solution, given by first-order optimal condition. Let l denote the objective function as given in equation
Its gradient be calculated as
de
oz - - - 2XW
2
(15)
Setting equation 15 leads to the solution Z" aT+
Step 2: Replace Z with Z", Solve optimal W Substituting Z in objective & with Z = (I
a we reduce the optimization to
min W.WTW=I
( XWW" F + T [I'
(16)
For this part only, let M = (I + +L)- to simplify notation. We can show that equation 16 is equivalent
Tr(Xx - WXW. WWWW"WW'XX"
min W.W. W=I
a 2TTMMM T X" XTMXMX))
(17)
Using the cyclic property of (Tr)ace (and plugging (I + aL)- for M back), we can write it as (see Supp. A.2 for detailed derivation.)
max W.W.W W=
Tr -
(18)
Based on the spectral theorem of PSD matrices, the optimal solution W of problem equation T8 is the combination of eigenvectors, associated with the largest e eigenvalues of the graph-revised covariance matrix XT((1 + -X.
A.2 DERIVATION FROM EQ. EQUATION 17 TO EQ EQUATION 18
For this part only, A (I+ aL) to simplify the notation. We can show that equation 16 equivalent to
min W.
Tr(xx") - (T(AXWWXX))
THAXWW WWT x X XTAXX) 2 (T(AXWWXX") TMAXWW"X
TT T X ALAXW)
(19)
Using the cyclic property of (Tr)ace, we can write
2Tr(WT AXW) TH(WT X AAXW)
W.
a TT X" ALAXW)
Tr [ (2A - AA A(aL)A)XX)
max W
Tr [ (A+ a.)
max W
Tr W (I
(20)
W.
where the objective simplifies upon replacing A with (T + -
13

---

Under review as a conference paper at ICLR 2022
A.3 DERIVATION OF EQUIVALENCE IN EQ. EQUATION 9
[corr(Y, 2)] [corr(Y, (Y, z)] var(z)
max x
var(Y) 2)] [corr(Y, ( z)] var(z)
max
(21)
[oov(Y, x) T co)(Y)
max
(22)
where cov(Y, / var(Y))oorr(, z) vvr(z)
max
[ 2] [T22
(23)
max x
z yYYYT
(24)
Note that in equation 21 added the term var(Y) without affecting the optimization problem with respect to z.
A.4
DATASET STATISTICS
Table 4: Statistics of used datasets.
DATASET
#NODES
#EDGES #FEATURES
#CLASSES
TRAIN/VAL//TSST
CORA
2,708
5,429
1,433
5.2% 11188.5%%366999
CITESEER
3,327
4,732
3,703
6
3.6%
PUBMED
19,717
44.338
500
3
0.3% %
ARXIV
169,343
1,166,243
128
40
54% 92888% %
PRODUCTS
2,449.029
61,859,140
47
8%/2%/90%%
Datasets used in the experiments are presented in Table 4 Cora, CiteSeer, and PubMed can be
downloaded in Pytorch Geometric Library Fey & Lenssen (2019). Arxiv and Products can be accessed in http::////oo.sssffor...o...
A.5 HYPERPARAMETER CONFIGURATIONS
We setup hyperparameters pool for each dataset, presented in Table All methods use the same pool. The only exception is GPCA, GPCA is just 1-layer shallow model which can be trained with lager learning rate; we use 0.1 learning rate for on all datasets.
Table 5: Hyperparameters pool for each dataset, includes learning rate (LR), weight decay (WD), number of layers (#layers), hidden size, dropout, a, and B. For ARXIV and PRODUCTS, weight decay is set as 0 because the dataset large and no overfit happened. Same reason for choosing smaller dropout rate for them.
DATASET
LR
WD
#LAYERS
HIDDEN
CORA
0.001
[0.0005, 0.005, 0.05]
3,
10,
15]
[128, 256]
CITESEBR
0.001
[0.0005, 0.005, 0.05]
[2
10,
15]
[128, 256]
PUBMED
0.001
[0.0005, 0.005, 0.05]
[2,
3,
5.
10.
15
[128, 256]
ARXIV
0.005
0
3.
10.
15]
[128, 256]
PRODUCTS
0.001
12. 3.
15]
[128, 256]
DATASET
DROPOUT
CORA
[0, 0.5]
[1.5,
10,
20,
50]
[0. 0.1, 0.2]
CITESEER
[0. 0.5]
[1
10,
20, 50]
[0,
0.1, 0.2]
PUBMED
0.5]
[1 10.
20,
50]
[0, 0.1.1.1.. 0.21
ARXIV
[0, 0.2
[1, 10,
20.
50]
PRODUCTS
[0, 0.1]
[1
10,
20,
50]
Models are trained every configuration across HP pools and picked based validation perfor- mance. We use the Adam optimizer for all models. Learning rate first manually tuned for each dataset achieve stable training, and the same learning rate is fixed for all models-wa empirically
14

---

Under review as a conference paper at ICLR 2022
observed that learning rate is sensitive datasets but insensitive models. For GPCA and GP- CANET, number of power iterations in Eq. equation 13 is always set to 5. All experiments use the maximum training epoch 1000 and repeat 5 times. Detailed configuration of HPss can be found in Supp. A.5 We mainly use a single GTX--0800 GPU for small datasets CORA, CITESEER, and PUBMED. RTX-3090 GPU is used for ARXTV and PRODUCTS.
Mini-batch training. As nodes are not independent, GNN is mostly trained in full-batch under semi-supervised setting. We use full-batch training for all datasets except PRODUCTS, which is large to fit into GPU memory during training. ClusterGCN Chiang et al. (2019), subgraph based mini-batch training algorithm, used train GCN and GPCANET. For evaluation, we still use full-batch since single forward pass can be conducted without memory issues. Initialization is also employed in full-batch.
Fair evaluation. Instead of picking the hyperparameter configurations manually, reported (test) performance is based on the best configuration selected using validation performance, where all models leverage the same hyperparameter pools. Further, each configuration from the pool is conducted times to reduce randomness.
A.6 GPCA WITH VARYING
Table 6: Performance of unsupervised GPCA (3 0) for varying a w.r.t. mean test accuracy and standard deviation (in parentheses), GPCA (best a:) selects a E {1, 10, 20, 50} based on validation, whereas GPCA with specific a uses the specified fixed a.
CORA CITESEER
PUBMED ARXIV PRODUCTS
81.10
71.80
78.78
71.86
79.23
GPCA (BEST o)
(0.00)
(0.75)
(0.36)
(0.18)
(0.14)
72.57
70.90
76.92
65.47
73.65
GPCA-a=1
(0.79)
(0.58)
(0.30)
(0.26)
(0.07)
80.95
71,80
79.40
70.69
78.66
GP
(0.17)
(0.75)
(0.29)
(0.11)
(0.09)
82.23
71.65
78.78
71.37
79.24
GPCA-a=10
(0.58)
(0.53)
(0.36)
(0.09)
(0.09)
82.05
72.15
78.15
71.86
79.23
GPCA-a=20
(0.54)
(0.47)
(0.50)
(0.18)
(0.14)
81.10
71.50
78.00
71.48
78.92
GPCA-a=50
(0.00)
(0.32)
(0.19)
(0.15
(0.10)
A.7 CONFIGURATIONS FOR EXPERIMENTS OF 1~3-LAYER GPCANET
To train a shallow GPCANET with tunable (8=0 is used), we setup different pool for different number of layers, because the effect increasing a the same to increasing number of layers (shown in Fi. We report the pool for for each layer in Table For other parameters use the same setting mentioned Table
Table 7: Pool of a for 3~y-layer GPCANET, same across all datasets.
# LAYERS
POOL OF
1-LAYER
[10. 20, 30] 53, 10]
2-LAYER
3-LAYER
2,
A.8 GPCANET-INIT'S ROBUSTNESS FOR ADDITIONAL DATASETS
Histogram of test set accuracy over 100 runs for GCN initialized by Xavier-initialization and OPCAArT-initialization in CORA (Figure 3, CITEŠEER (Figure 4. and PUBMED (Figure (5) We have ignored PRODUCTS as it takes too long to run 100 times, but the result should similar.
15

---

Under review as a conference paper at ICLR 2022
Cora, 2-Layer GCN
Cora, 15-Layer GCN
GPCANet-init
GPCANet-init
Xavier-init
Xavier-init
15
Counts
Counts
10
10
5
5
0
0
79
40
50
70
Test accuracy
Test accuracy
Figure 3: Comparison between Xavier-init and GPCANET-init in terms of test accuracy robustness
over 100 seeds on CORA.
CiteSeer, 2-Layer GCN
CiteSeer, 15-Layer GCN
GPCANet-init Xavier-init
GPCANet-init Xavier-init
15
Counts
10
5
2
70.25 70.50 70.75 71.00 71.25 71.50
71.75
72.00
50
55
60
65
70
Test accuracy
Test accuracy
Figure 4: Comparison between Xavier-init and GPCANET-init in terms of test accuracy robustness over 100 seeds on CITESEER.
PubMed, 2- 2-Layer GCN
PubMed, 15-Layer GCN
GPCANet-init
GPCANet-init
15
Xavier-init
60
Xavier-init
Counts
Counts
40
10
5
20
77.5
78.0
78.5
79.0
70
80
Test accuracy
Test accuracy
Figure 5: Comparison between Xavier-init and GPCANET-init in terms of test accuracy robustness over 100 seeds on PUBMED.
16

---

Under review as a conference paper at ICLR 2022
A.9
TRAINING CURVE COMPARISON FOR GPCANET-INIT
Dataset: cora, params=(11 (1:: 10, Ih: 128, wd" 00s; 'drop": 10.0", 1, Validation
Train
08
07
0.7
05
0.-
04
04
03
02
GCN with Xavier-ant
GCN GPCANet-int
01
02-
GCN with Xavies-ni GPCANet-inE
0.1
GCN GPCANet-int
GCN with Xavier-int
50
100
150
200
250
0
100
150
200
250
50
100
150
200
250
epach
esoch
epoch
Figure 6: Training curve of 10-layer GCN initialized with Xavier initialization and GPCANET-Init on CORA.
Dataset: arti., params= (1:: 10, 128. "wd"'0..0" 10.0", 'drop': 10.0", 'at: 1.'
Validition
0.6
0.6
0.5
0.5
04
aCturscy
03
0.2
02
GCN with Xavier-intt
01
GCN with Xavier-nit with GPCANet-MN ini
GCN with Xavier-int:
0.
GCN GPCANet
GCN GPCANet-int
0.
50
100
150
200
250
0
100
150
200
250
50
100
150
200
250
spoch
eboch
epoch
Figure 7: Training curve of 10-layer GCN initialized with Xavier initialization and GPCANET-Init on ARXIV.
A. RUNTIME COMPARISON
We have analyzed the runtime complexity of GPCA, GPCANET, and GPCANET-Init in Sec 3.6 and show their runtime is linear in number of nodes. Table & presents the practical runtime comparison among all methods. measured in seconds/epoch for all models, and total initialization seconds for GPCANET-Ini. which verified the complexity analysis. Besides, GPCA extremely fast method with strong performance, and should be used as strong baseline in future research.
Table 8: Runtime comparison for different methods over all datasets.
CORA CITESEER
PUBMED
ARXIV PRODUCTS
Num Nodes
2,708
3,327
19,717
169.343
2,449,029
Features
1,433
3,708
500
128
100
GCN (seconds/epoch)
0.0025
0.0025
0.0040
0.0469
30.9544
GPCA (scconds/epoch)
0.0010
0,0010
0.0010
0.0072
0.0443
GPCANET (seconds/epoch)
0.0062
0.0101
0,0202
0.2172
31.3664
GPCANET-Inie (seconds)
0.836
1.614
0.659
0.657
2.477
17


Reviews:
[{"review_id": "wAzqM8R8IaV", "reviewer": "Reviewer_Awat", "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": "The proposed method is technically sound.  The relation between PCA and GCN is well established in this paper.  My concerns are as follows,\n\n1. The experimental results of GPCANET-INIT is insignificant. GPCANET-INIT performs very close to XAIVER-INIT when L=2 and L=3. Although GPCANET-INIT performs better than  XAIVER-INIT as the number of layers increase, it is not meaningful to compare them since the performance does not get better when the model gets deeper.\n2. The paper lacks a unified ablation study. It is unclear to me which part of the proposed model contribute most to the model performance.\n3. The computation cost of the proposed method is expensive due to eigenvalue decomposition.\n ", "summary_of_the_paper": "This paper relates GCN to PCA from the perspective of optimization. The authors propose Graph PCA that is a general form of GCN. They further introduce a regularization term that enforces nodes with same labels close to each other. ", "summary_of_the_review": "The biggest contribution of this paper is that it derives a more general GCN from the perspective of PCA.  The paper is well written and easy to follow. However, due to computation bottleneck and insignificant empirical results, I would rate this paper with a weak accept. ", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "m_kt20pilZK", "reviewer": "Reviewer_eCjq", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The contributions presented in this manuscript are quite obvious to my knowledge, but not very novel. Basically the paper is well-presented and written with great readability.  I cannot see any obvious flaws in the theory, analysis and experiments presented in this paper. In addition, the paper provides sufficient experimental evidence to back the main claims introduced by the authors. \nThe paper builds around the careful revisit to the classic graph-regularized PCA (GPCA). This observation is very interesting indeed. GPCA combines the PCA and the graph-structure information when building embedding (or latent representation) of the data, i.e., the feature linear transformation is restricted to the orthogonal projection. In fact, the PPNP is a similar way without restricting to the orthogonal feature transformation. In theory, for both GCN and PPNP, it is naturally to consider orthogonal transformation (parameter W) to make them as a constrained network, thus GPCANet becomes this special case. From this aspect, the novelty of the paper is limited. Similarly the idea of the semi-supervised version is not absolutely new, this has been long in application in supervised dimensionality reduction framework.    ", "summary_of_the_paper": "This manuscript looks at the classic graph-regularized PCA (GPCA) and try to build the connection with GPCA and the state-of-the-art GCN, and finally proposes a new deep graph network GPCANet.  The authors make a number of clear contributions as listed in the paper: 1) they build the connection between GPCA and GCN, 2) Based on this connection, they propose novel way of using such GPCA as a graph layer or as an initialization process for training GCN etc. and 3) thus present a new architecture of GPCANet that performs well on their tests. ", "summary_of_the_review": "In general, there is no theoretical flaw in the paper, and the paper is well presented. However the novelty is limited as the proposed model is a parameter constrained NNPN or GCN.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "eWVERgZhunS", "reviewer": "Reviewer_uURT", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The biggest strength of this paper is the strong experimental results on their new initializations scheme on deep GNNs. I think that result alone could be the basis of a decent paper, if other major concerns are addressed. \n\nBelow is a major concern that the authors need to address: \n\n1. the first order approximation statement (in the sense of the first order Taylor series approximation) only holds if the learned parameters W in the graph NN are the eigenvectors of X^T \\phi_\\alpha^{-1}X. If the learned parameters W in the NN are not the appropriate eigenvectors, then there is no meaningful first order approximation going on. The authors did not provide any justification for why the weights of the NN will be the eigenvectors of said matrix (though this is an interesting conjecture given that GPCA provides good initialization). I find the authors first-order approximation claim, at least as stated on a theoretical level, quite inaccurate. Perhaps a more accurate description be \"there exist some parameter W for the GCN under which the GCN convolutional operator becomes a first order approximation of GPCA\". This would be a much weaker (though more accurate) statement of the authors' claims. \n\n", "summary_of_the_paper": "The authors establishes a connection between GPCA and graph convolution (graph convolution as a first order approximation of GPCA), and uses that connection to 1. propose a GPCANet model and 2. propose a new initialization strategy for GNNs. ", "summary_of_the_review": "Nice experimental results. Theoretical claim misleading/inaccurate as stated. If theoretical claim is fixed, then this could be a good paper.  ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "-Ljx8zFdVHO", "reviewer": "Reviewer_YcNy", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "### Reasons to accept\n1. The paper shows us that regularization of weights may be necessary for GNNs.\n2. A new mixhop network architecture has been proposed that seems to be more promising than mixup performance.\n3. This paper is well-written and easy to follow.\n\n### Reason to reject\nIn general, I think the novelty of this article is insufficient mainly in the following points.\n1. GPCA is only GC Operation with an orthogonal constraint. Eq (5) ||X-ZW^\\top||_F^2+\\alpha\\Tr{Z^\\top L Z} is able to reformulated as:\n||XW-ZW^\\topW||_F^2+\\alpha\\Tr{Z^\\top L Z}. Because of W^\\topW=I, we can have a GC operator defined in (1). So all things in this paper are based on the GC operator with the orthogonal constraint. \n2. The definition of supervised formulation can hardly be considered as an original definition, and such methods are widely used in semi-supervised manifold learning (so much relevant literature), but this paper does not seem to be a suitable reference for the relevant methods.\n3. The performance of the algorithm, as I analyzed earlier, is not very different and has significant advantages.\n\n### Recommendation\n1. Unless authors can theoretically analyze what benefits the orthogonal constraint actually brings, it is really hard to evaluate the contribution of this paper.\n2. cite papers about semi-supervised (or supervised) manifold learning.\n\n(1) Zhu and et, al Interpreting and Unifying Graph Neural Networks with An Optimization Framework, WWW 2021.\n", "summary_of_the_paper": "This paper attempts to establish the relationship between Graph PCA and Graph Convolutional Layer, so as to define a new Graph Neural Network based on graph PCA.", "summary_of_the_review": "Basically, the whole paper is based on posing an orthogonal constraint on GCN. However, they do not provide any convincing theoretical justification for that. Although it is a good paper to read, I tend to reject this paper because of a lack of novelty.", "strength_and_weaknesses": "", "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:

Meta-review: The paper presents several related results. The initial main result consists in relating GPCA to GCN, showing that GPCA can be understood as a first order approximation of some specific instance of GCN where the W matrix is directly defined on data. This result is then exploited to define a supervised version of GPCA. As a follow-up the authors propose a novel GPCA-based network (GPCANet) and a GPCANet initialisation for GNNs. The paper is well written and easy to read. Empirical results are reported to verify the above mentioned connection between  GPCA and GCN, as well as the performances of  GPCANet  and the proposed initialisation for GNNs. Overall, while the mentioned connection was never explicitly reported in the literature, its existence is not surprising and thus its significance seems to be limited. Also the performances of GPCANet do not seem to be significant from a statistical point of view. The novel initialisation procedure for GNNs seems to be interesting and promising, although the used datasets may not make evident its full power. Authors rebuttal and discussion did not change the reviewers' initial assessment.
Decision: Reject