Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning

Abstract

Learning representations of sets of nodes in a graph is crucial for applications ranging from node-role discovery to link prediction and molecule classification. Graph Neural Networks (GNNs) have achieved great success in graph representation learning. However, expressive power of GNNs is limited by the 1-Weisfeiler-Lehman (WL) test and thus GNNs generate identical representations for graph substructures that may in fact be very different. More powerful GNNs, proposed recently by mimicking higher-order-WL tests, only focus on representing entire graphs and they are computationally inefficient as they cannot utilize sparsity of the underlying graph. Here we propose and mathematically analyze a general class of structure-related features, termed Distance Encoding (DE). DE assists GNNs in representing any set of nodes, while providing strictly more expressive power than the 1-WL test. DE captures the distance between the node set whose representation is to be learned and each node in the graph. To capture the distance DE can apply various graph-distance measures such as shortest path distance or generalized PageRank scores. We propose two ways for GNNs to use DEs (1) as extra node features, and (2) as controllers of message aggregation in GNNs. Both approaches can utilize the sparse structure of the underlying graph, which leads to computational efficiency and scalability. We also prove that DE can distinguish node sets embedded in almost all regular graphs where traditional GNNs always fail. We evaluate DE on three tasks over six real networks: structural role prediction, link prediction, and triangle prediction. Results show that our models outperform GNNs without DE by up-to 15\% in accuracy and AUROC. Furthermore, our models also significantly outperform other state-of-the-art methods especially designed for the above tasks.

NeurIPS 2020

References in corpus (21)

• Finding community structure in networks using the eigenvectors of matrices
• Inductive Representation Learning on Large Graphs
• Neural Message Passing for Quantum Chemistry
• Higher-order organization of complex networks
• struc2vec: Learning Node Representations from Structural Identity
• Variational Graph Auto-Encoders
• Biological network comparison using graphlet degree distribution
• Nonoptimal Component Placement, but Short Processing Paths, due to Long-Distance Projections in Neural Systems
• Simplicial Closure and higher-order link prediction
• Learning Structural Node Embeddings Via Diffusion Wavelets
• Link Prediction Based on Graph Neural Networks
• Graph Isomorphism in Quasipolynomial Time
• Role Discovery in Networks
• Universal Invariant and Equivariant Graph Neural Networks
• Molecule Attention Transformer
• Invariant and Equivariant Graph Networks
• Adaptive Universal Generalized PageRank Graph Neural Network
• Position-aware Graph Neural Networks
• Covariant Compositional Networks For Learning Graphs
• Can Graph Neural Networks Count Substructures?
• Optimizing Generalized PageRank Methods for Seed-Expansion Community Detection

Cited by in corpus (18)

• A Generalization of Transformer Networks to Graphs
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
• SIGformer: Sign-aware Graph Transformer for Recommendation
• Networked Time Series Imputation via Position-aware Graph Enhanced Variational Autoencoders
• A Network Science perspective of Graph Convolutional Networks: A survey
• Projective Ranking-based GNN Evasion Attacks
• LPFormer: An Adaptive Graph Transformer for Link Prediction
• Multiresolution Graph Transformers and Wavelet Positional Encoding for Learning Hierarchical Structures
• SUREL+: Moving from Walks to Sets for Scalable Subgraph-based Graph Representation Learning
• Principled Hyperedge Prediction with Structural Spectral Features and Neural Networks
• On Graph Neural Networks versus Graph-Augmented MLPs
• Learning Scalable Structural Representations for Link Prediction with Bloom Signatures
• Learning Domain-Independent Heuristics for Grounded and Lifted Planning
• Hierarchical Position Embedding of Graphs with Landmarks and Clustering for Link Prediction
• Rankformer: A Graph Transformer for Recommendation based on Ranking Objective
• Breaking the Expressive Bottlenecks of Graph Neural Networks
• Graph Attention Networks with Positional Embeddings
• Understanding the Design Principles of Link Prediction in Directed Settings