OpenRaiser/Intern-Atlas huggingface dataset:
Temporal Ordered Clustering in Dynamic Networks: Unsupervised and Semi-supervised Learning Algorithms
Venue: arXiv cs.SI 2020
Year: 2020

In temporal ordered clustering, given a single snapshot of a dynamic network in which nodes arrive at distinct time instants, we aim at partitioning its nodes into $K$ ordered clusters $\mathcal{C}_1 \prec \cdots \prec \mathcal{C}_K$ such that for $i<j$, nodes in cluster $\mathcal{C}_i$ arrived before nodes in cluster $\mathcal{C}_j$, with $K$ being a data-driven parameter and not known upfront. Such a problem is of considerable significance in many applications ranging from tracking the expansion of fake news to mapping the spread of information. We first formulate our problem for a general dynamic graph, and propose an integer programming framework that finds the optimal clustering, represented as a strict partial order set, achieving the best precision (i.e., fraction of successfully ordered node pairs) for a fixed density (i.e., fraction of comparable node pairs). We then develop a sequential importance procedure and design unsupervised and semi-supervised algorithms to find temporal ordered clusters that efficiently approximate the optimal solution. To illustrate the techniques, we apply our methods to the vertex copying (duplication-divergence) model which exhibits some edge-case challenges in inferring the clusters as compared to other network models. Finally, we validate the performance of the proposed algorithms on synthetic and real-world networks.
Logic-based Specification and Verification of Homogeneous Dynamic Multi-agent Systems
Venue: arXiv cs.LO 2020
Year: 2020

We develop a logic-based framework for formal specification and algorithmic verification of homogeneous and dynamic concurrent multi-agent transition systems (HDMAS). Homogeneity means that all agents have the same available actions at any given state and the actions have the same effects regardless of which agents perform them. The state transitions are therefore determined only by the vector of numbers of agents performing each action and are specified symbolically, by means of conditions on these numbers definable in Presburger arithmetic. The agents are divided into controllable (by the system supervisor/controller) and uncontrollable, representing the environment or adversary. Dynamicity means that the numbers of controllable and uncontrollable agents may vary throughout the system evolution, possibly at every transition. As a language for formal specification we use a suitably extended version of Alternating-time Temporal Logic (ATL), where one can specify properties of the type "a coalition of (at least) $n$ controllable agents can ensure against (at most) $m$ uncontrollable agents that any possible evolution of the system satisfies a given objective $φ$", where $φ$ is specified again as a formula of that language and each of $n$ and $m$ is either a fixed number or a variable that can be quantified over. We provide formal semantics to our logic $\mathcal{L}_{HDMAS}$ and define normal form of its formulae. We then prove that every formula in $\mathcal{L}_{HDMAS}$ is equivalent in the finite to one in a normal form and develop an algorithm for global model checking of formulae in normal form in finite HDMAS models, which invokes model checking truth of Presburger formulae. We establish worst case complexity estimates for the model checking algorithm and illustrate it on a running example.
Defining Smart Contract Defects on Ethereum
Venue: arXiv cs.SE 2020
Year: 2020

Smart contracts are programs running on a blockchain. They are immutable to change, and hence can not be patched for bugs once deployed. Thus it is critical to ensure they are bug-free and well-designed before deployment. A Contract defect is an error, flaw or fault in a smart contract that causes it to produce an incorrect or unexpected result, or to behave in unintended ways. The detection of contract defects is a method to avoid potential bugs and improve the design of existing code. Since smart contracts contain numerous distinctive features, such as the gas system. decentralized, it is important to find smart contract specified defects. To fill this gap, we collected smart-contract-related posts from Ethereum StackExchange, as well as real-world smart contracts. We manually analyzed these posts and contracts; using them to define 20 kinds of contract defects. We categorized them into indicating potential security, availability, performance, maintainability and reusability problems. To validate if practitioners consider these contract as harmful, we created an online survey and received 138 responses from 32 different countries. Feedback showed these contract defects are harmful and removing them would improve the quality and robustness of smart contracts. We manually identified our defined contract defects in 587 real world smart contract and publicly released our dataset. Finally, we summarized 5 impacts caused by contract defects. These help developers better understand the symptoms of the defects and removal priority.
Unsupervised Detection of Distinctive Regions on 3D Shapes
Venue: arXiv cs.GR 2020
Year: 2020

This paper presents a novel approach to learn and detect distinctive regions on 3D shapes. Unlike previous works, which require labeled data, our method is unsupervised. We conduct the analysis on point sets sampled from 3D shapes, then formulate and train a deep neural network for an unsupervised shape clustering task to learn local and global features for distinguishing shapes with respect to a given shape set. To drive the network to learn in an unsupervised manner, we design a clustering-based nonparametric softmax classifier with an iterative re-clustering of shapes, and an adapted contrastive loss for enhancing the feature embedding quality and stabilizing the learning process. By then, we encourage the network to learn the point distinctiveness on the input shapes. We extensively evaluate various aspects of our approach and present its applications for distinctiveness-guided shape retrieval, sampling, and view selection in 3D scenes.
Distributional Semantics and Linguistic Theory
Venue: arXiv cs.CL 2020
Year: 2020

Distributional semantics provides multi-dimensional, graded, empirically induced word representations that successfully capture many aspects of meaning in natural languages, as shown in a large body of work in computational linguistics; yet, its impact in theoretical linguistics has so far been limited. This review provides a critical discussion of the literature on distributional semantics, with an emphasis on methods and results that are of relevance for theoretical linguistics, in three areas: semantic change, polysemy and composition, and the grammar-semantics interface (specifically, the interface of semantics with syntax and with derivational morphology). The review aims at fostering greater cross-fertilization of theoretical and computational approaches to language, as a means to advance our collective knowledge of how it works.
Missing Data Imputation with Adversarially-trained Graph Convolutional Networks
Venue: arXiv cs.LG 2020
Year: 2020

Missing data imputation (MDI) is a fundamental problem in many scientific disciplines. Popular methods for MDI use global statistics computed from the entire data set (e.g., the feature-wise medians), or build predictive models operating independently on every instance. In this paper we propose a more general framework for MDI, leveraging recent work in the field of graph neural networks (GNNs). We formulate the MDI task in terms of a graph denoising autoencoder, where each edge of the graph encodes the similarity between two patterns. A GNN encoder learns to build intermediate representations for each example by interleaving classical projection layers and locally combining information between neighbors, while another decoding GNN learns to reconstruct the full imputed data set from this intermediate embedding. In order to speed-up training and improve the performance, we use a combination of multiple losses, including an adversarial loss implemented with the Wasserstein metric and a gradient penalty. We also explore a few extensions to the basic architecture involving the use of residual connections between layers, and of global statistics computed from the data set to improve the accuracy. On a large experimental evaluation, we show that our method robustly outperforms state-of-the-art approaches for MDI, especially for large percentages of missing values.
Dissecting Android Cryptocurrency Miners
Venue: arXiv cs.CR 2020
Year: 2020

Cryptojacking applications pose a serious threat to mobile devices. Due to the extensive computations, they deplete the battery fast and can even damage the device. In this work we make a step towards combating this threat. We collected and manually verified a large dataset of Android mining apps. In this paper, we analyze the gathered miners and identify how they work, what are the most popular libraries and APIs used to facilitate their development, and what static features are typical for this class of applications. Further, we analyzed our dataset using VirusTotal. The majority of our samples is considered malicious by at least one VirusTotal scanner, but 16 apps are not detected by any engine; and at least 5 apks were not seen previously by the service. Mining code could be obfuscated or fetched at runtime, and there are many confusing miner-related apps that actually do not mine. Thus, static features alone are not sufficient for miner detection. We have collected a feature set of dynamic metrics both for miners and unrelated benign apps, and built a machine learning-based tool for dynamic detection. Our BrenntDroid tool is able to detect miners with 95% of accuracy on our dataset. This preprint is a technical report accompanying the paper "Dissecting Android Cryptocurrency Miners" published in ACM CODASPY 2020.
Collaborative Localization for Micro Aerial Vehicles
Venue: arXiv cs.RO 2020
Year: 2020

In this paper, we present a framework for performing collaborative localization for groups of micro aerial vehicles (MAV) that use vision based sensing. The vehicles are each assumed to be equipped with a forward-facing monocular camera, and to be capable of communicating with each other. This collaborative localization approach is developed as a decentralized algorithm and built in a distributed fashion where individual and relative pose estimation techniques are combined for the group to localize against surrounding environments. The MAVs initially detect and match salient features between each other to create a sparse reconstruction of the observed environment, which acts as a global map. Once a map is available, each MAV performs feature detection and tracking with a robust outlier rejection process to estimate its own pose in 6 degrees of freedom. Occasionally, one or more MAVs can be tasked to compute poses for another MAV through relative measurements, which is achieved by exploiting multiple view geometry concepts. These relative measurements are then fused with individual measurements in a consistent fashion. We present the results of the algorithm on image data from MAV flights both in simulation and real life, and discuss the advantages of collaborative localization in improving pose estimation accuracy.
Proportionally Fair Clustering
Venue: arXiv cs.LG 2020
Year: 2020

We extend the fair machine learning literature by considering the problem of proportional centroid clustering in a metric context. For clustering $n$ points with $k$ centers, we define fairness as proportionality to mean that any $n/k$ points are entitled to form their own cluster if there is another center that is closer in distance for all $n/k$ points. We seek clustering solutions to which there are no such justified complaints from any subsets of agents, without assuming any a priori notion of protected subsets. We present and analyze algorithms to efficiently compute, optimize, and audit proportional solutions. We conclude with an empirical examination of the tradeoff between proportional solutions and the $k$-means objective.
A reconstruction of the multipreference closure
Venue: arXiv cs.LO 2020
Year: 2020

The paper describes a preferential approach for dealing with exceptions in KLM preferential logics, based on the rational closure. It is well known that the rational closure does not allow an independent handling of the inheritance of different defeasible properties of concepts. Several solutions have been proposed to face this problem and the lexicographic closure is the most notable one. In this work, we consider an alternative closure construction, called the Multi Preference closure (MP-closure), that has been first considered for reasoning with exceptions in DLs. Here, we reconstruct the notion of MP-closure in the propositional case and we show that it is a natural variant of Lehmann's lexicographic closure. Abandoning Maximal Entropy (an alternative route already considered but not explored by Lehmann) leads to a construction which exploits a different lexicographic ordering w.r.t. the lexicographic closure, and determines a preferential consequence relation rather than a rational consequence relation. We show that, building on the MP-closure semantics, rationality can be recovered, at least from the semantic point of view, resulting in a rational consequence relation which is stronger than the rational closure, but incomparable with the lexicographic closure. We also show that the MP-closure is stronger than the Relevant Closure.
Integrating Tensor Similarity to Enhance Clustering Performance
Venue: arXiv cs.LG 2020
Year: 2020

The performance of most the clustering methods hinges on the used pairwise affinity, which is usually denoted by a similarity matrix. However, the pairwise similarity is notoriously known for its vulnerability of noise contamination or the imbalance in samples or features, and thus hinders accurate clustering. To tackle this issue, we propose to use information among samples to boost the clustering performance. We proved that a simplified similarity for pairs, denoted by a fourth order tensor, equals to the Kronecker product of pairwise similarity matrices under decomposable assumption, or provide complementary information for which the pairwise similarity missed under indecomposable assumption. Then a high order similarity matrix is obtained from the tensor similarity via eigenvalue decomposition. The high order similarity capturing spatial information serves as a robust complement for the pairwise similarity. It is further integrated with the popular pairwise similarity, named by IPS2, to boost the clustering performance. Extensive experiments demonstrated that the proposed IPS2 significantly outperformed previous similarity-based methods on real-world datasets and it was capable of handling the clustering task over under-sampled and noisy datasets.
Search for Smart Evaders with Sweeping Agents
Venue: arXiv cs.MA 2020
Year: 2020

Suppose that in a given planar circular region, there are some smart mobile evaders and we would like to find them using sweeping agents. We assume that the sweeping agents are in a line formation whose total length is 2r. We propose procedures for designing a sweeping process that ensures the successful completion of the task, thereby deriving conditions on the sweeping velocity of the linear formation and its path. Successful completion of the task means that evaders with a given limit on their velocity cannot escape the sweeping agents. A simpler task for the sweeping formation is the confinement of the evaders to their initial domain. The feasibility of completing these tasks depends on geometric and dynamic constraints that impose a lower bound on the velocity that the sweeper line formation must have. This critical velocity is derived to ensure the satisfaction of the confinement task. Increasing the velocity above the lower bound enables the agents to complete the search task as well. We present results on the total search time as a function of the sweeping velocity of the formation given the initial conditions on the size of the search region and the maximal velocity of the evaders.
K-Athena: a performance portable structured grid finite volume magnetohydrodynamics code
Venue: arXiv cs.DC 2020
Year: 2020

Large scale simulations are a key pillar of modern research and require ever-increasing computational resources. Different novel manycore architectures have emerged in recent years on the way towards the exascale era. Performance portability is required to prevent repeated non-trivial refactoring of a code for different architectures. We combine Athena++, an existing magnetohydrodynamics (MHD) CPU code, with Kokkos, a performance portable on-node parallel programming paradigm, into K-Athena to allow efficient simulations on multiple architectures using a single codebase. We present profiling and scaling results for different platforms including Intel Skylake CPUs, Intel Xeon Phis, and NVIDIA GPUs. K-Athena achieves $>10^8$ cell-updates/s on a single V100 GPU for second-order double precision MHD calculations, and a speedup of 30 on up to 24,576 GPUs on Summit (compared to 172,032 CPU cores), reaching $1.94\times10^{12}$ total cell-updates/s at 76% parallel efficiency. Using a roofline analysis we demonstrate that the overall performance is currently limited by DRAM bandwidth and calculate a performance portability metric of 62.8%. Finally, we present the implementation strategies used and the challenges encountered in maximizing performance. This will provide other research groups with a straightforward approach to prepare their own codes for the exascale era. K-Athena is available at https://gitlab.com/pgrete/kathena .
Deep Plug-and-play Prior for Low-rank Tensor Completion
Venue: arXiv cs.CV 2020
Year: 2020

Multi-dimensional images, such as color images and multi-spectral images, are highly correlated and contain abundant spatial and spectral information. However, real-world multi-dimensional images are usually corrupted by missing entries. By integrating deterministic low-rankness prior to the data-driven deep prior, we suggest a novel regularized tensor completion model for multi-dimensional image completion. In the objective function, we adopt the newly emerged tensor nuclear norm (TNN) to characterize the global low-rankness prior of the multi-dimensional images. We also formulate an implicit regularizer by plugging into a denoising neural network (termed as deep denoiser), which is convinced to express the deep image prior learned from a large number of natural images. The resulting model can be solved by the alternating directional method of multipliers algorithm under the plug-and-play (PnP) framework. Experimental results on color images, videos, and multi-spectral images demonstrate that the proposed method can recover both the global structure and fine details very well and achieve superior performance over competing methods in terms of quality metrics and visual effects.
DeepOPF: Deep Neural Network for DC Optimal Power Flow
Venue: arXiv cs.SY 2020
Year: 2020

We develop DeepOPF as a Deep Neural Network (DNN) approach for solving direct current optimal power flow (DC-OPF) problems. DeepOPF is inspired by the observation that solving DC-OPF for a given power network is equivalent to characterizing a high-dimensional mapping between the load inputs and the dispatch and transmission decisions. We construct and train a DNN model to learn such mapping, then we apply it to obtain optimized operating decisions upon arbitrary load inputs. We adopt uniform sampling to address the over-fitting problem common in generic DNN approaches. We leverage on a useful structure in DC-OPF to significantly reduce the mapping dimension, subsequently cutting down the size of our DNN model and the amount of training data/time needed. We also design a post-processing procedure to ensure the feasibility of the obtained solution. Simulation results of IEEE test cases show that DeepOPF always generates feasible solutions with negligible optimality loss, while speeding up the computing time by two orders of magnitude as compared to conventional approaches implemented in a state-of-the-art solver.
Election Control through Social Influence with Unknown Preferences
Venue: arXiv cs.SI 2020
Year: 2020

The election control problem through social influence asks to find a set of nodes in a social network of voters to be the starters of a political campaign aiming at supporting a given target candidate. Voters reached by the campaign change their opinions on the candidates. The goal is to shape the diffusion of the campaign in such a way that the chances of victory of the target candidate are maximized. Previous work shows that the problem can be approximated within a constant factor in several models of information diffusion and voting systems, assuming that the controller, i.e., the external agent that starts the campaign, has full knowledge of the preferences of voters. However this information is not always available since some voters might not reveal it. Herein we relax this assumption by considering that each voter is associated with a probability distribution over the candidates. We propose two models in which, when an electoral campaign reaches a voter, this latter modifies its probability distribution according to the amount of influence it received from its neighbors in the network. We then study the election control problem through social influence on the new models: In the first model, under the Gap-ETH, election control cannot be approximated within a factor better than $1/n^{o(1)}$, where $n$ is the number of voters; in the second model, which is a slight relaxation of the first one, the problem admits a constant factor approximation algorithm.
CASTNet: Community-Attentive Spatio-Temporal Networks for Opioid Overdose Forecasting
Venue: arXiv cs.LG 2020
Year: 2020

Opioid overdose is a growing public health crisis in the United States. This crisis, recognized as "opioid epidemic," has widespread societal consequences including the degradation of health, and the increase in crime rates and family problems. To improve the overdose surveillance and to identify the areas in need of prevention effort, in this work, we focus on forecasting opioid overdose using real-time crime dynamics. Previous work identified various types of links between opioid use and criminal activities, such as financial motives and common causes. Motivated by these observations, we propose a novel spatio-temporal predictive model for opioid overdose forecasting by leveraging the spatio-temporal patterns of crime incidents. Our proposed model incorporates multi-head attentional networks to learn different representation subspaces of features. Such deep learning architecture, called "community-attentive" networks, allows the prediction of a given location to be optimized by a mixture of groups (i.e., communities) of regions. In addition, our proposed model allows for interpreting what features, from what communities, have more contributions to predicting local incidents as well as how these communities are captured through forecasting. Our results on two real-world overdose datasets indicate that our model achieves superior forecasting performance and provides meaningful interpretations in terms of spatio-temporal relationships between the dynamics of crime and that of opioid overdose.