本文提出了一种新的图随机特征(GRFs)机制,可用于构建图节点上定义的几种重要核(特别是正则化拉普拉斯核)的无偏随机估计量。与非图核的常规随机特征一样,它们可以扩展基于图的核方法以处理更大的网络。更重要的是,即使对较小的图,它们在下游应用中也可以提供可观的计算收益。因此,GRFs解决了图核算法立方时间复杂性的难题。作者提供了GRFs的详细理论分析和广泛的实验评估:从速度测试、相对Frobenius范数误差分析到使用图核的k均值聚类。作者表明,GRFs的计算允许一个非常简单的分布式算法,可应用于特别大的图。作者还介绍了GRFs的一种(仍然无偏的)准蒙特卡洛变体,依赖于所谓的加强随机游走,可用于优化GRFs的方差。作为副产品,作者还获得了一种用于求解具有正和对称矩阵的线性方程组的新方法。
令由行向量组成,其中由下面的算法计算:
初始化: $\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
令是B的独立副本,则有:
该结论可以推广到更一般的正对称矩阵。
其中是对称规范的Laplacian矩阵。
其中的行向量为。
其中。
本文提出了图随机特征(GRFs)的新范式,以无偏、计算高效的方式估计定义在图节点上的各种核。GRFs依赖于在不同节点中启动的随机游走族,在访问的图顶点中存储负载。作者提供了GRFs的详细理论分析和大量实验,包括图上的k均值聚类。GRFs解决了图核算法立方时间复杂性的难题。作者的方法还提供了一种求解具有正对称矩阵的线性方程组的新方法。GRFs的计算非常简单,可以并行化,并且可以轻松地进行分布式实现。作者还引入了GRFs的准蒙特卡罗变体q-GRFs,它依赖于所谓的加强随机游走,旨在优化GRFs的方差。作者希望本文能推动图随机特征理论的发展。
联系客服