简介

Hello！
非常感谢您阅读海轰的文章，倘若文中有错误的地方，欢迎您指出～
 
ଘ(੭ˊᵕˋ)੭
昵称：海轰
标签：程序猿｜C++选手｜学生
简介：因C语言结识编程，随后转入计算机专业，获得过国家奖学金，有幸在竞赛中拿过一些国奖、省奖…已保研
学习经验：扎实基础 + 多做笔记 + 多敲代码 + 多思考 + 学好英语！
 
唯有努力💪
 
【每日一读】每天浅读一篇论文，了解专业前沿知识，培养阅读习惯（阅读记录 仅供参考）

论文简介

原文链接：https://dl.acm.org/doi/10.1145/3219819.3220062

会议：KDD '18: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining （CCF A类）

年度：2018年7月19日

ABSTRACT

网络嵌入学习顶点的低维表示，同时保留网络结构反映的顶点间相似性

顶点的邻域结构通常与底层的层次分类法密切相关——顶点与可以按层次组织的更广泛的类别相关联

不同层次的类别反映了不同粒度的相似性

因此，分类的层次结构要求学习的表示支持多层次的粒度

此外，分层分类法使信息能够通过它们的共同类别在顶点之间流动，从而为缓解数据稀缺性提供了有效的机制

然而，将分层分类法整合到网络嵌入中带来了巨大的挑战（因为分类法通常是未知的），并且被现有方法所忽视

在本文中，我们提出了 NetHiex，这是一种网络嵌入模型，可捕获潜在的 HIerarchical 分类法

在我们的模型中，顶点表示由与不同粒度类别相关联的多个组件组成（顶点和类别的表示都是共同正则化的）

• 采用嵌套的中餐厅流程来指导搜索最合理的分层分类法
• 然后通过伯努利分布从潜在表示中恢复网络结构
• 整个模型统一在一个非参数概率框架内
• 一种可扩展的期望最大化算法被推导出来进行优化

实证结果表明，NetHiex 比现有技术实现了显着的性能提升

1 INTRODUCTION

网络嵌入，也称为网络表示学习，是最近提出的一种范式，可以自动为网络中的顶点提取连续特征向量的过程

网络嵌入的一个基本要求是学习的顶点表示应该保持网络结构所反映的顶点间相似性[6,11,14]

因此，已经提出了各种网络嵌入方法来保留一阶、二阶和 k 阶接近度 [7、21、29]，以及通过随机游走探索的邻域结构 [13、23] 等

邻域结构通常与底层的层次分类法密切相关，其中与顶点相关的连续更广泛的类别被分层组织并形成分类法的树层次结构

不同层次的类别揭示了不同粒度的相似性

例如，在图 1 所示的引文网络中，一篇关于自然语言处理 (NLP) 的论文和一篇关于计算机视觉 (CV) 的论文属于两个不同的类别，并且根据它们的细粒度邻域结构被认为是不同的

尽管如此，在查看粗粒度结构时，关于 NLP 的论文和关于 CV 的论文实际上可以被认为是相似的，因为它们都属于人工智能 (AI) 类别

因此，分类的层次结构要求顶点表示跨多个粒度级别对结构信息进行编码，以便很好地支持各种下游应用程序。

此外，分层分类法为缓解数据稀缺问题提供了有效机制

现实世界的网络通常是非常稀疏的
要么是因为收集综合数据的困难
要么是实体之间没有足够多的接触以形成大多数链接

分层分类法有助于提取、存储和重用与每个类别相关的公共知识

因此，如果两个顶点在层次结构中共享公共类别，则两个远程连接的顶点（彼此相距几跳）之间的关系将得到加强

然而，分层分类法在很大程度上被现有的网络嵌入方法所忽视，将其纳入网络嵌入带来了巨大的挑战

我们面临着在无数树结构的组合空间中寻找合适的分类法的艰巨任务，因为底层的层次分类法通常是未知的

在本文中，我们提出了 NetHiex，这是一种网络嵌入模型，可以同时检测和利用底层的分层分类法

如图 1 所示，我们模型中的顶点表示由多个组件组成，每个组件对应于层次结构 1 的不同层的一个类别

与顶点关联的不同粒度的类别然后形成从根到树层次结构中的一个叶子

我们采用嵌套中餐厅过程 (nCRP) [3, 4] 作为树结构和路径的先验分布

然后将潜在表示和观察到的网络结构与伯努利分布联系起来

直观地说，层次结构顶部的类别将通过比底部类别更多的路径传递，因此倾向于表示更粗粒度的类别

结果，由不同级别的类别正则化的顶点表示的不同组件将倾向于捕获不同粒度的特征

此外，类别从相关的顶点表示中提取常识，并将其以类别表示的形式存储

两个远程连接的顶点之间的关系因此得到加强，因为它们现在通过其路径传递的公共类别共享信息

总体而言，我们的模型在非参数概率框架内统一

我们推导出一种有效的期望最大化（EM）算法来估计参数

我们的算法每次迭代的总体时间复杂度与网络规模成线性关系，这使得我们的方法适用于现实世界的大规模网络

我们在几个基准数据集上凭经验评估我们的方法

结果表明，我们的方法可以在各种任务（例如分类和链接预测）中显着优于最先进的方法，并且对缺失数据具有鲁棒性

我们进一步检查了在单词共现网络上学习的层次分类法，并可视化了多个粒度级别

我们论文的贡献总结如下：

• 我们研究了将层次分类法纳入网络嵌入的重要问题。我们的方法 NetHiex 能够学习同时保留细粒度和粗粒度网络结构的表示。
• 我们推导出一种高效的 EM 算法，其每次迭代都具有线性时间复杂度。这使得我们的方法与现有的可扩展方法具有很强的竞争力。
• 大量的定量和定性实验证明了学习具有多个粒度级别的表示并通过分层分类法减轻数据稀缺性的优点。

2 THE HIERARCHICAL MODEL

在本节中，我们将介绍 NetHiex，这是一个用于网络嵌入的统一概率框架，具有潜在的分层分类法。

2.1 Model Description

我们使用高度为 L 的树（从根到叶的所有路径的长度为 L）来表示类别的层次结构（例如图 1）

给定一个具有 N 个顶点的网络，我们假设每个顶点都与树层次结构中的一条路径（从根到叶）相关联

设cn为顶点n的路径。路径cn表示顶点n所属的一系列连续细粒度的类别。

树层次结构的确切结构是未知的，我们也不知道每个顶点被分配到哪条路径

因此，我们使用嵌套的中餐厅过程 (nCRP) [4] 作为树结构和路径的先验分布

换句话说，nCRP 提供了先验概率

我们将在下一小节中给出 nCRP 的详细定义

目前，让我们专注于模型的其余部分，以便全面了解我们的方法。

5 RELATED WORK

网络嵌入 [6 , 11 , 14 ]，也称为网络表示学习，在 DeepWalk [23] 最近取得成功之后获得了动力。与基于特征分解的前辈（例如 LLE [26]、拉普拉斯特征图 [2] 和 Isomap [32]）不同，DeepWalk 结合了 word2vec [19] 和随机游走，并允许可扩展的随机优化。从那时起，许多新算法被提出来更好地捕捉网络结构。 LINE [29] 提出保留一阶和二阶接近度，node2vec [13] 旨在探索具有偏向随机游走的不同邻域。还探讨了其他概念，例如非线性[8、36]、高阶关系[7、21、24]、网络社区[38]和结构身份[25]。另一项研究侧重于嵌入更复杂的网络，例如属性网络[40]、有向网络[21]、有符号网络[37、43]、异构信息网络[9、10、12]和动态网络[16、17、42、44]。网络嵌入也被集成到其他范式中，例如半监督学习 [41] 和归纳学习 [15]。然而，我们不知道其他研究底层层次分类法的网络表示学习工作。

实体的层次结构在自然语言处理（NLP）领域得到了更积极的研究。例如，本体学习旨在从文本中自动提取本体 [39]，其中构建了提取概念的层次结构。与 NLP 最接近的工作可能是分层主题建模 [4]。在分层主题模型中，主题形成层次结构，每个文档与一个 [4] 或多个 [22] 路径相关联（分别通过嵌套 CRP [1] 和分层 Dirichlet 过程 [31]）。我们的模型也建立在 nCRP [4] 上。但是，我们利用 nCRP 的方式是不同的。此外，以前基于 nCRP 的模型通常采用 MCMC [3, 4] 或变分推理 (VI) [35] 进行优化，而我们提出了一种 EM 算法，它比 MCMC 快得多，并且比 VI 更容易实现。

6 CONCLUSION

在本文中，我们介绍了 NetHiex，这是一种网络嵌入算法，它揭示并利用了分层分类法。特别是，我们利用分层分类法来捕获不同级别的粒度并缓解数据稀缺性。

将我们的工作扩展到加权/归因/定向网络很简单（参见第 2.3 节）。然而，如何将我们的算法推广到异构信息网络（HIN）还不太清楚。未来工作的一个有趣方向是整合元路径 [10, 12, 28] 和底层的分层分类，以学习 HIN 的顶点表示。

读后总结

emmm，第一次接触到嵌入中的层次分类法，孤陋寡闻了

还是得多阅读啊 😮‍💨

结语

文章仅作为个人学习笔记记录，记录从0到1的一个过程

希望对您有一点点帮助，如有错误欢迎小伙伴指正

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/127102450