OpenRaiser/Intern-Atlas huggingface dataset:
Agreement tests on graphs and hypergraphs
Venue: arXiv cs.CC 2020
Year: 2020

Agreement tests are a generalization of low degree tests that capture a local-to-global phenomenon, which forms the combinatorial backbone of most PCP constructions. In an agreement test, a function is given by an ensemble of local restrictions. The agreement test checks that the restrictions agree when they overlap, and the main question is whether average agreement of the local pieces implies that there exists a global function that agrees with most local restrictions. There are very few structures that support agreement tests, essentially either coming from algebraic low degree tests or from direct product tests (and recently also from high-dimensional expanders). In this work, we prove a new agreement theorem which extends direct product tests to higher dimensions, analogous to how low degree tests extend linearity testing. As a corollary of our main theorem, it follows that an ensemble of small graphs on overlapping sets of vertices can be glued together to one global graph assuming they agree with each other on average. We prove the agreement theorem by (re)proving the agreement theorem for dimension 1, and then generalizing it to higher dimensions (with the dimension 1 case being the direct product test, and dimension 2 being the graph case). A key technical step in our proof is the reverse union bound, which allows us to treat dependent events as if they are disjoint, and may be of independent interest. An added benefit of the reverse union bound is that it can be used to show that the "majority decoded" function also serves as a global function that explains the local consistency of the agreement theorem, a fact that was not known even in the direct product setting (dimension 1) prior to our work.
Convolutional Networks with Adaptive Inference Graphs
Venue: arXiv cs.CV 2020
Year: 2020

Do convolutional networks really need a fixed feed-forward structure? What if, after identifying the high-level concept of an image, a network could move directly to a layer that can distinguish fine-grained differences? Currently, a network would first need to execute sometimes hundreds of intermediate layers that specialize in unrelated aspects. Ideally, the more a network already knows about an image, the better it should be at deciding which layer to compute next. In this work, we propose convolutional networks with adaptive inference graphs (ConvNet-AIG) that adaptively define their network topology conditioned on the input image. Following a high-level structure similar to residual networks (ResNets), ConvNet-AIG decides for each input image on the fly which layers are needed. In experiments on ImageNet we show that ConvNet-AIG learns distinct inference graphs for different categories. Both ConvNet-AIG with 50 and 101 layers outperform their ResNet counterpart, while using 20% and 38% less computations respectively. By grouping parameters into layers for related classes and only executing relevant layers, ConvNet-AIG improves both efficiency and overall classification quality. Lastly, we also study the effect of adaptive inference graphs on the susceptibility towards adversarial examples. We observe that ConvNet-AIG shows a higher robustness than ResNets, complementing other known defense mechanisms.
Optimal Fast Johnson-Lindenstrauss Embeddings for Large Data Sets
Venue: arXiv cs.DS 2020
Year: 2020

Johnson-Lindenstrauss embeddings are widely used to reduce the dimension and thus the processing time of data. To reduce the total complexity, also fast algorithms for applying these embeddings are necessary. To date, such fast algorithms are only available either for a non-optimal embedding dimension or up to a certain threshold on the number of data points. We address a variant of this problem where one aims to simultaneously embed larger subsets of the data set. Our method follows an approach by Nelson: A subsampled Hadamard transform maps points into a space of lower, but not optimal dimension. Subsequently, a random matrix with independent entries projects to an optimal embedding dimension. For subsets whose size scales at least polynomially in the ambient dimension, the complexity of this method comes close to the number of operations just to read the data under mild assumptions on the size of the data set that are considerably less restrictive than in previous works. We also prove a lower bound showing that subsampled Hadamard matrices alone cannot reach an optimal embedding dimension. Hence, the second embedding cannot be omitted.
Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training
Venue: arXiv cs.CV 2020
Year: 2020

Large-scale distributed training requires significant communication bandwidth for gradient exchange that limits the scalability of multi-node training, and requires expensive high-bandwidth network infrastructure. The situation gets even worse with distributed training on mobile devices (federated learning), which suffers from higher latency, lower throughput, and intermittent poor connections. In this paper, we find 99.9% of the gradient exchange in distributed SGD is redundant, and propose Deep Gradient Compression (DGC) to greatly reduce the communication bandwidth. To preserve accuracy during compression, DGC employs four methods: momentum correction, local gradient clipping, momentum factor masking, and warm-up training. We have applied Deep Gradient Compression to image classification, speech recognition, and language modeling with multiple datasets including Cifar10, ImageNet, Penn Treebank, and Librispeech Corpus. On these scenarios, Deep Gradient Compression achieves a gradient compression ratio from 270x to 600x without losing accuracy, cutting the gradient size of ResNet-50 from 97MB to 0.35MB, and for DeepSpeech from 488MB to 0.74MB. Deep gradient compression enables large-scale distributed training on inexpensive commodity 1Gbps Ethernet and facilitates distributed training on mobile. Code is available at: https://github.com/synxlin/deep-gradient-compression.
Deep Echo State Network (DeepESN): A Brief Survey
Venue: arXiv cs.LG 2020
Year: 2020

The study of deep recurrent neural networks (RNNs) and, in particular, of deep Reservoir Computing (RC) is gaining an increasing research attention in the neural networks community. The recently introduced Deep Echo State Network (DeepESN) model opened the way to an extremely efficient approach for designing deep neural networks for temporal data. At the same time, the study of DeepESNs allowed to shed light on the intrinsic properties of state dynamics developed by hierarchical compositions of recurrent layers, i.e. on the bias of depth in RNNs architectural design. In this paper, we summarize the advancements in the development, analysis and applications of DeepESNs.
An Adaptive Gas Cost Mechanism for Ethereum to Defend Against Under-Priced DoS Attacks
Venue: arXiv cs.CR 2020
Year: 2020

The gas mechanism in Ethereum charges the execution of every operation to ensure that smart contracts running in EVM (Ethereum Virtual Machine) will be eventually terminated. Failing to properly set the gas costs of EVM operations allows attackers to launch DoS attacks on Ethereum. Although Ethereum recently adjusted the gas costs of EVM operations to defend against known DoS attacks, it remains unknown whether the new setting is proper and how to configure it to defend against unknown DoS attacks. In this paper, we make the first step to address this challenging issue by first proposing an emulation-based framework to automatically measure the resource consumptions of EVM operations. The results reveal that Ethereum's new setting is still not proper. Moreover, we obtain an insight that there may always exist exploitable under-priced operations if the cost is fixed. Hence, we propose a novel gas cost mechanism, which dynamically adjusts the costs of EVM operations according to the number of executions, to thwart DoS attacks. This method punishes the operations that are executed much more frequently than before and lead to high gas costs. To make our solution flexible and secure and avoid frequent update of Ethereum client, we design a special smart contract that collaborates with the updated EVM for dynamic parameter adjustment. Experimental results demonstrate that our method can effectively thwart both known and unknown DoS attacks with flexible parameter settings. Moreover, our method only introduces negligible additional gas consumption for benign users.
Tight Hardness for Shortest Cycles and Paths in Sparse Graphs
Venue: arXiv cs.DS 2020
Year: 2020

Fine-grained reductions have established equivalences between many core problems with $\tilde{O}(n^3)$-time algorithms on $n$-node weighted graphs, such as Shortest Cycle, All-Pairs Shortest Paths (APSP), Radius, Replacement Paths, Second Shortest Paths, and so on. These problems also have $\tilde{O}(mn)$-time algorithms on $m$-edge $n$-node weighted graphs, and such algorithms have wider applicability. Are these $mn$ bounds optimal when $m \ll n^2$? Starting from the hypothesis that the minimum weight $(2\ell+1)$-Clique problem in edge weighted graphs requires $n^{2\ell+1-o(1)}$ time, we prove that for all sparsities of the form $m = Θ(n^{1+1/\ell})$, there is no $O(n^2 + mn^{1-ε})$ time algorithm for $ε>0$ for \emph{any} of the below problems: Minimum Weight $(2\ell+1)$-Cycle in a directed weighted graph, Shortest Cycle in a directed weighted graph, APSP in a directed or undirected weighted graph, Radius (or Eccentricities) in a directed or undirected weighted graph, Wiener index of a directed or undirected weighted graph, Replacement Paths in a directed weighted graph, Second Shortest Path in a directed weighted graph, Betweenness Centrality of a given node in a directed weighted graph. That is, we prove hardness for a variety of sparse graph problems from the hardness of a dense graph problem. Our results also lead to new conditional lower bounds from several related hypothesis for unweighted sparse graph problems including $k$-cycle, shortest cycle, Radius, Wiener index and APSP.
Near-linear Time Algorithm for Approximate Minimum Degree Spanning Trees
Venue: arXiv cs.DS 2020
Year: 2020

Given a graph $G = (V, E)$, we wish to compute a spanning tree whose maximum vertex degree, i.e. tree degree, is as small as possible. Computing the exact optimal solution is known to be NP-hard, since it generalizes the Hamiltonian path problem. For the approximation version of this problem, a $\tilde{O}(mn)$ time algorithm that computes a spanning tree of degree at most $Δ^* +1$ is previously known [Fürer \& Raghavachari 1994]; here $Δ^*$ denotes the minimum tree degree of all the spanning trees. In this paper we give the first near-linear time approximation algorithm for this problem. Specifically speaking, we propose an $\tilde{O}(\frac{1}{ε^7}m)$ time algorithm that computes a spanning tree with tree degree $(1+ε)Δ^* + O(\frac{1}{ε^2}\log n)$ for any constant $ε\in (0,\frac{1}{6})$. Thus, when $Δ^*=ω(\log n)$, we can achieve approximate solutions with constant approximate ratio arbitrarily close to 1 in near-linear time.
General-Purpose Visual Language and Information System with Case-Studies in Developing Business Applications
Venue: arXiv cs.SE 2020
Year: 2020

Learning computer programming has been always challenging. Since the sixties of the last century, many researchers developed Visual Programming Languages (VPLs) to help in this regard. In this thesis, ten VPLs were specifically selected, studied, experimented with, and evaluated. A total of fifteen metrics were used to evaluate the tools. Comparisons, classification, and gap analysis were then presented. A list of requirements for a general-purpose VPL and a guide to help the novice programmer choose the right tool were generated and finally the PWCT (Programming Without Coding Technology, a novel general-purpose visual programming language) is developed and presented. PWCT has been launched as a Sourceforge project, which currently has more than 230,000 downloads for the language and more than 19,500,000 downloads for samples, tutorials and movies. Many business applications and projects are developed using PWCT, Also we developed the Supernova programming language and the Ring programming language using PWCT to prove that it can be used for advanced and large projects. Feedback from developers and results from the studies indicate that PWCT is a very appealing, competitive, and powerful language.
Side Information Fusion for Recommender Systems over Heterogeneous Information Network
Venue: arXiv cs.IR 2020
Year: 2020

Collaborative filtering (CF) has been one of the most important and popular recommendation methods, which aims at predicting users' preferences (ratings) based on their past behaviors. Recently, various types of side information beyond the explicit ratings users give to items, such as social connections among users and metadata of items, have been introduced into CF and shown to be useful for improving recommendation performance. However, previous works process different types of information separately, thus failing to capture the correlations that might exist across them. To address this problem, in this work, we study the application of heterogeneous information network (HIN) to enhance CF-based recommendation methods. However, we face challenging issues in HIN-based recommendation, i.e., how to capture similarities of complex semantics between users and items in a HIN, and how to effectively fuse these similarities to improve final recommendation performance. To address these issues, we apply metagraph to similarity computation and solve the information fusion problem with a ``matrix factorization (MF) + factorization machine (FM)'' framework. For the MF part, we obtain the user-item similarity matrix from each metagraph and then apply low-rank matrix approximation to obtain latent features for both users and items. For the FM part, we apply FM with Group lasso (FMG) on the features obtained from the MF part to train the recommending model and, at the same time, identify the useful metagraphs. Besides FMG, a two-stage method, we further propose an end-to-end method, hierarchical attention fusing (HAF), to fuse metagraph based similarities for the final recommendation. Experimental results on four large real-world datasets show that the two proposed frameworks significantly outperform existing state-of-the-art methods in terms of recommendation performance.
Design, Analysis & Prototyping of a Semi-Automated Staircase-Climbing Rehabilitation Robot
Venue: arXiv cs.RO 2020
Year: 2020

In this paper, we describe the mechanical design, system overview, integration and control techniques associated with SKALA, a unique large-sized robot for carrying a person with physical disabilities, up and down staircases. As a regular wheelchair is unable to perform such a maneuver, the system functions as a non-conventional wheelchair with several intelligent features. We describe the unique mechanical design and the design choices associated with it. We showcase the embedded control architecture that allows for several different modes of teleoperation, all of which have been described in detail. We further investigate the architecture associated with the autonomous operation of the system.
Preventing Social Disappointment in Elections
Venue: arXiv cs.MA 2020
Year: 2020

Mechanism design is concerned with settings where a policymaker (or social planner) faces the problem of aggregating the announced preferences of multiple agents into a collective (or social), system-wide decision. One of the most important ways for aggregating preference that has been used in multi-agent systems is election. In an election, the aim is to select the candidate who reflects the common will of society. Despite the importance of this subject, in some situations, the result of the election does not respect the purpose of those who execute it and the election leads to dissatisfaction of a large amount of people and in some cases causes polarization in societies. To analyze these situations, we introduce a new notion called social disappointment and we show which voting rules can prevent it in elections. In addition, we propose new protocols to prevent social disappointment in elections. A version of the impossibility theorem is proved regarding social disappointment in elections, showing that there is no voting rule for four or more candidates that simultaneously satisfies avoiding social disappointment and Condorcet winner criteria. We give conditions under which one of our new protocols always selects the Condorcet winner under the assumption of single peakedness. We empirically compare our protocols with seven well-known other voting protocols and observe that our protocols are capable of preventing social disappointment and are more robust against manipulations.
Quadratically Constrained Myopic Adversarial Channels
Venue: arXiv cs.IT 2020
Year: 2020

We study communication in the presence of a jamming adversary where quadratic power constraints are imposed on the transmitter and the jammer. The jamming signal is allowed to be a function of the codebook, and a noncausal but noisy observation of the transmitted codeword. For a certain range of the noise-to-signal ratios (NSRs) of the transmitter and the jammer, we are able to characterize the capacity of this channel under deterministic encoding or stochastic encoding, i.e., with no common randomness between the encoder/decoder pair. For the remaining NSR regimes, we determine the capacity under the assumption of a small amount of common randomness (at most $2\log(n)$ bits in one sub-regime, and at most $Ω(n)$ bits in the other sub-regime) available to the encoder-decoder pair. Our proof techniques involve a novel myopic list-decoding result for achievability, and a Plotkin-type push attack for the converse in a subregion of the NSRs, both of which which may be of independent interest. We also give bounds on the secrecy capacity of this channel assuming that the jammer is simultaneously eavesdropping.
Denoising Prior Driven Deep Neural Network for Image Restoration
Venue: arXiv cs.CV 2020
Year: 2020

Deep neural networks (DNNs) have shown very promising results for various image restoration (IR) tasks. However, the design of network architectures remains a major challenging for achieving further improvements. While most existing DNN-based methods solve the IR problems by directly mapping low quality images to desirable high-quality images, the observation models characterizing the image degradation processes have been largely ignored. In this paper, we first propose a denoising-based IR algorithm, whose iterative steps can be computed efficiently. Then, the iterative process is unfolded into a deep neural network, which is composed of multiple denoisers modules interleaved with back-projection (BP) modules that ensure the observation consistencies. A convolutional neural network (CNN) based denoiser that can exploit the multi-scale redundancies of natural images is proposed. As such, the proposed network not only exploits the powerful denoising ability of DNNs, but also leverages the prior of the observation model. Through end-to-end training, both the denoisers and the BP modules can be jointly optimized. Experimental results on several IR tasks, e.g., image denoisig, super-resolution and deblurring show that the proposed method can lead to very competitive and often state-of-the-art results on several IR tasks, including image denoising, deblurring and super-resolution.
JointDNN: An Efficient Training and Inference Engine for Intelligent Mobile Cloud Computing Services
Venue: arXiv cs.DC 2020
Year: 2020

Deep learning models are being deployed in many mobile intelligent applications. End-side services, such as intelligent personal assistants, autonomous cars, and smart home services often employ either simple local models on the mobile or complex remote models on the cloud. However, recent studies have shown that partitioning the DNN computations between the mobile and cloud can increase the latency and energy efficiencies. In this paper, we propose an efficient, adaptive, and practical engine, JointDNN, for collaborative computation between a mobile device and cloud for DNNs in both inference and training phase. JointDNN not only provides an energy and performance efficient method of querying DNNs for the mobile side but also benefits the cloud server by reducing the amount of its workload and communications compared to the cloud-only approach. Given the DNN architecture, we investigate the efficiency of processing some layers on the mobile device and some layers on the cloud server. We provide optimization formulations at layer granularity for forward- and backward-propagations in DNNs, which can adapt to mobile battery limitations and cloud server load constraints and quality of service. JointDNN achieves up to 18 and 32 times reductions on the latency and mobile energy consumption of querying DNNs compared to the status-quo approaches, respectively.
Graph-Theoretic Framework for Unified Analysis of Observability and Data Injection Attacks in the Smart Grid
Venue: arXiv cs.SY 2020
Year: 2020

In this paper, a novel graph-theoretic framework is proposed to generalize the analysis of a broad set of security attacks, including observability and data injection attacks, that target the state estimator of a smart grid. First, the notion of observability attacks is defined based on a proposed graph-theoretic construct. In this respect, a structured approach is proposed to characterize critical sets, whose removal renders the system unobservable. It is then shown that, for the system to be observable, these critical sets must be part of a maximum matching over a proposed bipartite graph. In addition, it is shown that stealthy data injection attacks (SDIAs) constitute a special case of these observability attacks. Then, various attack strategies and defense policies, for observability and data injection attacks, are shown to be amenable to analysis using the introduced graph-theoretic framework. The proposed framework is then shown to provide a unified basis for analysis of four key security problems (among others), pertaining to the characterization of: 1) The sparsest SDIA; 2) the sparsest SDIA including a certain measurement; 3) a set of measurements which must be defended to thwart all potential SDIAs; and 4) the set of measurements, which when protected, can thwart any SDIA whose cardinality is below a certain threshold. A case study using the IEEE 14-bus system with a set of 17 measurements is used to support the theoretical findings.
Parameter Box: High Performance Parameter Servers for Efficient Distributed Deep Neural Network Training
Venue: arXiv cs.DC 2020
Year: 2020

Most work in the deep learning systems community has focused on faster inference, but arriving at a trained model requires lengthy experiments. Accelerating training lets developers iterate faster and come up with better models. DNN training is often seen as a compute-bound problem, best done in a single large compute node with many GPUs. As DNNs get bigger, training requires going distributed. Distributed deep neural network (DDNN) training constitutes an important workload on the cloud. Larger DNN models and faster compute engines shift the training performance bottleneck from computation to communication. Our experiments show existing DNN training frameworks do not scale in a typical cloud environment due to insufficient bandwidth and inefficient parameter server software stacks.We propose PBox, a balanced, scalable central PS hardware that balances compute and communication resources, and PHub, a high performance parameter server (PS) software design that provides an optimized network stack and a streamlined gradient processing pipeline to benefit common PS setups to utilize PBox. We show that in a typical cloud environment, PBox can achieve up to 3.8x speedup over state-of-the-art designs when training ImageNet. We discuss future directions of integrating PBox with programmable switches for in-network aggregation during training, leveraging the datacenter network topology to reduce bandwidth usage and localize data movement.