Abstract:

Node representation learning has been widely applied in machine learning tasks， such as node classification， clustering and link prediction， since it can encode graph structure data information into low-dimensional potential space. In complex networks， nodes are interacted through not only low-order interactions， but also higher-order interactions formed by special connection modes. The higher-order interactions of a complex network are also called motifs. A node classification algorithm Fusing 2-connected Motif-structure Information （FMI） was proposed to use motif information among nodes to obtain node representation for node classification tasks. Firstly， the 2-connected motifs in the network were counted. A measure index of node importance， named motif-ratio， was proposed by using the motif information in the node； and a sampling probability was calculated according to the motif-ratio to carry out neighborhood sampling. A weighted auxiliary graph was constructed to fuse the low-order relations and the high-order relations of network nodes to aggregate neighborhoods weightedly. The node classification was performed on 5 datasets， Cora， Citeseer， Pubmed， Wiki and DBLP. By comparing with 5 classical baseline algorithms， the proposed algorithm FMI shows better performance on Accuracy， F1-score and other indicators.

Key words: node representation, 2-connected motif, neighborhood sampling, neighborhood aggregation, node classification

摘要：

节点表示学习将图结构数据信息编码到低维的潜在空间中，在节点分类、聚类、链路预测等机器学习任务中被广泛应用。在复杂网络中，节点与节点之间不仅存在直接相连的低阶结构，也存在以特殊连接模式形成的高阶结构，称为模体。提出一种融合二连通模体结构信息的节点分类算法（FMI），利用节点间高阶二连通模体信息学习节点表示，完成节点分类任务。首先，统计网络中的二连通模体，利用其中信息提出一个节点重要性的度量指标——模体比值。根据模体比值计算采样概率进行邻域采样；构造一个带权辅助图以融合网络节点连接的低阶关系与高阶关系，对节点进行加权邻域聚合以得到节点表示。在5个数据集Cora、Citeseer、Pubmed、Wiki和DBLP上执行节点分类任务，与5种经典基准算法进行对比，所提算法FMI在准确度和F1-分数等指标上表现良好。

关键词: 节点表示, 二连通模体, 邻域采样, 邻域聚合, 节点分类