OpenRaiser/Intern-Atlas huggingface dataset:
Attribute Truss Community Search
Venue: arXiv cs.DB 2017
Year: 2017

Recently, community search over graphs has attracted significant attention and many algorithms have been developed for finding dense subgraphs from large graphs that contain given query nodes. In applications such as analysis of protein protein interaction (PPI) networks, citation graphs, and collaboration networks, nodes tend to have attributes. Unfortunately, previously developed community search algorithms ignore these attributes and result in communities with poor cohesion w.r.t. their node attributes. In this paper, we study the problem of attribute-driven community search, that is, given an undirected graph $G$ where nodes are associated with attributes, and an input query $Q$ consisting of nodes $V_q$ and attributes $W_q$, find the communities containing $V_q$, in which most community members are densely inter-connected and have similar attributes. We formulate our problem of finding attributed truss communities (ATC), as finding all connected and close k-truss subgraphs containing $V_q$, that are locally maximal and have the largest attribute relevance score among such subgraphs. We design a novel attribute relevance score function and establish its desirable properties. The problem is shown to be NP-hard. However, we develop an efficient greedy algorithmic framework, which finds a maximal $k$-truss containing $V_q$, and then iteratively removes the nodes with the least popular attributes and shrinks the graph so as to satisfy community constraints. We also build an elegant index to maintain the known $k$-truss structure and attribute information, and propose efficient query processing algorithms. Extensive experiments on large real-world networks with ground-truth communities shows the efficiency and effectiveness of our proposed methods.
Joint Caching and Pricing Strategies for Popular Content in Information Centric Networks
Venue: arXiv cs.GT 2017
Year: 2017

We develop an analytical framework for distribution of popular content in an Information Centric Network (ICN) that comprises of Access ICNs, a Transit ICN and a Content Provider. Using a generalized Zipf distribution to model content popularity, we devise a game theoretic approach to jointly determine caching and pricing strategies in such an ICN. Under the assumption that the caching cost of the access and transit ICNs is inversely proportional to popularity, we show that the Nash caching strategies in the ICN are 0-1 (all or nothing) strategies. Further, for the case of symmetric Access ICNs, we show that the Nash equilibrium is unique and the caching policy (0 or 1) is determined by a threshold on the popularity of the content (reflected by the Zipf probability metric), i.e., all content more popular than the threshold value is cached. We also show that the resulting threshold of the Access and Transit ICNs, as well as all prices can be obtained by a decomposition of the joint caching and pricing problem into two independent caching only and pricing only problems.
Generic and Effective Specification of Structural Test Objectives
Venue: arXiv cs.SE 2017
Year: 2017

While a wide range of different, sometimes heterogeneous test coverage criteria have been proposed, there exists no generic formalism to describe them, and available test automation tools usually support only a small subset of them. We introduce a unified specification language, called HTOL, providing a powerful generic mechanism to define test objectives, which permits encoding numerous existing criteria and supporting them in a unified way. HTOL comes with a formal semantics and can express complex requirements over several executions (using a novel notion of hyperlabels), as well as alternative requirements or requirements over a whole program execution. A novel classification of a large class of existing criteria is proposed. Finally, a coverage measurement tool for HTOL objectives has been implemented. Initial experiments suggest that the proposed approach is both efficient and practical.
Minimal and minimum unit circular-arc models
Venue: arXiv cs.DM 2017
Year: 2017

A proper circular-arc (PCA) model is a pair ${\cal M} = (C, \cal A)$ where $C$ is a circle and $\cal A$ is a family of inclusion-free arcs on $C$ in which no two arcs of $\cal A$ cover $C$. A PCA model $\cal U = (C,\cal A)$ is a $(c, \ell)$-CA model when $C$ has circumference $c$, all the arcs in $\cal A$ have length $\ell$, and all the extremes of the arcs in $\cal A$ are at a distance at least $1$. If $c \leq c'$ and $\ell \leq \ell'$ for every $(c', \ell')$-CA model equivalent (resp. isomorphic) to $\cal U$, then $\cal U$ is minimal (resp. minimum). In this article we prove that every PCA model is isomorphic to a minimum model. Our main tool is a new characterization of those PCA models that are equivalent to $(c,\ell)$-CA models, that allows us to conclude that $c$ and $\ell$ are integer when $\cal U$ is minimal. As a consequence, we obtain an $O(n^3)$ time and $O(n^2)$ space algorithm to solve the minimal representation problem, while we prove that the minimum representation problem is NP-complete.
Analytic Performance Model of a Main-Memory Index Structure
Venue: arXiv cs.DB 2017
Year: 2017

Efficient evaluation of multi-dimensional range queries in a main-memory database is an important, but difficult task. State-of-the-art techniques rely on optimised sequential scans or tree-based structures. For range queries with small result sets, sequential scans exhibit poor asymptotic performance. Also, as the dimensionality of the data set increases, the performance of tree-based structures degenerates due to the curse of dimensionality. Recent literature proposed the Elf, a main-memory structure that is optimised for the case of such multi-dimensional low-selectivity queries. The Elf outperforms other state-of-the-art methods in manually tuned scenarios. However, choosing an optimal parameter configuration for the Elf is vital, since for poor configurations, the search performance degrades rapidly. Consequently, further knowledge about the behaviour of the Elf in different configurations is required to achieve robust performance. In this thesis, we therefore propose a numerical cost model for the Elf. Like all main-memory index structures, the Elf response time is not dominated by disk accesses, refusing a straightforward analysis. Our model predicts the size and shape of the Elf region that is examined during search. We propose that the response time of a search is linear to the size of this region. Furthermore, we study the impact of skewed data distributions and correlations on the shape of the Elf. We find that they lead to behaviour that is accurately describable through simple reductions in attribute cardinality. Our experimental results indicate that for data sets of up to 15 dimensions, our cost model predicts the size of the examined Elf region with relative errors below 5%. Furthermore, we find that the size of the Elf region examined during search predicts the response time with an accuracy of 80%.
Deviant Learning Algorithm: Learning Sparse Mismatch Representations through Time and Space
Venue: arXiv cs.AI 2017
Year: 2017

Predictive coding (PDC) has recently attracted attention in the neuroscience and computing community as a candidate unifying paradigm for neuronal studies and artificial neural network implementations particularly targeted at unsupervised learning systems. The Mismatch Negativity (MMN) has also recently been studied in relation to PC and found to be a useful ingredient in neural predictive coding systems. Backed by the behavior of living organisms, such networks are particularly useful in forming spatio-temporal transitions and invariant representations of the input world. However, most neural systems still do not account for large number of synapses even though this has been shown by a few machine learning researchers as an effective and very important component of any neural system if such a system is to behave properly. Our major point here is that PDC systems with the MMN effect in addition to a large number of synapses can greatly improve any neural learning system's performance and ability to make decisions in the machine world. In this paper, we propose a novel bio-mimetic computational intelligence algorithm -- the Deviant Learning Algorithm, inspired by these key ideas and functional properties of recent brain-cognitive discoveries and theories. We also show by numerical experiments guided by theoretical insights, how our invented bio-mimetic algorithm can achieve competitive predictions even with very small problem specific data.
Accelerating Nuclear Configuration Interaction Calculations through a Preconditioned Block Iterative Eigensolver
Venue: arXiv cs.NA 2017
Year: 2017

We describe a number of recently developed techniques for improving the performance of large-scale nuclear configuration interaction calculations on high performance parallel computers. We show the benefit of using a preconditioned block iterative method to replace the Lanczos algorithm that has traditionally been used to perform this type of computation. The rapid convergence of the block iterative method is achieved by a proper choice of starting guesses of the eigenvectors and the construction of an effective preconditioner. These acceleration techniques take advantage of special structure of the nuclear configuration interaction problem which we discuss in detail. The use of a block method also allows us to improve the concurrency of the computation, and take advantage of the memory hierarchy of modern microprocessors to increase the arithmetic intensity of the computation relative to data movement. We also discuss implementation details that are critical to achieving high performance on massively parallel multi-core supercomputers, and demonstrate that the new block iterative solver is two to three times faster than the Lanczos based algorithm for problems of moderate sizes on a Cray XC30 system.
Bounded degree and planar spectra
Venue: arXiv cs.LO 2017
Year: 2017

The finite spectrum of a first-order sentence is the set of positive integers that are the sizes of its models. The class of finite spectra is known to be the same as the complexity class NE. We consider the spectra obtained by limiting models to be either planar (in the graph-theoretic sense) or by bounding the degree of elements. We show that the class of such spectra is still surprisingly rich by establishing that significant fragments of NE are included among them. At the same time, we establish non-trivial upper bounds showing that not all sets in NE are obtained as planar or bounded-degree spectra.
An efficient Search Tool for an Anti-Money Laundering Application of an Multi-national Bank's Dataset
Venue: arXiv cs.DB 2017
Year: 2017

Today, money laundering (ML) poses a serious threat not only to financial institutions but also to the nations. This criminal activity is becoming more and more sophisticated and seems to have moved from the clichy of drug trafficking to financing terrorism and surely not forgetting personal gain. Most of the financial institutions internationally have been implementing anti-money laundering solutions (AML) to fight investment fraud activities. In AML, the customer identification is an important task which helps AML experts to monitor customer habits: some being customer domicile, transactions that they are involved in etc. However, simple query tools provided by current DBMS as well as naive approaches in customer searching may produce incorrect and ambiguous results and their processing time is also very high due to the complexity of the database system architecture. In this paper, we present a new approach for identifying customers registered in an investment bank. This approach is developed as a tool that allows AML experts to quickly identify customers who are managed independently across separate databases. It is tested on real-world datasets, which are real and large financial datasets. Some preliminary experimental results show that this new approach is efficient and effective.
HashTag Erasure Codes: From Theory to Practice
Venue: arXiv cs.IT 2017
Year: 2017

Minimum-Storage Regenerating (MSR) codes have emerged as a viable alternative to Reed-Solomon (RS) codes as they minimize the repair bandwidth while they are still optimal in terms of reliability and storage overhead. Although several MSR constructions exist, so far they have not been practically implemented mainly due to the big number of I/O operations. In this paper, we analyze high-rate MDS codes that are simultaneously optimized in terms of storage, reliability, I/O operations, and repair-bandwidth for single and multiple failures of the systematic nodes. The codes were recently introduced in \cite{7463553} without any specific name. Due to the resemblance between the hashtag sign \# and the procedure of the code construction, we call them in this paper \emph{HashTag Erasure Codes (HTECs)}. HTECs provide the lowest data-read and data-transfer, and thus the lowest repair time for an arbitrary sub-packetization level $α$, where $α\leq r^{\lceil \sfrac{k}{r} \rceil}$, among all existing MDS codes for distributed storage including MSR codes. The repair process is linear and highly parallel. Additionally, we show that HTECs are the first high-rate MDS codes that reduce the repair bandwidth for more than one failure. Practical implementations of HTECs in Hadoop release 3.0.0-alpha2 demonstrate their great potentials.
On the Power of Statistical Zero Knowledge
Venue: arXiv cs.CC 2017
Year: 2017

We examine the power of statistical zero knowledge proofs (captured by the complexity class SZK) and their variants. First, we give the strongest known relativized evidence that SZK contains hard problems, by exhibiting an oracle relative to which SZK (indeed, even NISZK) is not contained in the class UPP, containing those problems solvable by randomized algorithms with unbounded error. This answers an open question of Watrous from 2002 [Aar]. Second, we "lift" this oracle separation to the setting of communication complexity, thereby answering a question of Göös et al. (ICALP 2016). Third, we give relativized evidence that perfect zero knowledge proofs (captured by the class PZK) are weaker than general zero knowledge proofs. Specifically, we exhibit oracles relative to which SZK is not contained in PZK, NISZK is not contained in NIPZK, and PZK is not equal to coPZK. The first of these results answers a question raised in 1991 by Aiello and Håstad (Information and Computation), and the second answers a question of Lovett and Zhang (2016). We also describe additional applications of these results outside of structural complexity. The technical core of our results is a stronger hardness amplification theorem for approximate degree, which roughly says that composing the gapped-majority function with any function of high approximate degree yields a function with high threshold degree.
The Applied Pi Calculus: Mobile Values, New Names, and Secure Communication
Venue: arXiv cs.CR 2017
Year: 2017

We study the interaction of the programming construct "new", which generates statically scoped names, with communication via messages on channels. This interaction is crucial in security protocols, which are the main motivating examples for our work, it also appears in other programming-language contexts. We define the applied pi calculus, a simple, general extension of the pi calculus in which values can be formed from names via the application of built-in functions, subject to equations, and be sent as messages. (In contrast, the pure pi calculus lacks built-in functions, its only messages are atomic names.) We develop semantics and proof techniques for this extended language and apply them in reasoning about security protocols. This paper essentially subsumes the conference paper that introduced the applied pi calculus in 2001. It fills gaps, incorporates improvements, and further explains and studies the applied pi calculus. Since 2001, the applied pi calculus has been the basis for much further work, described in many research publications and sometimes embodied in useful software, such as the tool ProVerif, which relies on the applied pi calculus to support the specification and automatic analysis of security protocols. Although this paper does not aim to be a complete review of the subject, it benefits from that further work and provides better foundations for some of it. In particular, the applied pi calculus has evolved through its implementation in ProVerif, and the present definition reflects that evolution.
Energy-based Generative Adversarial Network
Venue: arXiv cs.LG 2017
Year: 2017

We introduce the "Energy-based Generative Adversarial Network" model (EBGAN) which views the discriminator as an energy function that attributes low energies to the regions near the data manifold and higher energies to other regions. Similar to the probabilistic GANs, a generator is seen as being trained to produce contrastive samples with minimal energies, while the discriminator is trained to assign high energies to these generated samples. Viewing the discriminator as an energy function allows to use a wide variety of architectures and loss functionals in addition to the usual binary classifier with logistic output. Among them, we show one instantiation of EBGAN framework as using an auto-encoder architecture, with the energy being the reconstruction error, in place of the discriminator. We show that this form of EBGAN exhibits more stable behavior than regular GANs during training. We also show that a single-scale architecture can be trained to generate high-resolution images.
Exact Dimensionality Reduction for Partial Line Spectra Estimation Problems
Venue: arXiv cs.IT 2017
Year: 2017

Line spectral estimation theory aims to estimate the off-the-grid spectral components of a time signal with optimal precision. Recent results have shown that it is possible to recover signals having sparse line spectra from few temporal observations via the use of convex programming. However, the computational cost of such approaches remains the major flaw to their application to practical systems. This work investigates the recovery of spectrally sparse signal from low-dimensional partial measurements. It is shown in the first part of this paper that, under a light assumption on the sub-sampling matrix, the partial line spectral estimation problems can be relaxed into a low-dimensional semidefinite program. The proof technique relies on a novel extension of the Gram parametrization to subspaces of trigonometric polynomials. The second part of this work focuses on the analysis of two particular sub-sampling patterns: multirate sampling and random selection sampling. It is shown that those sampling patterns guarantee perfect recovery of the line spectra, and that the reconstruction can be achieved in a poly-logarithmic time with respect to the full observation case. Moreover, the sub-Nyquist recovery capabilities of such sampling patterns are highlighted. The atomic soft thresholding method is adapted in the presented framework to estimate sparse spectra in noisy environments, and a scalable algorithm for its resolution is proposed.
Less is More: Minimizing Code Reorganization using XTREE
Venue: arXiv cs.SE 2017
Year: 2017

Context: Developers use bad code smells to guide code reorganization. Yet developers, text books, tools, and researchers disagree on which bad smells are important. Objective: To evaluate the likelihood that a code reorganization to address bad code smells will yield improvement in the defect-proneness of the code. Method: We introduce XTREE, a tool that analyzes a historical log of defects seen previously in the code and generates a set of useful code changes. Any bad smell that requires changes outside of that set can be deprioritized (since there is no historical evidence that the bad smell causes any problems). Evaluation: We evaluate XTREE's recommendations for bad smell improvement against recommendations from previous work (Shatnawi, Alves, and Borges) using multiple data sets of code metrics and defect counts. Results: Code modules that are changed in response to XTREE's recommendations contain significantly fewer defects than recommendations from previous studies. Further, XTREE endorses changes to very few code metrics, and the bad smell recommendations (learned from previous studies) are not universal to all software projects. Conclusion: Before undertaking a code reorganization based on a bad smell report, use a tool like XTREE to check and ignore any such operations that are useless; i.e. ones which lack evidence in the historical record that it is useful to make that change. Note that this use case applies to both manual code reorganizations proposed by developers as well as those conducted by automatic methods. This recommendation assumes that there is an historical record. If none exists, then the results of this paper could be used as a guide.
A Fast Proximal Gradient Algorithm for Decentralized Composite Optimization over Directed Networks
Venue: arXiv cs.DC 2017
Year: 2017

This paper proposes a fast decentralized algorithm for solving a consensus optimization problem defined in a directed networked multi-agent system, where the local objective functions have the smooth+nonsmooth composite form, and are possibly nonconvex. Examples of such problems include decentralized compressed sensing and constrained quadratic programming problems, as well as many decentralized regularization problems. We extend the existing algorithms PG-EXTRA and ExtraPush to a new algorithm PG-ExtraPush for composite consensus optimization over a directed network. This algorithm takes advantage of the proximity operator like in PG-EXTRA to deal with the nonsmooth term, and employs the push-sum protocol like in ExtraPush to tackle the bias introduced by the directed network. With a proper step size, we show that PG-ExtraPush converges to an optimal solution at a linear rate under some regular assumptions. We conduct a series of numerical experiments to show the effectiveness of the proposed algorithm. Specifically, with a proper step size, PG-ExtraPush performs linear rates in most of cases, even in some nonconvex cases, and is significantly faster than Subgradient-Push, even if the latter uses a hand-optimized step size. The established theoretical results are also verified by the numerical results.
Robust Resource Allocation for MIMO Wireless Powered Communication Networks Based on a Non-linear EH Model
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we consider a multiple-input multiple-output wireless powered communication network (MIMO-WPCN), where multiple users harvest energy from a dedicated power station in order to be able to transmit their information signals to an information receiving station. Employing a practical non-linear energy harvesting (EH) model, we propose a joint time allocation and power control scheme, which takes into account the uncertainty regarding the channel state information (CSI) and provides robustness against imperfect CSI knowledge. In particular, we formulate two non-convex optimization problems for different objectives, namely system sum throughput maximization and maximization of the minimum individual throughput across all wireless powered users. To overcome the non-convexity, we apply several transformations along with a one-dimensional search to obtain an efficient resource allocation algorithm. Numerical results reveal that a significant performance gain can be achieved when the resource allocation is designed based on the adopted non-linear EH model instead of the conventional linear EH model. Besides, unlike a non-robust baseline scheme designed for perfect CSI, the proposed resource allocation schemes are shown to be robust against imperfect CSI knowledge.