Time-evolving graphs, also known as temporal networks, are a crucial area of study in network science and are ubiquitous in the real world. They represent systems where entities (nodes) and their interactions (edges) change over time. Understanding and predicting the behavior of these dynamic networks are essential for various applications, from tracking disease spread to detecting fraudulent activities and enhancing recommendation systems. However, modeling and analyzing time-evolving graphs presents significant challenges due to their complex and ever-changing nature. Therefore, there is a pressing need to develop advanced machine learning techniques that can effectively handle the unique characteristics of temporal networks.
Selected Publications
UTG: Towards a Unified View of Snapshot and Event Based Models for Temporal Graphs
Here we introduce the Unified Temporal Graph (UTG) framework, which integrates snapshot-based and event-based machine learning models for temporal graphs under a single framework. This unification allows models developed for one type of temporal graph representation to be effectively applied to the other, addressing the previous isolation in their development. The research comprehensively evaluates both snapshot and event-based models on temporal link prediction tasks, revealing that snapshot-based models, when combined with UTG training, can perform competitively with event-based models like TGN and GraphMixer, even on event datasets. This work promotes experimental comparison and theoretical cross-pollination between the two approaches, advancing the field of temporal graph learning
TGB 2.0: A Benchmark for Learning on Temporal Knowledge Graphs and Heterogeneous Graphs
TGB 2.0 introduces a novel benchmarking framework for evaluating methods for predicting future links on Temporal Knowledge Graphs (TKGs) and Temporal Heterogeneous Graphs (THGs), focusing on large-scale datasets. This framework extends the original Temporal Graph Benchmark by providing eight new datasets spanning five domains, which are significantly larger and more diverse than existing datasets. TGB 2.0 includes a reproducible and realistic evaluation pipeline for multi-relational temporal graphs, addressing the challenges in this area and promoting standardized and reliable benchmarking.
Static graph approximations of dynamic contact networks for epidemic forecasting
In this work, we introduce new, more rigorous evaluation procedures for link prediction in dynamic graphs, addressing the challenges and real-world considerations that are often overlooked in static graph analysis. The authors propose tools to enhance the evaluation process, including new datasets, innovative negative sampling strategies, and a strong baseline model. These contributions aim to better compare the strengths and weaknesses of different methods, highlighting the importance of robust evaluation frameworks in advancing the field of dynamic graph learning
Temporal Graph Analysis with TGX
Here we introduce TGX, a Python package specifically designed for the analysis of temporal networks, addressing a gap in existing software libraries that primarily focus on static graphs. TGX provides an automated pipeline for data loading, processing, and analysis of evolving graphs, making it a robust tool for examining the features of temporal graphs. It includes functionalities for data processing, such as discretization of temporal graphs and node sub-sampling, and offers a variety of measures for network analysis, including average node degree and the evolving number of nodes and edges per timestamp. Additionally, TGX supports numerous temporal graph visualization plots and statistics out of the box, making it useful for studying social networks, citation networks, and tracking user interactions.
Temporal Graph Benchmark for Machine Learning on Temporal Graphs
In this paper, we introduce the Temporal Graph Benchmark (TGB), a comprehensive collection of large-scale, diverse datasets designed for the realistic, reproducible, and robust evaluation of machine learning models on temporal graphs. These datasets span multiple years and domains, including social, trade, transaction, and transportation networks, and encompass both node and edge-level prediction tasks. The research highlights significant variability in the performance of common models across different datasets and demonstrates that simple methods often outperform existing temporal graph models in dynamic node property prediction tasks. Additionally, TGB provides an automated machine learning pipeline for data loading, experiment setup, and performance evaluation, fostering reproducible and accessible research.
Fast and Attributed Change Detection on Dynamic Graphs with Density of States
We introduce a novel spectral method called Scalable Change Point Detection (SCPD) to address the limitations of current solutions in detecting anomalous change points in dynamic graphs. SCPD generates an embedding for each graph snapshot by efficiently approximating the distribution of the Laplacian spectrum, and it can capture shifts in node attributes by tracking correlations between attributes and eigenvectors. Through extensive experiments using synthetic and real-world data, the authors demonstrate that SCPD achieves state-of-the-art performance, is significantly faster than existing methods, can handle large quantities of node attributes, additions, or deletions, and effectively discovers interesting events in large real-world graphs
Towards Better Evaluation for Dynamic Link Prediction
In this work, we introduce new, more rigorous evaluation procedures for link prediction in dynamic graphs, addressing the challenges and real-world considerations that are often overlooked in static graph analysis. The authors propose tools to enhance the evaluation process, including new datasets, innovative negative sampling strategies, and a strong baseline model. These contributions aim to better compare the strengths and weaknesses of different methods, highlighting the importance of robust evaluation frameworks in advancing the field of dynamic graph learning
A Strong Node Classification Baseline for Temporal Graphs
Here we introduce a robust and effective baseline method for node classification in temporal graphs, serving as a benchmark for evaluating more complex models. This approach is characterized by its simplicity and strong performance in categorizing nodes based on their evolving characteristics within the graph. By addressing the unique challenges posed by temporal graphs, the method provides a clear point of comparison for researchers and practitioners, enhancing the understanding and development of advanced techniques in temporal graph analysis. Its relevance spans various applications, including link prediction and node attribute inference in dynamic networks.
SigTran: Signature Vectors for Detecting Illicit Activities in Blockchain Transaction Networks
SigTran is an efficient graph-based method for identifying illicit nodes in blockchain networks. SigTran constructs a graph from blockchain transaction records, representing nodes based on their structural and transactional characteristics to differentiate between legitimate and illicit activities. This method is versatile and can be applied to various blockchain networks.
Incorporating dynamic flight network in SEIR to model mobility between populations
In this paper, we introduce a significant enhancement to the standard SEIR (Susceptible, Exposed, Infectious, Recovered) epidemiological model by integrating dynamic flight networks to better capture the mobility of populations, particularly in the context of disease spread like COVID-19. The authors propose a modified model called Flight-SEIR, which accounts for the movement of individuals through air travel, thereby estimating imported cases based on air traffic volume and test positive rates. This modification allows for more accurate modeling of disease transmission between populations, enabling early detection of outbreaks, more precise estimation of the reproduction number, and better evaluation of the impact of travel restrictions. By incorporating real-world flight data, Flight-SEIR provides a more realistic and comprehensive approach to epidemiological modeling, crucial for navigating pandemics in an interconnected world.
Technology Transfer
Temporal Graph Benchmark
The Temporal Graph Benchmark (TGB) is a comprehensive collection of datasets designed for the realistic, reproducible, and robust evaluation of machine learning models on temporal graphs. These datasets are large-scale, span multiple years, and cover various domains such as social networks, trade networks, transaction networks, and transportation networks. They include both node and edge-level prediction tasks, providing a diverse set of challenges for researchers.
The follow-up work TGB 2.0 is a new benchmarking framework designed to evaluate methods for predicting future links on Temporal Knowledge Graphs (TKGs) and Temporal Heterogeneous Graphs (THGs). This framework extends the original Temporal Graph Benchmark by focusing on large-scale datasets, which are significantly larger than existing datasets in terms of nodes, edges, or timestamps.
TGB offers an automated machine learning pipeline that facilitates reproducible and accessible research. This pipeline includes tools for data loading, experiment setup, and performance evaluation. The benchmark is regularly maintained and updated, and it welcomes feedback from the community to ensure its continued relevance and improvement.
Funding
We acknowledge funding from the Canadian Institute for Advanced Research (CIFAR AI Chair Program), Google, Mila - Quebec AI Institute and Samsung.
