Vector Database Watermarking
Authors: zhiwen ren
Wei Fan
Qiyi Yao
Jing Qiu
Weiming Zhang
Nenghai Yu
Venue: NeurIPS 2025 poster ()
Keywords: Watermark
ANN
Vector database
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: A vector database watermarking scheme with fewer query errors is proposed.

Abstract: Vector databases support machine learning tasks using Approximate Nearest Neighbour (ANN) query functionality, making them highly valuable digital assets. However, they also face security threats like unauthorized replication. By embedding stealth information, watermarking technology can be used for ownership authentication. This paper introduces a watermarking scheme specifically designed for vector databases. The scheme consists of four steps: generating identifiers, grouping, cryptographic mapping, and modification. Since watermark embedding requires modification of certain vectors, it may negatively affect the ANN query results. Further investigation reveals that in the widely used Hierarchical Navigable Small World (HNSW) indexing structure for vector databases, heuristic edge selection and pruning strategies result in some vectors having fewer edges or even none at all. These vectors exhibit significantly lower query frequencies than others, which means that modifying these vectors incurs less impact on query results. Based on this observation, we propose the Transparent Vector Priority (TVP) watermarking scheme, which prioritizes embedding the watermark in these low-query-frequency “transparent” vectors to minimize the impact of watermark embedding on query results. Experimental results show that compared to the current most effective and relevant watermarking schemes, the TVP scheme can significantly reduce the number of missed and false queries by approximately 75\%.

Vector Database Watermarking
Zhiwen Ren, Wei Fan, Qiyi Yao", Jing Qiu, Weiming Zhang", Nenghai Yu
School of Cyber Science and Technology University of Science and Technology of China, Hefei, China
Abstract
Vector databases support machine learning tasks using Approximate Nearest Neigh- bour (ANN) query functionality, making them highly valuable digital assets. How- ever, they also face security threats like unauthorized replication. By embedding stealth information, watermarking technology can be used for ownership authentica- tion. This paper introduces watermarking scheme specifically designed for vector databases. The scheme consists of four steps: generating identifiers, grouping, cryptographic mapping, and modification. Since watermark embedding requires modification of certain vectors, may negatively affect the ANN query results. Further investigation reveals that in the widely used Hierarchical Navigable Small World (HNSW) indexing structure for vector databases, heuristic edge selection and pruning strategies result in some vectors having fewer edges all. These vectors exhibit significantly lower query frequencies than others, which means that modifying these vectors incurs less impact query results. Based on this observation. we propose the Transparent Vector Priority (TVP) watermarking scheme, which prioritizes embedding the watermark in these low-query low-query-frqquency "transparent" vectors to minimize the impact of watermark embedding on query results. Experimental results show that compared the current most effective and relevant watermarking schemes, the TVP scheme can significantly reduce the number of missed and false queries by approximately 75%.
none at
Introduction
vector database (25 is data management system specifically designed to store and retrieve vector data. These vectors are generated by machine learning models and represent raw unstructured data such text, images, and audio. By converting unstructured data into vectors, can measure the similarity between different data by calculating the distance between the vectors. Vector databases can recommender
be applied to scenarios such as retrieval augmentation generation (RAG) 22 16 systems, and similar case retrieval.
The applications of vector databases rely approximate nearest neighbor(ANN) search. Nearest neighbor (NN) search refers to finding multiple vectors in a vector dataset that are closest to a given query vector. When the size of the vector dataset large, the time cost of completely traversing all vectors for an exact search is too high, so the researchers proposed the approximate nearest neighbor ANN algorithms can find multiple vectors that are close to the query vector in reasonable amount of time, and even though these vectors may not be the absolute nearest vectors, they usually satisfy the practical requirements.
search (34 14 31
Criteria for evaluating ANN algorithms include recall, query response time, index construction time, space occupation, etc. After long period of development, variety of ANN methods have
emerged, mainly including tree-based 3 37 graph-based [3 hash-based (32 35 21 and
"Corresponding author:
(qyyao@mall mail,, zhangwm@ )
ustc.edu.en.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

quantization- based methods [5 11 6]. Hierarchical Navigational Small World (HNSW) stands out among many methods because its high recall and fast query speed. Therefore, it supported by many commercial vector database systems such as Milvus (24) and Pinecone 27 and is currently one of the most important vector database Indexing structures.
Recently vector databases have been widely used in various Al applications. For example, in medical scenarios, medical institutions can share desensitised disease feature vectors, and patients can retrieve similar cases and the doctors or institutions that have dealt with them through similarity searches, so as to obtain medical reference suggestions without compromising the privacy of patients. This shows that vector databases have high application value, and their copyright protection issues should be given due attention. Watermarking technology [I9] 10 20 13) is a common means of copyright protection, and watermarks can be embedded into digital assets to prove their ownership. However, existing vector data watermarking methods [33] 28 are primarily applied to coordinate vectors in Geographic Information Systems (GIS), while current database watermarking methods [li2022secure, 1 are mainly designed for relational databases. Neither of these approaches suitable for vector databases.
In this paper, we present for the first time a vector database watermarking scheme. The scheme is divided into four steps: identifier generation, vector grouping, cryptographic mapping and modifying partial vectors. The watermark information embedded by modifying some vectors to change the distribution of vector cryptographic mapping results within the group. We present two vector selection strategies: random selection (RS) and transparent vector priority (TVP). RS is basic strategy that selects vectors randomly for modification. The defect of RS is that it will change the relative positions and neighbor relationships between the vectors, and may have a negative impact on the ANN query, which is called the "embedding impact". In order to quantify this embedding impact, we define the number of missed queries and the number of false queries the vectors before and after embedding the watermark as the evaluation metrics. In order to reduce the embedding impact of watermarking, we conduct an in-depth study on the HNSW index structure. We conjecture and confirm that due to the heuristic edge selection and pruning strategy of HNSW, some vectors have few or even no edges, and these vectors are less frequently queried compared to other vectors, and thus modifying these vectors results in few query errors. We call these vectors with low query frequency "transparent vectors".
Based on this finding, we propose a transparent vector priority vector database watermarking scheme. When selecting vectors for modification, TVP prioritizes transparent vectors to minimize the embed- ding effect according to the transparency threshold required by the algorithm. Experimental results show that by prioritizing transparent vectors, TVP significantly reduces the impact of watermark embedding on ANN queries while maintaining good robustness.
Contributions. The contributions of this paper are as follows:
Quantifying embedding impact: Defining the number of missed queries and false queries to quantify the impact of watermark embedding on ANN queries for the first time.
Optimizing vector database watermarking schemes: Proposing the first vector database watermarking scheme RS and minimizing embedding impact through the Transparent Vector Priority (TVP) strategy.
Experimental Validation: Experimental results demonstrate that TVP significantly reduces the embedding impact and also has strong robustness.
2
Related Work
This section reviews existing watermarking schemes for relational databases and datasets, highlighting their development, challenges, and differences from vector database watermarking.
Agrawal et al. proposed the first relational database watermarking scheme [T. which embeds the watermark by modifying the least significant bit (LSB) of the data. Although it enables basic embedding and extraction, is less robust and susceptible to data tampering. Subsequently. Sion et al. (30) and Cui et al. improved enhance the robustness, but still causes data distortion.
26 have been developed to safeguard the availability of databases. These algorithms can recover the original data, but the process of recovering the
Reversible watermarking algorithms 5

---

original data is also the process of removing the watermark, so the recovery privileges need to be carefully managed. Schemes based on distortion constraints limit the magnitude of data modification during watermark embedding to maintain usability, but they often require compromises in embedding capacity or extraction accuracy.
Ren et al. 29 propose a statistical
watermarking scheme for relational databases that ensures that watermark embedding does affect the statistical properties of the data. Tabular- Mark (36], proposed by Zheng et al. makes watermarking virtually stealth to dataset applications for some machine learning tasks.
Vector database watermarking shares the same goals as these schemes, such as basic embed- ding/extraction. robustness and usability. However, the metrics to measure the impact of water- marking on usability are different due to different usage scenarios. Therefore, applying existing schemes directly to vector databases may not be effective.
3 Preliminaries
3.1 Approximate Nearest Neighbor (ANN)
Unstructured data (e.g.. text, images, audio) can be transformed into high-dimensional vectors via feature extraction. The distance between vectors indicates the similarity of the original data. Nearest- neighhor search of vectors enables quick location of similar data in large-scale datasets, supporting intelligent applications.
Let D {V*, V²,..., V") represent vector database with vectors, where V R For any two vectors Vú and V, in D, the Euclidean distance can be denoted as p(V", V.). Nearest neighbor (NN) search aims to find k neighbor vectors No (N1,N2, .N in the vector database D that are closest to the query vector q, satisfying:
N argmin
Σ N(g
(I)
NoC D. [N9] = R11
When the dataset size is large, the time cost of NN search is high. Thus, ANN search is proposed. relaxes the accuracy requirement and aims to find k vectors N2, NN such that:
p(g. N₂) S p(g, NT), 0 Osisk
where e 2 1 is the error tolerance, meaning the distance between the found vector and the query vector is most e times the distance of the true nearest neighbor.
3.2 Hierarchical Navigable Small World
Hicrarchical Navigable Small World (HNSW) 23 is an important graph-structured algorithm for ANN querying of high-dimensional data. It balances query efficiency and accuracy through four core ideas: hicrarchical, heuristic edge selection, pruning, and greedy search.
Hierarchical: HNSW constructs a multi-layered small world graph. The bottom layer contains all vectors, and as the number of layers increases, the number of vectors and connected edges decreases, creating sparse structure.
Edge selection strategy: When adding vector y. HNSW first finds the e/Construcl nearest neighbours of q and checks whether g should be connected to it. Given a set S of vectors that have been connected g, q will be connected to its nearest neighbour only if p(e, q) ple, of all in S.
Operation strategy: Each vector has upper bound on the number of edges. If adding g causes vector e to exceed this upper limit (set to 2M in the bottom layer and M in the other layers), then e must reselect its edges.
Greedy search: In HNSW for ANN search with query vector y to find the K closest vectors, start from the highest-level entry vector and move down layer-by-layer. At non-bottom layers, greedily find the closest vector to g as the next-layer entry. the bottom layer, maintain sets W (nearest neighbors) and C' (candidates). Continuously pick the closest vector from C to g to update W until C
3

---

is empty no C' vector is closer to q than W vectors. When K = 1, this process is known as greedy search. More detailed introductions and examples can be found in Appendix A
3.3 Watermarking Framework
The watermark W E {0, 134 is binary string be embedded into digital carriers for copyright verification. A watermarking scheme for vector database DD consists of the following two algorithms:
Embedding Algorithm:
(m W, - Dw
Input: the original database D, the watermark W, and the embedding parameters 0j.
Output: the watermarked database Dw.
Extraction Algorithm:
Ex(D', 02) + W"
Input: a database that may have been modified and extraction parameters 82.
Output: the extracted watermark W
Before sharing vector database, data owners can an embedding algorithm embed watermarks into the database. When copyright disputes arise, an extraction algorithm can be used to extract watermarks from suspected infringing copies of the data, serving evidence of copyright ownership.
3.4 Threat Model
Assume that the vector database is stolen. Then the thief may try remove the watermark through various attacks before using the database, thus preventing us from claiming the copyright. In this context, define the threat model for watermarking as follows:
Full access privileges: the attacker has all the privileges the vector database and can perform add, delete, change, and query operations.
Knowledge of the algorithm but not the parameters: the attacker is familiar with the embedding algorithm of the watermark, but does not know the specific parameters used for embedding.
The intensity of attacks is constrained: Since attackers themselves also database users, they must maintain retrieval functionality while attempting to remove watermarks. Therefore, they will only apply attacks of limited intensity avoid significant decline in retrieval accuracy.
Basic Methodology: Random Selection
This section describes basic watermarking scheme for vector databases, which generates a unique identifier ID for each vector, divides the vectors into groups based on the identifier, maps each vector as 'I-vector' or 'O-vector', and adjusts the ratio of different types of vectors each group by modifying the vectors to embed the watermark information. Since the vectors are randomly selected for modification, the scheme is called a Random Selection Scheme (RS). the following, we describe the watermark embedding and extraction process in detail.
4.1 Watermark Embedding
The watermark embedding process consists of four steps: generating vector identifier, vector grouping. cryptographic mapping and vector modification. The pseudo-code shown in Algorithm I in Appendix B
Generate vector identifier: To avoid relying the original vector identifiers,
the Most Significant Bit (MSB) method (36) to generate identifiers directly from the vector data. Initialise the random number generator using the seed parameter generate set of random dimension indices I -= {di, .2,.... dm J. Extract the highest bits from each selected dimension and concatenate these bits to form identifier DDy: IDv =
MVa...)
where (x) denotes the highest valid bit of x. For example, given a vector V (42, 23, 78, 14) and randomly chosen dimension I = {2, 3}. the identifier is (17) = 71.

---

Vectors grouping: Watermark W are binary sequences defined by the database owner. If the length of the watermark is L, the vectors are partitioned into L non-overlapping groups. A vector V is assigned to group when the result of taking the modulo of the hash value of its identifier (TDv) with I. is equal to g, that is, (IDvv) mod I. =
Cryptographic mapping: each vector V is converted to a binary value (0 or 1). First, the target embedding dimension dn (1D) mod is computed. To avoid changing the identifier DD of the vector during the watermarking process, if du is in the dimensions set I used to generate ID, it is iteratively updated as du (dw + 1) mod until dw is outside of that set. Next, the value Vd.. is extracted from the target dimension, converted to a binary b of length 1, and the index (0 < I 1) is computed. The (1 2)th bit of is used as the initial mapping result. The factor f (0- < f < 1) can modulate the size of the index i, indirectly affecting the magnitude of potential modifications in subsequent processes. For example, for the vector V = (42, 23, 78, 14), if d 3 conflicts with the dimension that produces IDv. it is updated to (3+1) mod 4 0. With Vo- 42 (in binary form 101010, 1 6) and 3, the initial mapping bit is 6[3] 0.
i (IDv) mod (1 X f) +
However, this approach faces the "sparsity curse": sparse vectors in the database tend to map primarily to 0, which skews the distribution and weakens the effectiveness of the watermark. To alleviate this problem. we introduce an enhancement strategy: XOR the initial result w with the least significant bit
of (1 - i). i.., w = w + ((1 - i) mod 2). The pseudo-code is shown in Algorithm 2 in Appendix B
Vector modification: Vectors mapped To embed the g-th bit W3 of the watermark W into the g-th group of vectors, the proportion of vectors that can be mapped to the value of W, needs to be increased to the preset watermark strength s. For example, if W, 9 and the g-th group contains 1,000 vectors, among which 500 are I-vector, when s = 0.7, it means that we expect the proportion of 1-vector to be 0.7, that is, there should be 700 1-vector. In this case, 200 O-vector need to be converted into 1-vector.
or O are respectively referred to as " "1-vector" or "O-vector".
Calculate the number of vectors 7.m that need be modified for each group, and then randomly select am vectors from these vectors that cannot be cryptographically mapped to W, as the carrier vector Cv. Change their cryptographic mapping results by flipping the bit b[[ a]. For instance, given = 101010 and = 3, flipping b[3] will change the mapping from biZ i] @ ((1 - i) mod 2) ④ 1 to 0 1 = 1. By traversing all groups and adjusting the distribution of vectors, the watermark embedding can be completed.
4.2 Watermark Extraction
The extraction process uses the same seed seed as the embedding to ensure that the vector groupings and cryptographic mappings are the same. For each group the watermark bit W,, is determined by majority voting: if the number of 1-vectors exceeds the number of O-vectors, then Ws 1; otherwise. W, g = 0. Iterate over all groups to reconstruct the extracted watermark W Pseudo-code is provided in the Algorithm 3a in Appendix
Embedding Impact
In this section, we define and model the impact of watermark embedding on the query process to guide us in optimizing the watermarking approach.
To quantitatively measure the negative impact of watermarking vector ANN queries, give the following definition:
Definition 1: (Nearest Neighbor Response Domain). The nearest neighbor response domain Ry of vector is defined as:
Rv A (alg e D, V N9).
For vector V D, all the query vectors q from D that consider V as a nearest neighbor vector make up the nearest neighbor response domain Ry of V.
Definition 2: (Number of Missed Queries). The number of missed queries My of vector V is defined as:
My & RRv \ Rvwh
(5)
5

---

before adding q
qis connected
1, disconnect from q
before adding q
q connected
disconnect
to 1,2
1,2
from q
Vector q no edge.
(b) query stuck a local optimum.
Figure I: Two cases in which the vector cannot be queried.
where \ represents the relative complement operation and \ B set elements A but
not B. and Vw respectively denote the vector data before and after the watermark embedding. Thus, the number of missed queries for refers to the number of vectors that originally belonged to the nearest neighbor response domain Ry of V but are absent from the nearest neighbor response domain Ryw of Vw.
Definition 3: (Number of False Queries). The number of false queries Fy of vector V is defined as:
Fy & RRw Ryl.
(6)
The Number of false queries of V refers the number of vectors that belong the nearest neighbor response domain Ryw of Vw but are missing in the nearest neighbor response domain Ry V.
The selection of carrier vectors Cv should be considered from the following two aspects:
Low embedding impact: in order minimize the impact watermarking on query results, i.e. to reduce My and Fv, vectors that are rarely queried should be preferred as carrier vectors.
High robustness: in order to prevent the attacker from accurately locating and deleting the carrier vectors by their features, the selection of vectors with too obvious features should be avoided.
Methodology: Transparent Vector Priority
This section introduces two key concepts, Stealth vectors and Transparent vectors, which are the basis of our proposed scheme. Based the study of these two types of vectors, Transparent Vector Priority scheme is proposed to reduce the impact of embedded watermarks on query results.
6.1 Stealth Vectors and Transparent Vectors
We conjecture that the heuristic edge selection and pruning strategy of HNSW may produce edgeless vectors. Take Fig. ((a) as an example, the vector is connected with vector 1 and 2 such that the number of edges of vector 1 and increases to three. If the maximum number of edges is set to 2, the vector and need to be re-selected according to the pruning strategy. Since they already have two neighbours closer than q, they will not be connected to q, and becomes edgeless vector. Experiments on the ANN SIFTIM dataset verified the existence such vectors, and the detailed procedure is shown in Appendix C only the conclusions 100, the constructed HNSW graph contains 12 connected
Stealth Vectors:
presented here. With
parameters M = 8 and e CConstrucl branches, 11 of which contain only one edgeless vector. In further experiments, all vectors used as query vectors to retrieve the 10 nearest neighbours, and the number of times each vector is queried recorded, which shows that the edgeless vector never queried.
In addition, 40 vectors the maximum connected branch are never queried, presumably due to the search algorithm falling into local optimum. As shown in Fig. [(b] vector I is disconnected from the edge due to the pruning strategy, and the greedy algorithm will mistakenly take vector 1 as the result when querying q. Experiments show that the average degree of the unqueriable vectors in the maximal connected branch 1.87, while the average degree of the random 1000 vectors 8.92, which verifies the property that such vectors have fewer edges.
Based on the above characteristics, we define these two types of unqueriable vectors as Stealth vectors.

---

Transparent Vectors:
Since stealth vectors are never queried, embedding watermarks in such vectors has minimal impact on queries. However, stealth vectors are not optimal watermarking vectors, as they are recognised by their distinctive features, and there is a risk of removing the watermark by deleting all non-queryable vectors. To balance the transparency and robustness of watermarking, we prefer to use vectors that are queried less frequently as carrier vectors, calling such vectors transparent vectors.
Based on the feature that stealth vectors are "far away from other vectors and have fewer edges", we propose the hypothesis that vectors with longer edges and fewer edges are more likely to be transparent vectors. We test this hypothesis experimentally. The experiments found that the number of times vector is queried decreases when the average edge length of the vector increases, while decrease in the number of edges also leads to a decrease in the number of queries.
To quantitatively measure the number of times vector is queried, we construct the transparency parameter is by combining the average edge length I and the number of edges of the vector:
me
La
61
8e
where my and & denote the mean and standard deviation of the variable I. To reduce the computational overhead, some of the vectors can be sampled for computation.
Table I: Correlation coefficient between different parameters and the count of queries.
parameter
ts
-0.6998
-0.5565
0.5131
To compare the correlation e between the transparency parameter tss, the average edge length and the number of edges with the number of queries, the correlation coefficients p between them and the number of queries were calculated, and the results are shown in Table It can be seen that the absolute value of the correlation coefficient between the transparency parameter is and the number of queries is the largest, which indicates that is has the strongest correlation with the number of queries, and therefore ts is more suitable to be used as parameter to measure the transparency of the vector. Furthermore, we calculated the Pearson correlation coefficient between the transparency parameter ts and query frequency under various HNSW configurations (see Appendix C Table 3}. The results consistently fell below -0.66, indicating that ts exhibits stable and consistent negative correlation with the query frequency, thereby serving as a reliable transparency metric.
In summary, we confirm the existence of transparent vectors in HNSW and conclude that: due to the edge pruning strategy, some vectors far away from other vectors have few edges or even no edges, which makes them difficult be retrieved; the transparency of vectors can be measured by the transparency score 1s, and the larger Is is, the more likely it is a highly transparent vector.
6.2 Transparent Vector Priority (TVP)
This section introduces the Transparent Vector Priority (TVP) vector database watermarking TVP follows the same framework as the RS scheme, but prioritises highly transparent vectors as carrier vectors to minimise query errors caused by watermark embedding.
Taking advantage of the edge correlation property of HNSW, query frequency as the ideal carrier. Theoretically. in order to find these transparent vectors accurately, it is necessary to count the number of queries for each vector through large number of queries, from which the vectors with low query frequency are filtered out. Based on the study of transparent vectors in the previous section, we can quickly find transparent vectors by using the is parameter.
transparent vectors with low
Specifically, the TVP algorithm uses the threshold parameter 7 (0- - 1) to select the first 7 x 100% of transparent vectors. It randomly samples the vectors, computes the mean and variance of their edge length and number of edges e, computes the transparency score ts, and determines the filtering threshold ts, based on the top J ranked vectors.
When the embedding algorithm needs to select vectors for modification, it no longer selects vectors randomly, but prefers vectors with transparency score ts greater than the threshold (sr, i.e., vectors with higher transparency and lower query frequency. If I is set smaller, there may not be enough eligible vectors, and the algorithm will only select vectors with slightly lower transparency scores.
7

---

7 Experiments
watermarking algorithm can be evaluated from two aspects: embedding impact and watermark robustness.
We use the average number of missed queries (AMQ) and the average number of false queries (AFQ) of watermarked vectors containing watermarks after adding watermarks to measure the embedding impact. The specific calculation methods of these indicators are as follows:
Every My Cvl
AFQ A Ever Fv
AMQ
CCvl
Watermark robustness is the ability to accurately extract watermarks from watermark-containie vectors under attack. Given the threat model in section 3.4 an attacker who knows about our watermarking approach will use adaptive attack strategy. All robustness experiments involve such adaptive attacks. Among them, adaptive deletion and modification attacks are the most effective. In the former attack, the attacker removes certain percentage of transparent vectors to remove the watermark. In the latter attack, the attacker modifies the values of some of the dimensions of the partially transparent vector. We measure robustness using the bit error rafe (BER) between the extracted watermark and the embedded watermark, which is calculated as:
BER
1=
wi ① W
L
where wy is the i-th watermark, and wi is the extracted i-th watermark.
The data and environment used for the experiments are consistent with Section 6.1 i.c., the commonly used vector dataset ANN SIFTIM(18) was implemented and experimented with using Python and Faiss libraries on PCs equipped with AMD Ryzen 5600G processors. Experimental results are generally the average of multiple runs. The default parameters for the experiment are M 8, efConstruct 100, and 100 neighbors per query.
7.1 Comparison
In this section, we apply state-of-the-an relevant watermarking schemes to vector databases and compare them with TVP. Specifically, they include SCPW, watermarking scheme for relational databases proposed in 2023; TabularMark, a watermarking scheme for tabular datasets proposed in 2024; and RS, a scheme proposed in Section 4 of this paper. In the comparison experiments, the public parameters of all the schemes are kept the same, while the private parameters of the schemes are chosen to have the optimal configurations according to their characteristics.
Table 2: Embedded impacts of different schemes.
Scheme
SCPW TabularMark[33 36)
RS
TVP
AMQ
14.26
12.76
13.52
3.15
AFQ
14.67
13.15
13.65
3.21
Table 2 demonstrates the AMQ and AFQ before and after embedding watermarks using different schemes. The results show that the AMQ and AFQ of the TVP scheme are reduced by approximately 75% compared to the other schemes. This is because the other schemes do not fully consider minimizing the impact of watermarking on queries, while TVP reduces the number of false and missed queries by preferring transparent vectors that have been queried less often to embed watermarks.
Additionally, evaluated the variance and maximum values of missed queries (MQ) and false queries (FQ) across different schemes. The results indicate that TVP exhibits lower volatility. Detailed findings are presented in Appendix Table We further evaluated generalization capabilities of TVP on other datasets, with results indicating it consistently achieves significant reductions in AMQ and AFQ across all datasets. Detailed results are presented in Tables 5 G Appendix [
Since TabularMark does not embed watermarked plaintext, its robustness cannot be directly measured using BER. Therefore, following the method proposed by the authors of the scheme, we use the

---

Watermark Extraction Performance under Deletion Attack
Watermark Extraction Performance Modification Attack
TVP (BER)
TVP (BER)
0.7-
RS (BER]
SCPW (BER)
SCPW (BER)
0.6
TabularMark (MP)
TabularMark (MP)
BER NP
0.4
BER
0.3
0.1
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.2
0.4
0.5
0.8
Deletion Proportion (p)
Modification Proportion (p)
(a) Deletion Attack.
(b) Modification Attack.
Figure 2: Watermark robustness of different schemes.
proportion of watermarks flipped due to vector modification, i.e., Mismatch Percentage (MP), as metric for robustness under modification attack. For deletion attack, the proportion of watermarked vectors deleted is used as the robustness metric. Since deletion also leads to mismatches, we also denote this metric by MP.
Figure illustrats the BER or MP of different schemes after being subjected to a deletion attack. Different colored lines represent different schemes. can be seen that the BER of is comparable to other schemes, indicating that its robustness can be as strong as existing schemes. Figure 2(b) shows the BER mismatch percentage of different schemes after a modification attack. Again, the robustness of TVP is similar to the existing schemes.
In summary, the experimental results show that TVP not only significantly reduces query errors but also maintains considcrable robustness compared to the current optimal watermarking scheme. Therefore, TVP is currently the most suitable watermarking scheme for vector databases.
7.2 Method Validation And Parameter Analysis Experiments
This section presents
comprehensive set of experiments designed to: (1) test the effectiveness of the proposed TVP strategy: (2) investigate the impact of key parameters on embedding impact and watermark robustness, thereby providing guidance for parameter selection. Detailed experimental procedures and most of the results are presented in the Appendix E
TVP Strategy Effectiveness: We evaluated the impact of TVP strategy on query performance under different HNSW parameter configurations. Results indicate that both AMQ and AFQ remain at low levels and are minimally affected by parameter variations. Detailed results presented in Appendix T To evaluate the impact of TVP on recall rate, we compared the recall rate (R @k) at different values before and after watermark embedding. As shown in Appendix E Table X the recall rate remained virtually unchanged, indicating that TVP has a negligible effect on retrieval accuracy. We evaluated the generalization capability of the TVP strategy across multiple ANN index structures. By recording the query frequency of vectors, TVP prioritises embedding watermarks in low-frequency vectors. This strategy was compared against the baseline method of randomly selecting vectors (RS). Experimental results, as shown in Appendix F Table demonstrate that TVP reduces the impact query performance caused by embedding across all indexes. Therefore, the concept of transparent vector priority applies not only to HNSW but also to other ANN indexes.
The parameter significantly influences both AMQ and AFQ. A smaller value o means that the algorithm prefers more transparent vectors as the carrier vectors, which drastically reduces the number of false queries and missed queries. As shown in Fig. 7 of Appendix B the smaller 7 is, the less impact it has on the query. The parameter s affects the number of vectors that need to be modified. The larger the s, the more vectors need to be adjusted to match the watermark bits, which has a greater impact on the query result.
Embedding Impact:
Watermark Robustness: The larger value of 8 enables more carrier vectors in each group after embedding to be mapped to the target watermarked bits and enhances the robustness of watermarking. Fixing other parameters, experiments are conducted on different combinations of and deletion

---

0.4
0.55
0.4
$ 0.6
-= 0.4
0.7
0.6
0.2
0.2
5 0.9
0.0
0.0
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
(a) Deletion Attack(s).
(b) Deletion Attack(r).
0.4
0.55
r= 0.2
0.4
0.4
$ = 0.7
T=
$ = 0.8
0.2
== 0.8
0.2
r=
0.0
0.0
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
(c) Modification Attack(s)
(d) Modification Attack(7)
Figure 3: The figure illustrates the impact of parameters on watermark robustness. The horizontal axis represents the attack intensity while the vertical axis shows the BER (Bit Error Rate).
attack proportion and the results are shown in Fig. 3(a) It can be seen that under the same attack strength, the larger the value the smaller the BER, i.c., the stronger the robustness. The results of the modified attack experiments (Fig, ((b) also confirm this conclusion. The smaller the T value is, the more prominent the carrier vector features are, and the watermark is easily damaged by the adaptive attack. From Fig. 3(c) and Fig. 3(d) the smaller r is, the larger BER is, and the weaker the robustness is.
Conclusion
This paper explores watermarking techniques in vector databases and proposes the first watermarking scheme, RS. However, RS will modify some vectors, leading to false queries and missed queries in ANN queries. To reduce these embedding impact, conducted in-depth study of the most popular index structure, HNSW, and discovered its characteristic: certain vectors the HNSW graph have few
edges, resulting in lower query frequencies for these vectors. Modifying these "transparency vectors" will not result in too many false queries and missed queries. Building upon this insight, refine RS into TVP, prioritising transparent vectors watermark carriers minimise embedding impact. Experimental results demonstrate that TVP significantly reduces false queries and missed queries while exhibiting robust performance.
This paper presents a transparency score construction formula specifically for HNSW. For other index structures, no suitable (s currently exists to enable rapid selection of transparent vectors. In future work, we shall explore concrete methods for extending the concept of transparent vectors priority to other index structures.
Limitations:
Acknowledgements
The authors thank the anonymous reviewers and meta-reviewers for their time and constructive feedback. This work was supported in part by the Natural Science Foundation of China under Grant U2336206, 62102386, 62372423, and 62121002.
10

---

References
[1] Rakesh Agrawal and Jerry Kiernan. "Watermarking relational databases". In: VLDB 02: Proceedings of the 28th International Conference on Very Large Databases. Elsevier. 2002,
pp. 155-166.
[2] Jon Louis Bentley. "K-d trees for semidynamic point sets". In: Proceedings of the sixth annual symposium on Computational geometry. 1990, pp. 187-197.
[3] Jon Louis Bentley. "Multidimensional binary search trees used for associative searching". In: Communications of the ACM 18.9 (1975), pp. 509-517.
[4] Xinchun Cui al. "A robust algorithm for watermark numeric relational databases". In: Lecture notes in control and information sciences 344 (2006), 810.
[5] Javier Franco- Contreras and Gouenou Coatrieux. "Robust watermarking of relational databases with ontology-guiin guiided distortion control". In: IEEE transactions on information forensics and security 10.9 (2015), pp. 1939-1952.
[6] Jianyang Gao and Cheng Long. "RaBitQ: Quantizing High-Dimensiont Vectors with Theoretical Error Bound for Approximate Nearest Neighbor Search". In: Proceedings of the ACM on Management of Data 2.3 (2024), pp. 1-27.
[7] Fabian Groh et al. "Ggnn: Graph-based gpu nearest neighbor search". In: IEEE Transactions
on Big Data 9.1 (2022). pp. 267-279.
[8] Bernal Jiménez Gutiérrez et al. "Hipporag: Neurobiologically inspired long-term memory for large language models". In: The Thirty-eighth Annual Conference on Neural Information Processing Systems. 2024.
[9] Ben Harwood and Tom Drummond. "Fanng: Fast approximate nearest neighbour graphs" In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2016, pp. 5713-5722.
[10] Xuanli He et "Cater: Intellectual property protection on text generation apis via conditional watermarks". In: Advances in Neural Information Processing Systems 35 (2022), pp. 5431- 5445.
[11] Jae-Pil Heo, Zhe Lin, and Sung- Eui Yoon. "Distance encoded product quantization for approx- imate k-nearest neighhor search in high-dimensional space" In: IEEE transactions on pattern analysis and machine intelligence 41.9 (2018), pp. 2084-2097.
[12] Donghui Hu et al. "Reversible database watermarking based on order- sieee-rreseriin encryption for data sharing". In: ACM Transactions on Database Systems 48.2 (2023), pp. 1-25.
[13] Huayang Huang. Yu Wu, and Qian Wang. "Robin: Robust and invisible watermarks for diffu- sion models with adversarial optimization". In: Advances in Neural Information Processing Systems 37 (2024), pp. 3937-3963.
[14] Elias Jääsaari, Ville Hyvönen, and Teemu Roos. "LoRANN: Low-Rank Matrix Factorization for Approximate Nearest Neighbor Search". In: Advances in Neural Information Processing Systems 37 (2024), pp. 102121-102153.
[15] Herve Jegou, Matthijs Douze, and Cordelia Schmid. "Product quantization for nearest neighbor search". In: IEEE transactions on puttern analysis and machine intelligence 33.1 (2010), pp. 117-128.
[16] Xinke Jiang et al. "Ragraph: A general retrieval- graph learning framework". In: Advances in Neural Information Processing Systems 37 (2024), pp. 29948-29985.
[17] Muhammad Kamran, Sabah Suhail. and Muddassar Farooq. "A robust, distortion minimizing technique for watermarking relational databases using once-for-all usability constraints". In:
IEEE Transactions on Knowledge and Data Engineering 25.12 (2013), pp.
[18] Laurent Amsaleg and Hervé Jégou. Datasets for approximate nearest neighbor search. http:
// corppss- - texmex. irisa. fr/ Accessed: 2024-08-03 2010.
[19] Yiming Li et al. "Untargeted backdoor watermark: Towards harmless and stealthy dataset
copyright protection". In: Advances in Neural Information Processing Systems 35 (2022),
pp. 13238-13250.
[20] Hongbin Liu et al. "Audiomarkbench: Benchmarking robustness of audio watermarking". In: Advances in Neural Information Processing Systems 37 (2024), pp. 52241-52265.
[21] Wanqi Liu et al. "EI-LSH: An carly-termination driven I/O efficient incremental c-approximate nearest neighbor search". In: The VLDB Journal 30 (2021), pp. 215-235.

---

[22] Zihan Liu et al. "Chatqa: Surpassing gpt-4 on conversational qa and rag". In: Advances in Neural Information Processing Systems 37 (2024), pp. 15416-15459.
[23] Yu A Malkov and Dmitry A Yashunin. "Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs". In: IEEE transactions pattern analysis and machine intelligence 42.4 (2018), pp. 824-836.
hte///dc/vvvviiiie md. Accessed: 2025-05-14. 2025. [25] James Jie Pan, Jianguo Wang, and Guoliang Li. "Survey of vector database management systems". In: The VLDB Journal (2024), pp. 1-25.
[24]
Milvus. Milvus, https: bttps://milvve
[26] Maikel L Pérez Gort, Claudia Feregrino Uribe, and Jyrki Nummenmaa. "A minimum distortion: High capacity watermarking technique for relational data". In: Proceedings the 5th ACM Workshop on Information Hiding and Multimedia Security. 2017, pp. 111-121.
[27]
pinecone. pinecone. https: /www///wwwww.. www pinecone. 10 learn/ a developers guide to
ann awgorilgttio terr///mm// Accessed: 2025-05-14 14. 2025.
[28] Na Ren et al. "Commutative encryption and watermarking based on SVD for secure GIS vector data". In: Earth Science Informatics 14 (2021), pp. 2229-2292292 2249-2263.
[29] Zhiwen Ren et al. "A Robust Database Watermarking Scheme That Preserves Statistical Characteristics.. In: IEEE Transactions on Knowledge and Data Engineering (2023).
[30] Radu Sion, Mikhail Atallah, and Sunil Prabhakar. "Rights protection for categorical data". In: IEEE transactions on knowledge and data engineering 17.7 (2005), pp. 912-926.
[31] Philip Sun et al. "SOAR: improved indexing for approximate nearest neighbor search". In: Advances in Neural Information Processing Systems 36 (2023), pp- 3189-3204.
[32] Yao Tian, Xi Zhao, and Xiaofang Zhou. "DB-LSH 2.0: Locality-sensitive hashing with query- based dynamic bucketing". In: IEEE Transactions on Knowledge and Data Engineering (2023).
[33] Michael Voigt, Bian Yang. and Christoph Busch. "Reversible watermarking of 2D-vector data". In: Proceedings the 2004 Workshop Multimedia and Security. MMSec '04. Magdeburg, Germany: Association for Computing Machinery, 2004, pp. 160-165 165. ISBN: 1581138547. DOI:
10. N0.1145//022431.1 1022459 URL: https: org/ 10 1145/ 1022431 1022459
[34] Ming Yang, Yuzheng Cai, and Weiguo Zheng. "CSPG: Crossing Sparse Proximity Graphs for Approximate Nearest Neighbor Search". In: Advances in Neural Information Processing Systems 37 (2024), pp. 103076-103100.
[35] Xi Zhao et al. "Towards efficient index construction and approximate nearest neighbor search in high-dimensional spaces". In: Proceedings of the VLDB Endowment 16.8 (2023), pp. 1979- 1991.
[36] Yihao Zheng et al. "Tabularmark: Watermarking tabular datasets for machine learning". In: Proceedings of the 2024 ACM SIGSAC Conference Computer and Communications Security. 2024, pp. 3570-3584.
[37]
Yifan Zhu et al. "Pivot selection algorithms in metric spaces: a survey and experimental study". In: The VLDB Journal 31.1 (2022), pp. 23-47.
12

---

A Hierarchical Navigable Small World
Hierarchical Navigable Small World (HNSW) [3 is an efficient graph-structured algorithm for ANN querying, aiming at accelerating the querying process of high-dimensional data, and it is the most dominant vector database index. The core ideas of HNSW include hierarchization, heuristic edge selection strategy, pruning strategy and greedy search. The query efficiency and result accuracy are balanced by quickly locating the query target in the high-level graph, and then searching in a refined way through the low-level graph.
HNSW constructs a small-world graph containing multiple layers. At the bottom layer, the graph contains all vectors and constitutes the edges of the graph by connecting each point to several vectors its neighborhood. As the number of layers of the graph increases, the number of vectors in each layer decreases, and the number of connected edges also decreases, creating a sparse graph structure.
Hierarchization:
Heuristic edge selection strategy: At each layer, HNSW uses a heuristic edge selection strategy to determine which vectors the newly added vector should be connected to. Let consstrutt E N be a parameter, that for a vector q to be added to HNSW, the e/Construcl near-neighbors of first found and then traversed in order of proximity q. Here it is important distinguish between the concepts of near-neighhor and neighbor; for a vector, a near-neighbor is a vector that close it, and a neighbor is a vector that connected to it and can be accessed by each other. The set of vectors already connected to q is denoted as S. For a near-neighbor of q. q will only connect to e if the distance from e q less than the distance from to any vector in S (i.e., Vo E S. p(e, q) < p)).
Pruning strategy: Let M N be a parameter that controls the upper limit of the number of edges for each vector. If the addition of q causes the vector e to have more edges than the upper limit, e must re-select its edges conform the edge limit. This upper limit set to 2M in the bottom layer of the graph, and M in the other layers.
For example, set e &Construct = 3. MM = 1. As shown in Figure 4(a) there already three vectors 1, 2, and in the HNSW graph, with two edges E(1, 2) and E(, Now add a vector q. where u(L, q) < 22(2 q) < p333 g). Follow these steps to determine whether connects to 1, 2, and 3: First, connect to 1, since q has no neighbors yet; do not connect to 2, because p(2. q) > (2, 1); connect to 3. because 3u33gg 9) p(3, 1). At this point, the heuristic edge selection for vector is complete, as shown in Figure 4(d) due to the addition of q, the number of edges for vector increases to 3, exceeding the upper limit 2M 2, vector 1 needs to prune some edges. The final HNSW graph is shown in Figure (()
(a) Before adding vector q.
(b) Connect
(c) Do not (d) Connect
(e) Vector
(f) Final sit-
q and 1.
connect q
and
reselect
uation after
and 2. since 3. since
neighbors. adding q.
d(2. > d(3.gg g)
d(2. d(3, 1).
Figure 4: Add a new vector g to HNSW using heuristic edge selection and pruning strategies.
Greedy search: The ANN search process in HNSW is described next. Suppose we have query vector 9. and the goal is to find the K closest vectors to g. The search process starts at the highest level of the entry vector of the HNSW and proceeds downward layer by layer. At each layer except the bottom layer, a greedy search is performed to find the closest vector to the query vector q at that layer, which serves as the entry vector for the next layer. At the bottom layer, nearest neighbor vectors) and C (the set of candidate vectors) need to be maintained, and the closest vector g from C is continuously selected to update W until C is empty or the vectors in C no longer closer to than any vectors in W. At this point the vectors kept in W are the nearest neighbors of q. When K 1, this process is known as greedy search.
sets W (the set of
13

---

B Pseudo-code
Algorithm 1: Watermark Embedding
Input: Vector database D, Watermark W, Strength 8, Random seed seed, Limiting factor f Watermarked vector database Dw
Output:
1 +- dimension of vector in L + &elengtth of the watermark W
3 Initialize L empty groups
Initialize random number generator with seed
5 Randomly generate the set of positive integers for V E D do
IDv < the identifier V
g H(IDv) mod L
Gg + GgGU
Cryptographic Mapping(V,I,,
11
now + ngw +1// Ng1 and 7g00 represent the number of 1-vector and 0-vector group 9, respectively, with initial value 0.
end
13 for
g + t do
W // W, is the g-th position of the watermark.
then 16
+ mar(0, (Gyl - ng1)
// Calculate the number vectors N'm that need to be modified.
17
Cv + randomly select num O-vector for modification
18
else
19
nm mar(0, |Ggl - ngo))
20
Cv + randomly select 7.m. 1-vector for modification
21
end
for V Cv do
23
Vw + Vector Modification(V,I.55.
end
end
Algorithm 2: Cryptographic Mapping
Input: Vector V, Set I, Limiting factor f, Dimension d
Output: Mapping bit
dn <- H(IDy) mod
while dw E I do
dw + (dw + 1) mod
end
5 b + the binary form of Va..
I t the length of b
7 i H(IDv) mod (1 x f) +1 mod
b[l @ (a1
14

---

Algorithm 3: Watermark Extraction
Input: Watermarked Database Dw, Watermark Length I., Random Seed seed Output: Extracted Watermark W
d dimensions of vector in Dw
Initialize random number generator with seed Randomly generate the set of positive integers I
4 for V E D do
IDv the identifier of V < H(IDv) mod L
+ Cryptographic Mapping( V f)
Rgw + ngw +
end
for g 0 L do
11
if gg 2 0g
then
12
W
13
else
14
Wg
15
end
16
end
W Wo Willlill W
C Stealth Vectors and Transparent Vectors
C.1
Stealth Vectors
According to the heuristic edge selection and pruning strategy HNSW, we believe that there are vectors with edges in the bottom layer, and such vectors are difficult to query. As shown in Figure 5[a) vector is chosen to be connected to vectors and 2, resulting in these two vectors having three 2, according to the pruning strategy, vectors and will reselect edges. If vector is far away from them, they will not connect to & as they already have two neighbors that are closer than q. Since does not have any edges, cannot be queried from any other vector as an entry vector.
edges both. If the upper limit of the number of edges is
To test whether such vectors exist, employ the widely-used vector dataset ANN SIFTIM (18), as an example. The experiment was conducted on PC equipped with an AMD Ryzen 5600G processor and implemented using Python and the Faiss library. Specifically, test whether the graph at the bottom the HNSW is divided into multiple connected components. When M 8 and ef /Construcl 100, there 12 connected components in the graph constructed by HNSW, yet 11 of them contain only one vector without edges. All the other vectors are the last biggest connected. This confirms the existence of vectors without edges.
before adding q
qis connected 1, 2
2 disconnect from q
before adding
qis connected
disconnect
2
from
(a) Vector has no edge. Figure 5: Two cases in which the vector q cannot be queried.
(b) The query is stuck in a local optimum.
Next we test whether these vectors are unsearchable. We queried the nearest neighbors using all vectors as query vectors and recorded the number of times each vector was queried. The edgeless vectors are never queried, which as expected. However, we also find that 40 vectors in the biggest connected component never queried. A possible reason is that the greedy algorithm used in
15

---

25
25
20
20
25
15
15
20
10
10
5
5
0
100
200
300
400
0
8
12
16
-2
-1
0
1
Average Edge Length
Number of Edges
Transparency Score(ts)
(a)
(h)
(c)
Figure 6: Experimental analysis of the effect of vector parameters transparency. The vertical axis
represents the average number of times queried.
the search process falls into local optimum, resulting in another class of unsearchable vectors that are difficuul to search for. As shown in Figure 5(b) due to the pruning strategy of HNSW, would only have neighbor When querying vector g, if the current vector is 1, the algorithm will consider 1 to be the query result and fail to find the real search result since for any neighbor of 1, uue, q) > p(1, q). From the fact that cannot be queried starting from all black nodes in the graph. This explains why there vectors in the main connected component that are not queried. It can be seen that the edge between q and is the key edge that determines whether q can queried or not, and when the key edge is pruned, q becomes difficult to be queried.
To summarize, the above properties of unsearchable vectors lead to a possible conclusion: vectors with fewer edges are more likely to be unsearchable due to the prune of key edges. Indeed, in the above test, the average degree of vectors that are never queried in the main connected component is 1.87, while the average degree of 1000 randomly chosen vectors is 8.92, which confirms this conclusion some extent. We define stealth vectors as follows.
Definition 4: (Stealth Vector). A vector V E D is stealth vector if
Ry = Ø.
(10)
Stealth vectors are indeed vectors whose nearest neighbor response domain is empty. According to the above analysis, there are two classes of stealth vectors: the first category is the no-edge vectors, which are away from other vectors, and the pruning strategy causes all neighboring vectors to be disconnected from them; and the second category is the vectors that have small number of edges, but their key edges are disconnected due to the pruming strategy, which makes these vectors unsearchable when searched using the greedy algorithm.
C.2 Transparent Vectors
Because stealth vectors are never queried, embedding watermarks in such vectors has the lowest embedding impact. However, stealth vectors not the most suitable candidates for watermarking since their distinct characteristics make them easily identifiable, resulting in the risk watermark remove by deleting all vectors that cannot be queried. To better balance the watermark transparency and robustness, we expand the range of carrier vectors available for selection with relatively low trans- parency requirements. These vectors named transparency vectors with the following definition:
Definition 5: (Transparency Vector). A vector V E D is f- transpparnyy vector if
Ry < t.
(11)
The transparency of a vector measured using the size of the nearest neighbor response domain; the smaller the nearest neighbor response domain is, the higher transparent the vector is. The Stealth vector is an extreme case of the transparent vector when f = 0.
Longer edges and fewer edges characterize stealth vectors, thus we have the following hypothesis: Vectors with longer and fewer edges are likely to transparent vectors. To validate this, a series of validation experiments were conducted. We take the average edge length of the vector at the bottom
16

---

layer of the graph as its average edge length. In order to examine the effect of the average edge length on the number of queries, we divide the range of average edge lengths and group the vectors within the same range into one class, and calculate the average number of queries for each class of vectors.
The experimental results are shown in Fig. ((a)] where the horizontal axis represents the average edge length and the vertical axis represents the average number of queries. It can be seen that the number of queries decreases with the increase of the average edge length, especially when the average edge length is extremely large, the number of queries is close to zero, indicating that the long edge vectors are rarely queried. Similarly, we verified the effect of the number of edges of a vector on the number of queries. We caleulated the average number of queries for vectors with the same number of edges. The experimental results are shown in Fig. 6(b) which shows that as the number of edges decreases, the average number of queries for the vector decreases.
The transparency parameter iss is constructed from the vector's average edge length and the number of edges e, serving to evaluate the frequency with which the vector is queried. The specific formula for calculating is provided in Equation (7) of the main text. A larger indicates either a greater average edge length fewer edges in the vector, and such vectors are typically queried less frequently. Based on this, it can be hypothesised that the transparency parameter is exhibits a negative correlation with the number of queries. To validate this hypothesis, we experimentally analysed the relationship between ts and query frequency. Specifically, we divided the range of ts into several intervals, grouped vectors within each interval into category, and calculated the average query frequency for each category. The experimental results are shown in Figure [6c] where the horizontal axis represents ts and the vertical axis denotes the average query count. It can be observed that as ts increases, the average query count decreases, confirming the hypothesis of a negative correlation between i.s and query frequency. Concurrently, Table in the main text lists the correlation coefficients between the average edge length 1, the number of edges e, and is with the number of queries. The results indicate that exhibits the highest absolute correlation coefficient with the number of queries, signifying the strongest relationship between the two. This demonstrates that employing is as metric for measuring the number of vector queries yields optimal effectiveness.
Additionally, to verify the stability of the transparency parameter ts under different HNSW configura- tions, calculated the Pearson correlation coefficient between the value of each vector and its actual query frequency for different parameter combinations. The results are shown in Table
Table 3: Correlation coefficients (p) between the query count and ts under different values of M and efConstruct.
M
efConstruct = 50
efConstruct = 100
efConstruct 150
M 4
-0.6969
-0.6886
-0.6885
M 8
-0.6978
-0.6732
-0.6603
M = 12
-0.6911
-0.6696
-0.6572
M 16
-0.6860
-0.6731
-0.6600
These results indicate that, under all parameter settings, ts maintains significant negative correlation with vector query frequency (Pearson coefficients all below -0.66), suggesting that ts is a stable and generalizable transparency metric that reliably guide carrier vector selection.
In this section, we confirm the existence of transparent vectors in HNSW and draw the following conclusions through analysis and experiments:
Some vectors that are far away from other vectors may have fewer edges or even no edges due to the edge pruning strategy, which ultimately makes them difficult to be searched.
The transparency of a vector can be measured by its transparency score ts. The larger ts is. the more likely it is highly transparent vector.
17

---

D
Comparison experiment
To conduct more comprehensive analysis of the impact of TVP on query behavior, conducted experiments and recorded the variance and maximum values of missed queries (MQ) and false queries (FQ) under each scheme. The results are shown in Table
Table Embedded impacts of different schemes.
Scheme
SCPW(var/max))29
TabularMark 36)
RS
TVP
AMQ 161.79/91.3
179.18 87.3
184.36 89.2
13.75 / 28.08
AFQ 187.54 100.9
184.87 101.6 189.57 / 104.7
12.39 / 30.15
As can be seen from Table the fluctuations MQ and FQ caused by TVP are significantly smaller than those caused by other methods, with both variance and maximum values being notably lower. This indicates that TVP more effectively controls query errors, not only achieving smaller average value but also minimizing the impact in worst-case scenarios, thereby demonstrating greater stability.
Since "transparent" vectors (i.e., vectors with relatively query frequencies) are common any dataset, we speculate that the TVP method has good cross-dataset generalization capabilities.
To validate this hypothesis, conducted extended experiments on two widely used deep learning (antoomi-------ommalll
(derived from VIBE, representing text summaries) and deeplb (a classic large-scale image vector dataset). The experimental parameters were consistent with those in the paper. We evaluated the average missed queries (AMQ) and average false queries (AFQ) caused by different watermark embedding schemes, with experimental results shown in Tables[]andd]]
embedding datasets:
Table 5: Embedded impacts of different schemes (Deeplb).
Scheme
SCPW[29)
TabularMark 36
RS
TVP
AMQ 13.96
13.38
13.42
3.17
AFQ
14.21
13.73
13.59
3.29
Table Embedded impacts of different schemes (arxiv-nomic- 76--nommazzdze))
Scheme
SCPW TabularMark 36)
RS
TVP
AMQ 13.51
13.83
13.75
4.26
AFQ
14.17
14.02
14.11
4.74
It can be observed that, on both datasets, the TVP scheme achieves significantly lower average missed query counts (AMQ) and average false positive query counts (AFQ) compared to other methods. This indicates that the strategy of prioritizing "transparent" vectors for modification can also reduce query errors on other datasets, thereby validating the cross-dataset generalization capability our method.
18

---

E Method Validation And Parameter Analysis Experiment
E.1 TVP Strategy Effectiveness
We evaluated the average number of missed queries (AMQ) and average number of false queries
(AFQ) introduced by TVP under various HNSW parameter settings (M E {4,8, 12, 16) and ef eCoostrruct E (50, 100, 150)). with the number retrieved neighbors fixed at k = 100. The results are summarized in Table
Table 7: Embedding effects of TVP under different parameter configurations
efConstruct
50 (AMQ (FQ)
100 (AMQ AFQ)
150 (AMQ / AFQ)
= 4
4.69 / 4.84
4.32/4.50
3.71 3.85
M 8
/
3.12
3.02 3.15
12
2.42 2.45
2.64 2.61
2.81 2.83
= 16 2.88 2.83
2.61 2.66
2.58 / 2.61
It can be seen that regardless of how the HNSW parameters change, the AMQ/AFQ values of TVP remain at a low level, indicating minimal impact on queries. This demonstrates that TVP has good adaptability different parameter configurations.
We conducted supplementary evaluation TVP's impact on standard approximate nearest neighbor (ANN) retrieval performance, focusing recall metrics for vector databases. Specifically, measured recall at & (R@k), which represents the proportion of true nearest neighbors successfully retrieved within the top h results. A higher R@k indicates greater retrieval accuracy. We compared the recall of the original, unembedded watermark database with that of the database after embedding watermarks using the TVP method, summarizing the results in Table g
Table 8: Changes in ANN recall rates before and after TVP watermark embedding
R R@k
10
30
50
100
Original
0.9933
0.9647
0.8918
0.8253
0.6847
TVP
0.9914
0.9633
0.8898
0.8219
0.6843
As shown in the table, recall remains nearly unchanged all k levels after watermark embedding. For instance, at R@l, recall decreased only from 0.9933 to 0.9914, 14, drop of less than 0.2%. Similarly, at R@100, the change was negligible, from 0.6847 to 0.6843. These results indicate that TVP has minimal impact on retrieval quality.
Table 9: Comparison of TVP and RS across different ANN index types
Index Type
TVP (AMQ AFQ)
RS (AMQ/AFF)
NSG
0.12 0.09
0.38 0.27
LSH
0.75 / 0.95
2.27 / 2.49
IVFFlat
1.46 / 1.52
3.57 / 3.81
IVFPQ
6.46 / 9.34
17.38 19.21
We further validated the generalization capability of the Transparent Vector Priority (TVP) strategy by applying to multiple Approximate Nearest Neighbor (ANN) index structures. We conducted experiments on four typical indexes: NSG, LSH, IVFFlat, and IVFPQ. By recording the query frequency of each vector, we prioritized embedding watermarks low-frequency vectors (TVP) and compared this approach with a baseline method that randomly selects vectors for embedding (RS). The experiments evaluated the performance of both schemes on average missed queries (AMQ) and average false queries (AFQ), with results shown in Table g
19

---

As shown in the table, TVP achieves lower AMQ and AFQ than RS across all index structures. This indicates that TVP not only applicable HNSW but also demonstrates excellent adaptability across index structures.
E.2 Embedding impact
The most critical parameter affecting the embedding effect is the threshold т, which determines the transparency requirement of the algorithm for the watermark carrier vectors, A smaller value of implies higher transparency requirement and fewer queries for the selected carrier vectors, which reduces the number of false queries and missed queries due to watermark embedding.
Under the premise of keeping other parameters unchanged, adjust the parameter th to study its effect on the watermark embedding effect. For each set value of th, the watermark embedding algorithm is executed, and the changes in the near-neighbor response domains of the carrier vectors before and after embedding are recorded, the number of false and missed queries are counted, and their averages are finally calculated.
Average Missed
Queries vs Threshold
Average Missed Queries
Average Query Count
15.0
Average
12.5
10.0
2.5
Thresheld (th)
Figure 7: The influence of T on embedding impact.
The experimental results are shown in Figure 7 where the horizontal axis represents the threshold r and the vertical axis represents the number of queries, and the two curves correspond to the average number of false queries (AFQ) and the average number of missed queries (AMQ), respectively. It be that when small, the values of AFQ and AMQ also small, which indicates that the impact of watermark embedding on the query results can indeed be kept at very low level when the transparency requirement is high. As th increases, AFQ and AMQ also increase synchronously, indicating that the th parameter can effectively regulate the impact of watermark embedding, which a key regulating factor. In addition, the figure presents an interesting phenomenon: the values of AFQ and AMQ are close to equal. We hypothesize that this is because the number of times the carrier vectors are queried does not change significantly before and after the watermark embedding, and thus the number of false queries and missed queries are roughly equal. Through experiments, we verify this speculation and explain the phenomenon the figure.
The parameter & indicates the proportion of vectors each group that can be correctly mapped to the corresponding watermark bit after embedding the watermark. Before embedding the watermark, the mapping results are usually more uniform across the groups, with equal proportions of I and 0 vectors. Therefore, if is large, it is necessary increase the proportion of vectors in certain category from 0.5 to a very high one, which will result in more vectors needing to be modified, thus having large impact the query results.
E.3 Watermark robustness
This section explores the effect of algorithm parameters on the robustness watermarking. Based on the threat model in Section 3.4 the attacker is aware of our watermarking method and thus will adopt an adaptive attack strategy of transparent vector prioritization, e.g., prioritizing the deletion of transparent vectors when deleting vectors to remove the watermark more effectively. All the attacks discussed in this section are such adaptive attacks.
An adaptive modification attack is an attempt by the attacker to remove the watermark by deleting certain percentage of transparent vectors. The larger the parameter is. the more vectors mapped to the corresponding watermark in each group after embedding
daptive Deletion Attack:
20

---

Im pmpac of Adaptive Deletion Bit Error Rate
Impact of Adaptive Deletion on Bit Error Rate
0.4
0.4
+=2.2
Btt ELEEro Rate (BER)
0.7
Ex Rate (BER)
0.9
0.8
0.3
T-
0.3
r-1
0.2
0.2
0.1
0.1
0.0
0.0
0,6 Deletion Proportion (p)
Proportion (p)
(a) Watermark Strength s.
(b) Transparency Threshold
Figure 8: Impact of Parameters on Watermark Robustness (Under Adaptive Deletion Attacks).
watermark, and theoretically, the more robust it should against the adaptive deletion attack. To verify this hypothesis, conducted experiments under the condition of r 0.5 for different combinations of adaptive deletion proportion and watermark strengths s, embedded the watermark using the parameter and then deleted the vectors of the most transparent p proportion, and then extracted the watermarks and computed the BER.
The experimental results are shown in Figure ((a) The horizontal axis represents the deletion proportion p. the larger p means the stronger the attack intensity; the vertical axis represents the BER, the larger the BER means the more extraction errors and the worse the robustness. The lines of different colors represent different 8 values.
The following points can be observed from the Figure ((a)
Performance under attack: for all curves, when the deletion proportion O, the BER is also O. This indicates that the watermark can extracted completely and accurately without attack, which proves that the basic embedding and extracting functions of this scheme are reliable.
Relation between Attack Strength and BER: as the deletion proportion p increases, the BER also rises, which indicates that adaptive deletion is indeed effective means of attack.
Effect of watermark strength on robustness: for the same strength of deletion attack, the larger the 8, the lower the BER. This indicates that larger values of s can enhance the robustness of watermarking, which is consistent with our speculation.
High robustness: when s=1, the BER always remains O, which means that the watermark can be extracted accurately no matter how strong the attack is. This result shows that the proposed scheme is very robust at and can meet the needs of application scenarios that require high robustness.
Next, discuss the impact of the transparency threshold the robustness. determines the requirement of the algorithm on the transparency of the carrier vectors. The smaller T is, the higher the transparency of the selected vectors, and the more obvious their features are, which easier to be recognized and suffer from accurate attacks under adaptive attacks. Therefore, the smaller r is, the less robust the watermark should be.
To verify this hypothesis, we conducted experiments under the condition of s = 0.7 for different combinations of adaptive deletion proportion p and thresholds th, embedded the watermark using the parameter 7, and then deleted the vectors of the most transparent proportion, then extracted the watermark and computed the BER.
The experimental results are shown in Figure 8(b) The horizontal axis represents the deletion proportion which indicates the strength of the attack; the vertical axis represents the BER. The lines of different colors represent different 7 values. It can seen that for the same deletion proportion, the smaller т is, the larger the BER is, which is consistent with our hypothesis. In addition, the curves of 0.2 and 7 = 0.4 almost overlap in the figure. This indicates that the setting of the complementary vectors plays role in the selection of the carrier vectors. When is too small and
21

---

80
Flase Queries
Flase Queries
60
70
50
Count
60
Count
40
50
30
40
20
10
0.25
0.50
0.75
0.25
0.50
0.75
Deletion Proportion (p)
Modification Proportion (p)
(a) Deletion Attack.
(b) Modification Attack.
Figure 9: Impact of Attacks on Query Results.
large, the number vectors satisfying the transparency requirement may be insufficient. this case, the algorithm, after prioritizing the high transparency vectors, will supplement the selection of some vectors with lower transparency. Therefore, although t is different, the selected vectors are similar in this case, and the BER are similar when facing adaptive deletion attacks.
According to the analysis of the threat model, an attacker needs to balance the effect of watermark removal with its impact on their own use of the database. To this end, we test the specific impact of adaptive deletion attacks on query results. The experiment sets the number of query neighbors k == 100 and measures the average number of query errors of all vectors before and after deleting varying proportions of vectors, and the experimental results are shown Figure (a)) The figure shows that the number of query errors rises significantly as the deletion proportion increases. When the deletion rate reaches 0.5, the average number of query errors is close to 50, which means that the proportion of query errors is close half of the total number of queries. At this intensity, the query result has been seriously distorted, and it difficult to meet the actual application requirements. Therefore, attackers usually do not choose such high intensity attack, and it can be inferred that the actual attack intensity is lower than the maximum value set by the experiment.
An adaptive modification attack is an attempt by the attacker to remove the watermark by modifying a certain percentage of transparent vectors, where the modifications are conducted on the partial dimension values of the vectors.
Adaptive Modification Attack:
Under the condition of threshold 0.5, conducted experiments for different combinations of watermark strength and modification proportion The specific steps include watermark embedding, performing modification attacks, and then extracting the watermark and recording the BER. The test results show that a significant bit error rate occurs only when the modification dimension reaches 30. Therefore, we set the number of modified dimensions for the modification attack
The experimental results are shown in Figure TO(a) The horizontal axis represents the modification attack strength, and the vertical axis represents the BER. The lines of different colors represent different values. It can be seen that for the same modification proportion, the larger the 8, the smaller the BER, indicating the higher robustness. This verifies that higher value of can significantly enhance the modification resistance of the watermark.
Next, we test the effect of the transparency threshold watermark robustness. Under the condition of watermark strength s = 0.7, we conducted experiments for different combinations of transparency threshold th and modification proportion p. The experimental steps also include watermark embed- ding, performing a modification attack, and then extracting the watermark followed by recording the BER.
The experimental results are shown in Figure 10(b) The horizontal axis represents strength the modification attack (i.e., modification proportion p) and the vertical axis represents the B RR. The lines of different colors represent different 7 values. It can seen that with the same modification proportion, the larger the the smaller the BER, indicating the higher robustness.
22

---

Impact of Adaptive Modification Bit Error Rate
Imp impact of Adaptive Modification on Bit Error Rate 0.4
+=0.2
0.4
Bit ELEorr Rate (BER)
Emerr Rate (BER)
0.8
0.3
0.3
T-1
0.2
0.1
0.0
0.0
0.8
Modification Propartion (p)
Modification Proportion (p)
(a) Watermark Strength
(b) Transparency Threshold
Figure 10: Impact of Parameters on Watermark Robustness (Under Adaptive Modification Attacks).
Finally, we evaluated the impact of this attack on query results. We measured the average number of query errors for all vectors before and after modifying different proportions of vectors. The results are shown in Figure 9(b As the proportion of modified vectors increases, the number of false queries increases rapidly. On the other hand, since the watermarking algorithm modifies only one dimension for each vector, and the attack needs modify multiple dimensions significantly impact watermark extraction, it indicates that the modification attack is more expensive to implement. Therefore, ensure database availability, attackers usually avoid high-intensity adaptive modification attack strategies, which limits the actual threat of the attack.
Shuffle Attack: Shuffle Attack is disturb the order between vectors and the correspondence between vectors and IDs. The watermark extraction of TVP does not depend on the order of vectors their original IDs, so this attack is effective for TVP.
Reconstructed Index Attack: Reconstruction indexing attack refers to reconstructing the indexes of vectors. Since the index construction process has certain degree of randomness, even if the same vectors are used to construct the index multiple times, the results will be different. If the watermark embedded in the index structure, reconstructing the index will lead to wrong watermark extraction. The TVP scheme does not depend on the index structure, so the reconstructed index attack is also ineffective for TVP.
By analyzing the experiments Section E.2 and Section E.3 we draw the following brief conclusions:
Transparency Threshold 7: the smaller is, the smaller the impact on query result is, but the robustness will become worse.
Watermark Strength s: the larger is, the stronger the robustness is, but more vectors need to be modified and the impact on query results increases.
23

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction provide a precise overview of the motivation and contributions of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of this work are discussed in the conclusion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]

---

Justification:
The hypothesis on the existence of edgeless vectors is verified by theoretical analyses and experiments.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The dataset used for the experiments, and the key parameters have been described.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
25

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer:
[Yes]
Justification:
I will provide all the code and datasets for the experiment.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ mripss.cc/ubllic/gui.eee CoodeSumeeieeeeee ssi iessonPolll molyicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: This paper describes the details of the experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: In papers in the field of watermarking, reporting the average of multiple experiments is sufficient. did not use error lines, confidence intervals, or statistical significance tests because they are not standard practice in the validation of my work.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
26

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
These are mentioned in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
We comply with the NeurIPS Code of Ethics in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: As a technology copyright protection and prevention of illegal distribution, watermarking inherently brings about positive social impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
27

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The creators of datasets from http://corrpss-txxmex... iri waived copyright rights, fulfilling proper crediting and license respect requirements.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
28

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
29

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM for what should or should not be described.
30


Reviews:
[{"review_id": "l9bJnzLX59", "reviewer": "Reviewer_7c4a", "summary": "The paper introduces Transparent Vector Priority (TVP) watermarking, a novel scheme designed for embedding watermarks into vector databases, specifically focusing on minimizing the impact on Approximate Nearest Neighbor (ANN) query results. Vector databases, which are crucial for machine learning tasks, are susceptible to security threats like unauthorized replication, and watermarking offers a solution for ownership authentication.\n\nThe core challenge addressed is that modifying vectors to embed a watermark can negatively affect ANN query performance. The authors observe that within widely used indexing structures like Hierarchical Navigable Small World (HNSW), some \"transparent\" vectors have significantly fewer edges or no edges at all and consequently exhibit much lower query frequencies.\n\nKey Contributions of this work are:\n\n-C1. Novel Watermarking Scheme: The paper proposes the Transparent Vector Priority (TVP) watermarking scheme specifically for vector databases, addressing the critical security need for ownership authentication.\n\n-C2. Minimizing Query Impact: It introduces a unique approach by identifying and prioritizing \"transparent\" vectors (low-query-frequency vectors with fewer or no edges in HNSW graphs) for watermark embedding, thereby minimizing the degradation of ANN query results.", "questions": "Q1- The proposed TVP watermarking scheme effectively leverages the characteristics of \"transparent\" vectors within the HNSW indexing structure. Have you explored, or do you have plans to investigate, how this scheme might be adapted or optimized for other widely used ANN indexing structures (e.g., IVF, tree-based methods, or different graph-based approaches) that may not exhibit the same 'transparent' vector properties as HNSW?\n\nQ2- Beyond the HNSW structure, how might the concept of prioritising low-impact vectors be identified and applied in other types of vector database architectures or even different data management systems where modifications are necessary but impact needs to be minimised?", "limitations": "L1- Robustness Against Sophisticated Attacks: The paper focuses on ownership authentication and minimising query impact. While all watermarking schemes face challenges, the specific robustness of TVP against various advanced adversarial attacks (e.g., subtle noise injection, vector perturbations, or targeted attempts to remove the watermark without destroying the data's utility) is not detailed as a primary focus of this work.\n\nL2- Subtle Impact on \"Transparent\" Vectors: Although \"transparent\" vectors have low query frequency, modifying them still alters the original data. In highly specialized or niche analytical tasks, even these seldom-queried vectors might hold unique information, and their alteration, however minimal, could theoretically have unforeseen, tiny impacts on very specific data analysis or rare queries.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "1. Strengths:\n\nS1- Addresses a Critical Security Need: The paper tackles the important and practical problem of ownership authentication in vector databases, which are increasingly vital for machine learning applications and susceptible to unauthorized replication.\n\nS2- Minimises Impact on Query Performance: A key strength is the innovative approach of identifying and prioritising \"transparent\" vectors (those with fewer or no edges and low query frequency in HNSW graphs) for watermark embedding. This strategic placement significantly reduces the negative impact on Approximate Nearest Neighbor (ANN) query results, which is often a major drawback of watermarking schemes.\n\nS3- Leverages HNSW Structure Intelligently: The scheme cleverly exploits the inherent characteristics of the widely used Hierarchical Navigable Small World (HNSW) indexing structure, demonstrating a deep understanding of how these databases operate.\n\n2. Weaknesses: Dependence on Specific Indexing Structure- While a strength, the method's reliance on the existence and characteristics of \"transparent vectors\" derived from HNSW's edge selection and pruning strategies suggests that its direct applicability or optimal performance might be limited to HNSW or very similar graph-based indexing structures. Its generalizability to other types of ANN indexes (e.g., IVF, tree-based, or pure hashing methods) is not explicitly discussed and might be challenging", "was_revised": true, "final_justification": "The paper addresses the novel challenge that embedding watermarks in vectors can degrade approximate nearest neighbor (ANN) query performance. Overall, basic idea is new and has promising strength. It provides new approach for the outstanding problem for good real impacts.\nIt observes that in popular indexing structures like Hierarchical Navigable Small World (HNSW): some “transparent” vectors, those with few or no edges, are queried much less frequently. Leveraging key innovation, the authors propose the Transparent Vector Priority (TVP) watermarking scheme for vector databases. TVP embeds watermarks preferentially in these low-query-frequency vectors to reduce the impact on ANN query accuracy. This approach aims to balance robust ownership authentication with minimal performance loss.", "rebuttal": "Dear Reviewer 7c4a: \n\nWe appreciate your insightful and valuable comments. We have carefully considered each comment and responded to them individually, and sincerely hope that our responses have adequately addressed your concerns. If so, we would be grateful if you could raise your score. If not, please let us know your further concerns, and we will continue to respond positively to your comments and improve our submission. \n\n## Weakness & Question 1.\n\n> **1. Is the TVP scheme applicable to other ANN indexes?**\n\nWe believe that the Transparent Vector Priority (TVP) concept has good generalizability, not only applicable to HNSW but also extendable to other mainstream ANN index structures (such as IVF, NSG, LSH, etc.), simply by redefining the transparency parameters according to the specific characteristics of the index.\n \nTo verify the universality of transparent vectors, we tested the frequency distribution of vector queries across multiple index structures and used the Gini coefficient to measure their imbalance. A higher Gini coefficient indicates a more uneven query frequency distribution. The experimental results are shown in Table 1.\n\n**Table 1**: Gini coefficient of vector query frequency under different ANN index structures.\n\n| Index | HNSW | IVFPQ | NSG | IVFFlat | LSH | \n|----------------|--------|--------|--------|---------|--------| \n| **Gini coefficient** | 0.3558 | 0.3683 | 0.4203 | 0.4132 | 0.6097 |\n\nAs shown in the table above, the Gini coefficients for other index structures are all higher than those for HNSW, indicating that the distribution of vector query frequencies is more uneven in these structures. This confirms that the transparent vector phenomenon is widely present in various index structures and not limited to HNSW.\n\nTherefore, the “transparent vector priority” approach can be adopted in different index structures to minimize query errors caused by watermark embedding.\n\nThis aligns with reviewer ieq6's perspective: “Although the paper states that the method is limited to HNSW, it appears to be applicable to other indexing structures as long as the method for determining the transparency parameter is modified.”\nIn the future, we will further explore how to design appropriate transparency parameters for other index structures, thereby extending the TVP concept to a broader range of index structures.\n\n## Question 2.\n> **2. Methods for identifying low-impact vectors and the potential of TVP concepts in different data management systems.**\n\nIn any vector database, a direct method for identifying low-impact (i.e., “transparent”) vectors is to count their query frequencies. However, this method incurs excessive computational overhead in large-scale systems. To efficiently identify low-impact vectors, we need to deeply understand the internal mechanisms of various index structures. For example, in HNSW, edge nodes have lower query frequencies, while in PQ, quantization errors and cluster density may influence query probabilities.\n\nBased on these structural characteristics, we can design more efficient heuristic strategies to estimate vector impact without enumerating queries. This is a challenging yet worthwhile direction for further research.\n\nMore broadly, the TVP approach can be viewed as a general data perturbation strategy applicable to other data management systems: prioritizing the modification of low-impact data without significantly affecting critical system performance (such as accuracy or availability). To systematically promote this strategy, we propose a general three-step framework:\n\n1.**Impact Quantification**: Define system-specific impact metrics (e.g., query frequency, access heat, node centrality);   \n2.**Low-Impact Target Identification**: Combine statistical or structural heuristics to identify low-impact data units;   \n3.**Targeted Modification**: Implement minimized modifications under system constraints to reduce side effects. \n\nWe believe this framework has good general applicability and plan to explore its implementation in more data systems in future work.\n\n## Limitation 1.\n\n> **3. Robustness against sophisticated attacks was not discussed in detail.**\n\nWe appreciate your comments on the stability assessment. We have conducted various adaptive attack experiments targeting TVP, including subtle perturbation injection (referred to as “adaptive modification attacks” in the paper), and quantified the extraction performance using BER (bit error rate). Due to space limitations, the results of these experiments are presented in Figure 10 of Appendix D.\n\nWe will move these experimental results to the main text in the revised version based on your review comments. Once again, we sincerely appreciate the reviewers' valuable feedback.\n\n## Limitation 2.\n\n> **4. Modifications to low-frequency but semantically critical vectors may introduce unforeseen minor impacts.**\n\nWe appreciate your forward-thinking question, which has helped us further consider the applicability of TVP in extreme scenarios.\n\nWe fully acknowledge that in certain specific application scenarios, modifying vectors with low query frequencies that possess unique semantic meanings or carry critical information may result in minor but unforeseen impacts.\n\nHowever, this issue is not unique to TVP but rather a common challenge shared by most data perturbation-based watermarking schemes. There is inherently a trade-off between security and usability.\n\nTo address this issue, this paper not only proposes the “Transparent Vector Priority” concept to minimize impact but also provides adjustable parameters for the extent of data modification to further control potential distortion.\n\nIn the future, we plan to integrate multi-dimensional information such as semantic labels and task sensitivity to further identify vectors that are “low-impact” in both the “access frequency” and “semantic importance” dimensions, thereby enhancing the controllability of TVP."}, {"review_id": "iOktms2RZ8", "reviewer": "Reviewer_Ncy6", "summary": "This paper introduces the problem of vector database watermarking. With the advent of vector embeddings as a prominent data modality, vector databases have become valuable digital assets. As a result, this paper is the first to extend the idea of watermarking, which has previously been well studied in the context of relational databases, to the new domain of vector DBs. In this paper, the authors propose two vector DB watermarking schemes: random selection (RS) and transparent vector priority (TVP). Random selection selects vectors randomly for perturbation and has the benefit of being agnostic to the specifics of the how the vector DB is implemented. However, RS has relatively poor \"embeddings impact\" as the perturbations can significantly degrade the quality of the vector DB results. In fact, Table 2 shows that RS performs worse than a method designed for tabular data and not vector DBs specifically. On the other hand, TVP focuses on watermarking for the specific case of the popular HNSW index. The authors propose a novel scheme for identifying \"transparent vectors\" -- those that are far away from others in the graph -- and seek to perturb those. In Table 2, the authors report that TVP outperforms other watermarking baselines for HNSW by a sizable margin. In summary, this paper is the first to introduce the problem of vector database watermarking and proposes two candidate solutions: random selection and transparent vector priority. The paper also discusses the tradeoffs between these watermarking approaches and presents metrics for assessing the quality of vector DB watermarks.", "questions": "Q1. Can you provide formal definitions of watermarking (and specifically a vector DB watermark)? *I would be willing to raise my evaluation score if the authors can revise their paper to present a formal definition and demonstrate how their proposed schemes fit within this definition.*\n\nQ2. Can you provide a formal definition of the threat model and include a (possibly informal) proof of security associated with your proposed watermarking schemes? I am particularly interested in seeing a more formal treatment of the adversary's capabilities and computational power? For example, would an adversary with unlimited computational power be able to break these watermarking schemes? *I would be willing to raise my evaluation score if the authors can provide a formal treatment of the threat model and provide a proof of security about to their proposed schemes in relation to an adversary with precisely defined capabilities.*\n\nQ3. Can you extend the watermarking evaluation to more datasets beyond SIFT 1M? I would particularly be interested in seeing results for deep learning based embedding datasets. [VIBE](https://github.com/vector-index-bench/vibe), [ANN Benchmarks](https://github.com/erikbern/ann-benchmarks) and [BigANN Benchmarks](https://github.com/harsha-simhadri/big-ann-benchmarks) might all be good places to obtain additional datasets. *I would be willing to raise my evaluation score if the authors can demonstrate that their proposed techniques generalize across a variety of datasets. In particular, I am curious to see if the logic behind node selection in TVP generalizes to additional datasets. I would also be curious to know of TabularMark is still on par or better than RS on additional datasets.*", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths\n\n1. [Originality] To my knowledge, this paper is the first to introduce the problem of vector database watermarking and thus this works stands out for blazing a trail and addressing an original problem. The authors successfully position their work as an evolution of prior literature on watermarking for datasets and relational databases and they introduce a corresponding new sets of evaluation metrics to measure watermarking impact on queries in this domain. \n\n2. [Significance] This paper introduces a potentially high-impact problem and presents the first solutions to tackle this challenge. Given the impact that the first relational database watermarking papers have had in both industry and in follow-up academic work, I see this paper has having the potential to be a pioneering work in establishing a new research area. \n\n\nWeaknesses\n\n1. [Clarity] While I am enthusiastic about the potential for this paper to establish a new, high-impact research direction, I feel the execution in the current version of the paper can be improved considerably. First and foremost, the paper lacks clarity in several places. Perhaps most crucially, the threat model introduced in Section 3.3 is vague and lacks precise definitions. Moreover, while the components of a watermark are described in Section 4.1, I don't believe there is a formal definition of watermarking included in the paper. Beyond just orienting readers to the nature of the problem, I think these formal definitions are critical to be able to judge the quality of the proposed watermarking schemes presented in the paper. For example, in Section 3.3, the authors mention that their threat model assumes attackers are \"not too strong\" but it is unclear what exactly this means. Is the attacker computationally bounded in some manner (e.g. it can run only in polynomial time)? What would then be the time complexity of an attacker trying to recover the watermark? I think this paper would benefit greatly from a revision that introduces formal definitions of the key concepts behind a watermark and then organizes the evaluation of the paper in relation to these definitions. I believe this change would improve the clarity of this work quite a bit. \n\n2. [Quality] In addition to improving the quality of the paper's presentation, I think the authors could also make this submission stronger by either improving the efficacy of their proposed watermarking schemes, or presenting a more comprehensive case that their schemes are viable solutions to the vector DB watermarking problem. For example, the authors present random selection (RS) as a universal method that can be applied to any vector DB regardless of how the index is implemented. But Table 2 seems to suggest that a tabular watermark can match or even exceed the performance of RS. It would be interesting to understand why this is the case. Does TabularMark work as well as RS on other datasets beyond SIFT 1M or is this a one-off result. Moreover, I think it is critical for the authors to evaluate their technique on additional vector datasets, especially those with embeddings derived from modern deep learning models (SIFT is not a deep learning based dataset). Furthermore, while TVP attains the best performance when compared to the baseline methods in Table 2, it is unclear if result this generalizes to other datasets, or even if the transparent vector technique proposed by the authors extends to other datasets. I think this is a critical question to address. Another weakness of TVP is that the technique is presented as an approach highly specialized to HNSW, which limits its impact. Could TVP work for other navigable small world graph indexes like Vamana/DiskANN or NSG? This would give me more confidence in the generality of the technique. With a more comprehensive experimental evaluation, I believe this paper can be much stronger.", "was_revised": true, "final_justification": "Based on the authors' responses during the rebuttal and discussion period, I will raise my score to a 4 and will advocate for acceptance of this paper. I choose not to assign a higher score at this time because I think the paper would still benefit from a more comprehensive evaluation on more benchmark datasets (at least 5-6 in total), and I hope the authors can consider adding these additional results to the camera-ready version of the paper.\n\nI congratulate the authors on their strong efforts to address reviewer concerns during the rebuttal and discussion period. I think their proposed additions to the paper (formal definitions of watermarking and the threat model, discussions around the adversarial robustness of their AMQ and AFQ metrics, and more thorough experiments on additional datasets and indexes) make the paper much, much stronger than their initial submission. Thus, I am happy to recommend acceptance of this paper. I believe the idea of vector database watermarking is a new and timely contribution to the community and has the potential to inspire additional research in this direction.", "rebuttal": "Dear Reviewer Ncy6:\n\nWe sincerely appreciate the insightful and constructive feedback provided by the reviewers, which has been crucial in helping us improve the quality of our work. We are particularly grateful for your recognition of the originality and potential impact of this paper. As you pointed out, this work presents the first dedicated scheme and evaluation metrics, laying the foundational framework for vector database watermarking, which may open up a new research direction.\n\nIn response to your valuable suggestions, we have made the following revisions: we have provided formal definitions of watermarks and threat models (see responses to Questions 1 and 2), and expanded the experimental evaluation to two additional large-scale datasets to further demonstrate the generality and effectiveness of our method (see response to Question 3 and the newly added Tables 1-2).\n\nWe hope these modifications adequately address your concerns. We sincerely hope you will consider increasing your score, as your support is crucial for advancing this research direction.\n\n## **W1 & Q1.** \n> **Can you provide a precise definition of a watermark?**\n\nThank you for raising this important question. Below, we provide the **formal definition of watermarks in vector databases**. We will incorporate this definition into the revised manuscript if deemed appropriate.\n\n### **1. Watermarking Algorithms**\n\nThe watermark $W \\in \\\\{0, 1\\\\}^L$ is a binary string that can be embedded into digital carriers for copyright verification.\n$\\mathcal{D} = \\\\{V^1, V^2, \\cdots, V^n\\\\}$ is a vector database containing $n$ $d$-dimensional vectors.\n A watermarking scheme for vector database $\\mathcal{D}$ consists of the following two algorithms:\n\n* **Embedding Algorithm**:  \\$\\mathsf{Em}(\\mathcal{D}, W, \\theta\\_1) \\rightarrow \\mathcal{D}\\_w\\$  \n**Input**: the original database \\$\\mathcal{D}\\$, the watermark \\$W\\$, and the embedding parameter $\\theta_1$ (which includes encryption parameters and adjustment parameters for controlling embedding impact and robustness).  \n**Output**: the watermarked database \\$\\mathcal{D}\\_w\\$.\n\n* **Extraction Algorithm**:  \\$\\mathsf{Ex}(\\mathcal{D'}, \\theta\\_2) \\rightarrow W’\\$  \n**Input**: a database \\$\\mathcal{D'}\\$ that may have been modified and extraction parameters \\$\\theta\\_2\\$ (which includes decryption parameters and recovery parameters for ensuring accurate watermark extraction).  \n**Output**: the extracted watermark \\$W’\\$.\n\nWatermarking schemes have two major pursuits: low embedding impact and high robustness. The evaluation criteria of these two properties for vector database watermarking are presented below.\n\n### **2. Embedding Impact**\n\nThe embedding algorithm $\\mathsf{Em}(\\cdot)$ selects a set of vectors—called the carrier vector set $\\mathbf{C_V} \\subseteq \\mathcal{D}$ —whose elements may be modified to encode the watermark.\nThese modifications may affect ANN queries. To quantify this impact, we introduce two metrics (detailed definitions in sections 5 and 7) :  \n\n**Average Missed Query (AMQ)**: Number of true neighbors lost after embedding.  \n**Average False Query (AFQ)**: Number of incorrect neighbors newly introduced after embedding.\n\nLower AMQ and AFQ values indicate smaller embedding impact and higher transparency.\n\n### **3. Robustness**\n\nAfter obtaining the watermarked database $\\mathcal{D}\\_w\\$, an attacker may attempt to remove the watermark by modifying the data, thereby tampering with the database to $\\mathcal{D}'\\$, which may cause errors in watermark extraction. The robustness of the watermark can be evaluated using the bit error rate (BER):\n\n$$\n\\text{BER} \\triangleq \\frac{\\sum_{i=1}^L W_i \\oplus W_i'}{L}\n$$\n\nThe lower the BER, the higher the robustness against adversarial interference.\n\nOur proposed TVP scheme fits within this framework: it selects carrier vectors with minimal query impact , thereby minimizing AMQ and AFQ. Simultaneously, it ensures robust extraction under common perturbations, achieving low BER. \n\n\n## **W1 & Q2.** \n> **Define threat model and explain the meaning of \"not too strong\" in Section 3.3.**\n\nWe appreciate your interest in the threat model and would like to clarify its definition here.\n\nThe core threat we focus on is watermark removal attacks, where attackers attempt to destroy watermarks by deleting or disturbing part of the vector, thereby evading ownership verification. The essence of such attacks is not to crack a certain encryption mechanism, and their effectiveness does not depend on the attacker's computing resources.  Therefore, the statement in the threat model that “**the attacks are usually not too strong**” does not refer to limitations on the attacker's **computational power**, but rather to limitations on the **intensity** of the attacker's attacks.\n\nAttackers are also users of the vector database, so while attempting to remove the watermark, they must also maintain the database's availability. If overly intense attack methods are employed, it may result in severe degradation of approximate nearest neighbor (ANN) query results, rendering the database virtually unusable.\n\nWe have demonstrated the relationship between attack intensity and query errors in Appendix D (Figure 9): when the proportion of vectors deleted or altered by attackers reaches 50%, query errors also approach 50%. This indicates that once attackers exceed a certain modification threshold, the database's functionality becomes unsustainable. Therefore, we reasonably assume that attackers will not employ overly strong attacks, forming the fundamental premise of our threat model.\n\nTo eliminate ambiguity, we will revise the description of the threat model in the paper. Specifically, we will clarify that “not too strong” refers to attack intensity restrictions, rather than computing power restrictions. Based on our experimental results, we will also suggest a rough upper bound for attack intensity—for example, modifying more than 30% of vectors may already lead to unacceptable query degradation. This revision will enhance the rigor and clarity of our threat assumptions.\n\n## **W2 & Q3.**\n> **Experiments on other datasets.**\n\nWe thank you for your valuable suggestions regarding the generalization of the experiments.\n\nSince “transparent” vectors (i.e., vectors with relatively low query frequencies) are common in any dataset, we speculate that the TVP method has good cross-dataset generalization capabilities.\n\nTo validate this hypothesis, we conducted extended experiments on two widely used deep learning embedding datasets: arxiv-nomic-768-normalized (derived from VIBE, representing text summaries) and deep1b (a classic large-scale image vector dataset). The experimental parameters were consistent with those in the paper. We evaluated the average missed queries (**AMQ**) and average false queries (**AFQ**) caused by different watermark embedding schemes, with experimental results shown in Tables 1 and 2.\n\n\nTable 1: Experimental results on the Deep1b dataset\n\n| Scheme | SCPW | TabularMark | RS | TVP |\n |------------|------|-------------|-----|------|\n | **AMQ** | 13.96| 13.38 | 13.42| **3.17** | \n| **AFQ** | 14.21| 13.73 | 13.59| **3.29** |\n\nTable 2: Experimental results on the arxiv-nomic-768-normalized dataset\n| Scheme | SCPW | TabularMark | RS | TVP | \n|------------|------|-------------|-----|------| \n| **AMQ** | 13.51| 13.83 | 13.75| **4.26** | \n| **AFQ** | 14.17| 14.02 | 14.11| **4.74** |\n\nIt can be observed that, on both datasets, the TVP scheme achieves significantly lower average missed query counts (AMQ) and average false positive query counts (AFQ) compared to other methods. This indicates that the strategy of prioritizing “transparent” vectors for modification can also reduce query errors on other datasets, thereby validating the cross-dataset generalization capability of our method.\n\nAdditionally, we note that on both datasets, TabularMark performs very similarly to the random selection (RS) method, with little difference between the two in terms of AMQ and AFQ.\n\n## Weakness 2.\n\n> **Is the TVP scheme applicable to other ANN indexes?**\n\nWe believe that the Transparent Vector Priority (TVP) concept has good generalizability, not only applicable to HNSW but also extendable to other mainstream ANN index structures (such as IVF, NSG, LSH, etc.), simply by redefining the transparency parameters according to the specific characteristics of the index.\n \nTo verify the universality of transparent vectors, we tested the frequency distribution of vector queries across multiple index structures and used the Gini coefficient to measure their imbalance. A higher Gini coefficient indicates a more uneven query frequency distribution. The experimental results are shown in Table 3.\n\nTable 3: Gini coefficient of vector query frequency under different ANN index structures.\n\n| Index | HNSW | IVFPQ | NSG | IVFFlat | LSH | \n|----------------|--------|--------|--------|---------|--------| \n| **Gini coefficient** | 0.3558 | 0.3683 | 0.4203 | 0.4132 | 0.6097 |\n\nAs shown in the table above, the Gini coefficients for other index structures are all higher than those for HNSW, indicating that the distribution of vector query frequencies is more uneven in these structures. This confirms that the transparent vector phenomenon is widely present in various index structures and not limited to HNSW.\n\nTherefore, the “transparent vector priority” approach can be adopted in different index structures to minimize query errors caused by watermark embedding.\n\nThis aligns with reviewer ieq6's perspective: “Although the paper states that the method is limited to HNSW, it appears to be applicable to other indexing structures as long as the method for determining the transparency parameter is modified.”\nIn the future, we will further explore how to design appropriate transparency parameters for other index structures, thereby extending the TVP concept to a broader range of index structures."}, {"review_id": "aPhH8pJAOu", "reviewer": "Reviewer_ir5J", "summary": "This paper introduces a watermarking scheme for vector databases, focusing on addressing the security threat of unauthorized replication. The core of the scheme is the Transparent Vector Priority (TVP) strategy, which leverages the characteristic of the Hierarchical Navigable Small World (HNSW) indexing structure where some vectors have few or no edges and thus low query frequencies. By prioritizing watermark embedding in these \"transparent\" vectors, TVP minimizes the impact on Approximate Nearest Neighbor (ANN) query results. Experiments show that TVP reduces missed and false queries by about 75% compared to existing schemes. The paper's contributions include proposing the first vector database watermarking scheme, defining metrics to quantify embedding impact, and optimizing the scheme via transparent vector prioritization to balance query performance and watermark robustness.", "questions": "1. May I ask if the phrase “Presenting RS” summarized in the Contributions section is a typo? The main technical contribution of this paper should be the TVP strategy.\n2. Could the authors provide comparisons with more methods or evaluate the model's performance on additional datasets?", "limitations": "1. The authors should improve the writing and structure of the paper to make it more readable and easier to understand.\n2. See in Weakness.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. Proposing the first kind vector database watermarking scheme (RS) fills a gap in the research field.\n2. Defining missed queries and false queries to measure the impact of watermark embedding on ANN queries is a precise and necessary step. \n3. The TVP scheme shows a smart optimization approach. By leveraging the characteristics of the HNSW index structure (identifying vectors with low query frequency as \"transparent vectors\") to minimize the impact of watermark embedding, it addresses a key concern in watermarking—preserving the normal operation of the database. \nWeakness:\n1. The allocation of space in the paper is problematic: the sections Basic Methodology: Random Selection and Preliminaries are somewhat lengthy, which results in some important ablation studies being relegated to the appendix. There is still some content overlap between the main text and the appendix, such as Table 1 and Table3\n2. The experimental validation is insufficient, as the experiments were conducted on only a single dataset. Moreover, the two baseline methods used for comparison were not specifically designed for vector datasets, which introduces a certain degree of unfairness.", "was_revised": true, "final_justification": "The authors' response addressed my concerns. After carefully considering both the rebuttal and the comments from other reviewers, I have decided to raise my score to 4.", "rebuttal": "Dear Reviewer ir5J:\n\nWe appreciate your insightful and valuable comments. We have carefully considered each comment and responded to them individually, and sincerely hope that our responses have adequately addressed your concerns. If so, we would be grateful if you could raise your score. If not, please let us know your further concerns, and we will continue to respond positively to your comments and improve our submission.\n\n## **Weakness 1 & Limitation 1.**\n> **The allocation of space in the paper is problematic.**\n\nThank you for your comment. We will rearrange the length of each section to ensure that the core content of each section is presented more clearly and concisely. In particular, for the sections on the “Random Selection (RS)” method and Preliminaries, we plan to streamline the content of Section 3.1 Approximate Nearest Neighbor (ANN) and Section 3.2 Hierarchical Navigable Small World (HNSW), moving more background information to the appendix. Additionally, we will explore the possibility of merging the RS and TVP schemes into a single section to free up more space in the main text for presenting more comprehensive ablation experiment results. Furthermore, we will ensure that there is no repetition between the main text and the appendix. Once again, thank you for your careful review.\n\n## **Weakness 2 & Question 2.**\n> **The experimental validation is insufficient, as the experiments were conducted on only a single dataset.**\n\nWe thank your valuable suggestions regarding the generalization of the experiment.\n\nSince “transparent” vectors (i.e., vectors with relatively low query frequencies) are common in any dataset, we speculate that the TVP method has good cross-dataset generalization capabilities.\n\nTo validate this hypothesis, we conducted extended experiments on two widely used deep learning embedding datasets: arxiv-nomic-768-normalized (derived from VIBE, representing text summaries) and deep1b (a classic large-scale image vector dataset). The experimental parameters were consistent with those in the paper. We evaluated the average missed queries (**AMQ**) and average false queries (**AFQ**) caused by different watermark embedding schemes, with experimental results shown in Tables 1 and 2.\n\n\nTable 1: Experimental results on the Deep1b dataset\n\n| Scheme | SCPW | TabularMark | RS | TVP |\n |------------|------|-------------|-----|------|\n | **AMQ** | 13.96| 13.38 | 13.42| **3.17** | \n| **AFQ** | 14.21| 13.73 | 13.59| **3.29** |\n\nTable 2: Experimental results on the arxiv-nomic-768-normalized dataset\n| Scheme | SCPW | TabularMark | RS | TVP | \n|------------|------|-------------|-----|------| \n| **AMQ** | 13.51| 13.83 | 13.75| **4.26** | \n| **AFQ** | 14.17| 14.02 | 14.11| **4.74** |\n\nIt can be observed that, on both datasets, the TVP scheme achieves significantly lower average missed query counts (AMQ) and average false positive query counts (AFQ) compared to other methods. This indicates that the strategy of prioritizing “transparent” vectors for modification can also reduce query errors on other datasets, thereby validating the cross-dataset generalization capability of our method.\n\n\n## **Weakness 2.**\n> **Moreover, the two baseline methods used for comparison were not specifically designed for vector datasets, which introduces a certain degree of unfairness.**\n\nSince watermarking in vector databases is still an emerging topic, there are currently no mature baseline methods specifically designed for this scenario. Therefore, we selected high-quality methods that are representative of the database and dataset watermarking fields in recent years as comparison objects.\n\nThese methods were originally designed for other data models and did not take into account the structural characteristics (e.g., index structure) and usage scenarios (e.g., ANN queries) of vector databases. Therefore, they may not achieve optimal performance in our experimental setup.\n\nHowever, this result itself highlights a critical issue: existing watermarking methods are difficult to directly apply to vector databases, and their performance in this scenario has obvious shortcomings. This phenomenon indirectly validates the necessity and innovation of our work, namely: there is an urgent need to design specialized watermarking methods tailored to the unique structure and application scenarios of vector databases, which is precisely the core contribution of the TVP and other schemes proposed in this paper.\n\n## **Question 1.**\n> **May I ask if the phrase “Presenting RS” summarized in the Contributions section is a typo? The main technical contribution of this paper should be the TVP strategy.**\n\nThank you for your careful correction. “Presenting RS” was indeed a typo. The main technical contribution of this paper should be the TVP strategy. We will correct this in the revised version."}, {"review_id": "YwPcV9SDqq", "reviewer": "Reviewer_ieq6", "summary": "The proposed method deals with embedding watermark information into feature vectors to prevent unauthorized replication of the vector DB.\nEach data point belongs to one of L groups and is converted to a binary value by cryptographic mapping.\nThen the ratio of 1-vectors to 0-vectors in the g-th group determines the g-th value of the watermark code.\nIf the watermark code is pre-defined, a portion of bits in $n_m$ vectors must be flipped to match the ratio of 0- or 1-vectors to the watermark code.\nThe main contribution of the proposed method is that it selects the data to be flipped based on their expected lower search frequency, rather than choosing them randomly.", "questions": "[Question 1]\nAs mentioned in Weakness 1, this method inevitably introduces performance degradation. \nHowever, since the paper does not use standard ANN evaluation metrics such as R@1, it is difficult to quantify the extent of this degradation. \nThe authors should report these metrics.\n\n[Question 2]\nAs mentioned in Weakness 2, it would be beneficial to provide the variance and maximum values of MQ and FQ instead of the average.\nAdditionally, the paper should show the difference between queries whose first nearest neighbor is a modified data point and those whose first nearest neighbor is an unmodified data point.\n\n[Question 3]\nAs mentioned in Weakness 3, bit flips can completely alter the feature information when used together with VQ techniques like product quantization. \nSince HNSW and VQ techniques are often used in combination, an ablation study on this case should be provided.\n\n[Question 4]\nIf the watermark code S is chosen according to the original cryptographic value distribution, wouldn’t it be possible to skip the modification step?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n\n1. The proposed method appears to be robust against deletion attacks because altering a specific g-th watermark bit requires changing the majority in the g-th group, which cannot be achieved by deleting only a few data points.\n\n2. The paper provides a clear introduction to the important yet underexplored area of preventing unauthorized replication in vector databases.\n\n3. Although the paper states that the method is limited to HNSW, it appears to be applicable to other indexing structures as long as the method for determining the transparency parameter is modified.\n\nWeaknesses\n\n1. However, the method inherently modifies the original feature vectors, which inevitably leads to performance degradation.\nIt would be more ideal to embed watermark information without altering the original feature vectors, such as by using the connectivity of the ANN graph or the indices of nodes selected in the upper layers of HNSW.\n\n2. The modifications are applied to vectors that are expected to be searched less frequently, so the overall performance degradation is minimal. \nHowever, if a query with the modified vector as its first nearest neighbor is provided as input, significant performance degradation can occur.\n\n3. The impact of bit flips during the modification stage is highly concerning when used together with VQ.\nWhile bit flips have little effect on data measured by Hamming distance, they have a much greater impact on data measured by L2 distance.\nMoreover, when each bit of the feature refers to a pre-defined codebook index, as in VQ, this impact is further amplified.", "was_revised": true, "final_justification": "The authors provided additional experiments that addressed the concerns for Q1 and Q2.\nA detailed explanation for Q4 was helpful for understanding, and although Q3 remains unresolved, it is not critical enough to warrant rejection.\nTherefore, I am raising my score from 3 to 4.", "rebuttal": "Dear Reviewer ieq6:\n\nWe sincerely appreciate your insightful and constructive feedback. In response to your comments, we conducted a series of additional experiments and analyses, including evaluating standard ANN recall metrics (e.g., R@1), the variance and maximum value of query errors, and the compatibility of our method with vector quantization (VQ) technology.\nThese efforts reflect our deep respect for your feedback. If our modifications meet your expectations, we would be grateful if you could consider raising your rating. If there are any further questions or concerns, we welcome your continued suggestions, and we will actively work to further improve the paper.\n\n## **W1 & Q1.**\n> **Modifying vectors will result in performance degradation. Standard ANN evaluation metrics such as R@1 should be added.**\n\nWe have conducted a supplementary assessment of the impact of TVP on standard ANN metrics, recording the recall rates of the vector database without watermarks and after embedding watermarks. The experimental results are shown in Table 1.\n\nTable 1: Changes in ANN recall rates before and after TVP watermark embedding\n| R@k | 1 | 10 | 30 | 50 | 100 | \n|-------|-------|-------|-------|-------|-------|\n | Original | 0.9933 | 0.9647 | 0.8918 | 0.8253 | 0.6847 | \n| TVP | 0.9914 | 0.9633 | 0.8898 | 0.8219 | 0.6843 |\n\nIt can be seen that the impact of TVP on all recall metrics is very limited, with minimal performance degradation.\nWe completely understand your concern about “performance loss due to embedding.” This is a common issue faced by most perturbation-based watermarking schemes, not unique to TVP. However, unlike the “using the connectivity of the ANN graph” method, perturbation-based watermarking offers greater robustness, making it difficult for attackers to remove the watermark through simple index reconstruction. This provides a more reasonable trade-off between security and practicality.\n\n## **W2 & Q2.**\n> **As mentioned in Weakness 2, it would be beneficial to provide the variance and maximum values of MQ and FQ instead of the average.**\n\nThank you for your valuable suggestions. To conduct a more comprehensive analysis of the impact of TVP on query behavior, we conducted experiments and recorded the variance and maximum values of missed queries (MQ) and false queries (FQ) under each scheme. The results are shown in Table 2.\n\nTable 2: Variance/Maximum Values of MQ and FQ for Different Schemes\n\n|  | SCPW (Var / Max) | TabularMark    | RS             | TVP               |\n| -------- | ---------------- | -------------- | -------------- | ----------------- |\n| **MQ**   | 161.79 / 91.3    | 179.18 / 87.3  | 184.36 / 89.2  | **13.75 / 28.08** |\n| **FQ**   | 187.54 / 100.9   | 184.87 / 101.6 | 189.57 / 104.7 | **12.39 / 30.15** |\n\nAs can be seen from the table, the fluctuations in MQ and FQ caused by TVP are significantly smaller than those caused by other methods, with both variance and maximum values being notably lower. This indicates that TVP more effectively controls query errors, not only achieving a smaller average value but also minimizing the impact in worst-case scenarios, thereby demonstrating greater stability.\n\n## **W2 & Q2 Follow-up.** \n> **Although the overall impact is small, performance may degrade significantly when the modified vector becomes the top-1 nearest neighbor. Comparison results between such queries and regular queries should be provided.**\n\nThank you for your insightful comments. We fully agree that analyzing specific queries where the Top-1 nearest neighbor is the modified vector can provide a deeper understanding of potential performance degradation.\n\nTo address this issue, we conducted an additional experiment, dividing all queries into two groups:\n\n* **M group (modified)**: Queries where the Top-1 nearest neighbor is the modified vector;\n* **U group (unmodified)**: Queries where the Top-1 nearest neighbor is the unmodified vector.\n\nWe then compared the recall rates (R\\@k) of the two groups. The results are shown in table 3.\n\nTable 3: Nearest neighbor query performance of the two vector groups.\n\n| k   | Modified R@k | Unmodified R@k | Difference |\n| --- | ------------- | --------------- | ---------- |\n| 1   | 0.9545        | 0.9998         | 0.0453     |\n| 10  | 0.9682        | 0.9692          | 0.0010     |\n| 30  | 0.9000        | 0.8940          | -0.0060    |\n| 50  | 0.8336        | 0.8251          | -0.0085    |\n| 100 | 0.6914        | 0.6847          | -0.0066    |\n\n\nAlthough Group M shows a slight decrease in performance at R@1 (approximately 4.5%), its performance rapidly converges with Group U as k increases. It is worth noting that only 4.61% of queries belong to Group M, indicating that after adopting the “transparent vector priority” strategy, very few modified vectors become the first nearest neighbor. Therefore, even though there is a certain performance difference at R@1, its impact on the overall retrieval effectiveness remains limited.\n\n## **W3 & Q3.**\n> **As mentioned in Weakness 3, bit flips can completely alter the feature information when used together with VQ techniques like product quantization. Since HNSW and VQ techniques are often used in combination, an ablation study on this case should be provided.**\n\nThank you for pointing out the potential serious implications of bit flipping in a vector quantization (VQ) environment. This is a critical issue that has prompted us to further explore the compatibility between watermark embedding and VQ technology.\n\nWe understand your concerns as follows: In vector databases using VQ techniques such as product quantization (PQ), each subvector is typically encoded as a codeword (i.e., an index in the codebook), which corresponds to a specific centroid vector. If we directly flip the bits of these discrete indices, although the modification seems small from the perspective of Hamming distance, the large Euclidean distance between the corresponding centroids of adjacent indices will lead to significant L2 distance deviation, which may seriously affect the ANN query results. Therefore, simple bit flipping is no longer applicable in this scenario.\n\nWe agree with this view and recognize that in vector databases combining VQ technology, watermark embedding should avoid direct bit-level perturbations. We have an initial idea for this:\nWhen embedding watermarks, we can treat each dimension's codebook as a candidate set, first read the centroid vector corresponding to the current codeword, and then sort the other candidate centroid vectors in ascending order of their L2 distances from the current codeword. Among these candidates with closer distances, we can select an alternative codeword that both maps to the target watermark bit and is as close as possible to the original center vector, thereby minimizing the impact of modifications. This is a “minimum perturbation” watermark embedding strategy specifically tailored for scenarios combining VQ technology.\n\nAdditionally, we believe that since bit flipping is not applicable to VQ-encoded vectors, conducting ablation experiments in this environment is not meaningful and may lead to misunderstandings. We will explicitly highlight the limitations of the bit flipping strategy in the discussion section of the paper and will explore watermark design tailored to VQ scenarios as an important direction for future research.\n\nOnce again, thank you for raising this forward-thinking and insightful question.\n\n## **Q4.**\n> **If the watermark code S is chosen according to the original cryptographic value distribution, wouldn’t it be possible to skip the modification step?**\n\nThank you for your insightful question. We understand that you mean: if the pre-selected watermark code $S$ happens to match the distribution of values naturally extracted from the vector database, then perhaps we can skip the modification step and directly use $S$ as the “natural watermark” of the original database.\n\nThis approach does indeed have potential in certain application scenarios, particularly in data integrity verification. For example, data owners could record $S$ after its initial extraction and use it in the future to verify whether the database has been modified. However, in the copyright authentication scenario we are focusing on, this approach has limitations: the naturally extracted $S$ is typically a string of meaningless random bits lacking semantic or structural meaning, and thus cannot fulfill the functions of identifying ownership or conveying copyright information. Therefore, the modification process remains a necessary step for embedding specified watermark information.\n\nNevertheless, your question has inspired us to explore a potential optimization direction: introducing additional parameters to guide the original distribution toward the target watermark, thereby reducing the number of vectors requiring modification. We will further investigate this approach in future work."}, {"review_id": "ZA54druuMX", "reviewer": "Reviewer_SNQH", "summary": "The paper introduces the innovative Transparent Vector Priority (TVP) watermarking scheme for vector databases, effectively protecting these assets from unauthorized replication while preserving ANN query accuracy. By leveraging the HNSW structure’s edge properties, TVP prioritizes low-query-frequency transparent vectors, reducing query errors by ~75% compared to existing methods, as demonstrated on the ANN_SIFT1M dataset. Its robust design against various attacks and commitment to open access for code and data highlight a significant contribution to secure vector database management.", "questions": "1. The TVP scheme uses basic graph metrics like degree and edge length. Have the authors considered more refined measures, such as spectral properties or centrality, to improve carrier selection and theoretical grounding?\n2. The experiments are conducted with fixed HNSW parameters (\\(M=8\\), \\(efConstruct=100\\)). How does the TVP scheme perform under different HNSW configurations (e.g., varying \\(M\\) or \\(efConstruct\\)), and can the authors validate the robustness of the transparency parameter (ts) across these variations?\n3. Given the reliance on ANN_SIFT1M, have the authors tested or considered evaluating TVP on other datasets, such as deep1b dataset, to ensure the generalizability of the transparent vector selection strategy?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\nThe paper’s Transparent Vector Priority (TVP) scheme innovatively uses HNSW’s graph properties to embed watermarks in low-query-frequency vectors, reducing ANN query errors by ~75% and ensuring robustness against attacks, with reproducible results on ANN_SIFT1M.\n\nWeakness:\n1. Limited Graph-Theoretic Depth: TVP relies on basic node degree and edge length metrics for transparent vector selection, lacking advanced graph-theoretic analysis (e.g., spectral or centrality measures), reducing its innovation in graph-based watermarking.\n2. Narrow Experimental Scope: Experiments use fixed HNSW parameters (\\(M=8\\), \\(efConstruct=100\\)) and a single dataset (ANN_SIFT1M), limiting validation of TVP’s applicability across varied configurations and datasets.", "was_revised": true, "final_justification": "In light of the discussions, I consider my concerns adequately resolved and recommend a borderline accept.", "rebuttal": "Dear Reviewer SNQH:\n\nWe sincerely appreciate your constructive comments and insightful observations. In response to your suggestions, we have supplemented our experiments and further clarified the theoretical details. If our response has addressed your concerns, we kindly ask that you consider raising your rating, for which we would be most grateful. If you have any further suggestions or concerns, we will continue to respond positively and improve our work.\n\n## **Weakness 1 & Question 1.**\n> **The TVP scheme uses basic graph metrics like degree and edge length. Have the authors considered more refined measures, such as spectral properties or centrality, to improve carrier selection and theoretical grounding?**\n\nThank you for your valuable suggestions.\nCurrently, the TVP strategy primarily selects carrier vectors based on the fundamental structural characteristics of the HNSW graph, utilizing each node's degree and edge length to construct transparency scores. This method is efficient in implementation and has already demonstrated significant performance improvements. In fact, node degree has been widely regarded as a measure of centrality in graph theory. TVP has preliminarily embodied the concept of degree centrality and further enhanced the discrimination of “transparency” through edge length information.\nWe fully agree with the reviewers' perspective that more refined graph theory metrics can uncover nodes' deeper structural roles within the graph, potentially providing a more robust theoretical foundation and selection precision for carrier selection.\nIn future work, we plan to systematically incorporate these more complex graph metrics to further enhance TVP's theoretical rigor and application performance.\n\n## **Weakness 2 & Question 2.**\n\n> **The TVP scheme's performance and the robustness of the transparency parameter (ts) under different HNSW configurations.**\n\nThank you for your interest in the stability and generalization capabilities of TVP. We fully agree on the necessity of verifying the robustness of the method under different HNSW configurations.\n\nBased on your feedback, we evaluated the average number of missed queries (AMQ) and average number of false queries (AFQ) introduced by TVP under various HNSW parameter settings (\\$M \\in \\\\{4, 8, 12, 16\\\\}\\$ and \\$efConstruct \\in \\\\{50, 100, 150\\\\}\\$), with the number of retrieved neighbors fixed at \\$k = 100\\$. The results are summarized in Table 1.\n\nTable 1: Embedding effects of TVP under different parameter configurations\n| efConstruct | 50 (AMQ / AFQ) | 100 (AMQ / AFQ) | 150 (AMQ / AFQ) |\n |----|-------------------|--------------------|--------------------| \n|M = 4 | 4.69 / 4.84 | 4.32 / 4.50 | 3.71 / 3.85 | \n|M = 8 | 3.33 / 3.20 | 3.19 / 3.22 | 3.02 / 3.15 |\n|M = 12 | 2.42 / 2.45 | 2.64 / 2.61 | 2.81 / 2.83 | \n|M = 16 | 2.88 / 2.83 | 2.61 / 2.66 | 2.58 / 2.61 |\n\nIt can be seen that regardless of how the HNSW parameters change, the AMQ/AFQ values of TVP remain at a low level, indicating minimal impact on queries. This demonstrates that TVP has good adaptability to different parameter configurations.\nAdditionally, to verify the stability of the transparency parameter ts under different HNSW configurations, we calculated the Pearson correlation coefficient between the ts value of each vector and its actual query frequency for different parameter combinations. The results are shown in Table 2.\n\nTable 2: Pearson correlation coefficient between the ts of vectors and the number of times they are queried under different parameter configurations.\n\n| efConstruct | 50 | 100 | 150 | \n|----|------------------|-------------------|-------------------|\n| M = 4 | -0.6969 | -0.6886 | -0.6885 |\n| M = 8 | -0.6978 | -0.6732 | -0.6603 |\n| M = 12 | -0.6911 | -0.6696 | -0.6572 |\n| M = 16 | -0.6860 | -0.6731 | -0.6600 |\n\nThese results indicate that, under all parameter settings, ts maintains a significant negative correlation with vector query frequency (Pearson coefficients all below -0.66), suggesting that ts is a stable and generalizable transparency metric that can reliably guide carrier vector selection.\n\nIn summary, we believe that TVP continues to demonstrate consistent advantages under different HNSW parameter configurations, and its core idea (screening transparent vectors via ts) exhibits excellent robustness and generalization capabilities.\n\n## **Question 3.**\n\n> **Experiments on other datasets.**\n\nSince “transparent” vectors (i.e., vectors with relatively low query frequencies) are common in any dataset, we speculate that the TVP method has good cross-dataset generalization capabilities.\n\nTo validate this hypothesis, we conducted extended experiments on two widely used deep learning embedding datasets: arxiv-nomic-768-normalized (derived from VIBE, representing text summaries) and deep1b (a classic large-scale image vector dataset). The experimental parameters were consistent with those in the paper. We evaluated the average missed queries (**AMQ**) and average false queries (**AFQ**) caused by different watermark embedding schemes, with experimental results shown in Tables 3 and 4.\n\nTable 3: Experimental results on the Deep1b dataset\n\n| Scheme | SCPW | TabularMark | RS | TVP |\n |------------|------|-------------|-----|------|\n | **AMQ** | 13.96| 13.38 | 13.42| **3.17** | \n| **AFQ** | 14.21| 13.73 | 13.59| **3.29** |\n\nTable 4: Experimental results on the arxiv-nomic-768-normalized dataset\n| Scheme | SCPW | TabularMark | RS | TVP | \n|------------|------|-------------|-----|------| \n| **AMQ** | 13.51| 13.83 | 13.75| **4.26** | \n| **AFQ** | 14.17| 14.02 | 14.11| **4.74** |\n\nIt can be observed that, on both datasets, the TVP scheme achieves significantly lower average missed query counts (AMQ) and average false positive query counts (AFQ) compared to other methods. This indicates that the strategy of prioritizing “transparent” vectors for modification can also reduce query errors on other datasets, thereby validating the cross-dataset generalization capability of our method."}]

Author rebuttal:

Meta-review: Considering the potential threat to vector dataset, the authors present a Transparent Vector Priority (TVP) watermarking scheme.
All the FIVE reviewers basically appreciate the contributions of this work, and are mostly satisfied with authors' responses:
Reviewer 7c4a: 
Novel Watermarking Scheme: The paper proposes the Transparent Vector Priority (TVP) watermarking scheme specifically for vector databases, addressing the critical security need for ownership authentication.
Reviewer: Ncy6
... their proposed additions to the paper (formal definitions of watermarking and the threat model, discussions around the adversarial robustness of their AMQ and AFQ metrics, and more thorough experiments on additional datasets and indexes) make the paper much, much stronger than their initial submission. ... believe the idea of vector database watermarking is a new and timely contribution to the community and has the potential to inspire additional research in this direction.
Reviewer ir5:
...the first kind vector database watermarking scheme (RS) fills a gap in the research field.
Defining missed queries and false queries to measure the impact of watermark embedding on ANN queries is a precise and necessary step. The TVP scheme shows a smart optimization approach.
Reviewer ieq6:
remaining concern: potential serious implications of bit flipping in a vector quantization (VQ) environment.
Reviewer SNQH: satisfied with the authors' rebuttal 

Based on the above, the AC suggests to accept this submission.
Decision: Accept (poster)