OpenRaiser/Intern-Atlas huggingface dataset:
Strong Subgraph Connectivity of Digraphs: A Survey
Venue: arXiv cs.DM 2018
Year: 2018

In this survey we overview known results on the strong subgraph $k$-connectivity and strong subgraph $k$-arc-connectivity of digraphs. After an introductory section, the paper is divided into four sections: basic results, algorithms and complexity, sharp bounds for strong subgraph $k$-(arc-)connectivity, minimally strong subgraph $(k, \ell)$-(arc-) connected digraphs. This survey contains several conjectures and open problems for further study.
Sample size estimation for power and accuracy in the experimental comparison of algorithms
Venue: arXiv cs.NE 2018
Year: 2018

Experimental comparisons of performance represent an important aspect of research on optimization algorithms. In this work we present a methodology for defining the required sample sizes for designing experiments with desired statistical properties for the comparison of two methods on a given problem class. The proposed approach allows the experimenter to define desired levels of accuracy for estimates of mean performance differences on individual problem instances, as well as the desired statistical power for comparing mean performances over a problem class of interest. The method calculates the required number of problem instances, and runs the algorithms on each test instance so that the accuracy of the estimated differences in performance is controlled at the predefined level. Two examples illustrate the application of the proposed method, and its ability to achieve the desired statistical properties with a methodologically sound definition of the relevant sample sizes.
An Iterative Boundary Random Walks Algorithm for Interactive Image Segmentation
Venue: arXiv cs.CV 2018
Year: 2018

The interactive image segmentation algorithm can provide an intelligent ways to understand the intention of user input. Many interactive methods have the problem of that ask for large number of user input. To efficient produce intuitive segmentation under limited user input is important for industrial application. In this paper, we reveal a positive feedback system on image segmentation to show the pixels of self-learning. Two approaches, iterative random walks and boundary random walks, are proposed for segmentation potential, which is the key step in feedback system. Experiment results on image segmentation indicates that proposed algorithms can obtain more efficient input to random walks. And higher segmentation performance can be obtained by applying the iterative boundary random walks algorithm.
Sentimental Content Analysis and Knowledge Extraction from News Articles
Venue: arXiv cs.CL 2018
Year: 2018

In web era, since technology has revolutionized mankind life, plenty of data and information are published on the Internet each day. For instance, news agencies publish news on their websites all over the world. These raw data could be an important resource for knowledge extraction. These shared data contain emotions (i.e., positive, neutral or negative) toward various topics; therefore, sentimental content extraction could be a beneficial task in many aspects. Extracting the sentiment of news illustrates highly valuable information about the events over a period of time, the viewpoint of a media or news agency to these events. In this paper an attempt is made to propose an approach for news analysis and extracting useful knowledge from them. Firstly, we attempt to extract a noise robust sentiment of news documents; therefore, the news associated to six countries: United State, United Kingdom, Germany, Canada, France and Australia in 5 different news categories: Politics, Sports, Business, Entertainment and Technology are downloaded. In this paper we compare the condition of different countries in each 5 news topics based on the extracted sentiments and emotional contents in news documents. Moreover, we propose an approach to reduce the bulky news data to extract the hottest topics and news titles as a knowledge. Eventually, we generate a word model to map each word to a fixed-size vector by Word2Vec in order to understand the relations between words in our collected news database.
A Constrained Shortest Path Scheme for Virtual Network Service Management
Venue: arXiv cs.PF 2018
Year: 2018

Virtual network services that span multiple data centers are important to support emerging data-intensive applications in fields such as bioinformatics and retail analytics. Successful virtual network service composition and maintenance requires flexible and scalable 'constrained shortest path management' both in the management plane for virtual network embedding (VNE) or network function virtualization service chaining (NFV-SC), as well as in the data plane for traffic engineering (TE). In this paper, we show analytically and empirically that leveraging constrained shortest paths within recent VNE, NFV-SC and TE algorithms can lead to network utilization gains (of up to 50%) and higher energy efficiency. The management of complex VNE, NFV-SC and TE algorithms can be, however, intractable for large scale substrate networks due to the NP-hardness of the constrained shortest path problem. To address such scalability challenges, we propose a novel, exact constrained shortest path algorithm viz., 'Neighborhoods Method' (NM). Our NM uses novel search space reduction techniques and has a theoretical quadratic speed-up making it practically faster (by an order of magnitude) than recent branch-and-bound exhaustive search solutions. Finally, we detail our NM-based SDN controller implementation in a real-world testbed to further validate practical NM benefits for virtual network services.
Optimal conditions for connectedness of discretized sets
Venue: arXiv cs.DM 2018
Year: 2018

Constructing a discretization of a given set is a major problem in various theoretical and applied disciplines. An offset discretization of a set $X$ is obtained by taking the integer points inside a closed neighborhood of $X$ of a certain radius. In this note we determine a minimum threshold for the offset radius, beyond which the discretization of a disconnected set is always connected. The results hold for a broad class of disconnected and unbounded subsets of $R^n$, and generalize several previous results. Algorithmic aspects and possible applications are briefly discussed.
Hardware realization of residue number system algorithms by Boolean functions minimization
Venue: arXiv cs.AR 2018
Year: 2018

Residue number systems (RNS) represent numbers by their remainders modulo a set of relatively prime numbers. This paper pro- poses an efficient hardware implementation of modular multiplication and of the modulo function (X(mod P)), based on Boolean minimiza- tion. We report experiments showing a performance advantage up to 30 times for our approach vs. the results obtained by state-of-art industrial tools.
Energy Efficiency Maximization for C-RANs: Discrete Monotonic Optimization, Penalty, and l0-Approximation Methods
Venue: arXiv cs.IT 2018
Year: 2018

We study downlink of multiantenna cloud radio access networks (C-RANs) with finite-capacity fronthaul links. The aim is to propose joint designs of beamforming and remote radio head (RRH)-user association, subject to constraints on users' quality-of-service, limited capacity of fronthaul links and transmit power, to maximize the system energy efficiency. To cope with the limited-capacity fronthaul we consider the problem of RRH-user association to select a subset of users that can be served by each RRH. Moreover, different to the conventional power consumption models, we take into account the dependence of baseband signal processing power on the data rate, as well as the dynamics of the efficiency of power amplifiers. The considered problem leads to a mixed binary integer program (MBIP) which is difficult to solve. Our first contribution is to derive a globally optimal solution for the considered problem by customizing a discrete branch-reduce-and-bound (DBRB) approach. Since the global optimization method requires a high computational effort, we further propose two suboptimal solutions able to achieve the near optimal performance but with much reduced complexity. To this end, we transform the design problem into continuous (but inherently nonconvex) programs by two approaches: penalty and \ell_{0}-approximation methods. These resulting continuous nonconvex problems are then solved by the successive convex approximation framework. Numerical results are provided to evaluate the effectiveness of the proposed approaches.
Building a Kannada POS Tagger Using Machine Learning and Neural Network Models
Venue: arXiv cs.CL 2018
Year: 2018

POS Tagging serves as a preliminary task for many NLP applications. Kannada is a relatively poor Indian language with very limited number of quality NLP tools available for use. An accurate and reliable POS Tagger is essential for many NLP tasks like shallow parsing, dependency parsing, sentiment analysis, named entity recognition. We present a statistical POS tagger for Kannada using different machine learning and neural network models. Our Kannada POS tagger outperforms the state-of-the-art Kannada POS tagger by 6%. Our contribution in this paper is three folds - building a generic POS Tagger, comparing the performances of different modeling techniques, exploring the use of character and word embeddings together for Kannada POS Tagging.
Overcoming Missing and Incomplete Modalities with Generative Adversarial Networks for Building Footprint Segmentation
Venue: arXiv cs.CV 2018
Year: 2018

The integration of information acquired with different modalities, spatial resolution and spectral bands has shown to improve predictive accuracies. Data fusion is therefore one of the key challenges in remote sensing. Most prior work focusing on multi-modal fusion, assumes that modalities are always available during inference. This assumption limits the applications of multi-modal models since in practice the data collection process is likely to generate data with missing, incomplete or corrupted modalities. In this paper, we show that Generative Adversarial Networks can be effectively used to overcome the problems that arise when modalities are missing or incomplete. Focusing on semantic segmentation of building footprints with missing modalities, our approach achieves an improvement of about 2% on the Intersection over Union (IoU) against the same network that relies only on the available modality.
Who Falls for Online Political Manipulation?
Venue: arXiv cs.SI 2018
Year: 2018

Social media, once hailed as a vehicle for democratization and the promotion of positive social change across the globe, are under attack for becoming a tool of political manipulation and spread of disinformation. A case in point is the alleged use of trolls by Russia to spread malicious content in Western elections. This paper examines the Russian interference campaign in the 2016 US presidential election on Twitter. Our aim is twofold: first, we test whether predicting users who spread trolls' content is feasible in order to gain insight on how to contain their influence in the future; second, we identify features that are most predictive of users who either intentionally or unintentionally play a vital role in spreading this malicious content. We collected a dataset with over 43 million elections-related posts shared on Twitter between September 16 and November 9, 2016, by about 5.7 million users. This dataset includes accounts associated with the Russian trolls identified by the US Congress. Proposed models are able to very accurately identify users who spread the trolls' content (average AUC score of 96%, using 10-fold validation). We show that political ideology, bot likelihood scores, and some activity-related account meta data are the most predictive features of whether a user spreads trolls' content or not.
Effective Caching for the Secure Content Distribution in Information-Centric Networking
Venue: arXiv cs.CR 2018
Year: 2018

The secure distribution of protected content requires consumer authentication and involves the conventional method of end-to-end encryption. However, in information-centric networking (ICN) the end-to-end encryption makes the content caching ineffective since encrypted content stored in a cache is useless for any consumer except those who know the encryption key. For effective caching of encrypted content in ICN, we propose a novel scheme, called the Secure Distribution of Protected Content (SDPC). SDPC ensures that only authenticated consumers can access the content. The SDPC is a lightweight authentication and key distribution protocol; it allows consumer nodes to verify the originality of the published article by using a symmetric key encryption. The security of the SDPC was proved with BAN logic and Scyther tool verification.
On-Chip Optical Convolutional Neural Networks
Venue: arXiv cs.ET 2018
Year: 2018

Convolutional Neural Networks (CNNs) are a class of Artificial Neural Networks(ANNs) that employ the method of convolving input images with filter-kernels for object recognition and classification purposes. In this paper, we propose a photonics circuit architecture which could consume a fraction of energy per inference compared with state of the art electronics.
The Elephant in the Room
Venue: arXiv cs.CV 2018
Year: 2018

We showcase a family of common failures of state-of-the art object detectors. These are obtained by replacing image sub-regions by another sub-image that contains a trained object. We call this "object transplanting". Modifying an image in this manner is shown to have a non-local impact on object detection. Slight changes in object position can affect its identity according to an object detector as well as that of other objects in the image. We provide some analysis and suggest possible reasons for the reported phenomena.
Metrics for Signal Temporal Logic Formulae
Venue: arXiv cs.LO 2018
Year: 2018

Signal Temporal Logic (STL) is a formal language for describing a broad range of real-valued, temporal properties in cyber-physical systems. While there has been extensive research on verification and control synthesis from STL requirements, there is no formal framework for comparing two STL formulae. In this paper, we show that under mild assumptions, STL formulae admit a metric space. We propose two metrics over this space based on i) the Pompeiu-Hausdorff distance and ii) the symmetric difference measure, and present algorithms to compute them. Alongside illustrative examples, we present applications of these metrics for two fundamental problems: a) design quality measures: to compare all the temporal behaviors of a designed system, such as a synthetic genetic circuit, with the "desired" specification, and b) loss functions: to quantify errors in Temporal Logic Inference (TLI) as a first step to establish formal performance guarantees of TLI algorithms.
Computational Complexity of Observing Evolution in Artificial-Life Forms
Venue: arXiv cs.NE 2018
Year: 2018

Observations are an essential component of the simulation based studies on artificial-evolutionary systems (AES) by which entities are identified and their behavior is observed to uncover higher-level "emergent" phenomena. Because of the heterogeneity of AES models and implicit nature of observations, precise characterization of the observation process, independent of the underlying micro-level reaction semantics of the model, is a difficult problem. Building upon the multiset based algebraic framework to characterize state-space trajectory of AES model simulations, we estimate bounds on computational resource requirements of the process of automatically discovering life-like evolutionary behavior in AES models during simulations. For illustration, we consider the case of Langton's Cellular Automata model and characterize the worst case computational complexity bounds for identifying entity and population level reproduction.
Distinctiveness, complexity, and repeatability of online signature templates
Venue: arXiv cs.CV 2018
Year: 2018

This paper proposes three measures to quantify the characteristics of online signature templates in terms of distinctiveness, complexity and repeatability. A distinctiveness measure of a signature template is computed from a set of enrolled signature samples and a statistical assumption about random signatures. Secondly, a complexity measure of the template is derived from a set of enrolled signature samples. Finally, given a signature template, a measure to quantify the repeatability of the online signature is derived from a validation set of samples. These three measures can then be used as an indicator for the performance of the system in rejecting random forgery samples and skilled forgery samples and the performance of users in providing accepted genuine samples, respectively. The effectiveness of these three measures and their applications are demonstrated through experiments performed on three online signature datasets and one keystroke dynamics dataset using different verification algorithms.
Optimizing error of high-dimensional statistical queries under differential privacy
Venue: arXiv cs.DB 2018
Year: 2018

Differentially private algorithms for answering sets of predicate counting queries on a sensitive database have many applications. Organizations that collect individual-level data, such as statistical agencies and medical institutions, use them to safely release summary tabulations. However, existing techniques are accurate only on a narrow class of query workloads, or are extremely slow, especially when analyzing more than one or two dimensions of the data. In this work we propose HDMM, a new differentially private algorithm for answering a workload of predicate counting queries, that is especially effective for higher-dimensional datasets. HDMM represents query workloads using an implicit matrix representation and exploits this compact representation to efficiently search (a subset of) the space of differentially private algorithms for one that answers the input query workload with high accuracy. We empirically show that HDMM can efficiently answer queries with lower error than state-of-the-art techniques on a variety of low and high dimensional datasets.
Disease Progression Timeline Estimation for Alzheimer's Disease using Discriminative Event Based Modeling
Venue: arXiv cs.LG 2018
Year: 2018

Alzheimer's Disease (AD) is characterized by a cascade of biomarkers becoming abnormal, the pathophysiology of which is very complex and largely unknown. Event-based modeling (EBM) is a data-driven technique to estimate the sequence in which biomarkers for a disease become abnormal based on cross-sectional data. It can help in understanding the dynamics of disease progression and facilitate early diagnosis and prognosis. In this work we propose a novel discriminative approach to EBM, which is shown to be more accurate than existing state-of-the-art EBM methods. The method first estimates for each subject an approximate ordering of events. Subsequently, the central ordering over all subjects is estimated by fitting a generalized Mallows model to these approximate subject-specific orderings. We also introduce the concept of relative distance between events which helps in creating a disease progression timeline. Subsequently, we propose a method to stage subjects by placing them on the estimated disease progression timeline. We evaluated the proposed method on Alzheimer's Disease Neuroimaging Initiative (ADNI) data and compared the results with existing state-of-the-art EBM methods. We also performed extensive experiments on synthetic data simulating the progression of Alzheimer's disease. The event orderings obtained on ADNI data seem plausible and are in agreement with the current understanding of progression of AD. The proposed patient staging algorithm performed consistently better than that of state-of-the-art EBM methods. Event orderings obtained in simulation experiments were more accurate than those of other EBM methods and the estimated disease progression timeline was observed to correlate with the timeline of actual disease progression. The results of these experiments are encouraging and suggest that discriminative EBM is a promising approach to disease progression modeling.
An Implementation, Empirical Evaluation and Proposed Improvement for Bidirectional Splitting Method for Argumentation Frameworks under Stable Semantics
Venue: arXiv cs.AI 2018
Year: 2018

Abstract argumentation frameworks are formal systems that facilitate obtaining conclusions from non-monotonic knowledge systems. Within such a system, an argumentation semantics is defined as a set of arguments with some desired qualities, for example, that the elements are not in conflict with each other. Splitting an argumentation framework can efficiently speed up the computation of argumentation semantics. With respect to stable semantics, two methods have been proposed to split an argumentation framework either in a unidirectional or bidirectional fashion. The advantage of bidirectional splitting is that it is not structure-dependent and, unlike unidirectional splitting, it can be used for frameworks consisting of a single strongly connected component. Bidirectional splitting makes use of a minimum cut. In this paper, we implement and test the performance of the bidirectional splitting method, along with two types of graph cut algorithms. Experimental data suggest that using a minimum cut will not improve the performance of computing stable semantics in most cases. Hence, instead of a minimum cut, we propose to use a balanced cut, where the framework is split into two sub-frameworks of equal size. Experimental results conducted on bidirectional splitting using the balanced cut show a significant improvement in the performance of computing semantics.
Neural Network Encapsulation
Venue: arXiv cs.LG 2018
Year: 2018

A capsule is a collection of neurons which represents different variants of a pattern in the network. The routing scheme ensures only certain capsules which resemble lower counterparts in the higher layer should be activated. However, the computational complexity becomes a bottleneck for scaling up to larger networks, as lower capsules need to correspond to each and every higher capsule. To resolve this limitation, we approximate the routing process with two branches: a master branch which collects primary information from its direct contact in the lower layer and an aide branch that replenishes master based on pattern variants encoded in other lower capsules. Compared with previous iterative and unsupervised routing scheme, these two branches are communicated in a fast, supervised and one-time pass fashion. The complexity and runtime of the model are therefore decreased by a large margin. Motivated by the routing to make higher capsule have agreement with lower capsule, we extend the mechanism as a compensation for the rapid loss of information in nearby layers. We devise a feedback agreement unit to send back higher capsules as feedback. It could be regarded as an additional regularization to the network. The feedback agreement is achieved by comparing the optimal transport divergence between two distributions (lower and higher capsules). Such an add-on witnesses a unanimous gain in both capsule and vanilla networks. Our proposed EncapNet performs favorably better against previous state-of-the-arts on CIFAR10/100, SVHN and a subset of ImageNet.