Weisfeiler-Lehman Similarity Class¶
Introduction¶
The Weisfeiler-Lehman Similarity class is a Python implementation for measuring the structural similarity between graphs based on the Weisfeiler-Lehman (WL) isomorphism test. This method is particularly useful in various fields such as social network analysis, chemoinformatics, and machine learning on graphs, where comparing graph structures is essential.
Understanding Weisfeiler-Lehman Similarity¶
The Weisfeiler-Lehman similarity is based on the WL graph isomorphism test, which iteratively refines node labels based on their neighborhoods. The similarity between two graphs is then computed by comparing these refined label sets.
The process works as follows:
Initialize node labels (e.g., with degree or a constant).
For each iteration: a. For each node, aggregate labels of its neighbors. b. Hash this aggregated label to create a new label for the node.
After a fixed number of iterations, compare the resulting label sets.
The similarity is typically computed as the average Jaccard similarity between the label multisets at each iteration:
Where: - k is the number of iterations - L_i(G) is the multiset of labels for graph G at iteration i
Key properties: - It’s sensitive to structural differences in graphs. - It can distinguish many (but not all) non-isomorphic graphs. - It’s computationally efficient compared to exact isomorphism tests.
Usage Example¶
Here’s a basic example of how to use the WeisfeilerLehmanSimilarity class:
from distancia import WeisfeilerLehmanSimilarity
import networkx as nx
from distancia import *
def create_sample_graphs():
# Create a cycle graph
C5 = nx.cycle_graph(5)
# Create a path graph
P5 = nx.path_graph(5)
# Create a complete graph
K5 = nx.complete_graph(5)
# Create a star graph
S5 = nx.star_graph(4)
# Create two random graphs
G1 = nx.gnm_random_graph(5, 7)
G2 = nx.gnm_random_graph(5, 7)
return C5, P5, K5, S5, G1, G2
def compare_graphs(graphs, names):
# Initialize WeisfeilerLehmanSimilarity object
wl = WeisfeilerLehmanSimilarity(num_iterations=3)
print("Weisfeiler-Lehman similarities between graphs:")
for i, (G1, name1) in enumerate(zip(graphs, names)):
for j, (G2, name2) in enumerate(zip(graphs[i+1:], names[i+1:])):
similarity = wl.calculate(G1, G2)
print(f"{name1} vs {name2}: {similarity:.4f}")
# Check for potential isomorphism with itself (should always be true)
is_iso = wl.is_isomorphic(G1, G1)
print(f"Is {name1} isomorphic to itself? {is_iso}")
# Check for potential isomorphism between different graphs
print("\nChecking for potential isomorphism:")
for i, (G1, name1) in enumerate(zip(graphs, names)):
for j, (G2, name2) in enumerate(zip(graphs[i+1:], names[i+1:])):
is_iso = wl.is_isomorphic(G1, G2)
print(f"Are {name1} and {name2} potentially isomorphic? {is_iso}")
def main():
# Create sample graphs
C5, P5, K5, S5, G1, G2 = create_sample_graphs()
graph_names = ["Cycle", "Path", "Complete", "Star", "Random1", "Random2"]
# Compare the graphs
compare_graphs([C5, P5, K5, S5, G1, G2], graph_names)
if __name__ == "__main__":
main()
This example compares a cycle graph with a path graph, both having 5 nodes. The Weisfeiler-Lehman similarity quantifies how structurally similar these graphs are.
Weisfeiler-Lehman similarities between graphs:
Cycle vs Path: 0.3849
Cycle vs Complete: 0.2500
Cycle vs Star: 0.2500
Cycle vs Random1: 0.2500
Cycle vs Random2: 0.2778
Is Cycle isomorphic to itself? True
Path vs Complete: 0.2500
Path vs Star: 0.3125
Path vs Random1: 0.2778
Path vs Random2: 0.2778
Is Path isomorphic to itself? True
Complete vs Star: 0.2778
Complete vs Random1: 0.2778
Complete vs Random2: 0.2500
Is Complete isomorphic to itself? True
Star vs Random1: 0.3403
Star vs Random2: 0.2500
Is Star isomorphic to itself? True
Random1 vs Random2: 0.3571
Is Random1 isomorphic to itself? True
Is Random2 isomorphic to itself? True
Checking for potential isomorphism:
Are Cycle and Path potentially isomorphic? False
Are Cycle and Complete potentially isomorphic? False
Are Cycle and Star potentially isomorphic? False
Are Cycle and Random1 potentially isomorphic? False
Are Cycle and Random2 potentially isomorphic? False
Are Path and Complete potentially isomorphic? False
Are Path and Star potentially isomorphic? False
Are Path and Random1 potentially isomorphic? False
Are Path and Random2 potentially isomorphic? False
Are Complete and Star potentially isomorphic? False
Are Complete and Random1 potentially isomorphic? False
Are Complete and Random2 potentially isomorphic? False
Are Star and Random1 potentially isomorphic? False
Are Star and Random2 potentially isomorphic? False
Are Random1 and Random2 potentially isomorphic? False
Academic Citations¶
When using this implementation in academic work, please cite the following papers:
For the original Weisfeiler-Lehman test: Douglas[1]
For the use of WL in graph kernels and similarity measures: Shervashidze et al.[2]
Conclusion¶
The Weisfeiler-Lehman Similarity class provides an efficient and powerful tool for comparing graph structures. Its strengths lie in its ability to capture fine-grained structural similarities and differences between graphs, making it valuable in various applications of network analysis and graph-based machine learning.
Key advantages: 1. Efficient computation, even for large graphs 2. Captures structural similarities beyond simple graph statistics 3. Can be used as a fast approximation for graph isomorphism testing
However, users should be aware of its limitations: 1. Cannot distinguish all non-isomorphic graphs (known as the “WL test’s blindness”) 2. Sensitive to initial node labeling in some cases 3. May require tuning of the number of iterations for optimal performance
Future work could explore extensions to edge-labeled graphs, adaptations for directed graphs, or combinations with other graph comparison techniques to overcome some of these limitations. Despite these considerations, the Weisfeiler-Lehman similarity remains a fundamental and widely-used method in the field of graph analysis and comparison, offering a good balance between computational efficiency and discriminative power.