大家好，又见面了，我是你们的朋友全栈君。
有问题欢迎留言讨论
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:
- An initial assignment stage in which each atom has an integer identifier assigned to it.
- 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.
- 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.)
- 初始化原子标识符。哈希函数处理非氢原子属性（原子序号、连接性等），得到一个整数
- 标志符的迭代更新。类似Mogan算法，但是迭代次数是预先设定的，不追求得到1-WL的区分度。
- 标识符去重。保留所有不同的标识符，压缩到一个比特串中。
- 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 m_v^t mvt is message and e v w e_{vw} evw 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 ϕ f\phi fϕ
- READOUT函数
实验（图分类 Graph Classification)
训练集：
测试集：
Beyond WL
Beyond 1-WL
non local
基于k-WL及各种变种k-WL设计的网络，虽然理论很好但实际效果不佳。
- k-GNNs 需要 O ( n k ) O(n^k) O(nk)级别内存
- 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
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/126245.html原文链接：https://javaforall.cn