OpenRaiser/Intern-Atlas huggingface dataset:
Network Community Detection with A Successive Spectral Relaxation Method
Venue: arXiv cs.SI 2018
Year: 2018

With invaluable theoretical and practical benefits, the problem of partitioning networks for community structures has attracted significant research attention in scientific and engineering disciplines. In literature, Newman's modularity measure is routinely applied to quantify the quality of a given partition, and thereby maximizing the measure provides a principled way of detecting communities in networks. Unfortunately, the exact optimization of the measure is computationally NP-complete and only applicable to very small networks. Approximation approaches have to be sought to scale to large networks. To address the computational issue, we proposed a new method to identify the partition decisions. Coupled with an iterative rounding strategy and a fast constrained power method, our work achieves tight and effective spectral relaxations. The proposed method was evaluated thoroughly on both real and synthetic networks. Compared with state-of-the-art approaches, the method obtained comparable, if not better, qualities. Meanwhile, it is highly suitable for parallel execution and reported a nearly linear improvement in running speed when increasing the number of computing nodes, which thereby provides a practical tool for partitioning very large networks.
Shortest $k$-Disjoint Paths via Determinants
Venue: arXiv cs.DS 2018
Year: 2018

The well-known $k$-disjoint path problem ($k$-DPP) asks for pairwise vertex-disjoint paths between $k$ specified pairs of vertices $(s_i, t_i)$ in a given graph, if they exist. The decision version of the shortest $k$-DPP asks for the length of the shortest (in terms of total length) such paths. Similarly the search and counting versions ask for one such and the number of such shortest set of paths, respectively. We restrict attention to the shortest $k$-DPP instances on undirected planar graphs where all sources and sinks lie on a single face or on a pair of faces. We provide efficient sequential and parallel algorithms for the search versions of the problem answering one of the main open questions raised by Colin de Verdiere and Schrijver for the general one-face problem. We do so by providing a randomised $NC^2$ algorithm along with an $O(n^ω)$ time randomised sequential algorithm. We also obtain deterministic algorithms with similar resource bounds for the counting and search versions. In contrast, previously, only the sequential complexity of decision and search versions of the "well-ordered" case has been studied. For the one-face case, sequential versions of our routines have better running times for constantly many terminals. In addition, the earlier best known sequential algorithms (e.g. Borradaile et al.) were randomised while ours are also deterministic. The algorithms are based on a bijection between a shortest $k$-tuple of disjoint paths in the given graph and cycle covers in a related digraph. This allows us to non-trivially modify established techniques relating counting cycle covers to the determinant. We further need to do a controlled inclusion-exclusion to produce a polynomial sum of determinants such that all "bad" cycle covers cancel out in the sum allowing us to count "good" cycle covers.
Online Compact Convexified Factorization Machine
Venue: arXiv cs.LG 2018
Year: 2018

Factorization Machine (FM) is a supervised learning approach with a powerful capability of feature engineering. It yields state-of-the-art performance in various batch learning tasks where all the training data is made available prior to the training. However, in real-world applications where the data arrives sequentially in a streaming manner, the high cost of re-training with batch learning algorithms has posed formidable challenges in the online learning scenario. The initial challenge is that no prior formulations of FM could fulfill the requirements in Online Convex Optimization (OCO) -- the paramount framework for online learning algorithm design. To address the aforementioned challenge, we invent a new convexification scheme leading to a Compact Convexified FM (CCFM) that seamlessly meets the requirements in OCO. However for learning Compact Convexified FM (CCFM) in the online learning setting, most existing algorithms suffer from expensive projection operations. To address this subsequent challenge, we follow the general projection-free algorithmic framework of Online Conditional Gradient and propose an Online Compact Convex Factorization Machine (OCCFM) algorithm that eschews the projection operation with efficient linear optimization steps. In support of the proposed OCCFM in terms of its theoretical foundation, we prove that the developed algorithm achieves a sub-linear regret bound. To evaluate the empirical performance of OCCFM, we conduct extensive experiments on 6 real-world datasets for online recommendation and binary classification tasks. The experimental results show that OCCFM outperforms the state-of-art online learning algorithms.
Deterministic Regular Expressions With Back-References
Venue: arXiv cs.FL 2018
Year: 2018

Most modern libraries for regular expression matching allow back-references (i.e., repetition operators) that substantially increase expressive power, but also lead to intractability. In order to find a better balance between expressiveness and tractability, we combine these with the notion of determinism for regular expressions used in XML DTDs and XML Schema. This includes the definition of a suitable automaton model, and a generalization of the Glushkov construction. We demonstrate that, compared to their non-deterministic superclass, these deterministic regular expressions with back-references have desirable algorithmic properties (i.e., efficiently solvable membership problem and some decidable problems in static analysis), while, at the same time, their expressive power exceeds that of deterministic regular expressions without back-references.
Smart Contracts Software Metrics: a First Study
Venue: arXiv cs.SE 2018
Year: 2018

Smart contracts (SC) are software codes which reside and run over a blockchain. The code can be written in different languages with the common purpose of implementing various kinds of transactions onto the hosting blockchain, They are ruled by the blockchain infrastructure and work in order to satisfy conditions typical of traditional contracts. The software code must satisfy constrains strongly context dependent which are quite different from traditional software code. In particular, since the bytecode is uploaded in the hosting blockchain, size, computational resources, interaction between different parts of software are all limited and even if the specific software languages implement more or less the same constructs of traditional languages there is not the same freedom as in normal software development. SC software is expected to reflect these constrains on SC software metrics which should display metric values characteristic of the domain and different from more traditional software metrics. We tested this hypothesis on the code of more than twelve thousands SC written in Solidity and uploaded on the Ethereum blockchain. We downloaded the SC from a public repository and computed the statistics of a set of software metrics related to SC and compared them to the metrics extracted from more traditional software projects. Our results show that generally Smart Contracts metrics have ranges more restricted than the corresponding metrics in traditional software systems. Some of the stylized facts, like power law in the tail of the distribution of some metrics, are only approximate but the lines of code follow a log normal distribution which reminds of the same behavior already found in traditional software systems.
Abstractly Interpreting Argumentation Frameworks for Sharpening Extensions
Venue: arXiv cs.AI 2018
Year: 2018

Cycles of attacking arguments pose non-trivial issues in Dung style argumentation theory, apparent behavioural difference between odd and even length cycles being a notable one. While a few methods were proposed for treating them, to - in particular - enable selection of acceptable arguments in an odd-length cycle when Dung semantics could select none, so far the issues have been observed from a purely argument-graph-theoretic perspective. Per contra, we consider argument graphs together with a certain lattice like semantic structure over arguments e.g. ontology. As we show, the semantic-argumentgraphic hybrid theory allows us to apply abstract interpretation, a widely known methodology in static program analysis, to formal argumentation. With this, even where no arguments in a cycle could be selected sensibly, we could say more about arguments acceptability of an argument framework that contains it. In a certain sense, we can verify Dung extensions with respect to a semantic structure in this hybrid theory, to consolidate our confidence in their suitability. By defining the theory, and by making comparisons to existing approaches, we ultimately discover that whether Dung semantics, or an alternative semantics such as cf2, is adequate or problematic depends not just on an argument graph but also on the semantic relation among the arguments in the graph.
Real-time Prediction of Intermediate-Horizon Automotive Collision Risk
Venue: arXiv cs.CV 2018
Year: 2018

Advanced collision avoidance and driver hand-off systems can benefit from the ability to accurately predict, in real time, the probability a vehicle will be involved in a collision within an intermediate horizon of 10 to 20 seconds. The rarity of collisions in real-world data poses a significant challenge to developing this capability because, as we demonstrate empirically, intermediate-horizon risk prediction depends heavily on high-dimensional driver behavioral features. As a result, a large amount of data is required to fit an effective predictive model. In this paper, we assess whether simulated data can help alleviate this issue. Focusing on highway driving, we present a three-step approach for generating data and fitting a predictive model capable of real-time prediction. First, high-risk automotive scenes are generated using importance sampling on a learned Bayesian network scene model. Second, collision risk is estimated through Monte Carlo simulation. Third, a neural network domain adaptation model is trained on real and simulated data to address discrepancies between the two domains. Experiments indicate that simulated data can mitigate issues resulting from collision rarity, thereby improving risk prediction in real-world data.
One-Shot Imitation from Observing Humans via Domain-Adaptive Meta-Learning
Venue: arXiv cs.LG 2018
Year: 2018

Humans and animals are capable of learning a new behavior by observing others perform the skill just once. We consider the problem of allowing a robot to do the same -- learning from a raw video pixels of a human, even when there is substantial domain shift in the perspective, environment, and embodiment between the robot and the observed human. Prior approaches to this problem have hand-specified how human and robot actions correspond and often relied on explicit human pose detection systems. In this work, we present an approach for one-shot learning from a video of a human by using human and robot demonstration data from a variety of previous tasks to build up prior knowledge through meta-learning. Then, combining this prior knowledge and only a single video demonstration from a human, the robot can perform the task that the human demonstrated. We show experiments on both a PR2 arm and a Sawyer arm, demonstrating that after meta-learning, the robot can learn to place, push, and pick-and-place new objects using just one video of a human performing the manipulation.
Selective Sampling and Mixture Models in Generative Adversarial Networks
Venue: arXiv cs.LG 2018
Year: 2018

In this paper, we propose a multi-generator extension to the adversarial training framework, in which the objective of each generator is to represent a unique component of a target mixture distribution. In the training phase, the generators cooperate to represent, as a mixture, the target distribution while maintaining distinct manifolds. As opposed to traditional generative models, inference from a particular generator after training resembles selective sampling from a unique component in the target distribution. We demonstrate the feasibility of the proposed architecture both analytically and with basic Multi-Layer Perceptron (MLP) models trained on the MNIST dataset.
Adviser Networks: Learning What Question to Ask for Human-In-The-Loop Viewpoint Estimation
Venue: arXiv cs.CV 2018
Year: 2018

Humans have an unparalleled visual intelligence and can overcome visual ambiguities that machines currently cannot. Recent works have shown that incorporating guidance from humans during inference for monocular viewpoint-estimation can help overcome difficult cases in which the computer-alone would have otherwise failed. These hybrid intelligence approaches are hence gaining traction. However, deciding what question to ask the human at inference time remains an unknown for these problems. We address this question by formulating it as an Adviser Problem: can we learn a mapping from the input to a specific question to ask the human to maximize the expected positive impact to the overall task? We formulate a solution to the adviser problem for viewpoint estimation using a deep network where the question asks for the location of a keypoint in the input image. We show that by using the Adviser Network's recommendations, the model and the human outperforms the previous hybrid-intelligence state-of-the-art by 3.7%, and the computer-only state-of-the-art by 5.28% absolute.
Polynomial Invariants for Affine Programs
Venue: arXiv cs.LO 2018
Year: 2018

We exhibit an algorithm to compute the strongest polynomial (or algebraic) invariants that hold at each location of a given affine program (i.e., a program having only non-deterministic (as opposed to conditional) branching and all of whose assignments are given by affine expressions). Our main tool is an algebraic result of independent interest: given a finite set of rational square matrices of the same dimension, we show how to compute the Zariski closure of the semigroup that they generate.
RDMAvisor: Toward Deploying Scalable and Simple RDMA as a Service in Datacenters
Venue: arXiv cs.DC 2018
Year: 2018

RDMA is increasingly adopted by cloud computing platforms to provide low CPU overhead, low latency, high throughput network services. On the other hand, however, it is still challenging for developers to realize fast deployment of RDMA-aware applications in the datacenter, since the performance is highly related to many lowlevel details of RDMA operations. To address this problem, we present a simple and scalable RDMA as Service (RaaS) to mitigate the impact of RDMA operational details. RaaS provides careful message buffer management to improve CPU/memory utilization and improve the scalability of RDMA operations. These optimized designs lead to simple and flexible programming model for common and knowledgeable users. We have implemented a prototype of RaaS, named RDMAvisor, and evaluated its performance on a cluster with a large number of connections. Our experiment results demonstrate that RDMAvisor achieves high throughput for thousand of connections and maintains low CPU and memory overhead through adaptive RDMA transport selection.
Storage-Latency Trade-off in Cache-Aided Fog Radio Access Networks
Venue: arXiv cs.IT 2018
Year: 2018

A fog radio access network (F-RAN) is studied, in which $K_T$ edge nodes (ENs) connected to a cloud server via orthogonal fronthaul links, serve $K_R$ users through a wireless Gaussian interference channel. Both the ENs and the users have finite-capacity cache memories, which are filled before the user demands are revealed. While a centralized placement phase is used for the ENs, which model static base stations, a decentralized placement is leveraged for the mobile users. An achievable transmission scheme is presented, which employs a combination of interference alignment, zero-forcing and interference cancellation techniques in the delivery phase, and the \textit{normalized delivery time} (NDT), which captures the worst-case latency, is analyzed.
A Distance Between Channels: the average error of mismatched channels
Venue: arXiv cs.IT 2018
Year: 2018

Two channels are equivalent if their maximum likelihood (ML) decoders coincide for every code. We show that this equivalence relation partitions the space of channels into a generalized hyperplane arrangement. With this, we define a coding distance between channels in terms of their ML-decoders which is meaningful from the decoding point of view, in the sense that the closer two channels are, the larger is the probability of them sharing the same ML-decoder. We give explicit formulas for these probabilities.
Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials
Venue: arXiv cs.CC 2018
Year: 2018

The theory of kernelization can be used to rigorously analyze data reduction for graph coloring problems. Here, the aim is to reduce a q-Coloring input to an equivalent but smaller input whose size is provably bounded in terms of structural properties, such as the size of a minimum vertex cover. In this paper we settle two open problems about data reduction for q-Coloring. First, we obtain a kernel of bitsize $O(k^{q-1}\log{k})$ for q-Coloring parameterized by Vertex Cover, for any q >= 3. This size bound is optimal up to $k^{o(1)}$ factors assuming NP is not a subset of coNP/poly, and improves on the previous-best kernel of size $O(k^q)$. We generalize this result for deciding q-colorability of a graph G, to deciding the existence of a homomorphism from G to an arbitrary fixed graph H. Furthermore, we can replace the parameter vertex cover by the less restrictive parameter twin-cover. We prove that H-Coloring parameterized by Twin-Cover has a kernel of size $O(k^{Δ(H)}\log k)$. Our second result shows that 3-Coloring does not admit non-trivial sparsification: assuming NP is not a subset of coNP/poly, the parameterization by the number of vertices n admits no (generalized) kernel of size $O(n^{2-e})$ for any e > 0. Previously, such a lower bound was only known for coloring with q >= 4 colors.
A Log-Euclidean and Total Variation based Variational Framework for Computational Sonography
Venue: arXiv cs.CV 2018
Year: 2018

We propose a spatial compounding technique and variational framework to improve 3D ultrasound image quality by compositing multiple ultrasound volumes acquired from different probe orientations. In the composite volume, instead of intensity values, we estimate a tensor at every voxel. The resultant tensor image encapsulates the directional information of the underlying imaging data and can be used to generate ultrasound volumes from arbitrary, potentially unseen, probe positions. Extending the work of Hennersperger et al., we introduce a log-Euclidean framework to ensure that the tensors are positive-definite, eventually ensuring non-negative images. Additionally, we regularise the underpinning ill-posed variational problem while preserving edge information by relying on a total variation penalisation of the tensor field in the log domain. We present results on in vivo human data to show the efficacy of the approach.
Non-Projective Dependency Parsing via Latent Heads Representation (LHR)
Venue: arXiv cs.CL 2018
Year: 2018

In this paper, we introduce a novel approach based on a bidirectional recurrent autoencoder to perform globally optimized non-projective dependency parsing via semi-supervised learning. The syntactic analysis is completed at the end of the neural process that generates a Latent Heads Representation (LHR), without any algorithmic constraint and with a linear complexity. The resulting "latent syntactic structure" can be used directly in other semantic tasks. The LHR is transformed into the usual dependency tree computing a simple vectors similarity. We believe that our model has the potential to compete with much more complex state-of-the-art parsing architectures.
Generalizing Multiple Access Wiretap and Wiretap II Channel Models: Achievable Rates and Cost of Strong Secrecy
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, new two-user multiple access wiretap channel models are studied. First, the multiple access wiretap channel II with a discrete memoryless main channel, under three different wiretapping scenarios, is introduced. The wiretapper, as in the classical wiretap channel II model, chooses a fixed-length subset of the channel uses on which she obtains noise-free observations of one of the codewords, a superposition of the two codewords, or each of the two codewords. These thus extend the recently examined wiretap channel II with a noisy main channel to a multiple access setting with a variety of attack models for the wiretapper. Next, a new multiple access wiretap channel model, which further generalizes the multiple access wiretap channel II under the third wiretapping scenario, i.e., that which features the strongest adversarial model, is proposed. In this model, the wiretapper, besides choosing a subset of the channel uses to noiselessly observe the transmitted codeword symbols of both users, observes the remainder of the two codewords through a discrete memoryless multiple access channel. Achievable strong secrecy rate regions for all the proposed models are derived. Achievability is established by solving dual multi-terminal secret key agreement problems in the source model, and converting the solution to the original channel models using probability distribution approximation arguments. The derived achievable rate regions quantify the secrecy cost due to the additional capabilities of the wiretapper with respect to the previous multiple access wiretap models.
An Occluded Stacked Hourglass Approach to Facial Landmark Localization and Occlusion Estimation
Venue: arXiv cs.CV 2018
Year: 2018

A key step to driver safety is to observe the driver's activities with the face being a key step in this process to extracting information such as head pose, blink rate, yawns, talking to passenger which can then help derive higher level information such as distraction, drowsiness, intent, and where they are looking. In the context of driving safety, it is important for the system perform robust estimation under harsh lighting and occlusion but also be able to detect when the occlusion occurs so that information predicted from occluded parts of the face can be taken into account properly. This paper introduces the Occluded Stacked Hourglass, based on the work of original Stacked Hourglass network for body pose joint estimation, which is retrained to process a detected face window and output 68 occlusion heat maps, each corresponding to a facial landmark. Landmark location, occlusion levels and a refined face detection score, to reject false positives, are extracted from these heat maps. Using the facial landmark locations, features such as head pose and eye/mouth openness can be extracted to derive driver attention and activity. The system is evaluated for face detection, head pose, and occlusion estimation on various datasets in the wild, both quantitatively and qualitatively, and shows state-of-the-art results.
Face Detection Using Improved Faster RCNN
Venue: arXiv cs.CV 2018
Year: 2018

Faster RCNN has achieved great success for generic object detection including PASCAL object detection and MS COCO object detection. In this report, we propose a detailed designed Faster RCNN method named FDNet1.0 for face detection. Several techniques were employed including multi-scale training, multi-scale testing, light-designed RCNN, some tricks for inference and a vote-based ensemble method. Our method achieves two 1th places and one 2nd place in three tasks over WIDER FACE validation dataset (easy set, medium set, hard set).