标题： 有符号图学习：算法与理论 显示英文标题

标题： Signed Graph Learning: Algorithms and Theory

摘要： 现实世界的数据通常通过数据样本之间的关系来表示，形成一个图结构。 在许多应用中，有必要从观察到的数据中学习这种图结构。 当前的图学习研究主要集中在无符号图上，这些图仅包含正边。 然而，许多生物和社会系统更适合用有符号图来描述，这些图考虑了正负交互作用，捕捉了样本之间的相似性和差异性。 在本文中，我们开发了一种从一组平滑的有符号图信号中学习有符号图的方法。 具体来说，我们采用净拉普拉斯矩阵作为图移位算子（GSO），将平滑的有符号图信号定义为由净拉普拉斯矩阵定义的低通有符号图滤波器的输出。 然后通过构建一个非凸优化问题来学习有符号图，该问题以净拉普拉斯矩阵为变量，最小化观察到的信号的总变化量。 所提出的问题使用交替方向乘子法（ADMM）求解，并引入了一种快速算法，将每次ADMM迭代的复杂度从节点数的二次方降低到线性。 此外，提供了该算法的收敛性理论证明，并给出了学习到的净拉普拉斯矩阵的估计误差在样本数量、节点数和图拓扑结构下的误差界。 最后，所提出的方法在模拟数据和基因调控网络推断问题上进行了评估，并与现有的有符号图学习方法进行了比较。 显示英文摘要

摘要： Real-world data is often represented through the relationships between data samples, forming a graph structure. In many applications, it is necessary to learn this graph structure from the observed data. Current graph learning research has primarily focused on unsigned graphs, which consist only of positive edges. However, many biological and social systems are better described by signed graphs that account for both positive and negative interactions, capturing similarity and dissimilarity between samples. In this paper, we develop a method for learning signed graphs from a set of smooth signed graph signals. Specifically, we employ the net Laplacian as a graph shift operator (GSO) to define smooth signed graph signals as the outputs of a low-pass signed graph filter defined by the net Laplacian. The signed graph is then learned by formulating a non-convex optimization problem where the total variation of the observed signals is minimized with respect to the net Laplacian. The proposed problem is solved using alternating direction method of multipliers (ADMM) and a fast algorithm reducing the per-ADMM iteration complexity from quadratic to linear in the number of nodes is introduced. Furthermore, theoretical proofs of convergence for the algorithm and a bound on the estimation error of the learned net Laplacian as a function of sample size, number of nodes, and graph topology are provided. Finally, the proposed method is evaluated on simulated data and gene regulatory network inference problem and compared to existing signed graph learning methods.