OpenRaiser/Intern-Atlas huggingface dataset:
The inverse Voronoi problem in graphs
Venue: arXiv cs.DS 2020
Year: 2020

We introduce the inverse Voronoi diagram problem in graphs: given a graph $G$ with positive edge-lengths and a collection $\mathbb{U}$ of subsets of vertices of $V(G)$, decide whether $\mathbb{U}$ is a Voronoi diagram in $G$ with respect to the shortest-path metric. We show that the problem is NP-hard, even for planar graphs where all the edges have unit length. We also study the parameterized complexity of the problem and show that the problem is W[1]-hard when parameterized by the number of Voronoi cells or by the pathwidth of the graph. For trees we show that the problem can be solved in $O(N+n \log^2 n)$ time, where $n$ is the number of vertices in the tree and $N=n+\sum_{U\in \mathbb{U}}|U|$ is the size of the description of the input. We also provide a lower bound of $Ω(n \log n)$ time for trees with $n$ vertices.
Effects of Loss Functions And Target Representations on Adversarial Robustness
Venue: arXiv cs.LG 2020
Year: 2020

Understanding and evaluating the robustness of neural networks under adversarial settings is a subject of growing interest. Attacks proposed in the literature usually work with models trained to minimize cross-entropy loss and output softmax probabilities. In this work, we present interesting experimental results that suggest the importance of considering other loss functions and target representations, specifically, (1) training on mean-squared error and (2) representing targets as codewords generated from a random codebook. We evaluate the robustness of neural networks that implement these proposed modifications using existing attacks, showing an increase in accuracy against untargeted attacks of up to 98.7\% and a decrease of targeted attack success rates of up to 99.8\%. Our model demonstrates more robustness compared to its conventional counterpart even against attacks that are tailored to our modifications. Furthermore, we find that the parameters of our modified model have significantly smaller Lipschitz bounds, an important measure correlated with a model's sensitivity to adversarial perturbations.
Simultaneous Detection of Multiple Change Points and Community Structures in Time Series of Networks
Venue: arXiv cs.SI 2020
Year: 2020

In many complex systems, networks and graphs arise in a natural manner. Often, time evolving behavior can be easily found and modeled using time-series methodology. Amongst others, two common research problems in network analysis are community detection and change-point detection. Community detection aims at finding specific sub-structures within the networks, and change-point detection tries to find the time points at which sub-structures change. We propose a novel methodology to detect both community structures and change points simultaneously based on a model selection framework in which the Minimum Description Length Principle (MDL) is utilized as minimizing objective criterion. The promising practical performance of the proposed method is illustrated via a series of numerical experiments and real data analysis.
Simulated Tempering Langevin Monte Carlo II: An Improved Proof using Soft Markov Chain Decomposition
Venue: arXiv cs.LG 2020
Year: 2020

A key task in Bayesian machine learning is sampling from distributions that are only specified up to a partition function (i.e., constant of proportionality). One prevalent example of this is sampling posteriors in parametric distributions, such as latent-variable generative models. However sampling (even very approximately) can be #P-hard. Classical results going back to Bakry and Émery (1985) on sampling focus on log-concave distributions, and show a natural Markov chain called Langevin diffusion mixes in polynomial time. However, all log-concave distributions are uni-modal, while in practice it is very common for the distribution of interest to have multiple modes. In this case, Langevin diffusion suffers from torpid mixing. We address this problem by combining Langevin diffusion with simulated tempering. The result is a Markov chain that mixes more rapidly by transitioning between different temperatures of the distribution. We analyze this Markov chain for a mixture of (strongly) log-concave distributions of the same shape. In particular, our technique applies to the canonical multi-modal distribution: a mixture of gaussians (of equal variance). Our algorithm efficiently samples from these distributions given only access to the gradient of the log-pdf. For the analysis, we introduce novel techniques for proving spectral gaps based on decomposing the action of the generator of the diffusion. Previous approaches rely on decomposing the state space as a partition of sets, while our approach can be thought of as decomposing the stationary measure as a mixture of distributions (a "soft partition"). Additional materials for the paper can be found at http://holdenlee.github.io/Simulated%20tempering%20Langevin%20Monte%20Carlo.html. The proof and results have been improved and generalized from the precursor at arXiv:1710.02736.
A Coalition-Based Communication Framework for Task-Driven Flying Ad-Hoc Networks
Venue: arXiv cs.NI 2020
Year: 2020

In this paper, we develop a task-driven networking framework for Flying Ad-hoc Networks (FANETs), where a coalition-based model is outlined. Firstly, we present a brief survey to show the state-of-the-art studies on the intra-communication of unmanned aerial vehicle (UAV) swarms. The features and deficiencies of existing models are analyzed. To capture the task-driven requirement of the flying multi-agent system, a coalition-based framework is proposed. We discuss the composition, networking mode and the classification of data transmission. After that, the application scenario of UAV coalitions is given, where large-scale, distributed and highly dynamic characteristics greatly increase the difficulty of resource optimization for UAVs. To tackle the problem, we design an intelligence-based optimization architecture, which mainly includes the game model, machine learning and real-time decision. Under the guidance of game theories and machine learning, UAVs can make comprehensive decisions by combining the previous training results with their sensing, information interaction, and game strategies. Finally, a preliminary case and promising open issues of UAV coalitions are studied.
PES: Priority Edge Sampling in Streaming Triangle Estimation
Venue: arXiv cs.SI 2020
Year: 2020

The number of triangles (hereafter denoted by $Δ$) is an important metric to analyze massive graphs. It is also used to compute clustering coefficient in networks. This paper proposes a new algorithm called PES (Priority Edge Sampling) to estimate the number of triangles in the streaming model where we need to minimize the memory window. PES combines edge sampling and reservoir sampling. Compared with the state-of-the-art streaming algorithms, PES outperforms consistently. The results are verified extensively in 48 large real-world networks in different domains and structures. The performance ratio can be as large as 11. More importantly, the ratio grows with data size almost exponentially. This is especially important in the era of big data--while we can tolerate existing algorithms for smaller datasets, our method is indispensable when sampling very large data. In addition to empirical comparisons, we also proved that the estimator is unbiased, and derived the variance.
Semi-Supervised Cross-Modal Retrieval with Label Prediction
Venue: arXiv cs.CV 2020
Year: 2020

Due to abundance of data from multiple modalities, cross-modal retrieval tasks with image-text, audio-image, etc. are gaining increasing importance. Of the different approaches proposed, supervised methods usually give significant improvement over their unsupervised counterparts at the additional cost of labeling or annotation of the training data. Semi-supervised methods are recently becoming popular as they provide an elegant framework to balance the conflicting requirement of labeling cost and accuracy. In this work, we propose a novel deep semi-supervised framework which can seamlessly handle both labeled as well as unlabeled data. The network has two important components: (a) the label prediction component predicts the labels for the unlabeled portion of the data and then (b) a common modality-invariant representation is learned for cross-modal retrieval. The two parts of the network are trained sequentially one after the other. Extensive experiments on three standard benchmark datasets, Wiki, Pascal VOC and NUS-WIDE demonstrate that the proposed framework outperforms the state-of-the-art for both supervised and semi-supervised settings.
The Robot Economy: Here It Comes
Venue: arXiv cs.RO 2020
Year: 2020

Automation is not a new phenomenon, and questions about its effects have long followed its advances. More than a half-century ago, US President Lyndon B. Johnson established a national commission to examine the impact of technology on the economy, declaring that automation "can be the ally of our prosperity if we will just look ahead". In this paper, our premise is that we are at a technological inflection point in which robots are developing the capacity to greatly increase their cognitive and physical capabilities, and thus raising questions on labor dynamics. With increasing levels of autonomy and human-robot interaction, intelligent robots could soon accomplish new human-like capabilities such as engaging into social activities. Therefore, an increase in automation and autonomy brings the question of robots directly participating in some economic activities as autonomous agents. In this paper, a technological framework describing a robot economy is outlined and the challenges it might represent in the current socio-economic scenario are pondered.
Dynamic Spatio-temporal Graph-based CNNs for Traffic Prediction
Venue: arXiv cs.CV 2020
Year: 2020

Forecasting future traffic flows from previous ones is a challenging problem because of their complex and dynamic nature of spatio-temporal structures. Most existing graph-based CNNs attempt to capture the static relations while largely neglecting the dynamics underlying sequential data. In this paper, we present dynamic spatio-temporal graph-based CNNs (DST-GCNNs) by learning expressive features to represent spatio-temporal structures and predict future traffic flows from surveillance video data. In particular, DST-GCNN is a two stream network. In the flow prediction stream, we present a novel graph-based spatio-temporal convolutional layer to extract features from a graph representation of traffic flows. Then several such layers are stacked together to predict future flows over time. Meanwhile, the relations between traffic flows in the graph are often time variant as the traffic condition changes over time. To capture the graph dynamics, we use the graph prediction stream to predict the dynamic graph structures, and the predicted structures are fed into the flow prediction stream. Experiments on real datasets demonstrate that the proposed model achieves competitive performances compared with the other state-of-the-art methods.
The Spread of Voting Attitudes in Social Networks
Venue: arXiv cs.DM 2020
Year: 2020

The Shapley-Shubik power index is a measure of each voters power in the passage or failure of a vote. We extend this measure to graphs and consider a discrete-time process in which voters may change their vote based on the outcome of the previous vote. We use this model to study how voter influence can spread through a network. We find conditions under which a vanishingly small portion of consenting voters can change the votes of the entirety of the network. For a particular family of graphs, this process can be modelled using cellular automata. In particular, we find a connection between this process and the well-studied cellular automata, Rule 90. We use this connection to show that such processes can exhibit arbitrarily-long periods.
Comparative Document Summarisation via Classification
Venue: arXiv cs.IR 2020
Year: 2020

This paper considers extractive summarisation in a comparative setting: given two or more document groups (e.g., separated by publication time), the goal is to select a small number of documents that are representative of each group, and also maximally distinguishable from other groups. We formulate a set of new objective functions for this problem that connect recent literature on document summarisation, interpretable machine learning, and data subset selection. In particular, by casting the problem as a binary classification amongst different groups, we derive objectives based on the notion of maximum mean discrepancy, as well as a simple yet effective gradient-based optimisation strategy. Our new formulation allows scalable evaluations of comparative summarisation as a classification task, both automatically and via crowd-sourcing. To this end, we evaluate comparative summarisation methods on a newly curated collection of controversial news topics over 13 months. We observe that gradient-based optimisation outperforms discrete and baseline approaches in 14 out of 24 different automatic evaluation settings. In crowd-sourced evaluations, summaries from gradient optimisation elicit 7% more accurate classification from human workers than discrete optimisation. Our result contrasts with recent literature on submodular data subset selection that favours discrete optimisation. We posit that our formulation of comparative summarisation will prove useful in a diverse range of use cases such as comparing content sources, authors, related topics, or distinct view points.
Neural Abstractive Text Summarization with Sequence-to-Sequence Models
Venue: arXiv cs.CL 2020
Year: 2020

In the past few years, neural abstractive text summarization with sequence-to-sequence (seq2seq) models have gained a lot of popularity. Many interesting techniques have been proposed to improve seq2seq models, making them capable of handling different challenges, such as saliency, fluency and human readability, and generate high-quality summaries. Generally speaking, most of these techniques differ in one of these three categories: network structure, parameter inference, and decoding/generation. There are also other concerns, such as efficiency and parallelism for training a model. In this paper, we provide a comprehensive literature survey on different seq2seq models for abstractive text summarization from the viewpoint of network structures, training strategies, and summary generation algorithms. Several models were first proposed for language modeling and generation tasks, such as machine translation, and later applied to abstractive text summarization. Hence, we also provide a brief review of these models. As part of this survey, we also develop an open source library, namely, Neural Abstractive Text Summarizer (NATS) toolkit, for the abstractive text summarization. An extensive set of experiments have been conducted on the widely used CNN/Daily Mail dataset to examine the effectiveness of several different neural network components. Finally, we benchmark two models implemented in NATS on the two recently released datasets, namely, Newsroom and Bytecup.
Guided Zoom: Questioning Network Evidence for Fine-grained Classification
Venue: arXiv cs.CV 2020
Year: 2020

We propose Guided Zoom, an approach that utilizes spatial grounding of a model's decision to make more informed predictions. It does so by making sure the model has "the right reasons" for a prediction, defined as reasons that are coherent with those used to make similar correct decisions at training time. The reason/evidence upon which a deep convolutional neural network makes a prediction is defined to be the spatial grounding, in the pixel space, for a specific class conditional probability in the model output. Guided Zoom examines how reasonable such evidence is for each of the top-k predicted classes, rather than solely trusting the top-1 prediction. We show that Guided Zoom improves the classification accuracy of a deep convolutional neural network model and obtains state-of-the-art results on three fine-grained classification benchmark datasets.
Secure Federated Transfer Learning
Venue: arXiv cs.LG 2020
Year: 2020

Machine learning relies on the availability of a vast amount of data for training. However, in reality, most data are scattered across different organizations and cannot be easily integrated under many legal and practical constraints. In this paper, we introduce a new technique and framework, known as federated transfer learning (FTL), to improve statistical models under a data federation. The federation allows knowledge to be shared without compromising user privacy, and enables complimentary knowledge to be transferred in the network. As a result, a target-domain party can build more flexible and powerful models by leveraging rich labels from a source-domain party. A secure transfer cross validation approach is also proposed to guard the FTL performance under the federation. The framework requires minimal modifications to the existing model structure and provides the same level of accuracy as the non-privacy-preserving approach. This framework is very flexible and can be effectively adapted to various secure multi-party machine learning tasks.
Toward a General Theory of Motion Planning Complexity: Characterizing Which Gadgets Make Games Hard
Venue: arXiv cs.CC 2020
Year: 2020

We build a general theory for characterizing the computational complexity of motion planning of robot(s) through a graph of "gadgets", where each gadget has its own state defining a set of allowed traversals which in turn modify the gadget's state. We study two families of such gadgets, one which naturally leads to motion planning problems with polynomially bounded solutions, and another which leads to polynomially unbounded (potentially exponential) solutions. We also study a range of competitive game-theoretic scenarios, from one player controlling one robot to teams of players each controlling their own robot and racing to achieve their team's goal. Under small restrictions on these gadgets, we fully characterize the complexity of bounded 1-player motion planning (NL vs. NP-complete), unbounded 1-player motion planning (NL vs. PSPACE-complete), and bounded 2-player motion planning (P vs. PSPACE-complete), and we partially characterize the complexity of unbounded 2-player motion planning (P vs. EXPTIME-complete), bounded 2-team motion planning (P vs. NEXPTIME-complete), and unbounded 2-team motion planning (P vs. undecidable). These results can be seen as an alternative to Constraint Logic (which has already proved useful as a basis for hardness reductions), providing a wide variety of agent-based gadgets, any one of which suffices to prove a problem hard.
An Open-Source System for Vision-Based Micro-Aerial Vehicle Mapping, Planning, and Flight in Cluttered Environments
Venue: arXiv cs.RO 2020
Year: 2020

We present an open-source system for Micro-Aerial Vehicle autonomous navigation from vision-based sensing. Our system focuses on dense mapping, safe local planning, and global trajectory generation, especially when using narrow field of view sensors in very cluttered environments. In addition, details about other necessary parts of the system and special considerations for applications in real-world scenarios are presented. We focus our experiments on evaluating global planning, path smoothing, and local planning methods on real maps made on MAVs in realistic search and rescue and industrial inspection scenarios. We also perform thousands of simulations in cluttered synthetic environments, and finally validate the complete system in real-world experiments.
A Unified Approach to Scalable Spectral Sparsification of Directed Graphs
Venue: arXiv cs.DS 2020
Year: 2020

Recent spectral graph sparsification research allows constructing nearly-linear-sized subgraphs that can well preserve the spectral (structural) properties of the original graph, such as the first few eigenvalues and eigenvectors of the graph Laplacian, leading to the development of a variety of nearly-linear time numerical and graph algorithms. However, there is not a unified approach that allows for truly-scalable spectral sparsification of both directed and undirected graphs. In this work, we prove the existence of linear-sized spectral sparsifiers for general directed graphs and introduce a practically-efficient and unified spectral graph sparsification approach that allows sparsifying real-world, large-scale directed and undirected graphs with guaranteed preservation of the original graph spectra. By exploiting a highly-scalable (nearly-linear complexity) spectral matrix perturbation analysis framework for constructing nearly-linear sized (directed) subgraphs, it enables us to well preserve the key eigenvalues and eigenvectors of the original (directed) graph Laplacians. The proposed method has been validated using various kinds of directed graphs obtained from public domain sparse matrix collections, showing promising results for solving directed graph Laplacians, spectral embedding, and partitioning of general directed graphs, as well as approximately computing (personalized) PageRank vectors.
Towards Understanding Language through Perception in Situated Human-Robot Interaction: From Word Grounding to Grammar Induction
Venue: arXiv cs.CL 2020
Year: 2020

Robots are widely collaborating with human users in diferent tasks that require high-level cognitive functions to make them able to discover the surrounding environment. A difcult challenge that we briefy highlight in this short paper is inferring the latent grammatical structure of language, which includes grounding parts of speech (e.g., verbs, nouns, adjectives, and prepositions) through visual perception, and induction of Combinatory Categorial Grammar (CCG) for phrases. This paves the way towards grounding phrases so as to make a robot able to understand human instructions appropriately during interaction.
Learning Features of Network Structures Using Graphlets
Venue: arXiv cs.SI 2020
Year: 2020

Networks are fundamental to the study of complex systems, ranging from social contacts, message transactions, to biological regulations and economical networks. In many realistic applications, these networks may vary over time. Modeling and analyzing such temporal properties is of additional interest as it can provide a richer characterization of relations between nodes in networks. In this paper, we explore the role of \emph{graphlets} in network classification for both static and temporal networks. Graphlets are small non-isomorphic induced subgraphs representing connected patterns in a network and their frequency can be used to assess network structures. We show that graphlet features, which are not captured by state-of-the-art methods, play a significant role in enhancing the performance of network classification. To that end, we propose two novel graphlet-based techniques, \emph{gl2vec} for network embedding, and \emph{gl-DCNN} for diffusion-convolutional neural networks. We demonstrate the efficacy and usability of \emph{gl2vec} and \emph{gl-DCNN} through extensive experiments using several real-world static and temporal networks. We find that features learned from graphlets can bring notable performance increases to state-of-the-art methods in network analysis.