OpenRaiser/Intern-Atlas huggingface dataset:
Modeling Graphs Using a Mixture of Kronecker Models
Venue: arXiv cs.SI 2017
Year: 2017

Generative models for graphs are increasingly becoming a popular tool for researchers to generate realistic approximations of graphs. While in the past, focus was on generating graphs which follow general laws, such as the power law for degree distribution, current models have the ability to learn from observed graphs and generate synthetic approximations. The primary emphasis of existing models has been to closely match different properties of a single observed graph. Such models, though stochastic, tend to generate samples which do not have significant variance in terms of the various graph properties. We argue that in many cases real graphs are sampled drawn from a graph population (e.g., networks sampled at various time points, social networks for individual schools, healthcare networks for different geographic regions, etc.). Such populations typically exhibit significant variance. However, existing models are not designed to model this variance, which could lead to issues such as overfitting. We propose a graph generative model that focuses on matching the properties of real graphs and the natural variance expected for the corresponding population. The proposed model adopts a mixture-model strategy to expand the expressiveness of Kronecker product based graph models (KPGM), while building upon the two strengths of KPGM, viz., ability to model several key properties of graphs and to scale to massive graph sizes using its elegant fractal growth based formulation. The proposed model, called x-Kronecker Product Graph Model, or xKPGM, allows scalable learning from observed graphs and generates samples that match the mean and variance of several salient graph properties. We experimentally demonstrate the capability of the proposed model to capture the inherent variability in real world graphs on a variety of publicly available graph data sets.
Go game formal revealing by Ising model
Venue: arXiv cs.AI 2017
Year: 2017

Go gaming is a struggle for territory control between rival, black and white, stones on a board. We model the Go dynamics in a game by means of the Ising model whose interaction coefficients reflect essential rules and tactics employed in Go to build long-term strategies. At any step of the game, the energy functional of the model provides the control degree (strength) of a player over the board. A close fit between predictions of the model with actual games is obtained.
SqueezeSeg: Convolutional Neural Nets with Recurrent CRF for Real-Time Road-Object Segmentation from 3D LiDAR Point Cloud
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we address semantic segmentation of road-objects from 3D LiDAR point clouds. In particular, we wish to detect and categorize instances of interest, such as cars, pedestrians and cyclists. We formulate this problem as a point- wise classification problem, and propose an end-to-end pipeline called SqueezeSeg based on convolutional neural networks (CNN): the CNN takes a transformed LiDAR point cloud as input and directly outputs a point-wise label map, which is then refined by a conditional random field (CRF) implemented as a recurrent layer. Instance-level labels are then obtained by conventional clustering algorithms. Our CNN model is trained on LiDAR point clouds from the KITTI dataset, and our point-wise segmentation labels are derived from 3D bounding boxes from KITTI. To obtain extra training data, we built a LiDAR simulator into Grand Theft Auto V (GTA-V), a popular video game, to synthesize large amounts of realistic training data. Our experiments show that SqueezeSeg achieves high accuracy with astonishingly fast and stable runtime (8.7 ms per frame), highly desirable for autonomous driving applications. Furthermore, additionally training on synthesized data boosts validation accuracy on real-world data. Our source code and synthesized data will be open-sourced.
STREAK: An Efficient Engine for Processing Top-k SPARQL Queries with Spatial Filters
Venue: arXiv cs.DB 2017
Year: 2017

The importance of geo-spatial data in critical applications such as emergency response, transportation, agriculture etc., has prompted the adoption of recent GeoSPARQL standard in many RDF processing engines. In addition to large repositories of geo-spatial data -- e.g., LinkedGeoData, OpenStreetMap, etc. -- spatial data is also routinely found in automatically constructed knowledgebases such as Yago and WikiData. While there have been research efforts for efficient processing of spatial data in RDF/SPARQL, very little effort has gone into building end-to-end systems that can holistically handle complex SPARQL queries along with spatial filters. In this paper, we present Streak, a RDF data management system that is designed to support a wide-range of queries with spatial filters including complex joins, top-k, higher-order relationships over spatially enriched databases. Streak introduces various novel features such as a careful identifier encoding strategy for spatial and non-spatial entities, the use of a semantics-aware Quad-tree index that allows for early-termination and a clever use of adaptive query processing with zero plan-switch cost. We show that Streak can scale to some of the largest publicly available semantic data resources such as Yago3 and LinkedGeoData which contain spatial entities and quantifiable predicates useful for result ranking. For experimental evaluations, we focus on top-k distance join queries and demonstrate that Streak outperforms popular spatial join algorithms as well as state of the art end-to-end systems like Virtuoso and PostgreSQL.
Distributed Deep Transfer Learning by Basic Probability Assignment
Venue: arXiv cs.LG 2017
Year: 2017

Transfer learning is a popular practice in deep neural networks, but fine-tuning of large number of parameters is a hard task due to the complex wiring of neurons between splitting layers and imbalance distributions of data in pretrained and transferred domains. The reconstruction of the original wiring for the target domain is a heavy burden due to the size of interconnections across neurons. We propose a distributed scheme that tunes the convolutional filters individually while backpropagates them jointly by means of basic probability assignment. Some of the most recent advances in evidence theory show that in a vast variety of the imbalanced regimes, optimizing of some proper objective functions derived from contingency matrices prevents biases towards high-prior class distributions. Therefore, the original filters get gradually transferred based on individual contributions to overall performance of the target domain. This largely reduces the expected complexity of transfer learning whilst highly improves precision. Our experiments on standard benchmarks and scenarios confirm the consistent improvement of our distributed deep transfer learning strategy.
The Emptiness Problem for Valence Automata over Graph Monoids
Venue: arXiv cs.FL 2017
Year: 2017

This work studies which storage mechanisms in automata permit decidability of the emptiness problem. The question is formalized using valence automata, an abstract model of automata in which the storage mechanism is given by a monoid. For each of a variety of storage mechanisms, one can choose a (typically infinite) monoid $M$ such that valence automata over $M$ are equivalent to (one-way) automata with this type of storage. In fact, many important storage mechanisms can be realized by monoids defined by finite graphs, called graph monoids. Examples include pushdown stacks, partially blind counters (which behave like Petri net places), blind counters (which may attain negative values), and combinations thereof. Hence, we study for which graph monoids the emptiness problem for valence automata is decidable. A particular model realized by graph monoids is that of Petri nets with a pushdown stack. For these, decidability is a long-standing open question and we do not answer it here. However, if one excludes subgraphs corresponding to this model, a characterization can be achieved. Moreover, we provide a description of those storage mechanisms for which decidability remains open. This leads to a model that naturally generalizes both pushdown Petri nets and the priority multicounter machines introduced by Reinhardt. The cases that are proven decidable constitute a natural and apparently new extension of Petri nets with decidable reachability. It is finally shown that this model can be combined with another such extension by Atig and Ganty: We present a further decidability result that subsumes both of these Petri net extensions.
Hardened Paxos Through Consistency Validation
Venue: arXiv cs.DC 2017
Year: 2017

Due to the emergent adoption of distributed systems when building applications, demand for reliability and availability has increased. These properties can be achieved through replication techniques using middleware algorithms that must be capable of tolerating faults. Certain faults such as arbitrary faults, however, may be more difficult to tolerate, resulting in more complex and resource intensive algorithms that end up being not so practical to use. We propose and experiment with the use of consistency validation techniques to harden a benign fault-tolerant Paxos, thus being able to detect and tolerate non-malicious arbitrary faults.
Learning compressed representations of blood samples time series with missing data
Venue: arXiv cs.NE 2017
Year: 2017

Clinical measurements collected over time are naturally represented as multivariate time series (MTS), which often contain missing data. An autoencoder can learn low dimensional vectorial representations of MTS that preserve important data characteristics, but cannot deal explicitly with missing data. In this work, we propose a new framework that combines an autoencoder with the Time series Cluster Kernel (TCK), a kernel that accounts for missingness patterns in MTS. Via kernel alignment, we incorporate TCK in the autoencoder to improve the learned representations in presence of missing data. We consider a classification problem of MTS with missing values, representing blood samples of patients with surgical site infection. With our approach, rather than with a standard autoencoder, we learn representations in low dimensions that can be classified better.
Strategies and Influence of Social Bots in a 2017 German state election - A case study on Twitter
Venue: arXiv cs.CY 2017
Year: 2017

As social media has permeated large parts of the population it simultaneously has become a way to reach many people e.g. with political messages. One way to efficiently reach those people is the application of automated computer programs that aim to simulate human behaviour - so called social bots. These bots are thought to be able to potentially influence users' opinion about a topic. To gain insight in the use of these bots in the run-up to the German Bundestag elections, we collected a dataset from Twitter consisting of tweets regarding a German state election in May 2017. The strategies and influence of social bots were analysed based on relevant features and network visualization. 61 social bots were identified. Possibly due to the concentration on German language as well as the elections regionality, identified bots showed no signs of collective political strategies and low to none influence. Implications are discussed.
Low Precision RNNs: Quantizing RNNs Without Losing Accuracy
Venue: arXiv cs.LG 2017
Year: 2017

Similar to convolution neural networks, recurrent neural networks (RNNs) typically suffer from over-parameterization. Quantizing bit-widths of weights and activations results in runtime efficiency on hardware, yet it often comes at the cost of reduced accuracy. This paper proposes a quantization approach that increases model size with bit-width reduction. This approach will allow networks to perform at their baseline accuracy while still maintaining the benefits of reduced precision and overall model size reduction.
A Computational Framework for Multi-Modal Social Action Identification
Venue: arXiv cs.SI 2017
Year: 2017

We create a computational framework for understanding social action and demonstrate how this framework can be used to build an open-source event detection tool with scalable statistical machine learning algorithms and a subsampled database of over 600 million geo-tagged Tweets from around the world. These Tweets were collected between April 1st, 2014 and April 30th, 2015, most notably when the Black Lives Matter movement began. We demonstrate how these methods can be used diagnostically-by researchers, government officials and the public-to understand peaceful and violent collective action at very fine-grained levels of time and geography.
BigSparse: High-performance external graph analytics
Venue: arXiv cs.DB 2017
Year: 2017

We present BigSparse, a fully external graph analytics system that picks up where semi-external systems like FlashGraph and X-Stream, which only store vertex data in memory, left off. BigSparse stores both edge and vertex data in an array of SSDs and avoids random updates to the vertex data, by first logging the vertex updates and then sorting the log to sequentialize accesses to the SSDs. This newly introduced sorting overhead is reduced significantly by interleaving sorting with vertex reduction operations. In our experiments on a server with 32GB to 64GB of DRAM, BigSparse outperforms other in-memory and semi-external graph analytics systems for algorithms such as PageRank, BreadthFirst Search, and Betweenness-Centrality for terabyte-size graphs with billions of vertices. BigSparse is capable of highspeed analytics of much larger graphs, on the same machine configuration.
An efficient deep learning hashing neural network for mobile visual search
Venue: arXiv cs.CV 2017
Year: 2017

Mobile visual search applications are emerging that enable users to sense their surroundings with smart phones. However, because of the particular challenges of mobile visual search, achieving a high recognition bitrate has becomes a consistent target of previous related works. In this paper, we propose a few-parameter, low-latency, and high-accuracy deep hashing approach for constructing binary hash codes for mobile visual search. First, we exploit the architecture of the MobileNet model, which significantly decreases the latency of deep feature extraction by reducing the number of model parameters while maintaining accuracy. Second, we add a hash-like layer into MobileNet to train the model on labeled mobile visual data. Evaluations show that the proposed system can exceed state-of-the-art accuracy performance in terms of the MAP. More importantly, the memory consumption is much less than that of other deep learning models. The proposed method requires only $13$ MB of memory for the neural network and achieves a MAP of $97.80\%$ on the mobile location recognition dataset used for testing.
Human Learning of Unknown Environments in Agile Guidance Tasks
Venue: arXiv cs.RO 2017
Year: 2017

Trained human pilots or operators still stand out through their efficient, robust, and versatile skills in guidance tasks such as driving agile vehicles in spatial environments or performing complex surgeries. This research studies how humans learn a task environment for agile behavior. The hypothesis is that sensory-motor primitives previously described as interaction patterns and proposed as units of behavior for organization and planning of behavior provide elements of memory structure needed to efficiently learn task environments. The paper presents a modeling and analysis framework using the interaction patterns to formulate learning as a graph learning process and apply the framework to investigate and evaluate human learning and decision-making while operating in unknown environments. This approach emphasizes the effects of agent-environment dynamics (e.g., a vehicle controlled by a human operator), which is not emphasized in existing environment learning studies. The framework is applied to study human data collected from simulated first-person guidance experiments in an obstacle field. Subjects were asked to perform multiple trials and find minimum-time routes between prespecified start and goal locations without priori knowledge of the environment.
Skew constacyclic codes over Fq+uFq+vFq
Venue: arXiv cs.IT 2017
Year: 2017

In this paper skew constacyclic codes over finite non-chain ring R = F_q+uF_q+vF_q, where q= p^m, p is an odd prime and u^{2}=u, v^{2}=v, uv = vu = 0 are studied. We show that Gray image of a skew alpha-constacyclic cyclic code of length n over R is a skew alpha-quasi-cyclic code of length $3n$ over F_{q} of index 3. It is also shown that skew alpha-constacyclic codes are either equivalent to alpha-constacyclic codes or alpha-quasi-twisted codes over R. Further, the structural properties of skew constacyclic over R are obtained by decomposition method.
Geometric Computing with Chain Complexes: Design and Features of a Julia Package
Venue: arXiv cs.CG 2017
Year: 2017

Geometric computing with chain complexes allows for the computation of the whole chain of linear spaces and (co)boundary operators generated by a space decomposition into a cell complex. The space decomposition is stored and handled with LAR (Linear Algebraic Representation), i.e. with sparse integer arrays, and allows for using cells of a very general type, even non convex and with internal holes. In this paper we discuss the features and the merits of this approach, and describe the goals and the implementation of a software package aiming at providing for simple and efficient computational support of geometric computing with any kind of meshes, using linear algebra tools with sparse matrices. The library is being written in Julia, the novel efficient and parallel language for scientific computing. This software, that is being ported on hybrid architectures (CPU+GPU) of last generation, is yet under development.
Strategic Classification from Revealed Preferences
Venue: arXiv cs.LG 2017
Year: 2017

We study an online linear classification problem, in which the data is generated by strategic agents who manipulate their features in an effort to change the classification outcome. In rounds, the learner deploys a classifier, and an adversarially chosen agent arrives, possibly manipulating her features to optimally respond to the learner. The learner has no knowledge of the agents' utility functions or "real" features, which may vary widely across agents. Instead, the learner is only able to observe their "revealed preferences" --- i.e. the actual manipulated feature vectors they provide. For a broad family of agent cost functions, we give a computationally efficient learning algorithm that is able to obtain diminishing "Stackelberg regret" --- a form of policy regret that guarantees that the learner is obtaining loss nearly as small as that of the best classifier in hindsight, even allowing for the fact that agents will best-respond differently to the optimal classifier.
Analysis of Discrete-Time MIMO OFDM-Based Orthogonal Time Frequency Space Modulation
Venue: arXiv cs.IT 2017
Year: 2017

Orthogonal Time Frequency Space (OTFS) is a novel modulation scheme designed in the Doppler-delay domain to fully exploit time and frequency diversity of general time-varying channels. In this paper, we present a novel discrete-time analysis of OFDM-based OTFS transceiver with a concise and vectorized input-output relationship that clearly characterizes the contribution of each underlying signal processing block in such systems. When adopting cyclic prefix in the time domain, our analysis reveals that the proposed MIMO OTFS and OFDM systems have the same ergodic capacity despite the well-known fact that the former has great advantages in low-complexity receiver design for high Doppler channels. The proposed discrete-time vectorized formulation is applicable to general fast fading channels with arbitrary window functions. It also enables practical low-complexity receiver design for which such a concise formulation of the input-output relationship is of great benefits.
Communication Dualism in Distributed Systems with Petri Net Interpretation
Venue: arXiv cs.DC 2017
Year: 2017

In the paper notion of communication dualism id formalized and explained in Petri net interpretation. We consider communication dualism a basic property of communication in distributed systems. The formalization is done in the Integrated Model of Distributed Systems (IMDS) where synchronous communication, as well as asynchronous message-passing and variable-sharing are modeled in a common framework. In the light of this property, communication in distributed systems can be seen as a two-dimensional phenomenon with passing being its spatial dimension and sharing its temporal dimension. Any distributed system can be modeled as a composition of message-passes asynchronous processes or as a composition of variable-sharing asynchronous processes. A method of automatic process extraction in Petri net interpretation of IMDS is presented.
Further factorization of $x^n-1$ over a finite field
Venue: arXiv cs.IT 2017
Year: 2017

Let $\Bbb F_q$ be a finite field with $q$ elements and $n$ a positive integer. Martínez, Vergara and Oliveira \cite{MVO} explicitly factorized $x^{n} - 1$ over $\Bbb F_q$ under the condition of $rad(n)|(q-1)$. In this paper, suppose that $rad(n)\nmid (q-1)$ and $rad(n)|(q^w-1)$, where $w$ is a prime, we explicitly factorize $x^{n}-1$ into irreducible factors in $\Bbb F_q[x]$ and count the number of its irreducible factors.
How big is big enough? Unsupervised word sense disambiguation using a very large corpus
Venue: arXiv cs.CL 2017
Year: 2017

In this paper, the problem of disambiguating a target word for Polish is approached by searching for related words with known meaning. These relatives are used to build a training corpus from unannotated text. This technique is improved by proposing new rich sources of replacements that substitute the traditional requirement of monosemy with heuristics based on wordnet relations. The naïve Bayesian classifier has been modified to account for an unknown distribution of senses. A corpus of 600 million web documents (594 billion tokens), gathered by the NEKST search engine allows us to assess the relationship between training set size and disambiguation accuracy. The classifier is evaluated using both a wordnet baseline and a corpus with 17,314 manually annotated occurrences of 54 ambiguous words.