Learning Structural Node Embeddings Via Diffusion Wavelets

Abstract

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%.

The 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, August 19--23, 2018, London, United Kingdom

References in corpus (4)

• Inductive Representation Learning on Large Graphs
• Emergence of network features from multiplexity
• Learning Graph Representations with Embedding Propagation
• Axiomatic Ranking of Network Role Similarity

Cited by in corpus (75)

• Self-supervised Learning: Generative or Contrastive
• GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
• REGAL: Representation Learning-based Graph Alignment
• Graph Signal Processing: History, Development, Impact, and Outlook
• Graph Neural Networks: Taxonomy, Advances and Trends
• Adversarial Graph Augmentation to Improve Graph Contrastive Learning
• GNNGuard: Defending Graph Neural Networks against Adversarial Attacks
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning
• Filter-informed Spectral Graph Wavelet Networks for Multiscale Feature Extraction and Intelligent Fault Diagnosis
• Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patterns
• Measuring and Improving the Use of Graph Information in Graph Neural Networks
• A Broader Picture of Random-walk Based Graph Embedding
• Network Representation Learning: A Survey
• Subgraph Neural Networks
• Heterogeneous Network Representation Learning: A Unified Framework with Survey and Benchmark
• Beyond Low-Pass Filters: Adaptive Feature Propagation on Graphs
• Network Embedding: An Overview
• GraphSAC: Detecting anomalies in large-scale graphs
• Learning to Identify High Betweenness Centrality Nodes from Scratch: A Novel Graph Neural Network Approach
• Graph embeddings for Abusive Language Detection
• Beyond Localized Graph Neural Networks: An Attributed Motif Regularization Framework
• DEMO-Net: Degree-specific Graph Neural Networks for Node and Graph Classification
• Source Free Unsupervised Graph Domain Adaptation
• Graph Learning Network: A Structure Learning Algorithm
• Embedding Node Structural Role Identity into Hyperbolic Space
• Multiresolution Graph Transformers and Wavelet Positional Encoding for Learning Hierarchical Structures
• Karate Club: An API Oriented Open-source Python Framework for Unsupervised Learning on Graphs
• Graph Meta Learning via Local Subgraphs
• Dirichlet Graph Variational Autoencoder
• Discriminative structural graph classification
• Influence maximization in unknown social networks: Learning Policies for Effective Graph Sampling
• Cross-GCN: Enhancing Graph Convolutional Network with $k$-Order Feature Interactions
• RiWalk: Fast Structural Node Embedding via Role Identification
• Twitch Gamers: a Dataset for Evaluating Proximity Preserving and Structural Role-based Node Embeddings
• Deconvolutional Networks on Graph Data
• A novel similarity measure for mining missing links in long-path networks
• Embedding Node Structural Role Identity Using Stress Majorization
• Calibrating and Improving Graph Contrastive Learning
• ANAE: Learning Node Context Representation for Attributed Network Embedding
• Deep Node Ranking for Neuro-symbolic Structural Node Embedding and Classification
• Better with Less: A Data-Active Perspective on Pre-Training Graph Neural Networks
• Representation Learning on Graphs: A Reinforcement Learning Application
• Graph Autoencoders with Deconvolutional Networks
• Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank
• Spectral Graph Attention Network with Fast Eigen-approximation
• Ego-based Entropy Measures for Structural Representations
• Hypergraph Neural Network with State Space Models for Node Classification
• The Autodidactic Universe
• GraLSP: Graph Neural Networks with Local Structural Patterns
• Heterogeneous Hypergraph Embedding for Graph Classification
• PINE: Universal Deep Embedding for Graph Nodes via Partial Permutation Invariant Set Functions
• Learning Optimal Graph Filters for Clustering of Attributed Graphs
• Graph-Level Embedding for Time-Evolving Graphs
• A Deep Graph Wavelet Convolutional Neural Network for Semi-supervised Node Classification
• From Static to Dynamic Node Embeddings
• Inferential SIR-GN: Scalable Graph Representation Learning
• Dynamic Graph Embedding via LSTM History Tracking
• Fast Mesh Data Augmentation via Chebyshev Polynomial of Spectral filtering
• Dynamic Network Embedding via Incremental Skip-gram with Negative Sampling
• Stochastic Opinion Dynamics for Interest Prediction in Social Networks
• Conversation-Based Multimodal Abuse Detection Through Text and Graph Embeddings
• PanRep: Graph neural networks for extracting universal node embeddings in heterogeneous graphs
• MOHONE: Modeling Higher Order Network Effects in KnowledgeGraphs via Network Infused Embeddings
• struc2gauss: Structural Role Preserving Network Embedding via Gaussian Embedding
• Contributions to Representation Learning with Graph Autoencoders and Applications to Music Recommendation
• A Consistent Diffusion-Based Algorithm for Semi-Supervised Graph Learning
• A Survey on Role-Oriented Network Embedding
• Self-Supervised Graph Learning with Proximity-based Views and Channel Contrast
• Graph Structural-topic Neural Network
• A Consistent Diffusion-Based Algorithm for Semi-Supervised Classification on Graphs
• Exemplar-based Layout Fine-tuning for Node-link Diagrams
• Spectral Embedding of Graph Networks
• Fast Polynomial Approximation of Heat Kernel Convolution on Manifolds and Its Application to Brain Sulcal and Gyral Graph Pattern Analysis
• Graph Embedding via Diffusion-Wavelets-Based Node Feature Distribution Characterization
• Role Similarity Metric Based on Spanning Rooted Forest