PaperlayerView exact revision on arXiv

Source-linked AI summary

CLDG: Contrastive Learning on Dynamic Graphs

Yiming Xu, Bin Shi, Teng Ma, Bo Dong, Haoyi Zhou, Qinghua Zheng

arXiv:2412.14451v1cs.LGcs.AI

TL;DR

Graph labels are difficult to obtain, and perturbation-based graph contrastive learning can change semantics without using temporal information. CLDG samples timespan views to learn local and global representations under temporal translation invariance. Across seven datasets, it reports state-of-the-art results against 12 established baselines and better classification accuracy than supervised methods on four datasets.

  • Problem

    Graph labels can be difficult and costly to obtain, while perturbation-based contrastive learning may change semantics and labels and does not use temporal information.

    Source: §I · p. 1

  • Method

    CLDG samples multiple timespan views and trains local- and global-level contrastive representations to maintain temporal translation invariance.

    Source: §I · p. 2

  • Results

    On 7 datasets, CLDG achieves state-of-the-art results on 12 established baselines and better classification accuracy than supervised methods on 4 datasets.

    Source: §I · p. 2

  • Takeaways & Limitations

    CLDG is presented as a simpler, lighter approach with lower space and time complexity than existing dynamic-graph methods.

    Source: §I · p. 2

    CLDG may not apply when dynamic-graph changes are noncontinuous and nonsmooth and graph labels are constantly changing.

    Source: §VI · p. 11

Abstract

from arXiv · show

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.

I. INTRODUCTION

CLDG addresses the difficulty of learning graph representations without abundant labels and the risks of applying static graph contrastive learning to dynamic graphs. It uses temporal translation invariance to build an unsupervised framework, with reported strong benchmark results and lower complexity than existing dynamic-graph methods.

I. INTRODUCTION

  • Dynamic-graph labels are costly to obtain, while perturbation-based contrastive views can alter semantics and fail to use temporal information.Source: §I · p. 1
  • Temporal translation invariance describes same-node semantics and labels remaining similar across timespans, motivating local- and global-level contrastive pairs.Source: §I · pp. 1–2
  • CLDG samples multiple timespan views, then learns node and neighborhood representations with shared encoders, readout functions, and projection heads, using separate local and global contrastive losses.Source: §I · p. 2
  • CLDG is designed for unsupervised representation learning on both discrete-time and continuous-time dynamic graphs.Source: §I · p. 2
  • The paper characterizes CLDG as simpler and lighter, with lower space and time complexity than existing dynamic-graph methods, and says it permits varied encoder architectures.Source: §I · p. 2
  • On 7 datasets, CLDG achieves state-of-the-art results on 12 established baselines and better classification accuracy than supervised methods on 4 datasets.Source: §I · p. 2

A. Contrastive Learning on Graphs

  • Graph contrastive methods generate views through graph perturbations, but unsuitable augmentations can introduce noise or change semantics and labels; these methods are designed for static graphs.Source: A. Contrastive Learning on Graphs · p. 2

B. Representation Learning on Dynamic Graphs

Dynamic-graph representation methods span discrete-time and continuous-time approaches, but existing methods face concerns around scalability, noisy information, and representation collapse. The paper distinguishes graphs organized as snapshots from graphs whose nodes and edges carry timestamps.

B. Representation Learning on Dynamic Graphs

  • Dynamic-graph methods divide into discrete-time approaches, which model snapshots, and continuous-time approaches, which model timestamped interactions.Examples include DySAT and TGAT for discrete-time graphs, and HTNE and JODIE for continuous-time graphs.Source: B. Representation Learning on Dynamic… · p. 3
  • Existing methods may incur high time complexity and limited parallelism, fit noisy information, or collapse under temporal regularization.The passage attributes these as limitations affecting at least some existing dynamic-graph methods.Source: B. Representation Learning on Dynamic… · p. 3

A. Dynamic Graph Modeling

  • A discrete-time dynamic graph is a sequence of network snapshots within a given time interval.Each snapshot is represented as Gt = {Vt, Et}, with edges drawn from the snapshot's nodes.Source: A. Dynamic Graph Modeling · p. 3
  • A continuous-time dynamic graph has nodes and edges annotated with timestamps.The timestamp function maps each node and edge to a real-valued time.Source: A. Dynamic Graph Modeling · p. 3

B. Problem Formulation

The paper formulates dynamic-graph representation as learning embeddings that preserve temporal and structural information. CLDG addresses contrastive-pair selection through timespan views and local and global temporal translation invariance.

B. Problem Formulation

  • The goal is to map each dynamic-graph vertex to a lower-dimensional embedding that preserves temporal and structural information.The embedding dimension d is much smaller than the number of vertices.Source: B. Problem Formulation · p. 3

IV. PROPOSED METHOD

  • CLDG addresses two challenges: applying contrastive learning to dynamic graphs and selecting timespans as contrastive pairs.The paper treats timespan selection as a challenge built on its dynamic-graph contrastive-learning approach.Source: §IV · p. 3
  • CLDG's five components are a timespan-view sampling layer, base encoder, readout function, projection head, and contrastive loss.The sampling layer extracts temporally persistent signals; the encoder and readout learn local and global representations.Source: §IV · p. 3
  • The architecture samples multiple views, encodes them with shared weights, and uses readout to generate node-neighborhood embeddings.The figure describes the input as a graph and applies the shared encoder to the sampled views.Source: Figure 2 · p. 4
  • A projection head maps node and neighborhood embeddings into the contrastive-loss space.The architecture applies contrastive learning to maintain local and global temporal translation invariance.Source: Figure 2 · p. 4, §IV · p. 4
  • CLDG uses its contrastive loss to maintain temporal translation invariance at both local and global levels.The architecture applies the contrastive approach after projection of node and neighborhood embeddings.Source: §IV · p. 4, Figure 2 · p. 4

A. Temporal Translation Invariance

The paper reports that the same node's prediction labels tend to remain similar across timespans, motivating temporal translation invariance as a basis for dynamic-graph contrastive pairs. Its sampling layer varies view timing and overlap to explore suitable timespan pairs.

A. Temporal Translation Invariance

  • Graph augmentation through node, edge, or feature perturbation may change labels, motivating a more graceful way to select contrastive pairs.The passage gives edge addition and edge dropping as examples of perturbations that may alter graph semantics.Source: A. Temporal Translation Invariance · p. 4
  • Across the studied timespans, the same node's prediction labels tend to be similar regardless of the encoder, a phenomenon termed temporal translation invariance.The empirical study used GNN encoders with the same architecture but without shared weights.Source: A. Temporal Translation Invariance · p. 4
  • Under temporal translation invariance, CLDG pairs the same node across views locally and a node with its neighbor across views globally.Local pairs pull same-node representations closer and different-node representations apart; global pairs pull node-neighbor representations closer and other nodes' neighbor representations apart.Source: A. Temporal Translation Invariance · p. 4

B. Timespan View Sampling Layer

  • Four sampling strategies vary temporal overlap, since excessive overlap may oversimplify pairs while widely separated views may lose shared semantic context.The strategies also examine the number and size of views; Figure 3 presents four candidate strategies.Source: B. Timespan View Sampling Layer · p. 4, Figure 3 · p. 5
  • The sampling layer selects v views of duration Δt/s from a continuous graph, with v and s controlling view count and size.The overall graph span is defined as Δt, and the sampled time tuple determines which edges each view retains.Source: B. Timespan View Sampling Layer · p. 5
  • Sequential sampling divides the graph into s non-overlapping views and randomly selects v unduplicated views, whereas high- and low-overlap strategies use 75% and 25% overlap.The random strategy can produce views that do not overlap or only partially overlap; sequential sampling is described as usable for discrete-time dynamic graphs.Source: B. Timespan View Sampling Layer · p. 5

C. Base Encoder Layer

CLDG samples multiple graph views each training epoch and encodes them to produce node embeddings. It permits different encoder architectures and uses shared weights across views.

C. Base Encoder Layer

  • Each training epoch, the sampling layer draws V graph views for encoding.The views are denoted eG1 through eGV.Source: C. Base Encoder Layer · p. 5
  • Each view contains a feature matrix and adjacency matrix, and CLDG permits arbitrary encoder architectures, using GCN in this paper.The GCN is chosen to model structural dependencies.Source: C. Base Encoder Layer · p. 5
  • Because sampled views can contain different nodes and edges, implementation uses minibatches and shared encoder weights to improve representation consistency across views.The i-th view's encoder output is a node embedding Hi with batch size N and embedding dimension d.Source: C. Base Encoder Layer · p. 5

D. Readout Function Layer

The readout function forms neighborhood representations for nodes in each sampled view using statistical aggregation. The authors use average, maximum, or summation rather than graph pooling.

D. Readout Function Layer

  • The readout function generates neighborhood representations from each node’s neighbors under a sampled view.The neighbor set and its embedding representation are identified for node i under view T.Source: D. Readout Function Layer · pp. 5–6
  • Average, maximum, and summation are the statistical readout methods used to aggregate neighborhood information.The authors state graph pooling is not the core of this work.Source: D. Readout Function Layer · p. 6
  • The statistical readout is described as simple and effective, without introducing additional model parameters.Source: D. Readout Function Layer · p. 6

E. Projection Head Layer

CLDG projects node and neighborhood representations into the contrastive-loss space, then trains with local and global temporal consistency objectives. Each epoch samples views and shared nodes before updating the encoder and projection head.

E. Projection Head Layer

  • The shared projection head maps node and neighborhood representations into the space where contrastive loss is applied.It is a two-layer MLP with L2 normalization and LeakyReLU nonlinearity.Source: E. Projection Head Layer · p. 6

F. Contrastive Loss Function

  • Local consistency pairs the same node across views as positives, while global consistency pairs a node with neighbors across views.The objectives use InfoNCE; local negatives are different nodes, and global negatives are neighbors of other nodes.Source: F. Contrastive Loss Function · p. 6
  • Each epoch samples multiple views and nodes shared across them, then updates the encoder and projection head by minimizing the local or global loss.The minibatch contains N nodes sampled from nodes shared by the views.Source: F. Contrastive Loss Function · p. 6

G. Advantages over Dynamic Graph Methods

CLDG is presented as handling both discrete- and continuous-time graphs, accommodating different encoders, and avoiding a sequential model architecture. The experiments are framed around benchmark performance, view selection, encoder choice, complexity, and hyperparameters.

G. Advantages over Dynamic Graph Methods

V. EXPERIMENTS

  • The experiments assess benchmark performance, timespan-view choice, encoder effects, complexity, and hyperparameter impacts.The experiments are described as comparing CLDG with twelve baselines and including ablations of its components.Source: §V · p. 7

A. Experiment Preparation

The evaluation uses seven dynamic graph datasets from four fields and compares CLDG with semi-supervised, dynamic-graph, and graph-contrastive baselines. Dataset labels represent application-specific categories such as research field, company industry, credit rating, and sentiment.

1) Real-world Dataset:

  • Seven datasets from academic citation, tax transaction, Bitcoin, and Reddit hyperlink networks are used to evaluate learned representations.Source: 1) Real-world Dataset · p. 7
  • Dataset labels cover researcher field, company industry, Bitcoin-user credit rating, and Reddit hyperlink sentiment.Source: 1) Real-world Dataset · p. 7

2) Baselines:

  • The twelve baselines span semi-supervised methods, unsupervised dynamic-graph methods, and unsupervised contrastive-learning methods.Named examples include GCN and GAT, CAW and TGAT, and DGI and GRACE.Source: 2) Baselines · pp. 7–8

3) Evaluation Protocols:

The evaluation uses linear probing for unsupervised methods and compares CLDG with 12 baselines on seven datasets. CLDGnode leads prior unsupervised results and exceeds supervised baselines on some dataset-metrics.

3) Evaluation Protocols:

  • Unsupervised methods use linear evaluation with a frozen representation model and a classifier trained on training-set embeddings; results report test-set Accuracy and Weighted-F1.Source: 3) Evaluation Protocols · p. 8

4) Implementation Details:

B. Comparison with State-of-the-Art (RQ1)

C. View Sampling Architecture (RQ2)

CLDG's sampling results favor sequential or random views with low overlap, while the view timespan is robust. Experiments also find competitive performance across three encoder architectures.

C. View Sampling Architecture (RQ2)

D. Encoder Architecture (RQ3)

  • All three tested encoders are competitive; GAT leads on DBLP and BITotc, while GCN is only 0.02% and 0.21% above the suboptimal result on BITalpha.Source: D. Encoder Architecture (RQ3) · p. 10

E. Space and Time Complexity Analysis (RQ4)

CLDG has substantially lower parameter counts and running times than compared dynamic graph methods. Sensitivity findings vary by dataset, and the conclusion limits applicability under certain graph changes.

E. Space and Time Complexity Analysis (RQ4)

F. Hyperparameters Sensitivity (RQ5)

VI. CONCLUSIONS

  • The authors state CLDG may not apply when graph changes are noncontinuous and nonsmooth and graph labels change constantly.Source: §VI · p. 11
Loading 2412.14451v1…