Graph Masked Autoencoders (GMAEs) have emerged as a notable self-supervised learning approach for graph-structured data. Existing GMAE models primarily focus on reconstructing node-level information, categorizing them as single-scale GMAEs. This methodology, while effective in certain contexts, tends to overlook the complex hierarchical structures inherent in many real-world graphs. For instance, molecular graphs exhibit a clear hierarchical organization in the form of the atoms-functional groups-molecules structure. Therefore, the inability of single-scale GMAE models to incorporate these hierarchical relationships often results in an inadequate capture of crucial high-level graph information, leading to a noticeable decline in performance. To address this limitation, we propose Hierarchical Graph Masked AutoEncoders (Hi-GMAE), a novel multi-scale GMAE framework designed to handle the hierarchical structures within graphs. First, Hi-GMAE constructs a multi-scale graph hierarchy through graph pooling, enabling the exploration of graph structures across different granularity levels. To ensure masking uniformity of subgraphs across these scales, we propose a novel coarse-to-fine strategy that initiates masking at the coarsest scale and progressively back-projects the mask to finer scales. Furthermore, we integrate a gradual recovery strategy with the masking process to mitigate the learning challenges posed by completely masked subgraphs. Diverging from the standard graph neural network (GNN) used in GMAE models, Hi-GMAE modifies its encoder and decoder into hierarchical structures. This entails using GNN at the finer scales for detailed local graph analysis and employing a graph transformer at coarser scales to capture global information. Such a design enables Hi-GMAE to effectively capture the multi-level information inherent in complex graph structures. Our experiments on 17 graph datasets, covering two graph learning tasks, consistently demonstrate that Hi-GMAE outperforms 29 state-of-the-art self-supervised competitors in capturing comprehensive graph information.

The introduction of knowledge graphs (KG) into recommendation systems (RS) has been proven to be effective because KG introduces a variety of relations between items. In fact, users have different relation preferences depending on the relationship in KG. Existing GNN-based models largely adopt random neighbor sampling strategies to process propagation; however, these models cannot aggregate biased relation preference local information for a specific user, and thus cannot effectively reveal the internal relationship between users' preferences. This will reduce the accuracy of recommendations, while also limiting the interpretability of the results.

Node classification is a fundamental graph-based task that aims to predict the classes of unlabeled nodes, for which Graph Neural Networks (GNNs) are the state-of-the-art methods. Current GNNs assume that nodes in the training set contribute equally during training. However, the quality of training nodes varies greatly, and the performance of GNNs could be harmed by two types of low-quality training nodes: (1) inter-class nodes situated near class boundaries that lack the typical characteristics of their corresponding classes. Because GNNs are data-driven approaches, training on these nodes could degrade the accuracy. (2) mislabeled nodes. In real-world graphs, nodes are often mislabeled, which can significantly degrade the robustness of GNNs. To mitigate the detrimental effect of the low-quality training nodes, we present CLNode, which employs a selective training strategy to train GNN based on the quality of nodes. Specifically, we first design a multi-perspective difficulty measurer to accurately measure the quality of training nodes. Then, based on the measured qualities, we employ a training scheduler that selects appropriate training nodes to train GNN in each epoch. To evaluate the effectiveness of CLNode, we conduct extensive experiments by incorporating it in six representative backbone GNNs. Experimental results on real-world networks demonstrate that CLNode is a general framework that can be combined with various GNNs to improve their accuracy and robustness.

Multi-task Learning (MTL), which involves the simultaneous learning of multiple tasks, can achieve better performance than learning each task independently. It has achieved great success in various applications, ranging from Computer Vision (CV) to Natural Language Processing (NLP). In MTL, the losses of the including tasks are jointly optimized. However, it is common for these tasks to be competing. When the tasks are competing, minimizing the losses of some tasks increases the losses of others, which accordingly increases the task variance (variance between the task-specific loss); furthermore, it induces under-fitting in some tasks and over-fitting in others, which degenerates the generalization performance of an MTL model. To address this issue, it is necessary to control the task variance; thus, task variance regularization is a natural choice. While intuitive, task variance regularization remains unexplored in MTL. Accordingly, to fill this gap, we study the generalization error bound of MTL through the lens of task variance and propose the task variance matters the generalization performance of MTL. Furthermore, this paper investigates how the task variance might be effectively regularized, and consequently proposes a multi-task learning method based on adversarial multi-armed bandit. The proposed method, dubbed BanditMTL, regularizes the task variance by means of a mirror gradient ascent-descent algorithm. Adopting BanditMTL both in CV and NLP applications is found to achieve state-of-the-art performance. The results of extensive experiments back up our theoretical analysis and validate the superiority of our proposals.

Link prediction has attracted considerable attention. Empiricism and the evolution mechanism based approach are the mainstream methods for link prediction. However, one drawback of such approaches is that they usually ignore the dynamic evolution mechanism of social networks, yet being dynamic is an essential characteristic of a social network that exists in every stage of the networks evolution. In this paper, we address the problem of temporal link prediction and investigate social networks from the time dimension with the purpose of dynamic evolution mechanism capturing. First, we separate a temporal network into a series of snapshots. Then, we propose a triad transition matrix prediction algorithm to learn the change of the distribution of triads among the different snapshots. The learned changes in the distribution of triads can capture the dynamic evolution of the network. With a proposed triad transition influence quantification algorithm, we propose a motifs based link prediction method for temporal link prediction. The proposed method can capture the dynamic evolution of temporal networks and is universal than existing methods. Extensive experiments on disparate real-world networks and model networks with controllable evolution demonstrate the effectiveness of the proposed method.

Signed network representation is a key problem for signed network data. Previous studies have shown that by preserving multi-order signed proximity (SP), expressive node representations can be learned. However, multi-order SP cannot be perfectly encoded using limited samples extracted from random walks, which reduces effectiveness. To perfectly encode multi-order SP, we have innovatively integrated the informativeness of infinite samples to construct high-level summaries of multi-order SP without explicit sampling. Based on these summaries, we propose a method called SPMF, in which node representations are obtained using low-rank matrix approximation. Furthermore, we theoretically investigate the rationality of SPMF by examining its relationship with a powerful representation learning architecture. In sign inference and link prediction tasks with several real-world datasets, SPMF is empirically competitive compared with state-of-the-art methods. Additionally, two tricks are designed for improving the scalability of SPMF. One trick aims to filter out less informative summaries, and another one is inspired by kernel techniques. Both tricks empirically improve scalability while preserving effective performance. The code for our methods is publicly available.

Signed network embedding (SNE) has received considerable attention in recent years. A mainstream idea of SNE is to learn node representations by estimating the ratio of sampling densities. Though achieving promising performance, these methods based on density ratio estimation are limited to the issues of confusing sample, expected error, and fixed priori. To alleviate the above-mentioned issues, in this paper, we propose a novel dual-branch density ratio estimation (DDRE) architecture for SNE. Specifically, DDRE 1) consists of a dual-branch network, dealing with the confusing sample; 2) proposes the expected matrix factorization without sampling to avoid the expected error; and 3) devises an adaptive cross noise sampling to alleviate the fixed priori. We perform sign prediction and node classification experiments on four real-world and three artificial datasets, respectively. Extensive empirical results demonstrate that DDRE not only significantly outperforms the methods based on density ratio estimation but also achieves competitive performance compared with other types of methods such as graph likelihood, generative adversarial networks, and graph convolutional networks. Code is publicly available at https://github.com/WHU-SNA/DDRE.

Trust prediction in online social networks is crucial for information dissemination, product promotion, and decision making. Existing work on trust prediction mainly utilizes the network structure or the low-rank approximation of a trust network. These approaches can suffer from the problem of data sparsity and prediction accuracy. Inspired by the homophily theory, which shows a pervasive feature of social and economic networks that trust relations tend to be developed among similar people, we propose a novel deep user model for trust prediction based on user similarity measurement. It is a comprehensive data sparsity insensitive model that combines a user review behavior and the item characteristics that this user is interested in. With this user model, we firstly generate a user's latent features mined from user review behavior and the item properties that the user cares. Then we develop a pair-wise deep neural network to further learn and represent these user features. Finally, we measure the trust relations between a pair of people by calculating the user feature vector cosine similarity. Extensive experiments are conducted on two real-world datasets, which demonstrate the superior performance of the proposed approach over the representative baseline works.

Developing effective network embedding methods for social trust networks (STNs) is a non-trivial problem because two key pieces of information need to be preserved simultaneously: a user's relations to latent factors and the trust transfer patterns that govern what type of relationship will form. In this study, we propose a novel social trust network embedding method (STNE) to address these issues. Specifically, we present a modified Skip-Gram model with negative sampling to jointly learn latent factor features, along with the trust transfer pattern features. Moreover, we define a flexible notion about a user's latent relationships with other users, which generates reliable negative samples for optimization. Extensive experiments on several real-world networks demonstrate the efficacy of the proposed STNE.

Link prediction in signed social networks is an important and challenging problem in social network analysis. To produce the most accurate prediction results, two questions must be answered: (1) Which unconnected node pairs are likely to be connected by a link in future? (2) What will the signs of the new links be? These questions are challenging, and current research seldom well solves both issues simultaneously. Additionally, neutral social relationships, which are common in many social networks can affect the accuracy of link prediction. Yet neutral links are not considered in most existing methods. Hence, in this paper, we propose a s igned l atent f actor (SLF) model that answers both these questions and, additionally, considers four types of relationships: positive, negative, neutral and no relationship at all. The model links social relationships of different types to the comprehensive, but opposite, effects of positive and negative SLFs. The SLF vectors for each node are learned by minimizing a negative log-likelihood objective function. Experiments on four real-world signed social networks support the efficacy of the proposed model.

Based on the performance of entire social networks, anomaly analysis for evolving social networks generally ignores the otherness of the evolutionary behaviors of different nodes, such that it is difficult to precisely identify the anomalous evolutionary behaviors of nodes ( AEBN ). Assuming that a node's evolutionary behavior that generates and removes edges normally follows stable evolutionary mechanisms, this study focuses on detecting and assessing AEBN, whose evolutionary mechanisms deviate from their past mechanisms, and proposes a link prediction detection ( LPD ) method and a matrix perturbation assessment ( MPA ) method. LPD describes a node's evolutionary behavior by fitting its evolutionary mechanism, and designs indexes for edge generation and removal to evaluate the extent to which the evolutionary mechanism of a node's evolutionary behavior can be fitted by a link prediction algorithm. Furthermore, it detects AEBN by quantifying the differences among behavior vectors that characterize the node's evolutionary behaviors in different periods. In addition, MPA considers AEBN as a perturbation of the social network structure, and quantifies the effect of AEBN on the social network structure based on matrix perturbation analysis. Extensive experiments on eight disparate real-world networks demonstrate that analyzing AEBN from the perspective of evolutionary mechanisms is important and beneficial.

Recently, social networks have witnessed a massive surge in popularity. A key issue in social network research is network evolution analysis, which assumes that all the autonomous nodes in a social network follow uniform evolution mechanisms. However, different nodes in a social network should have different evolution mechanisms to generate different edges. This is proposed as the underlying idea to ensure the nodes' evolution diversity in this paper. Our approach involves identifying the micro-level node evolution that generates different edges by introducing the existing link prediction methods from the perspectives of nodes. We also propose the edge generation coefficient to evaluate the extent to which an edge's generation can be explained by a link prediction method. To quantify the nodes' evolution diversity, we define the diverse evolution distance. Furthermore, a diverse node adaption algorithm is proposed to indirectly analyze the evolution of the entire network based on the nodes' evolution diversity. Extensive experiments on disparate real-world networks demonstrate that the introduction of the nodes' evolution diversity is important and beneficial for analyzing the network evolution. The diverse node adaption algorithm outperforms other state-of-the-art link prediction algorithms in terms of both accuracy and universality. The greater the nodes' evolution diversity, the more obvious its advantages.