Learning Graphs From Linear Measurements: Fundamental Trade-Offs and Applications
Learning Graphs From Linear Measurements: Fundamental Trade-Offs and Applications
复制标题
DOI：
10.1109/tsipn.2020.2975368
复制
发表时间：
2019-09
影响因子：
3.2
通讯作者：
Tongxin Li;Lucien Werner;S. Low
中科院分区：
文献类型：
--
作者：
Tongxin Li;Lucien Werner;S. Low
我们考虑一个特定的图学习任务：重建一个对称矩阵，表示使用线性测量的底层图。我们提出了一个稀疏性特征的随机图（允许包含高程度的节点）的分布，基于此，我们研究基本的权衡测量的数量，图形类的复杂性，和错误的概率。我们首先推导出测量次数的一个必要条件。然后，通过考虑一个三阶段的恢复计划，我们给出了恢复的充分条件。此外，假设测量是高斯IID，我们证明了上界和下界（最坏情况下）的样本复杂性的噪声和无噪声恢复。在具有$n$个节点的树上的均匀分布和埃尔德什-雷尼$（n，p）$类的特殊情况下，基本的权衡与无噪声测量的乘法因子紧密相关。此外，对于实际应用，我们设计并实现了一个多项式时间（在$n$）算法的基础上的三阶段恢复计划。实验结果表明，该算法在星星图上的性能优于基追踪算法。我们应用启发式算法学习电网中的导纳矩阵。几个典型图类和IEEE电力系统测试案例的仿真表明，所提出的算法的参数重构的有效性和鲁棒性。
We consider a specific graph learning task: reconstructing a symmetric matrix that represents an underlying graph using linear measurements. We present a sparsity characterization for distributions of random graphs (that are allowed to contain high-degree nodes), based on which we study fundamental trade-offs between the number of measurements, the complexity of the graph class, and the probability of error. We first derive a necessary condition on the number of measurements. Then, by considering a three-stage recovery scheme, we give a sufficient condition for recovery. Furthermore, assuming the measurements are Gaussian IID, we prove upper and lower bounds on the (worst-case) sample complexity for both noisy and noiseless recovery. In the special cases of the uniform distribution on trees with $n$ nodes and the Erdős-Rényi $(n,p)$ class, the fundamental trade-offs are tight up to multiplicative factors with noiseless measurements. In addition, for practical applications, we design and implement a polynomial-time (in $n$) algorithm based on the three-stage recovery scheme. Experiments show that the heuristic algorithm outperforms basis pursuit on star graphs. We apply the heuristic algorithm to learn admittance matrices in electric grids. Simulations for several canonical graph classes and IEEE power system test cases demonstrate the effectiveness and robustness of the proposed algorithm for parameter reconstruction.