Abstract
Graph partitioning (GP) is a critical task in network science, yet it remains computationally expensive for large-scale datasets. This paper introduces RaftGP (RAndom FasT Graph Partitioning), a novel method that leverages Gaussian random projections and untrained Graph Neural Networks (GNNs) to achieve state-of-the-art accuracy with significant speedups. By treating the GNN architecture as a spatial filter rather than a learnable model, RaftGP bypasses the costly training phase typical of modern deep learning approaches. Experimental results on the IEEE HPEC Graph Challenge benchmarks demonstrate that RaftGP outperforms traditional baselines by up to 64x in speed while maintaining near-perfect partitioning accuracy.
1. Introduction
Graph Partitioning, or community detection, involves clustering nodes such that intra-cluster connectivity is maximized and inter-cluster connectivity is minimized. While fundamental to fields ranging from social network analysis to parallel computing, the problem is NP-hard. Existing methodologies generally bifurcate into two categories: traditional statistical models, such as Stochastic Block Models (SBM), which scale poorly with graph size, and GNN-based methods, which require extensive training and hyperparameter tuning. RaftGP proposes a "third way" by combining the efficiency of random projections with the structural expressivity of GNNs, all without the need for backpropagation.
2. Methodology
RaftGP operates through a three-stage pipeline designed for maximum throughput and scalability.
2.1 Random Feature Extraction
To avoid the computational burden of processing massive, dense matrices (e.g., Modularity or Normalized Cut matrices), RaftGP employs Gaussian random projection. This technique projects high-dimensional graph data into a lower-dimensional space. Mathematically, this preserves the pairwise distances between nodes, ensuring that the underlying community structure remains intact while reducing the dimensionality to a manageable scale.
2.2 Random Embedding Derivation
The core innovation of RaftGP lies in its use of an untrained multi-layer Graph Convolutional Network (GCN). The authors demonstrate that a single forward pass through a randomly initialized GCN acts as a sophisticated multi-hop feature aggregator. In this context, the GNN functions as a spatial filter that smooths features across neighboring nodes, enhancing the community signal. This approach proves that for partitioning tasks, the structural inductive bias of the GNN architecture is often more critical than the specific values of the weights.
2.3 Hierarchical Model Selection
Determining the optimal number of communities ($K$) is a persistent challenge in GP. RaftGP addresses this via a recursive splitting algorithm. The graph is iteratively bisected using KMeans. To determine whether a split is valid or if the recursion should terminate, the authors introduced a "local modularity" metric. Unlike global modularity, which can lead to over-partitioning, local modularity accounts for the edges connecting a subgraph to the broader network, ensuring that communities are not fragmented unnecessarily.
3. Experimental Setup
The performance of RaftGP was evaluated using the IEEE HPEC Graph Challenge benchmark. The researchers utilized synthetic graphs generated via the Stochastic Block Model (SBM), with node counts ranging from 1,000 ($10^3$) to 200,000 ($2 \times 10^5$). These datasets were specifically configured to represent high block size heterogeneity, representing the most challenging scenarios within the benchmark suite. To facilitate this, the authors also developed a nearly linear-time graph generator to overcome the limitations of existing benchmark tools.
4. Results and Discussion
RaftGP was recognized as the Innovation Award Winner at the IEEE HPEC 2023 Graph Challenge due to its exceptional performance metrics:
- Computational Efficiency: On graphs containing 100,000 nodes, RaftGP achieved a speedup of at least 64.5x compared to the MC-SBM baseline. On smaller-scale graphs, it consistently remained 6x to 23x faster than competing methods.
- Partitioning Accuracy: Despite the lack of training, RaftGP achieved near-perfect scores across Accuracy, Adjusted Rand Index (ARI), and F1-score (frequently > 0.99). It successfully partitioned large datasets where greedy and spectral modularity methods either timed out or suffered from Out-of-Memory (OOM) errors.
- Scalability: While traditional statistical methods required nearly three hours (10,000+ seconds) to process the largest test cases, RaftGP completed the same tasks in approximately 370 seconds.
5. Conclusion and Future Work
RaftGP demonstrates that the combination of random projections and untrained GNN architectures provides a powerful, scalable solution for graph partitioning. Currently, the primary bottleneck is the hierarchical model selection process, which accounts for roughly 80% of the total execution time. Future research will focus on optimizing this recursive splitting phase and extending the RaftGP framework to dynamic or streaming graphs. Given that RaftGP requires no training, it is uniquely positioned to handle real-time network updates where traditional models would require constant, expensive retraining.
Summary updated