jasperzhong
commented
2 years ago Dynamic Graphs
- Continuous-time dynamic graphs (CTDG): 用(G, O)表示，G是初始图，O是事件集合，每个事件用 (event type, event, timestamp)表示. 事件类型可以是增删边/节点. 在任何一个时间点t，都可以通过replay events来得到时间点t对应的snapshot G_t.
- Discrete-time dynamic graphs (DTDG): 用{G_1, G_2, ..., G_T}表示. 每个snapshot G_t = {V_t, E_t}.
显然相比CTDG，DTDG是lose information，但研究DTDG模型比较简单. 而survey说为CTDG开发的模型也可以用于DTDG，反之不成立. （感觉需要考证下）
Prediction Tasks
任务基本还是常规的任务：node classification, edge prediction, graph classification.
但Dynamic Graph又有不一样的地方，分两种interpolation和extrapolation. 如果给定的图信息是[t_0, t_T]，
- interpolation problem: 对时间t做预测，t_0 < t < t_T. 主要用来completing缺失的信息.
- extrapolation problem: 对t >= t_T的时间点做预测，即根据过去预测未来 .
还有一个场景是streaming. 新的events不断地stream到模型，模型需要real-time更新，这样它能在每个event达到后立刻做出predictions. 对于这种场景，模型是没有办法立刻就retrain的. 这个场景一般适合CTDG，并且适合extrapolation problems.
encoder-decoder framework
graph -> encoder -> node embeddings -> decoder -> prediction
感觉没什么...只不过这里的node embedding除了node representation之外，还可以包括其他的东西.
sequence models
dynamic环境下，数据总是包括变长的sequence of events. 所以一般用RNN或者self-attention方法.
temporal point processes
给定一系列发生过的事件发生在t_1, t_2, ...for t_i <= T，TPP一般表示为用一个条件密度函数\lambda(t)，\lambda(t)dt表示下一个事件发生在[t, t+dt]发生的概率.
传统上intensity functions有很多hand-designed model. 后来流行用ML方法来学习. 在dynamic graphs的context下，TPP的intensity function用node representations来parameterized，被用来构建预测什么时候某件事会发生在某个节点或者一对节点上.
https://arxiv.org/pdf/1905.11485.pdf
引用量87