OpenRaiser/Intern-Atlas huggingface dataset:
Efficiently Counting Vertex Orbits of All 5-vertex Subgraphs, by EVOKE
Venue: arXiv cs.SI 2019
Year: 2019

Subgraph counting is a fundamental task in network analysis. Typically, algorithmic work is on total counting, where we wish to count the total frequency of a (small) pattern subgraph in a large input data set. But many applications require local counts (also called vertex orbit counts) wherein, for every vertex $v$ of the input graph, one needs the count of the pattern subgraph involving $v$. This provides a rich set of vertex features that can be used in machine learning tasks, especially classification and clustering. But getting local counts is extremely challenging. Even the easier problem of getting total counts has received much research attention. Local counts require algorithms that get much finer grained information, and the sheer output size makes it difficult to design scalable algorithms. We present EVOKE, a scalable algorithm that can determine vertex orbits counts for all 5-vertex pattern subgraphs. In other words, EVOKE exactly determines, for every vertex $v$ of the input graph and every 5-vertex subgraph $H$, the number of copies of $H$ that $v$ participates in. EVOKE can process graphs with tens of millions of edges, within an hour on a commodity machine. EVOKE is typically hundreds of times faster than previous state of the art algorithms, and gets results on datasets beyond the reach of previous methods. Theoretically, we generalize a recent "graph cutting" framework to get vertex orbit counts. This framework generate a collection of polynomial equations relating vertex orbit counts of larger subgraphs to those of smaller subgraphs. EVOKE carefully exploits the structure among these equations to rapidly count. We prove and empirically validate that EVOKE only has a small constant factor overhead over the best (total) 5-vertex subgraph counter.
CANTO -- Covert AutheNtication with Timing channels over Optimized traffic flows for CAN
Venue: arXiv cs.CR 2019
Year: 2019

Previous research works have endorsed the use of delays and clock skews for detecting intrusions or fingerprinting ECUs on the CAN bus. Similar techniques have been also proposed for establishing a time-covert cryptographic authentication channel, in this way cleverly removing the need for cryptographic material inside the limited payload of CAN frames. The main shortcoming of such works is the limited security level that can be achieved under normal CAN-bus traffic. In this work we endeavour to test the limits of the achievable security level by relying on optimization algorithms for scheduling CAN frames. Under practical bus allocations that are based on real-world scenarios, we are able to extract around 4--5 bits of authentication data from each frame which leads to an efficient intrusion detection and authentication mechanism. By accumulating covert channel data over several consecutive frames, we can achieve higher security levels that are in line with current security demands. To prove the correctness of our approach, we present experiments on state-of-the-art automotive-grade controllers (Infineon Aurix) and bus measurements with the use of industry standard tools, i.e., CANoe.
Conversational implicatures in English dialogue: Annotated dataset
Venue: arXiv cs.CL 2019
Year: 2019

Human dialogue often contains utterances having meanings entirely different from the sentences used and are clearly understood by the interlocutors. But in human-computer interactions, the machine fails to understand the implicated meaning unless it is trained with a dataset containing the implicated meaning of an utterance along with the utterance and the context in which it is uttered. In linguistic terms, conversational implicatures are the meanings of the speaker's utterance that are not part of what is explicitly said. In this paper, we introduce a dataset of dialogue snippets with three constituents, which are the context, the utterance, and the implicated meanings. These implicated meanings are the conversational implicatures. The utterances are collected by transcribing from listening comprehension sections of English tests like TOEFL (Test of English as a Foreign Language) as well as scraping dialogues from movie scripts available on IMSDb (Internet Movie Script Database). The utterances are manually annotated with implicatures.
CAMUS: A Framework to Build Formal Specifications for Deep Perception Systems Using Simulators
Venue: arXiv cs.LG 2019
Year: 2019

The topic of provable deep neural network robustness has raised considerable interest in recent years. Most research has focused on adversarial robustness, which studies the robustness of perceptive models in the neighbourhood of particular samples. However, other works have proved global properties of smaller neural networks. Yet, formally verifying perception remains uncharted. This is due notably to the lack of relevant properties to verify, as the distribution of possible inputs cannot be formally specified. We propose to take advantage of the simulators often used either to train machine learning models or to check them with statistical tests, a growing trend in industry. Our formulation allows us to formally express and verify safety properties on perception units, covering all cases that could ever be generated by the simulator, to the difference of statistical tests which cover only seen examples. Along with this theoretical formulation , we provide a tool to translate deep learning models into standard logical formulae. As a proof of concept, we train a toy example mimicking an autonomous car perceptive unit, and we formally verify that it will never fail to capture the relevant information in the provided inputs.
Shenjing: A low power reconfigurable neuromorphic accelerator with partial-sum and spike networks-on-chip
Venue: arXiv cs.ET 2019
Year: 2019

The next wave of on-device AI will likely require energy-efficient deep neural networks. Brain-inspired spiking neural networks (SNN) has been identified to be a promising candidate. Doing away with the need for multipliers significantly reduces energy. For on-device applications, besides computation, communication also incurs a significant amount of energy and time. In this paper, we propose Shenjing, a configurable SNN architecture which fully exposes all on-chip communications to software, enabling software mapping of SNN models with high accuracy at low power. Unlike prior SNN architectures like TrueNorth, Shenjing does not require any model modification and retraining for the mapping. We show that conventional artificial neural networks (ANN) such as multilayer perceptron, convolutional neural networks, as well as the latest residual neural networks can be mapped successfully onto Shenjing, realizing ANNs with SNN's energy efficiency. For the MNIST inference problem using a multilayer perceptron, we were able to achieve an accuracy of 96% while consuming just 1.26mW using 10 Shenjing cores.
End-to-End Trainable Non-Collaborative Dialog System
Venue: arXiv cs.CL 2019
Year: 2019

End-to-end task-oriented dialog models have achieved promising performance on collaborative tasks where users willingly coordinate with the system to complete a given task. While in non-collaborative settings, for example, negotiation and persuasion, users and systems do not share a common goal. As a result, compared to collaborate tasks, people use social content to build rapport and trust in these non-collaborative settings in order to advance their goals. To handle social content, we introduce a hierarchical intent annotation scheme, which can be generalized to different non-collaborative dialog tasks. Building upon TransferTransfo (Wolf et al. 2019), we propose an end-to-end neural network model to generate diverse coherent responses. Our model utilizes intent and semantic slots as the intermediate sentence representation to guide the generation process. In addition, we design a filter to select appropriate responses based on whether these intermediate representations fit the designed task and conversation constraints. Our non-collaborative dialog model guides users to complete the task while simultaneously keeps them engaged. We test our approach on our newly proposed ANTISCAM dataset and an existing PERSUASIONFORGOOD dataset. Both automatic and human evaluations suggest that our model outperforms multiple baselines in these two non-collaborative tasks.
Deep Image-to-Video Adaptation and Fusion Networks for Action Recognition
Venue: arXiv cs.CV 2019
Year: 2019

Existing deep learning methods for action recognition in videos require a large number of labeled videos for training, which is labor-intensive and time-consuming. For the same action, the knowledge learned from different media types, e.g., videos and images, may be related and complementary. However, due to the domain shifts and heterogeneous feature representations between videos and images, the performance of classifiers trained on images may be dramatically degraded when directly deployed to videos. In this paper, we propose a novel method, named Deep Image-to-Video Adaptation and Fusion Networks (DIVAFN), to enhance action recognition in videos by transferring knowledge from images using video keyframes as a bridge. The DIVAFN is a unified deep learning model, which integrates domain-invariant representations learning and cross-modal feature fusion into a unified optimization framework. Specifically, we design an efficient cross-modal similarities metric to reduce the modality shift among images, keyframes and videos. Then, we adopt an autoencoder architecture, whose hidden layer is constrained to be the semantic representations of the action class names. In this way, when the autoencoder is adopted to project the learned features from different domains to the same space, more compact, informative and discriminative representations can be obtained. Finally, the concatenation of the learned semantic feature representations from these three autoencoders are used to train the classifier for action recognition in videos. Comprehensive experiments on four real-world datasets show that our method outperforms some state-of-the-art domain adaptation and action recognition methods.
Data-driven Network Simulation for Performance Analysis of Anticipatory Vehicular Communication Systems
Venue: arXiv cs.NI 2019
Year: 2019

The provision of reliable connectivity is envisioned as a key enabler for future autonomous driving. Anticipatory communication techniques have been proposed for proactively considering the properties of the highly dynamic radio channel within the communication systems themselves. Since real world experiments are highly time-consuming and lack a controllable environment, performance evaluations and parameter studies for novel anticipatory vehicular communication systems are typically carried out based on network simulations. However, due to the required simplifications and the wide range of unknown parameters (e.g., Mobile Network Operator (MNO)-specific configurations of the network infrastructure), the achieved results often differ significantly from the behavior in real world evaluations. In this paper, we present Data-driven Network Simulation (DDNS) as a novel data-driven approach for analyzing and optimizing anticipatory vehicular communication systems. Different machine learning models are combined for achieving a close to reality representation of the analyzed system's behavior. In a proof of concept evaluation focusing on opportunistic vehicular data transfer, the proposed method is validated against field measurements and system-level network simulation. In contrast to the latter, DDNS does not only provide massively faster result generation, it also achieves a significantly better representation of the real world behavior due to implicit consideration of cross-layer dependencies by the machine learning approach.
Low Cost 3D Printing for Rapid Prototyping and its Application
Venue: arXiv cs.RO 2019
Year: 2019

In the recent years of industrial revolution, 3D printing has shown to grow as an expanding field of new applications. The low cost solutions and short time to market makes it a favorable candidate to be utilized in the dynamic fields of engineering. Additive printing has the vast range of applications in many fields. This study presents the wide range of applications of the 3D printers along with the comparison of the additive printing with the traditional manufacturing methods have been shown. A tutorial is presented explaining the steps involved in the prototype printing using Rhinoceros 3D and Simplify 3D software including the detailed specifications of the end products that were printed using the Delta 3D printer.
Filling Conversation Ellipsis for Better Social Dialog Understanding
Venue: arXiv cs.CL 2019
Year: 2019

The phenomenon of ellipsis is prevalent in social conversations. Ellipsis increases the difficulty of a series of downstream language understanding tasks, such as dialog act prediction and semantic role labeling. We propose to resolve ellipsis through automatic sentence completion to improve language understanding. However, automatic ellipsis completion can result in output which does not accurately reflect user intent. To address this issue, we propose a method which considers both the original utterance that has ellipsis and the automatically completed utterance in dialog act and semantic role labeling tasks. Specifically, we first complete user utterances to resolve ellipsis using an end-to-end pointer network model. We then train a prediction model using both utterances containing ellipsis and our automatically completed utterances. Finally, we combine the prediction results from these two utterances using a selection model that is guided by expert knowledge. Our approach improves dialog act prediction and semantic role labeling by 1.3% and 2.5% in F1 score respectively in social conversations. We also present an open-domain human-machine conversation dataset with manually completed user utterances and annotated semantic role labeling after manual completion.
Discriminative training of conditional random fields with probably submodular constraints
Venue: arXiv cs.LG 2019
Year: 2019

Problems of segmentation, denoising, registration and 3D reconstruction are often addressed with the graph cut algorithm. However, solving an unconstrained graph cut problem is NP-hard. For tractable optimization, pairwise potentials have to fulfill the submodularity inequality. In our learning paradigm, pairwise potentials are created as the dot product of a learned vector w with positive feature vectors. In order to constrain such a model to remain tractable, previous approaches have enforced the weight vector to be positive for pairwise potentials in which the labels differ, and set pairwise potentials to zero in the case that the label remains the same. Such constraints are sufficient to guarantee that the resulting pairwise potentials satisfy the submodularity inequality. However, we show that such an approach unnecessarily restricts the capacity of the learned models. Guaranteeing submodularity for all possible inputs, no matter how improbable, reduces inference error to effectively zero, but increases model error. In contrast, we relax the requirement of guaranteed submodularity to solutions that are probably approximately submodular. We show that the conceptually simple strategy of enforcing submodularity on the training examples guarantees with low sample complexity that test images will also yield submodular pairwise potentials. Results are presented in the binary and muticlass settings, showing substantial improvement from the resulting increased model capacity.
Improving VAE generations of multimodal data through data-dependent conditional priors
Venue: arXiv cs.LG 2019
Year: 2019

One of the major shortcomings of variational autoencoders is the inability to produce generations from the individual modalities of data originating from mixture distributions. This is primarily due to the use of a simple isotropic Gaussian as the prior for the latent code in the ancestral sampling procedure for the data generations. We propose a novel formulation of variational autoencoders, conditional prior VAE (CP-VAE), which learns to differentiate between the individual mixture components and therefore allows for generations from the distributional data clusters. We assume a two-level generative process with a continuous (Gaussian) latent variable sampled conditionally on a discrete (categorical) latent component. The new variational objective naturally couples the learning of the posterior and prior conditionals, and the learning of the latent categories encoding the multimodality of the original data in an unsupervised manner. The data-dependent conditional priors are then used to sample the continuous latent code when generating new samples from the individual mixture components corresponding to the multimodal structure of the original data. Our experimental results illustrate the generative performance of our new model comparing to multiple baselines.
Exposing SED Models And Snapshots Via VO Simulation Artefacts
Venue: arXiv cs.DL 2019
Year: 2019

The Virtual Observatory (VO) simulation standards, Simulation Data Model (SimDM) and Simulation Data Access Layer (SimDAL), establish a framework for the discoverability and dissemination of data created in simulation projects. These standards address the complexity of having a standard access and facade for data which is expected to be multifaceted and, of a diverse range. In this paper, we detail the realisation of an application exposing the theoretical products of one such scientific project via the simulation facades proposed by the VO. The scientific project in question, is a study of the evolution of young clusters in dense molecular clumps. The theoretical products arising from this study include a grid of 20 million SED (Spectral Energy Distribution) models for synthetic young clusters and related data products. Details on the implementation of SimDAL components in the application as well as the ways in which the data structures of SimDM are incorporated onto the existing data products are provided.
Women, politics and Twitter: Using machine learning to change the discourse
Venue: arXiv cs.SI 2019
Year: 2019

Including diverse voices in political decision-making strengthens our democratic institutions. Within the Canadian political system, there is gender inequality across all levels of elected government. Online abuse, such as hateful tweets, leveled at women engaged in politics contributes to this inequity, particularly tweets focusing on their gender. In this paper, we present ParityBOT: a Twitter bot which counters abusive tweets aimed at women in politics by sending supportive tweets about influential female leaders and facts about women in public life. ParityBOT is the first artificial intelligence-based intervention aimed at affecting online discourse for women in politics for the better. The goal of this project is to: $1$) raise awareness of issues relating to gender inequity in politics, and $2$) positively influence public discourse in politics. The main contribution of this paper is a scalable model to classify and respond to hateful tweets with quantitative and qualitative assessments. The ParityBOT abusive classification system was validated on public online harassment datasets. We conclude with analysis of the impact of ParityBOT, drawing from data gathered during interventions in both the $2019$ Alberta provincial and $2019$ Canadian federal elections.
Listing Conflicting Triples in Optimal Time
Venue: arXiv cs.DS 2019
Year: 2019

Different sources of information might tell different stories about the evolutionary history of a given set of species. This leads to (rooted) phylogenetic trees that "disagree" on triples of species, which we call "conflict triples". An important subtask of computing consensus trees which is interesting in its own regard is the enumeration of all conflicts exhibited by a pair of phylogenetic trees (on the same set of $n$ taxa). As it is possible that a significant part of the $n^3$ triples are in conflict, the trivial $Θ(n^3)$-time algorithm that checks for each triple whether it constitutes a conflict, was considered optimal. It turns out, however, that we can do way better in the case that there are only few conflicts. In particular, we show that we can enumerate all d conflict triples between a pair of phylogenetic trees in $O(n + d)$ time. Since any deterministic algorithm has to spend $Θ(n)$ time reading the input and $Θ(d)$ time writing the output, no deterministic algorithm can solve this task faster than we do (up to constant factors).
Voice Search and Typed Search Performance Comparison on Baidu Search System
Venue: arXiv cs.IR 2019
Year: 2019

Although the voice search system is getting more and more developed, some people still have difficulties when searching for information with the voice search system. This paper is a pilot study to compare the search performance of people using voice search and typed search using Baidu search system. We surveyed and interviewed 40 Chinese students who have been using the Baidu search system. Afterward, we analyzed 8 people who had a middle to advanced searching ability by their behaviors, search results, and average query length. We found that there are a lot of variations among the participants' time when searching for different queries, and there were some interesting behaviors that were displayed by a number of participants. We conclude that more participants are needed to make a firm conclusion on the performance comparison between the voice search and typed search.
Analysing Russian Trolls via NLP tools
Venue: arXiv cs.IR 2019
Year: 2019

The fifty-eighth American presidential election in 2016 still arouse fierce controversyat present. A portion of politicians as well as medium and voters believe that theRussian government interfered with the election of 2016 by controlling malicioussocial media accounts on twitter, such as trolls and bots accounts. Both of them willbroadcast fake news, derail the conversations about election, and mislead people.Therefore, this paper will focus on analysing some of the twitter dataset about theelection of 2016 by using NLP methods and looking for some interesting patterns ofwhether the Russian government interfered with the election or not. We apply topicmodel on the given twitter dataset to extract some interesting topics and analysethe meaning, then we implement supervised topic model to retrieve the relationshipbetween topics to category which is left troll or right troll, and analyse the pattern.Additionally, we will do sentiment analysis to analyse the attitude of the tweet. Afterextracting typical tweets from interesting topic, sentiment analysis offers the ability toknow whether the tweet supports this topic or not. Based on comprehensive analysisand evaluation, we find interesting patterns of the dataset as well as some meaningfultopics.
Analyzing resilience of interest-based social networks against node and link failures
Venue: arXiv cs.SI 2019
Year: 2019

In typical online social networks, users are linked by symmetric friend relations and can define circles of friends based on shared interests. In this paper, we look at social networks where users form links subject to both friendships and shared interests. Our goal is to understand resilience of these networks in terms of connectivity when both nodes and links are allowed to fail. We derive a zero-one law as well as the asymptotically exact probability result for connectivity under both node and link failures. The results answer the question of how to set the network parameters such that reliable message dissemination can be achieved. We formally prove the results and confirm the results via experiments as well.