Representation Learning on Spatial Networks
Authors: Zheng Zhang
Liang Zhao
Venue: NeurIPS 2021 Poster (2021)
Keywords: Spatial networks
graph neural network
representation learning

Abstract: Spatial networks are networks for which the nodes and edges are constrained by geometry and embedded in real space, which has crucial effects on their topological properties. Although tremendous success has been achieved in spatial and network representation separately in recent years, there exist very little works on the representation of spatial networks. Extracting powerful representations from spatial networks requires the development of appropriate tools to uncover the pairing of both spatial and network information in the appearance of node permutation invariant, and rotation and translation invariant. Hence it can not be modeled merely with either spatial or network models individually. To address these challenges, this paper proposes a generic framework for spatial network representation learning. Specifically, a provably information-lossless and roto-translation invariant representation of spatial information on networks is presented. Then a higher-order spatial network convolution operation that adapts to our proposed representation is introduced. To ensure efficiency, we also propose a new approach that relied on sampling random spanning trees to reduce the time and memory complexity from $O(N^3)$ to $O(N)$. We demonstrate the strength of our proposed framework through extensive experiments on both synthetic and real-world datasets. The code for the proposed model is available at \url{https://github.com/rollingstonezz/SGMP_code}. 

Representation Learning on Spatial Networks
Zheng Zhang
Liang Zhao Department of Computer Science
Department of Computer Science
Emory University Atlanta, GA 30322, USA
Emory University Atlanta, GA 30322, USA
zheng zhangeemory edu
liang zhao@emory. edu
Abstract
Spatial networks are networks for which the nodes and edges are constrained by geometry and embedded in real space, which has crucial effects on their topolog- ical properties. Although tremendous success has been achieved in spatial and network representation separately in recent years, there exist very little works on the representation of spatial networks. Extracting powerful representations from spatial networks requires the development of appropriate tools to uncover the pairing of both spatial and network information in the appearance of node permutation invariant, and rotation and translation invariant. Hence it not be modeled merely with either spatial or network models individually. To ad- dress these challenges, this paper proposes generic framework for spatial net- work representation learning. Specifically, a provably information-losee and rotation-translatioo invariant representation of spatial information networks is presented. Then a higher-order spatial network convolution operation that adapts to our proposed representation is introduced. To ensure efficiency, we also propose new approach that relied on sampling random spanning trees to reduce the time and space complexity from O(N²) O(N). We demonstrate the strength of our proposed framework through extensive experiments on both synthetic and real-world datasets. The code for the proposed model is available btttps://gither www.oo////oo/oo wtw./oooooooooonneeeeeeoeoeeeeee www.innsttoeezzSMMP..co Bttps/GMMP_Codoo
Introduction
Spatial data and network data are both popular types of data modern big data era. The study of spatial data focuses on the properties of continuous spatial entities under specific geometry, while analysis of network data investigates the properties of discrete objects and their pairwise relationship. Spanning these two data types, spatial networks a crucial type of data structure that nodes occupy po- sitions in Euclidean space, where spatial patterns and constraints may have a strong effect on their connectivity patterns (6) Understanding the mecha- nism of organizing spatial networks has significant importance for broad range fields [29]. ranging
(a) Geometric Space
(b) Network
Continuous data
Discrete data
from micro-scale (e.g., molecule structure (.4).
(c) A Spatial Network
middle-scale (e.g., biological neural network (31)
to macro-scale (e.g.. mobility networks [18 Ef- fectively learning the representations of spatial net- works is extremely challenging due to the close interactions between network and spatial topology, the incompatibility between the treatments for dis- crete and continuous data, and particular properties
topology depends embedding space
Figure I: Spatial network contains not only the infor- mation of network topology and spatial topology but also their interaction.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

such as permutation invariant and rotation-tranae translation invariant. Spatial networks have long been researched in the domains such as physics and mathematics, which usually extend complex networks and graph theory into spatial networks [80 71- They typically rely on network generation principles predefined by human heuristics and prior knowledge. Such methods usually characterize well on the aspects of the data that have been covered by the predefined principles, but not on those have not been covered(6). However, the underlying network process in complex networks is largely unknown and extremely difficult to be predefined in simple rules, especially in crucial and open domains such as brain network modeling [8]. network catastrophic failure 722.. and protein folding 127].
Remarkable progress has been made towards generalizing deep representation learning approaches in spatial data and network data [96] 46 43 28), respectively, in recent years. For spatial data, deep
learning achieved significant progress in different commonly used formats such as images [53] 75
61 21), point clouds [4 71 [5], meshes
85 90]. and volumetric grids (95 66]. On the other hand,
deep learning has also boosted the research of encoding graph structure on network data 46
5 45
and downstream applications such as recommender systems [99 60, drug discovery
33
22
FinTech [91], customer care [93], and natural language processing 662 92)
Despite the respective progress in representation learning on spatial data and network data in par- allel, the representation learning for spatial networks have been largely underexplored and has just started to attract fast-increasing attention. Merely combining spatial and graph representa- tions separately cannot handle that for spatial networks where spatial and network process are For example, Fig. 2 shows simple example with a pair of spatial networks, in which there are different formation rules on the edges relied on the spa- tial distance, that is non-distinguishable for spatial and network embedding methods, respectively. Few recent attempts have been proposed to handle representation learning on spatial net- works but still suffer from key challenges: Spatial network representation learning is a problem extremely difficult to address due to several unique challenges: 1) Difficult in distinguishing the patterns that require joint spatial and graph consideration. Examples like Figure. 2 that share the same spatial and network topology, respectively, but with sig- nificantly different interaction mechanisms, are vonndistinguishable to either spatial or graph methods. 2) Difficult in jointly maintaining that the learned representation is invariant to node permutation, and rotation and translation transformations, Notice that spatial and graph information confine each other which neutralizes conventional methods to have either of them. For example, although point clouds representation learning can easily preserve rotation- and cianslaaion-invaiian by using spatial nearest neighbors, here in spatial networks the neighbor is confined also by graph neighbors. Such additional confinement largely harden our task. 3) High efficiency and scalability in the graph size. The confinement between spatial and graph information inevitably leads to taking into account more entities simultaneously to maintain sufficient information. The requirement to handle incremental information increases the demand for model efficiency and scalability.
deeply coupled together 68 33
Figure 2: The left figure reflects closer nodes tend to connect with each other (known as the first law goography (79), while the right figure reflects a spatial tele-connecting pat- tern where faraway nodes tend to connect. Discriminating these two spatial networks requires new method that can jointly consider spatial and network properties.
In order to address all the aforementioned challenges, this paper proposes a new spatial graph message passing neural network (SGMP) for learning the representations of generic spatial networks, with theoretical guarantees on discriminative power and various spatial and network properties, and an accelerating algorithm which adjusts to our theoretical framework. Specifically, model the intrinsic coupled spatial and graph properties, we propose a novel message passing neural network organically aggregate the spatial and graph information. To ensure the invariance of learned representation under rotation and translation transformations, novel way to represent the node spatial information by characterizing geometric invariant features with lossless information is proposed. To alleviate the efficiency issue, we propose a new accelerating algorithm for learning on graph-structured data. The proposed accelerating algorithm effectively reduces the time and memory complexity from O(N3) to O(N), and maintains the theoretical guarantees for spatial networks. Finally, we demonstrate the strength of our theoretical findings through extensive experiments on both synthetic datasets and real-world datasets.
capture and

---

2 Related Work
There has been long time of research efforts on the subjects of spatial net- works (6. the area of quantitative geography, Haggett and Chorley discussed the relevance of space in the formation and evolution of networks, and developed models to characterize spatial networks at least fourty years ago [44] 17. New insights leading to modern quantitative solutions are gained due
Spatial Networks
to the advance in complex networks 32 89
3 20], and appears in more practical fields such as
transportation networks 2 54 551, mobility networks
18 24 biological networks [31 [6). and
computational chemistry 38 73 52
Geometric Deep Learning. This more recent domain which handles -un-ideli structured data such as graphs and manifolds [I3]
Geometric Deep Learning on Manifolds. There a large body of research efforts of generalizing deep learning models to 3D shapes as manifolds in the computer graphics community. Many works have been conducted to find better approach to generalize convolution-lik operations to the non- Euclidean domain 665 10 74 98 64 [9]. J. Masci et al. proposed the framework of generalizing convolution neural network paradigm to manifolds by applying filters to extract local patches in polar coordinates [65]. Litany el at. [59] proposed FMNet to learn the dense correspondence between deformable 3D shapes.
Geometric Deep Learning on Graphs. The carliest attempts networks to graphs are attributed to M. Gori et at. [40]. More recently, a number of approaches encouraged by the success of convolutional neural networks (53) have attempted to generalize the notion of convolution to graphs. One important stream of convolution graph neural networks is spectral-based where emerges after the pioneering work of Bruna et at. [1] which based on the
aware of to generalize neural
spectral graph theory. There have been many following works 48
25 [1] [66. Another stream of
work define graph convolutions as extracting locally connected regions from the graph [30 58
69 45)
97/67). Many of these works were formulated in the family of message passing neural networks [38
which apply parametric functions to node and its proximities, and use pooling operations to generate features for the node. Efficiency and scalability for deep graph learning is very important especially for large graphs and higher-order operations, which triggers research on accelerating GNNs 45 16 15]. Hamilton et at. 45 first introduced sampling scheme on neighborhood nodes to
restrict the size. Chen et at. 166 proposed a method which samples vertices rather than neighbors. However, none of these works can guarantee the sampled graph is connected.
Deep Learning on Spatial Data. Deep learning has also boosted the study on spatial data. Significant progress has been achieved on deep learning on images since AlexNet [47 75 For 3D point clouds, PointNet [71] is pioneering work which addressed the permutation invariance by symmetric function. PointCNN (57 transforms the input points into a latent and potentially canonical order by a X-conv transformations, Volumetric-basee methods usually apply 3D Convolution Neural Network (CNN) to 3D grids [95] 666. Wang et at. (85) first performed shape segmentation on 3D meshes by laking three low-level geometric features as its input.
Despite the success of generalizing deep learning to network and spatial data separately, there has been relatively little work that simultaneously characterize both of them and their interaction. Previous models such as [38 73 52 are domain-specific, 773
52
treat spatial networks as point clouds which
ignores the influence of network structure, and 887 86 consider POI (Point of Interest) categories, hence such concept graphs are not physically embedded in a geometric space. In addition, existing typically utilize the off-the-shelf deep neural networks with Cartesian coordinates as inputs and a large amount of rotation-and translation-augment expensive and lacks theoretical guarantee of rotation- and translation-invariant on the representation. To the best of our knowledge, our proposed method is the first generic framework of spatial network representation learning that handles substantial properties of rotation- and translation-invarian and the interplay between spatial and graph patterns with a theoretical guarantee.
works 88 23
data, which is computationally
3 Preliminaries
In this section, we first formalize spatial networks, and the problem of representation learning on spatial networks, then we introduce the challenges in order to solve this problem.
Spatial graphs (also known spatial networks (6) are networks for which the nodes and edges are embedded in a geometric space. Spatial networks is ubiquitous in real world, such as molecular graphs (94). biological neural networks (3I), and mobility networks [8] where the spatial and
3

---

network properties are usually coupled together tightly. For example, chemical bonds are derived from spatially close atoms, and fiber nerves tend to connect neurons close to each other. A spatial network is typically defined as S = (G, P), where graph G = (V, F.) denotes the graph topology such that V is the set of N nodes and F S V x is the set of M edges. Eij E is an edge connecting nodes 2 and fy E V. P denotes the spatial information that is expressed as set of [4 points P = { Mis 24, Mr: 2s E ] in Cartesian coordinate system, such that for a node v; E V. its coordinate is denoted as (Ti, Mk, z4) E P. Permutation invariance are crucial to graph structured data 196). The collections of permutation-invaaiiee
functions on graph-structured data is defined so Sn, where S, is the permutation group of elements. Rotation
that f(r ST) f(S), for all and translation invariance are in natural and common requirements for spatial data [6 52). The collections of rotation- and consslationinvariii
functions spatial networks is defined so that ((P)) = J(G, P), for all T E SF(3), where SF(() is the continuous Lie group of rotation and translation transformations in R.3
The main goal of this paper is to learn the representation (S) of spatial network = (G, P), with the simultaneous satisfaction of strong discriminative power and the aforementioned significant symmetry properties, which is a problem extremely difficult to address due to several unique challenges: 1) Difficult in distinguishing the patterns that require joint spatial and graph consideration. 2) Difficult in jointly maintaining that the representation is invariant to node permutations, rotation and translation transformations. 3) High efficiency and scalability according to the requirement of handling incremental information.
4 Approach
In order to achieve the novel spatial network representation learning by addressing the above- mentioned challenges, we propose a new method named spatial graph message passing neural network (SGMP) and a new accelerating algorithm which relies on sampling random spanning trees. Specifically, to discriminate spatial networks especially for the spatial-graph joint patterns, we propose new message passing scenario which aggregates the node spatial information via higher-order edges as shown in Figure B|a) and elaborated in Section 4.2 This scenario preserves graph and spatial information while aggregation with theoretical guarantees. To ensure that the representation is invariant to rotation and translation transformations, we propose to characterize several geometric properties in length three path, which proved to represent node spatial information with guarantee on the properties of intation-inariann
invariant, and information-lossler This is illustrated in Figure and will be detailed in Section 4.1 To address the efficiency issue, an graph-sampled
innovative sampling algorithm for accelerating training named Kirchhoff-normallzz random spanning tree is proposed. The algorithm reduces the time and space complexity from O(N3) to O(N) while still stay equivalent to original graph, which will be discussed in details in Section 4.3
4.1 Node Spatial Information Representation
we need a novel way to represent the node spatial information that can preserve all the spatial structure information losslessly and also maintain rotation and trans- lation invariance. We cannot directly use the Cartesian coordinates because they are not rotation- and translation-invarian Although there are conventional node spatial information representation methods that maintained the rotation and translation invariance in the domain of spatial deep learn- ing [78] 36), we cannot simply use them to handle spatial networks because they cannot consider the confinement on neighborhood from graph perspective. Otherwise, the coupled apatial-graph properties cannot be captured. Therefore, spatial information. The most simplest way is to just use the distance among nodes and we can have 4 to ensure the spatial information is preserved. However, we want to minimize the length of the path since the size of the neighborhood grows with a factor of ONN) when one more length for the path is considered. To achieve this, we successfully reduce n to 3 by proposing a new spatial information representation on path, where we use geometry features distance, angle, and torsion as detailed in the following equation and also illustrated in Figure 3(b).
As mentioned above and in Figure 2
consider to leverage length n path to represent the node
The spatial information of a spatial network S (G, P) with N nodes can be expressed as a set of Cartesian coordinates P = { Vs. 2,) Ui. 2 R) It can also be represented as P Nx3 in a matrix form. The set of all length n path starts from node can be represented as II. Particularly, a length three path 1;- + Dy + Uk - Up can be expressed as Tijkp E II3 Given a spatial network S where its graph G is strongly connected and the longest path Ç 2 3. the proposed

---

(a)
SPNN
(12) (2) (2))
hg
P.. (N) M0 (1
SPNN
(b)
Lipp
(R,
SIR
ML.P
Pijhp
m (Tola)
deg
11
T
Lijh
(N 0M0.4990 AA9
SPNN
Figure 3: Illustration of the proposed spatial graph message passing neural network (SGMP). (a) The process of updating the hidden state embedding 11t)) of node v, by aggregating the spatial-gran -rapp message information from length three path. (b) An example to illustrate cach elements in our spatial information representation (Equation [T. Here Lupp is the plane defined by node v, V, and dp and Lesa is the plane defined by node Vs f/y and Ug- (c) This is the spatial path neural network block which is designed learn the coupled spatial-graph property. This block also maintains the invariance to rotation and translation transformations by the spatial information representation (SIR).
spatial information representation can be expressed by of its length three path Tijkp
(dey, dyk: dip; Oijks Besps :Piskp):
(1)
where
d, |P Pulle jjkk
|P s& dp = |P pppll
Púj
P5k )), Oipp arccos(
P P Piy)), dij djp
0ykk arccos(
dij djb
Pijkp Parity- Pijkpt
Pij x Pjt
Pij X Pir
(2)
Djjk =
P& X 1
Dip
Pij Pipl2
Pigkp = arccos( (nijk, njkp)).
Parity nyjk X nijp Pij
Inikk X nijpl [P
Theorem 1. Here the distances dij E [0, angles Oizk. E 10, π)) and torsions Piikpp E [- x) are rigorously invariant under all rotation and translation transformations'
(SF(3).
The proof for Theorem is straightforward and can be found in Appendix B It is remarkable to mention that the proposed representation in Equation not only satisfies the invariance under rotation and translation transformation but also retains the necessary information to reconstruct the original spatial networks under weak conditions, described in the following theorem.
Given spatial network S = (G, P), G is a strongly connected graph with longest path Ç then given Cartesian coordinates of three non-collinear connected nodes (uy, Uky Up) in length three path Tiikp of one node the Cartesian coordinates P can be determined by the representation defined in Equation] 7
Theorem 2.
The proof to this theorem is a consequence of the following lemma, which is proved Appendix
Lemma 1. Given Cartesian coordinates of three non-collinear connected nodes (Vzz Uks Up) in length three puth Tiskp of one node V;, the Cartesian coordinate P; of node vi can be determined by the representation defined in Equation 7
5

---

Now we can prove Theorem 2. As stated in Lemma 1, the Cartesian coordinate of node can be determined by its connected neighbors Uj, Ug. up in the path of Tijkp- Due to the property of strong connectivity of graph G = (V, F), we can repeatly solve the coordinate of connected node to the set of nodes with known coordinates. Thus, start from an arbitrary length three path the Cartesian coordinates P of whole spatial networks is determined.
4.2 Spatial Graph Message Passing Neural Network (SGMP)
Spatial network representation learning requires us do convolution that aggregates jointly the graph and spatial information from the graph neighborhood. The most important issue is to maintain the discriminative power without loss of graph and spatial information during the aggregation operation. In the meanwhile, we need to maintain permutation comnutation-ivvaiinnt rotation- and translation-invariant, To achieve this, we propose the following operation to update the hidden state embedding I!? of node 2s by aggregate the messages passing on all its length three path Ilz.
h (++1)) o00)
o00 (SUM(f (Tagkp)) (TTg))) E mz))).
(3)
where (0)) is multilayer perceptron (MLP) with ReLU activation function and the spatial-graph interacted message m ! (Tishe) is generated by spatial path neural network (SPNN) block:
10 (Teskp)) (5(0) (Tijkp);
(Mi(()gkp)))
m (Taskp)) (1 10) N1 11 n22), (Ttsppp))) (dey, dike djp= Oigk. Oepp. Pktkk))
(4)
where (5(1) and si(() are two nonlinear functions to extract the complicated coupling relationship between spatial and graph information, in which we use the multilayer perceptron (MLP) with ReLU
as the activation function in our settings.
Finally, the representation of spatial network can be achieved by applying a graph aggregation operation: f(S) AGG ((M (1) E G)), where AGG is a permutation invariant function such as SUM or MEAN, and K' is the number of our message passing operation layers.
Since the node spatial information is already rotation- and iottlatioonivvarinn these properties can be intrinsically preserved by the operation in Equation 3 Node permutation will also be preserved due to the usage of the permutation invariant function SUM. Moreover, the following theorem proves that the discriminative power is also preserved from the perspective of maintaining the necessary spatial information, when the dimensions of hidden state embedding are sufficiently large.
Theorem 3. Let denote the collection of spatial networks with N nodes given the graph G (V. E), and F denote the class of our SGMP functions while y is continuous function. Suppose 9: S + R a continuous set function. For all O, there exists a function F, such that for any S E S,
Lg(S) - (f()) <E.
(5)
The proof can be found in Appendix B The key idea to the proof of this theorem is that we can discretize the continuous spatial information by partitioning the space into voxels.
4.3 Accelerate Training through Sampling Random Spanning Trees
Note that our model is a high order message passing neural network whose time and memory consumption cubic to the average number of node degree. To reduce the complexity of graph neural networks, a typical way is based on sampling [96]. Many graph-sampling methods have been proposed for accelerating graph neural network [5] 16]. which typically focus on randomly extracting a subgraph from the original graph. However, they cannot guarantee the generated graph a strongly connected graph, which required by our node spatial information representation in order to maintain no information loss. To ensure that the sampled graphs are connected and sparse, we innovatively propose a
graph-sampled random spanning tree method for accelerating the training. The proposed method largely reduces the complexity and maintains the equivalence to the original graph. Specifically, a spanning tree = (V, Er) of an undirected graph G (V, E') that is tree which contains all vertices in G. The number of edges of spanning trees is

---

[El] = |V| 1, which implies that the time and space complexity during training will not be affected by the number of original edges |E| in graph G. We modify our updating operation in Equation as
h (++1)) =6(0) (SUM({ (T(Rk)) E l));
(6)
where we use 3r' denotes the set of all length three path starts from node vi in a sampled spanning tree 7 = (V. F. It is noticed in Equation 6 that randomly sampling spanning trees 7 from the original graph G will introduce an uneven probability distribution for edges, which results in non- uniform weights for path messages in our proposed message passing layer. Here we introduce the firchhoff-normalizer method to remove the uneven distribution by pre-computing the sampling probability of path Tijkp in sampled random spanning tree T. We further modify the Equation
as
h =
- =0 (SU)(
(9 (Trkp)) (Fagin)
Tiskp 1)
where (FFsjkp) is the sampled probability of path Teskp in a random spanning tree.
Proposition 1. Let T denote uniformly random spanning tree of a graph G. Then for length three path Tijkp = (exj. Cyk: Ckp) we have that
Pr(miskp E T) det(l
where Y is called the transfer function matrix 9 The proof is achieved by applying graph theory theorems including Kirchhoff matrix tree theorem [4] and be found in Appendix B] The following result establishes that the approximated form in Equation 7 consistent to original form.
theorem [12), which can
Proposition 2. If o()) is continuous, the expectation of the approximated form in Equation converges surely to the original form in Equation when the number of samples is sufficiently large.
The proof is consequence of the strong law of large numbers and the continuous mapping theorem, which can also be found in Appendix B
Complexity analysis of single layer. Consider spatial network with N nodes and dense edge data, our full SGMP layer has ((N3) time and space complexity according to the size of the neighborhood. Our accelerating algorithm based on sampling random spanning tree, however, has only O(N) time and space complexity as only N - 1 edges exist in the generated spanning trees.
5 Experiments
In this section, the experimental settings are introduced first, then the performance of the proposed method is presented through a set of comprehensive experiments. All experiments are conducted on 64-bit machine with an NVIDIA GPU (GTX 1080 Ti, 11016 MHz, 11 GB GDDR5). The proposed method is implemented with Pytorch deep learning framework (70]
5.1 Experiment Setup
(i) Synthetic dataset. The spatial growth graph model 66] is spatial variant of the preferential attachment model proposed by Albert and Barabasi []]. which describes that spatial information concerns the formation of networks and long-range links are usually connecting the hubs (well-connected nodes). The process to generate such spatial networks starts from an initial connected network of mo nodes and introduces a new node n at each time step. The new node is allowed to make m < mo connections towards existing nodes with a probability II,- ~ F, F (n, i)], where k; is the degree of node i and F' is an exponential function Fdd) = e dd/re of the euclidean distance d dg(n, i) between the node and the node (5). General characteristics of spatial networks O such as clustering coefficient, f4, spatial diameter D, spatial radius are set as the prediction targets. Besides, we also add the interaction range re. which is significant coupled spatial-grap formation of the spatial networks, as another prediction target. We vary the size and other parameters (according to Appendix. for details) of spatial networks to collect 3, 200 samples our synthetic dataset. (ūi) Real-world molecular property datasets. We experiment on 5 chemical molecule benchmark datasets from (94), including both classification (BACE, BBBP) and regression (ESOL,
Datasets
label that affects the
LIPO, QM9). Particularly, QM9 is a multi-task regression benchmark with 12 quantum mechanics
7

---

Task
Regression
Chasiisattio
Table 1: Root mean square error (RMSE) results
SUME
SahNat
GIN
SGCN
DimeNNt
SGMP (with so
PointNer
GAT
GuEeGGNN
0.133,003
0.1001022:
0:129,0013
0.12910003
0.128.001;
0.089L.013)
000881001
0.29110211
6.733:074)
6.747:087)
1.266.147)
1.291:0991
100600580
1.399055)
0,500
0.666
6.36
0.556
0.252.023)
066550020
042100060
1,611
1,551 066)
1.412/0599
1,1100311
1,266.019)
1.736
1,7166017)
1.35200211
PPENer
Dilmet
DioneNet
SchNct
GAT
SOMP swith
GaEdGNNN
0612:484:
ESOL
0.743
02700/221
0.780.047)
0.7830083)
02166
06250080)
0.73%
0.601.050)
0.357.049
0.8650007)
(1779
(.660(011)
0,555,045)
0:561.177)
0.808, 0.503.017)
13333.1333
0.544,059)
0.818.127))
0.720.
0.566.100)
081110024
0.791,031)
0816) (023)
BACE
0.778.
019220023)
013)
BEBP
026440366
0.890.020)
0.8731024)
0:34401300
0.85810200
0.354(015))
02631002)
Table 2: Results for four molecule property datascts and the
synthetic dataset. Here is clustering coef- ficient, D is spatial diameter, is spatial radius and re the interaction radius in the formation of spatial growth graph.
HCP brain network. We report accuracy score for BACE
and BBBP datasets, root mean square error (RMSE) for ESOL and LIPO, and mean average error (MAE) for HCP brain network dataset.
properties. The data is obtained from the pytorch-geometric library brain network dataset. We also conducted an experiment using the structural connectivity (SC) of the brain network to predict the age of the subjects, which is significant task in understanding the aging process of the human brain [50]. In specific, SC is processed from the Magnetic Resonance Imaging (MRI) data obtained from the human connectome project (HCP) (82) By following the preprocessing procedure in [84), the SC data is constructed by applying probabilistic tracking on the diffusion MRI data using the Probtrackx tool from FMRIB Software Library
35
(iii) Real-world HCP
49 with 68 predefined regions of
interest (ROIs). Then a threshold is applied to SC data to construct the brain networks 777 37|. The
spatial coordinates of regions are expressed as the center point of each region.
Comparison methods. To the best of our knowledge, there has been little previous work to handle the generic spatial networks. Spatial graph convolutional networks (SGCN) is a recently proposed method to handle generic spatial networks by applying a convolution operation to learn the spatial- graph interacted information using the relative coordinates between nodes and their first-order neighbors. In addition, we compare with three strong graph neural networks (GIN, GAT and Gated GNN) methods and four spatial neural networks (PointNet, PPFNet, SchNet, and DimeNet) methods for comparisons. For methods in the class of GNNs, we feed the Cartesian coordinates as node attributes while we add the node attribute and graph connectivity information to the class of SNNs for a fair comparison. The details about the benchmark models can be found in Appendix. C Besides the models above, we also compare our model with state-of sfate-of-the-are higher-order graph neural networks PPGN 63 in the QM9 benchmark, the results are provided from original authors.
5.2 Experimental Performance
In this section, the performance of the proposed method and its accelerated algorithm with sampling random spanning tree (with st), as well other methods on both synthetic and real-world datasets presented first. Then we present the efficiency test on our sampling random spanning trees method. In addition, we measure the exactness of invariance of our proposed model under translation and rotation transformations.
Effectiveness results. . (i) Synthetic Dataset. Table D summarizes the effectiveness comparison for the synthetic dataset, where our proposed SGMP model with sampling spanning tree outperforms the best benchmark model (GatedGNN) by 35%7% on average. Especially, our model achieves lower error on the target of interaction radius (rz), which proves that our proposed model can better capture and exploit the significant coupled spatial-graph characteristics in spatial networks. * (ii) Real-world Datasets. Table presents the results of four molecule property datasets and the HCP brain network dataset, where our proposed method achieves the best results in 4 out of 5 datasets. The results for the QM9 dataset are presented in Table 3 where our proposed method demonstrates its strength through outperforming the benchmark methods in 10 out of 12 targets, which is an improvement by over 14% on average. Particularly. we notice that the performance of the class of SNNs achieved significantly better results than the class of GNNs by a 38% improvement on average, which arguably implics that the quantum mechanics targets of the QM9 dataset are dominated by the spatial information. In addition, the group of jointly-spatial methods. The twelve quantum mechanical properties in the QM9 dataset seems highly related to the spatial geometry properties between nodes. For example, the formation energy (U) is related to the distances, angles, and torsions among nodes. In this situation, we notice that the performance of the group of point-cloud- based methods is significantly better than the group of GNN based methods, and coupled spatial- graph property.
to the group of point-cloud-basse sirtiial-grah-booa graph-based methods achieved 68 68.9% improvement compared
graph-based methods can better explore the
8

---

Target
GIN
Gised
PointNet
PPENet
SOCNN
PAGN
SchNet
DimeNet
SGMP
SGMP
0,583
0.661
0,543
0.465
0,503
0,503
0.093
0:452
0,360
0.130
0.187
MBOMO
326.7
206-2
47.3
45.7
175.4
237.1
135.4
123.8
136.9
141.7
57.1
15L6
61.0
44.7
67.9
4
361.4
510.3
314,4
245.5
221.9
275.5
78,9
120.6
103.7
83.7
98.8
63.7
97.1
14.5
27.8
34.9
ZPVE
12.3
15.7
12.0
7.0
74
7.4
10.8
34,3
3.1
2.3
2.0
260.1
335.9
211.5
112.7
153.5
201.3
36.8
101.7
26.8
26.1
31,9
244.7
36.8
II
269.0
329.7
239.2
123.1
157.6
19922
36.8
107.0
27.9
27.5
31.3
G
252.7
314.1
221.1
124.3
158.
207
36,4
95.0
25.8
24.6
28,2
Table 3: The mean average eтrоr (MAF) results for QM9 dataset.
ADR (%)
wo
W
speed up
2
0.203s
0.158s
1.3x
0.323s
0.184s
1.7x
Time [sccones)
111
PPPhic
10
7.52s
0.225s
33.4x
SGCN
31.43s
0.209s
150.3x
Direker
20
80.96s
0,213s
379.7x
SGMP
0.193s
SUMP (4)
100
0,214s
Table 4: Training time per epoch for our full model without sampling spanning tree (wo st) and accelcrating method with sampling spanning tree (w st). (-) indicates an out-of-memory emoor The sampling algorithm is on average 113 times faster than our full method. ADR is short for the average degrec ratio.
20 50
Average dogree ratio (1()
Figure 4: Efficiency analysis of our proposed models and all benchmark models. Note that our proposed algorithm with sampling random spanning tree significantly improves the scalability and efficiency.
Efficiency analysis. To validate the efficiency of the proposed sampling random spanning tree algorithm, we use our HCP brain network dataset with different thresholds on structural connectivity (SC) obtain different average degrees for the nodes. The number of nodes is a fixed number (68) while we vary the average of degrees ratio (ADR= Ey
E where E is the number of edges and E is the
number of edges in complete graphs, e.g. ADR= 100% indicates complete graph). We report the results of the average training time per epoch among all models for 20 epochs. As shown in Figure 4 and Table our accelerating algorithm achieves significant improvements in training efficiency, Note that our method is even faster than most of the first-order methods when the graph connections are dense (ADR over 50%). Notice that higher-ordh
methods (c.g. our full method is third-order and DimeNet is second-order) are unable to handle complete graphs due to the limits of GPU memory. The scalability of our sampling method is remarkable, which can maintain a constant time and space complexity with the increasing number of connected edges.
Rotation and translation invariant test. Similar to previous work [3), we also measure the rotation and translation robustness by uniformly adding translation and rotation transformations to the input Cartesian coordinates. Here we only report the accuracy results of classification task on the molecular dataset BACE due to the space limit while the results are similar on all datasets. According Figure 5 we can note that the performance of our proposed model stays invariant under both translation and rotation transformations. SchNet and DimeNet can also achieve invariance under transformations because they also only the rotation- and vanslation-invariant spatial features their models. PPFNet can stay invariant under rotation transformations but not translation transformations because it preserves the origin in the model. On the other hand, SGCN can stay invariant under translation transformations but not rotation invariant because only utilizes relative coordinates. This experiment validates the importance of applying a rotation- and matsslaaioninvaiiann model since we can observe that the performance of models without a theoretical guarantee drop significantly under adding rotation and translation transformations.
Conclusion
This paper focuses on the crucial problem of learning powerful representations from spatial networks, which has tightly coupled spatial and graph information that can not be addressed by applying spatial and network methods separately. The proposed spatial graph message passing neural network (SGMP) effectively addresses the unique challenges in spatial networks by jointly considering the spatial and graph properties, and still maintain the invariance to node permutations, well as rotation and

---

GIN
GAT
0.8
0.8
GatedGNN
Pointle:
Accuracc
0.7
Accuracy
0.7
PPfNet
SGCN
SchNet
DimeNet
0.6
0.6
SGMP
0.5
0.5
0.4
0.4
30
90
150
Magnitude rotation anglo
Magnitude of translation distance
Figure 5: Robustness test of rotation and translation invariant: æ-axis shows data augmentation the test set. The v-value corresponds the magnitude of rotation angle (left) translation distance (right). The y-axis shows the accuracy score the test
translation transformations. In addition, our proposed accelerating algorithm largely alleviates the efficiency issue in solving spatial network issues. Experimental results synthetic and real-world datasets demonstrate the outstanding discriminative power of our model, and the efficiency test shows remarkable improvement in training time and scalability of our proposed accelerating method.
Acknowledgement
This work was supported by the National Science Foundation (NSF) Grant No. 1755850, No. 1841520, No. 2007716, No. 2007976, No. 1942594, No. 1907805, Jeffress Memorial Trust Award, Amazon Research Award, NVIDIA GPU Grant, and Design Knowledge Company (subcontract number: 10827.002. (0.2.002..20.04) 120.04). The authors acknowledge Emory Computer Science department for providing computational resources and technical support that have contributed to the experimental results reported within this paper.
References
[1] Réka Albert and Albert-László Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002.
[2] Jayanth R Banavar, Amos Maritan, and Andrea Rinaldo. Size and form in efficient transportation networks. Nature, 3990 1999.
[3] Albert-László Barabási and Eric Bonabeau. Scale-free networks. Scientific american, 288(5):60- 69, 2003.
[4] Alain Barrat, Mare Barthelemy, and Alessandro Vespignani. Dynamical processes on complex networks. Cambridge university press, 2008
[5] Mare Barthélemy. Crossover from scale-free to spatial networks. EPL (Europhysics Letters), 63(6):915, 2003.
[6] Marc Barthélemy. Spatial networks. Physics Reports, 499(1-3):1-101, 2011.
[7] Mare Barthelemy. Morphogenesis of spatial networks. Springer, 2018.
[8] Joost Bastings, Ivan Titov, Wilker Aziz, Diego Marcheggiani, and Khalil Sima' an. Graph convo- lutional encoders for syntax-aware neural machine translation. arXiv preprint arXivv1704.046755 2017.
[9] Stephen P Borgatti and Daniel S Halgin. On network theory. Organization science, 22(5): 168- 1181, 2011.
[10] Davide Boscaini, Jonathan Masci, Emanuele Rodoià, and Michael Bronstein. Learning shape correspondence with anisotropic convolutional neural networks. In Proceedings of the 30th International Conference Neural Information Processing Systems, pages 3197-3205, 2016.
10

---

[11] Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint 13X2:63322.603, 2013.
[12] Robert Burton and Robin Pemantle. Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances. The Annals of Probability, pages 1329-1377 1371, 1993.
[13] Wenming Cao, Zhiyue Yan, Zhiquan Hc, and Zhihai He. A comprehensive survey on geometric deep learning. IEEE Access, 1.39929-35949 2020.
[14] Seth Chaiken and Daniel Kleitman. Matrix tree theorems. Journal of combinatorial theory, Series A, 24(3)377-381, 1978.
[15] Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. arXiv preprint arXiv: 10568, 2017.
[16] Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. arXiv preprint arXiv: 1801. 2018.
[17] Richard J Chorley and Petercoed Haggett. Models in geography. Technical report, 1967.
[18] Gerardo Chowell, James M Hyman, Stephen Eubank, and Carlos Castillo-Chavez. Scaling laws for the movement of people between locations in a large city. Physical Review E, 68(6):066102, 2003.
[19] Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. Empirical evaluation of gated recurrent neural networks on sequence modeling. arXiv preprint arXiv: /412.3555,
2014.
[20] Reuven Cohen and Shlomo Havlin. Complex networks: structure, robustness and function. Cambridge university press, 2010.
[21] Camille Couprie, Clément Farabet, Laurent Najman, and Yann LeCun. Indoor semantic segmentation using depth information. arXiv preprint arXiv:1301.3572, 2013.
[22] Hanjun Dai, Yingtao Tian, Bo Dai, Steven Skiena, and Le Song. autoencoder for molecule generation. In Proceedings of the International Conference Learning Representations, 2018
variational
[23] Tomasz Danel, Przemyslaw Spurek, Jacek Tabor, Marek Šmieja, Lukasz Struski, Agnieszka Stowik, and Lukasz Maziarka. Spatial graph convolutional networks. In International Confer- ence on Neural Information Processing, pages
Springer, 2020.
[24] Andrea De Montis, Mare Barthélemy, Alessandro Chessa, and Alessandro Vespignani. The structure of interurban traffic: a weighted network analysis. Environment and Planning B: Planning and Design, 34(5):905-9244 2007.
[25] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. arXiv preprint 1606.0:600.099 09375, 2016.
[26] Haowen Deng, Tolga Birdal, and Slobodan Ilie. Ppfnet: Global context aware local features for robust 3d point matching. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 195-205, 2018.
[27] Christopher M Dobson. Protein folding and misfolding. Nature, 426(6968):884-890 2003.
[28] Yuanqi Du, Shiyu Wang, Xiaojie Guo, Hengning Cao, Shujie Hu, Junji Jiang, Aishwarya Varala, Abhinav Angirekula, and Liang Zhao. Graphgt: Machine learning datasets for deep graph generation and transformation. 2021.
[29] César Ducruet and Laurent Beauguitte. Spatial science and network science: review and outcomes of complex relationship. Networks and Spatial Economics, 14(3):977-116, 2014.
11

---

[30] David Duvenaud, Dougal Maclaurin, Jorge Aguilera-Ipann Iparraguirre, Rafael Gómez-Bombareile Timothy Hirzel, Alán Aspuru-Guzia and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. arXiv preprint urXiv:/509.09220) 2015.
[31] Victor M Eguiluz, Dante R Chialvo, Guillermo A Cecchi, Marwan Baliki, and A Vania Apkarian. Scale-free brain functional networks. Physical review letters, 94(1):018102 2005.
[32] Paul Erdós and Alfréd Rényi. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17-60, 1960.
[33] Paul Expert, Tim S Evans, Vincent Blondel, and Renaud Lambiotte. Uncovering space- independent communities in spatial networks. Proceedings of the National Academy of Sciences, 108(19)776337665) 2011.
[34] Haoqiang Fan, Hao Su, and Leonidas Guibas. point set generation network for 3d object reconstruction from a single image. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 605-613, 2017.
[35] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: 99990022228 2019.
[36] Fabian B Fuchs, Daniel E Worrall, Volker Fischer, and Max Welling. Se trnstronsf::::::: 3d roto-trane troo-translation equivariant attention networks. arXiv preprint arXiv:2006. 10503, 2020.
[37] Linda Geerligs, Remco Renken, Emi Saliasi, Natasha M Maurits, and Monicque M Lorist. A brain-widh wide study of age-related changes functional connectivity. Cerebral cortex, 25(7))1987-
1999, 2015.
[38] 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, pages
PMLR, 2017.
[39] Rafael G6mez-Bombardee Jennifer N Wei, David Duvenaud, José Miguel Hernández-LLoato Benjamín Sánchez-Lengelingg Dennis Sheberla, Jorge Aguilera-iparraguiree, Timothy D Hirzel, Ryan Adams, and Alán Aspuru-Guzik. Automatic chemical design using data-driven continuous representation of molecules. ACS central science, 4(2):268-276, 2018.
[40] Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2, pages 729-734. IEEE, 2005.
[41] Xiaojic Guo, Yuanqi Du and Liang Zhao. Property controllable variational autoencoder via invertible mutual dependence. In International Conference on Learning Representations, 2020.
[42] Xiaojie Guo, Yuanqi Du, and Liang Zhao. Deep generative models for spatial networks. In Proceedings the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 505-515, 2021.
[43] Yulan Guo, Hanyun Wang, Qingyong Hu, Hao Liu, Li Liu, and Mohammed Bennamoun. Deep learning for 3d point clouds: survey. IEEE transactions on pattern analysis and machine intelligence, 2020.
[44] Peter Haggett and Richard J Chorley, Network analysis in geography, volume 1, Hodder Education, 1969.
[45] William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. arXiv preprint arXiv:
2017.
[46] William L Hamilton, Rex Ying, and Jure Leskovee. Representation learning on graphs: Methods 2017.
and applications. arXiv preprint
[47] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
12

---

[48] Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structue structured data. arXiv preprint (rXv::506.0016: 2015.
[49] Mark Jenkinson, Christian F Beckmann, Timothy EJ Behrens, Mark W Woolrich, and Stephen M Smith. Fsl. Neuroimage, 62(2):782-790, 2012.
[50] Benedikt Atli Jónsson, Gyda Bjornsdottir, TE Thorgeirsson, Lotta María Ellingsen, G Bragi Walters, DF Gudbjartsson, Hreinn Stefansson, Kari Stefansson, and MO Ulfarsson. Brain age prediction using deep learning uncovers associated sequence variants. Nature communications, 10(1):1-10, 2019.
[51] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint
2016.
[52] Johannes Klicpera, Janek Groß, and Stephan Günnemann. Directional message passing for molecular graphs. arXiv preprint arXiv:2003.03/23, 2020.
[53] Alex Krizhevsky, llya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. Advances in neural information processing systems, 25: 1105, 2012.
[54] Maciej Kurant and Patrick Thiran. Extraction and analysis of traffic and topologies of trans- portation networks. Physical Review E, 74(3):0361 14, 2006.
[55] Vito Latora and Massimo Marchiori. Vulnerability and protection of infrastructure networks. Physical Review E, 71(1):015103, 2005.
[56) Ron Levie, Federico Monti, Xavier Bresson, and Michael M Bronstein. Cayleynets: Graph convolutional neural networks with complex rational spectral filters. IEEE Transactions on Signal Processing, 67(1))97-109, 2018.
[57] Yangyan Li, Rui Bu, Mingchao Sun, Wei Wu, Xinhan Di, and Baoquan Chen. Pointenn: Convolution x-transformed points. Advances in neural information processing systems, 31:820-830, 2018.
[58] Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint 1rXiv:1511.05449 2015.
[59] Or Litany, Tal Remez, Emanuele Rodola, Alex Bronstein, and Michael Bronstein. Deep functional maps: Structured prediction for dense shape correspondence. In Proceedings of the IEEE international conference on computer vision, pages 5659-5667,, 2017.
[60] Ao Liu, Qiong Wu, Zhenming Liu, and Lirong Xia. Near-neighbor methods in random preference completion. In Proceedings of the AAAI Conference Artificial Intelligence, 2019.
[61] Jonathan Long, Evan Shelhamer, and Trevor Darrell. Fully convolutional networks for se- mantic segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3431-3440, 2015.
[62] Diego Marcheggiani and Ivan Titov. Encoding sentences with graph convolutional networks for semantic role labeling. arXiv preprint arXiv.1703.04822. 2017.
[63] Haggai Maron, Heli Ben-Hame Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. arXiv preprint arxiv: 2019.
[64] Haggai Maron, Meirav Galun, Noam Aigerman, Miri Trope, Nadav Dym, Ersin Yumer, Vladimir G Kim, and Yaron Lipman. Convolutional neural networks on surfaces via seamless toric covers. ACM Trans. Graph., 36(4):71-1) 2017.
[65] Jonathan Masci, Davide Boscaini, Michael Bronstein, and Pierre Vandergheynst. Geodesic con- volutional neural networks on riemannian manifolds. Proceedings of the IEEE international conference computer vision workshops, pages 37-45, 2015.
13

---

[66] Daniel Maturana and Sebastian Scherer. Voxnet: A 3d convolutional neural network for real- time object recognition. In 2015 JEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 922-928. IEEF, 2015.
[67] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4602-4609, 2019.
[68] Richard G Morris and Mare Barthelemy. Transport on coupled spatial networks. Physical review letters, (09(1)):22873, 2012.
[69] Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In International conference on machine learning, pages 2014-2023. PMLR, 2016.
[70] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- pettr-rerfrmm deep learning library. arXiv preprint arXiv:1912.01700 2019.
[71] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 652-660, 2017.
[72] Saulo DS Reis, Yanqing Hu, Andrés Babino, José S Andrade Jr, Santiago Canals, Mariano Sigman, and Hernán A Makse. Avoiding catastrophic failure in correlated networks of networks Nature Physics, 10(10):762-677, 2014
[73] Kristof T Schütt, Pieter-Jan Kindermans, Huziel E Sauceda, Stefan Chmiela, Alexandre Tkatchenko, and Klaus-Rose Robert Müller. Schnet: A continuous-filter convolutional neural network for modeling quantum interactions. arXiv preprint arXiv:1706.08566, 2017.
[74] David Shuman, Benjamin Ricaud, and Pierre Vandergheynst. Vertex-frequenn, analysis on graphs. Applied and Computational Harmonic Analysis, 40(2):260-291, 2016.
[75] Richard Socher, Brody Huval, Bharath Bath, Christopher D Manning, and Andrew Ng. Convolutional-recurs deep learning for 3d object classification. Advances in neural in- formation processing systems, 25:656-664, 2012.
[76] Olaf Sporns, Giulio Tononi, and Gerald M Edelman. Theoretical neuroanatomy: relating anatomical and functional connectivity in graphs and cortical connection matrices. Cerebral cortex, 10(2):127-141, 2000.
[77] Kaustubh Supekar, Vinod Menon, Daniel Rubin, Mark Musen, and Michael Greicius. Network analysis of intrinsic functional brain connectivity in alzheimer's 's disease. PLoS Comput Biol, 4(6):e1000100, 2008
[78] Nathaniel Thomas, Tess Smidt, Steven Kearnes, Lusann Yang, Li Li, Kai Kohlhoff, and Patrick Riley. Tensor field networks: Rotation-ann conssaaiio-equivartiii neural networks for 3d point clouds. arXiv preprint arXiv:1802.082/11 2018.
[79] Waldo R Tobler. A computer movie simulating urban growth in the detroit region. Economic geography, 46(sup1):234-22) 1970.
[80] Dimitrios Tsiotas and Serafeim Polyzos. The complexity in the study of spatial networks: an epistemological approach. Networks and Spatial Economics, 18(1):1-32, 2018.
[81] Martijn P Van Den Heuvel and Hilleke E Hulshoff Pol. Exploring the brain network: a review on resting-star fmri functional connectivity. European neumppychophammccoloyyy 20(8):519-534, 2010.
[82] David C Van Essen, Stephen M Smith, Deanna M Barch, Timothy EJ Behrens, Essa Yacoub, Kamil Ugurbil, Wu-Minn HCP Consortium, et al. The wu-minn human connectome project: an overview. Neuroimage, 80:62-79, 2013.
14

---

[83] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10903 2017
2017.
[84] Jichuan Wang and Xiaoqian Wang. Structural equation modeling: Applications using Mplus. John Wiley & Sons, 2019.
[85] Nanyang Wang, Yinda Zhang, Zhuwen Li, Yanwei Fu, Wei Liu, and Yu-Gang Jiang. Pixel2mesh: Generating 3d mesh models from single rgb images. In Proceedings of the European Conference on Computer Vision (ECCV), pages 52-67, 2018.
[86] Pengyang Wang, Yanjie Fu, Hui Xiong, and Xiaolin Li. Adversarial substructured representation learning for mobile user profiling. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 130-138, 2019.
[87] Pengyang Wang, Kunpeng Liu, Lu Jiang, Xiaolin Li, and Yanjie Fu. Incremental mobile user profiling: Reinforcement learning with spatial knowledge graph for modeling event streams. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 853-861, 2020.
[88] Zheng Wang, Ce Ju, Gao Cong, and Cheng Long. Representation learning for spatial graphs. arXiv preprini 1812::881.006660 2018.
[89] Duncan J Watts and Steven H Strogatz. Collective dynamics of "small-world networks. nature, 393(6684):440 442, 1998.
[90] Chao Wen, Yinda Zhang, Zhuwen Li, and Yanwei Fu. Pixel2mesh++:: Multi-view 3d mesh generation via deformation. In Proceedings of the IEEE/CVE International Conference on Computer Vision, pages 1042-1051, 2019.
[91] Q Wu, C Brinton, Z Zhang. M Cucuringu, Pizzoferrato, and Z Liu. Equity2vec: End-to-end deep learning framework for cross-sectional asset pricing. In 2nd ACM International Conference on Al Finance, 2021.
[92] Qiong Wu, Adam Hare, Sirui Wang, Yuwei Tu, Zhenming Liu, Christopher G Brinton, and Yanhua Li. Bats: A spectral biclustering approach to single document topic modeling and segmentation. ACM Transactions on Intelligent Systems and Technology, 2021.
[93] Qiong Wu, Wen-Ling Hsu, Tan Xu, Zhenming Liu, George Ma, Guy Jacobson, and Shuai Zhao. Speaking with actions learning customer journey behavior. In 2019 IEEE 13th International Conference on Semantic Computing (ICSC), pages 279-286, 2019.
[94] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learning. Chemical science, 9():513-533, 2018.
[95] Zhirong Wu, Shuran Song, Aditya Khosla, Fisher Yu, Linguang Zhang, Xiaoou Tang, and Jianxiong Xiao. 3d shapenets: A deep representation for volumetric shapes. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1912-1920, 2015.
[96] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 2020.
[97] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: arXiv:1810.00826 2018.
[98] Li Yi, Hao Su, Xingwen Guo, and Leonidas J Guibas. Syncspeccnn: Synchronized spectral cnn for 3d shape segmentation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2282-2290, 2017.
[99] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 974-983, 2018
15

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] [Yes], [No], or [N/A] You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section ??.
Did you include the license to the code and datasets? [No] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 4.3 for the discussion of the efficiency issue of our full SGMP model.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] have read the ethics review guidelines and ensure that our paper conforms to them.
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] We report error bars in our experimental results.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'le 're using/curating? [Yes]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
16


Reviews:
[{"review_id": "c-WTEjcXzvl", "reviewer": "Reviewer_pPBn", "summary": "The paper proposed a new graph representation learning method specifically for spatial networks. This method considered both spatial and network information with a theoretical guarantee with node permutation, rotation and translation invariance by introducing length three path. Additionally, an approach was developed to improve time and memory efficiency. Its ability of network representation has been demonstrated in multiple synthetic and real-world datasets. Overall, this paper is easy to follow and well-written.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "The method is new and easy to understand. Their main contributions lie in three aspects. First, use geometry features (i.e., distance, angle, and torsion) to represent spatial information. These good geometry features remain invariant under rotation and translation transformation. Second, based on geometry features as well coordinate representations of points, they proposed Spatial Graph Message Passing Neural Network. Third, an algorithm to speed up the training process.\n\nQuestions: 1) As said, Cartesian coordinates are not rotation- and translation-invariant. But why still remain them in Eq.4 when geometry features are used to represent spatial information and incorporated. It would be interesting to see the impacts of coordinates of points vs. geometry properties individually on the performance. 2) Essentially, SGMPNN is a path-based method rather than classic graph representation methods, where local graph structures are used in aggregation. 3) It is not very clear explained how authors decided on those three geometry features.\n\nThe tasks are not new and even questionable (e.g., why it is useful to predict clustering efficient), although they are conventional and the method was proved to perform well on these tasks. I am wondering to which practical applications the method can be applied.\n\nTheir results are sound. In Table 1, 2 and 3, the description of SGMP (st) was not given, though readers may infer st refers to Spanning Tree. Besides, SGMP (with st) and SGMP performed very differently shown in those tables. Authors may explain why one is better than the other in some cases while is beaten in other cases.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't see any potential negative societal impact", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "CYEveRWq0Vm", "reviewer": "Reviewer_wGJF", "summary": "This paper advances graph representation learning into spatial networks, which is closer to the networks in physical world that are embedded in (3D) space and impacted by geometric perspectives. This work demonstrated how existing GNN or point cloud methods are not sufficient and then propose their new geometric-driven graph convolution layers which preserves discriminative power, rotation- and translation-invariant. The authors also propose a graph sampling method which ensure graph-connectivity, sparsity, and recoverability. Experimental results on 5 real-world benchmark datasets and one synthetic dataset demonstrate the effectiveness, efficiency, and geometric-property preservation over several comparison methods.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "This paper focuses on spatial network representation learning problem. Spatial networks encompass both graph information and geometric information such as node coordinates. This paper first rigorously analyzes why spatial graph pattern representation learning requires a coupled consideration on geometric properties and graph isomorphism, and why it cannot be handled by the existing works on merely graphs or point clouds individually. Then the authors propose new spatial network convolution layers which considers higher-order graph neighborhood in order to preserve geometric shape properties. Theoretical analyses/guarantees have been provided for the properties such as rotation-invariant, translate-invariant, and discriminative power. \n\nTo handle the computational complexity issue caused by the higher-order neighborhood consideration, the authors propose an acceleration technique by sampling min-spanning trees, which are sparsest graphs that maintain graph connectivity. This way the authors claim that it can reduce the computational complexity to almost linear, even it is higher-order convolution. The authors also give theorems on the effectiveness of the above approximation. Experiments on five real-world benchmark datasets and synthetic datasets are conducted where the proposed method have, for example, outperformed the state-of-the-art methods by >=30% on synthetic datasets and >=15% on QM9 dataset. Ablation studies have demonstrated the efficiency of the proposed spanning tree sampling methods, which provide a speed-up up to 300 times with similar prediction accuracy. Rotation- and translate-invariant properties of the learned representations have also been examined and seems apparently outperformed existing work.\n\nOverall, I like this paper which seems solid in both theoretical aspect and experimental perspective. However, there are still several (minor) issues, as follows:\n\n- Need to give more explanations on why spatial information must be represented in Equation (1). Many terms in Equation (2) have no sufficient explanations. I understand in Theorem 1 the authors have proved Equation (1) can provide rotation- and translation- invariant properties. But is Equation (1) the simplest way to formalize it?\n- Some experiment results require more explanations. Despite the good performance shown in Tables 2 and 3, the authors need to provide more detailed analyses on the results. For example, in order to see the potential advantage/disadvantage, analysis on the comparisons is needed among purely-GNN-based methods, purely-point-cloud based methods, and jointly-spatial-graph-based methods.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no obvious limitation or potential negative societal impact of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "5OOMQs-N5Pv", "reviewer": "Reviewer_Jj9n", "summary": "In this paper, the authors studied the problem of representation learning on spatial graphs. To achieve the goal, the authors proposed a generic framework by aggregating message passing mechanisms and spatial information. The authors also evaluated the proposed method on both synthetic data and real-world data.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "Strong Points:\n1. The writing is clear and easy to follow.\n2. The theoretical foundation is solid.\n\n\nConcerns and Questions.\n1. In Line 188, the authors claimed that \"n=4 can ensure the spatial information is preserved\". Why?\n\n2, In Line 4, the authors claimed there exist very few works on the representation learning of spatial networks, which is not necessarily correct. In fact, there are some works studying representation learning for spatial graphs, or spatial graph embedding, which also considered spatial information while modeling topology, such as [1][2]\n[1] Molecule property prediction based on spatial graph embedding\n[2] Representation Learning for Spatial Graphs.\nHow does this work compare to the literature?\n\n3. In the experiment, the authors compared the proposed method with GCN models. As the GCN models do not consider spatial information, I doubt whether it is fair to do the comparison.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I suggest the authors introduce some potential real-world applications that the proposed method can be applied to, in a short paragraph, to show the potential social impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper discusses the problem of representation learning for geometric graphs, which are graphs in which the vertices are positions in 3d space (or some other geometry), and the edges obey some local law.  These graphs come about in areas such as biology and chemistry.  Being able to compute certain functions on such objects, using deep networks, requires a good representation in latent space.  This paper suggests a novel method for learning representations of such networks.  The reviews are all in favor of acceptance, and they seem to favorably note the importance of this problem, as well as the novelty of the methods and the experiment outcomes.  I therefore am inclined toward accepting.


Decision: Accept (Poster)