OpenRaiser/Intern-Atlas huggingface dataset:
Spectral Alignment of Graphs
Venue: arXiv cs.DS 2017
Year: 2017

Graph alignment refers to the problem of finding a bijective mapping across vertices of two graphs such that, if two nodes are connected in the first graph, their images are connected in the second graph. This problem arises in many fields such as computational biology, social sciences, and computer vision and is often cast as a quadratic assignment problem (QAP). Most standard graph alignment methods consider an optimization that maximizes the number of matches between the two graphs, ignoring the effect of mismatches. We propose a generalized graph alignment formulation that considers both matches and mismatches in a standard QAP formulation. This modification can have a major impact in aligning graphs with different sizes and heterogenous edge densities. Moreover, we propose two methods for solving the generalized graph alignment problem based on spectral decomposition of matrices. We compare the performance of proposed methods with some existing graph alignment algorithms including Natalie2, GHOST, IsoRank, NetAlign, Klau's approach as well as a semidefinite programming-based method over various synthetic and real graph models. Our proposed method based on simultaneous alignment of multiple eigenvectors leads to consistently good performance in different graph models. In particular, in the alignment of regular graph structures which is one of the most difficult graph alignment cases, our proposed method significantly outperforms other methods.
Optimal Sample Complexity for Stable Matrix Recovery
Venue: arXiv cs.IT 2017
Year: 2017

Tremendous efforts have been made to study the theoretical and algorithmic aspects of sparse recovery and low-rank matrix recovery. This paper fills a theoretical gap in matrix recovery: the optimal sample complexity for stable recovery without constants or log factors. We treat sparsity, low-rankness, and potentially other parsimonious structures within the same framework: constraint sets that have small covering numbers or Minkowski dimensions. We consider three types of random measurement matrices (unstructured, rank-1, and symmetric rank-1 matrices), following probability distributions that satisfy some mild conditions. In all these cases, we prove a fundamental result -- the recovery of matrices with parsimonious structures, using an optimal (or near optimal) number of measurements, is stable with high probability.
Low Correlation Sequences from Linear Combinations of Characters
Venue: arXiv cs.IT 2017
Year: 2017

Pairs of binary sequences formed using linear combinations of multiplicative characters of finite fields are exhibited that, when compared to random sequence pairs, simultaneously achieve significantly lower mean square autocorrelation values (for each sequence in the pair) and significantly lower mean square crosscorrelation values. If we define crosscorrelation merit factor analogously to the usual merit factor for autocorrelation, and if we define demerit factor as the reciprocal of merit factor, then randomly selected binary sequence pairs are known to have an average crosscorrelation demerit factor of $1$. Our constructions provide sequence pairs with crosscorrelation demerit factor significantly less than $1$, and at the same time, the autocorrelation demerit factors of the individual sequences can also be made significantly less than $1$ (which also indicates better than average performance). The sequence pairs studied here provide combinations of autocorrelation and crosscorrelation performance that are not achievable using sequences formed from single characters, such as maximal linear recursive sequences (m-sequences) and Legendre sequences. In this study, exact asymptotic formulae are proved for the autocorrelation and crosscorrelation merit factors of sequence pairs formed using linear combinations of multiplicative characters. Data is presented that shows that the asymptotic behavior is closely approximated by sequences of modest length.
Entity Embeddings with Conceptual Subspaces as a Basis for Plausible Reasoning
Venue: arXiv cs.AI 2017
Year: 2017

Conceptual spaces are geometric representations of conceptual knowledge, in which entities correspond to points, natural properties correspond to convex regions, and the dimensions of the space correspond to salient features. While conceptual spaces enable elegant models of various cognitive phenomena, the lack of automated methods for constructing such representations have so far limited their application in artificial intelligence. To address this issue, we propose a method which learns a vector-space embedding of entities from Wikipedia and constrains this embedding such that entities of the same semantic type are located in some lower-dimensional subspace. We experimentally demonstrate the usefulness of these subspaces as (approximate) conceptual space representations by showing, among others, that important features can be modelled as directions and that natural properties tend to correspond to convex regions.
Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders
Venue: arXiv cs.GT 2017
Year: 2017

We study a central problem in Algorithmic Mechanism Design: constructing truthful mechanisms for welfare maximization in combinatorial auctions with submodular bidders. Dobzinski, Nisan, and Schapira provided the first mechanism that guarantees a non-trivial approximation ratio of $O(\log^2 m)$ [STOC'06], where $m$ is the number of items. This was subsequently improved to $O(\log m\log \log m)$ [Dobzinski, APPROX'07] and then to $O(\log m)$ [Krysta and Vocking, ICALP'12]. In this paper we develop the first mechanism that breaks the logarithmic barrier. Specifically, the mechanism provides an approximation ratio of $O(\sqrt {\log m})$. Similarly to previous constructions, our mechanism uses polynomially many value and demand queries, and in fact provides the same approximation ratio for the larger class of XOS (a.k.a. fractionally subadditive) valuations. We also develop a computationally efficient implementation of the mechanism for combinatorial auctions with budget additive bidders. Although in general computing a demand query is NP-hard for budget additive valuations, we observe that the specific form of demand queries that our mechanism uses can be efficiently computed when bidders are budget additive.
The AV1 Constrained Directional Enhancement Filter (CDEF)
Venue: arXiv cs.MM 2017
Year: 2017

This paper presents the constrained directional enhancement filter designed for the AV1 royalty-free video codec. The in-loop filter is based on a non-linear low-pass filter and is designed for vectorization efficiency. It takes into account the direction of edges and patterns being filtered. The filter works by identifying the direction of each block and then adaptively filtering with a high degree of control over the filter strength along the direction and across it. The proposed enhancement filter is shown to improve the quality of the Alliance for Open Media (AOM) AV1 and Thor video codecs in particular in low complexity configurations.
Sorting With Forbidden Intermediates
Venue: arXiv cs.DS 2017
Year: 2017

A wide range of applications, most notably in comparative genomics, involve the computation of a shortest sorting sequence of operations for a given permutation, where the set of allowed operations is fixed beforehand. Such sequences are useful for instance when reconstructing potential scenarios of evolution between species, or when trying to assess their similarity. We revisit those problems by adding a new constraint on the sequences to be computed: they must \emph{avoid} a given set of \emph{forbidden intermediates}, which correspond to species that cannot exist because the mutations that would be involved in their creation are lethal. We initiate this study by focusing on the case where the only mutations that can occur are exchanges of any two elements in the permutations, and give a polynomial time algorithm for solving that problem when the permutation to sort is an involution.
Recurrent Orthogonal Networks and Long-Memory Tasks
Venue: arXiv cs.NE 2017
Year: 2017

Although RNNs have been shown to be powerful tools for processing sequential data, finding architectures or optimization strategies that allow them to model very long term dependencies is still an active area of research. In this work, we carefully analyze two synthetic datasets originally outlined in (Hochreiter and Schmidhuber, 1997) which are used to evaluate the ability of RNNs to store information over many time steps. We explicitly construct RNN solutions to these problems, and using these constructions, illuminate both the problems themselves and the way in which RNNs store different types of information in their hidden states. These constructions furthermore explain the success of recent methods that specify unitary initializations or constraints on the transition matrices.
How Deep Neural Networks Can Improve Emotion Recognition on Video Data
Venue: arXiv cs.CV 2017
Year: 2017

We consider the task of dimensional emotion recognition on video data using deep learning. While several previous methods have shown the benefits of training temporal neural network models such as recurrent neural networks (RNNs) on hand-crafted features, few works have considered combining convolutional neural networks (CNNs) with RNNs. In this work, we present a system that performs emotion recognition on video data using both CNNs and RNNs, and we also analyze how much each neural network component contributes to the system's overall performance. We present our findings on videos from the Audio/Visual+Emotion Challenge (AV+EC2015). In our experiments, we analyze the effects of several hyperparameters on overall performance while also achieving superior performance to the baseline and other competing methods.
Reachability-Based Safety and Goal Satisfaction of Unmanned Aerial Platoons on Air Highways
Venue: arXiv cs.MA 2017
Year: 2017

Recently, there has been immense interest in using unmanned aerial vehicles (UAVs) for civilian operations. As a result, unmanned aerial systems traffic management is needed to ensure the safety and goal satisfaction of potentially thousands of UAVs flying simultaneously. Currently, the analysis of large multi-agent systems cannot tractably provide these guarantees if the agents' set of maneuvers is unrestricted. In this paper, platoons of UAVs flying on air highways is proposed to impose an airspace structure that allows for tractable analysis. For the air highway placement problem, the fast marching method is used to produce a sequence of air highways that minimizes the cost of flying from an origin to any destination. The placement of air highways can be updated in real-time to accommodate sudden airspace changes. Within platoons traveling on air highways, each vehicle is modeled as a hybrid system. Using Hamilton-Jacobi reachability, safety and goal satisfaction are guaranteed for all mode transitions. For a single altitude range, the proposed approach guarantees safety for one safety breach per vehicle, in the unlikely event of multiple safety breaches, safety can be guaranteed over multiple altitude ranges. We demonstrate the platooning concept through simulations of three representative scenarios.
Range Assignment for Power Optimization in Load-Coupled Heterogeneous Networks
Venue: arXiv cs.IT 2017
Year: 2017

We consider the problem of transmission energy op- timization via range assignment for Low Power Nodes (LPNs) in Long Term Evolution (LTE) Heterogenous Networks (HetNets). The optimization is subject to the load coupling model, where the cells interfere with one another. Each cell provides data service for its users so as to maintain a target Quality-of-Service (QoS). We prove that, irrespective the presence of maximum power limit or its value, operating at full load is optimal. We perform energy minimization by optimizing the association between User Equipments (UEs) and cells via selecting cell- specific offsets on LPNs. Moreover, the optimization problem is proved to be NP-hard. We propose a tabu search algorithm for offset optimization (TSO). For each offset, TSO computes the optimal power solution such that all cells operate at full load. Numerical results demonstrate the significant performance improvement of TSO on optimizing the sum transmission energy, compared to the conventional solution where uniform offset is used for all LPNs.
U-BeAS: A Stackelberg Game for Device-to-Device Communications
Venue: arXiv cs.NI 2017
Year: 2017

User-behavior-aware communications will be a key feature of future generation cellular networks, so user experience is enhanced with greater benefit to users. In this paper, a user-behavior-aware Stackelberg (U-BeAS) game for device-to-device (D2D) communications overlaying cellular communications is proposed. Our proposed game provides an optimal trade-off between minimizing transmit power and maximizing packet delivery ratio (PDR), with respect to D2D user-behavior for all D2D pairs. The Stackelberg leader, base station (BS), selects its satisfaction with the social welfare of the D2D followers by considering the reaction of the followers to the price it charges. All followers (D2D pairs) select transmit power so as to guarantee a desired quality-of-experience (QoE), where each follower enacts one of three possible behaviors: (i) casual; (ii) intermediate; or (iii) serious. Analysis shows that there exists a sub-game perfect Stackelberg Equilibrium across all players. Analysis and simulation demonstrates that the BS leader rapidly converges to an optimal satisfaction while guaranteeing social welfare across D2D users, and all D2D followers then rapidly converge to a Pareto-efficient outcome with respect to transmit power and PDR.
From Duels to Battefields: Computing Equilibria of Blotto and Other Games
Venue: arXiv cs.GT 2017
Year: 2017

We study the problem of computing Nash equilibria of zero-sum games. Many natural zero-sum games have exponentially many strategies, but highly structured payoffs. For example, in the well-studied Colonel Blotto game (introduced by Borel in 1921), players must divide a pool of troops among a set of battlefields with the goal of winning (i.e., having more troops in) a majority. The Colonel Blotto game is commonly used for analyzing a wide range of applications from the U.S presidential election, to innovative technology competitions, to advertisement, to sports. However, because of the size of the strategy space, standard methods for computing equilibria of zero-sum games fail to be computationally feasible. Indeed, despite its importance, only a few solutions for special variants of the problem are known. In this paper we show how to compute equilibria of Colonel Blotto games. Moreover, our approach takes the form of a general reduction: to find a Nash equilibrium of a zero-sum game, it suffices to design a separation oracle for the strategy polytope of any bilinear game that is payoff-equivalent. We then apply this technique to obtain the first polytime algorithms for a variety of games. In addition to Colonel Blotto, we also show how to compute equilibria in an infinite-strategy variant called the General Lotto game; this involves showing how to prune the strategy space to a finite subset before applying our reduction. We also consider the class of dueling games, first introduced by Immorlica et al. (2011). We show that our approach provably extends the class of dueling games for which equilibria can be computed: we introduce a new dueling game, the matching duel, on which prior methods fail to be computationally feasible but upon which our reduction can be applied.
Exploiting nodes symmetries to control synchronization and consensus patterns in multiagent systems
Venue: arXiv cs.SY 2017
Year: 2017

We present new conditions to obtain synchronization and consensus patterns in complex network systems. The key idea is to exploit symmetries of the nodes' vector fields to induce a desired synchronization/consensus pattern, where nodes are clustered in different groups each converging towards a different synchronized evolution. We show that the new conditions we present offer a systematic methodology to design a distributed network controller able to drive a network of interest towards a desired synchronization/consensus pattern.
BPTree: an $\ell_2$ heavy hitters algorithm using constant memory
Venue: arXiv cs.DS 2017
Year: 2017

The task of finding heavy hitters is one of the best known and well studied problems in the area of data streams. One is given a list $i_1,i_2,\ldots,i_m\in[n]$ and the goal is to identify the items among $[n]$ that appear frequently in the list. In sub-polynomial space, the strongest guarantee available is the $\ell_2$ guarantee, which requires finding all items that occur at least $ε\|f\|_2$ times in the stream, where the vector $f\in\mathbb{R}^n$ is the count histogram of the stream with $i$th coordinate equal to the number of times~$i$ appears $f_i:=\#\{j\in[m]:i_j=i\}$. The first algorithm to achieve the $\ell_2$ guarantee was the CountSketch of [CCF04], which requires $O(ε^{-2}\log n)$ words of memory and $O(\log n)$ update time and is known to be space-optimal if the stream allows for deletions. The recent work of [BCIW16] gave an improved algorithm for insertion-only streams, using only $O(ε^{-2}\logε^{-1}\log\log n)$ words of memory. In this work, we give an algorithm \bptree for $\ell_2$ heavy hitters in insertion-only streams that achieves $O(ε^{-2}\logε^{-1})$ words of memory and $O(\logε^{-1})$ update time, which is the optimal dependence on $n$ and $m$. In addition, we describe an algorithm for tracking $\|f\|_2$ at all times with $O(ε^{-2})$ memory and update time. Our analyses rely on bounding the expected supremum of a Bernoulli process involving Rademachers with limited independence, which we accomplish via a Dudley-like chaining argument that may have applications elsewhere.
First Steps Toward Camera Model Identification with Convolutional Neural Networks
Venue: arXiv cs.CV 2017
Year: 2017

Detecting the camera model used to shoot a picture enables to solve a wide series of forensic problems, from copyright infringement to ownership attribution. For this reason, the forensic community has developed a set of camera model identification algorithms that exploit characteristic traces left on acquired images by the processing pipelines specific of each camera model. In this paper, we investigate a novel approach to solve camera model identification problem. Specifically, we propose a data-driven algorithm based on convolutional neural networks, which learns features characterizing each camera model directly from the acquired pictures. Results on a well-known dataset of 18 camera models show that: (i) the proposed method outperforms up-to-date state-of-the-art algorithms on classification of 64x64 color image patches; (ii) features learned by the proposed network generalize to camera models never used for training.
Rigorous Analysis of Software Countermeasures against Cache Attacks
Venue: arXiv cs.CR 2017
Year: 2017

CPU caches introduce variations into the execution time of programs that can be exploited by adversaries to recover private information about users or cryptographic keys. Establishing the security of countermeasures against this threat often requires intricate reasoning about the interactions of program code, memory layout, and hardware architecture and has so far only been done for restricted cases. In this paper we devise novel techniques that provide support for bit-level and arithmetic reasoning about memory accesses in the presence of dynamic memory allocation. These techniques enable us to perform the first rigorous analysis of widely deployed software countermeasures against cache attacks on modular exponentiation, based on executable code.
Template Matching via Densities on the Roto-Translation Group
Venue: arXiv cs.CV 2017
Year: 2017

We propose a template matching method for the detection of 2D image objects that are characterized by orientation patterns. Our method is based on data representations via orientation scores, which are functions on the space of positions and orientations, and which are obtained via a wavelet-type transform. This new representation allows us to detect orientation patterns in an intuitive and direct way, namely via cross-correlations. Additionally, we propose a generalized linear regression framework for the construction of suitable templates using smoothing splines. Here, it is important to recognize a curved geometry on the position-orientation domain, which we identify with the Lie group SE(2): the roto-translation group. Templates are then optimized in a B-spline basis, and smoothness is defined with respect to the curved geometry. We achieve state-of-the-art results on three different applications: detection of the optic nerve head in the retina (99.83% success rate on 1737 images), of the fovea in the retina (99.32% success rate on 1616 images), and of the pupil in regular camera images (95.86% on 1521 images). The high performance is due to inclusion of both intensity and orientation features with effective geometric priors in the template matching. Moreover, our method is fast due to a cross-correlation based matching approach.
A consensus-based secondary control layer for stable current sharing and voltage balancing in DC microgrids
Venue: arXiv cs.SY 2017
Year: 2017

In this paper, we propose a secondary consensus-based control layer for current sharing and voltage balancing in DC microGrids (mGs). To this purpose, we assume that Distributed Generation Units (DGUs) are equipped with decentralized primary controllers guaranteeing voltage stability. This goal can be achieved using, for instance, Plug-and-Play (PnP) regulators. We analyze the behavior of the closed-loop mG by approximating local primary control loops with either unitary gains or first-order transfer functions. Besides proving exponential stability, current sharing, and voltage balancing, we describe how to design secondary controllers in a PnP fashion when DGUs are added or removed. Theoretical results are complemented by simulations, using a 7-DGUs mG implemented in Simulink/PLECS, and experiments on a 3-DGUs mG.
Cost-sensitive Learning for Utility Optimization in Online Advertising Auctions
Venue: arXiv cs.LG 2017
Year: 2017

One of the most challenging problems in computational advertising is the prediction of click-through and conversion rates for bidding in online advertising auctions. An unaddressed problem in previous approaches is the existence of highly non-uniform misprediction costs. While for model evaluation these costs have been taken into account through recently proposed business-aware offline metrics -- such as the Utility metric which measures the impact on advertiser profit -- this is not the case when training the models themselves. In this paper, to bridge the gap, we formally analyze the relationship between optimizing the Utility metric and the log loss, which is considered as one of the state-of-the-art approaches in conversion modeling. Our analysis motivates the idea of weighting the log loss with the business value of the predicted outcome. We present and analyze a new cost weighting scheme and show that significant gains in offline and online performance can be achieved.