Emory提出最新PolygonGNN框架：可捕捉通用多邊形內外的空間關系 | KDD 2024
圖像作為一種直觀普遍的數據類型被廣泛應用于各種任務場景中。圖像既可以表示自然界中物體，也可以表示建筑、機械部件等人造幾何物體。然而對于幾何物體來說，使用多邊形表示比圖像既節省空間又更加精確。
多邊形表示幾何物體的例子
- 地圖上的建筑物：想象在二維地圖上有一座矩形房屋，當作為圖像表示時，這幢房屋可能需要占用數百個像素，然而只有邊框的黑線才是有用的信息。多邊形表示只需記錄四個角的坐標和它們的連接順序，就能準確描繪出房屋的形狀。
- 雪花分形圖案：當我們放大觀察分形深層結構時，分形邊緣會變得模糊。而多邊形表示則可以輕松記錄任意多的坐標點來展示深層的分形細節。
這些例子說明了，使用多邊形表示幾何物體比圖像更有優勢，特別是在需要精確性和數據效率的場景中。
多邊形表征學習捕捉和編碼輸入多邊形幾何體的基本特征。這些學習到的嵌入（embeddings）對于各種下游應用具有直接的實用價值，包括城市規劃、形狀編碼、建筑模式識別以及地理問題解答等。
與早期只關注單一多邊形的研究不同，本文強調了多多邊形(multipolygon)的重要性，這對于全面理解物理環境至關重要。
多邊形應用的例子
- 地理問題解答：例如，問題“加拿大到美國有多遠？”需要正確編碼兩個多邊形（美國和加拿大的地圖輪廓）的關系，否則就會得到錯誤答案，比如“1404英里”。為了獲得正確答案（0，因為兩個國家接壤），我們需要對多多邊形進行合理的表征學習。
- 建筑模式分析：建筑群的形狀和空間分布揭示了其功能的許多信息。美國別墅區建筑通常呈現出不規則的形狀，并且沿著道路松散地分布。這種隨機對齊與聯排別墅區形成鮮明對比，后者以統一的形狀和大小緊密排列，以優化土地使用；而商業建筑則根據業務需求呈現出各種不同的形狀和大小。
這些例子凸顯了多多邊形表征學習的重要性，不僅需要考慮單一多邊形的形狀，還需要考慮多個多邊形之間的相互關系，以確保有效的學習。
多邊形表征學習對于多個應用領域至關重要，包括形狀編碼、建筑模式分類和地理問題解答等。
盡管近年來該領域取得了顯著進展，但大多數研究仍集中在單一多邊形上，忽視了多邊形間的相互關系。為了解決這一問題，埃默里大學的研究人員提出了一個用于學習通用多邊形（包括單一多邊形和多多邊形）幾何體的框架。
原文鏈接：https://arxiv.org/abs/2407.00742
代碼鏈接：https://github.com/dyu62/PolyGNN
本文提出使用異質可見圖（Heterogeneous Visibility Graph）表示多邊形，這種圖無縫整合了多邊形內和多邊形間的關系。為了提高計算效率并減少冗余，本文提出了一種異質生成樹（Spanning Tree）抽樣方法。
此外，本文設計了一種旋轉-平移不變的幾何表示，確保了在各種場景下的廣泛適用性。
最后，本文引入了Multipolygon-GNN，一個新穎的GNN模型，來學習可見圖中的空間和語義異質性。
在五個數據集上的實驗表明，該模型能夠有效捕捉多邊形幾何體的有用表征。
挑戰與解決方案
開發一個能夠有效學習多邊形表征的機器學習模型面臨諸多挑戰。
1）設計一種能夠保存幾何細節的數據結構，這種結構需要處理多邊形內關系（單個多邊形的形狀細節）和多邊形間關系（不同多邊形之間的空間動態）。這要求我們提出一種方法，將詳細信息與宏觀空間背景統一起來，確保沒有幾何信息的丟失。
為了解決這一問題，我們提出了一種可逆的多邊形到異質可見圖的轉換過程。在這種方法中，圖通過頂點和邊巧妙地表示多邊形的形狀，同時可見性連接捕捉了多邊形之間的空間關系。
2）多邊形間的復雜成對關系引入了二次復雜度，這進一步要求學習方法的高效性。
為了減少異質可見圖中的冗余并提高訓練效率，我們開發了一種異質生成樹采樣策略，該策略選擇性地采樣可見邊，實現線性復雜度。
3）多邊形表征學習的一個關鍵是所得到表征的泛化能力。為了保持多邊形幾何信息的旋轉和位移不變性，我們提出了一種異質幾何表示，用于異質可見圖中的節點。這種異質幾何表示被證明能夠封裝圖中存在的完整空間和語義信息。
4）多多邊形本質上包含了層次結構，這一點雖然關鍵但尚未得到充分探討。例如，一排排聯排別墅可能共同構成一個更大的社區結構。識別和有效建模這些層次關系對于全面理解多邊形至關重要。因此，需要先進的模型來刻畫這些層次組織的模式。為此，我們開發了Multipolygon-GNN，這是一種新的圖神經網絡模型，通過堆疊多個層的信息傳遞操作，能夠在不同粒度下聚合多邊形模式。
方法簡介
在多邊形表征學習中，我們面臨的一個關鍵挑戰是如何有效地統一多邊形內和多邊形間的關系。為了解決這一問題，我們將多邊形轉換為異質可見圖，如圖a所示。這一過程被證明是可逆的，能夠在將多邊形轉換為結構化數據格式的同時，保持其必要的信息。
在圖b中，為了減少可見圖中的冗余并解決可擴展性問題，我們提出了一種采樣方法，從中抽取出簡潔的圖。這種方法可以有效地減少計算負擔，同時保留關鍵的幾何信息。
圖c展示了我們為每個兩跳路徑設計的五元組異質幾何表示。該表示將幾何信息轉換為向量形式，同時保持可見圖中的信息，實現了旋轉和位移不變性。通過這種表示，我們進一步消除了異質可見圖中的冗余。
最后，如圖d所示，我們提出了多層異質兩跳信息傳遞機制，以刻畫多邊形的層次模式。這一機制能夠分層學習節點的上下文信息，而不會丟失幾何信息和屬性。我們證明了這種異質圖神經網絡能夠區分不同的輸入圖形，體現了其強大的區分能力。
異質可見圖：捕捉多多邊形幾何及空間關系
多多邊形不僅由其構成部分的形狀來定義，還包括這些組成部分之間的空間關系。為了統一多多邊形的這兩個方面，我們提出了異質可見圖的概念，G(V,E,X,?)。
在我們的模型中，每個圖節點表示一個多邊形的頂點，其坐標作為節點特征，而形狀信息由邊記錄。異質可見圖包含了兩種不同類型的邊：內部邊和可見邊，分別用于定義個體部分的形狀和連接各個部分，建模它們的空間關系。
對于可見邊，我們遍歷節點集??，在彼此可見的節點對之間構建邊。通過這種異質可見圖，我們不僅捕捉了多邊形的幾何形狀，還建模了其部分之間的空間關系，從而提供了對多邊形網絡的整體理解。
異質生成樹采樣：減少異質可見圖中的冗余
我們通過利用異質可見圖的特征，開發了一種線性復雜度的采樣策略。關鍵在于理解可見邊的作用，它們用于連接多多邊形的各個部分。
為了確保不同部分之間的信息交換有效，需保持至少一條路徑連接不同的部分。這個需求可以通過求解生成樹問題來有效處理。
我們通過隨機采樣可見邊來構建一個生成樹。通過這種方法，我們有效地減少了異質可見圖中的冗余，同時保持了多邊形部分之間的連接性，確保了信息的完整性和有效的空間關系建模。
五元組異質幾何表示：實現多邊形表示的旋轉和平移不變性
在多邊形的表征學習中，旋轉和平移不變性是一個重要目標，因為多邊形結構在這些變換下保持不變，而原始坐標本身并不具備這一特性。
為了實現這一目標，我們提出了一種五元組異質幾何表示。考慮所有匯聚到節點??的兩跳路徑的集合。異質可見圖G(V,E,X,?)可以表示為一組元組，其中每個元組包含以下信息：節點vi與vj之間的距離，節點vj和vk之間的距離，三個節點形成的角度，構成路徑的兩條邊的類型。
這種表示方法具有旋轉和平移不變性，確保了圖的結構完整性不受其方向或位置的影響。我們進一步確認，這種元組格式能夠封裝圖的所有異質空間信息。
Multipolygon-GNN：實現層次化多邊形表征學習的圖神經網絡
我們提出了Multipolygon-GNN來學習異質可見圖中的不同交互關系。在每一層中，我們采用兩跳信息傳遞機制，利用前述的五元組異質幾何表示來更新節點嵌入。一條兩跳路徑可以通過不同邊類型連接同一多邊形部分內的節點或不同部分之間的節點。
信息從一個多邊形部分流向另一個部分在學習多個多邊形間的相互關系時至關重要，而內部部分的信息流則增強了對單個多邊形內的局部上下文的理解。我們根據涉及的邊類型將可能的路徑類型劃分為四類。
為了有效利用圖的異質性并區分不同的信息源，我們提出了一種異質函數，根據路徑類型使用不同的權重網絡學習信息。我們對所有節點的嵌入進行求和，形成圖嵌入。接著，將所有層的圖嵌入連接起來用于下游任務。
實驗驗證
數據集
- MNIST-P-2：包含 10,000 個兩位數多邊形樣本。類別：90類（數字 10-99）。
- Building-S：包含 5,000 個單建筑物多邊形樣本，建筑物多邊形來自OpenStreetMap (OSM) 建筑數據集。建筑物的標簽反映了其形狀，分為十種字母形狀（H, I, E, Y, T, F, U, L, Z, O）。類別：10類
- Building-2-R：包含 3,469 個雙建筑物多邊形樣本，每個樣本對為OSM建筑數據集的建筑物與其在地圖上最近的鄰居配對得來。類別：100類
- Building-2-C：包含 5,000 個雙建筑物多邊形樣本。每個樣本對為OSM建筑數據集的建筑物進行歸一化后隨即匹配而來。類別：100類
- DBSR-cplx46K：包含 46,567 個復雜多邊形幾何樣本，每個樣本由兩個多邊形組成，分類判斷兩個多邊形是否有包含關系。類別：2類有效性分析
表格展示了五個數據集上的性能比較。特別是在 MNIST-P-2 數據集上，PolygonGNN在準確率、精確率、F1 分數和 AUC 指標上均取得了最高分，顯著超越了其他方法。在 Building-2-C和Building-2-R數據集中，盡管絕對性能一般，但PolygonGNN依然顯著優于其他方法。
這兩個數據集由于是直接從地圖中抽取的，每個建筑的方向并未校準對齊，可能出現顛倒的狀況導致標簽本身存在爭議。
Building-S作為單個建筑物的數據集不存在標簽爭議，DBSR-cplx46K數據集數據量很大并且任務相對簡單，因此所有方法在這兩個數據集上都取得了較好的表現。
以上實驗說明PolygonGNN在單一多邊形和多多邊形數據上都優于現有方法，尤其是在多多邊形數據上具有絕對優勢。本文其他實驗可以參考原文。
總結 & 限制性
本文提出了PolygonGNN，一個強大的多邊形表征學習框架。PolygonGNN通過用異質可見圖統一了單一多邊形和多多邊形的表征學習，在多種多邊形數據集上達到了最先進的性能。
局限性：PolygonGNN在采樣可見邊的時候選擇僅保留一條可見邊連接不同的部分，這可能會限制信息在不同部分之間的傳遞。未來的研究可以設計自適應采樣策略根據不同部分的復雜性動態調整可見邊數量，或者將輸入圖進行多級粗化（coarsening），利用分層圖神經網絡（Hierarchical GNN）分步學習每個部分的表征和全局表征，同時考慮不同部分之間的相對空間信息。
