2026· IEEE Transactions on Signal Processing· Vol 74, pp. 2839-2854· 0 citations· 73 references
Computer Science
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.
A novel convex optimization framework in which an initial matrix is projected onto an elliptope under a positive semidefiniteness constraint, providing a principled and tunable way to construct correlation matrices suitable for benchmarking statistical methods for graphical model inference.
Ali Fakhar, Kévin Polisano, Irène Gannaz et al.· 0 citations
This paper proposes a feature-graph-guided adaptive Log-L2,1 sparse NMF with anchor dual graphs under a logarithmic framework that jointly integrate sample structure preservation, feature structure preservation, and feature-aware sparse learning within a unified graph-NMF model.
Quanrun Li, Tao Ma, Fangchen Xu et al.· Mathematics· 0 citations
This work proposes a simple and effective column-selective graph sampling algorithm based on a minimum inner product greedy selection rule, well-suited for large-scale graphs where the full Laplacian cannot be stored in memory.
Structured Connection Graph Learning (SCGL), a block-coordinate algorithm that combines closed-form updates, manifold projections, and spectral constraints, and converges to stationary points of the resulting nonconvex problem, is developed.
Leonardo Di Nino, Gabriele D’Acunto, Sergio Barbarossa et al.· 0 citations
The findings illustrate that geometric insights grounded in hyperbolic geometry can offer powerful tools for understanding, embedding, and visualizing complex graph structures.
†. SalouaNaama, Kave Salamatian, M. Crovella· 0 citations
Correlation Clustering (CC) is a natural formulation of clustering in combinatorial optimization, which uses a graph representation of the input and does not require a pre-specified number of clusters. Given $n$ objects and a pairwise similarity function, the goal is to cluster the objects so that similar objects are put in the same cluster and dissimilar objects are put in different clusters. Despite its versatility, existing CC algorithms suffer from significant scalability issues and are inherently transductive: i.e., the algorithm must be executed from scratch for any new problem instance. In this work, we bridge this gap by leveraging Graph Neural Networks (GNNs) to solve Inductive Correlation Clustering, a novel generalization of the CC problem designed to handle unseen graph instances. By learning to exploit common structural patterns and node features during training, our framework generalizes to new graphs drawn from the same distribution with minimal computational overhead with respect to standard algorithms. We demonstrate the effectiveness and scalability of our approach through extensive experiments. Our framework not only excels in the inductive setting, e.g., lowering the inference time up to $5$ order of magnitude, while maintaining an approximation ratio within $~10\%$ of the best baseline solution, but also achieves competitive results on standard (transductive) CC benchmarks. Finally, we showcase a practical application of our framework as a learnable pooling mechanism for graph classification. Our results indicate that our method serves as an efficient pooling layer, enhancing the ability of GNNs to capture hierarchical structural information in networks.
Francesco Paolo Nerini, Francesco Bonchi, Arijit Khan et al.· 0 citations