OpenRaiser/Intern-Atlas huggingface dataset:
Node Representation Learning for Directed Graphs
Venue: arXiv cs.SI 2019
Year: 2019

We propose a novel approach for learning node representations in directed graphs, which maintains separate views or embedding spaces for the two distinct node roles induced by the directionality of the edges. We argue that the previous approaches either fail to encode the edge directionality or their encodings cannot be generalized across tasks. With our simple \emph{alternating random walk} strategy, we generate role specific vertex neighborhoods and train node embeddings in their corresponding source/target roles while fully exploiting the semantics of directed graphs. We also unearth the limitations of evaluations on directed graphs in previous works and propose a clear strategy for evaluating link prediction and graph reconstruction in directed graphs. We conduct extensive experiments to showcase our effectiveness on several real-world datasets on link prediction, node classification and graph reconstruction tasks. We show that the embeddings from our approach are indeed robust, generalizable and well performing across multiple kinds of tasks and graphs. We show that we consistently outperform all baselines for node classification task. In addition to providing a theoretical interpretation of our method we also show that we are considerably more robust than the other directed graph approaches.
RCanopus: Making Canopus Resilient to Failures and Byzantine Faults
Venue: arXiv cs.DC 2019
Year: 2019

Distributed consensus is a key enabler for many distributed systems including distributed databases and blockchains. Canopus is a scalable distributed consensus protocol that ensures that live nodes in a system agree on an ordered sequence of operations (called transactions). Unlike most prior consensus protocols, Canopus does not rely on a single leader. Instead, it uses a virtual tree overlay for message dissemination to limit network traffic across oversubscribed links. It leverages hardware redundancies, both within a rack and inside the network fabric, to reduce both protocol complexity and communication overhead. These design decisions enable Canopus to support large deployments without significant performance degradation. The existing Canopus protocol is resilient in the face of node and communication failures, but its focus is primarily on performance, so does not respond well to other types of failures. For example, the failure of a single rack of servers causes all live nodes to stall. The protocol is also open to attack by Byzantine nodes, which can cause different live nodes to conclude the protocol with different transaction orders. In this paper, we describe RCanopus (`resilent Canopus') which extends Canopus to add liveness, that is, allowing live nodes to make progress, when possible, despite many types of failures. This requires RCanopus to accurately detect and recover from failure despite using unreliable failure detectors, and tolerance of Byzantine attacks. Second, RCanopus guarantees safety, that is, agreement amongst live nodes of transaction order, in the presence of Byzantine attacks and network partitioning.
Moore-Machine Filtering for Timed and Untimed Pattern Matching
Venue: arXiv cs.FL 2019
Year: 2019

Monitoring is an important body of techniques in runtime verification of real-time, embedded, and cyber-physical systems. Mathematically, the monitoring problem can be formalized as a pattern matching problem against a pattern automaton. Motivated by the needs in embedded applications---especially the limited channel capacity between a sensor unit and a processor that monitors---we pursue the idea of filtering as preprocessing for monitoring. Technically, for a given pattern automaton, we present a construction of a Moore machine that works as a filter. The construction is automata-theoretic, and we find the use of Moore machines particularly suited for embedded applications, not only because their sequential operation is relatively cheap but also because they are amenable to hardware acceleration by dedicated circuits. We prove soundness (i.e., absence of lost matches), too. We work in two settings: in the untimed one, a pattern is an NFA; in the timed one, a pattern is a timed automaton. The extension of our untimed construction to the timed setting is technically involved, but our experiments demonstrate its practical benefits.
Ain't Nobody Got Time For Coding: Structure-Aware Program Synthesis From Natural Language
Venue: arXiv cs.LG 2019
Year: 2019

Program synthesis from natural language (NL) is practical for humans and, once technically feasible, would significantly facilitate software development and revolutionize end-user programming. We present SAPS, an end-to-end neural network capable of mapping relatively complex, multi-sentence NL specifications to snippets of executable code. The proposed architecture relies exclusively on neural components, and is trained on abstract syntax trees, combined with a pretrained word embedding and a bi-directional multi-layer LSTM for processing of word sequences. The decoder features a doubly-recurrent LSTM, for which we propose novel signal propagation schemes and soft attention mechanism. When applied to a large dataset of problems proposed in a previous study, SAPS performs on par with or better than the method proposed there, producing correct programs in over 92% of cases. In contrast to other methods, it does not require post-processing of the resulting programs, and uses a fixed-dimensional latent representation as the only interface between the NL analyzer and the source code generator.
Analyzing Neuroimaging Data Through Recurrent Deep Learning Models
Venue: arXiv cs.LG 2019
Year: 2019

The application of deep learning (DL) models to neuroimaging data poses several challenges, due to the high dimensionality, low sample size and complex temporo-spatial dependency structure of these datasets. Even further, DL models act as as black-box models, impeding insight into the association of cognitive state and brain activity. To approach these challenges, we introduce the DeepLight framework, which utilizes long short-term memory (LSTM) based DL models to analyze whole-brain functional Magnetic Resonance Imaging (fMRI) data. To decode a cognitive state (e.g., seeing the image of a house), DeepLight separates the fMRI volume into a sequence of axial brain slices, which is then sequentially processed by an LSTM. To maintain interpretability, DeepLight adapts the layer-wise relevance propagation (LRP) technique. Thereby, decomposing its decoding decision into the contributions of the single input voxels to this decision. Importantly, the decomposition is performed on the level of single fMRI volumes, enabling DeepLight to study the associations between cognitive state and brain activity on several levels of data granularity, from the level of the group down to the level of single time points. To demonstrate the versatility of DeepLight, we apply it to a large fMRI dataset of the Human Connectome Project. We show that DeepLight outperforms conventional approaches of uni- and multivariate fMRI analysis in decoding the cognitive states and in identifying the physiologically appropriate brain regions associated with these states. We further demonstrate DeepLight's ability to study the fine-grained temporo-spatial variability of brain activity over sequences of single fMRI samples.
Further Towards Unambiguous Edge Bundling: Investigating Power-Confluent Drawings for Network Visualization
Venue: arXiv cs.CG 2019
Year: 2019

Bach et al. [1] recently presented an algorithm for constructing confluent drawings, by leveraging power graph decomposition to generate an auxiliary routing graph. We identify two issues with their method which we call the node split and short-circuit problems, and solve both by modifying the routing graph to retain the hierarchical structure of power groups. We also classify the exact type of confluent drawings that the algorithm can produce as 'power-confluent', and prove that it is a subclass of the previously studied 'strict confluent' drawing. A description and source code of our implementation is also provided, which additionally includes an improved method for power graph construction.
DeepLSR: a deep learning approach for laser speckle reduction
Venue: arXiv cs.CV 2019
Year: 2019

Speckle artifacts degrade image quality in virtually all modalities that utilize coherent energy, including optical coherence tomography, reflectance confocal microscopy, ultrasound, and widefield imaging with laser illumination. We present an adversarial deep learning framework for laser speckle reduction, called DeepLSR (https://durr.jhu.edu/DeepLSR), that transforms images from a source domain of coherent illumination to a target domain of speckle-free, incoherent illumination. We apply this method to widefield images of objects and tissues illuminated with a multi-wavelength laser, using light emitting diode-illuminated images as ground truth. In images of gastrointestinal tissues, DeepLSR reduces laser speckle noise by 6.4 dB, compared to a 2.9 dB reduction from optimized non-local means processing, a 3.0 dB reduction from BM3D, and a 3.7 dB reduction from an optical speckle reducer utilizing an oscillating diffuser. Further, DeepLSR can be combined with optical speckle reduction to reduce speckle noise by 9.4 dB. This dramatic reduction in speckle noise may enable the use of coherent light sources in applications that require small illumination sources and high-quality imaging, including medical endoscopy.
Accurate and efficient explicit approximations of the Colebrook flow friction equation based on the Wright-Omega function
Venue: arXiv cs.NA 2019
Year: 2019

The Colebrook equation is a popular model for estimating friction loss coefficients in water and gas pipes. The model is implicit in the unknown flow friction factor f. To date, the captured flow friction factor f can be extracted from the logarithmic form analytically only in the term of the Lambert W-function. The purpose of this study is to find an accurate and computationally efficient solution based on the shifted Lambert W-function also known as the Wright Omega-function. The Wright Omega-function is more suitable because it overcomes the problem with the overflow error by switching the fast growing term y=W(e^x) of the Lambert W-function to the series expansions that further can be easily evaluated in computers without causing overflow run-time errors. Although the Colebrook equation transformed through the Lambert W-function is identical to the original expression in term of accuracy, a further evaluation of the Lambert W-function can be only approximate. Very accurate explicit approximations of the Colebrook equation that contains only one or two logarithms are shown. The final result is an accurate explicit approximation of the Colebrook equation with the relative error of no more than 0.0096%. The presented approximations are in the form suitable for everyday engineering use, they are both accurate and computationally efficient.
Multi-scale Geometric Summaries for Similarity-based Sensor Fusion
Venue: arXiv cs.CV 2019
Year: 2019

In this work, we address fusion of heterogeneous sensor data using wavelet-based summaries of fused self-similarity information from each sensor. The technique we develop is quite general, does not require domain specific knowledge or physical models, and requires no training. Nonetheless, it can perform surprisingly well at the general task of differentiating classes of time-ordered behavior sequences which are sensed by more than one modality. As a demonstration of our capabilities in the audio to video context, we focus on the differentiation of speech sequences. Data from two or more modalities first are represented using self-similarity matrices(SSMs) corresponding to time-ordered point clouds in feature spaces of each of these data sources; we note that these feature spaces can be of entirely different scale and dimensionality. A fused similarity template is then derived from the modality-specific SSMs using a technique called similarity network fusion (SNF). We investigate pipelines using SNF as both an upstream (feature-level) and a downstream (ranking-level) fusion technique. Multiscale geometric features of this template are then extracted using a recently-developed technique called the scattering transform, and these features are then used to differentiate speech sequences. This method outperforms unsupervised techniques which operate directly on the raw data, and it also outperforms stovepiped methods which operate on SSMs separately derived from the distinct modalities. The benefits of this method become even more apparent as the simulated peak signal to noise ratio decreases.
Memorization in Overparameterized Autoencoders
Venue: arXiv cs.CV 2019
Year: 2019

The ability of deep neural networks to generalize well in the overparameterized regime has become a subject of significant research interest. We show that overparameterized autoencoders exhibit memorization, a form of inductive bias that constrains the functions learned through the optimization process to concentrate around the training examples, although the network could in principle represent a much larger function class. In particular, we prove that single-layer fully-connected autoencoders project data onto the (nonlinear) span of the training examples. In addition, we show that deep fully-connected autoencoders learn a map that is locally contractive at the training examples, and hence iterating the autoencoder results in convergence to the training examples. Finally, we prove that depth is necessary and provide empirical evidence that it is also sufficient for memorization in convolutional autoencoders. Understanding this inductive bias may shed light on the generalization properties of overparametrized deep neural networks that are currently unexplained by classical statistical theory.
Quantifying Learning Guarantees for Convex but Inconsistent Surrogates
Venue: arXiv cs.LG 2019
Year: 2019

We study consistency properties of machine learning methods based on minimizing convex surrogates. We extend the recent framework of Osokin et al. (2017) for the quantitative analysis of consistency properties to the case of inconsistent surrogates. Our key technical contribution consists in a new lower bound on the calibration function for the quadratic surrogate, which is non-trivial (not always zero) for inconsistent cases. The new bound allows to quantify the level of inconsistency of the setting and shows how learning with inconsistent surrogates can have guarantees on sample complexity and optimization difficulty. We apply our theory to two concrete cases: multi-class classification with the tree-structured loss and ranking with the mean average precision loss. The results show the approximation-computation trade-offs caused by inconsistent surrogates and their potential benefits.
Modeling Perceptual Aliasing in SLAM via Discrete-Continuous Graphical Models
Venue: arXiv cs.RO 2019
Year: 2019

Perceptual aliasing is one of the main causes of failure for Simultaneous Localization and Mapping (SLAM) systems operating in the wild. Perceptual aliasing is the phenomenon where different places generate a similar visual (or, in general, perceptual) footprint. This causes spurious measurements to be fed to the SLAM estimator, which typically results in incorrect localization and mapping results. The problem is exacerbated by the fact that those outliers are highly correlated, in the sense that perceptual aliasing creates a large number of mutually-consistent outliers. Another issue stems from the fact that most state-of-the-art techniques rely on a given trajectory guess (e.g., from odometry) to discern between inliers and outliers and this makes the resulting pipeline brittle, since the accumulation of error may result in incorrect choices and recovery from failures is far from trivial. This work provides a unified framework to model perceptual aliasing in SLAM and provides practical algorithms that can cope with outliers without relying on any initial guess. We present two main contributions. The first is a Discrete-Continuous Graphical Model (DC-GM) for SLAM: the continuous portion of the DC-GM captures the standard SLAM problem, while the discrete portion describes the selection of the outliers and models their correlation. The second contribution is a semidefinite relaxation to perform inference in the DC-GM that returns estimates with provable sub-optimality guarantees. Experimental results on standard benchmarking datasets show that the proposed technique compares favorably with state-of-the-art methods while not relying on an initial guess for optimization.
Chain of Antichains: An Efficient and Secure Distributed Ledger Technology and Its Applications
Venue: arXiv cs.DC 2019
Year: 2019

Since the inception of blockchain and Bitcoin (Nakamoto (2008)), a decentralized-distributed ledger system and its associated cryptocurrency, respectively, the world has witnessed a slew of newer adaptations and applications. Although the original distributed ledger technology (DLT) of blockchain is deemed secure and decentralized, the confirmation of transactions is inefficient by design. Recently adopted, directed acyclic graph (DAG)-based distributed ledgers validate transactions efficiently without the physically and environmentally costly building process of blocks (Lerner (2015)). However, centrally-controlled confirmation against the odds of multiple validation disqualifies the DAG as a decentralized-distributed ledger. In this regard, we introduce an innovative DLT by reconstructing a chain of antichains based on a given DAG-pool of transactions. Each antichain (box) contains distinct nodes whose approved transactions are recursively validated by subsequently augmenting nodes. The boxer node closes the box and keeps the hash of all transactions confirmed by the box-genesis node. Designation of boxers and box-geneses is conditionally randomized for decentralization. The boxes are serially concatenated with recursive confirmation (boxchain) without incurring the cost of box generation. Rewards (boxcoin) are paid to the contributing nodes of the ecosystem whose trust is built on the doubly-secure protocol of confirmation. A value-preserving medium of payment (boxdollar) is among numerous practical applications discussed herein.
GOT-10k: A Large High-Diversity Benchmark for Generic Object Tracking in the Wild
Venue: arXiv cs.CV 2019
Year: 2019

We introduce here a large tracking database that offers an unprecedentedly wide coverage of common moving objects in the wild, called GOT-10k. Specifically, GOT-10k is built upon the backbone of WordNet structure and it populates the majority of over 560 classes of moving objects and 87 motion patterns, magnitudes wider than the most recent similar-scale counterparts. The contributions of this paper are summarized in the following: (1) GOT-10k offers over 10,000 video segments with more than 1.5 million manually labeled bounding boxes, enabling unified training and stable evaluation of deep trackers. (2) GOT-10k is by far the first video trajectory dataset that uses the semantic hierarchy of WordNet to guide class population. (3) For the first time, GOT-10k introduces the one-shot protocol for tracker evaluation, where the training and test classes are zero-overlapped. The protocol avoids biased evaluation results towards familiar objects and it promotes generalization in tracker development. (4) We conduct extensive tracking experiments with 39 typical tracking algorithms on GOT-10k and analyze their results in this paper. (5) Finally, we develop a comprehensive platform for the tracking community that offers full-featured evaluation toolkits, an online evaluation server, and a responsive leaderboard. The annotations of GOT-10k's test data are kept private to avoid tuning parameters on it. The database, toolkits, evaluation server and baseline results are available at http://got-10k.aitestunion.com.
Deep Reinforcement Learning based Recommendation with Explicit User-Item Interactions Modeling
Venue: arXiv cs.IR 2019
Year: 2019

Recommendation is crucial in both academia and industry, and various techniques are proposed such as content-based collaborative filtering, matrix factorization, logistic regression, factorization machines, neural networks and multi-armed bandits. However, most of the previous studies suffer from two limitations: (1) considering the recommendation as a static procedure and ignoring the dynamic interactive nature between users and the recommender systems, (2) focusing on the immediate feedback of recommended items and neglecting the long-term rewards. To address the two limitations, in this paper we propose a novel recommendation framework based on deep reinforcement learning, called DRR. The DRR framework treats recommendation as a sequential decision making procedure and adopts an "Actor-Critic" reinforcement learning scheme to model the interactions between the users and recommender systems, which can consider both the dynamic adaptation and long-term rewards. Furthermore, a state representation module is incorporated into DRR, which can explicitly capture the interactions between items and users. Three instantiation structures are developed. Extensive experiments on four real-world datasets are conducted under both the offline and online evaluation settings. The experimental results demonstrate the proposed DRR method indeed outperforms the state-of-the-art competitors.
Logit Pairing Methods Can Fool Gradient-Based Attacks
Venue: arXiv cs.LG 2019
Year: 2019

Recently, Kannan et al. [2018] proposed several logit regularization methods to improve the adversarial robustness of classifiers. We show that the computationally fast methods they propose - Clean Logit Pairing (CLP) and Logit Squeezing (LSQ) - just make the gradient-based optimization problem of crafting adversarial examples harder without providing actual robustness. We find that Adversarial Logit Pairing (ALP) may indeed provide robustness against adversarial examples, especially when combined with adversarial training, and we examine it in a variety of settings. However, the increase in adversarial accuracy is much smaller than previously claimed. Finally, our results suggest that the evaluation against an iterative PGD attack relies heavily on the parameters used and may result in false conclusions regarding robustness of a model.