Structure-Aware Random Fourier Kernel for Graphs
Authors: Jinyuan Fang
Qiang Zhang
Zaiqiao Meng
Shangsong Liang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Structure-Aware Random Fourier Kernel
Gaussian Process
Graph Learning
Random Fourier Feature

Abstract: Gaussian Processes (GPs) define distributions over functions and their generalization capabilities depend heavily on the choice of kernels. In this paper, we propose a novel structure-aware random Fourier (SRF) kernel for GPs that brings several benefits when modeling graph-structured data. First, SRF kernel is defined with a spectral distribution based on the Fourier duality given by the Bochner's theorem, transforming the kernel learning problem to a distribution inference problem. Second, SRF kernel admits a random Fourier feature formulation that makes the kernel scalable for optimization. Third, SRF kernel enables to leverage geometric structures by taking subgraphs as inputs. To effectively optimize GPs with SRF kernel, we develop a variational EM algorithm, which alternates between an inference procedure (E-step) and a learning procedure (M-step). Experimental results on five real-world datasets show that our model can achieve state-of-the-art performance in two typical graph learning tasks, i.e., object classification and link prediction. 

Structure-Aware Random Fourier Kernel for Graphs
Jinyuan Fang!?? 1.2, Qiang Zhang2:4.5 Zaiqiao Meng"., Shangsong
1,2,7 Liangl.2,7+
School of Computer Science and Engineering, Sun Yat-sen University, China Guangdong Key Laboratory of Big Data Analysis and Processing, Guangzhou, China Hangzhou Innovation Center, Zhejiang University, China A College of Computer Science and Technology. Zhejiang University, China
AZFT Knowledge Engine Lab, China
School of Computing Science University of Glasgow, United Kingdom
Mohamed bin Zayed University of Artificial Intelligence, United Arab Emirates
(fangjy6dgmail. com; qiang. zhang csúzju edu. en; zaiqiao. www.omeeeennnaa.eee.eeeee.e.. com) (1 iiiagghangoongggaal....
Abstract
Gaussian Processes (GPs) define distributions over functions and their generaliza- tion capabilities depend heavily the choice of kernels. In this paper, we propose a novel structure-aware random Fourier (SRF) kernel for GPs that brings several benefits when modeling graph-structured data. First, SRF kernel defined with a spectral distribution based on the Fourier duality given by the Bochner's theo- rem, transforming the kernel learning problem distribution inference problem. Second, SRF kernel admits a random Fourier feature formulation that makes the kernel scalable for optimization. Third, SRF kernel enables leverage geometric structures by taking subgraphs as inputs. To effectively optimize GPs with SRF ker- nel, we develop variational EM algorithm, which alternates between an inference procedure (E-step) and learning procedure (M-step). Experimental results on five real-world datasets show that our model can achieve state-of-the-an performance in two typical graph learning tasks, i.e., object classification and link prediction.
Introduction
Gaussian Process (GP) a typical Bayesian non-parametric method for function learning. Choosing appropriate kernels profoundly improves the generalization performance of GPs on various learning tasks 22. Stationary kernels, such as Radial Basis Function (RBF) kernel, are common choices of GP kernels and have been successfully applied in many regression and classification problems 33 5) However, due to their restricted smoothness assumption and the limited expressiveness, stationary kernels may not be capable for complex data structures, such graph- graph-structured data (6], where both object features and geometric structures are essential.
To improve GP's performance on data with complex structures, some expressive kernels have been proposed. Two typical expressive kernels are: compositional kernels 7 g 9 which are obtained
based on the kernel composition rules [10. and deep kernels [2]. which are defined as the stack
of a deep neural network and a base kernel. Alternatively, the spectral kernels are defined in the
spectral domain 22] 3 [4]. Nonetheless, when modeling graph-structured data, prior kernels face several challenges. First of all, the flexibility and expressiveness of these kernels are limited by the simple base kernels upon which they are built, and the optimization of base kernels is computationally expensive [1). Second, these kernels are usually reature-based which indicates that they capture the similarities between graph objects based solely object features. It may be inefficient for them to
"Correspondigg Author.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

capture the structural smoothness in graph data, i.e., neighboring objects tend to share similar function values (6. However, capturing such structural smoothness is critical to the success of many graph learning methods [6 17 [8] In another line of work, structure-based Laplacian kernels [19 20 21
have been proposed to model functions over graphs. They are obtained by applying transformation functions to the graph Laplacian matrices. However, they rarely utilize the object features and may be suboptimal to model complicated functions over large-scale graphs
To tackle the aforementioned challenges, we propose a Structure-aware Random Fourier (SRF) kernel, which is both feature- based and structure-awes aware. To improve the kernel expressiveness, inspired by the Bochner's 's theorem [22], we define SRF kernel with a spectral distribution based on the Fourier duality between the kernel and the spectral distribution. This definition brings some benefits: (1) the SRF kernel converts the kernel learning problem into a distribution inference problem. and the resulting SRF kernel will be fairly expressive if the dual spectral distribution is adequately complex; (2) the SRF kernel admits random Fourier feature formulation for scalable learning, which leads to a linear computational complexity with respect to the number of data points. Compared with feature-based kernels and Laplacian kernels, SRF kernel enables to leverage both object features and local geometric structures to measure similarities by taking subgraphs as inputs. Moreover, to effectively optimize the GPs with proposed SRF, abbreviated as GPSRF, we develop a variational Expectation- Expectation-Maximizzttoo Maximization (EM) method [23], which alternates between an inference procedure (E- step) for posterior inference and a learning procedure (M-step) for parameter learning. It's empirically verified that GP with SRF kernel can achieve superior performance than GPs with feature- based kernels or Laplacian kernels when modeling graph-structures data.
Our contributions can be summarized as follows: (1) We propose novel SRF kernel for modeling functions over graphs, which enables to leverage both geometric structures and object features. (2) Based on the SRF kernel, we propose a GP model, GPSRF, for graph learning tasks. (3) To effectively pnpectation-Maxiiizaainn
optimize GPSRF, we develop variational results on five real-world graph datasets show that GPSRF can outperform strong baselines in two typical graph learning tasks, i.e., object classification and link prediction.
algorithm. (4) Experimental
2 Related Work
Gaussian Processes and Kernel Learning for Graphs. GP models for graph-structured data have been widely studied. They have been proposed for different learning tasks, such as object classifica- tion 18), link prediction [66 27], user profiling [2] 29 30) and graph classification BT Nonetheless, the kernels applied in these methods are feature-based, which may be suboptimal in capturing the local structural smoothness in graph data. contrast, the structure-based Laplacian kernels [19 20 21 capture object similarities based on the geometric structures. However, they rarely utilize the rich object features and may not be capable enough to model the complicated functions over large-scale graphs. Our GPSRF differs from these works in that: (1) the SRF kernel in GPSRF is both basturreebbaedd and structure- aware; (2) the random Fourier feature formulation of our GPSRF enables efficient optimization with reduced computational complexity.
Similar to this work, the graph convolutional kernel 32 proposes to incorporate graph convolution network in kernels to leverage local structure information. However, the variational inducing point method (33] used in 32) for posterior inference has a higher computational cost than our GPSRF (see Appendix E.6 for empirical results). In a different manner, the deep spectral kernel network (DSKN) 34 proposes to form an expressive kernel by staking multiple layers of base kernels, while we propose to define an expressive SRF kernel with a complex spectral distribution. The kernel graph convolutional network (KGCN) [35] proposes to learn graph representations with graph kernels and then uses the convolution network to deal with the graph classification task. By contrast, our GPSRF uses graph neural network to obtain SRF kernel and then leverages the Gaussian Process to handle the graph learning tasks.
Another line of research that is closely related to ours the graph kernels (36,, which are kernel functions between pairs of graphs. The graph kernels measure similarities between two graphs for graph classification tasks, whereas our SRF kernel measures similarity between two objects in a single graph for the node-oriented tasks such as object classification and link prediction. Of special interest to us is the neighborhood aggregation based graph kernels such as Weisfeiler-Lehmme kernels 37 38 39], and the subgraph pattern based kernels 41). These two kinds of graph kernels

---

are both defined based on the subgraph structures. Our SRF kernel differs from them in number of ways. First, the neighborhood aggregation based graph kernels aggregates the neighborhood's label information while our SGK kernel aggregates the neighborhood information based on the continuous feature vectors. In our remi-supervised setting, where the labeled data is scarce, is infeasible to straightforwardly apply these graph kernels to our problem. Second, the subgraph pattern based graph kernels proposes to measure the similarities between two graphs by counting the occurrences of subgraph patterss (graphlets) of fixed size. These graph kernels, which are obtained based only on graph structures, do not consider any labels or feature vectors. It is also computationally expensive to find all the subgraph patterns (graphlets) in graphs. By contrast, our SGK kernel measures similarities between nodes by aggregating the L-hop neighborhood's ' feature information using an aggregation function, and it is also more computationally efficient to obtain these subgraph representations.
a powerful technique for kernel It has been successfully applied to address the high computational cost Typically, the sparse spectrum GP (SSGP) 47 proposes to directly optimize spectral points along with the hyperparameters. The variational method used in (48) infers the posteriors over the frequencies of the kernel to avoid potential overfitting of SSGP. In comparison, we learn the SRF kernel by inferring the spectral distribution in data-driven way, which makes the learnt kernel more flexible.
Random Fourier Feature. The random Fourier feature (RFF) 43
approximation 44
45
46
of GPs 43
49
We would like to clarify the differences between RFF and our SRF kernel. The RFF is technique to approximate a pre-defined kernel function, which requires calculating the spectral distribution of the pre-defined kernel function through the Fourier transform (we refer to 4 or Appendix A for more details about RFF). We emphasize that for most complex kernel functions, it is not feasible to obtain the corresponding spectral distributions due to the intractability of Fourier transform. This is also the reason why RFF is only applicable to a small range of simple kernel functions so far, such as RBF kernel and arc-cosine kernel. By contrast, our SRF kernel is kernel function directly defined with a spectral distribution (we define SRF kernel with a hierarchy Bayesian distribution in our paper) based on Bochner's ' theorem. Similar ideas have also been explored to obtain time embedding (50). The definition of SRF kernel sidesteps calculating the potentially intractable spectral distribution. Also, we can obtain complex and expressive kernel by defining a complicated spectral distribution. Henee, we generalize RFF to a family of complex and expressive kernel functions, i.c., SRF kernels.
Graph Neural Networks. Graph neural networks (GNNs) have been proposed for graph learning. They leverage both graph structures and features to learn useful representations, and have achieved state-of-the-art performance in some graph learning tasks [16 17 51 52 53 54 [55. Compared with GNNs, which are parametric deterministic models, our GPSRF a Bayesian non-parametric GP model. Moreover, GPSRF enables to incorporate background knowledge by selecting proper kernel function, and obtain uncertainty estimations of predictions, which are infeasible for GNNs.
Preliminaries
3.1 Gaussian Process with Random Fourier Feature
Gaussian Process defines a distribution in a function space, which assumes that the marginal distribution over function values of any finite inputs is Gaussian. Specifically, a GP places prior distribution over functions, i.e., f(x) GO (o x') æ²)), where kif x') E R denotes the kernel (covariance) function with parameters 9 between x, x' E R. One critical challenge of GPs is the cubic computational cost incurred by the inverse of kernel matrix in posterior inference [10] To address the challenge, the random Fourier feature (RFF) method has been proposed for scalable learning 43 45]. Based on the Bochner's 's theorem (22], the RFF method proposes to approximate kernels with explicit feature mappings 43) Specifically, for ihift-invariant ker-
nel (2, x²) Ke (r), where r = x x', the Fourier duality between the kernel and spectral
distribution [0 enables to define an explicit feature mapping function:
2 MM
M
(x)
V
cos cos c2 m + bm)))
m=1
such that the inner product between the feature maps is an unbiased estimate of the kernel function, i..., ko (r) Ri (xr) (ax). In Eq. ( wm RRF and bm are samples drawn from the spectral distribution p(w) and the uniform distribution Onif(0, 2m]] respectively, and M represents the total
3

---

number of samples. The features obtained with dw is referred to as the random Fourier features More details about RFF can be found in Appendix A.
43
When modeling graph-structured data with GPs, in addition to the inference problem, it is nontrivial choose suitable kernel function as: (1) the RFF method is limited a small range of kernels since it requires to calculate the spectral distribution, which is not always feasible due to the intractability of Fourier transform; (2) a majority of GP kernels are feature-based, which capture similarities based solely on features, making them inefficient in capturing the local geometric structures in graphs.
3.2 Graph Neural Network
Recently, graph neural networks 16 ometric structures for graph learning. They aim to learn object representations by capturing the structural information within the neighborhoods of these objects. Specifically, they follow an iterative aggregation (message passing) scheme to update the object representations. For an L-layer GNN, the update function at the l-th layer is represented as:
51
42 have been proposed effectively leverage ge-
by ( (C (1-) :je Ne(i))),
COMBINE (1-1) b (()).
where h, is the embedding object i at the 1-th layer with h (0) z; Ne(i) a set of adjacent objects to Us and AGGREGATION()) and COMBINE()) are the component functions of GNN. Compared with GPs, GNNs suffer from several drawbacks: is difficult for GNNs (1) incorporate background knowledge of the learning problem and (2) estimate uncertainties for predictions.
4 Task Formulation of Graph Learning
Graph-structured data are ubiquitous in the real world with variety of applications, such as object classification [16) and link prediction (56). In this paper, we instantiate graph learning with the task of object classification in the semi- semi-supervised setting, as many other applications can be reformulated into this task [57] Let g (V, &, X, Y') represent a partially-labeled graph where = (v, N is set of objects, & is a set of edges and N is the total number of objects. The object features are denoted as X E IR NxF where F is the feature dimension. The labels Y E R NxC are in the one-hot form, where N₁ and C' represent the number of labeled objects and the number of classes, respectively. Given the partially-labeled graph, the goal of object classification to predict the labels of the remaining N,, unlabeled objects, i.e., Y E NC
5 Structure-Aware Random Fourier Kernel
To address the aforementioned issues of GPs on graph-structure data (Section 3.1) 1. we propose novel Structure-awar Random Fourier (SRF) kernel. We introduce the kernel this section and detail a GP model with this kernel in next section.
5.1 Random Fourier Kernel
The Bochner's theorem 22 states that the Fourier transform of positive finite measure a positive definite shift-invariant kernel. Moreover, when the kernel is properly scaled, the measure has density [43], called the spectral distribution p(w). Inspired by the Fourier duality between the kernel and the spectral distribution, we propose to define kernel function with spectral distribution, which we refer to as the Random Fourier (RF) kernel. The RF kernel advantageous in that: (1) RF kernel naturally enables random Fourier feature (RFF) formulation for scalable kernel learning; (2) RF kernel transforms the kernel learning problem to the distribution inference problem, i.e., we can learn an appropriate kernel for data by inferring proper spectral distribution, and the resulting kernel will be fairly expressive if the dual spectral distribution is adequately complex.
To clarify the first point, it is worth noting that RF kernel is a kernel function defined with spectral distribution while RFF is method for approximating a kernel function. Compared with other kernels, it is convenient for RF kernel to leverage RFF for scalable learning, as it is unnecessary to compute

---

the potentially intractable spectral distribution from the kernel function. The second point states that we can obtain an expressive kernel by defining a complicated spectral distribution. For example, the spectral mixture (SM) kernel [2] can be considered as a special case of RF kernel by setting the spectral distribution as mixture of Gaussians. Compared with SM kernel, our RF kernel more general as the spectral distribution can take on many forms, and the resulting kernel function may not have a closed-form solution, which motivates us to utilize RFF for approximation.
To efficiently infer the spectral distribution, it is convenient to define the spectral distribution as reparameterizable distributions [58], such as Gaussians. However, they may not be rich enough to represent expressive kernels. For examples, the unimodal reparameterizable distributions are difficult to reconstruct the kernels whose spectral distributions are multimodal. To obtain a flexible and expressive kernel for the complicated functions over graph data, we define the spectral distribution in hierarchical Bayesian manner: po Po(w) = (wwle) where is the parameters of the conditional distribution and p(e) is the base distribution. The dependence of conditional distribution po(wle) on random variable can be arbitrarily complex. To enable efficient optimization of 0, we assume that the conditional distribution pa (wl E) is reparameterizable (such as Gaussian or exponential distributions). As a result, we can obtain samples from the conditional distribution by drawing an auxiliary variable and obtain w deterministic function (-))) of the sampled u,
~ p(e), p(u), ho(u;
With the spectral points sampled from the spectral distribution, i.e., w. we can utilize the RFF, which is defined in Eq. @ to approximate the RF kernel. Consequently, the RF kernel between two objects is given by: (ot; = d5ه x; ) dw my ). By learning the parameters of the spectral distribution (ow in a data-driven way, we are able to implicitly learn a flexible and expressive kernel function.
5.2 Structure-Aware Random Fourier Kernel
Despite the RF kernel is expressive and scalable, it is still feature-basse and may be inefficient in capturing the local geometric structures graphs. To address this issue, we further propose a Structure-awar Random Fourier (SRF) kernel, which is RF kernel that takes L-hop subgraphs centered at the objects as inputs. Specifically, the SRF kernel between two objects is defined as:
U1) Ko (o( )((()) dwl (o(G))) T (GG))
(5)
where g = E -V,,, { represents the L-hop subgraph centered at object 8, with V..
E, being the set of objects and edges, respectively. The subgraph aggregation function g outputs subgraph representations. The SRF kernel is general framework as we can consider diverse subgraph aggregation functions, such summation, pooling operation (59) and graph kernels [60] Inspired by the success of GNN in aggregating the neighborhood information, we set as an I--lyer graph neural network (defined in Eq. (3). We use the node-level representation of node v; output by GNN as the result of function g( ). With the representational power and learning biases of GNNs, is
supposed effectively capture the local geometric structure of objects.
6 Gaussian Process Model with SRF Kernel
After developing a novel SRF kernel, we equip GP with this kernel for graph learning, that is GPSRF (Section 6.1. To efficiently optimize GPSRF, we develop variational EM algorithm (Section 6.2p
6.1 Graph GP Model
We define a vector- valued stochastic function f RF - R over graph graph-structured data, where D is the output dimensions. The joint probability of our graph GP model is defined as: Po F|X, E) (F E) I po PY,Y, where Y YY: Y"I and F f(X) represent the labels and function values of all the objects, respectively. The likelihood function in our model is defined with the softmax
exPs (Y..F.)
function in the following way: pe (F. = 5: (e..F"..F.)) where e, is the indicator vector with the e-th element being 1 and the remainder 0. The stochastic function is assumed follow a GP prior. By using the proposed SRF kernel, this GP prior is given by:
pe (F = (FFF; 0, 46 7)
(6)
5

---

where Φ = -ow (hi)..... ow ow (bx)]" and h; = " for all i = ,....,,,, N. It is well-known that GP equivalent to Bayesian linear model with basis functions (b): X - H. which transforms the features into high (possibly infinite) dimensional Hilbert space H such that the kernel ko hj) can expressed as the inner product of basis functions in Hilbert space [Q]] i.e., ko (h;, h,) (w,)), (b;))) xt We propose approximate the basis functions & with the random Fourier feature maps &w such that: (h,), (H))) se (ow (h.), Dw (hy) ()a)) Consequently, the GP-distributed function f can be equivalentyy represented as: F; f(h;) A @w (h.), where A = [ar,..... ap) and (0, lar) for all d = I..... D. We refer to A as the random Fourier feature coefficients of the kernel-dependent feature mappings ow-
6.2 Variational EM
With the random Fourier feature formulation of our GPSRF, the joint distribution is equivalently represented as: pol Po(Y, X) po( (Y X) p(A). Note that Y represents the labels of all the objects and we omit the dependence on network structure & for clarity. To make predictions for the unlabeled objects, we need to infer the posterior pe A Y Y"), which is intractable for our multi-classification model. To address this issue, we develop a variational Expectation ExpeetationMMxxiizzatooo (EM) algorithm [2 (57. Specifically, we introduce variational distributions over latent variables 4p (A, Y X) = 44 A Po(
Y A, X). The log-likelihood of observations can be rewritten as:
P(A)
log X (A)(
logpe( Y X) + log
(7)
4o ()
C(8,0iX,Y0
where the expectation term, i.c., [(0, yo; X, ). is the Evidence Lower BOund (ELBO), and the full derivation can be found in Appendix B. According to variational EM, the model parameters, i.e., yp and 0, are alternatively learned through an inference and learning procedure.
Inference Procedure. In the inference procedure (E-step), the model estimates true posteriors latent variables po (A, Y [X Y'). Following the principle of variational EM (3), we fix Pa and update the variational distributions approximate the true posteriors. We further define the variational distributions over latent variables as Gaussian distributions, i.e., (A) IT N(aa; ma. Sa). Consequently, the variational parameters at step are optimized as:
kp arg min KI. (1. (A, Y X) || Pe Pallp---AAA (A, YLA, X, Y'))
arg min KL (1-0 Y')..
(8)
According to Eq. 7 minimizing this KL divergence is equivalent to maximizing the ELBO, hence can optimize the variational parameters by maximizing ELBO using the stochastic back propagation and reparameterization trick [58), where the generative parameters gr-1 are kept fixed.
Learning Procedure. In the learning procedure (M-step), the goal to update the generative parameters 0. Specifically, we will fix Up and update po at step as:
0f arg max E. (A.Y-IX) log pa Y A[X)]
arg max E. (A.Y-IX) log PO A X)] + const.
To effectively optimize the parameters, i.e., ;o and 0, we first pre-train the inference model q, for few steps and then perform alternate optimization between an inference procedure and a learning procedure, following the previous work [57]. Also, the subgraph transformation function g is learned in conjunction with model parameters. Such joint learning can make our model more adaptive to the training data and obtain better performance. After optimization, the labels of the unlabeled objects can be predicted with the generative model The pseudo codes can be found in Appendix C.
7 Discussions
Computational Complexity. The time complexity of GPSRF (NN D)), where M, F, D represent the the number of samples from p(w), the dimension of subgraph representations (i.c., h)

---

MNIST
Original
7
2
5
8
3
GF-RBF
7
2
5
g 8
GP DK
7
2
5
3
GPSRF
7
2
5
8
3
(a) 1-D regression results
(b) 2-D regression results
Figure/ 1: (a) The I-dimension regression results of the proposed RF kernel ko (left) compared with the RBF kernel (middle) and deep kernel (right). The gray-dot points are the noisy training data, the red lines are the ground-truth, the blue lines are the interpolation results of different kernels, and the shaded areas represent 2- standard deviations. (b) Pixel intensity (2-dimension) regression on MNIST. Each row represents the predictions of GP with a specific kernel on different digits.
and the dimension of the output of function f. respectively. Compared with the GPs with variational inducing point methods (3] for optimization, which has a time complexity of O(N D(P + p2 F)), where P is the number of inducing points, our method can reduce the time complexity. Since the likelihood function of GPSRF factorizes across observations, we can sample a mini-batch of data for training. In such case, the time complexity can be further reduced to O(SM + D)), where S < N mini-batch size. The empirical results in Appendix E.6 also validate that GPSRF has reduced time complexity.
Applications. Despite GPSRF is presented with the instance of semi-supervised object classification task, it can be easily extended to other graph learning tasks by modifying the likelihood function. For example, it can be naturally applied to the link prediction task [6] 62). where the model is given partially observed links and the goal is to predict the remaining links. The link prediction task also be regarded Specifically, for an edge Eij between two objects, we can concatenate the function values these two objects, i.e., F; and F,, as the function values for the edge. By replacing function values of objects with those of edges in likelihood function, we can obtain GPSRF for link prediction task.
classification task where each link is treated binary random variable.
The pseudo-label perspective of the learning procedure. In the learning procedure of variational EM algorithm, we need to sample labels of unlabeled objects from the variational distribution (A, Y X) for updating the generative parameters 6. If we sample the label of each unlabeled object as the class that has maximum probability in the variational distribution, our method is closely related the pseudo-label technique [63], which labels each unlabeled object with the class that has the maximum predictive probability and use both the true labels and the pseudo-labels to update the model parameters. Compared with the pseudo-label technique where the pseudo-labels are kept fixed after pre-training stage, the "pseudo-labels" in our method are dynamically sampled from the variational distribution each iteration. Moreover, our method only use the "pseudo-labels" in learning procedure (M-step) while in the inference procedure (E-step), only true labels are used. From this perspective, similar to some pseudo-label techniques (64] which only use an unlabeled object for training when its maximum predicted probability is above a certain threshold, we can also introduce a threshold т and only include the comparatively accurate "pseudo-labels labels" for optimization. Empirically, we found GPSRF achieves better performance when introducing the threshold 7 as it can alleviate the overfitting problem in semi-supervised setting (see Section 8.3 for details).
8 Experiments
To examine the proposed kernel and GP model, we study the following research questions. (RQI) How does the RF kernel ko (defined in Section 5.1) perform in regression tasks compared with existing kernels? (RQ2) Can GPSRF outperform baselines in the graph learning tasks, such as semi-supervised object classification and link prediction? (RQ3) How does the number of samples from spectral distribution M affect the performance of GPSRF? (RQ4) What are the effects of each component, i.e., subgraph aggregation function and RF kernel ko. in our SRF kernel? In addition to these research questions, further experimental results can be found in Appendix E.
7

---

Table 1: Classification accuracies (%) of GPSRF and baselines different datasets. The best and second best performance under each dataset marked with boldface and underline. respectively.
Category
Method
Cora
Citeseer
Pubmed
Photo
Computers
GP-RBF
60.8 = 0.3
55,4 t 0.3
74.2 = 0.5
82.4 = 0.2
68.8 : 0.5
GP-SM
63.1 = 0.3
58.0 + 0.4
75.1 = 0.4
86.8 = 0.3
71.2 : 0.6
GP
GP-DIF
68.1 1.1:000 0.4
47.9 0.4
65.3
77.8 0.6
63.4 0
GP-DK
72.6 1.0
60.4 0.6
76.2 0.8
90.3 0.4
74.5 + 0.9
GGP
81.1 + 0.5
69.3 0.4
76.7 + 0.4
91.2 0.3
79.7 + 0.8
GraphSAGE
80.6 0.3
68.6
77.9 +.2
84.7 0.7
78.5 + 1.1
GCN
81.4 0.5
70.3 0.7
78.9 0.3
88.2 +.44
83.0 + 0.8
GNN
GAT
82.8 +.8+00 0.7
72.1 0.4
79.2 0.2
85.3 + 0.4
75.6 + 0.7
DGI
82.3 + 0.6
71.5 0.7
78.4 + 0.5
90.8 0.9
82.1 + 1.2
w/o
81.9 + 0.6
71.4 + 0.5
78.7 + 0.4
91.9 + 0.4
85,8 + 0.8
GPSRF
with
83.6 0.3
72.7 0.5
79.6 0.5
92.2 + 0.3
86.5 + 0.2
Cora
Photo
1.50
1.0
GPSRF with (Training)
GPSRF with
(Training)
1.25
GPSRF with (Validation)
0.8
GPSRF with (Validation)
1.00
GPSRF w/ (Training)
GPSRF w/o (Training)
0.6
0.75
GPSRF (Validation)
GPSRF w/o1 (Validation)
0.4
0.50
0.25
0.2
0.00
0.0
0
100
200
300
400
500
0
100
200
300
400
500
Steps
Steps
Figure 2: Training and validation loss of GPSRF under different settings on Cora and Photo datasets.
8.1 Experimental Settings
To evaluate GPSRF in graph learning tasks, we conduct experiments on three benchmark citation networks 665, including Cora, Citeseer and Pubmed, and two Amazon product co-purchase net- works (66.. including Photo and Computers. We use the standard split of the citation networks [16]. For the co-purchase networks, we randomly select 20% of nodes as training nodes, 10% of nodes as validation nodes and the remaining nodes are treated as test nodes. In object classification tasks, we take GP models with different kernels as baselines, including the RBF kernel, the SM kernel (2), the Laplacian kernel [19] and the deep kernel [12]. which are denoted as GP-RBF, GP-SM, GP-DIF and GP-DK, respectively. Moreover, we also compare against some strong graph learning methods, including GCN 116., GraphSAGE 117, GAT (51), DGI [67] and GGP [8]. For link prediction, take node2vec (68), GAE/VGAE 61 and GraphSAGE as baselines. Throughout the experiments, to enable mini-batch training, we set the transformation function g two-layer GraphSAGE network with mean aggregator, where both the aggregation function in Eq. 2 and the combination function in Eq. (3) are mean functions. As for the RF kernel function kg. we set the base distribution p(e) as the standard Gaussian and use the Gaussian conditional po (w(l)) N(w;; no (o(E), ( oo)))), whose mean and variance are parameterized with neural networks. The parameters of our model are learned with the Adam optimizer [69] through alternating steps of an inference procedure and a learning procedure. More details about experimental settings of our GPSRF and baselines are provided in Appendix D.
8.2 Results for Answering RQI: Regression Tasks
To examine the performance 1-D regression and 2-D regression tasks. Specifically, for 1-D regression task, the goal is to fit target ops Szresin 3r. with some noisy observations. We randomly select 200 data-points in the
kernel ko we compare with RBF kernel and deep kernel in both
function y = Ix +
range of [-3,3] 3] and add noises to their function values, which are drawn from (O, 0.01), to obtain the training set. The regression results are presented Figure [(a) shows that, compared with
RBF and deep kernels, the shape of function produced with RF kernel can better match the shape of target function, especially on the region where the training data are sparse. To further examine the
expressiveness of RF kernel, we apply it on more complex 2-D regression task. Following [70),
8

---

Table 2: Link prediction performance (AUC) (%) of GPSRF and baselines on different datasets.
Method
Cora
Citeseer
Pubmed
Photo
Computers
node2vec
81.3 + 0.3
79,6 + 0.5
87.7 1 0.1
83.14 0.4
79.5 10.7
GraphSAGE
89.2 = 0.3
91.3 = 0.2
93.5 + 0.2
87.4 + 0.7
81.8 + 0.6
GAE
92.3 0.3
89.4 0.6
95.9 0.2
90.1 0.8
86.4 1.1
VGAE
92.2 0.2
91.5 1.1
94.4
90.8
+ 0.4
87.1 0.9
GPSRF
96.7 + 0.3
97.2 + 0.4
96.5
0.2
92.1
0.6
90.8 0.5
Cora
Photo
92.5
82.5
Accuracy (%)
Accuracy (%)
80.0
90.0
77.5
87.5
75.0
72.5
GPSRF with GPSRT w/or
85.0
GPSRF with
70.0
82.5
GPSRF w/o
100
600
800
1000
400
600
800
1000
M
M
Figure 3: Classification accuracies of GPSRF under different M, i.e., the number samples drawn from the spectral distribution, on Cora and Photo datasets.
treat image completion as regression task, then given some pixel intensities the goal is to predict the unseen pixel intensities. this formulation, the input features are the coordinates of each pixel and the function values are the corresponding pixel intensities. We train models on MNIST [71] dataset, where we randomly select 200 pixels an image as the training set and use the remaining for prediction. The results are presented in Figure [(b) which shows that the proposed RF kernel can better reconstruct the original images compared with bascline kernels.
8.3 Results for Answering RQ2: The Performance of GPSRF in Graph Learning Tasks
Semi-supervised Object Classification. Next, we examine the performance of GPSRF on semi- supervised object classification task. In addition to the original GPSRF setting, denoted as "GPSRF w/o r", further introduce threshold т, denoted as "GPSRF with r". for optimization from the pseudo-label perspective of the learning procedure (see Section 7 for details). In the following, GPSRF refers "GPSRF w/o 7" unless specifically stated.
The classification results are presented in Table
is shown that GPSRF can outperform all the other GP models except GGP on all the datasets. Compared with GGP, GPSRF performs better on three out of five datasets (Citeseer, Pubmed and Computers) and achieves quite similar results on the other two datasets. These results validate the effectiveness of our SRF kernel for improving the performance of GP on graphs. Compared with parametric GNNs, GPSRF can outperform GraphS and GCN on all the datasets, and achieve comparative results with GAT and DGI. In addition, by introducing the threshold т, we further improve the performance of GPSRF and obtain the best results on all the datasets. This can be explained from the pseudo-label perspective of the learning procedure: by using the comparatively accurate predictions whose maximum predicted probability is above the threshold for optimization, GPSRF be prevented from accumulating errors, alleviating the overfitting problem in superviiee setting. We also evaluate the performance of GPSRF and baselines under different percentage of labeled data, which is presented in Appendix 1. and different edge sparsity, which is presented in Appendix E.7.
Convergence Analysis. In GPSRF, variational EM algorithm, which alternates between inference and learning procedure, is used for optimization. We next study the convergence of GPSRF. Specifi- cally, we report the training and validation loss of GPSRF under different settings Cora and Photo datasets. The results in Figure show that GPSRF can converge within a few hundred steps, which is efficient. Moreover, by introducing the threshold, the validation loss gets smaller, which empirically validates that it can help alleviating the overfitting problem in semi semi- supervised setting.
Link Prediction. We follow the experimental settings in [6 and use area under the ROC curve (AUC) and average precision (AP) as evaluation metrics. Due to the space limit, we report the AUC results in Table 2 and the AP results in Appendix E.2. We only report results of GPSRF without the threshold as we empirically found similar results when introducing the threshold. Note that the GPs not taken as
Subsequently, we examine the performance of GPSRF in link prediction task.

---

Table Classification accuracies (%) of GPs with different settings SRF kernel. (Note that "RFF + g + ko the same as our GPSRF.)
Method
Cora
Citeseer
Pubmed
Photo
Computers
RFF RFF +
71.4 1.3
53.8 0.8
71.7 0.6
89.5 + 0.4
80.4 + 0.8
82.3 1 0.5
71.9 1 0.6
78.1 0.5
91.7 1 0.3
86.0 1 0.5
RFF + g Ka 83.6 - 0.3
72.7 0.5
79.6 0.5
92.2 + 0.3
86.5 + 0.2
baselines since they are tailored for classification tasks. The results show that GPSRF can outperform all the baselines on all datasets. This is because the SRF kernel in GPSRF is structure- and can capture the local patterns of the objects, which is beneficial to the success of link prediction.
8.4 Results for Answering RQ3: The Effect of the Number of Samples
In our GPSRF, we leverage RFF method to approximate the SRF kernel, which requires to sample from the spectral distribution. To understand the effect of the sampling size M on the performance of GPSRF. we further conduct experiments on the object classification task. Specifically, we report the performance of GPSRF under different sampling sizes on Cora and Photo datasets. The experimental results in Figure 3 show that GPSRF can achieve decent results even with a low sampling rate and the performance converges when the sampling size is cross certain value. These findings show another merit of our GPSRF: it is sufficient for GPSRF to use only small number of samples for optimization to obtain satisfactory performance, which is efficient.
8.5 Results for Answering RQ4: Ablation Study
Finally, we conduct ablation study to examine the effect of each component in SRF kernel, i.e., y and kg. The experimental results on object classification are presented in Table 3 where "RFF" denotes the random Fourier feature with spectral distribution corresponding to the RBF kernel. It's shown that the performance of RFF can be greatly improved by introducing the function g, which is because the 9 can summarize the local patterns of objects and produce useful representations for them. This result indicates the necessity of considering geometric structures in the kernel when modeling graphs. Moreover, by additionally introducing the RF kernel ko, the performance can be further improved as kg is more expressive and flexible than RBF kernel, and is adaptively learned from the data. These results prove the effectiveness of employing both g and ko in the proposed SRF kernel.
9 Conclusion
In this paper, to improve GP's performance on graph-structured data, we propose novel SRF kernel. The SRF kernel is defined with a spectral distribution based the Fourier duality given by the Bochner's 's theorem. Compared with feature-based kernels, the SRF kernel enables to leverage both objects features and geometric structures. Based on the SRF kernel, propose GP model, GPSRF, for graph learning tasks. To effectively optimize GPSRF, we develop a variational EM algorithm. Empirically, we conduct experiments five real-world datasets in two graph learning settings, i.e., semi- superviee object classification and link prediction. Experimental results show that our method yields best performance compared with state-of-the-ee baselines.
This paper defines SRF kernel with hierarchy Bayesian spectral distribution and we empirically find this can achieve satisfactory results. However, the performance of many other complicated distributions, such as mixture distributions and blow- distributions [72), remains uncxplored. Moreover, our GPSRF aims to solve learning tasks in homogeneous graphs and it is unclear how it performs on heterogeneous graphs with multiple types of relations and objects. We leave these limitations to further work.
The proposed method can be applied in various graph-based applications and improve the capacity of the current graph learning algorithms. However, when applied practically, it may incur some negative societal impacts. For instance, our method requires offline training, which may results in biased predictions when employed in online scenarios, where the real-time updates are essential. Moreover, the robustness of our method could be further improved to prevent attacks from an adversary, who tries to mislead the algorithm to make false predictions.
10

---

Acknowledgments
This research was supported by the National Natural Science Foundation of China (Grant No. 61906219).
References
Carl Edward Rasmussen. Evaluation of Gaussian processes and other methods for non-linear regression. PhD thesis, University of Toronto Toronto, Canada, 1997.
[2] Andrew Wilson and Ryan Adams. Gaussian process kernels for pattern discovery and extrapolation. In International conference on machine learning, pages 1067-1075, 2013.
[3] James Hensman, Alexander G Matthews, Zoubin Ghahramani. Scalable variational gaussian process classification. Proceedings of Machine Learning Research, 38:351-360, 2015.
[4] Mark Van der Wilk, Carl Edward Rasmussen, and James Hensman. Convolutional gaussian processes. In Advances in Neural Information Processing Systems, pages 2849 2858, 2017.
[5] lan Walker and Ben Glocker. Graph convolutional gaussian processes. In Proceedings of International Conference on Machine Learning, pages 6495-650 66504, 2019.
[6] Vassilis N loannidis, Meng Ma, Athanasios N Nikolakopoulos, Georgios B Giannakis. and Daniel Romero. Kernel-based inference of functions over graphs. In Adaptive Learning Methods for Nonlinear System Modeling, pages 173-198 Elsevier, 2018
David Duvenaud, James Robert Lloyd, Roger Grosse, Joshua B Tenenbaum, and Zoubin Ghahramani. Structure discovery in nonparametric regression through compositional kernel search. arXiv preprint 1r02v:1302.49222 2013.
[8] James Robert Lloyd, David Duvenaud, Roger Grosse, Joshua Tenenbaum, and Zoubin Ghahramani. Automatic construction and natural- languagg description of nonparametric regression models. In Twenty- eighth AAAI conference artificial intelligence, 2014.
[9] Shengyang Sun, Guodong Zhang, Chaoqi Wang. Wenyuan Zeng. Jiaman Li, and Roger Grosse. Differen- tiable compositional kernel learning for gaussian processes. arXiv preprint arXiv:1806. 04326, 2018.
[10] Christopher KI Williams and Carl Edward Rasmussen. Gaussian processes for mackine learning, volume 2.
MIT press Cambridge. MA. 2006.
[11] Roberto Calandra, Jan Peters, Carl Edward Rasmussen, and Mare Peter Deisenroth. Manifold gaussian processes for regression. In 2016 International Joint Conference on Neural Networks (IJCNN, pages 3338-3345. IEEE, 2016.
[12] Andrew G Wilson, Zhiting Hu, Russ R Salakhutdinov, and Eric P Xing. Stochastic variational deep kemel learning. In Advances in Neural Information Processing Systems, pages 2586-2594, 2016.
[13] Laurent Kom Samo and Stephen Roberts. M8Kiv:500.002240 2015.
Generalized spectral kernlss.
arXiv preprint
[14] Sami Remes, Markus Heinonen, and Samuel Kaski. Non-stationary spectral kemels. In Advances in Neural Information Processing Systems, pages 4642-4651, 2017.
[15] Hugh Salimbeni and Marc Deisenroth. Doubly stochastic variational inference for deep gaussian processes. In Advances in Neural Information Processing Systems, pages 4588-4599, 2017.
[16] Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint 1e09.v:600.00000 2016.
[17] Hamilton, Zhitao Ying, and Jure Leskovee. Inductive representation learning on large graphs. In
Advances in Neural Information Processing Systems, pages 1024-1034, 2017. 2017.
[18] Yin Cheng Ng. Nicolò Colombo, and Ricardo Silva. Bayesian semi-supervised learning with graph gaussian processes. In Advances in Neural Information Processing Systems, pages 1683-1694, 2018.
[19] Risi Imre Kondor and John Lafferty. Diffusion kernels on graphs and other discrete structures. In International conference machine learning, volume 2002, pages 315-22, 2002.

---

[20] Alexander J Smola and Risi Kondor. Kernels and regularization graphs. In Learning theory and kernel machinex, pages 144-158. Springer, 2003.
[21] Daniel Romero, Meng Ma, and Georgios B Giannakis. Kemel-basee reconstruction of graph signals. IEEE Transactions on Signal Processing, 65(3):764-778, 2016.
[22] Walter Rudin. Fourier analysis on groups, volume 121967. Wiley Online Library, 1962.
[23] Matthew J Beal. Variational algorithms for approximate Bayesian inference. PhD thesis, UCL (University College London), 2003.
[24] Wei Chu, Vikas Sindhwani. Zoubin Ghahramani, and S Sathiya Keerthi. Relational learning with gaussian processes. In Advances in Neural Information Processing Systems, pages 289- 189-296, 2007.
[25] Ricardo Silva, Wei Chu, and Zoubin Ghahramani. Hidden common cause relations in relational learning. In Advances in neural information processing systems, pages 1345-1352, 2008
[26] Kai Yu, Wei Chu, Shipeng Yu, Volker Tresp, and Zhao Xu. Stochastic relational models for discriminative link prediction. In Advances in neural information processing systems, pages 1553 1560, 2007.
[27] Felix I. Opolka and Pietro Liò. Graph convolutional gaussian processes for link prediction. arXiv preprint arXiv:2002.0433: 043337 2020.
[28] Shangsong Liang. Collaborative, dynamic and diversified user profiling. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4269-4466008 4276, 2019.
[29] Shangsong Liang, Xiangliang Zhang, Zhaochun Ren, and Evangelos Kanoulas. Dynamic embeddings for profiling in twitter. In SIGKDD, pages 17744-177..10 ACM, 2018
[30] Yupeng Luo, Shangsong Liang, and Zaiqiao Meng. Constrained co-embedding model for profiling in question answering communitics. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pages 439-448, 2019.
[31] Naiqi Li, Wenjie Li, Jifeng Sun, Yinghua Gao. Yong Jiang, and Sau-Tao Xia. Stochastic deep gaussian processes over graphs. Advances in Neural Information Processing Systems, 33, 2020.
[32] Jinyuan Fang. Shangsong Liang, Zaiqiao Meng, and Qiang Zhang. Gaussian process with graph convolu- tional kernel for relational learning. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Dixcovery & Data Mining, pages 353-363, 2021.
[33] Michalis Titsias. Variational learning of inducing variables in sparse gaussian processes. In Artificial Intelligence and Statistics, pages 567-574, 2009.
[34] Hui Xue, Zheng-Fan Wu, and Wei-Xiang Sun. Deep spectral kernel learning. In Sarit Kraus, editor, International Joint Conference on Artificial Intelligence, IJCAI, pages 2019-4025,20 2019.
[35] Giannis Nikolentzos, Polykarpos Meladianos, Antoine Jean-Pierre Tixier, Konstantinos Skianis, and Michalis Vazirgiannis. Kernel graph convolutional neural networks. In International conference on artificial neural networks, pages 22-32. Springer, 2018
[36] Nils M. Kriege. Fredrik D. Johansson, and Christopher Morris. survey on graph kemels.. Appl. Netw. Sci., 5(1) 2020.
[37] Shohei Hido and Hisashi Kashima. A linear-time graph kernel. 2009 Ninth IEEE International Conference on Data Mining, pages 179-188. IEEE, 2009.
[38] Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lehman graph kemnels. Journal of Machine Learning Research, 12(9), 2011. 2011.
[39] Till Hendrik Schulz, Tamás Horváth, Pascal Welke, and Stefan Wrobel. A generalized weisfeiler-lehman graph kernel. arXiv preprint (xXi::2101.0804 2021.
[40] Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Efficient graphlet kernels for large graph comparison. In Artificial intelligence and statistics, pages 488-495. PMLR, 2009.
[41] Fabrizio Costa and Kurt De Grave. Fast neighborhood subgraph pairwise distance kernel. In ICML, 2010.
12

---

[42] Daniele Zambon, Cesare Alippi, and Lorenzo Livi. Graph random neural features for distance-preserviie preserving graph representations. In International Conference on Machine Learning, pages 10968-10977. PMLR, 2020.
[43] Ali Rahimi and Benjamin Recht. Random features for large-scale kemel machines. In Advances in neural information processing systems, pages 1177-1188 2008
[44] Aman Sinha and John C Duchi. Learning kernels with random features. In Advances in Neural Information Processing Systems, pages 1298-1306, 2016.
[45] Kurt Cutajar, Edwin V Bonilla, Pietro Michiardi. and Maurizio Filippone. Random feature expansions for deep gaussian processes. In International Conference on Muchine Learning, pages 884-893. PMLR. 2017.
[46] Xiantong Zhen, Haoliang Sun, Yingjun Du, Jun Xu, Yilong Yin, Ling Shao, and Cees Snoek. Learning learn kernels with variational random features. In International Conference on Machine Learning, pages 11409-11411 1141,, 2020.
[47] Miguel Lázaro-Gredilla, Joaquin Muinonero-Candele Carl Edward Rasmussen, and Aníbal Figueiras- Vidal. Sparse spectrum gaussian process regression. The Journal of Machine Learning Research, 11:1865- 1881, 2010.
[48] Yarin Gal and Richard Turner. Improving the gaussian process sparse spectrum approximation by repre- senting uncertainty in frequency inputs. In International Conference on Machine Learning, pages 2015.
[49] Vitor RM Elias, Vinay C Gogineni, Wallace A Martins, and Stefan Werner. Kernel regression graphs in random fourier features space. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). pages 5235-5239. IEEE, 2021.
[50] Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Inductive representation learning on temporal graphs. arXiv preprint 0709:2200..07962, 2020.
[51] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Reprexentations 2018.
[52] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: 1810.0082,, 2018
[53] Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. arXiv preprint arXiv: 100X:::9022.7153.3 2019.
[54] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolu- tional networks. In International Conference on Machine Learning, pages 1725-1735. PMIR, 2020.
[55] Zaiqiao Meng, Shangsong Liang. Jinyuan Fang, and Teng Xiao. superviserii co-embedding attributed networks. Advances in Neural Information Processing Systems, pages 6504-6513, 2019.
[56] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances Neural Information Processing Systems, pages 5165-5175, 2018.
[57] Meng Qu, Yoshua Bengio, and Jian Tang. Gmnn: Graph markov neural networks. In International conference on machine learning, pages 5241-5250, 2019.
[58] Diederik Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint 1r1iv:1312.6114, 2013.
[59] Hierarchical graph representation learning with differentiable pooling. Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò -isachianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems, pages 4805-4815, 2018.
[60] Mattco Togninalli, M. Elisabetta Ghisu, Felipe Llinarcs-Lópcz Bastian Rieck, and Karsten M. Borgwardt. Wasserstein weisfeiler-lehman graph kernels. In Advances in Neural Information Processing Systems, pages 6436-6446, 2019.
[61] Thomas N Kipf and Max Welling, Variational graph auto-cncoders. In NIPS Workshop on Bayesian Deep Learning, 2016.
[62] Zaiqiao Meng. Shangsong Liang, Hongyan Bao, and Xiangliang Zhang, Co-embedding attributed networks. In International Conference Web Search and Data Mining, pages 393 401. ACM, 2019.
13

---

[63] Dong-Hyun Lee. Pseudo-label: The simple and efficient seni-superrised learning method for deep neural networks. In Workshop on challenges in representation learning, ICML, volume 2013.
[64] Jachyung Kim, Youngbum Hur, Sejun Park, Funho Yang, Sung Ju Hwang, and Jinwoo Shin. Distribution aligning refinery of pseudo-label for imbalanced semi-supervised leaminn.. Advances in Neural Information Processing Systems, 33, 2020.
[65] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification network data, magazine, 29(3):93 93, 2008.
[66] Oleksandr Shehur, Maximilian Mumme, Aleksandar Bojchevski. and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint 181
2018.
[67] Petar Velickovic, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and Devon Hjelm. Deep graph infomax. International Conference on Learning Representations, 2019.
[68] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In International Conference on Knowledge Discovery and Data Mining, SIGKDD, pages 855-864. ACM, 2016.
[69] Diederik P Kingma and Jimmy Ba. Adam: methad for stochastic optimization. In International Conference on Learning Representation, 2015.
[70] Marta Garnelo, Jonathan Schwarz, Dan Rosenbaum, Fabio Viola, Danilo Rezende, SM Eslami, and Yee Whye Teh, Neural processes. arXiv preprint arXiv:1807.01622, 2018.
[71] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied document recognition. Proceedings of the IEEE, 86(1 1):2278-2324, 1998.
[72] Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. Density estimation using real NVP. In Interna- tional Conference on Learning Representations, 2017.
14


Reviews:
[{"review_id": "jhVuGEeH5zs", "reviewer": "Reviewer_hdfy", "summary": "This paper proposed a novel SRF kernel defined with spectral distribution based on the Fourier duality given by Bochner's theorem on the vector embedding of subgraphs using GCNN.  Based on the SRF kernel, the paper  proposes a GP model, GPSRF,  for graph learning tasks. Paper developed a variational EM algorithm to solve kernel parameters. It also studies the run time complexity of the proposed method. Model has been evaluated for semi-supervised object classification and link prediction. Experimental results show that GPSRF yields best performance compared with state-of-the-art baselines.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Use of GCNN to define a graph based kernel is new to me. \nCombining subgraph embedding with Fourier kennel is interesting and might be very useful for many graph based tasks. \nAdvantage of this method is that it can capture features and graph structure in one kernel and the run time complexity is very less O(N). \nPaper is well written and has clarity and is technically sound.\nExperiment section is well planned and has been compared with many possible state of the art methods. \nPaper has also discussed the possible negative social impact.\n\nThis model is applicable when an object is in a graph. Does it also applicable for tasks when the data object is a graph like protein classification etc?\n\nFollowing related work is missing.\nNikolentzos, G., Meladianos, P., Tixier, A.J.P., Skianis, K. and Vazirgiannis, M., 2018, October. Kernel graph convolutional neural networks. In International conference on artificial neural networks (pp. 22-32). Springer, Cham.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Author has already discussed it in paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "HKP7XfqQnTD", "reviewer": "Reviewer_JdRE", "summary": "Paper presents a novel graph-structure aware kernel for graph data that leverages local sub-graph structure for node label and link prediction. It leverages spectral representation of kernels and RFFs along with ideas from graph learning to present a variational EM algorithm for graph learning. Strong empirical results show efficacy of proposed method over non-GP based GNN learning approaches.", "questions": "", "limitations": "", "rating": 9, "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": "A key contribution of the paper is the idea of using local sub-graph structure around each node in order to define a structure-ware Bayesian graph kernel. It combines several ideas of spectral kernel representation, RFFs and GP's to proposes an interesting idea that leverages local neighborhood of a node for graph learning.  \n\nPaper is well written and technically strong and addresses several aspects of proposed framework including choice of distributions, convergence, label distribution impact, sample size, effect thresholding and so on. It also provides a Bayesian and computationally efficient algorithm to estimate model parameters. \n\nAnother aspect of Graph learning that is not considered in this work is most real-world graphs (random graphs with large N) are sparse with fewer edges and how does this impact EM modeling, convergence and results. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Paper addresses some limitations of the graph learning framework in the conclusion but without any empirical results. Appendix E.1 addresses effect of label data imbalance. No direct societal impact of concern.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethics review concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "30WRgd2bkIa", "reviewer": "Reviewer_TzfG", "summary": "\nThis paper develops a structure-aware random feature kernel for Gaussian process-based learning over graphs. Experiments were carried out on real-world datasets for classification and link prediction.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The reviewer finds the novelty of the proposed framework not enough. It is a direct combination of Gaussian process +Fourier Random Feature +GNN (GP+RF+GNN). However, GP+RF has already been studied in previous work, and the incorporation of graph structure is just by input the graph with the existing GNN framework to obtain a representation.\n\nMoreover, in the experiments, it is shown that a threshold needs to be introduced for the proposed algorithm to obtain better results than GAT. However, the choice of \\tau was not discussed. Moreover, the choice of some critical parameters such as L (hops of neighbors), F (number of RFs) is not discussed for the experiments either.\n\nThe reviewer finds the organization of the paper can be improved. Some important information is missing. For example, it is claimed that the output of g() is a subgraph representation obtained using GNN in (2) and (3), but (2) (3) only provides node-level representation. It is not clear how the subgraph representation is obtained.\n\nThe writing of the paper could be improved by clearly defining operators, discussing or clarifying the procedure of parameter selection, as well as clarifying the novelty compared with existing works.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The reviewer finds this aspect inadequate, while the authors discussed the limitation: require off-line training and not robust to attacks from adversary and claim that as negative societal impact, but it seems to the reviewer believe these are just algorithmic limitation instead of societal impact. The reviewer believes societal impact could be discussed regarding the potential privacy concern, as a lot of social network datasets are used which naturally leads to privacy concerns.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "1K8mpfLqyfs", "reviewer": "Reviewer_Trb2", "summary": "The idea of this paper is to build a kernel on the features of the graph that takes into account the underlying structure of the graph. Once found, this kernel is used to define a GP on the graph. This is useful for learning tasks on graphs such as node classification/link prediction. In order to build this kernel, the authors propose to use a base translation invariant kernel that admits, by Bochner, a feature expansion, i.e. an embedding $\\phi(x,w)$ (like RFF). More precisely, they propose to learn the law on the drawing of the frequencies $w$ of these features under the constraint that the features must incorporate the structure of the graph. These features are built in two steps: 1) the law on the drawing of frequencies $w$ is defined by a \"hierarchical\" law parameterized by a neural network that can be \"arbitrarily complex\" (in the manner of a GAN generator) 2) the features take the embedding of a subgraph centered at this node as input $x$. This embedding is defined by a GNN.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- Pros:\n\t- The article is well written, quite clear.\n\t- The method proposed is interesting, and, to the best of my knowledge quite new.\n\n- Cons:\n\t- The method supposes to have already a good embedding of the graph, which is rather limiting. \n\t- Some points in the experiments are not very clear.\n\t- The advantages and limitations of the approach could be better underlined.\n\nOverall I find this article interesting, it combines many ideas and domains (kernels/GNN/GP) to define an interesting method for learning on structured data. I also find it well written, pedagogical, and I thank the authors for this effort. The proposed method seems to me quite relevant. There are however some points that are not very clear to me. Here are my detailed comments.\n\n- About the method:\n\nI find the method well detailed and clear. I think, the use of GNN embedding is the central point of the method. In this context, a point that seems unclear to me is that, as far as I understand, this embedding is not learned in conjunction with the kernel and is considered as fixed. Overall this implies to have already a good embedding of the graph, which can cause some problems in practice. Indeed, for the method to work, one needs to: 1) either have a good pre-trained GNN 2) or re-train a GNN on the data. Moreover, as shown in experiment 8.5 it seems that it is quite crucial to have a good embedding $g$. I find that this limitation is not discussed enough in the paper, especially in terms of learning complexity (section 7). It would have been good to point out that this complexity also depends on having a good GNN. On the other hand the method is flexible enough to consider more hand-crafted and unsupervised embeddings based on graph kernels for example. Did the authors test with other embeddings that are less dependent on a GNN? Moreover I think that ref [1] can be interesting in this context. The Variational EM part is quite \"classical\" for this kind of problems and seems relevant to me.\n\n- About the experiments:\n\n\t- Semi supervised classification task. I am a bit skeptical about the message brought by this experiment. I find that the conclusion that \"GPSRF > all GP models\" is a bit misleading. As much as it is clear for most of the GPs, it is a bit less clear for the GPP method [2] (ref [17] of the article) which is the most similar to the method proposed in this article. The major difference between the two methods is that the base kernel of the graph-based GP of [2] is based on the Laplacian of the graph. So it is really interesting to compare with GPP. However, the performances between the two methods are very close, because of the variance, on all datasets (except maybe Computers). Especially since the performances are only calculated on one train/validation/test split. For me it is difficult to see that the difference between the two is statistically significant. \n\t- Link prediction. The results of this experiment seem convincing and show the advantage of the method on this type of task. \n\t- Regression task. It is not really clear to me the relevance of this experiment. More precisely I don't understand the interest of an experiment that considers only the base kernel (without the graph part). Is it to illustrate that the hierarchical Bayesian approach to learn the RF law is interesting? In this case, I think it would have been interesting to discuss a little bit why this idea is new (because I think that some works approach the same idea of learning the law of frequencies according to the data [3,4,5]).\n\nOne point that I thought was worth highlighting is the fact that the method in question can take into account/model uncertainty in the prediction. I think that this property is interesting and should be emphasized, because, to the best of my knowledge, it is rarely taken into account in the context of graphs. \n\n- Minors:\n\nI think it should be mitigated that methods relying on traditional kernels and Laplacian are wether \"inefficient for them to capture the structural smoothness in graph data\" (row 31) and \"they ignore the rich features of objects and may not be capable to model complicated functions over large-scale graphs\" (row 36). It is precisely what they are attempting to do, based on the prior that \"close\" nodes (in the topology of the graph) should share similar features, and, as always, the fact that these methods sometimes struggle with the learning task depends on the dataset.\n\n\n[1] Daniele Zambon, Cesare Alippi, Lorenzo Livi. Graph Random Neural Features for Distance-Preserving Graph Representations\n\n[2] Yin Cheng Ng, Nicolo Colombo, Ricardo Silva. Bayesian Semi-supervised Learning with Graph Gaussian Processes\n\n[3] Zichao Yang, Alexander J. Smola, Le Song, Andrew Gordon Wilson. A la Carte - Learning Fast Kernels\n\n[4] Aman Sinha, John C. Duchi. Learning Kernels with Random Features\n\n[5] Junier Oliva, Avinava Dubey, Andrew G. Wilson, Barnabas Poczos, Jeff Schneider, Eric P. Xing. Bayesian Nonparametric Kernel-Learning\n\n\n---- AFTER REBUTTAL ----\n\nThe authors addressed most of my concerns (see my comment below). I am changing my score to 7.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Authors did not provide any potential negative societal impact of their work however, it is difficult for me to foresee these impacts as the work is mostly a methodological paper. There are some other limitations that I think should be more discussed. Especially concerning the fact that one needs to have a good GNN at first (see my review above).", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper received positive reviews and the rebuttal phase clarified some potential 
issues. Overall, this is a solid contribution, which should be accepted. The final submission 
should, however, incorporate suggestions made during the rebuttal phase.
Decision: Accept (Poster)