前言

這篇是我在閱讀論文:

Defferrard, Michaël, Xavier Bresson, and Pierre Vandergheynst. "Convolutional neural networks on graphs with fast localized spectral filtering." Advances in neural information processing systems 29 (2016).

其中的關鍵部分，關於如何設計Graph上的filter時學習整理的相關內容，因為這部分內容公式推導比較多，且是本論文的主要貢獻，所以單獨摘出。

背景

將CNN推廣到Graph的結構要經過三個過程:

  1. Design of localized convolutional filter on graph
  2. graph coarsening procedure that grpup together similar vertices
  3. graph pooling operation that trades spatial resolution for highter filter resolution

本文主要專注在過程一關於設計graph上的filter的問題。

設計卷積核主要有兩種方式，即spatial approach&spectral approach，但spectral有一些前人定義好的Operator，有更完善的數學定義。以下都是基於Spectral Graph theory。

Notation

undirected and connected graph , where is a finite set of vertices, is a set of edges and is a weighted adjacency matrix encoding the connection weight between two vertices. A signal defined on the nodes of graph may be regarded as a vector 𝕟 where is the value of at the node.

Graph Laplacian

where is the diagonal degree matrix with and the normalized definition is:

where is the identity matrix. As is a real symmetric positive semidefinite matrix(半正定矩陣), it has a complete set of orthonormal eigenvectors(正交特征向量), known as the graph Fourier modes, and their associated ordered real nonnegative eigenvalues , identified as the frequencies of the graph.The Laplacian is indeed diagonalized by the Fourier basis such that:

where .

The graph Fourier transform of a signal is defined as:

and its inverse as:

Graph在空間域內無法直接得到好的卷積,在經過傅裡葉變換後,可以在Fourier domain對graph做一些諸如 filtering的操作。

Spectral filtering of graph signals

The convolution oprator on graph is defined in the Fourier domain such that

where is the element-wise Hadamard product. It follows that a signal is filtered by as：

本文的關鍵就在於如何設計這個函數(即filter函數)，文章中作者先是將其設計為non-parametric的模式如下：

the parameter is a vector of Fourier coefficient

而以上的設計存在兩個缺陷: 1. not localized in space 2. their learning complexity is in O(n), the dimensionlaity of the data.

所以作者又提出了一種Polynomial filter:

where the is a vector of polynomial coefficient.

儘管以上的Polynomial方案解決了一些問題，但其在對一個graph signal 做filter時還是會達到O()的複雜度。文章作者又給出了一個Chebyshev expansion(polynomial)來近似上邊的式(2),將複雜度降低至。其公式如下：

其對應到這邊得到的filter with Cheybeshev polynomial:

where the parameter is a vector of Chebyshev coeffcient and 𝕟𝕟 is the Chebyshev polynomial of order evaluated at

這時我們回到我們的原始問題式(1),其可被重寫為:

where is the Chebyshev polynomial of order evaluated at the scaled Laplacian .進一步簡化符號: with and