OpenRaiser/Intern-Atlas huggingface dataset:
REGAL: Representation Learning-based Graph Alignment
Venue: arXiv cs.SI 2018
Year: 2018

Problems involving multiple networks are prevalent in many scientific and other domains. In particular, network alignment, or the task of identifying corresponding nodes in different networks, has applications across the social and natural sciences. Motivated by recent advancements in node representation learning for single-graph tasks, we propose REGAL (REpresentation learning-based Graph ALignment), a framework that leverages the power of automatically-learned node representations to match nodes across different graphs. Within REGAL we devise xNetMF, an elegant and principled node embedding formulation that uniquely generalizes to multi-network problems. Our results demonstrate the utility and promise of unsupervised representation learning-based network alignment in terms of both speed and accuracy. REGAL runs up to 30x faster in the representation learning stage than comparable methods, outperforms existing network alignment methods by 20 to 30% accuracy on average, and scales to networks with millions of nodes each.
Nonconvex Matrix Factorization from Rank-One Measurements
Venue: arXiv cs.IT 2018
Year: 2018

We consider the problem of recovering low-rank matrices from random rank-one measurements, which spans numerous applications including covariance sketching, phase retrieval, quantum state tomography, and learning shallow polynomial neural networks, among others. Our approach is to directly estimate the low-rank factor by minimizing a nonconvex quadratic loss function via vanilla gradient descent, following a tailored spectral initialization. When the true rank is small, this algorithm is guaranteed to converge to the ground truth (up to global ambiguity) with near-optimal sample complexity and computational complexity. To the best of our knowledge, this is the first guarantee that achieves near-optimality in both metrics. In particular, the key enabler of near-optimal computational guarantees is an implicit regularization phenomenon: without explicit regularization, both spectral initialization and the gradient descent iterates automatically stay within a region incoherent with the measurement vectors. This feature allows one to employ much more aggressive step sizes compared with the ones suggested in prior literature, without the need of sample splitting.
Improving the accuracy of the fast inverse square root algorithm
Venue: arXiv cs.NA 2018
Year: 2018

We present improved algorithms for fast calculation of the inverse square root for single-precision floating-point numbers. The algorithms are much more accurate than the famous fast inverse square root algorithm and have the same or similar computational cost. The main idea of our work consists in modifying the Newton-Raphson method and demanding that the maximal error is as small as possible. Such modification is possible when the distribution of Newton-Raphson corrections is not symmetric (e.g., if they are non-positive functions).
Large Neighborhood-Based Metaheuristic and Branch-and-Price for the Pickup and Delivery Problem with Split Loads
Venue: arXiv cs.AI 2018
Year: 2018

We consider the multi-vehicle one-to-one pickup and delivery problem with split loads, a NP-hard problem linked with a variety of applications for bulk product transportation, bike-sharing systems and inventory re-balancing. This problem is notoriously difficult due to the interaction of two challenging vehicle routing attributes, "pickups and deliveries" and "split deliveries". This possibly leads to optimal solutions of a size that grows exponentially with the instance size, containing multiple visits per customer pair, even in the same route. To solve this problem, we propose an iterated local search metaheuristic as well as a branch-and-price algorithm. The core of the metaheuristic consists of a new large neighborhood search, which reduces the problem of finding the best insertion combination of a pickup and delivery pair into a route (with possible splits) to a resource-constrained shortest path and knapsack problem. Similarly, the branch-and-price algorithm uses sophisticated labeling techniques, route relaxations, pre-processing and branching rules for an efficient resolution. Our computational experiments on classical single-vehicle instances demonstrate the excellent performance of the metaheuristic, which produces new best known solutions for 92 out of 93 test instances, and outperforms all previous algorithms. Experimental results on new multi-vehicle instances with distance constraints are also reported. The branch-and-price algorithm produces optimal solutions for instances with up to 20 pickup-and-delivery pairs, and very accurate solutions are found by the metaheuristic.
Minimum length RNA folding trajectories
Venue: arXiv cs.DS 2018
Year: 2018

The Kinfold and KFOLD programs for RNA folding kinetics implement the Gillespie algorithm to generate stochastic folding trajectories from an initial structure s to a target structure t, in which each intermediate secondary structure is obtained from its predecessor by the addition, removal or shift of a single base pair. Define MS2 distance between secondary structures s and t to be the minimum path length to refold s to t, where a move from MS2 is applied in each step. We describe algorithms to compute the shortest MS2 folding trajectory between any two given RNA secondary structures. These algorithms include an optimal integer programming (IP) algorithm, an accurate and efficient near-optimal algorithm, a greedy algorithm, a branch-and-bound algorithm, and an optimal algorithm if one allows intermediate structures to contain pseudoknots. Our optimal IP [resp. near-optimal IP] algorithm maximizes [resp. approximately maximizes] the number of shifts and minimizes [resp. approximately minimizes] the number of base pair additions and removals by applying integer programming to (essentially) solve the minimum feedback vertex set (FVS) problem for the RNA conflict digraph, then applies topological sort to tether subtrajectories into the final optimal folding trajectory. We prove NP-hardness of the problem to determine the minimum barrier energy over all possible MS2 folding pathways, and conjecture that computing the MS2 distance between arbitrary secondary structures is NP-hard. Since our optimal IP algorithm relies on the FVS, known to be NP-complete for arbitrary digraphs, we compare the family of RNA conflict digraphs with the following classes of digraphs (planar, reducible flow graph, Eulerian, and tournament) for which FVS is known to be either polynomial time computable or NP-hard. Source code available at http://bioinformatics.bc.edu/clotelab/MS2distance/.
Sequence-to-Sequence Prediction of Vehicle Trajectory via LSTM Encoder-Decoder Architecture
Venue: arXiv cs.LG 2018
Year: 2018

In this paper, we propose a deep learning based vehicle trajectory prediction technique which can generate the future trajectory sequence of surrounding vehicles in real time. We employ the encoder-decoder architecture which analyzes the pattern underlying in the past trajectory using the long short-term memory (LSTM) based encoder and generates the future trajectory sequence using the LSTM based decoder. This structure produces the $K$ most likely trajectory candidates over occupancy grid map by employing the beam search technique which keeps the $K$ locally best candidates from the decoder output. The experiments conducted on highway traffic scenarios show that the prediction accuracy of the proposed method is significantly higher than the conventional trajectory prediction techniques.
An Overview of Physical Layer Security with Finite-Alphabet Signaling
Venue: arXiv cs.IT 2018
Year: 2018

Providing secure communications over the physical layer with the objective of achieving perfect secrecy without requiring a secret key has been receiving growing attention within the past decade. The vast majority of the existing studies in the area of physical layer security focus exclusively on the scenarios where the channel inputs are Gaussian distributed. However, in practice, the signals employed for transmission are drawn from discrete signal constellations such as phase shift keying and quadrature amplitude modulation. Hence, understanding the impact of the finite-alphabet input constraints and designing secure transmission schemes under this assumption is a mandatory step towards a practical implementation of physical layer security. With this motivation, this article reviews recent developments on physical layer security with finite-alphabet inputs. We explore transmit signal design algorithms for single-antenna as well as multi-antenna wiretap channels under different assumptions on the channel state information at the transmitter. Moreover, we present a review of the recent results on secure transmission with discrete signaling for various scenarios including multi-carrier transmission systems, broadcast channels with confidential messages, cognitive multiple access and relay networks. Throughout the article, we stress the important behavioral differences of discrete versus Gaussian inputs in the context of the physical layer security. We also present an overview of practical code construction over Gaussian and fading wiretap channels, and we discuss some open problems and directions for future research.
Using 3D Hahn Moments as A Computational Representation of ATS Drugs Molecular Structure
Venue: arXiv cs.CV 2018
Year: 2018

The campaign against drug abuse is fought by all countries, most notably on ATS drugs. The technical limitations of the current test kits to detect new brand of ATS drugs present a challenge to law enforcement authorities and forensic laboratories. Meanwhile, new molecular imaging devices which allowed mankind to characterize the physical 3D molecular structure have been recently introduced, and it can be used to remedy the limitations of existing drug test kits. Thus, a new type of 3D molecular structure representation technique should be developed to cater the 3D molecular structure acquired physically using these molecular imaging devices. One of the applications of image processing methods to represent a 3D image is 3D moments, and this study formulates a new 3D moments technique, namely 3D Hahn moments, to represent the 3D molecular structure of ATS drugs. The performance of the proposed technique was analysed using drug chemical structures obtained from UNODC for the ATS drugs, while non-ATS drugs are obtained randomly from ChemSpider database. The evaluation shows the technique is qualified to be further explored in the future works to be fully compatible with ATS drug identification domain.
Solving Large-Scale Minimum-Weight Triangulation Instances to Provable Optimality
Venue: arXiv cs.CG 2018
Year: 2018

We consider practical methods for the problem of finding a minimum-weight triangulation (MWT) of a planar point set, a classic problem of computational geometry with many applications. While Mulzer and Rote proved in 2006 that computing an MWT is NP-hard, Beirouti and Snoeyink showed in 1998 that computing provably optimal solutions for MWT instances of up to 80,000 uniformly distributed points is possible, making use of clever heuristics that are based on geometric insights. We show that these techniques can be refined and extended to instances of much bigger size and different type, based on an array of modifications and parallelizations in combination with more efficient geometric encodings and data structures. As a result, we are able to solve MWT instances with up to 30,000,000 uniformly distributed points in less than 4 minutes to provable optimality. Moreover, we can compute optimal solutions for a vast array of other benchmark instances that are not uniformly distributed, including normally distributed instances (up to 30,000,000 points), all point sets in the TSPLIB (up to 85,900 points), and VLSI instances with up to 744,710 points. This demonstrates that from a practical point of view, MWT instances can be handled quite well, despite their theoretical difficulty.
Sim-to-Real Optimization of Complex Real World Mobile Network with Imperfect Information via Deep Reinforcement Learning from Self-play
Venue: arXiv cs.AI 2018
Year: 2018

Mobile network that millions of people use every day is one of the most complex systems in the world. Optimization of mobile network to meet exploding customer demand and reduce capital/operation expenditures poses great challenges. Despite recent progress, application of deep reinforcement learning (DRL) to complex real world problem still remains unsolved, given data scarcity, partial observability, risk and complex rules/dynamics in real world, as well as the huge reality gap between simulation and real world. To bridge the reality gap, we introduce a Sim-to-Real framework to directly transfer learning from simulation to real world via graph convolutional neural network (CNN) - by abstracting partially observable mobile network into graph, then distilling domain-variant irregular graph into domain-invariant tensor in locally Euclidean space as input to CNN -, domain randomization and multi-task learning. We use a novel self-play mechanism to encourage competition among DRL agents for best record on multiple tasks via simulated annealing, just like athletes compete for world record in decathlon. We also propose a decentralized multi-agent, competitive and cooperative DRL method to coordinate the actions of multi-cells to maximize global reward and minimize negative impact to neighbor cells. Using 6 field trials on commercial mobile networks, we demonstrate for the first time that a DRL agent can successfully transfer learning from simulation to complex real world problem with imperfect information, complex rules/dynamics, huge state/action space, and multi-agent interactions, without any training in the real world.
A Method to Translate Order-Sorted Algebras to Many-Sorted Algebras
Venue: arXiv cs.PL 2018
Year: 2018

Order-sorted algebras and many sorted algebras exist in a long history with many different implementations and applications. A lot of language specifications have been defined in order-sorted algebra frameworks such as the language specifications in K (an order-sorted algebra framework). The biggest problem in a lot of the order-sorted algebra frameworks is that even if they might allow developers to write programs and language specifications easily, but they do not have a large set of tools to provide reasoning infrastructures to reason about the specifications built on the frameworks, which are very common in some many-sorted algebra framework such as Isabelle/HOL, Coq and FDR. This fact brings us the necessity to marry the worlds of order-sorted algebras and many sorted algebras. In this paper, we propose an algorithm to translate a strictly sensible order-sorted algebra to a many-sorted one in a restricted domain by requiring the order-sorted algebra to be strictly sensible. The key idea of the translation is to add an equivalence relation called core equality to the translated many-sorted algebras. By defining this relation, we reduce the complexity of translating a strictly sensible order-sorted algebra to a many-sorted one, make the translated many-sorted algebra equations only increasing by a very small amount of new equations, and keep the number of rewrite rules in the algebra in the same amount. We then prove the order-sorted algebra and its translated many-sorted algebra are bisimilar. To the best of our knowledge, our translation and bisimilar proof is the first attempt in translating and relating an order-sorted algebra with a many-sorted one in a way that keeps the size of the translated many-sorted algebra relatively small.
Reduced Dependency Spaces for Existential Parameterised Boolean Equation Systems
Venue: arXiv cs.LO 2018
Year: 2018

A parameterised Boolean equation system (PBES) is a set of equations that defines sets satisfying the equations as the least and/or greatest fixed-points. Thus this system is regarded as a declarative program defining predicates, where a program execution returns whether a given ground atomic formula holds or not. The program execution corresponds to the membership problem of PBESs, which is however undecidable in general. This paper proposes a subclass of PBESs which expresses universal-quantifiers free formulas, and studies a technique to solve the problem on it. We use the fact that the membership problem is reduced to the problem whether a proof graph exists. To check the latter problem, we introduce a so-called dependency space which is a graph containing all of the minimal proof graphs. Dependency spaces are, however, infinite in general. Thus, we propose some conditions for equivalence relations to preserve the result of the membership problem, then we identify two vertices as the same under the relation. In this sense, dependency spaces possibly result in a finite graph. We show some examples having infinite dependency spaces which are reducible to finite graphs by equivalence relations. We provide a procedure to construct finite dependency spaces and show the soundness of the procedure. We also implement the procedure using an SMT solver and experiment on some examples including a downsized McCarthy 91 function.
Space Improvements and Equivalences in a Functional Core Language
Venue: arXiv cs.PL 2018
Year: 2018

We explore space improvements in LRP, a polymorphically typed call-by-need functional core language. A relaxed space measure is chosen for the maximal size usage during an evaluation. It abstracts from the details of the implementation via abstract machines, but it takes garbage collection into account and thus can be seen as a realistic approximation of space usage. The results are: a context lemma for space improving translations and for space equivalences, all but one reduction rule of the calculus are shown to be space improvements, and for the exceptional one we show bounds on the space increase. Several further program transformations are shown to be space improvements or space equivalences in particular the translation into machine expressions is a space equivalence. We also classify certain space-worsening transformations as space-leaks or as space-safe. These results are a step forward in making predictions about the change in runtime space behavior of optimizing transformations in call-by-need functional languages.
Human and Smart Machine Co-Learning with Brain Computer Interface
Venue: arXiv cs.AI 2018
Year: 2018

Machine learning has become a very popular approach for cybernetics systems, and it has always been considered important research in the Computational Intelligence area. Nevertheless, when it comes to smart machines, it is not just about the methodologies. We need to consider systems and cybernetics as well as include human in the loop. The purpose of this article is as follows: (1) To integrate the open source Facebook AI Research (FAIR) DarkForest program of Facebook with Item Response Theory (IRT), to the new open learning system, namely, DDF learning system; (2) To integrate DDF Go with Robot namely Robotic DDF Go system; (3) To invite the professional Go players to attend the activity to play Go games on site with a smart machine. The research team will apply this technology to education, such as, playing games to enhance the children concentration on learning mathematics, languages, and other topics. With the detected brainwaves, the robot will be able to speak some words that are very much to the point for the students and to assist the teachers in classroom in the future.
Closing the loop on multisensory interactions: A neural architecture for multisensory causal inference and recalibration
Venue: arXiv cs.NE 2018
Year: 2018

When the brain receives input from multiple sensory systems, it is faced with the question of whether it is appropriate to process the inputs in combination, as if they originated from the same event, or separately, as if they originated from distinct events. Furthermore, it must also have a mechanism through which it can keep sensory inputs calibrated to maintain the accuracy of its internal representations. We have developed a neural network architecture capable of i) approximating optimal multisensory spatial integration, based on Bayesian causal inference, and ii) recalibrating the spatial encoding of sensory systems. The architecture is based on features of the dorsal processing hierarchy, including the spatial tuning properties of unisensory neurons and the convergence of different sensory inputs onto multisensory neurons. Furthermore, we propose that these unisensory and multisensory neurons play dual roles in i) encoding spatial location as separate or integrated estimates and ii) accumulating evidence for the independence or relatedness of multisensory stimuli. We further propose that top-down feedback connections spanning the dorsal pathway play key a role in recalibrating spatial encoding at the level of early unisensory cortices. Our proposed architecture provides possible explanations for a number of human electrophysiological and neuroimaging results and generates testable predictions linking neurophysiology with behaviour.
Unboundedness problems for languages of vector addition systems
Venue: arXiv cs.FL 2018
Year: 2018

A vector addition system (VAS) with an initial and a final marking and transition labels induces a language. In part because the reachability problem in VAS remains far from being well-understood, it is difficult to devise decision procedures for such languages. This is especially true for checking properties that state the existence of infinitely many words of a particular shape. Informally, we call these \emph{unboundedness properties}. We present a simple set of axioms for predicates that can express unboundedness properties. Our main result is that such a predicate is decidable for VAS languages as soon as it is decidable for regular languages. Among other results, this allows us to show decidability of (i)~separability by bounded regular languages, (ii)~unboundedness of occurring factors from a language $K$ with mild conditions on $K$, and (iii)~universality of the set of factors.
Sponge-Based Control-Flow Protection for IoT Devices
Venue: arXiv cs.CR 2018
Year: 2018

Embedded devices in the Internet of Things (IoT) face a wide variety of security challenges. For example, software attackers perform code injection and code-reuse attacks on their remote interfaces, and physical access to IoT devices allows to tamper with code in memory, steal confidential Intellectual Property (IP), or mount fault attacks to manipulate a CPU's control flow. In this work, we present Sponge-based Control Flow Protection (SCFP). SCFP is a stateful, sponge-based scheme to ensure the confidentiality of software IP and its authentic execution on IoT devices. At compile time, SCFP encrypts and authenticates software with instruction-level granularity. During execution, an SCFP hardware extension between the CPU's fetch and decode stage continuously decrypts and authenticates instructions. Sponge-based authenticated encryption in SCFP yields fine-grained control-flow integrity and thus prevents code-reuse, code-injection, and fault attacks on the code and the control flow. In addition, SCFP withstands any modification of software in memory. For evaluation, we extended a RISC-V core with SCFP and fabricated a real System on Chip (SoC). The average overhead in code size and execution time of SCFP on this design is 19.8% and 9.1%, respectively, and thus meets the requirements of embedded IoT devices.