Information-Theoretic Limits on Exact Subgraph Alignment Problem
Chun Hei Michael Shiu, Hei Victor Cheng, Lele Wang · 2026
Read Information-Theoretic Limits on Exact Subgraph Alignment Problem by Chun Hei Michael Shiu, Hei Victor Cheng, Lele Wang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-05173.txt.
Introduction
Chun Hei Michael Shiu, Hei Victor Cheng, and Lele Wang find information-theoretic limits for finding a small graph inside a larger one in a 2026 paper. Graph alignment matches vertices between two correlated graphs, but most theory assumes both graphs share the same vertices. Real tasks in computer vision, social networks, and bioinformatics instead ask where a small pattern graph sits inside a big graph, a harder subgraph version.
Existing algorithms and analyses do not directly address locating that specific subset of vertices. The authors study the exact subgraph alignment problem's fundamental limits: when recovery is possible at all, regardless of computing power. Such limits tell practitioners whether a matching failure reflects a weak algorithm or missing information that no algorithm could overcome.
Catalog record
| CREATOR | Chun Hei Michael Shiu, Hei Victor Cheng, Lele Wang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-05173
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Information-Theoretic Limits on Exact Subgraph Alignment Problem Chun Hei Michael Shiu, Hei Victor Cheng, Lele Wang 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 Erdös-Rényi 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. I Introduction † † This work was presented in part at the 2025 IEEE International Symposium on Information Theory [ 43 ] and submitted in part to the 2026 IEEE International Symposium on Information Theory. The graph alignment problem, also known as the graph matching problem or noisy graph isomorphism problem, has received increasing attention over the last decade due to its wide applications across multiple fields such as natural language processing [ 18 , 36 ] , bioinformatics [ 45 , 22 , 37 ] , and social network de-anonymization [ 34 , 21 ] , among others. The graph alignment problem aims to find the best vertex correspondence between two correlated graphs with respect to a certain criterion. Extensive studies have been done to establish the information-theoretic limits [ 35 , 8 , 9 , 51 ] and efficient algorithms [ 11 , 17 , 14 , 28 , 13 , 29 , 30 ] for the graph alignment problem. Variations such as seeded alignment [ 21 , 52 , 33 , 42 ] , database alignment [ 10 ] , and alignment with additional attribute information [ 53 , 48 , 49 ] have also been studied. Most existing work on graph alignment focuses on scenarios where the two graphs have the same number of vertices. However, in many real-world applications, such as computer vision [ 24 , 44 , 26 ] , social network analysis [ 16 , 12 , 27 ] , and bioinformatics [ 6 , 47 , 54 ] , the problem often involves locating a small graph pattern within a larger graph. For example, in chemistry and biology, when searching for a specific (properties indicating) molecules in a large structure, the goal is to identify and locate the set of vertices of the subgraph representing the molecules [ 6 ] . In applications such as social network analysis, finding both the user set (represented as vertices) and their vertex correspondence is crucial for tasks like user profiles matching [ 16 ] . Existing graph alignment analysis and algorithms are not well-suited for these scenarios, as they are not designed to identify the specific subset of vertices where the small graph pattern is embedded within the larger graph. Therefore, the task of locating a small graph pattern within a larger graph is not a trivial extension of the graph alignment problem. These challenges motivate the formulation of the subgraph alignment problem , which aims to recover the vertex set and/or the vertex correspondence of a small graph pattern embedded within a larger graph. A closely related problem from theoretical computer science is the subgraph isomorphism problem, which studies whether a given pattern exists as an induced subgraph in a larger base graph. The subgraph isomorphism problem is known to be NP-complete [ 19 ] . Nevertheless, it has been extensively investigated over the past decades in both theory and practice due to its wide range of applications. Several influential works, including efficient heuristics and algorithms such as QuickSI [ 39 ] , GraphQL [ 20 ] , have been developed to address subgraph alignment tasks in real-life applications. Another closely related problem is the graph isomorphism problem, which belongs to NP, but is not known to be either in P or NP-complete. The current state of the art of the graph isomorphism problem for all graphs is Babai’s quasi-polynomial time algorithm in [ 3 ] . Moreover, several studies have observed that the average-case complexity [ 31 , 38 , 46 ] of the graph isomorphism problem under random graph models can be polynomial time, suggesting that an average-case complexity analysis can yield more optimistic results than a worst-case complexity analysis. This motivates us to study the subgraph isomorphism problem from a similar average-case perspective. While it is well-understood that the subgraph isomorphism problem is computationally intractable in the worst-case, its average-case behavior remains far less explored. Therefore, our work (subgraph alignment problem) focuses on analyzing the conditions under which a random subgraph can be reliably located within a base graph, by allowing a vanishing probability of error as the graph size grows. To investigate the subgraph alignment problem, we introduce the Erdös-Rényi subgraph pair model . For a pair of graphs (G,H_{\pi}) , generated from the Erdös-Rényi subgraph pair model, we first generate G to be the base Erdös-Rényi graph on vertex set [n] according to the Erdös-Rényi measure. Then we choose m vertices from [n] uniformly at random, let \mathcal{S} denote the collection of the chosen vertices, and let H be the induced subgraph on the vertices \mathcal{S} . Next, the graph H is anonymized by applying a random bijection \pi from the vertices \mathcal{S} to [m] , and the anonymized graph is denoted as H_{\pi} . Under this formulation, one typical goal is to achieve exact set recovery , i.e., recovering the set \mathcal{S} . Moreover, conditioning on having exactly recovered \mathcal{S} , another typical goal is to achieve exact permutation recovery , i.e., recovering the set \mathcal{S} and the permutation \pi at the same time. Under our Erdös-Rényi subgraph pair model, we use a brute-force estimator for estimating the vertex set \mathcal{S} and the bijection \pi , and it turns out that the brute-force estimator is equivalent to the maximum a posterior (MAP) estimator. We establish the achievability and converse results for both exact set recovery and exact permutation recovery. Moreover, under certain mild conditions, we establish the following asymptotically tight thresholds for achievability and converse results for exact set recovery and exact permutation recovery respectively as n\to\infty (See Theorem 7 and Theorem 8 for the formal statement). The main contributions of this paper are summarized as follows. 1. Model Formulation. We propose the Erdös-Rényi subgraph pair model, which integrates ideas from the subgraph isomorphism problem and allows randomness in the subgraph,