Topology Only Graph Representation Learning

285 concepts208 papers1 proposal

Graph Neural Networks (GNNs) traditionally thrive on a dual diet: graph topology (the adjacency matrix detailing who connects to whom) and node attributes (text, vectors, or images associated with each node). In many practical applications, node attributes act as a vital crutch, smoothing over structural noise and guiding message passing.

But what happens when this crutch is completely removed? In domains ranging from anonymized social networks and router paths to massive function-call graphs like the MALNET database, we are faced with unattributed graphs—structures where only the raw connectivity is known.

Topology-only representation learning addresses this challenge. It answers a fundamental question: How can a model learn deep, generalized representations of nodes and graphs when it has absolutely no feature metadata to rely on?

The Core Intuition: Structure is Feature

Why should topology-only learning work at all? The fundamental intuition is that the graph structure itself implicitly encodes the missing features. When a graph is formed via node similarities or latent real-world interactions, the resulting topology becomes a geometric footprint of that hidden space.

This concept was mathematically formalized by Sato in Graph Neural Networks can Recover the Hidden Features Solely from the Graph Structure. The author proved that a properly designed GNN can reverse-engineer and reconstruct hidden node features (such as latent coordinates) using only the graph's adjacency matrix. While the exact coordinates might undergo rigid transformations like rotation or shifting, the relative structural distances and underlying similarities remain completely recoverable from the topology alone.

[Latent Space / Hidden Features] ──(Generates Graph)──> [Raw Topology (Adjacency Only)]
                                                               │
[Recovered Latent Representations] <──(Reverse Engineers)──────┘

Overcoming the Collapse: How Models Learn Without Attributes

If the structure contains the necessary information, the practical challenge shifts to extraction. Without node features to differentiate one node from another, standard GNNs risk treating symmetric or structurally similar nodes identically, leading to "representation collapse" where the model maps distinct nodes to identical vectors.

To extract meaningful patterns without falling into this trap, researchers employ three primary mechanisms:

1. Coordinate-Free Positional Encodings and Spectral Invariants

Without initial attributes, models require a non-trivial starting point to anchor nodes in space. Frasca et al. demonstrated in Understanding and Improving Laplacian Positional Encodings For Temporal GNNs that Laplacian-derived positional encodings serve as the primary mechanism for a model to distinguish topological positions in feature-poor environments. These mathematical signals replace raw features, allowing the network to map out a node's global and local neighborhood.

To ensure these structural properties generalize across entirely different graph domains, Ghose et al. introduced theoretically grounded spectral augmentations in Spectral Augmentations for Graph Contrastive Learning. By utilizing techniques like spectral cropping and frequency reordering during contrastive pre-training, the authors forced the model to focus on universal structural semantics rather than domain-specific feature spaces.

2. Imposing Geometric Orthogonality Constraints

When training an unsupervised model on purely structural data, a common failure mode is for the optimization objective to collapse to trivial solutions. Lin et al. proposed a geometric solution to this problem in Effective Clustering for Large Multi-Relational Graphs. By imposing a strict orthogonality constraint on the learned features, the authors prevented the optimization from collapsing. This mathematical boundary forces the model to distribute its representations across a latent space, capturing distinct community structures purely from multi-relational connectivity.

3. Injecting Global Structural Priors

Another strategy is to compensate for missing attributes by injecting explicit topological biases directly into the network architecture. Lutzeyer et al. showed in New Frontiers in Graph Autoencoders: Joint Community Detection and Link Prediction that incorporating global structural community priors (such as modularity-inspired loss functions) into a graph autoencoder allows it to achieve high clustering performance even on graphs completely lacking node features.

For graphs where connectivity patterns are complex or heterophilous (where different types of nodes connect), Zhu et al. introduced a learnable compatibility matrix in Graph Neural Networks with Heterophily. This layer allows the model to rely on learned structural dependencies between labels to infer node identities based solely on their position and neighbors within the graph topology, bypassing the need for high-quality node attributes to compensate for structural complexities.

When Less is More: Filtering Out Feature Noise

Surprisingly, completely ignoring node features can sometimes improve representation quality, even when features are available. In graph regions dominated by homophily (where similar nodes cluster together), individual node attributes can introduce high-frequency noise or cause feature-based interference between different node categories.

Xu et al. leveraged this insight in Divergent Paths: Separating Homophilic and Heterophilic Learning for Enhanced Graph-level Representations. The authors utilized featureless convolutions that focus exclusively on connectivity within node categories. By ignoring initial node features in these regions, the model relies entirely on the topological arrangement of nodes to define the representation, demonstrating that pure structure can provide a cleaner, more robust signal for learning than noisy attribute data.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_attribute_agnostic_graph_representation_45d7fd51,
  title = {attribute-agnostic graph representation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/attribute-agnostic-graph-representation/rdr_45d7fd517e5e4340b1e560faeb975ab2},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_attribute_agnostic_graph_representation_45d7fd51_v1,
  title = {attribute-agnostic graph representation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/attribute-agnostic-graph-representation/rdr_45d7fd517e5e4340b1e560faeb975ab2/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake