OpenRaiser/Intern-Atlas huggingface dataset:
Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees
Venue: arXiv cs.DC 2021
Year: 2021

Recently, Balliu, Brandt, and Olivetti [FOCS '20] showed the first $ω(\log^* n)$ lower bound for the maximal independent set (MIS) problem in trees. In this work we prove lower bounds for a much more relaxed family of distributed symmetry breaking problems. As a by-product, we obtain improved lower bounds for the distributed MIS problem in trees. For a parameter $k$ and an orientation of the edges of a graph $G$, we say that a subset $S$ of the nodes of $G$ is a $k$-outdegree dominating set if $S$ is a dominating set of $G$ and if in the induced subgraph $G[S]$, every node in $S$ has outdegree at most $k$. Note that for $k=0$, this definition coincides with the definition of an MIS. For a given $k$, we consider the problem of computing a $k$-outdegree dominating set. We show that, even in regular trees of degree at most $Δ$, in the standard \LOCAL model, there exists a constant $ε>0$ such that for $k\leq Δ^ε$, for the problem of computing a $k$-outdegree dominating set, any randomized algorithm requires at least $Ω(\min\{\logΔ,\sqrt{\log\log n}\})$ rounds and any deterministic algorithm requires at least $Ω(\min\{\logΔ,\sqrt{\log n}\})$ rounds. The proof of our lower bounds is based on the recently highly successful round elimination technique. We provide a novel way to do simplifications for round elimination, which we expect to be of independent interest. Our new proof is considerably simpler than the lower bound proof in [FOCS '20]. In particular, our round elimination proof uses a family of problems that can be described by only a constant number of labels. The existence of such a proof for the MIS problem was believed impossible by the authors of [FOCS '20].
GasHisSDB: A New Gastric Histopathology Image Dataset for Computer Aided Diagnosis of Gastric Cancer
Venue: arXiv cs.CV 2021
Year: 2021

Background and Objective: Gastric cancer has turned out to be the fifth most common cancer globally, and early detection of gastric cancer is essential to save lives. Histopathological examination of gastric cancer is the gold standard for the diagnosis of gastric cancer. However, computer-aided diagnostic techniques are challenging to evaluate due to the scarcity of publicly available gastric histopathology image datasets. Methods: In this paper, a noble publicly available Gastric Histopathology Sub-size Image Database (GasHisSDB) is published to identify classifiers' performance. Specifically, two types of data are included: normal and abnormal, with a total of 245,196 tissue case images. In order to prove that the methods of different periods in the field of image classification have discrepancies on GasHisSDB, we select a variety of classifiers for evaluation. Seven classical machine learning classifiers, three Convolutional Neural Network classifiers, and a novel transformer-based classifier are selected for testing on image classification tasks. Results: This study performed extensive experiments using traditional machine learning and deep learning methods to prove that the methods of different periods have discrepancies on GasHisSDB. Traditional machine learning achieved the best accuracy rate of 86.08% and a minimum of just 41.12%. The best accuracy of deep learning reached 96.47% and the lowest was 86.21%. Accuracy rates vary significantly across classifiers. Conclusions: To the best of our knowledge, it is the first publicly available gastric cancer histopathology dataset containing a large number of images for weakly supervised learning. We believe that GasHisSDB can attract researchers to explore new algorithms for the automated diagnosis of gastric cancer, which can help physicians and patients in the clinical setting.
COINS: Dynamically Generating COntextualized Inference Rules for Narrative Story Completion
Venue: arXiv cs.CL 2021
Year: 2021

Despite recent successes of large pre-trained language models in solving reasoning tasks, their inference capabilities remain opaque. We posit that such models can be made more interpretable by explicitly generating interim inference rules, and using them to guide the generation of task-specific textual outputs. In this paper we present COINS, a recursive inference framework that i) iteratively reads context sentences, ii) dynamically generates contextualized inference rules, encodes them, and iii) uses them to guide task-specific output generation. We apply COINS to a Narrative Story Completion task that asks a model to complete a story with missing sentences, to produce a coherent story with plausible logical connections, causal relationships, and temporal dependencies. By modularizing inference and sentence generation steps in a recurrent model, we aim to make reasoning steps and their effects on next sentence generation transparent. Our automatic and manual evaluations show that the model generates better story sentences than SOTA baselines, especially in terms of coherence. We further demonstrate improved performance over strong pre-trained LMs in generating commonsense inference rules. The recursive nature of COINS holds the potential for controlled generation of longer sequences.
Graph-based Deep Learning for Communication Networks: A Survey
Venue: arXiv cs.NI 2021
Year: 2021

Communication networks are important infrastructures in contemporary society. There are still many challenges that are not fully solved and new solutions are proposed continuously in this active research area. In recent years, to model the network topology, graph-based deep learning has achieved the state-of-the-art performance in a series of problems in communication networks. In this survey, we review the rapidly growing body of research using different graph-based deep learning models, e.g. graph convolutional and graph attention networks, in various problems from different types of communication networks, e.g. wireless networks, wired networks, and software defined networks. We also present a well-organized list of the problem and solution for each study and identify future research directions. To the best of our knowledge, this paper is the first survey that focuses on the application of graph-based deep learning methods in communication networks involving both wired and wireless scenarios. To track the follow-up research, a public GitHub repository is created, where the relevant papers will be updated continuously.
Flying with Cartographer: Adapting the Cartographer 3D Graph SLAM Stack for UAV Navigation
Venue: arXiv cs.RO 2021
Year: 2021

This paper describes an application of the Cartographer graph SLAM stack as a pose sensor in a UAV feedback control loop, with certain application-specific changes in the SLAM stack such as smoothing of the optimized pose. Pose estimation is performed by fusing 3D LiDAR/IMU-based proprioception with GPS position measurements by means of pose graph optimisation. Moreover, partial environment maps built from the LiDAR data (submaps) within the Cartographer SLAM stack are marshalled into OctoMap, an Octree-based voxel map implementation. The OctoMap is further used for navigation tasks such as path planning and obstacle avoidance.
Heterogeneous Wasserstein Discrepancy for Incomparable Distributions
Venue: arXiv cs.LG 2021
Year: 2021

Optimal Transport (OT) metrics allow for defining discrepancies between two probability measures. Wasserstein distance is for longer the celebrated OT-distance frequently-used in the literature, which seeks probability distributions to be supported on the $\textit{same}$ metric space. Because of its high computational complexity, several approximate Wasserstein distances have been proposed based on entropy regularization or on slicing, and one-dimensional Wassserstein computation. In this paper, we propose a novel extension of Wasserstein distance to compare two incomparable distributions, that hinges on the idea of $\textit{distributional slicing}$, embeddings, and on computing the closed-form Wassertein distance between the sliced distributions. We provide a theoretical analysis of this new divergence, called $\textit{heterogeneous Wasserstein discrepancy (HWD)}$, and we show that it preserves several interesting properties including rotation-invariance. We show that the embeddings involved in HWD can be efficiently learned. Finally, we provide a large set of experiments illustrating the behavior of HWD as a divergence in the context of generative modeling and in query framework.
Pose and Semantic Map Based Probabilistic Forecast of Vulnerable Road Users' Trajectories
Venue: arXiv cs.CV 2021
Year: 2021

In this article, an approach for probabilistic trajectory forecasting of vulnerable road users (VRUs) is presented, which considers past movements and the surrounding scene. Past movements are represented by 3D poses reflecting the posture and movements of individual body parts. The surrounding scene is modeled in the form of semantic maps showing, e.g., the course of streets, sidewalks, and the occurrence of obstacles. The forecasts are generated in grids discretizing the space and in the form of arbitrary discrete probability distributions. The distributions are evaluated in terms of their reliability, sharpness, and positional accuracy. We compare our method with an approach that provides forecasts in the form of Gaussian distributions and discuss the respective advantages and disadvantages. Thereby, we investigate the impact of using poses and semantic maps. With a technique called spatial label smoothing, our approach achieves reliable forecasts. Overall, the poses have a positive impact on the forecasts. The semantic maps offer the opportunity to adapt the probability distributions to the individual situation, although at the considered forecasted time horizon of 2.52 s they play a minor role compared to the past movements of the VRU. Our method is evaluated on a dataset recorded in inner-city traffic using a research vehicle. The dataset is made publicly available.
Popular individuals process the world in particularly normative ways
Venue: arXiv cs.SI 2021
Year: 2021

People differ in how they attend to, interpret, and respond to their surroundings. Convergent processing of the world may be one factor that contributes to social connections between individuals. We used neuroimaging and network analysis to investigate whether the most central individuals in their communities (as measured by in-degree centrality, a notion of popularity) process the world in a particularly normative way. We found that more central individuals had exceptionally similar neural responses to their peers and especially to each other in brain regions that are associated with high-level interpretations and social cognition (e.g., in the default-mode network), whereas less-central individuals exhibited more idiosyncratic responses. Self-reported enjoyment of and interest in stimuli followed a similar pattern, but accounting for these data did not change our main results. These findings suggest that highly-central individuals process the world in exceptionally similar ways, whereas less-central individuals process the world in idiosyncratic ways.
Encoder-Decoder Neural Architecture Optimization for Keyword Spotting
Venue: arXiv cs.LG 2021
Year: 2021

Keyword spotting aims to identify specific keyword audio utterances. In recent years, deep convolutional neural networks have been widely utilized in keyword spotting systems. However, their model architectures are mainly based on off-the shelfbackbones such as VGG-Net or ResNet, instead of specially designed for the task. In this paper, we utilize neural architecture search to design convolutional neural network models that can boost the performance of keyword spotting while maintaining an acceptable memory footprint. Specifically, we search the model operators and their connections in a specific search space with Encoder-Decoder neural architecture optimization. Extensive evaluations on Google's Speech Commands Dataset show that the model architecture searched by our approach achieves a state-of-the-art accuracy of over 97%.
PEEL: A Provable Removal Attack on Deep Hiding
Venue: arXiv cs.CR 2021
Year: 2021

Deep hiding, embedding images into another using deep neural networks, has shown its great power in increasing the message capacity and robustness. In this paper, we conduct an in-depth study of state-of-the-art deep hiding schemes and analyze their hidden vulnerabilities. Then, according to our observations and analysis, we propose a novel ProvablE rEmovaL attack (PEEL) using image inpainting to remove secret images from containers without any prior knowledge about the deep hiding scheme. We also propose a systemic methodology to improve the efficiency and image quality of PEEL by carefully designing a removal strategy and fully utilizing the visual information of containers. Extensive evaluations show our attacks can completely remove secret images and has negligible impact on the quality of containers.
The Four Levels of Fixed-Points in Mean-Field Models
Venue: arXiv cs.NI 2021
Year: 2021

The fixed-point analysis refers to the study of fixed-points that arise in the context of complex systems with many interacting entities. In this expository paper, we describe four levels of fixed-points in mean-field interacting particle systems. These four levels are (i) the macroscopic observables of the system, (ii) the probability distribution over states of a particle at equilibrium, (iii) the time evolution of the probability distribution over states of a particle, and (iv) the probability distribution over trajectories. We then discuss relationships among the fixed-points at these four levels. Finally, we describe some issues that arise in the fixed-point analysis when the system possesses multiple fixed-points at the level of distribution over states, and how one goes beyond the fixed-point analysis to tackle such issues.
ImGAGN:Imbalanced Network Embedding via Generative Adversarial Graph Networks
Venue: arXiv cs.LG 2021
Year: 2021

Imbalanced classification on graphs is ubiquitous yet challenging in many real-world applications, such as fraudulent node detection. Recently, graph neural networks (GNNs) have shown promising performance on many network analysis tasks. However, most existing GNNs have almost exclusively focused on the balanced networks, and would get unappealing performance on the imbalanced networks. To bridge this gap, in this paper, we present a generative adversarial graph network model, called ImGAGN to address the imbalanced classification problem on graphs. It introduces a novel generator for graph structure data, named GraphGenerator, which can simulate both the minority class nodes' attribute distribution and network topological structure distribution by generating a set of synthetic minority nodes such that the number of nodes in different classes can be balanced. Then a graph convolutional network (GCN) discriminator is trained to discriminate between real nodes and fake (i.e., generated) nodes, and also between minority nodes and majority nodes on the synthetic balanced network. To validate the effectiveness of the proposed method, extensive experiments are conducted on four real-world imbalanced network datasets. Experimental results demonstrate that the proposed method ImGAGN outperforms state-of-the-art algorithms for semi-supervised imbalanced node classification task.
Dynamic Resource Configuration for Low-Power IoT Networks: A Multi-Objective Reinforcement Learning Method
Venue: arXiv cs.IT 2021
Year: 2021

Considering grant-free transmissions in low-power IoT networks with unknown time-frequency distribution of interference, we address the problem of Dynamic Resource Configuration (DRC), which amounts to a Markov decision process. Unfortunately, off-the-shelf methods based on single-objective reinforcement learning cannot guarantee energy-efficient transmission, especially when all frequency-domain channels in a time interval are interfered. Therefore, we propose a novel DRC scheme where configuration policies are optimized with a Multi-Objective Reinforcement Learning (MORL) framework. Numerical results show that the average decision error rate achieved by the MORL-based DRC can be even less than 12% of that yielded by the conventional R-learning-based approach.
Improving Automated Evaluation of Open Domain Dialog via Diverse Reference Augmentation
Venue: arXiv cs.CL 2021
Year: 2021

Multiple different responses are often plausible for a given open domain dialog context. Prior work has shown the importance of having multiple valid reference responses for meaningful and robust automated evaluations. In such cases, common practice has been to collect more human written references. However, such collection can be expensive, time consuming, and not easily scalable. Instead, we propose a novel technique for automatically expanding a human generated reference to a set of candidate references. We fetch plausible references from knowledge sources, and adapt them so that they are more fluent in context of the dialog instance in question. More specifically, we use (1) a commonsense knowledge base to elicit a large number of plausible reactions given the dialog history (2) relevant instances retrieved from dialog corpus, using similar past as well as future contexts. We demonstrate that our automatically expanded reference sets lead to large improvements in correlations of automated metrics with human ratings of system outputs for DailyDialog dataset.
MergeDistill: Merging Pre-trained Language Models using Distillation
Venue: arXiv cs.CL 2021
Year: 2021

Pre-trained multilingual language models (LMs) have achieved state-of-the-art results in cross-lingual transfer, but they often lead to an inequitable representation of languages due to limited capacity, skewed pre-training data, and sub-optimal vocabularies. This has prompted the creation of an ever-growing pre-trained model universe, where each model is trained on large amounts of language or domain specific data with a carefully curated, linguistically informed vocabulary. However, doing so brings us back full circle and prevents one from leveraging the benefits of multilinguality. To address the gaps at both ends of the spectrum, we propose MergeDistill, a framework to merge pre-trained LMs in a way that can best leverage their assets with minimal dependencies, using task-agnostic knowledge distillation. We demonstrate the applicability of our framework in a practical setting by leveraging pre-existing teacher LMs and training student LMs that perform competitively with or even outperform teacher LMs trained on several orders of magnitude more data and with a fixed model capacity. We also highlight the importance of teacher selection and its impact on student model performance.
Constrained Generalized Additive 2 Model with Consideration of High-Order Interactions
Venue: arXiv cs.LG 2021
Year: 2021

In recent years, machine learning and AI have been introduced in many industrial fields. In fields such as finance, medicine, and autonomous driving, where the inference results of a model may have serious consequences, high interpretability as well as prediction accuracy is required. In this study, we propose CGA2M+, which is based on the Generalized Additive 2 Model (GA2M) and differs from it in two major ways. The first is the introduction of monotonicity. Imposing monotonicity on some functions based on an analyst's knowledge is expected to improve not only interpretability but also generalization performance. The second is the introduction of a higher-order term: given that GA2M considers only second-order interactions, we aim to balance interpretability and prediction accuracy by introducing a higher-order term that can capture higher-order interactions. In this way, we can improve prediction performance without compromising interpretability by applying learning innovation. Numerical experiments showed that the proposed model has high predictive performance and interpretability. Furthermore, we confirmed that generalization performance is improved by introducing monotonicity.
Reinforcement Learning for Assignment Problem with Time Constraints
Venue: arXiv cs.AI 2021
Year: 2021

We present an end-to-end framework for the Assignment Problem with multiple tasks mapped to a group of workers, using reinforcement learning while preserving many constraints. Tasks and workers have time constraints and there is a cost associated with assigning a worker to a task. Each worker can perform multiple tasks until it exhausts its allowed time units (capacity). We train a reinforcement learning agent to find near optimal solutions to the problem by minimizing total cost associated with the assignments while maintaining hard constraints. We use proximal policy optimization to optimize model parameters. The model generates a sequence of actions in real-time which correspond to task assignment to workers, without having to retrain for changes in the dynamic state of the environment. In our problem setting reward is computed as negative of the assignment cost. We also demonstrate our results on bin packing and capacitated vehicle routing problem, using the same framework. Our results outperform Google OR-Tools using MIP and CP-SAT solvers with large problem instances, in terms of solution quality and computation time.
Ensemble Defense with Data Diversity: Weak Correlation Implies Strong Robustness
Venue: arXiv cs.LG 2021
Year: 2021

In this paper, we propose a framework of filter-based ensemble of deep neuralnetworks (DNNs) to defend against adversarial attacks. The framework builds an ensemble of sub-models -- DNNs with differentiated preprocessing filters. From the theoretical perspective of DNN robustness, we argue that under the assumption of high quality of the filters, the weaker the correlations of the sensitivity of the filters are, the more robust the ensemble model tends to be, and this is corroborated by the experiments of transfer-based attacks. Correspondingly, we propose a principle that chooses the specific filters with smaller Pearson correlation coefficients, which ensures the diversity of the inputs received by DNNs, as well as the effectiveness of the entire framework against attacks. Our ensemble models are more robust than those constructed by previous defense methods like adversarial training, and even competitive with the classical ensemble of adversarial trained DNNs under adversarial attacks when the attacking radius is large.
A Generative Node-attribute Network Model for Detecting Generalized Structure
Venue: arXiv cs.SI 2021
Year: 2021

Exploring meaningful structural regularities embedded in networks is a key to understanding and analyzing the structure and function of a network. The node-attribute information can help improve such understanding and analysis. However, most of the existing methods focus on detecting traditional communities, i.e., groupings of nodes with dense internal connections and sparse external ones. In this paper, based on the connectivity behavior of nodes and homogeneity of attributes, we propose a principle model (named GNAN), which can generate both topology information and attribute information. The new model can detect not only community structure, but also a range of other types of structure in networks, such as bipartite structure, core-periphery structure, and their mixture structure, which are collectively referred to as generalized structure. The proposed model that combines topological information and node-attribute information can detect communities more accurately than the model that only uses topology information. The dependency between attributes and communities can be automatically learned by our model and thus we can ignore the attributes that do not contain useful information. The model parameters are inferred by using the expectation-maximization algorithm. And a case study is provided to show the ability of our model in the semantic interpretability of communities. Experiments on both synthetic and real-world networks show that the new model is competitive with other state-of-the-art models.