Abstract

Community detection is the problem of identifying natural divisions in networks. A relevant challenge in this problem is to find communities on rapidly evolving graphs. In this paper, we design efficient community detection algorithms in the batch dynamic setting. First, we present our parallel Dynamic Frontier approach. Given a batch update of edge deletions or insertions, this approach incrementally identifies an approximate set of affected vertices in the graph with minimal overhead. We apply this approach to both Louvain, a high quality, and Label Propagation Algorithm (LPA), a fast static community detection algorithm. Our approach achieves a mean speedup of 7.3× and 6.7×, when applied to Louvain and LPA respectively, compared to our parallel and optimized implementation of Δ-screening, a recently proposed state-of-the-art approach. Finally, we show how to combine Louvain and LPA with the Dynamic Frontier approach to arrive at a hybrid algorithm. This algorithm produces high-quality communities while being 14.6× faster than state-of-the-art, and identifying communities with the same quality score.

Abstract

Graph Neural Networks (GNNs) have emerged as powerful tools for learning representations of graph-structured data, demonstrating remarkable performance across various tasks. Recognising their importance, there has been extensive research focused on explaining GNN predictions, aiming to enhance their interpretability and trustworthiness. However, GNNs and their explainers face a notable challenge: graphs are primarily designed to model pair-wise relationships between nodes, which can make it tough to capture higher-order, multi-node interactions. This characteristic can pose difficulties for existing explainers in fully representing multi-node relationships. To address this gap, we present Framework For Higher-Order Representations In Graph Explanations (FORGE), a framework that enables graph explainers to capture such interactions by incorporating higher-order structures, resulting in more accurate and faithful explanations. Extensive evaluation shows that on average real-world datasets from the GraphXAI benchmark and synthetic datasets across various graph explainers, FORGE improves average explanation accuracy by 1.9x and 2.25x, respectively. We perform ablation studies to confirm the importance of higher-order relations in improving explanations, while our scalability analysis demonstrates FORGE's efficacy on large graphs.

Abstract

Developing Virtual Reality (VR) software products with discrete and incremental requirements is a challenging task for VR practitioners. A domain expert’s assistance plays a key role in VR product completeness, as most VR requirements are abstract or under-specified during the early stages. Slight changes to the requirements can significantly impact the overall flow of the VR software development process. In this paper, we introduce VReqST, a tool for VR requirement analysts to specify requirements for building effective VR software products. It is developed based on a Role-based model template for specifying virtual environments, custom behaviors, VR-specific algorithms, user-flows, action responses, timeline of events, etc. The tool has been developed after several interactions with VR practitioners from industry & academia. We share our insights on the effectiveness of this tool in practice.

Abstract

One of the key tasks in graph learning is node classification. While Graph neural networks have been used for various applications, their adaptivity to reject option setting is not previously explored. In this paper, we propose NCwR, a novel approach to node classification in Graph Neural Networks (GNNs) with an integrated reject option, which allows the model to abstain from making predictions when uncertainty is high. We propose both cost-based and coverage-based methods for classification with abstention in node classification setting using GNNs. We perform experiments using our method on three standard citation network datasets Cora, Citeseer and Pubmed and compare with relevant baselines. We also model the Legal judgment prediction problem on ILDC dataset as a node classification problem where nodes represent legal cases and edges represent citations. We further interpret the model by analyzing the cases that the model abstains from predicting by visualizing which part of the input features influenced this decision.

Abstract

Automated segmentation of medical image volumes promises to reduce costly medical experts’ time for annotation. However, using machine learning for the task is challenging due to variations in imaging modalities and scarcity of patient data. While interactive image segmentation methods and foundational models incorporating user-provided prompts to refine segmentation masks have shown promise, they overlook crucial sequential information between the slices in 3D medical image volumes and videos, resulting in discontinuities in the segmentation results. This paper proposes a new framework that dynamically updates model parameters during inference in a test time training framework using user-provided scribbles. Our framework preserves acquired knowledge from the previous slices of the current medical volume and the training dataset via student-teacher learning. We evaluate our method on diverse CT, MRI, and microscopic cell datasets. Our framework significantly reduces user annotation time by a factor of 6.72×. Compared to other interactive segmentation methods, we reduce the time by a factor of 2.64×. Our method also outperforms prompting foundation models for segmentation by achieving a dice score of 0.9 in 3-4 interactions compared to 5-8 user interactions for the foundation model, significantly reducing annotation time for the CT and MRI volumes.

Abstract

This paper explores the concept of solving implicature in Natural Language Processing (NLP), highlighting its significance in understanding indirect communication. Drawing on foundational theories by Austin, Searle, and Grice, we discuss how implicature extends beyond literal language to convey nuanced meanings. We review existing datasets, including the Pragmatic Understanding Benchmark (PUB), that assess models’ capabilities in recognizing and interpreting implicatures. Despite recent advances in large language models (LLMs), challenges remain in effectively processing implicature due to limitations in training data and the complexities of contextual interpretation. We propose future directions for research, including the enhancement of datasets and the integration of pragmatic reasoning tasks, to improve LLMs’ understanding of implicature and facilitate better human-computer interaction.

Abstract

This research utilises the capabilities of Google Earth Engine, a cloud-based computing platform, to conduct a comprehensive spatiotemporal assessment of the Coringa mangrove. Situated within the Coringa Wildlife Sanctuary in Andhra Pradesh, India, this mangrove – the country's second largest – is evaluated across various timeframes: 1999, 2002, 2007, 2013, 2017, and 2022. ML algorithms – Random Forest and Support Vector Machine with an RBF kernel – are employed. These algorithms analyze band composites derived from Landsat-7 ETM+ (1999, 2002, 2007), Landsat-8 (2013, 2017), and Sentinel-2 MSI (2022) satellite images. This analysis incorporates key spectral indices and utilises two spectral index thresholds for mangrove classification: one derived from established literature that identifies common thresholds at which mangroves typically occur (standard threshold), and the other is a customised threshold obtained from individual spectral index maps, tailored specifically to delineate mangrove areas in the study area (customized threshold). The results show that RF, particularly with the CT, outperforms all other methods, including RF with the ST and SVM with both thresholds, in terms of training and testing accuracy. These findings affirm the effectiveness of RF with the CT approach in accurately differentiating mangrove areas, emphasizing the critical role of threshold selection in enhancing the accuracy and competence of classification methods for mapping mangrove ecosystems.

Abstract

Understanding what makes a video memorable has important applications in advertising or education technology. Towards this goal, we investigate spatio-temporal attention mechanisms underlying video memorability. Different from previous works that fuse multiple features, we adopt a simple CNN+Transformer architecture that enables analysis of spatio-temporal attention while matching state-of-the-art (SoTA) performance on video memorability prediction. We compare model attention against human gaze fixations collected through a small-scale eye-tracking study where humans perform the video memory task. We uncover the following insights: (i) Quantitative saliency metrics show that our model, trained only to predict a memorability score, exhibits similar spatial attention patterns to human gaze, especially for more memorable videos. (ii) The model assigns greater importance to initial frames in a video, mimicking human attention patterns. (iii) Panoptic segmentation reveals that both (model and humans) assign a greater share of attention to things and less attention to stuff as compared to their occurrence probability.

Abstract

Existing research suggests that mountain and plain societies differ due to geographical factors and this study tests this hypothesis by examining the political dynamics of these two types of societies. We perform a quantitative analysis, followed by an exploration of possible qualitative explanations. Duverger’s Law states that single-member plurality electoral systems typically result in two-party dominance. However, India is a well-known exception in the literature due to strong regional parties as it deviates from this trend. For the quantitative analysis, central election data from the Election Commission of India from 1977 to 2014 is used to conduct a temporal analysis. Laakso and Taagepera’s Effective Number of Parties (ENP) metric is calculated by squaring each party’s share of votes or seats, summing these squares and taking the reciprocal. It is used to find the effective political parties that exist in a district considering both their number and vote share. According to Duverger’s Law, the ENP should ideally converge to 2 over time. This analysis reveals that in plains the ENP values are increasing over time (suggesting divergence) whereas mountain regions are gradually converging towards a two-party system. We conduct a one-way ANOVA for each election by grouping the ENP values for mountain and plain districts separately. A statistically significant difference between the ENP values of mountain and plain districts across all elections. For qualitative analysis, James Scott’s concept of Zomia along with different ideas of Zomia presented by Schendel, Schneiderman are discussed and how they might offer an explanation for the observation. Ultimately, the study sheds light on the socio-political distinctions between mountainous and plain regions in India, supporting historical and sociological theories that suggest mountain societies preserve unique political traits.

Abstract

The rapid evolution of Large Language Models (LLMs) have opened new possibilities in automating tasks across the software developing life cycle, including test case generation This paper presents a comparative analysis of six LLMs in the context of generating test cases for technical requirements written in natural language (in this case English). We compare publicly available general purpose LLMs viz., BARD, ChatGPT3.5, Claude, Gemini, ChatGPT4.o (Omni) and Llama3. The generated test cases are tested against a Simulink model created for the corresponding set of requirements. The coverage metrics thus generated are used for a quantitative comparison of the LLMs.