coarsen_graph_multilevel: Multi-level Graph Coarsening by Local Variation (Edge-based)

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

Multi-level Graph Coarsening by Local Variation (Edge-based)

Description

Implements the multi-level edge-based local variation coarsening based on Loukas (2019). The method updates the Laplacian and a subspace U at each level, ensuring stable re-orthonormalization and forcing at least one contraction if needed.

Usage

coarsen_graph_multilevel(
  A,
  n,
  k = 2,
  epsilon_prime = 0.5,
  max_levels = NULL,
  verbose = FALSE
)

Arguments

A	A sparse adjacency matrix (dgCMatrix) of the undirected graph.
n	Target number of vertices after coarsening (must be < N).
k	Dimension of the subspace to preserve (e.g., first k eigenvectors of L).
epsilon_prime	Error threshold for restricted spectral approximation (used as a heuristic).
max_levels	Maximum levels allowed (default: log2(N/n)), just to prevent infinite loops.
verbose	If TRUE, prints progress messages.

Value

A list:

A_coarse	The coarsened adjacency matrix.
P	The overall reduction matrix mapping original N to final n.
info	A list with final_epsilon, final_n, levels.

References

Loukas, A. (2019). "Graph Reduction with Spectral and Cut Guarantees." Journal of Machine Learning Research, 20(116):1–42.

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