cs.NENov 12, 2026

Similarity-Guided Optimization Strategies for Approximate Network Symmetry Detection

Authors: David Hartman, Jaroslav Hlinka, Dominik Klepl, Anna Pidnebesna, Petra Vidnerová

Organizations: Institute of Computer Science of the Czech Academy of Sciences, Prague, Czech Republic · Unicorn University, Prague, Czech Republic · National Institute of Mental Health, Klecany, Czech Republic

Abstract

Symmetry in complex networks is a structural property with broad implications for network function, dynamics, and robustness. While classical approaches rely on exact automorphisms and thus remain highly sensitive to small perturbations, recent work of Liu has introduced approximate formulations that relax the strict invariance condition and recast symmetry detection as an optimization problem over permutations. We investigate how node-level similarity information can be used to bias the search toward structurally plausible vertex correspondences, with network centralities serving as one interpretable instance. Building on this perspective, we adapt simulated annealing, genetic algorithms, tabu search, particle swarm optimization, differential evolution and the quadratic symmetry approximator to this problem, add similarity guidance to each, and introduce Bilinear Approximate Symmetry Inference (BASIN), which learns a soft assignment matrix via bilinear embeddings. Using a unified evaluation pipeline, we compare their guided and unguided variants, BASIN and a random baseline on four synthetic graph families, structural brain connectomes, and three empirical networks with known automorphism groups. Node-similarity guidance is decisive where a planted orbit exists that the unguided search misses, and algorithm-dependent elsewhere, on synthetic and empirical networks alike. Overall, tabu search achieves the strongest performance; its guided variant (SGTS) has the lowest median score among the guided variants in all 44 synthetic conditions, while BASIN is the better of the continuous relaxations on rewired lateral graphs. The effect of node-similarity guidance is therefore regime-dependent rather than uniformly positive.

Figures & tables

Appendix figures & tables71 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Discovering Symmetries in Neural Network Parameter Spaces

    Sep 27, 2026Bo Zhao, Nima Dehmamy, Robin Walters +1Scientific DiscoverySymmetry Discovery

  2. A Nonmonotone Gradient-Based Algorithm for Symmetric Nonnegative Matrix Factorization and Graph Clustering

    Jun 1, 2026Ryan Swart, Johannes BrustNon-Negative Matrix FactorizationGraph Clustering