| 基于随机化矩阵分解的网络嵌入方法 |
| 来源：一起赢论文网 日期：2021-11-25 浏览数：1008 【 字体： 大 中 小 大 中 小 大 中 小 】 |
|
第４４ 卷 第３ 期２０２１ 年３ 月计 算机 学 报ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳＶｏｌ ．４４Ｎｏ． ３Ｍａｒ． ２０２１基于随机化矩阵分解的网络嵌入方法谢雨洋 冯 栩 喻文健 唐 杰（清华大学计算机科学与技术系 北京 １０００８ ４）（北京信息科学与技术国家研究中心 北京 １００ ０８ ４）摘 要 随着互联网的普及， 越来越多的问题以社交网络这样的网络形式出现． 网络通常用图数据表示， 由于图数据处理的挑战性， 如何从图中学习到重要的信息是当前被广泛关注的问题． 网络嵌人就是通过分析图数据得到反映网络结构的特征向量， 利用它们进而实现各种数据挖掘任务， 例如边预测、节点分类、网络重构、标签推荐和异常检测． 最近， 基于矩阵分解的网络嵌人方法ＮｅｔＭＦ被提出， 它在理论上统一了多种网络嵌人方法， 并且在处理实际数据时表现出很好的效果．然而， 在处理大规模网络时， ＮｅｔＭＦ需要极大的时间和空间开销． 本文使用快速随机化特征值分解和单遍历奇异值分解技术对ＮｅｔＭＦ进行改进， 提出一种高效率、且内存用量小的矩阵分解网络嵌人算法ｅＮｅｔＭＦ． 首先， 我们提出了适合于对称稀疏矩阵的随机化特征值分解算法ｆｒｅｉｇｓ， 它在处理实际的归一化网络矩阵时比传统的截断特征值分解算法快近１０ 倍， 且几乎不损失准确度． 其次， 我们提出使用单遍历奇异值分解处理ＮｅｔＭＦ方法中高次近似矩阵从而避免稠密矩阵存储的技术， 它大大减少了网络嵌人所需的内存用量．最后， 我们提出一种简洁的、 且保证分解结果对称的随机化单遍历奇异值分解算法， 将它与上述技术结合得到ｅＮｅｔＭＦ算法． 基于５ 个实际的网络数据集， 我们评估了ｅＮｅｔＭＦ学习到的网络低维表示在多标签节点分类和边预测上的有效性．实验结果表明， 使用ｅＮｅｔＭＦ替代ＮｅｔＭＦ后在后续得到的多标签分类性能指标上几乎没有损失， 但在处理大规模数据时有超过４０倍的加速与内存用量节省． 在一台３２ 核的机器上， ｅＮｅｔＭＦ 仅需约１．３ｈ即可对含一百多万节点的ＹｏｕＴｕｂｅ 数据学习到网络嵌人， 内存用量仅为１２０ＧＢ， 并得到较高质量的分类结果． 此外， 最近被提出的网络嵌人算法ＮｅｔＳＭＦ 由于图稀疏化过程的内存需求太大， 无法在２５６ＧＢ内存的机器上处理两个较大的网络数据， 而ＰｒｏＮＥ算法则在多标签分类的结果上表现不稳定， 得到的Ｍａｃｒｏ ＦＩ 值都比较差．因此，ｅＮｅｔＭＦ算法在结果质量上明显优于ＮｅｔＳＭＦ和ＰｒｏＮＥ算法． 在边预测任务上，ｅＮｅｔＭＦ算法也表现出与其它方法差不多甚至更好的性能．关键词 网络嵌人； 网络表示学习； 随机化特征值分解； 单遍历奇异值分解； 多标签节点分类中图法分类号ＴＰ１８ＤＯＩ号１０．１１８９７／ＳＰ．Ｊ．１０１６ ．２０２１． ００４４７ＬｅａｒｎｉｎｇＮｅｔｗｏｒｋＥｍｂｅｄｄｉｎｇｗｉｔｈＲａｎｄｏｍｉｚｅｄＭａｔｒｉｘＦａｃｔｏｒｉｚａｔｉｏｎＸＩＥＹｕ ＹａｎｇＦＥＮＧＸｕＹＵＷｅｎＪｉ ａｎＴＡＮＧＪｉ ｅ｛ ＤｅｐａｒＬｍｅｎＬｏｆＣｏｍｐｕｔｅｒＳｃｉ ｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ？ ＴｓｉｎｇｈｕａＵｎｉｖｅｒｓｉ ｔｙ？ Ｂｅｉｊｉ ｎｇ１０００ ８４）（ＢｅｉｊｉｎｇＮａｔｉｏｎａｌＲｅｓｅａｒｃｈＣｅｎｔ ｅｒｆｏｒＩｎｆｏｒｍａｔｉｏｎＳｃｉ ｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ？ Ｔｓｉ ｎｇｈｕａＵｎｉ ｖｅｒｓｉｔｙ？Ｂｅｉｊｉ ｎｇ１０００ ８４）ＡｂｓｔｒａｃｔＷｉｔｈｔｈｅｐｏｐｕｌａｒｉｔｙｏｆｔｈｅＩｎｔｅｒｎｅｔ ，ｍｏｒｅａｎｄｍｏｒｅｐｒｏｂｌ ｅｍｓａｐｐｅａｒｉｎｔｈｅｆｏｒｍｏｆｎｅｔｗｏｒｋｓｓｕｃｈａｓｓｏｃｉａｌｎｅｔｗｏｒｋｓ． Ｎｅｔｗｏｒｋｓａｒｅｏｆｔｅｎｏｒｇａｎｉｚｅｄｂｙｇｒａｐｈｄａｔａａｎｄｉｔｉｓｗｉ ｄｅｌ ｙａｃｃｅｐｔｅｄｔｈａｔｇｒａｐｈｄａｔａｉｓｓｏｐｈｉｓｔｉｃａｔｅｄａｎｄｃｈａｌ ｌ ｅｎｇｉ ｎｇｔｏｄｅａｌｗｉｔｈ．Ｔｈｅｒｅｆｏｒｅ，ｈｏｗｔｏｌ ｅａｒｎｉ ｍｐｏｒｔａｎｔｉ ｎｆｏｒｍａｔｉ ｏｎｆｒｏｍｔｈｅｇｒａｐｈｉｓｃｕｒｒｅｎｔｌ ｙａｗｉｄｅｓｐｒｅａｄｃｏｎｃｅｒｎ．Ｎｅｔｗｏｒｋｅｍｂｅｄｄｉ ｎｇ，ｗｈｉｃｈａｉ ｍｓｔｏｌ ｅａｒｎｌ ａｔｅｎｔｒｅｐｒｅｓｅｎｔａｔｉ ｏｎｓｆｏｒｎｅｔｗｏｒｋｓ，ｉｓａｎｉｍｐｏｒｔａｎｔｆｉｅｌ ｄｉ ｎｄａｔａｍｉｎｉ ｎｇ． Ｔｈｅｒｅｓｕｌ ｔｏｆｎｅｔｗｏｒｋｅｍｂｅｄｄｉ ｎｇｓｈｏｕｌ ｄｐｒｅｓｅｒｖｅｎｅｔｗｏｒｋｓｔｒｕｃｔｕｒｅａｎｄｃａｎｂｅｕｓｅｄａｓｔｈｅｆｅａｔｕｒｅｓｆｏｒｆｕｒｔｈｅｒａｐｐｌ ｉ ｃａｔｉｏｎｓｏｎｄａｔａｍｉｎｉ ｎｇｔａｓｋｓｌ ｉ ｋｅｌ ｉ ｎｋｐｒｅｄｉ ｃｔｉ ｏｎ，ｎｏｄｅｃｌ ａｓｓｉｆｉ ｃａｔｉ ｏｎ，ｎｅｔｗｏｒｋｒｅｃｏｎｓｔｒｕｃｔｉ ｏｎ，ｔａｇｒｅｃｏｍｍｅｎｄａｔｉ ｏｎａｎｄａｎｏｍａｌ ｙｄｅｔｅｃｔｉ ｏｎ．Ｓｋｉｐ ｇｒａｍｂａｓｅｄａｌｇｏｒｉｔｈｍｓｌｉ ｋｅ收稿日期：２０ ２０ ０３ ２０； 在线发布日期：２０２０ ０８ ２３ ． 本课题得到科技创新２０３０“新一代人工智能”重大项目（２０２０ＡＡＡ０１０３５０２） 及国家自然科学基金（ ６１８ ７２２０ ６） 资助． 谢雨洋， 博士研究生， 主要研究方向为数据挖掘、 矩阵算法． Ｅｍａｉｌ： ｘｙｙｌ８＠ｍａｉｌＳ．ｔｓｉｎｇｈｕａ．ｅｄｕ．ｃｎ．冯 栩， 博士研究生， 主要研究方向为矩阵算法． 喻文健（ 通信作者） ， 博士， 副教授， 中国计算机学会（ ＣＣＦ） 会员， 主要研究方向为集成电路计算机辅助设计、 矩阵算法． Ｅｍａｉｌ ：ｙｕｗｊ ＠ｔｓｉ ｎｇｈｕａ．ｅｄｕ．ｃｎ． 唐 杰， 博士， 教授， 中国计算机学会（ＣＣＦ） 会员， 主要研究领域为社交网络挖掘与学术知识图谱．４４８ 计 算机 学 报 ２０２１年ＤｅｅｐＷａｌ ｋ，ＬＩＮＥ，ｎｏｄｅ２ｖｅｃｈａｖｅｂｅｅｎｃｏｍｍｏｎｌ ｙｃｏｎｓｉ ｄｅｒｅｄａｓｐｏｗｅｒｆｕｌｂｅｎｃｈｍａｒｋｓｏｌ ｕｔｉ ｏｎｓｆｏｒｅｖａｌ ｕａｔｉ ｎｇｎｅｔｗｏｒｋｅｍｂｅｄｄｉ ｎｇｒｅｓｅａｒｃｈ．Ｒｅｃｅｎｔｌ ｙ，ｎｅｔｗｏｒｋｅｍｂｅｄｄｉｎｇａｓｍａｔｒｉ ｘｆａｃｔｏｒｉｚａｔｉ ｏｎ（ＮｅｔＭＦ）ｗａｓｐｒｏｐｏｓｅｄ． ＩｔｓｈｏｗｓｔｈａｔＤｅｅｐＷａｌ ｋｉ ｓａｃｔｕａｌ ｌｙｉ ｍｐｌ ｉ ｃｉ ｔｌ ｙｆａｃｔｏｒｉ ｚｉ ｎｇａｎｅｔｗｏｒｋ’ｓｎｏｒｍａｌ ｉｚｅｄＬａｐｌａｃｉ ａｎｍａｔｒｉｘ，ａｎｄＬＩＮＥ，ｉ ｎｔｈｅｏｒｙ，ｉｓａｓｐｅｃｉａｌｃａｓｅｏｆＤｅｅｐＷａｌ ｋ．ＮｅｔＭＦｔｈｅｏｒｅｔｉ ｃａｌ ｌ ｙｕｎｉｆｉ ｅｓｓｅｖｅｒａｌｎｅｔｗｏｒｋｅｍｂｅｄｄｉ ｎｇｍｅｔｈｏｄｓａｎｄｓｈｏｗｓｉ ｔｓｓｕｐｅｒｉ ｏｒｉ ｔｙｗｈｅｎｐｒｏｃｅｓｓｉ ｎｇｔｈｅｒｅａｌｎｅｔｗｏｒｋｄａｔａ．Ｈｏｗｅｖｅｒ，ｔｈｅｅｘｃｅｓｓｉ ｖｅｒｕｎｔｉｍｅａｎｄｓｔｏｒａｇｅｏｆＮｅｔＭＦｌ ｉｍｉ ｔｓｉ ｔｓｕｓａｇｅｏｎｌ ａｒｇｅ ｓｃａｌ ｅｄａｔａ．Ｉｎｔｈｉ ｓｗｏｒｋ，ｗｅｕｓｅｆａｓｔｒａｎｄｏｍｉ ｚｅｄｅｉｇｅｎｖａｌ ｕｅｄｅｃｏｍｐｏｓｉｔｉｏｎ（ ＥＶＤ）ａｎｄｓｉ ｎｇｌ ｅｐａｓｓｓｉ ｎｇｕｌ ａｒｖａｌ ｕｅｄｅｃｏｍｐｏｓｉ ｔｉ ｏｎ（ＳＶＤ）ｔｏｉ ｍｐｒｏｖｅＮｅｔＭＦａｎｄｐｒｅｓｅｎｔａｎｅｆｆｉｃｉ ｅｎｔｒａｎｄｏｍｉ ｚｅｄｍａｔｒｉ ｘｆａｃｔｏｒｉ ｚａｔｉｏｎｂａｓｅｄｎｅｔｗｏｒｋｅｍｂｅｄｄｉ ｎｇａｌｇｏｒｉ ｔｈｍ（ ｅＮｅｔＭＦ）．Ｆｉｒｓｔｌｙ，ｗｅｐｒｏｐｏｓｅａｆａｓｔｒａｎｄｏｍｉｚｅｄＥＶＤａｌｇｏｒｉｔｈｍ（ ｆｒｅｉｇｓ）ｆｏｒｓｐａｒｓｅｍａｔｒｉ ｘ．Ｉｔｉｓａｂｏｕｔ１０Ｘｆａｓｔｅｒｔｈａｎｔｒａｄｉ ｔｉ ｏｎａｌｔｒｕｎｃａｔｅｄＥＶＤａｌｇｏｒｉｔｈｍｓｆｏｒｔｈｅｎｏｒｍａｌ ｉ ｚｅｄｎｅｔｗｏｒｋｍａｔｒｉ ｘ，ｗｈｉ ｌｅｋｅｅｐｉ ｎｇａｃｃｕｒａｃｙ． Ｓｅｃｏｎｄｌｙ，ｗｅｐｒｏｐｏｓｅｔｏｕｓｅｓｉｎｇｌ ｅ ｐａｓｓＳＶＤａｐｐｒｏａｃｈｔｏｐｒｏｃｅｓｓｈｉｇｈ ｏｒｄｅｒｐｒｏｘｉ ｍｉ ｔｙｍａｔｒｉ ｘｉｎｔｈｅＮｅｔＭＦ，ｓｏｔｈａｔｗｅｃａｎａｖｏｉｄｓｔｏｒｉｎｇｔｈｅｌａｒｇｅｄｅｎｓｅｍａｔｒｉ ｘａｎｄｌａｒｇｅｌｙｒｅｄｕｃｅｔｈｅｍｅｍｏｒｙｃｏｓｔｆｏｒｎｅｔｗｏｒｋｅｍｂｅｄｄｉｎｇ． Ｔｈｉｒｄｌ ｙ，ｗｅｐｒｏｐｏｓｅａｓｉ ｍｐｌｉｆｉｅｄ，ｒａｎｄｏｍｉ ｚｅｄｓｉ ｎｇｌ ｅｐａｓｓＳＶＤａｌｇｏｒｉｔｈｍｔｈａｔｇｕａｒａｎｔｅｅｓａｓｙｍｍｅｔｒｉｃｄｅｃｏｍｐｏｓｉｔｉｏｎｒｅｓｕｌｔ． Ｃｏｍｂｉ ｎｉ ｎｇｔｈｅａｂｏｖｅｔｅｃｈｎｉｑｕｅｓ，ｗｅｆｉｎａｌ ｌｙｏｂｔａｉｎｔｈｅｅＮｅｔＭＦａｌｇｏｒｉｔｈｍ．Ｗｉｔｈｆｉ ｖｅｒｅａｌｎｅｔｗｏｒｋｄａｔａｓｅｔｓ， ｗｅｅｖａｌ ｕａｔｅｔｈｅｅｆｆｉｃｉｅｎｃｙａｎｄｅｆｆｅｃｔｉ ｖｅｎｅｓｓｏｆｔｈｅｅＮｅｔＭＦａｌｇｏｒｉｔｈｍｏｎｍｕｌ ｔｉｌ ａｂｅｌｎｏｄｅｃｌａｓｓｉ ｆｉｃａｔｉ ｏｎａｎｄｌｉ ｎｋｐｒｅｄｉｃｔｉ ｏｎ，ｃｏｍｍｏｎｌ ｙｕｓｅｄｔａｓｋｓｆｏｒｎｅｔｗｏｒｋｅｍｂｅｄｄｉ ｎｇｅｖａｌ ｕａｔｉ ｏｎ．Ｅｘｐｅｒｉ ｍｅｎｔａｌｒｅｓｕｌ ｔｓｓｈｏｗｔｈａｔｉ ｎｔｅｒｍｓｏｆｔｈｅｍｅｔｒｉｃｓＭａｃｒ〇 ＦｌａｎｄＭｉｃｒｏＦｌ，ｔｈｅｅｍｂｅｄｄｉ ｎｇｇｅｎｅｒａｔｅｄｂｙｅＮｅｔＭＦｈａｓｔｈｅｓａｍｅｐｅｒｆｏｒｍａｎｃｅａｓＮｅｔＭＦｉ ｎｍｕｌ ｔｉｌ ａｂｅｌｎｏｄｅｃｌ ａｓｓｉ ｆｉｃａｔｉ ｏｎ． Ｆｏｒａｌ ａｒｇｅ ｓｃａｌ ｅｇｒａｐｈｄａｔａ，ｅＮｅｔＭＦｅｘｈｉ ｂｉｔｓｍｏｒｅｔｈａｎ４０Ｘａｃｃｅｌ ｅｒａｔｉ ｏｎａｎｄｍｅｍｏｒｙｕｓａｇｅｓａｖｉｎｇｏｖｅｒＮｅｔＭＦ．Ｏｎａｍａｃｈｉｎｅｗｉｔｈ３２ｃｏｒｅｓ，ｅＮｅｔＭＦｔａｋｅｓｏｎｌ ｙ１．３ ｈａｎｄ１２０ ＧＢｍｅｍｏｒｙｔｏｌ ｅａｒｎａｇｏｏｄｎｅｔｗｏｒｋｅｍｂｅｄｄｉ ｎｇｆｏｒｔｈｅｌ ａｒｇｅｓｔｔｅｓｔｄａｔａ（ＹｏｕＴｕｂｅ）ｗｈｉｃｈｈａｓｍｏｒｅｔｈａｎｏｎｅｍｉｌ ｌｉ ｏｎｎｏｄｅｓ．Ｉｎａｄｄｉｔｉ ｏｎ，ｄｕｅｔｏｔｈｅｍｅｍｏｒｙｃｏｓｔｏｆｓｐｅｃｔｒａｌｓｐａｒｓｉ ｆｉｃａｔｉｏｎ，ｔｈｅｒｅｃｅｎｔｌ ｙｐｒｏｐｏｓｅｄｎｅｔｗｏｒｋｅｍｂｅｄｄｉ ｎｇａｌｇｏｒｉｔｈｍＮｅｔＳＭＦｃａｎｎｏｔｈａｎｄｌ ｅｔｗｏｌ ａｒｇｅｎｅｔｗｏｒｋｄａｔａｏｎａｍａｃｈｉ ｎｅｗｉ ｔｈ２５６ＧＢｍｅｍｏｒｙ，ｗｈｉ ｌ ｅｔｈｅＰｒｏＮＥａｌｇｏｒｉ ｔｈｍｐｒｏｄｕｃｅｓｕｎｓｔａｂｌ ｅｒｅｓｕｌ ｔｓｏｆｍｕｌｔｉ ｌ ａｂｅｌｎｏｄｅｃｌ ａｓｓｉｆｉ ｃａｔｉ ｏｎ． Ｔｏｂｅｐｒｅｃｉ ｓｅ，Ｍａｃｒ〇Ｆｌｏｂｔａｉ ｎｅｄｗｉ ｔｈＰｒｏＮＥｉ ｓｇｅｎｅｒａｌ ｌ ｙｐｏｏｒ． Ｔｈｅｒｅｆｏｒｅ，ｔｈｅｅＮｅｔＭＦａｌｇｏｒｉ ｔｈｍｉ ｓａｄｖａｎｔａｇｅｏｕｓｔｏｔｈｅＮｅｔＳＭＦａｎｄＰｒｏＮＥａｌｇｏｒｉｔｈｍｓｉｎｔｅｒｍｓｏｆｐｅｒｆｏｒｍａｎｃｅ． Ｉｎｔｈｅｌ ｉ ｎｋｐｒｅｄｉｃｔｉ ｏｎｔａｓｋ，ｔｈｅｅＮｅｔＭＦａｌｇｏｒｉ ｔｈｍａｃｈｉ ｅｖｅｓｂｅｔｔｅｒｏｒｃｏｍｐａｒａｂｌ ｅｐｅｒｆｏｒｍａｎｃｅｗｈｅｎｃｏｍｐａｒｅｄｔｏｏｔｈｅｒｂａｓｅｌ ｉ ｎｅｓ．Ｋｅｙｗｏｒｄｓｎｅｔｗｏｒｋｅｍｂｅｄｄｉ ｎｇ；ｎｅｔｗｏｒｋｒｅｐｒｅｓｅｎｔａｔｉ ｏｎｌ ｅａｒｎｉ ｎｇ；ｒａｎｄｏｍｉ ｚｅｄｅｉｇｅｎｖａｌ ｕｅｄｅｃｏｍｐｏｓｉ ｔｉ ｏｎ；ｓｉ ｎｇｌ ｅｐａｓｓｓｉ ｎｇｕｌ ａｒｖａｌ ｕｅｄｅｃｏｍｐｏｓｉ ｔｉ ｏｎ；ｍｕｌ ｔｉ ｌ ａｂｅｌｎｏｄｅｃｌ ａｓｓｉｆｉ ｃａｔｉ ｏｎｉ 引 言社交网络等大规模复杂网络的挖掘与智能分析是当前的研究热点． 这种网络包括微信、微博用户之间通过好友关系和互相联动形成的在线社交网络、学术论文之间的引用关系形成的网络［ １ ］等等． 进行图数据挖掘主要有图卷积网络和网络嵌人两种方法． 网络嵌人一般不考虑节点的属性， 侧重于学习节点的拓扑结构， 而图卷积网络可以将节点的属性作为特征一起学习， 对于属性敏感的实验数据， 图卷积网络的效果要更好， 但由于很多网络数据缺少节点属性特征， 图卷积网络对此类数据节点拓扑结构的学习不如网络嵌人， 因此网络嵌人在图数据挖掘中占有很重要的地位． 应用网络嵌人的方法对网络进行分析， 首先要将网络用图的邻接矩阵表示． 接下来， 还要将网络中的每个节点映射到一个低维稠密实数向量上， 这样可以很好地保存节点的拓扑结构信息， 同时有利于使用机器学习等智能处理方法进行后续分析． 因此网络嵌人的目标就是将网络映射到潜在的低维空间， 得到网络节点的低维表示［ ２ ］． 研究表明， 网络嵌人技术可以促进各种网络分析与应用［３］， 例如边预测、节点分类、 网络重构、标签推荐和异常检测． 通常， 基于传统拓扑的网络表示直接使用谢雨洋等： 基于随机化矩阵分解的网络嵌人方法 ４４９３ 期对应图的邻接矩阵， 但这可能包含噪声或冗余信息．若使用网络嵌人技术， 每个节点都由包含潜在信息的向量表示， 因此许多网络分析中的迭代或组合的问题可以通过计算映射函数， 距离度量或嵌人向量运算的方式解决， 从而避免了高复杂度．主要的网络嵌人方法包括ＤｅｅｐＷａｌｋ？、ＬＩＮＥ［４］、ｎｏｄｅ２ｖｅｃ［５］、ｍｅｔａｐａｔｈ２ｖｅｃ［６］等， 它们都是基于ｓｋｉｐｇｒａｍ的模型 ？ 最近， 文献 ［７］指出ＤｅｅｐＷａｌ ｋ和ＬＩＮＥ都可以看成是基于矩阵分解的技术， 并提出了一种基于矩阵分解的网络嵌人方法ＮｅｔＭＦ， 基于它在后续进行网络节点多标签分类时表现出比使用ＤｅｅｐＷａｌ ｋ和ＬＩＮＥ更好的性能． 然而， ＮｅｔＭＦ在处理超大规模网络时需要巨大的内存开销和计算成本， 这主要是由于它得到的高次近似矩阵是稠密的． 后续， 人们基于谱图稀疏化理论对ＮｅｔＭＦ进行了改进， 得到了利用谱图稀疏化理论和稀疏矩阵分解的网络嵌人方法ＮｅｔＳＭＦ［８］和Ｐｒ〇ＮＥ［９］， 这使得处理超大规模网络成为可能． 但是， 稀疏化矩阵的过程仍然需要大量的内存， 这使得ＮｅｔＳＭＦ的应用受到一定的限制， 而ＰｒｏＮＥ得到的网络嵌人在应用时的效果也存在不稳定的问题．另一方面， 牺牲少量准确度的随机化低秩矩阵分解方法由于其适用于现代计算机体系结构和某些大数据应用场景正得到越来越多的关注［１＂１ １］． 本文将随机化矩阵分解技术与网络嵌人方法ＮｅｔＭＦ相结合， 提出了一种快速、 节省内存、 且保证准确度的网络嵌人算法ｅＮｅｔＭＦ． 具体的创新点如下：（１） 提出使用单遍历奇异值分解处理ＮｅｔＭＦ方法中高次近似矩阵从而避免存储此稠密矩阵的思路， 显著减少了ＮｅｔＭＦ方法所需的内存开销．（２） 提出针对稀疏对称矩阵的随机化特征值分解算法， 并调节需进行特征值分解的归一化网络矩阵奇异值衰减速度， 从而在保证准确性的同时显著加快了ＮｅｔＭＦ方法中高次近似矩阵的构造．（３） 提出一种简洁的且保证分解结果对称的随机化单遍历奇异值分解算法， 将它用于ＮｅｔＭＦ算法中减少了计算时间、 又保证了网络嵌人的质量．实验结果表明， 在相对较大的真实数据集上， 随机化特征值分解算法比传统截断特征值分解算法快１０ 倍， 且几乎没有误差． 而进行网络嵌人后再做节点多标签分类和边预测的实验中， ｅＮｅｔＭＦ算法在保持ＮｅｔＭＦ结果质量的同时大大减少了其计算时间与内存用量． 例如， 对Ｆｌｉｃｋｒ 数据ｅＮｅｔＭＦ的运行时间和内存用量分别为ＮｅｔＭＦ的１／４１ 和１／４６， 而对于节点数超过１ 百万、ＮｅｔＭＦ与ＮｅｔＳＭＦ由于内存需求太大无法处理的ＹｏｕＴｕｂｅ 数据， ｅＮｅｔＭＦ只需１．３ ｈ和１２０ＧＢ 内存开销即可得到网络嵌人， 并取得很好的多标签分类结果．２ 相关工作近年来兴起的网络嵌人的研究起源于自然语言处理领域的表示学习［ １ ２ ］， 该类问题的研究可以追溯到谱图理论［１ ３］， 社交维度学习［１ ４］等研究． 随着该领域的发展， 很多网络嵌人的方法都旨在建模节点的相似性． 谱网络嵌人方法和谱降维方法相关， 例如快速近似谱聚类方法［１ ５］和拉普拉斯特征映射方法［１ ６］．受ｗｏｒｄ２ｖｅｃ模型［１ ２］的启发，一类基于ｓｋｉｐ ｇｒａｍ模型的方法被提出， 并有很好的性能， 例如ＤｅｅｐＷａｌ ｋ？、ＬＩＮＥ［ ４］、ｎｏｄｅ２ｖｅｃ［ ５ ］、 ｍｅｔａｐａｔｈ２ｖｅｃ［ ６ ］等模型． 最近，受词嵌人问题转化为矩阵分解的启发［ １ ７ ］， 文献［７］指出基于ｓｋｉｐ ｇｒａｍ这一类的方法可以转化成矩阵分解问题． 通过将随机游走的过程建模成矩阵的乘法， 然后在近似的高阶矩阵上做奇异值分解， 可以得到网络节点的低维表示． 并且， 其中提出的ＮｅｔＭＦ方法在设置较大窗口大小参数时可以得到高质量的网络嵌人， 基于它再做网络节点多标签分类时表现出比使用ＤｅｅｐＷａｌ ｋ和ＬＩＮＥ更好的性能？除了文献［７］的ＮｅｔＭＦ方法外， 其它基于矩阵分解的网络嵌人模型还包括ＧｒａＲｅｐ［ １ ８ ］、ＨＯＰＥ［ １９ ］、ＴＴＡＤＷ［ ２ ＜＾ｔＩＤＨＰＥ［ ２ １ ］， 其中ＧｒａＲｅｐ模型考虑整合高次相似度矩阵来获取节点的相似度信息， 但巨大的计算量和内存开销限制了其在大规模网络上的应用， ＨＯＰＥ模型可以应用于有向图的场景， ＴＡＤＷ模型可以应用于节点带有特征信息的数据， ＤＨＰＥ模型可以应用于动态网络的场景． 最近， 也有几个ＮｅｔＭＦ方法的改进算法被提出． ＮｅｔＳＭＦ［８］通过引人谱图稀疏化方法使得模型可以运行得较快， 不过仍然需要较大的运行内存． Ｐｒ〇ＮＥ［ ９ ］方法通过交换随机游走和矩阵分解的过程， 先对稀疏矩阵分解得到节点的低维表示， 然后再对节点的低维表示做信息传播增强， 这样大大降低了整体的计算复杂度． 然而， 在后续使用节点低维表示的应用任务（如多标签分类） 中， ＰｒｏＮＥ的性能很不稳定， 往往比ＮｅｔＭＦ的结果差．３ 技术背景在本文中， 为了方便描述算法， 我们采用Ｍａｔｌ ａｂ４５０ 计 算机 学 报 ２０２１年所使用的方法来指定矩阵的部分元素．３． １ 奇异值分解和特征值分解矩阵ＡｅＲ？ｘ＂的奇异值分解（ＳＶＤ） 可以表示为Ａ＝ＵＳＶＴ（１）其中［／＝［Ｍ！， Ｍ２，…］和Ｖ＝［Ｗ！， ，…］是分别包含左右奇异向量的正交矩阵． 对角矩阵ｚ包含了矩阵Ａ的奇异值（的， 内，…） ？ 设队和１分别是［／ 和Ｖ的前々 列， 对角矩阵厶包含矩阵Ａ的前＆ 个最大的奇异值， 矩阵Ａ的截断ＳＶＤ可以表示为人， 即Ａ＾Ａｔ＝ＵｋＳｋＶｌ（２）其中Ａｔ也是初始矩阵Ａ的最佳秩＆ 近似［ ２ ２ ］．若Ａ为对称矩阵， 它存在如下形式的特征值分解（ ＥＶＤ） ：Ａ＝ＵＡＵｔ（３）其中ｙｉ 为对角阵， 其对角元为Ａ的特征值， 正交矩阵［／ 的各列是Ａ的特征向量． 由于实对称阵的特征值均为实数， 只需将式（ ３） 中Ａ的负对角元取相反数、 然后将Ｃ／Ｔ的相应行也取相反数， 式（３） 即可变成Ａ的奇异值分解， 其中［／ 的各列是Ａ的左奇异向量．类似于截断奇异值分解， 由式（３） 也可以得到截断特征值分解：＝ＵｈＡｈＵＴｈ（４）其中对角阵儿为Ｚｌ Ｘ 的对角阵， 对角元为／！ 个绝对值最大或代数值最大的特征值， 队为［／中与这些特征值相应的特征向量组成的矩阵． 计算截断特征值分解的传统算法为ＡＲＰＡＣＫ算法［２ ３］， 其具体实现包括Ｍａｔｌ ａｂ中的ｅｉｇｓ 命令和Ｐｙｔｈｏｎ 的ｅｉｇｓ、ｅｌｇｓｈ命令等， 它们特别适合处理稀疏矩阵．３． ２ 基于矩阵分解的网络表示本文的主要目的是提出一种ＮｅｔＭＦ算法的改进版本， 它能够显著减少ＮｅｔＭＦ算法的内存用量和计算时间． 由于ＮｅｔＭＦ算法是针对无向图的网络嵌人方法， 我们提出的方法也只考虑无向图即对称稀疏矩阵． 我们用Ｇ＝（ｙ， Ｅ， Ａ） 表示一个无向网络， 其中Ｖ表示顶点集， Ｅ表示边的集合， Ａ表示Ｇ的邻接矩阵．网络嵌人的目标是学习到一个投影， 该投影可以映射每一个顶点到一个々 维向量（ 々■＜＜？） ，使得可以保存它的结构属性信息， 进而这种网络表示被提供给后续的网络分析使用， 例如边预测和节点分类等．最近， 基于矩阵分解的网络嵌人显示出它在网络表示上的优越性． ＤｅｅｐＷａｌ ｋ 是一个近年来被广泛承认的网络嵌人模型， 随机游走的长度对ＤｅｅｐＷａｌ ｋ模型的实验结果有影响． 该参数越大， 随机游走得越远且更多较远的点也会被认为是当前节点相似的节点， 但一定程度上也相当于放宽相似性约束， 可能会引人一些噪声， 因此如何设置这个参数使得实验结果更好并没有普遍适用的结论． 文献［７］揭示了当ＤｅｅｐＷａｌ ｋ里的随机游走的长度达到无穷大时， 它相当于是对矩阵ｔｒｕｎｃ＿ｌ ｏｇ° （Ｖ〇［（ｑＧ）（Ｄ＾ＡＹＤ１ｊ（ ５）作分解， 其中１：］： １１ １１￡；＿１ （＾°表示矩阵的每个元素和１取最大值后再取ｌ ｏｇ， 即ｔｒｕｎｃ＿ｌ ｏｇ〇（ ：ｒ）＝ｌ ｏｇ（ ｍａｘ（ｌ ， ：ｒ） ）（ ６）式（５） 的参数Ｄ为邻接矩阵Ａ生成的对角阵， 其对角元Ｉ ， ｔＷ（Ｇ）二Ｄ， 而参数ｇ和参数６ 分别表示窗口大小和ｓｋｌｐ ｇｒａｍ模型里负采样的大小． 在下面的工作里， 我们考虑带有较大的窗口大小的情况， 比如ＤｅｅｐＷａｌ ｋ 默认的情况下＜７＝１０．文献［７］提出的ＮｅｔＭＦ给基于ｓｋｉｐ ｇｒａｍ的网络嵌人方法奠定了理论基础， 使得网络嵌人模型有更强的可解释性． 算法１ 描述了处理较大窗口的ＮｅｔＭＦ算法［ ７ ］＿算法１．ＮｅｔＭＦ．输人： 邻接矩阵Ａｅｉ ｒｘ＂， 特征值截断参数ｆｅ， 奇异值截断参数ｈ窗口大小ｇ输出： 网络嵌人ＢｅＲ－ｘ＊１．截断特征值分解： ￡＞２． 构造矩阵Ｍ＝Ｄ＂２１／＊（公７１： ；）１／加＂２ｒ１３． 计算Ｍ＝ｔｒｕｎｃ ｌｏｇ。（Ｖ〇｜＾Ｇ）ｊＶｆ）４． 截断奇异值分解： Ｍ？队ｕｒ５．返回￡＝仏对／２然而，当直接应用ＮｅｔＭＦ算法到大规模的数据集上时存在一些问题． 首先， 在算法１ 第１ 步， 对矩阵ｉｒ１ ／ ２ＡＩＴ１ ／ ２做截断特征值分解， 但直接计算特征值分解需要很长的时间． 算法１ 的第２、４ 步也需要花费较多的时间， 且第２ 步存储大的稠密矩阵Ｍ是很有挑战性的． 比如， 当网络节点数《为１１０ 万时， 稠密矩阵Ｍ的存储量超过８ ＴＢ， 这使得该算法很难应用到大型网络分析当中．３． ３ 随机化奇异值分解有关技术基础的随机化奇异值分解算法［ １ °］可以用来计算近似的截断ＳＶＤ， 该算法如算法２ 所示．算法２． 基础随机化奇异值分解．输人： 矩阵Ａｅｉ ｉｒｘ ＂， 奇异值截断参数Ｉ幂迭代参数户， 过采样参数＾谢雨洋等： 基于随机化矩阵分解的网络嵌人方法 ４５ １３ 期输出：１． Ｘ２＝ｒａｎｄｎ（ｎ，々 ＋ｓ）２．ｇ＝ｏｒｔｈ（ＡＸ２）３． ＦＯＲｆ＝１，２，…，＞ＤＯ４． Ｇ＝ｏｒｔｈ（ＡＴｇ）５． ｇ＝ｏｒｔｈ（ＡＧ）６． ＥＮＤＦＯＲ７． Ｂ＝ＱｒＡ８． ［ Ｕ， Ｕ］＝ｓｖｄ（Ｂ）９． Ｕ＝ＱＵ１０．Ｕ＝Ｕ（ ｔ ａｔ ｋ） ，Ｓ＝Ｓ（ｌ ｔ ｋＡｔ ｋ），Ｖ＝Ｖ（ ｔ ｙ ｌ ｔ ｋ）在算法２ 中， １２ 是一个高斯随机矩阵， 参数ｓ使得采样矩阵１２ 超过＆ 列以获得更好的计算结果． 矩阵２的列包含了Ａ列空间的主要基， 因此Ａ？２Ｂ＝２２ｔａ， 然后对一个ａ＋ｄＸｗ大小的矩阵ｂ使用ＳＶＤ， 就可以得到矩阵Ａ的近似截断ＳＶＤ． 算法１的第３？６ 步为幂迭代技术［１ °］， 应用它之后相当于计算矩阵Ｃ４ＡＴ）１的奇异向量， 由于Ｃ４ＡＴ） １的奇异值衰减比原始矩阵Ａ快得多， 使用幂迭代后再做随机化奇异值分解可以使结果更接近最佳秩＆ 近似．幂迭代过程中的正交化〇ｒｔｈ（ ） 可减轻浮点数计算的舍人误差影响， 这个正交化操作通过ＱＲ分解来实现． 随机化奇异值分解算法在很高概率下能保证：Ａ ＱＱＴＡ＝Ａ ＵＳＶＴ＜（ ｌ ＋ｅ）Ａ Ａｔ（７）其中Ａｔ是矩阵Ａ的最佳秩々 近似，ｅ 是一个误差阈值．对于实对称阵ＡｅＲ＂ｘ＂， 对算法２ 稍作修改就可以得到截断特征值分解［ １ °］． 此时算法２ 中的矩阵２表示了Ａ的行空间和列空间的主要基， 因此：Ａ＾ＱＺＱＴ＝ＱＱｔＡＱＱｔ（８）对实对称阵ｚ＝２ＴＡ２做截断特征值分解， 然后将分解结果代人式（８） 就可以得到矩阵Ａ的近似截断特征值分解．应当指出， 由式（ ８） 得到的算法相比基于Ａ？２２ｔａ的算法其低秩近似效果差一些． 对于对称矩阵， Ｔｒ〇ＰＰ等人最近提出了基于２２ＴＡ形式的近似、且保证结果仍为对称矩阵的方法［ ２ ４］， 它对原矩阵的近似程度更好． 基于算法２ 得到的矩阵２、ｂ， 即得到原矩阵Ａ的近似矩阵Ａ＝２Ｂ， 文献［２４］指出：Ａｓｙｍ＝＾（Ａ＋ＡＴ）＝＾（ＱＢ＋ＢｔＱｔ）（９）为对Ａ近似程度更好的对称矩阵． 根据文献［２５］ ，Ａｓｙｍ是Ａ到所有《 阶实对称阵形成的凸集上的投影， 由于Ａ本身也在这个凸集内， 则根据文献［２６］＾■定有：ＩＡ Ａｓｙｍ｜ ｜ ｆ＜ＩＡ ＡＩＦ（ １０）并且， 对Ａｓｙｍ再做低秩近似得到的结果也比Ａ的结果更准确［ ２ ４］．此外， 文献［２７］提出了一种单遍历奇异值分解算法， 它在数学上与幂迭代参数ｆ＝〇 的算法２ 等价， 但只需要对矩阵Ａ访问一遍， 特别适合于在内存受限的情况下处理大型的稠密矩阵、 或者高效率地处理流数据． 针对大型稀疏矩阵， 文献［２８］提出了高效率的随机化ＳＶＤ算法， 它与算法２ 在数学上等价， 但使用了多种加速技巧可使得对实际大型稀疏矩阵的处理时间缩小９ 倍． 这些加速技巧主要包括：（ １） 利用特征值分解来快速计算细长条矩阵的ＳＶＤ和ＱＲ分解， 即使用ｅｌｇＳＶＤ算法［ ２ ８ ］．（２） 在幂迭代过程中， 每隔一次矩阵乘法之后再做正交化操作．（ ３） 幂迭代中可使用ＬＵ分解替代ＱＲ分解．４ 基于高效矩阵分解的网络嵌入方法在这一节， 我们首先给出利用随机化矩阵分解技术提高ＮｅｔＭＦ方法处理大型网络的效率的主要思路， 然后依次提出针对稀疏实对称阵的快速随机化特征值分解、矩阵Ｍ的高效率构造与隐式存储以及快速单遍历奇异值分解这三项技术， 最后给出算法ｅＮｅｔＭＦ的完整描述， 并做计算量分析．４．１基本思想可粗略地将ＮｅｔＭＦ方法分为三个主要步骤：用截断特征值分解归一化网络矩阵来近似矩阵、 基于特征值分解构造高次近似矩阵Ｍ、计算Ｍ矩阵的截断奇异值分解． 对于大型网络， 第一步和第三步都无法使用传统的矩阵分解算法来实现， 它们需要巨大的运行时间， 而第二步不但有很大的计算量， 而且形成的稠密矩阵造成巨大的内存开销， 也给第三步的执行带来困难．首先我们可以使用随机化特征值分解算法来代替ＮｅｔＭＦ方法的第一个主要步骤， 在几乎不损失准确度的情况下减少其计算量． 其次， 为了解决大型稠密矩阵Ｍ或Ｍ给内存量带来的挑战， 我们提出高次近似矩阵的高效率构造方法以及不显式存储Ｍ和Ｍ， 然后采用单遍历随机化ＳＶＤ算法近似计算奇异值分解的思路， 这样极大地减少了整个算法的内存用量．同时我们还提出快速、 准确的单遍历奇异值分解技术保证最终网络嵌人的结果有足够的准确度．４５ ２ 计 算机 学 报 ２０２１年本文提出的ｅＮｅｔＭＦ算法的流程图如图１ 所示， 图中上排实线框表示本文提出的ｅＮｅｔＭＦ算法输入图Ｇ＝（Ｆ， Ｅ， 』）Ａｔ股主要步骤， 下排虚线框表示ＮｅｔＭＦ箕法的主要步骤？网络嵌入的结果＃［０．３２１，０．７７１，－０．１８９］厲１ｅＮｅｔＭＰ＾＿， 雜爾靡眞（下排虛线： 框； ｔＮｅｔＭｆ算中相霞敵步４．２ 针对稀疏实对称阵的快速随机化特征值分解我们将文献＆８］： 輕出的适用于稀疏矩阵加速分解的技巧与文就［２４１提出的对称矩阵随机化特征值分解算法锫脅． ， 餐到算法丄其中，ｌ ｕ表示对矩阵做ＬＵ分解．算法３．快速随机化特征值分解（ｆｒｇｉｇｓ＞．：输人：艇阵Ａ６： ，＂， 特狼值戴断参数是， ■迭 蠢数６过意導参数输坶５ ｃ：ｅｉ ｒ％灰£ ；４＊１．ｒａｎｄｎ（ｎ，＾ ＋ ５）２．Ｙ＝ＡＱ３．［Ｑ，？，？］＝ｅｉｇＳＶＤ（Ｙ）４．ＦＯＲｆ ＝ｌ，２，？？ ？， 夕ＤＯ５．ＩＦｉ＜ｐＴＨＥＮ６．［２，？］＝ｌｕ（Ａ（Ａ？）７．ＥＬＳＥ８．［２，？，？］＝ｅｉｇＳＶＤ（Ａ （Ａ？）９．ＥＮＤＦＯＲ１０．Ｚ＝ｌＱ，ＡＱ］１１．［ｉ＞， Ｔ］＝ｑｒＣＺ）１２． 乃， ：ｒ２ 分别是矩阵：ｒ的前６＋５ 列和后ａ＋５ 列１３ ．Ｓ＝（Ｔ１ｔ！－＼－Ｔ２ｔＤ／２１４．［Ｕ， ｙ］＝ｅｉｇ（Ｓ＞１５ ．ｉｎｄ为Ａ中Ａ 个最大的特征值的位置索引集合１６．Ｕ＝ ＰｌＫ：ｙｉｎｄ），Ａ＝Ａ（ｉｎｄ，ｉｎｄ）震鑛４的第：ｌ〇？１４＃裹于如Ｔ推导＊ 斑于— —＝Ｙ（２Ｂ＋ＢＴＱＴ？＝ｙＣＳ＞ ＢＴ］［２ＴＪａｉ）如杲对二［２３２］做精简＇的ＱＲ分解５［Ｑ． Ｂ１］＝Ｐｔｒ！， Ｔ，Ｊ（１２）其中Ｐ为列班交阵，［Ａ，Ｔ２ ］为上三角方阵且Ｔ： 和１＾维度一样， 则：－（ＰＴ．ｆ－－（ＰＴ１）Ｔ－ ｙＰ（： ｔ１ ｔＪ＋ｔｚ ｔＤｐｔａｓ）记ｓ （ｉ？＋ｒ２ｉｆ）， 对ｓ作特征值分解？苒代入式（１３） 即得到 的值分解， 进而得到雇矩哞Ａ的近似特怔值分解下面进行算法计算量微空间开销的分析． 设／＝是＋ “隸法３的第２步的浮．点运箕欲＿是〇（：前＊Ｕ）／），ｗｗ（Ａ）为Ａ中＃零元素的数Ｉ根据文献［２８］， 第３＾發步的浮戾运箅次纖、为０（左（ ？ｚ ／２＋＿多（皮）ｉ ，篇１０ 步蠻裏 ＋Ｗ锻Ｕ） Ｄ次浮逼： 貧雾， 簾１１？１６ 步鄉需要 ＋？／２｝ 次浮点运算？ 逋常情况下， ／远小于网络顶点数 算法３ 的浮点运算次数为０（扒《？元４） ／＋？产））？ 考虑到幂迭代参数ｐ与过采样参数ｓ 均为不大时常数， 商由ｆ大规模两络的稀疏性， ｗｍ（Ａ）也本超过》 的某个常数倍｜ 箕法３的时间复杂度为〇（ ｒｔ肢（Ａ从－Ｉ－邊２），， 其中灸 为特怔值截断参数． 这与Ｍａｔｌａｂ 中ｅｉｇｓ命奢的复獻 卷，钽由于随机化算抜中的运算更适合于当前的计算机体系绪构， 算法３ 的运行时间比ｅｉｇｓ 显著缩短， 后面的实验结果将發证这一点， 此外，： 上述分析也表明算法３ 的时间复杂度与矩阵规模呈线性关系．在全间复杂度方商， 矩阵Ａ采用稀疏矩阵方式存储＊而算法渉及的稠密矩阵维数都不超过 或所以算壤３＿空间愈觀愈为〇（＞？？￡（▲； ）＋喊），也与矩阵规模呈栽性关， 系．４． ３ 矩阵Ｍ的高效率构造与隐式存储義ＮｅｔＭＦ＃法中， Ｄ１ ／２ＡＤ—１ ／２的＃征償范圈＇在［１，１］ 賴内ｗ， 对于大型矩阵来说这意味着该谢雨洋等： 基于随机化矩阵分解的网络嵌人方法 ４５ ３３ 期矩阵的奇异值衰减趋势比较缓慢． 随机化算法在处理奇异值衰减缓慢的矩阵时， 得到计算结果的近似误差较大． 为了缓解它给矩阵近似准确度带来的问题， 我们提出在保证算法１ 第２ 步矩阵Ｍ不变的同时修改计算截断特征值分解的矩阵， 通过对一个奇异值衰减较快的矩阵计算截断特征值提高准确度．具体地：ｑｑ（Ｄ＾ＡＹＤ１＝Ｄ１ ＋ａＤＡ（（Ｄ１Ａ）ｒ １）Ｄ＾Ｄ１ ＋ａｒ１「１（１４）其中 （ ｏ，ｉ）． 如果对矩阵 执行截断特征值分解， 即ＤＡＤａ＾ＧｈＨｈＧｊ（ １５）将式（１５） 代人式（１４） 当中， 得Ｘ）（Ｄ＾Ａ） ＾１＾Ｄ１ ＋ａ（ＧｈＨｈＧｊ＋ｒ ｌ１ ＋２ ａＧ＋…＋ＧｈＨｈＧｊ－Ｄ＾Ｇ．Ｈ．ＧＤＤ１ ＾ｑ＝Ｄ１ ＋ａＧｈＨｈ（ＹｊＫｒ＾）ＧｌＤ１ ＋ａ（１６）ｒ １其中１ ＋２ ａＧＡＨＡ， 为一个ＡＸＡ 矩阵． 由于／Ｋ＜ｗ， 计算矩阵Ｋ及（ １６） 中它的各次幂花费的时间很少．因此， 可以将算法１ 中的矩阵Ｍ替换为：ｑＭ＝Ｄ１ ＋ａＧｈＨｈ（Ｋｒ１）ＧＴｈＤ１ ＋ａ（ １７）ｒ１这样， 选择合适的《可使矩阵ＤｉＡＤｉ的奇异值衰减较快， 从而使用算法３ 能比较高效、 准确地得到其截断特征值分解， 也不损失ＮｅｔＭＦ方法中矩阵Ｍ的准确度．为了避免存储稠密矩阵Ｍ或Ｍ， 我们提出一种隐式存储方案， 即考虑分解式Ｍ＝ＦＣＦＴ， 其中＿Ｆ＝Ｄ１ ＋？ＧＡ ， Ｃ＝ｉ＾（ ｆ；ｉｒ〇， 然后分批计算出Ｍ的ｒ １行， 利用下面将介绍的单遍历ＳＶＤ算法计算其截断奇异值分解， 由于它只访问矩阵Ｍ的元素一遍， 对计算出来的Ｍ的若干行处理后即可将其删除， 因此可大大节省内存用量． 而需要存储的矩阵ＦｅＲ＂ＸＡ，（＾肢以＾远小于两＾肢＾的规模．４． ４ 快速准确的单遍历ＳＶＤ算法我们首先提出一种简洁的单遍历ＳＶＤ算法， 它与文献［２７］ 中的算法等价， 但构造 近似矩阵的操作更简洁， 运行效率更高， 如算法４ 所示． 其中， Ａ，表示输人矩阵Ａ 的第ｚ 行， 通过步骤４？７， 我们可以得到两个包含原始矩阵Ａ信息的小矩阵Ｙ和Ｗ，它们保存了矩阵Ａ的行、 列空间的主要成分， 基于它们可以进一步计算Ａ的奇异值分解．算法４．一种更简洁的单遍历ＳＶＤ．输人： 矩阵Ａｅｉｒｘ＂， 奇异值截断参数ｈ过采样参数＾输出：， ｖｅｉ ｒｘ＊１．Ｘ２＝ｒａｎｄｎ（ｎ，是＋ ５）２．ｙ＝［ ］３．Ｗ＝ｚｅｒｏｓ（ｎ＾ ＋ ５）４．ＦＯＲｚ＝１，２， ？ ＊ ？ＤＯ５．ｙ＝ ＡＱｙｙ＝［ｙ；ｊ］６．Ｗ＝Ｗ＼ ＡＩ＇ｙ７．ＥＮＤＦＯＲ８．［ｇ， Ｒ］＝ ｑｒ〇〇９．Ｂ＝ＲＴＷＴ１０．［Ｕ， Ｕ］＝ｓＶｄ（Ｂ）１１． Ｕ＝ ＱＵ１２． Ｕ＝ Ｕ（ ｔ Ａｔｋ），Ｓ＝Ｓ（ｌｔｋ，ｌｔｋ）， Ｖ＝ Ｖ（ ｔ ｙｌｔｋ）在算法４ 中， 步骤８？１２ 是具体计算矩阵Ａ的奇异值分解的过程， 它不同于现有的单遍历ＳＶＤ算法［２ ７］． 定理１ 表明算法４与不做幂迭代的算法２０＝〇） 在数学上是等价的．定理１．在算法４ 中得到的２的各列是ＡＸ２列空间的单位正交基， ｂ＝２ｔａ．证明． 根据算法４的第４？７ 步， 我们得Ｙ＝ＡＸ２， 再根据第８ 步， 对Ｙ执行ＱＲ分解， 因此得到的２的各列是ＡＸ２ 列空间的单位正交基．下面再证Ｂ＝２ＴＡ， 由算法４ 的第４？７ 步， 有再根据第９ 步，Ｂ＝ＲＴＷＴ＝Ｒｔ（ＡｔＡ￡２）ｔ＝ＲｔＱｔＡｔＡ＝（Ａｆ２Ｊ？＾）ＴＡ．又因为 得 ， 将２代人上式， 得Ｂ＝ＱＴＡ．证毕．文献［２７］中的单遍历ＳＶＤ算法与不做幂迭代的基础随机化ＳＶＤ算法（算法２） 在数学上是等价的， 故定理１ 也表明算法４ 与文献［２７］里的单遍历ＳＶＤ算法也是等价的．对于实对称矩阵， 文献［２４］提出的技术可以保证得到的低秩矩阵也是对称的， 从而提高结果的准确性． 将它与算法４ 结合， 得到算法５．算法５． 针对实对称阵的单遍历ＳＶＤ．输人： 矩阵Ｍ６Ｒ＂ｘ ＂， 奇异值截断参数ｈ过采样参数＾输出： ｔ／ｅＲ＂ｘ＊， 從Ｒ＊ｘ＊Ｒ＂ｘ＊１．ｎ＝ｒａｎＡｎｉｎ，ｋ＼ｓ）２．ｙ＝［ ］３．Ｖｙ＝ｚｅｒｏｓ（ｎ，是＋ ５）４５４ 计 算机 学 报 ２０２１年４． ＦＯＲｚ＝１ ， ２， ？ ＊ ？ ＤＯ５． ：ｙ＝ＭＷ， ｙ＝［ｙｊ］６． Ｗ＝Ｗ＼ Ｍｊｙ７． ＥＮＤＦＯＲ８． ［ ２， Ｒ］＝ｑｒ 〇０９． Ｚ＝ｌＱ， ＷＲ１＾１０．［Ｐ， Ｔ］＝ｑｒ（Ｚ）１１．Ｔｕｔ分别是矩阵Ｔ的前Ａ＋ｓ 列和后Ａ＋ ５ 列１２．Ｓ＝（Ｉ＼ Ｔｌ ＼ Ｔ２ Ｔｊ＇）／２１３ ．［＆， Ａ］＝ｅｉｇ⑶１４．ｉ ｎｄ为Ａ中＆个绝对值最大的特征值的位置索引集合１５ ．ｒ／＝Ｐ＆（：，ｉ ｎｄ）， Ｓ＝ａｂｓ（Ａ（ｉｎｄ，ｉｎｄ） ）１６ ．Ｖ＝ ｒ／ｓｉｇｎ（Ａ（ｉｎｄ， ｉｎｄ） ）算法５ 的第９ 步是由于， 根据算法４ ， 我们有Ｂ＝ＲＴＷＴ， 则式（ １２） 中的［２， ＢＴ］＝［ＡＷＲ１］？ 第１４？１６ 步与算法３ 不同， 是由于这里要求奇异值分解，所以需保证Ｚ的对角元非负．４．５ｅＮｅｔＭＦ算法与相关分析结合算法１、３ 和５， 我们得到基于高效矩阵分解的网络嵌人算法ｅＮｅｔＭＦ， 如算法６ 所示．算法６． 基于高效矩阵分解的网络嵌人方法（ｅＮｅｔＭＦ） ．输人： 矩阵ＡｅｉＴｘ ＂， 特征值截断参数ｆｅ， 奇异值截断参数ｈ批处理大小参数＾过采样参数＾归一化参数ａ输出： 网络嵌人ＢｅＲ＂＇１． 用算法３ 计算截断特征值分解２． ｉｆＭＫ＝ＧｌＤ１ ＋２＂Ｇｔ Ｈｔ３．计算Ｆ＝Ｄ１ ＋－Ｇ４以及Ｃ＝ ｆｌ＊（ ｆ；ｉＴ”ｒ１４． ＞Ｔ３＝ｒａｎｄｎ（ｎ，是＋ ｓ）５． ｙ＝［ ］６． Ｗ＝ｚｅｒｏｓ（ｎ＾ ＋ ５）７． ＦＯＲｆ＝１，２，． ． ．，ｎ／ｒ？ＤＯ８． Ｆ｝ ＝Ｆ＼＾ｉｖ ｕ＋ｌ：ｉｖｊ：］９． Ｍ， ｆｉ＝ｔｒｕｎｃ ｌｏｇ°（Ｖ〇｜＾Ｇ）Ｆ， ＣＦＴ）１０．ｙ＝Ｍ， ｎ， Ｙ＝［Ｙ；ｙ＾１１．ＥＮＤＦＯＲ１２． 执行算法５ 的第８？１ ５ 步１３．Ｅ＝ＵＳｍ算法６ 的第１ 步使用算法３ 实现， 对中小规模网络《可以取１ ／２ ， 对于大规模网络可以通过试验得到更合适的取值， 从而提高运行效率、减少近似误差． 第２？１２ 步实现了矩阵Ｍ和Ｍ的隐式构造， 并对Ｍ的行进行批处理的单遍访问， 为后续计算截断ＳＶＤ做准备． 这里， 为了算法描述简洁、 且不失一般性， 只考虑了〃能被ｎ整除的情况．下面分析算法６ 的计算量和空间开销， 设／＝々＋二第１ 步的时间复杂度为ＯＣ ｗｗｚＵＨ＋Ｍ２） ， 空间复杂度均为０（ ｗｗｚＵ） ＋舫） ？ 算法６ 的第２、３ 步包含ｏｃ ｎｐ） 次浮点运算， 第７？１２ 步包含ｏｃｖａ＋ｚ） ）次浮点运算， 第１３、１４ 步的浮点运算次数为０（ ｎＺ２＋Ｚ３） ． 由于《远大于其它参数的值， 算法６ 总的计算复杂度为〇（？２ａ＋／） ） ． 在空间开销方面， 第１ 步需要的存储量是〇（ ｗｗｚ（Ａ）＋Ｍ） ， 在后续计算步骤中，需要存储的矩阵尺寸都不超过ｗＸ／＾ｗＸＺ 或ｗＸｗ，考虑到矩阵Ａ在后续不再使用， 算法６ 的空间复杂度为０（ｗ（／ｉ＋ Ｚ＋ｗ） ）．可以看出， ｅＮｅｔＭＦ算法在空间复杂度方面大大优于ＮｅｔＭＦ算法． ＮｅｔＳＭＦ算法［８］的空间复杂度为０（叫．期２〇４） ） ， 其中￡：一般取值１０００ 或者１００００ ，因此我们的ｅＮｅｔＭＦ算法在内存用量方面也显著小于ＮｅｔＳＭＦ算法的内存用量． 由于ｅＮｅｔＭＦ的时间复杂度仍为〇（？２ａ＋／） ） ， 它处理特别大的网络时会花费过多的计算时间， 将来可以考虑采用分布式并行计算等方式来加以改进．５ 实 验本文算法均使用ｃ语言编程实现， 其中用到的矩阵计算和ＱＲ分解、ＬＵ分解、ＳＶＤ分解等算法通过调用ＩｎｔｅｌＭＫＬ的库函数进行实现， 同时采用ＯｐｅｎＭＰ编程实现了多线程计算． 所有实验均运行于装有３２核Ｉｎｔｅｌ（ Ｒ）Ｘｅｏｎ（Ｒ）ＣＰＵ、２５６ＧＢ内存的Ｌｍｕｘ工作站上， 实验结果中的时间均为３２ 线程并行计算的实测运行时间．下面我们首先介绍测试的网络数据， 然后验证第４．２ 节提出的特征值分解算法ｆｒｅｉｇｓ 的准确度与有效性， 最后通过多标签分类的实验验证ｅＮｅｔＭＦ算法的优势， 并给出更多实验结果．５． １ 数据集我们选择如下５ 个网络数据集来进行测试．（ １） ＰＰＩ［ ２ ９］． 该数据集是一个蛋白质和蛋白质交互的网络子图， 数据集里节点的标签是从标志性基因集获取的， 可以表示生物学状态．（ ２）Ｂｌ 〇ｇＣａｔａｌ 〇ｇ［ ３°］． 该数据集是一个线上博客主的社交关系的网络， 其中节点标签表示博客主的兴趣．（ ３） ＤＢＬＰ［３ １］． 该数据集是一个学术引用网络，网络中的节点是作者， 标签是他们所活跃的会议．（ ４）Ｆｌ １ Ｃｋｒ［ ３ °］． 该数据集是一个ＦＨｃｋｒ 网站上的谢雨洋等： 基于随机化矩阵分解的网络嵌人方法 ４５ ５图２５． ３ｅＮｅｔＭＦ算法在多凇５． ３．１ 实验参数设置与评价指标我们将本文提出的ｅＮｅｔＭＦ网络嵌入方法与ＤｅｅｐＷａｌｋ、ＮｅｔＭＦ、ＮｅｔＳＭＦ、 ＰｒｏＮＥ四种方法进行对中给出的程序． 根据文献［７］， 对于所有的方法在不额外说明的情况下都默认设置成窗口大小ｇ＝１０、负采样参数 １ 以及嵌入映射维度 １２８． 在２００１００ ２００ １００ ２００Ｆｌｉｃｋｒ２００ ４００ＹｏｕＴｕｂｅ６５遄４－－ｅｉｇｓ■■ ■■■ ｆｒｅｉｇｓ嵙３＃２、？１０ １００ ２００算塗软 Ｕｇｓｔ函魏对归一化Ｍ翁雉阵酸＿鑛斷特征偉聲觳＿绪暴ｆ、签分类问题上的效果比》 对比的程序是这四种方法的作者在文献Ｃｌ Ｊ邛］－－ｅｉｇｓ■■ …ｆｒｅｉｇｓ３ 期用戸黑相联系的网络， 标签代表了用．户的兴趣组．（ ５）ＹｏｕＴｕｂｅ？． 读数据梟是一个视频分享网姑上的用户玄互网络， 用户的标签为他们喜致的视频的类型．其中＊ＰＰＩ 和ＢｂｇＣａｔａｌ ｏｇ规模相对较／Ｍ旦是在网络嵌入方面的研究工作中被广泛使用＊ 而ＤＢＬＰ、Ｆｌ ｉｃｋｒ 和Ｙｏｕｆｕｂｅ的：规儀相对较： 大．这巻载摒集的一些具体倩息如表１ 所示？表１ 数据集的具体信息数据集名称 点个数 边个数 标签个数ＰＰＩ３８９０ ７６ ５８４ ５０ＢｌｏｇＣａｔａｌ ｏｇ１０３１２ ３３３９８３ ３９ＤＢＬＰ ５ １２６４ １２７９６８ ６０Ｆｌｉ ｃｋｒ ８０５１３ ５ ８９９８８２ １９５ＹｏｕＴｕｂｅ １ １３８ ４９９２９ ９０４４３ ４７５．２ 特征值分解算法ｆｒｅｉｇｓ 的有效性计算截断奇异值分解的传统算法是ＡＲＰＡＣＫ算法Ｐ３］， Ｐｙｔ： ｈ＿麗：＆ｃｉｐｆ 贈ｅｉｇｓ、 ｅｉｇｓｈ涵敎慕基：于它ｔ且使用Ｉｎｔｅｌ 的ＭＫＬ实规的， 下面将我们的算法３（ 即ｆｍｇｓ）与处理对称稀：疏矩阵的ｒｉｇｓｌｉ函数做比较， 后者也就是Ｎｅ＇ｔＭｉ＊８中所使用的．测试的矩阵是由表１中＾个数据梟鲁到的矩阵，除了对ＤＢＬＰ 和ＹｍｉＴｔＡｅ 我们分别睫ｃ？＝ｄ．ｒ邦 ｄ． 玆５ 外， 对其它：数摒囊我们都设ａ值ＰＰＩ为缺省的〇．＿？！齿了与后？面的网络嵌人实验保持一致， 对ＰＰＩ、Ｂｌｃ＾Ｃｓｔｓｌ 〇ｆ、ＤｍｆｎＹ轉 这４个数据集４寺征值截断参数６＝２５６， 对Ｆｌｉ ｃｋｒ 我们取々＝５１２． 对于華迭代参数和过采祥参数餘了ＤＢＬＰ、Ｆｌｉｃｋｒ 外都取多＝ＩＱ？ｓ＝５： ６．Ｆｌ ｉｃ． ｋｆ 对应：餘＿障载稠密、 且特征植． 截断参数较大， 我们取ｆ＝８ｙ＝１０（ＶＤＢＬＰ对应的蔚一化网络矩阵特征值下降缓慢， 我们取ｆ＝１６ｙ＝２５６． 我们的算法３（ ｆｒｅｉｇｓ箅法）与ｅｉｇｓｈ的运行时间列于表２中． ． 从中可看出，随机化特征值分解算法在： 大数据．集上比传统算法快接近１０ 倍．表２算法３（ｆｒｅｉｇｓ） 与ｅｉ获ｈ 的运行时间比较 （单位： ５）数据集名称 ｅｉｇｓｈ ｆｒｅｉｇｓ 加速比ＰＰＩ ３． ０ ０．７ ４．３ＸＢｌｏｇＣａｔａｌｏｇ１１． ０１． ９５．８ＸＤＢＬＰ ８１． ０ ９． ０ ９． ＯＸＦｌｉｃｋｒ ４１５． ０７９． ０５．３ＸＹｏｕＴｕｂｅ １３２０．０ １３８．０ ９．６Ｘ图２ 显示了算法３ 和ｅｉｇｓｈ 计算出的最大特征值曲线？ 从中可以着：出， 两＇者的结果几乎是不可区分的， 这反映出随机化待征値算法ｆｒｅｉｇｓ有较圩的准确度？通过铃＿多标：盤分类问题上的实验结果， 我们也可以看出ｆｒｅｉｇｓ算法每到的截断特征值分解几乎不会影响网络嵌人的性能．ＤＢＬＰ ＢｌｏｇＣａｔａｌｏｇｆｆｔ＾．３．３．．０． ８ｊ．４ｌ．ｏ．ｏ．ｏ．４５６ 计 算机 学 报 ２０２１年ＮｅｔＭＦ和ｅＮｅｔＭＦ算法中， 对归一化网络矩阵作截断特征值分解的参数／ｉ 基本上都取值２５６， 只是对Ｆｌｉｃｋｒ令５１２．对于ＤｅｅｐＷａｌ ｋ算法， 我们按照文献［３］的作者建议的参数进行设置， 即随机游走的长度取４０ ， 每一个点的游走数量取８０ 以及窗口大小的参数取１０．对于ＮｅｔＳＭＦ算法， 需要设置网络稀疏化的非零元参数Ｍ． 我们和文献［８］保持一致， Ｍ的值几乎都是１０３Ｘ ｇＸｗｗｚ（Ａ） ／２， 只有对Ｂｌ ｏｇＣａｔａｌ ｏｇ， Ｍ＝１０４Ｘ，ｑＸ， ｎｎｚ（Ａ）／２．对于ＰｒｏＮＥ算法， 我们和文献［９］设置相同的参数， 即切比雪夫扩展次数为１０， 拉普拉斯算子里的＂＝０．２，６＝０．５．对于ｅＮｅｔＭＦ方法， 除了在５．２ 节已经介绍的．？参数和进行第一步快速随机化特征值分解所需要的幂迭代参数、过采样参数外， 还需要设置逐行遍历矩阵Ｍ的批处理参数Ｗ和最后单遍历奇异值分解中使用的过采样参数＾批处理参数ｎ影响内存开销和矩阵乘法的计算时间， 较大的？会使得矩阵乘法加快， 但也导致峰值内存用量较大． 我们对大多测例使用ｗ＝３２００ ， 而对于最大的ＹｏｕＴｕｂｅ 设置ｗ＝１２８００． 对最后的过采样参数， 统一取５＝１００．在上述各种方法得到网络嵌人后， 与文献［３，７９］一样我们将其应用到多标签分类问题上， 通过分类的准确性来评价不同网络嵌人表示的性能． 对各个数据集， 我们随机采样一部分的带标签节点作为训练数据， 剩下的作为测试数据＿ 对于ＰＰＩ 和Ｂｌ ｏｇＣａｔａｌ ｏｇ，训练节点所占比例从１０ ％起每次增加１０ ％递增到９０％， 总共进行９ 组节点分类的实验． 对于ＤＢＬＰ、Ｆｌｉｃｋｒ 和ＹｏｕＴｕｂｅ， 训练节点所占比例从１％起逐渐增到１０％， 共进行１０ 组节点分类的实验． 在实验中， 我们使用由ＬＩＢＬＩＮＥＡＲ［３ ２］库实现的一对多的逻辑回归模型进行多标签分类． 在测试阶段， 逻辑回归模型生成排序的标签、而不是确切的标签分配， 为了避免阈值效应， 我们假定对于测试数据， 标签的数量是给定的［ ３’３３ ］． 对于每个实验， 我们重复预测１０ 次，然后观测不同网络嵌人方法得出的平均Ｍｌ ｃｒ〇 ＿Ｆｌ、平均ＭａｃｒｏＦＩ 指标［３ ４］和准确率指标［３ ５］． ＿Ｆ１ 分数指标的定义为Ｆ１２ＰＲＰ＋Ｒ（１８）其中Ｐ表示精确率，ｉ？ 表示召回率． 计算Ｍｉｃｒｏ ＦＩ时， 先将所有类别的真正例数量（ ＴＰ）、假正例数量（ＰＴ） 和假负例数量（ＦＮ） 相加得到总体的ＴＦ、ＴＷ、值以及总体精确率Ｐ和召回率犮．ＴＰ二￣ＴＰｅｌａｓ；ｓ ｌ￣￣Ｉ－ＴＰｄａ ｓｓ２ ￣￣Ｉ－．＋ＴＰｃｌａｓ ｓ」 ｖ（ １９）ＦＰ：二ＦＰｃｈｓ； ｓ ｌ￣￣Ｉ－ＦＰｄａｓ ｓ２￣￣Ｉ－？ ？ ？ＦＰｃｌ ａｓ ｓＪ＂ｖ（２０）￥ｎ二二ＦＮ如；ｓｉ＋ＦＮｃ＼＆＾２＋＊ ？ ？＋ＦＮｃｌａ ｓｓｗ（２１）ｔｐＰ＝＝￣＝（２２）ＴＰ＋ＦＰ－ｆｐＲ＝＿＿（２３）ＴＰ＋ＦＮ然后， 类似式（Ｉ８） 计算Ｍｉｃｒｏ ＦＩ：Ｍｉ ｃｒｏ ＦＩ２ＰＲＰ＋Ｒ（２４）计算Ｍａｃｒｏ ＦＩ 时， 则是分别计算每个类别的Ｆ１ 分数， 然后求平均：Ｍａｃｒｏ ＦＩ＝ＦＩｃｌａｓ ｓｌ￣￣ｔ－？ ？ ？￣￣ｔ－Ｆｌｃｌａｓｓ ＮＮ（２５）在计算多标签分类的准确率时， 我们先计算一个节点的多标签准确率为预测正确的标签除以总共的标签数量， 然后取整体的分类准确率为所有节点的平均：ＡｃｃＭｒａｃ＾＝（２６）ｎｔｉ｜ ｉ，Ｕ＞ ５．Ｉ其中Ｔ， 表示正确的标签集， Ｓ， 表示预测的标签集．５．３．２ 实验结果图３ 和图４ 显示了不同网络嵌人算法在５ 个数据集上进行多标签节点分类的性能．其中， 由于所需内存超出了２５６ＧＢ， Ｎｅｔ ＳＭＦ对Ｆｌ ｉ ｃｋｒ和ＹｏｕＴｕｂｅ的实验结果无法获得， 而由于同样的原因ＮｅｔＭＦ对ＹｏｕＴｕｂｅ 的结果也无法获得． 从图３ 和图４ 可以看出， 无论是Ｍａｃｒ〇＿Ｆｌ还是Ｍｉ ｃｒｏ ＿Ｆ１， 使用ｅＮｅｔＭＦ算法后的结果都与使用ＮｅｔＭＦ得到的一致（尤其在训练比例较大时） ， 这说明本文提出的改进ＮｅｔＭＦ算法的技术并没有给网络嵌人的质量带来明显的影响． ＤｅｅｐＷａｌ ｋ方法在ＰＰＩ、Ｂｌ ｏｇＣａｔａｌ ｏｇ、ＤＢＬＰ和ＹｏｕＴｕｂｅ 上有和ｅＮｅｔＭＦ差不多甚至更差的效果，仅在ＦＵｃｋｒ上要好于我们的方法． ＰｒｏＮＥ方法虽然在某些数据上得到的Ｍｌ ｃｒ〇Ｆｌ 值最好， 但在所有测试数据上其得到的Ｍａｃｒｏ ＦＩ 值明显比其它方法的差， 这说明ＰｒｏＮＥ得到的嵌人表达没有包含图中足够的信息， 因此对一些标签较少的节点分类效果不够好．网络嵌人算法在多标签分类问题上的准确率结果列于表３ 中． 我们记录当训练节点所占比例为６０％时的ＰＰＩ 和Ｂｌ ｏｇＣａｔａｌ ｏｇ 的准确率结果， 以及当训练节点所占比例为６％时的ＤＢＬＰ、 ＦＵｃｋｒ 和ＹｏｕＴｕｂｅ 的准确率结果． 从表３ 的结果可以看出， 我们的方法和ＮｅｔＭＦ的效果差不多， 在所有数据集上与其它对比对象比较均有差不多或者更好的准确率．谢雨洋等： 基于随机化矩阵分解的网络嵌人方法 ４５ ７ ３ 期训练比例／％Ｆｌ ｉｃｋｒ ＹｏｕＴｕｂｅ图３ 使用不同网络嵌人算法后进行节点多标签分类得到的Ｍａｒｃｏ－Ｆｌ 值（横轴为训练数据所占的比例）ＰＰＩ ＢｌｏｅＣａｔａｌｏｅ＾－ＤｅｅｐＷａｌｋ－？－ＮｅｔＭＦ备ＮｅｔＳＭＦ＋ＰｒｏＮＥ￣ｔ—ｅＮｅｔＭＦ２０ ４０６０训练比例／％８０３０Ｌ２０ＤｅｅｐＷａｌｋ夺ＮｅｔＭＦＮｅｔＳＭＦ＾ＰｒｏＮＥｅＮｅｔＭＦ４０６０８０训练比例／％ＤＢＬＰ４０Ｙｏｕｔｕｂｅ＾ＤｅｅｐＷａｌｋ－？－ＮｅｔＭＦ各ＮｅｔＳＭＦ斗ＰｒｏＮＥ十ｅＮｅｔＭＦ４训练比例／％１０－＾ＤｅｅｐＷａｌｋ－？－ＮｅｔＭＦ各ＮｅｔＳＭＦ＋ＰｒｏＮＥ￣ｉ—ｅＮｅｔＭＦ４６训练比例／％１０训练比例Ａ庫． 傳兩不■ 翬儀Ａ＃■翁嫌行节属＿签＃： ＿飼的ＭｔｅｉＦｌ疸１猜轴为刺馨敷．腐古鋒比例）表３各种网络嵌入算法的多标签分类准确率（筚偉数据集名称 ＤｅｅｐＷａｌｋ ＮｅｔＭＦ ＮｅｔＳＭＦ ＰｒｏＮＥ ｅＮｅｔＭＦＰＰＩ１７． ０８２ １８． ０２０１８．６２１ １８． ９８５ １８．１４８ＢｌｏｇＣａｔａｌｏｇ４０．１４３４１．１ １８３９．３６１３９． ５２９ ４０．９５８ＤＢＬＰ ５８．２８０ ５９．９ １９ ５９．２８７ ５５．５２７ ５８．３５２Ｆｌｉ ｃｋｒ３４．３５ １３３．１７３ Ｎ． Ａ．３３．４８５３３．０８０ＹｏｕＴｕｂｅ ９８．２４７ Ｎ． Ａ． Ｎ． Ａ． ９８． ２８９ ９８．２５６各种网络嵌人算法的运＃时间列于表４ 中， 所有算法对应的程序都是适含ｆｌ３２ 线程运行的并行程序？且对间包括了读取数据文件的时间？ 从表．４可以看出，ＰｒｏＫＥ算：法的运行时间最親ｄＮｅｔＭＦ算法在矩阵规模不大的时候， 速度也比较快． 在Ｆｌｉｃｋｒ 数摈上其相对于ＮｅｔＭＦ 的加速比高达４１ 倍． 而ＭｅｆｌＳｌｖＩＦＳ： 然在； 处理ＤＢＬＰ时也比ＮｅｔＭＦ耗时■？钽在处理更大例子时由于内存蕾求太大而无法运行． Ｄｅ仲Ｗａｌ ｋ算法是所有对比对象里运行时间最夂的，ｅｓＭｅＢｖＩＦ算驗相对＂于Ｄ？ｐＷ？ｉｌｋ 算法翁每个数磨集上的加速比都要超过２〇倚．表４ 各种网络嵌入算法的运行时间 （筚偉，．ｓ）＇数据：集舊猶ＤｅｅｐＷｆｔ？Ｎｅｔ？ｔＮ８Ｉ獅ＰＪｆｌｊＮＥ．ｅＮｅ爾ｆ 加速比ＰＰＩ３１８ １４ １９ １．４ １．５ ９．３ＸＢｌｏｇＣａｔａｌｏｇ８１６ ８４ １１４０ ５．０ ４．６ １８．ＯＸＤＢＬＰ ４５４０ ６３２ ８２ １１． ０３９． ０ １６． ＯＸＦｌｉｃｋｒ ７９２０６１２０ Ｎ．Ａ．７２．７ １５０ ． ０４１． ＯＸＹｏｕＴｕｂｅ １０８０１５ Ｎ． Ａ． Ｎ． Ａ．１９４．３ ４８５２． ０—４５８ 计 算机 学 报 ２０２１年对于ＮｅｔＭＦ、ＮｅｔＳＭＦ、ＰｒｏＮＥ和ｅＮｅｔＭＦ这四种算法的峰值内存用量列于表５． 从中可以看出，对Ｆｌ ｉ ｃｋｒ 数据ｅＮｅｔＭＦ的内存用量仅为ＮｅｔＭＦ的１／４６． 处理最大的ＹｏｕＴｕｂｅ 数据，ｅＮｅｔＭＦ 只需１２０ ＧＢ内存即可算出网络嵌人， 并得到非常好的网络节点分类结果（ 如图３、 图４）． 虽然在运行时间和内存用量上， 本文的方法不如ＰｒｏＮＥ， 但是如前面所展示的， 本文方法在多标签分类结果的效果上更稳定、更好．表５ 各种网络嵌入算法的峰值内存用量（单位： ＧＢ）数据集名称Ｎｅｔ ＭＦＮｅｔＳＭＦＰｒｏＮＥｅＮｅｔ ＭＦ 缩小倍数ＰＰＩ０． ３９６． ８６０． １６０． ２９１． ３ＸＢｌｏｇＣａｔａｌｏｇ２． ２０１３５． ０００． ４６０． ５５４． ＯＸＤＢＬＰ３１． ００１８． ２００． ７２２． ００１６． ＯＸＦｌｉｃｋｒ１８２． ００＞２５６５． ５０４． ００４６． ＯＸＹｏｕＴｕｂｅ＞２５ ６＞２５ ６１２． ００１２０． ００对ｅＮｅｔＭＦ算法各部分的运行时间进行详细统计后发现， 第一步随机化特征值分解和最后的单遍历奇异值分解所花费时间占比例很小， 而两者之间的矩阵计算部分（算法６ 的第７？１２ 步） 消耗时间最多． 例如， 对ＹｏｕＴｕｂｅ 数据， 矩阵计算部分花费的时间为４５７４ ｓ， 占总运行时间９０％以上， 而单遍历奇异值分解的时间仅为３５ｓ． 对于该数据， 我们还比较了算法６ 中的单遍历奇异值分解与文献［２７］ 中的单遍历奇异值分解算法， 后者的运行时间为１４３４ｓ， 可见我们提出的简洁单遍历算法与保证分解结果对称的技术显著加速了计算、也有很高的准确度．５．４ｅＮｅｔＭＦ算法在边预测问题上的效果５． ４．１ 实验设置与评价指标我们将本文提出的ｅＮｅｔＭＦ 网络嵌人算法和ＤｅｅｐＷａｌ ｋ、ＮｅｔＭＦ、ＮｅｔＳＭＦ、 ＰｒｏＮＥ在网络的边预测问题上进行比较， 这些方法的参数设置和５．３ 节所介绍的一致． 边预测问题旨在基于现有的网络结构来预测可能存在的边． 在我们的实验当中， 我们随机地抽取原始图３０％的边作为测试集， 剩余７０ ％的边作为训练集． 首先将不同的算法在训练集上进行学习得到训练集的网络嵌人结果， 然后根据网络嵌人结果来计算每一个在测试集的点对（Ｍ， Ｗ） 上的相似度分数， 最后采用广泛使用的ＡＵＣ指标［ ５ ］来评价边预测质量的好坏． 在上述过程中， 计算点对（Ｍ， Ｗ的相似度分数可以按照点对Ｕ， Ｗ对应的嵌人向量的内积、余弦距离或欧式距离来计算， 也可以使用边特征方法［ ５ ］来计算． 对于每个网络嵌人算法，我们选取使其ＡＵＣ指标结果最好的相似度分数计算方法并记录ＡＵＣ的结果．５．４．２ 实验结果各种网络嵌人算法在边预测问题上的ＡＵＣ指标的结果列于表６ 中． 从表６ 可以看出在ＰＰＩ 和Ｆｌｉｃｋｒ数据集上ｅＮｅｔＭＦ算法比ＤｅｅｐＷａｌ ｋ、ＰｒｏＮＥ要差， 但在数据集Ｂｌ ｏｇＣａｔａｌ ｏｇ、ＤＢＬＰ和ＹｏｕＴｕｂｅ上， ｅＮｅｔＭＦ算法的结果比其它方法好或差不多． 整体来看， ｅＮｅｔＭＦ的效果和ＮｅｔＭＦ的效果相比差不多甚至更好， 特别是在ＤＢＬＰ数据集上， ｅＮｅｔＭＦ算法显著更好， 这是因为ＤＢＬＰ的归一化网络矩阵的特征值衰减非常缓慢， ＮｅｔＭＦ算法里的ｅｌｇｓｈ函数在不设置迭代次数的时候很难收敛， 而设置了迭代次数的特征值计算的结果有一定的误差， 故该数据集的结果也验证了本文第４．３ 节提出的矩阵高效率构建方法的有效性． 边预测实验验证了ｅＮｅｔＭＦ算法具有很好的推断预测的能力， 这得益于我们的模型和ＮｅｔＭＦ—样， 较好地保存了网络的结构信息．表６ 各种网络嵌入算法在边预测问题上的ＡＵＣ值数据集名称ＤｅｅｐＷａｌ ｋＮｅｔ ＭＦＮｅｔＳＭＦＰｒｏＮＥｅＮｅｔ ＭＦＰＰＩ０． ７４３０． ７３７０． ７６４０． ７９７０． ７３５ＢｌｏｇＣａｔａｌｏｇ０． ８８００． ８７８０． ８８３０． ８８６０． ８７６ＤＢＬＰ０． ８４８０． ８５７０． ８４８０． ８４５０．９１６Ｆｌｉｃｋｒ０． ９２３０． ８７９Ｎ．Ａ． ０． ９２６０． ８７１ＹｏｕＴｕｂｅ０． ７７９Ｎ．Ａ． Ｎ．Ａ． ０． ８０５０． ８０５６ 结论与展望本文在网络嵌人问题上， 提出了一个基于高效随机化矩阵分解的网络嵌人方法， 该方法显著减少了ＮｅｔＭＦ［７］模型的内存开销和运行时间． 本文首先提出了一种快速随机化特征值分解算法， 用以加速归一化网络矩阵求特征值分解的速度， 该算法展现出相比传统的稀疏矩阵截断特征值分解方法近十倍的加速， 且几乎不损失精度． 然后提出了一种简洁的且适用于对称矩阵的单遍历奇异值分解算法， 利用该算法避免了显式存储稠密矩阵， 使得算法的内存开销跟矩阵维度呈线性关系， 适合于处理大规模网络数据． 最后， 结合以上技术， 提出了基于高效随机化矩阵分解的网络嵌人算法ｅＮｅｔＭＦ， 并将其应用于实际网络数据， 基于得到的低维嵌人进行多标签分类和边预测． 多标签分类的实验结果表明，ｅＮｅｔＭＦ在各个数据集上的评测结果均与ＮｅｔＭＦ得到的结果差不多， 显著优于ＮｅｔＳＭＦ和ＰｒｏＮＥ等其它网络嵌人方法， 而且ｅＮｅｔＭＦ方法内存用量小、谢雨洋等： 基于随机化矩阵分解的网络嵌人方法 ４５ ９３ 期运行速度快． 对于节点数超过１ 百万、ＮｅｔＭＦ 与ＮｅｔＳＭＦ由于内存需求太大无法处理的ＹｏｕＴｕｂｅ数据， ｅＮｅｔＭＦ只需１．３ ｈ 和１２０ ＧＢ 内存开销即可得到网络嵌人， 并进而获得很好的多标签分类结果．边预测的实验结果表明ｅＮｅｔＭＦ算法也表现出与其它方法差不多甚至更好的性能．本文提出的方法， 虽然在运行时间上相比ＮｅｔＭＦ有显著的优势， 但其时间复杂度仍为〇ｃｖａ＋／） ） ，其中《为网络节点数目． 因此， 在它在处理特别大的网络时需要很长、 甚至不能忍受的时间． 后续我们将考虑用ＧＰＵ并行计算或分布式计算对改算法进行加速， 使得它在保证准确的同时能够处理更大规模的网络数据． 其次， 本文通过随机化矩阵计算方法改进ＮｅｔＭＦ方法， 取得了一定的效果， 后续还可以研究随机化矩阵方法在其它大数据挖掘和处理问题上的应用， 期望在保证结果准确的同时减少算法的时间和内存开销． 此外， 对于本文实验中体现出的ＰｒｏＮＥ算法得到的网络嵌人结果不稳定的问题， 很可能是由于ＰｒｏＮＥ算法做了近似的信息传播增强， 导致在一些稀疏图数据上的表现较差． 这种信息传播过多导致的过度平滑问题最近也得到学术界的关注， 将来我们也计划针对该问题开展工作， 希望研究出既保证网络嵌人质量又具有非常低算法复杂度的网络嵌人方法．参 考 文 献［１］ＺｈａｎｇＦ，ＬｉｕＸ， ＴａｎｇＪ， ｅｔ ａｌ ． ＯＡＧ； Ｔｏｗａｒｄｌｉｎｋｉ ｎｇｌａｒｇｅｓｃａｌｅｈｅｔｅｒｏｇｅｎｅｏｕｓｅｎｔｉｔｙｇｒａｐｈｓ／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆ ｔ ｈｅ２５ｔｈＡＣＭＳＩＧＫＤＤＩｎｔｅｒｎａｔ ｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙａｎｄＤａｔａＭｉｎｉｎｇ（ ＫＤＤ） ． Ａｎｃｈｏｒａｇｅ， ＵＳＡ，２０１ ９；２５８５ ２５９５［２］Ｈａｍｉｌｔｏｎ ＷＬ？ＹｉｎｇＲ，ＬｅｓｋｏｖｅｃＪ． Ｒｅｐｒｅｓｅｎｔ ａｔ ｉｏｎ ｌｅａｒｎｉ ｎｇｏｎｇｒａｐｈｓ： Ｍｅｔｈｏｄｓａｎｄａｐｐｌｉｃａｔ ｉｏｎｓ． ＩＥＥＥＤａｔａ（ ｂａｓｅ）ＥｎｇｉｎｅｅｒｉｎｇＢｕｌ ｌｅｔ ｉｎ，２０１７ ，４０ ：５２ ７４［３］ＰｅｒｏｚｚｉＢ？Ａｌ ＲｆｏｕＲ？ＳｋｉｅｎａＳ． Ｄｅｅｐｗａｌｋ： Ｏｎｌｉ ｎｅｌｅａｒｎｉ ｎｇｏｆｓｏｃｉａｌｒｅｐｒｅｓｅｎｔ ａｔｉｏｎｓ／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ２０ｔｈＡＣＭＳＩＧＫＤＤＩｎｔ ｅｒｎａｔ ｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙａｎｄＤａｔａＭｉｎｉｎｇ． ＮｅｗＹｏｒｋ， ＵＳＡ， ２０１４ ：７０１ ７ １０［４］ＴａｎｇＪ， ＱｕＭ， ＷａｎｇＭ， ｅｔａｌ． Ｌｉｎｅ： Ｌａｒｇｅｓｃａｌｅｉｎｆ ｏｒｍａｔｉｏｎｎｅｔｗｏｒｋｅｍｂｅｄｄｉｎｇ／／Ｐｒｏｃｅｅｄｉ ｎｇｓｏｆｔｈｅ２４ｔｈＩｎｔ ｅｒｎａｔ ｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＷｏｒｌｄＷｉｄｅＷｅｂ． Ｆｌｏｒｅｎｃｅ？ Ｉｔ ａｌｙ，２０１５：１０６７ １０ ７７［５］ＧｒｏｖｅｒＡ，ＬｅｓｋｏｖｅｃＪ． Ｎｏｄｅ２ｖｅｃ： Ｓｃａｌａｂｌｅｆｅａｔ ｕｒｅｌｅａｒｎｉ ｎｇｆｏｒｎｅｔ ｗｏｒｋｓ／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆ ｔｈｅ２２ｎｄＡＣＭＳＩＧＫＤＤＩｎｔ ｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙａｎｄＤａｔ ａ［６］ＤｏｎｇＹ， ＣｈａｗｌａＮＶ， ＳｗａｍｉＡ． Ｍｅｔ ａｐａｔｈ２ｖｅｃ： Ｓｃａｌａｂｌｅｒｅｐｒｅｓｅｎｔａｔｉｏｎｌｅａｒｎｉｎｇｆｏｒｈｅｔ ｅｒｏｇｅｎｅｏｕｓｎｅｔ ｗｏｒｋｓ／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ２３ｒｄＡＣＭＳＩＧＫＤＤＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙａｎｄＤａｔａＭｉｎｉｎｇ． Ｈａｌ ｉｆａｘ，Ｃａｎａｄａ，２０ １７： １３５ １４４［７］ＱｉｕＪ ， ＤｏｎｇＹ， ＭａＩ Ｉ ， ｅｔａｌ． Ｎｅｔｗｏｒｋｅｍｂｅｄｄｉ ｎｇａｓｍａｔ ｒｉｘｆａｃｔｏｒｉｚａｔｉｏｎ： Ｕｎｉｆｙｉｎｇｄｅｅｐｗａｌｋ，ｌｉｎｅ ，ｐｔｅ ，ａｎｄｎｏｄｅ２ｖｅｃ／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ１１ｔｈＡＣＭＩｎｔ ｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＷｅｂＳｅａｒｃｈａｎｄＤａｔ ａＭｉ ｎｉｎｇ． ＭａｉｎａＤｅｌＲｅｙ，ＵＳＡ，２０１８；４５９４６７［８］ＱｉｕＪ ， ＤｏｎｇＹ， ＭａＩ Ｉ，ｅｔａｌ ． ＮｅｔＳＭＦ： Ｌａｒｇｅｓｃａｌｅ ｎｅｔ ｗｏｒｋｅｍｂｅｄｄｉｎｇａｓｓｐａｒｓｅｍａｔ ｒｉｘｆａｃｔｏｒｉｚａｔ ｉｏｎ／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ２８ｔ ｈＩｎｔ ｅｒｎａｔ ｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＷｏｒｌｄＷｉｄｅＷｅｂ． ＳａｎＦｒａｎｃｉｓｃｏ， ＵＳＡ， ２０１９： １５０ ９ １５２０［９］ＺｈａｎｇＪ，ＤｏｎｇＹ，ＷａｎｇＹ， ｅｔａｌ． ＰｒｏＮＥ： Ｆａｓｔ ａｎｄｓｃａｌａｂｌｅｎｅｔ ｗｏｒｋｒｅｐｒｅｓｅｎｔ ａｔｉｏｎｌｅａｒｎｉｎｇ／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔ ｈｅ２８ｔ ｈＩｎｔｅｒｎａｔ ｉｏｎａｌＪｏｉｎｔＣｏｎｆ ｅｒｅｎｃｅｏｎＡｒｔ ｉｆ ｉｃｉａｌＩｎｔ ｅｌ ｌｉｇｅｎｃｅ．Ｍａｃａｏ ，Ｃｈｉｎａ，２０ １９； ４２７８ ４ ２８４［１０］Ｉ ｌ ａｌｋｏＮ， Ｍａｒｔ ｉｎｓｓｏｎＰＧ， ＴｒｏｐｐＪＡ． Ｆｉｎｄｉｎｇｓｔ ｒｕｃｔｕｒｅｗｉｔｈｒａｎｄｏｍｎｅｓｓ： Ｐｒｏｂａｂｉｌｉｓｔｉｃａｌｇｏｒｉｔｈｍｓｆ ｏｒｃｏｎｓｔ ｒｕｃｔ ｉｎｇａｐｐｒｏｘｉｍａｔ ｅｍａｔ ｒｉｘｄｅｃｏｍｐｏｓｉｔｉｏｎｓ． ＳｏｃｉｅｔｙｆｏｒＩｎｄｕｓｔｒｉ ａｌａｎｄＡｐｐｌｉｅｄＭａｔ ｈｅｍａｔｉ ｃｓＲｅｖｉ ｅｗ， ２０ １１， ５３ （ ２） ： ２１７ ２８８［１１］ＤｒｉｎｅａｓＰ，ＭａｈｏｎｅｙＭＷ． ＲａｎｄＮＬＡ： Ｒａｎｄｏｍｉｚｅｄｎｕｍｅｒｉｃａｌｌｉｎｅａｒａｌｇｅｂｒａ． Ｃｏｍｍｕｎｉｃａｔ ｉｏｎｓｏｆｔｈｅＡＣＭ， ２０１ ６，５９（６）：８０ ９０［１２］ＭｉｋｏｌｏｖＴ， ＳｕｔｓｋｅｖｅｒＩ ， ＣｈｅｎＫ， ｅｔ ａｌ． Ｄｉｓｔ ｒｉｂｕｔ ｅｄｒｅｐｒｅｓｅｎｔａｔ ｉｏｎｓｏｆｗｏｒｄｓａｎｄｐｈｒａｓｅｓａｎｄｔ ｈｅｉｒｃｏｍｐｏｓｉｔｉ ｏｎａｌｉ ｔｙ／／ＡｄｖａｎｃｅｓｉｎＮｅｕｒａｌＩｎｆｏｒｍａｔｉｏｎＰｒｏｃｅｓｓｉｎｇＳｙｓｔ ｅｍｓ． ＬａｋｅＴａｈｏｅ， ＵＳＡ， ２０１３： ３１１１ ３１１９［１３］ＣｈｕｎｇＦＲＫ？ ＧｒａｈａｍＦＣ． Ｓｐｅｃｔ ｒａｌｇｒａｐｈｔ ｈｅｏｒｙ． Ｐｒｏｖｉｄｅｎｃｅ ？ＲｈｏｄｅＩｓｌａｎｄ： ＡｍｅｒｉｃａｎＭａｔｈｅｍａｔ ｉｃａｌＳｏｃｉｅｔｙ？１９９７［１４］ＴａｎｇＬ， ＬｉｕＩ Ｉ ． Ｒｅｌａｔｉｏｎａｌｌｅａｒｎｉｎｇｖｉａ ｌａｔｅｎｔｓｏｃｉａｌ ｄｉｍｅｎｓｉｏｎｓ／／Ｐｒｏｃｅｅｄｉ ｎｇｓｏｆ ｔ ｈｅ１５ｔ ｈＡＣＭＳＩＧＫＤＤＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙａｎｄＤａｔ ａＭｉｎｉｎｇ． Ｐａｒｉｓ，Ｆｒａｎｃｅ， ２００ ９； ８１７ ８２６［１５］ＹａｎＤ， Ｉ ｌ ｕａｎｇＬ，ＪｏｒｄａｎＭＩ． Ｆａｓｔａｐｐｒｏｘｉｍａｔ ｅｓｐｅｃｔ ｒａｌｃｌｕｓｔｅｒｉｎｇ／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ１５ ｔｈＡＣＭＳＩＧＫＤＤＩｎｔ ｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙａｎｄＤａｔ ａＭｉｎｉｎｇ．Ｐａｒｉｓ， Ｆｒａｎｃｅ， ２００９： ９０７ ９１６［１６］ＢｅｌｋｉｎＭ， ＮｉｙｏｇｉＰ． Ｌａｐｌａｃｉａｎｅｉｇｅｎｍａｐｓａｎｄｓｐｅｃｔ ｒａｌｔｅｃｈｎｉｑｕｅｓｆ ｏｒｅｍｂｅｄｄｉｎｇａｎｄｃｌｕｓｔ ｅｒｉｎｇ／／ＡｄｖａｎｃｅｓｉｎＮｅｕｒａｌＩｎｆｏｒｍａｔ ｉｏｎＰｒｏｃｅｓｓｉｎｇＳｙｓｔｅｍｓ． Ｖａｎｃｏｕｖｅｒ ，Ｃａｎａｄａ ，２００２：５８５ ５９１［１７］Ｌｅｖｙ０， ＧｏｌｄｂｅｒｇＹ． Ｎｅｕｒａｌｗｏｒｄｅｍｂｅｄｄｉｎｇａｓｉｍｐｌｉｃｉ ｔｍａｔｒｉｘｆａｃｔｏｒｉｚａｔ ｉｏｎ／／ ＡｄｖａｎｃｅｓｉｎＮｅｕｒａｌＩｎｆｏｒｍａｔｉｏｎＰｒｏｃｅｓｓｉｎｇＳｙｓｔ ｅｍｓ． Ｍｏｎｔ ｒｅａｌ ， Ｃａｎａｄａ，２０１４： ２１７７ ２１８５［１８］ＣａｏＳ， ＬｕＷ， ＸｕＱ． ＧｒａＲｅｐ： Ｌｅａｒｎｉｎｇｇｒａｐｈｒｅｐｒｅｓｅｎｔ ａｔｉｏｎｓｗｉ ｔｈｇｌｏｂａｌｓｔ ｒｕｃｔｕｒａｌｉｎｆｏｒｍａｔ ｉｏｎ／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ２４ｔｈＡＣＭＩｎｔｅｒｎａｔｉｏｎａｌｏｎＣｏｎｆｅｒｅｎｃｅｏｎＩｎｆ ｏｒｍａｔ ｉｏｎａｎｄＫｎｏｗｌｅｄｇｅＭａｎａｇｅｍｅｎｔ． Ｍｅｌｂｏｕｒｎｅ， Ａｕｓｔ ｒａｌｉａ， ２０１５： ８９１９００ Ｍｉｎｉｎｇ． ＳａｎＦｒａｎｃｉｓｃｏ ， ＵＳＡ，２０１６： ８５５ ８６４４６０ 计 算机 学 报 ２０２１年［１９］ＯｕＭ， ＣｕｉＰ， ＰｅｉＪ ，ｅｔａｌ． Ａｓｙｍｍｅｔｒｉ ｃｔｒａｎｓｉｔｉｖｉｔｙｐｒｅｓｅｒｖｉｎｇｇｒａｐｈｅｍｂｅｄｄｉｎｇ／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ２２ｎｄＡＣＭＳＩＧＫＤＤＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙａｎｄＤａｔａＭｉｎｉｎｇ．ＳａｎＦｒａｎｃｉｓｃｏ，ＵＳＡ，２０１ ６： １１０５－１１１４［２０］ＹａｎｇＣ，Ｌｉ ｕＺ，ＺｈａｏＤ，ｅｔａｌ． Ｎｅｔｗｏｒｋｒｅｐｒｅｓｅｎｔａｔｉｏｎｌｅａｒｎｉｎｇｗｉｔｈｒｉｃｈｔｅｘｔｉｎｆｏｒｍａｔｉｏｎ／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ２４ ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＪｏｉｎｔＣｏｎｆｅｒｅｎｃｅｏｎＡｒｔｉｆｉｃｉａｌＩｎｔｅｌ ｌｉｇｅｎｃｅ．ＢｕｅｎｏｓＡｉｒｅｓ，Ａｒｇｅｎｔｉｎａ，２０１５：２１１１－２１１７［２１］ＺｈｕＤ，ＣｕｉＰ，ＺｈａｎｇＺ，ｅｔａｌ．Ｉ Ｉｉｇｈ－ｏｒｄｅｒｐｒｏｘｉｍｉｔｙ ｐｒｅｓｅｒｖｅｄｅｍｂｅｄｄｉｎｇｆｏｒｄｙｎａｍｉｃｎｅｔｗｏｒｋｓ． ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＫｎｏｗｌｅｄｇｅａｎｄＤａｔａＥｎｇｉｎｅｅｒｉｎｇ，２０１８ ，３０（１１）： ２１３４－２１４４［２２］ＥｃｋａｒｔＣ，ＹｏｕｎｇＧ． Ｔｈｅａｐｐｒｏｘｉｍａｔｉｏｎｏｆｏｎｅｍａｔｒｉｘｂｙａｎｏｔｈｅｒｏｆｌｏｗｅｒｒａｎｋ． Ｐｓｙｃｈｏｍｅｔｒｉｋａ，１９３６，１（３ ） ：２１１－２ １８［２３］ＬｅｈｏｕｃｑＲＢ，ＳｏｒｅｎｓｅｎＤＣ，ＹａｎｇＣ． ＡＲＰＡＣＫｕｓｅｒｓ？ｇｕｉｄｅ：Ｓｏｌｕｔｉｏｎｏｆｌａｒｇｅ－ｓｃａｌｅｅｉｇｅｎｖａｌｕｅｐｒｏｂｌｅｍｓｗｉｔｈｉｍｐｌｉｃｉｔｌｙｒｅｓｔａｒｔｅｄＡｒｎｏｌｄｉ ｍｅｔｈｏｄｓ．Ｐｈｉｌａｄｅｌｐｈｉａ ：ＳｏｃｉｅｔｙｆｏｒＩｎｄｕｓｔｒｉａｌａｎｄＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉ ｃｓ，１９９８［２４］Ｔｒｏｐｐ ＪＡ，ＹｕｒｔｓｅｖｅｒＡ，ＵｄｅｌｌＭ，ｅｔ ａｌ．Ｐｒａｃｔｉ ｃａｌｓｋｅｔｃｈｉｎｇａｌｇｏｒｉｔｈｍｓｆｏｒｌｏｗ－ｒａｎｋｍａｔｒｉｘａｐｐｒｏｘｉｍａｔｉｏｎ． ＳＩＡＭＪｏｕｒｎａｌｏｎＭａｔｒｉｘＡｎａｌｙｓｉｓａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２０１７ ，３８ （４） ： １４５４－１４８ ５［２５］Ｉ ｌｉｇｈａｍＮＪ． Ｍａｔｒｉｘｎｅａｒｎｅｓｓｐｒｏｂｌｅｍｓａｎｄａｐｐｌｉ ｃａｔｉｏｎｓ／／ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＩＭＡＣｏｎｆｅｒｅｎｃｅｏｎＡｐｐｌｉ ｃａｔｉｏｎｓ ｏｆ ＭａｔｒｉｘＴｈｅｏｒｙ． ＮｅｗＹｏｒｋ，ＵＳＡ，１９８９： １－２７［２６］ＢｏｙｄＳ，ＶａｎｄｅｎｂｅｒｇｈｅＬ． ＣｏｎｖｅｘＯｐｔｉｍｉｚａｔｉｏｎ．Ｃａｍｂｒｉｄｇｅ，ＵＫ：ＣａｍｂｒｉｄｇｅＵｎｉｖｅｒｓｉｔｙＰｒｅｓｓ，２００４（Ｓｅｃｔｉｏｎ４．２．３）［２７］ＹｕＷ， ＧｕＹ，ＬｉＪ． Ｓｉ ｎｇｌｅ－ｐａｓｓＰＣＡｏｆｌａｒｇｅｈｉｇｈ？ｄｉｍｅｎｓｉｏｎａｌｄａｔａ／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆ ｔｈｅ ２６ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＪｏｉ ｎｔＣｏｎｆｅｒｅｎｃｅｏｎＡｒｔｉｆｉｃｉａｌＩｎｔｅｌｌｉｇｅｎｃｅ． Ｍｅｌｂｏｕｒｎｅ，Ａｕｓｔｒａｌｉａ，２０１７ ： ３３５０－３３５６［２８］ＦｅｎｇＸ， Ｘｉ ｅＹ，ＳｏｎｇＭ，ｅｔａｌ． ＦａｓｔｒａｎｄｏｍｉｚｅｄＰＣＡｆｏｒｓｐａｒｓｅｄａｔａ／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ１０ｔｈＡｓｉａｎＣｏｎｆｅｒｅｎｃｅｏｎＭａｃｈｉｎｅＬｅａｒｎｉｎｇ．Ｂｅｉｊｉｎｇ，Ｃｈｉｎａ，２０１８ ：７１０－７２５［２９］ＳｔａｒｋＣ，Ｂｒｅｉ ｔｋｒｅｕｔｚＢＪ ， Ｃｈａｔｒ－ＡｒｙａｍｏｎｔｒｉＡ，ｅｔａｌ． ＴｈｅＢｉｏＧＲＩＤｉｎｔｅｒａｃｔｉｏｎｄａｔａｂａｓｅ： ２０１ １ｕｐｄａｔｅ． Ｎｕｃｌ ｅｉｃＡｃｉｄｓＲｅｓｅａｒｃｈ，２０１０，３９（Ｓｕｐｐｌ＿ｌ）：Ｄ６９８－Ｄ７０４［３０］Ｓｏｃｉａｌ－ＤｉｍｅｎｓｉｏｎＡｐｐｒｏａｃｈｔｏＣｌａｓｓｉｆｉｃａｔｉｏｎｉｎＬａｒｇｅ－ＳｃａｌｅＮｅｔｗｏｒｋｓ， ｈｔｔｐ： ／／ｌｅｉｔａｎｇ．ｎｅｔ／ｓｏｃｉａｌ＿ｄｉｍｅｎｓｉｏｎ， ｈｔｍｌ，２０１０．７． ２９［３ １］Ｔａｎｇ Ｊ ， Ｚｈａｎｇ Ｊ， ＹａｏＬ， ｅｔａｌ．Ａｒｎｅｔｍｉ ｎｅｒ：Ｅｘｔｒａｃｔｉｏｎａｎｄｍｉｎｉｎｇｏｆａｃａｄｅｍｉｃｓｏｃｉａｌｎｅｔｗｏｒｋｓ／／Ｐｒｏｃｅｅｄｉ ｎｇｓｏｆｔｈｅ１４ｔｈＡＣＭＳＩＧＫＤＤＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙａｎｄＤａｔａＭｉｎｉｎｇ．ＬａｓＶｅｇａｓ？ＵＳＡ，２００８： ９９０－９９８［３２］ＦａｎＲＥ，ＣｈａｎｇＫＷ？Ｉ ｌｓｉ ｅｈＣＪ，ｅｔａｌ． ＬＩＢＬＩＮＥＡＲ：Ａｌｉ ｂｒａｒｙｆｏｒｌａｒｇｅｌｉ ｎｅａｒｃｌ ａｓｓｉｆｉ ｃａｔｉｏｎ． ＪｏｕｒｎａｌｏｆＭａｃｈｉｎｅＬｅａｒｎｉｎｇＲｅｓｅａｒｃｈ， ２００８ ，９ ：１８７１－１８７４［３３］ＴａｎｇＬ，ＲａｊａｎＳ， ＮａｒａｙａｎａｎＶＫ． Ｌａｒｇｅｓｃａｌｅｍｕｌｔｉ－ｌ ａｂｅｌｃｌａｓｓｉｆｉｃａｔｉｏｎｖｉａｍｅｔａｌａｂｅｌｅｒ／／Ｐｒｏｃｅｅｄｉ ｎｇｓｏｆｔｈｅ１８ｔｈＩｎｔｅｒ？ｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＷｏｒｌｄＷｉｄｅＷｅｂ． Ｍａｄｒｉｄ，Ｓｐａｉｎ，２００９： ２１１－２２０［３４］ＹａｎｇＹ． Ａｎｅｖａｌｕａｔｉｏｎｏｆｓｔａｔｉｓｔｉｃａｌａｐｐｒｏａｃｈｅｓｔｏｔｅｘｔｃａｔｅｇｏｒｉｚａｔｉｏｎ． ＩｎｆｏｒｍａｔｉｏｎＲｅｔｒｉ ｅｖａｌ，１９９９，１（１－２）： ６９－９０［３５］ＧｏｄｂｏｌｅＳ，ＳａｒａｗａｇｉＳ． Ｄｉ ｓｃｒｉｍｉｎａｔｉｖｅｍｅｔｈｏｄｓｆｏｒｍｕｌ ｔｉ－ｌａｂｅｌｅｄｃｌ ａｓｓｉｆｉ ｃａｔｉｏｎ／／Ｐａｃｉｆｉｃ－ＡｓｉａＣｏｎｆｅｒｅｎｃｅｏｎＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙａｎｄＤａｔａＭｉｎｉｎｇ． Ｂｅｒｌ ｉｎ， Ｇｅｒｍａｎｙ：Ｓｐｒｉｎｇｅｒ，２００４：２２－３０ＸＩＥＹｕ－Ｙａｎｇ，Ｐｈ．Ｄ．ｃａｎｄｉｄａｔｅ．Ｈｉｓｒｅｓｅａｒｃｈｉｎｔｅｒｅｓｔｓｉｎｃｌｕｄｅｄａｔａｍｉｎｉｎｇａｎｄｍａｔｒｉｘａｎａｌｙｓｉｓ．ＦＥＮＧＸｕ， Ｐｈ．Ｄ．ｃａｎｄｉｄａｔｅ．Ｈｉｓｒｅｓｅａｒｃｈｉｎｔｅｒｅｓｔｉｓｍａｔｒｉｘａｎａｌｙｓｉｓ．ＹＵＷｅｎ－Ｊｉａｎ， Ｐｈ．Ｄ． ，ａｓｓｏｃｉａｔｅｐｒｏｆｅｓｓｏｒ．Ｈｉｓｒｅｓｅａｒｃｈｉｎｔｅｒｅｓｔｓｉｎｃｌ ｕｄｅｃｏｍｐｕｔｅｒａｉｄｅｄｄｅｓｉｇｎｏｆＩＣａｎｄｍａｔｒｉｘａｎａｌｙｓｉｓ．ＴＡＮＧＪｉｅ， Ｐｈ．Ｄ． ，ｐｒｏｆｅｓｓｏｒ．Ｈｉｓｒｅｓｅａｒｃｈｉｎｔｅｒｅｓｔｓｉｎｃｌｕｄｅｓｏｃｉａｌｎｅｔｗｏｒｋｍｉｎｉｎｇａｎｄａｃａｄｅｍｉｃｋｎｏｗｌｅｄｇｅｇｒａｐｈ．ＢａｃｋｇｒｏｕｎｄＩｎｏｒｄｅｒｔｏｐｒｏｃｅｓｓｎｅｔｗｏｒｋｄａｔａｅｆｆｅｃｔｉｖｅｌｙ，ｔｈｅｃｈａｌｌｅｎｇｅｉｓｔｏｆｉｎｄｅｆｆｅｃｔｉｖｅｎｅｔｗｏｒｋｄａｔａｒｅｐｒｅｓｅｎｔａｔｉｏｎ．Ｔｈｅｔｒａｄｉｔｉｏｎａｌｎｅｔｗｏｒｋｄａｔａｒｅｐｒｅｓｅｎｔａｔｉｏｎｈａｓｂｅｃｏｍｅａｂｏｔｔｌｅｎｅｃｋｉｎｌａｒｇｅ－ｓｃａｌ ｅｎｅｔｗｏｒｋｄａｔａｎｏｗａｄａｙｓ．Ｎｅｔｗｏｒｋｅｍｂｅｄｄｉｎｇ，ｗｈｉｃｈａｉｍｓｔｏｌｅａｒｎｌｏｗ－ｄｉ ｍｅｎｓｉｏｎａｌｖｅｃｔｏｒｒｅｐｒｅｓｅｎｔａｔｉｏｎｓｆｏｒｎｅｔｗｏｒｋｎｏｄｅｓａｎｄｅｆｆｅｃｔｉｖｅｌｙｐｒｅｓｅｒｖｅｔｈｅｎｅｔｗｏｒｋｓｔｒｕｃｔｕｒｅ，ｉ ｓａｐｒｏｍｉｓｉｎｇｗａｙｏｆｎｅｔｗｏｒｋｒｅｐｒｅｓｅｎｔａｔｉｏｎ．Ｄｕｒｉｎｇｔｈｅｐａｓｔｆｅｗｙｅａｒｓ ，ｔｈｅｒｅｉｓａｓｕｒｇｅｏｆｒｅｓｅａｒｃｈｏｎｎｅｔｗｏｒｋｅｍｂｅｄｄｉ ｎｇ．ＤｅｅｐＷａｌｋ， ＬＩＮＥａｎｄｎｏｄｅ２ｖｅｃｍｏｄｅｌ ｓｗｈｉ ｃｈａｒｅｓｋｉｐ－ｇｒａｍｂａｓｅｄｈａｖｅｂｅｅｎｃｏｎｓｉｄｅｒｅｄａｓｐｏｗｅｒｆｕｌｂｅｎｃｈｍａｒｋｓｏｌｕｔｉｏｎｓｆｏｒｎｅｔｗｏｒｋｅｍｂｅｄｄｉｎｇｒｅｓｅａｒｃｈ．ＧｒａＲｅｐ， ＨＯＰＥ， ＮｅｔＭＦ， ＮｅｔＳＭＦａｎｄＰｒｏＮＥｍｏｄｅｌｓａｒｅｍａｔｒｉ ｘｆａｃｔｏｒｉｚａｔｉｏｎｂａｓｅｄｎｅｔｗｏｒｋｅｍｂｅｄｄｉｎｇｍｅｔｈｏｄｓ．ＮｅｔＭＦａｌｇｏｒｉｔｈｍｔｈｅｏｒｅｔｉｃａｌｌｙｕｎｉｆｉｅｓｓｅｖｅｒａｌ ｎｅｔｗｏｒｋｅｍｂｅｄｄｉｎｇｍｅｔｈｏｄｓａｎｄｓｈｏｗｔｈｅｅｍｂｅｄｄｉｎｇｌ ｅａｒｎｅｄｂｙＮｅｔＭＦｉｓａｓｐｏｗｅｒｆｕｌａｓｔｈｏｓｅｌ ｅａｒｎｅｄｆｒｏｍｔｈｅｓｋｉｐ－ｇｒａｍｂａｓｅｄｍｅｔｈｏｄｓ．Ｔｈｅｍａｊｏｒｄｉ ｓａｄｖａｎｔａｇｅｏｆｅｘｉ ｓｔｉｎｇｍｅｔｈｏｄｓｗｈｉ ｃｈｉｓｂａｓｅｄｏｎｍａｔｒｉｘｆａｃｔｏｒｉ ｚａｔｉ ｏｎｉｓｔｈｅｌａｒｇｅｃｏｓｔｏｎ谢雨洋等： 基于随机化矩阵分解的网络嵌人方法 ４６ １３ 期ｃｏｍｐｕｔａｔｉｏｎａｎｄｍｅｍｏｒｙ．Ｉｎｔｈｉｓｗｏｒｋ， ｗｅｕｓｅｆａｓｔｒａｎｄｏｍｉｚｅｄｅｉｇｅｎｖａｌ ｕｅｄｅｃｏｍｐｏｓｉｔｉｏｎ（ＥＶＤ）ａｎｄｓｉｎｇｌｅｐａｓｓｓｉｎｇｕｌａｒｖａｌｕｅｄｅｃｏｍｐｏｓｉｔｉｏｎ（ＳＶＤ）ｔｏｉｍｐｒｏｖｅＮｅｔＭＦａｎｄｐｒｅｓｅｎｔａｎｅｆｆｉｃｉｅｎｔｒａｎｄｏｍｉｚｅｄｍａｔｒｉｘｆａｃｔｏｒｉｚａｔｉｏｎｂａｓｅｄｎｅｔｗｏｒｋｅｍｂｅｄｄｉ ｎｇａｌｇｏｒｉｔｈｍ（ｅＮｅｔＭＦ）． Ｆｉｒｓｔｌｙ， ｗｅｐｒｏｐｏｓｅａｆａｓｔｒａｎｄｏｍｉｚｅｄＥＶＤａｌｇｏｒｉｔｈｍ（ｆｒｅｉｇｓ）ｆｏｒｓｐａｒｓｅｍａｔｒｉ ｘ． Ｓｅｃｏｎｄｌ ｙ， ｗｅｐｒｏｐｏｓｅｔｏｕｓｅｓｉｎｇｌ ｅｐａｓｓＳＶＤａｐｐｒｏａｃｈｔｏｐｒｏｃｅｓｓｈｉｇｈ ｏｒｄｅｒｐｒｏｘｉｍｉｔｙｍａｔｒｉｘｉｎｔｈｅＮｅｔＭＦ， ｓｏｔｈａｔｗｅｃａｎａｖｏｉｄｓｔｏｒｉｎｇｔｈｅｌａｒｇｅｄｅｎｓｅｍａｔｒｉｘａｎｄｌａｒｇｅｌｙｒｅｄｕｃｅｔｈｅｍｅｍｏｒｙｃｏｓｔ．Ｔｈｉｒｄｌ ｙ， ｗｅｐｒｏｐｏｓｅａｓｉ ｍｐｌｉｆｉｅｄ， ｒａｎｄｏｍｉｚｅｄｓｉｎｇｌｅｐａｓｓＳＶＤａｌｇｏｒｉｔｈｍｔｈａｔｇｕａｒａｎｔｅｅｓａｓｙｍｍｅｔｒｉｃｄｅｃｏｍｐｏｓｉｔｉｏｎｒｅｓｕｌｔ．Ｃｏｍｂｉｎｉｎｇｔｈｅａｂｏｖｅｔｅｃｈｎｉｑｕｅｓ，ｗｅｆｉｎａｌｌｙｏｂｔａｉｎｔｈｅｅＮｅｔＭＦａｌｇｏｒｉｔｈｍ．Ｗｉｔｈｆｉ ｖｅｒｅａｌｎｅｔｗｏｒｋｄａｔａｓｅｔｓ， ｗｅｅｖａｌｕａｔｅｔｈｅｅｆｆｉｃｉ ｅｎｃｙａｎｄｅｆｆｅｃｔｉｖｅｎｅｓｓｏｆｔｈｅｅＮｅｔＭＦａｌｇｏｒｉｔｈｍｏｎｍｕｌｔｉｌ ａｂｅｌｎｏｄｅｃｌ ａｓｓｉｆｉｃａｔｉｏｎ． ＥｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｉｎｔｅｒｍｓｏｆｔｈｅｍｅｔｒｉｃｓＭａｃｒｏ ＦＩａｎｄＭｉｃｒｏ Ｆｌ ， ｔｈｅｅｍｂｅｄｄｉｎｇｇｅｎｅｒａｔｅｄｂｙｅＮｅｔＭＦｈａｓｔｈｅｓａｍｅｐｅｒｆｏｒｍａｎｃｅａｓＮｅｔＭＦｉｎｍｕｌ ｔｉ ｌａｂｅｌ ｎｏｄｅｃｌ ａｓｓｉｆｉｃａｔｉｏｎ．Ｂｅｎｅｆｉｔｉｎｇｆｒｏｍｒａｎｄｏｍｉｚｅｄｍａｔｒｉｘｄｅｃｏｍｐｏｓｉｔｉｏｎａｌｇｏｒｉｔｈｍｓ＞ｅＮｅｔＭＦｉｓｆａｓｔａｎｄｍｅｍｏｒｙｆｒｉｅｎｄｌｙｃｏｍｐａｒｅｄｔｏＮｅｔＭＦ．Ｗｅｂｅｌｉｅｖｅｔｈｅｒａｎｄｏｍｉｚｅｄｍａｔｒｉｘｄｅｃｏｍｐｏｓｉｔｉｏｎａｌｇｏｒｉｔｈｍｓａｒｅｇｅｎｅｒｉｃａｎｄｃａｎｂｅａｐｐｌ ｉｅｄｔｏｍａｔｒｉ ｘｆａｃｔｏｒｉｚａｔｉｏｎｂａｓｅｄｎｅｔｗｏｒｋｅｍｂｅｄｄｉ ｎｇｍｏｄｅｌｓ， ａｎｄｈｏｐｅｔｈｉ ｓｐａｐｅｒｗｉｌｌｉｎｓｐｉｒｅｍｏｒｅｆｕｔｕｒｅｒｅｓｅａｒｃｈｉｎｔｈｉｓａｒｅａ．ＴｈｉｓｗｏｒｋｉｓｓｕｐｐｏｒｔｅｄｂｙＮａｔｉｏｎａｌＫｅｙＲ＆ＤＰｒｏｇｒａｍｏｆＣｈｉｎａ（ＧｒａｎｔＮｏ． ２０２０八八八０１０３５０２）ａｎｄｔｈｅＮａｔｉｏｎａｌＮａｔｕｒａｌＳｃｉ ｅｎｃｅＦｏｕｎｄａｔｉｏｎ（ ＧｒａｎｔＮｏ． ６１ ８７ ２２０６）． Ｔｈｉｓｗｏｒｋｆｏｃｕｓｅｓｏｎｔｈｅｒａｎｄｏｍｉｚｅｄｍａｔｒｉｘｄｅｃｏｍｐｏｓｉｔｉｏｎａｎｄｉｔｓａｐｐｌｉｃａｔｉｏｎｉｎｎｅｔｗｏｒｋｅｍｂｅｄｄｉｎｇ． Ｏｕｒｇｒｏｕｐｈａｓｂｅｅｎｓｔｕｄｙｉｎｇｒａｎｄｏｍｉｚｅｄｍａｔｒｉｘｄｅｃｏｍｐｏｓｉｔｉｏｎａｎｄｎｅｔｗｏｒｋｅｍｂｅｄｄｉｎｇｆｏｒｙｅａｒｓ， ａｎｄｈａｓｐｒｏｐｏｓｅｄａｓｅｒｉ ｅｓｏｆｗｏｒｋｓｕｃｈａｓｆｒＰＣ八， ＮｅｔＭＦ， ＮｅｔＳＭＦａｎｄＰｒｏＮＥ． |
| [返回] |
下一篇：基于目标导向行为和空间拓扑记忆的视觉导航方法_阮晓钢