内容纲要

这是一篇NIPS2020的论文。但就论文写作来说,真TM难懂,写的是什么鬼文章,阅读理解都没你这秀。
如何选择嵌入维度是一个细微的决定,但是在理论上,可以使用阵势维度的概念。在谱嵌入中,维度通常很高,然而,这篇文章表示,已存在的随机图模型,包含graphon或者其他潜在的位置模型,预测数据应该位于一个低维的集合。

introduction

高维数据通常位于低维的流形中,通常用来解释为什么高维学习实际上可行。本文的目的是表明,对于理论上易处理但丰富的一类随机图模型,这种现象会在图的光谱嵌入中发生。
当图遵循潜在位置模型时,就会出现流形结构,其中根据节点在空间中的基础位置来确定发生连接的位置。
频谱嵌入通过图的邻接或归一化拉普拉斯矩阵的特征组合来获得每个节点的矢量表示,并且与给定模型的潜在位置之间存在有意义的联系不够明显。本文的一个贡献是使这个联系更加清晰,尽管现有的研究已经把我们带到了大部分途径:Tang和合著者[65]和Lei [40]分别构造了相同的图,并假设其为正定核(在此概括为 不确定)和一个graphon模型(此处扩展为d维)。通过这种联系,出现了真正的嵌入维D的概念,它是预期邻接矩阵的大样本秩,并且可能比潜在空间维d大得多。
本文的主要贡献是证明,尽管数据是高维的,但数据却“靠近”低维结构(潜伏空间的失真),该结构的尺寸受潜在位置模型内核沿其对角线的曲率控制。作为一种特殊情况,将d维流形嵌入到无限维的环境空间中。但是,相信graphon模型作用于单位间隔,即d = 1,只能产生一维流形,这将是一个重大的误解。 取而代之的是,常见的Hölder光滑度假设将最大可能流形尺寸限制为2 /α。
“紧密”表示一种强形式的一致性,其中最大的位置误差随着图形的增长而消失,因此后续的统计分析(例如流形估计)将从更高质量的数据(包括接近于流形和数量)双倍增益。通过广义随机点积图(或其无限维扩展)在环境空间中运行,并调用相应的估计理论,可以简单地建立这一点。
人们通常认为,研究图的相关渐近机制是稀疏的,从某种意义上说,平均而言,节点的度数在节点数上的增长应小于线性增长。 只要度数增长足够快(比对数快),上述估计理论就适用于这种情况,并指出后者的速率对应于信息理论极限的强一致性。尽管是标准的且是理论所需的,但通过全局缩放来诱发稀疏性的方式并不是最现实的,未能通过对其他期望的投射性测试。 其他几篇论文也对此问题进行了深入探讨。

最后修改日期:2020年12月26日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。