Multimodal entity linking (MEL) aims to link ambiguous multimodal mentions to their corresponding entities in a multimodal knowledge graph. Although many existing methods have been dedicated to exploring fine-grained intra- and cross-modal interactions between mentions and entities and have achieved good results, the discrepancies between the data distributions in training and real-world applications, as well as the noisy onehot labels, still impede the generalization of MEL models, which leads to poor performance when encountering unseen entities. Although general-purpose multimodal large language models (MLLMs) are powerful, it is costly and time-consuming to apply them directly to the MEL task. To address the above issues, we propose a Distillation-Enhanced framework for Multimodal Entity Linking (DEMEL). During training, DEMEL takes the best-trained MEL model so far as the teacher model, and distills the knowledge of the teacher model into the student model, i.e. the MEL model of the current iteration, when training it with onehot labels. This imposes regularization on the model, balances bias and variance in the training process, and improves the generalization ability of the MEL model. Moreover, DEMEL employs an MLLM to selectively rerank predictions for uncertain samples in the inference phase, improving accuracy while minimizing invocation costs. Extensive experiments on three public MEL datasets demonstrate that DEMEL outperforms state-of-the-art baselines, achieving 3.27% improvement with MLLM reranking for just 8.59% of test samples, and up to 4.8% H@1 enhancement in low-resource settings even without using MLLM reranking.

Parsing Natural Language to SQL (NL2SQL) helps users who are not proficient in databases to efficiently query desired data through natural language. Although existing NL2SQL parsers demonstrate good capabilities in processing clear queries, ambiguity still remains an unresolved issue which makes parsers produce unstable outputs that deviate from the user's actual intent. To bridge the gap, this paper introduces the CLEAR framework, a systematic study of disambiguation for NL2SQL, including ambiguity detection, clarification, and reformulation, which benefits any NL2SQL parsers. Firstly, CLEAR employs a pipeline using Large Language Models (LLMs) and a series of rules to detect ambiguities, thus obtaining the “candidate mapping” for ambiguity representation. Secondly, an interactive selection module is employed to collect the clarification information from users through multiple-choice questions, thus obtaining the “selection mapping”. Finally, rewriting rules are employed to reformulate the question and schema, thus obtaining a clear input for parsers to generate clear SQLs. Furthermore, we construct CLAMBSQL, a novel benchmark for systematic evaluation for NL2SQL disambiguation, which contains fine-grained ambiguity and clarification annotations. Experiments on various datasets and baselines demonstrate that CLEAR can successfully address seven types of ambiguity. When parsers are integrated with CLEAR, the performance of ambiguous SQLs detection achieves a significant improvement of 30.5 % on AMBROSIA in the AllFound metric and 21.1 % on AmbiQT in the BothInTop-5 metric, the performance of ambiguity clarification achieves a remarkable improvement of 16.2 % on CLAMBSQL in the CEX metric, and the performance of the general prediction achieves an increase of 1.6 % in the EX metric and 7.7 % in the CSR metric on BIRD. The CLEAR code and CLAMBSQL dataset are available at https://github.com/mengzhang18/CLEAR.

Functional dependencies (FDs) form a valuable ingredient for various data management tasks. However, existing methods can hardly discover practical and interpretable FDs, especially in large noisy real-life datasets. This paper studies the problem of discovering meaningful functional dependencies (FDms) that utilize support and error parameters to capture interesting dependencies in such datasets and proposes an efficient discovery algorithm called FDMε. In order to scale with large datasets, FDM ε employs an efficient sampling method with accuracy guarantees to capture the differences between tuple pairs and to quantify the connection between support/error of dependencies on samples and those on the entire dataset. Moreover, it adopts a clustering-based correlated attributes extraction to divide the exponentially large search space into multiple small sub-spaces and proposes an easy-first traversal strategy with covariance-based guidance that quickly detects candidate dependencies and validates them. Additionally, we prove a covariance lower bound as an additional pruning criterion to reduce the search space. Extensive experiments on real-life and synthetic datasets demonstrate that FDM ε is 14 times faster than existing discovery algorithms on average, up to 31 times, and scales to larger datasets with the least memory cost.

In the era of big data, decision-making in social networks may introduce bias due to interconnected individuals. For instance, in peer-to-peer loan platforms on the Web, considering an individual's attributes along with those of their interconnected neighbors, including sensitive attributes, is vital for loan approval or rejection downstream. Unfortunately, conventional fairness approaches often assume independent individuals, overlooking the impact of one person's sensitive attribute on others' decisions. To fill this gap, we introduce "Interference-aware Fairness" (IAF) by defining two forms of discrimination as Self-Fairness (SF) and Peer-Fairness (PF), leveraging advances in interference analysis within causal inference. Specifically, SF and PF causally capture and distinguish discrimination stemming from an individual's sensitive attributes (with fixed neighbors' sensitive attributes) and from neighbors' sensitive attributes (with fixed self's sensitive attributes), separately. Hence, a network-informed decision model is fair only when SF and PF are satisfied simultaneously, as interventions in individuals' sensitive attributes or those of their peers both yield equivalent outcomes. To achieve IAF, we develop a deep doubly robust framework to estimate and regularize SF and PF metrics for decision models. Extensive experiments on synthetic and real-world datasets validate our proposed concepts and methods.

This article proposes a notion of parametric simulation to link entities across a relational database 𝒟 and a graph G . Taking functions and thresholds for measuring vertex closeness, path associations, and important properties as parameters, parametric simulation identifies tuples t in 𝒟 and vertices v in G that refer to the same real-world entity, based on both topological and semantic matching. We develop machine learning methods to learn the parameter functions and thresholds. We show that parametric simulation is in quadratic-time by providing such an algorithm. Moreover, we develop an incremental algorithm for parametric simulation; we show that the incremental algorithm is bounded relative to its batch counterpart, i.e., it incurs the minimum cost for incrementalizing the batch algorithm. Putting these together, we develop HER , a parallel system to check whether ( t, v ) makes a match, find all vertex matches of t in G , and compute all matches across 𝒟 and G , all in quadratic-time; moreover, HER supports incremental computation of these in response to updates to 𝒟 and G . Using real-life and synthetic data, we empirically verify that HER is accurate with F-measure of 0.94 on average, and is able to scale with database 𝒟 and graph G for both batch and incremental computations.

This paper proposes an approach to querying a relational database $\mathcal{D}$ and a graph G taken together in SQL. We introduce a semantic extension of joins across $\mathcal{D}$ and G such that if a tuple t in $\mathcal{D}$ and a vertex v in G refer to the same real-world entity, then we join t and v to correlate their information and complement tuple t with additional properties of vertex v from the graph. Moreover, we extract hidden relationships between t and other entities by exploring paths from v. To support the semantic joins, we develop an extraction scheme based on LSTM, path clustering and ranking, to fetch important properties from graphs, and incrementally maintain the extracted data in response to updates. We also provide methods for implementing static joins when t is a tuple in $\mathcal{D}$, dynamic joins when t comes from the intermediate result of a sub-query, and heuristic joins to strike a balance between the complexity and accuracy. Using real-life data and queries, we experimentally verify the effectiveness, scalability and efficiency of the methods.

This paper proposes an approach for entity resolution (ER) and conflict resolution (CR) in large-scale graphs. It is based on a class of Graph Cleaning Rules (GCRs), which support the primitives of relational data cleaning rules, and may embed machine learning classifiers as predicates. As opposed to previous graph rules, GCRs 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 the satisfiability, implication and validation problems are all in polynomial time (PTIME) for GCRs, as opposed to the intractability of these classical problems for previous graph dependencies. We develop a parallel algorithm to discover GCRs by combining the generations of patterns and predicates, and a parallel PTIME algorithm for "deep" ER and CR by recursively applying the mined GCRs. We show that these algorithms guarantee to reduce runtime when more processors are used. Using real-life and synthetic graphs, we experimentally verify that rule discovery and error detection with GCRs are substantially faster than with previous graph dependencies, with improved accuracy.

This paper proposes a notion of parametric simulation to link entities across a relational database$\mathcal{D}$and a graph$G$. Taking functions and thresholds for measuring vertex close-ness, path associations and important properties as parameters, parametric simulation identifies tuples$t$in$\mathcal{D}$and vertices$v$in$G$that refer to the same real-world entity, based on topological and semantic matching. We develop machine learning methods to learn the parameter functions and thresholds. We show that parametric simulation is in quadratic-time, by providing such an algorithm. Putting these together, we develop HER, a parallel system to check whether$(t,v)$makes a match, find all vertex matches of$t$in$G$, and compute all matches across$\mathcal{D}$and$G$, all in quadratic-time. Using real-life and synthetic data, we empirically verify that HER is accurate with$\mathbf{F}$-measure of 0.94 on average, and is able to scale with database$\mathcal{D}$and graph$G$.

This paper tackles two challenges to discovery of graph rules. Existing discovery methods often (a) return an excessive number of rules, and (b) do not scale with large graphs given the intractability of the discovery problem. We propose an application-driven strategy to cut back rules and data that are irrelevant to users' interests, by training a machine learning (ML) model to identify data pertaining to a given application. Moreover, we introduce a sampling method to reduce a big graph G to a set H of small sample graphs. Given expected support and recall bounds, the method is able to deduce samples in H and mine rules from H to satisfy the bounds in the entire G . As proof of concept, we develop an algorithm to discover Graph Association Rules (GARs), which are a combination of graph patterns and attribute dependencies, and may embed ML classifiers as predicates. We show that the algorithm is parallelly scalable, i.e. , it guarantees to reduce runtime when more machines are used. We experimentally verify that the method is able to discover rules with recall above 91% when using sample ratio 10%, with speedup of 61 times.

This paper proposes a class of temporal association rules, denoted by TACOs, for event prediction. As opposed to previous graph rules, TACOs monitor updates to graphs, and can be used to capture temporal interests in recommendation and catch frauds in response to behavior changes, among other things. TACOs are defined on temporal graphs in terms of change patterns and (temporal) conditions, and may carry machine learning (ML) predicates for temporal event prediction. We settle the complexity of reasoning about TACOs, including their satisfiability, implication and prediction problems. We develop a system, referred to as TASTE. TASTE discovers TACOs by iteratively training a rule creator based on generative ML models in a creator-critic framework. Moreover, it predicts events by applying the discovered TACOs. Using real-life and synthetic datasets, we experimentally verify that TASTE is on average 31.4 times faster than conventional data mining methods in TACO discovery, and it improves the accuracy of state-of-the-art event prediction models by 23.4%.

Graph partitioning is crucial to parallel computations on large graphs. The choice of partitioning strategies has strong impact on not only the performance of graph algorithms, but also the design of the algorithms. For an algorithm of our interest, what partitioning strategy fits it the best and improves its parallel execution? Is it possible to develop graph algorithms with partition transparency, such that the algorithms work under different partitions without changes? This paper aims to answer these questions. We propose an application-driven hybrid partitioning strategy that, given a graph algorithm A, learns a cost model for A as polynomial regression. We develop partitioners that given the learned cost model, refine an edge-cut or vertex-cut partition to a hybrid partition and reduce the parallel cost of A. Moreover, we identify a general condition under which graph-centric algorithms are partition transparent. We show that a number of graph algorithms can be made partition transparent. Using real-life and synthetic graphs, we experimentally verify that our partitioning strategy improves the performance of a variety of graph computations, up to 22.5 times.

This article proposes an Adaptive Asynchronous Parallel (AAP) model for graph computations. As opposed to Bulk Synchronous Parallel (BSP) and Asynchronous Parallel (AP) models, AAP reduces both stragglers and stale computations by dynamically adjusting relative progress of workers. We show that BSP, AP, and Stale Synchronous Parallel model (SSP) are special cases of AAP. Better yet, AAP optimizes parallel processing by adaptively switching among these models at different stages of a single execution. Moreover, employing the programming model of GRAPE, AAP aims to parallelize existing sequential algorithms based on simultaneous fixpoint computation with partial and incremental evaluation. Under a monotone condition, AAP guarantees to converge at correct answers if the sequential algorithms are correct. Furthermore, we show that AAP can optimally simulate MapReduce, PRAM, BSP, AP, and SSP. Using real-life and synthetic graphs, we experimentally verify that AAP outperforms BSP, AP, and SSP for a variety of graph computations.