Crate wl_isomorphism 

Weisfeiler-Leman Graph Isomorphism

This crate provides an implementation of the Weisfeiler-Leman (WL) graph isomorphism algorithm for petgraph graphs. WL is a sound but incomplete isomorphism test, that because of its speed is often used as a subroutine in complete tests and feature extraction for graph kernels. Additionally, it includes an implementation of the two-dimensional version of the algorithm, which offers greater distinguishing power—particularly for regular graphs—at the cost of a significant runtime penalty.

Example

The crate’s most basic usage is to compare two graphs for isomorphism using the invariant function. The function will return the same graph hash for isomorphic graphs (hence it is called an “invariant”), and in most cases different hashes for non-isomorphic graphs.

use petgraph::graph::{UnGraph, DiGraph};

let g1 = UnGraph::<u64, ()>::from_edges([(0,1), (1,2), (2,0), (2,3)]);
let g2 = UnGraph::<u64, ()>::from_edges([(0,1), (1,2), (2,0), (0,3)]);
let g3 = UnGraph::<u64, ()>::from_edges([(0,1), (1,2), (2,3), (0,3)]);
let g4 = DiGraph::<u64, ()>::from_edges([(0,1), (1,2), (2,0), (2,3)]);
let hash1 = wl_isomorphism::invariant(g1);
let hash2 = wl_isomorphism::invariant(g2);
let hash3 = wl_isomorphism::invariant(g3);
let hash4 = wl_isomorphism::invariant(g4);
println!("The final hashes (u64) are:");
println!("1: {}, 2: {}, 3: {}, and: {}", hash1, hash2, hash3, hash4);
// 1: 16339153988175251892, 2: 16339153988175251892, 3: 14961629621624962419, and: 15573326168912649736

IMPORTANT

• The WL algorithm is not a complete isomorphism test. This means that when the algorithm returns the same hash for two graphs, they are possibly isomorphic, but not guaranteed. On certain classes of graphs (such as random graphs) this is almost always a good indicator of isomorphism, but it is for example not trustworthy on regular graphs. It is, however, a sound test, meaning that if the algorithm returns different hashes, the graphs are guaranteed to be non-isomorphic.
• Hash values depend on the number of iterations. For algorithms with a fixed iteration count, even the same graph will yield different hashes for different iteration counts.
• Hash values depend on device endianness. The same graph will produce different hashes on little-endian and big-endian systems. Compare hashes only on the same device or verify results using example graphs.

Features

• Isomorphism testing.
  • Calculate a graph’s hash to compare it with other graphs’ hashes to determine if they are isomorphic.
  • Use invariant, or if you want the algorithm to run for a specific number of iterations, use invariant_iters.
  • Alternatively, use the two-dimensional versions of these, invariant_2wl and iter_2wl, which offer greater distinguishing power—particularly for regular graphs—at the cost of a significant runtime penalty.
• Subgraph hashing .
  • Obtain subgraph hashes for each node at each iteration for tasks like feature extraction for graph kernels.
  • Use neighbourhood_hash for a fixed number of iterations or neighbourhood_stable to run until stabilisation.
• Dot file output.
  • Write the graph to a dot file, where the colour class of each node is visualised.
  • Use invariant_dot or iter_dot.
• Read from NetworkX edgelist file
  • Load graphs from text files in the NetworkX edgelist format.
  • Use ungraph_from_edgelist or digraph_from_edgelist.

Functions

digraph_from_edgelist

Read a directed graph from a text file, as produced by Networkx.write_edgelist. Note that this does not support weights and that if the edgelist skips certain indices, petgraph will infer an unconnected node at that index.

invariant

Calculate the graph invariant using 1-dimensional WL. Automatically stabilises. On graph classes like regular graphs, it is better to use invariant_2wl, which is more expressive but slower.

invariant_2wl

Calculate the graph invariant using 2-dimensional WL. Automatically stabilises. This is an implementation of ‘2-FWL’. This is more expressive than 1-dimensional WL, but much slower. Therefore only use this on graph classes where our default invariant does not work well.

invariant_dot

Like invariant, but it additionally writes the graph with the final colouring in dot format to path.

invariant_iters

Calculate the graph invariant using 1-dimensional WL. Runs for n_iters. Regular graphs tend to need at most 3 iterations for stabilisation, but for example random trees significantly more. We recommend using invariant for optimal results, if you don’t require a specific number of iterations.

iter_2wl

Calculate the graph invariant using 2-dimensional WL. Runs for n_iters. We recommend using invariant_2wl for optimal results if you don’t require a specific number of iterations.

iter_dot

Like invariant_iters, but it additionally writes the graph with the final colouring in dot format to path.

neighbourhood_hash

Generate the subgraph hashes per node per iteration. Can, for example, be used for feature extraction for graph kernels. The computed hash values give some information on the i-hop neighbourhood. The first hash, for example, gives some information on the neighbourhood of each node reachable within one hop.

neighbourhood_stable

Like neighbourhood_hash, but instead calculated until stability is achieved. (Note that we do not return the last calulated hashes, as these do not provide any new information: they are stable with respect to the last ones that áre returned.)

ungraph_from_edgelist

Read an undirected graph from a text file, as produced by Networkx.write_edgelist. Note that this does not support weights and that if the edgelist skips certain indices, petgraph will infer unconnected nodes at said indices.