Fair graph learning plays a pivotal role in numerous practical applications. Recently, many fair graph learning methods have been proposed; however, their evaluation often relies on poorly constructed semi-synthetic datasets or substandard real-world datasets. In such cases, even a basic Multilayer Perceptron (MLP) can outperform Graph Neural Networks (GNNs) in both utility and fairness. In this work, we illustrate that many datasets fail to provide meaningful information in the edges, which may challenge the necessity of using graph structures in these problems. To address these issues, we develop and introduce a collection of synthetic, semi-synthetic, and real-world datasets that fulfill a broad spectrum of requirements. These datasets are thoughtfully designed to include relevant graph structures and bias information crucial for the fair evaluation of models. The proposed synthetic and semi-synthetic datasets offer the flexibility to create data with controllable bias parameters, thereby enabling the generation of desired datasets with user-defined bias values with ease. Moreover, we conduct systematic evaluations of these proposed datasets and establish a unified evaluation approach for fair graph learning models. Our extensive experimental results with fair graph learning methods across our datasets demonstrate their effectiveness in benchmarking the performance of these methods. Our datasets and the code for reproducing our experiments are available at //github.com/XweiQ/Benchmark-GraphFairness.
相關內容
Scaling the amount of compute used to train language models has dramatically improved their capabilities. However, when it comes to inference, we often limit the amount of compute to only one attempt per problem. Here, we explore inference compute as another axis for scaling by increasing the number of generated samples. Across multiple tasks and models, we observe that coverage - the fraction of problems solved by any attempt - scales with the number of samples over four orders of magnitude. In domains like coding and formal proofs, where all answers can be automatically verified, these increases in coverage directly translate into improved performance. When we apply repeated sampling to SWE-bench Lite, the fraction of issues solved with DeepSeek-V2-Coder-Instruct increases from 15.9% with one sample to 56% with 250 samples, outperforming the single-attempt state-of-the-art of 43% which uses more capable frontier models. Moreover, using current API pricing, amplifying the cheaper DeepSeek model with five samples is more cost-effective and solves more issues than paying a premium for one sample from GPT-4o or Claude 3.5 Sonnet. Interestingly, the relationship between coverage and the number of samples is often log-linear and can be modelled with an exponentiated power law, suggesting the existence of inference-time scaling laws. Finally, we find that identifying correct samples out of many generations remains an important direction for future research in domains without automatic verifiers. When solving math word problems from GSM8K and MATH, coverage with Llama-3 models grows to over 95% with 10,000 samples. However, common methods to pick correct solutions from a sample collection, such as majority voting or reward models, plateau beyond several hundred samples and fail to fully scale with the sample budget.
Unsupervised embeddings are fundamental to numerous machine learning applications, yet their evaluation remains a challenging task. Traditional assessment methods often rely on extrinsic variables, such as performance in downstream tasks, which can introduce confounding factors and mask the true quality of embeddings. This paper introduces the Intrinsic Distance Preservation Evaluation (IDPE) method, a novel approach for assessing embedding quality based on the preservation of Mahalanobis distances between data points in the original and embedded spaces. We demonstrate the limitations of extrinsic evaluation methods through a simple example, highlighting how they can lead to misleading conclusions about embedding quality. IDPE addresses these issues by providing a task-independent measure of how well embeddings preserve the intrinsic structure of the original data. Our method leverages efficient similarity search techniques to make it applicable to large-scale datasets. We compare IDPE with established intrinsic metrics like trustworthiness and continuity, as well as extrinsic metrics such as Average Rank and Mean Reciprocal Rank. Our results show that IDPE offers a more comprehensive and reliable assessment of embedding quality across various scenarios. We evaluate PCA and t-SNE embeddings using IDPE, revealing insights into their performance that are not captured by traditional metrics. This work contributes to the field by providing a robust, efficient, and interpretable method for embedding evaluation. IDPE's focus on intrinsic properties offers a valuable tool for researchers and practitioners seeking to develop and assess high-quality embeddings for diverse machine learning applications.
Machine Learning has made remarkable progress in a wide range of fields. In many scenarios, learning is performed on datasets involving sensitive information, in which privacy protection is essential for learning algorithms. In this work, we study pure private learning in the agnostic model -- a framework reflecting the learning process in practice. We examine the number of users required under item-level (where each user contributes one example) and user-level (where each user contributes multiple examples) privacy and derive several improved upper bounds. For item-level privacy, our algorithm achieves a near optimal bound for general concept classes. We extend this to the user-level setting, rendering a tighter upper bound than the one proved by Ghazi et al. (2023). Lastly, we consider the problem of learning thresholds under user-level privacy and present an algorithm with a nearly tight user complexity.
Generative art is a rules-driven approach to creating artistic outputs in various mediums. For example, a fluid simulation can govern the flow of colored pixels across a digital display or a rectangle placement algorithm can yield a Mondrian-style painting. Previously, we investigated how genetic improvement, a sub-field of genetic programming, can automatically create and optimize generative art drawing programs. One challenge of applying genetic improvement to generative art is defining fitness functions and their interaction in a many-objective evolutionary algorithm such as Lexicase selection. Here, we assess the impact of each fitness function in terms of the their individual effects on generated images, characteristics of generated programs, and impact of bloat on this specific domain. Furthermore, we have added an additional fitness function that uses a classifier for mimicking a human's assessment as to whether an output is considered as "art." This classifier is trained on a dataset of input images resembling the glitch art aesthetic that we aim to create. Our experimental results show that with few fitness functions, individual generative techniques sweep across populations. Moreover, we found that compositions tended to be driven by one technique with our current fitness functions. Lastly, we show that our classifier is best suited for filtering out noisy images, ideally leading towards more outputs relevant to user preference.
The use of quantum cryptography in everyday applications has gained attention in both industrial and academic fields. Due to advancements in quantum electronics, practical quantum devices are already available in the market, and ready for wider use. Quantum Key Distribution (QKD) is a crucial aspect of quantum cryptography, which involves generating and distributing symmetric cryptographic keys between geographically separated users using principles of quantum physics. Many successful QKD networks have been established to test different solutions. The objective of this paper is to delve into the potential of utilizing established routing design techniques in the context of quantum key distribution, a field distinguished by its unique properties rooted in the principles of quantum mechanics. However, the implementation of these techniques poses substantial challenges, including quantum memory decoherence, key rate generation, latency delays, inherent noise in quantum systems, limited communication ranges, and the necessity for highly specialized hardware. This paper conducts an in-depth examination of essential research pertaining to the design methodologies for quantum key distribution. It also explores the fundamental aspects of quantum routing and the associated properties inherent to quantum QKD. This paper elucidates the necessary steps for constructing efficient and resilient QKD networks. In summarizing the techniques relevant to QKD networking and routing, including their underlying principles, protocols, and challenges, this paper sheds light on potential applications and delineates future research directions in this burgeoning field.
In pace with developments in the research field of artificial intelligence, knowledge graphs (KGs) have attracted a surge of interest from both academia and industry. As a representation of semantic relations between entities, KGs have proven to be particularly relevant for natural language processing (NLP), experiencing a rapid spread and wide adoption within recent years. Given the increasing amount of research work in this area, several KG-related approaches have been surveyed in the NLP research community. However, a comprehensive study that categorizes established topics and reviews the maturity of individual research streams remains absent to this day. Contributing to closing this gap, we systematically analyzed 507 papers from the literature on KGs in NLP. Our survey encompasses a multifaceted review of tasks, research types, and contributions. As a result, we present a structured overview of the research landscape, provide a taxonomy of tasks, summarize our findings, and highlight directions for future work.
Deep learning has been the mainstream technique in natural language processing (NLP) area. However, the techniques require many labeled data and are less generalizable across domains. Meta-learning is an arising field in machine learning studying approaches to learn better learning algorithms. Approaches aim at improving algorithms in various aspects, including data efficiency and generalizability. Efficacy of approaches has been shown in many NLP tasks, but there is no systematic survey of these approaches in NLP, which hinders more researchers from joining the field. Our goal with this survey paper is to offer researchers pointers to relevant meta-learning works in NLP and attract more attention from the NLP community to drive future innovation. This paper first introduces the general concepts of meta-learning and the common approaches. Then we summarize task construction settings and application of meta-learning for various NLP problems and review the development of meta-learning in NLP community.
As an effective strategy, data augmentation (DA) alleviates data scarcity scenarios where deep learning techniques may fail. It is widely applied in computer vision then introduced to natural language processing and achieves improvements in many tasks. One of the main focuses of the DA methods is to improve the diversity of training data, thereby helping the model to better generalize to unseen testing data. In this survey, we frame DA methods into three categories based on the diversity of augmented data, including paraphrasing, noising, and sampling. Our paper sets out to analyze DA methods in detail according to the above categories. Further, we also introduce their applications in NLP tasks as well as the challenges.
Deep learning methods are achieving ever-increasing performance on many artificial intelligence tasks. A major limitation of deep models is that they are not amenable to interpretability. This limitation can be circumvented by developing post hoc techniques to explain the predictions, giving rise to the area of explainability. Recently, explainability of deep models on images and texts has achieved significant progress. In the area of graph data, graph neural networks (GNNs) and their explainability are experiencing rapid developments. However, there is neither a unified treatment of GNN explainability methods, nor a standard benchmark and testbed for evaluations. In this survey, we provide a unified and taxonomic view of current GNN explainability methods. Our unified and taxonomic treatments of this subject shed lights on the commonalities and differences of existing methods and set the stage for further methodological developments. To facilitate evaluations, we generate a set of benchmark graph datasets specifically for GNN explainability. We summarize current datasets and metrics for evaluating GNN explainability. Altogether, this work provides a unified methodological treatment of GNN explainability and a standardized testbed for evaluations.
Machine learning techniques have deeply rooted in our everyday life. However, since it is knowledge- and labor-intensive to pursue good learning performance, human experts are heavily involved in every aspect of machine learning. In order to make machine learning techniques easier to apply and reduce the demand for experienced human experts, automated machine learning (AutoML) has emerged as a hot topic with both industrial and academic interest. In this paper, we provide an up to date survey on AutoML. First, we introduce and define the AutoML problem, with inspiration from both realms of automation and machine learning. Then, we propose a general AutoML framework that not only covers most existing approaches to date but also can guide the design for new methods. Subsequently, we categorize and review the existing works from two aspects, i.e., the problem setup and the employed techniques. Finally, we provide a detailed analysis of AutoML approaches and explain the reasons underneath their successful applications. We hope this survey can serve as not only an insightful guideline for AutoML beginners but also an inspiration for future research.
小貼士
登錄享
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191