第 8 周 图神经网络与动态网络建模

局部聚合、异步记忆与物理执行

石守谦

2027 春季 · 资料核对至 2026-10-15

怎样在变化的邻居之间共享模型

• 邻居数量和顺序不断变化
• 消息可能迟到、重复或缺失
• 共享模型需要适应这些输入条件

复习W6向量与metadata，连接W7内部状态和预测。不要把动态图理解为每个时刻都能瞬间读取全图。所有输入必须来自本地传感器、实际到达消息或合法缓存。

把协作关系表示为图

• 节点：无人机或其他参与者
• 边：当前允许的信息交互
• 边属性：方向、时延、质量与代价

学生已修数据结构，图结构本身无需重复完整图算法。重点在特征的来源和可用时间。不要用真实距离或未来链路作为节点尚未知晓的输入。

交换编号之后，结果应该怎样变化

• 汇总整个集合：结果不随排列改变
• 分别输出节点动作：输出随节点一起换位
• 节点类型和能力可以作为显式输入

deepsets · NeurIPS 2017

用数组按节点编号排序的反例说明。固定槽位可能让新节点加入困难。对坐标旋转的equivariance是另一类对称性，不要与邻居重排混为一谈。

来源与阅读边界： - Deep Sets. NeurIPS 2017. https://proceedings.neurips.cc/paper_files/paper/2017/hash/f22e4747da1aa27e363d86d40ff442fe-Abstract.html 核验深度：官方摘要或作者项目说明；未宣称全文精读。使用边界：排列不变性不自动保证数量外推或任务泛化。

Deep Sets：无序集合的结构依据

$$z=\rho\!\left(\sum_{j\in\mathcal N_i}\phi(x_j)\right)$$

• 对每个元素使用共享变换
• 用对称运算汇总邻居
• 用不同节点数量检验实际泛化

deepsets · NeurIPS 2017

NeurIPS 2017讨论排列不变函数及对应结构。展示常用构造，不把有限维求和结构的表达能力和数量泛化作无条件保证。课堂交换邻居排列，检查输出保持一致；增减数量则需要额外实验。

来源与阅读边界： - Deep Sets. NeurIPS 2017. https://proceedings.neurips.cc/paper_files/paper/2017/hash/f22e4747da1aa27e363d86d40ff442fe-Abstract.html 核验深度：官方摘要或作者项目说明；未宣称全文精读。使用边界：排列不变性不自动保证数量外推或任务泛化。

手算：求和与取平均

邻居特征为 $0.2,0.6,1.0$。

$$\mathrm{sum}=1.8,\qquad \mathrm{mean}=0.6$$

求和保留数量效应；平均值需要另行输入邻居数量。

数字仅代表教学feature，不直接解释成经校准的概率。让学生加入一个重复0.9，观察sum和mean怎样变化。聚合器需要依据任务选择，不存在普遍正确的平均方式。

对邻居使用同一套参数

$$m_{ij}=\phi(h_j,e_{ij}),\qquad z_i=\sum_{j\in\mathcal N_i}m_{ij}$$

• $h_j$：邻居状态
• $e_{ij}$：链路与消息属性
• $\phi$：所有邻居共用的消息编码器

解释phi可以是可学习函数，参数通过W6介绍的loss优化。不同硬件能力可以作为显式类型输入，或者使用不同encoder；同一规则不意味着忽略异构性。

一层消息传递怎样计算

$$m_i=\operatorname{AGG}_{j\in\mathcal N_i}\phi(h_i,h_j,e_{ij})$$ $$h'_i=\psi(h_i,m_i)$$

先编码每条消息，再聚合，最后更新本地状态。

mpnn · ICML 2017

逐个解释符号，避免上来只放公式。layer index与消息的event time不能混淆。如果表示来自缓存，e需要反映缓存年龄。一个模型层可在集中内存中计算，也可能需要真实通信来实现。

来源与阅读边界： - Neural Message Passing for Quantum Chemistry. ICML 2017. https://proceedings.mlr.press/v70/gilmer17a.html 核验深度：官方摘要或作者项目说明；未宣称全文精读。使用边界：原任务为分子属性预测；无线消息传递需实现真实传输。

MPNN：统一消息与状态更新

• 消息函数根据节点与边属性产生信息
• 聚合函数汇总邻居消息
• 更新函数形成新的节点状态

mpnn · ICML 2017

ICML 2017在分子预测任务中统一消息传递神经网络的框架。课程借其结构组织节点计算。数学计算图中的边需通过真实通信实现，消息长度和交换频率应另行规定。

来源与阅读边界： - Neural Message Passing for Quantum Chemistry. ICML 2017. https://proceedings.mlr.press/v70/gilmer17a.html 核验深度：官方摘要或作者项目说明；未宣称全文精读。使用边界：原任务为分子属性预测；无线消息传递需实现真实传输。

手算：加权聚合

两条消息的值为 $0.5$、$1.0$，权重均为 $0.5$。

$$z=0.5\times0.5+0.5\times1.0=0.75$$

权重应结合任务、消息新旧与可信程度。

让学生说明为什么降低B权重可能有用，以及如果B是唯一看到关键区域的节点会怎样。年龄只是效用的一个因素，不应无条件删除旧信息。

把评分转换为权重

评分为 $(\ln2,0,0)$。

$$\operatorname{softmax}(s)=\frac{(2,1,1)}4=(0.5,0.25,0.25)$$

评分控制相对权重，不能单独决定是否发送。

解释e的幂只用于将分数转换为正值。实现可先减最大值避免数值溢出。所有候选都非法时需要专门分支，不能对全负无穷直接softmax。

先筛选可用消息，再计算权重

• 剔除失效记录和不兼容版本
• 排除测试时无法获得的信息
• 对没有有效邻居的情况设置回退规则

训练时用真实未来链路做mask会泄漏。缓存旧记录可以合法使用，但必须与“当前收到”区分。能否保留旧消息由任务模型决定，不是一条普遍的过期阈值。

GAT：按内容分配邻居权重

• 为邻居消息计算相关性评分
• 在允许的邻居集合内归一化
• 将消息按权重汇总为节点表示

gat · ICLR 2018

GAT是ICLR2018原论文。一个训练框架先把所有特征传到集中内存再算attention，实际通信可能早已发生。后续W9专门处理发送前的选择和硬预算。

来源与阅读边界： - Graph Attention Networks. ICLR 2018. https://openreview.net/forum?id=rJXMpikCZ 核验深度：官方记录/作者说明。使用边界：attention 权重不等于实际发送决策。

GraphSAGE：学习共享的聚合规则

• 采样邻居，控制计算规模
• 使用共享聚合器生成节点表示
• 对新节点的适用性仍需用新场景检验

graphsage · NeurIPS 2017

依据NeurIPS2017官方摘要。课程不把节点分类基准结果直接当作无人机策略结果。学生要说明自己项目改变的是节点数量、图结构还是任务目标。

来源与阅读边界： - Inductive Representation Learning on Large Graphs. NeurIPS 2017. https://proceedings.neurips.cc/paper/2017/hash/5dd9db5e033da9c6fb5ba83c7a7ebea9-Abstract.html 核验深度：原论文§2与Figure 1；PDF已取得。使用边界：新节点归纳不自动保证新任务泛化。

GraphSAGE：采样、聚合与更新

GraphSAGE Figure 1

GraphSAGE 原论文

沿原图识别邻域采样、特征聚合和输出预测。图中的计算发生在模型定义的邻域上，不自动表示真实无线消息已经送达。请学生将其中每一个远端feature映射到本机收到的消息或合法缓存。 来源：Hamilton, Ying, Leskovec. Inductive Representation Learning on Large Graphs. NeurIPS 2017, Figure 1、§2。已取得原文并核对相关机制，未将其节点分类数值外推到飞行任务。

Set Transformer：处理无序消息集合

• 消息之间通过注意力交换信息
• 聚合结果可保持排列不变
• 时间、来源与坐标仍需显式编码

sets · ICML 2019

ICML2019。先让学生对比mean忽略了什么关系，再理解attention能建模条件相关性。但复杂模型不一定值得更高计算成本，简单mean必须保留作基线。

来源与阅读边界： - Set Transformer: A Framework for Attention-based Permutation-Invariant Neural Networks. ICML 2019. https://proceedings.mlr.press/v97/lee19d.html 核验深度：官方摘要。使用边界：无序聚合不解决时间戳和坐标不一致。

模型层数与无线交换轮数

• 模型的一层表示一次特征聚合
• 分布式执行时，跨节点依赖需要真实传输
• 缓存、批处理和中继会改变实际通信轮数

公式是粗略加和模型，实际流水并发时需要关键路径分析。K层也可能复用缓存，不一定每步恰好K次新发包；必须说明实现。不要把神经网络层数直接等同于传播时延。

时间顺序决定信息能否到达

A 的新消息必须等待下一次 B→C 传输，才能到达 C。

A 的新消息必须等待下一次 B→C 传输，才能到达 C。

让学生把信息从产生时刻向后追踪。即使窗口内并集连通，也要检查消息产生、等待与deadline。这一例子帮助理解RSS时间聚合连通性与具体消息可达性的差异。

估算通信量

$N$ 个节点，平均发送给 $d$ 个邻居，每条 $b$ 字节，每秒 $f$ 次：

$$R\approx Ndbf$$

这是应用层估算；多跳、协议头和重传应另计。

以N,d,b,f帮助学生把模型计算量与通信量分开。若使用广播，同一空口帧可能被多个邻居接收，不应简单按接收者复制发送成本；但可靠性和覆盖又不同。

增加聚合层数之后要检查什么

• 接收信息的范围是否扩大？
• 信息是否已经过期或重复？
• 计算、通信与任务收益是否相称？

第一点通常称over-smoothing，用直觉解释即可，不需要本页宣称所有GNN都必然如此。分别做层数、去重、年龄特征消融，避免用单一术语解释全部失败。

将消息接收建模为事件

每次收到消息，记录：

• 原始生成时间与本地接收时间
• 来源、序号及内容
• 接收时可用的本地状态

回应用户“输入触发更新，周期只负责广播”的想法。事件驱动内部状态与周期发送是两个独立调度器。训练批处理可以模拟这些事件，但不能改变其因果顺序。

动态图有两种时间建模思路

工作	主要思路
TGAT	将时间编码带入邻域聚合
EvolveGCN	随时间更新图卷积参数

部署时，模型只能使用当时已经到达的信息。

tgat · ICLR 2020 · evolvegcn · AAAI 2020

TGAT为ICLR 2020；EvolveGCN为AAAI 2020。两篇提供时间信息和动态图变化的建模方式，均不自动给出无线队列及乱序接收的完整执行方案。项目可比较时间编码、固定衰减和无时间输入三类方法。

来源与阅读边界： - Inductive Representation Learning on Temporal Graphs. ICLR 2020. https://openreview.net/forum?id=rJeW1yHYwH 核验深度：官方摘要或作者项目说明；未宣称全文精读。使用边界：图上的时间建模仍需服从部署时实际接收顺序。 - EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs. AAAI 2020. https://ojs.aaai.org/index.php/AAAI/article/view/5984 核验深度：官方摘要或作者项目说明；未宣称全文精读。使用边界：快照更新不直接给出异步无线执行方案。

用本地记忆保留历史

• 新观测到来时更新状态
• 旧消息到来时检查时间与来源
• 长期未更新时，提高不确定性或转入回退策略

h正负表示一次事件前后，避免假设全局离散t。重申运行期state和训练weight区别。缓存应该有容量、过期和去重策略，而不无限保存。

暂时没有邻居时怎样运行

• 使用本地观测继续执行允许的动作
• 保留待同步的状态变化
• 重连后校验版本，按需补传增量

不把断网一律写成悬停或返航，这取决于具体应用和规则。教学原型可以选择安全简化动作，但必须在报告里声明。关键是训练集中包含zero-neighbor，而不是运行时崩溃。

研究设想：断联时积累，重连后补传

从共同版本出发，独立更新、校验、增量合并

用连续失联区段训练，分别测量失联表现和恢复过程。

ramen · RSS 2025 · asyncac · NeurIPS 2022

推导：持续等待邻居会阻塞本地决策，保留本地记忆可以维持运行；重连时全量同步可能造成拥塞。设想交换必要增量并处理冲突。验证使用成段失联和相关丢包，不能只用独立随机丢包；测量关键事件漏报、任务完成率、恢复时间和补传量。若冲突累积导致性能恶化，需检查记忆与合并规则。

来源与阅读边界： - RAMEN: Real-time Asynchronous Multi-agent Neural Implicit Mapping. RSS 2025. https://www.roboticsproceedings.org/rss21/p041.html 核验深度：官方摘要已核对；Link端PDF下载超时。使用边界：地图参数共识不能直接变成任意策略共识。 - Asynchronous Actor-Critic for Multi-Agent Reinforcement Learning. NeurIPS 2022. https://proceedings.neurips.cc/paper_files/paper/2022/hash/1c153788756d35559c22d105d1182c30-Abstract-Conference.html 核验深度：官方摘要或作者项目说明；未宣称全文精读。使用边界：动作持续时间不同与数据包异步到达仍需分别建模。

交互：改变邻居与消息权重

演示用表格显示邻居分数、合法mask和归一化权重。切换某个节点是否可用，观察其分母如何变化。测试全部不可用分支，输出应回到仅使用本地信息，而不是NaN。

训练样本必须遵守接收时序

• 输入只能包含决策时已经到达的信息
• 先按接收事件重放，再构造训练样本
• 将未来信息作为输入会高估部署效果

这是实际分布式系统中常被忽略的leakage。用同一个消息event_t=5 recv_t=8的例子问：在t=6可用吗？答案不可以，除非明确有另一个本地来源。

根据输出任务选择训练目标

• 检测或建图：使用对应标注
• 动作选择：使用专家动作或任务回报
• 表示一致性：作为辅助目标单独做消融

不要把GNN等同RL。先有输出和评价，再选监督、模仿、自监督或RL。若任务没有标签，仍需说明reward和采样机制，而不是只说端到端训练。

异步决策也需要相应的训练方法

• 不同节点的动作可能持续不同时间
• 异步 Actor-Critic 直接建模异步策略
• 数据包接收事件与动作结束事件分别记录

asyncac · NeurIPS 2022

NeurIPS 2022工作支持异步动作选择，包含仿真和硬件实验。课程特别区分动作异步与通信异步；项目若两者同时存在，应在事件日志中记录清楚，不能把统一步长仿真结果直接称为异步网络验证。

来源与阅读边界： - Asynchronous Actor-Critic for Multi-Agent Reinforcement Learning. NeurIPS 2022. https://proceedings.neurips.cc/paper_files/paper/2022/hash/1c153788756d35559c22d105d1182c30-Abstract-Conference.html 核验深度：官方摘要或作者项目说明；未宣称全文精读。使用边界：动作持续时间不同与数据包异步到达仍需分别建模。

模仿学习与 DAgger

• 首先模仿专家在训练场景中的动作
• 再让学习器运行，采集自身遇到的状态
• 请专家补充标注，缓解状态分布偏移

swarmgnn · CoRL 2019 / PMLR 2020；dagger · AISTATS 2011

两个来源分别支持局部控制学习与imitation的分布问题，不宣称两篇完全相同。DAgger需要专家对学习器访问状态提供标签，现实中可能代价高。

来源与阅读边界： - Learning Decentralized Controllers for Robot Swarms with Graph Neural Networks. CoRL 2019 / PMLR 2020. https://proceedings.mlr.press/v100/tolstaya20a.html 核验深度：官方摘要已核对；Link端PDF下载超时。使用边界：CoRL届次2019，出版年2020，不能混写。 - A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning. AISTATS 2011. https://proceedings.mlr.press/v15/ross11a.html 核验深度：官方摘要/论文。使用边界：专家可用性与查询成本需要考虑。

RAMEN：异步协作建图的启发

• 在异步条件下交换地图信息
• 根据不确定性处理过期的邻居地图
• 迁移到控制任务时，重新定义状态与损失

ramen · RSS 2025

根据RSS官方摘要。地图优化有特定变量、损失与不确定性定义，课堂应明确这一对象边界。让学生比较“旧副本降权”与“全部丢弃”各自可能失败的情况。

来源与阅读边界： - RAMEN: Real-time Asynchronous Multi-agent Neural Implicit Mapping. RSS 2025. https://www.roboticsproceedings.org/rss21/p041.html 核验深度：官方摘要已核对；Link端PDF下载超时。使用边界：地图参数共识不能直接变成任意策略共识。

学习协作图需要考虑物理执行

• G-Designer：为任务生成智能体协作图
• SOPS：在稀疏结构上选择连接
• 无线部署还需计算路径、时延和信道占用

gdesigner · ICML 2025；sops · ICML 2026

SOPS官方摘要明确使用exponential-graph backbone，不能说它天然适配任意FANET物理图。对比的重点是“候选连接从哪里来”，不是直接比较两个任务的benchmark分数。

来源与阅读边界： - G-Designer: Architecting Multi-agent Communication Topologies via Graph Neural Networks. ICML 2025. https://proceedings.mlr.press/v267/zhang25cu.html 核验深度：官方摘要已核对；Link端PDF下载超时。使用边界：没有证明该图可在无线多跳网络低成本执行。 - Sparse Topology-Aware Pairwise Scoring for Large-Scale Multi-Agent Reinforcement Learning. ICML 2026. https://proceedings.mlr.press/v306/deng26n.html 核验深度：官方摘要已核对；Link端PDF下载超时。使用边界：exponential graph backbone 不是物理无线可达图。

从期望协作关系到可执行连接

为模型需要的远端信息安排可用路径、队列与预算。

为模型需要的远端信息安排可用路径、队列与预算。

这是课程提出的设计空间，不是四选一固定答案。可以混合，但必须声明优先级和成本归属。GNN学得的edge score还需要调度器处理链路与预算。

联邦学习怎样进入课程

• FedAvg 聚合训练期间的模型参数
• 运行期消息传递交换任务信息
• 两者可以组合，但应分别设置周期与预算

fedavg · AISTATS 2017

避免抢讲W11完整内容。用户设想的HFL可作为跨场地持续学习路线，但不应作为每次动态分组发生时的必需步骤。训练拓扑与执行拓扑可以不同。

来源与阅读边界： - Communication-Efficient Learning of Deep Networks from Decentralized Data. AISTATS 2017. https://proceedings.mlr.press/v54/mcmahan17a.html 核验深度：官方摘要。使用边界：Federated Learning 不等于运行期消息传递，也不自动保证隐私。

去中心化学习还依赖哪些条件

• 节点通过时变稀疏网络交换学习信息
• 局部回报与邻居消息共同参与更新
• 通信连通性和函数形式会影响理论结论

networkedrl · ICML 2018

ICML 2018给出网络化多智能体的去中心化Actor-Critic方法，线性函数逼近条件下有收敛分析。本课程不将这些保证外推到任意深度网络。运行期协调与训练参数交换应分别预算。

来源与阅读边界： - Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents. ICML 2018. https://proceedings.mlr.press/v80/zhang18n.html 核验深度：官方摘要或作者项目说明；未宣称全文精读。使用边界：收敛结论依赖线性函数逼近等设定，不能泛化到任意深度模型。

实验：实现一个邻居聚合器

1. 支持任意数量的邻居
2. 过滤过期与重复消息
3. 保持排列不变
4. 检查零邻居和迟到消息

让学生先做规则版本，再谈可学习权重。可运行的标准库实验在labs/local_state_lab.py中演示mask、去重和预算核算，不要求先安装PyTorch。

本讲需要形成的设计

• 节点状态与消息格式
• 聚合、记忆和回退规则
• 时序重放方法与训练目标

结课时让学生区分aggregate与schedule。模型对已接收内容的权重，不等同于发送前省掉了数据。下一周将这一差异作为第一处关键复习。