On the Equivalence between Positional Node Embeddings and Structural Graph Representations

Abstract

This work provides the first unifying theoretical framework for node (positional) embeddings and structural graph representations, bridging methods like matrix factorization and graph neural networks. Using invariant theory, we show that the relationship between structural representations and node embeddings is analogous to that of a distribution and its samples. We prove that all tasks that can be performed by node embeddings can also be performed by structural representations and vice-versa. We also show that the concept of transductive and inductive learning is unrelated to node embeddings and graph representations, clearing another source of confusion in the literature. Finally, we introduce new practical guidelines to generating and using node embeddings, which fixes significant shortcomings of standard operating procedures used today.

This version corrects some typos in the definition of Σ, it should be Σ_n. Code available at https://github.com/PurdueMINDS/Equivalence

Cited by in corpus (13)

• E(n) Equivariant Graph Neural Networks
• Machine Learning on Graphs: A Model and Comprehensive Taxonomy
• GraphSAIL: Graph Structure Aware Incremental Learning for Recommender Systems
• Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks
• Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning
• GIN-SD: Source Detection in Graphs with Incomplete Nodes via Positional Encoding and Attentive Fusion
• Graph Neural Networks with Learnable Structural and Positional Representations
• Equivariant Subgraph Aggregation Networks
• On the Equivalence Between Temporal and Static Graph Representations for Observational Predictions
• Principled Hyperedge Prediction with Structural Spectral Features and Neural Networks
• On Positional and Structural Node Features for Graph Neural Networks on Non-attributed Graphs
• Unsupervised Joint $k$-node Graph Representations with Compositional Energy-Based Models
• Connecting Graph Convolutional Networks and Graph-Regularized PCA