OpenRaiser/Intern-Atlas huggingface dataset:
Spread of hate speech in online social media
Venue: arXiv cs.SI 2018
Year: 2018

The present online social media platform is afflicted with several issues, with hate speech being on the predominant forefront. The prevalence of online hate speech has fueled horrific real-world hate-crime such as the mass-genocide of Rohingya Muslims, communal violence in Colombo and the recent massacre in the Pittsburgh synagogue. Consequently, It is imperative to understand the diffusion of such hateful content in an online setting. We conduct the first study that analyses the flow and dynamics of posts generated by hateful and non-hateful users on Gab (gab.com) over a massive dataset of 341K users and 21M posts. Our observations confirms that hateful content diffuse farther, wider and faster and have a greater outreach than those of non-hateful users. A deeper inspection into the profiles and network of hateful and non-hateful users reveals that the former are more influential, popular and cohesive. Thus, our research explores the interesting facets of diffusion dynamics of hateful users and broadens our understanding of hate speech in the online world.
Cerebrovascular Network Segmentation on MRA Images with Deep Learning
Venue: arXiv cs.CV 2018
Year: 2018

Deep learning has been shown to produce state of the art results in many tasks in biomedical imaging, especially in segmentation. Moreover, segmentation of the cerebrovascular structure from magnetic resonance angiography is a challenging problem because its complex geometry and topology have a large inter-patient variability. Therefore, in this work, we present a convolutional neural network approach for this problem. Particularly, a new network topology inspired by the U-net 3D and by the Inception modules, entitled Uception. In addition, a discussion about the best objective function for sparse data also guided most choices during the project. State of the art models are also implemented for a comparison purpose and final results show that the proposed architecture has the best performance in this particular context.
Mapping RDF Graphs to Property Graphs
Venue: arXiv cs.DB 2018
Year: 2018

Increasing amounts of scientific and social data are published in the Resource Description Framework (RDF). Although the RDF data can be queried using the SPARQL language, even the SPARQL-based operation has a limitation in implementing traversal or analytical algorithms. Recently, a variety of graph database implementations dedicated to analyses on the property graph model have emerged. However, the RDF model and the property graph model are not interoperable. Here, we developed a framework based on the Graph to Graph Mapping Language (G2GML) for mapping RDF graphs to property graphs to make the most of accumulated RDF data. Using this framework, graph data described in the RDF model can be converted to the property graph model and can be loaded to several graph database engines for further analysis. Future works include implementing and utilizing graph algorithms to make the most of the accumulated data in various analytical engines.
MLIC: A MaxSAT-Based framework for learning interpretable classification rules
Venue: arXiv cs.AI 2018
Year: 2018

The wide adoption of machine learning approaches in the industry, government, medicine and science has renewed the interest in interpretable machine learning: many decisions are too important to be delegated to black-box techniques such as deep neural networks or kernel SVMs. Historically, problems of learning interpretable classifiers, including classification rules or decision trees, have been approached by greedy heuristic methods as essentially all the exact optimization formulations are NP-hard. Our primary contribution is a MaxSAT-based framework, called MLIC, which allows principled search for interpretable classification rules expressible in propositional logic. Our approach benefits from the revolutionary advances in the constraint satisfaction community to solve large-scale instances of such problems. In experimental evaluations over a collection of benchmarks arising from practical scenarios, we demonstrate its effectiveness: we show that the formulation can solve large classification problems with tens or hundreds of thousands of examples and thousands of features, and to provide a tunable balance of accuracy vs. interpretability. Furthermore, we show that in many problems interpretability can be obtained at only a minor cost in accuracy. The primary objective of the paper is to show that recent advances in the MaxSAT literature make it realistic to find optimal (or very high quality near-optimal) solutions to large-scale classification problems. The key goal of the paper is to excite researchers in both interpretable classification and in the CP community to take it further and propose richer formulations, and to develop bespoke solvers attuned to the problem of interpretable ML.
HashFlow For Better Flow Record Collection
Venue: arXiv cs.NI 2018
Year: 2018

Collecting flow records is a common practice of network operators and researchers for monitoring, diagnosing and understanding a network. Traditional tools like NetFlow face great challenges when both the speed and the complexity of the network traffic increase. To keep pace up, we propose HashFlow, a tool for more efficient and accurate collection and analysis of flow records. The central idea of HashFlow is to maintain accurate records for elephant flows, but summarized records for mice flows, by applying a novel collision resolution and record promotion strategy to hash tables. The performance bound can be analyzed with a probabilistic model, and with this strategy, HashFlow achieves a better utilization of space, and also more accurate flow records, without bringing extra complexity. We have implemented HashFlow, as well as several latest flow measurement algorithms such as FlowRadar, HashPipe and ElasticSketch, in a P4 software switch. Then we use traces from different operational networks to evaluate them. In these experiments, for various types of traffic analysis applications, HashFlow consistently demonstrates a clearly better performance against its state-of-the-art competitors. For example, using a small memory of 1 MB, HashFlow can accurately record around 55K flows, which is often 12.5% higher than the others. For estimating the sizes of 50K flows, HashFlow achieves a relative error of around 11.6%, while the estimation error of the best competitor is 42.9% higher. It detects 96.1% of the heavy hitters out of 250K flows with a size estimation error of 5.6%, which is 11.3% and 73.7% better than the best competitor respectively. At last, we show these merits of HashFlow come with almost no degradation of throughput.
Voting and Bribing in Single-Exponential Time
Venue: arXiv cs.DS 2018
Year: 2018

We introduce a general problem about bribery in voting systems. In the $\mathcal{R}$-Multi-Bribery problem, the goal is to bribe a set of voters at minimum cost such that a desired candidate wins the perturbed election under the voting rule R. Voters assign prices for withdrawing their vote, for swapping the positions of two consecutive candidates in their preference order, and for perturbing their approval count to favour candidates. As our main result, we show that $\mathcal{R}$-Multi-Bribery is fixed-parameter tractable parameterized by the number of candidates for many natural voting rules $\mathcal{R}$, including Kemeny rule, all scoring protocols, maximin rule, Bucklin rule, fallback rule, SP-AV, and any C1 rule. In particular, our result resolves the parameterized complexity of $\mathcal{R}$-Swap Bribery for all those voting rules, thereby solving a long-standing open problem and "Challenge #2" of the "Nine Research Challenges in Computational Social Choice" by Bredereck et al. Further, our algorithm runs in single-exponential time for arbitrary cost; it thus improves the earlier double-exponential time algorithm by Dorn and Schlotter that is restricted to the uniform-cost case for all scoring protocols, the maximin rule, and Bucklin rule.
Termination of $λ$$Π$ modulo rewriting using the size-change principle (work in progress)
Venue: arXiv cs.LO 2018
Year: 2018

The Size-Change Termination principle was first introduced to study the termination of first-order functional programs. In this work, we show that it can also be used to study the termination of higher-order rewriting in a system of dependent types extending LF.
Chore division on a graph
Venue: arXiv cs.AI 2018
Year: 2018

The paper considers fair allocation of indivisible nondisposable items that generate disutility (chores). We assume that these items are placed in the vertices of a graph and each agent's share has to form a connected subgraph of this graph. Although a similar model has been investigated before for goods, we show that the goods and chores settings are inherently different. In particular, it is impossible to derive the solution of the chores instance from the solution of its naturally associated fair division instance. We consider three common fair division solution concepts, namely proportionality, envy-freeness and equitability, and two individual disutility aggregation functions: additive and maximum based. We show that deciding the existence of a fair allocation is hard even if the underlying graph is a path or a star. We also present some efficiently solvable special cases for these graph topologies.
Improving Medical Short Text Classification with Semantic Expansion Using Word-Cluster Embedding
Venue: arXiv cs.CL 2018
Year: 2018

Automatic text classification (TC) research can be used for real-world problems such as the classification of in-patient discharge summaries and medical text reports, which is beneficial to make medical documents more understandable to doctors. However, in electronic medical records (EMR), the texts containing sentences are shorter than that in general domain, which leads to the lack of semantic features and the ambiguity of semantic. To tackle this challenge, we propose to add word-cluster embedding to deep neural network for improving short text classification. Concretely, we first use hierarchical agglomerative clustering to cluster the word vectors in the semantic space. Then we calculate the cluster center vector which represents the implicit topic information of words in the cluster. Finally, we expand word vector with cluster center vector, and implement classifiers using CNN and LSTM respectively. To evaluate the performance of our proposed method, we conduct experiments on public data sets TREC and the medical short sentences data sets which is constructed and released by us. The experimental results demonstrate that our proposed method outperforms state-of-the-art baselines in short sentence classification on both medical domain and general domain.
A Knowledge Graph Based Solution for Entity Discovery and Linking in Open-Domain Questions
Venue: arXiv cs.CL 2018
Year: 2018

Named entity discovery and linking is the fundamental and core component of question answering. In Question Entity Discovery and Linking (QEDL) problem, traditional methods are challenged because multiple entities in one short question are difficult to be discovered entirely and the incomplete information in short text makes entity linking hard to implement. To overcome these difficulties, we proposed a knowledge graph based solution for QEDL and developed a system consists of Question Entity Discovery (QED) module and Entity Linking (EL) module. The method of QED module is a tradeoff and ensemble of two methods. One is the method based on knowledge graph retrieval, which could extract more entities in questions and guarantee the recall rate, the other is the method based on Conditional Random Field (CRF), which improves the precision rate. The EL module is treated as a ranking problem and Learning to Rank (LTR) method with features such as semantic similarity, text similarity and entity popularity is utilized to extract and make full use of the information in short texts. On the official dataset of a shared QEDL evaluation task, our approach could obtain 64.44% F1 score of QED and 64.86% accuracy of EL, which ranks the 2nd place and indicates its practical use for QEDL problem.
Computational Graph Approach for Detection of Composite Human Activities
Venue: arXiv cs.NE 2018
Year: 2018

Existing work in human activity detection classifies physical activities using a single fixed-length subset of a sensor signal. However, temporally consecutive subsets of a sensor signal are not utilized. This is not optimal for classifying physical activities (composite activities) that are composed of a temporal series of simpler activities (atomic activities). A sport consists of physical activities combined in a fashion unique to that sport. The constituent physical activities and the sport are not fundamentally different. We propose a computational graph architecture for human activity detection based on the readings of a triaxial accelerometer. The resulting model learns 1) a representation of the atomic activities of a sport and 2) to classify physical activities as compositions of the atomic activities. The proposed model, alongside with a set of baseline models, was tested for a simultaneous classification of eight physical activities (walking, nordic walking, running, soccer, rowing, bicycling, exercise bicycling and lying down). The proposed model obtained an overall mean accuracy of 77.91% (population) and 95.28% (personalized). The corresponding accuracies of the best baseline model were 73.52% and 90.03%. However, without combining consecutive atomic activities, the corresponding accuracies of the proposed model were 71.52% and 91.22%. The results show that our proposed model is accurate, outperforms the baseline models and learns to combine simple activities into complex activities. Composite activities can be classified as combinations of atomic activities. Our proposed architecture is a basis for accurate models in human activity detection.
Ibdxnet: Leveraging InfiniBand in Highly Concurrent Java Applications
Venue: arXiv cs.NI 2018
Year: 2018

In this report, we describe the design and implementation of Ibdxnet, a low-latency and high-throughput transport providing the benefits of InfiniBand networks to Java applications. Ibdxnet is part of the Java-based DXNet library, a highly concurrent and simple to use messaging stack with transparent serialization of messaging objects and focus on very small messages (< 64 bytes). Ibdxnet implements the transport interface of DXNet in Java and a custom C++ library in native space using JNI. Several optimizations in both spaces minimize context switching overhead between Java and C++ and are not burdening message latency or throughput. Communication is implemented using the messaging verbs of the ibverbs library complemented by an automatic connection management in the native library. We compared DXNet with the Ibdxnet transport to the MPI implementations FastMPJ and MVAPICH2. For small messages up to 64 bytes using multiple threads, DXNet with the Ibdxnet transport achieves a bi-directional message rate of 10 million messages per second and surpasses FastMPJ by a factor of 4 and MVAPICH by a factor of 2. Furthermore, DXNet scales well on a high load all-to-all communication with up to 8 nodes achieving a total aggregated message rate of 43.4 million messages per second for small messages and a throughput saturation of 33.6 GB/s with only 2 kb message size.
Correlation Clustering in Data Streams
Venue: arXiv cs.DS 2018
Year: 2018

Clustering is a fundamental tool for analyzing large data sets. A rich body of work has been devoted to designing data-stream algorithms for the relevant optimization problems such as $k$-center, $k$-median, and $k$-means. Such algorithms need to be both time and and space efficient. In this paper, we address the problem of correlation clustering in the dynamic data stream model. The stream consists of updates to the edge weights of a graph on $n$ nodes and the goal is to find a node-partition such that the end-points of negative-weight edges are typically in different clusters whereas the end-points of positive-weight edges are typically in the same cluster. We present polynomial-time, $O(n\cdot \ \mbox{polylog}~n)$-space approximation algorithms for natural problems that arise. We first develop data structures based on linear sketches that allow the "quality" of a given node-partition to be measured. We then combine these data structures with convex programming and sampling techniques to solve the relevant approximation problem. Unfortunately, the standard LP and SDP formulations are not obviously solvable in $O(n\cdot \mbox{polylog}~n)$-space. Our work presents space-efficient algorithms for the convex programming required, as well as approaches to reduce the adaptivity of the sampling.
Point-to-Pose Voting based Hand Pose Estimation using Residual Permutation Equivariant Layer
Venue: arXiv cs.CV 2018
Year: 2018

Recently, 3D input data based hand pose estimation methods have shown state-of-the-art performance, because 3D data capture more spatial information than the depth image. Whereas 3D voxel-based methods need a large amount of memory, PointNet based methods need tedious preprocessing steps such as K-nearest neighbour search for each point. In this paper, we present a novel deep learning hand pose estimation method for an unordered point cloud. Our method takes 1024 3D points as input and does not require additional information. We use Permutation Equivariant Layer (PEL) as the basic element, where a residual network version of PEL is proposed for the hand pose estimation task. Furthermore, we propose a voting based scheme to merge information from individual points to the final pose output. In addition to the pose estimation task, the voting-based scheme can also provide point cloud segmentation result without ground-truth for segmentation. We evaluate our method on both NYU dataset and the Hands2017Challenge dataset. Our method outperforms recent state-of-the-art methods, where our pose accuracy is currently the best for the Hands2017Challenge dataset.
Simple, Fast and Practicable Algorithms for Cholesky, LU and QR Decomposition Using Fast Rectangular Matrix Multiplication
Venue: arXiv cs.NA 2018
Year: 2018

This note presents fast Cholesky/LU/QR decomposition algorithms with $O(n^{2.529})$ time complexity when using the fastest known matrix multiplication. The algorithms have potential application, since a quickly made implementation using Strassen multiplication has lesser execution time than the employed by the GNU Scientific Library for the same task in at least a few examples. The underlaying ideas are very simple. Despite this, I have been unable to find these methods in the literature.
Vision-Based High Speed Driving with a Deep Dynamic Observer
Venue: arXiv cs.RO 2018
Year: 2018

In this paper we present a framework for combining deep learning-based road detection, particle filters, and Model Predictive Control (MPC) to drive aggressively using only a monocular camera, IMU, and wheel speed sensors. This framework uses deep convolutional neural networks combined with LSTMs to learn a local cost map representation of the track in front of the vehicle. A particle filter uses this dynamic observation model to localize in a schematic map, and MPC is used to drive aggressively using this particle filter based state estimate. We show extensive real world testing results, and demonstrate reliable operation of the vehicle at the friction limits on a complex dirt track. We reach speeds above 27 mph (12 m/s) on a dirt track with a 105 foot (32m) long straight using our 1:5 scale test vehicle. A video of these results can be found at https://www.youtube.com/watch?v=5ALIK-z-vUg
Characterization and space embedding of directed graphs and social networks through magnetic Laplacians
Venue: arXiv cs.SI 2018
Year: 2018

Though commonly found in the real world, directed networks have received relatively less attention from the literature in which concerns their topological and dynamical characteristics. In this work, we develop a magnetic Laplacian-based framework that can be used for studying directed complex networks. More specifically, we introduce a specific heat measurement that can help to characterize the network topology. It is shown that, by using this approach, it is possible to identify the types of several networks, as well as to infer parameters underlying specific network configurations. Then, we consider the dynamics associated with the magnetic Laplacian as a means of embedding networks into a metric space, allowing the identification of mesoscopic structures in artificial networks or unravel the polarization on political blogosphere. By defining a coarse-graining procedure in this metric space, we show how to connect the specific heat measurement and the positions of nodes in this space.
Performance Evaluation of Cryptographic Ciphers on IoT Devices
Venue: arXiv cs.CR 2018
Year: 2018

With the advent of Internet of Things (IoT) and the increasing use of application-based processors, security infrastructure needs to be examined on some widely-used IoT hardware architectures. Applications in today's world are moving towards IoT concepts as this makes them fast, efficient, modular and future-proof. However, this leads to a greater security risk as IoT devices thrive in an ecosystem of co-existence and interconnection. As a result of these security risks, it is of utmost importance to test the existing cryptographic ciphers on such devices and determine if they are viable in terms of swiftness of execution time and memory consumption efficiency. It is also important to determine if there is a requirement to develop new lightweight cryptographic ciphers for these devices. This paper hopes to accomplish the above-mentioned objective by testing various encryption-decryption techniques on different IoT based devices and creating a comparison of execution speeds between these devices for a variety of different data sizes. Keywords-Internet of things(IoT), application-based processors, security, encryption-decryption, speed, efficiency
Relative Entropy Regularized Policy Iteration
Venue: arXiv cs.LG 2018
Year: 2018

We present an off-policy actor-critic algorithm for Reinforcement Learning (RL) that combines ideas from gradient-free optimization via stochastic search with learned action-value function. The result is a simple procedure consisting of three steps: i) policy evaluation by estimating a parametric action-value function; ii) policy improvement via the estimation of a local non-parametric policy; and iii) generalization by fitting a parametric policy. Each step can be implemented in different ways, giving rise to several algorithm variants. Our algorithm draws on connections to existing literature on black-box optimization and 'RL as an inference' and it can be seen either as an extension of the Maximum a Posteriori Policy Optimisation algorithm (MPO) [Abdolmaleki et al., 2018a], or as an extension of Trust Region Covariance Matrix Adaptation Evolutionary Strategy (CMA-ES) [Abdolmaleki et al., 2017b; Hansen et al., 1997] to a policy iteration scheme. Our comparison on 31 continuous control tasks from parkour suite [Heess et al., 2017], DeepMind control suite [Tassa et al., 2018] and OpenAI Gym [Brockman et al., 2016] with diverse properties, limited amount of compute and a single set of hyperparameters, demonstrate the effectiveness of our method and the state of art results. Videos, summarizing results, can be found at goo.gl/HtvJKR .