\section{Introduction}
Localizing activities in videos  \cite{regneri2013grounding,yuan2016temporal,gavrilyuk2018actor,feng2018video,feng2019spatio} is an important topic in multimedia information retrieval.
However, in realistic scenario, YouTube videos normally contain complicated background contents, and cannot be directly indicated by a pre-defined list of action classes.
To address this problem, query-based moment localization is proposed recently \cite{gao2017tall,anne2017localizing} and attracts increasing interests from the multimedia community \cite{liu2018cross,zhang2019exploiting}.
It aims to ground the most relevant video segment according to a given sentence query. This task is challenging because most part of video contents are irrelevant to the query while only a short segment matches the sentence. Therefore,
video and sentence information need to be deeply incorporated to distinguish the fine-grained details of different video segments and perform accurate segment localization.

\begin{figure}[t]
    \centering
    \includegraphics[width=0.48\textwidth]{figure/introduction6.pdf}
    \caption{Given a query and an untrimmed video, CSMGAN considers cross-modal relation for highlighting relevant instances (brown rectangles), and self-modal relation for correlating sequential elements (red rectangle) and distinguishing components near the boundary (green rectangle).}
    \label{fig:introduction}
    \vspace{-15pt}
\end{figure}

Most existing methods \cite{liu2018attentive,chen2018temporally,zhang2019cross,yuan2019find,yuan2019semantic} for this task focus on learning the cross-modal relations between video and sentence. Specifically, they develop attention based interaction mechanisms to enhance the video representation with sentence information.
Meanwhile, few algorithms \cite{chen2017msrc,zhang2019cross} attempt to learn the self-modal relations. For example,
Zhang \textit{et al.} \cite{zhang2019cross} leverage self-attention to capture long-range semantic dependencies just in video encoding.
However, the cross- and self-modal relations are never jointly investigated in a joint framework for this task.
As shown in Figure \ref{fig:introduction}, for the video modality, each frame should not only obtain information from its associated words in the query to highlight relevant frames (brown rectangles), but also need to correlate these highlighted frames to infer the sequential activity (red rectangle). At the same time, as the adjacent frame (green rectangle) near the boundary shows different visual appearance, such self-modal relation also contributes to distinguishing the segment boundaries for more precise localization.
Similarly, for the query modality, a better understanding of sentence can be acquired in conjunction with both frames and other words. Such cases motivate us to propose a joint framework for modelling both cross- and self-modal relations.

In this paper, we develop a novel cross- and self-modal graph attention network (CSMGAN) for query-based moment localization, which recasts this task as an end-to-end, message passing based joint graph information fusion procedure. The joint graph consists of a cross-modal relation graph (CMG) and a self-modal relation graph (SMG), and represents both video frames and sentence words as nodes. Specially, in each joint graph layer, CMG first establishes the edges between each word-frame pair for cross-modal information passing, where the directed pair-wise relations are efficiently captured by a heterogeneous attention mechanism. Subsequently, SMG is designed to capture the complex self-modal relations by establishing the edges within each modality.
The combination of CMG and SMG makes it possible to obtain more contextual representations by correlating highlighted cross-modal instances with sequential elements.
Moreover, by stacking multiple layers to recursive propagate messages over the joint graph, our CSMGAN can capture higher-level relationships among multi-modal representations, and comprehensively integrates the localization information for precise moment retrieval.

Besides, traditional methods \cite{zhang2019man,yuan2019semantic,wang2019temporally,mithun2019weakly,yuan2019find,chen2019semantic} adopt RNN for sentence query embedding.
However, they fail to explicitly consider the multi-granular textual information, such as specific phrases which are crucial to understanding the sentence. To capture the fine-grained query representations, we build a hierarchical structure to understand the query at three levels: word-, phrase- and sentence-level. These hierarchical representations are then merged to stand for a more informative understanding of the sentence query.

In summary, the main contributions of our work are:
\vspace{-5pt}
\begin{itemize}
    \item We present a cross- and self-modal graph attention network (CSMGAN), which is made up of cross- and self-modal graph for localizing desired moments. To the best of our knowledge, it is the first time that a joint framework is proposed to consider both cross- and self-modal relations for query-based moment localization.

    \item We design a hierarchical structure to capture the fine-grained sentence representation at three different levels: word-level, phrase-level and sentence-level.

    \item We conduct experiments on Activity Caption and TACoS datasets and our CSMGAN outperforms the state-of-the-arts with clear margins.

\end{itemize}

\vspace{-10pt}
\section{Related works}

\noindent \textbf{Query-based localization in images.} Early works of localization task mainly focus on localizing the image region corresponding to a language query. They first generate candidate image regions using image proposal method \cite{ren2015faster}, and then find the matched one with respect to the given query. Some works \cite{mao2016generation,hu2016natural,rohrbach2016grounding} try to extract target image regions based on description reconstruction error or probabilities. There are also several studies \cite{yu2016modeling,chen2017query,chen2017msrc,zhang2018grounding} considering incorporating contextual information of region-phrase relationship into the localization model. \cite{wang2016structured} further models region-region and phrase-phrase structures. Some other methods exploit attention modeling in queries, images, or object proposals \cite{endo2017attention,deng2018visual,yu2018mattnet}.

\begin{figure*}[t]
    \centering
    \includegraphics[width=1.0\textwidth]{figure/pipeline5.pdf}
    \caption{Illustration of our proposed CSMGAN. We first utilize a self-attention based video encoder and a hierarchical sentence encoder to extract corresponding features. Then, a jointly cross- and self-modal graph is devised for multi-modal interaction. In the joint graph, words and frames both represented as nodes first construct CMG to mine cross-modal relations and update their states through ConvGRU. Then the nodes are reorganized as SMG to model the self-modal relationships and updated for the next layer graph input. At last, we conduct multi-modal integration and perform moment localization.}
    \label{fig:pipeline}
    \vspace{-8pt}
\end{figure*}

\noindent\textbf{Query-based moment localization in videos.}
Different from traditional video retrieval \cite{dong2018predicting, dong2019dual}, it is a new task introduced recently \cite{gao2017tall,anne2017localizing}, which aims to localize the most relevant video segment from a video with text descriptions. Traditional methods \cite{liu2018attentive,gao2017tall} sample candidate segments from a video first, and subsequently integrate query with segment representations via a matrix operation.
To further mine the cross-modal interaction more effectively, some works \cite{xu2019multilevel,chen2019semantic,ge2019mac,zhang2019learninga} integrate the sentence representation with those video segments individually, and then evaluated their matching relationships.
For instance, Xu \textit{et al.} \cite{xu2019multilevel} introduce a multi-level model to integrate visual and textual features earlier and further re-generate queries as an auxiliary task.
Chen \textit{et al.} \cite{chen2018temporally} capture the evolving fine-grained frame-by-word interactions between video and query to enhance the video representation understanding.
Recently, other works \cite{chen2018temporally,wang2019temporally,zhang2019cross,zhang2019man,yuan2019semantic,mithun2019weakly} propose to directly integrate sentence information with fine-grained video clip, and predict the temporal boundary of the target segment by gradually merging the fusion feature sequence over time.
Zhang \textit{et al.} \cite{zhang2019man} model relations among candidate segments produced from a convolutional neural network with the guidance of the query information.
To modulate temporal convolution operations, Yuan \textit{et al.}\cite{yuan2019semantic} and Mithun \textit{et al.} \cite{mithun2019weakly} introduce the sentence information as a critical prior to compose and correlate video contents.
Although these methods achieve relatively superior performances by capturing cross-modal information, they ignore to utilize the self-modal relation which is complementary to the cross-modal relation.
Different from them, we propose a cross- and self-modal graph attention network to jointly consider both cross- and self-modal relations. The successive cross- and self-modal graphs enable our model to capture much higher-level interactions.

\noindent \textbf{Graph neural networks.}
Graph neural network (GNN) \cite{scarselli2008graph} is an extension for recursive neural networks and random walk based models for graph structured data. As a follow-up work,  Gilme \textit{et al.} \cite{gilmer2017neural} further adapt GNN to sequential outputs with a learnable message passing module.
As GNN is wildly used in sequential information processing, in this paper, we design a novel GNN module for cross- and self-modal relations mining. Different from original GNN, we represent edge weights by an attention mechanism and aggregate messages with a gate function. Moreover, we utilize a ConvGRU \cite{ballas2015delving} layer for node state updating.

\vspace{-7pt}
\section{The proposed CSMGAN framework}

\subsection{Overview}
Given an untrimmed video $\bm{V}$ and a sentence query $\bm{Q}$, the task aims to determine the start and end timestamps $(s, e)$ of specific video segment referring to the sentence query. Formally, we represent the video as $\bm{V}=\{\bm{v}_t\}_{t=1}^{N_v}$ frame-by-frame, where $\bm{v}_i$ is the $i$-th frame in the video and $N_v$ is the total frame number. We also denote the given sentence query as $\bm{Q}=\{\bm{q}_n\}_{n=1}^{N_q}$ word-by-word, where $\bm{q}_n$ is the $n$-th word.
With the training set $\{V,Q,(s,e)\}$, we aim to learn to predict the most relevant video segment boundary $(\hat{s}, \hat{e})$ which conforms to the sentence query information.

We present our method CSMGAN in Figure \ref{fig:pipeline}.
First of all, a self-attention based video encoder and a hierarchical sentence encoder are utilized to extract contextual sentence and video embeddings.
Then, in order to better interact multi-modal features, we capture both cross- and self-modal relations by developing a jointly cross- and self-modal graph network.
Specially, in the joint graph, a cross-modal relation graph (CMG) establishes weighted edges between frame-word pairs to pass the message flows across the modalities. Following it, a self-modal relation graph (SMG) reorganizes the previous nodes and edges to model the relationships within each modality. With the self-relation complemented to the cross-relation, the joint graph can perform richer interaction of multi-modalities. Moreover, with multiple layers of such joint graph, the CSMGAN can capture higher-order relationships.
At last, the enhanced two modal representations are integrated to score different candidate video segments by a moment localization module.
\vspace{-8pt}

\begin{figure*}[t]
    \centering
    \includegraphics[width=1.0\textwidth]{figure/edge5.pdf}
    \caption{Illustration of our cross-modal relation graph and self-modal relation graph. Both two graphs compute attention matrices to stand for the attention weights on the corresponding edges. Each node aggregates the messages from its neighbor nodes in an edge-weighted manner and updates its state with both aggregated message and current state through ConvGRU. We apply a gate function in cross-modal graph and consider the temporal position for all nodes in self-modal graph.}
    \label{fig:edge}
    \vspace{-8pt}
\end{figure*}

\subsection{Video and Sentence Encoder}
\textbf{Video encoder.}
Following \cite{zhang2019cross}, we first extract the frame-wise features by a pre-trained C3D network \cite{tran2015learning}, and then employ a self-attention \cite{vaswani2017attention} module to capture the long-range dependencies among video frames.
Considering the sequential characteristic in video, a bi-directional GRU \cite{chung2014empirical} is further utilized to capture the contextual information in time series. We denote the encoded representation as $\hat{\bm{V}}=\{\hat{\bm{v}}_t\}_{t=1}^{N_v} \in \mathbb{R}^{N_v \times d}$, where the $\hat{\bm{v}}_t \in \mathbb{R}^{1 \times d}$ is the feature of the $t$-th frame.\\
\textbf{Sentence encoder.}
Most previous works generally adopt recurrent neural networks to model the contextual information for each word during the sentence encoding process. However, considering the query ``He continues playing the instrument", it is reasonable to focus on the phrase ``continues playing" instead of each single word to obtain more detailed temporal clues for precise localization. Therefore, to fully mine the guiding information, we develop a hierarchical structure with word-, phrase-, and sentence-level feature extracting for sentence query encoding.

We first generate the word-level features for the query by using the Glove word2vec embedding \cite{pennington2014glove}, and denote them as $\bm{Q}^w=\{\bm{q}_n^w\}_{n=1}^{N_q} \in \mathbb{R}^{N_q \times d_g}$, where $N_q$ is the number of words in the sentence and $d_g$ is the Glove embedding dimension.
To discover the potential phrase-level features, we apply 1D convolutions on the word-level features with different window sizes. Specially, at each word location, we compute the inner product of the word feature vectors with convolution filters of three kinds of window sizes, which captures unigram, bigram and trigram features.
To maintain the sequence length after convolution process, we zero-pad the sequence vectors when convolution window size is larger than one.
The output of the $n$-th word location with window size $k \in \{1,2,3\}$ is formulated as follows:
\begin{equation}
    \bm{q}_{n,k}^p = \text{tanh}(\text{Conv1d}(\bm{q}^w_{n:n+k-1}))  \in \mathbb{R}^{1 \times d_g},
\end{equation}
where $\text{Conv1d}(\cdot)$ operates on the windowed features with $d_g$ kernels. $\bm{q}_{n,k}^p$ is the phrase-level feature corresponding to $n$-th word location with window size $k$. To find the most contributed phrase at each word location, we then apply max-pooling to obtain the final phrase-level feature $\bm{Q}^p=\{\bm{q}_n^p\}_{n=1}^{N_q} \in \mathbb{R}^{N_q \times d_g}$ by:
\begin{equation}
    \bm{q}_n^p = \text{max}(\bm{q}_{n,1}^p, \bm{q}_{n,2}^p, \bm{q}_{n,3}^p), n \in \{1,2,...,N_q\}.
\end{equation}
After obtaining the phrase-level feature vector $\bm{Q}^p$, we encode them with a bi-directional GRU network to produce the sentence-level feature $\bm{Q}^s =\{\bm{q}_n^s\}_{n=1}^{N_q} \in \mathbb{R}^{N_q \times d_g}$. At last, we concat these three-level features and leverage another bi-directional GRU network to integrate them by:
\begin{equation}
    \hat{\bm{Q}} = \text{Bi-GRU}(\text{Concat}[\bm{Q}^w,\bm{Q}^p,\bm{Q}^s]) \in \mathbb{R}^{N_q \times d}.
\end{equation}
Here the contextual query representation $\hat{\bm{Q}}=\{\hat{\bm{q}}_n\}_{n=1}^{N_q}$ is projected from the length $3d_g$ to $d$ to keep same dimension as video representation.
After the hierarchical embedding structure, the given query can obtain comprehensive understanding and provide robust representation for later localization.

\subsection{Jointly Cross- and Self-modal Graph}
As shown in Figure \ref{fig:edge}, we develop a jointly cross- and self-modal graph to capture both cross- and self-modal information for multi-modal representation interaction. Specially, the joint graph consists of two subgraphs: cross-modal relation graph (CMG) and self-modal relation graph (SMG). In the CMG, each frame (word) integrates information from the other modality according to the cross-modal attentive relations. Subsequently, in the SMG, the self-attentive contexts within modality are further captured. By stacking $L$ layers of such joint graphs, we can comprehensively perform the interaction between two modalities. Next, we will describe the detailed process of each subgraph in the $l$-th joint graph layer.

\subsubsection{Cross-Modal Relation Graph}
\ \\
\textbf{Graph construction.} In the CMG, we build a directed graph as $\mathcal{G}_{cross}=(\mathcal{V}_{cross}, \mathcal{E}_{cross})$, where $\mathcal{V}_{cross} = \bm{V} \cup \bm{Q} = \{\bm{v}_t\}_{t=1}^{N_v} \cup \{\bm{q}_n\}_{n=1}^{N_q}$, containing all frames and words as nodes, and $\mathcal{E}_{cross}$ is the edge set between all word-frame node pairs, namely edge $\bm{e}_{(n,t)}=(\bm{q}_n,\bm{v}_t)$ represents the cross-modal interaction from word node $\bm{q}_n$ to frame node $\bm{v}_t$ and $\bm{e}_{(t,n)}=(\bm{v}_t,\bm{q}_n)$ denotes the reverse interaction.
To initialize the input features for each node,
we set the encoded video representation of nodes $\bm{V}$ and query representation of nodes $\bm{Q}$ as initial hidden states: $\text{H}^{0}(\bm{V})=\hat{\bm{V}}$ and $\text{H}^{0}(\bm{Q})=\hat{\bm{Q}}$ in the CMG, respectively.
\\
\textbf{Cross-modal attention.} To update CMG, the first step is to compute the attention weights between frame and word nodes $\bm{V}$, $\bm{Q}$ which represent their pair-wise relations. As in Figure \ref{fig:edge} (a), the attention weight on each pair-wise edge can be computed as below:
\begin{equation}
    \bm{e}^l = (\text{H}^{l-1}(\bm{Q})\cdot\bm{W_q})(\text{H}^{l-1}(\bm{V})\cdot\bm{W_v})^T \in \mathbb{R}^{N_q \times N_v}.
    \label{eq:embedding}
\end{equation}
$\text{H}^{l-1}(\bm{Q})$ and $\text{H}^{l-1}(\bm{V})$ are the feature vectors for word and frame nodes in $(l-1)$-th layer. As $\bm{Q}$ and $\bm{V}$ come from different feature distributions, $\bm{W_q},\bm{W_v} \in \mathbb{R}^{d \times d}$ are linear projection used to embed the heterogeneous nodes \cite{hu2020heterogeneous} into a joint latent space instead of direct computing in the node embedding space. Each row of $\bm{e}^l$ denotes the similarity of all frame nodes $\bm{V}$ to the specific word node ${\bm{q}_n}$, and each column represents the similarity of all word nodes $\bm{Q}$ to the specific frame node ${\bm{v}_t}$.
\\
\textbf{Node message aggregation.} For message aggregation, we aggregate the assigned features for each node from its neighbors in an edge-weighted manner \cite{velivckovic2017graph}.
Here we introduce Figure \ref{fig:edge} (b) which aggregates all neighboring word nodes $\{\bm{q}_n\}_{n=1}^{N_q}$ for frame node ${\bm{v}_t}$, and Figure \ref{fig:edge} (c) performs the reverse aggregation process. For word node $\bm{q}_n$ in $\bm{Q}$, the assigned feature to ${\bm{v}_t}$ is:
\begin{equation}
    \bm{M}^l_{(n,t)} = \text{Softmax}(\bm{e}^l_{(n,t)})\text{H}^{l-1}(\bm{q}_n) \in \mathbb{R}^{1\times d}.
\end{equation}
The softmax procedure makes the sum of all word nodes' attention vectors
to one.
However, not all neighborhood nodes share same semantic importance, several neighborhood nodes contribute less to target node. For example, word ``the" in the query is not informative enough to the frame, and the frames only containing one stationary basketball should have less significance to highlight ``playing basketball".
To emphasize informative neighborhood nodes and weaken inessential ones, we apply a learnable gate function $G(\cdot)$ to measure the confidence of each neighbor message by:
\begin{equation}
    \bm{g}^l_{(n,t)} = G(\bm{M}^l_{(n,t)}) = \sigma(\bm{M}^l_{(n,t)}\bm{W}_g+\bm{b}_g) \in (0,1),
\end{equation}
where $\sigma(\cdot)$ is the sigmoid function, $\bm{W}_g\in\mathbb{R}^{d\times 1}$ and $\bm{b}_g\in\mathbb{R}^{1}$ are the trainable weight parameter and bias. Then, we can aggregate the gated messages for node ${\bm{v}}_t$ by:
\begin{equation}
    \bm{M}_t^l = \sum_{n=1}^{N_q} \bm{g}^l_{(n,t)}\bm{M}_{(n,t)}^l \in \mathbb{R}^{1 \times d}.
\end{equation}
With the help of such gate mechanism, the irrelevant aggregated messages are filtered and messages from relevant node pairs are further enhanced.\\
\textbf{Node representation update.}
After aggregating the information from all neighbors, node $\bm{v}_t$ gets a new state by taking into account its current state and its received messages $\bm{M}_t^l$. To preserve the sequential information conveyed in the prior state and the messages, we do not utilize a simple element-wise matrix addition on $\text{H}^{l-1}(\bm{v}_t)$ and $\bm{M}_t^l$. Instead, we leverage a ConvGRU \cite{ballas2015delving} layer to update the node state with two inputs by:
\begin{equation}
    \bar{\text{H}}^{l}(\bm{v}_t) = \text{ConvGRU}(\text{H}^{l-1}(\bm{v}_t), \bm{M}_t^l) \in \mathbb{R}^{1 \times d}.
\end{equation}
This ConvGRU is proposed as a convolutional counterpart to original fully connected GRU \cite{cho2014learning}. In the same way, the representations for nodes of two modalities can be updated.

\subsubsection{Self-Modal Relation Graph}
\ \\
\textbf{Graph construction.}
Following CMG, our SMG aims to capture the complex self-modal relations within each modality. It only connects edges between word-word or frame-frame node pairs. Like CMG, we denote this graph as $\mathcal{G}_{self}=(\mathcal{V}_{self}, \mathcal{E}_{self})$, where $\mathcal{V}_{self}$ is the node set containing all frames and words, and each edge in edge set $\mathcal{E}_{inter}$ indicates the self-modal relation.
\\
\textbf{Self-modal attention.}
Figure \ref{fig:edge} (d) and (e) depict the process of self-modal information passing. Given a node $\bm{v}_t$ in Figure \ref{fig:edge} (d) for example, we first compute a self-attention matrix to stand for the relations from its neighbor nodes to itself. To better correlate the relevant nodes, in this stage, we consider both the semantic information as well as the temporal position in the sequence of each node. We argue that the temporal index of the node is critical to our localization task as less attention should be given to distant frame (word) nodes, even if they are semantically similar to the current node. Inspired by Transformer’s positional encoding \cite{vaswani2017attention}, we denote the position encoding for each node as:
\begin{equation}
    \text{PE}(\bm{v}_t) = \left\{
             \begin{array}{cl}
              {\rm sin}(t/10000^{j/d}),  & \text{if}\; j \;  \text{is even}  \\ {\rm cos}(t/10000^{j/d}),  & \text{if}\;  j \;  \text{is odd}  \\
             \end{array},
\right.
\end{equation}
where $\text{PE}(\bm{v}_t) \in \mathbb{R}^{1 \times d}$, and $j$ varies from 1 to $d$ dimension. With the positional and semantic information combined, the self-attention matrix can be calculated by:
\begin{equation}
\bar{\bm{e}}^l_t = (\bar{\text{H}}^{l}(\bm{v}_t)+\alpha\text{PE}(\bm{v}_t)) (\bar{\text{H}}^{l}(\bm{V}) + \alpha\text{PE}(\bm{V}))^T,
\end{equation}
where $\bar{\bm{e}}^l_t \in \mathbb{R}^{1 \times N_v}$ calculates the similarity for all frame nodes $\bm{V}$ to current nodes $\bm{v}_t$, $\alpha$ is to balance the two types of information. \\
\textbf{Node message aggregation.}
The aggregation process can be formulated as following:
\begin{equation}
\bar{\bm{M}}_t^l = \text{Softmax}(\bar{\bm{e}}^l_t)\bar{\text{H}}^{l}(\bm{V}) \in \mathbb{R}^{1 \times d}.
\end{equation}
Here we only aggregate the information from $\bar{\text{H}}^{l}(\bm{v}_t)$ as positional information is designed for auxiliary similarity computing.
\\
\textbf{Node representation update.}
Similar to CMG, we also exploit a ConvGRU layer to update the node state and get the output as:
\begin{equation}
    \text{H}^{l}(\bm{v}_t) = \text{ConvGRU}(\bar{\text{H}}^{l}(\bm{v}_t),\bar{\bm{M}}_t^l) \in \mathbb{R}^{1 \times d}.
\end{equation}
At last, following the same procedure, we can get the final representations for all nodes of each modality in the $l$-th jointly cross- and self-modal graph layer as $\text{H}^{l}(\bm{V}) \in \mathbb{R}^{N_v \times d}$ and $\text{H}^{l}(\bm{Q}) \in \mathbb{R}^{N_q \times d}$. Subsequently, these two modal features will be feed to the $(l+1)$-th joint graph layer as input.

\subsection{Multi-Modal Integration Module}
After $L$ joint graph layer, we can get mutual sentence-aware video representation $\tilde{\bm{V}}=\{\tilde{\bm{v}}_t\}_{t=1}^{N_v}=\text{H}^{L}(\bm{V})$ and video-aware sentence representation $\tilde{\bm{Q}}=\{\tilde{\bm{q}}_n\}_{n=1}^{N_q}=\text{H}^{L}(\bm{Q})$. To integrate both two representations,
we first compute the cosine similarity between each pair of word feature $\tilde{\bm{q}}_n$ and frame feature $\tilde{\bm{v}}_t$ as:
\begin{equation}
    c_{n,t} = \frac{(\tilde{\bm{v}}_t)(\tilde{\bm{q}}_n\bm{W}_c)^T}{\parallel \tilde{\bm{v}}_t \parallel_2 \parallel \tilde{\bm{q}}_n\bm{W}_c \parallel_2},
\end{equation}
where $\bm{W}_c \in \mathbb{R}^{d \times d}$ is the linear parameter. $c_{n,t}$ is used to further extract the implicit query clues for each frame.
Once we get the similarity scores between entire words $\{\tilde{\bm{q}}_n\}_{n=1}^{N_q}$ and a specific frame $\tilde{\bm{v}}_t$,
we integrate the query information for frame $\tilde{\bm{v}}_t$ as:
\begin{equation}
    \bm{h}_t = \sum_{n=1}^{N_q} \text{Softmax}(c_{n,t}) \tilde{\bm{q}}_n \in \mathbb{R}^{1 \times d},
\end{equation}
where $\bm{h}_t$ is aggregated with the query representation relevant to the $t$-th frame. We concat such aggregated query feature vectors with frame features to get the final multi-modal semantic representations $\bm{f} = \{\bm{f}_t\}_{t=1}^{N_v}$, where $\bm{f}_t = \text{Concat}[\tilde{\bm{v}}_t,\bm{h}_t] \in \mathbb{R}^{1 \times 2d}$.

\subsection{Moment Localization}
We first apply a bi-directional GRU network on $\bm{f}$ to further absorb the contextual evidences in temporal domain. To predict the target video segment, we pre-define a set of candidate moments $\Phi_t = \{(\hat{s}_{t, i}, \hat{e}_{t, i})\}_{i=1}^{N_{\Phi}}$ with multi-scale windows \cite{yuan2019semantic} at each time $t$, where $N_{\Phi}$ is the number of moments at current time-step. Then, we need to score these candidate moments and predict the offsets $\hat{\delta}_t = \{(\hat{\delta}_{t,i}^s, \hat{\delta}_{t,i}^e)\}_{i=1}^{N_{\Phi}}$ of them relative to the ground-truth. In details, we produce the confidence scores $cs_t = \{cs_{t,i}\}_{i=1}^{N_{\Phi}}$ for these moments at time $t$ by a Conv1d layer:
\begin{equation}
    cs_{t,i} = \sigma(\text{Conv1d}(\bm{f}_t)) \in (0,1),
\end{equation}
where $\sigma(\cdot)$ is the sigmoid function. The temporal offsets are predicted by another Conv1d layer:
\begin{equation}
    (\hat{\delta}_{t,i}^s, \hat{\delta}_{t,i}^e) = \text{Conv1d}(\bm{f}_t).
\end{equation}
Therefore, the final predicted moment $i$ of time $t$ can be presented as $(\hat{s}_{t,i}+\hat{\delta}_{t,i}^s, \hat{e}_{t, i}+\hat{\delta}_{t,i}^e)$.
\\
\textbf{Training.}
We first compute the IoU (Intersection over Union) score $IoU_{t,i}$ between each candidate moment $(\hat{s}_{t,i}, \hat{e}_{t, i})$ with the ground truth $(s_t, e_t)$. If $IoU_{t,i}$ is larger than an IoU threshold $\tau$, we treat this candidate moment as a positive sample.
We adopt an alignment loss to learn the confidence scoring rule for candidate moments, where the moments with higher IoUs will get higher confidence scores. The alignment loss function can be formulated as follows:
\begin{equation}
    \mathcal{L}_{align} = - \frac{1}{N_vN_{\Phi}} \sum_{t=1}^{N_v}\sum_{i=1}^{N_{\Phi}} IoU_{t,i} log(cs_{t,i}) + (1-IoU_{t,i}) log(1-cs_{t,i}).
\end{equation}
Since parts of the pre-defined candidates are coarse in boundaries, we only fine-tune the localization offsets of positive moment samples by a boundary loss:
\begin{equation}
    \mathcal{L}_{b} = \frac{1}{N_{pos}} \sum_j^{N_{pos}} \mathcal{R}_1(\hat{\delta}_j^s-\delta_j^s) + \mathcal{R}_1(\hat{\delta}_j^e-\delta_j^e),
\end{equation}
where $N_{pos}$ denotes the number of positive moments, and $\mathcal{R}_1$ is the smooth L1 loss. Therefore, the joint loss can be represented as:
\begin{equation}
    \mathcal{L} = \mathcal{L}_{align} + \beta \mathcal{L}_b,
\end{equation}
where $\beta$ is utilized to control the balance.
\\
\textbf{Inference.}
We first rank all candidate moments according to their predicted confidence scores, and then adopt a non-maximum suppression (NMS) to select ``Top $n$" moments as the prediction.

\section{EXPERIMENTS}
\subsection{Datasets and Evaluation Metrics}

\noindent\textbf{Activity Caption.}
Activity Caption \cite{krishna2017dense} contains 20k untrimmed videos with 100k descriptions from YouTube. The videos are 2 minutes on average, and the annotated video clips have much larger variation, ranging from several seconds to over 3 minutes. Since the test split is withheld for competition, following public split, we adopt ``val 1” as validation subset, ``val 2” as our test subset.

\noindent \textbf{TACoS.}
TACoS \cite{regneri2013grounding} is widely used on this task and contain 127 videos. The videos from TACoS are collected from cooking scenarios, thus lacking the diversity. They are around 7 minutes on average. We use the same split as \cite{gao2017tall}, which includes 10146, 4589, 4083 query-segment pairs for training, validation and testing.

\noindent \textbf{Evaluation Metrics.}
Following previous works \cite{gao2017tall,yuan2019semantic}, we adopt ``R@n, IoU=m” as our evaluation metrics. The “R@n, IoU=m” is defined as the percentage of at least one of top-n selected moments having IoU larger than m.
Following \cite{liu2018attentive,yuan2019semantic,wang2019temporally}, we choose the evaluation criteria “R@n, IoU=m” with $\text{n} \in \{1, 5\}, \text{m} \in \{0.3, 0.5, 0.7\}$ and “R@n, IoU=m” with $\text{n} \in \{1, 5\}, \text{m} \in \{0.1, 0.3, 0.5\}$ for Activity Caption and TACoS datasets, respectively.

\begin{table}[t!]
    \small
    \centering
    \caption{Performance compared with previous methods on the Activity Caption dataset.}
    \label{tab:compare1}
    \setlength{\tabcolsep}{1.5mm}{
    \begin{tabular}{c|cccccc}
    \hline \hline
    \multirow{2}*{Method} & R@1 & R@1 & R@1 & R@5 & R@5 & R@5 \\
    ~ & IoU=0.3 & IoU=0.5 & IoU=0.7 & IoU=0.3 & IoU=0.5 & IoU=0.7 \\ \hline
    MCN \cite{anne2017localizing} & 39.35 & 21.36 & 6.43 & 68.12 & 53.23 & 29.70 \\

    TGN \cite{chen2018temporally} & 45.51 & 28.47 & - & 57.32 & 43.33 & - \\
    CTRL  \cite{gao2017tall} & 47.43 & 29.01 & 10.34 & 75.32 & 59.17 & 37.54 \\
    ACRN \cite{liu2018attentive} & 49.70 & 31.67 & 11.25 & 76.50 & 60.34 & 38.57 \\
    QSPN \cite{xu2019multilevel} & 52.13 & 33.26 & 13.43 & 77.72 & 62.39 & 40.78 \\
    CBP \cite{wang2019temporally} & 54.30 & 35.76 & 17.80 & 77.63 & 65.89 & 46.20 \\
    SCDM \cite{yuan2019semantic} & 54.80 & 36.75 & 19.86 & 77.29 & 64.99 & 41.53 \\
    ABLR \cite{yuan2019find} & 55.67 & 36.79 & - & - & - & - \\
    GDP \cite{chenrethinking} & 56.17 & 39.27 & - & - & - & - \\
    CMIN \cite{zhang2019cross} & 63.61 & 43.40 & 23.88 & 80.54 & 67.95 & 50.73 \\ \hline
    \textbf{CSMGAN} & \textbf{68.52} & \textbf{49.11} & \textbf{29.15} & \textbf{87.68} & \textbf{77.43} & \textbf{59.63} \\ \hline
    \end{tabular}}
\end{table}

\begin{table}[t!]
    \small
    \centering
    \caption{Performance compared with previous methods on the TACoS dataset.}
    \label{tab:compare2}
    \setlength{\tabcolsep}{1.5mm}{
    \begin{tabular}{c|cccccc}
    \hline \hline
    \multirow{2}*{Method} & R@1 & R@1 & R@1 & R@5 & R@5 & R@5 \\
    ~ & IoU=0.1 & IoU=0.3 & IoU=0.5 & IoU=0.1 & IoU=0.3 & IoU=0.5 \\ \hline
    MCN \cite{anne2017localizing} & 3.11 & 1.64 & 1.25 & 3.11 & 2.03 & 1.25 \\

    CTRL  \cite{gao2017tall} & 24.32 & 18.32 & 13.30 & 48.73 & 36.69 & 25.42 \\
    ABLR \cite{yuan2019find} & 34.70 & 19.50 & 9.40 & - & - & - \\
    ACRN \cite{liu2018attentive} & 24.22 & 19.52 & 14.62 & 47.42 & 34.97 & 24.88 \\
    QSPN \cite{xu2019multilevel} & 25.31 & 20.15 & 15.23 & 53.21 & 36.72 & 25.30 \\
    TGN \cite{chen2018temporally} & 41.87 & 21.77 & 18.90 & 53.40 & 39.06 & 31.02 \\
    GDP \cite{chenrethinking} & 39.68 & 24.14 & 13.50 & - & - & - \\
    CMIN \cite{zhang2019cross} & 32.48 & 24.64 & 18.05 & 62.13 & 38.46 & 27.02 \\
    SCDM \cite{yuan2019semantic} & - & 26.11 & 21.17 & - & 40.16 & 32.18 \\
    CBP \cite{wang2019temporally} & - & 27.31 & 24.79 & - & 43.64 & 37.40 \\
    \hline
    \textbf{CSMGAN} & \textbf{42.74} & \textbf{33.90} & \textbf{27.09} & \textbf{68.97} & \textbf{53.98} & \textbf{41.22} \\ \hline
    \end{tabular}}
    \vspace{-5pt}
\end{table}

\begin{table*}[t!]
\small
\centering
\caption{Ablation study on the Activity Caption and TACoS datasets, where the reference is our full model.}
\label{tab:ablation12}
\begin{tabular}{c|c|cccccc|cccccc}
\hline
\multirow{3}*{Components} & \multirow{3}*{Module} &  \multicolumn{6}{c|}{Activity Caption} & \multicolumn{6}{c}{TACoS} \\ \cline{3-8} \cline{9-14}
~ & ~ & R@1 & R@1 & R@1 & R@5 & R@5 & R@5 & R@1 & R@1 & R@1 & R@5 & R@5 & R@5 \\
~ & ~ & IoU=0.3 & IoU=0.5 & IoU=0.7 & IoU=0.3 & IoU=0.5 & IoU=0.7 & IoU=0.1 & IoU=0.3 & IoU=0.5 & IoU=0.1 & IoU=0.3 & IoU=0.5 \\ \hline \hline
Reference & \textbf{full} & \textbf{68.52} & \textbf{49.11} & \textbf{29.15} & \textbf{87.68} & \textbf{77.43} & \textbf{59.63} & \textbf{42.74} & \textbf{33.90} & \textbf{27.09} & \textbf{68.97} & \textbf{53.98} & \textbf{41.22} \\ \hline \hline
Encoder & \textbf{w/o HS} & 66.32 & 46.80 & 26.54 & 85.97 & 74.43 & 56.49 & 39.56 & 30.42 & 24.40 & 65.50 & 51.39 & 39.38 \\ \hline
Joint Graph & \textbf{w/o CSG} & 64.13 & 44.47 & 25.49 & 84.35 & 72.97 & 54.47 & 36.91 & 28.45 & 22.27 & 63.18 & 49.19 & 37.11 \\ \hline
\multirow{2}*{\tabincell{c}{Cross-Modal\\ Graph}} & \textbf{w/o EM} & 67.48 & 47.94 & 28.09 & 86.02 & 75.27 & 56.32 & 41.11 & 32.24 & 25.93 & 66.67 & 53.05 & 40.17 \\
~ & \textbf{w/o MG} & 67.28 & 47.39 & 28.13 & 86.46 & 74.91 & 56.47 & 40.48 & 31.66 & 25.73 & 66.39 & 52.56 & 40.21 \\ \hline
\multirow{2}*{\tabincell{c}{Self-Modal\\ Graph}} & \textbf{w/o SMG} & 66.53 & 46.62 & 27.57 & 85.68 & 73.97 & 55.68 & 39.64 & 30.86 & 24.61 & 65.10 & 50.90 & 39.11 \\
~ & \textbf{w/o PE} & 67.41 & 48.45 & 28.56 & 86.51 & 75.20 & 57.20 & 40.23 & 31.32 & 25.30 & 66.17 & 51.41 & 39.43 \\ \hline
Node Update& \textbf{w/o CG} & 67.37 & 47.51 & 28.07 & 86.06 & 75.66 & 56.96 & 40.97 & 31.96 & 25.66 & 66.42 & 52.00 & 40.04 \\
\hline
\end{tabular}
\vspace{-8pt}
\end{table*}

\subsection{Implementation Details}
For training our CSMGAN, we first resize every frame of videos to $112 \times 112$ pixels as input, and then apply a pre-trained C3D \cite{tran2015learning} to obtain 4096 dimension features. After that we apply PCA to reduce the feature dimension from 4096 to 500 for decreasing the model parameters. These 500-d features are used as the frame features in our model. Since some videos are overlong, we set the length of video feature sequences to 200 for both Activity Caption and TACoS datasets. As for sentence encoding, we utilize Glove word2vec \cite{pennington2014glove} to embed each word to 300 dimension features. The hidden state dimension of BiGRU networks is set to 512. We set $\alpha$ to 1 for positional encoding. During moment localization, we adopt convolution kernel size of [16, 32, 64, 96, 128, 160, 192] for Activity Caption, and [8, 16, 32, 64] for TACoS. We set the stride of them as 0.5, 0.125, respectively. We then set the high-score threshold $\tau$ to 0.45, and the balance hyper-parameter $\beta$ to 0.001 for Activity Caption, 0.005 for TACoS. The number of our joint graph layer is set to 2. We train our model with an Adam optimizer with leaning rate $8\times 10^{-4}, 3\times 10^{-4}$ for Activity Caption and TACoS, respectively. The batch size is set to 128 and 64 for two datasets, respectively.

\begin{figure}
    \centering
    \subfloat{\includegraphics[width=0.23\textwidth]{figure/activity.pdf}}
    \subfloat{\includegraphics[width=0.23\textwidth]{figure/tacos.pdf}}
    \caption{Effect of the number of graph layers on the Activity Caption and TACoS Datasets.}
    \label{fig:graph_layer}
    \vspace{-12pt}
\end{figure}

\subsection{Performance Comparison and Analysis}
\textbf{Activity Caption.}
Table \ref{tab:compare1} shows the performance evaluation results of our method and all comparing methods on Activity Caption dataset. Compared to the state-of-the-arts methods, our model surpasses them with clear margin on all R@1 and R@5 metrics. Specially, our method brings 5.27\% and 8.90\% absolute improvements in the strict metrics ``R@1, IoU=0.7”  and ``R@5, IoU=0.7”.

\noindent \textbf{TACoS.}
Table \ref{tab:compare2} shows the performance results of our method and all baselines on TACoS dataset.
On this challenging dataset, we find that our method still achieves significant improvements. In details, our method brings 2.30\% and 3.82\% improvements in the strict metrics``R@1, IoU=0.5”  and ``R@5, IoU=0.5”, respectively.

\noindent \textbf{Analysis.}
Specifically, the compared methods can be divided into two classes: 1) Sliding window based methods: MCN \cite{anne2017localizing}, CTRL \cite{gao2017tall}, and ACRN \cite{liu2018attentive} first sample candidate video segments using sliding windows, and directly integrate query representations with window-based segment representations via a matrix operation. They do not employ a comprehensively structure for effective cross-modal interaction, leading to relatively lower performances than other methods. 2) Cross-modal interaction based methods: TGN \cite{chen2018temporally}, QSPN \cite{xu2019multilevel}, CBP \cite{wang2019temporally}, SCDM \cite{yuan2019semantic}, ABLR \cite{yuan2019find}, GDP \cite{chenrethinking}, and CMIN \cite{zhang2019cross} integrate query representations with the whole video representations in an attention-guided manner, and can generate contextual query-guided video representation for precisely boundary localization. However, they ignore to capture the self-modal relation which helps to correlate relevant instances within each modality.
Compared to them, our method emphasizes the importance of capturing both cross- and self-modal relation during the effective integration of multi-modal feature. Our jointly cross- and self-modal graph can mine much richer and higher-level interactions, thus achieving better results than both two kinds of methods.

\subsection{Ablation Study}
In this section, we perform ablation studies to examine the effectiveness of our proposed CSMGAN. Specifically, we re-train our model with the following settings:
\begin{itemize}
    \item \textbf{w/o HS}: We first remove the hierarchical structure from the sentence encoder, and only take a bi-directional GRU to encode the sentence query.
    \item \textbf{w/o CSG}: We then discard the jointly cross- and self-modal graph to validate the importance of cross- and self-modal relations capturing in multi-modal interaction.
    \item \textbf{w/o EM}: To explore the effect of heterogeneous attention in CMG, we remove the embedding matrices in Eq. \ref{eq:embedding}, and compute the attentive matrix in the node embedding space.
    \item \textbf{w/o MG}: To further analyze the gate mechanism in CMG, we remove the gate function during the message passing in the cross-modal graph layer.
    \item \textbf{w/o SMG}: To evaluate the effect of SMG, we remove the self-modal graph, and only apply cross-modal graph for multi-modal interaction.
    \item \textbf{w/o PE}: To assess the component of SMG, we remove the positional encoding from the SMG.
    \item \textbf{w/o CG}: Finally, we replace the ConvGRU with a simple matrix element-wise addition during the node updating.

    \item \textbf{full}: The full model.
\end{itemize}

\begin{figure*}
    \centering
    \includegraphics[width=1.0\textwidth]{figure/weight_fusion.pdf}
    \caption{Visualization on the edge weights of both cross-modal graph (CMG) and self-modal graph (SMG). Left: column-wise weights of the attention matrix of different CMG layer, where the weights stands for the relations from all words to a specific frame. Right: self-attention weights of different SMG layer, where the relevant frames have higher context weights.}
    \label{fig:weight}
    \vspace{-8pt}
\end{figure*}

The ablation study conducted on Activity Caption and TACoS datasets are shown in Table \ref{tab:ablation12}. By analyzing the ablation results, we have the conclusions as follows:
\begin{itemize}
    \item First of all, our full model outperforms all the ablation models on both two datasets, which demonstrates each component is definitely helpful for this task.
    \item Compared to other ablation models, the w/o CSG model performs worst on two datasets. This means that our jointly cross- and self-modal graph takes an important role in effective multi-modal features interaction. Besides, the hierarchical structure (HS) for sentence embedding also has significant contribution to the full model.

    \item At last, almost all ablation models still yield better results than all state-of-the-arts methods. This fact demonstrates that the excellent performance of our graph based framework does not only rely on one specific key component, and our full model is robust to address this task.
\end{itemize}

To further investigate the influence on the various number of our joint graph layers, we show the impact of different layer numbers on two datasets in Figure \ref{fig:graph_layer}. We can observe that our model achieves best result when the number of layer is set to 2. Then the performance will drop if the number of layers increases. The propagated messages between the instances in cross-modality and self-modality will be accumulated if we use more graph layers, resulting in over-smoothing \cite{li2018deeper} problem, namely the representations of both video and sentence converge to the same value.

\begin{figure}
   \centering
    \includegraphics[width=0.45\textwidth]{figure/result.pdf}
    \caption{Qualitative visualization on both two datasets (top: Activity Caption, bottom: TACoS).}
    \label{fig:result}
    \vspace{-12pt}
\end{figure}

\subsection{Qualitative Results}
To qualitatively validate the effectiveness of our method, we show examples from two datasets in Figure \ref{fig:result}. Although the sentences are very diverse, our full model can still localize more accurate boundaries than CMIN. In two variant models, the w/o CSG has the most coarse boundaries because it lacks the detailed interaction of multi-modal features. The w/o HS fails to capture more contextual sentence guiding clues for localization, leading to relatively coarse boundaries. As a comparison, our full model achieves the most precise localization.

We further give a deep visualization on the cross- and self-modal relations in each joint graph layer. Specially, we first visualize the relations from all words to a specific frame in the cross-modal graph. As shown in Figure \ref{fig:weight} (left), sentence ``she begins brushing the horse while still speaking" has two activities. For the non-relevant frame, the attention weights on these eight words are more inclined to be an even distribution. But for the relevant frame, the contributed words like ``begins", ``brushing", ``still", and ``speaking" obtain higher attention weights since the described action indeed happens there. Moreover, with GNN layer increasing, the distribution of these words weights are sharper and more distinguishable. However, too many GNN layers will result in over-smoothing problem, where each frame-word pair has almost the same activation. We also plot the context weights in the self-modal graph as shown in Figure \ref{fig:weight} (right). The weights are calculated by a softmax function, and they represent the relations from surrounding frames to one specific frame. We find that frame containing ``brushing while speaking" is more relevant to the frame ``begin brushing". Although the frames near the segment boundaries are visually similar to the frames in the segment, the self-modal relation can effectively distinguish them and produce lower attention weights for such noisy frames.

\section{Conclusion}
In this paper, we propose a jointly cross- and self-modal graph attention network (CSMGAN) for query-based moment localization in video. We consider both cross- and self-modal relations in a joint framework to capture much higher-level interactions. Specially,
cross-modal relation highlights relevant components across video and sentence, and
then self-modal relation models the pairwise correlation inside each modality for
frames/words association.
Besides, we also develop a hierarchical structure for more contextual sentence understanding in a word-phrase-sentence process. The experimental results on various datasets demonstrate the effectiveness of our proposed method.

\bibliographystyle{ACM-Reference-Format}