Inductive Representation Learning on Large Graphs

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "arXiv — non-exclusive licence to distribute" does not allow redistributing the text itself. Original — arxiv.org/pdf/1706.02216

Summary

Most node-embedding methods learn one vector per node of a fixed graph. They cannot place nodes they did not see during training without retraining, which is a problem for graphs that keep growing (new posts, users, papers) and for moving a model to a new graph. Hamilton, Ying and Leskovec present GraphSAGE, an inductive framework. Instead of storing an embedding for each node, it learns functions that build a node's representation from its own features and a fixed-size sample of its neighbours' features, repeated over several hops. The aggregators they test are mean, LSTM, max-pooling and a GCN-style variant. The model can be trained with an unsupervised, random-walk-based loss or trained end-to-end on labels. It is evaluated on three node-classification tasks: an evolving citation graph, Reddit posts and multiple protein-protein interaction (PPI) graphs. GraphSAGE beats feature-only and transductive baselines while producing embeddings for new nodes far faster. This made the work a foundation for scalable, production-ready graph neural networks.

Key points

Benchmarks: paper subject classification on citation data, community (subreddit) prediction on Reddit, and protein-function prediction on PPI. PPI tests whether a model trained on some graphs works on entirely unseen graphs.
Main result: the supervised GraphSAGE raises F1 by about 51% on average over a classifier that uses only raw node features. It also beats a strong transductive embedding baseline (DeepWalk), which is roughly 100× slower at inference on new nodes.
Aggregators: the proposed LSTM and pooling aggregators improve on the GCN-inspired aggregator by about 7.4% on average. A Wilcoxon signed-rank test over 6 settings gives p ≈ 0.02. LSTM and pooling perform about the same, but pooling is roughly 2× faster.
Neighbourhood sampling: sampling a fixed number of neighbours keeps memory and runtime bounded per batch while preserving most of the accuracy.
Theory: if every node's features are distinct, the algorithm with K = 4 search depths can approximate any node's clustering coefficient to arbitrary precision. This shows that a feature-based model can still learn graph structure.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Other

Cited by

559 papers of our library cite it (of the 140673 whose bibliographies we read); 6 of them have a page here, 553 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1706.02216 · arXiv 1706.02216

@misc{hamilton2017inductive,
  title = {{Inductive Representation Learning on Large Graphs}},
  author = {Hamilton, William L. and Ying, Rex and Leskovec, Jure},
  year = {2017},
  doi = {10.48550/arxiv.1706.02216},
  eprint = {1706.02216},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1706.02216}
}

References

41 references, 5 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

M. Abadi, A. Agarwal, P. Barham, E. Brevdo, Z. Chen, C. Citro, G. S. Corrado, A. Davis, J. Dean, M. Devin, et al. Tensorflow: Large-scale machine learning on heterogeneous distributed systems. arXiv preprint , 2016. find our card
S. Arora, Y. Liang, and T. Ma. A simple but tough-to-beat baseline for sentence embeddings. In ICLR, 2017. find
A. R. Benson, D. F. Gleich, and J. Leskovec. Higher-order organization of complex networks. Science, 353(6295):163–166, 2016. find
J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun. Spectral networks and locally connected networks on graphs. In ICLR, 2014. find
S. Cao, W. Lu, and Q. Xu. Grarep: Learning graph representations with global structural information. In KDD, 2015. find
J. Chen and J. Zhu. Stochastic training of graph convolutional networks. arXiv preprint arXiv:1710.10568, 2017. — [arXiv:1710.10568](https://arxiv.org/abs/1710.10568) find
H. Dai, B. Dai, and L. Song. Discriminative embeddings of latent variable models for structured data. In ICML, 2016. find
M. Defferrard, X. Bresson, and P. Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NIPS, 2016. find our card
D. K. Duvenaud, D. Maclaurin, J. Iparraguirre, R. Bombarell, T. Hirzel, A. Aspuru-Guzik, and R. P. Adams. Convolutional networks on graphs for learning molecular fingerprints. In NIPS, 2015. find
M. Gori, G. Monfardini, and F. Scarselli. A new model for learning in graph domains. In IEEE International Joint Conference on Neural Networks, volume 2, pages 729–734, 2005. find
A. Grover and J. Leskovec. node2vec: Scalable feature learning for networks. In KDD, 2016. find
W. L. Hamilton, J. Leskovec, and D. Jurafsky. Diachronic word embeddings reveal statistical laws of semantic change. In ACL, 2016. find our card
K. He, X. Zhang, S. Ren, and J. Sun. Identity mappings in deep residual networks. In EACV, 2016. find
S. Hochreiter and J. Schmidhuber. Long short-term memory. Neural Computation, 9(8):1735– 1780, 1997. find
K. Hornik. Approximation capabilities of multilayer feedforward networks. Neural Networks, 4(2):251–257, 1991. find
D. Kingma and J. Ba. Adam: A method for stochastic optimization. In ICLR, 2015. find
T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2016. find our card
T. N. Kipf and M. Welling. Variational graph auto-encoders. In NIPS Workshop on Bayesian Deep Learning, 2016. find
J. B. Kruskal. Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis. Psychometrika, 29(1):1–27, 1964. find
O. Levy and Y. Goldberg. Neural word embedding as implicit matrix factorization. In NIPS, 2014. find
Y. Li, D. Tarlow, M. Brockschmidt, and R. Zemel. Gated graph sequence neural networks. In ICLR, 2015. find
T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean. Distributed representations of words and phrases and their compositionality. In NIPS, 2013. find
A. Y. Ng, M. I. Jordan, Y. Weiss, et al. On spectral clustering: Analysis and an algorithm. In NIPS, 2001. find
M. Niepert, M. Ahmed, and K. Kutzkov. Learning convolutional neural networks for graphs. In ICML, 2016. find
L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999. find our card
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825–2830… find
J. Pennington, R. Socher, and C. D. Manning. Glove: Global vectors for word representation. In EMNLP, 2014. find
B. Perozzi, R. Al-Rfou, and S. Skiena. Deepwalk: Online learning of social representations. In KDD, 2014. find
C. R. Qi, H. Su, K. Mo, and L. J. Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In CVPR, 2017. find
R. Řehůřek and P. Sojka. Software Framework for Topic Modelling with Large Corpora. In LREC, 2010. find
F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61–80, 2009. find
N. Shervashidze, P. Schweitzer, E. J. v. Leeuwen, K. Mehlhorn, and K. M. Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12:2539–2561, 2011. find
S. Siegal. Nonparametric statistics for the behavioral sciences. McGraw-hill, 1956. find
A. Subramanian, P. Tamayo, V. K. Mootha, S. Mukherjee, B. L. Ebert, M. A. Gillette, A. Paulovich, S. L. Pomeroy, T. R. Golub, E. S. Lander, et al. Gene set enrichment analysis: a knowledge-based approach for interpreting genome-wide expression profiles. Proceedings of the National Academy of Science… find
J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei. Line: Large-scale information network embedding. In WWW, 2015. find
D. Wang, P. Cui, and W. Zhu. Structural deep network embedding. In KDD, 2016. find
X. Wang, P. Cui, J. Wang, J. Pei, W. Zhu, and S. Yang. Community preserving network embedding. In AAAI, 2017. find
D. J. Watts and S. H. Strogatz. Collective dynamics of ‘small-world’ networks. Nature, 393(6684):440–442, 1998. find
L. Xu, X. Wei, J. Cao, and P. S. Yu. Embedding identity and interest for social networks. In WWW, 2017. find
Z. Yang, W. Cohen, and R. Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In ICML, 2016. find
M. Zitnik and J. Leskovec. Predicting multicellular function through multi-layer tissue networks. Bioinformatics, 33(14):190–198, 2017. find