How to find a good individualising set in graph isomorphism The procedure called individualization breaks symmetry arbitrarily. It chooses some nodes in the graph, arbitrarily, to give their own unique names.
Suppose there exists a set $S \subset V$, such that after individualising this set and running plane WL (Weisfeiler-Lehman) algorithm each vertex gets a unique label (i.e. discretised ). There may be other subsets of $V$ of the same size as $S$, whose individualisation (after running WL procedure) does not assign an unique label to each vertex of input graph.
I am not individualising $k$ vertices simultaneously, but individualising one and then running the WL procedure.
Is there any way to minimise the individualising set size? If it is given that individualising $l$ many vertices is sufficient?
Question : After individualising one vertex of an input graph and then running the WL, I will have some equitable partitions of the vertex set of the input graph $G$. How should the second vertex for individualisation process be chosen? To me it appears I should choose a vertex who has, say, almost the same number of neighbours as non-neighbours. I have tried some other parameters like degree etc to pick the second vertex, but it doesn't seem to work. The best choice seems, to me, the vertex which belongs to the same orbit as the first vertex.
Please note that I don't want to try all possible choices of $S$ and that I am looking at this from a theoretical point of view completely.
EDIT: If the input graph is regular then the choice of the first vertex is not important. I mean to say there is always going to be an individualising set (minimum size) which contain this first vertex. And since the input graph is regular, the number of neighbours and non-neighbours set size will be the same for every choice of first vertex.
 A: It depends on the type of graph. Whatever algorithm you choose there are probably graphs that it works badly on. Similarly, given a vertex choice method, there are graphs it is bad for. Here are two examples: 
The first is one where it is unwise to pick a vertex adjacent to half the others. Let $G$ be a strongly regular graph with $n$ vertices of degree $d$ where $d \leq \frac{n}{2}.$  Then make a new bipartite graph also regular of degree $d$ but with twice as many vertices by replacing each vertex $x$ by a pair $x_1,x_2$ and each edge $(x,y)$ by the $2$ edges $(x_1,y_2)$ and $(y_1,x_2)$ Finally, add two new vertices $X_1$ and $X_2$ with $X_1$ adjacent to all the $u_2$ (and also $X_2$) and $X_2$ adjacent to all the $u_1$ (and also $X_1$.) These two new vertices are the only ones adjacent to half the vertices (the rest are adjacent to under a quarter of the vertices.) But picking an $X_i$ as a named vertex at any stage is of little to no use.
To give an example where your second idea does not do well I need to know what you mean by "in the same orbit." Are you saying that the graph (before any vertices get names) has an automorphism group with orbits and the first two points chosen come (one at a time) from the same orbit? I don't like this construction as much as the other one, but replace every vertex $x$ by a $K_m$ with vertices $x_1,x_2,\cdots,x_m.$  Then replace every edge $(x,y)$ with the $m$ edges $(x_i,y_i).$ If your first chosen vertex is, say, $u_1$ then certainly $u_2$ is in the same orbit but picking it next is not very helpful. I suppose that a distinguishing set must utilize at least $m-1$ of the labels. Now it might be that some $v_2$ is a good thing to pick next but your rule would make picking $v_1$ equally attractive, which it shouldn't be. Since I don't know for sure what your suggestion is, I'll stop there. Except to say that $m$ need not be too large. I do like the idea that there is no $m$-clique in the starting graph. Then it is obvious if an edge is of the type $(x_i,x_j)$ or of type $(x_i,y_i).$
