# Similarity-Guided Optimization Strategies for Approximate Network Symmetry Detection

DevFeed: [Similarity-Guided Optimization Strategies for Approximate Network Symmetry Detection](<https://devfeed.tech/articles/similarity-guided-optimization-strategies-for-approximate-network-symmetry-detection-133125.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.16555>)

Author: David Hartman, Jaroslav Hlinka, Dominik Klepl, Anna Pidnebesna, Petra Vidnerov\\'a

Published: 2026-11-13T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [graph theory](<https://devfeed.tech/topics/graph-theory.md>), [Embeddings](<https://devfeed.tech/topics/embeddings.md>)

Tags: [abstract](<https://devfeed.tech/tags/abstract.md>), [algorithm](<https://devfeed.tech/tags/algorithm.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [all](<https://devfeed.tech/tags/all.md>), [arxiv](<https://devfeed.tech/tags/arxiv.md>), [automorphism-groups](<https://devfeed.tech/tags/automorphism-groups.md>), [better](<https://devfeed.tech/tags/better.md>), [bias](<https://devfeed.tech/tags/bias.md>), [brain](<https://devfeed.tech/tags/brain.md>), [building](<https://devfeed.tech/tags/building.md>), [can](<https://devfeed.tech/tags/can.md>), [compare](<https://devfeed.tech/tags/compare.md>), [complex](<https://devfeed.tech/tags/complex.md>), [condition](<https://devfeed.tech/tags/condition.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [cs-ne](<https://devfeed.tech/tags/cs-ne.md>), [detection](<https://devfeed.tech/tags/detection.md>), [network](<https://devfeed.tech/tags/network.md>), [optimization](<https://devfeed.tech/tags/optimization.md>), [q-bio-nc](<https://devfeed.tech/tags/q-bio-nc.md>), [similarity](<https://devfeed.tech/tags/similarity.md>), [strategies](<https://devfeed.tech/tags/strategies.md>), [symmetry](<https://devfeed.tech/tags/symmetry.md>)

## AI overview

The study adapts six permutation-search methods for approximate network symmetry detection with node-similarity guidance, and introduces BASIN, which learns a soft assignment matrix through bilinear embeddings. Across four synthetic graph families, brain connectomes, and three empirical networks with known automorphism groups, guidance helps when it reveals a planted orbit missed by unguided search, but its effect varies by algorithm and setting. Tabu search performs strongest overall; similarity-guided tabu search has the lowest median score among guided variants across all 44 synthetic conditions. BASIN performs better than the other continuous relaxation on rewired lateral graphs. The authors conclude that similarity guidance is not uniformly beneficial.

## Source excerpt

arXiv:2611.16555v1 Announce Type: cross 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.