Video as Conditional Graph Hierarchy for Multi-Granular Question Answering

Video. We extract a video at $p$ frames per second and then partition it into $K$ clips of length $L$. For each clip, we maintain a dense stream of $L$ frames to obtain the clip-level motion feature and a sparse stream of $\gamma L$ frames ($\gamma\in(0,1)$) to obtain the region and frame appearance features. In our implementation, the motion features $F_{m}=\{f_{m_{k}}\}_{k=1}^{K}$ and frame appearance features $F_{a}=\{f_{a_{t}}\}_{t=1}^{T}$ ($T=\gamma LK$) are extracted from pre-trained CNNs, specifically 3D version ResNeXt-101 (Hara, Kataoka, and Satoh 2018) for motion and ResNet-101 (He et al. 2016) for frame appearance. Importantly, we also extract $N$ RoIs’ (region of interest) appearance features $F_{r}=\{f_{r_{n}}\}_{n=1}^{N}$ along with their bounding boxes from each frame in the sparse stream, using a pre-trained object detector (Anderson et al. 2018).

After the extraction, all three types of features are projected into a $d$-dimension space. Specifically, for motion and frame appearance features, the projections are achieved by applying two respective 1-D convolution operations along the time dimension, in which the window sizes are set to 3 to consider the previous and next neighbors as contexts. For clarity, we denote the projected features as $F_{m}^{K\times d}=\{f_{m_{k}}^{d}\}_{k=1}^{K}$ for motion and $F_{a}^{T\times d}=\{f_{a_{t}}^{d}\}_{t=1}^{T}$ for frame appearance. For each object, to retain both semantic and geometric information, we jointly represent its RoI appearance $f_{r}$, bounding box location $f_{s}$, and temporal position $f_{t}$ similar to (Huang et al. 2020). The final object feature comes from concatenating the three components and projecting them into $d$-dimensions with a linear transformation followed by an ELU activation: $f_{o}=\mathrm{ELU}(W_{o}[f_{r};f_{s};f_{t}]),$ in which $[;]$ denotes concatenation and $W_{o}$ are the parameters of the linear projection. Again, for clarity, we denote the projected object features in a frame as $F_{o}^{N\times d}=\{f_{o_{n}}^{d}\}_{n=1}^{N}$.

Question. To obtain a well-contextualized word representation, we extract the token-wise sentence embeddings from the penultimate layer of a fine-tuned BERT model (Devlin et al. 2018) (refer to Appendix B for details). Similar to (Xiao et al. 2021), we further apply a Bi-GRU (Cho et al. 2014) to project the word representations into the $d$-dimension space as the visual part for convenience of cross-modal interaction. Consequently, a language query of length M is represented by $Q^{M\times d}=\{q_{m}^{d}|q_{m}=[\overrightarrow{q_{i}};\overleftarrow{q_{i}}]\}_{m=1}^{M},$ where $\overrightarrow{q_{i}}^{\frac{d}{2}}$ and $\overleftarrow{q_{i}}^{\frac{d}{2}}$ denoted the forward and backward hidden states respectively. Particularly, the last hidden state $q_{M}^{d}$ is treated as the global query representation $f_{Q}$.

In this section, we introduce QGA - the key component in our model architecture. As illustrated in Figure 3, QGA first contextualizes a set of input visual nodes $X_{\text{in}}$ in relation to their neighbors in both the semantic and geometric (realized by the geometric embeddings of the nodes) space, under the condition of a language query $Q^{M\times d}$, and then aggregates the contextualized output nodes $X_{\text{out}}$ into a single global descriptor $x_{p}$. The input nodes $X_{\text{in}}^{*\times d}=\{x_{\text{in}_{i}}\}_{i=1}^{*}$ depend on the hierarchy level; at the bottom, $X_{\text{in}}$ are the object features $F_{o}$, while at higher levels, the inputs are the outputs of QGAs at the preceding level. The dimension varies accordingly and we use * as a placeholder for the number of input nodes.

Query Condition. By condition, we pay attention to the video elements that are invoked in the questions, which is achieved by augmenting the corresponding nodes’ representations with $Q$:

where $\sigma(\cdot)$ is the softmax normalization function and ^′ indicates matrix transpose. The indices of $x$ are omitted for brevity. We expect that, through the cross-attention aggregation of the word representations with respect to the visual node $x_{in}$, the visual node’s textual correspondence will have a stronger response in the aggregation if the represented video element is mentioned in the question. As a result, the corresponding video element (represented by $x_{\text{in}}$) will be highlighted and contribute more to subsequent operations.

Graph Attention. After obtaining the augmented node representations $\hat{X}^{*\times d}=\{\hat{x}\}_{i=1}^{*}$, the edges (including self-loops) represented by the values of the adjacency matrix $A^{*\times*}$ are dynamically computed as the similarities between the node pairs:

in which the function $\phi$ denotes linear transformation with learnable parameters $W_{av}$ and $W_{ak}\in\mathbb{R}^{d\times\frac{d}{2}}$ respectively. The softmax operation normalizes each row, so that the $i^{th}$ row $A_{i}$ denotes the attention values (i.e., values of normalized dot-product) of node $i$ with regard to all the other nodes. We then apply a $H$-layer graph attention aggregation with skip-connections to refine the nodes in relation to their neighbors based on the adjacency matrix $A$:

where $W^{(h)}\in\mathbb{R}^{d\times d}$ and $\hat{X}^{(h)}$ are the parameters and outputs of the $h^{th}$-layer graph attention respectively. $\hat{X}^{(0)}$ is initialized with the query-attended node $\hat{X}$. $I$ is the identity matrix for skip connections. The final output is obtained by a last skip-connection: $X_{\text{out}}=\hat{X}+\hat{X}^{(H)}$.

Node Aggregation. To get an aggregated representation $x_{p}$ for a QGA unit, we apply self-attention pooling (Lee, Lee, and Kang 2019) over the set of output nodes:

where $W_{p}\in\mathbb{R}^{d\times 1}$ are the learnable linear mapping weights.

By the hierarchical graph structure, the video elements of different granularity can be level-wisely inferred. Besides, by the multi-level token-level query conditions, the model is capable of pinpointing the referred video elements at different granularity, and it is also flexible in handling different textual queries. In addition, by introducing the context features (i.e., $F_{a}$ and $F_{m}$), the model can make up the downside of lacking the respective global information at each level. Importantly, the model is of enhanced flexibility and interpretability, from a perspective of query-instantiated neural modular networks (Hu et al. 2018) and from a introspective analysis of the learned attention weights as our model are purely attention-based, respectively.

For multi-choice QA, we concatenate each candidate answer with the corresponding question to form a holistic query. The resulting global query feature $f_{Q}$ is fused with the final video feature $f_{V}$ via Hadamard product (a.k.a., element-wise product) $\odot$. Then, a full-connected layer with softmax is applied as classifier:

where $W_{c}\in\mathbb{R}^{d\times 1}$ and $b$ are learnable parameters. s is the prediction score. During training, we maximize the margin between the positive and negative QA-pairs (i.e., $s^{p}$ and $s^{n}$ respectively) with the hinge loss: $\mathcal{L}=\sum\nolimits_{i=1}^{|\mathcal{A}_{mc}|}\max(0,1+s_{i}^{n}-s^{p})$, where $|\mathcal{A}_{mc}|$ is the number of choices in a question.

For open-ended QA, as the number of categories (answers) are large, we empirically find that it is better to concatenate the global question feature $f_{Q}$ with the video feature $f_{V}$ before the classifier.

in which $W_{qv}\in\mathbb{R}^{2d\times d}$, $W_{c}\in\mathbb{R}^{d\times|\mathcal{A}_{oe}|}$, and $b^{|\mathcal{A}_{oe}|}$ are learnable parameters. Besides, $|\mathcal{A}_{oe}|$ is the size of the predefined answer set. During training, the optimization is achieved by minimizing the cross-entropy loss: $\mathcal{L}=-\sum\nolimits_{i=1}^{|\mathcal{A}_{oe}|}y_{i}\log s_{i}$, where $s_{i}$ is the prediction score for the $i^{th}$ sample. $y_{i}=1$ if the answer index corresponds to the $i^{th}$ sample’s ground-truth answer and 0 otherwise.

We experiment on four VideoQA datasets that challenge the various aspects of video understanding: TGIF-QA (Jang et al. 2019) features questions about action repetition, state transition and frame QA. Action repetition includes the sub-tasks of repetition counting and repeating action recognition. In this work, we experiment on the latter since the prediction of numbers are hard to explain. MSRVTT-QA and MSVD-QA mainly challenge a recognition of video elements. Their question-answer pairs are automatically generated from the respective video descriptions by (Xu et al. 2017). NExT-QA (Xiao et al. 2021) is a challenging benchmark that goes beyond superficial video description to emphasize causal and temporal multi-object interactions. It is rich in object relations in space-time (Shang et al. 2019). The dataset has both multi-choice QA and generation-based QA. In this work, we focus on the former and leave the generation-based QA for future exploration. For all datasets, we report accuracy (percentage of correctly answered questions) as the evaluation metric. Other statistical details are given in Appendix A.

We extract each video in NExT-QA, MSVD-QA and MSRVTT-QA at $p=\{6,15,15\}$ frames per second respectively. For TGIF-QA, all the frames are used. Based on the average video lengths, we uniformly sample $K=\{16,8,8,4\}$ clips for each video in the four datasets respectively, while fixing the clip length $L=16$. The sparse stream is obtained by evenly sampling with $\gamma=0.25$. For each frame in the sparse stream, we detect $N=20$ regions for NExT-QA and 10 for the others. The dimension of the models’ hidden states is $d=512$ and the default number of graph layers in QGA is $H=2$. For training, we adopt a two-stage scheme by firstly training the model with learning rate $lr=10^{-4}$ and then fine-tune the best model obtained in the $1st$ stage with a smaller $lr$, e.g., $5\times 10^{-5}$. For both stages, we train the models by using Adam optimizer with batch size of 64 and maximum epoch of 25. Other details are presented in Appendix B.

In Table 1 and Table 2, we compare our model with some established VideoQA techniques covering 4 major categories: 1) cross-attention (e.g., ST-VQA (Jang et al. 2017), PSAC (Li et al. 2019b), STA (Gao et al. 2019), MIN (Jin et al. 2019) and QueST (Jiang et al. 2020)), 2) motion-appearance memory (e.g., AMU (Xu et al. 2017), Co-Mem (Gao et al. 2018) and HME (Fan et al. 2019)), 3) graph-structured models (e.g., L-GCN²²2L-GCN’s results on NExT-QA and MSRVTT-QA are reproduced by us with the official code. (Huang et al. 2020), HGA(Jiang and Han 2020), DualVGR (Wang, Bao, and Xu 2021), GMIN (Gu et al. 2021) and B2A (Park, Lee, and Sohn 2021)) and 4) hierarchical models (e.g., HCRN (Le et al. 2020) and HOSTR (Dang et al. 2021)). The results show that our Hierarchical QGA (HQGA) model performs consistently better than the others on all the experimented datasets.

Particularly, both L-GCN and GMIN are graph-based methods that focus on leveraging object-level information (similar to us) for question-answering. However, they model the object either in a monolithic way in space-time or in trajectories. This neither reflect the hierarchical nor the compositional nature of the video elements. Furthermore, their graphs are constructed without the guidance of language queries. By filling such gaps, our model shows clear superiority to both methods on the experimented datasets.

HCRN and HOSTR are similar to us in designing hierarchical conditional architectures. Nonetheless, HCRN is limited to hierarchical temporal relations between frames, in which the relations are modeled by simple average pooling. It is helpful for identifying repeated actions and state transition of single object (see results on TGIF-QA), but it is insufficient to understand more complicated object interactions in space-time. As a result, it performs even worse than L-GCN on NExT-QA. HOSTR advances HCRN by building the hierarchy over object trajectories and adopting graph operation for relation reasoning. Yet still, it focuses merely on designing general-purpose neural building blocks and lacks the bottom-up and top-down insight (Figure 1) for VideoQA, which results in its sub-optimal model design and results.

While HCRN and HOSTR use global query representations, QueST breaks down the question into spatial and temporal components, and designs separated attention modules to aggregate information from video for question answering. It obtains good results on TGIF-QA but does not generalize well to MSRVTT-QA and MSVD-QA where the questions do not have such spatial and temporal syntactic structure. Finally, the methods HGA, DualVGR and B2A, like us, try to align words in the language query with their visual correspondences in the video. However, all of them adopt a flat way of alignment at segment level and lack the hierarchical structure, which most likely accounts for their inferiority.

We analyze our model on the validation sets of NExT-QA and MSRVTT-QA. We first conduct an ablation study on the number of graph attention layers $H$, sampled video clips $K$ and regions $N$ to find the optimal settings on the two datasets (refer to Appendix C for more details). Then, we fix the optimal settings for subsequent experiments.

Hierarchy. The top section of Table 3 shows that accuracy drops by 0.9% on both datasets when removing the QGA units at the bottom ($w/o$ $G_{O}$) ($F_{a}$ and $F_{m}$ are used as respective inputs for $G_{F}$ and $G_{C}$.). The results demonstrate the importance of modeling the static picture of object interactions. Taking away the $2nd$ level graph units ($w/o$ $G_{F}$) by directly applying $G_{C}$ over $G_{O}$’s outputs corresponding to the respective middle frames of the clips, we can observe even more drastic accuracy drops (over 1.2%) on both datasets. This results demonstrate the critical role of $G_{F}$ in modeling the short-term dynamics of object interactions. Finally, when we remove both $G_{O}$ and $G_{F}$ and apply a monolithic graph over the clips (directly using $F_{m}$ as inputs for $G_{C}$), the accuracy drops sharply by 1.5% and 2.6% on NExT-QA and MSRVTT-QA respectively. This clearly shows that only modeling clip-level information is unsatisfactory. The comparisons confirm the significance of hierarchically weaving together video elements of different levels.

Graph. The middle section of Table 3 shows that substituting the top QGA ($G_{C}$) with a sum-pooling over the corresponding input nodes ($w/o$ $G_{C}(s)$), leads to accuracy drops from HQGA of 0.68% and 0.54% on NExT-QA and MSRVTT-QA respectively. The result validates the importance of $G_{C}$ in reasoning over local, short-term dynamic interactions. Replacing the middle QGAs ($G_{F}$) with sum-poolings ($(ss)$) further degrades the performance on both datasets. The result indicates that a sum-pooling is neither sufficient in capturing the short-term dynamics of object interactions nor capable of relation reasoning over them. Thus, it evinces the strengths of both $G_{C}$ and $G_{F}$. Finally, by replacing the last (bottom) QGAs ($G_{O}$) with sum-poolings ($(sss)$), we can observe a further exacerbation of performances on the basis of the previous two ablations. The results demonstrate $G_{O}$’s superiority in capturing object relations in static frames. This experiment demonstrates the advantage of graph attention over a simple sum-pooling.

Multi-level Condition. As shown in Table 3 (bottom part), the results in the first three rows show that removing the language condition at any single level jeopardize the overall performance, indicating the necessity of injecting the query cues at multiple levels. Specially, we investigate replacing the token-wise query representations $Q$ with a global one $f_{Q}$, i.e., by concatenating $f_{Q}$ with the respective graph nodes at all levels. From the results shown in the row $w/f_{Q}$, we find that a global condition can slightly boost the performance on MSRVTT-QA compared with the model variant without any conditioning (e.g., 37.52% vs. 37.03%). However, such benefit disappears when the model is extrapolated to the scenario where the videos and questions are much more complex (e.g., NExT-QA). Finally, we conduct additional ablation studies on $F_{a}$ and $F_{m}$ that serve as global contexts to enhance the representations of graph nodes at the corresponding levels. The results show that both features help a bit to the overall performance.

Discussion. By jointly considering the ablation results of graph hierarchy and multi-level condition in Table 3, we can see that, compared with the graph hierarchy, the multi-level query condition has relatively smaller influence on the performance. We speculate that some questions are too simple to provide meaningful referring clues to the video contents (e.g., ‘what is happening’). Such questions purely rely the model to reason the video contents for answers.

Another finding is that, both the graph hierarchy and multi-level condition have relatively smaller performance gains on NExT-QA than on MSRVTT-QA. A possible reason could be that NExT-QA emphasizes causal and temporal action relations; it requires high-quality action recognition. Yet recognizing actions in such complex multiple-object scenarios remains a significant challenge in video understanding (Gu et al. 2018; Feichtenhofer et al. 2019). Our model can reason on the relations between video elements at multi-granularity levels. However, such capability seriously relies on object appearance features in its current version; the absence of region-level motion is a limitation. Our further analyses of model performances per question type on MSRVTT-QA and MSVD-QA (see Table 4) show that there are still clear gaps between action/activity recognition and object/attribute recognition in videos; the gaps remain 4.6% on MSRVTT-QA and 7.5% on MSVD-QA for ’what’ questions. A promising solution would be to jointly model both the appearance and motion for each object. As it is not the focus of this work, we leave it for future exploration.

Intriguingly, the results of our simplest model variant ($w/o$ $G_{O}\&G_{F}$) are still on par with some previous SOTAs. Such strong results can be attributed to our better data representation. Here to verify BERT, we additionally explore substituting BERT with GloVe (Pennington, Socher, and Manning 2014) and achieve 37.2% on MSRVTT-QA test set. This result confirms the advantages of BERT (38.6% vs. 37.2%) as a good contextualized representation to fulfill the multi-granular condition, e.g., the disambiguation between the male and female skaters denoted as $O_{1}$ and $O_{2}$ respectively in Figure 4 ($G_{O}$). Also, the result prompts future exploration of finetuning pre-trained vision-text architectures (Lei et al. 2021) for potential improvement of performance.

Qualitative Analysis. We show a prediction case in Figure 4 (find more examples in Appendix C). Firstly, by tracing down the self-attention pooling weights $\beta$, our model precisely finds the video contents that are relevant to the textual query, e.g., from the $6th$ video clip $C_{6}$ to its $2nd$ frame $F_{2}$, and further to the male and female skaters (denoted as $O_{1}$ and $O_{2}$ respectively in $F_{2}$). Secondly, according to the query-conditional weights $\alpha$, our model successfully differentiates the information of different granularity levels for both the video and question contents, and discriminatingly match them at the corresponding levels. For example, the nodes at high level $G_{C}$ show stronger responses to the action-related words (‘do’ and ‘back down’), whereas those nodes at the lower levels ($G_{F}$ and $G_{O}$) respond strongly to the visual objects (‘skater’). Finally, according to the learned adjacency matrices, while we construct fully-connected graphs in QGA, the learned connections are quite sparse, suggesting that our model can learn to filter out meaningless relations with respect to the query.

As shown in Figure 5 (left), a two-layer graph attention $H=2$ in each QGA unit brings the best results for both datasets. We speculate that a one-layer graph is insufficient to learn the complex relations between different video elements, while a three-layer graph may over-smooth the visual components (as we stack 3 QGAs to achieve the whole hierarchical model) and hence hurt the performance. From Figure 5 (right), we can see that $K=8$ video clips are enough to bring good performances on the validation splits of both datasets. (Yet, we empirically find that our default setting of 16 clips yield the optimal results on NExT-QA test set.). However, NExT-QA demands relative more candidate regions ($N=20$) than MSRVTT-QA ($N=10$). Such difference is reasonable as NExT-QA’s videos are relative longer with multiple objects interacted with each other.

Our model is light-weight with three stacked 2-layer graphs, and graphs at the same level share parameters. Besides, modelling video as graph hierarchy benefits time efficiency compared with previous works that use RNNs. As videos are also sparsely sampled (4-16 clips, with 4 frames per clip) so running speed is fast (see Table 6) once the features are ready. However, the overall speed (with feature extraction) could possibly be slower than those models that use only segment-level feature.

The example in Figure 6(a) shows that our model successfully predict the correct answer for the question that features both dynamic action (e.g., “bending down”) and contact action (e.g., “feed horse”). Meanwhile, the learned conditional graphs tell that our model can precisely align the query phrases of different contents with the video elements at the corresponding hierarchy level. For example, the expression “after bending down” which features dynamics is grounded at the top two levels, i.e., $G_{C}$ and $G_{F}$ that aim at capturing the interaction dynamics across frames and across clips respectively. In contrast, the expression “feed horse” which features contact action is grounded at the bottom level, i.e., $G_{O}$ that focuses on learning a static overview of the object interaction based on certain frames. Furthermore, by aligning the visual nodes in the graphs with the respective video contents, we can see that the model can spatio-temporally ground (localize) the question and answer in the video. Concretely, according to the two nodes $C_{2}$ and $C_{3}$ (in $G_{C}$) that response relatively stronger to the final video representation $V$, the model can temporally find the video clips that are relevant to the query. By tracing from $C_{3}$ through $F_{1}$ (in $G_{F}$) down to $O_{18}$ (in $G_{O}$), the model can further pinpoint the specific frame and region that are related to the answer “feed horse”.

In Figure 6(b), we show another correct prediction case where the question gives no referring hint to the video contents but generally asks the global event in the video. To study why it can answer the question, again we trace down the learned graph hierarchy. We can see that the model can accurately finds the visual elements in the video to deduce the answer “singing performance”, e.g., the singer ($O_{14}$, $O_{2}$), guitar ($O_{6}$) and other musical instruments ($O_{4}$, $O_{10}$) in frame $F_{1}$ of video clip $C_{5}$. The example demonstrates that the hierarchical architecture is able to abstract a set of low-level, local visual components into a high-level, global event even without explicit language cues.

Finally, we show a failing case in Figure 6(c). In the example, our model fails to obtain the correct answer “lie on man s stomach” but gets a negative one “hold the swing”. By analyzing the wrong prediction, we find that the model 1) incorrectly aligns the video clips $C_{4}$ and $C_{5}$ with the referring expression “fell off swing” and 2) is also distracted by the negative answer “hold the swing”. For the first problem, a further study of the video clips reveals that they are incomplete to cover the video contents corresponding to “fell off swing” which should be the contents between $C_{6}$ and $C_{7}$. We speculate that the process of “fell off” is likely transient and thus unfortunately gets missing during sampling in this case. Yet, our aforementioned study on video sampling suggests that 8 clips is enough for a overall good performance. For the second problem, we analyze it through the learned graph hierarchy. By tracing from the video clip $C_{5}$ (in $G_{C}$) through the video frame $F_{2}$ (in $G_{F}$) to the region $O_{2}$ (in $G_{O}$), we find that the region content $O_{2}$ does correspond to the distractor answer “hold the swing”. Besides, the contents of video clip $C_{5}$ are visually similar to “fell off”. Consequently, the two factors jointly lead our model to the wrong answer.

Overall, the above analyses demonstrate the effectiveness of our hierarchical conditional graph model in 1) reasoning and inferring video elements of different granularity, and 2) fine-grained matching between visual and textual contents at multi-granularity levels. Also, the model is of enhanced explanability either in interpreting the correct predictions, or in diagnosing the source of the wrong predictions.