Recent studies have shown that unsupervised graph contrastive learning (GCL) is vulnerable to adversarial attacks. Automatic adversarial augmentation techniques are proposed to improve both the effectiveness and robustness of GCL. Existing methods typically regard unsupervised contrastive loss as the adversarial goal, essentially aiming to maximize inter-view instance-wise discrepancies between adversarial and original views. However, such attacks overlook intra-view neighborhood inconsistency, which hinders the robustness of GCL models against local neighborhood noises, resulting in performance degradation on low-homophily graphs. To tackle this issue, we propose a novel adversarial contrastive paradigm, named Edge self-aDversarial Augmentation for Graph Contrastive Learning (EDA-GCL). We theoretically establish that the adversarial objective of the intra-view neighborhood is equivalent to maximizing the discrepancy between bidirectional edge features. Hence, we build our adversarial framework based on edge self-adversarial learning. It generates pairwise adversarial augmentations from the original view by learning distinct neighborhood connectivity structures. The learned pairwise adversarial views are utilized for GCL model training in the minimization stage. Notably, this edge-level adversarial approach reduces the computational complexity to the level of the edge number. Experiments on various graph tasks and complex noise scenarios demonstrate the superiority and robustness of our EDA-GCL.

Zhiyin Yu, Yuchen Mou, Juncheng Yan, Junyu Luo, Chunchun Chen, Xing Wei, Yunhui Liu, Hongru Sun, Yuxing Zhang, Jun Xu, Yatao Bian, Ming Zhang, Wei Ye, Tieke He, Jie Yang, Guanjie Zheng, Zhonghai Wu, Bo Zhang, Lei Bai, Xiao Luo. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

Spectral clustering is a leading clustering method. Two of its major shortcomings are the disjoint optimization process and the limited representation capacity. To address these issues, we propose a deep spectral clustering model (named BootSC), which jointly learns all stages of spectral clustering—affinity matrix construction, spectral embedding, and$k$-means clustering—using a single network in an end-to-end manner. BootSC leverages effective and efficient optimal-transport-derived supervision to bootstrap the affinity matrix and the cluster assignment matrix. Moreover, a semantically-consistent orthogonal re-parameterization technique is introduced to orthogonalize spectral embeddings, significantly enhancing the discrimination capability. Experimental results indicate that BootSC achieves state-of-the-art clustering performance. For example, it accomplishes a notable 16% NMI improvement over the runner-up method on the challenging ImageNet-Dogs dataset. Our code is available athttps://github.com/spdj2271/BootSC.

Graph contrastive learning (GCL) has achieved remarkable success in graph self-supervised learning (SSL) through an augmenting-contrasting paradigm. Existing augmentation strategies typically generate augmentations independently, ignoring the explicit modeling of the underlying relationship between augmentations, i.e., augmentation discrepancy. In addition, previous discrete augmentations (e.g., edge dropping and feature masking) also hinder the path toward joint optimization. These limit the diversity and complementarity of augmentations, leading to the suboptimal contrastive learning. In this article, we propose a novel adversarial augmentation method, called adversarial augmentation with maximum discrepancy for GCL (AMD-GCL), to jointly optimize pairwise augmentations. The core of AMD-GCL is an adversarial augmentation constraint module that maximizes the discrepancy between pairwise augmentations. Specifically, we establish a theoretical analysis indicating that maximizing graph reconstruction error in a continuous space serves as a surrogate for minimizing mutual information (MI), laying the basis for the differentiable constraint of augmentation discrepancy. Based on this, AMD-GCL designs a min-max problem. We directly add continuous adversarial perturbations to the original graph structure and features to maximize the reconstruction error. Meanwhile, we maximize the reconstruction error between pairwise augmentations to amplify the discrepancy. This leads to a maximization problem. After obtaining augmentations, AMD-GCL optimizes both the contrastive loss and reconstruction objectives, deriving a unified minimization problem. The adversarial augmentations are iteratively updated during the training process. Comprehensive experiments on 18 datasets demonstrate the superiority and robustness of AMD-GCL on several downstream tasks and various adversarial scenarios.

Graph neural networks (GNNs) can efficiently process text-attributed graphs (TAGs) due to their message-passing mechanisms, but their training heavily relies on the human-annotated labels. Moreover, the complex and diverse local topologies of nodes of real-world TAGs make it challenging for a single mechanism to handle. Large language models (LLMs) perform well in zero-/few-shot learning on TAGs but suffer from a scalability challenge. Therefore, we propose a preference-driven knowledge distillation (PKD) framework to synergize the complementary strengths of LLMs and various GNNs for few-shot node classification. Specifically, we develop a GNN-preference-driven node selector that effectively promotes prediction distillation from LLMs to teacher GNNs. To further tackle nodes' intricate local topologies, we develop a node-preference-driven GNN selector that identifies the most suitable teacher GNN for each node, thereby facilitating tailored knowledge distillation from teacher GNNs to the student GNN. Extensive experiments validate the efficacy of our proposed framework in few-shot node classification on real-world TAGs. Our code can be available at <https://github.com/GEEX-Weixing/PKD>.

Graph neural networks (GNNs) have a wide range of applications in multimedia. Recent studies have shown that Graph neural networks (GNNs) are vulnerable to link stealing attacks, which infers the existence of edges in the target GNN's training graph. Existing attacks are usually based on the assumption that links exist between two nodes that share similar posteriors; however, they fail to focus on links that do not hold under this assumption. To this end, we propose LinkThief, an improved link stealing attack that combines generalized structure knowledge with node similarity, in a scenario where the attackers' background knowledge contains partially leaked target graph and shadow graph. Specifically, to equip the attack model with insights into the link structure spanning both the shadow graph and the target graph, we introduce the idea of creating a Shadow-Target Bridge Graph and extracting edge subgraph structure features from it. Through theoretical analysis from the perspective of privacy theft, we first explore how to implement the aforementioned ideas. Building upon the findings, we design the Bridge Graph Generator to construct the Shadow-Target Bridge Graph. Then, the subgraph around the link is sampled by the Edge Subgraph Preparation Module. Finally, the Edge Structure Feature Extractor is designed to obtain generalized structure knowledge, which is combined with node similarity to form the features provided to the attack model. Extensive experiments validate the correctness of theoretical analysis and demonstrate that LinkThief still effectively steals links without extra assumptions. Our code is available at https://github.com/octopusStar218/LinkThief-MM2024.

Graph data can characterize many complex network systems, hence many community detection methods have been proposed to analyze graph problems. Recently, Non-negative matrix factorization (NMF) has been widely used for community detection due to its good interpretability of community detection results. However, existing NMF-based community detection methods are designed without considering extreme adversarial attacks (or perturbations). In reality, complex and diverse adversarial perturbations can easily destroy the network structure, so the classical NMF method cannot effectively identify the attacked network. Inspired by adversarial training technique, we propose a novel NMF method for extreme adversarial attacks, coined as Extreme Adversarial Attack NMF. Specifically, we consider the existence of extreme adversarial perturbations which destroy the network structure, while the matrix factorization results can still fit the attacked network well. A strict optimization algorithm is also devised to dynamically simulate the generation of extreme adversarial perturbations. This work aims to improve the robustness and generalization of NMF methods in graph-based learning. We conduct extensive experiments on six original real-world networks and their edge-missing networks. The experiment results show that the proposed method can effectively improve the performance of the NMF-based community detection method, which outperforms 4.69% and 7.07% on average over the standard NMF on the original and edge-missing networks, respectively.

Subspace clustering based on data self-expressive model aims to represent each data point as a linear combination of other data points on the dataset. Most existing methods focus on developing the regularization of self-expressive coefficients to solve the transductive unsupervised problem. In this paper, we propose a novel Self-Supervised Embedding for Subspace Clustering (S2ESC), which exploits a low-dimensional feature space where the data points belonging to the same category can be well-connected. Specifically, each data point is encouraged to be close to its transformation which is termed as self-supervised embedding learning. Therefore, the self-expressive coefficients can be learned by representing the data points over the corresponding transformations in the feature space. We introduce the low-rank and sparse regularization to illustrate the performance of self-supervised embedding. Extensive experiments on benchmark datasets demonstrate that our method outperforms the compared traditional subspace clustering methods.