Rational Neural Networks for Approximating Graph Convolution Operator on Jump Discontinuities
Rational Neural Networks for Approximating Graph Convolution Operator on Jump Discontinuities
复制标题
DOI：
10.1109/icdm.2018.00021
复制
发表时间：
2018-11
期刊：
影响因子：
--
通讯作者：
Zhiqian Chen;Feng Chen;Rongjie Lai;Xuchao Zhang;Chang-Tien Lu
中科院分区：
文献类型：
--
作者：
Zhiqian Chen;Feng Chen;Rongjie Lai;Xuchao Zhang;Chang-Tien Lu
对于节点级图编码，最近一种重要的最先进的方法是图卷积网络（GCN），它很好地融合了谱域的局部顶点特征和图拓扑。然而，目前的研究存在以下几个缺点：(1)图cnn依赖于切比雪夫多项式近似，导致跳变不连续处的振荡近似；(2)提高Chebyshev多项式的阶数可以减少振荡问题，但也会带来难以承受的计算成本；(3)切比雪夫多项式需要Ω（poly(1/ε)）次来近似|x|这样的跳跃信号，而有理函数只需要O（poly log(1/ε)）次。然而，在不增加计算复杂度的情况下应用有理近似是非常重要的。利用有理逼近法在图信号恢复中的优越性。提出了将有理函数与神经网络相结合的RatioanlNet。我们证明了特征值的有理函数可以重写为图拉普拉斯函数，从而避免了与特征向量矩阵的乘法。重点分析了图卷积运算的逼近性，提出了一个图信号回归任务。在图信号回归任务下，采用图傅里叶变换可以显著降低其时间复杂度。为了克服神经网络模型的局部最小值问题，采用松弛Remez算法对权重参数进行初始化。分析了比率网络和多项式方法对跳变信号的收敛速度，为其提供了理论保证。大量的实验结果表明，我们的方法可以有效地表征跳跃不连续，在合成图和实际图上都优于竞争方法。
For node level graph encoding, a recent important state-of-art method is the graph convolutional networks (GCN), which nicely integrate local vertex features and graph topology in the spectral domain. However, current studies suffer from several drawbacks: (1) graph CNNs rely on Chebyshev polynomial approximation which results in oscillatory approximation at jump discontinuities; (2) Increasing the order of Chebyshev polynomial can reduce the oscillations issue, but also incurs unaffordable computational cost; (3) Chebyshev polynomials require degree Ω(poly(1/ε)) to approximate a jump signal such as |x|, while rational function only needs O(poly log(1/ε)). However, it is non-trivial to apply rational approximation without increasing computational complexity due to the denominator. In this paper, the superiority of rational approximation is exploited for graph signal recovering. RatioanlNet is proposed to integrate rational function and neural networks. We show that the rational function of eigenvalues can be rewritten as a function of graph Laplacian, which can avoid multiplication by the eigenvector matrix. Focusing on the analysis of approximation on graph convolution operation, a graph signal regression task is formulated. Under graph signal regression task, its time complexity can be significantly reduced by graph Fourier transform. To overcome the local minimum problem of neural networks model, a relaxed Remez algorithm is utilized to initialize the weight parameters. Convergence rate of RatioanlNet and polynomial based methods on a jump signal is analyzed for a theoretical guarantee. The extensive experimental results demonstrated that our approach could effectively characterize the jump discontinuities, outperforming competing methods by a substantial margin on both synthetic and real-world graphs.