Graph Random Neural Features for Distance-Preserving Graph Representations
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.
Code (1)
Tasks
Graph Neural NetworkSimilar Papers 제목 키워드 기반
Local Distance-Preserving Node Embeddings and Their Performance on Random Graphs
Learning node representations is a fundamental problem in graph machine learning. While existing embedding methods effectively preserve local similarity measures, they often fail to capture global functions like graph di…
Graph Representation LearningRepresentation LearningGeodesic Distance Between Graphs: A Spectral Metric for Assessing the Stability of Graph Neural Networks
This paper presents a spectral framework for assessing the generalization and stability of Graph Neural Networks (GNNs) by introducing a Graph Geodesic Distance (GGD) metric. For two different graphs with the same number…
Graph MatchingFree Lunch for Privacy Preserving Distributed Graph Learning
Learning on graphs is becoming prevalent in a wide range of applications including social networks, robotics, communication, medicine, etc. These datasets belonging to entities often contain critical private information.…
Graph LearningPrivacy PreservingRandom Projections of Sparse Adjacency Matrices
We analyze a random projection method for adjacency matrices, studying its utility in representing sparse graphs. We show that these random projections retain the functionality of their underlying adjacency matrices whil…
Graph Random Features for Scalable Gaussian Processes
We study the application of graph random features (GRFs) - a recently introduced stochastic estimator of graph node kernels - to scalable Gaussian processes on discrete input spaces. We prove that (under mild assumptions…
Bayesian InferenceGaussian Processes