Generative graph self-supervised learning (SSL), represented by masked graph autoencoders (GAEs), has shown great potential in graph representation learning. Existing masked GAEs typically rely on reconstruction criteria, such as mean squared error, to measure the discrepancy between the input graph and the reconstructed output. However, this learning paradigm struggles with perturbed graph characteristics, hindering the learning of robust graph representations. To address this, we introduce AMGAE -- an Adversarial Masked Graph AutoEncoder, which enhances the robustness of masked GAEs by integrating an adversarial learning strategy. Specifically, we design AMGAE to comprise a generator and a discriminator, optimized alternately and interconnected by a binary discrimination task (BDT). We treat the entire masked GAE as the generator, which produces a reconstructed output using the visible graph features. Then, we synthesize the reconstructed output by substituting the visible node features with the corresponding raw input features. Finally, we employ an additional GNN layer as the discriminator to determine the authenticity of the node-level features synthesized by BDT. By introducing the adversarial strategy, AMGAE reformulates masked GAE learning into a min-max game, which facilitates the learning of robust graph representations. We conduct extensive experiments on three graph tasks, demonstrating that AMGAE performs favorably against diverse baselines.

Recently, the emergence of large language models (LLMs) has revolutionized the paradigm of information retrieval (IR) applications, especially in web search, by generating vast amounts of human-like texts on the Internet. As a result, IR systems in the LLM era are facing a new challenge: the indexed documents are now not only written by human beings but also automatically generated by the LLMs. How these LLM-generated documents influence the IR systems is a pressing and still unexplored question. In this work, we conduct a quantitative evaluation of IR models in scenarios where both human-written and LLM-generated texts are involved. Surprisingly, our findings indicate that neural retrieval models tend to rank LLM-generated documents higher. We refer to this category of biases in neural retrievers towards the LLM-generated content as the source bias. Moreover, we discover that this bias is not confined to the first-stage neural retrievers, but extends to the second-stage neural re-rankers. Then, in-depth analyses from the perspective of text compression indicate that LLM-generated texts exhibit more focused semantics with less noise, making it easier for neural retrieval models to semantic match. To mitigate the source bias, we also propose a plug-and-play debiased constraint for the optimization objective, and experimental results show its effectiveness. Finally, we discuss the potential severe concerns stemming from the observed source bias and hope our findings can serve as a critical wake-up call to the IR community and beyond. To facilitate future explorations of IR in the LLM era, the constructed two new benchmarks are available at https://github.com/KID-22/Source-Bias.

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.

Kernel$k$-means is a fundamental unsupervised learning in data mining. Its computational requirements are typically at least quadratic in the number of data, which are prohibitive for large-scale scenarios. To address these issues, we propose a novel randomized sketching approach SKK based on the circulant matrix. SKK projects the kernel matrix left and right according to the proposed sketch matrices to obtain a smaller one and accelerates the matrix-matrix product by the fast Fourier transform based on the circulant matrix, which can greatly reduce the computational requirements of the approximate kernel$k$-means estimator with the same generalization bound as the exact kernel$k$-means in the statistical setting. In particular, theoretical analysis shows that taking the sketch dimension of$\sqrt{n}$is sufficient for SKK to achieve the optimal excess risk bound with only a fraction of computations, where$n$is the number of data. The extensive experiments verify our theoretical analysis, and SKK achieves the state-of-the-art performances on 12 real-world datasets. To the best of our knowledge, in randomized sketching, this is the first time that unsupervised learning makes such a significant breakthrough.

In this paper, by introducing Generalized Bernstein condition, we propose the first O(√p over n∈ ) high probability excess population risk bound for differentially private algorithms under the assumptions G-Lipschitz, L-smooth, and Polyak-Łojasiewicz condition, based on gradient perturbation method. If we replace the properties G-Lipschitz and L-smooth by α-Hölder smoothness (which can be used in non-smooth setting), the high probability bound comes to O(n-α over 1+2α) w.r.t n, which cannot achieve O (1/n) when α ∈(0,1]. To solve this problem, we propose a variant of gradient perturbation method, max1,g -Normalized Gradient Perturbation (m-NGP). We further show that by normalization, the high probability excess population risk bound under assumptions α-Hölder smooth and Polyak-Łojasiewicz condition can achieve O (√p over n∈), which is the first O (1/n) high probability excess population risk bound w.r.t n for differentially private algorithms under non-smooth conditions. Moreover, experimental results show that m-NGP improves the performance of the differentially private model over real datasets.

Differentiable Neural Architecture Search (DARTS) is becoming more and more popular among Neural Architecture Search (NAS) methods because of its high search efficiency and low compute cost. However, the stability of DARTS is very inferior, especially skip connections aggregation that leads to performance collapse. Though existing methods leverage Hessian eigenvalues to alleviate skip connections aggregation, they make DARTS unable to explore architectures with better performance. In the paper, we propose operation-level progressive differentiable neural architecture search (OPP-DARTS) to avoid skip connections aggregation and explore better architectures simultaneously. We first divide the search process into several stages during the search phase and increase candidate operations into the search space progressively at the beginning of each stage. It can effectively alleviate the unfair competition between operations during the search phase of DARTS by offsetting the inherent unfair advantage of the skip connection over other operations. Besides, to keep the competition between operations relatively fair and select the operation from the candidate operations set that makes training loss of the supernet largest. The experiment results indicate that our method is effective and efficient. Our method’s performance on CIFAR-10 is superior to the architecture found by standard DARTS, and the transferability of our method also surpasses standard DARTS. We further demonstrate the robustness of our method on three simple search spaces, i.e., S2, S3, S4, and the results show us that our method is more robust than standard DARTS. Our code is available at https://github.com/zxunyu/OPP-DARTS.

Dimension reduction is a fundamental data mining task. However, it has limited applicability in high-dimensional scenarios because of stringent computational requirements. To address these issues, we propose ESE, an extremely sparse Johnson-Lindenstrauss transform, which takes a substantial step in dimension reduction. The projection matrix of ESE is an extremely sparse matrix, which has only k nonzero elements by employing the hash functions, where k is the embedded dimension. Theoretical analysis shows that ESE has a smaller time complexity than the existing projection algorithms and keeps the best accuracy (1+ε) for the general case, where 0 <; ε ≪ 1. In particular, the optimal statistical accuracy is achieved requiring log(n)log(d)/ε embedded dimension, where n is the number of data, d is the dimension of data. The extensive experiments verify that ESE has a significant advantage in time with satisfactory accuracy, compared to the state-of-the-art dimension reduction algorithms.

Kernel selection is one of the key issues both in recent research and application of kernel methods. This is usually done by minimizing either an estimate of generalization error or some other related performance measure. It is well known that a kernel matrix can be interpreted as an empirical version of a continuous integral operator, and its eigenvalues converge to the eigenvalues of integral operator. In this paper, we introduce new kernel selection criteria based on the eigenvalues perturbation of the integral operator. This perturbation quantifies the difference between the eigenvalues of the kernel matrix and those of the integral operator. We establish the connection between eigenvalues perturbation and generalization error. By minimizing the derived generalization error bounds, we propose the kernel selection criteria. Therefore the kernel chosen by our proposed criteria can guarantee good generalization performance. To compute the values of our criteria, we present a method to obtain the eigenvalues of integral operator via the Fourier transform. Experiments on benchmark datasets demonstrate that our kernel selection criteria are sound and effective.

We propose a new leaning method for Multiple Kernel Learning (MKL) based on the upper bounds of the leave-one-out error that is an almost unbiased estimate of the expected generalization error. Specifically, we first present two new formulations for MKL by minimizing the upper bounds of the leave-one-out error. Then, we compute the derivatives of these bounds and design an efficient iterative algorithm for solving these formulations. Experimental results show that the proposed method gives better accuracy results than that of both SVM with the uniform combination of basis kernels and other state-of-art kernel learning approaches.