arXiv:2606.27455stat.MLcs.LG2026-06

从节点数据反推有向网络结构,解决复杂扩散过程下的拓扑识别难题。

Directed Graph Topology Inference via Graph Filter Identification

论文配图:Directed Graph Topology Inference via Graph Filter Identification
图 1 · 摘自论文原文
  • 通过输出信号与输入统计信息联合识别图滤波器,构建二次矩阵方程求解框架。
  • 在输入协方差谱多样性假设下可唯一识别滤波器,算法基于流形约束优化实现。
  • 适用于城市交通、投资组合等实际场景,对稀疏有向图恢复效果显著。

我们研究从线性扩散动态产生的节点观测数据中推断有向网络拓扑的问题。观测模型为图卷积滤波器的输出,即未知系数多项式形式的局部扩散图移位算子(编码潜在图结构),其输入为一组具有任意相关性的独立图信号。与以往仅考虑无向图和白噪声激励的研究不同,此处图移位算子与观测协方差矩阵不同时可对角化。为此,我们利用输出信号及输入先验统计信息,识别扩散滤波器。该系统辨识问题涉及求解一组二次矩阵方程,在输入协方差谱多样性假设下具备可辨识性。为算法实现,将其转化为带施蒂费尔流形约束的光滑二次最小化问题。在获得滤波器估计后,进一步通过寻找与滤波器可交换且稀疏、结构合法的移位算子,完成网络拓扑识别,从而保证滤波器为所求图移位算子的多项式。还提出一种联合滤波器与拓扑识别算法,交替执行上述步骤,相互促进以提升样本效率。数值实验验证了该方法在合成有向图和真实数据案例中的有效性,并展示了其在城市出行分析与投资组合优化中的潜力。

原文摘要 · Abstract (English)

We address the problem of inferring a directed network from nodal measurements generated by linear diffusion dynamics on the sought graph. Observations are modeled as the outputs of a graph convolutional filter, i.e., a polynomial (with unknown coefficients) of a local diffusion graph-shift operator encoding the latent graph topology, excited with an ensemble of independent graph signals with arbitrarily-correlated nodal components. Unlike prior efforts that considered undirected graphs and white signal excitations, here the graph-shift operator and the observations' covariance matrix are not simultaneously diagonalizable. In this challenging context, we first rely on measurements of the output signals along with prior statistical information on the inputs to identify the diffusion filter. Such system identification problem involves solving a system of quadratic matrix equations, which we show is identifiable under spectral-diversity assumptions on the input covariances. For algorithmic purposes we recast it as a smooth quadratic minimization subject to Stiefel manifold constraints. Subsequent identification of the network topology given the graph filter estimate boils down to finding a sparse and structurally admissible shift that commutes with the given filter, thus, forcing the latter to be a polynomial in the sought graph-shift operator. A joint graph filter and topology identification algorithm is also proposed, which alternates between the aforementioned steps in a mutually reinforcing fashion to offer improved sample complexity. Numerical tests corroborate the effectiveness of the proposed algorithms in recovering synthetic digraphs and real-data case studies, and illustrate their potential utility on urban mobility analyses as well as portfolio optimization.

图神经网络拓扑推断有向图系统辨识

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