陳枳扦博士：現(xiàn)任密西西比州立大學(xué)計(jì)算機(jī)系助理教授，專注于圖機(jī)器學(xué)習(xí)及應(yīng)用領(lǐng)域，在譜域視角與不確定性研究方面著力頗深。其研究成果見諸于 AAAI、IJCAI、ACM、ICDM、EMNLP、Computing Surveys、Nature Communication 等。他的科研工作承蒙美國國家科學(xué)基金會(huì)（NSF）及美國農(nóng)業(yè)部（USDA）多個(gè)項(xiàng)目的資助，且榮獲豐田研究院杰出貢獻(xiàn)獎(jiǎng)與 ACM SIGPSATIAL 2020 最佳論文獎(jiǎng)。

張磊博士：于 2024 年畢業(yè)于弗吉尼亞理工后，以助理教授身份加盟北伊利諾伊大學(xué)。他的研究興趣廣泛覆蓋機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘范疇，尤其聚焦于圖神經(jīng)網(wǎng)絡(luò)、圖結(jié)構(gòu)學(xué)習(xí)、雙層優(yōu)化、神經(jīng)架構(gòu)搜索以及社交網(wǎng)絡(luò)挖掘等方面。在 AAAI、ICDM 等頂級(jí)會(huì)議上發(fā)表多篇論文，并于 2023 年夏季斬獲弗吉尼亞理工大學(xué)的 Cunningham Fellowship。

趙亮博士：身為埃默里大學(xué)計(jì)算機(jī)系副教授，他的研究領(lǐng)域橫跨數(shù)據(jù)挖掘、人工智能等多學(xué)科，在圖學(xué)習(xí)領(lǐng)域成果斐然。在 KDD、NeurIPS、AAAI、IJCAI、WWW 等眾多頂級(jí)會(huì)議及期刊上發(fā)表超百篇論文，屢獲殊榮，如 NSF CAREER 獎(jiǎng)、Meta Research 獎(jiǎng)、Amazon Research 獎(jiǎng)等，還榮獲 ICDM 2022 最佳論文獎(jiǎng)、ACM SIGPSATIAL 2022 最佳論文獎(jiǎng)以及 WWW 2023 最佳論文提名等。

圖數(shù)據(jù)學(xué)習(xí)在過去幾年中取得了顯著的進(jìn)展，圖神經(jīng)網(wǎng)絡(luò)（GNN）在此過程中起到了核心作用。然而，不同的 GNN 方法在概念和實(shí)現(xiàn)上的差異，對(duì)理解和應(yīng)用圖學(xué)習(xí)算法構(gòu)成了挑戰(zhàn)。

針對(duì)這一問題，來自密西西比州立大學(xué)，北伊利諾伊大學(xué)和埃默里大學(xué)的學(xué)者通過一系列教程對(duì)此問題展開了討論，這些教程展示在 CVPR 2024、CIKM 2024、SIAM Math and Data Science 2024，以及發(fā)表在 Computing Surveys 的一篇論文: 《Bridging the Gap between Spatial and Spectral Domains: A Unified Framework for Graph Neural Networks》。

論文地址：https://dl.acm.org/doi/10.1145/3627816

問題：統(tǒng)一框架的突破意義何在？

盡管圖神經(jīng)網(wǎng)絡(luò)已經(jīng)在多個(gè)領(lǐng)域展示出了卓越的性能，從化學(xué)分子識(shí)別到社交網(wǎng)絡(luò)分析，從交通網(wǎng)絡(luò)到輸電網(wǎng)絡(luò)，再到大腦網(wǎng)絡(luò)。GNN 也在不同的場景下，用不同的理論和機(jī)制來設(shè)計(jì)新的圖神經(jīng)網(wǎng)絡(luò)，例如 Heat diffusion, page rank, random walk, attention model, ARMA, low-pass filtering。雖然展現(xiàn)了 GNN 和很多不同理論工具的連接性，但這也加劇了 GNN 領(lǐng)域的分裂。這些方法因?yàn)榧庇诓煌碚?，無法進(jìn)行理論上直接的比較。

Part 1: 圖學(xué)習(xí)理論框架的現(xiàn)狀

目前，圖神經(jīng)網(wǎng)絡(luò)（GNN）涵蓋了多種模型和層的類型，但總體可以分為空域（spatial）圖模型和頻域（spectral）圖模型。針對(duì)這些模型，不少研究者嘗試提出通用框架，以便在同一框架下對(duì)不同模型進(jìn)行分析和比較。然而，這些框架主要集中于空域圖模型。值得注意的是，有一類研究從統(tǒng)一的出發(fā)點(diǎn) —— 即模型的表達(dá)能力（Expressive Power）—— 對(duì)空域和頻域圖模型進(jìn)行了分析。盡管如此，空域和頻域圖模型在表達(dá)能力的定義上存在差異，其分析結(jié)論和設(shè)計(jì)建議既有共通之處，也各有不同，同時(shí)兩者均存在一定的局限性。

Part 2: 圖卷積

圖卷積可以通過譜圖理論（Spectral Graph Theory）中的圖傅里葉變換（Graph Fourier Transform）和卷積定理（Convolution Theorem）來理解。

圖傅立葉變換：圖的結(jié)構(gòu)通過圖拉普拉斯矩陣（Graph Laplacian）來表示。拉普拉斯矩陣 L 可以進(jìn)行特征值分解：，其中 U 是特征向量矩陣，∧ 是特征值的對(duì)角矩陣。圖傅里葉變換就是將圖信號(hào)轉(zhuǎn)換到頻域：。其逆變換為。通過這種變換，研究者可以在頻域中處理和分析圖信號(hào)。

卷積定理：在傳統(tǒng)信號(hào)處理中，時(shí)域的卷積等價(jià)于頻域的逐點(diǎn)相乘。對(duì)于圖信號(hào)，同樣成立：設(shè)兩個(gè)圖信號(hào) X（輸入特征）和 g（濾波器），它們的圖卷積定義為：。其中，⊙ 表示頻域的逐點(diǎn)相乘，g 表示頻域?yàn)V波器。這表明圖卷積可以通過頻域操作實(shí)現(xiàn)。為了在圖神經(jīng)網(wǎng)絡(luò)中實(shí)現(xiàn)卷積，濾波器 g 被參數(shù)化為，它是特征值 ∧ 的函數(shù)：，其中 θ 是可訓(xùn)練的參數(shù)向量。卷積操作可以寫為：。

圖卷積網(wǎng)絡(luò)（GCN）在頻域和空域的解釋：在頻域圖模型中，GCN 使用的是的一階近似，其中。這種操作本質(zhì)上是一種固定的卷積操作，沒有可學(xué)習(xí)參數(shù)。由于歸一化之后的拉普拉斯矩陣的特征值范圍為 0 到 2 之間，2-θ 的濾波器實(shí)際上是一個(gè)低通濾波器：放大低頻平滑信號(hào)，減弱高頻信號(hào)。在空域圖模型中， GCN 的操作可以理解為對(duì)每個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的特征值進(jìn)行求和，然后取平均值。這是一種基于鄰居特征聚合的方式。GCN 的頻域和空域視角是等價(jià)的，但各有側(cè)重。頻域解釋更偏向理論上的信號(hào)處理本質(zhì)，而空域解釋更貼近工程實(shí)現(xiàn)和直觀理解。對(duì)于研究者而言，這兩種視角是相輔相成的，結(jié)合使用可以更全面地理解和改進(jìn) GCN。

Part 3: 新的統(tǒng)一框架：連接空域和頻域

教程中提出的框架基于一個(gè)核心假設(shè)：空間域和頻譜域的圖表示學(xué)習(xí)可以通過一個(gè)共同的數(shù)學(xué)語言進(jìn)行描述。研究人員引入了一種新的圖嵌入方法，該方法結(jié)合了圖的空間連接性和節(jié)點(diǎn)特征，能夠更加精準(zhǔn)地捕捉和表示圖數(shù)據(jù)的復(fù)雜性。

其他領(lǐng)域里頻域和空域的研究

在已存在的研究里，這種空域和頻域相互連接視角并不少見。研究者用兩個(gè)例子來說明：

（1）譜聚類：從譜域的視角看譜聚類是使用譜分解 (spectral decomposition) 或則說特征分解（eigen-decomposition），然后使用分解結(jié)果中特征值響亮的低頻信號(hào)來作為新的表達(dá)，然后使用較為簡單快速的 Kmeans 得到聚類結(jié)果。而另外一個(gè)新的實(shí)現(xiàn)，SpectralNet，設(shè)計(jì)了一個(gè)特別 loss，使用神經(jīng)網(wǎng)絡(luò)來得到幾乎一樣的結(jié)果。單神經(jīng)網(wǎng)絡(luò)是一種以降低 loss 為導(dǎo)向的迭代算法，所以可以視為一種近似譜聚類的算法。

（2）另外一個(gè)例子是著名的 Word2Vec 算法。以 Skip-gram 為例，每個(gè)單詞都要相似于它的上下文的環(huán)境里其他單詞。所以 Word2Vec 是一個(gè)迭代算法。在后來的研究中，Levy 提出了一些分析，發(fā)現(xiàn)使用 Word2Vec 的結(jié)果里的矩陣，能夠幾乎完整的還原單詞的共現(xiàn)矩陣（PPMI）。也就是說 Word2Vec 可以看作是矩陣分解算法的一種近似算法。

在這兩個(gè)例子中，研究者發(fā)現(xiàn)這種比較中，有類似于該研究提出的譜域和空域方法區(qū)別。即，一種方法側(cè)重矩陣分解，而另外一種側(cè)重于迭代近似。

Part 4: 未來方向展望

這項(xiàng)研究開辟了圖結(jié)構(gòu)學(xué)習(xí)領(lǐng)域的新方向，未來的研究可以基于此框架進(jìn)一步探索：

• 計(jì)算效率：如何進(jìn)一步優(yōu)化統(tǒng)一框架以處理大規(guī)模圖數(shù)據(jù)，在譜論表達(dá)下，圖的信息量依然巨大，對(duì)計(jì)算仍然是一個(gè)挑戰(zhàn)。
• 統(tǒng)一的譜論：目前譜論主要應(yīng)用于靜態(tài)圖結(jié)構(gòu)，而且是簡單圖（即無向，邊只連接兩個(gè)節(jié)點(diǎn)）。然后圖論中仍然有大量的不同類型的圖，缺少譜論的表達(dá)，例如有向圖，超圖，或則動(dòng)態(tài)圖。
• 應(yīng)用擴(kuò)展：將統(tǒng)一框架應(yīng)用到更多實(shí)際問題中，如生物信息學(xué)和社會(huì)網(wǎng)絡(luò)分析，如何解釋譜論視角下真實(shí)應(yīng)用的規(guī)律，是一個(gè)值得探索的領(lǐng)域。