# Spatial-Temporal Correlation and Topology Learning
for Person Re-Identification in Videos

Jiawei Liu  Zheng-Jun Zha* Wei Wu  Kecheng Zheng  Qibin Sun
University of Science and Technology of China  China
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Video-based person re-identification aims to match pedestrians from video
sequences across non-overlapping camera views. The key factor for video person
re-identification is to effectively exploit both spatial and temporal clues
from video sequences. In this work, we propose a novel Spatial-Temporal
Correlation and Topology Learning framework (CTL) to pursue discriminative and
robust representation by modeling cross-scale spatial-temporal correlation.
Specifically, CTL utilizes a CNN backbone and a key-points estimator to
extract semantic local features from human body at multiple granularities as
graph nodes. It explores a context-reinforced topology to construct multi-
scale graphs by considering both global contextual information and physical
connections of human body. Moreover, a 3D graph convolution and a cross-scale
graph convolution are designed, which facilitate direct cross-spacetime and
cross-scale information propagation for capturing hierarchical spatial-
temporal dependencies and structural information. By jointly performing the
two convolutions, CTL effectively mines comprehensive clues that are
complementary with appearance information to enhance representational
capacity. Extensive experiments on two video benchmarks have demonstrated the
effectiveness of the proposed method and the state-of-the-art performance.

##  1 Introduction

††footnotetext: * Corresponding author.

Person re-identification (Re-ID) is an important technology to retrieve a
person-of-interest across non-overlapping cameras. It has drawn increasing
attention during the past few years, owing to its broad application in many
realistic scenarios, such as video surveillance [11, 47] and behavior analysis
[43] etc. However, this task remains challenging due to the variations in
illumination, viewpoint and pose, as well as the influence of background
clutter and occlusion.

Figure 1: Three example video sequences on MARS and iLIDS-VID datasets with
partial occlusions, inaccurate detection and viewpoint variation.

Existing person Re-ID approaches are mainly divided into two categories:
image-based methods [39, 33, 41, 25] and video-based methods [36, 26, 22]. The
former exploits static images without temporal information to retrieve
pedestrians. It has achieved impressive advances with the surge of deep
learning technique in recent years [18]. However, image-based person Re-ID
heavily relies on the quality of static images, which are sensitive to noise,
occlusion and viewpoint variation, etc. Different from static images with
limited content, video sequences contain rich spatial-temporal information
across a long span of time, which can provide clean and informative clues
against these problem [22, 8]. Thus, video-based person Re-ID has the
potential to solve the restrictions in image-based person Re-ID.

A typical video-based person Re-ID pipeline extracts and aggregates spatial
and temporal clues from video sequences to generate discriminative
representations. Some preliminary methods [29, 10, 13, 52] extract appearance
features from each frame independently, and aggregate them into video-level
representation by temporal pooling layer or recurrent neural network (RNN). In
presence of partial occlusions, inaccurate detection and viewpoint variation,
the learned features are often corrupted, result in significant performance
degradation. Figure 1 illustrates some video sequences of pedestrians on MARS
[52] and iLIDS-VID [42] datasets with these issues. Recent works attempt to
address them by dividing video frames into horizontal rigid stripes [8, 6, 43]
or utilizing attention mechanism [22, 21, 36, 31, 14] to discover distinctive
partial regions for extracting local appearance features. However, much
background noise is blended in their located partial regions, thus they can
not learn precise aligned part features from videos [53]. Considering that, a
few works [3, 19, 9, 51] employ pose estimation model [30] to adaptively
locate key-points of pedestrians for extracting aligned part features.
However, drastic viewpoint and pose variations as well as occlusion within
videos affect the reliability of pose estimation model. Meanwhile, these
methods only extract local features with fixed semantics from one-granularity
partition, which can not cover all discriminative clues. Further, all the
aforementioned methods only model the temporal relation across different
frames, while neglecting complicated spatial-temporal dependencies and
structural information of different body parts within a frame or across
frames, restricting the capability of pedestrian representation.

In this work, we propose a novel Spatial-Temporal Correlation and Topology
Learning framework (CTL) for video-based person re-identification, which
pursues discriminative and robust representations. CTL extracts local features
at multi-granularity levels to capture diverse discriminative semantics and
alleviate unstable pose estimation results, and learns the potential cross-
scale spatial-temporal dependencies and structure information among body parts
for enhancing feature representation. Specifically, CTL employs a CNN backbone
and a key-points estimator to extract semantic part features from human body
at three granularities as graph nodes. It then explores a context-skeleton
enriched topology to construct multi-scale graphs by considering both global
contextual information and physical connections of human body, which
effectively models the intrinsic spatial-temporal linkages between nodes.
Moreover, a 3D graph convolution and a cross-scale graph convolution are
designed for these multi-scale graphs, which facilitate direct cross-spacetime
and cross-scale information propagation for capturing hierarchical spatial-
temporal dependencies and structural information. By jointly performing the
two convolutions, CTL effectively mines comprehensive and discriminative clues
that are complementary with appearance information to enrich representation.
Extensive experiments on two video datasets, i.e., MARS and iLIDS-VID, have
demonstrated the effectiveness of the proposed approach.

Although graph modeling has been explored in person Re-ID, most of them only
construct a graph on image-level [33, 1, 45, 23] without considering temporal
relation. A few of preliminary works [43, 44, 46] extend graph modeling to
video person Re-ID. However, they neglect the spatial structural information
within each frame [43, 44], or simply utilize factorized spatial and temporal
graph modeling [46], failing to capture complex spatial-temporal relation.
Further, all of them essentially belong to a local method. They utilize pair-
wise feature affinity to measure the linkage between two nodes, while ignoring
the impact of global contextual information from all other nodes, which is
significance for learning reliable and useful graph topology.

The main contributions of this paper are as following: (1) We propose a novel
Spatial-Temporal Correlation and Topology Learning framework (CTL) for person
re-identification in videos. (2) We learn a context-reinforced topology to
construct multi-scale graphs by considering both global contextual information
and physical connections of human body. (3) We develop a 3D graph convolution
and a cross-scale graph convolution to model high-oder spatial-temporal
dependencies and structural information.

##  2 Related Work

Figure 2: The overall architecture of the proposed CTL. It consists of a
backbone network with a key-points estimator, a context block, multiple 3D
graph convolution layers (3D-GCLs), multiple cross-scale graph convolution
layers (CS-GCLs) and a fusion block.

Image-based Person Re-ID. It is extensively explored in the literature.
Existing methods mainly focus on three categories: designing discriminative
hand-crafted descriptors [2], robust distance metric learning [24, 50] or deep
learning technique [27, 39, 18, 17, 16]. For example, Chen et al. [5]
introduced a cascaded feature suppression mechanism that mines all potential
salient features stage-by-stage and integrates these discriminative salience
features with the global feature, producing the final pedestrian feature.

Video-based Person Re-ID. Compared with image-based person Re-ID, video-based
person Re-ID provides richer spatial-temporal clues and is promising for
precise retrieval [37, 15, 48]. Some existing works [29, 10, 13] formulate
video-based person Re-ID as an extension of image-based person Re-ID. They
extract appearance representation from each frame, and aggregates the
representations of all frames by using temporal pooling layer or RNN. For
example, McLaughlin et al. [29] proposed a siamese network, which captures
features from each video, and then employs a recurrent layer and a temporal
pooling layer to abstract video-level feature. In order to learn robust
representation against partial occlusions, inaccurate detection and pose
variation, rigid stripe partition [8, 6, 43] and attention mechanism [22, 21,
36, 31] methods attract more attention recently. For example, Subramaniam et
al. [36] formulated a Co-segmentation Activation Module to enhance common
abstract features and suppress background features by jointly exploring common
features across frames. Moreover, a few works [3, 19, 9] utilize pose
estimation model to adaptively locate key-points of human body and learn
aligned semantic features. For example, Jones et al. [19] proposed a pose-
guided alignment framework, which mimicked the top-down attention of the human
visual cortex to learn aligned features.

Graph Learning. Graphs are typically utilized to model relationships between
nodes. Graph convolutional network (GCN) and its variant models [20] have
achieved great success in many computer vision tasks, e.g., object detection
[35], multi-label image recognition [7] and skeleton-based action recognition
[49, 28]. Similarity, some methods also apply GCN to person Re-ID. Most of
them [33, 1, 45, 23] build the graph models on image-level by considering the
relations among images, which neglect the beneficial temporal information. In
addition, a few of recent works [43, 44, 46] extent GCN to video person Re-ID
by exploring spatial and temporal relation, while they ignore the spatial
structural information of body parts within each frame [43, 44] or only
consider factorized spatial and temporal relation modeling [46]. For example,
Yang et al. [46] proposed a Spatial-Temporal Graph Convolutional Network
(STGCN) which includes two GCN branches. The spatial branch learns spatial
relation of human body, and the temporal branch mines discriminative temporal
relation from adjacent frames.

##  3 Method

To further enhance the capacity of representations, this work explicitly
explores spatial-temporal features across multi-granularity levels. To this
end, we propose a Spatial-Temporal Correlation and Topology Learning
framework, which models high-order spatial-temporal correlation to learn
comprehensive representation. The overall architecture is shown in Figure 2.
It consists of a backbone network with a key-points estimator, a context
block, multiple 3D graph convolution layers (3D-GCL), multiple cross-scale
graph convolution layers (CS-GCL) and a fusion block.

###  3.1 Multi-Scale Feature Extraction

Figure 3: Three scales of body partition. In $s_{1}$, we adopt 17 key-points,
In $s_{2}$ and $s_{3}$, we adopt 10 and 5 parts of body, respectively.

Given a video sequence, we denote it as $\\{\boldsymbol{I}_{t}\\}_{t=1}^{T}$,
where $T$ is the sequence length. The backbone network takes each frame as
input to extract the initial feature map
$\boldsymbol{F}=\\{\boldsymbol{F}_{t}|\boldsymbol{F}_{t}\in\mathbb{R}^{H\times
W\times C}\\}_{t=1}^{T}$, where $H$, $W$ and $C$ denote the height, width and
channel size of the feature maps, respectively. The backbone network is based
on ResNet-50 model [12]. As part-based representations have shown
effectiveness for person Re-ID [39], we adopt a key-points estimator [38] to
adaptively locate the key-points of human body, and extract aligned part
features from these key-points against partial occlusions, misalignment and
viewpoint variation. Although, key-points estimation models have obtained high
accuracy, they remain suffering from unreliable performance under complex
surveillance scenes, leading to inaccurate key-points location and their
confidence. Thus, exploring multi-scale part features with their spatial-
temporal correlation is particularly important, which can alleviate unreliable
key-point estimation results and capture diverse discriminative semantics.

Based on human nature, we divide human body at three granularities: the key-
point scale ($s_{1}$), the low-level-part scale ($s_{2}$) and the high-level-
part scale ($s_{3}$), as show in Figure 3. We merge spatially nearby key-
points to each part in coarser scales based on human prior. The heat maps
$\boldsymbol{m}$ of key-points are generated through the key-point estimator,
which are then normalized with a softmax function. The group of semantic local
feature $\boldsymbol{V}_{s1}\in\mathbb{R}^{T\times N_{s_{1}}\times C}$ for the
granularity $s_{1}$ and the global feature
$\boldsymbol{V}_{g}\in\mathbb{R}^{T\times C}$ are computed as following:

$\begin{split}\boldsymbol{V}_{s1}&=\\{\boldsymbol{v}_{s1}\\}=g_{GAP}(\boldsymbol{F}_{t}\otimes\boldsymbol{m}_{s_{1}}^{t})\\\
\boldsymbol{V}_{g}&=g_{GAP}(\boldsymbol{F})\end{split}$ (1)

where $\otimes$ and $g_{GAP}$ refer to outer product and global average
pooling operations, respectively. $N_{s}$ is the number of body parts (17, 10
and 5 parts for $s_{1}$, $s_{2}$, $s_{3}$, respectively). The part features
$\boldsymbol{V}_{s2}$ and $\boldsymbol{V}_{s3}$ for the low-level-part and
high-level-part scales are computed by performing average pooling operation on
the features $\boldsymbol{V}_{s1}$ of the key-points within each body part.

###  3.2 Context-Reinforced Topology Graph

In order to excavate spatial-temporal information from video frames, we employ
advanced GCN to model hierarchical spatial-temporal dependencies and
structural information. Let
$\mathcal{G}=\\{\mathcal{G}_{s}\\}_{s\in\\{s_{1},s_{2},s_{3}\\}}$ be a set of
constructed multi-scale graphs of one video frame, where each graph
corresponds to a specific granularity level $s$. Specifically,
$\mathcal{G}_{s}(\mathcal{V}_{s},\mathcal{E}_{s})$ includes $N_{s}$ nodes
$\boldsymbol{v}_{i}\in\mathcal{V}_{s}$ and a set of edges
$\boldsymbol{e}_{ij}=(\boldsymbol{v}_{i},\boldsymbol{v}_{j})\in\mathcal{E}_{s}$.
Each part of body within one video frame is viewed as a graph node and the
edges represent the relationship between these body parts. The input node
feature of frame $t$ is denoted as
$\boldsymbol{X}_{s}^{t}=\boldsymbol{V}_{s}^{t}\in\mathbb{R}^{N_{s}\times C}$.
$\boldsymbol{A}_{s}\in\mathbb{R}^{N_{s}\times N_{s}}$ is the corresponding
frame-level adjacency matrix, in which each element represents the linkage of
two arbitrary nodes. The topology of the graph is actually decided by
$\boldsymbol{A}_{s}$. Existing GCN-based Re-ID methods predict the
relationship between two nodes independently by calculating pair-wise feature
affinity, which ignore the impact of all other contextual nodes and only
consider undirected dependency, restricting the capacity and expressiveness of
the graph model.

Figure 4: Detailed network structure of (a) the context block; (b) the
advanced context block.

Considering that, we explore a context-reinforced topology to construct graph,
which simultaneously encodes contextual information along the node, temporal
and feature dimensions, as well as physical structural information of human
body. The context-reinforced adjacency matrix $\boldsymbol{A}_{s}$ consists of
three components:

$\begin{split}\boldsymbol{A}_{s}=\boldsymbol{A}_{s}^{p}+\boldsymbol{A}_{s}^{m}+\boldsymbol{A}_{s}^{c}\end{split}$
(2)

where $\boldsymbol{A}_{s}^{p}\in\\{0,1\\}^{N_{s}\times N_{s}}$ denotes the
physical connections of human body with rich structural information, which is
fixed during training. $\boldsymbol{A}_{s}^{m}$ denotes a mask adjacency
matrix, which is utilized as the attention on the physical structure, inspired
by [34]. $\boldsymbol{A}_{s}^{m}$ improves the flexibility and generality of
static global graph structure $\boldsymbol{A}_{s}^{p}$, and is initialized
with zeros and optimized together with other parameters during training.
$\boldsymbol{A}_{s}^{c}$ is a data-dependent individual adjacency matrix,
which incorporates the global contextual information of all nodes and learns a
unique dynamic topology graph for each sample. $\boldsymbol{A}_{s}^{c}$ is
learned by a context block, as shown in Figure 4(a). Given the node features
$\\{\boldsymbol{X}_{s}^{t}\\}_{t=1}^{T}\in\mathbb{R}^{T\times N_{s}\times C}$,
the context block firstly squeezes the feature and temporal dimensions of each
node by two convolution layers with $1\times 1$ kernel. Then, it utilizes an
addition $1\times 1$ convolution layer to transfer the $N_{s}$-dimension
feature vector into the $N_{s}\times N_{s}$ adjacency matrix
$\boldsymbol{A}_{s}^{c}$. Afterwards, $L2$ normalization operation is applied
to each row of $\boldsymbol{A}_{s}^{c}$ for stable optimization. The context
block adequately considers the influence of all other nodes when measuring the
relationship between two arbitrary nodes.

###  3.3 3D Graph Convolutional Layer

Figure 5: (a) Cross-spacetime information propagation by 3D graph convolution;
(b) Cross-scale information propagation by cross-scale graph convolution.

After obtaining the frame-level graphs for all frames, we design a 3D graph
convolution to effectively propagate messages and update node features. 3D-GCL
allows direct cross-spacetime information propagation for capturing complex
spatial-temporal dependencies and structural information in a spatial-temporal
graph, as shown in Figure 5(a). Concretely, 3D-GCL first uses a temporal
sliding window with size of $\tau$ over the sequence of frame-level graphs. At
each sliding step, a spatial-temporal subgraph
$\mathcal{G}_{s}^{(\tau)}=(\mathcal{V}^{(\tau)}_{s},\mathcal{E}^{(\tau)}_{s})$,
in which
$\mathcal{V}^{(\tau)}_{s}=\mathcal{V}^{1}_{s}\cup...\cup\mathcal{V}^{\tau}_{s}$
denote the union set of all nodes across $\tau$ video frames in this window.
And the edge set $\mathcal{E}^{(\tau)}_{s}$ is represented by a block
adjacency matrix $\boldsymbol{A}_{s}^{(\tau)}$. It is computed as following:

$\begin{split}\boldsymbol{A}_{s}^{(\tau)}&=\boldsymbol{A}_{s}^{(\tau),p}+\boldsymbol{A}_{s}^{(\tau),m}+\boldsymbol{A}_{s}^{(\tau),c}\\\
&=\begin{bmatrix}[\boldsymbol{A}_{s}^{(\tau)}]_{1,1}&\cdots&[\boldsymbol{A}_{s}^{(\tau)}]_{1,\tau}\\\
\vdots&\ddots&\vdots\\\ [\boldsymbol{A}_{s}^{(\tau)}]_{\tau,1}&\cdots\
&[\boldsymbol{A}_{s}^{(\tau)}]_{\tau,\tau}\\\ \end{bmatrix}\in\mathbb{R}^{\tau
N_{s}\times\tau N_{s}}\end{split}$ (3)

where each submatrix $[\boldsymbol{A}_{s}^{(\tau)}]_{i,j}$ denotes the graph
nodes of $\mathcal{V}^{i}_{s}$ are connected to themselves and their temporal
neighboring nodes at frame $j$, by expanding the frame-level spatial
connection (corresponding to $[\boldsymbol{A}_{s}^{(\tau)}]_{i,i}$) to the
temporal domain. $\boldsymbol{A}_{s}^{(\tau)}$ is still composed of three
parts. The block adjacency matrix $\boldsymbol{A}_{s}^{(\tau),p}$ is computed
by tiling the static $\boldsymbol{A}_{s}^{p}$ in each block.
$\boldsymbol{A}_{s}^{(\tau),m}$ is obtained as the same way.
$\boldsymbol{A}_{s}^{(\tau),c}$ is learned by the advanced context block in
Figure 4(b). Simultaneously,
$\boldsymbol{X}_{s}^{(\tau)}\in\mathbb{R}^{T\times\tau N_{s}\times C}$ is
obtained by employing the sliding temporal window over
$\boldsymbol{X}^{0}=\\{\boldsymbol{X}_{s}^{t}\\}_{t=1}^{T}\in\mathbb{R}^{T\times
N_{s}\times C}$ with zero padding operation to build $T$ windows, which is the
input of 3D-GCL.

The 3D graph convolution for the $t$-th temporal window at $l$-th iteration is
formulated as following:

$\begin{split}[\boldsymbol{X}_{s}^{(\tau),l+1}]_{t}=\sigma(\tilde{\boldsymbol{D}}^{-\frac{1}{2}}\boldsymbol{\hat{A}}_{s,t}^{(\tau)}\tilde{\boldsymbol{D}}^{-\frac{1}{2}}[\boldsymbol{X}_{s}^{(\tau),l}]_{t}\boldsymbol{W}^{l})\end{split}$
(4)

where
$\small(\tilde{\boldsymbol{D}})_{i,i}=\sum_{j}(\boldsymbol{\hat{A}}_{s,t}^{(\tau)})_{i,j}$
denotes diagonal node degree matrix [20],
$\small\boldsymbol{\hat{A}}_{s,t}^{(\tau)}=\boldsymbol{A}_{s,t}^{(\tau)}+I_{\tau
N_{s}}$ denotes the self-loop adjacency matrix. $\boldsymbol{I}_{\tau N_{s}}$
denotes an identity matrix. $\boldsymbol{W}^{l}$ refers to the learnable
parameter and $\sigma$ represents a non-linear activation function. After each
3D-GCL, a convolution layer followed with a batch normalization (BN) layer and
a rectified linear units (ReLU) layer is employed to collapse the window
dimension $\tau$ and output the updated node feature
$\boldsymbol{X}^{l+1}\in\mathbb{R}^{T\times N_{s}\times C}$ . In addition,
shortcut connection
$\boldsymbol{X}^{l+1}=\boldsymbol{X}^{l+1}+\boldsymbol{X}^{l},1\leq l\leq L-1$
is adopted for effective and stable optimizing. The refined part features at
three granularities $\boldsymbol{\hat{X}}_{s_{1}}$,
$\boldsymbol{\hat{X}}_{s_{2}}$, $\boldsymbol{\hat{X}}_{s_{3}}$ are finally
obtained by performing multiple 3D-GCLs.

###  3.4 Cross-Scale Graph Convolutional Layer

Figure 6: The inference of the cross-scale adjacent matrix.

Multi-scale part features obtained from different partitions contain diverse
discriminative semantics. To enable information diffusion across scales and
learn comprehensive representation, we propose a cross-scale graph
convolution, which propagates the informative clues of part features from one
scale to another, as shown in Figure 5(b). The cross-scale topology graph is a
directed graph that corresponds the nodes in one scale graph to the nodes in
another scale graph. For simplicity, we elaborate a CS-GCL associated from
$s_{2}$ to $s_{3}$. The adjacent matrix
$\boldsymbol{A}_{s_{2},s_{3}}\in\mathbb{R}^{N_{s_{3}}\times N_{s_{2}}}$ of the
cross-scale graph predicts the cross-scale relationship. As shown in Figure 6,
the dependency $(\boldsymbol{A}_{s_{2},s_{3}})_{i,m}$ between $i$-th part in
$s_{2}$ and $m$-th part in $s_{3}$ is computed as following:

$\begin{split}&\boldsymbol{p}_{i,s_{2}}=\sum_{j=1}^{N_{s_{2}}}h_{s_{2}}([{\phi}(\boldsymbol{x}_{i,s_{2}}),\varphi(\boldsymbol{x}_{j,s_{2}}-\boldsymbol{x}_{i,s_{2}})])\\\
&\boldsymbol{r}_{i,s_{2}}=f_{s_{2}}([\boldsymbol{x}_{i,s_{2}},\boldsymbol{p}_{i,s_{2}}])\\\
&\boldsymbol{p}_{m,s_{3}}=\sum_{j=1}^{N_{s_{3}}}h_{s_{3}}([{\phi}(\boldsymbol{x}_{m,s_{3}}),\varphi(\boldsymbol{x}_{j,s_{3}}-\boldsymbol{x}_{m,s_{3}})])\\\
&\boldsymbol{r}_{m,s_{3}}=f_{s_{3}}([\boldsymbol{x}_{m,s_{3}},\boldsymbol{p}_{m,s_{3}}])\\\
&(\boldsymbol{A}_{s_{2},s_{3}})_{i,m}=softmax(\boldsymbol{r}_{m,s_{3}}^{\top}\boldsymbol{r}_{i,s_{2}})\end{split}$
(5)

where $\boldsymbol{x}_{i,s_{2}}\in\mathbb{R}^{C}$ denotes the $i$-th component
of $\boldsymbol{\hat{X}}_{s_{2}}$ at one specific frame. $h_{s_{2}}$,
$f_{s_{2}}$, $\phi$, $\varphi$ are the embedding functions implemented by a
full connected layer with a BN layer and a ReLU layer.
$\boldsymbol{p}_{i,s_{2}}$ and $\boldsymbol{p}_{m,s_{3}}$ aggregate the global
relation information of all other part features to the $i$-th and the $m$-th
components at the two scales. $\boldsymbol{r}_{i,s_{2}}$ and
$\boldsymbol{r}_{m,s_{3}}$ are the augmented global relation features, which
are then used to calculate the dependency
$(\boldsymbol{A}_{s_{2},s_{3}})_{i,m}$ by inner product operation and softmax
function. Thus, $\boldsymbol{A}_{s_{2},s_{3}}$ constructs the influence from
the body in $s_{2}$ to each part in $s_{3}$.

Given the part feature $\boldsymbol{\hat{X}}_{s_{2}}$ at scale $s_{2}$, the
cross-scale convolution for frame $t$ is formulated as following:

$\begin{split}[\boldsymbol{\hat{X}}_{s_{23}}]_{t}=\sigma(\boldsymbol{A}_{s_{2},s_{3}}^{t}[\boldsymbol{\hat{X}}_{s_{2}}]_{t}\boldsymbol{W}_{s_{23}})\end{split}$
(6)

where $\boldsymbol{W}_{s_{23}}$ denotes the parameter matrix, and
$\boldsymbol{\hat{X}}_{s_{23}}$ is the transformed part feature. Such feature
adaptively absorbs informative clues from the corresponding parts of body in
$s_{2}$. Analogously, we also utilize another CS-GCL to transfer the part
feature $\boldsymbol{\hat{X}}_{s_{1}}$ from $s_{1}$ to $s_{3}$, and produce
the transformed part feature $\boldsymbol{\hat{X}}_{s_{13}}$. Finally, the
comprehensive part feature $\boldsymbol{V}_{p}$ with three-granularity
information is obtained as following:

$\begin{split}\boldsymbol{V}_{p}=\boldsymbol{\hat{X}}_{s_{3}}+\alpha(\boldsymbol{\hat{X}}_{s_{13}}+\boldsymbol{\hat{X}}_{s_{23}})\end{split}$
(7)

where $\alpha$ denotes the balance weight.

###  3.5 Model Optimizing

After obtaining the features $\boldsymbol{V}_{p}\in\mathbb{R}^{T\times
N_{s_{3}}\times C}$ and $\boldsymbol{V}_{g}$, they are fed into a fusion block
to further incorporate the global and local information, and are finally
optimized by loss function. The fusion block consists of three branches. The
first branch employs a temporal average pooling layer ($g_{TAP}$) for
$\boldsymbol{V}_{g}$ to generate the feature vector
$\small\boldsymbol{V}_{f}^{g}=g_{TAP}(\boldsymbol{V}_{g})$. The second branch
utilizes the function $\small
g_{TAP}((\sum\limits_{n=1}^{N_{s_{3}}}[\boldsymbol{V}_{p}]_{:,n,:})+\boldsymbol{V}_{g})$
to generate the feature vector $\boldsymbol{V}_{f}^{a}$. The third branch
utilizes the function $\small
g_{TAP}([g_{c}([\boldsymbol{V}_{p}]_{:,1,:}),...,g_{c}([\boldsymbol{V}_{p}]_{:,N_{s_{3}},:})]+\boldsymbol{V}_{g})$
to produce the feature vector $\boldsymbol{V}_{f}^{c}$, where $g_{c}$ denotes
a $1\times 1$ convolution layer for reducing the dimension. The third branch
implicitly promotes the channel-wise semantic alignment between the global and
local features, which drives different channel of the global feature to focus
on different body parts for improving the performance. Identification loss and
triplet loss are the widely-used losses for person re-identification, we adopt
triplet loss with hard mining strategy [46] and identification loss with label
smoothing regularization [40] to optimize these three features
$\boldsymbol{V}_{f}^{g}$, $\boldsymbol{V}_{f}^{a}$ and
$\boldsymbol{V}_{f}^{c}$, respectively. The two losses are denoted as
$\mathcal{L}_{tri}$ and $\mathcal{L}_{ide}$ respectively. Moreover, a
diversity regularization loss is proposed to encourage the diversity of the
local features and increase the discrimination of the final video
representation. This loss is defined as following:

$\begin{split}\mathcal{L}_{div}=\lVert\boldsymbol{V}_{p}\boldsymbol{V}_{p}^{T}-\boldsymbol{I}\rVert^{2}_{F}\end{split}$
(8)

where $\lVert\cdot\lVert_{F}$ denotes Frobenius norm. $\boldsymbol{V}_{p}$ is
applied with temporal average pooling and $L2$ normalization in advance for
this loss. Therefore, the total loss $\mathcal{L}$ for CTL is the combination
of the three losses:

$\begin{split}\mathcal{L}=\lambda_{1}\cdot\mathcal{L}_{tri}+\lambda_{2}\cdot\mathcal{L}_{ide}+\lambda_{3}\cdot\mathcal{L}_{div}\end{split}$
(9)

where $\lambda_{1-3}$ are the balance weights of the three loss terms.

##  4 Experiments

###  4.1 Experimental Settings

Datasets. MARS dataset [52] is one of the existing largest video benchmark,
consisting of 1,261 identities and 20,715 video sequences. The training set
contains 625 identities and the testing set contains 636 identities. iLIDS-VID
dataset [42] is a small-scale benchmark. It consists of 600 video sequences of
300 different identities, each of which has two sequences captured by two non-
overlapping cameras. It is randomly split into a training set with 150
identities and a testing set with the remaining 150 identities.

Evaluation Metrics. We adopt the standard metrics, i.e., Cumulative Matching
Characteristic (CMC) curves and mean average precision (mAP), to evaluate the
performance of different person Re-ID algorithms.

Implementation Details. We randomly sample $T=6$ frames from a variable-length
sequence as a input clip. Each mini-batch has 8 identities and 4 video clips
for each identity. We resize all video frames to $256\times 128$ pixels, which
are normalized with $1.0/256$. We then apply image-level data augmentation to
each video clip, including random horizontal flipping and random erasing
probability. ResNet-50 [12] pre-trained on ImageNet is used as the backbone
network. The last stride of ResNet-50 is set to 1. The Adam optimizer is
adopted with the initial learning rate $lr$ of $3e^{-4}$ and the weight decay
of $5e^{-4}$. We train our model for 240 epochs in total. The learning rate
$lr$ is decayed by 10 after every 60 epochs. $H$, $W$ and $C$ are 16, 8 and
2048, respectively. The numbers of 3D-GCLs is set to $L=2$. $\alpha$ in Eq. 7
is set to $0.3$, and $\lambda_{1-3}$ in Eq. 9 are all set to 1. During
inference, $\boldsymbol{V}_{f}^{a}$ is used as the final video representation
for calculating the similar scores.

###  4.2 Comparison to State-of-the-Arts

Table 1: Performance comparison to the state-of-the-art methods on MARS
dataset.

Method | Rank-1 | Rank-5 | Rank-20 | mAP
---|---|---|---|---
CNN+XQDA [52] | 68.3 | 82.6 | 89.4 | 49.3
TriNet [13] | 79.8 | 91.36 | - | 67.7
STAL[3] | 82.2 | 92.8 | 98.0 | 73.5
STAN [21] | 82.3 | - | - | 65.8
COSAM[37] | 84.9 | 95.5 | 97.9 | 79.9
VRSTC [15] | 88.5 | 96.5 | 97.4 | 82.3
RGSAT [22] | 89.4 | 96.9 | 98.3 | 84.0
AGRL [43] | 89.8 | 96.1 | 97.6 | 81.1
TCLNet [14] | 89.8 | - | - | 85.1
STGCN [46] | 90.0 | 96.4 | 98.3 | 83.7
MGH [44] | 90.0 | 96.7 | 98.5 | 85.8
AP3D[11] | 90.1 | - | - | 85.1
AFA [4] | 90.2 | 96.6 | - | 82.9
CTL | 91.4 | 96.8 | 98.5 | 86.7

Table 2: Performance comparison to the state-of-the-art methods on iLIDS-VID
dataset.

Method | Rank-1 | Rank-5 | Rank-20
---|---|---|---
CNN+XQDA [52] | 53.0 | 81.4 | 95.1
RCNet [29] | 58 | 84.0 | 96.0
COSAM[37] | 79.6 | 95.3 | -
STAN [21] | 80.2 | - | -
STAL[3] | 82.8 | 95.3 | 98.8
VRSTC [15] | 83.4 | 95.5 | 99.5
AGRL [43] | 83.7 | 95.4 | 99.5
MGH [44] | 85.6 | 97.1 | 99.5
RGSAT [22] | 86.0 | 98.0 | 99.4
TCLNet [14] | 86.6 | - | -
AP3D[11] | 86.7 | - | -
FGRA [6] | 88.0 | 96.7 | 99.3
AFA [4] | 88.5 | 96.8 | 99.7
CTL | 89.7 | 97.0 | 100.0

Results on MARS. In Table 1, we compare the proposed method with 13 state-of-
the-art methods on MARS dataset. The first two methods belong to the expansion
of image-based person Re-ID. We can observe that CTL achieves 91.4% Rank-$1$
accuracy and 86.7% mAP, surpassing the current state-of-the-art methods by a
large margin. It improves the 2nd best method AFA [4] by 1.2% Rank-$1$
accuracy and MGH [44] by 0.9% mAP, respectively. The comparison clearly
demonstrates the effectiveness and superiority of CTL for exploring
hierarchical spatial-temporal dependencies and structural information among
body parts from videos. Note that, compared with other graph-based methods,
including AGRL[43], STGCN [46] and MGH [44], CTL obtains better results in
terms of Rank-$1$ accuracy and mAP. The main reason for the boosting is two
aspects: 1) using context-reinforced topology to construct graph instead of
pair-wise feature affinity; 2) the advantage of modeling high-order spatial-
temporal correlation by 3D-GCL and CS-GCL.

Results on iLIDS-VID. Table 2 reports the performance of our approach with 13
state-of-the-art methods on iLIDS-VID dataset. CNN+XQDA [52] and RCNet [29]
are the straightforward expansion method of image-based person Re-ID. It can
be seen that CTL obtains the best performance of 89.7% Rank-$1$ accuracy and
100.0% Rank-$20$ accuracy. It beats AFA [4] on Rank-$1$ and Rank-$20$ accuracy
by 1.2% and by 0.3%, respectively. The comparison demonstrates the advantage
of spatial-temporal feature learning by CTL, and the applicability of CTL for
a small-scale dataset.

###  4.3 Ablation Studies

Effectiveness of Components. Table 3 reports the experimental results of the
ablation studies for CTL. Basel denotes using the backbone network with the
key-points estimator to learn the global and multi-scale part features.
Basel+ContRe denotes using the context-reinforced topology to structure multi-
scale frame-wise graphs, and applying original GCN to learn the refined multi-
scale part features and global feature. Basel+ContRe+3D refers to CTL using
addition operation to replace CS-GCL for learning the fused part feature and
the global feature. Basel+ContRe+3D+CS refers to the whole framework of CTL.
Compared with Basel, Basel+ContRe boosts Rank-$1$ accuracy and mAP by 0.8% and
2.7%. This indicts that the effectiveness of the context-reinforced topology
to capture the intrinsic relationship among body parts for enhancing feature
representation. Moreover, Basel+ContRe+3D improves Basel+ContRe by 1.3% Rank-1
accuracy and 0.6% mAP, which verifies the effectiveness of 3D-GCL for allowing
direct cross-spacetime information propagation to enrich part features. By
utilizing the cross-scale graph convolutional layer, Basel+ContRe+3D+CS
achieves the best performance. This demonstrates that CS-GCL effectively
capture diverse visual semantic across multiple scales to integrate them into
a comprehensive representation.

Analysis of Context-Reinforced Topology. The results in Table 4 show the
influence of different components of the context-reinforced graph topology.
CTL-$\boldsymbol{A}_{s}^{p}$,
CTL-$\boldsymbol{A}_{s}^{p}\boldsymbol{A}_{s}^{m}$,
CTL-$\boldsymbol{A}_{s}^{p}\boldsymbol{A}_{s}^{m}\boldsymbol{A}_{s}^{c}$,
denote using $\boldsymbol{A}_{s}^{m}$,
$\boldsymbol{A}_{s}^{p}+\boldsymbol{A}_{s}^{m}$ and
$\boldsymbol{A}_{s}^{p}+\boldsymbol{A}_{s}^{m}+\boldsymbol{A}_{s}^{c}$ to
measure the dependency between two nodes, respectively. By comparing
CTL-$\boldsymbol{A}_{s}^{p}$ and
CTL-$\boldsymbol{A}_{s}^{p}\boldsymbol{A}_{s}^{m}$, we can conclude that
$\boldsymbol{A}_{s}^{m}$ improves the flexibility of graph topology and
captures more complex spatial-temporal correlation.
CTL-$\boldsymbol{A}_{s}^{p}\boldsymbol{A}_{s}^{m}\boldsymbol{A}_{s}^{c}$
achieves remarkable performance improvement as compared to
CTL-$\boldsymbol{A}_{s}^{p}\boldsymbol{A}_{s}^{m}$, which means
$\boldsymbol{A}_{s}^{c}$ is complementary to physical topology, and mines
potential connections that are informative by considering global contextual
information of all nodes.

Analysis of 3D-GCL. We conduct the experiments to analyze the influence of the
number layer $L$ and window size $\tau$ for 3D-GCL. In Figure 7(a), we can
observe that the best Rank-1 accuracy of 91.4% and mAP of 86.7% are obtained
when $L=2$. This implies that one-layer 3D-GCL has insufficient capability for
capturing complex spatial-temporal information, whilst three-layer 3D-GCLs
bring more training parameters, result in hard optimizing and performance
degradation. Thus, $L$ is set to $2$. In Figure 7(b), $\tau=3$ obtains
superior performance as compared to $\tau=1$ due to utilizing the temporal
complementary information from local temporal neighborhood nodes, but the gain
diminishes when $\tau=5$ as the discriminative clues in aggregated features
are counteracted due to the over-sized local temporal neighborhood nodes.
Thus, $\tau$ is set to $3$.

Table 3: Evaluation of the effectiveness of each component of CTL on MARS
dataset.

Model | Rank-1 | Rank-5 | Rank-20 | mAP
---|---|---|---|---
Basel | 88.6 | 96.1 | 97.9 | 82.7
Basel+ContRe | 89.4 | 95.6 | 98.2 | 85.4
Basel+ContRe+3D | 90.7 | 96.4 | 98.4 | 86.0
Basel+ContRe+3D+CS | 91.4 | 96.8 | 98.5 | 86.7

Table 4: Evaluation of the influence of different components of the context-
reinforced topology on MARS dataset.

Model | Rank-1 | Rank-5 | Rank-20 | mAP
---|---|---|---|---
CTL-$\boldsymbol{A}_{s}^{p}$ | 90.4 | 96.4 | 98.5 | 86.1
CTL-$\boldsymbol{A}_{s}^{p}\boldsymbol{A}_{s}^{m}$ | 90.9 | 96.3 | 98.6 | 86.3
CTL-$\boldsymbol{A}_{s}^{p}\boldsymbol{A}_{s}^{m}\boldsymbol{A}_{s}^{c}$ | 91.4 | 96.8 | 98.5 | 86.7

Table 5: Evaluation of the influence of CS-GCL with different settings on MARS
dataset.

Model | Rank-1 | Rank-5 | Rank-20 | mAP
---|---|---|---|---
CS-GCL($\boldsymbol{M}=1$) | 91.4 | 96.8 | 98.5 | 86.7
CS-GCL($\boldsymbol{M}=2$) | 90.1 | 96.5 | 98.3 | 85.5
CS-GCL-$\boldsymbol{s}_{3}$ | 90.4 | 96.4 | 98.4 | 85.9
CS-GCL-$\boldsymbol{s}_{3}\boldsymbol{s}_{1}$ | 90.7 | 96.6 | 98.4 | 85.8
CS-GCL-$\boldsymbol{s}_{3}\boldsymbol{s}_{1}\boldsymbol{s}_{2}$ | 91.4 | 96.8 | 98.5 | 86.7

Figure 7: Analysis on the influence of different hyperparameters for 3D-GCL,
(a) the number layer $L$; (b) windows size $\tau$. Figure 8: (a) Visualization
of the learned feature maps; (b) Visualization of some retrieval results by
CTL.

Analysis of CS-GCL. In Table 5, we investigate the influence of the number $M$
of CS-GCLs for transferring each granularity-level part features from one
scale to another one, and analyze the performance of fusing different scales
of part features. We can observe that the two-layer CS-GCLs (denotes using
another CS-GCL after the first 3D-GCL) obtain performance degradation over
one-layer CS-GCL. It indicates that two-layer CS-GCLs tend to fuse much
redundant information, which weaken the representational capability. Moreover,
CS-GCL-$\boldsymbol{s}_{3}\boldsymbol{s}_{1}\boldsymbol{s}_{2}$ achieves
better results over CS-GCL-$\boldsymbol{s}_{3}\boldsymbol{s}_{1}$ and CS-
GCL-$\boldsymbol{s}_{3}$ by combing more granularity-level part features. The
improvement verifies CS-GCL can effectively mine the distinct patterns from
each scale and enhance feature representation by fusing the complementary
information among them.

Visualization Results. We visualize the learned feature respond maps of one
video sequence by Grad-CAM [32]. In Figure 8(a), we can observe that the
feature maps from different video frames of a pedestrian have stronger
response on the same discriminative regions, which verifies that CTL can
extract aligned discriminative clues by modeling cross-scale spatial-temporal
correlation. Figure 8(b) shows the retrieval results of two pedestrians by
CTL. We can observe that Rank-$5$ retrieval results by CTL are all matching.
This indicates CTL effectively alleviates the problem of misalignment and
occlusion, viewpoint variation, etc.

##  5 Conclusion

In this work, we propose a novel Spatial-Temporal Correlation and Topology
Learning framework (CTL) for video-based person re-identification to learn
discriminative and robust representation. CTL utilizes a key-points estimator
to extract multi-scale part features as graph nodes. A context-reinforced
topology is then explored to structure multi-scale graphs by considering
global contextual information and physical connection of human body. Moreover,
a 3D graph convolution and a cross-scale graph convolution are designed, and
performed on the multi-scale graphs. They facilitate direct cross-spacetime
and cross-scale information propagation among graph nodes, and model complex
relation and structural information to refine pedestrian representation.
Extensive experiments on two video datasets validate the effectiveness of the
proposed method.

## Acknowledgment

This work was supported by the National Key R&D Program of China under Grand
2020AAA0105702, National Natural Science Foundation of China (NSFC) under
Grants U19B2038 and U19B2023, and China Postdoctoral Science Foundation Funded
Project under Grant 2020M671898.

## References

  * [1] Dapeng Chen, Dan Xu, Hongsheng Li, Nicu Sebe, and Xiaogang Wang.  Group consistent similarity learning via deep crf for person re-identification.  In CVPR, pages 8649–8658, 2018.
  * [2] Dapeng Chen, Zejian Yuan, Badong Chen, and Nanning Zheng.  Similarity learning with spatial constraints for person re-identification.  In CVPR, pages 1268–1277, 2016.
  * [3] Guangyi Chen, Jiwen Lu, Ming Yang, and Jie Zhou.  Spatial-temporal attention-aware learning for video-based person re-identification.  IEEE Transactions on Image Processing, 28(9):4192–4205, 2019.
  * [4] Guangyi Chen, Yongming Rao, Jiwen Lu, and Jie Zhou.  Temporal coherence or temporal motion: Which is more critical for video-based person re-identification?  In ECCV, pages 660–676, 2020.
  * [5] Xuesong Chen, Canmiao Fu, Yong Zhao, Feng Zheng, Jingkuan Song, Rongrong Ji, and Yi Yang.  Salience-guided cascaded suppression network for person re-identification.  In CVPR, pages 3300–3310, 2020.
  * [6] Zengqun Chen, Zhiheng Zhou, Junchu Huang, Pengyu Zhang, and Bo Li.  Frame-guided region-aligned representation for video person re-identification.  In AAAI, pages 10591–10598, 2020.
  * [7] Zhao-Min Chen, Xiu-Shen Wei, Peng Wang, and Yanwen Guo.  Multi-label image recognition with graph convolutional networks.  In CVPR, pages 5177–5186, 2019.
  * [8] Yang Fu, Xiaoyang Wang, Yunchao Wei, and Thomas Huang.  Sta: Spatial-temporal attention for large-scale video-based person re-identification.  In AAAI, volume 33, pages 8287–8294, 2019.
  * [9] Changxin Gao, Yang Chen, Jin-Gang Yu, and Nong Sang.  Pose-guided spatiotemporal alignment for video-based person re-identification.  Information Sciences, 527:176–190, 2020.
  * [10] Jiyang Gao and Ram Nevatia.  Revisiting temporal modeling for video-based person reid.  In BMVC, pages 1320–1329, 2018.
  * [11] Xinqian Gu, Hong Chang, Bingpeng Ma, Hongkai Zhang, and Xilin Chen.  Appearance-preserving 3d convolution for video-based person re-identification.  In ECCV, 2020.
  * [12] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In CVPR, pages 770–778, 2016.
  * [13] Alexander Hermans, Lucas Beyer, and Bastian Leibe.  In defense of the triplet loss for person re-identification.  arXiv preprint arXiv:1703.07737, 2017.
  * [14] Ruibing Hou, Hong Chang, Bingpeng Ma, Shiguang Shan, and Xilin Chen.  Temporal complementary learning for video person re-identification.  In ECCV, pages 600–616, 2020.
  * [15] Ruibing Hou, Bingpeng Ma, Hong Chang, Xinqian Gu, Shiguang Shan, and Xilin Chen.  Vrstc: Occlusion-free video person re-identification.  In CVPR, pages 7183–7192, 2019.
  * [16] Yukun Huang, Zheng-Jun Zha, Xueyang Fu, Richang Hong, and Liang Li.  Real-world person re-identification via degradation invariance learning.  In CVPR, pages 14084–14094, 2020.
  * [17] Yukun Huang, Zheng-Jun Zha, Xueyang Fu, and Wei Zhang.  Illumination-invariant person re-identification.  In ACM MM, pages 365–373, 2019.
  * [18] Xinyang Jiang, Yifei Gong, Xiaowei Guo, Qize Yang, Feiyue Huang, Wei-Shi Zheng, Feng Zheng, and Xing Sun.  Rethinking temporal fusion for video-based person re-identification on semantic and time aspect.  In AAAI, pages 11133–11140, 2020.
  * [19] Michael J Jones and Sai Rambhatla.  Body part alignment and temporal attention for video-based person re-identification.  In BMVC, 2019.
  * [20] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  arXiv preprint arXiv:1609.02907, 2016.
  * [21] Shuang Li, Slawomir Bak, Peter Carr, and Xiaogang Wang.  Diversity regularized spatiotemporal attention for video-based person re-identification.  In CVPR, pages 369–378, 2018.
  * [22] Xingze Li, Wengang Zhou, Yun Zhou, and Houqiang Li.  Relation-guided spatial attention and temporal refinement for video-based person re-identification.  In AAAI, pages 11434–11441, 2020.
  * [23] Yaoyu Li, Hantao Yao, Lingyu Duan, Hanxing Yao, and Changsheng Xu.  Adaptive feature fusion via graph neural network for person re-identification.  In ACM MM, pages 2115–2123, 2019.
  * [24] Shengcai Liao, Yang Hu, Xiangyu Zhu, and Stan Z Li.  Person re-identification by local maximal occurrence representation and metric learning.  In CVPR, pages 2197–2206, 2015.
  * [25] Jiawei Liu, Zheng-Jun Zha, Di Chen, Richang Hong, and Meng Wang.  Adaptive transfer network for cross-domain person re-identification.  In CVPR, pages 7202–7211, 2019.
  * [26] Jiawei Liu, Zheng-Jun Zha, Xuejin Chen, Zilei Wang, and Yongdong Zhang.  Dense 3d-convolutional neural network for person re-identification in videos.  ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM), 15(1s):1–19, 2019.
  * [27] Jiawei Liu, Zheng-Jun Zha, QI Tian, Dong Liu, Ting Yao, Qiang Ling, and Tao Mei.  Multi-scale triplet cnn for person re-identification.  In ACM MM, pages 192–196. ACM, 2016.
  * [28] Ziyu Liu, Hongwen Zhang, Zhenghao Chen, Zhiyong Wang, and Wanli Ouyang.  Disentangling and unifying graph convolutions for skeleton-based action recognition.  In CVPR, pages 143–152, 2020.
  * [29] Niall McLaughlin, Jesus Martinez Del Rincon, and Paul Miller.  Recurrent convolutional network for video-based person re-identification.  In CVPR, pages 1325–1334, 2016.
  * [30] Jiaxu Miao, Yu Wu, Ping Liu, Yuhang Ding, and Yi Yang.  Pose-guided feature alignment for occluded person re-identification.  In ICCV, pages 542–551, 2019.
  * [31] Deqiang Ouyang, Yonghui Zhang, and Jie Shao.  Video-based person re-identification via spatio-temporal attentional and two-stream fusion convolutional networks.  Pattern Recognition Letters, 117:153–160, 2019.
  * [32] Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra.  Grad-cam: Visual explanations from deep networks via gradient-based localization.  In ICCV, pages 618–626, 2017.
  * [33] Yantao Shen, Hongsheng Li, Shuai Yi, Dapeng Chen, and Xiaogang Wang.  Person re-identification with deep similarity-guided graph neural network.  In ECCV, pages 486–504, 2018.
  * [34] Lei Shi, Yifan Zhang, Jian Cheng, and Hanqing Lu.  Skeleton-based action recognition with directed graph neural networks.  In CVPR, pages 7912–7921, 2019.
  * [35] Weijing Shi and Raj Rajkumar.  Point-gnn: Graph neural network for 3d object detection in a point cloud.  In CVPR, pages 1711–1719, 2020.
  * [36] Arulkumar Subramaniam, Athira Nambiar, and Anurag Mittal.  Co-segmentation inspired attention networks for video-based person re-identification.  In ICCV, October 2019.
  * [37] Arulkumar Subramaniam, Athira Nambiar, Anurag Mittal, and Anurag Mittal.  Co-segmentation inspired attention networks for video-based person re-identification.  In ICCV, pages 562–572, 2019.
  * [38] Ke Sun, Bin Xiao, Dong Liu, and Jingdong Wang.  Deep high-resolution representation learning for human pose estimation.  In CVPR, pages 5693–5703, 2019.
  * [39] Yifan Sun, Liang Zheng, Yi Yang, Qi Tian, and Shengjin Wang.  Beyond part models: Person retrieval with refined part pooling (and a strong convolutional baseline).  In ECCV, pages 480–496, 2018.
  * [40] Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna.  Rethinking the inception architecture for computer vision.  In CVPR, pages 2818–2826, 2016.
  * [41] Chiat-Pin Tay, Sharmili Roy, and Kim-Hui Yap.  Aanet: Attribute attention network for person re-identifications.  In CVPR, pages 7134–7143, 2019.
  * [42] Taiqing Wang, Shaogang Gong, Xiatian Zhu, and Shengjin Wang.  Person re-identification by video ranking.  In ECCV, pages 688–703. Springer, 2014.
  * [43] Yiming Wu, Omar El Farouk Bourahla, Xi Li, Fei Wu, Qi Tian, and Xue Zhou.  Adaptive graph representation learning for video person re-identification.  IEEE Transactions on Image Processing, 29:8821–8830, 2020.
  * [44] Yichao Yan, Jie Qin, Jiaxin Chen, Li Liu, Fan Zhu, Ying Tai, and Ling Shao.  Learning multi-granular hypergraphs for video-based person re-identification.  In CVPR, pages 2899–2908, 2020.
  * [45] Yichao Yan, Qiang Zhang, Bingbing Ni, Wendong Zhang, Minghao Xu, and Xiaokang Yang.  Learning context graph for person search.  In CVPR, pages 2158–2167, 2019.
  * [46] Jinrui Yang, Wei-Shi Zheng, Qize Yang, Ying-Cong Chen, and Qi Tian.  Spatial-temporal graph convolutional network for video-based person re-identification.  In CVPR, pages 3289–3299, 2020.
  * [47] Zheng-Jun Zha, Jiawei Liu, Di Chen, and Feng Wu.  Adversarial attribute-text embedding for person search with natural language query.  IEEE Transactions on Multimedia, 22(7):1836–1846, 2020.
  * [48] Wei Zhang, Shengnan Hu, Kan Liu, and Zhengjun Zha.  Learning compact appearance representation for video-based person re-identification.  IEEE Transactions on Circuits and Systems for Video Technology, 29(8):2442–2452, 2018.
  * [49] Xikun Zhang, Chang Xu, and Dacheng Tao.  Context aware graph convolution for skeleton-based action recognition.  In CVPR, pages 14333–14342, 2020.
  * [50] Yiheng Zhang, Dong Liu, and Zheng-Jun Zha.  Improving triplet-wise training of convolutional neural network for vehicle re-identification.  In ICME, pages 1386–1391, 2017.
  * [51] Haiyu Zhao, Maoqing Tian, Shuyang Sun, Jing Shao, Junjie Yan, Shuai Yi, Xiaogang Wang, and Xiaoou Tang.  Spindle net: Person re-identification with human body region guided feature decomposition and fusion.  In CVPR, pages 1077–1085, 2017.
  * [52] Liang Zheng, Zhi Bie, Yifan Sun, Jingdong Wang, Chi Su, Shengjin Wang, and Qi Tian.  Mars: A video benchmark for large-scale person re-identification.  In ECCV, pages 868–884. Springer, 2016.
  * [53] Kuan Zhu, Haiyun Guo, Zhiwei Liu, Ming Tang, and Jinqiao Wang.  Identity-guided human semantic parsing for person re-identification.  In ECCV, 2020.


# Doing More by Doing Less: How Structured Partial Backpropagation Improves
Deep Learning Clusters

Adarsh Kumar<EMAIL_ADDRESS>Amazon Alexa AI ,  Kausik Subramanian
University of Wisconsin, Madison ,  Shivaram Venkataraman  University of
Wisconsin, Madison and  Aditya Akella  University of Texas at Austin

(2018; 2021)

###### Abstract.

Many organizations employ compute clusters equipped with accelerators such as
GPUs and TPUs for training deep learning models in a distributed fashion.
Training is resource-intensive, consuming significant compute, memory, and
network resources. Many prior works explore how to reduce training resource
footprint without impacting quality, but their focus on a subset of the
bottlenecks (typically only the network) limits their ability to improve
overall cluster utilization. In this work, we exploit the unique
characteristics of deep learning workloads to propose Structured Partial
Backpropagation(SPB), a technique that systematically controls the amount of
backpropagation at individual workers in distributed training. This
simultaneously reduces network bandwidth, compute utilization, and memory
footprint while preserving model quality. To efficiently leverage the benefits
of SPB at cluster level, we introduce Jigsaw, a SPB aware scheduler, which
does scheduling at the iteration level for Deep Learning Training(DLT) jobs.
We find that Jigsaw can improve large scale cluster efficiency by as high as
28%.

††copyright: acmcopyright††journalyear: 2018††doi:
10.1145/1122445.1122456††conference: Woodstock ’18: ACM Symposium on Neural
Gaze Detection; June 03–05, 2018; Woodstock, NY††booktitle: Woodstock ’18: ACM
Symposium on Neural Gaze Detection, June 03–05, 2018, Woodstock, NY††price:
15.00††isbn: 978-1-4503-XXXX-X/18/06††journalyear: 2021††copyright:
acmcopyright††conference: 2nd International Workshop on Distributed Machine
Learning DistributedML 2021; December 7, 2021; Virtual Event,
Germany††booktitle: 2nd International Workshop on Distributed Machine Learning
DistributedML 2021 (DistributedML’21), December 7, 2021, Virtual Event,
Germany††price: 15.00††doi: 10.1145/3488659.3493778††isbn:
978-1-4503-9134-4/21/12

##  1\. Introduction

With the widespread use of deep learning models in a variety of applications,
many organizations are employing large clusters of machines equipped with
hardware accelerators for model training. These clusters are expensive to
build and are power hungry. They are also oversubscribed with Deep Learning
Training(DLT) jobs often having to wait in queues for hours to days before
getting scheduled (Jeon et al., 2019; Gu et al., 2019). Thus, understanding
how to improve the utilization of such clusters is an important goal. In this
paper, we develop a novel technique for improving deep learning cluster
efficiency that is centered around the idea of having DLT jobs do less work
which can be systematically leveraged to run more training jobs in a highly
efficient manner.

Today, training of DNNs is typically done using algorithms like stochastic
gradient descent (SGD), an iterative algorithm where every iteration computes
gradients by running a forward pass followed by a backward pass. To scale SGD
across machines the most commonly used method is data parallel distributed
training, where gradients computed at each worker are aggregated after every
iteration of training. SGD can take thousands of iterations to converge and
thus training a deep learning model can take days or weeks (Jeon et al.,
2019).

Many recent works (Vogels et al., 2019; Lin et al., 2020; Alistarh et al.,
2017) have considered how to reduce the resources required by a given job with
the primary focus being algorithmic techniques that can approximate gradients
exchanged between workers during distributed training without affecting
accuracy. Most of these techniques aim to solely minimize network
communication and examples include quantizing gradients (Alistarh et al.,
2017), dropping parts of the gradient (Lin et al., 2020) or using low-rank
updates (Vogels et al., 2019; Wang et al., 2018).

Unfortunately, these techniques provide limited improvements for deep learning
clusters equipped with modern hardware that are used to train multiple models
simultaneously (Xiao et al., 2018; Gu et al., 2019; Jeon et al., 2019). This
is primarily due to following reasons: First, while existing approaches
optimize communication, they fail to reduce the total amount of compute
resources or memory required during training. For example, if a gradient
dropping scheme only preserves the top-20% of the gradient values for
communication, we still need to compute the gradients for all the parameters
during the backward phase, ending up using the same compute. Thus, prior
approaches simply shift bottlenecks from the network to compute in large
multi-tenant clusters. Further, while running in a multi-tenant cluster, the
goals for an organization are typically to improve overall cluster-wide
utilization (Xiao et al., 2018) (e.g., reduce makespan given a set of jobs)
and only reducing the network resources required provides limited cluster-wide
benefits.

Figure 1. Structured Partial Backpropagation (SPB)

This prompts us to ask the following question:

_“How can we design a distributed training scheme that can provide cluster-
wide benefits in a multi-tenant setting?”_

To improve the overall cluster efficiency we need to improve the resource
utilization of jobs across both compute as well as communication dimension.
Thus, techniques that avoid computation of gradients which do not need to be
communicated can lead to savings across both resources. Based on this insight,
we design Structured Partial Backpropagation (SPB), a new gradient compression
scheme that can provide cluster-wide benefits.

Our first observation in designing SPB is that similar to existing schemes
like top-K gradient dropping, we can approximate the gradient by updating
different parts of the overall gradient from different workers. For example,
consider a job which is spread across three workers as shown in Figure 1. In
this case, two of the three workers compute partial gradients (33% and 66%)
which are aggregated to derive an overall approximate gradient. Assuming
synchronous SGD, the above described scheme does not improve the time taken by
a single iteration as there is one worker which needs to compute the entire
gradient. However, this scheme does yield cluster-wide benefits as it leads to
an aggregate reduction in network utilization (similar to the top-50% scheme),
while also saving compute resources along with memory as we describe next.

The compute and memory savings in SPB arise from the way gradients are
computed for deep learning jobs. To compute a gradient, first a forward pass
is performed that computes the loss value for the data examples with respect
to the current model. Following this, a backward pass is performed to compute
the final gradient values. When using SPB, we conduct the backward pass for a
fraction of the layers from the end111By “end” we refer to the final output
layer of the DNN of the DNN network, and this leads to reduced computation as
shown in Figure 1. The fraction of layers are carefully chosen to be the
suffix layers as computing gradients for layer $k$ requires gradients from all
layers $l$, where $l\geq k$.

% Backprop |  Forward Pass (ms) |  Backward Pass(ms) |  Peak Mem (GB)
---|---|---|---
100 |  34.79 |  79.89 |  6.5
90 |  34.85 |  70.24 |  5.7
80 |  34.71 |  58.86 |  5.1
70 |  34.61 |  49.92 |  4.6
60 |  34.72 |  43.74 |  4.3
50 |  34.70 |  36.58 |  4.1
40 |  34.61 |  29.93 |  3.8
30 |  34.67 |  23.02 |  3.5
20 |  34.84 |  16.34 |  3.3
10 |  34.86 |  8.35 |  3.1
5 |  34.64 |  3.56 |  2.9
Table 1. Effect of % partial Backprop on Resource Utilization of ResNet101
model. BatchSize:64, Tesla V100

SPB can also save memory, as we can avoid storing intermediate outputs for
layers that are not going to participate in the backward pass. This opens the
door for space multiplexing in hardware accelerators.

We theoretically prove that SPB converges in the same order as SGD and has
bounded impact on model quality in a limited setting and empirically show
minimal impact on model quality across 10 models ranging from computer vision
models (e.g., ResNet-50, VGG-19 etc.) to NLP models (CNN-Text, LSTM etc.).

While SPB can help reduce the resource requirement for a single job, there is
limited impact on cluster-wide resource utilization without corresponding
support from the job schedulers. Today, schedulers treat DLT jobs as fixed-
work units and perform gang scheduling such that every worker receives the
same amount of compute, memory and network resources. Thus, even if SPB were
used, existing schedulers would not be able to capitalize on resources that
become available (e.g., $2^{nd}$/$3^{rd}$ worker in Fig 1).

To this end, we design a new cluster scheduler, Jigsaw, that can account for
the variable amounts of computation that are created as a result of SPB and
pack computations from different workloads at fine time-scales to improve
overall cluster utilization. Performing such packing requires reasoning about
when and how much resources are going to be available in the future. We
perform fine-grained iteration-level scheduling and exploit the repetitive
nature of DL workloads to derive a centralized scheduling policy that
intelligently places tasks to maximize resource utilization.

Our experiments on a 45-GPU cluster show that Jigsaw, in conjunction with SPB,
can improve the makespan and cluster utilization by $~{}28\%$ while running a
publicly available trace of DL jobs (Jeon et al., 2019). We also show that
Jigsaw is more tolerant to resource contention in comparison to other state of
the art DLT schedulers.

##  2\. Structured Partial Backprop

We now describe Structured Partial Backpropagation, a distributed training
scheme that can provide benefits across multiple resource dimensions. Consider
a distributed training job running with $k$ workers, training a $L$ layer DNN.
We assume a parameter server (PS) setup (Li et al., 2014a) for data parallel
training where each worker computes the gradient for all $L$ layers and the
gradient values are aggregated at the PS. The PS maintains a global copy of
the model, which is updated after every iteration.

We first describe the changes in the role of each worker with SPB. At the
start of an iteration $i$, as in existing frameworks, each worker fetches the
latest model version from the parameter server (PS). To make sure all training
data points contribute equally, each worker samples its batch of data from the
entire dataset and performs a forward pass to obtain

Table 2. Median time and memory usage during forward and backward pass, and gradient size of different DNN architectures on Tesla V100 (batch size of 128). Model | Forward | Backward |
---|---|---|---
Time (ms) |  Mem (GB) |  Time (ms) |  Mem (GB) |  Grad (MB)
ResNet18 |  9.19 |  0.05 |  21.49 |  2.46 |  44
ResNet34 |  16.11 |  0.08 |  36.69 |  3.08 |  85
ResNet50 |  36.32 |  0.09 |  78.9 |  7.33 |  94
ResNet101 |  60.51 |  0.17 |  135.14 |  9.79 |  170
ResNet152 |  86.9 |  0.23 |  197.05 |  12.81 |  232
VGG19 |  6.82 |  0.08 |  16.31 |  2.02 |  80
VGG16 |  5.68 |  0.06 |  13.96 |  1.97 |  59
VGG11 |  3.34 |  0.04 |  7.8 |  1.83 |  36
GoogleNet |  41.33 |  0.05 |  99.17 |  5.96 |  24

the loss with respect to the model. The main changes occur during the backward
pass: instead of performing the entire backward pass i.e. computing the
gradient for all the layers, each worker performs backpropagation on a fixed
suffix of the network. As shown in Figure 1, the $j^{th}$ worker does backward
propagation for $\frac{jL}{k}$ of the layers starting from the output layer of
the model. Finally, each worker sends the gradients computed to the PS.

Similar to existing setups, the PS in SPB sends the latest version of the
model to all workers at the start of an iteration. The main difference occurs
in the aggregation phase: the PS now receives partial gradient from each
worker and needs to aggregate them to update the model. The PS computes a
weighted average, i.e., a layer’s gradient update is averaged by the effective
number of workers that contributed to it. Accordingly, the learning rate is
also scaled with respect to the number of workers contributing towards the
gradient.

The above _structured_ approach to backpropagation has following notable
aspects:

Resource Savings: As shown in Table 2, the backward pass uses more memory and
takes longer to complete for DNNs. By doing backward pass for fraction of
layers, SPB can save both compute and memory, thus enabling better time
multiplexing of a GPU across jobs. Table: 1 shows the savings when partial
backpropagation is done for ResNet 101 model.

Gradient Dependency: Compute can only be saved with our proposed SPB approach.
Avoiding backpropagation in Random-k or Top-k dropping is not possible because
of the dependency of the gradients of early layers on later ones.

Per-Iteration Time: On average, SPB reduces workers’ running time. However,
the per-iteration time remains the same as in synchronous SGD training as
there’s one worker that does complete backward propagation of all $L$ layers.
Also, unlike previous gradient compression techniques like PowerSGD (Vogels et
al., 2019) or Atomo (Wang et al., 2018), we do not add any additional compute
overhead to perform gradient compression.

###  2.1. Theoretical Analysis

We now present a worst-case theoretical analysis that proves that SPB
converges to an equivalent solution as traditional distributed SGD. We
approach this problem by first presenting the convergence rate for traditional
distributed SGD and then compare this to the convergence rate when using SPB.

Assumptions and Notation. We denote $X$ as the trainable parameters of the
model and $f$ as the loss function. To simplify our theoretical analysis we
assume that $f:X\to\mathbb{R}$ is a convex function with
$\beta$-smoothness222A continuously differentiable function $f$ is
$\beta$-smooth if the gradient $\nabla f$ is $\beta$ Lipschitz continuous..

Given these assumptions the convergence rate for SGD is known from (Bubeck,
2014) to be:

###### Theorem 2.1.

Let X be convex compact set and $R^{2}=sup_{x,x_{1}\in X}||x-x_{1}||^{2}$. If
the approximate gradient $\tilde{g}(x)$ is such that $E||\nabla
f(x)-\tilde{g}(x)||^{2}\leq V^{2}$, after $t$ iterations, SGD with step size
$\frac{1}{\beta+\frac{1}{\eta(t)}}$, where
$\eta(t)=\frac{R}{\sigma}\sqrt{\frac{2}{t}}$, achieves

(1) $E(f(\frac{1}{t}\sum_{s=1}^{t}x_{s+1})-f(x^{*}))\leq
R\sqrt{\frac{2V^{2}}{t}}+\frac{\beta R^{2}}{t}$

The above result bounds the difference between $f(\hat{x})$ after $t$
iterations and the optimal value $f(x^{*})$ in terms of $V^{2}$, which is a
bound on how far our estimated gradient is from the true gradient.

Please see our Github repo333https://github.com/adarsh-kr/Paper_JigSaw- for a
complete proof.

Distributed Mini-batch SGD. Now, we consider the scenario where we have $k$
workers each processing a batch $\frac{B}{k}$ at every iteration. We first
consider the scenario where every worker computes the entire gradient and
attempt to bound the value of $E||\nabla f(x)-\tilde{g}(x)||^{2}$.

###### Lemma 2.2.

With $k$ workers, an overall batch size of $B$ and assuming $||g(x_{i})||<P$
$\forall i$, for mini-batch SGD, we have $E\|\nabla
f(X)-\tilde{g}(x)\|^{2}\leq 2P^{2}\frac{k}{B}$

SPB Convergence Rate We next consider the case when SPB is used to prune
gradients. The main difference here is that $i^{th}$ block of the gradient
vector will be updated by $i$ workers.

###### Theorem 2.3.

When using SPB with $k$ workers and overall batch size of $B$ and assuming
$||g(x_{i})||<P$ $\forall i$, we have $E\|\nabla f(X)-\tilde{g}(x)\|^{2}\leq
2P^{2}\frac{k}{B}log(k)$

The above result shows that when using SPB we can similarly bound the value of
$E||\nabla f(x)-\tilde{g}(x)||^{2}$, but the bound here has an additional
factor of $log(k)$ where $k$ is the number of workers. Applying this result to
Theorem 2, we see that the convergence rate when using SPB is, in the worst
case, $log(k)$ slower, i.e., when using SPB we might require a factor of
$log(k)$ more iterations to converge to a similar quality result. However,
this is a worst-case bound for convex functions. We empirically show how SPB
performs in practice for real-world deep learning models next.

(a) Job DAG Structure (b) Gang Scheduling with SPB (c) Iteration-level
scheduling with SPB

Figure 2.  (a) DAG of a DNN training job trained with SPB with arrows
indicating dependencies. Tasks of iteration 2 can run only after all tasks of
iteration 1 have completed. Worker sizes indicate varying work distribution.
Example of (b) gang scheduling versus (c) iteration-level scheduling. Gang
scheduling, which operates at a job-level, cannot utilize the resource savings
generated by SPB.

##  3\. Jigsaw: A SPB aware scheduler

In this section, we describe the Jigsaw scheduler and how it is designed to
leverage the gains obtained from our SPB to maximize cluster efficiency. We
first describe some unique properties of SPB jobs that our scheduler needs to
consider. Following that we present our scheduling algorithm that aims to
improve cluster utilization and makespan.

Figure 2(a) shows the task DAG of a single deep learning training job trained
with SPB with three workers; for each iteration, we have multiple tasks
running on parallel workers. Once the workers have computed the gradients for
iteration $i$ and updated the parameter server, we can schedule tasks
corresponding to iteration $i+1$. Each task has two resources in its
specification: peak GPU memory required, and running time. We note that these
resource specifications can be obtained by profiling a job for a few
iterations (Xiao et al., 2018). Different tasks in the same iteration can have
different resource characteristics due to SPB.

Given a set of DLT task DAGs, the Jigsaw scheduler computes _when_ a task
should run, and on _which_ machine.

###  3.1. Iteration-Level Scheduling

Existing state of the art DLT schedulers like Gandiva (Xiao et al., 2018) and
Tiresias (Gu et al., 2019) perform scheduling at the granularity of jobs, and
rely on the paradigm of gang scheduling, i.e., for each iteration, all
parallel workers begin and end at the same time. However performing scheduling
only when all workers have finished one (or more) iterations is insufficient
to make use of resources saved by SPB.

Consider the example shown in Figure 2(b). In this case we have two parallel
DLT jobs (Job1, Job2) each of which has workers using SPB. Thus one of the
workers finishes in 0.3s while the other two take 0.6s and 1s respectively.
With gang scheduling we can see that the scheduler is only invoked once all
tasks of the iteration complete. Thus even though Device0 has finished worker0
of Job1 at 0.3s, it remains idle for 0.7s before being assigned a new task. By
scheduling at the _granularity of iterations_ , we can utilize the gains from
SPB and utilize the cluster in a more effective way. In Figure 2(c), we can
see that each worker in a job can start at a staggered time (e.g. for Job2)
but they still follow the dependencies where one iteration is completed before
the next one starts. In this case as soon as Device0 is done with worker0 of
Job1 at 0.3s, it can be assigned to start Job2 thus improving resource
utilization and makespan for the cluster.

Scheduling overheads. However performing iteration-level scheduling can be
challenging as there is additional overhead for a centralized cluster
scheduler to come up with iteration-level schedules as iterations can be very
short (100ms). To overcome the challenge of generating schedules efficiently,
in Jigsaw we utilize the fact that ML-training jobs are iterative and thus the
scheduler has visibility into what tasks may arrive in the future from a given
job. Thus we perform coarse-grained scheduling (on the granularity of minutes)
of fine-grained iterations (Venkataraman et al., 2017).

Task switching overheads. Switching between tasks at a fine granularity on a
device can be expensive, especially when workers are moved to a new device.
This arises from the fact that moving a worker to a new device entails
fetching the model’s computation graph and its latest parameters to the GPU
before training can resume. We find that the model parameters and computation
graph are typically much smaller (Yu and Chowdhury, 2019) compared to the
intermediate data generated. Thus for workers that are time-sharing in the
same device (e.g. Device1 in Figure 2(b) we retain the model parameters in the
global memory of the GPU and this helps reduce switching overheads. For moving
models across machines, as shown (e.g. Device3 in Figure 2(b)), we account for
the overhead of data transfer as a part of scheduling.

###  3.2. Scheduling Algorithm

We next describe our scheduling algorithm. The scheduler computes the task
placement for a scheduling interval $\mathcal{I}$. Our heuristic places
schedulable tasks (taking into account iteration dependencies) in a
2-dimensional space of resources (compute/device) and time (RT-Space) and
tries to minimize makespan.

Task Prioritization. All tasks that are ready to run are placed in priority
queue. Similar to existing big-data schedulers that aim to improve packing
(Grandl et al., 2014, 2016), we prioritize tasks that require greater amount
of resources. We calculate this priority as a normalized product of the task’s
GPU resource and running time. Given the dependency structure across
iterations, placing the task with the highest resource requirement first also
ensures that overall job progress does not get delayed.

Task Placement. Given a task and a partially occupied RT-Space, our scheduler
next decides when a task must be run and on which machine. There are multiple
considerations which decide placement of a task - first and foremost, we must
wait for tasks corresponding to the previous iteration to finish before we can
schedule the current task. Furthermore, the machine must have resources
available for the entire duration of the task.

The scheduler first finds the earliest time the task can be scheduled to run
based on the end times of the tasks of the previous iterations $T_{i-1}$.
However, not all machines can start the task immediately after $T_{i-1}$. If a
machine ran the task corresponding to the same worker and the $i-1$ iteration,
the task is immediately schedulable as the machine can reuse the model
computation graph from previous iteration. For the other machines, we add a
startup time which is dependent on the size of the model ($\gamma\times
model\\_size$) to capture the delay in transferring the model to a new
machine. To reduce makespan, we greedily schedule the task on a machine where
the task can start the earliest of all machines. Since the scheduler chooses a
machine where we can start the task the earliest, it will naturally prefer
machines which ran the previous iteration tasks and avoid unnecessary task
movement across iterations.

##  4\. Evaluation

###  4.1. SPB effect on Model Quality

We first present empirical results on the convergence of popular deep learning
models when using SPB while training. We consider models from a number of
domains including computer vision, NLP etc. and also consider models of
different complexity (i.e., depth or number of layers).

Figure 3. Convergence of ResNet18 on CIFAR10 as we vary the number of workers.
(SPB)

For CV, we considered image classification with CIFAR10 and CIFAR100 datasets
and a number of DNN families (ResNet, VGG, GoogLeNet, and DenseNet). We used
SGD with momentum and $10^{-4}$ weight decay as our optimizer configuration.
We tried 3 learning rates for each model and picked the one attaining best
accuracy. For NLP, we selected models for classification on the MR dataset
(Pang and Lee, 2005) and language modeling on WikiText (Merity et al., 2016).
We use 4 workers, each running on an NVIDIA V100 GPU, for all the experiments.

We present a comparison of the accuracy achieved when using SPB vs. a baseline
where models are trained using standard distributed SGD optimization in Table
3.

Our results from Table 3 shows that there is a minimal effect on the accuracy
achieved when models are trained with SPB. Even though the DNN early layers
are getting updated by fewer workers, model convergence is not significantly
impacted. We attribute this behavior of SPB to the fact that early layers
converge faster than later layers, and thus require fewer gradient descent
steps. This has also been observed by previous work (Brock et al., 2017; Raghu
et al., 2017).

Further, we note that using SPB for a more complex task could lead to a bigger
difference in

Dataset | Model | Accuracy | Accuracy
---|---|---|---
SPB | SGD
CIFAR10 | ResNet18 | 93.96 | 94.02
ResNet34 | 93.81 | 94.96
DenseNet121 | 94.18 | 94.35
GoogleNet | 94.07 | 93.83
VGG16 | 91.93 | 92.35
CIFAR100 | ResNet18 | 71.31 | 72.83
ResNet34 | 69.94 | 71.2
MR | CNNText | 77.12 | 77.35
LSTMText | 78.02 | 80.23
WikiText 2 | LSTM | 105* | 103*
Table 3. Comparison of maximum accuracy of various models w/o SPB. *Perplexity
is reported for language model on WikiText.

accuracy (though still under 2%). For example, with ResNet18, the accuracy
difference due to SPB increases from 0.06% to 1.52% as we go from CIFAR10 to
CIFAR100. This we believe can be overcome by warm up epochs, where for initial
$N$ epochs we train the model using the full gradient from all the workers.

Figure 3 shows the convergence of ResNet18 model when varying the number of
workers on the CIFAR10 dataset while using SPB. We maintain a batch size of
128 per worker. From the figure we see that as we increase the number of
workers it takes more iterations to converge to the best accuracy. Our theory
also suggests this in terms of the $log(k)$ factor in the convergence rate for
$k$ workers, albeit for convex functions. Also, we find that the maximum
accuracy achieved using 8 workers is slightly lesser than that achieved with 4
workers. We believe that this could be related to using a larger batch size in
this setting. We discuss ways in discussion section to close this gap in
accuracy.

(a) Makespan comparison on 45 GPU Cluster (b) JCT comparison 45 GPU Cluster

(c) Worker Migrations

Figure 4.  [Simulated]: (a) Makespan comparison on 45 Tesla V100 cluster. (b)
CDF of JCT for different schedulers (c) CDF for fraction of iterations in
which DLT jobs were migrated to another machine

###  4.2. Jigsaw effect on Cluster Efficiency

In this section, we use a mix of simulations and cluster experiments to
present the performance of our system Jigsaw and compare with other state of
the art DLT schedulers.

Setup: For our simulations, we created a discrete event based simulator which
we run using a large scale DLT job trace from Microsoft (Gu et al., 2019; Jeon
et al., 2019). We enriched the trace with additional information, specifically
peak memory usage, execution time, gradient size and model size etc. by
profiling models used in Gu et al. (2019) trace. To enable SPB, we also
profiled execution time of DLT workers when varying the proportion of layers
that perform backpropagation. All our profiling was done in isolation on Tesla
V100 GPU. To account for migration overheads, we measure the transfer cost of
moving models across different machines and the network overhead in PS-worker
communication.

As described in Section 3, Jigsaw creates a schedule for all the active DLT
jobs for next $T$ minutes considering the complete cluster and communicates
this schedule to the individual machines. In our experiments we have kept $T$,
the scheduling interval to be 1 min. While creating the scheduling plan for
next scheduling interval, Jigsaw considers the affinity of tasks towards the
machine they were executed previously to avoid overheads from migration.

Workload: We have evaluated Jigsaw on publicly available workload of DNN
training from Microsoft (Gu et al., 2019) which was scaled down for practical
purposes. This workload contains around 500 DLT Training Job, with each job
arriving at an average interval of 30 seconds. Around 50% of the DLT jobs had
1 worker and the rest are multi-worker DLT jobs, with 10% having 2, 20% having
4, 15% having 8 and 5% having 16 workers. A DLT job is considered finished
once a pre-specified number of iterations has been executed.

Metrics: To quantify and compare the performance of Jigsaw, we use two
metrics: Job Completion Time(JCT): JCT is defined as the time taken to finish
one job from the time it was submitted. This also includes any waiting time
which the job had to incur. Makespan: Makespan is the end time of the last job
to finish in a trace. Improving makespan, correlates with improvement in
resource utilization.

Baselines: We evaluate our system Jigsaw against two state of the art DLT
schedulers: Gandiva (Xiao et al., 2018), which improves cluster efficiency by
packing jobs on as few machines as possible and Tiresias (Gu et al., 2019),
which schedules job according to Least Attained Service(LAS) policy so that
all jobs obtain equal service over time. Both baselines are run standard DLT
jobs, without SPB, as their APIs do not allow workers of same DLT job to have
different resource requirements.

Results: Figure 4 we compare makespan and JCT for Tiresias and Gandiva with
Jigsaw. As can be seen, on 45 GPU Cluster, Jigsaw improves makespan by around
22% over Tiresias and 28% over Gandiva.

Similarly, as can be seen from the CDF plot of JCT, our system Jigsaw improves
the JCT of DLT jobs against Gandiva and Tiresias on a 45 GPU Cluster.

###  4.3. Testbed Overheads

We discuss the systems overheads observed in our testbed.

Model Movements: Migrating DLT job’s worker across different machines is
costly (Xiao et al., 2018). Since Jigsaw does fine grained scheduling at the
level of iteration, migrating the workers of DLT jobs at every iteration would
result in significant overheads. Jigsaw mitigates this by considering the
migration overhead while deciding the placement of a task. In Figure 4(c) we
plot the CDF of fraction of iterations for which a worker had to be migrated
to different machine. Fraction of iteration is calculated as total migrations
divided by total iterations (lower the better). As can be seen from the plot,
even after scheduling at iteration level Jigsaw has low migration overhead.

Time Multiplexing Overhead: To improve the cluster utilization, Jigsaw also
does time multiplexing of DLT tasks. SPB creates opportunity for time
multiplexing by finishing tasks earlier by doing partial backprop. To study
the overhead of time multiplexing of DLT tasks, we ran 500 iterations of 5
real DNN models from Computer Vision and NLP family in sequence and in a round
robin manner. In sequence, the models are trained for 500 iterations one after
the another, while in round-robin we train a model for an iteration and then
we switch to another model and proceed in a round-robin manner. We found the
slowdown to be less than 1% during round-robin training, thus, the overhead of
time multiplexing within a GPU is minimal.

##  5\. Related Work

DL training schedulers: There have been several recent works on improving
cluster level scheduling of DL training jobs, with each having a different
objective function (Xiao et al., 2018; Gu et al., 2019; Zhang et al., 2017;
Peng et al., 2018). For example, Gandiva (Xiao et al., 2018) focuses on
improving overall cluster efficiency, while Tiresias (Gu et al., 2019)
optimizes on job completion time and fairness. Similar to Tiresias, Optimus
(Peng et al., 2018) also focuses on average job completion time, while SLAQ
(Zhang et al., 2017) optimizes on model quality. All existing DL training
schedulers gang-schedule and assume equal resource requirement for all the
workers and hence cannot capitalize on resource savings from SPB.

Gradient Pruning: Ali et al (Aji and Heafield, 2017) introduced the idea of
gradient dropping. Strom et al (Strom, 2015; Li et al., 2014b) introduced
dropping gradients larger than a threshold and Adacomp (Chen et al., 2017)
proposed automatically tuning it. To further improve the convergence of
gradient dropping schemes, Chen et al (Ba et al., 2016) introduced layer
normalization. Other works in this domain involve gradient quantization (Seide
et al., 2014; Bernstein et al., 2018; Wen et al., 2017), using low rank
estimation of gradients‘(Vogels et al., 2019). All the above works focus on a
single job setting where compute is not a contended resource, and thus focus
solely on improving communication. We introduce a new structured pruning
approach that can save compute, memory, and network resources.

##  6\. Conclusion

We show how using a structured approach to partial backpropagation can improve
resource utilization of DL training jobs in shared clusters. We introduced a
novel gradient pruning scheme called Structured Backprop Pruning, which saves
compute, memory and network resources, while preserving model quality. To
leverage the gains from SPB, we also introduced a new SPB-aware cluster
scheduler Jigsaw that can improve utilization by performing better time and
space multiplexing. We show that our approach of making the cluster scheduler
aware of the ML workload properties can lead to significant benefits.

## References

  * (1)
  * Aji and Heafield (2017) Alham Fikri Aji and Kenneth Heafield. 2017.  Sparse Communication for Distributed Gradient Descent.  _ArXiv_ abs/1704.05021 (2017).
  * Alistarh et al. (2017) Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. 2017.  QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding.  arXiv:1610.02132 [cs.LG]
  * Ba et al. (2016) Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. 2016\.  Layer Normalization.  _CoRR_ abs/1607.06450 (2016).
  * Bernstein et al. (2018) Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Anima Anandkumar. 2018.  signSGD: compressed optimisation for non-convex problems. In _ICML_.
  * Brock et al. (2017) Andrew Brock, Theodore Lim, James M. Ritchie, and Nick Weston. 2017.  FreezeOut: Accelerate Training by Progressively Freezing Layers.  _ArXiv_ abs/1706.04983 (2017).
  * Bubeck (2014) Sébastien Bubeck. 2014\.  Theory of Convex Optimization for Machine Learning.  _ArXiv_ abs/1405.4980 (2014).
  * Chen et al. (2017) Chia-Yu Chen, Jungwook Choi, Daniel Brand, Ankur Agrawal, Wei Zhang, and Kailash Gopalakrishnan. 2017\.  AdaComp : Adaptive Residual Gradient Compression for Data-Parallel Distributed Training.  _CoRR_ abs/1712.02679 (2017).
  * Grandl et al. (2014) Robert Grandl, Ganesh Ananthanarayanan, Srikanth Kandula, Sriram Rao, and Aditya Akella. 2014\.  Multi-Resource Packing for Cluster Schedulers.  _SIGCOMM Comput. Commun. Rev._ 44, 4 (Aug. 2014), 455–466.  https://doi.org/10.1145/2740070.2626334
  * Grandl et al. (2016) Robert Grandl, Srikanth Kandula, Sriram Rao, Aditya Akella, and Janardhan Kulkarni. 2016.  GRAPHENE: Packing and Dependency-Aware Scheduling for Data-Parallel Clusters. In _12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16)_. Savannah, GA, 81–97.
  * Gu et al. (2019) Juncheng Gu, Mosharaf Chowdhury, Kang G. Shin, Yibo Zhu, Myeongjae Jeon, Junjie Qian, Hongqiang Harry Liu, and Chuanxiong Guo. 2019.  Tiresias: A GPU Cluster Manager for Distributed Deep Learning. In _NSDI_.
  * Jeon et al. (2019) Myeongjae Jeon, Shivaram Venkataraman, Amar Phanishayee, Junjie Qian, Wencong Xiao, and Fan Yang. 2019\.  Analysis of Large-Scale Multi-Tenant GPU Clusters for DNN Training Workloads. In _2019 USENIX Annual Technical Conference (USENIX ATC 19)_. USENIX Association, Renton, WA, 947–960.
  * Li et al. (2014a) Mu Li, David G. Andersen, Jun Woo Park, Alexander J. Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene J. Shekita, and Bor-Yiing Su. 2014a.  Scaling Distributed Machine Learning with the Parameter Server. In _Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation_ (Broomfield, CO) _(OSDI’14)_. USENIX Association, USA, 583–598.
  * Li et al. (2014b) Mu Li, David G. Andersen, Alexander Smola, and Kai Yu. 2014b.  Communication Efficient Distributed Machine Learning with the Parameter Server. In _Proceedings of the 27th International Conference on Neural Information Processing Systems \- Volume 1_ (Montreal, Canada) _(NIPS’14)_. MIT Press, Cambridge, MA, USA, 19–27.
  * Lin et al. (2020) Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William J. Dally. 2020.  Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training.  arXiv:1712.01887 [cs.CV]
  * Merity et al. (2016) Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. 2016.  Pointer Sentinel Mixture Models.  _CoRR_ abs/1609.07843 (2016).
  * Pang and Lee (2005) Bo Pang and Lillian Lee. 2005.  Seeing Stars: Exploiting Class Relationships For Sentiment Categorization With Respect To Rating Scales. In _Proceedings of ACL_. 115–124.
  * Peng et al. (2018) Yanghua Peng, Yixin Bao, Yangrui Chen, Chuan Wu, and Chuanxiong Guo. 2018.  Optimus: an efficient dynamic resource scheduler for deep learning clusters. In _Proceedings of the Thirteenth EuroSys Conference_. 1–14.
  * Raghu et al. (2017) Maithra Raghu, Justin Gilmer, Jason Yosinski, and Jascha Sohl-Dickstein. 2017.  SVCCA: Singular Vector Canonical Correlation Analysis for Deep Understanding and Improvement.  _ArXiv_ abs/1706.05806 (2017).
  * Seide et al. (2014) Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 2014.  1-bit stochastic gradient descent and its application to data-parallel distributed training of speech DNNs. In _INTERSPEECH_.
  * Strom (2015) Nikko Strom. 2015\.  Scalable distributed DNN training using commodity GPU cloud computing. In _INTERSPEECH_.
  * Venkataraman et al. (2017) Shivaram Venkataraman, Aurojit Panda, Kay Ousterhout, Michael Armbrust, Ali Ghodsi, Michael J Franklin, Benjamin Recht, and Ion Stoica. 2017.  Drizzle: Fast and adaptable stream processing at scale. In _Proceedings of the 26th Symposium on Operating Systems Principles_. 374–389.
  * Vogels et al. (2019) Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. 2019\.  PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization.  In _Advances in Neural Information Processing Systems 32_. 14259–14268.
  * Wang et al. (2018) Hongyi Wang, Scott Sievert, Zachary Charles, Shengchao Liu, Stephen Wright, and Dimitris Papailiopoulos. 2018.  ATOMO: Communication-efficient Learning via Atomic Sparsification.  arXiv:1806.04090 [stat.ML]
  * Wen et al. (2017) Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. 2017.  TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning.  In _Advances in Neural Information Processing Systems 30_ , I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.). Curran Associates, Inc., 1509–1519.
  * Xiao et al. (2018) Wencong Xiao, Romil Bhardwaj, Ramachandran Ramjee, Muthian Sivathanu, Nipun Kwatra, Zhenhua Han, Pratyush Patel, Xuan Peng, Hanyu Zhao, Quanlu Zhang, Fan Yang, and Lidong Zhou. 2018\.  Gandiva: Introspective Cluster Scheduling for Deep Learning. In _13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18)_. USENIX Association, Carlsbad, CA, 595–610.
  * Yu and Chowdhury (2019) Peifeng Yu and Mosharaf Chowdhury. 2019.  Salus: Fine-Grained GPU Sharing Primitives for Deep Learning Applications.  arXiv:1902.04610 [cs.DC]
  * Zhang et al. (2017) Haoyu Zhang, Logan Stafman, Andrew Or, and Michael J. Freedman. 2017.  SLAQ: Quality-Driven Scheduling for Distributed Machine Learning. In _Proceedings of the 2017 Symposium on Cloud Computing_ (Santa Clara, California) _(SoCC ’17)_. Association for Computing Machinery, New York, NY, USA, 390–404.  https://doi.org/10.1145/3127479.3127490

##  7\. Appendix

###  7.1. Convergence Analysis

We start by presenting the convergence theorem about SGD in Equation 2 from
(Bubeck, 2014)

###### Theorem 7.1.

Let X be convex compact set and $R^{2}=sup_{x,x_{1}\in X}||x-x_{1}||^{2}$. If
the approximate gradient $\tilde{g}(x)$ is such that $E||\nabla
f(x)-\tilde{g}(x)||^{2}\leq V^{2}$, after $t$ iterations, SGD with step size
$\frac{1}{\beta+\frac{1}{\eta(t)}}$, where
$\eta(t)=\frac{R}{\sigma}\sqrt{\frac{2}{t}}$, achieves

(2) $E(f(\frac{1}{t}\sum_{s=1}^{t}x_{s+1})-f(x^{*}))\leq
R\sqrt{\frac{2V^{2}}{t}}+\frac{\beta R^{2}}{t}$

The above result bounds the difference between $f(\hat{x})$ after $t$
iterations and the optimal value $f(x^{*})$ in terms of $V^{2}$, which is a
bound on how far our estimated gradient is from the true gradient.

Distributed Mini-batch SGD. Now, we consider the scenario where we have $k$
workers each processing a batch $\frac{B}{k}$ at every iteration where $B$ is
cumulative mini batch size. We first consider the scenario where every worker
computes the entire gradient and attempt to bound the value of $E||\nabla
f(x)-\tilde{g}(x)||^{2}$.

###### Lemma 7.2.

With $k$ workers, an overall batch size of $B$ and assuming $||g(x_{i})||<P$
$\forall i$, for mini-batch SGD, we have $E\|\nabla
f(X)-\tilde{g}(x)\|^{2}\leq 2P^{2}\frac{k}{B}$

Proof: We partition the parameter space $X$ into subparts, $x_{i}$

(3)
$\tilde{g}(x,\epsilon)=[....,\frac{1}{B}\sum_{j=1}^{B}g_{i}(x_{i},\epsilon_{j}),....]$

For $i^{t}h$ block of parameters,

(4) $\begin{split}E\|\nabla
f(x_{i})-\tilde{g}(x_{i},\epsilon)\|^{2}&=E\|\nabla
f(x_{i})-\frac{1}{B}\sum_{j=1}^{B}g_{j}(x_{i})\|^{2}\\\ &=\frac{1}{B}E\|\nabla
f(x_{i})-g_{1}(x_{i})\|^{2}\\\ &=\frac{1}{B}p_{i}\end{split}$

where we denote $p_{i}$ as $E\|\nabla f(x_{i})-g_{1}(x_{i})\|^{2}$

For the overall parameter space this reduces to:

(5) $E\|\nabla
f(x)-\tilde{g}(x,\epsilon)\|^{2}=\sum_{i=1}^{k}\frac{1}{B}p_{i}$

Under the assumption that $||g(x_{i})||<P$ $\forall i$, we get

(6) $E\|\nabla f(x)-\tilde{g}(x,\epsilon)\|^{2}\leq 2P^{2}\frac{k}{B}$

We now obtain the same bound for SPB case.

SPB Convergence Rate We next consider the case when SPB is used to prune
gradients. The main difference here is that $i^{th}$ block of the gradient
vector will be updated by $i$ workers.

###### Lemma 7.3.

When using SPB with $k$ workers and overall batch size of $B$ and assuming
$||g(x_{i})||<P$ $\forall i$, we have $E\|\nabla f(X)-\tilde{g}(x)\|^{2}\leq
2P^{2}\frac{k}{B}log(k)$

In SPB setting, $i^{th}$ block will be updated by i workers, leading to
$\frac{iB}{k}$ mini batch, as each worker is processing $\frac{B}{k}$ mini
batch.

(7)
$\tilde{g_{SPB}(x,\epsilon)})=[....,\frac{1}{\frac{iB}{k}}\sum_{j=1}^{\frac{iB}{k}}g_{i}(x_{i},\epsilon_{j}),....]\\\
$

For the $i^{th}$ block of parameters,

(8) $\begin{split}E\|\nabla
f(x_{i})-\tilde{g}(x_{i},\epsilon)\|^{2}&=\frac{k}{iB}p_{i}\end{split}$

Similar to previous baseline case, for the overall parameter space we get,

(9) $\begin{split}E\|\nabla
f(x)-\tilde{g}(x,\epsilon)\|^{2}&=\sum_{i=1}^{k}\frac{k}{iB}p_{i}\\\ &\leq
P^{2}\frac{k}{B}\sum_{i=1}^{k}\frac{1}{i}\\\ &\leq 2P^{2}\frac{k}{B}log(k)\\\
\end{split}$

Substituting Equation 9 and Equation 8 in Equation 2, we compare the
convergence rate, which shows that SPB needs $log(k)$ times more iterations to
achieve similar performance as the baseline setting where all workers are
sending complete gradients. This bound suggests that on increasing the number
of workers, logarithmically more iteration are going to be needed, which seems
intuitive as the more the number of workers, the more fraction of data points
that are not getting utilized in updating the parameters in comparison to
baseline.