Exploring Cohesive Subgraphs with Vertex Engagement and Tie Strength in Bipartite Graphs

Abstract We propose a novel cohesive subgraph model called τ -strengthened ( α , β ) -core (denoted as ( α , β ) τ -core), which is the first to consider both tie strength and vertex engagement on bipartite graphs. An edge is a strong tie if contained in at least τ butterflies ( 2 × 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 cohesive subgraphs; (2) the proposed techniques significantly improve the efficiency of index construction and query processing.