Abstract

Centrality measures on graphs have found appli- cations in a large number of domains including modeling the spread of an infection/disease, social network analysis, and transportation networks. As a result, parallel algorithms for computing various centrality metrics on graphs are gaining significant research attention in recent years. In this paper, we study parallel algorithms for the percolation centrality measure which extends the betweenness-centrality measure by incorporating a time dependent state variable with every node. We present parallel algorithms that compute the source-based and source-destination variants of the percolation centrality values of nodes in a network. Our algorithms extend the algorithm of Brandes, introduce optimizations aimed at exploiting the structural properties of graphs, and extend the algorithmic techniques introduced by Sariyuce et al. [26] in the context of centrality computation. Experimental studies of our algorithms on an Intel Xeon(R) Silver 4116 CPU and an Nvidia Tesla V100 GPU on a collection of 12 real-world graphs indicate that our algorithmic techniques offer a significant speedup.

Abstract

Quantum walks [1–6] are quantum analogs of random walks on graphs and have widespread applications in several areas of quantum information processing [7]. In particular, they are a universal model for quantum computation and are crucial to the design of quantum algorithms for a plethora of problems such as element distinctness [8,9], searching for a marked state in graphs [10–16], matrix product verification [17], triangle finding [18], group commutativity [19], and many others [20–24]. In fact, for some oracular problems, quantum walks exhibit an exponential speedup over their classical counterparts [21,22]. For several of these algorithms, the runtime strongly depends on the time required for the quantum walk on a graph to localize at a vertex inside a marked set of vertices of interest. In the context of classical random walks, the hitting time is defined as the expected time required to hit a marked vertex. As such, the quantum hitting time characterizes the running time of the underlying quantum algorithm [14,15,20,21,25,26]. For continuous-time quantum walk (CTQW), the Hamiltonian governing the dynamics of the walk encodes the (vertex or edge) connectivity of the underlying graph. The dynamics involves evolving some initial state according to this Hamiltonian for time T , followed by a measurement in the basis spanned by the vertices of the graph, thus finding a target state with a high probability. However, Hamiltonian evolutions are unitary, and therefore, unlike classical random walks, quantum walks never converge to a fixed state with time. One method to address this is to evolve the system by H

Abstract

Indian English (IE), on the surface, seems quite similar to standard English. However, closer observation shows that it has actually been influenced by the surrounding vernacu- lar languages at several levels from phonology to vocabulary and syntax. Due to this, automatic speech recognition (ASR) systems developed for American or British varieties of English result in poor performance on Indian English data. The most prominent feature of Indian English is the characteristic pronunciation of the speakers. The systems are unable to learn these acoustic variations while modelling and cannot parse the non-standard articulation of non-native speakers. For this purpose, we propose a new phone dictionary de- veloped based on the Indian language Com- mon Phone Set (CPS). The dictionary maps the phone set of American English to existing Indian phones based on perceptual similarity. This dictionary is named Indian English Com- mon Phone Set (IE-CPS). Using this, we build an Indian English ASR system and compare its performance with an American English ASR system on speech data of both varieties of En- glish. Our experiments on the IE-CPS show that it is quite effective at modelling the pro- nunciation of the average speaker of Indian En- glish. ASR systems trained on Indian English data perform much better when modelled us- ing IE-CPS, achieving a reduction in the word error rate (WER) of upto 3.95% when used in place of CMUdict. This shows the need for a different lexicon for Indian English.

Abstract

We propose the ViNet architecture for audiovisual saliency prediction. ViNet is a fully convolutional encoder-decoder architecture. The encoder uses visual features from a network trained for action recognition, and the decoder infers a saliency map via trilinear interpolation and 3D convolutions, combining features from multiple hierarchies. The overall architecture of ViNet is conceptually simple; it is causal and runs in real-time (60 fps). ViNet does not use audio as input and still outperforms the state-of-the-art audio-visual saliency prediction models on nine different datasets (three visual-only and six audio-visual datasets). ViNet also surpasses human performance on the CC, SIM and AUC metrics for the AVE dataset, and to our knowledge, it is the first model to do so. We also explore a variation of ViNet architecture by augmenting audio features into the decoder. To our surprise, upon sufficient training, the network becomes agnostic to the input audio and provides the same output irrespective of the input. Interestingly, we also observe similar behaviour in the previous state-of-the-art models [1] for audio-visual saliency prediction. Our findings contrast with previous works on deep learning-based audio-visual saliency prediction, suggesting a clear avenue for future explorations incorporating audio in a more effective manner. The code and pre-trained models are

Abstract

We consider the problem of learning low-rank tensors from partial observations with structural constraints, and propose a novel factorization of such tensors, which leads to a simpler optimization problem. The resulting problem is an optimization problem on manifolds. We develop first-order and second-order Riemannian optimization algorithms to solve it. The duality gap for the resulting problem is derived, and we experimentally verify the correctness of the proposed algorithm. We demonstrate the algorithm on nonnegative constraints and Hankel constraints

Abstract

The paper introduces the novel Modular Pipe Climber III with a Three-Output Open Differential (3-OOD) mechanism to eliminate slipping of the tracks due to the changing cross-sections of the pipe. This will be achieved in any orientation of the robot. Previous pipe climbers use three-wheel/track modules, each with an individual driving mechanism to achieve stable traversing. Slipping of tracks is prevalent in such robots when it encounters the pipe turns. Thus, active control of each module’s speed is employed to mitigate the slip, thereby requiring substantial control effort. The proposed pipe climber implements the 3-OOD to address this issue by allowing the robot to mechanically modulate the track speeds as it encounters a turn. The proposed 3-OOD is the first three-output differential to realize the functional abilities of a traditional two-output differential.

Abstract

In this paper, we explore Probabilistic Inverse Velocity Obstacle (PIVO) as an alternative to probabilistic versions of Velocity Obstacles (PVO) for free flying quadrotor systems. Inverse Velocity Obstacles compute effective controls from a sequence of observations on other agents without the need to access ego state information. As a direct consequence of this the ego state noise is not entailed in probabilistic formulations bringing in verifiable advantages in the form of reduced path lengths, less conservative maneuvers, reduced occurrences of stopping/hovering to let others pass. These advantages are vividly tabulated in this paper, showcasing the efficacy of PIVO as an alternative to probabilistic versions of Velocity Obstacles. In particular we show the benefits of PIVO over PVO in relation to sample complexity as well as overall trajectory lengths. We also show the efficacy of our probabilistic formulation in handling non-parametric and often multimodal noise distributions.

Abstract

Discourse parsing, which involves understand- ing the structure, information flow, and mod- eling the coherence of a given text, is an im- portant task in natural language processing. It forms the basis of several natural language pro- cessing tasks such as question-answering, text summarization, and sentiment analysis. Dis- course unit segmentation is one of the funda- mental tasks in discourse parsing and refers to identifying the elementary units of text that combine to form a coherent text. In this pa- per, we present a transformer based approach towards the automated identification of dis- course unit segments and connectives. Early approaches towards segmentation relied on rule-based systems using POS tags and other syntactic information to identify discourse seg- ments. Recently, transformer based neural sys- tems have shown promising results in this do- main. Our system, SegFormers, employs this transformer based approach to perform multi- lingual discourse segmentation and connective identification across 16 datasets encompassing 11 languages and 3 different annotation frame- works. We evaluate the system based on F1 scores for both tasks, with the best system re- porting the highest F1 score of 97.02% for the treebanked English RST-DT dataset

Abstract

We present our work in using enhanced sampling method of metadynamics in combination with machine learning techniques to speed-up the exploration of all relevantphase space of biomolecular systems that keeps the two related tasks separate: (a) collective variable should cluster configurations into correct states, that is, classify states accurately and (b) collective variable should improve the local sampling in the ‘current free energy basin’, that is, shape the collective variable in line with the data collected (regression). We demonstrate the method on the alanine tetrapeptide system in explicit solvent. We use Elliptic Envelope (EE) classifier to identify outliers from a particular class, and each class will use a different fully-connected autoencoder (ANC) whose bottleneck layer (latent variable) will be used as collective variable in Well-Tempred Metadynamics simulation to generate more data. Comparison against benchmark indicate that the proposed scheme can traverse all relevant phase space

Abstract

Sexism, a prejudice that causes enormous suffering, manifests in blatant as well as subtle ways. As sexist content towards women is increasingly spread on social networks, the automatic detection and categorization of these tweets/posts can help social scientists and policymakers in research, thereby combating sexism. In this paper, we explore the problem of detecting whether a Twitter/Gab post is sexist or not. We further discriminate the detected sexist post into one of the fine-grained sexism categories. We propose a neural model for this sexism detection and classification that can combine representations obtained using RoBERTa model and linguistic features such as Empath, Hurtlex, and Perspective API by involving recurrent components. We also leverage the unlabeled sexism data to infuse the domain-specific transformer model into our framework. Our proposed framework also features a knowledge module comprised of emoticon and hashtag representations to infuse the external knowledge-specific features into the learning process. Several proposed methods outperform various baselines across several standard metrics.