🤖 machine learning

Text-attributed Graph Condensation via Text Selection and Attribute Matching

The paper proposes TAGSAM, a novel graph condensation method for Text-Attributed Graphs that significantly improves training efficiency and accuracy by employing subgraph text selection to compress node descriptions and attribute similarity matching to stabilize topology compression, outperforming state-of-the-art baselines even at extreme compression ratios.

Original authors: Haowei Han, Yuxiang Wang, Guojia Wan, Hao Wang, Shanshan Feng, Hao Huang, Jiawei Jiang, Xiao Yan

Published 2026-06-03

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Haowei Han, Yuxiang Wang, Guojia Wan, Hao Wang, Shanshan Feng, Hao Huang, Jiawei Jiang, Xiao Yan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive library where every book (a node) is connected to other books it cites or mentions (edges), and every book has a long, detailed summary written on its back cover (text attributes). This is a Text-Attributed Graph (TAG).

To teach a computer to understand this library, you usually need to read every single book and study every connection. But if the library has millions of books, this takes forever and requires a supercomputer.

The authors of this paper, TAGSAM, propose a clever way to shrink this giant library down to a tiny, manageable "pocket guide" without losing the ability to teach the computer effectively. They call this process Graph Condensation.

Here is how they do it, using two main tricks:

1. The "Highlighter" Trick (Subgraph Text Selection)

The Problem:
Imagine trying to summarize a library by asking a robot to write new, shorter summaries from scratch. If the robot just writes random words, the summaries become gibberish. The computer can't read them because they aren't real sentences anymore.

The Solution:
Instead of writing new text, TAGSAM acts like a super-efficient editor with a highlighter.

Sampling: It picks small groups of connected books (subgraphs).
Scoring: It reads the summaries of these books and scores every sentence based on how much "unique information" it adds.
Selection: It grabs the best, most representative sentences and stitches them together to form a new, concise summary.
The Result: The new summary is made of real, readable sentences from the original books, not made-up gibberish. It's like creating a "Greatest Hits" playlist of text chunks that captures the essence of the whole group.

2. The "Stable Mirror" Trick (Attribute Similarity Matching)

The Problem:
Usually, when shrinking data, researchers try to make the small dataset mimic the learning journey of the big dataset. They force the computer to learn the small set in a way that matches the exact steps the computer took on the big set.

The Analogy: Imagine trying to teach a student by making them copy the exact hand movements of a master painter. But if the master painter's hand shakes a little (which happens often in complex math called "contrastive learning"), the student gets confused and ends up with a messy painting. This is called high variance, and it makes the training unstable.

The Solution:
Instead of copying the shaky hand movements (the training trajectory), TAGSAM looks at the final picture the master painter created.

The Analogy: It asks, "Does the student's painting have the same relationships between colors as the master's?"
How it works: It compares the "similarity map" (who looks like whom) of the big library with the small pocket guide. It adjusts the small guide until the relationships between the books match the big library perfectly.
The Result: This is much more stable. It doesn't matter if the teacher's hand shook; as long as the final relationships are correct, the student learns effectively.

Why is this a big deal?

The paper tested this method on five different real-world datasets (like citation networks and Amazon product reviews).

Performance: Even when they shrunk the dataset to just 1% of its original size, the computer trained on this tiny guide performed just as well (or better) as if it had trained on the whole library.
Speed: Because they only needed to train one "teacher" model (instead of many to capture different shaky hand movements), the process was much faster and cheaper.
Readability: Unlike other methods that turn text into unreadable code, TAGSAM keeps the text human-readable, which is crucial for tasks where the computer needs to understand the actual words later.

In short: TAGSAM is a method that creates a tiny, high-quality "cheat sheet" for a massive graph. It picks the best real sentences to keep and uses a stable mathematical mirror to ensure the connections between them are perfect, allowing computers to learn faster without getting confused.

Technical Summary: Text-attributed Graph Condensation via Text Selection and Attribute Matching

Problem Statement

Text-Attributed Graphs (TAGs) integrate graph topology with textual node descriptions, enabling powerful downstream tasks like zero-shot classification and article classification through the joint training of Graph Neural Networks (GNNs) and Language Models (LMs). However, this dual-modal training is computationally expensive, requiring significant memory and time, particularly on large-scale datasets.

While Dataset Condensation offers a solution by compressing large datasets into smaller, representative synthetic ones, existing methods fail to address TAGs effectively:

Traditional Graph Condensation (e.g., GCond): These methods typically compress only the graph modality, ignoring rich text information. Furthermore, they often rely on label supervision, which is incompatible with TAG scenarios where ground-truth labels are scarce or expensive to obtain.
Multi-modal Condensation (e.g., MTT-VL): Methods based on Matching Training Trajectories (MTT) attempt to compress both image and text. However, when applied to TAGs, they face two critical issues:
- Unreadable Text: MTT optimizes text in continuous embedding space via gradient descent. This produces unreadable embedding vectors that are incompatible with tokenizers and downstream language models.
- Unstable Training: In TAGs, teacher models are often trained via contrastive learning. The loss in contrastive learning depends on the entire batch, leading to high variance in training trajectories. This instability hinders the student model's ability to match the teacher's trajectory, resulting in sub-optimal convergence.

The core research question is: Is it possible to design a TAG condensation method for no-label scenarios that generates discrete, readable compressed text and achieves stable convergence?

Methodology: TAGSAM

The authors propose TAGSAM, a condensation framework comprising two key components: Subgraph Text Selection and Attribute Similarity Matching.

1. Subgraph Text Selection

Instead of optimizing continuous embeddings, TAGSAM selects and merges representative text chunks from the original discrete space to form concise, readable compressed texts.

Process:
1. Subgraph Sampling: Randomly sample $M$ subgraphs from the original graph using Breadth-First Search (BFS).
2. Text Chunking & Scoring: Divide text within each subgraph into chunks. Calculate a Representative Score (RS) for each chunk based on Chunk-wise Mutual Information (CMI). The RS maximizes information coverage of the subgraph while penalizing redundancy.
3. Selection & Merging: A greedy algorithm sequentially selects the top- $k$ chunks with the highest RS to form a compressed text $\hat{T}_i$ .
Theoretical Guarantee: The authors prove that this greedy selection approximates the optimal solution within a factor of $(1 - 1/e)$ .

2. Attribute Similarity Matching (ASM)

To compress the graph structure and node features, TAGSAM replaces the unstable MTT approach with Attribute Similarity Matching.

Mechanism: Instead of aligning full parameter update trajectories (which suffer from high variance), ASM aligns the attribute similarity matrices between the teacher and student models.
- The similarity matrix $S_M$ is computed as the product of graph embeddings and text embeddings for all node pairs.
- The matching loss minimizes the discrepancy between the student's similarity matrix and the teacher's, using a row-wise softmax before Binary Cross Entropy (sBCE) to ensure smoother gradients.
Theoretical Justification: The authors demonstrate that in contrastive learning, the optimal similarity between attributes corresponds to their Pointwise Mutual Information (PMI). Unlike full trajectories, which are sensitive to arbitrary rotation and scaling matrices in the encoder space, the similarity matrix is inherently stable and invariant to these transformations.
Efficiency: Unlike MTT, which requires training multiple teacher models (typically 15) to capture diverse trajectories, ASM requires only a single teacher model, significantly reducing computational cost.

Key Contributions

Problem Identification: The authors identify that traditional graph condensation is unsuitable for TAGs due to its neglect of text and label dependency, while existing multi-modal methods fail due to unreadable text outputs and training instability caused by high-variance contrastive trajectories.
Novel Framework (TAGSAM):
- Subgraph Text Selection: A method to compress text in the discrete space by selecting representative chunks via mutual information, ensuring the output remains readable and compatible with tokenizers.
- Attribute Similarity Matching: A robust condensation technique that aligns stable attribute similarity matrices rather than volatile training trajectories, improving convergence stability.
Theoretical Analysis: The paper provides theoretical proofs showing that the greedy text selection approximates the optimal solution and that attribute similarity serves as a stable estimate of PMI, justifying the robustness of the matching strategy.

Experimental Results

The authors evaluated TAGSAM on five datasets (Cora, Photo, Computer, Arxiv, Products) ranging from 2.7K to 2.4M nodes, comparing against six state-of-the-art baselines (Random, Herding, K-Center, GCond*, MTT-TAG, MTT-KNN).

Classification Accuracy: TAGSAM consistently outperformed all baselines. On average, it improved accuracy by 4.9% over the best-performing baseline (MTT-TAG). Notably, it achieved competitive accuracy even when condensing the dataset to just 1% of its original size.
Link Prediction: TAGSAM achieved significant AUC improvements (up to 4.1% over Random and 2.1% over MTT-TAG), indicating better retention of structural information.
Cross-Architecture Generalization: Models trained on TAGSAM-condensed data maintained higher accuracy when tested with different encoder architectures (e.g., GCN, SAGE, Cheby) compared to baselines.
Efficiency: While condensation incurs a one-time cost, TAGSAM significantly accelerates downstream hyperparameter searches. Due to the single-teacher requirement, TAGSAM is more scalable than MTT-based methods for large graphs.
Ablation Studies: Experiments confirmed that both the subgraph text selection and the attribute similarity matching components are essential, with the combination yielding superior performance over variants using random selection or trajectory matching.

Significance

The paper claims that TAGSAM makes efficient pre-training on large-scale Text-Attributed Graphs feasible. By addressing the specific challenges of discrete text compression and contrastive learning instability, TAGSAM enables the creation of highly compressed datasets that preserve the joint information necessary for effective zero-shot classification and other TAG tasks, without relying on expensive label supervision.