Generalizing Graph Convolutional Networks via Heat Kernel
Authors: Jialin Zhao
Yuxiao Dong
Jie Tang
Ming Ding
Kuansan Wang
Venue:  (2021)
Keywords: graph networks

Abstract: Graph convolutional networks (GCNs) have emerged as a powerful framework for mining and learning with graphs. A recent study shows that GCNs can be simplified as a linear model by removing nonlinearities and weight matrices across all consecutive layers, resulting the simple graph convolution (SGC) model. In this paper, we aim to understand GCNs and generalize SGC as a linear model via heat kernel (HKGCN), which acts as a low-pass filter on graphs and enables the aggregation of information from extremely large receptive fields. We theoretically show that HKGCN is in nature a continuous propagation model and GCNs without nonlinearities (i.e., SGC) are the discrete versions of it. Its low-pass filter and continuity properties facilitate the fast and smooth convergence of feature propagation. Experiments on million-scale networks show that the linear HKGCN model not only achieves consistently better results than SGC but also can match or even beat advanced GCN models, while maintaining SGC’s superiority in efficiency.

Under review as a conference paper at ICLR 2021
GENERALIZING GRAPH CONVOLUTIONAL NETWORKS VIA HEAT KERNEL
Anonymous authors Paper under double-blind review
ABSTRACT
Graph convolutional networks (GCNs) have emerged as powerful framework for mining and learning with graphs. A recent study shows that GCNs can be simplified as linear model by removing nonlinearities and weight matrices across all consecutive layers, resulting the simple graph convolution (SGC) model. In this paper, we aim to understand GCNs and generalize SGC linear model via heat kernel (HKGCN), which acts as a low-pass filter on graphs and enables the aggregation of information from extremely large receptive fields. We theoretically show that HKGCN is in nature continuous propagation model and GCNs without nonlincarities (i.e., SGC) are the discrete versions of it. Its low-pass filter and con- tinuity properties facilitate the fast and smooth convergence of feature propagation. Experiments on million-scale networks show that the linear HKGCN model not only achieves consistently better results than SGC but also can match or even beat advanced GCN models, while maintaining SGC's superiority in efficiency.
INTRODUCTION
Graph neural networks (GNNs) have emerged as powerful framework for modeling structured and relational data (Gori et al. 2005 Scarselli et al.] [2008] Gilmer et al., 2017 Kipf & Welling) (017)) A wide range of graph mining tasks and applications have benefited from its recent emergence, such as node classification (Kipf & Welling 2017 Veličković et al. 2018). link inference (Zhang & Chen 2018 Ying et al. 2018), and graph classification (Xu et al. 2019b).
The core procedure of GNNs is the (discrete) feature propagation operation, which propagates information between nodes layer by layer based on rules derived from the graph structures. Take the graph convolutional network (GCN) (Kipi' & Welling 2017) for example, its propagation is performed through the normalized Laplacian of the input graph. Such a procedure usually involves 1) the non-linear feature transformation, commonly operated by the activation function such as ReLU, and 2) the discrete propagation layer by layer. Over the course of its development, various efforts have been devoted to advancing the propagation based architecture, such incorporating self-attention in GAT (Veličković et al., (2188, mixing high-order neighborhoods in MixHop (Abu- Elu-El-Bn El-Haija et al. 2019. and leveraging graphical models in GMNN (Qu et al.) 2019).
Recently, Wu et al. (Wu et al. 2019) observe that the non-linear part of GCNs' feature propagation actually associated with excess complexity and redundant operations. To that end, they simplify GCNs into linear model SGC by removing all non- non-linearities between consecutive GCN layers. Surprisingly, SGC offers comparable or even better performance to advanced GCN models, based on which they argue that instead of the non-linear feature transformation, the repeated graph propagation may contribute the most to the expressive power of GCNs.
Though interesting results generated, SGC still inherits the discrete nature of GCNs' propagation, which can lead to strong oscillations during the procedure. Take, for example, a simple graph of & x² 2 and one weighted edge
two nodes i and 82 with one-dimension input features between them, the feature updates Ø; and T2 during the GCN propagation is shown in Figure [ (a), from which we can clearly observe the oscillations of 2ı and z2 step by step. This indicates that though the features from multi-hops away may seem to be taken into consideration during the GCN propagation, is still far away to learn patterns from them.

---

Under review as a conference paper at ICLR 2021
In this work, we aim to generalize GCNs into continuous and linear propagation model, which is referred to as HKGCN. We derive inspiration from Newton's 's law of cooling by assuming graph feature propagation follow similar process. Straightforwardly. this leads us to leverage heat kernel for feature propagation in HKGCN. Theoretically, we show that the propagation matrix of GCNs is equivalent to the finite difference version of the heat kernel. In other words, using heat kernel as the propagation matrix will lead to smooth feature convergence. In the same example above, we show the heat kernel based propagation in HKGCN can prevent oscillations, as illustrated in Figure T (b). Finally, from the graph spectral perspective, heat kernel acts as towpass filter and the cutoff frequency of heat kernel can be adjusted by changing the propagation time.
Empirically, we demonstrate the per- formance of HKGCN for both trans- ductive and inductive semi-supervised node classification tasks. The exper- iments are conducted on both tradi- tional GNN datasets, such as Cora, CiteSeer, Pubmed, and Reddit, and latest graph benchmark data indexed by Open Graph Benchmark (Hu et al.) 2020). The results suggest that the simple and línear HKGCN model can consistently outperform SGC on all six datasets and match or even beat the performance of advanced graph neural networks on both tasks, while at the same time maintaining the order-of -oarr-ff--mgiiuuee efficiency superiority inherited from SGC.
2.0
2.0
XL
X1
1.8
1.8-
Festure
1.6
Feature
1.6
1.4
1.4
1.2
1.2
1.0
Propagation Step (O
Propegation Time
GCN
(b) HKGCN
Figure 1:
Feature propagation under GCN and HKGCN.
2 RELATED WORK
Graph Neural Networks. Graph neural networks (GNNs) have emerged as a new paradigm for graph mining and learning, significant progresses have been made in recent years. Notably, the spectral graph convolutional network (Bruna et al.] 2013) is among the first to directly use back propagation learn the kernel filter, but this has the shortcoming of high time complexity. Another work shows how to use Chebyshev polynomial approximation to fast compute the filter kernel (Hammond et al., (01T). Attempts further this direction leverage Chebyshev Expansion to achieve the same linear computational complexity classical CNNs (Defferrard et al.) 2016). Later, the graph convolutional network (GCN) (Kipt & Welling| 2017) simplities the filter kernel to the second-order of Chebyshev Expansion, inspiring various advancements in GNNs. GAT brings the attention mechanisms into graph neural networks (Veličković et al., 2018). GMNN combines the benefits of statistical relational learning and GNNs into unified framework (Qu al. 2019). To enable fast and scalable GNN training, FastGCN interprets graph convolutions as integral transforms of features and thus uses Monte Carlo method to simulate the feature propagation step (Chen et al.) 2018). GraphSage treats the feature propagation as the aggregation from (sampled) neighborhoods (Hamilton et al. 2017). LADIES (Zou et al. 2019) further introduces the layer-dependent importance sampling technique for efficient training.
Recently, there are also research efforts devoting on the theoretical or deep understanding of GCNs (Xu et al. 2019b; Battaglia et al. 2018). For example, the feature propagation in GNNs can be also explained neural message passing (Gilmer al., 2017). In addition, studies also find that the performance of GNNs decreases with more and more layers, known as the smor-hhn issue (Li al. 2018 Zhao & Akoglu 2020). To reduce GCNs' complexity, SGC turns the GCN model into a linear model by removing the nin-lr activation operations between consecutive GCN layers (Wu)
et al.
2019), producing promising results terms of both efficacy and efficiency.
Heat Kernel. The properties of heat kernel for graphs are reviewed in detail by Chuang in (Chung & Graham 1997.. Recently, heat kernel has been frequently used as the feature propagation modulator.
In (Kondor & Lafferty 2002), the authors show that heat kernel can be regarded as the discretization of the familiar Gaussian kernel of Euclidean space. Additionally, heat kernel is often used as the window function for windowed graph Fourier transform (Shuman et al., 2016). In (Zhang al. 2019), the second-order heat kernel is used as the band-pass filter kernel to amplify local and global structural information for network representation learning.
2

---

Under review as a conference paper at ICLR 2021
Concurrent work. Several recent works have developed similar idea. (Poli et al. 2020 Zhuang ct al. 2020) use the Neural ODE framework and parametrize the derivative function using a or layer GNN directly. (Xhonneux et al. 2020) improved ODE by developing a continuous message- passing layer. All ODE models make feature converge to stable point by adding residual connection. In contrast, our model outputs intermediate state of feature, which is balance between local and global features. Some recent works (Xu et al., 2019a Klicpera et al., 2019) propose to leverage heat kernel enhance frweereuency filters and enforce smooth feature propagation. However, they do not realize the relationship between the feature propagation of GCNs and heat kernel.
GENERALIZING (SIMPLE) GRAPH CONVOLUTION VIA HEAT KERNEL
3.1 PROBLEM AND BACKGROUND
We focus on the problem of uumi-supervised node classification on graphs, which is the same as GCN (Kipf & Welling 2017). Without loss of generality, the input to this problem is an undirected network G EV, where V denotes the node set of nodes {Ui,..., Un and E represents the edge set. The symmetric adjacency matrix of G is defined as A and its diagonal degree matrix as D with D,; = -, Aig. For each node U; E V, it is associated with feature vector x E X E Raxd
and a one-hot label vector yi Y E [0,1)"XC where C is the number of classes. The problem setting of semi-supervised graph learning is given the labels Yz of a subset of nodes Vz, to infer the labels YU of the remaining nodes Vv. where Vu= V.
Graph Convolutional Networks. Given the input graph G = EV with A. D, X. and YL. GCN can be understood as feature propagation over the graph structure. Specifically, it follows the following propagation rule:
H (+11 oD 1 AD "
(I)
where À = A + In the adjacency matrix with additional self-connections with IN as the identity matrix, (1)) is trainable weight matrix in the 7 layer, (-) a nonlinear function such as ReLU, and ( denotes the hidden node representation in the 1th layer with the first layer H X.
The essence of GCN is that each GCN layer is equivalent to the first-order Chebyshev expansion of spectral convolution (Kipf & Welling 2017). It also assumes that the first-order coefficient a is equal to the 0-th order coefficient dg multiplied by i.. aj = -ap. We will later prove that this just discrete solution of heat equation.
Simple Graph Convolution. Since its inception, GCNs have drawn tremendous attention from researchers (Chen et al. 2018, Veličkovćć et al., 2018 Qu et al. 2019). A recent study shows that GCNs can be simplified as the Simple Graph Convolution (SGC) model by simply removing the nonlinearities between GCN layers (Wu et al. 2019). Specifically, the SGC model is a linear model and can be formalized by the following propagation rule:
safbmaz (DD AD XW)
(2)
Surprisingly, the linear SGC model yields comparable prediction accuracy to the sophisticated GCN models in various downstream tasks, with significant advantages in efficiency and scalability due to its simplicity.
Heat Equation and Heat Kernel. The heat equation, special case of the diffusion equation, is used to describe how heat distributes and flows over time (Widder & Vernon 1976).
Image a scenario of graph, in which each node has temperature and heat energy could only transfer along the edge between connected nodes, and the heat propagation on this graph follows Newton's law of cooling. So the heat propagation between node 2 and node ty should be proportional to 1) the edge weight and 2) the temperature difference between U; and ey. Let x(" denote the temperature of iy at time the heat diffusion on graph G can be described by the following heat equation:
dx
= k Σ (x - x(0) = =DDD,x -- - EAyx
(3)
dt
3

---

Under review as a conference paper at ICLR 2021
The equation under the matrix form ex" (LX( where = A is the graph Laplacian matrix. By reparameterizing and k into single term t' = kt, the equation can be rewritten as:
dt
dx(+) du'
Lxx(')
(4)
A heat kernel is the fundamental solution of the heat equation (Chung & Graham 1997). kernel H, is defined to be the n X n matrix:
The heat
H T.
(5)
Given the initial status ( X, the solution to the heat equation in Eq. can be written as
x H.X
Naturally, the heat kernel can be used as the feature propagation matrix in GCNs.
3.2 CONNECTING GCN AND SGC TO HEAT KERNEL
GCN's feature propagation follows D 1 AD- through which node features diffuse over graphs. Note that the feature propagation in GCN is just step each time/layer, hindering individual nodes from learning global information. By analogy with the heat diffusion process on graphs, the heat kernel solution also be perfectly generalized the feature propagation in the graph convolution.
Instead of using L, we follow GCN to use the symmetric normalized Laplacian L = -- D AD to replace it. According to SGC (Wu et al. 2019), this convert also serves as a low-pass-type filter in graph spectral. Then we have Eq. as
Lx(() and the heat kernel in Eq. 5 as H, e Lt Consider the finite difference of this heat equation, could be written as:
dx de
X((+00
x
-
we set At = 1, we have ( propagation rule in Eq. [ In other words, each layer of GCN's feature propagation on graphs is equal to the finite difference of the heat kernel. we consider the multilayer GCN without the activation
(+)
Lx( = AD- ((), This is the same feature
function, could be written as SGC Wu et al. p019): Y soflmaz((B= 2) XW), where
Y is the classification result and W is the merged weight matrix. Using the finite difference of heat equation above, can be rewritten as:
Y softmar(X(XX (K)))
(8)
which is still multistep finite difference approximation of the heat kernel.
Reduce At. Assuming can be divided by At, the number of iterations is n, 1. making Eq.
become X (I - -AtL) X. By fixing 1, we have
(1) (I 1 L))
X
ni
(n:
L
(-1)"in,1
L
nu! X
n
n2
2!
n2
Therefore, n, iterations of approximate to Taylor expansion of the heat kernel order n,, So GCN could also be seen as the first-order Taylor expansion of the heat kernel.
3.3 HEAT KERNEL AS FEATURE PROPAGATION
We have shown that the feature propagation in GCN is a multistep finite difference approximation of the heat kernel. Next, we briefly illustrate the advantage of differentiation.
case study. We illustrate how the features are updated during the GCN and heat kernel propaga- tions. Let us consider graph of two nodes and 222 with one-dimension input features x; 1 and X₂ = 2 and one weighted edge A = A21 = between them. Recall that with At = GCN is equivalent to the finite difference of the heat kernel. Thus, set At for the heat kernel well.
4

---

Under review as a conference paper at ICLR 2021
The updates of x2 and X2 the propagation step t increases shown in Figure We observe that heat kernel shows much smoother and faster convergence than GCN.
In GCN, the discrete propagation D DD layer by layer causes node features to keep oscillating around the convergence point. The reason lies in GCN's ' requirement for At = which is too large to have a smooth convergence. Straightforwardly. the oscillating nature of GCN's feature propagation makes it sensitive hyperrparameters and generate weak performance large graphs. Theoretical analysis is given in Section 3.5
3.4 GENERALIZING GRAPH CONVOLUTIOON
We have shown that the feature propagation in GCN is merely the solution of the finite difference version of the heat equation when Át 1. As result, using heat kernel as feature propagation can lead to smooth convergence. Since the range of t is in real number field, the propagation time in heat kernel can be seen as a generalized parameter of the number of layers in GCN (Kipí & Welling 2017) and SGC (Wu et al. 2019). The advantage of heat kernel also includes that t can change smoothly compared to the discrete parameters.
In light of this, propose generalize graph convolution networks by using heat kernel and present the HKGCN model. Specifically, we simply use the one layer linear model:
= softmar X W) = softmar(e" (L))
(10)
where W the n C feature transformation weight and f can a learnable scalar or a preset hyper-parameter.
Using preset i converts HKGCN 1) pre-processing step X e( without parameters and 2) linear logistic regression classifier Y = softmar((X) This makes the training speed much faster than GCN. The algorithm of presetting is Appendix (Algorithm 1).
To avoid eigendecomposition, we use Chebyshev expansion to calculate e Hammond et al. 2011 Zhang et al. 2 The first kind Chebyshev polynomials are defined as Ti+1 (x) 2x
T-)(2) with (x) = and Ti (x) = x. The requirement of the Chebyshev polynomial is that x should be in the range of [-1, 1]. however, the eigenvalues of L satisfy 0 = λo S S An S 2. To make the eigenvalues of L fall in the range of [-1, 1], we convert L to L L/2. In addition, we reparameterize / to / = 21 so that the heat kernel keeps in the original form. In doing so, we have
(
Σ (1))(()
(11)
And the coefficient e; of the Chebyshev expansion can be obtained by:
3 //1 Ti(z)e de = B(-)
(1) =
(12)
v1
where when i i otherwise 8 = 2, and (i is the modified Bessel function of the first
kind (Andrews & of Photo-optical Instrumentation Engineers 1998). By combining Eqs. [] and 12 together, we can have el L() approximated as:
Li) Bo(t)T((L) + Σ (-1yB,
(13)
3.5 SPECTRAL ANALYSIS
From the graph spectral perspective, heat kernel acts as a low-pass filter (Xu et al., 2019a). In addition, as the propagation time increases, the cutoff frequency decreases, smoothing the feature propagation.
Graph Spectral Review. We define A diag (ai.g(A,,...,,..) An) as the diagonal matrix of eigenvalues of i. and U (i, ...; Un) the corresponding eigenvectors, that is, L UAUT.
5

---

Under review as a conference paper at ICLR 2021
1,0
9W1
0.0
-1
0.5
0.5
2.0
1000
2000
Index of
(a) g(A)
(b) g(A) Cora
Figure 2: Effects of different kernels.
The graph Fourier transform defines that & - U is the frequency speetrum of x, with the inverse operation Ux. And the graph convolution between the kernel filter g(-) and x is g x*x= Ug(A)U*> x with g(A) = diag(o(Az), (((n))
For polynomial g(L), we have g(L) Ug(A)UT. This can be verified by setting g(>:) Σ N,X that is, Ug(A)UT U a = =oz
"UA-U -Eoo a, g[L).
Heat Kernel. As (L) Ug(A)U?, the heat kernel H. =e e-- Ei= It'LL could also be seen as polynomial L. Thus its kernel filter g(A;) = E Adt Note that the eigenvalues of L is in the range of [0, 2). For Ji,j, if A < Aj. we have g(2.)
s(2,) = elAo-dile > 1. Thus 9(A,) > g(A)).
Heat kernel acts as low-pass filter. As increases, the ratio (A also increases, discounting more and more high frequencies. That said, acts modulator between the low frequency and high frequency.
Different Kernels. We summary the kernel filters of GCN, SGC, and HKGCN in [ In Figure 2 we
Table 1: Kernel Filters.
use the eigenvalues of L. to illustrate the effects of dif- ferent kernel filters. We can observe that on Cora the absolute values of the filtered eigenvalues by GCN and SGC kernel filters do not decrease monotonically. However, the filtered eigenvalues of heat kernels in HKGCN do monotonically decrease. This is because for g\) (1 ( it monotonically increases when E [1,2] In other words, the kernel filter GCN acts band-stop filter, attenuating eigenvalues near
Model
Kernel Filter
Propagation
GCN
g(A) 1 A
D AD
SGC
s(2) 2)²
(D
FAD 4)²
HKGCN
2(A)
-
HKGCN
= 9(1) -2 e-
The Influence of High Frequency Spectrum. The eigenvalues of L and associated eigenvectors satisfy the following relation (Shuman et al. 2016) (Cf Appendix for Proof):
A
Σ (RLR))ER
A.pl
us()) VD.
1
2
(14)
DD,
This means that similar to classical Fourier transform, those eigenvectors associated with high oscillate more rapidly than those associated with low X. And we know that = Σi= uuu where u is the projection matrix project to u, Since the eigenvector u, oscillates more rapidly as the increase of i, the projection matrix u.u will also globally oscillate more rapidly as i increases. Because the filter kernel follows g(L) = Σi= g(A.)u,u," the larger g(X:) is, the greater influence on ((L will u,u," have. We show above that as increase, the oscillation of u,u, also increase. Since Y = (()), an oscillating g(L) will cause oscillating output Y. Therefore, we want the influence of higher i's u,u as small as possible, i.c. large i's g(A.) as small as possible. This explains why we need low-pass filter.
3.6 COMPLEXITY ANALYSIS
For the preprocessing step, the time complexity for matrix multiplication between the sparse Laplacian matrix and the feature vector in Chebyshev expansion is O El), with |F] is the number of edges

---

Under review as a conference paper at ICLR 2021
and d is the dimension size of input feature. Thus, the time complexity of the preprocessing step is O(kd] with is the Chebyshev expansion step. For prediction, the time complexity of logistic regression is ((VV) with [V]l is the number of unlabeled nodes, and C' is the number of label
categories.
The space complexity is O( nd), where is the number of nodes.
EXPERIMENTS
4.1
EXPERIMENTAL SETUP
We follow the standard GNN experimental settings to evaluate HKGCN on benchmark datasets for both transductive and inductive tasks. The reproducibility information detailed in Appendix.
Datasets. For transductive learning, we use Cora, Citeseer and Pubmed (Kipf & Welling 2017
Veličković et al. 2018). For inductive tasks, we use Reddit (Hamilton al. 2017). ogbn-arxiv (Hu et al. (220), and new arXiv dataset collected by ourselves, which contains over one million nodes and million edges. all inductive tasks, we train models on subgraphs which only contain training nodes and test models on original graphs. We adopt exactly the same data splitting as existing work for Cora, Citeseer, Pubmed, and Reddit.
The ogbn-arxiv dataset is accessed from OGB https://ocgt stanford It is the
Table Dataset Statistics
edu/docs nodeprop/). citation network between computer science arXiv papers and the task is infer arXiv papers' categories, such as cs.LG, Cs.SI, and CB. Each paper is given a 128-dimension word embedding based feature vector. The graph is split based on time, that is, papers published until 2017 as training, papers published in 2018 as validation, and papers published in 2019 as
Cora
Citeseer
Pubmed
Reddit
arXiv
oghn-arxiv
#Nodes
2,708
3,527
19,717
233K
1.4M
169K
#Edgos
5,429
4,732
44,338
11.6M
16.4M
1.2M
#Training-Nodes
140
120
60
152K
1.1M
90K
#Validation Nodes
500
500
500
24K
121K
30K
#Test-Nodee
1000
1000
1000
55K
18IK
49K
#Classes
test. Inspired by ogbn-arxiv. we also constructed a full arXiv paper citation graph from the public MAG (https: docs microsoft. cww./coo//oooooommo./oo en us aww.aaaaaacccccccceca serviccsseriies..eee graph/). ) We follow the same feature extraction and data splitting procedures as ogbn-arxiv and generate the arXiv dataset, which will be made publicly available upon publication.
The statistics and splitting information of the six datasets are listed in Table
Baselines. For the transductive tasks Cora, Citeseer, and Pubmed, use the same baselines used in SGC (Wu et al., 2019), including GCN (Kipf & Welling 2017). GAT (Veličković et al. (l., (2018). FastGCN (Chen et al. 2018), LanczosNet, AdaLanczos (Liao al. 2019). DGI (Veličković et al.)
2019). GIN (Xu et al. 2019b), and SGC (Wu et al. 2019).
For the inductive tasks. 2017). GCN (Kipf & Welling 2017), ClusterGCNN (Chiang et al. 2019), GraphSaint (Zeng et al.
supervised GraphSage (mean) without sampling (Hamilton al.
2019 MLP, and SGC (Wu al. (2019) baselines.
For the proposed HKGCN, the propagation time is preset based on the performance on the validation On Reddit, we follow SGC (Wu al., 2019) to train HKGCN and SGC with L-BFGS without regularization as optimizer (Liu & Nocedal] | 1989), due to its rapid convergence and good performance. However, this advantage brought by L-BFGS can not be observed in the other datasets, which we use adam optimizer (Kingma & Ba 2014), same as the other baselines.
4.2 RESULTS
We report the performance of HKGCN and baselines in terms of both effectiveness and efficiency.
Transductive. Table 3 reports the results for the transductive node classification tasks Cora, Citeseer, and Pubmed, as well as the relative rumning time on Pubmed. As the reference point, takes 0.81s for training HKGCN on Pubmed. Per community convention (Kipf & Welling 2017
7

---

Under review as a conference paper at ICLR 2021
Veličković et al. 2018). take the results of baselines from existing publications (Wu et al. 2019 and report the results of our HKGCN model by averaging over 100 runs. Finally, the efficiency is measured by the training time NVIDIA TITAN Xp GPU.
We can observe that 1) HKGCN outper- forms SGC in all three datasets with similar training time consumed, and 2) HKGCN can achieve the best prediction results on Citeseer and Pubmed among all methods and comparable results on Cora, while us- ing 2-3 orders of magnitude less time than all baselines except FastGCN and SGC.
Table 3: Transductive results in terms of test accuracy.
Cora
Citeseer
Pubmed
Pubmed (T)
GUN GAT
81.4 + 0.4
70.9 0.5
79.0
0.4
25x
+
FastGCN
79.8 0.3
6.6
77.4
5x
GIN
77.6
1.1
66.1
6..1
77.0
81x
LanezosNet
80.2
3.0
0.5
78.3 0..3:0.6
826x
NdaLanczosNet
81.9 1.9
7..6
77.8 #.7
689x
In addition, it is easy to notice that compar- ing to complex GNNs, the performance of HKGCN (and SGC) is quite stable across 100 runs, as benefits from the simple and deterministic propagation.
DGI
82. 0.7
7.74 0.7
236x
SGC
81.0
71.9
08.900000
HKGCN
81.5 1: 0.0
72.8 +
0.0
79.9 0.0|
(0.815)
Inductive. SableBssmmarrizz the perfor- mance of inductive tasks large datasets, including both test accuracy and relative running time with HKGCN's the ref- erence points. Most reported results are averaged over 10 runs, except the super- vised GraphSage (mean) and SGC meth- ods' accuracies on Reddit, which di- rectly taken from the SGC work (Wu et al. 2019).
Table 4: Inductive results in terms of test accuracy (left) and running time (right), averaged over 10 runs.
Reckit
arXiv
oghn arxiv
Redkit
arXiv
arxi-
GraphSage GCN
69.4
3.6x
3.8x
94.3
59.8
70.7
64x
2.9x
2.9%
ClusterGCN
60.7
55.9
GraphSaiint
92.3
59.2
56.1
138x
2.4x
4.0x
MLP
70.0
44.1
55.5
9.3x
1.75x
5.2x
SGC
94.9
60.1
69.6
0.5x
0.93x
0.95x
HKGCN
95.5
60.4
70.0
1x
1x
1x
The results suggest that 1) the performance HKGCN is consistently better than SGC and comparable to advanced GNN models, such as supervised GraphSage, ClusterGCN, and GraphSaint Additionally, we notice that HKGCN, GraphSage, and GCN yield the best results Reddit, arXiv, and ogbn-arxiv, respectively, indicating the lack of universally-bes: GNN models.
Efficiency wise, HKGCN costs 2.2s, 48.5s, and 5.2s three datasets, respectively, which are similar to SGC, both which are clearly more efficient than other GNN models as well as MLP.
Analysis of 7. In HKGCN, i determines how long the feature propagation lasts for. larger f can amplify global features and lower can emphasize local information. From Figure we can observe that i has similar impact on different datasets, and as the propagation time increases, the model at first benefits from information from its local neighbors. How- ever, as the feature propagation continues (e.g.. f > 9 or 12), the performance of the model starts to decrease, likely suffering from the over-smoothing issue (Li et al. 2018).
Accuracy (%)
80
ciesseer
20
pubmed
reddit
60
ogbm-aniv
50
40
20
30
value of
Figure 3: Performances with varying from 0 to 30.
CONCLUSION AND DISCUSSION
In this work, we propose to generalize graph convolutional networks (GCNs) and simple graph convolution (SGC) via heat kernel, based on which, we present the HKGCN model. The core idea of HKGCN to use heat kernel as the feature propagation matrix, rather than the discrete and non-linear feature propagation procedure in GCNs. We theoretically show that the feature propagation of GCNs is equivalent to the finite difference version of heat equation, which leads overshoot the convergence point and causes oscillated propagation. Furthermore, show that
8

---

Under review as a conference paper at ICLR 2021
heat kernel in HKGCN acts as low-pass filter. On the contrary, the filter kernel of GCNs fails to attenuate fegh-frquency signals, which is also a factor leading to the slow convergence and feature oscillation. While in heat kernel, the cutoff frequency decreases as the increase of the propagation time f. Consequently, the HKGCN model could avoid these oscillation issue and propagate features smoothly. Empirical experiments six datasets suggest that the proposed HKGCN model generates promising results. Effectiveness wise, the linear HKGCN model consistently beats SGC and achieves better or comparable performance than advanced GCN baselines. Efficiency wise, inherited from SGC, HKGCN offers order-of seder-of-maagituee magnitude faster training than GCNs.
Notwithstanding the interesting results of the present work, there is still much room left for fu- ture work. One interesting direction is to learn the propagation time t from data in HKGCN for automatically balancing information between local and global features.
REFERENCES
Sami -l-jaa, Bryan Perozzi, Amol Kapoor, Hrayr Harutyunyan, Nazanin Alipourfard, Kristina Lerman, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolution archi- tectures via sparsified neighborhood mixing. In International Conference on Machine Learning (ICML), 2019.
L.C. Andrews and Society Photo-optical Instrumentation Engineers. Special Functions of Mathe- matics for Engineers. Oxford science publications. SPIE Optical Engineering Press, 1998. ISBN
9780819426161 URL atttps://bodte google www/bookokkeeeoooooooooooooooooe Seidd2cCAgss -RebgC
Peter Battaglia, Jessica Blake Chandler Hamrick, Victor Bapst, Alvaro Sanchez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Caglar Gulcehre, Francis Song, Andy Ballard, Justin Gilmer, George E. Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash, Victoria Jayne Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matt Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks. arXiv, 2018 URL htt.//tttt::.....rrr///////// 01261. Fdd
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.622 2013.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. arXiv preprint arXiv: 1801 2018.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsich. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th A ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 257-266, 2019.
Fan RK Chung and Fan Chung Graham. Spectral graph theory. Number 92. American Mathematical Soc., 1997.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems, pp. 3844-3852, 2016.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, ICML'17, pp. 2263-1272 JMLR.org. 2017.
Marco Gori, Gabricle Monfardini, and Franco Scarselli. A new model for learning in graph domains. In IJCNN'OS, 2005.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in neural information processing systems, pp. 1024-1034, 2017.
David Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):129-150) 2011.

---

Under review as a conference paper at ICLR 2021
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint wwXh:22005.00687 2020.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint 1rXivv1412.69800 2014.
Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. In Advances in Neural Information Processing Systems, pp. 13354-13366 2019.
Risi Imre Kondor and John Lafterty. Diffusion kernels graphs and other discrete structures. In Proceedings of the 19th international conference on machine learning, volume 2002, pp. 315-22, 2002.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI'18, 2018.
Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard S Zemel. Lanczosnet: Multi-scale deep 2019.
graph convolutional networks. arXiv preprint
Dong Liu and Jorge Nocedal. On the limited memory bfgs method for large scale optimization. Mathematical programming. 45(1-3):503-522 -285000-5-8,11 1989.
Michael Poli, Stefano Massaroli, Junyoung Park, Atsushi Yamashita, Hajime Asama, and Jinkyoo Park. Graph neural ordinary differential equations, 2020.
Meng Qu, Yoshua Bengio, and Jian Tang. Gmnn: Graph markov neural networks. ICML'19, 2019.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2008.
David Shuman, Benjamin Ricaud, and Pierre Vandergheynst. Vertex- Vertex-frequency analysis on graphs. Applied and Computational Harmonic Analysis, 40(2):260-291 2016.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, 2018.
URL
net fort/forum?? ri= accepted as poster.
Petar Veličković, William Fedus, William L. Hamilton, Pietro Liø, Yoshua Bengio, and R Devon Hjelm. Deep Graph Infomax. International Conference on Learning Representations, 2019.
URL_htttss:///peerree
net forumf wetrrmmiidrrk.. 2wikkkg99icKK
Widder and David Vernon. The heat equation, volume 67. Academic Press, 1976.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning, pp. 6861 6861-6871. PMLR, 2019.
Louis-Pascal A. C. Xhonneux, Meng Qu, and Jian Tang. Continuous graph neural networks, 2020.
Bingbing Xu, Huawei Shen, Qi Cao, Keting Cen, and Xueqi Cheng. Graph convolutional networks using heat kernel for semi-supervised learning. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 1928-1934, AAAI Press, 2019a.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In International Conference on Learning Representations, 2019b. URL https //openreview.o .nt. wttppe/w......rrmmmmmoaaaa......
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In KDD'18 18, 2018.
10

---

Under review as a conference paper at ICLR 2021
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. arXiv preprint arXiv:1907.09931, 2019.
Jie Zhang, Yuxiao Dong, Yan Wang, Jie Tang, and Ming Ding. Prone: fast and scalable network representation learning. Proc. 28th Int. Joint Conf. Artif. Intell., IJCAI, pp. 4278-4284, 2019.
Muhan Zhang and Yixin Chen, Link prediction based on graph neural networks. In NeurlPS' 18, 2018.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. ICLR 2020.
Juntang Zhuang, Nicha Dvorekk Xiaoxiao Li, and James S. Duncan. Ordinary differential equations on graph networks, 2020. URL WRR_httts:///peeeevieee net fwrmm?orrmmmmmo (ttp:mmmddddUgg9277700
Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. Layer-dependent importance sampling for training deep and large graph convolutional networks. In NeurlPS' 19, 2019.

---

Under review as a conference paper at ICLR 2021
A REPRODUCIBILITY INFORMATION
A.1 HYPERPARAMETERS
We introduce the hyperparameters used in the experiments, including weight decay, #epochs, learning rate, f, and optimizer, which are also summarized in Table The Chebyshev expansion step &s is set to 20.
Citation Networks. We train HKGCN for 100 epochs using the Adam optimizer (Kingma & Ba 2014) with 0.2 as the learning rate, which are the same settings used in SGC (Wu et al. 2019). First, fix the weight decay to 5 10-6 and search i from {0,3, 6, 9, 12, 15, 18, 21, 27, 30) based on the performance on the validation set. Then fix the best performance & and search the weight decay from {10-9 6 10 100 $} based on the performance on the validation set.
Reddit dataset. We follow SGC (Wu al., 2019) train HKGCN and SGC with L-BFGS without regularization as the optimizer (Liu Nocedal 1989). due to its rapid convergence (2 epochs) and good performance. However, this advantage brought by L-BFGS can not be observed in the other datasets, for which we use the adam optimizer (Kingma & Ba 2014), same as the other baselines. We search é from all non-negative integers equal or lower than 15, based on the performance on the validation set.
Xiv and ogbn-arxiv datasets. We the Adam optimizer with no weight decay train HKGCN and SGC, same as other baselines. Using the same treatments in citation networks, we fix the learning rate to 0.2. We first fix 500 epochs and search f from all non-negative integers equal or lower than 15 by using the validation set. On the ogbn-arxiv dataset, the model does not converge after 500 epochs and thus we extend it to 1000.
Situation for Large f. If i is greater than 10, the floating point precision error would be- come an issue in calculating the Bessel function. Therefore, in practice, we convert e(-L into -
Situation for Very Large Graphs. Though the Chebyshev expansion is very close to the minimax polynomial on the range [-1,1] and thus makes converge very fast, the recurrence relation in Eq. 13 is second-order. In other words, the calculation of T (x) needs to store Tx(x), T: (x) and L, making it require more GPU memory than the first-order recurrence relation expansion, such as Taylor expansion. Therefore, instead of using the Chebyshev expansion, we leverage Eq. aas (++ = (I A for the calculation. In this way, we only need to store X and L, which requires much less memory space.
Training Time We tested all experiments on NVIDIA TITAN Xp GPU with 12 GB memory. The training time of HKGCN is the sum of 1) the feature pre-processing time and 2) logistic regression training time. So we can see the largest training time difference between SGC and HKGCN occurs on the Reddit dataset. This is because it only takes two epochs to converge on the Reddit dataset by using L-BFGS, making the logistic regression step very fast. Thus the pre-processing step dominates the training time for HKGCN and SGC on Reddit.
Table 5: Hyperparameters
Cora
Citeseer
Pubmed
Reddit
arXiv
ogbn-arxiv
i
12
15
6
weight decay
10 10-5
10
10
n/a
0
0
#epochs
100
100
100
500
1000
learning rate
0.2
0.2
0.2
0.2
0.2
optimizer
adam
adam
adam
1-bfgs
adam
adam
A.2 BASELINE METHODS
Per community convention (Kipf & Welling 2017 Veličković et al. 2018). the results baselines in
the three citation networks (Cora, Citeseer, and Pubmed) are taken from existing publications (Wul
12

---

Under review as a conference paper at ICLR 2021
et al. 2019). The hyperparameters settings of inductive tasks three large datasets (Reddit, arXiv, and ogbn-arxiv) are introduced as follow.
SGC. To make fair comparison, select K in SGC based the performance the validation set, which has similar meaning as HKGCN.
GCN. The learning rate is set to 0.01 all datasets. The weight decay is O. The number of layers is 3 on Reddit and ogbn-arxin and on arviv because of the GPU memory limit. The hidden layer size 256 Reddit and ogbn-arxiv, and 128 arXiv also due memory limit. The number of epochs is 500.
GraphSage. Results the Reddit dataset directly taken from the SGC paper (Wu et al. 2019). The other parameter settings are the same as GCN above. We use the mean- aggregator as provides the best performance.
MLP. The number of layers is 3 and the hidden layer size is 256, and Batch Norm is not used.
ClusterGCN. On the Reddit dataset, the number of partitions is 1500, the batch size is 20, the hidden layer size 128, which are the same parameter settings as the original SGC paper (Chiang al. 2019). On the arXiv dataset, the number of partitions is 15000, the batch size is 32, the hidden layer size is 256. The number of epochs of these two datasets is 50. On the ogbn-arxiv dataset, the number of partitions is (as large number would cause an unknown bug in the Geome-ie library), the batch size is 32, the hidden layer size is 256. We set the epoch number to 200 on the ogbn-arxiv dataset because it does not converge after 50 epochs.
GraphSaint. On the Reddit dataset, the number of layers is 4, the hidden layer size is 128, the dropout rate 0.2, the same parameter settings as used SGC (Zeng et al.] (211)). On the arXiv dataset, the number of layers is 3, the hidden layer size is 256, the dropout rate is 0.5. On the ogbn-arxiv dataset, we use the same parameter setting as the Reddit dataset, because both graphs are on the same scale.
B ALGORITHM OF PRESETTING
Algorithm Preset / in HKGCN
Input: input features X; feature propagation duration time i; Chebyshev expansion step k; scaling augmented normalized Laplacian L/2; (t) is the modified Bessel function. pre-processed features (+);
Output:
To(x) < X;
x < (x);;
Ti(x) <- LX:
X(O) +- x() 2B (f):;
for = 2...k
Tx(x) +- 2LT;-1 (x) - (x);
if is odd then
(*) - (1) (f)T,
else
(t) - (1) + (x);
end if
end for
13

---

Under review as a conference paper at ICLR 2021
C PROOF OF EQ. 14
A un Luk
= u (I D- 3)
2Aij
Σ (x())²
Σ
us (1
V Dir ij
iE(1.....)
(EIRY)EE
Σ
Ayy
ux(i)
uu mx(i)]
Via
v DD3
14


Reviews:
[{"review_id": "rv5EwIWWhbo", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This submission introduced a new graph convolutional operator based on heat diffusion, named heat kernel GCN (HKGCN). First, continuous-time heat diffusion on graphs is reviewed, where the solution is given by the heat equation (6). Then, the authors showed that classical GCN can be approximated in the same formulation through discretization.\n\nThe proposed method HKGCN is similar to the simplified GCN (SGC) by Wu et al. The learning procedure is quite straightforward: first, a heat diffusion is performed on the input features for a pre-specified time $t$; then, logic regression is performed on the diffused features to train the classifier. The SGC model performs several times of neighborhood averaging (as in vanilla GCN) based on a polynomial spectral filter of order one; while HKGCN performs heat diffusion with higher-order polynomial terms.\n\nMy main criticism is that applying heat diffusion on graph convolution is not new and the relationship with previous works is not clearly stated. See the cited (Xu et al 2019a) or not mentioned (Klicpera 2019) (Xu et al 2019c), where similar formulations and ideas already appeared. The main novelty of the proposed HKGCN, therefore, is on a combination of heat kernel and the SGC approach. This combination is not non-trivial enough and may not be significant enough to be published in ICLR.\n\nThe HKGCN method is motivated by the oscillation problem of GCN. How does the heat kernel help avoid oscillation? After the introduction of the heat equation, there should be some theoretical statements to provide a solution to this problem and to correspond to this motivation. Ideally, to show how HKGCN is different with the GCN approach. Instead, the oscillation problem is mainly solved by numerical simulation on the toy example and informal arguments.\n\nAs another novelty, the authors revealed that GCN can be approximated using heat diffusion under the same formulation. Again the connection although interesting is not a major contribution.\n\nEmpirically, the authors tested the HKGCN method on commonly used citation datasets and an OGB graph of arxiv articles, on both transitive and inductive learning tasks.\n\nThe huge speed improvement is mainly due to the same trick as SGC is used in HKGCN: there is no activation between the convolution layers which allows a pre-computation step followed by an extremely simplified learning step (logistic regression). This improvement is due to SGC and is expected.\n\nBy looking at the accuracy scores, the main comparison is HKGCN vs SGC because of their similarities. It is not convincing that using heat diffusion (HKGCN) instead of graph convolution (SGC) can bring a notable performance improvement. In most of the time, the improvement is quite marginal.\n\nOverall, this technical novelty and empirical significance are limited. There are not theoretical statements in this paper and I am evaluating it as an algorithmic contribution. I am recommending a weak rejection.\n\nMore comments:\n\nThe title is too broad. Please be more specific.\n\nToy example in the introduction: As this toy is mentioned again in later text, please explain in more detail the computation of GCN vs HKGCN.\n\nAs you started from GNN, it is good to cite some original GNN paper (Gori et al. 2005; Scarselli et al 09)\n\neq.(9) n_{iter} is hard to read\n\nin this template, most of the citations should use \\citep instead of \\cite\n\nReferences:\n\n(Klicpera 2019)\n\"Diffusion Improves Graph Learning\", Klicpera et al. 2019\n\n(Xu et al 2019c)\n\"graph wavelet neural network\" Xu et al. 2019\n\n---\nAfter rebuttal:\n\nThank you for the revision and the clarifications.\n\n\"no one has made a clear connection between GCN and the heat kernel.\" \nFor example, in (Klicpera 2019) section 2, the heat kernel is discussed as a special case.\n\n\"We don’t simply combine SGC and heat kernel.\"\nClearly, the only difference between the proposed method in section 3.4 and SGC is that the authors used heat diffusion as the spectral filter matrix, while SGC used a polynomial filter (the K'th power of the normalized adjacency matrix).\n\nFurthermore, the other reviewers raised similar works such as graph ODE, which further reduces the novelty of this work.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "rJoVdZ4Y4xn", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors  shed light on  linear GCNs models and propose  a new design which aim at generalizing  GCNs to continuous and  and a linear propagation model inspired by Newton's law. \nIt is based on the hypothesis that features propagation across nodes in a given graph follows the same process.\n To do so, the authors establish a link with heat kernels and formulate the problem as heat kernel learning within linear GCN model so that the network at the feature propagation step takes into consideration  multi-hop neighboring systems to refine the features of a given central node. \n\nIn this paper, the authors find out that features propagation based on heat kernel allows to control the oscillation between low and high frequencies. Controlling the appropriate level of granularities is quite a challenging task in deep learning mainly, as the convolutional filters are biased toward low frequencies. \nHowever,  important invariants and informative information for classification are within the chaos of high frequencies. In order to control that, the authors explain that  GCN based heat kernels can act as a low-pass filter cutoff. This combination of GCN and heat kernels are empirically validated considering node and graph classification tasks. The settings are clear and the comparison with related works is convincing.\n\nOne of the strong points of the paper is its capacity to provide comparable results state-of-the-art  with a reasonable complexity in space, with the advantage of being more simple and interpretable compared to existing (related) methods. Moreover a theoretical analysis from a spectral standpoint is introduced clearly.  It consists at setting link between Linear GCN and heat kernels, as well as with finite difference methods.\nHowever, it’s not clear how the proposed GCN tackles the problem of over-smoothness and graph isomorphism. They are among the most challenging problems in graph learning. From that, l derive two questions :\n\n1- To what extent GCN based on heat kernel formulation is able to mitigate over-smoothness ?\n\n2- Is the proposed heat kernel function injective so that it is able to distinguish two non-isomorphic graphs ?\n\nOne possible weakness of the proposed design, is that it can be applicable only on graphs with fixed topology and size as it is the case for all spectral GCN (filters are not transferable across graphs since they are basis dependent). However, in real world problems  graphs are irregular.\n\nThe overall approach is  original, well placed in the litterature and the paper is well written. The authors conduct both theoretical and practical studies to show that this research direction could be important to improve existing GCN models. For that reason, l propose to accept the paper.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "RBLU7p8zpR", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies semi-supervised node classification in graph data. One powerful approach to the task is graph convolutional networks, which use discrete layers to perform information propagation. The paper generalizes GCNs into a continuous model via heat kernel, where the proposed model uses continuous layers for information propagation. The authors conduct both theoretical and empirical analysis of the proposed model. Experiments on several standard datasets show promising results. Overall, the paper studies an important problem in graph machine learning, and proposes a principled approach, which combines graph neural networks with heat kernels, and gives a new way of analyzing existing graph neural networks.\nHowever, the paper also has several weaknesses:\n1. The novelty is limited.\nAlthough the idea of developing continuous propagation layers is interesting, the idea has been explored by many recent works. For example, [1,2,3] use a graph neural network to define an ODE, which leads to a continuous feature propagation layer for node classification. [4] uses a linear ODE for feature propagation, which is very similar to the method proposed here, and the only difference is that the ODE in [4] also incorporates some constant term besides -LX. The authors should explain and clarify the difference between this work and existing works.\n\n2. The results are worse than SOTA methods.\nIn experiments, the authors conduct experiments in many standard datasets (e.g., Cora, Citeseer, Pubmed), and the proposed method shows promising results. However, the compared methods used in experiments are not competitive enough. The strongest baseline methods in Table 3 are GCN and GAT, and in Table 4 they are GraphSage and GCN. All these methods are proposed before 2017, and recently there are many more competitive methods proposed. To make the results more convincing, it is helpful to compare against some recent graph neural networks for node classification.\nBesides, I also have some questions regarding the model detail:\n1. About t in equation (6).\nIn Equation (6), the analytical form of X^{(t)} is given by X^{(t)}=e^{-Lt}X, where t can have a high impact on the results. If t is very small, then e^{-Lt} becomes an identity matrix, and hence H_t will be very close to X. If t is very large, then e^{-Lt} becomes an matrix whose elements are all close to 0, and thus all the rows in H_t will be almost the same, yielding an over-smoothing problem. In practice, what would be a proper value of t? Moreover, if we look at Figure (6), even when t is very large (e.g., t>20), the accuracy is still very high especially on Cora, which indicates that the model does not suffer from over-smoothing in practice. But if we check the analytical form X^{(t)}=e^{-Lt}X, when t is large, all the rows in H_t become very similar, which may lead to over-smoothing and a low accuracy. I wonder how does the proposed model manage to avoid over-smoothing in practice? Could the authors elaborate on that?\n2. About feature dimensionality.\nIn the propose method, the hidden matrix H_t has the same size as the feature matrix X. If the feature dimensionality of a dataset is very high, which is quite common in practice, then computing H^{(t)} can entail high cost. Is there a way to deal with the potential problem?\n3. About the time complexity.\nIn Section 3.6, the authors mention that the time complexity of data processing is O(k|E|). What is k here?\nReferences:\n[1] Poli, Michael, et al. \"Graph neural ordinary differential equations.\" arXiv preprint arXiv:1911.07532 (2019).\n[2] Deng, Zhiwei, et al. \"Continuous graph flow for flexible density estimation.\" arXiv preprint arXiv:1908.02436 (2019).\n[3] Zhuang, Juntang, et al. \"Ordinary differential equations on graph networks.\" (2019).\n[4] Xhonneux, Louis-Pascal AC, Meng Qu, and Jian Tang. \"Continuous Graph Neural Networks.\" arXiv preprint arXiv:1912.00967 (2019).", "extra_scores": {}, "extra_text": {}}, {"review_id": "JZVlMesxb1p", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This submission proposes to use heat kernel as the propagation matrix in graph convolutional networks. The authors show that heat kernels can induce more smooth propagation behavior than the commonly used discrete propagation. The submission also designs an efficient method to calculate the heat kernel (using Chebyshev expansion). \n\nStrength:\n- The proposed method is well motivated and heat kernel is (relatively) well-understood. \n- The writing is clear and easy-to-understand\n- The proposed method demonstrates improved performance on node classification datasets while inheriting the efficiency of simple graph convolution\n- The submission collects a larger scale arxiv graph dataset, which can be useful for the community. Will the authors release this dataset in the future?\n- This submission has done a detailed and thorough evaluation of the proposed method. I appreciate the effort to analyze $\\tilde{t}$, which should be helpful for practitioners.\n\nWeakness:\n- SGC is known to be ineffective for graph classification tasks. Does the proposed model also inherits this downside?\n- Table 3 lacks comparisons to more recent graph neural networks like Graph Markov Neural Networks. However, I don't think this is critical given the efficiency and strong performance of the proposed method on larger graph datasets. \n\n\n=== UPDATED ===\n\nGiven that the reviewers have not reached a consensus, I want to add more discussion to my review to facilitate the AC to make the decision. I would also include a few more quick TODOs for the authors and hope they can help add evidence to my argument.\n\n1. This submission proposes to replace the propagation in GNNs with heat kernel. The main motivation for this method is that the laplacian filters tend to oscillate, as illustrated by Figure 1. The heat-kernel provides a continuous convergence process and intuitively may address the oscillation process. Importantly, I believe the motivation of this method is *not* to prevent oversmoothing but to prevent over-oscillation. \n\nI believe this intuition is sound but encourage the authors to do more to validate this hypothesis. I appreciate the ablation study in Figure 6. As one more analysis, I suggest the authors to add the performance curves of SGC to Figure 6 (under the same setting). If this theoretical intuition is valid, we should expect HKGCN and SGC to behave more differently when the propagation degree is low (within 2-10). My understanding is that both HKGCN and SGC are efficient so this experiment shouldn't take long. Ideally the authors can update this result, at least on 1-2 datasets, within the discussion period.\n\n2. I am also very impressed by the efficiency of HKGCN. This submission has experimented with, to my knowledge, the largest publicly available graph dataset (arXiv), which contains more than one million nodes. According to the authors, HKGCN can be trained for this arXiv dataset in 48.5s, which is impressive. \n\nNote that here the heat diffusion matrix does not need to be computed/stored explicitly. Following the setup in SGC, HKGCN only needs to compute the propagated features in a preprocessing step.  \n\nI suggest the authors to give more concrete numbers to illustrate the efficiency of this method. For this arXiv dataset, what kind of hardware is required? How much actual RAM did you use to compute the preprocessing step?\n\n3. After reading other reviews, I now realize that this submission is not the first to introduce heat kernels into GCNs. Among the papers pointed out by other reviewers, I find [1] to be most relevant in that they also proposed the usage of heat kernels. Can the authors also clarify the difference between this submission and [2]?\n\nBased on this novelty concern, I have lowered my review score to 6. \n\n[1] Xu et al, graph wavelet neural network, ICLR 2019\n[2] Xu et al, Graph Convolutional Networks using Heat Kernel for Semi-supervised Learning, IJCAI 2019. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper has been evaluated by four reviewers who overall hesitated between borderline reject/accept. In general, as Rev. 4 points out, this paper appears to cope with over-oscillation rather than over-smoothing aspect of GCN modeling (something worth clarifying). Rev. 3 also rightly points out that the connection between the heat kernel and GCN in fact was established in previous works. Also, the connection between SGC (polynomial filter) and  the heat diffusion (the spectral filter matrix) is hard to overlook (the impression that this work builds heavily on SGC). Therefore, while AC sympathizes with the idea, it is also difficult to overlook the incremental nature of the paper and therefore the paper cannot be accepted in its current form.
Decision: Reject