OpenRaiser/Intern-Atlas huggingface dataset:
Joint group and residual sparse coding for image compressive sensing
Venue: arXiv cs.CV 2019
Year: 2019

Nonlocal self-similarity and group sparsity have been widely utilized in image compressive sensing (CS). However, when the sampling rate is low, the internal prior information of degraded images may be not enough for accurate restoration, resulting in loss of image edges and details. In this paper, we propose a joint group and residual sparse coding method for CS image recovery (JGRSC-CS). In the proposed JGRSC-CS, patch group is treated as the basic unit of sparse coding and two dictionaries (namely internal and external dictionaries) are applied to exploit the sparse representation of each group simultaneously. The internal self-adaptive dictionary is used to remove artifacts, and an external Gaussian Mixture Model (GMM) dictionary, learned from clean training images, is used to enhance details and texture. To make the proposed method effective and robust, the split Bregman method is adopted to reconstruct the whole image. Experimental results manifest the proposed JGRSC-CS algorithm outperforms existing state-of-the-art methods in both peak signal to noise ratio (PSNR) and visual quality.
Fast and Robust Distributed Subgraph Enumeration
Venue: arXiv cs.DB 2019
Year: 2019

We study the classic subgraph enumeration problem under distributed settings. Existing solutions either suffer from severe memory crisis or rely on large indexes, which makes them impractical for very large graphs. Most of them follow a synchronous model where the performance is often bottlenecked by the machine with the worst performance. Motivated by this, in this paper, we propose RADS, a Robust Asynchronous Distributed Subgraph enumeration system. RADS first identifies results that can be found using single-machine algorithms. This strategy not only improves the overall performance but also reduces network communication and memory cost. Moreover, RADS employs a novel region-grouped multi-round expand verify & filter framework which does not need to shuffle and exchange the intermediate results, nor does it need to replicate a large part of the data graph in each machine. This feature not only reduces network communication cost and memory usage, but also allows us to adopt simple strategies for memory control and load balancing, making it more robust. Several heuristics are also used in RADS to further improve the performance. Our experiments verified the superiority of RADS to state-of-the-art subgraph enumeration approaches.
Single-Server Single-Message Online Private Information Retrieval with Side Information
Venue: arXiv cs.IT 2019
Year: 2019

In many practical settings, the user needs to retrieve information from a server in a periodic manner, over multiple rounds of communication. In this paper, we discuss the setting in which this information needs to be retrieved privately, such that the identity of all the information retrieved until the current round is protected. This setting can occur in practical situations in which the user needs to retrieve items from the server or a periodic basis, such that the privacy needs to be guaranteed for all the items been retrieved until the current round. We refer to this setting as an \emph{online private information retrieval} as the user does not know the identities of the future items that need to be retrieved from the server. Following the previous line of work by Kadhe \emph{et al.}~we assume that the user knows a random subset of $M$ messages in the database as a side information which are unknown to the server. Focusing on scalar-linear settings, we characterize the \emph{per-round capacity}, i.e., the maximum achievable download rate at each round, and present a coding scheme that achieves this capacity. The key idea of our scheme is to utilize the data downloaded during the current round as a side information for the subsequent rounds. We show for the setting with $K$ messages stored at the server, the per-round capacity of the scalar-linear setting is $C_1= ({M+1})/{K}$ for round $i=1$ and ${C_i= {(2^{i-1}(M+1))}/{KM}}$ for round $i\geq2$, provided that ${K}/({M+1})$ is a power of $2$.
Programmable Neural Network Trojan for Pre-Trained Feature Extractor
Venue: arXiv cs.CR 2019
Year: 2019

Neural network (NN) trojaning attack is an emerging and important attack model that can broadly damage the system deployed with NN models. Existing studies have explored the outsourced training attack scenario and transfer learning attack scenario in some small datasets for specific domains, with limited numbers of fixed target classes. In this paper, we propose a more powerful trojaning attack method for both outsourced training attack and transfer learning attack, which outperforms existing studies in the capability, generality, and stealthiness. First, The attack is programmable that the malicious misclassification target is not fixed and can be generated on demand even after the victim's deployment. Second, our trojan attack is not limited in a small domain; one trojaned model on a large-scale dataset can affect applications of different domains that reuse its general features. Thirdly, our trojan design is hard to be detected or eliminated even if the victims fine-tune the whole model.
Cooperation Speeds Surfing: Use Co-Bandit!
Venue: arXiv cs.NI 2019
Year: 2019

In this paper, we explore the benefit of cooperation in adversarial bandit settings. As a motivating example, we consider the problem of wireless network selection. Mobile devices are often required to choose the right network to associate with for optimal performance, which is non-trivial. The excellent theoretical properties of EXP3, a leading multi-armed bandit algorithm, suggest that it should work well for this type of problem. Yet, it performs poorly in practice. A major limitation is its slow rate of stabilization. Bandit-style algorithms perform better when global knowledge is available, i.e., when devices receive feedback about all networks after each selection. But, unfortunately, communicating full information to all devices is expensive. Therefore, we address the question of how much information is adequate to achieve better performance. We propose Co-Bandit, a novel cooperative bandit approach, that allows devices to occasionally share their observations and forward feedback received from neighbors; hence, feedback may be received with a delay. Devices perform network selection based on their own observation and feedback from neighbors. As such, they speed up each other's rate of learning. We prove that Co-Bandit is regret-minimizing and retains the convergence property of multiplicative weight update algorithms with full information. Through simulation, we show that a very small amount of information, even with a delay, is adequate to nudge each other to select the right network and yield significantly faster stabilization at the optimal state (about 630x faster than EXP3).
Construction of One-Bit Transmit-Signal Vectors for Downlink MU-MISO Systems with PSK Signaling
Venue: arXiv cs.IT 2019
Year: 2019

We study a downlink multi-user multiple-input single-output (MU-MISO) system in which the base station (BS) has a large number of antennas with cost-effective one-bit digital-to-analog converters (DACs). In this system, we first identify that antenna-selection can yield a non-trivial symbol-error-rate (SER) performance gain by alleviating an error-floor problem. Likewise the previous works on one-bit precoding, finding an optimal transmit-signal vector (encompassing precoding and antenna-selection) requires exhaustive-search due to its combinatorial nature. Motivated by this, we propose a low-complexity two-stage algorithm to directly obtain such transmit-signal vector. In the first stage, we obtain a feasible transmit-signal vector via iterative-hard-thresholding algorithm where the resulting vector ensures that each user's noiseless observation is belong to a desired decision region. In the second stage, a bit-flipping algorithm is employed to refine the feasible vector so that each user's received signal is more robust to additive Gaussian noises. Via simulation results, we demonstrate that the proposed method can yield a more elegant performance-complexity tradeoff than the existing one-bit precoding methods.
On the Power of Symmetric Linear Programs
Venue: arXiv cs.LO 2019
Year: 2019

We consider families of symmetric linear programs (LPs) that decide a property of graphs (or other relational structures) in the sense that, for each size of graph, there is an LP defining a polyhedral lift that separates the integer points corresponding to graphs with the property from those corresponding to graphs without the property. We show that this is equivalent, with at most polynomial blow-up in size, to families of symmetric Boolean circuits with threshold gates. In particular, when we consider polynomial-size LPs, the model is equivalent to definability in a non-uniform version of fixed-point logic with counting (FPC). Known upper and lower bounds for FPC apply to the non-uniform version. In particular, this implies that the class of graphs with perfect matchings has polynomial-size symmetric LPs while we obtain an exponential lower bound for symmetric LPs for the class of Hamiltonian graphs. We compare and contrast this with previous results (Yannakakis 1991) showing that any symmetric LPs for the matching and TSP polytopes have exponential size. As an application, we establish that for random, uniformly distributed graphs, polynomial-size symmetric LPs are as powerful as general Boolean circuits. We illustrate the effect of this on the well-studied planted-clique problem.
DroidMeter: A Measurement Tool to Study Embedded Web Pages
Venue: arXiv cs.SE 2019
Year: 2019

Traditional Web browsing involves typing a URL on a browser and loading a Web page. In contrast, there is another form of Web browsing on mobile devices, i.e., embedded Web browsing, which occurs when mobile apps embed a Web page within the app. When the user navigates to the specific page in the app, the Web page is loaded from within the app. However, little is known about the prevalence or performance of these embedded Web pages. To analyze the embedded Web browsing performance at scale, we design and implement DroidMeter, a tool that can automatically search for embedded Web pages inside apps, trigger page loads, and retrieve performance metrics.
Analysis of the $(μ/μ_I,λ)$-CSA-ES with Repair by Projection Applied to a Conically Constrained Problem
Venue: arXiv cs.NE 2019
Year: 2019

Theoretical analyses of evolution strategies are indispensable for gaining a deep understanding of their inner workings. For constrained problems, rather simple problems are of interest in the current research. This work presents a theoretical analysis of a multi-recombinative evolution strategy with cumulative step size adaptation applied to a conically constrained linear optimization problem. The state of the strategy is modeled by random variables and a stochastic iterative mapping is introduced. For the analytical treatment, fluctuations are neglected and the mean value iterative system is considered. Non-linear difference equations are derived based on one-generation progress rates. Based on that, expressions for the steady state of the mean value iterative system are derived. By comparison with real algorithm runs, it is shown that for the considered assumptions, the theoretical derivations are able to predict the dynamics and the steady state values of the real runs.
The Junk News Aggregator: Examining junk news posted on Facebook, starting with the 2018 US Midterm Elections
Venue: arXiv cs.SI 2019
Year: 2019

In recent years, the phenomenon of online misinformation and junk news circulating on social media has come to constitute an important and widespread problem affecting public life online across the globe, particularly around important political events such as elections. At the same time, there have been calls for more transparency around misinformation on social media platforms, as many of the most popular social media platforms function as "walled gardens," where it is impossible for researchers and the public to readily examine the scale and nature of misinformation activity as it unfolds on the platforms. In order to help address this, we present the Junk News Aggregator, a publicly available interactive web tool, which allows anyone to examine, in near real-time, all of the public content posted to Facebook by important junk news sources in the US. It allows the public to gain access to and examine the latest articles posted on Facebook (the most popular social media platform in the US and one where content is not readily accessible at scale from the open Web), as well as organise them by time, news publisher, and keywords of interest, and sort them based on all eight engagement metrics available on Facebook. Therefore, the Aggregator allows the public to gain insights on the volume, content, key themes, and types and volumes of engagement received by content posted by junk news publishers, in near real-time, hence opening up and offering transparency in these activities as they unfold, at scale across the top most popular junk news publishers. In this way, the Aggregator can help increase transparency around the nature, volume, and engagement with junk news on social media, and serve as a media literacy tool for the public.
Machine Learning for Wireless Communications in the Internet of Things: A Comprehensive Survey
Venue: arXiv cs.NI 2019
Year: 2019

The Internet of Things (IoT) is expected to require more effective and efficient wireless communications than ever before. For this reason, techniques such as spectrum sharing, dynamic spectrum access, extraction of signal intelligence and optimized routing will soon become essential components of the IoT wireless communication paradigm. Given that the majority of the IoT will be composed of tiny, mobile, and energy-constrained devices, traditional techniques based on a priori network optimization may not be suitable, since (i) an accurate model of the environment may not be readily available in practical scenarios; (ii) the computational requirements of traditional optimization techniques may prove unbearable for IoT devices. To address the above challenges, much research has been devoted to exploring the use of machine learning to address problems in the IoT wireless communications domain. This work provides a comprehensive survey of the state of the art in the application of machine learning techniques to address key problems in IoT wireless communications with an emphasis on its ad hoc networking aspect. First, we present extensive background notions of machine learning techniques. Then, by adopting a bottom-up approach, we examine existing work on machine learning for the IoT at the physical, data-link and network layer of the protocol stack. Thereafter, we discuss directions taken by the community towards hardware implementation to ensure the feasibility of these techniques. Additionally, before concluding, we also provide a brief discussion of the application of machine learning in IoT beyond wireless communication. Finally, each of these discussions is accompanied by a detailed analysis of the related open problems and challenges.
An information theoretic approach to the autoencoder
Venue: arXiv cs.LG 2019
Year: 2019

We present a variation of the Autoencoder (AE) that explicitly maximizes the mutual information between the input data and the hidden representation. The proposed model, the InfoMax Autoencoder (IMAE), by construction is able to learn a robust representation and good prototypes of the data. IMAE is compared both theoretically and then computationally with the state of the art models: the Denoising and Contractive Autoencoders in the one-hidden layer setting and the Variational Autoencoder in the multi-layer case. Computational experiments are performed with the MNIST and Fashion-MNIST datasets and demonstrate particularly the strong clusterization performance of IMAE.
Can Adversarial Networks Hallucinate Occluded People With a Plausible Aspect?
Venue: arXiv cs.CV 2019
Year: 2019

When you see a person in a crowd, occluded by other persons, you miss visual information that can be used to recognize, re-identify or simply classify him or her. You can imagine its appearance given your experience, nothing more. Similarly, AI solutions can try to hallucinate missing information with specific deep learning architectures, suitably trained with people with and without occlusions. The goal of this work is to generate a complete image of a person, given an occluded version in input, that should be a) without occlusion b) similar at pixel level to a completely visible people shape c) capable to conserve similar visual attributes (e.g. male/female) of the original one. For the purpose, we propose a new approach by integrating the state-of-the-art of neural network architectures, namely U-nets and GANs, as well as discriminative attribute classification nets, with an architecture specifically designed to de-occlude people shapes. The network is trained to optimize a Loss function which could take into account the aforementioned objectives. As well we propose two datasets for testing our solution: the first one, occluded RAP, created automatically by occluding real shapes of the RAP dataset (which collects also attributes of the people aspect); the second is a large synthetic dataset, AiC, generated in computer graphics with data extracted from the GTA video game, that contains 3D data of occluded objects by construction. Results are impressive and outperform any other previous proposal. This result could be an initial step to many further researches to recognize people and their behavior in an open crowded world.
Siamese Networks with Location Prior for Landmark Tracking in Liver Ultrasound Sequences
Venue: arXiv cs.CV 2019
Year: 2019

Image-guided radiation therapy can benefit from accurate motion tracking by ultrasound imaging, in order to minimize treatment margins and radiate moving anatomical targets, e.g., due to breathing. One way to formulate this tracking problem is the automatic localization of given tracked anatomical landmarks throughout a temporal ultrasound sequence. For this, we herein propose a fully-convolutional Siamese network that learns the similarity between pairs of image regions containing the same landmark. Accordingly, it learns to localize and thus track arbitrary image features, not only predefined anatomical structures. We employ a temporal consistency model as a location prior, which we combine with the network-predicted location probability map to track a target iteratively in ultrasound sequences. We applied this method on the dataset of the Challenge on Liver Ultrasound Tracking (CLUST) with competitive results, where our work is the first to effectively apply CNNs on this tracking problem, thanks to our temporal regularization.
A Tool for Spatio-Temporal Analysis of Social Anxiety with Twitter Data
Venue: arXiv cs.CL 2019
Year: 2019

In this paper, we present a tool for analyzing spatio-temporal distribution of social anxiety. Twitter, one of the most popular social network services, has been chosen as data source for analysis of social anxiety. Tweets (posted on the Twitter) contain various emotions and thus these individual emotions reflect social atmosphere and public opinion, which are often dependent on spatial and temporal factors. The reason why we choose anxiety among various emotions is that anxiety is very important emotion that is useful for observing and understanding social events of communities. We develop a machine learning based tool to analyze the changes of social atmosphere spatially and temporally. Our tool classifies whether each Tweet contains anxious content or not, and also estimates degree of Tweet anxiety. Furthermore, it also visualizes spatio-temporal distribution of anxiety as a form of web application, which is incorporated with physical map, word cloud, search engine and chart viewer. Our tool is applied to a big tweet data in South Korea to illustrate its usefulness for exploring social atmosphere and public opinion spatio-temporally.
Fundamental Limits of Approximate Gradient Coding
Venue: arXiv cs.DC 2019
Year: 2019

It has been established that when the gradient coding problem is distributed among $n$ servers, the computation load (number of stored data partitions) of each worker is at least $s+1$ in order to resists $s$ stragglers. This scheme incurs a large overhead when the number of stragglers $s$ is large. In this paper, we focus on a new framework called \emph{approximate gradient coding} to mitigate stragglers in distributed learning. We show that, to exactly recover the gradient with high probability, the computation load is lower bounded by $O(\log(n)/\log(n/s))$. We also propose a code that exactly matches such lower bound. We identify a fundamental three-fold tradeoff for any approximate gradient coding scheme $d\geq O(\log(1/ε)/\log(n/s))$, where $d$ is the computation load, $ε$ is the error of gradient. We give an explicit code construction based on random edge removal process that achieves the derived tradeoff. We implement our schemes and demonstrate the advantage of the approaches over the current fastest gradient coding strategies.
TigerGraph: A Native MPP Graph Database
Venue: arXiv cs.DB 2019
Year: 2019

We present TigerGraph, a graph database system built from the ground up to support massively parallel computation of queries and analytics. TigerGraph's high-level query language, GSQL, is designed for compatibility with SQL, while simultaneously allowing NoSQL programmers to continue thinking in Bulk-Synchronous Processing (BSP) terms and reap the benefits of high-level specification. GSQL is sufficiently high-level to allow declarative SQL-style programming, yet sufficiently expressive to concisely specify the sophisticated iterative algorithms required by modern graph analytics and traditionally coded in general-purpose programming languages like C++ and Java. We report very strong scale-up and scale-out performance over a benchmark we published on GitHub for full reproducibility.
Confidence-based Graph Convolutional Networks for Semi-Supervised Learning
Venue: arXiv cs.LG 2019
Year: 2019

Predicting properties of nodes in a graph is an important problem with applications in a variety of domains. Graph-based Semi-Supervised Learning (SSL) methods aim to address this problem by labeling a small subset of the nodes as seeds and then utilizing the graph structure to predict label scores for the rest of the nodes in the graph. Recently, Graph Convolutional Networks (GCNs) have achieved impressive performance on the graph-based SSL task. In addition to label scores, it is also desirable to have confidence scores associated with them. Unfortunately, confidence estimation in the context of GCN has not been previously explored. We fill this important gap in this paper and propose ConfGCN, which estimates labels scores along with their confidences jointly in GCN-based setting. ConfGCN uses these estimated confidences to determine the influence of one node on another during neighborhood aggregation, thereby acquiring anisotropic capabilities. Through extensive analysis and experiments on standard benchmarks, we find that ConfGCN is able to outperform state-of-the-art baselines. We have made ConfGCN's source code available to encourage reproducible research.