Contrastive Graph Autoencoder for Shape-based Polygon Retrieval from Large Geometry Datasets
Authors: Zexian Huang
Kourosh Khoshelham
Martin Tomko
Venue: Accepted by TMLR ()

Abstract: Retrieval of polygon geometries with similar shapes from maps is a challenging geographic information task. Existing approaches can not process geometry polygons with complex shapes, (multiple) holes and are sensitive to geometric transformations (e.g., rotations). We propose Contrastive Graph Autoencoder (CGAE), a robust and effective graph representation autoencoder for extracting polygon geometries of similar shapes from real-world building maps based on template queries. By leveraging graph message-passing layers, graph feature augmentation and contrastive learning, the proposed CGAE embeds highly discriminative latent embeddings by reconstructing graph features w.r.t. the graph representations of input polygons, outperforming existing graph-based autoencoders (GAEs) in geometry retrieval of similar polygons. Experimentally, we demonstrate this capability based on template query shapes on real-world datasets and show its high robustness to geometric transformations in contrast to existing GAEs, indicating the strong generalizability and versatility of CGAE, including on complex real-world building footprints.

Published in Transactions on Machine Learning Research (06/2024)
Contrastive Graph Autoencoder for Shape-based Polygon Retrieval from Large Geometry Datasets
Zexian Huang, Kourosh Khoshelham & Martin Tomko
The University of Melbourne, Parkville, Victoria, 3010, Australia (zexianh@stuudent. k. k.xhoahelhame, tomkom@@uuimeeb..edee adu. ad
Reviewed on OpenRevicw:
Abstract
Retrieval of polygon geometries with similar shapes from maps is a challenging geographic information task. Existing approaches can not process geometry polygons with complex shapes, (multiple) holes and are sensitive to geometric transformations (e-g., rotations). We propose Contrastive Graph Autocncoder (CGAE), robust and effective graph representa- vion autoencoder for extracting polygon geometries of similar shapes from real-world building maps based on template queries. By leveraging graph message- passing layers, graph feature augmentation and contrastive learning, the proposed CGAE embeds highly discriminative latent embeddings by reconstructing graph features w.r.t. the graph representations of input polygons, outperforming existing graph-based autoencoders (GAFs) in geometry retrieval of similar polygons. Experimentally, we demonstrate this capability based on template query shapes on real-world datasets and show high robustness geometric transformations in contrast to existing GAFs, indicating the strong generalizability and versatility of CGAF, including complex real-world building footprints.
1 Introduction
Geometric shape matching and retrieval is non-trivial task in geographic information systems especially challenging when handling complex geometries. Queries describing the geometric shapes of objects to be matched (templates) are encoded and models then retrieve objects with shapes that are visually similar. Traditional approaches encode query shapes into vector reprosentations to search for similar geometrics in databases. Statistically, Goodall (1911) presented a model-based Procrustes approach to analysing sets of shapes. Conceptually, Egenhofer (1997) first proposed system that converts sketched queries into topolog- ical scene descriptions. Walter & Fritsch (1999) proposed statistical approach to compute the geometric distributions (i.e., length, angle and distance) of road networks for data matching. Shape recognition meth- ods approached shape matching and identification through shape contexts (Belongie et al. 2002). turning functions (Arkin et al. 1991), shape compactness (Li et al. 2013) or Fourier-transfrm methods (Ai et al, 2013). Specifically, Xu et al. (2017) proposed a shape-similarity measurement model, which adopts position graphs to describe geometric properties of polygons and applies Fourier descriptors to measure the shape similarity of spatial polygons with holes. While such methods statistically characterize the goometric infor- mation of polygons for shape matching and retrieval, they are often limited in applications to simple polygon geometries and do not generalize well to large-scale polygon databases.
Recently, learning-based methods have been developed to encode polygon geometric features for geospatial applications. van Veer el. al. (2018) proposed deep neural networks for the semantic classifications of polygons that vectorize vertices of simple polygon boundaries as vertex sequences. A 1D convolutional neural network is applied to learn discriminative geometric features (i.c., building types). The classification accuracy of deep convolutional approaches outperformed traditional "shallow" machine learning methods (i.e., logistic regression, support vector machine (SVM) and decision tree), as shown in their study.

---

Published in Transactions on Machine Learning Research (06/2024)
More recently, Mai et al. (2023) have developed a polygon encoding model that leverages non-uniform Fourier transform (NUFT) (Jiang et al. 2019) and multilayer perceptron (MIP) to generate latent embeddings of simplex-based based signals from spectral feature domains. The latent embeddings of polygons in form of 2D geometric grid frequency maps, capturing global geometric features of polygons, are applied for classifying geometric shapes and predicting spatial relations of polygons. Yan et al. (2021) proposed a graph-based convolution autoencoder to learn the compact embeddings of simple polygons for shape coding and retrieval tasks on building footprint dataset. They represented simple polygons as graphs, with boundary vertices nodes and the adjacency of the vertices along the outer polygon boundary as edges. They then devised graph convolution autoencoder (GAE) to learn the normalized Laplacian features of graphs in spectral domain (Kipf & Welling 2017), which implicitly reflect the convolutional features of k-hop neighboring nodes in graphs. While the GAE is effective on certain polygon retrieval tasks, it is not robust to geomelric transformations (e.g., rotations) of polygon shapes and has not been tested on geometries with holes, Hence, a robust method for retrieving complex polygons with holes from spatial databases (c.g., polygonal building maps) operating on graph representations of polygons is worth investigating. We hypothesize that the model robustness to geometric transformations and model generalisability supporting retrieval of complex polygons (with holes) from large-scale spatial geometry databases can be achieved by graph autoencoder leveraging the structural information and connectivity of graph representation of polygons with contrastive lcarning.
We thus propose an unsupervised Contrastive GAF for polygon shape matching and retrieval on large-scale geometry (e.g, building polygon) databases. In contrast to traditional models and state-of-art learning- bearning-based graph autoencoders, our Contrastive Graph Autoencoder (CGAE) is independent of polygonal vertex counts; capable of retrieving polygons with or without holes; robust to polygon rotations; and can effectively generalizes to large polygon datascts.
2
Graph Autoencoder
Autoencoders (Hinton & Zemel 1993) are unsupervised learning models designed to reconstruct input data from compact embeddings in latent space. A range of autoencoders has been proposed for graph data: in particular, the variational graph autoencoder (VGAE) (Kipf & Welling 2016) applics graph convolution layers (Kipl & Welling (017) as encoders to learn graph topology embeddings for link predictions. Following VGAE, the adversarially regularized graph autoencoder (Pan et al. 2018) introduced an adversarial training scheme to enforce latent embeddings of graph encoders to match a prior normal distribution and reinforce the robustness of latent embeddings. For unsupervised learning of universal latent embeddings across data domains, contrastive learning (Chen et al.) (220)) has been combined with graph autoencoders (You et al., 2020 Hou al. 2022). Graph autoencoders are thus far mainly applied on relatively small graph datasets for link prediction and unsupervised graph clustering. The applications of graph autocncoders to spatial geometries (e.g., large-scale building footprints) with iveerastive learning has not been fully investigated.
Conceptually, the objective of a graph autoencoder is to learn compact latent embeddings Z for input graph G= (A, X}, where X E Rd denotes a node feature matrix of graph G, and A is a square adjacency matrix that encodes the topological information of graph G, where dt E = if there exists an edge bet ween nodes n4, ny E X, otherwise ai,j = Typically, GAEs consist of: (1). graph encoder that takes graph G [A, X) as input and generates compact latent embeddings Z via differential neural network layers 0A + Z E Rdd; (2). graph decoder that reconstructs the graph embeddings G" X'',X') from latent embeddings Z: (3). an optimization component, with reconstruction loss L that minimizes the reconstruction error between input graph and reconstructed graph embeddings.
Our Contrastive Graph Autoencoder (CGAE) introduces a contrastive component Lo to GAE, minimizing the contrastive error between the compact graph embeddings zo and the contrastive graph counterparts z Fig. I demonstrates the overall architecture of proposed CGAE. We first outline the novel contributions of CGAE, and introduce the graph contrastive component next.
2

---

Published in Transactions on Machine Learning Research (06/2024)
Z EX
A" D(EE, 2E
Z3 E(LA4,0)
X" = 4;
ZN E(X,,,))
Edge Recon. Loss
Adjacency
Perturbation
Liee Lo
x
passing Graph Encoder
Message-passing Graph Decoder
Recon. Loss
Node
Node Ramoval
Contrastive Loss
Graph Representation
Graph Augmentation by
2 Readout(
Reconstruction
(eadout(Zi))
B 2
Readout
B2g
Added
Downstram Tack
Removed Node Edge
Contrastive Node Loss Ao
Contratiiee Edge Loss Icee
Non-llnear Activation
Le LON + LCE
Model architecture of CGAE. Inputs: vertex coordinates of T-shape polygon are encoded into node feature matrix X, and the connectivity of vertices into the adjacency matrix A. We produce contrastive pairs of X and A by graph augmentations, obtaining a removed node feature matrix X and a perturbed adjacency matrix, A", CGAE learns robust and discriminative latent embeddings by the computation of the graph reconstruction loss Lee and costrastive loss Lc.
Figure 1:
2.1 Graph Representation of 2D Polygons
A polygon defined as a simple geometry (i.e., no self-intersoctions) consisting collection of sequences of vertices encoding single exterior ring defining the exterior boundary, and zero or multiple interior rings defining the internal holes of the geometry (Open Geospatial Consortiumi 2003). The polygon geometry is converted into graph representation G AA input to the graph autoencoder, where X captures the vertex positions and the adjacency matrix A captures the adjacency of the vertices in the boundary linear ring of vertices (Fig. D The graph representation enables describing the geometric and connectivily information of polygons as matrices, which are computationally efficient for graph representation learning.
2.2
Message- passeeggasing Graph Encoder
Graph encoder then embeds G into a latent space. Typical graph encoders use graph convolutional networks (GCN) from Kipf & Welling (2017) and its variants to learn node-wise convolution features of with the normalized graph Laplacian matrix À --1--/1/2
1/2 AD 1122 where À = A + I is the adjacency matrix with an identity matrix (i.e., self-connections of nodes); and 5 is the diagonal degree matrix. The latent embeddings Z of graph G are hence learned by diffcrentiable neural network layer f(:;6) (Eq. 1 Subscquently, can express how GCN learns the latent node- wise euneddinggs of graph G as per Eq.
((),A:0) 1-1 1/2 X 1/2
(1)
Åxo.
2, TT
Σ
āi,j Iz. T/J where n's = Vd, x dj
(2)
d.yEA=1
3i.1 corresponds to the edge weight between nodes I; and T, of the normalized graph Laplacian matrix
fd,xd,
A. We observe that typical GCN encoder is limited to encoding polygon's boundary information and does
3

---

Published in Transactions on Machine Learning Research (06/2024)
not generalize to polygons with holes. Eq. 2 suggest that the edge weights between the node pair (I,, 2z) are constants defined by a fixed adjacency and node degree matrix, A and D of input graph. This largely limits the capability of graph encoders to learn expressive latent embeddings Z for complex polygons with holes. Previous studics (Qi et al. 2017a b Wang et al.) 2019) have demonstrated the importance of encoding and learning local geometric features for point sets, in particular, 3D point clouds. These learning- models construct local ANN graphs from 3D point clouds and aggregate local geometric features of points in local kNN sub-graphs per point. These studies also show that learning local geometric features as node features of point sets extensively increases the performance of point cloud classification and segmentation. Analogically, we hypothesize that polygon boundaries can be learned as local geometric node features via graph-based neural networks in an unsupervised graph autoencoder, leading to robust and highly expressive latent embeddings = for polygon geometries with holes. We thus propose a graph-based autoencoder with a message- saaaagg-psssing neural network as encoder (Gilmer et al. 2017) (Eq. 3
2 max O (a;; ll (xx zz)), as.y EA=1
(3)
where the message wetween nodes I; and Ty is (x, - xc), defined as the relative feature positions wet the two nodes, or "node centralization" " (Tailor et al. 2021p. We observe that in Eq. 3 the latent embedding 2, updated for node x; in a single pessage-passing layer encodes the maximum of the concatenation || of the positional feature r₃ E X of vertex and its boundary information defined by the relative positions between its neighboring nodes. A multi-layer perceptron (MLP) with trainable weights @ linearly projects the local geometric information to a latent space and the non-linearity of the message-passingg layer is then carried out by a non-linear activation function applied to the layer output 24.
Compared to GCN, the messsgg-ppssiiggg layers leverage the local geometric features (i.c., relative positional features), which are previously demonstrated to be elfective on 3D point sets, learn expressive and robust node-wise embeddings for polygons. Noted that in typical graph autoencoder, the GCN layers apply the summation pooling to aggregate neighboring convolution features z'j, instead in the peessag-passiing layers, we propose to use the maximum pooling to aggregate the local geometric features. Here, the use of maximum aggregation/ /pwolino aims to generate output features that outline representative elements and capture the
skeleton of point sets (Xu et al. 2019: Qi ct al. 201 7a b Wang et al. 2019
2.3 Graph Reconstruction
Graph decoder targets to reconstruct the graph data G from latent embeddings Z, such that the reconstructed graph G' to be as close as to the input graph G. In CGAE, we propose two kinds of decoder to reconstruct the node features X" and edge features A' of graph G", respectively.
Node Feature Reconstruction We apply a symmetric message pasasing network architecture (Park al. 2019h in CGAE's decoders to reconstruct the node feature matrix X' from the latent embeddings Z. Con- cretely, given embeddings Z, a single-layer node decoder is defined in Eq as:
max θ (=: ll (z3 =2)),
(4)
where the MLP eventually projects latent node-wise embedding z; E Z to input node-wise embedding, of E X'. Similar to the node decoder in GAE (Yan et al., 2021 the node reconstruction loss of CGAE is based on the mean squared crror (MSE) (Eq.))
1 1 n
LN
(5)
1=1
Edge Reconstruction We add an additional edge decoder, the inner product decoder from Kipl & Welling 2016), to reconstruct the topologiaal structure A' of graph. The edge decoder leverages the latent node embeddings Z, with a being a sigmoid activation function and p(ylæ) conditional probability, mapping Ci, A' to (0, 1) (Eq. c
A' p(A'lZ) oZZ7),
(6)
4

---

Published in Transactions on Machine Learning Research (06/2024)
To compute the reconstruction loss between the graph adjacency A and reconstructed adjacency A', we produce binary labels for edges based on the ground-truth adjacency A. For matrix A values indexed by {i,j}, values where ai,j = 1 are positive, and values where aij = 0 are negative. The indexes of positive ground-truths are then (i.j and negative ground-truths neg(t.)- For balanced binary label representation leeding edge reconstruction, we randomly sample equal amounts of negative and positive ground-truths from adjacency A. We compute the edge reconstruction loss with the binary cross entropy error between the positive and negative edge labels (Eq. 7
LE = log( ( Apoeru.)) log(1 Anest
where (pos denotes the reconstructed odge value with ground-truth positive edge indexes and Alee denotes the reconstructed edge value with ground-truth negative edge indexes.
Incorporating edge reconstruction to CGAE is necessary as the topological structure captures non-trivial connectivity information of the polygon graphs, to expressively outline the shape of the geometry. The decoders and edge reconstruction loss thus inherently force the graph encoder to learn latent embeddings that encode salient topological information of input graphs
3 Contrastive Graph Autoencoder
The key contribution of CGAE is the contrastive learning of latent graph embeddings za At its core, contrastive learning maximizes the mutual information agreement between the positive contrastive pairs and push the negative contrastive pairs apart in training batches (Hjelm et al. 2019 Belghazi et al. 2018 It thus forces similar features to be closer in latent space.
Graph Augmentation As a desirable property, if graph embeddings are robust to node corruptions (i.e,, if random node elimination/ addition does not drastically change the semantic representation of the polygon boundary graph (You et al.] 2020)), a trained CGAE should enable reconstructing uncorrupted node features from corrupted latent embeddings Z" We apply graph-level augmentations to input data in graph G = (A, X) and generate contrastive pairs for learning by perturbing edge information of G by randomly adding an r percentage of new edges to the adjacency matrix A, resulting in the perturbed adjacency matrix A (Fig. 1 For node features of G, we randomly drop an percentage of nodes along with corresponding edges, resulting in the corrupted node feature matrix X*. We define graph augmentation function s(A, X() on G = {A,
X}, and as hyper-parameter augmentation ratio. By defining r, 6(1, X/r) returns a corrupted node matrix X* ~ X(r) and a perturbed edge matrix A ~ ((A, respectively.
Corrupted Node and Perturbed Edge Reconstruction The pressge-passing graph encoder (Eq, 3 now takes a corrupted node feature x E X" and returns a latent nodc-wisc embedding 2 E Zi: with 2 representing the corrupted latent. node-wise embeddings generated based on the corrupted node feature X*. We then reconstruct the node-wise embeddings as proposed in Eq. (applied to 2)) and compute the node reconstruction loss LN as proposed in Eq. 5 (applied to x;").
Similarly, the principal prior of edge perturbation is that randomly adding edges as noise to graph con- nectivity should not alter its semantic information. We therefore reconstruct G's connectivity from latent embeddings Z" with perturbed edge information. Correspondingly, the message-passing graph encoder in Eq, 3 takes perturbed edge connection of,- E A' as imputs and returns a latent node-wise embedding 2 E Z where Z represents the latent node-wise embeddings generated based on the perturbed edge matrix ^*.
We then reconstruct the graph connectivity A" by applying Eq. D and compute the edge reconstruction loss LE as proposed in Eq. 7 applied on Ajos and Allo The resulting latent embeddings should thus be less sensitive to arbitrary variations of boundary edges of polygon geometries, thus robustly capturing significant shape and semantic information.
Contrastive Learning The main objective of contrastive learning with graph autoencoders is maximize the mutual information between the global latent graph embeddings and their augmented counterparts.
5

---

Published in Transactions on Machine Learning Research (06/2024)
Graph encoders thus learn to encode compact graph and node-wise embeddings tolerant to node corruptions (i.e., random node dropping) and edge perturbation (i.e., random edge addition). The latent embedding representing polygon shapes thus become more robust to geometric transformations and minor variations of boundary information.
We thus compute three kinds of latent graph embeddings zG; Nς and zg E RRd from the latent node- wise embeddings Z, En and i E Raxd with a graph readout function: z Readout (2), where Readout (+) is global average pooling to compute graph-wise representations from node-wise embed- dings. We put latent graph embeddings in training batches with pre-defined batch size b (b 32), giving: E2..... ..... Zg, where Bze, B2g and
Bzc [ ...., Bzg E gxxd are training batches of latent graph embeddings 2G, 26 and zg. A contrastive loss function is then defined to maximize the mutual information agrcement of positive contrastive pairs and push negative contrastive pairs apart in batches. Here, we apply the normalized temperature-scaledd cross-entropy loss (NT-Xent) from Sohn 2016 and Chen et al. 22220 to compute the contrastive loss of contrastive pairs Lex(2e, 28) and LCE 7 2g,
..... T B2g = I X
N2...... ......,, -N,"", Bzg = 100 2
in Eq.
exp(sim (2,,&8)/1
CoN(Z, ( = - -log
(8)
Σ Ej,fj (xp(sim
simm ( 22,)/T)
where 7 is temperature-scaled value that controls the impact of positive (i.e., (Z 2 vs. negative (i.e., (Z ZX,) )) contrastive pairs, and sim(.) is similarity function that measures the similarity of embeddings, the average NT-Xent loss on batches (Bza, Bzg)
which is defined as the cosine similarity. Following Eq. g
and (Bza, Bzg) is defined as (Eq. 9
1 h LoN( B2g) = b
Σ i=1
CoN (Z, xx.)
(9)
We optimize the CGAE with the reconstruction loss LRce and contrastive loss Lc. According to Eq. 5 and Liee is defined as Liee = LN + Lg, and based on Eq. Band Eq. 9 La is defined as Lo = Lcn + Leg. We then optimize the CGAE by minimizing the sum of losses L = Ree + Le. CGAE is designed to cluster graph embeddings of complex shapes using latent node wise embeddings Z generated from the message-passian passing encoder CGAE. The global graph embeddings z are pooled by a readout layer (i.e., Readoulmean) from Z. Since graph embeddings z encode the geometric and boundary information of polygons in latent space, polygons with geometrically similar shapes are clustered, and hence retrieved by finding the k nearest neighbours (kNN) of latent graph embeddings of query shapes.
4 Experiments
We evaluate the performances of proposed CGAE against two baselines: GAE Yan et al. 2021 and NUFT (Mai et al.) 2023 Jiang et al. 2019 on polygon retrieval from the Glyph, Open Street Map (OSM) and Melbourne datasets (Appendix A). We conduct an ablation study to demonstrate the effectiveness of the proposed peessag--assing encoder-decoder structure and the contrastive components of CGAE. Stepwise, we first replace the GCN backbone GAE with a pressage-passingg backbone, and enrich the baseline GAE (i.e., GAE (Cx)) by adding the edge reconstruction loss CE (i.e., GAE (E)+ and the proposed contrastive loss Lo, resulting in CGAE and evaluate performance gains. The progressively refined GAEs are applicd on three distinct backbone networks: (1). the GCN by Kipf & Welling (0017) (2). the message-passing passing neural network: EdgeeCnnv (Wang et al.; 2019), to test the benefit of learning local geometric features (i.e., the relative positions between nodes), and (3). the graph isomorphic network (GIN {Xu et al. 2019)). Model
training and parameters for experiments are described in Appendix B
Model Discriminability (Glyph Datasct) robust and effective autoencoder generates highly discrim- inative latent embeddings for geometrically transformed polygons. We train a CGAE (EdgeConv backbone) and baseline GAF on the synthetic Glyph-O dataset, and visualize the respective latent embeddings in

---

Published in Transactions on Machine Learning Research (06/2024)
25
-20
-60
-80
-75
-100
-75
-50
(a) t-SNE plot of CAE
(b) t-SNE plot of CGAE.
Figure t-SNE plot of latent feature emboddings (auto learning rate, perplexity=50, itcrations=1000) of the feature embeddings of models tested dataset Glyph-O.
2D space via I-SNE plot (Van der Maaten & Hinton 2008 (Fig. 2 The latent embeddings of CGAE are highly discriminative and less noisy than in GAE. This qualitatively indicates the effectiveness of in- corporating graph augmentation, contrastive learning, and message-pssing layers into graph autoencoder architectures. To investigate the gains brought by these components individually, we quantitatively evaluate the performance on a retrieval task with geometrically transformed (rotated, skewed and scaled) shapes (Glyph dataset).
Table I reports the polygon retrieval performance and standard deviations of GAEs and NUFT the Clyph dataset using shape similarity (Hausdorff distance, Appendix D between the query shape and its k nearest neighbors (for & to 6). The CGAE-EdgeConv achieves the best performance on Glyph-O, Glyph- R, Glyph-SC and Glyph-SK datasets for all & neighbors. By ablation we identify the performance gains of CGAE brought by edge reconstruction loss CE over the baseline GAE. Reconstructing the edge connectivity generates latent emboddings that encode information cnabling the effective discovery of similar shapes. By comparing models with different backbones, EdgeConv achieves the best performance on both GAE and CGAE. This suggests that peessag-ppssing graph encoders learning of local geometric information (i.e., node centralization and relative positions) is key for superior performance shape retrieval w.r.t geometric transformations. While the CGAE performs best on all Glyph datasets, contrastive learning has the highest impact on encoding skewed polygons, where Glyph-SK CGAF-FdgeConv leads to largest improvement compared to GAE-EdgeConv.
Building Polygon Retrieval (OSM Dataset) Table 2 reports the polygon retrieval performances and standard deviations of models on two variants of the OSM building dataset: (1) original polygons (OSM-O) and (2) rotated and mirrored polygons (OSM-R). The CGAE performs best among all models on both. By ablation, we find that GAE with edge reconstruction loss LE generalizes better both OSM-O and OSM-R building footprints compared to baseline GAE but with limited performance gains (OSM-O: 1-NN (0.218
0.208) to 6-NN (0.271 + 0.267) and OSM-R: 1-NN (0.323 + 0.308) to 6-NN (0.400 + 0.396)). Message- passing backbone networks (either GIN or EdgeConv) bring significant model generalizability (Table 2) Extracting shapes from geometrically transformed datasets is challenging, yet CGAE with contrastive loss and edge roconstruction loss LE + Lo is robust to polygon rotations. Typically, CGAE-EdgeConv shows large improvements on OSM-R compared with Edge-Ede (i.e., 1-NN (0.235 0.225) to 6-NN (0.320- 0.301)).

---

Published in Transactions on Machine Learning Research (06/2024)
Table CGAE performance against baselines on the Glyph dataset. Hausdorff distance (# standard deviation) best in bold (the smaller the better).
Dataset
Model
Backbone
1-NN
2-NN
3-NN
4-NN
B-NN
G-NN
NUPT
+0.230
0.304
+0.226
0.354
+0.220
0.385
+0.0.224
0.379
GAE (Cg)
GCN
20:154
0.193
1.0
0.220
0.245
10.159
1:0 161
0,257
10.100
0.284
20 001161
0,271
Glypl-O
GAR (AN 4
GCN
GIN
+0.124
10.150
0.159
0.183
+-01188
10.156
0.182
0.218
10.156
+2.
1.0.159
+0.183
0.217
0.245
10.161
+0.184
0.224
0.252
20.161
+0.136
0.232
0,260
EdgeConv
20:114
0.152
10.116
0.188
10.121
0.109
10.122
0,211
10.125
0.218
20.127
0.225
CCAE (CN CE
0.159
0.903
0.213
0.236
10:125
10.1199
10.130
1.0 130
10.133
20.133
EdgaCony
#0.110
0.150
#:0.12
0.180
#0.
0.193
#0.112
0.203
#0.118
0.209
#0.110
0.213
0.417
0.442
0-436
0.483
0.470
0.472
0.220
CAE (4N)
GCN
#0.154
0.271
10.154
0.802
#0.150
0.318
10.164
0.328
10.164
0.396
0.115
0.348
Clypb--t
0.263
0.296
-0.165
(AN fg)
40.131
$0.140
1001446
EdgeCony
10.114
0.219
10.118
0.248
10.183
10
0,276
10.127
20.131
0,292
0.245
0.270
0.285
0.284
0.304
0.311
10.140
1:0.142
10.141
1: 143
1..143
20.144
(CN + 4E Cc)
0.222
1..125
1:0.128
0.266
10.130
0.278
+0.103
NUFT
MLP
+0,246
0.465
+0.244
0.488
+0.239
0.495
0.501
0. 257
+0.288
0.502
0.505
0.2
0.344
(4N)
+0.144
+0.149
+0.146
CAB (AN + 4g)
GCN
10:145
0.245
0.272
10.148
0.501
10.151
0.313
399
1:0 101
0.206
0.521
10.101
0.530
0.314
10.
0.322
0.597
10.136
1:0
15.153
2:0
160160
105165
EdgeCoav
0.284
0.261
0,200
0.118
CGAR (CN 1 CE Fc)
GCN
GIN
10:113
10.130
0.228
0.256
1:0.192
10.117
0.279
0.249
10.117
#0. 154
0.291
0.260
10.111
155
0,300
0,288
10.121
10.157
0.307
0.272
10.123
101157
0,278
0.312
EdgeGonn
10.095
0.219
10.097
0.240
10.300
0.252
10.101
0,261
10.102
0.266
20.105
0.271
NUPT
MLPP
20.228
0.536
122
0.380
10.222
0.374
222
0.379
20.224
0.590
200
0.393
GAR (CN)
0.229
0.257
0.278
0.287
0.283
00.167
GAR (ex + Gg>
GCN
GIN
+0.108
10.128
0.189
0.224
+0..167
10.133
0.215
0.253
+0.
10.141
0.265
0.330
1:0.146
+00.77
0.240
0.279
20.149
#0.1779
0.248
0.286
20.1b
+0.181
0.207
0,298
EdgeConn
10:113
0.181
10 193
0.205
0.221
196
1: 132
0,250
10-133
0.239
2
0.245
CCAE (Cy 4R 4e)
GCN
GIN
#0.116
10.133
0.182
0 0.208
#:0.120
1.0.140
0.230
0.280
10.146
0.213
0.343
12.
1:0
1:0.148
0.219
0.232
10.144
10.
0.260
10.12
20.14
0.230
0.262
PdgeConv
20.100
0.173
+00.103
0.194
+0.204
0,305
1:0.108
0.218
#0.110
0.210
20.110
0.223
We emphasize that all models were only trained the synthetic Glyph dataset, and evaluated the OSM building dataset to explore model gencralizability. Compare the performance on Glyph-O and Glyph-R (Table 1 with that on OSM-O and OSM-R (Table 2). The baseline GCN achieves comparable performances on both Glyph-O and OSM-O datasets (from 1-NN (0.193 - 0.218) to 6-NN (0.271 + 0.271)) but the model degrades when generalizing from Glyph-R to OSM-R: 1-NN (0.271 - 0.323) to 6-NN (0.343 - 0.400). In contrast, the CGAE-Edee AC-Eeedeeon only suffers limited degradation generalizing from Glyph-R OSM-R: from 1-NN (0.212 0.225) to 6-NN (0.269 0.301).
8

---

Published in Transactions on Machine Learning Research (06/2024)
When comparing CGAE-Edge to baseline GAE-EdgeCony the performance gain OSM-O is small (1- NN (0.174 - 0.172), 2-NN (0.191 - 0.190) and 3-NN (0.202 0.200)). This small performance difference between Coge-Ed vs. GAE-EdgeConv is mainly because of the polygon geometries in OSM dataset manifesting low variability (without any geometric transformation, i.c.; rotations). The task is therefore not challenging for the baselines, as shown Fig. 7 (Appendix E enabling GAE-GCN to achieve com- parable retrieval performance. Despite the small performance gain, the smaller standard deviations of our CGAE-Edgeeony in Table 2 (i.e., from I-NN 10.126 to 6-NN #0.134) suggest more stable and robust model performance compared to GAE-EdgeCony (i.e., from 1-NN #0.131 to 6-NN =0.148), with reduced performance uncertainty.
Table 2: CGAE performance against baselines on the OSM building dataset. Hausdorff distance (+ slandard deviation) best in bold (the smaller the better). Qualitative results are displayed in Appendix
Dataset
Model
Backbone
1-NN
2-NN
S-NN
4-NN
5-NN
6-NN
0.302
0.327
0.341
0.352
0.354
0.363
NUFT
MLP
#0.238
#0.241
#0.245
#0.250
#0.246
#0,250
GAE (4x)
0.218
0.238
0.250
0.261
0.265
0.271
GCN
#0.174
#0.178
#0.178
#0.184
10.186
10.187
0.208
0.232
0.245
0.254
0.259
0.267
GCN
OSM-O
GAE (CN + LE)
10.169
10.175
10.182
#0.184
10.186
10.189
0.187
0.209
0.221
0.229
0.237
0.243
GIN
+0.145
+0.154
#0.158
#0.158
#0.162
10.164
0.174
0.191
0.202
0.212
0.219
0.228
EdgeConv
+0.131
+0.133
+0.134
#0.139
#0.142
=0.148
0.200
0.220
0.231
0.238
0.244
0.251
GCN
10.159
10.162
10.163
10.165
10.166
10.170
CGAE (Cx + LE Lc)
0.184
0.203
0.213
0.221
0.227
0.231
GIN
+0.144
+0.149
+0.150
+0.151
+0.154
+0.153
0.172
0.190
0.200
0.208
0.214
0.217
EdgeConv
+0.126
10.129
10.132
10.134
10.135
10.134
0.431
0.461
0.481
0.490
0.502
0.508
NUFT
MLP
#0.269
#0.260
#0.258
#0,253
#0.252
#0.251
GAE (Ix)
0.323
0.353
0.373
0.384
0.394
0.400
GCN
10.211
10.204
10.204
10.202
10.200
10.199
0.308
0.344
0.359
0.379
0.387
0.396
GCN
OSM-R
GAE (CN + LF)
+0.208
+0.211
+0,208
+0,208
+0.207
#0.206
0.267
0.302
0.325
0.340
0.353
0.362
GIN
10.181
10.185
10.188
10.188
10.191
10.190
0.235
0.266
0.285
0.302
0.311
0.320
EdgeConv
+0.145
+0.152
+0.152
+0.155
+0.158
10.15
0.292
0.320
0.338
0.351
0.359
0.369
GCN
10.195
10.192
10.190
10.191
10.190
10.189
CGAF (Lx + LE Lc)
0..445
0.277
0.296
0.310
0.317
0.326
GTN
+0.161
+0.166
+0.165
+0.170
+0.169
+0.167
0.225
0.255
0.272
0.286
0.295
0.301
EdgeConv
+0.133
+0.136
10.135
#0.137
10.137
10.138
Building Polygon Retrieval (Melbourne Dataset) We finally test. the large-scale real-world shape retrieval performances of GAEs and NUFT on the Melbourne building dataset, with uncontrolled shapes, where GAEs were trained on the synthetic Glyph datasot. Table 3 shows that CGAF-EdgeConv again outperforms other models by a large margin, especially the baseline GAE that cannot handle multipart polygons. Comparing CGAF-Edgeeony with GAE GAE-EdgeCony implies that the incorporation of contrastive

---

Published in Transactions on Machine Learning Research (06/2024)
Table 3: CGAE performance against baselines on the Melbourne building dataset. Hausdorff distance (+
standard deviation) best in bold (the smaller the better). Qualitative results are displayed in Appendix E.2
Dataset
Model
Backbone
1-NN
2-NN
3-NN
4-NN
5-NN
6-NN
0.382
0.401
0.413
0.418
0.424
0.429
NUFT
MLP
10.230
10.230
10.232
10.232
10.232
10.233
GAE (Cx)
0.588
0.597
0.598
0.604
0.602
0.608
GCN
+0.251
+
+0.246
+0.245
0..24
+0.243
0.579
0.588
0.591
0.592
0.596
0.598
Melbourne
GCN
+0.254
+0.249
0.246
#0.246
0..444
0.245
GAE (CN + Le)
0.566
0.572
0.577
0.579
0.581
0.583
GIN
+0.257
+0.251
+0.250
+0.249
00224
0.247
0.223
0.255
0.273
0.283
0,290
0,297
EdgeConv
+0.148
10.156
#0.159
#0.161
10.12
16.14
0.575
0.584
0.587
0.590
0.589
0.593
GCN
+0.255
#0.248
#0.246
#0.246
#0.245
#0.247
CGAE (Cx + Lg + Lc)
0.555
0.562
0.565
0.568
0.570
0.572
GIN
+0.260
+0.253
#0.252
#0.251
#0.251
#0.55
0.214
0.242
0.257
0.266
0.273
0.278
EdgeConv
10.141
10.146
10.149
10.150
10.151
10.151
loss brings positive effects to retrieval of multipart (incl. with holes) polygons (from 1-NN (0.223 + 0.214) to 6-NN (0.297 + 0.278)). Overall, the proposed CGAE demonstrates strong capability of latent feature encoding even for complex shapes. The model can identify and retrieve similar shapes, even from large-scale real-world geometry datascts and on shapes with nuanced geometrics of the kind never seen in training.
5
Discussion
Node centralization in message- paaggg-gpsinggggg graph autoencoders key for shape retricval performance as shown through ablation studies on synthetic (Glyph), controlled (OSM), and uncontrolled (Melbourne) datasets, compared to graph (Laplacian) convolution layers. The relative node position message computed in Edge- Conv (i.e., node centralization) and passed between nodes of local sub-graphs encodes highly expressive local geometric information. While this has been previously shown effective on unstructured 3D point cloud learn- ing (Qi et al. 2017a b Wang et al. 2019), our study documents the significance of learning local geometric features on 2D vector polygons.
Joint reconstruction of edge and node features from latent node-wise embeddings enables GAFs to exploit the structural and geometrie information for finer feature encoding. Our ablation study shows that the GAE with the reconstruction loss LN + LE overperforms baseline GAE with Ln independently of network backbones. This indicates the importance of learning graph connectivity and structural information for graph feature encoding.
Graph augmentation and contrastive learning further improve latent feature generalization and robustness as shown by CGAE's performance on Glyph-R, Glyh-SK (Table D and OSM-R (Table 2 The CGAF- EdgeConv combination achieves strong performance on geometrically transformed polygons over bascline GAE-EdgeConv, as shown by consistently smaller standard deviations of Hausdorff distance on both Glyph and OSM datasets. The information captured by the latent graph embedding is enhanced through con- trastive learning and contrastive loss from augmented signals (i.c., based on random node dropping and edge perturbation). This supports our hypothesis that the graph encoder is capable of learning compact graph embeddings that are tolerant to node corruptions and edge perturbations.
CGAE's superior performance (Table 3) demonstrates how contrastive learning aids model generalisa- tion. The polygons in Glyph and OSM datasets have comparatively simple boundaries (i.e., small vertex counts) that encapsulate distinct. geometric and semantic information (i.e., shapes of characters), whereas
10

---

Published in Transactions on Machine Learning Research (06/2024)
the boundaries of complex building footprints in Melbourne dataset may consist of many vertices. CGAE generalizes effectively the geometric information learned from simple polygons to complex shapes, demon- strating a desirable model property, ie., decoupling of shape detail (i.e., polygon trivial vertex count) from retricval accuracy.
6 Conclusion
We presenl a novel unsupervised contrastive graph auloencoder (CGAE) for robust polygon retrieval of build- ing polygons. We conduct ablation studies on multiple polygonal datasets to demonstrate the effectiveness of proposed CGAE, and present empirical evidence that the proposcd CGAE with graph messago-passee passing encoder-decoder, multiple reconstruction losses and contrastive learning outperforms baseline graph au- toencoder with single node reconstruction loss, well baselines with GCN or MLP backbones. The proposed CGAE exhibits desirable characteristics for retrieval of spatial geometries, such building poly- gons: is robust to variable geometry vertex counts; can retrieve complex polygons with or without holes; is robust to polygon rotations; can effectively generalize to large-scale polygon maps without fur- ther model fine-tuning. Note that the generalisation of CGAE to arbitrary graphs that only capture topology e.gg, social networks) but not graph geometry or the application to ensembles of shapes defining semantics (e.g.; terrace houses (Lischer al. 2009)) are not addressed here.
Reproducibility Statement
Source code for method implementation and datasets for reproducing experiment results is available https///gttauo..ccmeeeehaaggggg
11

---

Published in Transactions on Machine Learning Research (06/2024)
References
Tinghua Ai, Xiaoqiang Cheng, Pengcheng Liu, and Min Yang. A shape analysis and template matching of building features by the fourier transform method. Computers, Environment and Urban Systems, 41: 219-233, 2013.
Anonymous. Learning geometric invariant features for classification of vector polygons with graph message- passing neural network. unpublished, 2023.
Esther M Arkin, L Paul Chew, Daniel P Huttenlocher, Klara Kedem, and Joseph S Mitchell. An efficiently computable metric for comparing polygonal shapes. Technical report, CORNELL UNIV ITHACA NY, 1991.
Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeswar, Sherjil Ozair, Yoshua Bengio, R. Devon Hjelm, and Aaron C. Courville. Mutual information neural estimation. In ICML, volume 80 of Proceedings of Machine Learning Research, pp. 530-539. PMLR, 2018
Serge Belongie, Jitendra Malik, and Jan Puzicha. Shape matching and object recognition using shape contexts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(4):509 522, 2002.
Ting Chen, Simon Korublith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive lcarning of visual representations. In International Conference on Machine Learning, pp. 1597-1607. PMLR, 2020.
CoM Open Data. City of Melbourne 2020 building footprints, May 2021. URL https://daaae /ttt://elaaaaaeeembr...
vic.gov ric.gov.au/explorzee
David H. Douglas and Thomas K. Peucker. Algorithms for the reduction of the number of points required to
represent a digitized line or its caricature. Cartographien: The International Journal for Geographic In-
formation and Geovisualization, 10:112 122, 1973. URL httpp:////pp sea.aaacsseaattttcccooorra.oo.o http://ccccoaaooorooorrppsaaaaaa org/CorpusID:
60447873
Max J Egenhofer. Query processing in spatial-query--b-sketthd Journal of Visual Languages & Computing, 8(4):403 424, 1997.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, pp. 1263-1272 PMLR, 2017.
Colin Goodall. Procrustes methods in the statistical analysis of shape. Journal of the Royal Statistical Society; Series B (Methodological), 53(2):285-33)) 1991.
Google, May 2010. URL https://fonte.gogl...cooo
Geoffrey Hinton and Richard Zemel. Autoencoders, minimum description length and helmholtz free energy. Advances in Newral Information Processing Systems, 6, 1993.
R. Devon Hjelm, Alex Fodorov, Samuel Lavoic-Marchille Karan Grewal, Philip Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. In ICLR. OpenReview.net, 2019.
Zhenyu Hou, Xiao Liu, Yukuo Cen, Yuxiao Dong, Hongxia Yang, Chunjie Wang, and Jie Tang. Graphmae: Self-supervised masked graph autoencoders. In KDD, pp. 594 604. ACM, 2022.
Chiyu Jiang, Dana Lansigan, Philip Marcus, Matthias Nießner, et al. Ddsl: Deep differentiable simplex layer for learning geometric signals. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 8769 8778, 2019.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
12

---

Published in Transactions on Machine Learning Research (06/2024)
Thomas N. Kipf and Max Welling. Variational graph auto-encoders. CoRR, abs/1611.07303 2016.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Represenlations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.nn net, 2017.
Wenwen Li, Michael F Goodchild, and Richard Church. An efficient measure of compactness for two- dimensional shapes and its application in regionalization problems. International Journal of Geographical Information Science, 27(6):1227-1256) 2013.
Tya Loshchilov and Frank Hutter. SGDR: stochastic gradient descent with warm restarts. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview net, 2017.
Patrick Lüscher, Robert Weibel, and Dirk Burghardt. Integrating ontological modelling and bayesian infer- ence for pattern classification in topographic vector data. Computers, Environment and Urbon Systems, 33(5):363-377 374, 2009.
Gengchen Mai, Chiyu Jiang, Weiwei Sun, Rui Zhu, Yao Xuan, Ling Cai, Kraysatof Janowicz, Stefano Frmon, and Ni Lao. Towards general-purpose representation learning of polygonal geometries. Geolnformatica, 27(2))289 340, 2023.
Deng Min, Li Zhilin, and Chen Xiaoyong. Extended hausdorff distance for spatial objects in gis. International Journal of Geographical Information Science, 21(4):459-41 2007.
Open Gcospatial Consortium. Opengis simple features specification for SQL revision 1.0, 2003. URL http:
org/
OpenStrcetMap contributors. OSM Planet dump, 2023. URL https://planet: osm. org.
Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, Lina Yao, and Chengqi Zhang. Adversarially regularized graph autoencoder for graph embedding, In IJCAI, pp. 2609 2615. ijeai.org, 2018.
Jiwoong Park, Minsik Lee, Hyung Jin Chang, Kyuewang Lee, and Jin Young Choi. Symmetric graph con- volutional autoencoder for unsupervised graph representation learning. In Proceedings of the IEEE/CVP International Conference on Computer Vision, pp. 6519 6528, 2019.
Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. Pointnet: Deep learning on point sets for 3D classification and segmentation. In Proceedings of the TEFE Conference Computer Vision and Pattern Recognition, pp. 652 660, 2017a.
Charles Ruizhongtai Qi, Li Yi, Hao Su, and Leonidas J Guibas. Pointnet++: Deep hierarchical feature learning on point sets in a metric space. Advances in Neural Information Processing Systems, 30, 2017b.
William Rucklidge. Efficient visual recognition using the Hausdorff distance. Springer, 1996.
Kihyuk Sohn. Improved deep metric learning with multi-class n-pair loss objective. Advances in Neural Information Processing Systems, 29, 2016.
Shyam A Tailor, René de Jong, Tiago Azevedo, Matthew Mattina, and Partha Maji. Towards efficient point cloud graph ncural networks through architectural simplification. In Proceedings of the IEEE/CV International Conference on Compuler Vision, pp. 2095 2104, 2021.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine Learning Research, 9(1),, 2008.
Rein van 't Veer, Peter Bloem, and Erwin Folmer. Deep learning for classification tasks geospatial vector polygons. CoRR, abs/1886.03887. 2018.
Remco C Veltkamp. Shape matching: Similarity measures and algorithms. In Proceedings International Conference Shope Modeling and Applications, pp. 188 197. IEFE, 2001.
13

---

Published in Transactions on Machine Learning Research (06/2024)
Volker Walter and Dicter Fritsch. Matching spatial data sets: statistical approach. International Journal of Geographicul Information Science, 13(5):445 473, 1999.
Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay Sarma, Michael M Bronstein, and Justin M Solomon. Dynamic graph CNN for learning point clouds. ACM Transactions On Graphics, 38(5):1-12, 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks?
ICLR. OpenReview. net, 2019.
Yongyang Xu, Zhong Xie, Zhanlong Chen, and Liang Wu. Shape similarity measurement model for holed polygons based on position graphs and fourier descriptors. International Journal of Geographical Infor- malion Science, 31(2):253 279, 2017.
Xiongfeng Yan, Tinghua Ai, and Xiang Zhang. Template matching and simplification method for building features based on shape cognition. ISPRS International Journal of Gea-Information, 6(8):250, 2017.
Xiongleng Yan, Tinghua Ai, Min Yang, and Xiaohua Tong. Graph convolutional auloencoder model for the shape coding and cognition of buildings in maps. International Journal of Geographical Information Science, 35(3):490-512, 2021.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in Neural Information Processing Systems, 33:5812 5823, 2020.
Afra Zomorodian and Gunnar E. Carlsson. Computing persistent homology. Discrete 8 Computational Geometry, 33:249 274, 2004. URL https::////// /etps://api... wew.ssiccchntncool.......o. ort.ssscco....roor//oooopaoao190
14

---

Published in Transactions on Machine Learning Research (06/2024)
Appendix
The appendix is organized into the following sections:
Appendix
Details of Glyph polygons, OSM and Melbourne building footprint datasets
Appendix
B
Model parameters & training setup
Appendix
C
Listing of notations and learnable parameters in ML models
Appendix D
Details of Hausdorff distance metric
Appendix E
Qualitative results that support results in Section
Appendix F
Qualitative results of Non-ML based polygon shape retrieval methods
Appendix G
Persistent diagrams describing the topological features query shapes tested in Mel-
bourne dataset
A Datasets
To evaluate the performance of CGAE, conduct retrieval experiments three polygon datasets and compare model performance with the bascline model GAE of Yan et al. (2021). For consistent shape performance on the three 2D polygon datasets noted below, we center and normalize the coordinates of polygon vertices to the range [].
Glyph polygons. Anonymous (023)) introduce a synthetic dataset of highly variable goometric shapes for model training and evaluation. The synthetic Glyph dataset. consists of 26 Latin alphabet glyph geometries of alphabet letters (semantic class A to Z) of fonts gathered from an online source (Google 2010 Anonymous (2023) extract the boundaries of glyphs for 1,413 sans serif and 1,002 serif fonts, to produce 2D simple polygon geometries compliant with Open Geospatial Consortium (2003). Geometric transformations (i.e., rotate, scale and skew) are applied to 2D simple polygons for data angmentations. Fach glyph geometry sample was rotated by a random angle in [-75", ] sheared by a random angle in [-45", 45%] on the æ and y axes; and scaled by random factor in 00.1,2) 2] on the æ and y axes. After geometric transformations, four categories of datasets are generated, including the original dataset: Glyph-O for original polygons, Glyph-R for rotated polygons, Glyph-SC for scaled polygons, and Glyph-SK for skewed polygons. The four Glyph datasets are combined and divided into a training/ valiaaaiiaaaaeeeeeea set (60 20 20). Examples of glyph
geometries are displayed in Fig. 3
ABC
GHGH
Figure The top 10 samples from Glyph-O datasct semantic class A to J.
OSM buildings. We further use the benchmark dataset by Yan al. (021 for mode evaluation. The dataset contains 10,000 real-world building footprints extracted from OSM (OpenStreetMap contributors, 2023), labelled in 10 categorics based on template matching to letters (Yan et al. 2017). 50% of building footprints are randomly rotated or reflected. We categorize the dataset into: OSM-O and OSM-R, where OSM-O contains 5000 canonical building footprints, and OSM-R contains 5000 randomly rotated or reflected buildings. The dataset includes additional standard polygons as query shapes, depicted in Fig. 4 to evaluate how the performance of CGAE, trained on synthetic polygonal dataset, generalizes to a real-world building footprint dataset, in comparison the GAE baseline.
15

---

Published in Transactions on Machine Learning Research (06/2024)
(a) standard shapes of canonical building polygons.
HENNLLTRYN
(b) standard shapes rotated or reflected building polygons.
Figure 4: Standard shapes of dataset OSM in 10 categories: E, H, T, U, Y, Z-shape polygons.
H.
Melbourne footprints. While the synthetic Glyph dataset includes polygon geometries with holes (i.e., Latin alphabet letters with holes) and dataset OSM includes real-world building footprints without holes, further explore the capability of CGAE in encoding information of polygons with extremely variable shapes and numerous holes for polygon retrieval. We use the open Melbourne building footprints dataset for evaluation (CoM Open Data 2021 comprising the footprints of all structures within the City of Melbourne in Australia (Fig 5).
While these geometries are annotated with semantic labels such as Building structure, Tram stop, Bridge, Jetty, Toilet, Train Platform or Ramp. We only investigate models' performance on retrieving building structures of similar shapes and exchude these semantic categories, as they do not directly map to footprint shape.
B Model Training & Parameters
We train all models for 100 epochs with the Adam optimizer (Kingma & Ba 2015 and initial learning rate of 0.0001. We reduce the scale of the learning rate with cosine annealing schedule (Loshchilov & Hutter 2017) for better model convergence. We set the training batch size b = 32 and apply the same batch size to contrastive loss in CGAE. We set the angmentation ratio r to 20% for both random node dropping and edge perturbation in graph augmentation.
C Algorithm Statement
We depict the algorithmic sequence of CGAE and its relationship with the Equations noted the main paper in Fig, 6
Evaluation Metric
We use the Hausdorff distance metric (Rucklidge 1996) measure the similarity between the query and extracted polygons. The Hausdorff distance has the advantage of taking the position, shape and orientation of objects measured into account when computing the similarity of two geometries (i.e., point sets) (Veltkanpp)
2001 Min et al. 2007). Let A and B represent two closed point sets, and Pa, Ps are two points E A and
B, respectively. - is a distance metric, typically Euclidean distance. The Hausdorff distance (AA, B) e
10.0, +oc] is the maximum of all the shortest distances from Pa E to the closest point ps E B, or formally
(Eq. 10
H B) max(h((A B), ((B, A)}, where h(A, B) max { min ||pa Pbll) P. P.EB
(10)
h(B, A) max { min I|pa -Pll). P.EB PAEA
16

---

Published in Transactions on Machine Learning Research (06/2024)
Figure 5: The map visualisation of Melbourne building foolprint dataset (CoM Open Data 2021 recorded
in May, 2020. Purple structures are bridges and green structures are buildings.
17

---

Published in Transactions on Machine Learning Research (06/2024)
Node Feature Recon.
R-F
Node Recon. Loss (Eq.5)
EdgeConv (Eq.4) MLPs
R-N
Z E N-D
X R.F
EdgeConv (Eq.3) MLPs
Polygon
W E D.F
N-F
A' E RNN-N
Edge Recon. Loss (Eq.7)
W E RFD
(Eq.6): ZZ" E N.N
A E N.N
Pooling:
zo E N.D
Edge Feature Recon.
Contrasti ve Loss (Eq.8)
Figure 6: Algorithm statement of CGAE, which includes listing of learnable parameters and references equations Eq.
18

---

Published in Transactions on Machine Learning Research (06/2024)
E Qualitative Results
E.1 OSM Dataset
We present the polygon retricval performance of GAEs with ten standard polygons (Fig. 4 as queries, on the OSM dataset (Yan et al. 2021 ), illustrating the qualitative performances of baseline GAE and CAGE on the OSM dataset Fig. and S (OSM-O), Fig. 10 and 11 (OSM-R), respectively. We also add the results of the benchmark NUFT method in Fig. (OSM-O) and Fig. 12 (OSM-R).
CGAE handles both simple query shapes well as more challenging query templates when retrieving geometries from OSM-R, matching semantic categories and shapes. In contrast, the baseline GAE only extracts visually similar polygons with correct semantic categorics for simple query shapes, such as Y, U, I, 0 and H, and fails to differentiate shapes with added boundary complexity, e.g., E, F and T (Fig. 10). Baseline GAE incorrectly extracts multiple I and L-shaped polygons as matches for the query template E, and U and I-shaped polygons for a F query shape, as reflected in the high Hausdorff distance indicating shape dissimilarity between the extracted and query polygons.
The proposed CGAE performs more robustly the rotated query shapes and extracts polygons with the correct semantic category for E (Fig. I1 For the challenging F-shaped query, CGAE deteriorates only from the 3rd position (with an H-shaped polygon) and on the 5th and 6-NN (extracting E-shaped polygons). Note that overall, the incorrectly retrieved polygons are still geometrically more similar to the query shape, as reflected by the low Hausdorff distance.
This further illustrates the desired qualities of the proposed model CGAF, i.e., robustness polygon rota- tions, and the ability to generalize real-world shapes (e.g., building footprints from OSM).
We note that comparatively to GAE and CGAE, the NUFT-based method struggles, in the case of the shape of L already at the 1-NN on OSM-O, and produces somewhat unrealiable results on OSM-R (e.g., E).
E.2 Melbourne Dataset
We present the polygon retrieval performance of GAFs the Melbourne building footprint dataset qual- itatively in Fig. 13 and 15 (Melbourne), Fig. 14 and 16 (Melbourne simplified), and add the results of the benchmark NUFT method in Fig. 17 (Melbourne) and Fig. 18 (Melbourne simplified).
For simpler circular query polygons without internal holes, CGAE successfully retrieves geometrically similar polygons for query geometries with low Hausdorff distances (< 0.5) while GAE identifies shapes with a relatively higher Hausdorff distance (> 0.5). With more complex circular polygons with a single hole, both GAF and CGAF successfully identify matching counterparts. CGAE finds highly similar geometries with complex exteriors, while GAE returns polygons with over-simplified exteriors, less geometrically similar to the query templates. This performance of GAE is deteriorating with more and more complex shapes, while CGAE maintains robust performance.
Further, to qualitatively verify that the CGAE is independent of polygonal vertex counts, we present the retrieval results with query shapes simplified by Douglas & Peucker 19733 for Melbourne dataset.
We note that compared to GAE and CGAE, the NUFT-based method underperforms, In particular, we note deterioration of performance when it comes to polygons with holes, where this significant characteristic of the shapes is, inconsistently, neglected.
19

---

Published in Transactions on Machine Learning Research (06/202))
Query Shase
1xt
Vertes OAAEE
Werten PIEN Au
Neste SIMR
Vestea coet:
Vertee DO
VHITA WARH 20
Vertas
Vorter 10-6
Vente 12.6
Vener
13.
194
Hesadefff
Mesedorf
sdort
Handaart
Honndurff 2.0
Hesodbalt dkll E.00
Revodaaft akli 2.11
Resulunt 245
Hiandoon ditt 0.005
Hesrddoff 0.009
Hesodovt dee 8.10
Hiuudoot det 3.000
liks siortt der 34B
iesestont can 803
Vertee muslt
Bucldtonn dat c.dte
(velldeen del E.08
Ese ioeee del 8:00
Exdisies cst R
Vertas count: 32.0
Buckddan ast DOL2
meaelt Raciddio BALL
reeat fucildooe 2.011
Venter cesel 8418
Esc ideae det 8.18
Excksaat
ceadt 126
VerTer COUIE
Viree CaMe DE
Weites EOUNE 2
Nertes connc C.3
Vettes COUPT BOLY
Vertes DOURE &O
WITEE COURT &O
Verion 200 10E Figure 7: Polygon retrievals of GAE-GCN (baseline) OSM-O using ten standard shapes queries.
Vertze
Vertes 380
Weiter (peal) 30
Vertee coeal 20
20

---

Published in Transactions on Machine Learning Research (06/2024)
Query Sheer
3xt
2rd HM
AFR
AM
Vartex
Vertie
Verten
Vertee HARt
123
Hecadart
Henodor
Feesdert
Houadomt
louaderf
Heaadortt cit 8.222
ieundortt sesadom
Hendaall
Hosndell 5.63
Haaseelt dki
Hosssart shi 5.673
Hosssettt oul
Haaddanf din 6.005
Ressderff 2.000
Heksdbeff tur 0.000
Heasdbeff dhr 8.008
Pesssbrtt oul
8322
Resosdett den 833
Vartes doant:
Bei this Haaddstf BiAG
Housdom oit B00k
rosisbert ar 800
reundorf oit1 B.0
tui reassoott 2008
mesisoon
tha 9.09
Weitea COLeR 12.5
fockston dit E/00
ceseti Eucaduel $1100
ceatt Escistia 8
Lecioces den 8:16
113
Vertos DRURR 8J
caum be belii Eutra
Werte ceuet
836
Wetta reed
$245
Vette moen
8:49
Vettr meat
C
Vertes COLFE 13.6
Vertoc CEU4) 1ED
Nertic copet 38.0
Writer creat: 33.0
Vetto coast 10
Martio cea11: 100
Wattor caast 10.9
Figure 8: Polygon retrievals of CGAE-EdgoConw OSM-O using ten standard shapes queries.
21

---

Published in Transactions on Machine Learning Research (06/202))
Query Staus
3et
Ird
Vertes DAVE
Nertes SEO
Vestes
AED
Vertas
Werter 21.6
Venter 12.6
Voner
198
194
lowaddo 1.70
Hesaderff
Heseddomf poort
lexsiot
Hisobeeff E.00
Resoobett ski
Hos unert
Hesukunt
count
The 50l0 Heandaoft din
Insaddortiil dee E.014
Heuudovf dre 6.144
Hissadort del 3,000
liks
sioue skll 8400
llsescont den 603
Weitew must
bulldionn Ban 0.000
cound fucidiia E.00
tve Melldee dil 2o0e
clidee &Ce vul
Ehe lobee del 8:000
Exdiccer cst 3
Verter count: 32.0
Baciidaoo 3it ba0e
rovet Reciddon B401
reeat: laboss L.00
Saciddess de 8400
sic loea det 8400
meatt Secicias EE0
VETTE DAUIE 3.0
Vurse cauee 3.
Nertee CAIE 2/0
Venarccust 21D
Vertes DONE &O
WItTE DOUR &O
Werte 11.6
Uedee 38,0
30.
Wetee creali 35
Vistoe conal
Vorinc CEP
Badiy Inc
Figure 9: Polygon retrievals of NUFT OSM-O using ten standard shapes queries.
22

---

Published in Transactions on Machine Learning Research (06/2024)
Query Sheer
3xt
2rd HI
3Hd AFR
AM
Vartex
Vertic
Verten
Nertee
Vertee sARt
Wette
Nendame
Recadamt
Henodor
Peesdort
Houndorf
iouaderft
Hiaadorf Cit
inuadortt Resadom
Hendeell snis
Hoandell Hasskelf uki
Hossbett osl
Haaddatf thi 6:501
Pessderff dei 9.3
Heksdbeff tui 5.1
Heasdbeff dirt 9:404
Pessdortt cut 8.32
mesoddett dan 459
Vartes cuant:
the this Haaddsit B.1V
Houssomt oit Buck
resisbert ar L.v
reandorf oit1 8u22
reassoott ost 2.40
mesisoon
dhl 8.82
Vertee ousti
Ducktion M51 C013
fueidiie den cnt
(ucadoe dif B005
Escliiee 0811 8006
Esclaces den B.0
Excidias 00 0.0
Vertic COLIE: 12.0
Verter reaeh 12A
Neviin meeen: BADE
Vinter reset:
Ventow ceaen (015
Vomen cesem 8.13
cease Extiabes 2214
Varteu couati BLD
YUrto CUUE: DE
Nettee count Ea
Wi creat: 32.0
Wetter CAUE Sol
Wetter DOUFD &J
Witter CUeR EQ
Figure 10: Polygon retrievals of GAE-GON (baseline) on OSM-R using ten standard shapes as queries.
23

---

Published in Transactions on Machine Learning Research (06/2024)
Query Stase
1xt
Neste SIMR
Vestea coef:
VHITA HARE TO
R
Verta
Vorter 140
12.
Vente
Venee 11
1E0
Hoardooff
Misedooft
adort
Resalort
Handart
Handdarff
Hosndaaf dki. E.89
Rosddarf akl 8.333
Resulett 38c
count:
Hiandtont din 0.211
lesuddoit dee 8.200
Risusoof der 3.305
liks sdort der
8-203
Iesestont can 252
Vertee must
Bucldton tet 6.170
del 5-000
(velldeen aks E.54
cueldie oni 3:308
Exe ineee del 8332
Exdisies cst
0.2
Vertex count 9.0
Bucidtao sst EAU
covall fuciidiol Baku
lucildiss dil E080
Bucildes dil 8.124
Ese ioeae det 8:25
Excides 8.25
VertE count: 12.0
Vertec coont: 12.0
Wertec couert 12.0
Witter coeat: 32.0
Vinto coUnt 120
Nittoo count: 12.0
Mox capat: 12.6
Vertes
32.0
Wotee Leed:
Votee
Vortin ceasl C&D
Figure 11: Polygon retrievals of CGAEC CGAE-Edgeeoon OSM-R using ten standard shapes queries.
24

---

Published in Transactions on Machine Learning Research (06/202))
Query Stase
3et
ventes DURE
Vente sEAR 25
VeON CONEECORE 23
NErOA coat SED
Nest LSE
Verta
6.4
Vertica
L&D
Vetter 46
Halndoof
lowerdo Gick
Hesaddeff K.0k
tiseddomf
Handart
Manokelf EXT1
Reoobatt ski 9.13
Hos unert
Hesukut
Vertes sount
Heandauft din Cuilo
Heundorf dee E.00
Hit Hiroddot del 1.50)
lies sdoff
dkl 8-32
fesescnt cen 838
Veiter must
belldion Ban E,07
couftt fuclddie 8.00
cesat: the Sdoan uki. E.07
clllee te 2.03
the loee det 8.33
Exckcerr cot 2011
Vartex sount s.p
Baciidao 3at EAUi
roydl Baciidio 6004
licis oNl E.0
Saciddes de 8400
sic lous dit 8200
mest
UWINN COUrE: 12.0
Verter CRenc 12.
WertEc count 35.0
Mertue coanc CORA
Verarccus: BOTS
VETTo coUTE 21D
Ne CEaTT L2
Vestre KE
Wnteetore 24
Wetee creali 3ED
Vetee CNRDI
Vortin contt 12B
Weter meet AO
Figure 12: Polygon retrievals of NUFT OSM-R using ten standard shapes queries.
25

---

Published in Transactions on Machine Learning Research (06/2024)
Qvery Shaer
3xt
2rd
APV
AMV
Vertex
coaRt 27.
Vertee zoee
Vertie
Nertow 50
31.
16.
RED.
Recadort 8.00
Henodor Feesddrth
Houndort B505
touaderft det EAC
Hisasdort citt
ieuadortt Resadort
Henudall skis
Hosndell 5.003
Hosskelf uki
Honssaaf chi
Posssbttt osl
Heaudarff din 6.606
Ressderf 8.874
Heksdbeff der 8.5
Reasdbeff dar1 9:42
Pessdurtt out
Resodeett den 0.004
Verte count
Houssom oet Blora
sos misosoort ar 5.502
reandorf oit1 9.88
reassont ost 2.95
mesisoon
thi 8.59
Wertes Court 205
Dociltionn dit E.0
Ebeiidicaa den BA01
ceseti Excadoee 2003
Luciaces den 8.16
Vertes count: 100.0
baciiton Wil E00
reeen faciidis RAMS
reed ducillos 200e
Vette moen
Vedrr meat
Verteo CounT. 159.0
Yurse CUIE CE
Wertic copet: 28D
Wittr CODE 2015
Wetees CAUE SolE
Wutte DOUFD &J
WUTTA CRUIT 40.9
Figure 13: GAE-GCN (baseline) polygon retrieval on Melbourne building footprint dataset.
26

---

Published in Transactions on Machine Learning Research (06/2024)
Query Shape
Sel MN
MV
BAA HM
Vertee COunti
Nortor coalt 1.
Aetter soatt 6.377
Tertin care 0.03
Verten care do
Netter can do
Nerter moaal
5.3dd
Hocobort als 1.00
Hewdurt ou 0.30
Headdaff ou 9.84
Peestteni dan 6dde
Peesoort dis 6.76
Vertas coant 23,0
Vertec coent
0.11
Vernec soert: 38
Veroo DACR 2.3
Vento comp 50
Wetter capet 6203
Vettex copst 5-24
Hesoaboft 0.578
Honddorf cuh
dit Fessslert 64613
Vertex count:
Verter mest Coco
Weter reave A.dd
racee Euckitoon dea
Wette roaer 2009
Witter cavee Eoee
Vitter reaet Cuko
Hocsbetf ell 0.123
Hovdduft es OLECE
Henddatf cul
Pesssurtt Bll 6-03
Vertas
Vertes coart: $5.0
Suoldtes 4E 0:18
Burt 4C 0.311
1oued Buckdaon 011
rowd) fectiean 101
reyah Suciooas E01
Figure 14: GAE-GON (baseline) polygon retrieval on Melbourne building footprint dalaset simplified by Monglas-Peucker algorithm (Dogllas & Peucker 1973 with = 0.00002.
27

---

Published in Transactions on Machine Learning Research (06/2024)
Qvery Shaee
3xt RM
3nd HM
3rd ArV
AM
Vertex count:
Nerten caat 84
Vertes cover &Jl
Vertin cwee
Verten sourh
Nertee pours Ed
Ventee reath 6.0.
Vertea count:
Virter
Nerter 216
Wetter 1100
Hemddrtt
Recpdort 8:86
Hauadert del
Henodort cit1
Peesdorth
Recadent 343
Hf E.000
Houndomt B311
iouadeeft dic 1.30
Hmandort cit B
ieundorf 3:52
sessdom 2.34
Handaall skis E.004
Hosnddedl skd. 2.013
Hosssell dki 2.003
Hoansaalt chi 5.400
Posssettt osl 1.5
Resadelt 4.44
Haaddartf tiir 6.006
Ressdarff der 6.00
Haksdbeff tui
3-500
Reasderff d0r1 9.183
Pessdortt dul 3.34
Ressdertt den 341
Vertes count 74.6
the dhis Hesadoott B.10)
Houisoom dit 0-107
resisbort dr
5:144
Heandoof 0311 0.277
reassort ost 2.27
Residom 247
dei
Wertes court 225-
Selidiica den 1In
cRaeli Eacadue 2:14
ceatl Escistaa BIEE
Lsciaces de 8211
Vertes count: 100.0
Sontin besiiii del E.5
reeen fuciidia 6.244
Vitte resat 2356
Vedty casmh
2214
Vonw cesem 2258
casm: Exttalas 5255
Veiteo count 159.0
Surtee CRand 150, Bioiii
Mertoo coant 127.
Wette CAAE 2.11
NeTte core: 115.0
Martin CEa1: BLB
Watte cRAST 42.8
Figure 15: CGdE-Edgoonn polygon retrieval on Melbourne building footprint datasct.
28

---

Published in Transactions on Machine Learning Research (06/2024)
Qurry Showe
S44 MN
2nd MV
AM
41h 30h CIA NN
Werter coant
0.006
Wortee CoART 6,900
marte coee 233
Nett coue L.
Verter cla A.
Verte coant C-313
Hesubutt
Hawduul pur
5,00
Hann and del
225
Hecubult cat 6.111
Vetees count:
33,0
Wervin caent
Wetee cur
Vettec 0227
Worte owen 20
Vetter coae E343
Verne capnt
5,26
Veries
Hessabett aua
Handdart the
Hann ailt dui 3.38
Readeall
15.1
Vertes count:
22,0
Varter capet
Sude
Vetee raye Bede
reset backibus B
Martey moee 10.8
Vontes cuse caas Bold
Varve secasas e1G 5-26
Resubrtf eul
Mondall
Readdat 0.30
Hossbelf ell 0.00
Wrtta
Vetter
Verter 27
13
17
Vertes COLPE: $5.0
Wetee read SLAY
Bockaae 001 212
ALCICONv BEL E.42
Verie dtc CU46 Rocubalt
Figure 16: CGAE-EdgeCony polygon retrieval on Melbourne building footprint dataset simplified by Nouglas-Peucker algorithm (Douglas & Peucker
1973 with e = 0.00002.
29

---

Published in Transactions on Machine Learning Research (06/2024)
Query Stass
Vertes ONAEE
Vertes seaet 38O
Vertee maae Bu
Nestee sier
Vestes coert
Vertee SO
VeTte WAth EO
Vertex counts
Vertee
Nerten
Vertes
Vertes 66
Hoandorf
adort
Resalorf
Hesndaalt dkil E-4
Resodarf akl
Mossieel Resuubeff onn
Resulutt
Vetter
Hiandtomt din C.066
Hesrddoft Heundov dee 8.700
Hi Risusoot der 9.302
liis sdort de 3.429
Insnson cen 648
Vette coart:
huciddue Wel B.D0
coeat: Duildoon dks $.305
Ext leeee del
2.38
Exeloces cot
Vertex
count: Corte:
225.0
caatt Buckidann E.M
covel faciidiot 6.0s
ducildos dil Lobe
Bucildes dil R408
Esc loeae det 8200
Exckeaa EAC7
ceadt
Veitea count: 100.
Virtes caMe 6.E.
Werter countt 34.
Nertee counc crees
Vinoo ceset 290
Nertio coust: -3.0
Marto ceper 11.
Verte COUnT
Vandow Coueth 190
Wetee cordl
Wotee ceed
Vistae (oaa)
Wetter 70
Witte owrti &o
Figure 17: NUFT polygon retrieval Melbourne building footprint dataset.
30

---

Published in Transactions on Machine Learning Research (06/2024)
Query Shipe
So4 HV
MV
54h
Vertee counti
Nerter crea
0.000
Verte care d-
Metter cata dud
Vertee mtaal 5.303
Hosabolt als 6.002
Hevddurf cun 0.600
Hendalf ou 0.30
Bevsderiidn
Peestlent dat 6:30)
Fessoort Bis 6.16
Verta coant 23,0
Vertec crent
6:311
Vertic COUPT: 801
Wortee coant 251
Wirtes moee 13.8
Wetter copre 7.
Vertex copst C.3d
Hesoabrft 6.700
Honddorf duh
Hemddaaf
Vettes count 22,0
Verter mese
Coca
soart Builhie 6.00
rocee Euckitoon da3
Wetter roaer 1003
Witter cavee Eoet
Vitter meaet Cuice
Hosseet ell 0,113
Hovduut esi 0.75
Hemdaaf oul 9.72
Reusouct ail 6.70
Pessoutt Bls 6.701
Vertas
Vertes coare $5.0
Buoldtes 48 0.06
Wetey reare
0.00
1004d: Buckaao 0 203
meath fucidean $208 an
repel Suciooas 6013
Bucidess At 6.11
Figure 18: NUFT polygon retrieval on Melbourne building foolprint datasel simplified by Douglas-Peucker algorithm Douglas & Peucker 1973 with e = 0.00002.
31

---

Published in Transactions on Machine Learning Research (06/2024)
F Non-ML based Benchmarks
For completeness, we present the qualitative polygon retrieval performance on the Melbourne dataset, using the turning function AArkín et al. 1991 in Fig. 19 (Melbourne) and 20 (Melbourne simplified); and using
the Procrustes method (Goodall 1991 in Fig. 21
Melbourne) and 22 [Melbourne simplified).
F.1 Turning Function
The Turning function (Arkin et al. 1991 (TF) measures the tangent angles of polygons with monotone function where function valuos increase for left-hand turns and decrease for right-hand turns on polygon boundarics. The accumulated function values (i.e., are length) are used to compute a distance function (i.e., Fuclidean distance) for comparing two simple polygons. This method typically robust. under rotation, translation and scaling but sensitive to non-uniform noise.
Qualitative results in Fig. 19 (Melbourne) and 20 (Melbourne simplified) suggest that TF performs poorly polygons without clear turning signals (Fig. 19 row 2 - 4) but performs relatively well on simplified
polygons with salient turning signals (Fig. 20 row and row 5).
F.2 Procrustes Method
discovers optimal geometric transformations (i.e., rotation, scaling and translation) that minimises the disparity (i.e., the sum of square of the point-wise differences) between two geometries. The Procrustes method retrieves geometries based on finding the nearest neighbours of queries with disparity as distance metric. The qualitative results of Procrustes are shown in Fig. 21 (Melbourne) and 22 (Melbourne simplified). Experimental results suggest. that Procrustes is not suitable for handling complex polygons with holes the retrieval task.
Procrustes analysis (Goodall) 1991
G Persistent Homology Diagrams
To quantitatively mcasure the topological signatures of polygons (i.c., OD connected components and 1D holes), we display the persistent homology diagram of the 10 query shapes of the Melbourne dataset in Fig. 23 Sub-figures (a) (e) show persistent 1D (H₂) topological features, suggesting existence of holes in
queries. Sub-figures (f) (j) show persistent topological features in both Ho and H,, suggesting polygons with complex exterior boundaries and holes.
We refer the computation persistent homology of data E IRd to Zomorodian & Carlsson 2004
32

---

Published in Transactions on Machine Learning Research (06/202))
Query Stass
Vertes ONAEE
Vertes SANEE DED
Werten sian BJ
Nesten sier
Vesten coeet
VHTTE WATH EO
Vertex counts
Worker 210
150
Nerten
Vemee
174
sdort
Reealort
Hosndaaf dki. E.80t
Moxsiion Resuubeff ourr
Resulunt
Vetter
Hiandtomt din 0.006
Heurddoff 0.35
Heuudovr dre 8.77
Hiuudoot der 9:004
liss siort der
8-588
Iesesoont cen 629
Vettee coart:
Bucldton det 1433
fuciddue Wil 100
coeat: Dueldoon 3.007
Cueldie 1-00 aNd
Exc leee del
18.0
3.30
Exeloces cot
0.411
Vertex count: 223.0
Backdaon dtt E-17
coaett faciddio 2.14
aud fuciddose 1.31
caued lncilduss 1471
Mottes ideae det 2468
Mettee meet 1124
Veitea count: 100.
Namtec cRUnE LOCB
Verter couett 34.0
Witter coeat: 30
Vinto cesen: 26
Vertee count 30
Witte Doent: &O
Vertek COURT
Variow Coaeth 190
Wetee cordl X8
Watee Lned
Verioneent 2&D ISE Vatta cENa) 25
Figure 19: Polygon retrieval of Turning Function Melbourne building footprint dataset.
33

---

Published in Transactions on Machine Learning Research (06/2024)
Query Shipe
So4 HV
MV
50h
Vertee Count)
Nerter coett
0.900
Tertin cared 031
Verte care dd
Metter can dul
Nertee moaal 6-311
Hocabolt als 6.79
Hesdurt cu 0.13
Headdalf eu 9:44
Fessourt dis balt
Verta coanc 23,0
Vertor coart 12.0
Wette squre Brck Bls
Vortee coant 15.
Virtes meet 21
Vortos court: 22.8
Vartic coure 12.0
Honndorft duh 0L130
dEt Revudarti
Reanderrt dal
Pessotert 0.714
Vettes count 22,0
Virter cll Cu0
Mortee reast 201-2331
Wirtes meen 2309
Vomts ctre 6008
Vitter meset C.18
Hossbrtf etl 6.13
Revduutt esl 0.80
Henddaff cul $.39
Reusoutt
Pessoutt Bls 6013
Vertas
It
Vertes CoAPE: $5.0
Buckitus 4d 0.17
Buckdao 011 1.34
meat fucidean 2.31
Aucionas att 1013
Bucidbus et 1316
Figure 20: Polygon retrieval of Turning Function on Melbourne building footprint dataset simplified by Douglas-Peucker algorithm (Dogllas & Peucker 1973 with = 0.00002.
34

---

Published in Transactions on Machine Learning Research (06/2024)
Query Stass
1xt
Vertes OOVEE
Yesten HOUID BE
Verten DOAIE B-
Nasten GHeR
Vettea coutl E404
Vertee more: R.C3
WITTR DARE 60
Vertex counts
Woneer 115-
Mortor 1004
Virtes 2044
1840
Venio RCD
Vatte cwrtd 1450
Hisaddrff
Hiuadorf
Resstot
Iepprtty
Hasoobalf E.77
Hasodarff ski 8.42
Hosubbeff Mosulbat 0.438
Vette
Hourddofff E-066
Hiundon of dec
Hicodoof det
sioor cer
seandorf car 3a5
Vettee coart:
Slipardy skis Eusde
Sispertyy 2.5E aul E-R5
Departhy del Ed4t
Dapentt oul 2.14
Disprtt & Mas 1885
3LD
Disarity a
0.393
Vertex count: 223.0
Waddey caasl: Rkiparyy SODE
Wartor cardl begandy: 8-73
Veries beiaaity 5:6 E:000
Wettes cuedd
ceast Dispanty 8.23 Hits
Disauiiyy 4374
ceart
6:200
Veites count: 100.
NETOO CRUNC LO0
Nertta chare: 100U
Vinter coent tee
Venor CRUST 340
Verto cRast GLD
WITte DUUEE 176. Dasrry
Vanine CRart: 190
Yor 2100
Vertoo
Water
Veconcoust 32.
WItEe UNEG 180,0
Figure 21: Polygon retrieval of Procrustes method on Melbourne building footprint dataset.
35

---

Published in Transactions on Machine Learning Research (06/2024)
Query Shipe
So4 HV
MV
54A
Vertee counti
Verter mes 0.00
fartes mort aM
Verter soald de
Wetter dern 6.dd
Vetted Poea 8-000
Henobell tei 6a13
Hemsaeli de 0.827
Hemdaal cu
Beander del
Pessoett thi 6.11
Verta coanc 23,0
Vertor cRaRE
Wettr cRUrE 24
Wortee coant 203
Wirtes moet 21
Vento court 28
Vento caurt 1E0
Hondootf du
Hamddaaf est 0.0
Readart
Pessoaat 6.333
Vertes coent 22,0
Venter coaet
Eliparty &JM
Weter reuve 20
Wiite reast $J2 432
Wittes must EJE3
Votus mort dearii E-C
Vorte caure Slepatty 6-12
Honoeel Eize
Handdoff cut quepa
Hamidalf 0317
Reaider
Possourt ai 6.703
Vertas
Metter
Votee
5.12
Varter
Vertes CoAPE $5.0
(Rad: Eltgatty 241
Weter reaen Bigasty 0LE23
crast (ipurtty 242
meall 15. Dipprroy
Toitee Diganto 6.06
Viite caadd Ripurlty 0.11
Figure 22: Polygon retrieval of Procrustes method on Melbourne building footprint dataset simplified by Doucles-Peucker algorithm (Doullas & Peucker 1973 with = 0.00002.
36

---

Published in Transactions on Machine Learning Research (06/2024)
1.5
1.5
HD
Death
Death
0.5
Birth
Birth
(a)
(b)
0.8
Death
Death
0.4
0.4
0.2
Birth
Birth
0.4
Death
0.4
Death
0.3
0.2
0.1
Birth
0.4
0.5
0.6
0.1
0.2
Birth
0.3
0.4
0.5
0.3
0.4
Death
0.2
0.2
0.1
0.1
0.1
0.2
0.3
0.4
0.05
0.1
0.15
0.2
0.25
0.3
(9)
0.3
Deeth
0.3
Death
0.2
0.1
0.1
0.2 Birth
0.3
0.05
0.15
0.2
0.25
Birth
()
()
Figure 23: Persistent diagrams (a) (i) of query shapes (row 1 -10) of Melbourne dataset. Persistent
diagrams (Zoorodiian & Carlsson 2004) is a plotting of multi-set of points that summarise the topological signatures of irregular data X R (i.e., 2D or 3D point sets). Birth (X-axis): time when data point P E emerge. Death (Y-axis): time when data point P E X disappear. Ho: O-th dimension topological feature that summarizes the number of connected component of data. Hi: 1-th dimension topological feature that summarizes the number of hole/loop in data.
37


Reviews:
[{"review_id": "WXGGwz18SP", "reviewer": "Reviewer_5JPo", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is overall well written, I was able to easily follow the proposed method and retrieve the information I needed \n- The method is above the competitive methods for all datasets\n- The authors show the same ablation study for three datasets, which is not common but shows consistency\n- The proposed techniques are technically sound\n- A large-scale real-world dataset is used to validate the method\n\nWeaknesses:\n- The gains in performance are dominated by the use of a better backbone (EdgeConv). The contrastive loss, although it seems to help consistently, it can decrease the Hausdorff distance by as low as 0.001 (table 2, 2-NN, line 5 vs 8)\n- There are no standard deviations in the results, making in impossible to know which performance change is statistically significant.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work is about polygon geometry retrieval, which is useful for the building footprint retrieval task. The authors propose the contrastive graph autoencoder: A graph autoencoder that is used with contrastive learning and it consists of a message-passing encoder, one node decoder and one edge decoder. In order to create the contrastive pairs, the authors propose the use of graph augmentations. The proposed method is tested in three datasets including a large-scale real-world dataset and it beats the two competitive literature methods consistently.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Critical for acceptance:\n- I would like to see standard deviations on tables 1-3 and a discussion on the cases that the decrease is not significant (if any)\n\nNon-critical:\n - Unorthodox references. Just remember not to keep the \"Anonymous\" reference in the final version of this paper. Also there are references with \"(Poster)\" after a conference. The references are about the proceedings that include the paper, not about how their authors presented their work in the conference.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "0wM5cN2PrG", "reviewer": "Reviewer_RWhc", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nThe proposed method is novel; its components are described clearly, with reasonable motivation for each\n\nExperiments show that the proposed contrastive loss results in cleaner separation of representations of similar polygons than a pure autoencoding loss\n\nExperiments show the proposed method achieves better retrieval performance than the included baselines, according to Hausdorff distance between the input and retrieved shapes\n\nThe method is also found to generalise (without further training) from synthetic (glyph) to real-world (building footprint) datasets, still out-performing baselines in the latter setting\n\nThe paper is clear and pleasant to read throughout; it is well structured and the figures etc. are clear and legible\n\n**Weaknesses**\n\nThe method described is a simple composition of existing, well-understood ideas – message-passing graph neural networks, and contrastive training objectives. This is not an issue per se, but there is not much insight for the reader here, e.g. how to choose a particular variant of contrastive objective that is particularly suited to GNNs, how to choose good node features for the particular task, usefulness of different augmentations in contrastive loss, etc. – it is just a description of one method that works (plus some ablations). This is particularly problematic for TMLR, where most readers are looking for insights on how to develop ML models for other domains (e.g. general graphs rather than polygons from GIS systems), rather than a domain- / application-specific 'cookbook'\n\nThere is no rasterisation-based baseline, i.e. a large pretrained-then-finetuned CNN / ViT operating on 2D images of the polygons. This is a very natural baseline, since rendering polygons is exceedingly fast on modern hardware, and it would benefit from the vast body of research on CNNs/ViTs for images. Currently I think it will not be clear to the TMLR community why the chosen setting of operating directly on polygons as a graph is worthwhile\n\nAlthough invariance to rotations is claimed, this is not parametrically guaranteed in the model, and the results are difficult to interpret. In particular the evaluation metric, Hausdorff distance, is *not* invariant to rotations / reflections, and it is unclear how it is being used here to verify this", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work considers the task of learning an embedder for 2D planar polygons; similarity of embeddings can then be used as a metric for retrieving similar polygons. The proposed autoencoder is a graph neural network that passes messages over the graph of polygon edges to encode and decode shapes; the main difference over existing work is use of a contrastive training objective in addition to the usual autoencoding objective. The method is evaluated on shape retrieval on three datasets, and shown to out-perform baselines.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Either add a rasterisation baseline (render polygons as some fixed resolution, then use a large-scale-pretrained CNN/ViT, maybe fine-tuned), or some convincing discussion of why this is impossible, impractical or irrelevant\n\nThe claim about robustness to reflections and rotations is surprising – as far as I understand, there is no reason to expect the model to have any invariance to reflections. This needs properly addressing, e.g. by giving a convincing explanation of how this invariance can arise, and/or showing that augmenting the dataset with reflections doesn't help further (or work as an alternative). Also a more detailed explanation of how the OSM-R experiment shows this empirically would be beneficial", "broader_impact_concerns": "None -- this work does not raise any significant concerns (nor is there any broader impact statement present)", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "KpDsZV5EBf", "reviewer": "Reviewer_CMBY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The testing of the method seems pretty extensive, and ablation studies show that each part of their method seems to be necessary.\n* The method can handle shapes with holes, and can allow matching across shapes with different numbers of holes (perhaps desirable if there are small holes that are just noise), due to the contrastive setup with its edge and node perturbation.\n\nWeaknesses:\n* The application scenario is quite narrow. The method seems like it could be useful for other applications, but the authors do not explore this. IMO, this presents a simple opportunity for improving the impact of their work.\n* It's unclear to me if the method is robust to rotations and reflections as claimed (see below).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors provide a model for polygon retrieval in a GIS setting. The model encodes polygon shapes (with holes, potentially) with a graph autoencoder. The most effective version utilizes an EdgeConv message-passing convolutional architecture to generate embeddings, and a contrastive component that allows for perturbation of nodes and edges. The method is compared against two similar methods, GAE and NUFT, and outperforms on three datasets ranging in complexity.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Clarification around the invariance to rotations and reflections is necessary in my opinion:\n* Why is Hausdorff distance the appropriate error metric? From the text and App. D, it is not clear to me that rotations are factored in. The Hausdorff distance between a polygon and its rotated copy could be quite high, but presumably you still want retrieval of that shape? If there is some sort of minimization over rotations and translations, this should be represented in (10) of App. D.\n* Perhaps the clearest demonstration that I could imagine is to augment the test dataset with exact rotated copies of existing shapes, and to see if the method returns those as the 1-NN. I would imagine that this is the desired behavior. Could you try this experiment?", "broader_impact_concerns": "I do not think any broader impact statement is necessary.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces a Contrastive Graph Autoencoder (CGAE) for geometric shape retrieval. The proposed CGAE consists of a message-passing encoder and a node and edge decoder. The main contribution is the introduction of a contrastive learning method based on graph augmentations. The method is evaluated for shape retrieval on three datasets and shown to outperform baseline models such as GAE and NUFT.\
The paper initially received mixed ratings. Reviewers appreciated the relevance of contrastive learning but raised concerns about the relevance of the Hausdorff distance and the proposed model's invariance to rotations and reflections. They also noted the limited improvement of the approach, questioned its statistical significance, and requested comparisons to other baselines, e.g., rasterization methods using image-based models like convolutional backbones or vision transformers.\
During the rebuttal, the authors provided standard deviations of reported results and clarified the claims regarding invariance but argued that comparison with rasterization methods was outside the submission's scope. After the discussion period, two reviewers recommended acceptance, while one reviewer recommended rejection because they were not convinced by the invariance properties and the experimental validation.

The AE carefully reviewed the submission and discussions. The AE considers that the contrastive training is an interesting contribution for learning GAE in the context of polygonal shape retrieval, which is especially relevant for dealing with shapes with a varying number of holes. The overall framework is sound, and the improvements shown in experiments over the baselines, although not huge, are consistent across datasets and are especially pronounced for complex-shape geometries with holes. Although the comparison with rasterization techniques would have been a plus, the AE also acknowledges that it is not strictly required to validate the claims. Finally, the authors clarified that the approach is not invariant with respect to rotations or reflections, but that CGAE is empirically better able than GAE to generalize to rotated versions of inputs on which the model was trained, which the AE finds convincing. Therefore, the AE recommends acceptance under minor corrections, including a final proofread for adapting the claims and correcting typos, e.g., "With evaluate how the performance of CGAE" p. 15.
Decision: Accept (poster)