NAFS: A Simple yet Tough-to-Beat Baseline for Graph Representation Learning
Authors: Wentao Zhang
Zeang Sheng
Mingyu Yang
Yang Li
Yu Shen
Zhi Yang
Zichao Yang
Bin CUI
Venue: ICLR 2022 Submitted (2022)
Keywords: Feature Smoothing
Graph Neural Network
Graph Representation Learning

Abstract: Recently, graph neural networks (GNNs) have shown prominent performance in graph representation learning by leveraging knowledge from both graph structure and node features. However, most of them have two major limitations. First, GNNs can learn higher-order structural information by stacking more layers but can not deal with large depth due to the over-smoothing issue.  Second, it is not easy to apply these methods on large graphs due to the expensive computation cost and high memory usage. In this paper, we present node-adaptive feature smoothing (NAFS), a simple non-parametric method that constructs node representations without parameter learning. NAFS first extracts the features of each node with its neighbors of different hops by feature smoothing, and then adaptively combines the smoothed features. Besides, the constructed node representation can further be enhanced by the ensemble of smoothed features extracted via different smoothing strategies. We conduct experiments on four benchmark datasets on two different application scenarios: node clustering and link prediction. Remarkably, NAFS with feature ensemble outperforms the state-of-the-art GNNs on these tasks and mitigates the aforementioned two limitations of most learning-based GNN counterparts. 

Under review as a conference paper at ICLR 2022
NAFS: A SIMPLE YET TOUGH-TO-BEAT BASELINE FOR GRAPH REPRESENTATION LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Recently, graph neural networks (GNNs) have shown prominent performance in graph representation learning by leveraging knowledge from both graph structure and node features. However, most of them have two major limitations. First, GNNs can learn higher-order structural information by stacking more layers but can not deal with large depth due to the moo-smngthing issue. Second, is easy to apply these methods on large graphs due to the expensive computation cost and high memory usage. this paper, we present node-adaptive feature smoothing (NAFS), a simple paramaraettric method that constructs node representations without parameter learning. NAFS first extracts the features of each node with its neighbors of different hops by feature smoothing, and then adaptively combines the smoothed features. Besides, the constructed node representation can further be enhanced by the ensemble of smoothed features extracted via different smoothing strategies. We conduct experiments on four benchmark datasets on two different application scenarios: node clustering and link prediction. Remarkably, NAFS with feature ensemble outperforms the state-of-the-an GNNs on these tasks and mitigates the aforementioned two limitations of most learning-basce GNN counterparts.
INTRODUCTION
In recent years, graph representation learning has been extensively applied in various application scenarios, such as node clustering. link prediction, node classification, and graph classification (Kipf) & Welling 201 6b Hamilton et al. 2017 Bo et al.) 2020 Hettige et al. 2020 Wang et al.) 2016 Wu al., 2020 Abu-El EI-Haija et al. 2019). The goal graph representation learning is to encode graph information node embeddings. Traditional graph representation learning methods, such
as Walk (Perozzi et al.] 2014). Node2vee (Grover Leskoved 2016). LINE (Tang et al.
2015), and ComE (Cavallari al. (217)) merely focus preserving graph structure information. GNN-based graph representation learning has attracted intensive interest by combining knowledge from both graph structure and node features. While most of these GNN-based methods are designed based on Graph AutoEnc (GAE) and Variational Graph AutoEncoder (VGAE) (Kipf & Welling 2016b), these methods share two major limitations:
Shallow Architecture. Previous work shows that although stacking multiple GNN layers in Graph Convolutional Network (GCN) (Kipf & Welling (016a) is capable of exploiting deep structural information, applying a large number of GNN layers might lead to indistinguishabl node embeddings, i.e., the over-smoothing issue (Li al. 2018 Therefore, most state-of-the-ar GNNs resort to shallow architectures, which hinders the model from capturing long-range dependencies.
Low Scalability. based graph representation learning methods can not scale well large graphs due to the expensive computation cost and high memory usage. Most existing GNNs need to repeatedly perform the computationally expensive and recursive feature smoothing. which involves the participation of the entire graph at each training epoch. Furthermore, most methods adopt the same training loss function as GAE, which introduces high memory usage by storing the dense- form adjacency matrix GPU. For a graph of size 200 million, its dense-form adjacency matrix requires a space of roughly 150GB, exceeding the memory capacity of the current powerful GPU devices.
To tackle these issues, we propose embarrassingly simple: just smooth the node features and then combine the smoothed features in node-adaptive manner. We name this method node-adaptive feature smoothing (NAFS), and its
graph representation learning method. which is

---

Under review as a conference paper at ICLR 2022
goal is to construct better node embeddings that integrate the information from both graph structural information and node features. Based on the observation that different nodes have highly diverse "smoothing speed",, NAFS adaptively smooths each node feature and takes advantage of both low- order and high-order neighborhood information of each node. In addition, feature ensemble is also employed to combine the smoothed features extracted via different smoothing operators. Since NAFS is training-free, it significantly reduces the training cost and scales better to large graphs than most GNN-based graph representation learning methods.
This paper is not meant to diminish the current advancements in GNN-based graph representation learning approaches. Instead, we aim to introduce an easier way obtain high-quality node embeddings and understand the source of performance gains of these approaches better. Feature smoothing could be a promising direction towards a more simple and effective integration of information from both graph structure and node features.
Our contributions are as follows: (1) New perspective. To the best of our knowledge, we are the first to explore the possibility that simple feature smoothing without any trainable parameters could even outperform state-of-the-art GNNs; this incredible finding opens up new direction towards efficient and scalable graph representation learning. (2) Novel method. We propose NAFS, a node- adaptive feature smoothing approach along with various feature ensemble strategies, to fully exploit knowledge from both the graph structure and node features. (3) State-of-ther oatte--o-tehearr art performance. We evaluate the effectiveness and efficiency of NAFS on real-world datasets across various graph-based tasks, including node clustering and link prediction. Empirical results demonstrate that NAFS performs comparably with or even outperforms the state-of-the-an GNNs, and achieves up to two orders of magnitude speedup. In particular, on PubMed, NAFS outperforms GAE (Kipf & Welling 2016b) and AGE (Cui et al. (020) by margin of 9.0% and 3.8% in terms of NMI in node clustering, while achieving up to 65.4x and 88.6x training speedups, respectively.
PRELIMINARY
In this section, we first explain the notations and problem formulation. Then, review current GNNs and GNN-based graph representation learning.
2.1 NOTATIONS AND PROBLEM FORMULATION.
In this paper, we consider an undirected graph (V,8) with |V] nodes and |8| = m edges. Here we suppose that m x n as it is the case in most real-world graphs. We denote by A the adjacency matrix of G. Each node can possibly have feature vector of size f. which stacks up to an x f feature matrix X. The degree matrix of A is denoted as D diag (d), d2. where d. = Eeyev Aij- We denote the final node embedding matrix as Z, and evaluate in both the node clustering and the link prediction tasks. The node clustering task requires the model to partition the nodes into disjoint groups G1, G2,, Ge. where similar nodes should be in the same group. The target of the link prediction task is to predict whether an edge exists between given node pairs.
d,)) E R=**
2.2 GRAPH CONVOLUTIONAL NETWORK.
Based on the assumption that locally connected nodes are likely to enjoy high similarity (ccPheson cct al., 2001), each node in most GNN models iteratively smooths the representations of its neighbors for better node embedding. Below the formula of the (-th GCN layer (Kipf & Welling 2016a):
x 8 (Ax""
Á A= -112
= A+...
(0) is the original feature matrix, ( are the trainable weights, and 5 is the activation function. Å is the smoothing matrix that helps each node to smooth representations of neighboring nodes.
where (1) is the node embedding matrix at layer 7, (0)
As shown in Eq. [ each GCN layer contains two operations: feature aggregation (smoothing) and feature transformation. Figure I shows the framework of a two-layer GCN. The (-th layer in GCN firstly executes feature smoothing on the node embedding (I-1), Then, the smoothed feature (1-1) transformed with trainable weights ( and activation function 8 to generate new node embedding (1), Note that GCN will degrade to ML.P if feature smoothing is removed from each layer.
2

---

Under review as a conference paper at ICLR 2022
Matrix X
GNN
ML.P
X
XP9
Oulputs
Dense layer
Aggregation
2000
g
AX
Normalized adjucent matrix
Figure 1: The framework of two-layer GNN models.
2.3 GNN-BASED GRAPH REPRESENTATION LEARNING.
GAE Kipf & Welling 201 the first and the most representative GNN-based graph embedding method, adopts an encoder to generate node embedding matrix Z with inputs Å and X. A simple inner product decoder is then used reconstruct the adjacency matrix. The final training loss of GAE the binary entropy loss between A' and A, the reconstructed adjacency matrix and the original adjacency matrix with self loop added.
sigmoid(Z ) L
-A., log - -(1 (11 A.,)) log(1 A(.)).
(2)
ISijSn
Motivated by GAE, lots of GNN-based graph representation learning methods are proposed recently. MGAE (Wang et al. 2017) presents a denoising marginalized autoencoder that reconstructs the node feature matrix X. ARGA Pan et 2018) adopts the adversarial learning strategy, and its generated node embeddings are forced to match prior distribution. DAEGC (Wang et al.) 2019)) exploits side information to generate node embeddings in a self-supervised way. AGC (Zhang et al. 2019) proposes an improved filter matrix to better filter out the high-frequency noise. AGE (Cui et al. 2020) further improves AGC by using the similarity of embedding rather than the adjacency matrix to consider original node feature information. Compared with GNN-based graph representation learning methods that rely on the trainable parameters to learn node embeddings, our NAFS is training-free and thus enjoys higher efficiency and scalability.
3 OBSERVATION AND INSIGHT
In this section, we make a quantitative analysis on the over-smoothing issue at the node level and then provide some insights when designing NAFS on graphs.
3.1 FEATURE SMOOTHING IN DECOUPLED GNNS
Recently, many works (Wu et al. 2019 Zhu & Koniusz 2021 Chen et al. 2020 Zhang al. 2021
propose to decouple the feature smoothing and feature transformation in each GCN layer for scalable node classification. Concretely, they execute the feature smoothing operation in advance, and the smoothed features are then fed into a simple MLP to generate the final predicted node labels. Under this framework, the predictive node classification accuracy of these methods is comparable with or even higher than the one of coupled GNNs, and these works claim that the true power of GNNs lies in feature smoothing rather than feature transformation.
We split the framework of these decoupled GNNs into two parts: feature smoothing and MLP training. Feature smoothing aims to combine the graph structural information and node features into better features for the subsequent MIP; while MI.P training only takes in the smoothed feature and is specially trained for a given task. As stated by previous decoupled GNNs (Wu et al. 2019 Zhu & Koniusz 2021), the true success of GNNs lies in feature smoothing rather than feature transformation. Correspondingly, we propose to remove feature transformation and preserve the key feature smoothing part alone for simple and scalable node representation.
There another branch of GNNs that also decouple the feature smoothing and feature transformation. The most representative method of this category is APPNP (Klicpera et al., 22188. It first feeds the raw node features into an MLP to generate intermediate node embeddings; then the personalized RageRank based propagation operations performed the node embeddings to produce final
3

---

Under review as a conference paper at ICLR 2022
prediction results. However, compared with scalable decoupled GNNs mentioned in the previous paragraph, this branch of GNNs still have to recursively execute propagation operations in each training epoch, which makes it impossible to perform on large-scale graphs. In the remaining part of this paper, the terminology "decoupled GNNs" refers particularly to the scalable decoupled GNNs mentioned in the previous two paragraphs.
3.2 MEASURING SMOOTIIIGG LEVEL
To capture deep graph structural information, straightforward way is simply stack multiple GNN layers. However, large number of feature smoothing operations in GNN model would lead to indistinguishable node embeddings, i.c., the over-smoothing issue (Li al., 2018). Concretely, if we execute ÁX for infinite times, the node embeddings within the same connected component would reach a stationary state. When adopting À = D AAD A follows
(d. (d, + +1)=-
A A
2m +
which shows that the influence from node to by is only determined by their degrees. Under the extreme condition that r = O, all the nodes within one connected component have exactly the same representation, making it impossible to apply the node embeddings to subsequent tasks.
Here we introduce a new metric, "Over-smoothing Distance", to measure each node's smoothing level. A smaller value indicates that the node is closer to the stationary state, i.e., closer to over-smoothing.
Definition 3.1 (Over-smoothing Distance). The Over-smoothing Distance (k(k) parameterized by node i and smoothing step k is defined as
Di(k)= = Dis([A (I,
(4)
where [A*X]; denotes the ith row of A representing the representations of node vi after smoothing is times; X); denotes the 8t row of A X, representing the stationary state of node vai Dis(-) a distance function or a function positively relative with the difference, which can be implemented using Euclidean distance, the inverse of cosine similarity, etc.
3.3 DIVERSE SMOOTHING SPEED ACROSS NODES.
To examine the factors that affect D; (k). divide nodes in the PubMed dataset into three different groups according to their degrees. In Figure 2 we show the trends of nodes the first group and the second group where the group-averaged (k) changes with the number of smoothing step increases. The trend of (k) averaged over all the nodes is also provided, and the Euclidean distance is chosen the distance function. Figure 2 shows that the (k) of nodes with degrees larger than 60 drops more quickly than nodes with degrees smaller than 3, which implies that nodes with high degrees approach the stationary state more rapidly than the nodes with low degrees.
The quantitative analysis empirically illustrates that the degree of each node plays an essential role in one's 's optimal smoothing step. Intuitively, nodes with high degrees should have relatively small smoothing steps than nodes with low degrees. In addition, in Appendix A we have made detailed theoretical analysis about the graph sparsity, another factor that influences the smoothing speed.
3.4 DESIGN INSIGHTS OF NAFS
Though using feature smoothing operations inside the previous decoupled GNNs is scalable for large graph representation learning. it will lead to sub-optimal node representation. According to the observation in Sec. 3.3 is sub-optimal to execute feature smoothing for all the nodes indiscriminately as previous decoupled GNNs do since nodes with different structural properties have diverse smoothing speeds. Therefore, node-adaptive feature smoothing (i.e., different nodes have different smoothing levels or mechanisms with equivalent effect) must be adopted to satisfy each node's 's diverse needs of smoothing level. In our proposed method NAFS, we utilize the metric (k) defined in Def. 3.1 to help accomplish the aim of node-adaptive feature smoothing.
4

---

Under review as a conference paper at ICLR 2022
Average Over- smoothing Distance
0.4
all the nodes
nodes with degree
0.3
nodes with degree
0.2
0.1
2
6
10
12
14
16
18
20
Number of Aggregation Steps
Figure 2: Diverse smoothing speed across nodes with different degrees.
PROPOSED METHOD
In this section, we present NAFS, training-free method for scalable graph representation learning. We first compute the smoothed features with the feature smoothing operation. Then the feature ensemble operation is used to combine the smoothed features generated by different smoothing strategies. The pseudo code of NAFS is provided in Appendix D
4.1 NODE-ADAPTIVE FEATURE SMOOTHING
Figure provides overview of NAFS. When repeatedly executing X Áx(11), the smoothed node embedding matrix (I-1) contains deeper graph structural information with / increases. The multi-scale node embedding matrices (X( ( ..... x(K) (K' is the maximal smoothing step) are then combined into single matrix X such that both local and global neighborhood information are reserved for each node.
The analysis in Sec. 3.3 illustrates that the speed each node achieving its stationary state is highly diverse, which suggests that nodes should be treated individually. To this end, we define "Smoothing Weight" based on (k))) introduced in Def. 3.1 for each node that the smoothing operation be performed in a node-adaptive manner.
Definition 4.1 (Smoothing Weight). The Smoothing Weight (k(k) parameterized by node v; and smoothing step l is defined based on the softmax value of (O), D,(1), ..., .",):())):
K
wx(k) c
P.())
P.0))
L=0
where K is the maximal smoothing step.
To calculate D.(k) more efficiently, alternative is to replace [À x XX, in Eq. with X, and implement Dis(-) as the cosine similarity. Larger D:(k) this case means that node v; is farther from the stationary state and [ X intuitively contains more relevant node information. Therefore, for node vs the smoothed feature with larger (k) (i.e., larger w, (k)) should contribute more the final node embedding. The smoothing weight can be formulated in the following matrix form: Definition 4.2 (Smoothing Weight Matrix). The Smoothing Weight Matrix W (k) parameterized by smoothing step k is defined as the diagonal matrix derived from n(k) E R
W(k) Diag(n(k)).
T)(k)[ wi(k), V1 Visisn
(6)
Given the maximal smoothing step K, the multi-scale smoothed features (x("), X, x(), x X (() and the corresponding Smoothing Weight Matrices (W()), W(1).... W(K) the final smoothed
feature X can be represented as: X W(k)A*X.
4.2 FEATURE ENSEMBLE
Different smoothing operators actually act as different knowledge extractors. For example, by setting 0.5, and 0, À Dr represents the symmetric normalized adjacency matrix
5

---

Under review as a conference paper at ICLR 2022
A
X
X
X
X
OX 1)
ANNNNNSS
W(K (K)
W
Figure 3: An overview the proposed node-adaptive feature smoothing operation.
D-1/2 AD 1/2 (Kipf & Welling 2016a), the random walk transition probability matrix D Xu al. 2018 and the reverse random walk transition probability matrix AD ZZng al. 2019). respectively. These variants of Å captures and reserves different scales and dimensions of knowledge from both graph structures and node features.
To achieve the same effect, the feature ensemble operation has multiple knowledge extractors: we vary the value of in the normalized adjacency matrix A, D AD -" to easily acquire different knowledge extractors. These knowledge extractors are adopted inside the feature smoothing operation to generate different smoothed features. Concretely, the value of r controls each edge. So different values of generate different weight values for all the edges in the graph. which would increase the diversity of our smoothed features evidently. The ablation study in Sec. 66.5 shows that the increased diversity contributes lot the high performance of our generated node embeddings when applied to downstream tasks.
normalized weight of
The detailed procedure of feature ensemble operation is follows: Given {ri, r2, ..., rr). firstly perform the feature smoothing operation to generate corresponding smoothed features (X(11, ( strategy, which can be implemented as concatenating, mean pooling, max pooling, etc.
{.). Then, we combine them as Z + @ X(1) where + is the ensemble
5 ADVANTAGES OVER TRADITIONAL APPROACHES
NAFS generates node embeddings in a training free manner, making it highly efficient and scalable. Moreover, the node-adaptive smoothing strategy enables it to capture deep structural information. In this subsection, we analyze the advantages our NAFS over GAE and its variants.
Deep Structural Information. By assigning each node with personalized smoothing weights, NAFS can gather deep structural information without encountering the wre-smoothing issue and keep the time and memory cost low. While for GAE and its variants, they either 1) have coupled structure that cannot go deep due to low efficiency and high memory cost (e-g., GAE) or 2) are unable to adaptively capture structural information and encounter the over-smoothing issue when going deeper (e.g., AGE).
Efficiency. Compared with GAE and its variants, our proposed NAFS does not have any trainable parameters, giving a significant advantage in efficiency. When generating node embeddings, NAFS only needs to execute the feature smoothing and feature ensemble operations, which has a time complexity of OfKmff + Kn), where K denotes the maximal smoothing step. On the other hand, the asymptotic training time complexity of GAE and its variants is On + n² which is one further present efficiency comparison in detail on
magnitude larger than NAFS. In Sec. 6.4 real-world datasets between NAFS and GAE.
Memory Cost. Our proposed NAFS enjoys not only high efficiency but also low memory cost. NAFS only requires to store the sparse adjacency matrix and the smoothed features, and thus the memory cost is Omm + nff), which grows linearly with graph size in typical real-world graphs. For GAE and its variants, they need additional space to store the training parameters and especially the reconstructed dense adjacency matrix, making their memory cost Onn + nf),, which is also one magnitude larger than NAFS. Scalability comparison conducted on synthetic datasets between NAFS and GAE can be found in Appendix C.2

---

Under review as a conference paper at ICLR 2022
Table 1: Link prediction performance comparison.
Cora
Citeseer
PubMed
Methods
AUC
AP
AUC
AP
AUC
AP
SC
84.6.10.0
88.5.0.0
80,510.0
85.010.0
84.2.10.0
87.810.0
DeepWalk
83. 03.1
85.0=0.4
80.5+0.5
83.6+0.4
84,4+0.4
84.1
GAR
91.0++05
92.0-0.4
89.5+0.3
89.9+0.4
96,4+0.44
96.5+00.5
VGAE
91.4:1..5
92.6=0.4
90.8+0.4
92.0=0.3
94.410.55
94.7=104
ARGA
92.4+t0.4
93.2=0.3
91.9+0.5
93.0=#.4
96.8+0.3
97.1=0.5
ARVGA
92.4.10.4
92.620.4
92.410.5
93.010.3
96.510..5
96,810.4
GALA
92.1+:0.3
92.2=0.4
94.410.55
94,820.5
93.5=0.4
94,5=0.4
AGB
95.1.10.5
94.6 0.5
96.3
96.6100.4
94,3.10.3
93.5
NAFS-simple
91.9+0.0
93.1=000
94.1+0.0
95.2+0.0
97.4++0.0
97.2+0000
NAFS-mean
92.6+0.0
93.9
94,9+0.0
95.9+0.0
9..4++0.0
9..2
NAFS-max
93.0++.0
94.2=000
94.8+0.0
96.0=#.00
97.5=0000
97.1=0.0
NAFS-concat
92.6++.00
93.8-0.0
93.7+0.0
93.1++000
97.6+0.00
97.2+000
6 EXPERIMENTAL RESULTS
In this section, conduct extensive experiments evaluate the proposed NAFS. We first introduce the considered baseline methods, used datasets, and experimental settings. Then, we demonstrate the advantages of NAFS from the following three perspectives: (1) end-to-end comparison with the state-of-the-art methods, (2) scalability and efficiency, and (3) effectiveness along with ablation studies.
6.1 DATASETS AND BASELINE METHODS
Four widely-used network datasets (i.e., Cora, Citeseer, PubMed, and Wiki) are used in our experiments. In Cora and Citeseer, the node features are binary word vectors; while in PubMed and Wiki, each node has a TF-IDF weighted word vector. We include the properties of these datasets in Appendix B.I.
For different downstream tasks, the considered baselines are as follows:
Node clustering: GAE and VGAE (Kipf & Welling 2016b), MGAE (Wang et al. 2017). ARGA and ARVGA (Pan et al. 2018). AGC (Zhang al. 2019), DAEGC (Wang et al.)
2019), and AGE (Cui al. 2020).
Link prediction: Spectral Clustering (SC) (Ng et al. 2002), Deep Walk (Proozi et al. 2014), GAE and VGAE (Kipf & Welling 2016b), ARGA and ARVGA (Pan al. 20188)
GALA (Park et al. 2019). and AGE (Cui et al. 2020).
For NAFS, we investigate four variants: NAFS-simple, NAFS mean, NAFS-max, and NAFS-concat. NAFS-simple only contains the feature smoothing operation. Besides, only uses the smoothed features at maximal smoothing step K with r = 0.5 and excludes the node-adaptive strategy. And for NAFS-mean, -max, and -concat, they all have the complete NAFS framework and only differ in the ensemble strategy adopted in feature ensemble operation.
6.2 EXPERIMENTAL SETTINGS
Node Clustering. For the node clustering task, we apply K-Means (Hartigan & Wong/ 1979) to node embeddings get the clustering results. Three widely-used metrics are used for evaluation: Accuracy (ACC), Normalized Mutual Information (NMI), and Adjusted Rand Index (ARI).
Link Prediction. For the link prediction task, 5% and 10% edges are randomly reserved for the validation set and the test set. Once the node embeddings have been generated, we follow the same procedure as GAE to reconstruct the adjacency matrix. Two metrics Area Under Curve (AUC) and Average Precision (AP) are used in the evaluation the link prediction task.
Hyperparameters. When generating node embeddings, we use the values r in [0, 0.1, 0.2, 0.3, 0.4, 0.5] to get six different normalized adjacency matrix Å. The only exception is the link prediction task on the PubMed dataset, where values of in [0.3, 0.4, 0.5] instead. The optimal value of
7

---

Under review as a conference paper at ICLR 2022
Table 2: Node clustering performance comparison.
Cora
ACC
NMI
ARI
ACC
NMI
ARI
ACC
NMI
ART
ACC
NMI
GAE
53.3:002
40.7+00.3
50.5=0..2
41 3:.44
18.3=0.3
19.1+0.3
63.1+94
24940.3
21.7+0..
37.9=0.2
34.5=003
1899=02
VGAE
56.0:003
38.51004
34.::0.3
4.4:002
22.7:0.3
20.6:0.3
63.510..
25.01.0.4
20.1:0.2
45.1:0.4
46.8:103
26.3:04
MGAE
63,42005
45.6220.3
42.62004
6355204
39.720.4
42.520.
59,349.5
28.210.2
24.320.44
52.920.3
51,020.4
37,9.00.5
AREA
63.9+04
45.1+003
35 15..
07.500.5
35.2-0.3
34,0+0.4
68.0+0.
27.6+004
29.000.
18.1
34,5=0.3
11:2+04
ARVGA
64.010.5
44.9104
37.410.5
$14.0..
25.9.0.5
24.510.3
51,3104
11.7.0.3
7.8.0.2
38.710.4
33.9.0.4
10.71002
68.9203
53.720.3
43.620.3
6692005
41.1=0.4
4199205
098844
31.620.3
5184004
45.3:005
14,3204
DAROI
70.2+0.4
52.6+003
40.7+04
67.2-0.5
39.7-0.5
41.140.4
66.84-0.5
27.740.3
44.8-004
33.1+00.3
58.110.6
44.6.044
05/410.
69.910.5
31.110.6
Mimp-iimpl
50.++00
71.5 5-000
468+000
6300+00
27.9+0.0
43.1-0.
NATS mean
70.4100
56.6.100
08.0...00
718
45.1-00
37.6100
70.5100
33.910.00
332210,0
$466..0
19,1100
27.3100
NAFS mus
70.8:000
56.6:100
49 0.00
70 1:000
45.
44.7:00.
70.6:0.0
33.41...0
35.1:10.0
51 41.:000
45.8:000
25.5:000
NAFS-concal
75,4::0.9
58.0::0.0
53 83.0
71.1200
45.8:0.0
46.12000
70.5000
33,910.0
33.2:000
53.6:0.0
50.5:00.0
26.31:0.
1000
90.
100
68.6
Nomattad Woaat Latomattion
34.0
Running Time (6)
800
AGE
Spreddu
Neematowdd MuntuaadMMuuuu Mutual Tifee
33.8
600
60
33.0
33.6
400
32.0
Naive Average
Single Hop
23.4
Mean
only
Adeptive Weght
200
15.0
31.5
132
25:
254
23-4
23:1
10
30
33.0
15
20
25
30
40
Cora
Citeseer Detasets
Pubmed
Maximal Hop
Macciaal Hop
(a) Weighting strategies
(b) Ensemble strategies
Figure 4: Efficiency comparison on citation networks.
Figure 5: Ablation study.
the maximal smoothing steps ranges from 70. Hyperparameters for the baseline methods are tuned following the settings in their original paper. We run all the methods using 200 epochs and repeat 10 times on all the datasets, and report the mean value of each evaluation metric. The details of the experimental environment setting are in Appendix B.2
6.3 END-TO-END COMPARISON
Link Prediction. Table I shows the performance of different methods on the link prediction task. On the three datasets, the proposed NAFS consistently achieves the best or the second-best performance compared with all the baseline methods. Remarkably, although NAFS-simple falls behind the other NAFS variants on Cora and Citeseer, achieves state-of-the-ar performance on PubMed, and outperforms the current state-of-the-art method ARGA by 0.6% and 0.1% on AUC and AP, respectively.
Node Clustering. The node clustering results of each method are shown in Table Among three ensemble strategies, NAFS-coneat has the overall best performance across the three datasets, which also consistently outperforms the strongest baseline AGE. For example, the best of NAFS variants exceeds AGE by 2.6%. 1.8%, 0.7%, and 3.5% on Cora, Citeseer, PubMed, and Wiki, respectively. Although NAFS-concat has the overall best performance, it falls behind NAFS-meaa NAFS-max on some metrics of some datasets; and it needs more CPU memory to store the node embeddings and longer time for inference.
is quite interesting to find that the simplified version of NAFS, NAFS NAFS-simple, outperforms training- based GAE all the four datasets, and it even outperforms the current SOTA method, AGE, Citeseer. The competitive performance NAFS-simple further illustrates that it is possible to achieve decent performance on graphs with only feature smoothing without any training parameters.
6.4 EFFICIENCY AND SCALABILITY ANALYSIS
To validate the efficiency and scalability of NAFS, we compare it with GAE and AGE, measuring their overall running time for generating node embeddings. The comparison is conducted on the three citation networks. For fairness, all methods only use CPUs for computation. Figure showcases the results along with the speedup ratio of NAFS against AGE.
8

---

Under review as a conference paper at ICLR 2022
Results from Figure show that NAFS is significantly faster than the considered methods the three datasets. For example. NAFS is almost two magnitudes faster than AGE on the relatively large dataset PubMed. The high efficiency of NAFS is attributed to trainable parameters. while GAE and AGE are both training-based methods. Although AGE executes the feature smoothing step in advance, it adopts time-consuming ranking policy to select positive and negative examples. This alteration in AGE brings both superior performance and longer running time compared with GAE. In addition, we also include more details in Appendix C.2 NAFS (See Figure 6
to demonstrate the excellent scalability of
6.5 ABLATION STUDY
To thoroughly investigate the proposed NAFS, ablation studies on the node clustering task are designed to analyze the effectiveness of feature smoothing and feature ensemble in NAFS. The experiments are conducted on the PubMed dataset, and Normalized Mutual Information (NMI) is used to measure the performance. To interpret its effectiveness better, also visualize the node embedding in Appendix C.4
Different Weighting Strategies. In NAFS, we use adae-ade weight to average the smoothed features of different steps. Here we change the "Adaptive Weight" in our method to "Single Hop" (only the smoothed feature at the last smoothing step is reserved) and "Naive Average" (smoothed features at every smoothing step has equal weight) and evaluate their performance. Figure (5a) shows the performance of the three different weighting strategies.
From Figure 5(a) the weighting strategy "Single Hop" performs the worst among the three, since only makes use of the information at the last smoothing step, which could lead to the over-smoothing issue when the maximal smoothing step becomes large. On the other hand, the weighting strategy "Adaptive Weight" shows better performance than "Naive Average". Besides, when the number of maximal smoothing steps becomes large, the performance of "Naive Average" begins to drop, while "Adaptive Weight" does not. "Naive Average" assigns the same weight across all the different steps of smoothed features, which also leads to over-smoothing when it tries to exploit extremely deep structural information. Instead, by assigning adaptive weights, the "Adaptive Weight" strategy in NAFS could exploit such deep information and avoid the over-smoothing issue, thus improving the quality of the generated node embedding.
Different Ensemble Strategies. We use different ensemble strategies to obtain the final node embeddings in our proposed method NAFS, which include "Mean", "Max", and "Concat". To evaluate the impacts of these different ensemble strategies, we change the maximal smoothing step, K, from 15 40, and evaluate corresponding node clustering performance. For reference, the performance of NAFS without feature ensemble, "r=0.3 only" is also reported. The experimental results in Figure ((b) illustrate that at most times, "r=0.3 only" performs worse than others, which shows the effectiveness of the three different ensemble strategies. However, we limit the comparison within the ensemble strategies, the performance superiority unclear. In Table and [ we can also have that different ensemble strategies perform diversely across different datasets and tasks. It indicates that these three ensemble strategies all have necessities in their own way.
CONCLUSION
This paper presents NAFS, a novel graph representation learning method. Unlike other GNN- based approaches, NAFS focuses on improving the feature smoothing operation in the GNN layer and generate node embeddings in a training-free manner. NAFS proposes Node-Adaptive Feature Smoothing to generate smoothed features with adaptivity to each node's individual properties; it further employs feature ensemble to combine multiple smoothed features from diverse knowledge extractors effectively. Experiments results typical tasks demonstrate that NAFS performs comparably with or even outperforms the ofate-of-the-aar GNNs, and at the same time enjoys high efficiency and scalability where NAFS shows its absolute superiority.

---

Under review as a conference paper at ICLR 2022
8 REPRODUCIBILITY STATEMENT
The source code of NAFS can be found in Anonymous Github acciencer/Naat S/ To ensure reproducibility, we have provided the overview of datasets and baselines in Section 6. and Appendix B.I. The settings for each task and baseline can be found in Section 6.2 Our experimental environment is presented in Appendix B.2, and please refer to "README.md" in the Github repository for more reproduction details.
4open
REFERENCES
Sami Abu-EI-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg. and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learning. pp. 21-29. PMIR, 2019.
Deyu Bo, Xiao Wang, Chuan Shi, Meiqi Zhu, Emiao Lu, and Peng Cui. Structural deep clustering network. In Proceedings of The Web Conference 2020, pp. 1400-1410, 2020.
Aleksandar Bojchevski, Johannes Kliepera, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberczki, Michal Lukasik, and Stephan Günnemann. Scaling graph neural networks with approximate pagerank. In Proceedings of the 26th ACM SIGKDD International Conference 2020.
Knowledge Discovery & Data Mining, pp.
Sandro Cavallari, Vincent W Zheng, Hongyun Cai, Kevin Chen-Chuan Chang, and Erik Cambria. Learning community embedding with community detection and node embedding on graphs. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, pp. 377-386, 2017.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. arXiv preprint
2018.
Ming Chen, Zhewei Wei, Bolin Ding, Yaliang Li, Ye Yuan, Xiaoyong Du, and Ji-Rong Wen. Scalable graph neural networks via bidirectional propagation. arXiv preprint arXiv:2010. /5421, 2020.
Fan RK Chung and Fan Chung Graham. Spectral graph theory. Number 92, American Mathematical Soc., 1997.
Ganqu Cui, Jie Zhou, Cheng Yang. and Zhiyuan Liu. Adaptive graph encoder for attributed graph embedding. In SIGKDD, pp. 976-985. 2020.
Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004. / 2020.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855-864, 2016.
Aric Hagberg, Pieter Swart, and Daniel Chult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Lab,(LANL), Los Alamos, NM (United States), 2008
Will Hamilton, Zhitao Ying, and Jure Leskovec, Inductive representation learning on large graphs. In NIPS, pp. 1024-1034, 2017.
John A Hartigan and Manchek A Wong. Algorithm as 136: A k-means clustering algorithm. Journal of the royal statistical society. series c (applied statistics), 28(1):100-108, 1979.
Bhagya Hettige, Yuan-Fang Li, Weiqing Wang, and Wray Buntine. Gaussian embedding of large-scale attributed graphs. In Australasian Database Conference, pp. 134-146. Springer, 2020.
Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin Benson. Combining label propagation and simple models out perfforsssm graph neural networks. In International Conference Learning Representations, 2020.
10

---

Under review as a conference paper at ICLR 2022
Thomas N Kipf and Max Welling. Semi- supervised classification with graph convolutional networks. arxiv preprint 1oX9::66090020000 2016a.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.07300 2016b.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.059997, 2018.
Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. In Advances in Neural Information Processing Systems, pp. 15354-133660 2019.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for cumessupervised learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 338 348, 2020.
Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of feather: Homophily in social networks. Annual review of sociology, 27(1):415 2001.
Federico Monti, Karl Otness, and Michael M Bronstein. Motifnet: a motif-based graph convolutional network for directed graphs. In 2018 IEEE Data Science Workshop (DSW), pp. 225-228. IEEE, 2018.
Andrew Y Ng. Michael I Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. In Advances in neural information processing systems, pp. 849-856, 2002.
Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, Lina Yao, and Chengqi Zhang. Adversarially regularized graph autoencoder for graph embedding. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pp. 2609-2615, 2018
Jiwoong Park, Minsik Lee, Hyung Jin Chang, Kyuewang Lee, and Jin Young Choi. Symmetric graph convolutional autoencoder for unsupervised graph representation learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 6519-6528, 2019.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710, 2014.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: information network embedding. In Proceedings of the 24th international conference on world wide web, pp. 1067-1077, 2015.
Large-scale
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 911)), 2008.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710. 2017.
Wang, S Pan, R Hu, Long, Jiang, and Zhang. Attributed graph clustering: deep attentional embedding approach. In International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence, 2019.
Chun Wang, Shirui Pan, Guodong Long, Xingquan Zhu, and Jing Jiang. Mgae: autoencoder for graph clustering. In Proceedings of the 2017 ACM Conference on Information and Knowledge Management, pp. 889-898, 2017.
Marginalized graph
Daixin Wang, Peng Cui, and Wenwu Zhu. Structural deep network embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1225-1234, 2016.
11

---

Under review as a conference paper at ICLR 2022
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference on machine learning. pp. 6861-6871. PMLR, 2019.
Shiwen Wu, Yuanxing Zhang, Chengliang Gao, Kaigui Bian, and Bin Cui. Garg: anonymous recommendation of point-of-interest in mobile networks by graph convolution network. Data Science and Engineering. 5(4):433-447, 2020.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning graphs with jumping knowledge networks. In International Conference on Machine Learning, pp. 5453-5462. PMLR, 2018.
Cheng Yang, Zhiyuan Liu, Deli Zhao, Maosong Sun, and Edward Chang. Network representation learning with rich text information. In Twenty-fourth international joint conference artificial intelligence, 2015.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graphsaint: Graph sampling based inductive learning method. In International Conference on Learning Representations, 2019.
Wentao Zhang, Mingyu Yang, Zeang Sheng. Yang Li, Wen Ouyang, Yangyu Tao, Zhi Yang, and Bin Cui. Node dependent local smoothing for scalable graph learning. arXiv preprint arXiv:2110.14377 2021.
Xiaotong Zhang, Han Liu, Qimai Li, and Xiao Ming Wu. Attributed graph clustering via adaptive graph convolution. In 28th International Joint Conference on Artificial Intelligence, IJCAI 2019, pp. 4327-4333. International Joint Conferences on Artificial Intelligence, 2019.
Hao Zhu and Piotr Koniusz. Simple spectral graph convolution. International Conference on Learning Representations, 2021.
12

---

Under review as a conference paper at ICLR 2022
A THEORETICAL ANALYSIS
The essential kernel of NAFS is the Smoothing Weight, which determines the output results. We now analyze the factors affecting the value of Smoothing Weight. To simplify our analysis, we suppose = 0 in the normalized adjacency matrix and apply Euclidean distance as the distance function in Definition [3.]] Thus we have
(k( = 11[Axx] - [ x1
where || 112 symbols two-norm.
Theorem A.1. For any node in graph G, there always exists
Σ (d x
D.(k) S X
(8)
d
where d, = d, + d, = dj + 1, ||2ز|2 denotes the two-norm of the initial feature of node j. and 0 A2 < denotes the second largest eigenvalue of the normalized adjacency matrix A.
To prove Theorem A.I we introduce the following lemma Lemma A.2.
1
- (e:A
A de
(9)
where es denoles one-hot row vector with its 7th components as I and other components as O, X2 is the second largest eigenvalue of A and d, denotes the degree of node i plus I (to include itself).
d
= +1
The proof of Lemma A.2 be found in (Chung & Graham 1997). Next will prove Theorem
A.1
Proof. According to equation we can have that
D.(k) ||[Á X]: [À x 1112
A & e )
((e,A)); (e,A0), 2X²
(10)
Σ d
Σ X2
Σ (d11I
2h
de
where Xjp denotes the th feature of node j.
Based on Lemma A.2 we then consider the smoothing distance for weighted averaged embedding features to the station state.
II|Á x X]: x
(11)
Therefore there holds Theorem
n
Σ /=1
(d, X
D.(k) S Xb1
(12)
d,
13

---

Under review as a conference paper at ICLR 2022
" Σ (dj] as edr because it is independent with then Theorem A.1
We denote the constant
can be written as
edæ D((k) S 2/ V d:
(13)
We then analyze the factors affecting the Smoothing Weight on a specific node u. From Eq. 13 we know that the nodes with smaller degrees may have larger (k). Combined with definition 4.1 we infer that larger D; (R)) makes the max; (k)): more dominant after the softmax operation, causing that weighted average results depend more itself and its near neighbors. Inversely, for the nodes with smaller degrees, its result of weighted average depends more equally on all itself, its near neighbors, and its distant neighbors.
At the same time, the Smoothing Weight of the node in a sparser graph (A2 is positively relative with the sparsity of a graph) decays slower as k increases. Thus, the weighted average result depends more equally itself, its near neighbors and its distant neighbors. While for the nodes in a denser graph, the weighted average result depends more on its near neighbors and itself.
Prevent over-smoothing. Based on Theorem A.1 we then consider the smoothing distance for weighted averaged embedding features the station state:
K
wi(k) * [A*X], [À x/l2 =
(k( * ([Å* - [À x|)l2
R=
k=0
(k) ||[Á* xAxl
(14)
Σ
(x))) (1)))
k=
When (k) 1/(K + 1), which means the average option is non-weighted, we have
lim +00
Σ
wi))
D.(k)
lim K-00
Di(k)
K
K
1
cdx
< lim
K
K
di
(15)
km
1
1
A
+1
cdx
lim
K
K
1
X2
V
d,
causing over-smoothing When wi(k) D:(k)/(Et Di(()), let X = [A*X]: [A=
we
have:
K
wi (k) (0)
|| x
lim [X K Koo
x l1
(16)
In the real-world graphs, nodes have different initial features, thus there is little chance that the combination of node's neighboring features both lies in the opposite direction and is of the same norm of the node's initial feature. Suppose that there exits a constant e > satisfying
min (D.(0,, I|P ΣK
(k) x 2 for node we have:
(0)
2
J A
limg- EK D((k)
0
(17)
Thus we see that even K goes to infinity, we are able to prevent the node representations from reaching the stationary state (the distance bound depends the node degree d and the initial feature
14

---

Under review as a conference paper at ICLR 2022
Table 3: Overview of the datasets.
Dataset
Nodes
#Features
#Edges
#Classes
Cora
2,708
1,433
5,429
7
Citeseer
3,327
3,703
4,732
PubMed
19,717
500
44.338
3
Wiki
2,405
4,973
17,981
17
X,). Note that in practice the representation at k-th smoothing step ( achieves the stationary state much earlier than the infinity-th smoothing step we use in the theoretical analysis, so we use the softmax normalization in Equation 5 to produce slightly larger bias towards features with longer distances to the stationary state.
Node-adaptive weighting. The above analysis theoretically proved our weighting scheme is able to prevent over-smoothing as the smoothing step goes to infinity. We now show that another advantage of our method is that it can fully leverage the multiple features over different smooth steps in a node-adaptive manner, which different from the traditional routine of the smooth-bling and fixed scheme. Suppose that the feature of l step is not over-smoothed yet for a specific node i, i.e., the distance of (k) G > have:
wi(k) limg +00 E (k)
E1
E
>0
odn d.
(18)
We see that as long as the feature is not over-smoothed, our method will assign non-zero weight to the feature. Further, we see that the bound of weight can be affected by the over-smoothing distance of e; and degree d, of specific node, implying adaptive weighting strategy.
B DETAILS ON THE EXPERIMENTS
B.1 DATASETS DESCRIPTION
Cora, Citeseer, PubMed, and Wiki four popular network datasets. The first three (Kipf & Welling 2016b) are citation networks where nodes stand for research papers and an edge exists between node pair if one cites the other. Wiki (Yang et al., 2013) is webpage network where nodes stand for webpages and an edge exists between node pair if one links the other. Table 3 presents overview of these four datasets.
B.2 EXPERIMENTAL ENVIRONMENT
The experiments are conducted machine with Intel(R) Xeon(R) Gold 5120 CPU @ 2.20GHz, and a single NVIDIA TITAN RTX GPU with 24GB GPU memory. The operating system of the machine is Ubuntu 16.04. For software versions, use Python 3.6, Pytorch 1.7.1, and CUDA 10.1.
C ADDITIONAL EMPIRICAL RESULTS
C.I PERFORMANCE ON THE NODE CLASSIFICATION TASK
In this subsection, we further assess the quality of the node embeddings generated by NAFS by the evaluation on the node classification task. We follow the linear evaluation protocol, which applies a linear classifier (i.e., Logistic Regression) to the node embeddings to generate final prediction results. We choose GCN Kipf & Welling 2016a), JK-Net (Xu et al. 2018), C&S (Huang et al.) 2020), SGC (Wu et al. 2019), GAT (Veličković et al.) 2017)) PPRGo (Bojchevski et al. (020), APPNP (Klicpera al. 2018), and DAGNN (Liu al. 2020 comparison baselines the node classification task. Note that C&S our evaluation adopts MLP as the base model. The evaluation results three popular datasets, Cora, Citeseer, and PubMed, are provided in Table
The table shows that our method achieves comparable predictive accuracy as one of the sfate-of-thh-ar methods DAGNN, However, since the node embeddings generated before training, method
15

---

Under review as a conference paper at ICLR 2022
Table 4: Test accuracy on the node classification task.
Methods
Cora
Citeseer
PubMed
GCN
81.8+0.5
70.8
79.340.6
JK-Net
81.9=1.4
70.7#0.7
78.8+0.7
C&S
76.7+004
70.8+0.6
76.5+0.5
SGC
81.0=0.2
71.3+0.5
78.9
GAT
83.0+0.7
72.5+0.6
79.0+L0.3
PPRGo
82.410.3
71.340.5
80.0+0.44
APPNP
83.
71.8+0.5
79.7
DAGNN
84.4
73.3+0.6
00.5
NAFS-mean
84.2
73.
80.5
NAFS-max
83.8
73.440.6
80.4
NAFS-concat
84.1
73.5+0.4
80.3
Table 5: Scalablity comparison on sampled real-world graphs with different sample sizes.
Methods
10,000
20,000
30,000
50,000
100,000
GAE
10.2s
36.3s
OOM
OOM
OOM
AGE
68.5s
256.2s
727.7s
2315.7s
OOM
NAFS-mean
2.8s
6.5s
10.8s
13.8s
23.7s
avoids performing recursive feature smoothing at each training epoch and storing the entire adjacency matrix on GPU. In this way, our method is more scalable and efficient to apply on large graphs than most state-of-the-ar methods like DAGNN.
C.2 SCALABILITY COMPARISON ON SYNTHETIC GRAPHS
challenging task in today's graph learning is how get decent node embedding large graphs To test the scalability of our proposed NAFS, we use the Erdös-Rényi Rényi graph generator in the Python package NetworkX (Hagberg et al.) 2008) to generate artificial graphs of different sizes. The node sizes of the generated artificial graphs vary from 5,000 to 100,000, and the probability of an edge exists between two nodes is set 0.0001. The experiment settings are altered compared Sec. 6.c.6..4 [6.4] both GAE and AGE are trained on an NVIDIA TITAN RTX which has 24 GB of memory, since only using CPU to train being unacceptable on large graphs real-world applications.
The overall experiment results are shown in Figure Figure 6(a) shows more detailed comparison on relatively small artificial graphs whose node sizes range from 5,000 to 20,000. Besides, Figure ((b) shows that GAE encounters the out-of nodes, while AGE encounters the out-of-memory problem at graph size 80,000, Our proposed NAFS successfully carried out all the artificial graphs. On the artificial graph consists of 100,000 nodes, NAFS accomplishes the node embedding generation in 66.1 seconds, which less than the running time of AGE the artificial graph consists of 10,000 nodes, 80.9 seconds. The graph size limit of our proposed NAFS is bounded by the CPU memory size. As long as one can successfully execute the multiplication of the sparse adjacency matrix and the feature matrix, NAFS can then be implemented.
problem the artificial graph composed of 30,000
C.3 SCALABILITY COMPARISON ON REAL-WORLD GRAPHS.
To verify the scalability advantage of NAFS, we also add the evaluation on real-world datasets. Concretely, sample subgraphs of different scales from the full ogbn-product graphs via uniformly random node selection and then report the sampled graph size (i.e., number of nodes) and the corresponding runtime (seconds) in Table The experimental results show that NAFS support
16

---

Under review as a conference paper at ICLR 2022
50
10
NAFS
43.8
Running Time (s)
400
GAE
381.2
40
100
GAE
300
AGE
28
30
Speedup
Running Time
NAFS
AGE
10a
200
18.6
20
100M
11,5
10
100
80.9
10
1.94.12
21.8
4.311.0
6.9
8.7
38.3
5000
10000
15000
20000
20000
40000 60000
80000 100000
Graph Size
Graph Size
Figure 6: Scalablity comparison on synthetic graphs, OOM is "out of memory".
larger graphs (i.e., larger than 30,000 nodes). Besides, it is significantly faster than the compared baselines, especially for large graph datasets.
C.4 VISUALIZATION OF EMBEDDING
(a) original
(b) our 5
(c) our 10
(d) 20
(e) 50
(f) 100
(g) 150
(h) 200
(i) original
only
(k) only 10
()) only 20
(m) only (n) only 100 (o) only 150 (p) only 200
Figure 7: T-SNE visualization of node embedding on Cora.
To better understand why NAFS is effective, we visualize the node embedding generated by NAFS using T-SNE (Van der Maaten & Hinton| (0088) on the Cora dataset. Moreover, we also visualize the node embedding of A & XX for reference. All the visualization results are shown in Figure 7 The first row is the results our proposed NAFS, and the second row the results of A
Figure 7(c) and 7(k) illustrate that at hop 10, the node embedding produced by NAFS and A are both distinguishable. But as the value of maximal smoothing step becomes larger, the node embedding of A X falls into total disorder, like the situation showed by Figure. 7(n) 7(o) and 7(p) At the same time, NAFS able to maintain the distinguishable results even when the value the maximal number of smoothing step increases to 200.
D MORE DETAILS OF NAFS
D.1 PSEUDO CODE OF NAFS
Alg. I shows the whole pipeline of our proposed NAFS. We first initialize ( the original feature matrix X. Given the normalization parameter rt, we obtained the corresponding normalized adjacency matrix A, = - ÄD r, which acts as knowledge extractors (line 4). After that, for each node,
E.q. to calculate the Over-smoothing Distance with all the & ranging from 0 to K (line 6, 7). Then we calculate its Aggregation Weights through Eq. 5 (line 8, 9). After obtaining Aggregation Weights with all i and we construct the Aggregation Weight matrix for each k with
17

---

Under review as a conference paper at ICLR 2022
Algorithm 1: NAFS pipeline.
Input: Smoothing step K, feature matrix X. adjacency matrix A, and (2., rT}.
Output: Graph embedding matrix Z.
Initialize the feature matrix X = X;
Operation 1: Feature Smoothing
for 1 S < 'T' do
Update the normalized adjacency matrix A,, D AP--AAD"1 for 1 I i S. do
for 0 O K do
Calculate Di(k) and w; (k) with Eq. and respectively;
for 0 S & K do Construct ((k) with Eq. 6
K
Smooth the node features X with (t)
Σ W
10
k=
11
Operation 2: Feature Ensemble
Compute the final embedding Z with Z + @iE (1,2,..... T
Eq. (line 10, 11). Next, we compute the NAFS output X with x0 W(H)A (line 12).
Finally, we compute the final embedding result of all t through Z +- @ie ry x (line 14).
D.2 MOTIVATION OF FEATURE ENSEMBLE
Adopting different smoothing operators in the feature smoothing operation (the normalized adjacency matrix A in Eq. 1 is equivalent to smoothing features in different manners. Other than the normalized adjacency matrix Å, there are many alternatives that have been proposed recently. For example, GraphSAGE (Hamilton et al., 2017) designs three smoothing operators (i.c., Mcan, LSTM and Pooling) to flexibly capture the information of neighboring nodes. SIGN (Frasca et al. 2020) enriches the smoothing operators with Praoonalize-PaaeRankke based (Monti et al.) 2018) adjacency matrices. However, these methods are not designed for graph representation learning and different smoothing operators may results in diverse smoothed features. For better node representation, feature ensemble is used to combine the smoothed feature under different smoothing operators.
(Klicpera et al.] (219)) and triangle-
D.3 RELATIONS WITH OTHER SCALABLE GNN ARCHITECTURES
The scalable GNNs can be roughly classified into two categories: (a) "first propagate then predict": (b) sampling ordinary GNN. The first category includes famous GNN models like SGC (Wul et al.] 2019) and SIGN (Frasca al. 2020). They disentangles the coupled propagation and transformation operations traditional GCN layers (Kipf & Welling 2016a), and exccute all the propagation operations preprocessing. The most representative GNN model of the second category GraphSAGE (Hamilton et al. 2017). ), and many other works have been proposed following it, like FastGCN (Chen al. (018)) and GraphSAINT (Zeng al. 2019). The main contribution of these works are effective sampling strategies that can preserve the most valuable information from the original graph. The sampling strategies always act as plug-and-play module, and can be combined with ordinary GNNs, which allows the latter to perform on large-scale graphs. GNNs belong to the "first propagate then predict" category usually enjoy higher efficiency since they avoid recursively performing propagation in each training epoch. Our proposed NAFS belongs to the "first propagate then predict" category.
D.4 ADVANTAGE DISTRIBUTED SETTINGS
NAFS can also be adapted to the distributed environment. The feature smoothing process in NAFS are sparse matrix dense matrix multiplications, which have mature implementations in distributed environments. Besides, this process only need be pre-computed once. In contrast, during
18

---

Under review as a conference paper at ICLR 2022
each training iteration of GAE and its variants, each node needs to repeatedly pull the intermediate representations of other nodes, which leads to high communication cost.
19


Reviews:
[{"review_id": "tZHz1pgNNgy", "reviewer": "Reviewer_w2Qg", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors took a novel perspective and presented NAFS which does not explicitly require parameter learning. It is also a bold idea that, in addition to separate feature transformation from feature smoothing, the model removes feature transformation altogether. \n\nA few questions:\n1. Since the method has no feature transformation step, the construction of node feature in the initial step seems to become rather important. What are the features used for each of the dataset in the experiment (Cora, Citeseer, PubMed, Wiki)? I would be good to state them clearly in the paper. \n\n2. Would be useful to comment on what the authors think might be the limitation of this method. For example, NAFS by design does not require task specific training, although hyper-parameter tuning allow the model to serve for different tasks. Then what types of graphs/tasks might work best with this model, or is it indifferent.\n", "summary_of_the_paper": "The authors of this paper took a novel perspective to present the node-adaptive feature smoothing (NAFS) algorithm, which generates node embeddings without explicit training/parameter learning. The method first performs feature smoothing, then combines the smoothed features using adaptive weights which are node-specific. They further enhanced this method by ensembling the smoothed features extracted with different hyper-parameters. The authors have conducted many experiments to validate the model performance, and demonstrate the model's efficiency empirically. ", "summary_of_the_review": "In summary, the paper is well presented. The motivations and the authors' insights to this model is well explained. The method is clearly described. The authors performed many experiments to validate the model's performance, with additional ablation studies. Would be nice to have more discussion on which scenarios the model works better/worse.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "QkBl6Emo9fX", "reviewer": "Reviewer_SHxg", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper tackles the problem of over-smoothing by proposing a method to differently weight the smoothing for each node. The problem is well known and in my opinion methods to better understand and solve it are very relevant for the community.\n\n**Positive aspects**\n\nWhile the connection of over-smoothing with powers of the adjacency matrix is not novel per se, I did not know about prior methods tackling the problem as it has been done in this paper. However, I should highlight that just recently another **very** similar paper was published on arxiv (Zhang et Al. \"Node Dependent Local Smoothing for Scalable Graph Learning\" https://arxiv.org/abs/2110.14377 ). While it seems recent enough to not put the contribute of this paper into discussion, I think it would be worth citing it and comparing its method to the presented one.\n\nThe approach is presented quite clearly and in a well-structured way. I appreciate that the authors introduce it as a baseline: better results might be obtained by adding a learning component to it, but it is interesting to see how far adaptive smoothing alone can go.\n\n**Main concerns and chances for improvement**\n\nBy being introduced as parameterless, NAFS is compared with other methods (autoencoders, adversarial models) which are typically unsupervised. Moreover, the only supervised task it is tested on is the link prediction one. I think further experiments are required to better understand how useful the method can be. In particular, I think it would be interesting to see how it performs on other supervised tasks such as node classification (e.g. suing the linear evaluation protocol, used to assess the performances of many recent graph SSL methods).\n\nThe weighting scheme looks intuitively useful, but I believe it would be useful to understand how it actually impacts final representations from a more theoretical perspective. How do weights change node representations from converging to the same identical one? \n\nFew minor corrections:\n- page 1: \"and these methods share two major limitations\" (\"and\" looks superfluous)\n- page 2: $\\hat{A} = A + I_n$ should be $\\tilde{A} = A + I_n$\n- the $r$ convolution coefficient which is introduced in Section 4.2 previously appears in Equation (1) and this makes the equation less clear. I think it would be easier for the reader to have its description close to (1) instead. \n", "summary_of_the_paper": "The paper presents NAFS (Node-Adaptive Feature Smoothing), a method that constructs node representations by relying on smoothing only, i.e. without parameter learning. To do this, the authors first provide a formulation for the smoothing operator after infinite steps, i.e. when the stationary state is reached. They then define over-smoothing distance as a way to assess how much a node is close to the stationary state after k smoothing steps. Finally, they use over-smoothing distances to calculate a different smoothing weight for each node.\n\nExperiments show that representations obtained by smoothing with these weights, together with feature ensembles obtained by applying different convolution coefficients, provide performances in clustering and link prediction tasks which are comparable, if not better, than many other state-of-the-art approaches.", "summary_of_the_review": "The paper tackles an interesting problem in a clear and reasonable way. The main issues I see here are the evaluation, that to me still looks quite limited, and the lack of a theoretical interpretation for the weighting scheme.\n\nWhile a possibly negative outcome of the evaluation of a node classification task does not concern me too much (the method itself is defined as a baseline and I think it does not require to be state-of-the-art in every single benchmark for it to be valuable), I think motivating the weighting scheme by formally demonstrating how it impacts smoothing when $K$ grows is an important step to make the paper more convincing.\n\n----\nI have read the authors' replies to the other reviewers and myself and they look convincing to me. I particularly appreciate they addressed my comments on related works, theoretical analysis, and further experiments on supervised tasks. They also took care of adding mean/std results for both new and old experiments (even when results are deterministic, which is great to emphasize). This makes the paper way more convincing in my opinion and worth being accepted, which is why I increased my score accordingly.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "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": "-Cbe1lWgS9H", "reviewer": "Reviewer_YM4P", "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": "**Strengths:**\n1. Simple approach that seems to work well\n2. Well-presented and easy to read\n3. Rather large set of baseline methods used\n\n**Weaknesses** \n1. Old, small-scale datasets\n2. No error bars/standard deviations were reported \n3. Scalability experiments only carried out on synthetic graphs\n\n**Suggestion**\n1. Evaluate the method on more large-scale, modern datasets, e.g. OGB datasets or graphlearning.io\n2. Perform scalability on real-world datasets \n3. Discuss \"linear\" GNN architectures, e.g., https://arxiv.org/abs/1810.05997\n4. Discuss other scalable GNN alternatives, e.g., ones based on label propagation, see https://arxiv.org/abs/2010.13993\n\n**Comments**\n1.  The discussion in section 2.2 only applies to a specific GNN layer, namely GCN \n\n**Question**\n1. Is your approach also liftable to other GNN architectures besides GCN?\n\n", "summary_of_the_paper": "The paper deals with (unsupervised) learning with graphs, specifically node-level tasks. Inspired by spectral GNNs, specifically Graph Convolutional Networks (GCN), the authors propose a simple neighborhood smoothing technique to capture the graph structure around each node in the given graph. Contrary to GNN, the proposed algorithm is parameter-free and hence scales better than their end-to-end trained GNN counterpart.                    \n\nMotivated by the problem of over-smoothing of GCN (Li et al., 2018), they propose the so-called \"over-smoothing distance\" measuring how close a node's feature is to be over-smoothed, which is simply the row-wise distance between $A^k X$ and $A^{\\infty}X$ with regard to the Euclidian distance, see Def. 3.1. Based on this distance they define the smoothing weight matrix which is then used to weight the neighboring node features during neighborhood aggregation. The resulting features $\\hat{X}$ are computed as $\\hat{X} =  \\sum^{K}_{k=0} W(k)\\hat{A}X$, where $W(k)$ is the $k$th smoothing weight matrix.\n\nThe proposed architecture is evaluated on standard, old, small-scale (unsupervsied) link and node classification (Cora, Citeseer, PubMed) tasks showing somewhat classification performance while showing a considerable speedup in computation time. ", "summary_of_the_review": "The approach is very simple, it offers no significant theoretical or methodological contributions, and the experimental study is not executed well enough, i.e., it only uses small-scale, old or synthetic datasets. Further, the are some problems in the experimental protocol, e.g., no standard deviations are reported. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes NAFS (Node-Adaptive Feature Smoothing), which constructs node representations by only using smoothing without parameter learning.  The authors first provide a formulation for the smoothing operator. They then define over-smoothing distance to assess how much a node is close to the stationary state. Finally, they use the over-smoothing distance to calculate a smoothing weight for each node. Experiments are conducted to verify the efficacy.

Strength
* The paper tackles the problem of over-smoothing, which is a well-known issue in GNN.
* The solution appears to be effective. 
* The paper is generally clearly written.

Weakness
* The novelty and significance of the work might not be enough. Aspects of the contributions exist in prior work.

---

Additional experiments have been conducted during the rebuttal. The reviewers appreciate the efforts.

After rebuttal：

Reviewer SHxg increased the score accordingly.

Reviewer w2Qg says “Given the concerns proposed by the other reviewers, I adjusted my score.”

Reviewer YM4P says “I read the rebuttal and slightly increased my score.”
Decision: Reject