Abstract

A graph transactional database (GTD) is a collection of graphs. Frequent Top-k Subgraph Pattern Mining (FTSPM) involves finding the complete set of top-k frequently occurring subgraph patterns in a GTD. Most previous studies focused on finding these patterns in certain graphs by disregarding the crucial information regarding the existential probabilities that may exist between the edges of any two nodes. With this motivation, this paper proposes a novel model to discover top-k (frequently occurring) subgraphs in an uncertain graph transactional database. We introduce a novel algorithm, top-k uncertain subgraph miner (TUSM), to find all top-k subgraphs in the data. We also introduce an approximate top-k uncertain subgraph miner (ATUSM) algorithm to tackle the computational expansiveness of TUSM. Experimental results on synthetic and protein-protein interaction datasets demonstrate that the proposed model finds valuable information and the algorithms are efficient.

Abstract

We develop new algorithms for Quantum Singular Value Transformation (QSVT), a unifying framework underlying a wide range of quantum algorithms. Existing implementations of QSVT rely on block encoding, incurring $O(log L)$ ancilla overhead and circuit depth $widetilde{O}(d lambda L)$ for polynomial transformations of a Hamiltonian $H = sum_{k=1}^L lambda_k H_k$, where $d$ is the polynomial degree, and $lambda = sum_k |lambda_k|$. We introduce a new approach that eliminates block encoding, needs only a single ancilla qubit, and maintains near-optimal complexity, using only basic Hamiltonian simulation methods such as Trotterization. Our method achieves a circuit depth of $widetilde{O}left(L (d lambda_{text{comm}})^{1+o(1)}right)$, without any multi-qubit controlled gates. Here, $lambda_{text{comm}}$ depends on the nested commutators of the $H_k$'s and can be much smaller than $lambda$. Central to our technique is a novel use of Richardson extrapolation, enabling systematic error cancellation in interleaved sequences of arbitrary unitaries and Hamiltonian evolution operators, establishing a broadly applicable framework beyond QSVT. Additionally, we propose two randomized QSVT algorithms for cases with only sampling access to Hamiltonian terms. The first uses qDRIFT, while the second replaces block encodings in QSVT with randomly sampled unitaries. Both achieve quadratic complexity in $d$, which we establish as a lower bound for any randomized method implementing polynomial transformations in this model. Finally, as applications, we develop end-to-end quantum algorithms for quantum linear systems and ground state property estimation, achieving near-optimal complexity without oracular access. Our results provide a new framework for quantum algorithms, reducing hardware overhead while maintaining near-optimal performance, with implications for both near-term and fault-tolerant quantum computing.

Abstract

Puns, as a linguistic phenomenon, hold significant importance in both humor and language comprehension. While extensive research has been conducted in the realm of pun generation in English, there exists a notable gap in the exploration of pun generation within code-mixed text, particularly in Hindi-English code-mixed text. This study addresses this gap by offering a computational method specifically designed to create puns in Hindi-English code-mixed text. In our investigation, we delve into three distinct methodologies aimed at pun generation utilizing pun-alternate word pairs. Furthermore, this novel dataset, HECoP, comprising of 2000 human-annotated sentences serves as a foundational resource for training diverse pun detection models. Additionally, we developed a structured pun generation pipeline capable of generating puns from a single input word without relying on predefined word pairs. Through rigorous human evaluations, our study demonstrates the efficacy of our proposed models in generating code-mixed puns. The findings presented herein lay a solid groundwork for future endeavours in pun generation and computational humor within diverse linguistic contexts.

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 settings has not been previously explored. In this paper, we propose NCwR, a novel approach to node classification in Graph Neural Networks (GNNs) with an integrated reject option. This allows the model to abstain from making predictions when uncertainty is high. We propose cost-based and coverage-based methods for classification with abstention in node classification settings 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 the 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 in which it abstains from predicting and visualizing which part of the input features influenced this decision.

Abstract

Recent evaluations of LLMs on coreference resolution have revealed that traditional output formats and evaluation metrics do not fully capture the models' referential understanding. To address this, we introduce IdentifyMe, a new benchmark for mention resolution presented in a multiple-choice question (MCQ) format, commonly used for evaluating LLMs. IdentifyMe features long narratives and employs heuristics to exclude easily identifiable mentions, creating a more challenging task. The benchmark also consists of a curated mixture of different mention types and corresponding entities, allowing for a fine-grained analysis of model performance. We evaluate both closed- and open source LLMs on IdentifyMe and observe a significant performance gap (20-30%) between the state-of-the-art sub-10B open models vs. closed ones. We observe that pronominal mentions, which have limited surface information, are typically much harder for models to resolve than nominal mentions. Additionally, we find that LLMs often confuse entities when their mentions overlap in nested structures. The highest-scoring model, GPT-4o, achieves 81.9% accuracy, highlighting the strong referential capabilities of state-of-the-art LLMs while also indicating room for further improvement

Abstract

Parkinson’s Disease (PD) neurodegenerative disorder which lacks reliable early diagnostic tests. In this study, we present a method for PD prediction that uses multimodal data from the Parkinson Progression Marker Initiative (PPMI), specifically clinico-demographic, biospecimen, and genetic data, to improve predictive accuracy and facilitate timely interventions via a multimodal machine learning approach. We evaluated data obtained from 598 participants (171 healthy controls and 427 PD patients) in three different modalities: 29 clinical features, five cerebrospinal fluid biomarkers, and 154 SNPs (single nucleotide polymorphisms), which were selected through a biology-driven feature selection method. We utilized three multimodal integration strategies—early, intermediate, and late—and trained various machine learning models, including LightGBM and Multilayer Perceptron (MLP), each of which was optimized by hyperparameter tuning and cross-validation. In early integration, we combined feature sets from all modalities into a single set, leveraging complementary information to increase predictive power. The intermediate integration method made use of autoencoders to encode features into a single 12 dimensional vector as the input into a Neural Network classifier. Late integration combined outputs from the top-performing models for each modality using ensemble techniques such as Voting Classifier and Stacking. We found that early integration achieved the highest performance, with Support Vector Machines with 90% accuracy, 0.98 AUC-ROC, 0.99 precision, and 0.93 F1 score. Intermediate integration with the Neural Network classifier followed with an AUC-ROC of 0.84 and an F1-score of 0.85. Our feature importance analysis identified two clinical scores, namely UPSIT (related to sensory decline) and SCOPA (measuring autonomic dysfunction), along with two SNPs (chr4 90755939 A G and chr4 90646886 G A, both previously linked to PD susceptibility) as crucial predictors, emphasizing their well established relevance in PD diagnosis. Early diagnosis and treatment of PD patients are facilitated by the integration of multiple data modalities, which also greatly increases the predicted accuracy for the disease while also providing us with a thorough understanding of its complexity.

Abstract

The constant shifts in social and political contexts, driven by emerging social movements and political events, lead to new forms of hate content and previously unrecognized hate patterns that machine learning models may not have captured. Some recent literature proposes data augmentation-based techniques to enrich existing hate datasets by incorporating samples that reveal new implicit hate patterns. This approach aims to improve the model's performance on out-of-domain implicit hate instances. It is observed, that further addition of more samples for augmentation results in the decrease of the performance of the model. In this work, we propose a Knowledge Transfer-driven Concept Refinement method that distills and refines the concepts related to implicit hate samples through novel prototype alignment and concept losses, alongside data augmentation based on concept activation vectors. Experiments with several publicly available datasets show that incorporating additional implicit samples reflecting new hate patterns through concept refinement enhances the model's performance, surpassing baseline results while maintaining cross-dataset generalization capabilities.

Abstract

The metaverse, a collection of virtual worlds offering a variety of social activities mirroring real-life interactions, is garnering increasing attention. Consequently, the need to ensure security and privacy within these spaces has become paramount. Metaverse users can create multiple avatars, a feature that can be exploited to deceive or threaten others, leading to significant internal security concerns. Additionally, users in the metaverse are susceptible to several external security threats due to the public nature of their communications with service providers.To address these challenges, we propose a novel quantum authentication scheme leveraging blockchain technology, decentralized identifiers, and verifiable credentials. This scheme enables secure identity verification and authentication for metaverse users. By allowing users to independently prove their identity without relying on service providers, the proposed approach mitigates privacy concerns associated with the management of personal information. Furthermore, our scheme achieves mutual authentication between the user and the service provider, while also being resilient against a variety of attacks, including unconditional security breaches, replay attacks, eavesdropping, man-in-the-middle attacks, and impersonation attempts. With a computation time of 17.4608 ms and a communication cost of 872 bits, the suggested protocol outperforms current solutions and provides superior security for the metaverse environment during data transmission and storage. Furthermore, we examine the operational capabilities and security features using the latest technology and techniques.

Abstract

The Ib Valley Coalfield in Odisha, one of India’s major coal-producing regions, has the third-highest coal reserves in the country. The study assesses how mining expansion and associated developments have reshaped the landscape over nearly five decades. Guided by the research goal of quantifying the impacts of coal mining activity on land use and land cover (LULC) changes, the study leverages multi-spectral/multi-temporal satellite imagery from multiple Landsat missions (2, 5, 7, 8, and 9) acquired between 1976 and 2024. The images were processed and divided into six primary LULC classes—Vegetation, Waterbodies, Mining Regions, Settlements, Industries, and Others—which were identified by employing visual interpretation techniques alongside using advanced band indices, namely, Normalized Difference Vegetation Index (NDVI) and Normalized Difference Water Index (NDWI) to validate the actual features on the ground, along with Google Earth Engine for ground truth. Comparative analysis reveals significant shifts in LULC composition over the study period, during which the expansion of coal mining activities emerged as a dominant driver of change. Results show a pronounced expansion in Mining Regions, from 0.12 km² in 1976 to 49.49 km² in 2024, reflecting the increasing dominance of open-cast mining. Concurrently, Settlements grew from 10.67 km² to 97.06 km², underscoring rapid urbanisation. By contrast, Vegetation declined from 1304.08 km² to 1142.14 km², underscoring pressures on natural ecosystems. Waterbodies exhibited modest fluctuations, influenced by reservoir management and rainfall patterns. Moreover, the open land available for agriculture was severely affected as 111.84 km2 of open land was converted into mines, settlements and industries. The transition matrix of the findings highlights the substantial environmental transformations occurring in the Ib Valley Coalfield, which shows how Vegetation experienced significant loss, primarily due to urbanization and mining, indicating ecological stress from human activities. Similarly, the conversion of water bodies into agricultural land highlights the growing human demand for cultivable areas, often resulting in the degradation of natural ecosystems. These land use transitions, particularly the expansion of extractive industries and urban settlements, collectively reflect the mounting pressures of industrialization and urbanization on the region’s ecological balance. This also highlights severe air and water pollution from open-cast mining operations with implications for habitat integrity, water resource management, and regional socio-economic dynamics—environmental assessments. Overall, this study underscores the far-reaching ecological and socio-economic consequences of coal extraction in Ib Valley.

Abstract

Aberrant genome-wide DNA methylation patterns is common in cancers. Understanding how these affect the transcriptome can provide insights into subtype specific development and progression of tumorigenesis. In this study we carried out genome-wide analysis of DNA methylation and gene expression profiles in TCGA-BRCA breast cancer samples to propose a novel set of 35 methylation-based prognostic markers that may provide insights to molecular subtype specific disease stratification. Gene-set enrichment and pathway analysis of the predicted markers using MSigDB and DAVID revealed their role in mammary gland development pathway, various signaling pathways (ERBB2, NOTCH, etc.), and other cancer pathways, and show clear association with genes affected by hormone receptor status. We further show the discriminative power of the proposed DNA methylation signature in classifying breast cancer samples into three molecular subtypes, viz., Luminal, HER2-enriched and Triple Negative. An accuracy of 94.12% and MCC of 0.87 is obtained in stratified 5-fold cross-validation for the three-class classification using SVM-RBF