@article{barros2021survey,
  title={A survey on embedding dynamic graphs},
  author={Barros, Claudio DT and Mendon{\c{c}}a, Matheus RF and Vieira, Alex B and Ziviani, Artur},
  journal={ACM Computing Surveys (CSUR)},
  volume={55},
  number={1},
  pages={1--37},
  year={2021},
  publisher={ACM New York, NY}
}

在 Day-03 的時候有稍微提到 Dynamic Graph，但是關於 Dynamic Graph 的研究相對於其他還是少了些，開源的專案基本都 focus 在 static graph 上，所以這邊就來看一下這篇論文，來稍微補一下這塊的知識。

Introduction

目前的研究主要都是針對 static graph，簡單來說就是只針對一個固定的時間點（graph snapshot）做 embedding。

但是很多真實世界的網路都具有動態行為，如果強制把這些特性忽略掉，可能會導致 embedding 的結果不夠準確。

The Challenge of Dynamic Graph Embedding

1. 使用哪種時域建模型
   • discrete time
   • continuous time
2. 要捕捉哪些行為特徵
3. which temporal granularity will be represented in the vector space
   • 在向量空間中要如何表示時間的精細程度

FUNDAMENTALS BEHIND THE EMBEDDING OF DYNAMIC GRAPHS

Graphs and Static Graph Embedding

這部分先前就提過很多次，因為不是我閱讀的重點，所以就不多做介紹了。

Dynamic Graphs

Notaion（1）

• Dynamic Graph：
• 一系列隨時間變化的節點集合：
• 一系列隨時間變化的邊集合：
• Graph Snapshot：

Notaion（2）

• Dynamic Graph：
• 表示特定時間點上節點 是否存在
• 表示特定時間點上節點 是否存在

Dynamic Graph Modeling

modeling 的方式又分成 discrete time 和 continuous time。

Graph Snapshots

簡單來說就是在不同時間點建立 static graph，然後再把這些 static graph 組合起來。

Difference Network Models

重點是記錄網絡的拓撲結構（adjacency matrix）隨時間變化的情況，重點是在於邊的變化，而節點的新增或刪除就不會被記錄下來（意思是它的維度只能是一個固定的 adjacency matrix ）。

Continuous-time Network Models

像是紀錄下來的邊是有 timestamp，或是使用 link stream 來記錄節點隨著時間變化之間的互動產生的改變。

Temporal Point Processes on Graphs

temporal point process 可以被表示成 counting process，紀錄在 t 之前所發生的事件數量，可以用來模擬連續時間中發生的順序非同步離散事件。

中間太多內容了先跳過，先講有哪些模型可以用來建模。

Dynamic Behaviors

圖片來源：A Survey on Embedding Dynamic Graphs

TECHNIQUES FOR THE EMBEDDING OF DYNAMIC GRAPHS

圖片來源：A Survey on Embedding Dynamic Graphs

看起來 Dynamic Graph Embedding 的方法跟 Static Graph Embedding 的方法差不多。