In this work, we propose a novel framework for graph canonisation called Hyperset Individualisation, using bisimulation on a set-theoretic framework in an efort to tackle the Graph Isomorphism problem on simple graphs. Building on this idea, we define algorithm HID, which we prove to be strictly more expressive than colour refinement. Moreover, we define two versions of a -dimensional HID, which we prove to have diferent expressive power.
preliminary analysis of their computational complexity. Finally, in Section 7 we draw conclusions and state some open problems, mainly concerning the expressiveness of the aforementioned methods.
In this paper, standard graph-theoretic and set-theoretic notations will be adopted. In particular, a tuple will be delimited by angled parentheses ⟨ ⟩ and a multiset by the parentheses {[ ]}; unordered pairs will be represented as (· , · ), as they often do in existing literature. ⊎ will denote the multiset sum operation, which sums the multiplicities of each element, common or not, of the addend multisets. Connections between two nodes will be referred to as edges in the case of undirected graphs and as arcs in the directed case; = ⟨, ⟩ (resp., ⃗ = ⟨⃗, ⃗⃗⟩) will denote an undirected (resp., directed) graph, while subscripts will be omitted whenever clear from the context and unless otherwise specified. In this case, by and we will denote, respectively, the number of nodes and edges (or arcs) of a graph.
We will mainly treat the case of finite undirected graphs without self-loops and weighted or multiple edges, also referred to as simple graphs. At due time, we will also require these graphs to be connected.
Consider then a pair of simple graphs = ⟨, ⟩ and = ⟨ , ⟩.
An ℎ between two simple graphs and is a bijection : → nodes , in . If such exists, is said to be isomorphic to , denoted by ∼= . which preserves both adjacencies and non-adjacencies, i.e. (, ) ∈ ⇔ ((), ()) ∈ for all
Given two graphs and , the Graph Isomorphism problem (from now on, also abbreviated as GI ) consists in establishing whether ∼= or not.
The 1-dimensional Weisfeiler-Leman (WL1, for short), also known as colour refinement , is the simplest graphs, we assume the initial colouring 01 to be uniform for all nodes. At step ≥ algorithm of the WL family. Given a graph = ⟨, ⟩, WL1 produces a stable colouring of its nodes. Let 1 be the colouring produced by WL1 after its -th iteration: since we only consider uncoloured 1 and for each node ∈ , WL1 collects the colours of ’s neighbours into a multiset (), called the aggregation map of at step : a new colour 1() is then computed from (and uniquely associated to) ’s previous colour and its current aggregation map, by means of a perfect hash function HASH. 0 is not defined. () = {[︁︁1− 1() : ∈ () ]}︁︁ () = HASH 1− 1(), ()︁) ︁(
Two nodes share the same colour at step only if they shared the same colour at step − 1 and their termination is guaranteed by the finiteness of . We define aggregation maps match. This refinement procedure repeats until a stable colouring ∞ WL1() = {[∞1() : ∈ ]}.
The generalised -dimensional Weisfeiler-Leman (WL, for short) produces a stable colouring of the ktuples in . Each ⃗ ∈ is initially coloured with its atomic type atp(⃗), which describes the (ordered) subgraph induced on by this tuple. Formally, two tuples ⃗ = ⟨1, .., ⟩ and ⃗ = ⟨1, .., ⟩ have the same atomic type if and only if the mapping ↦→ is an isomorphism from the -subgraph induced by ⃗ to the -subgraph induced by ⃗. We denote the initial colour of each tuple ⃗ by 0(⃗) = atp(⃗). As for the 1-dimensional version, WL also proceeds by repeated aggregation of neighbouring colours: given ⃗ = ⟨1, 2, .., ⟩ and a node , the tuple obtained by replacing exactly one of its nodes with is the -th -neighbour of ⃗, which we denote by ⃗,. The colour-update schema is similar to the one described for WL1, the sole diference being that the aggregation map of a tuple ⃗ is now a multiset 1 is reached: of -tuples of colours, one for each node in .
(⃗) =
{[︁︁
⟨− 1(⃗1,), . . . , − 1(⃗,)⟩ : ∈ ]}︁︁
︁(
(⃗) = HASH − 1(⃗), (⃗)
︁)
Again, the refinement procedure iterates until a stable colouring ∞
{[∞(⃗) : ⃗ ∈ ]}. WL can be implemented to run in time (+1 log ) on -vertex graphs [
WL() = 2.2. Hypersets and Bisimulation The set-theoretic framework for our algorithm is here introduced.
A well-founded set is such that every descending chain in the membership relation starting from it is finite and acyclic, meaning that ∋ 1 ∋ · · · ∋ eventually halts for a finite —in a pure set theory, is always the empty set ∅—and ̸= ̸= for every pair ̸= , , ∈ {1, . . . , }. To compare two well-founded sets, the extensionality criterion is applied: two sets are equal if and only if they have the same elements.1
On the contrary, a non-well-founded set, or hyperset, admits loops in the membership relation: with
such a move we grant, for example, the existence of “extra” sets such that ∈ , or ∈ 1 ∈ · · · ∈
∈ . By overcoming the limits imposed by a well-founded definition of ∈, Forti and Honsell [
We refer to [
Define the transitive closure trCl() of a (hyper-)set as the set containing its elements, and their elements, and so on. More formally: trCl() = ∪ ⋃︁ trCl().
∈ If an apg can be decorated by associating to each node either the set corresponding to its point, or an element of its transitive closure, it will be referred to as the pointed membership graph of the (hyper-)set labelling its point. If a hyperset ℎ has a finite transitive closure, then we can represent it by a finite pointed membership graph: in this case we will say that ℎ is a hereditarily finite rational hyperset .2
Observe that, as the hyperset Ω can be represented in several set-theoretic ways, it has also multiple graphical representations. To handle this, the following definition is needed to outline an equality criterion compatible with hypersets.
Definition 2.2 (Bisimulation, bisimilarity). Let ⃗ = ⟨, ⃗⟩ be a directed graph. A binary relation ♭
among the nodes of is said to be a bisimulation on ⃗ if ♭ with , ∈ always implies that:
• for every child ′ of there exists a child ′ of such that ′♭′, and
• for every child ′ of there exists a child ′ of such that ′♭′.
1This is very common to many standard set theories, in particular Zermelo-Fraenkel’s; see, e.g., [
The union of all bisimulations on ⃗ is still a bisimulation, it is called bisimilarity, and it is the coarsest bisimulation on ⃗: bisimilarity defines an equivalence relation on the nodes, denoted by ≡ ⃗.
The notion of bisimilarity constitutes an equality criterion for hypersets: stating that two pointed membership graphs (i.e., their points) are bisimilar means that they both represent the same hyperset. Intuitively, one can think of bisimilarity as the coarsest partition of the nodes set grouping functionally equivalent ones: assuming ≡ ⃗ , any “move” performed starting from can be mirrored starting from . Notice that the existence of an isomorphism between two oriented graphs implies that every vertex of the first graph is bisimilar to its image (). The converse does not hold true in general.
Individualisation of single nodes, for the purpose of symmetry breaking, is a well-known technique
in the field of graph canonisation. Most state-of-the-art practical tools, such as nauty and Traces
[
Individualisation finds applications in important theoretic results. -CR bounded graphs, for which a
discrete colouring can be obtained by repeatedly applying WL1 and assigning a unique colour to each
node of a non-singleton class of size at most , play a key role in Grohe et al.’s test for isomorphism
running in time polylog(ℎ) for -vertex graphs excluding some ℎ-vertex graph as a minor [
In both previous examples, this simmetry-breaking technique is iteratively paired with WL1 in order to reach a discrete colouring. On the other hand, in the HI framework introduced below, individualisation is applied only once for each node in the graph, before launching a bisimulation algorithm which produces a hyperset ℎ associated to .
The first definition of the Hyperset Individualisation algorithm HI is aimed at giving a set-theoretic cut to the graph canonisation problem by assigning a multiset of hypersets to each undirected simple graph. As for WL1, the result obtained after performing HI is a multiset encoding pieces of information about the chosen graph; however, while this is based on nodes’ degrees for the former, the latter computes bisimilarity contractions by interpreting the graph as the pointed membership graph of some hyperset.
Due to the following lemma, we can, and will, restrict our analysis to connected simple graphs. Lemma 3.1. Let = ⟨, ⟩ and = ⟨ , ⟩ be undirected, possibly non-connected simple graphs. Let ′ = ⟨ ∪ {}, ∪ {(, ) : ∈ }⟩ and ′ = ⟨ ∪ { }, ∪ {( , ) : ∈ }⟩ be the graphs obtained by adding to both a source node reaching each node of the original graphs. Then, ∼= if and only if ′ ∼= ′.
HI pseudocode is reported as Algorithm 1. After replacing each (undirected) edge with a pair of
opposite arcs, a new arc from a node to a new node ∅—which, from a set-theoretic perspective,
represents the empty set—is added. Given the so-modified pointed graph ⃗, with itself as the point,
a tool such as the one defined in [
Algorithm 1 Hyperset individualisation HI
Require: = ⟨, ⟩
Ensure: HI()
1: ⃗ ← ∅
2: for (, ) ∈ do
3: ⃗ ← ⃗ ∪ {⟨, ⟩, ⟨, ⟩}
4: end for
5: HI() ← { [ ]}
6: for ∈ do
7: ⃗ ← ⟨ ∪ {∅}, ⃗ ∪ {⟨, ∅⟩}, ⟩
8: ℎ ← DPP(⃗)
9: HI() ← HI() ⊎ {[ℎ]}
10: end for
◁ Undirected, simple, connected
◁ Replace an edge with a pair of arcs
◁ Initialise HI() as the empty multiset
◁ Append a node labelled as the empty set ∅ to
⃗
◁ Run the bisimulation algorithm defined in [
The hyperset individualisation algorithm provides a one-way error test for graph isomorphism: given a pair (, ) of undirected graphs, HI() ̸= HI() implies that and are not isomorphic, while the converse does not necessarily hold.
Example 3.1. HI can distinguish non-isomorphic graph pairs which WL1 cannot. Indeed, by performing HI on the graphs and below, we obtain the multisets containing the depicted hypersets with the reported multiplicities (recall that each undirected edge represents a pair of opposed arcs in hypersets). 2 1 3 4 6 5 2 1
3 4 6 5 ⇝ 4⋆ 2⋆ 2⋆ 4⋆ ⇝
Observe that in HI() (resp., HI()) there are four copies of the hyperset obtained by individualising (resp., ) with ∈ {1, 2, 5, 6} and two copies of the one obtained by individualising (resp., ) with ∈ {3, 4}. As they difer between the two graphs, HI distinguishes and ; on the contrary, WL1 produces the same colours for each pair (, ). Yet, this graph pair is distinguished also by WL2. Example 3.2. Despite WL1 can identify each non-isomorphic tree, the following pair is not distinguished by HI (for both graphs, nodes at the same depth yield the same hyperset after individualisation).
From the previous examples, it follows that the expressive powers of WL1 and HI are incomparable.
As Example 3.2 shows, HI (in fact, bisimulation) does not take into account the size of a node’s neighbourhood: indeed, it proves itself more powerful than WL1 exactly when this property is irrelevant, but it could fail otherwise. A natural way to address this limitation, in an attempt to make HI strictly stronger than WL1, is to endow each node with an initial label encoding its degree.
In order to maintain a purely set-theoretic view, the nodes’ degrees can be conveniently represented by adding edges towards a node in a directed, descending chain (gadget graph) of nodes which is external with respect to the original graph. Basically, this chain represents the (Zermelo) ordinals, or super-singletons of the empty set up to the maximum degree of a node in the graph; the fact that ∈ has degree can be represented by an arc ⟨, {∅} ⟩, where, iteratively, {∅}0 := ∅ and {∅} := {{∅}− 1}.
Consider an undirected simple graph = ⟨, ⟩ and define its gadget graph as ⃗ = ⟨⃗ , ⃗⃗ ⟩ := ⟨︀{ {∅} : 0 ≤ ≤ }︀ , {︀ ⟨{∅} , {∅}− 1 ⟩ : 1 ≤ ≤ }︀⟩ , where := max∈{deg()}. Then, the Hyperset Individualisation algorithm with Degrees HID is the ⃗ variant of HI obtained by re-defining as = ⟨︀ ∪ ⃗ , ⃗ ∪ ⃗ ∪ {⟨, {∅}deg() ⟩ : ∈ } ∪ {⟨, ∅⟩}, ⟩︀ ⃗ ⃗ at line 7 in Algorithm 1 (⃗ is the set of arcs replacing the undirected edges of ).
Notice how this edit shall not create ambiguity with the process of individualising a node: since we are now dealing just with connected graphs, no node is without edges, so they all have a positive degree; therefore, the only arc pointing to the node dubbed as the empty set—now part of the gadget graph—is the one issuing from the intended individualised node.
Remark 2. Let ⃗ = ⟨ ∪ ⃗ , ⃗ ∪ ⃗⃗ ∪ {⟨, {∅}deg() ⟩ : ∈ }⟩ (the same as in Definition 4.1, but without individualising any node and with no definite point; from now on, we will keep this notation whenever it is not ambiguous). Then, computing maximum bisimulation on the graph ⃗ is equivalent to computing maximum bisimulation on the graph by degree-encoding colours to each node. Moreover, the well-founded part of ⃗ is its gadget graph ⃗.
An interesting result that proves the greater efectiveness of HID w.r.t. HI and WL1 is the following. Theorem 4.1. HID is strictly more expressive than WL1.
Proof. By example 3.1, there exists a non-isomorphic graph-pair distinguished by HID, but not by WL1. Thus, we only need to show that every graph-pair distinguished by WL1 is also distinguished by HID. Let () be the colour assigned to the node after the -th WL1 iteration: we recall that () identifies the subtree structure () of height rooted in .4 We show that, for any pair of nodes (, ): (∃ ∈ N)(() ̸= ()) =⇒ ℎ ̸= ℎ, (1) where ℎ (resp., ℎ) is the (pointed membership graph of the) hyperset resulting after performing bisimulation contraction on ⃗ (resp., ⃗), pre-processed with nodes’ degrees.
For = 0, the implication is trivially true. Assume now that > 0, () ̸= () and () = () for all < . Since the subtree structures match up to height − 1, but not further, there must exist two leaves ˆ ∈ − 1(), ˆ ∈ − 1() such that deg(ˆ) ̸= deg(ˆ) and the degree sequences from the roots to their parents are equal. Besides, at least one between ˆ and ˆ must be of rank exactly :5 otherwise, the WL1 colouring for and would have diverged in an earlier iteration. It follows that, in the degree-partitioned graph, there is a coloured path of length − 1 starting from which cannot be replicated starting from : thus, is not bisimilar to or, equivalently, ℎ ̸= ℎ, proving (1).
Therefore, by considering every node-pair (, ), we obtain that if the multisets produced for two graphs (, ) by WL1 are diferent, so are the multisets produced by HID.
As HID is so proved to be strictly more expressive than WL1, we are interested in studying its limits. As an upper bound, we observe that HID is not as expressive as WL3.
Theorem 4.2. There exists a graph pair distinguished by WL3, but not by WL2 or HID.
Proof. Consider the 4x4 Rook’s and the Shrikhande graphs in Fig. 4, both strongly regular graphs with
parameters ⟨ = 16, = 6, = 2, = 2⟩, where is the number of nodes, the degree of each node,
and the number of common neighbours for adjacent and non-adjacent nodes, respectively. This pair
is distinguished by WL3, but not by WL2 (more generally, WL2 cannot tell apart SRGs with identical
parameters [
We point out two scenarios where HID allows to check for isomorphism in polynomial time. Lemma 4.1. Let the simple connected graphs = ⟨, ⟩, = ⟨ , ⟩ be such that || = | | = and ∃ℎ ∈ HID() ∩ HID() : |trCl(ℎ) = + + 1|. Then ∼= .
Proof. Notice that the ℎ of the statement has maximum transitive closure: there are no bisimulation collapses among the nodes originally in or , nor (trivially) among the + 1 nodes of their gadget graphs. Any two graphs ⃗, ⃗ associated to ℎ in HID() and HID() are, except in the connection to ∅, isomorphic to and themselves, respectively. The corresponding discrete partition induced by ℎ on both and naturally yields an isomorphism between the two.
Definition 4.2. Let = ⟨, ⟩ be a graph, let 2 be the powerset of its nodes. The (node) orbit partition of is the coarsest partition ⊂ 2 of such that all nodes belonging to the same class can be mapped into each other by an automorphism: such classes are called the (node) orbits of . If || = , we say that has a discrete orbit partition, as it only admits the identity on as an automorphism. Lemma 4.2. Let the simple connected graphs = ⟨, ⟩, = ⟨ , ⟩ be such that || = | | = and HID() = HID() contains distinct hypersets. Then, both graphs have discrete orbit partitions and the bijection : → such that () = if and only if ℎ = ℎ is the only possible isomorphism between and .
Proof. Two nodes producing diferent hypersets cannot belong to the same orbit (this is trivial: if they are mapped into each other by an automorphism, then they are bisimilar, thus they produce the same hyperset once individualised). Therefore, only bijections mapping nodes whose individualisation produces the same hyperset are candidate isomorphisms.
If the conditions of the previous lemma hold, ∼= can be verified in linear time. 5. Moving to a Higher Plane: -Dimensional HID In this section, we move to the following, natural question: can the HI(D) idea be lifted to achieve higher expressive power, in a similar fashion to the -dimensional WL? Specifically, we investigate diferent approaches to compute a multiset of hypersets associated to sets of > 1 nodes at a time, in order to define an algorithmic family HID akin to WL.
Before doing so, observe that a 0-dimensional Hyperset Individualisation algorithm HI0 is definable regardless of the precise definition given to any higher-dimensional version, as it subsumes the bisimulation contraction without individualising any node. Since there is no privileged starting point for the bisimulation algorithm, we will focus once again on the connected case only, so as to avoid that a single bisimulation reduction results in more than one hyperset.6 For the same reason, in this case we will also avoid to identify the point of the graph and so of the resulting hyperset.7 Remark 3. HI0—without degrees pre-processing—as applied to a simple connected graph either results in the empty set ∅ or in the hyperset Ω . Thus, it can only distinguish the graph having just one node (and no edges) from any other simple connected graph.
Diferently from the previous case, if the degrees’ pre-processing is performed—thus obtaining the HID0 algorithm—the graph results to be already partitioned before computing bisimulation. The following lemma holds true.
Lemma 5.1. HID0 is equivalent to WL1.
Proof. At each step and for each node , WL1 aggregates information about ’s own degree and, iteratively, those of all nodes that can be reached from it. Therefore, two nodes will get the same colour in the final stable partitioning of the graph if and only if they have the same degree, and their neighbours have pairwise the same degree, and so on. So, computing maximum bisimulation on that graph is equivalent to collapsing all the nodes belonging to the same WL1-class. 5.1. Individualising by the Empty Set: HIDE We define algorithm HIDE (Hyperset Individualisation with Degrees and the Empty set) on a connected simple graph . Instead of individualising just a node at a time, we will take -many, with ≤ , and run maximum bisimulation contraction on the resulting graph, much as HID does. For the sake of completeness, a new node will be linked to the newly-individualised nodes to serve as the point of the resulting hyperset.
Definition 5.1. Let = ⟨, ⟩ be a connected simple graph, = | | and ∈ {2, . . . , }; let ⃗ be the directed version of , encoding degrees through the gadget graph, as described in Remark 2. Then, the Hyperset Individualisation algorithm with Degrees and the Empty set of order HIDE is the generalisation of HID obtained by replacing ∈ with ⊆ : || = at every occurrence, and ⃗ with
⃗ := ⟨︀ ⃗ ∪ {}, ⃗⃗ ∪ {⟨, ⟩, ⟨, ∅⟩ : ∈ }, ⟩︀ , at line 7 in Algorithm 1, thus obtaining HIDE() := {[ℎ := DPP(⃗) : ⊆ , || = ]}.
Observe that, since each hyperset is associated to a unique -subset of , HIDE() contains (︀ )︀ many hypersets; for clarity, such hypersets will be denoted as ℎ for each subset fulfilling the previous definition. It is not trivial to see how much the expressive power of HIDE varies by changing . However, as a first result, we prove that the expressive power reached by HIDE on graphs with -many nodes is the same as the one reached by HIDE− .
Lemma 5.2. Let = ⟨, ⟩, = ⟨ , ⟩ be connected simple graphs. Then, HIDE() = HIDE() if and only if HIDE− () = HIDE− ().
Proof. Assume HIDE() = HIDE(): therefore, there is a one-to-one correspondence associating each ⊆ to a ⊆ , both of cardinality , in such a way that ℎ = ℎ. As they are both contracted by maximum bisimulation, for each node ∈ ℎ there exists exactly one node ∈ ℎ bisimilar to it: notice that and are the bisimulation contractions of {′ ∈ ⃗ : ′ ≡ ⃗ } and {′ ∈ ⃗ : ′ ≡ ⃗ } respectively, and that every ′ ∈ if and only if ′ ∈ . Taking ′ and ′ as representatives of those bimilarity classes, and assuming ′ ∈ and ′ ∈ (resp. ′ ∈ ∖ and ′ ∈ ∖ ), by removing (resp. adding) the links from the sources , and to the empty set ∅ from (to) the both of them, they will still be bisimilar. Therefore, if and are bisimilar 6As Lemma 3.1 points out, we can reduce to this case without any loss of generality anyway. 7This comes both because it is useless in DPP algorithm and because any node can be coherently dubbed as point (as they all have the same transitive closure): any chosen point then should be ignored when the hypersets are compared. w.r.t. ℎ and ℎ , then they will be bisimilar also w.r.t. the hypersets ℎ ∖ and ℎ ∖ obtained by individualising the previously non-individualised nodes, thus proving that ℎ ∖ and finally ∖ = ℎ HIDE− () = HIDE− (). The opposite implication is proven in the same way.
This result proves that HIDE reaches its maximum expressiveness for at most ⌈/2⌉. Since we have not obtained more precise results about it so far, we can just conjecture that such maximum is indeed reached at that exact point. To support our claim, the following lemma shows that HIDE2 could be strictly more powerful than HIDE1 = HID on graphs with suficiently many nodes. Lemma 5.3. There exists a graph pair distinguished by HIDE2, but not by WL2 or HID. Proof. Consider again the 4x4 Rook’s and the Shrikhande graphs in Fig. 4. On the Rook’s graph, HIDE2 produces two distinct hypersets, obtained by individualising adjacent and non-adjacent node pairs, respectively. On the Shrikhande graph, three distinct hypersets are produced, obtained by individualising adjacent pairs, non-adjacent pairs with adjacent common neighbours, and non-adjacent pairs with non-adjacent common neighbours.
Currently, we do not know if the expressive power of HIDE is bounded (i.e. if there exists a nonisomorphic graph pair which cannot be distinguished by HIDE, for any possible ), or if it can reach complete identification up to isomorphism. 5.2. Individualising by Atoms: HIDA Next, we define an alternative generalised algorithm HIDA (Hyperset Individualisation with Degrees and Atoms). Let ⃗ be as before and add nodes = {1, . . . , }, called atoms, each belonging to a unique class, so that they are pairwise non-bisimilar by definition. Thus, the method consists in linking one node of ⃗ to one node of at a time, then collapsing the resulting graph by maximum bisimulation. By introducing diferent atoms, we guarantee that each pair of the so-individualised nodes will not be bisimilar, which is not necessarily the case for HIDE; on the other hand, as the ordering of those atoms—and, consequently, of the individualised nodes—is irrelevant for that purpose, we need to introduce an equivalence relation in such a way that diferent orderings do not afect the reliability of the test.
Definition 5.2. Consider atoms = {1, . . . , }, and two hypersets with atoms ℎ{1,...,}, ℎ{1,...,} such that the -th node in the subscript is the only one connected by an arc to the atom , for any ∈ {1, . . . , }. We write ℎ{1,...,} ∼ ℎ{1,...,} if and only if ∃ ∈ : ℎ{1,...,} = ℎ{ (1),..., ()}, where is the symmetric group over the discrete interval [1, ].
From this point onwards, with a slight abuse of notation in order to improve readability, we shall use ℎ to denote the (permutation invariant) equivalence class [ℎ]∼ to which the (permutation dependent) hyperset ℎ belongs. We are now ready to define HIDA algorithmically. Definition 5.3. Let = ⟨, ⟩ be a connected simple graph, = | |, ∈ {2, . . . , } and define a set of -many atoms = {1, . . . , }; let ⃗ be the directed version of , encoding degrees through the gadget graph, as described in Remark 2. Then, the Hyperset Individualisation algorithm with Degrees and Atoms of order HIDA is the generalisation of HID obtained by replacing ∈ with ⊆ : || = at every occurrence and ⃗ with
⃗ := ⟨︀ ⃗ ∪ ∪ {}, ⃗⃗ ∪ {⟨, ⟩, ⟨, ⟩ : ∈ }, ⟩︀ , at line 7 in Algorithm 1, thus obtaining HIDA() := {[ℎ := DPP(⃗) : ⊆ , || = ]}.
In order to distinguish a hyperset produced by HIDA w.r.t. other already defined algorithms, we will write it as ℎ for a subset of nodes. Given the previous definition, when comparing the multisets produced by HIDA on a pair of graphs and , we will check if the hypersets they contain are equal up to any permutation of atoms. In this way, we do not have to consider all the possible permutations of atoms while performing the algorithm (leading to factorial space complexity), limiting the number of hypersets in HIDA() to (︀ )︀ on a graph with ≥ nodes, as HIDE does. Instead, this complexity is eventually transferred to the research space, as, computationally speaking, we do not have a trivial way to address sets’ comparison without imposing upon them a specific, although arbitrary, ordering.
The following lemma, along with its immediate corollary, allows us to conclude that the HIDA family defines a hierarchy of increasingly stronger algorithms, akin to WL. uniquely determines HIDA(), up to any permutation of the atoms.
Lemma 5.4. Given a simple graph = ⟨, ⟩ such that | | = and < , the multiset HIDA+1() cardinality + 1, from |HIDA+1()| = (︀
)︀ we get Proof. HIDA() is obtained from HIDA+1() by removing one atom from each hyperset ℎ and then checking for possible bisimulation collapse between the de-individualised node and any other non-individualised node in ℎ. In this way we get + 1 new hypersets ℎ∖{} from each ; however, as the same subset of nodes can be obtained from ( − )-many subsets of ∖{} for ∈ {1, . . . , + 1} ︂( )︂
+ 1 + 1 · − = ( + 1)!( − − 1)! · − + 1 = ︂( )︂ = |HIDA()|, thus confirming that the cardinality of the produced multiset coincides with the one of HIDA(). Corollary 5.1. For all > 1, HIDA+1 induces a finer or equal partition on the universe of simple graphs than HIDA does.
As the final point of this preliminary analysis, we prove that the highest expressiveness of HIDA— which is equivalent to explicitly checking for isomorphism—is reached for = − 1 over graphs with nodes. It is currently unknown whether such expressiveness can also be achieved with a smaller . Lemma 5.5. Let and be connected simple graphs with nodes. Then, the following are equivalent. +1
! 1. ∼= ;
Proof. Trivially, claim 1 implies claims 2 and 3, as the existence of an isomorphism between and implies HIDA() = HIDA() for every ≤ , in particular for = and = − 1.
Assume claim 2 holds true. Then, any bijection : → linking nodes connected to the same atom in two equal hypersets from HIDA() and HIDA() is an isomorphism, thus proving claim 1.
Assume claim 3 holds true: we will prove that in this case claim 2 holds, too. Since and are connected, each hyperset in both HIDA− 1() and HIDA− 1() has a unique node that has rank 2 with respect to at least one atom, i.e. it cannot collapse with any other node by computing bisimulation. hypersets are all ∼ -equivalent, thus proving that HIDA() = HIDA().
Therefore, by appending a new atom to this spare node we obtain copies of the same hyperset (up to any permutation of atoms) from both HIDA− 1() and HIDA− 1(). As these are equal, the resulting
while the opposite implication does not hold true.
While the definition of the HIDE version comes quite naturally as a generalisation of HID, it is not immediate to see whether the HIDA version provides any advantage. By definition, HIDA is at least as strong as HIDE on a local level, since ℎ ̸= ℎ ⇒ ℎ ̸= ℎ for any two subsets , of nodes, Lemma 5.6. Two sets of nodes = {1, 2}, = {1, 2} can generate distinct hypersets ℎ ̸= ℎ, but equal hypersets ℎ = ℎ.
Proof. Consider the following example (gadget graphs and sources have been omitted for clarity). 6 3 ⇝ As depicted above, individualisation of 1 and 2 in the first graph and of 1 and 2 in the second graph yield the same hyperset by doing so with the empty set (HIDE2), but diferent ones with atoms ( HIDA2). The same can be said for pairs (4, 5) w.r.t. (4, 5) (trivial), and for (3, 6) w.r.t. (3, 6).
It can be shown that by computing the whole HIDE/HIDA certificates, the previous graphs are distinguished by both methods;8 thus, although HIDA might be stronger at a local level, this does not imply that it is a stronger isomorphism test: HIDE might still be able to distinguish all graph pairs distinguished by HIDA, as long as ≤ ⌈ /2⌉. It is yet to be verified whether there exists some * such that HIDE* identifies all -vertex graphs up to isomorphism: if this holds, the maximum required for HIDA would also be at most * , much smaller than the currently established ≥ − 1 bound. 6. Implementation Sketch and Complexity Analysis We now provide an analysis of the time/space complexity of the aforementioned methods; as a reference, we recall that WL has time complexity (+1 log ). Although a multiset of hypersets may seem harder to describe than the multiset of colours produced by WL, it must be noted that such colours are iteratively obtained by applying a hash function to a multiset of previously computed colours, i.e. for all purposes they are equivalent to nested multisets.
Multisets of hypersets can be handled, for instance, by keeping a list of all distinct hypersets
generated during a run of HI on a graph = ⟨, ⟩. Whenever a node ∈ is individualised, ℎ ∈
can be checked in polynomial time [
A single hyperset ℎ can be computed in time ( log ) by an algorithm such as [
Each ℎ ∈ may also be associated to a unique integer in [1, ], according to the time it first appeared in , allowing for constant time comparisons between the hypersets of distinct nodes, if later needed.
To test a graph-pair (, ) for isomorphism, one can simply run HI in parallel on both, taking care of checking both and whenever a hyperset ℎ from either graph is computed, in order to keep the aforementioned hyperset enumeration coherent. In terms of space, this solution requires ( + ) for each ℎ ∈ / , by definition of bisimilarity: in the worst case, assuming each individualised hyperset to be distinct, HI has space complexity (( + )). In terms of time, the overall complexity of HI is (2 log ), since up to 2 hypersets comparisons, each of cost ( log ), may be required if either || ∈ Θ( ) or | | ∈ Θ( ). The same bounds hold for HID, as computing the initial degree-partition of the nodes and extending the graph takes time ( + ).
Moving to the -dimensional HIDE, complexity scales according to the number of computed hypersets: in the worst cases, space (︀( )︀ ( + )) and time (︀( )︀ 2 log ) may be required. HIDA may appear equally costly, since its final multiset also contains (︀ )︀ elements; however, it must be noted 8By individualising (1, 4) or (1, 5) w.r.t. (1, 4) or (1, 5), both HIDE2 and HIDA2 produce diferent hypersets. ◁ Apgs of hypersets ℎ1, ℎ2 to be compared ◁ New whose point is linked to the points of ⃗1 and ⃗2 ◁ Equivalently, they are merged together in ℎ0 ◁ ℎ1 and ℎ2 are bisimilar, and thus equal Algorithm 2 Hypersets comparison Require: ⃗1 = ⟨1, ⃗1, 1⟩, ⃗2 = ⟨2, ⃗2, 2⟩ that this relies on the use of equivalence relation ∼ , which hides the computational cost of comparing two hypersets ℎ{1,...,} and ℎ{1,...,} up to any of the ! possible permutations of the atoms. Since checking whether two hypersets belong to the same ∼ class requires ! comparisons of the kind described in Algorithm 2, the overall time complexity of HIDA is (!(︀ )︀ 2 log ). On a practical level, simple heuristics can be applied to avoid costly comparisons in all of the above algorithms: for instance, hypersets whose apgs difer in their number of nodes or edges will certainly be distinct.
In this preliminary work, we introduced the notion of Hyperset Individualisation algorithm HI, which combines a set-theoretic perspective, bisimulation, and a node individualisation technique in order to provide a novel approach to the Graph Isomorphism and Graph Canonisation problems. After proving that our 1-dimensional HID algorithm has a strictly stronger separation power than the well-known WL1 algorithm, we defined two -dimensional generalisations, called HIDE and HIDA, whose properties do not perfectly overlap. On -vertex graphs, HIDE is proved to be exactly as expressive as HIDE− , so that its peak must be reached at some ≤ ⌈ /2⌉; on the other hand, HIDA is at least as expressive as HIDA− 1 for any , becoming a complete isomorphism test for ≥ − 1.
A number of open problems arise. HIDA is known to be at least as expressive as HIDE at a local level, but the exact relationship between the two families should be further investigated. It is not clear whether HIDE ever reaches the level of a complete isomorphism test for some ≤ ⌈ /2⌉: in this case, HIDA for the same (or lower) would, too—thus for a much lower than the already established bound of = − 1.
How the HIDE/HIDA and WL hierarchies intersect, besides the preliminary result on HID being
strictly more expressive than WL1, is another point of interest. Studying the behaviour of our algorithms
on non-isomorphic graph pairs generated through the CFI construction [
From a practical standpoint, when checking for isomorphism between two graphs (, ), one could think of iteratively applying HIDE1, HIDE2, . . . , HIDE≤ until either a mismatch is found or a threshold (e.g. a bound on ) is met. In such a context, we would be interested in determining whether (and how much) we could restrict the choice of the -sets to be individualised when running HIDE on and , depending on the previously computed multiset HIDE− 1() = HIDE− 1(), in order to optimise such a sequential application. For the same purpose, given two sets and of size , being able to eficiently distinguish their hypersets ℎ and ℎ a priori, based on the hypersets for and ’s ( − 1)-subsets, could greatly reduce the number of required comparisons. Entirely similar considerations apply to HIDA.
The authors have not employed any Generative AI tools.