从稀疏数据中学习连通稀疏图，提升估计鲁棒性。
Sparse Graph Learning from Sparse Data via Fiedler Number Maximization
- 通过最大化Fiedler数正则化，增强图的连通性约束。
- 在K≪N条件下，性能优于已有稀疏图学习方法。
- 适合数据稀疏、需保证图连通性的场景。
我们旨在从稀疏数据中学习一个稀疏且连通的图，其中观测数K远小于信号维度N（x ∈ R^N），且底层分布未知。在此严重不适定问题中，我们将Fiedler数（图拉普拉斯矩阵的第二特征值，衡量连通性）作为稀疏图学习目标中的鲁棒正则项。首先，提出一种贪心算法，通过迭代全局选择一条边进行弱化或移除以降低目标函数，利用特征值扰动定理限制边变动对Fiedler数的负面影响。接着，基于Cheeger不等式设计了一种并行变体，通过近似Cheeger割递归将输入图划分为两个子图，分布式地寻找最优边。仿真实验表明，最大化Fiedler数能显著提升稀疏图估计的鲁棒性，优于现有算法。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。