OpenRaiser/Intern-Atlas huggingface dataset:
A method for eternally dominating strong grids
Venue: arXiv cs.DM 2020
Year: 2020

In the eternal domination game, an attacker attacks a vertex at each turn and a team of guards must move a guard to the attacked vertex to defend it. The guards may only move to adjacent vertices and no more than one guard may occupy a vertex. The goal is to determine the eternal domination number of a graph which is the minimum number of guards required to defend the graph against an infinite sequence of attacks. In this paper, we continue the study of the eternal domination game on strong grids. Cartesian grids have been vastly studied with tight bounds for small grids such as $2\times n$, $3\times n$, $4\times n$, and $5\times n$ grids, and recently it was proven in [Lamprou et al., CIAC 2017, 393-404] that the eternal domination number of these grids in general is within $O(m+n)$ of their domination number which lower bounds the eternal domination number. Recently, Finbow et al. proved that the eternal domination number of strong grids is upper bounded by $\frac{mn}{6}+O(m+n)$. We adapt the techniques of [Lamprou et al., CIAC 2017, 393-404] to prove that the eternal domination number of strong grids is upper bounded by $\frac{mn}{7}+O(m+n)$. While this does not improve upon a recently announced bound of $\lceil\frac{m}{3}\rceil \lceil\frac{n}{3}\rceil+O(m\sqrt{n})$ [Mc Inerney, Nisse, Pérennes, CIAC 2019] in the general case, we show that our bound is an improvement in the case where the smaller of the two dimensions is at most $6179$.
Graph Representation Learning for Merchant Incentive Optimization in Mobile Payment Marketing
Venue: arXiv cs.SI 2020
Year: 2020

Mobile payment such as Alipay has been widely used in our daily lives. To further promote the mobile payment activities, it is important to run marketing campaigns under a limited budget by providing incentives such as coupons, commissions to merchants. As a result, incentive optimization is the key to maximizing the commercial objective of the marketing campaign. With the analyses of online experiments, we found that the transaction network can subtly describe the similarity of merchants' responses to different incentives, which is of great use in the incentive optimization problem. In this paper, we present a graph representation learning method atop of transaction networks for merchant incentive optimization in mobile payment marketing. With limited samples collected from online experiments, our end-to-end method first learns merchant representations based on an attributed transaction networks, then effectively models the correlations between the commercial objectives each merchant may achieve and the incentives under varying treatments. Thus we are able to model the sensitivity to incentive for each merchant, and spend the most budgets on those merchants that show strong sensitivities in the marketing campaign. Extensive offline and online experimental results at Alipay demonstrate the effectiveness of our proposed approach.
Fast Gunrock Subgraph Matching (GSM) on GPUs
Venue: arXiv cs.DC 2020
Year: 2020

In this paper, we propose a GPU-efficient subgraph isomorphism algorithm using the Gunrock graph analytic framework, GSM (Gunrock Subgraph Matching), to compute graph matching on GPUs. In contrast to previous approaches on the CPU which are based on depth-first traversal, GSM is BFS-based: possible matches are explored simultaneously in a breadth-first strategy. The advantage of using BFS-based traversal is that we can leverage the massively parallel processing capabilities of the GPU. The disadvantage is the generation of more intermediate results. We propose several optimization techniques to cope with the problem. Our implementation follows a filtering-and-verification strategy. While most previous work on GPUs requires one-/two-step joining, we use one-step verification to decide the candidates in current frontier of nodes. Our implementation has a speedup up to 4x over previous GPU state-of-the-art implementation.
On the Effectiveness of Virtual Reality-based Training for Robotic Setup
Venue: arXiv cs.RO 2020
Year: 2020

Virtual Reality (VR) is rapidly increasing in popularity as a teaching tool. It allows for the creation of a highly immersive, three-dimensional virtual environment intended to simulate real-life environments. With more robots saturating the industry - from manufacturing to healthcare, there is a need to train end-users on how to set up, operate, tear down, and troubleshoot the robot. Even though VR has become widely used in training surgeons on the psychomotor skills associated with operating the robot, little research has been done to see how the benefits of VR could translate to teaching the bedside staff, tasked with supporting the robot during the full end-to-end surgical procedure. We trained 30 participants on how to set up a robotic arm in an environment mimicking clinical setup. We divided these participants equally into 3 groups with one group trained with paper-based instructions, one with video-based instructions and one with VR-based instructions. We then compared and contrasted these three different training methods. VR and paper-based were highly favored training mediums over video-based. VR-trained participants achieved slightly higher fidelity of individual robotic joint angles, suggesting better comprehension of the spatial awareness skills necessary to achieve desired arm positioning. In addition, VR resulted in higher reproducibility of setup fidelity and more consistency in user confidence levels as compared to paper and video-based training.
Direct Product Primality Testing of Graphs is GI-hard
Venue: arXiv cs.CC 2020
Year: 2020

We investigate the computational complexity of the graph primality testing problem with respect to the direct product (also known as Kronecker, cardinal or tensor product). In [1] Imrich proves that both primality testing and a unique prime factorization can be determined in polynomial time for (finite) connected and nonbipartite graphs. The author states as an open problem how results on the direct product of nonbipartite, connected graphs extend to bipartite connected graphs and to disconnected ones. In this paper we partially answer this question by proving that the graph isomorphism problem is polynomial-time many-one reducible to the graph compositeness testing problem (the complement of the graph primality testing problem). As a consequence of this result, we prove that the graph isomorphism problem is polynomial-time Turing reducible to the primality testing problem. Our results show that connectedness plays a crucial role in determining the computational complexity of the graph primality testing problem.
Analyzing Accuracy Loss in Randomized Smoothing Defenses
Venue: arXiv cs.LG 2020
Year: 2020

Recent advances in machine learning (ML) algorithms, especially deep neural networks (DNNs), have demonstrated remarkable success (sometimes exceeding human-level performance) on several tasks, including face and speech recognition. However, ML algorithms are vulnerable to \emph{adversarial attacks}, such test-time, training-time, and backdoor attacks. In test-time attacks an adversary crafts adversarial examples, which are specially crafted perturbations imperceptible to humans which, when added to an input example, force a machine learning model to misclassify the given input example. Adversarial examples are a concern when deploying ML algorithms in critical contexts, such as information security and autonomous driving. Researchers have responded with a plethora of defenses. One promising defense is \emph{randomized smoothing} in which a classifier's prediction is smoothed by adding random noise to the input example we wish to classify. In this paper, we theoretically and empirically explore randomized smoothing. We investigate the effect of randomized smoothing on the feasible hypotheses space, and show that for some noise levels the set of hypotheses which are feasible shrinks due to smoothing, giving one reason why the natural accuracy drops after smoothing. To perform our analysis, we introduce a model for randomized smoothing which abstracts away specifics, such as the exact distribution of the noise. We complement our theoretical results with extensive experiments.
VQ-DRAW: A Sequential Discrete VAE
Venue: arXiv cs.LG 2020
Year: 2020

In this paper, I present VQ-DRAW, an algorithm for learning compact discrete representations of data. VQ-DRAW leverages a vector quantization effect to adapt the sequential generation scheme of DRAW to discrete latent variables. I show that VQ-DRAW can effectively learn to compress images from a variety of common datasets, as well as generate realistic samples from these datasets with no help from an autoregressive prior.
Self-Supervised Graph Representation Learning via Global Context Prediction
Venue: arXiv cs.LG 2020
Year: 2020

To take full advantage of fast-growing unlabeled networked data, this paper introduces a novel self-supervised strategy for graph representation learning by exploiting natural supervision provided by the data itself. Inspired by human social behavior, we assume that the global context of each node is composed of all nodes in the graph since two arbitrary entities in a connected network could interact with each other via paths of varying length. Based on this, we investigate whether the global context can be a source of free and effective supervisory signals for learning useful node representations. Specifically, we randomly select pairs of nodes in a graph and train a well-designed neural net to predict the contextual position of one node relative to the other. Our underlying hypothesis is that the representations learned from such within-graph context would capture the global topology of the graph and finely characterize the similarity and differentiation between nodes, which is conducive to various downstream learning tasks. Extensive benchmark experiments including node classification, clustering, and link prediction demonstrate that our approach outperforms many state-of-the-art unsupervised methods and sometimes even exceeds the performance of supervised counterparts.
Deep Multi-Modal Sets
Venue: arXiv cs.CV 2020
Year: 2020

Many vision-related tasks benefit from reasoning over multiple modalities to leverage complementary views of data in an attempt to learn robust embedding spaces. Most deep learning-based methods rely on a late fusion technique whereby multiple feature types are encoded and concatenated and then a multi layer perceptron (MLP) combines the fused embedding to make predictions. This has several limitations, such as an unnatural enforcement that all features be present at all times as well as constraining only a constant number of occurrences of a feature modality at any given time. Furthermore, as more modalities are added, the concatenated embedding grows. To mitigate this, we propose Deep Multi-Modal Sets: a technique that represents a collection of features as an unordered set rather than one long ever-growing fixed-size vector. The set is constructed so that we have invariance both to permutations of the feature modalities as well as to the cardinality of the set. We will also show that with particular choices in our model architecture, we can yield interpretable feature performance such that during inference time we can observe which modalities are most contributing to the prediction.With this in mind, we demonstrate a scalable, multi-modal framework that reasons over different modalities to learn various types of tasks. We demonstrate new state-of-the-art performance on two multi-modal datasets (Ads-Parallelity [34] and MM-IMDb [1]).
A Survey on Big Data for Network Traffic Monitoring and Analysis
Venue: arXiv cs.DC 2020
Year: 2020

Network Traffic Monitoring and Analysis (NTMA) represents a key component for network management, especially to guarantee the correct operation of large-scale networks such as the Internet. As the complexity of Internet services and the volume of traffic continue to increase, it becomes difficult to design scalable NTMA applications. Applications such as traffic classification and policing require real-time and scalable approaches. Anomaly detection and security mechanisms require to quickly identify and react to unpredictable events while processing millions of heterogeneous events. At last, the system has to collect, store, and process massive sets of historical data for post-mortem analysis. Those are precisely the challenges faced by general big data approaches: Volume, Velocity, Variety, and Veracity. This survey brings together NTMA and big data. We catalog previous work on NTMA that adopt big data approaches to understand to what extent the potential of big data is being explored in NTMA. This survey mainly focuses on approaches and technologies to manage the big NTMA data, additionally briefly discussing big data analytics (e.g., machine learning) for the sake of NTMA. Finally, we provide guidelines for future work, discussing lessons learned, and research directions.
EXPLAIN-IT: Towards Explainable AI for Unsupervised Network Traffic Analysis
Venue: arXiv cs.AI 2020
Year: 2020

The application of unsupervised learning approaches, and in particular of clustering techniques, represents a powerful exploration means for the analysis of network measurements. Discovering underlying data characteristics, grouping similar measurements together, and identifying eventual patterns of interest are some of the applications which can be tackled through clustering. Being unsupervised, clustering does not always provide precise and clear insight into the produced output, especially when the input data structure and distribution are complex and difficult to grasp. In this paper we introduce EXPLAIN-IT, a methodology which deals with unlabeled data, creates meaningful clusters, and suggests an explanation to the clustering results for the end-user. EXPLAIN-IT relies on a novel explainable Artificial Intelligence (AI) approach, which allows to understand the reasons leading to a particular decision of a supervised learning-based model, additionally extending its application to the unsupervised learning domain. We apply EXPLAIN-IT to the problem of YouTube video quality classification under encrypted traffic scenarios, showing promising results.
Sealing Pointer-Based Optimizations Behind Pure Functions
Venue: arXiv cs.PL 2020
Year: 2020

Functional programming languages are particularly well-suited for building automated reasoning systems, since (among other reasons) a logical term is well modeled by an inductive type, traversing a term can be implemented generically as a higher-order combinator, and backtracking is dramatically simplified by persistent datastructures. However, existing pure functional programming languages all suffer a major limitation in these domains: traversing a term requires time proportional to the tree size of the term as opposed to its graph size. This limitation would be particularly devastating when building automation for interactive theorem provers such as Lean and Coq, for which the exponential blowup of term-tree sizes has proved to be both common and difficult to prevent. All that is needed to recover the optimal scaling is the ability to perform simple operations on the memory addresses of terms, and yet allowing these operations to be used freely would clearly violate the basic premise of referential transparency. We show how to use dependent types to seal the necessary pointer-address manipulations behind pure functional interfaces while requiring only a negligible amount of additional trust. We have implemented our approach for the upcoming version (v4) of Lean, and our approach could be adopted by other languages based on dependent type theory as well.
Image-based OoD-Detector Principles on Graph-based Input Data in Human Action Recognition
Venue: arXiv cs.CV 2020
Year: 2020

Living in a complex world like ours makes it unacceptable that a practical implementation of a machine learning system assumes a closed world. Therefore, it is necessary for such a learning-based system in a real world environment, to be aware of its own capabilities and limits and to be able to distinguish between confident and unconfident results of the inference, especially if the sample cannot be explained by the underlying distribution. This knowledge is particularly essential in safety-critical environments and tasks e.g. self-driving cars or medical applications. Towards this end, we transfer image-based Out-of-Distribution (OoD)-methods to graph-based data and show the applicability in action recognition. The contribution of this work is (i) the examination of the portability of recent image-based OoD-detectors for graph-based input data, (ii) a Metric Learning-based approach to detect OoD-samples, and (iii) the introduction of a novel semi-synthetic action recognition dataset. The evaluation shows that image-based OoD-methods can be applied to graph-based data. Additionally, there is a gap between the performance on intraclass and intradataset results. First methods as the examined baseline or ODIN provide reasonable results. More sophisticated network architectures - in contrast to their image-based application - were surpassed in the intradataset comparison and even lead to less classification accuracy.
Security of Deep Learning based Lane Keeping System under Physical-World Adversarial Attack
Venue: arXiv cs.CR 2020
Year: 2020

Lane-Keeping Assistance System (LKAS) is convenient and widely available today, but also extremely security and safety critical. In this work, we design and implement the first systematic approach to attack real-world DNN-based LKASes. We identify dirty road patches as a novel and domain-specific threat model for practicality and stealthiness. We formulate the attack as an optimization problem, and address the challenge from the inter-dependencies among attacks on consecutive camera frames. We evaluate our approach on a state-of-the-art LKAS and our preliminary results show that our attack can successfully cause it to drive off lane boundaries within as short as 1.3 seconds.
Building a larger class of graphs for efficient reconfiguration of vertex colouring
Venue: arXiv cs.DM 2020
Year: 2020

A $k$-colouring of a graph $G$ is an assignment of at most $k$ colours to the vertices of $G$ so that adjacent vertices are assigned different colours. The reconfiguration graph of the $k$-colourings, $\mathcal{R}_k(G)$, is the graph whose vertices are the $k$-colourings of $G$ and two colourings are joined by an edge in $\mathcal{R}_k(G)$ if they differ in colour on exactly one vertex. For a $k$-colourable graph $G$, we investigate the connectivity and diameter of $\mathcal{R}_{k+1}(G)$. It is known that not all weakly chordal graphs have the property that $\mathcal{R}_{k+1}(G)$ is connected. On the other hand, $\mathcal{R}_{k+1}(G)$ is connected and of diameter $O(n^2)$ for several subclasses of weakly chordal graphs such as chordal, chordal bipartite, and $P_4$-free graphs. We introduce a new class of graphs called OAT graphs that extends the latter classes and in fact extends outside the class of weakly chordal graphs. OAT graphs are built from four simple operations, disjoint union, join, and the addition of a clique or comparable vertex. We prove that if $G$ is a $k$-colourable OAT graph then $\mathcal{R}_{k+1}(G)$ is connected with diameter $O(n^2)$. Furthermore, we give polynomial time algorithms to recognize OAT graphs and to find a path between any two colourings in $\mathcal{R}_{k+1}(G)$.
Dependency-Aware Release Planning for Software Projects using Fuzzy Graphs and Integer Programming
Venue: arXiv cs.SE 2020
Year: 2020

Software Release Planning (SRP) is to find, for the software, a subset of the requirements with the highest value while respecting the budget. The value of a requirement however may, to various degrees, depend on selecting or ignoring other requirements. However, existing SRP models ignore either Value-Related Dependencies altogether or the strengths of those dependencies even if they consider them. This paper presents an Integer Programming model for software release planning, which considers the variances of strengths of positive and negative value-related dependencies among software requirements. To capture the imprecision associated with strengths of value-related dependencies we have made use of the algebraic structure of fuzzy graphs. We have further, contributed a scalable technique for automated identification of value-related dependencies based on user preferences for software requirements. The validity of the work is verified through simulations.
Scaling MAP-Elites to Deep Neuroevolution
Venue: arXiv cs.NE 2020
Year: 2020

Quality-Diversity (QD) algorithms, and MAP-Elites (ME) in particular, have proven very useful for a broad range of applications including enabling real robots to recover quickly from joint damage, solving strongly deceptive maze tasks or evolving robot morphologies to discover new gaits. However, present implementations of MAP-Elites and other QD algorithms seem to be limited to low-dimensional controllers with far fewer parameters than modern deep neural network models. In this paper, we propose to leverage the efficiency of Evolution Strategies (ES) to scale MAP-Elites to high-dimensional controllers parameterized by large neural networks. We design and evaluate a new hybrid algorithm called MAP-Elites with Evolution Strategies (ME-ES) for post-damage recovery in a difficult high-dimensional control task where traditional ME fails. Additionally, we show that ME-ES performs efficient exploration, on par with state-of-the-art exploration algorithms in high-dimensional control tasks with strongly deceptive rewards.
IsoRAN: Isolation and Scaling for 5G RANvia User-Level Data Plane Virtualization
Venue: arXiv cs.NI 2020
Year: 2020

5G presents a unique set of challenges for cellular network architecture. The architecture needs to be versatile in order to handle a variety of use cases. While network slicing has been proposed as a way to provide such versatility, it is also important to ensure that slices do not adversely interfere with each other. In other words, isolation among network slices is needed. Additionally, the large number of use cases also implies a large number of users, making it imperative that 5G architectures scale efficiently. In this paper we propose IsoRAN, which provides isolation and scaling along with the flexibility needed for 5G architecture. In IsoRAN, users are processed by daemon threads in the Cloud Radio Access Network (CRAN) architecture. Our design allows users from different use cases to be executed, in a distributed manner, on the most efficient hardware to ensure that the Service Level Agreements (SLAs) are met while minimising power consumption. Our experiments show that IsoRAN handles users with different SLA while providing isolation to reduce interference. This increased isolation reduces the drop rate for different users from 42% to nearly 0% in some cases. Finally, we run large scale simulations on real traces to show the benefits for power consumption and cost reduction scale while increasing the number of base stations.