Spatial-temporal graph have been widely observed in various domains such as neuroscience, climate research, and transportation engineering. The state-of-the-art models of spatialtemporal graphs rely on Graph Neural Networks (GNNs) to obtain explicit representations for such networks and to discover hidden spatial dependencies in them. These models have demonstrated superior performance in various tasks. In this paper, we propose a sparse adversarial attack framework AdverSparse to illustrate that when only a few key connections are removed in such graphs, hidden spatial dependencies learned by such spatial-temporal models are significantly impacted, leading to various issues such as increasing prediction errors. We formulate the adversarial attack as an optimization problem and solve it by the Alternating Direction Method of Multipliers (ADMM). Experiments show that AdverSparse can find and remove key connections in these graphs, leading to malfunctioning models, even in models capable of learning hidden spatial dependencies.

Deep neural networks (DNNs) have shown to provide superb performance in many real life applications, but their large computation cost and storage requirement have prevented them from being deployed to many edge and internet-of-things (IoT) devices. Sparse deep neural networks, whose majority weight parameters are zeros, can substantially reduce the computation complexity and memory consumption of the models. In real-use scenarios, devices may suffer from large fluctuations of the available computation and memory resources under different environment, and the quality of service (QoS) is difficult to maintain due to the long tail inferences with large latency. Facing the real-life challenges, we propose to train a sparse model that supports multiple sparse levels. That is, a hierarchical structure of weights are satisfied such that the locations and the values of the non-zero parameters of the more-sparse sub-model are a subset of the less-sparse sub-model. In this way, one can dynamically select the appropriate sparsity level during inference, while the storage cost is capped by the least sparse sub-model. We have verified our methodologies on a variety of DNN models and tasks, including the ResNet-50, PointNet++, GNMT, and graph attention networks. We obtain sparse sub-models with an average of 13.38% weights and 14.97% FLOPs, while the accuracies are as good as their dense counterparts. More-sparse sub-models with 5.38% weights and 4.47% of FLOPs, which are subsets of the less-sparse ones, can be obtained with only 3.25% relative accuracy loss. In addition, our proposed hierarchical model structure supports the mechanism to inference the first part of the model with less sparsity, and dynamically reroute to the more-sparse level if the real-time latency constraint is estimated to be violated. Preliminary analysis shows that we can improve the QoS by one or two nines depending on the task and the computation-memory resources of the inference engine.

Weight pruning methods of deep neural networks (DNNs) have been demonstrated to achieve a good model pruning rate without loss of accuracy, thereby alleviating the significant computation/storage requirements of large-scale DNNs. Structured weight pruning methods have been proposed to overcome the limitation of irregular network structure and demonstrated actual GPU acceleration. However, in prior work, the pruning rate (degree of sparsity) and GPU acceleration are limited (to less than 50%) when accuracy needs to be maintained. In this work, we overcome these limitations by proposing a unified, systematic framework of structured weight pruning for DNNs. It is a framework that can be used to induce different types of structured sparsity, such as filterwise, channelwise, and shapewise sparsity, as well as nonstructured sparsity. The proposed framework incorporates stochastic gradient descent (SGD; or ADAM) with alternating direction method of multipliers (ADMM) and can be understood as a dynamic regularization method in which the regularization target is analytically updated in each iteration. Leveraging special characteristics of ADMM, we further propose a progressive, multistep weight pruning framework and a network purification and unused path removal procedure, in order to achieve higher pruning rate without accuracy loss. Without loss of accuracy on the AlexNet model, we achieve 2.58× and 3.65× average measured speedup on two GPUs, clearly outperforming the prior work. The average speedups reach 3.15× and 8.52× when allowing a moderate accuracy loss of 2%. In this case, the model compression for convolutional layers is 15.0× , corresponding to 11.93× measured CPU speedup. As another example, for the ResNet-18 model on the CIFAR-10 data set, we achieve an unprecedented 54.2× structured pruning rate on CONV layers. This is 32× higher pruning rate compared with recent work and can further translate into 7.6× inference time speedup on the Adreno 640 mobile GPU compared with the original, unpruned DNN model. We share our codes and models at the link http://bit.ly/2M0V7DO.

To address the large model size and intensive computation requirement of deep neural networks (DNNs), weight pruning techniques have been proposed and generally fall into two categories, i.e., static regularization-based pruning and dynamic regularization-based pruning. However, the former method currently suffers either complex workloads or accuracy degradation, while the latter one takes a long time to tune the parameters to achieve the desired pruning rate without accuracy loss. In this paper, we propose a unified DNN weight pruning framework with dynamically updated regularization terms bounded by the designated constraint. Our proposed method increases the compression rate, reduces the training time and reduces the number of hyper-parameters compared with state-of-the-art ADMM-based hard constraint method.

The worst-case training principle that minimizes the maximal adversarial loss, also known as adversarial training (AT), has shown to be a state-of-the-art approach for enhancing adversarial robustness. Nevertheless, min-max optimization beyond the purpose of AT has not been rigorously explored in the adversarial context. In this paper, we show how a general notion of min-max optimization over multiple domains can be leveraged to the design of different types of adversarial attacks. In particular, given a set of risk sources, minimizing the worst-case attack loss can be reformulated as a min-max problem by introducing domain weights that are maximized over the probability simplex of the domain set. We showcase this unified framework in three attack generation problems -- attacking model ensembles, devising universal perturbation under multiple inputs, and crafting attacks resilient to data transformations. Extensive experiments demonstrate that our approach leads to substantial attack improvement over the existing heuristic strategies as well as robustness improvement over state-of-the-art defense methods against multiple perturbation types. Furthermore, we find that the self-adjusted domain weights learned from min-max optimization can provide a holistic tool to explain the difficulty level of attack across domains.

As deep neural networks (DNNs) achieve extraordinary performance in a wide range of tasks, testing their robustness under adversarial attacks becomes paramount. Adversarial attacks, also known as adversarial examples, are used to measure the robustness of DNNs and are generated by incorporating imperceptible perturbations into the input data with the intention of altering a DNN's classification. In prior work in this area, most of the proposed optimization based methods employ gradient descent to find adversarial examples. In this paper, we present an innovative method which generates adversarial examples via convex programming. Our experiment results demonstrate that we can generate adversarial examples with lower distortion and higher transferability than the C&W attack, which is the current state-of-the-art adversarial attack method for DNNs. We achieve 100% attack success rate on both the original undefended models and the adversarially-trained models. Our distortions of the L_inf attack are respectively 31% and 18% lower than the C&W attack for the best case and average case on the CIFAR-10 data set.

We study the problem of adaptive sensor management for target tracking, where at every instant we search for the best sensors to be activated at the next time step. In our problem formulation, the measurements may be corrupted by correlated noises, and the impact of correlated measurements on sensor selection is studied. Specifically, we adopt an alternative conditional posterior Cramér-Rao lower bound (C-PCRLB) as the optimization criterion for sensor selection, where the trace of the conditional Fisher information matrix is maximized subject to an energy constraint. We demonstrate that the proposed sensor selection problem can be transformed into the problem of maximizing a convex quadratic function over a bounded polyhedron. This optimization problem is NP-hard in nature, and thus we employ a linearization method and a bilinear programming approach to obtain locally optimal sensor schedules in a computationally efficient manner.

In this paper, we consider the problem of estimating a spatially varying field in a wireless sensor network, where resource constraints limit the number of sensors selected in the network that provide their measurements for field estimation. Based on a one-to-one correspondence between the selected sensors and the nonzero elements of Kriging weights, we propose a sparsity-promoting ordinary Kriging approach where we minimize the Kriging error variance while penalizing the number of nonzero Kriging weights. This yields a combinatorial optimization problem, which is intractable in general. To solve the proposed non-convex optimization problem, we employ the alternating direction method of multipliers (ADMM) and the reweighted ℓ1minimization method, respectively. Numerical results are provided to illustrate the effectiveness of our proposed approaches that provide a balance between the estimation accuracy and the number of selected sensors.

In the context of distributed estimation we consider the problem of sensor collaboration, which refers to the act of sharing measurements with neighboring sensors prior to transmission to a fusion center. While incorporating the cost of sensor collaboration, we aim to find optimal sparse collaboration topologies subject to a certain information or energy constraint. To achieve this goal, we present a tractable optimization framework and propose efficient methods to solve the formulated sensor collaboration problems. The effectiveness of our approach is demonstrated by numerical examples.

In this letter, a new sparsity-promoting penalty function is introduced for sensor selection problems in field reconstruction, which has the property of avoiding scenarios where the same sensors are successively selected. Using a reweighted ℓ1relaxation of the ℓ0norm, the sensor selection problem is reformulated as a convex quadratic program. In order to handle large-scale problems, we also present two fast algorithms: accelerated proximal gradient method and alternating direction method of multipliers. Numerical results are provided to demonstrate the effectiveness of our approaches.

In this letter, we study the problem of target tracking based on energy readings of sensors. We minimize the estimation error by using an extended Kalman filter (EKF). The Kalman gain matrix is obtained as the solution to an optimization problem in which a sparsity-promoting penalty function is added to the objective. The added term penalizes the number of nonzero columns of the Kalman gain matrix, which corresponds to the number of active sensors. By using a sparse Kalman gain matrix only a few sensors send their measurements to the fusion center, thereby saving energy. Simulation results show that an EKF with a sparse Kalman gain matrix can achieve tracking performance that is very close to that of the classical EKF, where all sensors transmit to the fusion center.