summaries: In this paper, the authors propose to sample nodes of a given graph multiple times to form a set of K sub-graphs. GNNs are then applied on each sampled graph for learning node representations. For each node, all representations are combined for the downstream tasks. The idea of doing multiple sampling is to increase the chance that nodes with different neighborhoods can be more different in the set of sampled graphs, than only considering the original single graph. In contrast, nodes with same neighborhood will remain the same over all sampled graphs. This mechanism helps discriminate node representations better.

summaries: The paper presents a method that should increase the expressive power of GNN. This method includes sampling subgraphs out of the input graph using a novel diverse sampling method and calculating the output of each node by using a shared GNN on each sampled graph and summing over the outputs. The empirical evidence presented shows that this method outperforms other GNN architectures such as GCN and GAT on several node classification tasks.

summaries: This paper claims that existing GNNs often suffers from the limited capability of the aggregation function. This paper proposes a new framework of a diverse sampling of the graph to solve this problem. Specifically, this paper first samples several different graphs and use GNN on each graph to generate features, and finally use a type of injective multi-set aggregation function to obtain the final representation. The experimental results show that adding this module to GCN and GAT can further boost node-based multi-class classification performance.

abstractText: Graph neural networks (GNNs) offer us an effective framework for graph representation learning via layer-wise neighborhood aggregation. Their success is attributed to their expressive power at learning representation of nodes and graphs. To achieve GNNs with high expressive power, existing methods mainly resort to complex neighborhood aggregation functions, e.g., designing injective aggregation function or using multiple aggregation functions. Consequently, their expressive power is limited by the capability of aggregation function, which is tricky to determine in practice. To combat this problem, we propose a novel framework, namely diverse sampling, to improve the expressive power of GNNs. For a target node, diverse sampling offers it diverse neighborhoods, i.e., rooted sub-graphs, and the representation of target node is finally obtained via aggregating the representation of diverse neighborhoods obtained using any GNN model. High expressive power is guaranteed by the diversity of different neighborhoods. We use classical GNNs (i.e., GCN and GAT) as base models to evaluate the effectiveness of the proposed framework. Experiments are conducted at multi-class node classification task on three benchmark datasets and multi-label node classification task on a dataset collected in this paper. Extensive experiments demonstrate the proposed method consistently improve the performance of base GNN models. The proposed framework is applicable to any GNN models and thus is general for improving the expressive power of GNNs.

authors:
Gabriele Corso
Luca Cavalleri
Dominique Beaini
Pietro Liò
Petar

title: Veličković. Principal neighbourhood aggregation for graph nets

venue: arXiv preprint arXiv:2004.05718,

authors:
Vikas K Garg
Stefanie Jegelka
Tommi Jaakkola

title: Generalization and representational limits of graph neural networks

venue: arXiv preprint arXiv:2002.06157,

authors:
Justin Gilmer
Samuel S Schoenholz
Patrick F Riley
Oriol Vinyals
George E Dahl

title: Neural message passing for quantum chemistry

venue: arXiv preprint arXiv:1704.01212,

authors:
Will Hamilton
Zhitao Ying
Jure Leskovec

title: Inductive representation learning on large graphs

venue: In Advances in neural information processing systems,

authors:
Arman Hasanzadeh
Ehsan Hajiramezanali
Shahin Boluki
Mingyuan Zhou
Nick Duffield
Krishna Narayanan
Xiaoning Qian

title: Bayesian graph neural networks with adaptive connection sampling

venue: arXiv preprint arXiv:2006.04064,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Kurt Hornik
Maxwell Stinchcombe
Halbert White

title: Multilayer feedforward networks are universal approximators

venue: Neural networks,

authors:
Yifan Hou
Jian Zhang
James Cheng
Kaili Ma
Richard TB Ma
Hongzhi Chen
Ming-Chang Yang

title: Measuring and improving the use of graph information in graph neural networks

venue: In International Conference on Learning Representations,

authors:
Wenbing Huang
Tong Zhang
Yu Rong
Junzhou Huang

title: Adaptive sampling towards fast graph representation learning

authors:
Thomas N Kipf
Max Welling

title: Semi-supervised classification with graph convolutional networks

venue: arXiv preprint arXiv:1609.02907,

authors:
Bryan Perozzi
Rami Al-Rfou
Steven Skiena

title: Deepwalk: Online learning of social representations

venue: In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining,

authors:
Yu Rong
Wenbing Huang
Tingyang Xu
Junzhou Huang

title: Dropedge: Towards deep graph convolutional networks on node classification

authors:
Ryoma Sato
Makoto Yamada
Hisashi Kashima

title: Approximation ratios of graph neural networks for combinatorial problems

venue: In Advances in Neural Information Processing Systems,

authors:
Nitish Srivastava
Geoffrey Hinton
Alex Krizhevsky
Ilya Sutskever
Ruslan Salakhutdinov

title: Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning

authors:
Boris Weisfeiler
Andrei A Lehman

title: A reduction of a graph to a canonical form and an algebra arising during this reduction

venue: Nauchno-Technicheskaya Informatsia,

authors:
Keyulu Xu
Weihua Hu
Jure Leskovec
Stefanie Jegelka

title: How powerful are graph neural networks

venue: arXiv preprint arXiv:1810.00826,

authors:
Keyulu Xu
Chengtao Li
Yonglong Tian
Tomohiro Sonobe
Ken-ichi Kawarabayashi
Stefanie Jegelka

title: Representation learning on graphs with jumping knowledge networks

venue: arXiv preprint arXiv:1806.03536,

heading: 1 INTRODUCTION

text:
Graph neural networks (GNNs) have been shown to be effective at graph representation learning and many predictive tasks on graph-structured data, e.g., node classification and graph classification (Kipf & Welling, 2016; Xu et al., 2018a). GNNs follow a neighborhood aggregation scheme, where the representation of a node is obtained by recursively aggregating and transforming representation of its neighboring nodes (Gilmer et al., 2017). The success of GNNs is believed to be attributed to their high expressive power at learning representation of nodes and graphs (Xu et al., 2018a). Therefore, it is an important research problem to analyze and improve the expressive power of existing GNN models and design new GNNs with high expressive power.
Several recent works focus on the expressive power of GNNs. Xu et al. pointed out that the expressive power of GNNs depends on the neighborhood aggregation function (Xu et al., 2018a). They develop a simple architecture, i.e., leveraging multi-layer perceptron (MLP) and a sum pooling as a universal approximator defined on multi-set, to achieve injective neighborhood aggregation function. With injective aggregation function in each layer, the proposed graph isomorphism network (GIN) has the expressive power as high as the Weisfeiler-Lehman (WL) graph isomorphism test (Weisfeiler & Lehman, 1968). Similarly, Sato et al. implement a powerful GNN via consistent port numbering, i.e., mapping edges to port numbering and neighbors are ordered by the port numbering (Sato et al., 2019). However, port ordering of CPNGNNs is not unique, and not all orderings can distinguish the same set of graphs (Garg et al., 2020). Principal neighborhood aggregation (PNA) defines multiple aggregation functions to improve the expressive power of GNNs (Corso et al., 2020). However, the number of required aggregation functions to discriminate multi-sets depends on the size of multi-set, which is prohibitive for real world networks with skewed degree distribution. In sum, existing methods focus on designing an injective, often complex, aggregation function in each layer to achieve GNNs with high expressive power. However, injective functions are difficult to obtain and tricky to
determine in practice. Indeed, layer-wise injective function is not always required and what we need is an injective function defined over rooted sub-graphs or graphs as a whole.
In this paper, we propose a novel framework, namely diverse sampling, to improve the expressive power of GNNs. For a target node, diverse sampling offers it diverse neighborhoods, i.e., rooted subgraphs, and the representation of target node is finally obtained via aggregating the representation of diverse neighborhoods obtained using any GNN model. High expressive power is guaranteed by the diversity of different neighborhoods. For convenience, we denote with DS-GNN the GNN implemented under the proposed diverse sampling framework.

heading: Input

heading: Injective

text:
Fig. 1 illustrates the main idea of the proposed DS-GNN, and compare it with two representative methods, i.e., GIN and PNA. Fig. 1 (a) depicts the injective layer implemented via MLP or multiple aggregation functions, aggregating first-order neighboring nodes to obtain the representation of central node. Injective layer are stacked to achieve an overall injective function defined on rooted sub-graphs. On the contrary, DS-GNN does not follow the line of designing complicated aggregation functions in each layer. Instead, DS-GNN improve the expressive power of GNNs via obtaining diverse rooted sub-graphs for each node. Specifically, we sample nodes multiple times on the entire input graph based on diverse sampling, and obtain multiple sampled sub-graphs for each node. After diverse sampling, we leverage the shared GNN model to get the representation for the central node, including its high-order neighbors. In this way, each node is represented by a multi-set, consisting of the representations obtained from different sampled rooted sub-graphs. The final representation of central node is finally obtained via aggregating the representation of diverse neighborhoods.
Finally, we use classical GNNs (i.e., GCN (Kipf & Welling, 2016) and GAT (Veličković et al., 2017)) as base models to evaluate the effectiveness of the proposed framework. Experiments are conducted at node-based multi-class classification task on three benchmark datasets and node-based multilabel classification task on a dataset collected in this paper. Extensive experiments demonstrate the proposed method consistently improve the performance of base GNN models. The proposed framework is applicable to any GNN models and thus is general for improving the expressive power of GNNs.

heading: 2 NOTATIONS AND PRELIMINARIES

text:
We first introduce the general framework of GNNs.
G = {V,A} denotes an undirected graph, where V is the set of nodes with |V | = n, and A is the adjacency matrix with Ai,j = Aj,i to define the connection between node i and node j. X ∈ Rn×p denotes the feature matrix and the i-th row in X represent the attributes of i-th node. DS-GNN Modern GNNs follow a neighborhood aggregation scheme, which iteratively update each node’s representation via aggregating the representation of its neighboring nodes. Formally, the k-th layer of GNN is
a(k)v = AGGREGATE (k)(h(k−1)u : u ∈ N(v)), h(k)v = COMBINE (k)(h(k−1)v , a (k) v ), (1)
whereN(v) represents the neighbors of node v, h(k)v is the representation of node v in the k-th layer, and h(0)v = Xv . Additionally, we introduce two representative base models: Graph Convolutional Network (GCN) (Kipf & Welling, 2016) and Graph Attention Networks (GAT) (Veličković et al., 2017) in Appendix A.

heading: 3 DIVERSE SAMPLING BASED POWERFUL GRAPH NEURAL NETWORK

text:
Considering that the injectivity of each node with its neighbors making GNNs be possessed with the most powerful ability for node-level task, i.e., representations can be distinguishable for two nodes when they have dissimilar attributes or different neighbors, we devote to designing a powerful GNN to reach such injectivity, thus increase its expressive power. Specifically, we propose a novel framework, i.e., Diverse Sampling (DS-GNN), to increase the expressive power via constructing diverse rooted sub-graphs for each node. In this section, we first give the framework of our DSGNN. Then we will introduce the important parts of DS-GNN, including diverse sampling strategy that ensure the diversity among each sampling, as well as the part of model learning. We also theoretically analyze how the proposed DS-GNN can improve the expressive abilities when added to generic GNNs.
3.1 METHOD
The framework of DS-GNN is illustrated in Fig. 2. For the input graph, instead of running GNN on the entire graph, we first do node sampling with K-times and then obtain K sampled graphs. During sampling, we calculate the sampling probability for each node and randomly retain the node based on the probability. If one node is not sampled, it means that the node and all edges connected with it will be removed from the graph. The updated adjacency matrix and feature matrix of each sampling are fed into the base GNN model, and the GNN is shared over all samplings. Then we obtain one representation for each sampled node corresponded with one input sampled graph. Thus, if one node is sampled more than one time, we will obtain multiple representations.
To get the final representation of each node, we need to integrate these representations. To hold the injectivity when integrating representations, we adopt a multi-layer perceptrons (MLP) followed by the sum aggregation to achieve the injective multi-set aggregation function. Once getting the final representation for each node, we calculate the loss function and optimize the model.
Sampling Strategy
Intuitively, with a large number of sampling numbers, the sampling results are expected to retain the information of entire graph. Thus previous methods, e.g., Dropedge (Rong et al., 2019) which samples in each training epoch, do not need to carefully design the sampling strategy and they keep all edges when testing and validation. Meanwhile, they fail to achieve diverse sampled graphs in testing. Different from previous methods, we need to hold the K sampled graphs in testing and keep training and testing consistently. To solve this, we only sample the entire graph K-times, and leverage these sampled K graphs in all training epochs, as well as the validation and testing. To guarantee the performance of the proposed DS-GNN when even small K is chosen, we carefully design the important diverse sampling strategy.
To ensure the reuse of sampling results, we propose node sampling to obtain K sampled graphs. In one sampling, the neighbors of each node are obtained from the same sampled graph. For the sampling probability of nodes, the most intuitive way is to set the same initial probability for each node, which is pinit. However, this method may require a large number of sampling numbers K. In order to further speed up or get an effective sampling plan, we also propose three intuitive guidelines for sampling strategy: 1) to ensure the coverage of samples, each node should appears at least in one sampled graph; 2) to achieve the diversity among samples, we assume that the sampling probability of each node should decrease when its sampled times in previous is already large; 3) to retain the important node in the original network and adopting the node degree as the importance indicator, we assume that the sampling probability of each node should increase when its degree in original network is large. Meanwhile, we also considering the previous sampled results, discounting the sampling probability of each node when the its degree in previous sampled graphs is already large. That’s to say, the sampling probability of each node increase with the increase of node degree in original network, and decrease with the increase of node degree in previous sampled graphs. To achieve the above three guidelines, we need to relate the sampling probability of each node to the historical sampling results. Next, we will introduce in detail how we do.
Let K represent the total number of samples, pv,i represent the probability of node v in the i-th sampling, and Hv,i represent the number of times that the node v has been sampled before the ith sampling. To achieve guideline 1), we should guarantee that the probability for a node, which has never been sampled in history K-1 samples, equals to 1 at the K-th sampling. In other words, pv,K = 1 when Hv,K = 0. Additionally, to achieve the diversity guideline of 2), the sampling probability pv,i should decrease with the increase of historical sampled numbers Hv,i. Together, the sampling probability of node v for the i-th sampling is defined as:
pv,i = pinit + (1− pinit)× i−Hv,i K . (2)
To achieve guideline of 3), a new sampling strategy is designed. Specifically, we define Dsamplev,j as the degree of node v in the j-th sampled graph, and Dv as the degree of node v in the original graph. To make the sampling probability increase with Dv , as well as decrease with D sample v,j as mentioned in guideline 3), we define the coefficient Dgapv,i as:
Dgapv,i =
∑i−1 j=1(Dv −D
sample v,j )∑i−1
j=1Dv (3)
To achieve our three guidelines in total, we integrate the Eq 2 and Eq 3, and define the sampling probability for node v in the i-th sampling as:
pv,i = pinit + (1− pinit)× i−Hv,i K ×Dgapv,i . (4)
Note that our sampling strategy is different from previous methods, i.e., dropping features and dropping edges. The Dropout (Srivastava et al., 2014) is proposed to prevent over-fitting by randomly dropping features. Dropping edges can be regarded as a generation of Dropout from dropping features to dropping edges. However, dropping edges may cause that two nodes who are the same with identical neighbors obtain different representations, since dropping edges may cause these two nodes result in different neighbors after edge sampling. In contrast, we propose node sampling strategy, ensuring that the nodes with the same input features and neighbors will still have the same
representation. We give the detailed introduction of some previous methods, included in dropping edges in Appendix B.

heading: Model Learning

text:
In the following, we describe in detail how DS-GNN can be applied to any base GNN to achieve a more powerful GNN model. Specifically, we first doK samplings on the input graphA via the above introduced diverse sampling, getting the sampled graphs [A1, A2, · · · , AK ] in a pre-processing step. Then we applied a base GNN model to obtain the representations of nodes in sampled graphs respectively, each layer is formulated as.
h(k,l)v = COMBINE (l)(h(k,l−1)v ,AGGREGATE (l)(h(k,l−1)u : u ∈ Nk(v))), (5) where hk,lv is the representation of node v at the l-th layer in the k-th sampled graphs, and Nk(v) denotes the neighbors of node v in the k-th sampled graphs Ak. For each node, we obtain K representations {h(1,L)v , h(2,L)v , · · · , h(K,L)v } from the L-th layer of base GNN based on the K sampled graphs. Note that if a node is not sampled in one sampling, we fill its representation with 0 to ensure that each node has K representations. In order to integrate them into one representation, we fed them into a MLP with two fully connected layers, and then sum the transferred representations after MLP. Note that the MLP is shared over all samplings. Let Ov denote the output representation of node v, Ov is calculated as
Ov = K∑ i=1 MLP(h(i,L)v ). (6)
To verify the ability of DS-GNN model, we adopt node-level tasks, i.e., node based multi-class classification and node-based multi-label classification, as the target task. Note that in multi-label classification, each node has multiple labels. Let V Label denote the set of labeled nodes andm is the number of total labels, Yvc equals 1 if node v has label c, otherwise 0. For node-based multi-class classification, the output probability vector Ẑv is calculated by applying “Softmax” funtion to the output representations Ov:
Ẑv = Softmax(Ov). (7)
For node-based multi-label classification, Ẑv is calculated by applied “Sigmoid” funtion instead:
Ẑv = Sigmoid(Ov). (8)
For these two tasks, the loss function is defined as the cross-entropy over all labeled nodes as
L = − ∑
v∈V Label
m∑ c=1 Yvc ln Ẑvc, (9)

heading: 3.2 TOWARDS HIGH EXPRESSIVE POWER

text:
Recall that, in this work we devote to achieving injectivity on nodes to increase the expressive power of GNN, i.e., for any two nodes with different attributes or different neighbors, the model can output different representations for them. In this section, we theoretically analyze whether our proposed DS-GNN method can achieve this goal. Note that the MLP applied to the K representations in Fig. 2 followed by the sum operator can achieve injectivity when integrating the multi-sets (Hornik et al., 1989; Xu et al., 2018a). As a result, to prove the injectivity on nodes of the proposed DS-GNN, we only need to prove that two nodes with different neighbors have different multi-sets of the K representations.
For simplicity, we denote the representation of node u on the i-th sampled graph under L layers base GNN model, i.e., h(i,L)u , as ui. Formally, for two nodes, i.e., node u and node v, with different attributes or different neighbors on the original graph, the multi-sets of their representations based on the K sampled graphs under L layers base GNN model are:
Multi− set(u) = {u1, u2, · · · , uK}, Multi− set(v) = {v1, v2, · · · , vK}. (10) We provide the following theorem and prove it in Appendix C to demonstrate that we can obtain different multi-sets for these two nodes with high probability.
Theorem As the number of samples increases, the probability that the multi-sets for two nodes with different attributes or different neighbors are different can be close to 1.
On the basis of the high probability of obtaining different multi-sets and the proven injective multiset function, i.e., MLP followed by “Sum”, the injectivity can be achieved among nodes.
Note that for the two nodes who are the same, i.e., they have the same attributes and neighbors, our DS-GNN also ensure that they have the same representation. This is because that we adopt node sampling instead of edge sampling. Under node sampling, the two identical nodes will lose this neighbor at the same time, otherwise, keeping the neighbor, as well as the representations obtained by base GNN model stay the same.

heading: 4 EXPERIMENTS

text: We use GCN and GAT as our base models and implement them under our proposed DS-GNN framework respectively, referred as DS-GCN and DS-GAT. The effectiveness of DS-GCN and DSGAT is evaluated on three benchmark datasets via multi-class classification. Detailed analysis of sampling times and sampling strategy are also provided. In addition, to enrich the type of node-level tasks, we also offer an multi-label classification task on a newly collected dataset from DouBan website1, namely DBMovie.

heading: 4.1 EXPERIMENTAL SETTINGS

text: We use Tensorflow to implement the proposed model and take Adam with an initial learning rate of 0.01 as optimizer. For the three benchmark datasets, we set a weight decay of 0.0005. For DBMovie, we do not use weight decay. Note that for the i-th sampling, we sample 10 times and take the average of these 10 sampled garphs as the result of the i-th sampling, preventing the instability of a single sampling. All GNN models has two layers and leverage Relu as the activation function of hidden layers. We add a ResNet (He et al., 2016) between the second GNN layer and the output layer. We run 1000 epochs and choose the model that performs the best on validation.

heading: 4.2 BASELINES

text: For the three benchmark datasets, GNNs have achieved large improvements than traditional methods. As a result, we choose the the representative GNN models, i.e., GCN (Kipf & Welling, 2016), GAT (Veličković et al., 2017), as the base GNN models and apply our DS-GNN to these two models. Additionally, we compare against the SOTA GNNs, including GraphSAGE (Hamilton et al., 2017), GIN (Xu et al., 2018a) and DropEdge (Rong et al., 2019). For the newly collected DBMovie dataset, we first consider traditional node classification methods as our baselines, including Multi-Layer Perceptrons (MLP), which only use node features, and graph embeddings (DeepWalk) (Perozzi et al., 2014), which only use graph structures. Since GNNs are proved to be effective in graph-based learning, we also compare against GCN and GAT.

heading: Datasets Nodes Edges Classes Features Train/Validation/Test Node-level Task

heading: 4.3 NODE-BASED MULTI-CLASS CLASSIFICATION

text:
To evaluate the proposed method on node-based multi-class classification, we conduct experiments on the three benchmark datasets, namely, Cora, CiteSeer, PubMed. The first three rows in Table 1 show an overview of these three multi-class datasets. To better verify the ability of each model and
1https://movie.douban.com/
eliminate the effect of other factors such as data insufficiency, we follow the data split in DropEdge (Rong et al., 2019).

heading: Performance on Node-based Multi-class Classification

heading: Method Cora CiteSeer PubMed

text: Experimental results are reported in Table 2. Additionally, we provide the corresponding standard deviation in Appendix D. Similar to previous research, we report the mean classification accuracy over nodes in test set for quantitative evaluation. DS-GNN methods all achieve improvements over base models (indicated by the bold numbers), e.g., in CiteSeer, DS-GCN (79.9%) achieves large improvement over GCN (75.9%). Furthermore, applying our proposed method to the base GNN models can achieve the better performance, outperforming the state-of-the-art models. Compared with DropEdge which takes GCN as base model, our DiverseSample (DS) mechanism achieves better or comparable results.

heading: Analysis of Sampling Numbers K

text: To analyze the impact of sampling timesK, we show the accuracy of Cora with differentK in Fig. 3. It is observed that the accuracy increases as K becomes larger at the beginning. This is owing to the increasing probability of achieving injectivity. When K continues to increase, the injective probability becomes stable and close to 1, resulting in the accuracy also showing a stability. The results show that we can achieve better experimental results with a small K, e.g., K = 5 in Fig. 3), which proves the practicability of our method.

heading: Analysis of Sampling Strategy

text:
To evaluate the effectiveness of the proposed diverse sampling strategy, we compare it with random sampling strategy. Fig. 4 show the accuracy of Cora and CiteSeer with different initial node sampling probability pinit respectively when sampling times K = 5. The results demonstrate that: 1) the performance of random sampling will be significantly affected by pinit. The model performs poor with a relatively small pinit, while the model effect is significantly improved when pinit increases. Thus, random sampling requires a relatively large pinit to maintain the sampling effect and model
performance. 2) The performance of Diverse sampling is relatively stable, obtaining comparable performance even with a small pinit. This is owing to diverse sampling considers the three guidelines mentioned earlier, which proves the effectiveness of the diverse sampling strategy we proposed.
Furthermore, under diverse sampling, we observe that the best pinit are different among datasets. If better results achieved under a smaller pinit, our diverse sampling can achieve improvements over random sampling. Also, it is observed that Cora performs well with a larger pinit, while CiteSeer achieves better performance when pinit is smaller, i.e., Cora tends to keep more edges in sampled graphs. Similarly, PubMed also performs better when pinit is smaller. The reason may be related to the property of label smoothness “λ” proposed in CS-GNN (Hou et al., 2019), which measures the quality of surrounding informations. A larger λ implies that nodes with different labels are connected in the graph. In CS-GNN, Cora has a smaller λ = 0.19, while Citeseer with a larger λ = 0.26 as well as PubMeb with λ = 0.5. These values indicate that the surrounding informations are of higher quality in Cora, which explain why Cora prefers to keep more edges.

heading: 4.4 NODE-BASED MULTI-LABEL CLASSIFICATION

text: To enrich the type of node-level tasks, we collect a new dataset from the DouBan website and offer an multi-label classification task. Each sample in this dataset has its descriptions (features), genres (labels), and similar movies (edges), as illustrated in Fig. 5. These similar movies (edges) are directly provided by DouBan website based on user co-preference. This dataset has 28 labels and each movie may have more than one label. We define the task as tagging the movie with its own labels. The last row in Table 1 shows an overview of the newly collected DBMovie dataset.

heading: Performance on Node-based Multi-label Classification

text: We now validate the effectiveness of DS-GCN and DS-GAT. For node-based multi-label classification, we leverage the widely used ranking metrics to evaluate our method, including Mean Average Precision (MAP), F1, and Normalized Discounted Cumulative Gain (NDCG). These metrics encourage the correct label to be placed ahead of irrelevant labels, and a larger value indicates better performance. Experimental results on DBMovie are reported in Table 3. In the multi-label classification task, GNN models, i.e., both GCN and GAT, also perform much better than traditional methods, including MLP (only using attributes) and DeepWalk (only using only). GAT performs better than GCN, owing to its attention mechanism to learn edge weight. Under all evaluation metrics, our proposed method achieves consistently an improvement over GCN and GAT, showing an increased expressive power of model.

heading: 5 CONCLUSION

text: We proposed DS-GNN to improve the expressive power of graph neural networks. Different from previous methods that aim to implement injectivity via designing complicated layer-wise aggregation functions, we focus on designing the diverse rooted sub-graphs for each node. To enhance the diversity of rooted sub-graphs, we design the diverse sampling strategy. As the number of samples increases, we can achieve injectivity with higher probability. Extensive experiments on nodebased multi-class classification and node-based multi-label classification prove that our method can achieve improvements over the baselines. In the future, we consider to extend our method to graph classification scenarios.

heading: A DESCRIPTION OF BASE MODELS

text:
The two basic models Graph Convolutional Networks (GCN) and Graph Attention Networks (GAT) output the probability distributions Z over labels for all the nodes. Formally, the probability distributions are calculated as follows
Z = f(X,A) = softmax(ÂReLU(ÂXW (0))W (1)), (11)
where W (0) ∈ Rp×d and W (1) ∈ Rd×m are weight matrices with d as the dimension of the hidden layer. The first layer leverages rectified linear unit (ReLU), and the second layer leverages softmax to obtain a probability distribution Z ∈ Rn×m. Z is a row-normalized matrix, where each row represents the probability that the node belongs to corresponding labels.
In GCN, Â = D− 1 2 ÃD− 1 2 is the symmetric normalized adjacency matrix with Ã = A+ I , and I is the identity matrix. D ∈ Zn×n is the diagonal degree matrix with Dii = ∑ j Ãij .
While, GAT modifies Â by introducing the attention mechanism:
Âij = exp(LeakyReLU(aT [hi||hj ]))∑
k∈N(vi) exp(LeakyReLU(a T [hi||hk]))
, (12)
where N(vi) is the set of neighboring nodes of node vi, a ∈ R2d is the attention vector, hi ∈ Rd is the representation of the i-th node, and || is the concatenation operator.

heading: B THE DIFFERENCES BETWEEN NODE SAMPLING AND OTHER RELATED

text:
CONCEPTS
We contrast the differences between node sampling and other related concepts including dropping features and dropping edges. The Dropout (Srivastava et al., 2014) is proposed to prevent overfitting by randomly dropping features. Dropping edges can be regarded as a generation of dropout from dropping features to dropping edges. DropEdge (Rong et al., 2019) proposed randomly setting the elements in the adjacency matrix to be zeros. Also, some recent methods, including GraphSAGE (Hamilton et al., 2017), ASGCN (Huang et al., 2018), can be seen as dropping edges. These methods extend GNN to large graphs by sampling neighbors for each node, i.e., sampling a neighbor is equivalent to sampling an edge. Hasanzadeh (Hasanzadeh et al., 2020) propose a general framework for these methods. However, for our method, dropping edges may cause that two nodes who are the same with identical neighbors obtain different representations, since dropping edge cannot guarantee that these two nodes still have identical neighbors after edge sampling. Thus we leverage node sampling, ensuring that the nodes with the same input features and identical neighbors will still have the same representation.

heading: C PROOF OF THEOREM

text:
Theorem As the number of samples increases, the probability that the multi-sets for two nodes with different attributes or different neighbors are different can be close to 1.
Proof: Let p denote the probability that representations of node u and node v are same on the i-th sampled graph, i.e., p = Probability(ui = vi). (13) Let q denote the the probability that representations of node u and node v are same on two different sampled graphs, i.e., q = Probability(ui = vj) for i 6= j. (14) It’s reasonable to assume that such a probability based on different sampled graphs is smaller than base on the same sampled graph, i.e., q <= p.
For the two multi-sets, without losing generality, we can sort the element in each multi-set by descending order based on a specified uniform ordering rules. After sorting, the two multi-sets can be written as
Multi− set(û) = {ui1 , ui2 , · · · , uiK}, Multi− set(v̂) = {vj1 , vj2 , · · · , vjK}, (15)
where ik represent the original index of uik in Multi− set(u), so as jk. For these two sorted multisets, if and only if their elements be equal at each position, these two sorted multi-sets can be the same, otherwise they are different.
As we defined, the probability of “uik = vjk” is smaller than p, thus the probability that two multisets are the same can be defined as following based on Bayesian Equation:
probability(Multi− set(û) = Multi− set(v̂)) ≤ p× p(ui2 = vj2 |ui1 = vj1)× · · · × p(uiK = vjK |ui1 = vj1 , · · · , uiK−1 = vjK−1).
(16)
Therefore, the probability that the injectivity can be achieved between the two multi-sets is larger than 1− probability(Multi− set(û) = Multi− set(v̂)). Since u and v have different attributes or neighbors, each item in Eq. 16 can be smaller than 1. Thus, with large number of samplings, we can achieve injectivity with a high probability.

heading: Method Cora CiteSeer PubMed

heading: D STANDARD DEVIATION OF NODE-BASED MULTI-CLASS CLASSIFICATION

title: TOWARDS POWERFUL GRAPH NEURAL NETWORKS: DIVERSITY MATTERS


summaries: The authors explored the robustness of video machine learning models to bit-level corruption. They investigated previous methods such as Out-Of-Distribution (OOD) detection and adversarial training and found that they are not effective enough to defense against the bit-level corruption.  Accordingly, this paper proposed a new framework, Bit-corruption Augmented Training (BAT), which utilizes the knowledge about corruption by bit-level data augmentation at the training stage. Also, the authors argue that the proposed method outperforms the previous methods in handling the bit-level corrupted dataset.

summaries: The authors evaluate the effect of bit-level corruption, including network packet losses and bit corruptions, on video models such as action recognition and multi-object tracking. They found that the model performances drop significantly under severe corruption levels. To overcome this issue, they propose a defense method named Bit-corruption Augmented Training (BAT) to enhance the robustness of the model by embedding corrupted video samples in the training process. Results show that BAT is able to improve the model robustness over other methods such as Out-Of-Distribution (OOD) detection and Adversarial Training (AT).

summaries: This work investigates the problem of building robust video prediction models in the presence of signal corruption. The problem itself is not widely studied and experimental work like this one certainly opens some possibilities. The solution on the other hand is surprisingly simple and easy to implement. It serves the purpose of introducing the problem to a wider audience, and shed some light in different types of remedies.

abstractText: We investigate the robustness of video machine learning models to bit-level network and file corruptions, which can arise from network transmission failures or hardware errors, and explore defenses against such corruptions. We simulate network and file corruptions at multiple corruption levels, and find that bit-level corruptions can cause substantial performance drops on common action recognition and multi-object tracking tasks. We explore two types of defenses against bit-level corruptions: corruption-agnostic and corruption-aware defenses. We find that corruption-agnostic defenses such as adversarial training have limited effectiveness, performing up to 11.3 accuracy points worse than a no-defense baseline. In response, we propose Bit-corruption Augmented Training (BAT), a corruptionaware baseline that exploits knowledge of bit-level corruptions to enforce model invariance to such corruptions. BAT outperforms corruption-agnostic defenses, recovering up to 7.1 accuracy points over a no-defense baseline on highly-corrupted videos while maintaining competitive performance on clean/near-clean data.

authors:
A.O. Adeyemi-Ejeye
M. Alreshoodi
L. Al-Jobouri
M. Fleury
J. Woods

title: Packet loss visibility across sd, hd, 3d, and uhd video streams

venue: Journal of Visual Communication and Image Representation,

authors:
Ayse Elvan Aydemir
Alptekin Temizel
Tugba Taskaya Temizel

title: The effects of jpeg and jpeg2000 compression on attacks using adversarial examples, 2018

authors:
Yuval Bahat
Gregory Shakhnarovich

title: Confidence from invariance to image transformations, 2018

authors:
Itamar Ben-Ari
Ravid Shwartz-Ziv

title: Attentioned convolutional LSTM inpaintingnetwork for anomaly detection in videos

authors:
Mariusz Bojarski
Davide Del Testa
Daniel Dworakowski
Bernhard Firner
Beat Flepp
Prasoon Goyal
Lawrence D Jackel
Mathew Monfort
Urs Muller
Jiakai Zhang

title: End to end learning for self-driving

authors:
Nicholas Carlini
David Wagner

title: Towards evaluating the robustness of neural networks, 2016

authors:
Yair Carmon
Aditi Raghunathan
Ludwig Schmidt
Percy Liang
John C. Duchi

title: Unlabeled data improves adversarial robustness, 2019

authors:
Joao Carreira
Andrew Zisserman

title: Quo vadis, action recognition? a new model and the kinetics

authors:
Joao Carreira
Eric Noland
Chloe Hillier
Andrew Zisserman

title: A short note on the kinetics-700 human action

authors:
Yiping Chen
Jingkang Wang
Jonathan Li
Cewu Lu
Zhipeng Luo
Han Xue
Cheng Wang

title: Lidar-video driving dataset: Learning driving policies effectively

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Nilaksh Das
Madhuri Shanbhogue
Shang-Tse Chen
Fred Hohman
Siwei Li
Li Chen
Michael E. Kounavis
Duen Horng Chau

title: Shield: Fast, practical defense and vaccination for deep learning using jpeg compression, 2018

authors:
Patrick Dendorfer
Hamid Rezatofighi
Anton Milan
Javen Shi
Daniel Cremers
Ian Reid
Stefan Roth
Konrad Schindler
Laura Leal-Taixé

title: Mot20: A benchmark for multi object tracking in crowded scenes, 2020

authors:
J. Deng
W. Dong
R. Socher
L. Li
Kai Li
Li Fei-Fei

title: Imagenet: A large-scale hierarchical image database

venue: IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Gintare Karolina Dziugaite
Zoubin Ghahramani
Daniel M. Roy

title: A study of the effect of jpg compression on adversarial images, 2016

authors:
Daniel Y. Fu
Will Crichton
James Hong
Xinwei Yao
Haotian Zhang
Anh Truong
Avanika Narayan
Maneesh Agrawala
Christopher Ré
Kayvon Fatahalian

title: Rekall: Specifying video events using compositions of spatiotemporal labels. 2019

authors:
Adrien Gaidon
Zaid Harchaoui
Cordelia Schmid

title: Temporal localization of actions with actoms

venue: IEEE transactions on pattern analysis and machine intelligence,

authors:
Aishwarya Ganesan
Ramnatthan Alagappan
Andrea C. Arpaci-Dusseau
Remzi H. ArpaciDusseau

title: Redundancy does not imply fault tolerance: Analysis of distributed storage reactions to file-system faults

venue: ACM Trans. Storage,

authors:
Yonatan Geifman
Ran El-Yaniv

title: Selectivenet: A deep neural network with an integrated reject option, 2019

authors:
Robert Geirhos
Patricia Rubisch
Claudio Michaelis
Matthias Bethge
Felix A. Wichmann
Wieland Brendel

title: Imagenet-trained cnns are biased towards texture; increasing shape bias improves accuracy and robustness, 2018

authors:
Ian J. Goodfellow
Jonathon Shlens
Christian Szegedy

title: Explaining and harnessing adversarial examples

authors:
Matt Gorbett
Nathaniel Blanchard

title: Utilizing network properties to detect erroneous inputs, 2020

authors:
Chuan Guo
Geoff Pleiss
Yu Sun
Kilian Q Weinberger

title: On calibration of modern neural networks

venue: In Proceedings of the 34th International Conference on Machine Learning-Volume

authors:
Chuan Guo
Mayank Rana
Moustapha Cissé
Laurens van der Maaten

title: Countering adversarial images using input transformations

authors:
Matheus Gutoski
Nelson Marcelo Romero Aquino
Manassés Ribeiro
André Lazzaretti
Heitor Lopes

title: Detection of video anomalies using convolutional autoencoders and one-class support vector machines

authors:
Dan Hendrycks
Thomas Dietterich

title: Benchmarking neural network robustness to common corruptions and perturbations, 2019

authors:
Dan Hendrycks
Kevin Gimpel

title: A baseline for detecting misclassified and out-of-distribution examples in neural networks, 2016

authors:
Dan Hendrycks
Norman Mu
Ekin D. Cubuk
Barret Zoph
Justin Gilmer
Balaji Lakshminarayanan

title: Augmix: A simple data processing method to improve robustness and uncertainty, 2019

authors:
Dan Hendrycks
Steven Basart
Norman Mu
Saurav Kadavath
Frank Wang
Evan Dorundo
Rahul Desai
Tyler Zhu
Samyak Parajuli
Mike Guo
Dawn Song
Jacob Steinhardt
Justin Gilmer

title: The many faces of robustness: A critical analysis of out-of-distribution generalization, 2020

authors:
Zhiguo Hu
Qiqiang Zhang

title: A new approach for packet loss measurement of video streaming and its application

venue: Multimedia Tools Appl.,

authors:
Nathan Inkawhich
Matthew Inkawhich
Yiran Chen
Hai Li

title: Adversarial attacks for optical flow-based action recognition

authors:
Bart Jansen
Timothy Goodwin
Varun Gupta
Fernando Kuipers
Gil Zussman

title: Performance evaluation of webrtc-based video conferencing

venue: SIGMETRICS Perform. Eval. Rev.,

authors:
Linxi Jiang
Xingjun Ma
Shaoxiang Chen
James Bailey
Yu-Gang Jiang

title: Black-box adversarial attacks on video recognition models

venue: In Proceedings of the 28th ACM International Conference on Multimedia,

authors:
Hirokatsu Kataoka
Tenga Wakamiya
Kensho Hara
Yutaka Satoh

title: Would mega-scale datasets further enhance spatiotemporal 3d cnns

authors:
H. Kuehne
H. Jhuang
E. Garrote
T. Poggio
T. Serre

title: HMDB: a large video database for human motion recognition

venue: In Proceedings of the International Conference on Computer Vision (ICCV),

authors:
Laura Leal-Taixé
Anton Milan
Ian Reid
Stefan Roth
Konrad Schindler

title: Towards a benchmark for multi-target tracking

venue: Motchallenge

authors:
B. Lee
J. Chang

title: Packet loss concealment based on deep neural networks for digital speech transmission

venue: IEEE/ACM Transactions on Audio, Speech, and Language Processing,

authors:
Kimin Lee
Kibok Lee
Honglak Lee
Jinwoo Shin

title: A simple unified framework for detecting out-of-distribution samples and adversarial attacks, 2018

authors:
Shiyu Liang
Yixuan Li
R Srikant

title: Enhancing the reliability of out-of-distribution image detection in neural networks

venue: International Conference on Learning Representations (ICLR),

authors:
Si Liu
Risheek Garrepalli
Thomas G. Dietterich
Alan Fern
Dan Hendrycks

title: Open category detection with pac guarantees, 2018

authors:
Weitang Liu
Xiaoyun Wang
John D. Owens
Yixuan Li

title: Energy-based out-of-distribution detection, 2020

authors:
R. Lotfidereshgi
P. Gournay

title: Speech prediction using an adaptive recurrent neural network with application to packet loss concealment

venue: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP),

authors:
Aleksander Madry
Aleksandar Makelov
Ludwig Schmidt
Dimitris Tsipras
Adrian Vladu

title: Towards deep learning models resistant to adversarial attacks, 2017

authors:
Mostafa M. Mohamed
Björn W. Schuller

title: Concealnet: An end-to-end neural network for packet loss concealment in deep speech emotion recognition, 2020

authors:
Mathew Monfort
Alex Andonian
Bolei Zhou
Kandan Ramakrishnan
Sarah Adel Bargal
Tom Yan
Lisa Brown
Quanfu Fan
Dan Gutfruend
Carl Vondrick
Aude Oliva

title: Moments in time dataset: one million videos for event understanding, 2018

authors:
Seyed-Mohsen Moosavi-Dezfooli
Alhussein Fawzi
Omar Fawzi
Pascal Frossard

title: Universal adversarial perturbations, 2016

authors:
Muhammad-Sajid Mushtaq
Abdelhamid Mellouk

title: 2 - methodologies for subjective video streaming qoe assessment

venue: Quality of Experience Paradigm in Multimedia Services, pp

authors:
Itay Naeh
Roi Pony
Shie Mannor

title: Flickering adversarial attacks against video recognition

authors:
Ravi Netravali
Anirudh Sivaraman
Somak Das
Ameesh Goyal
Keith Winstein
James Mickens
Hari Balakrishnan

title: Mahimahi: Accurate record-and-replay for HTTP

venue: In 2015 USENIX Annual Technical Conference (USENIX ATC

authors:
T.J. O’Gorman
J.M. Ross
A.H. Taber
J.F. Ziegler
H.P. Muhlfeld
C.J. Montrose
H.W. Curtis
J.L. Walsh

title: Field testing for cosmic ray soft errors in semiconductor memories

venue: IBM Journal of Research and Development,

authors:
Aditi Raghunathan
Jacob Steinhardt
Percy Liang

title: Certified defenses against adversarial examples, 2018a

title: Semidefinite relaxations for certifying robustness to adversarial examples, 2018b

title: H.264 and MPEG-4 Video Compression

authors:
Evgenia Rusak
Lukas Schott
Roland S. Zimmermann
Julian Bitterwolf
Oliver Bringmann
Matthias Bethge
Wieland Brendel

title: A simple way to make neural networks robust against diverse image corruptions, 2020

authors:
Bianca Schroeder
Raghav Lagisetty
Arif Merchant

title: Flash reliability in production: The expected and the unexpected

venue: In 14th USENIX Conference on File and Storage Technologies (FAST

authors:
Rowan Seymour
Darryl Stewart
Ji Ming

title: Comparison of image transform-based features for visual speech recognition in clean and corrupted videos

venue: EURASIP Journal on Image and Video Processing,

authors:
Gopalan Sivathanu
Charles P. Wright
Erez Zadok

title: Ensuring data integrity in storage: Techniques and applications

venue: In Proceedings of the 2005 ACM Workshop on Storage Security and Survivability,

authors:
Khurram Soomro
Amir Roshan Zamir
Mubarak Shah

title: Ucf101: A dataset of 101 human actions classes from videos

venue: in the wild,

authors:
V. Srinivasan
S. Gul
S. Bosse
J.T. Meyer
T. Schierl
C. Hellge
W. Samek

title: On the robustness of action recognition methods in compressed and pixel domain

venue: In 2016 6th European Workshop on Visual Information Processing (EUVIP),

authors:
Christian Szegedy
Wojciech Zaremba
Ilya Sutskever
Joan Bruna
Dumitru Erhan
Ian Goodfellow
Rob Fergus

title: Intriguing properties of neural networks

authors:
Yusuke Tsuzuku
Issei Sato

title: On the structural sensitivity of deep convolutional networks to the directions of fourier basis functions, 2018

authors:
Jue Wang
Anoop Cherian

title: Contrastive video representation learning via adversarial perturbations, 2018

authors:
Xingxing Wei
Jun Zhu
Hang Su

title: Sparse adversarial perturbations for videos, 2018

authors:
Eric Wong
Leslie Rice
J. Zico Kolter

title: Fast is better than free: Revisiting adversarial training, 2020

authors:
Dong Yin
Raphael Gontijo Lopes
Jonathon Shlens
Ekin D. Cubuk
Justin Gilmer

title: A fourier perspective on model robustness in computer vision, 2019

authors:
Yifu Zhang
Chunyu Wang
Xinggang Wang
Wenjun Zeng
Wenyu Liu

title: A simple baseline for multi-object tracking, 2020

authors:
Yupu Zhang
Abhishek Rajimwale
Andrea C. Arpaci-Dusseau
Remzi H. Arpaci-Dusseau

title: Endto-end data integrity for file systems: A zfs case study

venue: In Proceedings of the 8th USENIX Conference on File and Storage Technologies,

authors:
Stephan Zheng
Yang Song
Thomas Leung
Ian Goodfellow

title: Improving the robustness of deep neural networks via stability training

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR),

heading: 1 INTRODUCTION

text:
Video is becoming an increasingly common data modality, with applications in online conferencing (Jansen et al., 2018), autonomous vehicles (Chen et al., 2018; Bojarski et al., 2016), action recognition (Kuehne et al., 2011; Soomro et al., 2012; Carreira & Zisserman, 2017), and event detection (Fu et al., 2019; Gaidon et al., 2013). Recent work in computer vision has studied the robustness of machine learning (ML) models to pixel-space corruptions such as adversarial examples (Madry et al., 2017; Carlini & Wagner, 2016; Goodfellow et al., 2014; Moosavi-Dezfooli et al., 2016; Szegedy et al., 2013). However, in the real world, videos are susceptible to corruptions beyond the pixels, such as bit-level network and file corruptions (Fig. 1).
Bit-level corruptions are generally non-adversarial and arise in the real world from network congestion (Mushtaq & Mellouk, 2017), i.e., transmission problems in video conferencing, or hardware errors during storage (Sivathanu et al., 2005; Zhang et al., 2010). These corruptions spuriously modify bits in a video file, leading to data loss or visual distortion (e.g. object duplication, noisy patches, or freeze-frames). Although some previous work in computer vision robustness has been compresssion-aware, e.g. studying the effects of JPEG compression (Aydemir et al., 2018; Dziugaite et al., 2016; Das et al., 2018) or changing bitrates (Guo et al., 2017b), direct corruptions to the bit representations of videos remain underexplored.
In this work, we take a first step in understanding video model robustness to naturally-occurring levels of network and file corruptions, and explore baseline defenses to these corruptions. To this end, we simulate a wide range of corruption severity levels consistent with empirical studies of real-world corruptions (Schroeder et al., 2016; Hu & Zhang, 2018), and explore their effects on video artifacts and model performance. We evaluate model performance on two action recognition datasets (Kuehne et al., 2011; Soomro et al., 2012) and one multi-object tracking dataset (LealTaixé et al., 2015) under simulated network packet loss and random bit-flip file corruptions. Our experiments demonstrate that model performance begins to degrade when packet loss rates exceed 1%, or when the proportion of randomly-flipped bits in a file exceeds 10´6, and ultimately drops by up to 77.1% under the most severe corruption levels.
We then focus on exploring two categories of defenses against network and file corruptions: corruption-agnostic methods without knowledge of bit-level corruptions, and corruption-aware methods that exploit knowledge of bit-level corruptions to enforce model invariance to network and file corruptions. For corruption-agnostic defenses, we evaluate out-of-distribution (OOD) detection (Hendrycks & Gimpel, 2016; Liang et al., 2018) and adversarial training (Goodfellow et al., 2014) as baselines. Our findings suggest that corruption-agnostic defenses have limited effectiveness, especially at low corruption levels; for example, under adversarial training, model performance drops by up to 11.3 points on corrupted data, and 8.6 points on clean data, compared to the no-defense baseline.
In response, we propose Bit-corruption Augmented Training (BAT), a corruption-aware baseline. BAT augments data with corrupted video files from randomly chosen bit-level corruptions during training. Experiments show that BAT recovers up to 7.1 points over a no-defense baseline on highlycorrupted videos, while maintaining competitive performance on clean/near-clean data. This suggests that the noise structure of bit-level corruptions is fundamentally different from that of adversarial noise, and that incorporating knowledge of bit-level corruptions is crucial to model robustness against network and file corruptions. Lastly, to better understand the effect of augmenting with different corruptions, we explore variants of BAT that sample augmentations from different subsets of simulated corruptions. Interestingly, we find that augmenting with high levels of network and file corruption is key to improving model robustness, resulting in an accuracy gain of up to 10.1 points over the no-defense baseline. We conclude that BAT is a promising starting point for robustness to bit-level corruptions in video machine learning. Our results motivate future studies to understand and defend against bit-level corruption in ML robustness.

heading: 2 BIT-LEVEL VIDEO CORRUPTIONS

text: In this section, we first provide a brief overview on video encoding to provide intuition about the effects of network and file corruptions (Section 2.1), and then describe how we simulate a naturallyoccurring range of network and file corruptions (Section 2.2).

heading: 2.1 VIDEO ENCODING

text:
We present a simplified explanation of video encoding, using the H.264 codec as an example (Richardson, 2003). Let X “ RHˆWˆCˆT be the space of possible videos. An uncompressed video x P X consists of a sequence of frames. These frames are often redundant (i.e., two neighboring frames in a video are likely to look similar), so the H.264 codec stores only a small fraction of frames (known as I-frames) and encodes the remaining frames as differences from I-frames. To further save space, the frames go through a series of compression steps like frequency space conversion, quantization, and entropy encoding, much like JPEG compression. We notate the encoding process as the function Encpxq, which is a mapping from pixel-space to bit-space. The corresponding decoding function is denoted as Decp¨q.
The H.264 video codec is also equipped with error resilience and concealment techniques for repairing damaged data. For example, the codec might use uncorrupted portions of a frame to decode a corrupted frame (Arbitrary Slice Order/Flexible Macroblock Order), or store redundant portions of a frame for the same purpose. However, bit-level network/file corruptions can destroy particular information such that these methods are insufficient to restore visual quality; for example, I-frames are important references for decoding other frames, so corruptions to them often result in propagating noise patches or smearing artifacts throughout the video.

heading: 2.2 SIMULATING BIT-LEVEL CORRUPTIONS

text:
Network corruptions. We simulate packet loss, a network corruption where data packets are permanently lost during transmission (Fig. 2), which can result in visual quality drops in video streaming applications (Hu & Zhang, 2018; Adeyemi-Ejeye et al., 2017). We simulate packet loss by streaming videos using the Real-Time Streaming Protocol (RTSP) with UDP, dropping video packets randomly using the Mahimahi network emulator (Netravali et al., 2015). This setup targets real-time applications like video-conferencing that use UDP due to latency requirements.
File corruptions. We simulate random corruptions, a file corruption where random bits in a video file are erroneously flipped (Fig. 2). Such bit-flips occur as the result of hardware integrity issues like bus errors (Zhang et al., 2010), malicious software (Sivathanu et al., 2005), or cosmic rays (O’Gorman et al., 1996). Despite redundancy mechanisms in modern file systems, many such corruptions are unrecoverable due to unsafe faulthandling, or can persist undetected (Ganesan et al., 2017). In Appendix B, we additionally explore contiguous corruptions, another real-world bit-corruption pattern in which a contiguous segment of a file bitstream is replaced with random bits.
Corruption Levels. Our primary interest is in simulating naturally-occurring levels of bit-level corruptions. Thus, we choose ranges for p based on real-world empirical studies of packet loss and file corruption. Notationally, we describe corruptions with a parameter p P r0, 1s, the expected proportion of the video file corrupted. For packet loss, each packet is dropped with probability p. For random corruptions, we flip each bit with probability p. Real-world network traces have yielded packet loss rates from 0.31% to 12.38% (Hu & Zhang, 2018), so we simulate packet loss rates from 0.01% (p “ 10´4) up to 20% (p “ 0.2). On the file corruptions side, studies of flash memory have found median bit-error rates ranging from 6.0ˆ 10´10 to 1.0ˆ 10´5, with 99th percentile bit error rate up to 1.2 ˆ 10´4 (Schroeder et al., 2016), so we simulate file corruption rates from p “ 10´8 up to p “ 10´4. We provide more discussion of our chosen parameter settings in Appendix F.

heading: 3 BASELINE DEFENSES FOR BIT-LEVEL CORRUPTIONS

text: We explore three defenses as baselines for mitigating the impact of network and file corruptions. Broadly, these methods can be categorized as corruption-agnostic, which make no assumptions about network and file corruptions, or corruption-aware, which explicitly incorporate knowledge of network and file corruptions. As corruption-agnostic baselines, we evaluate out-of-distribution (OOD) detection and adversarial training (AT). We propose bit-corruption augmented training (BAT) as a corruption-aware baseline.

heading: 3.1 CORRUPTION-AGNOSTIC DEFENSES

text:
Network and file corruptions often result in severe visual artifacts (see Section 4.2 for some examples). As a result, these corrupted videos can be viewed as out-of-distribution examples, particularly for large amounts of corruption. In such cases, a natural defense for pre-trained video models is OOD detection, a test-time technique that attempts to identify out-of-distribution videos and filters them out. This method requires no model retraining, and makes zero assumptions about the noise structure.
As an overview of OOD detection, we consider a ML model fpx; θq : RHˆWˆCˆT Ñ RK with parameters θ, which are optimized under categorical cross-entropy loss:
min θ
ÿ
px,yq„P `pFθpxq, yq,
where Fθpxq is the softmax output. We use ODIN (Liang et al., 2018), a standard OOD detection method that uses calibrated softmax score Sθpxq as an indicator score for flagging OOD examples:
Sθpxq “ max j
efjpx;θq{T ř
i e fipx;θq{T
,
where T is a temperature scaling parameter (Guo et al., 2017a), and fipx; θq is the logit value for class i. The calibrated score Sθpxq is then compared against a preset threshold (often 95% TPR) computed on in-distribution data; x is flagged as OOD if it falls below the threshold and is marked as in-distribution otherwise. The idea is that corrupted videos yield lower average calibrated scores than clean videos.
Adversarial Training (AT). Adversarial training (Goodfellow et al., 2014) is a common technique that makes models robust to small adversarial perturbations. Adversarial training optimizes
min θ
ÿ
px,yq„P max ||δ||8ďε
`pFθpx` δq, yq,
where ε is the perturbation budget, or maximum permissible L8-norm of perturbation δ. We use the training scheme proposed in Wong et al. (2020), where an initial δ is randomly chosen from the pL8, εq-neighborhood of a video x. Then, the above objective is iteratively optimized for one step. This method requires model retraining, and assumes that the noise structure of test-time input is adversarial.

heading: 3.2 CORRUPTION-AWARE DEFENSES

text:
Bit-corruption Augmented Training (BAT). We consider a corruption-aware baseline defense that exploits knowledge of bit-level corruptions to enforce invariance to network and file corruptions. In particular, we propose Bit-corruption Augmented Training (BAT), which regularizes the video model by augmenting training data with examples from randomly chosen bit-level corruptions:
min θ
ÿ
px,yq„P,τPC Z`pFθppDec ˝ τ ˝ Encqpxqq, yq ` p1´ Zq`pFθpxq, yq,
where C is the set of possible network and file corruptions, τ is a randomly chosen corruption for a particular video x applied with probability 0.5 (shown with indicator variable Z P Bernoulli(0.5)). Enc and Dec denote the video encoding and decoding transformations, respectively, and ˝ denotes function composition. This method assumes prior knowledge about the nature of network and file corruptions, but not the exact corruption parameters for test-time videos. To better understand the effect of augmenting with different corruptions, we also consider variants of BAT that augment with a subset of corruption parameters.

heading: 4 EFFECT OF BIT-LEVEL CORRUPTIONS ON VIDEO MODELS

text: We provide an overview of our datasets and models in Section 4.1. In Section 4.2, we report the impact of bit-level corruptions on video model performance. We then report the performance of preexisting corruption-agnostic defenses (Section 4.3), as well as Bit-corruption Augmented Training (BAT) as a corruption-aware defense (Section 4.4), finding that BAT outperforms the corruptionagnostic defenses. We also discuss variants of BAT to study the effect of training with particular subsets of the available corruptions.

heading: 4.1 DATASETS AND MODELS

text:
HMDB51. The Human Motion DataBase (HMDB51) (Kuehne et al., 2011) is a 51-class action recognition benchmark comprised of movie scenes and web videos. We use a pre-trained 3DResnet18 architecture fine-tuned on HMDB51 split 1 (3520 train, 1530 test videos), using a standard
training setup (Kataoka et al., 2020). During evaluation, we split the input clip into contiguous 16- frame segments, outputting the action class with the highest probability averaged over all segments. We report top-1 accuracy.
UCF101. UCF101 (Soomro et al., 2012) is a 101-class action recognition benchmark comprised of web videos. Our setup is identical to that of HMDB51: we fine-tune a pre-trained 3D-Resnet18 architecture on UCF101 split 1 (9537 train, 3783 test videos) using the setup of Kataoka et al. (2020). We report top-1 accuracy.
MOT15. MOT15 (Leal-Taixé et al., 2015) is a multi-object tracking dataset. We use a DLANet-34 (Deep Layer Aggregation) architecture (Zhang et al., 2020) pre-trained on MOT20 (Dendorfer et al., 2020). We evaluate on a subset of the train split of MOT15 (6 clips, 12885 objects) following the setup in Zhang et al. (2020). We report object detection rate (1´FPR), representing the proportion of objects correctly detected.

heading: 4.2 EFFECTS OF BIT-LEVEL CORRUPTIONS

text:
Effects of bit-level corruptions on video model performance. We evaluate model performance on playable1 videos under bit-level corruptions, finding that model accuracy drops substantially as corruption level increases (Fig. 3). On HMDB51 and UCF101, for random file corruptions, accuracy drops under packet loss for p ą 0.01 and for random corruptions for p ą 10´6. Under packet loss, the performance drops reach 46.5% on HMDB51 and 32.6% on UCF101. For random file corruptions, the drop reaches 68.9% on HMDB51 and 77.1% on UCF101. On multi-object tracking, object detection rate drops to near 0 for all types of corruption. Notably, performance declines start at lower corruption levels for this task than for action recognition, starting at packet loss greater than p “ 10´3 and random corruption rates exceeding 10´7. More details on multi-object tracking performance are provided in Appendix E.
Pixel-space effects of bit-level corruptions. We visualize some corrupted videos to better understand the qualitative effects of bit-level corruptions. In general, misclassified videos are more visually distorted than correctly classified videos under corruption. We see this in Fig. 4: the model prediction changes as visual artifacts worsen and corruption level increases. Furthermore, under the same corruption type and proportion, visual artifacts correlate with erroneous model predictions, as seen in Fig. 5. In the leftmost pair of clips in Fig. 5, under packet loss (p “ 0.1), we see noisy patches in the Kayaking clip (incorrect), while the sky, grass, and person in the GolfSwing example (correct) are not distorted. Similar patterns hold for random corruption (Fig. 5, right). On MOT15, more distorted videos yield more false positive and false negative object detections. For visualizations of corrupted videos in MOT15, see Appendix E.
1Video files can become unplayable if file metadata is corrupted. Metrics are calculated on playable videos only: if a video is unplayable, the model does not output a prediction at all. We evaluate accuracy purely based on outputted model predictions. Appendix F gives a probabilistic overview of the effect of bit-level corruptions on video playability.
To quantify this visual distortion, we compute pixel-space Euclidean distance (L2 norm between pixels in corrupted vs. clean video clips). Fig. 3 shows the average L2 distance between corrupted and clean clips on the entire dataset (yellow), correctly classified examples (green), and incorrectly classified examples (red). Consistent with our qualitative analysis, incorrect examples have higher L2 distance on average than correct examples. Under packet loss, incorrect examples are up to 1.52 times more perturbed than correct examples on average (HMDB51, network corruption, top left). For random corruptions, incorrect examples are up to 1.57 more perturbed on average (UCF101, random corruption, bottom right). This strongly suggests that the visual severity of a network and file-corrupted video adversely affects model performance, as seen in Fig. 3.

heading: 4.3 CORRUPTION-AGNOSTIC DEFENSES FOR BIT-LEVEL CORRUPTIONS

text:
ODIN (Out-of-distribution Detection). As observed in Section 4.2, videos with larger pixelspace distortions are more likely to be misclassified, motivating OOD detection as a baseline for filtering out corrupted videos. This defense does not require modifying model parameters, and can be applied to any pre-trained model. Specifically, we use a HMDB51 clean test set as indistribution data, and a corrupted version of the same split as OOD data. During inference, we apply ODIN (Liang et al., 2018) with T “ 100 to corrupted datasets as a filter, setting the score threshold to the 5th percentile of calibrated scores on the in-distribution set (95% TPR).
We evaluate the effectiveness of ODIN based on its ability to successfully filter out corrupted videos. Figure 6 shows AUROC for whether ODIN can successfully filter out corrupted videos, as well as model accuracy on the videos labeled as in-distribution (clean). We observe that ODIN is best able to detect corrupted videos at high levels of corruption, with AUROC reaching 98.5% for the highest levels of random corruption. ODIN is less effective at discriminating packet loss, with AUROC only reaching 76.6% at the highest levels of corruption. At low levels of corruption, ODIN discards many clean/near-clean examples, as AUROC degrades to 0.5. This is consistent with Fig. 3, which
suggests that the pixel-space gap between correctly classified and incorrectly classified videos narrows at low levels of corruption, meaning that corrupted and clean videos are more distributionally similar. In conclusion, ODIN shows some promise for filtering out severely corrupted videos, but cannot effectively discriminate clean from corrupted video at low levels of corruption. Thus, applying ODIN for OOD detection could result in good performance in filtering out highly corrupted data at the expense of discarding clean/lightly corrupted data. We additionally run evaluation on energy-based OOD (Liu et al., 2020), with almost identical results. Full results on OOD detection can be found in Appendix D.
Adversarial Training. Given the pixel-space proximity between clean and corrupted videos at low levels of corruption (Fig. 3, right), we explore adversarial training (AT), a family of methods for increasing model robustness to small adversarial perturbations (Goodfellow et al., 2014; Madry et al., 2017). We follow the method in Wong et al. (2020). The best results (ε “ 2{255) are summarized in Table 1; larger ε “ 4{255, 8{255 yield worse performance (Appendix C). Interestingly, it appears that AT offers little to no utility in increasing robustness to bit-level corruptions, underperforming a nodefense baseline both on corrupted data by up to 11.3 points (packet loss, p “ 10´3), and on clean data by 8.6 points. This suggests that the noise structure of bit-level corruptions is fundamentally
different from that of adversarial noise, and that this form of AT may not be a viable defense against bit-level corruptions.

heading: 4.4 BIT-CORRUPTION AUGMENTED TRAINING

text:
We propose Bit-corruption Augmented Training (BAT) as a baseline corruption-aware defense that injects knowledge of file/network corruptions into video ML models. This technique augments training data with examples subjected to a randomly chosen network and file corruptions. We report the results of BAT, as well as a few variants, in Table 1. Overall, BAT shows promise, providing up to 7.1% lift on highly-corrupted data (packet loss, p “ 0.2) over a no-defense baseline. On
clean/near-clean data, BAT does only slightly worse than a no-defense baseline. This slight drop is likely attributable to the noise that BAT introduces into the model, since under BAT, we are now optimizing for accuracy not only on clean data, but also on corrupted data.
We study a few variants of BAT to determine which certain network and file corruptions are more important for increasing model robustness. First, we augment using two subsets of corruption levels: low levels of corruption, i.e. those that did not cause a significant performance drop on the baseline model, and high levels of corruption, i.e., corruption levels sufficient to cause significant performance drops in the baseline model2. Training on low levels of corruption (BAT-Low) decreases model robustness across almost all levels of corruptions, but training with high levels of corruption (BAT-High) results in an accuracy gain of up to 10.1% (random file corruption, p “ 10´4) over the no-defense baseline—and outperforms vanilla BAT at almost all levels of corruption. As with vanilla BAT, the lift over the no-defense baseline is correlated with corruption proportion. This suggests that augmenting with highly corrupted videos in particular is key to increased robustness.
Lastly, we explore the effect of training and testing on the same corruption type and level (BATOracle) as an oracle model with perfect knowledge of the corruption parameters the model will encounter. Though this assumption is unrealistic, BAT-Oracle provides insight into the utility of incorporating particular corruption levels within the BAT augmentation scheme. Interestingly, this technique lags behind BAT-High at high levels of corruption, and performs worse than BAT, BATHigh, and the no-defense baseline at low levels of corruption. This suggests that training on a variety of different corruptions is important for increasing robustness. Thus, BAT is a promising starting point for improving robustness to bit-level corruptions in video machine learning, especially for more severe corruptions. Our results motivate future studies of understanding and defending against bit-level corruptions.

heading: 5 RELATED WORK

text:
Robustness in computer vision. Imagenet-C and -P (Hendrycks & Dietterich, 2019) are ImageNet (Deng et al., 2009) extensions for benchmarking image classifiers with non-adversarial corruptions. Hendrycks et al. (2020) studies model robustness to distributional shifts like occlusion and perspective shift. The effect of frequency-domain features on convolutional networks has also been studied (Yin et al., 2019; Tsuzuku & Sato, 2018). On the adversarial side, Szegedy et al. (2013) introduce the idea of adversarial examples in ML, while Goodfellow et al. (2014); Zheng et al. (2016); Madry et al. (2017) propose methods for creating and defending against adversarial input. Recent works also extend adversarial attacks to the video domain (Wang & Cherian, 2018; Wei et al., 2018; Inkawhich et al., 2018; Jiang et al., 2019; Naeh et al., 2020). Our work is not only an extension of previous image ML robustness studies to video, but also a study of network and file corruptions, which remain underexplored in the robustness literature.
Defenses against corrupted data. Augmenting data with speckle noise (Rusak et al., 2020), style transfer (Geirhos et al., 2018), mixtures of augmentations (AugMix) (Hendrycks et al., 2019), and distortions constructed from image-to-image networks (DeepAugment) (Hendrycks et al., 2020) have been shown to increase robustness to common corruptions like Imagenet-C. Other defenses include certificate-based methods (Raghunathan et al., 2018a;b) or self-supervision (Carmon et al., 2019). Non-adversarial perturbations can be interpreted as OOD data, for which supervised (Lee et al., 2018; Bahat & Shakhnarovich, 2018; Geifman & El-Yaniv, 2019; Gorbett & Blanchard, 2020) and semi-supervised OOD detection techniques (Liu et al., 2018) have been proposed. Video anomaly detection techniques are also explored in (Ben-Ari & Shwartz-Ziv, 2018; Gutoski et al., 2017). Adversarial training (Goodfellow et al., 2014; Madry et al., 2017) is a common defense to adversarial corruptions. We evaluate baseline non-adversarial and adversarial robustness techniques, and extend the augmentation-as-defense paradigm to bit-level corruptions.
Bit-space aware robustness studies. Previous work has studied the robustness of computer vision models under various aspects of image and video compression, such as compression rates or encoding schemes (Srinivasan et al., 2016; Seymour et al., 2007). On the network side, deep learningbased packet loss concealment (Lee & Chang, 2016; Lotfidereshgi & Gournay, 2018; Mohamed & Schuller, 2020) techniques aim to recover from packet loss by predicting lost information. We view
2Exact corruption parameters for low/high levels of corruption are described in Appendix F.
our work as complementary to previous efforts, extending robustness studies to explicitly examine the effect of network and file corruptions at the bit-level on video model performance.

heading: 6 CONCLUSION

text: In this paper, we take a first step in investigating the effect of network and file corruptions on video model robustness, finding that these corruptions significantly decrease performance on benchmark tasks like action recognition and multi-object tracking. We propose a corruption-aware defense baseline, Bit-corruption Augmented Training (BAT), which incorporates knowledge of network and file corruptions directly. We show that BAT can improve performance by up to 7.1% accuracy, and outperforms corruption-agnostic baselines (OOD detection and AT) at a wide range of corruption levels while perserving performance on clean data. Further experiments highlight the utility of augmenting with high levels of corruption in particular. This suggests that exploiting knowledge of network and file corruptions in model training is important for improving robustness, making BAT a compelling starting point for future studies of network and file corruptions and model robustness. We hope this work motivates future studies of defenses against network and file corruptions, as well as other real-world non-adversarial corruptions.

heading: A METRICS INCLUDING READABLE FILES

text: For completeness, we provide performance metrics here for accuracy on all videos, including unplayable videos. Unplayable videos are logged as incorrect. We notice similar trends as described in Table 3, in that BAT outperforms the no-defense baseline at high levels of corruption, and is close to the no-defense baseline at low corruption of accuracy. We also see similar results on the variants: BAT-High outperforms BAT at high levels of corruption, which suggests that augmenting with high levels of corruption is important for model robustness, while BAT-Oracle underperforms BAT in general, suggesting that augmenting with a wide range of corruptions positively influences model robustness. These are the same conclusions drawn in Section 4.4. As observed earlier, adversarial training generally hurts model performance.

heading: B A STUDY ON CONTIGUOUS FILE CORRUPTIONS

text: We present a study on contiguous file corruptions. In contiguous corruptions, a segment of a video bitstream is replaced with random bits. These errors occur due to sudden temperature changes (thermal asperity), malware (Sivathanu et al., 2005), or misdirected data writes (Zhang et al., 2010). While these corruptions are plausible in the real world, corruptions do not yield significant performance drops or artifacts until over 10% of the file bitstream in all files are corrupted. For completeness, we include results on this type of corruption in Table 2, as well as in the remaining results in the Appendix.

heading: C FULL RESULTS OF ADVERSARIAL TRAINING

text: In summary, adversarial training offers little to no utility in defending against network corruptions. In Table 4, we see that at all levels of corruption except for random corruption, p “ 5e ´ 5 and contiguous corruption, p “ 0.9, adversarially trained models are significantly less accurate than the normally trained model. We also notice that as ε decreases (i.e. the adversary weakens), adversarial training accuracy tends to get closer to baseline accuracy. Interestingly, the gap between an adversarially trained model and the baseline model narrows as corruption proportion increases. Thus, this mode of adversarial training is an insufficient defense against network and file corruptions.

heading: D FULL RESULTS OF OUT-OF-DISTRIBUTION DETECTION

text:
D.1 MACHINE LEARNING-BASED SOLUTIONS
Table 5 provides full results for our study of ODIN OOD detection as a defense for network and file corruptions. We report in-distribution accuracy (left) and AUROC (right). As seen in Fig. 6, AUROC is relatively high at the maximum levels of corruption (76.6% on packet loss, 98.5% on random file corruptions), but drops down to essentially random at low levels of corruption.
Table 6 provides full results for the energy-based OOD detection (Liu et al., 2020) framework as a defense for network and file corruptions. As a brief overview, similarly to ODIN, energy-based OOD detection produces a score given by the Helmholtz free energy function, which is
Sθpxq “ ´T ¨ K ÿ
j
efjpx;θq{T ,
with T and fjpx; θq as defined for ODIN. We report in-distribution accuracy (left) and AUROC (right). The setup is identical to ODIN, except we have T “ 1 following the authors’ specification. Results for energy-based OOD detection are very similar to that of ODIN, with AUROC as high as 77.0% and 98.7% on packet loss and random
file corruptions, respectively. However, both techniques are near random at low levels of corruption. We provide a side-by-side comparison of ODIN and energy-based OOD detection in Figure ??, with plots of AUROC and in-distribution accuracy under packet loss and random file corruptions.
D.2 CHECKSUM-BASED FILE INTEGRITY CHECKS
In Table 7, we provide results testing the effectiveness of checksum-based file integrity checks, a model-agnostic, machine learning-free technique for detecting file corruption. We flag a video as corrupted/out-of-distribution if the checksums of the corrupted vs. original video fail to match. We use the MD5, SHA1, and SHA256 checksums using the corresponding Linux utilities; however, all checksums produced identical detections.
Ultimately, this method discards a large quantity of clean or near-clean videos, meaning that its effectiveness is limited. In fact, even re-streaming a video through a link with zero packet loss results in checksums no longer being equal, which can happen if there are differences in the uplink and downlink codec parameters. Since checksums are merely binary indicators of corruption, and have no notion of how severe or recoverable a corruption is, this is a core limitation of this technique in the setting of model robustness to bit-level network/file corruptions.

heading: E MULTI-OBJECT TRACKING

text:
We provide full results for our robustness study of multi-object tracking, with multi-object tracking, false positive count, and false negative count.
E.1 ROBUSTNESS STUDY RESULTS
On the MOT task, for all modes of corruption, multi-object tracking accuracy (MOTA) drops (Fig. 9). For random and network corruptions, performance drops to 0, while for contiguous corruptions, performance drops by 160% to´0.453. The negative value is possible due to the form of the MOTA calculation:
MOTA “ 1´ ř t FPt ` FNt ` SWITCHt ř
tOBJt (1)
where FPt is the number of false positive detections at frame/timestep t, FNt is the number of missed/false negative detections at timestep t, SWITCHt is the number of ”identity switches” at time t (i.e. one object is now classified as another object), and OBJt is the total number of objects at time t. The negativity comes from the fact that FPt and SWITCHt are not bounded above. This is likely attributable to the false positive rate being much higher on the contiguous corruption experiments; empirically, the maximum average false positive count in these experiments is 7.41x greater than the maximum average number (8030, contiguous corruption, p “ 0.75) of false positives in any other experiment (1083, packet loss, p “ 0.01). We also comment on the trends in the false positive and negative counts (center, right columns of Fig. 9). On each type of corruption, the number of false positives first increases, then decreases as corruption proportion increases. Similarly, the number of false negatives consistently increases. On average, there are overwhelmingly more false negatives than false positives.
To understand the patterns in false positive and false negative counts, we provide an illustrative visualization for packet loss in Fig. 8. In the ground truth example (Fig. 8a), the model detects three individuals, but in the example with packet loss p “ 0.01 (Fig. 8b), we see multiple object duplication artifacts, resulting in a double detection of the rightmost individual (false positive). This signals a partial non-I-frame corruption, as the motion information fails to erase some parts of the old image, while the new location of the individuals is not updated correctly, resulting in the double images. However, as corruption proportion continues to increase, the video becomes so damaged that the model makes very few detections, hence the continual increase in the number of false negatives. This is shown in Fig. 8c, showing an example at packet loss p “ 0.1, as the video becomes so distorted that two out of three of the individuals detected in the clean image are not detected at all. This signals I-frame destruction, as the image background is entirely grayed-out. The same visual trends hold on contiguous and random corruption.

heading: F ADDITIONAL EXPERIMENTAL DETAILS

text:
F.1 CORRUPTION SIMULATION PARAMETERS
Random file corruptions. We tested the effect of random corruptions on a semi-logarithmic scale, experimenting with p “ r1e´8, 5e´8, 1e´7, 5e´7, 1e´6, 5e´6, 1e´5, 5e´5, 1e´4s. We chose this scale since corruption proportions greater than p “ 1e ´ 4 yielded too few playable examples to get stable estimations of the accuracy and average pixel-space Euclidean distance. To randomly corrupt a video, we convert the video file into a raw bytearray and flip each bit independently with probability p. For BAT variants, we define our cutoff for low levels of corruption as p ď 10´6, and corruption as high otherwise.
Contiguous file corruptions. We tested the effect of contiguous corruptions at p “ r0.01, 0.1, 0.25, 0.5, 0.75, 0.9s. We chose this scale since the effect of corruption proportion on model accuracy and average pixel-space Euclidean distance was more visually apparent on this scale than on a logarithmic scale. To apply contiguous corruption, we convert the video file into a raw bytearray and choose a random starting bit from between 0 and tp1 ´ pq ¨ Lu, where L is the length of the video. For BAT variants, we define our cutoff for low levels of corruption as p ď 0.1, and corruptions as high otherwise.
Packet loss. We tested the effect of packet loss rates p “ r0.0001, 0.001, 0.01, 0.1, 0.2s. This parameter range yielded a wide variety of artifacts and allowed us to observe the accuracy decline of pre-trained video models. We stream videos using ffmpeg using the Real-Time Streaming Protocol (RTSP) over the User Datagram Protocol (UDP), and simulate packet loss by streaming within LossShell in the mahimahi network simulation program (Netravali et al., 2015). Each packet is dropped independently with probability p. For BAT variants, we define our cutoff for low levels of corruption as p ď 0.01, and corruption as high otherwise. Probabilistic perspective on bit-level corruptions. We provide a brief probabilistic perspective on the chance of corruptions making the video unplayable by hitting a critical section of the video file bitstream. For a video of P packets, the probability a video becomes unreadable is 1´p1´MqP ¨p, where M is the fraction of video composed of critical metadata. The probability of a corruption hitting a critical section due to a random corruption is 1 ´ p1´MqB¨p, where B is the number of bits in the video pP ! Bq. For contiguous corruptions, making the simplifying assumption that critical sections of the video are contiguous, the expression is tM{p1´ pqu, which is close to linear outside the neighborhood of p “ 1 for sufficiently smallM . In practice,M varies by video container
format (e.g. AVI, MP4) and with the size of the video file. Replacing M with the proportion of bits in the video that results in distortions when corrupted, we can derive analogous expressions for the probability of a visible corruption.
F.2 MODEL ARCHITECTURE AND CONFIGURATION
Training. For action recognition, follow the fine-tuning setup in Kataoka et al. (2020). We obtained the pre-trained model from the 3D-ResNets-PyTorch GitHub repository (https://github.com/kenshohara/3D-ResNets-PyTorch), using the model trained for 200 epochs on Kinetics-700 (Carreira et al., 2019) and MiT (Monfort et al., 2018) (r3d18 KM 200ep.pth). We fine-tune on split 1 of HMDB51 and UCF101, sampling a random 16-frame segment from each video. If the video is shorter than 16 frames, we loop the video to the required length. All videos are resized to 112 pixel frames. We also apply with a probability 0.5 a random crop across all frames of the segment with crop scales t1, 1
2 1 4 , 1? 2 , 1 2 3 4 , 12u, where a
crop scale of 1 means that the crop has the same width and height, a crop scale of 12 means that the shorter side is 12 the length of the longer side, and likewise for the other crop scales. We flip each clip with probability 0.5 and subtract the mean values of ActivityNet from each channel (RGB: r114.7748, 107.7354, 99.4755s). We train for 50 epochs using stochastic gradient descent with a learning rate 1e´ 3, momentum 0.9, and weight decay of 1e´ 5. We do not use early stopping; we reduce the learning rate by a factor of 10 if validation loss does not improve for 10 epochs, training for a maximum of 50 epochs. We use the same training parameters for adversarial training and corruption-augmented training.
We do not perform further training on multi-object tracking.
Evaluation. For action recognition, we split the clip into contiguous non-overlapping 16-frame segments, matching the length of segments used during training, and evaluate the model on each segment. We also subtract the mean values of ActivityNet from each channel (RGB: r114.7748, 107.7354, 99.4755s) during evaluation for consistency with training. If the final video segment is shorter than 16 frames, we loop it until it reaches the requisite 16 frames. For our prediction, we output the class with the highest probability averaged over all segments.
For multi-object tracking, we simply pass in the corrupted versions of MOT15train to the preset evaluation script for MOT15, which can be found at https://github.com/ifzhang/FairMOT.
Hardware. Training and evaluation was done on one NVIDIA Tesla P100 GPU with 16GB VRAM.
F.3 CALCULATING PIXEL-SPACE EUCLIDEAN DISTANCE
For completeness, we explicitly formulate our calculation of pixel-space Euclidean distance. A video can be interpreted as a four-dimensional tensor, with time, channel (representing colors), height, and width dimensions, which we can notate as C, T,W,H , respectively. In the HMDB51 and UCF101 datasets, the channel dimension has size 3, corresponding to the RGB values of each pixel, which we represent as a float between 0 and 1 inclusive.
Average pixel-space Euclidean distance measures the amount each pixel at a point in time and space changes on average. This is calculated as the pixel-wise L2 norm in the spatial and temporal dimensions averaged over all pixels in the video tensor. As an example, suppose that we have two video tensors, V0 and V1, each with dimensions pC ˆ T ˆW ˆ Hq. Consistent with Section F.2, in our experiments, C “ 3 and W “ H “ 112. The number of frames in a video T varies by video. In the case that durations T0 and T1 for videos V0 and V1, respectively, are different, we take length T 1 “ minpT0, T1q and truncate each video in the time dimension to have dimension pC ˆ T 1ˆW ˆHq. Let D “ V0´ V1, the element-wise difference; then the pixel-space Euclidean distance is
1? 3 ¨ T 1 ¨W ¨H
T ÿ
t“1
W ÿ
w“1
H ÿ h“1 ‖Dtwh‖2, (2)
whereDtwh is the pixel at the location specified by pw, hq at time t. Note the ? 3 in the denominator of the left-most term of Eq. 2. This is a normalization constant that ensures the pixel-space Euclidean distance between two video tensors stays between 0 and 1 inclusive.