2025-11-23T19:40:17.292793

Learning the Structure of Connection Graphs

Di Nino, D'Acunto, Barbarossa et al.

Connection graphs (CGs) extend traditional graph models by coupling network topology with orthogonal transformations, enabling the representation of global geometric consistency. They play a key role in applications such as synchronization, Riemannian signal processing, and neural sheaf diffusion. In this work, we address the inverse problem of learning CGs directly from observed signals. We propose a principled framework based on maximum pseudo-likelihood under a consistency assumption, which enforces spectral properties linking the connection Laplacian to the underlying combinatorial Laplacian. Based on this formulation, we introduce the Structured Connection Graph Learning (SCGL) algorithm, a block-optimization procedure over Riemannian manifolds that jointly infers network topology, edge weights, and geometric structure. Our experiments show that SCGL consistently outperforms existing baselines in both topological recovery and geometric fidelity, while remaining computationally efficient.

academic

Learning the Structure of Connection Graphs

基本信息

论文ID: 2510.11245
标题: Learning the Structure of Connection Graphs
作者: Leonardo Di Nino, Gabriele D'Acunto, Sergio Barbarossa, Paolo Di Lorenzo (Sapienza University of Rome & CNIT)
分类: cs.LG (Machine Learning), eess.SP (Signal Processing)
发表时间: 2025年10月13日提交至arXiv
论文链接: https://arxiv.org/abs/2510.11245v1

摘要

连接图(Connection Graphs, CGs)通过将网络拓扑与正交变换耦合，扩展了传统图模型，能够表示全局几何一致性。它们在同步、黎曼信号处理和神经束扩散等应用中发挥关键作用。本研究解决了从观测信号直接学习连接图的逆问题。作者提出了一个基于一致性假设下最大伪似然的原理性框架，该框架强制连接拉普拉斯算子与底层组合拉普拉斯算子之间的谱性质联系。基于此formulation，引入了结构化连接图学习(SCGL)算法，这是一个在黎曼流形上的块优化过程，能够联合推断网络拓扑、边权重和几何结构。

研究背景与动机

问题定义

本研究要解决的核心问题是从观测信号中学习连接图结构的逆问题。具体包括：

如何从向量值信号数据中同时推断网络拓扑结构
如何学习边上的正交变换矩阵
如何保证学习到的连接图满足几何一致性

问题重要性

传统的图信号处理(GSP)只能捕获节点间的局部、成对交互，限制了对网络全局一致性的建模能力。连接图通过引入正交变换，能够：

表示比传统图更丰富的同步配置
建模全局几何一致性
支持黎曼信号处理和神经束扩散等先进应用

现有方法局限性

Vector Diffusion Maps (VDM): 采用几何原理近似连接图拉普拉斯算子，但是正向方法，不适合逆问题
SDP方法: 使用半定规划扩展了束拉普拉斯算子学习，但无法正确恢复连接图的非欧几何特性
传统图学习: 只关注拓扑和信号平滑性，无法处理几何结构

研究动机

现有方法无法有效处理连接图学习中的关键挑战：

正交流形的非欧几何约束
拓扑和几何结构的联合优化
一致性条件的强制执行

核心贡献

理论框架: 提出了基于一致性假设的最大伪似然问题formulation，将谱控制从传统图扩展到连接图
算法创新: 开发了SCGL算法，利用黎曼流形上的块下降优化联合恢复拓扑和几何模式
实验验证: 在随机图和几何图的合成实验中证明了SCGL相比现有基线在连接图学习上的显著改进
计算效率: 实现了比锥规划方法更高效的参数化，将空间复杂度从O(V²n²)降低到O(Vn²)

方法详解

任务定义

输入: 观测信号集合 X = {x₁, ..., xₘ}，其中每个信号 xᵢ ∈ ℝⁿᵛ 是由节点局部测量 xᵥ ∈ ℝⁿ 堆叠而成输出: 连接拉普拉斯算子 L，包括：

底层图的组合拉普拉斯算子 L
边权重 w
节点正交基 O = blkdiag({Oᵥ}ᵥ∈V)

理论基础

连接图定义

连接图 G = ⟨G,ℝⁿ,w,O(n)⟩ 由以下组件构成：

底层图 G := (V,E)
每个节点 v ∈ V 上的 n 维欧几里得向量空间 ℝⁿ
每条边 e ∈ E 上的非负权重 wₑ 和正交矩阵 Oₑ ∈ O(n)

一致性条件

定理1 表明连接图一致性等价于以下条件：

正交映射沿图的每个环路复合为恒等映射
连接拉普拉斯算子的特征值是组合拉普拉斯算子特征值的 n 重复
存在节点正交矩阵使得边映射可分解为 Oᵢⱼ = Oᵢᵀ Oⱼ

优化问题formulation

最大伪似然问题

假设信号服从高斯分布 N_nv(0,L†)，原始问题为：

min_{L∈CL} -log gdet(L) + Tr(SL)     (P1)

一致性约束下的重formulation

利用一致性条件 L = Oᵀ(L⊗Iₙ)O，问题转化为：

min_{L∈GL, O∈O} -log gdet{Oᵀ(L⊗Iₙ)O} + Tr{SOᵀ(L⊗Iₙ)O}     (P2)

最终优化问题

通过引入 Kronecker 结构拉普拉斯算子和拉格朗日松弛：

min_{O,w,U,Λ} -n log gdet(Λ) + Tr{SOᵀL_K(w)O} + αΨ(w)
             + β/2 ||OᵀL_K(w)O - U(Λ⊗Iₙ)Uᵀ||²_F     (P3)

SCGL算法

块坐标下降优化

SCGL采用交替块最小化策略，分别优化四个变量块：

边权重更新 (w):
```
w^{t+1} = P^+_{α/β Ψ}{w^t - 1/τ L*_K[f(w^t)]}
```
使用 Minorization-Maximization (MM) 方法
正交基更新 (O): 在乘积流形 SO(n)^v 上使用黎曼梯度下降
特征向量更新 (U): 通过主特征向量计算：
```
U^{t+1} = [Eigenvecs{OᵀL_K(w)O}]_{:,(n+1):}
```
特征值更新 (Λ): 等张回归问题，具有闭式KKT解

计算复杂度

算法复杂度为 O(V³n³)，主要由正交基和特征向量优化步骤中的特征分解决定，相比结构化图学习仅增加了维度 n 的缩放因子。

实验设置

数据集

Erdős–Rényi (ER) 连接图:
- 节点数: |V| = 30
- 边概率: p_ER = 1.1 log V / V
- 向量空间维度: n = 2
- 边权重: Unif(0.2, 3)
球面几何连接图:
- R³中的球面，使用Fibonacci格子离散化
- 50个点，k=4的k-NN图
- 使用Vector Diffusion Maps构建连接拉普拉斯算子