research-article

Faster symmetry discovery using sparsity of symmetries

Authors:

Karem A. Sakallah,

Igor L. MarkovAuthors Info & Claims

DAC '08: Proceedings of the 45th annual Design Automation Conference

Pages 149 - 154

https://doi.org/10.1145/1391469.1391509

Published: 08 June 2008 Publication History

Abstract

Many computational tools have recently begun to benefit from the use of the symmetry inherent in the tasks they solve, and use general-purpose graph symmetry tools to uncover this symmetry. However, existing tools suffer quadratic runtime in the number of symmetries explicitly returned and are of limited use on very large, sparse, symmetric graphs. This paper introduces a new symmetry-discovery algorithm which exploits the sparsity present not only in the input but also the output, i.e., the symmetries themselves. By avoiding quadratic runtime on large graphs, it improves state-of-the-art runtimes from several days to less than a second.

References

[1]

A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.

Digital Library

[2]

F. A. Aloul, I. L. Markov, and K. A. Sakallah. Shatter: Efficient symmetry breaking for boolean satisfiability. In Design Automation Conference, pages 836--839, 2003.

Digital Library

[3]

F. A. Aloul, A. Ramani, I. L. Markov, and K. A. Sakallah. Solving difficult instances of boolean satisfiability in the presence of symmetry. Transactions on Computer Aided Design, 22(9): 1117--1137, 2003.

Digital Library

[4]

D. Chai and A. Kuehlmann. Building a better boolean matcher and symmetry detector. In Design and Test in Europe, 2006.

Digital Library

[5]

K.-H. Chang, I. L. Markov, and V. Bertacco. Postplacement rewiring by exhaustive search for functional symmetries. ACM Transactions on Design Automation of Electronic Systems, 12(3): Article 32, August 2007.

Digital Library

[6]

B. Cheswick, H. Burch, and S. Branigan. Mapping and visualizing the internet. In USENIX Annual Technical Conference, page 1, 2000.

Digital Library

[7]

P. Darga, M. Liffiton, K. Sakallah, and I. Markov. Exploiting structure in symmetry detection for CNF. In Design Automation Conference, 2004.

Digital Library

[8]

R. Govindan and H. Tangmunarunkit. Heuristics for internet map discovery. In INFOCOM (3), pages 1371--1380, 2000.

[9]

T. Junttila and P. Kaski. Engineering an efficient canonical labeling tool for large and sparse graphs. In SIAM Workshop on Algorithm Engineering and Experiments, 2007.

[10]

B. D. McKay. Practical graph isomorphism. Congressus Numerantium, 30:45--87, 1981.

[11]

C. Mears, M. Garcia de la Banda, and M. Wallace. On implementating symmetry detection. In Sixt International Workshop on Symmetry in Constraint Satisfaction Problems, 2006.

[12]

A. Miller, A. Donaldson, and M. Calder. Symmetry in temporal logic model checking. ACM Computing Surveys, 38(3): Article 8, 2006.

Digital Library

[13]

T. Miyazaki. The complexity of McKay's canonical labeling algorithm. Groups and Computation II, pages 239--256, 1995.

[14]

J.-F. Puget. Automatic detection of variable and value symmetries. volume 3709 of LNCS, pages 475--489, 2005.

[15]

U.S. Census Bureau. UA Census 2000 TIGER/Line file download page, 2000. http://www.census.gov/geo/www/tiger/tigerua/ua_tgr2k.html.

Cited By

Lim SOh EYang HKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Learning symmetric rules with SATNetProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3601233(13251-13262)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3601233
Arezoo JSalahshoor K(2022)A Novel Integrated Solution Algorithm for Explicit Model Predictive Control in Embedded ApplicationsJournal of Control10.52547/jocee.1.1.371:1(37-47)Online publication date: 1-Jul-2022
https://doi.org/10.52547/jocee.1.1.37
Bao QZhang Z(2022)Discriminating Power of Centrality Measures in Complex NetworksIEEE Transactions on Cybernetics10.1109/TCYB.2021.306983952:11(12583-12593)Online publication date: Nov-2022
https://doi.org/10.1109/TCYB.2021.3069839
Show More Cited By

Index Terms

Faster symmetry discovery using sparsity of symmetries
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Exploiting structure in symmetry detection for CNF
DAC '04: Proceedings of the 41st annual Design Automation Conference

Instances of the Boolean satisfiability problem (SAT) arise in many areas of circuit design and verification. These instances are typically constructed from some human-designed artifact, and thus are likely to possess much inherent symmetry and ...
Symmetry Definitions for Constraint Satisfaction Problems

We review the many different definitions of symmetry for constraint satisfaction problems (CSPs) that have appeared in the literature, and show that a symmetry can be defined in two fundamentally different ways: as an operation preserving the solutions ...
Vector Symmetry Reduction

Symmetry reduction is an effective state-space reduction technique for model checking, and works by restricting search to equivalence class representatives with respect to a group of symmetries for a model. A major problem with symmetry reduction ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '08: Proceedings of the 45th annual Design Automation Conference

June 2008

993 pages

ISBN:9781605581156

DOI:10.1145/1391469

General Chair:
Limor Fix
Intel Research Pittsburgh, Pittsburgh, PA

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

The EDA Consortium
IEEE/CASS/CANDE/CEDA
SIGDA: ACM Special Interest Group on Design Automation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 June 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

DAC '08

Sponsor:

SIGDA

DAC '08: The 45th Annual Design Automation Conference 2008

June 8 - 13, 2008

California, Anaheim

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

40
Total Citations
View Citations
264
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lim SOh EYang HKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Learning symmetric rules with SATNetProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3601233(13251-13262)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3601233
Arezoo JSalahshoor K(2022)A Novel Integrated Solution Algorithm for Explicit Model Predictive Control in Embedded ApplicationsJournal of Control10.52547/jocee.1.1.371:1(37-47)Online publication date: 1-Jul-2022
https://doi.org/10.52547/jocee.1.1.37
Bao QZhang Z(2022)Discriminating Power of Centrality Measures in Complex NetworksIEEE Transactions on Cybernetics10.1109/TCYB.2021.306983952:11(12583-12593)Online publication date: Nov-2022
https://doi.org/10.1109/TCYB.2021.3069839
Ignatov SBelyaev SPanteleev SMasunov A(2021)How Many Isomers Do Metallic Clusters Have? Case of Magnesium Clusters of up to 55 AtomsThe Journal of Physical Chemistry A10.1021/acs.jpca.1c02529125:30(6543-6555)Online publication date: 23-Jul-2021
https://doi.org/10.1021/acs.jpca.1c02529
Tchinda RDjamegni C(2020)On certifying the UNSAT result of dynamic symmetry-handling-based SAT solversConstraints10.1007/s10601-020-09313-2Online publication date: 30-Oct-2020
https://doi.org/10.1007/s10601-020-09313-2
Geyer-Schulz ABall F(2020)Comparing Partitions of the Petersen GraphAdvanced Studies in Behaviormetrics and Data Science10.1007/978-981-15-2700-5_5(83-101)Online publication date: 18-Apr-2020
https://doi.org/10.1007/978-981-15-2700-5_5
Mazouri FJabbour SRaddaoui BSais LAbounaima MZenkouar K(2019)Breaking Symmetries in Association RulesProcedia Computer Science10.1016/j.procs.2019.01.052148(283-290)Online publication date: 2019
https://doi.org/10.1016/j.procs.2019.01.052
Ball FGeyer-Schulz A(2018)Invariant Graph Partition Comparison MeasuresSymmetry10.3390/sym1010050410:10(504)Online publication date: 15-Oct-2018
https://doi.org/10.3390/sym10100504
Ball FGeyer-Schulz A(2018)How Symmetric Are Real-World Graphs? A Large-Scale StudySymmetry10.3390/sym1001002910:1(29)Online publication date: 16-Jan-2018
https://doi.org/10.3390/sym10010029
Zhang XWong ALea CCheng R(2018)Unambiguous Association of Crowd-Sourced Radio Maps to Floor Plans for Indoor LocalizationIEEE Transactions on Mobile Computing10.1109/TMC.2017.272241317:2(488-502)Online publication date: 1-Feb-2018
https://doi.org/10.1109/TMC.2017.2722413
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents