Sparse Graph Learning from Sparse Data via Fiedler Number Maximization

• URL: http://arxiv.org/abs/2604.26132v1
• Date: Tue, 28 Apr 2026 21:40:39 GMT
• Title: Sparse Graph Learning from Sparse Data via Fiedler Number Maximization
• Abstract summary: We aim to learn a sparse and connected graph from sparse data, where the number of observations K can be substantially smaller than the signal dimension N for signals x in RN, and the underlying distribution is unknown.<n>We incorporate Fiedler number (the second eigenvalue of the graph Laplacian matrix that quantifies connectedness) as a robust regularization term in the sparse graph learning objective.<n> Simulation experiments show that Fiedler number robustifies sparse graph estimates, outperforming previous sparse graph learning algorithms.
• Score: 16.83442282933831
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We aim to learn a sparse and connected graph from sparse data, where the number of observations K can be substantially smaller than the signal dimension N for signals x in R^N, and the underlying distribution is unknown. In this severely ill-posed setting, we incorporate Fiedler number (the second eigenvalue of the graph Laplacian matrix that quantifies connectedness) as a robust regularization term in the sparse graph learning objective. We first develop a greedy algorithm that iteratively selects one edge globally for weakening/removal to reduce the objective, leveraging eigenvalue perturbation theorems that bound the adverse effect of an edge change to the Fiedler number. Next, we design a parallel variant, based on the Cheeger's inequality, that recursively partitions an input graph into two sub-graphs using an approximate Cheeger cut to distributedly find an optimal edge. Simulation experiments show that Fiedler number maximization robustifies sparse graph estimates, outperforming previous sparse graph learning algorithms.

Related papers

• Scalable Graph Coreset Selection via Greedy Sampling [48.91894218306487]
  We propose a simple and effective column-selective graph sampling algorithm based on a minimum inner product greedy selection rule.<n>We analyze the algorithm under the block model and show that, when the degree distribution is balanced across nodes, the algorithm achieves proportional sampling to cluster size.
  arXiv  Detail & Related papers  (2026-07-30T02:45:31Z)
• Rethinking Efficient Graph Coarsening via a Non-Selfishness Principle [56.92868481531399]
  We propose a non-selfishness principle that prioritizes the collective interference of neighborhood in coarsening.<n>We derive a faster variant NOPE*, which reduces O(dot d) interference evaluation to O(d) based on the local isotropy assumption.<n>Learning on coarsened graphs yields comparable performance to original graphs, and can even show superior performance over LLM-based graph reasoning.
  arXiv  Detail & Related papers  (2026-05-13T05:24:35Z)
• Graph Semi-Supervised Learning for Point Classification on Data Manifolds [16.311715311352597]
  We propose a graph semi-supervised learning framework for classification tasks on data manifold.<n>Motivated by the manifold hypothesis, we model data as points sampled from a low-dimensional $mathcalM subset mathbbRF$.<n>We show that, under uniform sampling from $mathcalM$, the generalization gap of the semi-supervised task diminishes with increasing graph size.
  arXiv  Detail & Related papers  (2025-06-13T19:52:54Z)
• Efficient Graph Matching for Correlated Stochastic Block Models [7.320365821066744]
  We study learning problems on correlated block models with two balanced communities.<n>Our main result gives the first efficient algorithm for graph matching in this setting.<n>We extend this to an efficient algorithm for exact graph matching whenever this is information-theoretically possible.
  arXiv  Detail & Related papers  (2024-12-03T18:36:45Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  This paper proposes a novel Deep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE) for attributed graph data. The proposed method surpasses state-of-the-art baseline algorithms by a significant margin on different downstream tasks across popular datasets.
  arXiv  Detail & Related papers  (2024-01-12T17:57:07Z)
• Efficient Graph Laplacian Estimation by Proximal Newton [12.05527862797306]
  A graph learning problem can be formulated as a maximum likelihood estimation (MLE) of the precision matrix. We develop a second-order approach to obtain an efficient solver utilizing several algorithmic features.
  arXiv  Detail & Related papers  (2023-02-13T15:13:22Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
  arXiv  Detail & Related papers  (2023-02-08T08:17:43Z)
• Graph Summarization via Node Grouping: A Spectral Algorithm [4.967873417059781]
  Graph summarization via node grouping is a popular method to build concise graph representations. In this paper, we reformulate the loss minimization problem for summarization into an equivalent integer problem. We show that SpecSumm efficiently produces high-quality summaries compared to state-of-the-art summarization algorithms.
  arXiv  Detail & Related papers  (2022-11-08T11:23:16Z)
• Graph Condensation via Receptive Field Distribution Matching [61.71711656856704]
  This paper focuses on creating a small graph to represent the original graph, so that GNNs trained on the size-reduced graph can make accurate predictions. We view the original graph as a distribution of receptive fields and aim to synthesize a small graph whose receptive fields share a similar distribution.
  arXiv  Detail & Related papers  (2022-06-28T02:10:05Z)
• Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
  multilayer graph clustering aims at dividing the graph nodes into categories or communities. We propose a clustering-friendly embedding of the layers of a given multilayer graph. Experiments show that our method leads to a significant improvement.
  arXiv  Detail & Related papers  (2021-03-30T17:36:40Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph. Experiments show that our method leads to a clustered clusters w.r.t. We learn a clustering algorithm for solving clustering problems.
  arXiv  Detail & Related papers  (2020-10-29T09:58:02Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.