Taxonomy completion is the task of integrating new concepts into an existing taxonomy by determining the appropriate hypernym--hyponym relations. Existing approaches often struggle with the inherent imbalance between leaf and non-leaf edges, which induces bias in representation learning. In this paper, we propose BLEND: B alanced and L eaf- En hanced D ual Fine-Tuning for Taxonomy Completion, a novel framework designed to mitigate this inductive bias. Our method employs independent fine-tuning of two lightweight large language models (LLMs): one optimized with a leaf-focused objective and the other trained with a balanced focused strategy. To further enhance structural understanding, we apply contrastive learning over structure-encoded paths and introduce a combined loss function, enabling more robust representation of hierarchical relations. Extensive experiments on three real-world benchmark datasets demonstrate that BLEND achieves up to 9.32% improvement in recall or hit metrics compared to state-of-the-art approaches. Moreover, BLEND delivers efficient inference while outperforming the latest baseline COMI, highlighting its effectiveness for taxonomy completion tasks.

Abstract Automated program verifiers such as Dafny, F $$^{\star}$$ ⋆ , Verus, and Viper are now routinely used to verify real-world software. Unfortunately, the performance of the SMT solvers employed by these tools is not always able to keep up with the increasing size and complexity of verification problems, resulting in long verification times and verification failures due to time-outs. This performance degradation occurs because large SMT queries increase the search space for the SMT solver, in particular, the number of possible quantifier instantiations. Most existing attempts to mitigate this problem require substantial manual effort to reduce the size of the search space, for instance, by decomposing proofs. In this paper, we present an automatic technique to significantly improve the performance of SMT-based program proofs by drastically reducing the proof search space for each assertion, in particular, the performed quantifier instantiations. Starting from a successful verification, we automatically extract for each assertion the quantified axioms used by the SMT solver to show that the assertion is valid. Crucially, these include lurking axioms , which are logically irrelevant, but needed to trigger the instantiation of other, relevant axioms. We describe a novel proof localization algorithm that implements a semantics-preserving source-to-source translation of a program such that re-verifying an assertion in the optimized program uses only the axioms in its proof essence. This rewriting greatly reduces the possible quantifier instantiations and, thereby, the search space for the SMT solver, such that all future runs of the verifier, for instance as part of continuous integration, are substantially faster. We implemented our algorithm for the Boogie verifier and demonstrated its effectiveness on examples from Dafny and Viper. Specifically, for files with verification times over a minute, we show significant speedups of up to 100–1000 times and no slowdowns. We also provide some evidence that these improvements persist as projects evolve.

Machine Learning (ML) models become vulnerable to Model Stealing Attacks (MSA) when they are deployed as a service. In such attacks, the deployed model is queried repeatedly to build a labelled dataset. This dataset allows the attacker to train a thief model that mimics the original model. To maximize query efficiency, the attacker has to select the most informative subset of data points from the pool of available data. Existing attack strategies utilize approaches like Active Learning and Semi-Supervised learning to minimize costs. However, in the black-box setting, these approaches may select sub-optimal samples as they train only one thief model. Depending on the thief model’s capacity and the data it was pretrained on, the model might even select noisy samples that harm the learning process. In this work, we explore the usage of an ensemble of deep learning models as our thief model. We call our attack Army of Thieves(AOT) as we train multiple models with varying complexities to leverage the crowd’s wisdom. Based on the ensemble’s collective decision, uncertain samples are selected for querying, while the most confident samples are directly included in the training data. Our approach is the first one to utilize an ensemble of thief models to perform model extraction. We outperform the base approaches of existing state-of-the-art methods by at least 3% and achieve a 21% higher adversarial sample transferability than previous work for models trained on the CIFAR-10 dataset. Code is available at: https://github.com/akshitjindal1/AOT_WACV.

Online learning systems have multiple data repositories in the form of transcripts, books and questions. To enable ease of access, such systems organize the content according to a well defined taxonomy of hierarchical nature (subject - chapter -topic). The task of categorizing inputs to the hierarchical labels is usually cast as a flat multi-class classification problem. Such approaches ignore the semantic relatedness between the terms in the input and the tokens in the hierarchical labels. Alternate approaches also suffer from class imbalance when they only consider leaf level nodes as labels. To tackle the issues, we formulate the task as a dense retrieval problem to retrieve the appropriate hierarchical labels for each content. In this paper, we deal with categorizing questions and learning content. We model the hierarchical labels as a composition of their tokens and use an efficient cross-attention mechanism to fuse the information with the term representations of the content. We also adopt an adaptive in-batch hard negative sampling approach which samples better negatives as the training progresses. We demonstrate that the proposed approachTagRec++outperforms existing state-of-the-art approaches on question and learning content datasets as measured by Recall@k. In addition, we demonstrate zero-shot capabilities ofTagRec++and preliminary analysis of it's ability to adapt to label changes.

We propose SCANING, an unsupervised framework for paraphrasing via controlled noise injection. We focus on the novel task of paraphrasing algebraic word problems having practical applications in online pedagogy as a means to reduce plagiarism as well as evoke reasoning capabilities on the part of the student instead of rote memorization. This task is more complex than paraphrasing general-domain corpora due to the difficulty in preserving critical information for solution consistency of the paraphrased word problem, managing the increased length of the text and ensuring diversity in the generated paraphrase. Existing approaches fail to demonstrate adequate performance on at least one, if not all, of these facets, necessitating the need for a more comprehensive solution. To this end, we model the noising search space as a composition of contextual and syntactic aspects to sample noising functions. This allows for learning a denoising function, that operates over both aspects and produces semantically equivalent and syntactically diverse outputs through grounded noise injection. The denoising function serves as a foundation for training a paraphrasing function, which operates solely in the input-paraphrase space without carrying any direct dependency on noise. We demonstrate that SCANING improves performance in terms of producing semantically equivalent and syntactically diverse paraphrases by 35% through extensive automated and human evaluation across 4 datasets.

Multi-document Summarization (MDS) characterizes compressing information from multiple source documents to its succinct summary.An ideal summary should encompass all topics and accurately model cross-document relations expounded upon in the source documents.However, existing systems either impose constraints on the length of tokens during the encoding or falter in capturing the intricate cross-document relationships.These limitations impel the systems to produce summaries that are non-factual and unfaithful, thereby imparting an unfair comprehension of the topic to the readers.To counter these limitations and promote the information equivalence between the source document and generated summary, we propose FABRIC, a novel encoder-decoder model that uses pre-trained BART to comprehensively analyze linguistic nuances, simplicial complex layer to apprehend inherent properties that transcend pairwise associations and sheaf graph attention to effectively capture the heterophilic properties.We benchmark FABRIC with eleven baselines over four widely-used MDS datasets -Multinews, CQASumm, DUC and Opinosis, and show that FABRIC achieves consistent performance improvement across all the evaluation metrics (syntactical, semantical and faithfulness).We corroborate these improvements further through qualitative human evaluation.

The realm of scientific text summarization has experienced remarkable progress due to the availability of annotated brief summaries and ample data. However, the utilization of multiple input modalities, such as videos and audio, has yet to be thoroughly explored. At present, scientific multimodal-input-based text summarization systems tend to employ longer target summaries like abstracts, leading to an underwhelming performance in the task of text summarization.

Social media is awash with hateful content, much of which is often veiled with linguistic and topical diversity. The benchmark datasets used for hate speech detection do not account for such divagation as they are predominantly compiled using hate lexicons. However, capturing hate signals becomes challenging in neutrally-seeded malicious content. Thus, designing models and datasets that mimic the real-world variability of hate warrants further investigation.

Online learning platforms provide diverse questions to gauge the learners' understanding of different concepts. The repository of questions has to be constantly updated to ensure a diverse pool of questions to conduct assessments for learners. However, it is impossible for the academician to manually skim through the large repository of questions to check for duplicates when onboarding new questions from external sources. Hence, we propose a toolQDup in this paper that can surface near-duplicate and semantically related questions without any supervised data. The proposed tool follows an unsupervised hybrid pipeline of statistical and neural approaches for incorporating different nuances in similarity for the task of question duplicate detection. We demonstrate thatQDup can detect near-duplicate questions and also suggest related questions for practice with remarkable accuracy and speed from a large repository of questions. The demo video of the tool can be found at https://www.youtube.com/watch?v=loh0_-7XLW4.

Abstractive text summarization systems using recently improved RNN-based sequence-to-sequence architecture have shown great promise for single-document summarization. However, such neural models fail to perpetuate the performance in the multi-document summarization setting owing to the long-range dependencies within the documents, overlapping/contradicting facts and extrinsic model hallucinations. These shortcomings augment the model to generate inconsistent, repetitive and non-factual summaries. In this work, we introduce REISA, a sequence-to-sequence model with a novelreinforced selective attention spanthat attends over the input and recalibrates the local attention weights to focus on important segments while generating output at each time step. REISA utilizes a reinforcement learning-based policy gradient algorithm to reward the model and formulate attention distributions over the encoder input. We further benchmark REISA on two widely-used multi-document summarization corpora – Multinews and CQASumm, and observe an improvement of$+2.91$and$+6.64$ROUGE-L scores, respectively. The qualitative analyses on semantic similarity by BERTScore, faithfulness by question-answer evaluation and human evaluation show significant improvement over the baseline-generated summaries.

With an increasing outreach of digital platforms in our lives, researchers have taken a keen interest in studying different facets of social interactions. Analyzing the spread of information ( aka diffusion) has brought forth multiple research areas such as modelling user engagement, determining emerging topics, forecasting the virality of online posts and predicting information cascades. Despite such ever-increasing interest, there remains a vacuum among easy-to-use interfaces for large-scale visualization of diffusion models. In this article, we introduce DiVA — Di ffusion V isualization and A nalysis, a tool that provides a scalable web interface and extendable APIs to analyze various diffusion trends on networks. DiVA uniquely offers support for simultaneous comparison of two competing diffusion models and even the comparison with the ground-truth results, which help develop a coherent understanding of real-world scenarios. Along with performing an exhaustive feature comparison and system evaluation of DiVA against publicly-available web interfaces for information diffusion, we conducted a user study to understand the strengths and limitations of DiVA . We noticed that evaluators had a seamless user experience, especially when analyzing diffusion on large networks.

The ubiquity of mobile internet has led to the success of Spatial Crowdsourcing platforms like real-time taxi-hailing services, online food ordering services, etc. A critical component of such services is the task assignment algorithm employed for assigning the tasks to the workers of the platform. Our study of the literature in this domain shows that most of the task assignment algorithms developed for spatial crowdsourcing platforms address the problem from a utilitarian perspective, i.e., they optimise for only kind of entity. In contrast, we address the task assignment problem in spatial crowdsourcing platforms from an egalitarian perspective. An egalitarian approach aims to optimise the expectation of all entities involved. Specifically, we aim to minimise the waiting time for the customers and workers, while maximising the profit earned by the platform. To the best of our knowledge, ours is the only study that achieves this objective in a fully-online setting, with deadlines for both customers and workers. We propose two heuristic algorithms to solve the problem, and evaluate our algorithms on a real taxi-trips records dataset. Our algorithms exhibit a superior performance than the state-of-the-art algorithm for the fully-online bottleneck matching problem with deadlines, in terms of solution quality, running time and response time.

Rajat Agarwal, Varun Khurana, Karish Grover, Mukesh Mohania, Vikram Goyal. Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 2022.

Online hate speech, particularly over microblogging platforms like Twitter, has emerged as arguably the most severe issue of the past decade. Several countries have reported a steep rise in hate crimes infuriated by malicious hate campaigns. While the detection of hate speech is one of the emerging research areas, the generation and spread of topic-dependent hate in the information network remain under-explored. In this work, we focus on exploring user behavior, which triggers the genesis of hate speech on Twitter and how it diffuses via retweets. We crawl a large-scale dataset of tweets, retweets, user activity history, and follower networks, comprising over 161 million tweets from more than 41 million unique users. We also collect over 600k contemporary news articles published online. We characterize different signals of information that govern these dynamics. Our analyses differentiate the diffusion dynamics in the presence of hate from usual information diffusion. This motivates us to formulate the modeling problem in a topic-aware setting with real-world knowledge. For predicting the initiation of hate speech for any given hashtag, we propose multiple feature-rich models, with the best performing one achieving a macro F1 score of 0.65. Meanwhile, to predict the retweet dynamics on Twitter, we propose RETINA, a novel neural architecture that incorporates exogenous influence using scaled dot-product attention. RETINA achieves a macro F1-score of 0.85, outperforming multiple state-of-the-art models. Our analysis reveals the superlative power of RETINA to predict the retweet dynamics of hateful content compared to the existing diffusion models.

Globally, women are cautious when planning their routine travel routes. In a recent survey on street harassment, 82% of international respondents reported taking a different route to their destination than the conventional route due to fear of harassment. Such studies indicate an increasing need for `Safe Routing', especially in developing nations where the lack of infrastructure such as street lights, may contribute to higher crime rates. However, to the best of our knowledge, no state-of-the-art navigation system provides the option of `Safe Routing'. In this work, we propose a novel system that recommends "Safe Routes". Routes recommended by our system balance the conflicting requirements of increasing the safety and constraining the total length of the path to be within a reasonable limit (as desired by the user). From a theoretical perspective, the problem of `Safe Routing' can be modeled as the Arc Orienteering Problem, which is a well-known NP-hard combinatorial optimization problem.

Automatic estimation of relative difficulty of a pair of questions is an important and challenging problem in community question answering (CQA) services. There are limited studies that addressed this problem. Past studies mostly leveraged expertise of users answering the questions and barely considered other properties of CQA services such as metadata of users and posts, temporal information, and textual content. In this article, we propose DiffQue, a novel system that maps this problem to a network-aided edge directionality prediction problem. DiffQue starts by constructing a novel network structure that captures different notions of difficulties among a pair of questions. It then measures the relative difficulty of two questions by predicting the direction of a (virtual) edge connecting these two questions in the network. It leverages features extracted from the network structure, metadata of users/posts, and textual description of questions and answers. Experiments on datasets obtained from two CQA sites (further divided into four datasets) with human annotated ground-truth show that DiffQue outperforms four state-of-the-art methods by a significant margin (28.77% higher F 1 score and 28.72% higher AUC than the best baseline). As opposed to the other baselines, (i) DiffQue appropriately responds to the training noise, (ii) DiffQue is capable of adapting multiple domains (CQA datasets), and (iii) DiffQue can efficiently handle the “cold start” problem that may arise due to the lack of information for newly posted questions or newly arrived users.

Frequent subgraph pattern mining (FSM) finds subgraph patterns that occur in a graph database with a frequency that is more than a given threshold. In FSM, the notion of occurrence captures the presence or absence of a node and an edge in a binary fashion and considers relevance of each edge or node as same. However, an edge or a node may have different relevancy score. Therefore, the utility of a pattern should be defined using the relevance score of participating edges or nodes. This paper defines the utility notion of a pattern using this idea and presents algorithms to mine high-utility patterns from a given graph database. A significant issue in high-utility pattern mining is that the antimonotonic property no longer holds contrary to the FSM. Hence pruning of the search space becomes a daunting task. To address this issue, we incorporate a function to estimate an upper-bound utility of a pattern object that also satisfies the anti-monotonic property. This paper presents three optimization heuristics for the solution on a distributed platform, namely, a novel use of bloom filter to avoid exploration of non-candidates, avoidance of sending database information with each pattern, and avoidance of sending pattern embeddings with each pattern. The experimental study on Apache Spark shows the effectiveness of our proposed optimization strategies.

Time-series of geo-tagged data are routinely generated from GPS enabled devices, satellites and other motion capturing instruments. Such data can be thought of as sequences of locations where every location is associated with additional text annotations. Pattern mining for important sequences (aka. trajectory mining) is essential to extract information from such a database. However, the current trend of anonymization to avoid privacy breach makes it difficult to identify any correlation in the data, thus making it even harder, if not impossible, to look for actual trajectories. Noting this difficulty, we define our goal as mining for trajectory-patterns which is a generalization of trajectories. We first design a pattern-growth based algorithm towards this objective. Further, by identifying the limitation of the state-of-the-art sequential pattern growth algorithms in growing trajectory-patterns, we propose a new pattern growth algorithm-- Mintra. Experiments were performed to demonstrate efficiency and effectiveness of Mintra. We, therefore, show that important patterns can be mined from anonymized data without compromising user privacy.

High-utility itemset mining is an emerging research area in the field of Data Mining. Several algorithms were proposed to find high-utility itemsets from transaction databases and use a data structure called UP-tree for their working. However, algorithms based on UP-tree generate a lot of candidates due to limited information availability in UP-tree for computing utility value estimates of itemsets. In this paper, we present a data structure named UP-Hist tree which maintains a histogram of item quantities with each node of the tree. The histogram allows computation of better utility estimates for effective pruning of the search space. Extensive experiments on real as well as synthetic datasets show that our algorithm based on UP-Hist tree outperforms the state of the art pattern-growth based algorithms in terms of the total number of candidate high utility itemsets generated that needs to be verified.

In presence of a robust privacy infrastructure, an attacker can fulfil his purpose (malafide intension) only by masquerading it with bonafide purposes besides other authentication parameters. We address the issue of masquerading of purpose for a malafide intension by defining the mapping from a malafide intension to bonafide purposes in this paper. An understanding of such a mapping can facilitate both a hacker (assist him in masquerading) and a forensic expert to investigate malafide accesses. Determination of these bonafide purposes may help speed up the violation detection if the user accesses log has listed bonafide purpose with each user access. The bonafide purposes can be determined in data-independent (without accessing the database) or data-dependent (database access is required) mode. In this paper we define a mapping of a malafide intension to bonafide purposes in data-independent mode

When a privacy violation is detected the intension behind the violation is revealed. We refer to this as a malafide intension and the information revealed as the target. The target can be expressed using an SQL-like syntax. In sophisticated privacy attacks the target of the attack may not have been directly accessed but inferred from other pieces of information by exploiting functional dependencies present in the application domain. In this paper we present an efficient algorithm to rewrite the malafide intension query attributes which will return the minimal set of attribute from which the target can be derived. The attribute sets returned by algorithm can derive the target using functional dependencies (algorithm is sound) and furthermore if any minimal set can derive the target using functional dependencies then it will be returned by the algorithm (algorithm is complete).