arXiv:2507.09717stat.MLcs.LG2025-07被引 1

从信号中学习带正负边的图结构,适用于生物和社会网络分析。

Signed Graph Learning: Algorithms and Theory

  • 用净拉普拉斯算子定义平滑信号,通过最小化总变差来学习图结构。
  • 算法在1000节点上每轮迭代仅需线性时间,比传统方法快得多。
  • 理论证明了收敛性和误差边界,适合基因调控网络等真实场景。

现实世界数据常以样本间关系构成图结构表示。许多应用需从观测数据中学习该图结构。现有图学习研究主要聚焦无符号图(仅含正边),但生物与社交系统更宜用包含正负互动的有符号图,以刻画样本间的相似与相异。本文提出一种从一组平滑有符号图信号中学习有符号图的方法。具体地,采用净拉普拉斯算子作为图移位算子(GSO),将平滑信号定义为由净拉普拉斯决定的低通有符号图滤波器输出。通过构建非凸优化问题,最小化观测信号的总变差以估计净拉普拉斯。使用交替方向乘子法(ADMM)求解,并引入快速算法将每轮迭代复杂度从二次降低至线性。此外,提供了算法收敛性理论证明及净拉普拉斯估计误差随样本数、节点数和图拓扑变化的界。最后,在模拟数据与基因调控网络推断任务中评估方法,优于现有有符号图学习方法。

原文摘要 · Abstract (English)

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.

图学习有符号图基因网络

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。