Information-Theoretic Limits on Exact Subgraph Alignment Problem

Chun Hei Michael Shiu, Hei Victor Cheng, Lele Wang

TL;DR

This paper establishes the fundamental information-theoretic boundaries for the subgraph alignment problem—the task of finding a small, anonymized graph pattern hidden within a much larger network. By analyzing a random graph model, the authors identify the exact "tipping points" where recovering the hidden subgraph transitions from mathematically impossible to achievable, bridging the gap between graph theory and information theory.

What Problem Does This Paper Address?

Graph alignment is essentially the "search" function for networks. While standard graph alignment assumes you are matching two graphs of the same size, real-world tasks are rarely that neat. In bioinformatics, you might look for a specific protein structure within a massive cellular network; in social media, you might try to identify a specific group of users across different platforms.

This is the subgraph alignment problem: finding a "needle" (a small graph $H$) in a "haystack" (a large graph $G$). This is significantly harder than standard alignment because you must simultaneously solve two problems:

  1. Localization: Which subset of vertices in the large graph corresponds to the small pattern?
  2. Alignment: Once located, which specific vertex in the pattern matches which vertex in the large graph?

When the pattern is a perfect copy, this is the "subgraph isomorphism problem," which is notoriously NP-complete. This paper moves away from worst-case complexity to look at the average-case—asking when recovery is possible if the graphs are generated randomly.

Methods

The authors use the Erdös-Rényi subgraph pair model. They generate a large base graph $G$, pick a subset of vertices to form a subgraph $H$, and then "anonymize" $H$ by shuffling its labels (applying a random permutation $\pi$).

To find the limits of recovery, they analyze two criteria:

  • Exact Set Recovery: Just finding the right "neighborhood" (the set of vertices).
  • Exact Permutation Recovery: Finding the neighborhood and the correct mapping of every individual vertex.

The researchers employ a Brute-force/MAP (Maximum A Posteriori) Estimator to prove achievability. For the "converse" (proving when it's impossible), they use a novel approach based on structural entropy—a concept from lossless graph compression that quantifies how much information is actually contained in the shape of a graph, independent of its labels.

Datasets

As a theoretical study, this paper does not use empirical datasets. Instead, it relies on the Erdös-Rényi (ER) random graph model, $G(n, p)$, where $n$ is the number of vertices and $p$ is the probability of an edge existing between any two nodes. This is the standard mathematical benchmark for analyzing graph algorithms and information-theoretic limits.

Key Insights and Ideas

  • The Information vs. Search Space Trade-off: The core result shows that recovery depends on a tug-of-war between the "information" in the subgraph and the "noise" of the search space. The term $\frac{m}{2}h(p)$ represents the structural information in a subgraph of size $m$, while $\log n$ represents the complexity of searching through a graph of size $n$. If the information doesn't outweigh the search complexity, the subgraph is effectively "invisible."
  • Symmetry is the Enemy: For permutation recovery, the authors found an extra requirement: the subgraph must not be too symmetric. If a subgraph has many automorphisms (symmetries), you can find the right set of vertices but never be sure which vertex is which. This is captured by the condition $mp - \log m \to \infty$.
  • Entropy as a Bridge: By using structural entropy to prove the converse, the authors treat the subgraph alignment problem as a communication problem. If the "channel capacity" of the graph structure is lower than the entropy of the vertex selection, no decoder can ever recover the original set.

Key Results

The paper provides sharp thresholds for when recovery is possible as the graph size $n$ goes to infinity:

  • Set Recovery is achievable if $\frac{m}{2}h(p) - \log n \to \infty$.
  • Permutation Recovery is achievable if the above holds and the subgraph is sufficiently asymmetric ($mp - \log m \to \infty$).
  • Tightness: The authors show that these conditions are "almost tight." Specifically, if $\frac{m}{2}h(p) - \log(n/m) \to -\infty$, then no algorithm, regardless of its computational power, can recover the subgraph.
  • Improvement over prior work: This paper refines previous bounds by using the binary entropy function $h(p)$, which provides a much more accurate limit for graphs with varying edge densities compared to earlier results that relied on simpler logarithmic approximations.

Limitations and Future Work

  • Computational Complexity: The results are "information-theoretic," meaning they describe what is possible with unlimited computing power. The "Brute-force" estimator used in the proofs is computationally impossible for large graphs. The authors acknowledge that finding polynomial-time algorithms that reach these same limits is a major open challenge.
  • The "Log m" Gap: There is still a small mathematical gap (a factor of $\log m$) between the achievability and converse results in the most general cases. The authors conjecture a tighter limit (Conjecture 18) but note that proving it requires a deeper understanding of the expected number of symmetries in random subgraphs.
  • Model Generalization: The current work assumes the subgraph is an exact induced copy. Future work could explore "noisy" subgraph alignment, where edges might be deleted or added in the observed pattern.

Summary updated

Abstract

The graph alignment problem aims to identify the vertex correspondence between two correlated graphs. Most existing studies focus on the scenario in which the two graphs share the same vertex set. However, in many real-world applications, such as computer vision, social network analysis, and bioinformatics, the task often involves locating a small graph pattern within a larger graph. Existing graph alignment algorithms and analysis cannot directly address these scenarios because they are not designed to identify the specific subset of vertices where the small graph pattern resides within the larger graph. Motivated by this limitation, we introduce the subgraph alignment problem, which seeks to recover both the vertex set and/or the vertex correspondence of a small graph pattern embedded in a larger graph. In the special case where the small graph pattern is an induced subgraph of the larger graph and both the vertex set and correspondence are to be recovered, the problem reduces to the subgraph isomorphism problem, which is NP-complete in the worst case. In this paper, we formally formulate the subgraph alignment problem by proposing the Erdos-Renyi subgraph pair model together with some appropriate recovery criterion. We then establish almost-tight information-theoretic results for the subgraph alignment problem and present some novel approaches for the analysis.
BibTeX
@misc{shiu2026information,
  author = {Chun Hei Michael Shiu and Hei Victor Cheng and Lele Wang},
  title = {{Information-Theoretic Limits on Exact Subgraph Alignment Problem}},
  year = {2026},
  eprint = {2601.05173},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2601.05173},
}
Figure