论文检索

Sakhawat Hossain Saimon, Tanzira Najnin, Jianhua Ruan

Classification tasks in many real-world domains are exacerbated by class imbalance, relatively small sample sizes compared to high dimensionality, and measurement uncertainty. The problem of class imbalance has been extensively studied, and data augmentation methods based on interpolation of minority class instances have been proposed as a viable solution to mitigate imbalance. It remains to be seen whether augmentation can be applied to improve the overall performance while maintaining stability, especially with a limited number of samples. In this paper, we present a novel feature-space augmentation technique that can be applied to high-dimensional data for classification tasks and address these issues. Our method utilizes uniform random sampling and introduces synthetic instances by taking advantage of the local distributions of individual features in the observed instances. The core augmentation algorithm is class-invariant, which opens up an unexplored avenue of simultaneously improving and stabilizing performance by augmenting unlabeled instances. The proposed method is evaluated using a comprehensive performance analysis involving multiple classifiers and metrics. Comparative analysis with existing feature space augmentation methods strongly suggests that the proposed algorithm can result in improved classification performance while also increasing the overall reliability of the performance evaluation.

Jingqing Ruan, Ziyue Li 0002, Hua Wei 0001, Haoyuan Jiang, Jiaming Lu, Xuantang Xiong, Hangyu Mao, Rui Zhao 0001

该来源暂未提供摘要。

Luis Roque, Carlos Soares, Luís Torgo

We introduce the Robustness of Hierarchically Organized Time Series (RHiOTS) framework, designed to assess the robustness of hierarchical time series forecasting models and algorithms on real-world datasets. Hierarchical time series, where lower-level forecasts must sum to upper-level ones, are prevalent in various contexts, such as retail sales across countries. Current empirical evaluations of forecasting methods are often limited to a small set of benchmark datasets, offering a narrow view of algorithm behavior. RHiOTS addresses this gap by systematically altering existing datasets and modifying the characteristics of individual series and their interrelations. It uses a set of parameterizable transformations to simulate those changes in the data distribution. Additionally, RHiOTS incorporates an innovative visualization component, turning complex, multidimensional robustness evaluation results into intuitive, easily interpretable visuals. This approach allows an in-depth analysis of algorithm and model behavior under diverse conditions. We illustrate the use of RHiOTS by analyzing the predictive performance of several algorithms. Our findings show that traditional statistical methods are more robust than state-of-the-art deep learning algorithms, except when the transformation effect is highly disruptive. Furthermore, we found no significant differences in the robustness of the algorithms when applying specific reconciliation methods, such as MinT. RHiOTS provides researchers with a comprehensive tool for understanding the nuanced behavior of forecasting algorithms, offering a more reliable basis for selecting the most appropriate method for a given problem.

Ahsanur Rahman 0001, Kalyan Roy, Ramiza Maliha, Townim Faisal Chowdhury

Pseudo-cliques (subgraphs with almost all possible edges) have many applications. But they do not satisfy the convertible antimonotone constraint (as we prove here). So, it is hard to reduce the search space of pseudo-cliques and list them efficiently. To our knowledge, only two exact algorithms, namely, ODES and PCE, were proposed for this purpose, but both have high execution times. Here, we present an exact algorithm named Fast Pseudo-Clique Enumerator (FPCE). It employs some pruning techniques we derived to reduce the search space. Our experiment on 15 real and 16 synthetic graphs shows that (i) on real graphs, FPCE is, on average, 38.6 and 6.5 times faster than ODES and PCE, respectively, whereas (ii) on synthetic graphs, FPCE is, on average, 39.7 and 3.1 times faster than ODES and PCE, respectively. We apply FPCE and a popular heuristic method on a PPI network to identify pseudo-cliques. FPCE outputs match with more known protein complexes, are more accurate, and are biologically more significant - suggesting that the exact computation of pseudo-cliques may give better insights. For its speed, FPCE is a suitable choice in such cases.

Meng Qin 0002, Chaorui Zhang, Yu Gao 0041, Weixi Zhang, Dit-Yan Yeung

Community detection (CD) is a classic graph inference task that partitions nodes of a graph into densely connected groups. While many CD methods have been proposed with either impressive quality or efficiency, balancing the two aspects remains a challenge. This study explores the potential of deep graph learning to achieve a better trade-off between the quality and efficiency of K-agnostic CD, where the number of communities K is unknown. We propose PRoCD (Pre-training & Refinement fOr Community Detection), a simple yet effective method that reformulates K-agnostic CD as the binary node pair classification. PRoCD follows a pre-training & refinement paradigm inspired by recent advances in pre-training techniques. We first conduct the offline pre-training of PRoCD on small synthetic graphs covering various topology properties. Based on the inductive inference across graphs, we then generalize the pre-trained model (with frozen parameters) to large real graphs and use the derived CD results as the initialization of an existing efficient CD method (e.g., InfoMap) to further refine the quality of CD results. In addition to benefiting from the transfer ability regarding quality, the online generalization and refinement can also help achieve high inference efficiency, since there is no time-consuming model optimization. Experiments on public datasets with various scales demonstrate that PRoCD can ensure higher efficiency in K-agnostic CD without significant quality degradation.

Hong Qian, Shuo Liu 0017, Mingjia Li 0002, Bingdong Li, Zhi Liu, Aimin Zhou

该来源暂未提供摘要。

Chen Qian 0006, Huayi Tang, Hong Liang, Yong Liu 0018

Recently, Graph Neural Networks (GNNs) have achieved inspiring performances in graph classification tasks. However, the message passing mechanism in GNNs implicitly utilizes the topological information of the graph, which may lead to a potential loss of structural information. Furthermore, the graph classification decision process based on GNNs resembles a black box and lacks sufficient transparency. The non-linear classifier following the GNNs also defaults to the assumption that each class is represented by a single vector, thereby limiting the diversity of intra-class representations. To address these issues, we propose a novel prototype-based graph classification framework that introduces the Fused Gromov-Wasserstein (FGW) distance in Optimal Transport (OT) as the similarity measure. In this way, the model explicitly exploits the structural information on the graph through OT while leading to a more transparent and straightforward classification process. The introduction of prototypes also inherently addresses the issue of limited within-class representations. Besides, to alleviate the widely acknowledged computational complexity issue of FGW distance calculation, we devise a simple yet effective NN-based FGW distance approximator, which can enable full GPU training acceleration with a marginal performance loss. In theory, we analyze the generalization performance of the proposed method and derive an O (1 over N) generalization bound, where the proof techniques can be extended to a broader range of prototype-based classification frameworks. Experimental results show that the proposed framework achieves competitive and superior performance on several widely used graph classification benchmark datasets. The code is avaliable at https://github.com/ChnQ/PGOT.

Yiyan Qi, Rundong Li 0002, Pinghui Wang, Yufang Sun 0003, Rui Xing

Estimating cardinality, i.e., the number of distinct elements, of a data stream is a fundamental problem in areas like databases, computer networks, and information retrieval. This study delves into a broader scenario where each element carries a positive weight. Unlike traditional cardinality estimation, limited research exists on weighted cardinality, with current methods requiring substantial memory and computational resources, challenging for devices with limited capabilities and real-time applications like anomaly detection. To address these issues, we propose QSketch, a memory-efficient sketch method for estimating weighted cardinality in streams. QSketch uses a quantization technique to condense continuous variables into a compact set of integer variables, with each variable requiring only 8 bits, making it 8 times smaller than previous methods. Furthermore, we leverage dynamic properties during QSketch generation to significantly enhance estimation accuracy and achieve a lower time complexity of O(1) for updating estimations upon encountering a new element. Experimental results on synthetic and real-world datasets show that QSketch is approximately 30% more accurate and two orders of magnitude faster than the state-of-the-art, using only 1/8 of the memory.

Bardh Prenkaj, Mario Villaizán-Vallelado, Tobias Leemann, Gjergji Kasneci

We present GRACIE (Graph Recalibration and Adaptive Counterfactual Inspection and Explanation), a novel approach for generative classification and counterfactual explanations of dynamically changing graph data. We study graph classification problems through the lens of generative classifiers. We propose a dynamic, self-supervised latent variable model that updates by identifying plausible counterfactuals for input graphs and recalibrating decision boundaries through contrastive optimization. Unlike prior work, we do not rely on linear separability between the learned graph representations to find plausible counterfactuals. Moreover, GRACIE eliminates the need for stochastic sampling in latent spaces and graph-matching heuristics. Our work distills the implicit link between generative classification and loss functions in the latent space, a key insight to understanding recent successes with this architecture. We further observe the inherent trade-off between validity and pulling explainee instances towards the central region of the latent space, empirically demonstrating our theoretical findings. In extensive experiments on synthetic and real-world graph data, we attain considerable improvements, reaching ~99% validity when sampling sets of counterfactuals even in the challenging setting of dynamic data landscapes.

Pranav Poduval, Sanjay Kumar Patnala, Gaurav Oberoi, Nitish Srivasatava, Siddhartha Asthana

The Combined Algorithm Selection and Hyperparameter Optimization (CASH) problem is pivotal in Automatic Machine Learning (AutoML). Most leading approaches combine Bayesian optimization with post-hoc ensemble building to create advanced AutoML systems. Bayesian optimization (BO) typically focuses on identifying a singular algorithm and its hyperparameters that outperform all other configurations. Recent developments have highlighted an oversight in prior CASH methods: the lack of consideration for diversity among the base learners of the ensemble. This oversight was overcome by explicitly injecting the search for diversity into the traditional CASH problem. However, despite recent developments, BO's limitation lies in its inability to directly optimize ensemble generalization error, offering no theoretical assurance that increased diversity correlates with enhanced ensemble performance. Our research addresses this gap by establishing a theoretical foundation that integrates diversity into the core of BO for direct ensemble learning. We explore a theoretically sound framework that describes the relationship between pair-wise diversity and ensemble performance, which allows our Bayesian optimization framework Optimal Diversity Bayesian Optimization (OptDivBO) to directly and efficiently minimize ensemble generalization error. OptDivBO guarantees an optimal balance between pairwise diversity and individual model performance, setting a new precedent in ensemble learning within CASH. Empirical results on 20 public datasets show that OptDivBO achieves the best average test ranks of 1.57 and 1.4 in classification and regression tasks.

Xihao Piao, Zheng Chen 0012, Taichi Murayama, Yasuko Matsubara, Yasushi Sakurai

The Transformer model has shown leading performance in time series forecasting. Nevertheless, in some complex scenarios, it tends to learn low-frequency features in the data and overlook high-frequency features, showing a frequency bias. This bias prevents the model from accurately capturing important high-frequency data features. In this paper, we undertake empirical analyses to understand this bias and discover that frequency bias results from the model disproportionately focusing on frequency features with higher energy. Based on our analysis, we formulate this bias and propose Fredformer, a Transformer-based framework designed to mitigate frequency bias by learning features equally across different frequency bands. This approach prevents the model from overlooking lower amplitude features important for accurate forecasting. Extensive experiments show the effectiveness of our proposed approach, which can outperform other baselines in different real-world time-series datasets. Furthermore, we introduce a lightweight variant of the Fredformer with an attention matrix approximation, which achieves comparable performance but with much fewer parameters and lower computation costs. The code is available at: https://github.com/chenzRG/Fredformer

Shaowen Peng, Xin Liu 0020, Kazunari Sugiyama, Tsunenori Mine

It has been shown that the effectiveness of graph convolutional network (GCN) for recommendation is attributed to the spectral graph filtering. Most GCN-based methods consist of a graph filter or followed by a low-rank mapping optimized based on supervised training. However, we show two limitations suppressing the power of graph filtering: (1) Lack of generality. Due to the varied noise distribution, graph filters fail to denoise sparse data where noise is scattered across all frequencies, while supervised training results in worse performance on dense data where noise is concentrated in middle frequencies that can be removed by graph filters without training. (2) Lack of expressive power. We theoretically show that linear GCN (LGCN) that is effective on collaborative filtering (CF) cannot generate arbitrary embeddings, implying the possibility that optimal data representation might be unreachable. To tackle the first limitation, we show close relation between noise distribution and the sharpness of spectrum where a sharper spectral distribution is more desirable causing data noise to be separable from important features without training. Based on this observation, we propose a generalized graph normalization (G2N) with hyperparameters adjusting the sharpness of spectral distribution in order to redistribute data noise to assure that it can be removed by graph filtering without training. As for the second limitation, we propose an individualized graph filter (IGF) adapting to the different confidence levels of the user preference that interactions can reflect, which is proved to be able to generate arbitrary embeddings. By simplifying LGCN, we further propose a simplified graph filtering for CF (SGFCF) which only requires the top-K singular values for recommendation. Finally, experimental results on four datasets with different density settings demonstrate the effectiveness and efficiency of our proposed methods.

Furong Peng, Kang Liu, Xuan Lu 0001, Yuhua Qian, HongRen Yan, Chao Ma 0002

Graph Convolutional Neural Network (GCN), a widely adopted method for analyzing relational data, enhances node discriminability through the aggregation of neighboring information. Usually, stacking multiple layers can improve the performance of GCN by leveraging information from high-order neighbors. However, the increase of the network depth will induce the over-smoothing problem, which can be attributed to the quality and quantity of neighbors changing: (a) neighbor quality, node's neighbors become overlapping in high order, leading to aggregated information becoming indistinguishable, (b) neighbor quantity, the exponentially growing aggregated neighbors submerges the node's initial feature by recursively aggregating operations. Current solutions mainly focus on one of the above causes and seldom consider both at once. Aiming at tackling both causes of over-smoothing in one shot, we introduce a simple Two-Sided Constraint (TSC) for GCNs, comprising two straightforward yet potent techniques: random masking and contrastive constraint. The random masking acts on the representation matrix's columns to regulate the degree of information aggregation from neighbors, thus preventing the convergence of node representations. Meanwhile, the contrastive constraint, applied to the representation matrix's rows, enhances the discriminability of the nodes. Designed as a plug-in module, TSC can be easily coupled with GCN or SGC architectures. Experimental analyses on diverse real-world graph datasets verify that our approach markedly reduces the convergence of node's representation and the performance degradation in deeper GCN.

Cheng Peng 0011, Haobo Wang 0001, Ke Chen 0005, Lidan Shou, Chang Yao 0001, Runze Wu 0001, Gang Chen 0001

Multi-label text classification (MLTC) allows a given text to be associated with multiple labels, which well suits many real-world data mining scenarios. However, the annotation effort of MLTC is inevitably expensive and time-consuming. Although multi-label active learning provides a cost-effective solution, it still faces two major challenges: (i) constructing decent feature space to distinguish the confusing semantics of different labels; (ii) defining proper sampling criteria to measure a sample's joint effect over the entire label space. To bridge these gaps, we propose a Contrastive Multi-label Active Learning framework (CoMAL) that gives an effective data acquisition strategy. Specifically, a contrastive decoupling mechanism is introduced to fully release the semantic information of multiple labels into the latent space. Then, we devise a hybrid criterion that balances two data value measures: (i) similarity-enhanced label cardinality inconsistency reflects the uncertainty of data predictions. (ii) positive feature diversity evaluates the positive-propensity semantic diversity to handle the label sparsity. Extensive experiments demonstrate that our CoMAL outperforms the current state-of-the-art multi-label active learning approaches. Code for CoMAL is available at https://github.com/chengzju/CoMAL.

Leonardo Pellegrina, Fabio Vandin

Learning interpretable models has become a major focus of machine learning research, given the increasing prominence of machine learning in socially important decision-making. Among interpretable models, rule lists are among the best-known and easily interpretable ones. However, finding optimal rule lists is computationally challenging, and current approaches are impractical for large datasets. We present a novel and scalable approach to learn nearly optimal rule lists from large datasets. Our algorithm uses sampling to efficiently obtain an approximation of the optimal rule list with rigorous guarantees on the quality of the approximation. In particular, our algorithm guarantees to find a rule list with accuracy very close to the optimal rule list when a rule list with high accuracy exists. Our algorithm builds on the VC-dimension of rule lists, for which we prove novel upper and lower bounds. Our experimental evaluation on large datasets shows that our algorithm identifies nearly optimal rule lists with a speed-up up to two orders of magnitude over state-of-the-art exact approaches. Moreover, our algorithm is as fast as, and sometimes faster than, recent heuristic approaches, while reporting higher quality rule lists. In addition, the rules reported by our algorithm are more similar to the rules in the optimal rule list than the rules from heuristic approaches.

Zhongyi Pei, Zhiyao Cen, Yipeng Huang 0006, Chen Wang 0018, Lin Liu 0001, Philip S. Yu, Mingsheng Long, Jianmin Wang 0001

Hyperparameter optimization (HPO) is known to be costly in deep learning, especially when leveraging automated approaches. Most of the existing automated HPO methods are accuracy-based, i.e., accuracy metrics are used to guide the trials of different hyperparameter configurations amongst a specific search space. However, many trials may encounter severe training problems, such as vanishing gradients and insufficient convergence, which can hardly be reflected by accuracy metrics in the early stages of the training and often result in poor performance. This leads to an inefficient optimization trajectory because the bad trials occupy considerable computation resources and reduce the probability of finding excellent hyperparameter configurations within a time limitation. In this paper, we propose Bad Trial Tackler (BTTackler), a novel HPO framework that introduces training diagnosis to identify training problems automatically and hence tackles bad trials. BTTackler diagnoses each trial by calculating a set of carefully designed quantified indicators and triggers early termination if any training problems are detected. Evaluations are performed on representative HPO tasks consisting of three classical deep neural networks (DNN) and four widely used HPO methods. To better quantify the effectiveness of an automated HPO method, we propose two new measurements based on accuracy and time consumption. Results show the advantage of BTTackler on two-fold: (1) it reduces 40.33% of time consumption to achieve the same accuracy comparable to baseline methods on average and (2) it conducts 44.5% more top-10 trials than baseline methods on average within a given time budget. We also released an open-source Python library that allows users to easily apply BTTackler to automated HPO processes with minimal code changes\footnotehttps://github.com/thuml/BTTackler.

Yong-chan Park, Jongjin Kim 0001, U Kang

Given a multidimensional array, how can we optimize the computation process for a part of Fourier coefficients? Discrete Fourier transform plays an overarching role in various data mining tasks. Recent interest has focused on efficiently calculating a small part of Fourier coefficients, exploiting the energy compaction property of real-world data. Current methods for partial Fourier transform frequently encounter efficiency issues, yet the adoption of pre-computation techniques within the PFT algorithm has shown promising performance. However, PFT still faces limitations in handling multidimensional data efficiently and requires manual hyperparameter tuning, leading to additional costs. In this paper, we propose Auto-MPFT (Automatic Multidimensional Partial Fourier Transform), which efficiently computes a subset of Fourier coefficients in multidimensional data without the need for manual hyperparameter search. Auto-MPFT leverages multivariate polynomial approximation for trigonometric functions, generalizing its domain to multidimensional Euclidean space. Moreover, we present a convex optimization-based algorithm for automatically selecting the optimal hyperparameter of Auto-MPFT. We provide a rigorous proof for the explicit reformulation of the original optimization problem of Auto-MPFT, demonstrating the process that converts it into a well-established unconstrained convex optimization problem. Extensive experiments show that Auto-MPFT surpasses existing partial Fourier transform methods and optimized FFT libraries, achieving up to 7.6x increase in speed without sacrificing accuracy. In addition, our optimization algorithm accurately finds the optimal hyperparameter for Auto-MPFT, significantly reducing the cost associated with hyperparameter search.

Siru Ouyang, Jiaxin Huang 0001, Pranav Pillai, Yunyi Zhang 0001, Yu Zhang 0044, Jiawei Han 0001

Fine-grained entity typing (FET) is the task of identifying specific entity types at a fine-grained level for entity mentions based on their contextual information. Conventional methods for FET require extensive human annotation, which is time-consuming and costly given the massive scale of data. Recent studies have been developing weakly supervised or zero-shot approaches. We study the setting of zero-shot FET where only an ontology is provided. However, most existing ontology structures lack rich supporting information and even contain ambiguous relations, making them ineffective in guiding FET. Recently developed language models, though promising in various few-shot and zero-shot NLP tasks, may face challenges in zero-shot FET due to their lack of interaction with task-specific ontology. In this study, we propose øurs, where we (1) enrich each node in the ontology structure with two categories of extra information:instance information for training sample augmentation andtopic information to relate types with contexts, and (2) develop a coarse-to-fine typing algorithm that exploits the enriched information by training an entailment model with contrasting topics and instance-based augmented training samples. Our experiments show that øurs achieves high-quality fine-grained entity typing without human annotation, outperforming existing zero-shot methods by a large margin and rivaling supervised methods. øurs also enjoys strong transferability to unseen and finer-grained types. We will open source this work upon acceptance.

Harrie Oosterhuis, Rolf Jagerman, Zhen Qin 0001, Xuanhui Wang, Michael Bendersky

The traditional evaluation of information retrieval (IR) systems is generally very costly as it requires manual relevance annotation from human experts. Recent advancements in generative artificial intelligence -specifically large language models (LLMs)- can generate relevance annotations at an enormous scale with relatively small computational costs. Potentially, this could alleviate the costs traditionally associated with IR evaluation and make it applicable to numerous low-resource applications. However, generated relevance annotations are not immune to (systematic) errors, and as a result, directly using them for evaluation produces unreliable results. In this work, we propose two methods based on prediction-powered inference and conformal risk control that utilize computer-generated relevance annotations to place reliable confidence intervals (CIs) around IR evaluation metrics. Our proposed methods require a small number of reliable annotations from which the methods can statistically analyze the errors in the generated annotations. Using this information, we can place CIs around evaluation metrics with strong theoretical guarantees. Unlike existing approaches, our conformal risk control method is specifically designed for ranking metrics and can vary its CIs per query and document. Our experimental results show that our CIs accurately capture both the variance and bias in evaluation based on LLM annotations, better than the typical empirical bootstrapping estimates. We hope our contributions bring reliable evaluation to the many IR applications where this was traditionally infeasible.

Kohei Obata, Koki Kawabata, Yasuko Matsubara, Yasushi Sakurai

Multivariate time series data suffer from the problem of missing values, which hinders the application of many analytical methods. To achieve the accurate imputation of these missing values, exploiting inter-correlation by employing the relationships between sequences (i.e., a network) is as important as the use of temporal dependency, since a sequence normally correlates with other sequences. Moreover, exploiting an adequate network depending on time is also necessary since the network varies over time. However, in real-world scenarios, we normally know neither the network structure nor when the network changes beforehand. Here, we propose a missing value imputation method for multivariate time series, namely MissNet, that is designed to exploit temporal dependency with a state-space model and inter-correlation by switching sparse networks. The network encodes conditional independence between features, which helps us understand the important relationships for imputation visually. Our algorithm, which scales linearly with reference to the length of the data, alternatively infers networks and fills in missing values using the networks while discovering the switching of the networks. Extensive experiments demonstrate that MissNet outperforms the state-of-the-art algorithms for multivariate time series imputation and provides interpretable results.