图数据挖掘：算法、安全与应用

《图数据挖掘：算法、安全与应用》提供了对图数据挖掘方法的最新评述，在此基础上引申出一个前沿课题，即图数据挖掘的安全性问题，并介绍了一系列检测方法来识别图数据中的对抗样本。此外，它向读者介绍了图数据增强和子图网络以进一步增强模型，即提高其准确性和鲁棒性。最后，本书描述了这些前沿算法在各种场景中的应用，例如交通网络、社交和技术网络以及区块链交易网络等。

网络图的表征能力异常强大，它能够对事物之间任意类型的相互作用关系进行建模，因此网络图数据在生物信息、交通网络、科研合作、万维网和社交网络等领域的一系列实际场景中随处可见。图数据挖掘用于从图数据中发现有用的信息和知识。然而，网络中节点和链路及其半结构形式的复杂性在各种计算任务，如节点分类、链路预测和图分类等方面提出了挑战。在这一背景下，研究人员最近提出了各种前沿的图机器学习算法，包括图嵌入和图神经网络，显著地提升了图数据挖掘的性能。 《图数据挖掘：算法、安全与应用》提供了对图数据挖掘方法的**评述，在此基础上引申出一个前沿课题，即图数据挖掘的安全性问题，并介绍了一系列检测方法来识别图数据中的对抗样本。此外，它向读者介绍了图数据增强和子图网络以进一步增强模型，即提高其准确性和鲁棒性。最后，本书描述了这些前沿算法在各种场景中的应用，例如交通网络、社交和技术网络以及区块链交易网络等。

第1章  基于多通道图神经网络的信息源估计 1
1.1  介绍 1
1.2  相关工作 5
1.2.1  信息扩散模型 5
1.2.2  信息源检测 6
1.2.3  图神经网络 7
1.3  准备工作 8
1.4  多通道图神经网络 10
1.4.1  输入的征指数 11
1.4.2  图卷积网络 14
1.4.3  MCGNN的体系结构 15
1.4.4  损失函数 17
1.5  实验 17
1.5.1  数据集和实验装置 17
1.5.2  基线和评估指标 18
1.5.3  合成网络的结果 20
1.5.4  现实世界网络的结果 23
1.6  本章小结 26
第2章  基于超子结构网络的链路预测器 27
2.1  引言 27
2.2  现有的链路预测方法 29
2.2.1  启发式方法 29
2.2.2  基于嵌入的方法 31
2.2.3  基于深度学习的模型 32
2.3  模型介绍 33
2.3.1  问题表述 33
2.3.2  邻域归一化 34
2.3.3  构建HSN 35
2.3.4  HELP 37
2.4  实验分析 39
2.4.1  数据集 39
2.4.2  链路预测方法的比较 40
2.4.3  评价指标 40
2.4.4  实验设置 41
2.4.5  链路预测结果 41
2.4.6  参数的敏感性 45
2.5  本章小结 46
第3章  基于子图网络的宽度学习图分类方法 47
3.1  介绍 48
3.2  相关工作 49
3.2.1  子图网络 49
3.2.2  网络表示 50
3.2.3  宽度学习 50
3.3  子图网络 51
3.3.1  一阶子图网络 52
3.3.2  二阶子图网络 53
3.4  采样子图网络 55
3.4.1  采样策略 55
3.4.2  构建S2GN 58
3.5  基于S2GN的BLS分类器 59
3.5.1  图分类 59
3.5.2  BLS分类器 59
3.5.3  分类框架 62
3.6  实验 62
3.6.1  数据集 62
3.6.2  网络表示 63
3.6.3  基于SGN的图分类 64
3.6.4  基于S2GN的图分类 65
3.6.5  计算复杂度 67
3.7  总结与展望 68
第4章  子图增强及其在图数据挖掘中的应用 69
4.1  引言 69
4.2  相关工作 71
4.2.1  图分类 71
4.2.2  图学习中的数据增强 72
4.3  图分类模型演化框架 72
4.3.1  问题表述 72
4.3.2  子图增强 73
4.3.3  数据筛选 77
4.3.4  模型演化框架 77
4.4  子图增强的应用 79
4.4.1  图分类 80
4.4.2  链路预测 80
4.4.3  节点分类 82
4.4.4  实验结果 83
4.5  本章小结 86
第5章  基于图的对抗攻击：如何隐藏你的结构信息 87
5.1  背景 88
5.2  对抗攻击 90
5.2.1  问题描述 90
5.2.2  攻击分类 91
5.3  攻击策略 93
5.3.1  节点分类 93
5.3.2  链路预测 100
5.3.3  图分类 104
5.3.4  社团检测 108
5.4  本章小结 113
第6章  基于图的对抗防御：提高算法鲁棒性 115
6.1  引言 115
6.2  对抗 117
6.2.1  图对抗 117
6.2.2  平滑对抗 121
6.3  图净化 124
6.3.1  GCN-Jaccard 124
6.3.2  GCN-SVD 126
6.4  鲁棒性验证 127
6.4.1  图结构扰动下的鲁棒性验证 128
6.4.2  节点属性扰动下的鲁棒性验证 129
6.4.3  社团检测的鲁棒性验证 131
6.5  基于结构的防御 133
6.5.1  惩罚聚合GNN 133
6.5.2  鲁棒图卷积网络 135
6.6  对抗检测 137
6.6.1  基于节点分类的对抗检测 137
6.6.2  基于图分类的对抗检测 138
6.7  防御总结 140
6.8  实验和分析 142
6.8.1  对抗 142
6.8.2  对抗检测 146
6.9  本章小结 147
第7章  通过网络方法理解以太坊交易 149
7.1  介绍 149
7.2  以太坊交易数据集 151
7.3  图嵌入技术 153
7.3.1  基于因式分解的方法 153
7.3.2  基于随机游走的方法 154
7.3.3  基于深度学习的方法 155
7.3.4  其他方法 156
7.4  方法 156
7.4.1  基本定义 156
7.4.2  动态有偏游走 158
7.4.3  学习动态图嵌入 161
7.5  实验 163
7.5.1  节点分类 163
7.5.2  链路预测 165
7.6  本章小结 168
7.7  附录 169
第8章  寻找你的餐友：Yelp网络案例研究 171
8.1  介绍 171
8.2  数据描述和预处理 173
8.3  链路预测方法 176
8.3.1  相似性指数 176
8.3.2  变异图自动编码器 177
8.4  实验分析 178
8.4.1  实验设置 178
8.4.2  朋友推荐 178
8.4.3  共同觅食的预测 180
8.5  本章小结 183

第9章  基于图卷积循环神经网络的交通流量预测深度学习框架 185
9.1  研究背景 185
9.2  相关工作 187
9.2.1  图分析 187
9.2.2  交通状态预测 188
9.3  模型 189
9.3.1  图卷积神经网络 190
9.3.2  长短期记忆神经网络(LSTM) 192
9.3.3  图卷积循环神经网络 194
9.4  实验 195
9.4.1  数据集 195
9.4.2  对比实验 196
9.4.3  评价指标 196
9.4.4  评估 197
9.4.5  实验和结果分析 197
9.5  本章小结 200
第10章  基于复杂网络的时间序列分类 201
10.1  介绍 201
10.2  相关工作 203
10.2.1  时间序列分类 203
10.2.2  映射方法 204
10.2.3  图的分类 205
10.3  方法 206
10.3.1  CLPVG 206
10.3.2  基于GNN的AVG 210
10.3.3  与LPVG的比较 213
10.4  实验 214
10.4.1  数据集 214
10.4.2  实验设置 215
10.4.3  实验结果 216
10.5  本章小结 218
第11章  探索社交机器人的受控实验 219
11.1  简介 219
11.2  社交机器人的定义 221
11.3  社交机器人的应用和影响 221
11.3.1  应用 222
11.3.2  影响 222
11.4  社交机器人的开发技术 224
11.4.1  互联网接入技术 224
11.4.2  人工智能基础 225
11.4.3  网络科学理论 226
11.5  社交机器人检测 226
11.5.1  基于图的检测方法 227
11.5.2  基于征的检测方法 227
11.5.3  众包检测方法 228
11.5.4  多种方式的混合使用 229
11.6  社交机器人与社交网络受控实验 229
11.6.1  在线社交网络受控实验 230
11.6.2  社交机器人在受控实验中的应用 232
11.6.3  社交机器人受控实验中的问题 237
11.7  结语 238
参考文献(在线资源) 239

事物之间的相互作用造就了我们的美丽世界。许多现实世界的系统，无论是自然的还是人工的，都可以自然地表达为图或网络以捕捉其拓扑性，而不是采用欧几里得空间中的坐标形式。在生物学中，蛋白质相互调节，这种生理上的相互作用构成了所谓的生物体的交互组学；神经元相互连接，在大脑中处理信号，导致了智能的涌现；物种相互依赖，从而形成复杂的生态系统。此外，现代交通系统连接了不同国家的不同城市，极大地便利了我们的出行，使整个世界成为真正的地球村。如今，随着我们进入网络空间，各种网络层出不穷。人们通过Facebook、、Twitter、等社交网络平台紧密联系，分享各自的观点和个人兴趣。人们可以使用谷歌、百度和雅虎等搜索引擎搜索感兴趣的信息，而这些系统的核心便是一个巨大的网页网络。人们还可以通过电子银行或基于区块链的平台(如以太坊)轻松转移资金。此外，一些强大的数据挖掘或人工智能技术本质上也是网络，如知识图谱和深层神经网络。虽然这些网络促进了个人之间的信息交流，使我们的生活比以前更便捷，但也可能为病毒的传播提供便利，并造成隐私泄露。例如，仅仅根据个人的自我社交网络就可以推断出定种类的关系[1]。因此，我们迫切需要发展一些方法来更好地了解这些网络的拓扑结构，以便在一定程度上预测并进一步影响其演变趋势。
幸运的是，图论作为数学的一个分支，自1736年欧拉对哥尼斯堡七桥问题的开创性研究以来[2]，已被完备地建立起来。在这个大数据时代，越来越多的系统被描述为图(网络)，同时，相应的图数据也被不断地发布出来以供研究。网络已吸引了来自众多不同领域的研究人员前赴后继地投身其中。人们通过提出一系列的结构属性，从微观(节点和连边)、中观(模体和社团)到宏观(整个网络)的角度来观察并进一步测量这些网络[3]。在工业界，许多著名的搜索引擎和推荐系统基本上都是根据节点在相应网络中的结构重要性进行排名的，例如著名的PageRank算法[4]和协同过滤算法[5]。另外，在学术界，Strogatz等[6]根据较短的平均距离以及较大的平均聚类系数来表征小世界网络，而Barabási等[7]则通过幂律度分布来定义无标度网络。这些研究引领了复杂网络的发展。随后，研究人员提出了各种数学模型，模拟并分析了网络上的流行病传播、同步等不同类型的动力学行为[8]。最近，人们提出了图嵌入技术，如DeepWalk[9]和Node2Vec[10]，在网络空间和欧几里得空间之间架起了一座桥梁。因此，我们可以采用机器学习算法来自动分析图数据。很快，深度学习框架，如图卷积网络(GCN)[11, 12]等方法也被陆续提出，用以进一步分析网络图数据。
在本书中，我们主要关注图数据的监督学习。别地，前3章介绍了关于节点分类、链路预测和图分类的进的图数据挖掘算法，第4章介绍了用于进一步增强这些现有图数据挖掘算法的图增强算法。第5章和第6章分别分析了这些算法在对抗攻击下的脆弱性以及提高其鲁棒性的方法。值得注意的是，我们还在第5章中分析了社团检测作为无监督学习的脆弱性，并进行全面回顾。接下来，我们将对节点分类、链路预测和图分类进行简要回顾，并简单介绍本书的各个章节。
节点分类可以通过属性和结构信息来预测未知节点的标签，这在社会网络分析中具有广泛应用的场景。在某些情况下，同一类别的节点具有相似的拓扑属性，因此我们可以使用基本的结构征[13]来区分它们，包括节点的度中心性、接近中心性、介数中心性、征向量中心性、聚类系数、H指数、核数、PageRank指数等。我们可以使用其中的一个或多个，再加上机器学习算法来进行分类。这样的模型相对简单且可解释，因为我们很容易知道哪个征在模型中更重要，而且几乎所有这些手工设计的征都具有某个定的物理或社会意义。尽管这种简单的模型在某些情况下是可行的，但在其他一些情况下可能会失效，别是当现实世界的网络可能包含数以万计的节点，且网络拓扑结构不规则时。随后，研究人员发展了图嵌入技术，将图数据转换为可区分的矢量表示，同时保留固有的图属性。通常的嵌入技术主要基于随机游走、矩阵分解和神经网络。典型的图嵌入算法包括：DeepWalk[9]，它基于skip-gram模型[14]，利用网络中节点之间的共现关系信息得到节点的嵌入向量；GraRep[15]，它通过矩阵分解保留了嵌入空间中图形的高阶接近性；以及 LINE[16]，它保留了节点之间的一阶和二阶相似性，从而可以同时呈现网络的局部和全局结构信息。此外，随着深度学习的发展，一系列图神经网络(GNN)架构被提出，实现了节点的端到端分类。Bruna[17]提出了第一个基于谱域的图卷积神经网络(GCN)，它通过傅里叶变换将图和卷积运算扩展到谱域，ChebNet[11]和CayleyNet[18]分别采用切比雪夫多项式和凯利多项式对图滤波器进行了简化。Kipf和Welling[12]通过切比雪夫多项式的一阶近似进一步简化了操作，在基于谱域的方法和基于空域的方法之间架起了桥梁。这些研究在很大程度上促进了空域方法的发展，并显著提高了节点的分类性能。然而，这种深度模型具有高度的非线性和复杂性，使其难以理解并增加了潜在的脆弱性。
在第1章中，殳欣成等设计了一个双通道的图神经网络框架来定位网络上的流行病传播源，这可以被认为是一个典型的节点分类问题。其中，节点通道利用网络结构将每个节点表示为嵌入向量，而连边通道将原始网络转换为线图，并提取线图中节点的征向量作为原始连边的表示。然后，两个通道的征被整合，用来更好地估计传播源。
链路预测的目的是根据当前观察到的连边来预测缺失的或未来的关系[19]，这在社交网络和生物网络中已被广泛采用。在社交网络中，链路预测被用来推荐可能的朋友关系，从而带来更令人满意的用户体验[20]。在生物网络中，链路预测被用于预测以前未知的蛋白质之间的相互作用，从而大大降低实验方法的成本[21]。此外，用于构建社会和生物网络的数据可能包含不准确的信息，导致虚假的链接[22, 23]，这也可以通过链路预测算法来识别[24]。同样，链路预测也可以仅仅根据成对节点之间的预定义相似度来实现。这种相似性指数可以是局部的，也可以是全局的[25]。例如，共同邻居指数、优先连接指数[7]、Adamic-Adar指数和资源分配指数[26]是基于局部的，因为它们只涉及目标节点对的一阶或二阶邻居；Katz指数、有根PageRank指数[27]和SimRank指数[28]是基于全局的，需要知道整个网络的结构。然后，这些相似性指数的集合可以被输入机器学习模型中，通过与其中一个指数的比较，获得更高的链路预测性能。通过采用图嵌入和GNN技术可以进一步提高这一性能，因为一条边的嵌入向量可以很容易地通过二进制运算符，即Average、Hadamard、Weighted-L1和Weighted-L2，将相应的终端节点的嵌入向量结合起来得到更高的链路预测性能。
在第2章中，张剑等提出了一个超子结构增强链接预测器(HELP)，作为一个端到端的深度学习框架，用于链路预测。HELP利用给定节点对邻域的局部拓扑结构，并从超子结构网络中学习征以进一步利用高阶结构信息。这种方法具有相对较高的效率和较好的效果，实现了进的链路预测性能。
图分类的重点是通过不同网络的结构差异进行分类。在化学中，我们可能希望根据每个化合物的结构征将其分类为有毒或无毒[29]。考虑传统的新药发现是非常昂贵的，这可能对药物研究和开发有帮助[30]。在社会网络中，我们可以用图捕捉个人行为。例如，我们可以根据人的流动性或工作痕迹为其建立流动性网络[31]或焦点转移网络[32]，这样就可以根据这些网络的结构性对其分组。还可以根据团队的内部交流模式对其分类。同样，可以简单地使用图的统计数据，如度分布和平均最短路径长度，对不同的网络进行分类[33, 34]。此外，可以处理整个图，得到不同的小图或子图的数量，也可以使用这些频率统计产生图分类的征向量[35, 36]。另一种流行的方法是定义图核来测量图之间的相似性，可以将其插入一个核机器中。研究人员已经提出了许多图核，包括最短路径核[37]、Graphlet核[38]、随机行走核[39]、Weisfeiler-Lehman核[40]和深度图核[41]。同时还提出了图嵌入技术(如Graph2Vec[42])，以及GNN技术(如DiffPool[43])和图注意力网络(GAT)[44]，用于图分类，并且取得了良好的效果。
在第3章中，王金焕等介绍了构建子图网络(SGN)的方法，并通过整合不同的采样策略，进一步介绍了具有更高扩展性和多样性的采样子图网络(S2GN)。他们利用SGN和S2GN来扩展目标网络的结构征空间，再加上宽度学习(Broad Learning)，显著提高了一些图分类算法的性能。
在第4章中，周嘉俊等进一步介绍了一种新的迭代技术，即M-Evolve，用于图数据增强。M-Evolve包括子图增强、数据过滤和模型再，适用于包括节点分类、链路预测和图分类在内的多种任务。实验表明，该方法在一定程度上有助于克服过拟合，并能显著增强一系列图数据挖掘算法。
算法安全主要是分析图数据挖掘算法在网络结构的某种扰动下的脆弱性，并进一步提出相应的防御策略。最近的研究表明，许多人工智能(AI)算法在对抗性攻击下可能相当脆弱，例如通过对图像像素值的微小扰动，可以使得图像分类器的性能大大降低。这种对抗性攻击也可以威胁到图数据挖掘算法，即它们的性能可以通过稍微改变网络结构而大大降低。另外，我们也可以设计某些方法来检测和进一步防御这种攻击，从而提高图数据挖掘算法的鲁棒性。
在第5章中，单雅璐等对图数据挖掘的对抗性攻击进行了简要回顾。他们对现有的攻击方法进行了简单的分类，这些方法可能是启发式的、梯度的或基于强化学习的。然后，针对每个图挖掘任务详细介绍了一到两种对抗性攻击方法。实验结果表明，大多数图数据挖掘算法容易受到图结构或征微小变化的。
在第6章中，徐慧玲等简要回顾了针对图数据挖掘算法恶意攻击的防御策略。他们将这些策略分为5类：对抗性、图的净化、可认证的鲁棒性、关注机制和对抗性检测。不同种类的策略有不同的应用场景。希望此类研究能够提醒研究人员和工程师，算法的鲁棒性在许多现实世界的应用中可能至关重要。
应用是算法发展的驱动力。其余6章介绍了图数据挖掘算法在金融、社交网络、交通、通信、流行病等方面的各种应用；并希望引起数据挖掘、知识发现、人工智能、网络科学以及相关应用领域的科学家和研究人员的关注。这些章节的内容简要介绍如下。
在第7章中，谢昀苡等介绍了一个时间序列快照网络，将以太坊交易记录建模为一个空间-时间网络，并定义了时间上的有偏游走，从而有效地将账户转化为嵌入向量。在此基础上，他们使用节点分类和链路预测技术，分别检测网络钓鱼和跟踪交易。这类研究有助于从网络角度更好地理解以太坊交易系统。
在第8章中，张剑等建立了一个基于Yelp数据集的朋友网络，并通过随机森林和变分图自动编码器(VGAE)方法推荐朋友。随机森林将多个人工设计的节点相似度指数作为输入，而VGAE通过深度学习框架自动学习网络结构征。进一步地，他们构建了一个共同觅食网络，并向用户推荐潜在的餐友，验证了链路预测方法在Yelp上的潜在应用。
在第9章中，徐东伟等介绍了一个图卷积递归神经网络来预测交通流量。他们建立了一个交通网络，然后采用GCN模型来学习道路之间的相互作用以捕捉空间依赖性，并使用长短期记忆(LSTM)神经网络来学习交通动态变化以捕捉时间依赖性。他们在杭州交通网络上进行了预测，验证了该方法的有效性。
在第10章中，裘坤峰等介绍了循环有限可视图(CLPVG)，将时间序列映射到图中，该方法优于传统的有限可视图(LPVG)。此外，他们还介绍了第一个基于GNN的端到端时间序列分类方法，并在几个时间序列数据集上验证了该方法的有效性。
在第11章中，闵勇等介绍了社交机器人的概念，包括其定义、使用和潜在的影响。他们还介绍了在社交网络上部署社交机器人的相关技术，并总结了几种检测此类社交机器人的方法。未来，随着人工智能技术的发展，各种社交机器人可能会越来越多地被部署在网上，这可能会污染互联网生态系统，并引发网络空间安全问题。同时，社交机器人作为人工噪声，可能会在一定程度上误导图数据挖掘算法，这值得引起各领域研究者的更多关注。
本中文版翻译自英文书Graph Data Mining: Algorithm, Security and Application，其中各个章节的新增与修改之处包括：第5章新增了表5.1及相关描述；第6章修改了图6.3、图6.4以及在6.8.2节添加了两个数据集以及相关结果描述。
本书参考文献请扫封底二维码下载。

宣琦
中国杭州