基于图表示学习与维度选择的Top-k相似节点搜索研究

作     者：明钰博 

作者单位：安徽大学 

学位级别：硕士

导师姓名：叶凡

授予年度：2023年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 080402[工学-测试计量技术及仪器] 0804[工学-仪器科学与技术] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：Top-k节点搜索 无监督学习 图表示学习 维度选择 

摘      要：Top-k相似节点搜索问题是网络信息挖掘中的经典且重要的问题,旨在为网络中的节点寻找与其相似的前k个节点。随着网络与现实数据的爆炸性增长,为网络中的节点寻找适量的相似节点变得愈来愈困难,这在社交网络节点信息挖掘领域引起了不少学者的研究兴趣。基于无监督图表示学习的Top-k相似节点搜索具有速度快,复用性高,没有冷启动等优点。然而,现有的无监督图表示学习方法在提取节点信息时并没有充分的挖掘节点的全局信息以及高效的融合节点的局部信息和全局信息。并且在节点嵌入维度的选择上没有一个统一的规则,而是参考以往的经验值。针对目前一些无监督网络图表示学习方法所存在的问题,本文的主要工作如下: (1)提出了一种基于无监督图表示学习的Top-k相似节点搜索算法。首先,通过随机游走算法设置路径长度来获得节点的局部拓扑信息,再采用跳字模型获得节点与附近节点的相关性信息并构建全局共现矩阵。其次,通过对共现矩阵的处理得到所有节点之间的相关性信息,从而获得节点的全局信息,然后融合局部信息和全局信息再做进一步处理。最后,根据不同的处理过程设计不同的损失函数,然后通过数次的迭代训练获得网络节点的嵌入向量并将其应用至Top-k相似节点搜索任务中。在真实数据集的实验结果表明,该方法在性能评估上较其他无监督图表示学习算法提升了3%至5%。 (2)提出了一种基于最小化信息熵的图表示学习维度选择算法。此方法旨在获取能充分保留网络信息的节点嵌入向量维度最小值,寻找一个符合一般研究经验并能通过参数来确定节点最小嵌入维度的方法。该方法基于跳字模型总信息熵的性质,通过采样近似和假设分布确定参数,然后采用蒙特卡洛模拟算法确定信息熵与嵌入维度的关系,最后通过最小化信息熵确定节点最小嵌入维度值。在Top-k相似节点搜索任务和归一化嵌入函数评价标准上的实验结果表明,该方法选择的最小嵌入维度值能达到精度要求并且比一般经验维度嵌入值减少了30%至50%。