The agnostic setting is the hardest generalization of the PAC model since it is akin to learning with adversarial noise. In this paper, we give a poly $(n, t, 1/\epsilon)$ quantum algorithm for learning size $t$ decision trees over $n$-bit inputs with uniform marginal over instances, in the agnostic setting, without membership queries (MQ). This is the first algorithm (classical or quantum) for efficiently learning decision trees without MQ. First, we construct a quantum agnostic weak learner by designing a quantum variant of the classical Goldreich-Levin algorithm that works with strongly biased function oracles. Next, we show how to quantize the agnostic boosting algorithm by Kalai and Kanade (2009) to obtain the first efficient quantum agnostic boosting algorithm (that has a polynomial speedup over existing adaptive quantum boosting algorithms). We then use the quantum agnostic boosting algorithm to boost the weak quantum agnostic learner constructed previously to obtain a quantum agnostic learner for decision trees. Using the above framework, we also give quantum decision tree learning algorithms without MQ in weaker noise models.

Categorical attributes are those that can take a discrete set of values, e.g., colours. This work is about compressing vectors over categorical attributes to low-dimension discrete vectors. The current hash-based methods compressing vectors over categorical attributes to low-dimension discrete vectors do not provide any guarantee on the Hamming distances between the compressed representations. Here we presentFSketchto create sketches for a sparse categorical data and an estimator to estimate the pairwise Hamming distances among the uncompressed data only from their sketches. We claim that these sketches can be used in the usual data mining tasks in place of the original data without compromising the quality of the task. For that we ensure that the sketches also are categorical, sparse, and the Hamming distance estimates are reasonably precise. Both the sketch construction and the Hamming distance estimation algorithms require just a single-pass; furthermore, changes to a data point can be incorporated into its sketch in an efficient manner. The compressibility depends upon how sparse the data is and is independent of the original dimension – making our algorithm attractive for many real-life scenarios. Our claims are backed by rigorous theoretical analysis of the properties ofFSketchand supplemented by extensive comparative evaluations with related algorithms on some real-world datasets. We show thatFSketchis significantly faster, and the accuracy obtained by using its sketches are among the top for the standard unsupervised tasks of$\mathrm{RMSE}$, clustering and similarity search.

Representation learning using network embedding has received tremendous attention due to its efficacy to solve downstream tasks. Popular embedding methods (such as deepwalk,node2vec,LINE) are based on a neural architecture, thus unable to scale on large networks both in terms of time and space usage. Recently, we proposed BinSketch, a sketching technique for compressing binary vectors to binary vectors. In this paper, we show how to extend BinSketch and use it for network hashing. Our proposal named QUINT is built upon BinSketch, and it embeds nodes of a sparse network onto a low-dimensional space using simple bit-wise operations. QUINT is the first of its kind that provides tremendous gain in terms of speed and space usage without compromising much on the accuracy of the downstream tasks. Extensive experiments are conducted to compare QUINT with seven state-of-the-art network embedding methods for two end tasks link prediction and node classification. We observe huge performance gain for QUINT in terms of speedup (up to 7000) and space saving (up to 800) due to its bit-wise nature to obtain node embedding.Moreover, QUINT is a consistent top-performer for both the tasks among the baselines across all the datasets. Our empirical observations are backed by rigorous theoretical analysis to justify the effectiveness of QUINT.

Non-linearity of a Boolean function indicates how far it is from any linear function. Despite there being several strong results about identifying a linear function and distinguishing one from a sufficiently non-linear function, we found a surprising lack of work on computing the non-linearity of a function. The non-linearity is related to the Walsh coefficient with the largest absolute value; however, the naive attempt of picking the maximum after constructing a Walsh spectrum requires Θ (2 n ) queries to an n -bit function. We improve the scenario by designing highly efficient quantum and randomised algorithms to approximate the non-linearity allowing additive error, denoted λ, with query complexities that depend polynomially on λ. We prove lower bounds to show that these are not very far from the optimal ones. The number of queries made by our randomised algorithm is linear in n , already an exponential improvement, and the number of queries made by our quantum algorithm is surprisingly independent of n . Our randomised algorithm uses a Goldreich-Levin style of navigating all Walsh coefficients and our quantum algorithm uses a clever combination of Deutsch-Jozsa, amplitude amplification and amplitude estimation to improve upon the existing quantum versions of the Goldreich-Levin technique.

Recent advancement of the WWW, IOT, social network, e-commerce, etc. have generated a large volume of data. These datasets are mostly represented by high dimensional and sparse datasets. Many fundamental subroutines of common data analytic tasks such as clustering, classification, ranking, nearest neighbour search, etc. scale poorly with the dimension of the dataset. In this work, we address this problem and propose a sketching (alternatively, dimensionality reduction) algorithm - BinSketch (Binary Data Sketch) - for sparse binary datasets. BinSketch preserves the binary version of the dataset after sketching and maintains estimates for multiple similarity measures such as Jaccard, Cosine, Inner-Product similarities, and Hamming distance, on the same sketch. We present a theoretical analysis of our algorithm and complement it with extensive experimentation on several real-world datasets. We compare the performance of our algorithm with the state-of-the-art algorithms on the task of mean-square-error and ranking. Our proposed algorithm offers a comparable accuracy while suggesting a significant speedup in the dimensionality reduction time, with respect to the other candidate algorithms. Our proposal is simple, easy to implement, and therefore can be adopted in practice.

Discovering "closely related entities" in any network, a.k.a. communities, is a key goal for various network analytic applications. In particular, cliques and bicliques are two community structures that have influenced several tools and techniques in Big Data and social networking. A clique is a complete subgraph of an undirected graph and similarly, a biclique is a complete bipartite subgraph. A maximal clique (or biclique) is a clique that is not subset of any other clique (or biclique). Algorithms to list all maximal cliques in general graphs or bicliques in bipartite graphs have been previously studied. In this paper, we enhance these solutions explaining how a novel structure, that we call clique-biclique can be used to unravel richer communities with respect to different problems in a wide variety of networks. We then give two algorithms for efficiently listing maximal labelled-cliques and maximal clique-bicliques. The first algorithm is an extension of the maximal clique enumeration and the second cleverly combines enumeration of maximal cliques and maximal bicliques. We conduct an experimental analysis over different synthetic and real datasets to evaluate performance of the algorithms, and we found that even richer communities compared to cliques and bicliques can be efficiently found in most networks of interest.

Detection and isolation of faults is a crucial step in the physical realization of quantum circuits. Even though quantum gates and circuits compute reversible functions, the standard techniques of automatic test pattern generation (ATPG) for classical reversible circuits are not directly applicable to quantum circuits. For faulty quantum circuits under the widely accepted single fault assumption, we show that their behavior can be fully characterized by the (single) faulty gate and the corresponding fault model. This allows us to efficiently determine test input states as well as measurement strategy for fault detection and diagnosis. Building on top of these, we design randomized algorithms which are able to detect every nontrivial single-gate fault with minimal probability of error. We also describe similar algorithms for fault diagnosis. We evaluate our algorithms by the number of output samples that needs to be collected and the probability of error. Both of these can be related to the eigenvalues of the operators corresponding to the circuit gates. We experimentally compare all our strategies with the state-of-the-art ATPG techniques for quantum circuits under the “single missing faulty gate” model and demonstrate that significant improvement is possible if we can exploit the quantum nature of circuits.

There is a growing trend towards enriching the RDF content from its classical Subject-Predicate-Object triple form to an annotated representation which can model richer relationships such as including fact provenance, fact confidence, higher-order relationships and so on. One of the recommended ways to achieve this is to use reification and represent it as N-Quads "or simply quads" where an additional identifier is associated with the entire RDF statement which can then be used to add further annotations. A typical use of such annotations is to have quantifiable confidence values to be attached to facts. In such settings, it is important to support efficient top-k queries, typically over user-defined ranking functions containing sentence level confidence values in addition to other quantifiable values in the database. In this paper, we present Quark-X, an RDF-store and SPARQL processing system for reified RDF data represented in the form of quads. This paper presents the overall architecture of our system -- illustrating the modifications which need to be made to a native quad store for it to process top-k queries. In Quark-X, we propose indexing and query processing techniques for making top-k querying efficient. In addition, we present the results of a comprehensive empirical evaluation of our system over Yago2S and DBpedia datasets. Our performance study shows that the proposed method achieves one to two order of magnitude speed-up over baseline solutions.

Parallel graph algorithms continue to attract a lot of research attention given their applications to several fields of sciences and engineering. Efficient design and implementation of graph algorithms on modern manycore accelerators has to however contend with a host of challenges including not being able to reach full memory system throughput and irregularity. Of late, focusing on real-world graphs, researchers are addressing these challenges by using decomposition and preprocessing techniques guided by the structural properties of such graphs. In this direction, we present a new GPU algorithm for obtaining an ear decomposition of a graph. Our implementation of the proposed algorithm on an NVidia Tesla K40c improves the state-of-the-art by a factor of 2.3x on average on a collection of real-world and synthetic graphs. The improved performance of our algorithm is due to our proposed characterization that identifies edges of the graph as redundant for the purposes of an ear decomposition. We then study an application of the ear decomposition of a graph in computing the betweenness-centrality values of nodes in the graph. We use an ear decomposition of the input graph to systematically remove nodes of degree two. The actual computation of betweenness-centrality is done on the remaining nodes and the results are extended to nodes removed in the previous step. We show that this approach improves the state-of-the-art for computing betweenness-centrality on an NVidia K40c GPU by a factor of 1.9x on average over a collection of real-world graphs.

Time-series of geo-tagged data are routinely generated from GPS enabled devices, satellites and other motion capturing instruments. Such data can be thought of as sequences of locations where every location is associated with additional text annotations. Pattern mining for important sequences (aka. trajectory mining) is essential to extract information from such a database. However, the current trend of anonymization to avoid privacy breach makes it difficult to identify any correlation in the data, thus making it even harder, if not impossible, to look for actual trajectories. Noting this difficulty, we define our goal as mining for trajectory-patterns which is a generalization of trajectories. We first design a pattern-growth based algorithm towards this objective. Further, by identifying the limitation of the state-of-the-art sequential pattern growth algorithms in growing trajectory-patterns, we propose a new pattern growth algorithm-- Mintra. Experiments were performed to demonstrate efficiency and effectiveness of Mintra. We, therefore, show that important patterns can be mined from anonymized data without compromising user privacy.