Chen, Haochen (Stony Brook University) | Perozzi, Bryan (Google Research) | Hu, Yifan (Yahoo! Research) | Skiena, Steven (Stony Brook University)

We present HARP, a novel method for learning low dimensional embeddings of a graph’s nodes which preserves higher-order structural features. Our proposed method achieves this by compressing the input graph prior to embedding it, effectively avoiding troublesome embedding configurations (i.e. local minima) which can pose problems to non-convex optimization. HARP works by finding a smaller graph which approximates the global structure of its input. This simplified graph is used to learn a set of initial representations, which serve as good initializations for learning representations in the original, detailed graph. We inductively extend this idea, by decomposing a graph in a series of levels, and then embed the hierarchy of graphs from the coarsest one to the original graph. HARP is a general meta-strategy to improve all of the state-of-the-art neural algorithms for embedding graphs, including DeepWalk, LINE, and Node2vec. Indeed, we demonstrate that applying HARP’s hierarchical paradigm yields improved implementations for all three of these methods, as evaluated on classification tasks on real-world graphs such as DBLP, BlogCatalog, and CiteSeer, where we achieve a performance gain over the original implementations by up to 14% Macro F1.

Hamilton, Will, Ying, Zhitao, Leskovec, Jure

Low-dimensional embeddings of nodes in large graphs have proved extremely useful in a variety of prediction tasks, from content recommendation to identifying protein functions. However, most existing approaches require that all nodes in the graph are present during training of the embeddings; these previous approaches are inherently transductive and do not naturally generalize to unseen nodes. Here we present GraphSAGE, a general, inductive framework that leverages node feature information (e.g., text attributes) to efficiently generate node embeddings. Instead of training individual embeddings for each node, we learn a function that generates embeddings by sampling and aggregating features from a node's local neighborhood. Our algorithm outperforms strong baselines on three inductive node-classification benchmarks: we classify the category of unseen nodes in evolving information graphs based on citation and Reddit post data, and we show that our algorithm generalizes to completely unseen graphs using a multi-graph dataset of protein-protein interactions.

Hamilton, William L., Ying, Rex, Leskovec, Jure

Low-dimensional embeddings of nodes in large graphs have proved extremely useful in a variety of prediction tasks, from content recommendation to identifying protein functions. However, most existing approaches require that all nodes in the graph are present during training of the embeddings; these previous approaches are inherently transductive and do not naturally generalize to unseen nodes. Here we present GraphSAGE, a general, inductive framework that leverages node feature information (e.g., text attributes) to efficiently generate node embeddings for previously unseen data. Instead of training individual embeddings for each node, we learn a function that generates embeddings by sampling and aggregating features from a node's local neighborhood. Our algorithm outperforms strong baselines on three inductive node-classification benchmarks: we classify the category of unseen nodes in evolving information graphs based on citation and Reddit post data, and we show that our algorithm generalizes to completely unseen graphs using a multi-graph dataset of protein-protein interactions.

Chaturvedi, Iti (Nanyang Technological University) | Cambria, Erik (Nanyang Technological University) | Cavallari, Sandro (Nanyang Technological University) | Zheng, Vincent (Advanced Digital Sciences Center)

Textual queries in networks such as Twitter can have more than one label resulting in a multi-label classification problem. To reduce computational costs a low-dimensional representation of a large network is learned that preserves proximity among nodes in the same community. Similar to sequence of words in a sentence, DeepWalk consider sequence of nodes in a shallow graph and clustering is done using hierarchical softmax in an unsupervised manner. In this paper, we generate network abstractions at different levels using deep convolutional neural networks. Since, class labels of connected nodes in a network keep changing we consider a fuzzy recurrent feedback controller to ensure robustness to noise.

Hu, Fenyu, Zhu, Yanqiao, Wu, Shu, Wang, Liang, Tan, Tieniu

Graph convolutional networks (GCNs) have been successfully applied in node classification tasks of network mining. However, most of models based on neighborhood aggregation are usually shallow and lack the "graph pooling" mechanism, which prevents the model from obtaining adequate global information. In order to increase the receptive field, we propose a novel deep Hierarchical Graph Convolutional Network (H-GCN) for semi-supervised node classification. H-GCN first repeatedly aggregates structurally similar nodes to hyper-nodes and then refines the coarsened graph to the original to restore the representation for each node. Instead of merely aggregating one- or two-hop neighborhood information, the proposed coarsening procedure enlarges the receptive field for each original node, hence more global information can be learned. Comprehensive experiments conducted on public datasets demonstrate effectiveness of the proposed method over the state-of-art methods. Notably, our model gains substantial improvements when only very few labeled samples are provided.