OpenRaiser/Intern-Atlas huggingface dataset:
Botnet Campaign Detection on Twitter
Venue: arXiv cs.SI 2018
Year: 2018

This is an approach to detecting a subset of bots on Twitter, that at best is under-researched. This approach will be generic enough to be adaptable to most, if not all social networks. The subset of bots this focuses on are those that can evade most, if not all current detection methods. This is simply because they have little to no information associated with them that can be analyzed to make a determination. Although any account on any social media site inherently has information associated with it, it is very easy to blend in with the majority of users who are simply "lurkers" - those who only consume content, but do not contribute. How can you determine if an account is a bot if they don't do anything? By the time they act, it will be too late to detect. The only solution would be a real time, or near real-time, detection algorithm.
Submodular Maximization with Matroid and Packing Constraints in Parallel
Venue: arXiv cs.DS 2018
Year: 2018

We consider the problem of maximizing the multilinear extension of a submodular function subject a single matroid constraint or multiple packing constraints with a small number of adaptive rounds of evaluation queries. We obtain the first algorithms with low adaptivity for submodular maximization with a matroid constraint. Our algorithms achieve a $1-1/e-ε$ approximation for monotone functions and a $1/e-ε$ approximation for non-monotone functions, which nearly matches the best guarantees known in the fully adaptive setting. The number of rounds of adaptivity is $O(\log^2{n}/ε^3)$, which is an exponential speedup over the existing algorithms. We obtain the first parallel algorithm for non-monotone submodular maximization subject to packing constraints. Our algorithm achieves a $1/e-ε$ approximation using $O(\log(n/ε) \log(1/ε) \log(n+m)/ ε^2)$ parallel rounds, which is again an exponential speedup in parallel time over the existing algorithms. For monotone functions, we obtain a $1-1/e-ε$ approximation in $O(\log(n/ε)\log(m)/ε^2)$ parallel rounds. The number of parallel rounds of our algorithm matches that of the state of the art algorithm for solving packing LPs with a linear objective. Our results apply more generally to the problem of maximizing a diminishing returns submodular (DR-submodular) function.
Recognition and Drawing of Stick Graphs
Venue: arXiv cs.CG 2018
Year: 2018

A \emph{Stick graph} is an intersection graph of axis-aligned segments such that the left end-points of the horizontal segments and the bottom end-points of the vertical segments lie on a `ground line,' a line with slope $-1$. It is an open question to decide in polynomial time whether a given bipartite graph $G$ with bipartition $A\cup B$ has a Stick representation where the vertices in $A$ and $B$ correspond to horizontal and vertical segments, respectively. We prove that $G$ has a Stick representation if and only if there are orderings of $A$ and $B$ such that $G$'s bipartite adjacency matrix with rows $A$ and columns $B$ excludes three small `forbidden' submatrices. This is similar to characterizations for other classes of bipartite intersection graphs. We present an algorithm to test whether given orderings of $A$ and $B$ permit a Stick representation respecting those orderings, and to find such a representation if it exists. The algorithm runs in time linear in the size of the adjacency matrix. For the case when only the ordering of $A$ is given, we present an $O(|A|^3|B|^3)$-time algorithm. When neither ordering is given, we present some partial results about graphs that are, or are not, Stick representable.
The Impact of Preprocessing on Deep Representations for Iris Recognition on Unconstrained Environments
Venue: arXiv cs.CV 2018
Year: 2018

The use of iris as a biometric trait is widely used because of its high level of distinction and uniqueness. Nowadays, one of the major research challenges relies on the recognition of iris images obtained in visible spectrum under unconstrained environments. In this scenario, the acquired iris are affected by capture distance, rotation, blur, motion blur, low contrast and specular reflection, creating noises that disturb the iris recognition systems. Besides delineating the iris region, usually preprocessing techniques such as normalization and segmentation of noisy iris images are employed to minimize these problems. But these techniques inevitably run into some errors. In this context, we propose the use of deep representations, more specifically, architectures based on VGG and ResNet-50 networks, for dealing with the images using (and not) iris segmentation and normalization. We use transfer learning from the face domain and also propose a specific data augmentation technique for iris images. Our results show that the approach using non-normalized and only circle-delimited iris images reaches a new state of the art in the official protocol of the NICE.II competition, a subset of the UBIRIS database, one of the most challenging databases on unconstrained environments, reporting an average Equal Error Rate (EER) of 13.98% which represents an absolute reduction of about 5%.
Timelines for In-Code Discovery of Zero-Day Vulnerabilities and Supply-Chain Attacks
Venue: arXiv cs.CR 2018
Year: 2018

Zero-day vulnerabilities can be accidentally or maliciously placed in code and can remain in place for years. In this study, we address an aspect of their longevity by considering the likelihood that they will be discovered in the code across versions. We approximate well-disguised vulnerabilities as only being discoverable if the relevant lines of code are explicitly examined, and obvious vulnerabilities as being discoverable if any part of the relevant file is examined. We analyze the version-to-version changes in three types of open source software (Mozilla Firefox, GNU/Linus, and glibc) to understand the rate at which the various pieces of code are amended and find that much of the revision behavior can be captured with a simple intuitive model. We use that model and the data from over a billion unique lines of code in 87 different versions of software to specify the bounds for in-code discoverability of vulnerabilities - from expertly hidden to obviously observable.
IOTA Feasibility and Perspectives for Enabling Vehicular Applications
Venue: arXiv cs.CR 2018
Year: 2018

The emergence of distributed ledger technologies in the vehicular applications' arena is decisively contributing to their improvement and shaping of the public opinion about their future. The Tangle is a technology at its infancy, but showing enormous potential to become a key solution by addressing several of the blockchain's limitations. This paper focuses the use of the Tangle to improve the security of both in-vehicle and off-vehicle functions in vehicular applications. To this end, key operational performance parameters are identified, evaluated and discussed with emphasis on their limitations and potential impact in future vehicular applications.
Rational Neural Networks for Approximating Jump Discontinuities of Graph Convolution Operator
Venue: arXiv cs.LG 2018
Year: 2018

For node level graph encoding, a recent important state-of-art method is the graph convolutional networks (GCN), which nicely integrate local vertex features and graph topology in the spectral domain. However, current studies suffer from several drawbacks: (1) graph CNNs relies on Chebyshev polynomial approximation which results in oscillatory approximation at jump discontinuities; (2) Increasing the order of Chebyshev polynomial can reduce the oscillations issue, but also incurs unaffordable computational cost; (3) Chebyshev polynomials require degree $Ω$(poly(1/$ε$)) to approximate a jump signal such as $|x|$, while rational function only needs $\mathcal{O}$(poly log(1/$ε$))\cite{liang2016deep,telgarsky2017neural}. However, it's non-trivial to apply rational approximation without increasing computational complexity due to the denominator. In this paper, the superiority of rational approximation is exploited for graph signal recovering. RatioanlNet is proposed to integrate rational function and neural networks. We show that rational function of eigenvalues can be rewritten as a function of graph Laplacian, which can avoid multiplication by the eigenvector matrix. Focusing on the analysis of approximation on graph convolution operation, a graph signal regression task is formulated. Under graph signal regression task, its time complexity can be significantly reduced by graph Fourier transform. To overcome the local minimum problem of neural networks model, a relaxed Remez algorithm is utilized to initialize the weight parameters. Convergence rate of RatioanlNet and polynomial based methods on jump signal is analyzed for a theoretical guarantee. The extensive experimental results demonstrated that our approach could effectively characterize the jump discontinuities, outperforming competing methods by a substantial margin on both synthetic and real-world graphs.
Differential and integral invariants under Mobius transformation
Venue: arXiv cs.GR 2018
Year: 2018

One of the most challenging problems in the domain of 2-D image or 3-D shape is to handle the non-rigid deformation. From the perspective of transformation groups, the conformal transformation is a key part of the diffeomorphism. According to the Liouville Theorem, an important part of the conformal transformation is the Mobius transformation, so we focus on Mobius transformation and propose two differential expressions that are invariable under 2-D and 3-D Mobius transformation respectively. Next, we analyze the absoluteness and relativity of invariance on them and their components. After that, we propose integral invariants under Mobius transformation based on the two differential expressions. Finally, we propose a conjecture about the structure of differential invariants under conformal transformation according to our observation on the composition of the above two differential invariants.
Story Ending Generation with Incremental Encoding and Commonsense Knowledge
Venue: arXiv cs.CL 2018
Year: 2018

Generating a reasonable ending for a given story context, i.e., story ending generation, is a strong indication of story comprehension. This task requires not only to understand the context clues which play an important role in planning the plot but also to handle implicit knowledge to make a reasonable, coherent story. In this paper, we devise a novel model for story ending generation. The model adopts an incremental encoding scheme to represent context clues which are spanning in the story context. In addition, commonsense knowledge is applied through multi-source attention to facilitate story comprehension, and thus to help generate coherent and reasonable endings. Through building context clues and using implicit knowledge, the model is able to produce reasonable story endings. context clues implied in the post and make the inference based on it. Automatic and manual evaluation shows that our model can generate more reasonable story endings than state-of-the-art baselines.
ExIt-OOS: Towards Learning from Planning in Imperfect Information Games
Venue: arXiv cs.AI 2018
Year: 2018

The current state of the art in playing many important perfect information games, including Chess and Go, combines planning and deep reinforcement learning with self-play. We extend this approach to imperfect information games and present ExIt-OOS, a novel approach to playing imperfect information games within the Expert Iteration framework and inspired by AlphaZero. We use Online Outcome Sampling, an online search algorithm for imperfect information games in place of MCTS. While training online, our neural strategy is used to improve the accuracy of playouts in OOS, allowing a learning and planning feedback loop for imperfect information games.
Baidu Apollo Auto-Calibration System - An Industry-Level Data-Driven and Learning based Vehicle Longitude Dynamic Calibrating Algorithm
Venue: arXiv cs.RO 2018
Year: 2018

For any autonomous driving vehicle, control module determines its road performance and safety, i.e. its precision and stability should stay within a carefully-designed range. Nonetheless, control algorithms require vehicle dynamics (such as longitudinal dynamics) as inputs, which, unfortunately, are obscure to calibrate in real time. As a result, to achieve reasonable performance, most, if not all, research-oriented autonomous vehicles do manual calibrations in a one-by-one fashion. Since manual calibration is not sustainable once entering into mass production stage for industrial purposes, we here introduce a machine-learning based auto-calibration system for autonomous driving vehicles. In this paper, we will show how we build a data-driven longitudinal calibration procedure using machine learning techniques. We first generated offline calibration tables from human driving data. The offline table serves as an initial guess for later uses and it only needs twenty-minutes data collection and process. We then used an online-learning algorithm to appropriately update the initial table (the offline table) based on real-time performance analysis. This longitudinal auto-calibration system has been deployed to more than one hundred Baidu Apollo self-driving vehicles (including hybrid family vehicles and electronic delivery-only vehicles) since April 2018. By August 27, 2018, it had been tested for more than two thousands hours, ten thousands kilometers (6,213 miles) and yet proven to be effective.
Dense Scene Flow from Stereo Disparity and Optical Flow
Venue: arXiv cs.CV 2018
Year: 2018

Scene flow describes 3D motion in a 3D scene. It can either be modeled as a single task, or it can be reconstructed from the auxiliary tasks of stereo depth and optical flow estimation. While the second method can achieve real-time performance by using real-time auxiliary methods, it will typically produce non-dense results. In this representation of a basic combination approach for scene flow estimation, we will tackle the problem of non-density by interpolation.
Maximum Eccentric Connectivity Index for Graphs with Given Diameter
Venue: arXiv cs.DM 2018
Year: 2018

The eccentricity of a vertex $v$ in a graph $G$ is the maximum distance between $v$ and any other vertex of $G$. The diameter of a graph $G$ is the maximum eccentricity of a vertex in $G$. The eccentric connectivity index of a connected graph is the sum over all vertices of the product between eccentricity and degree. Given two integers $n$ and $D$ with $D\leq n-1$, we characterize those graphs which have the largest eccentric connectivity index among all connected graphs of order $n$ and diameter $D$. As a corollary, we also characterize those graphs which have the largest eccentric connectivity index among all connected graphs of a given order $n$.
Centroid estimation based on symmetric KL divergence for Multinomial text classification problem
Venue: arXiv cs.IR 2018
Year: 2018

We define a new method to estimate centroid for text classification based on the symmetric KL-divergence between the distribution of words in training documents and their class centroids. Experiments on several standard data sets indicate that the new method achieves substantial improvements over the traditional classifiers.
Fully Dynamic MIS in Uniformly Sparse Graphs
Venue: arXiv cs.DS 2018
Year: 2018

We consider the problem of maintaining a maximal independent set (MIS) in a dynamic graph subject to edge insertions and deletions. Recently, Assadi, Onak, Schieber and Solomon (STOC 2018) showed that an MIS can be maintained in sublinear (in the dynamically changing number of edges) amortized update time. In this paper we significantly improve the update time for uniformly sparse graphs. Specifically, for graphs with arboricity $α$, the amortized update time of our algorithm is $O(α^2 \cdot \log^2 n)$, where $n$ is the number of vertices. For low arboricity graphs, which include, for example, minor-free graphs as well as some classes of `real world' graphs, our update time is polylogarithmic. Our update time improves the result of Assadi et al. for all graphs with arboricity bounded by $m^{3/8 - ε}$, for any constant $ε> 0$. This covers much of the range of possible values for arboricity, as the arboricity of a general graph cannot exceed $m^{1/2}$.
Asymptotically Optimal Codes Correcting Fixed-Length Duplication Errors in DNA Storage Systems
Venue: arXiv cs.IT 2018
Year: 2018

A (tandem) duplication of length $ k $ is an insertion of an exact copy of a substring of length $ k $ next to its original position. This and related types of impairments are of relevance in modeling communication in the presence of synchronization errors, as well as in several information storage applications. We demonstrate that Levenshtein's construction of binary codes correcting insertions of zeros is, with minor modifications, applicable also to channels with arbitrary alphabets and with duplication errors of arbitrary (but fixed) length $ k $. Furthermore, we derive bounds on the cardinality of optimal $ q $-ary codes correcting up to $ t $ duplications of length $ k $, and establish the following corollaries in the asymptotic regime of growing block-length: 1.) the presented family of codes is optimal for every $ q, t, k $, in the sense of the asymptotic scaling of code redundancy; 2.) the upper bound, when specialized to $ q = 2 $, $ k = 1 $, improves upon Levenshtein's bound for every $ t \geq 3 $; 3.) the bounds coincide for $ t = 1 $, thus yielding the exact asymptotic behavior of the size of optimal single-duplication-correcting codes.
Algorithms and Bounds for Drawing Directed Graphs
Venue: arXiv cs.DS 2018
Year: 2018

In this paper we present a new approach to visualize directed graphs and their hierarchies that completely departs from the classical four-phase framework of Sugiyama and computes readable hierarchical visualizations that contain the complete reachability information of a graph. Additionally, our approach has the advantage that only the necessary edges are drawn in the drawing, thus reducing the visual complexity of the resulting drawing. Furthermore, most problems involved in our framework require only polynomial time. Our framework offers a suite of solutions depending upon the requirements, and it consists of only two steps: (a) the cycle removal step (if the graph contains cycles) and (b) the channel decomposition and hierarchical drawing step. Our framework does not introduce any dummy vertices and it keeps the vertices of a channel vertically aligned. The time complexity of the main drawing algorithms of our framework is $O(kn)$, where $k$ is the number of channels, typically much smaller than $n$ (the number of vertices).
Types of Fireballs (Extended Version)
Venue: arXiv cs.LO 2018
Year: 2018

The good properties of Plotkin's call-by-value lambda-calculus crucially rely on the restriction to weak evaluation and closed terms. Open call-by-value is the more general setting where evaluation is weak but terms may be open. Such an extension is delicate, and the literature contains a number of proposals. Recently, Accattoli and Guerrieri provided detailed operational and implementative studies of these proposals, showing that they are equivalent from the point of view of termination, and also at the level of time cost models. This paper explores the denotational semantics of open call-by-value, adapting de Carvalho's analysis of call-by-name via multi types (aka non-idempotent intersection types). Our type system characterises normalisation and thus provides an adequate relational semantics. Moreover, type derivations carry quantitative information about the cost of evaluation: their size bounds the number of evaluation steps and the size of the normal form, and we also characterise derivations giving exact bounds. The study crucially relies on a new, refined presentation of the fireball calculus, the simplest proposal for open call-by-value, that is more apt to denotational investigations.
Symbolic regression based genetic approximations of the Colebrook equation for flow friction
Venue: arXiv cs.CE 2018
Year: 2018

Widely used in hydraulics, the Colebrook equation for flow friction relates implicitly to the input parameters; the Reynolds number, and the relative roughness of inner pipe surface, with the output unknown parameter; the flow friction factor. In this paper, a few explicit approximations to the Colebrook equation are generated using the ability of artificial intelligence to make inner patterns to connect input and output parameters in explicit way not knowing their nature or the physical law that connects them, but only knowing raw numbers. The fact that the used genetic programming tool does not know the structure of the Colebrook equation which is based on computationally expensive logarithmic law, is used to obtain better structure of the approximations which is less demanding for calculation but also enough accurate. All generated approximations are with low computational cost because they contain a limited number of logarithmic forms used although for normalization of input parameters or for acceleration, but they are also sufficiently accurate. The relative error regarding the friction factor in best case is up to 0.13% with only two logarithmic forms used. As the second logarithm can be accurately approximated by the Pade approximation, practically the same error is obtained also using only one logarithm.
iCAN: Instance-Centric Attention Network for Human-Object Interaction Detection
Venue: arXiv cs.CV 2018
Year: 2018

Recent years have witnessed rapid progress in detecting and recognizing individual object instances. To understand the situation in a scene, however, computers need to recognize how humans interact with surrounding objects. In this paper, we tackle the challenging task of detecting human-object interactions (HOI). Our core idea is that the appearance of a person or an object instance contains informative cues on which relevant parts of an image to attend to for facilitating interaction prediction. To exploit these cues, we propose an instance-centric attention module that learns to dynamically highlight regions in an image conditioned on the appearance of each instance. Such an attention-based network allows us to selectively aggregate features relevant for recognizing HOIs. We validate the efficacy of the proposed network on the Verb in COCO and HICO-DET datasets and show that our approach compares favorably with the state-of-the-arts.
A Heuristic Approach towards Drawings of Graphs with High Crossing Resolution
Venue: arXiv cs.DS 2018
Year: 2018

The crossing resolution of a non-planar drawing of a graph is the value of the minimum angle formed by any pair of crossing edges. Recent experiments have shown that the larger the crossing resolution is, the easier it is to read and interpret a drawing of a graph. However, maximizing the crossing resolution turns out to be an NP-hard problem in general and only heuristic algorithms are known that are mainly based on appropriately adjusting force-directed algorithms. In this paper, we propose a new heuristic algorithm for the crossing resolution maximization problem and we experimentally compare it against the known approaches from the literature. Our experimental evaluation indicates that the new heuristic produces drawings with better crossing resolution, but this comes at the cost of slightly higher aspect ratio, especially when the input graph is large.