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

By Pan Li, Yanbang Wang, Hongwei Wang, Jure Leskovec. Neural Information Processing Systems, 2020

382 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/b8b3380efb26854bae6f51ad1d2b5a045129c5a1

How researchers see this paper

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

Citations in the corpus

Do Transformers Really Perform Badly for Graph Representation? (2021, background): “…between the center node and its higher-order neighbors; a distance-weighted aggregation scheme on graph is proposed in [53]; it has been proved in [32] that adopting distance encoding (i.e., one-hot feature of the distance as extra node attribute) could lead to a strictly more expressive power…”
Recipe for a General, Powerful, Scalable Graph Transformer (2022, methodology): “A common approach is to compute the pair-wise distance between each pairs of nodes or their eigenvectors as proposed in [38, 63, 36, 57], but this is not compatible with linear Transformers as it requires to materialize the full attention matrix [12].”
Identity-aware Graph Neural Networks (2021, unknown): “Recently, many neural networks have been proposed with expressive power beyond the 1-WL test, including (Chen et al. 2019; Maron et al. 2019a; Murphy et al. 2019; You, Ying, and Leskovec 2019; Li et al. 2020).”
How Powerful are Spectral Graph Neural Networks (2022, background): “Since then, various works have attempted to analyze GNNs with the WL test and graph isomorphism testing (Zhang et al., 2018; Morris et al., 2019; Maron et al., 2019a; Chen et al., 2019; Li et al., 2020; Sato et al., 2019; 2021; Zhang et al., 2021; Zhang & Li, 2021).”
Adversarial Graph Augmentation to Improve Graph Contrastive Learning (2021, background): “GNNs have been mostly studied in cases with supervised end-to-end training [10–16], where a large number of task-speciﬁc labels are needed.”
A Generalization of Transformer Networks to Graphs (2020, background): “The issue of positional embeddings has been explored in recent GNN works (Murphy et al. 2019; You, Ying, and Leskovec 2019; Srini-vasan and Ribeiro 2020; Dwivedi et al. 2020; Li et al. 2020) with a goal to learn both structural and positional features.”
Long Range Graph Benchmark (2022, background): “Thanks to the understanding of the limitations of message passing based GNNs [22] with respect to the 1-Weisfeiler Leman (WL) isomorphism test [60, 62, 46] and the information oversquashing [2], there has been several developments of GNN and Graph Transformer architectures which have strictly greate”
Structure-Aware Transformer for Graph Representation Learning (2022, methodology): “, 2019) and shortest path distances between pairs of nodes (Zhang et al., 2020; Li et al., 2020).”
Discovering Invariant Rationales for Graph Neural Networks (2022, methodology): “Speciﬁcally, we incorporate distance encoding measures (Li et al., 2020) like shortest-path distances as the extra node features for better structural representation learning.”
UniGNN: a Unified Framework for Graph and Hypergraph Neural Networks (2021, methodology): “, 2018a] and many provably more powerful GNNs mimicking higherorder-WL test have been presented [Morris et al., 2019a; Morris et al., 2019b; Li et al., 2020b].”
Do Transformers Really Perform Bad for Graph Representation? (2021, background): “For example, an attention-based aggregation is proposed in [9] where the node features, edge features, one-hot feature of the distance and ring flag feature are concatenated to calculate the attention probabilites; similar to [9], path-based attention is leveraged in [52] to model the influence betw”
Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting (2020, background): “[73] and [74] enhance the aggregation function with distance encodings (a strategy more relevant for vertex-level tasks) and graph eigenvectors respectively as alternative symmetry breaking mechanisms.”