DEEP GRAPH SPECTRAL EVOLUTION NETWORKS FOR GRAPH TOPOLOGICAL TRANSFORMATION
Authors: Liang Zhao
Qingzhe Li
Negar Etemadyrad
Xiaojie Guo
Venue:  (2020)
Keywords: deep graph learning
graph transformation
brain network

Abstract: Characterizing the underlying mechanism of graph topological evolution from a source graph to a target graph has attracted fast increasing attention in the deep graph learning domain. However, there lacks expressive and efficient that can handle global and local evolution patterns between source and target graphs. On the other hand, graph topological evolution has been investigated in the graph signal processing domain historically, but it involves intensive labors to manually determine suitable prescribed spectral models and prohibitive difficulty to fit their potential combinations and compositions. To address these challenges, this paper proposes the deep Graph Spectral Evolution Network (GSEN) for modeling the graph topology evolution problem by the composition of newly-developed generalized graph kernels. GSEN can effectively fit a wide range of existing graph kernels and their combinations and compositions with the theoretical guarantee and experimental verification. GSEN has outstanding efficiency in terms of time complexity ($O(n)$) and parameter complexity ($O(1)$), where $n$ is the number of nodes of the graph. Extensive experiments on multiple synthetic and real-world datasets have demonstrated outstanding performance.

Under review as a conference paper at ICLR 2020
DEEP GRAPH SPECTRAL EVOLUTION NETWORKS FOR GRAPH TOPOLOGICAL TRANSFORMATION
A Anonymous authors
Paper under double-blind review
ABSTRACT
Characterizing the underlying mechanism of graph topological evolution from a source graph to a target graph has attracted fast increasing attention in the deep graph learning domain. However, there lacks expressive and efficient that can han- dle global and local evolution patterns between source and target graphs. On the other hand, graph topological evolution has been investigated in the graph signal processing domain historically, but it involves intensive labors manually de- termine suitable prescribed spectral models and prohibitive difficulty to fit their potential combinations and compositions. To address these challenges, this paper proposes the deep Graph Spectral Evolution Network (GSEN) for modeling the graph topology evolution problem by the composition of newly-developed gen- eralized graph kernels. GSEN can effectively fit a wide range of existing graph kernels and their combinations and compositions with the theoretical guarantee and experimental verification. GSEN has outstanding efficiency in terms of time complexity (O(r)) and parameter complexity (1),, where n is the number of nodes of the graph. Extensive experiments on multiple synthetic and real-world datasets have demonstrated outstanding performance.
INTRODUCTION
Understanding the mechanism of graph generation and evolution has significant importance in many applications, such as brain simulation, mobility network simulation, and social network modeling and intervention. Beyond the traditional methods from network science domain, graph generation and evolution have been attracting fast increase attention by deep graph generative models due to their great potential of learning the underlying known generation and evolution mechanism in an end-to-end fashion (Simonovsky & Komodakis (2018). Based on deep graph generative models, the graph generation problem is considered as decoding graph based on latent variables following some underlying distribution while graph evolution can be modeled topology given a source graph topology. Graph evolution based on deep graph learning is a very challenging problem and is still in its nascent stage because of the extremely high-dimension of the data. An ideal model should be able to capture both the local and global characteristics of source graph and be able to determine the existence or weight of potential edges for each pair of nodes. Models that both expressive and efficient are in urgent demand.
mapping to target graph
The domain which has investigated graph evolution for a long time is graph signal processing, where well-defined mathematical framework and various techniques such graph wavelets and kernels that abstract the graph process in frequency domain have been hypothesized and verified in many applications. For example, Kunegis al. have demonstrated that triangle-closing kernels fit very well to the evolution of graph spectrum during the "befriending process" " in some social networks (Leskovec et al. (2008)). Most recently, neuroscience researchers found that the functional connec- tivity shares the same graph Fourier basis with structural connectivity in several special situations.
Although graph signal processing allows powerful and concise models to characterize many graph evolution processes, they require to first determine the potentially suitable type of graph kernel and then fit the parameters of it. However, this raises up serious challenges: First, it is difficult to discover or select suitable kernel types for various applications. Graph kernels are proposed based on the analyses and abstraction of the prior knowledge on various graph phenomena. But until now, quite lot of phenomena have not yet been analyzed interpreted by human. For example, it is unclear whether and how the spectrum of resting-state functional connectivity transforms into task- specific functional connectivity in human brain Hermundstad et al. (2013). Moreover, for many

---

Under review as a conference paper at ICLR 2020
sophisticated phenomena, the graph process typically involves the combination and composition of multiple graph processes corresponding to multiple kernels. For example, the evolution of social networks might involve not only the triangle closing process (i.e., two friends of a person tend to be friends) by triangle-closing kernels, but also could include the behavior diffusion process which can be characterized by diffusion kernels. Also, the involvement of different kernel process might be simultaneous or sequential, and hence prohibitively difficult to manually determine or combinatorially optimize.
To address these challenges, this paper proposes novel end-to-end model named Deep Graph Spectral Evolution Network (GSEN) to optimally fit the graph evolution process by the composition of newly-developed generalized graph kernels. The generalized graph kernels widely cover existing graph kernels as well as their combination and composition as special cases, and hence are able to fit them with outstanding expressiveness. In addition to this high expressiveness, GSEN is also highly concise in terms of small parameter complexity and time complexity for training. Specifically, the number of parameters and memory complexity of GSEN are independent of the graph size while the time complexity for the training of GSEN is linear to the graph size. This largely outperforms the state-of tfite--f-thhearr, which typically requires )n²) time complexity and memory complexity. Extensive experiments on several synthetic datasets and multiple real-world datasets in two domains have been conducted. The results demonstrate the superior accuracy of our GSEN over existing deep generative models for graph transformation and models based on graph signal processing. The higher efficiency of GSEN compared to existing deep generative models has also been verified.
2
RELATED WORK
2.1 SPECTRAL GRAPH TRANSLATION PROBLEMS
Spectral based approaches in graph translation have been the focus in many researches over the past decades. To model how networks are translated, the spectral evolution model was introduced by Kunegis et al. (2010). The growth of large networks is analyzed by studying the changes in the spectral characteristics of the graph. These changes are explained using the eigendecomposition of the graph adjacency matrix its laplacian. The new link prediction approach shows how eigen- vectors stay constant while the eigenvalues are evolved over the transition. This model can also generalize several graph kernels which are expressed as spectral transformations. Li et al. (2011) proposes the MERW (maximum entropy random walk) approach to the link prediction problem. MERW based approaches are introduced as various algorithms that could use four separate graph kernels, in addition to a class of similarity measures, to capture the proximity between two nodes. The resulting methods perform the prediction, while maintaining the centrality of the nodes. In Symeonidis et al. (2013), the link prediction problem for protein-protein interaction networks and online social networks is considered. The Spectrall.nnt Link algorithm is proposed to compute the sim- ilarity between every two nodes, by exploiting the top few eigenvectors of the laplacian matrix, which eliminates the redundant and noisy information. The link prediction is then performed faster and more accurate. Variants of the aforementioned method are also derived for signed and directed graphs. Spectral Graph analysis has been useful in behavior related link prediction problem Spiegel al. (2011), where there's a need predict whether and how much a user is likely to rate an item. Muluple network snapshots with temporal trends are captured and tensor factorization is used to extract hidden trends within dalti-dimension array. The higher-order data is then factorized into a lower dimension, using Parafac model. The spectral evolution model is finally applied, where the spectrum of decompositions change, while the eigenvectors stay constant.
2.2
DEEP LEARNING METHODS IN GRAPH SPECTRAL DOMAIN
There is large body of research on deep graph learning, for tasks such as the embedding and clas- sification of nodes and graphs. Kipf & Welling (2016) proposed a localized graph convolutional neural networks (CNNs) based on semi-supervised learning for graph-structured data, where labels are only available for a small subset of nodes. A neural network model is designed based on layer- wise propagation rule. The model is then trained on the supervised target which includes all nodes with labels. novel spectral graph CNN approach is proposed [i et al. (2018) to graph data that varies in both size and connectivity. To capture the variation in the input graph topology. the training process includes applying a customized graph laplacian to each sample input. The laplacian then becomes trainable by parameterizing the distance metrics that measure vertex similarity. Deep con- volutional approaches have been applied to data domains with irregularities which lack fundamental statistical properties in Henaff et al. (2015), to solve for large scale classification problems. In Def-
2

---

Under review as a conference paper at ICLR 2020
Table 1: Existing kernels for graph spectral translation problem
Kernel Name
Matrix Function
Spectral Function
Laplacian Commute-lime Komel
Koom (L) =
UA -A- define A. 0 A..:
Normliized appaccin Commute-time Kerne
KCoa = 7
UA U define A O A,,;
Notmalized Adjacent Exponential Kemne
Kin((N) = =
UE
Generalized Laplacian Kernel
K(rn(L) = 1 au
U -
Generalized Normalizdd Laplacion Kernel
Koaal = = Coel1 - 2)
U on - A) A)
Heat Diffusien Kernel
Knaa(L) -al.
Ue UE-OXUT
Normalized Heat Difftssion Kerne
Kinaa =c-
UETRAUT
Normalized Adjacent Neumann Kernel
KNoo(N) = =1 aNN
U(I 9(I-aM) 9(1-aN)-lET
Nonnalized Adjacent Path Count Kernel
(P)n(N) = =b== Ox
Eeso (UDD AAD bUTy
Rogularized Laplacion Kernel Normalized Regularized Laplacian Kernel
(1) aN)
U( oA) -0T
King (21(1 aZ)
U( aA) 2UT
ferrard et al. (2016). CNNs are presented in the context of spectral graph theory, and fast localized convolutional filters are designed.
2.3 DEEP LEARNING METHODS FOR GRAPH TRANSFORMATION PROBLEMS
Graph Transformation modeling based on deep neural networks has attracted fast-increasing atten- tion recently, where existing methods are based on spatial domain by operating the explicit connec- tivity among the nodes (Guo et al. (2019), Guo et al. 2018). Do et al. 2019). The prediction in most cases is performed either the node attributes of the graph its topology while the other is fixed. Guo et al. (2019) proposes the NEC-DGT (Node-Ede Co-evolving Deep Graph Translator) framework as a novel technique to approach the simultancous prediction challenge. A portion of these research is only tailored for specific applications and domains (Do et al. (2019)). For exam- plc, Do et al. (2019) and Jin et al. (2018) proposed methods only for transferring molecule graphs. Spatio-temporal dependencies in traffic flow are modeled as a diffusion process in a directed graph through DCRNN (Diffusion Convolutional Recurrent Neural Network) model Li et al. (2017). Using bidirectional random walks and encoder-decoder architecture the spatial and temporal depen- dencies are captured respectively. However, until now there is no work in this domain that models the graph topological transformation in spectral domain.
3
GRAPH TOPOLOGY TRANSFORMATION VIA SPECTRAL EVOLUTION
This paper focuses on a problem of predicting the topology of a target graph based on that of a source graph by characterizing spectral graph evolution.
3.1
PROBLEM FORMULATION
Define source graph as undirected weighted graph G= GVVV,,, E, A) where V is the set of nodes with size of [V]. E C V x V is the set of edges, and A E R|VIXVI is the adjacent matrix that defines the weights of the edges. The adjacent matrix A can be normalized by defining the normalized adjacent matrix N = D- à AD- 1, where D E | the diagonal matrix where each diagonal element is the degree of corresponding node. Besides, the Laplacian matrix of the source graph G is defined as L D- A, and the normalized Laplacian matrix is defined as Z D LD = I-N where 7 is the identity matrix. Define graph spectrum as A E VV and graph Fourier basis as U. which are obtained from the eigendecomposition of Laplacian matrix = UAUT. A target graph is defined as G' = (V', E', A'), where the set of nodes V = V, edges E', adjacent matrix A', normalized adjacent matrix N', the Laplacian matrix L', the normalized Laplacian matrix Z', graph spectrum A' and Fourier basis U' are defined the same way as that of source graph.
Graph Transformation via Spectral Evolution:
The spectral graph translation problem states that the graph topological transformation G' + F(G) from a source graph G to target graph G' can be modeled by a change in the graph's 's spectrum, while the graph basis remains the same.
To determine the function F, various graph kernels based on the existing research on graph wavelets can be utilized, including heat kernels (HEET (L) = exp(-aL) and many others such as those listed in Table [ Several such graph kernels have been empirically demonstrated to model some specific graph process effectively. For example, Kunegis et al. has verified that path count kernels fit very well to the link prediction problem in some email networks (Kunegis et al. al.) (2100). The evolutions of social networks typically involve triangle closing process (i.e., two friends of a person tend to be friends), which has been verified to be effectively modeled by triangle-closing kernels Leskovec et al. (2008).
Existing techniques basically first determine the potentially suitable type of kernels and then fit the parameters of the kernels. However, this raises up several challenges: First, it is difficult to discover or select suitable kernel types for various applications. Graph kernels are proposed based on the
3

---

Under review as a conference paper at ICLR 2020
analyses and abstraction of the prior knowledge on various graph phenomena. But until now, quite a lot of phenomena have not yet been analyzed or interpreted by human, let alone formulated kernel functions. For example, it is unclear whether and how the spectrum of resting-state functional con- nectivity transforms into task-specific functional connectivity 2013). Moreover, for many sophisticated phenomena, the graph process typically involves addi- tive and/or sequential compositions of multiple graph processes described by multiple kernels. For example, the evolution of social network might involve not only triangle closing process (i.e., two friends of a person tend to be friends) by triangle-closing kernels, but also could include behavior diffusion process which can be characterized by diffusion kernels. Also, the involvement of differ- ent kernel process might be simultaneous or sequential, and hence prohibitively difficult manually determine or combinatorially optimize.
human brain Hermundstad et al.
3.2 GENERALIZED GRAPH KERNELS
In order to address the above mentioned challenges, we propose a new generalized graph kernel that is highly expressive to cover various graph kemnlls well as their compositions. We first formulate the learning of such expressive kernel as an optimization problem as follows.
Lemma 3.1. Without loss of generalizability, using graph Laplacian and L' to represent the graph topology of G and G', the spectral graph translation can be explicitly formulated as F(L) - L' by an analytic function F, which learned by the following equation given [F(A]]kk = fA(kk):
min ((f(AR))- L'T,L'
(1)
Proof. The training purpose of F(.) is to minimize the squared loss against the real target graph:
min [L) - 1'11 = [(T(AUT) - -''13
PTt) (7) (UAUT)* - L''11 (power expansion)
E K=O A!
II E (T)
(A)*
-IUF(A)UT L'
IIU (F L'l12
[[diag([F(A1.)).. F(Avr..)) -UL'
Hence, this problem is equivalent to the problem of min, Ex(((Ann) - U. given F(A) = [(Ax)). The proof is completed.
We propose the following new generalized graph kernel:
F(A) = Σ ac
kmm A² D= + BI
Here we introduce some important properties of the proposed generalized graph kernel.
Lemma 3.2. The generalized graph kernel in Equation has the following properties:
1. Existing graph kernels based on L.A.N, and Z such as those in Table Mare its special cases.
2. The additive combinations and compositions of the existing graph kernels are special cases of our operation.
Proof. Now we prove Property 1. Graph kernels are typically functions of four types of variables, namely Laplacian L, adjacency matrix A = D - L, normalized Laplacian Z = D-1 For those kernels based on J. and A, they can be transformed to [F(A)] = Er mai Af,,, where my, = f(k) (0) for Laplacian while R!
and normalized adjacency matrix N = D-1/2
ma,i (*) (Dr..) for adjacency matrix. Therefore, both of them can be fit by our generalized graph kernel by setting ? = 0 for all & 0, ..... For those kernels based on N and Z, they can be transformed to [F())),. Ex= m
8,6 A²,)) where m for Z while m 1 for N. Hence, both of them can be fit by setting ag == for all o....
k! (D
Here we prove Property 2. Assume there are two generalized graph kernels FA(A) and (A(A), then it is easy that both their sumation and composition still be fit by another generalized graph
4

---

Under review as a conference paper at ICLR 2020
Dh-IFHAtIv
pm
pa
U
F((A)
F((A)
F(()
U
D
U'
α TM
α
G
[F-At)
Figure 1: The architecture of Deep Graph Spectral Evolution Networks.
kernel. By leveraging Property I, the additive and composition of all the various graph kernels such as those in Table Can be fit by our generalized graph kernels.
DEEP GRAPH SPECTRAL EVOLUTION NETWORKS
In this section, a new neural network named GSEN, which is based on the proposed generalized graph kernel, proposed. To achieve this, we reduce the order of the polynomials from infinity to K that is independent of and typically far less than the graph size. Moreover, our GSEN is composed by stacking multiple such generalized graph kernel as a special type of multi-order 1-D convolution operation, as illustrated in Figure I
and described as follows.
Specifically, each layer can be expressed as follows:
(((A) H, |Σn, (ox (oxT 76 7c FF- + +
where the function H:(-) is an activation function which performs element-wise activation based on commonly used ones such as ReLU, sigmoid, linear. An equivalent scalar form of the above equation is expressed (A hu (Etn (ax + (i,,,,)) (Ar,)) B), where hy(-) is
scalar version of Hı(-).
As shown Figure [I we implement GSEN through an L-layer convolution operations from the source graph to target graph. Specifically, the input, namely Fo(A), is A that is the spectrum of the source graph. For the 1th layer, the diagonal vectors of the matri- ces L, (i)),
,... Fi (A)2 Fi-1(A)* are calculated and concatenated ange region in Figure I Similarly, the diagonal vectors of the matrices D, Fi)1 D²
shown in the
(A-1 D (A) are calculated and concatenated as shown in the yellow region in Figure Then these two regions are convoluted by the kernels (!) and 70), respectively, to ob- tain (A) after performing activation function. Such convolution operation is repeatedly performed until I--th layer, which outputs the predicted graph spectrum (A) for the target graph.
Training neural network amounts to solve the optimization problem in Equation [ which can be handled by backpropagation. Our method largely and effectively reduces the number of parameters, to K L, which is small and independent the size of the graph and hence is highly memory-efficien and scalable. In terms of the time complexity, the calculation of the powers of graph spectrum has a time complexity involves another O(K N L) so the total time complexity of the neural network is O(K N L). Also, notice the generation of the input data involves eigendeconposition consuming for large graph. To address this issue, we can leverage reduced eigendecomposition to only involve the calculation of lower-rank matrix and hence can largely speed up and scalable to large graph.
Complexity and Efficiency:
O-K-N-1 -NL) while the convolution operations
which could be time-
EXPERIMENT
In this section, the experimental settings first introduced, then the performance of the proposed method is presented through a set of comprehensive experiments. All the experiments are conducted on a 64-bit machine with 40 GB memory, 4-core Intel CPU and an Nvidia @ RTX-2080 Ti GPU. The proposed method implemented with Pytorch deep learning framework.
5.1 EXPERIMENTAL SETUP
We evaluate the effectiveness on 11 synthetic datasets, and 4 real-world datasets on brain network prediction and malware confinement in the Internet of Things (IoT) task. The datasets, evaluation methods, and comparison methods are elaborated in turn.
5.1.1 DATASETS
Synthetic Datasets: In each of the 11 synthetic datasets, we generate 1000 source-target graph pairs. Specifically, first, 1000 unweighted and undirected random graphs with 50 nodes and 200 edges are generated as the source graphs, then each edge in the source graphs is assigned with
5

---

Under review as a conference paper at ICLR 2020
random weight between 0 and 1. Finally, 1000 target graphs are generated by applying of the kernels depicted [
Real-world HCP Dataset: In these datasets, the source and the target graphs respectively reflect the structural connectivity (SC) and the functional connectivity (FC) of the same subject's brain net- work. In particular, both types of connectivity are processed from the Magnetic Resonance Imaging (MRT) data obtained from the human connectome project (HCP) Van Essen et al. (2013). By fol- lowing the preprocessing procedure in Wang et al. (2019). the SC data is constructed by applying probabilistic tracking on the diffusion MRI data using the Probtrackx tool from FMRIB Software Library Jenkinson et al. (2012) with 68 predefined regions of interests (ROIs). Then, the FC is de- fined as the Pearson's 's correlation between two ROIs' blood oxygen level-dependent time obtained from the resting-state fuunctional MRI data. Finally, all the 823 pairs of SC and FC adjacent matrices are normalized as defined in Section 3.
Real-world IoT Datasets: In these datasets, the nodes represent the Internet of Things (IoT) devices and the edges denote the communication links between two devices. Each source graph reflects the communication status of the network, and some of the nodes in the network are infected by some types of malware. To limit the devices that are infected by the malware propagating to other devices, the malware confinement conducted by cutting some of the links while maximizing the functionality of the network. The confined network is considered as the target graph that corresponds to the source graph. The loT datasets contain three datasets, namely IoT-20, loT-40, and loT-60, which include 20, 40, and 60 devices. There are 343 source-target graph pairs in each of IoT datasets.
5.1.2 COMPARISON METHODS
The comparison methods include: Graph spectral transformation kernels: We compared our GSEN method with all single kernel methods defined in Table [ on synthetic datasets. The pa- rameters a or {ax k=1 in Table is learned from the training data. Baseline method: For this method, the eigenvalue transformation function F A - A' is learned by a fully connected four- layer perceptron activated by tanh function. Each hidden layer contains 4n neurons, where is the number of nodes in the graph. Brain network prediction methods: We consider four classic brain network prediction methods that use SC to FC Galán (2008); Abddlnoou et al. (2014); Meier et al. (016); Abdelnour et al. (2018). Abbelnour et al. (2014) and Abddeloour et al. (2018) considered the graph spectral transformation kernels by assuming that SC and FC share the identical eigenvectors on their Laplacians. The remaining two methods directly consider the graph translation between SC and FC. GT-GAN: Graph Translation- Geeirraiiveeee Adversarial Networks (GT-GAN) by [uo et al. (0188) is a newly proposed ceneral-purpose graph topology translation method based on the graph generative adversarial network. C-DGT node-edge Co-evolving Deep Graph Translator (C-DGT) by Guo et al. (2019) is the state-of-the-art deep graph translation network, which considers both and edge attributes that are regularized in the spectral domain. For the datasets without node and edge attributes in our experiments, we simply assign the attributes as all-ones.
5.1.3 EVALUATION METRIC
For the effectiveness experiments, the Pearson correlation is computed between the upper triangular values of the normalized adjacent matrix of the real target graph and that of the predicted target graph. For all the comparison and our methods, 5-fold cooss-vlidationn is performed.
For the efficiency experiments, as the training time depends on the data and the max number of epochs for the maddentt-baed optimization algorithms (e.g. SGD, ADAM). We use the per-epoch training time on CPU as the evaluation metric for efficiency study.
5.2 PERFORMANCE
In this section, the performance of the proposed method, namely GSEN, as well as other methods on effectiveness and efficiency on both 1I synthetic and 4 real-world datasets are elaborated. In addition, the case studies and the sensitivity tests on the real-world datasets are also presented.
5.2.1 PERFORMANCE ON SYNTHETIC DATASETS
For synthetic datasets, compare the Pearson correlation between the target graph generated by various kernels and the graphs predicted by various methods. Table 2 summarizes the effectiveness comparison for 11 synthetic datasets. Our GSEN method achieves 0.90 Pearson correlation aver- age among all 11 synthetic datasets. In contrast, the second-best method, namely the C-DGT, only can achieve 0.61 Pearson correlation. The traditional graph spectral kernel functions can achieve

---

Under review as a conference paper at ICLR 2020
Dataset
Mathod
Koul22)
N)
K
K
KHeal!)
K
Kxt/MM
(R
K
Avg.
KoafL)
1.00 (GS)
1.00 (GSS)
0.28
-0.04
-0.15
-0.26
-0.26
0.25
0.26
-0.02
-0.23
0.16
2)
1.00
1.00 (GS)
0.28
-0.04
-0.15
-0.26
-0.26
0.23
0.26
-0.02
-0.23
0.16
0,23
0.23
1,00 (GS)
0,25
0.69
1,00
1,00
-0.88
-0.91
0.13
-0.88
0.17
-1.00
(GS)
0.83
0.06
-0,99
0,80
0.95
K
-0.02
-0.18
-0.96
-0.05
1,00 (GSS)
0.21
0,84
-0.84
-0.92
-0.02
0.98
0.00
1.00
0.25
0.69
L.0 (GS)
1.00 (GS)
0.88
.0.11
0.13
KixdZ)
0.23
0.23
1,00
0.25
0.69
1.00 (GS)
1.00 (GS)
-0.88
-0.91
0.13
-0.88
0.17
Kid/N)
0..88
0099
1.00 (GS)
0,02
00.1
KiulN)
0.01
0.29
0.95
0.03
-0.77
-0.18
-0.99
1,00
1.00 (GS)
0.01
-0.91
0.04
-0.02
-0.23
-0.99
0.36
0.96
-0.11
0.91
-0.91
-0.97
0.97 (GS)
1,00
0.09
Kazal1
-9.02
-0,23
-0.99
0.31
0.97
-0.10
0.91
-0,91
-0.97
0.65
1.00 (GS)
0,06
GT-GAN
0.12
0,18
0.26
0.00
0.93
0.48
0.25
0.53
0.69
0.18
0.53
0.38
C-DGT
-0.05
0.16
1,00
-0.02
0.8U
1,00
1.00
0.92
0.98
-0.02
0.92
0.61
Baseline
0.14
0.28
0.99
-0.05
0.27
0.07
0.17
0.76
0.99
-0.03
0.63
0.13
GSEN
0.97
0.72
0.99
0.80
1,00
0.89
0.99
1,00
1,00
0,71
0.85
0.90
Table 2: Pearson correlation between the predicted graph and empirical graph 11 synthetic datasets. Each column denotes the Pearson correlation of the synthetic dataset generated by the kernel function of the second row. Each row denotes the Pearson correlation of the prediction method of the first column. Some results are "gold standard" ones because the predictor and synthetic data generator use the same graph kernel, and hence are marked "GS" for those results. The right-most column denotes the average Pearson correlation among all 11 synthetic datasets. The highest Pearson correlation in each column/dataset is highlighted in bold font while the second second-highest Pearson correlation is marked with an underline.
near-perfect results on the synthetic datasets generated from the same kemnl,, so all the diagonal Pearson correlation coefficients from the top left corner in Table [ are close to 1. But none of these kernels perform well on all 11 synthetic datasets, which means they are not generic methods. Their average performance is thus worse than the deep learning-based methods. The deep learning- based graph translation method C-DGT performs much better than the other deep learning-based GT-GAN and fully-connected baseline methods. This because the C-DGT methods partially con- sider the spectral property as a regularization term such that it can have relatively good performance (e.g. > 0.7) on 7 out of 11 synthetic datasets, but not as good our generic spectral method. GSEN typically performs better on normalized Laplacian matrix than original Laplacian matrix L, be- cause the eigenvalues of the normalized Laplacian matrix are between 0 and 2, which can have good estimation when using Taylor expansion to estimate F(A).
5.2.2
PERFORMANCE ON REAL-WORLD DATASETS
Metric-based evaluation: Table g shows the Pearson coefficient by comparing the pre- dicted graphs with the empirical target graphs Our method achieves the highest Pearson co-
Dataset
Method
loT-20
IoT-40
IoT-60 SC-FC
Avg.
Galan2008
0.74
0.79
0.81
0.23
0.64
efficient on 3 of 4 datasets, and the high- est average Pearson correlation among the four real-world datasets. For the malware confine- ment datasets, namely the loT datasets, GSEN slightly outperforms the C-DGT method, which is the state-of-tt the-art art method on these datasets. But as will show in the next section, our method is at least 40 times faster than the C- DGT method. In addition, the C-DGT method receives the lowest Pearson correlation coeffi- cient on the brain network SC-FC translation dataset whose nodes attributes are not available.
Abdelnour2014
0.73
0.76
0.81
0.23
0.63
Meier2016
0.74
0.78
0.81
0.26
0.65
Abdelnour2018
0.73
0.76
0.81
0.23
0.63
GT-GAN
0.80
0.74
0.64
0.45
0.66
C-DGT
0.81
0.82
0.84
0.14
0.65
Baseline
0.70
0.72
0.74
0.33
0.62
GSEN
0.82
0.84
0.84
0.35
0.71
Table 3: Pearson correlation between the pre- dicted graph and empirical graph on real-world datasets
The GT-GAN method achieves the highest SC-FC dataset, but performs worse than C-DGT and GSEN on other three datasets. The GT-GAN method is also the slowest method in terms of the per epoch training time. None of the methods can achieve the Pearson correlation higher than 0.5 including the top four methods that exclusively designed for the SC-FC mapping problem in the neural science domain. This might be caused by the noise in the resting-state fMRI data. We will show some insightful reasons through multiple case studies below.
Case study on the brain network SC-FC prediction dataset:
Figure 2 plots two subject's 1) structural connectivity (i.e., the adjacent matrix of the source graph shown on the left column), 2) empirical functional connectivity (i.e.. the adjacent matrix of target graph shown on the middle column), 3) predicted func- tional connectivity (i.e., the adjacent matrix of target graph shown on the right column.

---

Under review as a conference paper at ICLR 2020
Emprical
20
40
26 Broks RDX India
Aryr RCB Lndes
Drah R00
Inslxx
Case study on Subject 121.
(b) Case study Subyect 88.
Figure 2: Case studies of the source, real, and predicted target graph topologies on SC-FC dataset.
As shown in Figure 2 the predicted FC us- ing Subject 121's SC is very close to the same subject's empirical FC. On the other hand, the predicted FC using Subject 88's SC is differ- ent from Subject 88's empirical FC, although Subject 88's SC very similar to Subject 121's SC. This is because SC reflects human brain's anatomical neural network, which has rela- tively less individual differences among human beings. Unlike SC, the FC used in this datasets reflects the Pearson correlations between two time series (i.e., Blood Oxygen Level Dependent (BOLD) signal) of different brain Regions Of Interests (ROIs), when the subject is instructed under the resting-state. In practice, it is difficult to control these subjects' brain activities, which causes the empirical FC very noisy such that may affect the performance of all prediction methods. The additional cases are provided in our supplementary matcrial due to the space limitation.
Source graph
Empirical target
Prodicted
Figure 3:
Case studies of the source, real, and pre- dicted target graph topologies on IoT dataset.
Case study on the malware confinement (IoT) dataset: Figure 3 demonstrates the cases of the source graphs, empirical target graph and the predicted target graphs by our method from all three malware confinement datasets. The leftmost source graph in each dataset denotes the original network connections. To prevent the network ceased by malware, some of the links in the network are cut while maintaining the optimal functionality of the entire network, which formulates the empirical target graph that is sparser than the source graph. The rightmost graph the target network predicted by GSEN using the source graph. When comparing the empirical target graph with the predicted target graph, it is obvious that our method can mostly predict which link should be cut to prevent malware propagation.
5.2.3 EFFICIENCY EVALUATION
To validate the efficiency as well as the scalability of the proposed method, we use three real-world IoT datasets whose number of nodes is from 20 to 60. We further enlarge the IoT-20 dataset from 200 to 1000 nodes, which generates four larger datasets, namely the IoT-200), ..., IoT-
GSEN
GT-GAN
C-DTT
Dataset
time
spoed up
time
speed up
time
speed up
TaT:20
0.0fi
31s
2.44s
x
1oT-40
0.0%
X
66s
X 733
5.86s
x 65
1000 datasets. We report the results in Table
TaT-60
0.1
108s
x
for the mean training time per epoch using CPU for 100 epochs on the aforementioned 7
IoT-200
0.21s
174s
X 829
40s
X 190
ToT-400
0.72s
692s
961
IoT-600
1.60s
161
X 1007
datasets. We compare the results with the two
1cT--00
2.89s
X
2964s
X X1026
deep learning- based graph translation methods. For our network, we set both the degree of power K and the number of layers to 5. For the other two comparison methods, the default settings are applied. As shown in Table 4 our method is on average 967 times faster than the GT- GAN method and 72 times faster than the C-DGT method. Notice that the C-DGT is unable to handle the graphs with more than 400 nodes due to the out-of-memory error. The scalability of our GSEN is remarkable, which can be trained in 4.75 seconds per epoch the graphs with 1000 nodes.
16T- 1000
4.75%
4112s
X666
Table 4: Training time per epoch. (-) indicates out-of-memory error.
6 CONCLUSIONS
This paper focuses on the problem of spectral graph topological evolution, by proposing novel deep Graph Spectral Evolution Networks (GSEN) which achieves a compelling trade-off between model expressiveness and efficiency. The proposed GSEN solves crucial drawbacks of the existing models in the graph topological evolution domain, which typically suffer from superlinear time and mem- ory complexity. Experimental results on multiple synthetic and real-world datasets demonstrated the outstanding expressiveness and efficiency accuracy in terms of the graph topology prediction accuracy and runtime, as well as qualitative analyses the predicted graph topologies.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Farras Abdelnour, Henning U Voss, and Ashish Raj. Network diffusion accurately models the rela- tionship between structural and functional brain connectivity networks. Neuroimage, 90:335-347, 2014.
Farras Abdelnour, Michael Dayan, Orrin Devinsky, Thomas Thesen, and Ashish Raj. Functional brain connectivity predictable from anatomic network's laplacian cigen-structure. Neuroimage, 172:728-739, 2018.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In Advances in neural information processing systems, pp. 3884-38422 2016.
Kien Do, Truyen Tran, and Svetha Venkatesh. Graph transformation policy network for chemi- cal reaction prediction. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 750-760. ACM, 2019.
Roberto F Galán. On how network architecture determines the dominant patterns of spontaneous neural activity. PloS one, 3(5).e2148, 2008
Xiaojie Guo, Lingfei Wu, and I Liang Zhao. Deep graph translation. CoRR, abs/1 wtss/880509990 805.09980, 2018. hbcp:/bb/180000 099800
URL
Xiaojie Guo, Liang Zhao, Cameron Nowzari, Setareh Rafatirad, Houman Homayoun, and Sai Manoj Pudukotai Dinakarrao. Deep multi-attributed graph translation with node-edge co- evolution. In he 19th International Conference on Data Mining (ICDM 2019), pp. to appear, 2019.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data. arXiv preprint arxiv:1506.0511 2015.
Ann M Hermundstad, Danielle S Bassett, Kevin S Brown, Elissa M Aminoff, David Clewett, Scott Freeman, Amy Frithsen, Arianne Johnson, Christine M Tipper, Michael B Miller, al. Structural foundations of resting-state and task-based functional connectivity the human brain. Proceed- ings of the National Academy of Sciences, 110(15):669-6617) 6174, 2013.
Mark Jenkinson, Christian F Beckmann, Timothy EJ Behrens, Mark W Woolrich, and Stephen M Smith. Fst. Neuroimage, 62(2):782-790, 2012.
Wengong Jin, Kevin Yang, Regina Barzilay, and Tommi Jaakkola. Learning multimodal graph-to- graph translation for molecular optimization. arXiv preprint arXhv:1812.010000, 2018.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. arXiv preprint arXiv: www.iII09000999 2016.
Jérôme Kunegis, Damien Fay, and Christian Bauckhage. Network growth and the spectral evolution model. In Proceedings of the 19th ACM international conference on Information and knowledge management, pp. 739-748. ACM, 2010.
Jure Leskovec, Lars Backstrom, Ravi Kumar, and Andrew Tomkins. Microscopic evolution of social networks. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 462-470. ACM, 2008.
Rong- Hua Li, Jeffrey Xu Yu, and Jianquan Liu. Link prediction: the power of maximal entropy random walk. In Proceedings of the 20th ACM international conference on Information and knowledge management, pp. 1147-1156. ACM, 2011.
Ruoyu Li. Sheng Wang, Feiyun Zhu and Junzhou Huang. Adaptive graph convolutional neural networks. In Secood AAAI Conference Artificial Intelligence, 2018.
Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Diffusson convolutional recurrent neural net- work: Data-driven traffic forecasting, arXiv preprint arXiv: 2017.

---

Under review as a conference paper at ICLR 2020
Jil Meier, Prejaas Tewarie, Arjan Hillebrand, Linda Douw, Bob W van Dijk. Steven M Stufflebeam, and Piet Van Mieghem. mapping between structural and functional brain networks. Brain connectivity, 6(4):298-311) --11 2016.
Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. International Conference on Artificial Neural Networks, pp. 412- 422. Springer, 2018.
Stephan Spiegel, Jan Clausen, Sahin Albayrak, and Jérôme Kunegis. Link prediction evolving data using tensor factorization. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 100-110. Springer, 2011.
Panagiotis Symeonidis, Nantia lakovidou, Nikolaos Mantas, and Yannis Manolopoulos, From bi- ological social networks: Link prediction based on multi-way spectral clustering. Data & Knowledge Engineering, 87:226-242 2013.
David C Van Essen, Stephen M Smith, Deanna M Barch, Timothy EJ Behrens, Essa Yacoub, Kamil Ugurbil, Wu-Minn HCP Consortium, et The wu-minn human connectome project: an overview. Neuroimage, 80:62-79, 2013.
Peng Wang, Ru Kong, Xiaolu Kong, Raphaël Liégeois, Csaba Orban, Gustavo Deco, Martijn P van den Heuvel, and BT Thomas Yeo. Inversion of a large-scale circuit model reveals a cortical hierarchy in the dynamic resting human brain. Science advances, (())eeat7785, 2019.
10

---

Under review as a conference paper at ICLR 2020
A SUPPLEMENTARY MATERIAL
This is the supplementary material for deep graph spectral evolution networks for graph topologiaal evolution. In this supplementary material we provide additional case study results on the brain network structural connectivity (SC) and functional connectivity (FC) datasets.
A.1
HYPER- PAREAEERR SENSITIVITY TEST
Number of layers:
Value of K: 3
1.0
1.0
0.8-
0.8-
Pearson Correlation
Pearson Correlation
0.6
0.6
0.4
0.4
107-60 (tanh)
kTT-0 (tann)
0.2
0.2
6T Gigmo
(tanh)
2
3
4
5
6
7
8
9
10
1
2
3
4
5
7
10
Value of
Number layers
(a) Sensitivity test to the power degree K
(b) Sensitivity test to the number of layers
Figure 4: Sensitivity analysis
We use two real-world datasets, namely the loT-60 dataset and the SC-FC dataset to test the sensi- tivity of the proposed method to its hyper-parameters. The proposed method includes three hyper- parameters: 1) the number of layers, 2) the degree of power K, and 3). the activation function. For the choice of activation function, we exclusively select the sigmoid(-) and tanh(.) function because they can easily constrain the eigenvalues to a valid range (e.g. [0,2) for the normalized Laplacian matrix). The results of the sensitivity test to the power degree K plotted in Figure 4a| which fix the number of layers to 3. Our method is quite robust for K > on both datasets using both activa- tion functions. When K 1, the Pearson correlations are dropped on the SC-FC datasets because of the inaccurate estimation number of layers are plotted in Figure 4b The propose method is also insensitive to the number of layers as long as the number of layers is greater than one. Recall when there is only one layer, our method is reduced to single graph spectral kernel that may not be able to handle sophisticated graph translation problem (e.g. the SC-FC prediction problem). Therefore, this result has validated the necessity of the "deep" proposed in this paper.
the Taylor expansion. On the other hand, the sensitivity tests for the
A.2 ADDITIONAL CASE STUDY RESULTS ON SC-FC DATASETS
The additional case study results for SC-FC datasets are shown in Figure 5 and the case study results for loT datasets shown Figure
A.3
ADDITIONAL PERFORMANCE REAL-WORLD DATASETS
Table the R2 coefficient by comparing the predicted graphs with the empirical target graphs. R2 is a metric positively related to the proportion of the variance in the dependent variable that is predictable from the independent variable(s). Thus, the higher R2 is, the better the performance will be. Similar to the results in Pearson correlation in Table our method achieves the highest R2 coefficient out of datasets, and the highest average R2 correlation among the four real-world datasets. For the malware confinement datasets, namely the loT datasets, our method outperforms the C-DGT method in two out of three datasets. Also note that method is at least 40 times faster than the C-DGT method. Our method also achieves highest R2 score on brain network dataset (i.e., the column of "SC-FC" in Table 5 In all, our method GSEN achieves the highest performance in general among all four datasets with large margin comparing to the second-best one which is the baseline method.
11

---

Under review as a conference paper at ICLR 2020
SC
Empinical FC
Predicted FC
10
10
10
20
50
50
60
60
60
20
40
60
20
40
60
20
40
60
Brain ROI index
Brain ROlindox
Brain ROlindox
(a) Case study on Subject
Empirical FC
Predicted
Nalnndee
30
40-
40
40
(b) Case study on Subject 66.
SC
Empirical FC
Predicted FC
Brain bet a:det
20
20
20
30
60
60
60
20
00
20
60
40
Brain ROI index
Brain Rolindex
Brain ROI index
(c) Case study Subject 72.
SC
Empirical FC
Predicted FC
10
10
40
50
50
50
20
20
60
40
Briin ROI Index
Brain Index
Bmhn ROI Index
(d) Case study on Subject 123.
Figure 5: Case study of brain functional connectivity predicted by method.
Dataset
Method
IoT-20
16T-40
16T-60 SC-FC
Avg.
Galan2008
0.5433
0.6044
0.6527
-5.7832
-0.9957
Abdelnour2014
-1.8336
-0.0002
-0.6364
-0.8801
-0.8376
Mcier2016
0.5386
0.5991
0.6525 +3.5465
-0,4391
Abdelnour2018
-0.0011
-0.0005
-0.0002
-0.8805
-0.2206
GT-GAN
0.6552
0.4809
0.1795 -1.0315
0.0710
C-DGT
0.6400
0.6716
0.7055 -4.1410
-0.5311
Baseline
0.405I
0.4601
0.5137
-0.7548
0.1560
GSEN
0.6275
0.7050
0.7062 -0.5847
0.3635
Table 5: R2 score between the predicted graph and empirical graph on real-world datasets
12

---

Under review as a conference paper at ICLR 2020
Source graph
Empirical target graph
Predicted target graph
(a) Case study on IoT-20 dataset.
Source graph
Empirical target graph:
Predicted target graph
(b) Case study on loT-40 dataset.
Figure Case study of malware confinement datasets with our method.
13


Reviews:
[{"review_id": "r1g_0Jxl5S", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposed a method to model the graph topological evolution from the spectral domain by developing a new generalized graph kernel. The new graph kernels cover many existing graph kernels as well as their combination and composition as special cases. The idea of spectral graph translation and its integration with deep learning is interesting, especially considering that most previous spectral graph neural networks only transform the graph signal instead of graph structures. However, I do have some concerns of papers.\n\n1.\tMy major concern is the soundness of keeping eigenvectors unchanged in the evolution. Although the authors claim that in previous studies eigenvectors are found stable in evolution, it is very counter-intuitive, and I am not sure it is the case for all types of graphs. Let us look at the proof of Lemma 3.1, obviously $L^\\prime$ does not necessarily have the same eigenvectors, and $U^TL^\\prime U$ is not a diagonal matrix, so this loss is actually very large in many cases. That is to say, the evolution model does not have enough expressive power to recover the $L^\\prime$.\n2.\tSpectral graph translation looks interesting, but the main idea comes from Kunegis et al. (2010). Despite of a new designed graph kernel and adding nonlinear activations, the contributions seem not so significant.\n3.\tIn Kunegis et al. (2010), they consider the evolution of adjacency matrix $A$, but in this paper the authors use the Laplacian matrix $L$. If there any reason to make this choice? Also, I think some of the conclusions (e.g. stable eigenvectors) in Kunegis et al. (2010) may not work since $L$ is used instesd of $A$.\n4.    The correlation metric is acceptable, but it will be much better if the authors can do more analysis. For example, why not add the link prediction task as in Kunegis et al. (2010)? BTW, is correlation analysis used before in previous graph evolution papers? (if so, please add a reference)  \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SygNO0FTtS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a spectral graph neural network based on a graph kernel to predict graph evolution. The overall idea is interesting and the biggest advantage is scalability of the framework to large graphs in terms of time and parameter complexity. \nThe major drawback of the paper is the lack of experimentation with real datasets. Based on the results from four datasets they used, the efficacy of their proposed method is unclear. The synthetic datasets are hard to admit in this case.\nNote: I could not verify the theory in detail yet. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers kept their scores after the author response period, pointing to continued concerns with methodology, needing increased exposition in parts, and not being able to verify theoretical results. As such, my recommendation is to improve the clarity around the methodological and theoretical contributions in a revision.
Decision: Reject