OpenRaiser/Intern-Atlas huggingface dataset:
An optimal hierarchical clustering approach to segmentation of mobile LiDAR point clouds
Venue: arXiv cs.CV 2017
Year: 2017

This paper proposes a hierarchical clustering approach for the segmentation of mobile LiDAR point clouds. We perform the hierarchical clustering on unorganized point clouds based on a proximity matrix. The dissimilarity measure in the proximity matrix is calculated by the Euclidean distances between clusters and the difference of normal vectors at given points. The main contribution of this paper is that we succeed to optimize the combination of clusters in the hierarchical clustering. The combination is obtained by achieving the matching of a bipartite graph, and optimized by solving the minimum-cost perfect matching. Results show that the proposed optimal hierarchical clustering (OHC) succeeds to achieve the segmentation of multiple individual objects automatically and outperforms the state-of-the-art LiDAR point cloud segmentation approaches.
Distance Metric Learning using Graph Convolutional Networks: Application to Functional Brain Networks
Venue: arXiv cs.CV 2017
Year: 2017

Evaluating similarity between graphs is of major importance in several computer vision and pattern recognition problems, where graph representations are often used to model objects or interactions between elements. The choice of a distance or similarity metric is, however, not trivial and can be highly dependent on the application at hand. In this work, we propose a novel metric learning method to evaluate distance between graphs that leverages the power of convolutional neural networks, while exploiting concepts from spectral graph theory to allow these operations on irregular graphs. We demonstrate the potential of our method in the field of connectomics, where neuronal pathways or functional connections between brain regions are commonly modelled as graphs. In this problem, the definition of an appropriate graph similarity function is critical to unveil patterns of disruptions associated with certain brain disorders. Experimental results on the ABIDE dataset show that our method can learn a graph similarity metric tailored for a clinical application, improving the performance of a simple k-nn classifier by 11.9% compared to a traditional distance metric.
A Gentle Introduction to Epistemic Planning: The DEL Approach
Venue: arXiv cs.AI 2017
Year: 2017

Epistemic planning can be used for decision making in multi-agent situations with distributed knowledge and capabilities. Dynamic Epistemic Logic (DEL) has been shown to provide a very natural and expressive framework for epistemic planning. In this paper, we aim to give an accessible introduction to DEL-based epistemic planning. The paper starts with the most classical framework for planning, STRIPS, and then moves towards epistemic planning in a number of smaller steps, where each step is motivated by the need to be able to model more complex planning scenarios.
X-ray Astronomical Point Sources Recognition Using Granular Binary-tree SVM
Venue: arXiv cs.CV 2017
Year: 2017

The study on point sources in astronomical images is of special importance, since most energetic celestial objects in the Universe exhibit a point-like appearance. An approach to recognize the point sources (PS) in the X-ray astronomical images using our newly designed granular binary-tree support vector machine (GBT-SVM) classifier is proposed. First, all potential point sources are located by peak detection on the image. The image and spectral features of these potential point sources are then extracted. Finally, a classifier to recognize the true point sources is build through the extracted features. Experiments and applications of our approach on real X-ray astronomical images are demonstrated. comparisons between our approach and other SVM-based classifiers are also carried out by evaluating the precision and recall rates, which prove that our approach is better and achieves a higher accuracy of around 89%.
Survivability Improvement Against Earthquakes in Backbone Optical Networks Using Actual Seismic Zone Information
Venue: arXiv cs.NI 2017
Year: 2017

Optical backbone networks carry a huge amount of bandwidth and serve as a key enabling technology to provide telecommunication connectivity across the world. Hence, in events of network component (node/link) failures, communication networks may suffer from huge amount of bandwidth loss and service disruptions. Natural disasters such as earthquakes, hurricanes, tornadoes, etc., occur at different places around the world, causing severe communication service disruptions due to network component failures. Most of the previous works on optical network survivability assume that the failures are going to occur in future, and the network is made survivable to ensure connectivity in events of failures. With the advancements in seismology, the predictions of earthquakes are becoming more accurate. Earthquakes have been a major cause of telecommunication service disruption in the past. Hence, the information provided by the meteorological departments and other similar agencies of different countries may be helpful in designing networks that are more robust against earthquakes. In this work, we consider the actual information provided by the Indian meteorological department (IMD) on seismic zones, and earthquakes occurred in the past in India, and propose a scheme to improve the survivability of the existing Indian optical network through minute changes in network topology. Simulations show significant improvement in the network survivability can be achieved using the proposed scheme in events of earthquakes.
On the family of 0/1-polytopes with NP-complete non-adjacency relation
Venue: arXiv cs.CC 2017
Year: 2017

In 1995 T. Matsui considered a special family 0/1-polytopes for which the problem of recognizing the non-adjacency of two arbitrary vertices is NP-complete. In 2012 the author of this paper established that all the polytopes of this family are present as faces in the polytopes associated with the following NP-complete problems: the traveling salesman problem, the 3-satisfiability problem, the knapsack problem, the set covering problem, the partial ordering problem, the cube subgraph problem, and some others. In particular, it follows that for these families the non-adjacency relation is also NP-complete. On the other hand, it is known that the vertex adjacency criterion is polynomial for polytopes of the following NP-complete problems: the maximum independent set problem, the set packing and the set partitioning problem, the three-index assignment problem. It is shown that none of the polytopes of the above-mentioned special family (with the exception of a one-dimensional segment) can be the face of polytopes associated with the problems of the maximum independent set, of a set packing and partitioning, and of 3-assignments.
Scientific Outreach with Teegi, a Tangible EEG Interface to Talk about Neurotechnologies
Venue: arXiv cs.HC 2017
Year: 2017

Teegi is an anthropomorphic and tangible avatar exposing a users' brain activity in real time. It is connected to a device sensing the brain by means of electroencephalog-raphy (EEG). Teegi moves its hands and feet and closes its eyes along with the person being monitored. It also displays on its scalp the associated EEG signals, thanks to a semi-spherical display made of LEDs. Attendees can interact directly with Teegi -- e.g. move its limbs -- to discover by themselves the underlying brain processes. Teegi can be used for scientific outreach to introduce neurotechnologies in general and brain-computer interfaces (BCI) in particular.
Detecting Cancer Metastases on Gigapixel Pathology Images
Venue: arXiv cs.CV 2017
Year: 2017

Each year, the treatment decisions for more than 230,000 breast cancer patients in the U.S. hinge on whether the cancer has metastasized away from the breast. Metastasis detection is currently performed by pathologists reviewing large expanses of biological tissues. This process is labor intensive and error-prone. We present a framework to automatically detect and localize tumors as small as 100 x 100 pixels in gigapixel microscopy images sized 100,000 x 100,000 pixels. Our method leverages a convolutional neural network (CNN) architecture and obtains state-of-the-art results on the Camelyon16 dataset in the challenging lesion-level tumor detection task. At 8 false positives per image, we detect 92.4% of the tumors, relative to 82.7% by the previous best automated approach. For comparison, a human pathologist attempting exhaustive search achieved 73.2% sensitivity. We achieve image-level AUC scores above 97% on both the Camelyon16 test set and an independent set of 110 slides. In addition, we discover that two slides in the Camelyon16 training set were erroneously labeled normal. Our approach could considerably reduce false negative rates in metastasis detection.
A Novel Approach of Pseudorandomly sorted list-based Steganography
Venue: arXiv cs.CR 2017
Year: 2017

We propose a new model of steganography based on a list of pseudo-randomly sorted sequences of characters. Given a list $L$ of $m$ columns containing $n$ distinct strings each, with low or no semantic relationship between columns taken two by two, and a secret message $s \in \{0,1\}^*$, our model embeds $s$ in $L$ block by block, by generating, for each column of $L$, a permutation number and by reordering strings contained in it according to that number. Where, letting $l$ be average bit length of a string, the embedding capacity is given by $[(m-1)*log_2(n!-1)/n*l]$. We've shown that optimal efficiency of the method can be obtained with the condition that $(n >> l)$. The results which has been obtained by experiments, show that our model performs a better hiding process than some of the important existing methods, in terms of hiding capacity.
Data-Driven Estimation Of Mutual Information Between Dependent Data
Venue: arXiv cs.IT 2017
Year: 2017

We consider the problem of estimating mutual information between dependent data, an important problem in many science and engineering applications. We propose a data-driven, non-parametric estimator of mutual information in this paper. The main novelty of our solution lies in transforming the data to frequency domain to make the problem tractable. We define a novel metric--mutual information in frequency--to detect and quantify the dependence between two random processes across frequency using Cramér's spectral representation. Our solution calculates mutual information as a function of frequency to estimate the mutual information between the dependent data over time. We validate its performance on linear and nonlinear models. In addition, mutual information in frequency estimated as a part of our solution can also be used to infer cross-frequency coupling in the data.
Graph of Virtual Actors (GOVA): a Big Data Analytics Architecture for IoT
Venue: arXiv cs.SE 2017
Year: 2017

With the emergence of cloud computing and sensor technologies, Big Data analytics for the Internet of Things (IoT) has become the main force behind many innovative solutions for our society's problems. This paper provides practical explanations for the question "why is the number of Big Data applications that succeed and have an effect on our daily life so limited, compared with all of the solutions proposed and tested in the literature?", with examples taken from Smart Grids. We argue that "noninvariants" are the most challenging issues in IoT applications, which can be easily revealed if we use the term "invariant" to replace the more common terms such as "information", "knowledge", or "insight" in any Big Data for IoT research. From our experience with developing Smart Grid applications, we produced a list of "noninvariants", which we believe to be the main causes of the gaps between Big Data in a laboratory and in practice in IoT applications. This paper also proposes Graph of Virtual Actors (GOVA) as a Big Data analytics architecture for IoT applications, which not only can solve the noninvariants issues, but can also quickly scale horizontally in terms of computation, data storage, caching requirements, and programmability of the system.
Online Convex Optimization with Unconstrained Domains and Losses
Venue: arXiv cs.LG 2017
Year: 2017

We propose an online convex optimization algorithm (RescaledExp) that achieves optimal regret in the unconstrained setting without prior knowledge of any bounds on the loss functions. We prove a lower bound showing an exponential separation between the regret of existing algorithms that require a known bound on the loss functions and any algorithm that does not require such knowledge. RescaledExp matches this lower bound asymptotically in the number of iterations. RescaledExp is naturally hyperparameter-free and we demonstrate empirically that it matches prior optimization algorithms that require hyperparameter optimization.
HYDRA: HYbrid Design for Remote Attestation (Using a Formally Verified Microkernel)
Venue: arXiv cs.CR 2017
Year: 2017

Remote Attestation (RA) allows a trusted entity (verifier) to securely measure internal state of a remote untrusted hardware platform (prover). RA can be used to establish a static or dynamic root of trust in embedded and cyber-physical systems. It can also be used as a building block for other security services and primitives, such as software updates and patches, verifiable deletion and memory resetting. There are three major classes of RA designs: hardware-based, software-based, and hybrid, each with its own set of benefits and drawbacks. This paper presents the first hybrid RA design, called HYDRA, that builds upon formally verified software components that ensure memory isolation and protection, as well as enforce access control to memory and other resources. HYDRA obtains these properties by using the formally verified seL4 microkernel. (Until now, this was only attainable with purely hardware-based designs.) Using seL4 requires fewer hardware modifications to the underlying microprocessor. Building upon a formally verified software component increases confidence in security of the overall design of HYDRA and its implementation. We instantiate HYDRA on two commodity hardware platforms and assess the performance and overhead of performing RA on such platforms via experimentation; we show that HYDRA can attest 10MB of memory in less than 500msec when using a Speck-based message authentication code (MAC) to compute a cryptographic checksum over the memory to be attested.
MSF and Connectivity in Limited Variants of the Congested Clique
Venue: arXiv cs.DC 2017
Year: 2017

The congested clique is a synchronous, message-passing model of distributed computing in which each computational unit (node) in each round can send message of O(log n) bits to each other node of the network, where n is the number of nodes. This model has been considered under two extreme scanarios: unicast or broadcast. In the unicast model, a node can send (possibly) different message to each other node of the network. In contrast, in the broadcast model each node sends a single (the same) message to all other nodes. We study the congested clique model parametrized by the range r, the maximum number of different messages a node can send in one round. Following recent progress in design of algorihms for graph connectivity and minimum span- ning forest (MSF) in the unicast congested clique, we study these problems in limited variants of the congested clique. We present the first sub-logarithmic algorithm for connected components in the broadcast congested clique. Then, we show that efficient unicast deterministic algorithm for MSF and randomized algorithm for connected components can be efficiently imple- mented in the rcast model with range r = 2, the weakest model of the congested clique above the broadcast variant (r = 1) in the hierarchy with respect to range. More importantly, our al- gorithms give the first solutions with optimal capacity of communication edges, while preserving small round complexity.
Nviz - A General Purpse Visualization tool for Wireless Sensor Networks
Venue: arXiv cs.NI 2017
Year: 2017

In a Wireless Sensor Network (WSN), data manipulation and representation is a crucial part and can take a lot of time to be developed from scratch. Although various visualization tools have been created for certain projects so far, these tools can only be used in certain scenarios, due to their hard-coded packet formats and network's properties. To speed up the development process, a visualization tool which can adapt to any kind of WSN is essentially necessary. For this purpose, a general-purpose visualization tool - NViz, which can represent and visualize data for any kind of WSN, is proposed. NViz allows users to set their network's properties and packet formats through XML files. Based on properties defined, users can choose the meaning of them and let NViz represents the data respectively. Furthermore, a better Replay mechanism, which lets researchers and developers debug their WSN easily, is also integrated in this tool. NViz is designed based on a layered architecture which allows for clear and well-defined interrelationships and interfaces between each component.
Byzantine-Tolerant Machine Learning
Venue: arXiv cs.DC 2017
Year: 2017

The growth of data, the need for scalability and the complexity of models used in modern machine learning calls for distributed implementations. Yet, as of today, distributed machine learning frameworks have largely ignored the possibility of arbitrary (i.e., Byzantine) failures. In this paper, we study the robustness to Byzantine failures at the fundamental level of stochastic gradient descent (SGD), the heart of most machine learning algorithms. Assuming a set of $n$ workers, up to $f$ of them being Byzantine, we ask how robust can SGD be, without limiting the dimension, nor the size of the parameter space. We first show that no gradient descent update rule based on a linear combination of the vectors proposed by the workers (i.e, current approaches) tolerates a single Byzantine failure. We then formulate a resilience property of the update rule capturing the basic requirements to guarantee convergence despite $f$ Byzantine workers. We finally propose Krum, an update rule that satisfies the resilience property aforementioned. For a $d$-dimensional learning problem, the time complexity of Krum is $O(n^2 \cdot (d + \log n))$.
A Long-Term Analysis of Polarization on Twitter
Venue: arXiv cs.SI 2017
Year: 2017

Social media has played an important role in shaping political discourse over the last decade. At the same time, it is often perceived to have increased political polarization, thanks to the scale of discussions and their public nature. In this paper, we try to answer the question of whether political polarization in the US on Twitter has increased over the last eight years. We analyze a large longitudinal Twitter dataset of 679,000 users and look at signs of polarization in their (i) network - how people follow political and media accounts, (ii) tweeting behavior - whether they retweet content from both sides, and (iii) content - how partisan the hashtags they use are. Our analysis shows that online polarization has indeed increased over the past eight years and that, depending on the measure, the relative change is 10%-20%. Our study is one of very few with such a long-term perspective, encompassing two US presidential elections and two mid-term elections, providing a rare longitudinal analysis.
An Integrated and Scalable Platform for Proactive Event-Driven Traffic Management
Venue: arXiv cs.AI 2017
Year: 2017

Traffic on freeways can be managed by means of ramp meters from Road Traffic Control rooms. Human operators cannot efficiently manage a network of ramp meters. To support them, we present an intelligent platform for traffic management which includes a new ramp metering coordination scheme in the decision making module, an efficient dashboard for interacting with human operators, machine learning tools for learning event definitions and Complex Event Processing tools able to deal with uncertainties inherent to the traffic use case. Unlike the usual approach, the devised event-driven platform is able to predict a congestion up to 4 minutes before it really happens. Proactive decision making can then be established leading to significant improvement of traffic conditions.
Decidability of the Monadic Shallow Linear First-Order Fragment with Straight Dismatching Constraints
Venue: arXiv cs.LO 2017
Year: 2017

The monadic shallow linear Horn fragment is well-known to be decidable and has many application, e.g., in security protocol analysis, tree automata, or abstraction refinement. It was a long standing open problem how to extend the fragment to the non-Horn case, preserving decidability, that would, e.g., enable to express non-determinism in protocols. We prove decidability of the non-Horn monadic shallow linear fragment via ordered resolution further extended with dismatching constraints and discuss some applications of the new decidable fragment.
SensX: About Sensing and Assessment of Complex Human Motion
Venue: arXiv cs.CY 2017
Year: 2017

The great success of wearables and smartphone apps for provision of extensive physical workout instructions boosts a whole industry dealing with consumer oriented sensors and sports equipment. But with these opportunities there are also new challenges emerging. The unregulated distribution of instructions about ambitious exercises enables unexperienced users to undertake demanding workouts without professional supervision which may lead to suboptimal training success or even serious injuries. We believe, that automated supervision and realtime feedback during a workout may help to solve these issues. Therefore we introduce four fundamental steps for complex human motion assessment and present SensX, a sensor-based architecture for monitoring, recording, and analyzing complex and multi-dimensional motion chains. We provide the results of our preliminary study encompassing 8 different body weight exercises, 20 participants, and more than 9,220 recorded exercise repetitions. Furthermore, insights into SensXs classification capabilities and the impact of specific sensor configurations onto the analysis process are given.
The Half-integral Erdös-Pósa Property for Non-null Cycles
Venue: arXiv cs.DM 2017
Year: 2017

A Group Labeled Graph is a pair $(G,Λ)$ where $G$ is an oriented graph and $Λ$ is a mapping from the arcs of $G$ to elements of a group. A (not necessarily directed) cycle $C$ is called non-null if for any cyclic ordering of the arcs in $C$, the group element obtained by `adding' the labels on forward arcs and `subtracting' the labels on reverse arcs is not the identity element of the group. Non-null cycles in group labeled graphs generalize several well-known graph structures, including odd cycles. In this paper, we prove that non-null cycles on Group Labeled Graphs have the half-integral Erdös-Pósa property. That is, there is a function $f:{\mathbb N}\to {\mathbb N}$ such that for any $k\in {\mathbb N}$, any group labeled graph $(G,Λ)$ has a set of $k$ non-null cycles such that each vertex of $G$ appears in at most two of these cycles or there is a set of at most $f(k)$ vertices that intersects every non-null cycle. Since it is known that non-null cycles do not have the integeral Erdös-Pósa property in general, a half-integral Erdös-Pósa result is the best one could hope for.