summaries: This paper tackles the problem of designing neural network architectures that are robust to adversarial attacks. Several defense techniques against adversarial attacks have been proposed, mainly adversarial training (train on perturbed inputs) and introducing random perturbation to the weights or activations of the network. The paper claims that one limitation of the second approach is that it introduces artifacts (e.g. sparsity). The authors propose a simple but original idea to address this issue: parameterize the network's weight matrices as low rank tensors (in the Tucker format) and randomize the weights by sketching the core tensor of the Tucker decomposition (in effect, the sketching amounts to randomly setting fibers of the core tensor to 0).

summaries: In this paper, the authors propose a randomization-based tensorization framework towards robust network learning. The high-level idea of this work is to reparameterize the network parameters W of each layer with low-rank tensors, where the factor matrices are injected with randomization through randomly sampled sketching matrices. Since the randomization is is done within a subspace than directly on the weight matrix itself, the authors claim that this brings certain advantages such as less sparsity.

abstractText: As deep neural networks become widely adopted for solving most problems in computer vision and audio-understanding, there are rising concerns about their potential vulnerability. In particular, they are very sensitive to adversarial attacks, which manipulate the input to alter models’ predictions. Despite large bodies of work to address this issue, the problem remains open. In this paper, we propose defensive tensorization, a novel adversarial defence technique that leverages a latent high order factorization of the network. Randomization is applied in the latent subspace, therefore resulting in dense reconstructed weights, without the sparsity or perturbations typically induced by the randomization. Our approach can be easily integrated with any arbitrary neural architecture and combined with techniques like adversarial training. We empirically demonstrate the effectiveness of our approach on standard image classification benchmarks. We further validate the generalizability of our approach across domains and low-precision architectures by considering an audio classification task and binary networks. In all cases, we demonstrate superior performance compared to prior works in the target scenario.

authors:
Naveed Akhtar
Ajmal Mian

title: Threat of adversarial attacks on deep learning in computer vision: A survey

venue: IEEE Access,

authors:
Dario Amodei
Sundaram Ananthanarayanan
Rishita Anubhai
Jingliang Bai
Eric Battenberg
Carl Case
Jared Casper
Bryan Catanzaro
Qiang Cheng
Guoliang Chen

title: Deep speech 2: End-toend speech recognition in english and mandarin

venue: In International conference on machine learning,

authors:
Dario Amodei
Chris Olah
Jacob Steinhardt
Paul Christiano
John Schulman
Dan Mané

title: Concrete problems in ai safety

venue: arXiv preprint arXiv:1606.06565,

authors:
Marcella Astrid
Seung-Ik Lee

title: Cp-decomposition with tensor power method for convolutional neural networks

venue: compression. CoRR,

authors:
Anish Athalye
Nicholas Carlini
David Wagner

title: Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples

venue: arXiv preprint arXiv:1802.00420,

authors:
Yusuf Aytar
Carl Vondrick
Antonio Torralba

title: Soundnet: Learning sound representations from unlabeled video

venue: In Advances in Neural Information Processing Systems,

authors:
Casey Battaglino
Grey Ballard
Tamara G Kolda

title: A practical randomized cp tensor decomposition

venue: SIAM Journal on Matrix Analysis and Applications,

authors:
Adrian Bulat
Georgios Tzimiropoulos

title: Binarized convolutional landmark localizers for human pose estimation and face alignment with limited resources

authors:
Nicholas Carlini
David Wagner

title: Towards evaluating the robustness of neural networks

venue: IEEE Symposium on Security and Privacy (SP),

authors:
Matthieu Courbariaux
Yoshua Bengio
Jean-Pierre David

title: Binaryconnect: Training deep neural networks with binary weights during propagations

venue: In NIPS,

authors:
Matthieu Courbariaux
Itay Hubara
Daniel Soudry
Ran El-Yaniv
Yoshua Bengio

title: Binarized neural networks: Training deep neural networks with weights and activations constrained to+ 1 or-1

authors:
Guneet S Dhillon
Kamyar Azizzadenesheli
Zachary C Lipton
Jeremy Bernstein
Jean Kossaifi
Aran Khanna
Anima Anandkumar

title: Stochastic activation pruning for robust adversarial defense

venue: arXiv preprint arXiv:1803.01442,

authors:
Yinpeng Dong
Fangzhou Liao
Tianyu Pang
Hang Su
Jun Zhu
Xiaolin Hu
Jianguo Li

title: Boosting adversarial attacks with momentum

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

authors:
Simon S Du
Jason D Lee

title: On the power of over-parametrization in neural networks with quadratic activation

venue: In ICML,

authors:
N Benjamin Erichson
Krithika Manohar
Steven L Brunton
J Nathan Kutz

title: Randomized cp tensor decomposition

venue: arXiv preprint arXiv:1703.09074,

authors:
Angus Galloway
Graham W Taylor
Medhat Moussa

title: Attacking binarized neural networks

venue: arXiv preprint arXiv:1711.00449,

authors:
Ian J Goodfellow
Jonathon Shlens
Christian Szegedy

title: Explaining and harnessing adversarial examples

venue: arXiv preprint arXiv:1412.6572,

authors:
A. Graves
A. Mohamed
G. Hinton

title: Speech recognition with deep recurrent neural networks

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

authors:
Alex Graves
Navdeep Jaitly

title: Towards end-to-end speech recognition with recurrent neural networks

venue: Proceedings of the 31st International Conference on Machine Learning,

authors:
Chuan Guo
Mayank Rana
Moustapha Cisse
Laurens van der Maaten

title: Countering adversarial images using input transformations

venue: arXiv preprint arXiv:1711.00117,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

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

authors:
Sandy Huang
Nicolas Papernot
Ian Goodfellow
Yan Duan
Pieter Abbeel

title: Adversarial attacks on neural network policies

venue: arXiv preprint arXiv:1702.02284,

authors:
Elias B Khalil
Amrita Gupta
Bistra Dilkina

title: Combinatorial attacks on binarized neural networks

venue: arXiv preprint arXiv:1810.03538,

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

authors:
Tamara G. Kolda
Brett W. Bader

title: Tensor decompositions and applications

venue: SIAM REVIEW,

authors:
Jean Kossaifi
Adrian Bulat
Georgios Tzimiropoulos
Maja Pantic

title: T-net: Parametrizing fully convolutional nets with a single high-order tensor

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

authors:
Jean Kossaifi
Yannis Panagakis
Anima Anandkumar
Maja Pantic

title: Tensorly: Tensor learning in python

venue: The Journal of Machine Learning Research,

authors:
Alex Krizhevsky
Geoffrey Hinton

title: Learning multiple layers of features from tiny images

venue: Technical report, Citeseer,

authors:
Alexey Kurakin
Ian Goodfellow
Samy Bengio

title: Adversarial examples in the physical world

venue: arXiv preprint arXiv:1607.02533,

authors:
Vadim Lebedev
Yaroslav Ganin
Maksim Rakhuba
Ivan V. Oseledets
Victor S. Lempitsky

title: Speeding-up convolutional neural networks using fine-tuned cp-decomposition

venue: In ICLR,

authors:
Ji Lin
Chuang Gan
Song Han

title: Defensive quantization: When efficiency meets robustness

venue: arXiv preprint arXiv:1904.08444,

authors:
Xuanqing Liu
Yao Li
Chongruo Wu
Cho-Jui Hsieh

title: Adv-bnn: Improved adversarial defense through robust bayesian neural network

venue: arXiv preprint arXiv:1810.01279,

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

title: Towards deep learning models resistant to adversarial attacks

venue: arXiv preprint arXiv:1706.06083,

authors:
Alexander Novikov
Dmitry Podoprikhin
Anton Osokin
Dmitry Vetrov

title: Tensorizing neural networks

venue: In Proceedings of the 28th International Conference on Neural Information Processing Systems,

authors:
Adam Paszke
Sam Gross
Soumith Chintala
Gregory Chanan
Edward Yang
Zachary DeVito
Zeming Lin
Alban Desmaison
Luca Antiga
Adam Lerer

title: Automatic differentiation in PyTorch

venue: In NIPS Autodiff Workshop,

authors:
Mohammad Rastegari
Vicente Ordonez
Joseph Redmon
Ali Farhadi

title: Xnor-net: Imagenet classification using binary convolutional neural networks

venue: In ECCV,

authors:
Jonas Rauber
Wieland Brendel
Matthias Bethge. Foolbox v

title: 8.0: A python toolbox to benchmark the robustness of machine learning models

venue: arXiv preprint arXiv:1707.04131,

authors:
Pouya Samangouei
Maya Kabkab
Rama Chellappa

title: Defense-gan: Protecting classifiers against adversarial attacks using generative models

venue: arXiv preprint arXiv:1805.06605,

authors:
Nicholas D Sidiropoulos
Evangelos E Papalexakis
Christos Faloutsos

title: Parallel randomly compressed cubes: A scalable distributed architecture for big tensor decomposition

venue: IEEE Signal Processing Magazine,

authors:
Mahdi Soltanolkotabi
Adel Javanmard
Jason D Lee

title: Theoretical insights into the optimization landscape of over-parameterized shallow neural networks

venue: IEEE Transactions on Information

authors:
Yang Song
Taesup Kim
Sebastian Nowozin
Stefano Ermon
Nate Kushman

title: Pixeldefend: Leveraging generative models to understand and defend against adversarial examples

venue: arXiv preprint arXiv:1710.10766,

authors:
Florian Tramèr
Alexey Kurakin
Nicolas Papernot
Ian Goodfellow
Dan Boneh
Patrick McDaniel

title: Ensemble adversarial training: Attacks and defenses

venue: arXiv preprint arXiv:1705.07204,

title: Mach: Fast randomized tensor decompositions

venue: In Proceedings of the 2010 SIAM International Conference on Data Mining,

authors:
Nico Vervliet
Otto Debals
Laurent Sorber
Lieven De Lathauwer

title: Breaking the curse of dimensionality using decompositions of incomplete tensors: Tensor-based scientific computing in big data analysis

authors:
Siyue Wang
Xiao Wang
Pu Zhao
Wujie Wen
David Kaeli
Peter Chin
Xue Lin

title: Defensive dropout for hardening deep neural networks under adversarial attacks

venue: In Proceedings of the International Conference on Computer-Aided Design,

authors:
Yining Wang
Hsiao-Yu Tung
Alexander J Smola
Anima Anandkumar

title: Fast and guaranteed tensor decomposition via sketching

title: Speech Commands: A Dataset for Limited-Vocabulary Speech Recognition

venue: arXiv e-prints, art

authors:
Cihang Xie
Jianyu Wang
Zhishuai Zhang
Zhou Ren
Alan Yuille

title: Mitigating adversarial effects through randomization

venue: In International Conference on Learning Representations,

authors:
Weilin Xu
David Evans
Yanjun Qi

title: Feature squeezing: Detecting adversarial examples in deep neural networks

venue: arXiv preprint arXiv:1704.01155,

authors:
Longhao Yuan
Chao Li
Jianting Cao
Qibin Zhao

title: Randomized tensor ring decomposition and its application to large-scale data reconstruction

authors:
Guoxu Zhou
Andrzej Cichocki
Shengli Xie

title: Decomposition of big tensors with low multilinear rank

venue: arXiv preprint arXiv:1412.1885,

heading: 1 INTRODUCTION

text:
Deep neural networks (DNNs) are powerful predictive models that achieve impressive accuracy across a wide range of artificial intelligence tasks, including image classification (He et al., 2016; Krizhevsky & Hinton, 2009) and speech recognition (Amodei et al., 2016a; Graves et al., 2013; Graves & Jaitly, 2014). The popularity of DNNs in production-ready systems has raised a serious security concern as DNNs are found to be susceptible to a wide range of adversarial attacks (Madry et al., 2017; Akhtar & Mian, 2018; Dong et al., 2018; Huang et al., 2017; Goodfellow et al., 2014; Kurakin et al., 2016), where small and imperceptible perturbations of the input data lead to incorrect predictions by the networks. These shortcomings pose an obstacle in wide-scale adoption of DNNs and expose an inherent weakness in their reliability. This is especially important when such models become part of security and safety related solutions (Amodei et al., 2016b).
This susceptibility of DNNs to adversarial perturbations has led to a large volume of work that attempts to design robust networks (Dhillon et al., 2018; Lin et al., 2019; Samangouei et al., 2018; Song et al., 2017; Guo et al., 2017). However, advances in designing robust DNNs have been followed with stronger perturbation schemes that defeat such defences (Athalye et al., 2018).
Most defenses that rely on randomization, either apply randomized transformations to the input, e.g. (Xie et al., 2018), or randomization applied within the network, e.g., on the activations (Dhillon et al., 2018) or on the weights directly (Wang et al., 2018). However, all these approaches typically introduce artificats (e.g. sparsity in the weights or activations) and can be defeated by carefully crafted attacks (Athalye et al., 2018). In addition, it is preferable to not to rely on modifications of the inputs but have a network that is inherently robust against attacks. In this paper, we take a different approach to randomization. We first parametrize the network using tensor factorization, effectively introducing a latent subspace spanning the weights. We then apply randomization in that latent subspace, enabling us to create models that are robust to adversarial attacks, without modifying directly the weights, activations or inputs. In summary, we make the following contributions:
• We propose a novel adversarial defence technique that relies on a latent randomized tensor parametrization of each layer in the network and can be seamlessly integrated within any network architecture.
• We thoroughly evaluate the robustness of our method against various adversarial attacks and show that it consistently and significantly improves over the current state-of-the-art especially when combined with adversarial training.
• We show that our method successfully hardens the models against these attacks for both quantized and real-valued nets.
• We verify that our strategy works across domains, by experimenting on both image-based and audio-based classification.

heading: 2 RELATED WORK

text: In this Section, we review the related work on adversarial attacks (Section 2.1) and defences (Section 2.2), followed by an overview of tensor methods for deep learning (Section 2.3).

heading: 2.1 ADVERSARIAL ATTACKS

text:
First, we review a few of the most popular adversarial attacks alongside the current defense strategies employed. Given a data sample, e.g., an image X , an adversary will try to find a small perturbation, often imperceptible to a human eye, but that, added to the input sample, will cause it to be misclassified by the target model, with high confidence. Mathematically, the attacked generates a perturbation ∆ bounded in terms of some `p norm, i.e. ‖∆‖p ≤ , typically with p = 2 or p = ∞. The adversarial sample is obtained by adding the perturbation to the input sample Xadv = X + ∆. Several ways of obtaining this adversarial perturbations have been proposed (Goodfellow et al., 2014; Athalye et al., 2018; Carlini & Wagner, 2017). Among them, black box attacks, consider the network as a black-box in which the attacker has no information regarding its architecture or the gradients. White-box attacks on the contrary, assume complete access to the network architecture and all its parameters. Moreover, attacks can either be untargeted, in which case the goal is simply to make the network predict any wrong label, or targeted, in which case the aim is to force the network to predict a specific label, independently from the input sample. Next, we introduce the main white-box attacks used in this paper.
Fast Gradient Sign Method (FGSM) is a single-step, gradient based technique, introduced by Goodfellow et al. (2014) to generate `∞-bounded adversarial perturbations as follows:
Xadv = X + · sgn(∇XL(θ,X , y)) (1)
where θ is the parameters of the target neural network. While the single gradient-step nature of FGSM makes it better for transferability attacks, this can also lead to a suboptimal ascent direction.
Basic Iterative Method (BIM) and Projected Gradient Descend (PGD) aims to address the shortcoming of FGSM by running it for several iterations. Kurakin et al. (2016) propose BIM, in which the FGSM is run for for several iteration, clipping the values of the perturbation at each step to be inside the bounds. Madry et al. (2017) further improve upon this by prepending BIM with a random start and replacing clipping with a projection onto the acceptable set:
X t+1adv = ΠX+S(X t adv + α · sgn ( ∇XL(θ,Xtadv, y) ) , (2)
where α is the step size and ΠX+S is a projection operation forcing the generated adversarial samples to be in the `p ball S around X. A model resilient to PGD attacks is considered to be reasonably resistant to all first order attacks (Madry et al., 2017).

heading: 2.2 ADVERSARIAL DEFENCES

text:
Despite recent advances, developing robust neural networks remains an open, challenging problem (Athalye et al., 2018). Current defense strategies typically attempt to either detect the adversarial samples and denoise them, or inject adversarial samples during training. The latter is known as adversarial training (Goodfellow et al., 2014; Kurakin et al., 2016; Madry et al., 2017) and is considered the most resilient defense technique. However, the above mentioned defences typically do not increase the robustness to black box attacks. In addition they can typically be defeated using
two-step approaches (Tramèr et al., 2017). Feature squeezing is another model hardening approach introduced by Xu et al. (2017). This technique proposes to reduce the complexity of the data representation which in turn causes the adversarial perturbations to disappear due to lower sensitivity. Guo et al. (2017) proposes a set of five transformation, namely image cropping and re-scaling, bitdepth reduction, JPEG compression, pixel dropping and image quilting, that applied to the image to increase the robustness to adversarial attacks of a given model. However, even the combination of all these transformations was shown to be vulnerable to carefully tuned attacks (Athalye et al., 2018). Samangouei et al. (2018) introduces the so-called Defense-GAN technique. The main idea is to project the samples into the manifold of a generator before classifying them. Similarly, Song et al. (2017) uses a PixelCNN instead of a generative model. Despite the variety of recently proposed defence strategies, in (Athalye et al., 2018) the authors show that most of the existing defense techniques rely on one form of gradient obfuscation (gradients shattering, stochastic gradients and vanishing/exploding gradients), proposing both a method to detect such class of defences and to defeat them.
As opposed to all the aforementioned works which either manipulate the data samples (Samangouei et al., 2018; Song et al., 2017; Guo et al., 2017) or introduce stochasticity on the activations (Dhillon et al., 2018) or weights Wang et al. (2018) of each layer, we propose a novel defense strategy that leverages tensor factorization of the weights in order to apply randomization in that latent space, before reconstructing the weights the weights. The approach is introduced in details in section 3.

heading: 2.3 TENSOR METHODS IN DEEP LEARNING AND RANDOMIZED TENSOR DECOMPOSITION

text:
Tensors are high dimensional generalizations of matrices (Kolda & Bader, 2009). Recently, tensor decompositions have found a surge of applications in deep learning, mainly focusing on networks compression and acceleration. By parametrizing layers of neural networks using tensor decomposition, or even whole networks (Kossaifi et al., 2019a), the number of parameters can be reduced with little to no loss of performance, and in some cases the operations can be done more efficiently (Lebedev et al., 2015; Novikov et al., 2015; Kim et al., 2016; Astrid & Lee, 2017).
In some cases, tensor decompositions can exhibit high computational cost and possibly low convergence rates when applied to massive data. To accelerate computation, and enable them to scale, several randomized tensor decompositions have been developed. In this way, CP decomposition can be done by selecting randomly elements from the original tensor (Battaglino et al., 2018), or using randomization to solve the problem on one or several smaller tensors before projecting back the result to the original space (Erichson et al., 2017; Sidiropoulos et al., 2014; Vervliet et al., 2014). Wang et al. (2015) proposed a fast yet provable randomized CP decomposition using FFT to perform tensor contraction. Randomization approaches have also be explored for fast approximation of other tensor decompositions, e.g., Tucker decomposition via sketching (Tsourakakis, 2010; Zhou et al., 2014) and tensor ring using tensor random projections (Yuan et al., 2019).
These methods are orthogonal to our approach and can be combined with it. As opposed to the aforementioned works, which focus on compression or efficiency, we explore tensor factorization methods in the context of adversarial defense, proposing a novel approach in which the weight tensor of each convolutional layer are parametrized using a randomized tensor decomposition that significantly hardens the model, increasing its robustness to a wide range of adversarial attacks. Our method is generic and can be applied to both real-valued networks and binary ones. In addition, it is orthogonal to the existing defence methods and can be combined with existing defenses such as adversarial training. The method is introduced in details in section 3.

heading: 3 DEFENSIVE TENSORIZATION

text:
In this section, we introduce our method for the defense against adversarial attack. Our defense leverages a randomized higher-order factorization method, which is used as the basis for our defense. Typically, defensive methods relying on randomization do so by introducing sparsity in either the weights or the input activation tensors of the layers of the deep neural neural network. For instance, Dhillon et al. (2018) sparsify the input tensor, by stochastically pruning some of the activations and scaling up the remaining ones. Wang et al. (2018) apply sparsification to the weights directly using dropout both during training and testing. However, all these approaches degrade per-
formance by setting activations to zero, and, while rescaling the non-zero entries can mitigate the issue, increasing the sparsity (and therefore the efficiency of the defense) translates into large losses in performance. By contrast, we propose to rely on a latent parametrization of the layers using tensor decomposition. Intuitively, a latent subspace spanning the weights is learnt, along with a non-linear projection to and from that subspace. The sparsity inducing randomization is applied in the latent space. Upon projection, the resulting weights are dense and yet preserve the robustness against adversarial attacks. This allows us to built models that are both more robust to adversarial methods than existing works, while preserving high classification accuracy.
Notation: Throughout the papers, we denote vectors (1storder tensors) as small bold letters v, matrices (2ndorder tensors) as bold capital letters M and tensors, which generalize the concept of matrices for orders (number of dimensions) higher than 2, in capital calligraphic letters X . The n–mode product is defined, for a given tensor X ∈ RD0×D1×···×DN and a matrix M ∈ RR×Dn , as the tensor T = X ×n M ∈ RD0×···×Dn−1×R×Dn+1×···×DN , with: Ti0,i1,··· ,in = ∑Dn k=0 Min,kXi0,i1,··· ,in .
Latent high-order parametrization of the network: We introduce tensor factorization in the context of deep neural networks. Note that this method is independent of the dimensionality of the input but we introduce it here, without loss of generality, for the case of a 4 dimensional kernel of 2D convolutions. Specifically, we consider a deep neural network composed of L layers convolutional layers, interlaced with non-linearities Φl, l ∈ [1 . . L]. Let’s consider a convolutional layer l ∈ [1 . . L], taking as input an activation tensor Xl and parametrized by a weight tensor Wl ∈ RF,C,H,W , where F,C,H,W correspond respectively to number of Filters (e.g. output channels), input Channels, Height and Width of the convolutional kernel. The output of that layer, after applying non-linearity, will be Φ (Xl ?Wl). We introduce a latent parametrization of the weight kernelWl by expressing it as a low-rank tensor, in this paper using a Tucker decomposition Kolda & Bader (2009). In other words we expressWl in a latent subspace as a core tensor Gl. The mapping to and from this subspace is done via factor matrices UFl ,U C l ,U H l and U W l : Wl = Gl ×0 UFl ×1 UCl ×2 UHl ×3 UWl .
Randomizing in the latent subspace: In addition to the above deterministic decomposition, we introduce, for each layer, a randomization term stochastically controlling the rank of the decomposition. To do so, we introduce diagonal sketching matrices MF ,MC ,MH and MW , the diagonal entries of which are i.i.d. and follow a Bernoulli distribution parametrized by probability θ ∈ [0, 1]. Specifically, we samples random vectors λF ∈ RO,λC ∈ RC ,λH ∈ RH and λW ∈ RW , the entries of which are i.i.d. following a Bernoulli distribution parametrized by probability θ. We can then define the sketching matrices as MO = diag(λF ),MC = diag(λC),MH = diag(λH) and MW = diag(λW ).
This randomization is then applied not directly to the weight tensor W , but rather in the low-rank subspace, effectively randomizing the rank of the convolutional kernel:
W̃l = (Gl ×0 MF × · · · ×3 MW )︸ ︷︷ ︸ randomized core Ĝl
×0 ( UFl M > F ) × · · · ×3 ( UWl M > W )︸ ︷︷ ︸ randomized factors ÛFl ,Û I l ,Û H l ,Û W l
(3)
This stochastic reduction of the rank can be done without affecting performance thanks to the overparametrization of deep networks, which, while crucial for learning (Du & Lee, 2018; Soltanolkotabi et al., 2018), create large amounts of redundancies. In addition, since Gl ×0 MF ×0 ( UFl M > F ) =
Gl ×0 ( UFl M > FMF ) , and MF ,MI ,MH and MW are idempotent, eq. 3 can be simplified to:
W̃l = (Gl ×0 MF × · · · ×3 MW )×0 UFl × · · · ×3 UWl = G̃l ×0 UFl × · · · ×3 UWl (4) In other words, we sketch the core tensor, then project it back using the original factors. An important detail is that the randomization terms from the above equation, G̃ = G ×0 MF × · · · ×N MW is never explicitly computed using actual tensor contractions. Instead, the elements sampled are directly selected from the core and the corresponding factors, which is much more computationally effective. For the binary case, we additionally apply the process from eq. (5) by plugging in eq. (4).
The randomization being done in the latent subspace, it induces no sparsity, unlike pruning or dropout based methods and the reconstructed weights are dense. Since the weights are learnt endto-end with randomization on the latent cores, the network naturally learns not to rely on any single latent component for prediction, thus learning intrinsically more robust representations. The result is a network that is naturally more robust to perturbations in the inputs.

heading: 4 EXPERIMENTAL SETTING

text: In this section, we detail the experimental setting used for the experiments for image-based classification and audio-based classification.

heading: 4.1 DATASETS

text:
We conducted experiments on two widely used databases for image-based classification and audiobased classification, respectively:
CIFAR-10 (Krizhevsky & Hinton, 2009) is a widely used image classification dataset consisting of 60, 000 images of size 32 × 32px in 10 classes, equally represented. The dataset is divided into 50, 000 images for training and 10, 000 for testing. We did not use any particular data augmentation, beside random horizontal flipping.
Speech Command (Warden, 2018) is an audio recognition dataset comprised of 105, 000 1-second utterances of words from a large number of users spanning over a small vocabulary. The objective is to recognize among ten spoken words: yes, no, up, down, left, right, on, off, stop, go, in addition to recognizing words outside the vocabulary as unknown, and detecting silence. The dataset is balanced and all audio recordings are captured with a sampling frequency of 16 KHz. We use a 80%-10%-10% splits for training, validation and testing respectively.

heading: 4.2 IMPLEMENTATION DETAILS

text:
Training the model All our CIFAR-10 (Krizhevsky & Hinton, 2009) experiments were conducted using a ResNet-18 (He et al., 2016) architecture. The network was trained for 350 epochs using SGD with momentum (0.9) and a starting learning rate of 0.1 that was dropped at epoch 150 and 250 by a factor of 0.1. The weight decay was set to 1e − 6. In order to accelerate the training process the models with θ < 1 were initialized from a pretrained model that was trained without stochasticity (θ = 1). The binary counterpart models were trained following the method proposed by Rastegari et al. (2016) using the same optimizer and learning scheduler as for the real-valued ones. For the experiments conducted on the Speech Command dataset we build on the SoundNet5 (Aytar et al., 2016) architecture containing 5 convolutional layers [in channels, out channels, kernel, stride, padding]: [1, 16, (1×64), (1×2), (0×32)], [16, 32, (1×32), (1×2), (0×16)], [32, 64, (1×16), (1×2), (0× 8)], [64, 128, (1×8), (1×2), (0×4)], [128, 256, (1×4), (1×2), (0×2)] and 2 linear ones: [512, 256] and [256, 12]. Each convolutional layer was followed by a max-pooling operation. We trained all of the audio models using Adam (Kingma & Ba, 2014) for 50 epochs with an initial learning rate set to 0.01 that was dropped by 0.1× at epoch 25 and 35. The binarization and re-parametrization follows the same procedure as for CIFAR-10.
Attacking the model For FGSM, we run the attack for various values of = {1, 2, 4, 8, 16, 32, 64, 128} (for an image range [0 . . 255]) across the entire validation/testing set averaging the results over 10 runs. On the Speech Command dataset, since the raw data is in the range [−1, 1], we scaled the value of accordingly, running it for the following values = {0.008, 0.032, 0.063}. For the iterative methods BIM and PGD, we follow Kurakin et al. (2016) and Song et al. (2017) setting the step size to 1 and the number of iterations to bmin( + 4, 1.25 )c. Threat Model: we assume that the attacker has access to everything (e.g. the architecture of the network, its
weights, inputs, outputs, training process and gradients, etc) except the random seed used for sampling the Bernoulli random variables.
All of our models were implemented using PyTorch (Paszke et al., 2017) and trained on a single Titan X GPU. The latent, randomized tensor factorization was implemented using TensorLy (Kossaifi et al., 2019b). For the adversarial attacks we used the FoolBox (Rauber et al., 2017) package.

heading: 5 RESULTS

text:
In this section, we empirically demonstrate the robustness property of our proposed method against adversarial examples by extensively evaluating it on CIFAR-10 and comparing it against existing state-of-the-art defense techniques. Moreover, we show that our approach can be combined with adversarial training based techniques leading to further robustness gains. All the experiments are run using the experimental setup described in Section 4.
Robustness to adversarial attacks: When evaluated using the FGSM attack on the CIFAR-10 dataset our method is significantly more robust than the baseline approach, especially for high values of (see Table 1 and Fig. 1). Furthermore, the results presented in Table 1 show that for lower values of θ = 0.8, our network significantly decreases the typical high attack success-rate achieved by strong iterative attack algorithms such as BIM and PGD.
Comparison to the State-of-the-Art. To better understand the performance of our method, we compare it against existing state-of-the-art defense techniques such as: DQ (Lin et al., 2019) in which the authors attempt to reduce the propagation of the adversarial attacks inside the network by controlling the Lipschitz constant, features squeezing (Xu et al., 2017) that simple reduces the dimensionality of the search space by controlling the color bit depth of each pixel while applying spatial smoothing and finally, adversarial training in two variants: R+FGSM as proposed in (Lin et al., 2019) and PGD (Madry et al., 2017). Where the later (i.e. adversarial training) is considered to be one of the strongest defence techniques developed. For feature-squeezing we used 5 bits for image color reduction combined with a 2 × 2 median filter. For adversarial training as in (Madry et al., 2017; Kurakin et al., 2016) we sample the number of steps (for PGD) and randomly. As the results from Table 2 show, our method consistently outperforms existing defense strategies for various attacks (FGSM, BIM, PGD), across different values of = {2, 8, 16}. Furthermore, when combined with adversarial training our method can further increase its resilience to attacks.
Defending against omniscient attackers Another interesting question is whether our defense strategy would still work against an omniscient attacker, i.e., an attacker with access to the full unrandomized weights. We trained a network for θ = 0.9. Then, during training, we first generate an adversarial example using the full, un-randomized weights (i.e. θ = 1) and test it using the stochasticity (i.e. θ = 0.9). As can be seen in Table 3, our network is still robust against these
attacks, despite the attacker having full access to the weights. Similar behaviour can be observed for other values of θ. Note that this is an extreme scenario and in general, the weights could be stored separately (and safely) with the network getting, at each time, the randomly reconstructed weights.
6 ABLATION STUDIES
To further validate our findings we test out approach on two different scenarios: on fully binarized networks (Section 6.1) and audio classification task (Section 6.2).

heading: 6.1 ATTACKING BINARY NEURAL NETWORKS

text:
With the growing popularity of deep learning based methods and the constant need of incorporating such approaches on mobile devices, network quantization has emerged as a potential hardware-friendly solution, which squeezes the original network by reducing the number of bits required to represent the model parameters. In its most extreme form, binarization, the weights and features are represented using a single bit (Courbariaux et al., 2016; Rastegari et al., 2016; Bulat & Tzimiropoulos,
2017). The typical approach quantizes the network using the sign function (Courbariaux et al., 2015), however this introduces high quantization errors that hinder the learning process. To alleviate this, a real-valued scaling factor is introduced by Rastegari et al. (2016). In this work we binarize the network following Rastegari et al. (2016):
I ∗W = (sgn(I)©∗ sgn(W)) Kα, (5) where I ∈ Rc×win×hin andW ∈ Rc×h×w denote the input and respectively the weight of the L-th convolutional layer, α ∈ Rc×1×1 represent the weight scaling factor and K ∈ R1×hout×wout the input scaling factor. Both α andK are computed analytically as proposed by Rastegari et al. (2016). While it was previously thought that such binarized networks are more resilient to adversarial attacks (Khalil et al., 2018; Liu et al., 2018; Galloway et al., 2017) than their real-valued counterpart, in this work we confirm the recent findings of (Lin et al., 2019) by showing that in fact it is the opposite, i.e., binary networks are more susceptible to adversarial attacks. Typically, during the training phase the derivative of the quantization function (sgn) is approximated using a STE (e.g., an identity function clipped to [−1, 1] in this case). The same estimator can be used during the attacking phase and it often leads to a high rate of success of the attacks. Interestingly, the results in Table 4 show that we can go one step further by approximating the derivative of the sgn function using tanh(x) and tanh(0.75 ∗ x) respectively. The use of these approximations make the binary networks become more sensitive to the attacks. When evaluated on a binary network on the CIFAR-10 dataset, in accordance with the behaviour found on real-valued models, our method shows significant improvements across the entire range of values and attacks tested (see Table 4 and Fig. 1). We note that for the binary case, since such networks have a lower representational capacity, we set θ = 0.99.

heading: 6.2 DEFENSIVE TENSORIZATION FOR AUDIO CLASSIFICATION

text: To further demonstrate the generalizability of our approach, we next consider adversarial attacks on the audio domain. In-line with the latest success in audio recognition, we consider an end-to-end audio model following SoundNet (Aytar et al., 2016) architecture, that operates directly on the raw audio signal, without requiring any feature extractions (e.g., MFCC or log mel-spectrogram). We found that the end-to-end models show higher degree of vulnerability to the adversarial attacks, e.g., around 6% absolute degradation compared to the model operating on log mel-spectrogram. In case of the small vocabulary audio recognition task, we only consider FGSM attack and summarize our findings in Table 5. With a higher degree of stochasticity (i.e. θ = 0.9), both the real and the binarized model exhibit much higher resilience to the adversarial attacks.

heading: 7 CONCLUSION

text: In this paper, we propose defensive tensorization, a novel adversarial defence technique that leverages a latent high order factorization of the network. Randomization is applied in the latent subspace, therefore resulting in dense reconstructed weights, without the sparsity or perturbations typically induced by the randomization. We empirically demonstrate that our approach makes the network significantly more robust to adversarial attacks. Contrarily to a widely spread belief, we observe that binary networks are more sensitive to adversarial attacks than their real-valued counter-part. We show that our method significantly improves robustness in the face of adversarial attacks for both binary and real-valued networks. We demonstrate this empirically through thorough experimentation on image and audio classification.

heading: A APPENDIX

text:
Algorithm for defensive tensorization We summarize in Algorithm. 1 the steps for inference using our proposed defensive tensorization.
Algorithm 1 Defensive tensorization 1: Input sample X0. 2: for each layer l do 3: Sample random vector λF , · · · ,λW ∼ Bernouilli (θ) 4: Create sketch matrices MF = diag(λF ), · · · ,MW = diag(λW ) 5: Sketch the latent Core G̃l = Gl ×0 MF × · · · ×3 MW 6: ReconstructWk using Equation (3) . Randomized dense reconstruction 7: Xl+1 ← Φl(Wl ? Xl) . Convolve Xl with the randomized reconstruction and apply Φl 8: return XL
Low-dimensional visualization of loss landscape: To visually assess the impact of both our randomization scheme and adversarial training on the optimization landscape, we visualise the evaluation of the loss in a fixed neighbourhood around an unseen data point. Specifically, given a model and a data point x, we visualize the loss function learned by the model in the close proximity of x. For clarity, we visualise the loss in a 2–dimensional space, by selecting the two relevant axis: the direction of the gradient at x (x-axis) and a randomly chosen direction, orthogonal to the direction of gradient (y-axis). Next, a mesh-grid is constructed by sampling uniformly points along these two directions for the range [−0.5, 0.5]. Then a contour plot is constructed by evaluating the losses for all points on the mesh-grid. Examples of loss-surfaces are shown in Fig. 2, 3 and 4.
Effect on the optimization landscape: Intuitively, the randomization (which is done in the latent subspace of the decomposition, not on the weights themselves), changes the loss function, at each pass, making it hard to converge to a fixed attack due to the presence of many spurious minimums. This can be seen by looking at the landscape of the loss function around an arbitrary sample in Fig. 2, 3. For the adversarial case, the landscape is inline with the finding of Madry et al. (2017), where the authors show the adversarial training smooths the loss space around 0. This is even more noticeable for the method that combines our approach with adversarial training (see Fig. 4).

title: DEFENSIVE TENSORIZATION: RANDOMIZED TENSOR PARAMETRIZATION


summaries: This paper proposes a clustering attention-based approach to handle the problem of unsmoothness while modeling spatio-temporal data, which may be divided into several regions with unsmooth boundaries. With the help of a graph attention mechanism between vertices (which correspond to different regions), the CGT model is able to model the (originally unsmooth) cross-region interactions just like how Transformers are applied in NLP tasks (where words are discrete). Experiments seem to suggest a big improvement when compared to baselines.

summaries: In this paper, the authors developed a neural network architecture to address the spacial and temporal unsmoothness problem, which was claimed to be neglected by existing works. The proposed model, CGT, has an encoder-decoder structure, and is characterized by clustering modules for spacial regions based on their temporal patterns. To handle temporal unsmoothness, additivity-preserved multi-view position encoding was proposed to characterize different temporal relationships. The experimental results on real ride-hailing datasets demonstrate the effectiveness of the proposed method to some extent.

abstractText: Deep learning based approaches have been widely used in various urban spatiotemporal forecasting problems, but most of them fail to account for the unsmoothness issue of urban data in their architecture design, which significantly deteriorates their prediction performance. The aim of this paper is to develop a novel clustered graph transformer framework that integrates both graph attention network and transformer under an encoder-decoder architecture to address such unsmoothness issue. Specifically, we propose two novel structural components to refine the architectures of those existing deep learning models. In spatial domain, we propose a gradient-based clustering method to distribute different feature extractors to regions in different contexts. In temporal domain, we propose to use multi-view position encoding to address the periodicity and closeness of urban time series data. Experiments on real datasets obtained from a ride-hailing business show that our method can achieve 10%-25% improvement than many stateof-the-art baselines.

authors:
James Atwood
Don Towsley

title: Diffusion-convolutional neural networks

venue: In Advances in Neural Information Processing Systems,

authors:
Dzmitry Bahdanau
Kyunghyun Cho
Yoshua Bengio

title: Neural machine translation by jointly learning to align and translate

venue: International Conference on Learning Representations (ICLR),

authors:
Antoni Buades
Bartomeu Coll
J-M Morel

title: A non-local algorithm for image denoising

venue: IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05),

authors:
Rewon Child
Scott Gray
Alec Radford
Ilya Sutskever

title: Generating long sequences with sparse transformers

authors:
Daizong Ding
Mi Zhang
Xudong Pan
Min Yang
Xiangnan He

title: Modeling extreme events in time series prediction

authors:
David K Duvenaud
Dougal Maclaurin
Jorge Iparraguirre
Rafael Bombarell
Timothy Hirzel
Alán Aspuru-Guzik
Ryan P Adams

title: Convolutional networks on graphs for learning molecular fingerprints

venue: In Advances in neural information processing systems,

authors:
Xu Geng
Yaguang Li
Leye Wang
Lingyu Zhang
Qiang Yang
Jieping Ye
Yan Liu

title: Spatiotemporal multi-graph convolution network for ride-hailing demand forecasting

venue: In Proceedings of the AAAI Conference on Artificial Intelligence,

authors:
Shengnan Guo
Youfang Lin
Ning Feng
Chao Song
Huaiyu Wan

title: Attention based spatialtemporal graph convolutional networks for traffic flow forecasting

authors:
Will Hamilton
Zhitao Ying
Jure Leskovec

title: Inductive representation learning on large graphs

authors:
David K Hammond
Pierre Vandergheynst
Rémi Gribonval

title: Wavelets on graphs via spectral graph theory

venue: Applied and Computational Harmonic Analysis,

authors:
Guolin Ke
Qi Meng
Thomas Finley
Taifeng Wang
Wei Chen
Weidong Ma
Qiwei Ye
TieYan Liu

title: Lightgbm: A highly efficient gradient boosting decision tree

authors:
Thomas N Kipf
Max Welling

title: Semi-supervised classification with graph convolutional networks

authors:
Qimai Li
Zhichao Han
Xiao-Ming Wu

title: Deeper insights into graph convolutional networks for semi-supervised learning

authors:
Yaguang Li
Rose Yu
Cyrus Shahabi
Yan Liu

title: Diffusion convolutional recurrent neural network: Data-driven traffic forecasting

authors:
Yexin Li
Yu Zheng

title: Citywide bike usage prediction in a bike-sharing system

venue: IEEE Transactions on Knowledge and Data Engineering,

authors:
Yujia Li
Daniel Tarlow
Marc Brockschmidt
Richard Zemel

title: Gated graph sequence neural networks

venue: arXiv preprint arXiv:1511.05493,

authors:
Yuxuan Liang
Songyu Ke
Junbo Zhang
Xiuwen Yi
Yu Zheng

title: Geoman: Multi-level attention networks for geo-sensory time series prediction

venue: In IJCAI,

authors:
Binbing Liao
Jingqing Zhang
Ming Cai
Siliang Tang
Yifan Gao
Chao Wu
Shengwen Yang
Wenwu Zhu
Yike Guo
Fei Wu

title: Dest-resnet: A deep spatiotemporal residual network for hotspot traffic speed prediction

venue: ACM Multimedia Conference on Multimedia Conference,

authors:
Lei Lin
Zhengbing He
Srinivas Peeta

title: Predicting station-level hourly demand in a large-scale bike-sharing network: A graph convolutional neural network approach

venue: Transportation Research Part C: Emerging Technologies,

authors:
Ding Liu
Bihan Wen
Yuchen Fan
Chen Change Loy
Thomas S Huang

title: Non-local recurrent network for image restoration

authors:
Zheyi Pan
Yuxuan Liang
Weifeng Wang
Yong Yu
Yu Zheng
Junbo Zhang

title: Urban traffic prediction from spatio-temporal data using deep meta learning

venue: In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,

title: Automatic differentiation in pytorch

authors:
Filipe Rodrigues
Ioulia Markou
Francisco C Pereira

title: Combining time-series and textual data for taxi demand prediction in event areas: A deep learning approach

venue: Information Fusion,

title: Dynamic time warping algorithm review

venue: Information and Computer Science Department University of Hawaii at Manoa Honolulu, USA,

authors:
Hongzhi Shi
Quanming Yao
Qi Guo
Yaguang Li
Lingyu Zhang
Jieping Ye
Yong Li
Yan Liu

title: Predicting origin-destination flow via multi-perspective graph convolutional network

venue: IEEE 36th International Conference on Data Engineering (ICDE),

authors:
Xingjian Shi
Dit-Yan Yeung

title: Machine learning for spatiotemporal sequence forecasting: A survey

venue: arXiv preprint arXiv:1808.06865,

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N Gomez
Łukasz Kaiser
Illia Polosukhin

title: Attention is all you need

authors:
Dong Wang
Wei Cao
Jian Li
Jieping Ye

title: Deepsd: supply-demand prediction for online carhailing services using deep neural networks

venue: IEEE 33rd International Conference on Data Engineering (ICDE),

authors:
Menglin Wang
Baisheng Lai
Zhongming Jin
Xiaojin Gong
Jianqiang Huang
Xiansheng Hua

title: Dynamic spatio-temporal graph-based cnns for traffic prediction

venue: arXiv preprint arXiv:1812.02019,

authors:
Senzhang Wang
Jiannong Cao
Philip S Yu

title: Deep learning for spatio-temporal data mining: A survey

venue: arXiv preprint arXiv:1906.04928,

authors:
Xiaolong Wang
Ross Girshick
Abhinav Gupta
Kaiming He

title: Non-local neural networks

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

authors:
Ying Xu
Dongsheng Li

title: Incorporating graph attention and recurrent architectures for city-wide taxi demand prediction

venue: ISPRS International Journal of Geo-Information,

authors:
Huaxiu Yao
Fei Wu
Jintao Ke
Xianfeng Tang
Yitian Jia
Siyu Lu
Pinghua Gong
Jieping Ye
Zhenhui Li

title: Deep multi-view spatial-temporal network for taxi demand prediction

venue: In ThirtySecond AAAI Conference on Artificial Intelligence,

authors:
Zhitao Ying
Jiaxuan You
Christopher Morris
Xiang Ren
Will Hamilton
Jure Leskovec

title: Hierarchical graph representation learning with differentiable pooling

authors:
Junbo Zhang
Yu Zheng
Dekang Qi
Ruiyuan Li
Xiuwen Yi

title: Dnn-based prediction model for spatio-temporal data

venue: In Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems,

authors:
Junbo Zhang
Yu Zheng
Dekang Qi

title: Deep spatio-temporal residual networks for citywide crowd flows prediction

venue: In Thirty-First AAAI Conference on Artificial Intelligence,

authors:
Lingyu Zhang
Wei Ai
Chuan Yuan
Yuhui Zhang
Jieping Ye

title: Taxi or hitchhiking: Predicting passenger’s preferred service on ride sharing platforms

venue: In The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval,

authors:
Yu Zheng
Licia Capra
Ouri Wolfson
Hai Yang

title: Urban computing: concepts, methodologies, and applications

venue: ACM Transactions on Intelligent Systems and Technology (TIST),

authors:
Jie Zhou
Ganqu Cui
Zhengyan Zhang
Cheng Yang
Zhiyuan Liu
Lifeng Wang
Changcheng Li
Maosong Sun

title: Graph neural networks: A review of methods and applications, 2018

heading: 1 INTRODUCTION

text:
The aim of this paper is to use urban data to study spatio-temporal prediction problems, whose goal is to forecast region-based spatial distribution in the future (Shi & Yeung, 2018; Wang et al., 2019). Recently, region-based spatio-temporal forecasting has been extensively studied with various applications in traffic (Li et al., 2018b), ride-hailing services (Zhang et al., 2018; Li & Zheng, 2019), environment (Liang et al., 2018), resources (Li & Zheng, 2019), and human flows (Wang et al., 2019; Shi et al., 2020), among others. Such spatio-temporal forecasting is crucial for various tasks, such as dispatching and pricing, in urban computing (Zheng et al., 2014). Accurate spatiotemporal forecasting methods may not only lower the barrier for decision making, but also improve the quality of various services including traffic management, transportation, and air quality management. However, achieving accurate prediction represents major challenges for many existing methods due to some difficulties in urban data, such as unsmoothness.
As an illustration, we will show throughout the paper that urban spatio-temporal prediction task suffers from not appropriately handing spatial and temporal unsmoothness. Unsmoothness is a common phenomenon in many spatial and/or temporal data sets. The observations in some locations/time-steps differ substantially from the observations in their neighboring locations/time-steps. For example, rush-hour traffic surge is temporally unsmoothed, while it occurs in many regions in a city. Figure 1 shows potential spatial unsmoothness due to different points of interest. Specifically, S1, S2 and S3 denote business, residential, and recreational areas, respectively, whereas U1, U2, and U3 are their boundaries. Traffic observations in the interior areas of S1, S2 and S3 may be quite close to each other, whereas observations along U1, U2, and U3 may have much larger variations. Figure 2 shows 24-hour temporal patterns in the spatial neighborhood of a selected smooth
region (2a) and a selected unsmooth region (2b). The temporal patterns for the smooth region are
close to those of most of their closest neighbors except the region with yellow color 1 in terms of shape and magnitude. The temporal patterns of the unsmooth region differ more significantly from those in all his closest neighbors. Moreover, we also discover some sharp surge and drop patterns in the unsmooth region. For more quantitative metrics for measuring unsmoothness, please refer to Appendix A for details.
However, the attempt to handling unsmoothness is quite limited both at model and feature levels. Many existing prediction methods share their spatial and temporal feature extractors universally across all time-steps and/or all regions. Thus, it greatly limits the expressiveness of those prediction methods, since they are greatly vulnerable to the presence of unsmoothness in urban data.
In this paper, we develop a novel Clustered Graph Transformer (CGT) framework by integrating Graph Attention Network (GAT) (Veličković et al., 2018) with Transformer (Vaswani et al., 2017) based on a unified attention encoder-decoder architecture (Bahdanau et al., 2015). The GAT and Transformer are effective methods for spatial and temporal feature extraction based on attention mechanism. To handle spatial unsmoothness, we develop a novel Clustered Graph Attention Network (CGAT) by leveraging different graph attention kernels on different regions. The CGAT learns clustering assignments for each region according to their temporal patterns so that regions with different temporal patterns are assigned with different spatial feature extractors. To handle temporal unsmoothness, we propose additivity-preserved multi-view position encoding (MVPE) by characterizing different kinds of temporal relationship including weekly or daily periodicity and temporal closeness (Zhang et al., 2017). In summary, our major contributions are summarized as follows:
• To the best of our knowledge, CGT is the first of its kind in using graph attention network with a transformer under an encoder-decoder architecture for long sequence spatiotemporal forecasting.
• We propose to improve the expressiveness of spatial feature extraction using the clustering technique. We also handle the temporal unsmoothness by using MVPE, which is a tailored position encoding for urban computing.
• Compared with most existing baseline models, CGT achieves improvement ranging from 10% to 25% in spatiotemporal prediction on various tasks, datasets and cities. Error reduction on unsmooth areas dominates this improvement.
1Except region 1. Details are in section 4.3

heading: 2 METHODOLOGY

text: We formalize the learning problem of urban spatiotemporal forecasting and introduce the CGT framework to capture the spatial and temporal dependencies and unsmoothness of urban data.

heading: 2.1 URBAN SPATIOTEMPORAL FORECASTING

text:
We consider urban spatiotemporal forecasting problems in a city. Suppose that the city can be divided into V disjoint regions and we observe temporal information across T time intervals within each region. Our spatio-temporal data is represented as a |V | × T matrix. As an example, we consider taxi demand forecasting problem and each entry in the matrix represents the total number of taxi orders inside a region within a specific time interval. Our prediction problem is formulated as f : R|V |×Tx → R|V |×Ty such that we use the historical data within time period Tx to predict the future trend in time period Ty , that is,
Xt−Tx+1:t = [X t−Tx+1, . . . , Xt] f(·)−−→ Xt+1:t+Ty = [Xt+1, . . . , Xt+Ty ]. (1) Problem (1) is a one-step prediction problem as Ty = 1 and a multi-step prediction problem as Ty > 1. We regard the whole city as a graph with V regions (or vertices), each of which has both demand and supply numbers across T time intervals.

heading: 2.2 FRAMEWORK OVERVIEW

text:
Figure 3 shows the overview of the CGT framework. The CGT is an encoder-decoder based architecture. The clustered graph attention layers (CGAT) and temporal attention layers are stacked alternately in the encoder and decoder. For prediction problem (1), the input tensor to encoder is Xt−Tx+1:t. In the training phase, the whole target sequence Xt:t+Ty is input to the decoder and the masked attention controls the visibility of target sequence in each step of decoding. The Xt is used to initialize the decoder state at the initial decoding step. In the testing phase, at step Ts (Ts ≤ Ty), the decoder input tensor is [Xt, X̂t+1:t+Ts ], where X̂ represents predicted values from previous steps. The multi-view position encoding (MVPE) is added to input tensors in both encoder and decoder.
Our key novel contribution in CGT lies in the design and use of CGAT and MVPE. On spatial mode, CGAT integrates self-clustering and a set of graph attention kernels (GAT), which are used for region clustering and spatial feature extraction, respectively. CGATs firstly generate soft clustering assignment scores for regions according to their temporal pattern in the sampled period. The cluster scores are used as the weights to apply different GATs to each region. On temporal mode,
we use multi-view position encoding (MVPE) to manually inject ordering information, periodicity information, and closeness information to the model.

heading: 2.3 MULTI-VIEW POSITION ENCODING

text:
We design a multi-view position encoding mechanism (MVPE) for urban computing. The position encoding consists of five channels as follows. There are two channels for weekly periodicity given by
PE1(x) = (1 + sin(2πx/7))/2 and PE2(x) = (1 + cos(2πx/7))/2.
There are two channels for daily periodicity given by
PE3(x) = (1 + sin(2πx))/2 and PE4(x) = (1 + cos(2πx))/2.
There is one channel for closeness given by
PE5(x) = exp(−ax2),
where x represents the temporal difference between a fixed timestep (e.g. the time t+1 in formulation (1)) and a specific timestep in inputs or outputs.
The MVPE mechanism injects ordering information and relevance information to the temporal modeling. First, MVPE provides unique identifiers for all time-steps in temporal sequences, which is critical for non-recurrent to model sequences. Second, according to Zhang et al. (2016), the weekly and daily periodicity, as well as closeness are considered to be highly important in modeling urban time series. The periodicity channels provide constant crest/trough values for timesteps spanned by an integer number of periods. The closeness channel provides a surging value for the nearby timesteps. The model will be trained to make predictions according to different temporal relevance to avoid making over-smoothing ones.

heading: 2.4 CLUSTERED GRAPH ATTENTION

text:
We propose the clustered graph attention layer (CGAT) for spatial feature extraction. It learns different graph attention kernels for different regions based on a gradient-based self-clustering assignment such that different regions are treated differently in spatial dependency modeling.
First, a vertex-level soft-assignment to K clusters is learnt from the temporal pattern of each vertex:
C = σs(σr(XfWf )tWt), (2)
where C is the cluster assignment score for each vertex to K clusters. Wf and Wt are parameters for linear layers on the feature mode and temporal mode, respectively, and σr and σs represent the relu and softmax activation functions. The feature dimension of input tensor Xf is first squeezed to 1 using Wf , in order to provide summarized temporal pattern at each vertex. The Wt is further applied to the temporal pattern to calculate a K−dimensional cluster assignment score. Second, we use cxi,k to denote the assignment score of C for assigning vertex xi to cluster k. Then, C is used to re-weight the latent output by using K GATs as follows:
hxi = K∑ k=0 G(xi)cxi,k, (3)
where hxi is the summed output for a CGAT layer at vertex xi and Gθk(xi) is the output for each GAT at vertex xi. We use the GAT defined by Veličković et al. (2018). The attention between two vertex xi and xj is calculated as:
αi,j = exp(σ(aT [Wxi||Wxj ]))∑
xm∈Nxi exp(σ(aT [Wxi||Wxm]))
, (4)
where W and aT are network parameters, Nxi represents the neighborhood of region xi, [·||·] is the concatenation operation, and σ(·) is the Leakyrelu activation function. The aggregation function for GAT is given by G(xi) = σ( ∑ xj∈Ni αi,jWxj).

heading: 2.5 TEMPORAL ATTENTION AND TRANSFORMER

text: The temporal features are extracted by adapting the multi-head attention model to the temporal mode of spatio-temporal tensor (Vaswani et al., 2017). Detailed information is included in Appendix C.

heading: 2.6 OPTIMIZATION OBJECTIVE

text:
The optimization objective of CGT consists of two major components. The first component is the prediction error given by Lpred = ||y − ŷ||2, (5) where || · ||2 the standard L2 norm and ŷ and y are, respectively, the tensor of predicted values and that of true values.
The second component consists of three constraints for obtaining a good vertex cluster schema C. Let the clustering result C = (Cb,l,v,k) be a tensor of order (B,L, V,K), where B is the batch size, L is the number of all CGAT layers, V is the number of vertices, and K is the cluster number. Thus, Cb1,l1,·,· denotes a V × K matrix and Cb,l,v,· is a K × 1 vector. The three constraints including consistency, purity, and diversity are summarized below.
• Consistency: The clustering assignment is generated through the temporal pattern of each vertex such that C should be temporally (batch) invariant and layer invariant. The loss function for ensuring consistency is defined as
Lc = 4 BL(B − 1)(L− 1)V 2 B−1∑ b1=1 B∑ b2=b1+1 L−1∑ l1=1 L∑ l2=l1+1 ||Cb1,l1,·,· − Cb2,l2,·,·||22. (6)
• Purity: Ideally, each vertex should be only assigned to one cluster. The loss function for encouraging purity is given by
Lp = 1
BLV B∑ b=1 L∑ l=1 V∑ v=1 (1− ||Cb,l,v,·||22). (7)
• Diversity: To balance the cluster size, we define the loss function for ensuring diversity as follows:
Ld = 1
BLV 2 B∑ b=1 L∑ l=1 || V∑ v=1 Cb,l,v,·||22. (8)
The overall minimization goal is to minimize the following object function
L = Lpred + α(Lc + Lp + Ld), (9) where α is a tuning parameter. It is worth noting that each batch consists of training snippets within a continuous short period of time (e.g., several hours). Keeping the clusters stable by using above regularizations allows to capture the short-term stability of urban time series data, while it does not violate the daily or long-term variability. We verify this short-term stability feature in Appendix B.

heading: 2.7 APPLICATION-LEVEL ADAPTATIONS

text:
Several state-of-the-art techniques need to be considered for improving our implementation and evaluation on real-world applications. First, we construct a set of graphs G = {G1, G2, G3} as the graph adjacency matrix, each of which represents region-wise distance, region-wise functional similarity and region-wise road connectivity, respectively. It follows the idea of Geng et al. (2019) in order to encode multiple region-wise relationships as multi-graphs for the better utilization of auxiliary data. Second, following Child et al. (2019), we implement spatial atrous attention to reduce the extra large spatial dimension in order to reduce the computational cost for CGATs.
Denoting atrous stride and atrous offset as s and a, the atrous version of eq.(4) is revised to be:
αi,j,g,s,a = exp(σ(aTg [Wgxi||Wgxj ]))Is,a(j)∑
xm∈Nxi exp(σ(aTg [Wgxi||Wgxm]))Is,a(m)
, (10)
where aTg and Wg denote the feature transformation operation for graph g. Is,a(·) is a masking function for atrous attention:
Is,a(j) = { 1 if j mod s = a; 0 otherwise.
To cover all the regions, atrous-GAT needs to traverse a = 0, · · · , s − 1 by in-layer aggregation. The aggregated atrous-GAT output under single graph g ∈ G is calculated as:
Gg(xi) = σ( s−1∑ a=0 ∑ xj∈Ni αi,j,g,s,aWxj). (11)
Each GAT outputs an aggregated output over multi-graph given by G(xi) = ∑ g∈G Gg(xi)/|G|. The regularizers in eq.(6)-(8) are calculated separately for multi-graph and finally averaged for calculating the loss.

heading: 3 RELATED WORK

heading: 3.1 SPATIOTEMPORAL DEEP LEARNING

text: There have been various ways to model the spatial and temporal dependencies with deep neural networks. The combination of CNN and RNN is the most intuitive one (Yao et al., 2018; Zhang et al., 2017; Wang et al., 2017; Liao et al., 2018; Rodrigues et al., 2019). However, CNN-based architectures are unable to handle non-Euclidean region-wise relationships. The STMGCN (Geng et al., 2019), DCRNN (Li et al., 2018b) and GCNN-DDGF (Lin et al., 2018) use ChebNet (Kipf & Welling, 2017) and diffusion convolution to extract spatial features based on rather complex graph representations. The graph attention network (Veličković et al., 2018) is the third generation of spatial modeling, which has more complex structures for discovering region-wise relationships. The ST-MetaNet (Pan et al., 2019) is a representative work of GAT with application in urban computing. In temporal feature extraction, attention-based methods outperform RNNs in terms of both accuracy and efficiency. The ASTGCN (Guo et al., 2019) is an attention-based model on both spatial and temporal domains. The GeoMAN (Liang et al., 2018) further adapts the attention-based model to encoder-decoder architecture for long sequence prediction. However, all existing methods neglect the unsmoothness problem of urban data.

heading: 3.2 GRAPH NEURAL NETWORKS

text: The research works on graph neural networks could be summarized in several categories (Zhou et al., 2018). Spectral graph convolution (Hammond et al., 2011; Kipf & Welling, 2017) defines convolution operator by the eigen-decomposition of the graph laplacian, based on the graph spectral theorem. Non-spectral graph convolution (Duvenaud et al., 2015; Atwood & Towsley, 2016; Hamilton et al., 2017) directly operates the spatial domain by defining a set of neighborhood aggregation and updating rules on vertex-level. Moreover, the gated GNN (Li et al., 2015) leverages the gating technique from LSTM, which provides more complex operations for neighborhood aggregation. GAT (Veličković et al., 2018) is using attention mechanism to discover the vertex-wise similarities in a graph. In urban computing, the intuition is confident that regions are strongly correlated. The GAT might help to discover this intrinsic structure in the region-based spatial distribution.

heading: 3.3 VERTEX CLUSTERING AND GRAPH POOLING

text: Vertex clustering is a frequently used method for graph pooling (Ying et al., 2018), which is a common technique migrated from computer vision. However, the intuition for graph pooling and vertex clustering proposed in this work is different. Graph pooling is to reduce the number of vertices such that vertices in each cluster are regarded sampled into one in the next layer. Downscaling the graph layer would improve model generality and reduce computational cost. The vertex clustering in our approach is to discover a set of vertices sharing similar patterns, which is used for better feature extraction.

heading: 3.4 HANDLING UNSMOOTHNESS IN MACHINE LEARNING

text: Non-local mean methods are proposed for image denoising and restoration by investigating the pixel-level self-similarity in images. Buades et al. (2005) proposed to calculate pixel pair-wise similarity within a large search window. The densities for noisy pixels are interpolated by those similar pixels. Wang et al. (2018b),Liu et al. (2018) designed non-local neural networks to incorporate the similar idea in deep learning. However, these non-local mean methods are applied to fix part of the spatial distribution at corrupted areas, which is different from our problem formulation. In time series prediction, Ding et al. (2018) proposed a extreme-value loss (EVL) for extreme event prediction in time series data. Compared with our method, EVL has no model-level effort to extract unsmooth features from data, which totally relies on the success of optimization algorithm.

heading: 4 EXPERIMENTS

text: We conduct experiments on a demand/supply dataset for ride-hailing services in two cities A and B 2 from Jun 2017 to Jun 2019. The demand data is the number of ride-hailing orders in each region within each time interval. The supply data is the summation of online duration for all ridehailing drivers. The spatial and temporal distribution is sampled and aggregated into 1km×1km map gridding and 30 minutes temporal sampling interval3. For both datasets, we cut off the long tail on the 95th quantile and normalize them by min-max normalization. The duration of the dataset is two years, where first 70% is used for training, 10% for validation, and remaining 20% for test. The multi-graph G involves region-wise relationships including neighborhood, functional similarity, and road connectivity, which are identical to those used in (Geng et al., 2019). The functional similarity graph is binarized on 0.9 so that three graphs have almost equal graph sparsity4.

heading: 4.1 OVERALL PERFORMANCE

text:
In this section, the encoder and decoder both stack 3 CABs and TABs alternately, with 16 hidden states each. The default clustering number is 3, with atrous stride being equal to 2. The number of heads in TAB multi-head attention is set to be 3. The network is optimized by using scheduled Adam on PyTorch (Paszke et al., 2017).
We conduct both one-step prediction and multi-step prediction experiments. To avoid the long sequence problem, which may exhaust computational resource, we sampled 10 input time-steps for each output time-step Tk. The input time-steps include 3 closest time-steps (Tk−1, Tk−2, Tk−3), 2 from daily periodicity (Tk−48, Tk−96) and 1 from weekly periodicity (Tk−48∗7). For multi-step prediction, the default output length is 8, the encoder input length is 27.
2Anonymous for blind review. 3Designed according to industrial practices 4In city A, it is roughly 12000 edges for 1296 vertices.
Baselines are built based on following research works. For the sake of information fairness, all deep learning models are slightly revised to take in multiple graphs.
• HA, LR and XGBoost: Historical average, linear regression and XGBoost. The model parameters for LR and XGBoost are shared across space and time. XGBoost is implemented using LightGBM (Ke et al., 2017).
• DMVST (Yao et al., 2018): a CNN-RNN based model. Region-wise relationships are encoded as external inputs.
• DCRNN (Li et al., 2018b) and ST-MGCN (Geng et al., 2019): Both are GCN-RNN based model for spatiotemporal feature extraction. DCRNN is based on encoder-decoder architecture for multi-step traffic prediction.
• GeoMAN (Liang et al., 2018): The spatial and temporal features are extracted by spatial attention and RNN. It is based on the encoder-decoder architecture.
• ASTGCN (Guo et al., 2019): an attention-based model on spatial and temporal domain. Spatiotemporal features are extracted using GCN and convolution. ASTGCN don’t have position encoding.
• DST-GCNN 5(Wang et al., 2018a): A two stream framework for traffic prediction. The first stream constructs dynamic affinity graph. The second stream use the graph and spatiotemporal convolution for feature extraction.
• GAT+RNN 5(Xu & Li, 2019): a GAT+RNN structure for traffic forecasting.
Table 1 summarizes the RMSEs and MAPEs of CGT and state-of-the-art baselines. There are few observations from above experiment results. First, the proposed CGT model outperforms all baselines in all prediction tasks by a large margin. Second, all encoder-decoder based models, including m-DCRNN, m-GeoMAN and CGT, perform well in all multi-step prediction tasks.

heading: 4.2 ABLATION STUDY AND PARAMETER TEST

text:
In this section, we show the experiment results of CGT on the one-step demand prediction problem in city A with varying model configurations to show the parameter effect. As shown by figure 4, the optimal result is achieved when α = 0.1 and k = 3. Table 2 shows the model performance when specific component is removed from CGT. The ablation study shows the significance of our novel contribution.
5Made-up experiment according to reviewer’s comments. Unfinished due to time limit.

heading: 4.3 MODEL INTERPRETATION

text:
We claim that the prediction error is reduced due to more accurate predictions in spatial and temporal unsmooth areas. To validate this, we explore the relationship between the unsmoothness and the error reduction from a baseline model. The baseline model is designed by removing clustering and MVPE from CGT. Figure 5 shows a positive relationship between unsmoothness and error reduction. Table 3 shows the error reduction from the baseline model on different quantiles of spatial and temporal unsmooth areas. Conclusions could be drawn that CGT could improve the prediction performance, especially in spatial and temporal unsmooth areas by significant margins.
Above improvements on spatial mode may be caused by the effective clustering technique, which applies different spatial kernels to regions with different patterns. Referring back to Figure 2, the neighbor 1 (yellow line) in Figure 2a is an unsmooth point in the neighborhood. It is assigned to the same cluster with the target region (blue line) in Figure 2b, which is also an unsmooth region. The remaining regions in Figure 2a stay in the same cluster. According to above case study, the temporal pattern for inner-cluster regions are similar, while the temporal pattern for intra-cluster regions are diverse. It is sensible to apply a shared operator to target regions in a single cluster, since the relationship between target regions and their neighbors are more stable within a cluster. However, applying one smoothing operator to different clusters does not work very well, since it may introduce some artifacts. In conclusion, discriminating smooth and unsmooth patterns may greatly improve the local spatial feature extraction.

heading: 5 CONCLUSION AND FUTURE WORK

text: In this paper, we proposed Clustered Graph-Transformer for spatiotemporal prediction problems in urban computing. To handle the spatial and temporal unsmoothness problem, we use a gradientbased clustering technique in GAT to construct spatial feature extractor. We use MVPE and attention to handle temporal unsmoothness by providing a urban-specific temporal encoding to the temporal mode. The experiment has shown the effectiveness of the proposed model. In the future, we plan to explore long seq2seq problem using atrous transformer (Child et al., 2019) as well as explore the explanation for the attention and clustering assignments.

heading: A PRELIMINARY ANALYSIS

text:
In this section, we conduct a preliminary error analysis for a baseline GNN+RNN based model on spatial and temporal unsmooth areas in order to prove our assumptions and motivate our design methodology.
For input spatial temporal signal X , denote Xs and Xt as its spatial and temporal modes, respectively, and L as the graph laplacian matrix for spatial distribution. The L is the loss metric. The spatial and temporal unsmoothnesses could be represented by the difference between a convoluted value and its true value. We define the spatial convolution kernel as αL, which is a linear combination of the features from all neighboring locations. The temporal convolution kernel is defined as Wt∗, which is a 1d convolution along temporal mode. The spatial and temporal unsmoothnesses are calculated as φs = L(X,αLXs) and φt = L(X,Wt ∗ Xt), respectively. The α and Wt are optimized using the same training set as the baseline model. Spatial and temporal areas with larger unsmoothness means that they are hard to be represented by using
a linear combination of observations in neighboring locations.
(a) Positive relationship between spatial unsmoothness (X) and prediction error (Y) for the baseline model. (b) Positive relationship between temporal unsmoothness (X) and prediction error (Y) for the baseline model.
Figure 7: Baseline prediction error and unsmoothness
Figure 7 shows the positive relationship between baseline prediction error and spatial/temporal unsmoothness. There are several reasons for this. First, the expressiveness of GNNs are limited. Using
ChebNet as an example, it treats all neighbors in one convolution kernel homogeneously and shares its weighted transformation on feature dimension to all neighboring vertices. Thus, ChebNet lacks discriminativity within the neighborhood. Li et al. (2018a) also proves that the usage of laplacian smoothing will cause serious problem in deep-stacked GCN models. Second, spatial feature extractors are shared among all regions, that is, it is assumed that spatial feature extraction rule is universally applied to the whole city. In Figure 6, we clustered the regions in the city into 5 clusters according to their similarities by using DTW (Senin, 2008) of temporal pattern in a short snippet and print averaged 24 hour temporal pattern for them. The clustering result shows that the magnitudes for regions from different clusters are different with high confidence. The overall temporal patterns for different clusters are quite diverse.

heading: B LOCAL STABILITY ON THE TEMPORAL MODE

text: In this section, we prove in details that the temporal patterns are stable within each batch, compared with its large variation across the whole dataset. The average value for batch-level standard deviation on temporal mode is 658.57. The standard-deviation on temporal mode for the whole dataset is 1074.84, which is significantly larger. The batch-size is the same with our experiment setting.

heading: C CALCULATION FOR TEMPORAL ATTENTION IN TRANSFORMER

text:
The temporal attention is calculated as follows:
Attn(Q,K, V ) = softmax( QKT√ dk )V,
where QKT is a self-attention to represent relationships among different time-steps. Such relationship is further applied on V by transforming its temporal mode.
The feed forward layer is a linear transformation on the feature mode as follows:
Hffn(X) = σr(XfWf ).
In encoder, the self-attention is used to discover temporal dependencies in the latent feature vector h such that the attention is defined as
Q = hWq,K = hWk, and V = hWv. (12)
In decoder, the self-attention performs similarly, but a mask is applied on the input sequence so that the feature extraction at time t could not view the temporal features later than it. The mask is implemented by an upper triangular matrix. The encoder-decoder attention transforms the temporal mode of decoder latent feature based on temporal dependencies from the encoder as follows:
Q = hencWq,K = hencWk, and V = hWv, (13)
where h is the decoder latent feature vector from previous decoder layers and henc is the encoder feature vector which denotes the encoder state. In this application, the initial state for the decoder input sequence (target sequence) is copied from the last time-step of the input sequence.
D VISUALIZATION FOR PERFORMANCE ON TEMPORAL UNSMOOTHNESS
Figure 8 shows the comparison between ground truth and machine learning models based on 24- hour ride-hailing demand values in selected regions. According to the visualization, CGT model is more close to ground truth, especially in those temporal unsmoothed areas.