Spatial Heterophily Aware Graph Neural Networks
Graph Neural Networks (GNNs) have been broadly applied in many urban
applications upon formulating a city as an urban graph whose nodes are urban
objects like regions or points of interest. Recently, a few enhanced GNN
architectures have been developed to tackle heterophily graphs where connected
nodes are dissimilar. However, urban graphs usually can be observed to possess
a unique spatial heterophily property; that is, the dissimilarity of neighbors
at different spatial distances can exhibit great diversity. This property has
not been explored, while it often exists. To this end, in this paper, we
propose a metric, named Spatial Diversity Score, to quantitatively measure the
spatial heterophily and show how it can influence the performance of GNNs.
Indeed, our experimental investigation clearly shows that existing heterophilic
GNNs are still deficient in handling the urban graph with high spatial
diversity score. This, in turn, may degrade their effectiveness in urban
applications. Along this line, we propose a Spatial Heterophily Aware Graph
Neural Network (SHGNN), to tackle the spatial diversity of heterophily of urban
graphs. Based on the key observation that spatially close neighbors on the
urban graph present a more similar mode of difference to the central node, we
first design a rotation-scaling spatial aggregation module, whose core idea is
to properly group the spatially close neighbors and separately process each
group with less diversity inside. Then, a heterophily-sensitive spatial
interaction module is designed to adaptively capture the commonality and
diverse dissimilarity in different spatial groups. Extensive experiments on
three real-world urban datasets demonstrate the superiority of our SHGNN over
several its competitors.
Congxi Xiao, Jingbo Zhou, Jizhou Huang, Tong Xu, Hui Xiong
# Spatial Heterophily Aware Graph Neural Networks

###### Abstract.

Graph Neural Networks (GNNs) have been broadly applied in many urban applications upon formulating a city as an urban graph whose nodes are urban objects like regions or points of interest. Recently, a few enhanced GNN architectures have been developed to tackle heterophily graphs where connected nodes are dissimilar. However, urban graphs usually can be observed to possess a unique spatial heterophily property; that is, the dissimilarity of neighbors at different spatial distances can exhibit great diversity. This property has not been explored, while it often exists. To this end, in this paper, we propose a metric, named Spatial Diversity Score, to quantitatively measure the spatial heterophily and show how it can influence the performance of GNNs. Indeed, our experimental investigation clearly shows that existing heterophilic GNNs are still deficient in handling the urban graph with high spatial diversity score. This, in turn, may degrade their effectiveness in urban applications. Along this line, we propose a Spatial Heterophily Aware Graph Neural Network (SHGNN), to tackle the spatial diversity of heterophily of urban graphs. Based on the key observation that spatially close neighbors on the urban graph present a more similar mode of difference to the central node, we first design a rotation-scaling spatial aggregation module, whose core idea is to properly group the spatially close neighbors and separately process each group with less diversity inside. Then, a heterophily-sensitive spatial interaction module is designed to adaptively capture the commonality and diverse dissimilarity in different spatial groups. Extensive experiments on three real-world urban datasets demonstrate the superiority of our SHGNN over several its competitors.

Urban graphs, Spatial heterophily, Graph neural networks +
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: Corresponding authors.

+
Footnote †: thanks: Corresponding authors.
+
Footnote †: Corresponding authors.
and workplace, respectively, which are definitely heterophilic. Such difference information on the heterophilic urban graph may not be modeled well by many traditional homophilic GNNs, who tend to generate similar representations for connected nodes [2, 55]. In this way, the performance of these homophilic GNN methods on urban graphs may be largely hindered.

Our further observation is that urban graphs have a unique _Spatial Heterophily_ property. To be specific, we find that the heterophily on the urban graph often presents a characteristic of _spatial diversity_. In other words, the difference (or dissimilarity) between the central node and its neighbors at different distances or directions exhibits evident discrepancy, rather than distributed uniformly. Aware of such a characteristic, an attendant question is how to measure the spatial heterophily of the urban graph. There have been various studies put forward to investigate the graph homophily and heterophily from different perspectives, including node homophily [29], edge homophily [56] and class homophily [23]. But without considering the spatial position of linking nodes, these metrics cannot describe the spatial heterophily on urban graphs.

Therefore, in this work, we propose a metric named **spatial diversity score** to analyze the spatial heterophily, and investigate its influence on the performance of existing GNN methods on urban graphs. Firstly, we divide the neighbors on an urban graph into different spatial groups according to their locations (including direction and distance), and then the spatial diversity score measures the discrepancy between different spatial groups, in terms of their label dissimilarity to the central node. A higher score (close to one) indicates a larger discrepancy between different spatial groups, and thus a higher spatial diversity of heterophily on the urban graph.

Yet, it still remains an outstanding challenge for designing powerful heterophilic GNN models over an urban graph if its spatial diversity score is high, where there is a diversity of dissimilarity distributions between the central node and its neighbors at different spatial locations. There are some recent studies to improve the GNN architectures to handle the graph heterophily [8, 14, 17, 24, 48]. Most of these methods can only work on a heterophilic graph when there is limited difference between nodes. For example, GRKGNN [8] assumes that there are only two different kinds of nodes, and FAGCN [2] assumes that node features have only two different levels of frequencies (Note that this limitation is discussed in their papers). Following this line, it is hard to model such diverse distributions of spatial heterophily on urban graphs. To provide more evidence, we conduct an experiment on synthetic urban graphs with varying levels of spatial diversity score (details are in Section 3.2). As shown in Figure 1(d), when the graph presents higher spatial diversity score, the performance of these two state-of-the-art heterophilic GNNs, GBKGNN and FAGCN, is far from optimal. We also apply the proposed spatial diversity score to analyze three real-world urban graphs under different target tasks in our experiments. As we can see from Figure 1(c), three urban graphs present different levels of spatial heterophily, where one of them can get a very high score (0.99 on the urban graph in crime prediction task). Thus, it is valuable to develop an effective GNN model that can handle the diverse spatial heterophily of the urban graph.

Through our in-depth analysis of spatial heterophily, we observe that the heterophily further exhibits a spatial tendency on urban graphs, which reveals a promising opportunity for us to tackle such diverse heterophily in a divide-and-conquer way. Different from ordinary graphs, nodes on urban graphs should follow Tobler's First Law of Geography (TFL) [35]. As the fundamental assumption used in almost all urban analysis, TFL means _everything is related to everything else, but near things are more related than distant things_. Obeying TFL, spatially close neighbors on the urban graph present a more similar mode of difference to the central node, compared to the distant ones. We also analyze the real-world urban graph in commercial activeness prediction task to visualize such a tendency (details are in Section 4). Figure 2 clearly shows that spatially close neighbors present less discrepancy from both the direction and distance view. Thus, if we can properly group the spatially close neighbors together, it is possible to alleviate the diversity of heterophily inside groups on the urban graph.

To this end, we propose a novel Spatial Heterophily Aware Graph Neural Network (SHGNN), to tackle the spatial heterophily on urban graphs, with two specially designed modules. First, we devise a Rotation-Scaling Spatial Aggregation module. Its core idea is to properly divide the neighbors into different spatial groups according to their direction and distance to the central node, and perform a spatial-aware feature aggregation for each group, which serves as the basis of handling diverse heterophily distributions separately. Then, a Heterophily-Sensitive Spatial Interaction module with two learnable kernel functions is designed to capture the commonality and discrepancy in the neighborhood, and adaptively determine what and how much difference information the central node needs. It acts between the central node and neighbors in different groups to manage the spatial diversity of heterophily on the urban graph.

The contribution of this paper is summarized as follows:

* To the best of our knowledge, we are the first to investigate the spatial heterophily of urban graphs. We design a metric named

Figure 1. Analysis of spatial heterophily. (a)-(b) illustrate the space partition from two spatial views. (c) shows the spatial diversity scores calculated on three real-world urban graphs. (d) presents the results of experimental investigation.
spatial diversity score, to analyze the spatial heterophily property, and identify the limitation of existing GNNs in handling the diverse spatial heterophily on the urban graph.
* We propose a novel spatial heterophily aware graph neural network named SHGNN, in which two techniques: rotation-scaling spatial aggregation and heterophily-sensitive spatial interaction are devised to tackle the spatial heterophily of the urban graph in a divide-and-conquer way.
* We conducted extensive experiments to verify the effectiveness of SHGNN on three real-world datasets.

## 2. Preliminaries

In this section, we first introduce the basic concepts of the urban graph, then clarify the goal of our work. The frequently used notations are summarized in Table 4 in Appendix.

_Urban Graphs._ Let \(\mathcal{G}(\mathcal{V},\mathcal{E},\mathcal{X})\) denote an urban graph, where \(\mathcal{V}=\{v_{1},...,v_{N}\}\) denotes a set of nodes representing a kind of urban entity, \(\mathcal{E}\) denotes the edge set indicating one type of relation among nodes in the urban scenario, and \(\mathcal{N}(v_{i})=\{o_{j}|(v_{i},o_{j})\in\mathcal{E}\}\) is the neighborhood of node \(v_{i}\). \(X\in\mathbb{R}^{N\times d}\) denotes the feature matrix, in which the \(i\)-th row is the \(d\)-dimensional node features of \(v_{i}\) obtained from the urban data. Different instantiations of node set and edge set will form different urban graphs, such as: (1) **Mobility Graph** with regions as nodes and human flows as edges. The node features can be some region attributes such as the distribution of POI inside the region; (2) **Road Network** where the node set is formed by road sections, and the edges denote the connectivity between them. The node features can be the structural information of a section, such as the number of branches and lanes.

_Problem Formulation._ Given an urban graph, our goal is to design a GNN model, that considers and alleviates the spatial heterophily, to learn the node representation \(f\colon(v_{i}|\mathcal{G})\rightarrow\hat{\mathbf{h}}_{i}\), where \(\hat{\mathbf{h}}_{i}\) denotes the representation vector of node \(v_{i}\). The model \(f\) will be trained in an end-to-end manner in different downstream tasks.

## 3. Spatial Heterophily

In this section, an analysis of spatial heterophily on urban graphs is provided. We first introduce our metric to measure the spatial heterophily (Section 3.1). Then, Section 3.2 gives an experimental investigation on synthetic graphs. It not only demonstrates the importance for GNNs to consider the spatial heterophily on urban graphs, but also suggests a promising way to tackle this challenge.

### Spatial Diversity of Heterophily

To describe the spatial diversity of heterophily on urban graphs, we design a metric named **spatial diversity score**. Typically, the graph heterophily is measured by the label dissimilarity between the central node and its neighbors (e.g., (Beng et al., 2017; Wang et al., 2018)). Following this line, our spatial diversity score aims to further assess the discrepancy between neighbors at different spatial locations, in terms of the distributions of their label dissimilarity to the central node. Briefly, we first divide the neighborhood into different spatial groups according to their spatial locations. Then, we can measure spatial groups' discrepancy by calculating the Wasserstein distance between their label dissimilarity distributions, and the metric is further defined as the ratio of nodes with high discrepancy.

#### 3.1.1. Dual-View Space Partition

To distinguish the spatial location of neighbors and form different spatial groups, we first partition the geographic space into several non-overlap subspaces, and each neighbor of the central node can be assigned to the group corresponding to the subspace it locates in. Note that the spatial heterophily can both present in different directions and distances, thus we propose to perform space partition from both two views.

**Direction-Aware Partition.** Given the central node \(v_{i}\) on an urban graph, we evenly partition the geographic space centered by it into ten direction sectors \(\mathcal{S}=\{s_{k}\mid k=0,1,...,9\}\). Correspondingly, nodes in the neighborhood \(\mathcal{N}(v_{i})\) will be divided into the sector they locate in. Neighbors belonging to the same sector are redefined as the direction-aware neighborhood \(\{\mathcal{N}_{s_{k}}(v_{i})\mid k=0,1,...,9\}\), where \(\bigcup_{k=0}^{9}\mathcal{N}_{s_{k}}(v_{i})=\mathcal{N}(v_{i})\). In this way, the direction-aware neighborhoods can be regarded as different spatial groups associated with different spatial relations to the central node. We will then calculate the discrepancy between different spatial groups. Figure 1(a) illustrates such a sector partition.

**Distance-Aware Partition.** As illustrated in Figure 1(b), we also divide the neighbors based on their distance to the central node. To be specific, we first determine the distance range of the neighborhood on an urban graph, by making a statistic of the distance distribution between connected nodes. Note that we consider the 90% percentile of this distribution as the maximum distance of the neighborhood on the graph. This is based on the observation that the distance distribution often presents a long tail property, and such a distance cut-off can avoid interference from extremely distant outliers. And then, the distance range is evenly split into ten buckets, which results in distance rings \(\mathcal{R}=\{r_{k}\mid k=0,1,...,9\}\). Similarly, the original neighborhood \(\mathcal{N}(v_{i})\) can be divided into these ten distance-aware neighborhoods \(\{\mathcal{N}_{r_{k}}(v_{i})\mid k=0,1,...,9\}\) as another view of spatial groups, where we also have \(\bigcup_{k=0}^{9}\mathcal{N}_{r_{k}}(v_{i})=\mathcal{N}(v_{i})\).

#### 3.1.2. Spatial Diversity Score

After the neighborhood partition, our goal is to further define the spatial diversity score by measuring the discrepancy between different spatial groups, based on their distribution distance of label dissimilarity to the central node.

First of all, we define spatial group's label dissimilarity distribution to the central node. For a node classification task with \(\mathcal{C}\) classes, within a spatial group, this distribution is calculated as the ratio of neighbors belonging to each class (different to the central node's). Taking the direction view as an example, for the central node \(v_{i}\), the label dissimilarity distribution of \(s_{k}\) is formally defined as \(P_{i}^{s_{k}}=[\,P_{i,0}^{s_{k}},\,\,p_{i,1}^{s_{k}},\,\,...,\,P_{i,|\mathcal{C }|-1}^{s_{k}}]\) with:

\[P_{i,c}^{s_{k}}=\sum_{v_{j}\in\mathcal{N}_{s_{k}}(v_{i})\wedge y_{j}\neq y_{j}} \mathbb{I}\left(y_{j,c}=1\right)\cdot|\mathcal{N}_{s_{k}}(v_{j})|^{-1}, \tag{1}\]

where \(c=0,1,...,|\mathcal{C}|-1\), \(\mathbb{I}(\cdot)\) is the indicator function, and \(y_{i}\) is \(v_{i}\)'s one-hot label vector whose \(c\)-th value is denoted by \(y_{i,c}\).

In addition, to improve the generality of this metric to more urban applications (e.g., regression tasks), we also extend the definition of label dissimilarity distribution above to the node regression task. To be specific, we first make a statistic of the label difference between connected nodes on the whole graph \(\hat{\mathcal{Y}}=\{(y_{j}-y_{i})\mid(v_{i},v_{j})\in\mathcal{E}\}\), and calculate the deciles \(\{D_{1},D_{2},...,D_{9}\}\) of this distribution. These nine deciles can determine ten buckets (intervals), which will be used for the discretization of continuous label difference value, to
obtain a similar form of label dissimilarity as the node classification task. Hence, still for the spatial group \(\mathcal{N}_{s_{b}}(v_{i})\) in sector \(s_{k}\), its label dissimilarity distribution will be calculated as the ratio of neighbors mapped into different buckets, according to their discretized label difference to the central node, which can be also formulized as: \(P_{i,c}^{pk}=\{P_{i,0}^{k},\,P_{i,1}^{pk},\,...,\,P_{i,g}^{pk}\}\), with the \(c\)-th element computed by:

\[P_{i,c}^{sk}=\sum_{v_{j}\in\mathcal{N}_{s_{b}}(v_{i})}\mathbb{E}(D_{c}<y_{j}-y_ {i}\leq D_{c+1})\cdot|\mathcal{N}_{s_{b}}(v_{i})|^{-1}, \tag{2}\]

where \(c=0,1,...,9\). The \(D_{0}\) and \(D_{10}\) are used to denote the minimum and maximum of the label difference distribution on the whole graph, respectively (i.e., \(D_{0}=\min(\hat{\mathcal{Y}})\) and \(D_{10}=\max(\hat{\mathcal{Y}})\)).

Next, the discrepancy between different spatial groups can be defined by measuring the distance between their label dissimilarity distributions. Following a recent study on the graph heterophily (Sinkhorn, 2017), we adopt Wasserstein distance (WD) to measure the distribution distance between two spatial groups. Formally, consider two spatial groups \(\mathcal{N}_{s_{p}}(v_{i})\) and \(\mathcal{N}_{s_{q}}(v_{i})\) in sector \(s_{p}\) and \(s_{q}\) of node \(v_{i}\), the discrepancy between them is defined as:

\[Disc(v_{i},s_{p},s_{q})=WD(p_{i}^{s_{p}},P_{i}^{s_{q}}), \tag{3}\]

where \(WD(\cdot,\cdot)\) denotes the Wasserstein distance between two distributions, which can be approximately calculated by the Sinkhorn iteration algorithm (Sinkhorn, 2017).

With such a measurement, we can finally define the spatial diversity score to describe the diverse spatial heterophily of an urban graph. This metric can be computed based on the ratio of nodes with high discrepancy among different spatial groups:

\[\lambda_{d}^{s}=|\mathcal{V}|^{-1}\cdot\sum_{v_{i}\in\mathcal{V}}\mathbb{1}( \max_{p\neq q}Disc(v_{i},s_{p},s_{q})\geq 1), \tag{4}\]

where \(\max_{p\neq q}Disc(v_{i},s_{p},s_{q})\geq 1\) with \(p,q=0,1,...,9\) indicates that there are at least two sectors being discrepant in terms of their label dissimilarity distributions to the central node \(v_{i}\). In this way, the score \(\lambda_{d}^{s}\) will get higher if there are more nodes whose spatial groups present high discrepancy on the urban graph. Similarly, we can also define the score \(\lambda_{d}^{r}\) in the distance view, which measures the discrepancy between spatial groups formed by different rings in \(\mathcal{R}\), with different distances to the central node:

\[\lambda_{d}^{r}=|\mathcal{V}|^{-1}\cdot\sum_{v_{i}\in\mathcal{V}}\mathbb{1}( \max_{p\neq q}Disc(v_{i},r_{p},r_{q})\geq 1), \tag{5}\]

In practice, when only a part of nodes are labeled on an urban graph, it's often sufficient to use the labeled data to estimate \(\lambda_{d}^{s}\) and \(\lambda_{d}^{r}\). Figure 1(c) shows the scores of three real-world urban graphs. As we can see, from both the direction and distance view, urban graphs can present very high spatial diversity scores (e.g., 0.99 in crime prediction), which reveals the diverse heterophily in different spatial groups, with discrepant label dissimilarity distributions.

### Experimental Investigation

Next, we conduct an experimental investigation on synthetic urban graphs to illustrate the importance of considering the diverse spatial heterophily on the urban graph. Specifically, we test the performance of several GNN models on a series of synthetic urban graphs with increasing spatial diversity of the heterophily. We generate 10 graphs containing 5000 nodes with 10-dimensional randomly generated feature vectors. For each node, we build 50 edges and assume that these neighbors locate at 10 distance rings from near to far around the central node. To increase the spatial diversity of heterophily from \(\mathcal{G}_{1}\) to \(\mathcal{G}_{10}\), we gradually enlarge the discrepancy of label dissimilarity distributions between neighbors in different distance rings. Specifically, in graph \(\mathcal{G}_{i}\), we evenly divide the node set into \(i\) subsets \(\mathcal{V}_{i}=\bigcup_{j=1}^{i}\mathcal{V}_{i,j}\), where the labels of nodes in \(\mathcal{V}_{i,j}\) are sampled from the Gaussian distribution \(\mathcal{N}(10j,1)\). Then, the 50 neighbors connected to the node in \(\mathcal{V}_{i,j}\) are randomly selected from one of subsets \(\{\mathcal{V}_{i,k}\}|_{k=j}^{i}\) by an equal probability \(1/(i-j+1)\). Besides, we let neighbors' spatial distance be consistent with their label difference to the central node (i.e., neighbors with smaller differences locates in the closer distance ring). In this way, these 10 graphs will have increasing spatial diversity scores \(\lambda_{d}^{r}\). Meanwhile, neighbors in the same distance ring have less discrepancy.

Figure 1(d) shows the node regression error of GCN (Kip
## 4. Methodology

In this section, we first present that the heterophily on urban graphs often exhibits a spatial tendency: spatially close neighbors have more similar heterophily distributions than distant ones, which obeys TFL. This characteristic gives rise to the solution that we can properly divide neighbors according to their spatial locations, to achieve grouping neighbors with less discrepancy together. Then, we introduce our proposed SHGNN that leverages such a spatial tendency to tackle the spatial heterophily of urban graphs.

**Spatial Tendency.** In addition to the presence of a discrepancy between different spatial groups (discussed in Section 3.1), our in-depth investigation of spatial heterophily further reveals that such a discrepancy shows a spatial tendency on urban graphs. Specifically, we observe that the discrepancy between two spatially close groups is smaller, compared to two distant groups. We conduct a data analysis to visually present such a tendency. Figure 2 shows the pair-wise discrepancy of label dissimilarity distributions between any two spatial groups, which is computed based on real-world human mobility and regional commercial activeness data. In Figure 2(a), for the spatial group formed by distance ring \(r_{p}\), we can find that its discrepancy with other rings \(r_{q}\) is highly correlated to their spatial distance (i.e., the discrepancy gets higher when \(r_{q}\) is more distant to \(r_{p}\)). For example, the close ring pair \((r_{0},r_{1})\) are less discrepant than the distant pair \((r_{0},r_{0})\). A similar spatial tendency can also be observed from the direction view. As shown in Figure 2(b), in most cases, the discrepancy will increase along with the included angle between sectors. Taking sector \(s_{0}\) as an example, its discrepancy with \(s_{1}\sim s_{0}\) increases first and then decreases, which is roughly in sync with the change of their included angles. In other words, a sector is more likely to be discrepant to another distant sector (e.g., \((s_{1},s_{6})\)) than a nearby one (e.g., \((s_{1},s_{2})\)). This characteristic motivates us to address the diverse spatial heterophily on urban graphs, by properly grouping spatially close neighbors and separately processing each group with less discrepancy inside.

To this end, we propose a novel GNN architecture named SHGNN, which is illustrated in Figure 3 and 4. Our model consists of two components: Rotation-Scaling Spatial Aggregation (see Section 4.1) and Heterophily-Sensitive Spatial Interaction (see Section 4.2).

### Rotation-Scaling Spatial Aggregation

This component aims to properly group spatially close neighbors and alleviate the diversity of heterophily inside groups in the message passing process. In general, we first divide neighbors according to their relative positions to the central node. Then, the feature aggregation is performed in each spatial group separately.

#### 4.1.1. Rotation-Scaling Dual-View Partition

Following the neighborhood partition in Section 3.1.1, we also partition the geographic space into non-overlap subspaces, and neighbors located at the same subspace are then grouped together. Note that there are two major differences between the space partition performed in this component and that in Section 3.1.1. First, we apply a more general partition with a variable number of subspaces. Second, we introduce a rotation-scaling multi-head partition strategy to model the neighbor's spatial location in a more comprehensive way.

To be specific, in the direction view, we evenly partition the space into a set of sectors \(\mathcal{S}=\{s_{k}\,|\,k=0,1,...,n_{s}-1\}\), where \(n_{s}\) denotes the number of partitioned sectors, which can be appropriately set for different datasets. Nodes in each direction-aware neighborhood \(\mathcal{N}_{\text{sg}}(v_{i})\) of sector \(s_{k}\) are grouped together, which we still call spatial group. In the distance view, the space will be partitioned into \(n_{r}\) distance rings \(\mathcal{R}=\{r_{k}\,|\,k=0,1,...,n_{r}-1\}\), which is resulted from a predefined distance bucket (e.g., \(<1km,1-2km,\) and \(>2km\)). Note that the central node \(v_{i}\) itself does not belong to any sector or ring, we regard it as an additional group \(\mathcal{N}_{\text{sg}_{n_{r}}}(v_{i})=\mathcal{N}_{r_{n_{r}}}(v_{i})=\{v_{i}\}\).

#### Rotation-Scaling Multi-Head Partition

In view of the special case that a part of neighbors may locate at the boundary between two subspaces, we further propose a multi-head partition strategy to simultaneously perform multiple partitions at each view, where different heads can complement each other. For example, as shown in Figure 3(a), the orange node \(v_{4}\) locates at the boundary between sectors \(s_{0}\) and \(s_{1}\), which indicates that the spatial relation of the neighborhood is still inadequately excavated by the single direction-based partition. A similar situation can be found in the partition of distance rings, such as the node \(v_{4}\) in Figure 3(b).

To overcome this limitation, we extend our partition strategy by devising two operations, which are _sector rotation_ and _ring scaling_, to achieve multiple space partitions for capturing the diverse spatial relations comprehensively. Specifically, as illustrated in Figure 3(a) and (c), for the originally partitioned direction sectors, we turn the sector boundary a certain angle (e.g., 45 degrees) to derive another set of sectors, then the neighbors can be correspondingly reassigned in these new sectors and form a different set of direction-aware neighborhoods. Thus, we update the denotation of sectors as \(\mathcal{S}^{m}=\{s_{k}^{m}\,|\,k=0,1,...,n_{s}\}\), and that of direction-aware neighborhoods as \(\{\mathcal{N}_{\text{sg}}^{m}(v_{i})\,|\,k=0,1,...,n_{s}\}\), where \(m=1,2,...,M_{s}\) denotes the \(m\)-th head partition among total \(M_{s}\) heads. Similarly, from the distance view, we scale the boundary of the original distance rings to obtain the supplemental partition, which is shown in Figure 3(b) and (d). The denotations are updated as \(\mathcal{R}^{m}=\{r_{k}^{m}\,|\,k=0,1,...,n_{r}\}\) and \(\{\mathcal{N}_{\text{sg}}^{m}(v_{i})\,|\,k=0,1,...,n_{r}\}\) for rings and distance-aware neighborhoods, where \(m=1,2,...,M_{r}\). In this way, different heads of partitions model the spatial relation between neighbors and the central node complementarily, and thus we can avoid the improper grouping under a single partition.

#### 4.1.2. Spatial-Aware Aggregation

After the multi-head partition from two spatial perspectives, we collect messages from neighbors to the central node. Rather than mixing the messages (e.g., through averaging) that most of the GNNs follow (Nguyen et al., 2019), our model performs a group-wise aggregation to handle different spatial groups with diverse heterophily. An illustration is shown in Figure 4(a).

Figure 3. Illustration of Rotation-scaling Partition.
Formally, taking the direction view as an example, with the set of direction-aware neighborhoods (spatial groups) under the \(m\)-head partition \(\{\mathbf{N}_{s_{k}^{m}}(u_{i})\mid k=0,1,...,n_{s}\}\), we use graph convolution (Girshick et al., 2015) to respectively aggregate the features of nodes in each neighborhood \(\mathcal{N}_{s_{k}^{m}}(u_{i})\) with the normalization by degree:

\[\mathbf{z}_{i,s_{k}^{m}}(l+1)=\sum_{j\in\mathcal{N}_{s_{k}^{m}}(u_{i})}(\lvert \mathcal{N}(v_{i})\rvert\cdot\lvert\mathcal{N}(v_{j})\rvert)^{-\frac{1}{2}}\, \mathbf{h}_{j}(l)\,\mathbf{W}_{s_{k}^{m}}(l), \tag{6}\]

where \(\mathbf{z}_{i,s_{k}^{m}}(l)\) denotes the \(l\)-layer aggregated message from direction sector \(s_{k}^{m}\), \(\mathbf{h}_{j}(l)\) denotes the \(l\)-layer features of neighbor \(\mathbf{v}_{j}\) with \(\mathbf{h}_{j}(0)=\mathbf{x}_{j}\), and \(\mathbf{W}_{s_{k}^{m}}(l)\) is a trainable transformation extracting useful information from neighbors' features.

Similarly, at the distance view, we also perform the ring-wise aggregation in each distance ring separately by:

\[\mathbf{z}_{i,t_{k}^{m}}(l+1)=\sum_{j\in\mathcal{N}_{s_{k}^{m}}(u_{j})}(\lvert \mathcal{N}(v_{i})\rvert\cdot\lvert\mathcal{N}(v_{j})\rvert)^{-\frac{1}{2}}\, \mathbf{h}_{j}(l)\,\mathbf{W}_{r_{k}^{m}}(l), \tag{7}\]

where \(\mathbf{W}_{r_{k}^{m}}(l)\) is another feature transformation for neighbors at different distances. In this way, the aggregated messages can not only capture the structure information on the graph, but also discriminate their different spatial groups. It avoids losing different distributions of spatial heterophily on the urban graph.

### Heterophily-Sensitive Spatial Interaction

After the group-wise feature aggregation, SHGNN further captures the diverse spatial heterophily in different spatial groups on the urban graph. In detail, we devise two learnable kernel functions to first respectively capture the commonality and discrepancy between the central node and each spatial group. Then, an attentive gate is jointly learned to adaptively determine the ratio of two components that should be propagated to the central node. Additionally, as indicated by the analysis of spatial tendency in Figure 2, the discrepancy of heterophily distributions varies along with the distance between two spatial groups, we further consider such characteristics by allowing the kernel functions to act between groups, which encourages the propagation of common and discrepant information among them. Since we view the central node as an additional group, this process can be regarded as an interaction among every two groups. For simplicity, we omit the index \(l\) and \(m\) of layer and head in the following discussion.

_Commonality Kernel Function._ Given the fact that different sectors / rings all belong to the neighborhood of the central node, they may share some common knowledge that can probably enhance the representation of each other. Thus, we first design a commonality kernel function to capture such information among them.

Formally, taking the direction view as an example, with the representation \(\{\mathbf{z}_{i,s_{k}}\mid k=0,1,...,n_{s}\}\) of \(n_{s}\) sectors centered by \(v_{i}\), the kernel function \(\mathcal{N}_{C}^{s}(\cdot,\cdot)\) that models the commonality degree between sector \(s_{p}\) and \(s_{q}\) (including \(v_{i}\) itself) is defined as:

\[\mathcal{K}_{C}^{s}(\mathbf{z}_{i,s_{p}},\mathbf{z}_{i,s_{q}})\ =\ \mathbf{z}_{i,s_{p}},\mathbf{z}_{i,s_{q}}\text{-}\ \mathbf{z}_{i,s_{k}}\text{=}\ \mathbf{z}_{i,s_{k}}\mathbf{W}_{C}^{s}, \tag{8}\]

where \(<,>\) denotes the inner product and \(\mathbf{W}_{C}^{s}\) is the learnable matrix for common knowledge extraction. The larger output value suggests a higher similarity (i.e., commonality) between inputs. Based on this measurement, we enhance the sector representation with the extracted useful information from other sectors:

\[\mathbf{z}_{i,s_{p}}^{C}=\sum_{q=0}^{n_{s}}\alpha_{pq}^{C,s}\,z_{i,s_{q}}\mathbf{W}_{C} ^{s}, \tag{9}\]

\[\alpha_{pq}^{C,s}=\frac{exp\left(\mathcal{K}_{C}^{s}(\mathbf{z}_{i,s_{p}},\mathbf{z} _{i,s_{q}})\right)}{\sum_{k=0}^{n_{s}}exp\left(\mathcal{K}_{C}^{s}(\mathbf{z}_{i,s _{p}},\mathbf{z}_{i,s_{k}})\right)}, \tag{10}\]

where the coefficient \(\alpha_{pq}^{C,s}\) is the level of commonality normalized by the softmax function. In the same way, we can also obtain the representation of each distance ring \(\mathbf{z}_{i,s_{p}}^{C}\) with the enhancement of common knowledge from other rings using a similar kernel function \(\mathcal{K}_{C}^{s}(\cdot,\cdot)\) parametrized by \(\mathbf{W}_{C}^{s}\).

_Discrepancy Kernel Function._ In addition to the common knowledge, modeling the difference information is critical on heterophilic urban graphs. Thus, we devise another kernel function to capture

Figure 4. The architecture of SHGNN. We only detailedly present the operation under sector partition in the illustration of two kernel functions and the attentive component selection. The same operation is also performed under ring partition.
diverse dissimilarity between the central node and every group, as well as between any two groups. We introduce it from the direction view. Specifically, taking the original representation \(\{z_{i,s_{k}}|k=0,1,...,n_{s}\}\) as inputs, the discrepancy kernel is defined as:

\[\mathcal{K}_{D}^{s}(z_{i,s_{p}},z_{i,s_{q}})=\;<z_{i,s_{p}}W_{D}^{s,a},(z_{i,s_{ p}}W_{D}^{s,a}-z_{i,s_{q}}W_{D}^{s,b})>, \tag{11}\]

where \(W_{D}^{s,a}\) and \(W_{D}^{s,b}\) denote two transformations that learn to extract the difference of sector \(s_{q}\) compared to sector \(s_{p}\). According to (Kang et al., 2019), the kernel function \(\mathcal{K}_{D}^{s}(z_{i,s_{p}},z_{i,s_{q}})\) can be regarded as calculating the dissimilarity degree between two inputs, which tends to be higher when \(s_{p}\) and \(s_{q}\) are more dissimilar. Subsequently, our model facilitates each sector to be aware of the helpful difference information from others with this measurement of discrepancy:

\[z_{i,s_{p}}^{D} =\sum_{q=0}^{n_{s}}\sigma_{pq}^{D,s}\left(z_{i,s_{p}}W_{D}^{s,a}- z_{i,s_{q}}W_{D}^{s,b}\right), \tag{13}\] \[\alpha_{pq}^{D,s} =\frac{exp(\mathcal{K}_{D}^{s}(z_{i,s_{p}},z_{i,s_{q}}))}{\sum_{ k=0}^{n_{s}}exp(\mathcal{K}_{D}^{s}(z_{i,s_{p}},z_{i,s_{k}}))}. \tag{12}\]

Similarly, we utilize an analogous kernel function, which is denoted as \(\mathcal{K}_{D}^{r}(\cdot,\cdot)\) with parameters \(W_{D}^{r,a}\) and \(W_{D}^{r,b}\) to capture such discrepancy at the distance view and derive the ring representation \(z_{i,r_{p}}^{D}\) aware of the diverse distributions of spatial heterophily.

#### Attentive Component Selection

With these two kernel functions, we can exploit both the common knowledge and diverse discrepancy information between the central node and neighbors in different groups. However, different nodes may possess varying levels of spatial heterophily in various applications. Thus, SHGNN learns to derive a gate that adaptively determines the ratio of common and difference information in an end-to-end manner.

Specifically, for each central node \(v_{i}\), we concatenate both the commonality and discrepancy components of all sectors, to derive a scalar with a transformation:

\[\beta_{i}^{s}=\sigma(\|_{j\in\{C,D\}}\|_{k=0}^{n_{s}}\;z_{i,s_{k}}^{j}W_{t}^{ s}), \tag{14}\]

where \(W_{t}^{s}\) denotes the trainable transformation mapping the in-out to a scalar and \(\sigma\) denotes the _Sigmoid_ function restricting the output value into \((0,1)\). Then, \(\beta_{i}^{s}\) serves as a gate controlling the ratio of the commonality and discrepancy components in the final representation of each sector:

\[\tilde{z}_{i,s_{k}}=\beta_{i}^{s}\cdot z_{i,s_{k}}^{C}+(1-\beta_{i}^{s})\cdot z _{i,s_{k}}^{D}. \tag{15}\]

In the same way, we learn to derive the gate \(\beta_{i}^{r}\) that determines the ratio in each ring's final representation \(\tilde{z}_{i,r_{k}}\).

After the propagation among spatial groups (including the central node), different groups can contain diverse discrepancy information in the neighborhood, which is vital to the heterophilic urban graph. We then integrate this group-wise representation by concatenation (instead of summation, to avoid the mixing of diverse distributions of spatial heterophily) to obtain the global representation of two views. Since we adopt the multi-head partition strategy, a following concatenation is used to combine different heads at each view. The above two processes can be jointly expressed as:

\[\mathbf{h}_{i,s}=\|_{m=1}^{M_{s}}\;\;(\|_{k=0}^{n_{s}}\;\;\tilde{z}_{i,s_{k}^{m}}), \;\;\mathbf{h}_{i,r}=\|_{m=1}^{M_{r}}\;\;(\|_{k=0}^{n_{r}}\;\;\tilde{z}_{i,r_{k}^{ m}}^{m}). \tag{16}\]

#### Fusion of Two Spatial Views

Finally, we fuse two spatial views with a learnable weighted summation to update the central node's representation as follows:

\[\mathbf{h}_{i}=\gamma\;\mathbf{h}_{i,s}W_{f}^{s}+(1-\gamma)\;\mathbf{h}_{i,r}W_{f}^{r}, \tag{17}\]

where \(W_{f}^{s}\) and \(W_{f}^{r}\) are two weight matrices transforming the representation vectors of two views into the same space, and \(\gamma\) is a trainable trade-off parameter activated by _Sigmoid_ function, which learns to assign different importance to the direction and distance view according to the target task.

### Prediction and Optimization

Consistent with general GNNs, we use the \(L\)-layer output activated by \(ReLU\) function \(\mathbf{\hat{h}}_{i}\!=\!\sigma(\mathbf{h}_{i}^{(L)})\) as the node representation to make a prediction in different downstream tasks, and optimize the model by the appropriate loss function: \(\mathcal{L}\left(LR(\mathbf{\hat{h}}_{i})\,,\,y_{i}\right)\). In node regression tasks, \(LR(\cdot)\) is the linear regressor, \(y_{i}\!\in\!\mathbb{R}\) denotes the ground truth of labeled nodes, and \(\mathcal{L}\) can be L2 loss. While for node classification tasks, \(LR(\cdot)\) performs the logistic regression, \(y_{i}\!\in\!\{0,1\}^{C}\) is a one-hot label vector of \(C\) classes, and \(\mathcal{L}\) can be cross entropy loss.

## 5. Experiments

In this section, we conduct extensive experiments on real-world datasets in three different tasks upon two types of urban graphs to evaluate the effectiveness of our model. The code of SHGNN is available at [https://github.com/PaddlePaddle/PaddleSpatial/tree/main/research/SHGNN](https://github.com/PaddlePaddle/PaddleSpatial/tree/main/research/SHGNN).

### Experiment Settings

#### 5.1.1. Tasks and Data Description

We first briefly introduce the three datasets corresponding to three different tasks, and details of how to build each dataset are described in Appendix A.1. Table 1 summarizes the statistical information of the three datasets.

**Commercial Aectiveness Prediction (CAP)** is a node regression task on a mobility graph. Similar to (Zhu et al., 2019), we use the number of comments to POIs in each region as the indicator of regional commercial activeness. To form the dataset of this task, we collect the following urban data in _Shenzhen_ city in China from Baidu Maps, including POI data and satellite images in September 2019 to construct region features, the daily human flow data from July 2019 to September 2019 for building the edge set of the urban graph, and the number of regional POI comments from June 2019 to April 2020 which is regarded as the ground truth.

**Crime Prediction (CP)** is also a node regression task on the mobility graph. We collect the real-world dataset of _New York City_ from NYC open data website1 for this task. The dataset contains 180 regions in Manhattan, with the POI data and crime number in each region, as well as taxi trips between regions (Zhu et al., 2019; Zhang et al., 2019). We construct node features from POIs. Taxi trips are used to build the

\begin{table}
\begin{tabular}{l l l l l l} \hline \hline
**Task** & **Dataset** & **\# Nodes** & **\# Edges** & **\# Labeled** & \(\mathbf{\lambda}_{d}^{s}\) & \(\mathbf{\lambda}_{d}^{r}\) \\ \hline CAP & Shenzhen & 82,510 & 9,486,879 & 9,121 & 0.89 & 0.78 \\ CP & Manhattan & 180 & 3,780 & 180 & 0.98 & 0.98 \\ DRSD & Los Angeles & 253,985 & 1,365,289 & 15,274 & 0.23 & 0.14 \\ \hline \hline \end{tabular}
\end{table}
Table 1. Statistics of three real-world datasets.
urban graph, where we only keep the 20 most important edges for each region w.r.t. the number of trip records.

**Dangerous Road Section Detection (DRSD)** is a node classification task performed on the road network. In this work, the dangerous section is defined as the road section with a high incidence of traffic accidents. We build a real-world dataset in _Los Angeles_ based on the road network data from OSMnx Street Networks in Harvard Dataverse2 and the traffic accident records in December 2021 from Kaggle dataset website3. First, we make statistics of the number of accident records on each road section. Then, the sections containing more than 3 accident records in a month will be considered as dangerous road sections in our experiments.

Footnote 2: [https://dataverse.harvard.edu/dataverse/osmnx-street-networks](https://dataverse.harvard.edu/dataverse/osmnx-street-networks)

Footnote 3: [https://www.kaggle.com/datasets/sobhammoosavi/us-accidents](https://www.kaggle.com/datasets/sobhammoosavi/us-accidents)

To select the best hyper-parameters for all the comparing methods, we randomly split each dataset into three parts with 60% for training, 20% for validation and 20% for test.

#### 5.1.2. Baselines

We compare SHGNN with a variety of state-of-the-art GNN models, including two classical message passing neural networks (**GCN**(Krizhevsky et al., 2014) and **GAT**(Wang et al., 2015)), five representative methods for heterophilic graphs (**Mixhop**(Krizhevsky et al., 2014), **FAGCN**(Krizhevsky et al., 2014), **NLGCN**(Krizhevsky et al., 2014), **GPRGNN**(Krizhevsky et al., 2014) and **GBKGNN**(Krizhevsky et al., 2014)), two spatial GNN models (**SAGNN**(Krizhevsky et al., 2014) and **PRIM**(Krizhevsky et al., 2014)), as well as three task-specific baselines (**KnowCL**(Krizhevsky et al., 2014) for CAP, **NNCCRF**(Krizhevsky et al., 2014) for CP and **RFN**(Krizhevsky et al., 2014) for DRSD). Detailed descriptions are introduced in Appendix A.3.

#### 5.1.3. Evaluation Metrics

For the two regression tasks, we evaluate all methods with Root Mean Square Error (RMSE), Mean Absolute Error (MAE) and the coefficient of determination (\(\mathbb{R}^{2}\)). For the node classification task, we use Area Under Curve (AUC) and F1-score.

### Performance Evaluation

#### 5.2.1. Overall Comparison

The performance comparison of our SHGNN and baselines is presented in Table 2, in which the mean and standard deviation of all metrics are obtained through five random runs. As we can see, SHGNN consistently achieves the best performance in three tasks on two kinds of urban graphs, with 6.6% and 11.2% reductions of RMSE in commercial activeness prediction (CAP) and crime prediction (CP), as well as 7.2% improvements of AUC in dangerous road section detection (DRSD) over the most competitive baseline of each task. We also conduct a pairwise t-test between SHGNN and each baseline to demonstrate that our model outperforms all of them significantly. Note that although the spatial diversity of heterophily on the road network in DRSD task is not so strong (\(\lambda_{d}^{s}=0.23\) and \(\lambda_{d}^{r}=0.14\)) as another two urban graphs, our model can still improve the accuracy in a large margin. It indicates the effectiveness of SHGNN can be general but not just limited to urban graphs with strong spatial heterophily.

Specifically, the ordinary GNN models (GCN and GAT) generally have the worst overall performance. By contrast, approaches designed to deal with graph heterophily (Mixhop, FAGCN, NLGCN, GBKGNN and GPRGNN) evidently perform better. It indicates the inappropriateness of simply treating an urban graph as a general homophilic graph. However, as a specially designed model to handle spatial heterophily, our SHGNN remarkably outperforms these general heterophilic GNNs. The spatial GNN methods (SAGNN and PRIM) perform better than GCN and GAT sometimes, but perform worse than the methods for heterophilic graphs in many cases. And for task-specific baselines, it can also be found that some heterophilic GNNs are level pegging with them (such as Mixhop and GPRGNN vs. KnowCL in CAP task, GBKGNN vs. NNCCRF in CP task and Mixhop vs. RFN in DRSD task). These results also demonstrate the importance to take the spatial heterophily into consideration when using GNNs over an urban graph. To sum up, our SHGNN is much more effective in considering and alleviating the spatial heterophily on urban graphs in all the tasks.

#### 5.2.2. Ablation Study

To verify the effectiveness of each design in our model, we further compare SHGNN with its five variants:

* [leftmargin=*,noitemsep,topsep=0pt]
* **SHGNN-S** removes the direction section partition, which only models spatial heterophily from the distance view.

\begin{table}
\begin{tabular}{c|c c c|c c c|c c} \hline \hline  & \multicolumn{3}{c|}{Commercial Activeness Prediction} & \multicolumn{3}{c|}{Crime Prediction} & \multicolumn{3}{c}{Dangerous Road Section Detection} \\ \hline Methods & RMSE \(\downarrow\) & MAE \(\downarrow\) & \(\mathbb{R}^{2}\uparrow\) & RMSE \(\downarrow\) & MAE \(\downarrow\) & \(\mathbb{R}^{2}\uparrow\) & AUC \(\uparrow\) & F1-score \(\uparrow\) \\ \hline GCN & 8.354 \(\pm\) 0.020* & 5.018 \(\pm\) 0.028* & 0.388 \(\pm\) 0.003* & 156.1 \(\pm\) 1.312* & 114.5 \(\pm\) 1.005* & 0.082 \(\pm\) 0.015* & 0.634 \(\pm\) 0.002* & 0.229 \(\pm\) 0.003* \\ GAT & 8.952 \(\pm\) 0.153* & 5.134 \(\pm\) 0.099* & 0.298 \(\pm\) 0.023* & 166.8 \(\pm\) 5.750* & 127.1 \(\pm\) 4.359* & -0.400 \(\pm\) 0.071* & 0.613 \(\pm\) 0.006* & 0.213 \(\pm\) 0.008* \\ Mixhop & 8.168 \(\pm\) 0.038* & 4.981 \(\pm\) 0.010* & 0.415 \(\pm\) 0.005* & 147.6 \(\pm\) 0.576* & 109.0 \(\pm\) 0.398* & 0.179 \(\pm\) 0.006* & 0.636 \(\pm\) 0.003* & 0.229 \(\pm\) 0.005* \\ FAGCN & 8.327 \(\pm\) 0.018* & 5.063 \(\pm\) 0.031* & 0.392 \(\pm\) 0.002* & 150.9 \(\pm\) 3.618* & 108.1 \(\pm\) 2.179* & 0.142 \(\pm\) 0.014* & 0.632 \(\pm\) 0.004* & 0.228 \(\pm\) 0.009* \\ NLGCN & 8.495 \(\pm\) 0.108* & 4.883 \(\pm\) 0.053* & 0.367 \(\pm\) 0.016* & 151.7 \(\pm\) 4.496* & 110.2 \(\pm\) 3.557* & 0.133 \(\pm\) 0.050* & 0.626 \(\pm\) 0.003* & 0.224 \(\pm\) 0.004* \\ GBRGNN & 8.490 \(\pm\) 0.017* & 5.004 \(\pm\) 0.074* & 0.368 \(\pm\) 0.002* & 133.6 \(\pm\) 0.0495* & 98.28 \(\pm\) 3.792 & 0.327 \(\pm\) 0.041* & 0.626 \(\pm\) 0.011* & 0.225 \(\pm\) 0.013* \\ GPRGNN & 8.139 \(\pm\) 0.016* & 4.975 \(\pm\) 0.025* & 0.419 \(\pm\) 0.002* & 152.4 \(\pm\) 0.338* & 107.0 \(\pm\) 0.319* & 0.126 \(\pm\) 0.003* & 0.635 \(\pm\) 0.003* & 0.226 \(\pm\) 0.004* \\ PRIM & 8.928 \(\pm\) 0.144* & 5.186 \(\pm\) 0.086* & 0.301 \(\pm\) 0.022* & 151.7 \(\pm\) 6.243* & 118.6 \(\pm\) 4.320* & 0.131 \(\pm\) 0.070* & 0.615 \(\pm\) 0.008* & 0.210 \(\pm\) 0.005* \\ SAGNN & 8.843 \(\pm\) 0.068* & 5.305 \(\pm\) 0.057* & 0.315 \(\pm\) 0.010* & 142.2 \(\pm\) 2.451* & 108.6 \(\pm\) 1.360* & 0.238 \(\pm\) 0.026* & 0.630 \(\pm\) 0.006* & 0.216 \(\pm\) 0.008* \\ TASK-S & 8.360 \(\pm\) 0.068* & 4.875 \(\pm\) 0.028* & 0.387 \(\pm\) 0.010* & 138.8 \(\pm\) 2.619* & 100.4 \(\pm\) 0.945* & 0.274 \(\pm\) 0.027* & 0.638 \(\pm\) 0.012* & 0.240 \(\pm\) 0.008* \\ SHGNN & **7.605 \(\pm\) 0.131** & **4.485 \(\pm\) 0.056** & **0.493 \(\pm\) 0.017** & **118.7 \(\pm\) 4.135** & **91.16 \(\pm\) 2.754** & **0.469 \(\pm\) 0.036** & **0.684 \(\pm\) 0.004** & **0.263 \(\pm\) 0.003** \\ \hline \hline \end{tabular}
\end{table}
Table 2. Performance comparison. ‘TASK-S’ refers to task-specific baseline for CAP (KnowCL), CP (NNCCRF), and DRSD (RFN). Symbol \(*\),
* **SHGNN-R** removes the distance ring partition, which only models spatial heterophily from the direction view.
* **SHGNN-M** removes the multi-head partition strategy.
* **SHGNN-C** removes the commonality kernel function, without sharing common knowledge among spatial groups.
* **SHGNN-D** removes the discrepancy kernel function. It cannot capture the difference among spatial groups.

As shown in Figure 5, SHGNN outperforms all the variants, proving the significance of our designs in tackling spatial heterophily. Specifically, the performances get worse if we remove either the partition of direction sections or distance rings (SHGNN-S and SHGNN-R), which indicates the necessity of considering the spatial heterophily from both views. Besides, the rotation-scaling multi-head partition strategy can evidently help to model diverse spatial relations (SHGNN-M). In addition, the performance degrades if the commonality kernel function is not used, suggesting the effectiveness of sharing knowledge among neighbors. More importantly, removing the discrepancy kernel function results in a notable performance decline, which verifies the importance of further capturing and exploiting the difference information on heterophilic urban graphs.

#### 5.2.3. Parameters Analysis

We further investigate the influence of several important hyper-parameters on the performance of SHGNN while keeping other parameters fixed. Figure 6 presents the results in CP task, and other results are in Appendix A.4.

**Number of spatial groups \(n_{s}/n_{r}\).** We first analyze the effects made by the number of partitioned sectors \(n_{s}\) and rings \(n_{r}\). By increasing \(n_{s}/n_{r}\) to partition more subspaces, SHGNN can model more diverse spatial relations and further capture the diversity of spatial heterophily in a more fine-grained manner. However, over-dense partitions bring no further improvements but even slight performance declines. A possible explanation is that some subspaces contain too few neighbors to support its representation learning.

**Partition head number \(M_{s}/M_{r}\).** We also study the impact of head number \(M_{s}/M_{r}\) in the multi-head partition strategy. It can be observed that, compared to the single partition \((M_{s},M_{r}=1)\), SHGNN using such a strategy \((M_{s},M_{r}=2)\) can evidently perform better, thanks to the complementing role between two heads. When \(M_{s}\) and \(M_{r}\) continue to increase, the model generally gets fewer further improvements, and too many heads with additional redundancy may sometimes result in performance degradation. Thus, we recommend to set a small head number but larger than 1(e.g., 2), which is good enough while keeping efficiency.

## 6. Related Work

Here we briefly review two related topics: GNNs for urban applications and GNNs with heterophily.

**GNNs for Urban Applications.** As a powerful approach to representing relational data, GNN models are widely adapted in recent studies to learn on urban graphs, and achieve remarkable performance in various applications, including traffic forecasting (Gan et al., 2017; Li et al., 2018; Li et al., 2019; Li et al., 2019; Li et al., 2019; Li et al., 2019), bike demand prediction (Li et al., 2019), region embedding (Li et al., 2019; Li et al., 2019), regional economy prediction (Li et al., 2019) and special region discovery (Li et al., 2019). There are a few works that tend to encode the location information in GNNs' message passing process (Li et al., 2019; Li et al., 2019) in a special domain (POI relation prediction). But these methods fail to generalize to urban graphs with heterophily, which may significantly degrade their performance in other urban applications.

**GNNs with Heterophily.** Our research is also related to the studies of graph heterophily. Here we only make a brief introduction to heterophilic GNNs and refer readers to a recent comprehensive survey (Li et al., 2019). Such approaches solve the heterophily problem basically in the following two ways. The first branch is to reconstruct the homophilic neighborhood with similar nodes on the graph measured by different criteria. The used criteria include the structural similarity defined by the distance in latent space (Li et al., 2019) or degree sequence (Li et al., 2019), the difference of attention scores (Li et al., 2019), cosine similarity of node attributes (Li et al., 2019; Li et al., 2019), nodes' ability to mutually represent each other (Li et al., 2019) and so on. However, as pointed out by He et al. (He et al., 2019), these methods will damage the network topology and tamper with the original real-world dependencies on the urban graph.

Another branch tends to modify the GNN architecture to handle the difference information on heterophilic graphs, in contrast to the Laplacian smoothing (Li et al., 2019) of typical GNNs, such as processing neighbors in different classes separately (Li et al., 2019; Li et al., 2019), explicitly aggregating features from higher-order neighbors in each layer (Li et al., 2019; Li et al., 2019), allowing the high-frequency information by passing signed messages (Li et al., 2019; Li et al., 2019; Li et al., 2019; Li et al., 2019), and combining outputs of each layer (including ego features) to also empower the GNNs with a high-pass ability (Li et al., 2019; Li et al., 2019; Li et al., 2019). However, most of these methods do not consider the diversity of dissimilarity distribution between the central node and different neighbors, especially with different spatial relations.

## 7. Conclusion

In this paper, we studied the unique spatial heterophily of the urban graph and developed a spatial heterophily-aware graph neural network. We designed a spatial diversity score to uncover the diversity of heterophily at different spatial locations in the neighborhood, and showed the limitation of existing GNNs for handling diverse heterophily distributions on urban graphs. Further, motivated by the analysis that spatially close neighbors present a more similar mode of heterophily, we proposed a novel method, named SHGNN, which can group spatially close neighbors together and separately process each group with less diversity inside, to tackle the spatial heterophily in a divide-and-conquer way. Finally, extensive evaluations demonstrate the effectiveness of our approach.

#### Acknowledgments

This work is supported in part by Foshan HKUST Projects (FSUST21-FYTRI01A, FSUST21-FYTRI02A).

Figure 6. Parameter analysis in CP task.