Deep Temporal Graph Clustering
Authors: Meng Liu
Yue Liu
KE LIANG
Wenxuan Tu
Siwei Wang
sihang zhou
Xinwang Liu
Venue: ICLR 2024 poster (2024)
Keywords: Clustering
Graph Learning
Temporal Graph
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: We present the first general framework TGC for deep temporal graph clustering and discuss the differences between temporal graph clustering and existing graph clustering from multi-levels.

Abstract: Deep graph clustering has recently received significant attention due to its ability to enhance the representation learning capabilities of models in unsupervised scenarios. Nevertheless, deep clustering for temporal graphs, which could capture crucial dynamic interaction information, has not been fully explored. It means that in many clustering-oriented real-world scenarios, temporal graphs can only be processed as static graphs. This not only causes the loss of dynamic information but also triggers huge computational consumption. To solve the problem, we propose a general framework for deep Temporal Graph Clustering called TGC, which introduces deep clustering techniques to suit the interaction sequence-based batch-processing pattern of temporal graphs. In addition, we discuss differences between temporal graph clustering and static graph clustering from several levels. To verify the superiority of the proposed framework TGC, we conduct extensive experiments. The experimental results show that temporal graph clustering enables more flexibility in finding a balance between time and space requirements, and our framework can effectively improve the performance of existing temporal graph learning methods. The code is released: https://github.com/MGitHubL/Deep-Temporal-Graph-Clustering.

Published as a conference paper at ICLR 2024
DEEP TEMPORAL GRAPH CLUSTERING
Meng Liu' Siwei Wang*
Yue Liu'
Ke Liang' Wenxuan Tu'
Sihang Zhou' Xinwang Liu'
National University of Defense Technology, Changsha, China Inteelligent Game and Decision Lab, Beijing, China mengliuedue 63. com, xinwangl nudt. edu.cn
ABSTRACT
Deep graph clustering has recently received significant attention due to its ability to enhance the representation learning capabilities of models in unsupervised scenarios. Nevertheless, deep clustering for temporal graphs, which could capture crucial dynamic interaction information, has not been fully explored. It means that in many clustering-oriente oriented real-world scenarios, temporal graphs can only be processed as static graphs. This not only causes the loss of dynamic information but also triggers huge computational consumption. To solve the problem, we propose a general framework for deep Temporal Graph Clustering called TGC, which introduces deep clustering techniques to suit the interaction sequence-based aatch-processing pattern of temporal graphs. In addition, we discuss differences between temporal graph clustering and static graph clustering from several levels. To verify the superiority of the proposed framework TGC, we conduct extensive experiments. The experimental results show that temporal graph clustering enables more flexibility finding a balance between time and space requirements, and our framework effectively improve the performance of existing temporal graph lcarning methods. The code is released: Itttps:// //gttubb. com Motn///ittbbL//// Deep Teep-Tenppral-Graphh ChwphhCCuuutrnnnnnn
INTRODUCTION
Graph clustering is an important part of the clustering task, which refers to clustering nodes on graphs. Graph (also called network) data is common in the real world (Cui et al. 2018 Liang et al.) 2023a Hamilton 2020), such as citation graphs, knowledge graphs, e-commerce graphs, etc. In these graphs, graph clustering techniques can be used for many applications, such game community discovery, financial anomaly detection, urban criminal prediction, social group analysis, etc.
In recent years, deep graph clustering has received significant attention due its ability to enhance the representation learning capabilities of models in unsupervised scenarios. Nevertheless, existing deep graph clustering methods mainly focus static graphs and neglect temporal graphs. Static graph clustering methods treat the graph as the fixed data structure without considering the dynamic real-world scenarios, temporal graph
changes in graph. This means that in many clustering-orient data can only be processed as static graphs. But in these scenarios, there are usually lot of dynamic events, where relationships and identities of nodes are constantly changing. Thus the neglect of time may lead to the loss of useful dynamic information.
Compared static graphs, temporal graphs enable more fine observation of node dynamic interactions. However, existing temporal graph learning methods usually focus on link prediction rather than node clustering. This because adjacency matrix- bbsed deep graph clustering modules are no longer applicable to the batch-processing pattern based on the interaction sequence in temporal graphs. Thus we ask: what makes node clustering different between temporal graphs and static graphs? We attempt to answer this from the following perspectives.
"Corresoondigg Author: Xinwang Liu.

---

Published as a conference paper at ICLR 2024
(Mijps by menory)
Unkeoeabic
Incomppien moonds
Barch
N
Click case
X
Time
Teb
Memory
0
Jer
0
Jas
Sop
5
Dec
Ful maat opaniioo
Targredl sequerics
Aepporecy
Seepannce
69 Adjarmmey montis and interaation seqareet
(b) Full mutris operation and lanth prosssing
(6) Strict chronolagial order in temporal gropht.
Figure 1: Difference between static graph and temporal graph.
(I) As shown in Fig. (a), if there several interactions between two nodes, the adjacency matrix can hardly reflect the dynamic changes, especially when these interactions belong to different timestamps. In contrast, temporal graphs utilize the interaction sequence (i.e., adjacency list) to store interactions. The existence of multiple interactions between nodes can be clearly represented by interaction sequence of the temporal graph, but it will be compressed into two forms of 0 or in the adjacency matrix, i.c., it results in the absence of edges. This problem brings about a serious lack of information when there are frequent interactions between pairs of nodes.
(2) Further, we can find in Fig. (b), static graph methods usually train the whole adjacency matrix, which is not convenient enough for large-scale graphs (i.c., possible out-of -itmoorymooyy problem). By slicing the interaction sequence into multiple batches, temporal methods are naturally suitable for large-scale data processing (i.e., batch size can adjust by memory). And it also means that temporal methods can no longer take advantage of the node clustering modules based on the adjacency matrix.
(3) Although there are a few static methods that split graph data into multiple sub-grapha to solve the out-of- out-of-menne memory problems, this still differs from temporal methods. The most important issue is that the loading of temporal graphs must strictly follow the chronological order, i.e., the earlier nodes cannot "see" the later nodes, shown in Fig. (c). Suppose there is an interaction between two nodes in a subgraph occurs in 2023, while an interaction between a subgraph and another subgraph occurs in 2020. So how do we reverse time the information from 2023 and pass it on in 2020? Therefore, we believe that our framework is a more appropriate solution in the field of temporal graphs. In this case, the temporal relationship of node interactions should still be taken into account during training.
Due these discrepancies, the difficulty of temporal graph clustering find the balance between interaction sequence-based batch-processing patterns and adjacency matrix-based node clustering modules. Nowadays, few works discuss it comprehensively. Although few methods refer to temporal graph clustering, they are incomplete and we discuss them in the Appendix.
Driven by this, we propose general framework for Temporal Graph Clustering, called TGC. Such framework proposes two deep clustering modules (node assignment distribution and graph reconstruction) to suit the batch- secc-ppocessiig pattern of temporal graphs. In addition, we discuss temporal graph clustering at several levels, including intuition, complexity, data, and experiment. To verify the superiority of the proposed framework TGC on unsupervised temporal graph representation learning, we conduct extensive experiments. The experimental results show that temporal graph clustering enables more flcxibility in finding a balance between time and space requirements, and our framework can effectively improve the performance of existing temporal graph learning methods. In summary, our contributions are several-fold:
Problem. We discuss the differences between temporal graph clustering and static graph clustering. To the best of our knowledge, our work is the first to comprehensively focus on deep temporal graph clustering.
Algorithm. A simple general framework TGC is proposed, which introduces two deep clustering modules to suit the interaction sequence- based batch-processing pattern of temporal graphs.
Dataset. We discuss another issue that hinders the development of temporal graph clustering, namely the lack of datasets, and collate or develop several effective datasets.
Evaluation. We conduct several experiments to validate the clustering performance, flexibility, and transferability of TGC, and further elucidate the characteristics of temporal graph clustering.
2

---

Published as a conference paper at ICLR 2024
2 METHOD
In this section, we first give the definitions of temporal graph clustering, and then describe the proposed framework TGC. Our framework contains two modules: temporal module for time information mining, and a clustering module for node clustering. Here we introduce the classical HTNE (Zuo al. 2018) method as the baseline of temporal loss, and further discuss the transferability of TGC on other methods in the experiments. For the clustering loss, we improve two node clustering technologies to fit temporal graphs, i.e., node-level distribution and batch-level reconstruction.
2.1 PROBLEM DEFINITION
If a graph contains timestamp records between node interactions, we call it temporal graph. Definition Temporal graph. Given a temporal graph = (V, T,), where denotes nodes and E denotes interactions. In temporal graphs, the concept of edges is replaced by interactions. Because although there is only one edge between two nodes, there may be multiple interactions that occur at different times. Multiple interactions between {(x, y, (1), (I, y, 122..... ... (I, y: (n)). If two nodes interact with each other, we call them neighbors. When node's 's neighbors are sorted by interaction time, its historical neighbor sequence can be formulated as: N₂ = {(11.t)) (y2, t2), (y1,t)}
nodes can be formulated as: Ta.y
Temporal graph clustering aims to group nodes into different clusters on temporal graphs.
Definition 2. Temporal graph clustering. Node clustering in the graph follows some rules: (1) nodes in a cluster are densely connected. and (2) nodes in different clusters are sparsely connected.
Here define K clusters to divide all nodes, i.e., C {e1, C2...., CK) ). Node embeddings are continuously optimized during training and then fed into the K-means algorithm for performance evaluation during testing.
2.2 BASELINE TEMPORAL. AL. LOSS
How to capture the dynamic information is the most important problem in temporal graphs. As classical method, HTNE (Zuo al., 2018) introduces the Hawkes process (Hawkes) 1971) to capture the dynamic information in graph evolution. Such a process argues that node future interaction are influenced by historical interactions and this influence decays over time. Given two nodes and y interact at time their conditional interaction intensity ((x,y.)) can be formulated follows.
(xx.g11) P(z.v.)) ((x,))))
According to Eq. [ the conditional intensity can be divided into two parts: (1) the base intensity between two nodes without any external influences, i.e., ((ex..)) =1 =2/12, where 2 is the node embedding of x at time 1, and (2) the hawkes intensity ((ax,,)) from historical interaction influences, which is weighted by node similarity in addition decaying over time.
Σ ((6....0) (66.)))) ((..,111) = ((1x) . f(e 4) VEN.
Here, (K..)) is the node similarity weight to evaluate a neighbor's importance in all neighbors. f(te - t.) denotes the influences from neighbors decay with time, and the earlier the time, the less the influence. ó, is a learnable parameter, te denotes the current timestamp.
exp(H(()) (1,x)) EVEN, (x)()().)))
f(. 4)) exp( 5,, 1,)
Finally, given two nodes x and interact at time I, their conditional intensity should be as large as possible, and the intensity of node x with any other node should be as small as possible. Since requires large amount of computation to calculate the intensities of all nodes, we introduce the negative sampling technology (Mikolov et al.] 2013), which samples several unrelated nodes as negative samples. Thus the baseline temporal loss function be calculated as follows, where P(x) is the negative sampling distribution that is positively correlated with the degree of node x.
Ttem= = - log a (AA(..)))))
Σ n(P(
log (1- A(a,n,t))
(4)
3

---

Published as a conference paper at ICLR 2024
For the above temporal information modeling, introduce a classic HTNE method as the baseline without any additional changes. But the use time alone is not enough to improve the performance of temporal graph clustering, so propose clustering loss to compensate for this.
2.3 IMPROVED CLUSTERING LOSS
Compared with static graph clustering, temporal graph clustering faces the challenge that deep clustering modules based static adjacency matrix are longer applicable. Since temporal graph methods train data in batches, we propose two new batch-based modules for node clustering, i.e., node-level distribution and batch-level reconstruction.
2.3.1 NODE-LEVEL DISTRIBUTION
In this module, we focus on assigning all nodes to different clusters. Especially, for each node æ and each cluster C₁. we utilize the Student's t-distribution (Van der Maaten Hinton 2008) their similarity.
measure
(1 + 22 z 11//1) - ((z,k.1) Ec,Ec(1 ||= 2/ 112/0))
(5)
Here ((r,k,t) denotes the probability of assigning node cluster Ck. and is the degrees of freedom (default value is 1) for Student's t-distribution (Bo et al. 2020). 20 denotes the initial feature of node I, zi, is one clustering center embedding initialized by K-means on initial node features.
Considering that ((...))) and = need to be as reliable as possible, and not all temporal graph datasets provide original features to ensure such reliability. We select the classical method node2vec (Grover & Leekkveec 2016) to generate initial features for nodes by mining the graph structure, which is equivalent the pre-training. Note that many graph clustering methods use classical model pre-train to generate initialized clustering centers, such as SDCN (Bo et al. 2000)) utilizes AE, DFCN (Tu et al., 2021) and DCRN (Liu et al.) 2022a) utilize GAE, etc. Our selection of node2vec is not deliberate, and can be replaced by any other methods.
After calculating the initial probability, we aim to optimize the node embeddings by learning from the high-confidence assignments. In particular, we encourage all nodes to get closer to cluster centers, thus the target distribution P(a,,k))) at time can be sharpened as follows.
Ro..tt)/ ΣiEV ((,k.))
P(a,k.)) Eo EiEv 1(3..)))
The target distribution squares and normalizes each node-cluster pair in the assignment distribution to encourage the assignments to have higher confidence, then we can consider as the "correct" distribution. We introduce the KL divergence (Kullback & Leibler 1951) to the node-level distribution loss, where the real-time assignment distribution is aligned with the target distribution.
Σ P(z,k.)) log P(a,k,))
Imode
ELEC
Note that La,k,; is calculated from node embeddings and can change with the update of node embeddings. This loss function aims to encourage the real-time assignment distribution as close as possible to the target distribution, so that the node embeddings can be more suitable for clustering.
The calculation of the assignment distribution differs in the static and temporal graphs. In static graph clustering, all nodes are computed simultancously for the distribution. However, there is sequential order of interactions in temporal graphs, so we calculate the distribution of the nodes in each interaction by batches. Note that if node has multiple interactions, its distribution will be calculated multiple times, which we consider as multiple calibrations for important nodes.
2.3.2 BATCH-LEVEL RECONSTRUCTION
Graph reconstruction also plays an important role in node clustering, which can considered the pretext task. Due the batch training in temporal graph learning, the adjacency matrix- based reconstruction technology can hardly be applied in temporal methods. Thus we propose the batch-level module to simply simulate the adjacency relationships reconstruction.
4

---

Published as a conference paper at ICLR 2024
As mentioned above, for each batch, we calculate the temporal conditional intensity between nodes and y. To achieve that, we obtain the historical sequence N₂ of x. It means that both target node and neighbor nodes h N₂ have edges with in the graph, i... their adjacency relations are all 1. In addition, in the temporal loss function (Eq. 4). we also sample some negative nodes n ~ P(x), which have edges with in the real graph, i.e., their adjacency relations are all O.
Based on the adjacency relationships above, the embedding of these nodes should also follow this constraint. Thus we utilize the cosine similarity to measure the relationship between two node embeddings and constrain them as close to or 0 as possible. The cosine similarity between two
node embeddings can be calculated as cos [2x, mny | |
This pseudo-reconstruction operation on batches, while not fully restoring the adjacency matrix reconstruction, uses many nodes as possible that appear in the batch. It is equivalent simple reconstruction of the adjacency matrix without increasing the time complexity, which may provide a new idea for the problem that there is no adjacency matrix in batch processing of temporal graphs. Finally, the bateh-level loss function can be formulated as follows.
Lbatch = | - cos( ( 21)o + - cos 2111 + 10 cos(z (2)) 2/,1
(8)
Thus the improved clustering loss function can be formulated as Latu- = Lindd + Lhatch-
2.4 LOss FUNCTION AND COMPLEXITY ANALYSIS
Our total loss function includes temporal loss and clustering loss, which can be formulated as L= = (Ltem + Lefu). Note that the temporal graph is trained in batches, and this division of batches is not related to the number of nodes N, but to the length of the interaction sequence |F] (i.e., the total number of interactions). This means that the main complexity of the method for temporal graph clustering is O [)), rather than ((22) for static graph clustering because the temporal graph method does not need to call the whole adjacency matrix. other words, compared to static clustering, temporal clustering has the advantage of being more flexible and convenient for training:
(1) In the vast majority of cases, EE| is smaller than N2 because the upper bound of |E| is N (when the graph is fully connected), which means that O(E)) < O(N3) in most time.
(2) In individual cases, there is a case where O(EE) > O(N3). which means that there are multiple interactions between large number of node pairs. This underscores the superiority of dynamic interaction sequences over adjacency matrix, as the latter compresses multiple interactions into a single edge, leading to a significant loss of information.
(3) The above discussion applies not only to the time complexity but also to the space complexity. As the interaction sequence is arranged chronologically, it can be partitioned into multiple batches of varying sizes. The maximum batch size is primarily determined by the available memory of the deployed platform and can be dynamically adjusted to match the memory constraints. Therefore. TGC can be deployed on many platforms without strict memory requirements.
The different types of datasets mentioned above are all considered in our experiments, which have very different node degrees and sizes. Then, We conduct experiments and discussions around these datasets from multiple domains.
DATASETS
factor limiting the development of temporal graph clustering is that it is difficult to find a dataset suitable for clustering. Although node clustering is an unsupervised task, we need to use node labels when verifying the experimental results. Most public temporal graph datasets suffer from the following problems: (1) Researchers mainly focus on link prediction without node labels. Thus many public datasets have no labels (such as Ubuntu, Math, Email, and Cloud). (2) Some datasets have only two labels (0 and I), i.e., models on these datasets aim to predict whether node is active at certain timestamp. Node classification tasks on these datasets tend to be more binary-classification than calltiicasssfiiaaiion thus these datasets are also not suitable for clustering tasks (such Wiki, CollegeMsg, and Reddit). (3) Some datasets' labels do not match their own characteristics, e.g.. different ratings of products by users be considered labels, but it is difficult to say that these
5

---

Published as a conference paper at ICLR 2024
Table 1: Dataset statistics.
Datasets
Nodes
Interactions
Edgas
Complexity
Timestamps
K
Degrec
Minl
Maxl
DBLP
28,085
236,894
162.441
N2 te E
27
10
16.87
955
Brain
5,000
1,955,488
1,751,910
X2 >
12
10
782
484
1,456
Patent
12,214
41,916
41,915
N2 to E
891
6.86
789
School
327
188,500
5,802
N7 <
7,375
9
1153
7
4,647
arXivA1
69.854
699,206
NV
27
11,594
arXivCS
169,343
1,166,243
1,166,237
N3 35
29
40
13.77
13,161
labels are more relevant to the product characteristics than the product category labels, thus leading to the poor performance of all methods these datasets (such as Bitcoin, MIIM, Yelp, and Amazon).
Constrained by these problems, as shown in Table 1 we select these suitable datasets from 40+ datasets: DBLP (Zuo et al. 2018) is a co-author graph from the DBLP website, which contains 10 research areas, i.e., 10 clusters. Each researcher is considered a node, and the collaborative relationships between them are considered interactions. Brain (Preti et al. 2017) is human brain tissue connectivity graph, where the nodes represent tidy cubes of brain tissue, and the edges indicate connectivity. Patent (Hall et al. 2001) is patent citation graph of US patents. Each patent belongs to six different types of patent categories. School (Mastrandrea et al. (015)) is a high school dataset that records the contact and friendship between school students. Although the number of students is small, they have many interactions throughout the day.
ArXivAl and XSXIvSS (Wang et al. 2020) are two public citation graphs from the arXiv website, where papers are nodes, and citations are interactions. Note that these two datasets are developed by us large-scale temporal graph clustering, which record the academic citations on the arxiv website. Their original data are from the OGB benchmark (Wang et al.] (020), but are not applicable to temporal graph clustering. We extracted reference records from the original data to construct node interactions with timestamps and then find the corresponding node ids to construct the interaction sequence-style temporal graph.
To generate node labels suitable for clustering, we select the domain to which the paper belongs as its node label. Specifically, the arXiv website categorizes computer domains into 40 categories. We first identify the domains that correspond to the nodes, and then convert them into node labels. On the basis of arXivCS, we also construct the arXivAl dataset by extracting Top-5 relevant domains to AI from the original 40 domains and used them as the basis extract the corresponding nodes and interactions.
In Table I Nodes denotes the node number, and Interactions denotes the interaction number. Note that we also report Edges, which represents the edge number the adjacency matrix when we compress temporal graphs into static graphs for traditional graph clustering methods (As mentioned in Fig. I some duplicate interactions are missing). Complexity denotes the main complexity comparison between static graph clustering and temporal graph clustering, Timestamps means interaction time, K means the number of clusters (label categories), and Degree means node average degree. Minl and Maxl denote the maximum and minimum interaction times of nodes, respectively.
EXPERIMENTS
In this part, discuss the experiment results. Due to the limitation of space, we present some of the descriptions and experiments in the appendix. Here we ask several important questions about the experiment: Q1: What are the advantages of TGC? Q2: the memory requirement for TGC really lower? Q3: Is TGC valid for existing temporal graph learning methods? Q4: What restricts the development of temporal graph clustering?
4.1 BASELINES
To demonstrate the performance of TGC, we compare it with multiple state-of-the-an methods as baselines. In particular, we divide these methods into three categories: Classic methods refer to some early and highly influential methods, such as DeepWalk (Perozzi et al., 20144, AE (Hinton Salakhutdinov 2006). node2vec (Grover & Leskovec 2016). GAE (Kipf & Welling 2016). etc. Deep graph clustering methods refer to some methods that focus on clustering nodes static graphs, such as MVGRL (Hassani & Khasahmadi 2020), AGE (Cui et al. 2020). DAEGC (Wang
et al. 2019), SDCN and SDCNQ (Bo et al. 2020). DFCN (Tu et al. 2021
etc. Temporal graph

---

Published as a conference paper at ICLR 2024
Table 2: Node clustering results in common datasets. We bold the best results and underline the
second best results. a method face the out- ofmooo problem, we record as OOM.
Datu
Matric
despwoik
AE
GAE
MVCRL
ACIE
DAECC
SDCN
SDCNQ
DECN
HTNE
TOAT
JODIE
TGN
TREND
TGC
ACC
45.00
42.16
46.31
39.31
28,55
00M
00M
46.69
20.47
41.97
45.74
36.76
20.79
19.73
66.52
45.75
DBLP
NMI
17.89
34.87
17:87
00M
00M
33.74
15.07
21.45
36.94
22.05
38.95
1.70
38.50
35.00
40.31
13.23
ACC
41.28
43.45
43.92
$1.22
15.76
38.45
42.52
42.62
03.42
47.46
43.20
41.43
19:14
17.40
39.85
64.30
Brain
NMI
ARI
28.40
49.09
50,59
20.78
26.05
45.96
12.33
14.97
21.15
9.77
28.52
39.54
27.47
45.56
46.61
27.93
27.59
17:40
28.58
45.53
29.26
50.33
48.72
23.64
10.50
5.00
4.56
5,04
22.52
05.04
59,68
30,03
F1
42.54
$3.26
45.61
34:11
13.56
36,47
43.24
41.42
31.27
50.45
63.85
41.13
11:12
13.49
33.67
64.42
96.00
50.65
$7.95
99.25
90.83
Patent
NMI
ARI
22.71
10:32
24.84
18.95
13:11
17.75
19.35
21.28
13:17
10:12
12.24
10.69
19:74
13:31
9.55
7.45
6,01
13.45
25.04
F1
31.45
26.65
34.97
30.95
18.06
35.45
32.83
31.38
28.27
30.32
28.85
26.97
20.83
21.46
25.41
38,69
ADC
91.56
65.62
94.25
48:33 13
49.85
30.54
19.83
School
NMI
ART
02.63
83.09
70.24
K1.51
15.38
33:81
53.35
28.31
96.75
9004
73.25
285
9.26
F1
52.67
91.74
$2.60
45.03
47.05
79.56
13,00
Table 3: Node clustering results in large-scale datasets. We bold the best results and underline the
second best results. If a method face the out-of out-of-memory memory problem, we record as OOM.
Dota
deepwalk
aidd2ies
GAE
MVGRL
AGB
SUCN
SDCNG
DFCN
HINE
JODIE
TREND
ACC
60.91
23.85
65.01
38,72
00M
00M
0.M
44.44
37.62
0OM
65.66
48.69
30.71
31.25
29.82
73,59
4rXIVAL
XMI
ARI
34.34
16.08
10.20
14.00
36.18
40:35
32.54
12.98
00M
00M
00M
00M
00M
00M
2343
21.63
21:28
20.73
00M
00M
39.24
45.73
32.12
90.34
2.91
5.35
24.74
11:91
1.25
1.12
42,66
48.16
F1
49.47
19:20
53.65
16.97
00M
00M
00M
33.96
31.02
00M
52.85
43.62
25.24
21.53
19.22
$7.86
ACC
34.42
34.20
27.39
00M
00M
29.78
27.05
00M
25.57
11.27
20.10
39.95
NMI
10185
14.01
41.18
00M
00M
00M
00M
13.27
11.59
00M
40.83
18.64
5.12
16.31
5.57
43.80
ARI
24.65
11 108
19.34
00M
00M
00M
00M
14.30
13.00
00M
15.51
15.54
5.31
18.6%
3.49
36.06
F3
20.39
12:35
21.41
00M
00M
00M
00M
14.08
13.28
00M
19.56
13.25
4.85
22,67
4.02
25.46
learning methods refer to some methods that model temporal graphs without node clustering task, such as HTNE (Zuo et al. 2018). TGAT (Xu et al. (020), JODIE (Kumar et al. 2019). TGN (Rossi TREND (Wen & Fang 2022), etc.
et al. 2020).
4.2
NODE CLUSTERING PERFORMANCE
What the advantages of TGC? Answer: TGC is more adapted to high overlapping graphs and large-scale graphs. As shown in Table 2 and 3 we can observe that:
Q1:
(1) Although TGC may not perform optimally on all datasets, the aggregate results are leading. Especially on large-scale datasets, many static clustering methods face the out-of-memory (OOM) problem GPU (we use NVIDIA RTX 3070 Ti), only SDCN benefits from a simpler architecture and can run on the CPU (not GPU). This is due to the overflow of adjacency matrix computation caused by the excessive number of nodes, and of course, the problem can be avoided by cutting subgraphs. Nevertheless, we also wish to point out that by training the graph in batches, temporal graph learning can naturally avoid the OOM problem. This in turn implies that temporal graph clustering is more flexible than static graph clustering on large-scale temporal graph datasets.
(2) The performance varies between different datasets, which we believe is due to the datasets belonging to different fields. For example, the arXivCS dataset has 40 domains and some of which overlap, thus is difficult to say that each category is distinctly different, so the performance is relatively low. On the contrary, node labels of the School dataset come from the class and gender that students are divided into. Students in the same class or sex often interact more frequently, which enables most methods to distinguish them clearly. Note that the School dataset, almost all temporal methods achieve better performance than static methods. This echoes the complexity problem we analyzed above, as the only dataset where N < E, the dataset loses the vast majority of edges when we transfer it to the adjacency matrix, thus static methods face a large loss of valid information.
(3) The slightly poor performance of temporal graph learning methods compared deep graph clustering methods supports our claim that current temporal graph methods do not yet focus deeply on the clustering task. In addition, after considering the clustering task, TGC surpasses the static graph clustering method, also indicating that time information is indeed important and effective in the temporal graph clustering task. Note that these temporal methods achieve different results due to different settings, but we consider our TGC framework can effectively help them improve the clustering performance. Next, we will discuss TGC's memory usage and transferability.
4.3
GPU MEMORY USAGE STUDY
7

---

Published as a conference paper at ICLR 2024
Q2: Is the memory requirement for TGC really lower? Answer: Compared to static graph clustering methods, TGC significantly reduces memory requirements.
TGC
XVGAL
JomE
Memory (G2)
TREND
DPCN
We first compare the memory usage of static clustering methods and TGC on different datasets, which we sort by the number of nodes. As shown in Fig. 2 we report their max memory usage. As the node number increases, the memory usages of static meth- ods become larger and larger, and eventually Figure 2: Memory changes between different datasets. out-of-memory problem occurs.
School
Paien: 12,214
DBLP 28,085
xx 69,854
arXivCS
327
5,000
169,349
At the same time, the memory usage of TGC also gradually increasing, but the magnitude small and it is still far from the OOM problem. As mentioned above, the main complexity O(EE)) of temporal methods is usually smaller than (NN)) of static methods. To name a few, for the arXivCS dataset with large number of nodes and interactions, the memory usage of TGC is only 212.77 MB, while the memory usage of SDCN, the only one without OOM problem, is 6946.73 MB. For the Brain dataset with small number of nodes and large number of interactions, the memory usage of TGC (121.35 MB) is still smaller than SDCN (626.20 MB). We consider that for large-scale temporal graphs, TGC can be less concerned with memory usage, and thus can be deployed more flexibly to different platforms.
We further verify that TGC can flexibly adjust the batch size according the memory. As can see in Fig. 3 the runtime and memory footprint are basically inversely proportional on different timing diagram methods. This can also prove our conclusion that temporal graph clustering is able to find a balance between space requirements and time requirements. The only problem that occurs is the running time of TREND when the batch size is 10000, which increases rather than decreases. This because the TREND model is designed to search for higher-order neighbors, process that is done by the CPU. When the batch larger, the number of nodes that have to wait for the CPU search result is also larger. Therefore, the increase in TREND's 's runtime large batches is actually due to the increased computation by the CPU, rather than the GPU problem we usually consider. It also reflects the fact that TGC is flexible enough to find balance between time consumption and space consumption according to actual requirements, either time for space or space for time is feasible.
4.4 TRANSFERABILITY AND LIMITATION DISCUSSION
Q3: Is TGC valid for existing temporal graph learning methods? Answer: TGC is a simple general framework that can improve the clustering performance of existing temporal graph learning methods.
As shown in Fig. 4 in addition to the baseline HTNE, we also add the TGC framework to TGN and TREND for comparison. Although TGC improves these methods differently, basically they are effective in improving their clustering performance. This means that TGC is a general framework that can be easily applied to different temporal graph methods.
We also want to ask Q4: What restricts the development of temporal graph clustering? Answer: (1) Few available datasets and (2) information loss without adjacency matrix.
On the one hand, mentioned above, there are few available public datasets for temporal graph clustering. We collate lot of raw data and transform them into temporal graphs, and we also discard many of them with low label confidence incomplete labels. On the other hand, some global information is inevitably lost without adjacency matrix. Since temporal graph clustering is a novel task, there is still lot of room for expansion of TGC. For example, how to further optimize module migration without adjacency matrix and how to adapt to the incomplete label problem in some graphs.
These issues limit the efficiency and performance of temporal graph clustering, and further exploration is required. In conclusion, although the development of temporal graph clustering is only in its infancy, cannot ignore its possibility new solution.
8

---

Published as a conference paper at ICLR 2024
2000
Egods mantinn inii
Menuay (M00)
CPP XaB
Booch cuniise
1500
020
1000-
300
16
12x
1164
26
124
1004
10N00
125
2004
10000
(a) TGC
(b)
TGN
(c) TREND
Figure Changes in memory and runtime under different batch sizes.
301
6) Ard T00 DALP
06 AATA0C w0TON Bece
63 A.AATTOO TRUND DREP
90 AAFTOC TREND Paice
Figure 4: Transferability of TGC on different temporal graph methods.
Due to space constraints, we also present some of the content the Appendix, which includes the Related Work section and more experiment details (i.e., experimental settings, ablation study, and parameter sensitivity study).
DISCUSSION
Here we make summary statement in an attempt to bring out focus of paper:
(1) The main contribution of this paper is not only to present generalized framework, but also to attempt to introduce and explain the direction temporal graph clustering in several ways (intuition, method, data, experiment, etc.).
(2) We focus on temporal graph clustering because offers a new possibility clustering based on interaction sequences (adjacency lists) compared to clustering based adjacency matrices in discrete dynamic or static graphs. Here, we group discrete dynamic and static graphs together because they both require the entire adjacency matrix to be read for training, which can pose serious memory overflow problem.
(3) Interaction sequence- peaeenee-based temporal graph clustering does not suffer from memory overflow because it switches to batch processing model. By feeding the interaction records nodes into the model in batches, it is possible to modify the batch size avoid exceeding the memory. We therefore point out that temporal graph clustering is able to flexibly find a balance between temporal and spatial demands, which certainly provides new ideas for current graph clustering models.
(4) Thus, what we want to show is not that temporal graph clustering performs better compared other methods, but that it offers new horizons. Under this premise, even if there is gap the performance of temporal graph clustering compared to other methods, it does not detract from the benefits of its flexibility.
CONCLUSION
In this paper, we propose a general framework TGC for temporal graph clustering, which adapt clustering techniques to the interaction sequence-based batch-processing pattern of temporal graphs. To introduce temporal graph clustering as comprehensively as possible, we discuss the differences between temporal graph clustering and existing static graph clustering at several levels, including intuition, complexity, data, and experiments. Combining experiment results, we demonstrate the effectiveness of our TGC framework existing temporal graph learning methods, and point out that temporal graph clustering enables more flexibility in finding a balance between time and space requirements. In the future, will further focus large-scale and K-free temporal graph clustering.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work was supported by the National Natural Science Foundation of China (Project No. 62325604, 62276271).
REFERENCES
Deyu Bo, Xiao Wang, Chuan Shi, Meiqi Zhu, Emiao Lu, and Peng Cui. Structural deep clustering network. In Proceedings of the web conference 2020, pp. 1400-1410, 2020.
Zhan Bu, Hui-Jia Li, Jie Cao, Zhen Wang, and Guangliang Gao. Dynamic cluster formation game for attributed graph clustering. IEEE transactions cybernetics, 49(1))328 2017.
Shaosheng Cao, Wei Lu, and Qiongkai Xu. Deep neural networks for learning graph representations. In Proceedings of the AAAI conference on artificial intelligence, 2016.
Ganqu Cui, Jie Zhou, Cheng Yang, and Zhiyuan Liu. Adaptive graph encoder for attributed graph embedding. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 976-985, 2020.
Peng Cui, Xiao Wang, Jian Pei, and Wenwu Zhu. A survey on network embedding. IEEE transactions on knowledge and data engineering. 31(5):833 852, 2018.
Zeyu Cui, Zekun Li, Shu Wu, Xiaoyu Zhang, Qiang Liu, Liang Wang, and Mengmeng Ai. Dygen: Dynamic graph embedding with graph convolutional network. arXiv preprint arXiv:2104.02962 2021.
Lun Du, Yun Wang, Guojie Song, Zhicong Lu, and Junshan Wang. Dynamic network embedding: An extended approach for skip-gram based network embedding. In IJCAI, volume 2018, pp. 2086-2092, 2018
Jianfei Gao and Bruno Ribeiro. On the equivalence between temporal and static graph representations for observational predictions. arXiv preprint arXiv:2 103.0000,, 2021.
Robert Gorke, Tanja Hartmann, and Dorothea Wagner. Dynamic graph clustering using minimum-ou trees. In Algorithms and Data Structures: 1 11th International Symposium, WADS 2009, Banff. Canada, August 21-23, 2009, Proceedings 11, pp. 339-350. Springer, 2009.
Robert Gorke, Pascal Maillard, Andrea Schumm, Christian Staudt, and Dorothea Wagner. Dynamic graph clustering combining modularity and smoothness. Journal of Experimental Algorithmics (JEA), 18:1-1, 2013.
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.
Bronwyn H Hall, Adam B Jaffe, and Manuel Trajtenberg. The nber patent citation data file: Lessons, insights and methodological tools, 2001.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
William Hamilton. Graph representation learning. Synthesis Lectures on Artifical Intelligence and Machine Learning, 1455), 2020.
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In International conference on machine learning, pp. 4116-4126. PMLR, 2020.
Alan G Hawkes. Point spectra of some mutually exciting point processes. Journal of the Royal Statistical Society: Series B (Methodological), 33(33):48-444) 1971.
Dongxiao He, Tao Wang, Lu Zhai, Di Jin, Liang Yang, Yuxiao Huang, Zhiyong Feng, and Philip Yu. Adversarial representation mechanism learning for network embedding. JEEE Transactions on Knowledge and Data Engineering, 2021.
10

---

Published as a conference paper at ICLR 2024
Geoffrey E Hinton and Ruslan R Salakhutdinov. Reducing the dimensionality of data with neural networks. science, 313(5786):504-007, 2006.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. In Advances in neural information processing systems, 2016.
Solomon Kullback and Richard A Leibler. On information and sufficiency. The annals of mathemati- cal statistics, 22(1):79-86, 1951.
Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in temporal interaction networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1269-1276 2019.
Kuan Li, Yang Liu, Xiang Ao, and Qing He. Revisiting graph adversarial attack and defense from a data distribution perspective. In The Eleventh International Conference Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023, 2023.
Tianpeng Li, Wenjun Wang, Pengfei Jiao, Yinghui Wang, Ruomeng Ding, Huaming Wu, Lin Pan, and Di Jin. Exploring temporal community structure via network embedding. IEEE Transactions Cybernetics, 2022.
Ke Liang, Lingyuan Meng, Meng Liu, Yue Liu, Wenxuan Tu, Siwei Wang, Sihang Zhou, Xinwang Liu, and Fuchun Sun. A survey of knowledge graph reasoning on graph types: Static, dynamic, and multimodal. arXiv preprint orXIv:2212.05767, 2022.
Ke Liang, Yue Liu, Sihang Zhou, Wenxuan Tu, Yi Wen, Xihong Yang, Xiangjun Dong, and Xinwang Liu. Knowledge graph contrastive learning based on sllation-ymmmetricall structure. IEEE Transactions Knowledge and Data Engineering, pp. 1-12, 2023a. doi: .0.2023 3282989.
Ke Liang, Lingyuan Meng, Meng Liu, Yue Liu, Wenxuan Tu, Siwei Wang, Sihang Zhou, and Xinwang Liu. Learn from relational correlations and periodic events for temporal knowledge graph reasoning. In Proceedings of the 46th International ACM SIGIR Conference Research and Development in Information Retrieval, pp. 1559-1568, 2023b.
Yi Liang, Kaizhong Chen, Lan Yi, Xing Su, and Xiaoming Jin. Degtec: A deep graph-temporal clustering framework for data-parallel job characterization in data centers. Future Generation Computer Systems, 141:81-99 2023c.
Meng Liu and Yong Liu. Inductive representation learning in temporal networks via mining neighbor- hood and community influences. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 2202-2206 2021.
Meng Liu, Ke Liang, Dayu Hu, Hao Yu, Yue Liu, Lingyuan Meng, Wenxuan Tu, Sihang Zhou, and Xinwang Liu. Tmac: Temporal multi-modal graph learning for acoustic event classification. In Proceedings of the 31st ACM International Conference on Multimedia, pp. 3365-33744 2023a.
Meng Liu, Ke Liang, Bin Xiao, Sihang Zhou, Wenxuan Tu, Yue Liu, Xihong Yang, and Xinwang Liu. Self-supervised temporal graph learning with temporal and structural intensity alignment. arXiv preprint arXiv:2302.00440) 2023b.
Yue Liu, Wenxuan Tu, Sihang Zhou, Xinwang Liu, Linxuan Song, Xihong Yang, and En Zhu. Deep graph clustering via dual correlation reduction. In Proceedings of the AAAI Conference on Artificial Intelligence, 2022a.
Yue Liu, Jun Xia, Sihang Zhou, Siwei Wang, Xifeng Guo, Xihong Yang, Ke Liang, Wenxuan Tu, Z. Stan Li, and Xinwang Liu. A survey of deep graph clustering: Taxonomy, challenge, and application. arXiv preprint urXiv:2211.12877 2022b.
Yue Liu, Ke Liang, Jun Xia, Xihong Yang, Sihang Zhou, Meng Liu, Xinwang Liu, and Stan Z Li. Reinforcement graph clustering with unknown cluster number. In Proceedings of the 31 ACM International Conference Multimedia, pp.
2023c.
11

---

Published as a conference paper at ICLR 2024
Yuanfu Lu, Xiao Wang, Chuan Shi, Philip S Yu, and Yanfang Ye. Temporal network embedding with micro-and macro- macro-dynamics. In Proceedings of the 28th ACM international conference on information and knowledge management, pp. 469 478, 2019.
Rossana Mastrandrea, Julie Fournet, and Alain Barrat. Contact patterns in a high school: comparison between data collected using wearable sensors, contact diaries and friendship surveys. PloS one, (o9))=e0364497 2015.
Catherine Matias and Vincent Miele. Statistical clustering of temporal networks through a dynamic stochastic block model. Journal of the Royal Statistical Society Series B: Statistical Methodology, 19(4):1119 19- 1141, 2017.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg $ Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. Advances in neural information processing systems, 26, 2013.
Yujie Mo, Yuhuan Chen, Yajie Lei, Liang Peng, Xiaoshuang Shi, Changan Yuan, and Xiaofeng Zhu. Multiplex graph representation learning via dual correlation reduction. IEEE Transactions Knowledge and Data Engineering, pp. 1-14, 2023a. doi: 202.0./TTTEEE222.33226622
Yujie Mo, Yajie Lei, Jialie Shen, Xiaoshuang Shi, Heng Tao Shen, and Xiaofeng Zhu. Disentangled multiplex graph representation learning. In ICML, volume 202, pp.
2023b.
Charini Nanayakkara, Peter Christen, and Thilina Ranbaduge. Robust temporal graph clustering for group record linkage. In Advances in Knowledge Discovery and Data Mining: 23rd Pacific-Asia Conference, PAKDD 2019, Macau, China, April 14-17, 2019, Proceedings, Part I1 23, pp. 526-538. Springer, 2019.
Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, Lina Yao, and Chengqi Zhang. Adversarially regularized graph autoencoder for graph embedding. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pp.
2018.
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. In Proceedings of the AAAI conference on artificial intelligence, 2020.
Namyong Park, Ryan Rossi, Eunyee Koh, Iftikhar Ahamath Burhanuddin, Sungchul Kim, Fan Du, Nesreen Ahmed, and Christos Faloutsos. Cge: Contrastive graph clustering forcommunity detection and tracking. In Proceedings of the ACM Web Conference 2022, pp. 1115-1111 1126, 2022.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710, 2014.
Maria Giulia Preti, Thomas AW Bolton, and Dimitri Van De Ville. The dynamic functional connec- tome: State-of-the-art and perspectives. Neuroimage, 160:41-54, 2017.
Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning on dynamic graphs. arXiv preprint 1022::2000.10667 2020.
Boyu Ruan, Junhao Gan, Hao Wu, and Anthony Wirth. Dynamic structural clustering on graphs. In Proceedings of the 2021 International Conference on Management of Data, pp. 1491-1503, 2021.
Aravind Sankar, Yanhong Wu, Liang Gou, Wei Zhang, and Hao Yang. Dysat: Deep neural rep- resentation learning on dynamic graphs via self-attention networks. In Proceedings of the 13th international conference on web search and data mining, pp. 519-527, 2020.
Seyed Amjad Scyedi, Abdulrahman Lotfi, Parham Moradi, and Nooruldeen Nasih Qader. Dynamic graph-based label propagation for density peaks clustering. Expert Systems with Applications, 1 115: 314-328, 2019.
Fei Tian, Bin Gao, Qing Cui, Enhong Chen, and Tie- Yan Liu. Learning deep representations for graph clustering. In Proceedings of the AAAI Conference Artificial Intelligence, 2014. 4.
12

---

Published as a conference paper at ICLR 2024
Rakshit Trivedi, Mehrdad Farajtabar, Prasenjeet Biswal, and Hongyuan Zha. Dyrep: Learning representations over dynamic graphs. In International conference on learning representations. 2019.
Wenxuan Tu, Sihang Zhou, Xinwang Liu, Xifeng Guo, Zhiping Cai, En Zhu, and Jieren Cheng. Deep fusion clustering network. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008.
Wang, S Pan, R Hu, Long. Jiang, and Zhang. Attributed graph clustering: A deep attentional embedding approach. In International Joint Conference Artificial Intelligence. International Joint Conferences on Artificial Intelligence, 2019.
Kuansan Wang, Zhihong Shen, Chiyuan Huang, Chieh-Han Wu, Yuxiao Dong. and Anshul Kanakia. Microsoft academic graph: When experts are not enough. Quantitative Science Studies, 1(1): 396-413, 2020.
Yanbang Wang, Yen-Yu Yu Chang, Yunyu Liu, Jure Leskovec, and Pan Li. Inductive representation learning temporal networks via causal anonymous walks. arXiv preprint arXiv:2101.05974 2021.
Zhihao Wen and Yuan Fang. Trend: Temporal event and node dynamics for graph representation learning. In Proceedings of the ACM Web Conference 2022, pp. 1159-1169, 2022.
Hanrui Wu, Yuguang Yan, and Michael Kwok-Po Ng. Hypergraph collaborative network on vertices and hyperedges. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(3):2245- 3258, 2023.
Hanrui Wu, Andy Yip, Jinyi Long, Jia Zhang, and Michael K. Ng. Simplicial complex neural networks. IEEE Transactions on Puttern Analysis and Machine Intelligence, 46(1):561-575, 2024.
Jiaming Wu, Meng Liu, Jiangting Fan, Yong Liu, and Meng Han. Sagedy: A novel sampling and aggregating based representation learning approach for dynamic networks. In ICANN 2021: 30th International Conference on Artificial Neural Networks, pp. 3-15. Springer, 2021.
Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Inductive representa- tion learning on temporal graphs. In ICLR, 2020.
Dongkuan Xu, Wei Cheng, Dongsheng Luo, Xiao Liu, and Xiang Zhang. Spatio-temporal attentive mnn for node classification in temporal attributed graphs. In IJCAI, pp. 3947-3953, 2019.
Carl Yang, Mengxiong Liu, Zongyi Wang, Liyuan Liu, and Jiawei Han. Graph clustering with dynamic embedding. arXiv preprint arXiv:1712.08244) 2017.
Yuhang Yao and Carlee Joe- JongWong. Interpretable clustering dynamic graphs with recurrent graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
Jingyi You, Chenlong Hu, Hidetaka Kamigaito, Kotaro Funakoshi, and Manabu Okumura. Robust dy- namic clustering for temporal networks. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 2424-2433, 2021.
Yuan Zuo, Guannan Liu, Hao Lin, Jia Guo, Xiaoqian Hu, and Junjie Wu. Embedding temporal network via neighborhood formation. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 2857-2866, 2018
13

---

Published as a conference paper at ICLR 2024
A RELATED WORK
A.1 DEEP GRAPH CLUSTERING
Node clustering, commonly known as graph clustering, is classic and crucial unsupervised task in graph learning (Hamilton 2020 Liu et al.) 2022b). Recently, the utilization of deep learning techniques for graph clustering has emerged
research trend, resulting in the development of numerous methods (Liu et al. 2023c Li et al. 2023 Mo et al. 2023a).
For instance, GraphEncoder (Tia et al. 2014) generates non-linear embedding of the original graph through stacked autoencoders, followed by the K-means module to compute the clustering performance. DNGR (Cao et al.] 2016) extracts low-dimensional vector representation for every vertex, capturing the structural information of the graph. By utilizing an attention network to capture the importance of neighboring nodes to a target node, DAEGC (Wang et al. 2019) encodes the topological structure and node content of a graph into compact representation. ARGA (Pan et al. 2018) encodes the graph structure and node information into a concise embedding, which is then trained using decoder to reconstruct the structure. MVGRL (Hassani & Khasahmadi] 2020) is a self-supervised method that generates node representations by contrasting structural views of graphs. AGE (Cui et al., 2020) applies a Laplacian smoothing filter, carefully designed to enhance the filtered features for better node embeddings. SDCN (Bo et al., 2020) introduces a structural deep clustering network tointegrate the structural information into deep clustering. DFCN (Tu et al. 2021) utilizes two sub-networks to process augmented graphs independently. DCRN (Liu et al. 2022a proposes a dual correlation reduction module to reduce information correlation in a dual manner. CGC (Park et al., (2022) learns node embeddings and cluster assignments in contrastive graph learning framework, where positive and negative samples are carefully selected in a multi-level scheme.
The majority of these methods are based on static graphs, where different modules match the adjacency matrix, with the most common being the soft assignment distribution and graph reconstruction Wu al.] (2023 2024). However, the deep clustering for temporal graphs remains largely unexplored. Temporal graphs emphasize time information between nodes in interaction sequence, which is an important data form of dynamic graphs.
A.2 TEMPORAL GRAPH LEARNING
Graph data can be classified into static and dynamic graphs based on the presence absence of time information Liang et al. (2022) ; Mo et al. (202b)). Traditional static graphs represent data in the form of an adjacency matrix, where samples are nodes and relationships between samples are edges (He et al. 202I). Various methods based on static graphs process the adjacency matrix in different ways to generate node embeddings, such as DeepWalk (Perozzi et al. 22014), which employs random walk to generate node representations. Node2vec (Grover & Leskoved (016) extends the random walk strategy depth- first and breadth-firse AE (Hinton & Salakhutdinov (2006) first proposes the auto-encoder framework, while GAE and VGAE (Kipf & Welling (0166) further extend AE to graph data. GraphSAGE (Hamilton et al. 2017) is the first inductive method on graphs.
Dynamic graphs can be further classified into discrete graphs (discrete-tima) dynamic graphs, DTDGGs and temporal graphs (continuous-tim) dynamic graphs, CTDGs). Discrete graphs generate multiple static snapshots based on the fixed time interval, where each snapshot is considered as a static graph,
and all snapshots are sorted chronologically (Gao & Ribeiro 202T Wu et al. 202T Liang al. 2023b). Discrete graph methods typically use the static model to learn each snapshot and then introduce RNN or attention modules to capturethe time information between different snapshots,
such as EvolveGCN (Pareja et al. 2020) and DySAT (Sankar et al.) 2020). In this case, discrete graphs can still be handled with common graph clustering technologies.
Unlike discrete graphs, temporal graphs can observe each node interaction more clearly. Temporal graphs, also known as continuous-time dynamic graphs (CTDGs), discard the adjacency matrix form and record node interactions based on the sequence directly. Temporal graph methods can divide data into batches and then feed it into the model for a single batch. For instance, HTNE (Zuo et al. 2018) employs the Hawkes process (Hawkes) 1971) to model historical neighbors' influence. JODIE (Kumar et al. 2019) aims to predict future node embeddings with uncertain time intervals. DyRep (Trivedi al. 2019 combines local propagation, propaaaop,,,,,,,, and external information patterns
14

---

Published as a conference paper at ICLR 2024
to generate node embeddings. TGAT (Xu et al. 2020) encodes the time information and introduces the kernel function to decode it. TGN (Rossi et al.
2020 stores the historical memory of each node and then updates them after interactions. MNCI (Liu & Liu 202I) considers both community influence and neighhorhood influence to generate node representations inductively. TREND (Wen & Fang (022) utilizes a graph neural network module model the conditional intensity between nodes. TMac (Liu et al. 2023a) introduces the multi-modal temporal graph network for audiovisual event classification.
A.3 DIFFERENCE DISCUSSION
In fact, most temporal graph methods focus on link prediction rather than node clustering, which we attribute to the facts: On the one hand, temporal graph datasets rarely have corresponding node labels, and their data types are more suitable for targeting edges rather than nodes. On the other hand, the existing clustering techniques need to be adapted for the temporal graphs. Although there are very few methods that refer to the concept of temporal graph clustering from different perspectives, we should still point out that their description of temporal graph clustering is not sufficient:
(1) CGC (Park et al. 2022) claims to conduct the experiment of temporal graph clustering, but in fact, the experiment based on discrete dynamic graphs and only carries out on one dataset. We acknowledge that discrete graphs and temporal graphs are inter-convertible, but temporal graphs have a more granular way of observing data than discrete graphs. Discrete graphs have be processed as static graphs for each snapshot, which means that it can hardly process large-scale graphs. In other words, even discrete dynamic graphs (equivalent to static graphs) with only one static snapshot can cause memory overflow problems, discrete graphs with multiple static snapshots combined will only appear to be more problematic in this regard. Thus we cannot give up the novel data processing pattern of temporal graph methods, which is one of the implications of temporal graph clustering. As the same reason, DNE (Du et al., 2018), RTSC (You et al. 2021), DyGCN (Cui et al. 2021). and 2022) are successful on discrete graphs, but not applicable temporal graphs.
VGRGMM (Li et al.
(2) GRACE Yang et al. 2017) is a classical graph clustering method. Although its title includes "dynamic embedding", actually refers dynamic self-adjustment, which is still a static graph. STAR (Xu et al. 2019) and above Yao et al. (Yao & Wong 202T) focus on node classification in temporal graphs, which mismatch with the node clustering task.
(3) Some methods claim to discuss clustering on dynamic or temporal graphs (Gorke et al. 2009 2013, Matias & Miele 2017 Nanayakkara et al. 2019 Ruan et al.) 202I). However, they tend to use traditional machine learning or data mining algorithms rather than deep learning technologies, that
we do not discuss here.
(4) Some works contain keywords such as "temporal / dynamic graph clustering" in the title but are less relevant to temporal graph. For example, DeGiee (Liang al., (023c) a data-parallel job framework for directed acyclic graphs, where the graph and temporal information are fully separated. DCFG (Bu et al. 2017) focuses on the dynamic cluster formation game in attribute graphs. DPC-DLP (Scyedi et al. 2019) considers the clustering task and uses KNN to propagate labels dynamically.
Through the introduction some related work (more works will be described Appendix), we con- sider that there is little comprehensive discussion of temporal graph clustering. With this motivation, we propose the general framework TGC and further discuss temporal graph clustering.
B EXPERIMENTS
B.1 EXPERIMENTAL SETTINGS
We conduct node clustering experiments on all datasets for all methods. First, we perform these models generate node embeddings on all datasets, then utilize K-means to cluster these embeddings. We select Accuracy (ACC), Normalized Mutual Information (NMI), Average Rand Index (ARI), and macro F1-score (F1) as metrics.
We utilize Adam as the optimizer and select the value of pareeeerrsmeters embedding dimension size d, batch size, historical sequence length 1, negative sampling size Q, and learning rate as 128,
15

---

Published as a conference paper at ICLR 2024
60
50
Tom
Tow-BRuch
Tom
Ton-Rock
Tee
Tom-Baoc
TaneNNok
TGC
Tom=Nook
TGC
Temp Node
TOC
40
50
Perfomunct
Perfomant
40+
40
40
20+
20+
201
20-
20
ACC
NIM
ARI
20
ACC
F1
ACC
NMI
E1
(a) DBLP
(b) Brain
(c) Patent
50
Tux
Tau-Buudh
Tix
TaneBushh
Tann-Buk
Tode-Noe
Teec-Nook
TGCC
TGC
$9.5
Pefformmme
50
98.5
08.0
ACC
NIME
ARI
ACC
F1
ACC
NMI
F1
(d) School
(e) arXivAI
(f) arXivCS
Figure 5: Ablation study on all datasets.
1024, 3, 5, and 0.01, respectively. We set the epoch number T s 200 all datasets. For all baseline methods, we utilize their default parameter values.
Our proposed TGC framework is implemented with PyTorch, and all models are running NVIDIA RTX 3070Ti GPUs (8GB), 64GB RAM, 3.2GHz Intel i9- 12900KK CPU.
B.2 ABLATION STUDY
To verify the effectiveness of our proposed module in TGC, we conducted an ablation study ex- periment on three datasets. Our TGC method includes temporal loss and clustering loss, where the temporal loss is classic basic module introduced by many works and has not been modified. Therefore, the ablation study focuses only on the clustering loss, including the node-level module and batch-level module. We remove one module the model only retains the temporal loss, we name "Tem". If the model includes an additional node-level batch-level module top of the temporal loss, respectively name them "Tem+Node" and Batch. We compare these models with the full model "TGC".
time to verify its effectiveness. Specifically,
According to Fig. 5 we observe that both the node-level and batch-level modules effectively improve the performance of the model. In most cases, the node-level module has a greater effect on performance improvement than the batch-level module. The best performance is achieved when both modules are added to the model simultaneously. This suggests that the two modules we proposed can effectively enhance clustering performance, with the node-level module playing the most important role.
B.3 PARAMETER SENSITIVITY STUDY
In this section, we analyze some hyper-parameters in TGC, including the historical sequence length, 1, and the negative sampling number, Q.
As mentioned in the Problem Definition section, the historical sequence length, 1, is an important hyper-parameter in temporal graph learning. In real-world graphs, the total number of neighbors may
vary from node to node. To avoid computational inconvenience, we fix the sequence length, i, and
select the latest neighbors for all nodes in each batch, instead of all neighbors. Based on previous
works (Zuo et al. 2018 Lu et al. 2019 Xu al., 2020 Wang et al.
2021 Wen & Fang 2022
Liu
jet al., 2023bb and our experiments, we select different values for Q, 1.c. 1/Q = 1/2 3 3/5/ 10, to verify the sensitivity of l and Q.
16

---

Published as a conference paper at ICLR 2024
Wolel
Ne gloaa bodes
Figure 6: Parameter sensitivity study on the DBLP dataset.
nun
Figure 7: Parameter sensitivity study on the Brain dataset.
bodka
Beigttrr Sada
Figure 8: Parameter sensitivity study the Patent dataset.
ACC.1
Hodes
ploor Saca
ploot focas
Figure 9: Parameter sensitivity study on the School dataset.
Highte koW
Niggow
Figure 10: Parameter sensitivity study on the Aiv dataset.
Heighte
Figure 11: Parameter sensitivity study the arXivCS dataset.
17

---

Published as a conference paper at ICLR 2024
As shown in Figs. 6 11 report the effects of different parameter settings. It can be found that:
(1) TGC is relatively insensitive to different parameter settings, as the experimental results often fluctuate within small range. This demonstrates the stability of our framework, which is not constrained by syper-parameter settings.
(2) Changing the parameters will inevitably have some impact the experimental results, from which we can discover patterns. Regarding the historical neighbor sequence length, L, we find that larger values not always better, which is consistent with our previous statement. When is too small, the model may not obtain enough neighborhood information, resulting in poor performance. As I increases, the performance gradually improves, but after reaching certain threshold, the performance decreases again. This is because an excessively long neighbor sequence considers very early neighbor nodes, which have little influence on the current interaction and instead introduce noise. This also reflects that time information is relatively important, and different considerations of time information will bring different changes in performance. In addition, we argue that the optimal length of l varies on different datasets, depending on the average degree of the dataset.
(3) The selection of the number of negative samples, Q. for negative sampling has a high degree of uncertainty, which is not only related to the average node degree of different datasets but also affected by different model structures. Generally, choosing Q 2/3/5 leads to better results, and the variation in Q does not have a significant impact. This is because conditional intensity to be large enough, while also restricting negative intensities to be as small as possible. The ideal case is that negative intensities go O. In other words, as all of these negative intensities go to O, no amount of negative samples will make much difference to the loss value. Therefore, the low sensitivity of TGC Q precisely indicates that it can distinguish positive and negative samples well.
encourage the positive
In summary, the TGC framework is not sensitive the choice of Sypper-parameters, and set default. values that can be used for all datasets, i.c., I = 3 and Q 5, for convenience.
18


Reviews:
[{"review_id": "mVlxXSiZoK", "reviewer": "Reviewer_8jHD", "summary": "This work focuses on deep temporal graph clustering and proposes a general framework for deep Temporal Graph Clustering called TGC, which introduces deep clustering techniques to suit the interaction sequence-based batch-processing pattern of temporal graphs. The experimental results are impressive and demonstrate the effectiveness of the proposed framework.", "questions": "Why isn't there more discussion about the two new datasets that you developed yourself in the paper? It doesn't seem to be presented very well in the appendix section either.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1 The paper is well-written, structured and easy to follow. The authors provide sufficient implementation and experimental details in the Appendix. \n2 The authors' focus and exploration of temporal graph clustering may shed new light on the graph learning community.\n3 The experiments are extensive and the results are presented in a clear and concise manner.", "weaknesses": "1 The authors mention that datasets are processed by batches, so for each batch does that mean it is a subgraph structure obtained by sampling? Or what is the difference between this way of processing the data in batches, compared to the way of training according to subgraphs?\n\n2 I would like the authors to further discuss the practical application of temporal graph clustering in real-world scenarios to demonstrate the significance of this ‘new’ task.\n\n3 The authors need to check the paper for grammatical and spelling errors, such as the wrong quotation marks above the Eq (7).", "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": "", "extra_scores": {}}, {"review_id": "J81DytcBEk", "reviewer": "Reviewer_Euq6", "summary": "This paper studies temporal graph clustering via graph neural networks. Temporal graphs have been widely investigated in the graph community. However, the topic of temporal graph clustering is less explored. The authors argue that this is because of lacking datasets suitable for clustering, thus several datasets are carefully selected by the authors for experiments. Moreover, the authors also introduce two tricks (i.e., clustering assignment distribution and adjacency matrix reconstruction) to improve existing models’ performance on temporal graph clustering task. Experimental results on 6 public datasets demonstrate that the proposed general framework TGC can outperform recent baselines with different gains.", "questions": "1)\tThe comparisons of GPU memory usage are not fair in Figure 2. The authors only compare their TGC with static deep clustering baselines that feed whole graphs.\n2)\tThe running time should also compare with other temporal baselines.\n3)\tIt is not clear how clustering assignment distribution and adjacency matrix reconstruction will individually impact the model's performance.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1)\tThis paper investigates temporal graph clustering, which is less explored in the graph community.\n2)\tBoth large and small datasets are used in the experimental sections and the results demonstrate the proposed model achieve really good performance.\n3)\tMemory consumption and running time are reported to show the efficiency of the proposed framework.\n4)\tAblation studies are given to show the effectiveness of the proposed components.", "weaknesses": "1)\tThe technical contribution of this paper is very limited. The two introduced tricks (i.e., clustering assignment distribution and adjacency matrix reconstruction) have been widely used by existing works. Eq. 6 and Eq. 7 are commonly utilized in existing static graph clustering models. No new models are proposed in this paper.\n\n[1] Bo D, Wang X, Shi C, et al. Structural deep clustering network[C]//Proceedings of the web conference 2020. 2020: 1400-1410.\n\n[2] Xie J, Girshick R, Farhadi A. Unsupervised deep embedding for clustering analysis[C]//International conference on machine learning. PMLR, 2016: 478-487.\n\n2)\tThis paper studies continuous-time dynamic graphs. The authors argue that their selected datasets are more suitable for temporal graph clustering tasks. However, it seems that it is not true. As we can see in Table 1, most of the selected datasets have very limited timestamps, which is not consistent with their claimed continuous-time dynamic graphs. They are more like discrete-time dynamic graphs. For example, the DBLP, arXivAI and arXivCS datasets usually contain publication year only. \n3)\tThe comparisons of GPU memory usage are not fair in Figure 2. The authors only compare their TGC with static deep clustering baselines that feed whole graphs. The authors should compare their TGC with existing temporal graph clustering baselines like HTNE, TGAT, JODIE, etc. The low consumption of TGC largely depend on its backbone model HTNE, thus it is hardly to say this is the advantage of TGC. This comment can also be applied to Figure 3. The running time should also compare with other temporal baselines.\n4)\tIn Figure 4, it is not clear what is TGN + TGC? Since TGC is based on HTNE, I guess what you mean is applying clustering assignment distribution and adjacency matrix reconstruction to TGN. If so, please give the ablation studies on each component.\n\nThere are lots of typos in the paper. Some of them are listed as follows:\n\n“A sample general framework” should be “A simple general framework…”\n\n“which we do not discuss here” should be “that we do not discuss here”\n\n“Then We conduct” should be “Then, we conduct”", "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": "", "extra_scores": {}}, {"review_id": "O5uowPKcjD", "reviewer": "Reviewer_PosK", "summary": "This paper expands deep graph clustering to temporal graphs from four aspects, including problem, algorithm, dataset, and evaluation. A generalized framework named TGC is proposed for temporal graph clustering. The authors demonstrate the superiority of TGC and provide sound insights via extensive experiments.", "questions": "See Strengths and Weaknesses.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "+ The motivation is clear. It is meaningful to expand deep clustering to temporal graphs. The presentation is excellent. \n\n+ The core idea is novel and easy to follow. The temporal loss mines graph temporal information and the clustering loss is improved with node-level distribution and batch-level reconstruction. \n\n+ The experiments are comprehensive. The analyses provide many significant insights for temporal graph clustering.", "weaknesses": "- The authors just conduct the clustering algorithms one run. However, most clustering algorithms are not robust and are sensitive to random seeds.\n\n- The performance of TGC on the Brain dataset is not promising. Please provide the explanation and analyses. \n\n- The related work section is limited. The authors need to survey and compare more papers published in 2022 and 2023. \n\n- Missing middle-scale datasets. The authors should explore the dataset size boundaries of the statics deep graph clustering methods.\n\n- The chronological order training is a strong restriction. I’m concerned that such as this strong strict will limit the performance on some datasets. As I know, some methods can disrupt the graph structure for training. \n\n- In Figure 11, point out which sub-figure represents the result on which dataset. Besides, ablation studies should be provided in the main text. Figure 2 is too small. In addition, there seems to be something wrong with the commas.\n\n- Have you considered explaining the relationship between the number of nodes in the static graph and the number of edges in the temporal graph further? This is an exciting topic, i.e., what is the difference in the way of thinking about a problem when the focus shifts from nodes to edges?", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)