異構信息網絡 (Hetegeneous Information Network 以下簡稱 HIN),是由 UIUC 的 Han Jiawei 和 UCLA 的 Sun Yizhou 在 2011 年的 VLDB 論文中首次提出。

VIP內容

摘要近年來,使用結構化數據建模的圖神經網絡(GNNs)取得了巨大的成功。然而,大多數的GNN都是針對同構圖設計的,在同構圖中,所有的節點和邊都屬於同一種類型,使得它們無法表示異構結構。在這篇論文中,我們提出了一種異構圖 Transformer(HGT)結構來對web級的異構圖進行建模。為了對異構性進行建模,我們設計了節點類型和邊類型的相關參數來描述每個邊上的異構注意力程度,從而使HGT能夠維護不同類型節點和邊的特定表示。為了處理動態異構圖,我們在HGT中引入了相對時間編碼技術,該技術能夠捕獲具有任意持續時間的動態結構依賴關係。針對網絡規模圖數據的處理問題,設計了高效、可擴展的小批量圖數據采樣算法HGSampling。在擁有1.79億個節點和20億個邊的開放學術圖上進行的大量實驗表明,所提出的HGT模型在各種下遊任務上的性能始終比所有最先進的GNN基線高9-21%。

關鍵詞:圖神經網絡;異構信息網絡;表示學習;圖嵌入;圖注意力

介紹

異構圖通常對複雜的係統進行抽象和建模,其中不同類型的對象以各種方式相互交互。此類係統的一些常見實例包括學術圖、Facebook實體圖、LinkedIn經濟圖,以及廣泛的物聯網網絡。例如,圖1中的開放學術圖(OAG)[28]包含五種類型的節點:論文、作者、機構、場所(期刊、會議或預印本)和字段,以及它們之間不同類型的關係。

在過去的十年中,人們對異構圖[17]的挖掘進行了大量的研究。其中一個經典的範例就是定義和使用元路徑來對異類結構進行建模,例如PathSim[18]和變元ath2vec[3]。最近,鑒於圖神經網絡(GNNs)的成功[7,9,22],[14,23,26,27]嚐試采用GNNs來學習異構網絡。然而,這些工作麵臨著幾個問題:首先,它們大多涉及到為每種類型的異構圖設計元路徑,這需要特定的領域知識;其次,它們要麼簡單地假設不同類型的節點/邊共享相同的特征和表示空間,要麼為節點類型或單獨的邊類型保留不同的非共享權值,使它們不足以捕獲異類圖的屬性;三是大多忽略了每一個(異構)圖的動態性;最後,它們固有的設計和實現使得它們無法對web規模的異構圖進行建模。

以OAG為例:首先,OAG中的節點和邊可能具有不同的特征分布,如論文具有文本特征,而機構可能具有來自附屬學者的特征,共同作者明顯不同於引文鏈接;OAG一直在不斷發展,例如:1)出版物的數量每12年翻一倍[4];2)KDD會議在1990年代更多地與數據庫相關,而近年來更多地與機器學習相關;最後,OAG包含數億個節點和數十億個關係,使得現有的異構GNN無法擴展來處理它。

針對這些限製和挑戰,我們建議研究異構圖神經網絡,其目標是維護節點和邊類型依賴表示、捕獲網絡動態、避免自定義元路徑和可擴展到web級圖。在這項工作中,我們提出了異構圖 Transformer(HGT)架構來處理所有這些問題。

為了處理圖的異構性,我們引入了節點類型和邊類型依賴注意力機製。HGT中的相互注意不是對每一個類型邊參數化,而是根據其元關係三元組e=(s,t),即 s為節點類型,s與t之間的e的邊類型,t的節點類型。圖1展示了異構學術圖的元關係。具體來說,我們使用這些元關係來對權重矩陣參數化,以計算每條邊上的注意力。因此,允許不同類型的節點和邊維護其特定的表示空間。同時,不同類型的連接節點仍然可以交互、傳遞和聚合消息,而不受其分布差異的限製。由於其架構的性質,HGT可以通過跨層傳遞消息來整合來自不同類型的高階鄰居的信息,這可以看作是軟元路徑。也就是說,即使HGT隻將其單跳邊作為輸入,而不需要手動設計元路徑,所提出的注意力機製也可以自動、隱式地學習和提取對不同下遊任務重要的元路徑。

為了處理圖數據的動態特性,我們提出了相對時間編碼(RTE)策略來增強HGT。我們不打算將輸入圖分割成不同的時間戳,而是建議將發生在不同時間的所有邊作為一個整體進行維護,並設計RTE策略來對任何持續時間長度的結構性時間依賴關係進行建模,甚至包括不可見的和未來的時間戳。通過端到端訓練,RTE使HGT能夠自動學習異構圖的時間依賴性和演化。

為了處理網絡規模的圖形數據,我們設計了第一個用於小批量GNN訓練的異構子圖采樣算法HGSampling。它的主要思想是樣本異構子圖中不同類型的節點與類似的比例,由於直接使用現有的(均勻)GNN抽樣方法,如GraphSage [7], FastGCN[1],和LADIES[29],結果在高度不平衡的關於節點和邊緣的類型。此外,它還被設計成保持采樣子圖的密度以最小化信息的丟失。通過HGSampling,所有的GNN模型,包括我們提出的HGT,都可以在任意大小的異構圖上進行訓練和推斷。

我們證明了所提出的異構圖Transformer在網絡規模開放學術圖上的有效性和效率,該開放學術圖由1.79億個節點和20億個邊組成,時間跨度從1900年到2019年,這是迄今為止在異構圖上進行的規模最大、跨度最長的表示學習。此外,我們還檢查領域特定的圖表:計算機科學和醫學學術圖表。實驗結果表明,與最先進的GNNs和專用的異構模型相比,在下遊任務中HGT可以顯著提高9-21%。我們進一步進行了案例研究,表明了所提出的方法確實能夠自動捕獲不同任務的隱式元路徑的重要性。

成為VIP會員查看完整內容
0
75
3

最新論文

To explore heterogeneous information networks (HINs), network representation learning (NRL) is proposed, which represents a network in a low-dimension space. Recently, graph neural networks (GNNs) have drawn a lot of attention which are very expressive for mining a HIN, while they suffer from low efficiency issue. In this paper, we propose a pre-training and fine-tuning framework PF-HIN to capture the features of a HIN. Unlike traditional GNNs that have to train the whole model for each downstream task, PF-HIN only needs to fine-tune the model using the pre-trained parameters and minimal extra task-specific parameters, thus improving the model efficiency and effectiveness. Specifically, in pre-training phase, we first use a ranking-based BFS strategy to form the input node sequence. Then inspired by BERT, we adopt deep bi-directional transformer encoders to train the model, which is a variant of GNN aggregator that is more powerful than traditional deep neural networks like CNN and LSTM. The model is pre-trained based on two tasks, i.e., masked node modeling (MNM) and adjacent node prediction (ANP). Additionally, we leverage factorized embedding parameterization and cross-layer parameter sharing to reduce the parameters. In fine-tuning stage, we choose four benchmark downstream tasks, i.e., link prediction, similarity search, node classification and node clustering. We use node sequence pairs as input for link prediction and similarity search, and a single node sequence as input for node classification and clustering. The experimental results of the above tasks on four real-world datasets verify the advancement of PF-HIN, as it outperforms state-of-the-art alternatives consistently and significantly.

0
0
0
下載
預覽
Top