OpenRaiser/Intern-Atlas huggingface dataset:
Accurate position tracking with a single UWB anchor
Venue: arXiv cs.RO 2021
Year: 2021

Accurate localization and tracking are a fundamental requirement for robotic applications. Localization systems like GPS, optical tracking, simultaneous localization and mapping (SLAM) are used for daily life activities, research, and commercial applications. Ultra-wideband (UWB) technology provides another venue to accurately locate devices both indoors and outdoors. In this paper, we study a localization solution with a single UWB anchor, instead of the traditional multi-anchor setup. Besides the challenge of a single UWB ranging source, the only other sensor we require is a low-cost 9 DoF inertial measurement unit (IMU). Under such a configuration, we propose continuous monitoring of UWB range changes to estimate the robot speed when moving on a line. Combining speed estimation with orientation estimation from the IMU sensor, the system becomes temporally observable. We use an Extended Kalman Filter (EKF) to estimate the pose of a robot. With our solution, we can effectively correct the accumulated error and maintain accurate tracking of a moving robot.
WiFiTrace: Network-based Contact Tracing for Infectious Diseases Using Passive WiFi Sensing
Venue: arXiv cs.NI 2021
Year: 2021

Contact tracing is a well-established and effective approach for the containment of the spread of infectious diseases. While Bluetooth-based contact tracing method using phones has become popular recently, these approaches suffer from the need for a critical mass adoption to be effective. In this paper, we present WiFiTrace, a network-centric approach for contact tracing that relies on passive WiFi sensing with no client-side involvement. Our approach exploits WiFi network logs gathered by enterprise networks for performance and security monitoring, and utilizes them for reconstructing device trajectories for contact tracing. Our approach is specifically designed to enhance the efficacy of traditional methods, rather than to supplant them with new technology. We designed an efficient graph algorithm to scale our approach to large networks with tens of thousands of users. The graph-based approach outperforms an indexed PostgresSQL in memory by at least 4.5X without any index update overheads or blocking. We have implemented a full prototype of our system and deployed it on two large university campuses. We validated our approach and demonstrate its efficacy using case studies and detailed experiments using real-world WiFi datasets.
Happy Are Those Who Grade without Seeing: A Multi-Task Learning Approach to Grade Essays Using Gaze Behaviour
Venue: arXiv cs.CL 2021
Year: 2021

The gaze behaviour of a reader is helpful in solving several NLP tasks such as automatic essay grading. However, collecting gaze behaviour from readers is costly in terms of time and money. In this paper, we propose a way to improve automatic essay grading using gaze behaviour, which is learnt at run time using a multi-task learning framework. To demonstrate the efficacy of this multi-task learning based approach to automatic essay grading, we collect gaze behaviour for 48 essays across 4 essay sets, and learn gaze behaviour for the rest of the essays, numbering over 7000 essays. Using the learnt gaze behaviour, we can achieve a statistically significant improvement in performance over the state-of-the-art system for the essay sets where we have gaze data. We also achieve a statistically significant improvement for 4 other essay sets, numbering about 6000 essays, where we have no gaze behaviour data available. Our approach establishes that learning gaze behaviour improves automatic essay grading.
Design of a dynamic and self adapting system, supported with artificial intelligence, machine learning and real time intelligence for predictive cyber risk analytics in extreme environments, cyber risk in the colonisation of Mars
Venue: arXiv cs.CY 2021
Year: 2021

Multiple governmental agencies and private organisations have made commitments for the colonisation of Mars. Such colonisation requires complex systems and infrastructure that could be very costly to repair or replace in cases of cyber attacks. This paper surveys deep learning algorithms, IoT cyber security and risk models, and established mathematical formulas to identify the best approach for developing a dynamic and self adapting system for predictive cyber risk analytics supported with Artificial Intelligence and Machine Learning and real time intelligence in edge computing. The paper presents a new mathematical approach for integrating concepts for cognition engine design, edge computing and Artificial Intelligence and Machine Learning to automate anomaly detection. This engine instigates a step change by applying Artificial Intelligence and Machine Learning embedded at the edge of IoT networks, to deliver safe and functional real time intelligence for predictive cyber risk analytics. This will enhance capacities for risk analytics and assists in the creation of a comprehensive and systematic understanding of the opportunities and threats that arise when edge computing nodes are deployed, and when Artificial Intelligence and Machine Learning technologies are migrated to the periphery of the internet and into local IoT networks.
Network Bending: Expressive Manipulation of Deep Generative Models
Venue: arXiv cs.CV 2021
Year: 2021

We introduce a new framework for manipulating and interacting with deep generative models that we call network bending. We present a comprehensive set of deterministic transformations that can be inserted as distinct layers into the computational graph of a trained generative neural network and applied during inference. In addition, we present a novel algorithm for analysing the deep generative model and clustering features based on their spatial activation maps. This allows features to be grouped together based on spatial similarity in an unsupervised fashion. This results in the meaningful manipulation of sets of features that correspond to the generation of a broad array of semantically significant features of the generated images. We outline this framework, demonstrating our results on state-of-the-art deep generative models trained on several image datasets. We show how it allows for the direct manipulation of semantically meaningful aspects of the generative process as well as allowing for a broad range of expressive outcomes.
Benchmarking Graph Data Management and Processing Systems: A Survey
Venue: arXiv cs.DC 2021
Year: 2021

The development of scalable, representative, and widely adopted benchmarks for graph data systems have been a question for which answers has been sought for decades. We conduct an in-depth study of the existing literature on benchmarks for graph data management and processing, covering 20 different benchmarks developed during the last 15 years. We categorize the benchmarks into three areas focusing on benchmarks for graph processing systems, graph database benchmarks, and bigdata benchmarks with graph processing workloads. This systematic approach allows us to identify multiple issues existing in this area, including i) few benchmarks exist which can produce high workload scenarios, ii) no significant work done on benchmarking graph stream processing as well as graph based machine learning, iii) benchmarks tend to use conventional metrics despite new meaningful metrics have been around for years, iv) increasing number of big data benchmarks appear with graph processing workloads. Following these observations, we conclude the survey by describing key challenges for future research on graph data systems benchmarking.
3D-OGSE: Online Safe and Smooth Trajectory Generation using Generalized Shape Expansion in Unknown 3-D Environments
Venue: arXiv cs.RO 2021
Year: 2021

In this paper, we present an online motion planning algorithm (3D-OGSE) for generating smooth, collision-free trajectories over multiple planning iterations for 3-D agents operating in an unknown obstacle-cluttered 3-D environment. Our approach constructs a safe-region, termed 'generalized shape', at each planning iteration, which represents the obstacle-free region based on locally-sensed environment information. A collision-free path is computed by sampling points in the generalized shape and is used to generate a smooth, time-parametrized trajectory by minimizing snap. The generated trajectories are constrained to lie within the generalized shape, which ensures the agent maneuvers in the locally obstacle-free space. As the agent reaches boundary of 'sensing shape' in a planning iteration, a re-plan is triggered by receding horizon planning mechanism that also enables initialization of the next planning iteration. Theoretical guarantee of probabilistic completeness over the entire environment and of completely collision-free trajectory generation is provided. We evaluate the proposed method in simulation on complex 3-D environments with varied obstacle-densities. We observe that each re-planing computation takes $\sim$1.4 milliseconds on a single thread of an Intel Core i5-8500 3.0 GHz CPU. In addition, our method is found to perform 4-10 times faster than several existing algorithms. In simulation over complex scenarios such as narrow passages also we observe less conservative behavior.
Computing Subset Transversals in $H$-Free Graphs
Venue: arXiv cs.DS 2021
Year: 2021

We study the computational complexity of two well-known graph transversal problems, namely Subset Feedback Vertex Set and Subset Odd Cycle Transversal, by restricting the input to $H$-free graphs, that is, to graphs that do not contain some fixed graph~$H$ as an induced subgraph. By combining known and new results, we determine the computational complexity of both problems on $H$-free graphs for every graph $H$ except when $H=sP_1+P_4$ for some $s\geq 1$. As part of our approach, we introduce the Subset Vertex Cover problem and prove that it is polynomial-time solvable for $(sP_1+P_4)$-free graphs for every $s\geq 1$.
Erasure Broadcast Channels with Intermittent Feedback
Venue: arXiv cs.IT 2021
Year: 2021

Achievable data rates in wireless systems rely heavily on the available channel state information (CSI) throughout the network. However, feedback links, which provide this information, are scarce, unreliable, and subject to security threats. In this work, we study the impact of having intermittent feedback links on the capacity region of the canonical two-user erasure broadcast channels. In our model, at any time instant, each receiver broadcasts its CSI, and at any other node, this information either becomes available with unit delay or gets erased. For this setting, we develop a new set of outer bounds to capture the intermittent nature of the feedback links. These outer bounds depend on the probability that the CSI from both receivers are erased at the transmitter. In particular, if at any time, the CSI from at least one of the two receivers is available at the other two nodes, then the outer-bounds match the capacity with global delayed CSI. We also provide capacity-achieving transmission strategies under certain scenarios, and we establish a connection between this problem and Blind Index Coding with feedback.
Not made for each other- Audio-Visual Dissonance-based Deepfake Detection and Localization
Venue: arXiv cs.CV 2021
Year: 2021

We propose detection of deepfake videos based on the dissimilarity between the audio and visual modalities, termed as the Modality Dissonance Score (MDS). We hypothesize that manipulation of either modality will lead to dis-harmony between the two modalities, eg, loss of lip-sync, unnatural facial and lip movements, etc. MDS is computed as an aggregate of dissimilarity scores between audio and visual segments in a video. Discriminative features are learnt for the audio and visual channels in a chunk-wise manner, employing the cross-entropy loss for individual modalities, and a contrastive loss that models inter-modality similarity. Extensive experiments on the DFDC and DeepFake-TIMIT Datasets show that our approach outperforms the state-of-the-art by up to 7%. We also demonstrate temporal forgery localization, and show how our technique identifies the manipulated video segments.
Query complexity of heavy hitter estimation
Venue: arXiv cs.IT 2021
Year: 2021

We consider the problem of identifying the subset $\mathcal{S}^γ_{\mathcal{P}}$ of elements in the support of an underlying distribution $\mathcal{P}$ whose probability value is larger than a given threshold $γ$, by actively querying an oracle to gain information about a sequence $X_1, X_2, \ldots$ of $i.i.d.$ samples drawn from $\mathcal{P}$. We consider two query models: $(a)$ each query is an index $i$ and the oracle return the value $X_i$ and $(b)$ each query is a pair $(i,j)$ and the oracle gives a binary answer confirming if $X_i = X_j$ or not. For each of these query models, we design sequential estimation algorithms which at each round, either decide what query to send to the oracle depending on the entire history of responses or decide to stop and output an estimate of $\mathcal{S}^γ_{\mathcal{P}}$, which is required to be correct with some pre-specified large probability. We provide upper bounds on the query complexity of the algorithms for any distribution $\mathcal{P}$ and also derive lower bounds on the optimal query complexity under the two query models. We also consider noisy versions of the two query models and propose robust estimators which can effectively counter the noise in the oracle responses.
Non-Local Graph Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

Modern graph neural networks (GNNs) learn node embeddings through multilayer local aggregation and achieve great success in applications on assortative graphs. However, tasks on disassortative graphs usually require non-local aggregation. In addition, we find that local aggregation is even harmful for some disassortative graphs. In this work, we propose a simple yet effective non-local aggregation framework with an efficient attention-guided sorting for GNNs. Based on it, we develop various non-local GNNs. We perform thorough experiments to analyze disassortative graph datasets and evaluate our non-local GNNs. Experimental results demonstrate that our non-local GNNs significantly outperform previous state-of-the-art methods on seven benchmark datasets of disassortative graphs, in terms of both model performance and efficiency.
Massive Choice, Ample Tasks (MaChAmp): A Toolkit for Multi-task Learning in NLP
Venue: arXiv cs.CL 2021
Year: 2021

Transfer learning, particularly approaches that combine multi-task learning with pre-trained contextualized embeddings and fine-tuning, have advanced the field of Natural Language Processing tremendously in recent years. In this paper we present MaChAmp, a toolkit for easy fine-tuning of contextualized embeddings in multi-task settings. The benefits of MaChAmp are its flexible configuration options, and the support of a variety of natural language processing tasks in a uniform toolkit, from text classification and sequence labeling to dependency parsing, masked language modeling, and text generation.
KGTK: A Toolkit for Large Knowledge Graph Manipulation and Analysis
Venue: arXiv cs.AI 2021
Year: 2021

Knowledge graphs (KGs) have become the preferred technology for representing, sharing and adding knowledge to modern AI applications. While KGs have become a mainstream technology, the RDF/SPARQL-centric toolset for operating with them at scale is heterogeneous, difficult to integrate and only covers a subset of the operations that are commonly needed in data science applications. In this paper we present KGTK, a data science-centric toolkit designed to represent, create, transform, enhance and analyze KGs. KGTK represents graphs in tables and leverages popular libraries developed for data science applications, enabling a wide audience of developers to easily construct knowledge graph pipelines for their applications. We illustrate the framework with real-world scenarios where we have used KGTK to integrate and manipulate large KGs, such as Wikidata, DBpedia and ConceptNet.
Data Augmentation with Unsupervised Machine Translation Improves the Structural Similarity of Cross-lingual Word Embeddings
Venue: arXiv cs.CL 2021
Year: 2021

Unsupervised cross-lingual word embedding (CLWE) methods learn a linear transformation matrix that maps two monolingual embedding spaces that are separately trained with monolingual corpora. This method relies on the assumption that the two embedding spaces are structurally similar, which does not necessarily hold true in general. In this paper, we argue that using a pseudo-parallel corpus generated by an unsupervised machine translation model facilitates the structural similarity of the two embedding spaces and improves the quality of CLWEs in the unsupervised mapping method. We show that our approach outperforms other alternative approaches given the same amount of data, and, through detailed analysis, we show that data augmentation with the pseudo data from unsupervised machine translation is especially effective for mapping-based CLWEs because (1) the pseudo data makes the source and target corpora (partially) parallel; (2) the pseudo data contains information on the original language that helps to learn similar embedding spaces between the source and target languages.
Real-World Scenario Mining for the Assessment of Automated Vehicles
Venue: arXiv cs.RO 2021
Year: 2021

Scenario-based methods for the assessment of Automated Vehicles (AVs) are widely supported by many players in the automotive field. Scenarios captured from real-world data can be used to define the scenarios for the assessment and to estimate their relevance. Therefore, different techniques are proposed for capturing scenarios from real-world data. In this paper, we propose a new method to capture scenarios from real-world data using a two-step approach. The first step consists in automatically labeling the data with tags. Second, we mine the scenarios, represented by a combination of tags, based on the labeled tags. One of the benefits of our approach is that the tags can be used to identify characteristics of a scenario that are shared among different type of scenarios. In this way, these characteristics need to be identified only once. Furthermore, the method is not specific for one type of scenario and, therefore, it can be applied to a large variety of scenarios. We provide two examples to illustrate the method. This paper is concluded with some promising future possibilities for our approach, such as automatic generation of scenarios for the assessment of automated vehicles.
Submodular Bandit Problem Under Multiple Constraints
Venue: arXiv cs.LG 2021
Year: 2021

The linear submodular bandit problem was proposed to simultaneously address diversified retrieval and online learning in a recommender system. If there is no uncertainty, this problem is equivalent to a submodular maximization problem under a cardinality constraint. However, in some situations, recommendation lists should satisfy additional constraints such as budget constraints, other than a cardinality constraint. Thus, motivated by diversified retrieval considering budget constraints, we introduce a submodular bandit problem under the intersection of $l$ knapsacks and a $k$-system constraint. Here $k$-system constraints form a very general class of constraints including cardinality constraints and the intersection of $k$ matroid constraints. To solve this problem, we propose a non-greedy algorithm that adaptively focuses on a standard or modified upper-confidence bound. We provide a high-probability upper bound of an approximation regret, where the approximation ratio matches that of a fast offline algorithm. Moreover, we perform experiments under various combinations of constraints using a synthetic and two real-world datasets and demonstrate that our proposed methods outperform the existing baselines.
BadNL: Backdoor Attacks against NLP Models with Semantic-preserving Improvements
Venue: arXiv cs.CR 2021
Year: 2021

Deep neural networks (DNNs) have progressed rapidly during the past decade and have been deployed in various real-world applications. Meanwhile, DNN models have been shown to be vulnerable to security and privacy attacks. One such attack that has attracted a great deal of attention recently is the backdoor attack. Specifically, the adversary poisons the target model's training set to mislead any input with an added secret trigger to a target class. Previous backdoor attacks predominantly focus on computer vision (CV) applications, such as image classification. In this paper, we perform a systematic investigation of backdoor attack on NLP models, and propose BadNL, a general NLP backdoor attack framework including novel attack methods. Specifically, we propose three methods to construct triggers, namely BadChar, BadWord, and BadSentence, including basic and semantic-preserving variants. Our attacks achieve an almost perfect attack success rate with a negligible effect on the original model's utility. For instance, using the BadChar, our backdoor attack achieves a 98.9% attack success rate with yielding a utility improvement of 1.5% on the SST-5 dataset when only poisoning 3% of the original set. Moreover, we conduct a user study to prove that our triggers can well preserve the semantics from humans perspective.
SSumM: Sparse Summarization of Massive Graphs
Venue: arXiv cs.DB 2021
Year: 2021

Given a graph G and the desired size k in bits, how can we summarize G within k bits, while minimizing the information loss? Large-scale graphs have become omnipresent, posing considerable computational challenges. Analyzing such large graphs can be fast and easy if they are compressed sufficiently to fit in main memory or even cache. Graph summarization, which yields a coarse-grained summary graph with merged nodes, stands out with several advantages among graph compression techniques. Thus, a number of algorithms have been developed for obtaining a concise summary graph with little information loss or equivalently small reconstruction error. However, the existing methods focus solely on reducing the number of nodes, and they often yield dense summary graphs, failing to achieve better compression rates. Moreover, due to their limited scalability, they can be applied only to moderate-size graphs. In this work, we propose SSumM, a scalable and effective graph-summarization algorithm that yields a sparse summary graph. SSumM not only merges nodes together but also sparsifies the summary graph, and the two strategies are carefully balanced based on the minimum description length principle. Compared with state-of-the-art competitors, SSumM is (a) Concise: yields up to 11.2X smaller summary graphs with similar reconstruction error, (b) Accurate: achieves up to 4.2X smaller reconstruction error with similarly concise outputs, and (c) Scalable: summarizes 26X larger graphs while exhibiting linear scalability. We validate these advantages through extensive experiments on 10 real-world graphs.