Very recent developments in dense subgraph discovery

Tuesday, October 30, 2018

2.30 p.m.

ISI seminar room 1st floor

Dr. Atsushi Miyauchi, RIKEN Center for Advanced Intelligence Project

Finding a dense component in a graph is an important primitive in graph mining, which has many real-world applications in diverse domains. The most popular optimization model for dense subgraph discovery is the densest subgraph problem. In this problem, given an edge-weighted undirected graph G = (V,E,w), we are asked to find a vertex subset S that maximizes the average weighted degree of G[S]. In this talk, we will present our (very) recent developments in dense subgraph discovery.
In the first half, we propose an optimization model for finding a community that is densely connected internally but sparsely connected to the rest of the graph. The model extends the densest subgraph problem, in which we maximize the density while minimizing the average cut size. We first design two polynomial-time exact algorithms based on linear programming and a maximum flow algorithm, respectively. Moreover, to deal with larger-sized graphs in practice, we present a scalable greedy algorithm that runs in almost linear time with theoretical performance guarantee of the output. In addition, we show that our algorithms can also be used to find global community structure in a graph. Computational experiments using well-known real-world graphs demonstrate that our algorithms are highly effective in finding a suitable community in a graph.
In the second half, we provide a framework for dense subgraph discovery under the uncertainty of edge weights. In the densest subgraph problem, there is an implicit unrealistic assumption; it is assumed that all edge weights are known exactly as input. In real-world applications, there are often cases where we have only uncertain information of edge weights. We address such an uncertainty issue using the theory of robust optimization. We first formulate our basic problem, the robust densest subgraph problem, and present a simple algorithm. We then formulate the robust densest subgraph problem with sampling oracle that models dense subgraph discovery with the use of an edge-weight sampling oracle, and present an algorithm with a strong theoretical performance guarantee. With experiments using both synthetic graphs and well-known real-world graphs, we demonstrate the effectiveness of our proposed algorithms under the uncertainty.
This talk is based on a joint work with Naonori Kakimura (Keio University) and a joint work with Akiko Takeda (The University of Tokyo / RIKEN AIP).