\section{Introduction}
\IEEEPARstart{G}{iven} natural language queries, a visual grounding task aims to localize objects or regions in images or videos, which is an important task in the vision-language research field. It was originated by localizing objects in an image based on short descriptions or sentences~\cite{yu2016modeling,kazemzadeh2014referitgame} (Fig. \ref{fig:teaser}(a)). With the progress on video understanding, recent efforts have been made on referring expression in videos, such as temporal video grounding. Taking Fig. \ref{fig:teaser}(b) for an example, this video grounding task aims to localize a video segment corresponding to the given language query.

Several existing tasks are relevant to the newly proposed HC-STVG task from the task perspective, but they have a different focus.  Specifically,
\textbf{Referring Expression} aims to spatially localize the target object in an image and outputs a bounding box.
\textbf{Temporal video grounding} aims to determine the temporal boundaries of the target event in a video and thus returns a set of consecutive frames.
Compared with these two tasks, the HC-STVG task aims to localize the spatio-temporal tube of the target person described in the textual query, which is more challenging as it requires localization both spatially and temporally.
For example, the target person may appear in the video for a long time, but the interval of the event matching the description may be short. It is necessary to utilize both the textual cues (such as actions and relations with other objects) indicated in the query sentence and the visual cues shown in the video to determine the temporal boundaries.
Furthermore, compared to the \textbf{STVG} task, we only consider humans as our referent. This is out of two considerations. First, humans are specific and always the focus of all species in the videos.
Second, humans produce a wealth of action information and interact with other people or things. Therefore, the HC-STVG task requires a model to do fine-grained reasoning, which is more challenging but have more practical applications in the real world.

Grounding in both space and time domain is often required in real-world scenarios, especially for healthcare and security related applications, where the surveillance videos can be extremely long, but people only care about a specific person and his/her specific behaviors. For example, in a 24-hours monitoring video, a healthcare doctor at the nursing home may want to see how a particular older person was having his/her lunch, or a police officer may need to search for a suspect from the crowded people and locate the process when the suspect conducts a crime. In both cases, when the description is provided, the expected outputs are a sequence of bounding boxes related to the target person in the consecutive frames corresponding to the described action, i.e., a spatio-temporal tube. Unfortunately, such a video grounding setting has not been explored yet. Hence the existing methods cannot well handle this task.

In this work, we introduce a new task named Human-centric Spatio-Temporal Video Grounding (HC-STVG), which aims to localize a spatio-temporal tube of the target person in an untrimmed video given a query description. As shown in Fig. \ref{fig:teaser}(c), based on the description ‘The woman in a white apron comes to the table and puts the tray in her hands on the table’, an HC-STVG model needs to answer: which person is the target and which frames correspond to the described actions.  To the best of our knowledge, it is the first video grounding task centered on humans. There are three key challenges in our HC-STVG task:
1) It requires grounding referring expressions both spatially and temporally at the same time.
2) Multi-modality information, such as visual/textural attributes and actions, is often required for localizing a specific person, especially in a complex multi-person scene.
3) It can be difficult to determine the starting and ending frame of an action due to its dynamic nature. This task is meaningful as it involves cross-modality modeling and fine-grained reasoning.

To effectively deal with this task, we propose a new baseline method, termed Spatio-Temporal Grounding with Visual Transformers (STGVT), in which we jointly exploit multi-modality information from videos and textural descriptions by using a visual Transformer. Specifically, our STGVT method consists of four steps: After generating tube proposals from a video by linking bounding boxes in consecutive frames, our method learns the cross-modality interaction between the tube proposals and the query sentence via a Visual Transformer, which is then followed by predicting the matching tube and trimming the irrelevant frames. Although there are many vision-language datasets for the visual grounding tasks, none can support this new task. To address the issue, we contribute an HC-STVG dataset. Precisely, it consists of 5,660 video-query pairs, where 57.2\% of scenes have more than three people. Each query is a sentence with an average of 17.25 words, consisting of rich expressions related to actions and human-object interaction. Based on this new benchmark dataset, we demonstrate the effectiveness of our baseline method for the newly proposed HC-STVG task.

To summary up, the contributions of this work are three-fold:
1) We introduce a novel and challenging task, i.e., Human-centric Spatio-Temporal Video Grounding (HC-STVG), which for the first time, focuses on humans in spatio-temporal video grounding.
2) We build the first human-centric video-description dataset, which can be used as the benchmark dataset for the new task and inspires the subsequent research.
3) We propose an effective baseline method for the new task and demonstrate the effectiveness of the proposed method through extensive experiments.

\begin{figure*}[h]
  \includegraphics[width=0.98\linewidth]{fgs/track.pdf}
  \caption{Examples of our newly collected HC-STVG dataset. (a) For a video clip, we collect its text description (top), bounding boxes (green boxes), and temporal annotation (bottom). (b) An example of our semi-automatic annotation strategy. For each video clip, the volunteers are asked to annotate the yellow bounding boxes in three selected keyframes, while the green bounding boxes in the remaining frames are tracked by the method SiamPRN ~\cite{li2018high}.
  }
  \label{fig:track}
\end{figure*}

\section{RELATED WORK}

\subsection{Referring Expression in Images/Videos}
Referring Expression aims to localize the visual object described by any natural language expression ~\cite{yu2016modeling,kazemzadeh2014referitgame,mao2016generation,huang2020ordnet,huang2020referring,hui2020linguistic,Liao_2020_CVPR,yu2018mattnet,liao2019real}. The previous works~\cite{mao2016generation} and~\cite{yu2018mattnet} used a pretrained object detection network or an unsupervised method to generate object proposals and then match these regions with the textual description to select the most relevant proposal.
To better capture multi-modality context information, MAttNet~\cite{yu2018mattnet} proposed to decompose the referring expression into \textit{subject}, \textit{location}, and \textit{relation}. Moreover, cross-modality correlation filtering is adopted for the referring expression task in real-time~\cite{liao2019real}.
As for referring expression in videos, the WSSTG~\cite{chen2019weakly} is proposed to localize the spatial-temporal tube of an object in a \textit{trimmed} video where the target objects exist through the whole clip.

\subsection{Visual Transformer}
In recent years, Visual Transformer methods ~\cite{alberti2019fusion,chen2019uniter,li2020unicoder,li2019visualbert,su2019vl,lu2019vilbert,tan2019lxmert} have achieved impressive performance in many Vision-Language tasks, including the Referring Expression tasks.
These works usually employed a transformer-structure model to extract multi-modal feature representation from image-text or video-text pairs and then predict the regions of interest(ROI) based on the cross-modal features.
The existing transformer-based methods proposed for vision-language tasks can be divided into two categories, the single-stream models and the two-stream models. The single-stream models ~\cite{alberti2019fusion,chen2019uniter,li2020unicoder,li2019visualbert,su2019vl} employ a single transformer to learn cross-modal features from the visual and the textual modalities. In contrast, the two-stream models ~\cite{lu2019vilbert,tan2019lxmert} use different encoders to encode information of different modalities while using a co-attention module to learn cross-modal feature representation.

\subsection{Temporal Video Grounding}
The goal of temporal video grounding is localizing the most relevant video segment given a query sentence. The previous works ~\cite{gao2017tall,anne2017localizing,liu2018attentive,liu2018cross,xu2019multilevel} used a temporal sliding-window-based approach over the video frames to generate temporal candidates and choose the most relevant one as the output. Chen et al. ~\cite{chen2018temporally} proposed aggregating the fine-grained frame-by-word interaction between videos and queries.
Xu et al. ~\cite{xu2019multilevel} and Chen et al. ~\cite{chen2019semantic} proposed to generate query-specific proposals as candidate segments by directly integrating sentence information with each fine-grained video clip.
Ge et al.~\cite{ge2019mac} explored activity concepts in both videos and queries for temporal localization. Zhang et al. ~\cite{zhang2019man} iteratively adjusted the structured graph to deal with the semantic misalignment problem.
Yuan et al.~\cite{yuan2019sentence} utilized the Graph Convolutional Network ~\cite{kipf2016semi} to model the relations between different video clips and proposed a temporal conditioned pointer network to screen the answer.
Unlike these previous video grounding works, which only deal with temporal localization, the newly proposed HC-STVG tackles spatial localization and temporal localization simultaneously.

\section{HC-STVG BENCHMARK}\label{sec:Dataset detail}
The newly proposed HC-STVG task aims to localize the target person spatio-temporally in an untrimmed video. For this task, we collect a new benchmark dataset with spatio-temporal annotations related to the target persons in complex multi-person scenes, together with full interaction and rich action information.

\subsection{Task Formulation}\
In this work, the HC-STVG task is defined as follows.
Given an untrimmed video  $v\,\epsilon\,V$ and a natural language description $s\,\epsilon\,S$, which describes a sequence of actions related to a specific person in $v$, we aim to generate the spatio-temporal tube $T$ (i.e., a sequence of bounding boxes) corresponding to the target person. Specifically, the system needs to locate the segment by determining the starting and ending frames ($l$, $r$) and also generates the bounding boxes of the target person in the located segment.

\subsection{Overview of HC-STVG dataset}
There are 5,660 video-sentence pairs in our newly collected HC-STVG dataset, including 4,500 training pairs and 1,160 testing pairs.
The average temporal duration of the ground-truth tubes is 5.37 seconds while each sentence has an average of 17.25 words. The duration of videos is further normalized to 20 seconds.
We ensure that the test samples and the training samples do not originate from the same raw video.

The key characteristics of our HC-STVG are summarized as follows: (1) human-centric. The dataset contains precise spatio-temporal annotations  and textual description for the person of interest in each video. (2) All videos are captured in complex multi-person scenes, along which 57.2\% of the videos have more than three people while the rest videos have two persons. (3) All sentences have rich descriptions related to the interaction between human-human or human-objects and 56.1\% of the descriptions include both types of interaction.

Figure~\ref{fig:track}(a) and Fig.~\ref{fig:verb_vis} show several examples of our newly collected dataset. As demonstrated in these two figures, the videos in the new dataset are captured in multi-person scenes. Besides, the descriptions have rich expressions related to actions and relations.

\begin{figure*}[ht]
	\begin{center}
		\includegraphics[width=0.96\linewidth]{{fgs/verb_vis.pdf}}
	\end{center}
	\caption{An example video-sentence pair in our newly collected dataset. In the example video clip, the target person performs a series of actions. Correspondingly, these actions are described in the sentence, including `puts his glasses on the table',`pulls something out of his pocket', and `puts it on the table'.}
	\label{fig:verb_vis}
\end{figure*}

\subsection{Dataset Construction}\label{subsec:dataset_construction}
The whole process includes five modules: Raw Video Preparation, Video Span Selection, Video Description, Bounding box annotation, and Video Span Extension. We explain these parts in detail.

{\bfseries Raw Video Preparation}
We use raw video filtered by AVA dataset~\cite{DBLP:conf/cvpr/GuSRVPLVTRSSM18}.
These original videos have been collected on Youtube and have been carefully selected to ensure the diversity and high-quality of the videos. These videos contain a lot of realistic scenes, character actions, and character interactions. Therefore, we can produce more suitable video-description pairs from the videos.

{\bfseries Video Span Selection}
Annotators watch untrimmed videos sequentially and follow several rules to mark suitable describable spans. To be specific, the chosen spans must be multi-person scenes, thus increasing the difficulty of grounding in our dataset.
Shot switching is not allowed in the annotated clips because shot switching splits the video content into discrete paragraphs, bringing semantic incoherence. And We limit the shortest video span time to 3s to avoid annotators only tagging the instantaneous actions of the characters instead of continuous action sequences.
Under these restrictions, annotators annotate the precise temporal segment of the target person's actions in the scenario.

{\bfseries Video Description}
The annotator who decides the specific video span is required to write down a description of the target person.
To collect more diversified and natural expressions, we do not provide any templates and predefined verb lists for annotators to follow. But we still have some guidelines for annotators to make an appropriate textual annotation.
(1) The description can spatio-temporally locate the target person uniquely, which means that there can not exist another person that satisfies the description and the actions of the target person are traceable.
(2) We encourage annotators to describe in terms of explicit visual attributes, human actions, and relations, as our goal is to contain a variety of reasoning information. And descriptions of other persons' attributes in the sentence are also encouraged to increase diversity.
(3) As for actions descriptions, in addition to using some transitive verbs (e.g.\ walk, turn) for target persons, workers are encouraged to write human-to-human and human-to-object interactions (e.g.\ hug, follow) as much as possible, which urges the algorithm to pay close attention to the identification and alignment of dynamic visual relation.
(4) The annotators are encouraged to label successive events that consist of the target character and related actions, which increases the number of verbs in the sentence and differs HC-STVG from the mere action localization task.
(5) Since we only deal with the video images, the annotators are required to focus on the visual content rather than the sound content. At last, after the annotations, we manually review the descriptions to ensure label quality.

{\bfseries Bounding Box Annotation}
Frame-level bounding box annotation is quite crucial for visual grounding tasks to assist in the judgment of location correctness. However, manually labeling bounding boxes for each frame in the video may lead to enormous labor pressure.
To trade off this problem, we adopt the way of manually labeling keyframes and automatically labeling other frames with the tracking algorithm.
Concretely, we use SiamRPN~\cite{li2018high} to track the target person. We manually annotate three keyframes of a video span (i.e., starting, middle, ending frame) and track the other frames, which effectively outperforms using only one keyframe. We track the person in the annotated temporal clip from front to back and from back to front using keyframes, then we average these two tracking results as an annotation.
We conduct an additional manual review to correct the tube for samples with apparent differences in two direction tracking results.

{\bfseries Video Span Extension}
After the video spans are collected and the spatial-temporal annotations are complete, we extend the video clips forward and backward on the temporal ground truth randomly to achieve a fixed total length of time for final query videos, and the extended time also serves as a negative sample for temporal localization.
As localizing descriptions in query videos may be ambiguous after time extension, in HC-STVG, additional annotators review the total video span to guarantee there is no unambiguous referring.

\begin{table}[ht]
\centering
\caption{Statistics of Different Datasets. \\ ALS stands for average length of sentences. BA and TA stand for Bounding Box annotation and  Temporal annotation, respectively. HC stands for Human-centric.}
\begin{tabular}{p{2.5cm}p{1cm}p{1cm}p{0.5cm}p{0.3cm}p{0.3cm}p{0.3cm}}
\hline
Dataset & \#Queries & \#Videos & ALS & BA & TA & HC \\
\hline
DiDeMo~\cite{anne2017localizing} & 40,543 & 10,464   & 8.0           & $\times$              & \checkmark                     & $\times$             \\
CharadesSTA~\cite{gao2017tall} & 16,128 & 6,670  & 7.2  & $\times$              & \checkmark                     & \checkmark               \\
TACoS~\cite{rohrbach2014coherent} & 18,818 & 7,206 & 10.5 & $\times$        & \checkmark   & \checkmark   \\
ActivityNet-C~\cite{krishna2017dense}  & 71,942 & 12,460 & 14.8        & $\times$              & \checkmark                     & \checkmark               \\
VID-sentence~\cite{chen2019weakly}   & 7,654  & 5,318  & 13.2        & \checkmark              & $\times$                   & $\times$             \\
VidSTG~\cite{zhang2020does} &44,808  & 6,924 & 11.12       & \checkmark              & \checkmark                     & $\times$    \\
\hline
HC-STVG Dataset & 5,660 & 5,660  & 17.25       & \checkmark              & \checkmark                     & \checkmark    \\
\hline
\label{tab:datasets}
\end{tabular}
\end{table}

\subsection{Comparison with the Existing Datasets}
We compare the existing video grounding datasets with our newly collected HC-STVG dataset in Table~\ref{tab:datasets}. The DiDeMo dataset~\cite{anne2017localizing} only provides temporal annotation for the temporal localization task. The TACoS dataset~\cite{DBLP:journals/tacl/RegneriRWTSP13}, ActivityNet Captions dataset~\cite{krishna2017dense}, and Charades-STA dataset~\cite{gao2017tall} are all human-centric datasets as their videos capture human actions (e.g., cooking). Similar to DiDeMo dataset, these datasets are collected for the temporal localization task, and they do not have annotations at the bounding box level. The VID-sentence dataset ~\cite{chen2019weakly} provides the bounding-box-level annotations. However, it only focuses on spatial localization. Video clips in this dataset are all trimmed, hence it is not suitable for temporal localization. Among all datasets, the most relevant dataset is the VidSTG dataset~\cite{zhang2020does}. It is extended from the dataset Vidor~\cite{2019Annotating}, which is a dataset originally collected for detecting relations in videos. The VidSTG dataset provides both bounding-box-level annotations and temporal annotations. However, this dataset focuses on the task of relation referring between subjects and objects. In contrast, our HC-STVG dataset focuses on localizing the target person spatially and temporally from multi-person scenes based on the query sentences. Furthermore, on average the length of each sentence in our dataset is the longest among these datasets, and the descriptions from this dataset contain rich expressions related to actions and human-object interaction. The details of all these datasets are summarized in Table~\ref{tab:datasets}.

\begin{figure*}[ht]
    \includegraphics[width=1.0\linewidth]{fgs/fig2.pdf}
  \caption{The framework of our STGVT. The framework has four modules, which correspond to four steps explained in Methodology. Specifically, given a query sentence and video, it first generates tube proposals (A), and then each tube-description pair is fed into the visual transformer (B). The output feature of the visual transformer is used for predicting matching score, classification score, tube offsets , which to be used for tube selection (C) and tube trimming (D).}
  \label{fig:framework}

\end{figure*}
\section{METHODOLOGY} \label{sec:method}
The overall framework of our STGVT method is shown in Fig.~\ref{fig:framework}. Given a video $v$ and a query sentence $s$ depicting a person performing a series of actions, our STGVT  method aims to output a spatio-temporal tube $T$ corresponding to the description. The method consists of four steps:
\textbf{1)} it first generates the tube proposals (Sec.~\ref{sec:tube}). \textbf{2)} Then a visual transformer takes a pair of the tube proposal and the query sentence as the input, and extracts the cross-modal features, including the global feature and the frame features (Sec.~\ref{sec:cross_rep}). \textbf{3)} A matching classifier is adopted to predict a matching score for each tube-sentence pair. The tube proposal with the highest matching score will be proceeded in the final step (Sec.~\ref{sec:matching}). \textbf{4)} Based on the selected tube, a temporal trimming module is proposed to trim the irrelevant frames and produce the final spatio-temporal localization results. (Sec.~\ref{sec:trimming}).

In this section, we first describe each step of the proposed method and then introduce the loss functions (Sec.~\ref{sec:loss}) and the inference process (Sec.~\ref{sec:inference}).

\subsection{Tube Proposals Generation}\label{sec:tube}

Given a video, we first use the region proposal network~\cite{ren2015faster} to detect the bounding boxes $B_{t,i}$ in each frame, where $B_{t,i}$ represents the $i$-th bounding box in the $t$-th frame. Basically, we follow the ACT method~\cite{kalogeiton2017action} to link the bounding boxes in consecutive frames to form spatio-temporal tube proposals $T_p$.
This process is essential to group the bounding boxes containing similar visual content in adjacent frames.
Different from the method~\cite{kalogeiton2017action}, we compute the similarity score between two bounding boxes (i.e., $B_{t,i}$ and $B_{t+1,j}$) as follow:
\begin{center}
\begin{equation}
\label{eq:link_tube}
\begin{split}
S_(B_{t,i},B_{t+1,j}) =  \lambda_i*IoU(B_{t,i}, B_{t+1,j})  \\
+ \lambda_c*D_{cosine}(f(B_{t,i}),f(B_{t+1,j})) \\
+ \phi(B_{t,i}) +  \phi(B_{t+1,j}),
\end{split}
\end{equation}
\end{center}
where $f(\cdot)$ is a pretrained feature extractor, $D_{cosine}(\cdot,\cdot)$ is the cosine function, $\phi$ is the confidence score of the bounding boxes, and  $\lambda_i,\lambda_c$ are the weights of the IoU score and the cosine score. In practice, we set them as 0.7 and 0.3 respectively.

\subsection{Cross-modal Representation}
\label{sec:cross_rep}

The next step is to extract cross-modal features for each pair of the tube proposal $T_p$ and the query description $s$. We adopt Visual Transformer in this step due to its great success for the cross-modal tasks~\cite{lu2019vilbert}. The visual transformer takes the visual and textual inputs separately and models their interaction through a set of transformer layers based on the co-attention mechanism. Specifically, following~\cite{devlin2018bert}, we use the position information, token information, and segment embedding extracted from the query description $s$ as the textual inputs; while each temporal position, visual feature, and spatial location from tube proposal $T_p$ are used as the visual inputs for each tube proposal $T_p$. The temporal position refers to the frame index, the visual features are extracted from the bounding box in each frame of $T_p$, and the bounding boxes' coordinates are encoded as the location
embedding.

The visual transformer will output two cross-modal features $f^{global}$ and $f^{frame}$. When using the textual inputs as the Query and the visual inputs as the Key and Value, $f^{global}_p$ ($p$ indicates the $p$-th tube-sentence pair) is the element-wise product of the visual feature and textual feature, which are extracted from the first token position. When the visual inputs are used as Query and the textual inputs are used as Key and Value, the model generates the feature $f^{frame}_{p,t}$ for each bounding box in each frame of $T_p$ ($p$ and $t$ refer to the $t$-th frame of the $p$-th tube). These two features are used to predict the matching scores of $T_p$ at the tube-level and the frame-level, which to be explained below.

\subsection{Tube-description Matching}
\label{sec:matching}
In this step, our method will verify if the input tube proposal $T_p$ is matching with the query description $s$. As mentioned above, the visual transformer extracts the global feature $f^{global}_p$ for each pair of $T_p$ and $s$. We feed $f^{global}_p$ into a binary classifier to predict its matching score $M'_p \in [0,1]$. $T_p$ with the highest matching score will be selected and fed into the last step.

When training the classifier, it is worth noting that the positive and negative samples can be imbalanced if we only treat the ground-truth tube, $T_{GT}$, as the positive sample. To tackle this problem, we relax the criteria for the positive samples by introducing two scores, $s_{overlap}$ and $s_{IoU}$. The tube proposals which simultaneously satisfy the following two conditions, $s_{overlap}>=0.9$ and $s_{IoU}>0.5$, are treated as the positive samples. Specifically, (1) $s_{overlap}$ is defined as follow:
\begin{equation}
\label{eq:overlap}
s_{overlap} =  \frac{\left | T_p \cap  T_{GT} \right |}{\left | T_{GT} \right |},
\end{equation}
$\left | T_{GT} \right |$ refers to the total number of  frames in the ground-truth tube. This score reflects the ratio of the total number of the intersected frames between $T_p$ and $T_{GT}$ over all frames in $T_GT$.
2) The average IoU score $s_{IoU}$ is defined as follow:
\begin{equation}
\label{eq:IoU}
s_{IoU} = \frac{1}{\left | T_p \cap  T_{GT} \right |}\sum _{t\in {T_p \cap  T_{GT}}}{IoU \left ({B'_{t}},{B_{t}}\right)},
\end{equation}
where ${B'_t}$ and ${B_t}$ are the detected/ground-truth bounding boxes of $T_p$ and $T_{GT}$ at frame $t$, respectively. A tube is treated as a negative sample when its $s_{IoU}$ is lower than 0.2.

\subsection{Tube Trimming}
\label{sec:trimming}

Given the dynamic characteristics of actions, the selected tube proposal $T_p$ may contain redundant transition frames. Hence it is required to trim $T_p$ to output the final predicted tube $T$. We compute the relevance score of each frame in $T_p$ to the query $s$, and predict the regression offsets. Our trimming module consists of two subnets, a classification subnet and a boundary regression subnet, which will be detailed below.

\subsubsection{Classification Subnet}
The classification subset is used to predict if a video frame should be kept in the final tube -- the spatio-temporal localization result $T$, or not. As introduced in Sec.~\ref{sec:cross_rep}, the transformer outputs $f^{frame}_{p,t}$ for each frame of $T_p$. The classifier takes $f^{frame}_{p,t}$ as the input to predict a relevance score $C'_{p,t}$ indicating how relevant the $t$-th frame is to the query sentence $s$.

\subsubsection{Boundary Regression Subnet}
Besides the relevance score $C'_{p,t}$, we also adopt a network to predict the temporal offsets, which reflects how far away the current frame is from the ground-truth temporal boundary. This subset's architecture is the same as the classification subset except that it has two outputs. Specifically, for a positive frame at the $t$-th position, if the ground-truth tube spans from the $l$-th frame to the $r$-th frame (i.e., $R_{GT}=[l,r]$), the regression target is $O_{p,t}=(\delta{l}, \delta{r})$,
\begin{equation}
\delta{l} = \frac{t - l}{N} \ \ \ \ \ \delta{r} = \frac{r - t}{N},
\end{equation}
where $N$ is the number of frames in  tube $T_p$. $\delta{l}$ and $\delta{r}$ refer to the temporal offset from the $t$-th frame to the left and the right boundary, respectively.

\subsection{Loss Functions}
\label{sec:loss}
Given the tube-level matching prediction score $M_p'$, the frame-level relevance prediction score $C'_{p,t}$, and boundary regression prediction result $O'_{p,t}$, and their corresponding ground-truth labels $M_p$, $C_{p,t}$, $O_{p,t}$, the total loss is defined as follows,
\begin{center}
\begin{equation}
\label{eq:loss}
\begin{split}
L = \sum_p \{\lambda_1*L_{match}\left (M_p',M_p \right ) \\ +\lambda_2*\mathbb{I}_{\left \{ M_p=1 \right \}}  \frac{1}{N}  \sum_t{L_{cls}\left (C_{p,t}',C_{p,t} \right )}\\+
\lambda_3*\mathbb{I}_{\left \{ M_p=1,C_{t}=1 \right \}}  \frac{1}{N_{pos}}  \sum_t{L_{reg}\left (O'_{p,t},O_{p,t}\right)}\}
\end{split}
\end{equation}
\end{center}
where $L_{match}$ is the cross-entropy loss for the tube-description matching module, $L_{cls}$ and $L_{reg}$ is a cross-entropy loss and IoU loss (i.e., $-ln(\frac{O'_{p,t} \cap O_{p,t}}{O'_{p,t} \cup O_{p,t}})$) for the classification subset and the boundary regression subset, respectively. $N$ and $N_{pos}$ denote the number of frames and the \textit{positive} frames in the tube $T_p$.
It is worth noting that, except for the tube proposals generation network, the rest of the proposed modules can be trained in an end-to-end fashion. However, the loss $L_{cls}$ and $L_{reg}$ in Eq.~\ref{eq:loss} are only computed for the positive tubes (i.e., $I_{(M_p=1)}$) and positive frames ($I_{(M_p=1,C_{p,t}=1)}$).

\subsection{Inference}
\label{sec:inference}
During the inference process, given a query sentence $s$ and a video $v$, our proposed method:
\textbf{(1)} first generates $P$ tube proposals $T_p$ $(p=1,2,...,P)$. Each tube proposal $T_p$ and the query sentence $s$ form a pair, which will be fed into the visual transformer. \textbf{(2)} For each pair of $T_p$ and $s$, the visual transformer extracts cross-modal features, $f^{global}_p$ and $f^{frame}_{p,t}$. \textbf{(3)} The tube-description matching module takes the global feature $f^{global}_p$ as the input and predicts a matching score $M’_p$. The tube with the highest matching score $M’_p$ is selected and further trimmed.
\textbf{(4)} For all frames in the selected tube $T_p$, the classification subnet and the regression subnet take the frame feature $f^{frame}_{p,t}$ as the input, and output the classification score $C’_{p,t}$ and $O’_{p,t}=(\delta{l}, \delta{r})$ for each frame.
We follow the method DEBUG~\cite{lu2019debug} to determine the temporal boundary of the selected tube. Specifically, we start from the frame with the highest $C’_{p,t}$. Given its predicted regression offsets $O’_{p,t}=(\delta_l, \delta_r)$, we can produce an initial range $R_{init}=(t-\delta_{l}*N,t + \delta_{r}* N)$. Next, we compute $R_t$ for the remaining $N-1$ frames. If the predicted range of the $t$-th frame, $R_t$, has overlap with $R_{init}$, then $R_t$ is merged with $R_{init}$. This process is repeated for all frames whose $C'_{p,t}$ higher than a pre-defined threshold $\epsilon$, which will produce the final predicted tube.

\section{EXPERIMENTS}
\subsection{Evaluation Metrics  \& Implementation Details}
The main evaluation metric for HC-STVG is \textbf{\textit{vIoU}}, and it is defined as follow:
\begin{equation}
vIoU = \frac{1}{\left | {T_{union}}  \right |}\sum _{t\in {T_{inter}}}{IoU \left ({B'_t},{B_t}\right)},
\end{equation}
where $T_{inter}=T_p \cap  T_{GT} $ refers to the intersected frames between the predicted tube $T_p$ and the ground-truth (GT) tube $T_{GT}$, $T_{union}=T_p \cup  T_{GT}$ represents the union set of the predicted frames and the GT frames, ${B'_t}$ and ${B_t}$ are the predicted bounding box and the ground truth bounding box at frame $t$. \textbf{$vIoU$} reflects the accuracy of the predicted spatio-temporal tubes. The \textbf{\textit{vIoU@perc.}} score stands for the percentage of predicted tubes whose $vIoU$ is larger than \textit{perc.} and $\mathbf{m_{vIoU}}$ is the average of $vIoU$s score over the whole test set.

During the inference process, we
sample one frame from every six frames of the tube before feeding the sampled frames into the visual transformer in order to reduce redundancy. The maximum number of bounding boxes detected in each image is set as 101. We use Mask R-CNN pretrained on the Visual Genome dataset~\cite{krishna2017visual} to extract the visual features from each bounding box.
Every query sentence $s$ is truncated or filled to the maximum length of 40 words. The loss weights $\lambda_1$, $\lambda_2$, $\lambda_3$ are empirically set as 1, 1 and 2, respectively. During the training process, we use Adam optimizer~\cite{duchi2011adaptive}. The initial learning rate and batch size are empirically set as 2e-5 and 32, respectively.

\begin{table}[h]
\centering
\caption{Performance (\%) over $m\_vIoU$, $vIoU@0.3$ and $vIoU@0.5$ on the VidSTG Dataset of the declarative sentence.}
\begin{tabular}{|c|ccc|}
\hline
\multirow{2}{*}{Method} & \multicolumn{3}{c|}{Declarative Sentence} \\
                        & m\_vIoU     & vIoU@0.3     & vIoU@0.5     \\
\hline
Random                  & 0.69\%      & 0.04\%       & 0.01\%       \\
GroundeR~\cite{yu2017joint} + TALL~\cite{gao2017tall}         & 9.78\%      & 11.04\%      & 4.09\%       \\
STPR~\cite{yamaguchi2017spatio} +   TALL~\cite{gao2017tall}           & 10.40\%     & 12.38\%      & 4.27\%       \\
WSSTG +   TALL~\cite{gao2017tall}          & 11.36\%     & 14.63\%      & 5.91\%       \\
GroundeR~\cite{yu2017joint} + L-Net~\cite{chen2019localizing}        & 11.89\%     & 15.32\%      & 5.45\%       \\
STPR~\cite{yamaguchi2017spatio} +   L-Net~\cite{chen2019localizing}          & 12.93\%     & 16.27\%      & 5.68\%       \\
WSSTG~\cite{chen2019weakly} +   L-Net~\cite{chen2019localizing}         & 14.45\%     & 18.00\%      & 7.89\%       \\
STGRN~\cite{zhang2020does}                   & 19.75\%     & 25.77\%      & 14.60\%      \\
STGVT                   & \textbf{21.62\%}     & \textbf{29.80\%}      & \textbf{18.94\%}  \\ \hline
\end{tabular}
\label{tb:vid}
\end{table}

\begin{table}[h]
\centering
\caption{Performance (\%) of different methods on the HC-STVG Dataset in term of $m\_vIoU$, $vIoU@0.3$ and $vIoU@0.5$}
\begin{tabular}{p{3.5cm}p{1cm}p{1.25cm}p{1.25cm}}
\hline
Method & $m\_vIoU$ & $vIoU@0.3$ & $vIoU@0.5$ \\
\hline
Random                   & 0.71\%  & 0.03\%   & 0\%      \\
TALL~\cite{gao2017tall}+WSSTG~\cite{chen2019weakly}                & 13.37\% & 19.95\%  & 7.33\%   \\
2D-TAN~\cite{zhang2019learning}+WSSTG~\cite{chen2019weakly}              & 15.43\% & 19.83\%  & 6.81\%   \\
\hline
STGVT~($w/o~trimming$)  & 16.93\%  & 21.29\%  & 6.64\%       \\
STGVT~($w/o~pretraining$)       & 17.46\% & 25.09\%  & 7.76\%   \\
STGVT       & \textbf{18.15}\% & \textbf{26.81}\%  & \textbf{9.48}\%  \\
\hline
\label{tb:results}
\end{tabular}
\end{table}

\subsection{Baseline Methods}
Considering that the existing methods cannot be directly applied for the human-centric spatio-temporal video grounding task, we form two baselines by combining the existing methods on video grounding. Specifically, \textbf{TALL}~\cite{gao2017tall} and \textbf{2D-TAN}~\cite{zhang2019learning} are the two methods for temporal video localization, while \textbf{WSSTG}~\cite{chen2019weakly} method is proposed for localizing spatio-temporal tubes in \textit{trimmed} videos. So we first apply TALL or 2D-TAN to produce a temporary segment from each \textit{untrimmed} video based on each given sentence, and then utilize the WSSTG method to localize spatio-temporal tubes in the generated segment. The \textbf{Random} method localizes the temporal segment and spatial regions randomly.
It is worth noting that we replaced the tube-description matching module with the WSSTG method, while keeping the entire training process fully supervised.
For a fair comparison, we the same strategy for all these methods to generate the tube proposals, as introduced in Section IV-A.

\subsection{Experimental Results}
We report the results of our STGVT method and the baseline methods in Table \ref{tb:results}.
One can observe that our STGVT method outperforms all baseline methods. Our method achieves the $m_{vIou}$ score of  18.15\%, which outperforms baseline methods by a significant margin. Our method also surpasses the baselines in terms of $vIoU@0.3$ and $vIoU@0.5$.

To further verify the effectiveness of our method, we also conducted experiments on VidSTG~\cite{zhang2020does} dataset. VidSTG is a suitable dataset for Spatio-Temporal Video Grounding task, but it is not human-centric. Thus we considered all the categories in the library when generating tubes, and use the same method to select the target tube and trim it. Experimental results in  Table~\ref{tb:vid}.  show that our method is also effective on different databases.

\subsection{Ablation Study}
\subsubsection{Effectiveness of Tube-description Matching Module}
In our proposed method, the tube-description matching module outputs a raw prediction of the spatio-temporal tube, which will further be trimmed by the tube trimming module. We evaluate the quality of the raw predictions by comparing our method with the WSSTG~\cite{chen2019weakly} method in Table~\ref{tb:match}. It is worth noting that (1) we directly use the tube without any temporal trimming as the final prediction, (2) both ours and WSSTG use the same method for generating tube proposals.

\begin{table}[h]
\centering
\caption{Tube matching accuracy results on the HC-STVG dataset}
\begin{tabular}{p{2cm}p{1.5cm}p{1.5cm}p{1.5cm}}
\hline
Method & $m\_vIoU$ & $vIoU@0.3$ & $vIoU@0.5$ \\
\hline
Random  & 2.40\%  &  1.72\%   & 0.44\%       \\
WSSTG~\cite{chen2019weakly}   & 12.96\%  & 16.23\%  & 4.35\%       \\
STGVT   & \textbf{16.93}\%  & \textbf{21.29}\%  & \textbf{6.64}\%       \\
\hline
\label{tb:match}
\end{tabular}
\end{table}

\subsubsection{Effectiveness of Tube Trimming Module}
In this section, we demonstrate the effectiveness of the tube trimming module in our proposed method. As shown in Table~\ref{tb:results}, our full method (\textit{STGVT}) significantly outperforms the simplified version without the tube trimming module (termed as \textit{STGVT~(w/o~trimming)}). The performance improvement of our \textit{STGVT} over \textit{STGVT~(w/o~trimming)}  indicates the effectiveness of the tube trimming module. However, it is worth noting that, even without using the tube trimming module, our simplified version \textit{STGVT~(w/o~trimming)} method still achieves better performance compared with other baseline methods.
Besides, we compared the results of the trimmed positive tube, as shown in Table~\ref{tb:tem_results}, the result of tube selection we chose significantly outperforms the baseline method.

\begin{table}[h]
\centering
\caption{Temporal grounding Performance (\%) over $m\_tIoU$ and $m\_vIoU$}
\begin{tabular}{p{3.5cm}p{1.5cm}p{1.5cm}}
\hline
Method & $m\_vIoU$ & $m\_tIoU$ \\
\hline
Random                    & 0.71\%  & 10.50\%    \\
TALL~\cite{gao2017tall} +$Tube_{pos}$         & 31.64\% & 44.31\%   \\
2D-TAN~\cite{zhang2019learning}+$Tube_{pos}$       & 32.89\% & 46.20\%    \\
STGVT+$Tube_{pos}$        & \textbf{34.71}\% & \textbf{48.64}\%  \\
\hline
\label{tb:tem_results}
\end{tabular}
\end{table}

\begin{figure*}[h!]
    \begin{center}
    	\includegraphics[width=1.0\linewidth]{fgs/res_v1.pdf}
    \end{center}
    \centering
  \caption{
Representative results produced by our method and the baseline method (WSSTG+TALL). In the 2nd and the 5th examples, our method achieves better temporal localization results when compared with the baseline method. While in the 1st, the 3rd, and the 5th examples, our method achieves more accurate spatial localization results. }
  \label{fig:res}
\end{figure*}

\subsubsection{Effectiveness of the Pretraining Strategy}
Since we adopt the visual transformer \textit{pretrained} based on the Conceptual Captions dataset~\cite{sharma2018conceptual}, we wonder whether the performance improvement is due to the pretraining strategy. So we perform another experiment by training the visual transformer from scratch\footnote{The visual transformer has two branches, one for textual feature while the other for visual feature. All methods except for the baseline method `Random' use a pretrained transformer for the textual branch.} (and our method is referred as \textit{STGVT~(w/o~pretraining)}.
As shown in Table~\ref{tb:results},
we observe that: 1) our method \textit{STGVT~(w/o~pretraining)} outperforms existing baseline methods; 2) using the pretraining strategy can improve the performance.

\subsection{Qualitative Analysis}
We provide some visualization results in Fig.~\ref{fig:res}.
These examples show that our method outperforms the baseline method for video grounding both spatially and temporally. Specifically, in most examples (except the 3rd one), there are more overlap between our temporal tube prediction results (see the yellow line) and the ground-truth (see the green line) when compared with the baseline method TALL~\cite{gao2017tall} + WSSTG~\cite{chen2019weakly}(see the red line), which indicates our method can localize the video segment more precisely. In the 3rd example, both our method and the baseline method achieve good performance in temporal grounding, but our method generates more accurate bounding boxes.

\section{Conclusion}
In this work, we have introduced a novel task Human-centric Spatio-Temporal Video Grounding (HC-STVG). Furthermore, we have contributed a new HC-STVG dataset with rich spatio-temporal tube annotations for videos and the corresponding descriptive sentences.
We have also proposed a baseline method named STGVT, which takes advantage of the Visual Transformers to tackle the HC-STVG task. Comprehensive experiments have demonstrated that our method outperforms the existing grounding methods for the HC-STVG task.
\\

\noindent{\bfseries Acknowledgement:}
This research is supported in part by the National
Key Research and Development Project of China
(No. 2018AAA0101900), the National Natural Science Foundation of China (Grant
61876177), Beijing Natural Science
Foundation (4202034), the Guangdong Basic and Applied Basic Research Foundation (Grant No.2020B1515020048), Fundamental Research Funds
for the Central Universities, Zhejiang Lab (No. 2019KD0AB04).

\ifCLASSOPTIONcaptionsoff
  \newpage
\fi

{
\bibliographystyle{IEEEtran}


\section{Introduction\label{sec_intro}}
Recommendation systems aim to capture users' interests based on various kinds of clues and help users discover new items.
The primary source in personalised recommendation tasks is implicit user feedback (e.g. clicking, watching, and purchasing), which is routinely logged and reflects users' interests.
However, even with such abundant users' feedback,
recommender systems still suffer from the \emph{cold-start problem};
for new users who have not yet interacted with enough items,
recommender systems inevitably experience a lack of information.
The problem is severe in applications where the user and item databases are frequently updated, such as e-commerce, social news media, and online advertisement.
New items are also a typical cause of the cold-start problem, particularly in social networking services where user-generated contents continuously come in.
In such applications, recommender systems are required to handle new items associated with few interactions.

One option to mitigate this problem is to introduce knowledge graphs (KGs), which provide side-information about items~\cite{zhang2016collaborative,wang2018dkn,huang2018improving,yu2014personalized,zhao2017meta,MCRec}.
KGs are heterogeneous graphs of entities and relations between entities.
The nodes represent entities (e.g. items and their properties),
and the edges represent the relations between entities.

The problems due to lack of information remain challenging even with KGs.
Interactions observed in the form of implicit feedback provide only positive signals, and
this causes the fundamental obstacle in recommendation tasks, called the one-class problem~\cite{pan2008one,hu2008collaborative}.
For handling this only-positive setting, unobserved samples are the key resources, particularly for the sake of optimisation.
Conventional methods leverage unobserved samples to extract negative signals,
relying on the assumption that the unobserved samples can be utilised as negative instances~\cite{pan2008one,BPRMF,he2016fast}.
However, as this strategy distils only negative signals from unobserved samples,
it may lead to biased and sub-optimal results;
recommender systems may underestimate the chance of positive feedback of users or items rarely observed, namely, cold-start users and items~\cite{fairnessZuohui20}.

KG-aware recommender systems that utilise graph neural networks (GNNs)~\cite{wang2019knowledge,KGAT}
are promising directions.
GNNs leverage a KG in an end-to-end manner and
involve unobserved samples in the training phase by propagating features from labelled nodes to unlabelled nodes over a KG.
This nature of GNNs is suitable for the transductive setting of recommendation problems wherein
the goal is to predict labels for unlabelled nodes that are known in the training phase.
Nevertheless, conventional methods leverage unobserved samples mainly as negative instances based on the aforementioned assumption.

In this paper,
we address to improve recommendation for new items and users without compromising overall performance by appropriately leveraging unobserved samples.
We propose a KG-aware recommender based on GNNs and pseudo-labelling, namely, \emph{KGPL}.
Instead of handling unobserved samples only as negative,
we assign pseudo-labels to unobserved samples by model predictions that reflect the knowledge learnt from the observed data and KG.
Hence, in KGPL, unobserved samples can be handled as weak-positive instances in contrast to the conventional methods.
To ensure the reliability of pseudo-labels,
we carefully select the unobserved items to be labelled
through two sampling strategies;
(1) KG-aware sampling of items for pseudo-labelling based on the graph structures rooted at users and observed items in a KG; and
(2) popularity-aware sampling of items for negative instances.
Our KG-aware sampling for pseudo-labelling selects probably positive items
for a given user while ensuring the reliability of pseudo-labels.
We also introduce a negative sampling strategy for enhancing the stability of training.
Besides, to achieve further robust optimisation,
we propose a co-training approach that utilises a pair of GNNs.
Experimental results demonstrate that our method is effective for a wide range of users with different levels of data sparsity.

As overall average measures cannot describe the detailed difference between methods,
we showcase a series of experiments to extensively compare the behaviour of KG-aware recommenders with assuming user-side and item-side cold-start situations.
Our experiments provide more detailed insights on recommenders' behaviours which conventional evaluation methodology roughly abstracts.

\section{Related Work}
\subsection{Recommendations with Knowledge Graphs}
For leveraging a KG as additional side-information about items, various approaches are examined, such as
embedding-based methods~\cite{zhang2016collaborative,wang2018dkn,huang2018improving,wang2019multi},
path-based methods~\cite{yu2014personalized,zhao2017meta,hu2018leveraging,lu2020meta}, and
hybrid methods~\cite{RippleNet,sun2018recurrent,wang2019knowledge2,KGAT}.
Embedding-based methods alleviate cold-start problems
by extracting semantic knowledge from a KG.
Path-based methods manually design patterns of connectivity among items (i.e. meta-paths or meta-graph) to extract user-specific relatedness.
Recent hybrid methods adopt graph neural networks (GNNs) to learn representations of entities and user-specific relatedness without labour-intensive meta-paths~\cite{wang2019knowledge,wang2019knowledge2,KGAT}.
However, as in traditional recommender systems such as collaborative filtering~\cite{hu2008collaborative}, these methods leverage unobserved samples only as negative instances during training.
Wang \emph{et al.} proposed a negative sampling strategy based on reinforcement learning~\cite{KGPolicy20}.
Their method mainly focuses on finding informative negative samples and does not concern the problem of cold-start items that are rarely observed but can be relevant to certain users.
Our method utilises unobserved samples as both positive and negative instances to alleviate the cold-start problem.
To pull up cold-start items,
our KG-aware sampling and pseudo-labelling approach extract probably positive instances from unobserved samples.

\subsection{Graph-Based Semi-Supervised Learning and Pseudo-Labelling}
Semi-supervised learning (SSL) aims to correctly label all samples when a small fraction of samples are labelled.
A recommendation task with implicit feedback can be considered as an SSL problem;
in particular, the setting can be regarded as a transductive learning task wherein the unlabelled samples (i.e. user-item pairs) for inference are known in the training phase.
GNNs handle such a transductive setting
by propagating features over a graph~\cite{bruna2013spectral,defferrard2016convolutional,kipf2016semi,duvenaud2015convolutional,niepert2016learning,hamilton2017inductive}.
The recent success of GNN-based recommenders also demonstrates the effectiveness of GNNs~\cite{ying2018graph,monti2017geometric,berg2017graph,wang2019knowledge2,KGAT}.

Graph-based SSL has been extensively explored in various fields.
Existing methods often rely on
assumptions on the distribution of labels over a graph, such as label smoothness~\cite{wang2007label,karasuyama2013manifold,wang2019knowledge2}.
By adopting such assumptions, label propagation is widely utilised in a transductive setup~\cite{wu2012learning,Douze_2018_CVPR,iscen2019label}.
However, applying label propagation techniques to KG-aware personalised recommendation is not trivial for three reasons;
(1) only positive instances can be observed in implicit feedback settings;
(2) labels and edge weights depend on users' taste, and therefore, edges may not indicate similarity between their connecting nodes; and
(3) labelled nodes (i.e. the source of label propagation) for a single user are scarce.
Wang \emph{et al.} proposed a KG-aware recommender based on GNNs
with a regularisation technique that induces label smoothness in model predictions, namely, KGNN-LS~\cite{wang2019knowledge2}.
Their proposed regularisation technique realises label propagation on a KG through the \emph{leave-one-out} loss optimisation that
holds out an observed item for a user and leverages it as an unlabelled instance.
However, as they utilise only observed samples for their regularisation technique,
and unobserved samples are still not leveraged explicitly as positive.

Pseudo-labelling has been adopted particularly by deep learning-based methods~\cite{lee2013pseudo,shi2018transductive,ke2020multi}.
It reuses repeatedly updated model predictions as true labels for training, and thereby directly leverages unobserved samples as training data.
However, pseudo-labels generated by a model may be noisy, and leveraging all samples is infeasible in the context of recommendation problems as the number of all possible pairs of users and items can easily reach billion-scale.

Our method employs pseudo-labelling but inherits the spirit of label propagation.
To avoid exhaustively labelling unobserved samples,
we exploit graph structures for selecting candidates that can be labelled reliably.
In contrast to KGNN-LS, our loss function involves unobserved samples also as positive instances.

\section{Proposed Method\label{method}}
\subsection{Problem Formulation}
We now explain the primary setting of the problem discussed in this paper.
In a scenario of personalised recommendation,
we have a set of users $\mathcal{U}$ and a set of items $\mathcal{I}$.
The user-item interaction matrix $\bf{Y}$ can be obtained as the users' implicit feedback; we let $y_{u,i}$ be the $(u,i)$-entry of $\bf{Y}$, and then $y_{u,i}=1$ indicates that user $u$ has engaged with item $i$.
Unfortunately, we cannot observe $\bf{Y}_{ui}$ for all user-item pairs $(u, i) \in \mathcal{U}\times\mathcal{I}$ in realistic situations;
thus, $\bf{Y}_{ui}$ can be missing for the majority of $(u, i)$.
Hence, we let $\mathcal{I}_{u}^{+}$ denote the set of observed items for $u$,
and $\mathcal{I}\setminus\mathcal{I}_{u}^{+}$ indicates the set of unobserved items for $u$.
We also let $\mathcal{O}=\{(u,i)|u \in \mathcal{U}, i \in \mathcal{I}_u^{+}\}$ denote the set of observed user-item pairs.
Moreover, in the knowledge-aware recommendation problem,
we have a KG $\mathcal{G}=\{(h, r, t)|h, t\in \mathcal{E}, r\in\mathcal{R}\}$,
where each triplet $(h, r, t)$ describes that there is a relationship $r$ between head entity $h$ and tail entity $t$;
$\mathcal{E}$ and $\mathcal{R}$ denote the sets of entities and relations, respectively.
Here, $\mathcal{E}$ comprises items $\mathcal{I} (\mathcal{I} \subseteq \mathcal{E})$ and non-item entities $\mathcal{E}\setminus\mathcal{I}$ (e.g. nodes corresponding to the attributes of items).

The focus of this paper is
predicting the $y_{u,i}$ for each unobserved sample $(u, i) \in (\mathcal{U}\times\mathcal{I})\setminus\mathcal{O}$
based on the observed interactions $y_{u,i}$ corresponding to $\mathcal{O}$.
To this end, we aim to obtain a prediction function $\hat{y}_{u,i}=\mathcal{F}(u,i|\Theta,\bf{Y},\mathcal{G})$,
where $\hat{y}_{u,i}$ denotes the probability that user $u$ will engage with item $i$, and $\Theta$ are model parameters of function $\mathcal{F}$.

\subsection{Knowledge-Aware Graph Neural Networks\label{GNN-method}}
This section describes our GNN architecture for capturing users' preferences by exploiting a KG.
The architecture of our GNN is almost the same as KGNN-LS~\cite{wang2019knowledge2}.

We first model the user-specific relation scoring function that measures the importance of each relation for a user.
The $(j, k)$-th entry of a user-specific adjacency matrix ${\bf A}_u \in \mathbb R^{|\mathcal E| \times |\mathcal E|}$ can be obtained as follows:
\begin{eqnarray}
  \label{adj}
  (\bf{A}_u)_{jk} = \exp({\bf u}^{\top}r_{e_j, e_k})
\end{eqnarray}
where $\bf{r}_{e_j, e_k}$ is the relation between entities $e_j$ and $e_k$ in $\mathcal G$.
We set $(A_u)_{jk}=0$ if there is no relation between $e_j$ and $e_k$.
Then, the layer-wise forward propagation can be written by:
\begin{equation}
  \label{eq:kgcn}
  {\bf H}_{l+1} = \sigma_{l}\left({\bf D}_u^{-1/2} \left( {\bf A}_u + {\bf I} \right) {\bf D}_u^{-1/2} {\bf H}_l {\bf W}_l \right), \ l = 0, 1, \ldots, L-1,
\end{equation}
where ${\bf H}_l$ is the matrix of the hidden representations of entities in the $l$-th layer, and ${\bf H}_0$ is a trainable parameter ${\bf E}$.
Here, ${\bf A}_u$ aggregates the representation vectors of neighbouring entities, and we introduce a self-connection loop by ${\bf A}_u + {\bf I}$.
We also let ${\bf D}_u$ denote a diagonal degree matrix with entries $(\bf{D}_u)_{jj} = \sum_k ({\bf A_{u}})_{jk}$ to normalise ${\bf A}_u$.
Here, ${\bf W}_l \in \mathbb R^{d_l \times d_{l+1}}$ is the layer-wise trainable weight matrix, and $L$ is the number of layers.
$\sigma_l$ is the activation function for the $l$-th layer, and
we adopt LeakyReLU~\cite{maas2013rectifier} for the intermediate layers ($l < L$) and $\tanh(\cdot)$ for the last output layer.

The predicted engagement probability of user $u$ with item $i$
is computed by $\hat{y}_{u,i} = \sigma({\bf u}^{\top} {\bf i}_u)$,
where ${\bf i}_u$ (i.e. the row corresponding to item $i$ in ${\bf H}_L$) is the final personalised representation vector of $i$,
and $\sigma(\cdot)$ is a sigmoid function.
In the training phase, we aim to optimise model parameters $\Theta=\{{\bf U}, {\bf E}, {\bf R}, {\bf W}_{0},\dots,{\bf W}_{L}\}$.
We apply dropout to ${\bf U}$ and ${\bf H}_l\,(l=1,\dots,L)$ with a same ratio instead of L2 regularisation.

\subsection{Semi-Supervised Learning Based on Pseudo-Labelling\label{pl-section}}
Our method leverages a high coverage of unobserved user-item pairs to optimise the model
without assuming all unobserved pairs as negative instances.
Our approach comprises mainly three techniques;
(1) pseudo-labelling framework for one-class settings (described in this section);
(2) sampling strategies for pseudo-labelled and negative instances (described in Section~\ref{sampling-opt}); and
(3) co-training for robust optimisation with noisy pseudo-labels as in Section~\ref{co-training}.

To alleviate the sparsity issues of observed interactions,
we augment positive and negative labelled data by predicting the labels
of unobserved samples.
Our label function for user $u$ and item $i$ can be written as follows:
\begin{eqnarray}
\label{label-function}
  \hat{l}_u(i) = \begin{cases}
    1, & \text{if $u \in \mathcal{U} \land i \in \mathcal{I}_u^{+}$},\\
    \hat{y}_{u,i}, & \text{if $u \in \mathcal{U} \land i \in \mathcal{I}_u^{\pm}$},\\
    0, & \text{if $u \in \mathcal{U} \land i \in \mathcal{I}_u^{-}$},\\
    \end{cases}
\end{eqnarray}
where $\mathcal{I}_u^{+}$, $\mathcal{I}_u^{-}$, and $\mathcal{I}_u^{\pm}$ denote the sets of positive, negative, and pseudo-labelled items for $u$, respectively.
Then, our loss function can be expressed as follows:
\begin{eqnarray}
\notag
  \mathcal{L}
  &=& \sum_{u \in \mathcal{U}}\sum_{i \in \mathcal{I}_u^{+}}\ell\left(1, \hat{y}_{u,i};\Theta\right)
  +\sum_{u \in \mathcal{U}}\sum_{i \in \mathcal{I}_u^{\pm}}\alpha_{u,i}\ell\left(\hat{l}_u(i), \hat{y}_{u,i};\Theta\right)\\
  &+& \sum_{u \in \mathcal{U}}\sum_{i \in \mathcal{I}_u^{-}}\beta_{u,i}\ell\left(0, \hat{y}_{u,i};\Theta\right),
  \label{loss-function}
\end{eqnarray}
where $\ell(y_{u,i}, \hat{y}_{u,i};\Theta)$ is the loss function such as squared error and cross-entropy loss under a model with parameters $\Theta$.
$y_{u,i}$ and $\hat{y}_{u,i}$ denote a target label and a predicted label, respectively.
$\beta_{u,i}$ and $\alpha_{u,i}$ are the weight for the $(u, i)$-entry as a negative or pseudo-labelled instance, respectively.
We adopt the cross-entropy loss function as $\ell(\cdot)$.
As model prediction $\hat{y}_{u,i}$ can be considered as the probability that $i$ is positive for $u$,
the loss for a pseudo-labelled sample can be considered as an expected loss for the unobserved label;
$\ell(\hat{l}_{u}(i), \hat{y}_{u,i};\Theta)=-\hat{l}_u(i)\log(\hat{y}_{u,i})-(1-\hat{l}_u(i))\log(1-\hat{y}_{u,i})=\mathbb{E}_y[\ell(y, \hat{y}_{u,i};\Theta)]$.

There are two main challenges in the minimisation of $\mathcal{L}$;
(1) computing $\mathcal{L}$ is generally infeasible as $|\mathcal{U}\times\mathcal{I}|$ can easily reach the scale of billions in real applications; and
(2) training a model relying on probably noisy pseudo-labels may lead to poor optimisation.
To solve these obstacles, we propose a sampling-based learning framework for optimising $\mathcal{L}$.
As the unobserved samples dominate the whole of the user-item pairs,
we aim to efficiently select $\mathcal{I}_u^{-}$ and $\mathcal{I}_u^{\pm}$
for each user $u$ through two sampling strategies.

The expectation of loss function on a mini-batch, $\mathcal{L}_B$, can be expressed as follows:
\begin{eqnarray}
  \notag
  \mathbb{E}\left[\mathcal{L}_B\right]
    = \mathbb{E}_{u \sim Uni(\cdot)}\Bigg[&\,&\mathbb{E}_{i_{+}\sim P^{+}(\cdot|u)}\big[\ell(1,\hat{y}_{u,i_{+}};\Theta)\big] \\\notag
                                     &+&\mathbb{E}_{i_{-}\sim P^{-}(\cdot|u)}\big[\ell(0,\hat{y}_{u,i_{-}};\Theta)\big] \\
                                     &+&\mathbb{E}_{i_{\pm}\sim P^{\pm}(\cdot|u)}\big[\ell(\hat{l}_u(i_{\pm}),\hat{y}_{u,i_{\pm}};\Theta)\big]\Bigg]
\end{eqnarray}
where $P^{+}(i_{+}|u)$, $P^{-}(i_{-}|u)$ and $P^{\pm}(i_{\pm}|u)$ are the conditional distributions of the observed, unobserved, and pseudo-labelled items for $u$, respectively.
We set the distribution of users in the loss function to a uniform distribution so that each user contributes equally.
For observed data, we also utilise a uniform distribution as $P^{+}(i_{+}|u)$ to sample an observed item for a user.
The density of $P^{-}(i_{-}|u)$ and $P^{\pm}(i_{\pm}|u)$ are corresponding to weights $\beta_{u,i_{-}}$ and $\alpha_{u,i_{\pm}}$, respectively.

\subsection{Sampling Based on Knowledge Graph and Popularity\label{sampling-opt}}
\subsubsection{KG-Aware Item Sampling for Pseudo-Labelling\label{kgpl}}
To augment accurately labelled items for cold-start users through pseudo-labelling,
we sample items based on the graph structure centred on the observed user-item pairs.
The key idea to sample the items for pseudo-labelling is that,
for the items that can be reached through meta-paths (i.e. the paths rooted at a user's interacted items in a KG),
we can assign reliable pseudo-labels to the items for the user based on the knowledge learnt from observed samples; moreover, such items are probably positive items as they share entities with the positive items for the user.

To find items which we can assign reliable personalised pseudo-labels,
we count the number of paths to an item from the positive items for a user.
Suppose that $\mathcal{I}_u^{+}$ is the set of observed items that $u$ has interacted with.
We list a set of item-to-item paths from an observed item $i_{+} \in \mathcal{I}_u^{+}$ to an unobserved item $i_{\pm} \in \mathcal{I}\setminus\mathcal{I}_u^{+}$ as $T_{i_{+}i_{\pm}}$.
We employ the $h$-hop breadth-first search (BFS) for searching the paths rooted at the observed items for a user.
Based on these paths, we sample an unobserved item $i_{\pm}$ for $u$ according to the sampling distribution $P^{\pm}(i_{\pm}|u)$ that has the following probability density:
\begin{eqnarray}
  q(i_{\pm}|u) = \frac{n_{u,i_{\pm}}^{a}}{\sum_{i \in \mathcal{I}\setminus\mathcal{I}_u^{+}} n_{u,i}^{a}}, \,\,\,\, n_{u,i_{\pm}} = \sum_{i_{+} \in \mathcal{I}_u^{+}}|T_{i_{+}i_{\pm}}|
\end{eqnarray}
where $n_{u,i_{\pm}}$ is the number of paths,
and $a \in \mathbb{R}$ is a hyper-parameter to control the skewness of the sampling distribution; $P^{\pm}(i_{\pm}|u)$ becomes close to a uniform distribution with small $a$.
To ensure the coverage of item candidates to be labelled, we set $n_{u,i}=0.5$ for item $i$ that is unreachable through the $h$-hop BFS.

\subsubsection{Popularity-Aware Negative Sampling\label{popns}}
Uniformly sampling negative items as in conventional works~\cite{RippleNet,wang2019multi,wang2019knowledge2,KGAT} can reinforce biases toward the popularity in practical settings.
Because negative sampling extracts unobserved items as a negative instance for a user,
cold-start items, i.e., items with few interactions, are unobserved items for most users.
Thus, cold-start items are more likely to be selected by negative sampling than popular items.
This bias toward popularity can hurt performance, particularly for cold-start items and, thus, the quality of pseudo-labels for cold-start items.
In light of this consideration, we adopt a frequency-based strategy for negative sampling distribution $P^{-}(i_{-}|u)$,
as in conventional methods~\cite{rendle2014improving,he2016fast}.
We sample negative items from $\mathcal{I}\setminus\mathcal{I}_u^{+}$ according to the following probability:
\begin{eqnarray}
  \label{popns-density}
  p(i_{-}|u) = \frac{m_{u,i_{-}}^{b}}{\sum_{i \in \mathcal{I}\setminus\mathcal{I}_u^{+}}m_{u,i}^{b}}
\end{eqnarray}
where $m_{u,i_{-}}$ is the number of observed interactions for item $i_{-}$,
and $b$ controls the importance of frequency.

\subsubsection{Mini-Batch Sampling Strategy\label{mb-sampling}}
In the training phase, we construct mini-batches by utilising the aforementioned sampling distributions.
It should be noted that we sample an unobserved pair and determine its pseudo-label on the fly;
each set of unobserved samples for pseudo-labelling is generated after sampling a mini-batch from the observed data $\mathcal{I}_u^{+}$.
Moreover, we ensure that a mini-batch contains three samples for a user, namely, positive, negative, and pseudo-labelled samples
to ensure the class balance in a mini-batch for a user.
Algorithm~\ref{alg:kapl} describes our mini-batch sampling strategy.

\begin{algorithm}[t]
  \caption{Mini-batch sampling algorithm}
  \label{alg:kapl}
  \begin{algorithmic}[1]
    \REQUIRE{Interaction matrix $\bf Y$, KG $\mathcal G$, Model $f$}
    \ENSURE{Mini-batch $\mathcal B$}
    \STATE $\mathcal B \leftarrow \emptyset$
    \FOR{1/2 number of samples in a mini-batch}
      \STATE Sample a user by $u \sim Uni(\cdot)$
      \STATE Sample an observed item by $i_{+} \sim P^{+}(\cdot|u)$
      \STATE Sample a negative item by $i_{-} \sim P^{-}(\cdot|u)$;
      \STATE Sample an item for pseudo-labelling by $i_{\pm} \sim P^{\pm}(\cdot|u)$
      \STATE Compute pseudo-label $\hat y_{u,i_{\pm}}$
      \STATE Assign the pseudo-label as $\hat{l}_{u,i_{\pm}} \leftarrow \hat y_{u,i_{\pm}}$
      \STATE $\mathcal B \leftarrow \mathcal B \cup \{(u, i_{+}, 1), (u, i_{-}, 0), (u, i_{\pm}, \hat{l}_{u,i_{\pm}})\}$
      \ENDFOR
    \RETURN $\mathcal B$
  \end{algorithmic}
\end{algorithm}

\subsection{Co-training for Noisy Pseudo-Labels\label{co-training}}
Training a model on pseudo-labels that were generated by the model itself can make the optimisation unstable.
To realise more robust optimisation, we introduce a co-training approach~\cite{blum1998combining,qiao2018deep,han2018co}.
In our co-training approach, we train two models, $f$ and $g$, while ensuring that each of them is trained on the samples labelled by the other model.
This technique empirically improves the robustness of optimisation using pseudo-labelling in our experiments.
A brief explanation of the learning algorithm is as follows.
\begin{enumerate}
\item Sample two mini-batches $\mathcal{B}_f$ and $\mathcal{B}_g$. Pseudo-labels of $\mathcal{B}_f$ and $\mathcal{B}_g$ are given by $f$ and $g$, respectively.
\item Compute gradients of the loss functions and update $f$ on $\mathcal{B}_g$ and $g$ on $\mathcal{B}_f$.
\end{enumerate}
Therefore, the loss functions for $f$ on $\mathcal{B}_g$ is defined as:
\begin{eqnarray}
  \mathcal{L}_{B}^{(f)} &=& \sum_{(u, i, l_{u,i}^{(g)}) \in \mathcal{B}_{g}}\ell\left(l_{u,i}^{(g)}, \hat{y}_{u,i}^{(f)};\Theta_f\right)
\end{eqnarray}
where $l_{u,i}^{(g)}$ is the label determined by $\hat{l}_{u}(i)$ in Eq.~(\ref{label-function}) for user $u$ and item $i$ based on the prediction of $g$ (see also Algorithm~\ref{alg:kapl}).
For training $g$, we also optimise $\mathcal{L}_{B}^{(g)}$ on $\mathcal{B}_f$.
Throughout this paper,
we utilise only $f$ as the final model to predict $\bf Y$ and do not choose or ensemble the models for a fair comparison of methods even there are two well-trained models after the training procedure.

\section{Experimental Settings}
\subsection{Baselines\label{baseline}}
We select state-of-the-art KG-based recommenders as the baselines, namely, RippleNet, MKR, KGAT, and KGNN-LS; besides, we introduce a naive baseline based on item popularity, TopPopular.
\begin{itemize}[leftmargin=*]
\item\textbf{RippleNet}~\cite{RippleNet}: This leverages multi-hop paths rooted at each user in a KG to enrich their representations and employs matrix factorisation on the representations.

\item\textbf{MKR}~\cite{wang2019multi}: This introduces a multi-task learning algorithm for recommendation and graph translation to enhance a recommender with translated graph embeddings.

\item\textbf{KGAT}~\cite{KGAT}: This is a KG-based recommender, which employs GNN on a KG to generate the representations of users and items. This employs a pairwise loss function that optimises user wise recall directly.

\item\textbf{KGNN-LS}~\cite{wang2019knowledge2}: This is also a GNN-based recommender, which employs a regularisation technique based on the label-smoothness assumption. This adopts a point-wise loss function that does not require extensive negative sampling.

\item\textbf{TopPopular}~\cite{dacrema2019we}: This is a non-personalised baseline that ranks items in the order of popularity, i.e., the number of users who have interacted with the item, in the train and validation splits.

\end{itemize}

Throughout our experiments, we conduct model selection for each method based on R@10 computed on the validation split.

\subsection{Datasets\label{dataset}}
We utilise three public datasets in our experiments;
(a) MovieLens1M\footnote{\url{https://grouplens.org/datasets/movielens/}}; (b) Last.FM\footnote{\url{https://grouplens.org/datasets/hetrec-2011/}}; and (c) BookCrossig\footnote{\url{http://www2.informatik.uni-freiburg.de/~cziegler/BX/}}.
KG data is available in public\footnote{https://github.com/hwwang55} and built upon Satori\footnote{https://searchengineland.com/library/bing/bing-satori}.

The statistics of the three datasets are listed in Table~\ref{table:statistics}.
The number of interactions in Table~\ref{table:statistics} indicates only those of the observed samples.
We observe that the three datasets have different levels of sparsity:
it is 2.66\%, 0.294\% and 0.026\% for MovieLens1M, Last.FM, and BookCrossing, respectively.

We split each dataset into training, validation and test splits at the ratio of 6:2:2.
For all datasets, we keep all the observed samples as implicit feedback.
Note that we created the negative samples for evaluation splits (i.e. validation and test splits)
while ensuring that those examples are unobserved in the entire dataset.
By contrast, because we consider implicit settings wherein we cannot observe true negative samples,
we randomly create negative samples for training
so that the negative samples are unobserved in the training and validation splits.
Thus, some negative samples for training can be positive in the test split.

\begin{table}[t]
  \centering
  \caption{Statistics of the datasets: MovieLens1M, Last.FM, and BookCrossing.}
  \begin{tabular}{c|c|c|c}
    \hline
    & MovieLens1M & Last.FM & BookCrossing\\
    \hline
    \# users        & 6,036   & 1,872     & 17,860  \\
    \# items        & 2,347   & 3,846     & 14,967  \\
    \# interactions & 376,886 & 21,173    & 69,873  \\
    \# sparsity     & 2.66\%  & 0.294\%   & 0.026\%  \\
    \# entities     & 102,569 & 9,366     & 77,903  \\
    \# relations    & 32      & 60        & 25      \\
    \# KG triples   & 499,474 & 15,518    & 151,500 \\
    \hline
  \end{tabular}
  \label{table:statistics}
\end{table}

\subsection{Implementation Details}
For our proposed KGPL, the number of convolutional layers $L$ is chosen from $\{1,2\}$,
and the dimensionality of latent space $d_l$ is 64 for all three datasets.
The sampled neighbour size is 32, 32, and 8 for MovieLens1M, Last.FM, and BookCrossing, respectively.
The depth of BFS, $h$, is 5, 6, and 6 for MovieLens1M, Last.FM, and BookCrossing, respectively.
The dropout ratio is tuned in ${0.1,0.2,\dots,0.8}$.
$a$ and $b$ are tuned in $\{10^{-3},10^{-2},0.1,\dots,1.0\}$ and $\{10^{-3},10^{-2},0.1,\dots,1.0\}$.
The learning rate is tuned in $\{1e-3,2e-3,\ldots,1e-2\}$, and the batch size is in $\{3333,6666,9999\}$.

\begin{table*}[h]
  \centering
    \caption{Results of $Precision@K$ and $Recall@K$ in top-$K$ recommendation.}
  \setlength{\tabcolsep}{1.5pt}
  \label{tbl:fulleval}
  \begin{tabular}{c|cccc|cccc|cccc|cccc|cccc|cccc}
    \hline
    Model & \multicolumn{8}{c|}{MovieLens1M} & \multicolumn{8}{c|}{Last.FM} & \multicolumn{8}{c}{BookCrossing} \\ \hline
    Measure
    & \multicolumn{4}{c|}{\textit{Precision@K}} & \multicolumn{4}{c|}{\textit{Recall@K}}
    & \multicolumn{4}{c|}{\textit{Precision@K}} & \multicolumn{4}{c|}{\textit{Recall@K}}
    & \multicolumn{4}{c|}{\textit{Precision@K}} & \multicolumn{4}{c}{\textit{Recall@K}} \\ \hline
    $K$
    & \textit{10} & \textit{20} & \textit{50} & \textit{100} & \textit{10} & \textit{20} & \textit{50} & \textit{100}
    & \textit{10} & \textit{20} & \textit{50} & \textit{100} & \textit{10} & \textit{20} & \textit{50} & \textit{100}
    & \textit{10} & \textit{20} & \textit{50} & \textit{100} & \textit{10} & \textit{20} & \textit{50} & \textit{100} \\ \hline
    TopPopular
    & .125 & .102 & .070 & .051 & .113 & .186 & .310 & .430
    & .029 & .023 & .014 & .010 & .122 & .194 & .288 & .386
    & \textbf{.017} & \textbf{.011} & \textbf{.006} & \textbf{.005} & \textbf{.083} & \textbf{.101} & \textbf{.143} & \textbf{.186} \\
    RippleNet~\cite{RippleNet}
    & .125 & .100 & .070 & .052 & .113 & .183 & .307 & .434
    & .030 & .023 & .014 & .009 & .125 & .195 & .291 & .391
    & .014 & .009 & .005 & .004 & .069 & .086 & .117 & .150 \\
    MKR~\cite{wang2019multi}
    & .123 & .100 & .069 & .051 & .110 & .182 & .303 & .425
    & .029 & .022 & .014 & .010 & .121 & .181 & .293 & .397
    & .013 & .008 & .004 & .003 & .067 & .080 & .100 & .118 \\
    KGAT~\cite{KGAT}
    & \textbf{.188} & \textbf{.148} & \textbf{.100} & .069 & \textbf{.184} & .280 & .452 & .\textbf{603}
    & .046 & .034 & .020 & .013 & .186 & .272 & .398 & .506
    & .008 & .006 & .004 & .003 & .044 & .059 & .093 & .132 \\
    KGNN-LS~\cite{wang2019knowledge2}
    & .139 & .113 & .080 & .058 & .121 & .195 & .335 & .475
    & .029 & .022 & .014 & .009 & .122 & .182 & .289 & .386
    & .015 & .010 & .006 & .004 & .072 & .090 & .130 & .166 \\
    \hline
    KGPL
    & .177 & .144 & .099 & .069   & .183  & \textbf{.282} & \textbf{.454} & .602
    & \textbf{.054} & \textbf{.039} & \textbf{.023} & \textbf{.014} & \textbf{.221} & \textbf{.314} & \textbf{.452} & \textbf{.557}
    & .015 & .010 & .006 & .004 & .074 & .092 & .125 & .168 \\
    \hline
  \end{tabular}
\end{table*}

\begin{figure*}[h]
  \centering
  \includegraphics[clip,width=\linewidth]{all_user_group_stack_.pdf}
  \caption{R@10 for Four User Groups with Different Sparsity Levels in (a) MovieLens1M, (b) Last.FM, and (c) BookCrossing.}
  \label{fig:user-group-stack}
\end{figure*}

\section{Experimental Results\label{result-section}}
\subsection{Overall Comparison with Baselines\label{main-result}}
We compare our method and the baseline methods
in terms of overall performance.
To compare the multiple recommenders,
we carefully conducted statistical significance testing through a paired Tukey HSD test with 95\% confidence intervals for each dataset in terms of R@10
and report the results also with effect sizes (Hedge's $g$) accordingly~\cite{brashlerCLEF01,sakai2018laboratory}.

Table~\ref{tbl:fulleval} lists the precision and recall ($k=10,20,50,100$) of each method on the three datasets.
Remarkably, on BookCrossing, TopPopular performs better than the other methods including ours, whereas only KGAT and MKR are statistically significantly worse than TopPopular ($p \leq2\mathrm{e}\mbox{-}16$, $g=0.104$ and $p=0.016$, $g=0.070$, respectively).
BookCrossing is an extremely sparse dataset,
and there are many users with only one observed interaction in the training split.
Thus, personalising recommendation may be challenging, and TopPopular is a strong baseline just by exploiting popularity bias.
We also find that RippleNet, MKR and KGNN-LS perform similarly to TopPopular on the other datasets.
We will investigate these observations more in Section~\ref{sec:item-side analysis}.

While KGPL outperforms the other methods on Last.FM,
KGPL performs slightly worse than KGAT for MovieLens1M; however, the difference between KGPL and KGAT is not statistically significant ($p=1.0$, $g=0.005$ and $p=0.635$, $g=0.047$ for MovieLens1M and Last.FM).
In BookCrossing, the performance of KGPL is rather limited.
This is because KGPL cannot take the benefits of pseudo-labelling on the extremely sparse dataset.

Overall, KGPL can consistently achieve comparative performance with the best model in each dataset.
Our baseline TopPopular also reveals a challenge in the personalised recommendation on severely sparse datasets.
It is also remarkable that KGPL shows significant improvement from KGNN-LS, which has almost the same neural network architecture as KGPL,
in MovieLens1M and Last.FM ($p\leq2\mathrm{e}\mbox{-}16$, $g=0.343$ and $p\leq2\mathrm{e}\mbox{-}16$, $g=0.354$).
This performance boost validates the effectiveness of our proposed method.

\subsection{Analysis on Users with Different Sparsity\label{user-group-result}}
For a more detailed comparison of the methods,
we created four groups of users with different sparsity levels according to the number of observed samples for each user in the training split
with thresholds of 25\%, 50\%, 75\%, and 100\% as in the previous work~\cite{KGAT}.
Figure~\ref{fig:user-group-stack} (a)--(c) demonstrate R@10 of each method for each user group for the datasets of (a) MovieLens1M, (b) Last.FM and (c) BookCrossing.
Each bin corresponds to a group of users whose interactions is less than $x$. We set the threshold $x$ to 25\%, 50\%, 75\%, and 100\% percentile.
Therefore, the most left groups are cold-start users, and the most right ones show the performance on the whole users.
In Figure~\ref{fig:user-group-stack}~(a),
we can observe that KGAT and KGPL achieve consistently higher R@10 than the other methods for each user group.
Although KGPL performs slightly worse than KGAT in terms of overall performance ($|\mathcal{I}_u^{+}|<717$),
it achieves higher R@10 in the user group with the severe sparsity level ($|\mathcal{I}_u^{+}|<15$, $|\mathcal{I}_u^{+}|<32$, and $|\mathcal{I}_u^{+}|<66$).
In Figure~\ref{fig:user-group-stack}~(b),
KGPL performs best for three user groups ($|\mathcal{I}_u^{+}|<7$, $|\mathcal{I}_u^{+}|<9$, and $|\mathcal{I}_u^{+}|<24$),
and there is substantial improvement particularly for cold-start users ($|\mathcal{I}_u^{+}|<7$).
Figure~\ref{fig:user-group-stack}~(c) shows a similar trend.
It is remarkable that TopPopular shows extremely high performance for cold-start users and performs poorly for non-cold-start users in BookCrossing.
This result implies that the observed data for cold-start users (i.e. less frequent users in the observed dataset) is biased toward popularity.

As a summary,
KGPL can successfully adapt to various sparsity levels of datasets and shows improvements in performance, particularly for cold-start users.
The improvement of KGPL is relatively large for Last.FM, whereas those for MovieLens1M and BookCrossing are mild.
The results suggest the advantage and limitation of KGPL;
it can prove its merits for real-world datasets, yet the gain is rather mild for dense or highly sparse datasets (e.g. MovieLens1M and BookCrossing) in terms of overall performance.

\section{In-Depth Analyses}
As our main concern is the performance for cold-start users or items,
we investigate the behaviours of the baseline recommenders and KGPL for users and items with different frequencies (i.e. the number of observed data) from different angles in this section.

\subsection{User-Side Performance Analysis\label{win-analysis}}
We analyse how many users can benefit from each recommender
rather than the overall average of R@10.
To this end, for each user in the test split,
we record a \emph{winner system} which achieves the highest R@10.
If there are ties, we choose all of the tied systems as winners
while we do not choose any systems when the R@10 of all systems is 0.0.
Then, for each system, we count the number of wins for all users.
As we hypothesised that our pseudo-labelling is effective for alleviating user-side cold-start problems,
we also consider a variant of KGPL, $\mbox{KGPL}_{nopl}$, which does not augment labels through pseudo-labelling.

Figure~\ref{fig:freq-vs-win} shows the number of wins for each method
when the upper bound of the number of observed interactions for a user is varied.
The $x$- and $y$-axes in the figure indicate the number of observed interactions in the training split
and the cumulative number of wins for the set of users with, at most, $x$ interactions, respectively.
The inset shown in each part shows the result for users with less than 10 interactions,
and the $y$-axis is shown with a logarithmic scale.
In Figure~\ref{fig:freq-vs-win} (a),
KGAT and KGPL outperform the other methods as in the results of Section~\ref{result-section},
while KGPL can achieve better performance for more cold-start users than KGAT (see the small figure in Figure~\ref{fig:freq-vs-win} (a)).
Figure~\ref{fig:freq-vs-win} (b) also demonstrates the advantage of KGPL;
in addition to cold-start users, KGPL shows substantial improvement also in users with more than ten interactions.
This result is intuitive because KGPL can augment pseudo-positive samples more precisely for heavy users.
The comparison between KGPL and $\mbox{KGPL}_{nopl}$ in MovieLens1M and Last.FM demonstrates
the effectiveness of our pseudo-labelling approach.
In BookCrossing, KGPL achieves slightly better performance particularly for cold-start users than the other KG-aware methods,
whereas TopPopular performs best among all of the methods.

Based on these results, we conclude that
our KGPL can provide better recommendation results for a wide range of users through the proposed pseudo-labelling approach.
However, the results on BookCrossing reveals that developing a recommender for extremely sparse datasets is still challenging even with KGs.

\subsection{Item-Side Performance Analysis}
\label{sec:item-side analysis}
The effectiveness of the popularity-based method (i.e. TopPopular) indicates that the popularity of items is a strong clue in recommendation problems.
Nevertheless, a method heavily relying on popularity may impede the collection of informative users' feedback
by narrowing the coverage of exposed items.
Therefore, we examine the coverage of items in the ranked lists by each method.

\begin{figure*}[t!]
    \centering
    \includegraphics[clip,width=0.9\linewidth]{win_plot_.pdf}
    \caption{Cumulative number of wins for users with different number of observed interactions.
     }
    \label{fig:freq-vs-win}
\end{figure*}
\begin{figure*}[htpb]
    \centering
    \includegraphics[clip,width=\linewidth]{item_plot.pdf}
    \caption{Analysis of item coverage in the ranked lists.
      Each row from the top shows the results on MovieLens1M, Last.FM and BookCrossing, respectively.}
    \label{fig:item-coverage}
\end{figure*}

To this end, we calculate the number of unique items ranked at least once in a top-$K$ ranking for a user as relevant items.
We also check the number of unique items in the top-$K$ rankings regardless of relevance.
Figure~\ref{fig:item-coverage} shows the results in the three datasets,
and each row from the top is corresponding to MovieLens1M, Last.FM, and BookCrossing, respectively.
Columns from the left side in each row indicate
(a) the number of ranked unique items;
(b) the number of unique items that are ranked as relevant at least once;
(c) the median frequency of ranked unique items; and
(d) the median frequency of relevant items.
A large number of unique items in the ranked lists indicates that the method provides highly personalised results.
TopPopular shows the lowest coverage and highest median frequency of items as it provides identical results for all users based on popularity.
To examine the proposed negative sampling strategy, we test another variant of KGPL, $\mbox{KGPL}_{uns}$, which samples negative instances according to a uniform distribution.

In MovieLens1M,
the coverage of items of KGPL is higher than those of the other methods with/without regard to the relevance of items (see the first row and columns (a) and (b)).
KGPL also show lower values for the median frequency of ranked items (the first row in columns (c) and (d)).
This suggests that KGPL tries to pull up less popular but relevant items.
In Last.FM (the second row of Figure~\ref{fig:item-coverage}),
KGAT and KGPL show a similar coverage of ranked items (column (a));
however, KGPL achieves clearly a higher coverage for relevant items than that of KGAT (column (b)).
In terms of the median frequency of items, KGPL exhibits a lower median frequency of the relevant items as in MovieLens1M.
These results indicate that KGPL successfully adjust recommendation results for users,
whereas it slightly underperforms KGAT in MovieLens1M (discussed in Section~\ref{result-section}).

The results of BookCrossing show a different trend.
Based on columns (a) and (b) in the third row, KGAT shows the highest coverage,
and the median frequency of ranked relevant items is consistently smaller than those of the other methods.
However, it should be noted that KGAT compromises the overall accuracy in BookCrossing (Section~\ref{result-section})
and ranks nonrelevant items more in its top-K results.
KGPL shows a higher coverage of relevant/nonrelevant items than RippleNet, MKR, and KGNN-LS (column (a)),
but for relevant items, the coverage of KGPL is almost the same as those of the other three methods.
These results imply that KGPL captures the popularity bias in BookCrossing
and compromises the coverage of items.
This result is reasonable because the relevant items in BookCrossing are extremely biased by their popularity.

Comparison of KGPL and its variants show some positive effects of the popularity-aware negative sampling and pseudo-labelling on the coverage of items. By comparing $\mbox{KGPL}_{nopl}$ and KGPL, we observe that pseudo-labelling improves the coverage of items in MovieLens1M and Last.fm.
In MovieLens1M, $\mbox{KGPL}_{uns}$ shows a drop in coverage.
Without adjusting the distribution for negative sampling, KGPL relies on popularity biases and thus loses the personalised results.
For BookCrossing, due to its extreme sparsity, KGPL and its variants fail to personalise the recommendation results.
BookCrossing also has a strong popularity bias; thus the diversity of items and the accuracy of recommendation are in a relation of a trade-off to some extent. This prevents KGPL from improving the coverage of items.

For BookCrossing and Last.FM,
the item coverage of RippleNet, MKR and KGNN-L is relatively low (see columns (a) and (b)),
and the median frequency of items is high.
In particular, for Last.FM,
these three methods show extremely low coverage and high median frequency of relevant items,
and the overall performance of these methods is similar to that of TopPopular (Section~\ref{result-section}).
These results imply these methods collapse to TopPopular and excessively exploit the popularity bias when a dataset is sparse.

\section{Ablation Analysis}
KGPL comprises three main components:
(1) mini-batch augmentation through pseudo-labelling;
(2) knowledge-aware item sampling for pseudo-labelling; and
(3) co-training approach for stable training.
To demonstrate the effectiveness of each component,
we conduct ablation studies by comparing KGPL with its variants:
\begin{itemize}
\item $\mbox{KGPL}_{nopl}$: KGPL without the pseudo-labelling.
\item $\mbox{KGPL}_{rand,self}$: KGPL without the knowledge-aware sampling strategy and co-training technique.
\item $\mbox{KGPL}_{kapl,self}$: KGPL without the co-training technique.
\item $\mbox{KGPL}_{rand,cot}$: KGPL without the knowledge-aware sampling.
\item $\mbox{KGPL}_{kapl,cot}$: The full model of KGPL.
\end{itemize}
Figure~\ref{fig:curve_ablation} shows the curve of the validation R@10 of each KGPL variants in the training process in the Last.FM dataset.
Table~\ref{table:ablation_table} lists the precision and recall results for $k=10,20,50,100$ of each KGPL variants in the Last.FM dataset.

\subsection{Effects of the Co-Training}
Comparison between $\mbox{KGPL}_{rand,self}$ (blue line in Figure~\ref{fig:curve_ablation}) and $\mbox{KGPL}_{rand,cot}$ (grey line) demonstrate that only the co-training technique achieves substantial performance gain.
The same trend can be observed between $\mbox{KGPL}_{kapl,self}$ (purple line) and $\mbox{KGPL}_{kapl,cot}$ (yellow line).
Therefore, the co-training technique consistently improves performance.

\subsection{Effects of the Knowledge-Aware Item Sampling}
Pseudo-labelling without knowledge-aware sampling $\mbox{KGPL}_{rand,self}$ (blue line) performs poorly and even worse than the model without pseudo-labelling $\mbox{KGPL}_{nopl}$ (red line).
Solely introducing knowledge-aware sampling does not make full use of pseudo-labelling.
$\mbox{KGPL}_{kapl,self}$ (purple line) still does not outperform $\mbox{KGPL}_{nopl}$.
By contrast, when the co-training technique is used, knowledge-aware sampling provides a substantial performance lift as $\mbox{KGPL}_{rand,cot}$ (grey line) and $\mbox{KGPL}_{kapl,cot}$ (yellow line) show.
The knowledge-aware sampling enhances the stability of the training on pseudo-labels, and the performance gain is substantial particularly when used with the co-training approach.

\begin{table}[t!]
  \centering
  \caption{Comparison of KGPL and its ablated variants.}
\setlength{\tabcolsep}{2pt}
\small
  \begin{tabular}{c|cccc|cccc}
    \hline
    Measure & \multicolumn{4}{c}{\textit{Precision@K}} & \multicolumn{4}{c}{\textit{Recall@K}} \\\hline
    $K$      & \textit{10} & \textit{20} & \textit{50} & \textit{100} & \textit{10} & \textit{20} & \textit{50} & \textit{100} \\
    \hline
    $\mbox{KGPL}_{nopl}$
    & .048 & .033 & .016 & .006 & .209 & .304 & .437 & .522 \\
    $\mbox{KGPL}_{rand,self}$
    & .050 & .037 & .022 & .013 & .204 & .298 & .436 & .531 \\
    $\mbox{KGPL}_{kapl,self}$
    & .051 & .037 & .022 & .013 & .208 & .303 & .436 & .537 \\
    $\mbox{KGPL}_{rand,cot}$
    & .052 & .036 & .018 & .009 & .216 & .317 & .448 & .545  \\
    $\mbox{KGPL}_{kapl,cot}$
    & .054 & .039 & .023 & .014 & .221 & .314 & .452 & .557 \\
    \hline
  \end{tabular}
  \label{table:ablation_table}
\end{table}

\begin{figure}[htpb]
    \centering
    \includegraphics[height=4.0cm]{ablation.pdf}
    \caption{Training process of KGPL and its variants.}
    \label{fig:curve_ablation}
\end{figure}

\subsection{Hyper-Parameter Sensitivity}
KGPL has two hyper-parameters $a$ and $b$, which
control the skewness of sampling distributions for pseudo-labelling and negative sampling, respectively.
Figure~\ref{fig:hyperparam-analysis} shows the effect of $a$ and $b$ on R@10.
In the top figure, we observe that KGPL is highly stable for the value of $a$;
In the range from 0.7 to 0.4, KGPL consistently achieves high R@10.
The result suggests that both exploitation and exploration are important in the sampling of items for pseudo-labelling.
The figure shows that KGPL deteriorates substantially with a large $b$.
Sampling negatives with a large $b$ chooses popular items more as negatives,
and can impede the exploitation of the popularity bias.

\begin{figure}[htpb]
    \centering
    \includegraphics[height=2.7cm]{hyper.png}
    \caption{Impact of hyper-parameter $a$ and $b$.}
    \label{fig:hyperparam-analysis}
\end{figure}

\section{Conclusion}
We have proposed a KG-aware recommender, KGPL, for alleviating cold-start problems for both users and items.
Our method incorporates pseudo-labelling
to explicitly leverage unobserved samples as weak positive/negative instances.
To enhance the training procedure with pseudo-labelled samples,
we have developed a KG-aware sampling strategy and a co-training approach in which two different models provide supervisions with each other.

The experimental results demonstrate that our KGPL achieves performance comparable with state-of-the-art KG-aware recommenders in the multiple datasets.
KGPL outperforms the other methods, particularly for cold-start users and items.
Our extensive analyses indicate that KGPL provides more personalised recommendation results and discovers relevant items more from cold-start items than the baselines without compromising overall performance.

As future work,
we would like to explore an adaptive sampling for pseudo-labelling such as that presented by Wang~\emph{et al.}~\cite{KGPolicy20}.
It would also be interesting to investigate the connectivity between GNNs with many convolutional layers
and our proposed pseudo-labelling approach;
our method may help to propagate gradients from observed samples to unobserved ones, and therefore examining architectures such as residual networks may be insightful for solving cold-start problems by GNNs.
Combining our approach and recent non-sampling learning methods~\cite{chen2020jointly} is also interesting; our approach can provide adaptive weights for each user-item entry in their loss function with model predictions.