OpenRaiser/Intern-Atlas huggingface dataset:
Learning graphs from data: A signal representation perspective
Venue: arXiv cs.LG 2019
Year: 2019

The construction of a meaningful graph topology plays a crucial role in the effective representation, processing, analysis and visualization of structured data. When a natural choice of the graph is not readily available from the data sets, it is thus desirable to infer or learn a graph topology from the data. In this tutorial overview, we survey solutions to the problem of graph learning, including classical viewpoints from statistics and physics, and more recent approaches that adopt a graph signal processing (GSP) perspective. We further emphasize the conceptual similarities and differences between classical and GSP-based graph inference methods, and highlight the potential advantage of the latter in a number of theoretical and practical scenarios. We conclude with several open issues and challenges that are keys to the design of future signal processing and machine learning algorithms for learning graphs from data.
Load Balancing User Association in Millimeter Wave MIMO Networks
Venue: arXiv cs.IT 2019
Year: 2019

User association is necessary in dense millimeter wave (mmWave) networks to determine which base station a user connects to in order to balance base station loads and maximize throughput. Given that mmWave connections are highly directional and vulnerable to small channel variations, user association changes these connections and hence significantly affects the user's instantaneous rate as well as network interference. In this paper, we introduce a new load balancing user association scheme for mmWave MIMO networks which considers this dependency on user association of user's transmission rates and network interference. We formulate the user association problem as mixed integer nonlinear programming and design a polynomial-time algorithm, called Worst Connection Swapping (WCS), to find a near-optimal solution. Simulation results confirm that the proposed user association scheme improves network performance significantly by moving the traffic of congested base stations to lightly-loaded ones and adjusting the interference accordingly. Further, the proposed WCS algorithm outperforms other generic algorithms for combinatorial programming such as the genetic algorithm in both accuracy and speed at several orders of magnitude faster, and for small networks where exhaustive search is possible it reaches the optimal solution.
Efficient Database Generation for Data-driven Security Assessment of Power Systems
Venue: arXiv cs.SY 2019
Year: 2019

Power system security assessment methods require large datasets of operating points to train or test their performance. As historical data often contain limited number of abnormal situations, simulation data are necessary to accurately determine the security boundary. Generating such a database is an extremely demanding task, which becomes intractable even for small system sizes. This paper proposes a modular and highly scalable algorithm for computationally efficient database generation. Using convex relaxation techniques and complex network theory, we discard large infeasible regions and drastically reduce the search space. We explore the remaining space by a highly parallelizable algorithm and substantially decrease computation time. Our method accommodates numerous definitions of power system security. Here we focus on the combination of N-k security and small-signal stability. Demonstrating our algorithm on IEEE 14-bus and NESTA 162-bus systems, we show how it outperforms existing approaches requiring less than 10% of the time other methods require.
On Computing the Multiplicity of Cycles in Bipartite Graphs Using the Degree Distribution and the Spectrum of the Graph
Venue: arXiv cs.DM 2019
Year: 2019

Counting short cycles in bipartite graphs is a fundamental problem of interest in the analysis and design of low-density parity-check (LDPC) codes. The vast majority of research in this area is focused on algorithmic techniques. Most recently, Blake and Lin proposed a computational technique to count the number of cycles of length $g$ in a bi-regular bipartite graph, where $g$ is the girth of the graph. The information required for the computation is the node degree and the multiplicity of the nodes on both sides of the partition, as well as the eigenvalues of the adjacency matrix of the graph (graph spectrum). In this paper, the result of Blake and Lin is extended to compute the number of cycles of length $g+2, \ldots, 2g-2$, for bi-regular bipartite graphs, as well as the number of $4$-cycles and $6$-cycles in irregular and half-regular bipartite graphs, with $g \geq 4$ and $g \geq 6$, respectively.
Labeling Algorithm and Compact Routing Scheme for a Small World Network Model
Venue: arXiv cs.DS 2019
Year: 2019

This paper defines the toroidal small world labeling problem that asks for a labeling of the vertices of a network such that the labels possess information that allows a compact routing scheme in the network. We consider the problem over a small world network model we propose. Both the model and the compact routing scheme have applications in peer-to-peer networks. The proposed model is based on the model of Kleinberg (2000), and generates an undirected two-dimensional torus with one random long-range edge per vertex. These random edges create forbidden cycles that mimic the underlying torus topology, and this behavior confuses attempts for extracting the routing information from the network. We show that such forbidden cycles happen with small probability, allowing us to use a breadth-first search that finds the vertices positions on the torus. The positions are pairs of integer numbers that provides routing information to a greedy routing algorithm that finds small paths of the network. We present a linear time labeling algorithm that detects and removes the random edges, finds the underlying torus and labels almost all vertices through a breadth-first search. The labeling algorithm is then used by a compact routing scheme for the proposed small world model.
Competing Prediction Algorithms
Venue: arXiv cs.GT 2019
Year: 2019

Prediction is a well-studied machine learning task, and prediction algorithms are core ingredients in online products and services. Despite their centrality in the competition between online companies who offer prediction-based products, the strategic use of prediction algorithms remains unexplored. The goal of this paper is to examine strategic use of prediction algorithms. We introduce a novel game-theoretic setting that is based on the PAC learning framework, where each player (aka a prediction algorithm at competition) seeks to maximize the sum of points for which it produces an accurate prediction and the others do not. We show that algorithms aiming at generalization may wittingly miss-predict some points to perform better than others on expectation. We analyze the empirical game, i.e. the game induced on a given sample, prove that it always possesses a pure Nash equilibrium, and show that every better-response learning process converges. Moreover, our learning-theoretic analysis suggests that players can, with high probability, learn an approximate pure Nash equilibrium for the whole population using a small number of samples.
Deep Fluids: A Generative Network for Parameterized Fluid Simulations
Venue: arXiv cs.LG 2019
Year: 2019

This paper presents a novel generative model to synthesize fluid simulations from a set of reduced parameters. A convolutional neural network is trained on a collection of discrete, parameterizable fluid simulation velocity fields. Due to the capability of deep learning architectures to learn representative features of the data, our generative model is able to accurately approximate the training data set, while providing plausible interpolated in-betweens. The proposed generative model is optimized for fluids by a novel loss function that guarantees divergence-free velocity fields at all times. In addition, we demonstrate that we can handle complex parameterizations in reduced spaces, and advance simulations in time by integrating in the latent space with a second network. Our method models a wide variety of fluid behaviors, thus enabling applications such as fast construction of simulations, interpolation of fluids with different parameters, time re-sampling, latent space simulations, and compression of fluid simulation data. Reconstructed velocity fields are generated up to 700x faster than re-simulating the data with the underlying CPU solver, while achieving compression rates of up to 1300x.
Diffix-Birch: Extending Diffix-Aspen
Venue: arXiv cs.CR 2019
Year: 2019

A longstanding open problem is that of how to get high quality statistics through direct queries to databases containing information about individuals without revealing information specific to those individuals. Diffix is a framework for anonymous database query that adds noise based on the filter conditions in the query. A previous paper described the first version, called diffix-aspen. This version, diffix-birch, extends that description to include a wide variety of common features found in SQL. It describes attacks associated with various features, and the anonymization steps used to defend against those attacks. This paper describes diffix-birch, which was used for the bounty program sponsored by Aircloak starting December 2017.
On the Fourier Entropy Influence Conjecture for Extremal Classes
Venue: arXiv cs.CC 2019
Year: 2019

The Fourier Entropy-Influence (FEI) Conjecture of Friedgut and Kalai states that ${\bf H}[f] \leq C \cdot {\bf I}[f]$ holds for every Boolean function $f$, where ${\bf H}[f]$ denotes the spectral entropy of $f$, ${\bf I}[f]$ is its total influence, and $C > 0$ is a universal constant. Despite significant interest in the conjecture it has only been shown to hold for some classes of Boolean functions such as symmetric functions and read-once formulas. In this work, we prove the conjecture for extremal cases, functions with small influence and functions with high entropy. Specifically, we show that: * FEI holds for the class of functions with ${\bf I}[f] \leq 2^{-cn}$ with the constant $C = 4 \cdot \frac{c+1}{c}$. Furthermore, proving FEI for a class of functions with ${\bf I}[f] \leq 2^{-s(n)}$ for some $s(n) = o(n)$ will imply FEI for the class of all Boolean functions. * FEI holds for the class of functions with ${\bf H}[f] \geq cn$ with the constant $C = \frac{1 + c}{h^{-1}(c^2)}$. Furthermore, proving FEI for a class of functions with ${\bf H}[f] \geq s(n)$ for some $s(n) = o(n)$ will imply FEI for the class of all Boolean functions. Additionally, we show that FEI holds for the class of functions with constant $\|\widehat{f}\|_1$, completing the results of Chakhraborty et al. that bounded the entropy of such functions. We also improve the result of Wan et al. for read-k decision trees, from ${\bf H}[f] \leq O(k) \cdot {\bf I}[f]$ to ${\bf H}[f] \leq O(\sqrt{k}) \cdot {\bf I}[f]$. Finally, we suggest a direction for proving FEI for read-k DNFs, and prove the Fourier Min-Entropy/Influence (FMEI) Conjecture for regular read-k DNFs.
Reducing Transducer Equivalence to Register Automata Problems Solved by "Hilbert Method"
Venue: arXiv cs.FL 2019
Year: 2019

In the past decades, classical results from algebra, including Hilbert's Basis Theorem, had various applications in formal languages, including a proof of the Ehrenfeucht Conjecture, decidability of HDT0L sequence equivalence, and decidability of the equivalence problem for functional tree-to-string transducers. In this paper, we study the scope of the algebraic methods mentioned above, particularily as applied to the equivalence problem for register automata. We provide two results, one positive, one negative. The positive result is that equivalence is decidable for MSO transformations on unordered forests. The negative result comes from a try to extend this method to decide equivalence on macro tree transducers. We reduce macro tree transducers equivalence to an equivalence problem for some class of register automata naturally relevant to our method. We then prove this latter problem to be undecidable.
Reinforcement Learning-based Resource Allocation in Fog RAN for IoT with Heterogeneous Latency Requirements
Venue: arXiv cs.NI 2019
Year: 2019

In light of the quick proliferation of Internet of things (IoT) devices and applications, fog radio access network (Fog-RAN) has been recently proposed for fifth generation (5G) wireless communications to assure the requirements of ultra-reliable low-latency communication (URLLC) for the IoT applications which cannot accommodate large delays. Hence, fog nodes (FNs) are equipped with computing, signal processing and storage capabilities to extend the inherent operations and services of the cloud to the edge. We consider the problem of sequentially allocating the FN's limited resources to the IoT applications of heterogeneous latency requirements. For each access request from an IoT user, the FN needs to decide whether to serve it locally utilizing its own resources or to refer it to the cloud to conserve its valuable resources for future users of potentially higher utility to the system (i.e., lower latency requirement). We formulate the Fog-RAN resource allocation problem in the form of a Markov decision process (MDP), and employ several reinforcement learning (RL) methods, namely Q-learning, SARSA, Expected SARSA, and Monte Carlo, for solving the MDP problem by learning the optimum decision-making policies. We verify the performance and adaptivity of the RL methods and compare it with the performance of a fixed-threshold-based algorithm. Extensive simulation results considering 19 IoT environments of heterogeneous latency requirements corroborate that RL methods always achieve the best possible performance regardless of the IoT environment.
Subspace-Invariant AC$^0$ Formulas
Venue: arXiv cs.LO 2019
Year: 2019

We consider the action of a linear subspace $U$ of $\{0,1\}^n$ on the set of AC$^0$ formulas with inputs labeled by literals in the set $\{X_1,\overline X_1,\dots,X_n,\overline X_n\}$, where an element $u \in U$ acts on formulas by transposing the $i$th pair of literals for all $i \in [n]$ such that $u_i=1$. A formula is {\em $U$-invariant} if it is fixed by this action. For example, there is a well-known recursive construction of depth $d+1$ formulas of size $O(n{\cdot}2^{dn^{1/d}})$ computing the $n$-variable PARITY function; these formulas are easily seen to be $P$-invariant where $P$ is the subspace of even-weight elements of $\{0,1\}^n$. In this paper we establish a nearly matching $2^{d(n^{1/d}-1)}$ lower bound on the $P$-invariant depth $d+1$ formula size of PARITY. Quantitatively this improves the best known $Ω(2^{\frac{1}{84}d(n^{1/d}-1)})$ lower bound for {\em unrestricted} depth $d+1$ formulas, while avoiding the use of the switching lemma. More generally, for any linear subspaces $U \subset V$, we show that if a Boolean function is $U$-invariant and non-constant over $V$, then its $U$-invariant depth $d+1$ formula size is at least $2^{d(m^{1/d}-1)}$ where $m$ is the minimum Hamming weight of a vector in $U^\bot \setminus V^\bot$.
Stability and complexity of mixed discriminants
Venue: arXiv cs.DS 2019
Year: 2019

We show that the mixed discriminant of $n$ positive semidefinite $n \times n$ real symmetric matrices can be approximated within a relative error $ε>0$ in quasi-polynomial $n^{O(\ln n -\ln ε)}$ time, provided the distance of each matrix to the identity matrix in the operator norm does not exceed some absolute constant $γ_0 >0$. We deduce a similar result for the mixed discriminant of doubly stochastic $n$-tuples of matrices from the Marcus - Spielman - Srivastava bound on the roots of the mixed characteristic polynomial. Finally, we construct a quasi-polynomial algorithm for approximating the sum of $m$-th powers of principal minors of a matrix, provided the operator norm of the matrix is strictly less than 1. As is shown by Gurvits, for $m=2$ the problem is $\#P$-hard and covers the problem of computing the mixed discriminant of positive semidefinite matrices of rank 2.
Convex Class Model on Symmetric Positive Definite Manifolds
Venue: arXiv cs.CV 2019
Year: 2019

The effectiveness of Symmetric Positive Definite (SPD) manifold features has been proven in various computer vision tasks. However, due to the non-Euclidean geometry of these features, existing Euclidean machineries cannot be directly used. In this paper, we tackle the classification tasks with limited training data on SPD manifolds. Our proposed framework, named Manifold Convex Class Model, represents each class on SPD manifolds using a convex model, and classification can be performed by computing distances to the convex models. We provide three methods based on different metrics to address the optimization problem of the smallest distance of a point to the convex model on SPD manifold. The efficacy of our proposed framework is demonstrated both on synthetic data and several computer vision tasks including object recognition, texture classification, person re-identification and traffic scene classification.
BubbleRank: Safe Online Learning to Re-Rank via Implicit Click Feedback
Venue: arXiv cs.LG 2019
Year: 2019

In this paper, we study the problem of safe online learning to re-rank, where user feedback is used to improve the quality of displayed lists. Learning to rank has traditionally been studied in two settings. In the offline setting, rankers are typically learned from relevance labels created by judges. This approach has generally become standard in industrial applications of ranking, such as search. However, this approach lacks exploration and thus is limited by the information content of the offline training data. In the online setting, an algorithm can experiment with lists and learn from feedback on them in a sequential fashion. Bandit algorithms are well-suited for this setting but they tend to learn user preferences from scratch, which results in a high initial cost of exploration. This poses an additional challenge of safe exploration in ranked lists. We propose BubbleRank, a bandit algorithm for safe re-ranking that combines the strengths of both the offline and online settings. The algorithm starts with an initial base list and improves it online by gradually exchanging higher-ranked less attractive items for lower-ranked more attractive items. We prove an upper bound on the n-step regret of BubbleRank that degrades gracefully with the quality of the initial base list. Our theoretical findings are supported by extensive experiments on a large-scale real-world click dataset.
Flow Logic
Venue: arXiv cs.LO 2019
Year: 2019

Flow networks have attracted a lot of research in computer science. Indeed, many questions in numerous application areas can be reduced to questions about flow networks. Many of these applications would benefit from a framework in which one can formally reason about properties of flow networks that go beyond their maximal flow. We introduce Flow Logics: modal logics that treat flow functions as explicit first-order objects and enable the specification of rich properties of flow networks. The syntax of our logic BFL* (Branching Flow Logic) is similar to the syntax of the temporal logic CTL*, except that atomic assertions may be flow propositions, like $> γ$ or $\geq γ$, for $γ\in \mathbb{N}$, which refer to the value of the flow in a vertex, and that first-order quantification can be applied both to paths and to flow functions. We present an exhaustive study of the theoretical and practical aspects of BFL*, as well as extensions and fragments of it. Our extensions include flow quantifications that range over non-integral flow functions or over maximal flow functions, path quantification that ranges over paths along which non-zero flow travels, past operators, and first-order quantification of flow values. We focus on the model-checking problem and show that it is PSPACE-complete, as it is for CTL*. Handling of flow quantifiers, however, increases the complexity in terms of the network to ${\rm P}^{\rm NP}$, even for the LFL and BFL fragments, which are the flow-counterparts of LTL and CTL. We are still able to point to a useful fragment of BFL* for which the model-checking problem can be solved in polynomial time. Finally, we introduce and study the query-checking problem for BFL*, where under-specified BFL* formulas are used for network exploration.
Online Variant of Parcel Allocation in Last-mile Delivery
Venue: arXiv cs.HC 2019
Year: 2019

We investigate the problem of last-mile delivery, where a large pool of citizen crowd-workers are hired to perform a variety of location-specific urban logistics parcel delivering tasks. Current approaches focus on offline scenarios, where all the spatio temporal information of parcels and workers are given. However, the offline scenarios can be impractical since parcels and workers appear dynamically in real applications, and their information is unknown in advance. In this paper, in order to solve the shortcomings of the offline setting, we first formalize the online parcel allocation in last-mile delivery problem, where all parcels were put in pop-stations in advance, while workers arrive dynamically. Then we propose an algorithm which provides theoretical guarantee for the parcel allocation in last-mile delivery. Finally, we verify the effectiveness and efficiency of the proposed method through extensive experiments on real and synthetic datasets.
GILE: A Generalized Input-Label Embedding for Text Classification
Venue: arXiv cs.CL 2019
Year: 2019

Neural text classification models typically treat output labels as categorical variables which lack description and semantics. This forces their parametrization to be dependent on the label set size, and, hence, they are unable to scale to large label sets and generalize to unseen ones. Existing joint input-label text models overcome these issues by exploiting label descriptions, but they are unable to capture complex label relationships, have rigid parametrization, and their gains on unseen labels happen often at the expense of weak performance on the labels seen during training. In this paper, we propose a new input-label model which generalizes over previous such models, addresses their limitations and does not compromise performance on seen labels. The model consists of a joint non-linear input-label embedding with controllable capacity and a joint-space-dependent classification unit which is trained with cross-entropy loss to optimize classification performance. We evaluate models on full-resource and low- or zero-resource text classification of multilingual news and biomedical text with a large label set. Our model outperforms monolingual and multilingual models which do not leverage label semantics and previous joint input-label space models in both scenarios.