圖像作為一種直觀普遍的數(shù)據(jù)類型被廣泛應(yīng)用于各種任務(wù)場景中。圖像既可以表示自然界中物體，也可以表示建筑、機械部件等人造幾何物體。然而對于幾何物體來說，使用多邊形表示比圖像既節(jié)省空間又更加精確。 

多邊形表示幾何物體的例子

1. 地圖上的建筑物：想象在二維地圖上有一座矩形房屋，當(dāng)作為圖像表示時，這幢房屋可能需要占用數(shù)百個像素，然而只有邊框的黑線才是有用的信息。多邊形表示只需記錄四個角的坐標(biāo)和它們的連接順序，就能準(zhǔn)確描繪出房屋的形狀。
2. 雪花分形圖案：當(dāng)我們放大觀察分形深層結(jié)構(gòu)時，分形邊緣會變得模糊。而多邊形表示則可以輕松記錄任意多的坐標(biāo)點來展示深層的分形細節(jié)。

這些例子說明了，使用多邊形表示幾何物體比圖像更有優(yōu)勢，特別是在需要精確性和數(shù)據(jù)效率的場景中。

多邊形表征學(xué)習(xí)捕捉和編碼輸入多邊形幾何體的基本特征。這些學(xué)習(xí)到的嵌入（embeddings）對于各種下游應(yīng)用具有直接的實用價值，包括城市規(guī)劃、形狀編碼、建筑模式識別以及地理問題解答等。

與早期只關(guān)注單一多邊形的研究不同，本文強調(diào)了多多邊形(multipolygon)的重要性，這對于全面理解物理環(huán)境至關(guān)重要。

多邊形應(yīng)用的例子

1. 地理問題解答：例如，問題“加拿大到美國有多遠？”需要正確編碼兩個多邊形（美國和加拿大的地圖輪廓）的關(guān)系，否則就會得到錯誤答案，比如“1404英里”。為了獲得正確答案（0，因為兩個國家接壤），我們需要對多多邊形進行合理的表征學(xué)習(xí)。
2. 建筑模式分析：建筑群的形狀和空間分布揭示了其功能的許多信息。美國別墅區(qū)建筑通常呈現(xiàn)出不規(guī)則的形狀，并且沿著道路松散地分布。這種隨機對齊與聯(lián)排別墅區(qū)形成鮮明對比，后者以統(tǒng)一的形狀和大小緊密排列，以優(yōu)化土地使用；而商業(yè)建筑則根據(jù)業(yè)務(wù)需求呈現(xiàn)出各種不同的形狀和大小。

這些例子凸顯了多多邊形表征學(xué)習(xí)的重要性，不僅需要考慮單一多邊形的形狀，還需要考慮多個多邊形之間的相互關(guān)系，以確保有效的學(xué)習(xí)。

多邊形表征學(xué)習(xí)對于多個應(yīng)用領(lǐng)域至關(guān)重要，包括形狀編碼、建筑模式分類和地理問題解答等。

盡管近年來該領(lǐng)域取得了顯著進展，但大多數(shù)研究仍集中在單一多邊形上，忽視了多邊形間的相互關(guān)系。為了解決這一問題，埃默里大學(xué)的研究人員提出了一個用于學(xué)習(xí)通用多邊形（包括單一多邊形和多多邊形）幾何體的框架。

原文鏈接：https://arxiv.org/abs/2407.00742

代碼鏈接：https://github.com/dyu62/PolyGNN

本文提出使用異質(zhì)可見圖（Heterogeneous Visibility Graph）表示多邊形，這種圖無縫整合了多邊形內(nèi)和多邊形間的關(guān)系。為了提高計算效率并減少冗余，本文提出了一種異質(zhì)生成樹（Spanning Tree）抽樣方法。

此外，本文設(shè)計了一種旋轉(zhuǎn)-平移不變的幾何表示，確保了在各種場景下的廣泛適用性。

最后，本文引入了Multipolygon-GNN，一個新穎的GNN模型，來學(xué)習(xí)可見圖中的空間和語義異質(zhì)性。

在五個數(shù)據(jù)集上的實驗表明，該模型能夠有效捕捉多邊形幾何體的有用表征。

挑戰(zhàn)與解決方案

開發(fā)一個能夠有效學(xué)習(xí)多邊形表征的機器學(xué)習(xí)模型面臨諸多挑戰(zhàn)。

1）設(shè)計一種能夠保存幾何細節(jié)的數(shù)據(jù)結(jié)構(gòu)，這種結(jié)構(gòu)需要處理多邊形內(nèi)關(guān)系（單個多邊形的形狀細節(jié)）和多邊形間關(guān)系（不同多邊形之間的空間動態(tài)）。這要求我們提出一種方法，將詳細信息與宏觀空間背景統(tǒng)一起來，確保沒有幾何信息的丟失。

為了解決這一問題，我們提出了一種可逆的多邊形到異質(zhì)可見圖的轉(zhuǎn)換過程。在這種方法中，圖通過頂點和邊巧妙地表示多邊形的形狀，同時可見性連接捕捉了多邊形之間的空間關(guān)系。

2）多邊形間的復(fù)雜成對關(guān)系引入了二次復(fù)雜度，這進一步要求學(xué)習(xí)方法的高效性。

為了減少異質(zhì)可見圖中的冗余并提高訓(xùn)練效率，我們開發(fā)了一種異質(zhì)生成樹采樣策略，該策略選擇性地采樣可見邊，實現(xiàn)線性復(fù)雜度。

3）多邊形表征學(xué)習(xí)的一個關(guān)鍵是所得到表征的泛化能力。為了保持多邊形幾何信息的旋轉(zhuǎn)和位移不變性，我們提出了一種異質(zhì)幾何表示，用于異質(zhì)可見圖中的節(jié)點。這種異質(zhì)幾何表示被證明能夠封裝圖中存在的完整空間和語義信息。

4）多多邊形本質(zhì)上包含了層次結(jié)構(gòu)，這一點雖然關(guān)鍵但尚未得到充分探討。例如，一排排聯(lián)排別墅可能共同構(gòu)成一個更大的社區(qū)結(jié)構(gòu)。識別和有效建模這些層次關(guān)系對于全面理解多邊形至關(guān)重要。因此，需要先進的模型來刻畫這些層次組織的模式。為此，我們開發(fā)了Multipolygon-GNN，這是一種新的圖神經(jīng)網(wǎng)絡(luò)模型，通過堆疊多個層的信息傳遞操作，能夠在不同粒度下聚合多邊形模式。

方法簡介

在多邊形表征學(xué)習(xí)中，我們面臨的一個關(guān)鍵挑戰(zhàn)是如何有效地統(tǒng)一多邊形內(nèi)和多邊形間的關(guān)系。為了解決這一問題，我們將多邊形轉(zhuǎn)換為異質(zhì)可見圖，如圖a所示。這一過程被證明是可逆的，能夠在將多邊形轉(zhuǎn)換為結(jié)構(gòu)化數(shù)據(jù)格式的同時，保持其必要的信息。

在圖b中，為了減少可見圖中的冗余并解決可擴展性問題，我們提出了一種采樣方法，從中抽取出簡潔的圖。這種方法可以有效地減少計算負擔(dān)，同時保留關(guān)鍵的幾何信息。

圖c展示了我們?yōu)槊總€兩跳路徑設(shè)計的五元組異質(zhì)幾何表示。該表示將幾何信息轉(zhuǎn)換為向量形式，同時保持可見圖中的信息，實現(xiàn)了旋轉(zhuǎn)和位移不變性。通過這種表示，我們進一步消除了異質(zhì)可見圖中的冗余。

最后，如圖d所示，我們提出了多層異質(zhì)兩跳信息傳遞機制，以刻畫多邊形的層次模式。這一機制能夠分層學(xué)習(xí)節(jié)點的上下文信息，而不會丟失幾何信息和屬性。我們證明了這種異質(zhì)圖神經(jīng)網(wǎng)絡(luò)能夠區(qū)分不同的輸入圖形，體現(xiàn)了其強大的區(qū)分能力。

異質(zhì)可見圖：捕捉多多邊形幾何及空間關(guān)系

多多邊形不僅由其構(gòu)成部分的形狀來定義，還包括這些組成部分之間的空間關(guān)系。為了統(tǒng)一多多邊形的這兩個方面，我們提出了異質(zhì)可見圖的概念，G(V,E,X,?)。

在我們的模型中，每個圖節(jié)點表示一個多邊形的頂點，其坐標(biāo)作為節(jié)點特征，而形狀信息由邊記錄。異質(zhì)可見圖包含了兩種不同類型的邊：內(nèi)部邊和可見邊，分別用于定義個體部分的形狀和連接各個部分，建模它們的空間關(guān)系。

對于可見邊，我們遍歷節(jié)點集??，在彼此可見的節(jié)點對之間構(gòu)建邊。通過這種異質(zhì)可見圖，我們不僅捕捉了多邊形的幾何形狀，還建模了其部分之間的空間關(guān)系，從而提供了對多邊形網(wǎng)絡(luò)的整體理解。

異質(zhì)生成樹采樣：減少異質(zhì)可見圖中的冗余

我們通過利用異質(zhì)可見圖的特征，開發(fā)了一種線性復(fù)雜度的采樣策略。關(guān)鍵在于理解可見邊的作用，它們用于連接多多邊形的各個部分。

為了確保不同部分之間的信息交換有效，需保持至少一條路徑連接不同的部分。這個需求可以通過求解生成樹問題來有效處理。

我們通過隨機采樣可見邊來構(gòu)建一個生成樹。通過這種方法，我們有效地減少了異質(zhì)可見圖中的冗余，同時保持了多邊形部分之間的連接性，確保了信息的完整性和有效的空間關(guān)系建模。

五元組異質(zhì)幾何表示：實現(xiàn)多邊形表示的旋轉(zhuǎn)和平移不變性

在多邊形的表征學(xué)習(xí)中，旋轉(zhuǎn)和平移不變性是一個重要目標(biāo)，因為多邊形結(jié)構(gòu)在這些變換下保持不變，而原始坐標(biāo)本身并不具備這一特性。

為了實現(xiàn)這一目標(biāo)，我們提出了一種五元組異質(zhì)幾何表示。考慮所有匯聚到節(jié)點??的兩跳路徑的集合。異質(zhì)可見圖G(V,E,X,?)可以表示為一組元組，其中每個元組包含以下信息：節(jié)點vi與vj之間的距離，節(jié)點vj和vk之間的距離，三個節(jié)點形成的角度，構(gòu)成路徑的兩條邊的類型。

這種表示方法具有旋轉(zhuǎn)和平移不變性，確保了圖的結(jié)構(gòu)完整性不受其方向或位置的影響。我們進一步確認(rèn)，這種元組格式能夠封裝圖的所有異質(zhì)空間信息。

Multipolygon-GNN：實現(xiàn)層次化多邊形表征學(xué)習(xí)的圖神經(jīng)網(wǎng)絡(luò)

我們提出了Multipolygon-GNN來學(xué)習(xí)異質(zhì)可見圖中的不同交互關(guān)系。在每一層中，我們采用兩跳信息傳遞機制，利用前述的五元組異質(zhì)幾何表示來更新節(jié)點嵌入。一條兩跳路徑可以通過不同邊類型連接同一多邊形部分內(nèi)的節(jié)點或不同部分之間的節(jié)點。

信息從一個多邊形部分流向另一個部分在學(xué)習(xí)多個多邊形間的相互關(guān)系時至關(guān)重要，而內(nèi)部部分的信息流則增強了對單個多邊形內(nèi)的局部上下文的理解。我們根據(jù)涉及的邊類型將可能的路徑類型劃分為四類。

為了有效利用圖的異質(zhì)性并區(qū)分不同的信息源，我們提出了一種異質(zhì)函數(shù)，根據(jù)路徑類型使用不同的權(quán)重網(wǎng)絡(luò)學(xué)習(xí)信息。我們對所有節(jié)點的嵌入進行求和，形成圖嵌入。接著，將所有層的圖嵌入連接起來用于下游任務(wù)。

實驗驗證

數(shù)據(jù)集

1. MNIST-P-2：包含 10,000 個兩位數(shù)多邊形樣本。類別：90類（數(shù)字 10-99）。
2. Building-S：包含 5,000 個單建筑物多邊形樣本，建筑物多邊形來自O(shè)penStreetMap (OSM) 建筑數(shù)據(jù)集。建筑物的標(biāo)簽反映了其形狀，分為十種字母形狀（H, I, E, Y, T, F, U, L, Z, O）。類別：10類
3. Building-2-R：包含 3,469 個雙建筑物多邊形樣本，每個樣本對為OSM建筑數(shù)據(jù)集的建筑物與其在地圖上最近的鄰居配對得來。類別：100類
4. Building-2-C：包含 5,000 個雙建筑物多邊形樣本。每個樣本對為OSM建筑數(shù)據(jù)集的建筑物進行歸一化后隨即匹配而來。類別：100類
5. DBSR-cplx46K：包含 46,567 個復(fù)雜多邊形幾何樣本，每個樣本由兩個多邊形組成，分類判斷兩個多邊形是否有包含關(guān)系。類別：2類有效性分析

表格展示了五個數(shù)據(jù)集上的性能比較。特別是在 MNIST-P-2 數(shù)據(jù)集上，PolygonGNN在準(zhǔn)確率、精確率、F1 分?jǐn)?shù)和 AUC 指標(biāo)上均取得了最高分，顯著超越了其他方法。在 Building-2-C和Building-2-R數(shù)據(jù)集中，盡管絕對性能一般，但PolygonGNN依然顯著優(yōu)于其他方法。

這兩個數(shù)據(jù)集由于是直接從地圖中抽取的，每個建筑的方向并未校準(zhǔn)對齊，可能出現(xiàn)顛倒的狀況導(dǎo)致標(biāo)簽本身存在爭議。

Building-S作為單個建筑物的數(shù)據(jù)集不存在標(biāo)簽爭議，DBSR-cplx46K數(shù)據(jù)集數(shù)據(jù)量很大并且任務(wù)相對簡單，因此所有方法在這兩個數(shù)據(jù)集上都取得了較好的表現(xiàn)。

以上實驗說明PolygonGNN在單一多邊形和多多邊形數(shù)據(jù)上都優(yōu)于現(xiàn)有方法，尤其是在多多邊形數(shù)據(jù)上具有絕對優(yōu)勢。本文其他實驗可以參考原文。

總結(jié) & 限制性

本文提出了PolygonGNN，一個強大的多邊形表征學(xué)習(xí)框架。PolygonGNN通過用異質(zhì)可見圖統(tǒng)一了單一多邊形和多多邊形的表征學(xué)習(xí)，在多種多邊形數(shù)據(jù)集上達到了最先進的性能。

局限性：PolygonGNN在采樣可見邊的時候選擇僅保留一條可見邊連接不同的部分，這可能會限制信息在不同部分之間的傳遞。未來的研究可以設(shè)計自適應(yīng)采樣策略根據(jù)不同部分的復(fù)雜性動態(tài)調(diào)整可見邊數(shù)量，或者將輸入圖進行多級粗化（coarsening），利用分層圖神經(jīng)網(wǎng)絡(luò)（Hierarchical GNN）分步學(xué)習(xí)每個部分的表征和全局表征，同時考慮不同部分之間的相對空間信息。