Bipartite Graph Approximation and Inference: An Eigenstructure-Based Approach

Graph-Based Correlation Matrix Generation: A Convex Optimization Approach

This work addresses the generation of theoretical correlation matrices with prescribed sparsity patterns associated to graph structures. We propose a novel convex optimization framework in which an initial matrix is projected onto an elliptope under a positive semidefiniteness constraint. Several numerical schemes are implemented and compared. The problem falls within the broader class of matrix completion, where off-diagonal entries corresponding to absent edges are fixed to zero and diagonal entries are fixed to one. Beyond this structural constraint, the approach offers greater flexibility than existing methods by allowing control over the mean of the off-diagonal entry distribution, enabling the generation of correlation matrices that better reflect realistic data. This procedure is not designed to yield a uniform distribution over the feasible set; rather, it provides a principled and tunable way to construct correlation matrices suitable for benchmarking statistical methods for graphical model inference. Theoretical guarantees on the existence of solutions are established, both in the general setting and under the additional mean constraint. Simulation studies illustrate the properties of the generated matrices with respect to graph structure. The methodology is applied to two real-world datasets from neuroscience and finance, and a comparison with GAN-based correlation matrix generation is provided.

Feature-Graph-Guided Adaptive Sparse NMF with Anchor Dual Graphs Under the Logarithmic Framework for Data Clustering

Graph-based nonnegative matrix factorization (GNMF) has been widely used for dimensionality reduction and data clustering because it can preserve the intrinsic geometric structure of data. However, many existing GNMF-based methods still rely on full sample similarity graphs, resulting in high computational costs; moreover, their sparsity constraints usually treat all features uniformly, making it difficult to distinguish structurally important features from redundant or noisy ones. To address these issues, this paper proposes a feature-graph-guided adaptive Log-L2,1 sparse NMF with anchor dual graphs under a logarithmic framework. Specifically, anchor-based representations are simultaneously constructed in the sample and feature spaces to approximate the corresponding full-scale graphs. The sample anchor graph preserves the local manifold structure among samples, whereas the feature anchor graph plays a dual role: it preserves structural relationships among features and provides degree information for generating the adaptive weights gi of the row-wise Log-L2,1 penalty imposed on the basis matrix U. Consequently, structurally well-connected features receive weaker sparsity penalties, while weakly connected and potentially redundant features are more strongly suppressed. In addition, a logarithmic reconstruction framework is introduced to reduce the influence of large residuals caused by noise and outliers. These mechanisms jointly integrate sample structure preservation, feature structure preservation, and feature-aware sparse learning within a unified graph-NMF model. To optimize the model, multiplicative update rules are derived, while the nonnegativity of the factor matrices is inherently preserved throughout the iterations. Extensive evaluations on several benchmark datasets demonstrate the effectiveness and robustness of the proposed method.

Scalable Graph Coreset Selection via Greedy Sampling

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 Sheaf Learning of Consistent Connection Graphs

Connection graphs (CGs) extend classical graphs by associating vector-valued signals to nodes and orthogonal transport maps across edges, making them a natural model for synchronization and manifold-based signal processing. Despite their growing use, learning CGs directly from observations remains challenging because the network topology and the underlying geometric structure are coupled through non-Euclidean orthogonality constraints. In this work, we address this inverse problem by learning a consistent connection graph from noisy vector-valued signals. Exploiting the spectral characterization of consistent CGs, we formulate a structured learning problem that jointly estimates a denoised signal, the graph topology, and node-wise local reference frames. The proposed formulation couples the spectrum of the learned connection Laplacian to that of an underlying combinatorial Laplacian, enabling explicit spectral and topological priors while guaranteeing a nontrivial global-section space. We develop 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. Numerical experiments show that SCGL improves topology and geometry recovery over competing approaches, while also yielding effective denoising and signal-compression bases.

Geometric Hyperbolic Embedding of Metric Graphs Through Graph Decomposition

Inductive Correlation Clustering with Graph Neural Networks

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.