{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,12]],"date-time":"2025-12-12T13:27:06Z","timestamp":1765546026037},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2014,7]]},"abstract":"<jats:p>\n            A broad class of data, ranging from similarity networks, workflow networks to protein networks, can be modeled as graphs with data values as vertex labels. The vertex labels (data values) are often dirty for various reasons such as typos or erroneous reporting of results in scientific experiments.\n            <jats:italic>Neighborhood constraints<\/jats:italic>\n            , specifying label pairs that are allowed to appear on adjacent vertexes in the graph, are employed to detect and repair erroneous vertex labels. In this paper, we study the problem of repairing vertex labels to make graphs satisfy neighborhood constraints. Unfortunately, the relabeling problem is proved to be NP hard, which motivates us to devise approximation methods for repairing, and identify interesting special cases (star and clique constraints) that can be efficiently solved. We propose several approximate repairing algorithms including greedy heuristics, contraction method and a hybrid approach. The performances of algorithms are also analyzed for the special case. Our extensive experimental evaluation, on both synthetic and real data, demonstrates the effectiveness of eliminating frauds in several types of application networks. Remarkably, the hybrid method performs well in practice, i.e., guarantees termination, while achieving high effectiveness at the same time.\n          <\/jats:p>","DOI":"10.14778\/2732967.2732974","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"987-998","source":"Crossref","is-referenced-by-count":32,"title":["Repairing vertex labels under neighborhood constraints"],"prefix":"10.14778","volume":"7","author":[{"given":"Shaoxu","family":"Song","sequence":"first","affiliation":[{"name":"Tsinghua University, China"}]},{"given":"Hong","family":"Cheng","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, China"}]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, China"}]},{"given":"Lei","family":"Chen","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, China"}]}],"member":"320","published-online":{"date-parts":[[2014,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303983"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167174"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066175"},{"key":"e_1_2_1_4_1","first-page":"649","volume-title":"VLDB","author":"Bonifati A.","year":"2001","unstructured":"A. Bonifati , F. Casati , U. Dayal , and M. C. Shan . Warehousing workflow data: Challenges and opportunities . In VLDB , pages 649 -- 652 , 2001 . A. Bonifati, F. Casati, U. Dayal, and M. C. Shan. Warehousing workflow data: Challenges and opportunities. In VLDB, pages 649--652, 2001."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807217"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247574"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497500"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2004.04.007"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti610"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989286"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989420"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920878"},{"key":"e_1_2_1_13_1","unstructured":"Full Version. Repairing vertex labels under neighborhood constraints. http:\/\/ise.thss.tsinghua.edu.cn\/sxsong\/doc\/grelabel.pdf.  Full Version. Repairing vertex labels under neighborhood constraints. http:\/\/ise.thss.tsinghua.edu.cn\/sxsong\/doc\/grelabel.pdf."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btg469"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687771"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350276"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807182"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514901"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/140370.140377"},{"key":"e_1_2_1_21_1","first-page":"17","volume-title":"AAAI","author":"Minton S.","year":"1990","unstructured":"S. Minton , M. D. Johnston , A. B. Philips , and P. Laird . Solving large scale constraint satisfaction and scheduling problems using a heuristic repair method . In AAAI , pages 17 -- 24 , 1990 . S. Minton, M. D. Johnston, A. B. Philips, and P. Laird. Solving large scale constraint satisfaction and scheduling problems using a heuristic repair method. In AAAI, pages 17--24, 1990."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/375360.375365"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000824.2000826"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.46"},{"key":"e_1_2_1_25_1","first-page":"169","volume-title":"Business Process Management Workshops (1)","author":"W. M.","year":"2011","unstructured":"W. M. P. van der Aalst and et al. Process mining manifesto . In Business Process Management Workshops (1) , pages 169 -- 194 , 2011 . W. M. P. van der Aalst and et al. Process mining manifesto. In Business Process Management Workshops (1), pages 169--194, 2011."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022883727209"},{"key":"e_1_2_1_27_1","volume-title":"Information Retrieval. Butterworth","author":"van Rijsbergen C. J.","year":"1979","unstructured":"C. J. van Rijsbergen . Information Retrieval. Butterworth , 1979 . C. J. van Rijsbergen. Information Retrieval. Butterworth, 1979."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536206.2536212"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1093382.1093385"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btn036"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2732967.2732974","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:20:19Z","timestamp":1672219219000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2732967.2732974"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7]]},"references-count":30,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2014,7]]}},"alternative-id":["10.14778\/2732967.2732974"],"URL":"https:\/\/doi.org\/10.14778\/2732967.2732974","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2014,7]]}}}