OpenRaiser/Intern-Atlas huggingface dataset:
Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds
Venue: arXiv cs.CC 2016
Year: 2016

Given an $n*n$ sparse symmetric matrix with $m$ nonzero entries, performing Gaussian elimination may turn some zeroes into nonzero values. To maintain the matrix sparse, we would like to minimize the number $k$ of these changes, hence called the minimum fill-in problem. Agrawal et al.~[FOCS'90] developed the first approximation algorithm, based on early heuristics by George [SIAM J Numer Anal 10] and by Lipton et al.~[SIAM J Numer Anal 16]. The objective function they used is $m+k$, the number of nonzero elements after elimination. An approximation algorithm using $k$ as the objective function was presented by Natanzon et al.~[STOC'98]. These two versions are incomparable in terms of approximation. Parameterized algorithms for the problem was first studied by Kaplan et al.~[FOCS'94]. Fomin & Villanger [SODA'12] recently gave an algorithm running in time $2^{O(\sqrt{k} \log k)}+n^{O(1)}$. Hardness results of this problem are surprisingly scarce, and the few known ones are either weak or have to use nonstandard complexity conjectures. The only inapproximability result by Wu et al.~[IJCAI'15] applies to only the objective function $m+k$, and is grounded on the Small Set Expansion Conjecture. The only nontrivial parameterized lower bounds, by Bliznets et al.~[SODA'16], include a very weak one based on ETH, and a strong one based on hardness of subexponential-time approximation of the minimum bisection problem on regular graphs. For both versions of the problem, we exclude the existence of PTASs, assuming P$\ne$NP, and the existence of $2^{O(n^{1-δ})}$-time approximation schemes for any positive $δ$, assuming ETH. It also implies a $2^{O(k^{1/2-δ})} n^{O(1)}$ parameterized lower bound. Behind these results is a new reduction from vertex cover, which might be of its own interest: All previous reductions for similar problems are from some kind of graph layout problems.
Symmetric and antisymmetric properties of solutions to kernel-based machine learning problems
Venue: arXiv cs.LG 2016
Year: 2016

A particularly interesting instance of supervised learning with kernels is when each training example is associated with two objects, as in pairwise classification (Brunner et al., 2012), and in supervised learning of preference relations (Herbrich et al., 1998). In these cases, one may want to embed additional prior knowledge into the optimization problem associated with the training of the learning machine, modeled, respectively, by the symmetry of its optimal solution with respect to an exchange of order between the two objects, and by its antisymmetry. Extending the approach proposed in (Brunner et al., 2012) (where the only symmetric case was considered), we show, focusing on support vector binary classification, how such embedding is possible through the choice of a suitable pairwise kernel, which takes as inputs the individual feature vectors and also the group feature vectors associated with the two objects. We also prove that the symmetry/antisymmetry constraints still hold when considering the sequence of suboptimal solutions generated by one version of the Sequential Minimal Optimization (SMO) algorithm, and we present numerical results supporting the theoretical findings. We conclude discussing extensions of the main results to support vector regression, to transductive support vector machines, and to several kinds of graph kernels, including diffusion kernels.
Event Identification in Social Networks
Venue: arXiv cs.IR 2016
Year: 2016

Social networks enable users to freely communicate with each other and share their recent news, ongoing activities or views about different topics. As a result, they can be seen as a potentially viable source of information to understand the current emerging topics/events. The ability to model emerging topics is a substantial step to monitor and summarize the information originating from social sources. Applying traditional methods for event detection which are often proposed for processing large, formal and structured documents, are less effective, due to the short length, noisiness and informality of the social posts. Recent event detection techniques address these challenges by exploiting the opportunities behind abundant information available in social networks. This article provides an overview of the state of the art in event detection from social networks.
Finite Blocklength Performance of Multi-Terminal Wireless Industrial Networks
Venue: arXiv cs.IT 2016
Year: 2016

This work focuses on the performance of multi-terminal wireless industrial networks, where the transmissions of all terminals are required to be scheduled within a tight deadline. The transmissions thus share a fixed amount of resources, i.e., symbols, while facing short blocklengths due to the low-latency requirement. We investigate two distinct relaying strategies, namely best relay selection among the participating terminals and best antenna selection at the access point of the network. In both schemes, we incorporate the cost of acquiring instantaneous Channel State Information (CSI) at the access point within the transmission deadline. An error probability model is developed under the finite blocklength regime to provide accurate performance results. As a reference, this model is compared to the corresponding infinite bocklength error model. Both analytical models are validated by simulation. We show that the average Packet Error Rate (PER) over all terminals is convex in the target error probability at each single link. Moreover, we find that: (i) The reliability behavior is different for the two strategies, while the limiting factors are both finite blocklengths and overhead of acquiring CSI. (ii) With the same order of diversity, best antenna selection is more reliable than best relay selection. (iii) The average PER is increasing in the number of participating terminals unless the terminals also act as relay candidates. In particular, if each participating terminal is a candidate for best relay selection, the PER is convex in the number of terminals.
RDF Graph Alignment with Bisimulation
Venue: arXiv cs.DB 2016
Year: 2016

We investigate the problem of aligning two RDF databases, an essential problem in understanding the evolution of ontologies. Our approaches address three fundamental challenges: 1) the use of "blank" (null) names, 2) ontology changes in which different names are used to identify the same entity, and 3) small changes in the data values as well as small changes in the graph structure of the RDF database. We propose approaches inspired by the classical notion of graph bisimulation and extend them to capture the natural metrics of edit distance on the data values and the graph structure. We evaluate our methods on three evolving curated data sets. Overall, our results show that the proposed methods perform well and are scalable.
Hierarchical Neural Language Models for Joint Representation of Streaming Documents and their Content
Venue: arXiv cs.CL 2016
Year: 2016

We consider the problem of learning distributed representations for documents in data streams. The documents are represented as low-dimensional vectors and are jointly learned with distributed vector representations of word tokens using a hierarchical framework with two embedded neural language models. In particular, we exploit the context of documents in streams and use one of the language models to model the document sequences, and the other to model word sequences within them. The models learn continuous vector representations for both word tokens and documents such that semantically similar documents and words are close in a common vector space. We discuss extensions to our model, which can be applied to personalized recommendation and social relationship mining by adding further user layers to the hierarchy, thus learning user-specific vectors to represent individual preferences. We validated the learned representations on a public movie rating data set from MovieLens, as well as on a large-scale Yahoo News data comprising three months of user activity logs collected on Yahoo servers. The results indicate that the proposed model can learn useful representations of both documents and word tokens, outperforming the current state-of-the-art by a large margin.
Using Sequence Ensembles for Seeding Alignments of MinION Sequencing Data
Venue: arXiv cs.DS 2016
Year: 2016

Oxford Nanopore MinION sequencer is currently the smallest sequencing device available. While being able to produce very long reads (reads of up to 100~kbp were reported), it is prone to high sequencing error rates of up to 30%. Since most of these errors are insertions or deletions, it is very difficult to adapt popular seed-based algorithms designed for aligning data sets with much lower error rates. Base calling of MinION reads is typically done using hidden Markov models. In this paper, we propose to represent each sequencing read by an ensemble of sequences sampled from such a probabilistic model. This approach can improve the sensitivity and false positive rate of seeding an alignment compared to using a single representative base call sequence for each read.
Theta-RBM: Unfactored Gated Restricted Boltzmann Machine for Rotation-Invariant Representations
Venue: arXiv cs.CV 2016
Year: 2016

Learning invariant representations is a critical task in computer vision. In this paper, we propose the Theta-Restricted Boltzmann Machine (θ-RBM in short), which builds upon the original RBM formulation and injects the notion of rotation-invariance during the learning procedure. In contrast to previous approaches, we do not transform the training set with all possible rotations. Instead, we rotate the gradient filters when they are computed during the Contrastive Divergence algorithm. We formulate our model as an unfactored gated Boltzmann machine, where another input layer is used to modulate the input visible layer to drive the optimisation procedure. Among our contributions is a mathematical proof that demonstrates that θ-RBM is able to learn rotation-invariant features according to a recently proposed invariance measure. Our method reaches an invariance score of ~90% on mnist-rot dataset, which is the highest result compared with the baseline methods and the current state of the art in transformation-invariant feature learning in RBM. Using an SVM classifier, we also showed that our network learns discriminative features as well, obtaining ~10% of testing error.
Active Ranking from Pairwise Comparisons and when Parametric Assumptions Don't Help
Venue: arXiv cs.LG 2016
Year: 2016

We consider sequential or active ranking of a set of n items based on noisy pairwise comparisons. Items are ranked according to the probability that a given item beats a randomly chosen item, and ranking refers to partitioning the items into sets of pre-specified sizes according to their scores. This notion of ranking includes as special cases the identification of the top-k items and the total ordering of the items. We first analyze a sequential ranking algorithm that counts the number of comparisons won, and uses these counts to decide whether to stop, or to compare another pair of items, chosen based on confidence intervals specified by the data collected up to that point. We prove that this algorithm succeeds in recovering the ranking using a number of comparisons that is optimal up to logarithmic factors. This guarantee does not require any structural properties of the underlying pairwise probability matrix, unlike a significant body of past work on pairwise ranking based on parametric models such as the Thurstone or Bradley-Terry-Luce models. It has been a long-standing open question as to whether or not imposing these parametric assumptions allows for improved ranking algorithms. For stochastic comparison models, in which the pairwise probabilities are bounded away from zero, our second contribution is to resolve this issue by proving a lower bound for parametric models. This shows, perhaps surprisingly, that these popular parametric modeling choices offer at most logarithmic gains for stochastic comparisons.
Efficient Routing for Cost Effective Scale-out Data Architectures
Venue: arXiv cs.DB 2016
Year: 2016

Efficient retrieval of information is of key importance when using Big Data systems. In large scale-out data architectures, data are distributed and replicated across several machines. Queries/tasks to such data architectures, are sent to a router which determines the machines containing the requested data. Ideally, to reduce the overall cost of analytics, the smallest set of machines required to satisfy the query should be returned by the router. Mathematically, this can be modeled as the set cover problem, which is NP-hard, thus making the routing process a balance between optimality and performance. Even though an efficient greedy approximation algorithm for routing a single query exists, there is currently no better method for processing multiple queries than running the greedy set cover algorithm repeatedly for each query. This method is impractical for Big Data systems and the state-of-the-art techniques route a query to all machines and choose as a cover the machines that respond fastest. In this paper, we propose an efficient technique to speedup the routing of a large number of real-time queries while minimizing the number of machines that each query touches (query span). We demonstrate that by analyzing the correlation between known queries and performing query clustering, we can reduce the set cover computation time, thereby significantly speeding up routing of unknown queries. Experiments show that our incremental set cover-based routing is 2.5 times faster and can return on average 50% fewer machines per query when compared to repeated greedy set cover and baseline routing techniques.
Image Restoration Using Convolutional Auto-encoders with Symmetric Skip Connections
Venue: arXiv cs.CV 2016
Year: 2016

Image restoration, including image denoising, super resolution, inpainting, and so on, is a well-studied problem in computer vision and image processing, as well as a test bed for low-level image modeling algorithms. In this work, we propose a very deep fully convolutional auto-encoder network for image restoration, which is a encoding-decoding framework with symmetric convolutional-deconvolutional layers. In other words, the network is composed of multiple layers of convolution and de-convolution operators, learning end-to-end mappings from corrupted images to the original ones. The convolutional layers capture the abstraction of image contents while eliminating corruptions. Deconvolutional layers have the capability to upsample the feature maps and recover the image details. To deal with the problem that deeper networks tend to be more difficult to train, we propose to symmetrically link convolutional and deconvolutional layers with skip-layer connections, with which the training converges much faster and attains better results.
subgraph2vec: Learning Distributed Representations of Rooted Sub-graphs from Large Graphs
Venue: arXiv cs.LG 2016
Year: 2016

In this paper, we present subgraph2vec, a novel approach for learning latent representations of rooted subgraphs from large graphs inspired by recent advancements in Deep Learning and Graph Kernels. These latent representations encode semantic substructure dependencies in a continuous vector space, which is easily exploited by statistical models for tasks such as graph classification, clustering, link prediction and community detection. subgraph2vec leverages on local information obtained from neighbourhoods of nodes to learn their latent representations in an unsupervised fashion. We demonstrate that subgraph vectors learnt by our approach could be used in conjunction with classifiers such as CNNs, SVMs and relational data clustering algorithms to achieve significantly superior accuracies. Also, we show that the subgraph vectors could be used for building a deep learning variant of Weisfeiler-Lehman graph kernel. Our experiments on several benchmark and large-scale real-world datasets reveal that subgraph2vec achieves significant improvements in accuracies over existing graph kernels on both supervised and unsupervised learning tasks. Specifically, on two realworld program analysis tasks, namely, code clone and malware detection, subgraph2vec outperforms state-of-the-art kernels by more than 17% and 4%, respectively.
A Time-constraint Satisfying and Cost-reducing node evaluation metric for Message Routing in Mobile Crowd Sensing Networks
Venue: arXiv cs.NI 2016
Year: 2016

In mobile crowd sensing networks data forwarding through opportunistic contacts between participants. Data is replicated to encountered participants. For optimizing data delivery ratio and reducing redundant data a lot of data forwarding schemes, which selectively replicate data to encountered participants through node's data forwarding metric are proposed. However most of them neglect a kind of redundant data whose Time-To-Live is expired. For reducing this kind of redundant data we proposed a new method to evaluate node's data forwarding metric, which is used to measure the node's probability of forwarding data to destination within data's constraint time. The method is divided into two parts. The first is evaluating nodes whether have possibility to contact destination within time constraint based on transient cluster. We propose a method to detect node's transient cluster, which is based on node's contact rate. Only node, which has possibility to contact destination, has chances to the second step. It effectively reduces the computational complexity. The second is calculating data forwarding probability of node to destination according to individual ICT (inter contact time) distribution. Evaluation results show that our proposed transient cluster detection method is more simple and quick. And from two aspects of data delivery ratio and network overhead our approach outperforms other existing data forwarding approach.
Cross-layer design for downlink multi-hop cloud radio access networks with network coding
Venue: arXiv cs.IT 2016
Year: 2016

There are two fundamentally different fronthaul techniques in the downlink communication of cloud radio access network (C-RAN): the data-sharing strategy and the compression-based strategy. Under the former strategy, each user's message is multicast from the central processor (CP) to all the serving remote radio heads (RRHs) over the fronthaul network, which then cooperatively serve the users through joint beamforming; while under the latter strategy, the user messages are first beamformed then quantized at the CP, and the compressed signal is unicast to the corresponding RRH, which then decompresses its received signal for wireless transmission. Previous works show that in general the compression-based strategy outperforms the data-sharing strategy. This paper, on the other hand, point s out that in a C-RAN model where the RRHs are connected to the CP via multi-hop routers, data-sharing can be superior to compression if the network coding technique is adopted for multicasting user messages to the cooperating RRHs, and the RRH's beamforming vectors, the user-RRH association, and the network coding design over the fronthaul network are jointly optimized based on the techniques of sparse optimization an d successive convex approximation. This is in comparison to the compression-based strategy, where information is unicast over the fronthaul network by simple routing, and the RRH's compression noise covariance and beamforming vectors, as well as the routing strategy over the fronthaul network are jointly optimized based on the successive convex approximation technique. The observed gain in overall network throughput is due to that information multicast is more efficient than information unicast over the multi-hop fronthaul of a C-RAN.
Scene Text Detection via Holistic, Multi-Channel Prediction
Venue: arXiv cs.CV 2016
Year: 2016

Recently, scene text detection has become an active research topic in computer vision and document analysis, because of its great importance and significant challenge. However, vast majority of the existing methods detect text within local regions, typically through extracting character, word or line level candidates followed by candidate aggregation and false positive elimination, which potentially exclude the effect of wide-scope and long-range contextual cues in the scene. To take full advantage of the rich information available in the whole natural image, we propose to localize text in a holistic manner, by casting scene text detection as a semantic segmentation problem. The proposed algorithm directly runs on full images and produces global, pixel-wise prediction maps, in which detections are subsequently formed. To better make use of the properties of text, three types of information regarding text region, individual characters and their relationship are estimated, with a single Fully Convolutional Network (FCN) model. With such predictions of text properties, the proposed algorithm can simultaneously handle horizontal, multi-oriented and curved text in real-world natural images. The experiments on standard benchmarks, including ICDAR 2013, ICDAR 2015 and MSRA-TD500, demonstrate that the proposed algorithm substantially outperforms previous state-of-the-art approaches. Moreover, we report the first baseline result on the recently-released, large-scale dataset COCO-Text.
Routing Memento Requests Using Binary Classifiers
Venue: arXiv cs.DL 2016
Year: 2016

The Memento protocol provides a uniform approach to query individual web archives. Soon after its emergence, Memento Aggregator infrastructure was introduced that supports querying across multiple archives simultaneously. An Aggregator generates a response by issuing the respective Memento request against each of the distributed archives it covers. As the number of archives grows, it becomes increasingly challenging to deliver aggregate responses while keeping response times and computational costs under control. Ad-hoc heuristic approaches have been introduced to address this challenge and research has been conducted aimed at optimizing query routing based on archive profiles. In this paper, we explore the use of binary, archive-specific classifiers generated on the basis of the content cached by an Aggregator, to determine whether or not to query an archive for a given URI. Our results turn out to be readily applicable and can help to significantly decrease both the number of requests and the overall response times without compromising on recall. We find, among others, that classifiers can reduce the average number of requests by 77% compared to a brute force approach on all archives, and the overall response time by 42% while maintaining a recall of 0.847.
Distributed Average Tracking for Multiple Signals Generated by Linear Dynamical Systems: An Edge-based Framework
Venue: arXiv cs.SY 2016
Year: 2016

This paper studies the distributed average tracking problem for multiple time-varying signals generated by linear dynamics, whose reference inputs are nonzero and not available to any agent in the network. In the edge-based framework, a pair of continuous algorithms with, respectively, static and adaptive coupling strengths are designed. Based on the boundary layer concept, the proposed continuous algorithm with static coupling strengths can asymptotically track the average of multiple reference signals without the chattering phenomenon. Furthermore, for the case of algorithms with adaptive coupling strengths, average tracking errors are uniformly ultimately bounded and exponentially converge to a small adjustable bounded set. Finally, a simulation example is presented to show the validity of theoretical results.