09 Graph Similarity Description – Key Vocabulary

Vocabulary flashcards covering key terms, concepts, algorithms, and structures introduced in the paper "Graph Similarity Description: How Are These Graphs Similar?"

Graph Similarity Assessment

The task of comparing two or more graphs to understand their commonalities and differences.

Graph Similarity Description

An approach that explains how graphs are similar by describing shared and specific structures instead of outputting a single numeric score.

Minimum Description Length (MDL) Principle

An information-theoretic model-selection framework that chooses the model minimizing the total number of bits needed to describe the model plus the data given the model.

Crude MDL

MDL variant in which model length and data-given-model length are encoded separately; used in this paper to emphasize model interpretability.

Kolmogorov Complexity

The length of the shortest program that outputs a given object on a universal Turing machine; basis for MDL but not computable in practice.

Information Distance

A measure equal to the maximum of the conditional Kolmogorov complexities K(x|y) and K(y|x), capturing the effort to transform x into y and vice-versa.

Common Model (M12)

A model that captures the structures shared by the input graphs being compared.

Individual Model (M1 / M2)

A model summarizing a single input graph, containing both shared and graph-specific structures.

Transformation (Δ1, Δ2)

A set of edit operations that morph the common model into each individual model, encoding graph-specific differences.

Structure Vocabulary (Ω)

The set of allowed subgraph patterns—clique, star, biclique, starclique—used to build models.

Clique

A subgraph in which every pair of nodes is connected; modeled with one constraint (high internal density).

Star

A hub-and-spokes subgraph where one central node connects to many peripheral nodes that are sparsely interconnected.

Biclique

A subgraph whose nodes can be partitioned into left and right sets with dense cross-connections and sparse internal links within each set.

Starclique

A biclique whose left partition forms a clique, combining a dense core with a sparse periphery.

Node Alignment

A (possibly partial) bijection between node sets of two graphs that indicates corresponding vertices.

Partial Alignment

An alignment where some nodes remain unmatched, allowing comparison of graphs of different sizes.

Node Fraction

The proportion of the graph’s nodes that participate in a structure, stored relative to a reference size in the model.

Edge Density

The ratio of present edges to possible edges inside a structure’s specified area of the adjacency matrix.

Transformation Vocabulary (Σ)

The set of edit operations (add, grow, shrink) allowed when converting the common model into individual models.

Momo Framework

‘Model of models’; the overall two-step framework (Beppo + Gigi) proposed to perform graph similarity description.

Beppo Algorithm

Step 1 of Momo; summarizes each graph individually by greedily adding MDL-beneficial structures.

Gigi Algorithm

Step 2 of Momo; aligns two individual models to build the common model and corresponding transformations.

Graph Summarization

The process of creating a compact, interpretable model of a single graph that minimizes MDL coding cost.

Model Alignment

The task of matching structures from two individual models to form a common model while respecting type constraints.

MaximalGreedy Matching

Heuristic used by Gigi that greedily pairs structures of the same type based on node overlap or alignment similarity.

Normalized Model Distance (NMD)

A normalized similarity score derived from MDL models: (L(M12)+L(Δ1,Δ2)−min{L(M1),L(M2)}) / max{L(M1),L(M2)}.

Maximum Entropy Distribution

The probability distribution over adjacency entries with highest entropy that still satisfies all model constraints; used for optimal graph encoding.

Lagrange Multipliers

Variables introduced to enforce structural constraints when computing the maximum-entropy encoding probabilities.

Universal Code for Integers (LN)

A prefix-free encoding that efficiently represents positive integers and is used to transmit counts in MDL descriptions.

Node Overlap Graph

A graph whose vertices are structures from a model and edge weights are Jaccard similarities of their node sets.

Node Overlap Tree

A maximum spanning tree of a node overlap graph, offering an interpretable visualization of structure overlaps.

SlashBurn Decomposition

A technique that iteratively removes high-degree nodes to peel a graph; Beppo adapts this idea to create small-diameter components.

Description Length L(x)

The number of bits required to encode object x under the chosen encoding scheme.

Overlap-Allowed Structures

The modeling choice permitting different structures to share nodes and even edges, increasing expressiveness of the summary.

Shannon-Optimal Code

The code derived from the true probability distribution that minimizes expected message length; applied when encoding graph data under a model.