## Abstract

In the densest subgraph problem, given an undirected graph G(V, E, w) with non-negative edge weights we are asked to find a set of nodes S⊆V that maximizes the degree density w(S)/|S|, where w(S) is the sum of the weights of the edges in the graph induced by S. This problem is solvable in polynomial time, and in general is well studied. But what happens when the edge weights are negative? Is the problem still solvable in polynomial time? Also, why should we care about the densest subgraph problem in the presence of negative weights? In this work we answer the aforementioned questions. Specifically, we provide two novel graph mining primitives that are applicable to a wide variety of applications. Our primitives can be used to answer questions such as “how can we find a dense subgraph in Twitter with lots of replies and mentions but no follows?”, “how do we extract a dense subgraph with high expected reward and low risk from an uncertain graph”? We formulate both problems mathematically as special instances of dense subgraph discovery in graphs with negative weights. We study the hardness of the problem, and we prove that the problem in general is NP-hard, but we also provide sufficient conditions under which it is poly-time solvable. We design an efficient approximation algorithm that works best in the presence of small negative weights, and an effective heuristic for the more general case. Finally, we perform experiments on various real-world datasets that verify the value of the proposed primitives, and the effectiveness of our proposed algorithms. The code and the data are available at https://github.com/nega-tivedsd.

Original language | English |
---|---|

Title of host publication | Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2019, Proceedings |

Editors | Ulf Brefeld, Elisa Fromont, Andreas Hotho, Arno Knobbe, Marloes Maathuis, Céline Robardet |

Publisher | Springer |

Pages | 378-394 |

Number of pages | 17 |

ISBN (Print) | 9783030461492 |

DOIs | |

Publication status | Published - 2020 |

Event | European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2019 - Wurzburg, Germany Duration: 2019 Sept 16 → 2019 Sept 20 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 11906 LNAI |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2019 |
---|---|

Country/Territory | Germany |

City | Wurzburg |

Period | 19/9/16 → 19/9/20 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science