OpenRaiser/Intern-Atlas huggingface dataset:
Block-Structured Integer and Linear Programming in Strongly Polynomial and Near Linear Time
Venue: arXiv cs.CC 2020
Year: 2020

We consider integer and linear programming problems for which the linear constraints exhibit a (recursive) block-structure: The problem decomposes into independent and efficiently solvable sub-problems if a small number of constraints is deleted. A prominent example are $n$-fold integer programming problems and their generalizations which have received considerable attention in the recent literature. The previously known algorithms for these problems are based on the augmentation framework, a tailored integer programming variant of local search. In this paper we propose a different approach. Our algorithm relies on parametric search and a new proximity bound. We show that block-structured linear programming can be solved efficiently via an adaptation of a parametric search framework by Norton, Plotkin, and Tardos in combination with Megiddo's multidimensional search technique. This also forms a subroutine of our algorithm for the integer programming case by solving a strong relaxation of it. Then we show that, for any given optimal vertex solution of this relaxation, there is an optimal integer solution within $\ell_1$-distance independent of the dimension of the problem. This in turn allows us to find an optimal integer solution efficiently. We apply our techniques to integer and linear programming with $n$-fold structure or bounded dual treedepth, two benchmark problems in this field. We obtain the first algorithms for these cases that are both near-linear in the dimension of the problem and strongly polynomial. Moreover, unlike the augmentation algorithms, our approach is highly parallelizable.
Blockchain using Proof-of-Interaction
Venue: arXiv cs.CR 2020
Year: 2020

This paper we define a new Puzzle called Proof-of-Interaction and we show how it can replace, in the Bitcoin protocol, the Proof-of-Work algorithm.
Relationship between the visibility of political leaders during campaign and the outcome in general elections. A case study for Spain
Venue: arXiv cs.CY 2020
Year: 2020

In this article, the authors find the evidence that media coverage consisting of 13 online newspapers enhanced the electoral results of right wing party in Spain (Vox) during general elections in November 2019. We consider the political parties and leaders mentions in these media during the electoral campaign from 1st to 10th November 2019, and only visibility or prominence dimension is necessary for the evidence.
High-speed KATAN Ciphers on-a-Chip
Venue: arXiv cs.CR 2020
Year: 2020

Security in embedded systems has become a main requirement in modern electronic devices. The demand for low-cost and highly secure cryptographic algorithms is increasingly growing in fields such as mobile telecommunications, handheld devices, etc. In this paper, we analyze and evaluate the development of cheap and relatively fast hardware implementations of the KATAN family of block ciphers. KATAN is a family of six hardware oriented block ciphers. All KATAN ciphers share an 80-bit key and have 32, 48, or 64-bit blocks. We use VHDL under Altera Quartus in conjunction with ModelSim to implement and analyze our hardware designs. The developed designs are mapped onto high-performance Field Programmable Gate Arrays. We compare our findings with similar hardware implementations and C software versions of the algorithms. The performance analysis of the C implementations is done using Intel Vtune Amplifier running on Dell precision T7500 with its dual quad-core Xeon processor and 24 GB of RAM. The obtained results show better performance when compared with existing hardware and software implementations.
An enhanced Tree-LSTM architecture for sentence semantic modeling using typed dependencies
Venue: arXiv cs.CL 2020
Year: 2020

Tree-based Long short term memory (LSTM) network has become state-of-the-art for modeling the meaning of language texts as they can effectively exploit the grammatical syntax and thereby non-linear dependencies among words of the sentence. However, most of these models cannot recognize the difference in meaning caused by a change in semantic roles of words or phrases because they do not acknowledge the type of grammatical relations, also known as typed dependencies, in sentence structure. This paper proposes an enhanced LSTM architecture, called relation gated LSTM, which can model the relationship between two inputs of a sequence using a control input. We also introduce a Tree-LSTM model called Typed Dependency Tree-LSTM that uses the sentence dependency parse structure as well as the dependency type to embed sentence meaning into a dense vector. The proposed model outperformed its type-unaware counterpart in two typical NLP tasks - Semantic Relatedness Scoring and Sentiment Analysis, in a lesser number of training epochs. The results were comparable or competitive with other state-of-the-art models. Qualitative analysis showed that changes in the voice of sentences had little effect on the model's predicted scores, while changes in nominal (noun) words had a more significant impact. The model recognized subtle semantic relationships in sentence pairs. The magnitudes of learned typed dependencies embeddings were also in agreement with human intuitions. The research findings imply the significance of grammatical relations in sentence modeling. The proposed models would serve as a base for future researches in this direction.
Strategyproof Facility Location Mechanisms with Richer Action Spaces
Venue: arXiv cs.GT 2020
Year: 2020

We study facility location problems where agents control multiple locations and when reporting their locations can choose to hide some locations (hiding), report some locations more than once (replication) and lie about their locations (manipulation). We fully characterize all facility location mechanisms that are anonymous, efficient, and strategyproof with respect to the richer strategic behavior for this setting. We also provide a characterization with respect to manipulation only. This is the first, to the best of our knowledge, characterization result for the strategyproof facility location mechanisms where each agent controls multiple locations.
Deep Transform and Metric Learning Network: Wedding Deep Dictionary Learning and Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

On account of its many successes in inference tasks and denoising applications, Dictionary Learning (DL) and its related sparse optimization problems have garnered a lot of research interest. While most solutions have focused on single layer dictionaries, the improved recently proposed Deep DL (DDL) methods have also fallen short on a number of issues. We propose herein, a novel DDL approach where each DL layer can be formulated as a combination of one linear layer and a Recurrent Neural Network (RNN). The RNN is shown to flexibly account for the layer-associated and learned metric. Our proposed work unveils new insights into Neural Networks and DDL and provides a new, efficient and competitive approach to jointly learn a deep transform and a metric for inference applications. Extensive experiments are carried out to demonstrate that the proposed method can not only outperform existing DDL but also state-of-the-art generic CNNs.
Survey on Individual Differences in Visualization
Venue: arXiv cs.HC 2020
Year: 2020

Developments in data visualization research have enabled visualization systems to achieve great general usability and application across a variety of domains. These advancements have improved not only people's understanding of data, but also the general understanding of people themselves, and how they interact with visualization systems. In particular, researchers have gradually come to recognize the deficiency of having one-size-fits-all visualization interfaces, as well as the significance of individual differences in the use of data visualization systems. Unfortunately, the absence of comprehensive surveys of the existing literature impedes the development of this research. In this paper, we review the research perspectives, as well as the personality traits and cognitive abilities, visualizations, tasks, and measures investigated in the existing literature. We aim to provide a detailed summary of existing scholarship, produce evidence-based reviews, and spur future inquiry.
Action-Manipulation Attacks Against Stochastic Bandits: Attacks and Defense
Venue: arXiv cs.LG 2020
Year: 2020

Due to the broad range of applications of stochastic multi-armed bandit model, understanding the effects of adversarial attacks and designing bandit algorithms robust to attacks are essential for the safe applications of this model. In this paper, we introduce a new class of attack named action-manipulation attack. In this attack, an adversary can change the action signal selected by the user. We show that without knowledge of mean rewards of arms, our proposed attack can manipulate Upper Confidence Bound (UCB) algorithm, a widely used bandit algorithm, into pulling a target arm very frequently by spending only logarithmic cost. To defend against this class of attacks, we introduce a novel algorithm that is robust to action-manipulation attacks when an upper bound for the total attack cost is given. We prove that our algorithm has a pseudo-regret upper bounded by $\mathcal{O}(\max\{\log T,A\})$, where $T$ is the total number of rounds and $A$ is the upper bound of the total attack cost.
Realtime Index-Free Single Source SimRank Processing on Web-Scale Graphs
Venue: arXiv cs.DB 2020
Year: 2020

Given a graph G and a node u in G, a single source SimRank query evaluates the similarity between u and every node v in G. Existing approaches to single source SimRank computation incur either long query response time, or expensive pre-computation, which needs to be performed again whenever the graph G changes. Consequently, to our knowledge none of them is ideal for scenarios in which (i) query processing must be done in realtime, and (ii) the underlying graph G is massive, with frequent updates. Motivated by this, we propose SimPush, a novel algorithm that answers single source SimRank queries without any pre-computation, and at the same time achieves significantly higher query processing speed than even the fastest known index-based solutions. Further, SimPush provides rigorous result quality guarantees, and its high performance does not rely on any strong assumption of the underlying graph. Specifically, compared to existing methods, SimPush employs a radically different algorithmic design that focuses on (i) identifying a small number of nodes relevant to the query, and subsequently (ii) computing statistics and performing residue push from these nodes only. We prove the correctness of SimPush, analyze its time complexity, and compare its asymptotic performance with that of existing methods. Meanwhile, we evaluate the practical performance of SimPush through extensive experiments on 8 real datasets. The results demonstrate that SimPush consistently outperforms all existing solutions, often by over an order of magnitude. In particular, on a commodity machine, SimPush answers a single source SimRank query on a web graph containing over 133 million nodes and 5.4 billion edges in under 62 milliseconds, with 0.00035 empirical error, while the fastest index-based competitor needs 1.18 seconds.
Weakly-Supervised Semantic Segmentation by Iterative Affinity Learning
Venue: arXiv cs.CV 2020
Year: 2020

Weakly-supervised semantic segmentation is a challenging task as no pixel-wise label information is provided for training. Recent methods have exploited classification networks to localize objects by selecting regions with strong response. While such response map provides sparse information, however, there exist strong pairwise relations between pixels in natural images, which can be utilized to propagate the sparse map to a much denser one. In this paper, we propose an iterative algorithm to learn such pairwise relations, which consists of two branches, a unary segmentation network which learns the label probabilities for each pixel, and a pairwise affinity network which learns affinity matrix and refines the probability map generated from the unary network. The refined results by the pairwise network are then used as supervision to train the unary network, and the procedures are conducted iteratively to obtain better segmentation progressively. To learn reliable pixel affinity without accurate annotation, we also propose to mine confident regions. We show that iteratively training this framework is equivalent to optimizing an energy function with convergence to a local minimum. Experimental results on the PASCAL VOC 2012 and COCO datasets demonstrate that the proposed algorithm performs favorably against the state-of-the-art methods.
Analyzing Neural Networks Based on Random Graphs
Venue: arXiv cs.LG 2020
Year: 2020

We perform a massive evaluation of neural networks with architectures corresponding to random graphs of various types. We investigate various structural and numerical properties of the graphs in relation to neural network test accuracy. We find that none of the classical numerical graph invariants by itself allows to single out the best networks. Consequently, we introduce a new numerical graph characteristic that selects a set of quasi-1-dimensional graphs, which are a majority among the best performing networks. We also find that networks with primarily short-range connections perform better than networks which allow for many long-range connections. Moreover, many resolution reducing pathways are beneficial. We provide a dataset of 1020 graphs and the test accuracies of their corresponding neural networks at https://github.com/rmldj/random-graph-nn-paper
Rnn-transducer with language bias for end-to-end Mandarin-English code-switching speech recognition
Venue: arXiv cs.CL 2020
Year: 2020

Recently, language identity information has been utilized to improve the performance of end-to-end code-switching (CS) speech recognition. However, previous works use an additional language identification (LID) model as an auxiliary module, which causes the system complex. In this work, we propose an improved recurrent neural network transducer (RNN-T) model with language bias to alleviate the problem. We use the language identities to bias the model to predict the CS points. This promotes the model to learn the language identity information directly from transcription, and no additional LID model is needed. We evaluate the approach on a Mandarin-English CS corpus SEAME. Compared to our RNN-T baseline, the proposed method can achieve 16.2% and 12.9% relative error reduction on two test sets, respectively.
CodeBERT: A Pre-Trained Model for Programming and Natural Languages
Venue: arXiv cs.CL 2020
Year: 2020

We present CodeBERT, a bimodal pre-trained model for programming language (PL) and nat-ural language (NL). CodeBERT learns general-purpose representations that support downstream NL-PL applications such as natural language codesearch, code documentation generation, etc. We develop CodeBERT with Transformer-based neural architecture, and train it with a hybrid objective function that incorporates the pre-training task of replaced token detection, which is to detect plausible alternatives sampled from generators. This enables us to utilize both bimodal data of NL-PL pairs and unimodal data, where the former provides input tokens for model training while the latter helps to learn better generators. We evaluate CodeBERT on two NL-PL applications by fine-tuning model parameters. Results show that CodeBERT achieves state-of-the-art performance on both natural language code search and code documentation generation tasks. Furthermore, to investigate what type of knowledge is learned in CodeBERT, we construct a dataset for NL-PL probing, and evaluate in a zero-shot setting where parameters of pre-trained models are fixed. Results show that CodeBERT performs better than previous pre-trained models on NL-PL probing.
A Survey on Predictive Maintenance for Industry 4.0
Venue: arXiv cs.LG 2020
Year: 2020

Production issues at Volkswagen in 2016 lead to dramatic losses in sales of up to 400 million Euros per week. This example shows the huge financial impact of a working production facility for companies. Especially in the data-driven domains of Industry 4.0 and Industrial IoT with intelligent, connected machines, a conventional, static maintenance schedule seems to be old-fashioned. In this paper, we present a survey on the current state of the art in predictive maintenance for Industry 4.0. Based on a structured literate survey, we present a classification of predictive maintenance in the context of Industry 4.0 and discuss recent developments in this area.
BatchLayout: A Batch-Parallel Force-Directed Graph Layout Algorithm in Shared Memory
Venue: arXiv cs.SI 2020
Year: 2020

Force-directed algorithms are widely used to generate aesthetically pleasing layouts of graphs or networks arisen in many scientific disciplines. To visualize large-scale graphs, several parallel algorithms have been discussed in the literature. However, existing parallel algorithms do not utilize memory hierarchy efficiently and often offer limited parallelism. This paper addresses these limitations with BatchLayout, an algorithm that groups vertices into minibatches and processes them in parallel. BatchLayout also employs cache blocking techniques to utilize memory hierarchy efficiently. More parallelism and improved memory accesses coupled with force approximating techniques, better initialization, and optimized learning rate make BatchLayout significantly faster than other state-of-the-art algorithms such as ForceAtlas2 and OpenOrd. The visualization quality of layouts from BatchLayout is comparable or better than similar visualization tools. All of our source code, links to datasets, results and log files are available at https://github.com/khaled-rahman/BatchLayout.
Weakly Supervised Semantic Segmentation of Satellite Images for Land Cover Mapping -- Challenges and Opportunities
Venue: arXiv cs.CV 2020
Year: 2020

Fully automatic large-scale land cover mapping belongs to the core challenges addressed by the remote sensing community. Usually, the basis of this task is formed by (supervised) machine learning models. However, in spite of recent growth in the availability of satellite observations, accurate training data remains comparably scarce. On the other hand, numerous global land cover products exist and can be accessed often free-of-charge. Unfortunately, these maps are typically of a much lower resolution than modern day satellite imagery. Besides, they always come with a significant amount of noise, as they cannot be considered ground truth, but are products of previous (semi-)automatic prediction tasks. Therefore, this paper seeks to make a case for the application of weakly supervised learning strategies to get the most out of available data sources and achieve progress in high-resolution large-scale land cover mapping. Challenges and opportunities are discussed based on the SEN12MS dataset, for which also some baseline results are shown. These baselines indicate that there is still a lot of potential for dedicated approaches designed to deal with remote sensing-specific forms of weak supervision.
Beyond 5G Low-Power Wide-Area Networks: A LoRaWAN Suitability Study
Venue: arXiv cs.NI 2020
Year: 2020

In this paper, we deliver a discussion regarding the role of Low-Power Wide-Area Networks (LPWAN) in the cellular Internet-of-Things (IoT) infrastructure to support massive Machine-Type Communications (mMTC) in next-generation wireless systems beyond 5G. We commence by presenting a performance analysis of current LPWAN systems, specifically LoRaWAN, in terms of coverage and throughput. The results obtained using analytic methods and network simulations are combined in the paper for getting a more comprehensive vision. Next, we identify possible performance bottlenecks, speculate on the characteristics of coming IoT applications, and seek to identify potential enhancements to the current technologies that may overcome the identified shortcomings.
ITeM: Independent Temporal Motifs to Summarize and Compare Temporal Networks
Venue: arXiv cs.SI 2020
Year: 2020

Networks are a fundamental and flexible way of representing various complex systems. Many domains such as communication, citation, procurement, biology, social media, and transportation can be modeled as a set of entities and their relationships. Temporal networks are a specialization of general networks where the temporal evolution of the system is as important to understand as the structure of the entities and relationships. We present the Independent Temporal Motif (ITeM) to characterize temporal graphs from different domains. The ITeMs are edge-disjoint temporal motifs that can be used to model the structure and the evolution of the graph. For a given temporal graph, we produce a feature vector of ITeM frequencies and apply this distribution to the task of measuring the similarity of temporal graphs. We show that ITeM has higher accuracy than other motif frequency-based approaches. We define various metrics based on ITeM that reveal salient properties of a temporal network. We also present importance sampling as a method for efficiently estimating the ITeM counts. We evaluate our approach on both synthetic and real temporal networks.
Mode Selection and Resource Allocation in Sliced Fog Radio Access Networks: A Reinforcement Learning Approach
Venue: arXiv cs.NI 2020
Year: 2020

The mode selection and resource allocation in fog radio access networks (F-RANs) have been advocated as key techniques to improve spectral and energy efficiency. In this paper, we investigate the joint optimization of mode selection and resource allocation in uplink F-RANs, where both of the traditional user equipments (UEs) and fog UEs are served by constructed network slice instances. The concerned optimization is formulated as a mixed-integer programming problem, and both the orthogonal and multiplexed subchannel allocation strategies are proposed to guarantee the slice isolation. Motivated by the development of machine learning, two reinforcement learning based algorithms are developed to solve the original high complexity problem under traditional and fog UEs' specific performance requirements. The basic idea of the proposals is to generate a good mode selection policy according to the immediate reward fed back by an environment. Simulation results validate the benefits of our proposed algorithms and show that a tradeoff between system power consumption and queue delay can be achieved.