基于圖割和局部算子的圖子集選取

陳丹冉,王 健

(復旦大學 大數(shù)據(jù)學院,上海 200433)

0 引 言

在統(tǒng)計學、信號處理、計算機視覺等學科中傳統(tǒng)關注的數(shù)據(jù)多為結構化的,如音頻、雷達信號、生物醫(yī)學信號、圖像和視頻等。隨著信息技術的高速發(fā)展,當今社會萬物互聯(lián),數(shù)據(jù)來源分散且多存在于不規(guī)則拓撲結構,如社交網(wǎng)絡[1]、傳感器網(wǎng)絡[2]、生物網(wǎng)絡[3]等。這些網(wǎng)絡結構數(shù)據(jù),大多存在與節(jié)點相關的特征,如社交網(wǎng)絡中用戶的年齡等屬性,傳感器網(wǎng)絡中的各個傳感器的觀測值,這些節(jié)點數(shù)據(jù)可以視作一種圖上的信號。對于分布式的網(wǎng)絡信號,傳統(tǒng)的信號處理理論無法很好地描述其節(jié)點之間的相互關系,因此,圖信號處理(Graph Signal Processing,GSP)應運而生,通過引入圖上的傅里葉變換(Graph Fourier Transform,GFT),將時間信號推廣至基于圖網(wǎng)絡表征非規(guī)則域中的信號。

圖網(wǎng)絡的拓撲結構復雜多變,同時,較高的數(shù)據(jù)維度會使得計算復雜度增加,故在資源有限的情況下,能夠直接觀測到的圖信號個數(shù)變得十分有限。如何利用少部分最具有信息量的節(jié)點的觀測值與圖結構信息去準確快速地估計未觀測的節(jié)點信號,進而為圖結構數(shù)據(jù)的傳輸處理提供高效的技術支撐,是圖信號處理中的核心問題,即圖信號采樣與重構。該問題依賴于一個隱含假設——信號的平滑性,即圖上鄰近的節(jié)點具有相似的值。通常,圖信號處理中的平滑性假設采用圖傅里葉基的(近似)帶寬限制(Band-limitedness)形式,從而使得原始信號能夠被部分采樣信號重構。

目前,對圖信號采樣與重構的研究大致可分為局部觀測[4-5]與圖子集選取(Graph Subset Selection,GSS)[1,6-14]兩類。前者利用采樣節(jié)點鄰域的聚合觀測值去重構信號,更適用于存在聚集性質的圖結構。圖子集選取則從圖節(jié)點集中采樣最具有信息量的節(jié)點子集,將這些節(jié)點的(帶噪)信號值作為觀測值去重構原始信號,可應用于多個領域,如環(huán)境監(jiān)測[15]、半監(jiān)督節(jié)點分類[16]、矩陣補全[17]等。

由于圖結構具有離散性質,圖子集選取本質是一個組合優(yōu)化問題,已被證明為NP難[18],可以近似求解。現(xiàn)有方法可以歸為兩類：(1)隨機算法;(2)確定性算法[19]。前者通過在圖節(jié)點集上定義一個概率分布函數(shù),依據(jù)分布隨機地采樣節(jié)點[6-8]。后者則通過優(yōu)化預先定義的損失函數(shù),尋找最優(yōu)采樣集[9-14]。研究表明,在采樣點數(shù)相同的情況下,隨機算法的重構效果很難超過確定性算法[7]。雖然確定性算法效果更優(yōu),現(xiàn)有方法大多從譜域設計優(yōu)化準則,并未考慮節(jié)點域內采樣集節(jié)點的距離關系,而在平滑假設下,采樣距離相近的點對重構效果帶來的增益可能十分有限。同時,這類算法通常使用貪心優(yōu)化,即每一步迭代時,選擇最大化或最小化目標函數(shù)的局部最優(yōu)點。然而,貪心方法可能會陷入局部最優(yōu)解,并不能保證全局最優(yōu),并且由于采樣點的選擇依賴前序已采樣節(jié)點,采樣只能串行執(zhí)行,在處理大規(guī)模圖時效率較低。

針對以上不足,該文提出以圖割(Graph Cut) 的視角建模圖子集選取問題,既考慮了采樣集節(jié)點在節(jié)點域和譜域的信息,又可實現(xiàn)一次性采樣,并行運行。具體地,首先利用局部算子構建一個新的內積完全圖,再利用譜聚類算法生成標準圖割,得到節(jié)點集的劃分,使得同一子集內的節(jié)點距離盡可能近,不同子集間的節(jié)點距離足夠遠;其次,在每個子集內依據(jù)稀疏性度量采樣最優(yōu)節(jié)點,即可組成最終的采樣集。在多種圖上的實驗結果表明,提出的算法(Cut Sampling)優(yōu)于現(xiàn)有文獻中的幾種代表性算法。

該文的貢獻總結如下：

(1)提出利用圖割為圖子集選取劃分采樣可行集,利用局部算子構建內積完全圖,可控制采樣集節(jié)點的間隔距離,同時結合了譜域的局部性;

(2)提出的算法不需要貪心優(yōu)化,可以在采樣步驟并行運行,具有可擴展性;

(3)相比于幾種現(xiàn)有文獻中的代表性算法,提出的方法實驗效果更優(yōu)或相近。

1 相關研究

現(xiàn)有的圖子集選取方法可分為兩類：隨機算法和確定性算法。隨機算法根據(jù)定義的概率分布在節(jié)點集隨機采樣從而生成采樣集。研究表明,獨立于圖結構的均勻分布,當采樣足夠多個節(jié)點時,對于Erd?s-Rényi圖(ER圖)可高概率實現(xiàn)完美重構[1],而非均勻的隨機采樣則根據(jù)基于圖結構的節(jié)點重要性設計概率分布[7-8]。雖然與圖結構無關的隨機采樣計算高效,利用壓縮感知中約束等距性質(Restricted Isometry Property,RIP)的理論研究表明,在采樣點數(shù)相同的情況下,與圖結構相關的隨機采樣方法效果更優(yōu)[7],文獻[6]展示了具體對比。同時,隨機方法很難保證采樣集中的節(jié)點距離足夠遠,而在圖信號的平滑假設下,距離相近的采樣點帶來的信息增益可能有限[12]。故該文沿確定性算法展開研究。

確定性算法大多為譜方法,通過松弛優(yōu)化[20]或貪心優(yōu)化去最大化或最小化某種定義的損失函數(shù)。例如基于實驗設計的優(yōu)化準則,E-optimal[1],A-optimal和D-optimal[9]等。雖然這類貪心算法通常可以獲得較好的重構效果,但依賴特征分解,計算復雜度較高。為避免特征分解,可以對譜域優(yōu)化準則做近似處理,如MaxCutoff[10]利用圖譜代理 (Graph Spectral Proxies),去近似最大化截止頻率;Fen Wang等[21]利用諾伊曼級數(shù)(Neumann Series)優(yōu)化A-optimal準則等。另有一些方法雖無法避免準備工作階段的特征分解,但將貪心算法中加入一個節(jié)點后比較全局指標,轉換為利用每個節(jié)點的增量誤差衡量節(jié)點質量,可以避免節(jié)點選擇步驟的特征分解,如利用QR分解[13],借鑒壓縮感知中正交匹配追蹤算法的思路,通過投影算子定義殘差[14]等。但上述方法大多只實現(xiàn)了頻域內采樣的局部性,并沒有考慮圖拓撲結構以及采樣節(jié)點的空間關系。還有些確定性算法只考慮節(jié)點域信息,如傳感器設置方法[22],可有效避免對圖傅里葉基的依賴。

近年來,結合譜域與節(jié)點域信息的方法被相繼提出[11-12],Jayawant等[11]提出一個兩步算法,首先尋找和已采樣節(jié)點距離足夠遠的節(jié)點可行集,其次在可行集內根據(jù)準則貪心尋找最優(yōu)點。Sakiyama等[12]想法類似,利用定義在節(jié)點域的局部算子[23]合并上述兩步,提出Ed Free算法。同時,Sakiyama等還證明了許多確定性算法可用局部算子統(tǒng)一表示。但是這些算法同樣使用貪心優(yōu)化去一個個選擇最優(yōu)節(jié)點,串行采樣,效率較低。鑒于結合節(jié)點域與譜域的圖子集選取方法展示出優(yōu)秀的節(jié)點選擇能力,同時考慮到局部算子的泛化性及其可以結合兩域信息的特性,該文沿用局部算子并從節(jié)點距離出發(fā),提出用新的視角圖割[24]去建模圖子集選取問題,可在一定程度上克服現(xiàn)有譜域貪心算法的不足。

2 預備知識

2.1 圖信號處理

(1)

GFT之所以可利用LG的特征分解定義,可以從LG的二次型理解,它可表示為圖上有邊相連的節(jié)點信號值變化的加權平方和,反映了圖信號的平滑程度。

(2)

將ui視為圖上的信號,則當λi越小,ui會越平滑。傳統(tǒng)離散信號處理中,隨時間變化越緩慢的信號頻率越低,類似地,沿圖中邊變化越平滑的圖信號頻率越低,因此GFT可將特征值看作信號的頻率,低頻代表圖信號沿邊的變化平滑,高頻代表變化劇烈。

在圖信號處理中,通常假設圖信號滿足基于圖結構的某些條件,例如平滑、帶限等。該文研究帶限圖信號,定義如下：

(3)

局部算子(Localization Operators)是傳統(tǒng)信號處理中的平移算子在圖信號處理領域的拓展,可以同時結合節(jié)點域和譜域信息,定義如下：

定義2(局部算子[23])：?n∈{0,1,…,N-1},節(jié)點i∈V處局部算子的第n個分量元素定義如下：

(4)

其中,(*)表示圖卷積,g為譜域核,δi為節(jié)點i處的脈沖信號。局部算子的矩陣形式如下：

Tg=[Tg,0,Tg,1,…,Tg,N-1]=

(5)

常用譜域核有熱核g(λi)=e-πλi,此時Tg,i具有圍繞節(jié)點i移動窗口的作用[23]。另一常用的為理想核,當i

2.2 問題形式

圖子集選取問題可分為兩步：采樣和重構。假設想要找到一個大小為M的采樣集M?V,其中M=(M0,M1,…,MM-1)表示采樣序列,并且 Mi∈{0,1,…,N-1}是非重復的。只有采樣節(jié)點的信號值是可以觀測到的。采樣矩陣Ψ：RNRM定義如下：

(6)

令w∈RM為觀測中引入的噪聲,假設服從i.i.d.高斯分布,則采樣信號為xM=Ψx,觀測模型為yM=Ψx+w,對于帶限圖信號,觀測模型可寫作：

(7)

當采樣集M固定后,真實信號值可由最優(yōu)線性估計(Best Linear Unbiased Estimation)[25]重構得到：

(8)

2.3 圖 割

圖割是對圖節(jié)點集的劃分,標準圖割(Normalized Graph Cut,N-CUT)是一類經(jīng)典的圖割,通常具有優(yōu)秀的聚類效果,其定義如下：

定義3(標準圖割(N-CUT)[24])：圖G=(V,ε,W)大小為M的標準圖割為節(jié)點集V的一個分割{A1,A2,…,AM},使得下式目標函數(shù)最小化。

(9)

N-CUT通常作用于相似性圖,用于將節(jié)點集劃分為多個簇,使得簇間節(jié)點具有低相似度,簇內節(jié)點具有高相似度。這是一個NP難問題,可以用譜聚類算法放縮求解[26]。

3 Cut Sampling算法介紹

3.1 信號重構

由公式(8),利用帶理想核的局部算子,重構信號可表示為局部算子的加權線性組合形式：

TVM(TMM)?yM=

(10)

其中,c=(TMM)?yM。

由于信號重構本質是利用采樣值去插值估計未觀測值,由公式(10),未觀測節(jié)點的值亦可以由采樣節(jié)點處Tg,i的帶權線性組合插值得到。故Tg,i的非零分量,即覆蓋區(qū)域,可被視作節(jié)點i對重構信號有貢獻的節(jié)點區(qū)域。為使得重構誤差盡可能小,最優(yōu)采樣集應具有盡可能大的覆蓋區(qū)域,即單個采樣節(jié)點的覆蓋區(qū)域盡可能大,同時,采樣節(jié)點間的覆蓋區(qū)域交集盡可能小。

具體地,‖Tg,i‖1可表示節(jié)點i的信號覆蓋域,內積〈|Tg,i|,|Tg,j|〉可代表節(jié)點i和j信號覆蓋區(qū)域的交集大小。例如,若〈|Tg,i|,|Tg,j|〉=0,則表示節(jié)點i和j的信號覆蓋域無交集。

基于上述性質,該文利用局部算子的內積構建一張完全圖,邊權為信號覆蓋域交集大小的度量,并在此基礎上提出一個兩步的圖子集選取算法Cut Sampling：(1)N-CUT聚類;(2)在每個子集內根據(jù)稀疏性準則選擇最優(yōu)點。

完整算法流程如圖1所示。

圖1 Cut Sampling算法流程

3.2 圖割聚類

對于原始圖G=(V,ε,W),算法首先通過構建一個對應的完全圖Q=(V,ε'),以邊權去度量圖上任意兩個節(jié)點的空間距離關系。具體地,圖Q中的邊權為相連兩個節(jié)點的局部算子的內積。

(11)

由前述局部算子的性質可知,圖Q即為原始圖中節(jié)點距離的度量圖,可通過求解N-CUT將節(jié)點集按節(jié)點的距離關系劃分為指定個數(shù)簇。由公式(9),圖Q的N-CUT的最小化目標函數(shù)可寫作：

(12)

算法1：N-CUT譜聚類算法[26]。

輸入：距離圖Q=(V,ε'),采樣個數(shù)M,特征向量矩陣U;

輸出：節(jié)點子集{S1,S2,…,SM}。

1.取U的前M列的第i行,zi=UiM∈RM,?i∈{0,1,…,N-1};

3.3 簇內采樣

圖割步驟為后續(xù)采樣劃分了可行集范圍。由于圖割已控制不同子集間的點距離足夠遠,為了選出最具信息量的采樣集,算法Cut Sampling第二步在各子集Si內分別選取最有代表性的點,共同組成最終的采樣集。具體地,定義如下采樣準則,其中Tg,j表示節(jié)點j處的局部算子：

(13)

Ed Free[12]中利用了局部算子的1范數(shù),而最大化1范數(shù)等價于尋找覆蓋域最大的信號節(jié)點。該文在此基礎上增加了分母對2范數(shù)的限制,這也是一種稀疏性度量[8]。從信號重構的角度不難理解,由于信號重構本質是對觀測值的插值,過于稀疏的局部算子代表當前節(jié)點可能與其他節(jié)點有較小的關聯(lián),不具有代表性,可能帶來較大的重構誤差。算法希望采樣信號在具有較大覆蓋域的同時,不會過于稀疏,即避免非零分量過于集中導致難以提供足夠信息。例如,假設Tg,1=[1,0,0,…,0],Tg,2=[1/2,1/2,0,…,0],則Tg,1和Tg,2的1范數(shù)均為1,但Tg,2的2范數(shù)更小。由公式(13),該文的采樣準則將選擇Tg,2而非更稀疏的Tg,1。完整算法總結如算法2所示。

算法2：Cut Sampling算法。

輸入：圖G=(V,ε,W),采樣個數(shù)M,特征向量矩陣UVK,局部算子Tg;

輸出：采樣集M?V,|M|=M。

3.在各節(jié)點子集Si中,選擇最優(yōu)節(jié)點,?i=1,2,…,M;

4 數(shù)值實驗

4.1 實驗設置

實驗利用GSPBOX[27],在如下四類圖上對比不同算法的重構效果：

(1)隨機Sensor圖：為帶權稀疏圖;

(2)Minnesota交通圖：為等權重圖,邊權均為1;

(4)基于Erd?s-Rényi模型的隨機圖(ER 圖)：邊的連接概率p分別設置為0.05、0.15和0.5。

將Cut Sampling與下列三種方法進行比較：

(1)隨機采樣[7]：概率分布為均勻的;

(2)MinSpec[1]：確定性算法,貪心優(yōu)化E-Optimal準則,每次迭代需特征分解;

(3)Ed Free[12]：確定性算法,無需特征分解,利用局部算子,考慮了節(jié)點間的空間關系。

Cut Sampling與Ed Free算法中的局部算子均使用熱核函數(shù)g(λ)=e-aλ,其中a=vpepmpk/λmax,v∈R+為可調參數(shù),設置為75,pe=|ε|/N為連邊概率,pm=M/N為采樣比例,pk=K/N為帶寬。

4.2 采樣集比較

圖2展示了N=500的Sensor圖上四種算法的采樣結果,圈出節(jié)點構成采樣集,大小為M=15。如圖2(a)和圖2(b),隨機采樣和MinSpec生成的采樣集中,節(jié)點距離可能很近,分布并不均勻。這兩種方法在采樣時,隨機或根據(jù)譜域準則優(yōu)化,并未考慮圖的拓撲結構與節(jié)點間的位置關系,這也導致了較大的重構誤差。Ed Free和Cut Sampling在采樣時都考慮了節(jié)點的位置關系,最終的采樣集分布較為均勻,采樣節(jié)點間保持了一定距離,如圖2(c)和圖2(d)所示。同時,這兩種方法都利用了局部算子,可以觀察到采樣集有部分重合。

圖2 隨機Sensor圖的采樣節(jié)點集

4.3 重構誤差比較

圖3展示了四種圖場景下,四種算法的重構誤差隨采樣集大小的變化。實驗通過計算重構信號與原始信號的均方誤差(Mean Squared Error,MSE)來評價重構效果。為了獲得相對穩(wěn)定的實驗結果,對于每張圖,實驗均生成100次信號,并取均方誤差的平均值。評價指標如下：

圖3 重構誤差MSE隨采樣集大小M的變化(平均100次)

(14)

其中,x'表示重構信號。

實驗結果表明,該算法在幾乎所有場景下重構效果最優(yōu),算法在四種圖上都取得了最小或與其他方法接近的重構誤差。特別地,在Sensor圖和Minnesota圖上,Cut Sampling穩(wěn)定優(yōu)于其他三種方法。對于BA圖,當采樣集足夠大時,Cut Sampling效果更好。對于ER圖,當連邊的概率較小時,Cut Sampling重構效果接近其他方法,隨著連邊概率提高,Cut Sampling相比于Ed Free的提升也明顯增加。

同時,可以觀察到,對于考慮了圖拓撲結構的Cut Sampling和Ed Free,這兩種方法的重構表現(xiàn)基本優(yōu)于沒有考慮節(jié)點位置關系的隨機采樣和MinSpec,特別是在Sensor圖和Minnesota圖上。這也反映了將圖拓撲信息與頻域信息相結合,可有效提高采樣算法的重構效果。

5 結束語

該文提出了一種兩步圖子集選取方法,先圖割聚類,再簇內采樣。首先利用局部算子的內積生成一張度量節(jié)點空間距離的完全圖,再利用譜聚類算法求解該圖的N-CUT,得到節(jié)點集依距離的劃分。最后,在各個子集內,根據(jù)局部算子的稀疏性準則,分別選擇最優(yōu)點,組成最終的采樣集。相比于大多數(shù)譜域算法,該方法結合了頂點域的空間信息去控制采樣集內節(jié)點的距離,使得采樣集分布相對均勻。同時,區(qū)別于常見的貪心優(yōu)化框架,該文利用圖割實現(xiàn)采樣步驟可以并行選擇全部節(jié)點,具有一定可擴展性。在多種圖場景下與多種代表性算法相比,該方法能達到最優(yōu)或接近的效果。

考慮到譜聚類算法的計算復雜度較高,如何更加高效準確的聚類是未來的一個研究方向。同時,對該算法進一步的理論分析也是未來工作之一。