在当今的大数据环境中，开发强大的知识发现解决方案取决于来自各种来源的数据的集成。例如，情报机构融合来自多个来源的数据以识别犯罪活动；电子商务平台整合各种平台和设备上的用户活动以建立更好的用户资料；科学家连接来自各种模式的数据以开发新药和治疗方法。在所有这些活动中，来自不同数据源的实体需要对齐(aligned)——首先，以确保准确的分析，更重要的是，发现有关这些实体的新知识。如果数据源是网络，则对齐来自不同来源的实体会导致网络对齐的任务，这是本论文的重点。此任务的主要目标是利用图拓扑(graph topology)和节点/边属性(nodes/edges attributes)在两个或多个网络中的节点之间找到最佳的一一对应关系。
在现有的研究中，人们采用了多种计算方案来解决网络对齐任务；这些方案包括寻找相似性矩阵的特征分解、通过次梯度优化解决二次分配问题以及设计迭代贪婪匹配技术。当代研究使用深度学习框架通过学习节点表示来识别匹配来解决此问题。节点匹配(Node matching’s)的主要挑战包括计算复杂性和可扩展性。然而，隐私问题或不可用性通常会阻碍在实际场景中使用节点属性。鉴于此，我们旨在通过仅依靠图结构(graph structure)来解决这个问题，而无需先验知识、外部属性或地标节点的指导。显然，与其他网络匹配任务相比，基于拓扑的匹配是一个难题。
在本论文中，我提出了两项原创工作来解决基于网络拓扑的对齐任务。第一项工作是基于图元的对齐（Graphlet-Align），采用拓扑方法进行网络对齐。Graphlet-Align 用基于局部图元计数的签名表示每个节点，并将其用作在一对网络中导出节点到节点相似性的特征。通过在二分匹配算法中使用这些相似性值，GraphletAlign 获得初步对齐。然后，它使用扩展到节点 k 跳邻域的高阶信息进一步细化对齐，实现更好的准确性。我们通过将 Graphlet-Align 应用于各种大型现实世界网络来验证其有效性，在重复和嘈杂的图上，与最先进的方法相比，实现了从 20% 到 72% 的准确度提升。
在我的第二部作品中，我扩展了这种仅关注拓扑来解决图对齐问题的范式，开发了一个称为自监督拓扑对齐 (SST-Align) 的自监督学习框架。SST-Align 使用基于图元的签名来创建自监督节点对齐标签，然后使用这些标签在联合空间中生成两个网络的节点嵌入向量，从中可以有效准确地解决节点对齐任务。它从优化过程开始，该过程在提取的图元签名之上应用平均池化来构建初始节点分配。接下来，自监督的 Siamese 网络架构利用初始节点分配和图卷积网络通过对比损失生成节点嵌入。通过将 kd 树相似性应用于两个网络的嵌入，我们实现了最终的节点映射。在现实世界的图对齐数据集上进行的广泛测试表明，与现有的七种竞争模型相比，我们开发的方法在节点映射准确性方面具有竞争力。此外，我们建立了消融研究来评估两阶段准确度，排除学习表征部分并相应地比较映射准确度。
本论文增强了对网络对齐任务中图数据分析中拓扑特征的理论理解，从而促进了该领域未来的发展。
论文题目：Network Alignment Using Topological and Node Embedding Features
作者：Aljohara Almulhim
类型：2024年博士论文
学校：Purdue University（美国普渡大学）
下载链接：
链接: https://pan.baidu.com/s/1WCHlAjAGHMyFqnkBuV2yaQ?pwd=19rs
硕博论文汇总：
链接: https://pan.baidu.com/s/1Gv3R58pgUfHPu4PYFhCSJw?pwd=svp5
使用大小为 4 的节点中心图基元对齐两个图中的节点的示例
基于图基频率和高阶距离的提出框架。
GraphletAligngraphlet 签名距离矩阵计算概述。首先，提取 graphlet 向量。其次，应用平均池化操作。第三，计算距离矩阵，其中使用 Hangrian 方法匹配节点。
图基元计数大小为 4 的示例。(a) 给出了一个双玩具网络示例，目标是学习一个可以匹配图 1 到图 2 的节点的映射函数；(b) 不同的轨道将图基元轨道描绘为小的、连通的、非同构的子图，这些子图基于它们在网络中四个节点内出现的连接模式；(c) 为节点 1 和节点 A 提取的图基元计数向量分别与图 1 和图 2 匹配。
GraphletAlign 开发的嵌入框架的说明。在自监督学习方法中，连体嵌入结构和图卷积网络的组合有助于准确确定节点之间的最终对应关系。节点匹配是使用 kd-tree 完成的，以将 G1 中的每个节点与 G2 中具有最相似嵌入的精确节点进行匹配。
