Multi-View Graph Embedding Using Randomized Shortest Paths

Anuththari Gamage, Brian Rappaport, Shuchin Aeron, Xiaozhe HuarXiv 2018 · OpenReview

Abstract

Real-world data sets often provide multiple types of information about the same set of entities. This data is well represented by multi-view graphs, which consist of several distinct sets of edges over the same nodes. These can be used to analyze how entities interact from different viewpoints. Combining multiple views improves the quality of inferences drawn from the underlying data, which has increased interest in developing efficient multi-view graph embedding methods. We propose an algorithm, C-RSP, that generates a common (C) embedding of a multi-view graph using Randomized Shortest Paths (RSP). This algorithm generates a dissimilarity measure between nodes by minimizing the expected cost of a random walk between any two nodes across all views of a multi-view graph, in doing so encoding both the local and global structure of the graph. We test C-RSP on both real and synthetic data and show that it outperforms benchmark algorithms at embedding and clustering tasks while remaining computationally efficient.

Introduction

In many real-world scenarios, we encounter "multi-view" graphs—datasets where the same set of entities share multiple types of relationships. For instance, a group of social media users might interact via follows, mentions, and retweets. To analyze such complex data, researchers typically employ graph embeddings to map nodes into a Euclidean space.

However, traditional distance measures often fall short. Shortest Path (geodesic) distance focuses solely on the optimal route, ignoring connection density. Conversely, Commute Time distance (based on random walks) excels at identifying clusters but tends to "degenerate" in large graphs, losing global structure. This paper introduces C-RSP (Common Randomized Shortest Paths), a novel algorithm that bridges this gap by providing a tunable dissimilarity measure that captures both local clusters and global geometry across multiple data views.

Methodology: The C-RSP Framework

C-RSP builds upon the Randomized Shortest Paths (RSP) framework. It introduces a parameter $\beta$ that controls the trade-off between purely optimal shortest paths ($\beta \to \infty$) and purely random walks ($\beta \to 0$).

The Innovation of Common RSP

Unlike methods that embed views independently and then combine them, C-RSP performs "early fusion." It solves a constrained optimization problem to find a probability distribution that minimizes the expected cost of paths across all views simultaneously. The process involves:

  1. Aggregating Views: Combining transition probabilities using a geometric mean and summing edge costs.
  2. Dissimilarity Matrix: Computing a closed-form dissimilarity matrix ($\Delta^{CRSP}$) via efficient matrix inversions.
  3. Downstream Tasks: Using the matrix with Multidimensional Scaling (MDS) for visualization or Spectral Clustering for node grouping.

This approach is mathematically robust and avoids the heavy iterative optimization required by many competing multi-view methods.

Experimental Setup

The authors evaluated C-RSP against state-of-the-art benchmarks (SC-ML, CSC, MultiNMF) using several datasets:

  • Synthetic Swiss Roll: A 3D manifold projected into multiple 2D views to test geometric reconstruction.
  • Stochastic Block Model (SBM): Generative graphs used to assess clustering accuracy under noise.
  • Real-World Data: News stories (3Sources), handwritten digits (UCI Digits), and political social networks (Multi-view Twitter).
The 3D Swiss roll ground truth used for synthetic testing.

Key Results and Discussion

C-RSP demonstrates significant advantages in visualization, accuracy, and efficiency.

Superior Geometric Reconstruction

On the Swiss Roll benchmark, C-RSP was the only algorithm capable of accurately recovering the original 3D spiral shape and its internal "holes." Benchmark algorithms like SC-ML and MultiNMF failed to preserve the global geometry, often collapsing the manifold.

Comparison of embeddings for the Swiss roll dataset. C-RSP (a) successfully recovers the global 3D structure compared to benchmarks (b-d).

Clustering and Robustness

C-RSP consistently outperformed benchmarks on the Twitter and 3Sources datasets in terms of Correct Classification Rate (CCR) and Normalized Mutual Information (NMI). Furthermore, in SBM simulations, C-RSP maintained high accuracy even as graphs became sparse, whereas benchmark performance degraded significantly.

Computational Efficiency

By relying on matrix inversion rather than complex tensor factorizations, C-RSP is roughly 4x faster than Co-regularized Spectral Clustering (CSC) on smaller datasets and scales better than MultiNMF on larger ones.

Limitations and Future Outlook

While C-RSP is highly effective, its performance is sensitive to the choice of $\beta$. Future work aims to develop automated tuning methods to select the optimal parameter for a given data scale. Additionally, while matrix inversion is efficient, it may become a bottleneck for graphs with millions of nodes, suggesting a need for faster approximation techniques.

Summary updated

Abstract

Real-world data sets often provide multiple types of information about the same set of entities. This data is well represented by multi-view graphs, which consist of several distinct sets of edges over the same nodes. These can be used to analyze how entities interact from different viewpoints. Combining multiple views improves the quality of inferences drawn from the underlying data, which has increased interest in developing efficient multi-view graph embedding methods. We propose an algorithm, C-RSP, that generates a common (C) embedding of a multi-view graph using Randomized Shortest Paths (RSP). This algorithm generates a dissimilarity measure between nodes by minimizing the expected cost of a random walk between any two nodes across all views of a multi-view graph, in doing so encoding both the local and global structure of the graph. We test C-RSP on both real and synthetic data and show that it outperforms benchmark algorithms at embedding and clustering tasks while remaining computationally efficient.
BibTeX
@misc{gamage2018multi,
  author = {Anuththari Gamage and Brian Rappaport and Shuchin Aeron and Xiaozhe Hu},
  title = {{Multi-View Graph Embedding Using Randomized Shortest Paths}},
  year = {2018},
  eprint = {1808.06560},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1808.06560},
}
Figure