OpenRaiser/Intern-Atlas huggingface dataset:
Natural Graph Networks
Venue: arXiv cs.LG 2020
Year: 2020

A key requirement for graph neural networks is that they must process a graph in a way that does not depend on how the graph is described. Traditionally this has been taken to mean that a graph network must be equivariant to node permutations. Here we show that instead of equivariance, the more general concept of naturality is sufficient for a graph network to be well-defined, opening up a larger class of graph networks. We define global and local natural graph networks, the latter of which are as scalable as conventional message passing graph neural networks while being more flexible. We give one practical instantiation of a natural network on graphs which uses an equivariant message network parameterization, yielding good performance on several benchmarks.
Shortest Watchman Tours in Simple Polygons under Rotated Monotone Visibility
Venue: arXiv cs.CG 2020
Year: 2020

We present an $O(nrG)$ time algorithm for computing and maintaining a minimum length shortest watchman tour that sees a simple polygon under monotone visibility in direction $θ$, while $θ$ varies in $[0,180^{\circ})$, obtaining the directions for the tour to be the shortest one over all tours, where $n$ is the number of vertices, $r$ is the number of reflex vertices, and $G\leq r$ is the maximum number of gates of the polygon used at any time in the algorithm.
Automatic Detection of Cue Points for DJ Mixing
Venue: arXiv cs.SD 2020
Year: 2020

The automatic identification of cue points is a central task in applications as diverse as music thumbnailing, mash-ups generation, and DJ mixing. Our focus lies in electronic dance music and in specific cue points, the "switch points", that make it possible to automatically construct transitions among tracks, mimicking what professional DJs do. We present an approach for the detection of switch points that embody a few general rules we established from interviews with professional DJs; the implementation of these rules is based on features extraction and novelty analysis. The quality of the generated switch points is assessed both by comparing them with a manually annotated dataset that we curated, and by evaluating them individually. We found that about 96\% of the points generated by our methodology are of good quality for use in a DJ mix.
Accessible Computer Science for K-12 Students with Hearing Impairments
Venue: arXiv cs.HC 2020
Year: 2020

An inclusive science, technology, engineering and mathematics (STEM) workforce is needed to maintain America's leadership in the scientific enterprise. Increasing the participation of underrepresented groups in STEM, including persons with disabilities, requires national attention to fully engage the nation's citizens in transforming its STEM enterprise. To address this need, a number of initiatives, such as AccessCSforALL, Bootstrap, and CSforAll, are making efforts to make Computer Science inclusive to the 7.4 million K-12 students with disabilities in the U.S. Of special interest to our project are those K-12 students with hearing impairments. American Sign Language (ASL) is the primary means of communication for an estimated 500,000 people in the United States, yet there are limited online resources providing Computer Science instruction in ASL. This paper introduces a new project designed to support Deaf and Hard of Hearing (DHH) K-12 students and sign interpreters in acquiring knowledge of complex Computer Science concepts. We discuss the motivation for the project and an early design of the accessible block-based Computer Science curriculum to engage DHH students in hands-on computing education.
SketchGraphs: A Large-Scale Dataset for Modeling Relational Geometry in Computer-Aided Design
Venue: arXiv cs.LG 2020
Year: 2020

Parametric computer-aided design (CAD) is the dominant paradigm in mechanical engineering for physical design. Distinguished by relational geometry, parametric CAD models begin as two-dimensional sketches consisting of geometric primitives (e.g., line segments, arcs) and explicit constraints between them (e.g., coincidence, perpendicularity) that form the basis for three-dimensional construction operations. Training machine learning models to reason about and synthesize parametric CAD designs has the potential to reduce design time and enable new design workflows. Additionally, parametric CAD designs can be viewed as instances of constraint programming and they offer a well-scoped test bed for exploring ideas in program synthesis and induction. To facilitate this research, we introduce SketchGraphs, a collection of 15 million sketches extracted from real-world CAD models coupled with an open-source data processing pipeline. Each sketch is represented as a geometric constraint graph where edges denote designer-imposed geometric relationships between primitives, the nodes of the graph. We demonstrate and establish benchmarks for two use cases of the dataset: generative modeling of sketches and conditional generation of likely constraints given unconstrained geometry.
FTRANS: Energy-Efficient Acceleration of Transformers using FPGA
Venue: arXiv cs.DC 2020
Year: 2020

In natural language processing (NLP), the "Transformer" architecture was proposed as the first transduction model replying entirely on self-attention mechanisms without using sequence-aligned recurrent neural networks (RNNs) or convolution, and it achieved significant improvements for sequence to sequence tasks. The introduced intensive computation and storage of these pre-trained language representations has impeded their popularity into computation and memory-constrained devices. The field-programmable gate array (FPGA) is widely used to accelerate deep learning algorithms for its high parallelism and low latency. However, the trained models are still too large to accommodate to an FPGA fabric. In this paper, we propose an efficient acceleration framework, Ftrans, for transformer-based large scale language representations. Our framework includes enhanced block-circulant matrix (BCM)-based weight representation to enable model compression on large-scale language representations at the algorithm level with few accuracy degradation, and an acceleration design at the architecture level. Experimental results show that our proposed framework significantly reduces the model size of NLP models by up to 16 times. Our FPGA design achieves 27.07x and 81x improvement in performance and energy efficiency compared to CPU, and up to 8.80x improvement in energy efficiency compared to GPU.
Polyhedral value iteration for discounted games and energy games
Venue: arXiv cs.DS 2020
Year: 2020

We present a deterministic algorithm, solving discounted games with $n$ nodes in $n^{O(1)}\cdot (2 + \sqrt{2})^n$-time. For bipartite discounted games our algorithm runs in $n^{O(1)}\cdot 2^n$-time. Prior to our work no deterministic algorithm running in time $2^{o(n\log n)}$ regardless of the discount factor was known. We call our approach polyhedral value iteration. We rely on a well-known fact that the values of a discounted game can be found from the so-called optimality equations. In the algorithm we consider a polyhedron obtained by relaxing optimality equations. We iterate points on the border of this polyhedron by moving each time along a carefully chosen shift as far as possible. This continues until the current point satisfies optimality equations. Our approach is heavily inspired by a recent algorithm of Dorfman et al. (ICALP 2019) for energy games. For completeness, we present their algorithm in terms of polyhedral value iteration. Our exposition, unlike the original algorithm, does not require edge weights to be integers and works for arbitrary real weights.
The Monte Carlo Transformer: a stochastic self-attention model for sequence prediction
Venue: arXiv cs.LG 2020
Year: 2020

This paper introduces the Sequential Monte Carlo Transformer, an original approach that naturally captures the observations distribution in a transformer architecture. The keys, queries, values and attention vectors of the network are considered as the unobserved stochastic states of its hidden structure. This generative model is such that at each time step the received observation is a random function of its past states in a given attention window. In this general state-space setting, we use Sequential Monte Carlo methods to approximate the posterior distributions of the states given the observations, and to estimate the gradient of the log-likelihood. We hence propose a generative model giving a predictive distribution, instead of a single-point estimate.
Dagger: Towards Efficient RPCs in Cloud Microservices with Near-Memory Reconfigurable NICs
Venue: arXiv cs.AR 2020
Year: 2020

Cloud applications are increasingly relying on hundreds of loosely-coupled microservices to complete user requests that meet an applications end-to-end QoS requirements. Communication time between services accounts for a large fraction of the end-to-end latency and can introduce performance unpredictability and QoS violations. This work presents our early work on Dagger, a hardware acceleration platform for networking, designed specifically with the unique qualities of microservices in mind. The Dagger architecture relies on an FPGA-based NIC, closely coupled with the processor over a configurable memory interconnect, designed to offload and accelerate RPC stacks. Unlike the traditional cloud systems that use PCIe links as the NIC I/O interface, we leverage memory-interconnected FPGAs as networking devices to provide the efficiency, transparency, and programmability needed for fine-grained microservices. We show that this considerably improves CPU utilization and performance for cloud RPCs.
TUDataset: A collection of benchmark datasets for learning with graphs
Venue: arXiv cs.LG 2020
Year: 2020

Recently, there has been an increasing interest in (supervised) learning with graph data, especially using graph neural networks. However, the development of meaningful benchmark datasets and standardized evaluation procedures is lagging, consequently hindering advancements in this area. To address this, we introduce the TUDataset for graph classification and regression. The collection consists of over 120 datasets of varying sizes from a wide range of applications. We provide Python-based data loaders, kernel and graph neural network baseline implementations, and evaluation tools. Here, we give an overview of the datasets, standardized evaluation procedures, and provide baseline experiments. All datasets are available at www.graphlearning.io. The experiments are fully reproducible from the code available at www.github.com/chrsmrrs/tudataset.
Conservative AI and social inequality: Conceptualizing alternatives to bias through social theory
Venue: arXiv cs.CY 2020
Year: 2020

In response to calls for greater interdisciplinary involvement from the social sciences and humanities in the development, governance, and study of artificial intelligence systems, this paper presents one sociologist's view on the problem of algorithmic bias and the reproduction of societal bias. Discussions of bias in AI cover much of the same conceptual terrain that sociologists studying inequality have long understood using more specific terms and theories. Concerns over reproducing societal bias should be informed by an understanding of the ways that inequality is continually reproduced in society -- processes that AI systems are either complicit in, or can be designed to disrupt and counter. The contrast presented here is between conservative and radical approaches to AI, with conservatism referring to dominant tendencies that reproduce and strengthen the status quo, while radical approaches work to disrupt systemic forms of inequality. The limitations of conservative approaches to class, gender, and racial bias are discussed as specific examples, along with the social structures and processes that biases in these areas are linked to. Societal issues can no longer be out of scope for AI and machine learning, given the impact of these systems on human lives. This requires engagement with a growing body of critical AI scholarship that goes beyond biased data to analyze structured ways of perpetuating inequality, opening up the possibility for radical alternatives.
Toward Forgetting-Sensitive Referring Expression Generationfor Integrated Robot Architectures
Venue: arXiv cs.AI 2020
Year: 2020

To engage in human-like dialogue, robots require the ability to describe the objects, locations, and people in their environment, a capability known as "Referring Expression Generation." As speakers repeatedly refer to similar objects, they tend to re-use properties from previous descriptions, in part to help the listener, and in part due to cognitive availability of those properties in working memory (WM). Because different theories of working memory "forgetting" necessarily lead to differences in cognitive availability, we hypothesize that they will similarly result in generation of different referring expressions. To design effective intelligent agents, it is thus necessary to determine how different models of forgetting may be differentially effective at producing natural human-like referring expressions. In this work, we computationalize two candidate models of working memory forgetting within a robot cognitive architecture, and demonstrate how they lead to cognitive availability-based differences in generated referring expressions.
Maximum-Likelihood Channel Decoding with Quantum Annealing Machine
Venue: arXiv cs.IT 2020
Year: 2020

We formulate maximum likelihood (ML) channel decoding as a quadratic unconstraint binary optimization (QUBO) and simulate the decoding by the current commercial quantum annealing machine, D-Wave 2000Q. We prepared two implementations with Ising model formulations, generated from the generator matrix and the parity-check matrix respectively. We evaluated these implementations of ML decoding for low-density parity-check (LDPC) codes, analyzing the number of spins and connections and comparing the decoding performance with belief propagation (BP) decoding and brute-force ML decoding with classical computers. The results show that these implementations are superior to BP decoding in relatively short length codes, and while the performance in the long length codes deteriorates, the implementation from the parity-check matrix formulation still works up to 1k length with fewer spins and connections than that of the generator matrix formulation due to the sparseness of parity-check matrices of LDPC.
DACS: Domain Adaptation via Cross-domain Mixed Sampling
Venue: arXiv cs.CV 2020
Year: 2020

Semantic segmentation models based on convolutional neural networks have recently displayed remarkable performance for a multitude of applications. However, these models typically do not generalize well when applied on new domains, especially when going from synthetic to real data. In this paper we address the problem of unsupervised domain adaptation (UDA), which attempts to train on labelled data from one domain (source domain), and simultaneously learn from unlabelled data in the domain of interest (target domain). Existing methods have seen success by training on pseudo-labels for these unlabelled images. Multiple techniques have been proposed to mitigate low-quality pseudo-labels arising from the domain shift, with varying degrees of success. We propose DACS: Domain Adaptation via Cross-domain mixed Sampling, which mixes images from the two domains along with the corresponding labels and pseudo-labels. These mixed samples are then trained on, in addition to the labelled data itself. We demonstrate the effectiveness of our solution by achieving state-of-the-art results for GTA5 to Cityscapes, a common synthetic-to-real semantic segmentation benchmark for UDA.
Understanding and Diagnosing Vulnerability under Adversarial Attacks
Venue: arXiv cs.CV 2020
Year: 2020

Deep Neural Networks (DNNs) are known to be vulnerable to adversarial attacks. Currently, there is no clear insight into how slight perturbations cause such a large difference in classification results and how we can design a more robust model architecture. In this work, we propose a novel interpretability method, InterpretGAN, to generate explanations for features used for classification in latent variables. Interpreting the classification process of adversarial examples exposes how adversarial perturbations influence features layer by layer as well as which features are modified by perturbations. Moreover, we design the first diagnostic method to quantify the vulnerability contributed by each layer, which can be used to identify vulnerable parts of model architectures. The diagnostic results show that the layers introducing more information loss tend to be more vulnerable than other layers. Based on the findings, our evaluation results on MNIST and CIFAR10 datasets suggest that average pooling layers, with lower information loss, are more robust than max pooling layers for the network architectures studied in this paper.
Leveraging both Lesion Features and Procedural Bias in Neuroimaging: An Dual-Task Split dynamics of inverse scale space
Venue: arXiv cs.CV 2020
Year: 2020

The prediction and selection of lesion features are two important tasks in voxel-based neuroimage analysis. Existing multivariate learning models take two tasks equivalently and optimize simultaneously. However, in addition to lesion features, we observe that there is another type of feature, which is commonly introduced during the procedure of preprocessing steps, which can improve the prediction result. We call such a type of feature as procedural bias. Therefore, in this paper, we propose that the features/voxels in neuroimage data are consist of three orthogonal parts: lesion features, procedural bias, and null features. To stably select lesion features and leverage procedural bias into prediction, we propose an iterative algorithm (termed GSplit LBI) as a discretization of differential inclusion of inverse scale space, which is the combination of Variable Splitting scheme and Linearized Bregman Iteration (LBI). Specifically, with a variable the splitting term, two estimators are introduced and split apart, i.e. one is for feature selection (the sparse estimator) and the other is for prediction (the dense estimator). Implemented with Linearized Bregman Iteration (LBI), the solution path of both estimators can be returned with different sparsity levels on the sparse estimator for the selection of lesion features. Besides, the dense the estimator can additionally leverage procedural bias to further improve prediction results. To test the efficacy of our method, we conduct experiments on the simulated study and Alzheimer's Disease Neuroimaging Initiative (ADNI) database. The validity and the benefit of our model can be shown by the improvement of prediction results and the interpretability of visualized procedural bias and lesion features.
INDRA: Intrusion Detection using Recurrent Autoencoders in Automotive Embedded Systems
Venue: arXiv cs.CR 2020
Year: 2020

Today's vehicles are complex distributed embedded systems that are increasingly being connected to various external systems. Unfortunately, this increased connectivity makes the vehicles vulnerable to security attacks that can be catastrophic. In this work, we present a novel Intrusion Detection System (IDS) called INDRA that utilizes a Gated Recurrent Unit (GRU) based recurrent autoencoder to detect anomalies in Controller Area Network (CAN) bus-based automotive embedded systems. We evaluate our proposed framework under different attack scenarios and also compare it with the best known prior works in this area.
Security, Availability, and Multiple Information Sources: Exploring Update Behavior of System Administrators
Venue: arXiv cs.HC 2020
Year: 2020

Experts agree that keeping systems up to date is a powerful security measure. Previous work found that users sometimes explicitly refrain from performing timely updates, e.g., due to bad experiences which has a negative impact on end-user security. Another important user group has been investigated less extensively: system administrators, who are responsible for keeping complex and heterogeneous system landscapes available and secure. In this paper, we sought to understand administrators' behavior, experiences, and attitudes regarding updates in a corporate environment. Based on the results of an interview study, we developed an online survey and quantified common practices and obstacles (e.g., downtime or lack of information about updates). The findings indicate that even experienced administrators struggle with update processes as the consequences of an update are sometimes hard to assess. Therefore, we argue that more usable monitoring and update processes are essential to guarantee IT security at scale.
Constraint-Based Software Diversification for Efficient Mitigation of Code-Reuse Attacks
Venue: arXiv cs.CR 2020
Year: 2020

Modern software deployment process produces software that is uniform, and hence vulnerable to large-scale code-reuse attacks. Compiler-based diversification improves the resilience and security of software systems by automatically generating different assembly code versions of a given program. Existing techniques are efficient but do not have a precise control over the quality of the generated code variants. This paper introduces Diversity by Construction (DivCon), a constraint-based compiler approach to software diversification. Unlike previous approaches, DivCon allows users to control and adjust the conflicting goals of diversity and code quality. A key enabler is the use of Large Neighborhood Search (LNS) to generate highly diverse assembly code efficiently. Experiments using two popular compiler benchmark suites confirm that there is a trade-off between quality of each assembly code version and diversity of the entire pool of versions. Our results show that DivCon allows users to trade between these two properties by generating diverse assembly code for a range of quality bounds. In particular, the experiments show that DivCon is able to mitigate code-reuse attacks effectively while delivering near-optimal code (< 10% optimality gap). For constraint programming researchers and practitioners, this paper demonstrates that LNS is a valuable technique for finding diverse solutions. For security researchers and software engineers, DivCon extends the scope of compiler-based diversification to performance-critical and resource-constrained applications.
Low-dimensional Interpretable Kernels with Conic Discriminant Functions for Classification
Venue: arXiv cs.LG 2020
Year: 2020

Kernels are often developed and used as implicit mapping functions that show impressive predictive power due to their high-dimensional feature space representations. In this study, we gradually construct a series of simple feature maps that lead to a collection of interpretable low-dimensional kernels. At each step, we keep the original features and make sure that the increase in the dimension of input data is extremely low, so that the resulting discriminant functions remain interpretable and amenable to fast training. Despite our persistence on interpretability, we obtain high accuracy results even without in-depth hyperparameter tuning. Comparison of our results against several well-known kernels on benchmark datasets show that the proposed kernels are competitive in terms of prediction accuracy, while the training times are significantly lower than those obtained with state-of-the-art kernel implementations.