OpenRaiser/Intern-Atlas huggingface dataset:
Graphlet Decomposition: Framework, Algorithms, and Applications
Venue: arXiv cs.SI 2016
Year: 2016

From social science to biology, numerous applications often rely on graphlets for intuitive and meaningful characterization of networks at both the global macro-level as well as the local micro-level. While graphlets have witnessed a tremendous success and impact in a variety of domains, there has yet to be a fast and efficient approach for computing the frequencies of these subgraph patterns. However, existing methods are not scalable to large networks with millions of nodes and edges, which impedes the application of graphlets to new problems that require large-scale network analysis. To address these problems, we propose a fast, efficient, and parallel algorithm for counting graphlets of size k={3,4}-nodes that take only a fraction of the time to compute when compared with the current methods used. The proposed graphlet counting algorithms leverages a number of proven combinatorial arguments for different graphlets. For each edge, we count a few graphlets, and with these counts along with the combinatorial arguments, we obtain the exact counts of others in constant time. On a large collection of 300+ networks from a variety of domains, our graphlet counting strategies are on average 460x faster than current methods. This brings new opportunities to investigate the use of graphlets on much larger networks and newer applications as we show in the experiments. To the best of our knowledge, this paper provides the largest graphlet computations to date as well as the largest systematic investigation on over 300+ networks from a variety of domains.
Maximizing the Link Throughput between Smart-meters and Aggregators as Secondary Users under Power and Outage Constraints
Venue: arXiv cs.SY 2016
Year: 2016

This paper assesses the communication link from smart meters to aggregators as (unlicensed) secondary users that transmit their data over the (licensed) primary uplink channel. The proposed scenario assumes: (i) meters' and aggregators' positions are fixed so highly directional antennas are employed, (ii) secondary users transmit with limited power in relation to the primary, (iii) meters' transmissions are coordinated to avoid packet collisions, and (iv) the secondary links' robustness is guaranteed by an outage constraint. Under these assumptions, the interference caused by secondary users in both primary (base-stations) and other secondary users can be neglected. As unlicensed users, however, meter-aggregator links do experience interference from the mobile users of the primary network, whose positions and traffic activity are unknown. To cope with this uncertainty, we model the mobile users spatial distribution as a Poisson point process. We then derive a closed-form solution for the maximum achievable throughput with respect to a reference secondary link subject to transmit power and outage constraints. Our numerical results illustrate the effects of such constraints on the optimal throughput, evincing that more frequent outage events improve the system performance in the scenario under study. We also show that relatively high outage probabilities have little effect on the reconstruction of the average power demand curve that is transmitted from the smart-meter to the aggregator.
Early Predictions of Movie Success: the Who, What, and When of Profitability
Venue: arXiv cs.AI 2016
Year: 2016

This paper proposes a decision support system to aid movie investment decisions at the early stage of movie productions. The system predicts the success of a movie based on its profitability by leveraging historical data from various sources. Using social network analysis and text mining techniques, the system automatically extracts several groups of features, including "who" are on the cast, "what" a movie is about, "when" a movie will be released, as well as "hybrid" features that match "who" with "what", and "when" with "what". Experiment results with movies during an 11-year period showed that the system outperforms benchmark methods by a large margin in predicting movie profitability. Novel features we proposed also made great contributions to the prediction. In addition to designing a decision support system with practical utilities, our analysis of key factors for movie profitability may also have implications for theoretical research on team performance and the success of creative work.
LCSTS: A Large Scale Chinese Short Text Summarization Dataset
Venue: arXiv cs.CL 2016
Year: 2016

Automatic text summarization is widely regarded as the highly difficult problem, partially because of the lack of large text summarization data set. Due to the great challenge of constructing the large scale summaries for full text, in this paper, we introduce a large corpus of Chinese short text summarization dataset constructed from the Chinese microblogging website Sina Weibo, which is released to the public {http://icrc.hitsz.edu.cn/Article/show/139.html}. This corpus consists of over 2 million real Chinese short texts with short summaries given by the author of each text. We also manually tagged the relevance of 10,666 short summaries with their corresponding short texts. Based on the corpus, we introduce recurrent neural network for the summary generation and achieve promising results, which not only shows the usefulness of the proposed corpus for short text summarization research, but also provides a baseline for further research on this topic.
Communication Efficient Distributed Agnostic Boosting
Venue: arXiv cs.LG 2016
Year: 2016

We consider the problem of learning from distributed data in the agnostic setting, i.e., in the presence of arbitrary forms of noise. Our main contribution is a general distributed boosting-based procedure for learning an arbitrary concept space, that is simultaneously noise tolerant, communication efficient, and computationally efficient. This improves significantly over prior works that were either communication efficient only in noise-free scenarios or computationally prohibitive. Empirical results on large synthetic and real-world datasets demonstrate the effectiveness and scalability of the proposed approach.
Mining Mid-level Visual Patterns with Deep CNN Activations
Venue: arXiv cs.CV 2016
Year: 2016

The purpose of mid-level visual element discovery is to find clusters of image patches that are both representative and discriminative. Here we study this problem from the prospective of pattern mining while relying on the recently popularized Convolutional Neural Networks (CNNs). We observe that a fully-connected CNN activation extracted from an image patch typically possesses two appealing properties that enable its seamless integration with pattern mining techniques. The marriage between CNN activations and association rule mining, a well-known pattern mining technique in the literature, leads to fast and effective discovery of representative and discriminative patterns from a huge number of image patches. When we retrieve and visualize image patches with the same pattern, surprisingly, they are not only visually similar but also semantically consistent, and thus give rise to a mid-level visual element in our work. Given the patterns and retrieved mid-level visual elements, we propose two methods to generate image feature representations for each. The first method is to use the patterns as codewords in a dictionary, similar to the Bag-of-Visual-Words model, we compute a Bag-of-Patterns representation. The second one relies on the retrieved mid-level visual elements to construct a Bag-of-Elements representation. We evaluate the two encoding methods on scene and object classification tasks, and demonstrate that our approach outperforms or matches recent works using CNN activations for these tasks.
I/Q Imbalance Aware Widely-Linear Receiver for Uplink Multi-Cell Massive MIMO Systems
Venue: arXiv cs.IT 2016
Year: 2016

In-phase/quadrature-phase (I/Q) imbalance is one of the most important hardware impairments in communication systems. It arises in the analogue parts of direct conversion radio frequency (RF) transceivers and can cause severe performance losses. In this paper, I/Q imbalance (IQI) aware widely-linear (WL) channel estimation and data detection schemes for uplink multi-cell massive multiple-input multiple-output (MIMO) systems are proposed. The resulting receiver is a WL extension of the minimum mean square error (MMSE) receiver and jointly mitigates multi-user interference and IQI by processing the real and the imaginary parts of the received signal separately. The IQI arising at both the base station (BS) and the user terminals (UTs) is then taken into account. The considered channel state information (CSI) acquisition model includes the effects of both estimation errors and pilot contamination, which is caused by the reuse of the same training sequences in neighboring cells. We apply results from random matrix theory to derive analytical expressions for the achievable sum rates of the proposed IQI aware and conventional IQI unaware receivers. Our simulation results show that the performance of the proposed IQI aware WLMMSE receiver in a system with IQI is close to that of the MMSE receiver in an ideal system without IQI. Moreover, our results for the sum rate of the IQI unaware MMSE receiver reveal that the performance loss due to IQI can be large and, if left unattended, does not vanish for large numbers of BS antennas.
On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
Venue: arXiv cs.LG 2016
Year: 2016

We study optimization algorithms based on variance reduction for stochastic gradient descent (SGD). Remarkable recent progress has been made in this direction through development of algorithms like SAG, SVRG, SAGA. These algorithms have been shown to outperform SGD, both theoretically and empirically. However, asynchronous versions of these algorithms---a crucial requirement for modern large-scale applications---have not been studied. We bridge this gap by presenting a unifying framework for many variance reduction techniques. Subsequently, we propose an asynchronous algorithm grounded in our framework, and prove its fast convergence. An important consequence of our general approach is that it yields asynchronous versions of variance reduction algorithms such as SVRG and SAGA as a byproduct. Our method achieves near linear speedup in sparse settings common to machine learning. We demonstrate the empirical performance of our method through a concrete realization of asynchronous SVRG.
Device-to-Device Millimeter Wave Communications: Interference, Coverage, Rate, and Finite Topologies
Venue: arXiv cs.IT 2016
Year: 2016

Emerging applications involving device-to-device communication among wearable electronics require Gbps throughput, which can be achieved by utilizing millimeter wave (mmWave) frequency bands. When many such communicating devices are indoors in close proximity, like in a train car or airplane cabin, interference can be a serious impairment. This paper uses stochastic geometry to analyze the performance of mmWave networks with a finite number of interferers in a finite network region. Prior work considered either lower carrier frequencies with different antenna and channel assumptions, or a network with an infinite spatial extent. In this paper, human users not only carry potentially interfering devices, but also act to block interfering signals. Using a sequence of simplifying assumptions, accurate expressions for coverage and rate are developed that capture the effects of key antenna characteristics like directivity and gain, and are a function of the finite area and number of users. The assumptions are validated through a combination of analysis and simulation. The main conclusions are that mmWave frequencies can provide Gbps throughput even with omni-directional transceiver antennas, and larger, more directive antenna arrays give better system performance.
Apply Artificial Noise To Secure Fading Relay Networks: A SER-Based Approach
Venue: arXiv cs.IT 2016
Year: 2016

We apply the concept of artificial and controlled interference in a triangular relay network with an untrusted relay aiming at enhancing the wireless communication secrecy between the source and the destination node. In order to shield the square quadrature amplitude modulated (QAM) signals transmitted from the source node to the relay, the destination node designs and transmits artificial noise (AN) symbols to jam the relay reception. The objective of our considered AN design is to degrade the error probability performance at the untrusted relay, for different types of channel state information (CSI) at the destination. By considering perfect knowledge of the instantaneous CSI of the source-to-relay and relay-to-destination links, we first present an analytical expression for the symbol error rate (SER) performance at the relay. Based on the assumption of an average power constraint at the destination node, we then derive the optimal phase and power distribution of the AN that maximizes the SER at the relay. Furthermore, we obtain the optimal AN design for the case where only statistical CSI is available at the destination node. For both cases, our study reveals that the Gaussian distribution is generally not optimal to generate AN symbols. In particular, the conducted numerical results show that the Gaussian distributed AN is far from optimal. The presented AN design takes into account practical parameters for the communication links, such as QAM signaling and maximum likelihood decoding.
A Novel Approach for Stable Selection of Informative Redundant Features from High Dimensional fMRI Data
Venue: arXiv cs.CV 2016
Year: 2016

Feature selection is among the most important components because it not only helps enhance the classification accuracy, but also or even more important provides potential biomarker discovery. However, traditional multivariate methods is likely to obtain unstable and unreliable results in case of an extremely high dimensional feature space and very limited training samples, where the features are often correlated or redundant. In order to improve the stability, generalization and interpretations of the discovered potential biomarker and enhance the robustness of the resultant classifier, the redundant but informative features need to be also selected. Therefore we introduced a novel feature selection method which combines a recent implementation of the stability selection approach and the elastic net approach. The advantage in terms of better control of false discoveries and missed discoveries of our approach, and the resulted better interpretability of the obtained potential biomarker is verified in both synthetic and real fMRI experiments. In addition, we are among the first to demonstrate the robustness of feature selection benefiting from the incorporation of stability selection and also among the first to demonstrate the possible unrobustness of the classical univariate two-sample t-test method. Specifically, we show the robustness of our feature selection results in existence of noisy (wrong) training labels, as well as the robustness of the resulted classifier based on our feature selection results in the existence of data variation, demonstrated by a multi-center attention-deficit/hyperactivity disorder (ADHD) fMRI data.
Unsupervised Semantic Parsing of Video Collections
Venue: arXiv cs.CV 2016
Year: 2016

Human communication typically has an underlying structure. This is reflected in the fact that in many user generated videos, a starting point, ending, and certain objective steps between these two can be identified. In this paper, we propose a method for parsing a video into such semantic steps in an unsupervised way. The proposed method is capable of providing a semantic "storyline" of the video composed of its objective steps. We accomplish this using both visual and language cues in a joint generative model. The proposed method can also provide a textual description for each of the identified semantic steps and video segments. We evaluate this method on a large number of complex YouTube videos and show results of unprecedented quality for this intricate and impactful problem.
The First Reactive Synthesis Competition (SYNTCOMP 2014)
Venue: arXiv cs.LO 2016
Year: 2016

We introduce the reactive synthesis competition (SYNTCOMP), a long-term effort intended to stimulate and guide advances in the design and application of synthesis procedures for reactive systems. The first iteration of SYNTCOMP is based on the controller synthesis problem for finite-state systems and safety specifications. We provide an overview of this problem and existing approaches to solve it, and report on the design and results of the first SYNTCOMP. This includes the definition of the benchmark format, the collection of benchmarks, the rules of the competition, and the five synthesis tools that participated. We present and analyze the results of the competition and draw conclusions on the state of the art. Finally, we give an outlook on future directions of SYNTCOMP.
Smart Small Cell with Hybrid Beamforming for 5G: Theoretical Feasibility and Prototype Results
Venue: arXiv cs.NI 2016
Year: 2016

In this article, we present a real-time three dimensional (3D) hybrid beamforming for fifth generation (5G) wireless networks. One of the key concepts in 5G cellular systems is the small cell network, which settles the high mobile traffic demand and provides uniform user-experienced data rates. The overall capacity of the small cell network can be enhanced with the enabling technology of 3D hybrid beamforming. This study validates the feasibility of the 3D hybrid beamforming, mostly for link-level performances, through the implementation of a realtime testbed using a software-defined radio (SDR) platform and fabricated antenna array. Based on the measured data, we also investigate system-level performances to verify the gain of the proposed smart small cell system over long term evolution (LTE) systems by performing system-level simulations based on a 3D ray-tracing tool.
Approximating Sampled Sinusoids and Multiband Signals Using Multiband Modulated DPSS Dictionaries
Venue: arXiv cs.IT 2016
Year: 2016

Many signal processing problems--such as analysis, compression, denoising, and reconstruction--can be facilitated by expressing the signal as a linear combination of atoms from a well-chosen dictionary. In this paper, we study possible dictionaries for representing the discrete vector one obtains when collecting a finite set of uniform samples from a multiband analog signal. By analyzing the spectrum of combined time- and multiband-limiting operations in the discrete-time domain, we conclude that the information level of the sampled multiband vectors is essentially equal to the time-frequency area. For representing these vectors, we consider a dictionary formed by concatenating a collection of modulated Discrete Prolate Spheroidal Sequences (DPSS's). We study the angle between the subspaces spanned by this dictionary and an optimal dictionary, and we conclude that the multiband modulated DPSS dictionary--which is simple to construct and more flexible than the optimal dictionary in practical applications--is nearly optimal for representing multiband sample vectors. We also show that the multiband modulated DPSS dictionary not only provides a very high degree of approximation accuracy in an MSE sense for multiband sample vectors (using a number of atoms comparable to the information level), but also that it can provide high-quality approximations of all sampled sinusoids within the bands of interest.
Bluetooth Data Exchange Between Android Phones Without Pairing
Venue: arXiv cs.NI 2016
Year: 2016

In this paper we describe a novel method of exchanging data between Bluetooth smartphones on the Android platform without requiring pairing between devices. We discuss our approach of encoding and decoding data inside the UUIDs used by the Bluetooth Service Discovery Protocol (SDP). Future research remains to be done on the latency, bandwidth and compatibility of this approach, as well as the possibility of utilizing other protocols in conjunction with this method.
Finite nonassociative algebras obtained from skew polynomials and possible applications to $(f,σ,δ)$-codes
Venue: arXiv cs.IT 2016
Year: 2016

Let $S$ be a unital ring, $S[t;σ,δ]$ a skew polynomial ring where $σ$ is an injective endomorphism and $δ$ a left $σ$-derivation, and suppose $f\in S[t;σ,δ]$ has degree $m$ and an invertible leading coefficient. Using right division by $f$ to define the multiplication, we obtain unital nonassociative algebras $S_f$ on the set of skew polynomials in $S[t;σ,δ]$ of degree less than $m$. We study the structure of these algebras. When $S$ is a Galois ring and $f$ base irreducible, these algebras yield families of finite unital nonassociative rings $A$, whose set of (left or right) zero divisors has the form $pA$ for some prime $p$. For reducible $f$, the $S_f$ can be employed both to design linear $(f,σ,δ)$-codes over unital rings and to study their behaviour.
Dynamic Reallocation Problems in Scheduling
Venue: arXiv cs.DS 2016
Year: 2016

In this paper we look at the problem of scheduling tasks on a single-processor system, where each task requires unit time and must be scheduled within a certain time window, and each task can be added to or removed from the system at any time. On each operation, the system is allowed to reschedule any tasks, but the goal is to minimize the number of rescheduled tasks. Our main result is an allocator that maintains a valid schedule for all tasks in the system if their time windows have constant size and reschedules O(1/ε*log(1/ε)) tasks on each insertion as ε->0, where ε is a certain measure of the schedule flexibility of the system. We also show that it is optimal for any allocator that works on arbitrary instances. We also briefly mention a few variants of the problem, such as if the tasks have time windows of difference sizes, for which we have an allocator that we conjecture reschedules only 1 task on each insertion if the schedule flexibility remains above a certain threshold.
COEVOLVE: A Joint Point Process Model for Information Diffusion and Network Co-evolution
Venue: arXiv cs.SI 2016
Year: 2016

Information diffusion in online social networks is affected by the underlying network topology, but it also has the power to change it. Online users are constantly creating new links when exposed to new information sources, and in turn these links are alternating the way information spreads. However, these two highly intertwined stochastic processes, information diffusion and network evolution, have been predominantly studied separately, ignoring their co-evolutionary dynamics. We propose a temporal point process model, COEVOLVE, for such joint dynamics, allowing the intensity of one process to be modulated by that of the other. This model allows us to efficiently simulate interleaved diffusion and network events, and generate traces obeying common diffusion and network patterns observed in real-world networks. Furthermore, we also develop a convex optimization framework to learn the parameters of the model from historical diffusion and network evolution traces. We experimented with both synthetic data and data gathered from Twitter, and show that our model provides a good fit to the data as well as more accurate predictions than alternatives.