Clustering coefficient For a vertex v, the set of neighbours of v is n(v). The edge density among the vertices n(v) is calculated. The clustering coefficient is the mean average of this local edge density for all v [27] . It is intended to be a measure of the local cliqueness of the graph. This attribute has been used with machine learning for a model selection problem in constraint programming [11].

Normalised degree The normalised degree of a vertex is its degree divided by |V |. The minimum, maximum, mean and median normalised degree are used.

Normalised standard deviation of degree The standard deviation of vertex degree is normalised by dividing by |V |.

Width of ordering Each of our benchmark instances has an associated variable ordering. The width of a vertex v in an ordered graph is its number of *parents* (i.e. neighbours that precede v in the ordering). The width of the ordering is the maximum width over all vertices [3]. The width of the ordering normalised by the number of vertices was used.

Width of graph The width of a graph is the minimum width over all possible orderings. This can be calculated in polynomial time [3], and is related to some tractability results. The width of the graph normalised by the number of vertices was used.

Variable domains The quartiles and the mean value over the domains of all variables.

Constraint arity The quartiles and the mean of the arity of all constraints
(the number of variables constrained by it), normalised by the number of constraints.

Multiple shared variables The proportion of pairs of constraints that share more than one variable.

Normalised mean constraints per variable For each variable, we count the number of constraints on the variable. The mean average is taken, and this is normalised by dividing by the number of constraints.

Ratio of auxiliary variables to other variables Auxiliary variables are introduced by decomposition of expressions in order to be able to express them in the language of the solver. We use the ratio of auxiliary variables to other variables.

Tightness The tightness of a constraint is the proportion of disallowed tuples.

The tightness is estimated by sampling 1000 random tuples (that are valid w.r.t. variable domains) and testing if the tuple satisfies the constraint. The tightness quartiles and the mean tightness over all constraints is used.

Proportion of symmetric variables In many CSPs, the variables form equivalence classes where the number and type of constraints a variable is in are the same. For example in the CSP x1 × x2 = x3, x4 × x5 = x6, x1, x2, x4, x5 are all indistinguishable, as are x3 and x6. The first stage of the algorithm used by Nauty [20] detects this property. Given a partition of n variables generated by this algorithm, we transform this into a number between 0 and 1 by taking the proportion of all pairs of variables which are in the same part of the partition.