OpenRaiser/Intern-Atlas huggingface dataset:
RGCF: Refined Graph Convolution Collaborative Filtering with concise and expressive embedding
Venue: arXiv cs.LG 2020
Year: 2020

Graph Convolution Network (GCN) has attracted significant attention and become the most popular method for learning graph representations. In recent years, many efforts have been focused on integrating GCN into the recommender tasks and have made remarkable progress. At its core is to explicitly capture high-order connectivities between the nodes in user-item bipartite graph. However, we theoretically and empirically find an inherent drawback existed in these GCN-based recommendation methods, where GCN is directly applied to aggregate neighboring nodes will introduce noise and information redundancy. Consequently, the these models' capability of capturing high-order connectivities among different nodes is limited, leading to suboptimal performance of the recommender tasks. The main reason is that the the nonlinear network layer inside GCN structure is not suitable for extracting non-sematic features(such as one-hot ID feature) in the collaborative filtering scenarios. In this work, we develop a new GCN-based Collaborative Filtering model, named Refined Graph convolution Collaborative Filtering(RGCF), where the construction of the embeddings of users (items) are delicately redesigned from several aspects during the aggregation on the graph. Compared to the state-of-the-art GCN-based recommendation, RGCF is more capable for capturing the implicit high-order connectivities inside the graph and the resultant vector representations are more expressive. We conduct extensive experiments on three public million-size datasets, demonstrating that our RGCF significantly outperforms state-of-the-art models. We release our code at https://github.com/hfutmars/RGCF.
Tree Optimization Based Heuristics and Metaheuristics in Network Construction Problems
Venue: arXiv cs.AI 2020
Year: 2020

We consider a recently introduced class of network construction problems where edges of a transportation network need to be constructed by a server (construction crew). The server has a constant construction speed which is much lower than its travel speed, so relocation times are negligible with respect to construction times. It is required to find a construction schedule that minimizes a non-decreasing function of the times when various connections of interest become operational. Most problems of this class are strongly NP-hard on general networks, but are often tree-efficient, that is, polynomially solvable on trees. We develop a generic local search heuristic approach and two metaheuristics (Iterated Local Search and Tabu Search) for solving tree-efficient network construction problems on general networks, and explore them computationally. Results of computational experiments indicate that the methods have excellent performance.
Cultural Convergence: Insights into the behavior of misinformation networks on Twitter
Venue: arXiv cs.SI 2020
Year: 2020

How can the birth and evolution of ideas and communities in a network be studied over time? We use a multimodal pipeline, consisting of network mapping, topic modeling, bridging centrality, and divergence to analyze Twitter data surrounding the COVID-19 pandemic. We use network mapping to detect accounts creating content surrounding COVID-19, then Latent Dirichlet Allocation to extract topics, and bridging centrality to identify topical and non-topical bridges, before examining the distribution of each topic and bridge over time and applying Jensen-Shannon divergence of topic distributions to show communities that are converging in their topical narratives.
Total Variation Distance Based Performance Analysis of Covert Communication over AWGN Channels in Non-asymptotic Regime
Venue: arXiv cs.IT 2020
Year: 2020

This paper investigates covert communication over an additive white Gaussian noise (AWGN) channel in finite block length regime on the assumption of Gaussian codebooks. We first review some achievability and converse bounds on the throughput under maximal power constraint. From these bounds and the analysis of TVD at the adversary, the first and second asymptotics of covert communication are investigated by the help of some divergences inequalities. Furthermore, the analytic solution of TVD, and approximation expansions which can be easily evaluated with given snr (signal noise ratio) are presented. In this way, the proper power level for covert communication can be approximated with given covert constraint of TVD, which leads to more accurate estimation of the power compared with preceding bounds. Further elaboration on the effect of such asymptotic characteristics on the primary channels's throughput in finite block regime is also provided. The results will be very helpful for understanding the behavior of the total variation distance and practical covert communication.
On the Efficiency of Decentralized File Storage for Personal Information Management Systems
Venue: arXiv cs.CR 2020
Year: 2020

This paper presents an architecture, based on Distributed Ledger Technologies (DLTs) and Decentralized File Storage (DFS) systems, to support the use of Personal Information Management Systems (PIMS). DLT and DFS are used to manage data sensed by mobile users equipped with devices with sensing capability. DLTs guarantee the immutability, traceability and verifiability of references to personal data, that are stored in DFS. In fact, the inclusion of data digests in the DLT makes it possible to obtain an unalterable reference and a tamper-proof log, while remaining compliant with the regulations on personal data, i.e. GDPR. We provide an experimental evaluation on the feasibility of the use of DFS. Three different scenarios have been studied: i) a proprietary IPFS approach with a dedicated node interfacing with the data producers, ii) a public IPFS service and iii) Sia Skynet. Results show that through proper configuration of the system infrastructure, it is viable to build a decentralized Personal Data Storage (PDS).
scb-mt-en-th-2020: A Large English-Thai Parallel Corpus
Venue: arXiv cs.CL 2020
Year: 2020

The primary objective of our work is to build a large-scale English-Thai dataset for machine translation. We construct an English-Thai machine translation dataset with over 1 million segment pairs, curated from various sources, namely news, Wikipedia articles, SMS messages, task-based dialogs, web-crawled data and government documents. Methodology for gathering data, building parallel texts and removing noisy sentence pairs are presented in a reproducible manner. We train machine translation models based on this dataset. Our models' performance are comparable to that of Google Translation API (as of May 2020) for Thai-English and outperform Google when the Open Parallel Corpus (OPUS) is included in the training data for both Thai-English and English-Thai translation. The dataset, pre-trained models, and source code to reproduce our work are available for public use.
Detile: Fine-Grained Information Leak Detection in Script Engines
Venue: arXiv cs.CR 2020
Year: 2020

Memory disclosure attacks play an important role in the exploitation of memory corruption vulnerabilities. By analyzing recent research, we observe that bypasses of defensive solutions that enforce control-flow integrity or attempt to detect return-oriented programming require memory disclosure attacks as a fundamental first step. However, research lags behind in detecting such information leaks. In this paper, we tackle this problem and present a system for fine-grained, automated detection of memory disclosure attacks against scripting engines. The basic insight is as follows: scripting languages, such as JavaScript in web browsers, are strictly sandboxed. They must not provide any insights about the memory layout in their contexts. In fact, any such information potentially represents an ongoing memory disclosure attack. Hence, to detect information leaks, our system creates a clone of the scripting engine process with a re-randomized memory layout. The clone is instrumented to be synchronized with the original process. Any inconsistency in the script contexts of both processes appears when a memory disclosure was conducted to leak information about the memory layout. Based on this detection approach, we have designed and implemented Detile (\underline{det}ection of \underline{i}nformation \underline{le}aks), a prototype for the JavaScript engine in Microsoft's Internet Explorer 10/11 on Windows 8.0/8.1. An empirical evaluation shows that our tool can successfully detect memory disclosure attacks even against this proprietary software.
Expressiveness of SETAFs and Support-Free ADFs under 3-valued Semantics
Venue: arXiv cs.AI 2020
Year: 2020

Generalizing the attack structure in argumentation frameworks (AFs) has been studied in different ways. Most prominently, the binary attack relation of Dung frameworks has been extended to the notion of collective attacks. The resulting formalism is often termed SETAFs. Another approach is provided via abstract dialectical frameworks (ADFs), where acceptance conditions specify the relation between arguments; restricting these conditions naturally allows for so-called support-free ADFs. The aim of the paper is to shed light on the relation between these two different approaches. To this end, we investigate and compare the expressiveness of SETAFs and support-free ADFs under the lens of 3-valued semantics. Our results show that it is only the presence of unsatisfiable acceptance conditions in support-free ADFs that discriminate the two approaches.
Detecting Signatures of Early-stage Dementia with Behavioural Models Derived from Sensor Data
Venue: arXiv cs.CY 2020
Year: 2020

There is a pressing need to automatically understand the state and progression of chronic neurological diseases such as dementia. The emergence of state-of-the-art sensing platforms offers unprecedented opportunities for indirect and automatic evaluation of disease state through the lens of behavioural monitoring. This paper specifically seeks to characterise behavioural signatures of mild cognitive impairment (MCI) and Alzheimer's disease (AD) in the \textit{early} stages of the disease. We introduce bespoke behavioural models and analyses of key symptoms and deploy these on a novel dataset of longitudinal sensor data from persons with MCI and AD. We present preliminary findings that show the relationship between levels of sleep quality and wandering can be subtly different between patients in the early stages of dementia and healthy cohabiting controls.
Lower Bounds for XOR of Forrelations
Venue: arXiv cs.CC 2020
Year: 2020

The Forrelation problem, introduced by Aaronson [A10] and Aaronson and Ambainis [AA15], is a well studied problem in the context of separating quantum and classical models. Variants of this problem were used to give exponential separations between quantum and classical query complexity [A10, AA15]; quantum query complexity and bounded-depth circuits [RT19]; and quantum and classical communication complexity [GRT19]. In all these separations, the lower bound for the classical model only holds when the advantage of the protocol (over a random guess) is more than $\approx 1/\sqrt{N}$, that is, the success probability is larger than $\approx 1/2 + 1/\sqrt{N}$. To achieve separations when the classical protocol has smaller advantage, we study in this work the XOR of $k$ independent copies of the Forrelation function (where $k\ll N$). We prove a very general result that shows that any family of Boolean functions that is closed under restrictions, whose Fourier mass at level $2k$ is bounded by $α^k$, cannot compute the XOR of $k$ independent copies of the Forrelation function with advantage better than $O\left(\frac{α^k}{N^{k/2}}\right)$. This is a strengthening of a result of [CHLT19], that gave a similar result for $k=1$, using the technique of [RT19]. As an application of our result, we give the first example of a partial Boolean function that can be computed by a simultaneous-message quantum protocol of cost $\mbox{polylog}(N)$ (when players share $\mbox{polylog}(N)$ EPR pairs), however, any classical interactive randomized protocol of cost at most $\tilde{o}(N^{1/4})$, has quasipolynomially small advantage over a random guess. We also give the first example of a partial Boolean function that has a quantum query algorithm of cost $\mbox{polylog}(N)$, and such that, any constant-depth circuit of quasipolynomial size has quasipolynomially small advantage over a random guess.
Learning while Respecting Privacy and Robustness to Distributional Uncertainties and Adversarial Data
Venue: arXiv cs.LG 2020
Year: 2020

Data used to train machine learning models can be adversarial--maliciously constructed by adversaries to fool the model. Challenge also arises by privacy, confidentiality, or due to legal constraints when data are geographically gathered and stored across multiple learners, some of which may hold even an "anonymized" or unreliable dataset. In this context, the distributionally robust optimization framework is considered for training a parametric model, both in centralized and federated learning settings. The objective is to endow the trained model with robustness against adversarially manipulated input data, or, distributional uncertainties, such as mismatches between training and testing data distributions, or among datasets stored at different workers. To this aim, the data distribution is assumed unknown, and lies within a Wasserstein ball centered around the empirical data distribution. This robust learning task entails an infinite-dimensional optimization problem, which is challenging. Leveraging a strong duality result, a surrogate is obtained, for which three stochastic primal-dual algorithms are developed: i) stochastic proximal gradient descent with an $ε$-accurate oracle, which invokes an oracle to solve the convex sub-problems; ii) stochastic proximal gradient descent-ascent, which approximates the solution of the convex sub-problems via a single gradient ascent step; and, iii) a distributionally robust federated learning algorithm, which solves the sub-problems locally at different workers where data are stored. Compared to the empirical risk minimization and federated learning methods, the proposed algorithms offer robustness with little computation overhead. Numerical tests using image datasets showcase the merits of the proposed algorithms under several existing adversarial attacks and distributional uncertainties.
Resource-Aware Protocols for Network Cost-Sharing Games
Venue: arXiv cs.GT 2020
Year: 2020

We study the extent to which decentralized cost-sharing protocols can achieve good price of anarchy (PoA) bounds in network cost-sharing games with $n$ agents. We focus on the model of resource-aware protocols, where the designer has prior access to the network structure and can also increase the total cost of an edge(overcharging), and we study classes of games with concave or convex cost functions. We first consider concave cost functions and our main result is a cost-sharing protocol for symmetric games on directed acyclic graphs that achieves a PoA of $2+\varepsilon$ for some arbitrary small positive $\varepsilon$, which improves to $1+\varepsilon$ for games with at least two players. We also achieve a PoA of 1 for series-parallel graphs and show that no protocol can achieve a PoA better than $Ω(\sqrt{n})$ for multicast games. We then also consider convex cost functions and prove analogous results for series-parallel networks and multicast games, as well as a lower bound of $Ω(n)$ for the PoA on directed acyclic graphs without the use of overcharging.
Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learning
Venue: arXiv cs.LG 2020
Year: 2020

The problem of Offline Policy Evaluation (OPE) in Reinforcement Learning (RL) is a critical step towards applying RL in real-life applications. Existing work on OPE mostly focus on evaluating a fixed target policy $π$, which does not provide useful bounds for offline policy learning as $π$ will then be data-dependent. We address this problem by simultaneously evaluating all policies in a policy class $Π$ -- uniform convergence in OPE -- and obtain nearly optimal error bounds for a number of global / local policy classes. Our results imply that the model-based planning achieves an optimal episode complexity of $\widetilde{O}(H^3/d_mε^2)$ in identifying an $ε$-optimal policy under the time-inhomogeneous episodic MDP model ($H$ is the planning horizon, $d_m$ is a quantity that reflects the exploration of the logging policy $μ$). To the best of our knowledge, this is the first time the optimal rate is shown to be possible for the offline RL setting and the paper is the first that systematically investigates the uniform convergence in OPE.
Evaluating German Transformer Language Models with Syntactic Agreement Tests
Venue: arXiv cs.CL 2020
Year: 2020

Pre-trained transformer language models (TLMs) have recently refashioned natural language processing (NLP): Most state-of-the-art NLP models now operate on top of TLMs to benefit from contextualization and knowledge induction. To explain their success, the scientific community conducted numerous analyses. Besides other methods, syntactic agreement tests were utilized to analyse TLMs. Most of the studies were conducted for the English language, however. In this work, we analyse German TLMs. To this end, we design numerous agreement tasks, some of which consider peculiarities of the German language. Our experimental results show that state-of-the-art German TLMs generally perform well on agreement tasks, but we also identify and discuss syntactic structures that push them to their limits.
Towards a practical measure of interference for reinforcement learning
Venue: arXiv cs.LG 2020
Year: 2020

Catastrophic interference is common in many network-based learning systems, and many proposals exist for mitigating it. But, before we overcome interference we must understand it better. In this work, we provide a definition of interference for control in reinforcement learning. We systematically evaluate our new measures, by assessing correlation with several measures of learning performance, including stability, sample efficiency, and online and offline control performance across a variety of learning architectures. Our new interference measure allows us to ask novel scientific questions about commonly used deep learning architectures. In particular we show that target network frequency is a dominating factor for interference, and that updates on the last layer result in significantly higher interference than updates internal to the network. This new measure can be expensive to compute; we conclude with motivation for an efficient proxy measure and empirically demonstrate it is correlated with our definition of interference.
The impact of political party/candidate on the election results from a sentiment analysis perspective using #AnambraDecides2017 tweets
Venue: arXiv cs.SI 2020
Year: 2020

This work investigates empirically the impact of political party control over its candidates or vice versa on winning an election using a natural language processing technique called sentiment analysis (SA). To do this, a set of 7430 tweets bearing or related to #AnambraDecides2017 was streamed during the November 18, 2017, Anambra State gubernatorial election. These are Twitter discussions on the top five political parties and their candidates termed political actors in this paper. We conduct polarity and subjectivity sentiment analyses on all the tweets considering time as a useful dimension of SA. Furthermore, we use the word frequency to find words most associated with the political actors in a given time. We find most talked about topics using a topic modeling algorithm and how the computed sentiments and most frequent words are related to the topics per political actor. Among other things, we deduced from the experimental results that even though a political party serves as a platform that sales the personality of a candidate, the acceptance of the candidate/party adds to the winning of an election. For example, we found the winner of the election Willie Obiano benefiting from the values his party share among the people of the State. Associating his name with his party, All Progressive Grand Alliance (APGA) displays more positive sentiments and the subjective sentiment analysis indicates that Twitter users mentioning APGA are less emotionally subjective in their tweets than the other parties.
Energy Efficient Cross Layer Time Synchronization in Cognitive Radio Networks
Venue: arXiv cs.NI 2020
Year: 2020

Time synchronization is a vital concern for any Cognitive Radio Network (CRN) to perform dynamic spectrum management. Each Cognitive Radio (CR) node has to be environment aware and self adaptive and must have the ability to switch between multiple modulation schemes and frequencies. Achieving same notion of time within these CR nodes is essential to fulfill the requirements for simultaneous quiet periods for spectrum sensing. Current application layer time synchronization protocols require multiple timestamp exchanges to estimate skew between the clocks of CRN nodes. The proposed symbol timing recovery method already estimates the skew of hardware clock at the physical layer and use it for skew correction of application layer clock of each node. The heart of application layer clock is the hardware clock and hence application layer clock skew will be same as of physical layer and can be corrected from symbol timing recovery process. So one timestamp is enough to synchronize two CRN nodes. This conserves the energy utilized by application layer protocol and makes a CRN energy efficient and can achieve time synchronization in short span.
BlockFLow: An Accountable and Privacy-Preserving Solution for Federated Learning
Venue: arXiv cs.LG 2020
Year: 2020

Federated learning enables the development of a machine learning model among collaborating agents without requiring them to share their underlying data. However, malicious agents who train on random data, or worse, on datasets with the result classes inverted, can weaken the combined model. BlockFLow is an accountable federated learning system that is fully decentralized and privacy-preserving. Its primary goal is to reward agents proportional to the quality of their contribution while protecting the privacy of the underlying datasets and being resilient to malicious adversaries. Specifically, BlockFLow incorporates differential privacy, introduces a novel auditing mechanism for model contribution, and uses Ethereum smart contracts to incentivize good behavior. Unlike existing auditing and accountability methods for federated learning systems, our system does not require a centralized test dataset, sharing of datasets between the agents, or one or more trusted auditors; it is fully decentralized and resilient up to a 50% collusion attack in a malicious trust model. When run on the public Ethereum blockchain, BlockFLow uses the results from the audit to reward parties with cryptocurrency based on the quality of their contribution. We evaluated BlockFLow on two datasets that offer classification tasks solvable via logistic regression models. Our results show that the resultant auditing scores reflect the quality of the honest agents' datasets. Moreover, the scores from dishonest agents are statistically lower than those from the honest agents. These results, along with the reasonable blockchain costs, demonstrate the effectiveness of BlockFLow as an accountable federated learning system.