Kemeny Constant-Based\nOptimization of Network Clustering\nUsing Graph Neural Networks

The recent trend in using network and graph structures\nto represent\na variety of different data types has renewed interest in the graph\npartitioning (GP) problem. This interest stems from the need for general\nmethods that can both efficiently identify network communities and\nreduce the dimensionality of large graphs while satisfying various\napplication-specific criteria. Traditional clustering algorithms often\nstruggle to capture the complex relationships within graphs and generalize\nto arbitrary clustering criteria. The emergence of graph neural networks\n(GNNs) as a powerful framework for learning representations of graph\ndata provides new approaches to solving the problem. Previous work\nhas shown GNNs to be capable of proposing partitionings using a variety\nof criteria. However, these approaches have not yet been extended\nto Markov chains or kinetic networks. These arise frequently in the\nstudy of molecular systems and are of particular interest to the biomolecular\nmodeling community. In this work, we propose several GNN-based architectures\nto tackle the GP problem for Markov Chains described as kinetic networks.\nThis approach aims to maximize the Kemeny constant, which is a variational\nquantity and it represents the sum of time scales of the system. We\npropose using an encoder-decoder architecture and show how simple\nGraphSAGE-based GNNs with linear layers can outperform much larger\nand more expressive attention-based models in this context. As a proof\nof concept, we first demonstrate the method’s ability to cluster\nrandomly connected graphs. We also use a linear chain architecture\ncorresponding to a 1D free energy profile as our kinetic network.\nSubsequently, we demonstrate the effectiveness of our method through\nexperiments on a data set derived from molecular dynamics. We compare\nthe performance of our method to other partitioning techniques, such\nas PCCA+. We explore the importance of feature and hyperparameter\nselection and propose a general strategy for large-scale parallel\ntraining of GNNs for discovering optimal graph partitionings.