Efficient computation of cohesive subgraphs on bipartite graphs

Abstract

A bipartite graph is a graph with two layers such that vertices in the same layer are not connected, which is widely used to model the relationships among two types of entities. Examples of bipartite graphs include author-paper networks, customer-product networks, and ecological networks (e.g., the predator-prey network and the plant-animal network). In bipartite graphs, cohesive subgraph computation is a fundamental problem that aims to find closely-connected subgraphs, which can be applied to group recommendations, network visualization, and fraud detection. In this thesis, we propose a novel cohesive subgraph model called τ -strengthened (α, β)- core (denoted as (α, β)τ -core), which is the first work to consider both tie strength and vertex engagement on bipartite graphs. An edge is a strong tie if contained in at least τ butterflies (2 x 2-bicliques). (α, β)τ -core requires each vertex on the upper or lower level to have at least α or β strong ties, given strength level τ. To retrieve the vertices of (α, β)τ -core optimally, we construct index Iα,β,τ to store all (α, β)τ -cores. Effective optimization techniques are proposed to improve index construction. To make our idea practical on large graphs, we propose 2D-indexes Iα,β, Iβ,τ, and Iα,τ that selectively store the vertices of (α, β)τ -core for some α, β, and τ . The 2D-indexes are more space-efficient and require less construction time, each of which can support (α, β)τ -core queries. As query efficiency depends on input parameters and the choice of 2D-index, we propose a learning-based hybrid computation paradigm by training a feed-forward neural network to predict the optimal choice of 2D-index that minimizes the query time. Extensive experiments show that (1) (α, β)τ -core is an effective model capturing unique and important the proposed techniques significantly improve the efficiency of index construction and query processing.