1. 基本信息- 论文题目:Taming graph kernels with random features
- 作者:Krzysztof Choromanski,Columbia University
- 机构:Google DeepMind, Columbia University
2. 摘要本文提出了一种新的图随机特征(GRFs)机制,可用于构建图节点上定义的几种重要核(特别是正则化拉普拉斯核)的无偏随机估计量。与非图核的常规随机特征一样,它们可以扩展基于图的核方法以处理更大的网络。更重要的是,即使对较小的图,它们在下游应用中也可以提供可观的计算收益。因此,GRFs解决了图核算法立方时间复杂性的难题。作者提供了GRFs的详细理论分析和广泛的实验评估:从速度测试、相对Frobenius范数误差分析到使用图核的k均值聚类。作者表明,GRFs的计算允许一个非常简单的分布式算法,可应用于特别大的图。作者还介绍了GRFs的一种(仍然无偏的)准蒙特卡洛变体,依赖于所谓的加强随机游走,可用于优化GRFs的方差。作为副产品,作者还获得了一种用于求解具有正和对称矩阵的线性方程组的新方法。 3. 介绍- 目前研究工作中存在的问题是大多数图核算法的计算复杂度至少是图中节点数的三次方,这是一个实现这些方法更实用和主流的关键障碍。
- 本文的主要贡献是首次提出图随机特征(GRFs)的机制,为基于图节点的各种核提供无偏、计算高效的估计。
- GRFs通过在不同节点中启动的随机游走序列来构建,在访问的图顶点中存储负载。GRF计算的时间复杂度为O(Nmt/p + T),其中N为节点数,m为随机游走次数,t为每步游走的时间复杂度,p为提前终止游走的概率,T为图表示的复杂度。
 4. 方法4.1 正方逆矩阵的隐藏Gram结构令由行向量组成,其中由下面的算法计算: 初始化: $\phi(i)[j]$ = 0, $j=1,...,N$
初始化: H = ∅ # 访问顶点历史
for t=1,...,m:
初始化: load = 1
初始化: current vertex = i
更新: $\phi(i)[i]$ += 1
while not terminated:
v = current vertex
w,p = sample(v,G_U,H)
更新: current vertex = w
更新: load *= u_vw/p(1-pterm)
更新: $\phi(i)[w]$ += load
更新: H.add((v,w))
规范化: $\phi(i)$ /= m
该结论可以推广到更一般的正对称矩阵。 4.2 从平方逆矩阵到图核- 对于带权无向图,考虑d正则化Laplacian核:
其中是对称规范的Laplacian矩阵。 其中的行向量为。 其中。 4.3 GRF用于快速图核方法- GRFs可以在子立方时间内完成图核矩阵的低秩分解。
4.4 q-GRFs和相关随机游走- q-GRFs的想法是关联不同在给定节点启动的随机游走,以“更高效地”探索整个图,它可以看作是正交随机特征在非欧几里得域的拓展。
- 一种可能的q-GRF变体是实现强化随机游走策略,其中选择邻居w的概率与边(v,w)已被访问的次数相关。
5. 实验发现- 在不同大小的图上,即使对较小的图(节点数<1000),GRFs也可以将FLOPS数减少多个数量级。
- 通过相对Frobenius范数误差分析,作者发现每次随机游走数m=80就可以使误差小于2%。
- 在k均值聚类实验中,GRFs提供了精确的近似,在某些图上的错误小于1%。
6. 结论本文提出了图随机特征(GRFs)的新范式,以无偏、计算高效的方式估计定义在图节点上的各种核。GRFs依赖于在不同节点中启动的随机游走族,在访问的图顶点中存储负载。作者提供了GRFs的详细理论分析和大量实验,包括图上的k均值聚类。GRFs解决了图核算法立方时间复杂性的难题。作者的方法还提供了一种求解具有正对称矩阵的线性方程组的新方法。GRFs的计算非常简单,可以并行化,并且可以轻松地进行分布式实现。作者还引入了GRFs的准蒙特卡罗变体q-GRFs,它依赖于所谓的加强随机游走,旨在优化GRFs的方差。作者希望本文能推动图随机特征理论的发展。
|
