<p>Recent years have seen a great deal of effort in the area of developing fair machine learning algorithms. The definition of ‘fair’ varies, but often, the focus is along the lines of ensuring that algorithms do not systematically discriminate against individuals on the basis of their <i>protected attributes</i>-e.g., those describing race or gender. However, although there are numerous important network applications, comparatively little attention has been paid to fairness in network algorithms. Here, we focus on the problem of <i>fair dense subgraph discovery</i> in networks. Dense subgraph discovery is often used as a first step in applications like community detection or influence maximization. However, as we show, unfairness in the structure of the dense subgraphs may propagate to those downstream applications, magnifying any unfairness in those subsequent algorithmic processes. We propose properties by which one may quantify the fairness of a subgraph, introduce algorithms connected to these fairness objectives, analyze the properties of the resulting subgraphs, and demonstrate their use with respect to applications.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Fair dense subgraph discovery: algorithms and analysis

  • Danylo Honcharov,
  • Sucheta Soundarajan

摘要

Recent years have seen a great deal of effort in the area of developing fair machine learning algorithms. The definition of ‘fair’ varies, but often, the focus is along the lines of ensuring that algorithms do not systematically discriminate against individuals on the basis of their protected attributes-e.g., those describing race or gender. However, although there are numerous important network applications, comparatively little attention has been paid to fairness in network algorithms. Here, we focus on the problem of fair dense subgraph discovery in networks. Dense subgraph discovery is often used as a first step in applications like community detection or influence maximization. However, as we show, unfairness in the structure of the dense subgraphs may propagate to those downstream applications, magnifying any unfairness in those subsequent algorithmic processes. We propose properties by which one may quantify the fairness of a subgraph, introduce algorithms connected to these fairness objectives, analyze the properties of the resulting subgraphs, and demonstrate their use with respect to applications.