We present an unsupervised method for aggregating anomalies in tabular datasets by identifying the top-k tabular data quality insights. Each insight consists of a set of anomalous attributes and the corresponding subsets of records that serve as evidence to the user. The process of identifying these insight blocks is challenging due to (i) the absence of labeled anomalies, (ii) the exponential size of the subset search space, and (iii) the complex dependencies among attributes, which obscure the true sources of anomalies. Simple frequency-based methods fail to capture these dependencies, leading to inaccurate results. To address this, we introduce Tab-Shapley, a cooperative game theory based framework that uses Shapley values to quantify the contribution of each attribute to the data's anomalous nature. While calculating Shapley values typically requires exponential time, we show that our game admits a closed-form solution, making the computation efficient. We validate the effectiveness of our approach through empirical analysis on real-world tabular datasets with ground-truth anomaly labels.

Unsupervised Representation Learning on graphs is gaining traction due to the increasing abundance of unlabelled network data and the compactness, richness, and usefulness of the representations generated. In this context, the need to consider fairness and bias constraints while generating the representations has been well-motivated and studied to some extent in prior works. One major limitation of most of the prior works in this setting is that they do not aim to address the bias generated due to connectivity patterns in the graphs, such as varied node centrality, which leads to a disproportionate performance across nodes. In our work, we aim to address this issue of mitigating bias due to inherent graph structure in an unsupervised setting. To this end, we propose CAFIN, a centrality-aware fairness-inducing framework that leverages the structural information of graphs to tune the representations generated by existing frameworks. We deploy it on GraphSAGE (a popular framework in this domain) and showcase its efficacy on two downstream tasks – Node Classification and Link Prediction. Empirically, CAFIN consistently reduces the performance disparity across popular datasets (varying from 18 to 80% reduction in performance disparity) from various domains while incurring only a minimal cost of fairness.

Federated Learning (FL) is a machine learning paradigm in which multiple clients participate to collectively learn a global machine learning model at the central server. It is plausible that not all the data owned by each client is relevant to the server's learning objective. The updates incorporated from irrelevant data could be detrimental to the global model. The task of selecting relevant data is explored in traditional machine learning settings where the assumption is that all the data is available in one place. In FL settings, the data is distributed across multiple clients and the server can't introspect it. This precludes the application of traditional solutions to selecting relevant data here. In this paper, we propose an approach called Federated Learning with Relevant Data (FLRD), that facilitates clients to derive updates using relevant data. Each client learns a model called Relevant Data Selector (RDS) that is private to itself to do the selection. This in turn helps in building an effective global model. We perform experiments with multiple real-world datasets to demonstrate the efficacy of our solution. The results show (a) the capability of FLRD to identify relevant data samples at each client locally and (b) the superiority of the global model learned by FLRD over other baseline algorithms.

The paradigm of Federated learning (FL) deals with multiple clients participating in collaborative training of a machine learning model under the orchestration of a central server. In this setup, each client’s data is private to itself and is not transferable to other clients or the server. Though FL paradigm has received significant interest recently from the research community, the problem of selecting the relevant clients w.r.t. the central server's learning objective is under-explored. We refer to these problems as Federated Relevant Client Selection (FRCS). Because the server doesn't have explicit control over the nature of data possessed by each client, the problem of selecting relevant clients is significantly complex in FL settings. In this paper, we resolve important and related FRCS problems viz., selecting clients with relevant data, detecting clients that possess data relevant to a particular target label, and rectifying corrupted data samples of individual clients. We follow a principled approach to address the above FRCS problems and develop a new federated learning method using the Shapley value concept from cooperative game theory. Towards this end, we propose a cooperative game involving the gradients shared by the clients. Using this game, we compute Shapley values of clients and then present Shapley value based Federated Averaging (S-FedAvg) algorithm that empowers the server to select relevant clients with high probability. S-FedAvg turns out to be critical in designing specific algorithms to address the FRCS problems. We finally conduct a thorough empirical analysis on image classification and speech recognition tasks to show the superior performance of S-FedAvg than the baselines in the context of supervised federated learning settings.

To make ML systems deployment ready, one of the prominent challenges is to debug the performance issues of the trained ML models. This can be done by associating the issues with a set of Data Slices - aggregates of validation data records - to help the developers investigate these technical issues at a deeper level of granularity. Since the possible number of data slices are exponential in number, there is a need to prioritize the order (i.e. ranking) of slices before presenting to the users. However, there does not exist any work that deals with ranking these automatically generated slices and we refer to this problem as the data slice ranking problem (DSRP). This problem is challenging to address as the top ranked slices should contain significant error concentration (i.e. number of mis-classified data points), be statistically significant (i.e. having large size), and be non-redundant (i.e. contain unique mis-classified data points). In this paper, we tackle this challenging problem by proposing a novel game theoretic framework building upon Shapley value concept to derive a rank order for a given collection of data slices. In particular, we formally present a scheme that explicitly accounts only for the error concentration and we refer to this as Shapley Slice Ranking with Error concentration (SSR-E). We then prove a few useful properties of this scheme. Using thorough experimentation on 7 open source data sets, we demonstrate the superior performance of SSR mechanism vis-à-vis two baseline methods.

We study the complexity of equilibrium computation in discrete preference games. These games were introduced by Chierichetti, Kleinberg, and Oren (EC '13, JCSS '18) to model decision-making by agents in a social network that choose a strategy from a finite, discrete set, balancing between their intrinsic preferences for the strategies and their desire to choose a strategy that is `similar' to their neighbours. There are thus two components: a social network with the agents as vertices, and a metric space of strategies. These games are potential games, and hence pure Nash equilibria exist. Since their introduction, a number of papers have studied various aspects of this model, including the social cost at equilibria, and arrival at a consensus. We show that in general, equilibrium computation in discrete preference games is PLS-complete, even in the simple case where each agent has a constant number of neighbours. If the edges in the social network are weighted, then the problem is PLS-complete even if each agent has a constant number of neighbours, the metric space has constant size, and every pair of strategies is at distance 1 or 2. Further, if the social network is directed, modelling asymmetric influence, an equilibrium may not even exist. On the positive side, we show that if the metric space is a tree metric, or is the product of path metrics, then the equilibrium can be computed in polynomial time.

Measuring influence, through centrality measures, has been a center-piece of research in the analysis of complex social networks, such as finding coherent communities (clusters) and locating trend setters (prototypes) in viral marketing. Even though there exists a few axiomatic frameworks associated with some specific forms of influence measures in the literature, these formal frameworks are not generic in nature in terms of characterizing the space of influence measures for complex social networks. To address this research gap, we propose a generic axiomatic framework, in this paper, to capture most of the key intrinsic properties of any influence measure in networks. We further analyze certain popular centrality measures using this framework. Interestingly, our analysis reveals that none of the centrality measures considered satisfies all the desirable axioms. We finally conclude this paper by stating an appealing conjecture on a potential impossibility theorem associated with the proposed axiomatic framework.

In electricity markets, the choice of the right pricing regime is crucial for the utilities because the price they charge to their consumers, in anticipation of their demand in real-time, is a key determinant of their profits and ultimately their survival in competitive energy markets. Among the existing pricing regimes, in this paper, we consider ex-ante dynamic pricing schemes as (i) they help to address the peak demand problem (a crucial problem in smart grids), and (ii) they are transparent and fair to consumers as the cost of electricity can be calculated before the actual consumption. In particular, we propose an axiomatic framework that establishes the conceptual underpinnings of the class of ex-ante dynamic pricing schemes. We first propose five key axioms that reflect the criteria that are vital for energy utilities and their relationship with consumers. We then prove an impossibility theorem to show that there is no pricing regime that satisfies all the five axioms simultaneously. We also study multiple cost functions arising from various pricing regimes to examine the subset of axioms that they satisfy. We believe that our proposed framework in this paper is first of its kind to evaluate the class of ex-ante dynamic pricing schemes in a manner that can be operationalised by energy utilities.

We propose Shapley Value based centrality measures for signed social networks. We also demonstrate that they lead to improved precision for the troll detection task.

Research accomplishment is usually measured by considering all citations with equal importance, thus ignoring the wide variety of purposes an article is being cited for. Here, we posit that measuring the intensity of a reference is crucial not only to perceive better understanding of research endeavor, but also to improve the quality of citation-based applications. To this end, we collect a rich annotated dataset with references labeled by the intensity, and propose a novel graph-based semi-supervised model, GraLap to label the intensity of references. Experiments with AAN datasets show a significant improvement compared to the baselines to achieve the true labels of the references (46% better correlation). Finally, we provide four applications to demonstrate how the knowledge of reference intensity leads to design better real-world applications.

Several real-life social systems witness the presence of multiple interaction types (or layers) among the entities, thus establishing a collection of co-evolving networks, known as multiplex networks. More recently, there has been a significant interest in developing certain centrality measures in multiplex networks to understand the influential power of the entities (to be referred as vertices or nodes hereafter). In this paper, we consider the problem of studying how frequently the nodes occur on the shortest paths between other nodes in the multiplex networks. As opposed to simplex networks, the shortest paths between nodes can possibly traverse through multiple layers in multiplex networks. Motivated by this phenomenon, we propose a new metric to address the above problem and we call this new metric cross-layer betweenness centrality (CBC). Our definition of CBC measure takes into account the interplay among multiple layers in determining the shortest paths in multiplex networks. We propose an efficient algorithm to compute CBC and show that it runs much faster than the naïve computation of this measure. We show the efficacy of the proposed algorithm using thorough experimentation on two real-world multiplex networks. We further demonstrate the practical utility of CBC by applying it in the following three application contexts: discovering non-overlapping community structure in multiplex networks, identifying interdisciplinary researchers from a multiplex co-authorship network, and the initiator selection for message spreading. In all these application scenarios, the respective solution methods based on the proposed CBC are found to be significantly better performing than that of the corresponding benchmark approaches.

Performing literature survey for scholarly activities has become a challenging and time consuming task due to the rapid growth in the number of scientific articles. Thus, automatic recommendation of high quality citations for a given scientific query topic is immensely valuable. The state-of-the-art on the problem of citation recommendation suffers with the following three limitations. First, most of the existing approaches for citation recommendation require input in the form of either the full article or a seed set of citations, or both. Nevertheless, obtaining the recommendation for citations given a set of keywords is extremely useful for many scientific purposes. Second, the existing techniques for citation recommendation aim at suggesting prestigious and well-cited articles. However, we often need recommendation of diversified citations of the given query topic for many scientific purposes; for instance, it helps authors to write survey papers on a topic and it helps scholars to get a broad view of key problems on a topic. Third, one of the problems in the keyword based citation recommendation is that the search results typically would not include the semantically correlated articles if these articles do not use exactly the same keywords. To the best of our knowledge, there is no known citation recommendation system in the literature that addresses the above three limitations simultaneously. In this paper, we propose a novel citation recommendation system called DiSCern to precisely address the above research gap. DiSCern finds relevant and diversified citations in response to a search query, in terms of keyword(s) to describe the query topic, while using only the citation graph and the keywords associated with the articles, and no latent information. We use a novel keyword expansion step, inspired by community finding in social network analysis, in DiSCern to ensure that the semantically correlated articles are also included in the results. Our proposed approach primarily builds on the Vertex Reinforced Random Walk (VRRW) to balance prestige and diversity in the recommended citations. We demonstrate the efficacy of DiSCern empirically on two datasets: a large publication dataset of more than 1.7 million articles in computer science domain and a dataset of more than 29,000 articles in theoretical high-energy physics domain. The experimental results show that our proposed approach is quite efficient and it outperforms the state-of-the-art algorithms in terms of both relevance and diversity.

Inspired by emerging applications of social networks, we introduce in this paper a new centrality measure termed gate-keeper centrality. The new centrality is based on the well-known game-theoretic concept of Shapley value and, as we demonstrate, possesses unique qualities compared to the existing metrics. Furthermore, we present a dedicated approximate algorithm, based on the Monte Carlo sampling method, to compute the gatekeeper centrality. We also consider two well known applications in social network analysis, namely community detection and limiting the spread of mis-information; and show the merit of using the proposed framework to solve these two problems in comparison with the respective benchmark algorithms.

Bugs are inevitable in software projects. Resolving bugs is the primary activity in software maintenance. Developers, who fix bugs through code changes, are naturally important participants in bug resolution. However, there are other participants in these projects who do not perform any code commits. They can be reporters reporting bugs; people having a deep technical know-how of the software and providing valuable insights on how to solve the bug; bug-tossers who re-assign the bugs to the right set of developers. Even though all of them act on the bugs by tossing and commenting, not all of them may be crucial for bug resolution. In this paper, we formally define essential non-committers and try to identify these bug resolution catalysts. We empirically study 98304 bug reports across 11 open source and 5 commercial software projects for validating the existence of such catalysts. We propose a network analysis based approach to construct a Minimal Essential Graph that identifies such people in a project. Finally, we suggest ways of leveraging this information for bug triaging and bug report summarization.

Our study concerns an important current problem, that of diffusion of information in social networks. This problem has received significant attention from the Internet research community in the recent times, driven by many potential applications such as viral marketing and sales promotions. In this paper, we focus on the target set selection problem, which involves discovering a small subset of influential players in a given social network, to perform a certain task of information diffusion. The target set selection problem manifests in two forms: 1) top-knodes problem and 2) λ -coverage problem. In the top-knodes problem, we are required to find a set ofkkey nodes that would maximize the number of nodes being influenced in the network. The λ-coverage problem is concerned with finding a set of key nodes having minimal size that can influence a given percentage λ of the nodes in the entire network. We propose a new way of solving these problems using the concept of Shapley value which is a well known solution concept in cooperative game theory. Our approach leads to algorithms which we call the ShaPley value-based Influential Nodes (SPINs) algorithms for solving the top-knodes problem and the λ -coverage problem. We compare the performance of the proposed SPIN algorithms with well known algorithms in the literature. Through extensive experimentation on four synthetically generated random graphs and six real-world data sets (Celegans, Jazz, NIPS coauthorship data set, Netscience data set, High-Energy Physics data set, and Political Books data set), we show that the proposed SPIN approach is more powerful and computationally efficient.

Nodes in an ad hoc wireless network incur certain costs for forwarding packets since packet forwarding consumes the resources of the nodes. If the nodes are rational, free packet forwarding by the nodes cannot be taken for granted and incentive based protocols are required to stimulate cooperation among the nodes. Existing incentive based approaches are based on the VCG (Vickrey-Clarke-Groves) mechanism which leads to high levels of incentive budgets and restricted applicability to only certain topologies of networks. Moreover, the existing approaches have only focused on unicast and multicast. Motivated by this, we propose an incentive based broadcast protocol that satisfies Bayesian incentive compatibility and minimizes the incentive budgets required by the individual nodes. The proposed protocol, which we call BIC-B (Bayesian incentive compatible broadcast) protocol, also satisfies budget balance. We also derive a necessary and sufficient condition for the ex-post individual rationality of the BIC-B protocol. The BIC-B protocol exhibits superior performance in comparison to a dominant strategy incentive compatible broadcast protocol.

In this thesis work, we design rigorous and efficient protocols/mechanisms for different types of wireless networks using a mechanism design [1] and game theoretic approach [2]. Our work can broadly be viewed in two parts. In the first part, we concentrate on ad hoc wireless networks [3] and [4]. In particular, we consider broadcast in these networks where each node is owned by independent and selfish users. Being selfish, these nodes do not forward the broadcast packets. All existing protocols for broadcast assume that nodes forward the transit packets. So, there is need for developing new broadcast protocols to overcome node selfishness. In our paper [5], we develop a strategy proof pricing mechanism which we call immediate predecessor node pricing mechanism (IPNPM) and an efficient new broadcast protocol based on IPNPM. We show the efficacy of our proposed broadcast protocol using simulation results.