rec_coarsen: Randomized Edge Contraction (REC) Graph Coarsening

In bbuchsbaum/graphweights: Constructing Adjacency Matrices Based on Spatial and Feature Similarity

Randomized Edge Contraction (REC) Graph Coarsening

Description

Implements the randomized edge contraction (REC) coarsening method as described in the paper:

* A. Loukas and P. Vandergheynst, *"Spectrally Approximating Large Graphs with Smaller Graphs,"* Proceedings of the 35th International Conference on Machine Learning (ICML), 2018.

Given a weighted graph represented by a sparse adjacency matrix, this function attempts to coarsen the graph by contracting edges at random according to a given edge potential. The result is a reduced (coarsened) graph that preserves the spectrum of the original Laplacian up to certain guarantees detailed in the paper.

Usage

rec_coarsen(
  W,
  T = 100,
  phi = NULL,
  seed = NULL,
  deterministic_first_edge = FALSE,
  verbose = FALSE,
  use_cpp = FALSE,
  allow_multiple_passes = FALSE
)

Arguments

W	A sparse N \times N adjacency matrix of the original graph. Must be symmetric and non-negative.
T	The number of iterations for randomized edge contraction. A larger T increases the chance of forming a large matching.
phi	A vector or matrix of the same dimension as W (or length = number of edges) that encodes the edge potentials \phi_{ij}. If NULL, defaults to heavy-edge potentials \phi_{ij} = w_{ij}.
seed	An integer seed for reproducibility of random sampling.
deterministic_first_edge	Logical, if TRUE selects the first edge in the candidate set for the first iteration. This is primarily for testing purposes. Default is FALSE.
verbose	Logical, if TRUE prints debug information during the coarsening process.
use_cpp	Logical. If TRUE, uses the C++ implementation for faster computation. Default is FALSE.
allow_multiple_passes	Logical. If TRUE, allows multiple passes of coarsening. Default is FALSE.

Value

A list with elements:

C

The n \times N coarsening matrix, where n is the number of coarse vertices.

W_c

The n \times n adjacency matrix of the coarsened graph.

L_c

The n \times n coarsened Laplacian matrix L_c = C L C^\top.

mapping

An integer vector of length N indicating the coarse vertex each original vertex belongs to.

Method

The coarsening construction follows the framework detailed in Section 2 and Algorithm 1 of the paper. The main steps are:

1. **Set-up**: Given a graph G=(\mathcal{V},\mathcal{E},W) with N=|\mathcal{V}|, we form its Laplacian L defined in Equation (1) of the paper.

2. **Edge Potentials**: Assign a potential \phi_{ij} to each edge e_{ij} \in \mathcal{E}. (See Section 3 of the paper). A common choice is the heavy-edge potential \phi_{ij}=w_{ij}.

3. **Randomized Edge Contraction (REC)**: We perform up to T iterations (see Algorithm 1 in the paper): - At each iteration, from the set of candidate edges \mathcal{C}, select one edge e_{ij} with probability proportional to its potential \phi_{ij}. - Contract e_{ij} (merge vertices v_i and v_j) to form a coarse vertex. - Remove all edges in the "edge neighborhood" \mathcal{N}_{ij} (those incident on v_i or v_j) from \mathcal{C}. - If no edge is selected at some iteration, we proceed to the next iteration (or stop if we have reached iteration T).

4. **Coarsening Matrix**: Construct the coarsening matrix C as described in Section 2.1 (Equation (2) and discussion around it). Each contracted set of original vertices forms one coarse vertex. Within each coarse vertex, the coarsening weights are constant and normalized such that the norm of each block is 1.

5. **Result**: The output includes: - The coarsening matrix C (n \times N, with n < N), - The coarsened adjacency matrix W_c, - The coarsened Laplacian L_c = C L C^\top.

References

- Equation (1): Definition of Laplacian. - Equation (2): Definition of coarsened Laplacian. - Algorithm 1: Randomized Edge Contraction. - Sections 2 and 3: Construction and analysis of the coarsening.

Examples

# Example on a small random graph
set.seed(42)
library(Matrix)
N <- 10
# Create a random adjacency matrix for a weighted undirected graph
A <- rsparsematrix(N, N, density=0.2, symmetric=TRUE, rand.x=function(n) runif(n,0,1))
diag(A) <- 0
# Coarsen the graph
result <- rec_coarsen(A, T=10)
str(result)

bbuchsbaum/graphweights documentation built on Dec. 14, 2024, 1:13 a.m.