拓扑特征检测框架：TopoDetect - 图嵌入中节点拓扑特征的分析与应用

软件影响10（2021）100139原始软件出版物TopoDetect：图嵌入中的拓扑特征检测框架Maroun HaddadMr.，Mohamed Bouguessa加拿大魁北克蒙特利尔魁北克大学计算机科学系A R T I C L E I N F O保留字：图嵌入节点表示学习图的拓扑特征可解释的人工智能代码元数据A B标准TopoDetect是一个Python包，允许用户调查重要的拓扑特征，如节点的度、它们的三角形计数或它们的局部聚类得分被保留在图表示模型的嵌入中。此外，该框架使嵌入的可视化根据节点之间的拓扑特征的分布。此外，TopoDetect使我们能够通过评估嵌入对下游学习任务（如聚类和分类）的性能，研究保留这些特征的效果。当前代码版本v1.0用于此代码版本的代码/存储库的永久链接https://github.com/SoftwareImpacts/SIMPAC-2021-98可再生胶囊的永久链接https://codeocean.com/capsule/8314979/tree/v1法律代码许可证MIT许可证使用的代码版本控制系统无使用Python的软件代码语言、工具和服务编译要求，操作环境依赖python 3.6，dgl-cu 90 0.4.3，torch 1.4，networkx 2.4，numpy 1.18.1，scikit-learn0.22.2、node2vec 0.3.2、cuda 9.0如果可用，链接到开发人员文档/手册https://github.com/MH-0/RPGAE/blob/master/README.md问题支持电子邮件maroon_haddad@hotmail.com，bouguessa. uqam.ca1. 介绍近年来，图表示模型，特别是图神经网络，在许多图学习任务上表现出最先进的性能[1]。这些模型成功的主要原因之一是它们能够生成捕获图的重要特征的向量表示（或嵌入）。然而，我们对这些嵌入中编码的拓扑结构及其对下游学习的影响知之甚少。因此，我们设计了TopoDetect[2]，这是一个利用文献[3，4]中成熟技术的框架，用于确定嵌入中是否编码了某些拓扑特征或中心性度量。2. TopoDetect循环TopoDetect框架分为五个主要步骤，如图所示。1.一、在第一步，我们计算拓扑特征原文DOI：https://doi.org/10.1016/j.neucom.2021.06.034。图中的节点。在第二步中，我们使用图表示学习模型为节点生成嵌入。在第三步中，我们研究计算的拓扑特征是否 被编码在生成的嵌入中。对于该步骤，使用两种方法。在第一种方法中，使用线性回归直接从嵌入预测拓扑特征[3]。预测损失越低，嵌入在捕获拓扑特征方面就越好。在第二种方法中，我们使用直方图分箱将拓扑特征划分为不同的类[4]。例如，度在一定范围内的所有节点都属于同一个类。随后，我们使用经典的分类模型，如多层感知器和支持向量机的节点分类到各自的拓扑特征类，使用的嵌入作为学习属性。模型在分类任务中的得分越高，嵌入在捕获拓扑特征方面就越好。在第四步中，我们使用下游学习任务上的嵌入，根据to their其ground地面truth真相label标签.在第五步，也是最后一，我们分析本文中的代码（和数据）已由Code Ocean认证为可复制：（https://codeocean.com/）。更多关于生殖器的信息徽章倡议可在https://www.elsevier.com/physical-sciences-and-engineering/computer-science/journals上查阅。∗通讯作者。电子邮件地址：maroon_haddad@hotmail.com（M. 哈达德），bouguessa. uqam.ca（M。Bouguessa）。https://doi.org/10.1016/j.simpa.2021.100139接收日期：2021年8月13日;接收日期：2021年9月4日;接受日期：2021年9月13日2665-9638/©2021由Elsevier B. V.发布。这是CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表软件影响杂志 首页：www.journals.elsevier.com/software-impactsM. Haddad和M. 布盖萨软件影响10（2021）1001392imprtexpriments. run_experimentsaredataset=“brazil_airtraffic“bins=3运行=10个re. 运行（数据集，bins，运行）47Fig. 1. TopoDetect框架周期的流程图。结果，并总结了保留的拓扑特征对下游学习任务的影响。3. 运行实验该框架默认包括10个数据集，用户可以直接在其上运行实验，例如Cora，Citeseer和email- Eu-core。数据集可以在框架中的\data文件夹下找到。要运行实验，用户只需从run_experiments.py文件中调用run函数，并传递数据集名称（就像它出现在\data文件夹中一样）。 此外，用户必须提供用于划分拓扑特征类的箱数和实验的运行次数。箱的数量是通过实验确定的，但是，建议使用在特征之间生成最平衡类的箱的数量。该框架将显示结果的平均值和标准差，所有的运行。下面是巴西空中交通数据集的一个例子图二. 使用Graph Autoen生成的Cora数据集嵌入的可视化-使用SUM聚合规则和第一层输出作为嵌入的编码器。的1节点根据其度类着色。2三十五。影响5TopoDetect框架已经允许我们识别6图形自动编码器的两种变体，能够捕获清单1：预定义的数据集实验。还可以通过仅选择某些模型或测试的下游任务来定制实验。此外，可以通过从utils.py文件调用load_custom_dataset来使用4. 可视化TopoDetect还使用户能够根据直方图分箱生成的拓扑类可视化嵌入。 嵌入首先使用t-SNE [5]投影到2维中。图图2显示了使用SUM聚合规则和第一层输出作为嵌入的Graph Autoencoder生成的嵌入示例。每个等级范围（或类别）都以独特的颜色着色。在这种情况下，我们可以清楚地观察到属于同一Degree类的节点在2D投影中整齐地聚集在一起。这种可视化可以帮助我们确认某些模型嵌入中拓扑特征在它们的嵌入中的拓扑特征这些变体使用SUM规则来聚合消息，以及嵌入中编码器第一层的输出[2]。我们的研究表明，这些模型在某些下游任务上表现良好，其中保留的拓扑特征与学习任务相关我们的研究结果在一个案例研究中得到了进一步验证，其中捕获度，特征向量和介数中心性的模型在社会影响力预测任务上显示出有希望的6.可能的扩展默认情况下，TopoDetect包括五个著名的拓扑特征的探索，它们是：度，三角形计数，局部聚类得分，特征向量中心性和介数中心性。然而，TopoDetect可以很容易地扩展到研究其他拓扑特征，例如Katz中心性或页面排名。此外，在我们的研究中，我们检查了三类模型的嵌入：Ma-factorization [6]，Random Walk [7]和Graph Autoencoders [8]。M. Haddad和M. 布盖萨软件影响10（2021）1001393然而，我们的框架可以用来测试其他类型的模型，最有趣的是图注意力网络[9]。此外，TopoDetect还可以扩展到涵盖聚类和分类之外的下游学习任务。例如，用户可以研究拓扑特征的保留对链接预测或边缘标记任务的影响。最后，尽管我们的框架仅用于有向图和属性图的上下文中，但将其部署到其他图形家族（如加权图，多维图，甚至动态/时间图）上将非常有趣。CRediT作者贡献声明马伦·哈达德：概念化，方法论，软件，写作。穆罕默德·布盖萨：调查，写作。竞合利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作引用[1]W.L.汉密尔顿河，巴西-地Ying，J. Leskovec，图上的表示学习：方法和应用，IEEE数据工程。Bull. 40（3）（2017）52[2]M.哈达德，M。Bouguessa，探索图形自动编码器的表示能力，神经计算457（2021）225-241。[3]F.S. Rizi，M. Granitzer，社交网络中向量嵌入的属性，算法10（4）（2017）109。[4]S.邦纳岛Kureshi，J. Brennan，G. Theodoropoulos，A.S. McGough，B. Obara，Exploring the Semantic Content of Unsupervised Graph Embeddings ： AnEmpiricalStudy，Data Sci. Eng. 4（3）（2019）269[5]左室舒张末期Maaten，G. Hinton，使用t-SNE可视化数据，J. Mach。学习.第9（2008）2579-2605号决议。[6]M. Belkin，P. Niyogi，Laplacian eigenmaps and spectral techniques for embeddingand clustering ， in ： Proceedings of Neural Information Processing Systems（NIPS），2001，pp. 585-591。[7]A. Grover，J.Leskovec，node2vec：Scalable feature learning for networks，in：Proceedings of the 22nd ACM International Conference on Knowledge Discoveryand Data Mining，2016，pp. 855-864[8]T.N. Kipf，M. Welling变分图自动编码器，在：NIPS贝叶斯深度学习研讨会，NIPS贝叶斯深度学习研讨会论文集，2016年，pp。1比3。[9]P. Velickovic，G. Cucurull，A. Casanova，A. Romero，P. Bengio，Graph attentionnetworks ， in ： Proceedings of the 6th International Conference on LearningRepresentations（ICLR），2018，pp. 1-12.