SF-SGL: Solver-Free Spectral Graph Learning From Linear Measurements
SF-SGL: Solver-Free Spectral Graph Learning From Linear Measurements
复制标题
DOI：
10.1109/tcad.2022.3198513
复制
发表时间：
2023-02
影响因子：
2.9
通讯作者：
Ying Zhang;Zhiqiang Zhao;Zhuo Feng
中科院分区：
文献类型：
--
作者：
Ying Zhang;Zhiqiang Zhao;Zhuo Feng
这项工作引入了一种高度可扩展的谱图致密化(SGL)框架，用于学习具有线性测量的电阻网络，例如节点电压和电流。我们证明了所提出的图学习方法等价于求解具有类拉普拉斯精度矩阵的经典图Lasso问题。我们证明了在给定$O(\logN)$对的电压和电流测量的情况下，可以恢复稀疏的$N$节点电阻网络，该网络可以很好地保持原始图形上的有效电阻距离。此外，学习的图还保留了原始图的结构(谱)属性，这可能会被用于许多电路设计和优化任务。为了获得更可扩展的性能，我们还引入了一种无需求解器的方法(SF-SGL)，该方法利用了图的多级谱近似，并允许将整个图谱(待学习的)可扩展且灵活地分解为多个不同的特征值簇(频带)。这种无需解算器的方法使我们能够更有效地识别最关键的光谱边缘，以减少不同范围的光谱嵌入失真。学习图的一个独特性质是，在构造的图上的谱嵌入或有效电阻距离将编码原始输入数据点(节点电压测量)之间的相似性。通过对各种真实测试用例的大量实验，我们证明了该方法在不牺牲解质量的情况下，对于稀疏电阻网络的学习具有高度的可扩展性。我们还引入了用于无向量电源/热完整性验证的数据驱动EDA算法，允许通过利用几个电压/温度测量来估计整个芯片上的最坏情况下的电压/温度(梯度)分布。
This work introduces a highly scalable spectral graph densification (SGL) framework for learning resistor networks with linear measurements, such as node voltages and currents. We show that the proposed graph learning approach is equivalent to solving the classical graphical Lasso problems with Laplacian-like precision matrices. We prove that given $O(\log N)$ pairs of voltage and current measurements, it is possible to recover sparse $N$ -node resistor networks that can well preserve the effective resistance distances on the original graph. In addition, the learned graphs also preserve the structural (spectral) properties of the original graph, which can potentially be leveraged in many circuit design and optimization tasks. To achieve more scalable performance, we also introduce a solver-free method (SF-SGL) that exploits multilevel spectral approximation of the graphs and allows for a scalable and flexible decomposition of the entire graph spectrum (to be learned) into multiple different eigenvalue clusters (frequency bands). Such a solver-free approach allows us to more efficiently identify the most spectrally critical edges for reducing various ranges of spectral embedding distortions. A unique property of the learned graphs is that the spectral embedding or effective-resistance distances on the constructed graph will encode the similarities between the original input data points (node voltage measurements). Through extensive experiments for a variety of real-world test cases, we show that the proposed approach is highly scalable for learning sparse resistor networks without sacrificing the solution quality. We also introduce a data-driven EDA algorithm for vectorless power/thermal integrity verifications to allow estimating worst case voltage/temperature (gradient) distributions across the entire chip by leveraging a few voltage/temperature measurements.