Unsupervised/self-supervised graph neural networks (GNN) are susceptible to the inherent randomness in the input graph data, which adversely affects the model's performance in downstream tasks. In this paper, we propose USER, an unsupervised and robust version of GNN based on structural entropy, to alleviate the interference of graph perturbations and learn appropriate representations of nodes without label information. To mitigate the effects of undesirable perturbations, we analyze the property of intrinsic connectivity and define the intrinsic connectivity graph. We also identify the rank of the adjacency matrix as a crucial factor in revealing a graph that provides the same embeddings as the intrinsic connectivity graph. To capture such a graph, we introduce structural entropy in the objective function. Extensive experiments conducted on clustering and link prediction tasks under random-perturbation and meta-attack over three datasets show that USER outperforms benchmarks and is robust to heavier perturbations.

This paper is the first to use contrastive learning to improve the robustness of graph representation learning for signed bipartite graphs, which are commonly found in social networks, recommender systems, and paper review platforms. Existing contrastive learning methods for signed graphs cannot capture implicit relations between nodes of the same type in signed bipartite graphs, which have two types of nodes and edges only connect nodes of different types. We propose a Signed Bipartite Graph Contrastive Learning (SBGCL) method to learn robust node representation while retaining the implicit relations between nodes of the same type. SBGCL augments a signed bipartite graph with a novel two-level graph augmentation method. At the top level, we maintain two perspectives of the signed bipartite graph, one presents the original interactions between nodes of different types, and the other presents the implicit relations between nodes of the same type. At the bottom level, we employ stochastic perturbation strategies to create two perturbed graphs in each perspective. Then, we construct positive and negative samples from the perturbed graphs and design a multi-perspective contrastive loss to unify the node presentations learned from the two perspectives. Results show proposed model is effective over state-of-the-art methods on real-world datasets.

Signed graphs model complex relations using both positive and negative edges. Signed graph neural networks (SGNN) are powerful tools to analyze signed graphs. We address the vulnerability of SGNN to potential edge noise in the input graph. Our goal is to strengthen existing SGNN allowing them to withstand edge noises by extracting robust representations for signed graphs. First, we analyze the expressiveness of SGNN using an extended Weisfeiler-Lehman (WL) graph isomorphism test and identify the limitations to SGNN over triangles that are unbalanced. Then, we design some structure-based regularizers to be used in conjunction with an SGNN that highlight intrinsic properties of a signed graph. The tools and insights above allow us to propose a novel framework, Robust Signed Graph Neural Network (RSGNN), which adopts a dual architecture that simultaneously denoises the graph while learning node representations. We validate the performance of our model empirically on four real-world signed graph datasets, i.e., Bitcoin_OTC, Bitcoin_Alpha, Epinion and Slashdot, RSGNN can clearly improve the robustness of popular SGNN models. When the signed graphs are affected by random noise, our method outperforms baselines by up to 9.35% Binary-F1 for link sign prediction. Our implementation is available in PyTorch1.

Spectral Clustering is a popular technique to split data points into groups, especially for complex datasets. The algorithms in the Spectral Clustering family typically consist of multiple separate stages (such as similarity matrix construction, low-dimensional embedding, and K-Means clustering as post-processing), which may lead to sub-optimal results because of the possible mismatch between different stages. In this paper, we propose an end-to-end single-stage learning method to clustering called Regularized Non-negative Spectral Embedding (RNSE) which extends Spectral Clustering with the adaptive learning of similarity matrix and meanwhile utilizes non-negative constraints to facilitate one-step clustering (directly from data points to clustering labels). Two well-founded methods, successive alternating projection and strategic multiplicative update, are employed to work out the quite challenging optimization problems in RNSE. Extensive experiments on both synthetic and real-world datasets demonstrate RNSE's superior clustering performance to some state-of-the-art competitors.