VisAdj：从节点-链接图像中学习邻接矩阵

# 从节点-链接图像学习邻接矩阵
来源: https://arxiv.org/html/2608.21825
## VisAdj：从节点-链接图像学习邻接矩阵
DOI:XXXXXXX.XXXXXXX (https://doi.org/XXXXXXX.XXXXXXX)
会议: 请务必输入您权利确认邮件中的正确会议标题；2018年6月3-5日；纽约州伍德斯托克
ISBN:978-1-4503-XXXX-X/2018/06
会议: 第35届ACM国际信息与知识管理大会论文集；2026年11月7-11日；意大利罗马
第35届ACM国际信息与知识管理大会 (CIKM ’26) 论文集，2026年11月7-11日，意大利罗马
DOI:10.1145/3799682.3840917 (https://doi.org/10.1145/3799682.3840917)
ISBN:979-8-4007-2539-5/2026/11
CCS: 计算理论 图算法分析
2026; © cc

###### 摘要
从节点-链接图像中学习邻接矩阵，是从视觉观测中恢复结构化图信息的一个基本问题。现有方法通常依赖于固定的基于KNN的启发式方法来选择候选边，未能捕捉边之间的依赖关系。为克服这些局限，我们提出了VisAdj，一种新的拓扑感知邻接预测框架。VisAdj引入了一种注意力稀疏邻域采样器来自适应地选择高召回率的候选节点对，并使用线图Transformer进行联合边推理，该Transformer将候选边视为token，并显式建模关联边之间的依赖关系。在合成图、道路网络和血管图像上的大量实验表明，VisAdj始终以显著优势优于现有基线方法。

###### 关键词
学习，邻接矩阵，边推理，节点-链接图像

††cc-许可:by
## 1. 引言

节点-链接图像被广泛用于可视化关系结构(39; 24; 19; 46)，例如道路和血管网络（图1），其中底层的图编码了感兴趣的语义信息，而图像主要服务于人类解读。然而，在实践中，原始的图数据通常不可用，只剩下栅格化的图像，如卫星照片和医学图像。因此，邻接结构无法被下游图算法和学习模型访问。这就引出了从节点-链接图像恢复邻接矩阵的问题。

早期的尝试使用手工设计的启发式方法(12)从节点-链接图像中恢复图，这些方法对视觉变化敏感。近期的道路网络提取方法，如SAM-Road(20)和SAM-Road++(48)，采用了基于学习的流程，但仍依赖于固定的基于KNN的策略来选择候选节点对。这导致了一个固有的局限：较小的邻域半径会遗漏远距离连接，而较大的半径则会引入许多虚假的候选。这种设计对于结构相对简单、交叉点有限的道路网络（图1(a)）是有效的，但对于更一般的节点-链接图像则变得不太可靠，因为底层的图结构可能更复杂（图1(b)-1(c)）。更通用的图像到图方法，如RelationFormer(40)和Any2Graph(27)，通过学习关系推理来推断图结构，但仍然仅基于端点特征独立地预测每条边，没有考虑边之间的结构依赖关系。在实践中，边的依赖关系来自节点级和图级的结构约束：节点的度数限制了其关联边的数量，全局图属性（例如图1(a)中的平面性和图1(b)中的树拓扑）施加了额外的拓扑限制。忽略这种边-边交互往往会导致模糊或不一致的邻接预测，使边推理成为图重构的主要瓶颈。

图1：节点-链接图像及其底层图的示例。橙色线表示真实边。现有方法经常遗漏长距离连接（橙色虚线），并在视觉模糊的交叉区域预测错误的捷径边（红色点线）。展示了三个节点-链接图像示例：一个道路网络、一个血管网络和一个通用图图像。每张图像包含对应于底层图结构的可见节点和链接。

**贡献**：我们提出了VisAdj，一种从节点-链接图像重构邻接矩阵的新框架。VisAdj首先将输入图像编码为局部和全局视觉特征，以支持节点检测和图像级结构理解，其中全局特征通过可学习的拓扑token进行增强。为了克服基于KNN的候选选择的刚性，VisAdj引入了一种注意力稀疏邻域采样器来自适应地选择高召回率的候选节点对。此外，为了解决现有方法忽略边依赖关系的局限，VisAdj使用线图Transformer对候选节点对执行联合边推理，该Transformer将边视为token，并显式建模关联边之间的交互，以实现结构一致的邻接预测。实验上，VisAdj在图同构率上比现有最优方法提高了15%以上，在边预测F1分数上提高了8%以上，涵盖了多个基准数据集，同时作为即插即用的图推理模块，也增强了现有的道路网络提取流程。我们的代码、数据集和超参数设置可在 https://github.com/Jiahao-Xie-86/VisAdj 获取。

## 2. 相关工作

**道路网络提取**。大量工作研究了道路网络提取背景下的图像到图重构(36; 2; 41; 35)。Sat2Graph(18)通过使用局部邻域上的卷积特征预测检测到的交叉点之间的连通性来建模道路图。RNGDet++(47)采用迭代式图增长范式，通过在历史地图引导下对感兴趣区域进行采样，逐步添加节点和边。更近期的方法，如SAM-Road(20)和SAM-Road++(48)，利用视觉基础模型生成节点和边的表示，随后通过后处理将其转换为图结构。尽管这些方法在道路数据集上有效，但由于其图推理模块针对道路特定特性（例如平面性和局部连通性）进行定制，并依赖于固定的基于KNN的方法进行候选边选择，因此难以泛化到一般的节点-链接图像。

**通用图像到图方法**。除了道路网络外，若干方法旨在从图像中恢复更通用的图结构(5)。例如，RelationFormer(40)引入了一个基于Transformer的框架，使用集合预测和二部图匹配联合预测节点和边，无需显式后处理即可实现端到端的图推断。Any2Graph(27)通过提出一种基于最优传输的损失函数来改进这一范式，以在置换歧义下更好地对齐预测图和真实图。这些方法通过联合学习节点和边预测，向统一的图像到图建模迈进。然而，它们独立地预测每条边，并且缺乏显式机制来建模边之间的结构依赖关系。相比之下，我们的框架通过学习边交互并执行联合边推理来克服这些局限。

## 3. 预备知识

我们研究从节点-链接图像恢复图邻接矩阵的问题。令$\mathcal{I}$表示节点-链接图像的空间，$\mathcal{G}$表示无向无权图的空间。每个图像$\mathbf{I}\in\mathcal{I}$提供了底层图$G=(V,\mathbf{A})\in\mathcal{G}$的可视化，其中$V$表示节点集，$\mathbf{A}\in\{0,1\}^{|V|\times|V|}$是相应的邻接矩阵。给定一个数据集$\mathcal{D}=\{\left(\mathbf{I}_i,G_i=(V_i,\mathbf{A}_i)\right)\}_{i=1}^{n}$，目标是学习一个映射$h:\mathcal{I}\rightarrow\left(\widehat{V},\widehat{\mathbf{A}}\right)$，该映射能恢复底层的邻接结构。由于节点锚定在图像空间中，节点身份由其空间位置定义。在训练期间，预测节点通过空间匹配与真实节点对齐，这在$\widehat{V}$和$V$之间诱导了一个一致的排序。在此对应关系下，通过最小化经验损失来学习$h$：

$$\displaystyle\mathcal{L}(h)=\frac{1}{n}\sum_{i=1}^{n}\Big[\ell_{\text{node}}\!\big(\widehat{V}_{h}(\mathbf{I}_{i}),V_{i}\big)+\ell_{\text{edge}}\!\big(\widehat{\mathbf{A}}_{h}(\mathbf{I}_{i}),\mathbf{A}_{i}\big)\Big],$$
其中$\ell_{\text{node}}$衡量预测节点集与真实节点集之间的差异，$\ell_{\text{edge}}$衡量在诱导的节点对应下预测邻接矩阵与真实邻接矩阵之间的差异（例如交叉熵损失）。

图2：VisAdj架构概览。流程包含五个编号模块：图像编码、节点检测、全局拓扑编码、ASNS候选边生成以及使用线图Transformer的拓扑感知边推理。
给定输入节点-链接图像，VisAdj首先（#1）使用视觉基础编码器提取局部和全局视觉特征，并（#2）通过峰值提取、非极大值抑制和软-argmax细化从节点似然图中检测图节点。然后（#3）它使用可学习的拓扑token增强全局特征，以捕获图像级结构上下文。在检测到的节点条件下，VisAdj（#4）应用ASNS生成稀疏的高召回率候选边集，并（#5）将这些候选边表示为边token，用于与线图Transformer进行拓扑感知推理。得到的边logits经过对称化和阈值处理，以获得预测的邻接矩阵。

## 4. 方法

给定一个节点-链接图像$\mathbf{I}$，VisAdj旨在通过预测节点集和邻接矩阵来恢复底层图，即$\big(\widehat{V}(\mathbf{I}),\,\widehat{\mathbf{A}}(\mathbf{I})\big)$。为此，VisAdj遵循三阶段流程：1) **图像编码**：我们使用视觉基础模型编码$\mathbf{I}$以获得多尺度特征。2) **节点检测**：通过节点似然性预测检测节点集$\widehat{V}(\mathbf{I})$。3) **边推理**：基于$\widehat{V}(\mathbf{I})$，VisAdj使用可学习的拓扑token聚合图像级上下文，使用注意力稀疏邻域采样器（ASNS）自适应地选择候选节点对，并通过采用线图Transformer对边之间的依赖关系进行建模，联合推断连通性，从而预测$\widehat{\mathbf{A}}(\mathbf{I})$。我们框架的整体架构如图2所示，其中编号块对应于VisAdj的主要模块。下文首先详细说明架构，然后描述训练策略。

### 4.1. 架构

#### 4.1.1. 图像编码
给定输入节点-链接图像$\mathbf{I}\in\mathbb{R}^{H\times W\times 3}$，分辨率为$H\times W$，我们使用预训练的视觉基础模型(1; 32)（例如SAM(26)、SAM2(38)和SAM3(8)）提取视觉表示，如图2中的模块#1所示。编码器$\mathcal{E}_{\boldsymbol{\theta}_{E}}$首先将输入图像映射到主干特征表示，然后将其投影到两个互补的特征流(9)中：

$$\begin{aligned}
\displaystyle\mathbf{F}_{\text{local}} &= \mathcal{F}_{L,\boldsymbol{\theta}_{L}}\big(\mathcal{E}_{\boldsymbol{\theta}_{E}}(\mathbf{I})\big) \in \mathbb{R}^{H_{L}\times W_{L}\times D_{L}}, \\
\displaystyle\mathbf{F}_{\text{global}} &= \mathcal{F}_{G,\boldsymbol{\theta}_{G}}\big(\mathcal{E}_{\boldsymbol{\theta}_{E}}(\mathbf{I})\big) \in \mathbb{R}^{H_{G}\times W_{G}\times D_{G}},
\end{aligned}$$
其中$\boldsymbol{\theta}_{E}$表示视觉主干的参数。$(H_{L},W_{L})$和$(H_{G},W_{G})=(H_{L}/\lambda_{G},W_{L}/\lambda_{G})$分别表示局部和全局特征流的空间分辨率，$\lambda_{G}\in\mathbb{Z}^{+}$是下采样率。$D_{L},D_{G}\in\mathbb{Z}^{+}$是它们相应的特征维度。$\mathcal{F}_{L,\boldsymbol{\theta}_{L}}$和$\mathcal{F}_{G,\boldsymbol{\theta}_{G}}$都是由$\boldsymbol{\theta}_{L}$和$\boldsymbol{\theta}_{G}$参数化的可学习特征表示模块（例如CNN(17)）。局部特征流保留了更高的空间分辨率，并保留了对精确定位节点很重要的细粒度几何线索。相反，全局流在更粗的空间尺度上聚合特征，扩大了感受野，并捕获了对后续边推理至关重要的远距离上下文。

#### 4.1.2. 节点检测
我们通过从$\mathbf{F}_{\text{local}}$估计密集的节点似然图来检测图节点，然后进行峰值提取以定位节点，并进行特征采样以获得节点描述符。此节点检测过程如图2中的模块#2所示。

1) 节点似然性预测