Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks

Abstract

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.

Published in ICLR 2021. A bug in previous versions is fixed

References in corpus (9)

• Methods for Interpreting and Understanding Deep Neural Networks
• Variational Graph Auto-Encoders
• Temporal Graph Networks for Deep Learning on Dynamic Graphs
• Nonparametric Link Prediction in Dynamic Networks
• Inhomogeneous Hypergraph Clustering with Applications
• Time2Vec: Learning a Vector Representation of Time
• Self-attention with Functional Time Representation Learning
• Inductive Representation Learning on Temporal Graphs
• Higher-Order Ranking and Link Prediction: From Closing Triangles to Closing Higher-Order Motifs

Cited by in corpus (9)

• TREND: TempoRal Event and Node Dynamics for Graph Representation Learning
• Graph Sequential Neural ODE Process for Link Prediction on Dynamic and Sparse Graphs
• CLDG: Contrastive Learning on Dynamic Graphs
• Predicting Information Pathways Across Online Communities
• ConTIG: Continuous Representation Learning on Temporal Interaction Graphs
• Temporal Graph Network Embedding with Causal Anonymous Walks Representations
• Focus Where It Matters: Graph Selective State Focused Attention Networks
• Exploring the Performance of Continuous-Time Dynamic Link Prediction Algorithms
• Inductive Representation Learning in Temporal Networks via Mining Neighborhood and Community Influences