Sep, 2023

稀疏邻接矩阵的随机投影

PDF
TL;DR分析了一种用于邻接矩阵的随机投影方法，研究其在表示稀疏图中的实用性，展示了这些随机投影保留了其底层邻接矩阵的功能，同时具有额外的特性，使它们作为动态图表示具有吸引力。特别地，它们可以在相同的空间中表示不同大小和顶点集的图，从而实现对图的聚合和操作的统一方式。同时提供关于投影大小需要如何扩展以保留准确的图操作的结果，表明投影的大小可以与顶点数线性扩展，同时准确地保留一阶图信息。最后，将这种随机投影描述为保持距离的邻接矩阵映射，类似于通常的 Johnson-Lindenstrauss 映射。
random projection methodadjacency matricessparse graphsdynamic graph representationsdistance-preserving map
发现论文，激发创造
  • 随机投影下的节点相似性：极限和病态案例

    通过随机投影方法生成的嵌入向量在计算效率上得到了广泛应用，本文进一步研究了随机投影对点积和余弦相似度的保留效果并提供了新的理论结果，找出了病态案例并用数值实验进行了测试，发现对于低度或高度节点，此方法在点积上得到的嵌入向量相对不可靠，而与随机投影引入的统计噪声相比，余弦相似度得到了更精确的近似。

    Apr, 2024

  • 随机投影的精确表达式：低秩逼近与随机牛顿

    利用随机矩阵的谱分析最新进展，我们开发了一种新的技术，提供了随机投影矩阵的期望值的确切表达式，这些表达式可以用来表征多种常见的机器学习任务中的降维性能，包括低秩估计和迭代随机优化等。我们的结果适用于多种流行的草图方法，包括高斯和 Rademacher 草图，结果表明，我们推导出的表达式反映了这些草图方法的实际性能，甚至体现了较低阶效应和恒定因子。

    Jun, 2020

  • 一个用于比较图形的新空间

    本文提出了一种基于协方差矩阵的图形表示方法，并定义了相似度测量方法，可用于社交网络的分类，同时该方法的计算效率高，可用于大规模实践，并对截断幂次迭代的研究提供了理论和实证支持。

    Apr, 2014

  • 通过稀疏转置接近度可扩展的图嵌入

    本文研究了在有向和无向图上进行图嵌入技术的基础方法和存在的问题，提出了一个新的方法叫做转置接近度，以解决现有方法无法保持有向图外度分布和无向图优化目标冲突的问题，并且展示了该方法在各种图嵌入算法中的高效性和优越性。

    May, 2019

  • 重新审视 Nystrom 方法以改进大规模机器学习

    本篇研究论文旨在重新考虑随机算法用于对称半正定矩阵的低秩逼近，通过实证评估了样本抽样和投影方法的性能质量和运行时间，证明了它们的互补性，在相对误差较低前提下表明了不同采样方法之间的重要区别，并为随机抽样和随机投影方法提供最坏情况的理论边界。

    Mar, 2013

  • 结构化散列投影的二进制嵌入

    此论文研究了利用哈希机制来构建二进制嵌入的方法，该方法包括伪随机投影和非线性映射，使用结构化矩阵可以有效地压缩信息并降低随机性使用，实验证明了其对神经网络学习性能和最近邻分类器性能的依赖关系。

    Nov, 2015

  • 随机内积图的普适一致潜在位置估计及顶点分类

    本文介绍了使用邻接矩阵的特征分解可以一致地估计从分布中独立同分布的潜在位置，并且如果类标签对于趋近于无穷的顶点观察，则剩余的顶点可以使用 K 最近邻分类规则收敛于贝叶斯最优。我们使用模拟数据和从维基百科衍生的图表评估了提出的方法。

    Jul, 2012

  • 张量随机投影

    介绍了一种基于张量分解格式 —— 张量列车（TT）和 CP 分解格式 —— 的两种张量随机投影映射方法来降低高维张量的维数，从而显著地降低了存储和计算成本，并证明了采用 TT 格式比 CP 格式更能够更快地实现相同的降维效果，相关实验验证了理论分析结果。

    Mar, 2020

  • 通过低秩非对称投影学习边缘表示

    本文提出了一种新的无向图嵌入方法，通过建模节点的连边函数，并结合从随机游走中抽样的信息，对图的联通结构进行表达，从而提高了学到的嵌入空间的表现和空间效率。该方法在社交网络、蛋白质相互作用等数据集上均取得了较好的表现。

    May, 2017

  • 随机流形的随机投影

    通过研究典型的高斯随机流形的随机投影所产生的畸变，我们发现了一种明确可计算的近似理论界限来确保这些流形的几何形状的精度，我们的理论界限比之前的研究结果紧凑了几个数量级。

    Jul, 2016