cs224w(图机器学习)2021冬季课程学习笔记15 Frequent Subgraph Mining with GNNs

简介: 本章主要内容:本章首先介绍了图中motif / subgraph的概念,以及对motif significance的定义(即定义图中的subgraph要比null model多/少出多少才算显著,以及如何生成null model)。接下来介绍了神经网络模型下的subgraph matching方法(同时也是subgraph的表示方法)。最后介绍如何找到图中出现频率较高的motif / subgraph。

1. Identifying and Counting Motifs in Networks


  1. subgraph

subgraph是网络的组成部分,可用于识别和区分不同的网络(可以说是不同种类网络会具有不同特征的subgraph)。

使用传统的discrete type matching1 方法代价很大,本文会介绍使用神经网络解决subgraph matching问题的方法。

image.png


  1. 以下图分子式为例:含有羧基(subgraph)的分子(graph)是羧酸(group)

image.png


2. Subgraph and Motifs


2.1 Defining Subgraphs and Motifs

image.png

image.png

image.png

image.png


  1. 具体使用哪种定义取决于问题领域。

如在化学领域中常使用node-induced概念(官能团),在知识图谱中常用edge-induced概念(我们关心的是代表逻辑关系的边)。

image.png

image.png

image.png

image.png

image.png

image.png

image.png


  1. subgraph举例
  • 所有非同构的、connected、无向的4个节点的图:

image.png

  • 所有非同构的、connected、有向的3个节点的图:

image.png

一般最多也就4-5个节点了


  1. network motifs

定义:recurring, significant patterns of interconnections

  • pattern:小的node-induced subgraph
  • recurring:出现很多次,即出现频率高(以下将介绍如何定义频率)
  • signifant:比预期(如在随机生成的图中)出现的频率高(以下将介绍如何定义随机图)

image.png


  1. motif举例:

image.png

如图所示:左上角就是我们所感兴趣的induced subgraph(motif)。蓝三角内的induced subgraph符合要求,红三角内不是induced subgraph不符合要求。


  1. motif的意义:

 1. 帮助我们了解图的工作机制。

 2. 帮助我们基于图数据集中某种subgraph的出现和没有出现来做出预测3。


举例:

  • feed-forward loops:神经元网络中用于中和biological noise

image.png

  • parallel loops:食物链中(就两种生物以同一种生物为食并是同一种生物的猎物嘛)

image.png

  • single-input modules:基因控制网络中

image.png

image.png


  1. subgraph frequency

image.png

image.png

image.png

image.png

  1. 如果数据集中包含多个图,我们可将其视为一整个大图 G T(包含disconnected components,各组成部分对应单个图)

image.png


2.2 Determining Motif Significance

  1. 我们首先需要定义null-model

核心思想:在真实网络中比在随机网络中出现更频繁的subgraph有functional significance

image.png

image.png

image.png

image.png

image.png

image.png


  1. motif significance overview

检验motif在真实网络中是否比在随机图中overrepresent的步骤:

  • step1:在真实图中数motif的个数
  • step2:产生多个与真实图有相同统计量(如节点数、边数、度数序列等)的随机图,在这些随机图中数motif的个数
  • step3:使用统计指标衡量每一motif是否显著

image.png

image.png

image.png


  1. significance profile

对每个subgraph,Z-score指标可用于分类subgraph significance:负数意味着under-representation,整数意味着over-representation。

network significance profile是具有所有subgraph大小上的值的feature vector。

接下来就可以比较随机图和不同图上的profile了。

不同网络举例:

  • 基因调控网络4
  • 神经网络(突触连接)
  • 万维网(网页超链接)
  • 社交网络
  • language networks (word adjacency)

image.png


  1. significance profile示例:

image.png

相似领域的网络会具有相似的SP。可以通过motif frequency来判断网络功能。如社交网络中的subgraph6少、但是subgraph13多,因为一个人很难同时与两人保持紧密好友关系而这两个人不互相认识,每周还要出来喝2次咖啡。毕竟如果他们认识以后就可以一周出来只约1次咖啡了。


  1. 检测motif总结:

image.png

  1. motif概念的变体:

衍生:有向/无向,colored/uncolored(应该指的是节点类型,如下图中右上角045算motif出现、345不算motif出现的情况),动态/static motif

概念上的变体:不同的frequency概念、不同的significance指标、under-representation (anti-motifs)(如下图中右下角所示)、不同的null models

image.png


  1. motif总结:

subgraph和motif是图的组成部分,子图同构和技术问题是NP-hrad。

理解数据集中motif的频繁或显著出现,可以使我们了解该领域的独有特征。

使用随机图作为null model来通过Z-score衡量motif的显著性。

image.png


3. Neural Subgraph Matching / Representations


  1. subgraph matching

给出大的target graph(可以是disconnected),query graph(connected)

问题:query graph是否是target graph中的子图?

示例如下图(节点颜色表示映射关系):

image.png


  1. 在本课程中我们不用combinatorial matching、逐边检查,而将该问题视作预测任务,使用机器学习方法来解决这一问题。

直觉:利用嵌入域的几何形状来捕获子图同构的属性

image.png


  1. task setup

二元预测问题:返回query是否与target graph子图同构

(注意在这里我们只关注该预测问题的最终决策,即是不是。而具体的节点之间如何一一对应的关系本课程中不讲)

image.png


  1. overview of the approach

整体流程如图所示:将target graph拆成很多neighborhoods,嵌入neighborhoods和query,将每个neighborhood与query做匹配,判断其是否子图同构:

bac1f3f0e6a443e6b4cc7a843f5f0005.png


  1. neural architecture for subgraphs
  • 我们将使用node-anchored定义,用anchor的嵌入来判断是否同构

image.png

  • 使用node-anchored neighborhoods:

image.png

上图中应该是把右图的黄色点画成蓝色了


用GNN基于anchor的邻居得到其嵌入,预测 u 的邻居是否与 v  的邻居同构(图中应该是用了二阶邻居的意思):

image.png


  1. 为什么要使用anchor呢?

回忆node-level frequency definition。这是因为我们可以用GNN来获得 u  和 v 对应的嵌入,从而可以得知 u 的邻居是否与 v  的邻居同构,这样就可以预测是否存在anchor的映射关系并识别出对应的特定节点。

c30c2b0b50164458961d278e03335df6.png

image.png

image.png

image.png

image.png

总之可以用嵌入各维元素全部小于等于的关系来表示subgraph


  1. subgraph order embedding space

如图:在order embedding space中全部维度小于target graph的anchor嵌入的就是其subgraph的anchor嵌入(在二维嵌入域中,就是在target graph的左下角)

image.png

image.png

image.png

image.png


Corollary推论(必然的结果(或结论);)

这个valid embedding是啥东西我就没看懂


  1. order constraint

我们用GNN来嵌入neighborhoods并保持其order embedding结构,因此我们需要学习一种可以学习反映subgraph关系的order embedding的损失函数。

我们基于order constraint设计损失函数。order constraint规定了理想的可反映subgraph关系的order embedding属性:

image.png

image.png

image.png

image.png

3a60f781b0974fc08d77dc8c58fc7078.png

image.png

image.png

image.png

image.png


  1. 训练细节
  • 我们需要抽样出多少training examples?

每次迭代,我们都需要抽样新的target-query对。

这样做的好处是每次模型都会看到不同的subgraph例子,提升表现结果、避免过拟合(毕竟有指数级的可能subgraph可供抽样)

  • BFS抽样应该多深?

这是一个需要平衡运行时间和表现结果的超参数,一般设置为3-5,也需要取决于数据集的大小。

image.png

image.png

8ca0f56d0077462bb427eee60e099848.png

image.png

image.png


4. Mining / Finding Frequent Motifs / Subgraphs


  1. finding frequent subgraphs

找最频繁的大小为k的motif需要解决两个挑战:

  • 迭代所有大小为k的connected subgraph
  • 数每一类subgraph的出现次数

image.png


  1. 这个问题难在仅确定一个特定subgraph是否存在于图中就已是计算代价很高的问题(subgraph isomorphism是NP-complete),计算用时随subgraph指数级增长(因此传统方法可行的motif尺寸都相对较小,如3-7)。

可以说这是两个指数级增长的问题梦幻联动(特定大小有多少motif(组合爆炸combinatorial explosion)+找出每个motif的frequency(subgraph isomorphism and subgraph counting))

image.png


  1. 使用表示学习的方法来解决问题

表示学习通过search space(每次增加一个节点,累积到size k的subgraph上,详情见下文。注意我们仅关心高频subgraph)解决组合爆炸问题,通过GNN预测解决subgraph isomorphism问题(就是本章第三节所讲述的知识)。

image.png

image.png

image.png

image.png


  1. SPMiner overview

SPMiner:识别高频motifs的神经网络模型

步骤:将输入图 G T  decompose为重复的node-anchored neighborhoods,将subgraph嵌入到order embedding space(上述两步和neural subgraph matching是一样的);然后进行search procedure,策略是不遍历所有可能的subgraph,而直接从2个节点的图开始增长出一个所需节点数的subgraph,在增长的同时尽量保证频率高。

image.png


  1. SPMiner:核心思想

image.png


order embedding的核心优势:可以迅速找到特定subgraph G Q

 的频率

image.png

image.png

image.png


  1. SPMiner search procedure
  • 开始:从一个从target graph中随机选择的起点 u开始:设 S = { u }所有neighborhoods都在一个点的右上方区域,即都包含这个subgraph。

image.png

  • 迭代:每次选一个 S  中节点的邻居,加到 S 中,如此逐渐增长motif的尺寸。

目标:在 k 步后最大化红色阴影区域中的neighborhoods数目。

image.png

  • 停止:达到预期motif尺寸后,选取the subgraph of the target graph induced by S

我们找到的motif就是预期尺寸备选subgraph嵌入中有最多target graph neighborhoods(蓝点)在红色区域的subgraph。

image.png

image.png

image.png



  1. 实验结果
  • 小motif

ground truth:通过代价高昂的BF迭代算法(暴力破解)找到10个出现频率最高的motif。

在大小为5-6的motif上,SPMiner可以识别出top 10中前9/8个,识别出的频率接近真实值:

image.png

  • 大motif

SPMiner比baseline多识别10-100倍。

image.png


  1. 总结
  • subgraph和motif是可用于深入了解图结构的重要概念,对其计数可用作节点或图的特征。
  • 本章介绍一种预测subgraph isomorphism关系的神经网络方法。
  • order embeddings的特性可用于编码subgraph关系。
  • order embedding space上的neural embedding-guided search让我们有了一种比传统方法能识别出更高motif频率的机器学习模型。

image.png

相关文章
|
1月前
|
机器学习/深度学习 计算机视觉 Python
模型预测笔记(三):通过交叉验证网格搜索机器学习的最优参数
本文介绍了网格搜索(Grid Search)在机器学习中用于优化模型超参数的方法,包括定义超参数范围、创建参数网格、选择评估指标、构建模型和交叉验证策略、执行网格搜索、选择最佳超参数组合,并使用这些参数重新训练模型。文中还讨论了GridSearchCV的参数和不同机器学习问题适用的评分指标。最后提供了使用决策树分类器进行网格搜索的Python代码示例。
54 1
|
5月前
|
机器学习/深度学习 算法 BI
机器学习笔记(一) 感知机算法 之 原理篇
机器学习笔记(一) 感知机算法 之 原理篇
|
5月前
|
机器学习/深度学习 搜索推荐 PyTorch
【机器学习】图神经网络:深度解析图神经网络的基本构成和原理以及关键技术
【机器学习】图神经网络:深度解析图神经网络的基本构成和原理以及关键技术
1135 2
|
5月前
|
机器学习/深度学习 算法 数据可视化
技术心得记录:机器学习笔记之聚类算法层次聚类HierarchicalClustering
技术心得记录:机器学习笔记之聚类算法层次聚类HierarchicalClustering
51 0
|
5月前
|
机器学习/深度学习 分布式计算 API
技术好文:Spark机器学习笔记一
技术好文:Spark机器学习笔记一
39 0
|
6月前
|
机器学习/深度学习 自然语言处理 PyTorch
fast.ai 机器学习笔记(四)(1)
fast.ai 机器学习笔记(四)
137 1
fast.ai 机器学习笔记(四)(1)
|
6月前
|
机器学习/深度学习 数据挖掘 Python
fast.ai 机器学习笔记(一)(4)
fast.ai 机器学习笔记(一)
127 1
fast.ai 机器学习笔记(一)(4)
|
6月前
|
机器学习/深度学习 Python 文件存储
fast.ai 机器学习笔记(一)(3)
fast.ai 机器学习笔记(一)
132 1
fast.ai 机器学习笔记(一)(3)
|
6月前
|
机器学习/深度学习 算法 图计算
图机器学习入门:基本概念介绍
图机器学习是机器学习的分支,专注于处理图形结构数据,其中节点代表实体,边表示实体间关系。本文介绍了图的基本概念,如无向图与有向图,以及图的性质,如节点度、邻接矩阵。此外,还讨论了加权图、自循环、多重图、双部图、异构图、平面图和循环图。图在描述数据关系和特征方面具有灵活性,为机器学习算法提供了丰富的结构信息。
145 0
|
6月前
|
机器学习/深度学习 Python 索引
fast.ai 机器学习笔记(二)(4)
fast.ai 机器学习笔记(二)
55 0
fast.ai 机器学习笔记(二)(4)

热门文章

最新文章