Introduction
Graph coloring is a fundamental combinatorial optimization problem, which, given a graph and a palette of colors, asks for an assignment of colors to the nodes of the graph such that adjacent nodes receive different colors. Given a palette of k k k colors, deciding whether such an assignment exists is NP-complete for every fixed k ≥ 3 k \ge3 k ≥ 3 [22 ] . Moreover, computing the smallest number of colors required to obtain a conflict-free assignment, known as the chromatic number, is NP-hard.
Graph coloring has applications in several practical domains, such as register allocation, where a compiler has to choose how to assign the variables of a program to the computer registers [17 ] , and timetabling problems, where conflicting activities must occupy distinct timeslots [71 , 16 ] . Sudoku puzzles can also be seen as graph coloring instances, with cells represented as nodes and digits as colors [30 ] .
Traditional exact approaches include integer programming [48 ] , as well as SAT and constraint satisfaction problem (CSP) solvers [31 ] . Moreover, classical heuristics, which are generally faster but provide no guarantee of finding a valid coloring, include constructive algorithms such as greedy coloring [71 ] and DSATUR [13 ] , as well as local-search methods [29 , 46 ] .
Intuitively, when instances are drawn from a distribution or feature recurring structure, machine-learning-based algorithms can learn to exploit these regularities and produce high-quality solutions efficiently. More generally, neural combinatorial optimization uses learned models as heuristics for constrained optimization problems like the traveling salesman [11 , 35 ] and knapsack [20 ] . When trained on instance distributions, these models amortize the cost of learning a heuristic and enable fast inference on new instances [12 ] .
Related Work. For graph coloring, neural approaches can optimize instances directly or learn across a distribution. PI-SAGE [59 ] casts coloring as unsupervised node classification, using a graph neural network (GNN) to produce soft color assignments, which are then rounded. Building on PI-SAGE, Vanderschüt & Weber (2026) improve approximate k k k -coloring using recursive warm starts obtained from ( k − 1 ) (k-1) ( k − 1 ) -colorings. ROS [54 ] similarly relaxes assignments to continuous ones, optimizes a continuous objective, and samples discrete solutions. Other methods learn general procedures across instances. ANYCSP ([63 ] ) trains a GNN with reinforcement learning for solving general CSPs by performing global stochastic updates. Similarly, CONsFORMER ([73 ] ) trains a Transformer to improve complete assignments using differentiable relaxations of the constraints, as a learned form of local search. Le et al. [39 ] learn color representations with a contrastive loss and decode them by clustering. Li et al. [43 ] also propose a color-equivariant model using restricted linear equivariant updates, but predict all node colors simultaneously, without conditioning each assignment on previous ones as in sequential decoding. Instead, Watkins et al. [70 ] propose a sequential constructive heuristic that learns node selection, while a fixed rule assigns the lowest permissible color. See Appendix § 13 for additional related work.
Graph tasks often exhibit symmetries ([24 ] ). Most commonly, if two graphs are isomorphic via a node permutation, node-level outputs should permute accordingly. In graph coloring, applying the same node permutation to a graph and to a valid coloring preserves validity. Importantly, however, an individual coloring isn’t invariant under node permutations, since nodes in the same automorphism orbit may receive different colors. A solver must therefore be able to break node symmetries. Moreover, graph coloring exhibits a symmetry over its output . Color labels are interchangeable, since permuting them transforms any coloring into an equivalent one. These observations suggest that a learned solver should exploit both forms of symmetry to learn efficiently.
Contributions We introduce SCONE (Symmetry-aware COloring via Neural Equivariance), a model that constructs colorings sequentially, one node at a time. At each step, it takes as input the current partial coloring, allowing information from previous assignments to propagate through the graph, which distinguishes any nodes that were previously symmetric. Node colors are scored by a color-equivariant GNN, so relabeling the colors permutes the predictions accordingly without changing the behavior of the model. We show theoretically that equivariance reduces the state space that the model must learn (Theorem 1), and that sequential decoding yields expressive models (Theorems 3, 4). In summary, SCONE combines sequential predictions, equivariance and classical search for expressivity and efficiency. We evaluate SCONE on real-world coloring applications, including Sudoku, register allocation, and exam timetabling. Here, it achieves state-of-the-art solution quality among neural methods, achieving the best solution quality while also having the lowest solve times.
Preliminaries
A graph is a tuple G = ( V G , E G ) G = (V_G, E_G) G = ( V G , E G ) , where V G = { 1 , … , ∣ V G ∣ } V_G = \{1, \ldots, |V_G|\} V G = { 1 , … , ∣ V G ∣ } is a set of nodes and E G ⊆ { { u , v } : u , v ∈ V G , u ≠ v } E_G \subseteq\{\{u,v\} : u,v \in V_G, u \ne v\} E G ⊆ {{ u , v } : u , v ∈ V G , u = v } is a set of undirected edges. We denote by N G ( u ) N_G(u) N G ( u ) the set of neighbors of u u u .
Graph coloring Let C = { 1 , … , k } \mathcal{C} = \{1, \ldots, k\} C = { 1 , … , k } be a palette of k k k colors, and let ε \varepsilon ε denote the absence of a color. A partial k k k -coloring of G G G is a map c : V G → C ∪ { ε } c: V_G \to\mathcal{C} \cup\{\varepsilon\} c : V G → C ∪ { ε } . We refer to G = ( G , c ) G = (G,c) G = ( G , c ) as a k k k -coloring instance. A complete coloring c ∗ : V G → C c^*: V_G \to\mathcal{C} c ∗ : V G → C is a proper coloring if c ∗ ( u ) ≠ c ∗ ( v ) ∀ { u , v } ∈ E G c^*(u) \ne c^*(v) \ \forall\{u,v\} \in E_G c ∗ ( u ) = c ∗ ( v ) ∀ { u , v } ∈ E G . It is a valid solution of ( G , c ) (G,c) ( G , c ) if it is proper and extends the coloring c c c , i.e., c ( u ) ≠ ε ⇒ c ∗ ( u ) = c ( u ) c(u) \ne\varepsilon\Rightarrow c^*(u) = c(u) c ( u ) = ε ⇒ c ∗ ( u ) = c ( u ) . A graph is k k k -colorable if it has a proper k k k -coloring, and its chromatic number χ ( G ) \chi(G) χ ( G ) is the smallest such k k k .
Groups and permutations For group Γ \Gamma Γ , let γ ⋅ x \gamma\cdot x γ ⋅ x be the action of γ ∈ Γ \gamma\in\Gamma γ ∈ Γ on x x x . Its Γ \Gamma Γ -orbit is Γ ⋅ x = { γ ⋅ x : γ ∈ Γ } \Gamma\cdot x = \{\gamma\cdot x : \gamma\in\Gamma\} Γ ⋅ x = { γ ⋅ x : γ ∈ Γ } , and X / Γ \mathcal{X}/\Gamma X /Γ denotes the set of orbits. A function f : X → Y f: \mathcal{X} \to\mathcal{Y} f : X → Y is Γ \Gamma Γ -equivariant if f ( γ ⋅ x ) = γ ⋅ f ( x ) f(\gamma\cdot x) = \gamma\cdot f(x) f ( γ ⋅ x ) = γ ⋅ f ( x ) for all γ ∈ Γ \gamma\in\Gamma γ ∈ Γ and x ∈ X x \in\mathcal{X} x ∈ X . We denote by S m S_m S m the group of permutations of { 1 , … , m } \{1,\ldots,m\} { 1 , … , m } . For τ ∈ S m \tau\in S_m τ ∈ S m , let P τ ∈ { 0 , 1 } m × m P_\tau\in\{0,1\}^{m \times m} P τ ∈ { 0 , 1 } m × m be its permutation matrix, such that ( P τ x ) i = x τ − 1 ( i ) (P_\tau x)_i = x_{\tau^{-1}(i)} ( P τ x ) i = x τ − 1 ( i ) . A node permutation π \pi π acts on graphs by relabeling their nodes as π ⋅ G = ( V G , { { π ( u ) , π ( v ) } : { u , v } ∈ E G } ) \pi\cdot G = (V_G, \{\{\pi(u),\pi(v)\} : \{u,v\} \in E_G\}) π ⋅ G = ( V G , {{ π ( u ) , π ( v )} : { u , v } ∈ E G }) , and on a coloring as ( π ⋅ c ) ( π ( u ) ) = c ( u ) , ∀ u (\pi\cdot c)(\pi(u)) = c(u), \forall u ( π ⋅ c ) ( π ( u )) = c ( u ) , ∀ u . Two colorings that are isomorphic if one is obtained from the other by such a node permutation π \pi π , written ( G , c ) ≃ ( G ′ , c ′ ) (G,c) \simeq(G',c') ( G , c ) ≃ ( G ′ , c ′ ) . If such a π \pi π satisfies π ( u ) = u ′ \pi(u) = u' π ( u ) = u ′ , then u ∈ V G u \in V_G u ∈ V G and u ′ ∈ V G ′ u' \in V_{G'} u ′ ∈ V G ′ have the same rooted isomorphism type . We denote by Aut ( G , c ) = { π : π ⋅ G = G , π ⋅ c = c } \operatorname{Aut}(G,c) = \{\pi: \pi\cdot G = G, \pi\cdot c = c\} Aut ( G , c ) = { π : π ⋅ G = G , π ⋅ c = c } the automorphism group of ( G , c ) (G,c) ( G , c ) . Its orbits on V G V_G V G are called node orbits. Intuitively, two nodes share an orbit if an isomorphism from ( G , c ) (G,c) ( G , c ) to itself maps one to the other.
Graph Coloring and Symmetries
Our goal is to design a machine learning model that colors a graph from a fixed palette while minimizing monochromatic edges, ideally producing a proper coloring. This requires exploiting the symmetries of the task for sample efficiency, while breaking them when necessary for expressivity.
Node permutation symmetries and when to break them
Consider a graph coloring instance ( G , c ) (G,c) ( G , c ) and a valid solution (i.e., a valid coloring completing c c c ) c ∗ : V G → C c^*: V_G \to C c ∗ : V G → C . Then, if another graph ( G ′ , c ′ ) (G',c') ( G ′ , c ′ ) is isomorphic to ( G , c ) (G,c) ( G , c ) via an isomorphism π \pi π , the coloring π ⋅ c ∗ \pi\cdot c^* π ⋅ c ∗ is a valid solution for ( G ′ , c ′ ) (G',c') ( G ′ , c ′ ) . We therefore want to use an architecture that is equivariant to permutations of the nodes, like a message-passing GNN [24 ] .
The most immediate strategy for graph coloring with a model is to treat color assignment as a multiclass classification task with labels in C C C . We would predict the color scores simultaneously for each node, and then select the argmax color for each node independently from each other, as if it was a node classification task. However, as noted also in [43 ] , this strategy has a fundamental limitation, as nodes in the same node orbit of ( G , c ) (G,c) ( G , c ) are assigned the same color even if neighboring.
Consider, for example, the adjacent nodes v 1 v_1 v 1 and v 2 v_2 v 2 in Figure 1 (a). Since they belong to the same orbit, any node-equivariant predictor must assign them the same vector of color scores, even if it can distinguish arbitrary rooted-graph isomorphism types. Therefore, an adversary can always break any score ties so that these nodes are assigned the same color, thus failing to yield a proper coloring.
Figure 1. (a) Nodes v 1 v_1 v 1 and v 2 v_2 v 2 are symmetric and thus indistinguishable, so a deterministic model that predicts colors simultaneously for each node must assign them the same color, even if adjacent. (b) SCONE sequentially colors one node at a time, conditioned on previous assignments. Once v 1 v_1 v 1 has been colored, v 2 v_2 v 2 can be distinguished from it, allowing the model to assign a distinct color to v 2 v_2 v 2 .
Therefore, although the predictor itself remains permutation-equivariant, the decoding procedure must be able to break symmetries. We do so by constructing the solution sequentially, coloring one node at a time and recomputing the scores after every assignment, see Figure 1 (b). When automorphic nodes are tied, selecting any one of them breaks the symmetry of the resulting state, allowing previously indistinguishable nodes to become distinguishable. In particular, given the graph and a partial coloring, the model produces color scores to every uncolored node, selects one node, and updates the coloring by assigning it the highest-scoring color. The process ends when all nodes are colored.
More formally, given a k k k -coloring instance ( G , c 0 ) (G,c_0) ( G , c 0 ) , we define the state space S ( G , c 0 ) S_{(G,c_0)} S ( G , c 0 ) as the set of instances (up to isomorphism) that can be reached by coloring some uncolored nodes of G G G , and the set of extendable states S ( G , c 0 ) + S^+_{(G,c_0)} S ( G , c 0 ) + as states that can lead to a proper coloring c ∗ c^* c ∗ of ( G , c 0 ) (G,c_0) ( G , c 0 ) , i.e.
S ( G , c 0 ) = { ( G , c ) : c 0 ( v ) ≠ ⊥ ⇒ c ( v ) = c 0 ( v ) ∀ v ∈ V G } / ∼ S_{(G,c_0)}=\{(G,c):c_0(v)\ne\bot\Rightarrow c(v)=c_0(v)\ \forall v\in V_G\}/\sim S ( G , c 0 ) = {( G , c ) : c 0 ( v ) = ⊥ ⇒ c ( v ) = c 0 ( v ) ∀ v ∈ V G } / ∼
S ( G , c 0 ) + = { ( G , c ) : ∃ valid solution c ∗ of ( G , c 0 ) s.t. c ( v ) ≠ ⊥ ⇒ c ( v ) = c ∗ ( v ) ∀ v ∈ V G } / ∼ . S^+_{(G,c_0)}=\{(G,c):\exists\text{ valid solution }c^*\text{ of }(G,c_0)\text{ s.t. }c(v)\ne\bot\Rightarrow c(v)=c^*(v)\ \forall v\in V_G\}/\sim. S ( G , c 0 ) + = {( G , c ) : ∃ valid solution c ∗ of ( G , c 0 ) s.t. c ( v ) = ⊥ ⇒ c ( v ) = c ∗ ( v ) ∀ v ∈ V G } / ∼ .
From each state ( G , c ) ∈ S ( G , c 0 ) (G,c)\in S_{(G,c_0)} ( G , c ) ∈ S ( G , c 0 ) , the policy assigns to each uncolored node a score for each color. Based on these scores the policy selects a single uncolored node u ∈ V G u\in V_G u ∈ V G and assigns a color i i i to this node (breaking ties arbitrarily), updating the state to ( G , c ′ ) (G,c') ( G , c ′ ) , with c ′ ( u ) = i c'(u)=i c ′ ( u ) = i and c ′ ( v ) = c ( v ) ∀ v ≠ u c'(v)=c(v)\ \forall v\ne u c ′ ( v ) = c ( v ) ∀ v = u .
Supposing that the color predictor can distinguish any rooted isomorphism , a single parameter setting can then express every k k k -colorable graph of bounded size. At each extendable state, the predictor can memorize, for every uncolored node, the colors leading to an extendable successor. Since every uncolored node has at least one such color, selecting any node and any such color preserves extendability, so induction produces a proper coloring. (Thm. 5). While practical models generally cannot distinguish arbitrary rooted-graph isomorphism types [49 ] , this shows that, at least in principle, sequential coloring has enough expressivity to represent valid coloring strategies.
Color symmetries
While the equivariance to permutations of the nodes is common in most graph tasks, graph coloring presents another symmetry: the color labels are arbitrary. Indeed, consistently permuting the color labels leaves the validity and the number of monochromatic edges of a coloring unchanged. Figure 2 shows two instances that are exactly the same up to a permutation of the partial colors, and illustrates that their solutions are also the same up to the same permutation. Formally, let a color permutation τ ∈ S k \tau\in S_k τ ∈ S k act as ( τ ⋅ c ) ( v ) = τ ( c ( v ) ) (\tau\cdot c)(v) = \tau(c(v)) ( τ ⋅ c ) ( v ) = τ ( c ( v )) if c ( v ) ≠ ε c(v) \ne\varepsilon c ( v ) = ε and ( τ ⋅ c ) ( v ) = ε (\tau\cdot c)(v) = \varepsilon ( τ ⋅ c ) ( v ) = ε otherwise. If c ∗ c^* c ∗ is a valid solution for ( G , c ) (G,c) ( G , c ) , then for any τ ∈ S k \tau\in S_k τ ∈ S k we have that τ ⋅ c ∗ \tau\cdot c^* τ ⋅ c ∗ is a valid solution for ( G , τ ⋅ c ) (G,\tau\cdot c) ( G , τ ⋅ c ) .
Figure 2. Graph coloring is equivariant to color permutations. The instances ( G , c ) (G,c) ( G , c ) and ( G , c ′ ) (G,c') ( G , c ′ ) differ only by exchanging blue and green, so the solutions c 1 ∗ c_1^* c 1 ∗ and c 2 ∗ c_2^* c 2 ∗ are related by the same permutation. Moreover, blue and yellow are unused in c ′ c' c ′ and thus interchangeable, so c 2 ∗ c_2^* c 2 ∗ and c 3 ∗ c_3^* c 3 ∗ are equivalent.
We therefore seek a color-equivariant model in order to exploit the symmetries of the problem. Intuitively, if the model outputs the highest score for color blue on node v 6 v_6 v 6 for the instance ( G , c ) (G,c) ( G , c ) in Figure 2 , then the model should output exactly the same score for color green on node v 6 v_6 v 6 for the instance ( G , c ′ ) (G,c') ( G , c ′ ) . Let p u ( G , c ) ∈ R k p_u(G,c) \in\mathbb{R}^k p u ( G , c ) ∈ R k denote the color scores for an uncolored node u u u . For every color permutation τ ∈ S k \tau\in S_k τ ∈ S k , we require p u ( G , τ ⋅ c ) = P τ p u ( G , c ) p_u(G,\tau\cdot c) = P_\tau p_u(G,c) p u ( G , τ ⋅ c ) = P τ p u ( G , c ) . Importantly, color equivariance couples the policy across states that differ only by a permutation of the color labels. If s ′ = τ ⋅ s s' = \tau\cdot s s ′ = τ ⋅ s , then the action scores at s ′ s' s ′ are determined by those at s s s , up to the same permutation τ \tau τ . Therefore, learning the policy on one representative determines its behavior on the entire orbit { τ ⋅ s : τ ∈ S k } \{\tau\cdot s : \tau\in S_k\} { τ ⋅ s : τ ∈ S k } , reducing the size of the effective state space. Moreover, color equivariance does not hinder the model when several colors are symmetric, as the policy will select any one of the tied colors arbitrarily.
For an instance distribution supported on a set I \mathcal{I} I closed under color permutations, define the corresponding state space as S I = ⋃ ( G , c ) ∈ I S ( G , c ) S_{\mathcal{I}} = \bigcup_{(G,c)\in\mathcal{I}} S_{(G,c)} S I = ⋃ ( G , c ) ∈ I S ( G , c ) . Then, the effective state space of a color-equivariant model is the quotient S I / S k S_{\mathcal{I}}/S_k S I / S k , while an unconstrained model may need to learn the appropriate behavior separately for all states in S I S_{\mathcal{I}} S I , including states belonging to the same equivalence class. In fact, for the purpose of solving a feasible instance exactly, it is sufficient for the policy to learn how to act on extendable states. Indeed, if every choice preserves extendability, the decoding trajectory remains in S I + S_{\mathcal{I}}^+ S I + until it reaches a proper coloring. However, non-extendable states are still relevant when considering approximate solutions or suboptimal decisions, so we consider both S I S_{\mathcal{I}} S I and S I + S_{\mathcal{I}}^+ S I + .
Our goal is thus to quantify the reduction in effective state space induced by color equivariance. We begin by bounding how many states related by color permutations form a single equivalence class.
Lemma 1. Consider a state ( G , c ) ∈ ⋃ τ ∈ S k S τ ⋅ c 0 (G,c) \in\bigcup_{\tau\in S_k} S_{\tau\cdot c_0} ( G , c ) ∈ ⋃ τ ∈ S k S τ ⋅ c 0 with exactly r r r colors appearing in c c c . Let R ( G , c ) = ∣ S k ⋅ ( G , c ) ∣ R(G,c) = |S_k \cdot(G,c)| R ( G , c ) = ∣ S k ⋅ ( G , c ) ∣ denote the size of the orbit of ( G , c ) (G,c) ( G , c ) under color permutations. Then,
k ! ( k − r ) ! min ( ∣ Aut ( G ) ∣ , r ! ) ≤ R ( G , c ) ≤ k ! ( k − r ) ! . \frac{k!}{(k-r)! \min(|\operatorname{Aut}(G)|,r!)} \le R(G,c) \le\frac{k!}{(k-r)!}. ( k − r )! min ( ∣ Aut ( G ) ∣ , r !) k ! ≤ R ( G , c ) ≤ ( k − r )! k ! .
Intuitively, there are exactly k ! / ( k − r ) ! k!/(k-r)! k ! / ( k − r )! injective ways to relabel the r r r colors currently used by c c c , and graph automorphisms can cause some of these relabelings to yield the same state up to isomorphism. For example, for standard 9 × 9 9 \times9 9 × 9 Sudoku problems, we have k = 9 k = 9 k = 9 . Any uniquely solvable instance contains at least eight distinct fixed numbers, i.e. r ∈ { 8 , 9 } r \in\{8,9\} r ∈ { 8 , 9 } . A careful application of the lemma yields R ( G , c ) ≥ 9 ! / 648 = 560 R(G,c) \ge9!/648 = 560 R ( G , c ) ≥ 9 ! /648 = 560 [47 ] . Since this is valid for any extendable state, color equivariance reduces the number of distinct states by a factor ∣ S I + ∣ / ∣ S I + / S k ∣ |S_{\mathcal{I}}^+|/|S_{\mathcal{I}}^+/S_k| ∣ S I + ∣/∣ S I + / S k ∣ of at least 560.
In general, however, no nontrivial lower bound on r r r holds uniformly over the state space. For instance, register-allocation and timetabling instances typically begin with no assigned colors, so early decoding states may use only one color. Applying the lemma uniformly over all states would therefore use the worst case r = 1 r = 1 r = 1 , yielding only an overly pessimistic orbit-size bound of order k k k . The following more nuanced analysis, which exploits the fact that states using few colors are rare, yields a much stronger lower bound on the state space reduction, which is at least exponential in k k k .
Theorem 1. Consider a finite k k k -colorability instance set I \mathcal{I} I with no starting colors. Let ∣ Aut ( G ) ∣ ≤ B |\operatorname{Aut}(G)| \le B ∣ Aut ( G ) ∣ ≤ B ∀ G ∈ I \forall G \in\mathcal{I} ∀ G ∈ I . Let S I S_{\mathcal{I}} S I be its associated state space and S I + S_{\mathcal{I}}^{+} S I + the space of extendable states. Then:
If all graphs G ∈ I G \in\mathcal{I} G ∈ I have more than k k k nodes, then ∣ S I / S k ∣ ≤ B 16 e k ∣ S I ∣ |S_{\mathcal{I}}/S_k| \le B \frac{16}{e^k} |S_{\mathcal{I}}| ∣ S I / S k ∣ ≤ B e k 16 ∣ S I ∣ .
If all graphs G ∈ I G \in\mathcal{I} G ∈ I satisfy 0 ≤ k − χ ( G ) ≤ κ 0 \le k - \chi(G) \le\kappa 0 ≤ k − χ ( G ) ≤ κ , then ∣ S I + / S k ∣ ≤ B κ ! 2 k − κ k ! ∣ S I + ∣ |S_{\mathcal{I}}^{+}/S_k| \le B \frac{\kappa! \, 2^{k-\kappa}}{k!} |S_{\mathcal{I}}^{+}| ∣ S I + / S k ∣ ≤ B k ! κ ! 2 k − κ ∣ S I + ∣ .
Thus, for graph families with bounded B B B , color equivariance yields an exponential reduction over the full state space, and an even stronger reduction over the extendable states when k k k is close to the chromatic numbers. This reduction in effective state space suggests a corresponding improvement in sample efficiency, as the model needs to infer appropriate behavior over substantially fewer states.
Scone
In this section, we describe the design and theoretical properties of SCONE, which follows the sequential framework introduced in the previous section. Starting from an initial partial coloring, SCONE constructs a complete coloring one node at a time. At each step, the color predictor produces color scores for every uncolored node. A decoding rule then selects one uncolored node and assigns a color according to that node’s scores. The resulting partial coloring becomes the next state.
The main component of SCONE is its color predictor, which we require to be equivariant to both node and color permutations. While message-passing GNNs naturally provide node equivariance, enforcing color equivariance requires that, for every parameter setting, input ( G , c ) (G,c) ( G , c ) , and τ ∈ S k \tau\in S_k τ ∈ S k , GNN ( G , τ ⋅ c ) = τ ⋅ GNN ( G , c ) \operatorname{GNN}(G,\tau\cdot c)=\tau\cdot\operatorname{GNN}(G,c) GNN ( G , τ ⋅ c ) = τ ⋅ GNN ( G , c ) . Standard GNN constructions do not enforce this property. For example, representing color as one-hot encodings followed by unconstrained linear or MLP layers assign distinct parameters to each color, so permuting colors does not necessarily permute the output scores accordingly. We therefore design a predictor that is color-equivariant by construction.
A color-equivariant message-passing architecture
Our color predictor is based on a message-passing mechanism. Each node u u u will maintain, instead of a single embedding h u ℓ ∈ R d h_u^\ell\in\mathbb{R}^d h u ℓ ∈ R d , a collection of k k k embeddings, one per color, as a matrix H u ℓ = ( h u , 1 ℓ , … , h u , k ℓ ) ∈ R k × d H_u^\ell= (h_{u,1}^\ell,\ldots,h_{u,k}^\ell) \in\mathbb{R}^{k \times d} H u ℓ = ( h u , 1 ℓ , … , h u , k ℓ ) ∈ R k × d . Each slot h u , i ℓ h_{u,i}^\ell h u , i ℓ represents the state of node u u u relative to color i i i .
We initialize the embeddings of all nodes with color i i i with a vector e o n e_{\mathrm{on}} e on in the i i i -th slot and e o f f e_{\mathrm{off}} e off in all other slots, while uncolored nodes receive e u n k e_{\mathrm{unk}} e unk in every slot. Formally, if c ( u ) = ε c(u)=\varepsilon c ( u ) = ε , then H u 0 = ( e u n k , … , e u n k ) H_u^0=(e_{\mathrm{unk}},\ldots,e_{\mathrm{unk}}) H u 0 = ( e unk , … , e unk ) , whereas if c ( u ) ≠ ε c(u)\ne\varepsilon c ( u ) = ε , then H u , c ( u ) 0 = e o n H_{u,c(u)}^0=e_{\mathrm{on}} H u , c ( u ) 0 = e on and H u , i 0 = e o f f H_{u,i}^0=e_{\mathrm{off}} H u , i 0 = e off for all i ≠ c ( u ) i\ne c(u) i = c ( u ) . The vectors e o n e_{\mathrm{on}} e on , e o f f e_{\mathrm{off}} e off , and e u n k e_{\mathrm{unk}} e unk are learned parameters. This initialization is color-equivariant by construction, as for every τ ∈ S k \tau\in S_k τ ∈ S k , H u 0 ( G , τ ⋅ c ) = P τ H u 0 ( G , c ) H_u^0(G,\tau\cdot c)=P_\tau H_u^0(G,c) H u 0 ( G , τ ⋅ c ) = P τ H u 0 ( G , c ) .
As in standard message-passing GNNs, we aggregate the embeddings of neighboring nodes, i.e.,
H ^ u ℓ : = f a g g ( { H v ℓ − 1 : v ∈ N ( u ) } ) = ⨁ v ∈ N ( u ) H v ℓ − 1 ∈ R k × d . \widehat{H}_u^\ell:= f_{\mathrm{agg}}\left(\{H_v^{\ell-1}: v \in\mathcal{N}(u)\}\right) = \bigoplus_{v\in\mathcal{N}(u)} H_v^{\ell-1} \in\mathbb{R}^{k\times d}. H u ℓ := f agg ( { H v ℓ − 1 : v ∈ N ( u )} ) = v ∈ N ( u ) ⨁ H v ℓ − 1 ∈ R k × d .
Moreover, common element-wise aggregators ⊕ \oplus ⊕ such as sum, mean, and max commute with permutations of the color slots, and are therefore S k S_k S k -equivariant.
In a traditional GNN one would then process the aggregated messages to produce the new embeddings via the update function f u p d f_{\mathrm{upd}} f upd , which is typically an MLP. However, this is in general not S k S_k S k -equivariant, and therefore we process them with DeepSet-like layers {(citep}(Zaheer et al., 2017)}. In particular we can build an S k S_k S k -equivariant linear map L : R k × d 1 → R k × d 2 L:\mathbb{R}^{k\times d_1}\to\mathbb{R}^{k\times d_2} L : R k × d 1 → R k × d 2 with the form
L ( H ) [ i ] = W s e l f H [ i ] + W a l l ∑ j = 1 k H [ j ] + b with W s e l f , W a l l ∈ R d 2 × d 1 , b ∈ R d 2 . L(H)[i] = W_{\mathrm{self}} H[i] + W_{\mathrm{all}} \sum_{j=1}^{k} H[j] + b \quad\text{with} \quad W_{\mathrm{self}},W_{\mathrm{all}}\in\mathbb{R}^{d_2\times d_1},\ b\in\mathbb{R}^{d_2}. L ( H ) [ i ] = W self H [ i ] + W all j = 1 ∑ k H [ j ] + b with W self , W all ∈ R d 2 × d 1 , b ∈ R d 2 .
Since the same parameters are used for every slot and the sum over all slots is permutation-invariant, L L L is S k S_k S k -equivariant. Then, we set MLP S k ( H ) = L 2 ( σ ( L 1 ( H ) ) ) \operatorname{MLP}_{S_k}(H)=L_2(\sigma(L_1(H))) MLP S k ( H ) = L 2 ( σ ( L 1 ( H ))) , with σ \sigma σ a point-wise nonlinearity like ReLU or SiLU. Then, our update function is H u ℓ : = f u p d ( H u ℓ − 1 , H ^ u ℓ ) = MLP S k ( H u ℓ − 1 ∥ H ^ u ℓ ) H_u^\ell:= f_{\mathrm{upd}}(H_u^{\ell-1},\widehat{H}_u^\ell)=\operatorname{MLP}_{S_k}(H_u^{\ell-1}\mathbin\Vert\widehat{H}_u^\ell) H u ℓ := f upd ( H u ℓ − 1 , H u ℓ ) = MLP S k ( H u ℓ − 1 ∥ H u ℓ ) , where ∥ \mathbin\Vert ∥ denotes concatenation on the d d d -axis. This is guaranteed to be S k S_k S k -equivariant.
Moreover, we apply LayerNorm independently to each color slot, with shared parameters, and add a residual connection, as they have been shown to improve training stability [45 ] , as
H u ℓ = LayerNorm d ( MLP S k ( H u ℓ − 1 ∥ ⨁ v ∈ N ( u ) H v ℓ − 1 ) ) + H u ℓ − 1 . H_u^\ell= \operatorname{LayerNorm}_d\left(\operatorname{MLP}_{S_k}\left(H_u^{\ell-1} \mathbin\Vert\bigoplus_{v\in N(u)} H_v^{\ell-1}\right)\right) + H_u^{\ell-1}. H u ℓ = LayerNorm d MLP S k H u ℓ − 1 ∥ v ∈ N ( u ) ⨁ H v ℓ − 1 + H u ℓ − 1 .
Finally, after L \mathcal{L} L message-passing layers, for each node u u u we produce the color scores from the final layer embeddings H u L H_u^L H u L via a S k S_k S k -equivariant readout MLP S k : R k × d → R k × 1 \operatorname{MLP}_{S_k}: \mathbb{R}^{k\times d} \to\mathbb{R}^{k\times1} MLP S k : R k × d → R k × 1 .
All operations are color-equivariant, and they compose with the permutation equivariance acting on nodes typical of message-passing architectures. Therefore, we obtain the following result.
Theorem 2. The color predictor of SCONE is equivariant to the joint action of S ∣ V G ∣ × S k S_{\lvert V_G\rvert} \times S_k S ∣ V G ∣ × S k . Let ( G , c ) (G,c) ( G , c ) be any graph k k k -coloring instance, and let p u ( G , c ) ∈ R k p_u(G,c) \in\mathbb{R}^k p u ( G , c ) ∈ R k be the output of the predictor for node u u u . Then, for every parameter setting, every π ∈ S ∣ V G ∣ \pi\in S_{\lvert V_G\rvert} π ∈ S ∣ V G ∣ , every τ ∈ S k \tau\in S_k τ ∈ S k , and every u ∈ V G u \in V_G u ∈ V G ,
p π ( u ) ( π ⋅ G , τ ⋅ ( π ⋅ c ) ) = P τ p u ( G , c ) . p_{\pi(u)}\left(\pi\cdot G,\tau\cdot(\pi\cdot c)\right)=P_\tau p_u(G,c). p π ( u ) ( π ⋅ G , τ ⋅ ( π ⋅ c ) ) = P τ p u ( G , c ) .
Moreover, the parameterization of our color-equivariant message-passing architecture is independent of k k k . Since all transformations are shared across color slots, the same parameters apply to any value of k k k . This permits zero-shot evaluation on instances with palette sizes unseen during training.
Symmetry-aware training
We train SCONE in a supervised fashion, as a node prediction task, from target proper colorings. Given a partial coloring ( G , c ) (G,c) ( G , c ) and a target completion c ∗ c^* c ∗ , a natural approach would be to train each uncolored node u u u against the one-hot label corresponding to c ∗ ( u ) c^*(u) c ∗ ( u ) . However, such labels can conflict with color symmetries that are still present in the current state.
Let U ( c ) = { i ∈ C : ∃ u ∈ V G , c ( u ) = i } U(c)=\{i\in C:\exists u\in V_G,\ c(u)=i\} U ( c ) = { i ∈ C : ∃ u ∈ V G , c ( u ) = i } and F ( c ) = C ∖ U ( c ) F(c)=C\setminus U(c) F ( c ) = C ∖ U ( c ) denote the used and free colors, and let Stab ( c ) = { τ ∈ S k : τ ⋅ c = c } \operatorname{Stab}(c)=\{\tau\in S_k:\tau\cdot c=c\} Stab ( c ) = { τ ∈ S k : τ ⋅ c = c } be the stabilizer of c c c , i.e., all the color relabelings that leave the current partial coloring c c c unchanged. These permutations fix every used color and freely permute the remaining ones. Color equivariance therefore implies p u ( G , c ) = P τ p u ( G , c ) ∀ τ ∈ Stab ( c ) p_u(G,c)=P_\tau p_u(G,c)\ \forall\tau\in\operatorname{Stab}(c) p u ( G , c ) = P τ p u ( G , c ) ∀ τ ∈ Stab ( c ) , so all free colors receive the same score. Hence, if c ∗ ( u ) ∈ F ( c ) c^*(u)\in F(c) c ∗ ( u ) ∈ F ( c ) and ∣ F ( c ) ∣ > 1 \lvert F(c)\rvert>1 ∣ F ( c )∣ > 1 , a one-hot target for c ∗ ( u ) c^*(u) c ∗ ( u ) cannot be matched and produces an irreducible loss.
This ambiguity is intrinsic to the problem rather than a limitation of the architecture. Indeed, for every τ ∈ Stab ( c ) \tau\in\operatorname{Stab}(c) τ ∈ Stab ( c ) , the coloring τ ⋅ c ∗ \tau\cdot c^* τ ⋅ c ∗ is an equally valid completion of ( G , c ) (G,c) ( G , c ) . Figure 2 illustrates an example of this phenomenon. There, since only red and green have appeared in c ∗ c^* c ∗ , blue and yellow remain interchangeable, so completions obtained by swapping these two colors are equivalent.
While full symmetry-consistent supervision would also require averaging targets over automorphic nodes, doing so requires computing node orbits at each state, which can be expensive. In practice, we therefore replace the one-hot target by its average over all color-equivariant completions, i.e.,
y u ( i ) : = 1 ∣ Stab ( c ) ∣ ∑ τ ∈ Stab ( c ) 1 [ i = τ ( c ∗ ( u ) ) ] = { 1 , if c ∗ ( u ) ∈ U ( c ) and i = c ∗ ( u ) , 1 / ∣ F ( c ) ∣ , if c ∗ ( u ) ∈ F ( c ) and i ∈ F ( c ) , 0 , otherwise. y_u(i) := \frac{1}{\lvert\operatorname{Stab}(c)\rvert}\sum_{\tau\in\operatorname{Stab}(c)} \mathbb{1}[i=\tau(c^*(u))] =
\begin{cases}
1, & \text{if } c^*(u)\in U(c)\text{ and }i=c^*(u),\\
1/\lvert F(c)\rvert, & \text{if }c^*(u)\in F(c)\text{ and }i\in F(c),\\
0, & \text{otherwise.}
\end{cases} y u ( i ) := ∣ Stab ( c )∣ 1 τ ∈ Stab ( c ) ∑ 1 [ i = τ ( c ∗ ( u ))] = ⎩ ⎨ ⎧ 1 , 1/ ∣ F ( c )∣ , 0 , if c ∗ ( u ) ∈ U ( c ) and i = c ∗ ( u ) , if c ∗ ( u ) ∈ F ( c ) and i ∈ F ( c ) , otherwise.
We train the predictor by minimizing the cross-entropy of the softmax of color scores with these symmetry-aware labels y y y . The loss supervises every uncolored node rather than only a node selected by an expert ordering. The predictor is thus trained to provide a useful color distribution for whichever node the decoder selects next, without requiring a separate node-selection objective.
Ground truth construction For graphs drawn from a given distribution, we can obtain proper colorings using an exact solver, for example via integer linear programs (ILP). While computationally expensive, this is a one-time cost which is amortized by the much cheaper model at inference time.
Moreover, there is an asymmetry in the difficulty of solving given k k k -coloring instances and generating instances with valid solutions. Indeed, we can first draw a certain number of nodes, each with a color from C C C , and then draw edges according to a distribution of interest, only between nodes of different colors. Masking some or all of the assigned colors yields a k k k -coloring instance together with a proper coloring by construction, avoiding the need to solve the generated instance.
Given an instance ( G , c ) (G,c) ( G , c ) and a target completion c ⋆ c^{\star} c ⋆ , we generate multiple training states by partially revealing c ⋆ c^{\star} c ⋆ . Specifically, for a subset R R R of the uncolored nodes, we reveal c ⋆ ( u ) c^{\star}(u) c ⋆ ( u ) for every u ∈ R u \in R u ∈ R , obtaining a partial coloring c ′ c' c ′ . All such instances ( G , c ′ ) (G,c') ( G , c ′ ) belong to the state space S ( G , c ) S_{(G,c)} S ( G , c ) , with small sets R R R representing states near the beginning of the decoding process, and larger sets representing later stages. For a graph with m m m uncolored nodes, this construction yields up to 2 m 2^m 2 m training states.
Inference strategies
We train our model to predict a correct color for every uncolored node at any stage of the decoding process. Therefore, we could simply color the nodes in their input order. However, we find (see Appendix § 16 ) that in practice it is more effective to select nodes using the common most-constrained-first principle [27 ] from constraint satisfaction. In particular, we select an uncolored node with the largest number of distinct colors already assigned to its neighbors. In case of ties, we select the node with the highest maximum softmax probability, as a proxy for confidence. Then, we assign to this node the color with the maximum score, breaking any ties arbitrarily.
Moreover, we can improve over greedy decoding using beam search [51 ] . We maintain a beam of B B B partial colorings and, at each step, expand each of them with multiple color assignments, retaining the B B B states with highest cumulative score. This allows the model to maintain multiple decoding trajectories and recover from wrong choices made at earlier steps. We further increase diversity by ensembling independent decodings from E E E starting nodes, yielding up to B × E B \times E B × E candidate colorings. If an instance is not solved, we can repeat the decoding at increasing width, e.g., by doubling B B B or E E E . We return the coloring with the fewest monochromatic edges across all attempts.
Finally, we can avoid some model evaluations by directly propagating forced assignments . If an uncolored node has only one color that would not create a monochromatic edge, we assign it without running the color predictor. We repeatedly apply this propagation rule until no forced assignment remains, and then resume model-based decoding. When no conflict-free color is available for the selected node, SCONE assigns a conflicting color, so it always produces a complete coloring.
Scone is expressive
In § 3.1 , we argued that sequential coloring is expressive in principle. However, the message-passing-based predictor of SCONE is limited by 1-WL at each step [49 ] , so it is interesting to characterize on which graph families the model can implement a policy solving them.
The 1-WL algorithm iteratively updates each node’s label from its current label and those of its neighbors. A graph is amenable if its 1-WL multiset distinguishes it from every non-isomorphic graph [6 ] . We call a graph family cover-amenable if no two non-isomorphic connected components occurring in the family have isomorphic universal covers, and each is amenable.
On cover-amenable families of graphs, stable rooted 1-WL types determine rooted isomorphism types throughout decoding. This yields the following result. The condition holds, e.g., for families of trees or discrete graphs, which include almost all dense Erdos–Renyi graphs [8 ] .
Theorem 3. Let n , k ∈ N n,k \in\mathbb{N} n , k ∈ N , and let G \mathcal{G} G be a cover-amenable family of graphs with at most n n n nodes. There exists a parameter setting of SCONE s.t. every k k k -colorable ( G , c 0 ) (G,c_0) ( G , c 0 ) with G ∈ G G \in\mathcal{G} G ∈ G can be solved.
Note that the result, as common in expressivity results, is in the non-uniform regime, i.e. the model works for graphs of size up to n n n , but might not generalize to larger graphs. However, for some classes of graphs, we can actually show that SCONE can simulate classical algorithms for graph coloring, and therefore obtain uniform results. In particular, we can show that SCONE returns a proper coloring for all graphs in some graph families, even for ones of unbounded size.
Theorem 4. Let k , Δ ∈ N k,\Delta\in\mathbb{N} k , Δ ∈ N . There exists a parameter setting of SCONE s.t. every k k k -colorable cycle, chordal or bipartite graph with degree at most Δ \Delta Δ can be properly colored from the empty coloring.
Experimental Results
In this section, we experimentally evaluate the solution quality and efficiency of SCONE. We evaluate our method and baselines on both real-world graph coloring instances and on controlled synthetic data. Our code and the curated graph-coloring benchmark datasets will be provided publicly.
Datasets We place particular emphasis on graph-coloring instances arising from practical applications. We consider Sudoku instances, register-allocation graphs, and timetabling graphs, which exhibit substantially different graph structures, numbers of colors, and partial-coloring patterns. In addition, we use structured synthetic graph families to study controlled settings in which particular symmetries or expressivity limitations become relevant. See Appendix § 15 .§ 1 for additional details.
Metrics We evaluate each method using the percentage of instances solved (Solved%), the percentage of monochromatic edges in the returned colorings (Mono%), and the average inference time per graph. The solve percentage shows how often a method returns a proper coloring, while the percentage of monochromatic edges measures the solution quality when a proper coloring is not found. Unless specified, we report averages and standard deviations over five independent repeats.
Methods We compare SCONE against both classical methods and neural solvers. As classical baselines, we consider the greedy, DSATUR and RLF (Leighton, [41 ] ) heuristics, an ILP formulation with timelimit, and ACE, a frontier CSP solver. We also compare against the learning-based RoS (Qiu et al., [54 ] ), PI-SAGE (Schuetz et al., [59 ] ), ANYCSP (Tönshoff et al., [63 ] ), Cons-Former (Xu et al., [73 ] ), and RelCoL (Watkins et al., [70 ] ). For SCONE, we fix the number of layers to L = 10 \mathcal{L} = 10 L = 10 and the embedding dimension to d = 128 d = 128 d = 128 , which provides a good trade-off between solution quality and inference time. As aggregation ⨁ \bigoplus ⨁ , we use a N ( u ) \sqrt{\mathcal{N}(u)} N ( u ) -normalized sum, which retains degree information while controlling the scale of the aggregated messages. We train the model using the AdamW optimizer (lr = 10 − 3 \operatorname{lr} = 10^{-3} lr = 1 0 − 3 ). Checkpoints and the choice between beams and ensembling are selected on validation Solved%. See also Appendix § 15 .§ 3 for additional details.
Sudokus
Sudoku can be naturally formulated as a graph-coloring problem, with one node for each cell, edges connecting cells in the same row, column, or block, and digits represented as colors. Our main dataset is sudoku.17, which contains all known non-equivalent Sudoku puzzles with 17 clues, split into 70%/15%/15%. We also evaluate our model (without retraining it) on three datasets of increasing difficulty, satnet, rrn, and top1465. Since ANYCSP does not natively support fixed colors, we extended it accordingly and retrained it. PI-SAGE and RoS do not support fixed colors. Table 1 shows that SCONE performs strongly both in distribution and under increasingly difficult distribution shifts. ANYCSP is the strongest competing learning method, but its solution quality deteriorates on the harder instances and its iterative search is roughly two orders of magnitude slower. Classical heuristics struggle, while ILP and ACE have near-perfect quality, but are usually slower.
Table 1. Solution quality on Sudoku-graph coloring: Solved% (↑ \uparrow ↑ ), Mono% (↓ \downarrow ↓ ) and inference times.
Motivated by these results, we evaluate SCONE on sudoku.extreme (Wang et al., [68 ] ), the most challenging public Sudoku benchmark. Table 2 compares it with the state-of-the-art reasoning models LDT (Davis et al., [19 ] ) and TRM (Jolicoeur-Martineau, [33 ] ), using ANYCSP as a reference point. We use the splits introduced by LDT, so we train all the models on 1000 training instances, and evaluate on 4000 test instances. While the baselines leave some
Table 2. Solution quality and inference times on sudoku.extreme.
puzzles unsolved, SCONE consistently solves every test instance, with only a few requiring as many as 256 beams. Moreover, despite being a general graph-coloring model, SCONE is at least five times faster than LDT. Figure 3 shows that most instances are solved at small beam widths, as widths up to 32 solve 98.5% of instances, while only a small fraction require wider search. Adaptive widening therefore solves these harder instances with only a modest increase in total runtime.
Figure 3. Cumulative solutions and runtime with adaptive width
Register allocation graphs
Register allocation can be formulated as graph coloring. Indeed, nodes represent program variables, edges connect two variables that are used simultaneously and thus cannot occupy the same register, and colors represent registers. A proper coloring gives a conflict-free register allocation.
We evaluate on a filtered dataset of 8999 register-interference graphs collected by George & Appel [23 ] , split 70%/15%/15%. See Appendix § 15 .§ 1 for additional details. Rather than using the original budget of 21 registers, we set the palette size for each graph to its chromatic number, thereby testing whether each method can recover an optimal coloring. As shown in Table 3 , ACE, ANYCSP and SCONE solve every test instance, while the other learning-based methods produce lower-quality solutions. DSATUR and greedy also perform strongly, indicating that the structure of these graphs is well suited to constraint-aware node ordering. Among the learning-based methods, SCONE also has the lowest inference time, at approximately 4 ms per graph.
Table 3. Solution quality on registers: Solved% (↑ \uparrow ↑ ), Mono% (↓ \downarrow ↓ ) and inference times.
Generalization from synthetic training
Many important coloring benchmarks contain only a few isolated instances and therefore provide no natural training distribution. To evaluate transfer in this setting, we train a single model exclusively on synthetic data, as described in Sec. 4.2, and apply it without finetuning to multiple instance families. The Toronto timetabling graphs [16 ] represent exams as nodes, conflicts due to common students as edges, and timeslots as colors. We aggregate 4 smaller instances and 5 larger instances. We also consider queen graphs [65 ] , for p ∈ { 8 , 9 , 10 } p \in\{8, 9, 10\} p ∈ { 8 , 9 , 10 } , where nodes represent squares of a p × p p \times p p × p chessboard and edges connect squares sharing a row, column or diagonal.
Table 4 , using 20 repeats, shows that the synthetically trained model transfers reliably across these families, with SCONE being the only learned method to solve every instance. On the smaller Toronto instances, SCONE matches the 100% solve rate of ANYCSP while being slightly faster. The gap widens on the larger instances, where SCONE solves every graph, while ANYCSP fails on some and takes five times longer. On queen graphs, SCONE and ANYCSP both solve all instances, with the former being more consistent and faster. Overall, ACE also achieves near-perfect solution quality.
Table 4. Solution quality on isolated instances: Solved% (↑ \uparrow ↑ ), Mono% (↓ \downarrow ↓ ) and inference time (↓ \downarrow ↓ ).
We test the same model on structured synthetic families that expose potential failure modes, reporting cycle graphs here and full results in Table 9 . With greedy decoding alone, SCONE solves every graph with fast inference times. ANYCSP also succeeds but is slower, while other models struggle.
Table 9. Solution quality on additional structured graphs: Solved% (↑ \uparrow ↑ ), Mono% (↓ \downarrow ↓ ) and inference time per graph (↓ \downarrow ↓ ).
We additionally evaluate on book graphs connecting characters, Erdos-Renyi DSJC graphs, and random le450 graphs from the DIMACS collection. These experiments are deferred to Appendix F, and they confirm the strong solution quality observed in Table 4 . In particular, SCONE solves all book graphs and le450-15 instances, including cases rarely solved by baselines.
Ablation study
First, we study the contributions of learned color selection and forced assignments by ablating each at decoding widths W ∈ { 1 , 4 , 16 } W \in\{1,4,16\} W ∈ { 1 , 4 , 16 } . In particular, we compare SCONE to a variant with no forced assignments and, most importantly, to a variant that replaces the learned color scorer with a simple heuristic rule that assigns to the selected node the color with minimum number of conflicts. As shown in Figure 4 , removing the learned scorer lowers solved rates across all benchmarks, with particularly large drops on Sudoku and Toronto that persist not only on greedy decoding, but also when increasing the decoding width. Even on registers, removing the learned scorer reduces the greedy decoding solve rate below the one of DSATUR. Removing forced assignments has no effect on solution quality for greedy decoding or ensembling, and slightly helps to prune beams at W > 1 W > 1 W > 1 .
Figure 4. Solved rates at decoding widths W ∈ { 1 , 4 , 16 } W \in\{1,4,16\} W ∈ { 1 , 4 , 16 } for SCONE, for a version without forced assignments, and for a version with the neural scorer replaced by a minimum-conflict heuristic.
Moreover, we study the effect of equivariance by comparing SCONE and a variant without color equivariance, with and without data augmentation by color permutations. First, we train on increasing subsets of sudoku_17, see Figure 5 (a). With only N = 100 N = 100 N = 100 training instances, SCONE solves 49% of the test set, compared with just 2% for the non-equivariant model. Data augmentation narrows the gap in the low-data regime, but even at the largest subset it remains substantial, highlighting the greater sample efficiency of architectural equivariance. Second, we generate datasets targeting increasing chromatic numbers χ \chi χ , setting the palette size k = χ k = \chi k = χ . While the non-equivariant variants are competitive for small palette sizes k k k , their performance degrades as k k k increases, see Figure 5 (b). Data augmentation provides no improvement, and the gap to SCONE widens with k k k , indicating that color equivariance becomes increasingly important as k k k grows, as suggested by Theorem 1.
Figure 5. Ablation on Sudoku and synthetic graphs.
Conclusions
We introduced SCONE, a graph-coloring method combining color equivariance with sequential decoding, as supported by our theory. Across real-world and synthetic benchmarks, it achieves near-perfect solution quality with low inference times. As future work, these positive results motivate extending SCONE to handle richer constraints and objectives beyond standard graph coloring, such as room capacities in timetabling and move preferences in register allocation, making it applicable to a broader range of practical coloring-based applications in operations research. Moreover, it is interesting to study which symmetries can be exploited in other combinatorial problems.
Acknowledgements
The project is sponsored by the Defense Advanced Research Projects Agency under cooperative agreement HR0011262E027. The content of the information does not necessarily reflect the position or the policy of the Government, no official endorsement should be inferred. PP and MW further acknowledge support from the Aramont Fellowship Fund for Emerging Science Research. MW was partially funded by NSF award DMS-2406905, an Alfred P. Sloan Research Fellowship in Mathematics, and the AI2050 program at Schmidt Sciences (Grant G-25-69786).
AI Use Statement
In this work, we used generative AI tools to: assist in the writing of proofs, provide feedback on research methodology or experiments, propose or refine hypotheses, implement methods.
We have not used generative AI tools to: generate synthetic data sets, help develop theoretical models or conceptual frameworks, formulate mathematical claims, provide critical ingredients for proving mathematical claims, design the research methodology or experiments, assist with translation, clean and reformat dataset, support qualitative and thematic data analysis, interpret results, create or modify scientific figures or images, draft parts of a research paper.
Additionally, we used generative AI tools to: create or edit software code, edit the paper to improve readability, identify relevant literature, propose a title or keywords for a research paper.
We have reviewed all AI-assisted work. We have implemented the core parts of the model ourselves, and verified all the code for correctness. We take responsibility for the final content of this work, including text, claims or artifacts produced with the aid of generative AI.
Ethics Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are potential and indirect societal consequences of our work, none of which we feel must be specifically highlighted here.
Reproducibility Statement
For all our theoretical results, clear explanations of any assumptions and a complete proof of the claims are included in Appendix C. Descriptions and references for datasets and baselines are reported in Sections D.1 and D.2 respectively. A description of our model’s implementation and of the hyperparameters we used is reported in Section D.3. Section D.4 describes our computing infrastructure to ensure reproducible inference times. The code, checkpoints and datasets to reproduce our results will be made publicly available on GitHub.
Appendix
Limitations and Future Work
While SCONE achieves state-of-the-art performance, there are some limitations, which suggest promising directions for future work. For example, SCONE constructs a coloring sequentially and therefore requires up to O ( n ) O(n) O ( n ) forward passes for a graph with n n n nodes, which limits the applicability to larger graphs. A promising direction is to color multiple compatible nodes speculatively, retaining their assignments when they are consistent and revising them otherwise. Moreover, SCONE is an approximate solver. It always returns a complete coloring but cannot guarantee that it is proper or certify that no proper coloring exists for the given palette. Combining the model with backtracking or an exact solver could provide such guarantees while retaining its ability to identify promising assignments.
Additional related work
Classical graph coloring. The k k k -colorability problem is NP-complete for every fixed k ≥ 3 k \ge3 k ≥ 3 [22 ] , while it can be solved in linear time for k = 2 k = 2 k = 2 . Exact algorithms can however be faster than enumerating all k n k^n k n assignments. For example, 3-colorability can be decided in O ( 1.33 n ) O(1.33^n) O ( 1.3 3 n ) time using reductions to constraint satisfaction [10 ] . Moreover, several graph classes admit polynomial-time algorithms. Chordal graphs can be optimally colored in linear time [61 ] . Graphs of bounded treewidth can also be colored efficiently by dynamic programming over a tree decomposition [4 ] . Brooks’ theorem shows that every connected graph of maximum degree Δ \Delta Δ can be colored with Δ \Delta Δ colors unless it is a complete graph or an odd cycle [14 ] . The four-color theorem guarantees that every planar graph admits a coloring with at most four colors [3 ] , and the later proof of Robertson et al. [56 ] also yields a quadratic-time coloring algorithm.
Neural combinatorial optimization on graphs. Other works have addressed the graph coloring problem with machine learning. Huang et al. [32 ] target very large graphs, and combine Monte Carlo tree search with a model that predicts a distribution over valid colors for the current node. Lemos et al. [42 ] train a GNN to predict whether a graph is k k k -colorable, representing both nodes and candidate colors within the message-passing graph, and colorings are recovered indirectly by clustering the learned node embeddings. Finally, Li et al., [43 ] also identify node symmetry as a limitation of simultaneous GNN-based coloring and address it through randomly initialized node features. Their model is also color-equivariant, but uses a substantially more restricted class of linear equivariant updates. In contrast, SCONE employs expressive nonlinear equivariant layers and breaks node symmetries sequentially, as previous color assignments become part of the state.
Neural combinatorial optimization has mostly focused on routing problems [66 , 11 , 20 ] , but it has also been applied to several graph problems closely related to coloring, such as Max-Cut [34 ] . Khalil et al. [35 ] learn sequential construction policies for Max-Cut and minimum vertex cover using reinforcement learning, and Barrett et al. [9 ] learn a local-search policy that may revise previous decisions at inference time. Sequential policies have been used also for TSP [35 , 20 ] , graph edit distance [52 ] and for knapsack [1 ] . See also Cappart et al. [15 ] for an overview of the field.
Symmetry in combinatorial reasoning. Symmetry has long been exploited in constraint programming and SAT to reduce redundant search. For example, Lex-leader constraints select one representative from each orbit [18 ] , while specialized methods handle interchangeable values [53 , 67 ] . Symmetry-aware architectures have also been used for neural combinatorial optimization, notably in NEUROSAT [60 ] , which respects the natural permutations of SAT formulas by encoding them as graphs and using a message-passing mechanism. Methods for more general constraint-satisfaction problems based on message-passing paradigms like RUN-CSP [62 ] and ANYCSP [63 ] also inherit equivariance to the natural permutations of the constraint graphs. Finally, Kim et al. [36 ] introduce a regularization-based training scheme that exploits problem and solution symmetries in neural routing problems, including TSP and CVRP.
Proofs
Section 3
Theorem 5 (Expressivity of sequential coloring). Fix n n n , k ∈ N k \in\mathbb{N} k ∈ N , and let s θ ( G , c , u ) ∈ R k s_\theta(G,c,u) \in\mathbb{R}^k s θ ( G , c , u ) ∈ R k denote the color scores assigned to an uncolored node u u u . Assume that the predictor is universal over rooted isomorphism types of size at most n n n . Consider any sequential decoder that repeatedly selects an arbitrary uncolored node u u u , chooses i ∈ arg max j ∈ C [ s θ ( G , c , u ) ] j i \in\arg\max_{j \in C}[s_\theta(G,c,u)]_j i ∈ arg max j ∈ C [ s θ ( G , c , u ) ] j , and assigns color i i i to u u u , breaking ties arbitrarily. Then there exists a single parameter setting such that, for every extendable partial k k k -coloring ( G , c 0 ) (G,c_0) ( G , c 0 ) with ∣ V G ∣ ≤ n |V_G| \leq n ∣ V G ∣ ≤ n , every decoding trajectory yields a proper coloring extending c 0 c_0 c 0 .
Proof. For an uncolored node u u u , let c u ← i c^{u \leftarrow i} c u ← i denote the partial coloring obtained by assigning color i i i to u u u . Define the target score function as s ( G , c , u ) i = 1 s(G,c,u)_i = 1 s ( G , c , u ) i = 1 if ( G , c u ← i ) (G,c^{u \leftarrow i}) ( G , c u ← i ) is extendable and 0 otherwise. This function depends only on the rooted partial-coloring isomorphism type of ( G , c , u ) (G,c,u) ( G , c , u ) . In fact, it is also color-equivariant. There are finitely many rooted partial-coloring isomorphism types with at most n n n nodes. By the assumed universality, a single parameter setting θ \theta θ realizes this score function on all of them.
Now consider any extendable state ( G , c ) (G,c) ( G , c ) and any uncolored node u u u . Let c ⋆ c^\star c ⋆ be a proper completion of c c c . Assigning i = c ⋆ ( u ) i=c^\star(u) i = c ⋆ ( u ) to u u u preserves extendability, so the maximum score at u u u is 1. Consequently, every maximizing color preserves extendability.
The selected node and all score ties may therefore be resolved arbitrarily. Every decoding step preserves extendability and colors one additional node. By induction, decoding reaches a complete extendable state, which is a proper coloring extending c 0 c_0 c 0 . □ \square □
Lemma 1. Consider a state ( G , c ) ∈ ⋃ τ ∈ S k S τ ⋅ ( G , c 0 ) (G,c) \in\bigcup_{\tau\in S_k} S_\tau\cdot(G,c_0) ( G , c ) ∈ ⋃ τ ∈ S k S τ ⋅ ( G , c 0 ) with exactly r r r colors appearing in c c c . Let R ( G , c ) = ∣ S k ⋅ ( G , c ) ∣ R(G,c)=|S_k \cdot(G,c)| R ( G , c ) = ∣ S k ⋅ ( G , c ) ∣ denote the size of the orbit of ( G , c ) (G,c) ( G , c ) under color permutations. Then,
k ! ( k − r ) ! min ( ∣ Aut ( G ) ∣ , r ! ) ≤ R ( G , c ) ≤ k ! ( k − r ) ! . \frac{k!}{(k-r)! \min(|\operatorname{Aut}(G)|,r!)} \leq R(G,c) \leq\frac{k!}{(k-r)!}. ( k − r )! min ( ∣ Aut ( G ) ∣ , r !) k ! ≤ R ( G , c ) ≤ ( k − r )! k ! .
Proof. Let C 1 , … , C r C_1,\ldots,C_r C 1 , … , C r be the used colors, and let Π c ≤ S r \Pi_c \leq S_r Π c ≤ S r be the group of permutations of the used colors that can be realized by automorphisms of G G G , that is,
Π c = { τ ∈ S r : ∃ φ ∈ Aut ( G ) s.t. c ( v ) = C i ⇒ c ( φ ( v ) ) = C τ ( i ) ∀ v ∈ V G , ∀ i = 1 , … , r } . \Pi_c = \left\{\tau\in S_r : \exists\varphi\in\operatorname{Aut}(G)\ \text{s.t.}\ c(v)=C_i \Rightarrow c(\varphi(v))=C_{\tau(i)}\ \forall v \in V_G,\ \forall i=1,\ldots,r\right\}. Π c = { τ ∈ S r : ∃ φ ∈ Aut ( G ) s.t. c ( v ) = C i ⇒ c ( φ ( v )) = C τ ( i ) ∀ v ∈ V G , ∀ i = 1 , … , r } .
A permutation τ ∈ S k \tau\in S_k τ ∈ S k stabilizes the state ( G , c ) (G,c) ( G , c ) if the partial coloring obtained by relabeling the colors according to τ \tau τ is isomorphic to ( G , c ) (G,c) ( G , c ) . Hence, on the r r r used colors, τ \tau τ must induce a permutation belonging to Π c \Pi_c Π c , while the remaining k − r k-r k − r unused colors may be permuted arbitrarily. Therefore, ∣ Stab S k ( G , c ) ∣ = ∣ Π c ∣ ( k − r ) ! |\operatorname{Stab}_{S_k}(G,c)|=|\Pi_c|(k-r)! ∣ Stab S k ( G , c ) ∣ = ∣ Π c ∣ ( k − r )! . By the orbit-stabilizer theorem [57 Chapter 3] , the orbit S k ⋅ ( G , c ) S_k \cdot(G,c) S k ⋅ ( G , c ) of ( G , c ) (G,c) ( G , c ) has cardinality
R ( G , c ) = ∣ S k ∣ ∣ Stab S k ( G , c ) ∣ = k ! ( k − r ) ! ∣ Π c ∣ . R(G,c)=\frac{|S_k|}{|\operatorname{Stab}_{S_k}(G,c)|}=\frac{k!}{(k-r)!|\Pi_c|}. R ( G , c ) = ∣ Stab S k ( G , c ) ∣ ∣ S k ∣ = ( k − r )! ∣ Π c ∣ k ! .
Since 1 ≤ ∣ Π c ∣ ≤ min ( ∣ Aut ( G ) ∣ , r ! ) 1 \leq|\Pi_c| \leq\min(|\operatorname{Aut}(G)|,r!) 1 ≤ ∣ Π c ∣ ≤ min ( ∣ Aut ( G ) ∣ , r !) , we have the claim. □ \square □
In the main paper, we claim that, for Sudoku puzzles, a careful application of the lemma yields a reduction in the state space size by a factor of R ( G , c ) = 9 ! ∣ Π c ∣ ≥ 9 ! 648 = 560 R(G,c)=\frac{9!}{|\Pi_c|}\geq\frac{9!}{648}=560 R ( G , c ) = ∣ Π c ∣ 9 ! ≥ 648 9 ! = 560 . This requires first the following lemma.
Lemma 2 (Automorphisms of a uniquely completable Sudoku). Let G , c G,c G , c be a 9 × 9 9 \times9 9 × 9 Sudoku puzzle with unique completion c ⋆ c^\star c ⋆ , and let Π c \Pi_c Π c be as defined in Lemma 1. Then
∣ Π c ∣ ≤ ∣ Π c ⋆ ∣ ≤ 648. |\Pi_c| \leq|\Pi_{c^\star}| \leq648. ∣ Π c ∣ ≤ ∣ Π c ⋆ ∣ ≤ 648.
Proof. First, c c c must contain 8 or 9 distinct digits. Otherwise, two digits would be absent from c c c , and swapping those digits in c ⋆ c^\star c ⋆ would produce a second completion of c c c . Therefore, if r r r is the number of digits occurring in c c c , then r ∈ { 8 , 9 } r \in\{8,9\} r ∈ { 8 , 9 } . Let τ ∈ Π c \tau\in\Pi_c τ ∈ Π c . By the definition of Π c \Pi_c Π c , there exists ϕ ∈ Aut ( G ) \phi\in\operatorname{Aut}(G) ϕ ∈ Aut ( G ) such that c ( ϕ ( v ) ) = τ ( c ( v ) ) c(\phi(v)) = \tau(c(v)) c ( ϕ ( v )) = τ ( c ( v )) for every colored vertex v v v . Note that even if r = 8 r = 8 r = 8 , the permutation τ \tau τ has a unique extension in S 9 S_9 S 9 by fixing the remaining digit.
Define a completed coloring c ′ c' c ′ by c ′ ( ϕ ( v ) ) = τ ( c ⋆ ( v ) ) c'(\phi(v)) = \tau(c^\star(v)) c ′ ( ϕ ( v )) = τ ( c ⋆ ( v )) . The automorphism ϕ \phi ϕ preserves the Sudoku constraint graph, and τ \tau τ only relabels the digits, so c ′ c' c ′ is a valid completed Sudoku grid.
Let V c V_c V c be the set of colored nodes and note that ϕ ( V c ) = V c \phi(V_c) = V_c ϕ ( V c ) = V c . Now let x ∈ V c x \in V_c x ∈ V c . Since ϕ ( V c ) = V c \phi(V_c) = V_c ϕ ( V c ) = V c , there is some v ∈ V c v \in V_c v ∈ V c such that x = ϕ ( v ) x = \phi(v) x = ϕ ( v ) . Because c ⋆ c^\star c ⋆ extends c c c , we have
c ′ ( x ) = τ ( c ⋆ ( v ) ) = τ ( c ( v ) ) = c ( ϕ ( v ) ) = c ( x ) . c'(x) = \tau(c^\star(v)) = \tau(c(v)) = c(\phi(v)) = c(x). c ′ ( x ) = τ ( c ⋆ ( v )) = τ ( c ( v )) = c ( ϕ ( v )) = c ( x ) .
Hence c ′ c' c ′ extends c c c . Since c c c has the unique completion c ⋆ c^\star c ⋆ , it follows that c ′ = c ⋆ c' = c^\star c ′ = c ⋆ . Therefore, c ⋆ ( ϕ ( v ) ) = τ ( c ⋆ ( v ) ) c^\star(\phi(v)) = \tau(c^\star(v)) c ⋆ ( ϕ ( v )) = τ ( c ⋆ ( v )) for every v ∈ V G v \in V_G v ∈ V G . Hence τ ∈ Π c ⋆ \tau\in\Pi_{c^\star} τ ∈ Π c ⋆ and ∣ Π c ∣ ≤ ∣ Π c ⋆ ∣ |\Pi_c| \leq|\Pi_{c^\star}| ∣ Π c ∣ ≤ ∣ Π c ⋆ ∣ .
Let Γ c ⋆ \Gamma_{c^\star} Γ c ⋆ denote the full automorphism group of the completed grid, whose elements are the pairs ( ϕ , σ ) ∈ Aut ( G ) × S 9 (\phi, \sigma) \in\operatorname{Aut}(G) \times S_9 ( ϕ , σ ) ∈ Aut ( G ) × S 9 satisfying c ⋆ ( ϕ ( v ) ) = σ ( c ⋆ ( v ) ) c^\star(\phi(v)) = \sigma(c^\star(v)) c ⋆ ( ϕ ( v )) = σ ( c ⋆ ( v )) for every v v v . The projection of Γ c ⋆ \Gamma_{c^\star} Γ c ⋆ onto its digit-permutation component has image Π c ⋆ \Pi_{c^\star} Π c ⋆ . Therefore, ∣ Π c ⋆ ∣ ≤ ∣ Γ c ⋆ ∣ |\Pi_{c^\star}| \leq|\Gamma_{c^\star}| ∣ Π c ⋆ ∣ ≤ ∣ Γ c ⋆ ∣ . Finally, McGuire et al. (2014) argue that ∣ Γ c ⋆ ∣ ≤ 648 |\Gamma_{c^\star}| \leq648 ∣ Γ c ⋆ ∣ ≤ 648 , which proves the result.
Theorem 1 (Exponential reduction in the state space). Consider a finite k k k -colorability instance set I \mathcal{I} I with no starting colors. Let ∣ Aut ( G ) ∣ ≤ B ∀ G ∈ I |\operatorname{Aut}(G)| \leq B \ \forall G \in\mathcal{I} ∣ Aut ( G ) ∣ ≤ B ∀ G ∈ I . Let S I S_{\mathcal{I}} S I be its associated state space and S I + S_{\mathcal{I}}^+ S I + the space of extendable states. Then:
If all graphs G ∈ I G \in\mathcal{I} G ∈ I have more than k k k nodes, then ∣ S I / S k ∣ ≤ B 16 e k ∣ S I ∣ |S_{\mathcal{I}}/S_k| \leq B \frac{16}{e^k}|S_{\mathcal{I}}| ∣ S I / S k ∣ ≤ B e k 16 ∣ S I ∣ .
If all graphs G ∈ I G \in\mathcal{I} G ∈ I satisfy 0 ≤ k − χ ( G ) ≤ κ 0 \leq k - \chi(G) \leq\kappa 0 ≤ k − χ ( G ) ≤ κ , then ∣ S I + / S k ∣ ≤ B κ ! 2 k − κ k ! ∣ S I + ∣ |S_{\mathcal{I}}^+/S_k| \leq B \frac{\kappa! \, 2^{k-\kappa}}{k!}|S_{\mathcal{I}}^+| ∣ S I + / S k ∣ ≤ B k ! κ ! 2 k − κ ∣ S I + ∣ .
Proof. Let S ~ G \widetilde{S}_G S G be the state space before quotienting by graph isomorphisms, i.e. where each node has an unique identifier. We then have that S G = S ~ G / Aut ( G ) S_G = \widetilde{S}_G/\operatorname{Aut}(G) S G = S G / Aut ( G ) by definition, and since Aut ( G ) \operatorname{Aut}(G) Aut ( G ) commutes with the color permutations S k S_k S k , we have that S G / S k = S ~ G / ( Aut ( G ) × S k ) S_G/S_k = \widetilde{S}_G/(\operatorname{Aut}(G) \times S_k) S G / S k = S G / ( Aut ( G ) × S k ) . Moreover, ∣ S ~ G ∣ ≤ ∣ Aut ( G ) ∣ ∣ S ~ G / Aut ( G ) ∣ |\widetilde{S}_G| \leq|\operatorname{Aut}(G)||\widetilde{S}_G/\operatorname{Aut}(G)| ∣ S G ∣ ≤ ∣ Aut ( G ) ∣∣ S G / Aut ( G ) ∣ as every Aut ( G ) \operatorname{Aut}(G) Aut ( G ) -orbit can only have size at most ∣ Aut ( G ) ∣ |\operatorname{Aut}(G)| ∣ Aut ( G ) ∣ , and S ~ G / ( Aut ( G ) × S k ) ≤ S ~ G / S k \widetilde{S}_G/(\operatorname{Aut}(G) \times S_k) \leq\widetilde{S}_G/S_k S G / ( Aut ( G ) × S k ) ≤ S G / S k as quotienting by Aut ( G ) \operatorname{Aut}(G) Aut ( G ) can only decrease the number of elements. Therefore, we have that
∣ S G ∣ ∣ S G / S k ∣ = ∣ S ~ G / Aut ( G ) ∣ ∣ S ~ G / ( Aut ( G ) × S k ) ∣ ≥ ∣ S ~ G ∣ ∣ S ~ G / S k ∣ ∣ Aut ( G ) ∣ ≥ 1 B ∣ S ~ G ∣ ∣ S ~ G / S k ∣ . \frac{|S_G|}{|S_G/S_k|} = \frac{|\widetilde{S}_G/\operatorname{Aut}(G)|}{|\widetilde{S}_G/(\operatorname{Aut}(G) \times S_k)|} \geq\frac{|\widetilde{S}_G|}{|\widetilde{S}_G/S_k||\operatorname{Aut}(G)|} \geq\frac{1}{B}\frac{|\widetilde{S}_G|}{|\widetilde{S}_G/S_k|}. ∣ S G / S k ∣ ∣ S G ∣ = ∣ S G / ( Aut ( G ) × S k ) ∣ ∣ S G / Aut ( G ) ∣ ≥ ∣ S G / S k ∣∣ Aut ( G ) ∣ ∣ S G ∣ ≥ B 1 ∣ S G / S k ∣ ∣ S G ∣ .
The same derivation follows for the extendable versions, yielding ∣ S G + ∣ ∣ S G + / S k ∣ ≥ 1 B ∣ S ~ G + ∣ ∣ S ~ G + / S k ∣ \frac{|S_G^+|}{|S_G^+/S_k|} \geq\frac{1}{B}\frac{|\widetilde{S}_G^+|}{|\widetilde{S}_G^+/S_k|} ∣ S G + / S k ∣ ∣ S G + ∣ ≥ B 1 ∣ S G + / S k ∣ ∣ S G + ∣ . Since the 1 / B 1/B 1/ B factor does not depend on G G G , we can get the same factor uniformly over I \mathcal{I} I . Therefore, we will work with the states with identified nodes, which ensures that coloring different nodes leads to different states.
We first prove the reduction for S ~ I \widetilde{S}_{\mathcal{I}} S I . Let’s consider an graph G G G with n n n nodes. In the resulting state space S ~ G \widetilde{S}_G S G , each of those nodes can be either uncolored or have one of the k k k available colors, leading to a total of ( k + 1 ) n (k+1)^n ( k + 1 ) n possible states. The quotient space S ~ G / S k \widetilde{S}_G/S_k S G / S k ignores the identities of the colors. Therefore, to count the number of states using r r r colors, we count the number of partitions of n n n elements (the nodes) into r r r equivalent non-empty classes (the colors) and one distinct and possibly empty class (the uncolored nodes). To count these, we use the following construction. We add a dummy node, and we say that whichever class this node is assigned to, is the class of uncolored nodes. We can then count the number of partitions of n + 1 n+1 n + 1 elements into r + 1 r+1 r + 1 equivalent and non-empty classes, which is the Stirling number of second kind { n + 1 r + 1 } \left\{\begin{matrix} n+1 \\ r+1 \end{matrix}\right\} { n + 1 r + 1 } [25 ] . We then have that ∣ S ~ G / S k ∣ = ∑ r = 0 k { n + 1 r + 1 } |\widetilde{S}_G/S_k| = \sum_{r=0}^{k}\left\{\begin{matrix} n+1 \\ r+1 \end{matrix}\right\} ∣ S G / S k ∣ = ∑ r = 0 k { n + 1 r + 1 } . Therefore, we obtain the exact formula R : = ∣ S ~ G ∣ / ∣ S ~ G / S k ∣ = ( k + 1 ) n ∑ r = 0 k { n + 1 r + 1 } R := |\widetilde{S}_G|/|\widetilde{S}_G/S_k| = \frac{(k+1)^n}{\sum_{r=0}^{k}\left\{\begin{matrix} n+1 \\ r+1 \end{matrix}\right\}} R := ∣ S G ∣/∣ S G / S k ∣ = ∑ r = 0 k { n + 1 r + 1 } ( k + 1 ) n .
Then, a standard bound yields that { n + 1 r + 1 } ≤ ( r + 1 ) n r ! \left\{\begin{matrix} n+1 \\ r+1 \end{matrix}\right\} \leq\frac{(r+1)^n}{r!} { n + 1 r + 1 } ≤ r ! ( r + 1 ) n , which then implies a reduction of factor
R ≥ ( ∑ r = 0 k 1 r ! ( r + 1 k + 1 ) n ) − 1 ≥ ( ∑ r = 0 k 1 r ! ( 1 − k − r k + 1 ) k + 1 ) − 1 ≥ ( ∑ r = 0 k e r − k r ! ) − 1 = e k ( ∑ r = 0 k e r r ! ) − 1 ≥ e k e . (1) R \geq\left(\sum_{r=0}^{k}\frac{1}{r!}\left(\frac{r+1}{k+1}\right)^n\right)^{-1} \geq\left(\sum_{r=0}^{k}\frac{1}{r!}\left(1-\frac{k-r}{k+1}\right)^{k+1}\right)^{-1} \geq\left(\sum_{r=0}^{k}\frac{e^{r-k}}{r!}\right)^{-1} = e^k\left(\sum_{r=0}^{k}\frac{e^r}{r!}\right)^{-1} \geq\frac{e^k}{e}. \tag*{(1)} R ≥ ( r = 0 ∑ k r ! 1 ( k + 1 r + 1 ) n ) − 1 ≥ ( r = 0 ∑ k r ! 1 ( 1 − k + 1 k − r ) k + 1 ) − 1 ≥ ( r = 0 ∑ k r ! e r − k ) − 1 = e k ( r = 0 ∑ k r ! e r ) − 1 ≥ e e k . (1)
Taking the bound over all G ∈ I G \in\mathcal{I} G ∈ I yields the claim.
We then prove the reduction for S ~ + \widetilde{S}_+ S + . Let’s consider a graph G G G with χ ( G ) = q \chi(G)=q χ ( G ) = q . Let E r E_r E r be the number of extendable quotient states (i.e., states in S ~ G + / S k \widetilde{S}_G^+/S_k S G + / S k ) that use exactly r r r colors. If r < q r<q r < q , then at least q − r q-r q − r colors absent from the current state occur on uncolored vertices. Choosing one vertex carrying each such color produces at least q − r q-r q − r distinct ( r + 1 ) (r+1) ( r + 1 ) -color successor states. On the other hand, each r + 1 r+1 r + 1 -color state has an r r r -color predecessor of this type only by uncoloring the unique vertex of a singleton color class. Hence it has at most r + 1 r+1 r + 1 predecessors. This implies the inequality ( q − r ) E r ≤ ( r + 1 ) E r + 1 (q-r)E_r\leq(r+1)E_{r+1} ( q − r ) E r ≤ ( r + 1 ) E r + 1 . Importantly, if we didn’t work on S ~ \widetilde{S} S and didn’t have the unique node identifiers, several such successors may collapse to the same quotient state under graph automorphisms, so the lower bound ( q − r ) (q-r) ( q − r ) on the number of distinct successors could fail. We therefore have
E r ( q r ) ≤ E r + 1 ( q r + 1 ) ∀ 0 ≤ r < q , \frac{E_r}{\binom{q}{r}} \leq\frac{E_{r+1}}{\binom{q}{r+1}} \qquad\forall\ 0\leq r<q, ( r q ) E r ≤ ( r + 1 q ) E r + 1 ∀ 0 ≤ r < q ,
i.e., a r : = E r ( q r ) a_r:=\frac{E_r}{\binom{q}{r}} a r := ( r q ) E r is nondecreasing in r r r .
We claim that, for every R ≤ q R\leq q R ≤ q ,
∑ r = 0 R E r ∑ r = 0 q E r ≤ ∑ r = 0 R E r ∑ r = 0 q E r ≤ 2 − q ∑ r = 0 R ( q r ) . \frac{\sum_{r=0}^{R}E_r}{\sum_{r=0}^{q}E_r}
\leq
\frac{\sum_{r=0}^{R}E_r}{\sum_{r=0}^{q}E_r}
\leq
2^{-q}\sum_{r=0}^{R}\binom{q}{r}. ∑ r = 0 q E r ∑ r = 0 R E r ≤ ∑ r = 0 q E r ∑ r = 0 R E r ≤ 2 − q r = 0 ∑ R ( r q ) .
To prove it, set A : = ∑ r = 0 R a r ( q r ) A:=\sum_{r=0}^{R}a_r\binom{q}{r} A := ∑ r = 0 R a r ( r q ) , B : = ∑ r = R + 1 q a r ( q r ) B:=\sum_{r=R+1}^{q}a_r\binom{q}{r} B := ∑ r = R + 1 q a r ( r q ) , C : = ∑ r = 0 R ( q r ) C:=\sum_{r=0}^{R}\binom{q}{r} C := ∑ r = 0 R ( r q ) , and D : = ∑ r = R + 1 q ( q r ) D:=\sum_{r=R+1}^{q}\binom{q}{r} D := ∑ r = R + 1 q ( r q ) . Then it suffices to show
A A + B ≤ C C + D , \frac{A}{A+B}\leq\frac{C}{C+D}, A + B A ≤ C + D C ,
or equivalently, A D ≤ B C AD\leq BC A D ≤ B C .
Since a r ≤ a R a_r\leq a_R a r ≤ a R for every r ≤ R r\leq R r ≤ R , we have
A = ∑ r = 0 R a r ( q r ) ≤ a R ∑ r = 0 R ( q r ) = a R C . A=\sum_{r=0}^{R}a_r\binom{q}{r}\leq a_R\sum_{r=0}^{R}\binom{q}{r}=a_RC. A = r = 0 ∑ R a r ( r q ) ≤ a R r = 0 ∑ R ( r q ) = a R C .
Similarly, since a r ≥ a R a_r\geq a_R a r ≥ a R for every r > R r>R r > R ,
B = ∑ r = R + 1 q a r ( q r ) ≥ a R ∑ r = R + 1 q ( q r ) = a R D . B=\sum_{r=R+1}^{q}a_r\binom{q}{r}\geq a_R\sum_{r=R+1}^{q}\binom{q}{r}=a_RD. B = r = R + 1 ∑ q a r ( r q ) ≥ a R r = R + 1 ∑ q ( r q ) = a R D .
Multiplying the first inequality by D D D and the second by C C C we obtain A D ≤ a R C D ≤ B C AD\leq a_RCD\leq BC A D ≤ a R C D ≤ B C . We then have that
∑ r = 0 R a r ( q r ) ∑ r = 0 q a r ( q r ) ≤ ∑ r = 0 R ( q r ) ∑ r = 0 q ( q r ) . \frac{\sum_{r=0}^{R}a_r\binom{q}{r}}{\sum_{r=0}^{q}a_r\binom{q}{r}}
\leq
\frac{\sum_{r=0}^{R}\binom{q}{r}}{\sum_{r=0}^{q}\binom{q}{r}}. ∑ r = 0 q a r ( r q ) ∑ r = 0 R a r ( r q ) ≤ ∑ r = 0 q ( r q ) ∑ r = 0 R ( r q ) .
Finally, using ∑ r = 0 q ( q r ) = 2 q \sum_{r=0}^{q}\binom{q}{r}=2^q ∑ r = 0 q ( r q ) = 2 q , we obtain
∑ r = 0 R E r ∑ r = 0 k E r ≤ ∑ r = 0 R E r ∑ r = 0 q E r ≤ 2 − q ∑ r = 0 R ( q r ) . \frac{\sum_{r=0}^{R}E_r}{\sum_{r=0}^{k}E_r}
\leq
\frac{\sum_{r=0}^{R}E_r}{\sum_{r=0}^{q}E_r}
\leq
2^{-q}\sum_{r=0}^{R}\binom{q}{r}. ∑ r = 0 k E r ∑ r = 0 R E r ≤ ∑ r = 0 q E r ∑ r = 0 R E r ≤ 2 − q r = 0 ∑ R ( r q ) .
Therefore the distribution with density f ( r ) = E r ∑ j = 0 q E j f(r)=\frac{E_r}{\sum_{j=0}^{q}E_j} f ( r ) = ∑ j = 0 q E j E r stochastically dominates Bin ( q , 1 / 2 ) \operatorname{Bin}(q,1/2) Bin ( q , 1/2 ) , which stochastically dominates Bin ( k − κ , 1 / 2 ) \operatorname{Bin}(k-\kappa,1/2) Bin ( k − κ , 1/2 ) , for κ ∈ { 0 , … , k } \kappa\in\{0,\ldots,k\} κ ∈ { 0 , … , k } . Since 0 ≤ k − χ ( G ) ≤ κ ≤ k 0\leq k-\chi(G)\leq\kappa\leq k 0 ≤ k − χ ( G ) ≤ κ ≤ k , this is well defined. Since k ! ( k − r ) ! \frac{k!}{(k-r)!} ( k − r )! k ! is nondecreasing in r r r , we then have that
∣ S ~ + ∣ ∣ S ~ G + / S k ∣ = ∑ r = 0 k E r k ! ( k − r ) ! ∑ r = 0 k E r = ∑ r = 0 k E r ∑ j = 0 k E j k ! ( k − r ) ! ≥ ∑ r = 0 q 1 2 q ( q r ) k ! ( k − r ) ! ≥ ∑ r = 0 k − κ 1 2 k − κ ( k − κ r ) k ! ( k − r ) ! . \frac{|\widetilde{S}_+|}{|\widetilde{S}_G^+/S_k|}
=
\frac{\sum_{r=0}^{k}E_r\frac{k!}{(k-r)!}}{\sum_{r=0}^{k}E_r}
=
\sum_{r=0}^{k}\frac{E_r}{\sum_{j=0}^{k}E_j}\frac{k!}{(k-r)!}
\geq
\sum_{r=0}^{q}\frac{1}{2^q}\binom{q}{r}\frac{k!}{(k-r)!}
\geq
\sum_{r=0}^{k-\kappa}\frac{1}{2^{k-\kappa}}\binom{k-\kappa}{r}\frac{k!}{(k-r)!}. ∣ S G + / S k ∣ ∣ S + ∣ = ∑ r = 0 k E r ∑ r = 0 k E r ( k − r )! k ! = r = 0 ∑ k ∑ j = 0 k E j E r ( k − r )! k ! ≥ r = 0 ∑ q 2 q 1 ( r q ) ( k − r )! k ! ≥ r = 0 ∑ k − κ 2 k − κ 1 ( r k − κ ) ( k − r )! k ! .
If we take only the r = k − κ r=k-\kappa r = k − κ term, we obtain a k ! 2 k − κ κ ! \frac{k!}{2^{k-\kappa}\kappa!} 2 k − κ κ ! k ! bound. Taking the bound over all instances then yields the claim.
Section 4
We prove that the color predictor of SCONE is equivariant to node and color permutations. Importantly, this guarantee applies only to the predicted color scores. We do not require tie-breaking among colors or the complete decoding procedure to be equivariant.
Theorem 2. The color predictor of SCONE is equivariant to the joint action of S ∣ V G ∣ × S k S_{\lvert V_G\rvert} \times S_k S ∣ V G ∣ × S k . Let ( G , c ) (G,c) ( G , c ) be any graph k k k -coloring instance, and let p u ( G , c ) ∈ R k p_u(G,c) \in\mathbb{R}^k p u ( G , c ) ∈ R k be the output of the predictor for node u u u . Then, for every parameter setting, every π ∈ S ∣ V G ∣ \pi\in S_{\lvert V_G\rvert} π ∈ S ∣ V G ∣ , every τ ∈ S k \tau\in S_k τ ∈ S k , and every u ∈ V G u \in V_G u ∈ V G ,
p π ( u ) ( π ⋅ G , τ ⋅ ( π ⋅ c ) ) = P τ p u ( G , c ) . p_{\pi(u)}\left(\pi\cdot G,\tau\cdot(\pi\cdot c)\right)=P_\tau p_u(G,c). p π ( u ) ( π ⋅ G , τ ⋅ ( π ⋅ c ) ) = P τ p u ( G , c ) .
Proof. Let ( G ′ , c ′ ) = ( π ⋅ G , τ ⋅ ( π ⋅ c ) ) (G',c')=(\pi\cdot G,\tau\cdot(\pi\cdot c)) ( G ′ , c ′ ) = ( π ⋅ G , τ ⋅ ( π ⋅ c )) . We show by induction over the message-passing layers that
H π ( u ) ℓ ( G ′ , c ′ ) = P τ H u ℓ ( G , c ) ∀ u ∈ V G . H^\ell_{\pi(u)}(G',c')=P_\tau H^\ell_u(G,c) \qquad\forall u \in V_G. H π ( u ) ℓ ( G ′ , c ′ ) = P τ H u ℓ ( G , c ) ∀ u ∈ V G .
For ℓ = 0 \ell=0 ℓ = 0 , if c ( u ) = ε c(u)=\varepsilon c ( u ) = ε , then c ′ ( π ( u ) ) = ε c'(\pi(u))=\varepsilon c ′ ( π ( u )) = ε , and both sides contain e u n k e_{\mathrm{unk}} e unk in every color slot. Otherwise, c ′ ( π ( u ) ) = τ ( c ( u ) ) c'(\pi(u))=\tau(c(u)) c ′ ( π ( u )) = τ ( c ( u )) . Hence the slot containing e o n e_{\mathrm{on}} e on is permuted from c ( u ) c(u) c ( u ) to τ ( c ( u ) ) \tau(c(u)) τ ( c ( u )) , while every other slot contains e o f f e_{\mathrm{off}} e off . Therefore, we have that H π ( u ) 0 ( G ′ , c ′ ) = P τ H u 0 ( G , c ) H^0_{\pi(u)}(G',c')=P_\tau H^0_u(G,c) H π ( u ) 0 ( G ′ , c ′ ) = P τ H u 0 ( G , c ) .
Suppose that the claim holds at layer ℓ − 1 \ell-1 ℓ − 1 . Since node relabeling preserves neighborhoods,
N G ′ ( π ( u ) ) = { π ( v ) : v ∈ N G ( u ) } . N_{G'}(\pi(u))=\{\pi(v):v \in N_G(u)\}. N G ′ ( π ( u )) = { π ( v ) : v ∈ N G ( u )} .
Using the induction hypothesis and the equivariance of the element-wise aggregator, we obtain
H ^ π ( u ) ℓ ( G ′ , c ′ ) = ⨁ w ∈ N G ′ ( π ( u ) ) H w ℓ − 1 ( G ′ , c ′ ) = ⨁ v ∈ N G ( u ) P τ H v ℓ − 1 ( G , c ) = P τ H ^ u ℓ ( G , c ) . \begin{aligned}
\widehat{H}^\ell_{\pi(u)}(G',c') &= \bigoplus_{w \in N_{G'}(\pi(u))} H^{\ell-1}_w(G',c') \\
&= \bigoplus_{v \in N_G(u)} P_\tau H^{\ell-1}_v(G,c) \\
&= P_\tau\widehat{H}^\ell_u(G,c).
\end{aligned} H π ( u ) ℓ ( G ′ , c ′ ) = w ∈ N G ′ ( π ( u )) ⨁ H w ℓ − 1 ( G ′ , c ′ ) = v ∈ N G ( u ) ⨁ P τ H v ℓ − 1 ( G , c ) = P τ H u ℓ ( G , c ) .
We next verify that every linear map L L L used in MLP S k \operatorname{MLP}_{S_k} MLP S k is color-equivariant. For every slot i i i ,
L ( P τ H ) [ i ] = W s e l f H [ τ − 1 ( i ) ] + W a l l ∑ j = 1 k H [ τ − 1 ( j ) ] + b = W s e l f H [ τ − 1 ( i ) ] + W a l l ∑ j = 1 k H [ j ] + b = [ P τ L ( H ) ] i . \begin{aligned}
L(P_\tau H)[i] &= W_{\mathrm{self}}H[\tau^{-1}(i)] + W_{\mathrm{all}}\sum_{j=1}^{k} H[\tau^{-1}(j)] + b \\
&= W_{\mathrm{self}}H[\tau^{-1}(i)] + W_{\mathrm{all}}\sum_{j=1}^{k} H[j] + b \\
&= [P_\tau L(H)]_i.
\end{aligned} L ( P τ H ) [ i ] = W self H [ τ − 1 ( i )] + W all j = 1 ∑ k H [ τ − 1 ( j )] + b = W self H [ τ − 1 ( i )] + W all j = 1 ∑ k H [ j ] + b = [ P τ L ( H ) ] i .
Point-wise nonlinearities also commute with permutations of the color slots. Therefore, their composition MLP S k \operatorname{MLP}_{S_k} MLP S k is S k S_k S k -equivariant. Moreover, concatenation along the feature axis satisfies
P τ ( A ∥ B ) = ( P τ A ) ∥ ( P τ B ) . P_\tau(A \mathbin{\|} B)=(P_\tau A)\mathbin{\|}(P_\tau B). P τ ( A ∥ B ) = ( P τ A ) ∥ ( P τ B ) .
LayerNorm is applied independently to each color slot with shared parameters, so it also commutes with P τ P_\tau P τ . The same holds for the residual connection. Consequently,
H π ( u ) ℓ ( G ′ , c ′ ) = P τ H u ℓ ( G , c ) , H^\ell_{\pi(u)}(G',c')=P_\tau H^\ell_u(G,c), H π ( u ) ℓ ( G ′ , c ′ ) = P τ H u ℓ ( G , c ) ,
completing the induction.
Finally, the readout MLP S k \operatorname{MLP}_{S_k} MLP S k is color-equivariant by the same argument. If a softmax is applied to obtain probabilities, it also commutes with color permutations. We therefore have
p π ( u ) ( π ⋅ G , τ ⋅ ( π ⋅ c ) ) = P τ p u ( G , c ) p_{\pi(u)}\left(\pi\cdot G,\tau\cdot(\pi\cdot c)\right)=P_\tau p_u(G,c) p π ( u ) ( π ⋅ G , τ ⋅ ( π ⋅ c ) ) = P τ p u ( G , c )
for every node and parameter setting, proving equivariance to the joint action of S ∣ V G ∣ × S k S_{\lvert V_G\rvert} \times S_k S ∣ V G ∣ × S k .
Theorem 4. Let k , Δ ∈ N k,\Delta\in\mathbb{N} k , Δ ∈ N . There exists a parameter setting of SCONE s.t. every k k k -colorable cycle, chordal or bipartite graph with degree at most Δ \Delta Δ can be properly colored from the empty coloring.
Proof. Let c c c be the current proper partial coloring, and let ε \varepsilon ε denote the label of an uncolored node. For every uncolored node v v v , define
F c ( v ) = { c ( u ) : u ∈ N G ( v ) , c ( u ) ≠ ε } , F_c(v) = \{c(u) : u \in N_G(v),\ c(u) \ne\varepsilon\}, F c ( v ) = { c ( u ) : u ∈ N G ( v ) , c ( u ) = ε } ,
T c ( v ) = { c ( w ) : ∃ u , { v , u } , { u , w } ∈ E G , c ( u ) , c ( w ) ≠ ε } ∖ F c ( v ) . T_c(v) = \{c(w) : \exists u,\ \{v,u\},\{u,w\} \in E_G,\ c(u),c(w) \ne\varepsilon\} \setminus F_c(v). T c ( v ) = { c ( w ) : ∃ u , { v , u } , { u , w } ∈ E G , c ( u ) , c ( w ) = ε } ∖ F c ( v ) .
Thus, F c ( v ) F_c(v) F c ( v ) contains the colors appearing on colored neighbors of v v v , while T c ( v ) T_c(v) T c ( v ) contains the available colors observed at distance two through a colored neighbor.
The most-constrained-first decoder of SCONE selects an uncolored node maximizing ∣ F c ( v ) ∣ |F_c(v)| ∣ F c ( v ) ∣ .
The color predictor realizing the claim gives maximum score to the colors in T c ( v ) T_c(v) T c ( v ) when this set is nonempty, and to the colors in [ k ] ∖ F c ( v ) [k] \setminus F_c(v) [ k ] ∖ F c ( v ) otherwise. We first show that this is realizable by SCONE. The set F c ( v ) F_c(v) F c ( v ) is determined by the one-hop neighborhood of v v v . In the first message-passing layer, each colored node can additionally record the colors appearing in its neighborhood. Aggregating these representations in a second layer determines T c ( v ) T_c(v) T c ( v ) and whether it is empty. Since k k k and Δ \Delta Δ are fixed, only finitely many relevant aggregate inputs can occur. With sufficient width, the color-equivariant MLPs can assign distinct codes to these inputs. The codes can be chosen to remain distinct after LayerNorm, while the residual term can be incorporated into the finite lookup performed by the following layer. Any additional layers can implement the identity by setting their residual update to zero. Hence the rule can be realized by a single parameter setting of the full architecture SCONE. We then show that it succeeds on each graph family.
First, let G G G be bipartite. We treat each connected component separately, and isolated nodes are immediate. Let’s then consider a component with bipartition ( A , B ) (A,B) ( A , B ) , and assume without loss of generality that its first selected node lies in A A A and receives color a a a . The connectivity of the component guarantees that while there are uncolored nodes, at least one has ∣ F c ( v ) ∣ ≥ 1 |F_c(v)| \ge1 ∣ F c ( v ) ∣ ≥ 1 . Moreover, all nodes other components have ∣ F c ( v ) ∣ = 0 |F_c(v)| = 0 ∣ F c ( v ) ∣ = 0 , so the decoder will color the current component before moving to another one. The first selected node in B B B receives some color b ≠ a b \ne a b = a .
We show inductively that every colored node in A A A has color a a a and every colored node in B B B has color b b b . The base case is given by the first two selected nodes. Let’s then suppose that the inductive hypothesis holds. Suppose that the decoder selects the next node to be v ∈ A v \in A v ∈ A . Then it must have a colored neighbor u ∈ B u \in B u ∈ B , so F c ( v ) = { b } F_c(v) = \{b\} F c ( v ) = { b } . Moreover, u u u has a previously colored neighbor in A A A . Thus v v v has a colored node at distance two. Since every node at distance two from v v v lies in A A A , we have T c ( v ) = { a } T_c(v) = \{a\} T c ( v ) = { a } , and the decoder assigns color a a a to v v v . The argument for v ∈ B v \in B v ∈ B is symmetric. Hence, inductively, the component is colored properly using only a a a and b b b .
Every even cycle is bipartite, so the preceding argument also applies to it. Now consider an odd cycle. After the first two adjacent nodes receive distinct colors a a a and b b b , the same two-hop rule extends an alternating coloring along the cycle. Until only one node remains uncolored, the colored nodes form a path whose colors alternate between a a a and b b b . The path between the two neighbors of the final node has an odd number of edges, so these neighbors have different colors. Thus both a a a and b b b belong to F c ( v ) F_c(v) F c ( v ) for the final node and T c ( v ) = ∅ T_c(v) = \varnothing T c ( v ) = ∅ . Since an odd cycle is k k k -colorable only if k ≥ 3 k \ge3 k ≥ 3 , some color in [ k ] ∖ { a , b } [k] \setminus\{a,b\} [ k ] ∖ { a , b } remains available and completes a proper coloring.
Finally, let G G G be chordal. Let x 1 , … , x n x_1,\ldots,x_n x 1 , … , x n denote the order in which the decoder colors the nodes. We show inductively that every prefix x 1 , … , x t x_1,\ldots,x_t x 1 , … , x t is a valid prefix of maximum cardinality search (MCS), as introduced in [61 ] . The first choice is valid because all nodes initially have no colored neighbors.
Suppose that x 1 , … , x t − 1 x_1,\ldots,x_{t-1} x 1 , … , x t − 1 is an MCS prefix and that the current partial coloring is proper. Continue this prefix arbitrarily according to MCS, and number the resulting ordering by α ( x j ) = n − j + 1 \alpha(x_j) = n-j+1 α ( x j ) = n − j + 1 . On a chordal graph, every ordering produced by MCS is a perfect elimination ordering [61 ] . With this numbering convention, the higher-numbered neighbors of every node form a clique. Therefore, the already-colored neighbors of every uncolored node form a clique.
Since the partial coloring is proper, these neighbors have pairwise distinct colors. Therefore, for every uncolored node v v v , its saturation ∣ F c ( v ) ∣ |F_c(v)| ∣ F c ( v ) ∣ equals its number of already-colored neighbors. Maximizing saturation is therefore exactly the MCS selection rule. The node selected by the decoder is a valid next MCS choice, while its confidence-based secondary criterion only breaks ties between valid choices.
The already-colored neighbors of the selected node form a clique of size at most ω ( G ) − 1 \omega(G)-1 ω ( G ) − 1 . Chordal graphs are perfect, so ω ( G ) = χ ( G ) ≤ k \omega(G)=\chi(G)\le k ω ( G ) = χ ( G ) ≤ k . Hence at most k − 1 k-1 k − 1 colors are forbidden. The set [ k ] ∖ F c ( v ) [k]\setminus F_c(v) [ k ] ∖ F c ( v ) is therefore nonempty, and every color preferred by the predictor is available. Assigning one of these colors preserves properness and completes the induction.
Thus, the same parameter setting properly colors every k k k -colorable bipartite, chordal, or cycle graph of maximum degree at most Δ \Delta Δ , independently of its number of nodes.
Proof of Theorem 3
Theorem 5 shows that sequential coloring succeeds whenever the predictor can realize arbitrary scoring rules on the relevant rooted isomorphism types. We now show that the sum-aggregating version of SCONE has this property on cover-separated families of amenable graphs, and results easily extend to any injective aggregation ⊕ \oplus ⊕ . Throughout this section, the depth and width of the network may depend on n n n and k k k .
Recall that the 1-dimensional Weisfeiler-Leman algorithm (1-WL) iteratively refines node labels according to the labels of neighboring nodes [6 , 72 , 49 ] . Given a partially colored graph ( G , c ) (G,c) ( G , c ) , we initialize
W L 0 ( G , c , v ) = c ( v ) \mathrm{WL}^{0}(G,c,v)=c(v) WL 0 ( G , c , v ) = c ( v )
for every v ∈ V G v\in V_G v ∈ V G , where ε \varepsilon ε is treated as an additional label. For ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 , we define
W L ℓ ( G , c , v ) = HASH ( W L ℓ − 1 ( G , c , v ) , { { W L ℓ − 1 ( G , c , w ) : w ∈ N G ( v ) } } ) , \mathrm{WL}^{\ell}(G,c,v)=\operatorname{HASH}\left(\mathrm{WL}^{\ell-1}(G,c,v),\{\!\{\mathrm{WL}^{\ell-1}(G,c,w):w\in N_G(v)\}\!\}\right), WL ℓ ( G , c , v ) = HASH ( WL ℓ − 1 ( G , c , v ) , { { WL ℓ − 1 ( G , c , w ) : w ∈ N G ( v )} } ) ,
where HASH is injective and shared across graphs. We denote the resulting multiset of labels by
W L ℓ ( G , c ) = { { W L ℓ ( G , c , v ) : v ∈ V G } } . \mathrm{WL}^{\ell}(G,c)=\{\!\{\mathrm{WL}^{\ell}(G,c,v):v\in V_G\}\!\}. WL ℓ ( G , c ) = { { WL ℓ ( G , c , v ) : v ∈ V G } } .
Two partially colored graphs are distinguished by 1-WL if these multisets differ at some iteration. We say that ( G , c ) (G,c) ( G , c ) is identified by 1-WL if it is distinguished from every nonisomorphic partially colored graph.
Since the partition induced by the 1-WL labels is refined at every iteration, it eventually stabilizes. We refer to the resulting label of a node as its stable 1-WL label. Two rooted partially colored graphs ( G , c , u ) (G,c,u) ( G , c , u ) and ( G ′ , c ′ , u ′ ) (G',c',u') ( G ′ , c ′ , u ′ ) have the same stable rooted 1-WL type if u u u and u ′ u' u ′ receive the same stable 1-WL label when color refinement is run with a common labeling scheme. An uncolored graph G G G is amenable if ( G , c ε ) (G,c_\varepsilon) ( G , c ε ) is identified by 1-WL, where c ε c_\varepsilon c ε denotes the empty coloring.
We first assess that the color-equivariant MLPs used by SCONE can realize arbitrary equivariant functions on finite sets.
Lemma 3. Let X ⊆ R k × d \mathcal{X}\subseteq\mathbb{R}^{k\times d} X ⊆ R k × d be finite and closed under row permutations, and let F : X → R k × p F:\mathcal{X}\to\mathbb{R}^{k\times p} F : X → R k × p be S k S_k S k -equivariant. Then F F F can be realized on X \mathcal{X} X by a finite-width ReLU network whose linear layers have the form L ( H ) [ i ] = W s e l f H [ i ] + W a l l ∑ j = 1 k H [ j ] + b L(H)[i]=W_{\mathrm{self}}H[i]+W_{\mathrm{all}}\sum_{j=1}^{k}H[j]+b L ( H ) [ i ] = W self H [ i ] + W all ∑ j = 1 k H [ j ] + b .
Proof. We first use the fact that a ReLU MLP can realize any function on a finite set. Indeed, for distinct vectors a 1 , … , a m a_1,\ldots,a_m a 1 , … , a m , choose w w w such that the scalars w ⊤ a 1 , … , w ⊤ a m w^\top a_1,\ldots,w^\top a_m w ⊤ a 1 , … , w ⊤ a m are distinct. A piecewise-linear function can interpolate arbitrary prescribed values at these points, and every such function is representable by a one-hidden-layer ReLU network.
Let A = { a 1 , … , a m } \mathcal{A}=\{a_1,\ldots,a_m\} A = { a 1 , … , a m } be the set of all rows occurring in matrices in X \mathcal{X} X . Using the preceding fact, construct a row-wise ReLU MLP ψ \psi ψ such that ψ ( a ℓ ) = e ℓ \psi(a_\ell)=e_\ell ψ ( a ℓ ) = e ℓ . For H ∈ X H\in\mathcal{X} H ∈ X and i ∈ [ k ] i\in[k] i ∈ [ k ] , define
z ( H , i ) = ψ ( H [ i ] ) ∥ ∑ j = 1 k ψ ( H [ j ] ) z(H,i)=\psi(H[i])\left\Vert\sum_{j=1}^{k}\psi(H[j])\right. z ( H , i ) = ψ ( H [ i ]) j = 1 ∑ k ψ ( H [ j ])
The second component records the multiplicity of every row type in H H H .
If z ( H , i ) = z ( H ′ , i ′ ) z(H,i)=z(H',i') z ( H , i ) = z ( H ′ , i ′ ) , then H [ i ] = H ′ [ i ′ ] H[i]=H'[i'] H [ i ] = H ′ [ i ′ ] and H , H ′ H,H' H , H ′ have the same multiset of rows. Hence there exists τ ∈ S k \tau\in S_k τ ∈ S k such that H ′ = P τ H H'=P_\tau H H ′ = P τ H and i ′ = τ ( i ) i'=\tau(i) i ′ = τ ( i ) . Equivariance gives F ( H ′ ) [ i ′ ] = F ( H ) [ i ] F(H')[i']=F(H)[i] F ( H ′ ) [ i ′ ] = F ( H ) [ i ] . Therefore, the assignment ρ ( z ( H , i ) ) = F ( H ) [ i ] \rho(z(H,i))=F(H)[i] ρ ( z ( H , i )) = F ( H ) [ i ] is well defined on the finite set of pointed signatures. Another row-wise ReLU MLP realizes ρ \rho ρ exactly. Then, we have that
N ( H ) [ i ] = ρ ( ψ ( H [ i ] ) ∥ ∑ j = 1 k ψ ( H [ j ] ) ) N(H)[i] = \rho\left(\psi(H[i]) \mathbin\Vert\sum_{j=1}^{k}\psi(H[j])\right) N ( H ) [ i ] = ρ ( ψ ( H [ i ]) ∥ j = 1 ∑ k ψ ( H [ j ]) )
satisfies N ( H ) = F ( H ) N(H) = F(H) N ( H ) = F ( H ) on X \mathcal{X} X . Both ψ \psi ψ and ρ \rho ρ are implemented with W a l l = 0 W_{\mathrm{all}} = 0 W all = 0 , while the intermediate concatenation is one linear layer of the required form. Thus N N N has the stated S k S_k S k -equivariant architecture.
Lemma 4. For fixed n n n and k k k , there exist a depth, a width, and a parameter setting of SCONE such that the score predictor can realize any S k S_k S k -equivariant scoring rule on the finite set of stable rooted 1-WL types occurring in partially colored graphs with at most n n n nodes.
Proof. For fixed n n n and k k k , only finitely many 1-WL labels and neighborhood multisets can occur. The initialization of SCONE can be chosen to give distinct, S k S_k S k -equivariant representations to the initial node labels.
Suppose that the embeddings after layer ℓ − 1 \ell- 1 ℓ − 1 distinguish all ( ℓ − 1 ) (\ell- 1) ( ℓ − 1 ) -round 1-WL labels. Since every degree is at most n − 1 n - 1 n − 1 , the embeddings can be chosen so that their sums uniquely determine all multisets of at most n − 1 n - 1 n − 1 neighboring labels. There are only finitely many such multisets. Lemma 3 therefore allows the equivariant update MLP to map each pair consisting of a node embedding and its neighborhood aggregate to a distinct equivariant code for the corresponding ℓ \ell ℓ -round 1-WL label.
LayerNorm and the residual connections do not affect this finite-set construction. With sufficiently large width, choose the update codes orbit by orbit so that every color slot has zero mean and the same nonzero variance. The codes can be chosen generically so that adding the residual embeddings and summing the resulting node embeddings introduces no unintended collisions among the finitely many inputs under consideration. The update MLP realizes these normalized codes by Lemma 3. Shared per-slot LayerNorm preserves them up to its learnable affine transformation, which can absorb the normalization constant, and the residual term produces the chosen next-layer embeddings.
Induction therefore shows that sufficiently many message-passing layers distinguish all stable rooted 1-WL types occurring on graphs with at most n n n nodes. Finally, an equivariant readout of sufficient width realizes any prescribed S k S_k S k -equivariant scoring rule on this finite set of types.
We next record the closure of identification under refinements of the initial coloring. Throughout the remainder of the proof, partially colored graphs are regarded as vertex-colored graphs, with ε \varepsilon ε as an additional color, and all automorphisms and fractional automorphisms are required to preserve these colors. The definitions and implications from amenability to compactness and the Godsil property extend to vertex-colored graphs ([6 ] ). In particular, every partially colored graph identified by 1-WL is compact and Godsil.
Lemma 5. Let ( G , c ) (G,c) ( G , c ) be a partially colored graph identified by 1-WL, and let c ′ c' c ′ be a refinement of c c c . Then ( G , c ′ ) (G,c') ( G , c ′ ) is also identified by 1-WL.
Proof. Suppose that ( G , c ′ ) (G,c') ( G , c ′ ) and ( G ′ , d ′ ) (G',d') ( G ′ , d ′ ) are not distinguished by 1-WL. Since c ′ c' c ′ refines c c c , there exists a map ρ \rho ρ such that c = ρ ∘ c ′ c = \rho\circ c' c = ρ ∘ c ′ . Applying the same coarsening to d ′ d' d ′ , let d = ρ ∘ d ′ d = \rho\circ d' d = ρ ∘ d ′ . The partially colored graphs ( G , c ) (G,c) ( G , c ) and ( G ′ , d ) (G',d) ( G ′ , d ) are also indistinguishable by 1-WL. Since ( G , c ) (G,c) ( G , c ) is identified by 1-WL, there exists an isomorphism φ \varphi φ between them.
We use φ \varphi φ to transport d ′ d' d ′ to a refinement d ~ ′ \widetilde{d}' d ′ of c c c on G G G , defined by d ~ ′ ( u ) = d ′ ( φ ( u ) ) \widetilde{d}'(u) = d'(\varphi(u)) d ′ ( u ) = d ′ ( φ ( u )) . The 1-WL equivalence of ( G , c ′ ) (G,c') ( G , c ′ ) and ( G ′ , d ~ ′ ) (G',\widetilde{d}') ( G ′ , d ′ ) gives a fractional isomorphism X X X ([6 ] ). Since both colorings refine c c c , the matrix X X X is also a fractional automorphism of ( G , c ) (G,c) ( G , c ) . Since ( G , c ) (G,c) ( G , c ) is compact because it is identified by 1-WL. We may therefore write X = ∑ t α t P π t X = \sum_t \alpha_t P_{\pi_t} X = ∑ t α t P π t , where α t ≥ 0 \alpha_t \ge0 α t ≥ 0 , ∑ t α t = 1 \sum_t \alpha_t = 1 ∑ t α t = 1 , and each π t \pi_t π t is an automorphism of ( G , c ) (G,c) ( G , c ) .
Since X X X is a fractional isomorphism between the two refinements, X u v = 0 X_{uv} = 0 X uv = 0 whenever c ′ ( u ) ≠ d ~ ′ ( v ) c'(u) \ne\widetilde{d}'(v) c ′ ( u ) = d ′ ( v ) . All coefficients in the decomposition of X X X are nonnegative. Therefore, every π t \pi_t π t with α t > 0 \alpha_t > 0 α t > 0 satisfies c ′ ( u ) = d ~ ′ ( π t ( u ) ) c'(u) = \widetilde{d}'(\pi_t(u)) c ′ ( u ) = d ′ ( π t ( u )) for every u ∈ V G u \in V_G u ∈ V G . Such a π t \pi_t π t is an isomorphism between ( G , c ′ ) (G,c') ( G , c ′ ) and ( G , d ~ ′ ) (G,\widetilde{d}') ( G , d ′ ) . Composing it with φ \varphi φ gives an isomorphism between ( G , c ′ ) (G,c') ( G , c ′ ) and ( G ′ , d ′ ) (G',d') ( G ′ , d ′ ) . Hence ( G , c ′ ) (G,c') ( G , c ′ ) is identified by 1-WL.
We now use the assumption that distinct underlying graphs in the family have distinct universal covers [38 ] . Importantly, this assumption concerns the uncolored graphs rather than the initial instances or their subsequent partial colorings.
Lemma 6 (Rooted types in a cover-separated family). Let K \mathcal{K} K be a collection of connected amenable graphs such that no two nonisomorphic graphs in K \mathcal{K} K have isomorphic universal covers. Let G , G ′ ∈ K G,G' \in\mathcal{K} G , G ′ ∈ K , let c , c ′ c,c' c , c ′ be arbitrary partial colorings of G , G ′ G,G' G , G ′ , and let u ∈ V G u \in V_G u ∈ V G and u ′ ∈ V G ′ u' \in V_{G'} u ′ ∈ V G ′ . If u u u and u ′ u' u ′ have the same stable 1-WL label, then ( G , c , u ) (G,c,u) ( G , c , u ) and ( G ′ , c ′ , u ′ ) (G',c',u') ( G ′ , c ′ , u ′ ) are isomorphic as rooted partially colored graphs.
Proof. The colorings c c c and c ′ c' c ′ refine the empty colorings of the amenable graphs G G G and G ′ G' G ′ . Hence Lemma 5 shows that ( G , c ) (G,c) ( G , c ) and ( G ′ , c ′ ) (G',c') ( G ′ , c ′ ) are identified by 1-WL.
Equality of the stable labels of u u u and u ′ u' u ′ implies that their rooted color-labeled universal covers are isomorphic [38 ] . Forgetting the color labels gives isomorphic universal covers of the underlying graphs G G G and G ′ G' G ′ . The assumption on K \mathcal{K} K therefore implies that G G G and G ′ G' G ′ are isomorphic. In particular, ∣ V G ∣ = ∣ V G ′ ∣ |V_G| = |V_{G'}| ∣ V G ∣ = ∣ V G ′ ∣ .
The isomorphic rooted universal covers induce corresponding stable cells V 1 , … , V m V_1,\ldots,V_m V 1 , … , V m and V 1 ′ , … , V m ′ V'_1,\ldots,V'_m V 1 ′ , … , V m ′ with the same equitable-quotient parameters. Let d p q d_{pq} d pq denote the number of neighbors in V q V_q V q of a node in V p V_p V p . We have
∣ V p ∣ d p q = ∣ V q ∣ d q p and ∣ V p ′ ∣ d p q = ∣ V q ′ ∣ d q p . |V_p|d_{pq} = |V_q|d_{qp} \qquad\text{and}\qquad|V'_p|d_{pq} = |V'_q|d_{qp}. ∣ V p ∣ d pq = ∣ V q ∣ d q p and ∣ V p ′ ∣ d pq = ∣ V q ′ ∣ d q p .
Since the graphs are connected, their equitable quotients are connected. These equations therefore determine the cell sizes up to a common positive factor. Hence there exists λ > 0 \lambda> 0 λ > 0 such that ∣ V p ′ ∣ = λ ∣ V p ∣ |V'_p| = \lambda|V_p| ∣ V p ′ ∣ = λ ∣ V p ∣ for every p p p . Summing over the cells and using ∣ V G ∣ = ∣ V G ′ ∣ |V_G| = |V_{G'}| ∣ V G ∣ = ∣ V G ′ ∣ gives λ = 1 \lambda= 1 λ = 1 .
Thus ( G , c ) (G,c) ( G , c ) and ( G ′ , c ′ ) (G',c') ( G ′ , c ′ ) have the same stable 1-WL label multiset and are not distinguished by 1-WL. Since they are identified by 1-WL, there is a color-preserving isomorphism φ \varphi φ from ( G , c ) (G,c) ( G , c ) to ( G ′ , c ′ ) (G',c') ( G ′ , c ′ ) .
The nodes φ ( u ) \varphi(u) φ ( u ) and u ′ u' u ′ have the same stable 1-WL label in ( G ′ , c ′ ) (G',c') ( G ′ , c ′ ) . Moreover, every graph identified by 1-WL is Godsil [6 ] , so each stable cell is an orbit of a subgroup of color-preserving automorphisms. There is therefore an automorphism α \alpha α of ( G ′ , c ′ ) (G',c') ( G ′ , c ′ ) such that α ( φ ( u ) ) = u ′ \alpha(\varphi(u)) = u' α ( φ ( u )) = u ′ . The composition α ∘ φ \alpha\circ\varphi α ∘ φ is an isomorphism from ( G , c ) (G,c) ( G , c ) to ( G ′ , c ′ ) (G',c') ( G ′ , c ′ ) that maps u u u to u ′ u' u ′ .
We can now prove the main expressivity result.
Theorem 3. Let n , k ∈ N n,k \in\mathbb{N} n , k ∈ N , and let G \mathcal{G} G be a cover-amenable family of graphs with at most n n n nodes. There exists a parameter setting of SCONE s.t. every k k k -colorable ( G , c 0 ) (G,c_0) ( G , c 0 ) with G ∈ G G \in\mathcal{G} G ∈ G can be solved.
Proof. For an uncolored node u u u , let K u K_u K u denote its connected component, let c u c_u c u denote the restriction of c c c to K u K_u K u , and let c u u ← i c_u^{u\leftarrow i} c u u ← i be obtained by assigning color i i i to u u u . Define the target score function by
s ( G , c , u ) i = { 1 , if ( K u , c u u ← i ) is extendable , 0 , otherwise. s(G,c,u)_i =
\begin{cases}
1, & \text{if } (K_u,c_u^{u\leftarrow i}) \text{ is extendable},\\
0, & \text{otherwise.}
\end{cases} s ( G , c , u ) i = { 1 , 0 , if ( K u , c u u ← i ) is extendable , otherwise.
By Lemma 6, the stable rooted 1-WL type of u u u determines the rooted partially colored component ( K u , c u ) (K_u,c_u) ( K u , c u ) up to isomorphism. Consequently, the target score function is well defined on stable rooted 1-WL types. It is also S k S_k S k -equivariant, since permuting the color labels maps proper completions to proper completions with the same permutation applied. Lemma 4 therefore gives a single parameter setting of SCONE that realizes this scoring rule.
Consider an extendable state ( G , c ) (G,c) ( G , c ) and any uncolored node u u u . A proper completion c ∗ c^* c ∗ of c c c assigns some color i = c ∗ ( u ) i = c^*(u) i = c ∗ ( u ) to u u u . Its restriction to K u K_u K u shows that ( K u , c u u ← i ) (K_u,c_u^{u\leftarrow i}) ( K u , c u u ← i ) is extendable. Hence the maximum score at u u u is 1, and every maximizing color preserves the extendability of the component containing u u u . The other components are unchanged, so the complete state also remains extendable.
The decoder may therefore select any uncolored node and break every color tie arbitrarily. Each step preserves extendability and colors one additional node. By induction, decoding reaches a complete extendable state, which is a proper coloring extending c 0 c_0 c 0 .
A sufficient condition for Theorem 3 is that every connected component be 1-WL-discrete [6 ] . Such components are amenable, and two of them with isomorphic universal covers are necessarily isomorphic. This condition holds with high probability in the dense Erdős–Rényi model [8 ] . Moreover, the proof gives the stronger conclusion that every decoding trajectory solves the instance, independently of node selection and tie-breaking.
Experimental setup
In this section, we discuss additional details about the experimental setup, including dataset preparation, details on baselines, on our implementation of SCONE, and on the computing infrastructure.
Datasets
Sudoku instances. We evaluate on five collections of 9 × 9 9 \times9 9 × 9 Sudoku puzzles. The sudoku_satnet and sudoku_rrn datasets are taken from SATNet [69 ] and Recurrent Relational Networks [50 ] , respectively. We additionally use sudoku_17, a collection of non-equivalent puzzles with only 17 clues,1 and sudoku_top1465, a collection of 1,465 particularly difficult puzzles.2 Finally, we use sudoku_extreme, using the splits introduced by Davis et al. [19 ] (1000 training instances and 4000 test instances), which is the most challenging public Sudoku benchmark. We independently divide sudoku_17 and sudoku_satnet into 70%/15%/15% training, validation, and test splits. In contrast, sudoku_rrn and sudoku_top1465 are used only for testing. The optimal solutions used for training are either provided in the original data, or are obtained with an exact ILP solver.
Register-allocation instances. We curate this benchmark from Appel and George’s collection of 27,922 register-interference graphs [23 ] generated by Standard ML of New Jersey while compiling itself.3 We parse the data into undirected graphs, remove self-loops, and remap vertex identifiers to a contiguous range. The original format specifies K = 21 K = 21 K = 21 available registers and assumes an implicit clique (which we do not materialize) of K K K precolored register nodes. We also discard the move edges, which encode preferences for assigning two nodes the same register rather than interference constraints. We retain graphs with ∣ V G ∣ ≥ 4 |V_G| \ge4 ∣ V G ∣ ≥ 4 and filter out duplicated graphs. Finally, we compute a greedy clique lower bound and retain instances whose bound lies between 3 and 21, filtering graphs that are essentially trivially colourable or graphs whose clique lower bound already exceeds the original K = 21 K = 21 K = 21 available registers budget. The resulting 8999 instances contain no initially assigned colors and are all 21-colorable (or better). The optimal solutions used for training are obtained with an exact ILP solver.
Toronto examination timetabling. We use version I of the Carter–Laporte–Lee Toronto benchmark,4 see Carter et al. [16 ] . Each file records the exams and their enrollments, and the exams taken by each student. We construct an undirected conflict graph in which vertices represent exams and two exams are adjacent if some student takes both. Then, the exams taken by each student induce a clique. We adopt the uncapacitated minimum-timeslot formulation, ignoring room capacities and proximity costs, so a proper coloring represents a feasible timetable. Duplicate entries in each student’s exam list are removed before constructing edges, while isolated exams and the original exam numbering are retained. We set k k k to the best-known feasible number of colors for each instance as reported in Qu et al. (2009, Table 11), and these values are upper bounds on the chromatic number rather than certified optima. To reduce the size of the graphs without affecting the validity of the instance, we apply the standard k k k -core reduction, iteratively removing vertices of degree less than k k k , as these can be colored trivially. We partition the thirteen Toronto instances according to their original size before preprocessing. The four smallest instances, hec-s-92, sta-f-83, yor-f-83, and ute-s-92, form the validation set and are used only to select the decoding configuration. The remaining instances form the test set, which we divide into the smaller instances ear-f-83, tre-s-92, lse-f-91, and kfu-s-93, and the large instances rye-s-93, car-f-92, uta-s-92, car-s-91, and pur-s-93. No Toronto instance is used for training, as we apply the same synthetically trained model throughout.
Queen graphs. For each p p p , queens_p is the queen graph of a p × p p \times p p × p chessboard, with one node per square and edges connecting squares in the same row, column, or diagonal [65 ] . A proper coloring therefore partitions the board into sets of mutually non-attacking queens. We use queens_7 exclusively for validation and reserve queens_8, queens_9, and queens_10 for testing. None of these instances is used for training, and we apply the same synthetically trained model throughout.
Structured graphs. Alongside the application benchmarks, we evaluate on synthetic families with chromatic numbers known exactly by construction. These instances are straightforward for classical algorithms but isolate potential failure modes of learned colorers. The cycle graphs contain hundreds of nodes, with equal numbers of even and odd cycles requiring two and three colors, respectively, and thus test long-range parity reasoning. The grid graphs are 4-regular bipartite lattices with hundreds of nodes. The complete graphs are K n K_n K n for 32 ≤ n ≤ 64 32 \le n \le64 32 ≤ n ≤ 64 and admit no slack, since every vertex must receive a distinct color.
Synthetic training data. In Section 5.3, the results for SCONE are obtained using a single generalist checkpoint trained exclusively on synthetic graphs, and no benchmark instance is used for training. We generate graphs with planted proper colorings by partitioning the nodes into color classes and adding edges only between classes. The dataset spans diverse graph sizes, color budgets, densities, and degree distributions, combining random, preferential-attachment, and clique-augmented constructions. In particular, it contains 10000 graphs, split into 8000/1000/1000 training, validation, and test instances. We draw n n n log-uniformly from [ 20 , 200 ] [20, 200] [ 20 , 200 ] and k k k uniformly from [ 3 , min ( 30 , n ) ] [3, \min(30,n)] [ 3 , min ( 30 , n )] . Graph families are sampled as uniform-edge, preferential-attachment, and clique-augmented constructions with equal probabilities. We retain connected candidates with an edge between every pair of planted color classes for which the generator’s deterministic DSATUR requires at least k + 1 k+1 k + 1 colors. This provides valid supervision while preventing the training set from being dominated by instances that a standard constructive heuristic solves immediately. Importantly, the planted proper coloring is generated jointly with each graph, providing ground-truth supervision without requiring an additional graph-coloring solve, which would be computationally expensive.
Baselines
Greedy, DSATUR and RLF. We adapt all three heuristics to the fixed-budget setting considered in this work. Greedy [71 ] processes nodes in a fixed order, while DSATUR [13 ] repeatedly selects an uncolored node with the largest number of distinct colors among its colored neighbors, breaking ties by residual degree. RLF [41 ] constructs one color class at a time by greedily building a maximal independent set. In their classical formulations, all three methods assign the first available color and introduce a new color whenever all existing colors are blocked; they therefore always return a proper coloring, with the number of colors used serving as their output. In our setting, by contrast, the palette size k k k is fixed. We restrict all three methods to these k k k colors and, whenever every color already appears in the selected node’s neighborhood, assign a color that conflicts with the fewest colored neighbors. Thus, the methods always return a complete coloring, which may be improper and can be evaluated using the same solved-instance and monochromatic-edge metrics as the learning-based methods. On feasible bipartite, chordal, and complete graphs, where DSATUR is exact, the palette cap does not bind and this modification leaves its classical behavior unchanged.
ILP. We use a standard integer linear programming (ILP) formulation with binary variables assigning one of the k k k colors to each node and auxiliary variables indicating monochromatic edges. The objective minimizes the total number of monochromatic edges, with initial colors enforced as fixed assignments. The ILP uses color-symmetry-breaking constraints to ensure an efficient representation. We solve the resulting problem using Gurobi [26 ] .
ACE. ACE (Lecoutre, 2023) is a frontier general-purpose constraint solver for finite-domain constraint-satisfaction problems (CSP). We represent each node by an integer variable with do main { 1 , … , k } \{1,\ldots,k\} { 1 , … , k } , restrict precolored nodes to singleton domains, and impose a binary inequality constraint for every edge. We run ACE with its default search configuration and the same dataset-specific time limits as the ILP baseline. Since ACE searches directly for a feasible coloring, it either returns a proper coloring or terminates without a solution within the time limit. Therefore, either its Mono% is 0 or is not defined. To provide ACE with the most favorable comparison, we report only its internal solve time, excluding JVM startup and instance-loading overhead, which would add an additional 0.5s per instance.
PI-SAGE and ROS. Both methods optimize a separate GNN from scratch on each test instance using a relaxed coloring objective, and then round its predictions to obtain a discrete coloring. Thus, neither method uses a pretrained checkpoint or requires a training split. For PI-SAGE ([59 ] ), we use two mean-aggregating SAGEConv layers with hidden dimension 32 and minimize the soft Potts objective ∑ u , v ∈ E ⟨ p u , p v ⟩ \sum_{u,v\in E}\langle p_u,p_v\rangle ∑ u , v ∈ E ⟨ p u , p v ⟩ . We optimize with learning rate 10 − 4 10^{-4} 1 0 − 4 for at most 100,000 epochs, with tolerance 10 − 4 10^{-4} 1 0 − 4 and early-stopping patience 1,000, and retain the best argmax coloring encountered during optimization. For ROS ([54 ] ), we use the authors’ two-layer GraphConv architecture with GraphNorm and hidden dimension 100, and optimize the QUBO objective tr ( X W X T ) \operatorname{tr}(XWX^{\mathsf{T}}) tr ( X W X T ) with learning rate 10 − 2 10^{-2} 1 0 − 2 for at most 10,000 epochs, using tolerance 10 − 2 10^{-2} 1 0 − 2 and patience 100. We obtain discrete solutions by drawing 100 multinomial samples and retaining the best coloring. All hyperparameters follow the authors’ published defaults. Our implementations faithfully port PI-SAGE from DGL to PyG and reproduce the original ROS GCN.
AnyCSP. AnyCSP ([63 ] ) is a pretrained anytime solver for constraint-satisfaction problems. We train its graph-coloring model using the authors’ provided code and retain the default num_boost=8, which replicates each instance within a batch to perform eight parallel search restarts. Since the original checkpoint was not released, we compare our retrained model with the runtimes reported by the authors as a sanity check. They report 5 to 17 seconds for queen graphs of sizes 8 to 10, while our model solves the same sizes in 0.4 to 11 seconds. Although runtimes across different hardware are not directly comparable, these results suggest that our checkpoint is comparable to, and potentially stronger than, the original. Training takes more than 24 hours on an H200 GPU. We run AnyCSP with a time limit of 5 seconds on Sudokus to limit the runtime, and with a time limit of 30s per instance otherwise, albeit sometimes it exceeds this timelimit. Note that this limit is only reached on some large toronto instances and on queens_10_10, and this time limit is comfortably higher than the time used by Scone. The original method does not support fixed colors. We represent each pinned node using a singleton domain, making clue violations impossible, rather than introducing unary constraints that the solver could violate and whose penalties would be mixed with edge violations in its objective. Since the released model was not trained on instances with pinned nodes, we retrain it on sudoku_17 and on sudoku_extreme using the authors’ training procedure.
ConsFormer. ConsFormer ([73 ] ) is a self-supervised transformer that iteratively refines a complete assignment. Since no pretrained checkpoints are provided, we train all models ourselves. We use a candidate pool of one, corresponding to the standard model in the authors’ main experiments; we do not report the optional multi-start extension, for which additional candidates trade against refinement iterations under a fixed time budget. Following the authors’ ablations, we use masked relative positional encodings rather than the repository default of no relative encoding. The remaining settings follow the published configurations: seven layers, three attention heads, hidden dimension 128, the ABSE loss, and 5000 training epochs. For Sudoku, we use ape_dim=2 and threshold 0.5; for general coloring, we use ape_dim=1 and threshold 0.7.
We formulate Sudoku as graph coloring rather than using ConsFormer’s native all-different constraints. Each puzzle is represented as an 81-node, 20-regular constraint graph, with edges encoding pairwise inequalities and clues fixed as one-hot assignments. We retain the two-dimensional Sudoku positional encoding, so the model receives the grid geometry while using the same constraint formulation and evaluation metrics as the other coloring datasets. The native all-different formulation yields only marginally better results. We train the model on sudoku_satnet as in the original paper, as training on sudoku_17 yields significantly worse results both in terms of training loss and of validation solution quality.
RelCol. RelCol ([70 ] ) uses deep Q-learning and a GNN to learn a node ordering for greedy coloring, minimizing the number of colors. We adapt it to a fixed palette by retaining its first k k k color classes and assigning each remaining node its least-conflicting color among them. At inference, we repeat episodes under the same nominal per-graph budgets as ANYCSP: 5 s on registers, Sudoku and cycles, and 30 s on Toronto, queens and DIMACS. We retain the best coloring and stop once a proper k k k -coloring is found. On four of the five large Toronto instances, a single episode already exceeds the budget. We therefore report one episode and its full runtime, reaching approximately 3200 s on pur-s-93.
LDT. The Lattice Deduction Transformer (LDT) (Davis et al. [19 ] ) combines a recurrent Transformer with stochastic search over a lattice of candidate assignments. It cannot be applied directly to general graph-coloring instances and is therefore included only in the Sudoku experiments. Since no checkpoint is available, we train the model using the authors' unmodified implementation. We follow the configuration from their Table 1, using 4000 training steps while retaining all other defaults. At inference, we use the default 64 parallel chains and at most 1000 search rounds. We verified that the training and test instances exactly match the split used for SCONE.
TRM. The Tiny Recursive Model (TRM) (Jolicoeur-Martineau [33 ] ) is a recurrent Transformer-based refinement model. It cannot be applied directly to general graph-coloring instances and is therefore included only in the Sudoku experiments. Since no checkpoint is available, we train the official model on the same 1000 puzzles used by SCONE and LDT, following the authors' sudoku_extreme_1k_aug_1k configuration with 50000 training steps and 1000 augmentations per puzzle. The model and optimization procedure are unchanged. At inference, the number of refinement steps is controlled by n_supervision. We report 128 steps, the largest setting within the matched runtime budget and eight times the 16 steps used during training, thereby giving TRM a favorable test-time compute allowance.
Setup for Scone
Architecture and training. We implement SCONE in PyTorch Geometric (Fey & Lenssen [21 ] ). Following § 4 , each node maintains a k × d k \times d k × d representation with one slot per color, and all updates are equivariant to permutations of these slots. Unless otherwise stated, we use L = 10 L = 10 L = 10 message-passing layers, hidden dimension d = 128 d = 128 d = 128 , and the degree-normalized aggregation
∑ v ∈ N ( u ) H v ∣ N ( u ) ∣ \sum_{v \in N(u)} \frac{H_v}{\sqrt{|N(u)|}} v ∈ N ( u ) ∑ ∣ N ( u ) ∣ H v
, as it retains degree information while being stable across scales. See Section E for a comparison with different depths and widths. We use LayerNorm (Ba et al. [7 ] ) and residual connections (He et al. [28 ] ), as they have been shown to make training more stable (Luo et al. [45 ] ).
We generate training states by sampling a masking fraction uniformly for each graph and hiding the corresponding fraction of non-fixed colors from a target solution. Clues provided with the instance are retained. We train against the permutation-aware targets of § 4.2 using AdamW (Kingma & Ba [37 ] ; ); Loshchilov & Hutter [44 ] ) with learning rate 10 − 3 10^{-3} 1 0 − 3 , weight decay 10 − 5 10^{-5} 1 0 − 5 , batch size 64, and a cosine schedule with five warm-up epochs. We train for 50 epochs on sudoku_17 and registers, which takes less than 30 minutes, for 300 epochs on the synthetic data, which takes roughly 6 hours, and for 2000 epochs on sudoku_extreme, given its small size, which takes roughly 2.5 hours. We select the checkpoint that maximizes the fraction of solved instances (Solved%), and in case of ties the ones that minimizes the fraction of monochromatic edges (Mono%) on validation instances.
Inference strategies. For beam search, each state scores all k k k color slots for the selected node. After removing children equivalent under S k S_k S k color permutations, we retain the global top B B B states across the full candidate set. There is no per-parent quota, so a state may contribute multiple children or none. Beam states are ranked by the cumulative sum of assignment log-probabilities, while forced assignments contribute no score. Ensembling uses E E E independent replicas, with replica r r r initialized from the r r r -th highest-degree uncolored node. The final output is the coloring with the fewest monochromatic edges across all beams or replicas.
Adaptive test-time scaling. Our decoder has two width axes: a beam size B B B within each decoding replica and a number E E E of independent replicas, for total width W = B E W = B E W = B E . These axes are not interchangeable. Additional replicas never compete with previous ones, whereas increasing the beam size changes which partial colorings are retained and is therefore not monotone. We use the validation split only to determine whether additional width should be allocated to beams, replicas, or a mixture of both, see Section E for results.
At test time, each graph (or batch of graphs) is first decoded at the smallest width. If the returned coloring is proper, decoding stops. Otherwise, the width is doubled according to the selected allocation rule and the graph is decoded again, up to the fixed cap. Since correctness can be verified directly by counting monochromatic edges, this stopping rule requires neither ground-truth colorings nor validation labels. This adaptive scaling puts SCONE in the same broad category as ANYCSP, CONSFORMER, LDT, and TRM, which all employ anytime-style inference procedures that terminate either upon reaching a search limit or upon solving the instance at hand. We retain the best coloring found across all attempted widths because a wider beam may discard a trajectory completed by a narrower one. The reported decoding cost is the total time consumed across all rungs entered by each graph, averaged over the benchmark. In the experiments, we set a maximum width of 512 to avoid out-of-memory errors, but this value is reached only sporadically.
Architectures for ablations. All equivariance ablations use the same training configuration as the full model. The non-equivariant variant embeds a one-hot encoding of the current color and uses MLPs as update functions, while retaining the same message-passing depth and aggregation. We evaluate every variant using greedy decoding, i.e. setting B = 1 B = 1 B = 1 , E = 1 E = 1 E = 1 , with forced-assignment propagation disabled, so that additional search does not mask differences between the models.
Computing infrastructure
The experiments are run on a cluster equipped with AMD EPYC 9374F CPUs and NVIDIA H200 GPUs (143 GB). The code is based on PyTorch 2.11 and PyTorch-Geometric 2.8, with CUDA 12.8.
Hyperparameter studies
In this section, we discuss the sensitivity of SCONE to its hyperparameters. In particular, we analyze the importance of the node selection strategy, the effect of using E E E ensembles or B B B beams for beam search on different datasets, as well as the tradeoff between solution quality and inference times as the embedding dimension d d d , the number of GNN layers L L L and the decoding width W = B E W = B E W = B E . Importantly, all the following experiments are run exclusively on the validation splits, so that the selection of the best model configurations are not influenced by test set results.
We start by analyzing the effect of the node selection strategy. The simplest strategy is to just color the nodes in their natural order, i.e. the order in which the nodes are provided in input. By contrast, as described in § 4.3 , our decoder instead follows the common most-constrained-first (MCF) heuristic [27 ] from constraint satisfaction.
We randomly permute the input node order in every run and average over five repeats for Sudoku and registers. For queens_7 and Toronto, which contain fewer validation graphs, we use 20 repeats. Since at width 1 queens_7 cannot be solved, we use B = 8 B = 8 B = 8 beams. Figure 6 compares the validation Solved% for the two strategies, showing that the most-constrained-first performs consistently better than the natural order, confirming the validity of SCONE’s design.
Figure 6. Validation Solved% for coloring nodes in their natural order and in MCF order.
We next study how a fixed decoding width is allocated between an ensemble of E E E independent runs and beam width B B B . Figure 7 shows that, at total width W = B E = 8 W = B E = 8 W = B E = 8 , Sudoku consistently benefits more from beam search than from ensembling, while Toronto exhibits the opposite trend. Results on queens are noisier but also favor beams, while register allocation is nearly saturated across all mixtures, even at smaller widths. Based exclusively on these validation results, we use beams for Sudoku, queens, and registers, and ensembling for Toronto throughout the paper.
Figure 7. Validation Solved% for different ratios between independent runs E E E and beam width B B B .
Finally, we study how the embedding dimension d d d , the number of message-passing layers L \mathcal{L} L , and the decode width W W W affect solution quality and inference time. We focus on Sudoku and Toronto, which exhibit the clearest trends in the preceding hyperparameter studies. For both datasets, we retrain the model with d ∈ { 96 , 128 , 192 } d \in\{96, 128, 192\} d ∈ { 96 , 128 , 192 } while fixing L = 10 \mathcal{L} = 10 L = 10 , and with L ∈ { 5 , 10 , 15 } \mathcal{L} \in\{5, 10, 15\} L ∈ { 5 , 10 , 15 } while fixing d = 128 d = 128 d = 128 . These models are decoded at width W = 1 W = 1 W = 1 . We then vary W ∈ { 1 , 4 , 16 } W \in\{1, 4, 16\} W ∈ { 1 , 4 , 16 } while fixing d = 128 d = 128 d = 128 and L = 10 \mathcal{L} = 10 L = 10 , using beams for Sudoku and ensembles for Toronto. As in the main experiments, Sudoku is trained in-distribution, while Toronto is trained on synthetic graphs. All results are reported exclusively on the validation splits.
Figure 8. Validation Solved% and average inference times on sudoku_17 for different values of embedding dimension d d d , message-passing layers L \mathcal{L} L and beam width B B B .
Figures 8 and 9 show that both solution quality and inference time vary only marginally with d d d , although d = 128 d = 128 d = 128 achieves the best quality. Sudoku benefits from greater depth, while Toronto performs best at L = 10 \mathcal{L} = 10 L = 10 . As expected, inference time grows approximately linearly with L \mathcal{L} L , with a particularly noticeable effect on Toronto. Increasing the decode width consistently improves solution quality in these experiments, while also increasing inference time approximately linearly. Based on these results, we fix L = 10 \mathcal{L} = 10 L = 10 and d = 128 d = 128 d = 128 throughout, as they provide a good trade-off between solution quality and inference time across datasets. Tuning these values separately for each dataset could yield slightly better results but would require additional training.
Additional experimental results
In this section, we report some additional experimental results that were omitted from the main text for space reasons.
Figure 9. Validation Solved% and average inference times on toronto for different values of embedding dimension d d d , message-passing layers L \mathcal{L} L and ensemble size E E E .
Transfer across Sudokus. First, we evaluate SCONE across Sudoku benchmarks in a transfer-learning setting. In the main results, the model trained on sudoku_17 was evaluated in-distribution and transferred to sudoku_satnet, sudoku_rrn, and sudoku_top1465, while a separate model was trained and evaluated on sudoku_extreme. Here, we evaluate both checkpoints on all five datasets. We additionally consider a checkpoint trained on the training split of sudoku_satnet, which was used, e.g., in Xu et al. [73 ] .
Table 5 reports the results for the three checkpoints, decoded with up to B = 512 B = 512 B = 512 beams. The model trained on sudoku_satnet transfers least effectively, failing to solve every instance on several benchmarks and requiring on average wider beams, which then increases inference time. As expected, each checkpoint performs best on its training distribution, where it solves every instance with the lowest inference time. Under transfer, the models trained on sudoku_17 and sudoku_extreme perform similarly, although the former is slightly stronger, possibly because it was trained on more instances.
Table 5. Solution quality on Sudoku benchmarks with multiple checkpoints: Solved% (↑ \uparrow ↑ ) and inference time per graph (↓ \downarrow ↓ ).
Per-instance results. We then report the per-instance results for the Toronto timetabling and queens benchmarks. Each of these instances corresponds to a single graph, so pooling instances into one column, although necessary due to space constraints, averages over problems of substantially different difficulty. Tables 6, 7, and 8 decompose the three pooled columns of Table 4 into their constituent graphs. Since each column now represents one graph, Solved% denotes the fraction of 20 repeated runs that find a proper coloring, rather than the fraction of graphs solved.
Consistent with the pooled results, SCONE and ANYCSP are closely matched on the smaller Toronto instances, with each method holding a slight advantage on some graphs and falling behind on others. On the larger Toronto instances, SCONE consistently achieves both better solution quality and lower inference times. On queens, the two methods are essentially tied for sizes 8 and 9, while SCONE is faster for size 10.
Table 6. Per-instance breakdown of the results on toronto(small) instances. Solved% (↑ \uparrow ↑ ), Mono% (↓ \downarrow ↓ ) and inference time per graph (↓ \downarrow ↓ ).
Table 7. Per-instance breakdown of the results on toronto(large) instances. Solved% (↑ \uparrow ↑ ), Mono% (↓ \downarrow ↓ ) and inference time per graph (↓ \downarrow ↓ ).
Table 8. Per-instance breakdown of the results on queens (8–10) instances. Solved% (↑ \uparrow ↑ ), Mono% (↓ \downarrow ↓ ) and inference time per graph (↓ \downarrow ↓ ).
Synthetic structured graphs
Synthetic structured graphs. Finally, we report results on synthetic structured graphs to examine potential failure modes of the different methods. In addition to the cycle benchmarks presented in the main paper, we consider complete graphs with up to 64 nodes, regular bipartite grid graphs, a separate collection containing only even cycles, and the Mycielski graphs M 5 M_5 M 5 , M 6 M_6 M 6 , and M 7 M_7 M 7 . The latter are triangle-free despite having chromatic numbers 5, 6, and 7, respectively. As a stress test, SCONE uses width 1 with forced assignments disabled. Its performance therefore reflects the learned policy itself, without beam search, ensembling, or constraint propagation.
SCONE and the classical heuristics solve every instance. ANYCSP also solves all four families and is particularly fast on the sparse Mycielski graphs. However, it takes roughly an order of magnitude longer than SCONE on grids and even cycles. These connected bipartite graphs have an essentially unique 2-coloring up to color permutations and require consistency to be propagated over long distances, which may explain the additional search. CONSFORMER cannot be evaluated on the complete graphs because their palettes contain up to 64 colors, whereas its architecture does not support palette sizes beyond the maximum of 30 seen during training. Moreover, it can only solve roughly half of the grid graphs, and few even-size cycles. Finally, the relaxation-based methods frequently fail on grids and Mycielski graphs, and none solves any even cycle.
Additional baselines. Due to space constraints, we report some comparisons with three additional baselines here. Results are reported in Table 10 and Table 11 . CSO (Cat Swarm Optimization) [58 ] is a population-based metaheuristic without a learned component, alternating between local seeking moves and tracing moves guided by the best solution found. GBS [5 ] constructs color classes through GNN-guided extraction of large independent sets, while VCOLRL [2 ] uses reinforcement learning to assign colors to multiple vertices per step, reverting conflicting assignments. Since GBS and VCOLRL minimize the number of colors, we adapt them to our fixed palette by retaining their first k k k color classes and assigning each remaining node its least-conflicting color among them. All three methods receive the same nominal per-graph budgets as ANYCSP: 5 s on Sudoku and registers, and 30 s on Toronto and queens. VCOLRL repeats episodes within the budget, retains the best colouring, and stops once a proper k k k -colouring is found. GBS performs a single search per graph, capped at the budget. None of these methods solves an instance from Toronto or sudoku_17. GBS solves queens_8_8 in 35% of repeats and queens_9_9 in 5%.
Table 10. Solution quality of additional baselines on Sudoku-graph coloring.
Table 11. Solution quality of additional baselines on isolated instances and registers.
Additional datasets. Our main evaluations focus on graph instances drawn from practical applications. Here, we additionally evaluate on three DIMACS5 families: book graphs connecting characters that encounter one another, Erdős–Rényi DSJC graphs, and random le450 graphs with guaranteed k k k -colorings. On these graphs, we use the same synthetically-trained SCONE checkpoint used in Table 4 , and we use ensembling.
Table 12 reports the results on book graphs, where k k k is set to their chromatic number. These graphs are relatively easy to color, and SCONE solves 100% of them. However, for such simple instances, heuristics like DSATUR might be preferable, as they also solve them while being faster.
Table 12. Solution quality on book graphs: Solved% (↑ \uparrow ↑ ), Mono% (↓ \downarrow ↓ ) and inference time (↓ \downarrow ↓ ).
Table 13 reports the results on DSJC graphs, where k k k is set to the best-known feasible palette size. These graphs are much harder to solve compared to book graphs. SCONE solves DSJC125.1 and DSJC250.1 in all runs, but reaches a 20% solve rate on DSJC125.9. ANYCSP solves the latter consistently, while SCONE is faster and more reliable on DSJC250.1. None of the evaluated methods solves DSJC125.5.
Table 13. Solution quality on DSJC graphs: Solved% (↑), Mono% (↓) and inference time (↓).
Tables 14 and 15 report the results on le450 graphs, with the palette sizes set to k = 15 k=15 k = 15 and k = 25 k=25 k = 25 respectively. SCONE solves all 15-color instances, including le450_15c and le450_15d, where ANYCSP succeeds in only 5% of runs and all other reported baselines fail. For 25 colors, SCONE and several baselines consistently solve the a/b variants, while the c/d variants remain unsolved by all methods. Nevertheless, SCONE achieves the lowest monochromatic-edge rates on these two instances.
Table 14. Solution quality on le450_15 graphs: Solved% (↑), Mono% (↓) and inference time (↓).
Table 15. Solution quality on le450_25 graphs: Solved% (↑), Mono% (↓) and inference time (↓).
Searching for the best feasible palette size In all main experiments, SCONE takes the palette size k k k as input, as is natural in several applications with a fixed resource budget. This setting is also considered by ANYCSP and CONSFORMER, and is standard in CSP and ILP formulations of graph coloring. Here, we also consider the setting where k k k is not prescribed, and the goal is to obtain a coloring using as few colors as possible. Starting from a DSATUR coloring, we repeatedly attempt a proper coloring with one fewer color, stopping at the first failure and retaining the best proper coloring found. Retaining the best proper coloring makes this an anytime procedure.
For this experiment, we consider three hard instances, queens_10_10, DSJC250.1 and le450_15d, and use ANYCSP as a reference point, as it is the strongest neural baseline. Figure 10 compares 20 independent searches per method against cumulative wall-clock time. SCONE reaches the best-known color counts in every search: from 14 to 11 on queens_10_10, from 10 to 8 on DSJC250.1, and from 24 to 15 on le450_15d. Under the same search protocol, with a 30 s per-budget limit, ANYCSP reaches these counts only in 18 of 20 searches on each of the first two instances, taking slightly longer than SCONE. On le450_15d, only one of its searches reaches the 15 colors, while most runs can only reach a coloring with 16. Moreover, it takes significantly longer than SCONE.
Figure 10. Improving chromatic upper bounds from a DSATUR coloring. Curves show cumulative time to successive proper colorings over 20 independent searches. Dashed lines mark the best-known upper bounds χ \chi χ .
Infeasible palettes. While our training procedure and main experiments focus on producing proper colorings, we also examine the number of monochromatic edges when the available palette makes a proper coloring impossible. As a proof of concept, we consider register-interference graphs, where insufficient registers can necessitate spilling. To test at different levels of infeasibility, we set k = χ ( G ) − 1 k = \chi(G) - 1 k = χ ( G ) − 1 or k = ⌈ χ ( G ) / 2 ⌉ k = \lceil\chi(G)/2 \rceil k = ⌈ χ ( G ) /2 ⌉ and evaluate the resulting approximate colorings using Mono%. As reference points, we use ANYCSP with a timelimit of 1 s, which is reached on each instance, and our ILP formulation with a maximum timelimit of 5 s. Our ACE encoding searches for proper colorings and can certify infeasibility, but does not minimize monochromatic edges, so it is omitted from this comparison. We run SCONE with 256 replicas. On the easier k = χ ( G ) − 1 k = \chi(G) - 1 k = χ ( G ) − 1 , the ILP with a timelimit of 5 s certifies optimality on 97% of the graphs. Both SCONE and ANYCSP achieve Mono% values comparable to the ILP, with the former being slightly better than the latter and twice as fast. On the harder k = ⌈ χ ( G ) / 2 ⌉ k = \lceil\chi(G)/2 \rceil k = ⌈ χ ( G ) /2 ⌉ setting, the ILP can only certify optimality on 85% of the graphs. Here, SCONE produces better solutions than both baselines, while also having the lowest inference times. Since SCONE is trained on proper colorings, specializing its training to infeasible palettes and conflict minimization may further improve approximate solution quality.
Table 16. Mono% (↓ \downarrow ↓ ) and inference time (↓ \downarrow ↓ ) on registers with infeasible palettes.
Additional details on the equivariance ablations The ablations in the main paper compare SCONE with a sequential model that does not enforce color equivariance, both with and without color-permutation augmentation. Here, we provide additional details on the experimental protocol and capacity controls. All variants use the training configuration described in Sec. D.3 and the same most-constrained-first decoding procedure, ensuring that the color representation is the only difference between the primary models. Each configuration is trained three times, then report the mean and standard deviation of the evaluations across training runs. The augmented and unaugmented models share the same data pipeline. Data augmentation samples a fresh uniformly random color permutation on every fetch. Augmentation does not change the number of graph presentations or optimization updates.
For the sudoku_17 experiment in Figure 5 , we hold the training budget fixed at 10 6 10^6 1 0 6 graph presentations for every subset size N N N , setting the number of epochs to 10 6 / N 10^6/N 1 0 6 / N . We evaluate the validation objective at 100 equally spaced points during training, so all subset sizes receive the same number of checkpoint-selection opportunities. All models are evaluated on the same held-out test set. For the experiments varying the target chromatic number, we generate graphs with a planted χ \chi χ -coloring and n ∈ [ 128 , 512 ] n \in[128, 512] n ∈ [ 128 , 512 ] vertices. The planted coloring certifies that χ ( G ) ≤ χ \chi(G) \leq\chi χ ( G ) ≤ χ , but not equality. Since DSATUR fails to find a χ \chi χ -coloring for every retained graph, the datasets comprise challenging, predominantly tight instances as the palette size k k k grows. For χ ∈ { 3 , 5 , 7 , 9 } \chi\in\{3, 5, 7, 9\} χ ∈ { 3 , 5 , 7 , 9 } , we generate 2000 graphs and split them into 80%/10%/10% training, validation, and test instances. We use that same synthetic generator as described in Section D.1, fixing the number of colors to be exactly χ \chi χ . For each dataset, the model is trained with k = χ k = \chi k = χ .
Note that at equal hidden width (d = 128 d = 128 d = 128 ), the non-equivariant model has roughly half the number of trainable parameters than SCONE. For the experiments reported in the main paper in Figure 5 , we therefore set the non-equivariant model at width d = 256 d = 256 d = 256 , giving the baseline approximately twice as many parameters as SCONE. For completeness, Figure 11 gives the full results when all models use hidden width d = 128 d = 128 d = 128 , complementing the results in Figure 5 . Nevertheless, the equal-width and parameter-favorable comparisons yield the same qualitative trends.
Figure 11. Ablation study on Sudoku and synthetic graphs at equal hidden width (d = 128 d = 128 d = 128 ).
Scalability We study scalability on random graphs with 30 to 10,000 nodes, using greedy decoding (W = 1 W = 1 W = 1 ) and beam search (W = 16 W = 16 W = 16 ). As reported in Figure 12 , runtime grows approximately quadratically over the tested range. This is in line with the theory, as for a graph with n n n nodes SCONE takes O ( n ) O(n) O ( n ) forward passes to color each node sequentially, and each forward pass takes linear time in the number of edges, which is linear in n n n for sparse graphs. Greedy decoding remains below one second at 1,000 nodes but reaches tens of seconds at 10,000 nodes.
Figure 12. Inference time per graph versus node count on random graphs, using greedy decoding (W = 1 W = 1 W = 1 ) and beam search (W = 16 W = 16 W = 16 ).