Finding use cases for GPMA and PCSR

[JoelMathewC]

Seastar has dynamic graph support via Naive which can compete with PyG-T. But GPMA and PCSR performs much slower in comparison. However, GPMA and PCSR provide seastar with a data structure to represent dynamic graphs. This discussion will evaluate whether there is some use case where GPMA and PCSR will come in handy.

Possible areas are

1. Allow seastar to compile models that packages like PyG-T cant build.
2. Allow Seastar to process models and not go out of memory on certain datasets in comparison to PyG-T

[JoelMathewC]

Overall Idea

The following reference can be followed to understand the state of research of Temporal GNNs at the present.
Reference https://towardsdatascience.com/temporal-graph-learning-in-2023-d28d1640dbf2

Temporal Graph Networks is a system for training dynamic graphs. It might be possible to implement a TGN using seastar. We will however have to look at the validity of that.

TGN Reference https://towardsdatascience.com/temporal-graph-networks-ab8f327f2efe

[JoelMathewC]

Thinking about this logically

Think about the case where base graph is sufficiently large and the we have small batch updates and many timestamps of those updates. Naturally, a naive approach would have to store too many graphs in memory or would struggle with updating the base graph because its not optimized for insertions. So ideally the only way to perform better is to be more memory efficient on the GPU.

[JoelMathewC]

PyGT

TGL said the following about PyGT

Recently, PyTorch Geometric Temporal (PyGT) [16] attempted to design a library for dynamic and temporal geometric deep learning
on top of PyG. However, PyGT only supports discrete time snapshot-based method and full batch training on small-scale spatial-
temporal graphs.

[JoelMathewC]

This raises the question of whether Seastar can support

1. continuous time snapshot based methods
2. support mini batch training

[JoelMathewC]

CTDG and DTDG

Reference https://arxiv.org/pdf/1905.11485.pdf
CTDG Continuous time dynamic graph
DTDG Discrete time dynamic graph

[JoelMathewC]

The TGN paper states the following

Learning on dynamic graphs is relatively recent, and most works are limited to the setting of discrete-time dynamic graphs
represented as a sequence of snapshots of the graph. Such approaches are unsuitable for interesting real world settings such as social 
networks, where dynamic graphs are continuous (i.e. edges can appear at any time)

It may be noted that TGN is for continuous dynamic graphs.

[JoelMathewC]

Reference https://aclanthology.org/2022.dlg4nlp-1.3.pdf
This paper discusses the different representations of dynamic graph data

[JoelMathewC]

Where we are at right now

Based on the research done so far we can come to the following conclusions

1. Naive can be rebranded as Discrete for DTDG (PyGT only supports discrete so GPMA and PCSR need not be pitted against PyG-T)
2. PCSR and GPMA could be used for CTDG.
3. Additionally if this pans out we can make a continuos and discrete that inherits from dynamic graph. Also PCSR and GPMA inherits from continuous.

[JoelMathewC]

TGN

TGN uses a batch updates to update the base graph and perform some learning on it. However, even this case basically follows the same logic of building graphs from the base graph. In such cases using discrete snapshots as in Naive will provide the best performance. PCSR and GPMA will perform slowly because of the need label edge ids and move to the GPU.

The same fundamental problems with the original approach still remain.

[JoelMathewC]

Looking back

Maybe we should think about this from a solely discrete perspective. Lets do the math

Number of nodes (N): 2,500,000
Number of edges (E): 62,000,000

Say we have a 1000 timestamps

Number of edges for base graph (E_base): 15,000,000

graph storage: (2,500,000 + 2 * 62,000,000) * 2
= 253,000,000

CASE 1: node features

Size of node feature: 100
Total size of node features: 200,500,000

CASE 2: edge features

Size of edge features: 100
Total Size of edge features: 6,200,000,000

Basically the bottom line is that when it comes to comparing graph storage with feature vector size. When node feature vectors are in the picture graph storage is important. But in comparison to edge feature vectors they lose their importance.

[JoelMathewC]

Things that are not understood

1. How are dynamic graph data batched
2. what are we making predictions for

[JoelMathewC]

Closing this out since #53 did discover benefits for GPMA. PCSR however did not come to par with using GPU based data structures that performed extremely well for batched updates.