Graph Transformers：更稀疏、更快、有向

一年前GraphGPS（https://towardsdatascience.com/graphgps-navigating-graph-transformers-c2cc223a051c）被提出，ICML2023许多论文建立在GraphGPS框架之上，进一步扩展了GT。

Shirzad、Velingker、Venkatachalam 等人的Exphormer（https://openreview.net/forum?id=3Ge74dgjjU）为GT 添加了一个缺失的图驱动稀疏注意力：Exphormer 的注意力不是 BigBird 或 Performer（最初为序列设计），而是建立在 1 跳边、虚拟节点（连接到所有节点）的基础上图中的节点），以及扩展边的巧妙想法。扩展图具有恒定的度，并且显示为近似全连接图。所有组件结合起来，注意力成本为O(V+E)而不是O(V²)。这使得 Exphormer 几乎在任何地方都优于 GraphGPS，并可扩展到多达 160k 节点的真正大图。令人惊叹的工作和所有机会使 Exphormer 成为 GT 中的标准稀疏注意力机制。

与图transformers同时，expander graphs已可用于增强任何 MPNN 架构的性能，如Deac、Lackenby 和 Veličković的Expander Graph Propagation（https://arxiv.org/abs/2210.02997）中所示。

同样，Cai 等人（https://openreview.net/forum?id=1EuHYKFPgA）表明，具有虚拟节点的 MPNN 可以近似类似线性 Performer 的注意力，因此即使是经典的 GCN 和充满虚拟节点的 GatedGCN 在远程图任务中也显示出相当 SOTA 的性能（我们发布了LGRB基准（https://github.com/vijaydwivedi75/lrgb））去年正是为了测量 GNN 和 GT 的远程能力）。

https://openreview.net/forum?id=3Ge74dgjjU

受视觉模型启发的一些基于patch的GT 子采样方法：He 等人的“ViT/MLP-Mixer to Graphs 的泛化（https://openreview.net/forum?id=l7yTbEWuOQ）”将输入拆分为多个patches，使用 GNN 将每个patch编码为token，然后在这些token上运行transformer。

A Generalization of ViT/MLP-Mixer to Graph（https://openreview.net/forum?id=l7yTbEWuOQ）

在Kong 等人的GOAT（https://openreview.net/forum?id=Le2dVIoQun）中，节点特征通过 K-Means 投影到 K 个簇的codebook中，并且每个节点的采样 3 跳邻域参与该codebook。GOAT 是一个单层模型，可扩展到数百万个节点的图。

有向图也得到了一些Transformer的喜爱。Geisler 等人的“Transformers Meet Directed Graphs（https://openreview.net/forum?id=a7PVyayyfp）”介绍了Magnetic Laplacian磁性拉普拉斯算子——具有非对称邻接矩阵的有向图拉普拉斯算子的推广。Magnetic Laplacian磁拉普拉斯算子的特征向量与定向随机游走相结合，是transformer的强大输入特征，可以在OGB Code2（https://ogb.stanford.edu/docs/leader_graphprop/#ogbg-code2）图属性预测数据集上设置新的 SOTA！

最后但并非最不重要的一点是，我们在社区标准 ZINC 数据集上有了一个新的 SOTA GT — Ma、Lin 等人的GRIT （https://openreview.net/forum?id=HjMdlNgybR），它结合了完整的d维随机游走矩阵，称为相对随机游走概率 (RRWP)，作为边特征注意力计算（作为比较，流行的RWSE（https://openreview.net/forum?id=wTTjnvGphYj）特征只是该矩阵的对角元素）。事实证明，RRWP 比最短路径距离功能更强大，并在 ZINC 上创下了 0.059 MAE 的历史新低（低于 GraphGPS 的 0.070）。GRIT 在其他基准测试中也常常优于 GPS。同样，Eliasof （https://openreview.net/forum?id=1Nx2n1lk5T）等人提出了一个巧妙的想法，将随机特征和光谱特征结合起来作为位置编码，其性能优于 RWSE，但尚未在 GT 中进行尝试。

理论：GNN 的 VC 维度，深入探讨over-squashing过度挤压

VC维度（https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension）衡量模型容量和表达能力。它在经典机器学习算法中得到了很好的研究，但令人惊讶的是，它从未被应用于研究 GNN。在Morris 等人的“WL meet VC（https://openreview.net/forum?id=rZN3mc5m3C）”中，WL 测试和 VC 维度之间的联系终于被揭示了——事实证明 VC 维度可以由 GNN 权重的bitlength位长限制，即 float32 权重意味着 VC 维度为32. 此外，VC 维度以对数方式取决于给定任务中唯一 WL 颜色的数量，以多项式方式取决于深度和层数。这是一个很棒的理论结果。

WL meet VC（https://openreview.net/forum?id=rZN3mc5m3C）

over-squashing过度挤压效应——当你试图填充来自太多相邻节点的消息时会导致信息丢失——是 MPNN 的另一个常见问题，我们并不完全理解如何正确处理它。今年，有 3 篇论文专门讨论这个主题。也许最具基础性的是Di Giovanni （https://openreview.net/forum?id=t2tTfWwAEl）等人的工作，他们解释了 MPNN 的宽度、深度和图拓扑如何影响过度挤压。

https://openreview.net/forum?id=t2tTfWwAEl

事实证明，宽度可能有帮助（但存在泛化问题），深度并没有真正的帮助，而图拓扑（以节点之间的通勤时间为特征）起着最重要的作用。我们可以通过各种图重新布线策略（根据空间或光谱属性添加和删除边）来减少通勤时间，其中有很多策略（您可能听说过基于Ricci 流的重新布线（https://openreview.net/forum?id=7UmjRGzp-A），该策略获得了杰出论文奖） ICLR 2022）。事实上，这项研究还有一项后续工作（https://arxiv.org/abs/2306.03589），该工作更加深入，并导出了一些关于过度挤压的不可能性陈述和一些 MPNN 属性。

Effective resistance有效阻力是空间重新布线策略的一个例子，Black （https://openreview.net/forum?id=50SO1LwcYU）等人对其进行了详细研究。基于 Ricci 流的重新布线与图曲率一起工作，并在Nguyen （https://openreview.net/forum?id=eWAvwKajx2）等人的工作中进行了进一步研究。

子图 GNN 继续受到关注：两篇作品（Zhang、Feng、Du （https://openreview.net/forum?id=2Hp7U3k5Ph）等人和Zhou 、Wang、Zhang（https://openreview.net/forum?id=K07XAlzh5i））同时导出了最近提出的子图 GNN 的表达层次结构及其与 1 阶和高阶 WL 的关系测试。

新的 GNN 架构：Delays延迟和Half-hops半跳

如果厌倦了 GCN 或 GAT 的另一种变体，这里有一些新鲜的想法，可以与任何 GNN 一起使用：

正如从理论部分了解到的，重新布线有助于对抗过度挤压。Gutteridge （https://openreview.net/forum?id=WEgjbJ6IDN）等人介绍了“DRew：Dynamically Rewired Message Passing with Delay带延迟的动态重新连接消息传递”，它逐渐致密了后面的 GNN 层中的图，使得长距离节点可以看到先前节点的原始状态（原始 DRew），或者基于以下内容添加那些跳过连接延迟- 取决于两个节点之间的距离（vDrew 版本）。例如，在 vDrew 延迟消息传递中，第 0 层的起始节点将向第 1 层的 2 跳邻居显示其状态，并将向第 2 层的 3 跳邻居显示其状态。DRew 显着改进普通 GNN 执行远程任务的能力。事实上，用 DRew 的 GCN 是Long Range Graph Benchmark（https://github.com/vijaydwivedi75/lrgb）的 Peptides-func 数据集上的当前SOTA。

https://openreview.net/forum?id=WEgjbJ6IDN

Azabou （https://openreview.net/forum?id=lXczFIwQkv）等人的另一个好主意是通过在每个边插入具有特殊连接模式的新的慢速节点来减慢消息传递——只有来自起始节点的传入连接和与目标节点的对称边。慢节点极大地提高了普通 GNN 在异性基准上的性能，并且还可以通过为同一原始图创建具有不同位置的慢节点的视图来使用慢节点进行自监督学习。HalfHop是一个显而易见的 SSL 组件，可以提高性能，并且应该成为许多 GNN 库的标准套件中。

https://openreview.net/forum?id=lXczFIwQkv

生成模型 – Molecules分子的Stable Diffusion稳定扩散、Discrete Diffusion离散扩散

扩散模型可能在特征空间（例如，图像生成中的像素空间，如原始 DDPM）或潜在空间（如稳定扩散）中工作。在特征空间中，必须设计噪声过程以尊重特征空间的对称性和等变性。在潜在空间中，可以将高斯噪声添加到（预训练的）编码器生成的特征中。大多数 3D 分子生成模型在特征空间中工作（如开创性的EDM（https://arxiv.org/abs/2203.17003））， Xu 等人（著名的GeoDiff（https://arxiv.org/abs/2203.02923）的作者）的新GeoLDM（https://openreview.net/forum?id=sLfHWWrfe2）模型是第一个定义3D 分子生成的潜在扩散的模型。也就是说，在训练 EGNN 自动编码器之后，GeoLDM 在降噪目标上进行训练，其中噪声是从标准高斯采样的。GeoLDM 比 EDM 和其他非潜在扩散方法带来了显着改进。

GeoLDM（https://openreview.net/forum?id=sLfHWWrfe2）

在非几何图领域（仅具有邻接和分类节点特征），DiGress (ICLR’23)（https://openreview.net/forum?id=UaAD-Nu86WX） 首创的离散图扩散似乎是最适用的选择。Chen 等人提出了EDGE（https://openreview.net/forum?id=vn9O1N5ZOw），一种由节点度分布引导的离散扩散模型。与 DiGress 相比，EDGE 中的最终目标图是没有边的断开图，前向噪声模型通过伯努利分布删除边，反向过程将边添加到最近的活动节点（活动的是度数在上一步）。由于度数引导引入的稀疏性，EDGE 可以生成多达 4k 个节点和 40k 个边的相当大的图！

Graph Generation with EDGE（https://openreview.net/forum?id=vn9O1N5ZOw）

最后，Weilbach 等人的“图结构扩散模型（https://openreview.net/forum?id=24wzmwrldX）”弥合了连续生成模型和概率图模型之间的差距，这些模型在感兴趣的问题中引入了某种结构 – 通常此类问题具有组合性质。中心思想是将问题的结构编码为尊重排列不变性的注意掩码，并在 Transformer 编码器的注意计算中使用此掩码（根据定义，除非使用位置嵌入，否则它与输入标记排列等价）。GSDM可以处理二进制连续矩阵分解、布尔电路、可以生成数独并执行排序。

GSDM 任务注意力偏差Graphically Structured Diffusion Models（https://openreview.net/forum?id=24wzmwrldX）
Geometric几何学习：几何WL、Clifford代数

Geometric Deep Learning几何深度学习蓬勃发展！提出了很多有趣的论文。

几何 WL（https://openreview.net/forum?id=6Ed3gchl9L）终于出现在Joshi、Bodnar 等人的作品中。几何 WL 使用几何特征（例如，坐标或速度）扩展了 WL 测试的概念，并导出高达 k 阶 GWL 的表达层次。关键要点：等变模型比不变模型更具表现力（请注意，在完全连接的图中，差异消失）；特征的张量顺序提高了表现力；特征的主体顺序提高了表现力。也就是说，球面 > 笛卡尔 > 标量，多体相互作用 > 只有距离。本文还介绍了令人惊叹的学习资源Geometric GNN Dojo（https://github.com/chaitjo/geometric-gnn-dojo），您可以在其中从第一原理推导出并实现大多数 SOTA 模型！

https://openreview.net/forum?id=6Ed3gchl9L

除了矢量到 Clifford 代数，Ruhe（https://openreview.net/forum?id=DNAJdkHPQ5）等人还推导了几何 Clifford 代数网络(GCAN)。Clifford 代数自然地通过双向量、三向量和多向量支持高阶交互。关键思想是Cartan-Dieudonné 定理（https://en.wikipedia.org/wiki/Cartan%E2%80%93Dieudonn%C3%A9_theorem），即每个正交变换都可以分解为超平面中的反射，并且几何代数将数据表示为Pin(p,q,r)群的元素。GCAN 引入了线性层、归一化、非线性的概念，以及如何通过神经网络对它们进行参数化。实验包括fluid dynamics流体动力学和Navier-Stokes纳维-斯托克斯方程建模。

https://openreview.net/forum?id=DNAJdkHPQ5

事实上，已经有一项后续工作介绍了等变 Clifford NN – 您可以了解有关 Clifford 代数基础的更多信息以及Microsoft Research 支持的有关CliffordLayers（https://microsoft.github.io/cliffordlayers/）的最新论文。

Equivariant等变 GNN (EGNN)（http://proceedings.mlr.press/v139/satorras21a/satorras21a.pdf） 是几何 DL 中的Aspirin阿司匹林，几乎应用于所有任务，并且已经有了相当多的改进。Eijkelboom （https://openreview.net/forum?id=hF65aKF8Bf）等人将 EGNN 与在高阶结构（即simplicial complexes单纯复形（https://arxiv.org/abs/2103.03212））上运行的单纯形网络结合到EMPSN中。这是第一个结合几何和拓扑特征的例子，具有巨大的改进潜力！最后，Passaro 和 Zitnick（https://openreview.net/forum?id=QIejMwU0r9）推导出一个巧妙的技巧，将 SO(3) 卷积减少到 SO(2)，将复杂性从 O(L⁶) 降低到 O(L³)，但保证数学等价。这一发现允许在 OpenCatalyst 等更大的数据集上扩展几何模型，并且已经进入Equiformer V2（https://arxiv.org/abs/2306.12059） – 很快就会出现在许多其他几何模型库中。

Molecules分子：2D-3D 预训练、MD 中的不确定性估计

Liu Du （https://openreview.net/forum?id=mPEVwu50th）等人提出了MoleculeSDE，这是一种针对分子数据进行联合 2D-3D 预训练的新框架。除了标准对比损失之外，作者还添加了两个生成组件：通过基于score分数的扩散生成重建 2D -> 3D 和 3D -> 2D 输入。MoleculeSDE 使用标准 GIN 和 SchNet 作为 2D 和 3D 模型，在 PCQM4M v2 上进行了预训练，并且在下游微调任务上表现良好。

MoleculeSDE（https://github.com/chao1224/MoleculeSDE）

Wollschläger （https://openreview.net/forum?id=DjwMRloMCO）等人对molecular dynamics分子动力学和force fields力场的 GNN 中的不确定性估计进行了全面的研究。作者确定了关键的物理知识和以应用为中心的原则，提出了一种局部神经核（ Localized Neural Kernel），这是对任何几何 GNN 的基于Gaussian高斯过程的扩展，适用于invariant不变量和equivariant等变量（在 SchNet、DimeNet 和 NequIP 上尝试过）。在许多情况下，LNK 对一个模型的估计与需要训练多个模型的成本高昂的集成相当或更好。

https://openreview.net/forum?id=DjwMRloMCO

材料和Proteins蛋白质：蛋白质 CLIP、Ewald 消息传递、Equivariant等变增强

CLIP 及其后代已成为文本到图像模型的标准主要内容。我们可以做同样的事情在text-to-protein文本到蛋白质。

Xu Yuan （https://openreview.net/forum?id=ZOOwHgxfR4）等人提出了ProtST，这是一个用于学习文本蛋白质描述（通过 PubMedBERT）和蛋白质序列（通过 ESM）联合表示的框架。除了对比损失之外，ProtST 还具有多模态掩模预测目标，例如，掩模文本和蛋白质序列中 15% 的标记，并基于潜在表示联合预测这些标记，以及仅基于序列或语言的掩模预测损失。此外，作者还设计了一个新颖的ProtDescribe数据集，其中包含 55 万个对齐的蛋白质序列描述对。ProtST在PEER（https://github.com/DeepGraphLearning/PEER_Benchmark）基准测试中的许多蛋白质建模任务中表现出色，包括蛋白质功能注释和定位，但也允许直接从文本描述中进行零样本蛋白质检索（参见下面的示例）。看起来ProtST作为许多蛋白质生成模型背后的支柱有着光明的前景。

https://openreview.net/forum?id=ZOOwHgxfR4

实际上，ICML 具有多种蛋白质生成工作，例如Lin 和 AlQuraishi（https://openreview.net/forum?id=4Kw5hKY8u8）的GENIE以及Yim、Trippe、De Bortoli、Mathieu 等人的FrameDiff（https://openreview.net/forum?id=m8OUBymxwv）- 这些工作尚未以文本描述为条件，因此在其中合并 ProtST 看起来毫无疑问会带来性能提升。

SE(3) Diffusion（https://github.com/jasonkyuyim/se3_diffusion）

分子上的 MPNN 具有严格的局部性偏差，抑制了远程相互作用的建模。Kosmala （https://openreview.net/forum?id=vd5JYAml0A）等人推导出Ewald 消息传递，并应用Ewald 求和（https://en.wikipedia.org/wiki/Ewald_summation）的思想，将交互潜力分解为短程和长程项。短程交互可以通过任何 GNN 进行建模，而远程交互是新的，可以通过3D 傅里叶变换和通过Fourier傅里叶频率传递消息来建模。事实证明，这个长期术语非常灵活，可以应用于任何对周期性和非周期性系统（如晶体或分子）进行建模的网络，例如 SchNet、DimeNet 或 GemNet。该模型在 OC20 和 OE62 数据集上进行了评估。如果对更多详细信息感兴趣，请查看LOG2 阅读小组Arthur Kosmala 的 1 小时演讲（https://www.youtube.com/watch?v=Ip8EGde5SUQ）！

https://openreview.net/forum?id=vd5JYAml0A

Lin 等人在PotNet（https://openreview.net/forum?id=jxI4CulNr1）中使用了对 3D 晶体使用 Ewald 求和的类似想法，其中使用不完整的Bessel贝塞尔函数对远程连接进行建模。PotNet 在 Materials Project 数据集和 JARVIS 上进行了评估——因此阅读这两篇论文，可以很好地理解 Ewald 求和为许多晶体相关任务带来的好处。

https://openreview.net/forum?id=jxI4CulNr1

Duval、Schmidt 等人在FAENet（https://openreview.net/forum?id=HRDRZNxQXc）中给出了关于为任何GNN赋予晶体和分子等变性的另一种观点。一种标准方法是将某些对称性和等变性直接融入到 GNN 架构中（例如 EGNN、GemNet 和 Ewald 消息传递）——这是一种安全但计算成本昂贵的方法（特别是当涉及球谐函数和张量积时）。视觉中经常使用的另一个选项是显示相同输入的许多增强，并且模型最终应该在增强中学习相同的不变性。作者选择了第二条路径，并设计了一种严格的方法来对 2D / 3D 数据不变或等变增强（例如，分别针对能量或力）进行采样，所有这些都带有精美的证明。为此，数据增强管道包括将 2D / 3D 输入投影到规范表示（基于距离协方差矩阵的 PCA），可以从中均匀地采样旋转。

所提出的 FAENet 是一个简单的模型，仅使用距离，但通过随机帧平均数据增强表现出非常好的性能，同时速度提高了 6-20 倍。也适用于晶体结构！

Augmentations and Stochastic Frame Averaging增强和随机帧平均（https://openreview.net/forum?id=HRDRZNxQXc）

炫酷应用：算法推理、归纳 KG 完成、Mass Spectra质谱 GNN

本节中的一些论文不属于上述任何一类，但仍然值得关注。

Bevilacqua 等人的“具有因果正则化的神经算法推理（https://openreview.net/forum?id=kP2p67F4G7）”解决了图学习中的一个常见问题——在测试时对更大输入的 OOD 泛化。在研究算法推理问题中的 OOD 泛化时，作者发现存在许多不同的输入，它们在某个步骤中进行相同的计算。同时，这意味着输入的某些子集不会（不应该）影响预测结果。这个假设允许设计一个自我监督的目标（称为Hint-ReLIC），它更喜欢“有意义”的步骤，而不是一堆不影响预测结果的步骤。新目标将许多 CLRS-30 任务的性能显着提升至 90% 以上的 micro-F1。这是一个有趣的问题，是否可以在一般消息传递中利用相同的原理并在其他图学习任务中改进 OOD 传输。

Neural Algorithmic Reasoning with Causal Regularisation（https://openreview.net/forum?id=kP2p67F4G7）

如果对neural algorithmic reasoning神经算法推理进一步感兴趣，请查看Knowledge and Logical Reasoning workshop知识和逻辑推理研讨会（https://klr-icml2023.github.io/papers.html）的会议记录，其中有更多关于该主题的作品。

Lee 等人的“ InGram ：通过关系图进行归纳知识图嵌入（https://openreview.net/forum?id=OoOpO0u4Xd）”似乎是 ICML’23 上极少数的知识图谱论文之一。InGram是第一个可以在测试时归纳推广到看不见的实体和看不见的关系的方法之一。以前，归纳知识图谱模型至少需要学习某种形式的关系嵌入才能泛化到新节点，在这种范式中，新的看不见的关系对于建模来说并不简单。InGram 在原始多关系图之上构建关系图，即关系类型图，并通过运行 GAT 来学习基于该图的关系表示。实体表示是通过随机初始化和 GNN 编码器获得的。具有实体和关系表示，DistMult 解码器被用作评分函数。InGram 对于看不见的关系的影响力很有可能与GraIL (ICML 2020)（http://proceedings.mlr.press/v119/teru20a/teru20a.pdf）对于看不见的实体的影响力一样。

InGram: Inductive Knowledge Graph Embedding via Relation Graphs（https://openreview.net/forum?id=OoOpO0u4Xd）

Murphy 等人的“利用图神经网络有效预测高分辨率质谱（https://openreview.net/forum?id=81RIPI742h）”是 GNN 在预测质谱的实际物理问题中的一个很酷的应用。主要发现是质谱中的大部分信号是由少量成分（产物离子和中性损失公式）解释的。并且可以从训练数据中挖掘这些公式的词汇表。因此，当给定分子图时，当我们从与某些质谱值相对应的词汇表中预测标记时，问题可以被框架为图分类（或图属性预测）。GRAFF-MS方法通过具有边特征、拉普拉斯特征（通过 SignNet）的 GIN 构建分子图表示，并与协变量特征进行池化。与基线 CFM-ID 相比，GRAFF-MS 在约 19 分钟内执行推理，而无需花费 126 小时，从而达到更高的性能。

Efficiently predicting high resolution mass spectra with graph neural networks（https://openreview.net/forum?id=81RIPI742h）
Michael Galkin and Michael Bronstein

微信群                    公众号