1. 摘要（Abstract）

TGraph是首个基于张量的通用图处理框架，旨在解决现有图系统难以跨硬件后端迁移的问题。传统图处理系统（如Ligra、Gunrock、cuGraph等）多针对特定硬件（如NVIDIA GPU或FPGA）进行深度优化，虽然在特定平台上性能突出，但底层内核（如CUDA、Vitis）导致移植成本极高，无法轻松适配新兴硬件加速器（如TPU、NPU、AMD GPU、Apple MPS等）。TGraph创新性地将图计算构建在张量计算运行时（Tensor Computation Runtimes，简称TCRs）之上，利用PyTorch、TensorFlow等深度学习框架及其编译器和运行时提供的张量接口，实现对多种XPU（统一称呼硬件加速器）的无缝支持，同时无需用户深入底层硬件特性。

框架的核心贡献包括三个方面：一是提出张量中心的计算模型，通过TENSORIZE和COMPUTE两个高层接口将图算法分解为迭代过程，支持BFS、WCC、SSSP、PageRank等多种经典算法；二是抽象出一组图算子（vertexSelect、neighborSelect、reconstruct、aggregate、update），将计算模型与底层张量算子解耦，确保框架在不同TCRs间轻松迁移；三是设计张量驱动的图压缩策略和内存外计算策略，解决XPU内存受限问题，实现对超大规模图的高效处理。

大量实验在13个真实世界数据集（包括cit-Patents、soc-twitter等）上进行，与7个最先进图系统（Gunrock、cuGraph、GraphBLAST、Subway、Galois、Ligra等）对比，结果表明TGraph不仅在性能上全面领先，还成功部署于PyTorch和TensorFlow两大框架，以及NVIDIA GPU、AMD GPU、Apple MPS三种硬件后端。该工作填补了张量中心图处理框架的空白，为异构硬件时代图计算提供了可扩展、可移植的统一解决方案，具有重要的理论创新价值和工程实用意义。

2. 研究背景与问题动机（Introduction）

图数据在社交网络、推荐系统、生物信息学等现实应用中无处不在，过去十年涌现出大量图处理系统，大致可分为共享内存系统（Ligra、Galois、GraphChi等）和分布式系统（Pregel、PowerGraph、GraphX等）。近年来，随着硬件加速器的发展，GPU、FPGA等专用设备被广泛用于加速图计算，代表性工作包括Medusa、CuSha、Gunrock、cuGraph、GraphBLAST等。这些系统通过精心设计的负载均衡、内存访问优化和并行原语，显著提升了图算法的执行效率。然而，所有这些系统都面临一个共同的致命局限：高度硬件特定化。

NVIDIA GPU系统依赖CUDA内核，AMD GPU或Apple MPS则需完全不同的编程接口，FPGA系统更需Vitis等专用工具链。这种硬件绑定导致系统移植成本极高，无法跟上深度学习驱动的新兴加速器（如TPU、NPU）的快速发展。用户每更换一次硬件后端，就必须重写大量低层内核，极大阻碍了图计算在异构计算环境中的普及。同时，现有系统在表达性、可扩展性和可移植性上也存在不足：许多系统针对细粒度顶点/边操作设计，不适合张量级批量并行；部分系统虽支持子图中心模型，但仍依赖硬件特定数据结构，无法跨平台迁移。

TGraph正是针对上述痛点而设计。它首次将图计算完全构建在张量之上，利用TCRs（深度学习框架及其运行时）提供的硬件无关张量算子和自动优化能力（如算子融合、算子下沉、代数简化），实现“一处编写、处处运行”。通过张量中心计算模型和抽象图算子，TGraph既保留了图算法的表达灵活性，又实现了对多种XPU的无缝适配，同时通过压缩和内存外策略解决了大规模图的内存瓶颈。该工作不仅解决了硬件异构性带来的移植难题，也为未来图计算在AI驱动硬件生态中的发展提供了全新范式。

3. 系统架构与高层设计（System Overview）

TGraph采用三层架构，底层为TCRs和硬件层（支持PyTorch、TensorFlow、TVM等框架及NVIDIA GPU、AMD GPU、Apple MPS等XPU），中间为计算层（核心是张量中心计算模块和内存外计算模块），上层为应用层（支持BFS、WCC、SSSP、PageRank、HITS等算法）。存储层提供张量化的图表示（CSR/COO）和压缩模块，进一步节省空间并加速计算。

系统核心是张量中心计算模型，将每个迭代分解为TENSORIZE（将活跃顶点及其邻居组织为大尺寸一维张量）和COMPUTE（基于张量算子进行聚合、更新和活跃性判断）两个步骤。这种设计充分利用张量算子的批量并行能力，同时通过抽象的五种图算子（vertexSelect、neighborSelect、reconstruct、aggregate、update）屏蔽底层张量细节，确保计算模型与具体TCRs解耦。

为处理超大规模图，TGraph在存储层引入张量驱动的图压缩策略，通过虚拟顶点递归替换重复邻居序列，实现多层CSR表示；在计算层设计内存外计算策略，包括边均衡分区（EBP）和良好连接分区（WCP），结合流水线调度机制，实现主机内存与XPU内存的高效协同。该架构既保证了高性能，又实现了跨硬件、跨框架的极致可扩展性，是TGraph区别于传统图系统的关键创新点。

4. 张量中心计算模型与图算子（Tensor-centric Computation Model）

TGraph的核心创新在于提出张量中心计算模型，将图算法抽象为迭代过程：TENSORIZE负责从完整图中提取活跃子图并组织为张量，COMPUTE则在子图上执行聚合、更新和活跃性标记。算法1给出了概念流程：首先初始化顶点数据vData和活跃掩码actMask，随后循环调用TENSORIZE和COMPUTE，直至无活跃顶点。

为方便用户实现，TGraph进一步抽象五种图算子。vertexSelect用于从顶点集中选取子集；neighborSelect高效提取指定顶点的邻居；reconstruct将顶点子集及其邻居重构为张量子图；aggregate支持push/pull两种模式对邻居数据进行min/sum等聚合；update则根据聚合结果更新顶点值和活跃掩码。这些算子全部基于标准张量算子（如index_select、repeat_interleave、scatter_reduce、segment_csr等）实现，既保证了表达性，又实现了与底层TCRs的完全解耦。

算法表达性分析表明，这些算子可覆盖线性代数图系统（如GraphBLAS、GraphBLAST）的大多数原语，支持广泛的迭代类图算法。实际实现中，TGraph通过动态切换push/pull模式和优化关键张量算子，进一步提升性能。例如，aggregate在活跃顶点较多时自动切换到pull模式避免原子操作，在活跃顶点较少时使用push模式减少无效计算。这种设计既简化了用户编程，又最大化了张量并行潜力。

5. 扩展策略：图压缩与内存外计算（Scaling Strategies）

针对XPU内存受限问题，TGraph提出两大扩展策略。首先是张量驱动的图压缩：识别高频重复邻居序列并用虚拟顶点替换，形成多层嵌套CSR表示。压缩后图以分层张量CSR存储，并引入virtualMask标记虚拟顶点。计算时需按层级从低到高（pull模式）或高到低（push模式）遍历，确保数据依赖正确。该策略在AR和IT数据集上实现了4.35~4.65倍压缩比，显著降低存储开销并加速计算。

其次是内存外计算策略：先通过边均衡分区（EBP，使用searchsorted实现快速平衡边数）或良好连接分区（WCP，通过多轮多源BFS+合并生成高内聚子图）将图划分为多个子图，随后采用流水线调度机制。LoadQueue存储待调度子图ID，加载线程负责从主机内存加载子图到ComputeQueue，计算线程则在XPU上执行子图计算，同时利用共享数据区实现子图间消息传递。这种重叠加载与计算的设计，极大减少了数据传输开销，实现了对TB级图的高效处理。

6. 实验评估与性能分析（Experiments）

实验在13个真实世界数据集（从cit-Patents到sk-2005，边数从千万到数十亿）上进行，与7个最先进系统（Gunrock、cuGraph、GraphBLAST、Subway、Galois、Ligra等）全面对比。硬件环境为Intel Xeon Gold 6330 CPU + NVIDIA RTX 3090 GPU（24GB显存），软件基于PyTorch 1.11。

整体性能结果显示，TGraphG在PR、HITS等计算密集型算法上领先最多，在BFS、WCC等内存密集型算法上也保持竞争力。Nsight Compute性能剖析证实TGraphG通过动态push/pull切换避免原子操作，显著提升L1/L2/DRAM缓存吞吐量。

可扩展性评估表明，图压缩策略在AR/IT数据集上实现高效处理；内存外计算在TW/GS/SK等超大图上性能优于Ligra、Galois和Subway。跨硬件/框架测试进一步验证了TGraph在AMD GPU、Apple MPS、V100以及TensorFlow上的无缝部署，充分证明了框架的极致可移植性。消融实验和成本效益分析也显示，TGraph在性能、内存和开发效率上均取得良好平衡。

7. 贡献与结论（Contributions and Conclusion）

TGraph的主要贡献包括：（1）提出张量中心计算模型及TENSORIZE/COMPUTE接口，支持高效图算法实现；（2）抽象五种图算子，实现计算模型与底层张量算子的完全解耦，确保跨TCRs迁移；（3）设计张量驱动的图压缩和内存外计算策略，解决大规模图处理难题；（4）实现首个可跨DL框架和XPU部署的图处理框架；（5）通过全面实验验证TGraph在性能、可扩展性和可移植性上的全面优势。

论文结论指出，TGraph成功将深度学习生态中的张量计算能力引入图处理领域，为异构硬件时代提供了统一、高效、可移植的图计算解决方案。尽管当前主要聚焦单机图分析，但框架的开放设计为未来分布式、多模态图计算等扩展奠定了坚实基础。该工作不仅具有重要的学术创新价值，也为工业界在AI硬件生态中部署图计算提供了可落地的技术路径。