Graph Edit Distance (GED) is a widely used measure of graph similarity, valued for its flexibility in encoding domain knowledge through operation costs. However, existing learning-based approximation methods follow a modeling paradigm that decouples local candidate match selection from both operation costs and global dependencies between matches. This decoupling undermines their ability to capture the intrinsic flexibility of GED and often forces them to rely on costly iterative refinement to obtain accurate alignments. In this work, we revisit the formulation of GED and revise the prevailing paradigm, and propose Graph Edit Network (GEN), an implementation of the revised formulation that tightly integrates cost-aware expense estimation with globally guided one-step alignment. Specifically, GEN incorporates operation costs into node matching expenses estimation, ensuring match decisions respect the specified cost setting. Furthermore, GEN models match dependencies within and across graphs, capturing each match's impact on the overall alignment. These designs enable accurate GED approximation without iterative refinement. Extensive experiments on real-world and synthetic benchmarks demonstrate that GEN achieves up to a 37.8% reduction in GED predictive errors, while increasing inference throughput by up to 414x. These results highlight GEN's practical efficiency and the effectiveness of the revision. Beyond this implementation, our revision provides a principled framework for advancing learning-based GED approximation.

Retrieval-augmented generation (RAG) has become a cornerstone for enhancing large language models (LLMs) with real-time information from the Web, but its performance often heavily depends on the quality of the retrieved documents. Given that RAG systems frequently draw from vast and often noisy Web corpora, ensuring the reliability of retrieved content is paramount. While rerankers improve the factual accuracy of the RAG system by elevating the proportion of ground-truth documents (GD) in high-ranked results, the shifts of document type distributions during reranking remain unclear, hindering the understanding of the reranker's behavior. To bridge this gap, we conduct an empirical study to categorize documents and compare their distribution before and after reranking. We reveal a counterintuitive finding: though rerankers improve the proportion of GD, they also significantly increase the proportion of harmful documents (HD) in top-ranked retrieved documents. It not only narrows the potential context window for ranking the GD higher but also increases the risk of HD misleading the LLMs, potentially leading to the generation and propagation of misinformation across Web platforms. Motivated by this finding, we propose a risk-aware reranking method for RAG with LLMs, which balances the risk and benefit during reranking. Given a query, the RAG framework first retrieves relevant documents. Then, our approach quantifies the potential beneficial and harmful impacts of various documents on the LLMs' generation. To estimate the impacts, we conduct a dual-aspect document impact assessment via information gain, which employs a risk clipping to avoid the numerical fluctuations in the estimation. Finally, we conduct the reranking according to the potential impact of each document, enabling the reranker to significantly reduce the HD proportion. Experiments and analysis across multiple models and datasets, including Wikipedia, web news, and research papers, show the effectiveness of our method. Our code is available at https://github.com/lzz335/hidden_risk_of_reranking.

Rumor detection is essential for building a responsible web and internet ecosystem, which has attracted significant attention from the research community. However,emerging topic rumor detection, i.e., identify rumors at the early stages of a topic's emergence where only limited discussions can be observed, still remains a challenge. Technically, this scenario is accompanied by the issues ofdata scarcityon emerging topics and thedata distribution discrepancybetween old topics and emerging new topic. In this paper, we propose a new framework termedLLM-drivenADversarialExampleSynthesis (LADES) for emerging topic rumor detection. LADES utilizes Large Language Models (LLMs) for generating readable and contextually coherent adversarial examples. The generated adversarial examples not only expand the training set to tackle the data scarcity issue, but also act as a bridge to connect the data distribution of old and new topics. To overcome training instability in adversarial example generation, LADES introduces a gradient-free Markov Chain Monte Carlo (MCMC) sampling method. This method ensures adversarial examples are readable and contextually coherent by harnessing LLMs, while promoting effective attacks through entropy-based sampling that targets model uncertainty. To mitigate the impact of potential mislabeling in synthetic data, LADES implements a meta-mixed-learning mechanism. This mechanism dynamically adjusts the weights of synthetic adversarial examples, guided by limited labeled data from emerging topics, thereby alleviating the data noise.

While most existing speech-driven talking head generation methods provide effective solutions, they primarily focus on the facial area. However, producing upper-body talking videos from speech remains challenging. Addressing how to use speech to simultaneously drive subtle facial motion and large-scale body motion while generating naturally synchronized upper body video frames is urgent. In this study, we propose AnchorTalk, a novel system based on tri-plane hash NeRF, capable of producing high-quality anchor-style talking videos. Firstly, to integrate both rigid and non-rigid motion within a unified system, we introduce a coarse-to-fine framework that consists of coarse pose generation and facial details optimization. A speech disentanglement encoder decouples speech features into pose-related and head-related features to drive the motion of the body and head. Secondly, during the coarse pose generation phase, we propose a geometry correction module to obtain precise body parameters to guide the body motion. Thirdly, less detailed head parameters can lead to facial distortion and disjointed motion during facial optimization. To mitigate this issue, we propose a head controller to capture facial expressions accurately. By fine-tuning the model on a one-minute video, the system can generalize to novel identities. Experimental results validate the effectiveness and feasibility of our method in generating high-quality, coherent upper-body talking human videos from speech.

Large language models (LLMs) demonstrate significant potential in various applications; however, they are susceptible to generating hallucinations, which can lead to the spread of online misinformation. Existing studies address hallucination detection by (1) employing reference-based methods that consult external resources for verification or (2) utilizing reference-free methods that mainly estimate answer uncertainty based on LLM's internal states. However, reference-based methods incur significant costs and can be infeasible for obtaining reliable external references. Besides, existing uncertainty estimation (UE) methods often overlook the impact of scenario backgrounds inherited from the query's lexical resources, leading to noise in UE. In almost all real-world applications, users care about the uncertainty concerning semantics or facts instead of the query's scenario information. Therefore, we argue that mitigating scenario-related noise and focusing on semantic information can yield a more desirable UE. In this paper, we introduce a plug-and-play scenario-independent framework to enhance unsupervised UE in LLMs by removing scenario-related noise and focusing on semantic information. This framework is compatible with most existing UE methods, as it leverages only the existing UE methods' outputs. Specifically, we design a scenario-specific sampling to paraphrase queries, maintaining their common semantics while diversifying the scenario distribution. Subsequently, to estimate the contribution of the common semantics, we design a factor analysis (FA) model to disentangle the UE score obtained from the given UE method into a combination of multiple latent factors, which represent the contribution of the common semantics and scenario-related noise. By solving the FA model, we decompose the impact of the most significant factor to approximate the uncertainty caused by the common semantics, thus achieving scenario-independent UE. Extensive experiments and analysis across multiple models and datasets demonstrate the effectiveness of our approach.

Inductive relation prediction aims to predict missing connections between entities unseen during training. Recent approaches adopt binary (positive or negative) training labels, which indicate whether the query relation exists between the entities, as supervision to teach models recognizing the entity-independent relation patterns in the context (enclosed subgraph or connective path). However, we argue that in this kind of method, the trained models are guided to make relation predictions by remembering whether the query relation and its contextual relational pattern co-occur more frequently in positive or negative samples. This solution could introduce two major limitations: 1) the model struggles with long-tail combinations, i.e., the combination between query relation and the relational pattern rarely occurs during training; 2) when noisy relational patterns, which fail to provide evidence for predicting the query relation, frequently occur with the query relation in positive training samples, the model will be misled into considering the noisy relational patterns as a feature supporting the existence of the query relation. To solve these problems, we propose ToC (Thinking on Context). ToC first utilizes large language models (LLMs) to incorporate a chain of thought as an additional supervisory constraint, guiding the model to make relational predictions based on logical reasoning instead of co-occurrence frequency. Additionally, ToC employs the reasoning capabilities of LLMs to construct context-level negative samples, aiding the model in identifying and disregarding noisy relational patterns. Extensive experiments show that ToC significantly outperforms state-of-the-art methods across three widely used datasets in multiple inductive settingshttps://github.com/AI-Chen/ToC_KGC.

Asynchronous pipeline model parallelism with a “1F1B” (one forward, one backward) schedule generates little bubble overhead and always provides quite a high throughput. However, the “1F1B” schedule inevitably leads to weight inconsistency and weight staleness issues due to the cross-training of different mini-batches across GPUs. To simultaneously address these two problems, in this paper, we propose an optimizer-dependent weight prediction strategy (a.k.a PipeOptim) for asynchronous pipeline training. The key insight of our proposal is that we employ a weight prediction strategy in the forward pass to approximately ensure that each mini-batch uses consistent and staleness-free weights to compute the forward pass of the “1F1B” schedule. To be concrete, we first construct the weight prediction scheme based on the update rule of the used optimizer when training the deep neural network models. Then throughout the “1F1B” pipeline training, each mini-batch is mandated to execute weight prediction, subsequently employing the predicted weights to perform the forward pass. As a result, PipeOptim 1) inherits the advantage of the “1F1B” schedule and generates high throughput, and 2) can ensure effective parameter learning regardless of the type of the used optimizer. We conducted extensive experimental evaluations using nine different deep-learning models to verify the effectiveness of our proposal. The experiment results demonstrate that PipeOptim outperforms the other five popular pipeline approaches including GPipe, PipeDream, PipeDream-2BW, SpecTrain, and XPipe.

Subgraph matching is challenging as it necessitates time-consuming combinatorial searches. Recent Graph Neural Network (GNN)-based approaches address this issue by employing GNN encoders to extract graph information and hinge distance measures to ensure containment constraints in the embedding space. These methods significantly shorten the response time, making them promising solutions for subgraph retrieval. However, they suffer from scale differences between graph pairs during encoding, as they focus on feature counts but overlook the relative positions of features within node-rooted subtrees, leading to disturbed containment constraints and false predictions. Additionally, their hinge distance measures lack discriminative power for matched graph pairs, hindering ranking applications. We propose NC-Iso, a novel GNN architecture for neural subgraph matching. NC-Iso preserves the relative positions of features by building the hierarchical dependencies between adjacent echelons within node-rooted subtrees, ensuring matched graph pairs maintain consistent hierarchies while complying with containment constraints in feature counts. To enhance the ranking ability for matched pairs, we introduce a novel similarity dominance ratio-enhanced measure, which quantifies the dominance of similarity over dissimilarity between graph pairs. Empirical results on nine datasets validate the effectiveness, generalization ability, scalability, and transferability of NC-Iso while maintaining time efficiency, offering a more discriminative neural subgraph matching solution for subgraph retrieval.

Graph pooling technique in GNNs for learning expressive graph-level representation is critical yet still chal-lenging. Existing pooling methods either struggle to capture local substructures or fail to utilize high-order dependency, thus diminishing the expression capability. To solve this problem, we propose HAP, a hierarchical graph-level representation learning framework adaptively sensitive to graph structures. Specifically, HAP utilizes a novel cross-level attention mechanism MOA to naturally focus more on the close neighborhood while effectively capturing higher-order dependency. It also learns a global graph content GCont that extracts the graph pattern properties to stabilize the pre- and post-coarsening graph content, thus providing global guidance in graph coarsening. Experiments show that HAP significantly outperforms the state-of-the-art graph pooling methods.

Pre-training Event Extraction (EE) models on unlabeled data is an effective strategy that frees researchers from costly and labor-intensive data annotation. However, existing pre-training methods necessitate substantial computational resources, requiring high-performance hardware infrastructure and extensive training duration. In response to these challenges, this paper proposes a Lighter, Faster, and more Data-efficient pre-training framework for EE, named LFDe. Distinct from existing methods that strive to establish a comprehensive representation space during pre-training, our framework focuses on quickly familiarizing with the task format from a small amount of automatically constructed pseudo-events. It comprises three stages: weak-label data construction, pre-training, and fine-tuning. Specifically, during the first stage, LFDe first automatically designates pseudo-triggers and arguments based on the characteristics of real events to form pre-training samples. In the processes of pre-training and fine-tuning, the framework reframes EE as the identification of tokens semantically closest to the prompt within the given sentence. This paper also introduces a novel prompt-based sequence labeling model for EE to accommodate this reframing. Experiments on real-world datasets show that compared to similar models, our framework requires fewer pre-training data (only about 0.04%), a shorter pre-training period (about 0.03%), and lower memory requirements (about 57.6%). Simultaneously, our framework significantly improves performance in various data-scarce scenarios.

Knowledge graphs are crucial foundations for building intelligent systems, such as question answering and recommendation. However, their performance is hampered by the incompleteness of KGs, so the knowledge graph completion arises to infer whether a triple of the form (head entity, relation, tail entity) is a missing fact. The path‐based approach that encodes paths from the head entity to the tail entity for reasoning achieves good performance. Previous work suggests that entity type is beneficial for learning path representations. Nevertheless, the semantics of entities are not captured accurately, as many entities are not typed or loosely typed. In addition, previous methods tend to model paths only from the forward direction but fail to capture new path patterns from the reverse direction (i.e., tail entity to head entity). In this paper, we introduce a structure enhanced path reasoning (SPR) framework to address the above‐given problems. First, the model uilizes the structure of entities, i.e., their relational contexts (the relations linked from the given entity), to obtain a reliable path representation that captures correct entity semantics. This information is accessible to all nonisolated entities in all KGs, so that it can compensate the semantics for entities or KGs that have no type available. Second, we leverage the structure of paths to derive their reverse paths, so as to enhance the path representation by additionally encoding the new patterns embedded in them through a dual path encoding method. In order to verify the effectiveness of the proposed methods, we design different architectures based on LSTM and Transformer, respectively. Experimental results on two benchmark datasets, WN18RR, and FB15k‐237, show that our approach apparently outperforms state‐of‐the‐art methods on fact prediction task and relation prediction task. Furthermore, extensive experiments illustrate the benefits of enhancing path reasoning by exploiting structure information from entity relational contexts and the dual path encoding method.

Graph neural networks (GNN) have been proven to be mature enough for handling graph-structured data on node-level graph representation learning tasks. However, the graph pooling technique for learning expressive graph-level representation is critical yet still challenging. Existing pooling methods either struggle to capture the local substructure or fail to effectively utilize high-order dependency, thus diminishing the expression capability. In this paper we propose HAP, a hierarchical graph-level representation learning framework, which is adaptively sensitive to graph structures, i.e., HAP clusters local substructures incorporating with high-order dependencies. HAP utilizes a novel cross-level attention mechanism MOA to naturally focus more on close neighborhood while effectively capture higher-order dependency that may contain crucial information. It also learns a global graph content GCont that extracts the graph pattern properties to make the pre- and post-coarsening graph content maintain stable, thus providing global guidance in graph coarsening. This novel innovation also facilitates generalization across graphs with the same form of features. Extensive experiments on ten datasets show that HAP significantly outperforms twelve popular graph pooling methods on graph classification task with an maximum accuracy improvement of 20.18%, and exceeds the performance of state-of-the-art graph matching and graph similarity learning algorithms by over 3.42% and 16%.

Graph pooling plays a vital role in learning graph embeddings. Due to the lack of label information, unsupervised graph pooling has received much attention, primarily via mutual information (MI). However, most existing MI-based pooling methods only preserve node features while overlooking the hierarchical substructural information. In this paper, we propose SMIP, a novel unsupervised hierarchical graph pooling method based on substructure-sensitive MI maximization. SMIP reconstructs a hard-style substructure encoder based on cluster-based pooling paradigm, and trains it with two substructure-sensitive MI-based objectives, i.e., node-substructure MI and node-node MI. The node-substructure MI guides to transfer maximum node feature information into corresponded substructures and the node-node MI guarantees a more accurate node allocation. Moreover, to avoid extra computation of augmented graphs and prevent noise information during MI estimation, we propose a local-scope contrastive MI estimation method, making SMIP more potent in capturing intrinsic features of the input graph. Experiments on six benchmark graph classification datasets demonstrate that our hierarchical deep learning approach outperforms all state-of-the-art unsupervised GNN-based methods and even surpasses the performance of nine supervised ones. Generalization study shows that the proposed substructure-sensitive MI objective can be successfully embedded into other cluster-based pooling methods to improve their performance.

Online bipartite matching has attracted wide interest since it can successfully model the popular online car-hailing problem and sharing economy. Existing works consider this problem under either adversary setting or i.i.d. setting. The former is too pessimistic to improve the performance in the general case; the latter is too optimistic to deal with the varying distribution of vertices. In this article, we initiate the study of the non-stationary online bipartite matching problem, which allows the distribution of vertices to vary with time and is more practical. We divide the non-stationary online bipartite matching problem into two subproblems, the matching problem and the selecting problem, and solve them individually. Combining Batch algorithms and deep Q-learning networks, we first construct a candidate algorithm set to solve the matching problem. For the selecting problem, we use a classical online learning algorithm, Exp3, as a selector algorithm and derive a theoretical bound. We further propose CDUCB as a selector algorithm by integrating distribution change detection into UCB. Rigorous theoretical analysis demonstrates that the performance of our proposed algorithms is no worse than that of any candidate algorithms in terms of competitive ratio. Finally, extensive experiments show that our proposed algorithms have much higher performance for the non-stationary online bipartite matching problem comparing to the state-of-the-art.

We consider a class of nonconvex regularized optimization problems, which appear frequently in machine learning and data processing. Due to the structure of the problems, the iteratively reweighted algorithm was developed and applied to the consensus optimization. In this paper, we propose the acceleration of this scheme by adding an inertial term in each iteration. The proposed algorithms inherit the advantages of classical decentralized algorithms: they can be implemented over a connected network, in which the agents communicate with their neighbors and perform local computations. We also employ the diminishing stepsizes technique for the iteratively reweighted algorithm and consider its acceleration. In specific cases, our algorithms reduce to existing decentralized schemes and also indicate novel ones. Mathematically, we prove the convergence for both algorithms with several assumptions on the objective functions. With Kurdyka-Łojasiewicz property, convergence rates can be derived for constant stepsize case. Numerical results demonstrate the efficiency of the algorithms.

Entity resolution identifies all records in a database that refer to the same entity. In this paper, we propose an unsupervised framework for entity resolution using blocking and graph algorithms. The records are partitioned into blocks with no redundancy for efficiency improvement. For intra-block data processing, we propose a graph-theoretic fusion framework with two components, namely ITER and CliqueRank. Specifically, ITER constructs a weighted bipartite graph between terms and record-record pairs and iteratively propagates the node salience until convergence. Subsequently, CliqueRank constructs a record graph to estimate the likelihood of two records resident in the same clique. The derived likelihood from CliqueRank is fed back to ITER to rectify the edge weight until a joint optimum can be reached. Experimental evaluation was conducted with 4 real datasets. Results show that our unsupervised framework is comparable or even superior to state-of-the-art deep learning approaches.

Conventional deep learning-based Relation Classification (RC) methods heavily rely on large-scale training dataset and fail to generalize to unseen classes when training data is scant. This work concentrates on RC tasks in few-shot scenarios in which models classify the unlabelled samples given only few labeled samples. Existing few-shot RC models consider the dataset as a series of individual instances and have not fully utilized interaction information among them. Interaction information is conducive to indicate the important areas and produce discriminating representations. So this paper proposes a novel interactive attention network (IAN) which uses inter-instance and intra-instance interactive information to classify the relations. Inter-instance interactive information is first introduced to solve the low-resource problem by capturing the semantic relevance between an instance pair. Intra-instance interactive information is then introduced to address the ambiguous relation classification issue by extracting the entity information inner an instance. Extensive numerical experimental results demonstrate the proposed method promotes the accuracy of down-stream task.

Graph pooling that summaries the information in a large graph into a compact form is essential in hierarchical graph representation learning. Existing graph pooling methods either suffer from high computational complexity or cannot capture the global dependencies between graphs before and after pooling. To address the problems of existing graph pooling methods, we propose Coarsened Grap hInfomaxPooling (CGIPool) that maximizes the mutual information between the input and the coarsened graph of each pooling layer to preserve graph-level dependencies. To achieve mutual information neural maximization, we apply contrastive learning and propose a self-attention-based algorithm for learning positive and negative samples. Extensive experimental results on seven datasets illustrate the superiority of CGIPool comparing to the state-of-the-art

Distant supervision provides a means to create a large number of weakly labeled data at low cost for relation classification. However, the resulting labeled instances are very noisy, containing data with wrong labels. Many approaches have been proposed to select a subset of reliable instances for neural model training, but they still suffer from noisy labeling problem or underutilization of the weakly-labeled data. To better select more reliable training instances, we introduce a small amount of manually labeled data as reference to guide the selection process. In this paper, we propose a meta-learning based approach, which learns to reweight noisy training data under the guidance of reference data. As the clean reference data is usually very small, we propose to augment it by dynamically distilling the most reliable elite instances from the noisy data. Experiments on several datasets demonstrate that the reference data can effectively guide the selection of training data, and our augmented approach consistently improves the performance of relation classification comparing to the existing state-of-the-art methods.

Traditional graph partitioning methods attempt to both minimize communication cost and guarantee load balancing in computation. However, the skewed degree distribution of natural graphs makes it difficult to simultaneously achieve the two objectives. This paper proposes topology refactorization (TR), a topology-aware method allowing graph-parallel systems to separately handle the two objectives: refactorization is mainly focused on reducing communication cost, and partitioning is mainly targeted for balancing the load. TR transforms a skewed graph into a more communication-efficient topology through fusion and fission , where the fusion operation organizes a set of neighboring low-degree vertices into a super-vertex, and the fission operation splits a high-degree vertex into a set of sibling sub-vertices. Based on TR, we design an efficient graph-parallel system (TopoX) which pipelines refactorization with partitioning to both reduce communication cost and balance computation load. Prototype evaluation shows that TopoX outperforms state-of-the-art PowerLyra by up to 78.5% (from 37.2%) on real-world graphs and is significantly faster than other graph-parallel systems, while only introducing small refactorization overhead and memory consumption.

Most existing author disambiguation work relies heavily on feature engineering or cannot use multiple paper relationships. In this work, we propose a network-embedding based method for author disambiguation. For each ambiguous name, we construct networks among papers sharing an ambiguous name, and connect papers with multiple relationships (e.g., co-authoring a paper). We focus on maximizing the gap between positive paper edges and negative edges, and propose a graph coarsening technique to learn global information. Further, we design a clustering algorithm which partitions paper representations into disjoint sets such that each set contains all papers of a unique author. Through extensive experiments, we show that our method is significantly better than the state-of-the-art author disambiguation and network-embedding methods.

Continuous proximity detection monitors the real-time positions of a large set of moving users and sends an alert as long as the distance of any matching pair is smaller than the threshold. Existing solutions construct either a static safe region with maximized area or a mobile safe region with constant speed and direction, which cannot not capture real motion patterns. In this paper, we propose a new type of safe region that relies on trajectory prediction techniques to significantly reduce the communication I/O. It takes into account the complex non-linear motion patterns and constructs a stripe to enclose the sequence of future locations as a predictive safe region. The stripe construction is guided by a holistic cost model with the objective of maximizing the expected time for the next communication. We conduct experiments on four real datasets with four types of prediction models and our method reduces the communication I/O by more than 30% in the default parameter settings.

Compressive spectral clustering (CSC) efficiently leverages graph filter and random sampling techniques to speed up clustering process. However, we find that CSC algorithm suffers from two main problems: i) The direct use of the dichotomy and eigencount techniques for estimating laplacian matrix’s k-th eigenvalue is expensive. ii) The computation of polynomial approximation repeats in each iteration for every cluster in the interpolation process, which occupies most of the computation time of CSC. To address these problems, we propose a new approach called FCSC for fast compressive spectral clustering. FCSC addresses the first problem by assuming that the eigenvalues approximately satisfy local uniform distribution, and addresses the second problem by recalculating the pairwise similarity between nodes with low-dimensional representation to reconstruct denoised laplacian matrix. The time complexity of reconstruction is linear with the number of non-zeros in laplacian matrix. As experimentally demonstrated on artificial and real-world datasets, our approach significantly reduces the computation time while preserving high clustering accuracy comparable to previous designs, verifying the effectiveness of FCSC.

With the increasing popularity of the peer-to-peer (P2P) computing paradigm, many general range query schemes for distributed hash table (DHT)-based P2P systems have been proposed in recent years. Although those schemes can provide range query capability without modifying the underlying DHTs, they have the query delay depending on both the scale of the system and the size of the query space or the specific query, and thus cannot guarantee to return the query results in a bounded delay. In this paper, we propose Armada, an efficient range query processing scheme to support delay-bounded single-attribute and multiple-attribute range queries. It is the first delay-bounded general range query scheme on constant-degree DHTs, and can return the results for any range query within 2logN hops in a P2P system with N peers. Results of analysis and simulations show that the average delay in Armada is less than logN, and the average message cost of single-attribute range queries is about logN+2n 2 (n is the number of peers that intersect with the query). These results are very close to the lower bounds on delay and message cost of range queries over constant-degree DHTs.