OpenRaiser/Intern-Atlas huggingface dataset:
Tackling Contention Through Cooperation: A Distributed Federation in LoRaWAN Space
Venue: arXiv cs.NI 2020
Year: 2020

Low-Power Wide Area Networks (LPWAN) play a key role in the IoT marketplace wherein LoRaWAN is considered a leading solution. Despite the traction of LoRaWAN, research shows that the current contention management mechanisms of LoRaWAN do not scale. This paper tackles contention on LoRaWAN by introducing FLIP, a fully distributed and open architecture for LoRaWAN that fundamentally rethinks how LoRa gateways should be managed and coordinated. FLIP transforms LoRa gateways into a federated network that provides inherent support for roaming while tackling contention using consensus-driven load balancing. FLIP offers identical security guarantees to LoRaWAN, is compatible with existing gateway hardware and requires no updates to end-device hardware or firmware. These features ensure the practicality of FLIP and provide a path to its adoption. We evaluate the performance of FLIP in a large-scale real-world deployment and demonstrate that FLIP delivers scalable roaming and improved contention management in comparison to LoRaWAN. FLIP achieves these benefits within the resource constraints of conventional LoRa gateways and requires no server hardware.
Secure Network Code for Adaptive and Active Attacks with No-Randomness in Intermediate Nodes
Venue: arXiv cs.IT 2020
Year: 2020

In secure network coding, there is a possibility that the eavesdropper can improve her performance when she changes (contaminates) the information on the attacked edges (active attack) and chooses the attacked edges adaptively (adaptive attack). We analyze the security for network code over such types of attacks. We show that active and adaptive attacks cannot improve the performance of the eavesdropper when the code is linear. Further, we give a non-linear example, in which an adaptive attack improves the performance of the eavesdropper. We derive the capacity for the unicast case and the capacity region for the multicast case or the multiple multicast case in several examples of relay networks, beyond the minimum cut theorem, when no additional random number is allowed as scramble variables in the intermediate nodes. No prior study compared the difference of the capacity and the capacity region between the existence and the non-existence of randomness in the intermediate nodes under these network models even with non-adaptive and non-active attacks.
Efficient modeling of higher-order dependencies in networks: from algorithm to application for anomaly detection
Venue: arXiv cs.SI 2020
Year: 2020

Complex systems, represented as dynamic networks, comprise of components that influence each other via direct and/or indirect interactions. Recent research has shown the importance of using Higher-Order Networks (HONs) for modeling and analyzing such complex systems, as the typical Markovian assumption in developing the First Order Network (FON) can be limiting. This higher-order network representation not only creates a more accurate representation of the underlying complex system, but also leads to more accurate network analysis. In this paper, we first present a scalable and accurate model, BuildHON+, for higher-order network representation of data derived from a complex system with various orders of dependencies. Then, we show that this higher-order network representation modeled by BuildHON+ is significantly more accurate in identifying anomalies than FON, demonstrating a need for the higher-order network representation and modeling of complex systems for deriving meaningful conclusions.
Selective review of offline change point detection methods
Venue: arXiv cs.CE 2020
Year: 2020

This article presents a selective survey of algorithms for the offline detection of multiple change points in multivariate time series. A general yet structuring methodological strategy is adopted to organize this vast body of work. More precisely, detection algorithms considered in this review are characterized by three elements: a cost function, a search method and a constraint on the number of changes. Each of those elements is described, reviewed and discussed separately. Implementations of the main algorithms described in this article are provided within a Python package called ruptures.
ONETS: Online Network Slice Broker From Theory to Practice
Venue: arXiv cs.NI 2020
Year: 2020

Network slicing allows mobile network operators to open their physical network infrastructure platform to the concurrent deployment of multiple logical self-contained networks, i.e., network slices. In this paper we propose and analyze ONETS: an Online NETwork Slicing solution that (i) builds on the budgeted lock-up multi-armed bandit mathematical model and properties, (ii) derives its analytical bounds in our proposed extension for network slicing, (iii) seamlessly integrates into the 3GPP architecture, (iv) proves its feasibility through a proof-of-concept implementation on commercial hardware considering three network slices and (v) allows for the design of a low-complexity online network slice brokering solution that maximizes multiplexing gains.
Efficient Test Collection Construction via Active Learning
Venue: arXiv cs.IR 2020
Year: 2020

To create a new IR test collection at low cost, it is valuable to carefully select which documents merit human relevance judgments. Shared task campaigns such as NIST TREC pool document rankings from many participating systems (and often interactive runs as well) in order to identify the most likely relevant documents for human judging. However, if one's primary goal is merely to build a test collection, it would be useful to be able to do so without needing to run an entire shared task. Toward this end, we investigate multiple active learning strategies which, without reliance on system rankings: 1) select which documents human assessors should judge; and 2) automatically classify the relevance of additional unjudged documents. To assess our approach, we report experiments on five TREC collections with varying scarcity of relevant documents. We report labeling accuracy achieved, as well as rank correlation when evaluating participant systems based upon these labels vs.\ full pool judgments. Results show the effectiveness of our approach, and we further analyze how varying relevance scarcity across collections impacts our findings. To support reproducibility and follow-on work, we have shared our code online: https://github.com/mdmustafizurrahman/ICTIR_AL_TestCollection_2020/.
Intrinsic Dimension of Geometric Data Sets
Venue: arXiv cs.AI 2020
Year: 2020

The curse of dimensionality is a phenomenon frequently observed in machine learning (ML) and knowledge discovery (KD). There is a large body of literature investigating its origin and impact, using methods from mathematics as well as from computer science. Among the mathematical insights into data dimensionality, there is an intimate link between the dimension curse and the phenomenon of measure concentration, which makes the former accessible to methods of geometric analysis. The present work provides a comprehensive study of the intrinsic geometry of a data set, based on Gromov's metric measure geometry and Pestov's axiomatic approach to intrinsic dimension. In detail, we define a concept of geometric data set and introduce a metric as well as a partial order on the set of isomorphism classes of such data sets. Based on these objects, we propose and investigate an axiomatic approach to the intrinsic dimension of geometric data sets and establish a concrete dimension function with the desired properties. Our model for data sets and their intrinsic dimension is computationally feasible and, moreover, adaptable to specific ML/KD-algorithms, as illustrated by various experiments.
Eight Years of Rider Measurement in the Android Malware Ecosystem: Evolution and Lessons Learned
Venue: arXiv cs.CR 2020
Year: 2020

Despite the growing threat posed by Android malware, the research community is still lacking a comprehensive view of common behaviors and trends exposed by malware families active on the platform. Without such view, the researchers incur the risk of developing systems that only detect outdated threats, missing the most recent ones. In this paper, we conduct the largest measurement of Android malware behavior to date, analyzing over 1.2 million malware samples that belong to 1.2K families over a period of eight years (from 2010 to 2017). We aim at understanding how the behavior of Android malware has evolved over time, focusing on repackaging malware. In this type of threats different innocuous apps are piggybacked with a malicious payload (rider), allowing inexpensive malware manufacturing. One of the main challenges posed when studying repackaged malware is slicing the app to split benign components apart from the malicious ones. To address this problem, we use differential analysis to isolate software components that are irrelevant to the campaign and study the behavior of malicious riders alone. Our analysis framework relies on collective repositories and recent advances on the systematization of intelligence extracted from multiple anti-virus vendors. We find that since its infancy in 2010, the Android malware ecosystem has changed significantly, both in the type of malicious activity performed by the malicious samples and in the level of obfuscation used by malware to avoid detection. We then show that our framework can aid analysts who attempt to study unknown malware families. Finally, we discuss what our findings mean for Android malware detection research, highlighting areas that need further attention by the research community.
Phonocardiographic Sensing using Deep Learning for Abnormal Heartbeat Detection
Venue: arXiv cs.CV 2020
Year: 2020

Cardiac auscultation involves expert interpretation of abnormalities in heart sounds using stethoscope. Deep learning based cardiac auscultation is of significant interest to the healthcare community as it can help reducing the burden of manual auscultation with automated detection of abnormal heartbeats. However, the problem of automatic cardiac auscultation is complicated due to the requirement of reliability and high accuracy, and due to the presence of background noise in the heartbeat sound. In this work, we propose a Recurrent Neural Networks (RNNs) based automated cardiac auscultation solution. Our choice of RNNs is motivated by the great success of deep learning in medical applications and by the observation that RNNs represent the deep learning configuration most suitable for dealing with sequential or temporal data even in the presence of noise. We explore the use of various RNN models, and demonstrate that these models deliver the abnormal heartbeat classification score with significant improvement. Our proposed approach using RNNs can be potentially be used for real-time abnormal heartbeat detection in the Internet of Medical Things for remote monitoring applications.
Contextual Bandit with Adaptive Feature Extraction
Venue: arXiv cs.AI 2020
Year: 2020

We consider an online decision making setting known as contextual bandit problem, and propose an approach for improving contextual bandit performance by using an adaptive feature extraction (representation learning) based on online clustering. Our approach starts with an off-line pre-training on unlabeled history of contexts (which can be exploited by our approach, but not by the standard contextual bandit), followed by an online selection and adaptation of encoders. Specifically, given an input sample (context), the proposed approach selects the most appropriate encoding function to extract a feature vector which becomes an input for a contextual bandit, and updates both the bandit and the encoding function based on the context and on the feedback (reward). Our experiments on a variety of datasets, and both in stationary and non-stationary environments of several kinds demonstrate clear advantages of the proposed adaptive representation learning over the standard contextual bandit based on "raw" input contexts.
Cellular Cohomology in Homotopy Type Theory
Venue: arXiv cs.LO 2020
Year: 2020

We present a development of cellular cohomology in homotopy type theory. Cohomology associates to each space a sequence of abelian groups capturing part of its structure, and has the advantage over homotopy groups in that these abelian groups of many common spaces are easier to compute. Cellular cohomology is a special kind of cohomology designed for cell complexes: these are built in stages by attaching spheres of progressively higher dimension, and cellular cohomology defines the groups out of the combinatorial description of how spheres are attached. Our main result is that for finite cell complexes, a wide class of cohomology theories (including the ones defined through Eilenberg-MacLane spaces) can be calculated via cellular cohomology. This result was formalized in the Agda proof assistant.
A Praise for Defensive Programming: Leveraging Uncertainty for Effective Malware Mitigation
Venue: arXiv cs.CR 2020
Year: 2020

A promising avenue for improving the effectiveness of behavioral-based malware detectors would be to combine fast traditional machine learning detectors with high-accuracy, but time-consuming deep learning models. The main idea would be to place software receiving borderline classifications by traditional machine learning methods in an environment where uncertainty is added, while software is analyzed by more time-consuming deep learning models. The goal of uncertainty would be to rate-limit actions of potential malware during the time consuming deep analysis. In this paper, we present a detailed description of the analysis and implementation of CHAMELEON, a framework for realizing this uncertain environment for Linux. CHAMELEON offers two environments for software: (i) standard - for any software identified as benign by conventional machine learning methods and (ii) uncertain - for software receiving borderline classifications when analyzed by these conventional machine learning methods. The uncertain environment adds obstacles to software execution through random perturbations applied probabilistically on selected system calls. We evaluated CHAMELEON with 113 applications and 100 malware samples for Linux. Our results showed that at threshold 10%, intrusive and non-intrusive strategies caused approximately 65% of malware to fail accomplishing their tasks, while approximately 30% of the analyzed benign software to meet with various levels of disruption. With a dynamic, per-system call threshold, CHAMELEON caused 92% of the malware to fail, and only 10% of the benign software to be disrupted. We also found that I/O-bound software was three times more affected by uncertainty than CPU-bound software. Further, we analyzed the logs of software crashed with non-intrusive strategies, and found that some crashes are due to the software bugs.
Generalized Degrees of Freedom of Noncoherent Diamond Networks
Venue: arXiv cs.IT 2020
Year: 2020

We study the generalized degrees of freedom (gDoF) of the block-fading noncoherent diamond (parallel relay) wireless network with asymmetric distributions of link strengths, and a coherence time of T symbol duration. We first derive an outer bound for this channel and then derive the optimal signaling structure for this outer bound. Using the optimal signaling structure we solve the outer bound optimization problem in terms of its gDoF. Using insights from our outer bound signaling solution, we devise an achievability strategy based on a novel scheme that we call train-scale quantize-map-forward (TS-QMF). This uses training in the links from the source to the relays, scaling and quantizing at the relays combined with nontraining-based schemes. We show the optimality of this scheme with respect to the outer bound in terms of the gDoF. In noncoherent point-to-point multiple-input-multiple-output (MIMO) channels, where the fading channel is unknown to transmitter and receiver, an important tradeoff between communication and channel learning was revealed by Zheng and Tse, by demonstrating that not all the available antennas might be used, as it is suboptimal to learn all their channel parameters. Our results in this paper for the diamond network demonstrates that in certain regimes the optimal scheme uses a subnetwork, demonstrating a tradeoff between channel learning and communications. In some regimes, it is gDoF optimal to do relay selection, i.e, use a part of the network. In the other regimes, even when it is essential to use the entire network, it is suboptimal to learn the channel states for all the links in the network, i.e, traditional training-based schemes are suboptimal in these regimes.
TSViz: Demystification of Deep Learning Models for Time-Series Analysis
Venue: arXiv cs.LG 2020
Year: 2020

This paper presents a novel framework for demystification of convolutional deep learning models for time-series analysis. This is a step towards making informed/explainable decisions in the domain of time-series, powered by deep learning. There have been numerous efforts to increase the interpretability of image-centric deep neural network models, where the learned features are more intuitive to visualize. Visualization in time-series domain is much more complicated as there is no direct interpretation of the filters and inputs as compared to the image modality. In addition, little or no concentration has been devoted for the development of such tools in the domain of time-series in the past. TSViz provides possibilities to explore and analyze a network from different dimensions at different levels of abstraction which includes identification of parts of the input that were responsible for a prediction (including per filter saliency), importance of different filters present in the network for a particular prediction, notion of diversity present in the network through filter clustering, understanding of the main sources of variation learnt by the network through inverse optimization, and analysis of the network's robustness against adversarial noise. As a sanity check for the computed influence values, we demonstrate results regarding pruning of neural networks based on the computed influence information. These representations allow to understand the network features so that the acceptability of deep networks for time-series data can be enhanced. This is extremely important in domains like finance, industry 4.0, self-driving cars, health-care, counter-terrorism etc., where reasons for reaching a particular prediction are equally important as the prediction itself. We assess the proposed framework for interpretability with a set of desirable properties essential for any method.
Mean Field Multi-Agent Reinforcement Learning
Venue: arXiv cs.MA 2020
Year: 2020

Existing multi-agent reinforcement learning methods are limited typically to a small number of agents. When the agent number increases largely, the learning becomes intractable due to the curse of the dimensionality and the exponential growth of agent interactions. In this paper, we present \emph{Mean Field Reinforcement Learning} where the interactions within the population of agents are approximated by those between a single agent and the average effect from the overall population or neighboring agents; the interplay between the two entities is mutually reinforced: the learning of the individual agent's optimal policy depends on the dynamics of the population, while the dynamics of the population change according to the collective patterns of the individual policies. We develop practical mean field Q-learning and mean field Actor-Critic algorithms and analyze the convergence of the solution to Nash equilibrium. Experiments on Gaussian squeeze, Ising model, and battle games justify the learning effectiveness of our mean field approaches. In addition, we report the first result to solve the Ising model via model-free reinforcement learning methods.
An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
Venue: arXiv cs.DS 2020
Year: 2020

Betweenness centrality---measuring how many shortest paths pass through a vertex---is one of the most important network analysis concepts for assessing the relative importance of a vertex. The well-known algorithm of Brandes [J. Math. Sociol.~'01] computes, on an $n$-vertex and $m$-edge graph, the betweenness centrality of all vertices in $O(nm)$ worst-case time. In later work, significant empirical speedups were achieved by preprocessing degree-one vertices and by graph partitioning based on cut vertices. We contribute an algorithmic treatment of degree-two vertices, which turns out to be much richer in mathematical structure than the case of degree-one vertices. Based on these three algorithmic ingredients, we provide a strengthened worst-case running time analysis for betweenness centrality algorithms. More specifically, we prove an adaptive running time bound $O(kn)$, where $k < m$ is the size of a minimum feedback edge set of the input graph.
Controlling Human Utilization of Failure-Prone Systems via Taxes
Venue: arXiv cs.GT 2020
Year: 2020

We consider a game-theoretic model where individuals compete over a shared failure-prone system or resource. We investigate the effectiveness of a taxation mechanism in controlling the utilization of the resource at the Nash equilibrium when the decision-makers have behavioral risk preferences, captured by prospect theory. We first observe that heterogeneous prospect-theoretic risk preferences can lead to counter-intuitive outcomes. In particular, for resources that exhibit network effects, utilization can increase under taxation and there may not exist a tax rate that achieves the socially optimal level of utilization. We identify conditions under which utilization is monotone and continuous, and then characterize the range of utilizations that can be achieved by a suitable choice of tax rate. We further show that resource utilization is higher when players are charged differentiated tax rates compared to the case when all players are charged an identical tax rate, under suitable assumptions.
MILE: A Multi-Level Framework for Scalable Graph Embedding
Venue: arXiv cs.AI 2020
Year: 2020

Recently there has been a surge of interest in designing graph embedding methods. Few, if any, can scale to a large-sized graph with millions of nodes due to both computational complexity and memory requirements. In this paper, we relax this limitation by introducing the MultI-Level Embedding (MILE) framework -- a generic methodology allowing contemporary graph embedding methods to scale to large graphs. MILE repeatedly coarsens the graph into smaller ones using a hybrid matching technique to maintain the backbone structure of the graph. It then applies existing embedding methods on the coarsest graph and refines the embeddings to the original graph through a graph convolution neural network that it learns. The proposed MILE framework is agnostic to the underlying graph embedding techniques and can be applied to many existing graph embedding methods without modifying them. We employ our framework on several popular graph embedding techniques and conduct embedding for real-world graphs. Experimental results on five large-scale datasets demonstrate that MILE significantly boosts the speed (order of magnitude) of graph embedding while generating embeddings of better quality, for the task of node classification. MILE can comfortably scale to a graph with 9 million nodes and 40 million edges, on which existing methods run out of memory or take too long to compute on a modern workstation. Our code and data are publicly available with detailed instructions for adding new base embedding methods: \url{https://github.com/jiongqian/MILE}.