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

May 18, 2026

Prism: Structural Symmetry Scanning via Duality-Constrained Laplacian Projection

We introduce Prism, a framework for structural symmetry diagnosis in complex networks. Given a graph Laplacian LL and a duality operator PP (a symmetric involution), Prism computes the duality defect δ(L,P)=∥LP−PL∥F/∥L∥Fδ(L,P) = \|LP - PL\|_F / \|L\|_F -- a scalar measuring how far the network deviates from structural self-consistency. When PP encodes the network's true symmetry, δδ starts near zero and rises monotonically as structure degrades; an arbitrary PP gives noise. We prove that the optimal L′L' satisfying [L′,P]=0[L', P] = 0 is given by a closed-form block-diagonal projection, and provide an unsupervised alternating optimization that learns PP from the graph's own Fiedler vector. Experiments on synthetic networks show the true-PP defect is 3.38×3.38\times more sensitive to structural degradation than an index-reversal baseline and more sensitive than modularity. On Zachary's Karate Club with edge noise, Prism achieves 94.5%94.5\% community detection accuracy at 5%5\% noise versus 76.6%76.6\% for the raw Laplacian baseline. Applied to live S&P~500 data (2026-05-17), Prism detects rising structural stress (defect 0.43→0.730.43 \to 0.73 over 90 days) while surface correlations remain low -- a signal invisible to correlation-based methods. In a historical backtest spanning five major stress events (2011--2020), the duality defect exhibits a consistent pattern: it reaches elevated levels before the correlation spike that accompanies each crisis, and sustains high readings during periods of structural fragility that conventional metrics classify as calm. The duality defect is a first-principles structural admissibility condition, requiring no training data and computable in milliseconds.
Sep 27, 2026

Discovering Symmetries in Neural Network Parameter Spaces

Parameter space symmetries are important for understanding neural networks' loss landscape, training dynamics, and generalization. However, systematically identifying these symmetries remains a challenge. In this paper, we formalize data-dependent parameter symmetries and characterize loss invariance and the group-action axioms through infinitesimal conditions, which provide objectives for jointly learning group generators and nonlinear action maps. Our framework systematically uncovers parameter symmetries, including previously unknown ones. To study larger networks, we establish conditions under which subnetwork symmetries extend to the full model. The same construction gives an explicit family of finite-batch symmetries, providing both analytical examples and a foundation for discovery through small subnetworks. Using the infinitesimal characterization and subnetwork construction, we implement a framework for automated discovery of parameter symmetries, and successfully uncovered symmetries in various architectures, including pretrained transformer models.
Jun 1, 2026

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

Symmetric nonnegative matrix factorization (Symmetric NMF) approximates a matrix as WWTWW^T with nonnegative rectangular factor WW. It has broad applications in graph clustering and machine learning. In contrast to the NMF, projected gradient methods for the symmetric problem had been associated with slow convergence. To address this, we introduce SNMPBB, the first adaptation of nonmonotone projected Barzilai-Borwein methods to Symmetric NMF, demonstrating that gradient algorithms are significantly more effective than previously understood. We further extend SNMPBB to graph clustering using the graph Laplacian regularization (Graph-SNMPBB) and to large problems with low-rank approximations (LAI-SNMPBB). For all variants we prove global convergence to first-order stationary points and also that Barzilai-Borwein curvature information is preserved with randomized approximations. On synthetic data, SNMPBB achieves 6 times speedup over the alternative SymANLS for similar residuals, with advantages growing at higher ranks. Across six real-world clustering benchmarks, Graph-SNMPBB matches or exceeds SymANLS accuracy. Lastly, LAI-SNMPBB outperforms state-of-the-art LAI-SymPGNCG on 34 SuiteSparse matrices in both runtime and residual quality.