Graphhopper: Multi-hop Scene Graph Reasoning for Visual Question Answering

Visual Question Answering (VQA) is a challenging task that involves understanding and reasoning over two data modalities, i.e., images and natural language. Given an image and a free-form question which formulates a query about the presented scene—the issue is for the algorithm to find the correct answer.

VQA has been studied from the perspective of scene and knowledge graphs [6, 33], as well as vision-language reasoning [1, 10]. To study VQA, various real-world data sets, such as the VQA data set [4, 24], have been generated. It has been argued that, in the VQA data set, many of the apparently challenging reasoning tasks can be solved by an algorithm through exploiting trivial prior knowledge, and thus by shortcuts to proper reasoning (e.g., clouds are white or doors are made of wood). To address these shortcomings, the GQA dataset [17] has been developed. Compared to other real-world datasets, GQA is more suitable for evaluating reasoning abilities since the images and questions are carefully filtered to make the data less prone to biases.

Plenty of VQA approaches are agnostic towards the explicit relational structure of the objects in the presented scene and rely on monolithic neural network architectures that process regional features of the image separately [2, 39]. While these methods led to promising results on previous datasets, they lack explicit compositional reasoning abilities, which results in weaker performance on more challenging datasets such as GQA. Other works [15, 31, 34] perform reasoning on explicitly detected objects and interactive semantic and spatial relationships among them. These approaches are closely related to the scene graph representations [19] of an image, where detected objects are labeled as nodes and relationships between the objects are labeled as edges. In this work, we aim to combine VQA techniques with recent research advances in the area of statistical relation learning on knowledge graphs (KGs). KGs provide human-understandable, structured representations of knowledge about the real world via collections of factual statements. Inspired by multi-hop reasoning methods on KGs such as [8, 12, 38], we propose Graphhopper, a novel method that models the VQA task as a path-finding problem on scene graphs. The underlying idea can be summarized with the phrase: Learn to walk to the correct answer. More specifically, given an image, we consider a scene graph and train a reinforcement learning agent to conduct a policy-guided random walk on the scene graph until a conclusive inference path is obtained. In contrast to purely embedding-based approaches, our method provides explicit reasoning chains that lead to the derived answers. To sum up, our major contributions are as follows.

Moreover, we are the first group to conduct experiments and publish the code on generated scene graphs for the GQA dataset.¹ The remainder of this work is organized as follows. We review related literature in the next section. Section 3 introduces the notation and describes the methodology of Graphhopper. Section 4 and Sect. 5 detail an experimental study on the benchmark dataset GQA. Furthermore, through a rigorous study using both manually-curated ground-truth and generated scene graphs, we examine the reasoning capabilities of Graphhopper. We conclude in Sect. 6.

Visual Question Answering: Various models have been proposed that perform VQA on both real-world [4, 17] and artificial datasets [18]. Currently, leading VQA approaches can be categorized into two different branches: First, monolithic neural networks, which perform implicit reasoning on latent representations obtained from fusing the two data modalities. Second, multi-hop methods that form explicit symbolic reasoning chains on a structured representation of the data. Monolithic network architectures obtain visual features from the image either in the form of individual detected objects or by processing the whole image directly via convolutional neural networks (CNNs). The derived embeddings are usually scored against a fixed answer set along with the embedding of the question obtained from a sequence model. Moreover, co-attention mechanisms are frequently employed to couple the vision and the language models allowing for interactions between objects from both modalities [2, 5, 20, 40, 41]. Monolithic networks are among the dominant methods on previous real-world VQA datasets such as [4]. However, they suffer from the black-box problem and possess limited reasoning capabilities with respect to complex questions that require long reasoning chains (see [7] for a detailed discussion).

Explicit reasoning methods combine the sub-symbolic representation learning paradigm with symbolic reasoning approaches over structured representations of the image. Most of the popular explicit reasoning approaches follow the idea of neural module networks (NMNs) [3] which perform a sequence of reasoning steps realized by forward passes through specialized neural networks that each correspond to predefined reasoning subtasks. Thereby, NMNs construct functional programs by dynamically assembling the modules resulting in a question-specific neural network architecture. In contrast to the monolithic neural network architectures described above, these methods contain a natural transparency mechanism via functional programs. However, while NMN-related methods (e.g., [14, 26]) exhibit good performance on synthetic datasets such as CLEVR [18], they require functional module layouts as additional supervision signals to obtain good results. Closely related to our method is the Neural State Machine (NSM) proposed by [16]. NSM’s underlying idea consists of first constructing a scene graph from an image and treating it as a state machine. Concretely, the nodes correspond to states and edges to transitions. Then, conditioned on the question, a sequence of instructions is derived that indicates how to traverse the scene graph and arrive at the answer. In contrast to NSM, we treat path-finding as a decision problem in a reinforcement learning setting. Concretely, we outline in the next section how extracting predictive paths from scene graphs can be naturally formulated in terms of a goal-oriented random walk induced by a stochastic policy that allows the approach to balance between exploration and exploitation. Moreover, our framework integrates state-of-the-art techniques from graph representation learning and NLP. This paper only considers basic policy gradient methods, but more sophisticated reinforcement learning techniques will be employed in future works.

Statistical Relational Learning: Machine learning methods for KG reasoning aim at exploiting statistical regularities in observed connectivity patterns. These methods are studied under the umbrella of statistical relational learning (SRL) [27]. In recent years, KG embeddings have become the dominant approach in SRL. The underlying idea is that graph features that explain the connectivity pattern of KGs can be encoded in low-dimensional vector spaces. In the embedding spaces, the interactions among the embeddings for entities and relations can be efficiently modeled to produce scores that predict the validity of a triple. Despite achieving good results in KG reasoning tasks, most embedding-based methods have problems capturing the compositionality expressed by long reasoning chains. This often limits their applicability in complex reasoning tasks. Recently, multi-hop reasoning methods such as MINERVA [8] and DeepPath [38] were proposed. Both methods are based on the idea that a reinforcement learning agent is trained to perform a policy-guided random walk until the answer entity to a query is reached. Thereby, the path finding problem of the agent can be modeled in terms of a sequential decision making task framed as a Markov decision process (MDP). The method that we propose in this work follows a similar philosophy, in the sense that we train an RL agent to navigate on a scene graph to the correct answer node. However, a conceptual difference is that the agents in MINERVA and DeepPath perform walks on large-scale knowledge graphs exploiting repeating statistical patterns. Thereby, the policies implicitly incorporate approximate rules. In addition, instead of free-form processing questions, the query in the KG reasoning setting is structured as a pair of symbolic entities. That is why we propose a wide range of modifications to adjust our method to the challenging VQA setting.

The task of VQA is framed as a scene graph traversal problem. Starting from a hub node that is connected to all other nodes, an agent sequentially samples transitions to neighboring nodes on the scene graph until the node corresponding to the answer is reached. In this way, by adding transitions to the current path, the reasoning chain is successively extended. Before describing the decision problem of the agent, we introduce the notation that we use throughout this work.

Notation: A scene graph is a directed multigraph where each node corresponds to a scene entity which is either an object associated with a bounding box or an attribute of an object. Each scene entity comes with a type that corresponds to the predicted object or attribute label. Typed edges specify how scene entities are related to each other. More formally, let \(\mathcal {E}\) denote the set of scene entities and consider the set of binary relations \(\mathcal {R}\). Then a scene graph \(\mathcal {SG} \subset \mathcal {E} \times \mathcal {R} \times \mathcal {E} \) is a collection of ordered triples (s, p, o) - subject, predicate, and object. For example, as shown in Fig. 1, the triple (motorcycle-1, has_part, tire-1) indicates that both a motorcycle (subject) and a tire (object) are detected in the image. The predicate has_part indicates the relation between the entities. Moreover, we denote with \(p^{-1}\) the inverse relation corresponding to the predicate p. For the remainder of this work, we impose completeness with respect to inverse relations in the sense that for every \((s, p, o) \in \mathcal {SG}\) it is implied that \((o, p^{-1}, s) \in \mathcal {SG}\).

Environment. The state space of the agent \(\mathcal {S}\) is given by \(\mathcal {E} \times \mathcal {Q}\) where \(\mathcal {E}\) are the nodes of a scene graph \(\mathcal {SG}\) and \(\mathcal {Q}\) denotes the set of all questions. The state at time t is the entity \(e_t\) at which the agent is currently located and the question Q. Thus, a state \(S_t \in \mathcal {S}\) for time \(t \in \mathbb {N}\) is represented by \(S_t = \left( e_t, Q\right) \). The set of available actions from a state \(S_t\) is denoted by \(\mathcal {A}_{S_t}\). It contains all outgoing edges from the node \(e_t\) together with their corresponding object nodes. More formally, \(\mathcal {A}_{S_t} = \left\{ (r,e) \in \mathcal {R} \times \mathcal {E} : S_t = \left( e_t, Q\right) \wedge \left( e_t,r,e\right) \in \mathcal {SG}\right\} \,\). Moreover, we denote with \(A_t \in \mathcal {A}_{S_t}\) the action that the agent performed at time t. We include self-loops for each node in \(\mathcal {SG}\) that produce a NO_OP-label. These self-loops allow the agent to remain at the current location if it reaches the answer node. Furthermore, the introduction of inverse relations allows agent to transit freely in any direction between two nodes (Fig. 2).

The environments evolve deterministically by updating the state according to previous action. Formally, the transition function at time t is given by \(\delta _t({S_t},A_t) := \left( e_{t+1}, Q\right) \) with \(S_t = \left( e_{t}, Q \right) \) and \(A_t = \left( r, e_{t+1}\right) \).

Auxiliary Nodes: In addition to standard entity relation nodes present in a scene graph, we introduce a few auxiliary nodes (e.g. hub node). The underlying rationale for the inclusion of auxiliary nodes is that they facilitate the walk for the agent or help to frame the QA-task as a goal-oriented walk on the scene graph. These additional nodes are included during run-time graph traversal, but they are ignored during the compile time such as when computing node embedding. For example, we add a hub node (hub) to every scene graph which is connected to all other nodes. The agent then starts the scene graph traversal from a hub with global connectivity. Furthermore for a binary question, we add YES and NO nodes to the scene entities that correspond to the final location of the agent. The agent can then transition to either the YES or the NO node.

Question and Scene Graph Processing. We initialize words in Q with GloVe embeddings [29] with dimension \(d=300\). Similarly we initialize entities and relations in \(\mathcal {SG}\) with the embeddings of their type labels. In the scene graph, the node embeddings are passed through a multi-layered graph attention network (GAT) [36]. Extending the idea from graph convolutional networks [22] with a self-attention mechanism, GATs mimic the convolution operator on regular grids where an entity embedding is formed by aggregating node features from its neighbors. Relations and inverse relations between nodes allows context to flow in both ways through GAT. Thus, the resulting embeddings are context-aware, which makes nodes with the same type, but different graph neighborhoods, distinguishable. To produce an embedding for the question Q, we first apply a Transformer [35], followed by a mean pooling operation.

Finally, since we added auxiliary YES and NO nodes to the scene graph for binary questions, we train a feedforward neural network to classify query-type (i.e., questions that query for an object in the depicted scene) and binary questions. This network consists of two fully connected layers with ReLU activation on the intermediate output. We find that it is easy to distinguish between query and binary questions (e.g., query questions usually begin with What, Which, How, etc., whereas binary questions usually begin with Do, Is, etc.). Since our classifier achieves 99.99% accuracy we will ignore the error in question classification in the following discussions.

Policy. We denote the agent’s history until time t with the tuple \(H_t = \left( H_{t-1}, A_{t-1}\right) \) for \(t \ge 1\) and \(H_0 = hub\) along with \(A_0 = \emptyset \) for \(t = 0\). The history is encoded via a multilayered LSTM [13] where \(\mathbf {a}_{t-1} = \left[ \mathbf {r}_{t-1},\mathbf {e}_{t}\right] \in \mathbb {R}^{2d}\) corresponds to the embedding of the previous action with \(\mathbf {r}_{t-1}\) and \(\mathbf {e}_{t}\) denoting the embeddings of the edge and the target node into \(\mathbb {R}^{d}\), respectively. The history-dependent action distribution is given by where the rows of \(\mathbf {A}_t \in \mathbb {R}^{\vert \mathcal {A}_{S_t} \vert \times d}\) contain latent representations of all admissible actions. Moreover, \(\mathbf {Q} \in \mathbb {R}^{d}\) encodes the question Q. The action \(A_t = (r,e) \in \mathcal {A}_{S_t}\) is drawn according to \(\text {categorical}\left( \mathbf {d}_t\right) \). Equations (1) and (2) induce a stochastic policy \(\pi _{\theta }\), where \(\theta \) denotes the set of trainable parameters.

Rewards and Optimization. After sampling T transitions, a terminal reward is assigned according to We employ REINFORCE [37] to maximize the expected rewards. Thus, the agent’s maximization problem is given by where \(\mathcal {T}\) denote the set of training questions. During training the first expectation in Eq. (4) is substituted with the empirical average over the training set. The second expectation is approximated by the empirical average over multiple rollouts. We also employ a moving average baseline to reduce the variance. Further, we use entropy regularization with parameter \(\lambda \in \mathbb {R}_{\ge 0}\) to enforce exploration. During inference, we do not sample paths but perform a beam search with width 20 based on the transition probabilities given by Eq. (2).

Additional details on the model, the training and the inference procedure along with sketches of the algorithms, and a complexity analysis can be found in the supplementary material.

In this section we introduce the dataset and detail the experimental protocol.

As outlined before, VQA is a challenging task, and there is still a significant performance gap between state-of-the-art VQA methods and human performance on challenging, real-world datasets such as GQA (see [17]). Similar to other existing methods, our architecture involves multiple components, and it important to be able to analyse the performance of the different modules and processing steps in isolation. Therefore we first present the results of our experiments on manually curated, ground-truth scene graphs provided in the GQA dataset and compare the performance of Graphhopper against NSM and humans. This setting allows us to isolate the noise from the visual perception component and quantify our methods’ reasoning capabilities. Subsequently, we present the results with our own generated scene graphs.

Reproducing NSM: [15] proposed the state of the art method named NSM for VQA. NSM is the conceptually most similar method, as it also exploits the scene graph reasoning for VQA. We consider NSM to be our baseline method for comparison. However, their approach to reasoning is different from ours. To compare the reasoning ability of our method with the same generated scene graph, we tried to reproduce NSM, as the code for NSM is not open-sourced. We have used the available parameters from [15] and the implementation from [9].

We have proposed Graphhopper, a novel method for visual question answering that integrates existing KG reasoning, computer vision, and natural language processing techniques. Concretely, an agent is trained to extract conclusive reasoning paths from scene graphs. To analyze the reasoning abilities of our method, we conducted a rigorous experimental study on both manually curated and generated scene graphs. Based on the manually curated scene graphs we showed that Graphhopper reaches human performance. Moreover, we find that, on our own automatically generated scene graph, Graphhopper outperform another state-of-the-art scene graph reasoning model with respect to all considered performance metrics. In future works, we plan to combine scene graphs with common sense knowledge graphs to further enhance the reasoning abilities of Graphhopper.