OpenRaiser/Intern-Atlas huggingface dataset:
Towards Expressive Graph Representation
Venue: arXiv cs.LG 2020
Year: 2020

Graph Neural Network (GNN) aggregates the neighborhood of each node into the node embedding and shows its powerful capability for graph representation learning. However, most existing GNN variants aggregate the neighborhood information in a fixed non-injective fashion, which may map different graphs or nodes to the same embedding, reducing the model expressiveness. We present a theoretical framework to design a continuous injective set function for neighborhood aggregation in GNN. Using the framework, we propose expressive GNN that aggregates the neighborhood of each node with a continuous injective set function, so that a GNN layer maps similar nodes with similar neighborhoods to similar embeddings, different nodes to different embeddings and the equivalent nodes or isomorphic graphs to the same embeddings. Moreover, the proposed expressive GNN can naturally learn expressive representations for graphs with continuous node attributes. We validate the proposed expressive GNN (ExpGNN) for graph classification on multiple benchmark datasets including simple graphs and attributed graphs. The experimental results demonstrate that our model achieves state-of-the-art performances on most of the benchmarks.
OCNLI: Original Chinese Natural Language Inference
Venue: arXiv cs.CL 2020
Year: 2020

Despite the tremendous recent progress on natural language inference (NLI), driven largely by large-scale investment in new datasets (e.g., SNLI, MNLI) and advances in modeling, most progress has been limited to English due to a lack of reliable datasets for most of the world's languages. In this paper, we present the first large-scale NLI dataset (consisting of ~56,000 annotated sentence pairs) for Chinese called the Original Chinese Natural Language Inference dataset (OCNLI). Unlike recent attempts at extending NLI to other languages, our dataset does not rely on any automatic translation or non-expert annotation. Instead, we elicit annotations from native speakers specializing in linguistics. We follow closely the annotation protocol used for MNLI, but create new strategies for eliciting diverse hypotheses. We establish several baseline results on our dataset using state-of-the-art pre-trained models for Chinese, and find even the best performing models to be far outpaced by human performance (~12% absolute performance gap), making it a challenging new resource that we hope will help to accelerate progress in Chinese NLU. To the best of our knowledge, this is the first human-elicited MNLI-style corpus for a non-English language.
securePrune:Secure block pruning in UTXO based blockchains using Accumulators
Venue: arXiv cs.DC 2020
Year: 2020

In this paper, we propose a scheme called securePrune for reducing the storage space of a full node and synchronization time of bootstrapping nodes joining the Peer-to-Peer (P2P) network in an Unspent Transaction Outputs (UTXO) based blockchain like bitcoin using RSA accumulators. The size of the bitcoin blockchain is growing linearly with transactions. We propose a new block structure to represent the state of a blockchain also called UTXO set by including an accumulator of a state in the block header and proofs of knowledge for inclusion and deletion of the transactions of the current block in the block. In our scheme, the miners periodically release a snapshot of the blockchain state. The other full nodes in the network, securely prune the historical blocks after attaining the required number of confirmations for the snapshot block, which in turn confirms the snapshot of the state through an accumulator specified in the block header and proofs inside the block. The secure and periodic pruning of the old blocks, reduce the synchronization time for a new node joining into the network. The simulation results demonstrate a significant reduction in the storage space of a full node and bootstrapping cost of the new nodes.
Self-Stabilizing Indulgent Zero-degrading Binary Consensus
Venue: arXiv cs.DC 2020
Year: 2020

Guerraoui proposed an indulgent solution for the binary consensus problem. Namely, he showed that an arbitrary behavior of the failure detector never violates safety requirements even if it compromises liveness. Consensus implementations are often used in a repeated manner. Dutta and Guerraoui proposed a zero-degrading solution, \ie during system runs in which the failure detector behaves perfectly, a node failure during one consensus instance has no impact on the performance of future instances. Our study, which focuses on indulgent zero-degrading binary consensus, aims at the design of an even more robust communication abstraction. We do so through the lenses of self-stabilization - a very strong notion of fault-tolerance. In addition to node and communication failures, self-stabilizing algorithms can recover after the occurrence of arbitrary transient faults; these faults represent any violation of the assumptions according to which the system was designed to operate (as long as the algorithm code stays intact). This work proposes the first, to the best of our knowledge, self-stabilizing algorithm for indulgent zero-degrading binary consensus for time-free message-passing systems prone to detectable process failures. The proposed algorithm has an O(1) stabilization time (in terms of asynchronous cycles) from arbitrary transient faults. Since the proposed solution uses an Ω failure detector, we also present the first, to the best of our knowledge, self-stabilizing asynchronous Ω failure detector, which is a variation on the one by Mostéfaoui, Mourgaya, and Raynal.
Feature Extraction of Text for Deep Learning Algorithms: Application on Fake News Detection
Venue: arXiv cs.CL 2020
Year: 2020

Feature extraction is an important process of machine learning and deep learning, as the process make algorithms function more efficiently, and also accurate. In natural language processing used in deception detection such as fake news detection, several ways of feature extraction in statistical aspect had been introduced (e.g. N-gram). In this research, it will be shown that by using deep learning algorithms and alphabet frequencies of the original text of a news without any information about the sequence of the alphabet can actually be used to classify fake news and trustworthy ones in high accuracy (85\%). As this pre-processing method makes the data notably compact but also include the feature that is needed for the classifier, it seems that alphabet frequencies contains some useful features for understanding complex context or meaning of the original text.
A Lightweight Speaker Recognition System Using Timbre Properties
Venue: arXiv cs.SD 2020
Year: 2020

Speaker recognition is an active research area that contains notable usage in biometric security and authentication system. Currently, there exist many well-performing models in the speaker recognition domain. However, most of the advanced models implement deep learning that requires GPU support for real-time speech recognition, and it is not suitable for low-end devices. In this paper, we propose a lightweight text-independent speaker recognition model based on random forest classifier. It also introduces new features that are used for both speaker verification and identification tasks. The proposed model uses human speech based timbral properties as features that are classified using random forest. Timbre refers to the very basic properties of sound that allow listeners to discriminate among them. The prototype uses seven most actively searched timbre properties, boominess, brightness, depth, hardness, roughness, sharpness, and warmth as features of our speaker recognition model. The experiment is carried out on speaker verification and speaker identification tasks and shows the achievements and drawbacks of the proposed model. In the speaker identification phase, it achieves a maximum accuracy of 78%. On the contrary, in the speaker verification phase, the model maintains an accuracy of 80% having an equal error rate (ERR) of 0.24.
Explaining Neural Matrix Factorization with Gradient Rollback
Venue: arXiv cs.LG 2020
Year: 2020

Explaining the predictions of neural black-box models is an important problem, especially when such models are used in applications where user trust is crucial. Estimating the influence of training examples on a learned neural model's behavior allows us to identify training examples most responsible for a given prediction and, therefore, to faithfully explain the output of a black-box model. The most generally applicable existing method is based on influence functions, which scale poorly for larger sample sizes and models. We propose gradient rollback, a general approach for influence estimation, applicable to neural models where each parameter update step during gradient descent touches a smaller number of parameters, even if the overall number of parameters is large. Neural matrix factorization models trained with gradient descent are part of this model class. These models are popular and have found a wide range of applications in industry. Especially knowledge graph embedding methods, which belong to this class, are used extensively. We show that gradient rollback is highly efficient at both training and test time. Moreover, we show theoretically that the difference between gradient rollback's influence approximation and the true influence on a model's behavior is smaller than known bounds on the stability of stochastic gradient descent. This establishes that gradient rollback is robustly estimating example influence. We also conduct experiments which show that gradient rollback provides faithful explanations for knowledge base completion and recommender datasets.
Privacy-Preserving Distributed Projection LMS for Linear Multitask Networks
Venue: arXiv cs.MA 2020
Year: 2020

We develop a privacy-preserving distributed projection least mean squares (LMS) strategy over linear multitask networks, where agents' local parameters of interest or tasks are linearly related. Each agent is interested in not only improving its local inference performance via in-network cooperation with neighboring agents, but also protecting its own individual task against privacy leakage. In our proposed strategy, at each time instant, each agent sends a noisy estimate, which is its local intermediate estimate corrupted by a zero-mean additive noise, to its neighboring agents. We derive a sufficient condition to determine the amount of noise to add to each agent's intermediate estimate to achieve an optimal trade-off between the network mean-square-deviation and an inference privacy constraint. We propose a distributed and adaptive strategy to compute the additive noise powers, and study the mean and mean-square behaviors and privacy-preserving performance of the proposed strategy. Simulation results demonstrate that our strategy is able to balance the trade-off between estimation accuracy and privacy preservation.
Anomaly Detection With Conditional Variational Autoencoders
Venue: arXiv cs.LG 2020
Year: 2020

Exploiting the rapid advances in probabilistic inference, in particular variational Bayes and variational autoencoders (VAEs), for anomaly detection (AD) tasks remains an open research question. Previous works argued that training VAE models only with inliers is insufficient and the framework should be significantly modified in order to discriminate the anomalous instances. In this work, we exploit the deep conditional variational autoencoder (CVAE) and we define an original loss function together with a metric that targets hierarchically structured data AD. Our motivating application is a real world problem: monitoring the trigger system which is a basic component of many particle physics experiments at the CERN Large Hadron Collider (LHC). In the experiments we show the superior performance of this method for classical machine learning (ML) benchmarks and for our application.
The National Corpus of Contemporary Welsh: Project Report | Y Corpws Cenedlaethol Cymraeg Cyfoes: Adroddiad y Prosiect
Venue: arXiv cs.CL 2020
Year: 2020

This report provides an overview of the CorCenCC project and the online corpus resource that was developed as a result of work on the project. The report lays out the theoretical underpinnings of the research, demonstrating how the project has built on and extended this theory. We also raise and discuss some of the key operational questions that arose during the course of the project, outlining the ways in which they were answered, the impact of these decisions on the resource that has been produced and the longer-term contribution they will make to practices in corpus-building. Finally, we discuss some of the applications and the utility of the work, outlining the impact that CorCenCC is set to have on a range of different individuals and user groups.
The Decoding Success Probability of Sparse Random Linear Network Coding for Multicast
Venue: arXiv cs.IT 2020
Year: 2020

Reliable and low latency multicast communication is important for future vehicular communication. Sparse random linear network coding approach used to ensure the reliability of multicast communication has been widely investigated. A fundamental problem of such communication is to characterize the decoding success probability, which is given by the probability of a sparse random matrix over a finite field being full rank. However, the exact expression for the probability of a sparse random matrix being full rank is still unknown, and existing approximations are recursive or not consistently tight. In this paper, we provide a tight and closed-form approximation to the probability of a sparse random matrix being full rank, by presenting the explicit structure of the reduced row echelon form of a full rank matrix and using the product theorem. Simulation results show that our proposed approximation is of high accuracy regardless of the generation size, the number of coded packets, the field size and the sparsity, and tighter than the state-of-the-art approximations for a large range of parameters.
Graph Information Bottleneck for Subgraph Recognition
Venue: arXiv cs.LG 2020
Year: 2020

Given the input graph and its label/property, several key problems of graph learning, such as finding interpretable subgraphs, graph denoising and graph compression, can be attributed to the fundamental problem of recognizing a subgraph of the original one. This subgraph shall be as informative as possible, yet contains less redundant and noisy structure. This problem setting is closely related to the well-known information bottleneck (IB) principle, which, however, has less been studied for the irregular graph data and graph neural networks (GNNs). In this paper, we propose a framework of Graph Information Bottleneck (GIB) for the subgraph recognition problem in deep graph learning. Under this framework, one can recognize the maximally informative yet compressive subgraph, named IB-subgraph. However, the GIB objective is notoriously hard to optimize, mostly due to the intractability of the mutual information of irregular graph data and the unstable optimization process. In order to tackle these challenges, we propose: i) a GIB objective based-on a mutual information estimator for the irregular graph data; ii) a bi-level optimization scheme to maximize the GIB objective; iii) a connectivity loss to stabilize the optimization process. We evaluate the properties of the IB-subgraph in three application scenarios: improvement of graph classification, graph interpretation and graph denoising. Extensive experiments demonstrate that the information-theoretic IB-subgraph enjoys superior graph properties.
Joint Semantic Analysis with Document-Level Cross-Task Coherence Rewards
Venue: arXiv cs.CL 2020
Year: 2020

Coreference resolution and semantic role labeling are NLP tasks that capture different aspects of semantics, indicating respectively, which expressions refer to the same entity, and what semantic roles expressions serve in the sentence. However, they are often closely interdependent, and both generally necessitate natural language understanding. Do they form a coherent abstract representation of documents? We present a neural network architecture for joint coreference resolution and semantic role labeling for English, and train graph neural networks to model the 'coherence' of the combined shallow semantic graph. Using the resulting coherence score as a reward for our joint semantic analyzer, we use reinforcement learning to encourage global coherence over the document and between semantic annotations. This leads to improvements on both tasks in multiple datasets from different domains, and across a range of encoders of different expressivity, calling, we believe, for a more holistic approach to semantics in NLP.
Data Loss Detector: Automatically Revealing Data Loss Bugs in Android Apps
Venue: arXiv cs.SE 2020
Year: 2020

Android apps must work correctly even if their execution is interrupted by external events. For instance, an app must work properly even if a phone call is received, or after its layout is redrawn because the smartphone has been rotated. Since these events may require destroying, when the execution is interrupted, and recreating, when the execution is resumed, the foreground activity of the app, the only way to prevent the loss of state information is saving and restoring it. This behavior must be explicitly implemented by app developers, who often miss to implement it properly, releasing apps affected by data loss problems, that is, apps that may lose state information when their execution is interrupted. Although several techniques can be used to automatically generate test cases for Android apps, the obtained test cases seldom include the interactions and the checks necessary to exercise and reveal data loss faults. To address this problem, this paper presents Data Loss Detector (DLD), a test case generation technique that integrates an exploration strategy, data-loss-revealing actions, and two customized oracle strategies for the detection of data loss failures. DLD has been able to reveal 75% of the faults in a benchmark of 54 Android app releases affected by 110 known data loss faults. DLD also revealed unknown data loss problems, outperforming competing approaches.
Improving Compositional Generalization in Semantic Parsing
Venue: arXiv cs.CL 2020
Year: 2020

Generalization of models to out-of-distribution (OOD) data has captured tremendous attention recently. Specifically, compositional generalization, i.e., whether a model generalizes to new structures built of components observed during training, has sparked substantial interest. In this work, we investigate compositional generalization in semantic parsing, a natural test-bed for compositional generalization, as output programs are constructed from sub-components. We analyze a wide variety of models and propose multiple extensions to the attention module of the semantic parser, aiming to improve compositional generalization. We find that the following factors improve compositional generalization: (a) using contextual representations, such as ELMo and BERT, (b) informing the decoder what input tokens have previously been attended to, (c) training the decoder attention to agree with pre-computed token alignments, and (d) downsampling examples corresponding to frequent program templates. While we substantially reduce the gap between in-distribution and OOD generalization, performance on OOD compositions is still substantially lower.
Graph Regularized Nonnegative Tensor Ring Decomposition for Multiway Representation Learning
Venue: arXiv cs.CV 2020
Year: 2020

Tensor ring (TR) decomposition is a powerful tool for exploiting the low-rank nature of multiway data and has demonstrated great potential in a variety of important applications. In this paper, nonnegative tensor ring (NTR) decomposition and graph regularized NTR (GNTR) decomposition are proposed, where the former equips TR decomposition with local feature extraction by imposing nonnegativity on the core tensors and the latter is additionally able to capture manifold geometry information of tensor data, both significantly extend the applications of TR decomposition for nonnegative multiway representation learning. Accelerated proximal gradient based methods are derived for NTR and GNTR. The experimental result demonstrate that the proposed algorithms can extract parts-based basis with rich colors and rich lines from tensor objects that provide more interpretable and meaningful representation, and hence yield better performance than the state-of-the-art tensor based methods in clustering and classification tasks.
Hybrid Vehicular and Cloud Distributed Computing: A Case for Cooperative Perception
Venue: arXiv cs.DC 2020
Year: 2020

In this work, we propose the use of hybrid offloading of computing tasks simultaneously to edge servers (vertical offloading) via LTE communication and to nearby cars (horizontal offloading) via V2V communication, in order to increase the rate at which tasks are processed compared to local processing. Our main contribution is an optimized resource assignment and scheduling framework for hybrid offloading of computing tasks. The framework optimally utilizes the computational resources in the edge and in the micro cloud, while taking into account communication constraints and task requirements. While cooperative perception is the primary use case of our framework, the framework is applicable to other cooperative vehicular applications with high computing demand and significant transmission overhead. The framework is tested in a simulated environment built on top of car traces and communication rates exported from the Veins vehicular networking simulator. We observe a significant increase in the processing rate of cooperative perception sensor frames when hybrid offloading with optimized resource assignment is adopted. Furthermore, the processing rate increases with V2V connectivity as more computing tasks can be offloaded horizontally.
Logical Judges Challenge Human Judges on the Strange Case of B.C.-Valjean
Venue: arXiv cs.AI 2020
Year: 2020

On May 12th, 2020, during the course entitled Artificial Intelligence and Jurisdiction Practice organized by the Italian School of Magistracy, more than 70 magistrates followed our demonstration of a Prolog logical judge reasoning on an armed robbery case. Although the implemented logical judge is just an exercise of knowledge representation and simple deductive reasoning, a practical demonstration of an automated reasoning tool to such a large audience of potential end-users represents a first and unique attempt in Italy and, to the best of our knowledge, in the international panorama. In this paper we present the case addressed by the logical judge - a real case already addressed by a human judge in 2015 - and the feedback on the demonstration collected from the attendees.