Graph Random Neural Features for Distance-Preserving Graph Representations

Daniele Zambon, Cesare Alippi, Lorenzo Livi
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:10968-10977, 2020.

Abstract

We present Graph Random Neural Features (GRNF), a novel embedding method from graph-structured data to real vectors based on a family of graph neural networks. The embedding naturally deals with graph isomorphism and preserves the metric structure of the graph domain, in probability. In addition to being an explicit embedding method, it also allows us to efficiently and effectively approximate graph metric distances (as well as complete kernel functions); a criterion to select the embedding dimension trading off the approximation accuracy with the computational cost is also provided. GRNF can be used within traditional processing methods or as a training-free input layer of a graph neural network. The theoretical guarantees that accompany GRNF ensure that the considered graph distance is metric, hence allowing to distinguish any pair of non-isomorphic graphs.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-zambon20a, title = {Graph Random Neural Features for Distance-Preserving Graph Representations}, author = {Zambon, Daniele and Alippi, Cesare and Livi, Lorenzo}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {10968--10977}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/zambon20a/zambon20a.pdf}, url = {https://proceedings.mlr.press/v119/zambon20a.html}, abstract = {We present Graph Random Neural Features (GRNF), a novel embedding method from graph-structured data to real vectors based on a family of graph neural networks. The embedding naturally deals with graph isomorphism and preserves the metric structure of the graph domain, in probability. In addition to being an explicit embedding method, it also allows us to efficiently and effectively approximate graph metric distances (as well as complete kernel functions); a criterion to select the embedding dimension trading off the approximation accuracy with the computational cost is also provided. GRNF can be used within traditional processing methods or as a training-free input layer of a graph neural network. The theoretical guarantees that accompany GRNF ensure that the considered graph distance is metric, hence allowing to distinguish any pair of non-isomorphic graphs.} }
Endnote
%0 Conference Paper %T Graph Random Neural Features for Distance-Preserving Graph Representations %A Daniele Zambon %A Cesare Alippi %A Lorenzo Livi %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-zambon20a %I PMLR %P 10968--10977 %U https://proceedings.mlr.press/v119/zambon20a.html %V 119 %X We present Graph Random Neural Features (GRNF), a novel embedding method from graph-structured data to real vectors based on a family of graph neural networks. The embedding naturally deals with graph isomorphism and preserves the metric structure of the graph domain, in probability. In addition to being an explicit embedding method, it also allows us to efficiently and effectively approximate graph metric distances (as well as complete kernel functions); a criterion to select the embedding dimension trading off the approximation accuracy with the computational cost is also provided. GRNF can be used within traditional processing methods or as a training-free input layer of a graph neural network. The theoretical guarantees that accompany GRNF ensure that the considered graph distance is metric, hence allowing to distinguish any pair of non-isomorphic graphs.
APA
Zambon, D., Alippi, C. & Livi, L.. (2020). Graph Random Neural Features for Distance-Preserving Graph Representations. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:10968-10977 Available from https://proceedings.mlr.press/v119/zambon20a.html.

Related Material