Graph Neural Networks (GNNs) traditionally rely on two distinct pillars: node features ($X$) and explicit topological edges ($A$). To learn representations, GNNs pass messages along these edges, iteratively aggregating neighborhood information. While intuitive, this explicit reliance on graph structure introduces massive computational overhead, scalability bottlenecks, and storage challenges.
However, a powerful counter-intuitive realization is reshaping the field: explicit edge structures are often completely unnecessary if node features are sufficiently enriched with structural information.
This insight underpins a new paradigm known as structure-free graph condensation and feature-centric graph learning. Instead of preserving or learning complex topologies, researchers are finding that a graph's relational context can be baked directly into independent node representations, allowing simple, edge-free models to match or exceed the performance of heavy GNN architectures.
Condensing Graphs by Eliminating Edges
Graph condensation aims to shrink massive real-world graphs into tiny synthetic proxies (often less than 0.1% of the original size) to enable ultra-fast GNN training. Early frameworks like GCOND, introduced by Wei Jin et al. in Graph Condensation for Graph Neural Networks, demonstrated that during the optimization process, structural information can be embedded directly into node features. This allows a set of independent synthetic nodes to represent the relational properties of a complex graph without needing explicit edge definitions.
In traditional condensation, co-optimizing features and edges creates a highly complex, computationally expensive trajectory-matching problem. To bypass this, the "Precompute-Then-Adapt" (GCPA) framework proposed by Yuan Li et al. in Adapting Precomputed Features for Efficient Graph Condensation and A Precompute-Then-Adapt Approach for Efficient Graph Condensation completely eliminates explicit edge optimization.
Traditional Condensation:
[Original Graph] ---> Optimize (Features X + Edges A) ---> [Synthetic Graph with Edges] (Slow)
Structure-Free Condensation:
[Original Graph] ---> Neighborhood Aggregation ---> Precomputed Features ---> [Independent Synthetic Nodes] (Fast)
GCPA generates synthetic datasets where nodes lack explicit edges entirely, relying instead on pre-encoded structural features enriched via neighborhood aggregation. By removing the need to model synthetic topologies, this structure-free approach simplifies the condensation problem and speeds up the process by up to 2,455 times while maintaining high classification accuracy.
Comprehensive benchmarking by Ruihong Qiu et al. in GCondenser: Benchmarking Graph Condensation and a global survey by Xinyi Gao et al. in Graph Condensation: A Survey confirm this phenomenon. Synthetic graphs consisting solely of node features without explicit edge structures frequently rival or exceed the performance of models with complex synthetic topologies. This proves that node features alone can encapsulate the essential information required for training downstream models.
Why It Works: The Power of Pre-Enriched Representations
Why can a collection of isolated nodes perform as well as a fully connected network? The answer lies in the quality of the initial feature space. If a node's feature vector already encodes its local neighborhood, its semantic context, and its position in the network, downstream classifiers do not need to perform message-passing.
Several lines of research validate this intuition across different domains:
1. Self-Supervised Neighborhood Prediction
Eli Chien et al. developed GIANT in Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Prediction, which reformulates neighbor prediction as an extreme multi-label classification problem to fine-tune language models. The authors show that high-quality, structurally-informed node features allow simple Multi-Layer Perceptrons (MLPs) to achieve competitive performance, proving the bottleneck is often feature quality rather than message-passing complexity. Similarly, So Hasegawa et al. show in Improving Predicate Representation in Scene Graph Generation by Self-Supervised Learning that self-supervised relational encoders can replace message-passing modules entirely, yielding simpler, 6x faster classifiers.
2. Deep Semantic Modeling on Textual Graphs
In text-attributed graphs, Keyu Duan et al. demonstrate in SimTeG: A Frustratingly Simple Approach Improves Textual Graph Learning that a simple two-stage pipeline—fine-tuning a language model on the downstream task and feeding its embeddings into a standard GNN—reaches state-of-the-art results because the embeddings already capture deep semantic information.
Large-scale evaluations by Arpandeep Khatua et al. in IGB: Addressing The Gaps In Labeling, Features, Heterogeneity, and Size of Public Graph Datasets for Deep Learning Research and Hao Yan et al. in A Comprehensive Study on Text-attributed Graphs: Benchmarking and Rethinking confirm that enhancing the language model for feature generation influences model accuracy far more significantly than the underlying graph topology itself.
3. Exposing the Illusion of Structure Learning
Perhaps the most striking evidence comes from Yilun Zheng et al. in Rethinking Structure Learning For Graph Neural Networks. The authors re-evaluated Graph Structure Learning (GSL) methods designed to optimize noisy graphs and discovered that GSL's performance gains are primarily driven by the quality of the initial node embeddings (via self-training) rather than the learned edges. When given identical high-quality features, simple feed-forward networks match the performance of complex graph-based models.
Broad Applications: Beyond Standard GNNs
This feature-centric realization extends well beyond node classification and graph condensation into diverse domains:
- Brain Network Analysis: Instead of constructing static brain networks from fMRI data using hand-crafted formulas, Liang Yang et al. show in Brain Networks Should Be Learned, Not Constructed that learning high-quality brain representations allows simple MLPs to outperform complex graph transformers.
- Recommender Systems: In semantically-rich environments, Michael Färber et al. demonstrate in Bridging RDF Knowledge Graphs with Graph Neural Networks for Semantically-Rich Recommender Systems that dense semantic and literal features from RDF knowledge graphs reduce the necessity for complex heterogeneous message-passing architectures.
- Tabular Data Transformations: Even when converting traditional tabular patient data into knowledge graphs, Wasif Khan et al. show in Infant Low Birth Weight Prediction Using Graph Embedding Features that the choice of graph embedding feature engineering matters far more than the specific downstream classifier.
Conclusion
Structure-free graph condensation works because graph topology is not a rigid architectural requirement; it is an information source. By shifting the burden of structural aggregation from the model architecture (edges and message passing) to the data representation (enriched node features), we can compress massive graphs into independent node sets, replace heavy GNNs with lightweight MLPs, and achieve massive gains in training speed and efficiency without sacrificing predictive power.
Key Foundational Work
Graph Condensation for Graph Neural Networks (2022) — contributed 2 concept elements to this direction.
Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Prediction (2022) — contributed 1 concept elements to this direction.
SimTeG: A Frustratingly Simple Approach Improves Textual Graph Learning (2023) — contributed 1 concept elements to this direction.