SlenderGNN: Accurate, Robust, and Interpretable GNN, and the Reasons for its Success
Authors: Jaemin Yoo
Meng-Chieh Lee
Shubhranshu Shekhar
Christos Faloutsos
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph neural networks
Linear models
Node classification
Heterophily graphs
Lightweight models

Abstract: Can we design a GNN that is accurate and interpretable at the same time? Could it also be robust to handle the case of homophily, heterophily, or even noisy edges without network effects? We propose SlenderGNN that has all desirable properties: (a) accurate, (b) robust, and (c) interpretable. For the reasons of its success, we had to dig deeper: The result is our GNNLIN framework which highlights the fundamental differences among popular GNN models (e.g., feature combination, structural normalization, etc.) and thus reveals the reasons for the success of our SlenderGNN, as well as the reasons for occasional failures of other GNN variants. Thanks to our careful design, SlenderGNN passes all the 'sanity checks' we propose, and it achieves the highest overall accuracy on 9 real-world datasets of both homophily and heterophily graphs, when compared against 10 recent GNN models. Specifically, SlenderGNN exceeds the accuracy of linear GNNs and matches or exceeds the accuracy of nonlinear models with up to 64 times fewer parameters.

Under review as a conference paper at ICLR 2023
SlenderGNN: ACCURATE, ROBUST, AND INTER- PRETABLE GNN, AND THE REASONS FOR ITS SUCCESS
Anonymous authors Paper under double-blind review
ABSTRACT
What is the simplest, but still effective, graph neural network (GNN) that we can design, say, for node classification? Einstein said that we should "make everything as simple as possible, but not simpler." We rephrase it into the 'careful simplicity' principle: carefully-designel simple model can outperform sophisticated ones in real-world tasks, where data are scarce, noisy, and spuriously correlated. Based on that principle, we propose SlenderGNN that exhibits four desirable properties: It is (a) accurate, winning or tying on 11 out of 13 real-world datasets; (b) robust, being the only one that handles all settings (heterophily, random structure, useless features, etc.): (c) fast and scalable, with up to 18x faster training in million-scale graphs; and (d) interpretable, thanks the linearity and sparsity we impose. We explain the success of SlenderGNN via a systematic study on existing models, comprehensive sanity checks, and ablation studies on its design decisions.
All reviewers
INTRODUCTION
What is the simplest, and still performant, graph neural network (GNN) that can design? GNNs (Kipf & Welling, 2017; Hamilton et al., 2017: Gilmer et al., 2017) have succeeded in various graph mining tasks such as node classification, clustering, practitioner to choose proper model for each task without spending extensive time on searching, tuning, and training models due large number of GNN variants. Given all these variants, which one should a practitioner use first? Which are the strong and weak points of each variant? Could we design variant that matches all of the strong points and avoids all the weak ones?
link prediction. However, it is difficult for
In response to the questions above, we propose SlenderGNN based on the 'careful simplicity' prin- ciple: a simple, but carefully-designed model can be more accurate than complex ones due to better generalizability, robustness, and easier training. The design decisions of SlenderGNN (D1-4 in Sec- tion 4.2) are carefully made to follow this principle by observing and addressing the pain points of existing GNNs; for example, generate various forms of graph-based features and combine them (DI), propose structural features (D2), remove redundancy in the generated features (D3), and make the propagator function contain no hyperparameters (D4). The resulting model, SlenderGNN, is our main contribution (C1) which exhibits the following desirable properties:
All reviewers
C1.1 Accurate on both real-world and synthetic datasets, almost always winning tying in the first place (see Figure 1b, Table 2, and Table 3).
C1.2 Robust, being able handle numerous real settings such as homophily, heterophily, no network effects, graphs with useless features (see Figure 1a and Table 2).
C1.3 Fast and scalable, using few, carefully chosen features, it takes only 32 seconds on miclion-scale graphs (ogbn-Productt) on stock server (see Figure lb).
C1.4 Interpretable, learning the largest weights on informative features, ignoring noisy ones, based on the linear decision function (see Figure 2).
The natural question that arises from the success of SlenderGNN
All reviewers
"How is it possible that a simpler model is more accurate than sophisticated, more expressive one?"
Q:
Our intuitive justification for the success of SlenderGNN is as follows: (a) Occam's 's razor: Since a statistical model tries 'explain' the given labels, the simplest explanation performs best in general.

---

Under review as a conference paper at ICLR 2023
Graph
Feature
DGG
sooc d'ON
GON SAGE
APPNP GPR
SlenderGNN
Nolsy (uselese)
Sementic
/
Hamophily
Noisy (useless)
Hetorophily
Noisy (useless)
Hamophily
Structural
4
Hatorophily
Structral
Homophily
Semantic
Hotorophily
Semantic
(a) SlenderGNN succeeds in all sanity checks, while none of the existing models does. The table is generated from the results of actual experiments in Table 2: v means success (accuracy 80%).
ogbnn-arXiv
ogbn-Products
Faster
2.5x
125
18.0x Faster
Recuracy 199)
Faster
Aecuracy 1S]
760
60-
1.1X Higher
DOC
Accuras S
Doc
1.1x Higher
00c
Higher
CCN
62.5
-5
600
101
10
3x10 4K:00
1.1
10
Run Time (s)
Run Time (s)
Run Time Isi
(b) SlenderGNN wins both on accuracy and training time: it represented as the red star in (left) ogbn-arXiv, (middle) ggbn-Productt and (right) Pokec, which are large real-world graphs (1.2M, 61.9M and 30.6M edges, respectively). Several baselines out of memory ('crossed out').
Figure I: SlenderGNN outperforms existing GNN models, is fast, and passes all sanity checks. See our main results for details (sanity checks in Section 5 and real-world experiments in Section 6).
(b) Overfitting: Complex models often suffer from overfitting, exacerbated by the fact that training data are usually scarce and expensive. (c) Spurious correlations: Even with sufficient labeled data, model trained on noisy features may latch on spurious correlations, which hurt its performance; simple model effectively suppresses such noisy features as our design decision D3.
In addition the intuitive arguments above, our extensive experiments provide hard evidence in fa- vor of the 'careful simplicity' principle: SlenderGNN outperforms complex GNNs in both synthetic (in Table 2) and real-world (in Table 3) datasets, and even own variants that use nonlinear feature transformation in 9 of the 13 real-world datasets (in Table 4).
Not only we propose a carefully designed, high performing GNN, we also explain the reasons of its success. This is thanks to our two additional contributions (C2-3):
C2 Explanation: We propose GNNLIN, a framework for the systematic linearization of existing GNNs. As shown in Table I and Section 3, our GNNLIN highlights the similarities, differences, strengths and weaknesses of successful GNN baselines.
C3 - Sanity checks: We propose wide range of scenarios (homophily, heterophily, block- communitics, bipartite-grant communities, etc.), which reveal the strong and weak points of each GNN variant: see Figure la with more details in Table 2 and Section 5.
Reproducibility: Our code is available at http://itt.y/ffh///ttttt along with our datasets for "sanity checks' and real-world datasets of homophily and heterophily graphs.
R-D5
PROBLEM DEFINITION AND RELATED WORKS
We introduce the problem definition semi semi-supervised node classification, symbols frequently used in this paper, and related works on graph neural networks (GNN).
Problem definition
We define the problem of semi-supervised node classification as follows:
Given An undirected graph G X), where A p=*= is an adjacency matrix, X R is a node feature matrix, n is the number of nodes, and is the number features Given Labels y E (1.... .c] c for m nodes, where m < n, and e is the number of classes.
2

---

Under review as a conference paper at ICLR 2023
Predict the unknown classes of m test nodes in G.
We use the following symbols to represent modified adjacency matrices. À = i+ the adjacency matrix with self-loops. D diag A1,x1) is the diagonal degree matrix of A, where 1nx1 is the matrix of size n x filled with oncs. A Ayy = D 1/2 AD 1/2 is the symmetrically normalized A. Similarly, Asym D 1/2 AD-1/2 There are other types of normalization yow = D A and cc = AD (and accordingly Arow and Acol), which we call row and column normalization, respectively, based on the position of the degree matrix. Refer to Appendix A for the table of symbols used frequently in this work.
1/2 is also the symmetrically normalized A but without self-loops.
As background, formally define logistic regression (L.R) as a function to find the weight matrix W that best maps given features to predicted labels by linear function.
Definition (I.R), Given a feature X E RRnd and a label y E TIm", where m. S. Ti is the number of observations, let Y E Rmxe be the one-hot representation of y, and Yeş be the (i- element in Y. Then, logistic regression (LR) finds an optimal weight matrix W E BBde as follows:
1
exp(w.,xx))
LR(X. = arg max
Σ =1j=1
yiu log Dis
where dig = Ei= k= exp(w (xp(w].x,)
(1)
and w.g is the j-th column of W. We omit the bias term for brevity without loss of generality.
2.1 RELATED WORKS
Graph neural networks There are many recent GNN variants; recent surveys (Zhou et al., 2020; Wu et al., 2021) group them into spectral models (Defferrard et al., 2016; Kipf & Welling, 2017), sampling-based models (Hamilton et al., 2017; Ying et al., 2018), attention-based models (Velick- ovic et al., 2018; Kim & Oh, 2021; Brody et al., 2022), and deep models with residual connections (Li et al., 2019; Chen et al., 2020). Decoupled models (Kliepera al., 2019a;b; Chien et al., 2021) separate the two major functionalities of GNNs; the node-wise feature transformation and the prop- agation. GNNs are often fused with graphical inference (Yoo et al., 2019; Huang et al., 2021).
Linear graph neural networks Wu et al. (2019) proposed SGC by removing the nonlinear activa- tion functions of GCN (Kipf & Welling, 2017) reducing the propagator function to a simple matrix multiplication. Wang et al. (2021) and Zhu & Koniusz (2021) improved SGC by manually adjust- ing the strength of self-loops with hyperparameters, increasing the number of propagation steps. Li et al. (2022) proposed GCC, which improves the performance of DGC (Wang et al., 2021) on het- erophily graphs by combining multiple propagation settings (i.c. bandwidths). The main limitation of these models is the high complexity of propagator functions with many hyperparameters, which impairs both the robustness and interpretability of decisions even with linearity.
Graph kernel methods Traditional works graph kernel methods (Smola & Kondor, 2003; Ioan- nidis et al., 2017) are closely related to linear GNNs, which can be understood as applying a linear graph kernel to transform the raw features. A notable limitation of such kernel methods is that they are not capable of addressing various scenarios of real-world graphs, such as heterophily graphs, as their motivation is to aggregate all information in the local neighborhood of each node, rather than ignoring noisy and useless ones, We implement three popular kernel methods as additional baselines and show that our SlenderGNN outperforms them in both synthetic and real graphs.
R-V2
3 PROPOSED FRAMEWORK: GNNLIN
Why do GNNs work well when they do? In what cases will a GNN fail? We answer these questions with our proposed GNNLIN, which reveals the essence of each GNN variant. The idea is to derive the feature propagator function that each variant uses ignoring nonlinearity. Our observations help us do the careful design of our SlenderGNN, which we describe in Section 4.
Definition 2 (Linearized GNN). Given a graph G (A, X), let f(: ()) be a node classifier function to predict the labels of all nodes in G as y = f(, X;0), f), where is the set of learnable parameters. Then, is linearized if [W) and an optimal weight matrix W hxxx is given as
W (A,
3

---

Under review as a conference paper at ICLR 2023
Table 1: GNNLIN framework is general encompassing popular GNN models. The and ** super- scripts mark fully and partially linearized models, respectively, see Section 3.1 for details.
Model
Type
Propagator function P(A, X)
Hyperparameters
LR
Linear
X
SGC
Linear
A Anym
K K, T K,
DGC
Linear
[[1 T/K)I+ (T/K)A | 1
S'GC
Linear
ΣK (aT a)) a Sym)
GºCN
Linear
[1 (Ti/K)((b 1)I Asym) )
K, N.N.T. T..b
PPNP*
Decoupled
[I (1 Ayym) --
APPNP*
Decoupled
- a(1 a)* A + +1 aa*aa*aA*a A X
K,
GDC
Decoupled
Saym X where S = sparse, 12 12 aa) A
a,
GPR- *NN
Decoupled
K
ChebNet*
Coupled
K- A X
K
GCN
Coupled
Same as SGC
K
SAGE*
Coupled
A X
K
row
GCNII"
Coupled
X ((1 A + x
K,
k=
sym
GAT
Attention
[diag(Xw...)) A Adiag(Xwe.2)
K, Wh.1, Wx,2
k=
DA-GNN#*
Attention
k- diag(A (Am Xw) A.y
K. w
where P is a feature propagator functioooo that linear with X. and contains no learnable parameters, and (AA,X) E R= We ignore the bias term for brevity without loss of generality.
Definition (GNNLIN), Let (=;0) be a (nonlinear) GNN. GNNLIN is to represent I as a linearized GNN by replacing all (nonlinear) activation functions in f with the identity function and deriving variant f' that is at least as expressive as but contains no parameters in P.
GNNLIN represents the characteristic of a GNN as the linear feature propagation function P, which transforms raw features X by utilizing A. Lemma shows that GNNLIN generalizes existing linear GNNs. Logistic regression is also represented by GNNLIN with the identity XX) X. X
Lemma 1. Our GNNLIN framework includes existing linear GNN models as special cases: SGC, DGC, SC,, and GCCN.
Proof. The proof is given in Appendix B.
3.1 LESSONS FROM GNNLIN
Table 1 shows the linearized form of existing GNNs generated from our GNNLIN framework. Refer to Appendix C for the detailed information. Based on the result, we spot the fundamental similarities and differences among the GNN variants. There are three distinguishing factors.
Distinguishing Factor (Combination of features). How should we combine the node features, the immediate neighbors' features, and the K K-step-away neighbors' features?
GNNs propagate information by multiplying the feature X with (a variant of) the adjacency matrix A multiple times. There are two main choices in Table 1: (1) summation of the transformed features up K steps (most models), and (2) concatenation (GPR-GNN GraphSAGE, and GCNII). Simple approaches like SGC are categorized as summation due to the self-loops in Asym-
Distinguishing Factor (Modification of adjacency matrices). How should we normalize or modify the adjacency matrix?
The three prevailing choices are (1) symmetric vs. row normalization. (2) the strength of self-loops, including making zero self-loops, and (3) static vs. dynamic adjustment based on the given features. Most models the symmetric normalization Agym with self-loops, but some variants avoid self- loops and use either row normalization Arow or symmetric one Agym Recent models such as DGC, G2CN and GCNII determine the weight of self-loops with hyperparameters, since strong self-
4

---

Under review as a conference paper at ICLR 2023
allow one to increase the value of K for distant propagation. Finally, attention based models learn the elements in A based on node features, making propagator functions quadratic with X.
Distinguishing Factor 3 (Heterophily). What to do if the direct neighbors differ in their features or labels?
In such cases, the simple aggregation of the features of immediate neighbors may hurt performance, and therefore, several GNNs do suffer under heterophily shown in Figure 1a and Table 2. GNNs that can handle heterophily adopt one or more of these ideas: (1) using the square of A as the base structure (in GºCN; "the enemies of my enemy are my friends"); (2) learning different weights for different steps (GPR-GNN, ChebNet, SAGE, and GCNII), and (3) making small or no self-loops in the A matrix (DGC, GC and GCCN). The idea is to avoid downplay the effect of immediate (and odd-step-away) neighbors. Self-loops hurt under heterophily, as they force to have information of all intermediate neighbors by acting implicit summation of transformed features.
PROPOSED METHOD: SlenderGNN
We propose SlenderGNN, novel GNN model that addresses the limitations of existing GNNs with the strict adherence to the 'carefuu simplicity' principle. We first present the pain points of existing GNNs derived from Table and then describe how SlenderGNN addresses them.
4.1 PAIN POINTS OF EXISTING GNNS
Pain Point (Lack of robustness). All models in Table fail to handle multiple graph scenarios at the same time, i.e., graphs with homophily, heterophily, no network effects, or useless features.
R-f2, D3
Models in Table I assume specific scenario, such as homophily or heterophily graphs, rather than being able to perform in multiple scenarios at the same time. For example, all of these models except ChebNet and SAGE include the self-loops in the updated adjacency matrix, emphasizing the local neighborhood even in graphs with heterophily or no network effects. This is the pain point that we also observe empirically from the sanity checks (in Figure la and Table 2).
Pain Point 2 (Failure on noisy features). All models in Table I depend on the node feature matrix X, and cannot fully exploit the adjacency matrix A if the given features are noisy.
R-f2, D3
Real-world datasets often contain noisy features, and the graph structure A plays an essential role in the performance of node classification in such cases. That is, desirable property for a robust model is to adaptively emphasize important features or disregard noisy ones to maximize its generalization performance, However, the models in Table lack such a functionality.
Pain Point 3 (Hyperparameters in propagators). The hyperparameters in propagator function P impair the interpretability of the weight matrix W, and force the re-computation of the transformed feature for every new choice during hyperparameter search.
The last column of Table 1 summarizes the hyperparameters in each P, which make the following limitations in terms of linear models. First, the interpretability of the weight matrix W is impaired, because it is learned on the transformed feature P(A, X) whose meaning changes arbitrarily by the choice of hyperparameters, Second, (AA, X) should be computed for each choice of hyperparam- eters, while it can be cached and reused for searching hyperparameters outside P.
4.2 DESIGN DECISIONS OF SlenderGNN
Summary: Considering all the pain points and adhering to the 'careful simplicity' principle, we make design decisions (D1-D4) that lead to the following propagator function P of SlenderGNN:
P(A,X) X)
X
g(A row X)
g sym X)
(3)
Structure
Node fentures
2-step neighbors
Neighbors
where 9(-) is the principal component analysis (PCA) for the orthogonalization of each component, followed by an L2 normalization, and U e "x contains r-dimensional structural features derived by running the low-rank singular value decomposition (SVD) on the adjacency matrix A.
5

---

Under review as a conference paper at ICLR 2023
DI: Concatenation of winning normalizations The main principle of SlenderGNN to acquire the robustness and generalizability, in response to Pain Point 1, is to transform the raw features into var- ious forms and then combine them by concatenation. In this way, SlenderGNN is able to emphasize essential features or ignore useless ones by learning separate weights for different components. The four components of Equation 3 are proposed to have their strength in different scenarios: the struc- tural information U, self-feature information X. two-step aggregation A for heterophily graphs, and the smoothed two-hop aggregation 2ym of local neighborhood, respectively.
R-f2, D3
Specifically, we use the now-normllized matrix Arow with no self-loops due to the limitations of the symmetric normalization A First, the self-loops force one combine all intermediate neighbors until the K hhpop distance, even in heterophily graphs where the direct neighbors should be avoided. Second, the neighboring features are rescaled based on the node degrees during an aggregation, even when we want simple aggregation of K" K-hopp neighbors preserving the original scale.
D2: Structural features In response to Pain Point 2 where features are missing, noisy, or useless for classification, then we have to resort to the adjacency matrix A ignoring X. At the same time, it is not effective to use raw A, which is a large sparse matrix. We thus adopt low-rank SVD with rank to extract structural features U. The value of r is automatically selected to keep 90% of the energy of A, where the sum of the largest r squared singular values divided by the squared Frobenius norm of A is approximately 0.9. When the graph is large, we set to be d for the size consistency.
5- R-f2, D3
We use two reliable methods to further address Pain Point 2 about noisy features: dimensionality reduction by PCA and regularization by group LASSO. First, we run PCA on each component independently to orthogonalize given features and to improve the consistency of learned weights. Second, we apply group LASSO to learn sparse weights on the component level, preserving the relative magnitude of each element and suppressing noisy features. To make the consistency between multiple components, we force all components to have the same dimensionality by selecting features from each component when adopting PCA.
D3: Orthogonalization and sparsification
f R-12, D3
We address Pain Point by making the propaga- tor function P contain no hyperparameters to tune for each dataset. Most models in Table contain such hyperparameters. For example, DGC a linear model, but its interpretability limited since selects K and T from arbitrary values, i.e., K E (250, 300, 900} and T E (5.27, 3.78, 6.0498). On the contrary, our effective design of P (i.e., D1 and D2) allows us to keep the small value of K = in all 13 datasets we use in the experiments without sacrificing its performance.
D4: No hyperparameters the propagator P
5 PROPOSED SANITY CHECKS
We propose sanity checks to evaluate the robustness of GNNs to various scenarios of node classifi- cation and to observe their strengths and weaknesses in different settings.
Graph scenarios We categorize possible scenarios of node classification based on the character- isties of node features X, graph structure A, and node labels y. We describe only the main ideas, leaving exact definitions of such scenarios to Appendix D.
Features X:
We consider three cases: random, structural, and semantic. The random case means that each feature is determined independently of all other variables. In the structural case, features give information of the graph structure, and in the semantic case, they directly provide useful information for node labels. Unlike the cases of edges and labels, which are mutually exclusive, features can be both structural and semantic at the same time.
Edges A: We consider three cases: uniform (no communities). clustered -block-diagonal), and hipartite. The uniform case means that every element dsj is determined independently of the other edges in A. In the clustered case, nodes having common neighbors are likely to make more edges, while it is the opposite in the bipartite case.
Labels y: We consider three cases: individual (no network effects, i.e., there is no predic- tive power of connectivity). homophily, and heterophily. In the homophily case, adjacent nodes are likely to have the same label, while it is the opposite in the heterophily case.
Feasibility Although there exist a total of 27 combinations for (X, y), not all of them are pos- sible to implement; for example, either homophily or heterophily y is not compatible with uniform

---

Under review as a conference paper at ICLR 2023
Table 2: SlenderGNN passes all sanity checks. The accuracy of all models on sanity checks; there are three groups of scenarios: (left) only features X help; (middle) only connectivity A helps; (right) both help. See the text for details on S, U, I, C, B, etc. Green is darker); red marks the ones that are too low (2z below the third place).
marks the top three (higher
helps and A useless C. Individual
A helps and X is useless (R. C. O) Homophily
Both and A help (s.
Model
(S. D.D
(S. Individual
(R. B. E) Heterophily
CI Homophily
(T. B. E)
(S. B. E)
Individual
Heterophily
Homophily
Heterphhlly
LR
83.720.6
63,720.6
83.720.6
24.2:0.7
24:2:0.7
71.420.9
66.822.2
83.420.6
83.4=0.6
Reg. Kerne
82.710.5
82.31066
82.710.4
27.910.4
24.11.
75.710.2
65.3.116
91.510.55
79.5.0..3
Diff. Kemel
26.821.7
27.6+2.3
27.3#1.8
38.028.7
$7.627.5
79.5=0.33
73.5=0.6
70.9=23,
56.1=27.
Kernel
72.2+007
72.2+119
73.0+0.8
37.0=0.4
24.5+1.3
81.3+1.2
51.0+111
94.5+0.9
57.8=0.7
SGC
44.6+-9.8
43.0+99.0
40.
64.3+007
50.2+114
87.1+0.6
84.3+-0.5
93.9+0.9
91.5-0.5
DGC
63.8110
66.3100.9
65.911.2
50.5113.
26.010.9
68.6.11.0
15.
96,2.10.4
$4.0.0..6
S²GC
79.91-0.6
7..8
80.1+-1.0
18.5:12
25.4:10.99
88.411.0
6..9
95.9:10.6
78.0
GPCN
25.21:0.3
25.32:011
25.01:0.2
24.21:111
25.02:0.1
18.511.0
88.6111.2
24.311.1
50.7131.
GCN
36.323.5
33.24:2.4
35,723,5
46.728.0
43.7219
83,321.
72.24117
91.221.2
80.3=3.9
SAGE
80,3+1.1
79.0+112
79.8+0.7
31.1=007
34.6#2.1
83,9+0088
81 01.3++0.7
94.4=0.5
94:4-0.9
GCNIT
73.5
73.21:09
73.610.9
30.7:0.7
2..1
84.2.10.8
69.0:11.4
90.6:10.9
8.24
APPNP
66.0#266
65.41:2.7
64.211.6
30.32:12
25.22:0.7
71.244499
43.8:12.0
83.243.88
58.714.55
GPR-GNN
73.4=0.4
73.5+1.3
73.9+0.7
74.6=0.7
65.9=2.1
89.9=0066
87 1..6
95.0=t111
91.9=1.1
GAT
32.74-5.5
30.++3.0
33.8++6.8
42.6+488
36.8+5.7
64.0+5577
55.6+668
68.5+7.1
67.0+12.
SlenderGNN
810+111
81.0209
81.2#1.0
87.1=1.4
89
88.1=20.5
88 88.0:007
94,420.6
93.9=0.5
After removing the infeasible combinations of variables, we categorize the remaining choices based on the predictive power of structure (A) and features (X) for labels (y).
A.
Results of sanity checks 'abbl 2 shows the results of sanity checks for our SlenderGNN and all baseline models (details of the baselines in Section 6). = represent top three methods (higher darker) with overlap within 2o, and represents accuracy below 20 of the third-best method. We run each experiment five times and report the average and standard deviation. We assume four target classes of nodes, and thus the accuracy of random guessing 25%. The letters represent the cases of X, A, and y. respectively: S (semantic X), R (random X), T (structural X), U (uniform A), C (clustered A), (bipartite A), I (individual y). O (homophily y), and E (heterophily y).
It is clear that our SlenderGNN is the only approach that passes all sanity checks. The four compo- nents in SlenderGNN are carefully designed to maximize its robustness for various graph scenarios. Most GNNs work well in the cases (S, C, O) and (T, C, O), where X is either semantic structural, A is clustered, and y is homophily, since many real-world datasets that recent works on GNNs use in their experiments follow such assumptions. However, many GNNs fail when graph is generated with different assumptions, as we summarize as follows:
R-D4
No network effects: In the cases of (S, ?, D, where ? is placeholder, only few models such as SAGE and GPR-GNI perform well. This is because A is not informative in such cases, and models are required focus on raw features X ignoring A.
Useless features: In the cases of (R, C, O) and (R, B, E), models are required to do the opposite since X is not informative: they should focus on A, ignoring X. Since there is no approach that explicitly uses A, all baselines show low accuracy.
Heterophily graphs: In the cases of (?, B. E), where ? is placeholder, the labels follow heterophily. Models like G2CN, SAGE, and GPR-GN perform well in these cases, since they address the heterophily in their designs (details in Section 3.
EXPERIMENTS
We perform experiments on 13 real-world datasets to answer the following research questions (RQ):
RQL. Accuracy:
How well does SlenderGNN work on real-world graphs?
RQ2. Speed and Scalability: How fast and scalable is SlenderGNN to large real-world graphs?
RQ3. Interpretability: How to interpret the learned weights of SlenderGNN?
RQ4. Ablation Study: Are all the design decisions of SlenderGNN effective in real-world graphs?
What if we add nonlinearity to SlenderGNN or increase its receptive field?
7

---

Under review as a conference paper at ICLR 2023
Table 3: SlenderGNN wins most of the times on 13 real-world datasets (7 homophily and het- erophily graphs) against 14 competitors. We color the best and worst results as in Table 2.
Model
Cora
CiteSeer
PubMed
Comp.
Photo
ArXle
Products
Cham.
Squirrel
Actor
Penn94
Twitch
Pokec
LR
51.52112
32.9445
7999.0.5
73
79331.5
48.5119
36,2:05
24.911.7
26.7119
27,8108
63.500.5
53.000.11
61.31000
Reg Komel
67.8425
62.14-44
834514
80.5114
87.1+1.2
0.M.
00M.
294422
24.5+23
16611
0.0
00M
D.O.M
DET. Kemtel
10.51:5
62.72388
82.1204
13.1210
59.3106
O.O.M.
O.0.M.
34,5279
20,313
24.7009
53.208
O.O.M.
O.O.M
RW Kernel
12.74:17
66.11399
831303
M4,2007
906407
63.2002
74,2:00
34.9335
25
26411.1
0311207
51.00111
593100
SGC
76.211.1
65.81399
84.1203
83.711
90.1109
05.0134
74.6251
36.1445
26.6108
6402111
56.50011
093100
68.2
25242.1
025204
58.1002
007101
SPaC
18.3415
8433-03
K11+08
9011108
62:0+74
583-18
34.9+49
267418
63.5-0.5
SK.7-0
612100
GPCN
76.5215
04.21.33
$1.430.5
$2.8216
38.810.55
0.0.M.
O.O.M.
007329
32.13115
24.310.5
0.0.M
O.O.M.
O.O.M
OCN
76.0112
65.029
84.3-0.5
K5.1+09
91 016405
62.8+06
GOM.
38.5+300
11
268404
62.9+0.7
$7.0+0.1
679404
SAGE
74,E13
63.7136
82.9304
K3.500
906110
61.5205
O.O.M.
3981443
27,0113
2731099
0.0.M.
56.1004
68.910.1
OCNI
77.8117
63443.0
86.90.
KL3E18
903300
45.5
M.M.M
315:25
21,9130
29011.5
64520.
569100
62.1103
APPNI
642+17
S3441.3
63.70099
47.3+0-3
474104
GPR GNN
2440
130210
58.520.5
M.O.M.
31.724.7
36,2116
29511.1
64.520
57.6202
67640.11
GAP
78.2112
0581440
836302
834114
91.7105
58.21100
O.M.M
39.134.1
28.0106
26440.44
605:03
0.0.M
0.O.M
SlenderGNN
37.51111
84.630.
913100
00:330:3
549-00
805-32
31.12077
309105
05:230
59,
139101
Datasets and competitors We use homophily and 6 heterophily graphs in experiments. which were commonly used in previous works on node classification (Chien et al., 2021: Pei et al., 2020; Lim et al., 2021), 1). We adopt various types of models as competitors: linear GNNs (LR, SGC, DGC, S'GC, and G2CN), coupled nonlinear models (GCN, GraphSAGE, and GCNII), decoupled models (APPNP and GPR- GPR-GNN), and attention- methods (Smola & Kondor, 2003), namely Regularized Laplacian, Diffusion Process, and the K- step Random Walk. They are used with LR as SlenderGNN is. We perform hyperparameter search based on those reported in their original papers. Refer to Appendix for details.
models (GAT). We also include three graph kernel
R-V2
Experimental setup graph by the 235%..55// of each experiment with different random seeds and report the average and standard deviation. All hyperparameter search and early stopping are done based on validation accuracy for each run.
We perform semi-supervised node classification by dividing all nodes in a ratio into training, validation, and testing data. We perform five runs
RQI. Accuracy In Table 3. SlenderGNN is compared against linear as well as the state-of-the- datasets (7 homophily and 6 heterophily graphs) We report represent the top three methods (higher is darker), rep- resents the accuracy below 20 of the third-best method, and represents the out-of-memory error (O.O.M.). Our SlenderGNN outperforms all competitors in 4 homophily and 5 heterophily datasets, and shows competitive accuracy the rest (11 out of 13 times among top three methods). Moreover, SlenderGNN is the only model without red cells, which demonstrates its robustness and generality. Many competitors run out of memory when the graph reaches the million-edge scale.
art nonlinear GNNs on 13
the accuracy in Table 3 where =
RQ2. Speed and scalability We plot the training time versus the accuracy of each model on the ogbn-arXiv,
R3
and Pokec datasets, which are largest in our benchmark, in Figure 1b. We report the training time of each model with the hyperparameters that show the highest validation accuracy. SlenderGNN achieves the highest accuracy in the ogbn-arXiv and while being 10.4x and 2.5x faster than the second-best model, respectively. SlenderGNN also shows the highest accuracy in the Pokec dataset, which is large heterophily graph, while being 18.0x faster than the best performing deep model. It worth noting that SlenderGNN's is even faster than LR in ogbn-arXiv, requiring only half the number of iterations that LR needs while optimizing Its fast convergence is owing to orthogonalization on each component of the features.
datasets,
RQ3, Interpretability Figure 2 illustrates the learned weights of our SlenderGNN for the sanity checks, where the ground truths are known. SlenderGNN assigns large weights to the correct factors in graphs with different mutual information between variables. When there are no network effects in Figure 2a, it successfully assigns the largest weights to the self-features g(X), ), ignoring all other components. When the features useless in Figure 2b, it puts most of the attention the structural features U. In the left two of Figure 2c, when the features are useful but largely correlated with the structure, it ignores the features. In the right two of Figure 2c, when every component is informative, SlenderGNNN assigns large weights to both self- and propagated features to maximize its accuracy.
< R-V3, D4
(X) and assigns the largest weights to the graph-propagated
RQ4. Ablation studies We perform three ablation studies to better understand how SlenderGNN works: its (a) linearity, (b) receptive field, and (c) four different components. We show the result on
R-V1, V3
8

---

Under review as a conference paper at ICLR 2023
Aeg, Welght (or Cach Comp.
2.00 2.
52%
aic-
230
Semamic Clusterec A Individualy y
Semartic Biparite indiviuall
230
o00
Strudtrall Clustered A
Structural Hipartit Hateroshity
Semantic Clustered hamopnilyy
Semartic Sipart Heterophily y
Uniform A salvidaaly
Clustored
Bipartite Heterophily
Homophily
hemophily Iy
(a) network effects
(b) Useless features
(c) Homophily and heterophily
Figure 2: SlenderGNN is interpretable: it suppresses useless information and focuses on the infor- mative ones for each scenario: (a) self-features, (b) structural features, and (c) mixed.
Table 4: Ablation Study SlenderGNN works best with linearity: SlenderGNN outperforms its own variants that replace the linear classifier or the PCA function g with a nonlinear module.
Model
Cor
Cinbbeer
PubMed
ArXiv
Products
Cham.
Squirret
Actor
Penn9
Twitch
Pokec
wi MLN-1
65.9t1.11
Sc2453
8355002
648400.
90 1011
63.820.1
85.7:0.0
40.042255
30.50.5
28.8+1.0
66.7117
60.5003
76,5+0.1
w/ MLP3
66.1+2.0
50.3236
820509
652260.8
90.:08
63.020.1
$49:109
38.5+5.55
30.90.
28.911.2
65.106
60.4:02
764400.2
w/ NL Trons
70.722.3
57585.1
810804
71A310
779822
57,0830
O.U.M
413333
300216
27.422
61821A
61.203
757330.5
77881.11
67.1:23
846E0S
M.3:0.7
918:05
6633:8
$4930.0
408843
3111-07
38.9186
6822:0
$9.760.
73.030.1
linearity in Table 4, and give the results of the last two experiments in Table 8 and 9, respectively, in Appendix F. Detailed information on the settings of ablation studies is also given in Appendix F. In short, we observe that (a) the linear version performs best, (b) the two-step aggregation is sufficient, and (c) all four components in SlenderGNN are essential in its performance.
Specifically, the success SlenderGNN against its nonlinear variants Table supports the power
R-f1, yl, v2, D2
of the 'careful simplicity' principle. The increased expressiveness harms the accuracy since (a) the
original SlenderGNN already effective to capture necessary information for classification, and (b) an increased number of parameters cause the loss of generality through overfitting. Needless say, the nonlinear variants take longer time in training, have more hyperparameters to tune, and lose the interpretability which is the great advantage of linear models (as we show in Figure 2).
CONCLUSION
The main contribution (CI) of this work SlenderGNN, which is designed by the 'careful simplicity' principle, and thus has a long list of desirable properties:
C1.1 Accurate: On both synthetic and real graphs, SlenderGNN exceeds the accuracy of state-of-the-art linear GNNs and matches the accuracy of nonlinear models.
SlenderGNN succeeds in graphs with homophily, heterophily, no network effects (i.e., random connections), and no meaningful features.
C1.2 Robust:
C1.3 Fast and scalable: SlenderGNN is scalable to million-scale graphs, where most of the existing models run out of memory, with up 18x less training time.
C1.4 Interpretable: SlenderGNN automatically selects important features and can justify its decisions based on the learned weights, thanks to its linearity.
Additional contributions focus on explaining the success of SlenderGNN:
C2 Explanation: The GNNLIN framework illuminates the fundamental similarities and differences of popular GNN variants (see Table 1).
C3 Sanity checks: Our sanity checks immediately highlight the strengths and weaknesses of each GNN method before it is sent production (see Table 2).
Reproducibility: Our source code and 'sanity checks' are available at https:/bbitlly33hWJkrk.
R-D5

---

Under review as a conference paper at ICLR 2023
REFERENCES
Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. science, 286 (5439):509-512, 1999.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In ICLR, 2022.
Ming Chen, Zhewei Wei, Zengfeng Huang. Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks, In ICML, 2020.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. ICLR, 2021.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NIPS, 2016.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In ICML,
Nathan Halko, Per-Gunnar Martinsson, and Joel Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev. 53(2): 217-288, 2011.
William I.. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurIPS, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. arXiv preprint arXiv:2005.006% 2020.
Qian Huang, Horace He, Abhay Singh. Ser-Nam Lim, and Austin R. Benson. Combining label propagation and simple models out-performs graph neural networks. ICLR, 2021.
Vassilis N. loannidis, Meng Ma, Athanasios N. Nikolakopouloss, and Georgios B. Giannakis, Kernl- based inference of functions graphs. CoRR, abs/ 1top//711..1l 1..1111 2017.
Dongkwan Kim and Alice Oh. How find your friendly neighborhood: Graph attention design with self-supervision. In ICLR, 2021.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLR, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In ICLR, 2019a.
Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learn- ing. In NewrIPS, 2019b.
Jure Leskovec and Andrej Krevi. Snap datasets: Stanford large network dataset collection, 2014.
Jure Leskovec, Deepayan Chakrabarti, Jon M. Kleinberg, Christos Faloutsos, and Zoubin Ghahra- mani. Kronecker graphs: An approach to modeling networks. J. Mach. Learn. Res., 11:985-1042, 2010.
Guohao Li, Matthias Müller, Ali K. Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? In ICCV, 2019.
Mingjie Li, Xiaojun Guo, Yifei Wang, Yisen Wang, and Zhouchen Lin. G2en: Graph gaussian convolution networks with concentrated graph filters. In ICML, 2022.
Derek Lim, Felix Hohne. Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser- Nam Lim. Large scale learning on non- non-homophilous graphs: New benchmarks and strong simple methods. In NeurIPS, 2021.
10

---

Under review as a conference paper at ICLR 2023
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In KDD, 2020.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang. Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In ICLR, 2020.
Benedek Rozemberczki and Rik Sarkar. Twitch gamers: A dataset for evaluating proximity preserv- ing and structural role-based node mmbeddings. arXiv preprint arXiv:2101.03091, 2021.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. J. Complex Networks, 9(2), 2021.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad. Collective classification in network data. AI Mag., 29(3)9331066 2008.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günneemann. Pitfalls of graph neural network evaluation. CoRR, htss/811.05866. 2018.
Alexander Smola and Risi Kondor. Kernels and regularization on graphs. In Bernhard Schölkopf and Manfred K. Warmuth (eds.), Computational Learning Theory and Kernel Machines, 16th Annual Conference on Computational Learning Theory and 7th Kernel Workshop, COLT/Kemel 2003, Washington, DC, USA, August 24-27, 2003, Proceedings, volume 2777 of Lecture Notes in Computer Science, pp. 144-158. Springer, 2003.
Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks, In KDD, 2009.
Amanda Traud, Peter J Mucha, and Mason A Porter. Social structure of facebook networks. Physica A: Statistical Mechanics and its Applications, 391(166:4165-4188) 2012.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lið, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Yifei Wang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin. Dissecting the diffusion process in linear graph convolutional networks. NeurIPS, 2021.
Felix Wu, Amauri H. Souza Jr., Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. Simplifying graph convolutional networks. In ICML, 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. IEEE Trans. Neural Networks Learn. Syst., 32 (1):4 24, 2021.
Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In ICML, 2016.
Rex Ying. Ruining He. Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. KDD, 2018.
Jaemin Yoo, Hyunsik Jeon, and U Kang. Belief propagation network for hard inductive semi- supervised learning. In IJCAI, 2019.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applica- tions. Al Open, 1:57-81, 2020.
Hao Zhu and Piotr Koniusz. Simple spectral graph convolution. In ICLR, 2021.
11

---

Under review as a conference paper at ICLR 2023
Table Table of symbols.
Symbol
Description
G (A
Undirected graph of n nodes and features Symmetric adjacency matrix of size x n
A
X
Node feature matrix of size n d
y
Node label vector of size m, where <<
= A + Ln
Adjacency matrix with self-loops
= diag( Alaxi
Degree matrix of
Asym D D-1/2 A 1/2
Symmetrically normalized Á
Agym D D-1/2 AD 1/2
Symmetrically normalized A (i.e., no self-loops)
Arow D-IA
Row-wisely normalized A (i.e., no self-loops) Column-wisely normalized A (i.e., no self-loops)
Acol
AD
ding(-)
Function that creates diagonal matrix from a vector Matrix of size a x 6 filled with ones Identity matrix of size a, where the subscript can be omitted
Laxb
La
LR(-)
Logistic regression function defined in Definition
W
Learnable weight matrix of size h x c in the LR function
P()
Feature propagator function defined in Definition
A
TABLE OF SYMBOLS
Table 5 summarizes the symbols frequently used in this paper. The formal problem definition and the detailed description of such symbols are presented in Section 2.
B PROOF LEMMA 1: REPRESENTING LINEAR MODELS WITH GNNLIN
We prove Lemma by representing each linear GNN with GNNLIN. Let K 2 0 be hyperparameter that determines the number of propagation steps in every GNN.
SGC (Wu et al., 2019) fits the definition of linearization with the following propagator function:
P(A.X) = A K X.
DGC (Wang et al., 2021) has variants, DGC-Euler and DGC-DK, which have different propagator functions. We focus on DGC-Euler, which used as the main model in their experiments. DGC is similar to SGC, except that it controls the strength of self-loops as follows:
X)A,X) = (1-T/K)I (T Asym) XX.
(5)
where 7' > 0 is a hyperparameter. The self-loops become stronger if 7' is closer to 0.
S²GC (Zhu & Koniusz, 2021) computes the summation of features propagated with different num- bers of steps:
K Σ aI +1 (1 sym)) XX.
P(A,X)
The original formulation divides the added features by K, which can be safely ignored considering that the weight matrix W is multiplied to the transformed feature for classification.
GC (Li et al., 2022) does not provide an explicit formulation of the propagator function, and thus derive it. First, the parameterized version P' of the propagator function given follows:
N
P'AA,x:(0111
Σ
H.H.
12

---

Under review as a conference paper at ICLR 2023
where 0 is learnable parameter. The k-th feature representation H is recursively defined as
TV H,I)
H H
L
K
Tj ((b: 1-1] Asym) H
k
K
(8)
Ti ((b; 1)I + Asym) H
I H X,
K
where N, T. and b, are hyperparameters, and L = I- Asy is the normalized Laplacian matrix. Since the transformed features are combined with learnable parameter in Equation 7, we make a propagator function P that contains no learnable parameters as follows:
N
N = || i=1
T. [((0 K
P(A,X)
H
H
T-
1)I Asym) )
(9)
1=1
C LINEARIZATION PROCESSES
We present detailed processes to linearize various graph neural networks (GNN) as in Table 1. The linearization is done in two steps. First, replace all activation functions with the identity function from the original definition of each GNN. Second, the resulting layer function contains learnable parameters, we devise a replacement that is at least as expressive the given function but containing no learnable parameters. This is because our goal of linearization is not just deriving a linear function with respect X. but understanding GNNs in relation to logistic regression based on our GNNLIN framework. We ignore the bias terms of linear layers for simplicity, without loss of generality.
Decoupled models PPNP, APPNP (Klicpera et al., 2019a), GDC (Klicpera al., 2019b), and GPR-GNN (Chien et al., 2021) are decoupled GNNs that separate feature transformation and prop- agation stages. PPNP runs Personalized PageRank on the node features, and APPNP approximates PPNP with K steps of message propagation. GDC generalizes APPNP by increasing the value of K to co and sparsifies the propagator matrix S. GPR-GNN also generalizes APPNP avoid the usage of a by learning weight for each component, resulting in the concatenation of multiple different features. We provide details of linearization in Appendix C.I.
Coupled models We linearize coupled GNNs including ChebNet (Defferrard et al., 2016), GCN (Kipf Welling, 2017), GraphSAGE (Hamilton et al., 2017), and GCNII (Chen et al., 2020). The linearized version of GCN is the same SGC, since the motivation of SGC is to linearize GCN for better scalability and robustness. Although their motivations are different, the linearized versions of ChebNet, GraphSAGE, and GCNII are similar to linearized GPR-GNN in that features propagated by different steps are combined by concatenation. We provide the details in Appendix C.2.
Attention models 2022) are a popular category of GNNs to learn the importance of each edge based on X and learnable parameters. Thus, it is not straightforward to linearize them by the GNNLIN framework: even if assume the learnable parameters in P as fixed hyperparameters, P is at least quadratic with X, since X participates in computing the new adjacency matrix that is multiplied again with X. Nevertheless, we perform incomplete lincarization of attention-based models for completeness, and represent the results with the **** symbol Table 1. Detailed processes are given in Appendix C.3.
Attention-bass GNNs (Velickovic et al., 2018; Kim & Oh, 2021; Brody al.,
The linearized version of GAT uses a different adjacency matrix for each step k., which is the main difference from other linearized models. It is noteworthy that DA-GNN (Liu et al., 2020), proposed as decoupled model in their paper, is an attention-based model in our analysis. This is because X participates computing the new adjacency matrix, making P quadratic as GAT.
C.I LINEARIZATION OF DECOUPLED GNNS
The propagation in decoupled GNNs is done the abstract representations of node features, which are typically generated by multilayer perceptrons (MLP). Linearization starts with replacing MLPs with linear projections, and removes additional nonlinearity in the process of propagation.
13

---

Under review as a conference paper at ICLR 2023
C.1.1 PPNP (KLICPERA ET AL., 2019A)
The lineraization PPNP is straightforward, since the authors present closed- form representation of the propagator function. If we remove the activation function, we have the following:
P(A,X) = (I, - a:) Aym))
(10)
where 0 < a < 1 is hyperparameter that controls the weight of self-loops.
C.1.2 APPNP (KLICPERA ET AL., 2019A)
We assume that the initial node representation is created by single linear layer of XW, where W a weight matrix. Then, the k-th representation matrix H₂ is represented as follows:
H (1 ym H axW,
(11)
where 0 < a is hyperparameter. The closed-form representation H is given as follows:
K-1
Hg ((1-a)Agym) K
Σ
I[1-aa (ll-a)Ago a)
XW.
(12)
k=
We safely remove the weight matrix W, which is redundant, and get the fiinal representation:
K Σ
P(A,X) X)
a(1-aj aa) A sym + (1 - A
A K
X
(13)
sym
k=
C.1.3 GDC (KLICPERA ET AL., 2019B)
GDC generalizes APPNP and presents various forms of the propagation function. We pick the most representative given in the paper, which is directly related to APPNP. The unnormalized version of the propagation matrix is given as follows:
='=Zo
Σ
a(1 a)* A sym
(14)
k=
and then it is normalized and sparsified as
$ = sparsify (S'y
(15)
S'ym represents adding self-loops and applying the symmetric normalization to S'. The paper gives two approaches for sparsification, which a) removing elements smaller than e, which is given as a hyperparameter, and b) selecting the top k neighbors for each node. With any choice, the function P is simply given follows:
P(A, X) SX.
(16)
C.1.4 GPR-GNN (CHIEN AL.,, 2021)
We assume that the initial node representation is created by single linear layer of XW, where W a weight matrix. Then, have the following propagator function P' with parameters:
K
Og sym X.
(17)
where 0g is a parameter that is learned together with W. We replace the summation with concate- nation to remove the learnable parameters from p' and get the following:
P(A,X)
|| k=0
A X.
(18)
14

---

Under review as a conference paper at ICLR 2023
C.2 LINEARIZATION COUPLED GNNS
C.2.1 CHEBNET (DEFFERRARD ET AL., 2016)
Let H₂ be the k-th node representation matrix, and L = I Asym be the graph Laplacian matrix normalized symmetrically. Then, the propagator function of ChebNet with parameters 0
K-1
(A, X: 0) = Σ HgH
(19)
A=
where the recurrence relation is given as follows with the intial terms:
Hn X
H: LX = -Aym X +X
(20)
H. 2( - I)H H
- Ha-1 H
Based on the recurrence relation, the closed-form representation of Hg given
g 04 A sym + ag A sym
ag
(21)
where op.- ... ag are constants. Since have K free parameters oo. 0x corresponding the K terms in the representation matrix Hx, we safely rewrite the propagator function as
K-1
P'(A.
Σ
A
X.
(22)
k=
Each value of k has free parameter 0g. Thus, we generalize it as follows:
K-1
P(A,X)
|| k=0
A X. sym
(23)
C.2.2 GRAPISAGE (HAMILTON ET AL., 2017)
We assume the mean aggregator of GraphSAGE. By replacing the activation function as the identity function, each layer F of GraphSAGE is linearized follows:
F(X) XW, ArooWXW
(24)
where Azow D A represents the mean operator in the aggregation, and W, and W, are learn- able weight matrices the layer. we apply a chain of two layers, where the weight matrices of the second layer are represented as Wa and W4, we get the following:
F(F(X)) XW, W3 + A X(W,W, + W2W3) + 2 TOW XW2W,
(25)
XW, Arow XW, A
row XW
(26)
where we redefine the weight matrices without loss of generality as
Wa = W, W,W.
(27)
W; W, We + W.W,
(28)
W_ W W.
(29)
we generalize it into K layers, we get the following:
k row
XW k-
(30)
Note that different weight matrix W, is applied to each layer k. This is equivalent to concatenating the transformed features of all layers and learning single large weight matrix in training.
15

---

Under review as a conference paper at ICLR 2023
C.2.3 GCNII (CHEN ET AL., 2020)
After replacing the activation function with the identity function, the /-th layer Ji of GCNII given as follows:
Hi (11aa) H o; BJ)I+ W)))
(31)
where and 3 are hyperparameters, and W is a weight matrix. The second term is equivalent to W; regardless of the value of 3r, since Wt a free parameter. We also set a to a constant a which the same for every layer I, following the original paper (Chen et al., 2020)." Then, the equation is simplified as
Fi = ((1 a) sym H
(32)
If we apply chain of two layers/ / and + 1, get the following:
(H))) = ((1 a Aym ((1 a A sym H+ +
axX) ax)
(33)
= =1 -=)))² A sym
HW, W 1+1 + a(1 - a sym XW,W (41 + #XXW
(34)
= (1 - -=)²A² sym
HW, - a(1 a sym XW, oXW
(35)
where W = W,W which is also a free parameter. If we generalize it into K layers, we get the following:
K-2 E1- A
F k (X)= = a) K- (1-a))) a 1-1 JXW
XW
(36)
k=
We safely remove the constant from each term, which can be included in the weight matrix:
K-2
Fk (X) ((1 (1-a) A sym sym
( K
Σ
A XW k-
(37)
sym
A=0
We replace the summation operators between terms having different weight matrices with concate- nation operators, having the final propagator function P follows:
K-2
P(A,X) = ||
A A X ((1 ax) A sym + Baak- AK-1IX
(38)
sym
k=
C.3 LINEARIZATION OF ATTENTION GNNS
C.3.1 DA-GNN (LIU ET AL., 2020)
We assume that the initial node representation is created by a single linear layer XW, where is weight matrix. Then, the k-tth representation matrix Hę is represented as follows:
H A k XW.
(39)
DA-GNN computes the weighted sum of representations for all k E [0, K]. where the weight values determined also from the representation matrices:
K diag H
P(A,X)
k=
(40)
K
diag A
XWs) Sy XW.
sym
where s is a learnable weight vector. We safely remove the last W and rewrite Ws as w. Then, we have the final representation of the propagator function:
P(A.
diag(A Xw) Ak
(41)
is 0.1 the original paper of GCNIT (Chen al., 2020).
16

---

Under review as a conference paper at ICLR 2023
C.3.2 GAT (VELICKOVIC ET AL., 2018)
We apply the following changes to linearize GAT, whose linearization is not straightforward due to the nonlinearity in the attention function:
1. We replace the activation functions between layers with the identity functions.
2. We simplify the attention function az exp(e1))/ Σx exp(ea)) as Eij-
3. We remove the LeaklyReLU function the computation of eij.
4. We assume the single-head attention.
The edge weight Eij, which is the (i. element of the propagator matrix, is defined as follows:
G = dst [W]]
x
+
arc!
x)),
(42)
where x, and xj are feature vectors of length for node and j, respectively, W a d x c learnable weight matrix, and adst and aere are learnable weight vectors of length Then, we derive the initial form of a linearized GAT layer as follows:
H [diag( X Wa A Adiag( Wa XW.
(43)
Since all adst. asre and W are free parameters, we generalize it as follows:
H [diag( X Xwast) ) Ading((w..r))XXX
(44)
where Wast and Ware learnable vectors of length that replace adst and agres respectively.
D DETAILS ON SANITY CHECKS
D.1 FORMAL. DEFINITIONS GRAPH SCENARIOS
We categorize all possible scenarios of node classification based on the characteristics of node fea- tures X, graph structure A, and node labels y. We denote by A;j and Y; the random variables for edge (i.j) between nodes i and and label y; of node i, respectively.
Edges
For the adjacency matrix A, we consider the following three cases:
Uniform: P(As, A;j = Ast 1) = P(A 1) Clustered: P(A 1 A, A₁e = P(Au= 11)
Bipartite: P(A | = A,k 1) < P(An=
The uniform case represents that every edge is determined independently of the others, and the graph structure gives no useful information for node classification. In the clustered case, it more likely that nodes having common neighbors make more connections in graph. In the bipartite case, nodes make more connections with those sharing no common neighbors.
Labels
For the labels in we consider the following three cases:
Individual: P(Y; y A, -,,,- = y) P(Y, y) Homophily: P(Y, = y A. = 1,,, =
P(Y. =y)
Heterophily: P(Y,
A. = 1,,, = P(Y v)
The individual case means that the label of node is independent of the labels of its neighbors. This is the case when the graph structure works as noise information with regard to classification. In the homophily case, adjacent nodes are likely to have the same label. is the most popular assumption of GNNs for node classification. In the heterophily case, adjacent nodes are likely to have different labels, which is not as common as homophily but often observed in real-world graphs.
Features For the feature matrix X, we consider the following three cases based on A and y. We use the notation of p(-) since the features are typically modeled as continuous variables.
Random: p(x;, Xj Wi, Mj diz)) = p(x;, Xj)
Structural: xx Vi, Mj (1j) # p(x;, X; yi. M3)
17

---

Under review as a conference paper at ICLR 2023
Semantic: p(x,, X,
M/s By: aty) * p(x,,,) ais))
The random case represents that features are determined independently of the graph and labels. In this case, node features do not give useful information for classification, but work unique indices of nodes like one-hot embeddings if the dimensionality of features is large. In the structural case, features correlated with the graph structure, but not directly with labels. Such features give useful information for classification only if the graph structure and labels are related. In the semantic case, features directly provide useful information for predicting labels. Note that features can be semantic and structural at the same time by satisfying both of the conditions.
D.2 IMPLEMENTATION OF GRAPH SCENARIOS
There are various ways to generate synthetic graphs satisfying the definitions of different scenarios. One can use a synthetic graph generator designed to create more plausible graphs (Leskovec al., 2010; Barabási & Albert, 1999), but we choose the simplest one to focus on the mutual information, rather than the other characteristics of synthetic graphs such as the degree distribution.
Structure We assume that the number of structural clusters is the same as the number e of labels for the alignment with label information. We divide all nodes into c groups and then decide the edge densities for intra- and inter-connections of groups based on the structural type: uniform, clustered, and bipartite. We use a hyperparameter ca to determine the noise level in the case of homophily or heterophily: for example, if c, = 0, the graph has full block -oock-daagonal adjacency matrix in the case of homophily. The expected number of edges is the same for all three cases, and we set ea = 0 in all of our experiments.
notable characteristic of bipartite structure A is that A has clustered structure. If we create inter-group connections for every possible pair of different groups, even noise-free A with makes noisy A with inter-group connections. For better consistency, we set the number of classes to even number in our experiments, randomly pick paired classes such (1,3) and (2, 4) when c = 4, for example, and create inter inter-group group connections only for the chosen pairs. In this way, we create non-diagonal block- flock--ermutation matrix A when ea = 0. and the noise level of A which has a clustered structure, is solely controlled by the noise level of A.
0
Labels In the case of individual y, we determine the label of each node uniformly random, with no consideration of the graph structure. In the case of homophily or heterophily y, we assign labels based on the groups of nodes assumed by the graph structure. That is, nodes in the same group have the same label, and thus the group index itself works as the label y. In this way, we force homophily y for clustered A, and heterophily y for bipartite A. The degree of homophily (or heterophily) is also determined by the noise level Eg of the graph structure.
Features We basically assume that every feature element is sampled from a uniform distribution. Thus, in the random case, we sample each element from the uniform distribution Z/(0. 1) between 0 and 1. In the structural case, we run low-rank support vector decomposition (SVD) (Halko al., 2011) to make X have structural information. Given UTVT T ~ A from low-rank SVD, we take U and normalize each feature element to have the zero-mean and unit-variance. The rank r in the SVD is determined as a hyperparameter; higher captures the structure better, but can give noisy information. We also apply the ReLU function to U to make them positive.
In the semantic case, randomly pick e representative vectors {v* from the uniform distri- bution, which correspond to the e different classes. Then, for each node i with label y, we sample a feature vector such that arg max, Vı y. In this way, we have random vectors having sufficient semantic information for the classification of labels, with a guarantee that the perfect linear decision boundaries can be drawn in the feature space X at the training time.
E REPRODUCIBILIIT
E. DATASETS
We use 7 homophily and 6 heterophily datasets in experiments. which were used widely in previous works on node classification (Chien et al., 2021; Pei et al., 2020). Cora, CiteSeer, and PubMed (Sen et al., 2008; Yang et al., 2016) are homophily citation graphs between research articles. Computers
18

---

Under review as a conference paper at ICLR 2023
Table 6: The statisties of datasets used in our experiments. The first seven datasets are homophily graphs, while the last six are heterophily graphs.
Cora
CiteSeer
PubMed
Computers
Photo
ugba-arXh
agho-Prodocts
Chumeleon
Squircet
Actor
Pennt4
Twitch
Pokec
Nodee
2.4M
5.3
168K
Edga
53K
40K
4.3K
61.9M
3144
1988
6.8
306M
Features
1438
370
767
128
2089
981
Claeass
39
Table 7: Search spaces of hyperparameters.
Method
Hyperparameters
LR
wd- [0, 5e -]
SGC
wd 10,5e
K
DGC
wd = [0, 5c
K = 200, = 6
SCG
wd [0, 5.
K 16, = [0.01, 0.0.0.0.0.00500000, 0.09
GCCN
wd- = [0, 5e
2, *J. K - =
(10, 40), = 0,
GCN
wd = 10, 5e
Ir [2 0...1.0.05) K =
SAGE
wd = 00 5e
[2 3.0.01,0.05 =2
GCNII
wd = 00, 5E
[r
K 16, 64]. [0.1,0.2.0.5]
[0.5, 1, 1.5]
APPNP
wd = 0, 5E
-4
[r
[2 3.001, K = 10, =.1
GPR-GNN
wd 0, 5e
[r 2c 0.01, K 10, (0.1.0.2,0.5, 0.9
GAT
wd =
[0, 5e -4
lr 2e 0.01,
K = 2, heads =8 8
GNNnderGNN
wd1 [1
le le
1.
wd2
[1e
le 4 le le
and Photo (Shehur et al., 2018) are homophily Amazon co-purchase graphs between items. ogbn- Xrxiv and agbn-Products are large homophily graphs from Open Graph Benchmark (Hu et al., 2020). Since we use only 2.5% of labels as training data, we omit the classes with instances fewer than 100. Chameleon and Squirrel (aareeelooeeeeeeeeeeee (Rozemberczki et al., 2021) are heterophily Wikipedia graphs. Actor (Tang et al., 2009) is a heterophily graph connected by co-occurrence of actors on Wikipedia pages. Penn94 (Traud et al., 2012; Lim et al., 2021) is heterophily graph of gender relations in social network. Twitch (Rozemberczki & Sarkar, 2021) and Pokec (Leskovec & Krevl, 2014) are large graphs, which have been relabeled by (Lim et al., 2021) to be heterophily. We make the heterophily graphs undirected as done in (Chien et al., 2021). The statistics of datasets are reported Table
E.2 COMPETITORS
The propagator functions of graph kernel methods (Smola & Kondor, 2003) are given follows:
(Reg. Kernel) P(A, X) = (I, + -
(45)
(Diff. Kernel) P(A, = exp(-o2/2L_x
(46)
(RW Kernel) P(A,X) (aI, LL,X
(47)
where L D 1D2 A)D-A 1/2 is the normalized Laplacian matrix, and σ = 1, a= 1, and 2 are hyperparameters. We use reasonable default values introduced in the paper.
the node features of all datasets as done in most studies on GNNs. We report the hyperparameters used for a grid search Table 7, which is done every split of data. The dimensions of hidden layers are all set to 64, and the probabilities of dropout layers are all set to 0.5. For the linear models, we use L-BFGS as the optimizer for training 100 epochs with patience ADAM and train them for 1000 epochs with patience 200.
We perform row-normalization
5; for the nonlinear ones,
SlenderGNN contains only 2 hyperparameters, where wdy is the weight LASSO, and wdz is the weight of group LASSO. It is worth noting that, when searching the hyperparameters, SlenderGNN does not need to recompute the features, while most of the linear methods need to do so because of including one more hyperparameters in the features that can be precomputed otherwise.
19

---

Under review as a conference paper at ICLR 2023
Table Ablation Study 2-step aggregation is good enough: the first three places are statistically marks the top three (higher is darker).
tied. Green
Aow
Caro
Cheebeer
PuhMid
Camp-
Photo
Products
Clom.
Sgaiml
Actor
Pres94
Pikee
79.230.8
67 67.2:0.1
29.111
30-207
67,5205
10000.11
74.6:01
79.210.7
667884
64 0:043
852210.3
$4.7113
163163
292315
11200
07.710.1
903:00
142-02
3.
76.99.9
669822
M63667
07
75.9335
318407
7600001
2.4.0
2.3.4
79:683:1
66.244
$444:04
45.9250.3
91.320.
669952
$4.832.1
410013
3143308
29::06
05.25005
00.7:0011
766:022
Table 9: Ablation Study SlenderGNN is minimalistic: all its components needed achieve good accuracy in real-world graphs. The first two places are highlighted.
PubMed
Comp.
Squirrel
Prurf4
Twiich
77
05,03355
$58220.5
85.9203
91.7207
65.2302
83.4:19
40.123
30.4110
30.120.6
67.206
5988:0.1
74.2::..0
PCA
7.8
06.033.1
$47.005
81.4111
90,320.7
003:0022
$45500
41.320
3188111
27.341.1
67.72007
59.120.2
72.8:0.11
761
67,4335
8.0-0.
92.11044
66.1:9.3
925-006
375542
29.4.0
M1319.5
058:00
56.40000
728840.1
GRN
7788:11
67.1233
$46:0.5
86.3:07
66.3:0.3
$49:00
408:32
311220
30.91966
68.230
59.728.1
73.928.1
F ABLATION STUDIES
Nonlinearity Adding nonlinearity does not necessarily improve the accuracy, since the increased difficulty of training and hyperparameter tuning makes the model less generalizable. To demonstrate this, we design three nonlinear variants of SlenderGNN:
R-f1, y1, v2, D2
w/ MLP-2: We replace LR with 2-layer MLP.
w/ MLP-3: We replace LR with 3-layer MLP.
w/ NL Trans.: We replace the PCA function g(-) with a nonlinear function. Specifically, we adopt 2-layer MIP for the first two components, and a 2-layer GCN for the last two. The transformed features are concatenated and input into another 2-layer MLP.
We use dropout with a probability 0.5 to prevent overfitting in both MLP and GCN. The nonlinear models are trained with the same setting as GCN reported in Table 7. We report the result in Table 4, showing that adding nonlinearity does not necessarily improve the accuracy, while sacrificing both scalability and interpretability. We choose use linear function based on this result.
Receptive Fields To test the effect of changing the receptive field of our SlenderGNN, we vary the
R-VI
distance of aggregation as in Table krow denotes the number of steps for Arow, while ksym denotes the number of steps for Asym- Since Arow is designed to consider heterophily relations, we use only the even values of know- Table shows that the first three places each dataset are statistically tied in most of the cases. In other words, we have no significant gain by increasing the values of krow and ksym- and thus the 2-step aggregation for both Arow and Asym is good enough. To keep our model synthetic and real data.
simple and general, use know 2 and ksym 2 in all experiments
We evaluate the accuracy of SlenderGNN when each of its core modules is disabled: the sparse regularization, PCA, and structural features U. SlenderGNN performs well with all these ideas in all 13 datasets, i.e., it is always included in the top two at each dataset. This shows that our SlenderGNN is designed effectively with ideas that help improve its performance.
Components
20


Reviews:
[{"review_id": "xHSBSnuovl", "reviewer": "Reviewer_f9sS", "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 main objectives of this paper are two-fold. \nFirst, the authors introduced a linearization framework for transforming various GNNs into a linearized form. Removing non-linearities should improve interpretability.\nSecond, the authors applied what they have learned about different GNNs (pain points and factors that distinguish different GNN variants) in designing of their own GNN-variant which is optimized for interpretability, robust to various labeling scenarios in graphs and has fewer parameters.\nThe authors presented their results together with sanity checks where they identified three groups of graph scenarios composed of combination of Edge types, Labels types and Feature types.\n ", "summary_of_the_review": "Overall, I found this paper to be well-written and well-motivated. I believe this paper addresses an important problem and provides an innovating solution.", "strength_and_weaknesses": "This paper follows a strict logical path. The authors first describe their linearization framework. They proceed to describe lessons learned when applying linearization to previous GNN variants. The chief problem they listed have to do with the lack of explainability of GNN models with many layers. \nI was particularly impressed with the sanity checks proposed in this paper for evaluating robustness of the proposed method and for comparing it with previous methods.\n", "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": "i2BH8uyPKcw", "reviewer": "Reviewer_y6fQ", "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": "", "summary_of_the_paper": "Authors propose the framework that tackles crucial aspects of modeling, which include accuracy, robustness, slenderness, and interpretability. To tackle this, authors propose the generic framework, named GNNLIN, that consists of the propagation layer and the logistic regression layer. Through the generically structured propagation layer, the proposed method can provide the interpretability. Furthermore, authors propose the sanity checking framework that verifies whether a given model algorithms works broadly for various scenarios of graphs and features. Finally, authors use the proposed sanity checks and real-world datasets to show the proposed algorithm outperforming the baseline methods.", "summary_of_the_review": "The proposed framework is very intuitive and passes the sanity checking framework as well as outperforms the baseline methods. However, the model is essentially the logistic regression model using graph and node features, which are already being used commonly by industry. The novelty of the proposed model is limited in that sense.", "strength_and_weaknesses": "* Strengths\n- A simple but generic interpretable model is proposed.\n- The proposed model achieves many aspects all together.\n- Sanity check framework is proposed and it would be great for other researchers to analyze their own models.\n\n* Weaknesses\n- The non-linear component is cleared for simplicity, but it is not clear whether the activation is not necessary or it can play a role to improve the performance more.\n- In particular, the proposed method is just a logistic regression model that uses neighbor information, connectivity information, and node attributes as features. Eventually, the proposed model solves the iid logistic regression regardless of any latent space. Apparently, the proposed model does not seem to be a GNN. Authors need to modify the definition or the explanation of modeling, or regard the proposed model as the linear model using graph features. Robustness and interpretability can be achieved typically through such simple models.\n- Many GNN models rely on sampling methods, while the proposed method is based on more matrix operation. It would be great if the proposed method can work with some sampled data or scale enough.\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "39wpUkNnb0t", "reviewer": "Reviewer_VYo8", "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": "This paper reviews the desiderata of GNN and proposes SlenderGNN, a simple linear GNN, to meet the needs. The proposed SlenderGNN comes from the linearization framework, which can resemble various GNN designs. Towards these desiderata, the authors present several sanity check, and the proposed SlenderGNN pass all of them. Moreover, SlenderGNN shows superiority over various GNNs on several real-world node-classification tasks.", "summary_of_the_review": "I appreciate the discussion of what an ideal GNN is supposed to do, which makes the design of SlenderGNN well-motivated. Although the discussed linearization is somewhat straightforward, it well resembles various kinds of GNNs. I think it is helpful for the community to view existing GNNs from such a perspective. However, I have concerns about the novelty of SlenderGNN, which seems to be a trivial linearization. The consistent advantages achieved by SlenderGNN makes me eventually give a relatively positive score.", "strength_and_weaknesses": "Strength:\n1. This paper is well written, where all the definitions, declarations, and tables are self-contained.\n2. The discussion of linearizing GNN is comprehensive and valuable for the community, which unifies many SOTA GNN works.\n3. The performance of SlenderGNN is amazing, especially considering that outperforming those SOTA GNNs on such a variety of node classification tasks is very difficulty in nowadays.\n\nWeaknesses:\n1. The SlenderGNN is not a sophisticated instance among the linearization framework, that is to say, it has obvious limitations such as a restricted receptive field. In another word, it is not that novel to me.\n2. As a linear GNN, the transformation $P$ could be interpreted from the perspective of feature engineering. Thus, it might be necessary to include several works in that line as baselines (e.g., graph kernel methods) in the experiments.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "0pZKkCZlMT", "reviewer": "Reviewer_DLLT", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 paper proposes SlenderGNN, a new GNN method that is accurate, robust, and interpretable. Authors report experimental results comparing SlenderGNN's performance with a set of alternative methods. They also conduct an ablated study to assess the importance of individual modules of the proposed method in its performance.", "summary_of_the_review": "The paper addresses an important question/concern with GNNs, however there are major limitations in connecting the experimental results with the paper's claims. Also theoretical grounds of the paper are not very clear.", "strength_and_weaknesses": "Strength\n- The paper addresses an important topic (i.e. interpretability and robustness of GNN).\n\nWeaknesses\n- Scattered and not well supported claims. The contributions from GNNLin and SlenderGNN are mixed in the paper and empirical results only provide partial evidence about the claims. Maybe it would have been more beneficial if authors had fully focused on SlenderGNN rather than including SlenderGNN related materials as well.\n- Experimental results are not clearly discussed and it is not clear why LR shows comparable to superior results in most data sets vs. more state of the art and GNN-based approaches.\n- Also refer to reviewer's comment on clarity, quality, and novelty in the box below.", "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": {}}]

Author rebuttal:

Decision: Reject