Spectral Invariant Learning for Dynamic Graphs under Distribution Shifts
Authors: Zeyang Zhang
Xin Wang
Ziwei Zhang
Zhou Qin
Weigao Wen
Hui Xue'
Haoyang Li
Wenwu Zhu
Venue: NeurIPS 2023 poster (2023)
Keywords: Dynamic Graph Neural Networks
Out-of-Distribution Generalization

Abstract: Dynamic graph neural networks (DyGNNs) currently struggle with handling distribution shifts that are inherent in dynamic graphs.
Existing work on DyGNNs with out-of-distribution settings only focuses on the time domain, failing to handle cases involving distribution shifts in the spectral domain. In this paper, we discover that there exist cases with distribution shifts unobservable in the time domain while observable in the spectral domain, and propose to study distribution shifts on dynamic graphs in the spectral domain for the first time.
However, this investigation poses two key challenges: i) it is non-trivial to capture different graph patterns that are driven by various frequency components entangled in the spectral domain; and ii) it remains unclear how to handle distribution shifts with the discovered spectral patterns. To address these challenges, we propose Spectral Invariant Learning for Dynamic Graphs under Distribution Shifts (SILD), which can handle distribution shifts on dynamic graphs by capturing and utilizing invariant and variant spectral patterns. Specifically, we first design a DyGNN with Fourier transform to obtain the ego-graph trajectory spectrums, allowing the mixed dynamic graph patterns to be transformed into separate frequency components. We then develop a disentangled spectrum mask to filter graph dynamics from various frequency components and discover the invariant and variant spectral patterns. Finally, we propose invariant spectral filtering, which encourages the model to rely on invariant patterns for generalization under distribution shifts. Experimental results on synthetic and real-world dynamic graph datasets demonstrate the superiority of our method for both node classification and link prediction tasks under distribution shifts.

Spectral Invariant Learning for Dynamic Graphs under Distribution Shifts
Zeyang Zhang': Xin Wang'! Ziwei Zhang', Zhou Qin', Weigao Wen". Hui Xue², Haoyang Li', Wenwu Zhu"
Department of Computer Science and Technology. BNRist, Tsinghua University, AAlibba Group 2y- 3y-zhang200mails wts.aaghulsssssnuaaa.aa. .n txin_wang, {qinzhou qinzhou, weigao wen, hui mui.xuehheallibbbaiin waw.iibbaaaii.co.... lihyl80mails, htt.:mmmalle..sinnnaaaaaa edu. en, wwzhu@teinghua.ede edu..
edu. cn,
Abstract
Dynamic graph neural networks (DyGNNs) currently struggle with handling dis- tribution shifts that are inherent in dynamic graphs. Existing work on DyGNNs with out-of-distribution settings only focuses on the time domain, failing handle cases involving distribution shifts in the spectral domain. In this paper, we discover that there exist cases with distribution shifts unobservable the time domain while observable in the spectral domain, and propose to study distribution shifts dy- namic graphs in the spectral domain for the first time. However, this investigation poses two key challenges: i) it is non-trivial to capture different graph patterns that are driven by various frequency components entangled the spectral domain; and ii) it remains unclear how to handle distribution shifts with the discovered spectral patterns. To address these challenges, we propose Spectral Invariant Learning for Dynamic Graphs under Distribution Shifts (SILD), which can handle distribution shifts on dynamic graphs by capturing and utilizing invariant and variant spectral patterns. Specifically, we first design DyGNN with Fourier transform obtain the ego-graph trajectory spectrums, allowing the mixed dynamic graph patterns to be transformed into separate frequency components. We then develop disentangled spectrum mask to filter graph dynamics from various frequency components and discover the invariant and variant spectral patterns. Finally, propose invariant spectral filtering, which encourages the model to rely on invariant patterns for generalization under distribution shifts. Experimental results synthetic and real-world dynamic graph datasets demonstrate the superiority of our method for both node classification and link prediction tasks under distribution shifts.
Introduction
Dynamic graph neural networks (DyGNNs) have achieved remarkable success in many predictive tasks over dynamic graphs 2 Existing DyGNNs exhibit limitations in handling distribution shifts,
which naturally exist in dynamic graphs due multiple uncontrollable factors 3 5 6 Existing work on out-of-distribution generalized DyGNNs focuses on handling distribution shifts in the time domain. For example, DIDA (7) utilizes dynamic graph attention to mask the graph trajectories to capture the invariant patterns on dynamic graphs, which assumes that in the time domain, the distribution shift observable and the invariant and variant patterns can be easily disentangled.
However, there exist cases that the distribution shift is unobservable in the time domain while observable in the spectral domain, as shown in Figure | The shift in frequency components can
'This work was done during the author's 's internship at Alibaba Group t Corresponding authors
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Node Class
t=2,3,6
t=2,3,6
t=1,2
t-1,2 5=5
Node of Class B
t=5
Temporal Link
t=2
t=1,3,5
t=1,3,5
Invariant Spectrum
Variant Spectrum
Temporal signals on dynamic graph
Spectrums on the same dynamic graph
An illustration example: the graph dynamics from different frequency components entangled in the temporal domain, while it is much easier to distinguish different frequency compo- nents by masking the spectrums in the spectral domain. In this case, the frequency components in the invariant spectrums determine the node labels, while the relationship between the variant spectrums and labels is not stable under distribution shifts.
Figure 1:
be clearly observed in the spectral domain, while these components indistinguishable in the time domain. Moreover, in real-world applications, the observed dynamic graphs usually consist of
multiple mixed graph structural and featural dynamics from various frequency components [8. 9 10)
To address this problem, in this paper, we study the problem of handling distribution shifts on dynamic graphs in the spectral domain for the first time, which poses the following two key challenges: i) it is non-trivial to capture different graph patterns that are driven by various frequency components entangled in the spectral domain, and ii) it remains unclear how to handle distribution shifts with the discovered spectral patterns.
To tackle these challenges, we propose Spectral Invariant Learning for Dynamic Graphs under Distribution Shifts (SII.TF). Our proposed SILD model can effectively handle distribution shifts on dynamic graphs by discovering and utilizing invariant and variant spectral patterns. Specifically, we first design a DyGNN with Fourier transform to obtain the ego-graph trajectory spectrums so that the mixed graph dynamics can be transformed into separate frequency components. Then we develop disentangled spectrum mask that leverages the amplitude and phase information of the ego-graph trajectory spectrums to obtain invariant and variant spectrum masks so that graph dynamics from various frequency components can be filtered. Finally, we propose an invariant spectral filtering that discovers the invariant and variant patterns via the disentangled spectrum masks, and minimize the variance of predictions with exposure to various variant patterns. As such, SILD is able to exploit invariant patterns to make predictions under distribution shifts. Experimental results several synthetic and real-world datasets, including both node classification and link prediction tasks, demonstrate the superior performance of SILD model compared to state-of-the-an baselines under distribution shifts. To summarize, we make the following contributions:
We propose to study distribution shifts on dynamic graphs in the spectral domain, to the best of our knowledge, for the first time.
We propose Spectral Invariant Learning for Dynamic Graphs under Distribution Shifts (SILD), which can handle distribution shifts on dynamic graphs in the spectral domain.
We employ DyGNN with Fourier transform to obtain the node spectrums, design a disentangled spectrum mask to obtain invariant and variant spectrum masks in the spectral domain, and propose the invariant spectral filtering mechanism so that SILD is able to handle distribution shifts.
We conduct extensive experiments on several synthetic and real-world datasets, including both node classification and link prediction tasks, demonstrate the superior performance of our method compared to ofte-oof-hheare baselines under distribution shifts.
The codes available Github

---

2 Problem Formulation and Notations
Dynamic Graphs A dynamic graph can be represented as 9 = (( where T represents the total number of time stamps, and each g = (V*, E²) corresponds to graph snapshot at time stamp t with the node set V and the edge set E For simplicity, we also represent a graph snapshot as -'=(X (X', A"), which includes the node feature matrix X and the adjacency matrix A'. We further denote a random variable of G' as G.. The prediction task on dynamic graphs aims to utilize past graph snapshots to make predictions, i.e., p ( where G = = G² ..... .G) denotes the graph trajectory, and the label Y' represent the node properties or the links at time + 1. For brevity, we take node-level prediction tasks as example in this paper. Following [71. the distribution of graph trajectory can be factorized into ego-graph trajectories, such that p p (::)) = II, p(y G1:)).
Distribution Shifts on Dynamic Graphs The common optimization objective for prediction tasks on dynamic graphs is to learn an optimal predictor with empirical risk minimization (ERM). i.e. )²), where So is learnable dynamic graph neural networks.
ming (y "" (y", C( Under distribution shifts, however, the optimal predictor trained with ERM and the training dis- tribution may not generalize well the test distribution, since the risk minimization objectives under two distributions are different due to Ptr Pt" G1:+) * Pte (Y", G The distribution shift on dynamic graphs complex that may originate from temporal distribution shifts [T] 12
[3] 14] as well as structural distribution shifts [[5 16 17 For example, trends or community structures can
affect interaction patterns in co-author networks [18] and recommendation networks [19], i.e., the
distribution of ego-graph trajectories may vary through time and structures.
Following out-of-distributee (OOD) generalization literature 7 15
20
21
22
we make the
following assumptions of distribution shifts on dynamic graphs:
Assumption For a given task, there exists a predictor f()). for samples (G) -y' from any distribu- tion, there exists invariant pattern (t)) and a variant pattern Pa(w)) such that the following con- ditions are satisfied: 1) the invariant patterns are sufficient to predict the labels, y = (()( + where c is a random noise, 2) the observed data is composed of invariant and variant patterns, (v) 9 (1 3) the influence of the variant patterns on labels is shielded by the invariant patterns, y P((()) (v).
In the next section, inspired by 16. we give a motivation example to provide some high-level intuition before going our formal method.
3 Motivation Example
Here we introduce toy dynamic graph example to motivate learning invariant patterns in the spectral domain. We assume that the invariant and variant patterns lie the 1-hop neighbors, i.e., each node has an invariant subgraph and a variant subgraph. For simplicity, we focus on the number of neighbors, i.e., each node v has an invariant subgraph related degree d E Tx and a variant subgraph related degree dv.2 E 1Tx1, Only the former determines the node label, i.e., ye = g' de,1. Note that invariant and variant subgraphs are not observed in the data. We further assume one-dimensional constant feature for each node, which is set as 1 without loss of generality.
For the model in the spatial- -eatial-eemporl domain, we adopt sum pooling as one-layer graph convolution, d + d We further adopt a
i.e., the message passing for each node and time h, = EveN. mask m E TTx to filter patterns in the temporal domain and make predictions by a linear classifier, i.e., D. = w T (m O hn), where w 2x denotes the learnable parameters. Then, the empirical risk in the training dataset Dr. is Rey Rer(w) Deer EneD,, (1. y2. We have the following proposition.
Proposition 1 For any mask m E RRxx1, for the optimal classifier in the training data w" arg min Rey (w). if m @ w + O, there exist OOD nodes with unbounded error, i.e., 3u S.I. lil (No- y,)² ===o xc.
The proposition I shows that classifier trained with masks and empirical risk minimization has unbounded risks in testing data under distribution shifts as the classifier uses variant patterns to make predictions. Next, we show that under mild conditions, invariant linear classifier in the spectral
3

---

domain can solve this problem. Denote + E CTXT as the Fourier bases, where Øk.t 1 Denote 2U + EuEN, as the spectral representation after a linear message-passen -aassiig...nn..... The prediction is ye = w @ 2.), where m E CTx1 is the mask to filter the spectral patterns, w E CTx1 x1 is a linear classifier, and (.) denotes Hermitian transpose. We have the following proposition.
vT s
Proposition 2 If ( O Pdw.1)
2db.2) 0, Vdu,i, du then 3m E CTXI
such that the optimal spectral classifier in the training data has bounded error, i.e, for w = arg min (w), 3e 0, Vu, lim limm [ (Ur
y.)² <.
The proposition 2 shows that the frequency bandwidths of invariant and variant patterns do not have any overlap, there exists a spectral mask such that linear classifier trained with empirical risk minimization in the spectral domain will have bounded risk in any testing data distribution. This example motivates us capture invariant and variant patterns in the spectral domain, which is not feasible in the spatial-tempone domain.
4 Method
In this section, we introduce our method named Spectral Invariant Learning for Dynamic Graphs under Distribution Shifts (SILD) to handle distribution shifts dynamic graphs, including three modules, dynamic graph neural networks with Fourier transform, disentangled spectrum mask, and invariant spectral filterin.. The framework of our method is shown in Figure 2
4.1 Dynamic Graph Neural Network with Spectral Transform
Dynamic Graph Trajectories Modeling Each node on the dynamic graph has its ego- ego-graph trajectory evolving through time that may determine the node properties or the occurrence of future links. Following [23 24 25]. we adopt a message-passing network for each graph snapshot to aggregate the neighborhood information at the current time, i.e.,
m カーサ + MSG h,,, + AGG((mLL-v Ne
(I)
where 'MSG' and 'AGG' denote message and aggregation functions, m is the message from node u to node v, h" is the node embedding for node u at time 1, (b) {u (u, v) E E") is stack
node e's neighborhood at time t. To model the high-order neighborhood information, multiple message- paasgggg--gnngggggg layers. In this way, the node embedding along time {h summarizes the evolution of node u's ss ego-graph trajectories. We denote H R Nxd as the ego-graph trajectory signals for all nodes the dynamic graph, where T denotes the total time length, N denotes the number nodes and denotes the hidden dimensionality.
Spectral Transform As some patterns on dynamic graphs unobservable in the time domain, while observable in the spectral domain, we transform the summarized ego-graph trajectory signals H into the spectral domain via Fourier transform for each node and hidden dimension, Le.,
2nkt
Z HH.
(2)
VT
where E CTX denotes the Fourier bases, K denotes the number of frequency components, and Z C X Nxd denote the node embeddings along frequency components in the spectral domain, and
Zk. ET= &k. By choosing the Fourier bases, our spectral transform has the following advantages: 1) we can use fast Fourier transform (FFT) (26) to accelerate the computation. The computation complexity of Eq. (2) can be reduced from ONNT22 to O(NdTlogT). 2) Each basis has clear semantics, e.g., Z₁ denotes the node embeddings at the k-th frequency component in the spectral domain. this way, we can observe how the nodes on the dynamic graph evolve different frequency bandwidths. 3) Fourier transform is able to capture global and periodic patterns [27 28 which are common real-world dynamic graphs, egg., the interactions on e-commerce networks may result from seasonal sales product service cycles.

---

Dynamic Graph Neural Networks with Spectral Transform
Disentangled Spectrum Mask
Invariant Spectral Filtering
Invariant
Spectrum
Inwariant Patterns
Mask
Variant
Shuffle
Spectrum
Variant
Mask
Snapshot-wise Message Passing
Masked Spectrums
Shuffled Spectrums
Amplitudes
Phases
Node Classification
Var
MAAA MONAMAY
mildd al
Class?
FFT
MAMA VAMAAAA
Prediction
Var
MAAA MARGIMA
Input Dynamic Graph
Temporal Signals
Spectrums
Spectral Invariance Loss
Figure 2: The framework our proposed method SILD. Given dynamic graph evolving through time, the dynamic graph neural networks with spectral transform first obtain the ego-graph trajectory spectrums the spectral domain. Then disentangled spectrum mask leverages phase information of the ego-graph trajectory spectrums to obtain invariant and variant spectrum masks. Last, invariant spectral filtering discovers the invariant and variant patterns via the disentangled spectrum masks, and minimizes the variance of predictions with exposure various variant patterns, to help the model exploit invariant patterns to make predictions under distribution shifts.
amplitude and
4.2 Disentangled Spectrum Mask
To capture invariant patterns in the spectral domain, we propose to explicitly learn spectrum masks to disentangle the invariant and variant patterns. The embeddings in the spectral domain contain the amplitude information as well as the phase information for each node
Imag Z
Amp(Z)= = IImag2 - Reall o(Z)) arctan Real
(3)
where Real(-) and Imag(-) denote the real and imaginary part of the complex number, i.e., Z = Real(Z) + (aaa()) jImag(Z) j denotes the imaginary unit, Amp(Z) (Z) E IR Kxxxx xd and (Z) E K x Xxd
denote the amplitude and phase information respectively. For brevity, the tensor operators in Eq. (3) are all element-wise, e.g., (Imag²(Z)).,, (Z)):.,. (Imag (z),.))) Then, we obtain the spectrum masks by leveraging both the amplitude and phase information
M MLP(Reall Z)) |Imag (Z), M, sigmoid
(M (M/T),
(igmoid-MM/n
(4)
where MLP denotes multi-layer perceptrons. 7 is the temporature, M, E [0, 1] and My [0, 1] denote the spectrum mask for invariant and variant patterns, and represents the concatenation of the embeddings. In this way, the invariant and variant masks have a negative relationship, and each node can have its own spectrum mask. As the phase information includes high-level semanties in the we keep the phase information unchanged to reduce harm in the fine-gre ine-grained semantic information for the graph trajectories, and filter the spectrums by the learned disentangled masks in terms of amplitudes.
original signals [29 30 31 32 33
[Mr Amp(Z) (oos (Z) + sin (Z)), Zv (My @ Amp(Z)) (cos (ZZ) + jin (Z)). (5)
where Z, and Zy denote the summarized invariant and variant patterns in the spectral domain. For
node classification tasks, we can directly adopt the spectrums for the classifier to predict classes. For
link prediction tasks, we can utilize inverse fast Fourier transform (IFFT) to transform the embeddings into the temporal domain for future link prediction
H "Z Z1, Hy $ "Z,,,
(6)
5

---

where (.)a is Hermitian transpose, H and Hy denote the filtered invariant and variant patterns that are transformed back into the temporal domain respectively.
4.3 Invariant Spectral Filtering
Under distribution shifts, the variant patterns on dynamic graphs have varying relationships with labels, while the invariant patterns have sufficient predictive abilities with regard to labels. We propose invariant spectral filtering to capture the invariant and variant patterns in the spectral domain, and help the model focus invariant patterns to make predictions, thus handling distribution shifts. We take node classification tasks for an example as follows.
Let Z E CxxNxd and Zy E CK xXxxxxxx be the filtered invariant and variant spectrums in the spectral domain. Then we can utilize the invariant and variant node spectrums to calculate the task loss
(7) where Sr(+) and fv(() are the classifiers for invariant and variant patterns respectively, Y is the labels, and / is the loss function. The task loss is utilized to capture the patterns with the predictive abilities of labels. Recall in Assumption[]] the influence of variant patterns on labels is shielded given invariant patterns as the invariant patterns have sufficient predictive abilities w.r.t labels, and thus the model's predictions should not change when being exposed to different variant patterns and the original invariant patterns. Inspired by [15 7 we calculate the invariance loss by
L ((fr(Zz). Ly = ((fvv(z))
(Zv), Y),
(8) where L. 2 denotes the mixed loss to measure the model's 's prediction ability with exposure to the specific variant pattern E C xd that is sampled from a set variant patterns S. We adopt all the node embeddings in Zv to construct the set of variant patterns S. Inspired by [34 15,, calculate the mixed loss as
LNNV = Var([Lm ă 7 E S}),
Lm ē (Z)) O ofy (z)), Y), where a denotes the sigmoid function. Then, the final training objective is
min Li + ALINV + min Lv.
(10)
fv
where is the parameters that encompass all the model parameters except the classifiers, À is hyper- parameter to balance the trade-off between the model's predictive ability and invariance properties. A larger encourages the model to capture patterns with better invariance under distribution shifts, with the potential risk of lower predictive ability during training, as the shortcuts brought by the variant patterns might be discarded in the training process. After training, we only adopt invariant patterns to make predictions in the inference stage. The overall algorithm for training on node classification datasets is summarized in Algo.
Algorithm 1 Training pipeline for SILD on node classification datasets
Require: Training epochs L, sample number S, hyperparameter À
1: for 1 1,.., L do
2: Obtain the node embeddings H with snapshot-wis message passing as Eq.
3: Transform the node embeddings into the spectral domain with FFT Eq.
4: Calculate the disentangled spectrum masks as Eq. (4]
5: Filter spectrums into invariant and variant patterns as Eq. (5)
6: Calculate the task loss as Eq. (
7: Sample variant patterns from collections of Zv and calculate the invariance loss as Eq.
8: Update the model according to Eq. (10)
9: end for
5
Experiments
In this section, we conduct extensive experiments verify that our proposed method can handle distribution shifts on dynamic graphs by discovering and utilizing invariant patterns in the spectral domain. More details of the settings and other results can be found in Appendix.
Baselines. We adopt several representative dynamic GNNs and Out-of (nn-offDDistributtoo(00111) general- ization methods as our baselines:

---

Table 1: Results of different methods on real-worke link prediction and node classification datasets. The best results are in bold and the second- best results are underlined. The year in the Aminer dataset denotes the test split, e.g. 'Aminer15" denotes the average test accuracy in 2015.
Task
Link Prediction (AUC%)
Node Classification (ACC%)
Dataset
Collab
Yelp
Aminer15
Aminer16
Aminer17
GCRN
69.72+004
54.68:17.59
47.96:1.12
51.33=0062
42.93
EGCN
76.151091
53.82.1206
44.14
46.28-1.4
37.71 1.84
DySAT
76.5911.20
66.0911142
18.411081
49.76
42.39
IRM
75.42.1087
56.02.16608
48.4440..3
50.18
42.40
VREx
76.74
66.41+1887
48. 70.77
49.24=0.27
42.59
GroupDRO
76,33++0.29
66.97=t0.1
48.73+0.61
49.74=0.26
42.80+0.36
DIDA
81,87+0.00
75.92:+090
50.34+081
51,43=027
44.69+0.0
SILD
84.09:00.1
78.65+2222
52.35+1.04
54.11=0.2
45.54
Table 2: Results of different methods on synthetic link prediction and node classification datasets.
The best results are in bold and the second-best results are underlined. A larger 'shift' denotes higher distribution shift level.
Dataset Shift
Link- Sink-Synthetic (AUC%)
Node-Synthetic (ACC%)
0.4
0.6
0.8
0.4
0.6
0.8
GCRN
72.57
72.29
67 10.26
27.19
25.95
29.26:10.69
EGCN
69.00
62.70.1.14
60.1310.88
24.01 1:229
19.29
22.75
24.98
DySAT
70.24+1.26
64.01+0.19
62.19
40.95+2.89
37.94+1.01
30.90+1.97
IRM
69.40+0.09
63.97=0.37
62,66=0.33
33.23+4.70
30.29
29.4 1.34
VREx
70.44+1.08 .88
63.99+0.21
62.21
41.78:+1.30
38.114281
29.56+0044
GroupDRO
10.30+1.23
64.05
62.13
41.35
35.74
31,03
DIDA
85.20
82.89
72.59
43.33
39.48
28. 14::3077
SILD
85.95
84.69+1.18
78.01
43.62:+274
39.78:3.56
38.64
Dynamic GNNs: GCRN 335 is representative dynamic GNN that first adopts GCN 36 to
obtain node embeddings and then a GRU [37] to model the network evolution. EGCN (5 adopts
LSTM (38 or GRU (37] flexibly evolve the GCN (36) parameters through time. DySAT 24
aggregates neighborhood information at each graph snapshot using structural attention and models
network dynamies with temporal self-attention
OOD generalization methods: IRM (20 aims at learning an invariant predictor which minimizes the empirical risks for all training domains. GroupDRO 39 puts more weight on training domains with larger errors to minimize the worst-group risks across training domains. V-REx 44) reduces the differences in the risks across training domains to reduce the model's 's sensitivity to distributional shifts. As these methods are not specifically designed for dynamic graphs, we adopt the best- performedd dynamic GNNs as their backbones on each dataset.
OOD generalization methods for dynamic graphs: DIDA 7 utilizes disentangled attention to capture invariant and variant patterns in the temporal intervention mechanism let the model focus on invariant patterns make predictions.
domain, and conducts spatial-
5.1 Real-world Datasets
Settings We use 3 real-world dynamic graph datasets, including Collab Yelp 2 and Following [7), we adopt the challenging inductive future link prediction task on Collab and Yelp, where the model should exploit historical graphs to predict the occurrence of links in the next time step. To measure the model's performance under distribution shifts. the model is tested on another dynamic graph with different fields, which unseen during training. For node classification, we adopt Aminer, a citation network, where nodes represent papers, and edges from o with timestamp denote the paper published year / cites the paper w. The task to predict the venues of the papers. We train papers published between 2001 2011, validate
Aminer [42 43
7

---

those published in 2012 - 2014, and test on those published since 2015. On this dataset, the model is tested to exploit the invariant patterns and make stable predictions under distribution shifts, where the patterns on the dynamic graph may vary in different years.
Results Based on the results in Table we have the following observations: 1) Under distribution shifts, the general OOD generalization baselines have limited improvements over the dynamic GNNs, e.g. GroupDRO improves over DySAT with 0.9% in Yelp and 0.3% in Aminerl5 respectively. A plausible reason is that they are not specially designed to handle distribution shifts dynamic graphs, and may not consider the graph structural and temporal dynamics to capture invariant patterns. Another reason might be that they strongly rely on high-quality environment labels to capture invariant patterns, which are almost unavailable on real-world dynamic graphs. 2) Our method can better handle distribution shifts than the baselines. The datasets have strong distribution shifts, e.g., COVID-19 happens midway and has considerable influence on the consumer behavior on Yelp, and the citation patterns may shift with the outbreak of deep neural networks on Aminer. Nevertheless, our method SILD has significant improvements over the state-of-the-art OOD generalization baseline for dynamic graphs DIDA on all datasets, e.g., 2% on average for most datasets, which verifies that our method can better capture the invariant and variant patterns in the spectral domain, and thus handling distribution shifts on dynamic graphs.
5.2 Synthetic Datasets
Settings To evaluate the model's generalization ability under distribution shifts, we conduct ex- periments on synthetic link prediction and node classification datasets, which are constructed by introducing designe distribution shifts. For link prediction datasets, we follow [7] to generate additional varying features for each node and timestamps on the original dataset Collab, where these additional features are constructed with spurious correlations w.r.t the labels, i.e., the links in the next timestamps. The spurious correlation degree determined by a shift level parameter. On this dataset, to have better generalization ability. the model should not rely on variant patterns that exploit the additional features with spurious correlations. For node classification, we briefly introduce the construction of the synthetic dataset as follows. We generate the dynamic graph with stochastic block model 444, where the link probability between nodes at each graph snapshot is determined by two frequency factors. The correlation of one of the factors with class labels is always 1, while the other factor has a variant relationship with labels, where the relationship is also controlled by a shift level parameter. The model should discover and focus the invariant frequency factors whose relationship with labels is invariant under distribution shifts. For both datasets, we set the shift level parameters as 0.4, 0.6, 0.8 for training and validation splits, and 0 for test splits.
Results Based on the results in Table we have the following observations: 1) Our method can better handle distribution shifts than the baselines, especially under stronger distribution shifts. SILD consistently outperforms DyGNN and general OOD generalization baselines by significantly large margin, which can credit to our special design to handle distribution shifts dynamic graphs in the spectral domain. Our method also has a significant improvement over the best-performed baseline under the strongest distribution shift, e.g., with absolute improvements of 5% in Link- Synthetic(O.88 and 7% in Node-Synthetice patterns to consistently alleviate the harmful effects of variant patterns under different distribution shift levels. As the distribution shift level increases, almost all methods decline in performance since the relationship between variant patterns and labels goes stronger, so that the variant patterns are much easier to be exploited by the model, misleading the training process. However, the performance drop SILD is significantly lower than baselines. which demonstrates that our method can alleviate the harmful effects of variant patterns under distribution shifts by exploiting invariant patterns in the spectral domain.
respectively. 2) Our method can exploit invariant
5.3 Ablation Studies
We conduct ablation studies to verify the effectiveness of the proposed disentangled spectrum mask and invariant spectral filtering SILD. The ablated version 'SILD w/o I' removes invariant spectral filtering in SILD by setting À = 0, and 'SILD w/o M' is trained without the disentangled spectrum masks. From Figure 3 we have the following observations. First, our proposed SILD outperforms all the variants as well as the best-performed bascline on all datasets, demonstrating the effectiveness of
8

---

Best baseline
SILD
SILD woo
SILD w/o M
Perforaance (9)
19
74
16-
Collab
Yelp
Aminer
Link-Synthetic
Node-Synthetic
Figure 3: Results of ablation studies, where 'w/o removes invariant spectral filtering in SILD, 'w/o M' removes disentangled spectrum masks, and 'Best baseline' denotes the best- best-performed baseline on each dataset. The error bars report the standard deviations. (Best viewed color)
each component of our proposed method. Second, 'SILD w/o I' and 'SILD w/o M' drop drastically in performance on all datasets compared the full version, which verifies that our proposed disentangled spectrum mask and spectral invariant learning can help the model to focus on invariant patterns to make predictions and significantly improve the performance under distribution shifts.
6 Related Works
Dynamic graphs ubiquitously exist in real-world applica- such as event forecasting, recommendation. etc. In compari- dynamic graphs contain rich temporal information. Con- siderable research attention has been devoted to dynamic graph neural networks (DyGNNs) [I 60) to model the complex graph dynamics that include structures and features evolving through time. Some works adopt GNN to aggregate neighborhood information for each graph snapshot, and then utilize a sequence module to model the temporal information 61
Dynamic Graph Neural Networks
tions [45 46 47
48
49
50
51
52
53
with static graphs 54
55
56
58
59
Some others utilize time-encoding techniques to encode the temporal links into time-aware embeddings and adopt 66 67 to process structural information. Some other related works leverage spectral graph neural networks [68], global graph framelet convolution (69], and graph wavelets [70] to obtain better dynamic graph representations. However, distribution shifts remain largely unexplored in dynamic graph neural networks literature. The sole prior work DIDA 7 handles spatial-temporal distribution shifts on dynamic graphs in the temporal domain. To the best of our knowledge, this is the first study of handling distribution shifts on dynamic graphs in the spectral domain.
63
GNN or memory module 64 65
Diitr---ittiittionn Generalization A significant proportion of existing machine learning method- ologies operate on the assumption that training and testing data are independent and identically distributed (i...d.). However, this assumption may not always hold true, especially in the context of complex real-world scenarios 771), and the uncontrollable distribution shifts between training and test- ing data distribution may lead to significant decline in the model performance.
(OOD) generalization problem has recently drawn great attention in various areas
72
73
Some
works handle structural distribution shifts static graphs [5
16 75 76
78
79
80
8]
and temporal distribution shifts on time-series data [ 12 13 44 82). However, how to handle
distribution shifts dynamic graphs in the spectral domain remains unexplored.
Spectral Methods in Neural Networks The applications of spectral methods in neural networks have been broadly explored in many areas, including static graph data [3 84
87 time- series data [68] 88 89 90) 91], etc., for their advantages of modeling global patterns, powerful
85
86
expressiveness and interpretability [92 28). Some work [93] proposes to reconstruct the image in the
spectral domain obtain robust image representations. Some work (2 proposes to augment image data by perturbing the amplitude information in the spectral domain. Some work [94] proposes a multiwavelet-based method for compressing operator kernels. However, these methods are not applicable to dynamic graphs, not to mention the more complex scenarios under distribution shifts.

---

7 Conclusion
In this paper, we propose a novel model named Spectral Invariant Learning for Dynamic Graphs under Distribution Shifts (SILD), which can handle distribution shifts on dynamic graphs in the spectral domain. We design a DyGNN with Fourier transform to obtain the ego-graph trajectory spectrums. Then we propose a disentangled spectrum mask and invariant spectral filtering to discover the invariant and variant patterns in the spectral domain, and help the model rely on invariant spectral patterns to make predictions. Extensive experimental results on several synthetic and real-world datasets, including both node classification and link prediction tasks, demonstrate the superior performance of our method compared to mate-of-the-art baselines under distribution shifts. One limitation is that in this paper we mainly focus on dynamic graphs in scenarios of discrete snapshots, and we leave extending our methods to continuous dynamic graphs for further explorations.
Acknowledgements
This work was supported by the National Key Research and Development Program of China No. 0120AAA0106000 National Natural Science Foundation of China (No. 62222209, 62250008, 62102222, 62206 14)), Beijing National Research Center for Information Science and Technology under Grant No. BNR2023RC01003, BNR2023TD03006, China National Postdoctoral Program for Innovative Talents No. BX20220185, China Postdoctoral Science Foundation No. 2022M711 1813, and Beijing Key Lab of Networked Multimedia. All opinions, findings, conclusions, and recommendations in this paper are those of the authors and do not necessarily reflect the views of the funding agencies.
References
[1] Joakim Skarding, Bogdan Gabrys, and Katarzyna Musial, Foundations and modeling of dynamic networks using dynamic graph neural networks: A survey. IEEE Access, 9779143-79168, 2021.
[2] Yuecai Zhu, Fuyuan Lyu, Chengming Hu, Xi Chen, and Xue Liu. Learnalee eneoder-decoder architecture for dynamic graph: A survey. arXiv preprint arXiv:2203. 10480, 2022.
[3] Stephen J Brown, William Goetzmann, Roger G Ibbotson, and Stephen A Ross. Survivorship bias in performance studies. The Review of Financial Studiex, 5(4):553-580, 1992.
[4] Richard A Berk. An introduction sample selection hias in sociological data, American sociological review, pages 386-398, 1983.
[5] Qi Zhu, Natalia Ponomareva, Jiawei Han, and Bryan Perozzi. Shift-robust gnns: Overcoming the limitations of localized graph training data. Advances in Neural Information Processing Systems. 34, 2021.
[6] Taesung Kim, Jinhee Kim, Yunwon Tac, Cheonbok Park, Jang-Ho Choi, and Jacgul Choo. Reversible instance normalization for accurate time-series forecasting against distribution shift. In International Conference on Learning Representations, 2021.
[7] Zeyang Zhang. Xin Wang, Ziwei Zhang, Haoyang Li, Zhou Qin, and Wenwu Zhu. Dynamic graph neural networks under spatio-temporal distribution shift. In Advances in Neural Information Processing Systems, 2022.
[8] Jayanta Mondal and Amol Deshpande. Managing large dynamic graphs efficiently. In Proceedings of the 2012 ACM SIGMOD International Conference Management Data, pages 145-156, 2012.
[9] Tuan Nhon Dang, Nick Pendar, and Angus Graeme Forbes. Timeares: Visualizing fluctuations in dynamic networks. In Computer Graphics Forum, volume 35, pages 61-69. Wiley Online Library, 2016.
[10] Jozef Barunik, Michael Ellington, et al. Dynamic networks in large financial and economic systems. arXiv preprint wxXi:22007.78443 2020.
[11] Jean-Ch Can-Chrittophe Biggoon-Audel Kartik Ahuja, Mohammad- Javad Darvishi- Darvishi-Rayari, Guillaume Dumas, and Trina Rish. Woods: Benchmarks for out-of-distributiinn generalization in time series tasks. arXiv preprint 20X00:2003009978 2022.
[12] Yuntao Du Jindong Wang, Wenjie Feng, Sinno Pan, Tao Qin, Renjun Xu, and Chongjun Wang. Adarnn: Adaptive learning and forecasting of time series. In Proceedings of the 30th ACM International Conference Information & Knowledge Management, pages 402 411,,11,1 2021.
10

---

[13] Praveen Venkateswaran, Vinod Muthusamy, Vatche Isahagian, and Nalini Venkatasabramanian. Environ- ment agnostic invariant risk minimization for classification of sequential datasets. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1615-1624, 2021.
[14] Wang Lu, Jindong Wang, Yiqiang Chen, and Xinwei Sun. Diversify to generalize: Learning generalized representations for time series classification, arXiv preprint arXiv:2209.0000 2021.
[15] Ying-Xin Wu, Xiang Wang, An Zhang, Xiangnan Hc, and Tat-Seng Chua. Discovering invariant rationales for graph neural networks. arXiv preprint arXiv:2201 /2872, 2022.
[16] Qitian Wu, Hengrui Zhang, Junchi Yan, and David Wipf. Handling distribution shifts graphs: An invariance perspective. arXiv preprint 220.:2202.022666 2022.
[17] Mucong Ding, Kezhi Kong, Jiuhai Chen, John Kirchenbauer, Micah Goldblum, David Wipf, Furong Huang, and Tom Goldstein. A closer look at distribution shifts and out-of-distribution generalization on graphs. In NewrlPS 2021 Workshop on Distribution Shifts: Connecting Methods and Applications, 2021.
[18] Tian Jin, Qiong Wu, Xuan Ou, and Jianjun Yu. Community detection and co-author recommendation in co-author networks. International Journal of Machine Learning and Cybernetics, 12(2):597-609, 2021.
[19] Wenjie Wang, Xinyu Lin, Fuli Feng, Xiangnan He, Min Lin, and Tat-Seng Chua. Causal representation learning for duitr--diitrituttin recommendation. In Proceddings of the ACM Web Conference 2022, pages 3562-3571, 2022.
[20] Martin Arjovsky, Léon Bottou, Ishaan Guirajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint arXiv: (ee.) 028999....... 2019.
[21] Shiyu Chang, Yang Zhang, Mo Yu, and Tommi Jaakkola. Invariant rationalization. In International Conference on Machine Learning, pages 1458. PMLR, 2020.
[22] Kartik Ahuja, Karthikeyan Shanmugam, Kush Varshney, and Amit Dhurandhar. Invariant risk minimization games. In International Conference on Machine Learning, pages 145-155. PMLR, 2020.
[23] Jiaxuan You, Tianyu Du, and Jure Leskovec. Roland: graph learning framework for dynamic graphs. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pages 2358-2366, 2022.
[24] Aravind Sankar, Yanhong Wu, Liang Gou, Wei Zhang, and Hao Yang. Dysat: Deep neural representation learning on dynamic graphs via self-attention networks. In Proceedings of the 13th International Conference on Web Search and Data Mining, pages 519-527, 2020.
[25] Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, Tao Schardl, and Charles Leiserson. Evolvegen: Evolving graph convolutional networks for dynamic graphs. Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5363- 5370. 2020.
[26] James W Cooley and John W Tukey. An algorithm for the machine calculation of complex fourier series. Mathematics of computation, 190i),n,,.9999900/ 19900)) 1965.
[27] Ronald Newbold Bracewell and Ronald N Bracewell. The Fourier transform and its applications, volume 31999. McGraw-Hill New York, 1986.
[28] Kun Yi, Qi Zhang, Shoujin Wang, Hui He, Guodong Long, and Zhendong Niu. Neural time series analysis with fourier transform: A survey, arXiv preprint arXiv:2302.02 2023.
[29] Qinwei Xu, Ruipeng Zhang, Ya Zhang, Yanfeng Wang, and Qi Tian. A fourier-based framework for domain generalization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 14383 14392, 2021.
[30] Bruce C Hansen and Robert F Hess. Structural sparseness and spatial phase alignment in natural scenes. JOSA A, 2477)_183-11855 2007.
[31] Alan V Oppenheim and Jac S Lim. The importance phase in signals. Proceedings of the IEEE, 5955)522-55,, 1981.
[32] Leon N Piotrowski and Fergus W Campbell. A demonstration of the visual importance and flexibility of spatial- frequency amplitude and phase. Perception, 11(3):337-346, 1982.
11

---

[33] A Oppenheim, Jae Lim, Gary Kopec, and SC Pohlig. Phase in speech and pictures. In /CASSP'79, IEEE International Conference Acoustics, Speech, and Signal Processing, volume 4, pages 632-637. IECE, 1979.
[34] Remi Cadene, Corentin Dancetie, Matthieu Cord, Devi Parikh, et al. Rubi: Reducing unimodal biases for visual question answering. Advances in neural information processing systems, 32, 2019.
[35] 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, pages 362- 002-373.355 Springer, 2018
[36] Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv: 1.07308 2016.
[37] Kyunghyun Cho, Bart van Merrienboer, Çaglar Gülgehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using mn decoderr for statistical machine translation. EMNLP, 2014.
[38] Sepp Hachreiter and Jürgen Schmidhuher. Long short-term memory. Neural computation, 18):1735- 1997.
[39] Shiori Sagawa, Pang Wei Koh, Tatsunori Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. arXiv preprint arXiv: 19tp:/991..87// 2019.
[40] David Krueger, Ethan Caballero, Joern-Henrie Jacobsen, Amy Zhang, Jonathan Binas, Dinghuai Zhang, Remi Le Priol, and Aaron Courville. Out-of-distribution generalization via risk extrapolation (rex). In International Conference on Machine Learning, pages 5815-5826. PMLR, 2021.
[41] Jie Tang, Sen Wu, Jimeng Sun, and Hang Su. Cross-domain collaboration recommendation. In KDD '2012 2012.
[42] Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. Ametminer: extraction and mining of academic social networks. Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 990- 998, 2008
[43] Amah Sinha, Zhihong Shen, Yang Song, Hao Ma, Darri Fide, Bo-june Paul Hsu, and Kuansan Wang. An overview of microsoft academic service (mas) and applications. In Proceedings of the 24th international conference world wide web, pages 243-246. ACM. 2015.
[44] Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social Networks, 5(2):109-11) 137, 1983.
[45] Lei Cai, Zhengzhang Chen, Chen Luo, Jiaping Gui, Jingchao Ni, Ding Li, and Haifeng Chen. Structural temporal graph neural networks for anomaly detection in dynamic graphs. In Proceedings of the 30th ACM international conference on Information Knowledge Management, pages 3747-3756, 2021
[46] Songgaojun Deng, Huzefa Rangwala, and Yue Ning. Dynamic knowledge graph based multi-event forecasting. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1585-1595, 2020.
[47] Jiaxuan You, Yichen Wang, Aditya Pal, Pong Eksombatchai, Chuck Rosenburg, and Jure Leskovec. Hierarchical temporal convolutional networks for dynamic recommender systems. In The world wide web conference, pages 2236 2246, 2019.
[48] Yanbang Wang, Pan Li, Chongyang Bai, and Jure Leskovec. Tedic: Neural modeling of hehavioral patterns in dynamic social interaction networks. In Proceedings of the Web Conference 202/, pages 693-705, 2021.
[49] Haoyang Li, Peng Cui, Chengxi Zang, Tianyang Zhang, Wenwu Zhu, and Yishi Lin. Fates of microscopic social ecosystems: Keep alive dead? In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 668-676, 2019.
[50] Jiapeng Wu, Meng Cao, Jackie Chi Kit Cheung, and William L. Hamilton. Temp: Temporal message passing for temporal knowledge graph completion. arXiv preprint arXiv:2010.03526, 2020.
[51] Zeyang Zhang, Ziwei Zhang. Xin Wang, Yijian Qin, Zhou Qin, and Wenwu Zhu. Dynamic heterogeneous graph attention neural architecture search. In Thirty-Seventh AAAI Conference on Artificial Intelligence. 2023.
12

---

[52] Zeyang Zhang, Xingwang Li, Fei Teng, Ning Lin, Xueling Zhu, Xin Wang. and Wenwu Zhu. Out-of- distribution generalized dynamic graph neural network for human albumin prediction. IEEE International Conference on Medical Artificial Intelligence, 2023.
[53] Zeyang Zhang, Xin Wang, Ziwei Zhang, Haoyang Li, Yijian Qin, Simin Wu, and Wenwu Zhu. Llm4dyg: Can large language models solve problems on dynamic graphs? arXiv preprint, 2023.
[54] Ziwei Zhang, Peng Cui, and Wenwu Zhu. Deep learning on graphs: A survey. IEEE Transactions on Knowledge and Data Engineering, 34(1):249-21) 2020.
[55] Zeyang Zhang. Xin Wang, Ziwei Zhang. Haoyang Li, Guangyao Shen, Shiqi Shen, and Wenwu Zhu. Unsupervised graph neural architecture search with disentangled supervuuevisson. In Advances Neural Information Processing Systems, 2023.
[56] Chaoyu Guan, Ziwei Zhang, Haoyang Li, Heng Chang, Zeyang Zhang, Yijian Qin, Jiyan Jiang, Xin Wang. and Wenwu Zhu. Autogl: A library for automated graph learning. In ICLR 2021 Workshop GTRL, 2021.
[57] Yijian Qin, Ziwei Zhang, Xin Wang. Zeyang Zhang. and Wenwu Zhu. bra-beech-:raph: Benchmarking graph neural architecture search. In Shirtt--ixxhh Conference Neural Information Processing Systems, 2022.
[58] Yijian Qin, Xin Wang. Zeyang Zhang, and Wenwu Zhu. Graph differentiable architecture search with structure learning. In Thirty-Fifit Conference on Neural Information Processing Systems, 2021.
[59] Ziwei Zhang, Haoyang Li, Zeyang Zhang, Yijian Qin, Xin Wang, and Wenwu Zhu. Large graph models: A perspective. arXiv preprint arXiv:2308. 14522, 2023.
[60] Chao Chen, Haoyu Geng, Nianzu Yang. Xiaokang Yang, and Junchi Yan. Fasydgl: Encode, train and interpret for continuous-time dynamic graph learning. arXiv preprint arXiv:2303. 12341, 2023.
[61] Menglin Yang, Min Zhou, Marcus Kalander, Zengfeng Huang, and Irwin King. Discrete time temporal network embedding via implicit hicrarchical learning in hyperbolic space. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1985, 2021.
[62] Li Sun, Zhongbao Zhang, Jiawei Zhang. Feiyang Wang, Hao Peng, Sen Su, and Philip S Yu. Hyperbolic variational graph neural network for modeling dynamic graphs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 4375-4383, 2021.
[63] Ehsan Hajiramezanali, Arman Hasanzadeh, Krishna Narayanan, Nick Duffield, Mingyuan Zhou, and Xiaoning Qian. Variational graph recurrent neural networks. Advances in neural information processing systems, 32, 2019.
[64] Yanbang Wang, Yen- Yu Chang, Yunyu Liu. Jure Leskovec, and Pan Li. Inductive representation learning in temporal networks via causal anonymous walks. arXiv preprint arXiv:2101.055 055744 2021.
[65] Weilin Cong, Yanhong Wu, Yuandong Tian, Mengting Gu, Yinglong Xia. Mehrdad Mahdavi, and Chun- cheng Jason Chen. Dynamic graph representation learning via graph transformer networks. arXiv preprint 1.Xiv:2111.10447, 2021.
[66] Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan, Inductive representation learning temporal graphs. arXiv preprint arXh::2002.07962, 2020.
[67] Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bron- stein. Temporal graph networks for deep learning on dynamic graphs. arXiv preprint arXiv:2006. 106337 2020.
[68] Defu Cao, Yujing Wang. Juanyong Duan, Ce Zhang. Xia Zhu, Congrui Huang. Yunhai Tong. Bixiong Xu, Jing Bai, Jie Tong, et al. Spectral temporal graph neural network for multivariate time-series forecasting. Advances in neural information processing systems, 33:1 33:1778 17766-77778 2020.
[69] Bingxin Zhou, Xinliang Liu, Yuehua Liu, Yunying Huang, Pietro Lio, and Yu Guang Wang. Well- conditioned spectral transforms for dynamic graph representation. In Learning on Graphs Conference, pages 12-1. 1, PMLR, 2022.
[70] Anson Bastos, Abhishek Nadgeri, Kuldeep Singh, Toyotaro Suzumura, and Manish Singh. Learnall spectral wavelets on dynamic graphs to capture global interactions. arXiv preprint 4rXi::221..1197, 2022.
13

---

[71] Zheyan Shen, Jiashuo Liu, Yue He. Xingxuan Zhang, Renzhe Xu, Han Yu, and Peng Cui, Towards out-of-distribution generalization: A survey. arXiv preprint arXiv:2108. 136244 2021.
[72] Kaiyang Zhou, Ziwei Liu, Yu Qiao. Tao Xiang, and Chen Change Loy. Domain generalization: A survey. arXiv e-prints, pages arXiv- 2021.
[73] Huaxiu Yao, Yu Wang, Sai Li, Linjun Zhang, Weixin Liang. James Zou, and Chelsea Finn. Improving out-of-distribution robustness via selective augmentation. In Proceeding the Thirty-nimth International Conference on Machine Learning, 2022.
[74] Haoyang Li. Xin Wang. Ziwei Zhang. and Wenwu Zhu. Out-of-distribttion generalization on graphs: survey. Xrxiv preprint urXiv:2202.07960 2022.
[75] Yongqiang Chen, Yonggang Zhang, Han Yang, Kaili Ma, Binghui Xie, Tongliang Liu, Bo Han, and James Cheng. Invariance principle meets out-of-distribution generalization on graphs. arXiv preprint WwXiv:2202.05441,22
[76] Yijian Qin, Xin Wang. Ziwei Zhang. Pengtao Xie, and Wenwu Zhu. Graph neural architecture search under distribution shifts. In International Conference on Machine Learning, pages 18083-18095. PMLR, 2022.
[77] Hanyang Li, Xin Wang, Ziwei Zhang, and Wenwu 7hu. Ood-gnn: distriitiitiiiitionnn generalized graph neural network. IEEE Transactions on Knowledge and Data Engineering, 2022.
[78] Zeyang Zhang. Ziwei Zhang, Xin Wang, and Wenwu Zhu, Learning to solve travelling salesman problem with aadpnivs-ddaptive curriculum. arXiv preprint Xxxv:2204.032.66 2022.
[79] Ziwei Zhang, Xin Wang, Zeyang Zhang, Peng Cui, and Wenwu Zhu. Revisiting transformation invariant geometric deep learning: Are initial representations all you need? arXiv preprint arXiv:21 12.1245, 2021.
[80] Shaohua Fan, Xiao Wang, Chuan Shi, Peng Cui, and Bai Wang. Generalizing graph neural networks on out-of-distribution graphs. arXiv preprint arXiv:2111, 10657, 2021.
[81] Haoyang Li, Ziwci Zhang, Xin Wang, and Wenwu Zhu. Learning invariant graph representations for distribbbbti generalization. In Thitty-Sixth Conference on Neural Information Processing Systems, 2022.
[82] Huaxiu Yao, Caroline Choi, Yoonho Lee, Pang Wei Koh, and Chelsca Finn. Wild-time: A benchmark of in-the-wild distribution shift over time. In Proceedings of the Thirty-sixth Conference Neural Information Processing Systems Datasets and Benchmarks Track, 2022.
[83] Michaël Defferrard Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
[84] Bingbing Xu, Huawei Shen, Qi Cao, Yunqi Qiu, and Xueqi Cheng. Graph wavelet neural network. arXiv preprint 19X.v:9044.0777 07785, 2019.
[85] Henry Kenlay, Dorina Thanou, and Xiaowen Dong. Interpretable stability bounds for spectral graph filters. In Intermational conference on machine learning, pages 5388-5397. PMLR, 2021.
[86] Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. In International Conference on Machine Learning, pages 23341 23362. PMLR, 2022.
[87] Deyu Bo. Chuan Shi, Lele Wang. and Renjie Liao. Specformer: Spectral graph neural networks meet transformers. arXiv preprint arXiv:2303.01022 2023.
[88] Robert Salomone, Matias Quiroz. Robert Kohn, Mattias Villani, and Minh-Ngoc Tran. Spectral subsam- pling meme for stationary time series, International Conference on Machine Learning, pages 8449 8458. PMLR, 2020.
[89] Henning Lange, Steven L Brunton, and Nathan Kutz. From fourier koopman: Spectral methods for long-term time series prediction. The Journal of Machine Learning Research, 22(1):1881 19918, 2021.
[90] Tian Zhou, Ziqing Ma. Qingsong Wen, Xue Wang. Liang Sun, and Rong Jin. Fedformer: Frequency enhanced decomposed transformer for long-term series forecasting. In International Conference on Machine Learning, pages 27268-27286. PMLR, 2022.
[91] Xiang Zhang, Ziyuan Zhao, Theodoros Tsiligkaridis, and Marinka Zimik.. Self-supervised contrastive pre-training for time series via time- freefreyy consistency. Advances in Neural Information Processing Systems, 35:3988 4003, 2022.
14

---

[92] Deyu Bo, Xiao Wang, Yang Liu, Yuan Fang, Yawen Li, and Chuan Shi. A survey on spectral graph neural networks. arXiv preprini arXiv:2302.056:3 2023.
[93] Liming Jiang, Bo Dai, Wayne Wu, and Chen Change Loy. Focal frequency loss for image reconstruction and synthesis. In Proceedings of the IEEE/CVF International Conference Computer Vision, pages 13919-13922 13929, 2021.
[94] Gaurav Gupta, Xiongye Xiao, and Paul Bogdan. Multiwavelet-bnsed operator learning for differential equations, Advances neural information processing systems, 34:24048 22062, 2021.
15


Reviews:
[{"review_id": "3EYnD5ffg1", "reviewer": "Reviewer_vwaL", "summary": "This paper finds that there are cases with distribution shifts observable in the spectral domain while difficult to distinguish in the time domain. Based on this characteristic, the authors propose  Spectral Invariant Learning for Dynamic Graphs under Distribution Shifts (SILD) to handle distribution shifts on dynamic graphs in the spectral domain. A DyGNN with Fourier transform is designed to obtain the ego-graph trajectory spectrums. In addition, it develops a disentangled spectrum mask to filter graph dynamics and invariant spectral filtering to encourages the model to rely on invariant patterns. Experimental results verifies the superiority of this method under distribution shifts.", "questions": "Check the above weaknesses.", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Distribution shifts naturally exist in real-world dynamic graphs. Handling these issues is critical for the reliable applications of dynamic GNNs. The problem studied in this paper is valuable and the research perspective is novel.\n\n2. The paper is well-organized, and the analyses and examples given in the manuscript are easy to understand.\n\n3. Experimental results verify the superiority of this method under distribution shifts.", "weaknesses": "1. In Figure 2, the spectrums block (bottom-middle) seems a little confusing. I guess it shows a temporal signal of a node can be decomposed into amplitudes and phases in the spectral domain.\n\n2. In Line 195, what does the parameters $\\theta$ contain specifically?\n\n3. Typo in Table 2 caption. \n\n4. The construction of synthetic datasets seems complex. Can you provide the intuitions concisely?\n\n5. It seems $\\epsilon$ refers to random noise in Assumption 1, while it represents an arbitrary number in the proof.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our sincere gratitude to the reviewer for providing us with detailed comments and insightful questions. We have carefully considered the reviewer's feedback and would like to address each point as follows:\n\n> In Figure 2, the spectrums block (bottom-middle) seems a little confusing. I guess it shows a temporal signal of a node can be decomposed into amplitudes and phases in the spectral domain.\n\nThank you for your comment. Indeed, the spectrums block in Figure 2 illustrates the decomposition of a temporal signal of a node into amplitudes and phases in the spectral domain. To achieve this, we utilize dynamic graph neural networks with spectral transform to obtain ego-graph trajectory spectrums. Subsequently, the disentangled spectrum mask makes use of the amplitude and phase information from these spectrums to derive invariant and variant spectrum masks. We acknowledge the confusion caused by the current depiction and will make improvements to the diagram in the revised version of the main paper.\n\n> In Line 195, what does the parameters contain specifically?\n\nThank you for bringing this to our attention. The parameters denoted as $\\theta$ encompass all the network parameters, excluding the classifiers. These parameters are primarily associated with the dynamic graph neural network and disentangled spectrum masks. In response to your feedback, we will provide more detailed descriptions of the parameters in the revised version of the main paper.\n\n> Typo in Table 2 caption. It seems $\\epsilon$ refers to random noise in Assumption 1, while it represents an arbitrary number in the proof.\n\nWe appreciate your keen observation. You are correct that there is an inconsistency in the use of the symbol $\\epsilon$. In Assumption 1, $\\epsilon$ indeed refers to random noise, while in the proof of the propositions, $\\epsilon$ represents an arbitrary positive real number. We apologize for this oversight and will rectify the typo in the caption. Additionally, we will ensure consistency in the notation throughout the revised version of the main paper.\n\n> The construction of synthetic datasets seems complex. Can you provide the intuitions concisely?\n\nWe are grateful for your feedback. To provide a more concise and intuitive explanation of the construction of synthetic datasets, we offer the following summary. The underlying idea is to introduce spurious correlations in certain features and structures, requiring the model to rely on invariant patterns rather than variant ones when making predictions, even in the presence of distribution shifts.\n\nFor link synthetic datasets, we generate additional varying features that are concatenated with the original features. These additional features are specifically designed to exhibit spurious correlations with the labels, which represent the links at the next time step.\n\nFor node synthetic datasets, we generate dynamic graphs using a stochastic block model, where the probability of a link between nodes is determined by two frequency factors. One of these factors exhibits spurious correlations with the labels. The extent of spurious correlations in both datasets can be controlled using a parameter.\n\nWe appreciate your feedback and will revise the description to provide a clearer and more concise explanation in the updated version of the paper."}, {"review_id": "iukEI9U63M", "reviewer": "Reviewer_fiaV", "summary": "This paper addresses the problem of dynamic graph learning under distribution shifts. Distinct from the previous work that focuses on the time domain, the authors argue that there exists patterns that are not easily distinguished in the time domain while could be easier to recognize in the spectral domain. Some theoretical analyses and intuitive examples have been provided to clearly present the motivations. Based on these analyses, the authors propose a method named spectral invariant learning for dynamic graphs under distribution shift. The extensive experiments show that the method can well tackle the distribution shifts on dynamic graphs, and the performance is worthy of recognition. Detailed ablation studies also verify the effectiveness of each proposed components.", "questions": "- In line 87, the condition 2 assumes that the observed data is composed of invariant and variant patterns. Is it possible that there exist multiple invariant and variant patterns?\n\n- Some distribution shifts may stem from selection bias, e.g., some users in social networks may have much fewer or even no interactions in some periods. These issue let some temporal signals miss in some periods and nodes. And this seems to cause difficulties for the subsequent spectral analysis. It would be better to discuss this problem in the main paper.\n\n- The paper adopts Fourier transform as an implementation of spectral transform. It would be better to discuss whether other spectral transforms can be adopted.", "limitations": "None.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This work tackles the distribution shifts on dynamic graphs in the spectral domain for the first time. The paper is well written and easy to follow. \n\n- Some theoretical analyses and intuitive examples have been provided to clearly present the motivations. The motivations and the method designs sound reasonable.\n\n- The extensive experiments show that the method can well tackle the distribution shifts on dynamic graphs, and the performance is worthy of recognition.", "weaknesses": "Please see the Questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our sincere appreciation to the reviewer for providing us with detailed comments and suggestions. We have carefully reviewed each comment and offer the following responses:\n\n> In line 87, the condition 2 assumes that the observed data is composed of invariant and variant patterns. Is it possible that there exist multiple invariant and variant patterns?\n\nThank you for raising this point. We acknowledge that there can indeed be multiple invariant and variant patterns present in the observed data. In this paper, we define invariant patterns as those that maintain invariant relationships with the labels under distribution shifts, while variant patterns encompass all patterns that are not defined as invariant. Our disentangled spectrum mask is designed to handle cases with multiple invariant patterns by assigning higher mask scores to these patterns. Empirical results from our experiments on real-world datasets have demonstrated the effectiveness of our method in addressing complex scenarios involving real-world dynamic graphs under distribution shifts. \n\n> Some distribution shifts may stem from selection bias, e.g., some users in social networks may have much fewer or even no interactions in some periods. These issue let some temporal signals miss in some periods and nodes. And this seems to cause difficulties for the subsequent spectral analysis. It would be better to discuss this problem in the main paper.\n\nThank you for bringing up this important point. We acknowledge that distribution shifts originating from selection bias can indeed result in missing temporal signals and nodes in certain periods. To address this challenge, our model leverages the past graph trajectories to obtain node embeddings for nodes that may lack interactions during certain time intervals. Specifically, our model incorporates the past interactions in addition to the current interactions when aggregating neighborhood information and updating node embeddings. This approach helps mitigate the impact of missing signals to some extent. We have provided more detailed information about the model in Appendix D.1 to elaborate on this aspect.\n\n> The paper adopts Fourier transform as an implementation of spectral transform. It would be better to discuss whether other spectral transforms can be adopted.\n\nWe appreciate your suggestion. In this paper, our primary focus is on handling distribution shifts on dynamic graphs in the spectral domain, which remains an underexplored area in the literature. We have chosen Fourier transform due to its efficiency, semantic interpretability, and ability to capture global and periodic patterns [1-2]. We will extend our method to incorporate other spectral transforms such as Wavelet transform or more sophisticated techniques in future research.\n\n[1] Brigham, E. Oran. The fast Fourier transform and its applications. Prentice-Hall, Inc., 1988.\n\n[2] Yi, Kun, et al. \"Neural Time Series Analysis with Fourier Transform: A Survey.\" arXiv preprint arXiv:2302.02173 (2023)."}, {"review_id": "2qNS3aq77S", "reviewer": "Reviewer_4zF7", "summary": "Dynamic graph neural networks are still facing the difficulty in handling distribution shifts. This work discovers that in some cases, distribution shifts are unobservable in the time domain but not in the spectral domain. There are currently no studies to handle cases involving distribution shifts in the spectral domain. To solve these problems, the authors propose Spectral Invariant Learning for Dynamic Graphs under Distribution Shifts. Specifically, a DyGNN with Fourier transform is designed to obtain the ego-graph trajectory spectrums. Furthermore, a disentangled spectrum mask to filter graph dynamics from various frequency components is developed. Finally, invariant spectral filtering is proposed, which can encourage the model to rely on invariant patterns for generalization under distribution shifts. Experimental results on synthetic and real-world dynamic graph datasets verified that this method is superior for node classification and link prediction tasks under distribution shifts.\n", "questions": "1) It would be great to include the F1 scores as metrics for comparisons of different methods in node classification tasks. \n2) In Figure 2, the calculation flow of the framework is not very clear, and it would be great to highlight the order of each module. \n3) Some notations should be more clear. For example, the notation '||' in Eq. 4  and $\\odot$ in Eq. 5. \n4) It would be great to include more related works about spectral methods.\n", "limitations": "The authors state that this paper mainly focuses on dynamic graphs in scenarios of discrete snapshots, and leave extending the method to continuous dynamic graphs for further explorations.\n", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper studies distribution shifts on dynamic graphs in the spectral domain for the first time. The idea for tackling temporal distribution shifts in the spectral domain is natural. The theoretical anaylses strengthen the motivations. Experimental results on synthetic and real-world dynamic graph datasets verified that this method is superior for node classification and link prediction tasks under distribution shifts.\n", "weaknesses": "1) It would be great to include the F1 scores as metrics for comparisons of different methods in node classification tasks. \n2) In Figure 2, the calculation flow of the framework is not very clear, and it would be great to highlight the order of each module. \n3) Some notations should be more clear. For example, the notation '||' in Eq. 4  and $\\odot$ in Eq. 5. \n4) It would be great to include more related works about spectral methods.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the valuable suggestions. We respond to the reviewer’s comments point by point as follows.\n\n> It would be great to include the F1 scores as metrics for comparisons of different methods in node classification tasks.\n\nThank you for your suggestion. Following your suggestion, we report the Macro-F1 scores of different methods on the node classification dataset Aminer in the following table.\n\n| Model | Aminer-15 | Aminer-16 | Aminer-17 |\n|---|---|---|---|\n| GCRN | 36.89+-0.42 | 37.65+-0.88 | 35.30+-0.78 |\n| EGCN | 33.47+-4.78 | 30.54+-3.77 | 28.02+-5.68 |\n| DySAT | 38.37+-1.27 | 38.19+-0.45 | 35.52+-1.02 |\n| IRM | 37.44+-0.82 | 37.28+-0.48 | 35.23+-1.24 |\n| VREx | 37.25+-0.58 | 37.11+-0.49 | 35.03+-0.54 |\n| GroupDRO | 38.30+-0.86 | 37.64+-1.03 | 35.44+-0.74 |\n| DIDA | 38.26+-0.37 | 38.45+-0.52 | 36.63+-1.08 |\n| Ours | 40.81+-0.41 | 40.17+-0.49 | 37.16+-0.96 |\n\nAs shown in the table above, our method has a significant performance improvement over the baselines in terms of the metric of Macro-F1, which further verifies the effectiveness of our method in handling distribution shifts on dynamic graphs.\n\n> In Figure 2, the calculation flow of the framework is not very clear, and it would be great to highlight the order of each module. Some notations should be more clear. For example, the notation '||' in Eq. 4 and in Eq. 5.\n\nThank you for your suggestions. We provide the calculation flow of the framework as follows: 1) First, given a dynamic graph, the dynamic graph neural networks with spectral transform obtain the ego-graph trajectory spectrums in the spectral domain. 2) Second, the disentangled spectrum mask leverages the amplitude and phase information of the spectrums to obtain invariant and variant spectrum masks.  3) Third, the invariant spectral filtering discovers the invariant and variant patterns via the disentangled spectrum masks and helps the model rely on the invariant patterns to make predictions under distribution shifts. In the revised version of the main paper, we will enhance the diagram to highlight the order of each module in the framework, providing a clearer visualization of the calculation flow. Additionally, we will make the notations more explicit and improve the clarity of the notation '||' in Eq. 4 and Eq. 5, clearly indicating that it represents the concatenation of the embeddings. We appreciate your feedback and will address these issues in the updated version.\n\n> It would be great to include more related works about spectral methods.\n\nThank you for your suggestion. While we have covered spectral methods relevant to handling graph and time-series data, we acknowledge the importance of including more related works on spectral methods in the revised version of the main paper. We will incorporate recent works that focus on Fourier neural operators to introduce spectral analysis in downstream tasks, such as partial differential equations. Specifically, we will include references to works like [1], which proposes a multiwavelet-based method for compressing operator kernels, and [2], which introduces Fourier-enhanced blocks and Wavelet-enhanced blocks for capturing important time-series features in the frequency domain. We appreciate your suggestion and will provide a more comprehensive discussion of related spectral methods in the updated version of the main paper.\n\n[1] Gupta, Gaurav, Xiongye Xiao, and Paul Bogdan. \"Multiwavelet-based operator learning for differential equations.\" Advances in neural information processing systems 34 (2021): 24048-24062.\n\n[2] Zhang, Xiang, et al. \"Self-supervised contrastive pre-training for time series via time-frequency consistency.\" Advances in Neural Information Processing Systems 35 (2022): 3988-4003.\n"}, {"review_id": "P7vl3oY37E", "reviewer": "Reviewer_QjfT", "summary": "This paper studies the distribution shifts, i.e., out-of-distribution generalization, on graph data and focuses on distribution shifts on temporal dynamic graphs. To this end, the authors propose a model from the spectral domain and resort to the established techniques of invariant learning. Experiments on synthetic and real-world data show the effectiveness of the proposed model when compared to a number of baselines.", "questions": "1. How the mixed loss L_{INV} is calculated and how the sampling for the variant patterns is conducted?\n\n2. What is the rationale of the objective (10)? Can it guarantee the disentanglement for the invariant/variant frequency components and a solution for OOD generalization? \n\n3. The model seems to need two fundamental assumptions: 1) the observed temporal graphs are generated by a mixture of invariant and variant frequency patterns; 2) the invariant and variant components can be strictly disentangled. The authors are encouraged to discuss more on this, especially for how universal these assumptions can be and what if they are violated in real data.\n\n4. How does the model perform compared to other graph OOD competitors that do not involve temporal modeling?", "limitations": "The proposed model is heavily based on the invariant learning framework on graph data, and the originality concerning the distribution shifts seems limited. The novel part from the frequency modeling can be an orthogonal technique that is also applicable for other problems beyond the out-of-distribution generalization, and the authors fail to argue the advantage and uniqueness of the frequency modeling w.r.t. the temporal OOD problem. This weakens the originality.\n\nAnother concern to me is the soundness of the model. The proposed method requires the assumptions for the data generation of the temporal graph that may not hold in most cases. Furthermore, even when the assumption holds, it is not clear how the model can guarantee disentanglement of the variant/invariant frequency components and a well-posed solution for OOD generalization.\n\nThe comparison is insufficient, especially lacking comparison with some common baselines that do not involve the time information on graph data, e.g., the base model GCN, GraphSAGE, etc., as well as the graph OOD models EERM [1] and DIR [2].\n\n[1] Qitian Wu, Hengrui Zhang, Junchi Yan, and David Wipf. Handling distribution shifts on graphs: An invariance perspective, ICLR 2022.\n\n[2] Ying-Xin Wu, Xiang Wang, An Zhang, Xiangnan He, and Tat-Seng Chua. Discovering invariant rationales for graph neural networks, ICLR 2022.\n\n**Post-rebuttal comments**\n\nAfter discussions, the paper has the following main issues:\n\n1. The novelty and contributions are limited. The proposed model has no essential difference to the NeurIPS22 work DIDA which has explored invariant learning on dynamic graphs.\n\n2. The motivation examples are flawed, and the model is vague. How the model actually learns invariant/variant frequency patterns is unclear. The theoretical results are trivial and the reproducibility is zero.\n\n3. The comparison and evaluation are limited. Some important OOD baselines are not compared or weakened in the experiments. The datasets are also small with a dozen graph snapshots, arousing a question whether the model can indeed learn complex invariant frequency patterns. There is no concrete verification for this critical point.\n\n4. The model section seems like a combination of existing works, but unfortunately, citations are not properly provided. For example, the model in Sec 4 has large overlap with DIR, the theoretical motivation in Sec 3 is similar to EERM, the experiment in Sec 5 is nearly the same as DIDA.", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 2, "contribution": 2, "strengths": "1. The problem of distribution shifts on graph data is significant and a research area of growing interest.\n\n2. The proposed model is well motivated and grounded.", "weaknesses": "1. The novelty is limited especially given that the model is based on the existing framework\n\n2. The presentation can be improved as some parts of the model section are unclear and confusing\n\n3. The empirical comparison is insufficient", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the insightful comments provided by the reviewer. We have carefully considered each point raised and would like to respond as follows:\n\n> How the mixed loss $\\mathcal{L}_{INV}$ is calculated and how the sampling for the variant patterns is conducted?\n\nThank you for your comment. We collect the variant patterns of all nodes to construct the variant pattern set $\\mathcal{S}$, and uniformly sample the variant patterns from the set without replacement. For each sampled variant pattern, a mixed loss is calculated by Eq. (9) to measure the model's prediction ability with exposure to the specific variant pattern. Finally, we obtain the invariance loss $\\mathcal{L}_{INV}$ by calculating the variance of the mixed loss as Eq. (8). We appreciate your question and will provide further clarification in the revised paper.\n\n> What is the rationale of the objective (10)? Can it guarantee the disentanglement for the invariant/variant frequency components and a solution for OOD generalization?\n\nThank you for your question. In objective Eq. (10), the task losses $\\mathcal{L}\\_{I}$ and $\\mathcal{L}\\_{V}$ are utilized to capture the invariant and variant patterns, and the invariance loss $\\mathcal{L}_{INV}$ encourages the model to rely on invariant patterns to make predictions. In this way, the model is encouraged to disentangle the invariant and variant patterns and focus on invariant patterns, whose relationships to labels are invariant, to make predictions, and thus handle distribution shifts. In experiments, we empirically find that our method significantly outperforms the baselines in dynamic graph prediction tasks under distribution shifts. We will provide a more detailed explanation of the rationale behind this objective in the revised paper.\n\n> The authors are encouraged to discuss more on the two fundamental assumptions, especially for how universal these assumptions can be and what if they are violated in real data.\n\nThank you for highlighting this point. We acknowledge that we follow the invariant learning literature to adopt the assumptions of invariant patterns, and they are common on dynamic graphs. For example, on e-commerce networks, some low-frequency interactions may represent the user's long-term interest, while some high-frequency interactions may result from promotions. For another example, in the stock market, some low-frequency bandwidths may represent the value of the stock, while some high-frequency bandwidths may reflect noises that are not beneficial for investment. Although real-world data can be complex and noisy, making it challenging to strictly disentangle invariant and variant patterns, extensive experiments on real-world dynamic graphs empirically show that our method can better handle distribution shifts on dynamic graphs than the baselines. We will add the discussion in the revised paper.\n\n> The proposed model is heavily based on the invariant learning framework on graph data, and the originality concerning the distribution shifts seems limited. The novel part from the frequency modeling can be an orthogonal technique that is also applicable for other problems beyond the out-of-distribution generalization, and the authors fail to argue the advantage and uniqueness of the frequency modeling w.r.t. the temporal OOD problem. \n\nWe appreciate your perspective on the proposed model. To the best of our knowledge, this paper is the first to study distribution shifts on dynamic graphs in the spectral domain, and in section 3, we give a motivation example with theoretical analysis to bridge the relationship between the invariant/variant patterns in the spectral domain and OOD generalization. This frequency modeling on dynamic graph OOD generalization is unique, providing another spectral analytical perspective besides the temporal view in the literature, and tells us the advantage of achieving dynamic graph OOD generalization in the spectral domain. Based on these analyses, we design a DyGNN with Fourier transform to obtain the node spectrums, a disentangled spectrum mask to obtain invariant and variant spectrum masks in the spectral domain, and propose the invariant spectral filtering mechanism to handle distribution shifts. Extensive experiments also empirically verify the effectiveness of our method. Nevertheless, we agree that our method can be extended to other problems beyond OOD generalization in future works.\n\n> More comparisons with some static baselines, e.g., GCN, GraphSAGE, EERM and DIR.\n\nThank you for your suggestion. Following your suggestion, we provide comparisons with more static baselines on the dynamic link prediction datasets collab and yelp. We merge the graph snapshots to a static graph as inputs to the baselines. The results are shown in the following table, where OOM denotes out-of-memory on NVIDIA 3090 with 24GB GPU memory.\n\n| Model | Collab | Yelp |\n|:---:|:---:|:---:|\n| GCN | 76.17+-0.31 | 65.43+-1.07 |\n| GraphSAGE | 59.93+-0.09 | 62.61+-0.08 |\n| GAT | 69.43+-0.26 | 61.66+-0.03 |\n| GCRN | 69.72+-0.45 |  54.68+-7.59 |\n| EGCN |  76.15+-0.91 |  53.82+-2.06 |\n| DySAT |  76.59+-0.20 |  66.09+-1.42 |\n| IRM |  75.42+-0.87 |  56.02+-16.08 |\n| VREx |  76.24+-0.77 |  66.41+-1.87 |\n| GroupDRO |  76.33+-0.29 |  66.97+-0.61 |\n| DIR | 77.01+-0.16 | 67.21+-0.52 |\n| EERM | OOM | 65.55+-2.13 |\n| DIDA |   81.87+-0.40 |   75.92+-0.90 |\n| Ours |   84.09+-0.16 |   78.65+-2.22 |\n\nAs shown in the table above, although EERM and DIR have shown competitive performance in static graph OOD settings, they have limited improvements over static GNNs in dynamic link prediction, which may be due to their ignorance of tackling the time information that is essential in dynamic graphs. In contrast, our method has significant performance improvements over the baselines, which verifies the effectiveness of our method in handling distribution shifts on dynamic graphs. We appreciate your suggestion and will include the additional comparisons in the revised paper."}]

Author rebuttal:

Meta-review: This paper provides a new algorithm to learn dynamic graph neural networks which decomposes features into variant and invariant ones on the *frequency* domain. By doing so, it is claimed that the proposed model can outperform existing methods especially in OOD settings.   
The proposed idea is very simple extension from the exiting DIDA to a frequency domain while DIDA deals with the time domain. The proposed method is supported by some theoretical explanation and numerical experiments. In particular, the numerical experiments show effectiveness of the proposed method.  
Although there are some confusing description and the novelty of the method is rather limited given DIDA, I personally think this paper provides a practically useful method in the line of research. I hence recommend acceptance.   

However, some notations are not clearly defined and learning procedure can be described in a clearer way. I strongly encourage the author to fix them.
Decision: Accept (poster)