Repairing Vertex Labels under Neighborhood Constraints

Summary: Repairing Vertex Labels under Neighborhood Constraints studies cleaning vertex labels to satisfy allowed adjacent-label pairs in graphs. Facing NP-hard relabeling, it proposes greedy, contraction, and hybrid approximations, analyzes star/clique cases, and shows strong empirical performance on synthetic and real networks. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10979
Venue: VLDB
Year: 2014
Pagerank: 5.2872198e-05
Overall Rank: 5,881 | 59.13%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,544	KATARA: A Data Cleaning System Powered by Knowledge Bases and Crowdsourcing	2015	SIGMOD	0.00011438274
6,279	Self-supervised and Interpretable Data Cleaning with Sequence Generative Adversarial Networks	2023	VLDB	5.1241232e-05
8,008	Online Topic-Aware Entity Resolution Over Incomplete Data Streams	2021	SIGMOD	4.6037276e-05
8,363	Deducing Certain Fixes to Graphs	2019	VLDB	4.5311185e-05
11,711	Catching Numeric Inconsistencies in Graphs	2018	SIGMOD	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
49	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00067607389
268	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD	0.00029739054
351	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00026351742
682	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.0001816451
942	Framework for Evaluating Clustering Algorithms in Duplicate Detection	2009	VLDB	0.00015143877
1,419	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00012072488
1,806	Incremental Graph Pattern Matching	2011	SIGMOD	0.00010478244
3,749	Learning Expressive Linkage Rules using Genetic Programming	2012	VLDB	6.7868937e-05
5,374	A Quest for Beauty and Wealth (or, Business Processes for Database Researchers)	2011	PODS	5.5408029e-05
7,562	Efficient Recovery of Missing Events	2013	VLDB	4.7057229e-05
8,723	GBLENDER: Towards Blending Visual Query Formulation and Query Processing in Graph Databases	2010	SIGMOD	4.4546285e-05
8,724	Warehousing Workflow Data: Challenges and Opportunities	2001	VLDB	4.4546285e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,563	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD	4.1905499e-05
10,081	From Suspicious Errors to Valid Data: On Repairing Spatio-Temporal Data via Spatial and Temporal Dependencies	2026	SIGMOD	4.1905499e-05
11,141	Neighborhood-Preserving Graph Sparsification	2024	VLDB	4.1905499e-05
8,363	Deducing Certain Fixes to Graphs	2019	VLDB	4.5311185e-05
5,262	Enriching Data Imputation with Extensive Similarity Neighbors	2015	VLDB	5.5961016e-05
949	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.0001510288
8,014	The Computation of Optimal Subset Repairs	2020	VLDB	4.6020746e-05
2,958	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD	7.8126329e-05
268	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD	0.00029739054
10,235	Repairing Property Graphs under PG-Constraints	2026	VLDB	4.1905499e-05