Source-linked AI summary
Effective Graph and Rank-based Contextual Embeddings for Textual and Multimedia Data
Thiago César Castilho Almeida, Gustavo Rosseto Letício, Lucas Pascotti Valem, André Freitas, Daniel Carlos Guimarães Pedronette
TL;DR
Graph methods reduce structural data to manageable vectors but often lack interpretable dimensions and require costly computation. GRaCE addresses this gap with a fully unsupervised, rank-based framework for selecting representative nodes and generating embeddings. Across textual and multimedia datasets, it performs strongly in retrieval, classification, and clustering, often outperforming Original Features and providing an alternative to RaDE.
Problem
Graph-based methods can be computationally expensive, while conventional embeddings often lack interpretable dimensions; RaDE’s representative selection was not fully evaluated across tasks and classes.
Method
GRaCE uses robust rank-based measures to select representative nodes and create interpretable embeddings, with effectiveness estimated without labeled data.
Results
GRaCE performs strongly across retrieval, classification, and clustering on textual and multimedia datasets, often outperforming Original Features and serving as an alternative to RaDE.
Takeaways & Limitations
GRaCE is a versatile fully unsupervised option for representative subset selection and textual and multimedia applications.
Abstract
from arXiv · showhide
In a data-driven world, efficiently organizing and mapping relationships between objects is crucial. Graphs are powerful tools for modeling these connections, being widely used in social networks, telecommunications, and biology. However, graph-based methods often face high computational costs, particularly in memory and space usage. To address this, graph embedding techniques, also referred to as Network Representation Learning, encode graph information into lower-dimensional representations while preserving structural aspects. Traditional methods, however, lack interpretable dimensions. RaDE (Rank Diffusion Embedding) introduces a new approach using rank-based information, with a key step being the selection of a representative subset of nodes to provide interpretability for its dimensions and improve retrieval tasks. Despite its potential, RaDE's original proposal did not fully explore the effectiveness of representative subset selection across different classes or evaluate embeddings in tasks like classification and clustering. Inspired by RaDE, this work introduces GRaCE (Graph and Rank-based Contextual Embeddings), a fully unsupervised framework that generates interpretable embeddings by leveraging robust rank-based measures for representative subset selection and node embedding. GRaCE surpasses RaDE and Original Features across diverse datasets, including textual and image collections, excelling in retrieval, classification, and clustering tasks, considering state-of-the-art Transformer models as feature descriptors and Graph Convolutional Networks models in classification tasks.
I. INTRODUCTION
Graph methods organize relationships and support machine-learning tasks, but their computational costs and opaque dimensions motivate interpretable, efficient embeddings. GRaCE extends RaDE by evaluating representative selection and embedding performance across retrieval, classification, and clustering.
- Graph-based operations support classification, link prediction, clustering, and visualization but often incur high time and space costs.
- Graph embeddings encode graph structure in low-dimensional vectors to reduce computational costs while supporting downstream machine-learning tasks.
- Classical and deep graph embeddings are often black boxes because their dimensions lack explicit semantic meaning and their optimization is opaque.
- RaDE builds semantic dimensions through rank-based similarity, representative-node selection, and diffusion-based affinities.
- GRaCE introduces robust rank-based representative selection, evaluates representativeness, and assesses RaDE and GRaCE embeddings in retrieval, classification, and clustering.Its measures include JaccardMax, Reciprocal, Reciprocal Density, and Accumulated JaccardMax.
II. FORMAL DEFINITION
The paper represents a collection as a graph whose nodes are elements and whose edges encode connections, optionally weighted through an adjacency matrix.
- A collection C = {e1, e2, ..., en} is represented by a graph G(V, E), with each element ej corresponding to a node.
- The edge set E records connections between elements, and edge weights are represented in an adjacency matrix S.
- The weight of an edge between ei and ej is denoted si,j.
1) Graph Embedding:
GRaCE constructs rank-aware graph embeddings through a sequence of graph construction, representative selection, and node representation steps for textual and multimedia data.
- 1) Graph Embedding:: Node embedding maps graph nodes to a lower-dimensional space while preserving proximity between structurally close nodes.The mapping is defined as f: V → R^d, where d ≪ |V|.
- 1) Graph Embedding:: For multimedia data, similarity graphs are built from extracted feature vectors and distances between elements.
- 1) Graph Embedding:: GRaCE identifies representative nodes and constructs vector representations that preserve structural properties through three main steps.
- 1) Graph Embedding:: The framework transforms input data into a k-nearest-neighbors graph that captures local relationships and structural patterns.
- 1) Graph Embedding:: Representative nodes encode information from the graph while prioritizing effectiveness and reducing redundancy.
- 1) Graph Embedding:: Each node receives a new vector based on its similarity to the selected representative nodes, supporting clustering, classification, and visualization.
A. Rank-based Similarity Graph Construction
GRaCE constructs a similarity graph and selects effective, non-redundant representatives using rank correlation and unsupervised effectiveness estimates based on local ranked-list context.
- A. Rank-based Similarity Graph Construction: The framework builds a kNN graph with weighted edges or feature-based distances to capture local data structure.
- A. Rank-based Similarity Graph Construction: Representative selection prioritizes highly effective elements and penalizes correlation with previously selected nodes to reduce redundancy.
- A. Rank-based Similarity Graph Construction: Reciprocal and JaccardMax compare ranked lists using top-k neighborhood information, with rank weighting or maximum Jaccard similarity.
- A. Rank-based Similarity Graph Construction: Unsupervised effectiveness estimation evaluates ranked-list quality and distinguishes good from bad queries without labels.
- A. Rank-based Similarity Graph Construction: Reciprocal Neighborhood Density estimates effectiveness by counting reciprocal neighbors within a query’s ranked list.
- A. Rank-based Similarity Graph Construction: Accumulated JaccardMax averages rank-list similarity between a query and the rankings of its k-nearest neighbors.
C. Node Embedding
GRaCE creates each node’s low-dimensional representation by comparing it with selected representative nodes using rank correlation between ranked neighbor lists.
- GRaCE represents each element by its similarities to the selected representative nodes.The resulting representation is low-dimensional and semantically meaningful.
- Unlike RaDE’s diffusion-matrix affinity, GRaCE defines node similarity through rank correlation between nodes’ ranked lists.
IV. EXPERIMENTAL EVALUATION
The experimental evaluation covers four tasks, with separate subsections addressing representative selection, retrieval, classification, and clustering.
- GRaCE is evaluated on representative subset selection, retrieval, classification, and clustering.
- The evaluation section also describes datasets, feature descriptors, experimental protocols, measures, algorithms, and parameter settings.
A. Datasets and Representations
Experiments use image and text datasets, Transformer-based feature descriptors, multiple evaluation tasks, and fixed protocols for measuring representative selection and downstream performance.
- A. Datasets and Representations: The evaluation uses Flowers, Corel5k, BBCNews, and WOS-5736 across image and text modalities.The datasets contain 1,360 images, 5,000 images, 2,225 articles, and 5,736 abstracts, respectively.
- A. Datasets and Representations: Image representations use ViT-B16, Swin-Tf, and self-supervised DINOv2-B14 feature descriptors.
- A. Datasets and Representations: Coverage measures the percentage of dataset classes represented by the selected subset, while Clustering Accuracy assigns elements according to their most similar representative node.
- A. Datasets and Representations: Retrieval uses Precision at depths 2, 4, and 16 plus MAP at depth 1000; classification uses Accuracy and clustering uses NMI.
- A. Datasets and Representations: All generated embeddings have 128 dimensions, and RaDE uses t = 2 to align with the baseline configuration.
- A. Datasets and Representations: RaDE’s L and GRaCE’s k control similarity-graph construction and rank-based measures, with k = 200 for BBCNews and WOS-5736.
- A. Datasets and Representations: Classification averages Accuracy across five rounds of 10-fold cross-validation, using one fold for training and the others for testing.
- A. Datasets and Representations: Clustering evaluates KMeans, Affinity Propagation, and Agglomerative Hierarchical Clustering with dataset-specific class-count settings.
C. Representative Nodes Selection Task
GRaCE consistently outperforms RaDE in representative subset effectiveness, with JaccardMax variants producing particularly strong Clustering Accuracy results across image and text datasets.
- GRaCE achieves the best representative-subset evaluation values in at least two of three feature descriptors across every dataset.
- Both RaDE and GRaCE maintain consistently high Coverage and encompass the majority of dataset classes in every scenario.
- With DINOv2-B14, GRaCE using JaccardMax reaches Clustering Accuracy of 1.0 on Flowers and 0.9340 on Corel5k.
- On WOS-5736, JaccardMax-based GRaCE surpasses RaDE’s Clustering Accuracy by roughly 3% across all feature descriptors.
D. Retrieval Tasks
GRaCE generally outperformed RaDE and Original Features in retrieval, with its strongest advantage appearing at deeper ranking levels. However, Original Features often remained strongest at the shallowest precision depths.
- GRaCE achieved the highest MAP scores in 9 out of 12 retrieval cases.The improvement was especially evident on BBCNews, where MAP increased from around 50% to over 70% across all descriptors.
- Interpretable embeddings generally performed better as retrieval depth increased.This pattern applied to both RaDE and GRaCE across the evaluated retrieval tasks.
- Original Features often achieved the best results at shallow depths, particularly for P@2 and P@4.They remained competitive across several datasets and feature descriptors despite GRaCE’s stronger MAP results.
- The retrieval evaluation compared GRaCE and RaDE with Original Features across all datasets.The results are reported in Table II.
F. Clustering Tasks
Graph embeddings generally improved clustering relative to Original Features, with the largest gains appearing for HDBSCAN and textual data. GRaCE was particularly strong on textual datasets, while RaDE excelled on image datasets.
- GRaCE improved BBCNews NMI from 0.0521 with Original Features to 0.5299 using DistilRoBERTa features and HDBSCAN.HDBSCAN improvements over Original Features were observed in all evaluated cases.
- Interpretable embeddings outperformed Original Features in every HDBSCAN case.Graph embedding methods generally improved clustering results compared with Original Features.
- GRaCE achieved an NMI score of 1 on Flowers with DINOv2-B14 features and Agglomerative Hierarchical Clustering.Agglomerative Hierarchical Clustering was the clustering algorithm least affected by graph embeddings overall.
- Affinity Propagation and KMeans benefited from graph embeddings, especially on textual datasets.The methods also showed improvements on image collections.
- RaDE excelled on image datasets, whereas GRaCE stood out on textual data.This summarizes the reported overall clustering pattern across the evaluated algorithms and datasets.
V. CONCLUSION
GRaCE performs strongly across subset selection, retrieval, classification, and clustering, often outperforming Original Features and matching or surpassing RaDE. Its results support fully unsupervised graph embeddings for textual and multimedia applications, while scalability and comparisons with other graph embeddings remain future work.
- GRaCE was evaluated across subset selection, retrieval, classification, and clustering using four datasets and six state-of-the-art feature descriptors.The evaluation included Transformer-based descriptors for textual and image datasets.
- GRaCE matches or surpasses RaDE in many subset-selection cases, while RaDE achieves strong Clustering Accuracy and high Coverage across most evaluated cases.
- GRaCE maintains retrieval performance similar to RaDE and improves performance at deeper ranking levels, but shows slightly reduced precision at shallower depths.
- Both RaDE and GRaCE significantly improve classification results in some settings, particularly textual datasets and KNN classification, although Original Features remain competitive in certain cases.
- Graph embeddings significantly enhance NMI scores across clustering algorithms and datasets; RaDE is strong on image data, whereas GRaCE excels on textual data.
- GRaCE emerges as a robust option for subset selection and textual and multimedia applications within a fully unsupervised framework.