On Positional and Structural Node Features for Graph Neural Networks on Non-attributed Graphs

1 INTRODUCTION

• Graphs without node attributes pose a challenge for GNN tasks, including molecular-property prediction and subreddit prediction.The paper notes that missing user features in social networks introduce extra difficulties for subreddit prediction.Source: §1 · p. 1
• The paper identifies a gap in generic guidance for choosing artificial node features according to downstream task needs.Common initializations include degree-based, random, one-hot, position-based, and distance-based features.Source: §1 · p. 1
• Positional features help place globally near nodes A and B together, whereas structural features help place locally similar nodes A and C together.The paper studies these feature types across positional node classification, structural node classification, and graph classification; experiments on 10 datasets with 8 common artificial features validate task-specific fit.Source: §1 · p. 2, Figure 1 · p. 2
• Positional features are more suitable for positional node classification, while structural features benefit structural node classification and graph classification.With appropriately designed artificial features, GNN performance can surpass that with real features in some cases.Source: §1 · p. 2

2 TWO TYPES OF ARTIFICIAL NODE FEATURES

• Artificial node features are grouped into positional and structural families according to the information they help GNNs capture.The paper frames the distinction around relative positions versus structural information.Source: §2 · p. 2, §2.1 · p. 2, §2.2 · p. 2

2.1 Positional Node Features

• Positional features encode relative node positions; examples include random identity vectors, one-hot identities, top-k normalized-adjacency eigenvectors, and DeepWalk vectors.DeepWalk walks longer than two steps can capture higher-order positional information.Source: §2.1 · p. 2

2.2 Structural Node Features

• Structural features represent node degree and neighborhood patterns, with shared constant, one-hot degree, and extended PageRank features among the examples.The paper describes PageRank as generalized higher-order node-degree information and distinguishes structural roles from graph position.Source: §2.2 · p. 2

2.3 Byproduct: New SOTA for Structural Node Classification

• Degree+ buckets node degrees into ranges and maps each range to a unique one-hot class, improving on degree features for sparse, skewed degree distributions.The paper presents degree+ as a novel initialization method for structural node classification.Source: §2.3 · p. 3

3.1 Basic Settings

• GraphSAGE with mean and sum aggregators evaluates the artificial initializations across tasks; graph-level experiments vary feature sizes from 100 to 500 and average five runs.The study uses standard data splits and grid-searches learning rate, epochs, and neighborhood sample size.Source: §3.1 · p. 3

3.2 Positional Node Classification

• Positional features usually outperform structural features for positional node classification, especially with mean aggregation; eigen and DeepWalk perform best across the three datasets.Mean aggregation filters out neighborhood-size influence, while shared features yield identical node embeddings and consistently poor results; random and one-hot perform comparably.Source: §3.2 · p. 3, Table 1 · p. 3

3.3 Structural Node Classification

• Structural features usually outperform positional ones for structural node classification, and degree+ reaches a new state-of-the-art by bucketing degree values to alleviate sparsity and skewness.Sum aggregation outperforms mean aggregation because it captures neighbor counts; the authors conjecture that PageRank’s deterioration can arise from over-smoothing.Source: §3.3 · p. 4, Table 2 · p. 4

3.4 Graph Classification

• Structural features perform best across the four graph-classification datasets, although no single feature consistently wins; degree and PageRank with sum aggregation even surpass real features on MUTAG and PROTEINS, respectively.Sum aggregation outperforms mean aggregation, and PageRank performs best in most structural-feature cases.Source: §3.4 · p. 4, Table 3 · p. 4

• Positional features are more suitable for positional node classification, while structural features benefit structural node classification and graph classification.The study presents this task-dependent distinction as a practical guideline for choosing artificial node features on non-attributed graphs.Source: §4 · p. 4