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: 11166
Venue: VLDB
Year: 2014
Pagerank: 6.1885644e-05
Overall Rank: 5,519 | 62.14%
DOI: 10.14778/2733004.2733009

Incoming Non-self Citations Over Time

Authors

1. Shaoxu Song (Tsinghua University)
2. Hong Cheng (Chinese University of Hong Kong)
3. Jeffrey Xu Yu (Chinese University of Hong Kong)
4. Lei Chen (Hong Kong University of Science and Technology)

BibTeX Citation

@article{song_vldb14,
        title = {{Repairing Vertex Labels under Neighborhood Constraints}},
        author = {Song, Shaoxu and Cheng, Hong and Yu, Jeffrey Xu and Chen, Lei},
        journal = {PVLDB},
        series = {{VLDB} '14},
        volume = {7},
        number = {11},
        pages = {987--998},
        doi = {10.14778/2733004.2733009},
        url = {https://doi.org/10.14778/2733004.2733009},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,101	KATARA: A Data Cleaning System Powered by Knowledge Bases and Crowdsourcing	2015	SIGMOD	0.00012168934
5,518	Self-supervised and Interpretable Data Cleaning with Sequence Generative Adversarial Networks	2023	VLDB	6.1885722e-05
8,105	Online Topic-Aware Entity Resolution Over Incomplete Data Streams	2021	SIGMOD	5.4860105e-05
8,225	Deducing Certain Fixes to Graphs	2019	VLDB	5.4624971e-05
11,910	Catching Numeric Inconsistencies in Graphs	2018	SIGMOD	5.093636e-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
33	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00049907763
185	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD	0.00026231189
326	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00021152829
674	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00015081844
871	Framework for Evaluating Clustering Algorithms in Duplicate Detection	2009	VLDB	0.00013496531
1,128	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.0001206219
1,296	Incremental Graph Pattern Matching	2011	SIGMOD	0.00011269684
3,755	Learning Expressive Linkage Rules using Genetic Programming	2012	VLDB	7.1496482e-05
5,511	A Quest for Beauty and Wealth (or, Business Processes for Database Researchers)	2011	PODS	6.1915384e-05
8,008	Efficient Recovery of Missing Events	2013	VLDB	5.5077375e-05
8,884	GBLENDER: Towards Blending Visual Query Formulation and Query Processing in Graph Databases	2010	SIGMOD	5.3514928e-05
8,885	Warehousing Workflow Data: Challenges and Opportunities	2001	VLDB	5.3514928e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,756	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD
2	10,372	From Suspicious Errors to Valid Data: On Repairing Spatio-Temporal Data via Spatial and Temporal Dependencies	2026	SIGMOD
3	11,344	Neighborhood-Preserving Graph Sparsification	2024	VLDB
4	8,225	Deducing Certain Fixes to Graphs	2019	VLDB
5	5,167	Enriching Data Imputation with Extensive Similarity Neighbors	2015	VLDB
6	1,115	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB
7	8,103	The Computation of Optimal Subset Repairs	2020	VLDB
8	2,490	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD
9	185	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD
10	10,523	Repairing Property Graphs under PG-Constraints	2026	VLDB