# End-to-End Video Classification with Knowledge Graphs

Fang Yuan, Zhe Wang, Jie Lin, Luis Fernando D’Haro, Kim Jung Jae, Zeng Zeng,
Vijay Chandrasekhar
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
Institute for Infocomm Research, Singapore

###### Abstract

Video understanding has attracted much research attention especially since the
recent availability of large-scale video benchmarks. In this paper, we address
the problem of multi-label video classification. We first observe that there
exists a significant _knowledge gap_ between how machines and humans learn.
That is, while current machine learning approaches including deep neural
networks largely focus on the representations of the given data, humans often
look beyond the data at hand and leverage external knowledge to make better
decisions. Towards narrowing the gap, we propose to incorporate external
knowledge graphs into video classification. In particular, we unify
traditional “knowledgeless” machine learning models and knowledge graphs in a
novel end-to-end framework. The framework is flexible to work with most
existing video classification algorithms including state-of-the-art deep
models. Finally, we conduct extensive experiments on the largest public video
dataset YouTube-8M. The results are promising across the board, improving mean
average precision by up to 2.9%.

## Introduction

Since the advent of neural networks and deep learning, major breakthroughs
have been made in many artificial intelligence tasks ranging from computer
vision to natural language processing. However, a significant _knowledge gap_
still exist between machine and human intelligence. In particular, humans
often relate to and make use of semantic knowledge outside of the task-
specific data to make better decisions. On the other hand, most machine
learning algorithms including state-of-the-art deep methods, only focus on the
representation of the given data, without leveraging any external knowledge
that could benefit the given task.

Consider the surfing man example in Figure 1(a). By only analyzing the pixels
of the image (i.e., given data), it is difficult to conclude that the man is
on a surfboard since most of it is obsecured by the waves. However, given the
knowledge that a man cannot stand freely on water and surfing is a typical
sport at sea, it is straightforward to identify the surfboard in the picture.
Note that the knowledge crucial to recognizing the surfboard is external to
the raw data. Likewise, in the zoo example in Figure 1(b), with the knowledge
that man-made structures containing polar bears are most likely zoos, the
video can be correctly classified as zoo even though it is not evident from
the appearance of the structure in the frames.

(a) Image from Microsoft COCO22footnotemark: 2

(b) Video frames from YouTube444https://www.youtube.com/

Figure 1: Bridging the knowledge gap between how humans and machines learn in
visual tasks: (a) Recognition of an obscured surfboard in an image; (b)
Classification of zoo where the raw pixels in the video frames do not clearly
indicate a zoo.

In this paper, we study the problem of video classification. In contrast to
traditional “knowledgeless” models, we aim to design an end-to-end “knowledge-
aware” framework that can integrate external knowledge into the learning
process. The incorporation of knowledge is especially critical to large-scale
video classification benchmarks such as the recently released YouTube-8M
dataset (?), which presents two major challenges (?). First, videos can be
very diverse in nature, with vastly different topics (e.g., sports, politics,
entertainment, etc.) and genres (e.g., animation, documentary, etc.). Second,
the class distributions are highly imbalanced, where majority of the classes
have only very few instances. Such diversity and imbalance makes the classes
not easily separable based only on features in the videos. Thus, external
knowledge can play a vital role in complementing the video features to attain
higher classification performance.

More formally, knowledge is often represented as a _knowledge graph_ (?),
modeling each real-world concept as a node, and each semantic relationship
between two concepts as an edge. A toy knowledge graph is illustrated in
Figure 2. In particular, the relationships “person–on top of–surfboard” and
“surfboard–found in–sea” are likely to reinforce the recognition of surfboard
in Figure 1(a); similarly the relationship “polar bear–live in–zoo” could help
with the classification of zoo in Figure 1(b). While knowledge graphs have
already seen widespread use in fields such as Web search and social networks
(?), it has not been integrated into visual tasks including video
classification in a flexible and end-to-end fashion—Most existing knowledge-
aware approaches are either specific to a particular task and model, or
applying external knowledge as a decoupled after-thought, which we will
elaborate in related work.

Figure 2: Toy knowledge graph.

Towards knowledge-aware video classification, we make the following
contributions in this paper.

  * •

We propose to incorporate external knowledge graphs into video classification,
bridging the gap in existing state-of-the-art approaches.

  * •

We unify knowledge graphs and machine learning including deep neural networks
in a novel end-to-end learning framework, which is flexible to work with most
existing learning models.

  * •

We conduct extensive experiments on the largest public video dataset
YouTube-8M, outperforming state-of-the-art methods by up to 2.9% in mean
average precision.

The remainder of this paper is organized as follows. First, we review related
work. Next, we present the proposed approach, followed by experimental
evaluation. Finally, we conclude our paper and lay out directions for future
research.

Figure 3: Overall framework of the proposed end-to-end learning with knowledge
graphs (example video from YouTube).

## Related Work

Video understanding has been an active research area in computer vision.
Significant progress has been made especially since the release of large-scale
benchmarks such as Sports-1M (?), YFCC-100M (?) and YouTube-8M (?).

The problem of video classification is usually addressed at frame or video
levels. The deep bag-of-frames (DBoF) (?) is a typical frame-level approach,
inspired by various classic bag-of-words representations (?; ?). It feeds
frame-level features from randomly sampled input frames into a fully connected
layer, whose parameters are shared across the input frames. Beyond a bag of
frames, a video is naturally a temporal sequence of frames, which can be
modeled using a recurrent neural network. Typically Long Short-Term Memory
(LSTM) cells can be employed to capture long-term dependencies in the temporal
dimension (?). Furthermore, as an alternative to LSTM, Gated Recurrent Unit
(GRU) often achieves comparable if not better performance (?; ?). At video
level, a fixed-length feature vector is often extracted from the frames
through simple aggregation (which we call “aggregation of frame features” or
AoFF). As such, standard classifiers including logistic regression and support
vector machines can be adopted. In particular, the mixture of experts (MoE)
(?) classifier has shown superior empirical performance on video-level
representations (?). In this model, a binary classifier is trained for each
class, which is composed of a set of “experts” or hidden states, and a softmax
function is used to model the probability of selecting an expert. Apart from
frame or video-level features directly extracted from the videos, there is
also initial success in exploiting text features associated with the videos,
such as the accompanied title and keywords in YouTube (?).

All of the above methods are knowledgeless in the sense that they do not
exploit external knowledge. The use of external knowledge is emerging in some
computer vision tasks, including image classification (?), motivation
prediction (?), question answering (?), relationship extraction (?), as well
as object detection (?). However, most of these works are task or model
specific, and thus cannot be easily applied to different scenarios. While the
recent work on object detection (?) can work with any detection models, their
proposed approach is not end-to-end. Rather, it consists of two stages: in the
first stage, object localizations and class probabilities are obtained using
any existing model; in the second stage, the class probabilities are re-
optimized based on a knowledge graph. In particular, the use of knowledge in
the second stage is independent from the first stage, which means there is a
lack of feedback mechanism for the knowledge to directly improve the
parametrization of the existing model.

Finally, knowledge graph is a popular choice to represent external knowledge,
for capturing both concepts and their pairwise relationships. The use of
knowledge graphs have already demonstrated various degrees of success in
machine learning applications including Web search and social media (?). Quite
a number of large-scale knowledge graphs are available commercially or in open
source, which are generally constructed based on human curation (?),
crowdsourcing (?; ?), and distillation from semi-structured (?; ?) or
unstructured data (?; ?). The details of knowledge graph construction is
beyond the scope of this work.

## Proposed Approach

We describe our end-to-end knowledge-aware learning in this section, starting
with some preliminaries, followed by our choice of knowledge representation,
as well as the eventual knowledge-aware classification.

### Preliminaries and notations

Consider a set of pre-defined class labels $\mathcal{L}=\\{1,2,\ldots,L\\}$
and a set of videos $d$. We address the multi-label classification problem for
videos, where each video has one or more ground-truth labels which form a
subset of $\mathcal{L}$. We assume a supervised setting where some training
videos with known ground-truth labels are available. Given a test video with
hidden ground truth, the task is to estimate a series of probabilities
$(p_{1},p_{2},\ldots,p_{L})$ where $p_{i}$ represents the probability of label
$i$ on the video. We can subsequently rank the labels in descending
probability and take the top few as the final output.

In this work, we further assume a knowledge graph. Many off-the-shelf
knowledge graphs (?) exist for our purpose. A knowledge graph is formally a
graph $G=(V,E)$: $V$ is a set of vertices and $E$ is a set of edges between
the vertices. In the context of knowledge graph, each vertice represent a
concept or class label555We use the terms _concept_ and _label_
interchangeably hereafter., and each edge represent a relationship between two
concepts. A typical large-scale knowledge graph often contains millions or
billions of concepts, and hundreds or thousands of different relationship
types.

### Overall end-to-end framework

The overall framework of our proposed end-to-end learning with knowledge
graphs is presented in Figure 3. Given an input video, we can first extract
video and audio feature vectors from each frame. Note that in YouTube-8M, the
pre-extracted video and audio features per frame consist of 1024 and 128
dimensions, respectively, as exemplified in the diagram. The frame-by-frame
feature vectors are then feed into either frame or video-level models, to
produce ultimate input into the classifier. As our main novelty, in addition
to accounting for features from the video instance, our classifier further
integrates a knowledge graph to narrow the knowledge gap between traditional
machine learning and human intelligence. As such, in our running example,
while the man-made structure is not clearly a zoo from the frame pixels, we
are still able to predict it with the help of a knowledge graph, which reveals
the strong semantic tie between polar bears and zoos.

The proposed framework embodies two advantages. First, it enables the
incorporation of most existing video classification algorithms, including both
deep and shallow models. Thus, our framework can be highly flexible, without
being approach or task-specific. Second, the unification with knowledge graphs
happens within an end-to-end framework, which means external knowledge can
directly influence the feature-based models in a feedback loop through
mechanisms such as backpropagation. In contrast, one recent approach for the
related task of object recognition (?) also draws input from knowledge graphs.
However, it is not end-to-end; it consists of two decoupled stages where
external knowledge is independent of the feature-based model. Due to the lack
of a feedback loop, their performance turns out to be unsatisfactory in video
classification.

### Knowledge representation

While external knowledge is commonly represented as graphs, knowledge graphs
are inherently still symbolic and relational. Thus, quantifiable semantics
must be further extracted to enable integration with machine learning models
which typically operate over numerical representations. The notion of
_semantic consistency_ has been used (?) to quantify the strength of semantic
ties between class labels. Generally two labels with high semantic consistency
suggests that they are likely to show up in the same video. For instance,
polar bear and zoo are two semantically consistent concepts, whereas polar
bear and volcano have weak or no semantic consistency.

We can encode semantic consistency in an $L\times L$ matrix $S$, such that
$S_{ij}$ represents the semantic consistency between labels $i$ and $j$,
$\forall ij\in\mathcal{L}^{2}$. In particular, $S_{i}j$ can be established
based on the edges connecting the nodes representing labels $i$ and $j$ on the
knowledge graph. Note that two nodes can be either directly connected by an
edge (e.g., polar bear–zoo), or indirectly through a path of edges (e.g.,
person–surfing–sea), improving the generalization ability for concepts without
any direct edge. There can also exists multiple paths between two labels for
robustness. Intuitively, between two nodes on the knowledge graph, when there
are more paths and these paths are shorter, their semantic consistency is
stronger.

Random walk with restart (?) is a well-known method to realize the above
intuition. Starting from one node representing label $i$, we compute the
probability $R_{ij}$ of reaching another node representing label $j$ through
random walk. The higher probability $R_{ij}$ implies that there are more and
shorter paths from $i$ to $j$ and thus the semantic consistency $S_{ij}$ is
also higher. As $R_{ij}\neq R_{ji}$ in general, but the semantic consistency
matrix $S$ should be symmetric in our context, we adopt the below definition
follow the earlier work (?). We refer readers to existing work (?; ?; ?) on
the computation of random walk probabilities $R_{ij}$.

$\displaystyle S_{ij}=S_{ji}=\sqrt{R_{ij}R_{ji}}$ (1)

It is worth noting that semantic consistency can also be defined based on the
similarity of node embeddings, as enabled by recent representation learning
approaches on graphs (?; ?). However, our proposed approach is orthogonal to
the computation of semantic consistency, which is beyond the scope of this
paper.

Finally, for efficiency it is preferable to make the matrix $S$ sparser, by
only focusing on the largest semantic consistency. To this end, we consider
the $K$-nearest neighbor (KNN) reduction for matrix $S$. A pair of labels $i$
and $j$ are deemed KNN if $S_{ij}$ is one of the largest $K$ elements in the
$i$-th row or $j$-th row of $S$. Subsequently, we simply set $S_{ij}=S_{ji}=0$
iff $i$ and $j$ are not KNN. The resulting matrix is much sparser, as it only
encodes the strongest semantic consistency.

### Knowledge-aware classification

Consider any classifier with a cost function $C$ and model parameters
$\Theta$. For a given video instance, we propose the following knowledge-aware
cost function $K$, where $p_{1},p_{2},\ldots,p_{L}$ encode the label
probabilities of the video and they are functions of $\Theta$.

$\displaystyle
K(\Theta)=C(\Theta)+\lambda\sqrt{\textstyle\sum_{i=1}^{L}\sum_{j<i}S_{ij}(p_{i}-p_{j})^{2}}$
(2)

On the one hand, the original cost function $C$ captures the frame or video-
level features, whether they came from deep models or simple aggregation. On
the other hand, the new term here captures the semantics from the knowledge
graph. For a pair of labels $i$ and $j$, if $S_{ij}$ is large (i.e., the two
labels have strong semantic consistency), minimizing the cost function would
force $p_{i}$ and $p_{j}$ to become similar. That is, it is likely that they
either both appear in the video, or both not appear. In contrast, if $S_{ij}$
is small (i.e., they are not semantically consistent), $p_{i}$ and $p_{j}$
become less constrained by the knowledge graph. Note that the two cost terms,
on the features and knowledge graph respectively, are balanced through a
hyperparameter $\lambda\in(0,\infty)$.

While the above formulation is intuitive, it is not practical for
implementation with standard libraries such as
TensorFlow666https://www.tensorflow.org/. In particular, TensorFlow operations
are organized into a dataflow graph, as illustrated in Figure 4(a) for the
pairwise computation in Equation (2) with $L=4$ and batch size $M=1$ (i.e.,
for a single video). Evidently, the dataflow graph would contain $O(L^{2}M)$
nodes, which is not scalable in terms of the time required to construct this
graph, as well as the memory overhead incurred by storing the computation of
all the intermediate nodes.

(a) Pairwise computations

(b) Matrix computations

Figure 4: TensorFlow computation graphs.

As such, we employ the Laplacian matrix transformation. It has been
established (?) that Equation (2) is equivalent to the following:

$\displaystyle
K(\Theta)=C(\Theta)+\lambda\sqrt{\operatorname{Tr}\left[\mathbf{p}(D-S)\mathbf{p}^{T}\right]}$
(3)

where $D$ is a diagonal matrix such that $D_{ii}=\sum_{j=1}^{L}S_{ij}$ and
$\mathbf{p}=(p_{1},p_{2},\ldots,p_{L})$ is a vector of label probabilities.
Note that $D-S$ is known as the Laplacian matrix. Using matrix computations,
the dataflow graph is greatly simplified as illustrated in Figure 4(b) with
batch size $M=1$. The total number of nodes simply become bounded by $O(M)$,
improving the scalability significantly.

Provided that the original cost function $C$ and $\mathbf{p}$ are
differentiable (which are generally true), our knowledge-aware cost function
is also differentiable, as follows. Thus, it can be optimized with the
gradient descent algorithm.

$\displaystyle\frac{\partial K(\Theta)}{\partial\Theta}$
$\displaystyle=\frac{\partial
C(\Theta)}{\partial\Theta}+\lambda\frac{\partial\sqrt{\operatorname{Tr}\left[\mathbf{p}(D-S)\mathbf{p}^{T}\right]}}{\partial\mathbf{p}}\frac{\partial\mathbf{p}}{\partial\Theta}$
$\displaystyle=\frac{\partial
C(\Theta)}{\partial\Theta}+\lambda\frac{\mathbf{p}(D-S)}{\sqrt{\operatorname{Tr}\left[\mathbf{p}(D-S)\mathbf{p}^{T}\right]}}\frac{\partial\mathbf{p}}{\partial\Theta}$
(4)

## Empirical Evaluation

In this section, we conduct empirical evaluations on the largest public video
classification benchmark to date, namely YouTube-8M. We compare the
performance of our approach against state-of-the-art video classification
models, and further investigate the impact of parameters on the performance,
and finally present some case studies to illustrate the reasons that knowledge
graphs can improve video classification.

### Experimental setup

#### Data

We use the YouTube-8M benchmark777https://www.kaggle.com/c/youtube8m/data, the
largest public dataset for multi-label video classification. It contains over
7 million video instances and a diverse range of 4,716 classes (entities),
with an average of 3.4 labels per video. Pre-extracted and compressed features
at frame and video-levels are available, where the video and audio features
have 1024 and 128 dimensions, respectively.

We employ the off-the-shelf knowledge graph ConceptNet
5888http://conceptnet.io/. Following previous work (?), we only adopt its
English subgraph, and remove self-loops and the so-called “negative”
relationships (e.g., NotDesires, NotCapableOf, Antonym and DistinctFrom).
After these filtering steps, we obtain a knowledge graph with 1.3 million
concepts and 2.8 million relationships. To further compute semantic
consistency, we set the random walk restarting probability to 0.15 as well.

To map the concepts in ConceptNet to class labels, we simply apply exact
string matching. As a result, 1,867 labels that have a path to at least one
other label are found in ConceptNet. To demonstrate the advantage of using
knowledge graphs, we only consider these 1,867 class labels, which cover about
97% the videos. Furthermore, these labels account for almost 80% of all label
frequency. We emphasize that obtaining better concept-class mapping for more
coverage is not the focus of this paper, and the current mapping already
include the majority of the video instances and label occurrences.

We use the given training set for training, and the given validation set for
testing since the ground truth of the original test set is not known.

#### Evaluation metric

For each test video, a ranked list of class labels is produced, and we
consider up to top 20 predictions per video for the following evaluation
metrics.

  * •

Mean average precision (MAP): the mean value of the areas under the precision-
recall curve of each video.

  * •

Hit ratio (HIT): the percentage of test videos with the top one prediction
belonging to the ground truth.

  * •

Global average precision (GAP): area under the precision-recall curve over a
global list of predictions consisting of all the predictions of all videos.

#### Knowledgeless models

Our framework is flexible to integrate knowledge graphs with different
“knowledgeless” models (i.e., models without using external knowledge),
including frame-level deep models and video-level models. Thus, we consider
four different state-of-the-art baseline models, namely, AoFF, DBoF, LSTM and
GRU. For the first three models (?), we use the implementation by
Google999https://github.com/google/youtube-8m; for GRU (?), we use the
implementation by Miech et
al.101010https://github.com/antoine77340/Youtube-8M-WILLOW More details of
these models have been discussed in Related Work. To train the models, we
adhere to the setup in the two studies, as follows.

  * •

AoFF: learning rate 0.01, video-level model.

  * •

DBoF: learning rate 0.01, 30 frames per video.

  * •

LSTM: learning rate 1e-4, cell size 1024, all frames.

  * •

GRU: learning rate 2e-4, cell size 1200, all frames.

Note that MoE classifier is used in all models, with 2 experts and 5 epochs.
We further set a batch size of 1024 for AoFF and 128 for the other three
models.

#### Knowledge-aware models

We name our proposed end-to-end approach E2E. Each of the knowledgeless models
(AoFF, DBoF, LSTM and GRU) can be coupled with knowledge graphs in our E2E
framework. We use $K=5$ for the KNN reduction of the semantic consistency
matrix, and $\lambda=0.01$ for the trade-off between feature-based cost and
knowledge-based cost, which are generally robust values with stable
performance. We will vary these hyperparameters to study their impact on the
performance as well.

We also compare to a previous knowledge-aware method (?). This method is
originally designed for object detection in images, which can be adapted for
multi-label video classification as well. It involves two stages, where the
first stage uses an existing knowledgeless model, and the second stage uses a
knowledge graph two re-optimize the output from the first stage. Thus, the two
stages are independent and their approach is not end-to-end. We name this
method 2STG. We use $K=5$ for KNN as well, and choose $\epsilon=0.9$ which is
found to be the best setting.

### Comparison of performance

| AoFF | DBoF | LSTM | GRU
---|---|---|---|---
| MAP | HIT | GAP | MAP | HIT | GAP | MAP | HIT | GAP | MAP | HIT | GAP
- | 0.370 | 0.846 | 0.810 | 0.287 | 0.834 | 0.791 | 0.279 | 0.838 | 0.800 | 0.337 | 0.856 | 0.823
2STG | 0.364 | 0.841 | 0.804 | 0.286 | 0.830 | 0.787 | 0.275 | 0.838 | 0.797 | 0.331 | 0.855 | 0.819
E2E | 0.384 | 0.849 | 0.817 | 0.301 | 0.847 | 0.794 | 0.296 | 0.854 | 0.808 | 0.340 | 0.857 | 0.824
(+1.4%) | (+0.3%) | (+0.7%) | (+1.4%) | (+1.3%) | (+0.3%) | (+1.7%) | (+1.6%) | (+0.8%) | (+0.3%) | (+0.1%) | (+0.1%)
Table 1: Performance comparison between E2E and 2STG across four state-of-the-art knowledgeless methods. The first row records the performance of the knowledgeless models; the second row records the performance of 2STG that adopts the corresponding knowledgeless model in its first stage; the third row records the performance of E2E that couples with the corresponding knowledgeless model. Bold entries represent the best value in each column.  | AoFF | DBoF | LSTM | GRU
---|---|---|---|---
| MAP | HIT | GAP | MAP | HIT | GAP | MAP | HIT | GAP | MAP | HIT | GAP
- | 0.292 | 0.828 | 0.788 | 0.206 | 0.788 | 0.726 | 0.211 | 0.807 | 0.757 | 0.253 | 0.819 | 0.759
E2E | 0.321 | 0.829 | 0.785 | 0.212 | 0.801 | 0.737 | 0.232 | 0.814 | 0.767 | 0.259 | 0.826 | 0.776
(+2.9%) | (+0.1%) | (-0.3%) | (+0.6%) | (+1.3%) | (+1.1%) | (+2.1%) | (+0.7%) | (+1.0%) | (+0.6%) | (+0.7%) | (+0.7%)
Table 2: Performance advantage of E2E across four state-of-the-art
knowledgeless methods using only 10% training data. The percentage
improvements of E2E are bolded if they are greater than or equal to the
corresponding values in Table 1.

We first report the performance comparisons between the four knowledgeless
models and their respective knowledge-aware counterparts. Specifically, for
each knowledgeless model, we compare their results with those of both 2STG
(previous work) and E2E (our approach). The results are summarized in Table 1.
Note that we are only interested in comparing the values in each column,
instead of comparing across different knowledgeless models. Our approach E2E
can achieve better performance every time, beating the respective
knowledgeless model by up to 1.7% in MAP, 1.6% in HIT and 0.8% in GAP. In
contrast, 2STG performs poorly as it is not an end-to-end model. While 2STG
can outperform knowledgeless models for object detection on the Microsoft COCO
(?) and PASCAL VOC (?) datasets, the two datasets involve only a restricted
set of 80 and 20 classes, respectively. In contrast, our experiments deal with
1,867 classes over a much more complex and diverse range of topics, which
could be the potential reason that the decoupled two-stage method 2STG is
unable to cope.

We further hypothesize that our knowledge-aware model has more advantage when
the training set is smaller. Intuitively, when there are fewer videos to learn
from, the availability of external knowledge becomes ever more critical. Using
only 10% training data, the performance of E2E with the four knowledgeless
models is reported in Table 2. Not surprisingly, we observe slightly larger
improvements than those using all training data, especially for the MAP and
GAP metrics.

### Impact of parameters

(a) Effect of
$\lambda$$10^{-5}$$10^{-3}$$10^{-1}$$10^{1}$$10^{3}$$0.0$$0.2$$0.4$$0.6$$0.8$$1.0$Values
of $\lambda$PerformanceMAPHITGAP

(b) Effect of KNN1111222225555510101010$0.1$$0.3$$0.5$$0.7$$0.9$Values of
$K$PerformanceMAPHITGAP

Figure 5: Impact of parameters on the performance of E2E.

Next, we study the effect of parameters on the performance. There are two main
parameters for E2E: the trade-off $\lambda$ between the feature-based and
knowledge-based costs, and the choice of KNN for the semantic consistency
matrix. For brevity we only present their impact on AoFF, as similar trends
can be observed on other models.

In Figure 5(a), we vary $\lambda$ between 1e-5 and 1000, while fixing KNN at
$K=5$. Results show that the performance is generally stable for a wide range
of $\lambda$ between 1e-4 and 10. The performance only deteriorates for very
large values. Hence, it is robust to use $\lambda=0.01$ in our experiments.

In Figure 5(b), we vary $K\in\\{1,2,5,10\\}$ for the choice of KNN, while
fixing $\lambda=0.01$. When we use larger $K$, there is a slight increase in
performance, especially in MAP, although the matrix $S$ becomes denser and
results in lower efficiency. Generally, using $K=5$ can achieve a good balance
between accuracy and efficiency.

### Result analysis

| Ground truth | AoFF rank | E2E rank | Related concepts in the same video
---|---|---|---|---
1 | fashion | 20 | 1 ($\uparrow$19) | hairstyle, bollywood, cosmetics
2 | origami | 20+ | 1 ($\uparrow$19+) | paper, toy
3 | amusement park | 20+ | 1 ($\uparrow$19+) | food, roller coaster, train
4 | disc jockey | 5 | 2 ($\uparrow$3) | nightclub, dance, album, guitar
5 | food, drink | 1, 5 | 1, 2 ($\uparrow$3) | recipe, cocktail, juice, cooking, bartender, bottle
6 | camera, photography | 4, 9 | 1 ($\uparrow$3), 4 ($\uparrow$5) | gadget, camera lens, smart phone
7 | hunting, deer | 4, 20+ | 1 ($\uparrow$3), 6 ($\uparrow$14+) | forest, tree, plant, animal, weapon
8 | vehicle, tool, drill | 2, 4, 20+ | 1 ($\uparrow$1), 2 ($\uparrow$2), 6 ($\uparrow$14+) | car, metalworking
9 | concert, lighting, festival | 2, 5, 16 | 1 ($\uparrow$1), 2 ($\uparrow$3), 8 ($\uparrow$8) | dance, album, Ibiza
10 | furniture, couch, bed, chair | 1, 3, 11, 20+ | 1, 2 ($\uparrow$1), 6 ($\uparrow$5), 4 ($\uparrow$16+) | living room, home improvement, house, television

Table 3: Example videos that knowledge graphs can help with learning. Each row
describes a video, where “AoFF rank” and “E2E rank” columns indicate the rank
position of the ground truth label in the output of AoFF and E2E,
respectively; 20+ means the ground truth is not found in the top 20;
$\uparrow$ indicates the number of positions moved up in E2E output as
compared to AoFF; related concepts are listed if they have high semantic
consistency with the ground truth and they are within top 20 of both AoFF and
E2E.

| Ground truth | AoFF top | E2E top | Other concepts in the same video
---|---|---|---|---
1 | telescope | telescope | vehicle |  camera, car, boat, bicycle, motorcycle
2 | transistor | transistor | vehicle |  antenna, train, car
3 | running, marathon |  running, hiking |  mountain, nature |  climbing, walking, mountain pass, trail, lake
4 | gardening, plant |  plant, gardening |  food, news program |  tree, agriculture, cooking, television
5 | banknote, money, dollar | banknote, dollar, money | paper, animation, guitar |  manga, art, festival, musician

Table 4: Example videos where knowledge graphs can hurt performance. Each row
describes a video, where “AoFF top” and “E2E top” columns indicate the top
prediction(s) of AoFF and E2E, respectively; other concepts are listed if they
have high semantic consistency with the top prediction(s) of either AoFF or
E2E, and they are within top 20 of both AoFF and E2E; bold entries are a group
of concepts with strong mutual semantic consistency; likewise for italic
entries.

Finally, we conduct a more in-depth analysis of the results, using AoFF as the
knowledgeless model. At an aggregate level, we observe better predictions for
24.9% of the videos after incorporting external knowledge with E2E, whereas we
witness worse predictions for 8.9% of the videos. The remaining videos have no
change in their predictions. Given that the number of videos with better
results are almost three times of the videos with worse results, our approach
E2E does bring in net benefits, consistent with the quantitative evaluation
reported earlier.

We further zoom into some specific examples to understand the reasons behind
the improvement. In Table 3, we illustrated 10 videos where knowledge graphs
can help with learning. In these cases, E2E significantly improves the rank
positions of the ground truth labels over AoFF, due to the evidence of the
related concepts in the same video. For instance, in example #2, the concept
of origami is semantically consistent with paper and toy, which helps E2E to
identify origami correctly. On the contrary, even though AoFF also recognizes
the concepts paper and toy in the same video, it has no idea that those
concepts are related to origami, especially when there are not enough training
videos involving origami, paper and toy.

Finally, we investigate some negative cases in Table 4, where knowledge graphs
can hurt the performance. In these cases, E2E often makes overgeneralizations
based on the related concepts. In these videos, there exist an overwhelm of
concepts that are semantically consistent to the incorrect top predictions by
E2E, whereas the concepts that are consistent with the ground truth are much
fewer (e.g., #1 and #4) or even non-existent (e.g., #5). The root cause is
that E2E treats each related concepts uniformly. However, in an ideal
solution, we should only focus on the concepts related to the central theme of
the video. We leave the study of such “focus” concepts as potential future
work.

## Conclusion

In this paper, we studied the multi-label video classification problem. In
particular, we observed the knowledge gap between machine and human
intelligence. Towards bridging this gap, we proposed to utilize external
knowledge graphs for video classification, unifying machine learning including
deep neural networks with knowledge graphs in a novel end-to-end framework.
Extensive experiments on the largest public benchmark YouTube-8M showed the
superior performance of our approach, outperforming state-of-the-art
knowledgeless models by up to 2.9% in MAP among other metrics. Finally, we
analyzed some case studies to understand the scenarios in which knowledge
graphs can or cannot help.

As future work, we plan to extract features from knowledge graphs and directly
incorporate them into the deep neural networks. Moreover, it is also worth
investigating that how we can identify focus concepts that are related to the
central theme of a video.

## References

  * [Abu-El-Haija et al. 2016] Abu-El-Haija, S.; Kothari, N.; Lee, J.; Natsev, P.; Toderici, G.; Varadarajan, B.; and Vijayanarasimhan, S.  2016\.  Youtube-8m: A large-scale video classification benchmark.  arXiv preprint arXiv:1609.08675.
  * [Auer et al. 2007] Auer, S.; Bizer, C.; Kobilarov, G.; Lehmann, J.; Cyganiak, R.; and Ives, Z. G.  2007\.  DBpedia: A nucleus for a web of open data.  In ISWC-ASWC, 722–735.
  * [Bordes et al. 2013] Bordes, A.; Usunier, N.; Garcia-Duran, A.; Weston, J.; and Yakhnenko, O.  2013\.  Translating embeddings for modeling multi-relational data.  In NIPS, 2787–2795.  Curran Associates, Inc.
  * [Carlson et al. 2010] Carlson, A.; Betteridge, J.; Kisiel, B.; Settles, B.; Jr., E. R. H.; and Mitchell, T. M.  2010\.  Toward an architecture for never-ending language learning.  In AAAI.
  * [Chen et al. 2017] Chen, S.; Wang, X.; Tang, Y.; Chen, X.; Wu, Z.; and Jiang, Y.-G.  2017\.  Aggregating frame-level features for large-scale video classification.  arXiv preprint arXiv:1707.00803.
  * [Chung et al. 2014] Chung, J.; Gulcehre, C.; Cho, K.; and Bengio, Y.  2014\.  Empirical evaluation of gated recurrent neural networks on sequence modeling.  arXiv preprint arXiv:1412.3555.
  * [Deng et al. 2014] Deng, J.; Ding, N.; Jia, Y.; Frome, A.; Murphy, K.; Bengio, S.; Li, Y.; Neven, H.; and Adam, H.  2014\.  Large-scale object classification using label relation graphs.  In ECCV, Part I, 48–64.
  * [Dong et al. 2014] Dong, X.; Gabrilovich, E.; Heitz, G.; Horn, W.; Lao, N.; Murphy, K.; Strohmann, T.; Sun, S.; and Zhang, W.  2014\.  Knowledge vault: a Web-scale approach to probabilistic knowledge fusion.  In KDD, 601–610.
  * [Everingham et al. 2010] Everingham, M.; Gool, L. J. V.; Williams, C. K. I.; Winn, J. M.; and Zisserman, A.  2010\.  The PASCAL visual object classes (VOC) challenge.  IJCV 88(2):303–338.
  * [Fang and Chang 2011] Fang, Y., and Chang, K. C.  2011\.  Searching patterns for relation extraction over the web: rediscovering the pattern-relation duality.  In WSDM, 825–834.
  * [Fang et al. 2017] Fang, Y.; Kuan, K.; Lin, J.; Tan, C.; and Chandrasekhar, V.  2017\.  Object detection meets knowledge graphs.  In IJCAI, 1661–1667.
  * [Fang, Chang, and Lauw 2013] Fang, Y.; Chang, K. C.; and Lauw, H. W.  2013\.  RoundTripRank: Graph-based proximity with importance and specificity.  In ICDE, 613–624.
  * [Grover and Leskovec 2016] Grover, A., and Leskovec, J.  2016\.  node2vec: Scalable feature learning for networks.  In KDD, 855–864.  ACM.
  * [Jordan and Jacobs 1994] Jordan, M. I., and Jacobs, R. A.  1994\.  Hierarchical mixtures of experts and the em algorithm.  Neural computation 6(2):181–214.
  * [Karpathy et al. 2014] Karpathy, A.; Toderici, G.; Shetty, S.; Leung, T.; Sukthankar, R.; and Fei-Fei, L.  2014\.  Large-scale video classification with convolutional neural networks.  In CVPR, 1725–1732.
  * [Krishna et al. 2017] Krishna, R.; Zhu, Y.; Groth, O.; Johnson, J.; Hata, K.; Kravitz, J.; Chen, S.; Kalantidis, Y.; Li, L.; Shamma, D. A.; Bernstein, M. S.; and Fei-Fei, L.  2017\.  Visual genome: Connecting language and vision using crowdsourced dense image annotations.  IJCV 123:32–73.
  * [Laptev et al. 2008] Laptev, I.; Marszalek, M.; Schmid, C.; and Rozenfeld, B.  2008\.  Learning realistic human actions from movies.  In CVPR, 1–8.  IEEE.
  * [Lenat 1995] Lenat, D. B.  1995\.  CYC: A large-scale investment in knowledge infrastructure.  Commun. ACM 38(11):32–38.
  * [Lin et al. 2014] Lin, T.; Maire, M.; Belongie, S. J.; Hays, J.; Perona, P.; Ramanan, D.; Dollár, P.; and Zitnick, C. L.  2014\.  Microsoft COCO: common objects in context.  In ECCV, Part V, 740–755.
  * [Liu and Singh 2004] Liu, H., and Singh, P.  2004\.  ConceptNet—a practical commonsense reasoning tool-kit.  BT Technology Journal 22(4):211–226.
  * [Lu et al. 2016] Lu, C.; Krishna, R.; Bernstein, M. S.; and Li, F.  2016\.  Visual relationship detection with language priors.  In ECCV, Part I, 852–869.
  * [Miech, Laptev, and Sivic 2017] Miech, A.; Laptev, I.; and Sivic, J.  2017\.  Learnable pooling with context gating for video classification.  arXiv preprint arXiv:1706.06905.
  * [Paulheim 2017] Paulheim, H.  2017\.  Knowledge graph refinement: A survey of approaches and evaluation methods.  Semantic Web 8(3):489–508.
  * [Suchanek, Kasneci, and Weikum 2007] Suchanek, F. M.; Kasneci, G.; and Weikum, G.  2007\.  YAGO: a core of semantic knowledge.  In WWW, 697–706.
  * [Thomee et al. 2015] Thomee, B.; Shamma, D. A.; Friedland, G.; Elizalde, B.; Ni, K.; Poland, D.; Borth, D.; and Li, L.-J.  2015\.  The new data and new challenges in multimedia research.  arXiv preprint arXiv:1503.01817 1(8).
  * [Tong, Faloutsos, and Pan 2006] Tong, H.; Faloutsos, C.; and Pan, J.  2006\.  Fast random walk with restart and its applications.  In ICDM, 613–622.
  * [Vondrick et al. 2016] Vondrick, C.; Oktay, D.; Pirsiavash, H.; and Torralba, A.  2016\.  Predicting motivations of actions by leveraging text.  In CVPR, 2997–3005.
  * [Wang et al. 2009] Wang, H.; Ullah, M. M.; Klaser, A.; Laptev, I.; and Schmid, C.  2009\.  Evaluation of local spatio-temporal features for action recognition.  In BMVC, 124–134.  BMVA Press.
  * [Wang et al. 2017] Wang, Z.; Kuan, K.; Ravaut, M.; Manek, G.; Song, S.; Fang, Y.; Kim, S.; Chen, N.; Enriquez, L. F. D.; Tuan, L. A.; et al.  2017\.  Truly multi-modal youtube-8m video classification with video, audio, and text.  arXiv preprint arXiv:1706.05461.
  * [Weiss, Torralba, and Fergus 2009] Weiss, Y.; Torralba, A.; and Fergus, R.  2009\.  Spectral hashing.  In NIPS, 1753–1760.
  * [Wu et al. 2016] Wu, Q.; Wang, P.; Shen, C.; Dick, A. R.; and van den Hengel, A.  2016\.  Ask me anything: Free-form visual question answering based on knowledge from external sources.  In CVPR, 4622–4630.
  * [Yue-Hei Ng et al. 2015] Yue-Hei Ng, J.; Hausknecht, M.; Vijayanarasimhan, S.; Vinyals, O.; Monga, R.; and Toderici, G.  2015\.  Beyond short snippets: Deep networks for video classification.  In CVPR, 4694–4702.
  * [Zhu et al. 2013] Zhu, F.; Fang, Y.; Chang, K. C.; and Ying, J.  2013\.  Incremental and accuracy-aware personalized pagerank through scheduled approximation.  PVLDB 6(6):481–492.