mlsanityData to 7 Oct 2026

Graph Neural Networks can Recover the Hidden Features Solely from the Graph Structure

arXiv 2301.10956 ↗First posted 26 Jan 2023cs.LG cs.SIcited by 4

Not on the map. Why?

Abstract (arXiv)

Graph Neural Networks (GNNs) are popular models for graph learning problems. GNNs show strong empirical performance in many practical tasks. However, the theoretical properties have not been completely elucidated. In this paper, we investigate whether GNNs can exploit the graph structure from the perspective of the expressive power of GNNs. In our analysis, we consider graph generation processes that are controlled by hidden (or latent) node features, which contain all information about the graph structure. A typical example of this framework is kNN graphs constructed from the hidden features. In our main results, we show that GNNs can recover the hidden node features from the input graph alone, even when all node features, including the hidden features themselves and any indirect hints, are unavailable. GNNs can further use the recovered node features for downstream tasks. These results show that GNNs can fully exploit the graph structure by themselves, and in effect, GNNs can use both the hidden and explicit node features for downstream tasks. In the experiments, we confirm the validity of our results by showing that GNNs can accurately recover the hidden features using a GNN architecture built based on our theoretical analysis.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 46 of its 74 references that are in the map. First posted on arXiv 26 Jan 2023.

Builds on

46 of 74 references.

References · 46

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2017Graph Attention Networkscited by 8,854
  4. 2017Inductive Representation Learning on Large Graphscited by 6,284
  5. 2018How Powerful are Graph Neural Networks?cited by 4,355
  6. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  7. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  8. 2019Simplifying Graph Convolutional Networkscited by 1,470
  9. 2020LightGCN: Simplifying and Powering Graph Convolution Network for Recommendationcited by 1,134
  10. 2018Deep Graph Infomaxcited by 1,101
  11. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
  12. 2018Pitfalls of Graph Neural Network Evaluationcited by 994
34 more
  1. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 987
  2. 2016Revisiting Semi-Supervised Learning with Graph Embeddingscited by 970
  3. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  4. 2020Simple and Deep Graph Convolutional Networkscited by 857
  5. 2020Learning Mesh-Based Simulation with Graph Networkscited by 840
  6. 2018Link Prediction Based on Graph Neural Networkscited by 829
  7. 2019Graph Neural Networks for Social Recommendationcited by 711
  8. 2018FastGCN: Fast Learning with Graph Convolutional Networks via Importance Samplingcited by 583
  9. 2019Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological Viewcited by 544
  10. 2020GCC: Graph Contrastive Coding for Graph Neural Network Pre-Trainingcited by 461
  11. 2019Provably Powerful Graph Networkscited by 385
  12. 2018Invariant and Equivariant Graph Networkscited by 339
  13. 2020Discovering Symbolic Models from Deep Learning with Inductive Biasescited by 335
  14. 2020GPT-GNN: Generative Pre-Training of Graph Neural Networkscited by 302
  15. 2019Revisiting Graph Neural Networks: All We Have is Low-Pass Filterscited by 260
  16. 2019A Fair Comparison of Graph Neural Networks for Graph Classificationcited by 244
  17. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  18. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  19. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  20. 2022Vision GNN: An Image is Worth Graph of Nodescited by 185
  21. 2020Random Features Strengthen Graph Neural Networkscited by 184
  22. 2019Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networkscited by 177
  23. 2019What Can Neural Networks Reason About?cited by 155
  24. 2019Relational Pooling for Graph Representationscited by 150
  25. 2020When Does Self-Supervision Help Graph Convolutional Networks?cited by 121
  26. 2020AM-GCN: Adaptive Multi-channel Graph Convolutional Networkscited by 121
  27. 2020A Survey on The Expressive Power of Graph Neural Networkscited by 111
  28. 2019Approximation Ratios of Graph Neural Networks for Combinatorial Problemscited by 68
  29. 2021Structure-aware Interactive Graph Neural Networks for the Prediction of Protein-Ligand Binding Affinitycited by 60
  30. 2022Theory of Graph Neural Networks: Representation and Learningcited by 60
  31. 2019Understanding the Representation Power of Graph Neural Networks in Learning Graph Topologycited by 52
  32. 2022Towards Principled User-side Recommender Systemscited by 7
  33. 2014Metric recovery from directed unweighted graphscited by 4
  34. 2019Constant Time Graph Neural Networkscited by 4

Built on by

Cited by year

Citing papers per year: 2024: 3; 2025: 1.

4 papers.

  1. 2024Training-free Graph Neural Networks and the Power of Labels as Featurescited by 5
  2. 2024TEDDY: Trimming Edges with Degree-based Discrimination strategYcited by 4
  3. 2024GTAGCN: Generalized Topology Adaptive Graph Convolutional Networkscited by 1
  4. 2025How do Probabilistic Graphical Models and Graph Neural Networks Look at Network Data?cited by 0