OpenRaiser/Intern-Atlas huggingface dataset:
Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs
Venue: arXiv cs.DS 2021
Year: 2021

In this paper we give fast distributed graph algorithms for detecting and listing small subgraphs, and for computing or approximating the girth. Our algorithms improve upon the state of the art by polynomial factors, and for girth, we obtain an constant-time algorithm for additive +1 approximation in the Congested Clique, and the first parametrized algorithm for exact computation in CONGEST. In the Congested Clique, we develop a technique for learning small neighborhoods, and apply it to obtain an $O(1)$-round algorithm that computes the girth with only an additive +1 error. Next, we introduce a new technique (the partition tree technique) allowing for efficiently and deterministically listing all copies of any subgraph, improving upon the state-of the-art for non-dense graphs. We give two applications of this technique: First we show that for constant $k$, $C_{2k}$-detection can be solved in $O(1)$ rounds in the Congested Clique, improving on prior work which used matrix multiplication and had polynomial round complexity. Second, we show that in triangle-free graphs, the girth can be exactly computed in time polynomially faster than the best known bounds for general graphs. In CONGEST, we describe a new approach for finding cycles, and apply it in two ways: first we show a fast parametrized algorithm for girth with round complexity $\tilde{O}(\min(g\cdot n^{1-1/Θ(g)},n))$ for any girth $g$; and second, we show how to find small even-length cycles $C_{2k}$ for $k = 3,4,5$ in $O(n^{1-1/k})$ rounds, which is a polynomial improvement upon the previous running times. Finally, using our improved $C_6$-freeness algorithm and the barrier on proving lower bounds on triangle-freeness of Eden et al., we show that improving the current $\tildeΩ(\sqrt{n})$ lower bound for $C_6$-freeness of Korhonen et al. by any polynomial factor would imply strong circuit complexity lower bounds.
A family of codes with locality containing optimal codes
Venue: arXiv cs.IT 2021
Year: 2021

Locally recoverable codes were introduced by Gopalan et al. in 2012, and in the same year Prakash et al. introduced the concept of codes with locality, which are a type of locally recoverable codes. In this work we introduce a new family of codes with locality, which are subcodes of a certain family of evaluation codes. We determine the dimension of these codes, and also bounds for the minimum distance. We present the true values of the minimum distance in special cases, and also show that elements of this family are "optimal codes", as defined by Prakash et al.
COTORRA: COntext-aware Testbed fOR Robotic Applications
Venue: arXiv cs.RO 2021
Year: 2021

Edge & Fog computing have received considerable attention as promising candidates for the evolution of robotic systems. In this letter, we propose COTORRA, an Edge & Fog driven robotic testbed that combines context information with robot sensor data to validate innovative concepts for robotic systems prior to being applied in a production environment. In lab/university, we established COTORRA as an easy applicable and modular testbed on top of heterogeneous network infrastructure. COTORRA is open for pluggable robotic applications. To verify its feasibility and assess its performance, we ran set of experiments that show how autonomous navigation applications can achieve target latencies bellow 15ms or perform an inter-domain (DLT) federation within 19 seconds.
Choice Set Misspecification in Reward Inference
Venue: arXiv cs.AI 2021
Year: 2021

Specifying reward functions for robots that operate in environments without a natural reward signal can be challenging, and incorrectly specified rewards can incentivise degenerate or dangerous behavior. A promising alternative to manually specifying reward functions is to enable robots to infer them from human feedback, like demonstrations or corrections. To interpret this feedback, robots treat as approximately optimal a choice the person makes from a choice set, like the set of possible trajectories they could have demonstrated or possible corrections they could have made. In this work, we introduce the idea that the choice set itself might be difficult to specify, and analyze choice set misspecification: what happens as the robot makes incorrect assumptions about the set of choices from which the human selects their feedback. We propose a classification of different kinds of choice set misspecification, and show that these different classes lead to meaningful differences in the inferred reward and resulting performance. While we would normally expect misspecification to hurt, we find that certain kinds of misspecification are neither helpful nor harmful (in expectation). However, in other situations, misspecification can be extremely harmful, leading the robot to believe the opposite of what it should believe. We hope our results will allow for better prediction and response to the effects of misspecification in real-world reward inference.
Leveraging Peer Review in Visualization Education: A Proposal for a New Model
Venue: arXiv cs.HC 2021
Year: 2021

In visualization education, both science and humanities, the literature is often divided into two parts: the design aspect and the analysis of the visualization. However, we find limited discussion on how to motivate and engage visualization students in the classroom. In the field of Writing Studies, researchers develop tools and frameworks for student peer review of writing. Based on the literature review from the field of Writing Studies, this paper proposes a new framework to implement visualization peer review in the classroom to engage today's students. This framework can be customized for incremental and double-blind review to inspire students and reinforce critical thinking about visualization.
Out-of-distribution Prediction with Invariant Risk Minimization: The Limitation and An Effective Fix
Venue: arXiv cs.LG 2021
Year: 2021

This work considers the out-of-distribution (OOD) prediction problem where (1)~the training data are from multiple domains and (2)~the test domain is unseen in the training. DNNs fail in OOD prediction because they are prone to pick up spurious correlations. Recently, Invariant Risk Minimization (IRM) is proposed to address this issue. Its effectiveness has been demonstrated in the colored MNIST experiment. Nevertheless, we find that the performance of IRM can be dramatically degraded under \emph{strong $Λ$ spuriousness} -- when the spurious correlation between the spurious features and the class label is strong due to the strong causal influence of their common cause, the domain label, on both of them (see Fig. 1). In this work, we try to answer the questions: why does IRM fail in the aforementioned setting? Why does IRM work for the original colored MNIST dataset? How can we fix this problem of IRM? Then, we propose a simple and effective approach to fix the problem of IRM. We combine IRM with conditional distribution matching to avoid a specific type of spurious correlation under strong $Λ$ spuriousness. Empirically, we design a series of semi synthetic datasets -- the colored MNIST plus, which exposes the problems of IRM and demonstrates the efficacy of the proposed method.
Learning over Families of Sets -- Hypergraph Representation Learning for Higher Order Tasks
Venue: arXiv cs.LG 2021
Year: 2021

Graph representation learning has made major strides over the past decade. However, in many relational domains, the input data are not suited for simple graph representations as the relationships between entities go beyond pairwise interactions. In such cases, the relationships in the data are better represented as hyperedges (set of entities) of a non-uniform hypergraph. While there have been works on principled methods for learning representations of nodes of a hypergraph, these approaches are limited in their applicability to tasks on non-uniform hypergraphs (hyperedges with different cardinalities). In this work, we exploit the incidence structure to develop a hypergraph neural network to learn provably expressive representations of variable sized hyperedges which preserve local-isomorphism in the line graph of the hypergraph, while also being invariant to permutations of its constituent vertices. Specifically, for a given vertex set, we propose frameworks for (1) hyperedge classification and (2) variable sized expansion of partially observed hyperedges which captures the higher order interactions among vertices and hyperedges. We evaluate performance on multiple real-world hypergraph datasets and demonstrate consistent, significant improvement in accuracy, over state-of-the-art models.
Machine learning applications for COVID-19: A state-of-the-art review
Venue: arXiv cs.LG 2021
Year: 2021

The COVID-19 pandemic has galvanized the machine learning community to create new solutions that can help in the fight against the virus. The body of literature related to applications of machine learning and artificial intelligence to COVID-19 is constantly growing. The goal of this article is to present the latest advances in machine learning research applied to COVID-19. We cover four major areas of research: forecasting, medical diagnostics, drug development, and contact tracing. We review and analyze the most successful state of the art studies. In contrast to other existing surveys on the subject, our article presents a high level overview of the current research that is sufficiently detailed to provide an informed insight.
Multi-Task Network Pruning and Embedded Optimization for Real-time Deployment in ADAS
Venue: arXiv cs.CV 2021
Year: 2021

Camera-based Deep Learning algorithms are increasingly needed for perception in Automated Driving systems. However, constraints from the automotive industry challenge the deployment of CNNs by imposing embedded systems with limited computational resources. In this paper, we propose an approach to embed a multi-task CNN network under such conditions on a commercial prototype platform, i.e. a low power System on Chip (SoC) processing four surround-view fisheye cameras at 10 FPS. The first focus is on designing an efficient and compact multi-task network architecture. Secondly, a pruning method is applied to compress the CNN, helping to reduce the runtime and memory usage by a factor of 2 without lowering the performances significantly. Finally, several embedded optimization techniques such as mixed-quantization format usage and efficient data transfers between different memory areas are proposed to ensure real-time execution and avoid bandwidth bottlenecks. The approach is evaluated on the hardware platform, considering embedded detection performances, runtime and memory bandwidth. Unlike most works from the literature that focus on classification task, we aim here to study the effect of pruning and quantization on a compact multi-task network with object detection, semantic segmentation and soiling detection tasks.
Learning Abstract Task Representations
Venue: arXiv cs.LG 2021
Year: 2021

A proper form of data characterization can guide the process of learning-algorithm selection and model-performance estimation. The field of meta-learning has provided a rich body of work describing effective forms of data characterization using different families of meta-features (statistical, model-based, information-theoretic, topological, etc.). In this paper, we start with the abundant set of existing meta-features and propose a method to induce new abstract meta-features as latent variables in a deep neural network. We discuss the pitfalls of using traditional meta-features directly and argue for the importance of learning high-level task properties. We demonstrate our methodology using a deep neural network as a feature extractor. We demonstrate that 1) induced meta-models mapping abstract meta-features to generalization performance outperform other methods by ~18% on average, and 2) abstract meta-features attain high feature-relevance scores.
A Search-Based Testing Framework for Deep Neural Networks of Source Code Embedding
Venue: arXiv cs.SE 2021
Year: 2021

Over the past few years, deep neural networks (DNNs) have been continuously expanding their real-world applications for source code processing tasks across the software engineering domain, e.g., clone detection, code search, comment generation. Although quite a few recent works have been performed on testing of DNNs in the context of image and speech processing, limited progress has been achieved so far on DNN testing in the context of source code processing, that exhibits rather unique characteristics and challenges. In this paper, we propose a search-based testing framework for DNNs of source code embedding and its downstream processing tasks like Code Search. To generate new test inputs, we adopt popular source code refactoring tools to generate the semantically equivalent variants. For more effective testing, we leverage the DNN mutation testing to guide the testing direction. To demonstrate the usefulness of our technique, we perform a large-scale evaluation on popular DNNs of source code processing based on multiple state-of-the-art code embedding methods (i.e., Code2vec, Code2seq and CodeBERT). The testing results show that our generated adversarial samples can on average reduce the performance of these DNNs from 5.41% to 9.58%. Through retraining the DNNs with our generated adversarial samples, the robustness of DNN can improve by 23.05% on average. The evaluation results also show that our adversarial test generation strategy has the least negative impact (median of 3.56%), on the performance of the DNNs for regular test data, compared to the other methods.
Beyond Fine-tuning: Classifying High Resolution Mammograms using Function-Preserving Transformations
Venue: arXiv cs.CV 2021
Year: 2021

The task of classifying mammograms is very challenging because the lesion is usually small in the high resolution image. The current state-of-the-art approaches for medical image classification rely on using the de-facto method for ConvNets - fine-tuning. However, there are fundamental differences between natural images and medical images, which based on existing evidence from the literature, limits the overall performance gain when designed with algorithmic approaches. In this paper, we propose to go beyond fine-tuning by introducing a novel framework called MorphHR, in which we highlight a new transfer learning scheme. The idea behind the proposed framework is to integrate function-preserving transformations, for any continuous non-linear activation neurons, to internally regularise the network for improving mammograms classification. The proposed solution offers two major advantages over the existing techniques. Firstly and unlike fine-tuning, the proposed approach allows for modifying not only the last few layers but also several of the first ones on a deep ConvNet. By doing this, we can design the network front to be suitable for learning domain specific features. Secondly, the proposed scheme is scalable to hardware. Therefore, one can fit high resolution images on standard GPU memory. We show that by using high resolution images, one prevents losing relevant information. We demonstrate, through numerical and visual experiments, that the proposed approach yields to a significant improvement in the classification performance over state-of-the-art techniques, and is indeed on a par with radiology experts. Moreover and for generalisation purposes, we show the effectiveness of the proposed learning scheme on another large dataset, the ChestX-ray14, surpassing current state-of-the-art techniques.
PyTorch-Direct: Enabling GPU Centric Data Access for Very Large Graph Neural Network Training with Irregular Accesses
Venue: arXiv cs.LG 2021
Year: 2021

With the increasing adoption of graph neural networks (GNNs) in the machine learning community, GPUs have become an essential tool to accelerate GNN training. However, training GNNs on very large graphs that do not fit in GPU memory is still a challenging task. Unlike conventional neural networks, mini-batching input samples in GNNs requires complicated tasks such as traversing neighboring nodes and gathering their feature values. While this process accounts for a significant portion of the training time, we find existing GNN implementations using popular deep neural network (DNN) libraries such as PyTorch are limited to a CPU-centric approach for the entire data preparation step. This "all-in-CPU" approach has negative impact on the overall GNN training performance as it over-utilizes CPU resources and hinders GPU acceleration of GNN training. To overcome such limitations, we introduce PyTorch-Direct, which enables a GPU-centric data accessing paradigm for GNN training. In PyTorch-Direct, GPUs are capable of efficiently accessing complicated data structures in host memory directly without CPU intervention. Our microbenchmark and end-to-end GNN training results show that PyTorch-Direct reduces data transfer time by 47.1% on average and speeds up GNN training by up to 1.6x. Furthermore, by reducing CPU utilization, PyTorch-Direct also saves system power by 12.4% to 17.5% during training. To minimize programmer effort, we introduce a new "unified tensor" type along with necessary changes to the PyTorch memory allocator, dispatch logic, and placement rules. As a result, users need to change at most two lines of their PyTorch GNN training code for each tensor object to take advantage of PyTorch-Direct.
A Visual Analytics Approach to Facilitate the Proctoring of Online Exams
Venue: arXiv cs.HC 2021
Year: 2021

Online exams have become widely used to evaluate students' performance in mastering knowledge in recent years, especially during the pandemic of COVID-19. However, it is challenging to conduct proctoring for online exams due to the lack of face-to-face interaction. Also, prior research has shown that online exams are more vulnerable to various cheating behaviors, which can damage their credibility. This paper presents a novel visual analytics approach to facilitate the proctoring of online exams by analyzing the exam video records and mouse movement data of each student. Specifically, we detect and visualize suspected head and mouse movements of students in three levels of detail, which provides course instructors and teachers with convenient, efficient and reliable proctoring for online exams. Our extensive evaluations, including usage scenarios, a carefully-designed user study and expert interviews, demonstrate the effectiveness and usability of our approach.
FedNS: Improving Federated Learning for collaborative image classification on mobile clients
Venue: arXiv cs.CV 2021
Year: 2021

Federated Learning (FL) is a paradigm that aims to support loosely connected clients in learning a global model collaboratively with the help of a centralized server. The most popular FL algorithm is Federated Averaging (FedAvg), which is based on taking weighted average of the client models, with the weights determined largely based on dataset sizes at the clients. In this paper, we propose a new approach, termed Federated Node Selection (FedNS), for the server's global model aggregation in the FL setting. FedNS filters and re-weights the clients' models at the node/kernel level, hence leading to a potentially better global model by fusing the best components of the clients. Using collaborative image classification as an example, we show with experiments from multiple datasets and networks that FedNS can consistently achieve improved performance over FedAvg.
UPDeT: Universal Multi-agent Reinforcement Learning via Policy Decoupling with Transformers
Venue: arXiv cs.LG 2021
Year: 2021

Recent advances in multi-agent reinforcement learning have been largely limited in training one model from scratch for every new task. The limitation is due to the restricted model architecture related to fixed input and output dimensions. This hinders the experience accumulation and transfer of the learned agent over tasks with diverse levels of difficulty (e.g. 3 vs 3 or 5 vs 6 multi-agent games). In this paper, we make the first attempt to explore a universal multi-agent reinforcement learning pipeline, designing one single architecture to fit tasks with the requirement of different observation and action configurations. Unlike previous RNN-based models, we utilize a transformer-based model to generate a flexible policy by decoupling the policy distribution from the intertwined input observation with an importance weight measured by the merits of the self-attention mechanism. Compared to a standard transformer block, the proposed model, named as Universal Policy Decoupling Transformer (UPDeT), further relaxes the action restriction and makes the multi-agent task's decision process more explainable. UPDeT is general enough to be plugged into any multi-agent reinforcement learning pipeline and equip them with strong generalization abilities that enables the handling of multiple tasks at a time. Extensive experiments on large-scale SMAC multi-agent competitive games demonstrate that the proposed UPDeT-based multi-agent reinforcement learning achieves significant results relative to state-of-the-art approaches, demonstrating advantageous transfer capability in terms of both performance and training speed (10 times faster).
NEMR: Network Embedding on Metric of Relation
Venue: arXiv cs.SI 2021
Year: 2021

Network embedding maps the nodes of a given network into a low-dimensional space such that the semantic similarities among the nodes can be effectively inferred. Most existing approaches use inner-product of node embedding to measure the similarity between nodes leading to the fact that they lack the capacity to capture complex relationships among nodes. Besides, they take the path in the network just as structural auxiliary information when inferring node embeddings, while paths in the network are formed with rich user informations which are semantically relevant and cannot be ignored. In this paper, We propose a novel method called Network Embedding on the Metric of Relation, abbreviated as NEMR, which can learn the embeddings of nodes in a relational metric space efficiently. First, our NEMR models the relationships among nodes in a metric space with deep learning methods including variational inference that maps the relationship of nodes to a gaussian distribution so as to capture the uncertainties. Secondly, our NEMR considers not only the equivalence of multiple-paths but also the natural order of a single-path when inferring embeddings of nodes, which makes NEMR can capture the multiple relationships among nodes since multiple paths contain rich user information, e.g., age, hobby and profession. Experimental results on several public datasets show that the NEMR outperforms the state-of-the-art methods on relevant inference tasks including link prediction and node classification.
Scalable Deep Compressive Sensing
Venue: arXiv cs.CV 2021
Year: 2021

Deep learning has been used to image compressive sensing (CS) for enhanced reconstruction performance. However, most existing deep learning methods train different models for different subsampling ratios, which brings additional hardware burden. In this paper, we develop a general framework named scalable deep compressive sensing (SDCS) for the scalable sampling and reconstruction (SSR) of all existing end-to-end-trained models. In the proposed way, images are measured and initialized linearly. Two sampling masks are introduced to flexibly control the subsampling ratios used in sampling and reconstruction, respectively. To make the reconstruction model adapt to any subsampling ratio, a training strategy dubbed scalable training is developed. In scalable training, the model is trained with the sampling matrix and the initialization matrix at various subsampling ratios by integrating different sampling matrix masks. Experimental results show that models with SDCS can achieve SSR without changing their structure while maintaining good performance, and SDCS outperforms other SSR methods.