Abstract

Community detection is the problem of identifying natural divisions in networks. Efficient parallel algorithms for identifying such divisions is critical in a number of applications, where the size of datasets have reached significant scales. This paper presents one of the most efficient multicore implementations of the Louvain algorithm, a high quality community detection method. On a server equipped with dual 16-core Intel Xeon Gold 6226R processors, our Louvain, which we term as GVE-Louvain, outperforms Vite, Grappolo, NetworKit Louvain, and cuGraph Louvain (running on NVIDIA A100 GPU) by 50x, 22x, 20x, and 5.8x faster respectively - achieving a processing rate of 560M edges/s on a 3.8B edge graph. In addition, GVE-Louvain improves performance at an average rate of 1.6x for every doubling of threads.

Abstract

PageRank is a widely used centrality measure that assesses the significance of vertices in a graph. Efficiently updating PageRank on dynamic graphs is essential for various applications due to the increasing scale of datasets. This paper introduces our Dynamic Frontier (DF) and Dynamic Frontier with Pruning (DF-P) approaches. Given a batch update comprising edge insertions and deletions, these approaches iteratively identify vertices likely to change their ranks with minimal overhead. On a server featuring a 64-core AMD EPYC-7742 processor, our approaches outperform Static and Dynamic Traversal PageRank by and respectively - on real-world dynamic graphs, and by and on large static graphs with random batch updates. Our approaches scale at a rate of for every doubling of threads.

Abstract

Community detection is the problem of identifying natural divisions in networks. Efficient parallel algorithms for identifying such divisions is critical in a number of applications, where the size of datasets have reached significant scales. This paper presents one of the most efficient implementations of the Leiden algorithm, a high quality community detection method. On a server equipped with dual 16-core Intel Xeon Gold 6226R processors, our Leiden implementation, which we term as GVE-Leiden, outperforms NetworKit Leiden and cuGraph Leiden (running on NVIDIA A100 GPU) by 8.2× and 3.0× respectively — achieving a processing rate of 403M edges/s on a 3.8B edge graph. In addition, GVE-Leiden improves performance at a rate of 1.6× for every doubling of threads.

Abstract

Automatic syllable stress detection methods typically consider syllable-level features as independent. However, as per linguistic studies, there is a dependency among the syllables within a word. In this work, we address this issue by proposing a Post-Net approach using Time-Delay Neural Networks to exploit the syllable dependency in a word for stress detection task. For this, we propose a loss function to incorporate the dependency by ensuring only one stressed syllable in a word. The proposed Post-Net leverages the existing SOTA sequence-independent stress detection models and learns in both supervised and unsupervised settings. We compare the Post-Net with three existing SOTA sequence-independent models and also with sequential model (LSTMs). Experiments conducted on ISLE corpus show the highest relative accuracy improvement of 2.1% and 20.28% with the proposed Post-Net compared to the best sequenceindependent SOTA model in supervised and unsupervised manners, respectively.

Abstract

Automatic syllable stress detection is typically operated at syllable level with stress-related acoustic features. The stress placed on a syllable is influenced not only by its own characteristics but also by its context in the word. However, traditional methods for stress detection overlook the contextual acoustic factors that influence stress placement. By addressing this issue, we study sequential modeling approaches by integrating the syllable dependency for automatic syllable stress detection using a masking strategy. This approach considers a sequence of syllables at the word level and identifies its stress label sequence. We explore various sequential models, such as RNNs, LSTMs, GRUs, and Attention networks. We conduct experiments on the ISLE corpus comprising non-native speakers speaking English. From the experiments, we observe a significant improvement in the performance with all sequential models compared to the state-of-the-art non-sequential baseline (DNN).

Abstract

There have been various attempts at training LLMs to perform deductive reasoning tasks. Some among these show that LLMs behave like humans by displaying content effect, that is, they reason better on reasoning tasks containing rules that align with our everyday beliefs and reason poorly when the rules are belief-violating. On the other hand, there are studies which challenge whether LLMs genuinely reason and attribute their reasoning to artefacts from the training data. In order to make sense of claims concerning genuine reasoning, we introduce a framework developed by Diane Proudfoot’s externalist criteria for machine cognition, which has been inspired by Wittgenstein’s thoughts on rule-following. Based on Wittgenstein's notion that deductive reasoning is normative, we propose the use of Wittgensteinian distinction between genuine rule-following and quasi rule-following as a method to distinguish genuine deductive competence from quasi-competence. In doing so, we also draw attention to the limitations and implications of Proudfoot’s claims regarding machine cognition through the introduction of a thought experiment. This thought experiment enables us to think through Proudfoot’s argument, according to which it is due to pragmatic considerations–and not in principle–that LLMs are unlikely to possess genuine reasoning.

Abstract

We develop three new methods to implement any Linear Combination of Unitaries (LCU), a powerful quantum algorithmic tool with diverse applications. While the standard LCU procedure requires several ancilla qubits and sophisticated multi-qubit controlled operations, our methods consume significantly fewer quantum resources. The first method (Single-Ancilla LCU) estimates expectation values of observables with respect to any quantum state prepared by an LCU procedure while requiring only a single ancilla qubit, and no multi-qubit controlled operations. The second approach (Analog LCU) is a simple, physically motivated, continuous-time analogue of LCU, tailored to hybrid qubit-qumode systems. The third method (Ancilla-free LCU) requires no ancilla qubit at all and is useful when we are interested in the projection of a quantum state (prepared by the LCU procedure) in some subspace of interest. We apply the first two techniques to develop new quantum algorithms for a wide range of practical problems, ranging from Hamiltonian simulation, ground state preparation and property estimation, and quantum linear systems. Remarkably, despite consuming fewer quantum resources they retain a provable quantum advantage. The third technique allows us to connect discrete and continuous-time quantum walks with their classical counterparts. It also unifies the recently developed optimal quantum spatial search algorithms in both these frameworks, and leads to the development of new ones that require fewer ancilla qubits. Overall, our results are quite generic and can be readily applied to other problems, even beyond those considered here.

Abstract

Integrating traffic cameras with deep learning facilitates real-time multi-camera vehicle path reconstruction, benefiting smart city initiatives such as traffic management and public safety. The high demands on latency, bandwidth, and privacy underscore the necessity of edge computing platforms. However, the continuous operation of compute-intensive deep learning algorithms on round-the-clock camera streams can exceed the compute and power capacities of edge data centers. Therefore, it is critical to strategically deploy and activate camera streams to balance compute demands with performance requirements. Currently, there is a lack of tools to support this planning process. This paper presents Seer, a comprehensive suite of tools and algorithms that aids traffic planners in optimizing traffic camera placement and deep learning model deployment, considering compute and budgetary constraints. Seer encompasses (1) a graph-based algorithm for efficient camera placement incorporating road network topology, (2) a collaborative algorithm for vehicle path reconstruction that enables the use of less accurate but resource-efficient deep learning models, and (3) a scalable traffic simulation framework derived from open-source projects that model city road networks. Evaluations of Seer on two real-world road networks, each with thousands of intersections and simulated vehicle paths, show a 6.3x reduction in compute requirements. This is achieved through a combination of sparse camera deployment and the use of lightweight models, with an average 55% increase in the Hausdorff distance for the path reconstruction algorithm, translating to an absolute increase of 135 to 195 meters.

Abstract

Humans excel at forming mental maps of their surroundings, equipping them to understand object relationships and navigate based on language queries. Our previous work SI Maps (Nanwani L, Agarwal A, Jain K, et al. Instance-level semantic maps for vision language navigation. In: 2023 32nd IEEE International Conference on Robot and Human Interactive Communication (RO-MAN). IEEE; 2023 Aug.) showed that having instance-level information and the semantic understanding of an environment helps significantly improve performance for language-guided tasks. We extend this instance-level approach to 3D while increasing the pipeline's robustness and improving quantitative and qualitative results. Our method leverages foundational models for object recognition, image segmentation, and feature extraction. We propose a representation that results in a 3D point cloud map with instance-level embeddings, which bring in the semantic understanding that natural language commands can query. Quantitatively, the work improves upon the success rate of language-guided tasks. At the same time, we qualitatively observe the ability to identify instances more clearly and leverage the foundational models and language and image-aligned embeddings to identify objects that, otherwise, a closed-set approach wouldn't be able to identify.

Abstract

Smart grid system encompasses large power plants in the wholesale market and retail customers in the tariff market. An electricity broker liaises between the wholesale and tariff markets by procuring electricity from the power plants and selling it to subscribed customers. In our work, we address the prominent challenges in the smart grid system to achieve better efficiency. We discuss the wholesale market, for which we design efficient bidding strategies in periodic double auctions (PDAs), and the tariff market, which includes tariff contract generation strategies and peak demand mitigation strategies. We use the PowerTAC simulator as a test-bed; also utilise these strategies for our autonomous broker, VidyutVanika, which has been proven efficient in the PowerTAC tournaments.