Bipartite Graph Approximation and Inference: An Eigenstructure-Based Approach

Abstract

Bipartite graphs are a special class of graphs where nodes are divided into two distinct sets, with edges only connecting nodes from different sets. These graphs play a key role in applications such as critical sampling in filter banks and graph-based co-clustering. However, general graphs often lack an inherent bipartite structure. To address this limitation, we propose a novel algorithm for bipartite graph approximation (BGA) from general graphs. We formally show that the eigenvectors of a bipartite graph’s adjacency matrix exhibit symmetric properties intrinsically linked to node partitioning. Exploiting this insight, we then formulate BGA as an optimization problem based on the submatrix of the adjacency matrix that captures all effective edges. An alternating optimization approach is developed to tackle the nonconvex BGA problem efficiently. The proposed algorithm can be combined with state-of-the-art graph learning methods to infer bipartite structures from graph signals. Experimental results demonstrate that the proposed method significantly improves bipartite graph reconstruction accuracy, is robust to noise, and provides an efficient solution for learning bipartite graph topologies from data.