OpenRaiser/Intern-Atlas huggingface dataset:
Scheduling Lower Bounds via AND Subset Sum
Venue: arXiv cs.DS 2020
Year: 2020

Given $N$ instances $(X_1,t_1),\ldots,(X_N,t_N)$ of Subset Sum, the AND Subset Sum problem asks to determine whether all of these instances are yes-instances; that is, whether each set of integers $X_i$ has a subset that sums up to the target integer $t_i$. We prove that this problem cannot be solved in time $\tilde{O}((N \cdot t_{max})^{1-ε})$, for $t_{max}=\max_i t_i$ and any $ε> 0$, assuming the $\forall \exists$ Strong Exponential Time Hypothesis ($\forall \exists$-SETH). We then use this result to exclude $\tilde{O}(n+P_{max} \cdot n^{1-ε})$-time algorithms for several scheduling problems on $n$ jobs with maximum processing time $P_{max}$, based on $\forall \exists$-SETH. These include classical problems such as $1||\sum w_jU_j$, the problem of minimizing the total weight of tardy jobs on a single machine, and $P_2||\sum U_j$, the problem of minimizing the number of tardy jobs on two identical parallel machines.
A Novel Framework with Information Fusion and Neighborhood Enhancement for User Identity Linkage
Venue: arXiv cs.SI 2020
Year: 2020

User identity linkage across social networks is an essential problem for cross-network data mining. Since network structure, profile and content information describe different aspects of users, it is critical to learn effective user representations that integrate heterogeneous information. This paper proposes a novel framework with INformation FUsion and Neighborhood Enhancement (INFUNE) for user identity linkage. The information fusion component adopts a group of encoders and decoders to fuse heterogeneous information and generate discriminative node embeddings for preliminary matching. Then, these embeddings are fed to the neighborhood enhancement component, a novel graph neural network, to produce adaptive neighborhood embeddings that reflect the overlapping degree of neighborhoods of varying candidate user pairs. The importance of node embeddings and neighborhood embeddings are weighted for final prediction. The proposed method is evaluated on real-world social network data. The experimental results show that INFUNE significantly outperforms existing state-of-the-art methods.
RNE: A Scalable Network Embedding for Billion-scale Recommendation
Venue: arXiv cs.IR 2020
Year: 2020

Nowadays designing a real recommendation system has been a critical problem for both academic and industry. However, due to the huge number of users and items, the diversity and dynamic property of the user interest, how to design a scalable recommendation system, which is able to efficiently produce effective and diverse recommendation results on billion-scale scenarios, is still a challenging and open problem for existing methods. In this paper, given the user-item interaction graph, we propose RNE, a data-efficient Recommendation-based Network Embedding method, to give personalized and diverse items to users. Specifically, we propose a diversity- and dynamics-aware neighbor sampling method for network embedding. On the one hand, the method is able to preserve the local structure between the users and items while modeling the diversity and dynamic property of the user interest to boost the recommendation quality. On the other hand the sampling method can reduce the complexity of the whole method theoretically to make it possible for billion-scale recommendation. We also implement the designed algorithm in a distributed way to further improves its scalability. Experimentally, we deploy RNE on a recommendation scenario of Taobao, the largest E-commerce platform in China, and train it on a billion-scale user-item graph. As is shown on several online metrics on A/B testing, RNE is able to achieve both high-quality and diverse results compared with CF-based methods. We also conduct the offline experiments on Pinterest dataset comparing with several state-of-the-art recommendation methods and network embedding methods. The results demonstrate that our method is able to produce a good result while runs much faster than the baseline methods.
Refinements in Motion and Appearance for Online Multi-Object Tracking
Venue: arXiv cs.CV 2020
Year: 2020

Modern multi-object tracking (MOT) system usually involves separated modules, such as motion model for location and appearance model for data association. However, the compatible problems within both motion and appearance models are always ignored. In this paper, a general architecture named as MIF is presented by seamlessly blending the Motion integration, three-dimensional(3D) Integral image and adaptive appearance feature Fusion. Since the uncertain pedestrian and camera motions are usually handled separately, the integrated motion model is designed using our defined intension of camera motion. Specifically, a 3D integral image based spatial blocking method is presented to efficiently cut useless connections between trajectories and candidates with spatial constraints. Then the appearance model and visibility prediction are jointly built. Considering scale, pose and visibility, the appearance features are adaptively fused to overcome the feature misalignment problem. Our MIF based tracker (MIFT) achieves the state-of-the-art accuracy with 60.1 MOTA on both MOT16&17 challenges.
SocialGrid: A TCN-enhanced Method for Online Discussion Forecasting
Venue: arXiv cs.SI 2020
Year: 2020

As a means of modern communication tools, online discussion forums have become an increasingly popular platform that allows asynchronous online interactions. People share thoughts and opinions through posting threads and replies, which form a unique communication structure between main threads and associated replies. It is significant to understand the information diffusion pattern under such a communication structure, where an essential task is to predict the arrival time of future events. In this work, we proposed a novel yet simple framework, called SocialGrid, for modeling events in online discussing forms. Our framework first transforms the entire event space into a grid representation by grouping successive evens in one time interval of a particular length. Based on the nature of the grid, we leverage the Temporal Convolution Network to learn the dynamics at the grid level. Varying the temporal scope of an individual grid, the learned grid model can be used to predict the arrival time of future events at different granularities. Leveraging the Reddit data, we validate the proposed method through experiments on a series of applications. Extensive experiments and a real-world application. Results have shown that our framework excels at various cascade prediction tasks comparing with other approaches.
MegaM@Rt2 EU Project: Open Source Tools for Mega-Modelling at Runtime of CPSs
Venue: arXiv cs.SE 2020
Year: 2020

In this paper, we overview our experiences of developing large set of open source tools in ECSEL JU European project called MegaM@Rt2 whose main objective is to propose a scalable model-based framework incorporating methods and tools for the continuous development and runtime support of complex software-intensive Cyber-Physical Systems (CPSs). We briefly present the MegaM@Rt2 concepts, discuss our approach for open source, enumerate tools and give an example of a tools selection for a specific industrial context. Our goal is to introduce the reader with open source tools for the model-based engineering of CPSs suitable for diverse industrial applications.
The TrojAI Software Framework: An OpenSource tool for Embedding Trojans into Deep Learning Models
Venue: arXiv cs.LG 2020
Year: 2020

In this paper, we introduce the TrojAI software framework, an open source set of Python tools capable of generating triggered (poisoned) datasets and associated deep learning (DL) models with trojans at scale. We utilize the developed framework to generate a large set of trojaned MNIST classifiers, as well as demonstrate the capability to produce a trojaned reinforcement-learning model using vector observations. Results on MNIST show that the nature of the trigger, training batch size, and dataset poisoning percentage all affect successful embedding of trojans. We test Neural Cleanse against the trojaned MNIST models and successfully detect anomalies in the trained models approximately $18\%$ of the time. Our experiments and workflow indicate that the TrojAI software framework will enable researchers to easily understand the effects of various configurations of the dataset and training hyperparameters on the generated trojaned deep learning model, and can be used to rapidly and comprehensively test new trojan detection methods.
A Formal Analysis of Multimodal Referring Strategies Under Common Ground
Venue: arXiv cs.CL 2020
Year: 2020

In this paper, we present an analysis of computationally generated mixed-modality definite referring expressions using combinations of gesture and linguistic descriptions. In doing so, we expose some striking formal semantic properties of the interactions between gesture and language, conditioned on the introduction of content into the common ground between the (computational) speaker and (human) viewer, and demonstrate how these formal features can contribute to training better models to predict viewer judgment of referring expressions, and potentially to the generation of more natural and informative referring expressions.
Exploiting an Adversary's Intentions in Graphical Coordination Games
Venue: arXiv cs.GT 2020
Year: 2020

How does information regarding an adversary's intentions affect optimal system design? This paper addresses this question in the context of graphical coordination games where an adversary can indirectly influence the behavior of agents by modifying their payoffs. We study a situation in which a system operator must select a graph topology in anticipation of the action of an unknown adversary. The designer can limit her worst-case losses by playing a security strategy, effectively planning for an adversary which intends maximum harm. However, fine-grained information regarding the adversary's intention may help the system operator to fine-tune the defenses and obtain better system performance. In a simple model of adversarial behavior, this paper asks how much a system operator can gain by fine-tuning a defense for known adversarial intent. We find that if the adversary is weak, a security strategy is approximately optimal for any adversary type; however, for moderately-strong adversaries, security strategies are far from optimal.
Neighborhood-based Pooling for Population-level Label Distribution Learning
Venue: arXiv cs.LG 2020
Year: 2020

Supervised machine learning often requires human-annotated data. While annotator disagreement is typically interpreted as evidence of noise, population-level label distribution learning (PLDL) treats the collection of annotations for each data item as a sample of the opinions of a population of human annotators, among whom disagreement may be proper and expected, even with no noise present. From this perspective, a typical training set may contain a large number of very small-sized samples, one for each data item, none of which, by itself, is large enough to be considered representative of the underlying population's beliefs about that item. We propose an algorithmic framework and new statistical tests for PLDL that account for sampling size. We apply them to previously proposed methods for sharing labels across similar data items. We also propose new approaches for label sharing, which we call neighborhood-based pooling.
A Novel AI-enabled Framework to Diagnose Coronavirus COVID 19 using Smartphone Embedded Sensors: Design Study
Venue: arXiv cs.HC 2020
Year: 2020

Coronaviruses are a famous family of viruses that cause illness in both humans and animals. The new type of coronavirus COVID-19 was firstly discovered in Wuhan, China. However, recently, the virus has widely spread in most of the world and causing a pandemic according to the World Health Organization (WHO). Further, nowadays, all the world countries are striving to control the COVID-19. There are many mechanisms to detect coronavirus including clinical analysis of chest CT scan images and blood test results. The confirmed COVID-19 patient manifests as fever, tiredness, and dry cough. Particularly, several techniques can be used to detect the initial results of the virus such as medical detection Kits. However, such devices are incurring huge cost, taking time to install them and use. Therefore, in this paper, a new framework is proposed to detect COVID-19 using built-in smartphone sensors. The proposal provides a low-cost solution, since most of radiologists have already held smartphones for different daily-purposes. Not only that but also ordinary people can use the framework on their smartphones for the virus detection purposes. Nowadays Smartphones are powerful with existing computation-rich processors, memory space, and large number of sensors including cameras, microphone, temperature sensor, inertial sensors, proximity, colour-sensor, humidity-sensor, and wireless chipsets/sensors. The designed Artificial Intelligence (AI) enabled framework reads the smartphone sensors signal measurements to predict the grade of severity of the pneumonia as well as predicting the result of the disease.
Identifying Notable News Stories
Venue: arXiv cs.IR 2020
Year: 2020

The volume of news content has increased significantly in recent years and systems to process and deliver this information in an automated fashion at scale are becoming increasingly prevalent. One critical component that is required in such systems is a method to automatically determine how notable a certain news story is, in order to prioritize these stories during delivery. One way to do so is to compare each story in a stream of news stories to a notable event. In other words, the problem of detecting notable news can be defined as a ranking task; given a trusted source of notable events and a stream of candidate news stories, we aim to answer the question: "Which of the candidate news stories is most similar to the notable one?". We employ different combinations of features and learning to rank (LTR) models and gather relevance labels using crowdsourcing. In our approach, we use structured representations of candidate news stories (triples) and we link them to corresponding entities. Our evaluation shows that the features in our proposed method outperform standard ranking methods, and that the trained model generalizes well to unseen news stories.
Augmented Parallel-Pyramid Net for Attention Guided Pose-Estimation
Venue: arXiv cs.CV 2020
Year: 2020

The target of human pose estimation is to determine body part or joint locations of each person from an image. This is a challenging problems with wide applications. To address this issue, this paper proposes an augmented parallel-pyramid net with attention partial module and differentiable auto-data augmentation. Technically, a parallel pyramid structure is proposed to compensate the loss of information. We take the design of parallel structure for reverse compensation. Meanwhile, the overall computational complexity does not increase. We further define an Attention Partial Module (APM) operator to extract weighted features from different scale feature maps generated by the parallel pyramid structure. Compared with refining through upsampling operator, APM can better capture the relationship between channels. At last, we proposed a differentiable auto data augmentation method to further improve estimation accuracy. We define a new pose search space where the sequences of data augmentations are formulated as a trainable and operational CNN component. Experiments corroborate the effectiveness of our proposed method. Notably, our method achieves the top-1 accuracy on the challenging COCO keypoint benchmark and the state-of-the-art results on the MPII datasets.
Directions for Explainable Knowledge-Enabled Systems
Venue: arXiv cs.AI 2020
Year: 2020

Interest in the field of Explainable Artificial Intelligence has been growing for decades and has accelerated recently. As Artificial Intelligence models have become more complex, and often more opaque, with the incorporation of complex machine learning techniques, explainability has become more critical. Recently, researchers have been investigating and tackling explainability with a user-centric focus, looking for explanations to consider trustworthiness, comprehensibility, explicit provenance, and context-awareness. In this chapter, we leverage our survey of explanation literature in Artificial Intelligence and closely related fields and use these past efforts to generate a set of explanation types that we feel reflect the expanded needs of explanation for today's artificial intelligence applications. We define each type and provide an example question that would motivate the need for this style of explanation. We believe this set of explanation types will help future system designers in their generation and prioritization of requirements and further help generate explanations that are better aligned to users' and situational needs.
Time-Weighted Coverage of Integrated Aerial and Ground Networks for Post-Disaster Communications
Venue: arXiv cs.NI 2020
Year: 2020

In this paper, we propose a new three dimensional (3D) networking architecture with integrated aerial and ground base stations (BSs) for swift post-disaster communication recovery. By exploiting their respective advantages in terms of response time, coverage area, and operational duration, the proposed network is highly heterogeneous, consisting of sustained ground BSs, ground-vehicle mounted BSs, dropping-off BSs and flying BSs. To reflect the importance of swift communication recovery and the dynamics of coverage area in post-disaster scenarios, we propose a new performance metric called ``time-weighted coverage}", which is an integration of the achieved communication coverage area multiplied with a weighting function over time. By choosing different weighting functions, the network deployment can be designed to achieve tradeoffs between the ``swift communication recovery" and ``stable communication coverage". Simulation results show that the proposed integrated aerial and ground network has high implementation flexibility and it can significantly enhance the communication coverage compared with the conventional approaches.
Adapting Deep Learning Methods for Mental Health Prediction on Social Media
Venue: arXiv cs.CL 2020
Year: 2020

Mental health poses a significant challenge for an individual's well-being. Text analysis of rich resources, like social media, can contribute to deeper understanding of illnesses and provide means for their early detection. We tackle a challenge of detecting social media users' mental status through deep learning-based models, moving away from traditional approaches to the task. In a binary classification task on predicting if a user suffers from one of nine different disorders, a hierarchical attention network outperforms previously set benchmarks for four of the disorders. Furthermore, we explore the limitations of our model and analyze phrases relevant for classification by inspecting the model's word-level attention weights.
Semi-Supervised Learning on Graphs with Feature-Augmented Graph Basis Functions
Venue: arXiv cs.LG 2020
Year: 2020

For semi-supervised learning on graphs, we study how initial kernels in a supervised learning regime can be augmented with additional information from known priors or from unsupervised learning outputs. These augmented kernels are constructed in a simple update scheme based on the Schur-Hadamard product of the kernel with additional feature kernels. As generators of the positive definite kernels we will focus on graph basis functions (GBF) that allow to include geometric information of the graph via the graph Fourier transform. Using a regularized least squares (RLS) approach for machine learning, we will test the derived augmented kernels for the classification of data on graphs.
Toward a Wearable RFID System for Real-Time Activity Recognition Using Radio Patterns
Venue: arXiv cs.OH 2020
Year: 2020

Elderly care is one of the many applications supported by real-time activity recognition systems. Traditional approaches use cameras, body sensor networks, or radio patterns from various sources for activity recognition. However, these approaches are limited due to ease-of-use, coverage, or privacy preserving issues. In this paper, we present a novel wearable Radio Frequency Identification (RFID) system aims at providing an easy-to-use solution with high detection coverage. Our system uses passive tags which are maintenance-free and can be embedded into the clothes to reduce the wearing and maintenance efforts. A small RFID reader is also worn on the user's body to extend the detection coverage as the user moves. We exploit RFID radio patterns and extract both spatial and temporal features to characterize various activities. We also address the issues of false negative of tag readings and tag/antenna calibration, and design a fast online recognition system. Antenna and tag selection is done automatically to explore the minimum number of devices required to achieve target accuracy. We develop a prototype system which consists of a wearable RFID system and a smartphone to demonstrate the working principles, and conduct experimental studies with four subjects over two weeks. The results show that our system achieves a high recognition accuracy of 93.6 percent with a latency of 5 seconds. Additionally, we show that the system only requires two antennas and four tagged body parts to achieve a high recognition accuracy of 85 percent.
NP-Completeness Results for Graph Burning on Geometric Graphs
Venue: arXiv cs.DS 2020
Year: 2020

Graph burning runs on discrete time steps. The aim is to burn all the vertices in a given graph in the least number of time steps. This number is known to be the burning number of the graph. The spread of social influence, an alarm, or a social contagion can be modeled using graph burning. The less the burning number, the faster the spread. Optimal burning of general graphs is NP-Hard. There is a 3-approximation algorithm to burn general graphs where as better approximation factors are there for many sub classes. Here we study burning of grids; provide a lower bound for burning arbitrary grids and a 2-approximation algorithm for burning square grids. On the other hand, burning path forests, spider graphs, and trees with maximum degree three is already known to be NP-Complete. In this article we show burning problem to be NP-Complete on connected interval graphs, permutation graphs and several other geometric graph classes as corollaries.