Learning Structural Node Embeddings via Diffusion Wavelets

By Claire Donnat, Marinka Zitnik, David Hallac, Jure Leskovec. 2017

444 citations recorded by the source corpus.

Nodes residing in different parts of a graph can have similar structural roles within their local network topology. The identification of such roles provides key insight into the organization of networks and can be used for a variety of machine learning tasks. However, learning structural representations of nodes is a challenging problem, and it has typically involved manually specifying and tailoring topological features for each node. In this paper, we develop GraphWave, a method that represents each node's network neighborhood via a low-dimensional embedding by leveraging heat wavelet diffusion patterns. Instead of training on hand-selected features, GraphWave learns these embeddings in an unsupervised way. We mathematically prove that nodes with similar network neighborhoods will have similar GraphWave embeddings even though these nodes may reside in very different parts of the network, and our method scales linearly with the number of edges. Experiments in a variety of different settings demonstrate GraphWave's real-world potential for capturing structural roles in networks, and our approach outperforms existing state-of-the-art baselines in every experiment, by as much as 137%.

Subfields: Artificial Intelligence, Information Systems, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

In Statistical and Nonlinear Physics

Citations in the corpus

Deep Graph Infomax (2018, methodology): “…driven to preserve mutual information with the global graph summary, this allows for discovering and preserving similarities on the patch-level—for example, distant nodes with similar structural roles (which are known to be a strong predictor for many node classiﬁcation tasks; Donnat et al., 2018).”
Representation Learning on Graphs: Methods and Applications (2017, background): “[20] have developed node embedding approaches that are specifically designed to capture structural roles.”
Graph Wavelet Neural Network (2019, methodology): “Owing to the property of describing information diffusion, Donnat et al. (2018) learned structural node embeddings via wavelets.”
GNNGuard: Defending Graph Neural Networks against Adversarial Attacks (2020, methodology): “We synthesize cycle graphs with attached house shapes (see an example in Figure 3), where labels are defined by nodes’ structural roles [25].”
On the Equivalence between Positional Node Embeddings and Structural Graph Representations (2019, background): “iction and clustering. However, once the literature started deﬁning relative node closeness with respect to structural neighborhood similarities (e.g., Henderson et al. (2012); Ribeiro et al. (2017); Donnat et al. (2018)), node embeddings and structural representations became more strangely entangle”
Temporal Relational Ranking for Stock Prediction (2018, methodology): “Graph Convolutional Network (GCN) is a special kind of graph-based learning methods, which integrates the core idea of graph-based learning ( i.e., the smoothness assumption over graphs) with advanced convolutional neural networks (CNNs) [8, 10, 14, 20].”
Adversarial Graph Augmentation to Improve Graph Contrastive Learning (2021, unknown): “Experiments showed that these GNN models learn to over-emphasize node proximity [23] and may lose subtle but crucial structural information, thus failing in many tasks including node-role classiﬁcation [16,35,37,38] and graph classiﬁcation [17].”
Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning (2020, background): “…a graph can be leveraged for a wide range of applications, such as discovery of functions/roles of nodes based on individual node representations [2–6], link or link type prediction based on node-pair representations [7–10] and graph comparison or molecule classiﬁcation based on entire-graph…”
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training (2020, methodology): “We can see that, compared with Panther++ [66] and GraphWave [12] which are trained in place on co-author graphs, simply applying pre-trained GCC can be competitive.”
Rethinking Graph Neural Networks for Anomaly Detection (2022, methodology): “We discuss the differences between the proposed BWGNN and other related wavelet GNNs. Heat kernel-based methods (Xu et al., 2019a; Donnat et al., 2018; Li et al., 2021) do not essentially satisfy Hammond’s graph wavelet theory (Hammond et al., 2011) because they are not band-pass.”