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

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

We consider a periodic double auction (PDA) wherein the main participants are wholesale suppliers and brokers representing retailers. The suppliers are represented by a composite supply curve and the brokers are represented by individual bids. Additionally, the brokers can also participate in small-scale selling by placing individual asks; hence, they act as prosumers. Specifically, in a PDA, the prosumers who are net buyers have multiple opportunities to buy or sell multiple units of a commodity with the aim of minimising the cost of buying across multiple rounds of the PDA. Formulating optimal bidding strategies for such a PDA setting involves planning across current and future rounds while taking into account the bidding strategies of other agents. In this work, we propose Markov perfect Nash equilibrium (MPNE) policies for a setup where multiple prosumers with knowledge of the composite supply curve compete to procure commodities. Thereafter, the MPNE policies are used to develop an algorithm called MPNE-BBS for the case wherein the prosumers need to re-construct an approximate composite supply curve using past auction information. The efficacy of the proposed algorithm is demonstrated on the PowerTAC wholesale market simulator against several baselines and state-of-the-art bidding policies.

Abstract

Continual learning has primarily focused on the issue of catastrophic forgetting and the associated stability-plasticity tradeoffs. However, little attention has been paid to the efficacy of continually learned representations, as representations are learned alongside classifiers throughout the learning process. Our primary contribution is empirically demonstrating that existing online continually trained deep networks produce inferior representations compared to a simple pre-defined random transforms. Our approach embeds raw pixels using a fixed random transform, approximating an RBF-Kernel initialized before any data is seen. We then train a simple linear classifier on top without storing any exemplars, processing one sample at a time in an online continual learning setting. This method, called RanDumb, significantly outperforms state-of-the-art continually learned representations across all standard online continual learning benchmarks. Our study reveals the significant limitations of representation learning, particularly in low-exemplar and online continual learning scenarios. Extending our investigation to popular exemplar-free scenarios with pretrained models, we find that training only a linear classifier on top of pretrained representations surpasses most continual fine-tuning and prompt-tuning strategies. Overall, our investigation challenges the prevailing assumptions about effective representation learning in online continual learning.

Abstract

This article proposes a framework for adaptive synchronization of uncertain underactuated Euler–Lagrange (EL) agents. The designed distributed controller can handle both state-dependent uncertain system dynamics terms and state-dependent uncertain interconnection terms among neighboring agents. No structural knowledge of such terms is required other than the standard properties of EL systems (positive definite mass matrix, bounded gravity, velocity-dependent friction bound, etc.). The study of stability relies on a suitable analysis of the nonactuated and the actuated synchronization errors, resulting in stable error dynamics perturbed by parametrized state-dependent uncertainty. This uncertainty is tackled via appropriate adaptation laws, giving stability in the uniform ultimate boundedness sense, in line with available literature on state-dependent uncertain system dynamics and/or state-dependent uncertain interconnections. An example with a network of boom cranes is used to validate the proposed approach.