Network Vector: Distributed Representations of Networks with Global Context

We propose a neural embedding algorithm called Network Vector, which learns distributed representations of nodes and the entire networks simultaneously. By embedding networks in a low-dimensional space, the algorithm allows us to compare networks in terms of structural similarity and to solve outstanding predictive problems. Unlike alternative approaches that focus on node level features, we learn a continuous global vector that captures each node’s global context by maximizing the predictive likelihood of random walk paths in the network. Our algorithm is scalable to real world graphs with many nodes. We evaluate our algorithm on datasets from diverse domains, and compare it with state-of-the-art techniques in node classification, role discovery and concept analogy tasks. The empirical results show the effectiveness and the efficiency of our algorithm.

Inferring Generative Model Structure with Static Analysis

Obtaining enough labeled data to robustly train complex discriminative models is a major bottleneck in the machine learning pipeline. A popular solution is combining multiple sources of weak supervision using generative models. The structure of these models affects training label quality, but is difficult to learn without any ground truth labels. We instead rely on these weak supervision sources having some structure by virtue of being encoded programmatically. We present Coral, a paradigm that infers generative model structure by statically analyzing the code for these heuristics, thus reducing the data required to learn structure significantly. We prove that Coral’s sample complexity scales quasilinearly with the number of heuristics and number of relations found, improving over the standard sample complexity, which is exponential in n for identifying n^{\textrm{th}} degree relations. Experimentally, Coral matches or outperforms traditional structure learning approaches by up to 3.81 F1 points. Using Coral to model dependencies instead of assuming independence results in better performance than a fully supervised model by 3.07 accuracy points when heuristics are used to label radiology data without ground truth labels.

BlockSci: Design and applications of a blockchain analysis platform

Analysis of blockchain data is useful for both scientific research and commercial applications. We present BlockSci, an open-source software platform for blockchain analysis. BlockSci is versatile in its support for different blockchains and analysis tasks. It incorporates an in-memory, analytical (rather than transactional) database, making it several hundred times faster than existing tools. We describe BlockSci’s design and present four analyses that illustrate its capabilities. This is a working paper that accompanies the first public release of BlockSci, available at https://…/BlockSci. We seek input from the community to further develop the software and explore other potential applications.

DeepFeat: A Bottom Up and Top Down Saliency Model Based on Deep Features of Convolutional Neural Nets

A deep feature based saliency model (DeepFeat) is developed to leverage the understanding of the prediction of human fixations. Traditional saliency models often predict the human visual attention relying on few level image cues. Although such models predict fixations on a variety of image complexities, their approaches are limited to the incorporated features. In this study, we aim to provide an intuitive interpretation of convolu- tional neural network deep features by combining low and high level visual factors. We exploit four evaluation metrics to evaluate the correspondence between the proposed framework and the ground-truth fixations. The key findings of the results demon- strate that the DeepFeat algorithm, incorporation of bottom up and top down saliency maps, outperforms the individual bottom up and top down approach. Moreover, in comparison to nine 9 state-of-the-art saliency models, our proposed DeepFeat model achieves satisfactory performance based on all four evaluation metrics.

Deep Subspace Clustering Networks

We present a novel deep neural network architecture for unsupervised subspace clustering. This architecture is built upon deep auto-encoders, which non-linearly map the input data into a latent space. Our key idea is to introduce a novel self-expressive layer between the encoder and the decoder to mimic the ‘self-expressiveness’ property that has proven effective in traditional subspace clustering. Being differentiable, our new self-expressive layer provides a simple but effective way to learn pairwise affinities between all data points through a standard back-propagation procedure. Being nonlinear, our neural-network based method is able to cluster data points having complex (often nonlinear) structures. We further propose pre-training and fine-tuning strategies that let us effectively learn the parameters of our subspace clustering networks. Our experiments show that the proposed method significantly outperforms the state-of-the-art unsupervised subspace clustering methods.

Sorting with GPUs: A Survey

Sorting is a fundamental operation in computer science and is a bottleneck in many important fields. Sorting is critical to database applications, online search and indexing,biomedical computing, and many other applications. The explosive growth in computational power and availability of GPU coprocessors has allowed sort operations on GPUs to be done much faster than any equivalently priced CPU. Current trends in GPU computing shows that this explosive growth in GPU capabilities is likely to continue for some time. As such, there is a need to develop algorithms to effectively harness the power of GPUs for crucial applications such as sorting.

Adaptive Processing of Spatial-Keyword Data Over a Distributed Streaming Cluster

The widespread use of GPS-enabled smartphones along with the popularity of micro-blogging and social networking applications, e.g., Twitter and Facebook, has resulted in the generation of huge streams of geo-tagged textual data. Many applications require real-time processing of these streams. For example, location-based e-coupon and ad-targeting systems enable advertisers to register millions of ads to millions of users. The number of users is typically very high and they are continuously moving, and the ads change frequently as well. Hence sending the right ad to the matching users is very challenging. Existing streaming systems are either centralized or are not spatial-keyword aware, and cannot efficiently support the processing of rapidly arriving spatial-keyword data streams. This paper presents Tornado, a distributed spatial-keyword stream processing system. Tornado features routing units to fairly distribute the workload, and furthermore, co-locate the data objects and the corresponding queries at the same processing units. The routing units use the Augmented-Grid, a novel structure that is equipped with an efficient search algorithm for distributing the data objects and queries. Tornado uses evaluators to process the data objects against the queries. The routing units minimize the redundant communication by not sending data updates for processing when these updates do not match any query. By applying dynamically evaluated cost formulae that continuously represent the processing overhead at each evaluator, Tornado is adaptive to changes in the workload. Extensive experimental evaluation using spatio-textual range queries over real Twitter data indicates that Tornado outperforms the non-spatio-textually aware approaches by up to two orders of magnitude in terms of the overall system throughput.

Covariances, Robustness, and Variational Bayes

Variational Bayes (VB) is an approximate Bayesian posterior inference technique that is increasingly popular due to its fast runtimes on large-scale datasets. However, even when VB provides accurate posterior means for certain parameters, it often mis-estimates variances and covariances. Furthermore, prior robustness measures have remained undeveloped for VB. By deriving a simple formula for the effect of infinitesimal model perturbations on VB posterior means, we provide both improved covariance estimates and local robustness measures for VB, thus greatly expanding the practical usefulness of VB posterior approximations. The estimates for VB posterior covariances rely on a result from the classical Bayesian robustness literature relating derivatives of posterior expectations to posterior covariances. Our key assumption is that the VB approximation provides good estimates of a select subset of posterior means — an assumption that has been shown to hold in many practical settings. In our experiments, we demonstrate that our methods are simple, general, and fast, providing accurate posterior uncertainty estimates and robustness measures with runtimes that can be an order of magnitude smaller than MCMC.

The Expressive Power of Neural Networks: A View from the Width

The expressive power of neural networks is important for understanding deep learning. Most existing works consider this problem from the view of the depth of a network. In this paper, we study how width affects the expressiveness of neural networks. Classical results state that \emph{depth-bounded} (e.g. depth-2) networks with suitable activation functions are universal approximators. We show a universal approximation theorem for \emph{width-bounded} ReLU networks: width-(n+4) ReLU networks, where n is the input dimension, are universal approximators. Moreover, except for a measure zero set, all functions cannot be approximated by width-n ReLU networks, which exhibits a phase transition. Several recent works demonstrate the benefits of depth by proving the depth-efficiency of neural networks. That is, there are classes of deep networks which cannot be realized by any shallow network whose size is no more than an \emph{exponential} bound. Here we pose the dual question on the width-efficiency of ReLU networks: Are there wide networks that cannot be realized by narrow networks whose size is not substantially larger? We show that there exist classes of wide networks which cannot be realized by any narrow network whose depth is no more than a \emph{polynomial} bound. On the other hand, we demonstrate by extensive experiments that narrow networks whose size exceed the polynomial bound by a constant factor can approximate wide and shallow network with high accuracy. Our results provide more comprehensive evidence that depth is more effective than width for the expressiveness of ReLU networks.

Causality-Aided Falsification

Falsification is drawing attention in quality assurance of heterogeneous systems whose complexities are beyond most verification techniques’ scalability. In this paper we introduce the idea of causality aid in falsification: by providing a falsification solver — that relies on stochastic optimization of a certain cost function — with suitable causal information expressed by a Bayesian network, search for a falsifying input value can be efficient. Our experiment results show the idea’s viability.

Dimension Reduction and Smoothing in Quasi-Monte Carlo Method for Financial Engineering

Quasi-Monte Carlo (QMC) method is playing an increasing role in the problems of pricing and hedging of complex financial derivatives. These problems are usually of high dimensionality and discontinuities. The two factors may significantly deteriorate the performance of the QMC method. This paper develops a method that overcomes the challenges of the high dimensionality and discontinuities concurrently. For this purpose, a smoothing method is proposed to remove the discontinuities for some typical functions arising from financial engineering. To make the smoothing method applicable for more general functions, a new path generation method is designed for simulating the paths of the underlying assets such that the resulting function has the required form. The new path generation method has an additional power to reduce the effective dimension of the target function. Our proposed method caters for a large variety of model specifications, including the Black-Scholes, exponential normal inverse Gaussian L\’evy, and Heston models. Numerical experiments dealing with these models show that in the QMC setting the proposed smoothing method in combination with the new path generation method can lead to a dramatic variance reduction for pricing exotic options with discontinuous payoffs and for calculating options’ Greeks. The investigation on the effective dimension and the related characteristics explains the significant enhancement of the combined procedure.

Object-Oriented Knowledge Extraction using Universal Exploiters

This paper contains analysis and extension of exploiters-based knowledge extraction methods, which allow generation of new knowledge, based on the basic ones. The main achievement of the paper is useful features of some universal exploiters proof, which allow extending set of basic classes and set of basic relations by finite set of new classes of objects and relations among them, which allow creating of complete lattice. Proposed approach gives an opportunity to compute quantity of new classes, which can be generated using it, and quantity of different types, which each of obtained classes describes; constructing of defined hierarchy of classes with determined subsumption relation; avoidance of some problems of inheritance and more efficient restoring of basic knowledge within the database.

Entropic Determinants

The ability of many powerful machine learning algorithms to deal with large data sets without compromise is often hampered by computationally expensive linear algebra tasks, of which calculating the log determinant is a canonical example. In this paper we demonstrate the optimality of Maximum Entropy methods in approximating such calculations. We prove the equivalence between mean value constraints and sample expectations in the big data limit, that Covariance matrix eigenvalue distributions can be completely defined by moment information and that the reduction of the self entropy of a maximum entropy proposal distribution, achieved by adding more moments reduces the KL divergence between the proposal and true eigenvalue distribution. We empirically verify our results on a variety of SparseSuite matrices and establish best practices.

On-Disk Data Processing: Issues and Future Directions

In this paper, we present a survey of ‘on-disk’ data processing (ODDP). ODDP, which is a form of near-data processing, refers to the computing arrangement where the secondary storage drives have the data processing capability. Proposed ODDP schemes vary widely in terms of the data processing capability, target applications, architecture and the kind of storage drive employed. Some ODDP schemes provide only a specific but heavily used operation like sort whereas some provide a full range of operations. Recently, with the advent of Solid State Drives, powerful and extensive ODDP solutions have been proposed. In this paper, we present a thorough review of architectures developed for different on-disk processing approaches along with current and future challenges and also identify the future directions which ODDP can take.

Cycles in adversarial regularized learning

Regularized learning is a fundamental technique in online optimization, machine learning and many other fields of computer science. A natural question that arises in these settings is how regularized learning algorithms behave when faced against each other. We study a natural formulation of this problem by coupling regularized learning dynamics in zero-sum games. We show that the system’s behavior is Poincar\’e recurrent, implying that almost every trajectory revisits any (arbitrarily small) neighborhood of its starting point infinitely often. This cycling behavior is robust to the agents’ choice of regularization mechanism (each agent could be using a different regularizer), to positive-affine transformations of the agents’ utilities, and it also persists in the case of networked competition, i.e., for zero-sum polymatrix games.

Power Network Regulation Benchmark for Switched-Mode Optimal Control
EMD-regression for modelling multi-scale relationships, and application to weather-related cardiovascular mortality
Projection-Based Iterative Mode Scheduling for Switched Systems
A sharp bound for winning within a proportion of the maximum of a sequence
How Does Knowledge of the AUC Constrain the Set of Possible Ground-truth Labelings?
Bad semidefinite programs with short proofs, and the closedness of the linear image of the semidefinite cone
A Stochastic Approach to Shortcut Bridging in Programmable Matter
Status Updates Through Multicast Networks
A note about words which coincide except in one position
Deep Learning the Physics of Transport Phenomena
An Analysis of ISO 26262: Using Machine Learning Safely in Automotive Software
Millimeter Wave Multi-Beam-Switching Antenna
The Muffin Problem
Attack-Aware Multi-Sensor Integration Algorithm for Autonomous Vehicle Navigation Systems
Reservoir of Diverse Adaptive Learners and Stacking Fast Hoeffding Drift Detection Methods for Evolving Data Streams
End-to-end Face Detection and Cast Grouping in Movies Using Erdős-Rényi Clustering
Distance to the Nearest Stable Metzler Matrix
Local Neighborhood Intensity Pattern: A new texture feature descriptor for image retrieval
Hadamard Full Propelinear Codes of type Q. Rank and Kernel
On the classification of automorphisms of trees
Statistical Physics and Representations in Real and Artificial Neural Networks
Characterization of Extreme Copulas
Maximum independent sets near the upper bound
Fine-grained Recognition in the Wild: A Multi-Task Domain Adaptation Approach
Fine-Grained Car Detection for Visual Census Estimation
Scalable Annotation of Fine-Grained Categories Without Experts
A General Regularized Continuous Formulation for the Maximum Clique Problem
Exploiting Problem Structure in Optimization under Uncertainty via Online Convex Optimization
Optimal-Dimensionality Sampling on the Sphere: Improvements and Variations
Model Updating Using Sum of Squares (SOS) Optimization to Minimize Modal Dynamic Residuals
Super-speeds with Zero-RAM: Next Generation Large-Scale Optimization in Your Laptop!
Iterative Residual Fitting for Spherical Harmonic Transform of Band-Limited Signals on the Sphere: Generalization and Analysis
A Simple Two-stage Equalizer With Simplified Orthogonal Time Frequency Space Modulation Over Rapidly Time-varying Channels
Intelligent Subset Selection of Power Generators for Economic Dispatch
Extreme Sparse Multinomial Logistic Regression: A Fast and Robust Framework for Hyperspectral Image Classification
The quasi-Assouad dimension for stochastically self-similar sets
Spatial Modulation for More Spatial Multiplexing: RF-Chain-Limited Generalized Spatial Modulation Aided MmWave MIMO with Hybrid Precoding
FAST: Frequency-Aware Spatio-Textual Indexing for In-Memory Continuous Filter Query Processing
Generalizing Distance Covariance to Measure and Test Multivariate Mutual Dependence
Mirror Descent Search and Acceleration
CuRTAIL: ChaRacterizing and Thwarting AdversarIal deep Learning
A Novel Low-Complexity Framework in Ultra-Wideband Imaging for Breast Cancer Detection
Learning to Segment Breast Biopsy Whole Slide Images
Game Theory Models for the Verification of the Collective Behaviour of Autonomous Cars
A Rational Agent Controlling an Autonomous Vehicle: Implementation and Formal Verification
Coalescent results for diploid exchangeable population models
On Democratic Fairness for Groups of Agents
Segmentation and Classification of Cine-MR Images Using Fully Convolutional Networks and Handcrafted Features
The third symmetric potency of the circle and the Barnette sphere
Deep learning for undersampled MRI reconstruction
A Combinatorial Grassmannian Representation of the Magic Three-Qubit Veldkamp Line
Balanced Line Separators of Unit Disk Graphs
EMM: Energy-Aware Mobility Management for Mobile Edge Computing in Ultra Dense Networks
New congruences for broken $k$-diamond partitions
Variations on Baur–Marsh’s determinant
Scheduling with Explorable Uncertainty
On quasi-stationary Mean Field Games models
Identifying Product Order with Restricted Boltzmann Machines
Fast Algorithm for Enumerating Diagonal Latin Squares of Small Order
Objectness Scoring and Detection Proposals in Forward-Looking Sonar Images with Convolutional Neural Networks
Best Practices in Convolutional Networks for Forward-Looking Sonar Image Recognition
Consensus under Misaligned Orientations
Gaussian Quadrature for Kernel Features
Efficient Logging in Non-Volatile Memory by Exploiting Coherency Protocols
Likelihood informed dimension reduction for inverse problems in remote sensing of atmospheric constituent profiles
A Curious Family of Binomial Determinants That Count Rhombus Tilings of a Holey Hexagon
The Shape of a Benedictine Monastery: The SaintGall Ontology
Geometry and the onset of rigidity in a disordered network
Decentralized Robust Transceiver Designs for MISO SWIPT Interference Channel
Topological and Graph-coloring Conditions on the Parameter-independent Stability of Second-order Networked Systems
Strong stationary times and its use in cryptography
Controlling symmetry and localization with an artificial gauge field in a disordered quantum system
Additive energy and the metric Poissonian property
Calibration of depth cameras using denoised depth images
On asymptotic normality of certain linear rank statistics
Convex Hulls of Random Walks in Higher Dimensions: A Large Deviation Study
Completion of High Order Tensor Data with Missing Entries via Tensor-train Decomposition
Tropical Sufficient Statistics for Persistent Homology with a Parametric Application to Infectious Viral Disease
Locating 3D Object Proposals: A Depth-Based Online Approach
Minimal Glider-Gun in a 2D Cellular Automaton
Deep Packet: A Novel Approach For Encrypted Traffic Classification Using Deep Learning
Multi-level Feedback Web Links Selection Problem: Learning and Optimization
Full rainbow matchings in graphs and hypergraphs
Stabilization and state trajectory tracking problem for nonlinear control systems in the presence of disturbances
Combining cumulative sum change-point detection tests for assessing the stationarity of univariate time series
Uniform generation of random graphs with power-law degree sequences
Modeling Coefficient Alpha for Measurement of Individualized Test Score Internal Consistency
What Weights Work for You? Adapting Weights for Any Pareto Front Shape in Decomposition-based Evolutionary Multi-Objective Optimisation
Finite-size effects in a stochastic Kuramoto model
The normalized Laplacian spectra of the double corona based on $R$-graph
Applications of an algorithm for solving Fredholm equations of the first kind
A Real-time Trainable and Clock-less Spiking Neural Network with 1R Memristive Synapses
Method to Detect Eye Position Noise from Video-Oculography when Detection of Pupil or Corneal Reflection Position Fails
Optimally Learning Populations of Parameters
Enumerating traceless matrices over compact discrete valuation rings
A Modular Analysis of Adaptive (Non-)Convex Optimization: Optimism, Composite Objectives, and Variational Bounds
Crowdsourcing Predictors of Residential Electric Energy Usage
Vessel Segmentation and Catheter Detection in X-Ray Angiograms Using Superpixels
Privacy Loss in Apple’s Implementation of Differential Privacy on MacOS 10.12
Training RNNs as Fast as CNNs
A Self-aware Sampling Scheme to Efficiently Train Fully Convolutional Networks for Semantic Segmentation
Dissections of trapezoids into trapezoids homothetic to trapezoids of a given set
Machine learning \& artificial intelligence in the quantum domain
Detecting Hands in Egocentric Videos: Towards Action Recognition
A Statistical Comparison of Some Theories of NP Word Order
Biharmonic Distance and the Performance of Second-Order Consensus Networks with Stochastic Disturbances
Averages of Unlabeled Networks: Geometric Characterization and Asymptotic Behavior