OpenRaiser/Intern-Atlas huggingface dataset:
A Geometric Approach for Real-time Monitoring of Dynamic Large Scale Graphs: AS-level graphs illustrated
Venue: arXiv cs.NI 2018
Year: 2018

The monitoring of large dynamic networks is a major chal- lenge for a wide range of application. The complexity stems from properties of the underlying graphs, in which slight local changes can lead to sizable variations of global prop- erties, e.g., under certain conditions, a single link cut that may be overlooked during monitoring can result in splitting the graph into two disconnected components. Moreover, it is often difficult to determine whether a change will propagate globally or remain local. Traditional graph theory measure such as the centrality or the assortativity of the graph are not satisfying to characterize global properties of the graph. In this paper, we tackle the problem of real-time monitoring of dynamic large scale graphs by developing a geometric approach that leverages notions of geometric curvature and recent development in graph embeddings using Ollivier-Ricci curvature [47]. We illustrate the use of our method by consid- ering the practical case of monitoring dynamic variations of global Internet using topology changes information provided by combining several BGP feeds. In particular, we use our method to detect major events and changes via the geometry of the embedding of the graph.
On Multi-Layer Basis Pursuit, Efficient Algorithms and Convolutional Neural Networks
Venue: arXiv cs.LG 2018
Year: 2018

Parsimonious representations are ubiquitous in modeling and processing information. Motivated by the recent Multi-Layer Convolutional Sparse Coding (ML-CSC) model, we herein generalize the traditional Basis Pursuit problem to a multi-layer setting, introducing similar sparse enforcing penalties at different representation layers in a symbiotic relation between synthesis and analysis sparse priors. We explore different iterative methods to solve this new problem in practice, and we propose a new Multi-Layer Iterative Soft Thresholding Algorithm (ML-ISTA), as well as a fast version (ML-FISTA). We show that these nested first order algorithms converge, in the sense that the function value of near-fixed points can get arbitrarily close to the solution of the original problem. We further show how these algorithms effectively implement particular recurrent convolutional neural networks (CNNs) that generalize feed-forward ones without introducing any parameters. We present and analyze different architectures resulting unfolding the iterations of the proposed pursuit algorithms, including a new Learned ML-ISTA, providing a principled way to construct deep recurrent CNNs. Unlike other similar constructions, these architectures unfold a global pursuit holistically for the entire network. We demonstrate the emerging constructions in a supervised learning setting, consistently improving the performance of classical CNNs while maintaining the number of parameters constant.
Contextualize, Show and Tell: A Neural Visual Storyteller
Venue: arXiv cs.CL 2018
Year: 2018

We present a neural model for generating short stories from image sequences, which extends the image description model by Vinyals et al. (Vinyals et al., 2015). This extension relies on an encoder LSTM to compute a context vector of each story from the image sequence. This context vector is used as the first state of multiple independent decoder LSTMs, each of which generates the portion of the story corresponding to each image in the sequence by taking the image embedding as the first input. Our model showed competitive results with the METEOR metric and human ratings in the internal track of the Visual Storytelling Challenge 2018.
An Efficient Graph Accelerator with Parallel Data Conflict Management
Venue: arXiv cs.DC 2018
Year: 2018

Graph-specific computing with the support of dedicated accelerator has greatly boosted the graph processing in both efficiency and energy. Nevertheless, their data conflict management is still sequential in essential when some vertex needs a large number of conflicting updates at the same time, leading to prohibitive performance degradation. This is particularly true for processing natural graphs. In this paper, we have the insight that the atomic operations for the vertex updating of many graph algorithms (e.g., BFS, PageRank and WCC) are typically incremental and simplex. This hence allows us to parallelize the conflicting vertex updates in an accumulative manner. We architect a novel graphspecific accelerator that can simultaneously process atomic vertex updates for massive parallelism on the conflicting data access while ensuring the correctness. A parallel accumulator is designed to remove the serialization in atomic protection for conflicting vertex updates through merging their results in parallel. Our implementation on Xilinx Virtex UltraScale+ XCVU9P with a wide variety of typical graph algorithms shows that our accelerator achieves an average throughput by 2.36 GTEPS as well as up to 3.14x performance speedup in comparison with state-of-the-art ForeGraph (with single-chip version).
Mix and Match: Collaborative Expert-Crowd Judging for Building Test Collections Accurately and Affordably
Venue: arXiv cs.IR 2018
Year: 2018

Crowdsourcing offers an affordable and scalable means to collect relevance judgments for IR test collections. However, crowd assessors may show higher variance in judgment quality than trusted assessors. In this paper, we investigate how to effectively utilize both groups of assessors in partnership. We specifically investigate how agreement in judging is correlated with three factors: relevance category, document rankings, and topical variance. Based on this, we then propose two collaborative judging methods in which a portion of the document-topic pairs are assessed by in-house judges while the rest are assessed by crowd-workers. Experiments conducted on two TREC collections show encouraging results when we distribute work intelligently between our two groups of assessors.
Scaling Up Large-Scale Graph Processing for GPU-Accelerated Heterogeneous Systems
Venue: arXiv cs.DC 2018
Year: 2018

Not only with the large host memory for supporting large scale graph processing, GPU-accelerated heterogeneous architecture can also provide a great potential for high-performance computing. However, few existing heterogeneous systems can exploit both hardware advantages to enable the scale-up performance for graph processing due to the limited CPU-GPU transmission efficiency. In this paper, we investigate the transmission inefficiency problem of heterogeneous graph systems. Our key insight is that the transmission efficiency for heterogeneous graph processing can be greatly improved by simply iterating each subgraph multiple times (rather than only once in prior work) in the GPU, further enabling to obtain the improvable efficiency of heterogeneous graph systems by enhancing GPU processing capability. We therefore present Seraph, with the highlights of {\em pipelined} subgraph iterations and {\em predictive} vertex updating, to cooperatively maximize the effective computations of GPU on graph processing. Our evaluation on a wide variety of large graph datasets shows that Seraph outperforms state-of-the-art heterogeneous graph systems by 5.42x (vs. Graphie) and 3.05x (vs. Garaph). Further, Seraph can be significantly scaled up over Graphie as fed with more computing power for large-scale graph processing.
Low Cost Edge Sensing for High Quality Demosaicking
Venue: arXiv cs.CV 2018
Year: 2018

Digital cameras that use Color Filter Arrays (CFA) entail a demosaicking procedure to form full RGB images. As today's camera users generally require images to be viewed instantly, demosaicking algorithms for real applications must be fast. Moreover, the associated cost should be lower than the cost saved by using CFA. For this purpose, we revisit the classical Hamilton-Adams (HA) algorithm, which outperforms many sophisticated techniques in both speed and accuracy. Inspired by HA's strength and weakness, we design a very low cost edge sensing scheme. Briefly, it guides demosaicking by a logistic functional of the difference between directional variations. We extensively compare our algorithm with 28 demosaicking algorithms by running their open source codes on benchmark datasets. Compared to methods of similar computational cost, our method achieves substantially higher accuracy, Whereas compared to methods of similar accuracy, our method has significantly lower cost. Moreover, on test images of currently popular resolution, the quality of our algorithm is comparable to top performers, whereas its speed is tens of times faster.
Supporting Superpages and Lightweight Page Migration in Hybrid Memory Systems
Venue: arXiv cs.AR 2018
Year: 2018

Superpages have long been used to mitigate address translation overhead in big memory systems. However, superpages often preclude lightweight page migration, which is crucial for performance and energy efficiency in hybrid memory systems composed of DRAM and non-volatile memory (NVM). In this paper, we propose a novel memory management mechanism called \textit{Rainbow} to bridge this fundamental conflict between superpages and lightweight page migration. \textit{Rainbow} manages NVM at the superpage granularity, and uses DRAM to cache frequently-accessed (hot) small pages in each superpage. Correspondingly, \textit{Rainbow} utilizes split TLBs to support different page sizes. By introducing an efficient hot page identification mechanism and a novel NVM-to-DRAM address remapping mechanism, \textit{Rainbow} supports lightweight page migration while without splintering superpages. Experimental results show that Rainbow can significantly reduce applications' TLB misses by 99.8\%, and improve application performance (IPC) by up to 2.9X (43.0\% on average) when compared to a state-of-the-art memory migration policy without superpage support.
Multi-Cast Attention Networks for Retrieval-based Question Answering and Response Prediction
Venue: arXiv cs.CL 2018
Year: 2018

Attention is typically used to select informative sub-phrases that are used for prediction. This paper investigates the novel use of attention as a form of feature augmentation, i.e, casted attention. We propose Multi-Cast Attention Networks (MCAN), a new attention mechanism and general model architecture for a potpourri of ranking tasks in the conversational modeling and question answering domains. Our approach performs a series of soft attention operations, each time casting a scalar feature upon the inner word embeddings. The key idea is to provide a real-valued hint (feature) to a subsequent encoder layer and is targeted at improving the representation learning process. There are several advantages to this design, e.g., it allows an arbitrary number of attention mechanisms to be casted, allowing for multiple attention types (e.g., co-attention, intra-attention) and attention variants (e.g., alignment-pooling, max-pooling, mean-pooling) to be executed simultaneously. This not only eliminates the costly need to tune the nature of the co-attention layer, but also provides greater extents of explainability to practitioners. Via extensive experiments on four well-known benchmark datasets, we show that MCAN achieves state-of-the-art performance. On the Ubuntu Dialogue Corpus, MCAN outperforms existing state-of-the-art models by $9\%$. MCAN also achieves the best performing score to date on the well-studied TrecQA dataset.
Design and evaluation of a genomics variant analysis pipeline using GATK Spark tools
Venue: arXiv cs.DC 2018
Year: 2018

Scalable and efficient processing of genome sequence data, i.e. for variant discovery, is key to the mainstream adoption of High Throughput technology for disease prevention and for clinical use. Achieving scalability, however, requires a significant effort to enable the parallel execution of the analysis tools that make up the pipelines. This is facilitated by the new Spark versions of the well-known GATK toolkit, which offer a black-box approach by transparently exploiting the underlying Map Reduce architecture. In this paper we report on our experience implementing a standard variant discovery pipeline using GATK 4.0 with Docker-based deployment over a cluster. We provide a preliminary performance analysis, comparing the processing times and cost to those of the new Microsoft Genomics Services.
AID++: An Updated Version of AID on Scene Classification
Venue: arXiv cs.CV 2018
Year: 2018

Aerial image scene classification is a fundamental problem for understanding high-resolution remote sensing images and has become an active research task in the field of remote sensing due to its important role in a wide range of applications. However, the limitations of existing datasets for scene classification, such as the small scale and low-diversity, severely hamper the potential usage of the new generation deep convolutional neural networks (CNNs). Although huge efforts have been made in building large-scale datasets very recently, e.g., the Aerial Image Dataset (AID) which contains 10,000 image samples, they are still far from sufficient to fully train a high-capacity deep CNN model. To this end, we present a larger-scale dataset in this paper, named as AID++, for aerial scene classification based on the AID dataset. The proposed AID++ consists of more than 400,000 image samples that are semi-automatically annotated by using the existing the geographical data. We evaluate several prevalent CNN models on the proposed dataset, and the results show that our dataset can be used as a promising benchmark for scene classification.
k-Space Deep Learning for Parallel MRI: Application to Time-Resolved MR Angiography
Venue: arXiv cs.CV 2018
Year: 2018

Time-resolved angiography with interleaved stochastic trajectories (TWIST) has been widely used for dynamic contrast enhanced MRI (DCE-MRI). To achieve highly accelerated acquisitions, TWIST combines the periphery of the k-space data from several adjacent frames to reconstruct one temporal frame. However, this view-sharing scheme limits the true temporal resolution of TWIST. Moreover, the k-space sampling patterns have been specially designed for a specific generalized autocalibrating partial parallel acquisition (GRAPPA) factor so that it is not possible to reduce the number of view-sharing once the k-data is acquired. To address these issues, this paper proposes a novel k-space deep learning approach for parallel MRI. In particular, we have designed our neural network so that accurate k-space interpolations are performed simultaneously for multiple coils by exploiting the redundancies along the coils and images. Reconstruction results using in vivo TWIST data set confirm that the proposed method can immediately generate high-quality reconstruction results with various choices of view- sharing, allowing us to exploit the trade-off between spatial and temporal resolution in time-resolved MR angiography.
Low-Overhead Hierarchically-Sparse Channel Estimation for Multiuser Wideband Massive MIMO
Venue: arXiv cs.IT 2018
Year: 2018

The problem of excessive pilot overhead required for uplink massive MIMO channel estimation is well known, let alone when it is considered along with wideband (OFDM) transmissions. Towards channel estimators that are both efficient and require low-training overhead, compressive sensing (CS) approaches have been increasingly popular, exploiting the sparse nature of the physical channel. However, no analytical insights regarding the overhead required for reliable channel estimation in wideband massive MIMO are available. By observing that the wideband massive MIMO channel can be represented by a vector that is not simply sparse but has well defined structural properties, referred to as hierarchical sparsity, we propose low complexity channel estimators for the multiuser scenario that take this property into account. By employing the framework of the hierarchical restricted isometry property, rigorous performance guarantees for these algorithms are provided suggesting concrete design goals for the user pilot sequences. For a specific design, we analytically characterize the scaling of the required pilot overhead with increasing number of antennas and bandwidth, revealing that, as long as the number of antennas is sufficiently large, it is independent of the per user channel sparsity level as well as the number of active users. Hence, surprisingly, in contrast to the classical setting, pilot overhead can be shifted into spatial dimensions not affecting crucial bandwidth constraints thereby increasing the overall system capacity. These analytical insights are verified by simulation results demonstrating also the superiority of the proposed algorithm over conventional CS algorithms that ignore the hierarchical sparsity property.
BPjs --- a framework for modeling reactive systems using a scripting language and BP
Venue: arXiv cs.SE 2018
Year: 2018

We describe some progress towards a new common framework for model driven engineering, based on behavioral programming. The tool we have developed unifies almost all of the work done in behavioral programming so far, under a common set of interfaces. Its architecture supports pluggable event selection strategies, which can make models more intuitive and compact. Program state space can be traversed using various algorithms, such as DFS and A*. Furthermore, program state is represented in a way that enables scanning a state space using parallel and distributed algorithms. Executable models created with this tool can be directly embedded in Java applications, enabling a model-first approach to system engineering, where initially a model is created and verified, and then a working application is gradually built around the model. The model itself consists of a collection of small scripts written in JavaScript (hence "BPjs"). Using a variety of case-studies, this paper shows how the combination of a lenient programming language with formal model analysis tools creates an efficient way of developing robust complex systems. Additionally, as we learned from an experimental course we ran, the usage of JavaScript make practitioners more amenable to using this system and, thus, model checking and model driven engineering. In addition to providing infrastructure for development and case-studies in behavioral programming, the tool is designed to serve as a common platform for research and innovation in behavioral programming and in model driven engineering in general.
A Comprehensive Comparison between Neural Style Transfer and Universal Style Transfer
Venue: arXiv cs.CV 2018
Year: 2018

Style transfer aims to transfer arbitrary visual styles to content images. We explore algorithms adapted from two papers that try to solve the problem of style transfer while generalizing on unseen styles or compromised visual quality. Majority of the improvements made focus on optimizing the algorithm for real-time style transfer while adapting to new styles with considerably less resources and constraints. We compare these strategies and compare how they measure up to produce visually appealing images. We explore two approaches to style transfer: neural style transfer with improvements and universal style transfer. We also make a comparison between the different images produced and how they can be qualitatively measured.
Faster Dual-Key Stealth Address for Blockchain-Based Internet of Things Systems
Venue: arXiv cs.CR 2018
Year: 2018

Stealth address prevents public association of a blockchain transaction's output with a recipient's wallet address and hides the actual destination address of a transaction. While stealth address provides an effective privacy-enhancing technology for a cryptocurrency network, it requires blockchain nodes to actively monitor all the transactions and compute the purported destination addresses, which restricts its application for resource-constrained environments like Internet of Things (IoT). In this paper, we propose DKSAP-IoT, a faster dual-key stealth address protocol for blockchain-based IoT systems. DKSAP-IoT utilizes a technique similar to the TLS session resumption to improve the performance and reduce the transaction size at the same time between two communication peers. Our theoretical analysis as well as the extensive experiments on an embedded computing platform demonstrate that DKSAP-IoT is able to reduce the computational overhead by at least 50% when compared to the state-of-the-art scheme, thereby paving the way for its application to blockchain-based IoT systems.
Similarity encoding for learning with dirty categorical variables
Venue: arXiv cs.LG 2018
Year: 2018

For statistical learning, categorical variables in a table are usually considered as discrete entities and encoded separately to feature vectors, e.g., with one-hot encoding. "Dirty" non-curated data gives rise to categorical variables with a very high cardinality but redundancy: several categories reflect the same entity. In databases, this issue is typically solved with a deduplication step. We show that a simple approach that exposes the redundancy to the learning algorithm brings significant gains. We study a generalization of one-hot encoding, similarity encoding, that builds feature vectors from similarities across categories. We perform a thorough empirical validation on non-curated tables, a problem seldom studied in machine learning. Results on seven real-world datasets show that similarity encoding brings significant gains in prediction in comparison with known encoding methods for categories or strings, notably one-hot encoding and bag of character n-grams. We draw practical recommendations for encoding dirty categories: 3-gram similarity appears to be a good choice to capture morphological resemblance. For very high-cardinality, dimensionality reduction significantly reduces the computational cost with little loss in performance: random projections or choosing a subset of prototype categories still outperforms classic encoding approaches.
Distributed Learning from Interactions in Social Networks
Venue: arXiv cs.SY 2018
Year: 2018

We consider a network scenario in which agents can evaluate each other according to a score graph that models some interactions. The goal is to design a distributed protocol, run by the agents, that allows them to learn their unknown state among a finite set of possible values. We propose a Bayesian framework in which scores and states are associated to probabilistic events with unknown parameters and hyperparameters, respectively. We show that each agent can learn its state by means of a local Bayesian classifier and a (centralized) Maximum-Likelihood (ML) estimator of parameter-hyperparameter that combines plain ML and Empirical Bayes approaches. By using tools from graphical models, which allow us to gain insight on conditional dependencies of scores and states, we provide a relaxed probabilistic model that ultimately leads to a parameter-hyperparameter estimator amenable to distributed computation. To highlight the appropriateness of the proposed relaxation, we demonstrate the distributed estimators on a social interaction set-up for user profiling.
Path Throughput Importance Weights
Venue: arXiv cs.GR 2018
Year: 2018

Many Monte Carlo light transport simulations use multiple importance sampling (MIS) to weight between different path sampling strategies. We propose to use the path throughput to compute the MIS weights instead of the commonly used probability density per area measure. This new formulation is equivalent to the previous approach and results in the same weights as well as implementation. However, it is more intuitive and can help in understanding the effects of modifications to the weight function. We show some examples of required modifications which are often neglected in implementations. Also, our new perspective might help to derive MIS strategies for new samplers in the future.