Graph Neural Networks (GNNs) have demonstrated superior performance across
various graph learning tasks but face significant computational challenges when
applied to large-scale graphs. One effective approach to mitigate these
challenges is graph sparsification, which involves removing non-essential edges
to reduce computational overhead. However, previous graph sparsification
methods often rely on a single global sparsity setting and uniform pruning
criteria, failing to provide customized sparsification schemes for each node's
complex local context. In this paper, we introduce Mixture-of-Graphs (MoG),
leveraging the concept of Mixture-of-Experts (MoE), to dynamically select
tailored pruning solutions for each node. Specifically, MoG incorporates
multiple sparsifier experts, each characterized by unique sparsity levels and
pruning criteria, and selects the appropriate experts for each node.
Subsequently, MoG performs a mixture of the sparse graphs produced by different
experts on the Grassmann manifold to derive an optimal sparse graph. One
notable property of MoG is its entirely local nature, as it depends on the
specific circumstances of each individual node. Extensive experiments on four
large-scale OGB datasets and two superpixel datasets, equipped with five GNN
backbones, demonstrate that MoG (I) identifies subgraphs at higher sparsity
levels ($8.67\%\sim 50.85\%$), with performance equal to or better than the
dense graph, (II) achieves $1.47-2.62\times$ speedup in GNN inference with
negligible performance drop, and (III) boosts ``top-student'' GNN performance
($1.02\%\uparrow$ on RevGNN+\textsc{ogbn-proteins} and $1.74\%\uparrow$ on
DeeperGCN+\textsc{ogbg-ppa}).

使用混合图 (MoG) 技术对图神经网络进行图稀疏化处理，针对每个节点的特定环境选择合适的稀疏方案，并在 Grassmann 流形上生成最优稀疏图，从而实现更高的稀疏度水平、GNN 推理速度的提升，并改善 “顶级学生” GNN 在性能上的表现。

通过图的混合进行图稀疏化

Graph Sparsification via Mixture of Graphs

Graph Neural Networks (GNNs) have revolutionized many Machine Learning (ML)
applications, such as social network analysis, bioinformatics, etc. GNN
inference can be accelerated by exploiting data sparsity in the input graph,
vertex features, and intermediate data in GNN computations. For dynamic
sparsity exploitation, we leverage the heterogeneous computing capabilities of
AMD Versal ACAP architecture to accelerate GNN inference. We develop a custom
hardware module that executes the sparse primitives of the computation kernel
on the Programmable Logic (PL) and efficiently computes the dense primitives
using the AI Engine (AIE). To exploit data sparsity during inference, we devise
a runtime kernel mapping strategy that dynamically assigns computation tasks to
the PL and AIE based on data sparsity. Our implementation on the VCK5000 ACAP
platform leads to superior performance compared with the state-of-the-art
implementations on CPU, GPU, ACAP, and other custom GNN accelerators. Compared
with these implementations, we achieve significant average runtime speedup
across various models and datasets of 162.42x, 17.01x, 9.90x, and 27.23x,
respectively. Furthermore, for Graph Convolutional Network (GCN) inference, our
approach leads to a speedup of 3.9-96.7x compared to designs using PL only on
the same ACAP device.

基于 AMD Versal ACAP 架构，利用数据稀疏性加速图神经网络（GNN）推理，通过自定义硬件模块在可编程逻辑（PL）上执行稀疏计算，利用 AI Engine（AIE）高效计算稠密计算部分，并通过动态分配计算任务的运行时内核映射策略在 PL 和 AIE 上分别进行计算，从而在 VCK5000 ACAP 平台上相比于 CPU、GPU、ACAP 和其他自定义 GNN 加速器实现获得更好的性能，平均速度提升分别为 162.42x、17.01x、9.90x 和 27.23x，对于图卷积网络（GCN）推理，相对于仅使用 PL 设计的方案在同一 ACAP 设备上获得了 3.9-96.7 倍的速度提升。

利用 Versal 体系结构的芯片内异构性加速 GNN 推理

Exploiting On-chip Heterogeneity of Versal Architecture for GNN  Inference Acceleration

GNN inference is a non-trivial task, especially in industrial scenarios with
giant graphs, given three main challenges, i.e., scalability tailored for
full-graph inference on huge graphs, inconsistency caused by stochastic
acceleration strategies (e.g., sampling), and the serious redundant computation
issue. To address the above challenges, we propose a scalable system named
InferTurbo to boost the GNN inference tasks in industrial scenarios. Inspired
by the philosophy of ``think-like-a-vertex", a GAS-like (Gather-Apply-Scatter)
schema is proposed to describe the computation paradigm and data flow of GNN
inference. The computation of GNNs is expressed in an iteration manner, in
which a vertex would gather messages via in-edges and update its state
information by forwarding an associated layer of GNNs with those messages and
then send the updated information to other vertexes via out-edges. Following
the schema, the proposed InferTurbo can be built with alternative backends
(e.g., batch processing system or graph computing system). Moreover, InferTurbo
introduces several strategies like shadow-nodes and partial-gather to handle
nodes with large degrees for better load balancing. With InferTurbo, GNN
inference can be hierarchically conducted over the full graph without sampling
and redundant computation. Experimental results demonstrate that our system is
robust and efficient for inference tasks over graphs containing some hub nodes
with many adjacent edges. Meanwhile, the system gains a remarkable performance
compared with the traditional inference pipeline, and it can finish a GNN
inference task over a graph with tens of billions of nodes and hundreds of
billions of edges within 2 hours.

为了解决工业场景中超大图下，GNN 推理面临的可扩展性、一致性和冗余计算问题，本文提出了一种名为 InferTurbo 的可扩展系统，它基于类似於 Think-like-a-vertex 的 GAS（Gather-Apply-Scatter）模式和影子结点、部分聚集等策略来提高推理性能.