大家好,又见面了,我是你们的朋友全栈君。
有问题欢迎留言讨论
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
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/126245.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...