Diss-l-ECT: Dissecting Graph Data with Local Euler Characteristic Transforms¶

会议: ICML2025
arXiv: 2410.02622
领域: 图拓扑 / 图表示学习
关键词: Euler Characteristic Transform, 局部拓扑不变量, 节点分类, 异质图, 可解释性

一句话总结¶

提出 Local Euler Characteristic Transform (ℓ-ECT)，将经典 ECT 拓扑不变量扩展到图的局部邻域，为每个节点生成无损的拓扑-几何指纹，在节点分类任务（尤其是高异质性图）上超越标准 GNN，同时提供理论可逆性保证与可解释性。

研究背景与动机¶

核心问题：传统 GNN 依赖消息传递（message passing）聚合邻居特征，在信息扩散过程中会丢失关键的局部结构细节，尤其在高异质性（heterophily）图上表现不佳。

已有方案的不足：

GCN/GAT/GIN 等经典 GNN 的表达能力受 1-WL 测试上界限制，无法计数 ≥3 节点的诱导子图
异质性专用架构（如 H2GCN）在特定场景有效，但缺乏通用性
持久同调（Persistent Homology）虽具表达力，但计算代价高昂

本文动机：Euler Characteristic Transform (ECT) 是一种高效可计算的几何-拓扑不变量，已被证明对嵌入 \(\mathbb{R}^n\) 的数据具有可逆性（即可从 ECT 重建原始数据）。作者将其推广为局部版本，使其能刻画图中每个节点邻域的完整拓扑-几何信息，从而绕过消息传递的固有局限。

方法详解¶

1. Euler 特征与 ECT 基础¶

对单纯复形 \(K\)，Euler 特征定义为各维度单纯形数目的交替和：

\[\chi(K) = \sum_{k=0}^{d} (-1)^k \sigma_k(K)\]

其中 \(\sigma_k(K)\) 为 \(k\) 维单纯形个数。ECT 将此推广为方向扫描函数：

\[\text{ECT}(X)(v, t) := \chi(\{x \in X \mid x \cdot v \leq t\})\]

即沿方向 \(v \in S^{n-1}\) 以阈值 \(t\) 截取子水平集，记录其 Euler 特征。ECT 对嵌入 \(\mathbb{R}^n\) 的可构造集合具有可逆性——原始数据可从 ECT 完全重构。

2. Local ECT (ℓ-ECT) 核心定义¶

给定几何单纯复形 \(X \subset \mathbb{R}^n\) 中的顶点 \(x\)，定义其 \(k\)-局部 ECT：

\[\ell\text{-ECT}_k(x; X) := \text{ECT}(N_k(x; X))\]

其中 \(N_k(x; X)\) 为 \(x\) 的 \(k\)-hop 邻域诱导的完整子复形。实际计算中，通过在 \(S^{n-1}\) 上均匀采样 \(m\) 个方向 \(v_1, \dots, v_m\) 和 \(l\) 个滤波阈值 \(t_1, \dots, t_l\)，将 ℓ-ECT 近似为一个 \(m \cdot l\) 维向量。论文默认 \(m = l = 64\)，即每个节点获得 4096 维的拓扑指纹。

3. 理论保证¶

定理 1（包含消息传递信息）：对特征图 \(\mathcal{G}\)，1-hop 局部 ECT 集合 \(\{\ell\text{-ECT}_1(x; \mathcal{G})\}_x\) 包含执行一步消息传递所需的全部（非可学习）信息——可从中重建每个节点 1-hop 邻居的特征向量。

定理 2（图同构判别）：两个特征图 \(\mathcal{G}_1, \mathcal{G}_2\) 同构当且仅当 \(\text{ECT}(\mathcal{G}_1) = \text{ECT}(\mathcal{G}_2)\)。

推论 1（子图计数）：ECT 方法可以执行子图计数，而消息传递 GNN 对 ≥3 节点的连通子结构无法做到这一点。

4. 旋转不变度量¶

ECT 对平移和缩放不变，但对旋转敏感。为此构造旋转不变度量：

\[d_{\text{ECT}}(X, Y) := \inf_{\rho \in \text{SO}(n)} \|\text{ECT}(X) - \text{ECT}(\rho Y)\|_\infty\]

定理 3 证明 \(d_{\text{ECT}}\) 在有限单纯复形的旋转等价类上构成度量。该度量可用于图数据的空间对齐。

5. 整体流程¶

对图中每个节点 \(x\)，提取 \(k\)-hop 邻域子图 \(N_k(x; \mathcal{G})\)
计算该子图的近似 ECT，得到 \(m \cdot l\) 维向量
将 ℓ-ECT 向量与原始节点特征拼接，作为下游分类器输入
使用 XGBoost 进行节点分类（也可替换为任意分类器）

实验关键数据¶

在 10 个节点分类 benchmark 上与 GCN、GAT、GIN、GraphSAGE、H2GCN 对比，5 次训练取均值。

WebKB 异质图（高异质性，核心结果）¶

模型	Cornell	Wisconsin	Texas
GCN	45.0 ± 2.2	44.2 ± 2.6	47.3 ± 1.5
GAT	44.7 ± 2.9	48.2 ± 2.0	51.7 ± 3.2
GraphSAGE	76.0 ± 3.5	72.9 ± 1.9	71.8 ± 2.4
H2GCN	66.2 ± 3.5	70.2 ± 2.3	72.3 ± 3.0
ℓ-ECT₁+ℓ-ECT₂	67.1 ± 4.1	78.5 ± 2.6	74.8 ± 3.1

异质图 benchmark¶

模型	Amazon Ratings	Roman Empire
GAT	44.6 ± 0.9	76.4 ± 1.2
H2GCN	40.1 ± 0.7	64.2 ± 0.9
ℓ-ECT₁+ℓ-ECT₂	49.8 ± 0.3	81.1 ± 0.4

Planetoid 同质图¶

模型	Cora	CiteSeer	PubMed
GAT	88.3 ± 1.1	75.3 ± 1.5	85.7 ± 4.2
GCN	88.1 ± 1.2	74.6 ± 1.5	85.3 ± 4.7
ℓ-ECT₁+ℓ-ECT₂	87.8 ± 0.6	72.5 ± 0.7	90.3 ± 0.5

关键发现：ℓ-ECT₁+ℓ-ECT₂ 在 critical difference diagram 中平均排名第 2，即使最弱的 ℓ-ECT₂ 也超过了所有非 ℓ-ECT 方法（包括 GAT）。在同质图上与 GNN 接近，在异质图上大幅领先。

亮点与洞察¶

理论优雅：将代数拓扑中的 ECT 可逆性定理推广到图的局部邻域，证明 ℓ-ECT 严格包含一步消息传递的信息量，且能执行 GNN 无法完成的子图计数
架构无关：ℓ-ECT 生成固定维度向量表示，可接入任意下游模型（XGBoost、MLP、SVM 等），无需 GNN 专用训练技巧
异质图友好：不依赖邻居特征聚合，天然适合节点标签与邻居标签不一致的异质图场景
可解释性：基于 XGBoost 的特征重要性可追溯到 ECT 的具体方向和阈值，提供拓扑层面的决策解释
旋转不变度量：提出可高效近似计算的 \(d_{\text{ECT}}\) 度量，为图数据空间对齐提供了几何工具

局限与展望¶

计算复杂度：ℓ-ECT 需为每个节点提取 \(k\)-hop 子图并计算 ECT，当 \(k\) 较大或图稠密时开销显著增长，论文承认在大规模图上存在可扩展性挑战
同质图未占优：在 Cora/CiteSeer 等同质图上略逊于 GCN/GAT，消息传递的全局信息汇聚在此类任务中仍有优势
特定异质图场景受限：在 Chameleon/Squirrel 上不如 H2GCN，说明 ℓ-ECT 并非所有异质图的万能方案
下游模型依赖：论文主要使用 XGBoost，缺少与端到端可微架构的深度融合（如将 ℓ-ECT 层嵌入 GNN 中）
高维特征图：当节点特征维度很高时（如 Actor 数据集），ℓ-ECT 的 4096 维拓扑向量相对于原始特征的增量信息可能有限

评分¶

新颖性: ⭐⭐⭐⭐⭐ — 首次将 ECT 推广为局部版本用于图学习，理论框架优雅
实验充分度: ⭐⭐⭐⭐ — 覆盖 10 个数据集、多种对比方法，但缺少大规模图实验
写作质量: ⭐⭐⭐⭐ — 数学严谨，理论与实验组织清晰
价值: ⭐⭐⭐⭐ — 为拓扑方法在图学习中的应用开辟新方向，但可扩展性待验证