CLDG: Contrastive Learning on Dynamic Graphs
Yiming Xu, Bin Shi, Teng Ma, Bo Dong, Haoyi Zhou, Qinghua Zheng · 2024
Read CLDG: Contrastive Learning on Dynamic Graphs by Yiming Xu, Bin Shi, Teng Ma, Bo Dong, Haoyi Zhou, Qinghua Zheng (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-14451.txt.
Introduction
Yiming Xu and co-authors present a new method in 2024 for learning from graphs that change over time. A graph links items with lines, and in real data those links shift as time passes. Their method learns by comparing views of the same graph, but that step can blur the meaning of the data when the graph has changed.
Their fix rests on a simple point: some patterns in a changing graph stay the same when shifted in time. A sampling step pulls out parts of the graph that keep that trait. Then the model learns from views that hold on to the true meaning of the data. Tests on later tasks show the method keeps more of the signal that plain view building loses. The work is aimed at tasks where data come as a web that never stands still.
Catalog record
| CREATOR | Yiming Xu, Bin Shi, Teng Ma, Bo Dong, Haoyi Zhou, Qinghua Zheng |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 56 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-14451
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
CLDG: Contrastive Learning on Dynamic Graphs Yiming Xu, Bin Shi, Teng Ma, Bo Dong, Haoyi Zhou, Qinghua Zheng Abstract The graph with complex annotations is the most potent data type, whose constantly evolving motivates further exploration of the unsupervised dynamic graph representation. One of the representative paradigms is graph contrastive learning. It constructs self-supervised signals by maximizing the mutual information between the statistic graph’s augmentation views. However, the semantics and labels may change within the augmentation process, causing a significant performance drop in downstream tasks. This drawback becomes greatly magnified on dynamic graphs. To address this problem, we designed a simple yet effective framework named CLDG. Firstly, we elaborate that dynamic graphs have temporal translation invariance at different levels. Then, we proposed a sampling layer to extract the temporally-persistent signals. It will encourage the node to maintain consistent local and global representations, i.e., temporal translation invariance under the timespan views. The extensive experiments demonstrate the effectiveness and efficiency of the method on seven datasets by outperforming eight unsupervised state-of-the-art baselines and showing competitiveness against four semi-supervised methods. Compared with the existing dynamic graph method, the number of model parameters and training time is reduced by an average of 2,001.86 times and 130.31 times on seven datasets, respectively. The code and data are available at: https://github.com/yimingxu24/CLDG . I Introduction Graph neural network shows superior performance in many real-world applications, such as recommender systems [ 1 , 2 , 3 ] , combinatorial optimization [ 4 , 5 , 6 ] , traffic prediction [ 7 , 8 , 9 ] , risk management [ 10 , 11 , 12 ] , etc. Thus, it is widely investigated in recent years. However, existing methods mainly focus on supervised or semi-supervised learning paradigms, which rely on abundant ground-truth label information. The acquisition of ground-truth labels on graphs may be more complex and difficult than other media forms. Because the graph is an abstraction of the real world, it is not as straightforward as video, image, or text. For example, even without considering data privacy and security in the transaction network, it is impossible to label whether the credit card is frauded through the crowdsourced manner, because it requires a wealth of expert knowledge and experience. These make it very expensive to obtain graph datasets with a large amount of label information. Therefore, it is significant and challenging work to learn rich representations on graphs with unsupervised methods. Some recent works extend unsupervised contrastive learning to graphs [ 13 , 14 , 15 , 16 , 17 , 18 , 19 ] to tackle this problem. They mainly generate augmented views by perturbing nodes, edges, and features, and then construct self-supervised signals by maximizing the mutual information (MI) between different augmented views, thereby eliminating the dependence on labels. However, the semantics and labels may change within the perturbation-based augmentation process, causing a significant performance drop in downstream tasks. For example, adding edges may introduce noise, and deleting edges may delete the most important edges and neighbors for nodes. More seriously, existing methods fail to utilize the temporal information when constructing comparison signals, which further limits the performance on dynamic graphs. Therefore, existing static graph contrastive learning methods may not be the optimal solution for the dynamic graph. How to generalize contrastive learning to dynamic graphs is a challenge. Fig. 1: Illustration of our basic idea. In the dataset used in this paper (details of the datasets are demonstrated in Section V-A1 ), an interesting observation is that the semantics and labels learned by the same node tend to be similar no matter what encoder is used at different timespans of the dynamic graph. We refer to this observation as temporal translation invariance. Based on temporal translation invariance, our basic idea is that the features of the node A, on different timespan should be similar and pull apart the features of other nodes, such as B. To achieve this objective, we perform some empirical studies to explore the properties of dynamic graphs (details of the experimental setup are demonstrated in Section IV-A ). An interesting observation is that the prediction labels of the same node tend to be similar in different timespans, regardless of the encoder used (GCN [ 20 ] , GAT [ 21 ] or MLP [ 22 ] ), as shown in Figure 1 . The different datasets we use all share this characteristic (details of the datasets are demonstrated in Section V-A1 ), and we refer to this observation on dynamic graphs as temporal translation invariance. Under the assumption of temporal translation invariance, we can utilize different timespan views to construct contrastive pairs. We implement two different levels (local and global) of temporal translation invariance. Specifically, at the local-level, we treat the semantics of the same node in different timespan views as positive pairs, encouraging the representation of the same node in each timespan view should be similar. At the global-level, the representation of a node and its neighbors in different timespan views is considered positive pairs. This approach is also intuitively reasonable. For example, in the academic network, most scientific researchers are deeply involved in a certain field and strive for it all their lives. Likewise, the business scope of a company does not change at will in the tax transaction network. In this case, different timespan views of the dynamic graph can be regarded as a more graceful contrastive pairs selection method, without manual trial-and-error, cumbersome search, or expensive domain knowledge for augmentation selection [ 23 ] . Meanwhile, the additional temporal cues provided by dynamic graphs are implicitly exploited by maintaining temporal translation invariance on the graph. To sum up, we propose a new inductive bias on dynamic graphs, namely temporal translation invariance. We design a conceptually simple yet effective unsupervised C ontrastive L earning framework on the D ynamic G raph, called CLDG. Specifically, we first generate multiple views from continuous dynamic graphs via a timespan view sampling method. Subsequently, feature representations of nodes and neighborhoods are learned through a weight-shared encoder and readout function and a weight-shared projection head. Finally, we design local-level and global-level contrastive losses separately to train the model. The pseudocode for CLDG is provided in Algorithm 1 . The main contributions are summarized as follows: \bullet We propose an efficient contrastive learning method on dynamic graphs to perform representation learning on discrete-time and continuous-time dynamic graphs in unsupervised scenarios. \bullet The proposed method is simpler and lighter , and has lower space and time complexity than existing dynamic graph methods. \bullet The proposed method is highly scalable , allowing the selection of various encoder architectures in the past, present and even in the future without any restrictions. \bullet The experimental results on 7 datasets demonstrated that CLDG yields state-of-the-art results of unsupervised dynamic graph representation learning on 12 established baselines, and even achieves better classification accuracy than supervised learning methods on 4 datasets. Algorithm 1 Pseudocode of CLDG in a PyTorch-like style. # f: encoder networks + projection head # g: input graph # N: batchsize # d: embedding dimension # t: temperature # Timespan View Sampling Layer g1, feat1 = temporal_sampling(g) g2, feat2 = temporal_sampling(g) z1 = f(g1, feat1) # N×d