<figure><img src="image_1.png" /></figure>

HAL
open science

# Can Graph Convolution Networks Learn Spatial Relations?

Azelle Courtial, Guillaume Touya, Xiang Zhang

<figure><img src="image_2.png" /></figure>

## To cite this version:

Azelle Courtial, Guillaume Touya, Xiang Zhang. Can Graph Convolution Networks Learn Spatial Relations?. International Cartographic Conference, International Cartographic Association, Dec 2021, Florence, Italy. pp.1 - 2, 10.5194/ica-abs-3-60-2021. hal-03522030

HAL Id: hal-03522030

https://hal.science/hal-03522030

Submitted on 11 Jan 2022

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_4.png" /></figure>

# Can Graph Convolution Networks Learn Spatial Relations?

Azelle Courtial<sup>a, *</sup>, Guillaume Touya<sup>a</sup>, Xiang Zhang<sup>b</sup>

**Keywords:** Spatial relation, Convolution graph neural network, Building Alignment, Roads network selection

**Abstract:**

Maps are composed of spatially related geographic objects. Spatial relations are key information for human as they support the description of relative locations: the house is to the east of the city centre, near the interchange, or at the end of the path. Consequently, preserving these spatial relations is important during map generalisation. For example, building typification is a generalisation operation that seeks to reduce the quantity of building while preserving relation between and within homogeneous buildings groups (Regnauld, 2001). Building or road patterns are remarkable distributions of elements in the map from which high-level concepts and semantics (e.g. landuse types and urban morphology) can be inferred. Such patterns can be characterized by spatial relations (e.g. proximity, similarity and continuity of these elements) and hence are visually easy to identify by a human. To identify these patterns automatically is important for automated map generalisation (Christophe and Ruas, 2002). However, it remains challenging to devise algorithms that can resemble the human level performance. The goal of this paper is to illustrate the potential of graph convolutional networks (GCN) for the identification of patterns and relations important for map generalisation with two use cases: building patterns detection, and road segment selection. Both tasks require some degree of understanding of the spatial relations between map objects. Hence, our experiments constitute a first step in exploring the capability of deep neural network for learning representations of spatial relations.

GCN are specialized in analysing nodes and adjacencies in a graph to predict node or graph level information. These networks have already been employed for the detection of regular blocks in urban areas (Yan et al., 2019), and for the encoding of building shape (Yan et al., 2020). The GCN uses as input a feature description for every node, summarized in a feature matrix, along with the adjacency matrix of the graph. For each layer, the features are encoded by the matrix product of the previous layer features and the adjacency matrix, so that the value of a node depends on its features and the features of its neighbours.

In our first use case we want to predict the relation between buildings (belongs to a straight, curvilinear, or no alignment). In map generalisation, proximity graphs are often used to analyse urban structures. The most frequently used structures are variations of Delaunay triangulation (DT) presented in figure 1. DT gives a more complete view of the proximities between buildings but not all the edges of this graph are necessary to identify alignment structures.

<figure><img src="image_5.png" /><figcaption>Figure 1. Different proximity graphs in a simple situation of two parallels alignment perturbed by a building without relation.</figcaption></figure>

Relative neighbourhood graphs (RNG) connect the nodes that are at least as close to each other as they are to any other points (Toussaint, 1980). However, as shown in Figure 1, some edges being part of alignment are often missing in the RNG. We consequently propose a proximity graph (illustrated in Figure 1(c)) that fixes this problem based on RNG and refined by adding the edges from DT that are short enough, following the criteria proposed by (Bader et al., 2005).

Then, GCN provide a classification of the nodes, but we are interested in classifying edges. So, we propose to transform the graph into a kind of dual graph (Figure 1(d)): for each edge, we create a node, and we connect each node that are connected by an edge in our proximity graph.

<footnote><sup>a</sup> LASTIG, Univ Gustave Eiffel, ENSG, IGN, F-94160 Saint-Mandé, France, azelle.courtial@ign.fr, guilllaume.touya@ign.fr</footnote>

<footnote><sup>b</sup> School of Resource and Environmental Sciences, Wuhan University, Wuhan 430079, China, xiang.zhang@whu.edu.cn</footnote>

<footnote>* Corresponding author</footnote>
We also compute some characteristics for each node that describe the similarity and continuity of elements: the length of the proximity link, its distance and relative orientation to nearest road; the distance and facing ratio (Wang and Burghardt, 2019) between the two connected building; and the size, orientation and elongation difference between the two connected buildings.

We conduct our experiment for a dataset of almost 10,000 buildings extracted from OpenStreetMap in urban and suburban residential areas in the United States of America, where buildings have a regular organization. The graph for training is composed of 13993 edges labelled as “no alignment”, 2976 edges labelled as “straight alignments”, and 2010 edges labelled as “curvilinear alignments”. Figure 2 presents the annotation and the result. The results are not yet satisfying: the accuracy for edges not belonging to alignments is good, but the classification misses many edges that are not aligned. The separation between straight and curvilinear alignment seems to be well understood. Finally, the aligned segments at the extremity of a dead end are always erroneously classified.

<figure><img src="image_6.png" /><figcaption>Figure 2. Annotation (on the left) and prediction (on the right) for GCN building alignment detection</figcaption></figure>

Our second experiment is about road selection. The goal is to predict for each edge of the road network if it is kept or deleted at the target scale. For this use case, each segment of the road network is transformed into a node of the graph and is described by its length and importance as its feature vector. When two road segments cross each other in the network, an edge is added between their corresponding nodes in the graph.

For this experiment, the dataset is composed of roads from a map at the 1:25,000 scale, and their generalisation at the 1:50,000 scale in urban, suburban, and rural areas. This road network contains 12,837 edges (55% that should be kept and 45% that should to be deleted). The results are presented in Figure 4. The classification accuracy is around 69%, and the results are visually satisfying. Selection in rural areas, city centres, and the removal of dead ends, worked well. However, some unexpected disconnections remain in small isolated villages.

<figure><img src="image_7.png" /><figcaption>Figure 3. Annotation and predicted probability of being selected for road network selection.</figcaption></figure>

To conclude, our experiments show that GCNs are interesting tools to learn the representation of some spatial relations and map generalisation. However, some improvements are necessary for both use cases, as the choice of the features added to the graph nodes can be optimised, as well as the amount of training examples. Moreover, we plan to couple these techniques with generative adversarial networks (Courtial et al., 2021) to generalise roads and buildings at the same time while preserving structures.