OpenRaiser/Intern-Atlas huggingface dataset:
BB-Graph: A Subgraph Isomorphism Algorithm for Efficiently Querying Big Graph Databases
Venue: arXiv cs.DS 2018
Year: 2018

The big graph database model provides strong modeling for complex applications and efficient querying. However, it is still a big challenge to find all exact matches of a query graph in a big graph database, which is known as the subgraph isomorphism problem. The current subgraph isomorphism approaches are built on Ullmann's idea of focusing on the strategy of pruning out the irrelevant candidates. Nevertheless, the existing pruning techniques need much more improvement to efficiently handle complex queries. Moreover, many of those existing algorithms need large indices requiring extra memory consumption. Motivated by these, we introduce a new subgraph isomorphism algorithm, named as BB-Graph, for querying big graph databases efficiently without requiring a large data structure to be stored in main memory. We test and compare our proposed BB-Graph algorithm with two popular existing approaches, GraphQL and Cypher. Our experiments are done on three different data sets; (1) a very big graph database of a real-life population database, (2) a graph database of a simulated bank database, and (3) the publicly available World Cup big graph database. We show that our solution performs better than those algorithms mentioned here for most of the query types experimented on these big databases.
The Rise and Fall of Network Stars: Analyzing 2.5 million graphs to reveal how high-degree vertices emerge over time
Venue: arXiv cs.SI 2018
Year: 2018

Trends change rapidly in today's world, prompting this key question: What is the mechanism behind the emergence of new trends? By representing real-world dynamic systems as complex networks, the emergence of new trends can be symbolized by vertices that "shine." That is, at a specific time interval in a network's life, certain vertices become increasingly connected to other vertices. This process creates new high-degree vertices, i.e., network stars. Thus, to study trends, we must look at how networks evolve over time and determine how the stars behave. In our research, we constructed the largest publicly available network evolution dataset to date, which contains 38,000 real-world networks and 2.5 million graphs. Then, we performed the first precise wide-scale analysis of the evolution of networks with various scales. Three primary observations resulted: (a) links are most prevalent among vertices that join a network at a similar time; (b) the rate that new vertices join a network is a central factor in molding a network's topology; and (c) the emergence of network stars (high-degree vertices) is correlated with fast-growing networks. We applied our learnings to develop a flexible network-generation model based on large-scale, real-world data. This model gives a better understanding of how stars rise and fall within networks, and is applicable to dynamic systems both in nature and society.
Learnable pooling with Context Gating for video classification
Venue: arXiv cs.CV 2018
Year: 2018

Current methods for video analysis often extract frame-level features using pre-trained convolutional neural networks (CNNs). Such features are then aggregated over time e.g., by simple temporal averaging or more sophisticated recurrent neural networks such as long short-term memory (LSTM) or gated recurrent units (GRU). In this work we revise existing video representations and study alternative methods for temporal aggregation. We first explore clustering-based aggregation layers and propose a two-stream architecture aggregating audio and visual features. We then introduce a learnable non-linear unit, named Context Gating, aiming to model interdependencies among network activations. Our experimental results show the advantage of both improvements for the task of video classification. In particular, we evaluate our method on the large-scale multi-modal Youtube-8M v2 dataset and outperform all other methods in the Youtube 8M Large-Scale Video Understanding challenge.
Deep Learning Methods for Improved Decoding of Linear Codes
Venue: arXiv cs.IT 2018
Year: 2018

The problem of low complexity, close to optimal, channel decoding of linear codes with short to moderate block length is considered. It is shown that deep learning methods can be used to improve a standard belief propagation decoder, despite the large example space. Similar improvements are obtained for the min-sum algorithm. It is also shown that tying the parameters of the decoders across iterations, so as to form a recurrent neural network architecture, can be implemented with comparable results. The advantage is that significantly less parameters are required. We also introduce a recurrent neural decoder architecture based on the method of successive relaxation. Improvements over standard belief propagation are also observed on sparser Tanner graph representations of the codes. Furthermore, we demonstrate that the neural belief propagation decoder can be used to improve the performance, or alternatively reduce the computational complexity, of a close to optimal decoder of short BCH codes.
End-to-end Conversation Modeling Track in DSTC6
Venue: arXiv cs.CL 2018
Year: 2018

End-to-end training of neural networks is a promising approach to automatic construction of dialog systems using a human-to-human dialog corpus. Recently, Vinyals et al. tested neural conversation models using OpenSubtitles. Lowe et al. released the Ubuntu Dialogue Corpus for researching unstructured multi-turn dialogue systems. Furthermore, the approach has been extended to accomplish task oriented dialogs to provide information properly with natural conversation. For example, Ghazvininejad et al. proposed a knowledge grounded neural conversation model [3], where the research is aiming at combining conversational dialogs with task-oriented knowledge using unstructured data such as Twitter data for conversation and Foursquare data for external knowledge.However, the task is still limited to a restaurant information service, and has not yet been tested with a wide variety of dialog tasks. In addition, it is still unclear how to create intelligent dialog systems that can respond like a human agent. In consideration of these problems, we proposed a challenge track to the 6th dialog system technology challenges (DSTC6) using human-to-human dialog data to mimic human dialog behaviors. The focus of the challenge track is to train end-to-end conversation models from human-to-human conversation and accomplish end-to-end dialog tasks in various situations assuming a customer service, in which a system plays a role of human agent and generates natural and informative sentences in response to user's questions or comments given dialog context.
Computing Exact and Approximate Blocking Probabilities in Elastic Optical Networks
Venue: arXiv cs.NI 2018
Year: 2018

In this paper, we propose the first exact Markov model for connection blocking analysis in elastic optical networks, based on the occupancy status of spectrum slices on all links due to arrivals and departures of various classes of connections in a network. Since the complexity of the exact Markov model grows exponentially with the link capacity, number of links, routes, and classes of demands, we further advance the state-of-the-art in computing approximate blocking probability in elastic optical networks and propose two novel approximations, i.e., load-independent and load-dependent. These approximations are used to compute state-dependent per-class connection setup rates in multi-class elastic optical networks with or without spectrum converters by taking into account the spectrum fragmentation factor in each state. We validate approximation analysis by exact and/or simulation results, and show that load-independent and load-dependent approximations can be more accurately used than previously proposed approximations, under a random-fit (RF) and a first-fit (FF) spectrum allocation policies. The approximate results match closely with the exact model, for smaller networks, and with the simulations under a variety of network scenarios.
Control Synthesis for Permutation-Symmetric High-Dimensional Systems With Counting Constraints
Venue: arXiv cs.SY 2018
Year: 2018

General purpose correct-by-construction synthesis methods are limited to systems with low dimensionality or simple specifications. In this work we consider highly symmetrical counting problems and exploit the symmetry to synthesize provably correct controllers for systems with tens of thousands of states. The key ingredients of the solution are an aggregate abstraction procedure for mildly heterogeneous systems and a formulation of counting constraints as linear inequalities.
IS-ASGD: Accelerating Asynchronous SGD using Importance Sampling
Venue: arXiv cs.DC 2018
Year: 2018

Variance reduction (VR) techniques for convergence rate acceleration of stochastic gradient descent (SGD) algorithm have been developed with great efforts recently. VR's two variants, stochastic variance-reduced-gradient (SVRG-SGD) and importance sampling (IS-SGD) have achieved remarkable progresses. Meanwhile, asynchronous SGD (ASGD) is becoming more critical due to the ever-increasing scale of the optimization problems. The application of VR in ASGD to accelerate its convergence rate has therefore attracted much interest and SVRG-ASGDs are therefore proposed. However, we found that SVRG suffers dissatisfying performance in accelerating ASGD when the datasets are sparse and large-scale. In such case, SVRG-ASGD's iterative computation cost is magnitudes higher than ASGD which makes it very slow. On the other hand, IS achieves improved convergence rate with few extra computation cost and is invariant to the sparsity of dataset. This advantage makes it very suitable for the acceleration of ASGD for large-scale sparse datasets. In this paper we propose a novel IS-combined ASGD for effective convergence rate acceleration, namely, IS-ASGD. We theoretically prove the superior convergence bound of IS-ASGD. Experimental results also demonstrate our statements.
On subtrees of the representation tree in rational base numeration systems
Venue: arXiv cs.DM 2018
Year: 2018

Every rational number p/q defines a rational base numeration system in which every integer has a unique finite representation, up to leading zeroes. This work is a contribution to the study of the set of the representations of integers. This prefix-closed subset of the free monoid is naturally represented as a highly non-regular tree. Its nodes are the integers, its edges bear labels taken in {0,1,...,p-1}, and its subtrees are all distinct. We associate with each subtree (or with its root n) three infinite words. The bottom word of n is the lexicographically smallest word that is the label of a branch of the subtree. The top word of n is defined similarly. The span-word of n is the digitwise difference between the latter and the former. First, we show that the set of all the span-words is accepted by an infinite automaton whose underlying graph is essentially the same as the tree itself. Second, we study the function that computes for all n the bottom word associated with n+1 from the one associated with n, and show that it is realised by an infinite sequential transducer whose underlying graph is once again essentially the same as the tree itself. An infinite word may be interpreted as an expansion in base p/q after the radix point, hence evaluated to a real number. If T is a subtree whose root is n, then the evaluations of the labels of the branches of T form an interval of $\mathbb{R}$. The length of this interval is called the span of n and is equal to the evaluation of the span-word of n. The set of all spans is then a subset of R and we use the preceding construction to study its topological closure. We show that it is an interval when p is greater than or equal to 2q-1, and a Cantor set of measure zero otherwise.
An adaptive prefix-assignment technique for symmetry reduction
Venue: arXiv cs.LO 2018
Year: 2018

This paper presents a technique for symmetry reduction that adaptively assigns a prefix of variables in a system of constraints so that the generated prefix-assignments are pairwise nonisomorphic under the action of the symmetry group of the system. The technique is based on McKay's canonical extension framework [J.~Algorithms 26 (1998), no.~2, 306--324]. Among key features of the technique are (i) adaptability---the prefix sequence can be user-prescribed and truncated for compatibility with the group of symmetries; (ii) parallelizability---prefix-assignments can be processed in parallel independently of each other; (iii) versatility---the method is applicable whenever the group of symmetries can be concisely represented as the automorphism group of a vertex-colored graph; and (iv) implementability---the method can be implemented relying on a canonical labeling map for vertex-colored graphs as the only nontrivial subroutine. To demonstrate the practical applicability of our technique, we have prepared an experimental open-source implementation of the technique and carry out a set of experiments that demonstrate ability to reduce symmetry on hard instances. Furthermore, we demonstrate that the implementation effectively parallelizes to compute clusters with multiple nodes via a message-passing interface.
Ordered and Delayed Adversaries and How to Work against Them on a Shared Channel
Venue: arXiv cs.DC 2018
Year: 2018

In this work we define a class of ordered adversaries causing distractions according to some partial order fixed by the adversary before the execution, and study how they affect performance of algorithms. We focus on the Do-All problem of performing t tasks on a shared channel consisting of p crash-prone stations. The channel restricts communication: no message is delivered to the alive stations if more than one station transmits at the same time. The performance measure for the Do-All problem is work: the total number of available processor steps during the whole execution. We address the question of how the ordered adversaries controlling crashes of stations influence work performance of Do-All algorithms. The first presented algorithm solves Do-All with work O(t+p\sqrt{t}\log p) against the Linearly-Ordered adversary, restricted by some pre-defined linear order of crashing stations. Another algorithm runs against the Weakly-Adaptive adversary, restricted by some pre-defined set of f crash-prone stations (it can be seen as restricted by the order being an anti-chain of crashing stations). The work done by this algorithm is O(t+p\sqrt{t}+p\min{p/(p-f),t}\log p). Both results are close to the corresponding lower bounds from [CKL]. We generalize this result to the class of adversaries restricted by a partial order with a maximum anti-chain of size k and complement with the lower bound. We also consider a class of delayed adaptive adversaries, who could see random choices with some delay. We give an algorithm that runs against the 1-RD adversary (seeing random choices of stations with one round delay), achieving close to optimal O(t+p\sqrt{t}\log^2 p) work complexity. This shows that restricting adversary by even 1 round delay results in (almost) optimal work on a shared channel.
Paying More Attention to Saliency: Image Captioning with Saliency and Context Attention
Venue: arXiv cs.CV 2018
Year: 2018

Image captioning has been recently gaining a lot of attention thanks to the impressive achievements shown by deep captioning architectures, which combine Convolutional Neural Networks to extract image representations, and Recurrent Neural Networks to generate the corresponding captions. At the same time, a significant research effort has been dedicated to the development of saliency prediction models, which can predict human eye fixations. Even though saliency information could be useful to condition an image captioning architecture, by providing an indication of what is salient and what is not, research is still struggling to incorporate these two techniques. In this work, we propose an image captioning approach in which a generative recurrent neural network can focus on different parts of the input image during the generation of the caption, by exploiting the conditioning given by a saliency prediction model on which parts of the image are salient and which are contextual. We show, through extensive quantitative and qualitative experiments on large scale datasets, that our model achieves superior performances with respect to captioning baselines with and without saliency, and to different state of the art approaches combining saliency and captioning.
Generative Bridging Network in Neural Sequence Prediction
Venue: arXiv cs.AI 2018
Year: 2018

In order to alleviate data sparsity and overfitting problems in maximum likelihood estimation (MLE) for sequence prediction tasks, we propose the Generative Bridging Network (GBN), in which a novel bridge module is introduced to assist the training of the sequence prediction model (the generator network). Unlike MLE directly maximizing the conditional likelihood, the bridge extends the point-wise ground truth to a bridge distribution conditioned on it, and the generator is optimized to minimize their KL-divergence. Three different GBNs, namely uniform GBN, language-model GBN and coaching GBN, are proposed to penalize confidence, enhance language smoothness and relieve learning burden. Experiments conducted on two recognized sequence prediction tasks (machine translation and abstractive text summarization) show that our proposed GBNs can yield significant improvements over strong baselines. Furthermore, by analyzing samples drawn from different bridges, expected influences on the generator are verified.
Optimal quinary cyclic codes with minimum distance four
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, by analyzing solutions of certain equations in the finite field $\mathbb{F}_{5^m}$, three classes of new optimal quinary cyclic codes with parameters $[5^m-1,5^m-2m-2,4]$ and two theorems are presented. With the help of the two theorems, perfect nonlinear monomials, almost perfect nonlinear monomials and a number of other monomials are used to construct more classes of new optimal quinary cyclic codes with the same parameters.
Relativization and Interactive Proof Systems in Parameterized Complexity Theory
Venue: arXiv cs.CC 2018
Year: 2018

We introduce some classical complexity-theoretic techniques to Parameterized Complexity. First, we study relativization for the machine models that were used by Chen, Flum, and Grohe (2005) to characterize a number of parameterized complexity classes. Here we obtain a new and non-trivial characterization of the A-Hierarchy in terms of oracle machines, and parameterize a famous result of Baker, Gill, and Solovay (1975), by proving that, relative to specific oracles, FPT and A[1] can either coincide or differ (a similar statement holds for FPT and W[P]). Second, we initiate the study of interactive proof systems in the parameterized setting, and show that every problem in the class AW[SAT] has a proof system with "short" interactions, in the sense that the number of rounds is upper-bounded in terms of the parameter value alone.
Towards Practical Differential Privacy for SQL Queries
Venue: arXiv cs.CR 2018
Year: 2018

Differential privacy promises to enable general data analytics while protecting individual privacy, but existing differential privacy mechanisms do not support the wide variety of features and databases used in real-world SQL-based analytics systems. This paper presents the first practical approach for differential privacy of SQL queries. Using 8.1 million real-world queries, we conduct an empirical study to determine the requirements for practical differential privacy, and discuss limitations of previous approaches in light of these requirements. To meet these requirements we propose elastic sensitivity, a novel method for approximating the local sensitivity of queries with general equijoins. We prove that elastic sensitivity is an upper bound on local sensitivity and can therefore be used to enforce differential privacy using any local sensitivity-based mechanism. We build FLEX, a practical end-to-end system to enforce differential privacy for SQL queries using elastic sensitivity. We demonstrate that FLEX is compatible with any existing database, can enforce differential privacy for real-world SQL queries, and incurs negligible (0.03%) performance overhead.
Recurrent neural networks with specialized word embeddings for health-domain named-entity recognition
Venue: arXiv cs.CL 2018
Year: 2018

Background. Previous state-of-the-art systems on Drug Name Recognition (DNR) and Clinical Concept Extraction (CCE) have focused on a combination of text "feature engineering" and conventional machine learning algorithms such as conditional random fields and support vector machines. However, developing good features is inherently heavily time-consuming. Conversely, more modern machine learning approaches such as recurrent neural networks (RNNs) have proved capable of automatically learning effective features from either random assignments or automated word "embeddings". Objectives. (i) To create a highly accurate DNR and CCE system that avoids conventional, time-consuming feature engineering. (ii) To create richer, more specialized word embeddings by using health domain datasets such as MIMIC-III. (iii) To evaluate our systems over three contemporary datasets. Methods. Two deep learning methods, namely the Bidirectional LSTM and the Bidirectional LSTM-CRF, are evaluated. A CRF model is set as the baseline to compare the deep learning systems to a traditional machine learning approach. The same features are used for all the models. Results. We have obtained the best results with the Bidirectional LSTM-CRF model, which has outperformed all previously proposed systems. The specialized embeddings have helped to cover unusual words in DDI-DrugBank and DDI-MedLine, but not in the 2010 i2b2/VA IRB Revision dataset. Conclusion. We present a state-of-the-art system for DNR and CCE. Automated word embeddings has allowed us to avoid costly feature engineering and achieve higher accuracy. Nevertheless, the embeddings need to be retrained over datasets that are adequate for the domain, in order to adequately cover the domain-specific vocabulary.
Color-opponent mechanisms for local hue encoding in a hierarchical framework
Venue: arXiv cs.CV 2018
Year: 2018

A biologically plausible computational model for color representation is introduced. We present a mechanistic hierarchical model of neurons that not only successfully encodes local hue, but also explicitly reveals how the contributions of each visual cortical layer participating in the process can lead to a hue representation. Our proposed model benefits from studies on the visual cortex and builds a network of single-opponent and hue-selective neurons. Local hue encoding is achieved through gradually increasing nonlinearity in terms of cone inputs to single-opponent cells. We demonstrate that our model's single-opponent neurons have wide tuning curves, while the hue-selective neurons in our model V4 layer exhibit narrower tunings, resembling those in V4 of the primate visual system. Our simulation experiments suggest that neurons in V4 or later layers have the capacity of encoding unique hues. Moreover, with a few examples, we present the possibility of spanning the infinite space of physical hues by combining the hue-selective neurons in our model.