In short, I found an algorithm for GI and the only hard instances
I found so far are non-isomorphic strongly regular graphs with
large automorphism groups.

>Q1 What are hard instances for the alogrithm?

[The sage math code](https://j.ludost.net/isogun2.py.txt)
and the [preprint](https://j.ludost.net/graphiso1.pdf)

and the [code in a browser on sagemath.org](https://sagecell.sagemath.org/?z=eJy9WG1v2zgS_h4g_4Hn4LBWq1Msu9nuuiCuVp3EiddO0iZIUsNwGYmWGcuSQkp2fIu9335DSpTkl-7eLQ7rAIo4MxzOPBzODFWr1Q4PfE7iGWIiWkQ8njGxQEtGUBytKBcomqIVZf4soR4i3jNxaeiu0YIknLlUHB7Iv06azCLeRuicRtxn6DwNWSjmzES-n79-9BeEBZYbLYBY0PIXSZZ6bmcUxZzGnIUJ2INI0kazJIlF-_j42QpSLxKJFdLkWFkMBttW7E3lzC5JaBt9IQm6TEPUfIca79vvfmrDS2eA7m4_oWaj2ZKCd4L4tC3fVpwlCQ0RC5GkgUczSVZ89HeehlMWUIkKWNm04rVmLbD9rvHBb2BlhLA-k9CLFp-pnwaE1xfHxy1zYQCfYQ4cOb_uN0xBqYdtQyvpYL9hFXBOFJyvdeODg0GYGXtYembCFhQtlzgzTMF3Uu-YjiliEmLbjHmUwEIfgO9GaZgcHiCUcOIm5AncaRwefLq-U0pEG6WCcnRitWwkTCTWQLGthhokUUKCNvrRajURbPI9CQI1qY1O3jfQQpRIuTPqzmEx6SSYbi6XYOotTymCXylW4nVNAro-l-_1963vANX4q4BqVIHaRcb-qUCmZTVOwPECGmD-vAXNjyctBc3P6IhTN-WCLSlyga_gqsmjdnhw5AfREwmQWpPywwO9Pm5I9oxwLwMKj-oZSjX333xwesqYd_mF0Qd6dyPmc_E4_8gi5-L-88V978Hp3V3FZP7xhUWnot9jj_3ezDt1Ln_pTV7mc-fikd73Zx69up8L4d_Pny-vHPbo0X-uvTt6dfp823-ZPM6f-6JmmMWa_6L05oV9Wd1cEvbtt6uV6AWj24-MdFZX5Ok8uLh5vI6-koHjnH_jwbBzTvpe78br33ave2Q17_W_rO_dwfzW93qJN3HTW3J__dwbxJ3p9aWYfH4cfBt9u7hbP_ZrhjHO0sjhgUenaGe_hrhhdrGKjBCPxqZHFiTGwyik2R6ekUDQbFdl3JlxkAr1ZrRl8COkkJcvoK29J4nJHLdIg4ShDPlMeAixnXJOIRUtKU_oq8wUnYzXbSOP-pxSE_5PCcxF4oUn9dDI-NJUSIck4JR4azVUSrKUKSWUEyASE6BCOFSz75RHC9SBQEPOlgN57OiQQUd5FJmoH0IORqsoDbzwhwSRGKCB6APPEtCJ2vVMAZuiMEq0fdXQU1yt9y1Gdg4ZHmTnqpO75miCkxOOpnI7AEtBk2VGCnHHCnm0EvI0ZqRi-S7GDVi6i79-BbgspnAzCrbCReZ-ub_tHCf862-FQEDDuiIaGEsfOE1SHmZymdCnSQM339SHb20DHQ3fNnNHbG0jBNXQBCFDM2Lcsd-86eohxyORLurMQNOII6a23Y6tzJ-xlnILoypSsgYCa8TG2N6wuA5UQ1mckXOWjF8ZBLLg1WuVRF0zh0YpmfvIRMEHfTEcja4ZSk_M3DPtURN3Sn-ak30ONTf8ybe2iR01r7plzt75zuZ8NJx0sFxpNMwJIX1NHDitVVXFbMj3PoXd3wRD6sByOYCvnWuQkQhDbdIuZAAurpkSYiVvmLUhjIdmDR3VTB3Phq5FuQ6ZKypry2EHZ4mvYxuWHEMC8icJnHAxUSp0iOYxH0RRjOCAcWUmJHkoYB70IKL0dCk9VUZtuqno-QF0ozBhYUpLAacMU8dcVsI0Y8bYKUM1VwjJ8iWV_YsMCgP9DVcoMKOKchXDTar8aUw9Np1KDJcG2hTaNXcXTA2okwPq_AGgW5o60n41f4-Be06MFEWZsbvyu_aqNNHEHnOTPIts8yCC8bJ69MRWB2Gbjg01CdJLVpHk4-1oqetSpgUKVjerTvKRFSf5yIqTfBgbIHLZdOhzznUY5WNV4Mry-L0kIPOw3uy_Losd7UteYcW74izsOfXyBxEvLd8T7hl3J-Qz8r6ktO1fEY9zFuMcxSq9MpPvDzdZLHNU3D0ShXLZbuxnP0ELMN8NdZi09_xXIS3bdhEFacKisLaFTh7Oeg93_PoO5OVUucfgvMVCj0KNt2Xu3VqjWmCb6Ojh4UFn0gp3E9wsUsssNNjpxDIeguaKs6wBG2SMhK_RlIhkS54XpcQlhbshHpRtxh_5LXnPv4OJS0aDETOfx0XQw5qsVOmS3ABuiahsWfSR1cdTJ-8BRLOr1xjonmlg_AnL85AZjJYmG8v0KPunfATl0d0jCdewiqQalZK5yYMtk2VS-n-b_V0rf8eoMoCKa-GZKWbRSjf62QWxXVZzILRlz51MuLqLTySlLh-5mUuKA8ib9TNLN-F1I2eBLh1Zp_jMop4PzIA80UBk6xk67MpUyemyeHd177yayc8F0HID7KNxBQeCl3SkXIEz3VCtypIa_7CrSWpJLU4X0E_USeX0wZojMsYV6NxKZy6xpxL708pi1FMdU11OpaPGeGxmb_Z4rNeD1gUcnRExkU2MqPTeMtmdQUc-8RjcXxPA0JDfdPJCTj1TTcDw1OABPkqiy_bKlFsE21fWt3Np1Ma2n-tYLL8m2KbflA3cTupQIlKpb8t7QnFxcuWFyW-qb1fZHSLavj21sG9bbhSvtdN-C3BXuw17vnjyCHrNrkWj1_HmAYe52G9qM2X6qj9o03IRFWIyN6jgS4BvGNm19n__-PFnPnv8F986Dg_y0rL1fQJXeuX_AF7lj3o=&lang=sage&interacts=eJyLjgUAARUAuQ==)

Some success stories:

The Paley graph of order $73$ was solved in $9$ recursive calls
(each polynomial) and time 703 ms.

The strongly regular graph with parameters $(100, 44, 18, 20)$
was solved in $12$ calls and time 1.5 sec.

Related to [Permutation similarity of matrices with many distinct entries](https://mathoverflow.net/questions/448509/permutation-similarity-of-matrices-with-many-distinct-entries)