Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: Strong Points:
1. The writing is clear and easy to follow.
2. The theoretical foundation is solid.


Concerns and Questions.
1. In Line 188, the authors claimed that "n=4 can ensure the spatial information is preserved". Why?

2, 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]
[1] Molecule property prediction based on spatial graph embedding
[2] Representation Learning for Spatial Graphs.
How does this work compare to the literature?

3. 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.
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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

Questions: 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.

The 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.

Their 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.
limitations_and_societal_impact: I don't see any potential negative societal impact
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.
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. 

To 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.

Overall, I like this paper which seems solid in both theoretical aspect and experimental perspective. However, there are still several (minor) issues, as follows:

- 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?
- 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.

limitations_and_societal_impact: There is no obvious limitation or potential negative societal impact of this work.
review_title: null

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)