HyperEF Spectral Hypergraph Coarsening by Effective-Resistance Clustering Ali Aghdaei

2025-05-08 0 0 1.12MB 9 页 10玖币

侵权投诉

HyperEF: Spectral Hypergraph Coarsening by

Effective-Resistance Clustering

Ali Aghdaei

Stevens Institute of Technology

aaghdae1@stevens.edu

Zhuo Feng

Stevens Institute of Technology

zhuo.feng@stevens.edu

Abstract—This paper introduces a scalable algorithmic frame-

work (HyperEF) for spectral coarsening (decomposition) of large-

scale hypergraphs by exploiting hyperedge effective resistances.

Motivated by the latest theoretical framework for low-resistance-

diameter decomposition of simple graphs, HyperEF aims at

decomposing large hypergraphs into multiple node clusters with

only a few inter-cluster hyperedges. The key component in

HyperEF is a nearly-linear time algorithm for estimating hyper-

edge effective resistances, which allows incorporating the latest

diffusion-based non-linear quadratic operators deﬁned on hyper-

graphs. To achieve good runtime scalability, HyperEF searches

within the Krylov subspace (or approximate eigensubspace) for

identifying the nearly-optimal vectors for approximating the hy-

peredge effective resistances. In addition, a node weight propaga-

tion scheme for multilevel spectral hypergraph decomposition has

been introduced for achieving even greater node coarsening ratios.

When compared with state-of-the-art hypergraph partitioning

(clustering) methods, extensive experiment results on real-world

VLSI designs show that HyperEF can more effectively coarsen

(decompose) hypergraphs without losing key structural (spectral)

properties of the original hypergraphs, while achieving over 70×

runtime speedups over hMetis and 20×speedups over HyperSF.

Index Terms—hypergraph coarsening, effective resistance,

spectral graph theory, graph clustering

I. INTRODUCTION

Recent years have witnessed a surge of interest in graph

learning techniques for various applications such as vertex

(data) classiﬁcation [11], [25], link prediction (recommendation

systems) [28], [37], drug discovery [21], [26], solving partial

differential equations (PDEs) [13], [20], and electronic design

automation (EDA) [17], [23], [35], [36]. The ever-increasing

complexity of modern graphs (networks) inevitably demands

the development of efﬁcient techniques to reduce the size of

the input datasets while preserving the essential properties. To

this end, many research works on graph partitioning, graph

embedding, and graph neural networks (GNNs) exploit graph

coarsening techniques to improve the algorithm scalability, and

accuracy [6], [7], [27], [40].

Hypergraphs are more general than simple graphs since they

allow modeling higher-order relationships among the entities

[24]. The state-of-the-art hypergraph coarsening techniques are

all based on relatively simple heuristics, such as the vertex

similarity or hyperedge similarity [3], [8], [16], [29], [34]. For

example, the hyperedge similarity based coarsening techniques

contract similar hyperedges with large sizes into smaller ones,

which can be easily implemented but may impact the original

hypergraph structural properties; the vertex-similarity based

algorithms rely on checking the distances between vertices

for discovering strongly-coupled (correlated) node clusters,

which can be achieved leveraging hypergraph embedding

that maps each vertex into a low-dimensional vector such

that the Euclidean distance (coupling) between the vertices

can be easily computed in constant time. However, these

simple metrics often fail to capture higher-order global

(structural) relationships in hypergraphs.

The latest theoretical breakthroughs in spectral graph theory

have led to the development of nearly-linear time spectral graph

sparsiﬁcation (edge reduction) [9], [10], [14], [15], [19], [33],

[38] and coarsening (node reduction) algorithms [22], [39].

However,

existing spectral methods are only applicable to

simple graphs

but not hypergraphs. For example, the effective-

resistance based spectral sparsiﬁcation method [31] exploits

an effective-resistance based edge sampling scheme, while the

latest practically-efﬁcient sparsiﬁcation algorithm [10] leverages

generalized eigenvectors for recovering the most inﬂuential off-

tree edges for mitigating the mismatches between the subgraph

and the original graph.

On the other hand, spectral theory for hypergraphs has

been less developed due to the more complicated structure

of hypergraphs. For example, a classical spectral method has

been proposed for hypergraphs by converting each hyperedge

into undirected edges using star or clique expansions [12].

However, such a naive hyperedge conversion scheme may

result in lower performance due to ignoring the multi-way

high-order relationship between the entities. A more rigorous

approach by Tasuku and Yuichi [30] generalized spectral

graph sparsiﬁcation for hypergraph setting by sampling each

hyperedge according to a probability determined based on the

ratio of the hyperedge weight over the minimum degree of

two vertices inside the hyperedge. Another family of spectral

methods for hypergraphs explicitly builds the Laplacian matrix

to analyze the spectral properties of hypergraphs: Zhou et

al. proposes a method to create the Laplacian matrix of

a hypergraph and generalize graph learning algorithms for

hypergraph applications [41]. A more mathematically rigorous

approach by Chan et al. introduces a nonlinear diffusion process

for deﬁning the hypergraph Laplacian operator by measuring

the ﬂow distribution within each hyperedge [4], [5]; moreover,

arXiv:2210.14813v2 [cs.LG] 3 Dec 2022

the Cheeger’s inequality has been proved for hypergraphs

under the diffusion-based nonlinear Laplacian operator [5].

However, these theoretical results do not immediately allow

for practically-efﬁcient implementations.

This paper presents a scalable spectral hypergraph coarsening

algorithm via effective-resistance clustering to generate much

smaller hypergraphs that can still well preserve the original

hypergraph structural (global) properties. The key contribution

of this work is summarized below:

To the best of our knowledge, for the ﬁrst time, we propose

to extend the simple-graph effective resistance formulation

to the hypergraph setting by exploiting approximate eigen-

vectors (Krylov subspace) associated with the hypergraph.

Our approach (HyperEF) allows incorporating the recently

developed diffusion-based non-linear Laplacian operator

deﬁned on hypergraphs [5] for highly-efﬁcient estimation

of hyperedge effective resistances.

A scalable spectral hyperedge contraction (clustering)

scheme and a node weight propagation scheme have

been proposed for constructing coarse-level hypergraphs

that can well preserve the original spectral (structural)

properties.

Our extensive experiment results on real-world VLSI

designs show that HyperEF is over

70×

faster than hMetis,

while achieving comparable or better average conductance

values for most hypergraph decomposition tasks.

The rest of the paper is organized as follows. In Section II, we

provide a background introduction to the basic concepts related

to the spectral hypergraph theory. In Section III, we introduce

an optimization-based formulation for effective resistance

estimation in simple graphs. In section IV, we introduce the

technical details of HyperEF and its algorithm ﬂow. In section

V, we introduce a multilevel spectral hypergraph decompo-

sition framework. In section VI, we provide the complexity

analysis of HyperEF. In Section VII, we demonstrate extensive

experimental results to evaluate the performance of HyperEF

using a variety of real-word VLSI design benchmarks, which

is followed by the conclusion of this work in Section VIII.

II. BACKGROUND

Classical spectral graph theory shows that the structure

of a simple graph is closely related to the graph’s spectral

properties. Speciﬁcally, the Cheeger’s inequality shows the

close connection between expansion or conductance and the

ﬁrst few eigenvalues of graph Laplacians [18]. Moreover, the

Laplacian quadratic form computed with the Fiedler vector (the

eigenvector corresponding to the smallest nonzero Laplacian

eigenvalue) has been exploited to ﬁnd the minimum boundary

size or cut for graph partitioning tasks [32]. In recent years,

spectral theories for hypergraphs have been extensively studied

by theoretical computer scientists [5]. To allow a better

understanding of our work, the following important deﬁnitions

for hypergraphs are introduced.

Deﬁnition II.1.

Let

H= (V, E, w)

denote a weighted

hypergraph, where

w:E→R+

is a weight function over

hyperedges,

du:= Σu∈e,e∈Ewe

, and

vol(S) := ΣS∈V:u∈Sdu

The conductance of a given node set S∈Vis deﬁned as

CH(S) := cut(S, ¯

min{vol(S), vol(¯

S)},(1)

where the cut is the sum of the weights of the hyperedges

containing the nodes from both

and

. The hypergraph

conductance is deﬁned as CH:= min

∅*S⊆V

CH(S).

Deﬁnition II.2.

The non-linear quadratic form of a hypergraph

H= (V, E, w)

for any input vector

χ∈RV

is deﬁned as [5]

QH(χ) := X

e∈E

wemax

u,v∈e(χu−χv)2.(2)

III. EFFECTIVE RESISTANCES IN SIMPLE GRAPHS

Deﬁnition III.1.

Let

G= (V,E, z)

denote a weighted and

connected undirected graph with weights

z∈RV

≥0

bp∈RV

denote the standard basis vector with all zero entries except

for the

-th entry being

, and

bpq =bp−bq

, respectively. The

effective resistance between nodes (p, q)∈ V is deﬁned as

Reff (p, q) = b>

pqL†

Gbpq =

|V|

i=2

(u>

ibpq)2

λi

|V|

i=2

(u>

ibpq)2

iLGui

(3)

where

L†

denotes the Moore-Penrose pseudo-inverse of the

graph Laplacian matrix

, and

ui∈RV

for

i= 1, ..., |V|

denote the unit-length, mutually-orthogonal eigenvectors cor-

responding to Laplacian eigenvalues λifor i= 1, ..., |V|.

Theorem 1.

The effective resistance between

and

can be

computed by solving the following optimization problem:

Reff (p, q) = max

x∈RV

(x>bpq)2

x>LGx.(4)

Proof.

The original problem in (4) can be alternatively solved

by tackling the following convex optimization problem:

min

x∈RVx>LGx

s.t. x>bpq = 1.

(5)

After introducing a Lagrangian multiplier

, the following

Lagrangian function needs to be minimized

F(x, λ) = x>LGx−λ(x>bpq −1),(6)

which will lead to the following optimal solution:

λ∗=1

Reff (p, q), x∗=L†

Gbpq

Reff (p, q).(7)

Substituting x∗into (4) will complete the proof.

IV. SPECTRAL COARSENING VIA RESISTANCE CLUSTERING

A. Overview of HyperEF

A recent theoretical work proves that it is possible to

decompose a simple graph into multiple node clusters with

effective-resistance diameter at most the inverse of average

node degree (up to constant losses) by removing only a

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

HyperEF:SpectralHypergraphCoarseningbyEffective-ResistanceClusteringAliAghdaeiStevensInstituteofTechnologyaaghdae1@stevens.eduZhuoFengStevensInstituteofTechnologyzhuo.feng@stevens.eduAbstractThispaperintroducesascalablealgorithmicframe-work(HyperEF)forspectralcoarsening(decomposition)oflarge-scaleh...

展开>> 收起<<

HyperEF Spectral Hypergraph Coarsening by Effective-Resistance Clustering Ali Aghdaei.pdf

共9页,预览2页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

HyperEF Spectral Hypergraph Coarsening by Effective-Resistance Clustering Ali Aghdaei

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: