Graph上的dirichlet energy有什么意义?

Graph上的dirichlet energy有什么意义?

刚好之前在看这块,没大佬来就冒充一下大佬了,有错记得指教下_(:з」∠)_

函数的光滑程度实际上指高低频成分如何,高频成分越多函数变化得越剧烈。另一角度,对 ,要描述函数在一段区间内的震荡程度通常用Lipschitz约束:

上式只衡量了固定一段区间 内的变化剧烈程度,若想要衡量整个函数,自然想到在定义域上分割多个区间以后求和。而当 时,划分求和取极限变积分就是其导数,且因 而处处存在。因此衡量函数的变化剧烈程度可以是这个:

用能量的观点来看,实际上就是梯度的norm而已,很符合直觉 |・ω・`)。更一般地你也可以用其他形式的norm,比如L2 norm那不就是:

假设你已经知道了graph的Laplacian matrix的推导,那用graph上的梯度不难推出graph的Dirichlet energy:

所以为啥谱聚类用的是这坨东西,因为要用图的低频成分逼近数据呀( ’ - ’ * )。又Laplacian matrix的特征值对应图的频率,特征向量对应这个频率的Fourier base,所以去求Laplacian matrix最小的前几个特征值对应的特征向量,就把节点用低频成分表示了 (ˊvˋ*)

这跟把时域波形高频成分扔了得到了更平滑的波形是一个道理(*╹▽╹*)

ICLR2020的GraphZoom就把这招用得那叫一个暴力,因为求Dirichlet energy实际上等价于求Laplacian线性方程组,他们做spectral coarsening的时候就不直接用Laplacian matrix的SVD这么大计算量了,而用Gauss-Seidel迭代求方程组,其实就等价于做节点聚类。在embedding refinement的时候加入了 这项做优化得到那条解析式反推回去,无敌。

为啥要尽量让信号smooth当然是为了不要over-fitting鸭 (╯ ̄Д ̄)╯╘═╛

不然为啥loss function里常常会有个L2 regularization鸭 (╯ ̄Д ̄)╯╘═╛