Vertex classification: Vertex...

Vertex classification:

Vertex classification aims to assign a class label to each node in a graph based on the information learned from other labeled nodes. Intuitively, similar nodes should have the same label. For example, closely-related publication may be labeled as the same topic in the citation graph while individuals of the same gender, similar age, and shared interests may have the same preference in social networks. Graph embedding methods embed each node into a low-dimensional vector. Given an embedded vector, a trained classifier can predict the label of a vertex of interest, where the classifier can be support vector machine (SVM) [84], logistic regression [85], kNN (k nearest neighbors) [86], etc. The vertex label can be obtained in an unsupervised or semi-supervised way. Node clustering is an unsupervised method that groups similar nodes together. It is useful when labels are unavailable. The semi-supervised method can be used when part of the data are labeled. The F1 score is used for evaluation in binary-class classification, while the micro-F1 score is used in multi-class classification. Since accurate vertex representations contribute to high classification accuracy, vertex classification can be used to measure the performance of different graph embedding methods.

Table 2

Summary of different graph embedding methods

Category	Example algorithm	Advantage	Disadvantage
Dimension reduction based	PCA, LDA, MDS, Isomap, LLE, Kernel methods	Mathematicallytractable, well understood and easy to implement	Cannot capture higher order proximity well
Random walk based	DeepWalk, node2vec	Does not take the whole graph at once	Sometimes cannot capture global information very well
Matrix factorization based	Graph Laplacian Eigenmaps, Node proximity Matrix Factorization, TADW, HSCA, GraRep, HOPE	Can capture global structure	High time complexity
Neural network based	GCN, SGCN, VGAE, GraphSAGE, SDNE,	State-of-the-art performance	Hardware demanding,training with BP is time consuming
Large graph embedding Hyper Graph Embedding	LGCL, GPNN, LINE Spectral Hyper-graphembedding, HGNN, DHNE	Good scalability Can model more complex data	High time complexity More difficult to implement
Attention graph embedding Others	GAT, Attention Walks, AGRNN GraphGAN, GenVector	Better long distance node modeling Provide more alternatives	High time complexity Proof-of-concept stage

Category	Example algorithm	Advantage	Disadvantage
Dimension reduction based	PCA, LDA, MDS, Isomap, LLE, Kernel methods	Mathematicallytractable, well understood and easy to implement	Cannot capture higher order proximity well
Random walk based	DeepWalk, node2vec	Does not take the whole graph at once	Sometimes cannot capture global information very well
Matrix factorization based	Graph Laplacian Eigenmaps, Node proximity Matrix Factorization, TADW, HSCA, GraRep, HOPE	Can capture global structure	High time complexity
Neural network based	GCN, SGCN, VGAE, GraphSAGE, SDNE,	State-of-the-art performance	Hardware demanding,training with BP is time consuming
Large graph embedding Hyper Graph Embedding	LGCL, GPNN, LINE Spectral Hyper-graphembedding, HGNN, DHNE	Good scalability Can model more complex data	High time complexity More difficult to implement
Attention graph embedding Others	GAT, Attention Walks, AGRNN GraphGAN, GenVector	Better long distance node modeling Provide more alternatives	High time complexity Proof-of-concept stage

[ViewLarge]

Link prediction [87]:
Link prediction aims to infer the existence of relationship or interaction among pairs of vertices in a graph. The learned representation should help infer the graph structure, especially when some links are missing. For example, links might be missing between two users and link prediction can be used to recommend friends in social networks. The learned representation should preserve the network proximity and the structural similarity among vertices. The information encoded in the vector representation for each vertex can be used to predict missing links in incomplete networks. The link prediction performance can be measured by the area under curveor the receiver operating characteristiccurve. A better representation should be able to capture the connections among vertices better.

Sharing Unavailable