DepWiGNN: A Depth-wise Graph Neural Network for Multi-hop Spatial Reasoning in Text
Authors: Shuaiyi Li
Yang Deng
Wai Lam
Venue: EMNLP 2023 Findings (2023)
Keywords: Spatial Reasoning
Tensor Product Representation
Graph Neural Network

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.

DepWiGNN: A Depth-wise Graph Neural Network for Multi-hop Spatial Reasoning in Text
Shuaiyi Li', Yang Deng Wai Lam'
'Te Chinese University of Hong Kong, 2 National University of Singapore 1i shwaiyiel innk cuhk. edu. hk, ydengênus. edu. sg, wlam@se cuhk. cuhk.edu... hk
Abstract
Story:
K
vertical wine
Spatial reasoning in text plays a crucial role in various real-world applications. Existing ap- proaches 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 in- ducing and aggregating symbolic structures. However, classical GNNs face challenges in handling multi-hop spatial reasoning due to over-smoothing issue, Le., the performance de- creases substantially as the number of graph layers increases. To cope with these challenges, we propose novel Depth-Wisg Wise Graph Neural Network (Dep WiGNN). Specifically, we de- sign novel node memory scheme and aggre- gate the information over the depth dimension instead of the breadth dimension the graph, which empowers the ability to collect long de- pendencies without stacking multiple layers. Experimental results on two challenging multi- hop spatial reasoning datasets show that Dep- WIGNN outperforms existing spatial reasoning methods. The comparisons with the other three GNNs further demonstrate its superiority in capturing long dependency in the graph.
2. L center of flock Is between 10 11.
3 X K.
4 ispesiiioned below and to theright of
Question
What is thlation of theagen too the agont.A?
Candidate answers:
Lover-right upper-left, below, overlap, lover-left, left, right, above uppar-ight
Answer: Above
Figure 1: An example of multihop spatial reasoning in text from the StepGame dataset (Shi et al., 2022).
bAbl (Weston et al., 2016), suffer from the issue of over-simplicity and, therefore, not qualified for revealing real textual spatial reasoning scenario. Recently, researchers propose several new bench- marks (Shi et al., 2022; Mirzaee and Kordjamshidi, 2022; Mirzaee et al., 2021) with an increased level of complexity, which involve more required reason- ing steps, enhanced variety of spatial relation ex- pression, and more. As shown in Figure 1, 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 rea- soning, Shi et al. (2022) propose recurrent mem- ory network based on Tensor Product Represen- tation (TPR) (Schlag and Sehmidhuber, 2018a), which mimics the step-by-step reasoning by itera- tively updating and removing episodes from mem- ory. Specifically, TPR encodes symbolic knowl- edge 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 (Mirzace and Kordjamshidi, 2022). 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 (Xu et al., 2021b; Chen et al., 2020b; Qiu et al., 2019).
1 Introduction
Spatial reasoning in text is crucial and indispens- able in many areas, e.g., medical domain (Datta et al., 2020; Massa et al., 2015), navigations (Zhang et al., 2021; Zhang and Kordjamshidi, 2022; Chen al., 2019) and roboties (Luo et al., 2023; Venkatesh et al., 2021). It has been demonstrated to be challenging problem for both modern pre- trained language models (PLMs) (Mirzaee et al., 2021; Deng et al., 2023a) and large language mod- els (LLMs) like ChatGPT (Bang el al., 2023). How- ever, early textual spatial reasoning datasets, e.g.,
"This work is substantially supported by a grant from the Research Grant Council the Hong Kong Special Adminis- trative Region, China (Project Code: 14200719) Corresponding author.

---

These methods often treat single graph convolu- tional 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 (Li et al., 2018). This phe- nomenon, known 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 mulli-hop dependencies, imple- menting them can fail to capture these dependen- cies due to the over-smoothing problem. Further- more, many chain-finding problems, egg., multi- hop spatial reasoning, only require specific depth path information solve a single question and do not demand full breadth aggregation for all neigh- bors (Figure 1). Nevertheless, existing methods (Palm et al., 2018; Xu et al., 2021b; Chen et al., 2020b; Deng et al., 2022) 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.
aimlessly performing breadth aggregation on all immediate neighbors, selectively prioritizes the key path information.
Experiments on two challenging multi-hop spa- tial reasoning datasets show that DepWiGNN not only outperforms existing spatial reasoning meth- ods, but also enhances the spatial reasoning capa- bility of PLMs. The comparisons with three GNNs verify that DepWiGNN surpasses classical graph convolutional layers in capturing long dependen- cies by a noticeable margin without harming the performance of short dependency collection. Overall, our contributions are threefold:
We propose a novel graph-based method, Dep- WiGNN, to perform propagation over the depth dimension of graph, which can capture long dependency without the need of stacking layers and avoid the issue of over-smoothing.
We implement a novel node memory scheme, which takes advantage of TPR mechanism, en- abling convenient memory updating and retrieval operations through simple arithmetic operations instead of neural layers.
DepWiGNN excels in multi-hop spatial reason- ing tasks, surpassing existing methods in experi- mental evaluations on two challenging datasets. Besides, comparisons with three other GNNs highlight its superior ability to capture long de- pendencies within the graph. Our code will be released via https: h/gs:///8 /gi thub. com/ /ooo/SSonLL///// DepWiGNN.
In light of these challenges, we propose 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 reason- ing problem. It introduces a novel node memory implementation that only stores depth path informa- tion between nodes by applying the TPR technique. Specifically, it first initializes the node memory by filling the atomic information (spatial relation) be- tween 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. Un- like typical existing GNNs (Morris et al., 2019; Velickovic et al.. 2017: Hamilton al., 2017: Kipf and Welling, 2017), DepWiGNN does not need to be stacked gain long relationships between two distant nodes and, hence, is immune to the over-smoothing problem. Moreover, instead of
2 Related works
Spatial Reasoning In Text has experienced a thriving development in recent years, supported by several benchmark datasets. Weston et al. (2016) proposes the bAbl project, which contains 20 QA tasks, including one focusing on textual spatial rea- soning. However, some issues exist in bAbl, such as data leakage. overly short reasoning steps, and monotony of spatial relation categories and descrip- tions, which makes it fails to reflect the intricacy of spatial reasoning in natural language (Shi et al., 2022). Targeting these shortages, StepGame (Shi et al., 2022) expands the spatial relation types, the diversity of relation descriptions, and the required reasoning steps. Besides, SPARTQA (Mirzaee et al., 2021) augments the number of question types from one to four: find relation (FR), find blocks (FB), choose objects (CO), and yes/no (YN), while

---

SPARTUN (Mirzaee and Kordjamshidi, 2022) only has two question types (FR, YN) built with broader coverage of spatial relation types.
and Kordjamshidi, 2022), define the problem as follows: Given story description consisting of multiple sentences, the system aims to answer a question Q based on the story S by selecting a correct answer from the fixed set of given candidate answers regarding the spatial relations.
Tensor Product Representation (TPR) (Schlag and Schmidhuber, 2018a) is mechanism to en- code symbolic knowledge into a vector space. which can be applied to various natural language reasoning tasks (Huang et al., 2018; Chen al., 2020a). For example, Schlag and Schmidhuber (2018a) perform reasoning by deconstructing the language into combinatorial symbolic representa- tions and binding them using Third-order TPR, which can be further combined with RNN to im- prove the model capability of making sequential inference (Schlag al., 2021). Shi et al. (2022) used a paragraph-level. TPR eeemory-augmente way to implement complex multi-hop spatial rea- soning. However, existing methods typically apply TPR to pure text, which neglects the gap between natural language and symbolic structures.
3.2 The DepWiNet
As presented in Figure 2, the overall framework named DepWiNet consists of three modules: the entity representation extraction module, the Dep- WiGNN reasoning module, and the prediction mod- ule. The entity representation extraction module provides comprehensive entity embedding that is used in the reasoning module. A graph with recog- nized entities nodes is constructed after obtain- ing entity representations, which later will be fed into DepWiGNN. The DepWiGNN reasons over the constructed graph and updates the node embed- ding correspondingly. The final prediction module adds the entity embedding from DepWiGNN to the embeddings from the first extraction module and applies a single step of attention (Vaswani et al., 2017) generate the final result.
Graph Neural Networks (GNNs) (Morris et al., 2019; Velickovic et al., 2017: Hamilton et al., 2017: Kipf and Welling, 7) have been demonstrated to be effective in inducing and aggregating sym- bolic structures on other multi-hop question an- swering problems (Cao et al., 2019; Fang et al.. 2020; Huang and Yang, 2021; Heo al., 2022; Xu et al., 2021a; Deng et al., 2023b). In prac- tice, the required number of graph layers grows with the multi-hop dependency between two dis- tant nodes (Wang et al., 2021; Hong et al., 2022), which inevitably encounters the problem of over- smoothing (Li et al., 2018). Some researchers have conducted studies on relieving this problem (Wu et ul., 2023; Min et al., 2020; Huang and Li, 2023; Yang et al., 2023; Liu et al., 2023; Koishekenov, 2023; Song al., 2023). However, these methods are all breadth- mondtt-agggrgatioo--beee posed adjustments on breadth aggregation like im- proving the aggregation filters, scattering the aggre- gation target using the probabilistic tool, etc.. but never jumping out it. In this work, we investigate depth-wise aggregation approach that captures long-range dependencies across any distance with- out the need increase the model depth.
Entity Representation Extraction Module We leverage PL.Ss to extract entity representations! The model takes the concatenation of the story S and the question Q as the input and output embed- dings of each token. The output embeddings are further projected using single linear layer.
$ PLM(S.
(1)
S. SW.? Q., T
(2)
where PLM(.) denotes the PLM-based encoder, e.g., BERT (Devlin et al., 2019). S, E Rrexd, Qa. Rd denotes the list of projected tokens of size d, the story and question, and W. E Rdd xda the shared projection matrix. The entity representation is just the mean pooling of all token embeddings belonging to that entity.
i.e., they only
Graph Construction The entities are first rec- ognized from the input by employing rule-based entity recognition. Specifically, StepGame (Shi et al., 2022), the entities are represented by a single capitalized letter, so we only need to lo- cate all single capitalized letters. For SPARTUN
3 Method
3.1 Problem Definition
Following previous studies on spatial reasoning in text (Mirzaee et al., 2021; Shi et al., 2022; Mirzaee
FFitity in this paper refers to the spatial roles defined in(Kordjamshidi et al., 2010).

---

DepWiGNN
Prediction Module
Sycus)
PLM
Pcci
V.
Mean [5: Q] Wa),
Wa Rd
The WepWiNet framework. The entity representations are first extracted from the entity representation extraction module (left), and then homogeneous graph is constructed based the entity embeddings and fed into the DepWiNet reasoning module. The DepWiNet depth-wisely aggregates information for all indirectly connected node pairs, and stores in node memories. The updated node embeddings are then passed to the prediction module.
Figure 2:
and ReSQ, we use nltk RegexpParser' with self- designed grammars to recognize entities. Entities and their embeddings graph, and an edge between entities exists if and only if the entities co-occur in the same sentence. We also add an edge feature for each edge.
where V E R V xd, and E E Elx,, are the nodes and edges of the graph. It comprises three components: node memory initialization long de- pendency collection, and spatial relation retrieval. Details of these three components will be discussed in Section 3.3.
treated nodes of the
Prediction Module The node embedding up- dated in DepWiGNN is correspondingly added to entity embedding extracted from PLM.
ifi=j,
Eij
(3)
C(CLS) ortherwise.
If two entities are the same (self-loop), the edge feature is just
Z, + V Vida(i)
if i-th token E V
2,
(5)
tensor with size dui other- wise, it the sequence's last layer hidden state of the [CLS] token. The motivation behind treating [CLS] token as an edge feature is that it can help the model better understand the atomic relation (k=1) between two nodes (entities) so as to facili- tate later depth aggregation. A straightforward jus- tification can be found in Table 1, where all three PLMs achieve very high accuracy at k=1 cases by using the [CLS] token, which demonstrates that the [CLS] token favors the understanding of the atomic relation.
Z,
ortherwise.
where Z; |S; Q] is the ith token embedding from PLM and V. denotes the updated entity represen- tation set. idx(i) is the index of i-th token in the graph nodes.
Then, the sequence of token embeddings in the question and story extracted separately to per- form attention mechanism (Vaswani et al., 2017) with the query be the sequence of question kens embeddings 2q. key and value to be the se- quence of story token embeddings 2g.
WiGNN Module The DepWiGNN module (middle part in Figure 2) is responsible for multi- hop reasoning and can collect arbitrarily distant dependency without layer stacking.
202 2T R = Σ (sof hoosmar(
rQ
)2g) dd,
(6)
1=0
C = FFN (layernrn
(7)
= De
(4)
where layernm means layer normalization and C the final logits. The result embeddings are summed over the first dimension, layernormed, and
and

---

1. Node initialization
2. Long dependency collection 3. Spatial relation retrieval
acquire spatial orientation filler fú I by using feedforward network, the input to FFN concate- nation in the form [Vi, Eaj. Vz]- V; represents i-th node embedding.
Moka
Mots
poatle F. P.
fij - FFN((, Egg, VGD) Mc - E Evjcnvay Sy @ V3
(8)
Fa PVN Figes 0.V)) M4 m
FAx M,P, PFN
2 1a 8
M, OV,
(9)
Figure 3: The illustration of DepWIGNN.
The filler is bound together with the corresponding destination node Vj using the outer product. The initial node memory M, for node V; is just the summation of all outer product results of the fillers and corresponding neighbors (left part in Figure 3).
fed into 3-layer feedforward neural network to acquire the final result. The overall framework is trained in an end-to-end manner to minimize the cross-entropy loss between the predicted candidate answer probabilities and the ground-truth answer.
Long Dependency Collection We discuss how the model collects long dependencies in this sec- tion. Since the atomic relations are bound by corre- sponding destinations and have already been con- tained in the node memories, we can easily unbind all the atomic relation fillers in path using the corresponding atomic destination node embedding (middle part in Figure 3). For each pair of indi- rectly connected nodes, we first find the shortest path between them using treadth-first search (BFS). Then, all the existing atomic relation fillers along the path are unbound using the embedding of each node in the path (lqq.1).
3.3 Depth-wise Graph Neural Network
As illustrated in Figure 3, we introduce the pro- posed graph neural network, called DepWiGNNY Le.. the operation V = DepWiGNNN(; V, F)).
Unlike existing GNNs (c.g. (Morris et al., 2019;
Velickovic et al., 2017; Hamilton et al., 2017)).
which counts the one-dimension node embedding itself as its memory to achieve the function of in- formation reservation, updating, and retrieval, De- PWiGNN employs a novel two-dimension node memory implementation approach that takes the advantage of TPR mechanism allowing the updat- ing and retrieval operations of the memory to be conveniently realized by simple arithmetic oper- ations like plus, minus and outer product. This essentially determines that the information propa- gation between any pair of nodes with any distance in the graph can be accomplished without the de- mand to iteratively apply neural layers.
fp(inn = Mp. VT Pi+1
(10)
F Aggregator(F)
(11)
Spop.. = layernm(FFN FF)
(12)
Mp Mpo + Spop. & VT Pa
(13)
where p; denotes the i-th element in the path and F [ 1p.- is the retrived filler set along the path. The collected relation fillers are aggregated using a selected depth aggregator like LSTM (Hochreiter and Schmidhuber, 1997), etc, and passed to a feedforward neural network to rea- son the relation filler between the source and desti- nation node in the path (Eq. The result spatial filler then bound with the target node embedding and added to the source node memory (Eq.13). this way, each node memory will finally contain the spatial orientation information to every other connected node in the graph.
Node Memory Initialization At this stage, the node memories of all nodes are initialized with the relations their immediate neighbors. In the multi- hop spatial reasoning cases, the relations will be the atomic spatial orientation relations (which only needs one hop) of the destination node relative to the source node. For example, "X is to the left of K and is on the same horizontal plane." We follow the TPR mechanism (Smolensky, 1990), which uses outer product operation to bind roles and fillers4. In this work, the calculated spatial vectors are con- sidered to be the fillers. They will be bound with corresponding node embeddings and stored in the two-dimensional node memory. Explicitly, we first
Spatial Relation Retrieval After the collection process is completed, every node memory contains spatial relation information to all other connected nodes in the graph. Therefore, we can conveniently retrieve the spatial information from a source node
'The preliminary of TPR is presented in Appendix A.

---

a target node by unbinding the spatial filler from the source node memory (right part in Figure 3) using a self-determined key. The key can be the target node embedding itself if the target node can be easily recognized from the question, or some computationally extracted representation from the sequence of question token embeddings if the target node is hard to discern. We use the key to unbind the spatial relation from all nodes' memory and pass the concatenation of it with source and target node embeddings to a multilayer pereeptron to get the updated node embeddings.
which used BERT with or without further synthetic
supervision as baselines.
Implementation Details For all experiments, we use the base version of corresponding PLMs, which has 768 embedding dimensions. The model was trained in an end-to-end manner using Adam op- timizer (Kingma and Ba, 2015). The training was stopped if, up to 3 epochs, there is no improvement greater than le-3 on the cross entsopy loss for the validation set. We also applied Pytorch train- ing scheduler that reduces the learning rate with a factor of 0. if the improvement of cross- loss on the validation set is lower than 1e-3 for 2 epochs. In terms of the determination of the key in the Spatial Relation Retrieval part, we used the target node embedding for StepGame since it can be easily recognized, and we employed a single linear layer to extract the key representation from the sum-aggregated question token embeddings for ReSQ. In the StepGame experiment, we fine-tune the model on the training set and test on the test set. For ReSQ, we follow the procedure in (Mirzaee and Kordjamshidi, 2022) to test the model on ReSQ with or without further supervision from SPAR- TUN (Mirzaee and Kordjamshidi, 2022). Unless specified, all the experiments use LSTM (Hochre- iter and Schmidhuber, 1997) as depth aggregator by default. The detailed hyperparameter settings are given in the Appendix B.
fekevl M; V.Vikea) [key) 1/- = F FFN (fikkee)))( Mkeyl) (15)
(14)
The updated node embeddings are then passed to the prediction module to get the final result.
4 Experiments
4.1 Experimental Setups
Datasets & Evaluation Metrics We investigated our model on StepGame (Shi et al.. 2022) and ReSQ (Mirzace and Kordjamshidi, 2022) datasets, which were recently published for multi-hop spa- tial reasoning. StepGame is a synthetic textual QA dataset that has number of relations (k)) rang- ing from to 10. In particular, we follow the ex- perimental procedure in the original paper (Shi et al., 2022), which utilized the Version of the dataset containing 10,000/1,000 training/validation clean samples for each l value from 1 to and 10,000 noisy test examples for k value from 1 to 10. The test set contains three kinds of distraction noise: disconnected, irrelevant, and supporting. ReSQ is crowdsourcing benchmark that includes only Yes/No questions with 1008, 333, and 610 ex- amples for training, validating, and testing respec- tively. Since it is human- buman-generated. it can reflect the natural complexity of real-world spatial description. Following the setup in (Shi et al., 2022; Mirzace and Kordjamshidi, 2022), we report the accuracy on corresponding test sets for all experiments.
4.2 Overall Performance
Table and report the experiment results on StepGame and ReSQ respectively. As shown in Table I, PLMs overwhelmingly outperform all the traditional reasoning models and the proposed De- pWiNet overtakes the PLMs by a large margin, especially for the cases with greater k where the multi-hop reasoning capability plays a more im- portant role. This aligns with the characteristics of our model architecture that the aggregation fo- cuses on the depth dimension, which effectively avoids the problem of over-smoothing and the mix- ture of redundant information from the breadth aggregation. Despite the model being only trained on clean distraction-noise-aleee from to 5, it achieves impressive performance on the iistraatioonnniis--reeee test data with k value from 6 10, demonstrating the more advanced generalization capability of our model. Moreover, our method also entails an improvement for the examples with lower & values for BERT and AL-
Baselines For StepGame, we select all traditional reasoning models used in the original paper (Shi al., 2022) and three PLMs, i.e., BERT (De- vlin et al., 2019), RoBERTa (Liu et al., 2019), and ALBERT (Lan al., 2020) as our baselines. For ReSQ, we also follow the experiment setting described in (Mirzaee and Kordjamshidi, 2022),
samples with k

---

Method
k=
k=
k=3
k=44
k=
k=6
k=
k=8
k=9
k=10
Mean(k=1-S) Mean(k=6- 6-1))
(Santoro et al., 2017)
17.08
15.08
12.84
11.52
11:12
11.53
11.21
11.13
11.34
15.83
11.27
RRN (Palm et al., 2018)
24.05
19.98
16.03
13:22
12.31
1162
11.40
11.3
11.22
11.69
17.12
11.56
UT (Dehghani al., 2019)
45.11
28.36
17.41
14.07
13445
12.73
12.11
11.40
11.41
11.74
23.68
11.88
STM (Le al., 2020)
53.42
35.96
23.03 18.45
15.14
13.80
12.63
11.54
11:30
11.77
29.20
12.21
TPR RNN (Schlag and Schmidhuher, 2018h)
70.29 46.03
36. 14 26.82 24.77
22.25
19.88
15.45
13.01
12.65
40.81
16.65
TP-MANN (Shi et al., 2022)
85.77 60.31 50. 18 37.45 31.25
28.53
26.45
23.67
22.52
21.46
52,99
24.53
BERT (Mirzace and Kordjamshidi, 2022)
98.53
93:40 91.19 66.98 54.57
48.59
42.81
37.98
34.16
33.62
80.93
39.43
RoBERIs' (Mirzace and Kordjamshidi, 2022)
98.68
97.05 95.66 79.59 74.89
70.67
66.01
61.42
57.20
54.53
89.17
61.93
ALBBRRT (Minzaee and Kordjamshidi, 2022)
97.56
96.08
90.01
77.24
71.57 64.47
60.02
56.18
93.11
DepWiNet (BERT)
98.44
96.57
94.75
81.41 70.68 62.80 57.46 49.14 45.56
44.01
88.37
(8.79
DepWiNet (RoBERTa)
98.70
96.69 95.54
79.50 74.94
70.37 66.22
61.89
58.01 56.89
89 09.07
62.68
DepWiNet (ALBERT)
98.59
97.13 95.87 91.96 87.50 82.62 77.80 71.40 67.55 64.98
94.21
1.25
72.87
120.616
Table I: Experimental results StepGame. denotes the implementation of the same model BERT (Mirzaee and Kordjamshidi, 2022) with RoBERTa and ALBERT. The other results are reported in (Shi et al., 2022).
Method
SynSup
ReSQ
Impact of Dep WiNet components The model performance experiences drastic decrease, par- ticularly for the mean score of l between 6 and 10, after the Long Dependency Collection (LDC) has been removed, verifying that this component serves a crucial role the model. Note that the mean score for k(6-10) even drops below the AL- BERT baseline (Table 1). This is reasonable as the LDC is directly responsible for collecting long de- pendencies. We further defunctionalized the Node Memory Initialization (NMI) and then Spatial Re- lation Retrieval (SRR) by setting the initial fillers (Fq.8) and key representation (Eq.14) vector separately. Compared with the case where only LDC was removed, both of them lead to a further decrease in small and large & values.
Majority Baseline
50.21
BERT
57.37
BERT
SPARTQA-AUTO
55.08
BERT
StepGame
60.14
BERT
SPARTUN-S
58.03
BERT
SPARTUN
63.60
DepWiNet (BERT)
63.30
DepWiNet (BERT) SPARTUN
65.54
Table Experimental results on ReSQ, under the trans- fer learning setting (Mirzaee and Kordjamshidi, 2022).
random
BERT and an ignorable decrease for RoBERTa, which attests to the innocuity of our model to the few-hop reasoning tasks.
Experimental results in Table show that De- pWiNet reaches new SOTA result on ReSQ for both cases where extra supervision from SPAR- TUN is present and absent. Excitingly, the perfor- mance of our model without extra supervision even overwhelms the performance of the BERT with ex- tra supervision from SPARTQA AARTQA-AUTO (Mirzace et al., 2021), StepGame, and SPARTUN-S and ap- proaches closely to the SPARTUN supervision case. All these phenomenons signify that our model has the potential to better tackle the natural intricacy of real-world spatial expressions.
Impact of Different Aggregators The results show that the mean and max pooling depth aggre- gators fail understand the spatial rule as achieved by LSTM. This may be caused by the relatively less expressiveness and generalization caliber of mean and max pooling operation.
4.4 Comparisons with Different GNNs
To certify our model's capacity of collecting long dependencies as well as its immunity to the over- smoothing problem, we contrast it with four graph neural networks, namely, GCN (Kipf and Welling, 2017), GraphConv (Morris et al., 2019), GAT (Velickovic et al., 2017) and GCNII (Chen et al., 2020c). We consider the cases with the number of layers varying from to 5 and select the best perfor- mance to compare. The plot of the accuracy metric is reported in Figure and the corresponding best
4.3
Ablation study
We conduct ablation studies on the impact of the three components of DepWIGNN and different depth aggregators, as presented in Table 3.

---

Method
k=1
k=2
k=3
k=4
k=5
k=6
k=7
k=8
k=9
k=10
Mean(k=1-S) Mean(k=6- 10)
(ALBETY( (ALBERT)
98,59
97.13
95.87
91.96
87.50
82.62
77.80
71.40
67.55
64.98
94.21
72.87
-woo LDC
98.58
97.72
96.42
82.46
78.53
74.52
70.45
62.84
59.06
56.57
90.74- 3.7%
64.69 11.29
-wo NMI & LDC
98,48
96.88
94.83
79.14
75.46
70.51
67.19
61,88
57.65
55.02
88.96-5.6%
62.45 14.3%
w/o SRR & LDC
98.64
97.52
95.91
80.72
76.85
72.56
67.93
61.29
57.97
54.17
89,93 4.35%
62.78 13.8%
w/ DepWiGNNN.co
98.52
96.46
93.69
81.10
77.90
73:47
70.78
65,54
62.42
59.82
89.53 5.0%
66,41
w/ DepWiGNN maspooting
98.65
95.83
93.90
80.81
77.20
72.07
68.76
62.79
59.63
57.14
89.28
5..2%
64.08 12.1%
Table 3: Ablation study. NMI, LDC, and SRR denotes the three stages in DepWIGNN, i.e, Node Memory Initialization, Long Dependency Collection, and Spatial Relation Retrieval, respectively.
Method
k=1
k=2
3=
k=4
k=5
k=6
k=
k=8
k=9
k=10
Mcan(k=1-5) Mcaník=6-10)
ALBERT
98.56
97.56
96.08
90.01
83.33
77.24
71.57
64.47
60.02
56.18
93.11
65,90
w/ GCN, (Kipf and Welling, 2017)
98.62
97.72
96.49
82.01
76.70
71.60
67.34
60:49
56.11
52.65
90.31
a.01%
61.64
w/ GruphConvy, (Moris al., 2019)
98.66
97.73
96.48
82.37
78.57
74.47
69.91
63.04
60.01
56.58
90. 20.76_2.52%
64 64.80_1.677
w/ GAT; (Velickovic ul., 2017)
98.67
97.34
95.59
81.47
78.39
73.79
70.17
63.52
60.64
57.33
90.29
a.00rs
65.09 1.20%
w/ GCNIL (Chen al.. 2020c)
98.56
97.61
96.36
83.31
79.22
74.88
70.64
63,64
60.59
56.99
91.01
65. 65.35 00.0%
DepWiGNN
98.59
97.13
95.87
87.50
82.62
77.80
71.40
67.55
64.98
94.21
11188%
72.87, 10..88
Table 4: Comparisons with different GNNs. The subscripts represent the number of GNN layers. We select the best
mcan performance among layer number 1 5.
(a) Disconnected
Irrelevant
(c) Supporting
90
80
Accuracy(9))
70
E
M
60
OCN
Question:
What is relation the agent agant
50
Noise nodes
Answer: lower-right
Question
DeptWiNet answer: lower-right
Figure 5: Cases with distracting noisy from StepGame.
Number of layers
Figure 4: Impact of the layer number in different GNNs on StepGame. The solid and dashed lines denote the mean score of (k=1-5) and (k=6-100 10) respectively.
In both small and large ls cases, our model out- performs the best performance of all four GNNs (including GCNII, which is specifically designed for over-smoothing issues) by a large margin (Table 4), which serves as evidence of the superiority of our model in long dependency collection.
cases are in Table 4. It is worth noting that almost all the bascline GNNs cause a reduction in the orig- inal PLM performance (Table 4). The reason for this may partially come from the breadth aggre- gation, which aggregates the neighbors round and round and leads to indistinguishability among en- tity embeddings such that the PLM reasoning pro- cess has been disturbed. The majority of baseline GNNs suffer from apparent performance drop when increasing the number of layers (Figure 4), while our model consistently performs better and is not affected by the number of layers all since it does not use breadth aggregation. Therefore, our model has immunity to over smoothngg problems.
4.5 Case study
In this section, we present case studies to intuitively show how DepWiGNN mitigates the three kinds of distracting noise introduced in StepGame, namely, disconnected, irrelevant, and supporting.
The disconnected noise is the set of entities and relations that forms a new independent chain in the graph (Figure 5(a)). The node memories con- structed in Dep contain spatial informa- tion about the nodes if and only if that node stays in the same connected component; otherwise, it

---

has no information about the node as there is no path between them. Hence, in this case, for the questioned source node P. its memory has no information for the disconnected noise T and D.
node memory. This poses direct increase in mem- ory requirement. The system has assign extra space to store a matrix with shape Rd xdy, for each node in the graph, which makes the method less scalable. However, it is a worthwhile trade-off because the two-dimensional node memory can po- tentially store d,, - number of spatial fillers bound with node embeddings while keeping the size fixed, and it does not suffer from information overload- ing as faced by the one-dimension memory since the spatial fillers can be straightforwardly retrieved from the memory.
The irrelevant noise branches the correct reason- ing chain out with new entities and relations but results in no alternative reasoning path (Figure 5(b)). Hence the irrelevant noise entities will not be included in the reasoning path between the source and destination, which means that it will not affect the destination spatial filler stored in the source node memory. In this case, when the key representation (embedding of entity E) is used to unbind the spatial filler from node mem- ory of the source node P. obtains the filler fxQ: fQæl))
Another issue is the time complexity of finding the shortest path between every pair of nodes. For all experiments in this paper, since the edges do not have weights, the complexity is O(()+))nn), where and e are the numbers of nodes and edges, respectively. However, things will get worse if the edges in the graph are weighted. We believe this a potential future research direction for the improvement of the algorithm.
JPE = FFN (Aggregator which intact to the irrelevant entity and rela- tion fay or faz.
The supporting noise adds new entities and rela- tions to the original reasoning chain that provides an alternative reasoning path (Figure 5(c)). De- pWiGNN is naturally exempted from this noise for two reasons: first, it finds the shortest path between two entities, therefore, will not include I and M in the path; Second, even if the longer path is considered, the depth aggregator should reach the same result as the shorted one since the source and destination are the same.
References
Yejin Bang. Samuel Cahyawijaya, Nayeon Lee, Wen- liang Dai, Dan Su, Bryan Wilie, Holy Lovenia. Ziwei Ji, Ticzheng Yu, Willy Chung, Quyet V. Do. Yan Xu, and Pascale Fung. 2023. A multitask. multilingual, multimodal evaluation of chatgpt on reasoning, hal- lucination, and interactivity. CoRR, abs/2302.04025.
Yu Cao, Meng Fang, and Dacheng Tao. 2019. BAG: bi-directional attention entity graph convolutional network for multi-hop reasoning question answering. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computa- tional Linguistics: Human Language Technologies, NAACL-HLT 2019, pages 357-362.
5 Conclusion
In this work, we introduce DepWiGNN, novel graph-based method that facilitates depth-wist wise propagation in graphs, enabling effective capture of long dependencies while mitigating the challenges of werrsmoothing and excessive layer stacking. Our approach incorporates a node memory scheme leveraging the TPR mechanism, enabling simple arithmetic operations for memory updating and re- trieval, instead of relying on additional neural lay- ers. 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-smoo problem.
Howard Chen, Alane Suhr, Dipendra Misra, Noah Snavely. and Yoav Artzi. 2019, TOUCHDOWN: natural language navigation and spatial reasoning in visual street environments. In IEEE Conference Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019, pages 12547. Computer Vision Foundation/ / IEEE.
Kezhen Chen, Qiuyuan Huang, Hamid Palangi, Paul Smolensky, Kenneth D. Forbus, and Jianfeng Gao. 2020a. Mapping natural- language problems to formal-language solutions using structured neural representations. In Proceedings of the 37th Inter- national Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 1566 (175,157,,11 PMLR.
Limitation
Unlike the classical GNNs, which use one- dimensional embedding as the node memory, our method applies a two-dimensional matrix-shaped
Kunlong Chen, Weidi Xu, Xingyi Cheng, Zou Xi- aochuan, Yuyu Zhang, Le Song, Taifeng Wang, Yuan

---

Qi. and Wei Chu. 2020b. Question directed graph attention network for numerical reasoning over text. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020, pages 6759- 6768. Association for Computational Linguisties.
William Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In Advances in Neural Information Process- ing Systems 30: Annual Conference on Neural In- formation Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 1024-1034.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. 2020c. Simple and deep graph con- volutional networks. In Proceedings of the 37th In- ternational Conference 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 1725-1735. PMLR.
Yu-Jung Heo, Eun-Sol Kim, Woo Suk Choi, and Byoung-Tat, -aa Zhang. 2022. Hypergraph trans- former: Weakly-supervised multi-hop reasoning for knowledge- based visual question answering. In Pro- ceedings of the 60th Annual Meeting of the Associa- rion for Computational Linguistics (Volume I: Long Papers), ACL 2022, pages 373-390.
Machine Learning, ICML
Surabhi Datta, Yugi Si, Laritza Rodriguez, Sonya E. Shooshan, Dina Demner- Demner-Fushman, and Kirk Roberts. 2020. Understanding spatial language in radiology: Representation framework, annotation, and spatial relation extraction from chest x-ray reports using deep learning. J. Biomed. Informatics, 108:103473.
Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural Comput., 173: 1780.
Giwon Hong. Jeonghwan Kim, Junmo Kang, and Sung- Hyon Myaeng. 2022. Graph-induced transformers for efficient multi-hop question answering. In Pro- ceedings of the 2022 Conference on Empirical Meth- ods in Natural Language Processing, EMNLP 2022, pages 10288-10294
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. 2019. Univer- sal transformers. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans. LA, USA, May 6-9, 2019. OpenReview.net.
Qiuyuan Huang, Paul Smolensky, Xiaodong He, Li Deng, and Dapeng Oliver Wu. 2018. Tensor prod- uct generation networks for deep NLP modeling. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computa- tional Linguistics: Human Language Technologies, NAACL-HLT 2018, New Orleans, Louisiana, USA, June 1-6, 2018, Volume I (Long Papers), pages 1263- 1273, Association for Computational Linguisties.
Yang Deng. Shuaiyi Li, and Wai Lam, 2023a. Learning ask clarification questions with spatial reasoning. In Proceedings of the 46th International ACM SIGIR Conference Research and Development in Infor- mation Retrieval, SIGIR 2023, pages 2113-2117.
Yang Deng. Yuexiang Xie, Yaliang Li, Min Yang. Wai Lam, and Ying Shen. 2022. Contextualized knowledge-aware attentive neural network: Enhane- ing answer selection with knowledge. ACM Trans. Inf. Syst. 1-:33311-2
Rui Huang and Ping Li. 2023. Hub-hub connections matter: Improving edge dropout to relieve over- smoothing in graph neural networks. Knowl. Based Syst, 270: I 10556.
Yang Deng, Wemxuan Zhang, Weiwen Xu, Ying Shen, and Wai Lam. 2023b. Nonfactoid question answer- ing as query-focused summarization with graph- enhanced multihop inference. IEEE Transactions on Neural Networks and Learning Systems.
Yongjie Huang and Meng Yang. 2021. Breadth first reasoning graph for multi-hop question answering. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computa- tional Linguistics: Human Language Technologies, NAACL-HLT 2021, pages 58 10-5821..
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: pre-training of deep bidirectional transformers for language under- standing. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Tech- nologies, NAACL-HITT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume 1 (Long and Short Papers), pages 4171-4186 Association for Computational Linguistics.
Diederik P. Kingma and Jimmy Ba. 2015. Adam: A method for stochastic optimization. In 3rd Inter- national Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings.
Thomas N. Kipf and Max Welling. 2017. Semi- supervised classification with graph convolutional networks. In Sth International Conference on Learn- ing Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net.
Yuwei Fang, Siqi Sun, Zhe Gan, Rohit Pillai, Shuo- hang Wang, and Jingjing Liu. 2020. Hierarchical graph network for multi-hop question answering. In Proceedings of the 2020 Conference Empirical Methods in Natural Language Processing. EMNLP 2020, pages 8823-8838.
Yeskendir Koishekenov. 2023.
Reducing over-
smoothing graph neural networks using relational embeddings. CoRR, abs/2301.029

---

Parisa Kordjamshidi, Martijn van Otterlo, and Marie- Francine Moens. 2010. Spatial role labeling: Task definition and annotation scheme. In Proceedings of the International Conference on Language Resources and Evaluation, LREC 2010, 17-23 May 2010, Val- letta, Malta. European Language Resources Associa- tion.
Roshanak Mirzace, Hossein Rajaby Faghihi. Qiang Ning, and Parisa Kordjamshidi. 2021. SPARTQA: A textual question answering benchmark for spatial reasoning. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguisticx; Human Language Technologies, NAACI-IILLT 2021, Online, June 6-11, 2021. pages 4582-4598 Association for Computa- tional Linguisties.
Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. 2020. ALBERT: A lite BERT for self-supervised learning of language representations. In 8th Inter- national Conference on Learning Representations. ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net.
Roshanak Mirzaee and Parisa Kordjamshidi. 2022. Transfer learning with synthetic corpora for spatial role labeling and reasoning. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, EMNLP 2022, Abu Dhabi, United Arab Emirates, December 7-11, 2022, pages 6148 6165. Association for Computational Linguis- tics.
Hung Le. Truyen Tran, and Svetha Venkatesh. 2020. Self-attentive associative memory. In Proceedings of the 37th International Conference on Machine Learn- ing, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 5682-5691, PMI.R.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rat- tan, and Martin Grohe 2019. Weisfeiler and leman go neural: Higher-order graph neural networks. In The Thirty-Third AAAI Conference on Artificial Intel- ligence, AAAI 2019, The Thirty-First Innovative Ap- plications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Hon- olulu, Hawaii, USA, January 27 - Februury 1, 2019. pages 4602-46004 AAAI Press.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. 2018. Deeper insights into graph convolutional networks for superviuee learning. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelli- gence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18). and the 8th AAAI Symposium on Educational Advances in Artificial In- relligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pages 3538 3545. AAAI Press.
Rasmus Berg Palm, UIrich Paquet, and Ole Winther. 2018. Recurrent relational networks. In Advances in Neural Information Processing Systems 31: An- nual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 3372-3333 -382..
Yang Liu, Chuan Zhou, Shirui Pan, Jia Wu, Zhao Li, Hongyang Chen, and Peng Zhang. 2023. Curv- drop: ricci curvature based approach to prevent graph neural networks from over-smoothing and over- squashing. In Proceedings of the ACM Web Confer- ence 2023, WWW 2023, Austin, TX, USA, 30 April 2023- 4 May 2023, pages 221-230. ACM.
Lin Qiu, Yunxuan Xiao, Yanru Qu, Hao Zhou, Lei Li, Weinan Zhang, and Yong Yu. 2019. Dynamically fused graph network for multi hop reasoning. In Pro- ceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019, Florence, Italy, July 28- August 2, 2019, Volume 1: Long Pa- pers, pages 6140-6150. 50. Association for Computa- tional Linguistics.
Yinhan Liu, Myle Out, Naman Goyal, Jingfei Du, Man- dar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019. Roberta: A robustly optimized BERT pretraining approach. CoRR, abs/1907. 11692.
Qian Luo, Yunfei Li, and Yi Wu. 2023. Grounding robotic ma-
object relations in nipulation with semantic-spatial reasoning. CoRR, 10s/2303.17919.
Adam Santoro, David Raposo, David G. T. Barrett, Mateusz Malinowski, Razvan Pascanu, Peter W. Battaglia, and Tim Lillicrap. 2017. A simple neu- ral network module for relational reasoning. In Ad- vances in Neural Information Processing Syxtems 30: Annual Conference on Neural Information Process- ing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 4967-4976.
Wouter Massa, Parisa Kordjamshidi, Thomas Provoost, and
Moens. 2015. Machine reading of biological texts bacteria-biotope extraction. In KIOINFORMATIC 2015 Proceedings of the In- ternational Conference on Bioinformatics Models, Methods and Algorithms, Lisbon, Portugal, 12-15 January, 2015, pages 55-64. SciTePress.
Imanol Schlag, Tsendsuren Munkhdalai, and Jürgen Schmidhuber. 2021. Learning associative inference using fast weight memory. In 9th International Con- ference on Learning Representations, ICLR 2021, Vir- tual Event, Austria, May 3-7, 2021. OpenReview.net,
Yimeng Min, Frederik Wenkel, and Guy Wolf. 2020. Scattering GCN: overcoming oversmoothness in graph convolutional networks. In Advances in Neural Information Processing Systems 33: Annual Confer- ence on Neural Information Processing Systems 2020. NeurIPS 2020, December 6-12, 2020, virtual.
Imanol Schlag and Jürgen Schmidhuber. 2018 Learn- ing to reason with third order tensor products. Advances in Neural Information Processing Systems

---

31: Annual Conference on Neural Information Pro- cessing Systems 2018, NewrlPS 2018, December 3-8, 2018, Montréal, Canada, pages 10003-10014.
Weiwen Xu, Yang Deng, Huihui Zhang, Deng Cai, and Wai Lam. 2021a. Exploiting reasoning chains for multi-hop science question answering. In Findings of the Association for Computational Linguistics: EMNLP 2021, pages 1143-1156.
Imanol Schlag and Jürgen Schmidhuber. 2018b. Learn- ing to reason with third order tensor products. In Advances in Neural Information Processing Systems
Weiwen Xu, Huihui Zhang, Deng Cai, and Wai Lam. 2021b. Dynamic semantic graph construction and reasoning for explainable multi-hop science question answering. In Findings of the Association for Com- putational Linguistics: ACL/IICNLP 2021, Online Event, August 1-6, 2021, volume ACL/IJCNLP 2021 of Findings of ACL. pages 1044-1056. Association for Computational Linguistics.
31: Annual Conference on Neural Information Pro- cessing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages
Zhengxiang Shi, Qiang Zhang, and Aldo Lipani. 2022. Stepgame: A new benchmark for robust multi-hop spatial reasoning in texts. In Thirty-Sixhh AAAI Con- ference Artificial Intelligence, AAAI 2022. pages 11321-11329.
Rui Yang, Wenrui Dai, Chenglin Li, Junni Zou, and Hongkai Xiong. 2023. Tackling over-smoothing in graph convolutional networks with em-based joint topology optimization and node classification. IEEE Trans. Signal Inf. Process. over Nenworks, 9:123-139.
Paul Smolensky. 1990. Tensor product variable binding and the representation of symbolic structures in con- nectionist systems. Artif. Intell., (::(11)::99-21111
Yunchong Song, Chenghu Zhou, Xinbing Wang, and Zhouhan Lin. 2023. Ordered GNN: ordering mes- sage passing deal with heterophily and over- smoothing. CoRR, abs/2302.01524.
Yue Zhang, Quan Guo, and Parisa Kordjamshidi. 2021. Towards navigation by reasoning over spatial config- urations. CoRR, 00s/21055.06833
Yue Zhang and Parisa Kordjamshidi. 2022. Explicit object relation alignment for vision and language navigation. In Proceedings of the 60th Annual Meet- ing of the Association for Computational Linguistics: Student Research Workshop, ACL 2022, Dublin, Ire- land, May 22-27, 2022, pages 322-331. Association for Computational Linguistics.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones. Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Advances in Neural Information Pro- cessing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 3998-6008
Petar Velickovic. Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Ben- gio. 2017. Graph attention networks. CoRR, abs/1710.10903..
Appendix
A Preliminary of Tensor Product
Representation
Sagar Gubbi Venkatesh, Anirban Biswas, Raviteja Upadrashta, Vikram Srinivasan, Partha Talukdar, and Bharadwaj Amrutur. 2021. Spatial reasoning from natural language instructions for robot manipulation. In IEEE International Conference on Robotics and Automation, ICRA 2021, Xi an, China, May 30 June 5, 2021, pages 11202, IEEE
Consider the implicit relation hidden in the sen- tence "X is over K." Our method decomposes this sentence into two groups of role r c R and filler f E F symbol components, i.e., R = {x, K} and F = {above, below). The role and filler sym- bols are projected into role VR and filler V/ vector space, respectively. The TPR of these symbol struc- tures is defined as the tensor T within the vector space VR @ Vy, where & denotes the tensor prod- uct (equivalent to outer product when role and filler are one-dimension vectors). In this example, we can drive the equation of writing our example to T:
Guangtao Wang, Rex Ying, Jing Huang, and Jure Leskovec. 2021. Multi-hop attention graph neural networks. Proceedings of the Thirtieth Interna- tional Joint Conference on Artificial Intelligence, IJ- CAI 2021, pages 5089-3096. ijeai.org.
Jason Weston, Antoine Bordes, Sumit Chopra, and Tomás Mikolov. 2016. Towards ai-complete question answering: A set of prerequisite toy tasks. In 4th In- ternational Conference on Learning Representations. ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings.
= fahove & Fx + Fresow & TkK T K
(16)
fabane? X + foetow
The tensor product acts as a binding operator bind the corresponding role and filler.
Gongee Wu. Shukuan Lin. Xiaoxue Shao, Peng Zhang. and Jianzhong Qiao. 2023. QPGCN: graph con- volutional network with quadratic polynomial fil- ter for overcoming ovor-smoo Appl. Intell., 53(6):2116-2233
The tensor inner product serves as the unbinding operator in TPR, which is employed to reconstruct the previously reserved fillers from T. Given the

---

Experiment
Dutaset
epochs
batch size
PLM learning rate
non-PLM learning rale
BERT ALBERT RoBERTs
StepGame
22
32
2e-05
StepCoaee
32
6e-06
StepGame
16
32
6e 06
DepWiNat(BERI)
StepGamee
17
32
2c-05
1c-04
DepWENet(ALBERT)
StepGame
DepWiNet(koBERTh)
StepCaame
19
32
6c-06
1c-04
DepWiNe((BERT)
SPARTUN
16
8e-06
1c-04
DepWiNer(AERT)
ReSQ(with SPARTUN supervision)
5e-05
4c-05
DepWENe(BBRRT)
Re5Q(withou SPARTUN supervision)
16
Se-05
4e-05
DepWiNer(who L.CC)
StepGame
5c-05
DepWiNettwlo NMI LDC)
StepCiaee
14
32
6c-06
5c-05
DepWiNet(wlo SRR LDC)
StepGame
14
32
6e
Se
DepWiNettw/ DepWiGNN
StepCiame
6c-06
5c-05
DepWENettw/ DepWiNN
StepGame
14
32
6e 06
Se 05
DepWiNet(w/ GCN.
StepGame
(16.12.10,19.14)
DepWiNet(w// Graphoovr a)
StepCiame
(14,14,16,20,55)
32
6c-06
5c-05
DepWiNet(w/ GATTI GAT
StepGome
(16.13.16.16.17)
32
6c-06
5c-05
Table 5: Hyperparameters and setup information for each experiment.
unbinding vector uk,
retrieve the stored
filler Joelow from the T. In the most ideal cases, if the role vectors are orthogonal to each other, 4к equals rk- When T c IR?,, it can be expressed as the matrix multiplication.:
T uk (Fabove + fbctoo F rK
(17)
a fbelow X Sbelow
B Hyperparameter Settings
Detailed hyperparameter settings for each exper- iment are provided in Table 5. Epoch numbers
for WepWiNet with the three classical GNNs are grouped (in order) for simplicity.


Reviews:
[{"review_id": "I8p52g02OR", "reviewer": "Reviewer_jQ72", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the thoughtful and valuable comments. We carefully address all your concerns one by one as follows:\n1. Thanks so much for suggesting the analysis of the algorithm complexity of the proposed method. The time complexity of finding the shortest path between each pair of indirectly connected nodes is O((n+e)*n), as the edges are unweighted. The space consumption is not mainly from the breadth first search but the two-dimensional TPR node memory (as mentioned in the limitation). However, we believe it is worth applying such a node memory scheme as it considerably facilitates the reconstruction of the depth information. We will add the detailed algorithm complexity analysis. \n2. Sorry about the confusion regarding the main idea of the proposed method. We would like to clarify that the novelty of this paper is NOT about the BFS. It comes from mainly two points: (i) the depth aggregator that aggregates information over depth dimension, and (ii) the node memory scheme that could easily store and reconstruct depth-wise information for each pair of nodes. To the best of our knowledge, most of the research still focuses on the breadth aggregation scheme, some of them concerned with expanding the aggregation target range (as mentioned in the GNNs part of related works), but none of them studied directly aggregating information over depth dimension and using a two-dimension TPR node memory to store and reconstruct depth information between two nodes as we did. We will make this point clearer. \n3. We, indeed, conduct experiments to verify the over-smoothing issue. Following the standard experimental settings in previous studies [1,2], the experiments in section 4.4 can prove that our model can better handle the over-smoothing problem. In the paper, we compared our model with three different typical GNNs with different layer numbers. The result shows that other models’ performance decrease as their number of layer increases and our model consistently outperform all of them, which demonstrates that our model could better tackle the over-smoothing problem and has better capacity to collect long dependency.\n\nWe also followed the suggestion from another reviewer and did one extra experiment for the model GCNII [3], which is a popular model designed to overcome the over-smoothing problem. The results are shown below:\n\n\n|  Mean(k=1-5)/(k=6-10) | L=1  | L=2  | L=3  | L=4  |L=5 |\n|:---:|:---:|:---:|:---:|:---:|:---:|\n| GCNII  | 89.58/63.57  |  90.59/64.73 | 89.17/64.20  | 91.01/65.35  | 89.87/63.68 |\n| DepWiGNN  | 94.21/72.87  | 94.21/72.87  | 94.21/72.87  | 94.21/72.87  | 94.21/72.87 |\n\nL means the number of layers. \nWhile the performance of GCNII does not decline too much with increasing layer number, it underperforms our model by a large margin. This also proves our model’s immunity to the over-smoothing problem. We will add this result and further highlight the analysis of the over-smoothing issue to better address your concern.\n\n- [1] Li, Qimai, Zhichao Han, and Xiao-Ming Wu. \"Deeper insights into graph convolutional networks for semi-supervised learning.\" Proceedings of the AAAI conference on artificial intelligence. Vol. 32. No. 1. 2018.\n- [2] Wu, Gongce, et al. \"QPGCN: Graph convolutional network with a quadratic polynomial filter for overcoming over-smoothing.\" Applied Intelligence 53.6 (2023): 7216-7231.\n- [3] Chen, Ming, et al. \"Simple and deep graph convolutional networks.\" International conference on machine learning. PMLR, 2020.", "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": "(1) The paper proposes a novel GNN model for spatial reasoning.\n(2) The writing is well-organized and easy to follow. Each module in section 3 Method is clear.\n(3) The experiments are relatively detailed and the results demonstrate the effectiveness of the proposed model.", "reasons_to_reject": "(1) The model needs to first find the shortest path between two nodes using a breath-first search. It seems to require a lot of time and space overhead. But the authors do not explore it.\n(2) Actually, the main idea of the paper is the depth-wise graph neural network, which is realized by breath-first search and DepWiGNN Module. As there are already lots of relevant studies, the novelty is limited.\n(3) The authors argue that the model can avoid the issue of over-smoothing, but there are no experiments to verify it.", "questions_to_authors": "", "paper_topic_and_main_contributions": "The paper proposes a depth-wise graph neural network for multi-hop spatial reasoning in text. The model can capture long dependency without the need of stacking layers and avoid the issue of over-smoothing. The experiment results demonstrate its effectiveness.", "excitement": 3, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "KFrFqoKLJn", "reviewer": "Reviewer_YL2U", "summary": "", "questions": "1. What is the definition of an \"entity\"? I don't see it formally defined in the paper.\n2. In Section 3.1 the authors state \"The entities are first recognized from the input by employing rule-based entity recognition.\". Can you give more details.\nI'm confused as to exactly how the entities are identified and their tokens combined.\n3. Why is the [CLS] token used as the edge feature? What's the motivation/justification?\n4. What's the complexity of DepWiGNN? While it avoid propagating for many layers, the BFS search and the long dependency collection seem to have a large impact on the efficiency. A complexity or runtime analysis would be appropriate.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the detailed and valuable comments. We carefully address all your concerns one by one as follows:\n1. Thank you so much for the valuable and thoughtful suggestions. We will make necessary reorganizations to the relevant part according to your suggestions in the revision.\n2. The basic breadth aggregation scheme is susceptible to another problem called over-squashing [1], which means that there will be an information overflow for the node as the propagation goes on for many layers. The paper also presents that while some modifications about the breadth aggregation alleviate the over-squashing problem (like attention), they still suffer from that when the distance grows further. Hence, we tried a new approach that utilizes depth aggregation instead of typical breadth aggregation.\n3. We appreciate the valuable and thoughtful suggestions. We further compare the proposed method to GCNII. The results are shown below:\n| Mean(k=1-5)/(k=6-10) | L=1  | L=2  | L=3  | L=4  | L=5  |\n|---|---|---|---|---|---|\n| GCNII | 89.58/63.57  |  90.59/64.73 | 89.17/64.20  | 91.01/65.35  |  89.87/63.68 |\n| DepWiGNN | 94.21/72.87  | 94.21/72.87  | 94.21/72.87  | 94.21/72.87  | 94.21/72.87  |\n\nL means the number of layers.\n\nThe performance of GCNII does not decrease much when the layer number increases, yet it still underperforms our model by a large margin, which demonstrates our model’s capacity to collect long dependency. This may also serve as evidence that depth aggregation might be more effective at dealing with the over-smoothing problem than basic breadth aggregation. We will add this result to our experiment in section 4.4.\n\nAnswers to the questions:\n1. Entity in this paper refers to the spatial roles defined in [2]. For example, in stepgame, “X is to the left of K and is on the same horizontal plane.” the entities will be “X” and “K”; in ReSQ, “A small orange apple is inside and touching box one,” the entities will be “a small orange apple” and “box one.” We will make this point clearer. \n\n2. For StepGame, all the entities are represented by single capitalized letters from A to Z, so we just recognize them and mark their location during the tokenization process. For SPARTUN and ReSQ, we use nltk RegexpParser (https://www.nltk.org/api/nltk.chunk.regexp.html) with self-designed grammars r\"\"\"\"NP:{<ADJ|NOUN>+<NOUN|NUM>+}\"\"\" and r\"\"\"\"NP:{<ADJ|NOUN>+<VERB>+<NOUN|NUM>}\"\"\" to recognize entities. We will further elaborate the implementation details to make the process clearer.\n\n3. The motivation behind treating [CLS] token as an edge feature is that it can help the model better understand the atomic relation (k=1) between two nodes (entities) so as to facilitate later depth aggregation. A straightforward justification can be found in Table 1, where all three PLMs achieve very high accuracy at k=1 cases by using the [CLS] token, which demonstrates that the [CLS] token favors the understanding of the atomic relation.\n\n4. The most time-consuming part is the shortest path finding between each pair of indirectly connected nodes in LDC, since the edges do not have weights, its complexity is O((n+e)*n), where n and e are the number of nodes and edges, respectively. We will add relevant complexity analysis to the paper. \n\n- [1] Alon, Uri, and Eran Yahav. \"On the bottleneck of graph neural networks and its practical implications.\" arXiv preprint arXiv:2006.05205 (2020).\n- [2] Kordjamshidi, Parisa, Marie-Francine Moens, and Martijn van Otterlo. \"Spatial role labeling: Task definition and annotation scheme.\" Proceedings of the Seventh conference on International Language Resources and Evaluation (LREC'10). European Language Resources Association (ELRA), 2010.", "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": "1. The motivation is clear. They clearly state why traditiona GNNs may struggle in this task and why they design an alternative.\n2. The main results on the baselines are promising. They show that their framework can achieve both strong overall performance, and good performance on \nquestions with longer dependencies.\n3. The additional studies (ablation and case study) are useful and do a good job of supporting the main results.", "reasons_to_reject": "1. The methodology is confusing at times (see questions for some clarification). The issue for me is that the details of the framework are just presented to the reader, instead of being better introduced and motivated. I'd recommend re-organizing Section 3, empahsizing (a) the challanges of designing a GNN that addresses your motivation, (b) what general ideas/components are required to meet these challenges, and (c) mention how each component you introduce can address a challenge. Putting this in the beginning of section 3 will give the reader a better context behind the design of your framework. As of now, a lot of the design seems arbitrary (e.g. see question 3 later).\n\n2. While the motivation of the paper is clear (oversmoothing is detrimental to capturing long-term dependecies), more evidence should be given to support it. Specifically, the authors mention after introducing some works that study oversmoothing (on line 202) that \"However, these methods are all breadth-aggregation-based ... but never jumping out of it\". I think a clearer motivtion needs to be given why it's needed to \"jump out\" of the standard aggregation procedure. Is basic aggregation inheritely incapable of capturing the necessary information (theoretically or empirically)? \n\n\n3. In Table and Figure 4, DepWiGNN is compared against other traditional GNN frameworks. It's clear that such frameworks struggle as k increases. However, such models are well known to suffer from over-smoothing. It would be better to include methods meant to address over-smoothing. I recommend including GCNII [1], a popular method for doing so. It's possible that it may fair better as k increases. \n\n\n[1] Chen, Ming, et al. \"Simple and deep graph convolutional networks.\" International conference on machine learning. PMLR, 2020.", "questions_to_authors": "1. What is the definition of an \"entity\"? I don't see it formally defined in the paper.\n2. In Section 3.1 the authors state \"The entities are first recognized from the input by employing rule-based entity recognition.\". Can you give more details.\nI'm confused as to exactly how the entities are identified and their tokens combined.\n3. Why is the [CLS] token used as the edge feature? What's the motivation/justification?\n4. What's the complexity of DepWiGNN? While it avoid propagating for many layers, the BFS search and the long dependency collection seem to have a large impact on the efficiency. A complexity or runtime analysis would be appropriate.", "paper_topic_and_main_contributions": "In this paper, the authors study the problem of multi-hop spatial reasoning for text. They introduce a limitation that plague GNN models when applied to\nthis task. To address these issue they propose a framework that can better collect long-term dependencies between two nodes in the graph. They detail their results \non multiple benchmarks. They further show that their model excels for questions of longer length (i.e., relations). Overall, while I find the results quite promising, I believe the motivation and writing need to be further improved at this stage.\n\nRebuttal Update: Raised my soundness score from a 2 &rarr; 3 after a discussion with the authors.", "excitement": 3, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "dpMLtApVPY", "reviewer": "Reviewer_b7C1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments.\n\nWe, indeed, conduct experiments to verify the over-smoothing issue. Following the standard experimental settings in previous studies [1,2], Section 4.4 includes experiments for breadth based GNNs (GCN, GAT, GraphC) on the StepGame dataset, and it serves as the empirical evidence that our model alleviates the problem of over-smoothing. Specifically, we compared our model against the three breadth based GNNs on various layer numbers from 1-5. The result shows that the performance of our model surpasses all other baselines by a large margin for all layer number cases. This proves two things: First, the typical GNNs do suffer from the over-smoothing problem because their performance drops evidently while the number of layers increases (especially for the large k values); Second, our model has better immunity to the problem because, theoretically, it does not need to stack multiple layers to collect long dependencies and, empirically, it consistently performs better than all the other models.\n\nWe also followed the suggestion from another reviewer and did one extra experiment for the model GCNII [3], which is a popular model designed to overcome over-smoothing problems. The results are shown below:\n\n| Mean(k=1-5)/(k=6-10)  | L=1  | L=2  | L=3  | L=4  | L=5  |\n|---|---|---|---|---|---|\n| GCNII | 89.58/63.57  |  90.59/64.73 | 89.17/64.20  | 91.01/65.35  |  89.87/63.68 |\n| DepWiGNN  | 94.21/72.87  | 94.21/72.87  | 94.21/72.87  | 94.21/72.87  | 94.21/72.87  |\n\nL means the number of layers.\n\nWhile the GCNII performance does not decline too much with increasing layer number, it underperforms our model by a large margin. This also proves our model’s immunity to the over-smoothing problem. We will add this result and further highlight the analysis of the over-smoothing issue to address your concern better.\n\n- [1] Li, Qimai, Zhichao Han, and Xiao-Ming Wu. \"Deeper insights into graph convolutional networks for semi-supervised learning.\" Proceedings of the AAAI conference on artificial intelligence. Vol. 32. No. 1. 2018.\n- [2] Wu, Gongce, et al. \"QPGCN: Graph convolutional network with a quadratic polynomial filter for overcoming over-smoothing.\" Applied Intelligence 53.6 (2023): 7216-7231.\n- [3] Chen, Ming, et al. \"Simple and deep graph convolutional networks.\" International conference on machine learning. PMLR, 2020.", "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": "- The authors introduce a novel GNN modeling approach that incorporates a node memory scheme that leverages the TPR mechanism, enabling simple arithmetic operations for memory updating and retrieval, instead of relying on additional neural layers.\n\n- The authors perform several experiments and benchmark with both popular LLMs and GNNs to validate the performance of their approach.\n", "reasons_to_reject": "- Some experiments do not look very comprehensive to me, for instance, why don't the authors experiment with breath based GNNs in the StepGame experiment?\n\n- The authors constantly highlight the fact that DepWiGNN doesn't encounter the oversmoothing issue like regular GNNs but do not show empirical evidence for the same. ", "questions_to_authors": "", "paper_topic_and_main_contributions": "The paper proposes a novel Depth-Wise Graph Neural Network (DepWiGNN) for spatial reasoning in text. It addresses the challenges faced by classical GNNs in handling multi-hop spatial reasoning, specifically the over-smoothing issue, by designing a unique node memory scheme and aggregating information over the depth dimension of the graph. The proposed Transformed Product Rule (TPR) mechanism enables convenient memory updating and retrieval operations through simple arithmetic operations, rather than relying on additional neural layers. The authors claim thate xperimental results on challenging multi-hop spatial reasoning datasets demonstrate that DepWiGNN outperforms existing spatial reasoning methods. \n\n\n", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: **Summary:** The paper proposes a novel depth-wise graph neural network (DepWiGNN) for multi-hop spatial reasoning in text. The paper claims that DepWiGNN can mitigate the over-smoothing issue faced by GNNs through aggregating information over the depth dimension of the graph. The proposed Transformed Product Rule (TPR) mechanism enables convenient memory updating and retrieval operations through simple arithmetic operations, rather than relying on additional neural layers. Empirical evaluation is performed on two multi-hop spatial reasoning datasets where DepWiGNN outperforms three GNN based baselines.

Overall the paper is well written and easy to follow (with detailed explanation for specific design choices). The empirical results are sound and show that their approach achieves strong gains over multiple strong baselines on two multi-hop spatial reasoning benchmarks. The main concern raised by the reviewers is the limited empirical evidence in the paper pertaining to the main claim of their approach mitigating over-smoothing faced by classical GNNs. Through the rebuttal and reviewer discussion, the authors have added comparison with a stronger over-smoothing mitigating baseline GCNII, as well as expanding the results for the GraphConv model to 10 layers. The results show that the DepWiGNN approach avoids over-smoothing, however the strong empirical performance cannot be solely attributed to mitigating this issue. The paper's empirical claim needs to be strengthened by highlighting that baseline methods suffer from a bottleneck when aggregating longer paths, and how DepWiGNN avoids this.

**Recommendations for Improvement:** (i) Restructure the prose writing to mitigate the concern about the methodology of the paper lacking motivation for each individual design choice of the approach.

(ii) Add details around the time and space overhead complexity of the BFS to the paper.

(iii) Add additional experiments that highlight that baseline methods suffer from a bottleneck when aggregating longer paths, and how DepWiGNN avoids this.
Decision: Accept-Findings