Graph-based semi-supervised learning (GSSL) has long been a research focus. Traditional methods are generally shallow learners, based on the cluster assumption. Recently, graph convolutional networks (GCNs) have become the predominant techniques for their promising performance. However, a critical question remains largely unanswered: why do deep GCNs encounter the oversmoothing problem, while traditional shallow GSSL methods do not, despite both progressing through the graph in a similar iterative manner? In this article, we theoretically discuss the relationship between these two types of methods in a unified optimization framework. One of the most intriguing findings is that, unlike traditional ones, typical GCNs may not effectively incorporate both graph structure and label information at each layer. Motivated by this, we propose three simple but powerful graph convolution methods. The first, optimized simple graph convolution (OGC), is a supervised method, which guides the graph convolution process with labels. The others are two "no-learning" unsupervised methods: graph structure preserving graph convolution (GGC) and its multiscale version GGCM, both aiming to preserve the graph structure information during the convolution process. Finally, we conduct extensive experiments to show the effectiveness of our methods.

Graphs in the real world keep evolving with the integration of new nodes, and it is often infeasible to manually label all the new nodes promptly. In this case, graph learning algorithms can come in handy and perform classification on these newly emerging nodes. Typically, if unseen classes exist (i.e., no training samples from these classes), one can perform zero-shot learning (ZSL) or generalized ZSL (GZSL). During testing, ZSL aims to classify samples within unseen classes, whereas GZSL aims to classify samples within both seen and unseen classes, which is even more challenging. In our previous work, we proposed a decomposed graph prototype network (DGPN) to decompose the graph convolution operation for handling the zero-shot node classification (ZNC) problem. However, DGPN is not well-suited for the generalized ZNC (GZNC) problem. To this end, in this article, we propose a novel graph generative model, multihop reconstruction graph autoencoder (MHR-GAE). Unlike DGPN, MHR-GAE utilizes a multihop encoder with class semantic descriptions (CSDs) (as condition signals) to reconstruct the information and generate nodes of unseen classes. Thus, it can handle both the ZNC and GZNC problems and obtain competitive performance. We evaluate our model on real-world datasets, and the experimental results demonstrate that MHR-GAE outperforms other baseline methods.

Node classification is a central task in graph data analysis. Scarce or even no labeled data of emerging classes is a big challenge for existing methods. A natural question arises: can we classify the nodes from those classes that have never been seen?

Network embedding, aiming to project a network into a low-dimensional space, is increasingly becoming a focus of network research. Semi-supervised network embedding takes advantage of labeled data, and has shown promising performance. However, existing semi-supervised methods would get unappealing results in thecompletely-imbalancedlabel setting where some classes have no labeled nodes at all. To alleviate this, we propose two novel semi-supervised network embedding methods. The first one is a shallow method named RSDNE. Specifically, to benefit from the completely-imbalanced labels, RSDNE guarantees both intra-class similarity and inter-class dissimilarity in an approximate way. The other method is RECT which is a new class of graph neural networks. Different from RSDNE, to benefit from the completely-imbalanced labels, RECT explores the class-semantic knowledge. This enables RECT to handle networks with node features and multi-label setting. Experimental results on several real-world datasets demonstrate the superiority of the proposed methods.

Graph embedding, also known as network embedding and network representation learning, is a useful technique which helps researchers analyze information networks through embedding a network into a low-dimensional space. However, existing graph embedding methods are all node-based, which means they can just directly map the nodes of a network to low-dimensional vectors while the edges could only be mapped to vectors indirectly. One important reason is the computational cost, because the number of edges is always far greater than the number of nodes. In this article, considering an important property of social networks, i.e., the network is sparse, and hence the average degree of nodes is bounded, we propose an edge-based graph embedding ( edge2vec ) method to map the edges in social networks directly to low-dimensional vectors. Edge2vec takes both the local and the global structure information of edges into consideration to preserve structure information of embedded edges as much as possible. To achieve this goal, edge2vec first ingeniously combines the deep autoencoder and Skip-gram model through a well-designed deep neural network. The experimental results on different datasets show edge2vec benefits from the direct mapping in preserving the structure information of edges.

This paper presents the problem of tie direction learning which learns the directionality function of directed social networks. One way is based on hand-crafted features; the other called DeepDirect learns the social tie representation through the network topology. DeepDirect directly maps social ties to low-dimensional embedding vectors by preserving network topology, utilizing labeled data, and generating pseudo-labels based on observed directionality patterns. Experimental results on two tasks, i.e., direction discovery on undirected ties and direction quantification on bidirectional ties, demonstrate the proposed methods are effective and promising.

The problem of feature selection has attracted considerable research interest in recent years. Supervised information is capable of significantly improving the quality of selected features. However, existing supervised feature selection methods all require that classes in the labeled data (source domain) and unlabeled data (target domain) to be identical, which may be too restrictive in many cases. In this article, we consider a more challenging cross-class setting where the classes in these two domains are related but different, which has rarely been studied before. We propose a cross-class knowledge transfer feature selection framework which transfers the cross-class knowledge from the source domain to guide target domain feature selection. Specifically, high-level descriptions, i.e., attributes, are used as the bridge for knowledge transfer. To further improve the quality of the selected features, our framework jointly considers the tasks of cross-class knowledge transfer and feature selection. Experimental results on four benchmark datasets demonstrate the superiority of the proposed method.

There is a lot of research work on social ties, few of which is about the directionality of social ties. However, the directionality is actually a basic but important attribute of social ties. In this paper, we present a supervised learning problem, the tie direction learning (TDL) problem, which aims to learn the directionality function of directed social networks. Two ways are introduced to solve the TDL problem: one is based on hand-crafted features and the other, named DeepDirect, learns the social tie representation through the topological information of the network. In DeepDirect, a novel network embedding approach, which directly maps the social ties to low-dimensional embedding vectors by deep learning techniques, is proposed. DeepDirect embeds the network considering three different aspects: preserving network topology, utilizing labeled data, and generating pseudo-labels based on observed directionality patterns. Two novel applications are proposed for the learned directionality function, i.e., direction discovery on undirected ties and direction quantification on bidirectional ties. Experiments are conducted on five different real-world data sets about these two tasks. The experimental results demonstrate our methods, especially DeepDirect, are effective and promising.

Network embedding, aiming to project a network into a low-dimensional space, is increasingly becoming a focus of network research. Semi-supervised network embedding takes advantage of labeled data, and has shown promising performance. However, existing semi-supervised methods would get unappealing results in the completely-imbalanced label setting where some classes have no labeled nodes at all. To alleviate this, we propose a novel semi-supervised network embedding method, termed Relaxed Similarity and Dissimilarity Network Embedding (RSDNE). Specifically, to benefit from the completely-imbalanced labels, RSDNE guarantees both intra-class similarity and inter-class dissimilarity in an approximate way. Experimental results on several real-world datasets demonstrate the superiority of the proposed method.

Information source detection, which is the reverse problem of information diffusion, has attracted considerable research effort recently. Most existing approaches assume that the underlying propagation model is fixed and given as input, which may limit their application range. In this paper, we study the multiple source detection problem when the underlying propagation model is unknown. Our basic idea is source prominence, namely the nodes surrounded by larger proportions of infected nodes are more likely to be infection sources. As such, we propose a multiple source detection method called Label Propagation based Source Identification (LPSI). Our method lets infection status iteratively propagate in the network as labels, and finally uses local peaks of the label propagation result as source nodes. In addition, both the convergent and iterative versions of LPSI are given. Extensive experiments are conducted on several real-world datasets to demonstrate the effectiveness of the proposed method.