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

arXiv:1711.01714v1 [cs.CV] 6 Nov 2017

yfang@i2r.a-star.edu.sg, mark.wangzhe@gmail.com, luisdhe@i2r.a-star.edu.sg, jjkim@i2r.a-star.edu.sg
zengz@i2r.a-star.edu.sg, vijay@i2r.a-star.edu.sg
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 multilabel 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 endto-end framework. The framework is flexible to work with
most existing video classification algorithms including stateof-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
Copyright c 2018, Association for the Advancement of Artificial
Intelligence (www.aaai.org). All rights reserved.

zoo example in Figure 1(b), with the knowledge that manmade 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.
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 (Abu-El-Haija et al.
2016), which presents two major challenges (Wang et al.
2017). 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 (Paulheim 2017), modeling each realworld 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 (Dong et al.
2014), 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.
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-ofthe-art approaches.

(a) Image from Microsoft COCO1

(b) Video frames from YouTube2

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.

person

zoo

on top of

surfboard

surfing

sea
comprise of

polar bear

Arctic

Figure 2: Toy knowledge graph.
• 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-theart 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.

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 (Karpathy et al. 2014), YFCC-100M (Thomee et
al. 2015) and YouTube-8M (Abu-El-Haija et al. 2016).
The problem of video classification is usually addressed
at frame or video levels. The deep bag-of-frames (DBoF)
(Abu-El-Haija et al. 2016) is a typical frame-level approach,
inspired by various classic bag-of-words representations
(Laptev et al. 2008; Wang et al. 2009). 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 de1
2

http://cocodataset.org/
https://www.youtube.com/

pendencies in the temporal dimension (Yue-Hei Ng et al.
2015). Furthermore, as an alternative to LSTM, Gated Recurrent Unit (GRU) often achieves comparable if not better
performance (Chung et al. 2014; Chen et al. 2017). 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) (Jordan and Jacobs 1994) classifier has shown
superior empirical performance on video-level representations (Abu-El-Haija et al. 2016). 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 (Wang et al. 2017).
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 (Deng et al. 2014), motivation prediction (Vondrick et al. 2016), question answering (Wu et al. 2016), relationship extraction (Lu et al. 2016),
as well as object detection (Fang et al. 2017). 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 (Fang et al. 2017) 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 (Dong et al. 2014). Quite a number of large-scale

Input Video

…

1024-D

1024-D

Frame-level models

Video Frames

DBoF
LSTM
GRU
…

zoo

animal

polar bear

Ground-Truth Labels

…

128-D

wildlife

128-D

Video-level models
Aggregation of frame
features (AoFF)

Audio Channel

Input knowledge graph
Classifier
(e.g., MoE)

Output
wildlife zoo animal polar bear
0.80 0.75 0.95
0.90

Figure 3: Overall framework of the proposed end-to-end learning with knowledge graphs (example video from YouTube).
knowledge graphs are available commercially or in open
source, which are generally constructed based on human curation (Lenat 1995), crowdsourcing (Liu and Singh 2004;
Krishna et al. 2017), and distillation from semi-structured
(Suchanek, Kasneci, and Weikum 2007; Auer et al. 2007)
or unstructured data (Carlson et al. 2010; Fang and Chang
2011). 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 L = {1, 2, . . . , 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 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 (p1 , p2 , . . . , pL ) where pi 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 (Paulheim 2017) 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 label3 , 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
3

We use the terms concept and label interchangeably hereafter.

vectors from each frame. Note that in YouTube-8M, the preextracted 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 (Fang et
al. 2017) 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 featurebased 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 (Fang et al.
2017) 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 × L matrix
S, such that Sij represents the semantic consistency between
labels i and j, ∀ij ∈ L2 . In particular, Si 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 (Tong, Faloutsos, and Pan
2006) is a well-known method to realize the above intuition.
Starting from one node representing label i, we compute the
probability Rij of reaching another node representing label
j through random walk. The higher probability Rij implies
that there are more and shorter paths from i to j and thus
the semantic consistency Sij is also higher. As Rij 6= Rji
in general, but the semantic consistency matrix S should
be symmetric in our context, we adopt the below definition follow the earlier work (Fang et al. 2017). We refer
readers to existing work (Tong, Faloutsos, and Pan 2006;
Fang, Chang, and Lauw 2013; Zhu et al. 2013) on the computation of random walk probabilities Rij .
p
Sij = Sji = Rij Rji
(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 (Grover and Leskovec 2016; Bordes et al. 2013).
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 Sij is one of the largest K elements in
the i-th row or j-th row of S. Subsequently, we simply set
Sij = Sji = 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 Θ. For a given video instance, we propose
the following knowledge-aware cost function K, where
p1 , p2 , . . . , pL encode the label probabilities of the video and
they are functions of Θ.
qP
L P
2
(2)
K(Θ) = C(Θ) + λ
i=1
j<i Sij (pi − pj )
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.

(a) Pairwise computations

ଵ
ଶ
ଷ

ସ

Sub

Square

ଵଶ

Mul

Sub

Square

ଵଷ

Mul

Sub

Square

ଶଷ

Mul

Sub

Square

ଶସ

Mul

Sub

Square

ଷସ

Mul

Sub

Square

ଵସ

Mul

(b) Matrix computations

Mul
Add

Mul

Sub
்

Figure 4: TensorFlow computation graphs.

For a pair of labels i and j, if Sij is large (i.e., the two labels have strong semantic consistency), minimizing the cost
function would force pi and pj to become similar. That is,
it is likely that they either both appear in the video, or both
not appear. In contrast, if Sij is small (i.e., they are not semantically consistent), pi and pj 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 λ ∈ (0, ∞).
While the above formulation is intuitive, it is not practical
for implementation with standard libraries such as TensorFlow4 . 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(L2 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.
As such, we employ the Laplacian matrix transformation.
It has been established (Weiss, Torralba, and Fergus 2009)
that Equation (2) is equivalent to the following:
q
K(Θ) = C(Θ) + λ Tr [p(D − S)pT ]
(3)
PL
where D is a diagonal matrix such that Dii =
j=1 Sij
and p = (p1 , p2 , . . . , pL ) 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 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.
p
∂ Tr [p(D − S)pT ] ∂p
∂C(Θ)
∂K(Θ)
=
+λ
∂Θ
∂Θ
∂p
∂Θ
∂C(Θ)
p(D − S)
∂p
=
+ λp
(4)
T
∂Θ
∂Θ
Tr [p(D − S)p ]
4

https://www.tensorflow.org/

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 benchmark5 , 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 videolevels are available, where the video and audio features have
1024 and 128 dimensions, respectively.
We employ the off-the-shelf knowledge graph ConceptNet 56 . Following previous work (Fang et al. 2017), 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 precisionrecall 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”
5
6

https://www.kaggle.com/c/youtube8m/data
http://conceptnet.io/

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 (Abu-El-Haija et al. 2016), we use the implementation by Google7 ; for GRU (Miech, Laptev, and Sivic
2017), we use the implementation by Miech et al.8 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 endto-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
λ = 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
(Fang et al. 2017). This method is originally designed for
object detection in images, which can be adapted for multilabel 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 reoptimize 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  = 0.9 which is found to be the best setting.

Comparison of performance
We first report the performance comparisons between the
four knowledgeless models and their respective knowledgeaware 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 (Lin et al. 2014) and PASCAL VOC (Everingham et al. 2010) datasets, the two datasets involve only a
restricted set of 80 and 20 classes, respectively. In contrast,
7
8

https://github.com/google/youtube-8m
https://github.com/antoine77340/Youtube-8M-WILLOW

2STG
E2E

MAP
0.370
0.364
0.384

AoFF
HIT
0.846
0.841
0.849

(+1.4%)

(+0.3%)

GAP
0.810
0.804
0.817

DBoF
HIT
0.834
0.830
0.847

MAP
0.287
0.286
0.301

(+0.7%) (+1.4%)

GAP
0.791
0.787
0.794

(+1.3%)

MAP
0.279
0.275
0.296

(+0.3%) (+1.7%)

LSTM
HIT
0.838
0.838
0.854
(+1.6%)

GAP
0.800
0.797
0.808

MAP
0.337
0.331
0.340

(+0.8%) (+0.3%)

GRU
HIT
0.856
0.855
0.857

GAP
0.823
0.819
0.824

(+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.

E2E

MAP
0.292
0.321

AoFF
HIT
0.828
0.829

GAP
0.788
0.785

MAP
0.206
0.212

DBoF
HIT
0.788
0.801

GAP
0.726
0.737

MAP
0.211
0.232

LSTM
HIT
0.807
0.814

GAP
0.757
0.767

MAP
0.253
0.259

GRU
HIT
0.819
0.826

GAP
0.759
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.

(a) Effect of λ

(b) Effect of KNN

1.0

0.9

0.6
0.4

MAP
HIT
GAP

0.2
0.0

10−510−310−1 101 103
Values of λ

Performance

Performance

0.8

0.7
MAP
HIT
GAP

0.5
0.3
0.1

1

2
5
Values of K

10

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

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
Next, we study the effect of parameters on the performance.
There are two main parameters for E2E: the trade-off λ 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 λ between 1e-5 and 1000, while
fixing KNN at K = 5. Results show that the performance
is generally stable for a wide range of λ between 1e-4 and
10. The performance only deteriorates for very large values.
Hence, it is robust to use λ = 0.01 in our experiments.
In Figure 5(b), we vary K ∈ {1, 2, 5, 10} for the choice
of KNN, while fixing λ = 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
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

1
2
3
4
5
6
7
8
9
10

Ground truth
fashion
origami
amusement park
disc jockey
food, drink
camera, photography
hunting, deer
vehicle, tool, drill
concert, lighting, festival
furniture, couch, bed, chair

AoFF rank
20
20+
20+
5
1, 5
4, 9
4, 20+
2, 4, 20+
2, 5, 16
1, 3, 11, 20+

E2E rank
1 (↑19)
1 (↑19+)
1 (↑19+)
2 (↑3)
1, 2 (↑3)
1 (↑3), 4 (↑5)
1 (↑3), 6 (↑14+)
1 (↑1), 2 (↑2), 6 (↑14+)
1 (↑1), 2 (↑3), 8 (↑8)
1, 2 (↑1), 6 (↑5), 4 (↑16+)

Related concepts in the same video
hairstyle, bollywood, cosmetics
paper, toy
food, roller coaster, train
nightclub, dance, album, guitar
recipe, cocktail, juice, cooking, bartender, bottle
gadget, camera lens, smart phone
forest, tree, plant, animal, weapon
car, metalworking
dance, album, Ibiza
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; ↑ 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.

1
2
3
4
5

Ground truth
telescope
transistor
running, marathon
gardening, plant
banknote, money, dollar

AoFF top
telescope
transistor
running, hiking
plant, gardening
banknote, dollar, money

E2E top
vehicle
vehicle
mountain, nature
food, news program
paper, animation, guitar

Other concepts in the same video
camera, car, boat, bicycle, motorcycle
antenna, train, car
climbing, walking, mountain pass, trail, lake
tree, agriculture, cooking, television
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.
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.; Dollá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 spatiotemporal 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 youtube8m 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.

