OpenRaiser/Intern-Atlas huggingface dataset:
Computing Resource Allocation of Mobile Edge Computing Networks Based on Potential Game Theory
Venue: arXiv cs.NI 2019
Year: 2019

Mobile edge computing (MEC) networks are one of the key technologies for ultra-reliability and low-latency communications. The computing resource allocation solution needs to be carefully designed to guarantee the computing resource efficiency of MEC networks. Based on the potential game theory, a computing resource allocation solution is proposed to reduce energy consumption and improve computing resource efficiency in MEC networks. The computing resource allocation solution includes two parts: the first part is the power control scheme based on the potential game theory and the second part is the computing resource allocation scheme based on linear programming. The power control scheme is to find a set of the transmission powers of base stations (BSs) that maximizes the potential function of MEC networks. The computing resource allocation scheme is to maximize the average computing resource allocation coefficient of the MEC networks based on the results of the power control scheme. Compared with traditional solutions, simulation results indicate the computing resource utilization and energy efficiency of the proposed computing resource allocation solution are significantly improved.
Leader Election in Well-Connected Graphs
Venue: arXiv cs.DC 2019
Year: 2019

In this paper, we look at the problem of randomized leader election in synchronous distributed networks with a special focus on the message complexity. We provide an algorithm that solves the implicit version of leader election (where non-leader nodes need not be aware of the identity of the leader) in any general network with $O(\sqrt{n} \log^{7/2} n \cdot t_{mix})$ messages and in $O(t_{mix}\log^2 n)$ time, where $n$ is the number of nodes and $t_{mix}$ refers to the mixing time of a random walk in the network graph $G$. For several classes of well-connected networks (that have a large conductance or alternatively small mixing times e.g. expanders, hypercubes, etc), the above result implies extremely efficient (sublinear running time and messages) leader election algorithms. Correspondingly, we show that any substantial improvement is not possible over our algorithm, by presenting an almost matching lower bound for randomized leader election. We show that $Ω(\sqrt{n}/ϕ^{3/4})$ messages are needed for any leader election algorithm that succeeds with probability at least $1-o(1)$, where $ϕ$ refers to the conductance of a graph. To the best of our knowledge, this is the first work that shows a dependence between the time and message complexity to solve leader election and the connectivity of the graph $G$, which is often characterized by the graph's conductance $ϕ$. Apart from the $Ω(m)$ bound in [Kutten et al., J.ACM 2015] (where $m$ denotes the number of edges of the graph), this work also provides one of the first non-trivial lower bounds for leader election in general networks.
Learning Efficient Detector with Semi-supervised Adaptive Distillation
Venue: arXiv cs.CV 2019
Year: 2019

Knowledge Distillation (KD) has been used in image classification for model compression. However, rare studies apply this technology on single-stage object detectors. Focal loss shows that the accumulated errors of easily-classified samples dominate the overall loss in the training process. This problem is also encountered when applying KD in the detection task. For KD, the teacher-defined hard samples are far more important than any others. We propose ADL to address this issue by adaptively mimicking the teacher's logits, with more attention paid on two types of hard samples: hard-to-learn samples predicted by teacher with low certainty and hard-to-mimic samples with a large gap between the teacher's and the student's prediction. ADL enlarges the distillation loss for hard-to-learn and hard-to-mimic samples and reduces distillation loss for the dominant easy samples, enabling distillation to work on the single-stage detector first time, even if the student and the teacher are identical. Besides, ADL is effective in both the supervised setting and the semi-supervised setting, even when the labeled data and unlabeled data are from different distributions. For distillation on unlabeled data, ADL achieves better performance than existing data distillation which simply utilizes hard targets, making the student detector surpass its teacher. On the COCO database, semi-supervised adaptive distillation (SAD) makes a student detector with a backbone of ResNet-50 surpasses its teacher with a backbone of ResNet-101, while the student has half of the teacher's computation complexity. The code is avaiable at https://github.com/Tangshitao/Semi-supervised-Adaptive-Distillation
Persistent homology of unweighted complex networks via discrete Morse theory
Venue: arXiv cs.DM 2019
Year: 2019

Topological data analysis can reveal higher-order structure beyond pairwise connections between vertices in complex networks. We present a new method based on discrete Morse theory to study topological properties of unweighted and undirected networks using persistent homology. Leveraging on the features of discrete Morse theory, our method not only captures the topology of the clique complex of such graphs via the concept of critical simplices, but also achieves close to the theoretical minimum number of critical simplices in several analyzed model and real networks. This leads to a reduced filtration scheme based on the subsequence of the corresponding critical weights, thereby leading to a significant increase in computational efficiency. We have employed our filtration scheme to explore the persistent homology of several model and real-world networks. In particular, we show that our method can detect differences in the higher-order structure of networks, and the corresponding persistence diagrams can be used to distinguish between different model networks. In summary, our method based on discrete Morse theory further increases the applicability of persistent homology to investigate the global topology of complex networks.
Towards the Locality of Vizing's Theorem
Venue: arXiv cs.DS 2019
Year: 2019

Vizing showed that it suffices to color the edges of a simple graph using $Δ+ 1$ colors, where $Δ$ is the maximum degree of the graph. However, up to this date, no efficient distributed edge-coloring algorithms are known for obtaining such a coloring, even for constant degree graphs. The current algorithms that get closest to this number of colors are the randomized $(Δ+ \tildeΘ(\sqrtΔ))$-edge-coloring algorithm that runs in $\text{polylog}(n)$ rounds by Chang et al. (SODA '18) and the deterministic $(Δ+ \text{polylog}(n))$-edge-coloring algorithm that runs in $\text{poly}(Δ, \log n)$ rounds by Ghaffari et al. (STOC '18). We present two distributed edge-coloring algorithms that run in $\text{poly}(Δ,\log n)$ rounds. The first algorithm, with randomization, uses only $Δ+2$ colors. The second algorithm is a deterministic algorithm that uses $Δ+ O(\log n/ \log \log n)$ colors. Our approach is to reduce the distributed edge-coloring problem into an online, restricted version of balls-into-bins problem. If $\ell$ is the maximum load of the bins, our algorithm uses $Δ+ 2\ell - 1$ colors. We show how to achieve $\ell = 1$ with randomization and $\ell = O(\log n / \log \log n)$ without randomization.
Action2Vec: A Crossmodal Embedding Approach to Action Learning
Venue: arXiv cs.CV 2019
Year: 2019

We describe a novel cross-modal embedding space for actions, named Action2Vec, which combines linguistic cues from class labels with spatio-temporal features derived from video clips. Our approach uses a hierarchical recurrent network to capture the temporal structure of video features. We train our embedding using a joint loss that combines classification accuracy with similarity to Word2Vec semantics. We evaluate Action2Vec by performing zero shot action recognition and obtain state of the art results on three standard datasets. In addition, we present two novel analogy tests which quantify the extent to which our joint embedding captures distributional semantics. This is the first joint embedding space to combine verbs and action videos, and the first to be thoroughly evaluated with respect to its distributional semantics.
Measuring Physical Activity of Older Adults via Smartwatch and Stigmergic Receptive Fields
Venue: arXiv cs.HC 2019
Year: 2019

Physical activity level (PAL) in older adults can enhance healthy aging, improve functional capacity, and prevent diseases. It is known that human annotations of PAL can be affected by subjectivity and inaccuracy. Recently developed smart devices can allow a non-invasive, analytic, and continuous gathering of physiological signals. We present an innovative computational system fed by signals of heartbeat rate, wrist motion and pedometer sensed by a smartwatch. More specifically, samples of each signal are aggregated by functional structures called trails. The trailing process is inspired by stigmergy, an insects' coordination mechanism, and is managed by computational units called stigmergic receptive fields (SRFs). SRFs, which compute the similarity between trails, are arranged in a stigmergic perceptron to detect a collection of micro-behaviours of the raw signal, called archetypes. A SRF is adaptive to subjects: its structural parameters are tuned by a differential evolution algorithm. SRFs are used in a multilayer architecture, providing further levels of processing to realize macro analyses in the application domain. As a result, the architecture provides a daily PAL, useful to detect behavioural shift indicating initial signs of disease or deviations in performance. As a proof of concept, the approach has been experimented on three subjects.
Adaptive Locality Preserving Regression
Venue: arXiv cs.CV 2019
Year: 2019

This paper proposes a novel discriminative regression method, called adaptive locality preserving regression (ALPR) for classification. In particular, ALPR aims to learn a more flexible and discriminative projection that not only preserves the intrinsic structure of data, but also possesses the properties of feature selection and interpretability. To this end, we introduce a target learning technique to adaptively learn a more discriminative and flexible target matrix rather than the pre-defined strict zero-one label matrix for regression. Then a locality preserving constraint regularized by the adaptive learned weights is further introduced to guide the projection learning, which is beneficial to learn a more discriminative projection and avoid overfitting. Moreover, we replace the conventional `Frobenius norm' with the special l21 norm to constrain the projection, which enables the method to adaptively select the most important features from the original high-dimensional data for feature extraction. In this way, the negative influence of the redundant features and noises residing in the original data can be greatly eliminated. Besides, the proposed method has good interpretability for features owing to the row-sparsity property of the l21 norm. Extensive experiments conducted on the synthetic database with manifold structure and many real-world databases prove the effectiveness of the proposed method.
Causality Analysis for Concurrent Reactive Systems (Extended Abstract)
Venue: arXiv cs.FL 2019
Year: 2019

We present a comprehensive language theoretic causality analysis framework for explaining safety property violations in the setting of concurrent reactive systems. Our framework allows us to uniformly express a number of causality notions studied in the areas of artificial intelligence and formal methods, as well as define new ones that are of potential interest in these areas. Furthermore, our formalization provides means for reasoning about the relationships between individual notions which have mostly been considered independently in prior work; and allows us to judge the appropriateness of the different definitions for various applications in system design. In particular, we consider causality analysis notions for debugging, error resilience, and liability resolution in concurrent reactive systems. Finally, we present automata-based algorithms for computing various causal sets based on our language-theoretic encoding, and derive the algorithmic complexities.
Interactions between Causal Structures in Graph Rewriting Systems
Venue: arXiv cs.LO 2019
Year: 2019

Graph rewrite formalisms are a powerful approach to modeling complex molecular systems. They capture the intrinsic concurrency of molecular interactions, thereby enabling a formal notion of mechanism (a partially ordered set of events) that explains how a system achieves a particular outcome given a set of rewrite rules. It is then useful to verify whether the mechanisms that emerge from a given model comply with empirical observations about their mutual interference. In this work, our objective is to determine whether a specific event in the mechanism for achieving X prevents or promotes the occurrence of a specific event in the mechanism for achieving Y. Such checks might also be used to hypothesize rules that would bring model mechanisms in compliance with observations. We define a rigorous framework for defining the concept of interference (positive or negative) between mechanisms induced by a system of graph-rewrite rules and for establishing whether an asserted influence can be realized given two mechanisms as an input.
A Comprehensive Survey on Graph Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

Deep learning has revolutionized many machine learning tasks in recent years, ranging from image classification and video processing to speech recognition and natural language understanding. The data in these tasks are typically represented in the Euclidean space. However, there is an increasing number of applications where data are generated from non-Euclidean domains and are represented as graphs with complex relationships and interdependency between objects. The complexity of graph data has imposed significant challenges on existing machine learning algorithms. Recently, many studies on extending deep learning approaches for graph data have emerged. In this survey, we provide a comprehensive overview of graph neural networks (GNNs) in data mining and machine learning fields. We propose a new taxonomy to divide the state-of-the-art graph neural networks into four categories, namely recurrent graph neural networks, convolutional graph neural networks, graph autoencoders, and spatial-temporal graph neural networks. We further discuss the applications of graph neural networks across various domains and summarize the open source codes, benchmark data sets, and model evaluation of graph neural networks. Finally, we propose potential research directions in this rapidly growing field.
Edge-Semantic Learning Strategy for Layout Estimation in Indoor Environment
Venue: arXiv cs.CV 2019
Year: 2019

Visual cognition of the indoor environment can benefit from the spatial layout estimation, which is to represent an indoor scene with a 2D box on a monocular image. In this paper, we propose to fully exploit the edge and semantic information of a room image for layout estimation. More specifically, we present an encoder-decoder network with shared encoder and two separate decoders, which are composed of multiple deconvolution (transposed convolution) layers, to jointly learn the edge maps and semantic labels of a room image. We combine these two network predictions in a scoring function to evaluate the quality of the layouts, which are generated by ray sampling and from a predefined layout pool. Guided by the scoring function, we apply a novel refinement strategy to further optimize the layout hypotheses. Experimental results show that the proposed network can yield accurate estimates of edge maps and semantic labels. By fully utilizing the two different types of labels, the proposed method achieves state-of-the-art layout estimation performance on benchmark datasets.
A Fast Sketch Method for Mining User Similarities over Fully Dynamic Graph Streams
Venue: arXiv cs.DS 2019
Year: 2019

Many real-world networks such as Twitter and YouTube are given as fully dynamic graph streams represented as sequences of edge insertions and deletions. (e.g., users can subscribe and unsubscribe to channels on YouTube). Existing similarity estimation methods such as MinHash and OPH are customized to static graphs. We observe that they are indeed sampling methods and exhibit a sampling bias when applied to fully dynamic graph streams, which results in large estimation errors. To solve this challenge, we develop a fast and accurate sketch method VOS. VOS processes each edge in the graph stream of interest with small time complexity O(1) and uses small memory space to build a compact sketch of the dynamic graph stream over time. Based on the sketch built on-the-fly, we develop a method to estimate user similarities over time. We conduct extensive experiments and the experimental results demonstrate the efficiency and efficacy of our method.
Mergeable Dictionaries With Shifts
Venue: arXiv cs.DS 2019
Year: 2019

We revisit the mergeable dictionaries with shift problem, where the goal is to maintain a family of sets subject to search, split, merge, make-set, and shift operations. The search, split, and make-set operations are the usual well-known textbook operations. The merge operation merges two sets and the shift operation adds or subtracts an integer from all elements in a set. Note that unlike the join operation on standard balanced search tree structures, such as AVL trees or 2-4 trees, the merge operation has no restriction on the key space of the input sets and supports merging arbitrarily interleaved sets. This problem is a key component in searching Lempel-Ziv compressed texts, in the mergeable trees problem, and in the union-split-find problem. We present the first solution achieving O(log U) amortized time for all operations, where {1, 2, ..., U} is the universe of the sets. This bound is optimal when the size of the universe is polynomially bounded by the sum of the sizes of the sets. Our solution is simple and based on a novel extension of biased search trees.
Low-Cost Device Prototype for Automatic Medical Diagnosis Using Deep Learning Methods
Venue: arXiv cs.CY 2019
Year: 2019

This paper introduces a novel low-cost device prototype for the automatic diagnosis of diseases, utilizing inputted symptoms and personal background. The engineering goal is to solve the problem of limited healthcare access with a single device. Diagnosing diseases automatically is an immense challenge, owing to their variable properties and symptoms. On the other hand, Neural Networks have developed into a powerful tool in the field of machine learning, one that is showing to be extremely promising at computing diagnosis even with inconsistent variables. In this research, a cheap device was created to allow for straightforward diagnosis and treatment of human diseases. By utilizing Deep Neural Networks (DNNs) and Convolutional Neural Networks (CNNs), outfitted on a Raspberry Pi Zero processor ($5), the device is able to detect up to 1537 different diseases and conditions and utilize a CNN for on-device visual diagnostics. The user can input the symptoms using the buttons on the device and can take pictures using the same mechanism. The algorithm processes inputted symptoms, providing diagnosis and possible treatment options for common conditions. The purpose of this work was to be able to diagnose diseases through an affordable processor with high accuracy, as it is currently achieving an accuracy of 90% for Top-5 symptom-based diagnoses, and 91% for visual skin diseases. The NNs achieve performance far above any other tested system, and its efficiency and ease of use will prove it to be a helpful tool for people around the world. This device could potentially provide low-cost universal access to vital diagnostics and treatment options.
A dynamic ridesharing dispatch and idle vehicle repositioning strategy with integrated transit transfers
Venue: arXiv cs.CY 2019
Year: 2019

We propose a ridesharing strategy with integrated transit in which a private on-demand mobility service operator may drop off a passenger directly door-to-door, commit to dropping them at a transit station or picking up from a transit station, or to both pickup and drop off at two different stations with different vehicles. We study the effectiveness of online solution algorithms for this proposed strategy. Queueing-theoretic vehicle dispatch and idle vehicle relocation algorithms are customized for the problem. Several experiments are conducted first with a synthetic instance to design and test the effectiveness of this integrated solution method, the influence of different model parameters, and measure the benefit of such cooperation. Results suggest that rideshare vehicle travel time can drop by 40-60% consistently while passenger journey times can be reduced by 50-60% when demand is high. A case study of Long Island commuters to New York City (NYC) suggests having the proposed operating strategy can substantially cut user journey times and operating costs by up to 54% and 60% each for a range of 10-30 taxis initiated per zone. This result shows that there are settings where such service is highly warranted.
A^2-Net: Molecular Structure Estimation from Cryo-EM Density Volumes
Venue: arXiv cs.LG 2019
Year: 2019

Constructing of molecular structural models from Cryo-Electron Microscopy (Cryo-EM) density volumes is the critical last step of structure determination by Cryo-EM technologies. Methods have evolved from manual construction by structural biologists to perform 6D translation-rotation searching, which is extremely compute-intensive. In this paper, we propose a learning-based method and formulate this problem as a vision-inspired 3D detection and pose estimation task. We develop a deep learning framework for amino acid determination in a 3D Cryo-EM density volume. We also design a sequence-guided Monte Carlo Tree Search (MCTS) to thread over the candidate amino acids to form the molecular structure. This framework achieves 91% coverage on our newly proposed dataset and takes only a few minutes for a typical structure with a thousand amino acids. Our method is hundreds of times faster and several times more accurate than existing automated solutions without any human intervention.
Scalable Information-Flow Analysis of Secure Three-Party Affine Computations
Venue: arXiv cs.CR 2019
Year: 2019

Elaborate protocols in Secure Multi-party Computation enable several participants to compute a public function of their own private inputs while ensuring that no undesired information leaks about the private inputs, and without resorting to any trusted third party. However, the public output of the computation inevitably leaks some information about the private inputs. Recent works have introduced a framework and proposed some techniques for quantifying such information flow. Yet, owing to their complexity, those methods do not scale to practical situations that may involve large input spaces. The main contribution of the work reported here is to formally investigate the information flow captured by the min-entropy in the particular case of secure three-party computations of affine functions in order to make its quantification scalable to realistic scenarios. To this end, we mathematically derive an explicit formula for this entropy under uniform prior beliefs about the inputs. We show that this closed-form expression can be computed in time constant in the inputs sizes and logarithmic in the coefficients of the affine function. Finally, we formulate some theoretical bounds for this privacy leak in the presence of non-uniform prior beliefs.