OpenRaiser/Intern-Atlas huggingface dataset:
Testing isomorphism of circular-arc graphs -- Hsu's approach revisited
Venue: arXiv cs.DS 2019
Year: 2019

Circular-arc graphs are intersection graphs of arcs on the circle. The aim of our work is to present a polynomial time algorithm testing whether two circular-arc graphs are isomorphic. To accomplish our task we construct decomposition trees, which are the structures representing all normalized intersection models of circular-arc graphs. Normalized models reflect the neighbourhood relation in circular-arc graphs and can be seen as their canonical representations; in particular, every intersection model can be easily transformed into a normalized one. Our work adapts and appropriately extends the previous work on the similar topic done by Hsu [\emph{SIAM J. Comput. 24(3), 411--439, (1995)}]. In his work, Hsu developed decomposition trees representing all normalized models of circular-arc graphs. However due to the counterexample given in [\emph{Discrete Math. Theor. Comput. Sci., 15(1), 157--182, 2013}], his decomposition trees can not be used by algorithms testing isomorphism of circular-arc graphs.
Reliable Group Communication Protocol for Internet of Things
Venue: arXiv cs.NI 2019
Year: 2019

In this paper, we propose RECOUP, a reliable group communication routing protocol for IoT networks. RECOUP efficiently uses a low-overhead cluster-based multicast routing technique on top of the RPL protocol. RECOUP increases the probability of message delivery to the intended destination(s), irrespective of the network size and faults (such as broken links or non-responsive nodes), and in the presence of misbehaving nodes.We show that the cluster-based routing mechanism of RECOUP remains robust in presence of various topology (i.e., rank and sybil) and data communication (i.e., blackhole, wormhole, and jamming) attacks targeting the IoT networking infrastructure.An implementation of RECOUP is realized in Contiki. Our results show the effectiveness of RECOUP over state-of-art protocols concerning packet delivery ratio to 25%, end-to-end delay down to 100 ms, low radio transmissions required for per packet delivery to 6 mJ, and most importantly, it improves the robustness and scalability of data communication process in thewhole network.
BoLTVOS: Box-Level Tracking for Video Object Segmentation
Venue: arXiv cs.CV 2019
Year: 2019

We approach video object segmentation (VOS) by splitting the task into two sub-tasks: bounding box level tracking, followed by bounding box segmentation. Following this paradigm, we present BoLTVOS (Box-Level Tracking for VOS), which consists of an R-CNN detector conditioned on the first-frame bounding box to detect the object of interest, a temporal consistency rescoring algorithm, and a Box2Seg network that converts bounding boxes to segmentation masks. BoLTVOS performs VOS using only the firstframe bounding box without the mask. We evaluate our approach on DAVIS 2017 and YouTube-VOS, and show that it outperforms all methods that do not perform first-frame fine-tuning. We further present BoLTVOS-ft, which learns to segment the object in question using the first-frame mask while it is being tracked, without increasing the runtime. BoLTVOS-ft outperforms PReMVOS, the previously best performing VOS method on DAVIS 2016 and YouTube-VOS, while running up to 45 times faster. Our bounding box tracker also outperforms all previous short-term and longterm trackers on the bounding box level tracking datasets OTB 2015 and LTB35. A newer version of this work can be found at arXiv:1911.12836.
Assessing Capsule Networks With Biased Data
Venue: arXiv cs.CV 2019
Year: 2019

Machine learning based methods achieves impressive results in object classification and detection. Utilizing representative data of the visual world during the training phase is crucial to achieve good performance with such data driven approaches. However, it not always possible to access bias-free datasets thus, robustness to biased data is a desirable property for a learning system. Capsule Networks have been introduced recently and their tolerance to biased data has received little attention. This paper aims to fill this gap and proposes two experimental scenarios to assess the tolerance to imbalanced training data and to determine the generalization performance of a model with unfamiliar affine transformations of the images. This paper assesses dynamic routing and EM routing based Capsule Networks and proposes a comparison with Convolutional Neural Networks in the two tested scenarios. The presented results provide new insights into the behaviour of capsule networks.
A Survey on Software-Defined VANETs: Benefits, Challenges, and Future Directions
Venue: arXiv cs.NI 2019
Year: 2019

The evolving of Fifth Generation (5G) networks isbecoming more readily available as a major driver of the growthof new applications and business models. Vehicular Ad hocNetworks (VANETs) and Software Defined Networking (SDN)represent the key enablers of 5G technology with the developmentof next generation intelligent vehicular networks and applica-tions. In recent years, researchers have focused on the integrationof SDN and VANET, and look at different topics related to thearchitecture, the benefits of software-defined VANET servicesand the new functionalities to adapt them. However, securityand robustness of the complete architecture is still questionableand have been largely negleted. Moreover, the deployment andintegration of novel entities and several architectural componentsdrive new security threats and vulnerabilities.In this paper, first we survey the state-of-the-art SDN basedVehicular ad-hoc Network (SDVN) architectures for their net-working infrastructure design, functionalities, benefits, and chal-lenges. Then we discuss these SDVN architectures against majorsecurity threats that violate the key security services such asavailability, confidentiality, authentication, and data integrity.We also propose different countermeasures to these threats.Finally, we discuss the lessons learned with the directions offuture research work towards provisioning stringent security andprivacy solutions in future SDVN architectures. To the best of ourknowledge, this is the first comprehensive work that presents sucha survey and analysis on SDVNs in the era of future generationnetworks (e.g., 5G, and Information centric networking) andapplications (e.g., intelligent transportation system, and IoT-enabled advertising in VANETs).
Experimental Evaluation of Server Centric Passive Optical Network Based Data Centre Architecture
Venue: arXiv cs.NI 2019
Year: 2019

Passive optical networks (PON) technology has recently been proposed as a solution for scalability, energy efficiency, high capacity, low cost, flexibility and oversubscription issues in data centres. This paper experimentally demonstrates and discusses the implementation of a server centric PON based data centre architecture with high speed and reliability. The architecture is set up using a set of servers grouped into racks directly connected together and to the Optical Line Terminal (OLT) through gateway servers. The switching and routing functionalities have been embedded into servers using 4x10GE Xilinx NetFPGA. Flow continuity has been observed through live video streaming using IP cameras transmitting over up to 110 km optical connections through WDM nodes and the PON network.
Rain O'er Me: Synthesizing real rain to derain with data distillation
Venue: arXiv cs.CV 2019
Year: 2019

We present a supervised technique for learning to remove rain from images without using synthetic rain software. The method is based on a two-stage data distillation approach: 1) A rainy image is first paired with a coarsely derained version using on a simple filtering technique ("rain-to-clean"). 2) Then a clean image is randomly matched with the rainy soft-labeled pair. Through a shared deep neural network, the rain that is removed from the first image is then added to the clean image to generate a second pair ("clean-to-rain"). The neural network simultaneously learns to map both images such that high resolution structure in the clean images can inform the deraining of the rainy images. Demonstrations show that this approach can address those visual characteristics of rain not easily synthesized by software in the usual way.
Automated Search for Configurations of Deep Neural Network Architectures
Venue: arXiv cs.LG 2019
Year: 2019

Deep Neural Networks (DNNs) are intensively used to solve a wide variety of complex problems. Although powerful, such systems require manual configuration and tuning. To this end, we view DNNs as configurable systems and propose an end-to-end framework that allows the configuration, evaluation and automated search for DNN architectures. Therefore, our contribution is threefold. First, we model the variability of DNN architectures with a Feature Model (FM) that generalizes over existing architectures. Each valid configuration of the FM corresponds to a valid DNN model that can be built and trained. Second, we implement, on top of Tensorflow, an automated procedure to deploy, train and evaluate the performance of a configured model. Third, we propose a method to search for configurations and demonstrate that it leads to good DNN models. We evaluate our method by applying it on image classification tasks (MNIST, CIFAR-10) and show that, with limited amount of computation and training, our method can identify high-performing architectures (with high accuracy). We also demonstrate that we outperform existing state-of-the-art architectures handcrafted by ML researchers. Our FM and framework have been released %and are publicly available to support replication and future research.
Privacy protection of occupant behavior data and using blockchain for securely transferring temperature records in HVAC systems
Venue: arXiv cs.CR 2019
Year: 2019

The proportion of Energy consumption in the building industry is great, as well as the amount of cooling and heating system. Scholars have been working on energy conservation of Heating, ventilation, and air-conditioning and other systems in buildings. The application of occupant behavior data for building energy optimization has started gaining attention from scholars. However, occupant behavior data concerns many aspects of occupants' privacy. Different types of occupant behavior data contain occupants' private information to different levels. It is crucial to conduct privacy protection of occupant behavior data when using occupant behavior for energy conservation. This paper presents the aspects of privacy issue when using occupant behavior data, and methods to protect data privacy with blockchain technology. Both two options of using blockchain for privacy protection, sending data records as transactions and storing files on the blockchain, are explained and evaluated with temperature records from an open access paper. Sending data as transactions can be used between sensors and local building management system. While storing files on blockchain can be used for collaboration of different building management systems. Advantages, drawbacks, and potentials of using blockchain for data and file transfer are discussed. The results should be helpful for using occupant behavior data for building energy optimization.
Sizing Storage for Reliable Renewable Integration: A Large Deviations Approach
Venue: arXiv cs.SY 2019
Year: 2019

The inherent intermittency of wind and solar generation presents a significant challenge as we seek to increase the penetration of renewable generation in the power grid. Increasingly, energy storage is being deployed alongside renewable generation to counter this intermittency. However, a formal characterization of the reliability of renewable generators bundled with storage is lacking in the literature. The present paper seeks to fill this gap. We use a Markov modulated fluid queue to model the loss of load probability (LOLP) associated with a renewable generator bundled with a battery, serving an uncertain demand process. Further, we characterize the asymptotic behavior of the LOLP as the battery size scales to infinity. Our results shed light on the fundamental limits of reliability achievable, and also guide the sizing of the storage required in order to meet a given reliability target. Finally, we present a case study using real-world wind power data to demonstrate the applicability of our results in practice.
Bridging between 0/1 and Linear Programming via Random Walks
Venue: arXiv cs.DS 2019
Year: 2019

Under the Strong Exponential Time Hypothesis, an integer linear program with $n$ Boolean-valued variables and $m$ equations cannot be solved in $c^n$ time for any constant $c < 2$. If the domain of the variables is relaxed to $[0,1]$, the associated linear program can of course be solved in polynomial time. In this work, we give a natural algorithmic bridging between these extremes of $0$-$1$ and linear programming. Specifically, for any subset (finite union of intervals) $E \subset [0,1]$ containing $\{0,1\}$, we give a random-walk based algorithm with runtime $O_E((2-\text{measure}(E))^n\text{poly}(n,m))$ that finds a solution in $E^n$ to any $n$-variable linear program with $m$ constraints that is feasible over $\{0,1\}^n$. Note that as $E$ expands from $\{0,1\}$ to $[0,1]$, the runtime improves smoothly from $2^n$ to polynomial. Taking $E = [0,1/k) \cup (1-1/k,1]$ in our result yields as a corollary a randomized $(2-2/k)^{n}\text{poly}(n)$ time algorithm for $k$-SAT. While our approach has some high level resemblance to Schöning's beautiful algorithm, our general algorithm is based on a more sophisticated random walk that incorporates several new ingredients, such as a multiplicative potential to measure progress, a judicious choice of starting distribution, and a time varying distribution for the evolution of the random walk that is itself computed via an LP at each step (a solution to which is guaranteed based on the minimax theorem). Plugging the LP algorithm into our earlier polymorphic framework yields fast exponential algorithms for any CSP (like $k$-SAT, $1$-in-$3$-SAT, NAE $k$-SAT) that admit so-called `threshold partial polymorphisms.'
Universal Lipschitz Approximation in Bounded Depth Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

Adversarial attacks against machine learning models are a rather hefty obstacle to our increasing reliance on these models. Due to this, provably robust (certified) machine learning models are a major topic of interest. Lipschitz continuous models present a promising approach to solving this problem. By leveraging the expressive power of a variant of neural networks which maintain low Lipschitz constants, we prove that three layer neural networks using the FullSort activation function are Universal Lipschitz function Approximators (ULAs). This both explains experimental results and paves the way for the creation of better certified models going forward. We conclude by presenting experimental results that suggest that ULAs are a not just a novelty, but a competitive approach to providing certified classifiers, using these results to motivate several potential topics of further research.
SWNet: Small-World Neural Networks and Rapid Convergence
Venue: arXiv cs.LG 2019
Year: 2019

Training large and highly accurate deep learning (DL) models is computationally costly. This cost is in great part due to the excessive number of trained parameters, which are well-known to be redundant and compressible for the execution phase. This paper proposes a novel transformation which changes the topology of the DL architecture such that it reaches an optimal cross-layer connectivity. This transformation leverages our important observation that for a set level of accuracy, convergence is fastest when network topology reaches the boundary of a Small-World Network. Small-world graphs are known to possess a specific connectivity structure that enables enhanced signal propagation among nodes. Our small-world models, called SWNets, provide several intriguing benefits: they facilitate data (gradient) flow within the network, enable feature-map reuse by adding long-range connections and accommodate various network architectures/datasets. Compared to densely connected networks (e.g., DenseNets), SWNets require a substantially fewer number of training parameters while maintaining a similar level of classification accuracy. We evaluate our networks on various DL model architectures and image classification datasets, namely, CIFAR10, CIFAR100, and ILSVRC (ImageNet). Our experiments demonstrate an average of ~2.1x improvement in convergence speed to the desired accuracy
Black-Box Complexity of the Binary Value Function
Venue: arXiv cs.NE 2019
Year: 2019

The binary value function, or BinVal, has appeared in several studies in theory of evolutionary computation as one of the extreme examples of linear pseudo-Boolean functions. Its unbiased black-box complexity was previously shown to be at most $\lceil \log_2 n \rceil + 2$, where $n$ is the problem size. We augment it with an upper bound of $\log_2 n + 2.42141558 - o(1)$, which is more precise for many values of $n$. We also present a lower bound of $\log_2 n + 1.1186406 - o(1)$. Additionally, we prove that BinVal is an easiest function among all unimodal pseudo-Boolean functions at least for unbiased algorithms.
Asymptotic Optimality of a Time Optimal Path Parametrization Algorithm
Venue: arXiv cs.RO 2019
Year: 2019

Time Optimal Path Parametrization is the problem of minimizing the time interval during which an actuation constrained agent can traverse a given path. Recently, an efficient linear-time algorithm for solving this problem was proposed. However, its optimality was proved for only a strict subclass of problems solved optimally by more computationally intensive approaches based on convex programming. In this paper, we prove that the same linear-time algorithm is asymptotically optimal for all problems solved optimally by convex optimization approaches. We also characterize the optimum of the Time Optimal Path Parametrization Problem, which may be of independent interest.
Context-Aware Embeddings for Automatic Art Analysis
Venue: arXiv cs.CV 2019
Year: 2019

Automatic art analysis aims to classify and retrieve artistic representations from a collection of images by using computer vision and machine learning techniques. In this work, we propose to enhance visual representations from neural networks with contextual artistic information. Whereas visual representations are able to capture information about the content and the style of an artwork, our proposed context-aware embeddings additionally encode relationships between different artistic attributes, such as author, school, or historical period. We design two different approaches for using context in automatic art analysis. In the first one, contextual data is obtained through a multi-task learning model, in which several attributes are trained together to find visual relationships between elements. In the second approach, context is obtained through an art-specific knowledge graph, which encodes relationships between artistic attributes. An exhaustive evaluation of both of our models in several art analysis problems, such as author identification, type classification, or cross-modal retrieval, show that performance is improved by up to 7.3% in art classification and 37.24% in retrieval when context-aware embeddings are used.
An Interactive Musical Prediction System with Mixture Density Recurrent Neural Networks
Venue: arXiv cs.SD 2019
Year: 2019

This paper is about creating digital musical instruments where a predictive neural network model is integrated into the interactive system. Rather than predicting symbolic music (e.g., MIDI notes), we suggest that predicting future control data from the user and precise temporal information can lead to new and interesting interactive possibilities. We propose that a mixture density recurrent neural network (MDRNN) is an appropriate model for this task. The predictions can be used to fill-in control data when the user stops performing, or as a kind of filter on the user's own input. We present an interactive MDRNN prediction server that allows rapid prototyping of new NIMEs featuring predictive musical interaction by recording datasets, training MDRNN models, and experimenting with interaction modes. We illustrate our system with several example NIMEs applying this idea. Our evaluation shows that real-time predictive interaction is viable even on single-board computers and that small models are appropriate for small datasets.
DSNet: An Efficient CNN for Road Scene Segmentation
Venue: arXiv cs.CV 2019
Year: 2019

Road scene understanding is a critical component in an autonomous driving system. Although the deep learning-based road scene segmentation can achieve very high accuracy, its complexity is also very high for developing real-time applications. It is challenging to design a neural net with high accuracy and low computational complexity. To address this issue, we investigate the advantages and disadvantages of several popular CNN architectures in terms of speed, storage and segmentation accuracy. We start from the Fully Convolutional Network (FCN) with VGG, and then we study ResNet and DenseNet. Through detailed experiments, we pick up the favorable components from the existing architectures and at the end, we construct a light-weight network architecture based on the DenseNet. Our proposed network, called DSNet, demonstrates a real-time testing (inferencing) ability (on the popular GPU platform) and it maintains an accuracy comparable with most previous systems. We test our system on several datasets including the challenging Cityscapes dataset (resolution of 1024x512) with an mIoU of about 69.1 % and runtime of 0.0147 second per image on a single GTX 1080Ti. We also design a more accurate model but at the price of a slower speed, which has an mIoU of about 72.6 % on the CamVid dataset.
A Proposal for an Open Logistics Interconnection Reference Model for a Physical Internet
Venue: arXiv cs.DC 2019
Year: 2019

This paper presents a New Open Logistics Interconnection (NOLI) reference model for a Physical Internet, inspired by the Open Systems Interconnection (OSI) reference model for data networks. This NOLI model is compared to the OSI model, and to the Transmission Control Protocol/Internet Protocol (TCP/IP) model of Internet. It is also compared to the OLI model for a Physical Internet proposed by Montreuil. The main differences between the presented NOLI model and all the other models named above are in the appearance of definitions of physical objects in different layers and not just the lowest one. Also, the NOLI model we present locates the containerization and de-containerization operations in the topmost layer, and not in the layer below as does the OLI model. Finally, the NOLI model is closer to the TCP/IP and OSI models than the OLI model, keeping the integrity of the Link Layer that the OLI model divides in two layers, and keeping separate the Session and Transport OSI Layers that the OLI model unites in just one layer.
Cellular UAV-to-UAV Communications
Venue: arXiv cs.IT 2019
Year: 2019

Reliable and direct communication between unmanned aerial vehicles (UAVs) could facilitate autonomous flight, collision avoidance, and cooperation in UAV swarms. In this paper, we consider UAV-to-UAV (U2U) communications underlaying a cellular network, where UAV transmit-receive pairs share the same spectrum with the uplink (UL) of cellular ground users (GUEs). We evaluate the performance of this setup through an analytical framework that embraces realistic height-dependent channel models, antenna patterns, and practical power control mechanisms. Our results demonstrate that, although the presence of U2U communications may worsen the performance of the GUEs, such effect is limited as base stations receive UAV interference through their antenna sidelobes. Moreover, we illustrate that the quality of all links degrades as the UAV height increases---due to a larger number of line-of-sight interferers---, and how the performance of the U2U links can be traded off against that of the GUEs by varying the UAV power control policy.