OpenRaiser/Intern-Atlas huggingface dataset:
Complexity of the Multilevel Critical Node Problem
Venue: arXiv cs.CC 2020
Year: 2020

In this work, we analyze a sequential game played in a graph called the Multilevel Critical Node problem (MCN). A defender and an attacker are the players of this game. The defender starts by preventively interdicting vertices (vaccination) from being attacked. Then, the attacker infects a subset of non-vaccinated vertices and, finally, the defender reacts with a protection strategy. We provide the first computational complexity results associated with MCN and its subgames. Moreover, by considering unitary, weighted, undirected, and directed graphs, we clarify how the theoretical tractability of those problems vary. Our findings contribute with new NP-complete, $Σ_2^p$-complete and $Σ_3^p$-complete problems. Furthermore, for the last level of the game, the protection stage, we build polynomial time algorithms for certain graph classes.
Deep Convolutional Neural Network for Identifying Seam-Carving Forgery
Venue: arXiv cs.MM 2020
Year: 2020

Seam carving is a representative content-aware image retargeting approach to adjust the size of an image while preserving its visually prominent content. To maintain visually important content, seam-carving algorithms first calculate the connected path of pixels, referred to as the seam, according to a defined cost function and then adjust the size of an image by removing and duplicating repeatedly calculated seams. Seam carving is actively exploited to overcome diversity in the resolution of images between applications and devices; hence, detecting the distortion caused by seam carving has become important in image forensics. In this paper, we propose a convolutional neural network (CNN)-based approach to classifying seam-carving-based image retargeting for reduction and expansion. To attain the ability to learn low-level features, we designed a CNN architecture comprising five types of network blocks specialized for capturing subtle signals. An ensemble module is further adopted to both enhance performance and comprehensively analyze the features in the local areas of the given image. To validate the effectiveness of our work, extensive experiments based on various CNN-based baselines were conducted. Compared to the baselines, our work exhibits state-of-the-art performance in terms of three-class classification (original, seam inserted, and seam removed). In addition, our model with the ensemble module is robust for various unseen cases. The experimental results also demonstrate that our method can be applied to localize both seam-removed and seam-inserted areas.
Partial Order Resolution of Event Logs for Process Conformance Checking
Venue: arXiv cs.AI 2020
Year: 2020

While supporting the execution of business processes, information systems record event logs. Conformance checking relies on these logs to analyze whether the recorded behavior of a process conforms to the behavior of a normative specification. A key assumption of existing conformance checking techniques, however, is that all events are associated with timestamps that allow to infer a total order of events per process instance. Unfortunately, this assumption is often violated in practice. Due to synchronization issues, manual event recordings, or data corruption, events are only partially ordered. In this paper, we put forward the problem of partial order resolution of event logs to close this gap. It refers to the construction of a probability distribution over all possible total orders of events of an instance. To cope with the order uncertainty in real-world data, we present several estimators for this task, incorporating different notions of behavioral abstraction. Moreover, to reduce the runtime of conformance checking based on partial order resolution, we introduce an approximation method that comes with a bounded error in terms of accuracy. Our experiments with real-world and synthetic data reveal that our approach improves accuracy over the state-of-the-art considerably.
Attention-based Joint Detection of Object and Semantic Part
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we address the problem of joint detection of objects like dog and its semantic parts like face, leg, etc. Our model is created on top of two Faster-RCNN models that share their features to perform a novel Attention-based feature fusion of related Object and Part features to get enhanced representations of both. These representations are used for final classification and bounding box regression separately for both models. Our experiments on the PASCAL-Part 2010 dataset show that joint detection can simultaneously improve both object detection and part detection in terms of mean Average Precision (mAP) at IoU=0.5.
A stochastic calculus approach to the oracle separation of BQP and PH
Venue: arXiv cs.CC 2020
Year: 2020

After presentations of Raz and Tal's oracle separation of BQP and PH result, several people (e.g. Ryan O'Donnell, James Lee, Avishay Tal) suggested that the proof may be simplified by stochastic calculus. In this short note, we describe such a simplification.
Searching Scientific Literature for Answers on COVID-19 Questions
Venue: arXiv cs.IR 2020
Year: 2020

Finding answers related to a pandemic of a novel disease raises new challenges for information seeking and retrieval, as the new information becomes available gradually. TREC COVID search track aims to assist in creating search tools to aid scientists, clinicians, policy makers and others with similar information needs in finding reliable answers from the scientific literature. We experiment with different ranking algorithms as part of our participation in this challenge. We propose a novel method for neural retrieval, and demonstrate its effectiveness on the TREC COVID search.
Progressive Cluster Purification for Unsupervised Feature Learning
Venue: arXiv cs.CV 2020
Year: 2020

In unsupervised feature learning, sample specificity based methods ignore the inter-class information, which deteriorates the discriminative capability of representation models. Clustering based methods are error-prone to explore the complete class boundary information due to the inevitable class inconsistent samples in each cluster. In this work, we propose a novel clustering based method, which, by iteratively excluding class inconsistent samples during progressive cluster formation, alleviates the impact of noise samples in a simple-yet-effective manner. Our approach, referred to as Progressive Cluster Purification (PCP), implements progressive clustering by gradually reducing the number of clusters during training, while the sizes of clusters continuously expand consistently with the growth of model representation capability. With a well-designed cluster purification mechanism, it further purifies clusters by filtering noise samples which facilitate the subsequent feature learning by utilizing the refined clusters as pseudo-labels. Experiments on commonly used benchmarks demonstrate that the proposed PCP improves baseline method with significant margins. Our code will be available at https://github.com/zhangyifei0115/PCP.
Simulation-Guided Boolean Resubstitution
Venue: arXiv cs.LO 2020
Year: 2020

This paper proposes a new logic optimization paradigm based on circuit simulation, which reduces the need for Boolean computations such as SAT-solving or constructing BDDs. The paper develops a Boolean resubstitution framework to demonstrate the effectiveness of the proposed approach. Methods to generate highly expressive simulation patterns are developed, and the generated patterns are used in resubstitution for efficient filtering of potential resubstitution candidates to reduce the need for SAT validation. Experimental results show that improvements in circuit size reduction were achieved by up to 74%, compared to a state-of-the-art resubstitution algorithm.
Go local: The key to controlling the COVID-19 pandemic in the post lockdown era
Venue: arXiv cs.CY 2020
Year: 2020

The UK government announced its first wave of lockdown easing on 10 May 2020, two months after the non-pharmaceutical measures to reduce the spread of COVID-19 were first introduced on 23 March 2020. Analysis of reported case rate data from Public Health England and aggregated and anonymised crowd level mobility data shows variability across local authorities in the UK. A locality-based approach to lockdown easing is needed, enabling local public health and associated health and social care services to rapidly respond to emerging hotspots of infection. National level data will hide an increasing heterogeneity of COVID-19 infections and mobility, and new ways of real-time data presentation to the public are required. Data sources (including mobile) allow for faster visualisation than more traditional data sources, and are part of a wider trend towards near real-time analysis of outbreaks needed for timely, targeted local public health interventions. Real time data visualisation may give early warnings of unusual levels of activity which warrant further investigation by local public health authorities.
Optimal and Approximation Algorithms for Joint Routing and Scheduling in Millimeter-Wave Cellular Networks
Venue: arXiv cs.NI 2020
Year: 2020

Millimeter-wave (mmWave) communication is a promising technology to cope with the exponential increase in 5G data traffic. Such networks typically require a very dense deployment of base stations. A subset of those, so-called macro base stations, feature high-bandwidth connection to the core network, while relay base stations are connected wirelessly. To reduce cost and increase flexibility, wireless backhauling is needed to connect both macro to relay as well as relay to relay base stations. The characteristics of mmWave communication mandates new paradigms for routing and scheduling. The paper investigates scheduling algorithms under different interference models. To showcase the scheduling methods, we study the maximum throughput fair scheduling problem. Yet the proposed algorithms can be easily extended to other problems. For a full-duplex network under the no interference model, we propose an efficient polynomial-time scheduling method, the {\em schedule-oriented optimization}. Further, we prove that the problem is NP-hard if we assume pairwise link interference model or half-duplex radios. Fractional weighted coloring based approximation algorithms are proposed for these NP-hard cases. Moreover, the approximation algorithm parallel data stream scheduling is proposed for the case of half-duplex network under the no interference model. It has better approximation ratio than the fractional weighted coloring based algorithms and even attains the optimal solution for the special case of uniform orthogonal backhaul networks.
Providing In-network Support to Coflow Scheduling
Venue: arXiv cs.NI 2020
Year: 2020

Many emerging distributed applications, including big data analytics, generate a number of flows that concurrently transport data across data center networks. To improve their performance, it is required to account for the behavior of a collection of flows, i.e., coflows, rather than individual. State-of-the-art solutions allow for a near-optimal completion time by continuously reordering the unfinished coflows at the end-host, using network priorities. This paper shows that dynamically changing flow priorities at the end host, without taking into account in-flight packets, can cause high-degrees of packet re-ordering, thus imposing pressure on the congestion control and potentially harming network performance in the presence of switches with shallow buffers. We present pCoflow, a new solution that integrates end-host based coflow ordering with in-network scheduling based on packet history. Our evaluation shows that pCoflow improves in CCT upon state-of-the-art solutions by up to 34% for varying load.
Community detection and Social Network analysis based on the Italian wars of the 15th century
Venue: arXiv cs.SI 2020
Year: 2020

In this contribution we study social network modelling by using human interaction as a basis. To do so, we propose a new set of functions, affinities, designed to capture the nature of the local interactions among each pair of actors in a network. By using these functions, we develop a new community detection algorithm, the Borgia Clustering, where communities naturally arise from the multi-agent interaction in the network. We also discuss the effects of size and scale for communities regarding this case, as well as how we cope with the additional complexity present when big communities arise. Finally, we compare our community detection solution with other representative algorithms, finding favourable results.
Two-Stage Adaptive Pooling with RT-qPCR for COVID-19 Screening
Venue: arXiv cs.IT 2020
Year: 2020

We propose two-stage adaptive pooling schemes, 2-STAP and 2-STAMP, for detecting COVID-19 using real-time reverse transcription quantitative polymerase chain reaction (RT-qPCR) test kits. Similar to the Tapestry scheme of Ghosh et al., the proposed schemes leverage soft information from the RT-qPCR process about the total viral load in the pool. This is in contrast to conventional group testing schemes where the measurements are Boolean. The proposed schemes provide higher testing throughput than the popularly used Dorfman's scheme. They also provide higher testing throughput, sensitivity and specificity than the state-of-the-art non-adaptive Tapestry scheme. The number of pipetting operations is lower than state-of-the-art non-adaptive pooling schemes, and is higher than that for the Dorfman's scheme. The proposed schemes can work with substantially smaller group sizes than non-adaptive schemes and are simple to describe. Monte-Carlo simulations using the statistical model in the work of Ghosh et al. (Tapestry) show that 10 infected people in a population of size 961 can be identified with 70.86 tests on the average with a sensitivity of 99.50% and specificity of 99.62. This is 13.5x, 4.24x, and 1.3x the testing throughput of individual testing, Dorfman's testing, and the Tapestry scheme, respectively.
On the Evolution of Programming Languages
Venue: arXiv cs.PL 2020
Year: 2020

This paper attempts to connects the evolution of computer languages with the evolution of life, where the later has been dictated by \emph{theory of evolution of species}, and tries to give supportive evidence that the new languages are more robust than the previous, carry-over the mixed features of older languages, such that strong features gets added into them and weak features of older languages gets removed. In addition, an analysis of most prominent programming languages is presented, emphasizing on how the features of existing languages have influenced the development of new programming languages. At the end, it suggests a set of experimental languages, which may rule the world of programming languages in the time of new multi-core architectures. Index terms- Programming languages' evolution, classifications of languages, future languages, scripting-languages.
Real-Time Monitoring and Driver Feedback to Promote Fuel Efficient Driving
Venue: arXiv cs.HC 2020
Year: 2020

Improving the fuel efficiency of vehicles is imperative to reduce costs and protect the environment. While the efficient engine and vehicle designs, as well as intelligent route planning, are well-known solutions to enhance the fuel efficiency, research has also demonstrated that the adoption of fuel-efficient driving behaviors could lead to further savings. In this work, we propose a novel framework to promote fuel-efficient driving behaviors through real-time automatic monitoring and driver feedback. In this framework, a random-forest based classification model developed using historical data to identifies fuel-inefficient driving behaviors. The classifier considers driver-dependent parameters such as speed and acceleration/deceleration pattern, as well as environmental parameters such as traffic, road topography, and weather to evaluate the fuel efficiency of one-minute driving events. When an inefficient driving action is detected, a fuzzy logic inference system is used to determine what the driver should do to maintain fuel-efficient driving behavior. The decided action is then conveyed to the driver via a smartphone in a non-intrusive manner. Using a dataset from a long-distance bus, we demonstrate that the proposed classification model yields an accuracy of 85.2% while increasing the fuel efficiency up to 16.4%.
LFQ: Online Learning of Per-flow Queuing Policies using Deep Reinforcement Learning
Venue: arXiv cs.NI 2020
Year: 2020

The increasing number of different, incompatible congestion control algorithms has led to an increased deployment of fair queuing. Fair queuing isolates each network flow and can thus guarantee fairness for each flow even if the flows' congestion controls are not inherently fair. So far, each queue in the fair queuing system either has a fixed, static maximum size or is managed by an Active Queue Management (AQM) algorithm like CoDel. In this paper we design an AQM mechanism (Learning Fair Qdisc (LFQ)) that dynamically learns the optimal buffer size for each flow according to a specified reward function online. We show that our Deep Learning based algorithm can dynamically assign the optimal queue size to each flow depending on its congestion control, delay and bandwidth. Comparing to competing fair AQM schedulers, it provides significantly smaller queues while achieving the same or higher throughput.
Multi-tenant Pub/Sub Processing for Real-time Data Streams
Venue: arXiv cs.DC 2020
Year: 2020

Devices and sensors generate streams of data across a diversity of locations and protocols. That data usually reaches a central platform that is used to store and process the streams. Processing can be done in real time, with transformations and enrichment happening on-the-fly, but it can also happen after data is stored and organized in repositories. In the former case, stream processing technologies are required to operate on the data; in the latter batch analytics and queries are of common use. This paper introduces a runtime to dynamically construct data stream processing topologies based on user-supplied code. These dynamic topologies are built on-the-fly using a data subscription model defined by the applications that consume data. Each user-defined processing unit is called a Service Object. Every Service Object consumes input data streams and may produce output streams that others can consume. The subscription-based programing model enables multiple users to deploy their own data-processing services. The runtime does the dynamic forwarding of data and execution of Service Objects from different users. Data streams can originate in real-world devices or they can be the outputs of Service Objects.
Making Fair ML Software using Trustworthy Explanation
Venue: arXiv cs.SE 2020
Year: 2020

Machine learning software is being used in many applications (finance, hiring, admissions, criminal justice) having a huge social impact. But sometimes the behavior of this software is biased and it shows discrimination based on some sensitive attributes such as sex, race, etc. Prior works concentrated on finding and mitigating bias in ML models. A recent trend is using instance-based model-agnostic explanation methods such as LIME to find out bias in the model prediction. Our work concentrates on finding shortcomings of current bias measures and explanation methods. We show how our proposed method based on K nearest neighbors can overcome those shortcomings and find the underlying bias of black-box models. Our results are more trustworthy and helpful for the practitioners. Finally, We describe our future framework combining explanation and planning to build fair software.
MCMI: Multi-Cycle Image Translation with Mutual Information Constraints
Venue: arXiv cs.CV 2020
Year: 2020

We present a mutual information-based framework for unsupervised image-to-image translation. Our MCMI approach treats single-cycle image translation models as modules that can be used recurrently in a multi-cycle translation setting where the translation process is bounded by mutual information constraints between the input and output images. The proposed mutual information constraints can improve cross-domain mappings by optimizing out translation functions that fail to satisfy the Markov property during image translations. We show that models trained with MCMI produce higher quality images and learn more semantically-relevant mappings compared to state-of-the-art image translation methods. The MCMI framework can be applied to existing unpaired image-to-image translation models with minimum modifications. Qualitative experiments and a perceptual study demonstrate the image quality improvements and generality of our approach using several backbone models and a variety of image datasets.
Sharing Models or Coresets: A Study based on Membership Inference Attack
Venue: arXiv cs.LG 2020
Year: 2020

Distributed machine learning generally aims at training a global model based on distributed data without collecting all the data to a centralized location, where two different approaches have been proposed: collecting and aggregating local models (federated learning) and collecting and training over representative data summaries (coreset). While each approach preserves data privacy to some extent thanks to not sharing the raw data, the exact extent of protection is unclear under sophisticated attacks that try to infer the raw data from the shared information. We present the first comparison between the two approaches in terms of target model accuracy, communication cost, and data privacy, where the last is measured by the accuracy of a state-of-the-art attack strategy called the membership inference attack. Our experiments quantify the accuracy-privacy-cost tradeoff of each approach, and reveal a nontrivial comparison that can be used to guide the design of model training processes.
Incorrect Data in the Widely Used Inside Airbnb Dataset
Venue: arXiv cs.CY 2020
Year: 2020

Several recently published papers in Decision Support Systems discussed issues related to data quality in Information Systems research. In this short research note, I build on the work introduced in these papers and document two data quality issues discovered in a large open dataset commonly used in research. Inside Airbnb (IA) collects data from places and reviews as posted by users of Airbnb.com. Visitors can effortlessly download data collected by IA for several locations around the globe. While the dataset is widely used in academic research, no thorough investigation of the dataset and its validity has been conducted. This note examines the dataset and explains an issue of incorrect data added to the dataset. Findings suggest that this issue can be attributed to systemic errors in the data collection process. The results suggest that the use of unverified open datasets can be problematic, although the discoveries presented in this work may not be significant enough to challenge all published research that used the IA dataset. Additionally, findings indicate that the incorrect data happens because of a new feature implemented by Airbnb. Thus, unless changes are made, it is likely that the consequences of this issue will only become more severe. Finally, this note explores why reproducibility is a problem when two different releases of the dataset are compared.
Determination of the most representative descriptor among a set of feature vectors for the same object
Venue: arXiv cs.CV 2020
Year: 2020

On an example of solution of the face recognition problem the approach for estimation of the most representative descriptor among a set of feature vectors for the same face is considered in present study. The estimation is based on robust calculation of the mode-median mixture vector for the set as the descriptor by means of Welsch/Leclerc loss function application in case of very sparse filling of the feature space with feature vectors