2-3 You are AllSet！以多重集函数角度重新检视超图GNN.pdf

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傳播類