Graph neural networks (GNNs) have demonstrated remarkable success in numerous graph analytical tasks. Yet, their effectiveness is often compromised in real-world scenarios due to distribution shifts, limiting their capacity for knowledge transfer across changing environments or domains. Recently, Unsupervised Graph Domain Adaptation (UGDA) has been introduced to resolve this issue. UGDA aims to facilitate knowledge transfer from a labeled source graph to an unlabeled target graph. Current UGDA efforts primarily focus on model-centric methods, such as employing domain invariant learning strategies and designing model architectures. However, our critical examination reveals the limitations inherent to these model-centric methods, while a data-centric method allowed to modify the source graph provably demonstrates considerable potential. This insight motivates us to explore UGDA from a data-centric perspective. By revisiting the theoretical generalization bound for UGDA, we identify two data-centric principles for UGDA: alignment principle and rescaling principle. Guided by these principles, we propose GraphAlign, a novel UGDA method that generates a small yet transferable graph. By exclusively training a GNN on this new graph with classic Empirical Risk Minimization (ERM), GraphAlign attains exceptional performance on the target graph. Extensive experiments under various transfer scenarios demonstrate the GraphAlign outperforms the best baselines by an average of 2.16%, training on the generated graph as small as 0.25~1% of the original training graph.
论文检索
输入标题、作者或关键词，从 642 篇学术成果中精准定位
The robustness of large language models (LLMs) becomes increasingly important as their use rapidly grows in a wide range of domains. Retrieval-Augmented Generation (RAG) is considered as a means to improve the trustworthiness of text generation from LLMs. However, how the outputs from RAG-based LLMs are affected by slightly different inputs is not well studied. In this work, we find that the insertion of even a short prefix to the prompt leads to the generation of outputs far away from factually correct answers. We systematically evaluate the effect of such prefixes on RAG by introducing a novel optimization technique called Gradient Guided Prompt Perturbation (GGPP). GGPP achieves a high success rate in steering outputs of RAG-based LLMs to targeted wrong answers. It can also cope with instructions in the prompts requesting to ignore irrelevant context. We also exploit LLMs' neuron activation difference between prompts with and without GGPP perturbations to give a method that improves the robustness of RAG-based LLMs through a highly effective detector trained on neuron activation triggered by GGPP generated prompts. Our evaluation on open-sourced LLMs demonstrates the effectiveness of our methods.
In the era of large language models (LLMs), efficient and accurate data retrieval has become increasingly crucial for the use of domain-specific or private data in the retrieval augmented generation (RAG). Neural graph databases (NGDBs) have emerged as a powerful paradigm that combines the strengths of graph databases (GDBs) and neural networks to enable efficient storage, retrieval, and analysis of graph-structured data which can be adaptively trained with LLMs. The usage of neural embedding storage and Complex neural logical Query Answering (CQA) provides NGDBs with generalization ability. When the graph is incomplete, by extracting latent patterns and representations, neural graph databases can fill gaps in the graph structure, revealing hidden relationships and enabling accurate query answering. Nevertheless, this capability comes with inherent trade-offs, as it introduces additional privacy risks to the domain-specific or private databases. Malicious attackers can infer more sensitive information in the database using well-designed queries such as from the answer sets of where Turing Award winners born before 1950 and after 1940 lived, the living places of Turing Award winner Hinton are probably exposed, although the living places may have been deleted in the training stage due to the privacy concerns. In this work, we propose a privacy-preserved neural graph database (P-NGDB) framework to alleviate the risks of privacy leakage in NGDBs. We introduce adversarial training techniques in the training stage to enforce the NGDBs to generate indistinguishable answers when queried with private information, enhancing the difficulty of inferring sensitive information through combinations of multiple innocuous queries. Extensive experimental results on three datasets show that our framework can effectively protect private information in the graph database while delivering high-quality public answers responses to queries. The code is available at https://github.com/HKUST-KnowComp/PrivateNGDB.
Although Federated Learning (FL) enables global model training across clients without compromising their raw data, due to the unevenly distributed data among clients, existing Federated Averaging (FedAvg)-based methods suffer from the problem of low inference performance. Specifically, different data distributions among clients lead to various optimization directions of local models. Aggregating local models usually results in a low-generalized global model, which performs worse on most of the clients. To address the above issue, inspired by the observation from a geometric perspective that a well-generalized solution is located in a flat area rather than a sharp area, we propose a novel and heuristic FL paradigm named FedMR (Federated Model Recombination). The goal of FedMR is to guide the recombined models to be trained towards a flat area. Unlike conventional FedAvg-based methods, in FedMR, the cloud server recombines collected local models by shuffling each layer of them to generate multiple recombined models for local training on clients rather than an aggregated global model. Since the area of the flat area is larger than the sharp area, when local models are located in different areas, recombined models have a higher probability of locating in a flat area. When all recombined models are located in the same flat area, they are optimized towards the same direction. We theoretically analyze the convergence of model recombination. Experimental results show that, compared with state-of-the-art FL methods, FedMR can significantly improve the inference accuracy without exposing the privacy of each client.
Placement is a critical and challenging step of modern chip design, with routability being an essential indicator of placement quality. Current routability-oriented placers typically apply an iterative two-stage approach, wherein the first stage generates a placement solution, and the second stage provides non-differentiable routing results to heuristically improve the solution quality. This method hinders jointly optimizing the routability aspect during placement. To address this problem, this work introduces RoutePlacer, an end-to-end routability-aware placement method. It trains RouteGNN, a customized graph neural network, to efficiently and accurately predict routability by capturing and fusing geometric and topological representations of placements. Well-trained RouteGNN then serves as a differentiable approximation of routability, enabling end-to-end gradient-based routability optimization. In addition, RouteGNN can improve two-stage placers as a plug-and-play alternative to external routers. Our experiments on DREAMPlace, an open-source AI4EDA platform, show that RoutePlacer can reduce Total Overflow by up to 16% while maintaining routed wirelength, compared to the state-of-the-art; integrating RouteGNN within two-stage placers leads to a 44% reduction in Total Overflow without compromising wirelength.
We study the stochastic Budgeted Multi-Armed Bandit (MAB) problem, where a player chooses from K arms with unknown expected rewards and costs. The goal is to maximize the total reward under a budget constraint. A player thus seeks to choose the arm with the highest reward-cost ratio as often as possible. Current approaches for this problem have several issues, which we illustrate. To overcome them, we propose a new upper confidence bound (UCB) sampling policy, ømega-UCB, that uses asymmetric confidence intervals. These intervals scale with the distance between the sample mean and the bounds of a random variable, yielding a more accurate and tight estimation of the reward-cost ratio compared to our competitors. We show that our approach has sublinear instance-dependent regret in general and logarithmic regret for parameter ρ ≥ 1, and that it outperforms existing policies consistently in synthetic and real settings.
As its availability and generality in online services, implicit feedback is more commonly used in recommender systems. However, implicit feedback usually presents noisy samples in real-world recommendation scenarios (such as misclicks or non-preferential behaviors), which will affect precise user preference learning. To overcome the noisy samples problem, a popular solution is based on dropping noisy samples in the model training phase, which follows the observation that noisy samples have higher training losses than clean samples. Despite the effectiveness, we argue that this solution still has limits. (1) High training losses can result from model optimization instability or hard samples, not just noisy samples. (2) Completely dropping of noisy samples will aggravate the data sparsity, which lacks full data exploitation. To tackle the above limitations, we propose a Double Correction Framework for Denoising Recommendation (DCF), which contains two correction components from views of more precise sample dropping and avoiding more sparse data. In the sample dropping correction component, we use the loss value of the samples over time to determine whether it is noise or not, increasing dropping stability. Instead of averaging directly, we use the damping function to reduce the bias effect of outliers. Furthermore, due to the higher variance exhibited by hard samples, we derive a lower bound for the loss through concentration inequality to identify and reuse hard samples. In progressive label correction, we iteratively re-label highly deterministic noisy samples and retrain them to further improve performance. Finally, extensive experimental results on three datasets and four backbones demonstrate the effectiveness and generalization of our proposed framework.
Despite the encouraging successes in numerous applications, machine learning methods grounded on the i.i.d. assumption often experience performance deterioration when confronted with the distribution shift between training and test data. This challenge has instigated recent research endeavors focusing on out-of-distribution (OOD) generalization. A particularly pervasive and intricate OOD problem is to enhance the model's generalization ability by training it on samples drawn from a single environment. In response to the problem, we propose a simple model-agnostic method tailored for a practical OOD scenario in this paper. Our approach centers on pursuing robust weighted empirical risks, utilizing randomly shifted training distributions derived through a specific sample-based weighting strategy. Furthermore, we theoretically establish that the expected risk of the shifted training distribution can bound the expected risk of the test distribution. This theoretical foundation ensures the improved prediction performance of our method when employed in uncertain test distributions. Extensive experiments conducted on diverse real-world datasets affirm the effectiveness of our method, highlighting its potential to address the distribution shifts in machine learning applications.
An Efficient Local Search Algorithm for Large GD Advertising Inventory Allocation with Multilinear Constraints
PDF ↗The Guaranteed Delivery (GD) advertising is a crucial component of the online advertising industry, and the allocation of inventory in GD advertising is an important procedure that influences directly the ability of the publisher to fulfill the requirements and increase its revenues. Nowadays, as the requirements of advertisers become more and more diverse and fine-grained, the focus ratio requirement, which states that the portion of allocated impressions of a designated contract on focus media among all possible media should be greater than another contract, often appears in business scenarios. However, taking these requirements into account brings hardness for the GD advertising inventory allocation as the focus ratio requirements involve non-convex multilinear constraints. Existing methods which rely on the convex properties are not suitable for processing this problem, while mathematical programming or constraint-based heuristic solvers are unable to produce high-quality solutions within the time limit. Therefore, we propose a local search framework to address this challenge. It incorporates four new operators designed for handling multilinear constraints and a two-mode algorithmic architecture. Experimental results demonstrate that our algorithm is able to compute high-quality allocations with better business metrics compared to the state-of-the-art mathematical programming or constraint based heuristic solvers. Moreover, our algorithm is able to handle the general multilinear constraints and we hope it could be used to solve other problems in GD advertising with similar requirements.
A Unified Core Structure in Multiplex Networks: From Finding the Densest Subgraph to Modeling User Engagement
PDF ↗In many complex systems, the interactions between objects span multiple aspects. Multiplex networks are accurate paradigms to model such systems, where each edge is associated with a type. A key graph mining primitive is extracting dense subgraphs, and this has led to interesting notions such as k-cores, known as building blocks of complex networks. Despite recent attempts to extend the notion of core to multiplex networks, existing studies suffer from a subset of the following limitations: They (1) force all nodes to exhibit their high degree in the same set of relation types while in multiplex networks some connection types can be noisy for some nodes, (2) either require high computational cost or miss the complex information of multiplex networks, and (3) assume the same importance for all relation types. We introduce Score, a novel and unifying family of dense structures in multiplex networks that uses a function S(.) to summarize the degree vector of each node. We then discuss how one can choose a proper S(.) from the data. To demonstrate the usefulness of Scores, we focus on finding the densest subgraph as well as modeling user engagement in multiplex networks. We present a new density measure in multiplex networks and discuss its advantages over existing density measures. We show that the problem of finding the densest subgraph in multiplex networks is NP-hard and design an efficient approximation algorithm based on Scores. Finally, we present a new mathematical model of user engagement in the presence of different relation types. Our experiments shows the efficiency and effectiveness of our algorithms and supports the proposed mathematical model of user engagement.
Expander decompositions of graphs have significantly advanced the understanding of many classical graph problems and led to numerous fundamental theoretical results. However, their adoption in practice has been hindered due to their inherent intricacies and large hidden factors in their asymptotic running times. Here, we introduce the first practically efficient algorithm for computing expander decompositions and their hierarchies and demonstrate its effectiveness and utility by incorporating it as the core component in a novel solver for the normalized cut graph clustering objective. Our extensive experiments on a variety of large graphs show that our expander-based algorithm outperforms state-of-the-art solvers for normalized cut with respect to solution quality by a large margin on a variety of graph classes such as citation, e-mail, and social networks or web graphs while remaining competitive in running time.
Adapting Job Recommendations to User Preference Drift with Behavioral-Semantic Fusion Learning
PDF ↗Job recommender systems are crucial for aligning job opportunities with job-seekers in online job-seeking. However, users tend to adjust their job preferences to secure employment opportunities continually, which limits the performance of job recommendations. The inherent frequency of preference drift poses a challenge to promptly and precisely capture user preferences. To address this issue, we propose a novel session-based framework, BISTRO, to timely model user preference through fusion learning of semantic and behavioral information. Specifically, BISTRO is composed of three stages: 1) coarse-grained semantic clustering, 2) fine-grained job preference extraction, and 3) personalized top-k job recommendation. Initially, BISTRO segments the user interaction sequence into sessions and leverages session-based semantic clustering to achieve broad identification of person-job matching. Subsequently, we design a hypergraph wavelet learning method to capture the nuanced job preference drift. To mitigate the effect of noise in interactions caused by frequent preference drift, we innovatively propose an adaptive wavelet filtering technique to remove noisy interaction. Finally, a recurrent neural network is utilized to analyze session-based interaction for inferring personalized preferences. Extensive experiments on three real-world offline recruitment datasets demonstrate the significant performances of our framework. Significantly, BISTRO also excels in online experiments, affirming its effectiveness in live recruitment settings. This dual success underscores the robustness and adaptability of BISTRO. The source code is available at https://github.com/Applied-Machine-Learning-Lab/BISTRO.
Many evaluation metrics can be used to assess the performance of models in binary classification tasks. However, most of them are derived from a confusion matrix in a non-differentiable form, making it very difficult to generate a differentiable loss function that could directly optimize them. The lack of solutions to bridge this challenge not only hinders our ability to solve difficult tasks, such as imbalanced learning, but also requires the deployment of computationally expensive hyperparameter search processes in model selection. In this paper, we propose a general-purpose approach that transforms any confusion matrix-based metric into a loss function, AnyLoss, that is available in optimization processes. To this end, we use an approximation function to make a confusion matrix represented in a differentiable form, and this approach enables any confusion matrix-based metric to be directly used as a loss function. The mechanism of the approximation function is provided to ensure its operability and the differentiability of our loss functions is proved by suggesting their derivatives. We conduct extensive experiments under diverse neural networks with many datasets, and we demonstrate their general availability to target any confusion matrix-based metrics. Our method, especially, shows outstanding achievements in dealing with imbalanced datasets, and its competitive learning speed, compared to multiple baseline models, underscores its efficiency.
For natural language understanding and generation, embedding concepts using an order-based representation is an essential task. Unlike traditional point vector based representation, an order-based representation imposes geometric constraints on the representation vectors for explicitly capturing various semantic relationships that may exist between a pair of concepts. In existing literature, several approaches on order-based embedding have been proposed, mostly focusing on capturing hierarchical relationships; examples include vectors in Euclidean space, complex, Hyperbolic, order, and Box Embedding. Box embedding creates region-based rich representation of concepts, but along the process it sacrifices simplicity, requiring a custom-made optimization scheme for learning the representation. Hyperbolic embedding improves embedding quality by exploiting the ever-expanding property of Hyperbolic space, but it also suffers from the same fate as box embedding as gradient descent like optimization is not simple in the Hyperbolic space. In this work, we propose Binder, a novel approach for order-based representation. Binder uses binary vectors for embedding, so the embedding vectors are compact with an order of magnitude smaller footprint than other methods. Binder uses a simple and efficient optimization scheme for learning representation vectors with a linear time complexity. Our comprehensive experimental results show that Binder is very accurate, yielding competitive results on the representation task. But Binder stands out from its competitors on the transitive closure link prediction task as it can learn concept embeddings just from the direct edges, whereas all existing order-based approaches rely on the indirect edges. In particular, Binder achieves a whopping 70% higher F1-score than the second best method (98.6% vs 29%) in our largest dataset, WordNet Nouns (743,241 edges), when using only direct edges during training.
Federated Graph Learning (FGL) has emerged as a promising way to learn high-quality representations from distributed graph data with privacy preservation. Despite considerable efforts have been made for FGL under either cross-device or cross-silo paradigm, how to effectively capture graph knowledge in a more complicated cross-silo cross-device environment remains an under-explored problem. However, this task is challenging because of the inherent hierarchy and heterogeneity of decentralized clients, diversified privacy constraints in different clients, and the cross-client graph integrity requirement. To this end, in this paper, we propose a Hierarchical Federated Graph Learning (HiFGL) framework for cross-silo cross-device FGL. Specifically, we devise a unified hierarchical architecture to safeguard federated GNN training on heterogeneous clients while ensuring graph integrity. Moreover, we propose a Secret Message Passing (SecMP) scheme to shield unauthorized access to subgraph-level and node-level sensitive information simultaneously. Theoretical analysis proves that HiFGL achieves multi-level privacy preservation with complexity guarantees. Extensive experiments on real-world datasets validate the superiority of the proposed framework against several baselines. Furthermore, HiFGL's versatile nature allows for its application in either solely cross-silo or cross-device settings, further broadening its utility in real-world FGL applications.
Rankings are increasingly used as part of human decision-making processes to most effectively allocate reviewing resources. Many of these processes have complex constraints, and we identify slot constraints as a model for a wide range of application problems -- from college admission with limited slots for different majors, to composing a stratified cohort of eligible participants in a medical trial. In this paper, we formalize the slot-constrained ranking problem as producing a ranking that maximizes the number of filled slots if candidates are evaluated by a human decision maker for slot eligibility in the order of the ranking. We show that naive adaptations of the Probability Ranking Principle (PRP) can be highly sub-optimal for slot-constrained ranking problems, and we devise a new ranking algorithm, called MatchRank. MatchRank generalizes the PRP, and it subsumes the PRP as a special case when there are no slot constraints. Our theoretical analysis shows that MatchRank has a strong approximation guarantee without any independence assumptions between slots or candidates. Furthermore, we show how MatchRank can be implemented efficiently. Beyond the theoretical guarantees, empirical evaluations show that MatchRank can provide substantial improvements over a range of synthetic and real-world tasks.
Tripartite graph-based recommender systems markedly diverge from traditional models by recommending unique combinations such as user groups and item bundles. Despite their effectiveness, these systems exacerbate the long-standing cold-start problem in traditional recommender systems, because any number of user groups or item bundles can be formed among users or items. To address this issue, we introduce a Consistency and Discrepancy-based graph contrastive learning method for tripartite graph-based Recommendation (CDR). This approach leverages two novel meta-path-based metrics-consistency and discrepancy-to capture nuanced, implicit associations between the recommended objects and the recommendees. These metrics, indicative of high-order similarities, can be efficiently calculated with infinite graph convolutional networks (GCN) layers under a multi-objective optimization framework, using the limit theory of GCN. Additionally, we introduce a novel Contrastive Divergence (CD) loss, which can seamlessly integrate the consistency and discrepancy metrics into the contrastive objective as the positive and contrastive supervision signals to learn node representations, enhancing the pairwise ranking of recommended objects and proving particularly valuable in severe cold-start scenarios. Extensive experiments demonstrate the effectiveness of the proposed CDR. The code is released at https://github.com/foodfaust/CDR.
Graph neural networks (GNNs) have exhibited remarkable performance under the assumption that test data comes from the same distribution of training data. However, in real-world scenarios, this assumption may not always be valid. Consequently, there is a growing focus on exploring the Out-of-Distribution (OOD) problem in the context of graphs. Most existing efforts have primarily concentrated on improving graph OOD generalization from two model-agnostic perspectives: data-driven methods and strategy-based learning. However, there has been limited attention dedicated to investigating the impact of well-known GNN model architectures on graph OOD generalization, which is orthogonal to existing research. In this work, we provide the first comprehensive investigation of OOD generalization on graphs from an architecture perspective, by examining the common building blocks of modern GNNs. Through extensive experiments, we reveal that both the graph self-attention mechanism and the decoupled architecture contribute positively to graph OOD generalization. In contrast, we observe that the linear classification layer tends to compromise graph OOD generalization capability. Furthermore, we provide in-depth theoretical insights and discussions to underpin these discoveries. These insights have empowered us to develop a novel GNN backbone model, DGat, designed to harness the robust properties of both graph self-attention mechanism and the decoupled architecture. Extensive experimental results demonstrate the effectiveness of our model under graph OOD, exhibiting substantial and consistent enhancements across various training strategies. Our codes are available at https://github.com/KaiGuo20/DGAT **REMOVE 2nd URL**://github.com/KaiGuo20/DGAT.
Benefiting from the effective exploitation of the high-order correlations across multiple views, tensor-based multi-view clustering (TMVC) has garnered considerable attention in recent years. Nevertheless, prior TMVC techniques commonly involve assembling multiple view-specific spatial similarity graphs into a three-dimensional tensor, overlooking the intrinsic topological structure essential for precise clustering of data within a manifold. Additionally, mainstream techniques are constrained by equally shrinking all singular values to recover a low-rank tensor, limiting their capacity to distinguish significant variations among different singular values. In this investigation, we present an innovative TMVC framework termed toPology-driven multi-view clustering viA refined teNsorial sigmoiD rAnk minimization (PANDA ). Specifically, PANDA extracts view-specific topological structures from Euclidean graphs and intricately integrates them into a low-rank three-dimensional tensor, facilitating the concurrent utilization of intra-view topological connectivity and inter-view high-order correlations. Moreover, we develop a refined sigmoid function as the tighter surrogate to tensor rank, enabling the exploration of significant information of heterogeneous singular values. Meanwhile, the topological structures are merged into a unified structure with varying weights, associated with a connectivity constraint, empowering the significant divergence among views and the explicit cluster structure of the target graph are simultaneously leveraged. Extensive experiments demonstrate the superiority of PANDA, outperforming SOTA methods.
Graph neural networks have garnered notable attention for effectively processing graph-structured data. Prevalent models prioritize improving in-distribution (IND) data performance, frequently overlooking the risks from potential out-of-distribution (OOD) nodes during training and inference. In real-world graphs, the automated network construction can introduce noisy nodes from unknown distributions. Previous research into OOD node detection, typically referred to as entropy-based methods, calculates OOD measurements from the prediction entropy alongside category classification training. However, the nodes in the graph might not be pre-labeled with specific categories, rendering entropy-based OOD detectors inapplicable in such category-free situations. To tackle this issue, we propose an energy-centric density estimation framework for OOD node detection, referred to as EnergyDef. Within this framework, we introduce an energy-based GNN to compute node energies that act as indicators of node density and reveal the OOD uncertainty of nodes. Importantly, EnergyDef can efficiently identify OOD nodes with low-resource OOD node annotations, achieved by sampling hallucinated nodes via Langevin Dynamics and structure estimation, along with training through Contrastive Divergence. Our comprehensive experiments on real-world datasets substantiate that our framework markedly surpasses state-of-the-art methods in terms of detection quality, even under conditions of scarce or entirely absent OOD node annotations.