Organizations: Institut de Recherche en Informatique de Toulouse, Toulouse, France. · Artificial and Natural Intelligence Toulouse Institute, Toulouse, France. · Centre National de la Recherche Scientifique, France. · Delft Institute of Applied Mathematics, Delft University of Technology, Delft, Netherlands. · Toulouse-INP (ENSEEIHT), Toulouse, France. · Department of Computer Science, University of Geneva, Geneva, Switzerland.
Graph neural networks (GNNs) have emerged as a powerful framework for learning from graph-structured data. However, their efficient training remains challenging, particularly in distributed computing environments. This challenge arises from the use of message passing, which couples all graph nodes, leading to expensive optimization steps, high memory requirements, and substantial communication overhead. To alleviate these limitations, we propose a novel domain-decomposition (DD) variant of AG2m, an AdaGrad method enhanced with second-order curvature information and momentum, denoted by DD-AG2m. The proposed DD-AG2m alternates between AG2m optimization on the original (global) graph and AG2m optimization on the partitioned graphs. To incorporate global information at reduced cost, we further introduce a two-level variant (2DD-AG2m) that performs global optimization steps on a coarse graph obtained by randomly subsampling nodes within each subdomain. Numerical experiments spanning graph classification, node-level regression, and spatiotemporal forecasting tasks demonstrate that the proposed DD methods reduce the computational cost required to achieve the same predictive performance by a factor of 4-8. Moreover, for the fixed computational cost, they improve the predictive performance of GNNs by up to 22% compared with the baseline AG2m.
Figures & tables
Figure 1: Illustration of MP aggregation for node v1 with feature vector h1 . The sketch is adapted from 47 .
Figure 2: An example of non-overlapping graph partitioning. The original graph (left) and a partition of the node set \pazocalV into P=3 disjoint subsets \pazocalV1,\pazocalV2,\pazocalV3 (right).
Figure 3: Sketch of the per-subdomain random node subsampling to create the coarse graph. The original graph (left) and the coarse graph \pazocalGC , formed by the selected nodes together with the edges inherited between them (right).
CIFAR10
AirfRANS
METR-LA
Learning task
Graph classification
Node regression
Spatiotemporal regression
GNN architecture
GCN 25
GraphSAGE 3
DCRNN 34
Number of layers
4
4
2
Layer width
146
64
32
Loss function
Cross-entropy
MSE
Masked MAE
Graph partitioner
Spectral 53
Morton ordering 36
Multilevel Graclus 10
Table 1: Summary of the benchmark problems and the associated experimental setup.
Figure 4: Example of a sample from CIFAR10 and its corresponding super-pixel graph 12 : the original image (left), the super-pixel nodes (middle left), the k -nearest-neighbor graph (middle right), and the resulting graph (right).
Figure 5: Example of flow fields around a NACA airfoil from the AirfRANS dataset: the pressure divided by specific mass (left) and the velocity field in the x -direction (right).
Figure 6: Example of a sample from the METR-LA dataset 34 : the sensor locations (left) and the corresponding graph partitioned into 5 subgraphs (right).
Figure 7: Convergence of AG2 and AG2m on the CIFAR10 (left) and AirfRANS (right) benchmark problems. The results are reported in terms of the validation accuracy (acc val ) for CIFAR10 and the validation loss ( \pazocalLval ) for AirfRANS.
Figure 8: Convergence of AG2m and DD-AG2m with varying KG for the CIFAR10. DD-AG2m is executed with P={2,3,5} (from left to right), and Kp=∣\pazocalD∣ .
Figure 9: Convergence of AG2m and DD-AG2m ( P=2 , KG=∣\pazocalD∣ ) with varying Kp for the CIFAR10 (left), for AirfRANS (middle) and for METR-LA (right).
Figure 10: Convergence of AG2m and DD-AG2m ( KG=Kp=∣\pazocalD∣ ) with increasing number of partitions P for the CIFAR10 (left), AirfRANS (middle), and METR-LA (right).
Figure 11: Convergence of AG2m and 2DD-AG2m ( KG=10,cf=2 ) with varying KC for the CIFAR10, P=2 (left), P=3 (middle), and P=5 (right).
Figure 12: Convergence of AG2m and 2DD-AG2m ( KG=10,KC=Kp=∣\pazocalD∣ ) on the AirfRANS (top) and METR-LA (bottom), with the coarsening factors cf=2 (left) and cf=4 (right) for different numbers of graph partitions P .
Figure 13: Convergence of AG2m , DD-AG2m ( KG=Kp=∣\pazocalD∣ , P=5 ) and 2DD-AG2m ( KG=10,KC=Kp=∣\pazocalD∣ , P=5 ) on the CIFAR10 (left, cf=2 ), AirfRANS (middle, cf=4 ), and METR-LA (right, cf=4 ).
Graph Neural Networks (GNNs) are widely used for learning on graph-structured data, but scaling GNN training to massive graphs remains challenging. To enable scalable distributed training, graphs are divided into smaller partitions that are distributed across multiple machines such that inter-machine communication is minimized and computational load is balanced. In practice, existing partitioning approaches face a fundamental trade-off between partitioning overhead and partitioning quality. We propose EmbedPart, an embedding-driven partitioning approach that achieves both speed and quality. Instead of operating directly on irregular graph structures, EmbedPart leverages node embeddings produced during the actual GNN training workload and clusters these dense embeddings to derive a partitioning. EmbedPart achieves more than 100x speedup over Metis while maintaining competitive partitioning quality and accelerating distributed GNN training. Moreover, EmbedPart naturally supports graph updates and fast repartitioning, and can be applied to graph reordering to improve data locality and accelerate single-machine GNN training. By shifting partitioning from irregular graph structures to dense embeddings, EmbedPart enables scalable and high-quality graph data optimization.
Nikolai Merkel, Ruben Mayer, Volker Markl +1
Technical University of Munich (TUM) · University of Bayreuth · TU Berlin, BIFOLD, DFKI +1
Topological Deep Learning extends graph-based learning to higher-order domains, such as hypergraphs, cellular, and simplicial complexes. These domains are typically constructed from patterns in an input graph through a process of graph lifting. Full-domain training constructs and stores the complete lifted representation before model execution. On large and dense datasets like Reddit (233k nodes and 57.3M edges), this global materialization becomes a severe computational bottleneck, often rendering training infeasible. To address this limitation, we introduce Cluster-TNN, a domain-agnostic framework that avoids this bottleneck by lifting locally instead. After partitioning the input graph during preprocessing, at runtime Cluster-TNN dynamically samples groups of node clusters, reconstructs their induced subgraphs to form mini-batches, and applies the chosen lifting within each mini-batch. Retaining all edges among sampled nodes preserves the connectivity needed to construct higher-order structures across clusters, producing topological mini-batches that existing Topological Neural Networks can process directly. Across 21 matched comparisons with full-graph execution, Cluster-TNN reduces peak GPU memory in every configuration, by 83.2% on average while maintaining competitive predictive performance. Notably, such a reduction enables, to our knowledge, the first training of multiple different higher-order Topological Neural Networks on large datasets such as Reddit and OGBN Products. These results establish Cluster-TNN as a general strategy for scaling Topological Deep Learning beyond the limitations of global domain construction.
David Leko, Luka Benić, Guillermo Bernárdez +3
IMOS Lab, EPFL, Lausanne, Switzerland · University of Zagreb, Zagreb, Croatia · UC Santa Barbara, Santa Barbara, USA +1
Multi-domain graph pre-training is a crucial step in constructing foundational graph models with cross-domain generalization capabilities. However, existing methods predominantly rely on jointly training all source domain graphs, resulting in high computational costs. Furthermore, it remains unclear whether all source domain graph data contribute equally to effective transfer. This paper empirically reveals significant data redundancy in multi-domain graph pre-training. Based on this finding, we propose the Multi-domain Graph Pre-training Framework, MDGMIX, which combines boundary-aware subgraph mixing with hierarchical discrimination. By selecting boundary nodes to construct challenging mixed-domain subgraphs, MDGMIX employs coarse-grained domain discrimination and fine-grained domain decomposition losses to decouple shared patterns from domain-specific patterns. During adaptation, MDGMIX employs a lightweight prompt weighting mechanism to transfer source domain knowledge. Extensive experiments demonstrate that MDGMIX consistently outperforms strong baselines in few-shot classification tasks while exhibiting superior time and memory efficiency. The code is available at: https://github.com/zhengziyu77/MDGMIX.
Ziyu Zheng, Yaming Yang, Ziyu Guan +2
School of Computer Science and Technology, Xidian University, Xi’an, China · School of Artificial Intelligence, Xidian University, Xi’an, China