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: 10978
Venue: VLDB
Year: 2014
Pagerank: 5.3007132e-05
Overall Rank: 5,852 | 59.29%
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,546	KATARA: A Data Cleaning System Powered by Knowledge Bases and Crowdsourcing	2015	SIGMOD	0.00011446851
6,280	Self-supervised and Interpretable Data Cleaning with Sequence Generative Adversarial Networks	2023	VLDB	5.1290457e-05
8,005	Online Topic-Aware Entity Resolution Over Incomplete Data Streams	2021	SIGMOD	4.6081461e-05
8,422	Deducing Certain Fixes to Graphs	2019	VLDB	4.5167705e-05
9,564	Catching Numeric Inconsistencies in Graphs	2018	SIGMOD	4.3254416e-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.00067660624
265	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD	0.00029763412
350	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00026365067
686	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00018178029
936	Framework for Evaluating Clustering Algorithms in Duplicate Detection	2009	VLDB	0.0001521549
1,414	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00012118275
1,720	Incremental Graph Pattern Matching	2011	SIGMOD	0.00010779343
3,744	Learning Expressive Linkage Rules using Genetic Programming	2012	VLDB	6.7932071e-05
5,364	A Quest for Beauty and Wealth (or, Business Processes for Database Researchers)	2011	PODS	5.5461492e-05
7,561	Efficient Recovery of Missing Events	2013	VLDB	4.7102455e-05
8,726	GBLENDER: Towards Blending Visual Query Formulation and Query Processing in Graph Databases	2010	SIGMOD	4.4593116e-05
8,727	Warehousing Workflow Data: Challenges and Opportunities	2001	VLDB	4.4593116e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,559	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD	4.1945683e-05
10,081	From Suspicious Errors to Valid Data: On Repairing Spatio-Temporal Data via Spatial and Temporal Dependencies	2026	SIGMOD	4.1945683e-05
8,422	Deducing Certain Fixes to Graphs	2019	VLDB	4.5167705e-05
11,138	Neighborhood-Preserving Graph Sparsification	2024	VLDB	4.1945683e-05
5,253	Enriching Data Imputation with Extensive Similarity Neighbors	2015	VLDB	5.6014916e-05
951	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.00015106325
7,605	The Computation of Optimal Subset Repairs	2020	VLDB	4.697534e-05
2,957	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD	7.8198686e-05
265	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD	0.00029763412
10,235	Repairing Property Graphs under PG-Constraints	2026	VLDB	4.1945683e-05