1、YOURE ALLSET!以多重集函數角度重新檢視超圖GNNEli Chien(簡翌)UIUC 博士候選人|Github:https:/ Webpage:https:/ et al.ICML 2018,Chien et al.AISTATS 2019集團擴張(clique-expansion,CE)定義的消息傳播|為了簡單我們暫且集中討論於d-uniform超圖也就是每個超邊皆只包含k個節點而我們可以用連接張量(adjacency tensor)0,1(2)!或是關聯矩陣(incidence matrix)0,1來表示d-uniform超圖其中n為節點數，m為超邊數而若節點1,之前有超邊，則

2、1,=1(2)!或 1,=1,=1，否則為0注意的是為超對稱，也就是1,任意排序其值皆相同集團擴張(clique-expansion,CE)定義的消息傳播|透過集團擴張(CE)，我們可以分別從A 或 H來得到一般圖的連接矩陣因此，對一節點特徵之消息傳播即為(左邊)乘上,()以消息傳播的等價數學表示寫法為使用CE定義的消息傳播之超圖神經網絡|值得注意的是，先前一些超圖神經網絡正是以CE為其設計消息傳播機制的根基例如HGNN Feng et al.,AAAI 2019其中d,w為超圖之節點度(node degree)與超邊權重，,為神經網絡參數非CE之超圖學習|另一方面，在網絡科學(network

3、 science)中有許多複雜且直接定義於超圖上的信息傳播方法他們多為張量方法(tensor based method)，並與張量特徵問題相關例如多線性PageRankGleich et al.SIMAX 2015與超圖上的Z特徵問題有緊密的關係Tudisco et al.WWW 2021 也於其工作中指出使用CE做標籤傳播的表現在某些情況下會比專門設計的非線性超圖標籤傳播因此，我們有其必要設計超圖GNN也能涵蓋上述之傳播機制Z特徵問題與其對應之消息傳播|Z特徵問題對應之Z消息傳播對比CE消息傳播本次核心問題|根據之前的研究我們已知CE會有消息損失，因此CE並非設計超圖神經網絡最優選擇Z消息傳

4、播等非CE方法在特定問題上表現要比CE消息傳播強“是否存在一統一框架可以包含CE、Z-based以及其他超圖傳播?”“我們能否設計超圖神經網絡使其能根據數據學習不同且合適的超圖傳播？”本文中我們針對這兩個問題給出肯定的答案AllSet一個多重集視角的超圖神經網絡框架|AllSet:多重集視角的超圖神經網絡框架|AllSet的核心思想：許多超圖消息傳播皆可看作兩個多重集函數(,)的組合AllSet:多重集視角的超圖神經網絡框架|多重集函數(multiset function):輸入排序不影響函數輸出允許重複輸入(i.e.x1 x2 相同)，因此為多重集(multiset)AllSet:多重集視角

5、的超圖神經網絡框架|:學習每個超邊的表示(representation),:學習每個節點的表示AllSet:多重集視角的超圖神經網絡框架|在，對每個超邊e而言，其關聯節點之順序並不影響其表示結果(permutation invariant)對同理，對每個節點v而言，其關聯超邊之順序不影響其表示結果AllSet框架的理論表達能力(Expressive power)|(Theorem 3.3)CE-based 與 Z-based 傳播定義皆可被AllSet還原主要證明思路：藍框的部分可以看做，顯然累加與連乘皆為permutation invariant的操作，所以的確是一多重集函數，橘框部分同理可

6、以看做AllSet框架的理論表達能力(Expressive power)|(Theorem 3.4)AllSet框架的表達能力(expressive power)嚴格大於許多現有的超圖神經網絡，包含HGNN Feng et al.AAAI 2019,HyperGCN Yadati et al.NeurIPS 2019,HCHA Bai et al.PR 2021,HyperSAGE Arya et al.2020,HNHN Dong et al.2020主要證明思路：AllSet框架可以還原上述超圖神經網絡的傳播機制與Z傳播，但上述超圖神經網絡皆無法還原Z傳播以HGNN為例首先，這與CE傳播類

7、似所以的確屬於AllSet框架其次，在藍框的部分可以看到他就是一個最終結果的線性變換，因此無法模擬Z傳播AllSet框架的理論表達能力(Expressive power)|(Theorem 3.5)AllSet是MPNN架構Gilmer et al.ICML 2017的超圖推廣主要證明思路：因為超圖是圖的推廣，經過一些數學運算後便可以得到此一結果上述三個定理也從理論上展示了我們AllSet框架的強大表達能力我們先前也舉出張量方法在超圖學習上的成功例子，這說明了我們AllSet框架的表達能力是必要的，否則將無法涵蓋張量方法(例如Z傳播)設計可學習之AllSet層|目前我們雖然證明了AllSet框

8、架的強大理論表達能力，但仍未解釋如何設計可學習之AllSet層關鍵思想：使用具有多重集函數的萬能模擬性質(universal approximation)之模型Deep Sets Zaheer et al.NeurIPS 2017Set Transformer Lee et al.ICML 2019使用此二模型學習我們AllSet框架中的,，即分別為我們的AllDeepSets 與AllSetTransformer根據萬能模擬性質，我們的AllDeepSets與AllSetTransformer皆依然比前述之超圖神經網絡有更強大的表達能力設計可學習之AllSet層|雖然Deep Sets 與

9、Set Transformer皆具有相同的表達能力，但Lee et al.ICML 2019中的實驗顯示Set Transformer實際上表現更佳其可能原因為Deep Sets中的累加(Summation)是無權重的，而在Set Transformer中則以注意力機制(attention)去做權重累加我們在超圖實驗中也觀察到相似結果實驗結果|實驗說明|本文集中於超圖學習中的節點分類任務除了五個常用的引用網絡數據集，我們也蒐集了另外三個較少使用的UCI數據集(Zoo,20News,Mushroom)與兩個CV相關的數據集(NTU2012,ModelNet40)另外，我們也新提出了三個超圖數據集

10、(Yelp,House,Walmart)，且將許多現有的超圖神經網絡整合到我們的代碼中統一測試有鑑於在超圖任務上尚未有像OGB的整合，我們的代碼與新數據可以看做對於超圖神經網絡測試基準化的第一步實驗結果|粗體灰底粗體灰底表示最佳表現藍底表示在最佳表現一個標準差之内實驗結果|可以看出我們先提出的AllSetTransformer一般來說具有最優性能之前的超圖神經網絡在常用的學術網絡上表現很好，但是在其他數據集上就有可能表現不佳實驗結果|如其他模型都至少在兩個數據集上表現不佳最強的基線(baseline)模型UniGCNII Huang et al.2021 IJCAI在Yelp 以及Walmar

11、t上表現明顯差於AllSetTransformer這也說明了根據數據自適應學習超圖傳播機制的重要性結論與未來方向|結論|我們針對超圖神經網絡提出了一個泛用的框架AllSet我們證明了大部分現有超圖神經網絡層的表達能力皆嚴格弱於AllSet，且證明了AllSet為MPNN的超圖推廣我們利用近年深層多重集函數學習的結果，結合AllSet概念設計出可學習的AllSet層AllSetTransformer實驗顯示在節點分類任務中AllSetTransformer的表現優於SOTA超圖神經網絡我們也引入了新的超圖數據集，為超圖神經網絡的測試基準化做了初步的貢獻我們的代碼已開源，並附上所有測試的數據集和測

12、試baseline方法https:/ Transformer實際性能更好的模型可以利用？例如：Janossy pooling當前AllSet框架下的超圖神經網絡仍可能存在一般圖神經網絡之前遇過的問題如minibatch training,over-smoothing等等之前GNN的解決方案如何有效地應用到AllSet框架中？抑或需要新的解決方案？如Minibatch training，GNN 中常見解決方案為ClusterGCN或是GraphSAINT能否將這些方案推廣至AllSet中?未來方向|是否能根據AllSet學到的多重集函數判斷所學到的傳播機制較偏向於CE or Z or 其他？此方向能增強超圖學習的可解釋性是否能有類似於GPRGNN Chien et al.ICLR 2021的可解釋性結果？其是否與CE和高階馬可夫鏈定義下的傳播 Chien et al.ITW 2021 有關？AllSet於其他超圖任務中的性能與改良設計？超邊預測，超圖的圖分類問題等等非常感谢您的观看|