OpenRaiser/Intern-Atlas huggingface dataset:
A Neighborhood-preserving Graph Summarization
Venue: arXiv cs.DS 2021
Year: 2021

We introduce in this paper a new summarization method for large graphs. Our summarization approach retains only a user-specified proportion of the neighbors of each node in the graph. Our main aim is to simplify large graphs so that they can be analyzed and processed effectively while preserving as many of the node neighborhood properties as possible. Since many graph algorithms are based on the neighborhood information available for each node, the idea is to produce a smaller graph which can be used to allow these algorithms to handle large graphs and run faster while providing good approximations. Moreover, our compression allows users to control the size of the compressed graph by adjusting the amount of information loss that can be tolerated. The experiments conducted on various real and synthetic graphs show that our compression reduces considerably the size of the graphs. Moreover, we conducted several experiments on the obtained summaries using various graph algorithms and applications, such as node embedding, graph classification and shortest path approximations. The obtained results show interesting trade-offs between the algorithms runtime speed-up and the precision loss.
Differentiable sampling of molecular geometries with uncertainty-based adversarial attacks
Venue: arXiv cs.LG 2021
Year: 2021

Neural network (NN) interatomic potentials provide fast prediction of potential energy surfaces, closely matching the accuracy of the electronic structure methods used to produce the training data. However, NN predictions are only reliable within well-learned training domains, and show volatile behavior when extrapolating. Uncertainty quantification approaches can flag atomic configurations for which prediction confidence is low, but arriving at such uncertain regions requires expensive sampling of the NN phase space, often using atomistic simulations. Here, we exploit automatic differentiation to drive atomistic systems towards high-likelihood, high-uncertainty configurations without the need for molecular dynamics simulations. By performing adversarial attacks on an uncertainty metric, informative geometries that expand the training domain of NNs are sampled. When combined to an active learning loop, this approach bootstraps and improves NN potentials while decreasing the number of calls to the ground truth method. This efficiency is demonstrated on sampling of kinetic barriers and collective variables in molecules, and can be extended to any NN potential architecture and materials system.
List-Decodable Coded Computing: Breaking the Adversarial Toleration Barrier
Venue: arXiv cs.IT 2021
Year: 2021

We consider the problem of coded computing, where a computational task is performed in a distributed fashion in the presence of adversarial workers. We propose techniques to break the adversarial toleration threshold barrier previously known in coded computing. More specifically, we leverage list-decoding techniques for folded Reed-Solomon codes and propose novel algorithms to recover the correct codeword using side information. In the coded computing setting, we show how the master node can perform certain carefully designed extra computations to obtain the side information. The workload of computing this side information is negligible compared to the computations done by each worker. This side information is then utilized to prune the output of the list decoder and uniquely recover the true outcome. We further propose folded Lagrange coded computing (FLCC) to incorporate the developed techniques into a specific coded computing setting. Our results show that FLCC outperforms LCC by breaking the barrier on the number of adversaries that can be tolerated. In particular, the corresponding threshold in FLCC is improved by a factor of two asymptotically compared to that of LCC.
The Most Informative Order Statistic and its Application to Image Denoising
Venue: arXiv cs.IT 2021
Year: 2021

We consider the problem of finding the subset of order statistics that contains the most information about a sample of random variables drawn independently from some known parametric distribution. We leverage information-theoretic quantities, such as entropy and mutual information, to quantify the level of informativeness and rigorously characterize the amount of information contained in any subset of the complete collection of order statistics. As an example, we show how these informativeness metrics can be evaluated for a sample of discrete Bernoulli and continuous Uniform random variables. Finally, we unveil how our most informative order statistics framework can be applied to image processing applications. Specifically, we investigate how the proposed measures can be used to choose the coefficients of the L-estimator filter to denoise an image corrupted by random noise. We show that both for discrete (e.g., salt-pepper noise) and continuous (e.g., mixed Gaussian noise) noise distributions, the proposed method is competitive with off-the-shelf filters, such as the median and the total variation filters, as well as with wavelet-based denoising methods.
TT-Rec: Tensor Train Compression for Deep Learning Recommendation Models
Venue: arXiv cs.LG 2021
Year: 2021

The memory capacity of embedding tables in deep learning recommendation models (DLRMs) is increasing dramatically from tens of GBs to TBs across the industry. Given the fast growth in DLRMs, novel solutions are urgently needed, in order to enable fast and efficient DLRM innovations. At the same time, this must be done without having to exponentially increase infrastructure capacity demands. In this paper, we demonstrate the promising potential of Tensor Train decomposition for DLRMs (TT-Rec), an important yet under-investigated context. We design and implement optimized kernels (TT-EmbeddingBag) to evaluate the proposed TT-Rec design. TT-EmbeddingBag is 3 times faster than the SOTA TT implementation. The performance of TT-Rec is further optimized with the batched matrix multiplication and caching strategies for embedding vector lookup operations. In addition, we present mathematically and empirically the effect of weight initialization distribution on DLRM accuracy and propose to initialize the tensor cores of TT-Rec following the sampled Gaussian distribution. We evaluate TT-Rec across three important design space dimensions -- memory capacity, accuracy, and timing performance -- by training MLPerf-DLRM with Criteo's Kaggle and Terabyte data sets. TT-Rec achieves 117 times and 112 times model size compression, for Kaggle and Terabyte, respectively. This impressive model size reduction can come with no accuracy nor training time overhead as compared to the uncompressed baseline.
MiniV2G: An Electric Vehicle Charging Emulator
Venue: arXiv cs.CR 2021
Year: 2021

The impact of global warming and the imperative to limit climate change have stimulated the need to develop new solutions based on renewable energy sources. One of the emerging trends in this endeavor are the Electric Vehicles (EVs), which use electricity instead of traditional fossil fuels as a power source, relying on the Vehicle-to-Grid (V2G) paradigm. The novelty of such a paradigm requires careful analysis to avoid malicious attempts. An attacker can exploit several surfaces, such as the remote connection between the Distribution Grid and Charging Supply or the authentication system between the charging Supply Equipment and the Electric Vehicles. However, V2G architecture's high cost and complexity in implementation can restrain this field's research capability. In this paper, we approach this limitation by proposing MiniV2G, an open-source emulator to simulate Electric Vehicle Charging (EVC) built on top of Mininet and RiseV2G. MiniV2G is particularly suitable for security researchers to study and test real V2G charging scenarios. MiniV2G can reproduce with high fidelity a V2G architecture to easily simulate an EV charging process. Finally, we present a MiniV2G application and show how MiniV2G can be used to study V2G communication and develop attacks and countermeasures that can be applied to real systems. Since we believe our tool can be of great help for research in this field, we also made it freely available.
SimBle: Generating privacy preserving real-world BLE traces with ground truth
Venue: arXiv cs.CR 2021
Year: 2021

Bluetooth has become critical as many IoT devices are arriving in the market. Most of the current literature focusing on Bluetooth simulation concentrates on the network protocols' performances and completely neglects the privacy protection recommendations introduced in the BLE standard. Indeed, privacy protection is one of the main issues handled in the Bluetooth standard. For instance, the current standard forces devices to change the identifier they embed within the public and private packets, known as MAC address randomization. Although randomizing MAC addresses is intended to preserve device privacy, recent literature shows many challenges that are still present. One of them is the correlation between the public packets and the emitters. Unfortunately, existing evaluation tools such as NS-3 are not designed to reproduce this Bluetooth standard's essential functionality. This makes it impossible to test solutions for different device-fingerprinting strategies as there is a lack of ground truth for large-scale scenarios with the majority of current BLE devices implementing MAC address randomization. In this paper, we first introduce a solution of standard-compliant MAC address randomization in the NS-3 framework, capable of emulating any real BLE device in the simulation and generating real-world Bluetooth traces. In addition, since the simulation run-time for trace-collection grows exponentially with the number of devices, we introduce an optimization to linearize public-packet sniffing. This made the large-scale trace-collection practically feasible. Then, we use the generated traces and associated ground truth to do a case study on the evaluation of a generic MAC address association available in the literature. Our case study reveals that close to 90 percent of randomized addresses could be correctly linked even in highly dense and mobile scenarios.
An extensive empirical study of inconsistent labels in multi-version-project defect data sets
Venue: arXiv cs.SE 2021
Year: 2021

The label quality of defect data sets has a direct influence on the reliability of defect prediction models. In this study, for multi-version-project defect data sets, we propose an approach to automatically detecting instances with inconsistent labels (i.e. the phenomena of instances having the same source code but different labels over multiple versions of a software project) and understand their influence on the evaluation and interpretation of defect prediction models. Based on five multi-version-project defect data sets (either widely used or the most up-to-date in the literature) collected by diverse approaches, we find that: (1) most versions in the investigated defect data sets contain inconsistent labels with varying degrees; (2) the existence of inconsistent labels in a training data set may considerably change the prediction performance of a defect prediction model as well as can lead to the identification of substantially different true defective modules; and (3) the importance ranking of independent variables in a defect prediction model can be substantially shifted due to the existence of inconsistent labels. The above findings reveal that inconsistent labels in defect data sets can profoundly change the prediction ability and interpretation of a defect prediction model. Therefore, we strongly suggest that practitioners should detect and exclude inconsistent labels in defect data sets to avoid their potential negative influence on defect prediction models. What is more, it is necessary for researchers to improve existing defect label collection approaches to reduce inconsistent labels. Furthermore, there is a need to re-examine the experimental conclusions of previous studies using multi-version-project defect data sets with a high ratio of inconsistent labels.
A note on tight projective 2-designs
Venue: arXiv cs.IT 2021
Year: 2021

We study tight projective 2-designs in three different settings. In the complex setting, Zauner's conjecture predicts the existence of a tight projective 2-design in every dimension. Pandey, Paulsen, Prakash, and Rahaman recently proposed an approach to make quantitative progress on this conjecture in terms of the entanglement breaking rank of a certain quantum channel. We show that this quantity is equal to the size of the smallest weighted projective 2-design. Next, in the finite field setting, we introduce a notion of projective 2-designs, we characterize when such projective 2-designs are tight, and we provide a construction of such objects. Finally, in the quaternionic setting, we show that every tight projective 2-design for H^d determines an equi-isoclinic tight fusion frame of d(2d-1) subspaces of R^d(2d+1) of dimension 3.
Joint Transmission Scheme and Coded Content Placement in Cluster-centric UAV-aided Cellular Networks
Venue: arXiv cs.IT 2021
Year: 2021

Recently, as a consequence of the COVID-19 pandemic, dependence on telecommunication for remote working and telemedicine has significantly increased. In cellular networks, incorporation of Unmanned Aerial Vehicles (UAVs) can result in enhanced connectivity for outdoor users due to the high probability of establishing Line of Sight (LoS) links. The UAV's limited battery life and its signal attenuation in indoor areas, however, make it inefficient to manage users' requests in indoor environments. Referred to as the Cluster centric and Coded UAV-aided Femtocaching (CCUF) framework, the network's coverage in both indoor and outdoor environments increases via a two-phase clustering for FAPs' formation and UAVs' deployment. First objective is to increase the content diversity. In this context, we propose a coded content placement in a cluster-centric cellular network, which is integrated with the Coordinated Multi-Point (CoMP) to mitigate the inter-cell interference in edge areas. Then, we compute, experimentally, the number of coded contents to be stored in each caching node to increase the cache-hit ratio, Signal-to-Interference-plus-Noise Ratio (SINR), and cache diversity and decrease the users' access delay and cache redundancy for different content popularity profiles. Capitalizing on clustering, our second objective is to assign the best caching node to indoor/outdoor users for managing their requests. In this regard, we define the movement speed of ground users as the decision metric of the transmission scheme for serving outdoor users' requests to avoid frequent handovers between FAPs and increase the battery life of UAVs. Simulation results illustrate that the proposed CCUF implementation increases the cache hit-ratio, SINR, and cache diversity and decrease the users' access delay, cache redundancy and UAVs' energy consumption.
Reducing ReLU Count for Privacy-Preserving CNN Speedup
Venue: arXiv cs.CV 2021
Year: 2021

Privacy-Preserving Machine Learning algorithms must balance classification accuracy with data privacy. This can be done using a combination of cryptographic and machine learning tools such as Convolutional Neural Networks (CNN). CNNs typically consist of two types of operations: a convolutional or linear layer, followed by a non-linear function such as ReLU. Each of these types can be implemented efficiently using a different cryptographic tool. But these tools require different representations and switching between them is time-consuming and expensive. Recent research suggests that ReLU is responsible for most of the communication bandwidth. ReLU is usually applied at each pixel (or activation) location, which is quite expensive. We propose to share ReLU operations. Specifically, the ReLU decision of one activation can be used by others, and we explore different ways to group activations and different ways to determine the ReLU for such a group of activations. Experiments on several datasets reveal that we can cut the number of ReLU operations by up to three orders of magnitude and, as a result, cut the communication bandwidth by more than 50%.
Syntactic Nuclei in Dependency Parsing -- A Multilingual Exploration
Venue: arXiv cs.CL 2021
Year: 2021

Standard models for syntactic dependency parsing take words to be the elementary units that enter into dependency relations. In this paper, we investigate whether there are any benefits from enriching these models with the more abstract notion of nucleus proposed by Tesnière. We do this by showing how the concept of nucleus can be defined in the framework of Universal Dependencies and how we can use composition functions to make a transition-based dependency parser aware of this concept. Experiments on 12 languages show that nucleus composition gives small but significant improvements in parsing accuracy. Further analysis reveals that the improvement mainly concerns a small number of dependency relations, including nominal modifiers, relations of coordination, main predicates, and direct objects.
Disembodied Machine Learning: On the Illusion of Objectivity in NLP
Venue: arXiv cs.AI 2021
Year: 2021

Machine Learning seeks to identify and encode bodies of knowledge within provided datasets. However, data encodes subjective content, which determines the possible outcomes of the models trained on it. Because such subjectivity enables marginalisation of parts of society, it is termed (social) `bias' and sought to be removed. In this paper, we contextualise this discourse of bias in the ML community against the subjective choices in the development process. Through a consideration of how choices in data and model development construct subjectivity, or biases that are represented in a model, we argue that addressing and mitigating biases is near-impossible. This is because both data and ML models are objects for which meaning is made in each step of the development pipeline, from data selection over annotation to model training and analysis. Accordingly, we find the prevalent discourse of bias limiting in its ability to address social marginalisation. We recommend to be conscientious of this, and to accept that de-biasing methods only correct for a fraction of biases.
Continuous One-Counter Automata
Venue: arXiv cs.FL 2021
Year: 2021

We study the reachability problem for continuous one-counter automata, COCA for short. In such automata, transitions are guarded by upper and lower bound tests against the counter value. Additionally, the counter updates associated with taking transitions can be (non-deterministically) scaled down by a nonzero factor between zero and one. Our three main results are as follows: (1) We prove that the reachability problem for COCA with global upper and lower bound tests is in NC2; (2) that, in general, the problem is decidable in polynomial time; and (3) that it is decidable in the polynomial hierarchy for COCA with parametric counter updates and bound tests.
BERTaú: Itaú BERT for digital customer service
Venue: arXiv cs.CL 2021
Year: 2021

In the last few years, three major topics received increased interest: deep learning, NLP and conversational agents. Bringing these three topics together to create an amazing digital customer experience and indeed deploy in production and solve real-world problems is something innovative and disruptive. We introduce a new Portuguese financial domain language representation model called BERTaú. BERTaú is an uncased BERT-base trained from scratch with data from the Itaú virtual assistant chatbot solution. Our novel contribution is that BERTaú pretrained language model requires less data, reached state-of-the-art performance in three NLP tasks, and generates a smaller and lighter model that makes the deployment feasible. We developed three tasks to validate our model: information retrieval with Frequently Asked Questions (FAQ) from Itaú bank, sentiment analysis from our virtual assistant data, and a NER solution. All proposed tasks are real-world solutions in production on our environment and the usage of a specialist model proved to be effective when compared to Google BERT multilingual and the DPRQuestionEncoder from Facebook, available at Hugging Face. The BERTaú improves the performance in 22% of FAQ Retrieval MRR metric, 2.1% in Sentiment Analysis F1 score, 4.4% in NER F1 score and can also represent the same sequence in up to 66% fewer tokens when compared to "shelf models".
VAE^2: Preventing Posterior Collapse of Variational Video Predictions in the Wild
Venue: arXiv cs.CV 2021
Year: 2021

Predicting future frames of video sequences is challenging due to the complex and stochastic nature of the problem. Video prediction methods based on variational auto-encoders (VAEs) have been a great success, but they require the training data to contain multiple possible futures for an observed video sequence. This is hard to be fulfilled when videos are captured in the wild where any given observation only has a determinate future. As a result, training a vanilla VAE model with these videos inevitably causes posterior collapse. To alleviate this problem, we propose a novel VAE structure, dabbed VAE-in-VAE or VAE$^2$. The key idea is to explicitly introduce stochasticity into the VAE. We treat part of the observed video sequence as a random transition state that bridges its past and future, and maximize the likelihood of a Markov Chain over the video sequence under all possible transition states. A tractable lower bound is proposed for this intractable objective function and an end-to-end optimization algorithm is designed accordingly. VAE$^2$ can mitigate the posterior collapse problem to a large extent, as it breaks the direct dependence between future and observation and does not directly regress the determinate future provided by the training data. We carry out experiments on a large-scale dataset called Cityscapes, which contains videos collected from a number of urban cities. Results show that VAE$^2$ is capable of predicting diverse futures and is more resistant to posterior collapse than the other state-of-the-art VAE-based approaches. We believe that VAE$^2$ is also applicable to other stochastic sequence prediction problems where training data are lack of stochasticity.
Enhancing Sequence-to-Sequence Neural Lemmatization with External Resources
Venue: arXiv cs.CL 2021
Year: 2021

We propose a novel hybrid approach to lemmatization that enhances the seq2seq neural model with additional lemmas extracted from an external lexicon or a rule-based system. During training, the enhanced lemmatizer learns both to generate lemmas via a sequential decoder and copy the lemma characters from the external candidates supplied during run-time. Our lemmatizer enhanced with candidates extracted from the Apertium morphological analyzer achieves statistically significant improvements compared to baseline models not utilizing additional lemma information, achieves an average accuracy of 97.25% on a set of 23 UD languages, which is 0.55% higher than obtained with the Stanford Stanza model on the same set of languages. We also compare with other methods of integrating external data into lemmatization and show that our enhanced system performs considerably better than a simple lexicon extension method based on the Stanza system, and it achieves complementary improvements w.r.t. the data augmentation method.