Large language models pretrained on generaldomain corpora often exhibit tokenization inefficiencies when applied to specialized domains.Although continual pretraining for domain adaptation partially alleviate performance degradation, it does not resolve the fundamental vocabulary mismatch.To address this gap, we introduce a targeted parameterefficient domain adaptation approach that combines vocabulary adaptation with pretraining for LLM-based text summarization.Our unified framework augments pretrained tokenizers with domain-specific tokens while selectively replacing under-trained and unreachable tokens to limit parameter growth.We evaluate our approach on Llama-3.1-8B and Qwen2.5-7Bacross legal and medical summarization tasks on a challenge-oriented evaluation protocol focused on expert-driven text and summaries which typically has higher concentration of over-fragmented Out-of-Vocabulary (OOV) words.The vocabulary adaptation algorithm enhances the overall quality of the summarization model by improving semantic similarity between the generated summaries and their references.In addition, the adapted model produces summaries that incorporate more appropriate novel and domain-specific words, leading to improved coherence, relevance, and faithfulness.We further observe that our proposed approach significantly reduce training time by 35 -55% over continual pretraining and reduce parameter counts up to 37% w.r.t expansion-only methods.We make codebase publicly available 1 .

In this work, we expand the multicalibration fairness metric to graph-structured data. Machine learning models, including graph neural networks (GNNs), have been demonstrated to generate unfair results when trained on data containing biases towards certain demographic groups. Consequently, several fairness enhancing methods have been proposed to deal with such biases in the model predictions. To evaluate the performance of these methods, metrics such as demographic parity and equalized odds have been proposed, which aim to ensure equal treatment across groups. However, these metrics do not take into consideration the diverse underlying distribution of the data across the different demographic groups. Hence, fairness is only achieved at the cost of utility. Multicalibration, on the other hand, aims to generate calibrated predictions for each group, thereby providing much stronger fairness guarantees. However, multicalibration is only defined for tabular data. Consequently, in this work, we provide a novel formulation of multicalibration fairness metric for graph-structured data, specifically for the task of link prediction. We demonstrate that the existing fairness enhancing methods are unable to achieve multicalibration, which leads us to define a simple quadratic program-based postprocessing method. Experiments across several real-world datasets demonstrate the effectiveness of our method, consistently outperforming the existing approaches. Our method is model agnostic and can seamlessly adapt to scenarios with single or multiple sensitive attributes.

The proliferation in the use of Online Social Networks has revolutionized information sharing and consumption, leading to the development of advanced techniques such as link prediction, recommendation systems, community detection, node classification, and network representation learning. However, the availability and quality of real-world datasets for testing these algorithms pose challenges. Synthetic signed datasets generated through signed network reconstruction models offer alternatives for algorithm testing and experimentation. This survey presents an overview of state-of-the-art signed network reconstruction modeling techniques, evaluates their performance through rigorous experimental analysis, explores real-world applications, discusses challenges and open research problems, and guides future research efforts in the field. By consolidating knowledge and providing insights into existing models, this survey contributes to advancing the understanding and improvement of signed network reconstruction modeling. Various research papers discussed in this survey along with publicly available links to their codes are available at: https://github.com/Aikta-Arya/Signed-Network-Reconstruction-Modeling .

Marked Temporal Point Process (MTPP) -- the de-facto sequence model for continuous-time event sequences -- historically employed for modeling human-generated action sequences, lack awareness of external stimuli. In this study, we propose a novel framework developed over Transformer Hawkes Process (THP) to incorporate external stimuli in a domain-agnostic manner. Furthermore, we integrate personalization into our framework by employing language model-based representations of user and event descriptions, which is essential for modeling human-generated action sequences. Towards evaluating the efficacy, we put together a comprehensive benchmark comprising 5 datasets (2 novel additions, and 3 repurposed from existing open datasets) harvested from several domains, spanning education, e-commerce, online payment, and discussion forum. On average, we achieve 9.35% gain in type-prediction accuracy and 7.38% reduction in time-prediction RMSE across all datasets over SOTA MTPP baselines. We demonstrate the superior performance of our proposed model through extensive ablations and showcasing its ability to capture complex combinations of external stimuli in a synthetic set up.

Despite continuous advancements in the capabilities of large language models (LLMs), numerical reasoning remains a challenging area.Techniques like chain-of-thought prompting, tree-of-thought prompting, and program-ofthought prompting guide LLMs through intermediate reasoning steps.Although in-context learning with few-shot prompting has improved performance, LLMs still lag behind state-ofthe-art models on financial numerical reasoning datasets such as FinQA and ConvFinQA.In this work, we introduce FINDER, a novel twostep framework, to enhance LLM's capabilities in financial numerical reasoning.The first step utilizes a generative retriever to extract relevant facts from unstructured data, including both text and tables.This is followed by contextaware Program of Thought prompting with dynamic selection of in-context examples.Our model FINDER achieves a new state-of-theart performance on both the FinQA and Con-vFinQA datasets, surpassing previous benchmarks with execution accuracy improvements of 5.98% and 4.05%, respectively.

Ankan Mullick, Sombit Bose, Rounak Saha, Ayan Kumar Bhowmick, Aditya Vempaty, Prasenjit Dey, Ravi Kokku, Pawan Goyal, Niloy Ganguly. Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing. 2025.

Equivariant diffusion models have emerged as the prevailing approach for generat- ing novel crystal materials due to their ability to leverage the physical symmetries of periodic material structures. However, current models do not effectively learn the joint distribution of atom types, fractional coordinates, and lattice structure of the crystal material in a cohesive end-to-end diffusion framework. Also, none of these models work under realistic setups, where users specify the desired characteristics that the generated structures must match. In this work, we introduce TGDMat, a novel text-guided diffusion model designed for 3D periodic material generation. Our approach integrates global structural knowledge through textual descriptions at each denoising step while jointly generating atom coordinates, types, and lattice structure using a periodic-E(3)-equivariant graph neural network (GNN). Extensive experiments using popular datasets on benchmark tasks reveal that TGDMat out- performs existing baseline methods by a good margin. Notably, for the structure prediction task, with just one generated sample, TGDMat outperforms all baseline models, highlighting the importance of text-guided diffusion. Further, in the genera- tion task, TGDMat surpasses all baselines and their text-fusion variants, showcasing the effectiveness of the joint diffusion paradigm. Additionally, incorporating textual knowledge reduces overall training and sampling computational overhead while enhancing generative performance when utilizing real-world textual prompts from experts. Code is available at https://github.com/kdmsit/TGDMat

Soham Poddar, Paramita Koley, Janardan Misra, Niloy Ganguly, Saptarshi Ghosh. Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). 2025.

Recent advances in generative modeling have shown significant promise in designing novel periodic crystal structures. Existing approaches typically rely on either large language models (LLMs) or equivariant denoising models, each with complementary strengths: LLMs excel at handling discrete atomic types but often struggle with continuous features such as atomic positions and lattice parameters, while denoising models are effective at modeling continuous variables but encounter difficulties in generating accurate atomic compositions. To bridge this gap, we propose CrysLLMGen, a hybrid framework that integrates an LLM with a diffusion model to leverage their complementary strengths for crystal material generation. During sampling, CrysLLMGen first employs a fine-tuned LLM to produce an intermediate representation of atom types, atomic coordinates, and lattice structure. While retaining the predicted atom types, it passes the atomic coordinates and lattice structure to a pre-trained equivariant diffusion model for refinement. Our framework outperforms state-of-the-art generative models across several benchmark tasks and datasets. Specifically, CrysLLMGen not only achieves a balanced performance in terms of structural and compositional validity but also generates more stable and novel materials compared to LLM-based and denoising-based models Furthermore, CrysLLMGen exhibits strong conditional generation capabilities, effectively producing materials that satisfy user-defined constraints. Code is available at \url{https://github.com/kdmsit/crysllmgen}

AI is emerging as an efficient companion in medicine. While AI holds promise for reducing the cognitive load of researchers and practitioners, its adoption is often hindered by a lack of trust in new AI advancements. We present sophisticated techniques for developing trustworthy artificial intelligence (AI) models in medicine, bridging breakthroughs in AI research with practical healthcare applications. We will discuss in-depth the four stages (Design, Development, Implementation, and Evaluation) involved in the process of building trustworthy AI models customized for the medical domain. We present various techniques for incorporating important Trustworthy AI principles like data privacy, robustness, explainability, interpretability, medical experts-in-the-loop, and risk assessment while developing AI models for medicine. In contrast to prior tutorials, we make the following two key contributions: (i) While explaining the 'Implementation' stage, we cover various real-world healthcare applications developed as part of research projects in academia in collaboration with medical schools in India and Germany. (ii) By including a health informatics professional as one of the tutorial organizers, we provide a fresh and much-needed perspective on the research challenges and mitigation strategies in building AI models for medicine.

The rapid rise of generative AI (GenAI) technologies has revolutionized the way content is created and disseminated. As a result, highly convincing human-like malicious content including disinformation, misinformation, and propaganda can now be easily produced and distributed across the web. The diversity of generation models combined with various manipulation strategies applied to different modalities presents significant challenges for fact-checking systems and content moderation. To address this issue, we organize a workshop that focuses on harmful content that has been created intentionally (disinformation) and unintentionally (misinformation) in the era of generative AI. The workshop features specialized tracks on multimodal solutions, investigating narratives, trustworthy AI systems, and policy interventions. By bringing together experts from computer science and law, the workshop offers a comprehensive framework for combating fake content online.

In this article, we introduce FairLPG, a framework for ensuring fairness for the task of link prediction in graphs withmultiplesensitive attributes. In the context of link prediction in graphs, the fairness notions of demographic parity and equalized odds try to ensure equalaverage linking probabilityandtrue positive ratesacross different demographic groups consisting of various node pairs. Existing methods for achieving fairness in link prediction only consider a single sensitive attribute, which makes them unsuited for applications where multiple sensitive attributes need to be accounted for. Additionally, considering multiple sensitive attributes in the context of link prediction leads tooverlappingandintersectionalgroups, which further complicates designing such a framework. The proposed framework FairLPG assumes that the link prediction model generates a prediction score for each node pair to form an edge, and formulates a convex optimization problem that minimizes the squared Euclidean distance between the original prediction scores and transformed scores, subject to the fairness constraints. The transformed scores are then utilized for fair link prediction. To the best of our knowledge, this work is the first to handle the case of intersectional sensitive groups in the graph setting. To demonstrate its effectiveness, we deploy FairLPG on several real-world datasets and graph neural network based link prediction models. It either outperforms or performs competitively with existing methods both in terms of fairness and prediction accuracy across all the datasets and link prediction models at the same time being computationally more efficient.

Presents corrections to the paper, (Corrections to “Traffic Count Estimation at Basis Links Without Path Flow and Historic Data”).

Continuous-time models such as Neural ODEs and Neural Flows have shown promising results in analyzing irregularly sampled time series frequently encountered in electronic health records. Based on these models, time series are typically processed with a hybrid of an initial value problem (IVP) solver and a recurrent neural network within the variational autoencoder architecture. Sequentially solving IVPs makes such models computationally less efficient. In this paper, we propose to model time series purely with continuous processes whose state evolution can be approximated directly by IVPs. This eliminates the need for recurrent computation and enables multiple states to evolve in parallel. We further fuse the encoder and decoder with one IVP solver utilizing its invertibility, which leads to fewer parameters and faster convergence. Experiments on three real-world datasets show that the proposed method can systematically outperform its predecessors, achieve state-of-the-art results, and have significant advantages in terms of data efficiency.

Question-answering (QA) on hybrid scientific tabular and textual data deals with scientific information, and relies on complex numerical reasoning. In recent years, while tabular QA has seen rapid progress, understanding their robustness on scientific information is lacking due to absence of any benchmark dataset. To investigate the robustness of the existing state-of-the-art QA models on scientific hybrid tabular data, we propose a new dataset, “SciTabQA”, consisting of 822 question-answer pairs from scientific tables and their descriptions. With the help of this dataset, we assess the state-of-the-art Tabular QA models based on their ability (i) to use heterogeneous information requiring both structured data (table) and unstructured data (text) and (ii) to perform complex scientific reasoning tasks. In essence, we check the capability of the models to interpret scientific tables and text. Our experiments show that “SciTabQA” is an innovative dataset to study question-answering over scientific heterogeneous data. We benchmark three state-of-the-art Tabular QA models, and find that the best F1 score is only 0.462.

The absence of explicitly tailored, accessible annotated datasets for educational purposes presents a notable obstacle for NLP tasks in languages with limited resources. This study initially explores the feasibility of using machine translation (MT) to convert an existing dataset into a Tigrinya dataset in SQuAD format. As a result, we present TIGQA, an expert-annotated dataset containing 2,685 question-answer pairs covering 122 diverse topics such as climate, water, and traffic. These pairs are from 537 context paragraphs in publicly accessible Tigrinya and Biology books. Through comprehensive analyses, we demonstrate that the TIGQA dataset requires skills beyond simple word matching, requiring both single-sentence and multiple-sentence inference abilities. We conduct experiments using state-of-the-art MRC methods, marking the first exploration of such models on TIGQA. Additionally, we estimate human performance on the dataset and juxtapose it with the results obtained from pre-trained models. The notable disparities between human performance and the best model performance underscore the potential for fu- ture enhancements to TIGQA through continued research. Our dataset is freely accessible via the provided link to encourage the research community to address the challenges in the Tigrinya MRC. Keywords: Tigrinya QA dataset, Low resource QA dataset, domain specific QA

Gene transformer models such as Nucleotide Transformer, DNABert, and LOGO are trained to learn optimal gene sequence representations by using the Masked Language Modeling (MLM) training objective over the complete Human Reference Genome. However, the typical tokenization methods employ a basic sliding window of tokens, such as k-mers, that fail to utilize gene-centric semantics. This could result in the (trivial) masking of easily predictable sequences, leading to inefficient MLM training. Time-variant training strategies are known to improve pretraining efficiency in both language and vision tasks. In this work, we focus on using curriculum masking where we systematically increase the difficulty of masked token prediction task by using a Pointwise Mutual Information-based difficulty criterion, as gene sequences lack well-defined semantic units similar to words or sentences of NLP domain. Our proposed Curriculum Masking-based Gene Masking Strategy (CM-GEMS) demonstrates superior representation learning capabilities compared to baseline masking approaches when evaluated on downstream gene sequence classification tasks. We perform extensive evaluation in both few-shot (five datasets) and full dataset settings (Genomic Understanding Evaluation benchmark consisting of 27 tasks). Our findings reveal that CM-GEMS outperforms state-of-the-art models (DNABert-2, Nucleotide transformer, DNABert) trained at 120K steps, achieving similar results in just 10K and 1K steps. We also demonstrate that Curriculum-Learned LOGO (a 2-layer DNABert-like model) can achieve nearly 90% of the state-of-the-art model performance of 120K steps. We will make the models and codes publicly available at https://github.com/roysoumya/curriculum-GeneMask.

Abhilash Nandy, Yash Agarwal, Ashish Patwa, Millon Madhur Das, Aman Bansal, Ankit Raj, Pawan Goyal, Niloy Ganguly. Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing. 2024.

The debate around vaccines has been going on for decades, but the COVID-19 pandemic showed how crucial it is to understand and mitigate anti-vaccine sentiments. While the pandemic may be over, it is still important to understand how the pandemic affected the anti-vaccine discourse, and whether the arguments against non-COVID vaccines have also changed due to the pandemic. This study attempts to answer these questions through a large-scale study of anti-vaccine posts on Twitter. Almost all prior works that utilized social media to understand anti-vaccine opinions considered only the three broad stances of Anti-Vax, Pro-Vax, and Neutral. There has not been any effort to identify the specific reasons/concerns behind the anti-vax sentiments (e.g., side-effects, conspiracy theories, political reasons) on social media at scale. In this work, we propose two novel methods for classifing tweets into 11 different anti-vax concerns -- a discriminative approach (entailment-based) and a generative approach (based on instruction tuning of LLMs) -- which outperform several strong baselines. We then apply this classifier on anti-vaccine tweets posted over a 5-year period (Jan 2018 - Jan 2023) to understand how the COVID-19 pandemic has impacted the anti-vaccine concerns among the masses. We find that the pandemic has made the anti-vaccine discourse far more complex than in the pre-COVID times, and increased the variety of concerns being voiced. Alarmingly, we find that concerns about COVID vaccines are now being projected onto the non-COVID vaccines, thus making more people hesitant in taking them in post-COVID times.

Subhendu Khatuya, Rajdeep Mukherjee, Akash Ghosh, Manjunath Hegde, Koustuv Dasgupta, Niloy Ganguly, Saptarshi Ghosh, Pawan Goyal. Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). 2024.

While automatic summarization techniques have made significant advancements, their primary focus has been on summarizing short news articles or documents that have clear structural patterns like scientific articles or government reports. There has not been much exploration into developing efficient methods for summarizing financial documents, which often contain complex facts and figures. Here, we study the problem of bullet point summarization of long Earning Call Transcripts (ECTs) using the recently released ECTSum dataset. We leverage an unsupervised question-based extractive module followed by a parameter efficient instruction-tuned abstractive module to solve this task. Our proposed model FLANFinBPS achieves new state-of-the-art performances outperforming the strongest baseline with 14.88% average ROUGE score gain, and is capable of generating factually consistent bullet point summaries that capture the important facts discussed in the ECTs. We make the codebase publicly available at https://github.com/subhendukhatuya/FLAN-FinBPS.

GPT-4 demonstrates high accuracy in medical QA tasks, leading with an accuracy of 86.70%, followed by Med-PaLM 2 at 86.50%. However, around 14% of errors remain. Additionally, current works use GPT-4 to only predict the correct option without providing any explanation and thus do not provide any insight into the thinking process and reasoning used by GPT-4 or other LLMs. Therefore, we introduce a new domain-specific error taxonomy derived from collaboration with medical students. Our GPT-4 USMLE Error (G4UE) dataset comprises 4153 GPT-4 correct responses and 919 incorrect responses to the United States Medical Licensing Examination (USMLE) respectively. These responses are quite long (258 words on average), containing detailed explanations from GPT-4 justifying the selected option. We then launch a large-scale annotation study using the Potato annotation platform and recruit 44 medical experts through Prolific, a well-known crowdsourcing platform. We annotated 300 out of these 919 incorrect data points at a granular level for different classes and created a multi-label span to identify the reasons behind the error. In our annotated dataset, a substantial portion of GPT-4's incorrect responses is categorized as a "Reasonable response by GPT-4," by annotators. This sheds light on the challenge of discerning explanations that may lead to incorrect options, even among trained medical professionals. We also provide medical concepts and medical semantic predications extracted using the SemRep tool for every data point. We believe that it will aid in evaluating the ability of LLMs to answer complex medical questions. We make the resources available at https://github.com/roysoumya/usmle-gpt4-error-taxonomy.

Traffic count (or link count) data represents the cumulative traffic in the lanes between two consecutive signalised intersections. Typically, dedicated infrastructure-based sensors are required for link count data collection. The lack of adequate data collection infrastructure leads to lack of link count data for numerous cities, particularly those in low- and middle-income countries. Here, we address the research problem of link count estimation using crowd-sourced trajectory data to reduce the reliance on any dedicated infrastructure. A stochastic queue discharge model is developed to estimate link counts at signalised intersections taking into account the sparsity and low penetration rate (i.e., the percentage of vehicles with known trajectory) brought on by crowdsourcing. The issue of poor penetration rate is tackled by constructing synthetic trajectories entirely from known trajectories. The proposed model further provides a methodology for estimating the delay resulting from the start-up loss time of the vehicles in the queue under unknown traffic conditions. The proposed model is implemented and validated with real-world data at a signalised intersection in Kolkata, India. Validation results demonstrate that the model can estimate link count with an average accuracy score of 82% with a very low penetration rate (not in the city, but at the intersection) of 5.09% in unknown traffic conditions, which is yet to be accomplished in the current state-of-the-art.

While social media platforms play an important role in our daily lives in obtaining the latest news and trends from across the globe, they are known to be prone to widespread proliferation of harmful information in different forms leading to misconceptions among the masses. Accordingly, several prior works have attempted to tag social media posts with labels/classes reflecting their veracity, sentiments, hate content, and so on. However, in order to have a convincing impact, it is important to additionally extract the post snippets on which the labelling decision is based. We call such a post snippet the rationale . These rationales significantly improve human trust and debuggability of the predictions, especially when detecting misinformation or stigmas from social media posts. These rationale spans or snippets are also helpful in post-classification social analysis, such as for finding out the target communities in hate-speech, or for understanding the arguments or concerns against the intake of vaccines. Also it is observed that a post may express multiple notions of misinformation, hate, sentiment, and the like. Thus, the task of determining (one or multiple) labels for a given piece of text, along with the text snippets explaining the rationale behind each of the identified labels is a challenging multi-label, multi-rationale classification task, which is still nascent in the literature. While transformer -based encoder-decoder generative models such as BART and T5 are well suited for the task, in this work we show how a relatively simpler encoder-only discriminative question-answering (QA) model can be effectively trained using simple template-based questions to accomplish the task. We thus propose MuLX-QA and demonstrate its utility in producing (label, rationale span) pairs in two different settings: multi-class (on the HateXplain dataset related to hate speech on social media), and multi-label (on the CAVES dataset related to COVID-19 anti-vaccine concerns). MuLX-QA outperforms heavier generative models in both settings. We also demonstrate the relative advantage of our proposed model MuLX-QA over strong baselines when trained with limited data. We perform several ablation studies, and experiments to better understand the effect of training MuLX-QA with different question prompts, and draw interesting inferences. Additionally, we show that MuLX-QA is effective on social media posts in resource-poor non-English languages as well. Finally, we perform a qualitative analysis of our model predictions and compare them with those of our strongest baseline.

In recent years, graph neural network (GNN) based approaches have emerged as a powerful technique to encode complex topological structure of crystal materials in an enriched repre- sentation space. These models are often supervised in nature and using the property-specific training data, learn relation- ship between crystal structure and different properties like formation energy, bandgap, bulk modulus, etc. Most of these methods require a huge amount of property-tagged data to train the system which may not be available for different prop- erties. However, there is an availability of a huge amount of crystal data with its chemical composition and structural bonds. To leverage these untapped data, this paper presents CrysGNN, a new pre-trained GNN framework for crystalline materials, which captures both node and graph level structural information of crystal graphs using a huge amount of unla- belled material data. Further, we extract distilled knowledge from CrysGNN and inject into different state of the art prop- erty predictors to enhance their property prediction accuracy. We conduct extensive experiments to show that with distilled knowledge from the pre-trained model, all the SOTA algo- rithms are able to outperform their own vanilla version with good margins. We also observe that the distillation process provides significant improvement over the conventional ap- proach of finetuning the pre-trained model. We will release the pre-trained model along with the large dataset of 800K crys- tal graph which we carefully curated; so that the pre-trained model can be plugged into any existing and upcoming models to enhance their prediction accuracy.

In this paper, we consider the problem of global change-point detection in event sequence data, where both the event distributions and change-points are assumed to be unknown. For this problem, we propose a Log-likelihood Ratio based Global Change-point Detector, which observes the entire sequence and detects a prespecified number of change-points. Based on the Transformer Hawkes Process (THP), a well-known neural TPP framework, we develop DCPD, a differentiable change-point detector, along with maintaining distinct intensity and mark predictor for each partition. Further, we propose a sliding-window-based extension of DCPD to improve its scalability in terms of the number of events or change-points with minor sacrifices in performance. Experiments on synthetic datasets explore the effects of run-time, relative complexity, and other aspects of distributions on various properties of our changepoint detectors, namely robustness, detection accuracy, scalability, etc. under controlled environments. Finally, we perform experiments on six real-world temporal event sequences collected from diverse domains like health, geographical regions, etc., and show that our methods either outperform or perform comparably with the baselines.

Passwords are the most common mechanism for authenticating users online. However, studies have shown that users find it difficult to create and manage secure passwords. To that end, passphrases are often recommended as a usable alternative to passwords, which would potentially be easy to remember and hard to guess. However, as we show, user-chosen passphrases fall short of being secure, while state-of-the-art machine-generated passphrases are difficult to remember.

Large-scale language models such as DNABert and LOGO aim to learn optimal gene representations and are trained on the entire Human Reference Genome. However, standard tokenization schemes involve a simple sliding window of tokens like k-mers that do not leverage any gene-based semantics and thus may lead to (trivial) masking of easily predictable sequences, and subsequently inefficient Masked Language Modeling (MLM) training. Therefore, we propose a novel masking algorithm, GENEMASK, for MLM training of gene sequences, where we randomly identify positions in a gene sequence as mask centers and locally select the span around the mask center with the highest Normalized Pointwise Mutual Information (NPMI) to mask. We observe that in the absence of human-understandable semantics in the genomics domain (in contrast, semantic units like words and phrases are inherently available in NLP), GENEMASK-based models substantially outperform the SOTA models (DNABert and LOGO) over four benchmark gene sequence classification datasets in five few-shot settings (10 to 1000-shot). More significantly, the GENEMASK-based DNABert model is trained for less than one-tenth of the number of epochs of the original SOTA model. We also observe a strong correlation between top-ranked PMI tokens and conserved DNA sequence motifs, which may indicate the incorporation of latent genomic information. The codes (including trained models) and datasets are made publicly available at https://github.com/roysoumya/GeneMask.

Machine Learning models have emerged as a powerful tool for fast and accurate prediction of different crystalline properties. Exiting state-of-the-art models rely on a single modality of crystal data i.e crystal graph structure, where they construct multi-graph by establishing edges between nearby atoms in 3D space and apply GNN to learn materials representation. Thereby, they encode local chemical semantics around the atoms successfully but fail to capture important global periodic structural information like space group number, crystal symmetry, rotational information etc, which influence different crystal properties. In this work, we leverage textual descriptions of materials to model global structural information into graph structure and learn a more robust and enriched representation of crystalline materials. To this effect, we first curate a textual dataset for crystalline material databases containing descriptions of each material. Further, we propose CrysMMNet, a simple multi-modal framework, which fuses both structural and textual representation together to generate a joint multimodal representation of crystalline materials. We conduct extensive experiments on two benchmark datasets across ten different properties to show that CrysMMNet outperforms existing state-of-the-art baseline methods with a good margin. We also observe that fusing the textual representation with crystal graph structure provides consistent improvement for all the SOTA GNN models compared to their own vanilla versions. We have shared the textual dataset, that we have curated for both the benchmark material databases, with the community for future use..

Relation classification (sometimes called relation extraction ) requires trustworthy datasets for fine-tuning large language models, as well as for evaluation. Data collection is challenging for Indian languages, because they are syntactically and morphologically diverse, as well as different from resource-rich languages like English. Despite recent interest in deep generative models for Indian languages, relation classification is still not well served by public datasets. In response, we present IndoRE , a dataset with 21K entity- and relation-tagged gold sentences in three Indian languages (Bengali, Hindi, and Telugu), plus English. We start with a multilingual BERT (mBERT)-based system that captures entity span positions and type information, and provides competitive performance on monolingual relation classification. Using this baseline system, we explore transfer mechanisms between languages and the scope to reduce expensive data annotation while achieving reasonable relation extraction performance. Specifically, we (a) study the accuracy-efficiency trade-off between expensive, manually labeled gold instances vs. automatically translated and aligned silver instances to train a relation extractor, (b) device a simple mechanism for budgeted gold data annotation by intelligently converting distant-supervised silver training instances to gold training instances with human annotators using active learning, and finally (c) propose an ensemble model to provide a performance boost over that achieved via limited gold training instances. We release the dataset for future research. 1

This article investigates the dynamics of competition among organizations with unequal expertise. Multiagent reinforcement learning (MARL) has been used to simulate and understand the impact of various incentive schemes designed to offset such inequality. We design Touch-Mark, a game based on well-known multiagent particle environment, where two teams (weak and strong) with unequal but changing skill levels compete against each other. For training such a game, we propose a novel controller-assisted MARL algorithm C-MADDPG, which empowers each agent with an ensemble of policies along with a supervised controller that by selectively partitioning the sample space and triggers intelligent role division among the teammates. Using C-MADDPG as an underlying framework, we propose an incentive scheme for the weak team such that the final rewards of both teams become the same. We find that despite the incentive, the final reward of the weak team falls short of the strong team. On inspecting, we realize that an overall incentive scheme for the weak team does not incentivize the weaker agents within that team to learn and improve. To offset this, we now specially incentivize the weaker player to learn and, as a result, observe that the weak team beyond an initial phase performs at par with the stronger team. The final goal of this article has been to formulate a dynamic incentive scheme that continuously balances the reward of the two teams. This is achieved by devising an incentive scheme enriched with an RL agent, which takes minimum information from the environment.

Traffic counts (or link counts) are defined as cumulative traffic in the lanes between two consecutive intersections on a road network. Established methods of link count estimation assume the availability of count data at a set of basis links: a minimum subset of all the links of a network that still allow complete network traffic count estimation. If traffic count data are missing even at some basis links, current research must introduce additional assumptions, on path flow or historical data, to compensate. In this research, we present an approach to estimate the missing basis link count without the need for historical data or path-flow information, thereby overcoming the limitations of state-of-the-art estimation approaches. We develop a stochastic method using a canonical correlation analysis-based constrained minimization problem for estimation purposes. The proposed method has been validated with real-world link count data collected in Melbourne, Australia, between 2016 to 2019. The validation results indicate that we can achieve an accuracy of up to 90% in the real world, despite the unknown traffic patterns of the estimation period. Depending on the time of day, the modelling strategy selected, and the consistency of input data available at the road intersection, the estimation accuracy varies. The proposed methodology is useful when there is a general shortage of data since there is inadequate infrastructure for data collection in many major cities around the world.

Rajdeep Mukherjee, Abhinav Bohra, Akash Banerjee, Soumya Sharma, Manjunath Hegde, Afreen Shaikh, Shivani Shrivastava, Koustuv Dasgupta, Niloy Ganguly, Saptarshi Ghosh, Pawan Goyal. Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing. 2022.

Convincing people to get vaccinated against COVID-19 is a key societal challenge in the present times. As a first step towards this goal, many prior works have relied on social media analysis to understand the specific concerns that people have towards these vaccines, such as potential side-effects, ineffectiveness, political factors, and so on. Though there are datasets that broadly classify social media posts into Anti-vax and Pro-Vax labels, there is no dataset (to our knowledge) that labels social media posts according to the specific anti-vaccine concerns mentioned in the posts. In this paper, we have curated CAVES, the first large-scale dataset containing about 10k COVID-19 anti-vaccine tweets labelled into various specific anti-vaccine concerns in a multi-label setting. This is also the first multi-label classification dataset that provides explanations for each of the labels. Additionally, the dataset also provides class-wise summaries of all the tweets. We also perform preliminary experiments on the dataset and show that this is a very challenging dataset for multi-label explainable classification and tweet summarization, as is evident by the moderate scores achieved by some state-of-the-art models.

Occurrences of catastrophes such as natural or man-made disasters trigger the spread of rumours over social media at a rapid pace. Presenting a trustworthy and summarized account of the unfolding event in near real-time to the consumers of such potentially unreliable information thus becomes an important task. In this work, we propose MTLTS, the first end-to-end solution for the task that jointly determines the credibility and summary-worthiness of tweets. Our credibility verifier is designed to recursively learn the structural properties of a Twitter conversation cascade, along with the stances of replies towards the source tweet. We then take a hierarchical multi-task learning approach, where the verifier is trained at a lower layer, and the summarizer is trained at a deeper layer where it utilizes the verifier predictions to determine the salience of a tweet. Different from existing disaster-specific summarizers, we model tweet summarization as a supervised task. Such an approach can automatically learn summary-worthy features, and can therefore generalize well across domains. When trained on the PHEME dataset [29], not only do we outperform the strongest baselines for the auxiliary task of verification/rumour detection, we also achieve 21 - 35% gains in the verified ratio of summary tweets, and 16 - 20% gains in ROUGE1-F1 scores over the existing state-of-the-art solutions for the primary task of trustworthy summarization.

Recently, almost all conferences have moved to virtual mode due to the pandemic-induced restrictions on travel and social gathering. Contrary to in-person conferences, virtual conferences face the challenge of efficiently scheduling talks, accounting for the availability of participants from different timezones and their interests in attending different talks. A natural objective for conference organizers is to maximize efficiency, e.g., total expected audience participation across all talks. However, we show that optimizing for efficiency alone can result in an unfair virtual conference schedule, where individual utilities for participants and speakers can be highly unequal. To address this, we formally define fairness notions for participants and speakers, and derive suitable objectives to account for them. As the efficiency and fairness objectives can be in conflict with each other, we propose a joint optimization framework that allows conference organizers to design schedules that balance (i.e., allow trade-offs) among efficiency, participant fairness and speaker fairness objectives. While the optimization problem can be solved using integer programming to schedule smaller conferences, we provide two scalable techniques to cater to bigger conferences. Extensive evaluations over multiple real-world datasets show the efficacy and flexibility of our proposed approaches.

We propose modeling signed networks by considering two layers in a social network for generation of positive and negative links where both the layers comprise of identical set of nodes. The growth process is modeled based on preferential attachment, formation of links probabilistically asserting structural balance of local groups, and internal growth which happens without addition of new nodes. We prove that the degree distribution of a generated network follows a power-law whose exponent depends on the largest eigenvalue of a matrix which governs the dynamics of growth of degrees of nodes with respect to positive and negative links. A computable formula for average degree and lower-bounds for the number of balanced and unbalanced triads of modelled networks are also obtained. A method for structural reconstruction of real signed networks is formulated through estimation the values of the model parameters to generate the network that can inherit different structural properties of the corresponding real network. Experimental results show that our model which we term as 2L-SNM can replicate properties of several real world signed networks much more robustly than competitive state-of-the-art techniques.

Many online platforms today (such as Amazon, Netflix, Spotify, LinkedIn, and AirBnB) can be thought of as two-sided markets with producers and customers of goods and services. Traditionally, recommendation services in these platforms have focused on maximizing customer satisfaction by tailoring the results according to the personalized preferences of individual customers. However, our investigation reinforces the fact that such customer-centric design of these services may lead to unfair distribution of exposure to the producers, which may adversely impact their well-being. However, a pure producer-centric design might become unfair to the customers. As more and more people are depending on such platforms to earn a living, it is important to ensure fairness to both producers and customers. In this work, by mapping a fair personalized recommendation problem to a constrained version of the problem of fairly allocating indivisible goods, we propose to provide fairness guarantees for both sides. Formally, our proposed FairRec algorithm guarantees Maxi-Min Share of exposure for the producers, and Envy-Free up to One Item fairness for the customers. Extensive evaluations over multiple real-world datasets show the effectiveness of FairRec in ensuring two-sided fairness while incurring a marginal loss in overall recommendation quality. Finally, we present a modification of FairRec (named as FairRecPlus ) that at the cost of additional computation time, improves the recommendation performance for the customers, while maintaining the same fairness guarantees.

Bidisha Samanta, Mohit Agrawal, NIloy Ganguly. Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). 2021.

Online medical forums have become a predominant platform for answering health-related information needs of consumers. However, with a significant rise in the number of queries and the limited availability of experts, it is necessary to automatically classify medical queries based on a consumer's intention, so that these questions may be directed to the right set of medical experts. Here, we develop a novel medical knowledge-aware BERT-based model (MedBERT) that explicitly gives more weightage to medical concept-bearing words, and utilize domain-specific side information obtained from a popular medical knowledge base. We also contribute a multi-label dataset for the Medical Forum Question Classification (MFQC) task. MedBERT achieves state-of-the-art performance on two benchmark datasets and performs very well in low resource settings.

Relation classification (sometimes called 'ex traction') requires trustworthy datasets for fine tuning large language models, as well as for evaluation.Data collection is challenging for Indian languages, because they are syntacti cally and morphologically diverse, as well as different from resourcerich languages like En glish.Despite recent interest in deep gen erative models for Indian languages, relation classification is still not wellserved by pub lic data sets.In response, we present IndoRE, a dataset with 21K entity and relationtagged gold sentences in three Indian languages, plus English.We start with a multilingual BERT (mBERT) based system that captures entity span positions and type information, and pro vides competitive monolingual relation clas sification.Using this system, we explore and compare transfer mechanisms between lan guages.In particular, we study the accuracy efficiency tradeoff between expensive gold in stances vs. translated and aligned 'silver' in stances.We release the dataset for future re search. 1

Training vision-based Autonomous driving models is a challenging problem with enormous practical implications. One of the main challenges is the requirement of storage and processing of vast volumes of (possibly redundant) driving video data. In this paper, we study the problem of data-efficient training of autonomous driving systems. We argue that in the context of an edge-device deployment, multi-criteria online video frame subset selection is an appropriate technique for developing such frameworks. We study existing convex optimization based solutions and show that they are unable to provide solution with high weightage to loss of selected video frames. We design a novel multi-criteria online subset selection algorithm, TMCOSS, which uses a thresholded concave function of selection variables. Extensive experiments using driving simulator CARLA show that we are able to drop 80% of the frames, while succeeding to complete 100% of the episodes. We also show that TMCOSS improves performance on the crucial affordance "Relative Angle" during turns, on inclusion of bucket-specific relative angle loss (BL), leading to selection of more frames in those parts. TMCOSS also achieves an 80% reduction in number of training video frames, on real-world videos from the standard BDD and Cityscapes datasets, for the tasks of drivable area segmentation, and semantic segmentation.

The stance detection task aims at detecting the stance of a tweet or a text for a target.These targets can be named entities or free-form sentences (claims).Though the task involves reasoning of the tweet with respect to a target, we find that it is possible to achieve high accuracy on several publicly available Twitter stance detection datasets without looking at the target sentence.Specifically, a simple tweet classification model achieved human-level performance on the WT-WT dataset and more than two-third accuracy on various other datasets.We investigate the existence of biases in such datasets to find the potential spurious correlations of sentiment-stance relations and lexical choice associated with the stance category.Furthermore, we propose a new large dataset free of such biases and demonstrate its aptness on the existing stance detection systems.Our empirical findings show much scope for research on the stance detection task and proposes several considerations for creating future stance detection datasets.1

We propose VADEC, a multi-task framework that exploits the correlation between the categorical and dimensional models of emotion representation for better subjectivity analysis. Focusing primarily on the effective detection of emotions from tweets, we jointly train multi-label emotion classification and multi-dimensional emotion regression, thereby utilizing the inter-relatedness between the tasks. Co-training especially helps in improving the performance of the classification task as we outperform the strongest baselines with 3.4%, 11%, and 3.9% gains in Jaccard Accuracy, Macro-F1, and Micro-F1 scores respectively on the AIT dataset [17]. We also achieve state-of-the-art results with 11.3% gains averaged over six different metrics on the SenWave dataset [27]. For the regression task, VADEC, when trained with SenWave, achieves 7.6% and 16.5% gains in Pearson Correlation scores over the current state-of-the-art on the EMOBANK dataset [5] for the Valence (V) and Dominance (D) affect dimensions respectively. We conclude our work with a case study on COVID-19 tweets posted by Indians that further helps in establishing the efficacy of our proposed solution.

Graph-based semi-supervised learning (G-SSL) algorithms have witnessed rapid development and widespread usage across a variety of applications in recent years. However, the theoretical characterisation of the efficacy of such algorithms has remained an under-explored area. We introduce a novel algorithm for G-SSL, CSX, whose objective function extends those of Label Propagation and Expander, two popular G-SSL algorithms. We provide data-dependent generalisation error bounds for all three aforementioned algorithms when they are applied to graphs drawn from a partially labelled extension of a versatile latent space graph generative model. The bounds we obtain enable us to characterise the predictive performance as measured by accuracy in terms of homophily and label quantity. Building on this we develop a key notion of GLM-safety which enables us to compare G-SSL algorithms on the basis of the range of graphs on which they obtain a guaranteed accuracy. We show that the proposed algorithm CSX has a better GLM-safety profile than Label Propagation and Expander while achieving comparable or better accuracy on synthetic as well as real-world benchmark networks.

Smartphones provide the capability to perform in-situ sampling of human behavior using Experience Sampling Method (ESM). Designing an ESM schedule involves probing the user repeatedly at suitable moments to collect self-reports. Timely probe generation to collect high fidelity user responses while keeping probing rate low is challenging. In mobile-based ESM, timeliness of the probe is also impacted by user's availability to respond to self-report request. Thus, a good ESM design must consider -probing frequency,timely self-report collection, andnotifying at opportune momentto ensure highresponse quality. We propose a two-phase ESM design, where the first phase (a) balances between probing frequency and self-report timeliness, and (b) in parallel, constructs a predictive model to identify opportune probing moments. The second phase uses this model to further improve response quality by eliminating inopportune probes. We use typing-based emotion detection in smartphone as a case study to validate proposed ESM design. Our results demonstrate that it reduces probing rate by 64 percent, samples self-reports timely by reducing elapsed time between self-report collection, and event trigger by 9 percent while detecting inopportune moments with an average accuracy of 89 percent. These design choices improve the response quality, as manifested by 96 percent valid response collection and a maximum improvement of 24 percent in emotion classification accuracy.

The networked opinion diffusion in online social networks is often governed by the two genres of opinions— endogenous opinions that are driven by the influence of social contacts among users, and exogenous opinions which are formed by external effects like news and feeds. Accurate demarcation of endogenous and exogenous messages offers an important cue to opinion modeling, thereby enhancing its predictive performance. In this article, we design a suite of unsupervised classification methods based on experimental design approaches, in which, we aim to select the subsets of events which minimize different measures of mean estimation error. In more detail, we first show that these subset selection tasks are NP-Hard. Then we show that the associated objective functions are weakly submodular, which allows us to cast efficient approximation algorithms with guarantees. Finally, we validate the efficacy of our proposal on various real-world datasets crawled from Twitter as well as diverse synthetic datasets. Our experiments range from validating prediction performance on unsanitized and sanitized events to checking the effect of selecting optimal subsets of various sizes. Through various experiments, we have found that our method offers a significant improvement in accuracy in terms of opinion forecasting, against several competitors.

A consumer-dependent (business-to-consumer) organization tends to present itself as possessing a set of human qualities, which is termed the brand personality of the company. The perception is impressed upon the consumer through the content, be it in the form of advertisement, blogs, or magazines, produced by the organization. A consistent brand will generate trust and retain customers over time as they develop an affinity toward regularity and common patterns. However, maintaining a consistent messaging tone for a brand has become more challenging with the virtual explosion in the amount of content that needs to be authored and pushed to the Internet to maintain an edge in the era of digital marketing. To understand the depth of the problem, we collect around 300K web page content from around 650 companies. We develop trait-specific classification models by considering the linguistic features of the content. The classifier automatically identifies the web articles that are not consistent with the mission and vision of a company and further helps us to discover the conditions under which the consistency cannot be maintained. To address the brand inconsistency issue, we then develop a sentence ranking system that outputs the top three sentences that need to be changed for making a web article more consistent with the company’s brand personality.

Decisions are increasingly taken by both humans and machine learning models. However, machine learning models are currently trained for full automation—they are not aware that some of the decisions may still be taken by humans. In this paper, we take a first step towards the development of machine learning models that are optimized to operate under different automation levels. More specifically, we first introduce the problem of ridge regression under human assistance and show that it is NP-hard. Then, we derive an alternative representation of the corresponding objective function as a difference of nondecreasing submodular functions. Building on this representation, we further show that the objective is nondecreasing and satisfies α-submodularity, a recently introduced notion of approximate submodularity. These properties allow a simple and efficient greedy algorithm to enjoy approximation guarantees at solving the problem. Experiments on synthetic and real-world data from two important applications—medical diagnosis and content moderation—demonstrate that the greedy algorithm beats several competitive baselines.

Major online platforms today can be thought of as two-sided markets with producers and customers of goods and services. There have been concerns that over-emphasis on customer satisfaction by the platforms may affect the well-being of the producers. To counter such issues, few recent works have attempted to incorporate fairness for the producers. However, these studies have overlooked an important issue in such platforms -- to supposedly improve customer utility, the underlying algorithms are frequently updated, causing abrupt changes in the exposure of producers. In this work, we focus on the fairness issues arising out of such frequent updates, and argue for incremental updates of the platform algorithms so that the producers have enough time to adjust (both logistically and mentally) to the change. However, naive incremental updates may become unfair to the customers. Thus focusing on recommendations deployed on two-sided platforms, we formulate an ILP based online optimization to deploy changes incrementally in η steps, where we can ensure smooth transition of the exposure of items while guaranteeing a minimum utility for every customer. Evaluations over multiple real world datasets show that our proposed mechanism for platform updates can be efficient and fair to both the producers and the customers in two-sided platforms.

Temporal point process (TPP) models have hitherto been moderately good at nowcasting hashtag popularity, but have been very poor at forecasting due to insufficient modeling of Twitter microdynamics. Recent studies have shown that the highly fluctuating nature of hashtag popularity dynamics is due to the influence of two external factors: (i) hashtag-tweet reinforcement and (ii) inter-hashtag competition. In this paper, we propose a marked TPP based on Generative Adversarial Networks (GANs) which can seamlessly incorporate the assistive information necessary to capture the above effects and successfully forecast distant popularity trends. To achieve this, we employ a unique linear semi-autoregressive model for mark generation and couple the time and mark generative aspects. On seven diverse datasets crawled from Twitter covering several real-world events, our model yields remarkably stable performance in predicting hashtag popularity in diverse situations and offers a substantial improvement over the existing state of the art generative models.

With the proliferation of learning scenarios with an abundance of instances, but limited amount of high-quality labels, semi-supervised learning algorithms came to prominence. Graph-based semi-supervised learning (G-SSL) algorithms, of which Label Propagation (LP) is a prominent example, are particularly well-suited for these problems. The premise of LP is the existence of homophily in the graph, but beyond that nothing is known about the efficacy of LP. In particular, there is no characterisation that connects the structural constraints, volume and quality of the labels to the accuracy of LP. In this work, we draw upon the notion of recovery from the literature on community detection, and provide guarantees on accuracy for partially-labelled graphs generated from the Partially-Labelled Stochastic Block Model (PLSBM). Extensive experiments performed on synthetic data verify the theoretical findings.

A wide range of multimodal sensors such as sensors, video cameras, wearables worn by users in an IoT powered smarthome provide important albeit huge amount of data through which applications derive meaningful Activities of Daily Living (ADLs). Storing this massive amount of data is a significant challenge for efficient execution of the corresponding applications to meet real-time demands; there is scope for improving it as it is found that a substantial amount of the data produced may be unimportant. In this paper, we propose an end-to-end system GradeSense, which implements a grading mechanism based on multimodal data fusion by categorizing ‘important’ data. GradeSense is made complete by an applicationindependent storage module that leverages our grading scheme (as opposed to traditional usage-based models) for efficient storing. Activity prediction algorithms perform well (up to 17% improvement) with this now-fused and important data which is a mere fraction of the entire data, achieving 87% data reduction on average in faster storage tier. The throughput of GradeSense, measured through runtime, gives improvement up to 46% due to our enhanced data-categorization and storing mechanism.

The COVID-19 pandemic has made it paramount to maintain social distance to limit the viral transmission probability. At the same time, local businesses (e.g., restaurants, cafes, stores, malls) need to operate to ensure their economic sustainability. Considering the wide usage of local recommendation platforms like Google Local and Yelp by customers to choose local businesses, we propose to design local recommendation systems which can help in achieving both safety and sustainability goals. Our investigation of existing local recommendation systems shows that they can lead to overcrowding at some businesses compromising customer safety, and very low footfall at other places threatening their economic sustainability. On the other hand, naive ways of ensuring safety and sustainability can cause significant loss in recommendation utility for the customers. Thus, we formally express the problem as a multi-objective optimization problem and solve by innovatively mapping it to a bipartite matching problem with polynomial time solutions. Extensive experiments over multiple real-world datasets reveal the efficacy of our approach along with the three-way control over sustainability, safety, and utility goals.

Manually extracting relevant aspects and opinions from large volumes of user-generated text is a time-consuming process. Summaries, on the other hand, help readers with limited time budgets to quickly consume the key ideas from the data. State-of-the-art approaches for multi-document summarization, however, do not consider user preferences while generating summaries. In this work, we argue the need and propose a solution for generating personalized aspect-based opinion summaries from large collections of online tourist reviews. We let our readers decide and control several attributes of the summary such as the length and specific aspects of interest among others. Specifically, we take an unsupervised approach to extract coherent aspects from tourist reviews posted onTripAdvisor. We then propose an Integer Linear Programming (ILP) based extractive technique to select an informative subset of opinions around the identified aspects while respecting the user-specified values for various control parameters. Finally, we evaluate and compare our summaries using crowdsourcing and ROUGE-based metrics and obtain competitive results.

In this paper, we propose a Multi-View Learning (MVL) framework for news recommendation which uses both the content view and the user-news interaction graph view. In the content view, we use a news encoder to learn news representations from different information like titles, bodies and categories. We obtain representation of user from his/her browsed news conditioned on the candidate news article to be recommended. In the graph-view, we propose to use a graph neural network to capture the user-news, user-user and news-news relatedness in the user-news bipartite graphs by modeling the interactions between different users and news. In addition, we propose to incorporate attention mechanism into the graph neural network to model the importance of these interactions for more informative representation learning of user and news. Experiments on a real world dataset validate the effectiveness of MVL.

This paper tackles the problem of detecting a comprehensive set of sensor faults that can occur in IoT-instrumented smart homes customized to infer Activities of Daily Living (ADL) from the activation of sensor sets. Specifically, sensors can suffer faults that (a) span durations that vary between several seconds to hours, (b) can result in both missing or false-alarm sensor-events. Previous fault detection approaches are geared primarily to identify missing faults (absence of sensor readings) of a permanent (very long-lived) nature, or sporadic false-alarm events. We propose DetectIF, a fault-detection framework that detects faults of varying time duration, and identifies both missing and false-alarm sensor events. DetectIF's key novelties include developing rules capturing spatiotemporal correlations among sensors and augmenting those rules with statistical properties of such sensor-specific behavior. To test DetectIF under a variety of fault behavior, we develop a unified fault framework where the tuning of a couple of parameters allows us to generate and inject faults of desired type and duration into an underlying sensor stream. Experiments with such comprehensive fault data shows that DetectIF achieves 82-95% fault-detection accuracy, improving precision by a huge amount (33-66%) over competitive, state-of-the-art baselines. Moreover, we demonstrate the benefits of applying DetectIF on unmodified, benchmark smart home datasets: it is able to detect additional likely faults that prior fault detection approaches miss, and thus consequently achieve an average of 30% higher ADL recognition accuracy compared to prior state-of-the-art fault detection techniques.

We investigate the problem of fair recommendation in the context of two-sided online platforms, comprising customers on one side and producers on the other. Traditionally, recommendation services in these platforms have focused on maximizing customer satisfaction by tailoring the results according to the personalized preferences of individual customers. However, our investigation reveals that such customer-centric design may lead to unfair distribution of exposure among the producers, which may adversely impact their well-being. On the other hand, a producer-centric design might become unfair to the customers. Thus, we consider fairness issues that span both customers and producers. Our approach involves a novel mapping of the fair recommendation problem to a constrained version of the problem of fairly allocating indivisible goods. Our proposed FairRec algorithm guarantees at least Maximin Share (MMS) of exposure for most of the producers and Envy-Free up to One Good (EF1) fairness for every customer. Extensive evaluations over multiple real-world datasets show the effectiveness of FairRec in ensuring two-sided fairness while incurring a marginal loss in the overall recommendation quality.

Deep generative models have been praised for their ability to learn smooth latent representations of images, text, and audio, which can then be used to generate new, plausible data. Motivated by these success stories, there has been a surge of interest in developing deep generative models for automated molecule design. However, these models face several difficulties due to the unique characteristics of molecular graphs—their underlying structure is not Euclidean or grid-like, they remain isomorphic under permutation of the nodes’ labels, and they come with a different number of nodes and edges. In this paper, we first propose a novel variational autoencoder for molecular graphs, whose encoder and decoder are specially designed to account for the above properties by means of several technical innovations. Moreover, in contrast with the state of the art, our decoder is able to provide the spatial coordinates of the atoms of the molecules it generates. Then, we develop a gradient-based algorithm to optimize the decoder of our model so that it learns to generate molecules that maximize the value of certain property of interest and, given any arbitrary molecule, it is able to optimize the spatial configuration of its atoms for greater stability. Experiments reveal that our variational autoencoder can discover plausible, diverse and novel molecules more effectively than several state of the art models. Moreover, for several properties of interest, our optimized decoder is able to identify molecules with property values 121% higher than those identified by several state of the art methods based on Bayesian optimization and reinforcement learning.

Although public transport vehicles such as buses have always been an economical means of commuting in the cities of many developing countries, it is always considered as a secondary mode of transport owing to poor infrastructure, chaotic and reckless driving habits, and absence of any proper information system in buses. Based on rigorous experiments carried out over a period of two years and multiple surveys, we have tried to learn the problems faced by bus commuters. As a solution, in this article, we develop a novel energy-efficient system which would help commuters navigate through their journey safely. Along with making them aware of any upcoming points of concerns (PoCs) such as sudden bumps, sharp turns, and bad roads, we also inform commuters about the expected time of arrival at the destination. The system makes use of several landmarks such as speed breakers, turns, and bus stops on a trail stored in a specialized data structure, the probabilistic timed automata. We conducted extensive experiments using 25 volunteers over 50 trails. The system showed an average localization error of only 50 m and mean estimated time of arrival (ETA) error of 2.5 mins and a fairly high alert prediction accuracy while consuming significantly less energy when compared to GPS.

Fashionable outfits are generally created by expert fashionistas, who use their creativity and in-depth understanding of fashion to make attractive outfits. Over the past few years, automation of outfit composition has gained much attention from the research community. Most of the existing outfit recommendation systems focus on pairwise item compatibility prediction (using visual and text features) to score an outfit combination having several items, followed by recommendation of top-n outfits or a capsule wardrobe having a collection of outfits based on user’s fashion taste. However, none of these consider a user’s preference of price range for individual clothing types or an overall shopping budget for a set of items. In this article, we propose a box recommendation framework—BOXREC—which at first collects user preferences across different item types (namely, top-wear, bottom-wear, and foot-wear) including price range of each type and a maximum shopping budget for a particular shopping session. It then generates a set of preferred outfits by retrieving all types of preferred items from the database (according to user specified preferences including price ranges), creates all possible combinations of three preferred items (belonging to distinct item types), and verifies each combination using an outfit scoring framework—BOXREC-OSF. Finally, it provides a box full of fashion items, such that different combinations of the items maximize the number of outfits suitable for an occasion while satisfying maximum shopping budget. We create an extensively annotated dataset of male fashion items across various types and categories (each having associated price) and a manually annotated positive and negative formal as well as casual outfit dataset. We consider a set of recently published pairwise compatibility prediction methods as competitors of BOXREC-OSF. Empirical results show superior performance of BOXREC-OSF over the baseline methods. We found encouraging results by performing both quantitative and qualitative analysis of the recommendations produced by BOXREC. Finally, based on user feedback corresponding to the recommendations given by BOXREC, we show that disliked or unpopular items can be a part of attractive outfits.

Deep generative models have been praised for their ability to learn smooth latent representation of images, text, and audio, which can then be used to generate new, plausible data. However, current generative models are unable to work with molecular graphs due to their unique characteristics—their underlying structure is not Euclidean or grid-like, they remain isomorphic under permutation of the nodes labels, and they come with a different number of nodes and edges. In this paper, we propose NeVAE, a novel variational autoencoder for molecular graphs, whose encoder and decoder are specially designed to account for the above properties by means of several technical innovations. In addition, by using masking, the decoder is able to guarantee a set of valid properties in the generated molecules. Experiments reveal that our model can discover plausible, diverse and novel molecules more effectively than several state of the art methods. Moreover, by utilizing Bayesian optimization over the continuous latent representation of molecules our model finds, we can also find molecules that maximize certain desirable properties more effectively than alternatives.

Characteristics of typing on smartphone keyboards among different individuals can elicit emotion, similar to speech prosody or facial expressions. Existing works on typing based emotion recognition rely on feature engineering to build machine learning models, while recent speech and facial expression based techniques have shown the efficacy of learning the features automatically. Therefore, in this work, we explore the effectiveness of such learning models in keyboard interaction based emotion detection. In this paper, we propose an end-to-end framework, which first uses a sequence-based encoding method to automatically learn the representation from raw keyboard interaction pattern and subsequently uses this representation to train a multi-task learning based neural network (MTL-NN)to identify different emotions. We carry out a 3-week in-the-wild study involving 24 participants using a custom keyboard capable of tracing users' interaction pattern during text entry. We collect interaction details like touch speed, error rate, pressure and self-reported emotions (happy, sad, stressed, relaxed) during the study. Our analysis on the collected dataset reveals that the representation learnt from the interaction pattern has an average correlation of 0.901 within the same emotion and 0.811 between different emotions. As a result, the representation is effective in distinguishing different emotions with an average accuracy (AUCROC)of 84%.

Multilingual writers and speakers often alternate between two languages in a single discourse, a practice called "code-switching".Existing sentiment detection methods are usually trained on sentiment-labeled monolingual text.Manually labeled code-switched text, especially involving minority languages, is extremely rare.Consequently, the best monolingual methods perform relatively poorly on code-switched text.We present an effective technique for synthesizing labeled code-switched text from labeled monolingual text, which is more readily available.The idea is to replace carefully selected subtrees of constituency parses of sentences in the resource-rich language with suitable token spans selected from automatic translations to the resource-poor language.By augmenting scarce human-labeled code-switched text with plentiful synthetic code-switched text, we achieve significant improvements in sentiment labeling accuracy (1.5%, 5.11%, 7.20%) for three different language pairs (English-Hindi, English-Spanish and English-Bengali).We also get significant gains for hate speech detection: 4% improvement using only synthetic text and 6% if augmented with real text.

High-impact catastrophic events (bomb attacks, shootings) trigger posting of large volume of information on social media platforms such as Twitter. Recent works have proposed content-aware systems for summarizing this information, thereby facilitating post-disaster services. However, a significant proportion of the posted content is unverified, which restricts the practical usage of the existing summarization systems. In this paper, we work on the novel task of generating verified summaries of information posted on Twitter during disasters. We first jointly learn representations of content-classes and expression-classes of tweets posted during disasters using a novel LDA-based generative model. These representations of content & expression classes are used in conjunction with pre-disaster user behavior and temporal signals (replies) for training a Tree-LSTM based tweet-verification model. The model infers tweet verification probabilities which are used, besides information content of tweets, in an Integer Linear Programming (ILP) framework for generating the desired verified summaries. The summaries are fine-tuned using the class information of the tweets as obtained from the LDA-based generative model. Extensive experiments are performed on a publicly-available labeled dataset of man-made disasters which demonstrate the effectiveness of our tweet-verification (3-13% gain over baselines) and summarization (12-48% gain in verified content proportion, 8-13% gain in ROUGE-score over state-of-the-art) systems. We make implementations of our various modules available online.

Soumya Sharma, Bishal Santra, Abhik Jana, Santosh Tokala, Niloy Ganguly, Pawan Goyal. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 2019.

Code-switching, the interleaving of two or more languages within a sentence or discourse is pervasive in multilingual societies. Accurate language models for code-switched text are critical for NLP tasks. State-of-the-art data-intensive neural language models are difficult to train well from scarce language-labeled code-switched text. A potential solution is to use deep generative models to synthesize large volumes of realistic code-switched text. Although generative adversarial networks and variational autoencoders can synthesize plausible monolingual text from continuous latent space, they cannot adequately address code-switched text, owing to their informal style and complex interplay between the constituent languages. We introduce VACS, a novel variational autoencoder architecture specifically tailored to code-switching phenomena. VACS encodes to and decodes from a two-level hierarchical representation, which models syntactic contextual signals in the lower level, and language switching signals in the upper layer. Sampling representations from the prior and decoding them produced well-formed, diverse code-switched sentences. Extensive experiments show that using synthetic code-switched text with natural monolingual data results in significant (33.06\%) drop in perplexity.

Accurate modeling of network traffic has a wide variety of applications. In this paper, we propose Network Transmission Point Process (NTPP), a probabilistic deep machinery that models the traffic characteristics of hosts on a network and effectively forecasts the network traffic patterns, such as load spikes. Existing stochastic models relied on the network traffic being self-similar in nature, thus failing to account for traffic anomalies. These anomalies, such as short-term traffic bursts, are very prevalent in certain modern-day traffic conditions, e.g. datacenter traffic, thus refuting the assumption of self-similarity. Our model is robust to such anomalies since it effectively leverages the self-exciting nature of the bursty network traffic using a temporal point process model.On seven diverse datasets collected from the fields of cyberdefense exercises (CDX), website access logs, datacenter traffic, and P2P traffic, NTPP offers a substantial performance boost in predicting network traffic characteristics against several baselines, ranging from forecasting the network traffic volume to detecting traffic spikes. We also demonstrate an application of our model to a caching scenario, showing that it can be used to effectively lower the cache miss rate.

Typing based interfaces are common across many mobile applications, especially messaging apps. To reduce the difficulty of typing using keyboard applications on smartphones, smartwatches with restricted space, several techniques, such as auto-complete, auto-suggest, are implemented. Although helpful, these techniques do add more cognitive load on the user. Hence beyond the importance to improve the word recommendations, it is useful to understand the pattern of use of auto-suggestions during typing. Among several factors that may influence use of auto-suggest, the role of emotion has been mostly overlooked, often due to the difficulty of unobtrusively inferring emotion. With advances in affective computing, and ability to infer user's emotional states accurately, it is imperative to investigate how auto-suggest can be guided by emotion aware decisions. In this work, we investigate correlations between user emotion and usage of auto-suggest i.e. whether users prefer to use auto-suggest in specific emotion states. We developed an Android keyboard application, which records auto-suggest usage and collects emotion self-reports from users in a 3-week in-the-wild study. Analysis of the dataset reveals relationship between user reported emotion state and use of auto-suggest. We used the data to train personalized models for predicting use of auto-suggest in specific emotion state. The model can predict use of auto-suggest with an average accuracy (AUCROC) of 82% showing the feasibility of emotion-aware auto-suggestion.

Network traffic classification is an important tool for network administrators in enabling monitoring and service provisioning. Traditional techniques employed in classifying traffic do not work well for mobile app traffic due to lack of unique signatures. Encryption renders this task even more difficult since packet content is no longer available to parse. More recent techniques based on statistical analysis of parameters such as packet-size and arrival time of packets have shown promise; such techniques have been shown to classify traffic from a small number of applications with a high degree of accuracy. However, we show that when employed to a large number of applications, the performance falls short of satisfactory. In this paper, we propose a novel set of bit-sequence based features which exploit differences in randomness of data generated by different applications. These differences originating due to dissimilarities in encryption implementations by different applications leave footprints on the data generated by them. We validate that these features can differentiate data encrypted with various ciphers (89% accuracy) and key-sizes (83% accuracy). Our evaluation shows that such features can not only differentiate traffic originating from different categories of mobile apps (90% accuracy), but can also classify 175 individual applications with 95% accuracy.

Online news media sites are emerging as the primary source of news for a large number of users. Due to a large number of stories being published in these media sites, users usually rely on news recommendation systems to find important news. In this work, we focus on automatically recommending news stories to all users of such media websites, where the selection is not influenced by a particular user’s news reading habit. When recommending news stories in such non-personalized manner, there are three basic metrics of interest—recency, importance (analogous to relevance in personalized recommendation) and diversity of the recommended news. Ideally, recommender systems should recommend the most important stories soon after they are published. However, the importance of a story only becomes evident as the story ages, thereby creating a tension between recency and importance. A systematic analysis of popular recommendation strategies in use today reveals that they lead to poor trade-offs between recency and importance in practice. So, in this paper, we propose a new recommendation strategy (called Highest Future-Impact ) which attempts to optimize on both the axes. To implement our proposed strategy in practice, we propose two approaches to predict the future-impact of news stories, by using crowd-sourced popularity signals and by observing editorial selection in past news data. Finally, we propose approaches to inculcate diversity in recommended news which can maintain a balanced proportion of news from different news sections. Evaluations over real-world news datasets show that our implementations achieve good performance in recommending news stories.

Code-switching or the juxtaposition of linguistic units from two or more languages in a single utterance, has, in recent times, become very common in text, thanks to social media and other computer mediated forms of communication. In this exploratory study of English-Hindi code-switching on Twitter, we automatically create a large corpus of code-switched tweets and devise techniques to identify the relationship between successive components in a code-switched tweet. More specifically, we identify pragmatic functions such as narrative-evaluative, negative reinforcement, translation or semantically equivalent statements, and so on characterizing the relation between successive components. We analyze the difference/similarity between switching patterns in code-switched and monolingual multi-component tweets. We observe strong dominance of narrative-evaluative (non-opinion to opinion or vice versa) switching in case of both code-switched and monolingual multi-component tweets in around 40% of cases. Polarity switching appears to be a prevalent switching phenomenon (10%) specifically in code-switched tweets (three to four times higher than monolingual multi-component tweets) where preference of expressing negative sentiment in Hindi is approximately twice compared to English. Positive reinforcement appears to be an important pragmatic function for English multi-component tweets, whereas negative reinforcement plays a key role for Devanagari multi-component tweets. Our results also indicate that the extent and nature of code-switching also strongly depend on the topic (sports, politics, etc.) of discussion.

Public shaming in online social networks and related online public forums like Twitter has been increasing in recent years. These events are known to have a devastating impact on the victim's social, political, and financial life. Notwithstanding its known ill effects, little has been done in popular online social media to remedy this, often by the excuse of large volume and diversity of such comments and, therefore, unfeasible number of human moderators required to achieve the task. In this paper, we automate the task of public shaming detection in Twitter from the perspective of victims and explore primarily two aspects, namely, events and shamers. Shaming tweets are categorized into six types: abusive, comparison, passing judgment, religious/ethnic, sarcasm/joke, and whataboutery, and each tweet is classified into one of these types or as nonshaming. It is observed that out of all the participating users who post comments in a particular shaming event, majority of them are likely to shame the victim. Interestingly, it is also the shamers whose follower counts increase faster than that of the nonshamers in Twitter. Finally, based on categorization and classification of shaming tweets, a web application called BlockShame has been designed and deployed for on-the-fly muting/blocking of shamers attacking a victim on the Twitter.

In recent years, we have witnessed a paradigm shift in news consumption. In traditional news media organizations, a small number of expert editors are responsible for selecting news stories that are consumed by all news readers (the audience). However, with the growing popularity of social media as a news consumption medium, a part of the editorial power of selecting news stories has shifted to the audience who select and share the stories that can reach a large number of consumers. In this paper, we analyze data from two popular news media sites-The New York Times and The Guardian, and characterize the considerable differences in the types of stories selected by the audience and expert news editors. We also find that story selections by audience vary significantly across different social media channels such as Twitter, Facebook, and email. We contextualize the differences utilizing media and communication theory and discuss their implications for news readers and media organizations.

Microblogging platforms such as Twitter are widely used by eyewitnesses and affected people to post situational updates during mass convergence events such as natural and man-made disasters. These crisis-related messages disperse among multiple classes/categories such as infrastructure damage, shelter needs, information about missing, injured, and dead people. Moreover, we observe that sometimes people post information about their missing relatives and friends with personal details such as names and last seen location. The information requirements of different stakeholders (government, NGOs, and rescue workers) also vary a lot. This brings twofold challenges: 1) extracting important high-level situational updates from these messages, assigning them appropriate categories, and finally summarizing big trove of information in each category and 2) extracting small-scale time-critical sparse updates related to missing or trapped people. In this article, we propose a classification-summarization framework which first assigns tweets into different situational classes and then summarizes those tweets. In the summarization phase, we propose a two-step extractive-abstractive summarization framework. In the first step, it extracts a set of important tweets from the whole set of information, develops a bigram-based word-graph from those tweets, and generates paths by traversing the word-graph. Next, it uses an optimization technique based on integer linear programming (ILP) to select the most important tweets and paths based on different optimization parameters such as informativeness and coverage of content words. Apart from general classwise summarization, we also show the customization of our summarization model to address time-critical sparse information needs (e.g., missing relatives). Our proposed method is time- and memory-efficient and shows better performance than state-of-the-art methods in terms of both quantitative and qualitative judgment.

In this article, we perform a large-scale study of the Twitter follower network, involving around 0.42 million users who justify DA, to characterize the spreading of DA tweets across the network. Our observations reveal the existence of a very large giant component involving 99% of these users with dense local connectivity that facilitates the spreading of such messages. We further identify active cascades over the network and observe that the cascades of DA tweets get spread over a long distance through the engagement of several closely connected groups of users. Moreover, our observations also reveal a collective phenomenon, involving a large set of active fringe nodes (with a small number of follower and following) along with a small set of well-connected nonfringe nodes that work together toward such spread, thus potentially complicating the process of arresting such cascades. Furthermore, we discovered that the engagement of the users with respect to certain drugs, such as Vicodin, Percocet, and OxyContin, that were observed to be most mentioned in Twitter is instantaneous. On the other hand, for drugs, such as Lortab, that found lesser mentions, the engagement probability becomes high with increasing exposure to such tweets, thereby indicating that drug abusers engaged on Twitter remain vulnerable to adopting newer drugs, aggravating the problem further.

With the recent advances in Internet of Things, smarthomes containing a variety of sensors are expected to monitor and react to the activities of daily living (ADL) of the residents with the goal of improving convenience, comfort, and safety. However, a single human activity may trigger multiple sensors, and each sensor is triggered by multiple activities. Also, the very human nature of interleaving activities along with the presence of multiple inhabitants makes ADL detection a complex problem. This paper tackles the problem with a data driven de-multiplexing approach termed TSFS (Temporal-Sensor-Frequency-Stitch) that disentangles each individual activity from the sensor stream and thus simplifies the ADL recognition problem. TSFS leverages temporal(T), sensory(S), and frequency(F) information to discriminate between two consecutive/parallel activities, followed by a stitch(S) to enhance segmentation. The multi-faceted approach helps us in correctly identifying segments; extensive evaluation on 10 public datasets reveals that TSFS is better by 185 percent when compared to a simple temporal segmentation approach. The activity detection accuracy yields within 93 percent of the best possible (an oracle) approach.

Social networks, forums, and social media have emerged as global platforms for forming and shaping opinions on a broad spectrum of topics like politics, sports, and entertainment. Users (also calledactors) often update their evolving opinions, influenced through discussions with other users. Theoretical models and their analysis on understanding opinion dynamics in social networks abound in the literature. However, these models are often based on concepts from statistical physics. Their goal is to establish specific phenomena like steady state consensus or bifurcation. Analysis of transient effects is largely avoided. Moreover, many of these studies assume that actors’ opinions are observed globally and synchronously, which is rarely realistic. In this article, we initiate an investigation into a family of novel data-driven influence models that accurately learn and fit realistic observations. We estimate and do not presume edge strengths from observed opinions at nodes. Our influence models are linear but not necessarily positive or row stochastic in nature. As a consequence, unlike the previous studies, they do not depend on system stability or convergence during the observation period. Furthermore, our models take into account a wide variety of data collection scenarios. In particular, they are robust to missing observations for several timesteps after an actor has changed its opinion. In addition, we consider scenarios where opinion observations may be available only for aggregated clusters of nodes—a practical restriction often imposed to ensure privacy. Finally, to provide a conceptually interpretable design of edge influence, we offer a relatively frugal variant of our influence model, where the strength of influence between two connecting nodes depends on the node attributes (demography, personality, expertise, etc.). Such an approach reduces the number of model parameters, reduces overfitting, and offers a tractable and explicable sketch of edge influences in the context of opinion dynamics. With six real-life datasets crawled from Twitter and Reddit, as well as three more datasets collected from in-house experiments (with 102 volunteers), our proposed system gives a significant accuracy boost over four state-of-the-art baselines.

Traditionally, news media organizations used to publish only a few editions of the printed newspapers, and all subscribers of a particular edition used to receive the same information broadcasted by the media organization. The advent of personalized news recommendations has completely changed this simpler news landscape. Such recommendations effectively produce numerous personalized editions of a single newspaper, consisting of only the stories recommended to a particular reader. Although prior works have considered news coverage of different newspapers, due to the difficulty of knowing what news is recommended to whom, there has been no prior study to look into the coverage of information in different personalized news editions. Moreover, the evolution of the effects of personalization on recommended news stories is also not explored. In this work, we make the first attempt to investigate these issues. By collecting extensive data from New York Times personalized recommendations, we compare the information coverage in different personalized editions and investigate how they evolve over time. We observe that the coverage of news stories recommended to different readers are considerably different, and these differences further change with time. We believe that our work will be an important addition to the growing literature on algorithmic auditing and transparency.

Accurate modeling of how the visibility of a piece of information varies across time has a wide variety of applications. For example, in an e-commerce site like Amazon, it can help to identify which product is preferred over others; in Twitter, it can predict which hashtag may go viral against others. Visibility of a piece of information, therefore, indicates the ability of a piece of information to attract the attention of the users, against the rest. Therefore, apart from the individual information diffusion processes, the information visibility dynamics also involves a competition process, where each information diffusion process competes against each other to draw the attention of users. Despite models of individual information diffusion processes abounding in literature, modeling the competition process is left unaddressed. In this paper, we propose Competing Recurrent Point Process (CRPP), a probabilistic deep machinery that unifies the nonlinear generative dynamics of a collection of diffusion processes, and inter-process competition - the two ingredients of visibility dynamics. To design this model, we rely on a recurrent neural network (RNN) guided generative framework, where the recurrent unit captures the joint temporal dynamics of a group of processes. This is aided by a discriminative model which captures the underlying competition process by discriminating among the various processes using several ranking functions. On ten diverse datasets crawled from Amazon and Twitter, CRPP offers a substantial performance boost in predicting item visibility against several baselines, thereby achieving significant accuracy in predicting both the collective diffusion mechanism and the underlying competition processes.

A large fraction of video content providers have adopted adaptive bitrate streaming over HTTP. The client player typically runs an adaptive bitrate (ABR) algorithm to decide upon the most optimal quality for the next few seconds of video playback. State-of-the-art ABR algorithms attempt to achieve an optimal trade-off among the competing objectives of high bitrate, less rebuffering, and high smoothness, in the face of unpredictable bandwidth variability. However, optimal bandwidth utilization does not necessarily ensure high quality of experience (QoE). Different users have different content preferences even within the same video, due to differences in team loyalties (in sport), character preferences (in movies and soaps), and so on. In this work, we present HotDASH, a system which enables opportune prefetching of user-preferred temporal video segments (called hotspots). HotDASH implements a prefetch module in the open source DASH player dash.js, which is powered by an optimal prefetch and bitrate decision engine. The decision engine is designed as a cascaded reinforcement learning (RL) model, implemented using a state-of-the-art actor-critic RL algorithm over a neural network. We train the neural network using trace-driven simulations over a large variety of bandwidth conditions. HotDASH outperforms all baseline algorithms, with a 16.2% QoE improvement over the best-performing baseline, and achieves 14.31% better average bitrate due to its ability to prefetch opportunistically.

A large population of users gets affected by sudden slowdown or shutdown of an enterprise application. System administrators and analysts spend considerable amount of time dealing with functional and performance bugs. These problems are particularly hard to detect and diagnose in most computer systems, since there is a huge amount of system generated supportability data (counters, logs etc.) that need to be analyzed. Most often, there isn't a very clear or obvious root cause. Timely identification of significant change in application behavior is very important to prevent negative impact on the service. In this paper, we present ADELE, an empirical, data-driven methodology for early detection of anomalies in data storage systems. The key feature of our solution is diligent selection of features from system logs and development of effective machine learning techniques for anomaly prediction. ADELE learns from system's own history to establish the baseline of normal behavior and gives accurate indications of the time period when something is amiss for a system. Validation on more than 4800 actual support cases shows~83% true positive rate and~12% false positive rate in identifying periods when the machine is not performing normally. We also establish the existence of problem “signatures” which help map customer problems to already seen issues in the field. ADELE's capability to predict early paves way for online failure prediction for customer systems.

Typing characteristics on smartphones can provide clues for emotion detection. Collecting large volumes of typing data is also easy on smartphones. This motivates the use of Deep Neural Network (DNN) to determine emotion states from smartphone typing. In this work, we developed a DNN model based on typing features to predict four emotion states (happy, sad, stressed, relaxed) and investigate its performance on a smartphone. The evaluation of the model in a 3-week study with 15 participants reveals that it can reliably detect emotions with an average accuracy of 80% with peak CPU utilization less than 15%.

Passenger comfort is a major factor influencing a commuter's decision to avail public transport. Existing studies suggest that factors like overcrowding, jerkiness, traffic congestion etc. correlate well to passenger's (dis)comfort. An online survey conducted with more than 300 participants from 12 different countries reveals that different personalized and context dependent factors influence passenger comfort during a travel by public transport. Leveraging on these findings, we identify correlations between comfort level and these dynamic parameters, and implement a smartphone based application, ComfRide, which recommends the most comfortable route based on user's preference honoring her travel time constraint. We use a 'Dynamic Input/Output Automata' based composition model to capture both the wide varieties of comfort choices from the commuters and the impact of environment on the comfort parameters. Evaluation of ComfRide, involving 50 participants over 28 routes in a state capital of India, reveals that recommended routes have on average 30% better comfort level than Google map recommended routes, when a commuter gives priority to specific comfort parameters of her choice.

In recent times, humanitarian organizations increasingly rely on social media to search for information useful for disaster response. These organizations have varying information needs ranging from general situational awareness (i.e., to understand a bigger picture) to focused information needs e.g., about infrastructure damage, urgent needs of affected people. This research proposes a novel approach to help crisis responders fulfill their information needs at different levels of granularities. Specifically, the proposed approach presents simple algorithms to identify sub-events and generate summaries of big volume of messages around those events using an Integer Linear Programming (ILP) technique. Extensive evaluation on a large set of real world Twitter dataset shows (a). our algorithm can identify important sub-events with high recall (b). the summarization scheme shows (6---30%) higher accuracy of our system compared to many other state-of-the-art techniques. The simplicity of the algorithms ensures that the entire task is done in real time which is needed for practical deployment of the system.

The networked opinion diffusion in online social networks (OSN) is governed by the two genres of opinions-endogenous opinions that are driven by the influence of social contacts between users, and exogenous opinions which are formed by external effects like news, feeds etc. Such duplex opinion dynamics is led by users belonging to two categories- organic users who generally post endogenous opinions and extrinsic users who are susceptible to externalities, and mostly post the exogenous messages. Precise demarcation of endogenous and exogenous messages offers an important cue to opinion modeling, thereby enhancing its predictive performance. On the other hand, accurate user selection aids to detect extrinsic users, which in turn helps in opinion shaping. In this paper, we design CherryPick, a novel learning machinery that classifies the opinions and users by solving a joint inference task in message and user set, from a temporal stream of sentiment messages. Furthermore, we validate the efficacy of our proposal from both modeling and shaping perspectives. Moreover, for the latter, we formulate the opinion shaping problem in a novel framework of stochastic optimal control, in which the selected extrinsic users optimally post exogenous messages so as to guide the opinions of others in a desired way. On five datasets crawled from Twitter, CherryPick offers a significant accuracy boost in terms of opinion forecasting, against several competitors. Furthermore, it can precisely determine the quality of a set of control users, which together with the proposed online shaping strategy, consistently steers the opinion dynamics more effectively than several state-of-the-art baselines.

Opinion list (OL) queries like “valentines day gift ideas” and “best anniversary messages for your parents” are quite popular on web search engines. Users expect instant answers comprising of a list of relevant items (OL) for such a query. Surprisingly, current search engines do not provide any crisp instant answers for queries in this critical query segment. To the best of our knowledge, we present the first system that tackles such queries. Although such social factors are heavily discussed on online social networks like Twitter, extracting such lists from tweets is quite challenging. The challenges lie in discovering such lists from tweets, rank the discovered list items as well as handle lists with very low cardinality (tail OLs). We present an end-to-end system that: 1) identifies these “OLs” from a large number of Twitter hashtags using a classifier trained using novel task-specific features; 2) extracts suitable list answers from relevant tweets using carefully designed regex patterns; 3) uses the learning to rank framework to present a ranked list of these items; and 4) handles tail lists using a novel algorithm to borrow list items from similar lists. Crowd-sourced evaluation shows that the proposed system can extract OLs with a good accuracy.

The huge amount of tweets posted during a disaster event includes information about the present situation as well as the emotions/opinions of the masses. While looking through these tweets, we realized that a large amount of communal tweets, i.e., abusive posts targeting specific religious/racial groups are posted even during natural disasters-this paper focuses on such category of tweets, which is in sharp contrast to most of the prior research concentrating on extracting situational information. Considering the potentially adverse effects of communal tweets during disasters, in this paper, we develop a classifier to distinguish communal tweets from noncommunal ones, which performs significantly better than existing approaches. We also characterize the communal tweets posted during five recent disaster events, and the users who posted such tweets. Interestingly, we find that a large proportion of communal tweets are posted by popular users (having tens of thousands of followers), most of whom are related to media and politics. Further, users posting communal tweets form strong connected groups in the social network. As a result, the reach of communal tweets is much higher than noncommunal tweets. We also propose an event-independent classifier to automatically identify anticommunal tweets and also indicate a way to counter communal tweets, by utilizing such anticommunal tweets posted by some users during disaster events. Finally, we develop a real-time service to automatically collect tweets related to a disaster event and identify communal and anticommunal tweets from that set. We believe that such a system is really helpful for government and local monitoring agencies to take appropriate decisions like filtering or promoting some particular contents.

Microblogging sites like Twitter have become important sources of real-time information during disaster events. A large amount of valuable situational information is posted in these sites during disasters; however, the information is dispersed among hundreds of thousands of tweets containing sentiments and opinions of the masses. To effectively utilize microblogging sites during disaster events, it is necessary to not only extract the situational information from the large amounts of sentiments and opinions, but also to summarize the large amounts of situational information posted in real-time. During disasters in countries like India, a sizable number of tweets are posted in local resource-poor languages besides the normal English-language tweets. For instance, in the Indian subcontinent, a large number of tweets are posted in Hindi/Devanagari (the national language of India), and some of the information contained in such non-English tweets is not available (or available at a later point of time) through English tweets. In this work, we develop a novel classification-summarization framework which handles tweets in both English and Hindi—we first extract tweets containing situational information, and then summarize this information. Our proposed methodology is developed based on the understanding of how several concepts evolve in Twitter during disaster. This understanding helps us achieve superior performance compared to the state-of-the-art tweet classifiers and summarization approaches on English tweets. Additionally, to our knowledge, this is the first attempt to extract situational information from non-English tweets.

In Affective Computing, different modalities, such as speech, facial expressions, physiological properties, smart-phone usage patterns, and their combinations, are applied to detect the affective states of a user. Keystroke analysis i.e. study of the typing behavior in desktop computer is found to be an effective modality for emotion detection because of its reliability, non-intrusiveness and low resource overhead. As smartphones proliferate, typing behavior on smartphone presents an equally powerful modality for emotion detection. It has the added advantage to run in-situ experiments with better coverage than the experiments using desktop computer keyboards. This work explores the efficacy of smartphone typing to detect multiple affective states. We use a qualitative and experimental approach to answer the question. We conduct an online survey among 120 participants to understand the typing habits in smartphones and collect feedback on multiple measurable parameters that affect their emotion while typing. The findings lead us to design and implement an Android based emotion detection system, TapSense, which can identify four different emotion states (happy, sad, stressed, relaxed) with an average accuracy (AUCROC) of 73% (maximum of 94%) based on typing features only. The analysis also reveals that among different features, typing speed is the most discriminative one.

In recent times, people regularly discuss about poor travel experience due to various road closure incidents in the social networking sites. One of the fallouts of these road blocking incidents is the dynamic shift in regular taxi pickup locations. Although traffic monitoring from social media content has lately gained widespread interest, however, none of the recent works has tried to understand this relocation of taxi pickup hotspots during any road closure activity. In this work, we have tried to predict the taxi pickup hotspots, during various road closure incidents, using their past taxi pickup trend. We have proposed a two-step methodology. First, we identify and extract road closure information from social network posts. Second, leveraging the inferred knowledge, prediction of taxi pickup hotspot is done near the activity location with an average accuracy of ~ 86.04%, where the predicted locations are within an average radius of only 0.011 mile from the original hotspots.

Social list queries like 'valentines day gift ideas', 'best anniversary messages for your parents', etc. are quite popular on web search engines. Users expect instant answers comprising of a list of relevant items (social list) for such a query. Surprisingly, current search engines do not provide any crisp instant answers for queries in this critical query segment. To the best of our knowledge, we propose the first system that tackles such queries. Although such social factors are heavily discussed on online social networks like Twitter, extracting such lists from tweets is quite challenging. How to discover such lists from tweets? We present a system that identifies these 'social lists' from a large number of Twitter hashtags using a high recall classifier trained using novel task-specific features with good accuracy. Further, we briefly discuss how list items can be extracted from related tweets. Experiments over a dataset of ~4M tweets show that our recall-optimized system can obtain up to 75.5% precision at 95.3% recall.

Experience Sampling Method (ESM) is widely used in idiographic approaches to collect within-person patterns. Planning a suitable survey schedule while designing an ESM based experiment is challenging as it must balance between survey fatigue of users, and the timeliness and accuracy of the responses provided by users. Even with the proliferation of ESM experiments, survey scheduling typically remains confined to use of fixed schedules, where periodic probes are sent to user, or event-based schedules, where depending on the number of events, large number of probes may interrupt user frequently. We propose a novel survey scheduling scheme, Low-Interference High-fidelity (LIHF) ESM schedule, which is designed to reduce interference while retaining fidelity of user response. We integrated LIHF into an ESM application, called TapSense, that is used to infer user's emotion from typing characteristics on smartphone keypad. Conducting a 2-week field study involving 9 users, using proposed metrics we show that using LIHF there is 26% reduction in survey fatigue, 50% improvement in triggering survey probes in timely manner, and 8% improvement in predicting emotion states based on typing patterns compared to typical ESM scheduling techniques.

Existing systems for travel time estimation either use data collected from loop detectors and probe vehicle locations, or from GPS traces from cellphones of "online" users. The former methods of data acquisition are expensive, while the latter turns out to be infeasible in connectivity-poor regions. However, many crowdsourced taxi trip datasets (from Boston, Beijing, Rome, etc.) are publicly available which, despite containing limited information, can be made useful for inferring meaningful insights by certain amount of data engineering. The datasets are both cheap to acquire (hence available in large volumes), and impose less heavy connectivity requirements on the end user. One such crowdsourced dataset is the NYC (New York City) Taxi dataset, which contains only the end-point information for each trip. In this paper, a link (road segment) travel time estimation algorithm named Least Square Estimation with Constraint (LSEC) has been developed from such end-point data, which estimates travel time 20% more accurately than existing algorithms. The key idea is to augment a subset of trips with unique paths using logged distance information, as opposed to fitting adhoc "route-choice" models.

City transit maps are one of the important resources for public navigation in today's digital world. However, the availability of transit maps for many developing countries is very limited, primarily due to the various socio-economic factors that drive the private operated and partially regulated transport services. Public transports at these cities are marred with many factors such as uncoordinated waiting time at bus stoppages, crowding in the bus, sporadic road conditions etc., which also need to be annotated so that commuters can take informed decision. Interestingly, many of these factors are spatio-temporal in nature. In this paper, we develop CityMap, a system to automatically extract transit routes along with their eccentricities from spatio-temporal crowdsensed data collected via commuters' smart-phones. We apply a learning based methodology coupled with a feature selection mechanism to filter out the necessary information from raw smart-phone sensor data with minimal user engagement and drain of battery power. A thorough evaluation of CityMap, conducted for more than two years over 11 different routes in 3 different cities in India, show that the system effectively annotates bus routes along with other route and road features with more than 90% of accuracy.

Online Social Networks (OSNs) have emerged as a global media for forming and shaping opinions on a broad spectrum of topics like politics, e-commerce, sports, etc. So, research on understanding and predicting opinion dynamics in OSNs, especially using a tractable linear model, has abound in literature. However, these linear models are too simple to uncover the actual complex dynamics of opinion flow in social networks. In this paper, we propose SLANT+, a novel nonlinear generative model for opinion dynamics, by extending our earlier linear opinion model SLANT [7]. To design this model, we rely on a network-guided recurrent neural network architecture which learns a proper temporal representation of the messages as well as the underlying network. Furthermore, we probe various signals from the real life datasets and offer a conceptually interpretable nonlinear function that not only provides concrete clues of the opinion exchange process, but also captures the coupled dynamics of message timings and opinion flow. As a result, with five real-life datasets crawled from Twitter, our proposal gives significant accuracy boost over six state-of-the-art baselines.

Predicting the popularity dynamics of Twitter hashtags has a broad spectrum of applications. Existing works have mainly focused on modeling the popularity of individual tweets rather than the popularity of the underlying hashtags. Hence, they do not consider several realistic factors for hashtag popularity. In this paper, we propose Large Margin Point Process (LMPP), a probabilistic framework that integrates hashtag-tweet influence and hashtag-hashtag competitions, the two factors which play important roles in hashtag propagation. Furthermore, while considering the hashtag competitions, LMPP looks into the variations of popularity rankings of the competing hashtags across time. Extensive experiments on seven real datasets demonstrate that LMPP outperforms existing popularity prediction approaches by a significant margin. Going further, LMPP can accurately predict the relative rankings of competing hashtags, offering additional advantage over the state-of-the-art baselines.

Among the mobile applications contributing to the surging Internet traffic, video applications are some of the biggest contributors. Most of these video applications use HTTP/HTTPS tunneling making it difficult to apply port based or packet data based identification of flows. This makes it challenging for network operators to enforce bandwidth regulation policies for app based service differentiation due to lack of flow identification mechanisms for mobile apps. We explore a packet data agnostic feature of video flows, namely packet-size, to identify the flows. We show that it is possible to train a classifier that can distinguish packets from streaming and interactive video apps with high accuracy. We design and implement a system, called MoViDiff, with this classifier at the core, that allows bandwidth regulation between video traffic of two different categories, streaming and interactive. We show that we can achieve an average accuracy of 96% in classifying the traffic, with the maximum accuracy reaching as high as 98%.

With social media platform such as Twitter becoming the de facto destination for users' views and opinions, it is of great importance to forecast an information outbreak. In Twitter, tweets are often annotated with hashtags to help its users to quickly extract their contents. The existing approaches for modeling the dynamics of tweet-messages are usually limited to individual or simple aggregates of tweets rather than the underlying hashtags. In this paper, we develop, STRM, a novel point process driven model that considers the effect of cross-tweet impact in hashtag popularity. STRM, by assuming hashtag to be a heterogeneous collection of tweet-chains. Through extensive experimentation, we find that our algorithm - STRM, shows consistent performance boosts with six diverse real datasets against several strong baselines. Moreover surprisingly, it also offers significant accuracy gains in popularity-prediction for individual tweets as compared with the existing paradigms.

Typing based communication applications on smartphones, like WhatsApp, can induce emotional exchanges. The effects of an emotion in one session of communication can persist across sessions. In this work, we attempt automatic emotion detection by jointly modeling the typing characteristics, and the persistence of emotion. Typing characteristics, like speed, number of mistakes, special characters used, are inferred from typing sessions. Self reports recording emotion states after typing sessions capture persistence of emotion. We use this data to train a personalized machine learning model for multi-state emotion classification. We implemented an Android based smartphone application, called TapSense, that records typing related metadata, and uses a carefully designed Experience Sampling Method (ESM) to collect emotion self reports. We are able to classify four emotion states - happy, sad, stressed, and relaxed, with an average accuracy (AUCROC) of 84% for a group of 22 participants who installed and used TapSense for 3 weeks.

YouTube has emerged as the largest player among video streaming services, serving video content for users using DASH. Research studies on various aspects of YouTube, especially its streaming service, abound in the literature. However, these works study YouTube streaming from the periphery, and report results based on their understanding of general DASH recommendations. In this study, we explore in depth YouTube's implementation of the DASH client. We identify important parameters in YouTube's rate adaptation algorithm, and study their roles. In a departure from existing literature, we observe that YouTube opportunistically adapts segment length, in addition to quality level, in response to bandwidth fluctuations. We report that this scheme results in a much lower average data wastage ratio (0.82x10-6), than reported earlier. We also propose an analytical model, augmented with a machine learning based classifier (with average accuracy of 85.75%), to predict data consumption for a playback session in advance.

Online news media sites are emerging as the primary source of news for a large number of users. The selection of 'front-page' stories on these media sites usually takes into consideration several crowdsourced popularity metrics, such as number of views or shares by the readers. In this work, we focus on automatically recommending front-page stories in such media websites. When recommending news stories, there are two basic metrics of interest - recency and relevancy. Ideally, recommender systems should recommend the most relevant stories soon after they are published. However, the relevancy of a story only becomes evident as the story ages, thereby creating a tension between recency and relevancy. A systematic analysis of popular recommendation strategies in use today reveals that they lead to poor trade-offs between recency and relevancy in practice. So, in this paper, we propose a new recommendation strategy (called Highest Future-Impact) which attempts to optimize on both the axes. To implement our proposed strategy in practice, we develop an optimization framework combining the predicted future-impact of the stories with the uncertainties in the predictions. Evaluations over three real-world news datasets show that our implementation achieves good performance trade-offs between recency and relevancy.

With the growing shift towards news consumption primarily through social media sites like Twitter, most of the traditional as well as new-age media houses are promoting their news stories by tweeting about them. The competition for user attention in such mediums has led many media houses to use catchy sensational form of tweets to attract more users - a process known as clickbaiting. In this work, using an extensive dataset collected from Twitter, we analyze the social sharing patterns of clickbait and non-clickbait tweets to determine the organic reach of such tweets. We also attempt to study the sections of Twitter users who actively engage themselves in following clickbait and non-clickbait tweets. Comparing the advent of clickbaits with the rise of tabloidization of news, we bring out several important insights regarding the news consumers as well as the media organizations promoting news stories on Twitter.

Most of the online news media outlets rely heavily on the revenues generated from the clicks made by their readers, and due to the presence of numerous such outlets, they need to compete with each other for reader attention. To attract the readers to click on an article and subsequently visit the media site, the outlets often come up with catchy headlines accompanying the article links, which lure the readers to click on the link. Such headlines are known as Clickbaits. While these baits may trick the readers into clicking, in the long-run, clickbaits usually don't live up to the expectation of the readers, and leave them disappointed. In this work, we attempt to automatically detect clickbaits and then build a browser extension which warns the readers of different media sites about the possibility of being baited by such headlines. The extension also offers each reader an option to block clickbaits she doesn't want to see. Then, using such reader choices, the extension automatically blocks similar clickbaits during her future visits. We run extensive offline and online experiments across multiple media sites and find that the proposed clickbait detection and the personalized blocking approaches perform very well achieving 93% accuracy in detecting and 89% accuracy in blocking clickbaits.

Peer-review system has long been relied upon for bringing quality research to the notice of the scientific community and also preventing flawed research from entering into the literature. The need for the peer-review system has often been debated as in numerous cases it has failed in its task and in most of these cases editors and the reviewers were thought to be responsible for not being able to correctly judge the quality of the work. This raises a question "Can the peer-review system be improved?" Since editors and reviewers are the most important pillars of a reviewing system, we in this work, attempt to address a related question - given the editing/reviewing history of the editors or reviewers "can we identify the under-performing ones?", with citations received by the edited/reviewed papers being used as proxy for quantifying performance. We term such reviewers and editors as anomalous and we believe identifying and removing them shall improve the performance of the peer-review system. Using a massive dataset of Journal of High Energy Physics (JHEP) consisting of 29k papers submitted between 1997 and 2015 with 95 editors and 4035 reviewers and their review history, we identify several factors which point to anomalous behavior of referees and editors. In fact the anomalous editors and reviewers account for 26.8% and 14.5% of the total editors and reviewers respectively and for most of these anomalous reviewers the performance degrades alarmingly over time.

Extracting news on specific topics from the Twitter microblogging site poses formidable challenges, which include handling millions of tweets posted daily, judging topicality and importance of tweets, and ensuring trustworthiness of results in the face of spam. To date, all scalable approaches have relied on crowd wisdom, i.e., keyword-matching on the global tweet stream to gather relevant tweets, and crowd- endorsements to judge the importance of tweets. We propose a fundamentally different methodology -- for a given topic, we identify trustworthy experts on the topic, and extract news-stories that are most popular among the experts. Comparing the crowd-based and expert-based methodologies, we demonstrate that the news-stories obtained by our methodology (i) have higher relevance for a wide variety of topics, (ii) achieve very high coverage of important news-stories posted globally in Twitter, and (iii) are far more trustworthy. Using our methodology, we implemented and publicly deployed a topical news system for Twitter, which can extract news-stories on thousands of topics.

Linguistic research on multilingual societies has indicated that there is usually a preferred language for expression of emotion and sentiment (Dewaele, 2010).Paucity of data has limited such studies to participant interviews and speech transcriptions from small groups of speakers.In this paper, we report a study on 430,000 unique tweets from Indian users, specifically Hindi-English bilinguals, to understand the language of preference, if any, for expressing opinion and sentiment.To this end, we develop classifiers for opinion detection in these languages, and further classifying opinionated tweets into positive, negative and neutral sentiments.Our study indicates that Hindi (i.e., the native language) is preferred over English for expression of negative opinion and swearing.As an aside, we explore some common pragmatic functions of codeswitching through sentiment detection.* * This work was done when the author was a Research Fellow at Microsoft Research Lab India.1 Although some linguists differentiate between Codeswitching and Code-mixing, this paper will use the two terms interchangeably.

Public bus services in many cities in countries like India are controlled by private owners, hence, building up a database for all the bus routes is non-trivial. In this paper, we leverage smart-phone based sensing to crowdsource and populate the information repository for bus routes in a city. We have developed an intelligent data logging module for smart-phones and a server side processing mechanism to extract roads and bus routes information. From a 3 month long study involving more than 30 volunteers in 3 different cities in India, we found that the developed system, CrowdMap, can annotate bus routes with a mean error of 10m, while consuming 80% less energy compared to a continuous GPS based system.

Public transport in suburban cities (covers 80% of the urban landscape) of developing regions suffer from the lack of information in Google Transit, unpredictable travel times, chaotic schedules, absence of information board inside the vehicle. Consequently, passengers suffer from lack of information about the exact location where the bus is at present as well as the estimated time to be taken to reach the desired destination. We find that off-the-shelf deployment of existing (non-GPS) localization schemes exhibit high error due to sparsity of stable and structured outdoor landmarks (anchor points). Through rigorous experiments conducted over a month however, we realize that there are a certain class of volatile landmarks which may be useful in developing efficient localization scheme. Consequently, in this paper, we design a novel generalized energy-efficient outdoor localization scheme - UrbanEye, which efficiently combines the volatile and non-volatile landmarks using a specialized data structure, the probabilistic timed automata. UrbanEye uses speed-breakers, turns and stops as landmarks, estimates the travel time with a mean accuracy of ±2.5 mins and produces a mean localization accuracy of 50 m. Results from several runs taken in two cities, Durgapur and Kharagpur, reveal that UrbanEye provides more than 50% better localization accuracy compared to the existing system Dejavu [1], and consumes significantly less energy.

Social media and social networking sites have become a global pinboard for exposition and discussion of news, topics, and ideas, where social media users often update their opinions about a particular topic by learning from the opinions shared by their friends. In this context, can we learn a data-driven model of opinion dynamics that is able to accurately forecast users' opinions? In this paper, we introduce SLANT, a probabilistic modeling framework of opinion dynamics, which represents users' opinions over time by means of marked jump diffusion stochastic differential equations, and allows for efficient model simulation and parameter estimation from historical fine grained event data. We then leverage our framework to derive a set of efficient predictive formulas for opinion forecasting and identify conditions under which opinions converge to a steady state. Experiments on data gathered from Twitter show that our model provides a good fit to the data and our formulas achieve more accurate forecasting than alternatives.

The goal of community detection algorithms is to identify densely connected units within large networks. An implicit assumption is that all the constituent nodes belong equally to their associated community. However, some nodes are more important in the community than others. To date, efforts have been primarily made to identify communities as a whole, rather than understanding to what extent an individual node belongs to its community. Therefore, most metrics for evaluating communities, for example modularity, are global. These metrics produce a score for each community, not for each individual node. In this article, we argue that the belongingness of nodes in a community is not uniform. We quantify the degree of belongingness of a vertex within a community by a new vertex-based metric called permanence . The central idea of permanence is based on the observation that the strength of membership of a vertex to a community depends upon two factors (i) the extent of connections of the vertex within its community versus outside its community, and (ii) how tightly the vertex is connected internally. We present the formulation of permanence based on these two quantities. We demonstrate that compared to other existing metrics (such as modularity, conductance, and cut-ratio), the change in permanence is more commensurate to the level of perturbation in ground-truth communities. We discuss how permanence can help us understand and utilize the structure and evolution of communities by demonstrating that it can be used to -- (i) measure the persistence of a vertex in a community, (ii) design strategies to strengthen the community structure, (iii) explore the core-periphery structure within a community, and (iv) select suitable initiators for message spreading. We further show that permanence is an excellent metric for identifying communities. We demonstrate that the process of maximizing permanence (abbreviated as MaxPerm ) produces meaningful communities that concur with the ground-truth community structure of the networks more accurately than eight other popular community detection algorithms. Finally, we provide mathematical proofs to demonstrate the correctness of finding communities by maximizing permanence. In particular, we show that the communities obtained by this method are (i) less affected by the changes in vertex ordering, and (ii) more resilient to resolution limit, degeneracy of solutions, and asymptotic growth of values.

Detection of non-overlapping and overlapping communities are essentially the same problem. However, current algorithms focus either on finding overlapping or non-overlapping communities. We present a generalized framework that can identify both non-overlapping and overlapping communities, without any prior input about the network or its community distribution. To do so, we introduce a vertex-based metric,GenPerm, that quantifies by how much a vertex belongs to each of its constituent communities. Our community detection algorithm is based on maximizing the GenPerm over all the vertices in the network. We demonstrate, through experiments over synthetic and real-world networks, that GenPerm is more effective than other metrics in evaluating community structure. Further, we show that due to its vertex-centric property, GenPerm can be used to unfold several inferences beyond community detection, such as core-periphery analysis and message spreading. Our algorithm for maximizing GenPerm outperforms six state-of-the-art algorithms in accurately predicting the ground-truth labels. Finally, we discuss the problem of resolution limit in overlapping communities and demonstrate that maximizing GenPerm can mitigate this problem.

Predicting plausible links that may emerge between pairs of nodes is an important task in social network analysis, with over a decade of active research. Here, we propose a novel framework for link prediction. It integrates signals from node features, the existing local link neighborhood of a node pair, community-level link density, and global graph properties. Our framework uses a stacked two-level learning paradigm. At the lower level, the first two kinds of features are processed by a novel local learner. Its outputs are then integrated with the last two kinds of features by a conventional discriminative learner at the upper-level. We also propose a new stratified sampling scheme for evaluating link prediction algorithms in the face of an extremely large number of potential edges, out of which very few will ever materialize. It is not tied to a specific application of link prediction, but robust to a range of application requirements. We report on extensive experiments with seven benchmark datasets and over five competitive baseline systems. The system we present consistently shows at least 10 percent accuracy improvement over state-of-the-art, and over 30 percent improvement in some cases. We also demonstrate, through ablation, that our features are complementary in terms of the signals and accuracy benefits they provide.

This paper explores the feasibility of automatically extracting passwords from a user's daily activity logs, such as her Facebook activity, phone activity etc. As an example, a smartphone might ask the user: "Today morning from whom did you receive an SMS?" In this paper, we observe that infrequent activities (i.e., outliers) can be memorable and unpredictable. Building on this observation, we have developed an end to end system ActivPass and experimented with 70 users. With activity logs from Facebook, browsing history, call logs, and SMSs, the system achieves 95% success (authenticates legitimate users) and is compromised in 5.5% cases (authenticates impostors). While this level of security is obviously inadequate for serious authentication systems, certain practices such as password sharing can immediately be thwarted from the dynamic nature of passwords. With security improvements in the future, activity-based authentication could fill in for the inadequacies in today's password-based systems.

Microblogging sites like Twitter have become important sources of real-time information during disaster events. A significant amount of valuable situational information is available in these sites; however, this information is immersed among hundreds of thousands of tweets, mostly containing sentiments and opinion of the masses, that are posted during such events. To effectively utilize microblogging sites during disaster events, it is necessary to (i) extract the situational information from among the large amounts of sentiment and opinion, and (ii) summarize the situational information, to help decision-making processes when time is critical. In this paper, we develop a novel framework which first classifies tweets to extract situational information, and then summarizes the information. The proposed framework takes into consideration the typicalities pertaining to disaster events where (i) the same tweet often contains a mixture of situational and non-situational information, and (ii) certain numerical information, such as number of casualties, vary rapidly with time, and thus achieves superior performance compared to state-of-the-art tweet summarization approaches.

Analysis of content streams gathered from social networking sites such as Twitter has several applications ranging from content search and recommendation, news detection to business analytics. However, processing large amounts of data generated on these sites in real-time poses a difficult challenge. To cope with the data deluge, analytics companies and researchers are increasingly resorting to sampling. In this article, we investigate the crucial question of how to sample content streams generated by users in online social networks . The traditional method is to randomly sample all the data. For example, most studies using Twitter data today rely on the 1% and 10% randomly sampled streams of tweets that are provided by Twitter. In this paper, we analyze a different sampling methodology, one where content is gathered only from a relatively small sample (<1%) of the user population, namely, the expert users . Over the duration of a month, we gathered tweets from over 500,000 Twitter users who are identified as experts on a diverse set of topics, and compared the resulting expert sampled tweets with the 1% randomly sampled tweets provided publicly by Twitter. We compared the sampled datasets along several dimensions, including the popularity, topical diversity, trustworthiness, and timeliness of the information contained within them, and on the sentiment/opinion expressed on specific topics. Our analysis reveals several important differences in data obtained through the different sampling methodologies, which have serious implications for applications such as topical search, trustworthy content recommendations, breaking news detection, and opinion mining.

One of the key aspects instrumental in the advancement of science relates to “team science,” or in other words “group” collaborations. There have been extensive studies analyzing various statistical properties of collaborations of individual or pairs of authors. However, the number of studies pertaining to groups/teams of scientists working together is limited in number. In this paper, we set an objective to study the productivity of group collaborations where groups are represented as small substructures usually termed as network motifs in the literature. A preliminary observation is that star-like motifs have the largest productivity (defined as a function of citation count) followed by 4-cliques. We then introduce a bunch of features and study their individual relations with the productivity of a team. Building on these observations, we develop a supervised classification model that can automatically distinguish the highly productive teams from the low productive ones based on the set of identified features. The accuracy of the classification is 82% on an average for all the motifs with the accuracy reaching as high as 95% for 4-cliques. Finally, we present a detailed analysis of the time-transition behavior of different motifs along with some of the real world highly productive motifs found in our dataset. This empirical study is a first step toward the development of a full-fledged recommendation system that can predict how productive a team would be in the future.

Many social networks are characterized by actors (nodes) holding quantitative opinions about movies, songs, sports, people, colleges, politicians, and so on. These opinions are influenced by network neighbors. Many models have been proposed for such opinion dynamics, but they have some limitations. Most consider the strength of edge influence as fixed. Some model a discrete decision or action on part of each actor, and an edge as causing an ``infection'' (that is often permanent or self-resolving). Others model edge influence as a stochastic matrix to reuse the mathematics of eigensystems. Actors' opinions are usually observed globally and synchronously. Analysis usually skirts transient effects and focuses on steady-state behavior. There is very little direct experimental validation of estimated influence models. Here we initiate an investigation into new models that seek to remove these limitations. Our main goal is to estimate, not assume, edge influence strengths from an observed series of opinion values at nodes. We adopt a linear (but not stochastic) influence model. We make no assumptions about system stability or convergence. Further, actors' opinions may be observed in an asynchronous and incomplete fashion, after missing several time steps when an actor changed its opinion based on neighbors' influence. We present novel algorithms to estimate edge influence strengths while tackling these aggressively realistic assumptions. Experiments with Reddit, Twitter, and three social games we conducted on volunteers establish the promise of our algorithms. Our opinion estimation errors are dramatically smaller than strong baselines like the DeGroot, flocking, voter, and biased voter models. Our experiments also lend qualitative insights into asynchronous opinion updates and aggregation.

We present a semantic methodology to identify topical groups in Twitter on a large number of topics, each consisting of users who are experts on or interested in a specific topic. Early studies investigating the nature of Twitter suggest that it is a social media platform consisting of a relatively small section of elite users, producing information on a few popular topics such as media, politics, and music, and the general population consuming it. We show that this characterization ignores a rich set of highly specialized topics, ranging from geology, neurology, to astrophysics and karate - each being discussed by their own topical groups. We present a detailed characterization of these topical groups based on their network structures and tweeting behaviors. Analyzing these groups on the backdrop of the common identity and bond theory in social sciences shows that these groups exhibit characteristics of topical-identity based groups, rather than social-bond based ones.

Despite the prevalence of community detection algorithms, relatively less work has been done on understanding whether a network is indeed modular and how resilient the community structure is under perturbations. To address this issue, we propose a new vertex-based metric called "permanence", that can quantitatively give an estimate of the community- like structure of the network.

We propose a novel mechanism to infer topics of interest of individual users in the Twitter social network. We observe that in Twitter, a user generally follows experts on various topics of her interest in order to acquire information on those topics. We use a methodology based on social annotations (proposed earlier by us) to first deduce the topical expertise of popular Twitter users, and then transitively infer the interests of the users who follow them. This methodology is a sharp departure from the traditional techniques of inferring interests of a user from the tweets that she posts or receives. We show that the topics of interest inferred by the proposed methodology are far superior than the topics extracted by state-of-the-art techniques such as using topic models (Labeled LDA) on tweets. Based upon the proposed methodology, we build a system Who Likes What, which can infer the interests of millions of Twitter users. To our knowledge, this is the first system that can infer interests for Twitter users at such scale. Hence, this system would be particularly beneficial in developing personalized recommender services over the Twitter platform.

We present a generic method for augmenting unsupervised query segmentation by incorporating Parts-of-Speech (POS) sequence information to detect meaningful but rare n-grams. Our initial experiments with an existing English POS tagger employing two different POS tagsets and an unsupervised POS induction technique specifically adapted for queries show that POS information can significantly improve query segmentation performance in all these cases.

Study of community in time-varying graphs has been limited to its detection and identification across time. However, presence of time provides us with the opportunity to analyze the interaction patterns of the communities, understand how each individual community grows/shrinks, becomes important over time. This paper, for the first time, systematically studies the temporal interaction patterns of communities using a large scale citation network (directed and unweighted) of computer science. Each individual community in a citation network is naturally defined by a research field -- i.e., acting as ground-truth -- and their interactions through citations in real time can unfold the landscape of dynamic research trends in the computer science domain over the last fifty years. These interactions are quantified in terms of a metric called inwardness that captures the effect of local citations to express the degree of authoritativeness of a community (research field) at a particular time instance. Several arguments to unveil the reasons behind the temporal changes of inwardness of different communities are put forward using exhaustive statistical analysis. The measurements (importance of field) are compared with the project funding statistics of NSF and it is found that the two are in sync. We believe that this measurement study with a large real-world data is an important initial step towards understanding the dynamics of cluster-interactions in a temporal environment. Note that this paper, for the first time, systematically outlines a new avenue of research that one can practice post community detection.

Several applications today rely upon content streams crowd-sourced from online social networks. Since real-time processing of large amounts of data generated on these sites is difficult, analytics companies and researchers are increasingly resorting to sampling. In this paper, we investigate the crucial question of how to sample the data generated by users in social networks. The traditional method is to randomly sample all the data. We analyze a different sampling methodology, where content is gathered only from a relatively small subset (< 1%) of the user population namely, the expert users. Over the duration of a month, we gathered tweets from over 500,000 Twitter users who are identified as experts on a diverse set of topics, and compared the resulting expert-sampled tweets with the 1% randomly sampled tweets provided publicly by Twitter. We compared the sampled datasets along several dimensions, including the diversity, timeliness, and trustworthiness of the information contained within them, and find important differences between the datasets. Our observations have major implications for applications such as topical search, trustworthy content recommendations, and breaking news detection.

A link prediction (LP) algorithm is given a graph, and has to rank, for each node, other nodes that are candidates for new linkage. LP is strongly motivated by social search and recommendation applications. LP techniques often focus on global properties (graph conductance, hitting or commute times, Katz score) or local properties (Adamic-Adar and many variations, or node feature vectors), but rarely combine these signals. Furthermore, neither of these extremes exploit link densities at the intermediate level of communities. In this paper we describe a discriminative LP algorithm that exploits two new signals. First, a co-clustering algorithm provides community level link density estimates, which are used to qualify observed links with a surprise value. Second, links in the immediate neighborhood of the link to be predicted are interpreted %at face value, but through a local model of node feature similarities. These signals are combined into a discriminative link predictor. We evaluate the new predictor using five diverse data sets that are standard in the literature. We report on significant accuracy boosts compared to standard LP methods (including Adamic-Adar and random walk). Apart from the new predictor, another contribution is a rigorous protocol for benchmarking and reporting LP algorithms, which reveals the regions of strengths and weaknesses of all the predictors studied here, and establishes the new proposal as the most robust.

In superpeer based networks, the superpeers are discovered through the process of bootstrapping, whereby resourceful peers get upgraded to superpeers. However, bootstrapping is influenced by several factors like limitation on the maximum number of connections a peer can have due to bandwidth constraints, limitation on the availability of information of existing peers due to cache size constraints and also by the attachment policy of the newly arriving peers to the resourceful peers. In this paper, we derive closed form equations that model the effect of these factors on superpeer related topological properties of the networks. Based on the model, we observe that the cache parameters and the preferentiality parameters must be suitably tuned so as to increase the fraction of superpeers in the network. Finally, we perform an empirical analysis of social networks like Twitter and Facebook using our model to obtain and derive insights for suitably bootstrapping superpeer topology.

In online social systems, users with common affiliations or interests form social groups for discussing various topical issues. We study the relationships among these social groups, which manifest through users who are common members of multiple groups, and the evolution of these relationships as new users join the groups. Focusing on a certain number of the most popular groups, we model the group memberships of users as a subclass of bipartite networks, known as Alphabetic Bipartite Networks (α-BiNs), where one of the partitions contains a fixed number of nodes (the popular groups) while the other grows unboundedly with time (new users joining the groups). Specifically, we consider the evolution of the thresholded projection of the user-group bipartite network onto the set of groups, which accurately represents the inter-group relationships. We propose and solve a preferential attachment based growth model for evolution of α-BiNs, and analytically compute the degree distribution of the thresholded projection. We further investigate whether the predictions of this model can explain the projection degree distributions of user-group networks derived from several real social systems (Livejournal, Youtube and Flickr). The study also shows that the inter-group network is tightly knit, and there is an implicit semantic hierarchy within its structure, that is clearly identified by the method of thresholding. To the best of our knowledge, this is the first attempt to analytically model the dynamical relationships among groups in online social systems.

Proliferation of wireless technology and increasing demand of data result in traffic congestion. Congestion due to wireless Internet is increasing at an exponential rate and 50% of this traffic is due to video. However, as popularity of files in Internet follows power law and people with similar interest meet/interact more frequently, there is a good probability that many users in proximity would like to download similar files. In this paper we exploit this probability and propose a scheme for collaborative download where a number of users in proximity collaborate with each other for downloading a set of files. We have also developed a prototype in android platform, with basic features of collaborative download.

In the Recommendation Problem, it is often important to find a set of items similar to a particular item or a group of items. This problem of finding similar items for the recommendation task may also be viewed as a link prediction problem in a network, where the items can be treated as the nodes. The strength of the edge connecting two items represents the similarity between the items. In this context, a central challenge is to suitably define an appropriate dissimilarity function between the items. For content based recommender systems, the dissimilarity function should take into account the individual attributes of the items. The same attribute may have different importances in different parts of the underlying network. We focus on the problem of learning a suitable dissimilarity function between items and address it by formulating it as a constrained optimization problem which captures the local weightages of the attributes in different regions of the graph. The constraints are imposed in such a way that the non-connected nodes show higher value of dissimilarity than the connected nodes. The local tuning of the weights learns the optimal value of weights in various parts of the network: from the portions having rich graph information to the portions having only content information. Detailed experimentation shows the superiority of the proposed algorithm over the Adamic Adar metric as well as logistic regression methodology.

We propose a content distribution strategy over municipal WiFi networks where Access Points (APs) collaboratively cache popular multimedia content, and disseminate them in a manner that each mobile device has the portion of the content just-in-time for playback. If successful, we envision that a child will be able to seamlessly watch a movie in a car, as her tablet downloads different parts of the movie over different WiFi APs at different times.

Finding topic experts on microblogging sites with millions of users, such as Twitter, is a hard and challenging problem. In this paper, we propose and investigate a new methodology for discovering topic experts in the popular Twitter social network. Our methodology relies on the wisdom of the Twitter crowds -- it leverages Twitter Lists, which are often carefully curated by individual users to include experts on topics that interest them and whose meta-data (List names and descriptions) provides valuable semantic cues to the experts' domain of expertise. We mined List information to build Cognos, a system for finding topic experts in Twitter. Detailed experimental evaluation based on a real-world deployment shows that: (a) Cognos infers a user's expertise more accurately and comprehensively than state-of-the-art systems that rely on the user's bio or tweet content, (b) Cognos scales well due to built-in mechanisms to efficiently update its experts' database with new users, and (c) Despite relying only on a single feature, namely crowdsourced Lists, Cognos yields results comparable to, if not better than, those given by the official Twitter experts search engine for a wide range of queries in user tests. Our study highlights Lists as a potentially valuable source of information for future content or expert search systems in Twitter.

This paper presents the first evaluation framework for Web search query segmentation based directly on IR performance. In the past, segmentation strategies were mainly validated against manual annotations. Our work shows that the goodness of a segmentation algorithm as judged through evaluation against a handful of human annotated segmentations hardly reflects its effectiveness in an IR-based setup. In fact, state-of the-art algorithms are shown to perform as good as, and sometimes even better than human annotations a fact masked by previous validations. The proposed framework also provides us an objective understanding of the gap between the present best and the best possible segmentation algorithm. We draw these conclusions based on an extensive evaluation of six segmentation strategies, including three most recent algorithms, vis-a-vis segmentations from three human annotators. The evaluation framework also gives insights about which segments should be necessarily detected by an algorithm for achieving the best retrieval results. The meticulously constructed dataset used in our experiments has been made public for use by the research community.

In this paper, we propose a simple randomized protocol for identifying trusted nodes based on personalized trust in large scale distributed networks. The problem of identifying trusted nodes, based on personalized trust, in a large network setting stems from the huge computation and message overhead involved in exhaustively calculating and propagating the trust estimates by the remote nodes. However, in any practical scenario, nodes generally communicate with a small subset of nodes and thus exhaustively estimating the trust of all the nodes can lead to huge resource consumption. In contrast, our mechanism can be tuned to locate a desired subset of trusted nodes, based on the allowable overhead, with respect to a particular user. The mechanism is based on a simple exchange of random walk messages and nodes counting the number of times they are being hit by random walkers of nodes in their neighborhood. Simulation results to analyze the effectiveness of the algorithm show that using the proposed algorithm, nodes identify the top trusted nodes in the network with a very high probability by exploring only around 45% of the total nodes, and in turn generates nearly 90% less overhead as compared to an exhaustive trust estimation mechanism, named TrustWebRank. Finally, we provide a measure of the global trustworthiness of a node; simulation results indicate that the measures generated using our mechanism differ by only around 0.6% as compared to TrustWebRank.

Recently, Twitter has emerged as a popular platform for discovering real-time information on the Web, such as news stories and people's reaction to them. Like the Web, Twitter has become a target for link farming, where users, especially spammers, try to acquire large numbers of follower links in the social network. Acquiring followers not only increases the size of a user's direct audience, but also contributes to the perceived influence of the user, which in turn impacts the ranking of the user's tweets by search engines.

WiFi clients must associate to a specific Access Point (AP) to communicate over the Internet. Current association methods are based on maximum Received Signal Strength Index (RSSI) implying that a client associates to the strongest AP around it. This is a simple scheme that has performed well in purely distributed settings. Modern wireless networks, however, are increasingly being connected by a wired backbone. The backbone allows for out-of-band communication among APs, opening up opportunities for improved protocol design. This paper takes advantage of this opportunity through a coordinated client association scheme where APs consider a global view of the network, and decide on the optimal client-AP association. We show that such an association outperforms RSSI based schemes in several scenarios, while remaining practical and scalable for wide-scale deployment. We also show that optimal association is a NP-Hard problem and our max-flow based heuristic is a promising solution.

Wireless clients must associate to a specific Access Point (AP) to communicate over the Internet. Current association methods are based on maximum Received Signal Strength Index (RSSI) implying that a client associates to the strongest AP around it. This is a simple scheme that has performed well in purely distributed settings. Modern wireless networks, however, are increasingly being connected by a wired backbone. The backbone allows for out-of-band communication among APs, opening up opportunities for improved protocol design. This paper takes advantage of this opportunity through a coordinated client association scheme where APs consider a global view of the network, and decides on the optimal client-AP association. We show that such an association outperforms RSSI based schemes in several scenarios, while remaining practical and scalable for wide-scale deployment. Although an early work in this direction, our basic analytical framework (based on a max-flow formulation) can be extended to sophisticated channel and traffic models. Our future work is focussed towards designing and evaluating these extensions.

In this paper, we develop an analytical framework which explains the emergence of superpeer networks on execution of the commercial peer-to-peer bootstrapping protocols by incoming nodes. Bootstrapping protocols exploit physical properties of the online peers like resource content, processing power, storage space, connectivity etc as well as take the finiteness of bandwidth of each online peer into consideration. With the help of rate equations, we show that execution of these protocols results in the emergence of superpeer nodes in the network - the exact degree distribution is evaluated. We validate the framework developed in this paper through extensive simulation. The analysis of the results shows that the amount of superpeers produced in the network depends on the protocol as well as the properties of the joining nodes. Interestingly, our analysis reveals that increase in the amount of resource and the number of resourceful nodes do not always help to increase the fraction of superpeer nodes in the network. The impact of the frequent leaving of the peers on the topology of the emerging network is also evaluated. As an application study, we show that our framework can explain the topological configuration of commercial Gnutella networks. The developed model can almost perfectly match the degree distribution of Gnutella network.

In this paper, we develop an analytical framework to explain the appearance of bimodal degree distribution in existing popular superpeer networks like Gnutella. The framework leads to several interesting and important inferences related to network topology and node/link dynamics. Beyond the simulation based study, we validate our framework through almost exact matching of the topological structure of Gnutella network constructed from real data.

This paper proposes a fair association scheme between clients and APs in WiFi network, exploiting the hybrid nature of the recent WLAN architecture. We show that such an association outperforms RSSI based schemes in several scenarios, while remaining practical and scalable for wide-scale deployment.

We study broadcasting of information in a system of moving agents equipped with omnidirectional as well as directional antenna. The agent communication protocol is inspired by the classical SIRS epidemics dynamics. We assume that the antennas of all agents have a fixed transmitting power, while signal reception only occurs when the receivers sense signals with power exceeding a certain threshold. Thus, information exchange is a local phenomenon which depends on the relative distance and antenna orientation between the transmitting and the receiving agent. We derive an expression for the mean broadcasting time and study the information dissemination robustness of the system using elements of classical epidemiology and physics. In particular, we show that the mean broadcasting time depends upon ¿ which quantifies the area the radiation pattern of the antenna sweeps as it moves. We report three important observations (a) directional antennas perform better than omnidirectional antennas, (b) directional antennas whose beam-width is narrower perform even better, and (c) the performance enhances a lot if directional antennas rotate. These behaviors can be understood in the light of the reported analytical findings.

We propose a hybridization of collaborative filtering and content based recommendation system. Attributes used for content based recommendations are assigned weights depending on their importance to users. The weight values are estimated from a set of linear regression equations obtained from a social network graph which captures human judgment about similarity of items.

In this paper, we develop an analytical framework to measure the vulnerability of superpeer networks against attack. Two different kinds of attacks namely deterministic and degree dependent attack have been introduced here. We formally model the superpeer networks with the help of bimodal structure and different attacks with the help of graph dynamics. Our analysis shows that fraction of superpeers and their connectivity have profound impact upon the stability of the network. The results obtained from the theoretical analysis are validated through simulation. The agreement between the simulation results and theoretical predictions is almost perfect.

Many previous works of Peer-to-Peer traffic characterization and modeling focused their attention on the distribution of query contents. However, few has been done towards a better understanding of the time series distribution of these queries, which is vital for system performance. To remedy this situation, this paper characterizes query traffic by using automatic time series analysis to evaluate different linear models(Box-Jenkins models and some simple windowed-mean models) for predicting the number of duplicated queries from 10 minutes to 2 hours into the future. Both the predictive power and the computational costs of these models are evaluated over 318,942,450 real world Gnutella queries collected over 3 months. We find the number of duplicated queries is consistently predictable. Simple, practical models like AR perform well on prediction. To show that these characteristics have a wide range of potential applications, we propose two enhancement to existing search results caching and load balancing algorithms. Our simulation study shows that our methodology works quite well in both scenarios in terms of efficiency and effectiveness. The main contribution of this paper lies in: (1) proposing new measurement techniques on Gnutella, (2) characterizing and modeling peer-to-peer query traffic with Box-Jenkins Models, (3) presenting a general enhancement to existing performance optimization algorithm in P2P systems.

No abstract available.

Recent developments in information technology have brought about important changes in distributed computing. New environments such as massively large-scale, wide-area computer networks and mobile ad hoc networks have emerged. Common characteristics of these environments include extreme dynamicity, unreliability, and large scale. Traditional approaches to designing distributed applications in these environments based on central control, small scale, or strong reliability assumptions are not suitable for exploiting their enormous potential. Based on the observation that living organisms can effectively organize large numbers of unreliable and dynamically-changing components (cells, molecules, individuals, etc.) into robust and adaptive structures, it has long been a research challenge to characterize the key ideas and mechanisms that make biological systems work and to apply them to distributed systems engineering. In this article we propose a conceptual framework that captures several basic biological processes in the form of a family of design patterns. Examples include plain diffusion, replication, chemotaxis, and stigmergy. We show through examples how to implement important functions for distributed computing based on these patterns. Using a common evaluation methodology, we show that our bio-inspired solutions have performance comparable to traditional, state-of-the-art solutions while they inherit desirable properties of biological systems including adaptivity and robustness.

This paper reports a fault diagnosis scheme for very large scale integrated (VLSI) circuits. A special class of cellular automata (CA) referred to as multiple attractor CA (MACA) is employed for the design. State transition behavior of MACA has been analyzed to build a model that can efficiently classify the test responses of a VLSI circuit to diagnose its faulty subcircuit. The MACA-based model, in effect, provides an implicit storage for voluminous test response data and replaces the traditional fault dictionary used for diagnosis of VLSI circuits. The proposed diagnosis scheme employs significantly lesser memory to store the MACA parameters and performs faster diagnosis. Experimental results establish the efficiency of the model in respect of memory overhead, execution speed and percentage of diagnosis.

This work reports the design of a fool proof on-chip test pattern generator (TPG) for very large scale integration circuits. The TPG is designed to generate pseudorandom test patterns without a given prohibited pattern set (PPS). It ensures desired pseudorandom quality of the generated test patterns and maintains fault coverage close to the figures achieved with a conventional maximal length linear feedback shift register/cellular automaton (CA)-based TPG. The theory of vector subspace generated by a CA (Chaudhuri, 1997) has provided the foundation of this design. The proposed TPG does not incur any additional cost for the avoidance of PPS.

This paper reports a cellular automata (CA) based model of associative memory. The model has been evolved around a special class of CA referred to as generalized multiple attractor cellular automata (GMACA). The GMACA based associative memory is designed to address the problem of pattern recognition. Its storage capacity is found to be better than that of Hopfield network. The GMACA are configured with nonlinear CA rules that are evolved through genetic algorithm (GA). Successive generations of GA select the rules at the edge of chaos. The study confirms the potential of GMACA to perform complex computations like pattern recognition at the edge of chaos.

This paper reports the error correcting capability of an associative memory model built around the sparse network of cellular automata (CA). Analytical formulation supported by experimental results has demonstrated the capability of CA based sparse network to memorize unbiased patterns while accommodating noise. The desired CA are evolved with an efficient formulation of simulated annealing (SA) program. The simple, regular, modular, and cascadable structure of CA based associative memory suits ideally for design of low cost high speed online pattern recognizing machine with the currently available VLSI technology.

This paper reports the design of an on-chip Test Pattern Generator (TPG) for VLSI circuits that avoids generation of a given Prohibited Pattern Set (PPS). The design ensures desired pseudo-random quality of the test patterns generated while ensuring fault coverage close to the figures achieved with a typical Pseudo Random Pattern Generator (PRPG) designed around maximal length LFSR/CA. The theoretical framework of CA has provided the foundation of this work. A GA based evolution scheme is employed to achieve the desired TPG developed over the theory of cellular automata.

This paper reports an efficient technique of evolving Cellular Automata (CA) as an associative memory model. The evolved CA termed as GMACA (Generalized Multiple Attractor Cellular Automata), acts as a powerful pattern recognizer. Detailed analysis of GMACA rules establishes the fact that the rule subspace of the pattern recognizing CA lies at the edge of chaos — believed to be capable of executing complex computation.

This paper introduces the concept of hierarchical cellular automata (HCA). The theory of HCA is developed over the Galois extension field GF(2(pqr..)), where each cell of the CA can store and process a symbol in the extension field GF (2(pqr..)). The hierarchical field structure of GF(2(pqr..)) is employed for design of an HCA-based test pattern generator (HCATPG). The HCATPG is ideally suited for testing very large scale integration circuits specified in hierarchical structural description. Experimental results establish the fact that the HCATPG achieves higher fault coverage than that which could be achieved with any other test structures. The concept of percentile improvement in fault coverage is introduced to have a realistic assessment of fault coverage achieved with the proposed RCATPG.

This paper uses the hierarchical structure of a VLSI circuit to design an efficient diagnosis scheme. A special class of non-group GF(2/sup p/) CA referred to as multiple attractor cellular automata (MACH) is introduced to diagnose the faulty block of a circuit under test (CUT). The scheme employs significantly lesser memory and performs faster diagnosis than the existing methods reported so far. Experimental results validate the efficiency of the proposed scheme in terms of diagnostic resolution and execution speed along with significant reduction of memory.