1. Identifying and Counting Motifs in Networks
- subgraph
subgraph是网络的组成部分，可用于识别和区分不同的网络（可以说是不同种类网络会具有不同特征的subgraph）。
使用传统的discrete type matching1 方法代价很大，本文会介绍使用神经网络解决subgraph matching问题的方法。
- 以下图分子式为例：含有羧基（subgraph）的分子（graph）是羧酸（group）
2. Subgraph and Motifs
2.1 Defining Subgraphs and Motifs
- 具体使用哪种定义取决于问题领域。
如在化学领域中常使用node-induced概念（官能团），在知识图谱中常用edge-induced概念（我们关心的是代表逻辑关系的边）。
- subgraph举例
- 所有非同构的、connected、无向的4个节点的图：
- 所有非同构的、connected、有向的3个节点的图：
一般最多也就4-5个节点了
- network motifs
定义：recurring, significant patterns of interconnections
- pattern：小的node-induced subgraph
- recurring：出现很多次，即出现频率高（以下将介绍如何定义频率）
- signifant：比预期（如在随机生成的图中）出现的频率高（以下将介绍如何定义随机图）
- motif举例：
如图所示：左上角就是我们所感兴趣的induced subgraph（motif）。蓝三角内的induced subgraph符合要求，红三角内不是induced subgraph不符合要求。
- motif的意义：
1. 帮助我们了解图的工作机制。
2. 帮助我们基于图数据集中某种subgraph的出现和没有出现来做出预测3。
举例：
- feed-forward loops：神经元网络中用于中和biological noise
- parallel loops：食物链中（就两种生物以同一种生物为食并是同一种生物的猎物嘛）
- single-input modules：基因控制网络中
- subgraph frequency
- 如果数据集中包含多个图，我们可将其视为一整个大图 G T（包含disconnected components，各组成部分对应单个图）
2.2 Determining Motif Significance
- 我们首先需要定义null-model
核心思想：在真实网络中比在随机网络中出现更频繁的subgraph有functional significance
- motif significance overview
检验motif在真实网络中是否比在随机图中overrepresent的步骤：
- step1：在真实图中数motif的个数
- step2：产生多个与真实图有相同统计量（如节点数、边数、度数序列等）的随机图，在这些随机图中数motif的个数
- step3：使用统计指标衡量每一motif是否显著
- significance profile
对每个subgraph，Z-score指标可用于分类subgraph significance：负数意味着under-representation，整数意味着over-representation。
network significance profile是具有所有subgraph大小上的值的feature vector。
接下来就可以比较随机图和不同图上的profile了。
不同网络举例：
- 基因调控网络4
- 神经网络（突触连接）
- 万维网（网页超链接）
- 社交网络
- language networks (word adjacency)
- significance profile示例：
相似领域的网络会具有相似的SP。可以通过motif frequency来判断网络功能。如社交网络中的subgraph6少、但是subgraph13多，因为一个人很难同时与两人保持紧密好友关系而这两个人不互相认识，每周还要出来喝2次咖啡。毕竟如果他们认识以后就可以一周出来只约1次咖啡了。
- 检测motif总结：
- motif概念的变体：
衍生：有向/无向，colored/uncolored（应该指的是节点类型，如下图中右上角045算motif出现、345不算motif出现的情况），动态/static motif
概念上的变体：不同的frequency概念、不同的significance指标、under-representation (anti-motifs)（如下图中右下角所示）、不同的null models
- motif总结：
subgraph和motif是图的组成部分，子图同构和技术问题是NP-hrad。
理解数据集中motif的频繁或显著出现，可以使我们了解该领域的独有特征。
使用随机图作为null model来通过Z-score衡量motif的显著性。
3. Neural Subgraph Matching / Representations
- subgraph matching
给出大的target graph（可以是disconnected），query graph（connected）
问题：query graph是否是target graph中的子图？
示例如下图（节点颜色表示映射关系）：
- 在本课程中我们不用combinatorial matching、逐边检查，而将该问题视作预测任务，使用机器学习方法来解决这一问题。
直觉：利用嵌入域的几何形状来捕获子图同构的属性
- task setup
二元预测问题：返回query是否与target graph子图同构
（注意在这里我们只关注该预测问题的最终决策，即是不是。而具体的节点之间如何一一对应的关系本课程中不讲）
- overview of the approach
整体流程如图所示：将target graph拆成很多neighborhoods，嵌入neighborhoods和query，将每个neighborhood与query做匹配，判断其是否子图同构：
- neural architecture for subgraphs
- 我们将使用node-anchored定义，用anchor的嵌入来判断是否同构
- 使用node-anchored neighborhoods：
上图中应该是把右图的黄色点画成蓝色了
用GNN基于anchor的邻居得到其嵌入，预测 u 的邻居是否与 v 的邻居同构（图中应该是用了二阶邻居的意思）：
- 为什么要使用anchor呢？
回忆node-level frequency definition。这是因为我们可以用GNN来获得 u 和 v 对应的嵌入，从而可以得知 u 的邻居是否与 v 的邻居同构，这样就可以预测是否存在anchor的映射关系并识别出对应的特定节点。
总之可以用嵌入各维元素全部小于等于的关系来表示subgraph
- subgraph order embedding space
如图：在order embedding space中全部维度小于target graph的anchor嵌入的就是其subgraph的anchor嵌入（在二维嵌入域中，就是在target graph的左下角）
Corollary推论（必然的结果(或结论);）
这个valid embedding是啥东西我就没看懂
- order constraint
我们用GNN来嵌入neighborhoods并保持其order embedding结构，因此我们需要学习一种可以学习反映subgraph关系的order embedding的损失函数。
我们基于order constraint设计损失函数。order constraint规定了理想的可反映subgraph关系的order embedding属性：
- 训练细节
- 我们需要抽样出多少training examples？
每次迭代，我们都需要抽样新的target-query对。
这样做的好处是每次模型都会看到不同的subgraph例子，提升表现结果、避免过拟合（毕竟有指数级的可能subgraph可供抽样）
- BFS抽样应该多深？
这是一个需要平衡运行时间和表现结果的超参数，一般设置为3-5，也需要取决于数据集的大小。
4. Mining / Finding Frequent Motifs / Subgraphs
- finding frequent subgraphs
找最频繁的大小为k的motif需要解决两个挑战：
- 迭代所有大小为k的connected subgraph
- 数每一类subgraph的出现次数
- 这个问题难在仅确定一个特定subgraph是否存在于图中就已是计算代价很高的问题（subgraph isomorphism是NP-complete），计算用时随subgraph指数级增长（因此传统方法可行的motif尺寸都相对较小，如3-7）。
可以说这是两个指数级增长的问题梦幻联动（特定大小有多少motif（组合爆炸combinatorial explosion）+找出每个motif的frequency（subgraph isomorphism and subgraph counting））
- 使用表示学习的方法来解决问题
表示学习通过search space（每次增加一个节点，累积到size k的subgraph上，详情见下文。注意我们仅关心高频subgraph）解决组合爆炸问题，通过GNN预测解决subgraph isomorphism问题（就是本章第三节所讲述的知识）。
- SPMiner overview
SPMiner：识别高频motifs的神经网络模型
步骤：将输入图 G T decompose为重复的node-anchored neighborhoods，将subgraph嵌入到order embedding space（上述两步和neural subgraph matching是一样的）；然后进行search procedure，策略是不遍历所有可能的subgraph，而直接从2个节点的图开始增长出一个所需节点数的subgraph，在增长的同时尽量保证频率高。
- SPMiner：核心思想
order embedding的核心优势：可以迅速找到特定subgraph G Q
的频率
- SPMiner search procedure
- 开始：从一个从target graph中随机选择的起点 u开始：设 S = { u }所有neighborhoods都在一个点的右上方区域，即都包含这个subgraph。
- 迭代：每次选一个 S 中节点的邻居，加到 S 中，如此逐渐增长motif的尺寸。
目标：在 k 步后最大化红色阴影区域中的neighborhoods数目。
- 停止：达到预期motif尺寸后，选取the subgraph of the target graph induced by S
我们找到的motif就是预期尺寸备选subgraph嵌入中有最多target graph neighborhoods（蓝点）在红色区域的subgraph。
- 实验结果
- 小motif
ground truth：通过代价高昂的BF迭代算法（暴力破解）找到10个出现频率最高的motif。
在大小为5-6的motif上，SPMiner可以识别出top 10中前9/8个，识别出的频率接近真实值：
- 大motif
SPMiner比baseline多识别10-100倍。
- 总结
- subgraph和motif是可用于深入了解图结构的重要概念，对其计数可用作节点或图的特征。
- 本章介绍一种预测subgraph isomorphism关系的神经网络方法。
- order embeddings的特性可用于编码subgraph关系。
- order embedding space上的neural embedding-guided search让我们有了一种比传统方法能识别出更高motif频率的机器学习模型。
