An embedding-based distance for temporal graphs
Temporal graphs are commonly used to represent time-resolved relations between entities in many natural and artificial systems. Many techniques were devised to investigate the evolution of temporal graphs by comparing their state at different time points. However, quantifying the similarity between temporal graphs as a whole is an open problem. Here, we use embeddings based on time-respecting random walks to introduce a new notion of distance between temporal graphs. This distance is well-defined for pairs of temporal graphs with different numbers of nodes and different time spans. We study the case of a matched pair of graphs, when a known relation exists between their nodes, and the case of unmatched graphs, when such a relation is unavailable and the graphs may be of different sizes. We use empirical and synthetic temporal network data to show that the distance we introduce discriminates graphs with different topological and temporal properties. We provide an efficient implementation of the distance computation suitable for large-scale temporal graphs.
Code (1)
Tasks
RelationSimilar Papers 제목 키워드 기반
Local Distance-Preserving Node Embeddings and Their Performance on Random Graphs
Learning node representations is a fundamental problem in graph machine learning. While existing embedding methods effectively preserve local similarity measures, they often fail to capture global functions like graph di…
Graph Representation LearningRepresentation LearningComparing Temporal Graphs Using Dynamic Time Warping
Within many real-world networks the links between pairs of nodes change over time. Thus, there has been a recent boom in studying temporal graphs. Recognizing patterns in temporal graphs requires a proximity measure to c…
Dynamic Time WarpingTime Series AnalysisWILTing Trees: Interpreting the Distance Between MPNN Embeddings
We investigate the distance function learned by message passing neural networks (MPNNs) in specific tasks, aiming to capture the functional distance between prediction targets that MPNNs implicitly learn. This contrasts …
Embedding Directed Graphs in Potential Fields Using FastMap-D
Embedding undirected graphs in a Euclidean space has many computational benefits. FastMap is an efficient embedding algorithm that facilitates a geometric interpretation of problems posed on undirected graphs. However, E…
Metric Learning on Temporal Graphs via Few-Shot Examples
Graph metric learning methods aim to learn the distance metric over graphs such that similar graphs are closer and dissimilar graphs are farther apart. This is of critical importance in many graph classification applicat…
Drug DiscoveryGraph ClassificationMetric LearningRepresentation Learning