Dynamic Graph Representation Learning with Fourier Temporal State Embedding
Authors: Yihan He
Wei Cao
Shun Zheng
Zhifeng Gao
Jiang Bian
Venue:  (2021)
Keywords: Graph Neural Networks
Dynamic Graph
Signal Processing

Abstract: Static graph representation learning has been applied in many tasks over the years thanks to the invention of unsupervised graph embedding methods and more recently, graph neural networks (GNNs). However, in many cases, we are to handle dynamic graphs where the structures of graphs and labels of the nodes are evolving steadily with time. This has posed a great challenge to existing methods in time and memory efficiency. In this work, we present a new method named Fourier Temporal State Embedding (FTSE) to address the temporal information in dynamic graph representation learning. FTSE offered time and memory-efficient solution through applying signal processing techniques to the temporal graph signals. We paired the Fourier Transform with an efficient edge network and provided a new prototype of modeling dynamic graph evolution with high precision. FTSE can also prevent the 'history explosion' that exists in sequential models. The empirical study shows that our proposed approach achieves significantly better performance than previous approaches on public datasets across multiple tasks.

Under review as a conference paper at ICLR 2021
DYNAMIC GRAPH REPRESENTATION LEARNING WITH FOURIER TEMPORAL STATE EMBEDDING
Anonymous authors Paper under double-blind review
ABSTRACT
Static graph representation learning has been applied in many tasks over the years thanks to the invention of unsupervised graph embedding methods and more re- cently, graph neural networks (GNNs). However, in many cases, we are to handle dynamic graphs where the structures of graphs and labels of the nodes are evolving steadily with time. This has posed a great challenge existing methods in time and memory efficiency. In this work, we present a new method named Fourier Temporal State Embedding (FTSE) to address the temporal information in dy- namic graph representation learning. FTSE offered time and memory-efficien solution through applying signal processing techniques to the temporal graph sig- nals. We paired the Fourier Transform with an efficient edge network and pro- vided a new prototype of modeling dynamic graph evolution with high precision. FTSE can also prevent the 'history explosion' that exists in sequential models. The empirical study shows that our proposed approach achieves significantly bet- ter performance than previous approaches on public datasets across multiple tasks.
INTRODUCTION
Graph Representation Learning learns the graphs with low-dimensional vectors at nodes and graphs
level. (Perozzi et al. 2014 Tang et al. 2015 Wang et al., 2016 Cao al. 2013 Ou et al. 2016)
In recent years, deep neural networks (DNNs) are extended to process graphical data and have been
utilized in a plethora of real-time cases. (Estrach al.) 2014
Duvenaud et al.) [2015] Defferrard al.
2016 Li et al. 2015: Gilmer et al. 20177; Kipf& & Welling 2016 Hamilton et al. 2017 Jin et al.,
2017 Chen et al.] 2018: Veličković al. 2018 Gao & Ji. 2019). One of the most popular networks
Graph Convolution Neural Networks (GCNs) which originated from Spectral Graph Theory but developed into spatial-based varieties. GCNs are natural extensions of Convolution Neural Networks
(CNNs) which has been widely studied and used in many applications in different fields of research.
Traditional GCNs have achieved commendable performance on static graphs. However, many appli- cations involved dynamic graphs where nodes and edges evolved steadily over time. For example, a social network is updated on a day-to-day basis as people developed new friends. The dynamic graph represented users' evolving social relationships. In financial networks, transactions between nodes naturally adopt time-stamps as temporal features. Transactions of different nature may per- form differently in a financial network where our main focus is find malicious parties. Learning the evolving nature of graphs is an important task where we predict future graphical features and classify nodes based on their past behaviors.
Learning evolving graphs poses great challenges on traditional GCN as temporal features can not be easily incorporated into learning algorithms. The simple way of concatenating GCNs with RNNs is straight forward in handling dynamic graphs, but it suffered from many drawbacks. We can summarize them as three folds: Firstly, the embedding vector of each node not static and will be evolving with time. Models need to be capable of capturing the evolving nature. Secondly, the memory and computation cost for batch training is huge to keep multiple graphs from different timesteps in the memory at the same time. Finally, the large number of timesteps within a single batch brings difficulties to high precision modeling.
There is also focus using Deep Neural Networks to generate the graph embedding cently (Trivedi et al. 2018. Pareja et al.) (2000) Xu et al.) (020)) as another direction compared with traditional unsupervised dynamic graph embedding approaches (Nguyen et. 2018 Li al. 2018

---

Under review as a conference paper at ICLR 2021
Existing methods normally utilize Sequential Models Recurrett Neural Networks(RNN) to learn temporal features. However, as the graph is a non-linear data structure, sequential model-baset approaches are memory-costly to train and evaluate with the infor- mation from the whole graph as input. Meanwhile, pure GCN approaches built for static graphs are inefficient in capturing evolving features. Some approaches combining GCNs with RNNs (Trivedi) et al. 2018; Pareja et al., 2020) are costly to evaluate due to the high time complexity induced by repeated Graph Convolutions as well as high space complexity caused by large number of network parameters. Meanwhile, the RNN-based method could only see through a fixed amount of history timesteps in training, which makes the prediction imprecise.
Goyal et al., 2018 2020
We introduced Fourier temporal state embedding (FTSE) to address the above problem. Instead of using sequential models model the evolving nature of edges, we formalize the existence of edges as signal, transforming the original embedding problem into signal processing. We also designed simple and efficient Edge-Cone Coge-Coonvlltionn Network structure for FTSE and compared the complexity of it with RNN based approaches. Our main technique is Discrete-Time Fourier Transform (DTFT for short), which transforms the discrete temporal signal into its continuous frequency domain. There- fore,
embed history timesteps into fixed-length vector, enlarging the receptive field in single batch. Our empirical study shows that FTSE is an efficient method in modeling temporal graphs and a good approach model the signal with high precision.
We summarize the contribution of this work as follows:
1. We proposed Fourier Temporal State Embedding (FTSE) to learn dynamic graph repre- sentation via transforming time-series signal into the frequency domain. FTSE directly modeled the harmonic component rather than timesteps. We also designed a simple but po- tent edge convolution network to model continuous-time dynamic graphs. FTSE is also the first GCN based approach capable of modeling continuous time dynamic graphs (CTDGs).
2. We studied the drawbacks of sequential sequential-based methods in time and space complexity and justified that FTSE has much lower complexity and smaller parameter scale, making it more efficient alternative to sequential-ban based approaches. This has also been proven with experiments.
3. Extensive empirical study showed that FTSE significantly outperforms previous methods in convergence speed as well as model performance Link Prediction, Node/Edge Classi- fication, achieving more than 10% improvement on some datasets.
RELATED WORK
Many static network embedding methods are proposed to map the nodes to -ww-dimesiiona vector representations while preserving network structure as well as node information. Both supervised and unsupervised techniques have been designed. Dynamic graph embedding methods are often ex- tensions of their static counterparts. DANE (Roweis & Saul 2000 Belkin & Niyogi 2002) used matrix factorization based approach to generate static node embeddings from eigenvectors of graph Laplacian matrix. This work was extended by (Li et al. 2017) by updating eigenvectors from pre- vious ones to generate dynamic node embeddings. Random- walk based approaches (Perozzi et al.] 2014 Grover & Leskovee 2016) used normalized inner products of node embedding model the transition probabilities in random-walk. These two approaches are extended by CTDANE (Nguyen) al. 2018 which proposes walk on the temporal order.
Deep learning approaches are also popular in this area thanks to the flourishing new models. Dyn- GEM (Kamra et al.) 2017) used an autoencoding approach which minimizes the reconstruction loss as well as the distance of connected nodes in the embedding space. The point process-based ap- proach is also popular in dynamic knowledge graph modeling. KnowEvolve (Trivedi et al., 2018) and DyRep (Trivedi et al. (2018) model the occurrence of edges as point-process and model the intensity function with neural networks. DynamicTriad (Zhou et al., 2018)) focuses on the basic 'triad closure process' where a group of three vertices is developed from unconnected vertices. They proved that this process is fundamental in graph evolving thereby making their model able to predict network dynamics. HTNE (Zhou et al. 2018) used the Hawkes process with the attention mechanism to determine the influence of historical neighbors. Point process based approaches are especially good event time prediction.
2

---

Under review as a conference paper at ICLR 2021
Another set of approaches comes from the combination of Graph Neural Networks (GNNs) with Sequential Networks (e.g. RNNs). GNNs are used to digest topological information and RNNs used to handle dynamism. Graph Convolution Neural Networks (GCNs) is one of the most explored GNNs in this setting. GCRN (Seo et al. 2018) proposed two methods. The first one is doing GCN first and feed its output
LSTM capture dynamism. The second one put LSTM as an alternative for Fully Connected Layer in GCN and feed it with node features. STGCN (Yu al.) 2018) proposed ST-Conv block which was composed of ID convolution on the temporal dimension of node features followed by a Graph Convolution layer and another ID convolution. STGCN is designed for apatio-tempore traffic data, which had fixed graph structure but dynamic node embeddings. EvolveGCN (Pareja et al.) 2020) combines the two models together to form ExolveGCN-Unit. They propose two versions it. In the first one, the GCN parameters are hidden state of a recurrent architecture that takes node embeddings input. In the second one, the GCN parameters are the input of recurrent architecture.
3 PROBLEM FORMULATION
The dynamic graph has two notable varieties as has been formally defined in Kazemi & Goel, 2020). Continuous-timg time dynamic graph (CTDG) can be represented as a pair (G. ()) where ç is statie graph representing the initial state of dynamic graph at time la and (9 a set of observations where each observation is tuple of the form (even! type, event, limestep) where an event can be 1-step modification on the graph structure. (e.g. edge addition, edge deletion, node addition) At any point S to. we can obtain the snapshot G by updating G sequentially according to the observations O occured before time
The discrete time dynamic graph (DTDG) is the sequence of snapshots coming from the dynamic graph sampled at fixed space. DTDG is defined as the set G' G²,...C. "". where G' = (V*, is the snapshot time t. G is the set of nodes in G', and & is the set of edges in G
DTDG may lose information compared to their CTDG counterparts since it only includes snapshots at constant intervals. Models designed for CTDG are generally applicable to DTDG but the inverse is not necessarily true. CTDG problem can be approximated by DTDGs by aggregating G within a constant time period form the snapshot. This time period is called granularity, denoting the length of time within a single timestep. The smaller the granularity. the better the approximation to the CTDG. Existing methods predominately focus on the DTDG problem and make approximations to the respective CTDG problem. FTSE, based on Fourier Transform, is capable of modeling CTDGs which we detailed in section For a more detailed discussion on the implementation of them, please refer to appendix
B
The prediction problem could also be categorized into interpolation and extrapolation. Suppose we have information of G in time period [to. tr). In interpolation problem, we make predictions on some time such that 1. E [lo, 4T). It is also known as the completion problem as has been studied in (Li et al. 2017: Leblay & Chekol| 2018; Dasgupta al. 2018 Goel et al. 2019). In extrapolation problem, our goal is to make predictions at time such that t 2 tr. Extrapolation is more challenging problem it is trying predict the future based on the past. In this work focus on extrapolation problem.
In some cases, the observation is streamed to the model at fast rate that we cannot update the model in an on-line fashion. This is also called streaming scenario in (Kazemi & Goel 2020). This concept is similar to that of induative/transduciie learning, where the difference lied in whether or not using the training set to do inference on the testing set. Compared with the non-streaming scenario where we are able retrain the model once new data comes, this scenario poses greater challenges on the model's 's capacity to generalize.
METHOD
In this section we introduce the proposed FTSE. Existing approaches see the DTDG as graphs set with timestep and tried to sequentially learn the evolving pattern of graphs, which incurred great computation overhead. Besides, not much progress has been made in modeling CTDG as modeling a continuous function on temporal axis is not easy for neural architecture. In section 4.1 introduce
3

---

Under review as a conference paper at ICLR 2021
the definition of DIFT and DFT. In section 4.2 and section 4.3
formally define FTSE and the
memory efficient neural network EGC, later in section 4.4 we discuss the time complexity of FTSE and compared it with sequential based approaches.
4.1 PRELIMINARIES
Fourier Temporal State Embedding based on Fourier Transform on Discrete- Time Signals. We firstly review discrete-time Fourier transform (DTFT): (Oppenheim] 1999)
Definition 4.1 (Discrete-time Fourier transform) The discrete-time Fourier transform of dis-
crete set of real complex numbers Ino for all integers n, Fourier series, which produces periodic function of a frequency variable. When the frequency variable, w, has normalized units of sample, the period is 2T,, and the Fourier series is:
(2)
Σ
Ene ion
Since the result of DTFT is continuous function with periodicity, we can compute an arbitary num- ber of samples N in one cycle of the periodic function, which creates Discrete Fourier Transform (DFT). (Weinstein & Ebert 1971, Briggs Henson] 1995) Fast Fourier transform algorithm(FFT) is designed to speedily calculate DFT by factorizing the DFT matrix into product of sparse fac- tors. (Van Loan 1992; Nussbaumer 1981). >. Fast Fourier transform reduce the complexity of calcu- lating DFT from O(N to O(Nlog.V) where N is the data size.
4.2 FOURIER TEMPORAL STATE EMBEDDING
In Fourier Temporal State Embedding (FTSE) we propose formluate the existence of edges within a certain period of time (i.e. look back) as an aperiodic signal f where
f(i Pr(node i, is connected at time t)
(2)
Suppose we use information from 7 historical timesteps lo, 41...TT-11 are able to use DTFT get the frequency response /
T-1
F(i.j.)) = Σ f(i.j.t)e
n=0
which is a wi period function of w. Then we can compute N samples at interval 2g period. This creates N-length Fourier series X where
within a single
N
T-1
2nk N
X = F(i,j
Σ n=0
f(i.j.ta)e
2m
(4)
This corresponds to DFT on the original temporal sequence when we have N T. We thus embed the original temporal signal into its frequency representation length N. This transformed the original temporal relation to the amplitudes and phases of its harmonic components.
Since cannot take all history steps into one batch in training the model, the look back parameter / is delimited by the maximum history timesteps the memory can hold. Our modeled function became
(i, Pr(i.j is connected at time tx If t,), where i E -r-1)) (5)
Where f(;,;,t) fz) denotes the all structural information in previous I timesteps. However, FTSE had much larger receptive field, we can transform any number of timestamps into a /-dimensional vector by sampling values within period in the frequency domain, achieving the goal of embed- ding a high volume of data into low dimensional representation. On the other hand, we remove the inner dependency between different timesteps and transform the time series learning into frequency learning problem. This makes the use RNNs unnecessary. did an empirical study in section 5.6

---

Under review as a conference paper at ICLR 2021
Dmn
Canvelution
Timestamp
Temporal Domain Representation
Frequency Domein Representation
Concetnation
Figure
Work Flow of FTSE
4.3 NETWORK STRUCTURE
We designed time-efficient, parallelizable Edge Convolution Neural Network called EGC suitable for FTSE perform edge convolution on embedding vectors. EGC can handle edge-feature. There have been many approaches (Kim et al. 2019; Gong & Cheng 2019) trying to incorporate Edge features into GCNs. EGNNs introduced the convolution on edges and update edge features in each layer together with the node feature. Attention-based approaches incorporate edge feature in atten- tion score, which determined by the significance of correlation between nodes (Xu et al., 2020). However, in our problem setting, multiple timesteps of an evolving graph are fed into the model in one pass. This poses great challenge to the memory the model is overly complicated. Hence, we simplify the edge convolution with Vanilla GCN (Kipf & Welling, 2016) and incorporate the edge embedding naturally into the network structure. We did running- time comparison in the appendix which justified the rationale of our design.
As has been discussed in 4.2 the N-dimensional FTSE independent of each other, we perform N independent graph convolutions based on the normalized adjacency matrix Am (i.e. Ám D A D D where A is the adjacency matrix replacing its entries with corresponding edge feature entry (i.e.Ar Xijm ) and D diag(d) for d(i) the degree of node Layer-wise forward propagation can be formulated as:
H++1 = H,W,) where i 1,. 1}
In the above expression, H, is the hidden state of layer f, W, is the weight and / is the index of current layer. We concatenate the embedding of graphs different dimensions to form the final embedding. Finally, the edge embedding is calculated by concatenating the node embedding connected to
4.4 COMPLEXITY ANALYSIS
We compare the classic RNN+GCN approach with our proposed approach in time complexity. More complicated RNN structure (e.g. GRU LSTM) and GCN structure (e.g. GAT, GraphSage) has even higher time complexity in training, We assume that GCNs are calculated with dense vector multiplication. For detailed analysis, please refer to the AppendixC.1
Time Complexity In proposed method, the time complexity is O([[[TlogT (FTSE) + |0| (GCN) ) for forward propogation, assuming that we do graph convolution only once and optimization the matrix multiplication. The time complexity of RNN GCN sturcture is OTT (1912 (RNN) + [/l (GCN) )). The analysis shows that our algorithm compares favorably to RNN+GCN streture in time complexity.
Space Complexity Assuming the GCN only had a single layer. For FTSE, the parameters take up O (GCN's) + +N (MLP's)) parameters. On the other hand, sequential model based approaches

---

Under review as a conference paper at ICLR 2021
(the simplest RNN version) can take up O(10) (GCN's) + (MLP's) + +TV? (RNN's) param- eters, which has significantly more parameters than FTSE.
EXPERIMENTS
In the experiments section, we aim answer the following questions: (1) How does FTSE perform on modeling dynamic graphs compared to previous GCN+RNN based approaches? (2) What is the strength and weakness of FTSE? (3) How does each part of FTSE work? (4) How does FTSE handle the CTDG problem?
We evaluated and compared FTSE with state-of-the-arr approaches on link prediction, node clas- sification, and edge classification tasks on variety of datasets with ablation study and running time experiments. Due to space limitations, we put some figures and extensive discussions in the appendix.
5.1 TASKS
We perform link prediction, edge classification, and node classification in the experiments: Link Prediction is binary classification predicting the structure of an evolving graph at a certain time step t based on existing information from time {0, 1,.,, 1}. The classification is imbalanced with existing edges greatly outnumbered by non-exist edges, we apply 1000 times negative sampling and used weighted binary cross entropy its loss function during training. In the validation and test phase, we used the whole graph. Edge Classification the generalized link prediction task, where the edge has labels. We applied similar settings link prediction class.Node Classification is to classify future node categorization. In three tasks, we used Average Precision (AP) as well as ROC- AUC score (AUC) metrics to evaluate the final performance the model.
In streaming scenario we perform inductive learning where the training set was not used as history timesteps inference whereas transductive learning was carried out in non-streaming
5.2 DATASETS
We used public datasets from SNAP (Leskovec & Krevi 2014) and previous work for evaluation.
Autonomous System [AS for short) Autonomous System (AS) is coming from (Leskovec et al, 2005) which is communication network of routers. The edge represented the message exchange between routers and we used it to forecast the message exchange in the future. hyperlink network where the hyper-
Hyperlink
Network Reddit for short) Reddit is link is coming from post in the source community and links to another post in the target commu- nity. The hyperlink is annotated with timestep as well as sentiment, which makes it suitable for the UC classification of future edges. UC Irvine message=[]uc for short) UCI is a social network dataset creating out of students' message from the University of California, Irvine. The links within the dataset indicate the sent message between users. Stochastic Block Model (SBM for short) SBM is a random graph model for simulating graph structure and evolutions. The dataset comes from (Goyal et al. 2018). We did link prediction on this dataset. Elliptic Elliptic is a network of bitcoin transactions coming from (Weber et al. 2019). Each node the graph represents one transaction and the edges indicate payment flows. Edges are labeled with the illicit and licit category. The goal is the categorization of unlabeled transactions.
The statistics of datasets summarized in Table 2 The ratio the negative the positive. Timesteps are divided with granularity following (Pareja et al. 2020 Goyal et al. 2018).

---

Under review as a conference paper at ICLR 2021
5.3 BASELINES
We compared our proposed method with the following baselines based on deep learning approaches. GCN vanilla GCN without temporal modeling. The training loss is accumulated along timesteps. GCN+GRU/LSTM is GCN model co-trained with GRU/LSTM model. The GRU/LSTM is fed with GCN's output in each timestep. This method is similar to the one in (Goyal et al. 2020). EvolveGCN is proposed in (Pareja et al. 2020) This method is concatenating GCN with RNN to perform a new temporal graph convolution. GAT is the graph attention networks proposed by Velickovié al. 2018). We also combine it with sequential models. TGAT is proposed in (Xu et al. 2020) using the temporal kernel to define the inner product in temporal attention and perform spatial-temporal convolution similar to the structure in (Hamilton al. (017). Another comparison was between the EGNN" Kim et al. 2019) and our proposed edge convolution networks (EGC for short) at appendix D We also implemented an easy version TSE where we didn't 't apply Fourier transform and use the direct temporal signal as embedding vector. The code is posted online X All baselines are implemented in Pytorch.
5.4 EXPERIMENTAL SETTINGS
All experiments are performed on a Ubuntu 18.04 server with Nvidia Tesla V100 GPU (16GB memory) and Intel(R) Xeon(R) E5-2690 CPU. We did experiments 20 times for each model. Mean and standard deviation of AUC scores as well as mean score of AP are reported. The test result is based on the best performance epoch on validation set. Running time for every epoch as well as best valid epoch number is also reported in the appendix. The experimental settings are identical for different model except the model-specific parameters.
UCI
AS
SBM
Datasets
AUC
AP
Epochs
AUC
AP
Epochs
AUC
AP
Epochs
GCN
0.476(0.045)
61
32
0.673(0
323
96
0.715(0.007)
16587
7
GCN+GRU
0.509(0.027)
260
0.825(0.013)
935
0.718(0.004)
17061
50
GCN+LSTM
0.512(0.023)
383
0,801(0.017)
1749
10
0.714(0.003)
17954
57
GAT
0.592(0.023)
284
423
0.876(0.023)
1166
67
0.719(0.015)
15843
10
GAT+GRU
0.508(0.007)
227
14
0.658(0.030)
313.2
24
0.719(0.008)
16084
15
GAT+LSTM
0.511(0.004)
316
17
0.728(0.029)
424
18
0.718(0.009)
15845
16
EvolveGCN-O
0.580(0.019)
676
0.907(0.007)
4636
82
0.717(0.005)
16239
24
EvolyeGCN-H
0.583(0.018)
702
372
0.904(0.012)
4906
106
0.715(0.003)
16948
34
TGAT
TSE Fourier TSE
0.718(0.011)
761
108
(.989(0.002)
2983
26
0.721(0.008)
17739
13
0.714(0.018) 728
115
0.986(0.003)
3012
24
0.723(0.006)
17817
12
Table 1: The ROC-AUC score (AUC) and Average Precison(AP at scale) on non-streaming link prediction task, the mean and standard deviation of AUC score and the mean values of AP (due to space limitation) are reported according to 20 runs of each algorithm
5.5 RESULT AND DISCUSSION
Link Prediction In link prediction task, we experimented with different baselines, the results are in [ and In the three datasets we benchmarked, the experimental settings are identical for all the baselines except the GNN parts. TGAT was not able to run normally on our devices and overflows the memory because it has the "neighbor explosion" problem. EvolveGCN-O/HF's model was computed in CPU due to the memory limit of GPU while others are fully computed with GPUs. Our proposed methods TSE and FTSE achieve the best result in AUC score on all 3 datasets. In
http::://gttuu...cottttt///
httpss//atttbb.cco///ttavv//

---

Under review as a conference paper at ICLR 2021
(a)
(b)
(c)
(d)
Figure 2: (a) ROC-AUC score on Node Classification task of Elliptic dataset (b) Average Preci- sion on Node Classification task of Elliptic dataset (c) ROC-AUC score on Edge Classification task of Reddit dataset (d) Average Precision on Edge Classification task of Reddit dataset. Mean and standard deviation is reported based on 20 runs of algorithms
the average precision benchmark(AP), many previous approaches are still achieving commendable results. We also achieve moderate convergence speed compared with previous work.
Edge Classification In edge classification task, we compared FTSE with 5 baselines. The results shown in Figure 2 The GAT based varieties causing memory overflow and not included. The result shows that FTSE outperformed the state-of-the-art by 12% in the AUC score and 3% in average precision.
Node Classification In the node classification task, we compared FTSE with vanilla GCN and two EvolveGCN varieties. The result shows that we outperformed state-of-the-art in the AUC score and AP. However, the performance on the validation set is more significant. We believe it is due to the fact that the validation set is predicted in transduction setting where some of its previous timesteps have already been seen in the training set.
The result of those tasks justifies that FTSE/TSE is the new sate-of-the-art method in modeling Dynamic Graph. It is especially capable of capturing edge link evolving. The result shows that we can achieve very well performance even without Fourier Transform. our ablation study, we justify the rationale of the Fourier Transform.
5.6 ABLATION STUDY
In the ablation study, we simulate the effect of CTDG via granularizing the timesteps into smaller intervals. We detailed its reasoning in Appendix B We take on different values of look back pa- rameters and embed the temporal state into & dimensional vector with FTSE. TSE, we remove the compression process and use the last & timesteps of the original temporal signal as edge embed- ding. We compared the streaming as well as non-streaming scenarios. The result shows that with increased compression ratio (i.e. increasing the look back) the performance of FTSE compares favorably to original TSE. This justifies that FTSE could handle cases where the granularity small and performs more accurate inference with the same computation and memory budget. Extensive discussion and empirical study of FTSE vs TSE is presented the Appendix
CONCLUSION
Graph Neural Networks have already been developed into many popular branches and justified its effectiveness in modeling graphical data. However, dynamic graph modeling is still an useful but difficult task awaiting future study. The straightforward GNN RNN model bringing high computation overhead and memory cost, attention-based approach can induce high computation cost since the neighbors are spatial-temporal Instead, we explored another branch where we see the state of edges existence as a signal in the temporal domain. This facilitates the use of signal processing techniques like DTFT to provide better quality frequency-domat precision. Our approaches achieved impressive performance over dynamic graph modeling in differ- ent scenarios confirmed by empirical study. Future direction of this work included merging GCNs with Temporal Signals and extensive study the harmonic properties of graph signals.
embeddings with high
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. Advances neural information processing systems, pp. 585-595 2002.
William L Briggs and Van Emden Henson. The DFT: an owner's manual for the discrete Fourier transform. SIAM, 1995.
Shaosheng Cao, Wei Lu, and Qiongkai Xu. Grarep: Learning graph representations with global structural information. In Proceedings of the 24th ACM international on conference informa- tion and knowledge management, pp. 891-900, 2015.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 2.18.
Shib Sankar Dasgupta, Swayambhu Nath Ray, and Partha Talukdar. Hyte: Hlperplane-basee tem- porally aware knowledge graph embedding. In Proceedings of the 2018 conference on empirical methods in natural language processing, pp. 2001-2011, 2018.
Michaäl Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems, pp. 3844-3852, 2016.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in neural information processing systems, pp. 2224-2232, 2015.
Joan Bruna Estrach, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and deep locally connected networks on graphs. In 2nd International Conference on Learning Repre- sentations, ICLR 2014, 2014.
Hongyang Gao and Shuiwang Ji. Graph u-nets. In International Conference on Machine Learning, pp. 2083-2092. 2019.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. arXiv preprint 17X0v1100..0122,, 2017.
Rishab Goel, Seyed Mehran Kazemi, Marcus Brubaker, and Pascal Poupart. Diachronic embedding for temporal knowledge graph completion. arXiv preprint A90.v: 143, 2019.
Liyu Gong and Qiang Cheng. Exploiting edge features for graph neural networks. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 9211-9219, 2019.
Palash Goyal, Nitin Kamra, Xinran He, and Yan Liu. Dyngem: Deep embedding method for dy-
namic graphs arXiv preprint arXiv: 11273, 2018.
Palash Goyal, Sujit Rokka Chhetri, and Arquimedes Canedo. dyngraph2vec: Capturing network dynamics using dynamic graph representation learning. SooweddgeBaased Systems, 187:104816 2020.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855-864 2016.
Will Hamilton, Zhitao Ying. and Jure Leskovee. Inductive representation learning on large graphs. In Advances in neural information processing systems, pp. 1024-1034, 2017.
Wengong Jin, Connor Coley, Regina Barzilay, and Tommi Jaakkola. Predicting organic reaction out- comes with weisfeiler-lehman network. In Advances in Neural Information Processing Systems, pp. 2607-2616. 2017.
Nitin Kamra, Palash Goyal, Xinran He, and Yan Liu. Dyngem: deep embedding method for dynamic graphs. In IJCAI International Workshop on Representation Learning for Graphs (ReliG), 2017.

---

Under review as a conference paper at ICLR 2021
Seyed Mehran Kazemi and Rishab Goel. Representation learning for dynamic graphs: A survey. Journal of Machine Learning Research, 21(70):1-73, 2020.
Jongmin Kim, Taesup Kim, Sungwoong Kim, and Chang D Yoo. Edge-labeling graph neural net- work for few-shot learning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 11 11-20, 2019.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint 1609.02999 2016.
Julien Leblay and Melisachew Wudage Chekol. Deriving validity time in knowledge graph. In Companion Proceedings of the The Web Conference 2018, pp. 1771-1776, 2018.
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http:
lisnap.stanforee edu/ data June 2014.
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graphs over time: densification laws, shrink- ing diameters and possible explanations. In Proceedings of the eleventh ACM SIGKDD interna- tional conference Knowledge discovery in data mining, pp. 177-187, 2005.
Jundong Li, Harsh Dani, Xia Hu, Jiliang Tang, Yi Chang, and Huan Liu. Attributed network em- bedding for learning in a dynamic environment. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, pp. 387-396, 2017.
Taisong Li, Jiawei Zhang, S Yu Philip, Yan Zhang, and Yonghong Yan. Deep dynamic network embedding for link prediction. IEEE Access, 6:29219-29230, 2018
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint arXiv: 2015.
Giang Hoang Nguyen, John Boaz Lee, Ryan A Rossi, Nesreen K Ahmed, Eunyee Koh, and Sungehul Kim. Continuous-time dynamic network embeddings. In Companion Proceedings of the The Web Conference 2018, pp. 969-976, 2018.
Henri J Nussbaumer. The fast fourier transform. In Fast Fourier Transform and Convolution Algo- rithms, pp. 80-111. Springer, 1981.
Alan V Oppenheim. Discrete-time signal processing. Pearson Education India, 1999.
Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu. Asymmetric transitivity preserv- ing graph embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1105-1114 2016.
Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma. Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, Tao B Schardl, and Charles E Leiserson. Evolvegen: Evolving graph convolutional 2020.
networks for dynamic graphs. In AAAI, pp.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre-
sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710, 2014.
Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embed- ding. science, 29065500):223322336 2000.
Youngjoo Seo, Michaël Defferrard, Pierre Vandergheynst, and Xavier Bresson. Structured sequence modeling with graph convolutional recurrent networks. In International Conference on Neural Information Processing, pp. 362-373, Springer, 2018.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-seale information network embedding. In Proceedings of the 24th international conference on world wide web, pp. 1067-1077, 2015.
Rakshit Trivedi, Mehrdad Farajtabar, Prasenject Biswal, and Hongyuan Zha. Representation leamn ing dynamic graphs. arXiv preprint arXiv: 04051, 2018.
10

---

Under review as a conference paper at ICLR 2021
Charles Van Loan. Computational frameworks for fast Fourier transform. SIAM, 1992.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. In International Conference Learning Representations, 2018.
net/ forum?id= rJXMpikc2
Daixin Wang, Peng Cui, and Wenwu Zhu. Structural deep network embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp- 1225-1234, 2016.
Mark Weber, Giacomo Domeniconi, Jie Chen, Daniel Karl Weidele, Claudio Bellei, Tom Robin- son, and Charles E Leiserson. Anti-moncy laundering in bitcoin: Experimenting with graph convolutional networks for financial forensics. arXiv preprint arXiv: 02591, 2019.
S Weinstein and Paul Ebert. Data transmission by frequency-division multiplexing using the discrete fourier transform. IEEE transactions on Communication Technology, 19(5):22-633, 1971.
Da Xu, chuanwei ruan, evren korpeoglu, sushant kumar, and kannan achan. Inductive representation learning on temporal graphs. In International Conference on Learning Representations, 2020.
URL bettps:://pperevviii net http://wwww.eeeeeeoneeeeeeeee
Bing Yu, Haoteng Yin, and Zhanxing Zhu. Spatio-temporal graph convolutional networks: deep learning framework for traffic forecasting. In Proceedings of the 27th International Joint Confer- ence on Artificial Intelligence, pp. 3634-3640, 2018.
Le-kui Zhou, Yang Yang. Xiang Ren, Fei Wu, and Yueting Zhuang. Dynamic network embedding by modeling triadic closure process. In AAAI, pp. 571-578, 2018.
A DATASET STATISTICS
Datasets
Nodes
Edges
Class
Ratio
Timesteps (Train/Vall/Tes
SBM
1,000
4,870,863
2
513:
5
UCI
1,899
59,835
2
5,216:
62 /9 17
AS
6,474
13,785
2
30,390: 1
770 / 10 20
Reddit
55,863
858,490
2
1,489:
122 / 18 34
Elliptic
203,769
1,352,694
2
9,245:
/
Table 2: Dataset Statistics
B DISCUSSION ON CTDG vs DTDG
In this section, we discuss the actual implementation of the CTDG problem. Although CTDG is defined in the continuous temporal domain, it can always be approximated at any precision with DTDG since we can granularize the time period into discrete timesteps of any length. The granu- larity g depends on the number of timesteps we expected. For example, we have 1-year record of an evolving social network, we can split it into 365 days. We can aggregate all the connection information for each day and form 365 timesteps. This formulates the original CTDG into DTDG via taking snapshots over small period (i.e. day). Smaller granularity increased the prediction precision on the time axis (i.e. from the probability of having a connection in day to hour) but incurred more memory overhead when we are trying to take in the same historical period of data. Fourier TSE is better than TSE in that it transforms the original temporal signal into its frequency domain and generates fixed-length embedding vector completely made of the harmonic compo- nent the signal. We justify through ablation study that this is a rational approach to deal with low-granularity DTDG, yielding convincing performance.

---

Under review as a conference paper at ICLR 2021
C DETAILED COMPLEXITY ANALYSIS
First, we formalize the notation this section. A graph G(V, consists [0] nodes and [&] edges, the batch sizes (number of timesteps) is T and the dimension of embedded vector is N. Other parameters (i.e. hyperparameters like hidden state dimension) are treated as constant.
C.I TIME COMPLEXITY
GCN layer Vanilla GCN with dense matrix multiplication is calculated as:
H = X)
where A is the normalized adjacency matrix (i.c., A = D AD where D is the diagonal degree matrix) W is the weight and Xo the original node feature. Since the matrix multipli- cation can be calculated in (( although the upper bound can be reduced to O(N via Coppersmith- Winograd algorithm, we use dumb version of it for simplicity) Then the complex- ity of performing 1 I-layer graph convolution is O(N4) the assumption that the hidden state dimension does not have the same scale as N. Hence the complexity in Graph Convolution ((N+ in total following that it perform convolution in every timestep.
RNN The simplest structure of sequential model is Simple Recurrent Neural Network (SRN), which formulated as:
di. h4 + Un bn)
J.. W hy + by)
(There is also Elman network but they are similar in analysis.) The forward propogation has com- plexity ((1)) since 2, is the adjacency matrix Graph and has space complexity of O(1))). Therefore, the RNN has computation complexity of ((V](((T))
(T)) whole.
Thus, we conclude that the sequential-based model has forward complexity of O( Our algorithm, the other hand, is parallelisable since it has dependency between time steps. The FFT algorithm can be calculated in O([[[TlogT) presented This makes the total complexity O(1V + [8[TlogTT)
C.2 SPACE COMPLEXITY
The space complexity of neural networks is estimated from two parts: (1) model parameters (2) data volume.
1. In sequential-based models, the GCN part takes up O((Vl) parameters and RNN takes up O(Vi2T) since 2, and h2 are both O(V]2) length and there are T units. This makes the total parameter complexity amount to ((1V)2T) in total. In our proposed approach, the edge-convolution model takes up ((VINN parameters.
2. sequential-based models take up (O)V)2T) active memory to store its data while FTSE takes up (O)V|2N.
To summarize, sequential-based models had O(V(PT)) in space complexity whereas proposed approach takes up O(VV22) memory in total. In both parts, the sequential-model was out- performed by ours.
D RUNNING TIME EXPERIMENTS
We did 2 experiments about time complexity analysis.
Edge Convolution Network The first one compares EGNN(C) (Gong & Cheng 2019) with our proposed EGC network on FTSE, result shows that EGC could significantly improve the training speed of networks with the same hardware platform. The result for training is more impressive than validation and test phase, which be explained by the difference of their settings. In training phase we sampled a certain amount of non-exist" edges whereas validation and test set the whole graph is evaluated.
12

---

Under review as a conference paper at ICLR 2021
UCI Valid
AS Valid
Datasets
Train
Test
Train
Test
FTSE+EGNN
35.12(2.13)
21.31(0.42)
37.40(0.82)
102.35(12.60
356.24(8.44 345.18(8.00
691.93(16.40)
FTSE+EGC
26.68(1.43)
19.27(0.40)
33.95(0.67))
80. 80.16(6.28)
646.24(12.78)
Table 3: Training time of different GCN structures on link prediction task in seconds
Time Complexity We did an experiment justifying the time complexity of our proposed network. We used the exact same experimental setting for the two baselines and did experiment with the identical hardware platform. We test the performance on three ink-prediction datasets. Results show that our method could shorten the computation time RNN+GCN based approach by 50% on average, which corresponds to the previous complexity analysis.
68
(a)AS
(b)SBM
(c)UCI
Figure 3: Rumning Time Result on FTSE and EGCN on three different datasets, the scale is on the running time of EGCN. FTSE's time and the standard deviation adjusted correspondingly, the result is based on 20 runs of the algorithm under identical setting
E FTSE VS TSE
We did experiments comparing FTSE and TSE. The goal to learn the dynamic graph with high precision, where we need to huge amount of history timesteps (i.e. look back is very high) but could only use fixed-dimension embedding. Both FISE and TSE are using the same number of embedding dimensions for the time series and the network is EGCN. The result showed that FTSE outperforms TSE when the compression ratio is high, justifying its capability of modeling a dynamic graph with high precision. On the other hand, also found that when the compression ratio is lower, TSE performed more favorably. We believe the reasoning behind this symptom is caused by the information loss in DTFT.
STREAMING VS NON-STREAMING
We did our experiments on link prediction in streaming and non-streaming scenarios. In streaming case, we perform inductive learning where the inference is absolutely agnostic of any historical timesteps whereas in streaming case, the historical timesteps used during training. The result confirmed that the performance of non-streaming cases are generally better than the streaming cases. In both cases, our test performance outperform previous methods.
13

---

Under review as a conference paper at ICLR 2021
074
072
back
look
Compress to timesteps
Sconano FOh Strozminn
sconar 0. Stro2mingg
6m
(b) Compress to 5 timesteps
0.70
0.0
074
TSE
072
070
10
lock back
laok bazk
(c) Compress to 10 timesteps
Figure 4: ROC-AUC score on multiple compression ratios where TSE is running with uncompressed data, the result is based on 20 runs and the dataset is UCI, the granularity was also halved compared to the regular settings
14

---

Under review as a conference paper at ICLR 2021
SBM
Datasets
AUC
AP
AUC
AP
AUC
AP
GCN
0.464(0.042)
48(22)
0.664(0.030)
314(18)
(0.044))
(.999(302))
GCN+GRU
0.504(0.022)
146(13)
0.802(0.012)
783(10)
0.700(0.002)
16527(284)
GCN+LSTM
0.508(0.021)
145(13)
0.778(0.009)
1454(12)
0.697(0.002)
16549(278)
GAT
0.579(0.009)
549(32)
0.838(0.016)
679(30)
0.650(0.012)
13398(280)
GAT+GRU
0.506(0.008)
84(16)
0.586(0.013)
223(28)
0.659(0.00)
13695(204)
GAT+LSTM
0.504(0.007)
63(14)
0.625(0.014)
303(20)
0.643(0.008)
13284(226)
EvolveGCN-O
0.547(0.007)
447(8)
0.895(0.006)
4364(32)
0.697(0.005)
16211
EvolveGCN-H
0.552(0.006)
532())
0.893(0.008)
4572(28)
0.699(0.004)
16489(227)
TGAT
TSE Fourier TSE
0.706(0.008)
542(11)
0.978(0.003)
2894(49)
0.710(0.008)
16202(140)
0..04))
528(12)
0.983(0.007)
2987 (66)
0.708(0.007)
16377(167)
Table 4: The ROC-AUC score (AUC) and Average Precision AP at 1e 6 scale) on streaming link prediction task, mean and standard deviation are reported according to 20 runs of each algorithm
15


Reviews:
[{"review_id": "tmL3qrHYaB8", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a new method called Fourier temporal state embedding. The motivation for this approach is unclear and should be appropriately justified. In the abstract and introduction, the claim appears to be that previous methods are not time nor memory-efficient, and therefore FTSE is proposed. But this is obviously not true. So it is unclear what this new approach offers compared to the state-of-the-art. In Table 1, why not report performance for more standard baselines like CTDNE? The clarity and writing of this work require significant improvement. There are many incomplete and incorrect sentences throughout the paper that make it difficult if not impossible to understand. In the problem formulation, CTDG and DTDG were originally introduced in the CTDNE paper, but instead a more recent 2020 paper is referenced. Many of the ideas are never fully explained properly. The labels in nearly all the figures need to be appropriately sized, as they are impossible to read. \n\nThe motivation of this work needs to be stated clearly. The contribution and differences between existing work need to be clarified and discussed appropriately as well. In addition, some related work on temporal network representation learning is missing and should be appropriately discussed.\n\nOverall, the approach is interesting, the results seem promising, but more work is needed to better position and motivate it. Additional experiments and details would further strengthen it as well.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "_vXELcpherB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThe article presents a new approach for learning representations of dynamic graphs. The method is based on Fourier Transform of edges over time, and separate GCNs are used for each Fourier mode (N FTSE) to stain temporal embeddings. Numerical results illustrate the performance of the method on there graph tasks, namely link prediction, node and edge classifications.\n\n---------------\nStrengths:\n1. Novel method is presented based on the Fourier Transform of edges over time.\n2. Improved performance on some datasets.\n3. Complexity analysis is given. \n---------------\nWeakness:\n1. Model violates the temporal sequence.\n2. The number of parameters to be learned is large.\n3. Experiments are inadequate.\n\n---------------\nDetails:\nI have the following comments about the paper:\n\n1. Temporal sequence violation: The proposed method violates the temporal sequence of the graphs. Computing DFT and the sampling procedure ignores the temporal sequence (time linearity). Note that for the N GCN trained, the adjacency matrices are based on the FTSE which means an embedding at time t, would have information from future time instances. \nIntuitively this seems incorrect. The model does not account for the sequential correlation of the graphs over time. I recommend the authors clarify this issue.\n\n2. Number of parameters:  It appears the number of parameters in the proposed model will be significantly more than the compared methods. It appears we will have N different weight matrices to be learned for the N \"independent\" GCNs for each Fourier mode.  Note that for GCN-RNN based methods such as EvolveGCN, we only have one weight matrix corresponding to the GCN and one for the RNN that are to be learned over time. It appears the model is overparamterized and the comparisons seem unfair.\n \n3. Experiments are inadequate. It is unclear why just three datasets were used for link prediction, and one (different) dataset was used for node and edge classification, respectively. Link prediction and classification are feasible on all five datasets considered. It is unclear why datasets were picked in this manner. \nMoreover, the average precision (AP) reported seem very low (scale of 1e-2). This is contrary to the results presented in other paper, where AP are higher, see [3]. At such scale its hard to say one is better than other. For the supervised classification tasks (node and edge), results on just 1 dataset each are given. This is not adequate to make any conclusions.\n\n4. The paper is poorly written, and needs to be checked for language consistency throughout. I recommend having the paper proof-read by a native speaker. E.g., letter \n\"t\" is used for both layers and time instances.\n\nMinor Comment:\nFew recent related works are missing:\n\n[1] Sankar, Aravind, et al. \"DySAT: Deep Neural Representation Learning on Dynamic Graphs via Self-Attention Networks.\" Proceedings of the 13th International Conference on Web Search and Data Mining. 2020.\n\n[2] Franco Manessi, Alessandro Rozza, and Mario Manzo.  Dynamic graph convolutional networks. Pattern Recognition, 97, 2020.\n\n[3] Malik, Osman Asif, et al. \"Dynamic Graph Convolutional Networks Using the Tensor M-Product.\" arXiv preprint arXiv:1910.07643 (2020).", "extra_scores": {}, "extra_text": {}}, {"review_id": "XMHZSU0fP7X", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies dynamic graph embedding and proposes the method that first transforms the signal of certain edge's existence to its frequency domain by DFT and then considers it as edge features followed by the simplified vanilla GCN.  \nPros:\n  1. The idea of using DFT to capture the dynamics is simple yet powerful based on the results of experiments.\n  2. The experiments are able to show the improvements in various tasks.\nCons:\n  1. The definition of the edge existence signal f is not clear (e.g., Eq. 2). It's not defined how to compute the probability in Eq. 2, so I bet the authors directly use existence as Pr=1 and non-existence as Pr=0. But it's not clearly mentioned in Section 4.1. Similarly, how to compute the conditional probability in Eq. 5 is also not clear. \n  2. Usually in graph learning (especially GCNs), receptive field denotes the nodes that are used for aggregations. The paper claims the proposed FTSE has a larger receptive field, but didn't give the reason. \n  3. The proposed method actually remove the dependencies between two timestamps, which are usually very important information to capture the network dynamics. This is one limitation of the paper.\n  4. The notations are inconsistent. In Eq. 6, what is i? In Appendix C, the symbol N is first denoted as the embedding vector dimension, but then used as the number of nodes.\n  5. My major concern is the complexity analysis. Based on Eq. 4, the features in frequency domain are computed for every node pairs (i.e., N^2). That's why when conducting the convolutions in Eq. 6, the complexity is O(N^2), which is a bit high compared to the vanilla GCNs where the adjacency matrix is very sparse (i.e., |E| number of edges). Based on this, I think the complexity analysis in Appendix C is not fair. In the analysis, the authors directly assume dense matrix multiplication (e.g., the multiplication between A and X has O(N^3) time complexity), which is true for the proposed method. However, for the baseline which uses vanilla GCN + RNN, GCN only has O(|E|) time complexity.", "extra_scores": {}, "extra_text": {}}, {"review_id": "RzSMZn-AFrm", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a temporal embedding approach to handle the timely interactions between nodes. The paper is written clearly for most of the part, despite several typos and grammar mistakes. \n\nThe major contribution of the paper is the Fourier temporal state embedding. The authors use it as a plug-in for the standard GNN, so the novelty is limited on the GNN side. The motivations and general solutions for dynamic temporal graph embedding have been intensively mentioned in the recent literature, and the arguments and insights from this paper are relatively standard in this regard.\n\nThe highlights of this paper include:\n1. a computationally feasible embedding approach that takes account of the temporal information;\n2. a discussion on the advantage of the proposed approach in terms of the practical implementation.\n\nSince the contribution of the paper is focused on the Fourier temporal state embedding, my major concerns regarding this approach are summarized as follow.\n\n1. Unclear motivation of the Fourier temporal state embedding. The authors advertise on the advantage of converting the temporal signal to the frequency space throughout the paper, with multiple references on signal processing. However, they provide no evidence of theoretical justifications on:\n   a. what are the interpretations and properties of the proposed embedding on the frequency space;\n   b. how are they capturing the temporal signals and feeding them to the GNN;\n   c. why would the hidden representations (after local aggregation), which reflects the frequency signals according to the construction, possess valid temporal/frequency information after the GCN-type aggregation. \nIn the absence of the above discussions, even though the numerical results show some promising outcome, it remains mostly unknown why the proposed approach should be considered in the first place.\n\n2. Insufficient comparisons with the previous work of TGAT. The motivation and solution of this paper highly resemble the TGAT proposed by Xu, et al. 2020, from the idea of inventing a temporal embedding functional to converting the signals to the frequency space. Both papers leverage Fourier transformation to some extent, while TGAT has more a clear temporal-kernel interpretation and theoretical guarantee, and the temporal component, which is also reflected via the frequency domain, can be learnt in a data-adaptive fashion.  TGAT also treats the time as a continuous variable, whereas the authors do not study that part of the Fourier transformation in this paper. It seems the idea behind the Fourier temporal state embedding represents a subset of the temporal embedding in TGAT, and the authors do not make clear of the pros and cons compared with the temporal embedding in Xu, et al. 2020.\n\n3. The explanations for the working mechanism are mostly heuristic and not rigorous. The authors mention that the proposed embedding can be viewed as the signal strength under different frequencies.  In this regard, what is the geometric meaning of adding the embedding? Is it still reasonable to apply local convolution with respect to the embedding? How are the frequency components interacting with the features? The authors refer the classical approach from signal processing, but provide no rigorous analysis regarding the consequence of their practice in that regard. \n\n4. A fundamental issue of not treating time as a continuous variable. If the graph structure does not evolve (no nodes and edges are added/deleted), the prediction will be static regardless of the target time by the proposed approach, because the embeddings will not change according to how they are constructed. In many applications, the relative time span, rather than the absolute time value, is more important to reveal the temporal effect. I view this as a methodology limitation that requires improvement. \n\nBased on the above analysis, I believe the presentation and proposals in this version of the paper raise major concerns that eventually outweigh the contributions. Therefore, I vote for rejection.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes Fourier temporal state embedding, a new technique to embed dynamic graphs.  However, the paper needs to be improved in writing, computational complexity analysis, and more thorough baseline comparisons.
Decision: Reject