HybridGNN: A Self-Supervised Graph Neural Network for Efficient Maximum Matching in Bipartite Graphs
Chengliang Pan, Yi Qu, Yao Yao, Mujiangshan Wang · Preprints.org · 2024
Solving maximum matching problems in bipartite graphs is critical in fields such as computational biology and social network analysis. This study introduces HybridGNN, a novel graph neural network model designed to efficiently address complex matching problems at scale. HybridGNN combines the capabilities of Graph Attention Networks (GAT), GATv2, and Graph SAGE (SAGEConv) layers, integrating techniques like mixed precision training, gradient accumulation, and Jumping Knowledge networks to enhance computational efficiency and performance. Additionally, the incorporation of Graph Isomorphism Networks (GIN) enhances the model's ability to discriminate between structurally different graphs. A time complexity analysis shows that HybridGNN achieves efficient computation across different layers. When evaluated on an email communication dataset, HybridGNN outperformed traditional algorithms such as Hopcroft-Karp, particularly on large and complex graphs. These results demonstrate that HybridGNN offers a powerful and efficient approach for solving maximum matching problems in bipartite graphs, with potential applications in various fields requiring analysis of large-scale and complex graph data.