5,115 research outputs found
Intersectional fair ranking via subgroup divergence
No full textSocietal biases encoded in real-world data can contaminate algorithmic decisions, perpetuating preexisting inequalities in domains such as employment and education. In the fair ranking literature, following the doctrine of affirmative action, fairness is enforced by means of a group-fairness constraint requiring "enough" individuals from protected groups in the top-k positions, for a ranking to be considered valid. However, which are the groups that need to be protected? And how much representation is "enough"? As the biases affecting the process may not always be directly observable nor measurable, these questions might be hard to answer in a principled way, especially when many different potentially discriminated subgroups exist. This paper addresses this issue by automatically identifying the disadvantaged groups in the data and mitigating their disparate representation in the final ranking. Our proposal leverages the notion of divergence to automatically identify which subgroups, defined as combination of sensitive attributes, show a statistically significant deviation, in terms of ranking utility, compared to the overall population. Subgroups with negative divergence experience a disadvantage. We formulate the problem of re-ranking instances to maximize the minimum subgroup divergence, while maintaining the new ranking as close as possible to the original one. We develop a method which is based on identifying the divergent subgroups and applying a re-ranking procedure which is monotonic w.r.t. the goal of maximizing the minimum divergence. Our experimental results show that our method effectively eliminates the existence of disadvantaged subgroups while producing rankings which are very close to the original ones
Soft Constraint Based Pattern Mining
No full textThe paradigm of pattern discovery based on constraints was introduced with the aim of providing to the user a tool to drive the discovery process towards potentially interesting patterns, with the positive side effect of achieving a more efficient computation. So far the research on this paradigm has mainly focused on the latter aspect: the development of efficient algorithms for the evaluation of constraint-based mining queries. Due to the lack of research on methodological issues, the constraint-based pattern mining framework still suffers from many problems which limit its practical relevance. In this paper, we analyze such limitations and we show how they flow out from the same source: the fact that in the classical constraint-based mining, a constraint is a rigid boolean function which returns either true or false. Indeed, interestingness is not a dichotomy. Following this consideration, we introduce the new paradigm of pattern discovery based on Soft Constraints, where constraints are no longer rigid boolean functions.
Albeit based on a simple idea, our proposal has many merits: it provides a rigorous theoretical framework, which is very general (having the classical paradigm as a particular instance), and which overcomes all the major methodological drawbacks of the classical constraint-based paradigm, representing an important step further towards practical pattern discovery
How Low Interest Rates Discern the Bubbles Nature: Leveraged vs Unleveraged Bubble
No full textLeveraged asset price bubbles, i.e., boom-bust phases in asset prices accompanied by credit overhangs, are more harmful than unleveraged ones, in terms of financial and macroeconomic stability. If bubbles are not all alike, neither are all bubbles likely? As bubbles are difficult to detect in real-time data, early researches focused on the macroeconomic conditions exacerbating the bubbles' nature. We specifically look at a condition that could become more persistent in the aftermath of COVID-19 pandemic: low risk-free interest rates. In an OLG model, we show that the existence condition for a leveraged bubble is more easily met than that of an unleveraged bubble with low interest rates, and thus leveraged bubbly episodes are relatively more likely to emerge than unleveraged ones. Then, we show that this result holds empirically for post-World War II bubbles in advanced economies
How Low Interest Rates Discern the Bubbles Nature: Leveraged vs Unleveraged Bubble
No full textLeveraged asset price bubbles, i.e., boom-bust phases in asset prices accompanied by credit overhangs, are more harmful than unleveraged ones, in terms of financial and macroeconomic stability. If bubbles are not all alike, neither are all bubbles likely? As bubbles are difficult to detect in real-time data, early researches focused on the macroeconomic conditions exacerbating the bubbles' nature. We specifically look at a condition that could become more persistent in the aftermath of COVID-19 pandemic: low risk-free interest rates. In an OLG model, we show that the existence condition for a leveraged bubble is more easily met than that of an unleveraged bubble with low interest rates, and thus leveraged bubbly episodes are relatively more likely to emerge than unleveraged ones. Then, we show that this result holds empirically for post-World War II bubbles in advanced economies
The Effect of Homophily on Disparate Visibility of Minorities in People Recommender Systems
No full textEvaluating (and mitigating) the potential negative effects of algorithms has become a central issue in computer science. While research on algorithmic bias in ranking systems has dealt with disparate exposure of products or individuals, less attention has been devoted to the analysis of the disparate exposure of subgroups of online users.In this paper, we investigate the visibility of minorities in people recommender systems in social networks. Specifically, we consider a bi-populated social network, i.e., a graph where the nodes belong to two different groups (majority and minority) and, by applying state-of-the-art people recommenders, we analyze how disparate visibility can be amplified or mitigated by different levels of homophily within each subgroup.We start our analysis on real-world social graphs, where the two subgroups are defined by sensitive demographic attributes such as gender or age. Our findings suggest that the way and the extent to which people recommenders can produce disparate visibility on the two subgroups, might depend in large part on the level of homophily within the subgroups. % To verify these findings, we move our analysis to synthetic datasets, where we can control characteristics of the input social graph, such as the size of the minority and the level of homophily. Our results show that homophily plays a key role in promoting or reducing visibility for different subgroups under various combinations of dataset characteristics and recommendation algorithms
Identifying Buzzing Stories via Anomalous Temporal Subgraph Discovery
No full textStory identification from online user-generated content has recently raised increasing attention. Existing approaches fall into two categories. Approaches in the first category extract stories as cohesive substructures in a graph representing the strength of association between terms. The latter category includes approaches that analyze the temporal evolution of individual terms and identify stories by grouping terms with similar anomalous temporal behavior. Both categories have limitations. In this work we advance the literature on story identification by devising a novel method that profitably combines the peculiarities of the two main existing approaches, thus also addressing their weaknesses. Experiments on a dataset extracted from a real-world web-search log demonstrate the superiority of the proposed method over the state of the art. © 2016 IEEE
Explainable Classification of Brain Networks via Contrast Subgraphs
No full textMining human-brain networks to discover patterns that can be used to discriminate between healthy individuals and patients affected by some neurological disorder, is a fundamental task in neuro-science. Learning simple and interpretable models is as important as mere classification accuracy. In this paper we introduce a novel approach for classifying brain networks based on extracting contrast subgraphs, i.e., a set of vertices whose induced subgraphs are dense in one class of graphs and sparse in the other. We formally define the problem and present an algorithmic solution for extracting contrast subgraphs. We then apply our method to a brain-network dataset consisting of children affected by Autism Spectrum Disorder and children Typically Developed. Our analysis confirms the interestingness of the discovered patterns, which match background knowledge in the neuro-science literature. Further analysis on other classification tasks confirm the simplicity, soundness, and high explainability of our proposal, which also exhibits superior classification accuracy, to more complex state-of-the-art methods
Rebalancing Social Feed to Minimize Polarization and Disagreement
No full textSocial media have great potential for enabling public discourse on important societal issues. However, adverse effects, such as polarization and echo chambers, greatly impact the benefits of social media and call for algorithms that mitigate these effects. In this paper, we propose a novel problem formulation aimed at slightly nudging users' social feeds in order to strike a balance between relevance and diversity, thus mitigating the emergence of polarization, without lowering the quality of the feed. Our approach is based on re-weighting the relative importance of the accounts that a user follows, so as to calibrate the frequency with which the content produced by various accounts is shown to the user.
We analyze the convexity properties of the problem, demonstrating the non-matrix convexity of the objective function and the convexity of the feasible set. To efficiently address the problem, we develop a scalable algorithm based on projected gradient descent. We also prove that our problem statement is a proper generalization of the undirected-case problem so that our method can also be adopted for undirected social networks. As a baseline for comparison in the undirected case, we develop a semidefinite programming approach, which provides the optimal solution. Through extensive experiments on synthetic and real-world datasets, we validate the effectiveness of our approach, which outperforms non-trivial baselines, underscoring its ability to foster healthier and more cohesive online communities
- …
