paper：Dynamic graph representation learning with neural networks: a survey

我们根据处理时间和结构信息的策略对不同的嵌入方法进行了分类。

1. 动态图嵌入

1.1 discrete time transductive settings

对于discrete time transductive settings,case (1)、(2)，当节点集为常数时，输入节点可以在最细粒度$Z\in R^{|V|\times |T|\times d}$进行编码，因为所有的节点在学习过程中都是已知的.

当DTDG节点集在 transductive settings( (即对于情形( 3 )) )的快照中发生变化时，节点仍然可以被编码为| V | × | T | × d的形式，其中| V |表示通用节点集的基数，通过用0向量或最新更新的节点嵌入来填充缺失值。用0向量填充缺失值的例子，如图6 ( A )所示，节点C在t1时刻，节点A在t3时刻。

1.2 discrete time inductive settings

对于discrete time inductive settings(即,对于情形( 4 ))和( 5 ) )，预测器不能确定节点的存在，直到它第一次出现。其中预测器不能确定节点C的存在性，直到它出现在t4。因此，| Vt |可以在每个时间步t变化.因此，推断集中节点的嵌入不能用| V | × | T | × d的形式表示。在这种情况下，现有的方法使用不同大小的隐藏状态矩阵列表来存储每个节点的所有可访问时间步的表示，例如。Z = { Z1，Z2，…，Zt }，对于T∈{ 1，…，t }，Zt∈R | Vt | × D。

1.3 continuous time

在连续时间内，不再有一个时间网格，如图6 ( C & D)所示。因此，在每个时间步中不再对所有节点进行嵌入更新。相反，当CTDG上发生事件时，要么更新关联节点的嵌入，要么增加不可见节点的嵌入。

//

分类法基于同时处理时间和结构信息的策略。这导致了图7所示的5个类别。然后描述第六类，对应于混合了前一类思想的最近的transformer模型：
1 )通过面向节点的ESG对时序边进行建模，记为TE 。
2 )对隐藏状态进行顺序编码，记为enc ( H )。
3 )对DGNN参数进行顺序编码，记为enc (Θ) 。
4 )将发生时间t嵌入为面向边缘的ESG的边缘特征，记为emb ( t ) 。
5 )采样因果随机游走( RWs )，记为CausalRW 。
6 )动态图变换，记为DGT。

2. TEMPORAL EDGE MODELING（TE）

DG编码问题经常被转化为编码一个静态图，其中每个节点在相邻的快照中与自己相连，叫TE。这种方法也可以解释为构建一个时间扩展图或面向节点的ESG，并被广泛用于编码Trans -fix_(V，E)情况，即"时空图"或"时空图" ( STGs )。在更复杂的配置中，节点也与其相邻快照中的k跳邻居相连。

经典模型：ST-GCN、STSGCN、TSNet、Cola-GNN
相关论文：
Long-range transformers for dynamic spatiotemporal forecasting
Adaptive graph spatial–temporal transformer network for traffic flow forecasting
Spatial–temporal synchronous graph transformer network (STSGT) for COVID-19 forecasting
VDGCNeT: A novel network-wide virtual dynamic graph convolution neural network and transformer-based traffic prediction model

3. SEQUENTIALLY ENCODING HIDDEN STATES H

该类别记为enc ( H )，使用fG ( · )和fT ( · )交替对图域和时间域进行编码。Enc ( H )被广泛应用于Trans -fix(V，E)情形，即。STGs 和DTDGs上的Transfix_V案例 . fT ( · )要么在fG ( · )编码每个快照之后，以堆叠的方式编码每个快照，要么在编码每个跨时间快照时，以集成的方式编码每个快照。

相关论文：

1. B. Yu, H. Yin, and Z. Zhu, ‘‘Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting,’’ 2017, arXiv:1709.04875.
2. Y. Li, R. Yu, C. Shahabi, and Y. Liu, ‘‘Diffusion convolutional recurrent neural network: Data-driven traffic forecasting,’’ 2017, arXiv:1707.01926.
3. A. Kapoor, X. Ben, L. Liu, B. Perozzi, M. Barnes, M. Blais, and S. O’Banion, ‘‘Examining COVID-19 forecasting using spatio-temporal graph neural networks,’’ 2020, arXiv:2007.03113.
4. A GNN-RNN approach for harnessing geospatial and temporal information: Application to crop yield prediction
5. Z. Jia, Y. Lin, J. Wang, R. Zhou, X. Ning, Y. He, and Y. Zhao, ‘‘GraphSleepNet: Adaptive spatial–temporal graph convolutional networks for sleep stage classification,’’ in Proc. 29th Int. Joint Conf. Artif. Intell., Jul. 2020, pp. 1324–1330.
6. S. Guo, Y. Lin, N. Feng, C. Song, and H. Wan, ‘‘Attention based spatialtemporal graph convolutional networks for traffic flow forecasting,’’ in Proc. AAAI Conf. Artif. Intell., vol. 33, no. 1, 2019, pp. 922–929.
7. D. Xu, W. Cheng, D. Luo, X. Liu, and X. Zhang, ‘‘Spatio-temporal attentive RNN for node classification in temporal attributed graphs,’’ in Proc. 28th Int. Joint Conf. Artif. Intell., Aug. 2019, pp. 3947–3953.
8. Y. Fan, M. Ju, C. Zhang, and Y. Ye, ‘‘Heterogeneous temporal graph neural network,’’ in Proc. SIAM Int. Conf. Data Mining (SDM), 2022, pp. 657–665.
9. A. Nicolicioiu, I. Duta, and M. Leordeanu, ‘‘Recurrent space-time graph neural networks,’’ in Proc. Adv. Neural Inf. Process. Syst., 2019, pp. 12838–12850.
10. Dynamic regions graph neural networks for spatio-temporal reasoning
11. Learning dynamic graph representation of brain connectome with spatio-temporal attention
12. L. Yang, Z. Xiao, W. Jiang, Y. Wei, Y. Hu, and H. Wang, ‘‘Dynamic heterogeneous graph embedding using hierarchical attentions,’’ in Proc. Eur. Conf. Inf. Retr. Cham, Switzerland: Springer, 2020, pp. 425–432.
13. J. Chen, J. Zhang, X. Xu, C. Fu, D. Zhang, Q. Zhang, and Q. Xuan, ‘‘E-LSTM-D: A deep learning framework for dynamic network link prediction,’’ IEEE Trans. Syst. Man, Cybern. Syst., vol. 51, no. 6, pp. 3699–3712, Jun. 2021.
14. Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting
15. On the equivalence between temporal and static equivariant graph representations
16. Y. Seo, M. Defferrard, P. Vandergheynst, and X. Bresson, ‘‘Structured sequence modeling with graph convolutional recurrent networks,’’ in Proc. Int. Conf. Neural Inf. Process. Cham, Switzerland: Springer, 2018, pp. 362–373.
17. J. Chen, X. Wang, and X. Xu, ‘‘GC-LSTM: Graph convolution embedded LSTM for dynamic link prediction,’’ 2018, arXiv:1812.04206.
18. Y. Wang, P. Li, C. Bai, V. Subrahmanian, and J. Leskovec, ‘‘Generic representation learning for dynamic social interaction,’’ in Proc. 26th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining Workshop, 2020, pp. 1–9.
19. J. Choi, T. Ko, Y. Choi, H. Byun, and C.-K. Kim, ‘‘Dynamic graph convolutional networks with attention mechanism for rumor detection on social media,’’ PLoS ONE, vol. 16, no. 8, Aug. 2021, Art. no. e0256039.

4. SEQUENTIALLY ENCODING PARAMETERS THETA

尽管enc ( H )在模型结构方面相对直观和简单，但存在的问题是它们不能处理节点集的频繁变化，特别是在归纳任务中，也不能跨时间步传递fG ( · )的学习参数[ 3 ]。为了更灵活地编码DTDGs，一些其他方法限制或编码跨时间步的fG ( · )的参数。

相关论文：

20. P. Goyal, N. Kamra, X. He, and Y. Liu, ‘‘DynGEM: Deep embedding method for dynamic graphs,’’ 2018, arXiv:1805.11273.

21. E. Hajiramezanali, A. Hasanzadeh, K. Narayanan, N. Duffield, M. Zhou, and X. Qian, ‘‘Variational graph recurrent neural networks,’’ in Proc. Adv. Neural Inf. Process. Syst., 2019, pp. 1–2.

22. A. Pareja, ‘‘EvolveGCN: Evolving graph convolutional networks for dynamic graphs,’’ in Proc. AAAI Conf. Artif. Intell., 2020, pp. 5363–5370.

5. TIME EMBEDDING

时间嵌入当动态图的规模较大时，如在社交网络和推荐系统中，聚合到快照既不精确也不高效。这样的DG就用一组时间戳事件来表示。因此，当编码一个CTDG时，应该不仅考虑如何随时间异步更新节点表示，还要定义节点的邻居。
3. L. Qu, H. Zhu, Q. Duan, and Y. Shi, ‘‘Continuous-time link prediction via temporal dependent graph neural network,’’ in Proc. Web Conf., Apr. 2020, pp. 3026–3032.
4. A. Sankar, Y. Wu, L. Gou, W. Zhang, and H. Yang, ‘‘DySAT: Deep neural representation learning on dynamic graphs via self-attention networks,’’ in Proc. 13th Int. Conf. Web Search Data Mining, Jan. 2020, pp. 519–527.
5. J. Gehring, M. Auli, D. Grangier, D. Yarats, and Y. N. Dauphin, ‘‘Convolutional sequence to sequence learning,’’ in Proc. 34th Int. Conf. Mach. Learn., vol. 70. Sydney, NSW, Australia: International Convention Centre, Aug. 2017, pp. 1243–1252.
6. X. Chang, X. Liu, J. Wen, S. Li, Y. Fang, L. Song, and Y. Qi, ‘‘Continuoustime dynamic graph learning via neural interaction processes,’’ in Proc. 29th ACM Int. Conf. Inf. Knowl. Manage., Oct. 2020, pp. 145–154.
7. J. Grigsby, Z. Wang, N. Nguyen, and Y. Qi, ‘‘Long-range transformers for dynamic spatiotemporal forecasting,’’ 2021, arXiv:2109.12218.
8. A. Feng and L. Tassiulas, ‘‘Adaptive graph spatial–temporal transformer network for traffic flow forecasting,’’ 2022, arXiv:2207.05064.
9. S. Banerjee, M. Dong, and W. Shi, ‘‘Spatial–temporal synchronous graph transformer network (STSGT) for COVID-19 forecasting,’’ Smart Health, vol. 26, Dec. 2022, Art. no. 100348.
10. G. Zheng, W. K. Chai, J. Zhang, and V. Katos, ‘‘VDGCNeT: A novel network-wide virtual dynamic graph convolution neural network and transformer-based traffic prediction model,’’ Knowl.-Based Syst., vol. 275, Sep. 2023, Art. no. 110676.
11. X. Chang, X. Liu, J. Wen, S. Li, Y. Fang, L. Song, and Y. Qi, ‘‘Continuoustime dynamic graph learning via neural interaction processes,’’ in Proc. 29th ACM Int. Conf. Inf. Knowl. Manage., Oct. 2020, pp. 145–154.
12. B. Kim, J. Choi, E. Yun, K. Kim, X. Li, and J. Lee, ‘‘Large-scale graph representation learning of dynamic brain connectome with transformers,’’ in Proc. Temporal Graph Learn. Workshop@ NeurIPS, 2023, pp. 1–7.
13. A.-T. Kuo, H. Chen, Y.-H. Kuo, and W.-S. Ku, ‘‘Dynamic graph representation learning for depression screening with transformer,’’ 2023, arXiv:2305.06447.
14. W. Cong, Y. Wu, Y. Tian, M. Gu, Y. Xia, M. Mahdavi, and C. Chen, ‘‘Dynamic graph representation learning via graph transformer networks,’’ in Proc. ICLR, 2021, pp. 1–11.
15. S. Wei, B. Wu, A. Xiang, Y. Zhu, and C. Song, ‘‘DGTR: Dynamic graph transformer for rumor detection,’’ Frontiers Res. Metrics Anal., vol. 7, Jan. 2023, Art. no. 1055348.
16. L. Xia, C. Huang, Y. Xu, and J. Pei, ‘‘Multi-behavior sequential recommendation with temporal graph transformer,’’ IEEE Trans. Knowl. Data Eng., vol. 35, no. 6, pp. 6099–6112, Jun. 2023.
17. Y. Fan, M. Ju, S. Hou, Y. Ye, W. Wan, K. Wang, Y. Mei, and Q. Xiong, ‘‘Heterogeneous temporal graph transformer: An intelligent system for evolving Android malware detection,’’ in Proc. 27th ACM SIGKDD Conf. Knowl. Discovery Data Mining, Aug. 2021, pp. 2831–2839.
18. M. Biparva, R. Karimi, F. Faez, and Y. Zhang, ‘‘TodyFormer: Towards holistic dynamic graph transformers with structure-aware tokenization,’’ in Proc. Temporal Graph Learn. Workshop@ NeurIPS 2023, 2023.
19. L. Wang, X. Chang, S. Li, Y. Chu, H. Li, W. Zhang, X. He, L. Song, J. Zhou, and H. Yang, ‘‘TCL: Transformer-based dynamic graph modelling via contrastive learning,’’ 2021, arXiv:2105.07944.
20. C. Song, K. Shu, and B. Wu, ‘‘Temporally evolving graph neural network for fake news detection,’’ Inf. Process. Manage., vol. 58, no. 6, Nov. 2021, Art. no. 102712.
21. D. Xu, C. Ruan, E. Korpeoglu, S. Kumar, and K. Achan, ‘‘Inductive representation learning on temporal graphs,’’ 2020, arXiv:2002.07962.
22. R. Trivedi, M. Farajtabar, P. Biswal, and H. Zha, ‘‘Dyrep: Learning representations over dynamic graphs,’’ in Proc. Int. Conf. Learn. Represent., 2019, pp. 1–25.
23. X. Wang, D. Lyu, M. Li, Y. Xia, Q. Yang, X. Wang, X. Wang, P. Cui, Y. Yang, B. Sun, and Z. Guo, ‘‘APAN: Asynchronous propagation attention network for real-time temporal graph embedding,’’ in Proc. Int. Conf. Manage. Data, Jun. 2021, pp. 2628–2638.
24. W. Cong, S. Zhang, J. Kang, B. Yuan, H. Wu, X. Zhou, H. Tong, and M. Mahdavi, ‘‘Do we really need complicated model architectures for temporal networks?’’ 2023, arXiv:2302.11636.
25. P. Lewis, ‘‘Multivariate point processes,’’ in Proc. Berkeley Symp. Math. Statist. Probab., 1972, p. 401.

6. CAUSAL RANDOM WALKS

随机移走(Random walk-based)方法不聚合节点的邻域信息，而是将节点序列采样来捕捉局部结构。为了将时间信息融入到随机游动中，我们推导了在动态图上定义"因果游动"的不同方法。

相关论文：

1. C. Huang, L. Wang, X. Cao, W. Ma, and S. Vosoughi, ‘‘Learning dynamic graph embeddings using random walk with temporal backtracking,’’ in Proc. NeurIPS Temporal Graph Learn. Workshop, 2022.
2. K. Sato, M. Oka, A. Barrat, and C. Cattuto, ‘‘DyANE: Dynamics-aware node embedding for temporal networks,’’ 2019, arXiv:1909.05976.
3. G. H. Nguyen, J. B. Lee, R. A. Rossi, N. K. Ahmed, E. Koh, and S. Kim, ‘‘Continuous-time dynamic network embeddings,’’ in Proc. Companion Web Conf. Web Conf. (WWW), 2018, pp. 969–976.
4. S. Khoshraftar, S. Mahdavi, A. An, Y. Hu, and J. Liu, ‘‘Dynamic graph embedding via LSTM history tracking,’’ in Proc. IEEE Int. Conf. Data Sci. Adv. Anal. (DSAA), Oct. 2019, pp. 119–127.
5. D. Lin, J. Wu, Q. Yuan, and Z. Zheng, ‘‘T-EDGE: Temporal WEighted MultiDiGraph embedding for Ethereum transaction network analysis,’’ Frontiers Phys., vol. 8, p. 204, Jun. 2020.
6. M. Jin, Y. Li, and S. Pan, ‘‘Neural temporal walks: Motif-aware representation learning on continuous-time dynamic graphs,’’ in Proc. Adv. Neural Inf. Process. Syst., 2022, pp. 19874–19886.

7. DYNAMIC GRAPH TRANSFORMERS

作为最初为序列到序列问题设计的模型，Transformers架构越来越多地被用于静态图表示学习，并被扩展到动态图中。前面已经提到，模型是如何使用Transformer作为时间或空间编码器以及实现位置编码技术，这些都显示了其在学习动态图表示方面的巨大潜力。

7.1 COMBINATION OF TRANSFORMER WITH DGNNS

Transformers和DGNNs模型的结合有3种可能的方式，综合如图12 (左)所示。第一种组合是Transformers层和GNN层以独立的方式顺序应用。第二种组合是在DG编码器中交替使用GNN层和Transformer层。第三种组合是通过独立的变压器和GNN层对DG进行并行编码，然后将其编码的隐藏状态进行组合，合并这两层的强度。
相关论文：

7. G. Zheng, W. K. Chai, J. Zhang, and V. Katos, ‘‘VDGCNeT: A novel network-wide virtual dynamic graph convolution neural network and transformer-based traffic prediction model,’’ Knowl.-Based Syst., vol. 275, Sep. 2023, Art. no. 110676.

8. S. Banerjee, M. Dong, and W. Shi, ‘‘Spatial–temporal synchronous graph transformer network (STSGT) for COVID-19 forecasting,’’ Smart Health, vol. 26, Dec. 2022, Art. no. 100348.

9. A.-T. Kuo, H. Chen, Y.-H. Kuo, and W.-S. Ku, ‘‘Dynamic graph representation learning for depression screening with transformer,’’ 2023, arXiv:2305.06447.
   10.W. Cong, Y. Wu, Y. Tian, M. Gu, Y. Xia, M. Mahdavi, and C. Chen, ‘‘Dynamic graph representation learning via graph transformer networks,’’ in Proc. ICLR, 2021, pp. 1–11.

10. S. Wei, B. Wu, A. Xiang, Y. Zhu, and C. Song, ‘‘DGTR: Dynamic graph transformer for rumor detection,’’ Frontiers Res. Metrics Anal., vol. 7, Jan. 2023, Art. no. 1055348.

11. L. Xia, C. Huang, Y. Xu, and J. Pei, ‘‘Multi-behavior sequential recommendation with temporal graph transformer,’’ IEEE Trans. Knowl. Data Eng., vol. 35, no. 6, pp. 6099–6112, Jun. 2023.

12. Y. Fan, M. Ju, S. Hou, Y. Ye, W. Wan, K. Wang, Y. Mei, and Q. Xiong, ‘‘Heterogeneous temporal graph transformer: An intelligent system for evolving Android malware detection,’’ in Proc. 27th ACM SIGKDD Conf. Knowl. Discovery Data Mining, Aug. 2021, pp. 2831–2839.

13. M. Biparva, R. Karimi, F. Faez, and Y. Zhang, ‘‘TodyFormer: Towards holistic dynamic graph transformers with structure-aware tokenization,’’ in Proc. Temporal Graph Learn. Workshop@ NeurIPS 2023, 2023.

14. L. Wang, X. Chang, S. Li, Y. Chu, H. Li, W. Zhang, X. He, L. Song, J. Zhou, and H. Yang, ‘‘TCL: Transformer-based dynamic graph modelling via contrastive learning,’’ 2021, arXiv:2105.07944.

15. H. Li, S. Zhang, X. Li, L. Su, H. Huang, D. Jin, L. Chen, J. Huang, and J. Yoo, ‘‘DetectorNet: Transformer-enhanced spatial temporal graph neural network for traffic prediction,’’ in Proc. 29th Int. Conf. Adv. Geographic Inf. Syst., Nov. 2021, pp. 133–136.

16. J. Grigsby, Z. Wang, N. Nguyen, and Y. Qi, ‘‘Long-range transformers for dynamic spatiotemporal forecasting,’’ 2021,
    arXiv:2109.12218.

17. A. Feng and L. Tassiulas, ‘‘Adaptive graph spatial–temporal transformer network for traffic flow forecasting,’’ 2022, arXiv:2207.05064.

7.2 POSITIONAL ENCODING (PE) ON DYNAMIC GRAPHS

位置编码( PE )是变压器实现中的一个核心和基本问题。在动态图的背景下，PE远非平凡，因为它必须考虑元素在图结构中的位置，以及它们的时间位置。我们将位置编码区分为4种类型。第一种方法是基于节点或边的时间相关指数的嵌入。第二种方法利用(全局)图的光谱信息，如拉普拉斯或其特征向量。第三种方法依赖于空间域信息或局部结构，例如嵌入节点度或随机游走。最终，几乎所有的动态图转换器都使用时间嵌入来表示带有向量的时间戳或快照索引。
相关论文：
8. J. Grigsby, Z. Wang, N. Nguyen, and Y. Qi, ‘‘Long-range transformers for dynamic spatiotemporal forecasting,’’ 2021, arXiv:2109.12218.
9. A. Feng and L. Tassiulas, ‘‘Adaptive graph spatial–temporal transformer network for traffic flow forecasting,’’ 2022, arXiv:2207.05064.
10. S. Banerjee, M. Dong, and W. Shi, ‘‘Spatial–temporal synchronous graph transformer network (STSGT) for COVID-19 forecasting,’’ Smart Health, vol. 26, Dec. 2022, Art. no. 100348.
11. G. Zheng, W. K. Chai, J. Zhang, and V. Katos, ‘‘VDGCNeT: A novel network-wide virtual dynamic graph convolution neural network and transformer-based traffic prediction model,’’ Knowl.-Based Syst., vol. 275, Sep. 2023, Art. no. 110676.

7.3 SELF-ATTENTION (SA) MECHANISM

**Spatial SA：**当tokens代表快照中的节点时，SA在空间层面上操作，相当于图编码器fG，SA矩阵维度为快照t中节点数Nt的平方。
**Temporal SA：**当一个tokens在多个快照中表示同一个节点(或整个快照)时，SA在时态层面进行操作，充当时态编码器fT，因此其SA矩阵维度为时间步数K的平方。
**Spatial-Temporal SA：**遵循时间边建模，为K个快照中的每个节点创建副本，形成时空注意力，注意力矩阵大小为∑Nt或K × T的平方。
**Temporal Neighbor SA：**时态邻居SA同样在拓扑上运行，但其tokens是来自不同时间戳的节点/邻居，即CTDGs中的时态邻居。由于采用时间嵌入的方式将imestamp信息组合成隐藏状态，因此不需要像时空SA那样为每个节点创建节点的副本。
为动态图量身定制的Transformer架构的出现，标志着向更多样化的时间编码方式的进化。例如在ASTTN 中集成了多种类型的位置编码并学习时空注意力，以及在VDGCNeT 中结合了不同的注意力机制。同时，每种位置编码方式和注意力机制在不同情况和数据集上的有效性也提出了一个开放性的挑战，需要进一步的分析和研究。

8. ENCODING HETEROGENEOUS GRAPHS

由于异构图可以在推荐系统中的链接预测等任务中保持更多的信息表示，因此它们在动态图上的节点嵌入方面提出了独特的挑战。一个关键的问题是要有一个专门的模块来处理动态图上不同类型的节点和边。我们在以下章节中介绍了两种主要的方法，如图所示。由于异构图可以在推荐系统中的链接预测等任务中保持更多的信息表示，它们在动态图上的节点嵌入方面提出了独特的挑战。一个关键的问题是要有一个专门的模块来处理动态图上不同类型的节点和边。

基于GNN的模型对不同节点类型(例如,对于用户节点和项目节点)保持相同的嵌入维数d，以方便计算。例如JODIE将用户属性xu，物品属性xi，边属性xe和最近一次更新以来的时间差Δ嵌入到同一个维度d中，然后将它们相加，以更新用户u和物品i在时刻t有一个连接et u，i时的节点嵌入。
基于RW的方法通过定义元路径来处理异构图，元路径指定了游走中每个节点的类型，如(用户、物品、用户)，这样具有相同元路径的(又称’ ‘实例’ ")采样的每个随机游走都可以投影到相同的向量空间。动态图上的实例是THINE和HDGNN ，它们分别通过注意力层和双向RNN层对实例进行采样和编码。