论文解读《The Emerging Field of Signal Processing on Graphs》

---

Paper Information

---

Abstract

　　The emerging field of signal processing on graphs merges algebraic and spectral graph theoretic concepts with computational harmonic analysis to process such signals on graphs.

　　图上信号处理的新兴领域，将代数和谱图理论的概念与计算谐波分析相结合，以处理图上的信号。

　　本文将阐述该领域上的一些挑战，以及定义在  graph spectral domains  上的一些方法，这些方法和经典的 frequency domain  相似。本文同时还点明了在处理 graph signal 融合使用 irregular data of graph 的重要性（每每看论文都出现结合结构特性，但并没有有人能完全说清楚）。然后介绍一些 common operator ，比如说  filtering、translation、modulation、dilation、downsampling to the graph setting 。对已经提出的   localized, multiscale transforms  用于提取图数据的高维特征做了总结。

---

1 Introduction 

• 图中每条边的权重，经常表示为两个顶点之间的相似度。对于节点之间的连接性以及权重大小，一般为数据本身就有的，如社交关系，另外一种为自己根据需求构建的，比如使用KNN 构建权重矩阵 $W$。这在本博客《谱聚类原理总结》已经做了详细介绍。
• 这里相似性通常和距离成反比，采用聚类的思想：距离较远的两个点之间的边权重值较低，而距离较近的两个点之间的边权重值较高。
• graph signal：The data on these graphs can be visualized as a finite collection of samples, with one sample at each vertex in the graph. Collectively, we refer to these samples as a graph signal.示例： Fig. 1.

　　　　

1.1 The Main Challenges of Signal Processing on Graphs

• 目前的研究现状：使用  wavelet, time-frequency, curvelet and other localized transforms 可以很好的将 Euclidean space 上的高维不同类数据区分开来，但对 non-Euclidean space 上的数据却无有效手段。
• 传统的   signal processing techniques  忽略了 irregular data domain  。

 　　Challenges on Graph:

• The unavoidable fact is that weighted graphs are irregular structures that lack a shift-invariant notion of translation.
  
• 平移不变性（translation invariance）：在欧式空间中，平移是一种几何变换，表示把一幅图像或空间中的每一个点在相同方向移动相同距离。用基础的分类结构比如 ResNet、Inception 给一只猫分类时，无论猫怎么扭曲、平移，最终识别出来的都是猫，输入怎么变形输出都不变这就是平移不变性，网络的层次越深这个特性会越明显。
  
• 平移可变性（translation variance）：针对目标检测的，比如一只猫从图片左侧移到了右侧，检测出的猫的坐标会发生变化就称为平移可变性。当卷积网络变深后最后一层卷积输出的  feature map  变小，物体在输入上的小偏移，经过 $N$ 层  pooling  后在最后的小 feature map 上会感知不到，这就是为什么  R-FCN  原文会说网络变深平移可变性变差。
• CNN 无法处理 Non Euclidean Structure 的数据，通俗理解就是在拓扑图中每个顶点的相邻顶点数目都可能不同，那么当然无法用一个同样尺寸的卷积核来进行卷积运算。

• Tramsform thr spatial domain data into spectral domain date.$F\left(\lambda_{i}\right)=\hat{f}\left(\lambda_{i}\right)=\sum \limits _{i=1}^{N} f(i) u(i)$
• We need a method to generate a coarser version of the graph that somehow captures the structural properties embedded in the original graph.
• We intuitively downsample a discrete-time signal by deleting every other data point,the process is as Fig.1.

　　处理数据域的不规则性、图结构，在之前提到的应用中，可以表示很多顶点的特征。为了能很好地对数据的尺度进行缩放，对于图信号的处理技术应该使用局部操作，通过对每个顶点，计算顶点的邻居，或是和它很近的顶点的信息。

 　　  The overarching challenges of processing signals on graphs:

• 1. How to construct a weighted graph that captures the geometric structure of the underlying data domain;
  2. Incorporating the graph structure into localized transform methods;
  3. Leveraging the invaluable intuitions in Euclidean domains to deal with processing signals on graphs;
  4. Consider to improve the efficient of  localized transforms.

---

2 The graph spectral domain

2.1 Weighted Graphs and Graph Signals

　　Defitions of graph：

• • Graph type：undirected, connected, weighted graph  $\mathcal{G}=\{\mathcal{V}, \mathcal{E}, \mathbf{W}\} $,
  • Vertice set：a finite set of vertices  $\mathcal{V}$  with  $|\mathcal{V}|=N$ ,
  • Edge set：a set of edges  $\mathcal{E} $,
  • Weighted adjacency matrix：Symbol as  $\mathbf{W}$ . If there is an edge  $e=(i, j)$  connecting vertices  $i$ and  $j$ , the entry  $W_{i, j}$  represents the weight of the edge; otherwise,  $W_{i, j}=0$ .
  • SSC（连通分量）：If the graph  $\mathcal{G}$  is not connected and has  $M$  connected components $ (M>1)$ , we can separate signals on  $\mathcal{G}$  into  $M$  pieces corresponding to the  $M$  connected components, and independently process the separated signals on each of the subgraphs.

 　　According the need of application,a common way to construct a weight matrix is full connect which for construct a symmetric matrx.More detail you can refer to my blog 《谱聚类原理总结》.

　　　　$W_{i, j}=\left\{\begin{array}{ll}\exp \left(-\frac{[\operatorname{dist}(i, j)]^{2}}{2 \theta^{2}}\right) & \text { if } \operatorname{dist}(i, j) \leq \kappa \\0 & \text { otherwise }\end{array}\right.$

　　Where, $ dist(i, j)$ can be Euclidean distance between two vector $i$ and $j$. two leanable parmeter $\theta$ and $\kappa$.

　　Another way two generate a weight matrix is KNN .

　　$f: \mathcal{V} \rightarrow \mathbb{R}$ defined the value of verticles of the graph,the $i^{t h}$  component $f_i$ mean the $i^{t h}$ vertices value .

2.2  The Non-Normalized Graph Laplacian

　　The non-normalized graph Laplacian, also called the combinatorial graph Laplacian, is defined as

　　　　$L:=\mathbf{D}-\mathbf{W}$

　　Where

• • $D$ is degree matrix which a diagonal matrix ;
  • $\mathbf{W}$ is weighted adjacency matrix .

 　　The graph Laplacian matrix is define as :

　　　　$(L f)(i)=\sum \limits _{j \in \mathcal{N}_{i}} W_{i, j}[f(i)-f(j)]$

　　If you want to know the background physical meaning of this Eq, you can refer to my another blog 《图神经网络基础二：谱图理论》.

　　Where 

• • The neighborhood  $\mathcal{N}_{i}$  is the set of vertices connected to vertex  $i$  by an edge. More generally, we denote by  $\mathcal{N}(i, k)$  the set of vertices connected to vertex  $i$  by a path of  $k$  or fewer edges.（邻居定义为小于等于k-step可到达的点）

 　　Due to graph Laplacian matrix $L$ is a real symmetric matrix ,so it can do Laplace Spectral Decomposition as the following:

　　　　$L \mu_{k}=\lambda_{k} \mu_{k}$

 　　Because $L$ is real symmetric matrix ,so it can be transformed as：

　　　　$L=U \Lambda U^{-1}=U \Lambda U^{T}$

 　　Some note in here：

• • Orthonormal eigenvectors  $\left\{\mathbf{u}_{l}\right\}_{l=0,1, \ldots, N-1}$ ;
    
  • Non-negative eigenvalues $\left\{\lambda_{l}\right\}_{l=0,1, \ldots, N-1}$ ;
  • $\Lambda  $ is consist of the non-negative eigenvalues that are ordered as                                                                                                $0=\lambda_{0}<\lambda_{1} \leq \lambda_{2} \cdots \leq \lambda_{N-1}:=\lambda_{\max }$
  • We denote the entire spectrum by $\sigma(L):=\left\{\lambda_{0}, \lambda_{1}, \ldots, \lambda_{N-1}\right\}$ .