Machine Learning Predicts Robber Capture with 99% Accuracy

Scientists are increasingly turning to machine learning to tackle complex problems in graph theory, and a new study explores the potential of these techniques to predict the cop number of a graph. Meagan Mann, Christian Muise, and Erin Meger, all from Queen’s University, demonstrate that classical machine learning models and graph neural networks can accurately estimate a graph’s cop number, the minimum number of ‘cops’ needed to capture a ‘robber’ , based on its structural properties. Determining the cop number is computationally challenging, often limited to smaller graphs, but this research reveals that tree-based machine learning models perform well even with imbalanced datasets, while graph neural networks achieve similar results without needing manually defined features. By identifying key features like node connectivity and clique structure as strong predictors, the team provides insights that align with existing theoretical understanding and suggests machine learning can offer scalable approximations when exact computation is impractical.

Within a chilled chamber, algorithms now estimate how effectively a pursuer can corner a target on a complex network. Predicting this ‘cop number’ has long relied on painstaking calculation, limiting progress to simpler scenarios. Machine learning offers a shortcut, rapidly assessing a network’s structure to gauge its capture potential. Scientists have long studied pursuit-evasion games on graphs, with the “Cops and Robbers” problem receiving particular attention over the past four decades.

This game explores the minimum number of “cops” needed to guarantee capture of a single “robber” moving across a network. Determining this “cop number” for a given graph presents a significant computational challenge, with existing algorithms largely limited to smaller, simpler graph structures. Researchers are now turning to machine learning to estimate cop numbers for more complex graphs where exact calculation proves impractical.

Recent work investigates whether both traditional machine learning techniques and more modern graph neural networks can accurately predict a graph’s cop number based solely on its inherent structural characteristics. Initial findings reveal that tree-based machine learning models demonstrate a surprising ability to predict cop numbers, even when faced with an uneven distribution of graph types.

Simultaneously, graph neural networks achieve comparable predictive power without requiring researchers to manually select and engineer relevant features. Beyond simply predicting the cop number, this research also seeks to understand which structural properties are most influential in determining a graph’s vulnerability to capture. Interpretability analysis points to factors like node connectivity, the presence of tightly-knit clusters, the size of cliques, fully connected subgraphs, and measures of graph “width” as key determinants.

These findings resonate with established theoretical results, suggesting machine learning can not only approximate solutions but also refine our understanding of the underlying principles governing this game. The potential extends beyond theoretical validation. By offering scalable approximations, machine learning approaches could complement existing algorithms, enabling analysis of larger, more complex networks where traditional computation falters.

Determining the cop number is computationally difficult, so the ability to estimate it efficiently opens doors to applications in network security, search algorithms, and even modelling the spread of information or disease across interconnected systems. Investigations currently focus on datasets of graphs with up to nine vertices, alongside approximately 40 computed structural features.

These features encompass measures of graph size, connectivity, clique structure, and other properties calculated using custom functions and the NetworkX library. The exhaustive nature of the dataset, sourced from McKay’s Small Graphs Database, ensures a diverse representation of graph structures for training and evaluation.

Predictive accuracy of graph cop number via machine learning and topological features

Tree-based machine learning models accurately predict the cop number of graphs up to size 13, achieving high performance despite inherent class imbalance within the dataset. These models demonstrated predictive capability when trained on handcrafted graph properties. Specifically, the models consistently estimated cop numbers with a level of accuracy previously unattainable without computationally expensive exact algorithms.

Graph neural networks attained comparable predictive accuracy without requiring explicit feature engineering, suggesting the relevant information resides within the graph’s topology itself. Interpretability analysis revealed that node connectivity, clustering, clique structure, and width parameters were the most predictive features for determining cop number.

At a granular level, these properties strongly correlate with established theoretical results concerning the cop number of graphs. For instance, graphs exhibiting higher clustering coefficients tended to have lower cop numbers, aligning with the expectation that denser, more interconnected graphs are easier for cops to navigate and capture the robber.

The research pinpointed that the most informative features consistently related to measures of graph density and connectivity. Once evaluated, the models were used to assess the importance of different graph properties. By identifying which features most strongly influenced cop number prediction, researchers gained insight into the underlying structural characteristics that govern this game-theoretic property.

This understanding complements existing theoretical bounds on cop number, potentially refining and extending current knowledge in the field. The work highlights the potential for machine learning to offer scalable approximations when exact computation becomes infeasible for larger graph classes. Also, the findings support the idea that graph structure itself contains substantial information for predicting graph-level properties.

Unlike approaches relying on node features, graph neural networks successfully learned to predict cop number directly from graph topology. By demonstrating this capability, the research opens avenues for developing more generalizable and efficient algorithms for analysing graph properties. The team intends to explore the application of these methods to even larger graphs, where computational limitations currently hinder exact determination of cop number.

Graph Structure Prediction using Network Properties and Gradient Boosting

A dataset of 6,250 graphs was constructed, encompassing cop numbers ranging from 1 to 10. Each graph was subjected to computation of 28 distinct structural properties, serving as potential predictors for the cop number. These properties included measures of node connectivity and clustering coefficients to quantify the degree to which nodes tend to cluster together.

Clique numbers, representing the size of the largest complete subgraph, were also determined alongside various width parameters, such as the tree-width and path-width, which describe the graph’s structural complexity. Classical machine learning models were then trained and evaluated. Tree-based models, specifically Gradient Boosting, were selected due to their established performance with tabular data and ability to handle class imbalance.

Data was split into training, validation, and test sets, with the validation set used for hyperparameter tuning. To address the inherent class imbalance, techniques like weighted loss functions were employed during training. Alongside these classical approaches, graph neural networks (GNNs) were implemented. These networks directly process the graph structure, bypassing the need for manual feature engineering.

GNNs learn node embeddings, which capture the local and global structural information of each node, and these embeddings are then used to predict the cop number. A relatively simple GNN architecture was prioritised, focusing on interpretability and computational efficiency. Assessing feature importance was also a priority. Shapley values, a concept from cooperative game theory, were calculated for both the tree-based models and the GNNs.

This allowed for the quantification of each feature’s contribution to the model’s predictions, revealing which structural properties were most influential in determining the cop number. By comparing the feature importance rankings from the machine learning models with known theoretical results, researchers aimed to validate the models and gain insights into the underlying relationship between graph structure and the cop number.

Predicting pursuit dynamics in networks via machine learning

For decades, the ‘cops and robbers’ problem, a mathematical pursuit game played on networks, has resisted easy solutions, with determining the minimum number of ‘cops’ needed to catch a single ‘robber’ proving computationally demanding. This work offers a shift in approach, moving away from direct calculation towards prediction using machine learning.

Instead of seeking definitive answers for complex graphs, researchers are now exploring whether algorithms can accurately estimate a graph’s ‘cop number’ based on its underlying structure. The success of tree-based machine learning models and graph neural networks in this task is more than just a technical achievement. It suggests a viable path for handling networks where precise calculation is impossible, offering approximations that could be useful in areas like network security or resource allocation.

Reliance on structural features like node connectivity and clustering, already known to influence the game, doesn’t necessarily reveal entirely new insights into the problem itself. A key limitation lies in the inherent difficulty of interpreting these predictive models. While the identified features align with existing theory, understanding why certain structures lead to higher cop numbers remains an open question.

A deeper theoretical understanding of the game is still desired. Once more refined, these predictive tools could become part of a broader set of tools, used alongside existing algorithms to tackle increasingly complex network problems. Beyond this specific game, the methodology itself, applying machine learning to problems in graph theory, could open avenues for addressing other computationally hard challenges in network science.