Learning Heuristics over Large Graphs via Deep Reinforcement Learning
GCOMB combines GCN and Q-learning, enabling scalable, high-quality heuristics on billion-scale graphs, achieving 100x speedup with marginally better solutions.
Key Findings
Methodology
GCOMB integrates a probabilistic greedy mechanism to train a Graph Convolutional Network (GCN) for node quality prediction, and employs importance sampling within a Q-learning framework to focus on promising nodes. The framework combines supervised learning for node embeddings with reinforcement learning for solution set construction, allowing efficient handling of billion-scale graphs. During training, edge weights and node features are used to generate labels via the probabilistic greedy approach, which samples multiple solution sets to estimate node marginal gains. In inference, the trained GCN filters out low-potential nodes, and Q-learning determines the final node set, all in a single forward pass, avoiding iterative procedures. This design significantly reduces computational complexity while maintaining solution quality.
Key Results
- On YouTube social network data, GCOMB outperforms GCT-TreeSearch by 100x in runtime, with solution quality comparable or slightly better, especially in influence maximization where speed is increased 150x.
- In synthetic and real datasets like Gowalla and Twitter-ego, GCOMB achieves higher coverage and solution quality than S2V-DQN and GCT-TreeSearch, with training times reduced to minutes.
- Across multiple large-scale graphs, GCOMB demonstrates stable performance, with solution quality close to optimal and computational efficiency orders of magnitude better than baselines.
Significance
This work addresses the critical challenge of scalable learning heuristics for large graphs, enabling practical deployment in social networks, recommendation systems, and infrastructure planning. By effectively combining GCN and reinforcement learning, it overcomes the limitations of previous methods that struggled with billion-scale graphs. The probabilistic greedy training and importance sampling innovations provide a new paradigm for efficient, generalizable graph optimization, opening avenues for future research in dynamic and multi-task graph learning.
Technical Contribution
The paper introduces a novel training scheme that integrates probabilistic greedy sampling with GCN, enabling the prediction of node contributions at scale. It further innovates by applying importance sampling to reduce neighborhood computation costs, making the approach feasible for billion-edge graphs. The architecture combines supervised node embedding with a Q-learning module that models the combinatorial decision process, providing a unified, lightweight framework that surpasses previous state-of-the-art in both speed and solution quality. Theoretical analysis confirms the efficiency gains and approximation guarantees under certain conditions.
Novelty
This study is the first to embed probabilistic greedy sampling into GCN training for large-scale graph heuristics, and to leverage importance sampling within a reinforcement learning context for combinatorial problems. Unlike prior works like S2V-DQN and GCT-TreeSearch, which are either end-to-end or iterative, GCOMB’s single-pass inference and hybrid architecture enable unprecedented scalability. These innovations collectively push the boundary of what is achievable in large-scale graph optimization.
Limitations
- The approach relies on static graph features and may underperform in highly dynamic or evolving graphs where training data quickly becomes outdated.
- Node quality prediction can be biased in highly unbalanced or noisy graphs, affecting the final solution quality.
- Although importance sampling reduces complexity, it introduces stochasticity and potential variance in locality estimates, which may impact stability in some scenarios.
Future Work
Future research will explore adaptive online learning to handle dynamic graphs, multi-task frameworks for different combinatorial problems, and more sophisticated sampling strategies to further reduce variance. Extending the approach to heterogeneous graphs and incorporating temporal information are promising directions to broaden applicability and robustness.
AI Executive Summary
In recent years, the explosion of large-scale graph data—ranging from social networks to infrastructure systems—has posed significant challenges for traditional combinatorial optimization algorithms. Classic greedy or approximation methods, while effective on small or medium graphs, struggle to scale to billions of nodes and edges. Meanwhile, recent advances in graph neural networks (GNNs) and reinforcement learning have shown promise in learning heuristics, but their scalability remains limited. This gap has hindered practical deployment in real-world, large-scale scenarios.
Addressing this critical bottleneck, the paper introduces GCOMB, a novel framework that synergistically combines Graph Convolutional Networks (GCN) with deep Q-learning. The core innovation lies in a probabilistic greedy training mechanism that guides the GCN to predict node contributions efficiently. By integrating importance sampling, GCOMB reduces the computational burden of neighborhood aggregation, enabling it to handle graphs with billions of edges. During inference, the model performs a single pass: first filtering out nodes unlikely to contribute to the solution, then applying Q-learning to select the optimal subset within the given budget.
Extensive experiments on real large-scale datasets such as YouTube, Gowalla, and Twitter demonstrate GCOMB’s remarkable performance. It achieves solution quality comparable or superior to the best algorithms, while being up to 100 times faster. Notably, in influence maximization tasks, GCOMB’s speed surpasses specialized algorithms like IMM by 150 times, with minimal loss in solution quality. These results highlight GCOMB’s potential to revolutionize large-scale graph optimization, making it feasible for real-time, dynamic applications.
The significance of this work extends beyond mere speed. By effectively combining supervised and reinforcement learning, GCOMB offers a flexible, generalizable approach that can adapt to various combinatorial problems and graph types. Its lightweight architecture and single-pass inference make it suitable for deployment in industry-scale systems, opening new avenues for research and practical solutions in social network analysis, recommendation engines, and infrastructure planning. Despite its strengths, challenges remain in handling highly dynamic graphs and noisy data, which the authors plan to address in future work. Overall, GCOMB marks a substantial step forward in scalable, intelligent graph optimization.
Deep Dive
Abstract
There has been an increased interest in discovering heuristics for combinatorial problems on graphs through machine learning. While existing techniques have primarily focused on obtaining high-quality solutions, scalability to billion-sized graphs has not been adequately addressed. In addition, the impact of budget-constraint, which is necessary for many practical scenarios, remains to be studied. In this paper, we propose a framework called GCOMB to bridge these gaps. GCOMB trains a Graph Convolutional Network (GCN) using a novel probabilistic greedy mechanism to predict the quality of a node. To further facilitate the combinatorial nature of the problem, GCOMB utilizes a Q-learning framework, which is made efficient through importance sampling. We perform extensive experiments on real graphs to benchmark the efficiency and efficacy of GCOMB. Our results establish that GCOMB is 100 times faster and marginally better in quality than state-of-the-art algorithms for learning combinatorial algorithms. Additionally, a case-study on the practical combinatorial problem of Influence Maximization (IM) shows GCOMB is 150 times faster than the specialized IM algorithm IMM with similar quality.