  Graph databases have been the subject of significant research and
development. Problems such as modularity, centrality, alignment, and clustering
have been formalized and solved in various application contexts. In this paper,
we focus on databases for applications in which graphs have a spatial basis,
which we refer to as rigid graphs. Nodes in such graphs have preferred
positions relative to their graph neighbors. Examples of such graphs include
abstractions of large biomolecules, functional connectomes of the human brain,
and mobile device/ sensor communication logs. When analyzing such networks it
is important to consider edge lengths; e.g., when identifying conserved
patterns through graph alignment, it is important for conserved edges to have
correlated lengths, in addition to topological similarity. In contrast to a
large body of work on topological graph alignment, rigid graph alignment
simultaneously aligns the network, as well as the underlying structure as
characterized by edge lengths. We formulate the problem and present a
meta-algorithm based on expectation-maximization that alternately aligns the
network and the structure. We demonstrate that our meta-algorithm significantly
improves the quality of alignments in target applications, compared to
topological or structural aligners alone. We apply rigid graph alignment to
functional brain networks derived from 20 subjects drawn from the Human
Connectome Project (HCP) database, and show over a two-fold increase in quality
of alignment over state of the art topological aligners. We evaluate the impact
of various parameters associated with input datasets through a study on
synthetic graphs, where we fully characterize the performance of our method.
Our results are broadly applicable to other applications and abstracted
networks that can be embedded in metric spaces -- e.g., through spectral
embeddings.
