A Measure of the Connection Strengths between Graph Vertices with Applications

Jie Chen, Ilya Safro

Abstract This paper introduces "algebraic distance," a computationally efficient metric for determining vertex connectivity in large-scale networks. By leveraging Jacobi Over-Relaxation (JOR), the proposed method captures neighborhood similarity with linear complexity. Experimental results demonstrate that incorporating algebraic distance into graph matching and hypergraph partitioning algorithms significantly improves performance over traditional edge-weight-based approaches.

Introduction

In graph theory, determining the "strength" of a connection between two vertices is a fundamental challenge. While standard metrics like shortest path length, maximum flow, or commute time are conceptually useful, they often suffer from high computational costs, ranging from $O(n^3)$ to #P-complete. Furthermore, simple edge weights often fail to capture the broader structural context; two nodes might share a heavy edge but belong to distinct, unrelated neighborhoods.

To address these issues, Chen and Safro propose the "algebraic distance," a measure that is local, fast, and effective for guiding combinatorial optimization tasks.

The Algebraic Distance Metric

The core of the proposed approach is an iterative process based on Jacobi Over-Relaxation (JOR). The algebraic distance between two nodes is defined by the absolute difference between their values after a small number of iterations.

Algorithm 1: Iterative computation of algebraic distances using Jacobi Over-Relaxation.

The algorithm initializes vertices with random values and iteratively updates them by taking weighted averages of their neighbors. This "Mutually Reinforcing Model" ensures that nodes with similar local environments converge toward similar values, resulting in a small algebraic distance. To ensure robustness, multiple initial random vectors are used and aggregated via $p$-norms.

Computational Efficiency and Stability

A key advantage of this method is its linear complexity, $O(km)$, where $k$ is the number of iterations and $m$ is the number of edges. Unlike other iterative methods, JOR allows for massive parallelization because updates for a node do not depend on the new values of its neighbors within the same iteration.

Convergence factor $\theta$ vs. relaxation parameter $\omega$.

The authors highlight that while the system eventually converges to a trivial state where all distances are zero, the relative distances stabilize very quickly—typically within 30 to 50 iterations. This "early stability" makes the measure highly practical for large-scale applications.

Experimental Evaluation

The method was evaluated using the UFL Sparse Matrix Collection, with graphs ranging from $10^3$ to $10^7$ edges.

  1. Maximum Weighted Matching: By preprocessing graphs to favor edges with small algebraic distances, the authors improved the performance of standard greedy matching algorithms. The preprocessed approach consistently outperformed textbook versions, increasing the matching size/cost ratio by up to 40% in some cases.
  2. Hypergraph Partitioning: The metric was integrated into the HMetis2 solver. The enhanced version, HMetis2+, produced lower "cut costs" across 200 test cases compared to the original black-box solver.

Conclusion

Algebraic distance provides a powerful, scalable tool for capturing local graph structure. While its current focus is on local connectivity, future work may extend the metric to capture long-range global structures or provide more direct applications to complex hypergraph architectures. Integrating this measure into multilevel coarsening frameworks remains a promising avenue for improving hierarchical graph algorithms.

Summary updated

Abstract

We present a simple iterative strategy for measuring the connection strength between a pair of vertices in a graph. The method is attractive in that it has a linear complexity and can be easily parallelized. Based on an analysis of the convergence property, we propose a mutually reinforcing model to explain the intuition behind the strategy. The practical effectiveness of this measure is demonstrated through several combinatorial optimization problems on graphs and hypergraphs.
BibTeX
@misc{chen2009measure,
  author = {Jie Chen and Ilya Safro},
  title = {{A Measure of the Connection Strengths between Graph Vertices with Applications}},
  year = {2009},
  eprint = {0909.4275},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/0909.4275},
}

Loading related content...

Figure