遵循往年的传统,我们采访了一批杰出的多产的学术和工业专家,试图总结过去一年的亮点,并预测2024年将发生什么。2023年过去了,结果已经非常成熟了,所以我们不得不将这篇文章分成两部分。这是第一部分,重点是理论和新的架构,也请参阅第二部分的应用。
DALL-E 3
这篇文章由Michael Galkin和Michael Bronstein撰写和编辑,Johannes Brandstetter、İsmail İlkan Ceylan、Francesco Di Giovanni、Ben Finkelshtein、Kexin Huang、Chaitanya Joshi、Chen Lin、Christopher Morris、Mathilde Papillon、Liudmila Prokhorenkova、Bastian Rieck、David Ruhe、Hannes Stärk和Petar Veličković也有重要贡献。
图神经网络理论
消息传递神经网络和图Transformers
Michael Bronstein (Oxford), Francesco Di Giovanni (Oxford), İsmail İlkan Ceylan (Oxford), Chris Morris (RWTH Aachen)
图Transformers是图机器学习中相对较新的趋势,试图将Transformers的成功从序列扩展到图。就传统的表达能力而言,这些架构没有提供任何特别的优势。事实上,可以说它们在表达能力方面的大多数好处(参见例如Kreuzer等人https://arxiv.org/abs/2106.03893)来自强大的结构编码,而不是体系结构本身,这种编码原则上可以与MPNNs一起使用。
在最近的一篇论文中,Cai等人https://arxiv.org/abs/2301.11956研究了MPNNs和(图)Transformers之间的连接,表明具有虚拟节点(以特定方式连接到所有其他节点的辅助节点)的MPNNs可以模拟(图)Transformers。这种架构是非均匀的non-uniform,即神经网络的大小和结构可能取决于输入图的大小。有趣的是,一旦我们将注意力限制在线性Transformers(例如Performer)上,那么就会有一个统一uniform的结果: 存在一个使用虚拟节点的单一MPNNs,可以在任何大小的任何输入上近似Performer等线性Transformers。
(a) 具有虚拟节点的 MPNN,(b) Transformer。
时间这与关于图转换器架构与 MPNNs 相比是否具有捕获远程依赖关系的优势的讨论有关。图转换器与 MPNNs 进行比较,MPNNs 通过使用虚拟节点包含全局计算组件,这是一种常见的做法。蔡等人的经验表明,具有虚拟节点的 MPNNs 可以在长范围图基准(LRGB、Dwivedi 等人https://arxiv.org/abs/2206.08164)上超越图转换器的性能。此外,Tönshoff 等人https://arxiv.org/abs/2309.00367重新评估 LRGB 基准上的 MPNN 基线,发现之前报告的有利于图 Transformers 的性能差距由于超参数选择次优而被高估,从本质上缩小了 MPNNs 和图 Transformers 之间的差距。
SignNet
众所周知,常见的拉普拉斯位置编码(例如,LapPE)对于特征向量的符号和基础的变化并不是不变的。缺乏不变性使得更容易获得(非均匀)普遍性结果,但这些模型因此不会计算图不变量。这激发了今年的大量工作,包括符号和基不变网络( Lim et al., 2023a https://arxiv.org/abs/2202.13013)和符号等变网络(Lim et al., 2023b https://arxiv.org/abs/2312.02339)的研究。这些发现表明,需要进行更多的研究来从理论上证实文献中常见的有关 MPNN 和图转换器比较的主张。
图分量 Graph components、双连通性biconnectivity和平面性planarity
张等人(2023a) https://arxiv.org/abs/2301.09505使图双连通性的研究引起了图 ML 社区的关注。张等人(2023a)提出了许多结果相对于不同的双连接指标。事实证明,与许多现有的高阶模型(即那些可以与 2-FWL 的能力相匹配的模型)不同,标准 MPNNs 无法检测图双连通性。另一方面,具有一定距离编码的Graphomers和子图GNNs(例如ESAN)可以检测图的双连通性。
LHS 显示图分解 (AC),RHS 显示相关编码器 (DF) 和更新方程 (G)。
Dimitrov等人(2023) https://arxiv.org/abs/2307.01180依靠图分解来开发用于平面图学习的专用架构。这个想法是与用于平面同构测试的经典Hopcroft & Tarjan https://www.sciencedirect.com/science/article/pii/0020019071900196算法的变体保持一致。Dimitrov等人(2023)首先将图分解为其双连通分量和三连通分量,然后学习节点、割节点、双连通分量和三连通分量的表示。这是使用可以在线性时间内计算的块切割树和 SPQR 树的经典结构来实现的。生成的框架称为PlanE https://arxiv.org/abs/2307.01180并包含诸如BasePlanE https://arxiv.org/abs/2307.01180之类的体系结构。BasePlanE 计算同构完全图不变量,因此它可以区分任何一对平面图。这项工作的主要贡献是设计架构,以有效学习平面图的完整不变量,同时保持实际可扩展性。值得注意的是,已知 3-FWL 在平面图上是完备的(Kiefer et al., 2019 https://dl.acm.org/doi/10.1145/3333003),但该算法不可扩展。
聚合函数与统一表达力
它人们普遍认为不同的聚合函数有其用武之地,但这一点尚未得到严格证明。事实上,在非均匀设置中,与 MLP 的求和聚合会产生单射映射,并因此包含其他聚合函数(Xu 等人,2020 https://arxiv.org/abs/1810.00826),该函数建立在早期结果的基础上(Zaheer 等人,2017 https://arxiv.org/abs/1703.06114)。在统一设置中情况有所不同,需要一个固定模型来处理所有图。Rosenbluth等人(2023 https://arxiv.org/abs/2302.11603)表明求和聚合并不总是包含统一设置中的其他聚合。例如,如果我们考虑无界特征域,求和聚合网络甚至无法近似均值聚合网络。有趣的是,即使对于积极的结果,其中总和聚合显示为近似其他聚合,所提出的结构通常需要大量层(随着近似误差的倒数增长)。
GNNs的收敛性 Convergence和0-1定律zero-one laws
原则上,GNNs 可以应用于训练后任何大小的图。这使得输入图大小的渐近分析非常有吸引力。之前对 GNNs 渐近行为的研究主要集中在理论极限网络的收敛性(Keriven et al., 2020 https://arxiv.org/abs/2006.01868)及其在大图扰动下的稳定性(Levie et al., 2021 https://arxiv.org/abs/1907.12972)。
在最近的一项研究中,Adam-Day等人(2023 https://arxiv.org/abs/2301.13060) 证明了二元 GNNs 分类器的零一定律。正在解决的问题如下:当我们绘制具有随机节点特征的尺寸不断增加的 Erdos-Rényi 图时,二元 GNNs 分类器如何表现?主要发现是,此类图被一类 GNNs 分类器映射到特定输出的概率趋于零或一。也就是说,模型最终将所有图映射到零或将所有图映射到一。该结果适用于 GCN 以及具有总和和均值聚合的 GNNs。
这一结果的主要意义在于,它为 GNNs 的表达能力建立了一个新颖的统一上限:可以由这些 GNNs 架构统一表达的图的任何属性都必须遵守零一定律。不渐近趋于零或一的简单属性的一个例子是具有偶数个节点。
GNNs的描述复杂度
Grohe (2023) https://arxiv.org/abs/2303.04613最近根据布尔电路复杂性分析了 GNNs 的描述复杂性。感兴趣的特定电路复杂性类别是 TC0。此类包含由具有恒定深度和多项式大小的布尔电路决定的所有语言,仅使用 AND、OR、NOT 和阈值 (或多数)门。Grohe (2023) https://arxiv.org/abs/2303.04613证明,可以通过一类多项式大小有界深度 GNNs 系列计算的图函数位于电路复杂度类别 TC0 中。此外,如果允许 GNNs 类使用随机节点初始化和全局读出,如Abboud 等人(2020) https://arxiv.org/abs/2010.01179那么存在一个匹配的下界,因为它们可以计算与 TC0 中表达的函数完全相同的函数。这通过要求模型类别具有有界深度(固定#layers)和大小多项式,建立了具有随机节点特征的 GNNs 能力的上限。虽然这个结果仍然不均匀,但它改进了Abboud 等人(2020)https://arxiv.org/abs/2010.01179的结果其中构造可以是最坏情况下的指数。
GNNs的细粒度 Fine-grained表达力
最近的许多工作分析了 MPNNs 的表达能力,主要利用 1-WL 等组合技术来解决图同构问题。然而,图同构目标本质上是二元的,无法深入了解两个给定图之间的相似程度。Böker等人(2023) https://arxiv.org/abs/2306.03698通过将 1-WL 和 MPNN 连续扩展到图子来解决这个问题。具体来说,他们表明 1-WL 的连续变体提供了 MPNN 在图元上的表达能力的准确拓扑表征,揭示了这些网络可以区分哪些图以及分离它们的难度级别。他们结合了 1-WL 经典表征的各种拓扑变体,为图和图子相似性提供了一个理论框架。特别是,他们用树距离(基于分数同构概念的图距离)和通过树同态的子结构计数来表征 MPNN 的表达能力,表明这些概念具有与 1- 相同的表达能力。图子上的 WL 和 MPNN。有趣的是,他们还验证了他们的理论发现,表明随机初始化的 MPNN 在未经训练的情况下,与经过训练的对应模型相比表现出有竞争力的性能。
子图GNNs的表达性结果
基于 Subgraph 的 GNN 已经成为 2022 年的一大趋势(Bevilacqua et al., 2022 https://arxiv.org/abs/2110.02910、Qian et al., 2022 https://arxiv.org/abs/2206.11168)。今年,张等人(2023b) https://arxiv.org/abs/2302.07090为此类架构建立了更细粒度的表达结果。该论文通过所谓的子图 Weisfeiler-Leman 测试(SWL)研究了子图 GNN。通过这一点,他们展示了 SWL 的完整层次结构以及严格增长的表现力。具体来说,他们定义了 SWL 类型算法的等价类,并表明几乎所有现有的子图 GNN 都属于其中之一。此外,所谓的SSWL实现了最大的表达能力。有趣的是,他们还将 SWL 与几种现有的富有表现力的 GNN 架构联系起来。例如,他们表明 SWL 具有与 2-WL 的本地版本相同的表达能力(Morris 等人,2020 https://arxiv.org/abs/1904.01543)。除了理论之外,他们还表明 SWL 型架构取得了良好的实证结果。
链接预测与知识图谱表达能力研究
时间Barceló 等人(2022)https://arxiv.org/abs/2211.17113研究了 RGCN 和 CompGCN 等架构在知识图上链接预测的表达能力。今年,黄等人(2023)https://arxiv.org/abs/2302.02209概括了这些结果来表征各种其他模型架构的表达能力。
该图比较了 R-MPNN 和 C-MPNN 各自的操作模式。
黄等人(2023) https://arxiv.org/abs/2302.02209介绍了条件消息传递网络 ( C-MPNNs )的框架,其中包括NBFNets https://arxiv.org/abs/2106.06935等架构。经典关系消息传递网络(R-MPNNs)是一元编码器(即编码图节点),并依赖于二进制解码器来完成链接预测任务(Zhang,2021)https://arxiv.org/abs/2010.16103。另一方面,C-MPNNs 用作二进制编码器(即对图节点对进行编码),因此更适合链接预测的二进制任务。C-MPNNs 与关系 Weisfeiler-Leman 算法保持一致,该算法可被视为 2WL 的局部近似。这些发现解释了 NBFNets 等优于 RGCNs 等的性能。黄等人(2023) https://arxiv.org/abs/2302.02209还针对 C-MPNNs 捕获的二元函数类的精确逻辑表征提出了统一的表达结果。
过度挤压Over-squashing和表达力Expressivity
Over-squashing 是Alon 和 Yahav https://arxiv.org/abs/2006.05205于 2021 年最初描述的一种现象,即将指数增长的感受野压缩为固定大小的向量。随后的研究(Topping et al., 2022 https://arxiv.org/abs/2111.14522,Di Giovanni et al., 2023 https://arxiv.org/abs/2302.02941,Black et al., 2023 https://arxiv.org/abs/2302.06835,Nguyen et al., 2023 https://arxiv.org/abs/2211.15779)通过敏感性分析表征了过度挤压,证明输出特征对来自早期层的隐藏表示会受到拓扑特性(例如负曲率或较长的通勤时间)的损害。由于图拓扑在瓶颈的形成中起着至关重要的作用,因此图重新布线(一种将图连通性提升到 GNNs 中设计因素的范式转变)已被提出作为减轻过度挤压的关键策略(如果您有兴趣,请参阅下面有关奇异消息传递的部分 )。
对于给定的图,MPNN 为节点 (v, u) 和 (u, w) 学习更强的混合(紧弹簧),因为它们的通勤时间很短,而节点 (u, q) 和 (u, z) 的通勤时间很长通勤时间,混合较弱(弹簧松动)。
过度挤压会阻碍表达能力,因为它会导致 GNN 在长距离交互任务中表现不佳。为了正式研究这一点,Di Giovanni 等人(2023) https://arxiv.org/abs/2306.03589引入了一种新的表达能力度量,称为“混合”,它编码图函数对节点特征对的联合和非线性依赖性:对于 GNN 来说,具有大混合的功能,必要条件是允许相关节点之间进行“强”消息交换。因此,他们假设通过 GNN 预测的混合来测量过度挤压,并证明 GNN 诱导足够混合所需的深度(按照任务的要求)随着通勤时间的增加而增长——通常比最短的通勤时间差得多。路径距离。结果表明,过度挤压如何阻碍具有“实用”尺寸的 GNN 的表达能力,并验证了它是由任务(需要节点 i 和 j 之间的强烈混合)和拓扑(导致 i 和 j 之间的大量通勤时间)之间的不对准引起的。j)。
函数的“混合”涉及节点之间的信息交换,无论该信息是什么,而不是其分离节点表示的能力。事实上,这些结果 也适用于比 1-WL 测试更强大的 GNN。Di Giovanni 等人 (2023) https://arxiv.org/abs/2306.03589的分析提供了一种研究 GNN 表达能力的替代方法,该方法可以轻松扩展到 3D 空间中的等变 GNN 及其对节点之间交互进行建模的能力。
GNNs的泛化 Generalization和外推Extrapolation能力
时间近年来,MPNN 的表达能力通过与 WL 测试的联系引起了广泛关注。虽然这种联系在理解和增强 MPNN 的表达能力方面取得了重大进展(Morris 等人,2023a https://arxiv.org/abs/2301.11039),但它并没有提供对其泛化性能的深入了解,即它们在训练集之外做出有意义的预测的能力。令人惊讶的是,只有少数值得注意的贡献研究了 MPNN 的泛化行为,例如Garg 等人(2020)https://arxiv.org/abs/2002.06157,Kriege等人(2018)https://www.ijcai.org/proceedings/2018/0325.pdf,廖等人(2021) https://arxiv.org/abs/2012.07690,Maskey等人(2022)https://arxiv.org/abs/2202.00645,Scarselli等人(2018)https://pubmed.ncbi.nlm.nih.gov/30219742/。然而,这些方法仅使用经典图参数(例如最大度、顶点数或边数)来表达 MPNN 的泛化能力,而无法完全捕获现实世界图的复杂结构。此外,大多数方法研究非均匀状态下的泛化,即假设 MPNN 在预先指定的顺序的图上运行。
MPNN 的泛化能力及其与 1-WL 的链接的概述。
因此,Morris等人(2023b) https://arxiv.org/abs/2301.11039显示 1-WL 的表达能力和泛化性能之间存在紧密联系。他们通过紧密连接 1-WL 的表达性和 MPNN 的 Vapnik-Chervonenkis (VC) 维来研究图结构和参数编码长度对 MPNN 泛化的影响。为此,他们展示了一些结果。
1️⃣ 首先,在非均匀状态下,他们表明 MPNN 的 VC 维度紧密依赖于 1-WL 在一组图上计算的等价类的数量。此外,他们的结果很容易扩展到 k-WL 和许多最近的富有表现力的 MPNN 扩展。
2️⃣ 在统一制度中,即当图可以具有任意顺序时,它们表明 MPNN 的 VC 维度的下限和上限由其权重的最大位长度决定。在均匀和非均匀状态下,MPNN 的 VC 维度以对数方式取决于 1-WL 计算的颜色数量,以多项式方式取决于参数数量。此外,他们还通过实证表明,他们的理论发现在一定程度上在实践中是成立的。
预测时间
Christopher Morris(亚琛工业大学)
“我认为迫切需要更好、更实用的 GNN 泛化理论。”——克里斯托弗·莫里斯(亚琛工业大学)
➡️ 例如,我们需要了解图结构和各种架构参数如何影响泛化。此外,用于训练 GNN 的 SGD 动态目前尚未得到充分研究和充分理解,更多工作将对此进行研究。
İsmail İlkan Ceylan(牛津大学)
“我希望在统一的环境中看到更多的表现力结果,我们可以修复神经网络的参数并检查其功能。” —伊斯梅尔·伊尔坎·塞兰(牛津大学)
➡️ 在这种情况下,我们可以找到与泛化更好的联系,因为如果一个属性不能统一表达,那么模型就无法泛化到更大的图尺寸。
➡️ 今年,我们可能还会看到针对图回归或图生成的表达性研究,而这些研究尚未得到充分探索。有充分的理由希望学习算法在较大的图类上是同构完备的,严格概括平面图的结果。
➡️ 现在也是时候开发一种使用完全关系数据(即知识超图)进行学习的理论,这将解锁关系数据库中的应用程序!
Francesco Di Giovanni(牛津大学)
就GNN未来的理论发展而言,我认为有两个值得关注的方向。
“人们对梯度流(或 SGD)下 GNN 权重的动态了解甚少;评估图拓扑对权重演化的影响是解决任务泛化性和难度问题的关键。” — Francesco Di Giovanni(牛津大学)
➡️ 其次,我认为开发替代的表达范式是有价值的,它更直接地关注(图函数及其导数的)近似能力并准确识别难以学习的任务。后一个方向对于表征 3D 空间中等变 GNN 的能力也可能特别有意义,其中表达性的测量可能需要与 2D 情况分离,以便更好地与来自科学领域的任务保持一致。
最后:关于 2023 年 WL 走向何方的有趣事实
2023 年帖子的预测
(1) 在创建时间和内存高效的子图 GNN 方面付出更多努力。
❌其实不是
(2) 更好地理解 GNN 的泛化
✅ 是的,请参阅有关过度压缩和泛化的小节
(3) Weisfeiler 和 Leman 参观 10 个新地点!
❌(到目前为止 4 个)语法https://openreview.net/forum?id=eZneJ55mRO、无关紧要https://arxiv.org/abs/2311.01205、测量建模https://arxiv.org/abs/2307.05775、路径https://arxiv.org/abs/2308.06838
新的和奇异Exotic的消息传递
Ben Finkelshtein (Oxford), Francesco Di Giovanni (Oxford), Petar Veličković (Google DeepMind)
Petar Veličković (Google DeepMind)
多年来,消息传递运算符的发展已经饱和,这已成为民间传说的一部分。我觉得 2023 年取得的进展特别令人兴奋的是,几个独立研究小组(包括我们自己的研究小组)已经出现了一个统一的新颖方向:让我们开始考虑GNN 中时间的影响⏳。
“我预测,到 2024 年,时间将在新型 GNN 架构的开发中发挥核心作用。” — Petar Veličković(谷歌 DeepMind)
💡 当输入中明确提供时间(在时空或完全动态图中)时,时间就已经在 GNN 设计中得到了利用。今年,它开始在静态图输入的 GNN 算子研究中占据重要地位。一些工作正在放弃统一、同步时钟的假设⏱️,该时钟强制同一层中的所有消息立即发送和接收。
1️⃣ 第一个这样的工作,GwAC 🥑https://openreview.net/forum?id=zffXH0sEJP,只使用了基本的随机消息调度,但提供了为什么这种处理可能会显着提高表达能力的证据。Co-GNN https://arxiv.org/abs/2310.01267进一步发扬光大,展示了一种更精细、更微调的以节点为中心的消息调度机制,允许每个节点选择何时发送 📨 或接收 📬 消息。Co-GNN 还提供了一种通过梯度下降训练此类调度器的实用方法。虽然开发这种异步 GNN 模型是非常可取的,但我们也必须承认相关的可扩展性问题——我们目前的前沿硬件并不是为了有效地扩展这种顺序系统而设计的。
2️⃣ 在我们自己的异步算法对齐https://openreview.net/forum?id=ba4bbZ4KoF工作中,我们选择设计同步GNN,但限制其消息、聚合和更新功能,以便即使部分数据流异步,GNN 也会产生相同的嵌入。这让我们踏上了一段令人兴奋的旅程,通过幺半群、1-cocycle 和范畴论,产生了一个可扩展的 GNN 模型,该模型在许多 CLRS-30 任务上实现了卓越的性能。
异步 GNN 的可能执行轨迹。虽然传统的 GNN 同步发送和接收所有消息,但在我们的框架下,GNN 可以在任何步骤选择执行任意数量的可能操作(此处用图右侧的集合进行描述)。
➡️最后,值得注意的是,对于消息调度的某些特殊选择,我们不需要对同步 GNN 的架构进行修改 – 而是可以诉诸动态图重新布线。DREW https://arxiv.org/abs/2305.08018和Half-Hop https://openreview.net/forum?id=lXczFIwQkv是 ICML’23 上同时发表的两篇论文,体现了使用图重新布线来减慢消息传递🐌的原理。在 DREW 中,来自每个节点的消息实际上会发送到其他每个节点,但消息需要经过k层才能到达相距k跳的邻居!另一方面,半跳采用更宽松的方法,只是随机决定是否引入“慢节点”,该“慢节点”扩展了由边连接的任意两个节点之间的路径。这两种方法自然地缓解了过度平滑的问题,因为传输距离较长的消息的过度平滑程度会降低。
无论是用于消息传递设计、GNN 数据流还是图形重新布线,到 2023 年,我们才刚刚开始认识到时间的重要性——即使时间变化没有明确存在于我们的数据集中。
本·芬克尔施泰因(牛津大学)
时间Co-GNN https://arxiv.org/abs/2310.01267中提出的时间相关消息传递范式是消息传递的可学习概括,它允许每个节点决定如何从其邻居传播信息或向其邻居传播信息,从而实现更灵活的信息流。这些节点被视为参与者,可以向侦听的邻居广播,也可以侦听广播的邻居(如经典的消息传递),向侦听的邻居广播,或者隔离(既不侦听也不广播)。
这些动作之间的相互作用以及在本地动态更改它们的能力允许 CoGNN 确定特定于任务的计算图(可以将其视为动态和定向重新布线的一种形式,学习具有不同节点特征的两个节点的不同动作分布(基于特征和结构)。CoGNN允许跨节点异步更新,并且还以高概率生成唯一的节点标识符,这使它们能够区分任何图对(比 1-WL 更具表现力,但代价是仅在期待)。
从左到右:经典 MPNN(所有节点广播和监听)、DeepSet(所有节点隔离)和通用 CoGNN。
Francesco Di Giovanni (牛津大学)
“当任务依赖于通勤时间较长的节点之间的交互时,对过度挤压的理解就成为了图重新布线出现的催化剂,成为设计新 GNN 的有效方法。” — Francesco Di Giovanni(牛津大学)
️💡图重新连接广泛地需要改变输入图的连接性以促进下游任务的解决。最近,这通常针对图中的瓶颈,从而添加(和删除)边以改善信息流。虽然重点是在哪里交换消息,但最近的工作(如上所述)也阐明了何时应该交换消息的相关性。这些方法背后的一个基本原理(尽管通常是隐含的)是,由 GNN 各层构建的隐藏表示为图提供了(人为的)动态组件,即使图和输入特征是静态的。这种观点可以通过多种方式加以利用。
在经典的 MPNN 设置中,每一层信息仅从一个节点传输到其直接邻居。在 DRew 中,图根据层而变化,新添加的边连接从层 r-1 开始距离为 r 的节点。最后,在νDRew中,我们还引入了一种延迟机制,相当于不同节点之间基于相互距离的跳跃连接。
➡️ DRew https://arxiv.org/abs/2305.08018是特别拥抱这种角度的一个框架,它以两种方式扩展任何消息传递模型:(i)它直接连接距离为r 的节点,但仅从r层开始;(ii) 当节点连接时,根据它们的相互距离,它们的消息交换会受到延迟。如上图所示,(i)允许网络更好地保留归纳偏差,因为距离更近的节点更早交互;(ii) 相反,充当距离感知的 跳跃连接,从而促进损失梯度的传播。最有可能的是,正是由于这个原因,而不是防止过度平滑(这对图级任务几乎没有影响),该框架显着增强了标准 GNN 在更大深度的性能(更多详细信息可以在博客文章https://towardsdatascience.com/dynamically-rewired-delayed-message-passing-gnns-2d5ff18687c2)。
🔮预测:我相信,在“时间”组件上扩展消息传递的深远影响将在来年开始显现。像 DRew 这样的工作只触及了为什么随着时间(超越空间)重新布线可能有利于 GNN 的训练,从而极大地影响它们在不同深度范围内的准确性响应的表面。
更广泛地说,我希望图重新布线的理论和实践发展能够转化为科学领域,其中等变 GNN 经常应用于没有自然图结构的 3D 问题(使得消息应该在“哪里”的问题)交换的相关性越来越大)或(和)表现出自然的时间(多尺度)属性(使得“何时”交换消息的问题可能成为减少记忆限制和保留正确归纳偏差的关键)。
超出图
几何、拓扑、几何代数和偏微分方程
Johannes Brandstetter (JKU Linz), Michael Galkin (Intel), Mathilde Papillon (UC Santa Barbara), Bastian Rieck (Helmholtz & TUM), and David Ruhe (U Amsterdam)
2023 年对几何 GNN 进行了最全面的介绍(和调查),涵盖了最基本和必要的概念,并提供了一些示例:3D 原子系统几何 GNN 搭便车指南(Duval、Mathis、Joshi、Schmidt 等人 https://arxiv.org/abs/2312.07511)。如果您想从头开始学习推动图 ML 在蛋白质设计、材料发现、分子模拟等方面取得最新突破的核心架构 – 这就是您所需要的!
3D 原子系统的关键几何 GNN 的时间线,以层内中间表示的类型为特征。
拓扑结构Topology
由于PyT 团队https://github.com/pyt-team及其资源套件(TopoNetX、TopoModelX和TopoEmbedX )的惊人努力,2023 年研究人员和实践者的拓扑结构工作变得更加容易。TopoNetX https://github.com/pyt-team/TopoNetX基本上是拓扑数据的网络。TopoNetX 支持细胞复合体、单纯复合体和组合复合体等标准结构。TopoModelX https://github.com/pyt-team/TopoModelX是一个类似 PyG 的库,用于拓扑数据的深度学习,并以简洁的统一接口实现了MPSN https://arxiv.org/abs/2103.03212和CIN https://arxiv.org/abs/2106.12575等著名模型(原始 PyG 实现相当混乱)。TopoEmbedX https://github.com/pyt-team/TopoEmbedX有助于在拓扑数据上训练嵌入模型,并支持Cell2Vec https://arxiv.org/abs/2010.00743等核心算法。
域:蓝色的节点,粉色的(超)边,深红色的面。
Hajij 等人https://arxiv.org/abs/2206.00606和Papillon 等人https://arxiv.org/abs/2304.10031的论文是该领域的一个伟大的先行者和这些拓扑网络的基本构建模块。大部分模型是由数据科学中的拓扑、代数和几何(TAG) 社区https://www.tagds.com/home的成员实现的,该社区定期在 ML 会议上组织拓扑研讨会。
Mathilde Papillon (UCSB)
“直到 2023 年,拓扑深度学习领域的特点是关系数据的丰富表示形式支离破碎。” — Mathilde Papillon(加州大学圣巴巴拉分校)
➡️ 消息传递模型仅建立在同一领域的其他模型之上并对其进行基准测试,例如,单纯复杂社区与超图社区保持孤立。更糟糕的是,大多数模型都采用了独特的数学符号。决定哪种模型最适合给定的应用程序似乎是一项艰巨的任务。Hajij等人https://arxiv.org/abs/2206.00606提出的统一理论提供了一个通用方案,在该方案下所有模型都可以被系统地描述和分类。我们将该理论应用到文献中,对拓扑深度学习中的消息传递进行了全面而简洁的调查https://arxiv.org/abs/2304.10031,这也可以作为对该领域的简单介绍。我们还提供了一本字典,以统一的符号列出了所有模型架构https://github.com/awesome-tnns/awesome-tnns。
➡️为了进一步统一该领域,我们组织了首届拓扑深度学习挑战赛Topological Deep Learning Challenge https://pyt-team.github.io/topomodelx/challenge/index.html,该挑战赛在2023 年 ICML TAG 研讨会https://www.tagds.com/events/conference-workshops/tag-ml23上举办,并通过Papillon 等人https://proceedings.mlr.press/v221/papillon23a.html的白皮书进行了记录。目标是通过众包拓扑领域神经网络的开源实现来促进可重复的研究。作为挑战的一部分,来自世界各地的参与者贡献了TopoModelX https://github.com/pyt-team/TopoModelX中现有拓扑深度学习模型的实现。每份提交都经过严格的单元测试,并包括对从TopoNetX https://github.com/pyt-team/TopoNetX加载的数据集进行基准训练。我们希望这套一致实施的一站式模型套件将帮助从业者在 2024 年测试新应用和开发的拓扑方法。
Bastian Rieck(亥姆霍兹和慕尼黑工业大学)
对于拓扑驱动的机器学习方法来说,2023 年是激动人心的一年。一方面,我们看到了与曲率等几何概念的更多集成,从而证明了混合几何拓扑模型的多功能性。例如,在“图生成模型评估的曲率过滤”https://arxiv.org/abs/2301.12906中,我们展示了如何利用曲率来选择合适的图生成模型。在这里,曲率充当我们用来提取图结构信息的“镜头”,同时我们采用持久同源性(一种拓扑方法)以一致的方式比较这些信息。
使用离散曲率评估图生成模型的流程概述。边缘的排序产生曲率过滤,然后是相应的持久图和景观。对于图生成模型,我们选择曲率,按元素应用该框架,并通过比较生成的分布和参考分布的平均景观来评估它们的相似性。
➡️ 另一个方向强调拓扑驱动方法正在成为图学习研究的主要内容,使用拓扑来评估图神经网络模型的表达能力。有时,就像 Immonen 等人https://openreview.net/pdf?id=27TdrEvqLD在 NeurIPS 2023 中发表的一篇非常引人入胜的工作一样。这甚至导致了同时利用图的几何和拓扑方面的新颖模型!我自己的研究也旨在通过专门分析图学习中持久同源性的表达能力https://arxiv.org/abs/2302.09826来为这方面做出贡献。
“2023 年也是摆脱(或超越)持久同源性的风口浪尖。尽管代数拓扑和微分拓扑被正确地视为拓扑驱动机器学习的范例算法,但它们提供了更丰富的结构,可用于分析数据。” — Bastian Rieck(亥姆霍兹和慕尼黑工业大学)
➡️ 与我伟大的合作者一起,我们最近开始寻找一些替代方案,并提出了神经差分形式https://arxiv.org/abs/2312.08515的概念。微分形式允许我们通过德拉姆上同调 de Rham cohomology https://en.wikipedia.org/wiki/De_Rham_cohomology优雅地在几何和拓扑之间建立一座桥梁——一种将某些对象(微分形式)的积分(即基本的几何运算)与输入数据的拓扑特征联系起来的方法。通过一些额外的构造,德拉姆上同调允许我们学习图(或高阶组合复合体)的几何描述并解决学习任务,而不必依赖消息传递。结果是参数较少的模型在解决此类任务方面可能更有效。这里还有更多内容,因为我们才刚刚开始触及表面!
🔮我对 2024 年充满希望的预测是,我们将:
1️⃣ 看到更多来自代数和微分拓扑的工具应用于图和组合复形,
2️⃣ 更好地理解高阶输入数据上的消息传递,以及
3️⃣ 最终获得更好的持久同源并行算法,以在深度学习环境中真正释放其力量。Torras-Casas 最近发表的一篇关于光谱序列的论文https://link.springer.com/article/10.1007/s00454-023-00549-2报告了一些非常令人兴奋的结果,显示了该技术的巨大前景。
几何代数Geometric Algebras
Johannes Brandstetter (JKU Linz) and David Ruhe (U Amsterdam)
“2023 年,我们看到几何代数(也称为Clifford 代数)深度学习子领域的腾飞。此前,Brandstetter 等人引入了以 Clifford 代数多向量运算形式表示的神经网络层。今年,‘几何代数’中的‘几何’显然被付诸行动了。” — Johannes Brandstetter(林茨大学)和 David Ruhe(阿姆斯特丹大学)
➡️ 首先,Ruhe 等人https://arxiv.org/abs/2302.06594通过引入几何 Clifford 代数网络 (GCAN) ,应用现代(基于平面)几何代数的精髓,GCAN 是对各种几何代数描述的对称变换进行建模的神经网络模板。我们看到Pepe 等人https://openaccess.thecvf.com/content/WACV2024/papers/Pepe_CGAPoseNetGCAN_A_Geometric_Clifford_Algebra_Network_for_Geometry-Aware_Camera_Pose_WACV_2024_paper.pdf对其进行了有趣的应用。在CGAPoseNet中,为相机姿态回归构建几何感知管道。接下来,Ruhe 等人https://arxiv.org/abs/2305.11141引入了Clifford 群等变神经网络 (CGENN),通过 Clifford 群构建任意维度的可操纵 O(n) 和 E(n) 等变(图)神经网络。Pepe等人https://openreview.net/forum?id=JNfpsiGS5E将 CGENN 应用于蛋白质结构预测 (PSP) 流程,将预测精度提高高达 2.1%。
CGENN(用 表示)能够以 O(n) 或 E(n) 等变方式对多向量(Clifford 代数的元素)进行运算。具体来说,当将代表正交变换(例如旋转)的 Clifford 群的动作 ρ(w) 应用于数据时,模型的表示会同步旋转。多向量可以分解为标量、向量、双向量、三向量,甚至高阶分量。这些元素可以表示几何量,例如(定向)面积或体积。动作 ρ(w) 旨在在作用于这些结构时尊重这些结构。
➡️ 巧合的是, Brehmer等人https://arxiv.org/abs/2305.18415制定了几何代数变换器(GATr),这是一种可扩展的变换器架构,它利用射影几何代数提供的表示的优点和变换器的可扩展性来构建E(3)等变架构。Haan 等人https://arxiv.org/abs/2311.04744将 GATr 架构扩展到其他代数。他们还会检查哪种几何代数最适合您的 E(3) 等变机器学习问题。
GATr 架构概述。实线框是可学习组件,虚线框是固定组件。
🔮 2024 年,我们可以期待这些进步带来令人兴奋的新应用。一些示例包括以下内容。
1️⃣ 我们可以期待探索它们在分子数据、药物设计、神经物理仿真、晶体等方面的适用性。其他几何感知应用包括 3D 渲染、姿势估计和规划,例如机器人手臂。
2️⃣ 我们可以期待基于几何代数的网络扩展到其他神经网络架构,例如卷积神经网络。
3️⃣ 接下来,CGENN 的通用性允许在其他维度(例如 2D)进行探索,但也允许在需要一起处理不同维度数据的设置中进行探索。此外,它们还支持非欧几里得几何,这在相对论物理学中有几个用例。
4️⃣ 最后,GATr 和 CGENN 可以扩展并应用于射影、共形、双曲或椭圆几何。
偏微分方程PDEs
Johannes Brandstetter (JKU Linz)
关于神经 PDE 建模的前景,到 2023 年哪些主题已经浮出水面或势头强劲?
1️⃣ 首先,在复杂的几何形状上和内部对偏微分方程进行建模有明显的趋势,需要基于网格的空间离散化。这与解决日益现实的现实世界问题的总体目标是一致的。例如,李等人https://arxiv.org/abs/2309.00583引入了用于大规模 3D PDE 的几何通知神经算子 (GINO) 。
2️⃣ 其次,基于拉格朗日模拟的神经网络代理的开发变得越来越有趣。空间的拉格朗日离散化使用有限的物质点,这些物质点作为流体包裹通过空间和时间进行跟踪。最著名的拉格朗日离散化方案称为平滑粒子流体动力学(SPH),它是Toshev 等人https://arxiv.org/abs/2309.16342提供的LagrangeBench基准数据集中的数值基线。
我们数据集的时间快照,在轨迹的初始时间(顶部)、40%(中间)和 95%(底部)。色温代表速度大小。(a) 泰勒格林涡流(2D 和 3D),(b) 逆泊肃叶流(2D 和 3D),© 盖驱动腔(2D 和 3D),(d) 坝破 (2D)。
3️⃣ 第三,基于扩散的建模对于偏微分方程也没有停止。我们大致看到两个方向。第一个方向将扩散过程的迭代性质重新定义为从噪声初始化并以先前时间步长为条件的候选状态的细化。这种迭代细化被引入到PDE-Refiner(Lippe 等人 https://arxiv.org/abs/2308.05732)中,并且其变体已经应用于GenCast(Price 等人https://arxiv.org/abs/2312.15796)中。第二个方向利用扩散模型的概率性质来模拟 3D 湍流等混沌现象。这方面的例子可以在《湍流模拟》(Kohl 等人https://arxiv.org/abs/2309.01745)和《从零到湍流》(Lienen 等人https://arxiv.org/abs/2306.01776)中找到。特别是对于 3D 湍流,在不久的将来会发生很多有趣的事情。
“在过去的几个月里,天气建模已经成为一个巨大的成功故事。未来可能会有更多令人兴奋的事情发生,特别是直接根据观测数据进行天气预报或建立天气基础模型时。” — Johannes Brandstetter (JKU 林茨)
🔮 2024 年的期望:
1️⃣ 有关 3D 湍流建模的更多工作。
2️⃣ 偏微分方程的多模态方面可能会出现。这可能包括组合不同的偏微分方程、不同的分辨率或不同的离散化方案。我们已经在McCabe 等人的《物理代理模型的多重物理预训练》https://arxiv.org/abs/2310.02994中看到了这一点。
2023 年帖子的预测
(1) 神经偏微分方程及其应用有可能扩展到更多与物理相关的 AI4Science 子领域;计算流体动力学 (CFD) 可能会受到 GNN 的影响。
✅ 我们看到 3D 湍流建模、几何感知神经算子、基于粒子的神经代理以及天气预报等领域的巨大影响。
(2) 基于 GNN 的代理可能会增强/取代传统的久经考验的技术。
✅ 天气预报已成为一个巨大的成功故事。基于神经网络的天气预报超越了传统预报(中期+局部预报),例如Lam 等人的GraphCast https://www.science.org/doi/full/10.1126/science.adi2336。和Andrychowicz 等人的MetNet-3 https://arxiv.org/abs/2306.06079。
鲁棒性Robustness和可解释性Explainability
黄可欣(斯坦福大学)
“随着 GNN 被部署在各个领域,它们的可靠性和鲁棒性变得越来越重要,特别是在错误成本很高的安全关键应用(例如科学发现)中。” — 黄可欣(斯坦福大学)
1️⃣ 在讨论 GNN 的可靠性时,一个关键标准是不确定性量化——量化模型对预测的了解程度。有许多关于估计和校准不确定性的工作,也是专门为 GNN 设计的(例如GATS https://proceedings.neurips.cc/paper_files/paper/2022/hash/5975754c7650dfee0682e06e1fec0522-Abstract-Conference.html)。然而,它们在理论上和经验上都未能实现预定义的目标覆盖率(即落入预测集的点的百分比)。我想强调的是,覆盖率保证的概念至关重要,尤其是在科学发现的机器学习部署中,因为从业者通常信任具有统计保证的模型。
2️⃣ 保形预测是统计学中一个令人兴奋的方向,它具有有限的样本覆盖保证,并已应用于CV和 NLP https://arxiv.org/abs/2107.07511等许多领域。但理论上它是否可以在图中使用尚不清楚,因为可交换性假设是否适用于图设置并不明显。2023 年,我们看到保形预测已扩展到图形。值得注意的是,CF-GNN https://arxiv.org/abs/2305.14535和DAPS https://proceedings.mlr.press/v202/h-zargarbashi23a/h-zargarbashi23a.pdf推导了传导节点级预测设置中保形有效性的理论条件,并开发了减少预测集大小以实现下游高效使用的方法。最近,我们还看到了对链接预测https://arxiv.org/pdf/2306.14693v1.pdf、非均匀分割https://arxiv.org/abs/2306.07252、边缘可交换性https://openreview.net/forum?id=homn1jOKI5的共形预测扩展,以及对可交换性不成立的设置(例如归纳设置https://arxiv.org/abs/2211.14555)的适应。
图结构数据的共形预测。(1) 一个基础 GNN 模型 (GNN),为节点 i 生成预测分数 µ。(2)保形校正。由于训练步骤不知道保形校准步骤,因此预测集/间隔的大小/长度(即效率)未被优化。我们使用拓扑感知校正模型,该模型将 μ 作为输入节点特征,并聚合来自其本地子图的信息以生成更新的预测 μ~。(3)共形预测。我们证明,在传导随机分割设置中,图可交换性保持给定的排列不变性。因此,标准CP可用于产生基于μ~的预测集/间隔,其包括具有预先指定的覆盖率1-α的真实标签。
🔮 展望未来,我们预计会有更多扩展来涵盖广泛的 GNN 部署用例。总的来说,我认为 GNN 的统计保证非常好,因为它使从业者能够信任使用 GNN 预测。
图Transformers
陈琳(牛津大学)
💡 2023 年,我们看到了 Graph Transformer 的持续崛起。它已经成为常见的 GNN 设计,例如在GATr https://arxiv.org/abs/2305.18415中,作者将其流行归因于其“有利的缩放特性、表达能力、可训练性和多功能性”。
1️⃣ GT 的表现力。正如 GNN 理论部分中提到的,Cai 等人https://arxiv.org/abs/2301.11956最近的工作。(2023)显示了具有虚拟节点的 MPNN 与非均匀设置下的 GT 之间的等效性。这就提出了一个问题:GT到底有多强大,其表征能力的来源是什么?张等人(2023)https://arxiv.org/abs/2301.09505成功地结合了一种新的强大的位置嵌入(PE)来提高其 GT 的表达能力,实现了双连接问题的表达能力。这证明了 PE 对 GT 表达能力的重要性。最近提交的GPNN https://openreview.net/pdf?id=JfjduOxrTY提供了关于位置编码的核心作用的更清晰的观点。事实证明,可以推广Zhang等人https://arxiv.org/abs/2301.09505的证明。(2023)展示 GT 的表现力是如何由各种位置编码决定的。
2️⃣ 位置(结构)编码。鉴于 PE/SE 对 GT 的重要性,现在我们转向通常源自现有图不变量的那些表达特征的设计。2022 年,GraphGPS https://arxiv.org/abs/2205.12454通过将 GT 与各种(甚至多个)PE/SE 相结合,取得了巨大的经验成功。2023 年,将推出更强大的 PE/SE。
Ma等人https://arxiv.org/abs/2305.17589提出的相对随机游走PE(RRWP)概括了带有关系部分的随机游走结构编码。与新的注意力机制变体一起,GRIT在财产预测基准(ZINC 上的 SOTA)上与现有 PE/SE 相比实现了强大的实证性能。理论上,RRWP 可以通过特定的参数选择来近似最短路径距离、个性化 PageRank 和热核。对于 RRWP,GRIT 比 SPD-WL 更具表现力。
荧光素分子的 RRWP 可视化,最高可达 4 次方。较厚和较暗的边缘表示较高的边缘权重。较长随机游走的概率揭示了高阶结构(例如,3-RW 中明显的派系和 4-RW 中的星形模式)。
Puny 等人https://arxiv.org/abs/2302.11556提出了一种基于等变多项式的新表达性理论框架,其中可以通过基于等变基础的张量收缩计算的多项式特征作为位置编码来提高常见 GNN 的表达性。实证结果令人惊讶:使用 d 表达多项式,GatedGCN 从测试 MAE 0.265 提高到 0.106。看看未来是否有人将其与 GT 结合起来,将会非常有趣。
3️⃣高效GT。由于复杂度为 O(N²),GT 应用于大型图仍然具有挑战性。2023年,我们看到更多的工作试图通过降低GT的计算复杂度来消除这种困难。Deac 等人https://arxiv.org/abs/2210.02997使用扩展图https://en.wikipedia.org/wiki/Expander_graph进行传播,该图通常与很少的边连接。Exphormer https://arxiv.org/abs/2303.06147通过将扩展图与局部邻域聚合和虚拟节点相结合,将这一想法扩展到 GT。Exphormer 允许图形转换器扩展到更大的图形(与具有 169K 个节点的ogbn-arxiv一样大)。它还取得了强有力的实证结果,并在多项长期图基准https://github.com/vijaydwivedi75/lrgb任务中排名第一。
🔮展望2024年:
-
更好地理解自注意力对抽象超越表达能力的好处。
-
2024 年大型开源预训练等变 GT!
-
更强大的位置编码。
新的数据集和基准Benchmarks
结构生物学: VantAI 的 Pinder、Oxford 的PoseBusters https://arxiv.org/abs/2308.05777、 The Other Place 的PoseCheck https://arxiv.org/abs/2308.07413、 DockGen https://openreview.net/forum?id=UfBIxpTK10以及Valence Labs https://arxiv.org/abs/2310.04292的LargeMix 和 UltraLarge 数据集
时态图基准(TGB)http://tgb.mila.quebec/:到目前为止,时态图学习的进展一直因缺乏大型高质量数据集以及缺乏适当的评估而导致性能过于乐观而受到阻碍。TGB 通过引入七个现实的、大规模的和多样化的基准来解决这个问题,用于时间图的学习,包括节点式和链接式任务。受 OGB 成功的启发,TGB 自动执行数据集下载和处理以及评估协议,并允许用户使用排行榜https://tgb-website.pages.dev/docs/leader_linkprop/来比较模型性能。查看相关博客https://towardsdatascience.com/temporal-graph-benchmark-bb5cc26fcf11文章了解更多详细信息。
来自 Google Research 的TpuGraphs https://github.com/google-research-datasets/tpu_graphs:TPU 计算图的图属性预测数据集。该数据集提供的图形比最大的图形属性预测数据集(图形大小相当)多 25 倍,与机器学习程序的现有性能预测数据集相比,平均图形大 770 倍。Google基于 TpuGraphs举办了Kaggle 竞赛https://www.kaggle.com/competitions/predict-ai-model-runtime!
LagrangeBench https://github.com/tumaer/lagrangebench:拉格朗日流体力学基准测试套件 – 您可以在基于 JAX 的环境中评估您最喜欢的基于 GNN 的模拟器(针对 JAX 爱好者)。
RelBench https://relbench.stanford.edu/:来自斯坦福大学和 Kumo.AI 的关系深度学习基准:对关系数据库(您可以将其建模为图或超图)进行基于时间的预测。
来自 Google DeepMind 的GNoMe 数据集 https://github.com/google-deepmind/materials_discovery?tab=readme-ov-file#dataset:381k 种更多新颖稳定的材料,用于您的材料发现和 ML 潜力模型!
会议,课程和社区
图和几何学习领域的主要活动(除了大型 ML 会议)变得越来越大、越来越成熟:图学习会议 (LoG) https://logconference.org/、分子 ML (MoML) https://www.moml.mit.edu/和斯坦福图学习研讨会https://snap.stanford.edu/graphlearning-workshop-2023/。LoG 会议采用了很酷的形式,包括远程优先会议和由来自中国、英国、欧洲和美国西海岸等全球各地的社区成员组织的数十场本地聚会。
LoG 聚会在阿姆斯特丹、巴黎、特罗姆瑟和上海举行。
课程、书籍和教育资源
-
-
Geometric GNN Dojo https://github.com/chaitjo/geometric-gnn-dojo — 为初学者和专家提供的教学资源,用于探索几何图 GNN 的设计空间(与最近的《Hitchhiker’s Guide to Geometric GNNs》最搭配)。
-
-
TorchCFM https://github.com/atong01/conditional-flow-matching — 流量匹配世界的主要入口点。
-
-
PyT团队https://github.com/pyt-team维护着 TopoNetX、TopoModelX 和 TopoEmbedX——这是进入拓扑深度学习最实用的库。
-
-
Maurice Weiler、Patrick Forré、Erik Verlinde 和 Max Welling 所著的《等变和坐标独立卷积网络:神经网络规范场理论》https://maurice-weiler.gitlab.io/#cnn_book 一书汇集了等变 CNN 的表示理论和微分几何的发现
-
调查
-
-
来自 23 个机构的 60 多位作者(Zhang、Wang、Helwig、Luo、Fu、Xie 等人)在量子、原子和连续体系统中进行科学机器学习https://arxiv.org/abs/2307.08423
-
-
Wang等人在《自然》杂志上发表了人工智能时代的科学发现。https://www.nature.com/articles/s41586-023-06221-2
-
著名研讨会系列
-
-
学习图形和几何https://portal.valencelabs.com/logg
-
分子建模和药物发现(M2D2)https://portal.valencelabs.com/m2d2
-
VantAI读书会https://www.youtube.com/@Vant_AI
-
牛津 LoG2 研讨会系列https://log-2.github.io/
-
社区
-
-
LoGaG https://join.slack.com/t/logag/shared_invite/zt-22y7n3k7a-FHwX31gc85yZCa0uF8BU7w
-
LOG conference https://join.slack.com/t/logconference/shared_invite/zt-27nv8ba1y-pXspnAzgLOMdDzfKgpOafg
-
PyG https://data.pyg.org/slack.html
微信群 公众号