Introduction
The study of symmetries, or transformations that leave a system invariant, is central to physics [1 , 2 , 3 ] . In statistical physics, the symmetries are the organizing principle behind collective behavior: they are used to classify phases of matter, constrain the structure of the order parameter and the free energy that governs it, and determine the type of phase transition that may arise [4 , 5 , 6 , 7 , 8 , 9 ] . The study of symmetry is not restricted to the continuous and is equally applicable to systems defined on discrete structures, such as lattices. Complex networks, however, represent a more general class of discrete structures that model interactions in complex systems: the vertices carry the degrees of freedom, the edges carry the interactions, and the network’s structure shapes the collective behavior that emerges [10 , 11 ] . It is natural to ask, then, whether the statistical-physics notion of symmetry extends to the setting of a network and whether its symmetries play the same organizing role that they do for a system in continuous space [12 , 13 , 14 , 15 , 16 , 17 ] . A first step in that direction is to compare the nodes of a network in pairs. Two vertices may look identical without being interchangeable [18 , 19 , 20 ] . They may have the same degree, share the same distribution of distances to other vertices, or exhibit indistinguishable responses to a dynamical process, yet no symmetry of the graph need exchange them. Making this distinction precise is the task of vertex-orbit identification . For a graph G = ( V , E ) G = (V, E) G = ( V , E ) , its automorphism group Aut ( G ) \operatorname{Aut}(G) Aut ( G ) consists of the permutations of V V V that preserve adjacency. The orbit of a vertex u u u is
Orb G ( u ) = { π ( u ) : π ∈ Aut ( G ) } , \operatorname{Orb}_{G}(u) = \{\pi(u) : \pi\in\operatorname{Aut}(G)\}, Orb G ( u ) = { π ( u ) : π ∈ Aut ( G )} ,
and the orbits partition V V V into classes of genuinely interchangeable vertices. This partition is closely related to the graph-isomorphism problem, but it asks for more than a comparison of two graphs: it asks which vertices of a single graph are equivalent under its own symmetries. A standard way to approach such questions is to compute inexpensive, isomorphism-invariant vertex descriptors and refine the classes they induce [21 ] . The difficulty is that equality of descriptors need not imply membership in the same orbit. Indeed, obtaining the orbit partition efficiently on arbitrary graphs remains a challenging problem, against the backdrop of the quasipolynomial-time upper bound for general graph isomorphism [22 ] . Broad accounts of the algorithmic and complexity-theoretic landscape are provided by Grohe and Schweitzer [23 ] and Grohe and Neuen [24 ] ; the latter also surveys developments following Babai’s quasipolynomial-time isomorphism algorithm [22 ] . Practical solvers such as nauty and Traces use combinatorial invariants, partition refinement, and individualization to determine graph symmetries and construct canonical labelings [21 ] .
Among the refinement schemes these methods build on, the Weisfeiler–Leman (WL) hierarchy provides a natural starting point; its details are given in The k k k -dimensional Weisfeiler–Leman algorithm section. Its successive color refinements extract increasingly detailed combinatorial information, with higher-dimensional variants operating on tuples of vertices; surveys of its algorithmic and logical role can be found in [24 , 25 ] . Since the resulting colors are invariant under automorphisms, the induced vertex classes contain entire orbits, but distinct orbits may remain indistinguishable. The Cai–Fürer–Immerman construction establishes fundamental limitations of bounded-dimensional WL for distinguishing non-isomorphic graphs [26 ] . Such graph-identification lower bounds should not be conflated with failures of orbit recovery on a given graph.
A complementary approach extracts invariants from matrices associated with a graph. The spectral properties of graph Laplacians and the limits of spectral characterization are treated in the surveys of Merris [27 ] and van Dam and Haemers [28 ] . Although isomorphic graphs have the same Laplacian spectrum, the converse fails in general; at the vertex level, cospectrality is likewise weaker than equivalence under an automorphism [29 ] . Matrix functions such as the heat kernel retain information beyond a list of eigenvalues and give access to vertex-dependent, multiscale responses. Heat-kernel signatures were developed as intrinsic descriptors in geometric shape analysis [30 ] , and Raviv, Kimmel, and Bruckstein directly investigated graph isomorphisms and automorphisms through Laplacian spectral signatures [31 ] . Thus, the use of heat diffusion to study graph symmetry has important precedents.
The wider relationship between random walks, diffusion, and network structure is reviewed by Masuda, Porter, and Lambiotte [32 ] . More directly, Najem and Mouawad [33 ] used curvature-inspired coefficients fitted to heat-kernel returns, followed by refinement and probing, to construct and verify candidate graph isomorphisms. The present work departs from that fitting-based geometric interpretation and focuses instead on recovering the orbit partition from heat-kernel information itself. Our signatures incorporate full diffusion rows organized by graph distance, as well as complementary operators and graph transformations. In particular, Laplacian-based correlation functions have been considered in network coarse-graining [34 ] , while graph Dirac operators provide coupled vertex–edge dynamics [35 ] . We use these ingredients as sources of additional invariant information, together with line graphs and exact-distance graphs, rather than treating any one operator as a complete characterization of vertex symmetry.
Increasing the amount of information available is not, however, a cost-free remedy. Richer graph representations can make dense spectral computations prohibitively expensive, while even combinations of several signatures may leave vertices from different orbits in a common class. Rather than indefinitely enlarge the transformed graphs, we turn to probing . Here a vertex is distinguished not only by a signature of the original graph, but by the collection of signatures obtained after systematically applying controlled, rooted graph modifications. By considering admissible modifications in a way that respects relabeling, these probes expose relational differences that static summaries had concealed.
The outcome is a hierarchy of increasingly expressive signatures, not a claim that any one of them is a complete invariant for arbitrary graphs. We give the constructions, explain their automorphism-invariance in the exact setting, and document the counterexamples that motivated their successive refinements. We then evaluate the resulting partitions against known vertex orbits on a broad range of benchmark graphs, compare their distinguishing behavior with Weisfeiler–Leman refinement, and examine the time and memory costs of the spectral and probing stages. Under the stated arithmetic model, fixed-depth transformations and probes of fixed size admit polynomial bounds, but their degrees and practical costs can be substantial; moreover, numerical discretization introduces resolution limits absent from the exact mathematical objects. These distinctions matter: successfully recovering the orbit partition on difficult instances is evidence of discriminating power, not a general proof of completeness or of a polynomial-time orbit algorithm.
In this sense, the paper is both a continuation of and a departure from [33 ] . We retain the central insight that diffusion can reveal subtle structural information, but no longer require that information to be interpreted as curvature on a latent manifold. Instead, we ask a more directly combinatorial question: which invariant observations of a vertex and which invariant responses to controlled changes in the graph are sufficient to distinguish it from vertices outside its orbit? The counterexamples encountered along the way are not incidental obstacles; they are the organizing principle of the construction and the guide to its remaining limitations.
Construction and evolution of our signatures
We start from where Najem and Mouawad [33 ] left off. In that paper, the signatures are motivated by a direct analogy to a result for the heat kernel on a continuous, Riemannian manifold setting. In the short-time asymptotic, one can expand the heat kernel as an infinite series whose coefficients carry curvature information. More precisely, the classical Minakshisundaram–Pleijel expansion gives that the heat kernel obeys
K ( x , y , t ) = 1 ( 4 π t ) n / 2 exp ( − d ( x , y ) 2 4 t ) ∑ k = 0 ∞ u k ( x , y ) t k , (1) K(x,y,t) = \frac{1}{(4\pi t)^{n/2}} \exp\left(-\frac{d(x,y)^2}{4t}\right) \sum_{k=0}^{\infty} u_k(x,y)t^k, \tag*{(1)} K ( x , y , t ) = ( 4 π t ) n /2 1 exp ( − 4 t d ( x , y ) 2 ) k = 0 ∑ ∞ u k ( x , y ) t k , (1)
for an n n n -dimensional smooth Riemannian manifold, locally near the diagonal, as t → 0 + t \to0^{+} t → 0 + . In particular, on the diagonal (when x = y x=y x = y ), u 0 ( x , x ) = 1 u_0(x,x)=1 u 0 ( x , x ) = 1 , u 1 ( x , x ) = 1 6 R S c a l ( x ) u_1(x,x)=\frac{1}{6}R_{\mathrm{Scal}}(x) u 1 ( x , x ) = 6 1 R Scal ( x ) , and
u 2 ( x , x ) = 1 360 ( 12 Δ R S c a l ( x ) + 5 R S c a l ( x ) 2 − 2 ∣ Ric ( x ) ∣ 2 + 2 ∣ R ( x ) ∣ 2 ) , (2) u_2(x,x) = \frac{1}{360}\left(12\Delta R_{\mathrm{Scal}}(x) + 5R_{\mathrm{Scal}}(x)^2 - 2|\operatorname{Ric}(x)|^2 + 2|R(x)|^2\right), \tag*{(2)} u 2 ( x , x ) = 360 1 ( 12Δ R Scal ( x ) + 5 R Scal ( x ) 2 − 2∣ Ric ( x ) ∣ 2 + 2∣ R ( x ) ∣ 2 ) , (2)
with
∣ Ric ( x ) ∣ 2 : = R i j ( x ) R i j ( x ) g i i ( x ) g j j ( x ) , ∣ R ( x ) ∣ 2 : = R i j k l ( x ) R i j k l ( x ) g i i ( x ) g j j ( x ) g k k ( x ) g l l ( x ) , (3) \begin{aligned}
|\operatorname{Ric}(x)|^2 &:= R_{ij}(x)R_{ij}(x)g^{ii}(x)g^{jj}(x),\\
|R(x)|^2 &:= R_{ijkl}(x)R_{ijkl}(x)g^{ii}(x)g^{jj}(x)g^{kk}(x)g^{ll}(x), \tag*{(3)}
\end{aligned} ∣ Ric ( x ) ∣ 2 ∣ R ( x ) ∣ 2 := R ij ( x ) R ij ( x ) g ii ( x ) g j j ( x ) , := R ij k l ( x ) R ij k l ( x ) g ii ( x ) g j j ( x ) g k k ( x ) g l l ( x ) , (3)
where g g g is the Riemannian metric, R S c a l ( x ) R_{\mathrm{Scal}}(x) R Scal ( x ) is the scalar curvature at x x x , Ric i j ( x ) \operatorname{Ric}_{ij}(x) Ric ij ( x ) is the Ricci tensor, and R i j k l ( x ) R_{ijkl}(x) R ij k l ( x ) is the Riemann curvature tensor. Higher-order terms are polynomials depending on the curvature tensor and its covariant derivatives. For the mathematical literature, see [36 ] , [37 p. 201, Theorem 3.3.1] , [38 ] , and [39 Theorem 3.1] .
Conversely, a diffusion process on a graph G \mathcal{G} G with N N N nodes is given by the differential equation
∂ u ∂ t = − L u , (4) \frac{\partial u}{\partial t}=-Lu, \tag*{(4)} ∂ t ∂ u = − Lu , (4)
where u ( t ) u(t) u ( t ) is an N N N -vector representing a concentration variable over each node and L L L is the Laplacian matrix. The latter is given by L = D − A L=D-A L = D − A , where D D D is a diagonal matrix of the nodes’ degrees and A A A is the adjacency matrix satisfying A i j = 1 A_{ij}=1 A ij = 1 if ( i , j ) ∈ E (i,j)\in E ( i , j ) ∈ E and 0 0 0 otherwise. (4) admits the solution
u ( t ) = e − L t u ( 0 ) , (5) u(t)=e^{-Lt}u(0), \tag*{(5)} u ( t ) = e − L t u ( 0 ) , (5)
where K = e − L t K=e^{-Lt} K = e − L t is the heat kernel of G \mathcal{G} G , which will take center stage in the investigations below, and u ( 0 ) u(0) u ( 0 ) is the initial condition.
The paper [33 ] constructs vertex-based signatures by fitting an ansatz of the form
K ( i , i , t ) ≈ 1 t d s / 2 ∑ k = 0 N u k ( i ) t k , (6) K(i,i,t)\approx\frac{1}{t^{d_s/2}}\sum_{k=0}^{N}u_k(i)t^k, \tag*{(6)} K ( i , i , t ) ≈ t d s /2 1 k = 0 ∑ N u k ( i ) t k , (6)
to the heat kernel on a finite interval [ 0 , T ] [0,T] [ 0 , T ] . Here, the matrix heat kernel at each time t ∈ [ 0 , T ] t\in[0,T] t ∈ [ 0 , T ] is obtained by the eigendecomposition K ( t ) = e − L t = V e − Λ t V − 1 K(t)=e^{-Lt}=Ve^{-\Lambda t}V^{-1} K ( t ) = e − L t = V e − Λ t V − 1 where Λ \Lambda Λ is a diagonal matrix of the eigenvalues of the Laplacian λ 1 , λ 2 , … , λ n \lambda_1,\lambda_2,\ldots,\lambda_n λ 1 , λ 2 , … , λ n and V V V is the matrix whose columns are the eigenvectors of L L L . To each node i i i the tuple of coefficients ( u k ( i ) ) k = 1 N (u_k(i))_{k=1}^{N} ( u k ( i ) ) k = 1 N is attributed to obtain a partition of the graph by grouping nodes based on (rounded) equality of these tuples.
This algorithm offers a vivid geometric picture of the nodes in a graph “perturbing” a latent space in which the graph is embedded (see Figure 1 of [33 ] ). One might imagine that discovering curvature information of that latent manifold might help partition the graph into “similarly behaving nodes", thus motivating the formulation (6). A natural question then is: do the above signatures match the true orbit partition of a graph? How much information can we extract from this intuitive picture?
The route to attempting to answer this question starts by noting the shortcomings of the above approach. First, assuming that an ansatz of the form (6) holds, the dimension of a graph G \mathcal{G} G is not a particularly well-defined notion. In [33 ] , the authors make use of the spectral dimension d s d_s d s , as a drop-in substitute for the dimension of the manifold in the continuous setting. The spectral dimension is obtained by linear regressing on the log-log graph of
ρ ( λ ′ < λ ) ∼ λ d s / 2 , (7) \rho(\lambda' < \lambda)\sim\lambda^{d_s/2}, \tag*{(7)} ρ ( λ ′ < λ ) ∼ λ d s /2 , (7)
for λ → 0 \lambda\to0 λ → 0 . It is a particularly suitable notion for lattice, fractal, and power-law/scale-free graphs [40 ] , due to the structure of the small eigenvalues of their Laplacians. For other graph classes, the small eigenvalue regime might be sparse or might not obey a power law of the form (7), which drives the subdivision process that [33 ] adopts, leading to a growth in graph size, which became prohibitive. Even then, the notion of the spectral dimension is not presently rigorous, especially as to what counts as “λ → 0 \lambda\to0 λ → 0 ” and arbitrariness in the choice of the interval to fit on, and it appeared difficult to find a rigorous justification without developing a substantial theory. More importantly, the ansatz (6) is not rigorously justified in the graph setting. One can notice that for d s > 0 d_s>0 d s > 0 and u 0 ( i ) ≠ 0 u_0(i) \ne0 u 0 ( i ) = 0 , the above expansion 1 t d s / 2 ∑ k = 0 N u k ( i ) t k \frac{1}{t^{d s/2}}\sum_{k=0}^{N}u_k(i)t^k t d s /2 1 ∑ k = 0 N u k ( i ) t k goes to ± ∞ \pm\infty ± ∞ as t → 0 t \to0 t → 0 . However, the graph kernel behaves differently: at t = 0 t=0 t = 0 ,
K ( x , y , t ) = { 1 if x = y , 0 if x ≠ y , (8) K(x,y,t)=
\begin{cases}
1 & \text{if } x=y,\\
0 & \text{if } x\ne y,
\end{cases} \tag*{(8)} K ( x , y , t ) = { 1 0 if x = y , if x = y , (8)
which is not captured in the above expansion. Additionally, we remark on the difference in the evolution of the heat kernel on manifold and on a graph. In particular, the Minakshisundaram-Pleijel expansion gives that the short-time asymptotic on a manifold is
lim t → 0 + t log K ( x , y , t ) = − d g ( x , y ) 2 2 , (9) \lim_{t\to0^+} t\log K(x,y,t)=-\frac{d_g(x,y)^2}{2}, \tag*{(9)} t → 0 + lim t log K ( x , y , t ) = − 2 d g ( x , y ) 2 , (9)
whereas, on a graph setting, Keller, Lenz, Münch, Schmidt, & Telcs [41 ] and Steinerberger [42 ] prove considerably different short-time behavior, captured by
lim t → 0 + log K ( x , y , t ) log t = d ( x , y ) . (10) \lim_{t\to0^+}\frac{\log K(x,y,t)}{\log t}=d(x,y). \tag*{(10)} t → 0 + lim log t log K ( x , y , t ) = d ( x , y ) . (10)
Further, the presence of the log t \log t log t term in the denominator indicates a mismatch between the two equations and implies that the graph kernel should not include a time-dependent exponential factor. All of the above shortcomings inform the move to using the diagonal values of the heat kernel directly as signatures, that is, we endow the node i i i with the signature
sig ( i ) = { K ( i , i , t ) : t = 0 , Δ t , 2 Δ t , … , T } , (11) \operatorname{sig}(i)=\{K(i,i,t):t=0,\Delta t,2\Delta t,\ldots,T\}, \tag*{(11)} sig ( i ) = { K ( i , i , t ) : t = 0 , Δ t , 2Δ t , … , T } , (11)
for a chosen time step Δ t \Delta t Δ t and suitable large end-time T T T . We treat the signature as a set (or a lexicographically sorted array), so as to have automorphism-invariant vertex signatures, removing the effect of labeling.
This is the concrete starting point of the investigation. The following discussion will aim to progressively find counterexamples to the proposed algorithms to obtain stronger and stronger signatures. First, signatures of the form (11) do not distinguish the orbits of the Frucht graph, which possesses only a trivial automorphism (all nodes are in separate orbits), shown in Figure 1 . The above signatures merge nodes 1 and 10 into the same equivalence class, since they have the same heat kernel diagonal for all time. We prove this in Section “Counterexamples” of the Appendix in a computer-assisted Cayley-Hamilton-based argument. The mechanism of the proof follows from the observation that the heat kernel is represented mathematically by the matrix
Figure 1. Frucht was not resolved using the diagonal of K ( i , i , t ) K(i,i,t) K ( i , i , t ) , which merged nodes 1 and 10 into one equivalence class, while the full rows K ( i , : , t ) K(i,:,t) K ( i , : , t ) resolved the orbits and identified the nodes as singletons.
e − L t = ∑ k = 0 ∞ ( − 1 ) k t k k ! L k = I − t L + t 2 2 L 2 − t 3 3 ! L 3 + ⋯ . (12) e^{-Lt}=\sum_{k=0}^{\infty}\frac{(-1)^k t^k}{k!}L^k=I-tL+\frac{t^2}{2}L^2-\frac{t^3}{3!}L^3+\cdots. \tag*{(12)} e − L t = k = 0 ∑ ∞ k ! ( − 1 ) k t k L k = I − t L + 2 t 2 L 2 − 3 ! t 3 L 3 + ⋯ . (12)
This infinite sum cannot be evaluated (computationally) without truncation or approximation. However, by the Cayley-Hamilton theorem, every power L k L^k L k with k ≥ n k\ge n k ≥ n (the size of the matrix) can be expressed as a linear combination of I , L , … , L n − 1 I,L,\ldots,L^{n-1} I , L , … , L n − 1 , with coefficients depending on k k k and L L L . Consequently, for each time t t t , the matrix exponential admits the exact representation
e − L t = ∑ j = 0 n − 1 α j ( t ) L j , (13) e^{-Lt}=\sum_{j=0}^{n-1}\alpha_j(t)L^j, \tag*{(13)} e − L t = j = 0 ∑ n − 1 α j ( t ) L j , (13)
where the coefficients α j ( t ) \alpha_j(t) α j ( t ) depend on t t t and L L L . The diagonal algorithm only captures the values ( e − L t ) i i (e^{-Lt})_{ii} ( e − L t ) ii , which represent solely the probability of a random walker that start at node i i i to return to it at time t t t . We prove in the appendix that for the Frucht graph ( e − L t ) 1 , 1 = ( e − L t ) 10 , 10 (e^{-Lt})_{1,1}=(e^{-Lt})_{10,10} ( e − L t ) 1 , 1 = ( e − L t ) 10 , 10 , justifying their indistinguishability from the information only on the diagonal.
However, there is much more information in the heat kernel that is not captured in the diagonal, involving walks that start and end at different nodes. Najem and Mouawad [33 ] were cognizant of the presence of this information in the off-diagonal terms of the expansion. Nevertheless, they did not draw on it for the following reason: if the ansatz is adopted analogously with the Riemannian setting (1) , then for i ≠ j i \ne j i = j the kernel has a dependence on d d d through ∝ e − d ( i , j ) 2 / 4 t \propto e^{-d(i,j)^2/4t} ∝ e − d ( i , j ) 2 /4 t . Then if the standard graph distance is used, and, for the reasons we delineated above, which include subdivision, size growth, and a contrived spectral dimension, to list a few of them, it is not an adequate expansion for graphs. Otherwise, if the analogy with the latent manifold is pushed, with the latter’s distance measure is unknown, then a nonlinear least-squares problem has to be solved that requires fitting for u k ( i , j ) u_k(i,j) u k ( i , j ) and d ( i , j ) d(i,j) d ( i , j ) simultaneously. The two parameter sets are coupled making their simultaneous estimation hard and ill-posed, in addition to being an evident source of error for a problem that is precision-critical. Hence, a way to circumvent the shortcoming of the diagonal and the fit using the off-diagonal elements is to shift to the full row element, in the form of the signatures
sig ( i ) = { K ( i , j , t ) : j = 1 , … , n ; t = 0 , Δ t , 2 Δ t , … , T } . (14) \operatorname{sig}(i)=\{K(i,j,t):j=1,\ldots,n;\ t=0,\Delta t,2\Delta t,\ldots,T\}. \tag*{(14)} sig ( i ) = { K ( i , j , t ) : j = 1 , … , n ; t = 0 , Δ t , 2Δ t , … , T } . (14)
Some information is lost in just looking at the values as a set (or as a lexicographically sorted array). We can retain more information by sorting the rows in a BFS-aware manner and preserving the temporal order, as such
sig G , i n t e r ( i ) ( t ) = ( K ( i , i , t ) , { K ( i , j , t ) : d ( i , j ) = 1 } , { K ( i , j , t ) : d ( i , j ) = 2 } , … ) , (15) \operatorname{sig}_{G,\mathrm{inter}}(i)(t)=\left(K(i,i,t),\{K(i,j,t):d(i,j)=1\},\{K(i,j,t):d(i,j)=2\},\ldots\right), \tag*{(15)} sig G , inter ( i ) ( t ) = ( K ( i , i , t ) , { K ( i , j , t ) : d ( i , j ) = 1 } , { K ( i , j , t ) : d ( i , j ) = 2 } , … ) , (15)
and
sig G , i n t e r ( i ) = ( sig ( 0 ) , sig ( Δ t ) , sig ( 2 Δ t ) , … , sig ( T ) ) , (16) \operatorname{sig}_{G,\mathrm{inter}}(i)=\left(\operatorname{sig}(0),\operatorname{sig}(\Delta t),\operatorname{sig}(2\Delta t),\ldots,\operatorname{sig}(T)\right), \tag*{(16)} sig G , inter ( i ) = ( sig ( 0 ) , sig ( Δ t ) , sig ( 2Δ t ) , … , sig ( T ) ) , (16)
with the final signature being
sig G ( i ) = ( sig i n t e r ( i ) , { sig i n t e r ( j ) : d ( i , j ) = 1 } , { sig i n t e r ( j ) : d ( i , j ) = 2 } , … ) . (17) \operatorname{sig}_{G}(i)=\left(\operatorname{sig}_{\mathrm{inter}}(i),\{\operatorname{sig}_{\mathrm{inter}}(j):d(i,j)=1\},\{\operatorname{sig}_{\mathrm{inter}}(j):d(i,j)=2\},\ldots\right). \tag*{(17)} sig G ( i ) = ( sig inter ( i ) , { sig inter ( j ) : d ( i , j ) = 1 } , { sig inter ( j ) : d ( i , j ) = 2 } , … ) . (17)
We refer to the two levels of BFS as inner (Equation (15) ) and outer (Equation (17) ) BFS, referring to first ordering the kernel values based on distance from the source node, and then similarly for the full temporal row signature sig G , i n t e r ( i ) \operatorname{sig}_{G,\mathrm{inter}}(i) sig G , inter ( i ) . Loosely, this is motivated by a continuous analog: the Cartan-Ambrose-Hicks theorems says that if balls around points in two manifolds have matching curvature along corresponding geodesics, with directions compared by parallel transport, then those balls are isometric [43 Lemma 1.41] . Similarly, we imbue the same spirit in our signatures by grouping nodes based on distance to the source node i i i , as if batching nodes into concentric balls, making the signature comparison finer. With these signatures, the Frucht graph is resolved.
Given the cost of this computation, further exacerbated by the need for multiple time steps (as shown in Complexity of the final algorithm Section), we seek cheaper alternatives to compute these signatures. To this end, we draw on the Laplacian-based approach to graph coarse-graining [34 ] . In this framework, correlations between nodes are computed using a statistical-mechanical model, and coarse-graining proceeds by merging the most strongly correlated pairs. Each node i i i is assigned a scalar state variable φ i \varphi_i φ i , whose interactions are described through the Hamiltonian
H ( Φ ) = 1 2 ∑ i j φ i ( L i j + r δ i j ) φ j − ∑ i J i φ i , (18) \mathcal{H}(\Phi) = \frac{1}{2}\sum_{ij}\varphi_i(L_{ij}+r\delta_{ij})\varphi_j-\sum_i J_i\varphi_i, \tag*{(18)} H ( Φ ) = 2 1 ij ∑ φ i ( L ij + r δ ij ) φ j − i ∑ J i φ i , (18)
where Φ = ( φ 1 , … , φ N ) \Phi=(\varphi_1,\ldots,\varphi_N) Φ = ( φ 1 , … , φ N ) is the state of the network, J i J_i J i is an external field applied to node i i i , and r > 0 r>0 r > 0 is a regularization parameter that makes L + r I L+rI L + r I invertible. The Laplacian term encodes interactions between adjacent nodes. At inverse temperature β \beta β , the network states follow the Boltzmann distribution
P β ( Φ ) = e − β H Z , Z = ∫ e − β H ( Φ ) d Φ , (19) P_\beta(\Phi)=\frac{e^{-\beta\mathcal{H}}}{\mathcal{Z}},\qquad\mathcal{Z}=\int e^{-\beta\mathcal{H}(\Phi)}\,\mathrm{d}\Phi, \tag*{(19)} P β ( Φ ) = Z e − β H , Z = ∫ e − β H ( Φ ) d Φ , (19)
where Z \mathcal{Z} Z is the partition function. The correlation between nodes i i i and j j j is their covariance
C i j = φ j φ i ‾ − φ j ‾ φ i ‾ , (20) C_{ij}=\overline{\varphi_j\varphi_i}-\overline{\varphi_j}\,\overline{\varphi_i}, \tag*{(20)} C ij = φ j φ i − φ j φ i , (20)
where the overline denotes the average given by
φ i ‾ = ∫ φ i P β ( Φ ) d Φ , (21) \overline{\varphi_i}=\int\varphi_iP_\beta(\Phi)\,\mathrm{d}\Phi, \tag*{(21)} φ i = ∫ φ i P β ( Φ ) d Φ , (21)
Since the Hamiltonian is quadratic, the Boltzmann distribution is Gaussian, with covariance matrix
C = 1 β ( L + r I ) − 1 . (22) C=\frac{1}{\beta}(L+rI)^{-1}. \tag*{(22)} C = β 1 ( L + r I ) − 1 . (22)
Setting β = 1 \beta=1 β = 1 , we obtain
C = ( L + r I ) − 1 . (23) C=(L+rI)^{-1}. \tag*{(23)} C = ( L + r I ) − 1 . (23)
In what follows, we use the correlation matrix C C C to build new signatures, similarly to Equations (15) and (17) , with
sig C , i n t e r ( i ) = ( C i i , { C i j : d ( i , j ) = 1 } , { C i j : d ( i , j ) = 2 } , … ) , (24) \operatorname{sig}_{C,\mathrm{inter}}(i)=\left(C_{ii},\{C_{ij}:d(i,j)=1\},\{C_{ij}:d(i,j)=2\},\ldots\right), \tag*{(24)} sig C , inter ( i ) = ( C ii , { C ij : d ( i , j ) = 1 } , { C ij : d ( i , j ) = 2 } , … ) , (24)
and
sig C ( i ) = ( sig C , i n t e r ( i ) , { sig C , i n t e r ( j ) : d ( i , j ) = 1 } , { sig C , i n t e r ( j ) : d ( i , j ) = 2 } , … ) . (25) \operatorname{sig}_{C}(i)=\left(\operatorname{sig}_{C,\mathrm{inter}}(i),\{\operatorname{sig}_{C,\mathrm{inter}}(j):d(i,j)=1\},\{\operatorname{sig}_{C,\mathrm{inter}}(j):d(i,j)=2\},\ldots\right). \tag*{(25)} sig C ( i ) = ( sig C , inter ( i ) , { sig C , inter ( j ) : d ( i , j ) = 1 } , { sig C , inter ( j ) : d ( i , j ) = 2 } , … ) . (25)
The correlation signatures are not an exact substitute for multiple time steps of the heat kernel; concretely, we prove that the signatures that use the heat kernel for all times are equivalent to the signatures that use the correlation matrix for all positive values of r r r . See Section “Heat kernel and correlation equivalence” in the Appendix for the proof.
However, in case of either the heat kernel (17) or the correlation matrix (25) , we run into another counterexample: the sts-13 graph from the Nauty dataset [44 ] . The graph has two orbits, which get wrongly lumped into one equivalence class using our signatures, as shown in Figure 2 . The nodes are color-coded by their sig ( i ) \operatorname{sig}(i) sig ( i ) , which clearly does not separate those of the first orbit, which lie in the lower plane, from those in the second orbit of the upper plane. See Section “Counterexamples” in the Appendix for a proof that the full heat kernel row signatures, with inner and outer BFS, do not distinguish these two nodes. Here we ask ourselves the question: are we making maximal use of the data in the adjacency? Our measurements so far focused on heat diffusing through the “sensors”, which are the nodes, but did not consider edges, which are the other complementary building blocks of the graph that mediate diffusion. So, the natural question that follows is: what is happening to the heat across the edges? This required us to follow the diffusion on the line graph.
Figure 2. Nodes in orbit 1, lying in the lower plane, and those in orbit 2, lying in the upper plane get lumped into one big equivalence class using signature of the kernel of G \mathcal{G} G , and are subsequently undifferentiated using the node signature only. Using the information on the edges, computed from the kernel of L ( G ) L(\mathcal{G}) L ( G ) , the signatures now can separate the equivalence class into two, which match the orbits.
The line graph of a simple, undirected graph G = ( V , E ) \mathcal{G} = (V, E) G = ( V , E ) , denoted by L ( G ) = ( E , E 1 ) L(\mathcal{G}) = (E, E^{1}) L ( G ) = ( E , E 1 ) , is constructed by taking the edges of G \mathcal{G} G as the vertices of the line graph and connecting two distinct vertices whenever their corresponding edges share a vertex in the original graph. More precisely,
( e , f ) ∈ E 1 ⟺ e ≠ f and e ∩ f ≠ ∅ , (26) (e, f) \in E^{1} \Longleftrightarrow e \ne f \text{ and } e \cap f \ne\varnothing, \tag*{(26)} ( e , f ) ∈ E 1 ⟺ e = f and e ∩ f = ∅ , (26)
where each edge is identified with the set of its endpoints. Iterated line graphs of G \mathcal{G} G are defined recursively by by setting L 0 ( G ) = G L^{0}(\mathcal{G}) = \mathcal{G} L 0 ( G ) = G and L k + 1 ( G ) = L ( L k ( G ) ) L^{k+1}(\mathcal{G}) = L(L^{k}(\mathcal{G})) L k + 1 ( G ) = L ( L k ( G )) . In particular, writing L k ( G ) = ( V k , E k ) L^{k}(\mathcal{G}) = (V^{k}, E^{k}) L k ( G ) = ( V k , E k ) , the vertex set of each successive line graph is given by V k + 1 = E k V^{k+1} = E^{k} V k + 1 = E k , while its edges are determined by the same adjacency rule.
The signatures (whether heat kernel or correlation) are constructed by appending to the signature of each node i i i the signatures of all the edges ( i , j ) (i,j) ( i , j ) of the original graph that contain i i i , which are nodes in the line graph L ( G ) \mathcal{L}(G) L ( G ) . This is represented mathematically as
sig ( G , L ( G ) ) , i n t e r ( i ) = ( sig G ( i ) , { sig L ( G ) ( ( i , j ) ) : ( i , j ) ∈ E } ) , (27) \operatorname{sig}_{(G,\mathcal{L}(G)),\mathrm{inter}}(i)=\left(\operatorname{sig}_{G}(i),\left\{\operatorname{sig}_{\mathcal{L}(G)}((i,j)):(i,j)\in E\right\}\right), \tag*{(27)} sig ( G , L ( G )) , inter ( i ) = ( sig G ( i ) , { sig L ( G ) (( i , j )) : ( i , j ) ∈ E } ) , (27)
with the final signature being
sig ( G , L ( G ) ) ( i ) = ( sig ( G , L ( G ) ) , i n t e r ( i ) , { sig ( G , L ( G ) ) , i n t e r ( j ) : d ( i , j ) = 1 } , \operatorname{sig}_{(G,\mathcal{L}(G))}(i)=(\operatorname{sig}_{(G,\mathcal{L}(G)),\mathrm{inter}}(i),\{\operatorname{sig}_{(G,\mathcal{L}(G)),\mathrm{inter}}(j):d(i,j)=1\}, sig ( G , L ( G )) ( i ) = ( sig ( G , L ( G )) , inter ( i ) , { sig ( G , L ( G )) , inter ( j ) : d ( i , j ) = 1 } ,
{ sig ( G , L ( G ) ) , i n t e r ( j ) : d ( i , j ) = 2 } , … ) . (28) \{\operatorname{sig}_{(G,\mathcal{L}(G)),\mathrm{inter}}(j):d(i,j)=2\},\ldots). \tag*{(28)} { sig ( G , L ( G )) , inter ( j ) : d ( i , j ) = 2 } , … ) . (28)
In Figure 3 on the left, a sample graph is shown with nodes color-coded and sized by their distance from root node 1, which is shown in orange. Blue is assigned to its first neighbors and green to its second. Similarly, its line graph is constructed on the right. The signature of node 1 contains its kernel values sorted by distance and appended to it the signatures of nodes a a a , b b b , and c c c , which are the edges incident to 1. The structure of the signature is now schematized in Figure 4 . These updated signatures lead to the resolution of sts-13, shown in the right pane of Figure 2 ,
Figure 3. A sample graph shown in left along with its line graph on the right. The orange is the node is the root, blue nodes belong to BFS level 1, green to level 2.
Figure 4. The updated signature data structure, which involves inner BFS followed by the edges incident to the node, inside an outer BFS.
where the nodes are now distinguished by the color of the edges incident to them. In particular, nodes of the first orbits have six green edges and nine violet, versus twelve green edges and three violet for nodes of the second orbit.
Till now, the features incorporated in the nodes’ signatures were mostly retrieved from the diffusion dynamics over the graph via its heat kernel. However, this dynamical process is a dissipative one; that is, the kernel decays exponentially in time, which describes information spread through the network. For this, we wanted to resort to a non-dissipative dynamical process. We propose the use of the Dirac operator [35 ] , which describes a wave dynamics on the graph G \mathcal{G} G . The advantage of this is two fold: first it offers an oscillatory behavior and thus non-decaying signatures of the nodes, and second, and most importantly, it couples to the dynamics of the nodes to those of the edges by construction. The Dirac operator for a graph G \mathcal{G} G is an ( N + M ) × ( N + M ) (N+M)\times(N+M) ( N + M ) × ( N + M ) matrix and is given by
D = ( 0 B B T 0 ) , (29) \mathcal{D}=\begin{pmatrix} 0 & B \\ B^{T} & 0 \end{pmatrix}, \tag*{(29)} D = ( 0 B T B 0 ) , (29)
where B B B is the incidence matrix, an N × E N \times E N × E matrix defined as
B i j = { 0 , if edge j is not incident to node i , 1 , if edge j is directed towards node i , − 1 , if edge j is directed away from node i . (30) B_{ij} =
\begin{cases}
0, & \text{if edge } j \text{ is not incident to node } i,\\
1, & \text{if edge } j \text{ is directed towards node } i,\\
-1, & \text{if edge } j \text{ is directed away from node } i.
\end{cases} \tag*{(30)} B ij = ⎩ ⎨ ⎧ 0 , 1 , − 1 , if edge j is not incident to node i , if edge j is directed towards node i , if edge j is directed away from node i . (30)
Clearly, the Dirac operator acts on both nodes and edges in G \mathcal{G} G , increasing the degrees of freedom associated with the dynamics from N N N , in diffusion processes, to N + M N + M N + M , in this case. We can then write the topological Dirac equation on G \mathcal{G} G , given by
i ∂ φ ∂ t = D φ , (31) i\frac{\partial\varphi}{\partial t} = \mathcal{D}\varphi, \tag*{(31)} i ∂ t ∂ φ = D φ , (31)
The topological Dirac equation describes the time evolution of the state of the system encoded in the ( N + E ) × 1 (N + E) \times1 ( N + E ) × 1 vector φ \varphi φ , defined over nodes and edges. The solution to Equation (31) is
φ = e − i D t φ ( 0 ) . (32) \varphi= e^{-i\mathcal{D}t}\varphi(0). \tag*{(32)} φ = e − i D t φ ( 0 ) . (32)
This evolution is analogous to the heat flow on G \mathcal{G} G described by Equation (4) , but the factor i i i in the exponent produces oscillatory dynamics. To construct the signatures, we use the absolute values of the real and imaginary parts of each entry of e − i D t e^{-iDt} e − i D t . Thus, for indices x , y x,y x , y corresponding to nodes or edges, the microcomponents are the ordered pair
( ∣ Re ( e − i D t ) x y ∣ , ∣ Im ( e − i D t ) x y ∣ ) . (33) \left(\left|\operatorname{Re}\left(e^{-iDt}\right)_{xy}\right|,\left|\operatorname{Im}\left(e^{-iDt}\right)_{xy}\right|\right). \tag*{(33)} ( Re ( e − i D t ) x y , Im ( e − i D t ) x y ) . (33)
These absolute values remove the signs introduced by the choice of edge orientations. At each time, we sort these pairs lexicographically, keeping the node and edge blocks separate. We then concatenate the results in time order and append to each node the sorted temporal signatures of its incident edges. The resulting intermediary signatures are used in the outer BFS construction.
At this stage, we thought we had a strong signature that could resolve all the sts graphs until we encountered sts-15, where the kernels and the correlations of the graph, its line graph, and the Dirac operator failed to resolve its orbits. A simple visualization of the orbits provided us with tremendous insight, shown in Figure 5 . The graph had two orbits also placed in the upper and lower planes, with one very noticeable feature: the nodes of the lower plane, which belong to the first orbit, were not connected. Since the kernel is a measure of the probability of visits, it was clear that the signal between nodes i i i and j j j of the first orbit was weak. In particular, given a root node shown in orange in Figure 6 , the elements of the kernel associated with its nearest neighbors, shown in blue, are stronger than those farther away, shown in green; therefore, wanted to bring this small quantity to the front seat!
Figure 5. Nodes of orbit 1 do not communicate in G \mathcal{G} G , which are the ones that sit in the lower plane, while those in orbit 2 have intra links, and inter links that connect them to the first orbit. In G 2 \mathcal{G}^{2} G 2 intra orbit 1 edges get created, which amplify their shared information, relative to what it was in G \mathcal{G} G .
Figure 6. An illustration of information amplification, where the kernel values corresponding to the root node and its second neighbors in G \mathcal{G} G get stronger on G 2 \mathcal{G}^{2} G 2 which is constructed from the adjacency between nodes that are d = 2 d = 2 d = 2 away in G 2 \mathcal{G}^{2} G 2 .
Thus, to strengthen this structurally weak signal, we thought of a way to bring distant nodes closer and introduced the sequence of graphs G ( k ) \mathcal{G}^{(k)} G ( k ) . The latter is constructed using the nodes of G \mathcal{G} G where a connection is made between two nodes in G ( k ) \mathcal{G}^{(k)} G ( k ) if their pairwise shortest distance in G \mathcal{G} G is k k k . Hence, the adjacency matrix of G ( k ) \mathcal{G}^{(k)} G ( k ) is defined by
A i j ( k ) = { 1 if d ( i , j ) = k , 0 otherwise . (34) A_{ij}^{(k)} =
\begin{cases}
1 & \text{if } d(i,j)=k,\\
0 & \text{otherwise}.
\end{cases} \tag*{(34)} A ij ( k ) = { 1 0 if d ( i , j ) = k , otherwise . (34)
In Figure 6 , we show the relative kernel values for the nearest neighbors versus those of the second nearest neighbors in a graph G \mathcal{G} G . They switch order in G 2 \mathcal{G}^{2} G 2 . In particular, nodes 2,3, and 4, colored in blue, are the nearest neighbors of node 1 in G \mathcal{G} G . They become second neighbors in G ( 2 ) \mathcal{G}^{(2)} G ( 2 ) , and are subsequently colored in green, while nodes 5,6,7,8,9, and 10, which were second neighbors of 1 in G \mathcal{G} G and were colored in green, now shift roles in G 2 \mathcal{G}^{2} G 2 and become first neighbors and are thus colored in blue.
This approach bypasses intermediacy by making the connection between distant nodes immediate. In other words, it trades intermediacy with immediacy and subsequently brings information weakened by an inverse factorial weight between neighbors at distance k k k in G \mathcal{G} G , to the leading order as nearest neighbors in G ( k ) \mathcal{G}^{(k)} G ( k ) , which is illustrated in Figure 7 . The diffusion process is followed on these new
Figure 7. The scheme shows that the terms which are k k k -distant from a node i i i appear in the k k k -element in the expansion, where their contribution is weakened by an inverse factorial of k k k . G ( k ) \mathcal{G}^{(k)} G ( k ) brings their contribution to the leading term, and thus as a renormalization procedure its acts an amplifier that effectively brings O ( ε ) O(\varepsilon) O ( ε ) terms to O ( 1 ) O(1) O ( 1 ) .
structures using Equation (4) , which provides additional features for the nodes dictated by the behavior of the heat kernel of G ( k ) \mathcal{G}^{(k)} G ( k ) . The updated signature includes those of G d \mathcal{G}^{d} G d , where d d d here is the diameter of the matrix. An illustration is shown in Figure 8 . This resolved the orbits of sts-15 which were differentiated by the signature of G \mathcal{G} G , G 2 \mathcal{G}^{2} G 2 , L ( G ) L(\mathcal{G}) L ( G ) , and L ( G ) 2 L(\mathcal{G})^{2} L ( G ) 2 since the graph has d = 2 d=2 d = 2 , which is shown in the right pane of Figure 5 ; it was also solved using the Dirac operator on G \mathcal{G} G and G 2 \mathcal{G}^{2} G 2 only. At this stage, we were cognizant of the prohibitive aspect of building the graph using L k ( G ) L^{k}(\mathcal{G}) L k ( G ) , where k k k is the line graph order, which grows like ( N 2 ) k (N^{2})^{k} ( N 2 ) k . Two very hard graphs brought about a serious challenge that we had to face, for which a new strategy had to be devised.
Figure 8. The colors of the nodes of G \mathcal{G} G are shown together with G 2 \mathcal{G}^{2} G 2 , which is now added to the data structure of the signatures.
In Section “One direction of invariance” of the Appendix, we prove that vertices in the same orbit of G \mathcal{G} G receive equal signatures under all the constructions described above. Thus, unequal signatures certify that two vertices belong to different orbits, although equal signatures need not imply that they belong to the same orbit.
The unyielding graphs and the probing that defeats them
In this section, we report on the details of the two graphs which resisted our algorithm and had an uncompromising stiffness against any attempt to identify their orbits. These are had-52 (hadarmard-52 with N = 208 N=208 N = 208 ), and pp-9-2 (projective plane with N = 182 N=182 N = 182 ).
The first, shown in Figure 9 , has two orbits. Nodes that belong to the first orbit are colored in dark blue, while those that belong to the second are colored in green. When a representative node from each orbit is considered as a root, the colors of their BFS ordering clearly distinguish them. In addition, the colors of their edges further serve as identifiers of the orbits. This is what one would expect the signature to capture; alas, it does not. Our failing signature concatenated the kernels of G \mathcal{G} G , G 2 \mathcal{G}^{2} G 2 , L ( G ) \mathcal{L}(\mathcal{G}) L ( G ) , L ( G ) 2 \mathcal{L}(\mathcal{G})^{2} L ( G ) 2 , the correlations, and the Dirac operators that incorrectly lumped all the nodes in one equivalence class. Obviously, L ( L ( G ) ) \mathcal{L}(\mathcal{L}(\mathcal{G})) L ( L ( G )) pushed our graph size to ∼ N 4 \sim N^{4} ∼ N 4 , prohibiting the computation of the kernel at a cost of ∼ ( N 4 ) 3 = N 12 \sim(N^{4})^{3}=N^{12} ∼ ( N 4 ) 3 = N 12 . A different strategy to break it started to brew.
Figure 9. The real orbits of Hadamard-52 as they should be detected. The signatures fail to distinguish them and lumps them all in one orbit with similar node and edge signatures.
The second graph, pp-9-2, shown in Figure 10 has four orbits, a singleton, an orbit with 10 nodes, and two others. Again, it resisted our thus far invincible signatures, which in this case went to a depth of d = 3 d=3 d = 3 , concatenating G \mathcal{G} G , G 2 \mathcal{G}^{2} G 2 , G 3 \mathcal{G}^{3} G 3 L ( G ) \mathcal{L}(\mathcal{G}) L ( G ) , L ( G ) 2 \mathcal{L}(\mathcal{G})^{2} L ( G ) 2 , L ( G ) 3 \mathcal{L}(\mathcal{G})^{3} L ( G ) 3 , correlations, and the Dirac operators. This failure, which also lumped all the nodes in the same equivalence class, provided a ferment for another orbit identification strategy.
Figure 10. The orbits of pp-9-2 are shown in the figure lying in three planes along with a singleton orbit colored in dark orange.
Given these two very challenging graphs, we resorted to probing schemes. In particular, we describe the ones that hammered away these two graphs’ resistance: the folding scheme and the neighborhood deletion.
In order to distinguish vertices with identical signatures, we introduce probing techniques that apply temporary modifications to the graph and recompute signatures on the resulting graphs. These modifications aim to reveal structural differences that are not captured by the original signatures, allowing the separation of vertices belonging to distinct orbits.
Let G = ( V , E ) G=(V,E) G = ( V , E ) be a graph, and let τ G ( u ) \tau_G(u) τ G ( u ) denote the signature of a vertex u ∈ V u \in V u ∈ V . For each vertex u u u , a probing technique generates a collection of modified graphs G 1 ′ , G 2 ′ , … , G m ′ G'_1,G'_2,\ldots,G'_m G 1 ′ , G 2 ′ , … , G m ′ . Each modified graph G i ′ G'_i G i ′ contributes a signature value s i ( u ) s_i(u) s i ( u ) to the probing profile of u u u . Depending on the probing technique, these values may be derived from the signature of u u u itself or from the signatures of other vertices in the modified graph. The probing profile is defined as
P ( u ) = sort ( s 1 ( u ) , s 2 ( u ) , … , s m ( u ) ) , (35) P(u)=\operatorname{sort}(s_1(u),s_2(u),\ldots,s_m(u)), \tag*{(35)} P ( u ) = sort ( s 1 ( u ) , s 2 ( u ) , … , s m ( u )) , (35)
where sorting ensures that the profile is independent of the order in which the signatures are collected, while preserving repeated values. Probing is applied independently to each equivalence class of the current vertex partition. For each class, a probing profile is constructed for every vertex, and vertices are separated into new classes according to their profiles.
Our implementation supports several probing techniques. We describe below the techniques used in our experiments, each applied to a selected vertex u ∈ V u \in V u ∈ V . The remaining supported techniques are detailed in Appendix B.
Folding selects M ≥ 1 M \ge1 M ≥ 1 disjoint subsets S 1 , … , S M ⊆ V S_1,\ldots,S_M \subseteq V S 1 , … , S M ⊆ V , each containing p ≥ 2 p \ge2 p ≥ 2 vertices, with u ∈ S 1 u \in S_1 u ∈ S 1 . The vertices of each subset are merged into a single vertex, combining their incident edges and removing self-loops and duplicate edges. The subset containing u u u is represented by u u u in the modified graph. All possible selections of such disjoint subsets are considered, and the resulting signatures τ G ′ ( u ) \tau_{G'}(u) τ G ′ ( u ) are collected to construct P ( u ) P(u) P ( u ) . This strategy, for p = 2 p = 2 p = 2 , resolved the orbits of had-52, which is shown in Figure 11 . Note that the nodes’ signatures were indistinguishable before probing. The resulting signatures of folding two nodes of the same orbit, and two nodes of different orbits yield very distinct signatures, leading to the recovery of the correct colors.
Figure 11. The figure is an illustration of the folding procedure. When the two-nodes folding probe is applied, the resulting signatures allow to distinguish the orbit. The colors of the edges incident to a node of the first orbit are different from those incident to a node in the second.
Neighborhood deletion selects a subset S ⊆ V S \subseteq V S ⊆ V of p ≥ 2 p \ge2 p ≥ 2 vertices containing u u u . Let
N [ S ] = ⋃ v ∈ S ( N ( v ) ∪ { v } ) . N[S] = \bigcup_{v \in S} (N(v) \cup\{v\}). N [ S ] = v ∈ S ⋃ ( N ( v ) ∪ { v }) .
Remove all vertices in N [ S ] N[S] N [ S ] , then reintroduce u u u and connect it to every remaining vertex. An optional parameter d max d_{\max} d m a x restricts the selected vertices to be pairwise within distance d max d_{\max} d m a x . The profile P ( u ) P(u) P ( u ) collects τ G ′ ( u ) \tau_{G'}(u) τ G ′ ( u ) over all valid selections of S S S . This strategy resolved the orbits of pp-9-2 for p = 3 p = 3 p = 3 and d = 2 d = 2 d = 2 , with a sample deleted neighborhood shown in Figure 12 .
Figure 12. The neighborhood deletion probe is illustrated. The figure shows the correctly resolved orbits for pp-9-2, with three sample nodes, a a a , b b b , and v v v along with their neighborhoods N ( a ) \mathcal{N}(a) N ( a ) , N ( b ) \mathcal{N}(b) N ( b ) , and N ( v ) \mathcal{N}(v) N ( v ) . The resulting deleted neighborhood is also shown.
Complexity of the final algorithm
Having introduced the individual components of our signature construction, we now combine them into a unified hierarchical refinement procedure for our experimental evaluation. The procedure incrementally strengthens the vertex signatures by incorporating spectral operators, graph transformations, and probing strategies, allowing us to assess the contribution of each component to refining the vertex partition. Algorithm 1 summarizes this procedure, in which each stage preserves the distinctions established by the preceding stages 1 .
We analyze the worst-case time and space complexity of our approach by examining its main computational components. We first consider vertex signature construction using the Laplacian heat kernel, Dirac operator, and correlation matrix. We then examine how these operations scale across the original graph and its successive distance-based and line-graph transformations, including signature aggregation and partition refinement. Finally, we analyze the probing techniques and combine the results to derive the overall bounds for our algorithm.
Let G = ( V , E ) \mathcal{G}=(V,E) G = ( V , E ) denote a graph processed by the algorithm, with N = ∣ V ∣ N=|V| N = ∣ V ∣ vertices and M = ∣ E ∣ M=|E| M = ∣ E ∣ edges. Let T T T denote the number of sampled time points for time-dependent operators. We assume fixed-precision arithmetic and standard dense linear algebra, where eigendecomposition, matrix inversion, pseudoinversion, and multiplication of two dense matrices require O ( d 3 ) O(d^3) O ( d 3 ) time and O ( d 2 ) O(d^2) O ( d 2 ) space. We assume comparison-based sorting with O ( d log d ) O(d\log d) O ( d log d ) worst-case time for d d d scalar values. All-pairs shortest-path distances are computed using SciPy’s Floyd–Warshall algorithm, requiring O ( N 3 ) O(N^3) O ( N 3 ) time and O ( N 2 ) O(N^2) O ( N 2 ) space.
For the Laplacian heat kernel, computing the eigendecomposition of its N × N N\times N N × N matrix requires O ( N 3 ) O(N^3) O ( N 3 ) time and O ( N 2 ) O(N^2) O ( N 2 ) space. At each of the T T T sampled time points, computing the full heat-kernel matrix rows requires O ( N 3 ) O(N^3) O ( N 3 ) time. Computing all-pairs shortest-path distances requires O ( N 3 ) O(N^3) O ( N 3 ) time, while sorting the heat-kernel matrix rows based on these distances requires O ( N 2 log N ) O(N^2\log N) O ( N 2 log N ) time per time point. Quantizing the entries and refining the vertex equivalence classes require an additional O ( N 2 log N ) O(N^2\log N) O ( N 2 log N ) time per time point. Since the remaining operations are dominated by the heat-kernel computations, the overall worst-case time complexity is O ( T N 3 ) O(TN^3) O ( T N 3 ) . The resulting signatures are then aggregated according to BFS layers. Performing BFS from every vertex requires O ( N ( N + M ) ) O(N(N+M)) O ( N ( N + M )) time. Since each raw signature has O ( T N ) O(TN) O ( T N ) values, sorting these signatures within the BFS layers requires at most O ( T N 3 log N ) O(TN^3\log N) O ( T N 3 log N ) time across all vertices. Therefore, the overall worst-case time complexity, including BFS aggregation, is BFS aggregation, is
O ( T N 3 log N ) . O(TN^3\log N). O ( T N 3 log N ) .
For Laplacian space complexity, the implementation stores the heat-kernel values across all T T T sampled time points, requiring O ( T N 2 ) O(TN^2) O ( T N 2 ) space. The eigendecomposition, distance matrix, and intermediate matrices require an additional O ( N 2 ) O(N^2) O ( N 2 ) space. BFS aggregation reuses the stored raw signatures rather than duplicating their values, requiring at most O ( N 2 ) O(N^2) O ( N 2 ) additional space for the references across all vertices. Therefore, the overall worst-case space complexity is
O ( T N 2 + N 2 ) = O ( T N 2 ) . O(TN^2 + N^2) = O(TN^2). O ( T N 2 + N 2 ) = O ( T N 2 ) .
The Dirac matrix has dimension ( N + M ) × ( N + M ) (N + M) \times(N + M) ( N + M ) × ( N + M ) , and computing its eigendecomposition requires O ( ( N + M ) 3 ) O((N + M)^3) O (( N + M ) 3 ) time and O ( ( N + M ) 2 ) O((N + M)^2) O (( N + M ) 2 ) space. At each of the T T T sampled time points, constructing the full Dirac kernel requires O ( ( N + M ) 3 ) O((N + M)^3) O (( N + M ) 3 ) time. To construct the vertex signatures, the kernel entries corresponding to each vertex are divided into two groups: N N N vertex-to-vertex entries and M M M vertex-to-edge entries. The quantized real and imaginary value pairs are sorted lexicographically within each group separately, and both sorted groups are retained as components of the vertex signature. Similarly, each edge signature is constructed by separately sorting its N N N edge-to-vertex entries and M M M edge-to-edge entries. These components are collected across all T T T time points to form the initial vertex and edge signatures. Sorting the two groups for a single vertex or edge requires O ( N log N + M log M ) O(N \log N + M \log M) O ( N log N + M log M ) time. Since there are N N N vertices and M M M edges, the total sorting time per time point is
O ( ( N + M ) ( N log N + M log M ) ) = O ( ( N + M ) 2 log ( N + M ) ) . O((N + M)(N \log N + M \log M)) = O((N + M)^2 \log(N + M)). O (( N + M ) ( N log N + M log M )) = O (( N + M ) 2 log ( N + M )) .
After processing all time points, each vertex collects and lexicographically sorts the complete signatures of its incident edges. For a vertex v v v , sorting its deg ( v ) \deg(v) deg ( v ) edge signatures requires O ( deg ( v ) log deg ( v ) ) O(\deg(v)\log\deg(v)) O ( deg ( v ) log deg ( v )) comparisons. Since deg ( v ) ≤ N − 1 \deg(v) \le N - 1 deg ( v ) ≤ N − 1 , this is bounded by O ( deg ( v ) log N ) O(\deg(v)\log N) O ( deg ( v ) log N ) . Summing over all vertices and using ∑ v ∈ V deg ( v ) = 2 M \sum_{v\in V} \deg(v) = 2M ∑ v ∈ V deg ( v ) = 2 M , the total number of comparisons is
O ( ∑ v ∈ V deg ( v ) log N ) = O ( M log N ) . O\left(\sum_{v\in V} \deg(v) \log N\right) = O(M \log N). O ( v ∈ V ∑ deg ( v ) log N ) = O ( M log N ) .
Each comparison may examine up to O ( T ( N + M ) ) O(T(N + M)) O ( T ( N + M )) values, and the overall sorting time is O ( T M ( N + M ) log N ) O(TM(N + M)\log N) O ( T M ( N + M ) log N ) . Since the sorting operations are bounded by the kernel computations, the overall time complexity of constructing the raw Dirac signatures is
O ( T ( N + M ) 3 ) . O(T(N + M)^3). O ( T ( N + M ) 3 ) .
Algorithm 1 Hierarchical signature-based orbit refinement
Require: Graph $G = (V, E)$, maximum line-graph order $J$, probing strategies $\mathcal{Q}$, true orbits $\mathcal{O}$
Ensure: Refined vertex partition $\Pi$
1: $\Pi \leftarrow \{V\}$
2: $\mathcal{A} \leftarrow \{\text{Laplacian}, \text{Correlation}, \text{Dirac}\}$
3: for $j = 0$ to $J$ do
4: $H \leftarrow L^j(G)$
5: for $d = 1$ to $\operatorname{diameter}(H)$ do
6: $S \leftarrow$ distance-$d$ graph of $H$
7: for all $a \in \mathcal{A}$ do
8: $\sigma \leftarrow$ Spectral signatures on $S$ using $a$
9: $\Pi \leftarrow \operatorname{Refine}(\Pi, \sigma)$
10: if $\Pi = \mathcal{O}$ then
11: return $\Pi$
12: for all $q \in \mathcal{Q}$ do
13: $\sigma \leftarrow$ Correlation signatures on $S$ using probing technique $q$
14: $\Pi \leftarrow \operatorname{Refine}(\Pi, \sigma)$
15: if $\Pi = \mathcal{O}$ then
16: return $\Pi$
17: return $\Pi$
The resulting signatures are then aggregated according to BFS layers. Performing BFS from every vertex requires O ( N ( N + M ) ) O(N(N + M)) O ( N ( N + M )) time. Each raw Dirac vertex signature contains its own kernel entries and the signatures of its incident edges, giving at most O ( T N ( N + M ) ) O(TN(N + M)) O ( T N ( N + M )) values. Comparing two such signatures may therefore require O ( T N ( N + M ) ) O(TN(N + M)) O ( T N ( N + M )) time. Since sorting the BFS layers requires at most O ( N 2 log N ) O(N^2 \log N) O ( N 2 log N ) comparisons across all vertices, the overall time complexity, including BFS aggregation, is
O ( T ( N + M ) 3 + T N 3 ( N + M ) log N ) = O ( T ( N 6 + N 5 log N ) ) = O ( T N 6 ) , \begin{aligned}
O\left(T(N + M)^3 + TN^3(N + M)\log N\right)\\
= O\left(T(N^6 + N^5\log N)\right)\\
= O(TN^6),
\end{aligned} O ( T ( N + M ) 3 + T N 3 ( N + M ) log N ) = O ( T ( N 6 + N 5 log N ) ) = O ( T N 6 ) ,
where the simplification follows from M = O ( N 2 ) M = O(N^2) M = O ( N 2 ) for simple graphs.
For Dirac space complexity, storing the raw vertex and edge signatures across all T T T sampled time points requires O ( T ( N + M ) 2 ) O(T(N + M)^2) O ( T ( N + M ) 2 ) space. The incident-edge signatures and BFS aggregation reuse the stored signature values without duplicating them, requiring at most O ( N 2 ) O(N^2) O ( N 2 ) additional space for references.For space complexity, storing the raw vertex and edge signatures across all T T T sampled time points requires O ( T ( N + M ) 2 ) O(T(N + M)^2) O ( T ( N + M ) 2 ) space. The incident-edge signatures and BFS aggregation reuse the stored signature values without duplicating them, requiring at most O ( N 2 ) O(N^2) O ( N 2 ) additional space. Since M = O ( N 2 ) M = O(N^2) M = O ( N 2 ) for simple graphs, the overall worst-case space complexity simplifies to
O ( T ( N + M ) 2 ) = O ( T N 4 ) . O(T(N + M)^2) = O(TN^4). O ( T ( N + M ) 2 ) = O ( T N 4 ) .
As for the correlation matrix, computing the pseudoinverse of the N × N N \times N N × N Laplacian matrix requires O ( N 3 ) O(N^3) O ( N 3 ) time and O ( N 2 ) O(N^2) O ( N 2 ) space. Computing all-pairs shortest-path distances requires O ( N 3 ) O(N^3) O ( N 3 ) time, while sorting the correlation matrix rows according to these distances requires O ( N 2 log N ) O(N^2 \log N) O ( N 2 log N ) time. Since these operations are bounded by the pseudoinverse and shortest-path computations, constructing the raw correlation signatures requires O ( N 3 ) O(N^3) O ( N 3 ) time.
The resulting signatures are then aggregated according to BFS layers. Performing BFS from every vertex requires O ( N ( N + M ) ) = O ( N 3 ) O(N(N+M)) = O(N^3) O ( N ( N + M )) = O ( N 3 ) time. For each vertex, at most N N N raw signatures are sorted across its layers, requiring O ( N log N ) O(N\log N) O ( N log N ) comparisons. Since each signature contains O ( N ) O(N) O ( N ) values, each comparison may take O ( N ) O(N) O ( N ) time, giving O ( N 2 log N ) O(N^2\log N) O ( N 2 log N ) time per vertex. Across all N N N vertices, the overall worst-case time complexity, including BFS aggregation, is
O ( N 3 log N ) . O(N^3\log N). O ( N 3 log N ) .
For the correlation space complexity, storing the correlation matrix, shortest-path distances, and intermediate matrices requires O ( N 2 ) O(N^2) O ( N 2 ) space. BFS aggregation organizes the existing raw signatures into distance layers without duplicating their values, requiring at most O ( N 2 ) O(N^2) O ( N 2 ) additional space. Therefore, the overall worst-case space complexity is
Each distance graph G i \mathcal{G}_i G i preserves the original N N N vertices, with edges connecting pairs of vertices at distance exactly i i i , having at most ( N 2 ) = O ( N 2 ) \binom{N}{2}=O(N^2) ( 2 N ) = O ( N 2 ) edges. Constructing G i \mathcal{G}_i G i requires O ( N 2 ) O(N^2) O ( N 2 ) additional time and space. Thus, the overall time and space complexities of constructing a single distance graph are O ( N 3 ) O(N^3) O ( N 3 ) and O ( N 2 ) O(N^2) O ( N 2 ) , respectively.
For line graph constructions, each edge of G \mathcal{G} G becomes a vertex in L ( G ) L(\mathcal{G}) L ( G ) , giving ∣ V ( L ( G ) ) ∣ = M = O ( N 2 ) |V(L(\mathcal{G}))|=M=O(N^2) ∣ V ( L ( G )) ∣ = M = O ( N 2 ) . Two vertices in L ( G ) L(\mathcal{G}) L ( G ) are adjacent if their corresponding edges in G \mathcal{G} G share an endpoint. Thus, each vertex v ∈ V v\in V v ∈ V contributes ( deg ( v ) 2 ) \binom{\deg(v)}{2} ( 2 d e g ( v ) ) edges to L ( G ) L(\mathcal{G}) L ( G ) . Since G \mathcal{G} G is a simple graph, deg ( v ) ≤ N − 1 \deg(v)\le N-1 deg ( v ) ≤ N − 1 for every vertex. Therefore,
∣ E ( L ( G ) ) ∣ = ∑ v ∈ V ( deg ( v ) 2 ) ≤ ∑ v ∈ V ( N − 1 2 ) = N ( N − 1 2 ) = O ( N 3 ) . |E(L(\mathcal{G}))|=\sum_{v\in V}\binom{\deg(v)}{2}\le\sum_{v\in V}\binom{N-1}{2}=N\binom{N-1}{2}=O(N^3). ∣ E ( L ( G )) ∣ = v ∈ V ∑ ( 2 deg ( v ) ) ≤ v ∈ V ∑ ( 2 N − 1 ) = N ( 2 N − 1 ) = O ( N 3 ) .
More generally, for any fixed i ≥ 0 i\ge0 i ≥ 0 , the iterated line graph L i ( G ) L^i(\mathcal{G}) L i ( G ) has at most O ( N i + 1 ) O(N^{i+1}) O ( N i + 1 ) vertices and O ( N i + 2 ) O(N^{i+2}) O ( N i + 2 ) edges.
We analyze the spectral complexity across graph transformations by considering the successive line graphs L i ( G ) L^i(\mathcal{G}) L i ( G ) and their corresponding distance graphs. Let ℓ \ell ℓ denote the maximum line-graph order considered by the algorithm. At each order 0 ≤ i ≤ ℓ 0\le i\le\ell 0 ≤ i ≤ ℓ , the algorithm applies the spectral operators to L i ( G ) L^i(\mathcal{G}) L i ( G ) and its distance graphs ( L i ( G ) ) j (L^i(\mathcal{G}))_j ( L i ( G ) ) j , where 1 ≤ j ≤ D i 1\le j\le D_i 1 ≤ j ≤ D i and D i D_i D i is the diameter of L i ( G ) L^i(\mathcal{G}) L i ( G ) . We use j = 1 j=1 j = 1 to represent L i ( G ) L^i(\mathcal{G}) L i ( G ) itself, so i = 0 i=0 i = 0 and j = 1 j=1 j = 1 corresponds to the original graph G \mathcal{G} G . Let N i N_i N i denote the number of vertices in L i ( G ) L^i(\mathcal{G}) L i ( G ) and T i , j T_{i,j} T i , j the maximum number of sampled time points across the time-dependent operators at that stage. Using the previously established bounds for the Laplacian heat kernel, Dirac operator, and correlation matrix, the total time complexity of the spectral evaluations across all transformations is
O ( ∑ i = 0 ℓ ∑ j = 1 D i [ T i , j N i 3 log N i + T i , j N i 6 + N i 3 log N i ] ) . O\left(\sum_{i=0}^{\ell}\sum_{j=1}^{D_i}\left[T_{i,j}N_i^3\log N_i+T_{i,j}N_i^6+N_i^3\log N_i\right]\right). O ( i = 0 ∑ ℓ j = 1 ∑ D i [ T i , j N i 3 log N i + T i , j N i 6 + N i 3 log N i ] ) .
Since the Dirac operator has the highest asymptotic time complexity among the three operators, this simplifies to
O ( ∑ i = 0 ℓ ∑ j = 1 D i T i , j N i 6 ) . O\left(\sum_{i=0}^{\ell}\sum_{j=1}^{D_i}T_{i,j}N_i^6\right). O ( i = 0 ∑ ℓ j = 1 ∑ D i T i , j N i 6 ) .
Using D i = O ( N i ) D_i = O(N_i) D i = O ( N i ) and N i = O ( N i + 1 ) N_i = O(N^{i+1}) N i = O ( N i + 1 ) , the worst-case time complexity for fixed ℓ \ell ℓ can be further bounded as
= O ( T max ∑ i = 0 ℓ D i N i 6 ) = O ( T max ∑ i = 0 ℓ N i 7 ) = O ( T max ∑ i = 0 ℓ N 7 i + 7 ) = O ( T max N 7 ℓ + 7 ) = O\left(T_{\max}\sum_{i=0}^{\ell} D_iN_i^6\right) = O\left(T_{\max}\sum_{i=0}^{\ell} N_i^7\right) = O\left(T_{\max}\sum_{i=0}^{\ell} N^{7i+7}\right) = O(T_{\max}N^{7\ell+7}) = O ( T m a x i = 0 ∑ ℓ D i N i 6 ) = O ( T m a x i = 0 ∑ ℓ N i 7 ) = O ( T m a x i = 0 ∑ ℓ N 7 i + 7 ) = O ( T m a x N 7 ℓ + 7 )
where T max T_{\max} T m a x denotes the maximum number of sampled time points across all stages.
Similarly, the Dirac operator has the largest space requirement. Since the operators and graph transformations are processed sequentially, the peak space complexity is determined by the largest spectral computation. Using the previously established Dirac bound, each stage requires at most O ( T i , j N i 4 ) O(T_{i,j}N_i^4) O ( T i , j N i 4 ) space. Since N i = O ( N i + 1 ) N_i = O(N^{i+1}) N i = O ( N i + 1 ) , the overall worst-case space complexity for fixed ℓ \ell ℓ is
O ( T max N 4 ℓ + 4 ) . O(T_{\max}N^{4\ell+4}). O ( T m a x N 4 ℓ + 4 ) .
We analyze the probing techniques applied to the original graph G \mathcal{G} G following spectral refinement. Let C ⊆ V C \subseteq V C ⊆ V denote the selected unresolved vertex class, with ∣ C ∣ = N |C| = N ∣ C ∣ = N in the worst case. For each probed vertex u ∈ C u \in C u ∈ C , a probing technique constructs a set of temporarily modified versions of graphs G \mathcal{G} G , and computes their vertex signatures using the correlation matrix to form the probing profile P ( u ) P(u) P ( u ) . Since each modified graph has at most N N N vertices, computing its signatures requires O ( N 3 log N ) = O ( N 4 ) O(N^3 \log N) = O(N^4) O ( N 3 log N ) = O ( N 4 ) time and O ( N 2 ) O(N^2) O ( N 2 ) working space.
Folding considers M M M disjoint groups of size p p p , with the first group containing the probed vertex u u u . Since the order of the additional groups and the vertices within each group does not matter, the number of possible modifications per vertex is
F ( N , p , M ) = ( N − 1 p − 1 ) ( N − p ) ! ( N − M p ) ! ( p ! ) M − 1 ( M − 1 ) ! . F(N,p,M) = \binom{N-1}{p-1}\frac{(N-p)!}{(N-Mp)!(p!)^{M-1}(M-1)!}. F ( N , p , M ) = ( p − 1 N − 1 ) ( N − M p )! ( p ! ) M − 1 ( M − 1 )! ( N − p )! .
Expanding the binomial coefficient gives
F ( N , p , M ) = ( N − 1 ) ! ( p − 1 ) ! ( N − M p ) ! ( p ! ) M − 1 ( M − 1 ) ! . F(N,p,M) = \frac{(N-1)!}{(p-1)!(N-Mp)!(p!)^{M-1}(M-1)!}. F ( N , p , M ) = ( p − 1 )! ( N − M p )! ( p ! ) M − 1 ( M − 1 )! ( N − 1 )! .
For fixed p p p and M M M , this gives O ( N M p − 1 ) O(N^{Mp-1}) O ( N M p − 1 ) modifications per vertex. Each modified graph has N − M ( p − 1 ) N - M(p-1) N − M ( p − 1 ) vertices, and computing its correlation-based signatures requires at most O ( N 4 ) O(N^4) O ( N 4 ) time. Considering all N N N vertices, the overall worst-case time complexity is
O ( N ⋅ N M p − 1 ⋅ N 4 ) = O ( N M p + 4 ) . O(N \cdot N^{Mp-1} \cdot N^4) = O(N^{Mp+4}). O ( N ⋅ N M p − 1 ⋅ N 4 ) = O ( N M p + 4 ) .
For space complexity, each modification contributes one signature containing at most O ( N 2 ) O(N^2) O ( N 2 ) values to the probing profile of the selected vertex. Since each vertex has O ( N M p − 1 ) O(N^{Mp-1}) O ( N M p − 1 ) possible modifications, storing the profiles for all N N N vertices requires
O ( N ⋅ N M p − 1 ⋅ N 2 ) = O ( N M p + 2 ) O(N \cdot N^{Mp-1} \cdot N^2) = O(N^{Mp+2}) O ( N ⋅ N M p − 1 ⋅ N 2 ) = O ( N M p + 2 )
space.
Neighborhood deletion instead selects a group of p p p vertices including the probed vertex u u u , giving at most ( N − 1 p − 1 ) \binom{N-1}{p-1} ( p − 1 N − 1 ) possible modifications. Restrictions on the distances between selected vertices may reduce this number. For fixed p p p , this corresponds to O ( N p − 1 ) O(N^{p-1}) O ( N p − 1 ) modifications per vertex, or O ( N p ) O(N^p) O ( N p ) modifications across all N N N vertices. Since each modified graph has at most N N N vertices and computing its correlation-based signatures requires O ( N 4 ) O(N^4) O ( N 4 ) time, the overall worst-case time complexity is
O ( N p ⋅ N 4 ) = O ( N p + 4 ) . O(N^p \cdot N^4) = O(N^{p+4}). O ( N p ⋅ N 4 ) = O ( N p + 4 ) .
For space complexity, each probing profile stores at most ( N − 1 p − 1 ) = O ( N p − 1 ) \binom{N-1}{p-1}=O(N^{p-1}) ( p − 1 N − 1 ) = O ( N p − 1 ) signatures, each containing at most O ( N 2 ) O(N^2) O ( N 2 ) entries. Considering all N N N vertices, the space required to store the probing profiles is
O ( N ⋅ N p − 1 ⋅ N 2 ) = O ( N p + 2 ) . O(N\cdot N^{p-1}\cdot N^2)=O(N^{p+2}). O ( N ⋅ N p − 1 ⋅ N 2 ) = O ( N p + 2 ) .
Node deletion requires only one modification per probed vertex, obtained by removing that vertex and its incident edges. Computing the signatures of the remaining N − 1 N-1 N − 1 vertices requires O ( N 3 ) O(N^3) O ( N 3 ) time. Sorting these signatures does not increase the asymptotic bound. Since the procedure is repeated for all N N N vertices, the overall worst-case time complexity is
O ( N ⋅ N 4 ) = O ( N 5 ) . O(N\cdot N^4)=O(N^5). O ( N ⋅ N 4 ) = O ( N 5 ) .
For space complexity, each probing profile stores the BFS-aggregated signatures of the N − 1 N-1 N − 1 remaining vertices. Each signature contains at most O ( N ) O(N) O ( N ) references to raw correlation signatures, whose underlying values are shared rather than duplicated. Therefore, storing one probing profile requires O ( N 2 ) O(N^2) O ( N 2 ) space, and retaining the profiles for all N N N probed vertices requires O ( N 3 ) O(N^3) O ( N 3 ) space.
Results
To evaluate the effectiveness of the proposed hierarchy in recovering automorphism orbits, we compare the partition induced by the computed signatures with the true automorphism-orbit partition of each graph, obtained using nauty and Traces [21 ] . We use two evaluation metrics: normalized mutual information (NMI) and an orbit-compatibility score P P P . NMI measures the overall similarity between the computed and true orbit partitions, with a value of 1 indicating an exact match. However, NMI does not directly capture the usefulness of the computed classes for graph isomorphism testing, which is an intended future application of our signature library. To complement NMI, we introduce an orbit-compatibility score P P P , which evaluates how reliably vertices grouped into the same signature class belong to the same true automorphism orbit. Specifically, for a given signature class, we consider the probability that two vertices independently and uniformly selected from that class belong to the same orbit.
We evaluated the proposed hierarchy on benchmark graphs drawn from several structurally distinct families, including grids, Hadamard and projective-plane graphs, Steiner triple-system graphs, and the MZ, USR, Latin-SW, CHH, and F-LEX families. The simplest stage of the hierarchy already suffices for many instances, without recourse to graph transformations or probing. For example, the G \mathcal{G} G -Laplacian signature recovers the 19 orbit classes of kef10, which has 200 vertices, and the 325 classes of grid-2-50, which has 2,500 vertices. The appendix documents analogous exact recovery for numerous members of the grid, CHH, TNN, and other benchmark families. These examples demonstrate that the more expensive stages are not invariably necessary. At the same time, success on a graph with only one orbit, such as a vertex-transitive graph, should not be confused with distinguishing power: the more demanding tests are those in which several true orbits are initially merged by the signatures.
Table 1 collects a selection of such instances. The initial number of classes is that obtained from the G \mathcal{G} G -Laplacian signature, and the listed method is the first stage in the tested sequence at which the exact orbit partition is recovered. We display the number of recovered orbits and the corresponding k k k -WL result, while the complete progression of intermediate classes, NMI and P P P values remains in the appendix.
The distinctions in Table 1 are informative about what each additional stage contributes. For usr(1)_29-1 and sts-13, the Laplacian and correlation signatures each yield a single class, whereas the Dirac stage recovers, respectively, 13 and two orbits. For sts-15, neither the original-graph Dirac signature nor the Laplacian and correlation signatures of the distance-two graph distinguish its two orbits; the distance-two Dirac signature does. In latin-sw-10-2, the original-graph Dirac signature yields 99 classes instead of the 100 singleton orbits, and the distance-two Dirac stage resolves the remaining pair. A different benefit of distance transformations appears in mz-4: the first two distance levels leave 16 classes, while the distance-three Laplacian signature recovers all 20 orbits. Thus, increasing the information retained by the signatures can yield successive, and sometimes very fine, refinements of the partition.
Table 1. Representative benchmark instances requiring different stages of the signature hierarchy. “Initial classes” refers to the G \mathcal{G} G -Laplacian partition; “orbits” gives the number of classes in the recovered orbit partition. All listed successful stages attain NMI = P = 1 = P = 1 = P = 1 . The k k k -WL column gives the smallest tested dimension recovering the orbit partition; > 3 > 3 > 3 denotes failure for k ≤ 3 k \le3 k ≤ 3 , and – denotes an unreported value. The appendix gives the full results and probe parameters.
The most demanding examples in the table require a change of strategy. In had-52, the combined spectral signatures leave all 208 vertices in one class, whereas folding pairs of vertices separates its two orbits. In pp-9-2, the spectral constructions on the original graph, its distance graphs, and the tested line-graph transformations likewise leave a single class; neighborhood deletion with p = 3 p = 3 p = 3 and distance restriction d = 2 d = 2 d = 2 recovers all four orbits. Neighborhood deletion also resolves the 42 orbits of had-sw-32-1 and refines the 141 initial classes of f-lex-reg-10-1 into its 175 true orbits. These examples illustrate why probing is not merely an optional embellishment of the spectral hierarchy: in the tested instances, controlled modifications reveal distinctions that remain hidden in the unmodified graphs.
The comparison with k k k -WL addresses the same vertex-orbit recovery task. The reported k k k -WL values show that usr(1)_29-1, sts-13, and sts-15 require dimension four among those tested, while had-52, pp-9-2, and had-sw-32-1 are not resolved at any of dimensions one through three. Nevertheless, their exact orbit partitions are recovered by the spectral or probing stages indicated in Table 1 . This establishes the distinguishing power of the proposed signatures on particular examples that resist low-dimensional WL refinement. It does not imply a universal superiority over k k k -WL, nor does successful recovery alone establish an advantage in running time.
Finally, the observed effectiveness must be read alongside the numerical and computational limitations of the method. The detailed tables include numerical resolutions, so the reported partitions depend on the stated comparison settings. Moreover, Dirac computations, graph transformations, and exhaustive probing may be substantially more expensive than the initial Laplacian stage, as discussed in the complexity analysis. The experiments therefore support a hierarchy that succeeds on the tested benchmark instances, including some for which low-dimensional k k k -WL fails, without establishing completeness on arbitrary graphs or a general polynomial-time orbit-identification algorithm.
Conclusion
We return to the question with which we began. On a network, the automorphism group is the group of transformations that leave the interaction structure invariant, and its orbits are the classes of vertices that no symmetry can distinguish. Recovering those orbits is therefore the precise form of a physical question: which parts of a network are genuinely equivalent, and which merely look alike to the local probes available? The hierarchy we have developed answers this question incrementally, separating what can be resolved by spectral data from what requires controlled intervention in the graph. Its success on instances that resist WL refinement is evidence that the symmetry-based description of a physical system, which in statistical physics organizes phases and collective behavior, can be made operational for discrete, complex networks, not as a single diagnostic, but as a graded sequence of tests whose information content can be read from the partition it produces. The limitations are equally part of the result: the method is empirically successful on the tested families, its later stages are computationally non-trivial, and a general polynomial-time procedure for orbit identification remains out of reach. These are the boundaries within which the symmetry-based description of networks is, at present, a practical tool.
Acknowledgements
Mohamad Al Sayed received support as a research assistant from the Complexity and Network Science Cluster, Rana Dbouk also received support through the Complexity and Network Science Cluster and the University Research Board. Joe Germany is grateful for helpful discussions with Prof. Siamak Taati.
Proofs
In the below, let G \mathcal{G} G be a finite simple undirected graph on n n n vertices, with Laplacian L = D − A L = D - A L = D − A . We write the heat kernel and the correlation matrices as
K ( t ) = e − t L , C r = ( L + r I ) − 1 , (36) K(t) = e^{-tL}, \qquad C_r = (L + rI)^{-1}, \tag*{(36)} K ( t ) = e − t L , C r = ( L + r I ) − 1 , (36)
with the softening parameter r > 0 r > 0 r > 0 .
Counterexamples
We first prove a counterexample to our first algorithm, which involving only the values of the diagonal.
Theorem A.1. Let G \mathcal{G} G be the Frucht graph with the vertex labeling returned by nx.frucht_graph(). Vertices 1 and 10 belong to different orbits, but
K 1 , 1 ( t ) = K 10 , 10 ( t ) , t ≥ 0. (37) K_{1,1}(t) = K_{10,10}(t), \qquad t \ge0. \tag*{(37)} K 1 , 1 ( t ) = K 10 , 10 ( t ) , t ≥ 0. (37) Thus, the diagonal heat-kernel signatures do not distinguish their orbits.
Proof. The graph has 12 vertices. Computing L 0 , … , L 11 L^0,\ldots,L^{11} L 0 , … , L 11 gives
( ( L m ) 1 , 1 ) m = 0 11 = ( ( L m ) 10 , 10 ) m = 0 11 = ( 1 , 3 , 12 , 52 , 234 , 1078 , 5054 , 24034 , \begin{aligned}
\left((L^m)_{1,1}\right)_{m=0}^{11} = \left((L^m)_{10,10}\right)_{m=0}^{11} \\
&= (1,3,12,52,234,1078,5054,24034,
\end{aligned} ( ( L m ) 1 , 1 ) m = 0 11 = ( ( L m ) 10 , 10 ) m = 0 11 = ( 1 , 3 , 12 , 52 , 234 , 1078 , 5054 , 24034 ,
115660 , 562230 , 2756552 , 13614304 ) . (38) 115660,562230,2756552,13614304). \tag*{(38)} 115660 , 562230 , 2756552 , 13614304 ) . (38)
By Cayley–Hamilton, for every integer s ≥ 0 s \ge0 s ≥ 0 , there are coefficients c s , 0 , … , c s , 11 c_{s,0},\ldots,c_{s,11} c s , 0 , … , c s , 11 such that
L s = ∑ m = 0 11 c s , m L m . (39) L^s = \sum_{m=0}^{11} c_{s,m}L^m. \tag*{(39)} L s = m = 0 ∑ 11 c s , m L m . (39)
Consequently,
( L s ) 1 , 1 − ( L s ) 10 , 10 = ∑ m = 0 11 c s , m ( ( L m ) 1 , 1 − ( L m ) 10 , 10 ) = 0. (40) (L^s)_{1,1} - (L^s)_{10,10} = \sum_{m=0}^{11} c_{s,m}\left((L^m)_{1,1} - (L^m)_{10,10}\right) = 0. \tag*{(40)} ( L s ) 1 , 1 − ( L s ) 10 , 10 = m = 0 ∑ 11 c s , m ( ( L m ) 1 , 1 − ( L m ) 10 , 10 ) = 0. (40)
Using the exponential representation of the heat kernel, we obtain
K 1 , 1 ( t ) − K 10 , 10 ( t ) = ∑ s = 0 ∞ ( − t ) s s ! ( ( L s ) 1 , 1 − ( L s ) 10 , 10 ) = 0. (41) K_{1,1}(t) - K_{10,10}(t) = \sum_{s=0}^{\infty}\frac{(-t)^s}{s!}\left((L^s)_{1,1} - (L^s)_{10,10}\right) = 0. \tag*{(41)} K 1 , 1 ( t ) − K 10 , 10 ( t ) = s = 0 ∑ ∞ s ! ( − t ) s ( ( L s ) 1 , 1 − ( L s ) 10 , 10 ) = 0. (41)
To distinguish the orbits, let T T T be the set of vertices that belong to no triangle. For this labeling, we have
T = { 2 , 8 , 11 } , T = \{2,8,11\}, T = { 2 , 8 , 11 } ,
{ d ( 1 , j ) : j ∈ T } = { 1 , 2 , 2 } , \{d(1,j):j\in T\} = \{1,2,2\}, { d ( 1 , j ) : j ∈ T } = { 1 , 2 , 2 } ,
{ d ( 10 , j ) : j ∈ T } = { 1 , 2 , 3 } . (42) \{d(10,j):j\in T\} = \{1,2,3\}. \tag*{(42)} { d ( 10 , j ) : j ∈ T } = { 1 , 2 , 3 } . (42)
An automorphism preserves triangles and distances, and therefore maps T T T onto itself. If it mapped 1 to 10, the last two collections would be equal. Hence 1 and 10 belong to different orbits.
This next proof proves a counterexample to our algorithm that treats signatures as the full sorted rows of the heat kernel, without BFS.
Theorem A.2. Let G \mathcal{G} G be the s t s sts s t s -13 graph on 26 vertices, with labels 0, … \ldots … , 25, obtained from the nauty dataset [44 ] . Vertices 0 and 3 belong to different orbits, but
sort ( K 0 j ( t ) : j ∈ V ) = sort ( K 3 j ( t ) : j ∈ V ) , t ≥ 0. (43) \operatorname{sort}(K_{0j}(t):j\in V)=\operatorname{sort}(K_{3j}(t):j\in V),\qquad t\ge0. \tag*{(43)} sort ( K 0 j ( t ) : j ∈ V ) = sort ( K 3 j ( t ) : j ∈ V ) , t ≥ 0. (43) Proof. Let π \pi π be the permutation given by
( π ( 0 ) , … , π ( 25 ) ) = ( 3 , 0 , 1 , 2 , 4 , 5 , 7 , 9 , 6 , 8 , 12 , 10 , 13 , 11 , 14 , 15 , 18 , 21 , 22 , 16 , 23 , 17 , 19 , 20 , 25 , 24 ) . (44) (\pi(0),\ldots,\pi(25))=(3,0,1,2,4,5,7,9,6,8,12,10,13,11,14,15,18,21,22,16,23,17,19,20,25,24). \tag*{(44)} ( π ( 0 ) , … , π ( 25 )) = ( 3 , 0 , 1 , 2 , 4 , 5 , 7 , 9 , 6 , 8 , 12 , 10 , 13 , 11 , 14 , 15 , 18 , 21 , 22 , 16 , 23 , 17 , 19 , 20 , 25 , 24 ) . (44) Computing the first 26 powers of L L L gives
( L m ) 0 j = ( L m ) 3 , π ( j ) , j ∈ V , m = 0 , … , 25. (45) (L^m)_{0j}=(L^m)_{3,\pi(j)},\qquad j\in V,\quad m=0,\ldots,25. \tag*{(45)} ( L m ) 0 j = ( L m ) 3 , π ( j ) , j ∈ V , m = 0 , … , 25. (45) The same permutation π \pi π is used for every power. By Cayley–Hamilton, for every integer s ≥ 0 s\ge0 s ≥ 0 , we can write
L s = ∑ m = 0 25 c s , m L m . (46) L^s=\sum_{m=0}^{25}c_{s,m}L^m. \tag*{(46)} L s = m = 0 ∑ 25 c s , m L m . (46) Thus, for every j ∈ V j\in V j ∈ V ,
( L s ) 0 j − ( L s ) 3 , π ( j ) = ∑ m = 0 25 c s , m ( ( L m ) 0 j − ( L m ) 3 , π ( j ) ) = 0. (47) (L^s)_{0j}-(L^s)_{3,\pi(j)}=\sum_{m=0}^{25}c_{s,m}\left((L^m)_{0j}-(L^m)_{3,\pi(j)}\right)=0. \tag*{(47)} ( L s ) 0 j − ( L s ) 3 , π ( j ) = m = 0 ∑ 25 c s , m ( ( L m ) 0 j − ( L m ) 3 , π ( j ) ) = 0. (47) It follows that
K 0 j ( t ) − K 3 , π ( j ) ( t ) = ∑ s = 0 ∞ ( − t ) s s ! ( ( L s ) 0 j − ( L s ) 3 , π ( j ) ) = 0. (48) K_{0j}(t)-K_{3,\pi(j)}(t)=\sum_{s=0}^{\infty}\frac{(-t)^s}{s!}\left((L^s)_{0j}-(L^s)_{3,\pi(j)}\right)=0. \tag*{(48)} K 0 j ( t ) − K 3 , π ( j ) ( t ) = s = 0 ∑ ∞ s ! ( − t ) s ( ( L s ) 0 j − ( L s ) 3 , π ( j ) ) = 0. (48) Since π \pi π is a permutation, sorting the two rows gives (43) . Now let q ( i ) q(i) q ( i ) be the number of four-vertex cliques containing i i i . Each such clique consists of i i i and three pairwise adjacent neighbors. Enumerating these triples gives
q ( 0 ) = 73 , q ( 3 ) = 71. (49) q(0)=73,\qquad q(3)=71. \tag*{(49)} q ( 0 ) = 73 , q ( 3 ) = 71. (49) An automorphism mapping 0 to 3 would map the cliques containing 0 bijectively onto those containing 3. Since the counts differ, the two vertices belong to different orbits.
The same s t s sts s t s -13 graph is still a counterexample to the algorithm that incorporates both inner and outer BFS signatures.
Theorem A.3. Let G \mathcal{G} G be the same labeled s t s sts s t s -13 graph. Its inner and outer BFS heat-kernel signatures satisfy
sig G , i n t e r ( v ) ( t ) = sig G , i n t e r ( 0 ) ( t ) , v ∈ V , t ≥ 0 , \operatorname{sig}_{\mathcal{G},\mathrm{inter}}(v)(t)=\operatorname{sig}_{\mathcal{G},\mathrm{inter}}(0)(t),\qquad v\in V,\quad t\ge0, sig G , inter ( v ) ( t ) = sig G , inter ( 0 ) ( t ) , v ∈ V , t ≥ 0 , sig G ( v ) = sig G ( 0 ) , v ∈ V , (50) \operatorname{sig}_{\mathcal{G}}(v)=\operatorname{sig}_{\mathcal{G}}(0),\qquad v\in V, \tag*{(50)} sig G ( v ) = sig G ( 0 ) , v ∈ V , (50) for any common choice of sampling times and outer BFS depth. In particular, both signatures assign equal values to vertices 0 and 3, although these vertices belong to different orbits.
Proof. For every v ∈ V v \in V v ∈ V , the exact computation gives a permutation π v : V → V \pi_v: V \to V π v : V → V such that
d ( 0 , j ) = d ( v , π v ( j ) ) , ( L m ) 0 j = ( L m ) v , π v ( j ) , m = 0 , … , 25. (51) \begin{aligned}
d(0,j) &= d(v,\pi_v(j)),\\
(L^m)_{0j} &= (L^m)_{v,\pi_v(j)}, \qquad m=0,\ldots,25. \tag*{(51)}
\end{aligned} d ( 0 , j ) ( L m ) 0 j = d ( v , π v ( j )) , = ( L m ) v , π v ( j ) , m = 0 , … , 25. (51)
for every j ∈ V j \in V j ∈ V . These permutations are obtained by matching the vectors ( ( L m ) 0 j ) m = 0 25 \left((L^m)_{0j}\right)_{m=0}^{25} ( ( L m ) 0 j ) m = 0 25 with the corresponding vectors at v v v , within equal distance layers. The accompanying script checks both equalities directly. Each π v \pi_v π v is fixed for all 26 powers. For v = 3 v=3 v = 3 , we may take the permutation in (44).
By Cayley–Hamilton, for every integer s ≥ 0 s \ge0 s ≥ 0 , there are coefficients c s , 0 , … , c s , 25 c_{s,0},\ldots,c_{s,25} c s , 0 , … , c s , 25 such that
L s = ∑ m = 0 25 c s , m L m . (52) L^s = \sum_{m=0}^{25} c_{s,m}L^m. \tag*{(52)} L s = m = 0 ∑ 25 c s , m L m . (52)
Consequently,
( L s ) 0 j − ( L s ) v , π v ( j ) = ∑ m = 0 25 c s , m ( ( L m ) 0 j − ( L m ) v , π v ( j ) ) = 0. (53) (L^s)_{0j}-(L^s)_{v,\pi_v(j)}
=\sum_{m=0}^{25}c_{s,m}\left((L^m)_{0j}-(L^m)_{v,\pi_v(j)}\right)=0. \tag*{(53)} ( L s ) 0 j − ( L s ) v , π v ( j ) = m = 0 ∑ 25 c s , m ( ( L m ) 0 j − ( L m ) v , π v ( j ) ) = 0. (53)
Using the exponential representation of the heat kernel gives
K 0 j ( t ) − K v , π v ( j ) ( t ) = ∑ s = 0 ∞ ( − t ) s s ! ( ( L s ) 0 j − ( L s ) v , π v ( j ) ) = 0 , t ≥ 0. (54) \begin{aligned}
K_{0j}(t)-K_{v,\pi_v(j)}(t)
&=\sum_{s=0}^{\infty}\frac{(-t)^s}{s!}\left((L^s)_{0j}-(L^s)_{v,\pi_v(j)}\right)\\
&=0,\qquad t\ge0. \tag*{(54)}
\end{aligned} K 0 j ( t ) − K v , π v ( j ) ( t ) = s = 0 ∑ ∞ s ! ( − t ) s ( ( L s ) 0 j − ( L s ) v , π v ( j ) ) = 0 , t ≥ 0. (54)
First, consider the inner BFS signature. Since d ( v , π v ( 0 ) ) = d ( 0 , 0 ) = 0 d(v,\pi_v(0))=d(0,0)=0 d ( v , π v ( 0 )) = d ( 0 , 0 ) = 0 , we have π v ( 0 ) = v \pi_v(0)=v π v ( 0 ) = v , and hence
K 00 ( t ) = K v v ( t ) . (55) K_{00}(t)=K_{vv}(t). \tag*{(55)} K 00 ( t ) = K v v ( t ) . (55)
Moreover, π v \pi_v π v maps the distance-d d d layer of 0 bijectively onto the distance-d d d layer of v v v . Thus, for every d ≥ 1 d \ge1 d ≥ 1 ,
{ K 0 j ( t ) : d ( 0 , j ) = d } = { K v , π v ( j ) ( t ) : d ( 0 , j ) = d } = { K v ℓ ( t ) : d ( v , ℓ ) = d } . (56) \begin{aligned}
\{K_{0j}(t):d(0,j)=d\}
&=\{K_{v,\pi_v(j)}(t):d(0,j)=d\}\\
&=\{K_{v\ell}(t):d(v,\ell)=d\}. \tag*{(56)}
\end{aligned} { K 0 j ( t ) : d ( 0 , j ) = d } = { K v , π v ( j ) ( t ) : d ( 0 , j ) = d } = { K v ℓ ( t ) : d ( v , ℓ ) = d } . (56)
The diagonal entries agree, and the entries in each corresponding layer agree with multiplicity. Sorting within the layers and concatenating them therefore gives
sig G , i n t e r ( 0 ) ( t ) = sig G , i n t e r ( v ) ( t ) , v ∈ V , t ≥ 0. (57) \operatorname{sig}_{G,\mathrm{inter}}(0)(t)
=\operatorname{sig}_{G,\mathrm{inter}}(v)(t),\qquad v\in V,\quad t\ge0. \tag*{(57)} sig G , inter ( 0 ) ( t ) = sig G , inter ( v ) ( t ) , v ∈ V , t ≥ 0. (57)
For any common sampling times t 0 , … , t T t_0,\ldots,t_T t 0 , … , t T , it follows that
sig G , i n t e r ( 0 ) = ( sig G , i n t e r ( 0 ) ( t a ) ) a = 0 T = ( sig G , i n t e r ( v ) ( t a ) ) a = 0 T = sig G , i n t e r ( v ) . (58) \begin{aligned}
\operatorname{sig}_{G,\mathrm{inter}}(0)
&=\left(\operatorname{sig}_{G,\mathrm{inter}}(0)(t_a)\right)_{a=0}^{T}\\
&=\left(\operatorname{sig}_{G,\mathrm{inter}}(v)(t_a)\right)_{a=0}^{T}
=\operatorname{sig}_{G,\mathrm{inter}}(v). \tag*{(58)}
\end{aligned} sig G , inter ( 0 ) = ( sig G , inter ( 0 ) ( t a ) ) a = 0 T = ( sig G , inter ( v ) ( t a ) ) a = 0 T = sig G , inter ( v ) . (58)
In particular, the inner BFS signatures of 0 and 3 agree.
Now consider the outer BFS signature. The preceding equality holds at every vertex, so, for every j ∈ V j \in V j ∈ V ,
sig G , i n t e r ( j ) = sig G , i n t e r ( π v ( j ) ) . (59) \operatorname{sig}_{G,\mathrm{inter}}(j)
=\operatorname{sig}_{G,\mathrm{inter}}(\pi_v(j)). \tag*{(59)} sig G , inter ( j ) = sig G , inter ( π v ( j )) . (59)
Using the same distance-layer bijection π v \pi_v π v , we obtain
{ sig G , i n t e r ( j ) : d ( 0 , j ) = d } = { sig G , i n t e r ( π v ( j ) ) : d ( 0 , j ) = d } = { sig G , i n t e r ( ℓ ) : d ( v , ℓ ) = d } . (60) \begin{aligned}
\{\operatorname{sig}_{\mathcal{G},\mathrm{inter}}(j) : d(0,j)=d\}
&= \{\operatorname{sig}_{\mathcal{G},\mathrm{inter}}(\pi_v(j)) : d(0,j)=d\} \\
&= \{\operatorname{sig}_{\mathcal{G},\mathrm{inter}}(\ell) : d(v,\ell)=d\}. \tag*{(60)}
\end{aligned} { sig G , inter ( j ) : d ( 0 , j ) = d } = { sig G , inter ( π v ( j )) : d ( 0 , j ) = d } = { sig G , inter ( ℓ ) : d ( v , ℓ ) = d } . (60)
Thus each corresponding outer layer contains the same number of copies of the common intermediary signature. For any depth b b b ,
sig G ( 0 ) = ( sort ( sig G , i n t e r ( j ) : d ( 0 , j ) = d ) ) d = 0 b = ( sort ( sig G , i n t e r ( ℓ ) : d ( v , ℓ ) = d ) ) d = 0 b = sig G ( v ) . (61) \begin{aligned}
\operatorname{sig}_{\mathcal{G}}(0)
&= \left(\operatorname{sort}(\operatorname{sig}_{\mathcal{G},\mathrm{inter}}(j) : d(0,j)=d)\right)_{d=0}^{b} \\
&= \left(\operatorname{sort}(\operatorname{sig}_{\mathcal{G},\mathrm{inter}}(\ell) : d(v,\ell)=d)\right)_{d=0}^{b}
= \operatorname{sig}_{\mathcal{G}}(v). \tag*{(61)}
\end{aligned} sig G ( 0 ) = ( sort ( sig G , inter ( j ) : d ( 0 , j ) = d ) ) d = 0 b = ( sort ( sig G , inter ( ℓ ) : d ( v , ℓ ) = d ) ) d = 0 b = sig G ( v ) . (61)
This includes the root layer and any empty layers beyond the maximum distance. Hence the outer BFS signatures of 0 and 3 also agree. However, (49) gives q ( 0 ) = 73 q(0)=73 q ( 0 ) = 73 and q ( 3 ) = 71 q(3)=71 q ( 3 ) = 71 , so the two vertices belong to different orbits. Therefore both the inner and outer BFS signatures fail to recover the vertex-orbit partition of G \mathcal{G} G .
The same counterexamples hold for the corresponding correlation signatures. Indeed, each entry equality above holds under a fixed matching for every t ≥ 0 t \ge0 t ≥ 0 , so
( C r ) i j − ( C r ) k ℓ = ∫ 0 ∞ e − r t ( K i j ( t ) − K k ℓ ( t ) ) d t = 0 , r > 0. (62) (C_r)_{ij}-(C_r)_{k\ell}=\int_{0}^{\infty}e^{-rt}\left(K_{ij}(t)-K_{k\ell}(t)\right)\,dt=0,\qquad r>0. \tag*{(62)} ( C r ) ij − ( C r ) k ℓ = ∫ 0 ∞ e − r t ( K ij ( t ) − K k ℓ ( t ) ) d t = 0 , r > 0. (62)
The same matchings therefore apply within every BFS layer.
They also apply to the pseudoinverse L † L^\dagger L † used by the implementation. For any finite graph, let λ 1 , … , λ q \lambda_1,\ldots,\lambda_q λ 1 , … , λ q be its distinct nonzero Laplacian eigenvalues. Polynomial interpolation gives a polynomial p p p of degree at most q ≤ n − 1 q\le n-1 q ≤ n − 1 with p ( 0 ) = 0 p(0)=0 p ( 0 ) = 0 and p ( λ a ) = 1 / λ a p(\lambda_a)=1/\lambda_a p ( λ a ) = 1/ λ a . By the spectral theorem,
L † = p ( L ) = ∑ m = 0 n − 1 a m L m . (63) L^\dagger=p(L)=\sum_{m=0}^{n-1}a_mL^m. \tag*{(63)} L † = p ( L ) = m = 0 ∑ n − 1 a m L m . (63)
Every finite-power equality verified above therefore gives the corresponding equality of pseudoinverse entries. This uses no additional property of the counterexample graphs. It does not assert that the single matrix L † L^\dagger L † has the same distinguishing power as the family ( L + r I ) − 1 (L+rI)^{-1} ( L + r I ) − 1 for all r > 0 r>0 r > 0 .
Finally, the other graphs (sts-15, pp-9-2, had-52) that guide the storyline above can also be explicitly proved to be counterexamples to each iteration of the algorithm based on the same proof machinery.
One direction of invariance
In this section, we show that vertices in the same orbit of G \mathcal{G} G receive equal signatures.
We first show that vertices in the same orbit of G \mathcal{G} G remain in the same orbit of each distance graph G ( i ) \mathcal{G}^{(i)} G ( i ) .
Proposition A.1. Let G = ( V , E ) \mathcal{G}=(V,E) G = ( V , E ) be a graph on n n n vertices, and let u , v ∈ V u,v\in V u , v ∈ V . If u u u and v v v are in the same orbit in G \mathcal{G} G , then they are in the same orbit in G ( i ) \mathcal{G}^{(i)} G ( i ) for all i ∈ { 1 , … , n } i\in\{1,\ldots,n\} i ∈ { 1 , … , n } .
Proof. If u u u and v v v belong to the same vertex orbit of the graph G \mathcal{G} G , then there exists an automorphism f f f such that f ( u ) = v f(u)=v f ( u ) = v . We claim that f f f is also an automorphism of G ( i ) \mathcal{G}^{(i)} G ( i ) for every i ∈ { 1 , … , n } i\in\{1,\ldots,n\} i ∈ { 1 , … , n } . Let x , y ∈ V x,y \in V x , y ∈ V be connected by a path. Since f f f preserves adjacency, it maps a shortest path from x x x to y y y to a path of the same length from f ( x ) f(x) f ( x ) to f ( y ) f(y) f ( y ) . Therefore,
d G ( f ( x ) , f ( y ) ) ≤ d G ( x , y ) . (64) d_{\mathcal{G}}(f(x),f(y)) \le d_{\mathcal{G}}(x,y). \tag*{(64)} d G ( f ( x ) , f ( y )) ≤ d G ( x , y ) . (64)
Applying the same argument to f − 1 f^{-1} f − 1 gives
d G ( x , y ) ≤ d G ( f ( x ) , f ( y ) ) . (65) d_{\mathcal{G}}(x,y) \le d_{\mathcal{G}}(f(x),f(y)). \tag*{(65)} d G ( x , y ) ≤ d G ( f ( x ) , f ( y )) . (65)
Thus,
d G ( f ( x ) , f ( y ) ) = d G ( x , y ) . (66) d_{\mathcal{G}}(f(x),f(y)) = d_{\mathcal{G}}(x,y). \tag*{(66)} d G ( f ( x ) , f ( y )) = d G ( x , y ) . (66)
If x x x and y y y are disconnected, so are f ( x ) f(x) f ( x ) and f ( y ) f(y) f ( y ) ; otherwise, f − 1 f^{-1} f − 1 would map a path between their images to a path between x x x and y y y .
By the definition of G ( i ) \mathcal{G}^{(i)} G ( i ) , two vertices are adjacent in G ( i ) \mathcal{G}^{(i)} G ( i ) if and only if their distance in G \mathcal{G} G is i i i . Hence,
{ x , y } ∈ E ( G ( i ) ) ⟺ d G ( x , y ) = i ⟺ d G ( f ( x ) , f ( y ) ) = i ⟺ { f ( x ) , f ( y ) } ∈ E ( G ( i ) ) . (67) \begin{aligned}
\{x,y\} \in E(\mathcal{G}^{(i)}) &\Longleftrightarrow d_{\mathcal{G}}(x,y)=i \\
&\Longleftrightarrow d_{\mathcal{G}}(f(x),f(y))=i \\
&\Longleftrightarrow\{f(x),f(y)\} \in E(\mathcal{G}^{(i)}). \tag*{(67)}
\end{aligned} { x , y } ∈ E ( G ( i ) ) ⟺ d G ( x , y ) = i ⟺ d G ( f ( x ) , f ( y )) = i ⟺ { f ( x ) , f ( y )} ∈ E ( G ( i ) ) . (67)
Since f f f is a bijection of V V V , it is an automorphism of G ( i ) \mathcal{G}^{(i)} G ( i ) . Moreover, f ( u ) = v f(u)=v f ( u ) = v , so u u u and v v v belong to the same orbit in G ( i ) \mathcal{G}^{(i)} G ( i ) , for every i ∈ { 1 , … , n } i \in\{1,\ldots,n\} i ∈ { 1 , … , n } . □
An individual distance graph can therefore merge original orbits, but cannot split them. For example, the path 0–1–2–3 has orbits { 0 , 3 } \{0,3\} { 0 , 3 } and { 1 , 2 } \{1,2\} { 1 , 2 } , whereas its distance-2 graph consists of the two edges { 0 , 2 } \{0,2\} { 0 , 2 } and { 1 , 3 } \{1,3\} { 1 , 3 } and has a single vertex orbit. The permutations preserving the whole family, including G ( 1 ) \mathcal{G}^{(1)} G ( 1 ) , are exactly the automorphisms of G \mathcal{G} G .
Theorem A.4. Let G = ( V , E ) \mathcal{G}=(V,E) G = ( V , E ) and u , v ∈ V u,v \in V u , v ∈ V . If u u u and v v v belong to the same orbit in G \mathcal{G} G , then
sig G ( u ) = sig G ( v ) . (68) \operatorname{sig}_{\mathcal{G}}(u)=\operatorname{sig}_{\mathcal{G}}(v). \tag*{(68)} sig G ( u ) = sig G ( v ) . (68) This holds for the heat-kernel, correlation, and Dirac signatures, including their combinations on distance and iterated line graphs, with common settings, sampling times, and comparison parameters. The matrix entries are exact before rounding or truncation, and any relative-norm threshold is positive. The Dirac signatures are independent of the chosen edge orientations.
Proof. If u u u and v v v belong to the same vertex orbit of G \mathcal{G} G , then there exists an automorphism f f f such that f ( u ) = v f(u)=v f ( u ) = v . We claim that sig G ( x ) = sig G ( f ( x ) ) \operatorname{sig}_{\mathcal{G}}(x)=\operatorname{sig}_{\mathcal{G}}(f(x)) sig G ( x ) = sig G ( f ( x )) for every x ∈ V x \in V x ∈ V .
Since f f f preserves adjacency and degrees, L f ( x ) , f ( y ) = L x y L_{f(x),f(y)}=L_{xy} L f ( x ) , f ( y ) = L x y . Induction on m m m gives ( L m ) f ( x ) , f ( y ) = ( L m ) x y (L^m)_{f(x),f(y)}=(L^m)_{xy} ( L m ) f ( x ) , f ( y ) = ( L m ) x y , and hence
K f ( x ) , f ( y ) ( t ) = ∑ m = 0 ∞ ( − t ) m m ! ( L m ) f ( x ) , f ( y ) = K x y ( t ) . (69) K_{f(x),f(y)}(t)=\sum_{m=0}^{\infty}\frac{(-t)^m}{m!}(L^m)_{f(x),f(y)}=K_{xy}(t). \tag*{(69)} K f ( x ) , f ( y ) ( t ) = m = 0 ∑ ∞ m ! ( − t ) m ( L m ) f ( x ) , f ( y ) = K x y ( t ) . (69)
The same entry equality holds for the correlation L † L^\dagger L † used in the code, since L † L^\dagger L † is a polynomial in L L L , and for C r = ( L + r I ) − 1 C_r=(L+rI)^{-1} C r = ( L + r I ) − 1 , r > 0 r>0 r > 0 , by uniqueness of the inverse. Moreover, f f f maps each distance layer around x x x bijectively onto the corresponding layer around f ( x ) f(x) f ( x ) . Thus the diagonal, sorted full-row, and inner BFS constructions give
sig G , i n t e r ( x ) ( t ) = sig G , i n t e r ( f ( x ) ) ( t ) . (70) \operatorname{sig}_{\mathcal{G},\mathrm{inter}}(x)(t)=\operatorname{sig}_{\mathcal{G},\mathrm{inter}}(f(x))(t). \tag*{(70)} sig G , inter ( x ) ( t ) = sig G , inter ( f ( x )) ( t ) . (70)
This remains true after common scalar rounding or truncation and concatenation in time order. For the Dirac construction, extend f f f to edges by f ( { a , b } ) = { f ( a ) , f ( b ) } f(\{a,b\})=\{f(a),f(b)\} f ({ a , b }) = { f ( a ) , f ( b )} . Set ε x = 1 \varepsilon_x=1 ε x = 1 for x ∈ V x\in V x ∈ V and ε e = 1 \varepsilon_e=1 ε e = 1 or − 1 -1 − 1 according as f f f preserves or reverses the chosen orientation of e e e . The incidence matrix then satisfies B f ( x ) , f ( e ) = ε e B x e B_{f(x),f(e)}=\varepsilon_eB_{xe} B f ( x ) , f ( e ) = ε e B x e . Therefore
( D m ) f ( x ) , f ( y ) = ε x ε y ( D m ) x y , x , y ∈ V ⊔ E , m ≥ 0. (71) (D^m)_{f(x),f(y)}=\varepsilon_x\varepsilon_y(D^m)_{xy},\qquad x,y\in V\sqcup E,\quad m\geq0. \tag*{(71)} ( D m ) f ( x ) , f ( y ) = ε x ε y ( D m ) x y , x , y ∈ V ⊔ E , m ≥ 0. (71)
Indeed, the equality holds for m = 0 , 1 m=0,1 m = 0 , 1 , and each intermediate index z z z in matrix multiplication contributes ε z 2 = 1 \varepsilon_z^2=1 ε z 2 = 1 . For U ( t ) = e i D t U(t)=e^{iDt} U ( t ) = e i D t , it follows that U f ( x ) , f ( y ) ( t ) = ε x ε y U x y ( t ) U_{f(x),f(y)}(t)=\varepsilon_x\varepsilon_yU_{xy}(t) U f ( x ) , f ( y ) ( t ) = ε x ε y U x y ( t ) , so
∣ Re U f ( x ) , f ( y ) ( t ) ∣ = ∣ Re U x y ( t ) ∣ , ∣ Im U f ( x ) , f ( y ) ( t ) ∣ = ∣ Im U x y ( t ) ∣ . (72) \begin{aligned}
\left|\operatorname{Re}U_{f(x),f(y)}(t)\right|&=\left|\operatorname{Re}U_{xy}(t)\right|,\\
\left|\operatorname{Im}U_{f(x),f(y)}(t)\right|&=\left|\operatorname{Im}U_{xy}(t)\right|. \tag*{(72)}
\end{aligned} Re U f ( x ) , f ( y ) ( t ) Im U f ( x ) , f ( y ) ( t ) = ∣ Re U x y ( t ) ∣ , = ∣ Im U x y ( t ) ∣ . (72)
Consequently, the pairs used in the code satisfy
p t ( x , y ) = ( round ( R ∣ Re U x y ( t ) ∣ ) , round ( R ∣ Im U x y ( t ) ∣ ) ) , p t ( f ( x ) , f ( y ) ) = p t ( x , y ) . (73) \begin{aligned}
p_t(x,y)&=\bigl(\operatorname{round}(R|\operatorname{Re}U_{xy}(t)|),\operatorname{round}(R|\operatorname{Im}U_{xy}(t)|)\bigr),\\
p_t(f(x),f(y))&=p_t(x,y). \tag*{(73)}
\end{aligned} p t ( x , y ) p t ( f ( x ) , f ( y )) = ( round ( R ∣ Re U x y ( t ) ∣ ) , round ( R ∣ Im U x y ( t ) ∣ ) ) , = p t ( x , y ) . (73)
The map f f f permutes the vertex and edge blocks separately. Sorting these pairs within each block and concatenating in time order therefore gives equal vertex signatures at x , f ( x ) x,f(x) x , f ( x ) and equal edge signatures at e , f ( e ) e,f(e) e , f ( e ) . Since x ∈ e x\in e x ∈ e if and only if f ( x ) ∈ f ( e ) f(x)\in f(e) f ( x ) ∈ f ( e ) , appending the sorted temporal signatures of incident edges also preserves equality. These Dirac blocks use no inner BFS. Using e − i D t e^{-iDt} e − i D t gives the same pairs, since it is the complex conjugate of U ( t ) U(t) U ( t ) .
For the Dirac correlation, the matrix
D μ = ( μ I B B T − μ I ) , μ ∈ R ∖ { 0 } , (74) D_\mu=\begin{pmatrix}\mu I&B\\B^{\mathsf{T}}&-\mu I\end{pmatrix},\qquad\mu\in\mathbb{R}\setminus\{0\}, \tag*{(74)} D μ = ( μ I B T B − μ I ) , μ ∈ R ∖ { 0 } , (74)
is invertible because its square has positive definite diagonal blocks μ 2 I + B B T \mu^2I+BB^{\mathsf{T}} μ 2 I + B B T and μ 2 I + B T B \mu^2I+B^{\mathsf{T}}B μ 2 I + B T B . It satisfies the same sign rule as D D D , and uniqueness of the inverse gives
( D μ − 1 ) f ( x ) , f ( y ) = ε x ε y ( D μ − 1 ) x y . (75) (D_\mu^{-1})_{f(x),f(y)}=\varepsilon_x\varepsilon_y(D_\mu^{-1})_{xy}. \tag*{(75)} ( D μ − 1 ) f ( x ) , f ( y ) = ε x ε y ( D μ − 1 ) x y . (75)
Thus the same absolute-value and sorting argument applies. Changing edge orientations multiplies each matrix entry by the corresponding row and column signs. The preceding calculation, without permuting indices, shows that the absolute real and imaginary parts, and hence both Dirac constructions, remain unchanged.
By Proposition A.1, f f f is an automorphism of every distance graph. It also induces an automorphism of the line graph, since
e ∩ e ′ ≠ ∅ ⟺ f ( e ) ∩ f ( e ′ ) ≠ ∅ . (76) e\cap e'\ne\varnothing\quad\Longleftrightarrow\quad f(e)\cap f(e')\ne\varnothing. \tag*{(76)} e ∩ e ′ = ∅ ⟺ f ( e ) ∩ f ( e ′ ) = ∅ . (76)
Repeating these arguments gives an automorphism f H f_H f H of every transformed graph H H H . The membership sets initially satisfy M G ( x ) = { x } M_G(x)=\{x\} M G ( x ) = { x } . A distance operation leaves them unchanged, and a line operation gives
M L ( H ) ( x ) = { { a , b } ∈ E ( H ) : a ∈ M H ( x ) or b ∈ M H ( x ) } . (77) M_{L(H)}(x)=\bigl\{\{a,b\}\in E(H):a\in M_H(x)\ \text{or}\ b\in M_H(x)\bigr\}. \tag*{(77)} M L ( H ) ( x ) = { { a , b } ∈ E ( H ) : a ∈ M H ( x ) or b ∈ M H ( x ) } . (77)
We claim that
f H ( M H ( x ) ) = M H ( f ( x ) ) . (78) f_H(M_H(x))=M_H(f(x)). \tag*{(78)} f H ( M H ( x )) = M H ( f ( x )) . (78)
This holds initially and is preserved by a distance operation. For a line operation, the induction hypothesis gives
{ a , b } ∈ M L ( H ) ( x ) ⟺ a ∈ M H ( x ) or b ∈ M H ( x ) ⟺ f H ( a ) ∈ M H ( f ( x ) ) or f H ( b ) ∈ M H ( f ( x ) ) ⟺ { f H ( a ) , f H ( b ) } ∈ M L ( H ) ( f ( x ) ) . (79) \begin{aligned}
\{a,b\} \in M_{L(H)}(x) &\Longleftrightarrow a \in M_H(x)\ \text{or}\ b \in M_H(x)\\
&\Longleftrightarrow f_H(a) \in M_H(f(x))\ \text{or}\ f_H(b) \in M_H(f(x))\\
&\Longleftrightarrow\{f_H(a),f_H(b)\} \in M_{L(H)}(f(x)). \tag*{(79)}
\end{aligned} { a , b } ∈ M L ( H ) ( x ) ⟺ a ∈ M H ( x ) or b ∈ M H ( x ) ⟺ f H ( a ) ∈ M H ( f ( x )) or f H ( b ) ∈ M H ( f ( x )) ⟺ { f H ( a ) , f H ( b )} ∈ M L ( H ) ( f ( x )) . (79)
Thus the claim holds after every transformation.
The preceding operator arguments on H H H give sig H , i n t e r ( y ) = sig H , i n t e r ( f H ( y ) ) \operatorname{sig}_{H,\mathrm{inter}}(y)=\operatorname{sig}_{H,\mathrm{inter}}(f_H(y)) sig H , inter ( y ) = sig H , inter ( f H ( y )) . Together with (78), this yields
sort ( sig H , i n t e r ( y ) : y ∈ M H ( x ) ) = sort ( sig H , i n t e r ( z ) : z ∈ M H ( f ( x ) ) ) . (80) \operatorname{sort}\bigl(\operatorname{sig}_{H,\mathrm{inter}}(y):y\in M_H(x)\bigr)
=
\operatorname{sort}\bigl(\operatorname{sig}_{H,\mathrm{inter}}(z):z\in M_H(f(x))\bigr). \tag*{(80)} sort ( sig H , inter ( y ) : y ∈ M H ( x ) ) = sort ( sig H , inter ( z ) : z ∈ M H ( f ( x )) ) . (80)
Concatenating over the prescribed settings and operators therefore gives
sig G , i n t e r ( x ) = sig G , i n t e r ( f ( x ) ) . (81) \operatorname{sig}_{G,\mathrm{inter}}(x)=\operatorname{sig}_{G,\mathrm{inter}}(f(x)). \tag*{(81)} sig G , inter ( x ) = sig G , inter ( f ( x )) . (81)
Equal arrays receive the same identifier, including in relative-norm mode, where their comparison distance is zero.
Finally, f f f preserves distances in the original graph, so for any common outer BFS depth b b b ,
sig G ( x ) = ( sort ( sig G , i n t e r ( y ) : d G ( x , y ) = d ) ) d = 0 b = sig G ( f ( x ) ) . (82) \operatorname{sig}_G(x)=\left(\operatorname{sort}\bigl(\operatorname{sig}_{G,\mathrm{inter}}(y):d_G(x,y)=d\bigr)\right)_{d=0}^{b}=\operatorname{sig}_G(f(x)). \tag*{(82)} sig G ( x ) = ( sort ( sig G , inter ( y ) : d G ( x , y ) = d ) ) d = 0 b = sig G ( f ( x )) . (82)
If outer BFS is disabled, the intermediary signatures already agree. Taking x = u x=u x = u and using f ( u ) = v f(u)=v f ( u ) = v proves the claim. □
The scalar quantization and comparison parameters must be common to all compared vertices. Floating-point errors in the matrix computations are not covered by the exact equalities above.
Heat kernel and correlation equivalence
We prove the following equivalence between the heat kernel for all time t ≥ 0 t\geq0 t ≥ 0 and the correlation for r > 0 r>0 r > 0 :
Theorem A.5. For any i , j , k , ℓ ∈ V i,j,k,\ell\in V i , j , k , ℓ ∈ V , the following statements are equivalent:
( K ( t ) ) i j = ( K ( t ) ) k ℓ (K(t))_{ij}=(K(t))_{k\ell} ( K ( t ) ) ij = ( K ( t ) ) k ℓ for all time t ≥ 0 t\geq0 t ≥ 0 ,
( C r ) i j = ( C r ) k ℓ (C_r)_{ij}=(C_r)_{k\ell} ( C r ) ij = ( C r ) k ℓ for every r > 0 r>0 r > 0 ,
( L m ) i j = ( L m ) k ℓ (L^m)_{ij}=(L^m)_{k\ell} ( L m ) ij = ( L m ) k ℓ for m = 0 , … , n − 1 m=0,\ldots,n-1 m = 0 , … , n − 1 .
Proof. We note that, since L L L is positive semidefinite, C r C_r C r is well defined for every r > 0 r>0 r > 0 ; it is the resolvent of − L -L − L at r r r .
First, assume (i). By the Laplace transform representation of the resolvent [45 Lemma 1.3.7] , we can write C r C_r C r as
C r = ∫ 0 ∞ e − r t K ( t ) d t . (83) C_r=\int_{0}^{\infty}e^{-rt}K(t)\,\mathrm{d}t. \tag*{(83)} C r = ∫ 0 ∞ e − r t K ( t ) d t . (83)
Taking entries gives
( C r ) i j − ( C r ) k ℓ = ∫ 0 ∞ e − r t ( K i j ( t ) − K k ℓ ( t ) ) d t . (84) (C_r)_{ij}-(C_r)_{k\ell}=\int_{0}^{\infty}e^{-rt}\bigl(K_{ij}(t)-K_{k\ell}(t)\bigr)\,\mathrm{d}t. \tag*{(84)} ( C r ) ij − ( C r ) k ℓ = ∫ 0 ∞ e − r t ( K ij ( t ) − K k ℓ ( t ) ) d t . (84)
from which it is obvious that (i) implies (ii).
Now, assume (ii). For r > λ max r > \lambda_{\max} r > λ m a x , the maximum eigenvalue of L L L , the resolvent can be represented as the Neumann series
C r = ( L + r I ) − 1 = ∑ m = 0 ∞ ( − 1 ) m r m + 1 L m , (85) C_r = (L + rI)^{-1} = \sum_{m=0}^{\infty} \frac{(-1)^m}{r^{m+1}} L^m, \tag*{(85)} C r = ( L + r I ) − 1 = m = 0 ∑ ∞ r m + 1 ( − 1 ) m L m , (85)
which converges absolutely [45 Proposition 1.2.7(b)] . Thus, by (ii), for r > λ max r > \lambda_{\max} r > λ m a x , we have
0 = ( C r ) i j − ( C r ) k ℓ = ∑ m = 0 ∞ ( − 1 ) m r m + 1 ( ( L m ) i j − ( L m ) k ℓ ) . (86) 0 = (C_r)_{ij} - (C_r)_{k\ell} = \sum_{m=0}^{\infty} \frac{(-1)^m}{r^{m+1}} \left((L^m)_{ij} - (L^m)_{k\ell}\right). \tag*{(86)} 0 = ( C r ) ij − ( C r ) k ℓ = m = 0 ∑ ∞ r m + 1 ( − 1 ) m ( ( L m ) ij − ( L m ) k ℓ ) . (86)
The series vanishes for all sufficiently small values of 1 / r 1/r 1/ r , so every coefficient is zero. In particular, ( L m ) i j = ( L m ) k ℓ (L^m)_{ij} = (L^m)_{k\ell} ( L m ) ij = ( L m ) k ℓ for all m = 0 , … , n − 1 m = 0,\ldots,n-1 m = 0 , … , n − 1 , proving (iii).
Finally, assume (iii). By Cayley-Hamilton, every power L m L^m L m is a linear combination of I , L , … , L n − 1 I,L,\ldots,L^{n-1} I , L , … , L n − 1 . For any s ≥ 0 s \ge0 s ≥ 0 , we have
( L s ) i j − ( L s ) k ℓ = ∑ m = 0 n − 1 c m ( ( L m ) i j − ( L m ) k ℓ ) = 0 , (87) (L^s)_{ij} - (L^s)_{k\ell} = \sum_{m=0}^{n-1} c_m\left((L^m)_{ij} - (L^m)_{k\ell}\right) = 0, \tag*{(87)} ( L s ) ij − ( L s ) k ℓ = m = 0 ∑ n − 1 c m ( ( L m ) ij − ( L m ) k ℓ ) = 0 , (87)
by the assumption. Thus, by the exponential representation of the heat kernel, we obtain
K i j ( t ) − K k ℓ ( t ) = ∑ s = 0 ∞ ( − t ) s s ! ( ( L s ) i j − ( L s ) k ℓ ) = 0 , (88) K_{ij}(t) - K_{k\ell}(t) = \sum_{s=0}^{\infty} \frac{(-t)^s}{s!}\left((L^s)_{ij} - (L^s)_{k\ell}\right) = 0, \tag*{(88)} K ij ( t ) − K k ℓ ( t ) = s = 0 ∑ ∞ s ! ( − t ) s ( ( L s ) ij − ( L s ) k ℓ ) = 0 , (88)
which is (i).
Additional probing techniques
Edge swapping. Given two edges ( a , b ) , ( c , d ) ∈ E (a,b),(c,d) \in E ( a , b ) , ( c , d ) ∈ E with four distinct endpoints, an edge swap removes these edges and replaces them with either ( a , c ) , ( b , d ) (a,c),(b,d) ( a , c ) , ( b , d ) or ( a , d ) , ( b , c ) (a,d),(b,c) ( a , d ) , ( b , c ) . The resulting edge set is
E ′ = ( E ∖ { ( a , b ) , ( c , d ) } ) ∪ { { ( a , c ) , ( b , d ) } , { ( a , d ) , ( b , c ) } . E' = \left(E \setminus\{(a,b),(c,d)\}\right) \cup
\begin{cases}
\{(a,c),(b,d)\},\\
\{(a,d),(b,c)\}.
\end{cases} E ′ = ( E ∖ {( a , b ) , ( c , d )} ) ∪ { {( a , c ) , ( b , d )} , {( a , d ) , ( b , c )} .
The parameter M ≥ 1 M \ge1 M ≥ 1 specifies the number of simultaneous swaps. To probe a vertex u u u , all valid combinations of M M M swaps are considered, requiring at least one removed edge to be incident to u u u . Swaps must involve distinct removed and added edges, with no edge removed in one swap and added in another. Furthermore, newly added edges must not exist in the original graph, and only modifications preserving connectivity are retained. The signatures τ G ′ ( u ) \tau_{G'}(u) τ G ′ ( u ) from all valid modified graphs are collected to construct P ( u ) P(u) P ( u ) .
Edge addition. Add M ≥ 1 M \ge1 M ≥ 1 non-existing edges simultaneously, requiring at least one to be incident to u u u . All possible combinations of M M M edges satisfying this condition are considered, and the signatures τ G ′ ( u ) \tau_{G'}(u) τ G ′ ( u ) of the resulting graphs are collected to construct P ( u ) P(u) P ( u ) .
Edge deletion. Remove M ≥ 1 M \ge1 M ≥ 1 existing edges simultaneously, requiring at least one to be incident to u u u . All possible combinations of M M M edges that satisfy this condition are considered, excluding modifications that disconnect the graph. The signatures τ G ′ ( u ) \tau_{G'}(u) τ G ′ ( u ) of the resulting graphs are collected to construct P ( u ) P(u) P ( u ) .
P ( u ) = sort ( { τ G ′ ( v ) : v ∈ V ∖ { u } } ) . P(u) = \operatorname{sort}\left(\{\tau_{G'}(v) : v \in V \setminus\{u\}\}\right). P ( u ) = sort ( { τ G ′ ( v ) : v ∈ V ∖ { u }} ) .
The k k k -dimensional Weisfeiler–Leman algorithm
The Weisfeiler–Leman (WL) algorithm is a combinatorial method based on iterative color refinement, commonly used in graph isomorphism testing and vertex-orbit identification. Color refinement starts by assigning colors to vertices according to their degrees and repeatedly refines these colors based on the multisets of colors of their neighbors. The process continues until the coloring stabilizes, producing a partition of vertices into color classes. The k k k -dimensional Weisfeiler–Leman algorithm (k k k -WL), outlined in Algorithm 2, generalizes this refinement procedure by assigning colors to ordered k k k -tuples of vertices. Color refinement corresponds to the one-dimensional variant (1-WL). Initially, each k k k -tuple is assigned a color based on its atomic type, defined as its equality pattern and the adjacency relations among its coordinates. At each iteration, the k k k -tuple is re-assigned a new color based on its previous color and the multiset of colors of the tuples obtained by replacing each of its coordinates, one at a time, with every vertex in the graph. For fixed k k k , the refinement maintains N k N^k N k tuple colors and examines O ( k N k + 1 ) O(kN^{k+1}) O ( k N k + 1 ) coordinate replacements per iteration, before accounting for the cost of encoding and comparing colors.
Algorithm 2 The k k k -dimensional Weisfeiler–Leman algorithm
Require: An uncolored, undirected graph G = ( V , E ) G = (V, E) G = ( V , E ) ; dimension k ≥ 1 k \ge1 k ≥ 1 .
Ensure: The stable coloring of V k V^k V k .
Initialization:
for all tuples v ˉ ∈ V k \bar{v} \in V^k v ˉ ∈ V k do
\ \ C [ v ˉ ] ← atp k ( v ˉ ) C[\bar{v}] \leftarrow\operatorname{atp}_k(\bar{v}) C [ v ˉ ] ← atp k ( v ˉ )
repeat
\ \ for all tuples v ˉ = ( v 1 , … , v k ) ∈ V k \bar{v} = (v_1, \ldots, v_k) \in V^k v ˉ = ( v 1 , … , v k ) ∈ V k do
\ \ \ \ M ← ∅ M \leftarrow\varnothing M ← ∅
\ \ \ \ for all vertices u ∈ V u \in V u ∈ V do
\ \ \ \ \ \ for i = 1 i = 1 i = 1 to k k k do
\ \ \ \ \ \ \ \ w ˉ ← ( v 1 , … , v i − 1 , u , v i + 1 , … , v k ) \bar{w} \leftarrow(v_1, \ldots, v_{i-1}, u, v_{i+1}, \ldots, v_k) w ˉ ← ( v 1 , … , v i − 1 , u , v i + 1 , … , v k )
\ \ \ \ \ \ \ \ c i ← C [ w ˉ ] c_i \leftarrow C[\bar{w}] c i ← C [ w ˉ ]
\ \ \ \ \ \ Add ( atp k + 1 ( v 1 , … , v k , u ) , c 1 , … , c k ) (\operatorname{atp}_{k+1}(v_1, \ldots, v_k, u), c_1, \ldots, c_k) ( atp k + 1 ( v 1 , … , v k , u ) , c 1 , … , c k ) to M M M
\ \ \ \ \ C n e w [ v ˉ ] ← ( C [ v ˉ ] , M ) C_{\mathrm{new}}[\bar{v}] \leftarrow(C[\bar{v}], M) C new [ v ˉ ] ← ( C [ v ˉ ] , M )
\ \ \ \ \ C ← C n e w C \leftarrow C_{\mathrm{new}} C ← C new
until the coloring stabilizes
return C C C
An optimized implementation computes the stabilized k k k -WL coloring in time O ( k 2 N k + 1 log N ) O(k^{2}N^{k+1}\log N) O ( k 2 N k + 1 log N ) , which is O ( N k + 1 log N ) O(N^{k+1}\log N) O ( N k + 1 log N ) for fixed k k k [46 ] . This bound covers the entire refinement until stabilization, rather than a single iteration. For 1-WL, the tighter bound O ( ( N + M ) log N ) O((N+M)\log N) O (( N + M ) log N ) is known, where M M M is the number of edges [47 ] .
Figure 13 illustrates two non-isomorphic graphs: the cycle C 6 C_6 C 6 and the disjoint union of two triangles, 2 K 3 2K_3 2 K 3 . Since both graphs are 2-regular, color refinement (1-WL) assigns the same color to all vertices in both graphs and therefore fails to distinguish them as graphs. As shown in Figure 14 , 2-WL does distinguish the two graphs. This example concerns graph distinction rather than orbit recovery: each graph is vertex-transitive, so 1-WL already recovers its single vertex orbit. Our experiments instead compare the vertex partitions induced by k k k -WL directly with the true orbit partitions.
Figure 13. Two non-isomorphic 2-regular graphs that cannot be distinguished by 1-WL.
Figure 14. The 2-WL colorings of C 6 C_6 C 6 and 2 K 3 2K_3 2 K 3 .
For vertex-orbit identification, the stabilized k k k -tuple coloring induces a vertex coloring by assigning to each vertex v v v the color of its diagonal tuple ( v , … , v ) (v,\ldots,v) ( v , … , v ) . Vertices with the same induced color are placed in the same class. Because graph automorphisms preserve WL colors, each resulting class is a union of vertex orbits; nevertheless, distinct orbits may remain in the same class. We say that k k k -WL recovers the orbit partition of G G G when its induced vertex partition equals the partition into automorphism orbits.
Detailed experimental results
F-LEX Graphs
Table 2. Results on F-LEX graphs under fixed-resolution comparison (r = 10 9 r = 10^9 r = 1 0 9 ).
USR Graphs
Table 3. Results for the USR graphs.
Had-SW Graphs
Table 4. Results on Had-SW graphs.
Grid Graphs*
Table 5. Results on Grid graphs with adaptive fixed-resolution comparison.
Grid-W Graphs*
Table 6 : Results on Grid-W graphs with adaptive fixed-resolution comparison.
Table 6. Results on Grid-W graphs with adaptive fixed-resolution comparison.
dac Graphs
Table 7. Results on dac graphs with adaptive fixed-resolution comparison.
Hypercube Graphs
Table 8. Results on Hypercube graphs.
Latin-SW Graphs
Table 9. Results on Latin-SW graphs.
Hadamard Graphs*
Table 10. Results on had graphs.
MZ Graphs*
Table 11. Results on MZ graphs with adaptive fixed-resolution comparison.
mz-aug2 Graphs*
Table 12 : Results on mz-aug2 graphs under fixed-resolution comparison (r = 10 6 r = 10^6 r = 1 0 6 ).
Table 12.
mz-aug Graphs
Table 13. Results on mz-aug graphs.
CHH Graphs
Table 14: Results on CHH graphs under fixed-resolution comparison (r = 10 6 r = 10^{6} r = 1 0 6 ).
Table 14.
PP Graphs*
Table 15. Results on PP graphs under fixed-resolution comparison (r = 10 6 r = 10^{6} r = 1 0 6 ).
STS Graphs*
Table 16. Table 16: Results on STS graphs under fixed-resolution comparison (r = 10 6 r = 10^{6} r = 1 0 6 ).
STS-SW Graphs
Table 17. Results on STS-SW graphs at resolution 10 8 10^8 1 0 8 .
Table 1.
Table 25.
CMZ Graphs
Table 18: Results on CMZ graphs under fixed-resolution comparison (r = 10 6 r = 10^6 r = 1 0 6 ).
Table 18. Results on CMZ graphs under fixed-resolution comparison (r = 10 6 r = 10^6 r = 1 0 6 ).
Table 26.
SAT-CFI Graphs
Table 19. Results on sat_cfi_dim graphs at resolution 10 8 10^{8} 1 0 8 .
Table 27.
CFI Graphs
Table 20. Results on CFI graphs under fixed-resolution comparison (r = 10 6 r = 10^{6} r = 1 0 6 ).
rnd-3-reg Graphs
Table 21. Results on random 3-regular graphs.
KEF Graphs
Table 22. Results on KEF graphs.
TRAN Graphs
Table 23. Results on TRAN graphs.
Table 28.
TNN Graphs
Table 24. Results on TNN graphs.
AG Graphs
All 23 AG graphs were exactly resolved by the Laplacian of G G G at r = 10 6 r = 10^{6} r = 1 0 6 , yielding NMI = 1, P P P = 1, and two classes in every case. The vertex-orbit partition is also recovered by 1-WL for all these instances.
Paley Graphs
All 53 tested Paley graph instances were exactly resolved by the Laplacian of G G G , yielding NMI = 1, P P P = 1, and a single equivalence class in every case. The vertex-orbit partition is also recovered by 1-WL for all these instances.
PG Graphs
All 23 tested PG graph instances were exactly resolved by the Laplacian of G G G at r = 10 6 r = 10^{6} r = 1 0 6 , yielding NMI = 1, P P P = 1, and a single equivalence class in every case. The vertex-orbit partition is also recovered by 1-WL for all these instances.
Triang Graphs
All 27 tested triangular graph instances were exactly resolved by the Laplacian of G G G at r = 10 6 r = 10^{6} r = 1 0 6 , yielding NMI = 1 = 1 = 1 , P = 1 P = 1 P = 1 , and a single equivalence class in every case. The vertex-orbit partition is also recovered by 1-WL for all these instances.
K Graphs
All 99 tested clique graph instances were exactly resolved by the Laplacian of G G G , yielding NMI = 1 = 1 = 1 , P = 1 P = 1 P = 1 , and a single equivalence class in every case. The vertex-orbit partition is also recovered by 1-WL for all these instances.
Latin Graphs
All 29 tested Latin graph instances were exactly resolved by the Laplacian of G G G , yielding NMI = 1 = 1 = 1 , P = 1 P = 1 P = 1 , and a single equivalence class in every case. The vertex-orbit partition is also recovered by 1-WL for all these instances.
Lattice Graphs
All 27 tested Lattice graph instances were exactly resolved by the Laplacian of G G G , yielding NMI = 1 = 1 = 1 , P = 1 P = 1 P = 1 , and a single equivalence class in every case. The vertex-orbit partition is also recovered by 1-WL for all these instances.