On deterministic weighted graph isomorphism from randomized

Is there a $O(n^2)$ algorithm to resolve isomorphism between two weighted $n$-vertex graphs? This is a much easier problem than graph isomorphism.

Basically take an real edge weight set $\{w_1,\dots,w_s\}$ where $s=\Omega(n^\alpha)$ where $\alpha\in[0,2]$ and the edge weights are picked uniformly. We can think of the second graph as being generated as follows: Input the weighted first graph to a black box and the black box returns the second graph based on some mechanism.

For every $n$ fix a set of weights.

For every input graphs you assign weights uniformly from a distribution. Then you feed in the input graph, weights and the second graph to the black box and the black box returns you the weighted second graph. Then you have to decide isomorphism on these two weighted graphs. So the probability is over all assignments of weights (the weight set is fixed for every $n$ in some worst case way). If this has an algorithm that is in $\mathsf{BPP}$ then in theory it should be conjecturally derandomizable.

• How is this not a duplicate of your earlier question?
– Raphael
Feb 29 '16 at 10:08
• @Raphael Look at D.W. comment.
– user39969
Feb 29 '16 at 10:08
• 1) You did not undo the changes on that question which D.W. was concerned about. 2) You should state right at the beginning of this question what you are after. "Time X algorithm" is usually understood as "deterministic". 3) Your title is useless; please come up with a better one.
– Raphael
Feb 29 '16 at 10:11
• @Raphael 'If this has an algorithm that is in $BPP$ then in theory it should be conjecturally derandomizable'.
– user39969
Feb 29 '16 at 10:14

Consider first the case of two colors. We can identify with each vertex $x$ its color distribution $a$, which is the number of edges of color 1. The distribution of $a$ is $\mathrm{Bin}(n,1/2)$, and so if we divide the vertices into bins according to their color distribution, the heaviest bin will contain $O(\sqrt{n})$ vertices with high probability. If we repeat the process, we the heaviest will contain $O(\log n)$ vertices with high probability. Once more, and we expect all bins to have size 1.
Of course, this sketch isn't rigorous. To know for sure, you will have to make it rigorous, and find whether it indeed works; perhaps a constant number of rounds isn't enough, but $\alpha\log n$ rounds (as in your case) are.