https://arxiv.org/abs/1904.01543

https://www.github.com/chrsmrrs/sparsewl

Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings

1. 论文概述

1.1 论文摘要

Graph kernels based on the 1-dimensional Weisfeiler-Leman algorithm and corr-esponding neural architectures recently emerged as powerful tools for (supervised) learning with graphs. However, due to the purely local nature of the algorithms,they might miss essen-tial patterns in the given data and can only ha-ndle binary relations. The k-dimensional Weisfeiler-Leman algorithm address-es this by considering k-tuples, defined over the set of vertices, and defines a suitab-le notion of adjacency between these vertex tuples. Hence, it accounts for the higher-order interactions between vertices. However, it does not scale and may suffer from overfitting when used in a machine learning setting. Hence, it remains an important open problem to design WL-based graph learning methods that are simultan-eously expressive, scalable, and non-overfitting. Here, we propose local variants and corresponding neural architectures, which consid-er a subset of the original neighborhood, making them more scalable, and less prone to overfitting. The expressive power of (one of) our algorithms is strictly higher than the original algorithm, in terms of ability to distinguish non-isomorphic graphs. Our experimental study confirms that the local algorithms, both kernel and neural architectures,lead to vastly reduced computation times, and prevent overfitting. The kernel version establishes a new state-of-the-art for graph classi-fication on a wide range of benchmark datasets, while the neural version shows promising performance on large-scale molecular regression tasks.

基于1维WL算法及其对应的神经架构的图kernels已经成为了有监督图学习中非常强大的工具。但是，由于这些算法天然的纯局部性，它们可能会错过一些给定数据上的基本模式，并且只能处理二元关系。k维WL算法通过考虑顶点集上的k元组并且给这些顶点元组之间定义了一个合适的adjacency概念解决了这一问题，解释了顶点之间的高阶交互。但是它无法缩放，并且在及其学习的设置下可能会过拟合。因此，设计具有课表大型、可伸缩和non overfitting的基于WL的图学习方法任然是一个重要且开放的问题。本文中作者提出了局部变量和其对应的神经架构，它们使用原始邻域的一个子集，从而使模型更具伸缩性，并且不太容易过拟合。就区分非同构图而言，作者的算法的表现要优于原始算法。实验研究表明无论是基于kernel还是基于神经网络，作者的局部算法都能够大幅缩减计算时间，并防止过拟合。kernel版本的算法为许多基准数据集建立了新的state-of-the-art，而neural版本算法在大规模分子回归任务中也展现了promising性能。

1.2 内容简介

从化学生物到图片和社交网络，图结构的数据非常普遍存在的。为了在这些领域发展有效的机器学习模型，我们需要一些技术能够探索隐藏在图结构内部以及节点和边中的大量信息。近些年来，许多用于图学习的方法被提出，大部分都是基于graph kernel或者GNN。其中基于1维WL的graph kernel及其对应的GNNs取得了有监督图学习中最先进的结果。但是1维WL有两个缺点：

• 通过简单地聚合邻居信息，其纯局部性特点会使得模型忽略一些数据中的重要模式。
• 它只适用于二元结构，不能直接用于处理一般的t元结构，比如超图或者子图。

一个性能更强的算法是$k-WL$，通过给k元组分配颜色而不是单个节点，它能捕捉范围更广、更高阶的模式。但是它领域的基数是$k·n$，其中n表示整个图的节点数，因此其每次迭代的运行时间没有考虑图的稀疏性。另外，研究人员提出了和$k-WL$能力相当的神经网络架构，但是面临着同样地问题，必须使用$dense$矩阵乘法。

本文为了解决这一问题提出了$\delta-k-LWL$算法，它在每次迭代过程中只考虑局部邻居。因此，局部邻居的基数依赖于图的稀疏性。

之后作者从理论上分析了他们提出的这种$WL$变体在判别非同构图问题上比$k-WL$更强，并设计了一些$\delta-k-LWL$可以区分但是$k-WL$无法区分的非同构图。

在神经网络方面，作者给出了对应的神经网络版本$\delta-k-LGNN$，并证明了它和$\delta -k-LWL$具有相同的能力。

2. 算法

2.1 先验知识

1. 符号表示

   （1）

1

<h1>未完待续... ...</h1>