The famous paper of Boris Weisfeiler and Andrei Leman was published in an ordinary Soviet Union information sciences bulletin fifty years ago, just nine years before the graph isomorphism problem was termed a "disease" [16]. The problem was posed to the authors by G.E. Vladuts, an expert in the creation of chemical databases, where each organic compound is described with the aid of a structural formula, in fact, a multigraph with color vertices. In this relatively small but very compressed text, the algorithmic ideas of Leman (who later became a brilliant programmer) and the algebraic technique of Weisfeiler (who later became a famous algebraic geometer) were combined to produce new concepts which are still actively used.
From an algorithmic point of view, the main idea of the paper was to replace a successive classification of vertices of a graph by the classification of its ordered arcs. In matrix language, the input of each iteration is a linear space with a basis of $\{0,1\}$ matrices; during the iteration, this linear space is extended by adding the pairwise products of basis matrices and then closed with respect to entrywise Selur-Hadamard product. This operation was denoted as $\text{Ы}$, the twenty ninth letter in the Russian alphabet. "Why $\text{Ы}$? So nobody would guess" – this is a dialogue from a popular film in the Soviet Union in the 60s.
The output of the Weisfeiler-Leman algorithm, a stable graph, is known today as a coherent configuration, or more exactly, the coherent closure, or WL-closure of the initial graph. The term "coherent configuration" was coined by D. Higman who came to coherent configurations independently in [11]. Later, Higman mentioned the Weisfeiler-Leman algorithm in [12] and Weisfeiler mentioned coherent configurations in [19]. In this connection, it should be noted that a general cellular algebra and the cellular algebra associated with a stable graph are now called, respectively, a coherent algebra and the adjacency algebra of the corresponding coherent con-figuration.
Conjectures 1 and 2 proposed in the paper and which stated, in fact, that the Weisfeiler-Leman algorithm solves the graph isomorphism problem were incorrect. However, computations made by Leman in [14] show that these conjectures are true for all graphs with at most $9$ vertices. A counterexample, a strongly regular non-rank 3 graph with 26 vertices, was found a year later [1]*. In fact, the counterexample on 16 vertices, nowadays commonly called the Shrikhande graph, see [17], is known since 1959. Moreover, it turns out [5] that a deep stabilization algorithm described in a subsequent collective monograph edited by Weisfeiler [19] and closely related with a $k$-tuple coloring algorithm (the $k$-dim W-L in the sense of Babai [2]) cannot test graph isomorphism for a fixed $k$ correctly; an algebraic explanation of this result in terms of coherent configuration was obtained in [6]. A modern presentation of this topic can be found in [Sec. 3.5, 10].
For fifty years since the paper was written, the theory of coherent configurations (cellular algebras) has been repeatedly used to obtain strong mathematical results. First of all, one should mention here a seminal theorem of L. Babai giving an upper bound for the order of a uniprimitive permutation group [3] and recent improvement of this theorem [18]. Together with the Weisfeiler-Leman algorithm, this theory played a key role in constructing polynomial-time testing isomorphism of circulant graphs [8, 15]. Finally, the same can be said of the quasipolynomial algorithm of L. Babai for testing isomorphism of general graphs [4].
In conclusion, we note that the Weisfeiler-Leman paper had a profound impact on the development of algebraic combinatorics in the Soviet Union and Russia; the details can be found in a comprehensive survey [9] and a more recent text [7].
Acknowledgments. We thank Misha Klin and Andrei Vasilyiev for helpful inter-mediation, Grigory Ryabov for the translation of the text into English, as well as Katie Brodhead for assistance in the improvement of English in both preface and translation.
*The smallest counterexample to Conjecture 1 had recently been constructed in [13].