Year: 2020

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.

text: 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.

heading: 1 INTRODUCTION
text: Graph neural networks (GNNs) have emerged as a powerful framework for modeling structured and relational data (Gori et al., 2005; Scarselli et al., 2008; Gilmer et al., 2017; Kipf & Welling, 2017). A wide range of graph mining tasks and applications have benefited from its recent emergence, such as node classification (Kipf & Welling, 2017; Veličković 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) (Kipf & 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 as incorporating self-attention in GAT (Veličković et al., 2018), mixing high-order neighborhoods in MixHop (Abu-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 is actually associated with excess complexity and redundant operations. To that end, they simplify GCNs into a linear model SGC by removing all 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 two nodes v1 and v2 with one-dimension input features x1 = 1 & x2 = 2 and one weighted edge between them, the feature updates of x1 and x2 during the GCN propagation is shown in Figure 1 (a), from which we can clearly observe the oscillations of x1 and x2 step by step. This indicates that though the features from multi-hops away may seem to be taken into consideration during the GCN propagation, it is still far away to learn patterns from them.
In this work, we aim to generalize GCNs into a continuous and linear propagation model, which is referred to as HKGCN. We derive inspiration from Newton’s law of cooling by assuming graph feature propagation follow a 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 1 (b). Finally, from the graph spectral perspective, heat kernel acts as a low-pass filter and the cutoff frequency of heat kernel can be adjusted by changing the propagation time.
Empirically, we demonstrate the performance of HKGCN for both transductive and inductive semi-supervised node classification tasks. The experiments are conducted on both traditional 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 linear 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-magnitude efficiency superiority inherited from SGC.

heading: 2 RELATED WORK
text: Graph Neural Networks. Graph neural networks (GNNs) have emerged as a new paradigm for graph mining and learning, as 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 to 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., 2011). Attempts to further this direction leverage Chebyshev Expansion to achieve the same linear computational complexity as classical CNNs (Defferrard et al., 2016). Later, the graph convolutional network (GCN) (Kipf & Welling, 2017) simplifies the filter kernel to the second-order of Chebyshev Expansion, inspiring various advancements in GNNs. GAT brings the attention mechanisms into graph neural networks (Veličković et al., 2018). GMNN combines the benefits of statistical relational learning and GNNs into a unified framework (Qu et 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 as neural message passing (Gilmer et al., 2017). In addition, studies also find that the performance of GNNs decreases with more and more layers, known as the over-smoothing issue (Li et al., 2018; Zhao & Akoglu, 2020). To reduce GCNs’ complexity, SGC turns the GCN model into a linear model by removing the non-linear activation operations between consecutive GCN layers (Wu et al., 2019), producing promising results in 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 et 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.
Concurrent work. Several recent works have developed similar idea. (Poli et al., 2020; Zhuang et al., 2020) use the Neural ODE framework and parametrize the derivative function using a 2 or 3 layer GNN directly. (Xhonneux et al., 2020) improved ODE by developing a continuous messagepassing layer. All ODE models make feature converge to stable point by adding residual connection. In contrast, our model outputs an intermediate state of feature, which is a balance between local and global features. Some recent works (Xu et al., 2019a; Klicpera et al., 2019) propose to leverage heat kernel to enhance low-frequency filters and enforce a smooth feature propagation. However, they do not realize the relationship between the feature propagation of GCNs and heat kernel.

heading: 3 GENERALIZING (SIMPLE) GRAPH CONVOLUTION VIA HEAT KERNEL

heading: 3.1 PROBLEM AND BACKGROUND
text: We focus on the problem of semi-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 = (V,E), where V denotes the node set of n nodes {v1, ..., vn} and E represents the edge set. The symmetric adjacency matrix of G is defined as A and its diagonal degree matrix as D with Dii = ∑ j Aij . For each node vi ∈ V , it is associated with a feature vector xi ∈ X ∈ Rn×d and a one-hot label vector yi ∈ Y ∈ {0, 1}n×C , where C is the number of classes. The problem setting of semi-supervised graph learning is given the labels YL of a subset of nodes VL, to infer the labels YU of the remaining nodes VU , where VU = V \VL. Graph Convolutional Networks. Given the input graph G = (V,E) 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(l+1) = σ(D̃− 1 2 ÃD̃− 1 2H(l)W(l)), (1)
where Ã = A + IN is the adjacency matrix with additional self-connections with IN as the identity matrix, W(l) is a trainable weight matrix in the lth layer, σ(·) is a nonlinear function such as ReLU, and H(l) denotes the hidden node representation in the lth layer with the first layer H(0) = 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 a1 is equal to the 0-th order coefficient a0 multiplied by −1, i.e., a1 = −a0. We will later prove that this is just a discrete solution of heat equation.
Simple Graph Convolution. Since its inception, GCNs have drawn tremendous attention from researchers (Chen et al., 2018; Veličković 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:
Y = softmax((D̃− 1 2 ÃD̃− 1 2 ) K 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, as a 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 a 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 vi and node vj should be proportional to 1) the edge weight and 2) the temperature difference between vi and vj . Let x (t) i denote the temperature of vi at time t, the heat diffusion on graph G can be described by the following heat equation:
dx (t) i
dt = −k ∑ j Aij(x (t) i − x (t) j ) = −k[Diix (t) i − ∑ j Aijx (t) j ]. (3)
The equation under the matrix form is dX (t)
dt = −kLX (t), where L = D−A is the graph Laplacian
matrix. By reparameterizing t and k into a single term t′ = kt, the equation can be rewritten as:
dX(t ′)
dt′ = −LX(t
′) (4)
A heat kernel is the fundamental solution of the heat equation (Chung & Graham, 1997). The heat kernel Ht is defined to be the n× n matrix:
Ht = e −Lt (5)
Given the initial status X(0) = X, the solution to the heat equation in Eq. 4 can be written as
X(t) = HtX (6)
Naturally, the heat kernel can be used as the feature propagation matrix in GCNs.

heading: 3.2 CONNECTING GCN AND SGC TO HEAT KERNEL
text: GCN’s feature propagation follows D̃− 1 2 ÃD̃− 1 2 , through which node features diffuse over graphs. Note that the feature propagation in GCN is just one step each time/layer, hindering individual nodes from learning global information. By analogy with the heat diffusion process on graphs, the heat kernel solution can also be perfectly generalized to the feature propagation in the graph convolution.
Instead of using L, we follow GCN to use the symmetric normalized Laplacian L̃ = I− D̃− 12 ÃD̃− 12 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. 4 as dX (t)
dt = −L̃X (t) and the heat kernel in Eq. 5 as Ht = e−L̃t.
Consider the finite difference of this heat equation, it could be written as:
X(t+∆t) −X(t)
∆t = −L̃X(t) (7)
If we set ∆t = 1, we have X(t+1) = X(t) − L̃X(t) = D̃− 12 ÃD̃− 12 X(t). This is the same feature propagation rule in Eq. 1. In other words, each layer of GCN’s feature propagation on graphs is equal to the finite difference of the heat kernel. If we consider the multilayer GCN without the activation function, it could be written as SGC (Wu et al., 2019): Y = softmax((D̃− 1 2 ÃD̃− 1 2 ) K
XW), where Y is the classification result and W is the merged weight matrix. Using the finite difference of heat equation above, it can be rewritten as:
Y = softmax(X(K)W), (8)
which is still a multistep finite difference approximation of the heat kernel.
Reduce ∆t. Assuming t can be divided by ∆t, the number of iterations is ni = t∆t , making Eq. 7 become X(t) = (I−∆tL̃)niX. By fixing t = 1, we have
X(1) = (I− 1 ni L̃) ni X
= (I− ni ni L̃ + ni(ni − 1) n2i L̃2 2! + · · ·+ (−1) nini! nnii L̃ni ni! )X
(9)
Therefore, ni iterations of t = 1 approximate to Taylor expansion of the heat kernel at order ni. So GCN could also be seen as the first-order Taylor expansion of the heat kernel.

heading: 3.3 HEAT KERNEL AS FEATURE PROPAGATION
text: 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.
A case study. We illustrate how the features are updated during the GCN and heat kernel propagations. Let us consider a graph of two nodes v1 and v2 with one-dimension input features x1 = 1 and x2 = 2 and one weighted edge A12 = A21 = 5 between them. Recall that with ∆t = 1 GCN is equivalent to the finite difference of the heat kernel. Thus, we set ∆t = 1 for the heat kernel as well.
The updates of x1 and x2 as the propagation step t increases are shown in Figure 1. We can observe that heat kernel shows much smoother and faster convergence than GCN.
In GCN, the discrete propagation D̃− 1 2 ÃD̃− 1 2 layer by layer causes node features to keep oscillating around the convergence point. The reason lies in GCN’s requirement for ∆t = 1, which is too large to have a smooth convergence. Straightforwardly, the oscillating nature of GCN’s feature propagation makes it sensitive to hyper-parameters and generate weak performance on large graphs. Theoretical analysis is given in Section 3.5.

heading: 3.4 GENERALIZING GRAPH CONVOLUTION
text: 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 a 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 t in heat kernel can be seen as a generalized parameter of the number of layers in GCN (Kipf & 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, we propose to generalize graph convolution networks by using heat kernel and present the HKGCN model. Specifically, we simply use the one layer linear model:
Y = softmax(X(t)W) = softmax(e(−L̃t)XW), (10)
where W is the n × C feature transformation weight and t can be a learnable scalar or a preset hyper-parameter.
Using a preset t converts HKGCN to 1) a pre-processing step X̄ = e(−L̃t)X without parameters and 2) a linear logistic regression classifier Y = softmax(X̄W). This makes the training speed much faster than GCN. The algorithm of presetting t is in Appendix (Algorithm 1).
To avoid eigendecomposition, we use Chebyshev expansion to calculate e(−L̃t) (Hammond et al., 2011; Zhang et al., 2019). The first kind Chebyshev polynomials are defined as Ti+1(x) = 2xTi(x)− Ti−1(x) with T0(x) = 1 and T1(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 = λ0 ≤ ... ≤ λn−1 ≤ 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 t to t̃ = 2t so that the heat kernel keeps in the original form. In doing so, we have
e(−L̃t) = e(−L̄t̃) ≈ k−1∑ i=0 ci(t̃)Ti(L̄) (11)
And the coefficient ci of the Chebyshev expansion can be obtained by:
ci(t̃) = β
π ∫ 1 −1 Ti(x)e −xt̃ √ 1− x2 dx = β(−1)iBi(t̃) (12)
where β = 1 when i = 0, otherwise β = 2, and Bi(t̃) is the modified Bessel function of the first kind (Andrews & of Photo-optical Instrumentation Engineers, 1998). By combining Eqs. 11 and 12 together, we can have e(−L̄t̃) approximated as:
e(−L̄t̃) ≈ B0(t̃)T0(L̄) + 2 k−1∑ i=1 (−1)iBi(t̃)Ti(L̄) (13)

heading: 3.5 SPECTRAL ANALYSIS
text: From the graph spectral perspective, heat kernel acts as a low-pass filter (Xu et al., 2019a). In addition, as the propagation time t increases, the cutoff frequency decreases, smoothing the feature propagation.
Graph Spectral Review. We define Λ = diag(λ1, ..., λn) as the diagonal matrix of eigenvalues of L̃ and U = (u1, ...,un) as the corresponding eigenvectors, that is, L̃ = UΛUT .
The graph Fourier transform defines that x̂ = UTx is the frequency spectrum of x, with the inverse operation x = Ux̂. And the graph convolution between the kernel filter g(·) and x is g ∗ x = Ug(Λ)UTx with g(Λ) = diag(g(λ1), · · · , g(λn)). For a polynomial g(L̃), we have g(L̃) = Ug(Λ)UT . This can be verified by setting g(λi) =∑K j=0 ajλ j i , that is, Ug(Λ)U T = U ∑K j=0 ajΛ jUT = ∑K j=0 ajUΛ jUT = ∑K j=0 ajL̃ j = g(L̃).
Heat Kernel. As g(L̃) = Ug(Λ)UT , the heat kernel Ht = e−L̃t = ∑∞ i=0 1 i! t iL̃i could also be seen as a polynomial of L̃. Thus its kernel filter is g(λi) = e−λit. Note that the eigenvalues of L̃ is in the range of [0, 2]. For ∀i, j, if λi < λj , we have g(λi)g(λj) = e (λ2−λ1)t > 1. Thus g(λi) > g(λj). Heat kernel acts as a low-pass filter. As t increases, the ratio e(λ2−λ1)t also increases, discounting more and more high frequencies. That said, t acts as a modulator between the low frequency and high frequency.
Different Kernels. We summary the kernel filters of GCN, SGC, and HKGCN in Table 1. In Figure 2, we use the eigenvalues of L̃ to illustrate the effects of different 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−λ)k, it monotonically increases when λ ∈ [1, 2]. In other words, the kernel filter of GCN acts as a band-stop filter, attenuating eigenvalues near 1.
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):
λk = ∑
(vi,vj)∈E
Ãij [ 1√ D̃ii uk(i)− 1√ D̃jj uk(j)] 2
(14)
This means that similar to classical Fourier transform, those eigenvectors associated with high λ oscillate more rapidly than those associated with low λ. And we know that L̃ = ∑n i=1 λiuiu T i , where uiuTi is the projection matrix project to ui. Since the eigenvector ui oscillates more rapidly as the increase of i, the projection matrix uiuTi will also globally oscillate more rapidly as i increases. Because the filter kernel follows g(L̃) = ∑n i=1 g(λi)uiu T i , the larger g(λi) is, the greater influence on g(L̃) will uiuiT have. We show above that as i increase, the oscillation of uiuTi also increase. Since Y = g(L̃)X, an oscillating g(L̃) will cause oscillating output Y. Therefore, we want the influence of higher i’s uiuTi as small as possible, i.e. large i’s g(λi) as small as possible. This explains why we need a low-pass filter.

heading: 3.6 COMPLEXITY ANALYSIS
text: For the preprocessing step, the time complexity for matrix multiplication between the sparse Laplacian matrix and the feature vector in Chebyshev expansion is O(d|E|), with |E| is the number of edges
and d is the dimension size of input feature. Thus, the time complexity of the preprocessing step is O(kd|E|), with k is the Chebyshev expansion step. For prediction, the time complexity of logistic regression is O(|VU |dC) with |VU | is the number of unlabeled nodes, and C is the number of label categories.
The space complexity is O(|E|+ nd), where n is the number of nodes.

heading: 4 EXPERIMENTS

heading: 4.1 EXPERIMENTAL SETUP
text: We follow the standard GNN experimental settings to evaluate HKGCN on benchmark datasets for both transductive and inductive tasks. The reproducibility information is detailed in Appendix.
Datasets. For transductive learning, we use Cora, Citeseer and Pubmed (Kipf & Welling, 2017; Veličković et al., 2018). For inductive tasks, we use Reddit (Hamilton et al., 2017), ogbn-arxiv (Hu et al., 2020), and a new arXiv dataset collected by ourselves, which contains over one million nodes and 10 million edges. In 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://ogb.stanford. edu/docs/nodeprop/). It is the citation network between computer science arXiv papers and the task is to infer arXiv papers’ categories, such as cs.LG, cs.SI, and cs.DB. 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
test. Inspired by ogbn-arxiv, we also constructed a full arXiv paper citation graph from the public MAG (https://docs.microsoft.com/en-us/academic-services/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 2.
Baselines. For the transductive tasks on Cora, Citeseer, and Pubmed, we use the same baselines used in SGC (Wu et al., 2019), including GCN (Kipf & Welling, 2017), GAT (Veličković et al., 2018), FastGCN (Chen et al., 2018), LanczosNet, AdaLanczosNet (Liao et al., 2019), DGI (Veličković et al., 2019), GIN (Xu et al., 2019b), and SGC (Wu et al., 2019).
For the inductive tasks, we use supervised GraphSage (mean) without sampling (Hamilton et al., 2017), GCN (Kipf & Welling, 2017), ClusterGCN (Chiang et al., 2019), GraphSaint (Zeng et al., 2019), MLP, and SGC (Wu et al., 2019) as baselines.
For the proposed HKGCN, the propagation time t̃ is preset based on the performance on the validation set. On Reddit, we follow SGC (Wu et 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, for which we use adam optimizer (Kingma & Ba, 2014), same as the other baselines.

heading: 4.2 RESULTS
text: 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 on Cora, Citeseer, and Pubmed, as well as the relative running time on Pubmed. As the reference point, it takes 0.81s for training HKGCN on Pubmed. Per community convention (Kipf & Welling, 2017;
Veličković et al., 2018), we 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 on a NVIDIA TITAN Xp GPU.
We can observe that 1) HKGCN outperforms 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 using 2–3 orders of magnitude less time than all baselines except FastGCN and SGC.
In addition, it is easy to notice that comparing to complex GNNs, the performance of HKGCN (and SGC) is quite stable across 100 runs, as it benefits from the the simple and deterministic propagation.
Inductive. Table 4 summarizes the performance of inductive tasks on large datasets, including both test accuracy and relative running time with HKGCN’s as the reference points. Most reported results are averaged over 10 runs, except the supervised GraphSage (mean) and SGC methods’ accuracies on Reddit, which are directly taken from the SGC work (Wu et al., 2019).
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 on Reddit, arXiv, and ogbn-arxiv, respectively, indicating the lack of universally-best GNN models.
Efficiency wise, HKGCN costs 2.2s, 48.5s, and 5.2s on three datasets, respectively, which are similar to SGC, both of which are clearly more efficient than other GNN models as well as MLP.
Analysis of t̃. In HKGCN, t̃ determines how long the feature propagation lasts for. A larger t̃ can amplify global features and a lower one can emphasize local information. From Figure 3, we can observe that t̃ has a similar impact on different datasets, and as the propagation time increases, the model at first benefits from information from its local neighbors. However, as the feature propagation continues (e.g., t̃ > 9 or 12), the performance of the model starts to decrease, likely suffering from the over-smoothing issue (Li et al., 2018).

heading: 5 CONCLUSION AND DISCUSSION
text: 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 is 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 it to overshoot the convergence point and causes oscillated propagation. Furthermore, we show that
heat kernel in HKGCN acts as a low-pass filter. On the contrary, the filter kernel of GCNs fails to attenuate high-frequency 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 t. Consequently, the HKGCN model could avoid these oscillation issue and propagate features smoothly. Empirical experiments on 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-magnitude faster training than GCNs.
Notwithstanding the interesting results of the present work, there is still much room left for future work. One interesting direction is to learn the propagation time t from data in HKGCN for automatically balancing information between local and global features.

heading: A REPRODUCIBILITY INFORMATION
text: A.1 HYPERPARAMETERS
We introduce the hyperparameters used in the experiments, including weight decay, #epochs, learning rate, t̃, and optimizer, which are also summarized in Table 5. The Chebyshev expansion step k 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, we fix the weight decay to 5 × 10−6 and search t̃ from {0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30} based on the performance on the validation set. Then we fix the best performance t̃ and search the weight decay from {10−6, 10−5, 10−4} based on the performance on the validation set. Reddit dataset. We follow SGC (Wu et al., 2019) to 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 t̃ from all non-negative integers equal or lower than 15, based on the performance on the validation set.
arXiv and ogbn-arxiv datasets. We use the Adam optimizer with no weight decay to 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 t̃ 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 t̃. If t̃ is greater than 10, the floating point precision error would become an issue in calculating the Bessel function. Therefore, in practice, we convert e(−L̄t̃) into e(−L̄ t̃ 3 )e(−L̄ t̃ 3 )e(−L̄ t̃ 3 ).
Situation for Very Large Graphs. Though the Chebyshev expansion is very close to the minimax polynomial on the range of [−1, 1] and thus makes it converge very fast, the recurrence relation in Eq. 13 is second-order. In other words, the calculation of Ti+1(x) needs to store Ti(x), Ti−1(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. 7 as X(t+∆t) = (I−∆tL̃)X(t) for the calculation. In this way, we only need to store Xt 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
t̃ 12 9 15 6 6 8 weight decay 10−5 10−4 10−5 n/a 0 0
#epochs 100 100 100 2 500 1000 learning rate 0.2 0.2 0.2 1 0.2 0.2
optimizer adam adam adam l-bfgs adam adam
A.2 BASELINE METHODS
Per community convention (Kipf & Welling, 2017; Veličković et al., 2018), the results of baselines in the three citation networks (Cora, Citeseer, and Pubmed) are taken from existing publications (Wu
et al., 2019). The hyperparameters settings of inductive tasks on three large datasets (Reddit, arXiv, and ogbn-arxiv) are introduced as follow.
SGC. To make a fair comparison, we select K in SGC based on the performance on the validation set, which has similar meaning as t̃ in HKGCN.
GCN. The learning rate is set to 0.01 on all datasets. The weight decay is 0. The number of layers is 3 on Reddit and ogbn-arxiv, and 2 on arXiv because of the GPU memory limit. The hidden layer size is 256 on Reddit and ogbn-arxiv, and 128 on arXiv also due to memory limit. The number of epochs is 500.
GraphSage. Results on the Reddit dataset are directly taken from the SGC paper (Wu et al., 2019). The other parameter settings are the same as GCN above. We use the mean-based aggregator as it 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 is 128, which are the same parameter settings as the original SGC paper (Chiang et 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 15 (as a large number would cause an unknown bug in the PyTorch-Geometric 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 is 0.2, the same parameter settings as used in SGC (Zeng et al., 2019). 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 t
Algorithm 1 Preset t in HKGCN
Input: input features X; feature propagation duration time t̃; Chebyshev expansion step k; scaling augmented normalized Laplacian L̄ = L̃/2; Bi(t) is the modified Bessel function. Output: pre-processed features X(t); T0(x)← X; X(t) ← B0(t̃)T0(x); T1(x)← L̄X; X(t) ← X(t) − 2B1(t̃)T1(x); for i = 2...k do Ti(x)← 2L̄Ti−1(x)− Ti−2(x); if i is odd then
X(t) ← X(t) − 2Bi(t̃)Ti(x); else
X(t) ← X(t) + 2Bi(t̃)Ti(x); end if
end for
C PROOF OF EQ. 14
λk = u T k L̃uk
= uTk (I− D̃− 1 2 ÃD̃− 1 2 )uk
= ∑
i∈{1,...,n}
uk(i) 2 − ∑ (vi,vj)∈E 2Ãij√ D̃iiD̃jj uk(i)uk(j)
= ∑
(vi,vj)∈E
Ãij [ 1√ D̃ii uk(i)− 1√ D̃jj uk(j)] 2

Review summaries:
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.

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.