OpenRaiser/Intern-Atlas huggingface dataset:
EXIT Analysis for Community Detection
Venue: arXiv cs.SI 2019
Year: 2019

This paper employs the extrinsic information transfer (EXIT) method, a technique imported from the analysis of the iterative decoding of error control codes, to study the performance of belief propagation in community detection in the presence of side information. We consider both the detection of a single (hidden) community, as well as the problem of identifying two symmetric communities. For single community detection, this paper demonstrates the suitability of EXIT to predict the asymptotic phase transition for weak recovery. More importantly, EXIT analysis is leveraged to produce useful insights such as the performance of belief propagation near the threshold. For two symmetric communities, the asymptotic residual error for belief propagation is calculated under finite-alphabet side information, generalizing a previous result with noisy labels. EXIT analysis is used to illuminate the effect of side information on community detection, its relative importance depending on the correlation of the graphical information with node labels, as well as the effect of side information on residual errors.
Fake News Detection via NLP is Vulnerable to Adversarial Attacks
Venue: arXiv cs.SI 2019
Year: 2019

News plays a significant role in shaping people's beliefs and opinions. Fake news has always been a problem, which wasn't exposed to the mass public until the past election cycle for the 45th President of the United States. While quite a few detection methods have been proposed to combat fake news since 2015, they focus mainly on linguistic aspects of an article without any fact checking. In this paper, we argue that these models have the potential to misclassify fact-tampering fake news as well as under-written real news. Through experiments on Fakebox, a state-of-the-art fake news detector, we show that fact tampering attacks can be effective. To address these weaknesses, we argue that fact checking should be adopted in conjunction with linguistic characteristics analysis, so as to truly separate fake news from real news. A crowdsourced knowledge graph is proposed as a straw man solution to collecting timely facts about news events.
Deep Generative Graph Distribution Learning for Synthetic Power Grids
Venue: arXiv cs.SI 2019
Year: 2019

Power system studies require the topological structures of real-world power networks; however, such data is confidential due to important security concerns. Thus, power grid synthesis (PGS), i.e., creating realistic power grids that imitate actual power networks, has gained significant attention. In this letter, we cast PGS into a graph distribution learning (GDL) problem where the probability distribution functions (PDFs) of the nodes (buses) and edges (lines) are captured. A novel deep GDL (DeepGDL) model is proposed to learn the topological patterns of buses/lines with their physical features (e.g., power injection and line impedance). Having a deep nonlinear recurrent structure, DeepGDL understands complex nonlinear topological properties and captures the graph PDF. Sampling from the obtained PDF, we are able to create a large set of realistic networks that all resemble the original power grid. Simulation results show the significant accuracy of our created synthetic power grids in terms of various topological metrics and power flow measurements.
Quantitative Verification of Masked Arithmetic Programs against Side-Channel Attacks
Venue: arXiv cs.CR 2019
Year: 2019

Power side-channel attacks, which can deduce secret data via statistical analysis, have become a serious threat. Masking is an effective countermeasure for reducing the statistical dependence between secret data and side-channel information. However, designing masking algorithms is an error-prone process. In this paper, we propose a hybrid approach combing type inference and model-counting to verify masked arithmetic programs against side-channel attacks. The type inference allows an efficient, lightweight procedure to determine most observable variables whereas model-counting accounts for completeness. In case that the program is not perfectly masked, we also provide a method to quantify the security level of the program. We implement our methods in a tool QMVerif and evaluate it on cryptographic benchmarks. The experimental results show the effectiveness and efficiency of our approach.
Detecting Multiple Communities Using Quantum Annealing on the D-Wave System
Venue: arXiv cs.OH 2019
Year: 2019

A very important problem in combinatorial optimization is partitioning a network into communities of densely connected nodes; where the connectivity between nodes inside a particular community is large compared to the connectivity between nodes belonging to different ones. This problem is known as community detection, and has become very important in various fields of science including chemistry, biology and social sciences. The problem of community detection is a twofold problem that consists of determining the number of communities and, at the same time, finding those communities. This drastically increases the solution space for heuristics to work on, compared to traditional graph partitioning problems. In many of the scientific domains in which graphs are used, there is the need to have the ability to partition a graph into communities with the ``highest quality'' possible since the presence of even small isolated communities can become crucial to explain a particular phenomenon. We have explored community detection using the power of quantum annealers, and in particular the D-Wave 2X and 2000Q machines. It turns out that the problem of detecting at most two communities naturally fits into the architecture of a quantum annealer with almost no need of reformulation. This paper addresses a systematic study of detecting two or more communities in a network using a quantum annealer.
Attribute-Guided Sketch Generation
Venue: arXiv cs.CV 2019
Year: 2019

Facial attributes are important since they provide a detailed description and determine the visual appearance of human faces. In this paper, we aim at converting a face image to a sketch while simultaneously generating facial attributes. To this end, we propose a novel Attribute-Guided Sketch Generative Adversarial Network (ASGAN) which is an end-to-end framework and contains two pairs of generators and discriminators, one of which is used to generate faces with attributes while the other one is employed for image-to-sketch translation. The two generators form a W-shaped network (W-net) and they are trained jointly with a weight-sharing constraint. Additionally, we also propose two novel discriminators, the residual one focusing on attribute generation and the triplex one helping to generate realistic looking sketches. To validate our model, we have created a new large dataset with 8,804 images, named the Attribute Face Photo & Sketch (AFPS) dataset which is the first dataset containing attributes associated to face sketch images. The experimental results demonstrate that the proposed network (i) generates more photo-realistic faces with sharper facial attributes than baselines and (ii) has good generalization capability on different generative tasks.
Optimal and Automated Deployment for Microservices
Venue: arXiv cs.DC 2019
Year: 2019

Microservices are highly modular and scalable Service Oriented Architectures. They underpin automated deployment practices like Continuous Deployment and Autoscaling. In this paper, we formalize these practices and show that automated deployment - proven undecidable in the general case - is algorithmically treatable for microservices. Our key assumption is that the configuration life-cycle of a microservice is split into two phases: (i) creation, which entails establishing initial connections with already available microservices, and (ii) subsequent binding/unbinding with other microservices. To illustrate the applicability of our approach, we implement an automatic optimal deployment tool and compute deployment plans for a realistic microservice architecture, modeled in the Abstract Behavioral Specification (ABS) language.
Squeezed Very Deep Convolutional Neural Networks for Text Classification
Venue: arXiv cs.LG 2019
Year: 2019

Most of the research in convolutional neural networks has focused on increasing network depth to improve accuracy, resulting in a massive number of parameters which restricts the trained network to platforms with memory and processing constraints. We propose to modify the structure of the Very Deep Convolutional Neural Networks (VDCNN) model to fit mobile platforms constraints and keep performance. In this paper, we evaluate the impact of Temporal Depthwise Separable Convolutions and Global Average Pooling in the network parameters, storage size, and latency. The squeezed model (SVDCNN) is between 10x and 20x smaller, depending on the network depth, maintaining a maximum size of 6MB. Regarding accuracy, the network experiences a loss between 0.4% and 1.3% and obtains lower latencies compared to the baseline model.
Semi-supervised Learning in Network-Structured Data via Total Variation Minimization
Venue: arXiv cs.LG 2019
Year: 2019

We propose and analyze a method for semi-supervised learning from partially-labeled network-structured data. Our approach is based on a graph signal recovery interpretation under a clustering hypothesis that labels of data points belonging to the same well-connected subset (cluster) are similar valued. This lends naturally to learning the labels by total variation (TV) minimization, which we solve by applying a recently proposed primal-dual method for non-smooth convex optimization. The resulting algorithm allows for a highly scalable implementation using message passing over the underlying empirical graph, which renders the algorithm suitable for big data applications. By applying tools of compressed sensing, we derive a sufficient condition on the underlying network structure such that TV minimization recovers clusters in the empirical graph of the data. In particular, we show that the proposed primal-dual method amounts to maximizing network flows over the empirical graph of the dataset. Moreover, the learning accuracy of the proposed algorithm is linked to the set of network flows between data points having known labels. The effectiveness and scalability of our approach is verified by numerical experiments.
Tradeoff Between Delay and High SNR Capacity in Quantized MIMO Systems
Venue: arXiv cs.IT 2019
Year: 2019

Analog-to-digital converters (ADCs) are a major contributor to the power consumption of multiple-input multiple-output (MIMO) communication systems with large number of antennas. Use of low resolution ADCs has been proposed as a means to decrease power consumption in MIMO receivers. However, reducing the ADC resolution leads to performance loss in terms of achievable transmission rates. In order to mitigate the rate-loss, the receiver can perform analog processing of the received signals before quantization. Prior works consider one-shot analog processing where at each channel-use, analog linear combinations of the received signals are fed to a set of one-bit threshold ADCs. In this paper, a receiver architecture is proposed which uses a sequence of delay elements to allow for blockwise linear combining of the received analog signals. In the high signal to noise ratio regime, it is shown that the proposed architecture achieves the maximum achievable transmission rate given a fixed number of one-bit ADCs. Furthermore, a tradeoff between transmission rate and the number of delay elements is identified which quantifies the increase in maximum achievable rate as the number of delay elements is increased.
Clustered Millimeter Wave Networks with Non-Orthogonal Multiple Access
Venue: arXiv cs.IT 2019
Year: 2019

We introduce clustered millimeter wave networks with invoking non-orthogonal multiple access~(NOMA) techniques, where the NOMA users are modeled as Poisson cluster processes and each cluster contains a base station (BS) located at the center. To provide realistic directional beamforming, an actual antenna array pattern is deployed at all BSs. We propose three distance-dependent user selection strategies to appraise the path loss impact on the performance of our considered networks. With the aid of such strategies, we derive tractable analytical expressions for the coverage probability and system throughput. Specifically, closed-form expressions are deduced under a sparse network assumption to improve the calculation efficiency. It theoretically demonstrates that the large antenna scale benefits the near user, while such influence for the far user is fluctuant due to the randomness of the beamforming. Moreover, the numerical results illustrate that: 1) the proposed system outperforms traditional orthogonal multiple access techniques and the commonly considered NOMA-mmWave scenarios with the random beamforming; 2) the coverage probability has a negative correlation with the variance of intra-cluster receivers; 3) 73 GHz is the best carrier frequency for near user and 28 GHz is the best choice for far user; 4) an optimal number of the antenna elements exists for maximizing the system throughput.
Surrogate Gradient Learning in Spiking Neural Networks
Venue: arXiv cs.NE 2019
Year: 2019

Spiking neural networks are nature's versatile solution to fault-tolerant and energy efficient signal processing. To translate these benefits into hardware, a growing number of neuromorphic spiking neural network processors attempt to emulate biological neural networks. These developments have created an imminent need for methods and tools to enable such systems to solve real-world signal processing problems. Like conventional neural networks, spiking neural networks can be trained on real, domain specific data. However, their training requires overcoming a number of challenges linked to their binary and dynamical nature. This article elucidates step-by-step the problems typically encountered when training spiking neural networks, and guides the reader through the key concepts of synaptic plasticity and data-driven learning in the spiking setting. To that end, it gives an overview of existing approaches and provides an introduction to surrogate gradient methods, specifically, as a particularly flexible and efficient method to overcome the aforementioned challenges.
Secure Massive MIMO Communication with Low-resolution DACs
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we investigate secure transmission in a massive multiple-input multiple-output (MIMO) system adopting low-resolution digital-to-analog converters (DACs). Artificial noise (AN) is deliberately transmitted simultaneously with the confidential signals to degrade the eavesdropper's channel quality. By applying the Bussgang theorem, a DAC quantization model is developed which facilitates the analysis of the asymptotic achievable secrecy rate. Interestingly, for a fixed power allocation factor $ϕ$, low-resolution DACs typically result in a secrecy rate loss, but in certain cases they provide superior performance, e.g., at low signal-to-noise ratio (SNR). Specifically, we derive a closed-form SNR threshold which determines whether low-resolution or high-resolution DACs are preferable for improving the secrecy rate. Furthermore, a closed-form expression for the optimal $ϕ$ is derived. With AN generated in the null-space of the user channel and the optimal $ϕ$, low-resolution DACs inevitably cause secrecy rate loss. On the other hand, for random AN with the optimal $ϕ$, the secrecy rate is hardly affected by the DAC resolution because the negative impact of the quantization noise can be compensated for by reducing the AN power. All the derived analytical results are verified by numerical simulations.
Lyapunov-based Safe Policy Optimization for Continuous Control
Venue: arXiv cs.LG 2019
Year: 2019

We study continuous action reinforcement learning problems in which it is crucial that the agent interacts with the environment only through safe policies, i.e.,~policies that do not take the agent to undesirable situations. We formulate these problems as constrained Markov decision processes (CMDPs) and present safe policy optimization algorithms that are based on a Lyapunov approach to solve them. Our algorithms can use any standard policy gradient (PG) method, such as deep deterministic policy gradient (DDPG) or proximal policy optimization (PPO), to train a neural network policy, while guaranteeing near-constraint satisfaction for every policy update by projecting either the policy parameter or the action onto the set of feasible solutions induced by the state-dependent linearized Lyapunov constraints. Compared to the existing constrained PG algorithms, ours are more data efficient as they are able to utilize both on-policy and off-policy data. Moreover, our action-projection algorithm often leads to less conservative policy updates and allows for natural integration into an end-to-end PG training pipeline. We evaluate our algorithms and compare them with the state-of-the-art baselines on several simulated (MuJoCo) tasks, as well as a real-world indoor robot navigation problem, demonstrating their effectiveness in terms of balancing performance and constraint satisfaction. Videos of the experiments can be found in the following link: https://drive.google.com/file/d/1pzuzFqWIE710bE2U6DmS59AfRzqK2Kek/view?usp=sharing.
Online Algorithms for Constructing Linear-size Suffix Trie
Venue: arXiv cs.DS 2019
Year: 2019

The suffix trees are fundamental data structures for various kinds of string processing. The suffix tree of a string $T$ of length $n$ has $O(n)$ nodes and edges, and the string label of each edge is encoded by a pair of positions in $T$. Thus, even after the tree is built, the input text $T$ needs to be kept stored and random access to $T$ is still needed. The linear-size suffix tries (LSTs), proposed by Crochemore et al. [Linear-size suffix tries, TCS 638:171-178, 2016], are a `stand-alone' alternative to the suffix trees. Namely, the LST of a string $T$ of length $n$ occupies $O(n)$ total space, and supports pattern matching and other tasks in the same efficiency as the suffix tree without the need to store the input text $T$. Crochemore et al. proposed an offline algorithm which transforms the suffix tree of $T$ into the LST of $T$ in $O(n \log σ)$ time and $O(n)$ space, where $σ$ is the alphabet size. In this paper, we present two types of online algorithms which `directly' construct the LST, from right to left, and from left to right, without constructing the suffix tree as an intermediate structure. Both algorithms construct the LST incrementally when a new symbol is read, and do not access to the previously read symbols. The right-to-left construction algorithm works in $O(n \log σ)$ time and $O(n)$ space and the left-to-right construction algorithm works in $O(n (\log σ+ \log n / \log \log n))$ time and $O(n)$ space. The main feature of our algorithms is that the input text does not need to be stored.
Towards Fair Deep Clustering With Multi-State Protected Variables
Venue: arXiv cs.LG 2019
Year: 2019

Fair clustering under the disparate impact doctrine requires that population of each protected group should be approximately equal in every cluster. Previous work investigated a difficult-to-scale pre-processing step for $k$-center and $k$-median style algorithms for the special case of this problem when the number of protected groups is two. In this work, we consider a more general and practical setting where there can be many protected groups. To this end, we propose Deep Fair Clustering, which learns a discriminative but fair cluster assignment function. The experimental results on three public datasets with different types of protected attribute show that our approach can steadily improve the degree of fairness while only having minor loss in terms of clustering quality.
On the negation of a Dempster-Shafer belief structure based on maximum uncertainty allocation
Venue: arXiv cs.AI 2019
Year: 2019

Probability theory and Dempster-Shafer theory are two germane theories to represent and handle uncertain information. Recent study suggested a transformation to obtain the negation of a probability distribution based on the maximum entropy. Correspondingly, determining the negation of a belief structure, however, is still an open issue in Dempster-Shafer theory, which is very important in theoretical research and practical applications. In this paper, a negation transformation for belief structures is proposed based on maximum uncertainty allocation, and several important properties satisfied by the transformation have been studied. The proposed negation transformation is more general and could totally compatible with existing transformation for probability distributions.
On the $k$-error linear complexity of binary sequences derived from the discrete logarithm in finite fields
Venue: arXiv cs.CR 2019
Year: 2019

Let $q=p^r$ be a power of an odd prime $p$. We study binary sequences $σ=(σ_0,σ_1,\ldots)$ with entries in $\{0,1\}$ defined by using the quadratic character $χ$ of the finite field $\mathbb{F}_q$: $$ σ_n=\left\{ \begin{array}{ll} 0,& \mathrm{if}\quad n= 0,\\ (1-χ(ξ_n))/2,&\mathrm{if}\quad 1\leq n< q, \end{array} \right. $$ for the ordered elements $ξ_0,ξ_1,\ldots,ξ_{q-1}\in \mathbb{F}_q$. The $σ$ is Legendre sequence if $r=1$. Our first contribution is to prove a lower bound on the linear complexity of $σ$ for $r\geq 2$. The bound improves some results of Meidl and Winterhof. Our second contribution is to study the $k$-error linear complexity of $σ$ for $r=2$. It seems that we cannot settle the case when $r>2$ and leave it open.
Discovering Underlying Person Structure Pattern with Relative Local Distance for Person Re-identification
Venue: arXiv cs.CV 2019
Year: 2019

Modeling the underlying person structure for person re-identification (re-ID) is difficult due to diverse deformable poses, changeable camera views and imperfect person detectors. How to exploit underlying person structure information without extra annotations to improve the performance of person re-ID remains largely unexplored. To address this problem, we propose a novel Relative Local Distance (RLD) method that integrates a relative local distance constraint into convolutional neural networks (CNNs) in an end-to-end way. It is the first time that the relative local constraint is proposed to guide the global feature representation learning. Specially, a relative local distance matrix is computed by using feature maps and then regarded as a regularizer to guide CNNs to learn a structure-aware feature representation. With the discovered underlying person structure, the RLD method builds a bridge between the global and local feature representation and thus improves the capacity of feature representation for person re-ID. Furthermore, RLD also significantly accelerates deep network training compared with conventional methods. The experimental results show the effectiveness of RLD on the CUHK03, Market-1501, and DukeMTMC-reID datasets. Code is available at \url{https://github.com/Wanggcong/RLD_codes}.
Mask-RCNN and U-net Ensembled for Nuclei Segmentation
Venue: arXiv cs.CV 2019
Year: 2019

Nuclei segmentation is both an important and in some ways ideal task for modern computer vision methods, e.g. convolutional neural networks. While recent developments in theory and open-source software have made these tools easier to implement, expert knowledge is still required to choose the right model architecture and training setup. We compare two popular segmentation frameworks, U-Net and Mask-RCNN in the nuclei segmentation task and find that they have different strengths and failures. To get the best of both worlds, we develop an ensemble model to combine their predictions that can outperform both models by a significant margin and should be considered when aiming for best nuclei segmentation performance.