arXiv:2604.19116v1 [cs.DB] 21 Apr 2026
LIVE: Learnable Monotonic Vertex Embedding for Efficient Exact Subgraph Matching (Technical Report) Yutong Ye
Weilong Ren
Yang Liu
Beihang University Beijing, China [email protected]
ShenZhen Institute of Computing Sciences Shenzhen, China [email protected]
Beihang University Beijing, China [email protected]
Mengyi Yan
Ruijie Wang
Li Sun
Shandong University Jinan, China [email protected]
Beihang University Beijing, China [email protected]
Beijing University of Posts and Telecommunications Beijing, China [email protected]
Jianxin Li
Philip S. Yu
Beihang University Beijing, China [email protected]
University of Illinois at Chicago Chicago, USA [email protected]
ABSTRACT Exact subgraph matching is a fundamental graph operator that supports many graph analytics tasks, yet it remains computationally challenging due to its NP-completeness. Recent learning-based approaches accelerate query processing via dominance-preserving vertex embeddings, but they suffer from expensive offline training, limited pruning effectiveness, and heavy reliance on complex index structures, all of which hinder the scalability to large graphs. In this paper, we propose Learnable MonotonIc Vertex Embedding (LIVE), a learning-based framework for efficient exact subgraph matching that scales to large graphs. LIVE enforces monotonicity among vertex embeddings by design, making dominance correctness an inherent structural property and enabling embedding learning to directly optimize vertex-level pruning power. To this end, we introduce a query cost model with a differentiable surrogate objective to guide efficient offline training. Moreover, we design a lightweight one-dimensional iLabel index that preserves dominance relationships and supports efficient online query processing. Extensive experiments on both synthetic and real-world datasets demonstrate that LIVE significantly outperforms state-of-the-art methods in efficiency and pruning effectiveness. PVLDB Reference Format: Yutong Ye, Weilong Ren, Yang Liu, Mengyi Yan, Ruijie Wang, Li Sun, Jianxin Li, and Philip S. Yu. LIVE: Learnable Monotonic Vertex Embedding for Efficient Exact Subgraph Matching (Technical Report). PVLDB, 14(1): XXX-XXX, 2020. doi:XX.XX/XXX.XX PVLDB Artifact Availability: This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected]. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 14, No. 1 ISSN 2150-8097. doi:XX.XX/XXX.XX
(a) academic network 𝐺
(b) query graph 𝑞
Figure 1: Research collaboration pattern discovery.
The source code, data, and/or other artifacts have been made available at https://github.com/JamesWhiteSnow/LIVE.
1
INTRODUCTION
Graph data management has become increasingly important in a wide range of real-world applications, e.g., social network analysis [2], knowledge graph discovery [37], and biological network mining [52]. Among various graph operators, exact subgraph matching is one of the most fundamental yet computationally challenging tasks. Given a large data graph and a user-specified query graph, an exact subgraph matching query aims to retrieve all subgraphs that are isomorphic to the query graph, preserving both structural and label consistency. Such a query plays a central role in many graph data-driven analytical tasks, e.g., pattern recognition [59], community search [65], and graph-based query answering [15]. Below, we give an example of a subgraph matching query for the discovery of research collaboration patterns in academic networks. Example 1. (Research Collaboration Pattern Discovery in Academic Networks) As shown in Figure 1(a), an academic collaboration network can be modeled as an undirected, vertex-labeled graph, where each vertex represents a researcher labeled by their primary
Table 1: Symbols and Descriptions
research field (e.g., database, data mining, machine learning, and security), and each edge represents a collaborative relationship among two researchers. Such networks naturally form large-scale graphs capturing scholarly collaborations. A common analytical task is to identify recurring collaboration structures that match a particular team formation pattern. For example, a conference organizer may wish to find research teams exhibiting a specific interdisciplinary pattern, e.g., “a core researcher in data mining collaborating with colleagues in database systems, machine learning, security”. This pattern can be expressed as a query graph 𝑞 (Figure 1(b)), where vertices denote researchers with specified research fields and edges denote collaborations. Given a large academic network 𝐺 (Figure 1(a)), exact subgraph matching retrieves all subgraphs 𝑔 ⊆ 𝐺 isomorphic to the query graph 𝑞. As illustrated, one valid match is 𝑔 = {𝑣 1, 𝑣 2, 𝑣 3, 𝑣 4 }, corresponding to researchers in data mining, database, machine learning, and security, with all collaborations preserved.
Symbol 𝐺 𝑞 𝑔 𝑣𝑖 (or 𝑞𝑖 ) 𝑒𝑖 𝑗 (or 𝑒𝑞𝑖 𝑞 𝑗 ) 𝑉 (𝐺 ) (or 𝑉 (𝑞) ) 𝐿 (𝐺 ) (or 𝐿 (𝑞) ) 𝑜 (𝑣𝑖 ) (or 𝑜 (𝑞𝑖 ) ) 𝑔1 (𝑣𝑖 ) (or 𝑠 1 (𝑣𝑖 ) ) N1 (𝑣𝑖 ) (or N1 (𝑞𝑖 ) )
Description a data graph a query graph a subgraph of the data graph 𝐺 a vertex in graph 𝐺 (or 𝑞 ) an edge in graph 𝐺 (or 𝑞 ) a set of vertices 𝑣𝑖 (or 𝑞𝑖 ) in graph 𝐺 (or 𝑞 ) a labeling function of graph 𝐺 (or 𝑞 ) a vertex embedding vector of 𝑣𝑖 (or 𝑞𝑖 ) a 1-hop subgraph (or substructure) of 𝑣𝑖 a set of 𝑣𝑖 ’s (or 𝑞𝑖 ’s) 1-hop neighbors
ods often fail to complete offline preprocessing on graphs with millions of vertices and edges within practical time budgets [62]. This leads to a natural question: Is it possible to design a learningbased approach that further accelerates exact subgraph matching with a lightweight offline training phase, while enabling efficient online query processing without relying on heavy index structures? Our Contributions. In this paper, we answer the question above affirmatively by proposing Learnable MonotonIc Vertex Embedding (LIVE), a novel framework for efficient exact subgraph matching on large graphs. Unlike prior learning-based approaches, LIVE rethinks the coupling between no-false-dismissal guarantees and pruning power for vertex embedding learning in exact subgraph matching. Specifically, LIVE introduces a design that enforces monotonicity among vertex embeddings by construction. As a result, the no-false-dismissal guarantee of candidate filtering becomes an inherent structural property of the embeddings, rather than an outcome learned through enumerating subgraph–substructure pairs. This decoupling allows embedding learning to move beyond mere correctness preservation and directly optimize embedding quality, i.e., vertex-level pruning power. Accordingly, we develop a cost model that estimates the query cost induced by vertex embeddings, and derive a continuously differentiable surrogate of this model, enabling effective optimization of vertex embeddings during offline training and leading to more efficient online query processing. Building on the learned monotonic vertex embeddings, we further design a lightweight iLabel index that maps multi-dimensional embeddings into a one-dimensional key space while preserving dominance relationships. This design transforms dominance-region search for query vertices to efficient range queries supported by a B+ -tree, thereby eliminating the need for complex indexing structures. In addition, we incorporate multiple pruning strategies during index traversal to further reduce the candidate search space. In summary, we make the following contributions:
Despite its importance, exact subgraph matching remains highly challenging. The problem has been proven to be NP-complete [14, 18], and the search space grows exponentially with graph size and structural complexity, e.g., an exact subgraph matching query on a graph with only 3𝐾 vertices and 10𝐾 edges can yield over 4 billion answers [49], rendering such queries very costly on large graphs. Prior Arts. Existing subgraph matching methods can be broadly classified into the following two categories. (1) Structural-based approaches [8–10, 22, 24, 27, 34, 47, 49]. These methods rely on explicit structural comparisons between the query graph and candidate subgraphs, which often incur high computational overhead and limit query efficiency. (2) Learning-based approaches [7, 35, 38, 54, 61, 62]. Recent works in this line leverage Graph Neural Networks (GNNs) to embed graphs into embedding spaces, transforming subgraph matching into efficient vector-based operations. Early studies primarily targeted approximate matching or graph similarity search [7, 35, 38], where embeddings are used to estimate structural similarity rather than to guarantee exact matches. More recent efforts have extended learning-based techniques to exact subgraph matching, either by learning matching orders [54, 61] or by preserving dominance relationships in the embedding space [62]. Among them, dominance-based methods (e.g., GNN-PE [62]) learn vertex embeddings from labels and 1-hop neighborhoods, such that subgraph containment can be verified via coordinatewise dominance. This property enables candidate filtering without false dismissals and yields substantial speedups over traditional structure-based methods (e.g., up to 1–2 orders of magnitude [62]). Despite these advances, dominance-learning–based approaches still suffer from two fundamental limitations: (i) expensive offline training that requires enumerating 1-hop subgraphs and all possible 1-hop substructures for each vertex, and (ii) limited pruning effectiveness during online queries, as embedding learning is tightly constrained by dominance correctness. To compensate for the latter, existing methods often rely on complex index structures [62], which incur substantial storage and traversal overhead. Consequently, while learning-based approaches make exact subgraph matching feasible on small to medium-sized graphs, they remain inadequate for large-scale graphs. For instance, these meth-
• We propose LIVE (Section 2), a learning-based framework for efficient exact subgraph matching scaling to large graphs. • We develop a learnable monotonic vertex embedding method (Section 3) that enforces dominance relationships by design, allowing embedding learning to focus solely on optimizing vertex-level pruning power. We further introduce a query cost model and derive a continuous, differentiable surrogate objective to guide offline training. 2
• We design a lightweight one-dimensional iLabel index (Section 4) that preserves dominance relationships among multidimensional vertex embeddings, enabling efficient online query processing with low storage and traversal overhead. • We propose an efficient online query processing algorithm (Section 5) that integrates multiple pruning strategies supported by the iLabel index. • We conduct extensive experiments on both synthetic and real-world datasets (Section 6), confirming the efficiency and effectiveness of our LIVE for exact subgraph matching. We review related work in Section 7 and conclude in Section 8.
2
Algorithm 1: The LIVE Framework for Exact Subgraph Matching Input: a data graph 𝐺 and a query graph 𝑞 Output: subgraphs 𝑔 ( ⊆ 𝐺 ) that are isomorphic to 𝑞 // Offline Phase // Generate vertex embeddings 1 train a vertex embedding model Emb (·) that minimizes query processing cost over the data graph 𝐺 2 generate an embedding 𝑜 (𝑣𝑖 ) for ∀𝑣𝑖 ∈ 𝐺 using the trained Emb (·) // Index construction 3 build an iLabel index I over the learned data vertex embeddings 𝑜 (𝑣𝑖 ) // Online Phase 4 for each query vertex 𝑞𝑖 ∈ 𝑞 do // Retrieve candidate matching vertices 5 generate the query vertex embedding 𝑜 (𝑞𝑖 ) using the trained embedding model Emb (·) 6 obtain the candidate matching vertices 𝑞𝑖 .cand_set for 𝑞𝑖 by traversing the index I // Obtain and refine candidate subgraphs 7 obtain a matching order 𝑄 of query vertices 𝑞𝑖 ∈ 𝑞 based on the sizes of the their candidate sets |𝑞𝑖 .𝑐𝑎𝑛𝑑 _𝑠𝑒𝑡 | 8 assemble and refine candidate subgraphs 𝑔 from candidate vertices in 𝑞𝑖 .𝑐𝑎𝑛𝑑 _𝑠𝑒𝑡
PROBLEM DEFINITION
This section formally defines the graph data model and the subgraph matching problem over a graph database. Table 1 summarizes the frequently used symbols and their descriptions.
2.1
Preliminaries
We start with basic notations. Graph. A graph, 𝐺 is denoted by 𝐺 = (𝑉 (𝐺), 𝐸 (𝐺), 𝜙 (𝐺), 𝐿(𝐺)), where 𝑉 (𝐺) is a set of vertices 𝑣𝑖 , 𝐸 (𝐺) is a set of edges 𝑒𝑖 𝑗 = (𝑣𝑖 , 𝑣 𝑗 ) connecting vertex pairs, 𝜙 (𝐺) is a mapping function from vertex pairs to edges (i.e., Φ(𝐺):𝑉 (𝐺) × 𝑉 (𝐺) → 𝐸 (𝐺)), and 𝐿(𝐺) is a vertex labeling function that assigns each vertex 𝑣𝑖 ∈ 𝑉 (𝐺) a label 𝐿(𝑣𝑖 ) describing its attribute or type. In this paper, we consider an undirected labeled graph, which is widely used in applications such as social networks [55], knowledge graphs [37], and biological interaction networks [29], where vertices represent entities and edges capture their relationships. Graph Isomorphism [6, 19]. Given two graphs 𝐺 1 = (𝑉1, 𝐸 1, 𝜙 1, 𝐿1 ) and 𝐺 2 = (𝑉2, 𝐸 2, 𝜙 2, 𝐿2 ), 𝐺 1 is said to be isomorphic to 𝐺 2 , denoted by 𝐺 1 ≡ 𝐺 2 , if there exists a bijection mapping 𝑓 : 𝑉1 → 𝑉2 satisfying the following two conditions: (i) label preservation: for each vertex 𝑣𝑖 ∈ 𝑉1 , 𝐿1 (𝑣𝑖 ) = 𝐿2 (𝑓 (𝑣𝑖 )); and (ii) edge preservation: for any vertex pair (𝑣𝑖 , 𝑣 𝑗 ) ∈ 𝐸 1 , (𝑓 (𝑣𝑖 ), 𝑓 (𝑣 𝑗 )) ∈ 𝐸 2 . Intuitively, 𝐺 1 and 𝐺 2 are isomorphic, if they have identical structural topology and vertex labels under the mapping 𝑓 . Subgraph Isomorphism. Let 𝐺 be a data graph and 𝑞 be a query graph. We say that 𝑞 is subgraph-isomorphic to 𝐺, denoted by 𝑞 ⊆ 𝐺, if there exists a subgraph 𝑔 ⊆ 𝐺 such that 𝑔 ≡ 𝑞. The subgraph isomorphism problem asks whether a query graph 𝑞 exactly matches a subgraph of 𝐺 while preserving structure and labels. The problem has been proven to be NP-complete [14, 18].
9
return subgraphs 𝑔 (≡ 𝑞 )
2.3
Recent learning-based techniques [54, 61] have explored exact subgraph matching via learned matching orders, while dominancelearning-based methods [62] further enable embedding-based candidate filtering without false dismissals. However, integrating learning into exact subgraph matching poses several challenges. First, to guarantee correctness during candidate search, existing methods often require enumerating a massive number of subgraph– substructure pairs to learn dominance-preserving embeddings, resulting in substantial offline training costs and limited scalability. Second, prior embedding learning approaches are primarily driven by correctness constraints and do not explicitly optimize the pruning power of vertex embeddings, leading to suboptimal filtering effectiveness during query processing, especially on large graphs. Finally, even with dominance-preserving embeddings, efficiently retrieving all dominating vertices typically relies on complex indexing structures, incurring high storage and traversal overhead. These challenges highlight the need for a new framework that preserves dominance correctness while scaling to large graphs in both offline vertex embedding training and online query processing.
2.4 2.2
Challenges
Exact Subgraph Matching Query
The LIVE Framework
Algorithm 1 illustrates a novel Learning-based Vertex Embedding (LIVE) framework for efficiently answering exact subgraph matching queries on large graphs using learned vertex embeddings. The framework consists of two phases: an offline precomputation phase (lines 1–3) and an online subgraph matching phase (lines 4–9). Offline Phase. The offline phase learns vertex embeddings and builds an index to support efficient query processing. Specifically, LIVE trains an embedding model Emb(·) on the data graph 𝐺 using a proposed cost model (see Section 3.3) to minimize the expected query cost induced by vertex embeddings (line 1). After training, LIVE generates an embedding 𝑜 (𝑣𝑖 ) for each data vertex 𝑣𝑖 ∈ 𝑉 (𝐺) using the learned model (line 2). Based on these embeddings, an
Based on the preliminaries in Section 2.1, we formally define the subgraph matching query as follows: Definition 1. (Exact Subgraph Matching Query) Given a large data graph 𝐺 and a query graph 𝑞, an exact subgraph matching query retrieves all subgraphs 𝑔 ⊆ 𝐺 such that 𝑔 ≡ 𝑞. In other words, the goal is to enumerate all subgraphs of 𝐺 that are structurally identical to the query pattern 𝑞. Exact subgraph matching is fundamental to many applications, including pattern discovery in social networks [44], molecule search in bioinformatics [3], and entity-relation extraction in knowledge graphs [46]. 3
(a) 𝑔1 (𝑣1 )
(b) 𝑠 1 (𝑣1 ) ⊆ 𝑔1 (𝑣1 )
Figure 3: Illustration of our monotonic vertex embedding 𝑜 (𝑣𝑖 ).
Figure 2: 𝑔1 (𝑣 1 ) and all its possible 𝑠 1 (𝑣 1 ). iLabel index I is constructed by mapping multi-dimensional vertex embeddings into a one-dimensional key space, enabling efficient range-based retrieval during query processing (line 3). Online Phase. Given a query graph 𝑞, the online phase retrieves and refines candidate vertices to enumerate exact matches. For each query vertex 𝑞𝑖 ∈ 𝑉 (𝑞), LIVE first computes its embedding 𝑜 (𝑞𝑖 ) using the trained model (lines 4–5). The iLabel index I is then traversed to obtain a candidate set 𝑞𝑖 .cand_set of vertices in 𝐺 that may match 𝑞𝑖 (line 6). After candidate sets are generated for all query vertices, LIVE determines a matching order 𝑄 of query vertices 𝑞𝑖 ∈ 𝑞 based on their candidate set sizes, prioritizing query vertices with fewer candidates (line 7). Finally, an exact refinement procedure assembles and verifies candidate subgraphs by extending partial matches according to the matching order and enforcing subgraph isomorphism constraints (line 8). Finally, LIVE returns all subgraphs 𝑔 ⊆ 𝐺 that are isomorphic to 𝑞 (line 9). The design of LIVE is detailed in the following sections. Sections 3 and 4 describe the offline phase, including monotonic vertex embedding learning and iLabel index construction, respectively, while Section 5 presents the online subgraph matching algorithm. Note. The key advantage of LIVE lies in its principled separation of correctness guarantees from efficiency-oriented optimization. By enforcing dominance correctness as an intrinsic property of vertex embeddings through monotonicity, LIVE allows embedding learning to directly optimize vertex-level pruning power for improved query efficiency. Meanwhile, the dominance-preserving index reduces the cost of candidate retrieval while ensuring exactness, i.e., no false dismissals occur during index traversal.
3
1-hop Subgraph. Given a data graph 𝐺, the 1-hop subgraph centered at a vertex 𝑣𝑖 ∈ 𝐺 is the induced subgraph containing 𝑣𝑖 and all its immediate neighbors: 𝑔1 (𝑣𝑖 ) = 𝐺 [{𝑣𝑖 } ∪ N1 (𝑣𝑖 )], where N1 (𝑣𝑖 ) denotes the set of 1-hop neighbors of 𝑣𝑖 in 𝐺. The 1-hop subgraph captures both the label of the center vertex 𝑣𝑖 and the structural context of its local neighborhood. In subgraph matching, 𝑔1 (𝑣𝑖 ) provides the necessary local context for determining whether 𝑣𝑖 ∈ 𝐺 can serve as a candidate match for a query vertex 𝑞𝑖 ∈ 𝑞. In particular, any valid match between 𝑞𝑖 and 𝑣𝑖 must satisfy local consistency constraints within their respective 1-hop neighborhoods. 1-hop Substructure. Given the 1-hop subgraph 𝑔1 (𝑣𝑖 ) of a data vertex 𝑣𝑖 ∈ 𝐺, a 1-hop substructure 𝑠 1 (𝑣𝑖 ) is a subgraph induced by 𝑣𝑖 and a subset of its 1-hop neighbors N1 (𝑣𝑖 ). For a query vertex 𝑞𝑖 ∈ 𝑞 with 1-hop subgraph 𝑔1 (𝑞𝑖 ), if 𝑞𝑖 can be matched to 𝑣𝑖 , then there exists a substructure 𝑠 1 (𝑣𝑖 ) ⊆ 𝑔1 (𝑣𝑖 ) such that 𝑔1 (𝑞𝑖 ) ≡ 𝑠 1 (𝑣𝑖 ). This observation yields a necessary condition for vertex-level matching: the local neighborhood N1 (𝑞𝑖 ) of a query vertex 𝑞𝑖 ∈ 𝑞 must be realizable as a substructure of the 1-hop subgraph of data vertex 𝑣𝑖 ∈ 𝐺. Figure 2(a) illustrates an example 1-hop subgraph 𝑔1 (𝑣 1 ), and Figure 2(b) shows all 8 (= 23 ) possible 1-hop substructures contained in 𝑔1 (𝑣 1 ).
3.2
LEARNABLE MONOTONIC VERTEX EMBEDDING
This section presents the design of monotonic vertex embeddings and the training of the embedding model Emb(·) in LIVE (lines 1–2 of Algorithm 1). Specifically, Section 3.1 introduces structural notions for characterizing vertex neighborhoods, Section 3.2 presents the monotonic embedding design and its dominance-preserving properties, and Section 3.3 describes cost-model-based embedding learning for achieving strong pruning power.
3.1
Monotonic Vertex Embedding Design
In this subsection, we present a vertex embedding design that maps each vertex and its local neighborhood into an embedding space, enabling efficient and exact candidate filtering via vertex embeddings. Under this design, subgraph inclusion relationships are preserved by construction, rather than learned from enumerated subgraph– substructure pairs as in [62]. Monotonic Vertex Embedding Function. We define a vertex embedding function 𝑓 : 𝑔1 (𝑣𝑖 ) → 𝑜 (𝑣𝑖 ) ∈ R𝑑 , where 𝑔1 (𝑣𝑖 ) denotes the 1-hop subgraph centered at 𝑣𝑖 , and 𝑜 (𝑣𝑖 ) is the 𝑑-dimensional embedding of vertex 𝑣𝑖 . The embedding function 𝑓 (·) is said to be monotonic with respect to subgraph inclusion if 𝑠 1 (𝑣𝑖 ) ⊆ 𝑔1 (𝑣𝑖 ) =⇒ 𝑜 (𝑠 1 (𝑣𝑖 )) ⪯ 𝑜 (𝑔1 (𝑣𝑖 )), where ⪯ denotes coordinate-wise dominance between two embeddings, i.e., 𝑜 (𝑠 1 (𝑣𝑖 )) [ 𝑗] ≤ 𝑜 (𝑔1 (𝑣𝑖 )) [ 𝑗] holds for the embedding values in all 𝑑 dimensions [62, 63]. This monotonicity ensures that subgraph inclusion for each vertex in graph 𝐺 is faithfully reflected as dominance in the learned embedding space. Below, we show how the embedding function 𝑓 (·) is constructed. Embedding Design. The embedding 𝑜 (𝑣𝑖 ) of a vertex 𝑣𝑖 consists of two components: a vertex label embedding (VLE) that captures
Preliminaries
We introduce two structural notions used throughout the paper, which serve as conceptual units for characterizing local matching feasibility without requiring explicit enumeration during learning. 4
(a) initial VLE vectors 𝑜𝑙 (𝑣𝑖 )
(b) initial VSE vectors 𝑜𝑠 (𝑣𝑖 )
Figure 4: An illustration of the monotonicity of our vertex embedding. Figure 5: An example of initial VLE/VSE distributions. Lemma 1. (Monotonicity of Vertex Embeddings). Given a 1hop subgraph 𝑔1 (𝑣𝑖 ) and one of its 1-hop substructures 𝑠 1 (𝑣𝑖 ) with 𝑠 1 (𝑣𝑖 ) ⊆ 𝑔1 (𝑣𝑖 ), their embeddings satisfy 𝑜 (𝑠 1 (𝑣𝑖 )) ⪯ 𝑜 (𝑔1 (𝑣𝑖 )).
the semantic information of 𝑣𝑖 , and a vertex structure embedding (VSE) that summarizes its local neighborhood structure. Vertex Label Embedding (VLE). Let 𝑜𝑙 (𝑣𝑖 ) denote the vertex label embedding of vertex 𝑣𝑖 , defined as 𝑜𝑙 (𝑣𝑖 ) = softplus(Emb(𝐿(𝑣𝑖 ))),
Proof. Both 𝑔1 (𝑣𝑖 ) and 𝑠 1 (𝑣𝑖 ) share the same center vertex 𝑣𝑖 and thus have identical vertex label embeddings. Since N1 (𝑠 1 (𝑣𝑖 )) ⊆ N1 (𝑔1 (𝑣𝑖 )), their structure embeddings satisfy ∑︁ ∑︁ 𝑜𝑠 (𝑠 1 (𝑣𝑖 )) = 𝑜𝑙 (𝑣 𝑗 ) ⪯ 𝑜𝑙 (𝑣 𝑗 ) = 𝑜𝑠 (𝑔1 (𝑣𝑖 )).
(1)
where Emb(·) is a trainable embedding model (see Section 3.3 for its training) that maps the vertex label 𝐿(𝑣𝑖 ) to a 𝑑-dimensional vector, and softplus(𝑥) = log(1 + 𝑒 𝑥 ). The softplus activation ensures that all embedding dimensions are strictly non-negative, which is required to preserve dominance relationships among vertices. As illustrated in Figure 3, vertex label embeddings 𝑜𝑙 (𝑣 1 )–𝑜𝑙 (𝑣 4 ) are generated for vertices 𝑣 1 –𝑣 4 according to their respective labels 𝐿(𝑣 1 )–𝐿(𝑣 4 ) using Eq. 1. Vertex Structure Embedding (VSE). Let 𝑜𝑠 (𝑣𝑖 ) denote the vertex structure embedding, which captures the local structural context of 𝑣𝑖 by aggregating the label embeddings of its 1-hop neighbors: ∑︁ 𝑜𝑠 (𝑣𝑖 ) = 𝑜𝑙 (𝑣 𝑗 ). (2)
𝑣 𝑗 ∈ N1 (𝑠 1 (𝑣𝑖 ) )
Combining this with the non-negative weighted sum defining 𝑜 (𝑣𝑖 ) yields 𝑜 (𝑠 1 (𝑣𝑖 )) ⪯ 𝑜 (𝑔1 (𝑣𝑖 )), completing the proof. □ No-False-Dismissal Guarantee. The monotonicity property directly provides a no-false-dismissal guarantee for vertex-level candidate filtering. If a query vertex 𝑞𝑖 ∈ 𝑞 can be matched to a data vertex 𝑣𝑖 ∈ 𝐺, then the 1-hop subgraph of 𝑞𝑖 must be a substructure of 𝑔1 (𝑣𝑖 ). By the monotonic embedding design, their embeddings satisfy 𝑜 (𝑞𝑖 ) ⪯ 𝑜 (𝑣𝑖 ). Consequently, filtering candidates based on the dominance relationship among vertex embeddings preserves all valid matches and does not eliminate any true matches.
𝑣 𝑗 ∈ N1 (𝑣𝑖 )
This aggregation summarizes the neighborhood structure of 𝑣𝑖 in a manner consistent with its 1-hop subgraph 𝑔1 (𝑣𝑖 ). Since the aggregation is a summation over non-negative vectors, it is monotonic w.r.t. neighbor inclusion. For example, in Figure 3, the structure embedding 𝑜𝑠 (𝑣𝑖 ) of vertex 𝑣 1 is obtained by summing the label embeddings of its neighbors, i.e., 𝑜𝑠 (𝑣 1 ) = 𝑜𝑙 (𝑣 2 ) + 𝑜𝑙 (𝑣 3 ) + 𝑜𝑙 (𝑣 4 ). Monotonic Vertex Embedding. The final monotonic embedding of vertex 𝑣𝑖 is a weighted combination of its VLE and VSE components: 𝑜 (𝑣𝑖 ) = 𝛼 𝑜𝑙 (𝑣𝑖 ) + 𝛽 𝑜𝑠 (𝑣𝑖 ),
𝑣 𝑗 ∈ N1 (𝑔1 (𝑣𝑖 ) )
Example 2. Figure 4 illustrates how monotonic vertex embedding enables safe and effective candidate filtering. In the data graph 𝐺, the 1-hop subgraph of vertex 𝑣 2 contains that of the query vertex 𝑞 1 , i.e., 𝑔1 (𝑞 1 ) ⊆ 𝑔1 (𝑣 2 ). By the monotonic embedding design, this inclusion relationship is preserved in the embedding space as a dominance relation, i.e., 𝑜 (𝑞 1 ) ⪯ 𝑜 (𝑣 2 ). Consequently, 𝑣 2 lies in the dominating region 𝐷𝑅(𝑜 (𝑞 1 )), which consists of vertices whose embedding values are no smaller than 𝑜 (𝑞 1 ) in all dimensions, and is correctly retained as a candidate for 𝑞 1 during index-based retrieval. Vertices whose embeddings fall outside 𝐷𝑅(𝑜 (𝑞 1 )) violate the dominance condition and can be safely pruned without affecting correctness. Note that some vertices (e.g., 𝑣 3 ) may satisfy the dominance condition yet fail to match 𝑞 1 due to higher-order structural constraints, which will be eliminated later (Section 5).
(3)
where 𝛼 and 𝛽 are non-negative weighting parameters (see Section 3.3 for their settings). This formulation jointly encodes vertex semantics and local structural information while preserving monotonicity. As illustrated in Figure 3, the embedding of vertex 𝑣 1 is computed as 𝑜 (𝑣 1 ) = 𝛼 𝑜𝑙 (𝑣 1 ) + 𝛽 𝑜𝑠 (𝑣 1 ). Monotonicity and Dominance Preservation. By construction, all components of 𝑜𝑙 (𝑣𝑖 ) and 𝑜𝑠 (𝑣𝑖 ) are non-negative, and both summation and weighted addition are monotonic operations. Consequently, for any 1-hop subgraph 𝑔1 (𝑣𝑖 ) and its 1-hop substructure 𝑠 1 (𝑣𝑖 ) with 𝑠 1 (𝑣𝑖 ) ⊆ 𝑔1 (𝑣𝑖 ), their embeddings satisfy 𝑜 (𝑠 1 (𝑣𝑖 )) [ 𝑗] ≤ 𝑜 (𝑔1 (𝑣𝑖 )) [ 𝑗] for all 𝑗 ∈ [1, 𝑑]. That is, the embedding function 𝑓 (·) preserves inclusion relationships among 1-hop subgraphs as dominance relationships in the embedding space.
Decoupling Correctness Guarantees from Embedding Optimization. Unlike existing dominance learning-based exact subgraph matching methods (e.g., [62]) that tightly couple the no-falsedismissal guarantee with the embedding learning objective, LIVE preserves subgraph containment as dominance relations in the embedding space by design, rather than through learning. As a result, the no-false-dismissal guarantee becomes an inherent structural property of the embedding, independent of the learning objective. 5
(a) learned VLE vectors 𝑜𝑙 (𝑣𝑖 )
(b) learned VSE vectors 𝑜𝑠 (𝑣𝑖 )
(c) optimized VLE vectors 𝑜𝑙 (𝑣𝑖 )
Figure 6: An example of optimized VLE/VSE vector distributions.
This decoupling enables a new optimization perspective. Once correctness is ensured by construction, embedding learning is freed from dominance constraints and can directly target pruning power and query efficiency. This insight motivates the cost-model–driven embedding optimization introduced in Section 3.3, which explicitly minimizes query cost rather than learning dominance relations.
3.3
(a) 𝛼 = 10, 𝛽 = 1
(b) 𝛼 = 1, 000, 𝛽 = 0.01
Figure 7: An example of 𝑜 (𝑣𝑖 ) with different 𝛼/𝛽.
dominated by it. Accordingly, minimizing query cost is equivalent to minimizing the total number of dominance relations among vertex embeddings in the embedding space. Intuitively, the notion of anti-dominance, which indicates an object dominates or is dominated by only a few others [11], naturally aligns with this optimization objective. Following this intuition, we formalize Eq. 4 using the following anti-dominance cost:
Cost Model-based Embedding Optimization
Given that the monotonic vertex embedding design in Section 3.2 guarantees dominance correctness by construction, in this subsection, we focus on improving embedding quality by maximizing pruning power to reduce query cost during candidate retrieval. During online query processing, the cost of matching a query vertex 𝑞𝑖 is determined by the number of data vertices whose embeddings are dominated by 𝑜 (𝑞𝑖 ), i.e., the size of the dominanceinduced candidate set {𝑣 𝑗 | 𝑜 (𝑞𝑖 ) ⪯ 𝑜 (𝑣 𝑗 )}. Accordingly, embedding optimization aims to reduce the number of dominated vertices, thereby minimizing the size of candidates examined during query processing. However, query embeddings are unknown during offline training, and enumerating all possible 1-hop substructures is infeasible due to their exponential growth with vertex degree Í ( 𝑣 ∈𝑉 (𝐺 ) 2𝑑𝑒𝑔 (𝑣) ). To address this, we estimate query cost on data vertices and use it as a surrogate for expected query behavior. Cost Model for Query Efficiency. Based on the above observation, we define a cost model that captures query efficiency by measuring the average number of vertices dominated by a data vertex embedding. The expected query cost is approximated as ∑︁ 1 Cost = 𝑣 𝑗 ∈ 𝑉 (𝐺) | 𝑜 (𝑣𝑖 ) ⪯ 𝑜 (𝑣 𝑗 ) , (4) |𝑉 (𝐺)|
𝐿cost =
1 |𝑉 (𝐺)| 2
∑︁
∑︁
1{𝑜 (𝑣𝑖 ) ⪯ 𝑜 (𝑣 𝑗 )},
(5)
𝑣𝑖 ∈𝑉 (𝐺 ) 𝑣 𝑗 ∈𝑉 (𝐺 )
where 1{·} is an indicator function that equals 1 if the embedding 𝑜 (𝑣𝑖 ) dominates 𝑜 (𝑣 𝑗 ), and 0 otherwise. This objective measures the expected number of dominance relations among all vertex pairs; minimizing it directly reduces the number of dominated vertices and thus improves vertex-level pruning power during query processing. However, the anti-dominance cost in Eq. 5 is inherently discrete due to the indicator function induced by coordinate-wise dominance, and therefore cannot be optimized directly using gradientbased methods. To enable efficient optimization, we derive a continuous and differentiable relaxation of this objective. Specifically, we approximate the indicator function with a sigmoid-based surrogate and define the anti-dominance loss as ∑︁ ∑︁ min𝑘 𝑜 (𝑣𝑖 ) [𝑘] − 𝑜 (𝑣 𝑗 ) [𝑘] 1 𝜎 , (6) 𝐿= |𝑉 (𝐺)| 2 𝜏 𝑣𝑖 ∈𝑉 (𝐺 ) 𝑣 𝑗 ∈𝑉 (𝐺 )
where 𝜎 (𝑥) = 1+𝑒1−𝑥 is the sigmoid function and 𝜏 is a temperature parameter that controls the smoothness of the approximation. Note that the min𝑘 (·) operator is piecewise linear and subdifferentiable. Following PointNet [43] and Deep Sets [64], we use standard automatic differentiation [42] to obtain a valid subgradient; nondifferentiable ties occur with probability 0 for continuous parameters.
𝑣𝑖 ∈𝑉 (𝐺 )
which represents the expected size of the candidate set induced by dominance-based filtering and serves as a proxy for query efficiency. Figure 5 visualizes the initial distributions of 2D vertex label embeddings (VLE) and vertex structure embeddings (VSE) on the Yeast dataset. The VLE vectors are randomly initialized and thus uniformly scattered in the embedding space (Figure 5(a)), resulting in relatively small candidate sets. In contrast, VSE vectors, computed by summing non-negative VLE vectors, exhibit a strong concentration along the diagonal (Figure 5(b)). This concentration causes many vertices to satisfy the dominance condition, leading to large candidate sets and high query cost. Anti-Dominance Objective and Continuous Relaxation. As shown in Eq. 4, the query cost induced by a query vertex embedding is determined by the number of data vertices whose embeddings are
Lemma 2. (Relationship Between Anti-Dominance Loss and Discrete Objective). Let 𝐿cost and 𝐿 be defined in Eqs. 5 and 6, respectively. As the temperature parameter 𝜏 → 0+ , the anti-dominance loss 𝐿 converges to the discrete anti-dominance cost 𝐿cost . Moreover, for any finite 𝜏 > 0, 𝐿 serves as a smooth upper bound of 𝐿cost . Proof. By definition, the dominance relation 𝑜 (𝑣𝑖 ) ⪯ 𝑜 (𝑣 𝑗 ) holds if and only if min𝑘 𝑜 (𝑣𝑖 ) [𝑘] − 𝑜 (𝑣 𝑗 ) [𝑘] ≤ 0. Accordingly, the discrete indicator function 1{𝑥 ≤ 0} can be approximated by the sigmoid function 𝜎 (𝑥/𝜏), which converges pointwise to the indicator as 𝜏 → 0+ . 6
Therefore, for any vertex pair (𝑣𝑖 , 𝑣 𝑗 ), we have: Yeast dataset. The remaining gap to the theoretical lower bound |𝑉 (𝐺 ) | |𝐿 (𝐺 ) | is mainly due to label distribution skew. min𝑘 𝑜 (𝑣𝑖 ) [𝑘] − 𝑜 (𝑣 𝑗 ) [𝑘] lim+ 𝜎 = 1 min 𝑜 (𝑣𝑖 ) [𝑘] − 𝑜 (𝑣 𝑗 ) [𝑘] ≤ 0 . Optimization of 𝛼 and 𝛽. We refine the vertex embedding 𝑜 (𝑣𝑖 ) = 𝜏→0 𝜏 𝑘 𝛼 𝑜𝑙 (𝑣𝑖 )+𝛽 𝑜𝑠 (𝑣𝑖 ) by tuning the weighting parameters 𝛼 and 𝛽. Since Substituting this limit into the definition of 𝐿 yields: the optimized VLE embeddings exhibit strong global separability, ∑︁ we treat them as the base distribution and use VSE as a fine-grained 1 1{𝑜 (𝑣𝑖 ) ⪯ 𝑜 (𝑣 𝑗 )} = 𝐿cost . lim 𝐿 = structural perturbation. Setting 𝛼 ≫ 𝛽 (e.g., 𝛼 = 1000; 𝛽 = 0.01) 𝜏→0+ |𝑉 (𝐺)| 2 𝑣 ,𝑣 𝑖 𝑗 preserves the favorable VLE distribution while incorporating local Moreover, for any finite 𝜏 > 0, the sigmoid function satisfies structural cues. As illustrated in Figures 7(a) and 7(b), increasing 𝜎 (𝑥/𝜏) ≥ 1{𝑥 ≤ 0} for all 𝑥. Thus, each term in 𝐿 upper-bounds the 𝛼/𝛽 ratio substantially reduces dominating-region overlap and the corresponding indicator term in 𝐿cost , which implies 𝐿 ≥ 𝐿cost . lowers the average query cost from 732.6 to 103.34. Equality holds asymptotically as 𝜏 → 0+ , completing the proof. □
4
Although the anti-dominance loss in Eq. 6 provides a differentiable surrogate for the discrete cost objective, directly optimizing it requires evaluating all vertex pairs, incurring 𝑂 (|𝑉 (𝐺)| 2 ) time/space cost and rendering it infeasible for large graphs. To address this, we adopt a sampling-based approximation during training: instead of summing over all vertex pairs, we uniformly sample vertex pairs (𝑣𝑖 , 𝑣 𝑗 ) from 𝑉 (𝐺) × 𝑉 (𝐺) and optimize the expected anti-dominance loss: min𝑘 𝑜 (𝑣𝑖 ) [𝑘] − 𝑜 (𝑣 𝑗 ) [𝑘] 𝐿 = E (𝑣𝑖 ,𝑣 𝑗 )∼U (𝑉 (𝐺 ) ×𝑉 (𝐺 ) ) 𝜎 (7) 𝜏
The monotonic vertex embeddings in Section 3 enable exact vertexlevel filtering via dominance relationships, but efficiently enumerating dominating vertices remains challenging for high-dimensional embeddings on large graphs. To address this, we propose iLabel, a lightweight index that preserves dominance relationships while mapping multi-dimensional embeddings into a one-dimensional key space, enabling efficient range-based candidate retrieval.
This sampling strategy preserves the expectation of the full loss in Eq. 6 while reducing the computational cost to be linear in the number of sampled pairs. Consequently, the anti-dominance loss can be efficiently optimized using stochastic gradient-based methods. Model Training. We train the vertex embedding model Emb(·) by minimizing the sampled anti-dominance loss in Eq. 7 using minibatch stochastic gradient descent. In each iteration, a mini-batch of vertex pairs is sampled to estimate gradients, while the temperature parameter 𝜏 is gradually annealed to tighten the approximation to the discrete cost objective. After convergence, the trained model Emb(·) is used to generate embeddings for all data vertices in 𝐺. Figures 6(a) and 6(b) show the distributions of VLE and VSE embeddings on the Yeast dataset after training. Compared to the initial distributions in Figure 5, both embeddings become substantially more dispersed, resulting in fewer dominated vertices. For example, the average query cost decreases from 1,182.6 (resp. 1,403.97) to 522.28 (resp. 1,027.27) for VLE (resp. VSE). Optimizations. We further apply the following optimizations during vertex embedding training. Optimization via 𝐿1 Normalization. Although optimizing the structure embeddings VSE effectively reduces query cost, the average cost of label embeddings VLE remains relatively high (522.28), still (𝐺 ) | exceeding the theoretical lower bound |𝑉 |𝐿 (𝐺 ) | = 3,112/71 = 43.83. This indicates room for further refinement. To enhance discriminability, we apply 𝐿1 normalization to VLE embeddings: 𝑜𝑙′ (𝑣𝑖 ) =
𝑜𝑙 (𝑣𝑖 ) , ∥𝑜𝑙 (𝑣𝑖 )∥ 1
ILABEL: A DOMINANCE-PRESERVING INDEX FOR MONOTONIC VERTEX EMBEDDINGS
4.1
Design of the iLabel Index
The design of iLabel exploits two properties of the learned monotonic vertex embeddings: (i) vertex label embeddings (VLE) naturally form semantic clusters with identical vertex labels, and (ii) the final embedding (𝑜 (·)) is a weighted combination of label and structural components with 𝛼 ≫ 𝛽, enabling non-overlapping clusters. Label-based Clustering Recall that in the monotonic embedding design (Section 3.2), the vertex label embedding (VLE) 𝑜𝑙 (𝑣) is solely determined by the vertex label. Consequently, all vertices sharing the same label are mapped to the same VLE vector, naturally partitioning data vertices into disjoint label-based clusters: C = {𝐶 1, 𝐶 2, . . . , 𝐶𝑚 },
𝐶𝑖 = {𝑣 𝑗 | 𝐿(𝑣 𝑗 ) = 𝑙𝑖 },
(9)
where each cluster 𝐶𝑖 consists of vertices in 𝐺 with label 𝑙𝑖 . For each cluster 𝐶𝑖 , we define its center as the corresponding label embedding: 𝑐𝑖 = 𝑜𝑙 (𝑣 𝑗 ), ∀𝑣 𝑗 ∈ 𝐶𝑖 . Within a cluster, vertices differ only in their structural embeddings 𝑜𝑠 (𝑣 𝑗 ), which capture local neighborhood variations around the same semantic label. During query processing, label-based clustering restricts candidate retrieval to clusters with labels compatible with the query vertex, thereby avoiding unnecessary access to irrelevant vertices. One-dimensional Key Mapping. Recall that each vertex embedding is constructed as 𝑜 (𝑣) = 𝛼 𝑜𝑙 (𝑣) + 𝛽 𝑜𝑠 (𝑣), where 𝛼 and 𝛽 are non-negative weights with 𝛼 ≫ 𝛽. This design ensures that inter-cluster separation is dominated by label embeddings, while intra-cluster ordering is governed by structural embeddings. iLabel maps each vertex embedding to a one-dimensional key:
(8)
which constrains embeddings to a constant-𝐿1 manifold and spreads them along the anti-diagonal direction. Empirically, as shown in Figure 6(c), 𝐿1 normalization yields a clear anti-diagonal alignment of VLE embeddings and significantly reduces the average query cost (e.g., from 522.28 to 284.6) on the
key(𝑣) = 𝛼 ∥𝑜𝑙 (𝑣)∥ 2 + 𝛽 ∥𝑜𝑠 (𝑣)∥ 2,
(10)
where the first term defines a label-dependent base offset in the key space, and the second term introduces a fine-grained ordering 7
Figure 8: An illustration of our iLabel index design. Figure 9: An illustration of our auxiliary synopsis design. among vertices sharing the same label. This mapping projects highdimensional monotonic embeddings into a one-dimensional space while preserving their relative dominance order. We next show that this key mapping is sound for dominancebased pruning, i.e., dominance in the embedding space implies a consistent ordering in the key space.
Consider two adjacent labels 𝑙𝑖 and 𝑙𝑖+1 in ascending order of ∥𝑜𝑙 (𝑙)∥ 2 . The maximum key value in cluster 𝐶𝑙𝑖 is at most 𝛼 ∥𝑜𝑙 (𝑙𝑖 ) ∥ 2 + 𝛽𝑀, while the minimum key value in cluster 𝐶𝑙𝑖+1 is at least 𝛼 ∥𝑜𝑙 (𝑙𝑖+1 ) ∥ 2 . If 𝛼 (∥𝑜𝑙 (𝑙𝑖+1 )∥ 2 −∥𝑜𝑙 (𝑙𝑖 )∥ 2 ) > 𝛽𝑀, or equivalently Eq. 11 holds, then the following condition can be satisfied: max 𝑘𝑒𝑦 (𝑣) < min 𝑘𝑒𝑦 (𝑣),
𝑣 ∈𝐶𝑙𝑖
Lemma 3. (Dominance Preservation under One-dimensional Key Mapping). Let 𝑣𝑖 and 𝑣 𝑗 be two data vertices with monotonic vertex embeddings 𝑜 (𝑣𝑖 ) and 𝑜 (𝑣 𝑗 ). If 𝑜 (𝑣𝑖 ) ⪯ 𝑜 (𝑣 𝑗 ) holds, then their corresponding keys satisfy key(𝑣𝑖 ) ≤ key(𝑣 𝑗 ).
𝑣 ∈𝐶𝑙𝑖+1
which implies that the two cluster key ranges are strictly nonoverlapping. Since this condition holds for every adjacent pair of labels, all label clusters in the index are strictly separated. □
Proof. By definition of dominance, 𝑜 (𝑣𝑖 ) ⪯ 𝑜 (𝑣 𝑗 ) implies 𝑜 (𝑣𝑖 ) [𝑘] ≤ 𝑜 (𝑣 𝑗 ) [𝑘] for all dimensions 𝑘. Since both 𝑜𝑙 (·) and 𝑜𝑠 (·) are nonnegative vectors by construction, their 𝐿2 norms are monotonic with respect to coordinate-wise dominance. Thus, ∥𝑜𝑙 (𝑣𝑖 )∥ 2 ≤ ∥𝑜𝑙 (𝑣 𝑗 )∥ 2 and ∥𝑜𝑠 (𝑣𝑖 ) ∥ 2 ≤ ∥𝑜𝑠 (𝑣 𝑗 )∥ 2 . Given 𝛼, 𝛽 ≥ 0, it follows that key(𝑣𝑖 ) = 𝛼 ∥𝑜𝑙 (𝑣𝑖 ) ∥ 2 + 𝛽 ∥𝑜𝑠 (𝑣𝑖 )∥ 2 ≤ 𝛼 ∥𝑜𝑙 (𝑣 𝑗 )∥ 2 + 𝛽 ∥𝑜𝑠 (𝑣 𝑗 )∥ 2 = key(𝑣 𝑗 ), which completes the proof. □ Strict Separation of Label Clusters in the Key Space. While Lemma 3 guarantees that dominance relations are preserved under the one-dimensional key mapping, efficient index traversal further benefits from a stronger property: key ranges of different label clusters should be strictly non-overlapping. Intuitively, choosing 𝛼 sufficiently larger than 𝛽 (i.e., 𝛼 ≫ 𝛽) ensures that label semantics dominate inter-cluster separation, while preserving structural discrimination within each cluster. We formalize this intuition by giving a sufficient condition under which label-cluster key ranges in the iLabel index are guaranteed to be strictly non-overlapping. Lemma 4. (Non-overlapping Condition for Label Clusters). Let 𝑀 = max𝑣𝑖 ∈𝑉 (𝐺 ) ∥𝑜𝑠 (𝑣𝑖 )∥ 2 be the maximum 𝐿2 norm of vertex structure embeddings (VSEs) over all data vertices, and let Δmin = min𝑖 (∥𝑜𝑙 (𝑙𝑖+1 ) ∥ 2 − ∥𝑜𝑙 (𝑙𝑖 )∥ 2 ) be the minimum difference between the 𝐿2 norms of vertex label embeddings (VLEs) of two adjacent labels, where labels are ordered by increasing ∥𝑜𝑙 (𝑙)∥ 2 . If the following holds: 𝛼 𝑀 > , (11) 𝛽 Δmin then the key ranges of any two distinct label clusters in the iLabel index are strictly non-overlapping.
In practice, the value of 𝑀 can be obtained by a single linear scan during offline index construction, as ∥𝑜𝑠 (𝑣𝑖 )∥ 2 is already computed for key generation. Similarly, Δmin can be computed after sorting label embeddings by their 𝐿2 norms. Thus, the condition in Eq. 11 can be efficiently verified and enforced in the offline phase. Example 3. Figure 8 illustrates how iLabel organizes monotonic vertex embeddings via label-based clustering and one-dimensional key mapping. In this example, vertices have three labels, forming clusters 𝐶 33 , 𝐶 34 , and 𝐶 35 corresponding to labels 𝑙 33 , 𝑙 34 , and 𝑙 35 , respectively. Each cluster is anchored by its label embedding, serving as the cluster center, and vertices within a cluster share the same label embedding while differing in structural embeddings. Following Eq. 10, each vertex is mapped to a one-dimensional key 𝑘𝑒𝑦 (𝑣𝑖 ) = 𝛼 ∥𝑜𝑙 (𝑣𝑖 )∥ 2 + 𝛽 ∥𝑜𝑠 (𝑣𝑖 )∥ 2 with 𝛼 ≫ 𝛽. The first term determines the cluster offset, while the second induces a fine-grained ordering within the cluster. Consequently, key ranges of different clusters are strictly separated (e.g., max 𝐶 33 < min 𝐶 34 ), enabling range queries to be performed independently within each cluster. Meanwhile, variations in the structural component 𝛽 ∥𝑜𝑠 (𝑣𝑖 ) ∥ 2 order vertices within the same cluster, enabling efficient enumeration of candidates that satisfy dominance-based filtering.
4.2
Index Construction
Based on the iLabel key mapping in Section 4.1, this subsection describes how the index is constructed and organized, and how auxiliary information is incorporated to improve pruning efficiency during traversal. The index structure is solely responsible for organizing vertex keys and supporting efficient range search, while all auxiliary synopses are precomputed offline and used only as lightweight pruning aids during online query processing. Index Construction. The construction of the iLabel index is performed entirely offline. After training the embedding model Emb(·) using the cost-driven objective in Section 3.2, we generate the monotonic vertex embedding 𝑜 (𝑣𝑖 ) for each data vertex 𝑣𝑖 ∈ 𝑉 (𝐺) and
Proof. For any data vertex 𝑣𝑖 ∈ 𝑉 (𝐺) with label 𝑙 = 𝐿(𝑣𝑖 ), since ∥𝑜𝑠 (𝑣𝑖 ) ∥ 2 ∈ [0, 𝑀], its key value satisfies: 𝑘𝑒𝑦 (𝑣𝑖 ) = 𝛼 ∥𝑜𝑙 (𝑙) ∥ 2 + 𝛽 ∥𝑜𝑠 (𝑣𝑖 )∥ 2 ∈ 𝛼 ∥𝑜𝑙 (𝑙)∥ 2, 𝛼 ∥𝑜𝑙 (𝑙)∥ 2 + 𝛽𝑀 . Thus, the key range of the label cluster corresponding to 𝑙 is bounded by the above interval. 8
(3) are combined, yielding a single VSE (1.71, 1.29) and 𝑣 1 .MBR𝑑𝑒𝑔 = ([1.71, 1.71]; [1.29, 1.29]). These synopses compactly bound the structural embeddings of all degree-𝛿 (∈ [1, 3]) 1-hop substructures of 𝑣 1 . By precomputing them offline, LIVE avoids explicit substructure enumeration while enabling effective degree-aware pruning in online matching.
map it to a one-dimensional key using Eq. 10. A B+ -tree index I is then built over these keys to support efficient range-based access. The iLabel index follows a standard B+ -tree organization. Each leaf node stores data vertices together with their key values and vertex identifiers, while non-leaf nodes maintain routing entries that record the key ranges of their child subtrees. Non-leaf nodes store only key ranges, with no aggregated embedding or structural information, enabling traversal solely via key comparisons and keeping the index lightweight and scalable. Auxiliary Synopses for Pruning. While key-based range search effectively narrows candidate retrieval, dominance-based filtering alone may still yield false positives. Thus, we precompute two types of auxiliary embedding synopses for each data vertex; these synopses are lightweight geometric summaries that enable early pruning during index traversal without introducing false dismissals. Hop-based Embedding Synopsis. We construct a Minimum Bound-
Complexity Analysis. We provide the time and space complexity of constructing the iLabel index together with its auxiliary synopses as follows. Time. Given a data graph 𝐺, for each vertex 𝑣𝑖 ∈ 𝑉 (𝐺), computing its monotonic embedding 𝑜 (𝑣𝑖 ) = 𝛼𝑜𝑙 (𝑣𝑖 ) + 𝛽𝑜𝑠 (𝑣𝑖 ) requires aggregating the label embeddings of its 1-hop neighbors. This incurs 𝑂 (𝑑 · 𝑑𝑒𝑔(𝑣𝑖 )) time per vertex, where 𝑑 is the embedding dimenÍ sion. Since 𝑣𝑖 ∈𝑉 (𝐺 ) 𝑑𝑒𝑔(𝑣𝑖 ) = 2|𝐸 (𝐺)|, the total cost of embedding generation is 𝑂 (𝑑 · |𝐸 (𝐺)|). For hop-based synopses, we compute 𝑡-hop neighborhoods using BFS expansion. For each hop level, all vertices and edges are visited at most once. Thus, constructing hop-based MBRs for all vertices takes 𝑂 (𝑡 · (|𝑉 (𝐺)| + |𝐸 (𝐺)|)) time, where 𝑡 is a small constant. To computer degree-based synopses, for each vertex 𝑣𝑖 , we sort the label embeddings of its 1-hop neighbors once per embedding dimension. This yields a per-vertex cost of 𝑂 (𝑑 ·𝑑𝑒𝑔(𝑣𝑖 ) log 𝑑𝑒𝑔(𝑣𝑖 )). Í Summing over all vertices, the total time complexity is 𝑂 ( 𝑣𝑖 ∈𝑉 (𝐺 ) 𝑑· 𝑑𝑒𝑔(𝑣𝑖 ) log 𝑑𝑒𝑔(𝑣𝑖 )). After computing all key values, data vertices are sorted by 𝑘𝑒𝑦 (𝑣𝑖 ), which takes 𝑂 (|𝑉 (𝐺)| log |𝑉 (𝐺)|) time. Using bulk loading, B+ -tree can be constructed in linear time with respect to the number of sorted records, i.e., 𝑂 (|𝑉 (𝐺)|). Combining all steps, the overall time complexity of iLabel index Í construction is: 𝑂 (𝑑 · |𝐸 (𝐺)| + 𝑡 · (|𝑉 (𝐺)| + |𝐸 (𝐺)|) + 𝑣𝑖 ∈𝑉 (𝐺 ) 𝑑· 𝑑𝑒𝑔(𝑣𝑖 ) log 𝑑𝑒𝑔(𝑣𝑖 ) + |𝑉 (𝐺)| log |𝑉 (𝐺)|), which is near-linear in the graph size and small 𝑡. Space. Given a data graph 𝐺 and embedding dimension 𝑑, each data vertex 𝑣𝑖 stores its 𝑑-dimensional monotonic embedding 𝑜 (𝑣𝑖 ) and two types of auxiliary synopses. Storing vertex embeddings for all vertices requires 𝑂 (|𝑉 (𝐺)| · 𝑑) space. For hop-based embedding synopses, each vertex 𝑣𝑖 maintains 𝑡 (𝑡 ) hop-based MBRs 𝑣𝑖 .𝑀𝐵𝑅ℎ𝑜𝑝 , each consisting of two 𝑑-dimensional boundary vectors. The total space for hop-based synopses is therefore 𝑂 (|𝑉 (𝐺)| · 𝑡 · 𝑑). For degree-based embedding synopses, each vertex 𝑣𝑖 stores one (𝛿 ) degree-based MBR 𝑣𝑖 .𝑀𝐵𝑅𝑑𝑒𝑔 for each possible substructure degree 𝛿 ≤ 𝑑𝑒𝑔(𝑣𝑖 ). Each MBR consists of two 𝑑-dimensional vectors, resulting in 𝑂 (𝑑·𝑑𝑒𝑔(𝑣𝑖 )) space per vertex. Summed over all vertices, the total space requirement is 𝑂 (𝑑 · |𝐸 (𝐺)|). The B+ -tree stores only one-dimensional keys and pointers. Both leaf and non-leaf nodes require 𝑂 (|𝑉 (𝐺)|) space in total, which is negligible compared to embedding and synopsis storage. Overall, the space complexity of the iLabel index is 𝑂 (|𝑉 (𝐺)| ·𝑑 ·𝑡 +𝑑 · |𝐸 (𝐺)|), which scales linearly with the graph size and embedding dimension, and is suitable for large graphs.
(𝑡 ) ing Rectangle (MBR)–based embedding synopsis 𝑣𝑖 .MBRℎ𝑜𝑝 for each vertex 𝑣𝑖 and hop level 𝑡 (𝑡 ≥ 1), to capture higher-order neighborhood semantics. For the 𝑡-hop subgraph 𝑔𝑡 (𝑣𝑖 ) centered at 𝑣𝑖 , we compute per-dimension lower and upper bounds over the vertex label embeddings of all neighbor vertices of 𝑣𝑖 within 𝑔𝑡 (𝑣𝑖 ): (𝑡 ) 𝑣𝑖 .MBRℎ𝑜𝑝 [2𝑘] = (𝑡 ) [2𝑘 + 1] = 𝑣𝑖 .MBRℎ𝑜𝑝
min
𝑜𝑙 (𝑣 𝑗 ) [𝑘],
max
𝑜𝑙 (𝑣 𝑗 ) [𝑘],
𝑣 𝑗 ∈𝑉 (𝑔𝑡 (𝑣𝑖 ) )
(12)
𝑣 𝑗 ∈𝑉 (𝑔𝑡 (𝑣𝑖 ) )
for 𝑘 ∈ [0, 𝑑). The resulting 2𝑑-dimensional vector bounds the 𝑡-hop neighborhood embeddings, enabling pruning based on multi-hop semantic inconsistency without explicit neighborhood traversal. Degree-based Embedding Synopsis. We also construct a degree(𝛿 ) based embedding synopsis 𝑣𝑖 .MBR𝑑𝑒𝑔 to summarize degree-𝛿 neighbor combinations within the 1-hop neighborhood of a vertex 𝑣𝑖 . Specifically, given the 1-hop neighbors N1 (𝑣𝑖 ) of the vertex 𝑣𝑖 , we maintain sorted lists of their label embedding values, denoted by 𝑣𝑖 .vle_list𝑘 , for each embedding dimension 𝑘 ∈ [0, 𝑑). For a specified substructure degree 𝛿, the synopsis records lower and upper bounds on the aggregated structural embeddings of all possible 𝛿-neighbor combinations: (𝛿 ) 𝑣𝑖 .MBR𝑑𝑒𝑔 [2𝑘] =
𝛿 ∑︁
𝑣𝑖 .vle_list𝑘 [𝑟 ],
𝑟 =1 (𝛿 ) 𝑣𝑖 .MBR𝑑𝑒𝑔 [2𝑘 + 1] =
deg(𝑣 ∑︁𝑖 )
(13) 𝑣𝑖 .vle_list𝑘 [𝑟 ],
𝑟 =deg(𝑣𝑖 ) −𝛿+1
for 𝑘 ∈ [0, 𝑑). This bounds the structural embeddings of all degree-𝛿 1-hop substructures, avoiding explicit enumeration of substructures whose number grows exponentially with vertex degree. Example 4. Figure 9 illustrates the construction of the degreebased embedding synopsis for a vertex 𝑣 1 with three 1-hop neighbors {𝑣 2, 𝑣 3, 𝑣 4 }, where different neighbor combinations induce different 1-hop substructures. For degree 𝛿 = 1, the three possible substructures yield VSEs (0.78, 0.22), (0.56, 0.44), and (0.37, 0.63), resulting in (1) 𝑣 1 .MBR𝑑𝑒𝑔 = ( [0.37, 0.78]; [0.22, 0.63]). For 𝛿 = 2, the three neighbor pairs produce VSEs (1.34, 0.66), (1.15, 0.85), and (0.93, 1.07), giving (2) 𝑣 1 .MBR𝑑𝑒𝑔 = ( [0.93, 1.34]; [0.66, 1.07]). When 𝛿 = 3, all neighbors 9
5
and key intervals of different labels are disjoint. Hence, any data vertex with 𝑘𝑒𝑦(𝑣𝑖 ) ≥ 𝑘𝑒𝑦(𝐿(𝑞𝑖 ) + 1) belongs to a different label cluster and cannot match 𝑞𝑖 . Similarly, if 𝑁𝑖 . min ≥ 𝑘𝑒𝑦(𝐿(𝑞𝑖 ) + 1), then all vertices in the sub-tree rooted at 𝑁𝑖 fall outside the label-consistent key range of 𝑞𝑖 . Pruning under these conditions preserves all valid candidates and introduces no false dismissals. □
SUBGRAPH MATCHING WITH MONOTONIC VERTEX EMBEDDING
This section presents the online subgraph matching algorithm built on the learned monotonic vertex embeddings and the iLabel index. Given a query graph, the online phase efficiently retrieves candidate vertices for each query vertex without false dismissals and assembles valid matches through refinement. We introduce low-cost pruning strategies for index traversal and candidate retrieval in Section 5.1, and then present the integrated online subgraph matching algorithm in Section 5.2.
5.1
Embedding Dominance Pruning (Strategy 3). Within the queryspecific key range, we scan data vertices and apply a dominance check against the query embedding. Any vertex whose embedding are not dominated by the query embedding cannot satisfy 1-hop containment and is safely pruned.
Pruning Strategies
During online query processing, candidates for each query vertex are retrieved by traversing the iLabel index and scanning data vertices within a query-specific key range. To efficiently eliminate invalid candidates without sacrificing correctness, we apply the following pruning strategies to progressively refine the candidate set. These strategies are derived from necessary conditions under monotonic embeddings and therefore introduce no false dismissals. Key Lower-Bound Pruning (Strategy 1). For a query vertex 𝑞𝑖 , we first derive a query-specific lower bound 𝑘𝑒𝑦(𝑞𝑖 ) from the B+ -tree in the iLabel index. Due to the consistency between embedding dominance and key ordering, any data vertex with a key value smaller than 𝑘𝑒𝑦 (𝑞𝑖 ) cannot be dominated by 𝑜 (𝑞𝑖 ) and therefore cannot be a valid candidate. Such vertices, along with their corresponding index entries, can be safely pruned.
Lemma 7. (Embedding Dominance Pruning). Given a query vertex 𝑞𝑖 and a data vertex 𝑣𝑖 , if their monotonic vertex embeddings satisfy 𝑜 (𝑞𝑖 ) ⪯̸ 𝑜 (𝑣𝑖 ) (i.e., 𝑜 (𝑣𝑖 ) is not dominated by 𝑜 (𝑞𝑖 )), then 𝑣𝑖 cannot be a valid candidate for 𝑞𝑖 and can be safely pruned. Proof. A data vertex 𝑣𝑖 matches 𝑞𝑖 only if the 1-hop subgraph 𝑔1 (𝑞𝑖 ) is a substructure of 𝑔1 (𝑣𝑖 ). Under the monotonic vertex embedding design (Section 3.2), this subgraph containment relationship implies 𝑜 (𝑞𝑖 ) ⪯ 𝑜 (𝑣𝑖 ) in the embedding space. If 𝑜 (𝑞𝑖 ) ⪯̸ 𝑜 (𝑣𝑖 ) holds, then the necessary dominance condition is violated, and 𝑣𝑖 cannot satisfy the required subgraph relationship. Therefore, pruning 𝑣𝑖 does not introduce false dismissals. □ Hop-based Synopsis Pruning (Strategy 4). Vertex-level dominance alone does not capture higher-order structural feasibility. To further prune false positives at low cost, we exploit hop-based embedding synopses that bound multi-hop neighborhoods in the embedding space. During candidate evaluation, we compare query and data synopses in a coarse-to-fine manner, starting from larger hop distances and terminating early upon detecting a violation.
Lemma 5. (Key Lower-Bound Pruning). Given a query vertex 𝑞𝑖 ∈ 𝑞 with 𝑘𝑒𝑦 (𝑞𝑖 ), for any data vertex 𝑣𝑖 ∈ 𝐺 with 𝑘𝑒𝑦 (𝑣𝑖 ) or index entry 𝑁𝑖 ∈ I with key range [𝑁𝑖 .𝑚𝑖𝑛, 𝑁𝑖 .𝑚𝑎𝑥), if 𝑘𝑒𝑦(𝑣𝑖 ) < 𝑘𝑒𝑦(𝑞𝑖 ) or 𝑁𝑖 .𝑚𝑎𝑥 < 𝑘𝑒𝑦 (𝑞𝑖 ) holds, then 𝑣𝑖 or the entire subtree rooted at 𝑁𝑖 can be safely pruned. Proof. By the construction of the key mapping (Eq. 10), key ordering is consistent with the dominance ordering of vertex embeddings. If 𝑘𝑒𝑦 (𝑣𝑖 ) < 𝑘𝑒𝑦(𝑞𝑖 ), then 𝑜 (𝑞𝑖 ) ⪯̸ 𝑜 (𝑣𝑖 ), implying that 𝑣𝑖 cannot be dominated by 𝑜 (𝑞𝑖 ) and thus cannot be a valid candidate. Similarly, if 𝑁𝑖 . max < 𝑘𝑒𝑦 (𝑞𝑖 ), then all data vertices in the subtree rooted at 𝑁𝑖 have keys smaller than 𝑘𝑒𝑦(𝑞𝑖 ) and therefore cannot be dominated by 𝑜 (𝑞𝑖 ). Pruning under these conditions preserves all valid candidates and introduces no false dismissals. □
Lemma 8. (Hop-based Synopsis Pruning). Given a query vertex (𝑡 ) (𝑡 ) 𝑞𝑖 and a data vertex 𝑣𝑖 , let 𝑞𝑖 .𝑀𝐵𝑅ℎ𝑜𝑝 and 𝑣𝑖 .𝑀𝐵𝑅ℎ𝑜𝑝 denote their hop-based embedding synopses at hop distance 𝑡. If there exists 𝑡 ∈ (𝑡 ) (𝑡 ) {2, . . . , 𝑘 } such that 𝑞𝑖 .𝑀𝐵𝑅ℎ𝑜𝑝 ⊈ 𝑣𝑖 .𝑀𝐵𝑅ℎ𝑜𝑝 , then 𝑣𝑖 cannot be a valid candidate for 𝑞𝑖 and can be safely pruned. (𝑡 ) Proof. The synopsis 𝑣𝑖 .MBRℎ𝑜𝑝 bounds the embeddings of all vertices in the 𝑡-hop neighborhood of 𝑣𝑖 . If 𝑣𝑖 were a valid candidate for 𝑞𝑖 , the 𝑡-hop neighborhood of 𝑞𝑖 would have to be realizable within that of 𝑣𝑖 , which under monotonic embeddings requires (𝑡 ) (𝑡 ) 𝑞𝑖 .MBRℎ𝑜𝑝 ⊆ 𝑣𝑖 .MBRℎ𝑜𝑝 . Violation of this condition for any 𝑡 implies infeasibility. Thus, 𝑣𝑖 can be safely pruned. □
Key Upper-Bound Pruning (Strategy 2). After determining the lower bound of the query range, we further restrict candidate retrieval to a label-consistent key interval. Since key ranges of different label clusters are strictly disjoint, any data vertex with a key no smaller than the key of the next label (i.e., 𝑘𝑒𝑦 (𝐿(𝑞𝑖 ) + 1)) belongs to a different label cluster and cannot match the query vertex. Such vertices and index entries can therefore be safely pruned. Lemma 6. (Key Upper-Bound Pruning). Given a query vertex 𝑞𝑖 ∈ 𝑞 with label 𝐿(𝑞𝑖 ), for any data vertex 𝑣𝑖 ∈ 𝐺 with key 𝑘𝑒𝑦(𝑣𝑖 ) or index entry 𝑁𝑖 ∈ I with key range [𝑁𝑖 .𝑚𝑖𝑛, 𝑁𝑖 .𝑚𝑎𝑥), if 𝑘𝑒𝑦(𝑣𝑖 ) ≥ 𝑘𝑒𝑦 (𝐿(𝑞𝑖 ) + 1) or 𝑁𝑖 .𝑚𝑖𝑛 ≥ 𝑘𝑒𝑦 (𝐿(𝑞𝑖 ) + 1) holds, then 𝑣𝑖 or the entire subtree rooted at 𝑁𝑖 can be safely pruned.
Degree-based Synopsis Pruning (Strategy 5). For high-degree data vertices, explicitly enumerating 1-hop substructures is prohibitive. Instead, we leverage degree-based embedding synopses (Section 4.2) that bound the structural embeddings of all 1-hop substructures of a given degree. A necessary condition for matching a query vertex to a data vertex is that the query’s structural embedding lies within the corresponding degree-based bounding region; otherwise, the data vertex can be safely pruned.
Proof. By the iLabel key construction, all vertices with label 𝐿(𝑞𝑖 ) are indexed within the interval [𝑘𝑒𝑦 (𝐿(𝑞𝑖 )), 𝑘𝑒𝑦 (𝐿(𝑞𝑖 ) + 1)),
Lemma 9. (Degree-based Synopsis Pruning). Given a query vertex 𝑞𝑖 and a data vertex 𝑣𝑖 , let 𝑞𝑖 .𝑣𝑠𝑒 denote the vertex structure 10
the trained embedding model Emb(·) and computes the hop-based synopsis 𝑞𝑖 .𝑀𝐵𝑅ℎ𝑜𝑝 with the embeddings of its hop-based neighbors (lines 1–3). To retrieve candidate data vertices, a key-range search is performed on the iLabel index I. In particular, starting from the root, the algorithm descends to the first leaf node whose key range intersects the query interval [𝑘𝑒𝑦 (𝑞𝑖 ), 𝑘𝑒𝑦 (𝐿(𝑞𝑖 ) + 1)), leveraging key lower- and upper-bound pruning to skip irrelevant subtrees (lines 4–9; Lemmas 5 and 6). When reaching the leaf level, it performs a sequential scan over leaf nodes within the query range using the linked-leaf structure and terminates once the upper bound is exceeded (lines 10–13). For each encountered data vertex, a cascade of pruning strategies is applied, including embedding dominance pruning (line 14; Lemma 7), hop-based synopsis pruning (line 15; Lemma 8), and degree-based synopsis pruning (lines 16–17; Lemma 9). Vertices that pass all pruning checks are added to the candidate set 𝑞𝑖 .cand_set (line 17). Matching Order Generation (Stage 2). After constructing candidate sets for all query vertices, the algorithm determines a matching order 𝑄 to guide the refinement phase (line 19). To minimize intermediate join results, it selects the query vertex from 𝑞 with the smallest candidate set as the starting point and then iteratively appends adjacent query vertices with the smallest candidate sets until all vertices are ordered. Refinement (Stage 3). Then, a backtracking-based refinement procedure [28, 47, 63] is applied to enumerate valid matches using the candidate sets and the matching order (line 20). During refinement, partial mappings are incrementally extended while enforcing injective mapping constraints and edge-consistency conditions between the query graph 𝑞 and the data graph 𝐺; and all complete mappings that satisfy the query are added into the result set S. Finally, the algorithm returns S as the final output (line 21). Complexity Analysis. For each query vertex 𝑞𝑖 ∈ 𝑉 (𝑞), generating its monotonic vertex embedding requires aggregating embeddings of its 1-hop neighbors, which costs 𝑂 (𝑑𝑒𝑔(𝑞𝑖 ) · 𝑑) time (line 2), where 𝑑 is the embedding dimension. Computing the hopbased synopsis 𝑞𝑖 .𝑀𝐵𝑅ℎ𝑜𝑝 involves performing BFS expansions on the query graph up to 𝑘 hops while maintaining per-dimension minimum and maximum values. This costs 𝑂 (|𝐸 (𝑞)| + 𝑘 · |𝑉 (𝑞)| · 𝑑) per query vertex (line 3). Since query graphs are typically small, this cost is negligible compared to index traversal and refinement. For each query vertex, descending the B+ -tree from the root to the first relevant leaf node incurs 𝑂 (ℎ) time, where ℎ is the height of the index (lines 4–9). Let 𝑅𝑖 denote the number of data vertices whose keys fall within the query-specific range [𝑘𝑒𝑦(𝑞𝑖 ), 𝑘𝑒𝑦 (𝐿(𝑞𝑖 )+ 1)). During the sequential leaf scan, each such vertex is examined once. For each data vertex, embedding dominance pruning costs 𝑂 (𝑑) (line 14), hop-based synopsis pruning costs 𝑂 ((𝑘 − 1) · 𝑑) (line 15), and degree-based synopsis pruning costs 𝑂 (𝑑) (lines 16– 17). Thus, the total pruning cost per query vertex is 𝑂 (𝑅𝑖 · 𝑘 · 𝑑) (lines 10–18). After candidate sets are constructed, the greedy matching order generation procedure selects query vertices based on candidate set sizes. In the worst case, this procedure takes 𝑂 (|𝑉 (𝑞)| 2 ) time (line 19). Finally, the refinement phase performs a backtracking-based exact subgraph matching guided by the matching order and candidate
Algorithm 2: Exact Subgraph Matching with Learnable Monotonic Vertex Embedding Input: a query graph 𝑞 , a data graph 𝐺 , a trained embedding model Emb (·) , and an iLabel index I Output: a set S of matching subgraphs in 𝐺 // Candidate retrieval for each query vertex 1 for each query vertex 𝑞𝑖 ∈ 𝑉 (𝑞) do 2 generate query vertex embedding 𝑜 (𝑞𝑖 ) using Emb (·) ; 3 compute hop-based synopsis 𝑞𝑖 .𝑀𝐵𝑅ℎ𝑜𝑝 of 𝑞𝑖 ; // Locate the first relevant leaf node 4 𝑁 ← I.𝑟𝑜𝑜𝑡 ; 5 while 𝑁 is not a leaf node do 6 for each entry 𝑁 𝑗 ∈ 𝑁 do 7 if [𝑁 𝑗 .𝑚𝑖𝑛, 𝑁 𝑗 .𝑚𝑎𝑥 ) ∩ [𝑘𝑒𝑦 (𝑞𝑖 ), 𝑘𝑒𝑦 (𝐿 (𝑞𝑖 ) + 1) ) ≠ ∅ then // Lemmas 5 and 6 8 𝑁 ← 𝑁𝑗 ; 9 break;
10 11 12
13 14
// Sequential leaf scan within the query range while 𝑁 is not null do for each data vertex 𝑣𝑖 ∈ 𝑁 do if 𝑘𝑒𝑦 (𝑣𝑖 ) ≥ 𝑘𝑒𝑦 (𝐿 (𝑞𝑖 ) + 1) then // Lemma 6 break; if 𝑜 (𝑞𝑖 ) ⪯ 𝑜 (𝑣𝑖 ) then // Lemma 7 (𝑡 )
15
(𝑡 )
if 𝑞𝑖 .𝑀𝐵𝑅ℎ𝑜𝑝 ⊆ 𝑣𝑖 .𝑀𝐵𝑅ℎ𝑜𝑝 for all 𝑡 ∈ [2, 𝑘 ] then // Lemma 8 (𝑑𝑒𝑔 (𝑞 ) )
16
17
18
if 𝑞𝑖 .𝑣𝑠𝑒 ∈ 𝑣𝑖 .𝑀𝐵𝑅𝑑𝑒𝑔 𝑖 // Lemma 9 𝑞𝑖 .𝑐𝑎𝑛𝑑 _𝑠𝑒𝑡 .𝑎𝑑𝑑 (𝑣𝑖 ) ;
then
𝑁 ← 𝑁 .𝑛𝑒𝑥𝑡 ;
// Matching order generation generate an ordered list 𝑄 of query vertices 𝑞𝑖 ∈ 𝑞 based on candidate set sizes |𝑞𝑖 .𝑐𝑎𝑛𝑑 _𝑠𝑒𝑡 | ; // Candidate refinement 20 invoke a backtracking search procedure to enumerate valid matches in 𝐺 and add them to S ; 21 return S ;
19
(𝑑𝑒𝑔 (𝑞 ) )
embedding of 𝑞𝑖 . If 𝑞𝑖 .𝑣𝑠𝑒 ∉ 𝑣𝑖 .𝑀𝐵𝑅𝑑𝑒𝑔 𝑖 , then 𝑣𝑖 cannot be a valid candidate for matching 𝑞𝑖 and can be safely pruned. Proof. If 𝑣𝑖 is a valid candidate for 𝑞𝑖 , then the 1-hop subgraph 𝑔1 (𝑞𝑖 ) must correspond to one of the 1-hop substructures of 𝑣𝑖 with (𝛿 ) degree 𝑑𝑒𝑔(𝑞𝑖 ). By construction, 𝑣𝑖 .𝑀𝐵𝑅𝑑𝑒𝑔 bounds the structural embeddings of all such substructures with degree 𝛿. (𝑑𝑒𝑔 (𝑞 ) ) Hence, 𝑞𝑖 .𝑣𝑠𝑒 must lie within 𝑣𝑖 .𝑀𝐵𝑅𝑑𝑒𝑔 𝑖 . If this condition is violated, no feasible 1-hop substructure of 𝑣𝑖 can match 𝑔1 (𝑞𝑖 ). Pruning 𝑣𝑖 under this condition introduces no false dismissals. □
5.2
Online Subgraph Matching Algorithm
Algorithm 2 presents the complete online subgraph matching procedure based on monotonic vertex embeddings and the iLabel index I. It consists of three stages: candidate retrieval with index traversal and pruning (lines 1–18), matching order determination (line 19), and candidate refinement (line 20). Candidate Retrieval (Stage 1). For each query vertex 𝑞𝑖 ∈ 𝑉 (𝑞), the algorithm first computes its monotonic embedding 𝑜 (𝑞𝑖 ) using 11
Table 2: Parameter settings. Parameters
Values
the dimension, 𝑑 , of the vertex embedding vector the weight ratio, 𝛼/𝛽 the number, 𝑡 , of synopsis hops the size, |𝑉 (𝑞) | , of the query graph 𝑞 the average degree, 𝑎𝑣𝑔_𝑑𝑒𝑔 (𝑞) , of the query graph 𝑞 the number, |Σ| , of distinct labels the average degree, 𝑎𝑣𝑔_𝑑𝑒𝑔 (𝐺 ) , of the data graph 𝐺 the size, |𝑉 (𝐺 ) | , of the data graph 𝐺
2, 3, 4, 5 1K, 10K, 100K, 1M 1, 2, 3, 4 5, 6, 8, 10, 12 2, 3, 4 5, 10, 15, 20, 25 3, 4, 5, 6, 7 10K, 30K, 50K, 80K, 100K, 500K, 1M, 5M, 10M
Table 3: Statistics of real-world graph data sets. Data Sets
|𝑉 (𝐺 ) |
|𝐸 (𝐺 ) |
|Σ|
𝑎𝑣𝑔_𝑑𝑒𝑔 (𝐺 )
Yeast (ye) HPRD (hp) DBLP (db) Youtube (yt) US Patents (up)
3,112 9,460 317,080 1,134,890 3,774,768
12,519 34,998 1,049,866 2,987,624 16,518,947
71 307 15 25 20
8.0 7.4 6.6 5.3 8.8
sets (line 20). In the worst case, it enumerates all combinations of Î candidates, yielding 𝑂 ( 𝑞𝑖 ∈𝑉 (𝑞) |𝑞𝑖 .𝑐𝑎𝑛𝑑_𝑠𝑒𝑡 |) time. Therefore, the overall time complexity of Algorithm 2 is 𝑂 ( Í (𝑑𝑒𝑔(𝑞𝑖 ) ·𝑑 + |𝐸 (𝑞)| +𝑘 · |𝑉 (𝑞)| ·𝑑 +ℎ +𝑅𝑖 ·𝑘 ·𝑑) + |𝑉 (𝑞)| 2 + 𝑞 Î 𝑖 ∈𝑉 (𝑞) 𝑞𝑖 ∈𝑉 (𝑞) |𝑞𝑖 .𝑐𝑎𝑛𝑑_𝑠𝑒𝑡 |).
6
EXPERIMENTAL EVALUATION
To evaluate the effectiveness and efficiency of LIVE, we conducted extensive experiments on synthetic/real-world graph datasets.
6.1
Experiment Settings
All experiments were performed on an Ubuntu server equipped with an Intel Core i9-12900K CPU, 128GB memory, and an NVIDIA GeForce RTX 4090 GPU. Offline embedding optimization and model training were implemented in PyTorch, while the online exact subgraph matching components, including index traversal, pruning, and refinement, were implemented in C++. We used the Adam optimizer with a learning rate of 𝜂 = 0.01 for embedding training. To balance GPU memory usage and training cost, we fixed the number of sampled vertex pairs to 𝐾 = 4,096 and trained for 1,000 epochs across all datasets. The source code and all tested datasets are available at https://github.com/JamesWhiteSnow/LIVE. Baseline Methods. We compared LIVE with eleven representative exact subgraph matching methods, including both classical rulebased approaches and recent learning-based solutions: GraphQL (GQL) [24], QuickSI (QSI) [47], RI [10], CFLMatch (CFL) [9], VF2++ (VF) [27], DP-iso (DP) [22], CECI [8], Hybrid [49] (a hybrid of GQL, RI, and QSI), RapidMatch (RM) [50], GNN-PE [62], and BSX [39]. These baselines collectively represent the state of the art in exact subgraph matching with different indexing, pruning, and learning strategies, providing a comprehensive comparison against LIVE. Graph Datasets. We evaluated LIVE on both synthetic and realworld graph datasets, following widely adopted experimental settings as in prior works [26, 49, 50, 62, 63]. Synthetic Graphs. Following [39, 49, 62], we generated synthetic graphs using the Newman–Watts–Strogatz model [56] via the NetworkX package [21]. For each vertex 𝑣𝑖 , its label 𝐿(𝑣𝑖 ) was randomly
assigned from the range [1, |Σ|] following one of three distributions: Uniform, Gaussian, or Zipf. Accordingly, we constructed three types of synthetic graphs, denoted as syn-uni, syn-gau, and syn-zipf. Detailed parameter settings are summarized in Table 2. Real-world Graphs. We further evaluated LIVE on five real-world graph datasets that have been widely used in prior subgraph matching studies [8, 9, 22–24, 45, 47, 49, 51, 66]. The statistics of these datasets are reported in Table 3. Query Graphs. For each data graph 𝐺, we generated 100 connected query graphs following standard practices [5, 8, 9, 22, 23, 30, 45, 51]. Each query graph 𝑞 was obtained by performing a random walk on 𝐺 until |𝑉 (𝑞)| vertices were collected. If the induced subgraph exceeded the target average degree 𝑎𝑣𝑔_𝑑𝑒𝑔(𝑞), edges were randomly removed to match the desired density; otherwise, the sampling process was restarted. Detailed query parameters are listed in Table 2. Evaluation Metrics. Following [39, 49, 50, 62], we evaluated both efficiency and effectiveness of LIVE and all baselines. Efficiency was measured by the wall-clock query processing time, including both filtering and refinement phases. Effectiveness was evaluated in terms of pruning power, defined as the percentage of data vertices eliminated during candidate retrieval by the proposed pruning strategies (Section 5.1). Unless otherwise stated, all reported results were averaged over 100 query graphs. In addition, we reported the offline pre-computation costs of LIVE, including embedding model training time, iLabel index construction time, and iLabel index storage overhead, to demonstrate the practicality of the proposed framework. Table 2 summarizes the default parameter settings used in our experiments, where default values are highlighted in bold. In subsequent experiments, we vary one parameter at a time while keeping all others fixed at their default values.
6.2
Parameter Tuning
In this subsection, we studied the impact of key parameters in LIVE on query efficiency using synthetic datasets, varying one parameter at a time while holding the others at their default values. Impact of Vertex Embedding Dimension 𝒅. Figure 10(a) reports the query processing time of LIVE as the embedding dimension 𝑑 varied from 1 to 4. As shown there, increasing 𝑑 from 1 to 2 significantly reduces query time due to stronger pruning from more expressive embeddings , while further increases yield marginal benefits as pruning saturated and per-comparison cost grew linearly. This indicates that low-dimensional monotonic vertex embeddings (e.g., 𝑑 = 2) can support efficient subgraph matching on widely tested datasets. Nevertheless, LIVE maintains consistently low query latency across different values of 𝑑 (e.g., below 0.07𝑚𝑠 on syn-uni and syn-gau, and below 1.19𝑚𝑠 on syn-zipf ), demonstrating robustness to the embedding dimensionality. Impact of Weight Ratio 𝜶 /𝜷. Figure 10(b) evaluated the impact of the weight ratio 𝛼/𝛽 on query efficiency, where 𝛼 and 𝛽 control the relative contributions of vertex label embeddings (VLE) and vertex structure embeddings (VSE), respectively. As 𝛼/𝛽 increases from 103 to 105 , query time decreases and then stabilizes when 𝛼/𝛽 exceeds 105 . This behavior aligns with the design of iLabel: (i) a larger 𝛼/𝛽 enhances separation among label-based clusters in the key space, resulting in tighter query ranges and fewer vertices 12
(a) varying 𝑑
(b) varying 𝛼/𝛽
(c) varying 𝑡
Figure 10: LIVE efficiency w.r.t different parameters 𝒅, 𝜶 /𝜷, and 𝒕.
(a) real-world graphs
(b) synthetic graphs
Figure 11: LIVE pruning power.
(i) Initial embeddings (initial). Vertex embeddings are randomly initialized. While monotonicity guarantees correctness, pruning power is limited (e.g., only up to 66.32% of data vertices are eliminated). (ii) Lightweight optimizations (L1 norm and ratio). These apply non-learning-based optimizations, including 𝐿1 normalization of vertex label embeddings and tuning the weight ratio 𝛼/𝛽. Both reshape the embedding distribution: 𝐿1 normalization reduces dominance region size, while adjusting 𝛼/𝛽 strengthens label-based separation in the iLabel key space, yielding consistent but moderate gains (e.g., up to 76.49% and 79.73% pruning). (iii) Embedding learning (learning). Optimizing embeddings with the proposed antidominance loss significantly increases dispersion in the embedding space, resulting in much stronger pruning (e.g., up to 98.43%). (iv) Full LIVE pruning (LIVE). Combining embedding learning with all pruning strategies, i.e., key-based, dominance-based, hop-based, and degree-based pruning, further eliminates false positives and achieves high pruning power, up to 99.18%, removing over 99% of data vertices before refinement. These results confirm the effectiveness of LIVE’s embedding design and pruning strategies. More importantly, they highlight a clear separation between correctness guarantees and pruning effectiveness. While monotonicity alone ensures no false dismissals (even with randomly initialized embeddings), strong pruning power is achieved only when vertex embeddings are explicitly optimized to reduce dominance. This empirical evidence shows that dominance correctness by itself does not imply efficient filtering, and validates the core design of LIVE: decoupling correctness guarantees from pruning-oriented embedding optimization.
(b) synthetic graphs
Figure 12: LIVE efficiency on synthetic/real-world graphs.
examined during index traversal; and (ii) an effective 𝛼/𝛽 can be achieved with a relatively small value (e.g., 105 ). Overall, LIVE maintains low query latency across a wide range of 𝛼/𝛽 values (ranging from 0.06𝑚𝑠 to 1.16𝑚𝑠). Impact of Synopsis Hop Parameter 𝒕. Figure 10(c) examined the effect of the hop parameter 𝑡 in the hop-based embedding synopsis, which controls the amount of multi-hop structural information used for pruning. As shown in the figure, query time first decreases as 𝑡 increases from 1 to 2, and then increases for larger values of 𝑡. This behavior is expected: while a larger 𝑡 enables stronger pruning by incorporating richer multi-hop information, the overhead of comparing higher-dimensional synopses eventually outweighs the additional pruning benefit. The resulting U-shaped trend reflects the trade-off between pruning effectiveness and comparison cost. Nevertheless, LIVE maintains low query latency across all settings, ranging from 0.06𝑚𝑠 to 1.18𝑚𝑠. Default Parameter Selection. Based on the above observations, we set 𝑑 = 2, 𝛼/𝛽 = 100K, and 𝑡 = 2 as the default parameters in the remaining experiments. These values strike a good balance between pruning effectiveness and computational overhead, and provide stable performance across different datasets and query workloads.
6.3
(a) real-world graphs
6.4
Evaluation of LIVE Efficiency
In this subsection, we evaluated the efficiency of LIVE in terms of wall-clock time, and compared it with state-of-the-art baseline methods on both real-world and synthetic graphs. Unless otherwise stated, all parameters are set to their default values. Efficiency of LIVE on Synthetic and Real-world Graphs. Figure 12 compared the time cost of LIVE with eleven baselines on both synthetic and real-world datasets. As shown, LIVE consistently outperforms all baselines across all datasets, achieving up to an order-of-magnitude speedup over the strongest competitors on large-scale real-world graphs such as yt and up. Notably, LIVE answers exact subgraph matching queries on the largest up, which contains 3.77𝑀 vertices, in only 6.53𝑚𝑠. These results demonstrate the high efficiency of LIVE and its strong scalability to large graphs.
Evaluation of LIVE Effectiveness
In this subsection, we evaluated the effectiveness of LIVE in terms of pruning power, measured as the percentage of data vertices safely eliminated during candidate retrieval. Pruning Power of LIVE on Real-world and Synthetic Graphs. Figure 11 evaluated the pruning power of LIVE under different embedding configurations and optimizations on both real-world and synthetic graphs, with all parameters set to their default values. 13
(a) varying |Σ|
(b) varying 𝑎𝑣𝑔_𝑑𝑒𝑔 (𝑞)
(c) varying |𝑉 (𝑞) |
(d) varying 𝑎𝑣𝑔_𝑑𝑒𝑔 (𝐺 )
(e) varying |𝑉 (𝐺 ) |
Figure 13: LIVE efficiency evaluation on synthetic graphs. To further evaluate the efficiency of LIVE, we varied key parameters (e.g., |Σ|, 𝑎𝑣𝑔_𝑑𝑒𝑔(𝑞), |𝑉 (𝑞)|, 𝑎𝑣𝑔_𝑑𝑒𝑔(𝐺), and |𝑉 (𝐺)|) on synthetic graphs in subsequent tests. To better illustrate performance trends, baseline results are omitted below. Efficiency of LIVE w.r.t. # of Distinct Vertex Labels, |𝚺|. Figure 13(a) shows the query time of LIVE as the number of distinct vertex labels |Σ| increases from 5 to 25. As |Σ| increases, label-based clustering in the iLabel index becomes more effective, leading to smaller query ranges and fewer candidate vertices, and thus lower query time. Although different label distributions introduce some variation in pruning behavior, LIVE consistently maintains low query latency across all settings, ranging from 0.03𝑚𝑠 to 2.82𝑚𝑠. Efficiency of LIVE w.r.t. Average Degree, 𝒂𝒗𝒈_𝒅𝒆𝒈(𝒒), of the Query Graph 𝒒. Figure 13(b) evaluated the impact of the query graph’s average degree on efficiency. As 𝑎𝑣𝑔_𝑑𝑒𝑔(𝑞) increases, query time first rises and then declines. This is because although higher query density enables stronger pruning due to tighter matching requirements, it introduces additional overhead in computing hop-based synopses and enforcing structural constraints. Nevertheless, query time remains low across all settings (0.06𝑚𝑠 ∼ 1.15𝑚𝑠). Efficiency of LIVE w.r.t. Query Graph Size |𝑽 (𝒒)|. Figure 13(c) reports query time as the query graph size increased from 5 to 12 vertices. Intuitively, larger queries involve more vertices and can increase index traversal and refinement costs, but they also yield richer hop-based synopses that strengthen pruning and reduce candidate sets. As a result, LIVE exhibits decreasing query time as |𝑉 (𝑞)| grows, indicating that stronger structural constraints effectively offset the additional processing overhead. Across all query sizes, query time remains low, ranging from 0.05𝑚𝑠 to 1.16𝑚𝑠. Efficiency of LIVE w.r.t. Average Degree, 𝒂𝒗𝒈_𝒅𝒆𝒈(𝑮), of the Data Graph 𝑮. Figure 13(d) evaluated LIVE under varying data graph densities, with 𝑎𝑣𝑔_𝑑𝑒𝑔(𝐺) from 3 to 7. As shown in the figure, query time increases only moderately as graph density grows, even on graphs with skewed label distributions, e.g., from 0.41𝑚𝑠 to 1.51𝑚𝑠 on syn-zipf. This trend arises because higher density weakens pruning effectiveness and enlarges candidate sets. LIVE mitigates this effect through degree-based synopsis pruning, which restricts structural checks to substructures whose degrees match those of query vertices. Overall, LIVE is efficient across all settings. Scalability of LIVE w.r.t. Data Graph Size |𝑽 (𝑮)|. Figure 13(e) evaluated the scalability of LIVE as the data graph size increased from 10𝐾 to 10𝑀 vertices. LIVE consistently achieves the lowest query time across all settings, e.g., it answers exact subgraph matching queries within 45.26𝑚𝑠 on graphs with 10𝑀 vertices.
(a) model training time (b) index building time
(c) index storage cost
Figure 14: The LIVE offline pre-computation cost.
This efficiency stems from the one-dimensional iLabel index design combined with effective pruning strategies, which tightly bound candidate exploration even as graph size grows. This indicates that LIVE scales well for exact subgraph matching on large-scale graphs.
6.5
Offline Pre-Computation Performance
In this subsection, we evaluated the offline pre-computation cost of LIVE, including embedding model training and index construction, and compared it with the representative learning-based baseline GNN-PE. Experiments were conducted on both real-world and synthetic graphs using default parameter settings. Offline Pre-Computation Cost on Real-world Graphs. Figures 14(a) and 14(b) compared the model training and index construction costs of LIVE and GNN-PE on real-world datasets. As shown in Figure 14(a), GNN-PE incurs 104 × higher training cost, which increases sharply with graph size due to exhaustive enumeration of 1-hop subgraphs and their substructures for learning dominance relations. In contrast, LIVE decouples dominance correctness from the learning objective and adopts a sampling-based anti-dominance loss with a fixed number of sampled vertex pairs, resulting in low and stable training cost across datasets, with only minor overhead from embedding computation. Figure 14(b) further shows that although index construction time increases with graph size for both methods, LIVE consistently achieves 82× lower cost by building a lightweight iLabel index over vertex embeddings, whereas GNN-PE relies on path-based structures that substantially inflate index size and construction overhead. These results demonstrate the superior cost performance of LIVE in both model training and index construction on large-scale graphs. More importantly, they highlight a fundamental limitation of dominance learning-based approach (e.g., GNN-PE): by tightly coupling correctness guarantees with the learning objective, such methods 14
inevitably incur prohibitively high training costs due to exhaustive subgraph–substructure enumeration. In contrast, LIVE attains the same no-false-dismissal guarantee through monotonic embedding construction and decouples correctness from embedding optimization. This structural decoupling enables lightweight, samplingbased training and avoids the offline cost bottleneck inherent in dominance learning-based frameworks. Index Construction Time and Space Costs of LIVE w.r.t. Data Graph Size |𝑉 (𝐺)|. Figure 14(c) further evaluated the time and space overhead of constructing the iLabel index on synthetic graphs as the data graph size |𝑉 (𝐺)| increases from 10𝐾 to 10𝑀. Across this range, the total index construction time, including vertex embedding generation, auxiliary synopsis computation, and B+ -tree construction, grows from 19.98𝑚𝑠 to 163.59𝑠𝑒𝑐. Correspondingly, index storage increases from 7.93𝑀𝐵 to 7,400.51𝑀𝐵. These results indicate that the offline cost of LIVE scales gracefully with graph size and remains practical for large-scale graphs.
7
graph-structure comparisons. Early learning-based approaches focus on approximate matching, using GNNs or DNNs to embed graphs or subgraphs into embedding spaces and compare them via distance functions [7, 35, 38, 40, 53, 58]. More recently, learning has been brought to exact subgraph matching. For instance, GNNPE [62] is an early representative framework that learns dominancepreserving embeddings for graph paths, enabling candidate filtering without false dismissals; meanwhile, DIVINE [63] studies dynamic continuous matching using rule-based vertex-dominance embeddings generated by handcrafted rules rather than a learned model. This work differs from prior studies in two key respects. (a) LIVE provides correctness guarantees for exact subgraph isomorphism on large-scale static graphs, whereas prior learning-based methods largely target approximate matching [7, 35, 38, 40, 53, 58]. (b) LIVE enforces dominance preservation by construction via monotonic vertex embeddings, decoupling correctness from learning; this yields lower training cost and stronger pruning than prior embedding-based approaches (e.g., [62, 63]) that rely on costly enumeration or heuristic designs.
RELATED WORK
We classify existing works as follows. Exact Subgraph Matching. Existing exact subgraph matching methods fall into two categories: (i) join-based algorithms and (ii) backtracking-search-based algorithms. Join-based methods [1, 4, 31– 33, 41, 50] decompose a query graph into smaller substructures (e.g., edges, paths, or triangles), enumerate matches for each substructure independently, and join these partial results to obtain final matches. Backtracking-based algorithms [8–10, 12, 13, 22, 24, 47, 51] first compute candidate sets for query vertices using filtering techniques, and then enumerate exact matches via depth-first search while enforcing injective mapping and edge-consistency constraints; recent work further applies reinforcement learning to optimize matching orders in backtracking-based frameworks [54, 61]. LIVE differs from prior work in three key aspects: (i) it scales to dense queries and large graphs via effective pruning with the iLabel index, avoiding the large intermediates of join-based methods [1, 4, 31–33, 41, 50]; (ii) it relies on learned vertex embeddings rather than explicit structural comparisons, improving scalability over backtracking-based algorithms [8–10, 12, 13, 22, 24, 47, 51]; and (iii) unlike feature-vector graph search targeting small graphs [25, 48, 60], LIVE enumerates all exact matches within a single large graph. Approximate Subgraph Matching. Another line of work studies approximate subgraph matching, which aims to efficiently retrieve subgraphs that are similar to a given query graph rather than exactly isomorphic. To improve scalability, these methods relax exact structural constraints and employ heuristic or distance-based similarity measures, such as graph edit distance [36], neighborhood similarity [57], or feature-based approximations [16, 17, 20]. As a result, approximate matching algorithms trade accuracy for efficiency and may return false positives or miss valid exact matches. In contrast, the problem addressed in this work requires enumerating all subgraphs that are exactly isomorphic to the query graph, with no false positives or false dismissals. Therefore, approximate subgraph matching methods do not provide the correctness guarantees required here and are orthogonal to the focus of LIVE. Learning-based Subgraph Matching. Recent work explores learning techniques to accelerate subgraph matching by avoiding explicit
8
CONCLUSION
In this paper, we propose LIVE, a learning-based framework for exact subgraph matching on large graphs that achieves both scalability and exactness. By enforcing monotonicity in vertex embedding construction, LIVE guarantees dominance correctness by design and fundamentally decouples no-false-dismissal guarantees from embedding optimization. This decoupling enables candidate filtering without false dismissals while allowing embedding learning to directly focus on improving vertex-level pruning power. We further introduce a query cost model with a differentiable surrogate objective to guide offline embedding training, and design a lightweight one-dimensional iLabel index that preserves dominance relationships and supports efficient candidate retrieval without complex indexing structures. Extensive experiments on synthetic and real-world datasets validate the performance of LIVE.
15
REFERENCES
[25] Craig A James. 2004. Daylight theory manual. http://www. daylight. com/dayhtml/doc/theory/theory. toc. html (2004). [26] Haolin Jiang, Santosh Pandey, and Hang Liu. 2025. A Comprehensive Survey of Subgraph Matching:[Experiments & Analysis]. In Proceedings of the International Conference on Management of Data (SIGMOD). 1–30. [27] Alpár Jüttner and Péter Madarasi. 2018. VF2++—An improved subgraph isomorphism algorithm. Discrete Applied Mathematics 242 (2018), 69–81. [28] Chathura Kankanamge, Siddhartha Sahu, Amine Mhedbhi, Jeremy Chen, and Semih Salihoglu. 2017. Graphflow: An active graph database. In Proceedings of the International Conference on Management of Data (SIGMOD). 1695–1698. [29] Guy Karlebach and Ron Shamir. 2008. Modelling and analysis of gene regulatory networks. Nature Reviews Molecular Cell Biology 9, 10 (2008), 770–780. [30] Foteini Katsarou, Nikos Ntarmos, and Peter Triantafillou. 2017. Subgraph querying with parallel use of query rewritings and alternative algorithms. In Proceedings of the International Conference on Extending Database Technology (EDBT). 25–36. [31] Longbin Lai, Lu Qin, Xuemin Lin, and Lijun Chang. 2015. Scalable subgraph enumeration in mapreduce. In Proceedings of the International Conference on Very Large Data Bases (PVLDB). 974–985. [32] Longbin Lai, Lu Qin, Xuemin Lin, Ying Zhang, Lijun Chang, and Shiyu Yang. 2016. Scalable distributed subgraph enumeration. In Proceedings of the International Conference on Very Large Data Bases (PVLDB). 217–228. [33] Longbin Lai, Zhu Qing, Zhengyi Yang, Xin Jin, Zhengmin Lai, Ran Wang, Kongzhang Hao, Xuemin Lin, Lu Qin, Wenjie Zhang, et al. 2019. Distributed subgraph matching on timely dataflow. In Proceedings of the International Conference on Very Large Data Bases (PVLDB). 1099–1112. [34] Qiyan Li, Jeffrey Xu Yu, and Zongyan He. 2025. Subgraph Matching: A New Decomposition Based Approach. In Proceedings of the International Conference on Very Large Data Bases (PVLDB). 4282–4294. [35] Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. 2019. Graph matching networks for learning the similarity of graph structured objects. In Proceedings of the International Conference on Machine Learning (ICML). 3835– 3845. [36] Zijian Li, Xun Jian, Xiang Lian, and Lei Chen. 2018. An efficient probabilistic approach for graph similarity search. In Proceedings of the International Conference on Data Engineering (ICDE). 533–544. [37] Xiang Lian and Lei Chen. 2011. Efficient query answering in probabilistic RDF graphs. In Proceedings of the International Conference on Management of Data (SIGMOD). 157–168. [38] Zhaoyu Lou, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, Jure Leskovec, et al. 2020. Neural subgraph matching. arXiv preprint arXiv:2007.03092 (2020). [39] Yujie Lu, Zhijie Zhang, and Weiguo Zheng. 2025. BSX: Subgraph Matching with Batch Backtracking Search. In Proceedings of the International Conference on Management of Data (SIGMOD). 1–27. [40] Brian McFee and Gert Lanckriet. 2009. Partial order embedding with multiple kernels. In Proceedings of the International Conference on Machine Learning (ICML). 721–728. [41] Amine Mhedhbi and Semih Salihoglu. 2019. Optimizing subgraph queries by combining binary and worst-case optimal joins. In Proceedings of the International Conference on Very Large Data Bases (PVLDB). 1692–1704. [42] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019. Pytorch: An imperative style, high-performance deep learning library. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS). 1–12. [43] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. 2017. PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 652–660. [44] Miao Qiao, Hao Zhang, and Hong Cheng. 2017. Subgraph matching: on compression and computation. In Proceedings of the International Conference on Very Large Data Bases (PVLDB). 176–188. [45] Xuguang Ren and Junhu Wang. 2015. Exploiting vertex relationships in speeding up subgraph isomorphism over large graphs. In Proceedings of the International Conference on Very Large Data Bases (PVLDB). 617–628. [46] Siddhartha Sahu, Amine Mhedhbi, Semih Salihoglu, Jimmy Lin, and M Tamer Özsu. 2017. The ubiquity of large graphs and surprising challenges of graph processing. In Proceedings of the International Conference on Very Large Data Bases (PVLDB). 420–431. [47] Haichuan Shang, Ying Zhang, Xuemin Lin, and Jeffrey Xu Yu. 2008. Taming verification hardness: an efficient algorithm for testing subgraph isomorphism. In Proceedings of the International Conference on Very Large Data Bases (PVLDB). 364–375. [48] Dennis Shasha, Jason TL Wang, and Rosalba Giugno. 2002. Algorithmics and applications of tree and graph searching. In Proceedings of the Principles of Database Systems (PODS). 39–52. [49] Shixuan Sun and Qiong Luo. 2020. In-memory subgraph matching: An in-depth study. In Proceedings of the International Conference on Management of Data (SIGMOD). 1083–1098.
[1] Christopher R Aberger, Andrew Lamb, Susan Tu, Andres Nötzli, Kunle Olukotun, and Christopher Ré. 2017. Emptyheaded: A relational engine for graph processing. ACM Transactions on Database Systems 42, 4 (2017), 1–44. [2] Ahmed Al-Baghdadi and Xiang Lian. 2020. Topic-based community search over spatial-social networks. In Proceedings of the International Conference on Very Large Data Bases (PVLDB). 2104–2117. [3] Uri Alon. 2007. Network motifs: theory and experimental approaches. Nature Reviews Genetics 8, 6 (2007), 450–461. [4] Khaled Ammar, Frank McSherry, Semih Salihoglu, and Manas Joglekar. 2018. Distributed Evaluation of Subgraph Queries Using Worst-case Optimal LowMemory Dataflows. In Proceedings of the International Conference on Very Large Data Bases (PVLDB). 691–704. [5] Blair Archibald, Fraser Dunlop, Ruth Hoffmann, Ciaran McCreesh, Patrick Prosser, and James Trimble. 2019. Sequential and parallel solution-biased search for subgraph algorithms. In Proceedings of the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR). 20–38. [6] László Babai. 2018. Group, graphs, algorithms: the graph isomorphism problem. In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018. World Scientific, 3319–3336. [7] Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. 2019. Simgnn: A neural network approach to fast graph similarity computation. In Proceedings of the International Conference on Web Search and Data Mining (WSDM). 384–392. [8] Bibek Bhattarai, Hang Liu, and H Howie Huang. 2019. Ceci: Compact embedding cluster index for scalable subgraph matching. In Proceedings of the International Conference on Management of Data (SIGMOD). 1447–1462. [9] Fei Bi, Lijun Chang, Xuemin Lin, Lu Qin, and Wenjie Zhang. 2016. Efficient subgraph matching by postponing cartesian products. In Proceedings of the International Conference on Management of Data (SIGMOD). 1199–1214. [10] Vincenzo Bonnici, Rosalba Giugno, Alfredo Pulvirenti, Dennis Shasha, and Alfredo Ferro. 2013. A subgraph isomorphism algorithm and its application to biochemical data. BMC Bioinformatics 14, 7 (2013), 1–13. [11] Stephan Borzsony, Donald Kossmann, and Konrad Stocker. 2001. The skyline operator. In Proceedings of the International Conference on Data Engineering (ICDE). 421–430. [12] Vincenzo Carletti, Pasquale Foggia, Alessia Saggese, and Mario Vento. 2017. Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with VF3. IEEE Transactions on Pattern Analysis and Machine Intelligence 40, 4 (2017), 804–818. [13] Vincenzo Carletti, Pasquale Foggia, and Mario Vento. 2015. VF2 Plus: An improved version of VF2 for biological graphs. In International Workshop on GraphBased Representations in Pattern Recognition (GbRPR). 168–177. [14] Luigi P Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento. 2004. A (sub) graph isomorphism algorithm for matching large graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence 26, 10 (2004), 1367–1372. [15] Alin Deutsch, Nadime Francis, Alastair Green, Keith Hare, Bei Li, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Wim Martens, Jan Michels, et al. 2022. Graph pattern matching in GQL and SQL/PGQ. In Proceedings of the International Conference on Management of Data (SIGMOD). 2246–2258. [16] Boxin Du, Si Zhang, Nan Cao, and Hanghang Tong. 2017. First: Fast interactive attributed subgraph matching. In Proceedings of the International Conference on Knowledge Discovery and Data Mining (SIGKDD). 1447–1456. [17] Sourav Dutta, Pratik Nayek, and Arnab Bhattacharya. 2017. Neighbor-aware search for approximate labeled graph matching using the chi-square statistics. In Proceedings of the Web Conference (WWW). 1281–1290. [18] Michael R. Garey and David S. Johnson. 1983. Computers and intractability: A guide to the theory of NP-completeness. The Journal of Symbolic Logic 48, 2 (1983), 498–500. [19] Martin Grohe and Pascal Schweitzer. 2020. The graph isomorphism problem. Commun. ACM 63, 11 (2020), 128–134. [20] Qiuyu Guo, Jianye Yang, Wenjie Zhang, Hanchen Wang, Ying Zhang, and Xuemin Lin. 2025. Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach. In Proceedings of the International Conference on Very Large Data Bases (PVLDB). 2695–2708. [21] Aric Hagberg and Drew Conway. 2020. Networkx: Network analysis with python. URL: https://networkx. github. io (2020). [22] Myoungji Han, Hyunjoon Kim, Geonmo Gu, Kunsoo Park, and Wook-Shin Han. 2019. Efficient subgraph matching: Harmonizing dynamic programming, adaptive matching order, and failing set together. In Proceedings of the International Conference on Management of Data (SIGMOD). 1429–1446. [23] Wook-Shin Han, Jinsoo Lee, and Jeong-Hoon Lee. 2013. Turboiso: towards ultrafast and robust subgraph isomorphism search in large graph databases. In Proceedings of the International Conference on Management of Data (SIGMOD). 337–348. [24] Huahai He and Ambuj K Singh. 2008. Graphs-at-a-time: query language and access methods for graph databases. In Proceedings of the International Conference on Management of Data (SIGMOD). 405–418. 16
[50] Shixuan Sun, Xibo Sun, Yulin Che, Qiong Luo, and Bingsheng He. 2020. Rapidmatch: A holistic approach to subgraph query processing. In Proceedings of the International Conference on Very Large Data Bases (PVLDB). 176–188. [51] Zhao Sun, Hongzhi Wang, Haixun Wang, Bin Shao, and Jianzhong Li. 2012. Efficient Subgraph Matching on Billion Node Graphs. In Proceedings of the International Conference on Very Large Data Bases (PVLDB). 788–799. [52] Damian Szklarczyk et al. 2015. STRING v10: protein–protein interaction networks, integrated over the tree of life. Nucleic Acids Research 43, D1 (2015), D447–D452. [53] Ivan Vendrov, Ryan Kiros, Sanja Fidler, and Raquel Urtasun. 2016. Orderembeddings of images and language. In Proceedings of the International Conference on Learning Representations (ICLR). 1–12. [54] Hanchen Wang, Ying Zhang, Lu Qin, Wei Wang, Wenjie Zhang, and Xuemin Lin. 2022. Reinforcement learning based query vertex ordering model for subgraph matching. In Proceedings of the International Conference on Data Engineering (ICDE). 245–258. [55] Stanley Wasserman and Katherine Faust. 1994. Social network analysis: Methods and applications. (1994). [56] Duncan J Watts and Steven H Strogatz. 1998. Collective dynamics of ‘smallworld’networks. Nature 393, 6684 (1998), 440–442. [57] Qi Wen, Yutong Ye, Xiang Lian, and Mingsong Chen. 2025. S3AND: Efficient Subgraph Similarity Search Under Aggregated Neighbor Difference Semantics. In Proceedings of the International Conference on Very Large Data Bases (PVLDB). 3708–3720. [58] Kun Xu, Liwei Wang, Mo Yu, Yansong Feng, Yan Song, Zhiguo Wang, and Dong Yu. 2019. Cross-lingual knowledge graph alignment via graph matching neural
network. arXiv preprint arXiv:1905.11605 (2019). [59] Xifeng Yan, Hong Cheng, Jiawei Han, and Philip S Yu. 2008. Mining significant graph patterns by leap search. In Proceedings of the International Conference on Management of Data (SIGMOD). 433–444. [60] Xifeng Yan, Philip S Yu, and Jiawei Han. 2004. Graph indexing: a frequent structure-based approach. In Proceedings of the International Conference on Management of Data (SIGMOD). 335–346. [61] Linglin Yang, Lei Zou, and Chunshan Zhao. 2025. NeuSO: Neural Optimizer for Subgraph Queries. In Proceedings of the International Conference on Management of Data (SIGMOD). 1–28. [62] Yutong Ye, Xiang Lian, and Mingsong Chen. 2024. Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding. In Proceedings of the International Conference on Very Large Data Bases (PVLDB). 1628–1641. [63] Yutong Ye, Xiang Lian, Nan Zhang, and Mingsong Chen. 2025. Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings. In Proceedings of the International Conference on Management of Data (SIGMOD). 1–27. [64] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan Salakhutdinov, and Alexander Smola. 2017. Deep Sets. In Advances in Neural Information Processing Systems (NeurIPS), Vol. 30. [65] Nan Zhang, Yutong Ye, Xiang Lian, and Mingsong Chen. 2024. Top-𝐿 Most Influential Community Detection Over Social Networks. In Proceedings of the International Conference on Data Engineering (ICDE). 5767–5779. [66] Peixiang Zhao and Jiawei Han. 2010. On graph query optimization in large networks. In Proceedings of the International Conference on Very Large Data Bases (PVLDB). 340–351.
17