Neural Spacetimes for DAG Representation Learning

📄 arXiv: 2408.13885v2 📥 PDF

作者: Haitz Sáez de Ocáriz Borde, Anastasis Kratsios, Marc T. Law, Xiaowen Dong, Michael Bronstein

分类: cs.LG, cs.DM, cs.NE, math.MG, stat.ML

发布日期: 2024-08-25 (更新: 2025-03-09)

备注: 12 pages: main body and 19 pages: appendix

💡 一句话要点

提出神经时空模型以优化有向无环图表示学习

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 神经网络 图表示学习 有向无环图 深度学习 几何模型 因果关系 数据驱动

📋 核心要点

  1. 现有方法主要集中在无向图表示或因果嵌入，缺乏对加权有向无环图的有效表示。
  2. 提出神经时空模型（NST），通过可训练的几何结构同时编码图边权重和因果关系。
  3. 实验表明，NST在合成和真实网络嵌入中实现了更低的嵌入失真，相较于固定几何方法有显著提升。

📝 摘要（中文）

本文提出了一类可训练的深度学习几何模型，称为神经时空（NST），能够将加权有向无环图（DAG）中的节点普遍表示为时空流形中的事件。与现有文献主要关注无向图表示学习或因果嵌入不同，NST能够在空间维度中编码图边权重，并在时间维度中编码因果关系。NST由三个神经网络组成，分别用于节点嵌入、空间几何和时间几何的优化。我们的理论保证是一个通用嵌入定理，表明任何k点DAG可以嵌入到NST中，且失真度为$1+ ext{O}( ext{log}(k))$，同时精确保留其因果结构。实验结果表明，NST在合成加权DAG和实际网络嵌入中均优于使用固定时空几何的对比方法。

🔬 方法详解

问题定义：本文旨在解决加权有向无环图（DAG）的表示学习问题，现有方法往往无法同时有效编码图的边权重和因果关系，导致表示能力不足。

核心思路：论文提出的神经时空（NST）模型通过将DAG节点表示为时空流形中的事件，利用可训练的几何结构来同时优化空间和时间维度的表示，从而克服现有方法的局限性。

技术框架：NST由三个主要模块组成：嵌入网络用于学习节点在时空流形中的位置，神经（准）度量网络优化空间几何，神经偏序网络优化时间几何。这些网络通过端到端的方式共同训练。

关键创新：NST的核心创新在于其使用的产品流形结构，结合了准度量和偏序，能够灵活地适应数据驱动的几何形状，而不是依赖于固定的时空流形，如闵可夫斯基空间或德西特空间。

关键设计：NST的参数数量在k的子立方范围内，并且与DAG的宽度呈线性关系。对于具有平面哈斯图的DAG，空间和时间维度的复杂度进一步优化为$ ext{O}( ext{log}(k)) + 2$。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果显示，NST在合成加权DAG和实际网络嵌入中均实现了显著的性能提升，相较于使用固定时空几何的对比方法，NST的嵌入失真度更低，验证了其有效性和优越性。

🎯 应用场景

该研究的潜在应用领域包括社交网络分析、交通流量建模以及生物信息学等领域，能够为复杂网络的表示学习提供更高效的工具。未来，NST模型有望推动图神经网络的发展，提升其在动态和加权网络中的应用效果。

📄 摘要（原文）

We propose a class of trainable deep learning-based geometries called Neural Spacetimes (NSTs), which can universally represent nodes in weighted directed acyclic graphs (DAGs) as events in a spacetime manifold. While most works in the literature focus on undirected graph representation learning or causality embedding separately, our differentiable geometry can encode both graph edge weights in its spatial dimensions and causality in the form of edge directionality in its temporal dimensions. We use a product manifold that combines a quasi-metric (for space) and a partial order (for time). NSTs are implemented as three neural networks trained in an end-to-end manner: an embedding network, which learns to optimize the location of nodes as events in the spacetime manifold, and two other networks that optimize the space and time geometries in parallel, which we call a neural (quasi-)metric and a neural partial order, respectively. The latter two networks leverage recent ideas at the intersection of fractal geometry and deep learning to shape the geometry of the representation space in a data-driven fashion, unlike other works in the literature that use fixed spacetime manifolds such as Minkowski space or De Sitter space to embed DAGs. Our main theoretical guarantee is a universal embedding theorem, showing that any $k$-point DAG can be embedded into an NST with $1+\mathcal{O}(\log(k))$ distortion while exactly preserving its causal structure. The total number of parameters defining the NST is sub-cubic in $k$ and linear in the width of the DAG. If the DAG has a planar Hasse diagram, this is improved to $\mathcal{O}(\log(k)) + 2)$ spatial and 2 temporal dimensions. We validate our framework computationally with synthetic weighted DAGs and real-world network embeddings; in both cases, the NSTs achieve lower embedding distortions than their counterparts using fixed spacetime geometries.