Learning to Navigate Wikipedia by Taking Random Walks
Authors: Manzil Zaheer
Kenneth Marino
Will Sussman Grathwohl
John Schultz
Wendy Shang
Sheila Babayan
Arun Ahuja
Ishita Dasgupta
Christine Kaeser-Chen
Rob Fergus
Venue: NeurIPS 2022 Accept (2022)
Keywords: web navigation
wikipedia
retrieval
fact verification
question answering

Abstract: A fundamental ability of an intelligent web-based agent is seeking out and acquiring new information. Internet search engines reliably find the correct vicinity but the top results may be a few links away from the desired target. A complementary approach is navigation via hyperlinks, employing a policy that comprehends local content and selects a link that moves it closer to the target. In this paper, we show that behavioral cloning of randomly sampled trajectories is sufficient to learn an effective link selection policy. We demonstrate the approach on a graph version of Wikipedia with 38M nodes and 387M edges. The model is able to efficiently navigate between nodes 5 and 20 steps apart 96% and 92% of the time, respectively. We then use the resulting embeddings and policy in downstream fact verification and question answering tasks where, in combination with basic TF-IDF search and ranking methods, they are competitive results to the state-of-the-art methods.

Learning to Navigate Wikipedia by Taking Random Walks
Manzil Zaheer", Kenneth Marino", Will Grathwohl", John Schultz", Wendy Shang, Sheila Babayan, Arun Ahuja, Ishita Dasgupta, Christine Kaeser-Chen, Rob Fergus
DeepMind New York
(manzilzaheer, kmarino, xgrathwohl, jhtschultz, wendyshang, sbabayan, arahuja, idg, christinech, robfergus)@google.. com
Abstract
A fundamental ability of an intelligent web-based agent is seeking out and acquiring new information. Internet search engines reliably find the correct vicinity but the top results may be a few links away from the desired target. A complementary approach is navigation via hyperlinks, employing policy that comprehends local content and selects a link that moves it closer to the target. In this paper, we show that behavioral cloning of randomly sampled trajectories is sufficient to learn effective link selection policy. We demonstrate the approach on a graph version Wikipedia with 38M nodes and 387M edges. The model is able efficiently navigate between nodes and 20 steps apart 96% and 92% of the time, respectively. We then use the resulting embeddings and policy in downstream fact verification and question answering tasks where, in combination with basic TF-IDF search and ranking methods, they are competitive results the sfate-o--hhe-sd methods.
Introduction
The ability gather new knowledge about the world a fundamental aspect of intelligence. Based only on few words, a fact, question, or even vague idea, humans have the ability to use the internet find extremely specific information about the world. From the important (how to administer CPR) to the trivial (the LA Raiders won the 1983 SuperBowl), virtually any knowledge is click away.
In this work, focus in one particular aspect of this ability: web navigation. In general, navigation is a key component of an embodied agent: the ability to move efficiently toward target. In known environments, where map information available, shortest-path algorithms provide viable solution. However, in novel settings, the agent lacks such global information and must instead navigate to the target, using its understanding of the local environment select actions.
Other approaches to web agents have focused mostly on retrieval or search engines. These, however, only provide partial solution, typically getting close desired target but often not exactly the right page. In this work, we present an approach for navigation on graph-structured web data that uses hyperlinks within articles to navigate toward target. It complements search engines, using them to provide a sensible starting point for a local search for specific information.
To be able to navigate the web effectively, we must read the text of the page, see how concepts in the current page are related to possible next page, and use our understanding to learn policy to make the right navigation decision. Consider the scenario shown in Figure 1. The agent is trying to navigate to the target node NORTH AMERICA while currently at the node PRESIDENTS OF THE UNITED STATES containing two hyperlinks: BARACK OBAMA and USA. Our approach learns
Denotes equal contribution
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Node
Node Text
Transformer
MLP
Action probability
Current Node
Presidents
"Barack Obama President of United States
United States
Node
Barack Obama
"Barack Obama is an American Politician...
41
P1
wew. USA nation North America...
Node 2
USA
42
O
P2
Goal Node
North America
"North America continent the...
Our agent navigates through hyperlinks Wikipedia graph towards target node. It first embeds the text at each link node using Transformer o(.) and then evaluates different actions/links a1 22 with policy 0, conditioned the current and target embeddings st and sg. respectively.
Figure I:
embedding from the text of the current page and the text for each hyperlink node and passes these to goal- conliconditioned policy that selects the best possible action. To make the correct choice in this example, the agent should associate USA with NORTH AMERICA.
The particular web environment we consider here is Wikipedia, converted into a graph form. Each of the 38M paragraphs is represented by node; edges are links within and between articles. We introduce an approach for navigation on this graph based on behavioral cloning of automatically generated trajectories. This allows for unsupervised pre-training of both web page embeddings and navigation policy. We explore different trajectory distributions for training the model, the best practical choice being equivalent to random walks on the graph.
Contributions: Our work presents the first viable solution to the problem of web navigation', as demonstrated by reliable (>90% success) navigation on graph of size 10?. Previous attempts such as Nogueira and Cho [2016] show far inferior performance, well below that needed for practical utility, Furthermore, as there is nothing Wikipedia-speciffe about our approach and it scales gracefully, the method is applicable to general web settings. We also demonstrate the relevance of the pre-train + fine-tune paradigm to the web domain, showing that pre-training for navigation is a suitable objective to aid downstream tasks with limited data such as Q&A. We demonstrate this by applying our navigation approach on two challenging tasks: fact verification (FEVER; Thorne et al. [2018]) and Q&A (Natural Questions; Lee et al. [2019]) for evidence gathering. In both settings, we show a jump in performance over existing search-based approaches that rely retrieval followed by re-ranking, matching state-of-the-art methods despite using far simpler retrieval and re-ranking mechanisms.
2 Background
Wikipedia a navigation environment: Human behavior Wikipedia [West and Leskovee, 2012a] was collected via the Wikispeedia game [West et al., 2009], which asked the players to move between pair of arbitrarily chosen articles in the fewest steps. This rule allows the emergence of semantic distance between concepts that facilitates retrieval. West and Leskovec [2012b] conducted initial studies on this dataset for navigation, using supervised learning and reinforcement learning methods on a small subset of articles (4.6K) with simple TF-IDF features.
Most relevantly, Nogueira and Cho [2016] explore the same problem of navigation Wikipedia graph (12M nodes). They train LSTM agents to perform navigation on the graph, using Bag-of- Word features for each article. The trained agent is then applied to Jeopardy Q&A task. Our approach revisits this framing but with a number of important differences: (i) training on a significantly larger graph (38M 12M nodes, 51.5M 380M edges); (ii) using Transformer-based architectures for paragraph encodings and for the navigation policy; (iii) they use a single fixed start node, whereas ours is able navigate from any start node; (iv) removal of beam search, or other complex search mechanisms at evaluation time. Collectively, our approach boosts the navigation success rate from 12.5% in Nogueira and Cho [2016] to over 90%,2 despite a much larger graph.
large
A demo of our agent navigating is shown here https: //www http://wwwwww.bbbe////e wwwptte..ooo/wateeeeeeeeeeeeeeee cctm/rratcca////gaaapp....
2 Exact comparisons are infeasible given idiosynerasies in graph construction and other differences in setup.

---

Fact verification and Q&A using Wikipedia: Wikipedia is rich resource for evaluating language understanding through Q&A tasks. Chen et al. [2017] combine TF-IDF retrieval with an LSTM docu- ment reader to find answers to free-form questions within Wikipedia documents. Contemporary Q&A A systems [Semnani and Pandey, 2020, Qu et al., 2020] extend this general approach to more complex pipelines, combining traditional and neural methods with inverted index search/retrieval schemes, followed by document readers that perform re-ranking. We demonstrate our navigation approach in conjunction with very basic retrieval and re-ranking approaches, so as to clearly demonstrate the value of navigation. In common with our approach, Wang et al. [2021] also use graph version of Wikipedia, but with the goal of aligning it to knowledge base, rather than navigation. Stammbach and Neumann [2019] propose a scheme for finding evidence for the FEVER [Thorne et al., 2018] benchmark that explores all links one step away from an initial retrieval set. This can be viewed as 1steep navigation operation, in contrast to our scheme that permits an arbitrary number of steps.
Graph navigation is key element in utilizing knowledge bases (KB), where facts are represented as tuples of entity nodes connected by a labelled edge corresponding to relation between the two nodes. For example, Das et al. [2017] answer complex queries by navigating the graph, inferring missing edges along the way, and finding a valid path to the answer node. In our case, the graph is fixed but consists of natural language text and is partially observed. This makes the task much harder on two fronts. First, the policy must comprehend the natural language actions, without access to crisply labelled relation actions. Second, the action space is open and varying in size, unlike in a KB which typically has a fixed schema, i.c. relations/actions come from a fixed size set. Perhaps the closest work involving natural language actions, Fu et al. [2019] augment KB with textual nodes. However, it still operates under the fixed KB schema. Further improvements on navigation in KB have been shown by incorporating tricks like reward-shaping [Xiong et al., 2017] and action dropout [Lin et al., 201 8]. We adopted the action dropout where some outgoing edges are masked during training to enable more effective path exploration. Pushing more on exploration, inspired by AlphaGo. Shen et al. [2018]. He et al. [2022] combine the policy with Monte-Cart tree search to navigate KB. We find that no search method is necessary for our approach at evaluation time, with good performance obtained from the policy alone.
Navigation in knowledge bases:
Internet powered Q&A: Several recent works have attempted complex question answering using the internet. Talmor and Berant [2018] retrieve snippets of information from the web with a search engine to answer structured decomposition of the question with simpler Q&A model. The recent WebGPT [Nakano et al., 2021] system takes a broadly similar approach to long-form question answering. WebGPT accures information from the Bing search API as well as some navigation, and passes it to an LM to generate the answer text. The complexity of the system necessitates the use of human demonstrations for training. Related work from Lazaridou et al. [2022] utilizes few-shot supervision of an LM to perform Google queries, which are then used by the LM to generate an answer. They show that by incorporating information from Google queries. the answers are more factual than those generated directly from LMs. Another line of work, has leveraged link structure of webpages found on the internet to improve Q& In LinkBERT [Yasunaga et al., 2022] is pretrained to capture dependencies between documents and results in improvement for for multi-hop reasoning and few-shot reading comprehension. Asai et al. [2020] use the link structure to enhance open domain Q&& by learning to retrieve according to reasoning paths. In contrast to these works, we focus on mastering navigation rather than any combination with search/retrieval, albeit in more limited domain (Wikipedia vs the internet). However, our approach could potentially act as core component in general web navigation, being more versatile on account of not requiring supervision.
3 Approach
We consider navigation in a web environment W = (N, L}. where N == {n,) is the set of nodes, each n, representing web page with content s,. The links between pages are represented by = (4. N where = .l...... ......,,MMM } are the set of M, (directed) out-links from node i. We define NH(n.) as the set of nodes reached by following all links l, from node n,, where the jth neighbor is given by (m.))
We assume some target node ng and some starting node nig are given, and wish to train an agent that can navigate from ni to ny by walking along the edges of the graph within T steps. To accomplish this, we construct a parametric policy po (M++1 (4, nly) which, at time step I, parameterizes a distribution over n4-1 E NH(n.). We train this model via behavioral cloning to maximize
3

---

(() = Eg (T
Σ
log (m mas Ug)
(I)
where ( UT) is our trajectory distribution which generates trajectories (ro.,..., RTT) that would like our model to replicate (i.c. setting ny = =.
3.1 Trajectory distribution
This framework opens up many choices for E. Clearly some will result in ineffective navigation strategies while others may enable us train a policy which capable of generalizing to new graphs and downstream applications. We elaborate on some choices below.
Reverse trajectories: We define E(RT) Uniform(N) (the uniform distribution over nodes in the graph). Now we can define
E(melmet1)= = Kng, NH(n)H
if m4+1 E NH(n.), else 0
(2)
or, distribution which uniformly walks the reverse graph (with transposed adjacency matrix). We begin with some uniformly chosen target node and walk backward randomly to no in such a way that we can reach the target by walking forward from Aop
Intuitively, training with the reverse trajectories defined above should allow model to be able to reach any node in the graph from any node it is connected to. Unfortunately, in realistic web graph data, there exist many "dead-ends" or nodes with no in-going edges. The trajectories get stuck these nodes leading to low-diversity training data.
Random forward trajectories: In our real-world knowledge graph data, there far fewer nodes which have no out-going edges. Thus we propose an alternative method to generate target nodes based on randomly walking forward. We define E(n,) to be the Uniform(N) and
E(ne+1|me) [N+)]
if if E NH():), else O.
or, distribution which uniformly picks a starting node and randomly walks the forward graph for T steps. Training in this way should encourage our model to be able to reach any node which is reachable from some uniformly chosen start. We note that the target node distribution ((TT) will not be uniform and instead be function of the graph structure. We also note that while this generates T-step trajectory, because it is generated by random walk, the shortest path distance between start and target nodes may be smaller.
Random shortest paths: We define E(nr) Uniform (N) and let ((p)( be the uniform distri- bution of nodes whose shortest path length to ny is T steps. We then define E(n,) [og nr) to be the delta distribution that n, is the t-th node of this shortest path. While it can be challenging compute the probabilities of this distribution efficiently we can draw samples from it using a shortest path finding algorithm such as Dijkstra's algorithm.
3.2 Model parameterization
From above, we can see the core of our model is the (0 [,, nT) distribution. Given a sampled trajectory that begins at no. this is the distribution which attempts to choose the correct action to take at timestep f + starting at node n, in order to get to target node ny. We parameterize this distribution function of the text available node Ri.
po [n,, ng) x (o St, 8g.
where So embeds the text 8g. 8t and 8141 of the target, current and destination nodes, respectively. Further details on how we apply this general model to Wikipedia are given in Section 4.2 and an alternative interpretation of this approach based on variational inference in a latent-varialle model presented in Appendix D.

---

4 Application to Wikipedia
4.1 Navigation and sentence search tasks
Data processing: We convert snapshot of English Wikipedia into graph but split each article ( 1000 words) into paragraph-sized blocks (ī 100 words), which form the nodes. Edges in the graph are the union of (i) organic hyperlinks, (ii) additional entity linking and (iii) next/previous paragraph links. We consider two snapshots from year 2017 and 2018, which produces large full graphs with ~ 37M nodes and ~ 370M edges. For initial experiments, we also use a smaller subsampled graph, for which we sub-sample disjoint sets of 200k train / 200k evaluation nodes from the 2018 graph. All the obtained graphs are well connected with median path length of 15. Further details have been relegated to the Appendix (full graphs in Appendix A.I, the 200k graph in Appendix A.2, and graph statistics in Appendix A.3).
T-step navigation: The most basic task is Ttep navigation. the start of the episode, we randomly sample a start node and generate a T -step random walk trajectory. We then take the last node of this trajectory as the target ng. The agent is then given a time budget B (in most experiments, we fix max steps to B- = 100), and succeeds if it reaches the target node within B steps. In our experiments, we show results on various graphs and splits with = {5, 10, 20) -step navigation.
I Multistep navigation: The Multistep task is much like the previous setting, except that instead of generating fixed T'stte trajectories, we sample from Uniform( [1, T), T 20.
This is the same setup as 7-stpp navigation, except that rather than provide the full text for the target node R.g. only one sentence within that text is selected at random compute the target embeddings from. Thus agents have the more challenging task of locating the correct node, given only small snippet of its text (see Section 4.2 for details on target representation). We include this task because one of the difficulties of web navigation is establishing which page should be the target in the first place. It also has direct relevance to our downstream fact verification task.
T-step sentence search:
4.2 Model architecture
For each node n, we embed its text 8; using a Transformer o(.) to produce ((s;). By basing the state representation semantic content, rather than i.e. node index, the agent is able to learn about the relationships between entities in a manner that allows for generalization to new graphs evaluation time, instead of memorizing the structure of the training graph. Follow- ing Karpukhin et al. [2020], we append to the node text the title of the Wikipedia article to which belongs. This often provides context the node that might otherwise be missing - in many articles, the subject of the article will be referred to indirectly (e.g. it might state that "she" was born in 1945 instead of repeating the subject's name).
State representation:
For those experiments where the node embeddings are kept fixed, o(.) is a pre-trained ROBERTA [Liu et al., 2019] model that encodes the node text & title. However, in our large-scale experiments, we pre-train the Transformer ((.) directly using the text & title (see Appendix B.1). In both cases, we apply the Transformer the tokenized text, take the mean over the input tokens, and apply a tanh nonlinearity to produce ((s)).
Similarly, we use the article text Sy of the target node as input to the Transformer model to compute its representation ((x,). For some tasks, such as sentence search or fact verification, the target representation instead relies on a single sentence from each node or other text specific to the task and a separate transformer model @rarett is trained to embed the target.
Target representation:
Navigation policy network:
The network operates on the target node n, and the current node ni. and outputs a distribution over the possible actions that can be taken at n,, As the nodes in the graph have a variable number of outgoing edges, the policy must produce a distribution with variable number of outcomes. To do this, we first concatenate the embeddings of sg and st, and pass them through a 1-layer feed-forward network to produce a combined embedding Ctg = F FF(((s)), d(sy)]- Next we embed each possible action a, When we use fixed Φ, we directly use a; = ((s)) for n, (H().). However this is not feasible when pre-training our embedding model due to memory concerns. Instead, we compute a; = (f>; (Z]) where s((²] selects the words in s which belong to hyperlink i - see Appendix B.1 for more details. We then define the probability of moving to n, from
5

---

n, with target ng as p(n, Me, ngy) x exp (etg 0,) which is normalized to produce a distribution over the [NH(,,)] actions.
In our larger-scale model, we also include the trajectory leading up to the current node (no..... ne). We pass their embeddings, combined with the target embedding, (ó(sa)..... ((xx), c(s,)}, through 4-layer transformer and use the output as Eag when computing the transition probabilities above. We explore these two policy architecture choices, feed-forward and Transformer in Table 4.
4.3 Downstream tasks
Finally, we navigation approach gather information for the tasks of fact verification on the FEVER benchmark [Thorne et al., 2018] and question answering on Natural Questions (NQ) [Lee et al,, 2019] which also use Wikipedia a knowledge base. One important difference from earlier navigation task is that the target node ng is not specified at evaluation time. Instead, we are given a claim whose veracity must be established or a question that must be answered by finding information in a particular node in the graph. To determine which node this is, we use a target encoder which maps the claim or question to an embedding vector that can be used in place of ((s,) in Section 4.2.
Due to the limited size of the downstream training sets, we pre-train our graph embeddings, navigation policy and target encoder on the similar sentence search task. We then freeze the embeddings and policy and fine-tune the target encoder on (My. $g) pairs from the downstream task's training set. To avoid over-fitting, embedding and the embedding of the ground truth node containing the sentence needed to resolve the claim question. Training and evaluation FEVER and NQ required alignment between our version of Wikipedia and the one used to compile the benchmark and details of this can be found in Appendix C.1 and C.2.
add an auxiliary loss which enforces the similarity between our target
Next, our navigation method requires a starting node. To put our agent close to the articles we need in the downstream tasks, we run popular variant of TF-ID,, called BM25 [Robertson and Zaragoza, 2009]. We first create an index over all of the nodes in the graph, then take the top-5 BM25 matches as the starting nodes, and run navigation for 20 steps on each. Note that BM25 often does not find the exact text (i.e. the hits@I I is not high) but matches are in the right vicinity, usually the same or similar article. Thus the agent only has navigate few steps to reach the target: in FEVER and NQ datasets, the mean length of shortest path between start and target node is 4.3 and 5.1 steps respectively.
The final component is a re-ranker that takes all the sentences from all nodes visited by the agent and assigns a match score between each one and the claim. The ranked list of sentences can then be used for benchmark evaluation. We explore two types of ranker: (a) basic TF-IDF and (b) transformer based model like BERT or BigBird, fine tuned using hard negatives mined from the TF-IDF ranker. See Appendix C.I and C.2 for more details.
Evaluation of our approach thus consists of: (i) given a claim/question, use BM-225 to return list of promising start locations; (ii) from the top N = 10 of these, run our navigation model for 20 steps, using the target encoder to embed the claim/question, (iii) use the re-ranker to score sentences visited against the claim/question and (iv) select the top 5 for computing the recall, precision, or Fl score, for comparison on the benchmarks.
5 Experiments
5.1 Investigation of training trajectory distribution
On the smaller 200k node graph, we investigate different choices for the trajectory policy distributions E described in Section 3: (i) Random Forward Trajectories, where we randomly sample start nodes and do random walk to get target, (ii) Reverse Trajectories, where we randomly sample target node and and do a random walk on the reverse graph to get start node, and (iii) Random Shortest Paths where we randomly sample a start node and take a random walk and then compute the shortest path between the start and target nodes. For each of these we trained policies on 5, 10, and 20 step navigation tasks. We evaluate these two different ways: (i) forward sampling of source and target in the disjoint evaluation graph, (ii) reverse sampling of source and target. The results of this experiment are shown in Table 1. Unsurprisingly, we can see that forward and reverse trained policies both do better when evaluated in the way that matches training. However, forward trajectory policies

---

Table 1: Different trajectory distributions on small graph (200k nodes)
Navigation (Forward)
Navigation (Reverse)
Trajectory Policy
5
10
20
5
10
20
Forward
85.3
76.4
67.5
31.1
32.6
19.9
Reverse
2.3
0.5
0.2
91.3
87.9
87.3
Shortest path
86.7
85.0
84.6
74.3
31.6
28.4
generalize much better to reverse navigation. When we analyze the traces of these experiments, we see that in the reverse sampling, many target nodes are in "dead-ends" where many target nodes do not have long random trajectories to sample. This results in easier navigation (as we can see from higher accuracy in reverse trajectory trained policies on reverse navigation) and more extreme overfitting, leading to poor performance of reverse trajectory on forward navigation.
Not surprisingly, we also that training both in the forward and reverse sampling. This advantage is especially seen in the 20-step navigation task. Ideally, we would always train on shortest paths. However, the time complexity of pre-computing all shortest paths in a graph using Dijkstra's 's algorithm is OVV Vo) for the number of nodes V and number of edges in the graph. On the full 38M Wikipedia graph, this computation would be completely intractable. Luckily, the random forward trajectories perform almost as well and can be computed in constant time with respect the size of the graph and only linear time with respect to the trajectory length. For all subsequent experiments, we use the Random Forward Trajectories for our trajectory policy and evaluate on the forward version of the navigation tasks, where we call our approach Random Forward Behavioral Cloning (RFBC).
shortest path trajectories leads to better performance
5.2 Navigation
We next a more thorough set of experiments on the smaller 200k Wikipedia graph. Because the graph is much smaller than the full Wikipedia and thus prone to overfitting, for all of our methods and baselines we use the fixed RoBERTA embeddings ((s)), the simplest I-layer feed-forward network, and MiniBERT [Ture et al., 2019] for target sentence embedding ((sg).
Alongside our approach, we employ the following baselines/ablations:
RFBC: Random-forwan behavioral cloning (our approach).
RFBC RF: RFBC but with random features sampled from the unit sphere instead of
RL + RF: RL with random features.
Random: policy that chooses random action (out-link) at each timestep.
Greedy: selects the action embedding which has the smallest cosine distance with the target.
Random DFS: DFS of depth equal to number of steps, choosing actions at random.
Greedy DFS: DFS but select action with smallest cosine distance to the target.
More training details are in Appendix B.2 and computational cost of each in Appendix E.
The results evaluated on the held-out graph are shown in columns 1-4 of Table 2. Our approach (RFBC) performs well, achieving 77% in the multistep case. Performance also drops as the distance the target increases. contrast, the RL agent performs poorly (around 40% on navigation tasks). Because we generate virtually infinite expert trajectories with RFBC, RL performs worse as it is trained with essentially the same amount of exploration, but with more sparse signal than behavioral cloning. Using random features in place of ((-) caused the performance to drop to near chance, showing that the models are utilizing the semantics at each node and are not relying on a general search strategy of some kind. Random methods also do quite poorly, methods do a bit better than random, especially with DFS, but still well below our method.
when adding DFS. Greedy
We also consider the more challenging sentence search task described in Section 4.1. This task requires not only finding a known target node, but learning find target node given only a single random sentence from that node, more closely matching our downstream task and the way humans tend to approach finding information on the web. Columns 5-7 of Table show performance on this task for our approach and RL. Our method has reduced performance on the task due to the extra difficulty of learning the target embedding, but still performs reasonably. RI., however, degrades to near chance performance.
7

---

Table 2: Small graph navigation (200k nodes) Success rate (%)
Navigation
Sentence Search
Method
5
10
20
multistep
5
10
20
RFBC (ours)
85.3
76.4
67.5
77.4
60.7
47.6
34.6
RL
41.4
40.2
41.6
43.6
14.0
1.5
8.9
RFBC RL (ours)
85.1
77.6
68.1
78.3
RFBC RF
17.4
16.3
16.6
17.1
RL RF
6.0
7.5
7.0
6.7
Random
12.3
14.9
12.3
14.0
Greedy
19.7
16.7
21.7
23.4
Random DFS
10.0
9.5
8.3
10.0
Greedy DFS
31.1
23.8
22.7
51.8
Table 3: Wikipedia graph statistics
Year
# Articles
Nodes
# Edges
Words Node
Median Path Length
2017
4.92M
36.3M 38.5M
359M 387M
110
15
2018
5.27M
109
15
5.3 Navigation on full 38M node Wikipedia graph:
Our method scales naturally to much larger graphs, which we demonstrate by training on the entire Wikipedia 2017 graph. We evaluate on the entire Wikipedia 2018 graph. Each graph is ~ 37M nodes and ~ 370M edges (see Table 3 for details). We would like point out there is significant evolution (difference) between the 2017 and 2018 graph as analysed in Appendix A.3 along with further statistics.
We explore both architectures described Section 4.2 for the policy network: (i) the single feed- forward layer (as used in the smaller graph) and (ii) the 4-layer Transformer model. We also compare using a fixed RoBERTA model for & versus pre-training a text transformer directly on the navigation task (see Appendix B.3). DistillBERT [Sanh al., 2019] is used for o(n,)).
Table 4 shows the results on the full graph, evaluating on (5, 10, 20) step tasks, for both navigation and sentence search. Figure 2 shows example trajectories of the trained agent. The first thing to note that the overall navigation and sentence search performance of our methods is high. The 2018 Wikipedia graph we use for evaluation contains over 5 million articles, over 38 million nodes and 387 million edges. On this graph (which we generalize to from the previous year's graph) our best method can find an article 20 steps away 92.2% percent of the time and can locate it given just single sentence of that article 90.2% the time. This compares favorably with a similar evaluation performed in Nogueira and Cho [2016], where their WebNav approach achieved 12.5% success rate for 16 step tasks on a 12M node graph. Compared to the performance of our method on the smaller 200k graph, see that performance has greatly improved. most likely due to the addition of orders of magnitude more training data. In particular we see that sentence search performance on 20-step improves greatly from 34.6% best performance of 90.2%.
Additionally, in all cases, our learned embeddings perform better than using the fixed features. derived from large language models. In general, feed-forward policies perform best, except for 20 step navigation tasks. For longer trajectories, the Transformer policy network achieves slightly better performance, while on sentence search, the feed-forward model is consistently superior.
Table 4: Full graph navigation (38M nodes) Success rate (%)
Navigation
Sentence Search
Embedding + Policy
5
10
20
5
10
20
RoBERTA + Feed-forward
85.5
80.1
71.5
91.2
88.9
77.5
RoBERTA + Transformer
85.3
88.3
87.9
81.6
75.4
70.9
Embed train (ours) Feed-forward
96.1
94.1
89.8
96.3
92.8
90.2
Embed train (ours) + Transformer
93.5
90.6
92.2
93.9
86.3
79.7

---

5,4 Application to fact verification
We now evaluate the ability of our navigation approach to select evidence on the FEVER development set [Thorne et al., 3018] with results shown in Table 5. The primary metric used is F1 @top5 but we also give precision and recall. Paired with a basic retrieval (BM25) and re-ranker (TF-IDF), the approach obtains a respectable F1 of 0.46. If we remove our navigation component then this drops substantially to 0.36, demonstrating its utility. Swapping to a more powerful re-ranker (BigBird) boosts the F1 to 0.731, which is competitive with the state-of-the-art (FEVER leaderboard [2022] rank #6; rank #1 Fl is 0.799). We also compare to a leading approach [Stammbach, 2021] that similarly relies on the BigBird re-ranker, with our approach having a significantly better F1 score.
Table 5: Results on the FEVER benchmark (evidence retrieval only). The first two rows show the effect of adding our navigation scheme to the simple BM25 retrieval and TF-IDF re-ranker combination. Switching to a more powerful re-ranker (BigBird) results in a significant boost in Fl score, surpassing Stammbach [2021] who also use BigBird [Zaheer et al., 2020].
Method
Precision @5
R
F1 @
BM25 + TF-IDF [Thoree et al., 2018]
0.33
0.40
0.36
BM25 RFBC (Ours) + TF-IDF
0.38
0.55
0.46
BM25 + RFBC (Ours) + BigBird
0.71
0.75
0.73
Stammbach [2021]
0.26
0.94
0.41
Blansas Beiig
Ery excelnsy
Vintiasr Nahus
1stD Teaseing Scaedeee
Ryossasao deeade
PlAco (attematica)
cacapayaica
140
1333
Champtos
Cornestratice
2la0
3: Gpeace
202led
21 producs (buttnass
aopadcee 1223
(1)
Sydiew C1
ted len
51 5itt
medianal
2082222
91. call aignaling
peojactics
11: octonns 2epics
212 sageiteca nastasatica)
L22 of lide
11: Panction (atologg)
Nedierai Scant
22:
12: PetesEtality ard actuality
sntection
15r
15: Anctest
14: Creratiie
Ardul-
Gene
13: Avctest
191 Srace atocetace
Palloepphy
131 0el1 intolony)
Ford
23.
Asziant dcaada
21:
23: Palloaopiy
201 Rallyo
Figure 2: Example navigation trajectories in the 38M node Wikipedia graph. The start and target nodes are shown in the first two rows. Parentheses indicate paragraph block (zero-indexed) within article. Note that in cases where the agent fails to find the target node (cols & 3), it visits ones that are very close by.
2-2alar stacced an actrasz.
Solecun contaces the bozze
Srown Quanezadep'e MaL pepuiiona eftyy
The Rozid Stade Center descuced co bulldding.
Che 2-121A
List of plance con as recole
isz Stapard
Jeta lcomn ubode baland)
cce Rocid Ccada becoar
Zilasan
Ciute (111a]
Pezeuseeayy Haade Iedieel
Vield Trab Cester (1871-2301
Testede nor Rost Trips ang.
prpeloes 1ill de U.B. mean lade
York
and the bated math poplise
dettery at
trade
fodd Trade
3: The Nettles 194
3: List of plants boour to
3: Dax Shepard
3: John Brom Oliids Jsland)
E1 Den Morld Teate Center
11 List
plasia kauss
21 Dus Rejasi
Buions sily
21 Daar Mari4 Trase (1)
2: Li3E 22 plance tacur,
las
atom University
4: Mor14
(585e Oe0242 (4)
(fibe)
planty
1. 20222an
7: Peovidence Sbada 1eland
11 (t0 Ror-4 Teace Decter (2)
plancs
2033dan sodeeace
Tattls 127
1: 28579 (f1lm)
1: FroetSencs, 2325a 12land
51 058 R6254 Texce Center (3)
11- Nepreen
w-1th 11)
314 De Nmth 7-.4) Deninn 11)
13: 5a321an AN38E220
7. Bolarza
tax Stapas
13: Re20508000,
352 006 Nodis :11da Oeniat
Figure 3: Successful navigation trajectories on the FEVER [TTornee et al., 2018] evaluation set. Rows from top: claim to be verified; starting node (from BM25); ground truth target (not visible to agent); target node text; agent trajectory.
9

---

A possible explanation is that their approach overwhelms the re-ranker with all possible hyperlinks whereas, navigation being inherently sparse. our model presents more refined set for re-ranking, We note that our approach: (a) is significantly simpler than many top ranked approaches and (b) selects evidence over much larger set than the curated version of Wikipedia used in FEVER (38M vs 5M). Examples of successful navigation traces are shown in Figure 3.
5.5 Application to question answering
Finally, we present results on another downstream task where navigation helps. In particular, we consider the task of finding correct evidence passage for open domain question answering. We use the Natural Question (NQ) open-domain dataset presented in Lee ct al. [2019]. Since we target navigating to the exact evidence passage required to answer the question, we use recall @ 11,2,3,4,5 for finding the gold evidence passage as our metric. More commonly the metric marks a retrieved passage to be correct if it contains the answer string, but this causes lot of false positives, e.g. the answer string appears in a totally irrelevant context.
Table 6: Results on the Natural Questions open domain benchmark (evidence retrieval only). Third and fourth rows show the effect of adding our navigation scheme to the simple BM25 retrieval and BigBird re-ranker. First row is a reference re-training of state-of-the-ar method on our setup.
Recall@1 1
Recall@2
Recall@3
Recall@4
RocketQA [Qu et al., 2021]
32.7
43.8
51.7
58.3
62.5
BM25
11.1
17.3
21.8
24.9
27.3
BM25 BigBird ReRank
22.2
30.2
35.1
38.7
41.2
BM25 + RFBC (Ours) + BigBird ReRank Improvement
31.6
41.3
46.6
49.8
51.6
+42.3%
+36.7%
+32.7%
+28.7%
+25.2%
The results are tabulated in Table 6. Paired with a basic retrieval (BM25) and re-ranker (BigBird), the approach obtains a respectable Recall of 31.6. If we remove our navigation component then this drops substantially to 22.2, demonstrating its utility. As a reference, we also ran state-of-the-ar system RocketQA [Qu et al., 2021] on our setup and evaluated it using our harder metric. It is worthwhile to note that our approach (a) is significantly simpler than state-of-the-ar approaches like RocketQA which employ 4 stages of dual-encoder and cross-attention models, and (b) selects evidence over a larger set than the commonly used preprocess Wikipedia passages (38M vs 21M).
Discussion
We have presented a simple and effective scheme for navigating a large Wikipedia graph that is applicable to more general web navigation problems. We show that behavioral cloning of random trajectories is viable approach to learning both entity embeddings and a navigation policy. When applied to the fact verification task on FEVER dataset and the open-domain question answering task on NQ dataset, they offer highly competitive performance, whilst being complementary to existing approaches. Another advantage worth highlighting is that the navigating agent provides provenance on how it arrived at the relevant evidence, which many other methods (like dense passage retrieval) do not provide. One limitation of our approach when we move from Wikipedia to the wider Internet that our scheme relies on good target encoder. For navigation and our downstream tasks, there was clear ground-truth target node available training, but in other settings this might not be the case. Another limitation is that we require a re-rau re-ranker to decide on the final retrieved sentence, but ideally the agent would decide for itself when it has reached the correct node.
References
A. Asai, K. Hashimoto, H. Hajishirzi, R. Socher, and C. Xiong. Learning retrieve reasoning paths over wikipedia graph for question answering. In International Conference on Learning Representations, 2020. URL httpsts:::// httpp/reeeee..e//frrrrftr
D. Chen, A. Fisch, J. Weston, and A. Bordes. Reading wikipedia to answer open-domain questions. CoRR, J 2017.
10

---

H. Dai. R. Singh, B. Dai, C. Sutton, and D. Schuurmans. Learning discrete energy energy-based models via auxiliary-variian varriabl local exploration. Advances in Neural Information Processing Systems, 2020.
R. Das, S. Dhuliawala, M. Zaheer, L. Vilnis, I. Durugkar, A. Krishnamurthy, A. J. Smola, and A. McCallum. Go for walk and arrive at the answer: Reasoning over paths knowledge bases using reinforcement learning. CoRR. abs/ 171 , 2017.
L. Espeholt, H. Soyer, R. Munos, K. Simonyan, V. Mnih, T. Ward, Y. Doron, V. Firoiu, T. Harley, Dunning, S. Legg, and K. Kavukcuoglu. Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. ArXiv, abs/1802.01561, 2018.
C. Fu, T. Chen, M. Qu, W. Jin, and X. Ren. Collaborative policy learning for open knowledge graph reasoning. CoRR, htts/1999.0000 2019.
L. He, B. Shao, Xiao, Y. Li, T.-Y. Liu, E. Chen, and H. Xia. Neurally-guided semantic navigation in knowledge graph. IEEE Transactions on Big Data, 8(3):607-615, 2022.
Ho, A. Jain, and Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840 2020.
Hofstätter, Althammer, M. Schröder, M. Sertkan, and A. Hanbury. Improving efficient neural ranking models with cross-architecture knowledge distillation. CoRR, abs/2010.02666, 2020.
V. Karpukhin, B. Oguz, S. Min, L. Wu, S. Edunov, D. Chen, and W. Yih. Dense passage retrieval for open-domain question answering. CoRR, abs/2004.04906, 2020.
D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. CoRR, abs/ abss/441.6698/ 2014.
D. Kingma and M. Welling, Auto-encoding variational bayes. CoRR, abs/1312.61 14, 2013.
A. Lazaridou, E. Gribovskaya, W. Stokowiec, and N. Grigorev. Internet-augmented language models through few-shot prompting for open-domain question answering, 2022.
leaderboard. FEVER development set leaderboard. https://competiitee cotpaampttiiiioooooodollaa.bb codalab corglab.org/
competitions/ itteeiittiooo/181441141111 18814#results, 2022.
K. Lee, M.-W. Chang, and K. Toutanova. Latent retrieval for weakly supervised open domain question answering. In Proceedings of the 57th Annual Meeting of the Association for Compulational Linguistics, pages 6096, 01 2019. doi: 10.18653/v1/P19-1B 1612.
X. V. Lin, R. Socher, and C. Xiong. Multi-hop knowledge graph reasoning with reward shaping. CoRR, abs/1 10568, 2018.
Y. Liu, M. Out, N. Goyal, J. Du, M. Joshi, D. Chen, O. Levy, M. Lewis, L. Zettlemoyer, and
V. Stoyanov. Roberta: A robustly optimized BERT pretraining approach. CoRR, abs/1907.11692. 2019.
R. Nakano. J. Hilton, S. Balaji, Wu, L. Ouyang, C. Kim, C. Hesse, S. Jain, V. Kosaraju, W. Saunders, X. Jiang, K. Cobbe, T. Eloundou, G. Krueger, K. Button, M. Knight, B. Chess, and J. Schulman. Webgpt: Browser-assisted question-answering with human feedback. CoRR, abs/21 12.09332, 2021.
R. Nogueira and K. Cho. Webnav: A new large-scale task for natural language based sequential decision making. CoRR, abs//602..225 602.02261, 2016.
Y. Qu, Y. Ding. J. Liu, K. Liu, R. Ren, X. Zhao, D. Dong, H. Wu, and H. Wang. Rocketqa: An optimized training approach to dense passage retrieval for open-domain question answering. CoRR, abs/2010.08191. 2020.
Y. Qu, Ding, J. Liu, Liu, R. Ren, X. Zhao, D. Dong, H. Wu, and Wang. Rocketqa: An optimized training approach to dense passage retrieval for open-domain question answering. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 5835-5847, 2021.
11

---

S. Robertson and H. Zaragoza. The probabilistic relevance framework: Bm25 and beyond. Foun- dations and Trends@) Information Retrieval, 3(4):333-38) 2009. ISSN 1554-0669. doi: 10.1561/1500000019 URL htRt://p://d http:::/dxxx.dood doi. wttpdd/.......o...ooo.oo org/10. 1561/150000009.
V. Sanh, L. Debut, J. Chaumond, and T. Wolf. Distilbert, distilled version of bert: smaller, faster, cheaper and lighter. ArXiv, abs/1910.01 108, 2019.
S. J. Semnani and M. Pandey. Revisiting the open-domain question answering pipeline. CoRR, abs/2009.00 00999, 2020.
Y. Shen, J. Chen, P.S. Huang, Y. Guo, and J. Gao. M-walk: Learning to walk over graphs using monte carlo tree search. Advances in Neural Information Processing Systems, 31, 2018.
D. Stammbach. Evidence selection as a token-level prediction task. In Proceedings of the Fourth Workshop on Fact Extraction and VERification (FEVER), pages 14-20, Dominican Republic, Nov. 2021. Association for Computational Linguisties. doi: 10.18653/v1/2021.eee feverr- 1.2. URL https: htt.aaattoooooorrr2222111111 fever-1.2.
D. Stammbach and G. Neumann. Team DOMLIN: Exploiting evidence enhancement for the FEVER shared task. In Proceedings the Second Workshop on Fact Extraction and VERification (FEVER), pages 105-109, Hong Kong, China, Nov. 2019, Association for Computational Linguistics. doi: 118865//1//D19666
URL https: http:///aaaaaaaloooooooooo arg/D19-6616
A. Talmor and J. Berant. The web as knowledge-base for answering complex questions. CoRR, abs/1803.06643 2018.
J. Thorne, A. Vlachos, C. Christodouulppoulss,, and A. Mittal. FEVER: a large-scale dataset for fact extraction and VERification. In Association for Computational Linguistics; dataset released under Apache license., June 2018.
I. Turc, M. Chang, K. Lee, and K. Toutanova. Well-read students learn better: The impact of student initialization on knowledge distillation. CoRR, abs/1908.08962, 2019. URL http: //arxiv. org/ abs/1908. 08962.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
L. Wang, Y. Li, Ó. Aslan, and O. Vinyals. Wikigraphs: A wikipedia text knowledge graph paired dataset. CoRR, (bs//2107.0955, 2021.
R. West and J. Leskovec. Human wayfinding in information networks. In WWW, page 619-628, 2012a.
R. West and J. Leskovec. Automatic versus human navigation information networks. ICWSM, 2012b.
R. West, J. Pineau, and D. Precup. Wikispeedia: An online game for inferring semantic distances be- tween concepts. In Proceedings of the 21 International Joint Conference on Artificial Intelligence (IJCAI), 2009.
W. Xiong, T. Hoang, and Wang. Deeppath: reinforcement learning method for knowledge graph reasoning. CoRR, abs/1 abs/1700.006690 2017.
M. Yasunaga. Leskovee, and Liang. Linkbert: Pretraining language models with document links. CoRR, abs/2203. 15827, 2022.
Q. Ye, B. Wu, and B. Wang. Distance distribution and average shortest path length estimation in real-world networks. In International Conference on Advanced Data Mining and Applications, pages 322-333. Springer, 2010.
M. Zaheer, G. Guruganesh, K. A. Dubey, J. Ainslie, C. Alberti, S. Ontanon, P. Pham, A. Ravula. Q. Wang, L. Yang, et al. Big bird: Transformers for longer sequences. Advances in Neural Information Processing Systems, 13:17783-17297, 2020.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either the supplemental material or as a URL)? [Yes] The paper and supplemental provide full details on how to reproduce the simple approach. The datasets used are all public.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] appendix.
(c) Did you report error bars (e-g.. with respect the random seed after running experi- ments multiple times)? [N/A] Our experiments are on large datasets and thus did not require multiple runs.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [No] The experiments were proprietary infrastructure on which is hard to estimate the total amount of compute.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] See Thorne et al. reference.
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "qGlQr2TfQ58", "reviewer": "Reviewer_ewnP", "summary": "This paper focuses on the problem of web navigation. The authors proposed to train an agent which can navigate a large Wikipedia graph. They first generate sampled trajectories on the Wikipedia graph based on different methods (e.g. random forward trajectories, reverse trajectories, shortest paths). With these sampled trajectories, the behavioral cloning (i.e. supervised learning) method is adopted to train the model. The experiments show that the proposed method is not only able to efficiently navigate Wikipedia graph but also have competitive performance on the fact verification task.", "questions": "* If RL is adopted after behavioral cloning (i.e. RFBC+RL in Table 2), what's the performance?\n* What are the training details, e.g. hardware, and training time?\n* line 301, table 2 -> table 4?", "limitations": "The authors have discussed the limitation of this work.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "(1) Strengths\n* The proposed method works well on navigation task and obtains competitive performance on the fact verification task.\n* This paper is generally well written.\n\n(2) Weaknesses\n* Nogueira and Cho (2016)  is the most relevant work. The proposed method WebNav in Nogueira and Cho (2016) only gets 12.5% success rate, while the proposed method in this paper obtains more than 90% success rate in a similar setting. The reason for this large difference of performance is not explained or discussed in the experiments.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JK6Wc-6yIsO", "reviewer": "Reviewer_J6Fp", "summary": "In this paper, the authors study the web navigation problem. They propose behavioral cloning of the random trajectory method on Wikipedia graphs. They further apply their method to the FEVER verification task. Their experiments show that their method is effective in learning entity embeddings and a navigation policy. It also succeeds in a competitive performance in the verification task. ", "questions": "Please refer to the major weaknesses mentioned above. ", "limitations": "Yes, they mentioned two limitations of their work. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1) The proposed method is more effective than the baseline methods and scalable to large Wikipedia graphs. \n2) The extensive analysis of results and limitations of the study are presented.\n\nWeaknesses:\nMajor:\n1)  The proposed trajectories are very intuitive and lack novelty. They simply use random walks with the probabilities being decided based on neighboring vertices.  \n2) The proposed method is only compared with random and greedy methods, not other state-of-the-art methods. Hence, it is difficult to measure effectiveness.\n3) A comprehensive efficiency analysis would be helpful. Comparison between the running times of the proposed methods and other methods would give a better understanding of the method.\n\nMinor: \n1) There are some typing issues. For example, on page 8, line 301, \"Table 2\" should be \"Table 4\". \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2I2_ruR0Kqd", "reviewer": "Reviewer_L8iM", "summary": "The paper presents a web navigation agent that learns to reach target webpages by hopping hyperlinks. The paper uses Transformer-based models that encode the local content and learn to select the link the agent moves to next. This model is trained by behavior cloning of randomly sampled trajectories. The authors show that this approach provides improved performance on navigation and fact verification benchmarks.", "questions": "- I wonder if the authors have insights into why RL performs more poorly than the proposed RFBC (Table 2)?\n- Suggestion for related work discussion: there is a larger body of existing works in machine learning for Wikipedia hyperlink graphs, which may be worth discussing -- e.g. https://arxiv.org/abs/2203.15827 (Transformer language model that predicts hyperlinked pages from the current page), https://arxiv.org/abs/1911.10470 (QA model that predicts hyperlinked pages). The main difference of the proposed work from these papers seems that it focuses on longer-horizon navigation with a target in consideration.\n", "limitations": "- The authors discusses the limitation in the paper. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The proposed system is clean, and performs better than existing systems on navigation and fact verification benchmarks \n- Good execution - the paper conducts various ablation studies such as different navigation setups and different design choices of the method (trajectory sampling, policy features, etc.) \n\nWeaknesses\n- This might be due to the presentation of the paper, but the technical novelty or contribution appears somewhat limited to me after reading the paper. The method seems to be a fairly simple application of existing techniques such as Transformer encoder and behavioral cloning training. The experiments also seem not quite offering significant insights or takeaways for the Neurips community. It would be really helpful if the authors could crisply clarify the main contribution with respect to existing works, e.g. is it a new methodology, or a new empirical finding (if so, what might be the impact to the research community), or an improved performance (if so, what exact difference from prior works is enabling the improved performance)?\n- The navigation experiments are only conducted on a Wikipedia graph, which is smaller than the real-world web", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept