Conductance Estimation in Digraphs: Submodular Transformation, Lovász Extension and Dinkelbach Iteration
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909665389969408 |
|---|---|
| author | Shao, Sihong Yang, Chuan Ye, Xinyang |
| author_facet | Shao, Sihong Yang, Chuan Ye, Xinyang |
| contents | Conventional spectral digraph partitioning methods typically symmetrize the adjacency matrix, thereby transforming the directed graph partitioning problem into an undirected one, where bipartitioning is commonly linked to minimizing graph conductance. However, such symmetrization approaches disregard the directional dependencies of edges in digraphs, failing to capture the inherent imbalance crucial to directed network modeling. Building on the parallels between digraph conductance and conductance under submodular transformations, we develop a generalized framework to derive their continuous formulations. By leveraging properties of the Lovász extension, this framework addresses the fundamental asymmetry problem in digraph partitioning. We then formulate an equivalent fractional programming problem, relax it via a three-step Dinkelbach iteration procedure, and design the Directed Simple Iterative ($\mathbf{DSI}$) algorithm for estimating digraph conductance. The subproblem within $\mathbf{DSI}$ is analytically solvable, and the algorithm is guaranteed to converge provably to a binary local optimum. Extensive experiments on synthetic and real-world networks demonstrate that our $\mathbf{DSI}$ algorithm significantly outperforms several state-of-the-art methods in digraph conductance minimization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_23131 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Conductance Estimation in Digraphs: Submodular Transformation, Lovász Extension and Dinkelbach Iteration Shao, Sihong Yang, Chuan Ye, Xinyang Optimization and Control 05C20, 90C26, 90C27, 90C32, 90C30 Conventional spectral digraph partitioning methods typically symmetrize the adjacency matrix, thereby transforming the directed graph partitioning problem into an undirected one, where bipartitioning is commonly linked to minimizing graph conductance. However, such symmetrization approaches disregard the directional dependencies of edges in digraphs, failing to capture the inherent imbalance crucial to directed network modeling. Building on the parallels between digraph conductance and conductance under submodular transformations, we develop a generalized framework to derive their continuous formulations. By leveraging properties of the Lovász extension, this framework addresses the fundamental asymmetry problem in digraph partitioning. We then formulate an equivalent fractional programming problem, relax it via a three-step Dinkelbach iteration procedure, and design the Directed Simple Iterative ($\mathbf{DSI}$) algorithm for estimating digraph conductance. The subproblem within $\mathbf{DSI}$ is analytically solvable, and the algorithm is guaranteed to converge provably to a binary local optimum. Extensive experiments on synthetic and real-world networks demonstrate that our $\mathbf{DSI}$ algorithm significantly outperforms several state-of-the-art methods in digraph conductance minimization. |
| title | Conductance Estimation in Digraphs: Submodular Transformation, Lovász Extension and Dinkelbach Iteration |
| topic | Optimization and Control 05C20, 90C26, 90C27, 90C32, 90C30 |
| url | https://arxiv.org/abs/2506.23131 |