OpenRaiser/Intern-Atlas huggingface dataset:
Built-in Vulnerabilities to Imperceptible Adversarial Perturbations
Venue: arXiv cs.CV 2019
Year: 2019

Designing models that are robust to small adversarial perturbations of their inputs has proven remarkably difficult. In this work we show that the reverse problem---making models more vulnerable---is surprisingly easy. After presenting some proofs of concept on MNIST, we introduce a generic tilting attack that injects vulnerabilities into the linear layers of pre-trained networks by increasing their sensitivity to components of low variance in the training data without affecting their performance on test data. We illustrate this attack on a multilayer perceptron trained on SVHN and use it to design a stand-alone adversarial module which we call a steganogram decoder. Finally, we show on CIFAR-10 that a poisoning attack with a poisoning rate as low as 0.1% can induce vulnerabilities to chosen imperceptible backdoor signals in state-of-the-art networks. Beyond their practical implications, these different results shed new light on the nature of the adversarial example phenomenon.
Hulls of Cyclic Codes over $\mathbb{Z}_4$
Venue: arXiv cs.IT 2019
Year: 2019

The hulls of linear and cyclic codes over finite fields have been of interest and extensively studied due to their wide applications. In this paper, the hulls of cyclic codes of length $n$ over the ring $\mathbb{Z}_4$ have been focused on. Their characterization has been established in terms of the generators viewed as ideals in the quotient ring $\mathbb{Z}_4[x]/\langle x^n-1\rangle$. An algorithm for computing the types of the hulls of cyclic codes of arbitrary odd length over $\mathbb{Z}_4$ has been given. The average $2$-dimension $E(n)$ of the hulls of cyclic codes of odd length $n$ over $\mathbb{Z}_4$ has been established. A general formula for $E(n)$ has been provided together with its upper and lower bounds. It turns out that $E(n)$ grows the same rate as $n$.
Quick and Plenty: Achieving Low Delay and High Rate in 802.11ac Edge Networks
Venue: arXiv cs.NI 2019
Year: 2019

We consider transport layer approaches for achieving high rate, low delay communication over edge paths where the bottleneck is an 802.11ac WLAN. We first show that by regulating send rate so as to maintain a target aggregation level it is possible to realise high rate, low delay communication over 802.11ac WLANs. We then address two important practical issues arising in production networks, namely that (i) many client devices are non-rooted mobile handsets/tablets and (ii) the bottleneck may lie in the backhaul rather than the WLAN, or indeed vary between the two over time. We show that both these issues can be resolved by use of simple and robust machine learning techniques. We present a prototype transport layer implementation of our low delay rate allocation approach and use this to evaluate performance under real radio conditions.
An Application of Computable Distributions to the Semantics of Probabilistic Programs
Venue: arXiv cs.PL 2019
Year: 2019

In this chapter, we explore how (Type-2) computable distributions can be used to give both (algorithmic) sampling and distributional semantics to probabilistic programs with continuous distributions. Towards this end, we sketch an encoding of computable distributions in a fragment of Haskell and show how topological domains can be used to model the resulting PCF-like language. We also examine the implications that a (Type-2) computable semantics has for implementing conditioning. We hope to draw out the connection between an approach based on (Type-2) computability and ordinary programming throughout the chapter as well as highlight the relation with constructive mathematics (via realizability).
GPOP: A cache- and work-efficient framework for Graph Processing Over Partitions
Venue: arXiv cs.DC 2019
Year: 2019

Past decade has seen the development of many shared-memory graph processing frameworks, intended to reduce the effort of developing high performance parallel applications. However many of these frameworks, based on Vertex-centric or Edge-centric paradigms suffer from several issues, such as poor cache utilization, irregular memory accesses, heavy use of synchronization primitives and theoretical inefficiency, that deteriorate overall performance and scalability. Recently, we proposed a cache and memory efficient partition-centric paradigm for computing PageRank. In this paper, we generalize this approach to develop a novel Graph Processing Over Partitions (GPOP) framework that is cache-efficient, scalable and work-efficient. GPOP induces locality in memory accesses by increasing granularity of execution to vertex subsets called 'partitions', thereby dramatically improving the cache performance of a variety of graph algorithms. It achieves high scalability by enabling completely lock and atomic free computation. GPOP's built-in analytical performance model enables it to use a hybrid of source and partitioncentric communication modes in a way that ensures work-efficiency each iteration, while simultaneously boosting high bandwidth sequential memory accesses. We extensively evaluate the performance of GPOP for a variety of graph algorithms, using several large datasets. We observe that GPOP incurs up to 9x, 6.8x and 5.5x less L2 cache misses compared to Ligra, GraphMat and Galois, respectively. In terms of execution time, GPOP is upto 19x, 9.3x and 3.6x faster than Ligra, GraphMat and Galois respectively.
An output-sensitive algorithm for the minimization of 2-dimensional String Covers
Venue: arXiv cs.DS 2019
Year: 2019

String covers are a powerful tool for analyzing the quasi-periodicity of 1-dimensional data and find applications in automata theory, computational biology, coding and the analysis of transactional data. A \emph{cover} of a string $T$ is a string $C$ for which every letter of $T$ lies within some occurrence of $C$. String covers have been generalized in many ways, leading to \emph{k-covers}, \emph{$λ$-covers}, \emph{approximate covers} and were studied in different contexts such as \emph{indeterminate strings}. In this paper we generalize string covers to the context of 2-dimensional data, such as images. We show how they can be used for the extraction of textures from images and identification of primitive cells in lattice data. This has interesting applications in image compression, procedural terrain generation and crystallography.
Assumption-Commitment Types for Resource Management in Virtually Timed Ambients
Venue: arXiv cs.LO 2019
Year: 2019

This paper introduces a type system for resource management in the context of nested virtualization. With nested virtualization, virtual machines compete with other processes for the resources of their host environment in order to provision their own processes, which could again be virtual machines. The calculus of virtually timed ambients formalizes such resource provisioning, extending the capabilities of mobile ambients to model the dynamic creation, migration, and destruction of virtual machines. The proposed type system uses assumptions about the outside of a virtually timed ambient to guarantee resource provisioning on the inside. We prove subject reduction and progress for well-typed virtually timed ambients, expressing that upper bounds on resource needs are preserved by reduction and that processes do not run out of resources.
Combination of Domain Knowledge and Deep Learning for Sentiment Analysis
Venue: arXiv cs.CL 2019
Year: 2019

The emerging technique of deep learning has been widely applied in many different areas. However, when adopted in a certain specific domain, this technique should be combined with domain knowledge to improve efficiency and accuracy. In particular, when analyzing the applications of deep learning in sentiment analysis, we found that the current approaches are suffering from the following drawbacks: (i) the existing works have not paid much attention to the importance of different types of sentiment terms, which is an important concept in this area; and (ii) the loss function currently employed does not well reflect the degree of error of sentiment misclassification. To overcome such problem, we propose to combine domain knowledge with deep learning. Our proposal includes using sentiment scores, learnt by quadratic programming, to augment training data; and introducing the penalty matrix for enhancing the loss function of cross entropy. When experimented, we achieved a significant improvement in classification results.
Hierarchical Graph Representation Learning with Differentiable Pooling
Venue: arXiv cs.LG 2019
Year: 2019

Recently, graph neural networks (GNNs) have revolutionized the field of graph representation learning through effectively learned node embeddings, and achieved state-of-the-art results in tasks such as node classification and link prediction. However, current GNN methods are inherently flat and do not learn hierarchical representations of graphs---a limitation that is especially problematic for the task of graph classification, where the goal is to predict the label associated with an entire graph. Here we propose DiffPool, a differentiable graph pooling module that can generate hierarchical representations of graphs and can be combined with various graph neural network architectures in an end-to-end fashion. DiffPool learns a differentiable soft cluster assignment for nodes at each layer of a deep GNN, mapping nodes to a set of clusters, which then form the coarsened input for the next GNN layer. Our experimental results show that combining existing GNN methods with DiffPool yields an average improvement of 5-10% accuracy on graph classification benchmarks, compared to all existing pooling approaches, achieving a new state-of-the-art on four out of five benchmark data sets.
Towards a Theory of Mixing Graphs: A Characterization of Perfect Mixability
Venue: arXiv cs.DM 2019
Year: 2019

Some microfluidic lab-on-chip devices contain modules whose function is to mix two fluids, called reactant and buffer, in desired proportions. In one of the technologies for fluid mixing the process can be represented by a directed acyclic graph whose nodes represent micro-mixers and edges represent micro-channels. A micro-mixer has two input channels and two output channels; it receives two fluid droplets, one from each input, mixes them perfectly, and produces two droplets of the mixed fluid on its output channels. Such a mixing graph converts a set I of input droplets into a set T of output droplets, where the droplets are specified by their reactant concentrations. The most fundamental algorithmic question related to mixing graphs is to determine, given an input set I and a target set T, whether there is a mixing graph that converts I into T. We refer to this decision problem as mix-reachability. While the complexity of this problem remains open, we provide a solution to its natural sub-problem, called perfect mixability, in which we ask whether, given a collection C of droplets, there is a mixing graph that mixes C perfectly, producing only droplets whose concentration is the average concentration of C. We provide a complete characterization of such perfectly mixable sets and an efficient algorithm for testing perfect mixability. Further, we prove that any perfectly mixable set has a perfect-mixing graph of polynomial size, and that this graph can be computed in polynomial time.
An Analysis of Two-User Uplink Asynchronous Non-Orthogonal Multiple Access Systems
Venue: arXiv cs.IT 2019
Year: 2019

Recent studies have numerically demonstrated the possible advantages of the asynchronous non-orthogonal multiple access (ANOMA) over the conventional synchronous non-orthogonal multiple access (NOMA). The ANOMA makes use of the oversampling technique by intentionally introducing a timing mismatch between symbols of different users. Focusing on a two-user uplink system, for the first time, we analytically prove that the ANOMA with a sufficiently large frame length can always outperform the NOMA in terms of the sum throughput. To this end, we derive the expression for the sum throughput of the ANOMA as a function of signal-to-noise ratio (SNR), frame length, and normalized timing mismatch. Based on the derived expression, we find that users should transmit at full powers to maximize the sum throughput. In addition, we obtain the optimal timing mismatch as the frame length goes to infinity. Moreover, we comprehensively study the impact of timing error on the ANOMA throughput performance. Two types of timing error, i.e., the synchronization timing error and the coordination timing error, are considered. We derive the throughput loss incurred by both types of timing error and find that the synchronization timing error has a greater impact on the throughput performance compared to the coordination timing error.
Listing All Maximal $k$-Plexes in Temporal Graphs
Venue: arXiv cs.DS 2019
Year: 2019

Many real-world networks evolve over time, that is, new contacts appear and old contacts may disappear. They can be modeled as temporal graphs where interactions between vertices (which represent people in the case of social networks) are represented by time-stamped edges. One of the most fundamental problems in (social) network analysis is community detection, and one of the most basic primitives to model a community is a clique. Addressing the problem of finding communities in temporal networks, Viard et al. [TCS 2016] introduced $Δ$-cliques as a natural temporal version of cliques. Himmel et al. [SNAM 2017] showed how to adapt the well-known Bron-Kerbosch algorithm to enumerate $Δ$-cliques. We continue this work and improve and extend the algorithm of Himmel et al. to enumerate temporal $k$-plexes (notably, cliques are the special case $k=1$). We define a $Δ$-$k$-plex as a set of vertices and a time interval, where during this time interval each vertex has in each consecutive $Δ+ 1$ time steps at least one edge to all but at most $k-1$ vertices in the chosen set of vertices. We develop a recursive algorithm for enumerating all maximal $Δ$-$k$-plexs and perform experiments on real-world social networks that demonstrate the practical feasibility of our approach. In particular, for the special case of $Δ$-1-plexes (that is, $Δ$-cliques), we observe that our algorithm is on average significantly faster than the previous algorithms by Himmel et al. [SNAM 2017] and Viard et al. [IPL 2018] for enumerating $Δ$-cliques.
Physics-based Scene-level Reasoning for Object Pose Estimation in Clutter
Venue: arXiv cs.RO 2019
Year: 2019

This paper focuses on vision-based pose estimation for multiple rigid objects placed in clutter, especially in cases involving occlusions and objects resting on each other. Progress has been achieved recently in object recognition given advancements in deep learning. Nevertheless, such tools typically require a large amount of training data and significant manual effort to label objects. This limits their applicability in robotics, where solutions must scale to a large number of objects and variety of conditions. Moreover, the combinatorial nature of the scenes that could arise from the placement of multiple objects is hard to capture in the training dataset. Thus, the learned models might not produce the desired level of precision required for tasks, such as robotic manipulation. This work proposes an autonomous process for pose estimation that spans from data generation to scene-level reasoning and self-learning. In particular, the proposed framework first generates a labeled dataset for training a Convolutional Neural Network (CNN) for object detection in clutter. These detections are used to guide a scene-level optimization process, which considers the interactions between the different objects present in the clutter to output pose estimates of high precision. Furthermore, confident estimates are used to label online real images from multiple views and re-train the process in a self-learning pipeline. Experimental results indicate that this process is quickly able to identify in cluttered scenes physically-consistent object poses that are more precise than the ones found by reasoning over individual instances of objects. Furthermore, the quality of pose estimates increases over time given the self-learning process.
On Coalitional Manipulation for Multiwinner Elections: Shortlisting
Venue: arXiv cs.MA 2019
Year: 2019

Shortlisting of candidates--selecting a group of "best" candidates--is a special case of multiwinner elections. We provide the first in-depth study of the computational complexity of strategic voting for shortlisting based on the perhaps most basic voting rule in this scenario, l-Bloc (every voter approves l candidates). In particular, we investigate the influence of several tie-breaking mechanisms (e.g., pessimistic versus optimistic) and group evaluation functions (e.g., egalitarian versus utilitarian). Among other things, conclude that in an egalitarian setting strategic voting may indeed be computationally intractable regardless of the tie-breaking rule. Altogether, we provide a fairly comprehensive picture of the computational complexity landscape so far in the literature of this neglected scenario.
On the Error in Phase Transition Computations for Compressed Sensing
Venue: arXiv cs.IT 2019
Year: 2019

Evaluating the statistical dimension is a common tool to determine the asymptotic phase transition in compressed sensing problems with Gaussian ensemble. Unfortunately, the exact evaluation of the statistical dimension is very difficult and it has become standard to replace it with an upper-bound. To ensure that this technique is suitable, [1] has introduced an upper-bound on the gap between the statistical dimension and its approximation. In this work, we first show that the error bound in [1] in some low-dimensional models such as total variation and $\ell_1$ analysis minimization becomes poorly large. Next, we develop a new error bound which significantly improves the estimation gap compared to [1]. In particular, unlike the bound in [1] that is not applicable to settings with overcomplete dictionaries, our bound exhibits a decaying behavior in such cases.
Multicasting Energy and Information Simultaneously
Venue: arXiv cs.IT 2019
Year: 2019

Communication systems for multicasting information and energy simultaneously to more than one user are investigated. In the system under study, a transmitter sends the same message and signal to multiple receivers over distinct and independent channels. The fundamental communication limit under a received energy constraint, called the multicast capacity-energy function, is studied and a single-letter expression is derived. This is based on coding theorems for compound channels. The problem of receiver segmentation, where receivers are divided into related groups, is also considered.
A High-Diversity Transceiver Design for MISO Broadcast Channels
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, the outage behavior and diversity order of the mixture transceiver architecture for multiple-input single-output broadcast channels are analyzed. The mixture scheme groups users with closely-aligned channels and applies superposition coding and successive interference cancellation decoding to each group composed of users with closely-aligned channels, while applying zero-forcing beamforming across semi-orthogonal user groups. In order to enable such analysis, closed-form lower bounds on the achievable rates of a general multiple-input single-output broadcast channel with superposition coding and successive interference cancellation are newly derived. By employing channel-adaptive user grouping and proper power allocation, which ensures that the channel subspaces of user groups have angle larger than a certain threshold, it is shown that the mixture transceiver architecture achieves full diversity order in multiple-input single-output broadcast channels and opportunistically increases the multiplexing gain while achieving full diversity order. Furthermore, the achieved full diversity order is the same as that of the single-user maximum ratio transmit beamforming. Hence, the mixture scheme can provide reliable communication under channel fading for ultra-reliable low latency communication. Numerical results validate our analysis and show the outage superiority of the mixture scheme over conventional transceiver designs for multiple-input single-output broadcast channels.
How To Backdoor Federated Learning
Venue: arXiv cs.CR 2019
Year: 2019

Federated learning enables thousands of participants to construct a deep learning model without sharing their private training data with each other. For example, multiple smartphones can jointly train a next-word predictor for keyboards without revealing what individual users type. We demonstrate that any participant in federated learning can introduce hidden backdoor functionality into the joint global model, e.g., to ensure that an image classifier assigns an attacker-chosen label to images with certain features, or that a word predictor completes certain sentences with an attacker-chosen word. We design and evaluate a new model-poisoning methodology based on model replacement. An attacker selected in a single round of federated learning can cause the global model to immediately reach 100% accuracy on the backdoor task. We evaluate the attack under different assumptions for the standard federated-learning tasks and show that it greatly outperforms data poisoning. Our generic constrain-and-scale technique also evades anomaly detection-based defenses by incorporating the evasion into the attacker's loss function during training.
ModaNet: A Large-Scale Street Fashion Dataset with Polygon Annotations
Venue: arXiv cs.CV 2019
Year: 2019

Understanding clothes from a single image has strong commercial and cultural impacts on modern societies. However, this task remains a challenging computer vision problem due to wide variations in the appearance, style, brand and layering of clothing items. We present a new database called ModaNet, a large-scale collection of images based on Paperdoll dataset. Our dataset provides 55,176 street images, fully annotated with polygons on top of the 1 million weakly annotated street images in Paperdoll. ModaNet aims to provide a technical benchmark to fairly evaluate the progress of applying the latest computer vision techniques that rely on large data for fashion understanding. The rich annotation of the dataset allows to measure the performance of state-of-the-art algorithms for object detection, semantic segmentation and polygon prediction on street fashion images in detail. The polygon-based annotation dataset has been released https://github.com/eBay/modanet, we also host the leaderboard at EvalAI: https://evalai.cloudcv.org/featured-challenges/136/overview.