# Graph Similarity Description: How Are These Graphs Similar?

Corinna Coupette  Max Planck Institute for InformaticsSaarbrückenGermany
<EMAIL_ADDRESS>and  Jilles Vreeken  CISPA Helmholtz Center for
Information SecuritySaarbrückenGermany<EMAIL_ADDRESS>
(2021)

###### Abstract.

How do social networks differ across platforms? How do information networks
change over time? Answering questions like these requires us to compare two or
more graphs. This task is commonly treated as a _measurement_ problem, but
numerical answers give limited insight. Here, we argue that if the goal is to
gain understanding, we should treat graph similarity assessment as a
_description_ problem instead. We formalize this problem as a model selection
task using the Minimum Description Length principle, capturing the similarity
of the input graphs in a _common model_ and the differences between them in
_transformations_ to _individual models_. To discover good models, we propose
Momo, which breaks the problem into two parts and introduces efficient
algorithms for each. Through an extensive set of experiments on a wide range
of synthetic and real-world graphs, we confirm that Momo works well in
practice.

Graph Similarity; Graph Summarization; Information Theory

††copyright: rightsretained††submissionid: rst1537††journalyear:
2021††conference: Proceedings of the 27th ACM SIGKDD Conference on Knowledge
Discovery and Data Mining; August 14–18, 2021; Virtual Event,
Singapore††booktitle: Proceedings of the 27th ACM SIGKDD Conference on
Knowledge Discovery and Data Mining (KDD ’21), August 14–18, 2021, Virtual
Event, Singapore††doi: 10.1145/3447548.3467257††isbn:
978-1-4503-8332-5/21/08††ccs: Information systems Data mining††ccs:
Mathematics of computing Exploratory data analysis††ccs: Mathematics of
computing Graph algorithms

##  1\. Introduction

Comparing two or more graphs is important in many applications. In biology, we
might, for example, want to compare the protein interaction networks of
different human tissues so as to discover common and specialized mechanisms,
while in the social sciences, comparing collaboration networks over time or
across fields could reveal knowledge dynamics. The task of comparing graphs is
called _graph similarity assessment_. It is commonly treated as a
_measurement_ problem, i.e., a question to which a numerical answer suffices
(e.g., $0.42$). While such an answer may be useful in certain downstream tasks
like classification or clustering, it provides limited insight and is thus
generally dissatisfying to a domain expert.

In this paper, we argue that if the goal is to gain understanding, we should
not ask “how _similar_ are these graphs?” but rather “ _how_ are these graphs
similar?”. That is, we propose to treat graph similarity assessment as a
_description_ problem, demanding an answer that, in easily understandable
terms, characterizes what is similar and what is different between the input
graphs at hand. We formalize the problem in information-theoretic terms using
the Minimum Description Length (MDL) principle, by which we are after the
shortest lossless description of the input graphs using common and specific
structures (e.g., stars, cliques, bicliques, and starcliques) as well as
shared nodes and edges between these structures. Since we can measure how many
bits we gain by compressing the graphs jointly, rather than individually, our
formalization also allows for an easily interpretable quantification of
differences.

As an example of graph similarity description, consider Figure 1, which
depicts two toy graphs and the result returned by our method. Even though the
graphs are of different sizes, and no node alignment is given, our method
discovers that both graphs contain a star (orange triangle) that is connected
to a clique (blue circle) and a starclique (pink diamond). We further see that
the left graph is different in that it additionally contains a biclique (red
square), and that the structures in the left graph all contain more nodes than
their counterparts in the right graph (larger shapes).

Figure 1. A common model captures the structure shared between the individual
models of the input graphs.

When assessing the similarity between graphs in practice, we face a very large
search space: There exist exponentially many sets of nodes, i.e., potential
structures, exponentially many _sets_ of structures, and—unless a full node
alignment is given—also exponentially many alignments between the graphs. As
our score exhibits no structure that we could exploit to efficiently discover
the optimal solution, we propose a framework, called Momo (_Mo_ del of _mo_
dels), that breaks the problem into two parts and introduces efficient
algorithms for each: Beppo discovers interpretable summaries for the
individual input graphs, and Gigi uses them to unveil their shared and
specific structures, from which we can also compute an informative similarity
score. Through an extensive set of experiments on a wide range of synthetic
and real-world graphs, we confirm that our algorithms perform well in
practice: We discover summaries that are useful for domain experts, identify
meaningful similarities between the protein interaction networks of different
human tissues, and reveal distinct temporal dynamics in the collaboration
networks of different scientific communities. Not unimportantly, in practice,
our methods scale near-linearly in the number of edges.

The remainder of the paper is structured as follows. Section 2 introduces our
notation and gives a primer on MDL, and Sections 3, 4, and 6 present our main
contributions. We cover related work in Section 5, and round up with
discussion and conclusions in Section 7. All our data, code, and results are
publicly available,111http://eda.mmci.uni-saarland.de/prj/momo;
https://doi.org/10.5281/zenodo.4780912 and further information for
reproducibility is given in Appendix A.

##  2\. Preliminaries

We consider graphs $G_{i}=(V_{i},E_{i})$ with $n_{i}=|V_{i}|$ nodes,
$m_{i}=|E_{i}|$ edges, and adjacency matrix $\mathbf{A}_{i}$, omitting the
subscripts when clear from context. An alignment $\mathcal{A}_{ij}$ between
the graphs $G_{i}$ and $G_{j}$, denoted $G_{i}\parallel_{\mathcal{A}}G_{j}$,
is a bijection from $V_{i}$ to $V_{j}$. To allow comparisons between graphs of
different sizes or graphs for which no node alignment is known, we allow this
bijection to be _partial_ or _empty_ , i.e., there can be nodes in $V_{i}$
($V_{j}$) that have no image (preimage) in $V_{j}$ ($V_{i}$) under
$\mathcal{A}_{ij}$. We assume that our input graphs are _simple_ , i.e.,
undirected, unweighted, without loops or parallel edges, and that only _two_
input graphs are given, but our framework generalizes to comparisons between
_more than two_ _general_ graphs.

We build on the notion of _Kolmogorov complexity_. The Kolmogorov complexity
of an object $x$, $K(x)$, is the length in bits of the shortest program
computing $x$ on a universal Turing machine, and the _conditional_ Kolmogorov
complexity of $x$ given $y$, $K(x\mid y)$, is the length of such a program
with $y$ as auxiliary input (18). The _Information Distance_ between $x$ and
$y$ is (up to an additive logarithmic term) the length of the shortest program
transforming $x$ into $y$ and $y$ into $x$, i.e., $ID(x,y)=\max\\{K(x\mid
y),K(y\mid x)\\}$ (17). Dividing by $\max\\{K(x),K(y)\\}$, we obtain the
_Normalized Information Distance_.

The Kolmogorov complexity is not computable, and hence, neither is the
Normalized Information Distance. To _describe_ and _measure_ the similarity
between graphs in practice, we thus instantiate Kolmogorov complexity through
the Minimum Description Length (MDL) principle (11). MDL is a practical
version of Kolmogorov complexity embracing the slogan _Induction by
Compression_. Given a model class $\mathfrak{M}$ for some data $\mathcal{D}$,
the best model $M\in\mathfrak{M}$ minimizes $L(M)+L(\mathcal{D}\mid M)$, where
$L(M)$ is the description length of $M$, $L(\mathcal{D}\mid M)$ is the
description length of the data when encoded using $M$, and both are measured
in bits under our encoding. This is called _crude_ MDL, and it contrasts with
_refined_ MDL, which encodes the model and the data together (11). We opt for
crude MDL not only because it is computable but also because we are
particularly interested in the model: the structures shared by our input
graphs, and the transformations necessary to derive the individual graphs from
them. Finally, we require _lossless_ descriptions to ensure fair comparisons
between competing models.

All logarithms are to base $2$, and we define $\log 0=0$. We use
$\lfloor\cdot\rceil$ for rounding to the closest integer, and summarize our
notation in Table 2 in the Appendix.

##  3\. Theory

We now describe our first contribution, the MDL formulation of graph
similarity assessment. Our data is $\mathcal{D}=(G_{1},G_{2},\mathcal{A})$,
where $G_{1}$ and $G_{2}$ are our input graphs, and $\mathcal{A}$ is a
(potentially partial or empty) node alignment between $G_{1}$ and $G_{2}$.

###  3.1. Similarity Description, Informally

Our primary goal is to _describe_ the similarity of our input graphs. That is,
we aim to find the key structures that are shared between these graphs and
contrast them with the structures that are specific to the individual graphs.
By _structures_ , we mean subgraphs whose connectivity follows distinct,
interpretable patterns. Our _structure vocabulary_ $\Omega$ comprises four
structure types: (approximate) _cliques_ , _stars_ , _bicliques_ , and
_starcliques_. We choose these structure types because they are simple and
widespread in real-world graphs from many different fields, but further
structure types can easily be included, e.g., to tailor our method to a
particular domain.

Intuitively, _cliques_ are subgraphs with relatively homogeneous connectivity
whose density stands out against the background distribution (e.g., echo
chambers in social networks). _Stars_ are subgraphs in which one node, the
_hub_ , is connected to all other nodes, the _spokes_ , and the spokes are
hardly connected among themselves (e.g., influencers and their followers).
_Bicliques_ are subgraphs whose nodes can be partitioned into two sets, _left_
($L$) and _right_ ($R$), such that $L$ and $R$ are densely connected, the
nodes in $L$ are sparsely interconnected, and the nodes in $R$ are sparsely
interconnected (e.g., predators and prey in food webs). _Starcliques_ are
bicliques whose left nodes are densely, rather than sparsely,
interconnected—i.e., stars whose hub is a clique (e.g., core and periphery in
infrastructure networks). To describe real-world graphs accurately, we allow
structures to overlap on nodes _and_ on edges.

Figure 2. Graph structures are constraints over sets of (non-) edges. They can
be visualized as induced subgraphs (top), adjacency submatrices (middle), or
shapes (bottom). Each color in the adjacency submatrix is associated with a
different constraint, where the white constraint enforces loop-freeness.

As depicted in Figure 2, each structure imposes a set of constraints on the
connectivity in the adjacency submatrix it identifies. We think of the node
set sizes of a structure as _node fractions_ (relative to a reference $n$) and
of its connectivity constraints as _edge densities_ (relative to the maximum
possible number of edges).

We represent the structures we find in $G_{1}$ and $G_{2}$ individually as
lists $S_{1}$ and $S_{2}$ in their _individual models_ $M_{1}$ and $M_{2}$,
and the structures that are shared between $G_{1}$ and $G_{2}$ as a list
$S_{12}$ in their _common model_ $M_{12}$. To decide which structures to
include in $S_{12}$, we construct a matching $\mathcal{M}\subseteq S_{1}\times
S_{2}$, requiring that matched structures have the same type. For each
$(s_{1},s_{2})\in\mathcal{M}$, we include one structure $s$ of its type in
$S_{12}$, writing $\varphi_{1}(s)=s_{1}$ and $\varphi_{2}(s)=s_{2}$ for the
mappings from the shared structures to their counterparts. The node fractions
(edge densities) of $s$ are the averages of the node fractions (edge
densities) in $s_{1}$ and $s_{2}$. For example, if $s_{1}\in S_{1}$ is a
clique with node fraction $0.1$ and edge density $0.9$, and $s_{2}\in S_{2}$
is a clique with node fraction $0.2$ and edge density $0.7$, $s\in S_{12}$ is
a clique with node fraction $0.15$ and edge density $0.8$.

To link the common model to the individual models, we translate $M_{12}$ into
$M_{1}$ and $M_{2}$ using _transformations_ $\Delta_{1}$ and $\Delta_{2}$,
i.e., $\Delta_{1}(M_{12})=M_{1}$ and $\Delta_{2}(M_{12})=M_{2}$. Our
_transformation vocabulary_ $\Sigma$ contains edit operations to (1) add
unmatched structures contained in individual models, and (2) morph structures
from $M_{12}$ into those from $M_{1}$ and $M_{2}$, i.e., reverse the averaging
we perform when specifying the shared structures. For example, if a clique
$s\in S_{12}$ has node fraction $0.15$ and edge density $0.8$, and
$\varphi_{1}(s)=s_{1}\in S_{1}$ has node fraction $0.1$ and edge density
$0.9$, we need to _shrink_ the node fraction and _grow_ the edge density of
$s$ to match those in $s_{1}$.

To discover our common model $M_{12}$, individual models $M_{1}$, $M_{2}$, and
transformations $\Delta_{1}$, $\Delta_{2}$, we leverage the MDL principle. We
seek to optimize
$L(M_{12})+L(\Delta_{1},\Delta_{2})+L(G_{1}\parallel_{\mathcal{A}}G_{2}\mid
M_{12},\Delta_{1},\Delta_{2})$. For this purpose, we have to define several
encodings.

###  3.2. Similarity Description Encodings

We need to describe how we encode (1) the graphs $G_{1}$, $G_{2}$ under their
individual models $M_{1}$, $M_{2}$, (2) the models $M_{1}$, $M_{2}$, (3) the
common model $M_{12}$, and (4) the transformations $\Delta_{1}$, $\Delta_{2}$
in bits.

#### Encoding a Graph Under an Individual Model

Given a model $M$ of a graph $G$, rather than using an ad-hoc encoding of the
graph under the model (as is common practice), we seek to encode $G$
_optimally_ , leveraging the knowledge contained in $M$. As depicted in Figure
2, this knowledge primarily comes as constraints on the total number of edges
in the parts of the adjacency submatrix identified by the structures in $M$: A
clique imposes one constraint, a star imposes two constraints, and a biclique
or starclique imposes three constraints.

The probability distribution over the adjacency matrix $\mathbf{A}$ of $G$
that represents the knowledge imparted by $M$ (which includes $n$, $m$, and
loop-freeness) _without any bias_ is the distribution with the largest entropy
among all distributions fulfilling the constraints imposed by $M$. Under this
_maximum entropy distribution_ , $\Pr(a_{ij}\mid
M)=\frac{\exp(\sum_{\lambda\in\Lambda(i,j)}\lambda)}{1+\exp(\sum_{\lambda\in\Lambda(i,j)}\lambda)}$,
where $\Lambda(i,j)$ is the set of Lagrange multipliers associated with the
constraints covering $a_{ij}\in\mathbf{A}$ in the optimization problem finding
the maximum entropy distribution for $\mathbf{A}$ given $M$. The Shannon-
optimal code based on this distribution minimizes the worst-case expected
length of a message coming from the true distribution (8). Hence, the length
of $G$ given $M$ under an optimal encoding is

$\displaystyle L(G\mid M)=\sum_{a_{ij}\in A_{1}}-\log\Pr(a_{ij}\mid
M)+\sum_{a_{ij}\in A_{0}}-\log(1-\Pr(a_{ij}\mid M))\hphantom{\;},$

where $A_{x}=\\{a_{ij}\in\mathbf{A}\mid(a_{ij}=x)\wedge(i<j)\\}$ for
$x\in\\{0,1\\}$.

#### Encoding an Individual Model

To encode an individual model $M$ for a graph $G$, we communicate $n$, $m$,
and $|S|$ using $L_{\mathbb{N}}$, the universal code for positive integers
(24). We then transmit the number of structures per type, and for each
structure, in order, its type and its length. Thus, the length of an
individual model $M$ for a graph $G$ is

$\displaystyle
L(M)=L_{\mathbb{N}}(n+1)+L_{\mathbb{N}}(m+1)+L_{\mathbb{N}}(|S|+1)+\log\binom{|S|+|\Omega|-1}{|\Omega|-1}$
$\displaystyle+\sum_{s\in S}\big{(}-\log\Pr(\text{type}(s)\mid S)+L(s)\big{)}$
$\displaystyle\hphantom{\;}.$

Each structure is defined _abstractly_ by its constraints (cf. Figure 2), and
when we seek to find an MDL-optimal individual model, it is further identified
by _concrete_ node IDs (typeset in grey). Assuming that all structures contain
a positive number of nodes, the detailed encoding of our structures is as
follows.

##### Cliques

To communicate a clique $s$, we transmit its number of nodes $n_{s}$, its
number of edges $m_{s}$ or non-edges $\overline{m}_{s}$, and the node IDs.
Therefore, with $m^{*}_{s}=n_{s}(n_{s}-1)/2$, the length of a clique is

$\displaystyle
L(s)=L_{\mathbb{N}}(n_{s})+1+\log\log\bigg{\lfloor}\frac{m^{*}_{s}}{2}\bigg{\rfloor}+\log(\min\\{m_{s},\overline{m}_{s}\\})\leavevmode\nobreak\
{\color[rgb]{0.4,0.4,0.4}\definecolor[named]{pgfstrokecolor}{rgb}{0.4,0.4,0.4}+\log\binom{n}{n_{s}}}\hphantom{\;}.$

##### Stars

To communicate a star $s$, we transmit its number of spokes $n_{s}-1$, the
number of edges between its spokes $x_{s}=m_{s}-n_{s}+1$, the hub’s ID, and
the spokes’ IDs. Hence, with $x^{*}_{s}=(n_{s}-1)(n_{s}-2)/2$, the length of a
star is

$\displaystyle L(s)=L_{\mathbb{N}}(n_{s}-1)+\log\log x^{*}_{s}+\log
x_{s}{\color[rgb]{0.4,0.4,0.4}\definecolor[named]{pgfstrokecolor}{rgb}{0.4,0.4,0.4}\leavevmode\nobreak\
+\log n+\log\binom{n-1}{n_{s}-1}}\;.$

##### Bicliques and Starcliques

To communicate a biclique $s$, we transmit (1) its number of nodes $n_{s}$,
(2) its number of left nodes $n_{L}$, (3) its number of edges between left
nodes $m_{L}$, (4) its number of edges between right nodes $m_{R}$, (5) its
number of non-edges between left nodes and right nodes $m^{*}_{A}-m_{A}$
(where $m^{*}_{A}:=n_{L}n_{R}$), and (6) the IDs of its left nodes and its
right nodes. Thus, with $m^{*}_{L}=n_{L}(n_{L}-1)/2$ and
$m^{*}_{R}=n_{R}(n_{R}-1)/2$, the length of a biclique is

$\displaystyle L(s)=L_{\mathbb{N}}(n_{s})+\log n_{s}+\log\log m^{*}_{L}+\log
m_{L}+\log\log m^{*}_{R}+\log m_{R}$ $\displaystyle+\log\log
m^{*}_{A}+\log(m^{*}_{A}-m_{A})\leavevmode\nobreak\
{\color[rgb]{0.4,0.4,0.4}\definecolor[named]{pgfstrokecolor}{rgb}{0.4,0.4,0.4}+\log\binom{n}{n_{L}}+\log\binom{n-n_{L}}{n_{s}-n_{L}}}$
$\displaystyle\hphantom{\;}.$

To transmit a starclique $s$, we replace $m_{L}$ by
$\overline{m}_{L}=m^{*}_{L}-m_{L}$.

#### Encoding a Common Model

When communicating $M_{12}$, w.l.o.g., we assume that $n_{1}\geq n_{2}$, and
we transmit the node fractions and edge densities of all shared structures
with reference to $n_{1}$. Since we explicitly want to handle unaligned graphs
and graphs of different sizes, their common model does not include node IDs.
To encode $M_{12}$, we hence use the expression for individual models, with
the node ID parts omitted, and the terms for $n$ and $m$ replaced by

$L_{\mathbb{N}}(n_{1}+1)+L_{\mathbb{N}}(n_{1}-n_{2}+1)+L_{\mathbb{N}}(m_{1}+1)+L_{\mathbb{N}}(|m_{1}-m_{2}|+1)+1\hphantom{\;}.$

#### Encoding Transformations

The common model $M_{12}$ contains only structures that are shared between
$G_{1}$ and $G_{2}$, and structures may be shared without being isomorphic.
Consequently, $M_{12}$ is generally different from $M_{1}$ and $M_{2}$, even
if we define all models without node IDs. _Transformations_ link $M_{12}$ to
$M_{1}$ and $M_{2}$ such that $\Delta_{1}(M_{12})=M_{1}$ and
$\Delta_{2}(M_{12})=M_{2}$. That is, for $i\in\\{1,2\\}$, $\Delta_{i}$ morphs
$M_{12}$ into $M_{i}$ by _growing_ or _shrinking_ the node fractions and edge
densities of the structures in $S_{12}$ to match those in $S_{i}$ as well as
_adding_ those structures from $S_{i}$ that have no counterpart in $S_{12}$.

To derive the necessary content for the transformations, we reason as follows.
The node fractions and edge densities of each structure $s\in S_{12}$ are the
average of its representatives in $S_{1}$ and $S_{2}$, $\varphi_{1}(s)$ and
$\varphi_{2}(s)$. Hence, for each structure in $s\in S_{12}$, we expect a
structure of the same type in $S_{1}$ and $S_{2}$. For each node fraction $x$
in $s$, we expect the size of its counterpart in $\varphi_{i}(s)$ to be
$\lfloor x\cdot n_{i}\rceil$, and for each edge density $y$ in $s$, we expect
the number of edges in its counterpart in $\varphi_{i}(s)$ to be $\lfloor
y\cdot m^{*}_{y}\rceil$, where $m^{*}_{y}$ is the maximum number of edges in
the associated area of $\mathbf{A}_{i}$ (for $i\in\\{1,2\\}$).

The transformation $\Delta_{i}$ is the deviation of $M_{i}$ from our
expectation based on $M_{12}$, and since the node fractions and edge densities
of each structure in $S_{12}$ are the average of its representatives in
$S_{1}$ and $S_{2}$, for the shared structures, we can infer $\Delta_{2}$ from
$\Delta_{1}$. Hence, to communicate $\Delta_{1}$ and $\Delta_{2}$, for each
node fraction $x$ (edge density $y$) in each structure $s\in S_{12}$, we
transmit the number of nodes (edges) we need to add or subtract from $\lfloor
x\cdot n_{1}\rceil$ ($\lfloor y\cdot m^{*}_{y}\rceil$) to arrive at the size
of its counterpart in $\varphi_{1}(s)$, along with the change direction
(_grow_ or _shrink_). Finally, we transmit the structures in
$\overline{S}_{1}:=S_{1}\setminus\leavevmode\nobreak\ \varphi_{1}(S_{12})$ and
the structures in $\overline{S}_{2}:=S_{2}\setminus\leavevmode\nobreak\
\varphi_{2}(S_{12})$.

Therefore, if $L(\delta_{1}:\delta_{1}(s)=\varphi_{1}(s))$ is the description
length of the transformation $\delta_{1}$ morphing $s$ into $\varphi_{1}(s)$,
and $T$ is the total number of change directions we need to transmit, the
length of the transformations $\Delta_{1}$ and $\Delta_{2}$ is

$\displaystyle L(\Delta_{1},\Delta_{2})=\sum_{s\in
S_{12}}L\big{(}\delta_{1}:\delta_{1}(s)=\varphi_{1}(s)\big{)}+\log
T+\sum_{i\in\\{1,2\\}}L_{\mathbb{N}}(|\overline{S}_{i}|+1)$
$\displaystyle+\sum_{i\in\\{1,2\\}}\Bigg{(}\log\binom{|\overline{S}_{i}|+|\Omega|-1}{|\Omega|-1}+\sum_{s\in\overline{S}_{i}}\big{(}-\log\Pr(\text{type}(s)\mid\overline{S}_{i})+L(s)\big{)}\Bigg{)}$
$\displaystyle\hphantom{\;}.$

Although we have defined the individual models $M_{1}$ and $M_{2}$, the common
model $M_{12}$, and the transformations $\Delta_{1}$ and $\Delta_{2}$ for
similarity _description_ , we can also use them for similarity _measurement_.

###  3.3. Similarity Measurement

For similarity measurement, our score should reflect the extent to which the
structure of the input graphs can be captured by their common model. Since
graphs have many permutation-invariant representations (unlike, e.g.,
strings), and computable instantiations of the Normalized Information Distance
typically use opaque compressors, defining such a score is not
straightforward. To guarantee computability and interpretability, we thus
instantiate the Normalized Information Distance using our _models as
compressors_.

Let $G_{1}$ and $G_{2}$ be our input graphs with alignment $\mathcal{A}$ and
individual models $M_{1}$ and $M_{2}$ (encoded without node IDs). Let $M_{12}$
be their best $\mathcal{A}$-respecting common model, and let $\Delta_{1}$ and
$\Delta_{2}$ be transformations such that $\Delta_{1}(M_{12})=M_{1}$ and
$\Delta_{2}(M_{12})=M_{2}$. The _Normalized Model Distance_ (NMD) between
$G_{1}$ and $G_{2}$ is

$\mathrm{NMD}(G_{1},G_{2})=\frac{L(M_{12})+L(\Delta_{1},\Delta_{2})-\min\\{L(M_{1}),L(M_{2})\\}}{\max\\{L(M_{1}),L(M_{2})\\}}\hphantom{\;}.$

The NMD is $0$ if $M_{12}=M_{1}=M_{2}$ (with
$\Delta_{1}=\Delta_{2}=\emptyset$), and it is $1$ if $M_{12}=\emptyset$ (with
$\Delta_{1}=M_{1}$ and $\Delta_{2}=M_{2}$). It allows us to compare our method
with other similarity _measurement_ methods even though our primary goal is
similarity _description_ , which we formalize next.

###  3.4. Similarity Description, Formally

We are now ready to formally state our problem.

The Graph Similarity Description Problem. _Given graphs $G_{1}$, $G_{2}$, and
a (full, partial, or empty) alignment $\mathcal{A}:V_{1}\rightarrow V_{2}$,
find individual models $M_{1}$, $M_{2}$, common model $M_{12}$, and
transformations $\Delta_{1}$, $\Delta_{2}$ minimizing
$L(M_{12})+L(\Delta_{1},\Delta_{2})+L(G_{1}\parallel_{\mathcal{A}}G_{2}\mid
M_{12},\Delta_{1},\Delta_{2})$. _

The search space is huge: Even if we searched for _one_ individual model only,
limited the number of structures to $k$, set the minimum size of a structure
to $r$, and required the union of all structures to form a partition of $V$,
we would need to search over $4^{k}$ times the number of partitions of $n$
into $k$ parts of size at least $r$. These partitions are in bijection with
the partitions of $n-k(r-1)$ into $k$ parts, and hence, there are
$S(n-k(r-1),k)$ of them, where $S$ is the Stirling number of the second kind.
Since we are looking for _three_ models with intricate interconnections, the
search space for our problem is even larger—not to mention the NP-hard
subproblems we need to solve to identify optimal structures (e.g., MaxClique).
Furthermore, our search space exhibits no structure such as (weak)
(anti-)monotonicity of the total description length that would allow us to
search it efficiently. Hence, we resort to heuristics.

##  4\. Algorithm

We now introduce our second contribution, an algorithmic framework, called
Momo (_Mo_ del of _mo_ dels), to approximate the graph similarity description
problem. To discover good models in practice, we break this problem into two
parts:

  1. (1)

Approximate the individual models $M_{1}$ and $M_{2}$ minimizing
$L(M_{1})+L(G_{1}\mid M_{1})\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ L(M_{2})+L(G_{2}\mid M_{2})$. Since these
models can be thought of as graph summaries, we refer to this task as _graph
summarization_.

  2. (2)

Given individual models $M_{1}$ and $M_{2}$, approximate the common model
$M_{12}$ and the associated transformations $\Delta_{1}$ and $\Delta_{2}$
minimizing
$L(M_{12})+L(\Delta_{1},\Delta_{2})+L(G_{1}\parallel_{\mathcal{A}}G_{2}\mid
M_{12},\Delta_{1},\Delta_{2})$. Since we require there to be a unique
structure in both $M_{1}$ and $M_{2}$ for each structure in $M_{12}$, this
means we search for an optimal alignment between the structures in $M_{1}$ and
$M_{2}$. Hence, we refer to this task as _model alignment_.

Given $M_{1}$, $M_{2}$, $M_{12}$, $\Delta_{1}$, and $\Delta_{2}$, the NMD can
be readily computed.

Our architecture is flexible in that (1) any algorithm generating graph
summaries using the structure vocabulary $\Omega$ can be used in the first
step, (2) any algorithm finding a common model and transformations based on
individual graph summaries using the structure vocabulary $\Omega$ and the
transformation vocabulary $\Sigma$ can be used in the second step, and (3) all
alphabets can be replaced with other alphabets (if they are mutually
compatible and the encoding is suitably amended), just as the NMD can be
substituted with an alternative measure, e.g., to adapt our method to a
specific domain.

###  4.1. Step One: Graph Summarization (Beppo)

We begin by summarizing each of our input graphs individually. That is, our
input is a single graph $G$ with node set $V$ and edge set $E$, and our output
is a model $M$ approximately minimizing $L(M)+L(G\mid M)$. Our procedure,
called Beppo, is given as Algorithm 1.

To start, we decompose our graph into a set $\mathcal{C}$ of connected
components of diameter at most three (l. 1). We do this by iteratively
selecting the node $v$ with the highest degree in the currently largest
connected component to form a component $C\in\mathcal{C}$ with its neighbors,
then deleting all edges incident with $v$, until no more components can be
formed. This procedure is similar to the SlashBurn algorithm (19), but we
recurse on the _globally_ , rather than the _locally_ largest connected
component to ensure that all our components have small diameter. The generated
components are used as seeds to produce candidates for each structure type
from our structure vocabulary $\Omega$, where we merge candidates of the same
type if they overlap on a large fraction of their nodes (l. 1–1). We sort the
remaining candidates, which can overlap on nodes _and edges_ , from largest to
smallest (l. 1). Finally, for each structure $s$, in order, we add $s$ to $M$
if this reduces our description length (l. 1–1), i.e., if $L(s)+L(G\mid
M\cup\\{s\\})<L(G\mid M)$.

To generate a candidate of a certain structure type from a given component $C$
with node set $V_{C}$ (l. 1), we proceed as follows.

For a _clique_ with node set $V_{s}$, we first find the maximum clique in $C$
and include its nodes in $V_{s}$, then we iteratively add the node from
$V\setminus V_{s}$ with the highest degree in $G$ that is connected to at
least $50\%$ of the nodes in $V_{s}$ until no more nodes fulfill this
criterion.

For a _star_ with spoke set $V^{\prime}_{s}$, we declare a node with the
highest degree in $C$ to be the hub $v$, set
$V^{\prime}_{s}=V_{C}\setminus\\{v\\}$, and then iteratively (1) identify the
nodes in $V^{\prime}_{s}$ that have more than $0.05\cdot|V^{\prime}_{s}|$
neighbors in $V^{\prime}_{s}$, and (2) remove the $\min\\{(0.1+0.01i),1\\}$
fraction of these nodes from $V^{\prime}_{s}$ that has the most neighbors in
$V^{\prime}_{s}$ in iteration $i$.

For a _biclique_ with node sets $L$ and $R$, to start, we set the right node
set to be the (at most) $5$ nodes in a _maximal_ independent set (MIS) of
$V_{C}$ that have the highest degree in $G$. We then identify the set
$L^{\prime}\subseteq V\setminus R$ of nodes that are connected to at least
$50\%$ of the nodes in $R$, and set $L$ to be the (at most) $5$ nodes in an
MIS of $L^{\prime}$ that have the highest degree in $G$. If $|L|<3$ or
$|R|<5$, we discard the candidate early. For the surviving candidates, we then
iteratively (1) identify the set $X$ of nodes from $V\setminus(L\cup R)$ that
are connected to at most $5\%$ of the nodes in $L$ and at least $50\%$ of the
nodes in $R$, adding to $L$ the node from $X$ (if any) with the most neighbors
in $R$, and (2) perform (1), switching the roles of $L$ and $R$, until no more
nodes satisfy our criteria for addition to $L$ or $R$.

For a _starclique_ with node sets $L$ and $R$, to start, we set $L$ to be the
set of nodes contained in the maximum clique of $C$. We then identify the set
$R^{\prime}\subseteq V\setminus L$ of nodes that are connected to at least
$50\%$ of the nodes in $L$, and set $R=\mathrm{MIS}(R^{\prime})$.
Subsequently, we iteratively (1) identify the set $X$ of nodes from
$V\setminus(L\cup R)$ that are connected to at least $50\%$ of the nodes in
$L$ and to at least $50\%$ of the nodes in $R$, adding to $L$ the node from
$X$ (if any) with the most neighbors in $R$, and (2) identify the set $Y$ of
nodes from $V\setminus(L\cup R)$ that are connected to at most $5\%$ of the
nodes in $R$ and to at least $50\%$ of the nodes in $L$, adding to $R$ the
node from $Y$ (if any) with the most neighbors in $L$, until no more nodes can
be added.

Running Beppo on the graphs $G_{1}$ and $G_{2}$, we obtain interpretable
individual models $M_{1}$ and $M_{2}$. Our next task is to align these models.

###  4.2. Step Two: Model Alignment (Gigi)

For the model alignment step, our inputs are the graphs $G_{1}$, $G_{2}$, the
node alignment $\mathcal{A}$, and the models $M_{1}$, $M_{2}$. Our outputs are
a common model $M_{12}$ and the transformations $\Delta_{1}$, $\Delta_{2}$,
which together minimize
$L(M_{12})+L(\Delta_{1},\Delta_{2})+L(G_{1}\parallel_{\mathcal{A}}G_{2}\leavevmode\nobreak\
\mid\leavevmode\nobreak\ M_{12},\Delta_{1},\Delta_{2})$ approximately. Our
procedure, called Gigi, is given as Algorithm 2.

Input: Graph $G$; structure vocabulary $\Omega$

Output: Model $M$ with structure list $S$

1 $\mathcal{C}\leftarrow$ Connected components of $G$ from decomposition

2 $S^{\prime},S\leftarrow[],[]$

3 forall  __structure types_ $\omega\in\Omega$_ do

4 forall  __components_ $C\in\mathcal{C}$_ do

5 Generate candidate of type $\omega$ from $C$

6 Merge generated candidates if they have large overlap

7 Append remaining candidates to $S^{\prime}$

8

9Sort structures $s\in S^{\prime}$ by $(n_{s},m_{s})$ (descending)

10 forall  __structures_ $s\in S^{\prime}$_ do

11 if  _$L(s)+L(G\mid M\cup\\{s\\}) <L(G\mid M)$_ then

12 Append $s$ to $S$

13

return _$M$_

Algorithm 1 Graph summarization with Beppo

Input: Individual models $M_{1}$, $M_{2}$ with structures $S_{1}$, $S_{2}$;
node alignment $\mathcal{A}$; transformation vocabulary $\Sigma$

Output: Common model $M_{12}$ and transformations $\Delta_{1}$, $\Delta_{2}$
such that $\Delta_{1}(M_{12})=M_{1}$, $\Delta_{2}(M_{12})=M_{2}$

Compute constrained matching $\mathcal{M}\subseteq S_{1}\times S_{2}$

// Alg. 3

1 $M_{12},\Delta_{1},\Delta_{2}\leftarrow$ [], [], []

2 forall  __structures_ $(s_{1},s_{2})\in\mathcal{M}$_ do

3 Compute the common structure $s$ for $(s_{1},s_{2})$

4 Compute $\delta_{i}$ such that $\delta_{i}(s)=s_{i}$ for $i\in\\{1,2\\}$

5 Append $s$ to $M_{12}$ and $\delta_{i}$ to $\Delta_{i}$ for $i\in\\{1,2\\}$

6

7for  _$i\in\\{1,2\\}$_ do

8 forall  __structures_ $s\in S_{i}\setminus\\{s\in S_{i}\mid\exists
p\in\mathcal{M}:s\in p\\}$_ do

9 Append $s$ to $\Delta_{i}$

10

return _$M_{12}$ , $\Delta_{1}$, $\Delta_{2}$_

Algorithm 2 Model alignment with Gigi

In the critical first step, detailed below, Gigi computes a (bipartite)
matching $\mathcal{M}\subseteq S_{1}\times S_{2}$, pairing structures in
$S_{1}$ with structures in $S_{2}$ (l. 2). The matching is _constrained_
because we require that paired structures have the same type
$\omega\in\Omega$. For each structure pair $(s_{1},s_{2})\in\mathcal{M}$, we
then compute its common structure $s$ as well as transformations $\delta_{1}$
and $\delta_{2}$ such that $\delta_{1}(s)=s_{1}$ and $\delta_{2}(s)=s_{2}$,
which we add to $M_{12}$, $\Delta_{1}$, and $\Delta_{2}$, respectively (l.
2–2). Finally, we add the unpaired structures from both $S_{1}$ and $S_{2}$ to
$\Delta_{1}$ and $\Delta_{2}$, ensuring that $\Delta_{1}(M_{12})=M_{1}$ and
$\Delta_{2}(M_{12})=M_{2}$ (l. 2–2).

Typically, the matching $\mathcal{M}$ is not uniquely defined. We are
interested in the matching that helps us minimize the description length.
Sweeping the search space naïvely is not an option: For a structure vocabulary
$\Omega$, there exist
$\prod_{\omega\in\Omega}(\omega_{\max}-\omega_{\min})!\cdot\binom{\omega_{\max}}{\omega_{\min}}$
different _maximal_ matchings alone, where, for $f\in\\{\min,\max\\}$,
$\omega_{f}=f\\{|\\{s\in S_{1}\mid\mathrm{type}(s)=\omega\\}|,|\\{s\in
S_{2}\mid\mathrm{type}(s)=\omega\\}|\\}$. Hence, we propose a matching
heuristic, MaximalGreedy, whose detailed pseudocode is given as Algorithm 3 in
the Appendix.

If no node alignment is present, for $i\in\\{1,2\\}$, MaximalGreedy constructs
_node overlap graphs_ $H_{i}$. The nodes of these graphs are the structures in
$S_{i}$, and the weights of their edges $F_{i}$ are the Jaccard similarities
between the node sets of the structures (l. 3). MaximalGreedy then builds a
variant of the _product graph_ of $H_{1}$ and $H_{2}$, whose nodes are the
subset of $S_{1}\times S_{2}$ that agrees on type, and whose edge weights are
the product of the edge weights in $H_{1}$ and $H_{2}$ (l. 4–6). MaximalGreedy
then iteratively selects the heaviest edges in the product graph and removes
all nodes that are incompatible with these edges (l. 7–12). Finally, it pairs
the remaining structures of the same type in descending order of their size
(l. 13–19).

If a (partial) node alignment $\mathcal{A}$ is present, MaximalGreedy
iteratively matches those structures $s_{1}$ and $s_{2}$ of the same type
whose node sets have the largest average Jaccard similarity under
$\mathcal{A}$ (l. 20–27). For cliques, this equals the standard Jaccard
similarity. For structures of other types, it is defined as

$\displaystyle\text{Jaccard}_{\mathcal{A}}(s_{1},s_{2})=\frac{1}{2}\cdot\sum_{i\in\\{1,2\\}}\frac{|\mathcal{A}(V_{i}(s_{1}))\cap
V_{i}(s_{2})|}{|\mathcal{A}(V_{i}(s_{1}))\cup V_{i}(s_{2})|}\hphantom{\;},$

where $V_{1}$ and $V_{2}$ are the hub and spoke sets (for stars) or the left
and right node sets (for bicliques and starcliques), respectively.

MaximalGreedy is designed to ensure interpretability: In the presence of a
node alignment, it honors the node overlap of structures _between_ graphs, and
in the absence of such an alignment, it honors the node overlap of structures
_within_ graphs, all while respecting the constraints imposed by the structure
types.

###  4.3. Computational Complexity

Having specified Beppo and Gigi as the main components of Momo, we now analyze
Momo’s complexity. Here, we assume that the total number of structures is
$\mathcal{O}(1)$, which is required for interpretability.

For Beppo, due to the set intersection operations involved, constructing
structure candidates is $\tilde{\mathcal{O}}(nm)$, where $\tilde{\mathcal{O}}$
hides polylogarithmic factors. To decide whether to add a candidate to our
model, we need to find the maximum entropy distribution for the adjacency
matrix of the graph given that model, which is $\mathcal{O}(1)$ since the
number of Lagrange multipliers is $\mathcal{O}(1)$. We also need to keep track
of the mapping of Lagrange multipliers to potential edges, which is
$\mathcal{O}(n^{2})$ with $\mathcal{O}(1)$ candidates. Hence, Beppo runs in
$\tilde{\mathcal{O}}(nm)$.

Gigi’s complexity is driven by $\mathcal{O}(1)$ Jaccard similarity
computations, which together take $\mathcal{O}(n^{2})$ in the worst case
($\mathcal{O}(n)$ on average), where $n=\max\\{n_{1},n_{2}\\}$. Given
individual models $M_{1}$, $M_{2}$, and their model alignment
$(M_{12},\Delta_{1},\Delta_{2})$, computing the NMD takes $\mathcal{O}(1)$
basic arithmetic operations, i.e., its total complexity is $\mathcal{O}(1)$.

Overall, Momo’s complexity is dominated by Beppo, and hence
$\tilde{\mathcal{O}}(nm)$ in the worst case. However, as we show in Section 6,
in practice, Momo’s performance is near-linear in the number of edges.

##  5\. Related Work

To the best of our knowledge, we are the first to treat graph similarity
assessment primarily as a _description_ problem, rather than as a
_measurement_ problem. Related work broadly falls into two categories: graph
similarity measurement and graph summarization.

##### Graph Similarity Measurement

Early work on graph similarity measurement uses _global_ measures that capture
graph _structure_ , e.g., graph edit distance and maximum common subgraphs
(12; 23; 30). Later research also explores measures that capture graph
_connectivity_ (15), leverage graph _decompositions_ (21), or aggregate
_local_ similarities via node feature distributions (3; 2). Building on prior
work concerning _graph kernels_ (4; 26), recent contributions investigate
similarity learning via _deep_ graph kernels (29; 28; 20; 22).

In contrast to the existing literature, first, our _primary goal_ is graph
similarity _description_ , not _measurement_. Second, our _perspective_
emphasizes _interpretability_ , which leads us to build on intuitive meso-
level structures, rather than (overwhelmingly numerous) micro-level node
features, motifs, or (opaque) macro-level graph features. Third, our
_approach_ is novel in that it formalizes graph similarity as a model
selection task using the MDL principle.

When evaluating Momo, we compare the NMD to another normalized similarity
measure that is also based on information-theoretic principles: the _Network
Portrait Divergence_ (NPD) (2). The NPD is the Jensen-Shannon divergence of
the probability distributions of the input graphs that describe how many nodes
have $x$ neighbors at distance $y$. We show that the NMD and the NPD often
capture similar trends, but only the NMD is intuitively interpretable.

##### MDL-Based Graph Summarization

Although novel in graph similarity assessment, the MDL principle has been used
extensively in graph summarization. Starting with the SUBDUE system (5), a
rich line of work has sought to move summarization beyond clustering using
more expressive vocabularies to identify meaningful structures in _static_
graphs (9; 19; 14; 10). MDL has also been used to find partitions in graph
_streams_ (27) or structures ranging across multiple _aligned_ snapshots of
_dynamic_ graphs (25; 13).

Going beyond the existing literature, first, we allow our structures to
overlap not only on nodes but also on _edges_ , and we can handle multiple
graphs even if they are _unaligned_. Second, we improve the _methodology_ of
previous static summarization methods, leveraging more noise-tolerant
structure definitions and an optimal encoding of the data under the model.
Third, in our structure search, we emphasize result _quality_ , reflecting the
need for accurate graph summaries as inputs to our comparison algorithm.

When evaluating Momo, we compare Beppo to VoG (14), a static graph summarizer
built on a similar graph decomposition method and vocabulary of interpretable
structures (including cliques, bicliques, stars, and chains) that neither uses
maximum entropy modeling or component post-processing nor allows edge overlap.
We show that Beppo discovers more informative summaries than VoG.

##  6\. Experiments

We now present our third contribution, an extensive evaluation of the
framework presented in Section 4. To this end, we implement Beppo in Julia and
all other parts of Momo in Python. We run our experiments on Intel E5-2643
CPUs with 256 GB RAM. All data, code, and results are publicly
available.222http://eda.mmci.uni-saarland.de/prj/momo;
https://doi.org/10.5281/zenodo.4780912 We answer three questions:

  1. Q1

Does Beppo create useful graph summaries?

  2. Q2

Does Gigi discover interpretable common models?

  3. Q3

Does Momo yield informative similarity scores?

To ensure interpretability, we limit our summaries to at most $100$
structures, although allowing more would give better compression.

In our experiments, we use real-world graphs from seven collections (cf.
Appendix Table 3): Graphs in the _asb_ and _asp_ collections represent peering
relations between Autonomous Systems, each in $9$ different weeks from $2001$
(16); graphs in the _bio_ collection represent physical interactions between
human proteins in $144$ different tissues, where the protein identities induce
partial node alignments between all pairs of graphs in the collection (31);
graphs in the _clg_ and _csi_ collections represent arXiv collaboration
networks of cs.LG and cs.SI in each year from $2011$ to $2020$ (6); and graphs
in the _lus_ and _lde_ collections represent references between sections of
the United States Code and the Code of Federal Regulations or their German
equivalents in each year from $1998$ to $2019$ (7). We also include two
collections of synthetic random graphs, _rba_ and _rer_ , based on the
Barabási-Albert (BA) model and the Erdős-Rényi (ER) model. Our graphs vary in
size and density, containing up to $160K$ nodes and up to $525K$ edges (cf.
Appendix Figure 10).

##### _Q1: Does Beppo create useful graph summaries?_

In our context, graph summaries are useful if they capture the essence of a
graph in an easily comprehensible manner. To assess whether Beppo creates such
summaries, we start by comparing with VoG, which has been shown to produce
useful graph summaries, on graphs from the VoG paper (14). As shown in Table
1, in all experiments, Beppo saves more bits relative to the original encoding
length than VoG-$k$ for the same $k$, i.e., it achieves a better compression
$L\%$. Moreover, Beppo’s compression is comparable to that of VoG-Greedy,
although it uses much fewer structures. That is, even though our encoding of
the data under the model is optimal, we manage to save more bits per structure
than VoG. We also observe that while Beppo uses its entire vocabulary to
summarize its input graphs, VoG finds almost only stars. As we show in Figure
3, despite doing more work than VoG, Beppo is near-linear in practice.

In the left panel of Figure 4, we tally how many structures of each type we
find and what compression we achieve, on average, in each graph from our
collections. Since the edges of ER graphs are chosen uniformly at random, and
BA graphs are grown using preferential attachment, it comes as no surprise
that we find at most one star (with minimal gain) in ER graphs and only stars
in BA graphs, achieving no or little compression. The highest fraction of
cliques occurs in the collaboration graphs (_clg_ , _csi_), where papers with
many authors induce cliques. The hubs of the stars in these graphs correspond
to well-known researchers with many independent collaborations, e.g., _Yoshua
Bengio_ , _Yang Liu_ , and _Sergey Levine_ in _clg_ $2020$. Some researchers
occur in several structures, e.g., in _csi_ $2020$, $6$ of the spokes in the
star around _Christos Faloutsos_ , shown in the right panel of Figure 4,
reappear in the star around _Danai Koutra_ , and some of them are also
connected. This demonstrates the importance of allowing structures to overlap
on nodes _and_ on edges, a feature absent from other state-of-the-art
summarizers like VoG. For the law graphs (_lde_ , _lus_), analysis by the
first author (who happens to hold a PhD in law) and discussion with legal
scholars revealed that we can classify stars based on the ratio of the in- and
out-degree of their hubs to uncover their legal function. Thus, Beppo produces
summaries that are useful to domain experts even for _directed_ graphs, which
sets it further apart from other methods.

Table 1. Beppo compresses graphs more efficiently than VoG. $|S|$ is the number of structures, and $L\%$ is the compression (in percent of the uncompressed encoded length).  |  |  | Beppo | VoG-$k$ | VoG-G
---|---|---|---|---|---
Graph | $n$ | $m$ | $|S|$ | $L\%$ | $|S|$ | $L\%$ | $|S|$ | $L\%$
Epinions | 75879 | 405740 | 100 | 20 | 100 | 5 | 2746 | 19
Enron | 79870 | 288364 | 100 | 18 | 100 | 7 | 2331 | 25
AS-Oregon | 13579 | 37448 | 100 | 28 | 100 | 21 | 399 | 29
Chocolate | 2877 | 5467 | 55 | 9 | 100 | 7 | 101 | 12
Controversy | 1093 | 2942 | 20 | 15 | 100 | 4 | 35 | 13
Figure 3. Beppo is near-linear and output-sensitive. Its computation time is
shown as a function of $m$, with markers scaled by the number of discovered
structures $|S|$.

Coll. | $\mathbf{\widehat{cl}}$ | $\mathbf{\widehat{st}}$ | $\mathbf{\widehat{bc}}$ | $\mathbf{\widehat{sc}}$ | $\widehat{L\%}$
---|---|---|---|---|---
asb | 1 | 96 | 0 | 1 | 29
asp | 3 | 91 | 0 | 6 | 29
bio | 6 | 52 | 1 | 2 | 9
clg | 24 | 36 | 0 | 2 | 8
csi | 13 | 48 | 0 | 1 | 16
lde | 0 | 98 | 1 | 1 | 1
lus | 0 | 95 | 4 | 1 | 4
rba | 0 | 68 | 0 | 0 | 3
rer | 0 | 1 | 0 | 0 | 0
(a) Results of Beppo

(a) Example star from _csi_ $2020$

Figure 4. Beppo identifies meaningful structures. We show its average
compression and number of structures per type (left), and an example star
discovered in _csi_ $2020$ (right).

Since we allow structures to overlap, Beppo’s summaries can be visualized
intuitively as _node overlap trees_. Node overlap trees are the maximum
spanning trees of node overlap graphs, i.e., each vertex in them represents a
structure, the edge weights are the Jaccard similarities between the node sets
of the structures, and we remove all edges that are lightest in a cycle. To
ensure connectivity, we introduce a root vertex that connects to the vertex
with the largest degree inside each component. We depict the node overlap
trees for selected digestive tract tissues from the _bio_ collection in Figure
5. Here, larger shapes indicate larger structures, and thicker edges indicate
higher Jaccard similarities. From the vertices and the connectivity structure
of the trees, it is immediately apparent that the top-row tissues are very
similar, and indeed, the functions performed by the organs they represent are
closely related.

##### _Q2: Does Gigi discover interpretable common models?_

As Gigi builds on Beppo, the common models it discovers are composed of easily
comprehensible structures. By construction, this ensures a certain degree of
interpretability. To understand the composition of a common model $M_{12}$ and
its relationship to individual models $M_{1}$ and $M_{2}$, we can further
visualize these models using treemaps. We show an example from the _bio_
collection in Figure 6, contrasting the individual models for esophagus and
colon with their common model. We see that esophagus and colon have many
common structures, most of them stars, but the esophagus has more complex or
dense structures (cliques, bicliques, and starcliques), while the colon has
more simple sparse structures (stars). Using the node alignments between the
_bio_ graphs to annotate the shared structures with their average Jaccard
similarities, we observe that all stars that are shared between esophagus and
colon have a shared hub (indicated by a similarity above $0.5$). Similar
observations can be made for other tissues, e.g., the largest cliques in the
top-row tissues from Figure 5 all have a Jaccard similarity of at least
$0.58$. This indicates that _housekeeping proteins_ might be expressed as
_housekeeping structures_ that recur across tissues, but a detailed
investigation of this hypothesis lies outside the scope of this paper.

Beyond bilateral graph similarity assessment, Gigi’s output enables
comparisons between multiple graphs. As an example, in Figure 7, we display
the composition of the common models for comparisons of the esophagus with the
tissues from Figure 5 as a triptych of stacked bar charts. The graphic
illustrates that the relationship between esophagus and colon, shown in Figure
6, is comparable to that of the esophagus and _any_ top-row organ from Figure
5, and that all bottom-row organs share a biclique structure.

To further explore the relationships between shared structures, we can
leverage _common_ node overlap graphs, i.e., node overlap graphs induced by
our structure matching $\mathcal{M}$, with nodes
$(s_{1},s_{2})\in\mathcal{M}$, edges $((s_{1},s_{2}),(t_{1},t_{2}))$, and edge
weights $\prod_{i\in\\{1,2\\}}\mathrm{Jaccard}(s_{i},t_{i})$. These graphs
convey an interpretable notion of equivalence between the matched structures.
To visualize common node overlap graphs, we again use node overlap trees, and
Figure 11 in the Appendix shows an example from the _lde_ collection. While
not all patterns from the individual trees recur in the common tree, the trees
induced by the common tree in the individual node overlap graphs typically
weigh a large fraction of the individual node overlap trees, i.e., the
alignments discovered by Gigi respect much of the node overlap shared between
the structures in our input graphs.

Figure 5. Beppo creates similar summaries with similar node overlap structure
for similar graphs. The node overlap trees for selected digestive tract organs
in the _bio_ collection mirror the functional (dis)similarity between these
organs.  Figure 6. Gigi discovers interpretable common models. The common
model (left) for esophagus (middle) and colon (right) contains mostly
structures with high average Jaccard similarity (annotations). Each rectangle
corresponds to a structure, sized proportionally to its number of nodes, and
shared structures are greyed out in the individual models.  Figure 7. Gigi
allows multi-graph comparisons. Here, we juxtapose shared (left) and specific
(middle, right) structures for the esophagus and the tissues from Figure 5.

##### _Q3: Does Momo yield informative similarity scores?_

Although our focus is similarity _description_ , we can also use our
similarity score, the NMD, for similarity _measurement_. As depicted in Figure
12 in the Appendix, experiments on synthetic models show that the NMD is
almost scale-invariant when the graphs contain rescaled versions of the same
structures and their size differs within one order of magnitude, with larger
size differences leading to larger NMD values. The NMD also behaves
intuitively for models of varied compositions, showing a strong correlation
with the number of structures that can be matched across graphs.

When we compare NMDs to _Network Portrait Divergence_ values (NPDs), on the
yearly snapshots of the IBM GitHub collaboration network from $2013$ to $2017$
used in (2), the general trends are quite similar, but some years are _more_
similar and others are _less_ similar under NMD than under NPD (cf. Appendix
Figure 13). However, only our results are also interpretable: In $2014$, for
example, the network only has one star structure, explaining its high
dissimilarity to $2015$, which features one starclique and two cliques. The
differences between NMD values and NPD values are likely due to the dependence
of NPD on graph size, but since the underlying statistics are not intuitively
comprehensible, we cannot be sure.

Figure 8. NMDs are lower for cross-temporal comparisons of systems
experiencing gradual change (_asb_ , _asp_ , _lde_ , _lus_) than for cross-
temporal comparisons of systems undergoing radical change (_clg_ , _csi_) or
cross-sectional comparisons (_bio_).

In Figure 8, we depict the distribution of NMDs for all pairwise comparisons
of _different_ graphs in our real-world collections. We see that NMDs span the
whole range, and their distribution differs depending on the type of
comparison (_cross-sectional_ vs. _cross-temporal_) and the type of change
(_gradual_ vs. _radical_) experienced by the system we study. To illustrate
radical change, we show the NMDs of the collaboration graphs (_clg_ , _csi_)
from $2011$ to $2020$ in Figure 9. Both collections display the arrow of time,
but self-similarity drops faster in _clg_ than in _csi_ from about $2015$
onwards, and when comparing across collections, _csi_ $2015$ is most similar
to _clg_ $2015$ but _csi_ $2020$ is most similar to _clg_ $2017$. Thus, while
both communities have picked up tremendous pace in the past ten years,
development in _clg_ has been measurably more rapid than in _csi_.

Figure 9.  NMDs yield nuanced insights. The NMDs for the _clg_ and _csi_
graphs from $2011$ (top/left) to $2020$ (bottom/right) show the arrow of time
within each collection (left, right) and the lag between _clg_ and _csi_ from
$2015$ onwards (middle).

##  7\. Conclusion

We study graph similarity assessment as a _description_ problem, guided by the
question “ _how_ are these graphs similar?”. Formalizing the problem using the
MDL principle, we capture the similarity of the input graphs in their _common
model_ and the differences between them in _transformations_ to _individual
models_. Since our search space is huge and unstructured, we propose a
framework, Momo, which breaks the problem into two parts: Beppo creates graph
summaries that are useful to domain experts, and Gigi discovers interpretable
common models, from which we can also derive informative similarity scores.
Through experiments on undirected and directed graphs of radically varying
sizes from diverse domains, we confirm that Momo works well and is near-linear
in practice.

However, Momo also leaves room for improvement. For example, we would like to
handle richer graph types, including weighted and attributed graphs, using
encodings that fully leverage the available information. Ideally, Beppo and
Gigi would discover their structure and transformation vocabularies on the
fly, integrating domain-specific background knowledge in the process. An
improved structure encoding might account for the overlap between structures,
which is currently considered explicitly only by Gigi. Our NMD score focuses
on the models of the input graphs, and a more comprehensive measure could
integrate the data under these models.

Finally, MDL forces us to take a binary decision when considering structure
candidates, which can result in large differences between models based on
small differences between description lengths. To eliminate these artifacts
and still retain interpretability, we could consider the full set of high-
quality structure candidates and compress it using _structures of structures_.
This could lead to an _interpretable graph kernel_ , which—like overcoming
Momo’s other limitations—constitutes an engaging topic for future work.

## References

  * (1)
  * Bagrow and Bollt (2019) J. P. Bagrow and E. M. Bollt. 2019.  An information-theoretic, all-scales approach to comparing networks.  Applied Network Science 4, 1 (2019), 45:1–45:15.
  * Berlingerio et al. (2013) M. Berlingerio, D. Koutra, T. Eliassi-Rad, and C. Faloutsos. 2013.  Network similarity via multiple social theories. In ASONAM. ACM, 1439–1440.
  * Borgwardt and Kriegel (2005) K. M. Borgwardt and H.-P. Kriegel. 2005.  Shortest-path kernels on graphs. In ICDM. IEEE, 8 pp.
  * Cook and Holder (1994) D. J. Cook and L. B. Holder. 1994.  Substructure Discovery Using Minimum Description Length and Background Knowledge.  JAIR 1 (1994), 231–255.
  * Cornell University (2020) Cornell University. 2020\.  arXiv Dataset, Version 18 (2020/11/22).  (2020).  https://www.kaggle.com/Cornell-University/arxiv
  * Coupette et al. (2021) C. Coupette, J. Beckedorf, D. Hartung, M. Bommarito, and D. M. Katz. 2021.  Measuring Law Over Time.  Frontiers in Physics (2021).  DOI:http://dx.doi.org/10.3389/fphy.2021.658463
  * De Bie (2011) T. De Bie. 2011\.  Maximum entropy models and subjective interestingness: an application to tiles in binary databases.  Data Min. Knowl. Disc. 23, 3 (2011), 407–446.
  * Feng et al. (2013) J. Feng, X. He, N. Hubig, C. Böhm, and C. Plant. 2013.  Compression-based graph mining exploiting structure primitives. In ICDM. IEEE, 181–190.
  * Goebl et al. (2016) S. Goebl, A. Tonch, C. Böhm, and C. Plant. 2016\.  MeGS: Partitioning meaningful subgraph structures using minimum description length. In ICDM. IEEE, 889–894.
  * Grünwald (2007) P. Grünwald. 2007\.  The Minimum Description Length Principle.  MIT Press.
  * Kaden (1990) F. Kaden. 1990.  Graph distances and similarity.  In Topics in Combinatorics and Graph Theory. Springer, 397–404.
  * Kapoor et al. (2020) S. Kapoor, D. K. Saxena, and M. van Leeuwen. 2020.  Online summarization of dynamic graphs using subjective interestingness for sequential data.  Data Min. Knowl. Disc. 35, 1 (2020), 1–39.
  * Koutra et al. (2015) D. Koutra, U. Kang, J. Vreeken, and C. Faloutsos. 2015\.  Summarizing and understanding large graphs.  Stat. Anal. Data Min. 8, 3 (2015), 183–202.
  * Koutra et al. (2016) D. Koutra, N. Shah, J. T. Vogelstein, B. Gallagher, and C. Faloutsos. 2016.  DeltaCon: principled massive-graph similarity function with attribution.  ACM TKDD 10, 3 (2016), 1–43.
  * Leskovec et al. (2007) J. Leskovec, J. Kleinberg, and C. Faloutsos. 2007\.  Graph evolution: Densification and shrinking diameters.  ACM TKDD 1, 1 (2007), 2:1–2:41.
  * Li et al. (2004) M. Li, X. Chen, X. Li, B. Ma, and P. Vitanyi. 2004.  The similarity metric.  IEEE TIT 50, 12 (2004), 3250–3264.
  * Li and Vitányi (1993) M. Li and P. Vitányi. 1993.  An Introduction to Kolmogorov Complexity and its Applications.  Springer.
  * Lim et al. (2014) Y. Lim, U. Kang, and C. Faloutsos. 2014.  SlashBurn: Graph compression and mining beyond caveman communities.  IEEE TKDE 26, 12 (2014), 3077–3089.
  * Ma et al. (2019) G. Ma, N. K. Ahmed, T. L. Willke, and P. S. Yu. 2019\.  Deep Graph Similarity Learning: A Survey.  (2019).  arXiv:cs.LG/1912.11615
  * Nikolentzos et al. (2018) G. Nikolentzos, P. Meladianos, S. Limnios, and M. Vazirgiannis. 2018.  A Degeneracy Framework for Graph Similarity. In IJCAI. 2595–2601.
  * Ok (2020) S. Ok. 2020.  A graph similarity for deep learning. In NeurIPS, Vol. 34.
  * Raymond et al. (2002) J. W. Raymond, E. J. Gardiner, and P. Willett. 2002\.  Rascal: Calculation of graph similarity using maximum common edge subgraphs.  Comput. J. 45, 6 (2002), 631–644.
  * Rissanen (1983) J. Rissanen. 1983\.  A Universal Prior for Integers and Estimation by Minimum Description Length.  Annals Stat. 11, 2 (1983), 416–431.
  * Shah et al. (2015) N. Shah, D. Koutra, T. Zou, B. Gallagher, and C. Faloutsos. 2015.  Timecrunch: Interpretable dynamic graph summarization. In KDD. ACM, 1055–1064.
  * Shervashidze et al. (2009) N. Shervashidze, S. Vishwanathan, T. Petri, K. Mehlhorn, and K. Borgwardt. 2009.  Efficient graphlet kernels for large graph comparison. In Artificial Intelligence and Statistics. 488–495.
  * Sun et al. (2007) J. Sun, C. Faloutsos, S. Papadimitriou, and P. S. Yu. 2007\.  GraphScope: parameter-free mining of large time-evolving graphs. In KDD. 687–696.
  * Togninalli et al. (2019) M. Togninalli, E. Ghisu, F. Llinares-López, B. Rieck, and K. Borgwardt. 2019.  Wasserstein weisfeiler-lehman graph kernels. In NeurIPS. 6439–6449.
  * Yanardag and Vishwanathan (2015) P. Yanardag and S. Vishwanathan. 2015.  Deep graph kernels. In KDD. ACM, 1365–1374.
  * Zeng et al. (2009) Z. Zeng, A. K. Tung, J. Wang, J. Feng, and L. Zhou. 2009.  Comparing stars: On approximating graph edit distance.  PVLDB 2, 1 (2009), 25–36.
  * Zitnik and Leskovec (2017) M. Zitnik and J. Leskovec. 2017.  Predicting multicellular function through multi-layer tissue networks.  Bioinformatics 33, 14 (2017), i190–i198.

##  Appendix A Appendix

In this Appendix, we provide further details on our algorithms, our data
(i.e., graph collections), and our experiments. The basic notation used
throughout our paper is summarized in Table 2. We make all our data, code, and
results publicly available.333http://eda.mmci.uni-saarland.de/prj/momo;
https://doi.org/10.5281/zenodo.4780912

#### Algorithms

In the following, we provide implementation details for all components of
Momo: Beppo, Gigi, and the NMD computation.

#####  Beppo

Beppo has a size threshold, which allows us to stop decomposing connected
components or discard generated candidates when they are too small. We set
this threshold to $10$ for all our experiments except when comparing NMDs with
NPDs, where we set it to $3$ because the input graphs are relatively small.

When deciding whether to merge candidates due to large overlap between their
node sets in the final candidate generation step, we choose our merge
thresholds such that we can reduce redundancy amongst candidates without
harming structure quality. For cliques, we set the merge threshold to $90\%$
of the nodes. For bicliques and starcliques, we require both the left sets and
the right sets of two candidates to overlap on $90\%$ of the nodes. We do not
merge stars even for large overlaps because this would result in structures of
a different type, which we generate separately.

We allow Beppo to stop early if (1) it has added a given maximum number of
structures to our model, or (2) we have tested a given maximum number of
candidates _without_ adding them to our model. As described at the beginning
of Section 6, to guarantee that our summaries are interpretable, we set their
maximum number of structures to $100$. We set the maximum number of rejected
candidates to $300$, but in our experiments, this becomes relevant only for
graphs from the _bio_ collection. Because these graphs are relatively dense,
Beppo creates many overlapping candidates, but few of them suffice to cover
most of the nodes and edges. With early stopping, we can thus shorten the
running time of Beppo without compromising the quality of our graph summaries.

#####  Gigi

In Section 4.2, we give a verbal description of the MaximalGreedy matching
heuristic used by Gigi. Supplementing this description, we provide the
detailed pseudocode of MaximalGreedy as Algorithm 3. To speed up the
computation when no node alignment is given and structures do not overlap, our
implementation has a no-overlap flag which, when set, allows us to skip
directly to the greedy matching (l. 3–3).

##### NMD Computation

If we compute the NMD naïvely, it is in rare cases possible to obtain a value
above $1$. This occurs when the models for the two graphs are so different
that encoding them individually is cheaper than encoding them using a common
model and transformations, i.e., when
$L(M_{12})+L(\Delta_{1},\Delta_{2})>L(M_{1})+L(M_{2})$. As any value above $1$
signals that we do not gain any bits by compressing $G_{1}$ and $G_{2}$
together, we set the NMD to $1$ in this situation.

For the _bio_ collection, the NMD distribution we report in Figure 8 is based
on structure matchings using node alignments induced by protein identities.
For all other collections, the distributions reported are based on structure
matchings without node alignments.

Table 2. Basic notation. Symbol |  Description
---|---
$G_{i}=(V_{i},E_{i})$ |  graph $i$ with node set (edge set) $V_{i}$ ($E_{i}$)
$n_{i}=|V_{i}|$ |  number of nodes in $G_{i}$
$m_{i}=|E_{i}|$ |  number of edges in $G_{i}$
$\mathbf{A}_{i}$ |  adjacency matrix of $G_{i}$
$\mathcal{A}_{ij}$ |  alignment between $V_{i}$ and $V_{j}$
$L(x)$ |  number of bits to describe $x$ using our encoding
$L_{\mathbb{N}}(x)$ |  number of bits to describe $x$ using the universal code for integers
$\log$ |  binary logarithm with $\log(0)=0$
$\lfloor x\rceil$ |  $x$ rounded to the closest integer

Input: Structure lists $S_{1}$, $S_{2}$; node alignment $\mathcal{A}$

Output: Structure matching $\mathcal{M}\subseteq S_{1}\times S_{2}$

1

2$\mathcal{M}\leftarrow\emptyset$

3 if  _$\mathcal{A}=\emptyset$_ then

4 $H_{i}\leftarrow(S_{i},F_{i},w_{i})$ for
$i\in\\{1,2\\},w_{i}((s,t))=\mathrm{Jaccard}(s,t)$

5 $V\leftarrow\big{\\{}(s_{1},s_{2})\in S_{1}\times
S_{2}\mid\mathrm{type}(s_{1})=\mathrm{type}(s_{2})\big{\\}}$

6
$E\leftarrow\big{\\{}\big{(}(s_{1},s_{2}),(t_{1},t_{2})\big{)}\mid(s_{1},t_{1})\in
F_{1},(s_{2},t_{2})\in F_{2}\big{\\}}$

7 $G$
$\leftarrow(V,E,w),w\big{(}\big{(}(s_{1},s_{2}),(t_{1},t_{2})\big{)}\big{)}=\prod_{i\in\\{1,2\\}}w_{i}((s_{i},t_{i}))$

8 while  _$E\neq\emptyset$_ do

9 $(u,v)\leftarrow\arg\max_{(u,v)\in E}w((u,v))$

10 Add $u$ and $v$ to $\mathcal{M}$

11 $X\leftarrow\\{x\in V\setminus\mathcal{M}\mid(x\cap
u\neq\emptyset)\vee(x\cap v\neq\emptyset)\\}$

12 $E\leftarrow E\setminus\\{(u,v)\\}$

13 $G\leftarrow G[V\setminus X]$

14

15 $\overline{S}_{i}\leftarrow S_{i}\setminus\\{s\in S_{i}\mid\exists
p\in\mathcal{M}:s\in p\\}$ for $i\in\\{1,2\\}$

16 forall  __structures_ $s_{1}\in\overline{S}_{1}$_ do

17 forall  __structures_ $s_{2}\in\overline{S}_{2}$_ do

18 if  _$\mathrm{type}(s_{1})=\mathrm{type}(s_{2})$_ then

19 Add $(s_{1},s_{2})$ to $\mathcal{M}$

20 $\overline{S}_{i}\leftarrow\overline{S}_{i}\setminus\\{s_{i}\\}$ for
$i\in\\{1,2\\}$

21 break

22

23

24

25

26else

27 $\overline{S}_{i}\leftarrow S_{i}$ for $i\in\\{1,2\\}$

28 while  __true_ _ do

29
$U\leftarrow\\{(s_{1},s_{2})\in\overline{S}_{1}\times\overline{S}_{2}\mid\mathrm{type}(s_{1})=\mathrm{type}(s_{2})\\}$

30 if  _$U=\emptyset$_ then break

31 $(s_{1},s_{2})\leftarrow\arg\max_{(s_{1},s_{2})\in U}\leavevmode\nobreak\
\text{Jaccard}_{\mathcal{A}}(s_{1},s_{2})$

32 Add $(s_{1},s_{2})$ to $\mathcal{M}$

33 $\overline{S}_{i}\leftarrow\overline{S}_{i}\setminus\\{s_{i}\\}$ for
$i\in\\{1,2\\}$

34

35

36

return _$\mathcal{M}$_

Algorithm 3 Structure matching with MaximalGreedy

#### Data

Beyond the implementation details of our algorithms, to facilitate the
interpretation of our results, we provide additional background on the graph
collections we use in our experiments. Supplementing the description at the
beginning of Section 6, we give an overview of our graph collections in Table
3, and show their distributions of $n$ and $m$ in Figure 10. For all
collections except _asb_ and _asp_ , we perform some preprocessing to
transform the data provided into the graphs we use, which is documented in our
codebase. All random graphs are generated with graph generators available in
the Python library networkx.

Table 3. Our experiments are based on graph collections from highly diverse domains. $N$ is the number of networks in the respective collection. Coll. | Description | $N$ | Distinction | Source
---|---|---|---|---
asb | AS Oregon RouteViews basic | $9$ | 2001/03/31–05/26, | (16)
asp | AS Oregon RouteViews plus | $9$ | weekly
bio | physical protein interactions | 144 | human tissues | (31)
clg | arXiv cs.LG collaborations | $10$ | 2011–2020, | (6)
csi | arXiv cs.SI collaborations | $10$ | yearly (11/01)
lde | German federal law | $22$ | 1998–2019, | (7)
lus | United States federal law | $22$ | yearly
rba | Barabási-Albert random graphs | $50$ |  $10$ sizes, | –
rer | Erdős-Rényi random graphs | $50$ |  $5$ seeds | –

(a) Distribution of $n$

(b) Distribution of $m$

Figure 10. We consider graphs of radically varying sizes.

#### Experiments

We complete our additional remarks by delivering the details we deferred in
Section 6. Full results for all our collections, including further
visualizations, are provided along with our code.

When comparing Beppo with VoG in Table 1 of Q1, we state the $n$ and $m$ we
found in the original input data, which sometimes differs slightly from those
reported in (14).

As promised when answering Q2, we juxtapose common and individual node overlap
trees for an example from the _lde_ collection in Figure 11. Here, the trees
induced by the common tree in the individual node overlap graphs weigh more
than $4/5$ of the individual node overlap trees.

Supplementing the discussion in Q3, in Figure 12, we provide a single-linkage
hierarchical clustering of the NMDs of synthetic graphs with
$n\in\bigcup_{i=1}^{10}\\{i\cdot 10^{4}\\}$ nodes that contain $\lfloor
100/|\mathcal{S}|\rfloor$ structures of each type in $\mathcal{S}$, for
$\mathcal{S}\in\mathcal{P}(\Omega)\setminus\emptyset$ ($150$ graphs in total).
Finally, we visualize our comparison of NMDs with NPDs in Figure 13.

Figure 11. Gigi discovers common models retaining much of the node overlap
shared by the structures in the individual graphs, as can be seen by comparing
common (left) and individual (middle, right) node overlap trees.  Figure 12.
NMDs are (almost) scale-invariant (light strip along the diagonal) and
correlate strongly with the number of structures that are matched across
graphs (seven distinct shades of red). Row and column colors indicate model
composition (mixed proportionally using blue, yellow, red, and magenta as the
base colors for our structures); labels show structure counts per type and
graph size (represented by $i$).  Figure 13. NMD and NPD detect similar
trends, but where they differ, only NMD values are easy to interpret. Here, we
compare NMD values (left) with NPD values (right) on the IBM GitHub
collaboration network from (2).