OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Privacy Preserving Edge Computing Framework for Image Classification
Venue: arXiv cs.LG 2021
Year: 2021

In order to extract knowledge from the large data collected by edge devices, traditional cloud based approach that requires data upload may not be feasible due to communication bandwidth limitation as well as privacy and security concerns of end users. To address these challenges, a novel privacy preserving edge computing framework is proposed in this paper for image classification. Specifically, autoencoder will be trained unsupervised at each edge device individually, then the obtained latent vectors will be transmitted to the edge server for the training of a classifier. This framework would reduce the communications overhead and protect the data of the end users. Comparing to federated learning, the training of the classifier in the proposed framework does not subject to the constraints of the edge devices, and the autoencoder can be trained independently at each edge device without any server involvement. Furthermore, the privacy of the end users' data is protected by transmitting latent vectors without additional cost of encryption. Experimental results provide insights on the image classification performance vs. various design parameters such as the data compression ratio of the autoencoder and the model complexity.
PageRank and The K-Means Clustering Algorithm
Venue: arXiv cs.LG 2021
Year: 2021

We utilize the PageRank vector to generalize the $k$-means clustering algorithm to directed and undirected graphs. We demonstrate that PageRank and other centrality measures can be used in our setting to robustly compute centrality of nodes in a given graph. Furthermore, we show how our method can be generalized to metric spaces and apply it to other domains such as point clouds and triangulated meshes
The Hateful Memes Challenge: Detecting Hate Speech in Multimodal Memes
Venue: arXiv cs.AI 2021
Year: 2021

This work proposes a new challenge set for multimodal classification, focusing on detecting hate speech in multimodal memes. It is constructed such that unimodal models struggle and only multimodal models can succeed: difficult examples ("benign confounders") are added to the dataset to make it hard to rely on unimodal signals. The task requires subtle reasoning, yet is straightforward to evaluate as a binary classification problem. We provide baseline performance numbers for unimodal models, as well as for multimodal models with various degrees of sophistication. We find that state-of-the-art methods perform poorly compared to humans (64.73% vs. 84.7% accuracy), illustrating the difficulty of the task and highlighting the challenge that this important problem poses to the community.
Contra-*: Mechanisms for Countering Spam Attacks on Blockchain's Memory Pools
Venue: arXiv cs.CR 2021
Year: 2021

Blockchain-based cryptocurrencies, such as Bitcoin, have seen on the rise in their popularity and value, making them a target to several forms of Denial-of-Service (DoS) attacks, and calling for a better understanding of their attack surface from both security and distributed systems standpoints. In this paper, and in the pursuit of understanding the attack surface of blockchains, we explore a new form of attack that can be carried out on the memory pools (mempools) and mainly targets blockchain-based cryptocurrencies. We study this attack on Bitcoin mempool and explore the attack effects on transactions fee paid by benign users. To counter this attack, this paper further proposes Contra-*:, a set of countermeasures utilizing fee, age, and size (thus, Contra-F, Contra-A, and Contra-S) as prioritization mechanisms. Contra-*: optimize the mempool size and help in countering the effects of DoS attacks due to spam transactions. We evaluate Contra-* by simulations and analyze their effectiveness under various attack conditions.
Propagation Graph Estimation from Individual's Time Series of Observed States
Venue: arXiv cs.AI 2021
Year: 2021

Various things propagate through the medium of individuals. Some individuals follow the others and take the states similar to their states a small number of time steps later. In this paper, we study the problem of estimating the state propagation order of individuals from the real-valued state sequences of all the individuals. We propose a method to estimate the propagation direction between individuals by the sum of the time delay of one individual's state positions from the other individual's matched state position averaged over the minimum cost alignments and show how to calculate it efficiently. The propagation order estimated by our proposed method is demonstrated to be significantly more accurate than that by a baseline method for our synthetic datasets, and also to be consistent with visually recognizable propagation orders for the dataset of Japanese stock price time series and biological cell firing state sequences.
Neural Architecture Transfer
Venue: arXiv cs.CV 2021
Year: 2021

Neural architecture search (NAS) has emerged as a promising avenue for automatically designing task-specific neural networks. Existing NAS approaches require one complete search for each deployment specification of hardware or objective. This is a computationally impractical endeavor given the potentially large number of application scenarios. In this paper, we propose Neural Architecture Transfer (NAT) to overcome this limitation. NAT is designed to efficiently generate task-specific custom models that are competitive under multiple conflicting objectives. To realize this goal we learn task-specific supernets from which specialized subnets can be sampled without any additional training. The key to our approach is an integrated online transfer learning and many-objective evolutionary search procedure. A pre-trained supernet is iteratively adapted while simultaneously searching for task-specific subnets. We demonstrate the efficacy of NAT on 11 benchmark image classification tasks ranging from large-scale multi-class to small-scale fine-grained datasets. In all cases, including ImageNet, NATNets improve upon the state-of-the-art under mobile settings ($\leq$ 600M Multiply-Adds). Surprisingly, small-scale fine-grained datasets benefit the most from NAT. At the same time, the architecture search and transfer is orders of magnitude more efficient than existing NAS methods. Overall, the experimental evaluation indicates that, across diverse image classification tasks and computational objectives, NAT is an appreciably more effective alternative to conventional transfer learning of fine-tuning weights of an existing network architecture learned on standard datasets. Code is available at https://github.com/human-analysis/neural-architecture-transfer
CapablePtrs: Securely Compiling Partial Programs Using the Pointers-as-Capabilities Principle
Venue: arXiv cs.PL 2021
Year: 2021

Capability machines such as CHERI provide memory capabilities that can be used by compilers to provide security benefits for compiled code (e.g., memory safety). The existing C to CHERI compiler, for example, achieves memory safety by following a principle called "pointers as capabilities" (PAC). Informally, PAC says that a compiler should represent a source language pointer as a machine code capability. But the security properties of PAC compilers are not yet well understood. We show that memory safety is only one aspect, and that PAC compilers can provide significant additional security guarantees for partial programs: the compiler can provide security guarantees for a compilation unit, even if that compilation unit is later linked to attacker-provided machine code. As such, this paper is the first to study the security of PAC compilers for partial programs formally. We prove for a model of such a compiler that it is fully abstract. The proof uses a novel proof technique (dubbed TrICL, read trickle), which should be of broad interest because it reuses the whole-program compiler correctness relation for full abstraction, thus saving work. We also implement our scheme for C on CHERI, show that we can compile legacy C code with minimal changes, and show that the performance overhead of compiled code is roughly proportional to the number of cross-compilation-unit function calls.
Detecting and analyzing collusive entities on YouTube
Venue: arXiv cs.SI 2021
Year: 2021

In this work, we provide an in-depth analysis of collusive entities on YouTube fostered by various blackmarket services. Following this, we propose models to detect three types of collusive YouTube entities - videos seeking collusive likes, channels seeking collusive subscriptions, and videos seeking collusive comments. The third type of entity is associated with temporal information. To detect videos and channels for collusive likes and subscriptions respectively, we utilize one-class classifiers trained on our curated collusive entities and a set of novel features. The SVM-based model shows significant performance with a true positive rate of 0.911 and 0.910 for detecting collusive videos and collusive channels respectively. To detect videos seeking collusive comments, we propose CollATe, a novel end-to-end neural architecture that leverages time-series information of posted comments along with static metadata of videos. CollATe is composed of three components - metadata feature extractor (which derives metadata-based features from videos), anomaly feature extractor (which utilizes the comment time-series data to detect sudden changes in the commenting activity), and comment feature extractor (which utilizes the text of the comments posted during collusion and computes a similarity score between the comments). Extensive experiments show the effectiveness of CollATe (with a true positive rate of 0.905) over the baselines.
POSNoise: An Effective Countermeasure Against Topic Biases in Authorship Analysis
Venue: arXiv cs.CL 2021
Year: 2021

Authorship verification (AV) is a fundamental research task in digital text forensics, which addresses the problem of whether two texts were written by the same person. In recent years, a variety of AV methods have been proposed that focus on this problem and can be divided into two categories: The first category refers to such methods that are based on explicitly defined features, where one has full control over which features are considered and what they actually represent. The second category, on the other hand, relates to such AV methods that are based on implicitly defined features, where no control mechanism is involved, so that any character sequence in a text can serve as a potential feature. However, AV methods belonging to the second category bear the risk that the topic of the texts may bias their classification predictions, which in turn may lead to misleading conclusions regarding their results. To tackle this problem, we propose a preprocessing technique called POSNoise, which effectively masks topic-related content in a given text. In this way, AV methods are forced to focus on such text units that are more related to the writing style. Our empirical evaluation based on six AV methods (falling into the second category) and seven corpora shows that POSNoise leads to better results compared to a well-known topic masking approach in 34 out of 42 cases, with an increase in accuracy of up to 10%.
An Efficient Shared-memory Parallel Sinkhorn-Knopp Algorithm to Compute the Word Mover's Distance
Venue: arXiv cs.LG 2021
Year: 2021

The Word Mover's Distance (WMD) is a metric that measures the semantic dissimilarity between two text documents by computing the cost of moving all words of a source/query document to the most similar words of a target document optimally. Computing WMD between two documents is costly because it requires solving an optimization problem that costs \(O(V^3log(V))\) where \(V\) is the number of unique words in the document. Fortunately, the WMD can be framed as the Earth Mover's Distance (EMD) (also known as the Optimal Transportation Distance) for which it has been shown that the algorithmic complexity can be reduced to \(O(V^2)\) by adding an entropy penalty to the optimization problem and a similar idea can be adapted to compute WMD efficiently. Additionally, the computation can be made highly parallel by computing WMD of a single query document against multiple target documents at once (e.g., finding whether a given tweet is similar to any other tweets happened in a day). In this paper, we present a shared-memory parallel Sinkhorn-Knopp Algorithm to compute the WMD of one document against many other documents by adopting the \(O(V^2)\) EMD algorithm. We used algorithmic transformations to change the original dense compute-heavy kernel to a sparse compute kernel and obtained \(67\times\) speedup using \(96\) cores on the state-of-the-art of Intel\textregistered{} 4-sockets Cascade Lake machine w.r.t. its sequential run. Our parallel algorithm is over \(700\times\) faster than the naive parallel python code that internally uses optimized matrix library calls.
Echo State Networks trained by Tikhonov least squares are L2(μ) approximators of ergodic dynamical systems
Venue: arXiv cs.LG 2021
Year: 2021

Echo State Networks (ESNs) are a class of single-layer recurrent neural networks with randomly generated internal weights, and a single layer of tuneable outer weights, which are usually trained by regularised linear least squares regression. Remarkably, ESNs still enjoy the universal approximation property despite the training procedure being entirely linear. In this paper, we prove that an ESN trained on a sequence of observations from an ergodic dynamical system (with invariant measure $μ$) using Tikhonov least squares regression against a set of targets, will approximate the target function in the $L^2(μ)$ norm. In the special case that the targets are future observations, the ESN is learning the next step map, which allows time series forecasting. We demonstrate the theory numerically by training an ESN using Tikhonov least squares on a sequence of scalar observations of the Lorenz system.
A Polynomial-Time Algorithm for Unconstrained Binary Quadratic Optimization
Venue: arXiv cs.DS 2021
Year: 2021

In this paper, an exact algorithm in polynomial time is developed to solve unrestricted binary quadratic programs. The computational complexity is $O\left( n^{\frac{15}{2}}\right) $, although very conservative, it is sufficient to prove that this minimization problem is in the complexity class $P$. The implementation aspects are also described in detail with a special emphasis on the transformation of the quadratic program into a linear program that can be solved in polynomial time. The algorithm was implemented in MATLAB and checked by generating five million matrices of arbitrary dimensions up to 30 with random entries in the range $\left[ -50,50\right] $. All the experiments carried out have revealed that the method works correctly.
Evaluating Mixed-Initiative Procedural Level Design Tools using a Triple-Blind Mixed-Method User Study
Venue: arXiv cs.NE 2021
Year: 2021

Results from a triple-blind mixed-method user study into the effectiveness of mixed-initiative tools for the procedural generation of game levels are presented. A tool which generates levels using interactive evolutionary optimisation was designed for this study which (a) is focused on supporting the designer to explore the design space and (b) only requires the designer to interact with it by designing levels. The tool identifies level design patterns in an initial hand-designed map and uses that information to drive an interactive optimisation algorithm. A rigorous user study was designed which compared the experiences of designers using the mixed-initiative tool to designers who were given a tool which provided completely random level suggestions. The designers using the mixed-initiative tool showed an increased engagement in the level design task, reporting that it was effective in inspiring new ideas and design directions. This provides significant evidence that procedural content generation can be used as a powerful tool to support the human design process.
Why Do Smart Contracts Self-Destruct? Investigating the Selfdestruct Function on Ethereum
Venue: arXiv cs.SE 2021
Year: 2021

The selfdestruct function is provided by Ethereum smart contracts to destroy a contract on the blockchain system. However, it is a double-edged sword for developers. On the one hand, using selfdestruct function enables developers to remove smart contracts (SC) from Ethereum and transfers Ethers when emergency situations happen, e.g. being attacked. On the other hand, this function can increase the complexity for the development and open an attack vector for attackers. To better understand the reasons why SC developers include or exclude the selfdestruct function in their contracts, we conducted an online survey to collect feedback from them and summarize the key reasons. Their feedback shows that 66.67% of the developers will deploy an updated contract to the Ethereum after destructing the old contract. According to this information, we propose a method to find the self-destructed contracts (also called predecessor contracts) and their updated version (successor contracts) by computing the code similarity. By analyzing the difference between the predecessor contracts and their successor contracts, we found five reasons that led to the death of the contracts; two of them (i.e., Unmatched ERC20 Token and Limits of Permission) might affect the life span of contracts. We developed a tool named LifeScope to detect these problems. LifeScope reports 0 false positives or negatives in detecting Unmatched ERC20 Token. In terms of Limits of Permission, LifeScope achieves 77.89% of F-measure and 0.8673 of AUC in average. According to the feedback of developers who exclude selfdestruct functions, we propose suggestions to help developers use selfdestruct functions in Ethereum smart contracts better.
The Missing Path: Analysing Incompleteness in Knowledge Graphs
Venue: arXiv cs.HC 2021
Year: 2021

Knowledge Graphs (KG) allow to merge and connect heterogeneous data despite their differences; they are incomplete by design. Yet, KG data producers need to ensure the best level of completeness, as far as possible. The difficulty is that they have no means to distinguish cases where incomplete entities could and should be fixed. We present a new visualisation tool: The Missing Path, to support them in identifying coherent subsets of entities that can be repaired. It relies on a map, grouping entities according to their incomplete profile. The map is coordinated with histograms and stacked charts to support interactive exploration and analysis; the summary of a subset can be compared with the one of the full collection to reveal its distinctive features. We conduct an iterative design process and evaluation with 9 Wikidata contributors. Participants gain insights and find various strategies to identify coherent subsets to be fixed.
Neutral bots probe political bias on social media
Venue: arXiv cs.SI 2021
Year: 2021

Social media platforms attempting to curb abuse and misinformation have been accused of political bias. We deploy neutral social bots who start following different news sources on Twitter, and track them to probe distinct biases emerging from platform mechanisms versus user interactions. We find no strong or consistent evidence of political bias in the news feed. Despite this, the news and information to which U.S. Twitter users are exposed depend strongly on the political leaning of their early connections. The interactions of conservative accounts are skewed toward the right, whereas liberal accounts are exposed to moderate content shifting their experience toward the political center. Partisan accounts, especially conservative ones, tend to receive more followers and follow more automated accounts. Conservative accounts also find themselves in denser communities and are exposed to more low-credibility content.
Usage of Network Simulators in Machine-Learning-Assisted 5G/6G Networks
Venue: arXiv cs.NI 2021
Year: 2021

Without any doubt, Machine Learning (ML) will be an important driver of future communications due to its foreseen performance when applied to complex problems. However, the application of ML to networking systems raises concerns among network operators and other stakeholders, especially regarding trustworthiness and reliability. In this paper, we devise the role of network simulators for bridging the gap between ML and communications systems. In particular, we present an architectural integration of simulators in ML-aware networks for training, testing, and validating ML models before being applied to the operative network. Moreover, we provide insights on the main challenges resulting from this integration, and then give hints discussing how they can be overcome. Finally, we illustrate the integration of network simulators into ML-assisted communications through a proof-of-concept testbed implementation of a residential Wi-Fi network.
Certifiably Optimal Monocular Hand-Eye Calibration
Venue: arXiv cs.RO 2021
Year: 2021

Correct fusion of data from two sensors is not possible without an accurate estimate of their relative pose, which can be determined through the process of extrinsic calibration. When two or more sensors are capable of producing their own egomotion estimates (i.e., measurements of their trajectories through an environment), the 'hand-eye' formulation of extrinsic calibration can be employed. In this paper, we extend our recent work on a convex optimization approach for hand-eye calibration to the case where one of the sensors cannot observe the scale of its translational motion (e.g., a monocular camera observing an unmapped environment). We prove that our technique is able to provide a certifiably globally optimal solution to both the known- and unknown-scale variants of hand-eye calibration, provided that the measurement noise is bounded. Herein, we focus on the theoretical aspects of the problem, show the tightness and stability of our solution, and demonstrate the optimality and speed of our algorithm through experiments with synthetic data.
Achieving Online Regression Performance of LSTMs with Simple RNNs
Venue: arXiv cs.LG 2021
Year: 2021

Recurrent Neural Networks (RNNs) are widely used for online regression due to their ability to generalize nonlinear temporal dependencies. As an RNN model, Long-Short-Term-Memory Networks (LSTMs) are commonly preferred in practice, as these networks are capable of learning long-term dependencies while avoiding the vanishing gradient problem. However, due to their large number of parameters, training LSTMs requires considerably longer training time compared to simple RNNs (SRNNs). In this paper, we achieve the online regression performance of LSTMs with SRNNs efficiently. To this end, we introduce a first-order training algorithm with a linear time complexity in the number of parameters. We show that when SRNNs are trained with our algorithm, they provide very similar regression performance with the LSTMs in two to three times shorter training time. We provide strong theoretical analysis to support our experimental results by providing regret bounds on the convergence rate of our algorithm. Through an extensive set of experiments, we verify our theoretical work and demonstrate significant performance improvements of our algorithm with respect to LSTMs and the other state-of-the-art learning models.