A simple and effective convolutional operator for node classification without features by graph convolutional networks.

Graph neural networks (GNNs), with their ability to incorporate node features into graph learning, have achieved impressive performance in many graph analysis tasks. However, current GNNs including the popular graph convolutional network (GCN) cannot obtain competitive results on the graphs without node features. In this work, we first introduce path-driven neighborhoods, and then define an extensional adjacency matrix as a convolutional operator. Second, we propose an approach named exopGCN which integrates the simple and effective convolutional operator into GCN to classify the nodes in the graphs without features. Experiments on six real-world graphs without node features indicate that exopGCN achieves better performance than other GNNs on node classification. Furthermore, by adding the simple convolutional operator into 13 GNNs, the accuracy of these methods are improved remarkably, which means that our research can offer a general skill to improve accuracy of GNNs. More importantly, we study the relationship between node classification by GCN without node features and community detection. Extensive experiments including six real-world graphs and nine synthetic graphs demonstrate that the positive relationship between them can provide a new direction on exploring the theories of GCNs.

Path-enhanced graph convolutional networks for node classification without features.

Most current graph neural networks (GNNs) are designed from the view of methodology and rarely consider the inherent characters of graph. Although the inherent characters may impact the performance of GNNs, very few methods are proposed to resolve the issue. In this work, we mainly focus on improving the performance of graph convolutional networks (GCNs) on the graphs without node features. In order to resolve the issue, we propose a method called t-hopGCN to describe t-hop neighbors by the shortest path between two nodes, then the adjacency matrix of t-hop neighbors as features to perform node classification. Experimental results show that t-hopGCN can significantly improve the performance of node classification in the graphs without node features. More importantly, adding the adjacency matrix of t-hop neighbors can improve the performance of existing popular GNNs on node classification.

Study on the evolution of Chinese characters based on few-shot learning: From oracle bone inscriptions to regular script.

Oracle bone inscriptions (OBIs) are ancient Chinese scripts originated in the Shang Dynasty of China, and now less than half of the existing OBIs are well deciphered. To date, interpreting OBIs mainly relies on professional historians using the rules of OBIs evolution, and the remaining part of the oracle's deciphering work is stuck in a bottleneck period. Here, we systematically analyze the evolution process of oracle characters by using the Siamese network in Few-shot learning (FSL). We first establish a dataset containing Chinese characters which have finished a relatively complete evolution, including images in five periods: oracle bone inscriptions, bronze inscriptions, seal inscriptions, official script, and regular script. Then, we compare the performance of three typical algorithms, VGG16, ResNet, and AlexNet respectively, as the backbone feature extraction network of the Siamese network. The results show that the highest F1 value of 83.3% and the highest recognition accuracy of 82.67% are obtained by the combination of VGG16 and Siamese network. Based on the analysis, the typical structural performance of each period is evaluated and we identified that the optimized Siamese network is feasible to study the evolution of the OBIs. Our findings provide a new approach for oracle's deciphering further.

A new multi-scale method to reveal hierarchical modular structures in biological networks.

Biological networks are effective tools for studying molecular interactions. Modular structure, in which genes or proteins may tend to be associated with functional modules or protein complexes, is a remarkable feature of biological networks. Mining modular structure from biological networks enables us to focus on a set of potentially important nodes, which provides a reliable guide to future biological experiments. The first fundamental challenge in mining modular structure from biological networks is that the quality of the observed network data is usually low owing to noise and incompleteness in the obtained networks. The second problem that poses a challenge to existing approaches to the mining of modular structure is that the organization of both functional modules and protein complexes in networks is far more complicated than was ever thought. For instance, the sizes of different modules vary considerably from each other and they often form multi-scale hierarchical structures. To solve these problems, we propose a new multi-scale protocol for mining modular structure (named ISIMB) driven by a node similarity metric, which works in an iteratively converged space to reduce the effects of the low data quality of the observed network data. The multi-scale node similarity metric couples both the local and the global topology of the network with a resolution regulator. By varying this resolution regulator to give different weightings to the local and global terms in the metric, the ISIMB method is able to fit the shape of modules and to detect them on different scales. Experiments on protein-protein interaction and genetic interaction networks show that our method can not only mine functional modules and protein complexes successfully, but can also predict functional modules from specific to general and reveal the hierarchical organization of protein complexes.

Revealing the hidden relationship by sparse modules in complex networks with a large-scale analysis.

One of the remarkable features of networks is module that can provide useful insights into not only network organizations but also functional behaviors between their components. Comprehensive efforts have been devoted to investigating cohesive modules in the past decade. However, it is still not clear whether there are important structural characteristics of the nodes that do not belong to any cohesive module. In order to answer this question, we performed a large-scale analysis on 25 complex networks with different types and scales using our recently developed BTS (bintree seeking) algorithm, which is able to detect both cohesive and sparse modules in the network. Our results reveal that the sparse modules composed by the cohesively isolated nodes widely co-exist with the cohesive modules. Detailed analysis shows that both types of modules provide better characterization for the division of a network into functional units than merely cohesive modules, because the sparse modules possibly re-organize the nodes in the so-called cohesive modules, which lack obvious modular significance, into meaningful groups. Compared with cohesive modules, the sizes of sparse ones are generally smaller. Sparse modules are also found to have preferences in social and biological networks than others.

BinTree seeking: a novel approach to mine both bi-sparse and cohesive modules in protein interaction networks.

Modern science of networks has brought significant advances to our understanding of complex systems biology. As a representative model of systems biology, Protein Interaction Networks (PINs) are characterized by a remarkable modular structures, reflecting functional associations between their components. Many methods were proposed to capture cohesive modules so that there is a higher density of edges within modules than those across them. Recent studies reveal that cohesively interacting modules of proteins is not a universal organizing principle in PINs, which has opened up new avenues for revisiting functional modules in PINs. In this paper, functional clusters in PINs are found to be able to form unorthodox structures defined as bi-sparse module. In contrast to the traditional cohesive module, the nodes in the bi-sparse module are sparsely connected internally and densely connected with other bi-sparse or cohesive modules. We present a novel protocol called the BinTree Seeking (BTS) for mining both bi-sparse and cohesive modules in PINs based on Edge Density of Module (EDM) and matrix theory. BTS detects modules by depicting links and nodes rather than nodes alone and its derivation procedure is totally performed on adjacency matrix of networks. The number of modules in a PIN can be automatically determined in the proposed BTS approach. BTS is tested on three real PINs and the results demonstrate that functional modules in PINs are not dominantly cohesive but can be sparse. BTS software and the supporting information are available at: www.csbio.sjtu.edu.cn/bioinf/BTS/.

Large-scale mining co-expressed genes in Arabidopsis anther: from pair to group.

Research on gene co-expression not only plays an important role in understanding the complex regulatory relationships, but also contributes to our understanding of gene regulatory network. Beyond the co-expression knowledge between two genes, investigating the co-expression relationships among multiple target genes is more informative for understanding the basic working mechanisms in a cell. In this paper, all the Arabidopsis anther genes and every gene's potential co-expressed partners are collected by cross-database search. By combining simple pair gene co-expression networks, a complex Arabidopsis anther co-expression network is constructed. Maximum-clique algorithm is then applied to mine the groups reflecting co-expression relationships among multiple Arabidopsis anther genes that are represented by completely connected graphs. As a result, 254 Arabidopsis anther complete co-expression groups are obtained and our analysis shows that all the genes in the same group have high propensity to be functionally related and co-expressed together. We also demonstrate the efficacy of the proposed maximum-clique algorithm by comparing its results with the known Arabidopsis genome pathways, K-means clustering algorithm derived results and randomized data. It is expected that the 254 Arabidopsis anther complete co-expression groups generated in this paper can be a valuable knowledge source for further studies of molecular mechanisms of anther and its transcription regulations.