v#1

# Temporal Graph Analysis with TGX

Razieh Shirzadkhani  McGill University & MilaMontreal, QC, Canada
<EMAIL_ADDRESS>,  Shenyang Huang  McGill University &
MilaMontreal, QC, Canada<EMAIL_ADDRESS>,  Elahe Kooshafar
McGill University & MilaMontreal, QC, Canada<EMAIL_ADDRESS>,
Reihaneh Rabbany  McGill University & MilaMontreal, QC, Canada
<EMAIL_ADDRESS>and  Farimah Poursafaei  McGill University & MilaMontreal,
QC, Canada<EMAIL_ADDRESS>
(2024; 2024)

###### Abstract.

Real-world networks, with their evolving relations, are best captured as
temporal graphs. However, existing software libraries are largely designed for
static graphs where the dynamic nature of temporal graphs is ignored. Bridging
this gap, we introduce TGX, a Python package specially designed for analysis
of temporal networks that encompasses an automated pipeline for data loading,
data processing, and analysis of evolving graphs. TGX provides access to
_eleven_ built-in datasets and _eight_ external Temporal Graph Benchmark (TGB)
datasets as well as any novel datasets in the .csv format. Beyond data
loading, TGX facilitates data processing functionalities such as
discretization of temporal graphs and node sub-sampling to accelerate working
with larger datasets. For comprehensive investigation, TGX offers network
analysis by providing a diverse set of measures, including average node degree
and the evolving number of nodes and edges per timestamp. Additionally, the
package consolidates meaningful visualization plots indicating the evolution
of temporal patterns, such as Temporal Edge Appearance (TEA) and Temporal Edge
Traffic (TET) plots. The TGX package is a robust tool for examining the
features of temporal graphs and can be used in various areas like studying
social networks, citation networks, and tracking user interactions. We plan to
continuously support and update TGX based on community feedback. TGX is
publicly available on: https://github.com/ComplexData-MILA/TGX.

Temporal Graphs, Network Analysis, Network Statistics

††copyright: acmcopyright††journalyear: 2024††doi:
XXXXXXX.XXXXXXX††conference: The 17th ACM International Conference on Web
Search and Data Mining; March 4th-8th, 2024; Merida,Yucatan,Mexico††price:
15.00††isbn: 978-1-4503-XXXX-X/18/06††journalyear: 2024††copyright:
acmlicensed††conference: Proceedings of the 17th ACM International Conference
on Web Search and Data Mining; March 4–8, 2024; Merida, Mexico††booktitle:
Proceedings of the 17th ACM International Conference on Web Search and Data
Mining (WSDM ’24), March 4–8, 2024, Merida, Mexico††price: 15.00††doi:
10.1145/3616855.3635694††isbn: 979-8-4007-0371-3/24/03††ccs: Networks Network
algorithms††ccs: Networks Network structure

##  1\. Introduction

Figure 1. Overview of TGX main modules including data-loader, data processing,
visualization, and statistics.

Recent advances in graph-based data mining has shown promising applications in
different areas, such as Web data analysis, air/road traffic monitoring, and
epidemic modelling. This is mostly due to the recent advancements in graph
representation learning where powerful models have been developed for
prediction tasks on graphs (Xu et al., 2018). There are also commonly used
packages for training and benchmarking different graph learning models such as
PyTorch Geometric (Fey and Lenssen, 2019), DGL (Wang et al., 2019) and
StellarGraph (Data61, 2018). The main library currently used for visualization
and study of patterns of graphs is Networkx (Hagberg et al., 2008) on which
DGL and PyTorch Geometric packages are dependent for statistics and
visualization utilities.

Even though real-world networks typically change over time, the majority of
existing literature and tools predominantly concentrate on static graphs.
While analyzing static graphs is computationally less demanding in terms of
determining statistical and algebraic properties as well as in applying
machine learning models, using this static perspective results in loss of
important time related features and events. For example, in epidemic modeling,
the chronological order of contacts is vital in disease propagation, while
static networks assume that all the contacts happen at once.

Therefore, there are recent efforts to extend graph learning methods to
temporal graphs where the structure and attributes of graph elements are
changing over time (Kazemi et al., 2020). Several temporal graph learning
benchmarking suits have been developed for assessing TG methods, mainly
PyThorch Geometric Temporal (Rozemberczki et al., 2021), DyGLib (Yu et al.,
2023), and TGB (Huang et al., 2023). While these packages facilitate method
evaluation and development with easy benchmarking, they are not essentially
designed for providing comprehensive statistical analysis or visualizations
for deeper understanding of temporal graph characteristics. This holds
significant importance in the context of model design, particularly in the
incorporation of temporal patterns within datasets in addition to the
comprehensive analysis of their scalability, efficiency, and interpretability.

Table 1. Complete list of built-in and port-in datasets in TGX with their
computed statistics.

| Dataset | Domain | Nodes | Total Edges | Unique Edges | Timestamp | Duration | Unique Steps | Reoccurrence | Surprise | Node Activity | Novelty | Disc.
---|---|---|---|---|---|---|---|---|---|---|---|---|---
Built-in | Reddit | Social | 10,984 | 627,447 | 78,516 | Unix | 1 month | 669,065 | 0.250 | 0.280 | 0.617 | 0.266 | daily
MOOC | Interaction | 7,144 | 411,749 | 178,443 | Unix | 1 months | 345,600 | 0.044 | 0.786 | 0.161 | 0.755 | daily
LastFM | Interaction | 1,980 | 1,293,103 | 154,993 | Unix | 4 years | 1,283,614 | 0.226 | 0.369 | 0.630 | 0.332 | monthly
Enron | Social | 184 | 125,235 | 3,125 | Unix | 3 years | 22,632 | 0.255 | 0.369 | 0.409 | 0.322 | monthly
Social Evo. | Proximity | 74 | 2,099,519 | 4,486 | Unix | 8 months | 565,932 | 0.401 | 0.027 | 0.806 | 0.127 | weekly
UCI | Social | 1,899 | 59,835 | 20,296 | Unix | 196 days | 58,911 | 0.037 | 0.796 | 0.177 | 0.651 | weekly
Flights | Transport | 13,169 | 1,927,145 | 395,072 | days | 4 months | 122 | 0.265 | 0.400 | 0.348 | 0.194 | daily
Can. Parl. | Politics | 734 | 74,478 | 51,331 | years | 14 years | 14 | 0.063 | 0.654 | 0.458 | 0.673 | yearly
US Legis. | Politics | 225 | 60,396 | 26,423 | congress | 12 cong. | 12 | 0.173 | 0.475 | 0.448 | 0.437 | yearly
UN Vote | Politics | 201 | 1,035,742 | 31,516 | years | 72 years | 72 | 0.869 | 0.027 | 0.709 | 0.056 | yearly
Contact | Proximity | 694 | 2,426,280 | 79,530 | 5 minutes | 1 month | 8,065 | 0.232 | 0.289 | 0.698 | 0.422 | daily
TGB | tgbl-wiki | Social | 9,227 | 157,474 | 18,257 | Unix | 1 month | 152,757 | 0.130 | 0.554 | 0.160 | 0.475 | daily
tgbl-review | Rating | 352,637 | 4,873,540 | 4,730,223 | Unix | 22 years | 6,865 | 0.0004 | 0.999 | 0.249 | 0.999 | yearly
tgbl-coin | Transaction | 638,486 | 22,809,486 | 3,862,031 | Unix | 8 months | 1,295,720 | 0.129 | 0.435 | 0.233 | 0.430 | weekly
tgbl-comment | Social | 994,790 | 44,314,507 | 35,531,704 | Unix | 5 years | 30,998,030 | 0.006 | 0.964 | 0.054 | 0.910 | monthly
tgbl-flight | Transport | 18,143 | 67,169,570 | 2,309,707 | Unix | 3 years | 1,385 | 0.295 | 0.363 | 0.652 | 0.258 | monthly
tgbn-trade | Trade | 255 | 507,497 | 34,211 | year | 32 years | 32 | 0.702 | 0.088 | 0.868 | 0.091 | yearly
tgbn-genre | Interaction | 992 | 17,858,395 | 133,758 | Unix | 4 years | 133,758 | 0.411 | 0.246 | 0.594 | 0.189 | monthly
tgbn-reddit | Social | 11,068 | 27,174,118 | 516,669 | Unix | 3 years | 21,889,537 | 0.465 | 0.211 | 0.614 | 0.211 | monthly

In this work, we introduce TGX, a Python package designed for analysis and
visualization of temporal graphs. TGX builds upon our prior work (Poursafaei
et al., 2022), further extending it to enhance the evaluation and analysis
process for learning on temporal graphs. Here, we package the Temporal Edge
Appearance (TEA) and Temporal Edge Traffic (TET) plots, which are essential
for investigating evolutionary patterns of temporal graph datasets. In
addition, we utilize time discretization as a means to control the trade-off
between the computational complexity involved in generating these plots and
the richness of information they offer. We also facilitate easy access to
eleven commonly used small/medium-scale datasets provided in (Poursafaei et
al., 2022), as well as eight large-scale Temporal Graph Benchmarks (TGB)
(Huang et al., 2023). TGX is designed to complement the benchmarking package
that we recently introduced in TGB (Huang et al., 2023), providing researchers
with enhanced capabilities to comprehensively explore and analyze temporal
patterns within these datasets and beyond.

##  2\. Temporal Graph Preliminaries

Temporal graphs are often categorized into Continuous Time Dynamic Graphs
(CTDGs) and Discrete Time Dynamic Graphs (DTDGs) (Kazemi et al., 2020). CTDGs
are considered to be the most general format of temporal graphs and can be
discretized into DTDGs (Souza et al., 2022). In TGX, the input is a CTDG and
it supports the conversion from CTDGs into DTDGs by discretization as
explained in Section 3.2.

CTDGs are often represented as an edge-list in the form of
$\mathbf{G}=\\{(u_{1},v_{1},t_{1}),(u_{2},v_{2},t_{2}),...\\}$ where edges are
sorted based on timestamps, i.e., $0\leq t_{1}\leq t_{2}\leq...\leq T$ with
$T$ being the maximum timestamp in the dataset. Within a certain time interval
$[t_{a},t_{b}]$, a CTDG can be discretized into a cumulative graph snapshot
$\mathcal{G}_{t_{a},t_{b}}$ constructed from all edges in the stream with
timestamps $t$ where $t_{a}\leq t\leq t_{b}$ with nodes
$\mathcal{V}_{t_{a},t_{b}}$ and edges $\mathcal{E}_{t_{a},t_{b}}$. In this
way, one can evenly divide the interval $[t_{1},T]$ into $k$ equal size
intervals, thus creating a sequence of graph snapshots and forming the DTDG
$\mathcal{G}$ discretized from the CTDG $\mathbf{G}$ where
$\mathcal{G}=\\{\mathcal{G}_{t}\\}_{t=1}^{k}=\\{(\mathcal{V}_{t},\mathbf{E}_{t})\\}_{t=1}^{T}$.
For clarity, we omit the $[t_{a},t_{b}]$ subscripts when describing DTDGs as
each snapshot is from an equal size interval.

##  3\. Features

###  3.1. Temporal Graph Loader

TGX provides access to temporal graph datasets and benchmarks. Users can
either load their custom datasets into the package or take advantage of built-
in or ported datasets. Custom datasets can be loaded by providing the temporal
edge-list of graphs, containing triplets of source, destination and timestamp.
The edge-list can be loaded through the command read_edgelist. A complete list
of currently built-in and port-in datasets and some of their important
statistical properties are presented in Table 1.

Built-in datasets. TGX offers access to eleven built-in datasets from
(Poursafaei et al., 2022). These datasets are from different domains with
various sizes and can be useful in temporal graph learning. These datasets can
be directly loaded; for example, the MOOC dataset can be loaded via command
tgx.builtin.mooc.

Porting-in TGB datasets. The second group of temporal graph datasets that can
be loaded through TGX are the TGB (Huang et al., 2023) datasets. This
collection includes eight temporal graph datasets from various domains and
sizes, containing two medium-sized datasets with 5-25 million edges, and three
large-sized datasets with over 25 million edges. As an example, the command
tgx.tgb_data(“tgbl-wiki”) can be used for importing the wikipedia dataset via
TGB package.

###  3.2. Time Discretization

In temporal graphs, edges often arrive continuously with unique timestamps,
potentially resulting in millions of timestamps. To effectively visualize the
high-level information of a temporal graph, discretization might be necessary.
In TGX, users can specify their discretization preferences by specifying the
desired time interval for the discretized data. Discretization intervals can
be provided in two ways. The first option allows users to choose from time
granularities such as specifying “daily”, “weekly”or “monthly”. In this case,
it is assumed that the timestamps adhere to the Unix timestamp format.
Alternatively, users can provide the number of bins as an integer, specifying
the number of time slices where the entire time duration will be divided into
equal time intervals. In this scenario, the timestamp unit is irrelevant.
Discretization is performed directly on tgx.Graph object with the function
Graph.discretize. Note that the downside of discretization is the loss of
information resulting from grouping multiple edges with fine-grained
timestamps into a single coarse-grained timestamp.

###  3.3. Graph Sub-sampling

In large graphs with millions of nodes, generating dataset statistics or
visualization often proves challenging. A common approach is to sample a
subset of nodes to represent the graph. In TGX, sub-sampling can be performed
on the datasets by either providing a list of nodes or specifying number of
nodes to be randomly chosen by using the function subsampling. The sub-sampled
graph will only include edges where either the source or destination node is
in the selected node set.

###  3.4. Temporal Graph Statistics

When analyzing or experimenting on temporal graph data, it is essential to
have access to important statistical attributes in order to gain a better
understanding and more effective use of the data. TGX provides several tools
that are helpful in the statistical analysis of temporal graphs. A discretized
graph should be provided as input.

Total number of nodes/edges over time. The total number of nodes and edges
over time is important in understanding the evolving nature of temporal graphs
and the changes in their structure through time. For instance, Figure 2 shows
the total number of nodes and edges per timestamp for the MOOC dataset. In
this visualization, the data is discretized into 30 intervals.

Figure 2. Example plot illustrating the total number of nodes and edges per
timestamp in the MOOC dataset discretized into 30 time intervals.

Average node activity. Average node activity quantifies the average proportion
of timestamps during which a node is present within a temporal network (Spasov
et al., 2020). This metric reveals the degree of temporal activity of nodes.
In Table 1, we report the average node activity for the built-in and ported
TGB datasets discretized as specified.

Average node degree over time. The visualization of the average node degree
over time offers insight into the activity levels of nodes within the network.
Figure 3 shows the average degree per timestamp in the MOOC dataset
discretized into three different numbers of bins namely 10, 50, and 100.
Notably, an increase in the number of bins corresponds to a decrease in the
average degree, accompanied by more fluctuations in the trend.

Figure 3. The average node degree per timestamp plots for the MOOC dataset,
discretized into 10, 50 and 100 intervals. The red line indicates the average
degree over all timestamps.

###  3.5. Temporal Patterns

While temporal graphs share similarities with static graphs, conducting graph
learning on temporal graphs necessitates extra metrics to ensure a robust
evaluation. In this regard, TGX provides access to Temporal Edge Appearance
(TEA) and Temporal Edge Traffic (TET) plots as visualizations of edge dynamics
as well as three metrics namely novelty, reoccurrence and surprise indices
which are introduced in (Poursafaei et al., 2022).

Figure 4. TEA plot examples for (a) LastFM and (b) Social Evo. datasets,
discretized monthly and weekly, respectively.

Temporal Edge Appearance (TEA). TEA plots illustrate the portion of repeated
edges and newly observed edges in each timestamp. In TGX, TEA plots can be
generated using the command tgx.TEA. Figure 4 shows TEA plots for the LastFM
and Social Evo. datasets discretized based on monthly and weekly timestamps,
respectively. These visualizations display different temporal patterns in
these datasets. As shown in Figure 4, LastFM contains several new edges at
each timestamp, while in Social Evo., edges are mostly repeated after the
first few timestamps. TEA plots can play a key role in selecting the best
method for the dynamic link prediction task. Particularly, the emergence of
many new edges at each timestamp results in the failure of memorization
approaches.

Figure 5. TET plot examples for (a) LastFM and (b) Social Evo. datasets,
discretized monthly and weekly respectively.

Temporal Edge Traffic (TET). TET plots illustrate the reoccurrence pattern of
edges over time intervals. They provide more insights into the edge repetition
pattern and sparsity of the network. TET plots are accessible through tgx.TET
in the TGX package. Figure 5 shows the TET plots for the LastFM and Social
Evo. datasets, revealing temporal patterns in these datasets. Notably, in the
Social Evo. dataset, a significant portion of edges repeats over time, also
periods of inactivity can be observed. Figure 6 shows TET plots for the tgbn-
reddit dataset. In Figure 6.a, the data is discretized into 10 intervals,
whereas, figure 6.b displays the same dataset discretized into 50 intervals,
along with graph sub-sampling involving 1000 randomly selected nodes. Both
discretization and sub-sampling changes the appearance of TET plots.

Novelty, Reoccurrence and Surprise. These indices were originally introduced
in (Poursafaei et al., 2022) to quantify the patterns observed in TEA and TET
plots. The first index, novelty, measures the average proportion of new edges
at each timestamp and is defined as
$\textit{novelty}=\frac{1}{T}\sum_{t=1}^{T}\frac{|\mathbf{E}^{t}\backslash\mathbf{E}^{t}_{seen}|}{|\mathbf{E}^{t}|}$,
where $\mathbf{E}^{t}$ is the set of edges at timestamp $t$, and
$\mathbf{E}^{t}_{seen}$ stands for all edges seen in the previous timestamps.
The other two indices, reoccurrence and surprise, quantitatively assess
whether edges appear repetitively or disappear after a certain time period,
respectively. The formulation of these indices are as
$\textit{reoccurrence}=\frac{|\mathbf{E}_{train}\bigcap\mathbf{E}_{test}|}{|\mathbf{E}_{train}|}$
and
$\textit{surprise}=\frac{|\mathbf{E}_{test}\backslash\mathbf{E}_{train}|}{|\mathbf{E}_{test}|}$,
where $\mathbf{E}_{train}$ and $\mathbf{E}_{test}$ correspond to edges present
in the train and test set, respectively. These indices are reported for the
built-in and ported datasets in Table 1. For calculation of novelty, datasets
have been discretized to the mentioned interval size in Table 1. These
measures provide a more profound insight into a network’s temporal
characteristics. For instance, performing link prediction on datasets with
high novelty might be more complex as a simple memorization approach might not
be helpful with the predictions. For more details on these measures, please
refer to (Poursafaei et al., 2022).

Figure 6. TET plot examples for tgbn-reddit dataset. (a) Data discretized into
10 intervals. (b) Sub-sampled graph from 1000 random nodes, discretized into
50 intervals.

##  4\. Conclusion

In summary, TGX provides access to various tools for network analysis and
visualization of temporal graphs characteristics. TGX can be utilized in a
wide range of temporal graph learning tasks, facilitating the examination of
temporal patterns. More information and discussion can be found on the project
Github repository.

## Acknowledgment

This research was supported by the Canadian Institute for Advanced Research
(CIFAR AI chair program), Natural Sciences and Engineering Research Council of
Canada (NSERC) Postgraduate Scholarship-Doctoral (PGS D) Award and Fonds de
recherche du Québec - Nature et Technologies (FRQNT) Doctoral Award. We would
like to thank Samsung Electronics Co., Ldt. for partially funding this
research.

## References

  * (1)
  * Data61 (2018) CSIRO’s Data61. 2018.  StellarGraph Machine Learning Library.  https://github.com/stellargraph/stellargraph.
  * Fey and Lenssen (2019) Matthias Fey and Jan Eric Lenssen. 2019.  Fast graph representation learning with PyTorch Geometric.  _arXiv preprint arXiv:1903.02428_ (2019).
  * Hagberg et al. (2008) Aric Hagberg, Pieter Swart, and Daniel S Chult. 2008.  _Exploring network structure, dynamics, and function using NetworkX_.  Technical Report. Los Alamos National Lab.(LANL), Los Alamos, NM (United States).
  * Huang et al. (2023) Shenyang Huang, Farimah Poursafaei, Jacob Danovitch, Matthias Fey, Weihua Hu, Emanuele Rossi, Jure Leskovec, Michael Bronstein, Guillaume Rabusseau, and Reihaneh Rabbany. 2023.  Temporal graph benchmark for machine learning on temporal graphs.  _Advances in Neural Information Processing Systems_ (2023).
  * Kazemi et al. (2020) Seyed Mehran Kazemi, Rishab Goel, Kshitij Jain, Ivan Kobyzev, Akshay Sethi, Peter Forsyth, and Pascal Poupart. 2020.  Representation learning for dynamic graphs: A survey.  _The Journal of Machine Learning Research_ 21, 1 (2020).
  * Poursafaei et al. (2022) Farimah Poursafaei, Shenyang Huang, Kellin Pelrine, and Reihaneh Rabbany. 2022.  Towards better evaluation for dynamic link prediction.  _Advances in Neural Information Processing Systems_ 35 (2022), 32928–32941.
  * Rozemberczki et al. (2021) Benedek Rozemberczki, Paul Scherer, Yixuan He, George Panagopoulos, Alexander Riedel, Maria Astefanoaei, Oliver Kiss, Ferenc Beres, , Guzman Lopez, Nicolas Collignon, and Rik Sarkar. 2021.  PyTorch Geometric Temporal: Spatiotemporal Signal Processing with Neural Machine Learning Models. In _Proceedings of the 30th ACM International Conference on Information and Knowledge Management_.
  * Souza et al. (2022) Amauri Souza, Diego Mesquita, Samuel Kaski, and Vikas Garg. 2022.  Provably expressive temporal graph networks.  _Advances in Neural Information Processing Systems_ 35 (2022), 32257–32269.
  * Spasov et al. (2020) Simeon Spasov, Alessandro Di Stefano, Pietro Lio, and Jian Tang. 2020.  Grade: Graph Dynamic Embedding.  _arXiv preprint arXiv:2007.08060_ (2020).
  * Wang et al. (2019) Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, et al. 2019\.  Deep graph library: A graph-centric, highly-performant package for graph neural networks.  _arXiv preprint arXiv:1909.01315_ (2019).
  * Xu et al. (2018) Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2018.  How Powerful Are Graph Neural Networks?  _arXiv preprint arXiv:1810.00826_ (2018).
  * Yu et al. (2023) Le Yu, Leilei Sun, Bowen Du, and Weifeng Lv. 2023.  Towards Better Dynamic Graph Learning: New Architecture and Unified Library.  _arXiv preprint arXiv:2303.13047_ (2023).