图-解决模式识别（Pattern Recognize 问题） Node occurance 边的关联性 节点的属性 边的信息 $$ X _ {V} \in \mathbb {R} ^ {| V | \times d} $$ $$ X _ {E} \in \mathbb {R} ^ {| E | \times d _ {E}} $$ 动态图 在紧凑的表示中集成拓扑和时间信息能力，更多用于建模动态系统，如社交网络预测、推荐系统、交通预测、谣言传播等等，结合了顺序/时序数据处理和静态图学习的挑战。图被要求处理随时间变化的动态的拓扑结构（and/or）（边数）属性（节点属性边属性），为了对动态系统建模。 对顺序数据进行处理，捕获序列不同实体之间的依赖关系。 主要有 LSTM 的卷积架构所取代。 基于解码器/编码器框架的序列模型，如 Transformer、依赖于注意力机制 在静态图学习，克服图表示中缺乏节点排序所固有的置换不变性/等变性约束。 解决方法消息传递神经网络 MPNN 不同的 DG 离散的/连续的 边进化/节点进化/属性进化 同质与异质 学习环境：直推式还是归纳式 推断（前向预测）阶段 通过输入X预测Y 学习阶段（反向优化） 根据Y和Y‘，优化参数 如前所述，监督学习旨在学习输入空间 X和输出空间Y之间的映射函数。X可以表示的空间。本小节现在讨论空间Y。 由于动态图涉及来自图和时间/顺序数据的概念，因此必须考虑这两个方面来定义空间Y。 当学习序列数据的统计模型时，输入 X 可以由 T 个时间步长的 d 维特征表示，表示为X∈RTxd $\boldsymbol { X } \in \mathbb { R } ^ { T \times d }$。 输出Y的粒度可以是时间步长级别（每个时间步长一个输出，如在词性标记或更一般地序列标记中），或聚集的（一个输出用于许多输入，如在情感分类或更一般地序列分类中）。在静态图学习中，除了特征XV和XE之外，输入还具有拓扑信息。至于序列，输出 Y可以是局部的（每个节点或每条边一个标签）或全局的（每个子图或整个图一个标签）。 ![](images/296469f5d0a2010eb375ed7c66eed44792ebbceb0c9c733fa650c9c61c177c37.jpg) Inference Parameter Updates $$ \mathbf {\Theta} ^ {\prime} = \operatorname {u p d a t e} (\mathbf {\Theta}, \hat {\mathbf {Y}}, \mathbf {Y}) $$ 许多最新的模型遵循编码器/解码器原理，其中可变长度的输入信号被编码成潜在表示，然后由解码器使用该潜在表示来计算下游任务的输出信号 这里的 Z 就是 embedding 再把 embedding 通过解码器得到预测 ![](images/e2949c5b136177889bb7cc594ee5765d36bef4e6c8b7e90fe074c101bfb8a6ea.jpg) 输入和输出序列的单元可能具有不同的顺序。 学习潜在表示（也称为嵌入）被称为表示学习。 当有多个节点/边的类型（项目和用户），用类型映射函数 GNN/GAT/K-GNN DG 动态图——两种形式 一种离散形式的 DTDG 只要记住每一个时间段的快照（snapshot->ti） DTDG $=$ （G1,G2…,GT） 一种连续形式的 CTDG 连续时间动态图 基于事件流的形式 每一次事件的变化记录下来 瞬时交互两个节点的（u，v）和时间 t Contact -Sequence ={(ui,vi,ti)} Event-Based={(ui,vi,ti,deltai)} 起始(出现 )时间 ti 和持续时间 delta i，两个节点关联的边的存在的时刻 Interval-Graph={(ui,vi,Te);Te=((t1,t1’),(t2,t2’))}，用 Te 来表示边的所有活动 Graph stream 大规模图，用于边的添加和减少 delta i=1 add or -1deletion 标志位不考虑持续时间 Graph Stream={（ui，vi，ti，delta i）} 什么事件？ Ti时刻下，ui和vi的边增加了/减少了 Static Graphs Weighted directed graph ![](images/c746830d302e3e44284fd48b73c0af69a11d0acf4ee6059f4189b80414d69c7f.jpg) Heterogeneous graph ![](images/6f1bb89499913ea46bf89c5766e785d288ad81eb6d1d4371993b350c787bd28d.jpg) Dynamic Graphs DTDG (or Snapshot vision) ![](images/3e4e316277ba51154368e0a57961bebe492938e98fcdc466f4510639ac5629e6.jpg) CTDG (or Event vision) ![](images/8ef90f4621dfc41510d57405f3c6bb283fb266f06ec85835cad4eb31d5ae5683.jpg) (Edge-oriented) ESG ![](images/0681e7b4f29f3c5eba8a879c82bd10665da1edd827bdf1c903ae625ea3f30b1c.jpg) (Node-oriented) ESG ![](images/c758284426fe875cbb2097ef354f0d4a80e757498dc69b3b2a64c06ba310b2a0.jpg) 如何将动态图转换成等价的静态图ESG？ 1、基于边的形式 节点的备份 $^ +$ 边的联系（节点间 $^ +$ 时间戳，加入了节点之间的关联性） 2、基于节点的形式 GNNDelete如何删除边的关联性 # 定义动态度： 1、边和顶点都固定，fix V,E 时空图（STGCN 时空模型，既要学时间上的， 又要学空间上） 2、只固定了顶点,fix V 3、都变化，vary 4、边集不变，节点集变化，没有意义 # 输出是有粒度： # 预测单一时刻的结果 # 还是多个时刻的 ：时间步长级别的（ 每个时间步长一个输出） ：聚合的，一个输出多个输入（未来五个时间的拓扑结构） 拓扑结构也有局部（子图）和全局的 直推式 原来的拓扑结构不变 做出预测的时候没有在训练过程中没出现过的节点归纳式 做出推断的时候训练过程中没有看到 # Transductive (1) Transductive-fixv,ELearning Inference ![](images/bbcc93ac856be6d7c461092f4c7067219dd077d1ab5b3a264c057c10808b45aa.jpg) ![](images/db4d98da46d1e6c6e158c05a5859fb732876cbad79b0288d64c35862f9805c4c.jpg) (2) Transductive-fixyLearning Inference ![](images/5d77a9975b12967c827a904f0e653a6dd20b616eb17170ea86c227b4bff8c8af.jpg) ![](images/fae214f407c72c98ec8787121c73e96333ea90b02082385935af350087cea3a4.jpg) (3) Transductive-varyLearning Inference ![](images/e69e65651cde1ce432bc78ee711dfe7f2ab620c85a18ec5abadd2b7dc03c09ce.jpg) ![](images/d3f2b68951d63e00609989797d595e11f69387b3ae4a9d49ddf6e70f76b236b8.jpg) # Inductive （4） Inductivev ![](images/37efc40a1a19ed74b9949a8171bf9ac0dee51adfcf523d66b3d6c78e6feb4573.jpg) (5) InductiveDG ![](images/cf63288df9720a4b9ad1e8a1ad001c61714dd67c023f799376cc80871a30dffe.jpg) ![](images/8df199df3a9c6c47dd44f0eda1352bfe46da210844d723b3f9bda3fbbf91d868.jpg) 离散的时间直推式学习中（DTDG,Transductive），transfix VE ：交通流量，传染病病例，犯罪数量，作物产量 图/全局任务：每个快照的分类 睡眠阶段分类；整个DG的预测，如骨骼的动作STG；Tarnsfix V：电信网络中连通性，会议中个人联系 离散的归纳式学习（DTDG Inductive）中 社交网络未来快照的节点分类或链接预测图集输出 基于社交网络传播树的快照对真是和假新闻分类 连续时间（CTDG） 推荐系统、社交网络 CTCG再其最小时间单元下不能访问全局/整个图信息，全局的时间步标签是无意义的但是全局聚合任务可以通过聚合不同时间步长的节点来实现，如连续时间内谣言检测CTDG也可以定期拍摄快照转换为DTDG 动态时间下的任务 为了评估给定任务的统计模型的性能，传统机器学学习 分类任务 回归任务 节点排名任务 动态任务 沿着时间轴计算静态度量 动态图的嵌入 从编码器-解码器的角度来看，深度学习统计模型首先将原始输入映射到表示为 Z的嵌入中，然后利用 Z 来预测输出[12，4]。图形可以在节点/边缘级别或（子）图形级别嵌入[13，5].节点级嵌入有利于广泛的节点相关任务，并允许保留更完整的输入信息以供稍后计算[5]以同样的方式，时间步长级嵌入比时间聚合嵌入保留更多的信息。类似地，当在顺序数据上学 习 时 [7] 。 ![](images/c3a808e669a8b7be887e2835a878309fb07a5f2690536f0e5cc4d52868f7a209.jpg) $$ Z \in \mathbb {R} ^ {| V | \times | T | \times d}, z _ {v} ^ {t} \in \mathbb {R} ^ {d} $$ 对不同的动态图， 如何设计 encoder 的 settings (A) Discrete, transductive ![](images/46cb1d54b5358d567f25b2593621409ab8028885478293acb70c4cf8f849ab88.jpg) (B) Discrete, inductive ![](images/d2df25f6574b3cf24a96ef20688baf948c6322632b4acd9e8e97597ec9a56188.jpg) (C) Continuous, transductive ![](images/92b7d0fd700043ee860b01b2e882046208c24d7d786f335fd8b74b18954e36f3.jpg) (D) Continuous, inductive ![](images/731d08cee749b45a4111054e790163f2db076ce12de24586a28e861c309eb247.jpg) 为了将动态图信息化地编码为张量或向量列表，DGNN必须捕获结构信息及其随时间的演化 。 因 此 ， 为 了 分 别 处 理 拓 扑 和 时 间 ，DG 通常被 分 解 或转换 为 等效静 态 （ 子 ） 图[74，89，75]，随机游走[113，124，123，121，122]，或者是矩阵序列[95，86，93]。 在文献中，通过将不同的静态图编码器 fG（·）与时态数据的fT（·）相结合，出现了许多方法。大量的图和时态数据编码器是本节中回顾的 DG编码器的基础。这些编码器在附录B和C中进行了描述。 在下面的小节中，我们提出了一个DGNN模型的分类，它依赖于五个类别。我们的分类，如图7所示，是基于处理时间和结构信息的策略。 1.通过拓扑对时间边缘进行建模并对 ESG 进行编码，表示为 TE（第 3.1 节）。 2.对隐藏状态进行顺序编码，记为 enc（H）（第 3.2 节）。 3.对 DGNN 参数进行顺序编码，表示为 enc（Θ）（第 3.3 节）。 4.通过属性嵌入发生时间t作为ESG的边缘特征，表示为emb（t）（第3.4节）。 5.抽样因果游走，表示为 CauseRW（第 3.5 节）。 1. TE ![](images/497a6bfcb699c59d3b4a9b42e24e4270536c5f1681807f903e0e85dbc4a67ff8.jpg) ![](images/36a04b2c156c0dbfeeb1f8a5e3a2caa42895d4c195620b069cf075a54dca2717.jpg) ![](images/84576c405221d1001ad1ab5a0f3de8a24f61ef9923085f789c09f31cc6a792f9.jpg) 2. Enc(H) ![](images/1bb2a53245bd5c1de66e86cdf425f6fca9fbf5d9068fee5c6037b2afd2fff0d9.jpg) 3. Enc(0) ![](images/11776d45b7f1d6ffcfced0128e76a2d7ea793afc930bd40b6c3b614f0c6b1320.jpg) 4. Emb(t) ![](images/28df9d27ec3d3faac8c88b3acad757af84feff54fee07c071e078c0dff6e42e6.jpg) 请注意，这五种方法并不是唯一的，也就是说，它们可以组合在一起并用于同一 DG。 1、对时序的边进行建模——转换为静态图 FixV,E 考虑了时间信息（embedding ET） Snapshots ![](images/22d8dcba7544ae7f4b9a780b95130b617616df0c54a80f0a285449e5d6235839.jpg) ASTTN STG with Er ![](images/8169e54de8b83dfaaa4b484f35da48c4abb52c1e0df89fb0f62c7e9903e8e394.jpg) ST-GCN Module ![](images/6984145b6f133ae0040e209cde6ece2a90e61b23f8c1a1eedced479836a1b650.jpg) 2、对隐藏状态进行顺序编码 对拓扑结构和时间戳信息进行编码 RST DyReG Dyn-GCN 把通过 f(G)编码的信息经过 LSTM 或者 GRU（Sequential endocding）进行时间序列的学习 $$ Z ^ {t} = f _ {T} \left(\left(f _ {G} \left(X ^ {t}\right)\right)\right), o r f _ {T} \left(X ^ {T}\right) \oplus f _ {G} \left(X ^ {t}\right) $$ 解码的时候也要用sequential去阶码 3、对于新增的节点很难预测，及没有将 fG 和 fT 结合起来 对应的是 transformer 直接把时间戳的信息编码进去了 通过（fg参数）时间步来学习时间信息 将时间信息的编码加入到 fg 里 $$ \Theta_ {f _ {o}} ^ {t} = L S T M \left(\Theta^ {t - 1} _ {f _ {o}}\right) $$ $$ \Theta^ {t} _ {f _ {G}} = G R U \left(H ^ {t}, \Theta^ {t - 1} _ {f _ {G}}\right) $$ 再经过编码，就没有时间上的序列性了 4、 还把时间作为嵌入信息，如何编码时间信息 Temproal point process 在每个节点上加一个 t 的 embedding # 3、随机游走的方法 对于异质图的方法 怎么设计一个 GNN 设计 Workflow 如何优化框架 # 时序图神经网络 # 1、创建数据，根据快照的方式构建图 ![](images/215cfded78261b39f639e96eaae2b4b9cfafc37a05f9efefaa0359da4fcafbee.jpg) 表示节点的特征，如果没有特征用 one -hot 表示 计算 attention 系数 时间注意力 如何计算 loss？