大家好，又见面了，我是你们的朋友全栈君。

有问题欢迎留言讨论

Weisfeiler-Lehman图同构测试及其他

Weisfeiler-Lehman Test (WL Test)

Boris Weisfeiler and Andrey Lehman, 1968

Graph Isomorphism

一个简单的同构图例子：

1-dimensional WL Test

输入：两个可有节点属性的图

输出：两个图是否同构（满足WL Test是两图同构的必要条件）

• 演示1
  

• 演示2
  

• 更加具体的描述

• 稳定状态

• 失效情况

注意这里和原ppt不同，2-WL其实应该是无法区分这个六边形和两个三角形的。（一种说法是1-WL和2-WL的能力其实是一样的。）

k-dimensional WL Test

3维的WL Test首先枚举图中所有三个点的组合，初始化标签，然后按照类似的方法进行细化。

k维的WL Test考虑了k个节点的组合。

Morgan Algorithm

Morgan, 1965

• Chemical Fingerprints (ECFP)

  The ECFP generation process has three sequential stages:

  1. An initial assignment stage in which each atom has an integer identifier assigned to it.
  2. An iterative updating stage in which each atom identifier is updated to reflect the identifiers of each atom’s neighbors, including identification of whether it is a structural duplicate of other features.
  3. A duplicate identifier removal stage in which multiple occurrences of the same feature are reduced to a single representative in the final feature list. (The occurrence count may be retained if one requires a set of counts rather than a standard binary fingerprint.)

  1. 初始化原子标识符。哈希函数处理非氢原子属性（原子序号、连接性等），得到一个整数
  2. 标志符的迭代更新。类似Mogan算法，但是迭代次数是预先设定的，不追求得到1-WL的区分度。
  3. 标识符去重。保留所有不同的标识符，压缩到一个比特串中。

• Canonical SMILES

利用Mogan算法迭代连通度，直到稳定（更新后连通度直方图形状不变），利用连通度进行排序，得到唯一的SMILES记法。（这种算法是商业化的，所以计算Canonical SMILES要用Daylight软件。）

Message-Passing Neural Network (MPNN)

Weisfeiler-Lehman Netwrok (WLN)

WLN的思想是将1-WL 中离散的呈指数增长的节点标签用嵌入向量代替

用于预测有机分子化学反应，NeurIPS 2017

MPNN

消息传递网络MPNN是一种聚合邻近点信息的图神经网络框架。

MPNN contains two phases, a message passing phase (namely the propagation step) and a readout phase.

• The message passing phase runs for T times and is defined by message function Mt and vertex update function Ut.

where $m_v^t$ is message and $e_{vw}$ is the feature of the edge from node v to w

• The reader phase computes a feature vector for the whole graph using readout function

How Powerful Are Graph Neural Networks？

ICLR 2019

WL Test & MPNN

• MPNN

• 1d WL Test

1-WL 是MPNN类型的GNN的性能上界

不过利用WL得到的节点特征是离散的，或者说是one hot类型的，不能用于计算图的相似度等。

• 设计合适的更新函数和聚合函数非常重要
• 常用的聚合函数如MAX、MEAN不能处理的一些情况

聚合函数需要是 单射(injective) 的，即函数不同的输入不能有相同的输出。

Graph Isomorphism Networks (GIN)

• 更新（以及聚合）函数：MLP+SUM
  • 存在这样一个函数是单射的

• 用MLP拟合$f\varphi$

• READOUT函数

实验（图分类 Graph Classification)

训练集：

测试集：

Beyond WL

Beyond 1-WL

non local

基于k-WL及各种变种k-WL设计的网络，虽然理论很好但实际效果不佳。

• k-GNNs 需要$O(n^k)$级别内存
• Invariant Graph Networks (IGN) based on k-order tensors
  • 3-WL 级别的IGN有平方级别的复杂度，但较MPNN的线性复杂度还是略显臃肿

Beyond WL

• GSN 在MPNN的基础上，使聚合的信息包括局部图结构（保留了局部性和线性复杂度）

• 近似同构，用某种度量来衡量两图的相似性

Reference

Michael Bronstein’s Blog (Recommended)

• Expressive power of graph neural networks and the Weisfeiler-Lehman test
• Beyond Weisfeiler-Lehman: using substructures for provably expressive graph neural networks
• Beyond Weisfeiler-Lehman: approximate isomorphisms and metric embeddings

WL Test

• Combinatorial Properties of the Weisfeiler-Leman Algorithm by Sandra Kiefer
• Weisfeiler-lehman graph kernels
• On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties

Chemical Fingerprint

• Extended Connectivity Fingerprint ECFP
• Extended-Connectivity Fingerprints J.chem 2010

WLN

• Predicting organic reaction outcomes with weisfeiler-lehman network NeurIPS2017

MPNN

• Graph neural networks: A review of methods and applications arXiv 2018
• Neural message passing for quantum chemistry arXiv 2017

GIN

• How powerful are graph neural networks? ICLR 2019