基于全局采樣集優化的聯合多維度平滑性時變圖信號重構*

陳熠罡，吳贇

（東華大學，上海 201620）

0 引言

隨著圖論研究的深入，以圖為基礎的數據處理逐漸進入各個領域研究人員的視野，進而推動了圖信號處理領域的急速發展。圖信號處理是近年來受到廣泛關注的一個新的研究方向，它主要分析由圖捕獲的不規則域上的信號[1]，并在傳感器網絡[2-3]、機器學習[4-5]、推薦系統[6-7]、生物醫學[8-9]、圖像處理[10-12]等領域中有著優勢地位。

現階段在對圖信號的研究過程中，人們主要使用圖濾波和圖傅里葉變換[1]等方法對單個圖信號進行處理，但此時的圖信號是靜態的圖信號，和現實世界中的圖信號相比不具備時變性。因此，對時變圖信號的研究引發了研究人員的關注。由于采集到的圖信號數據往往具有時變特性，在實際應用中，數據缺失或不正確的問題非常普遍。為了解決相關問題，時變圖信號重構成為實際應用中的一個重要課題。例如，在低成本的傳感器網絡中，如空氣溫度傳感器網絡，由于傳感器故障或通信故障，數據丟失是常見的，此時便需要對時變信號進行重構。

近年來，圖信號數據重構是信號處理領域中的熱門問題。對時變圖信號的研究首次出現在文獻[13]中。文獻[13]在處理時變圖信號的重構問題時提出了兩種方法，一種是批量處理重構，另一種是在線分布式重構。兩種方法的主要思想是先將收集到的圖信號數據按時間順序排列，再對數據進行采樣，并通過采樣數據恢復所有信號數據。文獻[14]采用差分處理方法使得時變圖信號數據具有更好的平滑特性，取得較好的重構效果。文獻[15]利用時變圖信號在空間域和時間域都具有平滑性的特點，提出了基于聯合平滑性的時變圖信號重構算法。但以上3種方法對空時域平滑性的挖掘還不夠深入，并且采樣時均采用隨機采樣方法，采樣節點不具備代表性。

針對以上分析，本文對加權無向圖上的時變圖信號重構展開研究。和常用的隨機采樣不同，本文根據節點的區域關聯性，對圖結構進行分簇，在每個簇內選取具有代表性的節點數據，實現采樣集優化。通常情況下，傳統的時變圖信號重構方法為簇內重構，即對圖結構分簇之后，在每個簇內進行重構，但此時忽略了簇與簇之間邊的權重，重構結果會有很大的誤差。本文采用的重構形式則為全局重構，即在整個圖結構上進行重構。同時，本文對時變圖信號在空時域的特征進行深入挖掘，提出基于全局采樣集優化的聯合多維度平滑性時變圖信號重構算法（Joint Multidimensional Smoothness Time-Varying Graph Signal Reconstruction Based on Global Sampling Set Optimization，JMSR-GSSO-TVGS）。實驗證明，本文的方法能夠得到較好的重構質量。

1 圖信號相關知識

1.1 圖的構成

圖G可以定義為一個三元組(v,ε,W)，其中v和ε分別表示圖中n個節點和e條邊的集合。在連通的無向圖中，對于集合v中任意兩個不同的節點p和q，與每條邊(p,q)∈ε相關聯的是一個權重wp,q，它反映了節點p和節點q之間的相關性或相似性，并且wp,q=wq,p。W是權重矩陣，wp,q是W的一個元素，位于矩陣W的第p行，第q列。通常情況下，若邊(p,q)屬于集合ε，則wp,q>0，否則wp,q=0。時變圖信號數據集X是一個大小為n×m的矩陣，表示的是n個節點在m個時刻的總數據，第i行數據為向量X(i,:)，第j列數據為向量X(:,j)。xi,j是位于矩陣X的第i行、第j列的一個元素，表示圖G的第i個節點在第j個時刻獲取到的信息。

1.2 圖拉普拉斯矩陣

圖拉普拉斯矩陣在圖信號處理領域占據著重要的位置。在一個加權無向的圖結構圖G中，圖拉普拉斯矩陣定義為：

式中：矩陣K是對角矩陣，矩陣K的第i個對角元素是v節點i的度數，因此矩陣K被稱為圖G的度矩陣。由于時變圖信號包含空間域和時間域兩方面的信息，所以時變圖信號的底層圖結構可以看作聯合時間頂點圖，如圖1 所示。圖1（a）是信號的空間域拓撲圖G，圖1（b）是長度為T的時間域循環圖，圖1（c）是聯合時間頂點圖J。其中，圖1（c）是由圖1（a）和圖1（b）的笛卡爾乘積生成的圖。圖1（a）和圖1（b）的拉普拉斯矩陣分別用LG，LT表示。

圖1 聯合時間頂點圖的生成

2 JMSR-GSSO-TVGS 算法

在圖信號領域中，時變圖信號重構是研究的重點。在真實世界中，圖信號往往會隨著時間的變化而變化，因此在圖信號采樣過程中經常會出現數據錯漏的現象。為了更好地重構時變圖信號，本文提出了一種JMSR-GSSO-TVGS 算法。該算法在對信號數據進行優選的基礎上，進一步挖掘了時變圖信號在空時域的多維平滑性，使時變圖信號的重構結果更加精確。

2.1 采樣集優化

對圖信號數據進行重構之前需要對信號數據進行采樣。在以往的工作中通常使用隨機采樣，隨機采樣雖然可以獲取一定數量的采樣數據，但是有很大的弊端。對于大規模的圖，由于節點與節點之間的權重不同，圖結構往往會劃分為幾個區域，不同區域的節點數據會有些許差別，如果使用隨機采樣，很有可能采集到同一個區域上的節點數據，此時采集到的數據就不具有代表性，勢必對圖信號的重構結果產生影響。鑒于此，有必要對圖信號的采樣集進行優化處理。

一般情況下，時變圖信號的采樣可以表示為：

式中：Y∈Rn×m為經過采樣的時變圖信號；X為原始的時變圖信號；矩陣O∈Rn×m為采樣算子，在第m個時刻，若節點的數據被采集，則矩陣元素O(n,m)賦值為1，否則為0；○表示哈達瑪積。在實際情況下，噪聲是不可避免的，因此本文在研究時變圖信號重構即通過Y恢復X時，把噪聲納入了考慮范圍，并用矩陣代表噪聲。

因為節點的區域關聯性對空間域采樣有很大的幫助，所以本文根據節點的區域關聯性對采樣集進行優化。本文采用了一種有效的Louvain[16]算法對圖結構進行分簇。Louvain算法是一種社區發現算法，算法目標是優化模塊度（modularity）。模塊度描述了社區內節點的緊密程度，即節點的區域關聯性。分簇結束后，每個簇中的節點有一定的區域關聯性，節點數據會比較相似，此時在每個簇中按相同的比例采取節點，并把該節點在矩陣O的相應位置賦值為1，獲得優化全局采樣算子，進而根據式（2）獲得優化采樣數據。優化采樣數據相較于隨機采樣數據更能代表整個圖結構上數據的總體情況。使用優化的采樣數據，圖信號重構的準確率將大大提升。

2.2 聯合多維度平滑性全局重構

時變圖信號的平滑性對信號重構有很大的幫助。平滑性越大，恢復出來的數據越接近原始數據。由于時變圖信號在空間域和時間域都具有平滑性，并且在空間域和時間域進行差分處理后的時變圖信號具有更好的平滑特性，因此本文采用聯合多維度平滑性的方法對時變圖信號進行全局重構。此方法可以達到很好的重構效果。

在空間域對圖信號做差分處理時，差分算子定義為：

此時差分信號為XDh1=(X(:,2)-X(:,1),X(:,3)-X(:,2),…,X(:,m)-X(:,m-1))。在時間域對圖信號做差分處理時，差分算子定義為：

此時差分信號為Dh2X=(X(2,:)-X(1,:)T,X(3,:)T-X(2,:)T,…,X(n,:)T-X(n-1,:)T)T，(·)T表示矩陣的轉置。

根據時變圖信號總變差的定義[15]，在空間域中，時變圖信號的總變差可以表示為tr(XTLGX)；在時間域中，時變圖信號的總變差可以表示為tr(XLTXT)，tr(·)表示矩陣的跡。每個時刻圖結構上相鄰節點數據差值的絕對值之和即為該時刻圖信號的總變差。將每個時刻圖信號的總變差相加，得到的結果即為時變圖信號的總變差?？傋儾钤叫?，表示時變圖信號越平滑。基于時變圖信號及其差分信號在空間域和時間域中的聯合平滑性，本文建立如下的重構模型：

式中：LG為空間域圖拉普拉斯矩陣；LT為時間域圖拉普拉斯矩陣；α，β，γ，θ>0 均為正則化參數。式（5）中的第2 項表示計算誤差，第2 至第4 項表示時變圖信號各個維度的總變差，總變差越小，表示恢復的時變圖信號越平滑，越符合實際。

為了獲得重構信號X，需要對式（5）進行求解。令式（5）為F(X)，此時F(X)為凸優化問題，可以使用迭代算法獲得最優解。迭代前需要設置最大迭代次數S，迭代步長τ，以及正則化參數α，β，γ，θ。設置完畢后，使用效果優良的譜共軛梯度法[17]來對F(X)進行迭代求解。

每次迭代都需要使用譜共軛梯度算法。該算法的步驟為：第1 步，確定好每次迭代的步長；第2 步，更新下一步的搜索方向。將第k步的搜索方向表示為?X k，第k步的最優步長τ由線性最小化規則決定。線性最小化規則為：

可以通過對式（6）進行求導得到最優迭代步長為：

式中：?F(X)代表F(X)的梯度。?F(X)的計算方法為：

對式（7）進行求解，可以獲得迭代步長：

之后可以開始迭代，迭代過程為：

迭代結束后，將第k步的搜索方向和第k+1 步的梯度進行線性組合，從而更新第k+1 步的搜索方向為：

式中：μ為共軛參數；λ為譜參數。

2.3 算法步驟

根據2.1 節和2.2 節所述內容，本文提出的JMSR-GSSO-TVGS 算法的具體步驟歸納如下。

步驟1：獲取拉普拉斯矩陣?；跁r變圖信號聯合多維度平滑性的概念，得到空間域圖拉普拉斯矩陣LG和時間域圖拉普拉斯矩陣LT。

步驟2：獲取優化全局采樣算子。先對圖結構應用Louvain 社區發現算法進行分簇，采樣時在每個簇中以一定的采樣比例獲得每個采樣節點的位置，匯總每個簇中的采樣節點，獲取優化全局采樣算子O。

步驟3：采樣集優化。根據式（2），使用優化全局采樣算子O從總的圖信號數據中獲得采樣數據，實現采樣集優化。

步驟4：正則化參數優化。先對參數區間進行網格化，然后在網格化后的參數集合中對正則化參數α，β，γ，θ進行窮舉搜索，再使用每一種正則化參數組合通過步驟5～6 進行一次實驗測試，選取重構效果最好的一組作為最優參數組合，確定α，β，γ，θ的值。

步驟5：迭代。首先進行初始化設置。迭代次數s初始化為0，設置差分算子Dh1，Dh2，最大迭代次數S，終止迭代閾值ξ。令初始值X0=0，?X0=-?F(X0)。迭代步驟如下：

（1）根據式（9）確定迭代步長τ；

（2）根據式（11）更新第k+1 步的搜索方向。

步驟6：迭代終止判斷。當k=S或者||?X k||F≤ξ時，迭代結束，同時獲得經過重構后的時變圖信號Xk；反之，則k=k+1，并跳轉到步驟5 繼續迭代重構，直至迭代結束。

若對數據進行隨機采樣，并采用步驟4～6進行重構，則該重構算法為基于聯合多維度平滑性的時變圖信號全局重構算法（Joint Multidimensional Smoothness Time-varying Graph Signal Reconstruction，JMSR-TVGS）。

3 實驗結果分析

本節使用MATLAB 軟件進行仿真實驗。實驗分別研究分析全球海平面氣壓數據[18]和室內分布的53 個傳感器收集的溫度傳感器網絡數據[19]。全球海平面氣壓網絡拓撲圖如圖2（a）所示，溫度傳感器網絡如圖2（b）所示。在采樣過程中，采樣率在集合{10%,20%,30%,40%,50%,60%,70%,80%,90%}中選取。一般情況下，最大迭代次數S設置為2×104，終止迭代閾值ξ設置為1×10-6。經過參數區間網格化之后，正則化參數α，β，γ，θ在集合{1 ×10?3,1 × 10?2,2 × 10?2,5 × 10?2,0.1,0.2,0.5,1,2,5,10,20,50,1 × 102,2 × 102,5 × 102}中進行搜索選取。實驗均重復50 次。本文使用均方根誤差來衡量時變圖信號的重構效果，均方根誤差越小，重構的時變圖信號越接近原始數據。均方根誤差定義為：

圖2 網絡拓撲

式中：X*為重構后的時變圖信號；X為原始的時變圖信號；Nx為時變圖信號的長度。

首先，比較提出的全局采樣集優化重構和傳統的簇內采樣重構的性能。此時簇內重構在每個簇中使用JMSR-TVGS 算法，全局重構使用JMSRGSSO-TVGS 算法。首先使用Louvain 算法將圖結構分簇，其次使用JMSR-TVGS 算法對圖信號進行簇內重構，最后使用JMSR-GSSO-TVGS 算法對圖信號進行全局重構。圖3（a）和圖3（b）分別展示了對于全球海平面氣壓數據和溫度傳感器數據，全局重構與簇內重構結果的誤差對比。在圖3（a）中，當采樣率小于60%時，全局重構信號的誤差小于重構后的簇內信號的誤差，當采樣率等于60%時，兩者逐漸接近。在圖3（b）中，當采樣率小于40%時，全局重構信號的誤差小于重構后的簇內信號的誤差；當采樣率等于40%時，兩者的重構效果逐漸相似。由此可見，和簇內重構相比，在低采樣率時，使用全局重構的JMSR-GSSO-TVGS，重構性能更為優越。

圖3 簇內重構和全局重構實驗結果對比

其次，比較本文提出的基于采樣集優化的聯合多維度平滑性全局重構算法（JMSR-GSSOTVGS）和傳統算法的重構性能。對比的重構算法采用隨機采樣，此類算法有圖總變化量重構算法（Graph-regularization）[14]、Tikhonov 正則化重構算法（Graph-time Tikhonov）[14]、基于聯合平滑性的重構算法（JSR-TVGS）[15]、批量重構算法（BRTVGS）[13]、聯合變差最小化重構算法（JVMR）[15]、基于聯合多維度平滑性的全局重構算法（JMSRTVGS）。全球海平面氣壓數據和溫度傳感器網絡數據的實驗仿真結果分別如圖4（a）和圖4（b）所示。從圖4（a）和圖4（b）中可以看出：

圖4 全局重構實驗結果對比

（1）采樣率越高，獲取的數據信息越多，所提出的算法和其他重構算法的重構誤差越低。同時在相同采樣率下，對采樣集進行優化后，重構的效果更好。例如，在圖4（a）中，當采樣率為40%時，JMSR-TVGS 和JMSR-GSSO-TVGS 的重構誤差分別為0.30，0.28；在圖4（b）中，當采樣率為30%時，JMSR-TVGS 和JMSR-GSSO-TVGS 的重構誤差分別為0.516，0.512。由此可見，本文提出的經過采樣集優化的JMSR-GSSO-TVGS 比沒經過采樣集優化的JMSR-TVGS 重構效果更好。

（2）重構過程中利用的平滑性越多，重構的誤差越小。在重構算法中，Graph-regularization 利用了時變圖信號空間域平滑性，BR-TVGS 利用了差分時變圖信號空間域平滑性，JVMR 利用了時變圖信號空間域平滑性和時間域平滑性，JSR-TVGS利用了差分時變圖信號空間域平滑性和時變圖信號時間域平滑性。本文提出的JMSR-GSSO-TVGS 利用了差分時變圖信號的空間域平滑性和時間域平滑性，以及時變圖信號的空間域平滑性和時間域平滑性。和這些重構算法相比，JMSR-GSSO-TVGS 更充分地利用了空時二維平滑性，獲得了更小的重構誤差。例如，在圖4（a）中，當采樣率為40%時，Graph-regularization、Graph-time Tikhonov、BRTVGS、JVMR、JSR-TVGS 和JMSR-GSSO-TVGS 的重構誤差分別為0.42，0.37，0.31，0.37，0.32 和0.28；在圖4（b）中，當采樣率為30%時，Graphregularization、Graph-time Tikhonov、BR-TVGS、JVMR、JSR-TVGS 和JMSR-GSSO-TVGS 的重構誤差分別為0.574，0.562，0.523，0.535，0.519 和0.512。由此可見，JMSR-GSSO-TVGS 可以取得不錯的重構效果。

綜合兩部分的實驗結果可知，相較于其他重構算法，本文提出的JMSR-GSSO-TVGS 算法重構性能提升較大。

4 結語

本文研究了位于加權無向圖結構上的時變圖信號，提出了基于全局采樣集優化的聯合多維度平滑性重構算法來實現對時變圖信號的重構。首先使用基于圖結構中節點區域關聯性的分簇算法對圖結構進行分簇；其次在每個簇中選取規定采樣比例的節點數據，實現采樣集的優化；最后利用時變圖信號的聯合多維度平滑性進行全局重構。從實驗結果可以看出，基于全局采樣集優化的聯合多維度平滑性重構算法在采樣比例較低時，相較于其他時變圖信號重構算法可以取得較好的重構效果，從而證明了本文所提算法對時變圖信號重構的可靠性。在后續的工作中，將引入時變圖信號的帶限性，進一步改進重構性能。