OpenRaiser/Intern-Atlas huggingface dataset:
Subset Sampling For Progressive Neural Network Learning
Venue: arXiv cs.LG 2020
Year: 2020

Progressive Neural Network Learning is a class of algorithms that incrementally construct the network's topology and optimize its parameters based on the training data. While this approach exempts the users from the manual task of designing and validating multiple network topologies, it often requires an enormous number of computations. In this paper, we propose to speed up this process by exploiting subsets of training data at each incremental training step. Three different sampling strategies for selecting the training samples according to different criteria are proposed and evaluated. We also propose to perform online hyperparameter selection during the network progression, which further reduces the overall training time. Experimental results in object, scene and face recognition problems demonstrate that the proposed approach speeds up the optimization procedure considerably while operating on par with the baseline approach exploiting the entire training set throughout the training process.
Enabling Low-Power OFDM for IoT by Exploiting Asymmetric Clock Rates
Venue: arXiv cs.NI 2020
Year: 2020

The conventional high-speed Wi-Fi has recently become a contender for low-power Internet-of-Things (IoT) communications. OFDM continues its adoption in the new IoT Wi-Fi standard due to its spectrum efficiency that can support the demand of massive IoT connectivity. While the IoT Wi-Fi standard offers many new features to improve power and spectrum efficiency, the basic physical layer (PHY) structure of transceiver design still conforms to its conventional design rationale where access points (AP) and clients employ the same OFDM PHY. In this paper, we argue that current Wi-Fi PHY design does not take full advantage of the inherent asymmetry between AP and IoT. To fill the gap, we propose an asymmetric design where IoT devices transmit uplink packets using the lowest power while pushing all the decoding burdens to the AP side. Such a design utilizes the sufficient power and computational resources at AP to trade for the transmission (TX) power of IoT devices. The core technique enabling this asymmetric design is that the AP takes full power of its high clock rate to boost the decoding ability. We provide an implementation of our design and show that it can reduce up to 88% of the IoT's TX power when the AP sets $8\times$ clock rate.
Kalman meets Bellman: Improving Policy Evaluation through Value Tracking
Venue: arXiv cs.LG 2020
Year: 2020

Policy evaluation is a key process in Reinforcement Learning (RL). It assesses a given policy by estimating the corresponding value function. When using parameterized value functions, common approaches minimize the sum of squared Bellman temporal-difference errors and receive a point-estimate for the parameters. Kalman-based and Gaussian-processes based frameworks were suggested to evaluate the policy by treating the value as a random variable. These frameworks can learn uncertainties over the value parameters and exploit them for policy exploration. When adopting these frameworks to solve deep RL tasks, several limitations are revealed: excessive computations in each optimization step, difficulty with handling batches of samples which slows training and the effect of memory in stochastic environments which prevents off-policy learning. In this work, we discuss these limitations and propose to overcome them by an alternative general framework, based on the extended Kalman filter. We devise an optimization method, called Kalman Optimization for Value Approximation (KOVA) that can be incorporated as a policy evaluation component in policy optimization algorithms. KOVA minimizes a regularized objective function that concerns both parameter and noisy return uncertainties. We analyze the properties of KOVA and present its performance on deep RL control tasks.
How Impersonators Exploit Instagram to Generate Fake Engagement?
Venue: arXiv cs.SI 2020
Year: 2020

Impersonators on Online Social Networks such as Instagram are playing an important role in the propagation of the content. These entities are the type of nefarious fake accounts that intend to disguise a legitimate account by making similar profiles. In addition to having impersonated profiles, we observed a considerable engagement from these entities to the published posts of verified accounts. Toward that end, we concentrate on the engagement of impersonators in terms of active and passive engagements which is studied in three major communities including ``Politician'', ``News agency'', and ``Sports star'' on Instagram. Inside each community, four verified accounts have been selected. Based on the implemented approach in our previous studies, we have collected 4.8K comments, and 2.6K likes across 566 posts created from 3.8K impersonators during 7 months. Our study shed light into this interesting phenomena and provides a surprising observation that can help us to understand better how impersonators engaging themselves inside Instagram in terms of writing Comments and leaving Likes.
Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG
Venue: arXiv cs.CC 2020
Year: 2020

In this work, we establish lower-bounds against memory bounded algorithms for distinguishing between natural pairs of related distributions from samples that arrive in a streaming setting. In our first result, we show that any algorithm that distinguishes between uniform distribution on $\{0,1\}^n$ and uniform distribution on an $n/2$-dimensional linear subspace of $\{0,1\}^n$ with non-negligible advantage needs $2^{Ω(n)}$ samples or $Ω(n^2)$ memory. Our second result applies to distinguishing outputs of Goldreich's local pseudorandom generator from the uniform distribution on the output domain. Specifically, Goldreich's pseudorandom generator $G$ fixes a predicate $P:\{0,1\}^k \rightarrow \{0,1\}$ and a collection of subsets $S_1, S_2, \ldots, S_m \subseteq [n]$ of size $k$. For any seed $x \in \{0,1\}^n$, it outputs $P(x_{S_1}), P(x_{S_2}), \ldots, P(x_{S_m})$ where $x_{S_i}$ is the projection of $x$ to the coordinates in $S_i$. We prove that whenever $P$ is $t$-resilient (all non-zero Fourier coefficients of $(-1)^P$ are of degree $t$ or higher), then no algorithm, with $<n^ε$ memory, can distinguish the output of $G$ from the uniform distribution on $\{0,1\}^m$ with a large inverse polynomial advantage, for stretch $m \le \left(\frac{n}{t}\right)^{\frac{(1-ε)}{36}\cdot t}$ (barring some restrictions on $k$). The lower bound holds in the streaming model where at each time step $i$, $S_i\subseteq [n]$ is a randomly chosen (ordered) subset of size $k$ and the distinguisher sees either $P(x_{S_i})$ or a uniformly random bit along with $S_i$. Our proof builds on the recently developed machinery for proving time-space trade-offs (Raz 2016 and follow-ups) for search/learning problems.
Extracting hierarchical backbones from bipartite networks
Venue: arXiv cs.SI 2020
Year: 2020

We propose a method for extracting hierarchical backbones from a bipartite network. Our method leverages the observation that a hierarchical relationship between two nodes in a bipartite network is often manifested as an asymmetry in the conditional probability of observing the connections to them from the other node set. Our method estimates both the importance and direction of the hierarchical relationship between a pair of nodes, thereby providing a flexible way to identify the essential part of the networks. Using semi-synthetic benchmarks, we show that our method outperforms existing methods at identifying planted hierarchy while offering more flexibility. Application of our method to empirical datasets---a bipartite network of skills and individuals as well as the network between gene products and Gene Ontology (GO) terms---demonstrates the possibility of automatically extracting or augmenting ontology from data.
Investigating Extensions to Random Walk Based Graph Embedding
Venue: arXiv cs.LG 2020
Year: 2020

Graph embedding has recently gained momentum in the research community, in particular after the introduction of random walk and neural network based approaches. However, most of the embedding approaches focus on representing the local neighborhood of nodes and fail to capture the global graph structure, i.e. to retain the relations to distant nodes. To counter that problem, we propose a novel extension to random walk based graph embedding, which removes a percentage of least frequent nodes from the walks at different levels. By this removal, we simulate farther distant nodes to reside in the close neighborhood of a node and hence explicitly represent their connection. Besides the common evaluation tasks for graph embeddings, such as node classification and link prediction, we evaluate and compare our approach against related methods on shortest path approximation. The results indicate, that extensions to random walk based methods (including our own) improve the predictive performance only slightly - if at all.
Information Theory as a Means of Determining the Main Factors Affecting the Processors Architecture
Venue: arXiv cs.IT 2020
Year: 2020

In this article we are investigating the computers development process in the past decades in order to identify the factors that influence it the most. We describe such factors and use them to predict the direction of further development. To solve these problems, we use the concept of the Computer Capacity, which allows us to estimate the performance of computers theoretically, relying only on the description of its architecture.
A Depth-Aware Swap Insertion Scheme for the Qubit Mapping Problem
Venue: arXiv cs.ET 2020
Year: 2020

The rapid progress of physical implementation of quantum computers paved the way of realising the design of tools to help users write quantum programs for any given quantum devices. The physical constraints inherent to the current NISQ architectures prevent most quantum algorithms from being directly executed on quantum devices. To enable two-qubit gates in the algorithm, existing works focus on inserting SWAP gates to dynamically remap logical qubits to physical qubits. However, their schemes lack the consideration of the depth of generated quantum circuits. In this work, we propose a depth-aware SWAP insertion scheme for qubit mapping problem in the NISQ era.
Improving Tracking through Human-Robot Sensory Augmentation
Venue: arXiv cs.RO 2020
Year: 2020

This paper introduces human-robot sensory augmentation and illustrates it on a tracking task, where performance can be improved by the exchange of sensory information between the robot and its human user. It was recently found that during interaction between humans, the partners use each other's sensory information to improve their own sensing, thus also their performance and learning. In this paper, we develop a computational model of this unique human ability, and use it to build a novel control framework for human-robot interaction. The human partner's control is formulated as a feedback control with unknown control gains and desired trajectory. A Kalman filter is used to estimate first the control gains and then the desired trajectory. The estimated human partner's desired trajectory is used as augmented sensory information about the system and combined with the robot's measurement to estimate an uncertain target trajectory. Simulations and an implementation of the presented framework on a robotic interface validate the proposed observer-predictor pair for a tracking task. The results obtained using this robot demonstrate how the human user's control can be identified, and exhibit similar benefits of this sensory augmentation as was observed between interacting humans.
Vector Gaussian Successive Refinement With Degraded Side Information
Venue: arXiv cs.IT 2020
Year: 2020

We investigate the problem of the successive refinement for Wyner-Ziv coding with degraded side information and obtain a complete characterization of the rate region for the quadratic vector Gaussian case. The achievability part is based on the evaluation of the Tian-Diggavi inner bound that involves Gaussian auxiliary random vectors. For the converse part, a matching outer bound is obtained with the aid of a new extremal inequality. Herein, the proof of this extremal inequality depends on the integration of the monotone path argument and the doubling trick as well as information-estimation relations.
Secure Status Updates under Eavesdropping: Age of Information-based Physical Layer Security Metrics
Venue: arXiv cs.CR 2020
Year: 2020

This letter studies the problem of maintaining information freshness under passive eavesdropping attacks. The classical three-node wiretap channel model is considered, in which a source aims to send its latest status wirelessly to its intended destination, while protecting the message from being overheard by an eavesdropper. Considering that conventional channel capacity-based secrecy metrics are no longer adequate to measure the information timeliness in status update systems, we define two new age of information-based metrics to characterize the secrecy performance of the considered system. We further propose, analyze, and optimize a randomized stationary transmission policy implemented at the source for further enhancing the secrecy performance. Simulation results are provided to validate our analysis and optimization.
Leveraging Linear Quadratic Regulator Cost and Energy Consumption for Ultra-Reliable and Low-Latency IoT Control Systems
Venue: arXiv cs.IT 2020
Year: 2020

To efficiently support the real-time control applications, networked control systems operating with ultra-reliable and low-latency communications (URLLCs) become fundamental technology for future Internet of things (IoT). However, the design of control, sensing and communications is generally isolated at present. In this paper, we propose the joint optimization of control cost and energy consumption for a centralized wireless networked control system. Specifically, with the ``sensing-then-control'' protocol, we first develop an optimization framework which jointly takes control, sensing and communications into account. In this framework, we derive the spectral efficiency, linear quadratic regulator cost and energy consumption. Then, a novel performance metric called the \textit{energy-to-control efficiency} is proposed for the IoT control system. In addition, we optimize the energy-to-control efficiency while guaranteeing the requirements of URLLCs, thereupon a general and complex max-min joint optimization problem is formulated for the IoT control system. To optimally solve the formulated problem by reasonable complexity, we propose two radio resource allocation algorithms. Finally, simulation results show that our proposed algorithms can significantly improve the energy-to-control efficiency for the IoT control system with URLLCs.
ROBin: Known-Plaintext Attack Resistant Orthogonal Blinding via Channel Randomization
Venue: arXiv cs.CR 2020
Year: 2020

Orthogonal blinding based schemes for wireless physical layer security aim to achieve secure communication by injecting noise into channels orthogonal to the main channel and corrupting the eavesdropper's signal reception. These methods, albeit practical, have been proven vulnerable against multi-antenna eavesdroppers who can filter the message from the noise. The vulnerability is rooted in the fact that the main channel state remains static in spite of the noise injection, which allows an eavesdropper to estimate it promptly via known symbols and filter out the noise. Our proposed scheme leverages a reconfigurable antenna for Alice to rapidly change the channel state during transmission and a compressive sensing based algorithm for her to predict and cancel the changing effects for Bob. As a result, the communication between Alice and Bob remains clear, whereas randomized channel state prevents Eve from launching the known-plaintext attack. We formally analyze the security of the scheme against both single and multi-antenna eavesdroppers and identify its unique anti-eavesdropping properties due to the artificially created fast-changing channel. We conduct extensive simulations and real-world experiments to evaluate its performance. Empirical results show that our scheme can suppress Eve's attack success rate to the level of random guessing, even if she knows all the symbols transmitted through other antenna modes.
Updates-Aware Graph Pattern based Node Matching
Venue: arXiv cs.DB 2020
Year: 2020

Graph Pattern based Node Matching (GPNM) is to find all the matches of the nodes in a data graph GD based on a given pattern graph GP. GPNM has become increasingly important in many applications, e.g., group finding and expert recommendation. In real scenarios, both GP and GD are updated frequently. However, the existing GPNM methods either need to perform a new GPNM procedure from scratch to deliver the node matching results based on the updated GP and GD or incrementally perform the GPNM procedure for each of the updates, leading to low efficiency. Therefore, there is a pressing need for a new method to efficiently deliver the node matching results on the updated graphs. In this paper, we first analyze and detect the elimination relationships between the updates. Then, we construct an Elimination Hierarchy Tree (EH-Tree) to index these elimination relationships. In order to speed up the GPNM process, we propose a graph partition method and then propose a new updates-aware GPNM method, called UA-GPNM, considering the single-graph elimination relationships among the updates in a single graph of GP or GD, and also the cross-graph elimination relationships between the updates in GP and the updates in GD. UA-GPNM first delivers the GPNM result of an initial query, and then delivers the GPNM result of a subsequent query, based on the initial GPNM result and the multiple updates that occur between two queries. The experimental results on five real-world social graphs demonstrate that our proposed UA-GPNM is much more efficient than the state-of-the-art GPNM methods.
Deflecting Adversarial Attacks
Venue: arXiv cs.LG 2020
Year: 2020

There has been an ongoing cycle where stronger defenses against adversarial attacks are subsequently broken by a more advanced defense-aware attack. We present a new approach towards ending this cycle where we "deflect'' adversarial attacks by causing the attacker to produce an input that semantically resembles the attack's target class. To this end, we first propose a stronger defense based on Capsule Networks that combines three detection mechanisms to achieve state-of-the-art detection performance on both standard and defense-aware attacks. We then show that undetected attacks against our defense often perceptually resemble the adversarial target class by performing a human study where participants are asked to label images produced by the attack. These attack images can no longer be called "adversarial'' because our network classifies them the same way as humans do.
Generating random bigraphs with preferential attachment
Venue: arXiv cs.DM 2020
Year: 2020

The bigraph theory is a relatively young, yet formally rigorous, mathematical framework encompassing Robin Milner's previous work on process calculi, on the one hand, and provides a generic meta-model for complex systems such as multi-agent systems, on the other. A bigraph $F = \langle F^P, F^L\rangle$ is a superposition of two independent graph structures comprising a place graph $F^P$ (i.e., a forest) and a link graph $F^L$ (i.e., a hypergraph), sharing the same node set, to express locality and communication of processes independently from each other. In this paper, we take some preparatory steps towards an algorithm for generating random bigraphs with preferential attachment feature w.r.t. $F^P$ and assortative (disassortative) linkage pattern w.r.t. $F^L$. We employ parameters allowing one to fine-tune the characteristics of the generated bigraph structures. To study the pattern formation properties of our algorithmic model, we analyze several metrics from graph theory based on artificially created bigraphs under different configurations. Bigraphs provide a quite useful and expressive semantic for process calculi for mobile and global ubiquitous computing. So far, this subject has not received attention in the bigraph-related scientific literature. However, artificial models may be particularly useful for simulation and evaluation of real-world applications in ubiquitous systems necessitating random structures.
On the Complexity of the Cycles based Synthesis of Ternary Reversible Circuits
Venue: arXiv cs.ET 2020
Year: 2020

The paper studies the main aspects of the realization of 2 x 2 ternary reversible circuits based on cycles, considering the results of the realization of all 362,880 2 x 2 ternary reversible functions. It has been shown that in most cases, realizations obtained with the MMD+ algorithm have a lower complexity (in terms of cost) than realizations based on cycles. In the paper it is shown under which conditions realizations based on transpositions may have a higher or a lower cost than realizations using larger cycles. Finally it is shown that there are a few special cases where realizations based on transpositions have the same cost or possibly lower cost than the MMD+ based realizations. Aspects of scaleability are considered in terms of 2 x 2-based n x n reversible circuits.
Decentralized Validation for Non-malicious Arbitrary Fault Tolerance in Paxos
Venue: arXiv cs.DC 2020
Year: 2020

Fault-tolerant distributed systems offer high reliability because even if faults in their components occur, they do not exhibit erroneous behavior. Depending on the fault model adopted, hardware and software errors that do not result in a process crashing are usually not tolerated. To tolerate these rather common failures the usual solution is to adopt a stronger fault model, such as the arbitrary or Byzantine fault model. Algorithms created for this fault model, however, are considerably more complex and require more system resources than the ones developed for less strict fault models. One approach to reach a middle ground is the non-malicious arbitrary fault model. This model assumes it is possible to detect and filter faults with a given probability, if these faults are not created with malicious intent, allowing the isolation and mapping of these faults to benign faults. In this paper we describe how we incremented an implementation of active replication in the non-malicious fault model with a basic type of distributed validation, where a deviation from the expected algorithm behavior will make a process crash. We experimentally evaluate this implementation using a fault injection framework showing that it is feasible to extend the concept of non-malicious failures beyond hardware failures.