OpenRaiser/Intern-Atlas huggingface dataset:
Hybrid CPU-GPU Framework for Network Motifs
Venue: arXiv cs.DC 2016
Year: 2016

Massively parallel architectures such as the GPU are becoming increasingly important due to the recent proliferation of data. In this paper, we propose a key class of hybrid parallel graphlet algorithms that leverages multiple CPUs and GPUs simultaneously for computing k-vertex induced subgraph statistics (called graphlets). In addition to the hybrid multi-core CPU-GPU framework, we also investigate single GPU methods (using multiple cores) and multi-GPU methods that leverage all available GPUs simultaneously for computing induced subgraph statistics. Both methods leverage GPU devices only, whereas the hybrid multi-core CPU-GPU framework leverages all available multi-core CPUs and multiple GPUs for computing graphlets in large networks. Compared to recent approaches, our methods are orders of magnitude faster, while also more cost effective enjoying superior performance per capita and per watt. In particular, the methods are up to 300 times faster than the recent state-of-the-art method. To the best of our knowledge, this is the first work to leverage multiple CPUs and GPUs simultaneously for computing induced subgraph statistics.
Improving the Efficiency of DAMAS for Sound Source Localization via Wavelet Compression Computational Grid
Venue: arXiv cs.SD 2016
Year: 2016

Phased microphone arrays are used widely in the applications for acoustic source localization. Deconvolution approaches such as DAMAS successfully overcome the spatial resolution limit of the conventional delay-and-sum (DAS) beamforming method. However deconvolution approaches require high computational effort compared to conventional DAS beamforming method. This paper presents a novel method that serves to improve the efficiency of DAMAS via wavelet compression computational grid rather than via optimizing DAMAS algorithm. In this method, the efficiency of DAMAS increases with compression ratio. This method can thus save lots of run time in industrial applications for sound source localization, particularly when sound sources are just located in a small extent compared with scanning plane and a band of angular frequency needs to be calculated. In addition, this method largely retains the spatial resolution of DAMAS on original computational grid, although with a minor deficiency that the occurrence probability of aliasing increasing slightly for complicated sound source.
Design and Implementation of a Procedural Content Generation Web Application for Vertex Shaders
Venue: arXiv cs.GR 2016
Year: 2016

We present a web application for the procedural generation of transformations of 3D models. We generate the transformations by algorithmically generating the vertex shaders of the 3D models. The vertex shaders are created with an interactive genetic algorithm, which displays to the user the visual effect caused by each vertex shader, allows the user to select the visual effect the user likes best, and produces a new generation of vertex shaders using the user feedback as the fitness measure of the genetic algorithm. We use genetic programming to represent each vertex shader as a computer program. This paper presents details of requirements specification, software architecture, high and low-level design, and prototype user interface. We discuss the project's current status and development challenges.
On the Irregularity of Some Molecular Structures
Venue: arXiv cs.DM 2016
Year: 2016

Measures of the irregularity of chemical graphs could be helpful for QSAR/QSPR studies and for the descriptive purposes of biological and chemical properties, such as melting and boiling points, toxicity and resistance. Here we consider the following four established irregularity measures: the irregularity index by Albertson, the total irregularity, the variance of vertex degrees and the Collatz-Sinogowitz index. Through the means of graph structural analysis and derivation, we study the above-mentioned irregularity measures of several chemical molecular graphs which frequently appear in chemical, medical and material engineering, as well as the nanotubes: $TUC_4 C_8(S)$, $TUC_4 C_8(R)$, Zig-Zag $TUHC_{6}$, $TUC_4$, Armchair $TUVC_{6}$, then dendrimers $T_{k,d}$ and the circumcoronene series of benzenoid $H_k$. In addition, the irregularities of Mycielski's constructions of cycle and path graphs are analyzed.
A Tight Convex Upper Bound on the Likelihood of a Finite Mixture
Venue: arXiv cs.LG 2016
Year: 2016

The likelihood function of a finite mixture model is a non-convex function with multiple local maxima and commonly used iterative algorithms such as EM will converge to different solutions depending on initial conditions. In this paper we ask: is it possible to assess how far we are from the global maximum of the likelihood? Since the likelihood of a finite mixture model can grow unboundedly by centering a Gaussian on a single datapoint and shrinking the covariance, we constrain the problem by assuming that the parameters of the individual models are members of a large discrete set (e.g. estimating a mixture of two Gaussians where the means and variances of both Gaussians are members of a set of a million possible means and variances). For this setting we show that a simple upper bound on the likelihood can be computed using convex optimization and we analyze conditions under which the bound is guaranteed to be tight. This bound can then be used to assess the quality of solutions found by EM (where the final result is projected on the discrete set) or any other mixture estimation algorithm. For any dataset our method allows us to find a finite mixture model together with a dataset-specific bound on how far the likelihood of this mixture is from the global optimum of the likelihood
Sensitivity and Reliability in Incomplete Networks: Centrality Metrics to Community Scoring Functions
Venue: arXiv cs.SI 2016
Year: 2016

Network analysis is an important tool in understanding the behavior of complex systems of interacting entities. However, due to the limitations of data gathering technologies, some interactions might be missing from the network model. This is a ubiquitous problem in all domains that use network analysis, from social networks to hyper-linked web networks to biological networks. Consequently, an important question in analyzing networks is to understand how increasing the noise level (i.e. percentage of missing edges) affects different network parameters. In this paper we evaluate the effect of noise on community scoring and centrality-based parameters with respect to two different aspects of network analysis: (i) sensitivity, that is how the parameter value changes as edges are removed and (ii) reliability in the context of message spreading, that is how the time taken to broadcast a message changes as edges are removed. Our experiments on synthetic and real-world networks and three different noise models demonstrate that for both the aspects over all networks and all noise models, permanence qualifies as the most effective metric. For the sensitivity experiments closeness centrality is a close second. For the message spreading experiments, closeness and betweenness centrality based initiator selection closely competes with permanence. This is because permanence has a dual characteristic where the cumulative permanence over all vertices is sensitive to noise but the ids of the top-rank vertices, which are used to find seeds during message spreading remain relatively stable under noise.
Entropy Jumps for Radially Symmetric Random Vectors
Venue: arXiv cs.IT 2016
Year: 2016

We establish a quantitative bound on the entropy jump associated to the sum of independent, identically distributed (IID) radially symmetric random vectors having dimension greater than one. Following the usual approach, we first consider the analogous problem of Fisher information dissipation, and then integrate along the Ornstein-Uhlenbeck semigroup to obtain an entropic inequality. In a departure from previous work, we appeal to a result by Desvillettes and Villani on entropy production associated to the Landau equation. This obviates strong regularity assumptions, such as presence of a spectral gap and log-concavity of densities, but comes at the expense of radial symmetry. As an application, we give a quantitative estimate of the deficit in the Gaussian logarithmic Sobolev inequality for radially symmetric functions.
A Reconfigurable FIR Filter with Memristor-Based Weights
Venue: arXiv cs.ET 2016
Year: 2016

We report on experimental demonstration of a mixed-signal 6-tap finite-impulse response (FIR) filter in which weights are implemented with titanium dioxide memristive devices. In the proposed design weight of a tap is stored with a relatively high precision in a memristive device that can be configured in field. Such approach enables efficient implementation of the most critical operation of an FIR filter, i.e. multiplication of the input signal with the tap weights and summation of the products from taps, in analog domain. As a result, the proposed design, when implemented with fully integrated hybrid CMOS/memristor circuit, is expected to be much more compact and energy efficient as compared to the state-of-the-art approaches.
Uncertainty Principle for Measurable Sets and Signal Recovery in Quaternion Domains
Venue: arXiv cs.IT 2016
Year: 2016

The classical uncertainty principle of harmonic analysis states that a nontrivial function and its Fourier transform cannot both be sharply localized. It plays an important role in signal processing and physics. This paper generalizes the uncertainty principle for measurable sets from complex domain to hypercomplex domain using quaternion algebras, associated with the Quaternion Fourier transform. The performance is then evaluated in signal recovery problems where there is an interplay of missing and time-limiting data.
Goal-Oriented Reduction of Automata Networks
Venue: arXiv cs.LO 2016
Year: 2016

We consider networks of finite-state machines having local transitions conditioned by the current state of other automata. In this paper, we depict a reduction procedure tailored for a given reachability property of the form ``from global state s there exists a sequence of transitions leading to a state where an automaton g is in a local state T'. By exploiting a causality analysis of the transitions within the individual automata, the proposed reduction removes local transitions while preserving all the minimal traces that satisfy the reachability property. The complexity of the procedure is polynomial in the total number of local states and transitions, and exponential in the number of local states within one automaton. Applied to automata networks modelling dynamics of biological systems, we observe that the reduction shrinks down significantly the reachable state space, enhancing the tractability of the model-checking of large networks.
Implementing a Relevance Tracker Module
Venue: arXiv cs.AI 2016
Year: 2016

PC(ID) extends propositional logic with inductive definitions: rule sets under the well-founded semantics. Recently, a notion of relevance was introduced for this language. This notion determines the set of undecided literals that can still influence the satisfiability of a PC(ID) formula in a given partial assignment. The idea is that the PC(ID) solver can make decisions only on relevant literals without losing soundness and thus safely ignore irrelevant literals. One important insight that the relevance of a literal is completely determined by the current solver state. During search, the solver state changes have an effect on the relevance of literals. In this paper, we discuss an incremental, lightweight implementation of a relevance tracker module that can be added to and interact with an out-of-the-box SAT(ID) solver.
CurryCheck: Checking Properties of Curry Programs
Venue: arXiv cs.PL 2016
Year: 2016

We present CurryCheck, a tool to automate the testing of programs written in the functional logic programming language Curry. CurryCheck executes unit tests as well as property tests which are parameterized over one or more arguments. In the latter case, CurryCheck tests these properties by systematically enumerating test cases so that, for smaller finite domains, CurryCheck can actually prove properties. Unit tests and properties can be defined in a Curry module without being exported. Thus, they are also useful to document the intended semantics of the source code. Furthermore, CurryCheck also supports the automated checking of specifications and contracts occurring in source programs. Hence, CurryCheck is a useful tool that contributes to the property- and specification-based development of reliable and well tested declarative programs.
Operator-Valued Bochner Theorem, Fourier Feature Maps for Operator-Valued Kernels, and Vector-Valued Learning
Venue: arXiv cs.LG 2016
Year: 2016

This paper presents a framework for computing random operator-valued feature maps for operator-valued positive definite kernels. This is a generalization of the random Fourier features for scalar-valued kernels to the operator-valued case. Our general setting is that of operator-valued kernels corresponding to RKHS of functions with values in a Hilbert space. We show that in general, for a given kernel, there are potentially infinitely many random feature maps, which can be bounded or unbounded. Most importantly, given a kernel, we present a general, closed form formula for computing a corresponding probability measure, which is required for the construction of the Fourier features, and which, unlike the scalar case, is not uniquely and automatically determined by the kernel. We also show that, under appropriate conditions, random bounded feature maps can always be computed. Furthermore, we show the uniform convergence, under the Hilbert-Schmidt norm, of the resulting approximate kernel to the exact kernel on any compact subset of Euclidean space. Our convergence requires differentiable kernels, an improvement over the twice-differentiability requirement in previous work in the scalar setting. We then show how operator-valued feature maps and their approximations can be employed in a general vector-valued learning framework. The mathematical formulation is illustrated by numerical examples on matrix-valued kernels.
A family of linear codes with three weights
Venue: arXiv cs.IT 2016
Year: 2016

Recently, linear codes constructed by defining sets have attracted a lot of study, and many optimal linear codes with a few weights have been produced. The objective of this paper is to present a class of binary linear codes with three weights.
The languages of actions, formal grammars and qualitive modeling of companies
Venue: arXiv cs.AI 2016
Year: 2016

In this paper we discuss methods of using the language of actions, formal languages, and grammars for qualitative conceptual linguistic modeling of companies as technological and human institutions. The main problem following the discussion is the problem to find and describe a language structure for external and internal flow of information of companies. We anticipate that the language structure of external and internal base flows determine the structure of companies. In the structure modeling of an abstract industrial company an internal base flow of information is constructed as certain flow of words composed on the theoretical parts-processes-actions language. The language of procedures is found for an external base flow of information for an insurance company. The formal stochastic grammar for the language of procedures is found by statistical methods and is used in understanding the tendencies of the health care industry. We present the model of human communications as a random walk on the semantic tree
A Data-Driven Approach for Mapping Multivariate Data to Color
Venue: arXiv cs.GR 2016
Year: 2016

A wide variety of color schemes have been devised for mapping scalar data to color. Some use the data value to index a color scale. Others assign colors to different, usually blended disjoint materials, to handle areas where materials overlap. A number of methods can map low-dimensional data to color, however, these methods do not scale to higher dimensional data. Likewise, schemes that take a more artistic approach through color mixing and the like also face limits when it comes to the number of variables they can encode. We address the challenge of mapping multivariate data to color and avoid these limitations at the same time. It is a data driven method, which first gauges the similarity of the attributes and then arranges them according to the periphery of a convex 2D color space, such as HSL. The color of a multivariate data sample is then obtained via generalized barycentric coordinate (GBC) interpolation.
Analysis of Bayesian Classification based Approaches for Android Malware Detection
Venue: arXiv cs.CR 2016
Year: 2016

Mobile malware has been growing in scale and complexity spurred by the unabated uptake of smartphones worldwide. Android is fast becoming the most popular mobile platform resulting in sharp increase in malware targeting the platform. Additionally, Android malware is evolving rapidly to evade detection by traditional signature-based scanning. Despite current detection measures in place, timely discovery of new malware is still a critical issue. This calls for novel approaches to mitigate the growing threat of zero-day Android malware. Hence, in this paper we develop and analyze proactive Machine Learning approaches based on Bayesian classification aimed at uncovering unknown Android malware via static analysis. The study, which is based on a large malware sample set of majority of the existing families, demonstrates detection capabilities with high accuracy. Empirical results and comparative analysis are presented offering useful insight towards development of effective static-analytic Bayesian classification based solutions for detecting unknown Android malware.
Visual Processing by a Unified Schatten-$p$ Norm and $\ell_q$ Norm Regularized Principal Component Pursuit
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we propose a non-convex formulation to recover the authentic structure from the corrupted real data. Typically, the specific structure is assumed to be low rank, which holds for a wide range of data, such as images and videos. Meanwhile, the corruption is assumed to be sparse. In the literature, such a problem is known as Robust Principal Component Analysis (RPCA), which usually recovers the low rank structure by approximating the rank function with a nuclear norm and penalizing the error by an $\ell_1$-norm. Although RPCA is a convex formulation and can be solved effectively, the introduced norms are not tight approximations, which may cause the solution to deviate from the authentic one. Therefore, we consider here a non-convex relaxation, consisting of a Schatten-$p$ norm and an $\ell_q$-norm that promote low rank and sparsity respectively. We derive a proximal iteratively reweighted algorithm (PIRA) to solve the problem. Our algorithm is based on an alternating direction method of multipliers, where in each iteration we linearize the underlying objective function that allows us to have a closed form solution. We demonstrate that solutions produced by the linearized approximation always converge and have a tighter approximation than the convex counterpart. Experimental results on benchmarks show encouraging results of our approach.
Reducing State Explosion for Software Model Checking with Relaxed Memory Consistency Models
Venue: arXiv cs.SE 2016
Year: 2016

Software model checking suffers from the so-called state explosion problem, and relaxed memory consistency models even worsen this situation. What is worse, parameterizing model checking by memory consistency models, that is, to make the model checker as flexible as we can supply definitions of memory consistency models as an input, intensifies state explosion. This paper explores specific reasons for state explosion in model checking with multiple memory consistency models, provides some optimizations intended to mitigate the problem, and applies them to McSPIN, a model checker for memory consistency models that we are developing. The effects of the optimizations and the usefulness of McSPIN are demonstrated experimentally by verifying copying protocols of concurrent copying garbage collection algorithms. To the best of our knowledge, this is the first model checking of the concurrent copying protocols under relaxed memory consistency models.
FPGA Design for Pseudorandom Number Generator Based on Chaotic Iteration used in Information Hiding Application
Venue: arXiv cs.CR 2016
Year: 2016

Lots of researches indicate that the inefficient generation of random numbers is a significant bottleneck for information communication applications. Therefore, Field Programmable Gate Array (FPGA) is developed to process a scalable fixed-point method for random streams generation. In our previous researches, we have proposed a technique by applying some well-defined discrete chaotic iterations that satisfy the reputed Devaney's definition of chaos, namely chaotic iterations (CI). We have formerly proven that the generator with CI can provide qualified chaotic random numbers. In this paper, this generator based on chaotic iterations is optimally redesigned for FPGA device. By doing so, the generation rate can be largely improved. Analyses show that these hardware generators can also provide good statistical chaotic random bits and can be cryptographically secure too. An application in the information hiding security field is finally given as an illustrative example.
Planning With Discrete Harmonic Potential Fields
Venue: arXiv cs.RO 2016
Year: 2016

In this work a discrete counterpart to the continuous harmonic potential field approach is suggested. The extension to the discrete case makes use of the strong relation HPF-based planning has to connectionist artificial intelligence (AI). Connectionist AI systems are networks of simple, interconnected processors running in parallel within the confines of the environment in which the planning action is to be synthesized. It is not hard to see that such a paradigm naturally lends itself to planning on weighted graphs where the processors may be seen as the vertices of the graph and the relations among them as its edges. Electrical networks are an effective realization of connectionist AI. The utility of the discrete HPF (DHPF) approach is demonstrated in three ways. First, the capability of the DHPF approach to generate new, abstract, planning techniques is demonstrated by constructing a novel, efficient, optimal, discrete planning method called the M* algorithm. Also, its ability to augment the capabilities of existing planners is demonstrated by suggesting a generic solution to the lower bound problem faced by the A* algorithm. The DHPF approach is shown to be useful in solving specific planning problems in communication. It is demonstrated that the discrete HPF paradigm can support routing on-the-fly while the network is still in a transient state. It is shown by simulation that if a path to the target always exist and the switching delays in the routers are negligible, a packet will reach its destination despite the changes in the network which may simultaneously take place while the packet is being routed.