D ep W i GNN : A Depth-wise Graph Neural Network for Multi-hop Spatial Reasoning in Text (2023)

Abstract: Spatial reasoning in text plays a crucial role in various real-world applications. Existing approaches for spatial reasoning typically infer spatial relations from pure text, which overlook the gap between natural language and symbolic structures. Graph neural networks (GNNs) have showcased exceptional proficiency in inducing and aggregating symbolic structures. However, classical GNNs face challenges in handling multi-hop spatial reasoning due to the over-smoothing issue, i.e., the performance decreases substantially as the number of graph layers increases. To cope with these challenges, we propose a novel Depth-Wise Graph Neural Network (DepWiGNN). Specifically, we design a novel node memory scheme and aggregate the information over the depth dimension instead of the breadth dimension of the graph, which empowers the ability to collect long dependencies without stacking multiple layers. Experimental results on two challenging multi-hop spatial reasoning datasets show that DepWiGNN outperforms existing spatial reasoning methods. The comparisons with the other three GNNs further demonstrate its superiority in capturing long dependency in the graph.

## introduction spatial reasoning in text is crucial and indispensable in many areas, e.g., medical domain @xcite , navigations @xcite @xcite and robotics @xcite . it has been demonstrated to be a challenging problem for both modern pretrained language models (plms) @xcite and large language models (llms) like chatgpt @xcite . however, early textual spatial reasoning datasets, e.g., @xcite . recently, researchers propose several new benchmarks @xcite @xcite with an increased level of complexity, which involve more required reasoning steps, enhanced variety of spatial relation expression, and more. as shown in figure 1 , 4 steps of reasoning are required to answer the question, and spatial relation descriptions and categories are diverse. to tackle the problem of multi-hop spatial reasoning, @xcite propose a recurrent memory network based on tensor product representation (tpr) @xcite , which mimics the step-by-step reasoning by iteratively updating and removing episodes from memory. specifically, tpr encodes symbolic knowledge hidden in natural language into distributed vector space to be used for deductive reasoning. despite the effectiveness of applying tpr memory, the performance of this model is overwhelmed by modern plms @xcite . moreover, these works typically overlook the gap between natural language and symbolic relations. graph neural neural networks (gnns) have been considerably used in multi-hop reasoning @xcite @xcite . these methods often treat a single graph convolutional layer of node information propagation (node to its immediate neighbors) in gnn as one step of reasoning and expand it to multi-hop reasoning by stacking multiple layers. however, increasing the number of graph convolutional layers in deep neural structures can have a detrimental effect on model performance @xcite . this phenomenon, known as the over-smoothing problem, occurs because each layer of graph convolutions causes adjacent nodes to become more similar to each other. this paradox poses a challenge for multi-hop reasoning: although multiple layers are needed to capture multi-hop dependencies, implementing them can fail to capture these dependencies due to the over-smoothing problem. furthermore, many chain-finding problems, e.g., multihop spatial reasoning, only require specific depth path information to solve a single question and do not demand full breadth aggregation for all neighbors (figure 1 ). nevertheless, existing methods @xcite @xcite for solving this kind of problem usually lie in the propagation conducted by iterations of breadth aggregation, which brings superfluous and irrelevant information that may distract the model from the key information. in light of these challenges, we propose a novel graph-based method, named depth-wise graph neural network (depwignn), which operates over the depth instead of the breadth dimension of the graph to tackle the multi-hop spatial reasoning problem. it introduces a novel node memory implementation that only stores depth path information between nodes by applying the tpr technique. specifically, it first initializes the node memory by filling the atomic information (spatial relation) between each pair of directly connected nodes, and then collects the relation between two indirectly connected nodes via depth-wisely retrieving and aggregating all atomic spatial relations reserved in the memory of each node in the path. the collected long-dependency information is further stored in the source node memory in the path and can be retrieved freely if the target node is given. unlike typical existing gnns @xcite @xcite , depwignn does not need to be stacked to gain long relationships between two distant nodes and, hence, is immune to the over-smoothing problem. moreover, instead of aimlessly performing breadth aggregation on all immediate neighbors, it selectively prioritizes the key path information. experiments on two challenging multi-hop spatial reasoning datasets show that depwignn not only outperforms existing spatial reasoning methods, but also enhances the spatial reasoning capability of plms. the comparisons with three gnns verify that depwignn surpasses classical graph convolutional layers in capturing long dependencies by a noticeable margin without harming the performance of short dependency collection. overall, our contributions are threefold: tensor product representation (tpr) @xcite ) is a mechanism to encode symbolic knowledge into a vector space, which can be applied to various natural language reasoning tasks @xcite . for example, @xcite perform reasoning by deconstructing the language into combinatorial symbolic representations and binding them using third-order tpr, which can be further combined with rnn to improve the model capability of making sequential inference @xcite . @xcite used a paragraph-level, tpr memory-augmented way to implement complex multi-hop spatial reasoning. however, existing methods typically apply tpr to pure text, which neglects the gap between natural language and symbolic structures. graph neural networks (gnns) @xcite @xcite have been demonstrated to be effective in inducing and aggregating symbolic structures on other multi-hop question answering problems @xcite @xcite @xcite . in practice, the required number of graph layers grows with the multi-hop dependency between two distant nodes @xcite , which inevitably encounters the problem of oversmoothing @xcite . some researchers have conducted studies on relieving this problem @xcite @xcite @xcite @xcite . however, these methods are all breadth-aggregation-based, i.e., they only posed adjustments on breadth aggregation like improving the aggregation filters, scattering the aggregation target using the probabilistic tool, etc., but never jumping out it. in this work, we investigate a depth-wise aggregation approach that captures long-range dependencies across any distance without the need to increase the model depth. ## conclusion in this work, we introduce depwignn, a novel graph-based method that facilitates depth-wise propagation in graphs, enabling effective capture of long dependencies while mitigating the challenges of over-smoothing and excessive layer stacking. our approach incorporates a node memory scheme leveraging the tpr mechanism, enabling simple arithmetic operations for memory updating and retrieval, instead of relying on additional neural layers. experiments on two recently released textual multi-hop spatial reasoning datasets demonstrate the superiority of depwignn in collecting long dependencies over the other three typical gnns and its immunity to the over-smoothing problem.