Source-linked AI summary
Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks
Yanbang Wang, Yen-Yu Chang, Yunyu Liu, Jure Leskovec, Pan Li
TL;DR
Temporal-network representation learning must capture dynamic laws while generalizing to unseen nodes and systems, despite intertwined structural-temporal patterns and scalability demands. The paper introduces CAWs and CAW-N, which retrieve temporal motifs through causal walks and anonymize nodes using set-based relative identities. Across six real networks, CAW-N outperforms prior methods in inductive link prediction and also improves results in the transductive setting.
Problem
Temporal-network representation learning needs to capture dynamic laws inductively, but prior approaches depend on node identities or rich edge attributes and face structural-temporal and scalability challenges.
Method
CAW-N uses causal anonymous walks to implicitly retrieve temporal motifs, set-based relative-node anonymization to preserve motif correlations without identities, and constant-cost sampling for online learning.
Results
Inductive link prediction: CAW-N outperforms all SOTA methods by about 15% averaged over 6 networks; transductively, it significantly beats all SOTA methods on 5 networks.
Takeaways & Limitations
CAW-N represents temporal-network dynamics while remaining fully inductive, reducing motif feature-engineering effort and retaining fine-grained temporal information.
Takeaways & Limitations
The method assumes an inductive representation cannot directly use node identities, and its identity-invariance guarantee is stated under bijective mappings between walk sets.
Abstract
from arXiv · showhide
Temporal networks serve as abstractions of many real-world dynamic systems. These networks typically evolve according to certain laws, such as the law of triadic closure, which is universal in social networks. Inductive representation learning of temporal networks should be able to capture such laws and further be applied to systems that follow the same laws but have not been unseen during the training stage. Previous works in this area depend on either network node identities or rich edge attributes and typically fail to extract these laws. Here, we propose Causal Anonymous Walks (CAWs) to inductively represent a temporal network. CAWs are extracted by temporal random walks and work as automatic retrieval of temporal network motifs to represent network dynamics while avoiding the time-consuming selection and counting of those motifs. CAWs adopt a novel anonymization strategy that replaces node identities with the hitting counts of the nodes based on a set of sampled walks to keep the method inductive, and simultaneously establish the correlation between motifs. We further propose a neural-network model CAW-N to encode CAWs, and pair it with a CAW sampling strategy with constant memory and time cost to support online training and inference. CAW-N is evaluated to predict links over 6 real temporal networks and uniformly outperforms previous SOTA methods by averaged 10% AUC gain in the inductive setting. CAW-N also outperforms previous methods in 4 out of the 6 networks in the transductive setting.
1 INTRODUCTION
Temporal-network representation learning must model intertwined structural and temporal patterns, scale to arriving links, and remain inductive enough to generalize dynamic laws across unseen systems. The paper proposes CAWs and CAW-N to capture temporal motifs and their correlations without node identities.
- Temporal networks abstract dynamically interacting elements as nodes and time-stamped interactions as links.
- Representation learning of temporal networks faces entangled structural-temporal patterns and scalability demands from arriving and repetitive links.
- Inductive capability matters because models should capture dynamic laws and generalize to systems sharing those laws but absent from training.
- CAWs backtrack adjacent links over time to extract causal temporal motifs, then anonymize nodes using relative counts across sampled walks.
- CAW-N avoids explicit motif selection and counting, preserves fine-grained temporal information, and supports online learning through constant-memory, constant-time CAW sampling.
- 15% averaged over 6 networks: CAW-N outperforms all SOTA methods in the inductive setting and significantly beats them on 5 networks in the transductive setting.
2 RELATED WORK
Prior temporal-network methods commonly encode snapshots with neural models or assign node-specific representations, limiting inductive use. CAW-N instead removes original identities while preserving relative identities and correlations among temporal motifs.
- Snapshot-based approaches combine consecutive links into network snapshots, then separately encode structural and temporal patterns with neural architectures.
- Many temporal-network models are non-inductive because they associate nodes with one-hot identities, adjacency rows, or free-trained vectors.
- TGAT removes node identities and encodes timestamps and attributes, but its evaluation used networks with rich link attributes rather than structural dynamics alone.
- CAW-N removes original node identities while using relative node identities to avoid the ambiguity associated with identity removal.
3 PROBLEM FORMULATION AND NOTATIONS
A temporal network is represented as time-ordered links, and representation learning is evaluated by predicting future links from historical interactions. Reverse-time walks provide motif-like temporal structures within a restricted time range.
- A temporal network is a sequence of links and timestamps, with each link representing a dyadic event between two nodes.
- The link sequence encodes network dynamics, so models are evaluated by predicting future links from historical links.
- Inductive evaluation additionally tests link prediction between nodes never seen during training.
- A reverse-time walk follows adjacent temporal links with strictly decreasing timestamps.
- Each walk naturally corresponds to a temporal network motif when its time span falls within the motif’s restricted time range.
4 PROPOSED METHOD: CAUSAL ANONYMOUS WALK-NETWORK
CAW-N represents temporal-network dynamics with causal temporal walks and set-based anonymization, then encodes and aggregates these walks for link prediction. Its sampling strategy supports scalable online training and inference while preserving structural and fine-grained temporal information.
- Causal Anonymous Walks: CAWs remove original node identities while retaining relative identities through anonymization, supporting inductive temporal-network representation.Unlike independently anonymized walks, CAWs use a set-based approach designed for temporal-network dynamics.
- Causal Anonymous Walks: Causal sampling backtracks connected links over time, with temporal decay α emphasizing more recent links when α is large.Given a target link and time, the method collects M m-step walks from both endpoints.
- Causal Anonymous Walks: Set-based anonymization counts a node’s appearances at each walk position across endpoint-specific walk sets and establishes correlations within and across sampled walks.This representation can distinguish nodes that single-walk anonymization or timestamp-only encoding fails to distinguish.
- Neural Encoding: CAW-N encodes each anonymized node-time sequence with an RNN, combining anonymization features and time-gap features, then aggregates the encoded walks by mean pooling or self-attention.The resulting representation is passed to a two-layer perceptron for link prediction.
- Extensions: Attributes can be incorporated by concatenating node or link attributes with anonymization and temporal features in the walk encoder.The formulation also supports directed links.
- Extensions: The efficient sampling strategy avoids recording the entire link history, enabling online training and inference with complexity independent of the number of links.When α = 0, uniform sampling requires recording the entire history and is not scalable.
5 EXPERIMENTS
The experiments evaluate CAW-N on six real-world temporal networks using transductive and inductive link prediction, with AUC as the primary metric. CAW-N performs strongly across settings, while sampling studies examine sensitivity, runtime, and efficiency trade-offs.
- 5.2 RESULTS AND DISCUSSION: CAW-N significantly outperforms all baselines on inductive links across all datasets, especially for “new vs new” links.
- 5.2 RESULTS AND DISCUSSION: CAW-N significantly outperforms baselines on four of six datasets in the transductive setting.
- 5.2 RESULTS AND DISCUSSION: CAW-N achieves AUC scores above 0.98 on Reddit and Wikipedia, while baselines remain substantially lower.
- 5.2 RESULTS AND DISCUSSION: Four identity-dependent baselines show significant performance drops from transductive to inductive evaluation, whereas TGAT and EvolveGCN have smaller setting gaps.
- 5.2 RESULTS AND DISCUSSION: Attention pooling outperforms mean pooling for CAW-N, but incurs higher computational complexity.
- 5.3 HYPERPARAMETER INVESTIGATION OF CAW SAMPLING: Only a small number of sampled CAWs is needed for competitive performance, with gains saturating as sampling increases.
- 5.3 HYPERPARAMETER INVESTIGATION OF CAW SAMPLING: Performance typically peaks at a dataset-dependent CAW length; longer walks correspond to more complicated laws encoded in higher-order motifs.
6 CONCLUSION
The conclusion presents CAW-N as an inductive approach for representing temporal-network dynamics through anonymous walks and implicit motif extraction. It also identifies interpretation and higher-order prediction as future directions.
- 6 CONCLUSION: CAW-N uses temporal random walks to implicitly extract network motifs and set-based anonymization to relate motifs while preserving inductive representation.
- 6 CONCLUSION: Neural-network interpretation techniques may help discover larger, meaningful temporal-network motifs and patterns.
- 6 CONCLUSION: CAW-N may be generalized to predict higher-order structures such as triangles across temporal-network domains.
A EFFICIENT LINK SAMPLING
The appendix develops efficient online link sampling for CAW extraction. Precomputed probabilities support iterative sampling, while tree-structured sampling trades some performance for lower search cost.
- Online probability computation: Online probability computation assigns each incoming link a pair of endpoint probabilities for later sampling without further updates.
- Iterative sampling: Iterative sampling samples historical links with probability proportional to exp(α(t − tp)).
- Complexity analysis: For α > 0, each node requires recording only the most recent O(τ/α) links, making online training and inference independent of the total link count.
- Complexity analysis: Under a Poisson arrival assumption, the expected iterations of iterative sampling are bounded by min{2τ/α + 1, |Ewp,tp|}.
- Tree-structured sampling: Tree-structured sampling preserves the total number of walks while reducing link-search operations through per-level branching factors ki.
- Tree-structured sampling: With M = 64 and m = 3, branching factors k1 = k2 = k3 = 4 reduce link-search operations to about 0.44Mm, at slightly worse empirical performance.
C.3 EVALUATION OF SNAPSHOT-BASED BASELINES
The evaluation uses chronological snapshot splits and adjusts snapshot-based scoring for repeated links, enabling comparison with stream-based methods. Performance is reported primarily with AP rather than ACC because confidence thresholds for ACC are ill-defined.
- Evaluation setup: Snapshot-based baselines are evaluated by evenly splitting each dataset chronologically into multiple snapshots.The number of snapshots is selected with reference to the snapshot-based baselines; Wikipedia and MOOC receive dedicated splits because no baseline uses them.
- Evaluation setup: Repeated links within a snapshot are counted multiple times before computing performance metrics.This aligns snapshot-based evaluation with stream-based methods, which consider link multiplicity.
- Metrics: AUC and AP are used for binary link prediction, while ACC is excluded because its confidence threshold is ill-defined.The stated rationale is to avoid unfair comparisons across studies.
- Implementation: Experiments were run on a Ubuntu 16.04 server with a 40-core Xeon CPU, an Nvidia 2080 Ti GPU, and 768 GB memory.
D.2 MORE DISCUSSION ON STREAM-BASED VS. SNAPSHOT-BASED METHODS
Stream-based methods generally perform better because they preserve recent interaction order, whereas snapshot-based methods usually use less memory and computation. CAW sampling addresses the efficiency–effectiveness trade-off in stream-based processing.
- Performance comparison: Stream-based methods generally outperform snapshot-based methods because they access the most recent interactions.Snapshot-based methods aggregate links into static graphs and discard temporal order within each time slice.
- Interpretation: Figure 8 visualizes the most discriminatory CAWs and their occurrence ratios for positive and negative samples.
- Efficiency trade-off: Snapshot-based methods usually consume less memory and computation time than stream-based methods.Stream-based methods must carefully sample history to balance efficiency and effectiveness.
- CAW sampling: CAW sampling is introduced to address the efficiency–effectiveness trade-off in stream-based temporal processing.The cited discussion positions the proposed sampling algorithm as a response to the history-management challenge.
E VISUALIZING CAWS AND AWS
The paper interprets CAWs by mapping anonymized walk encodings to relative coordinates and scoring their contributions to prediction. The resulting CAW shapes separate positive and negative links more clearly than anonymous walks.
- CAW shape construction: CAW shapes map each walk node to relative coordinates based on temporal shortest-path distances from source nodes.The coordinates are derived from ICAW encodings over sampled walks associated with the sources.
- Contribution scoring: CAW-N assigns each sampled CAW a scalar contribution score by applying a linear projection to its encoding.For CAW-N-Mean, averaging and linear projection allow individual walk logits to contribute directly to the final prediction logit.
- CAW interpretation: The highest-scored CAW shapes indicate a general motif-closure pattern in which commonly co-occurring motif nodes are more likely to link.CAW-N adaptively samples informative temporal motif-closure patterns without explicitly enumerating or counting them.
- CAW–AW comparison: Figure 9 visualizes all anonymous walks and their occurrence ratios with positive and negative samples.
- CAW interpretation: Highest-scored CAWs almost never occur with negative links, while lowest-scored CAWs seldom occur with positive links.The within-shape difference between positive and negative occurrence ratios indicates strong discriminatory power.
- CAW–AW comparison: Anonymous-walk occurrence ratios for positive and negative links are highly mixed-up compared with CAWs.The analysis attributes this lower discriminatory power to AWs lacking set-based anonymization and therefore missing correlations between walks.
F COMPARISON WITH THE MOST RECENT WORK
The paper compares CAW-N with Temporal Graph Networks using reported evaluation settings and metrics. TGN is generally stronger than earlier baselines, but CAW-N outperforms it on most datasets, while TGN remains faster.
- Experimental comparison: TGN experiments use the default TGN-attn architecture with a memory updater and the implementation’s reported hyperparameters.The setup includes two attention heads, minibatches of 200, ten temporal neighbors, 100-dimensional time embeddings, 50 training epochs, and learning rate 0.0001.
- Reporting: Table 8 reports TGN average-precision performance as means with 95% confidence levels.The caption states that bold formatting identifies cases where TGN outperforms CAW-N.
- Results: TGN generally outperforms previous baselines and shows smaller inductive–transductive performance gaps.
- Results: CAW-N still outperforms TGN on most datasets, especially on Enron and UCI.
- Efficiency: TGN has the fastest execution speed among all baselines and is faster than CAW-N under its optimal hyperparameter setting.The paper attributes this possibly to TGN’s simple message function and first-hop neighbor sampling.
G NOTES ON UPDATED EXPERIMENTAL RESULTS (OCT 16, 2022)
An implementation error in ICAW and the Self-Att-AGG attention mechanism caused numerical changes in several reported results. The corrected implementation and artifacts were updated, while most conclusions about CAWN remained unchanged.
- An error was identified in the original implementations of ICAW and Self-Att-AGG(Su ∪Sv).
- Tables 2, 3, 6, and Fig.8 changed numerically after the implementation was corrected.
- The corrected implementation and relevant artifacts were updated at the original code repository.
- Despite these numerical changes, the vast majority of conclusions about CAWN remained unaffected.
- The authors credited the authors of Online Graph Nets for helping identify the implementation error.