Title: DEEP GRAPH SPECTRAL EVOLUTION NETWORKS FOR GRAPH TOPOLOGICAL TRANSFORMATION

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.

1. 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 a graph based on latent variables following some underlying distribution while graph evolution can be modeled as a mapping to a target graph 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 are both expressive and efficient are in urgent demand.

The domain which has investigated graph evolution for a long time is graph signal processing, where well-defined mathematical framework and various techniques such as graph wavelets and kernels that abstract the graph process in frequency domain have been hypothesized and verified in many applications. For example, Kunegis et 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 connectivity 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 a lot of phenomena have not yet been analyzed or interpreted by human. For example, it is unclear whether and how the spectrum of resting-state functional connectivity transforms into taskspecific functional connectivity in human brain Hermundstad et al. (2013) . Moreover, for many 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 a 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-the-art, which typically requires O(n 2 ) 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 or its laplacian. The new link prediction approach shows how eigenvectors 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 SpectralLink algorithm is proposed to compute the similarity 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 a behavior related link prediction problem Spiegel et al. (2011) , where there's a need to predict whether and how much a user is likely to rate an item. Multiple network snapshots with temporal trends are captured and tensor factorization is used to extract hidden trends within a multi-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 a large body of research on deep graph learning, for tasks such as the embedding and classification 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 a layerwise propagation rule. The model is then trained on the supervised target which includes all nodes with labels. A novel spectral graph CNN approach is proposed in Li 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 convolutional 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- 2019)). The prediction in most cases is performed either on the node attributes of the graph or its topology while the other is fixed. Guo et al. (2019) proposes the NEC-DGT (Node-Edge Co-evolving Deep Graph Translator) framework as a novel technique to approach the simultaneous prediction challenge. A portion of these research is only tailored for specific applications and domains (Do et al. (2019) ). For example, 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 a DCRNN (Diffusion Convolutional Recurrent Neural Network) model Li et al. (2017) .

EQUATION

Using bidirectional random walks and encoder-decoder architecture the spatial and temporal dependencies 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 a source graph as an undirected weighted graph G = (V, E, A) where V is the set of nodes with size of |V |, E ⊆ V ×V is the set of edges, and A ∈ R |V |×|V | 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 -1 2 AD -1 2 , where D ∈ R |V |×|V | is 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 -1 2 LD -1 2 = I -N where I is the identity matrix. Define graph spectrum as Λ ∈ R |V |×|V | and graph Fourier basis as U , which are obtained from the eigendecomposition of Laplacian matrix L = U ΛU . 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 Λ 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 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 K HEAT (L) = exp(-αL) and many others such as those listed in Table 1 . 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. (2010) ). 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 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 connectivity transforms into task-specific functional connectivity in human brain Hermundstad et al. (2013) . Moreover, for many sophisticated phenomena, the graph process typically involves additive 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 different kernel process might be simultaneous or sequential, and hence prohibitively difficult to manually determine or combinatorially optimize.

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 kernels as 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 L 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 is learned by the following equation given

[F (Λ)] kk = f (Λ kk ): min f k (f (Λ k,k ) -U •,k L U •,k ) 2 (1)

Proof. The training purpose of F (•) is to minimize the squared loss against the real target graph:

min F F (L) -L 2 2 = F (U ΛU ) -L 2 2 = ∞ k=0 F (k) (γ) k! (U ΛU ) k -L 2 2 (power expansion) = U ∞ k=0 F (k) (γ) k! (Λ) k U -L 2 2 = U F (Λ)U -L 2 2 = U • diag([F (Λ1,1), • • • , F (Λ |V |,|V | )])U -L 2 2 = diag([F (Λ1,1), • • • , F (Λ |V |,|V | )]) -U L U 2 2

Hence, this problem is equivalent to the problem of

min f k (f (Λ k,k ) -U •,k L U •,k ) 2 given F (Λ) kk = f (Λ kk ).

The proof is completed.

We propose the following new generalized graph kernel:

EQUATION

Here we introduce some important properties of the proposed generalized graph kernel. Lemma 3.2. The generalized graph kernel in Equation 2 has the following properties:

1. Existing graph kernels based on L,A,N , and Z such as those in Table 1 are 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/2 LD -1/2 , and normalized adjacency matrix N = I -D -1/2 LD -1/2 . For those kernels based on L and A, they can be transformed to

[F (Λ)] i,i = ∞ k=0 m k,i k! Λ k i,i , where m k,i = f (k) (0) for Laplacian while m k,i = f (k) (D i,i

) for adjacency matrix. Therefore, both of them can be fit by our generalized graph kernel by setting γ k := 0 for all k = 0, 1, • • • . For those kernels based on N and Z, they can be transformed to

[F (Λ)] i,i = ∞ k=0 m k! (D -k i,i Λ i,i ) k

, where m = 0 for Z while m = 1 for N . Hence, both of them can be fit by setting α k := 0 for all k = 0, 1, • • • .

Here we prove Property 2. Assume there are two generalized graph kernels F a (Λ) and F b (Λ), then it is easy to see that both their sumation and composition can still be fit by another generalized graph

... G G' U U T Λ U' U' T Λ' U U T Λ F0(Λ) F1(Λ) FL(Λ) (1) (2) (1) (2) [F0(Λ) ]i,i k Di,i [F0(Λ) ]i,i k . k Figure 1:

The architecture of Deep Graph Spectral Evolution Networks. kernel. By leveraging Property 1, the additive and composition of all the various graph kernels such as those in Table 1 can be fit by our generalized graph kernels.

4. DEEP GRAPH SPECTRAL EVOLUTION NETWORKS:

In this section, a new neural network named GSEN, which is based on the proposed generalized graph kernel, is 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 1 and described as follows.

Specifically, each layer can be expressed as follows:

F l (Λ) = H l ∞ k=1 (α k I + γ k D -k )F l-1 (Λ) k + βI (3)

where the function H l (•) is an activation function which performs element-wise activation based on commonly used ones such as ReLU, sigmoid, or linear. An equivalent scalar form of the above equation is expressed as

f l (Λ i,i ) = h l ∞ k=1 (α k + γ k D -k i,i )f l-1 (Λ i,i ) k + β , where h l (•) is a scalar version of H l (•).

As shown in Figure 1 , we implement GSEN through an L-layer convolution operations from the source graph to target graph. Specifically, the input, namely F 0 (Λ), is Λ that is the spectrum of the source graph. For the l -1th layer, the diagonal vectors of the matrices I, F l-1 (Λ), F l-1 (Λ) 2 , • • • , F l-1 (Λ) K are calculated and concatenated as shown in the orange region in Figure 1 . Similarly, the diagonal vectors of the matrices

I, D • F l-1 (Λ), D 2 • F l-1 (Λ) 2 , • • • , D K • F l-1 (Λ) K

are calculated and concatenated as shown in the yellow region in Figure 1 . Then these two regions are convoluted by the kernels α (l) and γ (l) , respectively, to obtain F l (Λ) after performing activation function. Such convolution operation is repeatedly performed until L-th layer, which outputs the predicted graph spectrum F L (Λ) for the target graph.

Complexity and Efficiency::

Training neural network amounts to solve the optimization problem in Equation 1, which can be handled by backpropagation. Our method largely and effectively reduces the number of parameters, to 2 • K • L, which is small and independent of the size of the graph and hence is highly memory-efficient and scalable. In terms of the time complexity, the calculation of the powers of graph spectrum has a time complexity of O(K •N •L) while the convolution operations 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 eigendecomposition of L which could be timeconsuming 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.

5. EXPERIMENT:

In this section, the experimental settings are 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, a 4-core Intel R CPU and an Nvidia R RTX-2080 Ti GPU. The proposed method is 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 a random weight between 0 and 1. Finally, 1000 target graphs are generated by applying one of the kernels depicted in Table 1 .

• 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 network. In particular, both types of connectivity are processed from the Magnetic Resonance Imaging (MRI) data obtained from the human connectome project (HCP) Van Essen et al. (2013) . By following 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 defined as the Pearson's correlation between two ROIs' blood oxygen level-dependent time obtained from the resting-state functional 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 is 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 IoT datasets contain three datasets, namely 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 1 on synthetic datasets. The parameters α or {α k } K k=1 in Table 1 is learned from the training data. Baseline method: For this method, the eigenvalue transformation function F : Λ → Λ is learned by a fully connected fourlayer perceptron activated by tanh function. Each hidden layer contains 4n neurons, where n 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); Abdelnour et al. (2014) ; Meier et al. (2016) ; Abdelnour et al. (2018) . Abdelnour et al. (2014) Abdelnour 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-Generative Adversarial Networks (GT-GAN) by Guo et al. (2018) is a newly proposed general-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 cross-validation is performed.

For the efficiency experiments, as the training time depends on the data and the max number of epochs for the gradient-based 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 11 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, we compare the Pearson correlation between the target graph generated by various kernels and the graphs predicted by various methods. near-perfect results on the synthetic datasets generated from the same kernel, so all the diagonal Pearson correlation coefficients from the top left corner in Table 2 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 learningbased 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 consider 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 as our generic spectral method. GSEN typically performs better on normalized Laplacian matrix Z than original Laplacian matrix L, because the eigenvalues of the normalized Laplacian matrix are between 0 and 2, which can have a good estimation when using Taylor expansion to estimate F(Λ). • Metric-based evaluation: Table 3 shows the Pearson coefficient by comparing the predicted graphs with the empirical target graphs.

Our method achieves the highest Pearson coefficient on 3 out of 4 datasets, and the highest average Pearson correlation among the four real-world datasets. For the malware confinement datasets, namely the IoT datasets, GSEN slightly outperforms the C-DGT method, which is the state-of-the-art method on these datasets. But as we 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 coefficient on the brain network SC-FC translation dataset whose nodes attributes are not available.

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 are 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: As shown in Figure 2 , the predicted FC using 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 different from Subject 88's empirical FC, although Subject 88's SC is very similar to Subject 121's SC. This is because SC reflects human brain's anatomical neural network, which has relatively 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 material due to the space limitation.

• 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 is 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-1000 datasets. We report the results in Table 4 for the mean training time per epoch using CPU for 100 epochs on the aforementioned 7 datasets. We compare the results with the two 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 on the graphs with 1000 nodes.

6. CONCLUSIONS:

This paper focuses on the problem of spectral graph topological evolution, by proposing a 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 memory 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 on the predicted graph topologies. 

:



Figures and Tables:

), 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 PROBLEMSGraph Transformation modeling based on deep neural networks has attracted fast-increasing attention recently, where existing methods are based on spatial domain by operating the explicit connectivity among the nodes(Guo et al. (2019),Guo et al. (2018),Do et al. (

Figure2plots 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 functional connectivity (i.e., the adjacent matrix of target graph shown on the right column.

Figure 2: Case studies of the source, real, and predicted target graph topologies on SC-FC dataset.

Figure 3: Case studies of the source, real, and predicted target graph topologies on IoT dataset.

Case study on IoT-40 dataset.

Figure 6: Case study of malware confinement datasets with our method.

Existing kernels for graph spectral translation problem

Table content: <table><tr><td>Kernel Name</td><td>Matrix Function</td><td>Spectral Function</td></tr><tr><td>Laplacian Commute-time Kernel</td><td>KCom</td><td/></tr></table>

Table2summarizes the effectiveness comparison for 11 synthetic datasets. Our GSEN method achieves 0.90 Pearson correlation on average 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 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 as "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-highest Pearson correlation is marked with an underline.

Table content: <table><tr><td>Dataset</td></tr></table>

Pearson correlation between the predicted graph and empirical graph on real-world datasets

Table content: <table/>

Training time per epoch. (-) indicates out-of-memory error.

Table content: <table><tr><td/><td>GSEN</td><td/><td colspan="2">GT-GAN</td><td colspan="2">C-DGT</td></tr><tr><td>Dataset</td><td colspan="6">time speed up time speed up time speed up</td></tr><tr><td>IoT-20</td><td>0.06s</td><td>× 1</td><td>31s</td><td colspan="2">× 517 2.44s</td><td>× 41</td></tr><tr><td>IoT-40</td><td>0.09s</td><td>× 1</td><td>66s</td><td colspan="2">× 733 5.86s</td><td>× 65</td></tr><tr><td>IoT-60</td><td>0.13s</td><td colspan="2">× 1 108s</td><td colspan="2">× 831 12.10s</td><td>× 93</td></tr><tr><td colspan="2">IoT-200 0.21s</td><td colspan="2">× 1 174s</td><td>× 829</td><td>40s</td><td>× 190</td></tr><tr><td colspan="2">IoT-400 0.72s</td><td colspan="2">× 1 692s</td><td>× 961</td><td>-</td><td>-</td></tr><tr><td colspan="2">IoT-600 1.60s</td><td colspan="3">× 1 1611s ×1007</td><td>-</td><td>-</td></tr><tr><td colspan="2">IoT-800 2.89s</td><td colspan="3">× 1 2964s ×1026</td><td>-</td><td>-</td></tr><tr><td colspan="2">IoT-1000 4.75s</td><td colspan="2">× 1 4112s</td><td>×866</td><td>-</td><td>-</td></tr></table>

Peer review (iclr2020):
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. 1. My 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 does not necessarily have the same eigenvectors, and 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 . 2. Spectral 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. 3. In Kunegis et al. (2010), they consider the evolution of adjacency matrix , but in this paper the authors use the Laplacian matrix . 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 is used instesd of . 4. 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)