Exploring Material Similarity using 

Graph-Based Crystal Structure Analysis 

and Machine Learning 

Karen Cao

Montgomery Blair High School

Mentor - Dr. William Ratcliff

1
Objective ● Investigate the types of crystal 

structures already discovered 

and how they are distributed 

● Represent crystal structures as 

graphs in order to create 

comparisons and place them in 

clusters or communities

2
Background

What is a Crystal Structure?

● 3D arrangement of atoms, 

molecules, or ions in a crystalline 

solid

● Symmetric and repeating patterns

What is a Graph?

● Mathematical structure

● Nodes and edges
Space Groups

Describes arrangement of atoms in unit cell with Hermann-Mauguin (HM) symbols

Bravais types 

● P – Primitive 

● I – Body Centered

● F – Face Centered

Symmetry Operations

● Rotations

● Reflections

● Inversions

● Glide Plane/Screw Axis

Each space group is associated with a unique number (230 total) 3

Space Group:

I 4 m m 
Crystal Structure → Crystal Graph

● Nearest_neighbor_edges - kNN (k-nearest neighbor) edge 

list 

● Radius_graph - edge list based 

on a specified cutoff radius 

after several conversions and 

calculations

4

The creators of the library to generate the crystal graph are Dr. Kamal Choudhary and Brian DeCost.

CIF File

Graph
Graph Edit Distance (GED)

● Measure of similarity between two 

graphs

● Minimum cost to transform one 

graph into another through a 

sequence of edit operations

● Edit operations - node/edge 

insertion, deletion, and substitution

5

The idea of using graph edit distance was inspired by Dr. Debra Audus
GED Example Visualization Animation

One node sub One edge ins

a
GED Calculation Algorithm

Based on the A* Search Algorithm1

1. Priority queue to store nodes 

and edges

2. Apply each possible operation 

to create a new graph state and 

calculate the cost function f(p)

3. Remove node with smallest f(p) 

from priority queue

g = cumulative cost 

Initial state→ current state

h = estimate cost 

Current state → goal state

7

1https://hal.science/hal-01168816
GED Calculation

graph_edit_distance(G1, G2, timeout=60)

● NetworkX Python Library

● Based on the A* Search Algorithm

● Calculates the GED between G1 and G2

● Returns the best GED calculation within 

a maximum number of seconds to 

execute

8
Hierarchical Clustering

● Groups similar objects into 

groups/clusters

● How it works:

○ Treats each graph as a separate 

cluster

○ Repeatedly merges two clusters 

that are closest

○ Iterates until all clusters merged 

together

9

Hierarchical Clustering Dendrogram

Space Group Number

Graph Edit Distance
Community Detection

● Locates tightly connected nodes in a graph

● How it works:

○ Assigns different community to nodes

○ Considers each neighboring 

community for placing nodes

○ Node placed in neighbor community 

based on modularity

10
Hierarchical Clustering Results

11

Dendrogram

Graph Edit Distance

Space Group Number
Community 

Detection 

Results

12

What’s Next

● Closely investigate the clusters and communities

● How has this distribution has changed over time?

● Continue calculating the graph edit distance for a complete 200,000 x 

200,000 distance matrix

13
Special Thanks 

Dr. William Ratcliff & Mr. Paul 

Kienzle

Dr. Paul Butler, Mr. Jeff Krzywon, Dr. Yun Liu

Dr. Julie Borchers, Dr. Leland Harriger
Any Questions?