OpenRaiser/Intern-Atlas huggingface dataset:
Discovering Bands from Graphs
Venue: arXiv cs.DS 2019
Year: 2019

Discovering the underlying structure of a given graph is one of the fundamental goals in graph mining. Given a graph, we can often order vertices in a way that neighboring vertices have a higher probability of being connected to each other. This implies that the edges form a band around the diagonal in the adjacency matrix. Such structure may rise for example if the graph was created over time: each vertex had an active time interval during which the vertex was connected with other active vertices. The goal of this paper is to model this phenomenon. To this end, we formulate an optimization problem: given a graph and an integer $K$, we want to order graph vertices and partition the ordered adjacency matrix into $K$ bands such that bands closer to the diagonal are more dense. We measure the goodness of a segmentation using the log-likelihood of a log-linear model, a flexible family of distributions containing many standard distributions. We divide the problem into two subproblems: finding the order and finding the bands. We show that discovering bands can be done in polynomial time with isotonic regression, and we also introduce a heuristic iterative approach. For discovering the order we use Fiedler order accompanied with a simple combinatorial refinement. We demonstrate empirically that our heuristic works well in practice.
3D Quantum Cuts for Automatic Segmentation of Porous Media in Tomography Images
Venue: arXiv cs.CV 2019
Year: 2019

Binary segmentation of volumetric images of porous media is a crucial step towards gaining a deeper understanding of the factors governing biogeochemical processes at minute scales. Contemporary work primarily revolves around primitive techniques based on global or local adaptive thresholding that have known common drawbacks in image segmentation. Moreover, absence of a unified benchmark prohibits quantitative evaluation, which further clouds the impact of existing methodologies. In this study, we tackle the issue on both fronts. Firstly, by drawing parallels with natural image segmentation, we propose a novel, and automatic segmentation technique, 3D Quantum Cuts (QCuts-3D) grounded on a state-of-the-art spectral clustering technique. Secondly, we curate and present a publicly available dataset of 68 multiphase volumetric images of porous media with diverse solid geometries, along with voxel-wise ground truth annotations for each constituting phase. We provide comparative evaluations between QCuts-3D and the current state-of-the-art over this dataset across a variety of evaluation metrics. The proposed systematic approach achieves a 26% increase in AUROC while achieving a substantial reduction of the computational complexity of the state-of-the-art competitors. Moreover, statistical analysis reveals that the proposed method exhibits significant robustness against the compositional variations of porous media.
FPGA/DNN Co-Design: An Efficient Design Methodology for IoT Intelligence on the Edge
Venue: arXiv cs.CV 2019
Year: 2019

While embedded FPGAs are attractive platforms for DNN acceleration on edge-devices due to their low latency and high energy efficiency, the scarcity of resources of edge-scale FPGA devices also makes it challenging for DNN deployment. In this paper, we propose a simultaneous FPGA/DNN co-design methodology with both bottom-up and top-down approaches: a bottom-up hardware-oriented DNN model search for high accuracy, and a top-down FPGA accelerator design considering DNN-specific characteristics. We also build an automatic co-design flow, including an Auto-DNN engine to perform hardware-oriented DNN model search, as well as an Auto-HLS engine to generate synthesizable C code of the FPGA accelerator for explored DNNs. We demonstrate our co-design approach on an object detection task using PYNQ-Z1 FPGA. Results show that our proposed DNN model and accelerator outperform the state-of-the-art FPGA designs in all aspects including Intersection-over-Union (IoU) (6.2% higher), frames per second (FPS) (2.48X higher), power consumption (40% lower), and energy efficiency (2.5X higher). Compared to GPU-based solutions, our designs deliver similar accuracy but consume far less energy.
PUNCH: Positive UNlabelled Classification based information retrieval in Hyperspectral images
Venue: arXiv cs.IR 2019
Year: 2019

Hyperspectral images of land-cover captured by airborne or satellite-mounted sensors provide a rich source of information about the chemical composition of the materials present in a given place. This makes hyperspectral imaging an important tool for earth sciences, land-cover studies, and military and strategic applications. However, the scarcity of labeled training examples and spatial variability of spectral signature are two of the biggest challenges faced by hyperspectral image classification. In order to address these issues, we aim to develop a framework for material-agnostic information retrieval in hyperspectral images based on Positive-Unlabelled (PU) classification. Given a hyperspectral scene, the user labels some positive samples of a material he/she is looking for and our goal is to retrieve all the remaining instances of the query material in the scene. Additionally, we require the system to work equally well for any material in any scene without the user having to disclose the identity of the query material. This material-agnostic nature of the framework provides it with superior generalization abilities. We explore two alternative approaches to solve the hyperspectral image classification problem within this framework. The first approach is an adaptation of non-negative risk estimation based PU learning for hyperspectral data. The second approach is based on one-versus-all positive-negative classification where the negative class is approximately sampled using a novel spectral-spatial retrieval model. We propose two annotator models - uniform and blob - that represent the labelling patterns of a human annotator. We compare the performances of the proposed algorithms for each annotator model on three benchmark hyperspectral image datasets - Indian Pines, Pavia University and Salinas.
Thinkey: A Scalable Blockchain Architecture
Venue: arXiv cs.CR 2019
Year: 2019

This paper presents Thinkey, an efficient, secure, infinitely scalable and decentralized blockchain architecture. It ensures system correctness and liveness by a multi-layer structure. In particular, the system is based on a double-chain architecture and uses a multi-layer consensus protocol to guarantee consistency. Thinkey also uses a novel account model which is based on Actor Model to support the complex logic in the multi-chain structure. Experiment results show that the proposed Thinkey architecture can achieve higher throughput as the number of nodes increases.
One-dimensional guarded fragments
Venue: arXiv cs.LO 2019
Year: 2019

We call a first-order formula one-dimensional if its every maximal block of existential (universal) quantifiers leaves at most one variable free. We consider the one-dimensional restrictions of the guarded fragment, GF, and the tri-guarded fragment, TGF, the latter being a recent extension of GF in which quantification for subformulas with at most two free variables need not be guarded, and which thus may be seen as a unification of GF and the two-variable fragment, FO2. We denote the resulting formalisms, resp., GF1, and TGF1. We show that GF1 has an exponential model property and NExpTime-complete satisfiability problem (that is, it is easier than full GF). For TGF1 we show that it is decidable, has the finite model property, and its satisfiability problem is TwoExpTime-complete (NExpTime-complete in the absence of equality). All the above-mentioned results are obtained for signatures with no constants. We finally discuss the impact of their addition, observing that constants do not spoil the decidability but increase the complexity of the satisfiability problem.
TDM/WDM over AWGR Based Passive Optical Network Data Centre Architecture
Venue: arXiv cs.NI 2019
Year: 2019

Passive Optical Data Centre Networks have been developed due to the performance limitations in current data centres to provide high performance within data centre networks. An AWGR based passive optical network data centre architecture is evaluated using a TDM/WDM multiple access technique to provision the flow of traffic among the network efficiently. A Mixed Integer Linear Programming model is developed to optimise resource allocation in the architecture. Using WDM-TDM as a multiple access technique helps in solving issues such as oversubscription and congestion by allowing servers to make simultaneous transmissions of packets in different time slots. The results show that the provisioning / allocation of resource within the architecture is improved with improvements of up to 75% in resource utilisation.
A new Hybrid Lattice Attack on Galbraith's Binary LWE Cryptosystem
Venue: arXiv cs.CR 2019
Year: 2019

LWE-based cryptosystems are an attractive alternative to traditional ones in the post-quantum era. To minimize the storage cost of part of its public key - a $256 \times 640$ integer matrix, $\textbf{T}$ - a binary version of $\textbf{T}$ has been proposed. One component of its ciphertext, $\textbf{c}_{1}$ is computed as $\textbf{c}_{1} = \textbf{Tu}$ where $\textbf{u}$ is an ephemeral secret. Knowing $\textbf{u}$, the plaintext can be deduced. Given $\textbf{c}_{1}$ and $\textbf{T}$, Galbraith's challenge is to compute $\textbf{u}$ with existing computing resources in 1 year. Our hybrid approach guesses and removes some bits of the solution vector and maps the problem of solving the resulting sub-instance to the Closest Vector Problem in Lattice Theory. The lattice-based approach reduces the number of bits to be guessed while the initial guess based on LP relaxation reduces the number of subsequent guesses to polynomial rather than exponential in the number of guessed bits. Further enhancements partition the set of guessed bits and use a 2-step application of LP. Given the constraint of processor cores and time, a one-time training algorithm learns the optimal combination of partitions yielding a success rate of 9\% - 23\% with 1000 - 100,000 cores in 1 year. This compares favourably with earlier work that yielded 2\% success with 3000 cores.
Hyper-Parameter Tuning for the (1+(λ,λ)) GA
Venue: arXiv cs.NE 2019
Year: 2019

It is known that the $(1+(λ,λ))$~Genetic Algorithm (GA) with self-adjusting parameter choices achieves a linear expected optimization time on OneMax if its hyper-parameters are suitably chosen. However, it is not very well understood how the hyper-parameter settings influences the overall performance of the $(1+(λ,λ))$~GA. Analyzing such multi-dimensional dependencies precisely is at the edge of what running time analysis can offer. To make a step forward on this question, we present an in-depth empirical study of the self-adjusting $(1+(λ,λ))$~GA and its hyper-parameters. We show, among many other results, that a 15\% reduction of the average running time is possible by a slightly different setup, which allows non-identical offspring population sizes of mutation and crossover phase, and more flexibility in the choice of mutation rate and crossover bias --a generalization which may be of independent interest. We also show indication that the parametrization of mutation rate and crossover bias derived by theoretical means for the static variant of the $(1+(λ,λ))$~GA extends to the non-static case.
Dynamic Scheduling and Power Control in Uplink Massive MIMO with Random Data Arrivals
Venue: arXiv cs.NI 2019
Year: 2019

In this paper, we study the joint power control and scheduling in uplink massive multiple-input multiple-output (MIMO) systems with random data arrivals. The data is generated at each user according to an individual stochastic process. Using Lyapunov optimization techniques, we develop a dynamic scheduling algorithm (DSA), which decides at each time slot the amount of data to admit to the transmission queues and the transmission rates over the wireless channel. The proposed algorithm achieves nearly optimal performance on the long-term user throughput under various fairness policies. Simulation results show that the DSA can improve the time-average delay performance compared to the state-of-the-art power control schemes developed for Massive MIMO with infinite backlogs.
The Complexity of Definability by Open First-Order Formulas
Venue: arXiv cs.CC 2019
Year: 2019

In this article we formally define and investigate the computational complexity of the Definability Problem for open first-order formulas (i.e., quantifier free first-order formulas) with equality. Given a logic $\mathbf{\mathcal{L}}$, the $\mathbf{\mathcal{L}}$-Definability Problem for finite structures takes as input a finite structure $\mathbf{A}$ and a target relation $T$ over the domain of $\mathbf{A}$, and determines whether there is a formula of $\mathbf{\mathcal{L}}$ whose interpretation in $\mathbf{A}$ coincides with $T$. We show that the complexity of this problem for open first-order formulas (open definability, for short) is coNP-complete. We also investigate the parametric complexity of the problem, and prove that if the size and the arity of the target relation $T$ are taken as parameters then open definability is $\mathrm{coW}[1]$-complete for every vocabulary $τ$ with at least one, at least binary, relation.
Kinematic Synthesis of Parallel Manipulator via Neural Network Approach
Venue: arXiv cs.RO 2019
Year: 2019

In this research, Artificial Neural Networks (ANNs) have been used as a powerful tool to solve the inverse kinematic equations of a parallel robot. For this purpose, we have developed the kinematic equations of a Tricept parallel kinematic mechanism with two rotational and one translational degrees of freedom (DoF). Using the analytical method, the inverse kinematic equations are solved for specific trajectory, and used as inputs for the applied ANNs. The results of both applied networks (Multi-Layer Perceptron and Redial Basis Function) satisfied the required performance in solving complex inverse kinematics with proper accuracy and speed.
Practical Open-Loop Optimistic Planning
Venue: arXiv cs.LG 2019
Year: 2019

We consider the problem of online planning in a Markov Decision Process when given only access to a generative model, restricted to open-loop policies - i.e. sequences of actions - and under budget constraint. In this setting, the Open-Loop Optimistic Planning (OLOP) algorithm enjoys good theoretical guarantees but is overly conservative in practice, as we show in numerical experiments. We propose a modified version of the algorithm with tighter upper-confidence bounds, KLOLOP, that leads to better practical performances while retaining the sample complexity bound. Finally, we propose an efficient implementation that significantly improves the time complexity of both algorithms.
Seq2Biseq: Bidirectional Output-wise Recurrent Neural Networks for Sequence Modelling
Venue: arXiv cs.CL 2019
Year: 2019

During the last couple of years, Recurrent Neural Networks (RNN) have reached state-of-the-art performances on most of the sequence modelling problems. In particular, the "sequence to sequence" model and the neural CRF have proved to be very effective in this domain. In this article, we propose a new RNN architecture for sequence labelling, leveraging gated recurrent layers to take arbitrarily long contexts into account, and using two decoders operating forward and backward. We compare several variants of the proposed solution and their performances to the state-of-the-art. Most of our results are better than the state-of-the-art or very close to it and thanks to the use of recent technologies, our architecture can scale on corpora larger than those used in this work.
Bilingual-GAN: A Step Towards Parallel Text Generation
Venue: arXiv cs.CL 2019
Year: 2019

Latent space based GAN methods and attention based sequence to sequence models have achieved impressive results in text generation and unsupervised machine translation respectively. Leveraging the two domains, we propose an adversarial latent space based model capable of generating parallel sentences in two languages concurrently and translating bidirectionally. The bilingual generation goal is achieved by sampling from the latent space that is shared between both languages. First two denoising autoencoders are trained, with shared encoders and back-translation to enforce a shared latent state between the two languages. The decoder is shared for the two translation directions. Next, a GAN is trained to generate synthetic "code" mimicking the languages' shared latent space. This code is then fed into the decoder to generate text in either language. We perform our experiments on Europarl and Multi30k datasets, on the English-French language pair, and document our performance using both supervised and unsupervised machine translation.
Social Influence in Agile Requirements Engineering
Venue: arXiv cs.SE 2019
Year: 2019

Agile requirements engineering implies more complex communication patterns since even the developers are supposed to have direct contact with customers. With more face-to-face communication comes social-psychological factors influencing the requirements. Studies have pointed at the importance of negotiation training, but I argue that more basic human traits can be triggered in favor of the negotiator with the most knowledge of social influence research and practice. I suggest a plan of how research in social influence and requirements facilitation can be conducted, mostly through experimentation.
Learning more from crossing levels: Investigating agility at three levels of the organization
Venue: arXiv cs.SE 2019
Year: 2019

Scholars have tried to explain how organizations can build agile teams by only looking at one level of analysis. We argue in this short paper that lessons can be learned from organizational science results explaining variance on three different abstraction levels of organizations. We suggest agility needs to be explained from organizational (macro), the team (meso), and individual (micro) levels to provide useful and actionable guidelines to practitioners. We are currently designing such studies and hope that they will eventually result in validated measurements that can be used to prevent companies from investing in the wrong areas when trying to move towards more agility.
Index Codes with Minimum Locality for Three Receiver Unicast Problems
Venue: arXiv cs.IT 2019
Year: 2019

An index code for a broadcast channel with receiver side information is 'locally decodable' if every receiver can decode its demand using only a subset of the codeword symbols transmitted by the sender instead of observing the entire codeword. Local decodability in index coding improves the error performance when used in wireless broadcast channels, reduces the receiver complexity and improves privacy in index coding. The 'locality' of an index code is the ratio of the number of codeword symbols used by each receiver to the number message symbols demanded by the receiver. Prior work on locality in index coding have considered only single unicast and single-uniprior problems, and the optimal trade-off between broadcast rate and locality is known only for a few cases. In this paper we identify the optimal broadcast rate (including among non-linear codes) for all three receiver unicast problems when the locality is equal to the minimum possible value, i.e., equal to one. The index code that achieves this optimal rate is based on a clique covering technique and is well known. The main contribution of this paper is in providing tight converse results by relating locality to broadcast rate, and showing that this known index coding scheme is optimal when locality is equal to one. Towards this we derive several structural properties of the side information graphs of three receiver unicast problems, and combine them with information theoretic arguments to arrive at a converse.
A Hybrid Evolutionary System for Automated Artificial Neural Networks Generation and Simplification in Biomedical Applications
Venue: arXiv cs.LG 2019
Year: 2019

Data mining and data classification over biomedical data are two of the most important research fields in computer science. Among the great diversity of techniques that can be used for this purpose, Artifical Neural Networks (ANNs) is one of the most suited. One of the main problems in the development of this technique is the slow performance of the full process. Traditionally, in this development process, human experts are needed to experiment with different architectural procedures until they find the one that presents the correct results for solving a specific problem. However, many studies have emerged in which different ANN developmental techniques, more or less automated, are described. In this paper, the authors have focused on developing a new technique to perform this process over biomedical data. The new technique is described in which two Evolutionary Computation (EC) techniques are mixed to automatically develop ANNs. These techniques are Genetic Algorithms and Genetic Programming. The work goes further, and the system described here allows to obtain simplified networks with a low number of neurons to resolve the problems. The system is compared with the already existent system which also uses EC over a set of well-known problems. The conclusions reached from these comparisons indicate that this new system produces very good results, which in the worst case are at least comparable to existing techniques and in many cases are substantially better.
Computational Parquetry: Fabricated Style Transfer with Wood Pixels
Venue: arXiv cs.GR 2019
Year: 2019

Parquetry is the art and craft of decorating a surface with a pattern of differently colored veneers of wood, stone or other materials. Traditionally, the process of designing and making parquetry has been driven by color, using the texture found in real wood only for stylization or as a decorative effect. Here, we introduce a computational pipeline that draws from the rich natural structure of strongly textured real-world veneers as a source of detail in order to approximate a target image as faithfully as possible using a manageable number of parts. This challenge is closely related to the established problems of patch-based image synthesis and stylization in some ways, but fundamentally different in others. Most importantly, the limited availability of resources (any piece of wood can only be used once) turns the relatively simple problem of finding the right piece for the target location into the combinatorial problem of finding optimal parts while avoiding resource collisions. We introduce an algorithm that allows to efficiently solve an approximation to the problem. It further addresses challenges like gamut mapping, feature characterization and the search for fabricable cuts. We demonstrate the effectiveness of the system by fabricating a selection of "photo-realistic" pieces of parquetry from different kinds of unstained wood veneer.
Generation & Evaluation of Adversarial Examples for Malware Obfuscation
Venue: arXiv cs.CR 2019
Year: 2019

There has been an increased interest in the application of convolutional neural networks for image based malware classification, but the susceptibility of neural networks to adversarial examples allows malicious actors to evade classifiers. Adversarial examples are usually generated by adding small perturbations to the input that are unrecognizable to humans, but the same approach is not effective with malware. In general, these perturbations cause changes in the byte sequences that change the initial functionality or result in un-executable binaries. We present a generative model for executable adversarial malware examples using obfuscation that achieves a high misclassification rate, up to 100% and 98% in white-box and black-box settings respectively, and demonstrates transferability. We further evaluate the effectiveness of the proposed method by reporting insignificant change in the evasion rate of our adversarial examples against popular defense strategies.