Node Dependent Local Smoothing for Scalable Graph Learning
Authors: Wentao Zhang
Mingyu Yang
Zeang Sheng
Yang Li
Wen Ouyang
Yangyu Tao
Zhi Yang
Bin CUI
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Graph Neural Network
Scalability
Smoothness

Abstract: Recent works reveal that feature or label smoothing lies at the core of Graph Neural Networks (GNNs). Concretely, they show feature smoothing combined with simple linear regression achieves comparable performance with the carefully designed GNNs, and a simple MLP model with label smoothing of its prediction can outperform the vanilla GCN. Though an interesting finding, smoothing has not been well understood, especially regarding how to control the extent of smoothness. Intuitively, too small or too large smoothing iterations may cause under-smoothing or over-smoothing and can lead to sub-optimal performance. Moreover, the extent of smoothness is node-specific, depending on its degree and local structure. To this end, we propose a novel algorithm called node-dependent local smoothing (NDLS), which aims to control the smoothness of every node by setting a node-specific smoothing iteration. Specifically, NDLS computes influence scores based on the adjacency matrix and selects the iteration number by setting a threshold on the scores. Once selected, the iteration number can be applied to both feature smoothing and label smoothing. Experimental results demonstrate that NDLS enjoys high accuracy -- state-of-the-art performance on node classifications tasks, flexibility -- can be incorporated with any models, scalability and efficiency -- can support large scale graphs with fast training.

Node Dependent Local Smoothing for Scalable Graph Learning
Wentao Zhang', Mingyu Yang', Zeang Sheng', Yang Li Wen Ouyang", Yangyu Tao", Zhi Yang' Bin Cui
School of CS, Peking University Teeneett Inc. Key Lab of High Confidence Software Technologies, Peking University Institute of Computational Social Science, Peking University (Qingdao), China wentao. weentao.zhang, ymyu, shengzeang 18, liyang.cs, yangzhi, bin.cui @ pku.edu.cn fgdpouyang, brucetao @ @teencnt.com
Abstract
Recent works reveal that feature label smoothing lies the of Graph Neural Networks (GNNs). Concretely, they show feature smoothing combined with simple linear regression achieves comparable performance with the carefully designed GNNs, and simple MIP model with label smoothing of its prediction can outperform the vanilla GCN. Though interesting finding, smoothing has not been well understood, especially regarding how to control the extent of smoothness. Intuitively, small or over- mner-smoo and can lead to sub-optimal performance. Moreover, the extent smoothness is node-spectie ssee-spe,,,,,, depending on degree and local structure. To this end, we propose novel algorithm called node-dependent local smoothing (NDLS), which aims control the smoothness of every node by setting a node- specific smoothing iteration. Specifically, NDLS computes influence scores based on the adjacency matrix and selects the iteration number by setting a threshold the scores. Once selected, the iteration number can be applied to both feature smoothing and label smoothing. Experimental results demonstrate that NDLS enjoys high accuracy state-of-the-art performance node classifications tasks, flexibility - can be incorporated with any models, scalability and efficiency can support large scale graphs with fast training.
large smoothing iterations may cause under-smoothing
Introduction
In recent years, Graph Neural Networks (GNNs) have received surge of interest with the state-of-the. art performance on many graph- based tasks (2] 36 9 34 28 29). Recent works have found that the success of GNNs can be mainly attributed to smoothing, either at feature or label level. For example, input to simple linear regression model achieves
SGC 27 shows using smoothed features comparable performance with lots of carefully designed and complex GNNs. At the smoothing stage, features of neighbor nodes are aggregated and combined with the current node's feature to form smoothed features. This process is often iterated multiple times. The smoothing is based on the assumption that labels of nodes that are close to each other highly correlated, therefore, the features of nodes nearby should help predict the current node's label.
One crucial and interesting parameter of neighborhood feature aggregation the number of smoothing iterations kt which controls how much information is being gathered. Intuitively, aggregation process of iterations (or layers) enables node to leverage information from nodes that are k-hop away 22 33 The choice of k is closely related to the structural properties of graphs and has
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

1.0
CDF
0.5
Cora
Citeseer
PubMed
10
30
50
70
80
Local Smoothing Iteration
(a) Two nodes with different local structures
(b) The CDF of LSI in different graphs
Figure 1: (Left) The node in dense region has larger smoothed area within two iterations of propagation. (Right) The CDF of LSI in three citation networks.
significant impact on the model performance. However, most existing GNNs only consider the fixed-length propagation paradigm uniform k for all the nodes. This is problematic since the number of iterations should be node dependent based on its degree and local structures. For example, shown in Figure (a) the two nodes have rather different local structures, with the left red one resides the center dense cluster and the right red one on the periphery with few connections. rather different for the two nodes. Ideally, poorly connected nodes (c.g., the red node on the right) needs large iteration numbers to efficiently gather information from other nodes while well-connected nodes (e.g., the red node the left) should keep the iteration number small to avoid over-smoothing. Though some learning-based approaches have proposed adaptively aggregate information for each node through gate/attention mechanism or reinforcement learning [25] 17 35 23), the performance gains are at the cost of increased training complexity, hence suitable for scalable graph learning.
The number of iterations to reach optimal level of smoothness
In this paper, propose simple yet effective solution this problem. Our approach, called node-dependent local smoothing (NDLS), calculates a node-specific iteration number for each node, referred to local smooth iteration (LSII). Once the LSI for specific node is computed, the corresponding local smoothing algorithm only aggregates the information from the nodes within a distance less than its LSI the new feature. The LSI is selected based on influence scores, which measure how other nodes influence the current node. NDLS sets the LSI for a specific node to be the minimum number of iterations that the influence score e-away from the over-smoothing score, defined as the influence score at infinite iteration. The insight is that each node's influence score should be at reasonable level. Since the nodes with different local structures have different "smoothing speed", " we expect the iteration number to be adaptive. Figure [(b) illustraes Cumulative Distribution Function (CDF) for the LSI of individual nodes real-world graphs. The heterogeneous and long-tail property exists in all the datasets, which resembles the characteristics of the degree distribution of nodes in real graphs.
Based NDLS, we propose new graph learning algorithm with three stages: (1) feature smoothing with NDLS (NDLS-F); (2) model training with smoothed features; (3) label smoothing with NDLS (NDLS-L). Note that in our framework, the graph structure information is only used in pre-processing and post- prott-proesssing steps, i.e., stages (1) and (3) (See Figure 2). Our NDLS turns a graph learning problem into vanilla machine learning problem with independent samples. This simplicity enables us to train models on larger-scale graphs. Moreover, our NDLS kernel can act as drop-in replacement for any other graph kernels and be combined with existing models such as Multilayer Perceptron (MLP), SGC [27]. SIGN (24). S²GC (37] and GBP [5].
Extensive evaluations on seven benchmark datasets, including large-scale datasets like ogbn- 100ers100M [13), demonstrates that NDLS achieves not only the state-of-the-art node classification performance but also high training scalability and efficiency. Especially, NDLS outperforms APPNP (55 and GAT (26] by margin of 1.0%-1.9% and 0.9%-2.4% in terms of test accuracy, while achieving up to 39x and 186x training speedups, respectively.
Preliminaries
In this section, we first introduce the semi-supervised node classification task and review the prior models, based on which we derive our method in Section 3. Consider graph G (V, E) with [V]

---

nodes and |g| = m edges, the adjacency matrix (including self loops) is denoted as A E R and the feature matrix is denoted as X = { Z2..., Fr) in which a;; E R/ represents the feature vector of node v, Besides, Y {y y2.... y1 is the initial label matrix consisting of one-hot label indicator vectors. The goal is to predict the labels for nodes in the unlabeled set Vu with the supervision of labeled set Vi.
GCN smooths the representation of each node via aggregating its own representations and the ones of its neighbors'. This process can be defined as
x
(Ax (AX()))))
= D
where Å is the normalized adjacency matrix, r [0, 1] is the convolution coefficient, and D is the diagonal node degree matrix with self loops. Here ( and X (k++) are the smoothed node features of layer ht and k + 1 respectively while ( is set to X, the original feature matrix. In addition, W(k) is layer-specific trainable weight matrix at layer k, and 8(-) is the activation function. By setting 0.5, 1 and 0, the convolution matrix D AD -T represents the symmetric normalization adjacency matrix D 1/2 Ā 1/2 (16), the transition probability matrix AD-1 [32], and the reverse transition probability matrix D-IÅ
30
respectively.
SGC. For each GCN layer defined in Eq. [ if the non-linear activation function ō(-) is an identity function and (k) is an identity matrix, we get the smoothed feature after k-iterations propagation as ( A Recent studies have observed that GNNs primarily derive their benefits from performing feature smoothing over graph neighborhoods rather than learning non-linear hierarchies of features as implied by the analogy to CNNs 21 12 By hypothesizing that the non- non-linear transformations between GCN layers are not critical, SGC (77 first extracts the smoothed features
(k) then feeds them to a linear model, leading to higher scalability and efficiency. Following the design principle of SGC, piles of works have been proposed further improve the performance of SGC while maintaining high scalability and efficiency, such as SIGN 24.. S2GC [37 and GBP (5].
Over-Smoothing 18] issue. By continually smoothing the node feature with infinite number of propagation in SGC, the final smoothed feature ((=) is
A (dg (y +1)
2m + n
where A 0o the final smoothed adjacency matrix, A is the weight between nodes v; and vy. d and dy are the node degrees for 2; and u/y respectively. Eq. (2) shows that as we smooth the node feature with an infinite number of propagations in SGC, the final feature is over-smoothed and unable to capture the full graph structure information since it only relates with the node degrees of target nodes and source nodes. For example, if we set r = 1, all nodes will have the same smoothed features because only the degrees of the source or target nodes have been considered.
Local Smoothing Iteration (LSI)
The features after k iterations of smoothing is (k) A*x. Inspired by (30], we measure the influence of node uy on node i by measuring how much change in the input feature of uj affects the representation of v; after A iterations. For any node u, the influence vector captures the influences of all other nodes. Considering the hh feature of X, we define an influence matrix I, (k):
[n(k) = ax (A)
(3)
OX
(0)
jh
1(K) A
(4)
Since In)k) is independent to h, we replace (k) with I [kk), which can be further represented
as I [kk (k), wh. E 21,2,.. .., f), where f indicates the number of features of X. We denote
I [(k), as the th row of [kk) and I as I (oo). Given the normalized adjacency matrix A, we can
3

---

have [(k) = A and i A According to Eq. 2 I converges to unique stationary matrix independent of the distance between nodes, resulting that the aggregated features of nodes are merely relative with their degrees (i.e., over-smoothing).
We denote [(k); as the jM row of I(k), and it means the influence from the other nodes to the node U; after iterations of propagation. We introduce new concept local smoothing iteration (parameterized by E), which measures the minimal number of iterations k required for the influence of other nodes on node v; to be within an e-distance to the over-smoothing stationarity 4. Definition 3.1. Local-Smoothing Iteration (LSI. parameterized by e) is defined
kii, c) = min 117, r(k))ll2 < c),
(5)
where || is two-norm, and is arbitrary small constant with 0.
Here is a graph-specife parameter, and a smaller indicates a stronger smoothing effect. The e-distance to the over-smoothing stationarity I ensures that the smooth effect on node is sufficient and bounded to avoid wer-smoothing. As shown Figure [[b]] we can have that the distribution of LSI owns the heterogeneows and long-tail property. where large percentage of nodes have much stationarity is heterogeneous across nodes. Now we discuss the connection between I.SI and node local structure, showcasing nodes the sparse region (e.g., both the degrees of itself and its neighborhood are low) can greatly prolong the iteration to approach mmoo-shgg stationarity. This heterogeneity property is not fully utilized in the design current GNNs, leaving the model design in a dilemma between unnecessary iterations for majority of nodes and insufficient iterations for the rest of nodes. Hence, by adaptively choosing the iteration based on LSI for different nodes, we can significantly improve model performance.
smaller L.ST than the rest. Therefore, the required I.SI to approach
Theoretical Properties of LSI. We now analyze the factors determining the LSI of a specific node. To facilitate the analysis, we set the coefficient = 0 for the normalized adjacency matrix Å in Eq. (T. thus À D The proofs of following theorems can be found in Appendix A.1.
Theorem 3.1. Given feature smoothing ( = -A with Å = D-1 A, we have
d, 2m +
K(i,e) S loga,
cV
(6)
where X2 is the second largest eigenvalue of A, d, denotes the degree of node vs plus I (i.e., d, di + 1), and m, denote the number of edges and nodes respectively.
Note that X2 < 1. Theorem 3.1 shows that the upper- upper-bound of the LSI is positively correlated with the scale of the graph (m, n),, the sparsity of the graph (small x2 means strong connection and low sparsity, and vice versa), and negatively correlated with the degree of node v;.
Theorem 3.2. For any nodes in a graph G.
K(i, c) S max (K(,C),J E()) +1, where N(1 is the set of node v; 's neighbours.
Theorem 3.2 indicates that the difference between two neighboring nodes' LSII is no more than 1, therefore the nodes with super-node neighbors (or neighbor's neighbors) may have small LSIs. That to say, the sparsity of the local area, where node locates, also affects its LSI positively. have union upper-bound of K K(i,e) as
Considering Theorems 3.1 and 3.2 together,
d,
K(i,e) S min max (K(j))),EENE + 1, 1, [e/ 2m +
(8)
NDLS Pipeline
The basic idea of NDL.S to utilize the L.ST heterogeneity to perform node-dependent aggregation over neighborhood within distance less than the specific LSI for each node. Further, propose

---

Smooth Feature with NDLS-f (rephaceable)
Smooth Label with NDLS-L
F
Adjacent preprceassing
labal
Adjscett Mebric
Final Prediction
Stage training
Stace postbrocessing
Derails NDLS-F
It's feature smoothed under optina stops
LSI Extimation
LSIJA]
LSHII=
Figure 2: Overview of the proposed NDLS method, including (1) feature smoothing with NDLS (NDLS-F), (2) model training with smoothed features, and (3) label smoothing with NDLS (NDLS-L). NDLS-F and NDLS-L correspond to pre-processing and post-processing steps respectively.
simple pipeline with three main parts (See Figure 2): (1) a node-dependent local smoothing of the feature (NDLS-F) over the graph, (2) a base prediction result with the smoothed feature, (3) a node-dependent local smoothing of the label predictions (NDLS-L) over the graph. Note this pipeline is not trained in an end-to-end way, the stages (1) and (3) in NDLS are only the pre-procsssing and post-processing steps, respectively. Furthermore, the graph structure is only used in the pre/post- processing NDLS steps, not for the base predictions. Compared with prior GNN models, this key design enables higher scalability and faster training process.
Based the graph structure, first compute the node-dependent local smoothing iteration that maintains a proper distance to the over-smoothing stationarity. Then the corresponding local smoothing kernel only aggregates the information (feature prediction) for each node from the nodes within a distance less than its LSI value. The combination of NDLS-F and NDLS-L takes advantage of both label smoothing (which tends perform fairly well its own without node features) and the node feature smoothing. We will see that combining these complementary signals yields state-of-the, art predictive accuracy. Moreover, our NDLS-F kernel can act as drop-in replacement for graph kernels in other scalable GNNs such as SGC, SCG GBP, etc.
4.1 Smooth Features with NDLS-F
Once the node-dependent LSI (ii, e) for a specific node obtained, we smooth the initial input feature X; of node i with node-dependent LSI as:
K(i.e)
(x(c)= K(i,c)+1
Σ x (8)
To capture sufficient neighborhood information, for each node u, average its multi-scale features (x(1) & < (i, })} obtained by aggregating information within hops from the node 84
The matrix form of the above equation can be formulated
max K(t.c)
KG.+T i=j and K ((i,c)
X(c)
(x
M is
(10)
0,
otherwise
where ((k) is a set of diagonal matrix.
4.2 Simple Base Prediction
With the smoothed feature according to Eq. 9 we then train a model to minimize the loss
Ever, E yo (X.)). where X, denotes the ith row X, is the cross-entropy loss function, and f(X.) is the predictive label distribution for node G. In NDLS, the default f is MLP model and
5

---

Y - is its soft label predicted (softmax output). Note that, many other models such as Random Forest 20 and XGBoost 66] could also be used in NDLS (See more results in Appendix A.2).
4.3 Smooth Labels with NDLS-L
Similar to the feature propagation, we can also propagate the soft label Y with Y = A²Y. Considering the influence matrix of softmax label (k).
OY (k)
(n(
(11)
(0) jh
According to the definition above we have that
(k)(k) In, vh E (1.
(12)
Therefore, local smoothing can be further applied address over-smoothing in label propagation. Concretely, we smooth an initial soft label Y, of node o; with NDLS follows
K(i.c)
Y,(0) K(i,c)+1 Σ
(13)
Similarly, the matrix form of the above equation can be formulated as
max K(tte)
(e)
Σ
( (A))
(14)
k=
where ((k) follows the definition Eq. (10).
5 Comparison with Existing Methods
Decoupled GNNs. The aggregation and transformation operations in coupled GNNs (i.e., GCN 15) GAT (26] and JK-Net (00) are inherently intertwined in Eq. ( so the propagation iterations L always equals to the transformation iterations K. Recently, some decoupled GNNs (e.g., PPNP [16. PPRGo M. APPNP [16), AP-GCN (25) and DAGNN (2I) argue the entanglement of these two operations limits the propagation depth and representation ability of GNNs, so they first do the transformation and then smooth and propagate the predictive soft label with higher depth in an end-to-end manner. Especially, AP-GCN and DAGNN both use learning mechanism learn propagation adaptively. Unfortunately, all these coupled and decoupled GNNs are hard to scale to large graphs scalability issue since they need repeatedly perform an expensive recursive neighborhood expansion in multiple propagations of the features soft label predicted. NDLS addresses this issue by dividing the training process into multiple stages.
Sampling-based GNNs. An intuitive method tackle the recursive neighborhood expansion problem is sampling. As a node-wise wise sampling method, GraphS AGE [11] samples the target nodes mini- batch and samples a fixed size set of neighbors for computing. VR-GCN 4 analyzes the variance reduction on node-wist sampling, and it can reduce the size of samples with an additional memory cost. the layer level, Fast-GCN (3) samples fixed number of nodes each layer, and ASGCN [4 proposes the adaptive layer-wise sampling with better variance control. For the graph-wise sampling, Cluster-GCN 7 clusters the nodes and only samples the nodes in the clusters, and GraphSAINT [32 directly samples a subgraph for mini-batch training. We don't use sampling in NDLS since the sampling quality highly influences the classification performance.
Linear Models. Following SGC [27] some recent methods remove the non-linearity between each layer in the forward propagation. SIGN 24 allows using different local graph operators and proposes to concatenate the different iterations propagated features. SC [37] proposes the simple spectral graph convolution to average the propagated features in different iterations. In addition, GBP [ further improves the combination process by weighted averaging, and all nodes in the same layer share the same weight. In this way, GBP considers the smoothness in layer perspective way. Similar

---

Table 1: Algorithm analysis for existing scalable GNNs. m, and ff are the number of nodes,
edges, classes, and feature dimensions, respectively. b is the batch size, and refers to the number of sampled nodes. L corresponds to the number of times aggregate features, K is the number of layers in MLP classifiers. For the coupled GNNs, we always have K = L.
Type
Method
Preprocessing and postprocessing
Training olk"
Inference
Memory
Node sampling
AGE
O(k'nF))
Olak" + LF)
Layer-wise sampling
PasIGUN
O[kZm)")
Otklaf")
O 1.99
Gruph-wise sampling
OCN
[lm]
OLLmf Laf"1
OiLmm + Laf")
Di6LT L("
SGC
Olaf")
Ohay-)
O1bT 19)
Linear model
S-GC
Limf))
Olnf*)
Oinfa)
Olbs
SIGN
Ol
O(Knf*)
O(Kny")
O(bLJ KP)
GMP
([Tn + T.2mpan)
O(Kuf")
O(KyF))
Oth OK
Lincar model
NDLS
O[Lon] Lime]
O(Kuf")
O(Kny")
Table 2: Overview of datasets and task types (T/I (T/I represents Transductive/IIductiie
Datuset
#Nudes
#Features
NEdges
#Clusses
VTrain/VallTest
Type
Description
Cora
2,708
1,433
5,429
140500/1 ,0000
T
citation network
Citeseer
3,327
3,703
4,732
12W500/1
citation network.
Pubmed
19,717
500
44,338
60/500/1 ,000
citation network
Industry
1,000,000
1,434,3822
5K/10K/30K
shott-form video netwerk
1gb0-papess100M
111,059.956
128
1,615,685887 .82
172
1.207K/125K221
citation network
Flickr
89,250
899,756
44K/22K/22K
image network social network
Reddit
232,965
602
11,006,919
41
LS5K/22K/54K
to these works, we also use a linear model for higher training scalability. The difference lies in that we consider the smoothness from node-dependee perspective and each node in NDLS has personalized aggregation iteration with the proposed local smoothing mechanism.
the asymptotic complexity of NDLS with several representative and scalable GNNs. In the stage of the preprocessing, the time cost of clustering in Cluster- is O(m) and the time complexity of most linear models is {(Lmf). Besides, NDLS has an extra time cost (Lme) for the postprocessing in label smoothing. GBP conducts this process approximately with bound of ( + I, m. ) where & a error threshold. Compared with the sampling- GNNs, the linear models usually have smaller training and inference complexity, i.c., higher efficiency. Memory complexity is a crucial factor in large-scale graph learning because it is difficult for memory-intensive algorithms such as GCN and GAT to train large graphs single machine. Compared with SIGN, both GBP and NDLS do not need to store smoothed features in different iterations, and the feature storage complexity can be reduced from ObLLf) to O(bf).
6 Experiments
In this section, we verify the effectiveness of NDLS on seven real-world graph datasets. We aim to answer the following four questions. Q1: Compared with current SOTA GNNs, can NDLS achieve higher predictive accuracy and why? Q2: Are NDLS-F and NDL.S-L better than the current feature and label smoothing mechanisms (c.g.. the weighted feature smoothing in GBP and the adaptive label smoothing in DAGNN)? Q3: Can NDLS obtain higher efficiency over the considered GNN models? Q4: How does NDLS perform on sparse graphs (i.e., low label/edge rate, missing features)?
6.1 Experimental Setup
Datasets. We conduct the experiments on (1) six publicly partitioned datasets, including four citation networks (Citescer, Cora, PubMed, and ogbn-papers 100M) in [15] [3] and two social networks (Flickr and Reddit) in [32) and (2) one short-form video recommendation graph (Industry) from our industrial cooperative enterprise. The dataset statistics are shown in Table 2 and more details about these datasets can be found Appendix A.3.
Baselines. In the transductive setting, we compare our method with (1) the coupled GNNs: GCN (15), GAT (26] and JK-Net [30]: (2) the decoupled GNNs: APPNP [16), AP-GCN (25).
7

---

Table 3: Results of transductive settings. OOM means "out of memory".
Type
Models
Cora
Citeseer
PubMed
Industry
ogbn-papers100M
GCN
81.8.0.5
70.8
79.310.7
45.910.4
0OM
Coupled
GAT
83.0=0.7
72.5=0.7
79.020.3
46.820.7
0OM
J--Net
81.8.0055
70.7.10.7
78.810.7
47.2.10.3
0OM
APPNP 83.3+0.55
718++0.5
80.1+0.2
46.7+00.6
0OM
AP-GCN
83.4.10.3
71.3::0.5
79.7100.3
46.9110.7
0OM
Decoupled
PPRGo
82.4+0.2
7133+0.5
80.0=0.4
46.6+0.55
0OM
DAGNN (Gate)
84,4+0.5
73.3+0.6
80.5+0.5
47.1+0.6
0OM
DAGNN (NDLS-L)"
84.4210.6
73.620.7
80.920.5
47.240.7
0OM
61.11006
61.81088
72.710.6
41.3.10.8
47.210.3
SGC
810:0.2
71.310.5
78.910.5
45.2110.3
63.210.2
Linear
SIGN
82.1
72.4:0.8
79.5
46.3100.
64.2
S'GC
82.7+0.3
73.0=0.2
79.9+0.3
46.6+0.66
64.7=0.3
GBP
83,910.7
72.910.5
80.610.4
46.910.7
65.210.3
NDLS-F+MLP"
84.1
13.5
81.1100.6
47.510.77
65.3
MLP+NDLS-L7
83,910.6
73.1
81.100.6
46.910.77
64.610.4
Linear
SGC+NDLS-I2
84,2+00.2
73.4+0.5
81.+0.44
47.1+0.6
64,9+0.3
NDLS
8..6
7..7
0.44
47.7.10.5
6..6
DAGNN (Gate) 21 and PPRGo M: (3) the linear-model-basee GNNs: MIP, SGC 27 SIGN 24
GC (37 and GBP 5). In the inductive setting, the compared baselines are sampling-baus based GNNs: GraphSAGE M. FastGCN [3]. ClusterGCN 7 and GraphSAINT (32). Detailed descriptions of these baselines are provided in Appendix A.4.
Implementations. To alleviate the influence of randomness, we repeat each method ten times and report the mean performance. The hyper-parameters of baselines are tuned by OpenBox [99 according to the original paper if available. Please refer to Appendix A.5 for more details.
Table 4: Results of inductive settings.
Tex Acturca
APLGCN
372k
SIGN
APPNP Atx
Models
Flickr
Reddit
SAGC
GraphSAGE
50.1
95,4=200
SCC
FastGCN
50.4110.1
93.720.0
ClusterGCN
48.120.5
95.710.0
GraphSAINT
51.1+0.1
96.6+0.1
10a
10
Training Time
NDL.SF+MLPP
51.9+0.2
96.6+-0.1
Figure Performance along with training time on the Industry dataset.
GraphS AGENND-LL
51.5+0.4
96,3++000
NDLS*
52.6+004
96.8++0.1
6.2 Experimental Results.
End-to-end comparison. To answer Q1, Table 3 and ssoow the test accuracy considered methods in transductive and inductive settings. In the inductive setting. NDLS outperforms one of the most competitive baselines GraphSAINT by a margin of 1.5% and 0.2% on Flickr and Reddit. NDLS exceeds the best GNN model among all considered baselines on each dataset by margin of 0.2% to 0.8% in the transductive setting. In addition, we observe that with NDLS-L, the model performance of MLP. SGC, NDLS-F+MLP, and GraphSAGE can be further improved by large margin. For example, the accuracy gain for MLP 21.8%, 11.3%, 8.4%, and 5.6% on Cora, Citseer, PubMed, and Industry, respectively. To answer Q2, we replace the gate mechanism in the vanilla DAGNN with NDLS-L and refer to this method as DAGNN (NDLS-L). Surprisingly. DAGNN (NDLS-L) achieves least comparable or (often) higher test accuracy compared with AP-GCN and DAGNN (Gate), and it shows that NDLS-L performs better than the learned mechanism in label smoothing, Furthermore, by replacing the original graph kernels with NDLS-F, IDLS-F+MLP outperforms both GC and GBP on all compared datasets. This demonstrates the effectiveness of the proposed NDLS.
Training Efficiency. answer Q3, we evaluate the efficiency of each method on a real-world industry graph dataset. Here, pre-compute the smoothed features of each imnerrmmoeel

---

80
80
Test Accuracy
80
Test Accuracy
70
60
8GC
5/GG
Test
SEN
60
GBP
70
03P
NBL5
0.25
0.50
0.75
1.00
0.25
0,50
0.75
1.00
10
20
Percent of Remaining Node Features
Percent of Remaining Edges
Training Nodes per Class
(a) Feature Sparsity
(b) Edge Sparsity
(c) Label Sparsity
Figure 4: Test accuracy on PubMed dataset under different levels of feature, edge and label sparsity.
Loca Smoothing Iteration
Gteeser Publiod
5
15
20
Node Degree
(a) LSI along with the node degree
(b) The visualization of LSI
Figure 5: (Left) LSI distribution along with the node degree in three citation networks. (Right) The visualization of LSI in Zachary's 's karate club network. Nodes with larger radius have larger LSIs.
GNN, and the time for pre-processing is also included in the training time. Figure illustrates the results the industry dataset across training time. Compared with mnear-model-aae GNNs, observe that (1) both the coupled and decoupled GNNs require a significantly larger training time; (2) NDLS achieves the best test accuracy while consuming comparable training time with SGC.
Performance on Sparse Graphs. To reply Q4, we conduct experiments to test the performance of NDLS on feature, edge, and label sparsity problems. For feature sparsity, we assume that the features of unlabeled nodes partially missing. In this scenario, it necessary to calculate personalized propagation iteration to "recover" each node's feature representation. To simulate edge sparsity settings, randomly remove fixed percentage of edges from the original graph. Besides, we enumerate the number of nodes per class from to 20 in the training set to measure the effectiveness of NDLS given different levels of label sparsity. The results in Figure 4 show that NDLS outperforms all considered baselines by large margin across different levels feature, edge, and label sparsity, thus demonstrating that our method is more robust the graph sparsity problem than the linear-model-baee GNNs.
Interpretability. As mentioned by Q1, we here answer why NDLS is effective. One theoretical property of LSI is that the value correlates with the node degree negatively. We divide nodes into several groups, and each group consists of nodes with the same degree. And then we calculate the
average LSII value for each group in the three citation networks respectively. Figure 5(a) depicts that
nodes with a higher degree have a smaller LSI, which is consistent with Theorem 3.1 We also use
NetworkX [10] visualize the LSI in Zachary's karate club network [31]. Figure ((b) where the
radius each node corresponds to the value of LSI, shows three interesting observations: (1) nodes
with larger degree have smaller LSIs; (2) nodes in the neighbor area have similar LSIs; (3) nodes
adjacent to super-node have smaller LSIs. The first observation is consistent with Theorem 3.1 and
the latter two observations show consistency with Theorem 3.2
7 Conclusion
In this paper, we present node-dependent local smoothing (NDLS), a simple and scalable graph learning method based on the local smoothing of features and labels. NDLS theoretically analyzes

---

what influences the smoothness and gives bound to guide how to control the extent of smoothness for different nodes. By setting a node-specific smoothing iteration, each node in NDLS can smooth its feature/label to a local-smoothing state and then help to boost the model performance. Extensive experiments on seven real-world graph datasets demonstrate the high accuracy, scalability, efficiency, and flexibility of NDLS against the state-of-the-ar GNNs.
Broader Impact
NDLS can be employed in areas where graph modeling is the foremost choice, such as citation networks, social networks, chemical compounds, transaction graphs, road networks, etc. The effectiveness of NDLS when improving the predictive performance broad range of societal benefits. For example, accurately predicting the malicious accounts on transaction networks can help identify criminal behaviors such as stealing money and money laundering. Prediction on road networks can help avoid traffic overload and save people's time. significant benefit of NDLS is that it offers a node-dependent solution. However, NDLS faces the risk of information leakage in the smoothed features or labels. In this regard, we encourage researchers to understand the privacy concerns of NDLS and investigate how to mitigate the possible information leakage.
those areas may bring
Acknowledgments and Disclosure of Funding
This work supported by NSFC (No. 61832001, 61972004), Beijing Academy of Artificial Intelligence (BAAI), PKU-Baidu Fund 2019BD006, and PKU-Tencent Joint Research Lab. Zhi Yang and Bin Cui are the corresponding authors.
References
[1] A. Bojchevski, J. Klicpera, B. Perozzi, A. Kapoor, M. Blais, B. Rózemberczki, M. Lukasik, and S. Günnemann. Scaling graph neural networks with approximate pagerank. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2464-2476 2020.
[2] L. Cai and S. Ji. A multi-scale approach for graph link prediction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3308-3315, 2020.
[3] Chen, T. Ma, and C. Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC. Canada, April 30- May 2018, Conference Track Proceedings. 2018
[4] J. Chen, J. Zhu, and L. Song. Stochastic training of graph convolutional networks with variance reduction. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, pages 941-949, 2018.
[5] M. Chen, Z. Wei, B. Ding, Y. Li, Y. Yuan, X. Du, and J. Wen. Scalable graph neural networks via bidirectional propagation. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[6] T. Chen and C. Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016, pages 785-794, 2016.
[7] W. Chiang, X. Liu, S. Si, Y. Li, S. Bengio, and C. 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, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pages 257-266, 2019.
[8] G. Cui, J. Zhou, C. Yang. and Z. Liu. Adaptive graph encoder for attributed graph embedding. In KDD 20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA. USA. August 23-27, 2020, pages 976-985, 2020.
10

---

[9] Q. Guo, X. Qiu, X. Xue, and Z. Zhang. Syntax-guided text generation via graph neural network. Sci. China Inf. Sci., 64(5). 2021.
[10] A. Hagberg, P. Swart, and D. S Chult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Lab.(LANL) Los Alamos, NM (United States), 2008.
[1]] W. L. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning on large graphs In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 1024-1034, 2017.
[12] x. He, K. Deng. X. Wang, Y. Li, Y. Zhang, and M. Wang. Lightgen: Simplifying and powering graph convolution network for recommendation. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 639-648. 2020.
[13] W. Hu, M. Fey, H. Ren, M. Nakata, Y. Dong, and J. Leskovec. OGB-LSC: A large-scale challenge for machine learning on graphs. CoRR, abs/2103.09430 2021.
[14] W. Huang, T. Zhang, Y. Rong, and J. Huang. Adaptive sampling towards fast graph representation learning. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8. 2018, Montréal, Canada, pages 4563-4572, 2018.
[15] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In Sth International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
[16] J. Klicpera, A. Bojchevski, and S. Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
[17] K.-H. Lai, D. Zha, K. Zhou, and X. Hu. Policy-gnn: Aggregation optimization for graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 461-471, 2020.
[18] Q. Li, Z. Han, and X.-M. Wu. Deeper insights into graph convolutional networks for semi- supervised learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018.
[19] Y. Li, Y. Shen, W. Zhang, Y. Chen, H. Jiang, M. Liu, J. Jiang. J. Gao, W. Wu, Z. Yang, C. Zhang, and B. Cui. Openbox: A generalized black-bor box optimization service. KDD '21: The 27th ACM SIGKDD Conference Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14-18, 2021, pages 3209-320 -219,, 2021.
[20] A. Liaw, M. Wiener, et al. Classification and regression by randomforest. R news, 2(3):18-22, 2002.
[21] M. Liu, H. Gao, and S. Ji. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 338-348, 2020.
[22] X. Miao, N. M. Gürel, W. Zhang, Z. Han, B. Li, W. Min, S. X. Rao, H. Ren, Y. Shan, Y. Shao, Y. Wang, F. Wu, H. Xue, Y. Yang. Z. Zhang, Y. Zhao, S. Zhang, Y. Wang, B. Cui, and C. Zhang. Degnn:
Improving graph neural networks with graph decomposition. ACM SIGKDD Conference Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14-18, 2021, pages 1223-1233, 2021.
KDD '11: The 27th
[23] X. Miao, W. Zhang, Y. Shao, B. Cui, L. Chen, C. Zhang, and J. Jiang. Lasagne: A multi-layer graph convolutional network framework via node-aware deep architecture. IEEE Transactions on Knowledge and Data Engineering, 2021.
11

---

[24] E. Rossi, F. Frasca, B. Chamberlain, D. Eynard, M. M. Bronstein, and F. Monti. SIGN: scalable inception graph neural networks. CoRR, abs/2004.11198, 2020.
[25] I. Spinelli, S. Scardapane, and A. Uncini. Adaptive propagation graph convolutional network. IEEE Transactions on Neural Networks and Learning Systems, 2020.
[26] P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
[27] Wu, A. H. Jr., Zhang, C. Fifty, T. Yu, and K. Q. Weinberger. Simplifying graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, Califormia, USA, pages 6861-6871, 2019,
[28] S. Wu, W. Zhang. Sun, and B. Cui. Graph neural networks in recommender systems: A survey. CoRR, abs/201 1.02260, 2020.
[29] S. Wu. Y. Zhang, C. Gao, K. Bian, and B. Cui. Garg; Anonymous recommendation of point- of-interest in mobile networks by graph convolution network. Data Science and Engineering, ((4):4334447 2020.
[30] K. Xu, C. Li, Y. Tian, T. Sonobe, K. Kawarabayashi, and S. Jegelka. Representation learning on graphs with jumping knowledge networks. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässsan, Stockholm, Sweden, July 10-15, 2018, pages 5449-5458, 2018.
[31] W. W. Zachary. An information flow model for conflict and fission in small groups. Journal of anthropologcaal research, 33(4):452 473, 1977.
[32] H. Zeng, H. Zhou, A. Srivastava, R. Kannan, and V. K. Prasanna. Graphsaint: Graph sampling based inductive learning method. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
[33] W. Zhang, Y. Jiang, Y. Li, Z. Sheng, Y. Shen, X. Miao, L. Wang. Z. Yang, and B. Cui. ROD: aeception-aware online distillation for sparse graphs. In KDD 21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14-18, 2021, pages 2232-2242, 2021.
[34] W. Zhang, X. Miao, Y. Shao, Jiang. L. Chen, O. Ruas, and B. Cui. Reliable data distillation on graph convolutional network. In Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14-19, 2020, pages
2020.
[35] W. Zhang, Z. Sheng, Y. Jiang, Y. Xia, J. Gao, Z. Yang, and B. Cui. Evaluating deep graph neural networks. CoRR, abs/2108.00 00055,, 2021.
[36] X. Zhang, H. Liu, Q. Li, and X. Wu, Attributed graph clustering via adaptive graph convolution. In Proceedings of the Ewenty-Eightt International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pages 4327-4333, 2019.
[37] H. Zhu and P. Koniusz. Simple spectral graph convolution. In 9th International Conference on Learning Representations, ICLR 2021, Viriual Event, Austria, May 3-7, 2021, 2021.
12


Reviews:
[{"review_id": "xvMZmych23", "reviewer": "Reviewer_yciW", "summary": "This work proposes NDLS, a strategy to estimate a different number of 'propagations' for each node in the graph, delimiting the neighborhoods used to update node embeddings. The authors apply NDLS both as a pre-processing (feature space) and post-processing (prediction space) technique. Between pre-processing and post-processing, any vanilla (non-Graph) classifier can be used.", "questions": "", "limitations": "", "rating": 7, "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": "Intuitively, NDLS chooses neighborhood sizes so that all nodes are equally far from oversmoothing. Overall, I like this idea and its simplicity. Scalability is also an asset, and the idea for computing node-dependent numbers of propagations is intuitive. I think this work fits well in the current trend of simplifying graph ML. The idea is significantly novel and the technical developments appear sound. The writing is passable.\n\n### Questions and issues\n* How does this work compare to https://arxiv.org/abs/2010.13993 ?\n\n* Why are the results in Table 3 different from the ones in the OGB leaderboard? For instance, Table 3 shows SIGN achieving $64.2$ average accuracy on ogbn-papers100M. However, OGB leaderboards (https://ogb.stanford.edu/docs/leader_nodeprop/) show $65.68$.\n\n* Previous works (https://arxiv.org/abs/2003.00982) have shown that small datasets --- such as Cora, Citeseer and Pubmed --- are not reliable benchmarks. Do you have results for other OGB large-scale benchmarks?  \n\n* Are the bounds in section 3 used only for interpretation or to avoid directly computing $k$? \n\n* How is $k(\\cdot, \\cdot)$ computed in practice and how expensive is it? Does the method require computation of eigenvalues (as in Theorem 3.1, eq 5)?\n\n* As a curiosity, how important is the normalization factor in Eq. 8? Do you have any ablation studies for this?\n\n* In the sparse graph experiments, what do the authors do with missing features? Fill with some default value?\n\n* Can the authors add more plots like Figure 3 (times vs. performance) either in the manuscript or appendix?\n\n\n### Typos, etc\n* The authors often use acronyms without introducing them (e.g. in the abstract and first paragraph of intro)\n* Line 40: 'poorly connected nodes needs' -> poorly connected nodes need \n* Lines 56-57: authors say real-world graphs have long-tailed degree distributions. Not all real-world graphs do have it. Probably better to be careful.\n* Line 75 and 76: a matrix should not be defined as a set\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately discussed limitations.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "q5IyFC3-AUA", "reviewer": "Reviewer_2avU", "summary": "In this paper, the authors proposed a GNN structure name NDLS which comprises three parts: i) the feature propagation part, NDLS-F, ii) a MLP for label prediction and iii) a post processing label smoothing part NDLS-L. The first and last part and are done individually as pre-processing and post-processing, where each node propagates its feature/label representation according to their local smooth iteration (LSI). The LSI is computed per node based on its connectivity and designed to avoid over-smoothing instead of using same step for all nodes. Due to the simplified framework, the model can be trained efficiently without losing performance when compared to SOTA baselines. ", "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 paper is very well-written and easy to follow, with intuitive figures for better understanding the concept. The authors did extensive experiments and the results are nicely interpreted. \n\npros: \n- The difference of LSI distribution in different datasets is a nice indicator of how over-smoothing is also a data-dependent issue and should be treated adaptively.\n- Detailed experiments with analysis on how different component of the model affect the results.\n- Efficient algorithm with separated component that can be precomputed.\n- Intuitive interpretation of results and trained models. \n\ncons: \n- The definition of LSI in equation (4) implicitly assumes a monotonous decreasing distance with k, which I am not sure if this is the case.  \n- Improvement on inductive settings are marginal, and wether separate pre/post processing is needed is not clear.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors did not addressed the possible limitation and negative societal impact of their work. Protecting personal privacy especially in social network data is always worth discussion. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "h4OkaemrTWt", "reviewer": "Reviewer_1k7Z", "summary": "This paper proposes a novel algorithm, node-dependent local smoothing (NDLS), which allows controlling the smoothness of every node by setting a node-specific smoothing iteration and applies to both feature smoothing and label smoothing. NDLS theoretically analyzes what influences the smoothness and gives a bound to guide how to control the extent of smoothness for different nodes. Extensive experiments on seven real-world graph datasets demonstrate that NDLS pipeline enjoys state-of-the-art performance on node classification tasks, can be combined with any GNN models, and is scalable and efficient.", "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": "----------Strengths----------\n\n(1) The proposed NDLS algorithm is novel and generalizes some existing smoothing techniques.\n\n(2) NDLS shows state-of-the-art performance across various datasets. Thus the algorithm is robust and generally reliable in practice.\n\n(3) The paper is generally well written. The authors provide some theoretical analysis of the space and time complexities of the proposed NDLS pipeline. Moreover, the experimental results are summarized using some nice figures.\n\n(4) The NDLS kernel can act as a drop-in replacement for other graph kernels and be combined with some existing models.\n\n----------Weaknesses----------\n\n(1) The NDLS pipeline effectively unifies and generalizes the feature and label smoothing algorithms used in GCN, SGC, APPNP, etc. The authors claim NDLS is advantageous because it allows controlling the smoothness to avoid under-smoothing or over-smoothing. However, it seems that this work does not provide deeper insight into the success of smoothing methods, especially why the control of smoothness is critical to improve the existing feature and label smoothing algorithms. In this sense, the overall contribution seems limited and a little bit incremental. The performances gain in experiments are also relatively small.\n\n(2) Apart from SGC, SIGN, and GBP, I think it is also a good idea to compare with C&S [1] if possible. C&S uses a different smoothing procedure which is called Correct and Smooth (C&S). It is interesting to discuss whether the proposed NDLS algorithm can be combined with C&S.\n\n----------Overall----------\n\nOverall, I think this work is an interesting generalization of the existing smoothing algorithms for graph learning. However, it seems unclear to me why setting a node-specific smoothing iteration is crucial. Hence, I recommend weak rejection.\n\n----------References----------\n\n[1] Huang, Q., He, H., Singh, A., Lim, S.N. and Benson, A.R., 2020. Combining label propagation and simple models out-performs graph neural networks. arXiv preprint arXiv:2010.13993.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The potential negative social impact of the work is not presented in the paper. Although the reviewer does not foresee any potential negative impacts, the authors are encouraged to add such discussions if space permits.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "LqafgQcuNX2", "reviewer": "Reviewer_8aSG", "summary": "This paper proposed a node-dependent local smoothing method for graph neural networks via computing a local smoothing iteration value. Experimental evaluation was conducted on seven datasets.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written on the whole. Illustrations are intuitive and can help readers understand the proposed idea greatly. Nonetheless, there are several questions/problems as detailed below:\n\n1. The use of acronyms, particularly in the abstract, is problematic to me. SGC and APPNP are acronyms unknown to me at least. Acronyms should be defined before using.\n\n2. Notations are not always consistent. For example, I think the X in line 109 and 111 should be in bold normal font, as previously appeared.\n\n3. Since the \"Industry\" dataset is not in the public domain, it will be helpful to provide an explanation why this dataset is chosen instead of another public dataset.\n\n4. Could you do a paired t-test at least for GBP vs NDLS in Table 3 to study the statistical significance of the improvements?\n\n5. Training efficiency study in Sec. 6.2 and Figure 3: Why to choose the private \"Industry\" dataset instead of a public dataset for this study. Do you have similar studies and plots for other datasets? Using a public dataset will make the result more reproducible.\n\n6. From Figure 5(a), I am wondering whether using the node degree will be a simpler alternative than the proposed LSI for the proposed framework, e.g. 1/node_degree or similar. Have you studied such a simple choice?\n\n7. Although Appendix A.5 provided hyperparameter details, it is not always clear how certain hyperparameters were chosen. For example, for k=200 in stage (1) and k=40 in stage (3), were these number just magically set by the authors or from tuning? If by tuning, how was it done? More importantly, I did not find studies on the performance sensitivity w.r.t. such hyperparameters.\n\n8. Consistency issue: why is the caption for Table 4 at the bottom while captions for other tables are at the top?\n\n9. Anonymity issue: the supplementary material is not fully anonymized. The readme shows a username with a local path \"C:\\Users\\......\\Desktop\\NDLS\", where I replaced the name with \"......\".\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See the above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a node-dependent local smoothing (NDLS) algorithm to control the smoothness of every node. NDLS provides a bound to guide how to control the extent of smoothness for different nodes. Extensive experiments on seven real-world graph datasets demonstrate that NDLS pipeline enjoys state-of-the-art performance on node classification tasks, can be combined with any GNN models, and is scalable and efficient.


The proposed NDLS algorithm is novel and generalizes some existing smoothing techniques. The NDLS kernel can act as a building block to replace other graph kernels and be combined with some existing models. The authors also provide some theoretical analysis of the space and time complexities of the proposed NDLS pipeline. 

The paper is very well-written and easy to follow, with intuitive figures for better understanding the concept. 

NDLS shows state-of-the-art performance across various datasets. The results are nicely interpreted.  Thus the algorithm is robust and generally reliable in practice.

Therefore, we recommend accepting this paper. 





Decision: Accept (Spotlight)