Wenfei Fan

This paper presents DocChecker, a system for detecting textual contradictions. Given a document collection 𝒟, DocChecker identifies conflicting properties or relationships assigned to the same entity, both within and across documents. It adopts a graph-based paradigm: entities and their relations are extracted, represented as a property graph G , joined across documents, and enriched with domain knowledge. DocChecker introduces a class of rules that detect vertex- and edge-level contradictions in PTIME, unifying logical reasoning, ML predictions and NLP tools. We present how graphs are extracted, joined and enriched, and propose a parallel rule discovery algorithm with new generation, evaluation and validation strategies tailored for sparse contradictions. Using real-life documents, we empirically verify that DocChecker detects intra- and inter-document contradictions with an average F1-score of 0.900, up to 0.935, and it scales to large collections 𝒟 in parallel.

This paper addresses the challenge of protecting Personally Identifiable Information (PII) in textual data, identifying and anonymizing PII to ensure privacy and regulatory compliance, while preserving data utility. We model this bi-criteria optimization problem as a two-player Stackelberg game, where an attacker seeks to link anonymized data back to individuals and a protector anonymizes the data to prevent re-identification. We show that the problem is intractable. Thus we develop SHIELD, an attack-aware PII protection system that iteratively engages the protector and attacker to prevent both PII breaches and over-scrubbing. SHIELD integrates logical reasoning with machine learning to identify PII, and supports pluggable attackers for robustness against re-identification. It achieves a constant-factor approximation for utility loss while mitigating risk. Using synthetic and real-world datasets, we empirically show that SHIELD offers better privacy-utility trade-off than prior PII protection systems, while remaining efficient and scalable.

This paper presents an ML-based method for SubIso, the graph pattern matching problem. Given a graph G and a pattern Q , SubIso aims to enumerate all subgraphs of G that are isomorphic to Q . We show that SubIso is EnumP-complete, where EnumP is the enumeration counterpart of NP. We then study revisions VF3 _M of the classical VF3 algorithm by incorporating an ML oracle ℻. The model ℻ predicts candidate matches, while VF3 _M verifies them, thereby reducing costly backtracking. We examine whether VF3 _M is (a) output-polynomial, i.e., its runtime is polynomial in the sizes of input and output; (b) consistent, i.e., its accuracy reaches 100% with error-free predictions from ℻; and (c) β-robust, i.e., it guarantees accuracy of at least β even with arbitrarily bad predictions. We establish several results, positive and negative. On the negative side, we show that it is impossible for VF3 _M to be both output polynomial and β-robust with a positive constant β unless P = fewP, a problem as hard as P = NP. On the positive side, we develop three versions of VF3 _M that are (a) consistent, and (b) either 1-robust or output polynomial with a high probability. We also train a model ℻ for VF3 _M . Using real-life and synthetic data, we show that VF3 _M is up to 15.75x--21x faster than VF3, with F1-score 0.98.

This paper studies the impact of outliers in relational dataset D on the accuracy of ML classifiers M , when D is used to train and evaluate M . Outliers are data points that statistically deviate from the distribution of the majority. We distinguish good outliers, i.e. novel data, from bad ones, i.e. those introduced by errors. Moreover, we separate ugly ones in influential features from the other bad ones. We find that only the ugly ones have negative impact on M , while the good (resp. the other bad) ones have positive (resp. neglectable) impact. To mitigate the negative impact, we propose a class of rules, denoted by OMRs, to identify ugly outliers by embedding ML outlier detectors and statistical functions as predicates. We develop algorithms to (a) learn OMRs from real-life data, and (b) catch and fix ugly outliers using the learned OMRs, instead of removing tuples. Using real-life data, we empirically show that OMRs improve the accuracy of various classifiers by 7.2% on average, up to 34.8%.

This paper studies incremental rule discovery. Given a dataset D, rule discovery is to mine the set of the rules on D such that their supports and confidences are above thresholds 𝜎 and 𝛅 , respectively. We formulate incremental problems in response to updates Δ𝜎 and/or Δ𝛅, to compute rules added and/or removed with respect to 𝜎 + Δ𝜎 and 𝛅 + Δ𝛅. The need for studying the problems is evident since practitioners often want to adjust their support and confidence thresholds during discovery. The objective is to minimize unnecessary recomputation during the adjustments, not to restart the costly discovery process from scratch. As a testbed, we consider entity enhancing rules, which subsume popular data quality rules as special cases. We develop three incremental algorithms, in response to Δ𝜎 , Δ𝜎 and both. We show that relative to a batch discovery algorithm, these algorithms are bounded, i.e., they incur the minimum cost among all incrementalizations of the batch one, and parallelly scalable, i.e., they guarantee to reduce runtime when given more processors. Using real-life data, we empirically verify that the incremental algorithms outperform the batch counterpart by up to 658× when Δ𝜎 and Δ𝜎 are either positive or negative.

This paper studies enhancement of training data D to improve the robustness of machine learning (ML) classifiers M against adversarial attacks on relational data. Data enhancing aims to (a) defuse poisoned imperceptible features embedded in D , and (b) defend against attacks at prediction time that are unseen in D . We show that while there exists an inherent tradeoff between the accuracy and robustness of M in case (b), data enhancing can improve both the accuracy and robustness at the same time in case (a). We formulate two data enhancing problems accordingly, and show that both problems are intractable.Despite the hardness, we propose a framework that integrates model training and data enhancing. Moreover, we develop algorithms for (a) detecting and debugging corrupted imperceptible features in training data, and (b) selecting and adding adversarial examples to training data to defend against unseen attacks at prediction time. Using real-life datasets, we empirically verify that the method is at least 20.4% more robust and 2.02X faster than SOTA methods for classifiers M , without degrading the accuracy of M .

This paper studies cost-effective graph cleaning with a single machine. We adopt a rule-based method that may embed machine learning models as predicates in the rules. Graph cleaning with the rules involves rule discovery, error detection and correction. These tasks are both computation-heavy and I/O-intensive as they repeatedly invoke costly graph pattern matching, and produce a large amount of a large volume of intermediate results, among other things. In light of these, no existing single-machine system is able to carry out these tasks even on not-too-large graphs, even using GPUs. Thus we develop MiniClean, a single-machine system for cleaning large graphs. It proposes (1) a workflow that better fits a single machine by pipelining CPU, GPU and I/O operations; (2) memory footprint reduction with bundled processing and data compression; and (3) a multi-mode parallel model for SIMD, pipelined and independent parallelism, and their scheduling to maximize CPU--GPU synergy. Using real-life graphs, we empirically verify that MiniClean outperforms the SOTA single-machine systems by at least 65.34× and multi-machine systems with 32 nodes by at least 8.09×.

This article develops Hercules, a system for entity resolution (ER), conflict resolution (CR), timeliness deduction (TD), and missing value/link imputation (MI) in graphs. It proposes GCR ⁺ s, a class of graph cleaning rules (GCR) that support not only predicates for ER and CR but also temporal orders to deduce timeliness and data extraction to impute missing data. As opposed to previous graph rules, GCR ⁺ s are defined with a dual graph pattern to accommodate irregular structures of schemaless graphs and adopt patterns of a star form to reduce the complexity. We show that while the implication and satisfiability problems are intractable for GCR ⁺ s, it is in polynomial time to detect and correct errors with GCR ⁺ s. Underlying Hercules, we train a ranking model to predict the temporal orders on attributes and embed it as a predicate of GCR ⁺ s. We provide an algorithm for discovering GCR ⁺ s by combining the generations of patterns and predicates. We also develop a method for conducting ER, CR, TD, and MI in the same process to improve the overall quality of graphs by leveraging their interactions and chasing with GCR ⁺ s; we show that the method has the Church–Rosser property under certain conditions. Using real-life and synthetic graphs, we empirically verify that Hercules is 53% more accurate than the state-of-the-art graph cleaning systems and performs comparably in efficiency and scalability.

This paper studies the problem of discovering top- k relevant and diversified rules. Given a real-life dataset, it is to mine a set of k rules that are as close to users' interest as possible, and meanwhile, as diverse to each other as possible. It aims to reduce excessive irrelevant rules commonly returned by rule discovery. As a testbed, we consider Entity Enhancing Rules (REEs), which subsume popular data quality rules as special cases. We train a relevance model to learn users' prior knowledge, rank rules based on users' need, and propose four diversity measures to assess the diversity between rules. Based on these measures, we formulate a new discovery problem. We show that the bi-criteria discovery problem is NP-complete and hard to approximate. This said, we develop a practical algorithm for the problem, and prove its approximation bounds under certain conditions. Moreover, we develop optimization techniques to speed up the process, and parallelize the algorithm such that it guarantees to reduce runtime when given more processors. Using real-life data, we empirically verify that on average, the top-10 REEs discovered by our algorithm is able to catch 77.5% of errors detected by the entire set Σ _all of REEs and achieve F_1 = 0.74 for real error detection; moreover, discovering top-ranked REEs is 62.4X faster than mining Σ _all .