基于图的机器学习：数据结构和算法的贡献

基于图的机器学习昆汀·卢茨引用此版本：昆汀·鲁兹。基于图的机器学习贡献。数据结构和算法[cs.DS]。巴黎理工学院，2022年。英语NNT：2022IPPAT010。电话：03634148HAL Id：tel-03634148https://theses.hal.science/tel-036341482022年4月7日提交HAL是一个多学科的开放获取档案馆，用于存放和传播科学研究文件，无论它们是否已这些文件可能来自法国或国外的教学和研究机构，或来自公共或私人研究中心。L’archive ouverte pluridisciplinaire626基于图形的机器学习Thehe` se de doctor at depre' pare' ea`Te'le' comP ar isE'cole docto ralen 626E' cole docto rale deSpe'cialite'de doctor at：In for matique，Donne' es et Intelligence Ar tificielle2022年9月9日，第2022年9月9日，QUENTINL UTZ评审团组成：让-卢·纪尧姆Professeur，Uni versite'delaRochelle Pre' sident马蒂厄·拉蒂默法国国家科学研究中心和索邦大学研究主任孔拉多·马尔内兹特别报告员Prof esseur，Uni versitatPolite` cnicadeCataluny a Rap por teurCe'cile Mailler巴斯大学考试委员会托马斯·博纳德Prof esseur，Te'le' comPar is Directeurdethe' se埃列德帕纳菲厄Chercheur，诺基亚贝尔实验室联合负责人Ge'r ard Bur nsideChefdede'partement，NokiaBellLabs In vite'NNT：2022IPPAT010摘要一个图表是一个渗透着数学的对象，代表了各种关系（即所谓的núuds）这些图是长期以来对欧拉在 PageRank 上的不同 问题的研究对象 ，通过对 一些问题的 Les graphes ont plusrécement trouvé des usages pour随着社会网络和这些图表一直都在增加，可能会有数十亿的营养和营养。 La concept d'algorithmesefficaces s'avèrenécessaire pour permettrel'analyzedecesdonnées.Cette thèse étudie另外，为了方便对grands graphes的操作，并将这些技术应用到学生身上，我们提出了Scikit-network，一个在Python中自由开发的库。我们关心的是如何解释这些问题Les techniques- niques supervisées这些数据的质量直接影响这些技术的质量。 然而，获取这些数据不应依赖于机器的帮助，而应依赖于人类的干预，使我们的研究最小化。这些贡献表明，在该报告ont toutes recours à des graphes。 由于Scikit网络的图形缺陷和发展，学生们不能以图形的形式来代表。为了解决数据注释问题，我们需要用数学图形来解释。 所有这些贡献都是在自动化领域的应用。Scikit网络中汇集了对该问题的逻辑贡献Scikit- network est inspirée de la librairieScikit-learn，whi proposed un large éventail d'algorithmes pour l'ap-prentissageautomatique surdesdonnées vectorielles. 通过类比，我们可以在Scikit网络中找到不同的方法来实现图形上的错误和自动识别。这本书在Python语言的生态系统中自由地使用了各种各样的名词，以便于使用分析器来分析所用的工具，从而提供了一种良好的人机工程学关于这些名词，我们可以通过Scikit网络的帮助来计算中心点和对节点进行分类。这是在图形中研究共同体技术的艺术我们学习的技术本身就不是等级制的在第二个案例中，我们特别学习了鲁汶的方法，并确定了各种各样的方法。我们对各种性能进行质量比较 我们建议采用一种新的鲁汶方法，以加快执行速度。我们支持共同体的研究技术，以便提出一种新的方法，用于挖掘一个graphe的核心Nous2mesurons la performance de cette methode en la comparant àNous illustronségalement certaines de ses propriétés ， notamment en expliquant comment lesrésultats peuvent être interprétés en fonadium des communautés trouvées parl'algorithmedeLouvain.本文的另一个贡献是对一个工业应用案例中的一个具体问题的研究Après avoir introduit le prob-lème en question，sous un formalisme utilisant des graphes，nous caractérisonssimple- ment les solutions optimales.Nous prouvons ensuite que cette famille desolutions opti- males partage la même distribution de complexité dont nous étudionsle comportement.我们决定平等对待多种可能的学习问题和应用。1内容1介绍31.1动机31.2图表31.3图表分析51.3.1图论51.3.2图挖掘71.4大纲91.5出版物92Scikit-network 112.1动机112.2软件功能122.3实际考虑132.3.1高效的图形表示132.3.2一揽子计划的指导方针.2.3.3业绩192.4结论203节点群集213.1一.导言. 213.1.1节点采样213.2扁平聚类223.2.1相似性措施223.2.2模块功能243.2.3鲁汶法283.2.4Leidenrefinements 313.3Hierarchicalclustering层次聚类353.3.1树状图353.3.2A.聚合办法363.3.3分裂性做法373.3.4实验373.4结论3924节点嵌入404.1一.导言. 404.1.1动机404.1.2相关工作414.2嵌入方法414.2.1算法414.2.2使用软集群的链路434.3结果434.3.1链接预测444.3.2节点分类454.3.3时间性能454.4房地产464.4.1可解释性464.4.2嵌入的稀疏性4.5结论485数据集标签495.1导言. 495.1.1动机和相关工作5.1.2设置515.2Chordal algorithms弦算法525.2.1Chordalgraphs弦图535.2.2Chordal算法的最优性5.2.3Chordal算法的成本等价性5.2.4复杂性估计615.3实际应用725.3.1实施的考虑因素5.3.2通过具体数据技术提供的援助735.3.3不完美的oracle 745.4结论786结论和展望797Bibliography参考书目813第1介绍1.1动机机器学习收集旨在从数据中“学习”的算法，即这些算法可以自己提高给定任务的性能。 它可以被视为人工智能的一个子领域，因为它允许计算机模拟某种形式的推理。机器学习算法旨在预测有关它们所输入的数据的信息这些数据可能有多种形状和格式：它可以是动物的图像，收集在文本语料库中的法律法案或由图表表示的分子相互 机器学习算法的应用同样多种多样，从农业和医学到银行和语言学。在这篇论文中，我们解决了机器学习中与图（这是几个实体之间相互作用的数学表示）有关的选定问题。 图在机器学习领域中以许多不同的方式使用。 在最近的发展中有图核（Vishwanathan等人，2010），其旨在测量图对之间的相似性，以及图神经网络（Scarselli等人，2008年），这使得有可能使用神经网络的数据表示的图形。在这篇论文中，我们区分了图被用来建模关系数据的情况（如第2、3和4章所示），以及图被用作形式化工具而不管实际数据的情况（如第5章所示然而，在这两种情况下，我们都试图利用图及其属性来提高机器学习算法的性能。1.2图图是一种数学对象，用于表示称为节点或顶点的实体之间的关系。节点之间的关系由它们之间的成对连接表示，根据上下文称为边或链接。由一条边连接的两个节点是彼此的邻居，称为相邻节点。一个节点的度是它的邻居的数量设G=（V，E）表示一个图，其中V是节点集，E∈V×V是图的4∈∈•∈•∀∈•||||(a) 无向（b）有向（c）二分图1.1：各种图表边缘设置。图表可以在从生物信息学到社会科学的各种领域中找到。根据所研究的领域，图有时也被称为网络。它们可用于表示许多不同的数据集，包括Web图形，其中每个节点是一个网站，链接表示它们之间的超链接。有许多图族 我们描述了在这项工作中发现的一些问题，并在图1.1中进行了说明：无向图描述了节点之间的对称关系也就是i，j V，如果（i，j）E那么（j，i）E。这是Facebook上的用户的情况，因为友谊链接是对称的。相反，有向图描述的关系中，前面的含义并不适用于所有的节点对。 这对应于Twitter上的关注者/被关注者关系或网络上的超链接。在有向图中，边有时被称为弧。为了清楚起见，我们将弧的源节点与其目标节点区分开来 考虑一条边（i，j）∈ E，我们说i是j的前趋，j是i的后继。• 二部图是无向图的一个子类，其中节点集V是两个集合V1和V2的不交并，使得E中的所有边的一端在一个集合中，另一端在另一个集合中。二分图用于表示两种不同类型的实体之间的关系，例如疾病及其相应的症状或Netflix用户及其评分的电影。在这项工作中，我们还考虑了一个自然的变种：加权图。在加权图中，每条边都被分配了一个称为权重的非负实数这允许进一步表征节点之间的连接的相对强度我们修正了一些可以在整个论文中找到的符号除非特别说明，我们注意n=V，节点数和m=E，边数如果图是无权无向图，则di是节点i V的度。 如果图是有向的，则d+（resp. d−）是出度（或入度），即边数J I·5其源（resp.target）是i。然后，d+（相应地，d−）正好对应于J I（i）的继任者（或前任）。如果图是加权的，则d+（resp.d−）是总和J I其源（resp.target）为i的边的权重。我们注意到w，图的总权重，即所有边的权重之和• 为了可读性，我们有时将边（i，j）转换为ij。1.3图分析在本节中，我们介绍了两个研究领域围绕图的分析虽然图论试图将图的属性描述为数学对象，但图挖掘的目的是从可以表示为图的数据集中提取信息。这两个领域在它们使用的方法上不同，但它们确实重叠，如最短路径问题所示，从理论观点来看，最短路径问题是历史上重要的问题（Ahuja等人，1990年），也看到了一些在现实世界中的应用（张和涂，2009年），如社会科学。1.3.1图论图论研究的是图的数学性质在这里，我们列出一些常见的图论问题：图类存在许多由它们的某些性质定义的图族。例如，在这些族中有平面图，它们可以在没有任何边相交的情况下绘制。 我们在图1.2中给出了一个具有这种性质的图的例子。对于其中的许多族，刻画它们（Lovász，1972; Farber，1983）并能够识别图是否属于某个族（Tarjan和Yannakakis，1984; Hopcroft和Tarjan，1974）是特别感兴趣的。第5章的重点就是这样一个类。图1.2平面图··6图着色一个感兴趣的是找到节点的着色（即，为图中的每个节点分配颜色），使得相邻节点没有相同的颜色（Jensen和Toft，2011）。虽然存在该问题的许多变型，但最知名的结果之一是四色定理（Gonthier等人，2008），其指出在无环平面图上，不需要超过四种颜色来解决问题。着色问题的一个简单应用出现在确定一个图是否是二部图时：一个图是二部图，当且仅当它具有2-着色，每个节点的着色取决于它所在的节点子集（如图1.3所示）。图1.3：二部图的2-着色路由问题路由问题是那些旨在找到一条路径（有时是一棵树）在一个图，满足某些条件，如通过每个节点一次，或找到一对节点之间的最短路径，如图1.4所示。他们收集著名的问题，包括七桥的柯尼希-贝格（欧拉，1956年）和汉密尔顿路径问题（古列维奇和谢拉，1987年）。路由问题在诸如计算机科学的领域中具有许多应用（Li等人，2013）和运输（小福特，1956;詹和中午，1998）。图1.4：两个节点之间的最短路径（红色）我们现在给出一些图论定义，我们将在整个工作中使用··7•CC（Golumbic，2004年）。一个图是连通的，如果每对节点之间有一条路，否则是不连通的一个图的连通分支是一个连通子图，对于包含是极大的u，v分隔符是节点集的一个子集，一旦被移除，就会断开图的，使得u和v处于不同的连通分量中循环是路径=（u，v，w，.- 是的- 是的，u）从一个节点到其自身的大小至少为3。除了第一个和最后一个节点之外，任何节点都不能重复。循环的弦是连接循环的两个非连续节点的边。没有和弦的循环是诱导的或没有和弦的。• 树是一个没有圈的连通图• 图的团是它的一个完全子图。1.3.2图挖掘图挖掘是一组旨在发现真实世界图的属性的技术。它包括在图上使用的数据挖掘技术（Rehman等人，2012年）。虽然这个定义暗示了与图论的一些重叠，但许多技术几乎只在图挖掘上下文中遇到。在这里，我们提供了一些常见的图挖掘任务列表节点排名排名包括为图中的每个节点分配一个分数，以说明其重要性或中心性。存在许多排名方法（Bloch等人，2019; Landherr等人，2010）定义了广泛的度量，一些基于图中的随机游走，如PageRank排名所示（Page et al.，1998）最初是为网页设计的;有些使用最短路径问题的解决方案（Okamoto等人，2008年）。图1.5给出了一个例子 我们在目前的工作中不处理这个任务。图1.5：使用PageRank对节点进行排名···8节点聚类，也称为社区检测，收集基于图的结构在图中寻找重要社区的方法。特别是，一个好的集群应该对节点进行分组，使它们与自己的集群的连接比与其他集群的连接更多，如图1.6 所 示 节 点 聚 类 在 物 联 网 中 具 有 应 用 （ Mitra 等 人 ， 2012 ） 和 推 荐 系 统（RepresentationSystem，2010）。第三章综述了聚类方法。图1.6：使用Louvain方法对节点进行聚类虽然图的形式非常适合表示关系数据，但可能需要将每个节点表示为向量，这种操作称为嵌入图的节点。例如，嵌入空间的维度可以被设置为与用于维度减少的节点的数量相比较低的值这也是一种应用机器学习技术的方法，将向量作为输入。我们在图1.7中举例说明了嵌入任务第4章介绍了一种嵌入方法。··9图1.7：使用奇异值分解的节点的三维嵌入。1.4纲要本论文的结构安排如下：第二章介绍了Scikit-network，一个我们在实验中使用的图形分析库。它是在本论文的框架中广泛开发的，提供了一个简单的API以及具有竞争力的性能。第三章回顾了一些典型的节点聚类方法。 我们描述了平面聚类的Louvain方法及其一些改进和一些层次聚类算法。第四章介绍了一种新的节点嵌入方法。它基于上一章的Louvain聚类方法来处理大规模数据集并提供可解释的结果。第5章处理数据集标记问题所研究的特定设置来自现实世界的问题。 我们描述了这种设置的最佳解决方案。• 第六章是本文的结论。1.5出版物在这篇论文中有两篇文章被接受Bonald，T.，de Lara，N.，Lutz，Q.，沙蓬捷湾（2020年）。Scikit-network ：Python中的图分析。 J. 马赫学习. Res. ，21，185-1.与第2章有关·····10Lutz，Q.，De Panafieu，E.，Stein，M.，Scott，A.（2021年）。用于标记训练数据的主动聚类神经信息处理系统的进展，34。与第5章有关·11第2Scikit网络Scikit网络包由Thomas Bonald和Bertrand Charpentier于2018年创建本章所述的工作是与内森·德·拉腊和托马斯·博纳尔德共同进行的。我们建议读者参考该软件包然而，应该注意的是，软件包的很大一部分是由几个贡献者同时开发的（以结对编程的方式），而只有一个人提交到Git仓库。此外，当只查看存储库时，软件包上的部分工作并没有被考虑在内：尝试不同的功能，库或持续集成工具;通过仔细理解科学文章来设计有效的代码以及学习软件开发中的新技能都是要求很高的任务。总的来说，可以肯定的是，核心开发人员中没有一个贡献者的角色超过其他人。2.1动机Scikit-learn（Pedregosa等人，2011）是一个基于流行的Python语言的机器学习包由于其多功能性、性能和易用性，该软件包在当今的机器学习社区中得到了广泛的认可它的主要资产是各种算法，其实现的性能和它们的公共API。Scikit-network是一个受scikit-learn启发的Python包，用于图形分析。实数图的稀疏性，多达数百万个节点，阻止了它们表示为密集矩阵，并排除了scikit-learn的大多数算法 Scikit-network以SciPy的CSR格式的稀疏矩阵作为输入，并提供最先进的算法来对图的节点进行排名，聚类，分类，嵌入和可视化。Scikit-network的设计目标与scikit-learn的成功目标相同：多功能性，性能和易用性。 结果是Python原生包，如NetworkX（Hagberg et al.，2008年），实现了iGraph的最先进性能1见https://github.com/sknetwork-team/scikit-network/graphs/contributors。12图2.1：Scikit-network徽标（Csardi和Nepusz，2006）、graph-tool（Peixoto，2014）和NetworkKit（Staudt等人，2016年）（参见第2.3.3节中的基准）。 Scikit-network使用与Scikit-learn相同的API，算法可作为具有相同方法的类（例如，适合）。它使用BSD许可证分发，依赖关系仅限于NumPy（Waltet al.，2011）和SciPy（Virtanen等人，2020年）。2.2软件功能该软件包以具有一致API的模块组织，涵盖各种任务：数据 用于从远程存储库加载图形的模块，包括Konect（Kunegis，2013），将tsv文件解析为图形，并从标准模型（如随机块模型）生成图形（Airoldi等人，2008年）。集群。 用于聚类图的模块，包括返回节点-聚类成员关系矩阵的软版本。等级制度。图的层次聚类模块，以SciPy的标准格式返回树状图。 该模块还提供了用于切割和压缩树状图的各种后处理算法。嵌入。 嵌入图在低维空间的模块。这包括谱嵌入和标准降维技术，如SVD和GSVD，以及正则化等关键特征榜 用于按重要性顺序对图的节点进行排序的模块。这包括PageRank（Page等人，1998）和各种中心性分数。分类. 用于基于几个节点的标签对图的节点进行分类的模块（半监督学习）。Topology. 探索图结构的模块：图遍历，k-核分解等.·······13•×模块NetworkXiGraph图形工具网络套件数据✓✗✓✓聚类✓✓✗✓层次结构✗✓✓✗嵌入✓✗✓✗排名✓✓✓✓分类✓✗✗✗拓扑✓✓✓✓路径✓✓✓✓链接预测✓✓✓✓可视化✓✓✓✓表2.1：图形软件功能概述A：可用。执行情况：部分可用或执行缓慢。秘书长：没有。• 路径 依赖SciPy解决最短路径问题的模块。链接预测用于基于部分图向节点对分配边的存在概率的模块。想象力。 SVG（可缩放矢量图形）格式的可视化图形和树状图的模块。示例如图2.2所示现有的图形软件仅部分涵盖了这些模块（见表2.1）。Scikit网络的另一个有趣的功能是它能够直接在二分图上工作，由它们的双邻接矩阵表示2.3实际考虑2.3.1高效图表示存在多种形式化表示图的方法 我们比较三个最常见的：邻接矩阵，大小为n的方阵Aij，其中Aij是边的权重（i，j）（或1为未加权图），如果它存在，否则为0• 邻接列表，一个列表的列表，其中第i个列表包含节点i的邻居.关联矩阵，形状为nm的矩形矩阵Bik，使得Bik = 1当且仅当节点i与第k条边关联。在更实际的意义上，仅仅选择表示不足以评估一些常见操作的性能，例如找到与特定边相关联的权重或从图中删除顶点任何这些陈述的实施都很重要。特别是，所选择的数据结构决定了···14亨利·马蒂斯·巴勃罗·毕加索Edouard Manet保罗·塞尚Gustav KlimtEgon Schiele克劳德·莫奈Pierre-Auguste Renoir文森特·梵高埃德加·德加Peter Paul Rubens米歇尔·安杰洛伦勃朗达芬奇亨利·马蒂斯·巴勃罗·毕加索皮埃尔-奥古斯特·雷诺阿·克劳德·莫奈·爱德华·马奈·文森特·梵高·埃德加·德加埃贡·席勒·古斯塔夫·克里姆特莱昂纳多·达芬奇米歇尔·安杰洛·伦勃朗Peter Paul Rubens图2.2：将图和树状图可视化为SVG图像。图表可以被操纵。例如，如果使用密集的类C（即，在内存中是连续的，因此索引是隐式的）分别用于邻接矩阵和关联矩阵的大小为n2和nm的数组，以及用于邻接列表的列表的列表，它们的性能如表2.2所述。注意，关联矩阵在所有情况下都比其他两种表示法表现得更差，因此在实践中很少使用然而，在邻接矩阵和邻接表之间没有绝对的赢家。为了进一步探索可用的数据结构，我们考虑实际的图形数据集。大多数真实世界图的一个有用的特征是它们的稀疏性。实际上，与可能的连接数n2相比，边数m通常非常低。给定表2.2中显示的结果，这将有利于邻接列表作为首选数据结构，因为它们天生稀疏。然而，也存在几种稀疏矩阵格式，可以用来表示邻接矩阵。 我们比较了SciPy的sparse模块2中可用的格式，并将它们与使用嵌套Python字典的邻接列表实现进行比较：2https://docs.scipy.org/doc/scipy/reference/sparse.html15∈≤ ≤任务内存空间检查（u，v）E添加节点u删除节点u添加边（u，v）删除边（u，v）列出我们的邻居邻接矩阵邻接列表关联矩阵O（n2）O（n+m）O（nm）O（1）O（du）O（m）O（n2）O（1）O（nm）O（n2）O（dudmax）O（nm）O（1）O（ 1）O（nm）O（1）O（dmax）O（nm）时间复杂度O（n） O（1）表2.2：图的不同表示的复杂性 dmax是图中的最大度。• coordinates（COO）格式由三个数组row、col和data组成，大小为m，因此对于任何1 i m，Arow（i）、col（i）=data（i），否则Ajk=0。与所有基于数组的格式一样，添加或删除边的成本很高，因为它需要调整数组大小。键字典（DOK）格式使用的字典中的键是作为元组给出的边，相关的值是相应的权重。 与基于数组的格式不同，它允许动态更改矩阵，同时提供对其值的恒定平均访问时间。 它的缺点是它的哈希表所需的内存空间。压缩稀疏行（CSR）（相应地压缩稀疏列（CSC））格式隐式地索引源（相应地，每一个节点都有自己的目标，但都有明确的索引。源）节点。它由三个数组组成 在CSR格式的情况下，两个数组索引和大小为m的数据分别包含目标节点和边的权重。 第三个数组indptr的大小为n +1，并限定每个源节点的后继节点。例如，节点i的邻居在索引阵列中的位置indptr（i）到indptr（i +1）处找到，其可以在恒定时间内计算。相反，在CSC格式中，indptr界定每个目标节点的前导节点此 外 ，当使用CSR/CSC格式时，矩阵/向量点积等代数运算非常有效。SciPy中没有字典的字典（DOD）格式 它基于嵌套的Python字典：主字典将节点作为键，将字典作为值。此外，还维护了一个索引，以允许添加和删除节点。 每个嵌套字典都将对应节点的邻居作为键，并将关联边的权重作为值。 与DOK格式不同，这使得通过查看相应嵌套字典的键来对节点的邻域进行恒定时间访问成为可能。这是以增加内存需求为代价的，因为嵌套字典的哈希表很多一个值得注意的缺点是这种格式不适合点积。每种格式都在图2.3所示的玩具图上进行了说明为了比较上述所有格式，我们使用每种格式存储各种图形并收集···16›→01(b)密集阵列23(a) 图来表示行Col数据012021201(c) COO矩阵（0，1）›→2（0，2）›→1（2，0）›→1(d) DOK矩阵印度国防技术研究所02233指标数据1 2210 10›→（1›→2;2›→1）1›→ ∅2›→（0›→ 1）3›→ ∅(f) 国防部矩阵(e)CSR矩阵图2.3一个图及其不同的表示 表示通过哈希函数将键与值关联。边（0，2）及其关联权重也会高亮显示。它们所需内存空间量见表2.3。我们还使用WikiVitals图在表2 - 4中报告了一些常见图操作的执行时间 在后一个表中，没有COO格式，因为它不允许执行列出的大多数任务（包括切片）。还应指出，所研究的任务绝非详尽无遗。特别是，手头上所有格式的一个共同缺点是它们不适合像稠密矩阵那样提取子图。图nMCSRCOO DOK DOD维基学校4.1031.105第六章1021.103 4.103 2.103WikiVitals1.1048.105第四章1037.103 3.104 1.104维基链接3.1067.1073. 1056.105 2.1061.10表2.3：各种图形的不同格式的内存使用情况（kB）在表2.4中，请注意DOD格式是如何从Python字典的效率中受益的，并且是所研究的许多任务的总体最快选项CSR格式具有类似的性能，尽管稍差，除了列出邻居和矩阵-200 2100 0 0 01 0 0 00 0 0 0