OpenRaiser/Intern-Atlas huggingface dataset:
A Comparative Study of Different Approaches for Tracking Communities in Evolving Social Networks
Venue: arXiv cs.SI 2019
Year: 2019

In real-world social networks, there is an increasing interest in tracking the evolution of groups of users and detecting the various changes they are liable to undergo. Several approaches have been proposed for this. In studying these approaches, we observed that most of them use a two-stage process. In the first stage, they run an algorithm to identify groups of users at each timestamp. In the second stage, a pair-wise comparison based on a similarity measure is employed to track groups of users and detect changes they may undergo. While the majority of existing approaches use a two-stage process, they all run different algorithms to identify communities and rely on different similarity measures to track groups of users over time. Noting that the different approaches may perform differently depending on the dynamic social network under investigation, we decided to make a high level survey of some existing tracking approaches and then do a comparative analysis of some of them. In our analysis, we compared the algorithms in two main situations: $(1)$ when groups of users do not overlap and $(2)$ when the groups are overlapping. The study was done on three different testbeds extracted from the DBLP, Autonomous System (AS) and Yelp datasets.
Umbrella: Enabling ISPs to Offer Readily Deployable and Privacy-Preserving DDoS Prevention Services
Venue: arXiv cs.CR 2019
Year: 2019

Defending against distributed denial of service (DDoS) attacks in the Internet is a fundamental problem. However, recent industrial interviews with over 100 security experts from more than ten industry segments indicate that DDoS problems have not been fully addressed. The reasons are twofold. On one hand, many academic proposals that are provably secure witness little real-world deployment. On the other hand, the operation model for existing DDoS-prevention service providers (e.g., Cloudflare, Akamai) is privacy invasive for large organizations (e.g., government). In this paper, we present Umbrella, a new DDoS defense mechanism enabling Internet Service Providers (ISPs) to offer readily deployable and privacy-preserving DDoS prevention services to their customers. At its core, Umbrella develops a multi-layered defense architecture to defend against a wide spectrum of DDoS attacks. In particular, the flood throttling layer stops amplification-based DDoS attacks; the congestion resolving layer, aiming to prevent sophisticated attacks that cannot be easily filtered, enforces congestion accountability to ensure that legitimate flows are guaranteed to receive their fair shares regardless of attackers' strategies; and finally the userspecific layer allows DDoS victims to enforce self-desired traffic control policies that best satisfy their business requirements. Based on Linux implementation, we demonstrate that Umbrella is capable to deal with large scale attacks involving millions of attack flows, meanwhile imposing negligible packet processing overhead. Further, our physical testbed experiments and large scale simulations prove that Umbrella is effective to mitigate various DDoS attacks.
Trick or TReAT: Thematic Reinforcement for Artistic Typography
Venue: arXiv cs.CV 2019
Year: 2019

An approach to make text visually appealing and memorable is semantic reinforcement - the use of visual cues alluding to the context or theme in which the word is being used to reinforce the message (e.g., Google Doodles). We present a computational approach for semantic reinforcement called TReAT - Thematic Reinforcement for Artistic Typography. Given an input word (e.g. exam) and a theme (e.g. education), the individual letters of the input word are replaced by cliparts relevant to the theme which visually resemble the letters - adding creative context to the potentially boring input word. We use an unsupervised approach to learn a latent space to represent letters and cliparts and compute similarities between the two. Human studies show that participants can reliably recognize the word as well as the theme in our outputs (TReATs) and find them more creative compared to meaningful baselines.
POP-CNN: Predicting Odor's Pleasantness with Convolutional Neural Network
Venue: arXiv cs.LG 2019
Year: 2019

Predicting odor's pleasantness simplifies the evaluation of odors and has the potential to be applied in perfumes and environmental monitoring industry. Classical algorithms for predicting odor's pleasantness generally use a manual feature extractor and an independent classifier. Manual designing a good feature extractor depend on expert knowledge and experience is the key to the accuracy of the algorithms. In order to circumvent this difficulty, we proposed a model for predicting odor's pleasantness by using convolutional neural network. In our model, the convolutional neural layers replace manual feature extractor and show better performance. The experiments show that the correlation between our model and human is over 90% on pleasantness rating. And our model has 99.9% accuracy in distinguishing between absolutely pleasant or unpleasant odors.
Stabilizability preserving quotients of non-linear systems
Venue: arXiv cs.SY 2019
Year: 2019

In this paper quotients of control systems which are generalizations of system reductions are used to study the stabilizability property of non-linear systems. Given a control system and its quotient we study under what conditions stabilizability of the quotient is sufficient to guarantee stabilizability of the original system. We develop a novel method of constructing a control Lyapunov function for the original system from the implied Lyapunov function of the quotient system, this construction involves the solution of a system of partial differential equations. By studying the integrability conditions of this associated system of partial differential equations we are able to characterize obstructions to our proposed method of constructing control Lyapunov functions in terms of the structure of the original control system.
DDoS attack detection method based on feature extraction of deep belief network
Venue: arXiv cs.CR 2019
Year: 2019

Distributed Denial of Service (DDOS) attack is one of the most common network attacks. DDoS attacks are becoming more and more diverse, which makes it difficult for some DDoS attack detection methods based on single network flow characteristics to detect various types of DDoS attacks, while the detection methods of multi-feature DDoS attacks have a certain lag due to the complexity of the algorithm. Therefore, it is necessary and urgent to monitor the trend of traffic change and identify DDoS attacks timely and accurately. In this paper, a method of DDoS attack detection based on deep belief network feature extraction and LSTM model is proposed. This method uses deep belief network to extract the features of IP packets, and identifies DDoS attacks based on LSTM model. This scheme is suitable for DDoS attack detection technology. The model can accurately predict the trend of normal network traffic, identify the anomalies caused by DDoS attacks, and apply to solve more detection methods about DDoS attacks in the future.
On First-Order Bounds, Variance and Gap-Dependent Bounds for Adversarial Bandits
Venue: arXiv cs.LG 2019
Year: 2019

We make three contributions to the theory of k-armed adversarial bandits. First, we prove a first-order bound for a modified variant of the INF strategy by Audibert and Bubeck [2009], without sacrificing worst case optimality or modifying the loss estimators. Second, we provide a variance analysis for algorithms based on follow the regularised leader, showing that without adaptation the variance of the regret is typically Ω(n^2) where n is the horizon. Finally, we study bounds that depend on the degree of separation of the arms, generalising the results by Cowan and Katehakis [2015] from the stochastic setting to the adversarial and improving the result of Seldin and Slivkins [2014] by a factor of log(n)/log(log(n)).
No more, no less - A formal model for serverless computing
Venue: arXiv cs.PL 2019
Year: 2019

Serverless computing, also known as Functions-as-a-Service, is a recent paradigm aimed at simplifying the programming of cloud applications. The idea is that developers design applications in terms of functions, which are then deployed on a cloud infrastructure. The infrastructure takes care of executing the functions whenever requested by remote clients, dealing automatically with distribution and scaling with respect to inbound traffic. While vendors already support a variety of programming languages for serverless computing (e.g. Go, Java, Javascript, Python), as far as we know there is no reference model yet to formally reason on this paradigm. In this paper, we propose the first formal programming model for serverless computing, which combines ideas from both the $λ$-calculus (for functions) and the $π$-calculus (for communication). To illustrate our proposal, we model a real-world serverless system. Thanks to our model, we are also able to capture and pinpoint the limitations of current vendor technologies, proposing possible amendments.
Residual Deep Convolutional Neural Network for EEG Signal Classification in Epilepsy
Venue: arXiv cs.LG 2019
Year: 2019

Epilepsy is the fourth most common neurological disorder, affecting about 1% of the population at all ages. As many as 60% of people with epilepsy experience focal seizures which originate in a certain brain area and are limited to part of one cerebral hemisphere. In focal epilepsy patients, a precise surgical removal of the seizure onset zone can lead to effective seizure control or even a seizure-free outcome. Thus, correct identification of the seizure onset zone is essential. For clinical evaluation purposes, electroencephalography (EEG) recordings are commonly used. However, their interpretation is usually done manually by physicians and is time-consuming and error-prone. In this work, we propose an automated epileptic signal classification method based on modern deep learning methods. In contrast to previous approaches, the network is trained directly on the EEG recordings, avoiding hand-crafted feature extraction and selection procedures. This exploits the ability of deep neural networks to detect and extract relevant features automatically, that may be too complex or subtle to be noticed by humans. The proposed network structure is based on a convolutional neural network with residual connections. We demonstrate that our network produces state-of-the-art performance on two benchmark data sets, a data set from Bonn University and the Bern-Barcelona data set. We conclude that modern deep learning approaches can reach state-of-the-art performance on epileptic EEG classification and automated seizure onset zone identification tasks when trained on raw EEG data. This suggests that such approaches have potential for improving clinical practice.
ExplainIt! -- A declarative root-cause analysis engine for time series data (extended version)
Venue: arXiv cs.DB 2019
Year: 2019

We present ExplainIt!, a declarative, unsupervised root-cause analysis engine that uses time series monitoring data from large complex systems such as data centres. ExplainIt! empowers operators to succinctly specify a large number of causal hypotheses to search for causes of interesting events. ExplainIt! then ranks these hypotheses, reducing the number of causal dependencies from hundreds of thousands to a handful for human understanding. We show how a declarative language, such as SQL, can be effective in declaratively enumerating hypotheses that probe the structure of an unknown probabilistic graphical causal model of the underlying system. Our thesis is that databases are in a unique position to enable users to rapidly explore the possible causal mechanisms in data collected from diverse sources. We empirically demonstrate how ExplainIt! had helped us resolve over 30 performance issues in a commercial product since late 2014, of which we discuss a few cases in detail.
Adaptive Hard Thresholding for Near-optimal Consistent Robust Regression
Venue: arXiv cs.LG 2019
Year: 2019

We study the problem of robust linear regression with response variable corruptions. We consider the oblivious adversary model, where the adversary corrupts a fraction of the responses in complete ignorance of the data. We provide a nearly linear time estimator which consistently estimates the true regression vector, even with $1-o(1)$ fraction of corruptions. Existing results in this setting either don't guarantee consistent estimates or can only handle a small fraction of corruptions. We also extend our estimator to robust sparse linear regression and show that similar guarantees hold in this setting. Finally, we apply our estimator to the problem of linear regression with heavy-tailed noise and show that our estimator consistently estimates the regression vector even when the noise has unbounded variance (e.g., Cauchy distribution), for which most existing results don't even apply. Our estimator is based on a novel variant of outlier removal via hard thresholding in which the threshold is chosen adaptively and crucially relies on randomness to escape bad fixed points of the non-convex hard thresholding operation.
Error Bounds and Guidelines for Privacy Calibration in Differentially Private Kalman Filtering
Venue: arXiv cs.SY 2019
Year: 2019

Differential privacy has emerged as a formal framework for protecting sensitive information in control systems. One key feature is that it is immune to post-processing, which means that arbitrary post-hoc computations can be performed on privatized data without weakening differential privacy. It is therefore common to filter private data streams. To characterize this setup, in this paper we present error and entropy bounds for Kalman filtering differentially private state trajectories. We consider systems in which an output trajectory is privatized in order to protect the state trajectory that produced it. We provide bounds on a priori and a posteriori error and differential entropy of a Kalman filter which is processing the privatized output trajectories. Using the error bounds we develop, we then provide guidelines to calibrate privacy levels in order to keep filter error within pre-specified bounds. Simulation results are presented to demonstrate these developments.
A tighter bound on the number of relevant variables in a bounded degree Boolean function
Venue: arXiv cs.DM 2019
Year: 2019

A classical theorem of Nisan and Szegedy says that a boolean function with degree $d$ as a real polynomial depends on at most $d2^{d-1}$ of its variables. In recent work by Chiarelli, Hatami and Saks, this upper bound was improved to $C \cdot 2^d$, where $C = 6.614$. Here we refine their argument to show that one may take $C = 4.416$.
Why Couldn't You do that? Explaining Unsolvability of Classical Planning Problems in the Presence of Plan Advice
Venue: arXiv cs.AI 2019
Year: 2019

Explainable planning is widely accepted as a prerequisite for autonomous agents to successfully work with humans. While there has been a lot of research on generating explanations of solutions to planning problems, explaining the absence of solutions remains an open and under-studied problem, even though such situations can be the hardest to understand or debug. In this paper, we show that hierarchical abstractions can be used to efficiently generate reasons for unsolvability of planning problems. In contrast to related work on computing certificates of unsolvability, we show that these methods can generate compact, human-understandable reasons for unsolvability. Empirical analysis and user studies show the validity of our methods as well as their computational efficacy on a number of benchmark planning domains.
Preprocessing Ambiguous Imprecise Points
Venue: arXiv cs.CG 2019
Year: 2019

Let ${R} = \{R_1, R_2, ..., R_n\}$ be a set of regions and let $ X = \{x_1, x_2, ..., x_n\}$ be an (unknown) point set with $x_i \in R_i$. Region $R_i$ represents the uncertainty region of $x_i$. We consider the following question: how fast can we establish order if we are allowed to preprocess the regions in $R$? The preprocessing model of uncertainty uses two consecutive phases: a preprocessing phase which has access only to ${R}$ followed by a reconstruction phase during which a desired structure on $X$ is computed. Recent results in this model parametrize the reconstruction time by the ply of ${R}$, which is the maximum overlap between the regions in ${R}$. We introduce the ambiguity $A({R})$ as a more fine-grained measure of the degree of overlap in ${R}$. We show how to preprocess a set of $d$-dimensional disks in $O(n \log n)$ time such that we can sort $X$ (if $d=1$) and reconstruct a quadtree on $X$ (if $d\geq 1$ but constant) in $O(A({R}))$ time. If $A({R})$ is sub-linear, then reporting the result dominates the running time of the reconstruction phase. However, we can still return a suitable data structure representing the result in $O(A({R}))$ time. In one dimension, ${R}$ is a set of intervals and the ambiguity is linked to interval entropy, which in turn relates to the well-studied problem of sorting under partial information. The number of comparisons necessary to find the linear order underlying a poset $P$ is lower-bounded by the graph entropy of $P$. We show that if $P$ is an interval order, then the ambiguity provides a constant-factor approximation of the graph entropy. This gives a lower bound of $Ω(A({R}))$ in all dimensions for the reconstruction phase (sorting or any proximity structure), independent of any preprocessing; hence our result is tight.
Note on bounds for symmetric divergence measures
Venue: arXiv cs.IT 2019
Year: 2019

I. Sason obtained the tight bounds for symmetric divergence measures are derived by applying the results established by G. L. Gilardoni. In this article, we are going to report two kinds of extensions for the above results, namely classical q-extension and non-commutative extension.
A Learning Framework for Distribution-Based Game-Theoretic Solution Concepts
Venue: arXiv cs.AI 2019
Year: 2019

The past few years have seen several works on learning economic solutions from data; these include optimal auction design, function optimization, stable payoffs in cooperative games and more. In this work, we provide a unified learning-theoretic methodology for modeling such problems, and establish tools for determining whether a given economic solution concept can be learned from data. Our learning theoretic framework generalizes a notion of function space dimension -- the graph dimension -- adapting it to the solution concept learning domain. We identify sufficient conditions for the PAC learnability of solution concepts, and show that results in existing works can be immediately derived using our methodology. Finally, we apply our methods in other economic domains, yielding a novel notion of PAC competitive equilibrium and PAC Condorcet winners.
Distributed Maximization of Submodular plus Diversity Functions for Multi-label Feature Selection on Huge Datasets
Venue: arXiv cs.LG 2019
Year: 2019

There are many problems in machine learning and data mining which are equivalent to selecting a non-redundant, high "quality" set of objects. Recommender systems, feature selection, and data summarization are among many applications of this. In this paper, we consider this problem as an optimization problem that seeks to maximize the sum of a sum-sum diversity function and a non-negative monotone submodular function. The diversity function addresses the redundancy, and the submodular function controls the predictive quality. We consider the problem in big data settings (in other words, distributed and streaming settings) where the data cannot be stored on a single machine or the process time is too high for a single machine. We show that a greedy algorithm achieves a constant factor approximation of the optimal solution in these settings. Moreover, we formulate the multi-label feature selection problem as such an optimization problem. This formulation combined with our algorithm leads to the first distributed multi-label feature selection method. We compare the performance of this method with centralized multi-label feature selection methods in the literature, and we show that its performance is comparable or in some cases is even better than current centralized multi-label feature selection methods.
Regularize, Expand and Compress: Multi-task based Lifelong Learning via NonExpansive AutoML
Venue: arXiv cs.CV 2019
Year: 2019

Lifelong learning, the problem of continual learning where tasks arrive in sequence, has been lately attracting more attention in the computer vision community. The aim of lifelong learning is to develop a system that can learn new tasks while maintaining the performance on the previously learned tasks. However, there are two obstacles for lifelong learning of deep neural networks: catastrophic forgetting and capacity limitation. To solve the above issues, inspired by the recent breakthroughs in automatically learning good neural network architectures, we develop a Multi-task based lifelong learning via nonexpansive AutoML framework termed Regularize, Expand and Compress (REC). REC is composed of three stages: 1) continually learns the sequential tasks without the learned tasks' data via a newly proposed multi-task weight consolidation (MWC) algorithm; 2) expands the network to help the lifelong learning with potentially improved model capability and performance by network-transformation based AutoML; 3) compresses the expanded model after learning every new task to maintain model efficiency and performance. The proposed MWC and REC algorithms achieve superior performance over other lifelong learning algorithms on four different datasets.
Drawing planar graphs with few segments on a polynomial grid
Venue: arXiv cs.CG 2019
Year: 2019

The visual complexity of a graph drawing can be measured by the number of geometric objects used for the representation of its elements. In this paper, we study planar graph drawings where edges are represented by few segments. In such a drawing, one segment may represent multiple edges forming a path. Drawings of planar graphs with few segments were intensively studied in the past years. However, the area requirements were only considered for limited subclasses of planar graphs. In this paper, we show that trees have drawings with $3n/4-1$ segments and $n^2$ area, improving the previous result of $O(n^{3.58})$. We also show that 3-connected planar graphs and biconnected outerplanar graphs have a drawing with $8n/3-O(1)$ and $3n/2-O(1)$ segments, respectively, and $O(n^3)$ area.