Kemeny Constant-Based Optimization of Network Clustering Using Graph Neural Networks

Area of Science:

• Computational chemistry and biomolecular modeling
• Network science and graph theory
• Machine learning and artificial intelligence

Background:

• Graph partitioning (GP) is crucial for analyzing complex network data, but traditional methods struggle with graph structures and diverse criteria.
• Graph neural networks (GNNs) show promise for learning graph representations and addressing GP challenges.
• Existing GNN approaches for GP have not been applied to Markov chains or kinetic networks, common in molecular systems.

Purpose of the Study:

• To develop and evaluate Graph Neural Network (GNN) architectures for graph partitioning (GP) of Markov chains represented as kinetic networks.
• To optimize GP by maximizing the Kemeny constant, a measure reflecting system time scales.
• To adapt GNNs for biomolecular modeling applications, particularly those involving kinetic networks.

Main Methods:

• Proposed several GNN-based architectures, including an encoder-decoder model utilizing GraphSAGE.
• Employed linear layers within GNNs, demonstrating their effectiveness over more complex attention-based models for this specific task.
• Validated the approach on randomly connected graphs, a 1D free energy profile kinetic network, and molecular dynamics data.

Main Results:

• GNN-based architectures successfully performed graph partitioning on kinetic networks, outperforming larger models in certain configurations.
• The method demonstrated effectiveness in clustering random graphs and analyzing molecular dynamics datasets.
• Compared favorably against established partitioning techniques like PCCA+, highlighting the potential of GNNs in this domain.

Conclusions:

• GNNs provide a powerful and adaptable framework for solving the graph partitioning problem in kinetic networks.
• The proposed GNN architectures offer an efficient method for analyzing molecular systems and optimizing the Kemeny constant.
• This work lays the groundwork for large-scale parallel training of GNNs for advanced graph partitioning tasks in computational chemistry and biomolecular modeling.