Hypergraphs as Weighted Directed Self-Looped Graphs: Spectral Properties, Clustering, Cheeger Inequality
Authors: Zihao Li
Dongqi Fu
Hengyu Liu
Jingrui He
Venue: Accepted by TMLR ()

Abstract: Hypergraphs naturally arise when studying group relations and have been widely used in the field of machine learning. 
To the best of our knowledge, the recently proposed edge-dependent vertex weights (EDVW) modeling is one of the most generalized modeling methods of hypergraphs, i.e., most existing hypergraph conceptual modeling methods can be generalized as EDVW hypergraphs without information loss.
However, the relevant algorithmic developments on EDVW hypergraphs remain nascent: compared to the spectral theories for graphs, its formulations are incomplete, the spectral clustering algorithms are not well-developed, and the hypergraph Cheeger Inequality is not well-defined.
To this end, deriving a unified random walk-based formulation, we propose our definitions of hypergraph Rayleigh Quotient, NCut, boundary/cut, volume, and conductance, which are consistent with the corresponding definitions on graphs.
Then, we prove that the normalized hypergraph Laplacian is associated with the NCut value, which inspires our proposed HyperClus-G algorithm for spectral clustering on EDVW hypergraphs.
Finally, we prove that HyperClus-G can always find an approximately linearly optimal partitioning in terms of both NCut and conductance.
Additionally, we provide extensive experiments to validate our theoretical findings from an empirical perspective.

Published in Transactions on Machine Learning Research (11/2025)
Hypergraphs as Weighted Directed Self-Looped Graphs: Spectral Properties, Clustering, Cheeger Inequality
Zihao Li University of Mlinois Urbena- Chanmpng
zhhool55@ilinoois.de edu
Dongqi Fu Meta
donggifu@@mtta.com com
Hengyu Liu University of Illinois Urbona- Chaann--maaoignn
bengyu2@@llinois. edu
Jingrui He
jingrui@illioois.o edu
University of Ilinois Urbona- Chanapagn
Reviewed on OpenReview:
https: // openreview. net/ forum? id= WWWhhCCWMM
Abstract
Hypergraphs naturally arise when studying group relations and have been widely used in the field of machine learning. To the best of our knowledge, the recently proposed edge- dependent perter weights (EDVW) modeling (Chitra & Raphael 2019h is one of the most generalized modeling methods of hypergraphs, i.c., most existing hypergraph conceptual modeling methods can be generalized as EDVW hypergraphs without information loss. However, the relevant algorithmic developments on EDVW hypergraphs remain nascent: compared to the spectral thcorics for graphs, its formulations are incomplete, the spectral clustering algorithms are not well-developed, and the hypergraph Cheeger Inequlliyy nol well-defined. To this end, deriving unified random walk-based formulation, propose our definitions of hypergraph Rayleigh Quotient, NCut, boundary volume, and con- ductance, which are consistent with the corresponding definitions on graphs. Then, we prove that the normalized hypergraph Laplacian associated with the NCut value, which inspires our proposed HyperClus-G algorithm for spectral clustering on EDVW hyper- graphs. Finally, we prove that HyperClus-G can always find an approximately linearly optimal partitioning in terms of both NCu and conductance" Additionally, we provide extensive experiments to validate theoretical findings from empirical perspective.
1 Introduction
Yadati et al. 2019 Sun al. 2021), interactions between multiple proteins chemicals FFng et al. 2021 Xia et al. 2022 items that are liked by the same person (Yang& & Leskovec 2015 Wu et al. 2021 and interactions between multiple species in an ecosystem (Grilli et al. 2017
Higher-order relations ubiquitous, such co-authorship (Feng et al.
2018
Gorohssiaa et al. 2019 Hypergraphs, extended from graphs, with the powerful capacity to model group interactions (i.c., higher-order relations), show extraordinary potential for real-world tasks beyond pair-wise counections. Therefore, hypergraphs have been used widely
The NCut of the returned partition and the optimal NCut any partition N satisfy N < O(A*). 2he conductance of the returned partition and the optimal conductance 4* satisfy & 0(4*)

---

Published in Transactions on Machine Learning Research (11/2025)
Table 1: Properties of graph fodells/orruulaiions. EDVW hypergraphs generalized ETVW hypergraphs by allowing cach hyperedge distribute its vertex weights, bringing better formulation ficxibility.
Medeling/Porrmaation Formulation
undirected graphs
EIVW hypergraphs EDVW hypergraphs
edge and vertex weights
hyperedges edge-dependent vertex weights
summary of our developed formulations of EDVW hypergraph spectral propertics. Basod on random walks on EDVW hypergraphs, further develop the Rayleigh Quolient, NCul, boundary /cut. volume, and conductance, well as their associations. means not studied in Chitra & Raphael (019
Table 2:
EDVW Hypengraphs
Terminology/ praiillggyyyrrPPrrge Property
Graphs
Chitra & Raphael 2019
Our work
Graph Definition
g (V,8)
(V,E,w, 7). w stores edge weight and stores EDVW. wis' ta(e) with row sum āे; ø(6)"
Random Walk Transition
Pu.e (((.v)EE) (
Pu, Eecrin
Stationary Distribution
6P and En M())
ΦP Φ En Ø(w) 1, diagonal matrix I( o(v)
Laplacian(s)
L A, bagi = LDー
DP
L = DP-P" Laym = -11
Boundary Volume
[as| Emes.ve3 1((,, E)
jas E ((
Vertex Set Volume
(S)( Eves degree(u)
vol(5) Luss M(u)
R(x) Limare (o)))x(()) Eyey [a
(n(w) x(U))
Rayleigh Quotient
R(a))
Σ, (a(
Normalized Cut (NCu))
(a)(S) vollS) ]las|
NCut(S, (wrt()) v jas
Conductance
(S)
[6S]
( mnin (ot
[8s)
Algebraic Connections
similar property theorem WGY
NCut(S, 1R((x)
Theorem
Cheeger Inequality
A 20)
6:12 de = 20(H))
on22 < Aaagm < 20(H). Theorem
Spectral Clustering
well-developed
a new Algorithm
for EDVW hypergraphs
in recommendation systems ZZuu et al. 2016 Liu et al., 2022: Gatta et al.
2023), information retrieval
(Huang al., 2009 Zhu et al. 2015 and link prediction Huang et al. 2020
Fan et al. 2022
Hypergraphs modeled by edge-dependent verter weights (EDVW) were necessitated in a recent work |CChitra & Raphael 2019), with a motivat- ing example that in citation networks, each scholar (i.e., node) may con- tribute differently to each co-authored publication (i.c., hyperedge). The authors show that hypergraphs with bllge-nndependent verler weights (EIVW) do not actually utilize the higher-order relations for the follow- ing two reasons. First, the hypergraph Laplacian matrix proposed by the seminal work (Zhou et al., 2006). which serves a basis of many follow-up algs is equal to the Taplacian matrix of closely related graph with only pair-wise relations. In this way, all the linear Laplacian operators utilize only pair-wise relationships between vertices (Agarwal
directed graphs
undirected graphs
EIVW hypergraphs
EDVW hypergraphs
Figure 1: Undirected graphs EIVW hypergraphs EDVW hypergraphs. Pair- wise edges are naturally hyper- edges; each EIVW hypergraph can be reformulated to an EDVW hypergraph by setting each ver- lex's 's weight to be the same across hyperedges, yet allowing different vertices to have different weights.
et al. 2006). Second, many hypergraph algorithms (Ma al.] 2018
jtt al. 2018 Carletti al. 2020) are basod on random walks (Tong al. 2006), but has been proved that for any EIVW hypergraph, there ex- ists weighted pair-wise graph on which random walk is equivalent to that on the original hypergraph (Chitra & Raphael 2019).
In nature, EDVW hypergraphs are not a special case of hypergraphs, but a more generalized way to model hypergraphs by allowing flexible weight distribution, as shown in Figure I [revised as a side figure]. As typical (EIVW) hypergraphs can be reformulated to EDVW modeling, the properties and algorithms of EDVW-formulated hypergraphs can be applied to EIVW hypergraphs.
2

---

Published in Transactions on Machine Learning Research (11/2025)
In this paper, we focus further developing the incomplete yet fundamental spectral theories for EDVW hypergraphs, with a straight application spectral clustering, i.e., k-way global partitioning, where typically == 2. To be specific, k-way global partitioning aims to partition an entire graph into k clusters, where the vertices in one cluster are densely connected within this cluster while having sparser connections to vertices outside this cluster. On the one hand, although the spectral theories and spectral clustering on graphs have been well studiod, converting the hypergraphs to graphs (by connecting each node hyperodge) and applying those classic graph methods may ignore the higher-order relations and result in sub-optimal results [Wang& & Kleinberg 2024). On the other hand, despite the advantage of EDVW modeling, directly developing spectral clustering algorithm on EDVW hypergraphs is still an open question. To this end, for the first time, we propose a provably linearly optimal spectral clustering algorithm on EDVW hypergraphs, together with theoretical analysis concerning the Rayleigh Quotient, Normalized Cut (i.e., NCut), and conductance. In the context of EDVW hypergraphs, we bridge the eigensystem of Laplacian with the NCut value through our proposed Rayleigh Quotient. As discussed previously, the proposed algorithm can be applicd to EIVW hypergraphs well.
1.1 Main Results
In this paper, we further develop the spectral hypergraph theory for EDVW hypergraphs, and then study global partitioning EDVW hypergraphs.
Theorem 1. (Algebraic connections among hypergraph NCul, Rayleigh Quolient, and Taplacian). Given any hypergraph H. with vertez set V and hyperedge set & in the EDVW formatting, i.e., H. = (V,E,w, 7) with positive edge weights w(-) > 0 and non-negative edge-dependend vertez weights %-(-) for any hyperedge E E, we define Normalized Cul NCuu(-), Volume of a verlea set (.) Rayleigh Quolient R(.)) Laplacian L, and stationary distribution matric 1I as Definition |V- -dddimensional vector x such that
16
13
14
and 7 For any vertez set S S V, we define a
vol(S) (S)
x(u)=
V
VuES,
(1)
x<()) vol(S)
A E.
vol(S))
Then,
1 R(z) 2I1
x² Lae
8)
(2)
To the best of our knowledge, while prior works Jost & Mulas (0119); Mulas et al. 2022 studied the Rayleigh Quotient under the EIVW model, this is the first work that develops the Rayleigh Quotient for EDVW hypergraphs. Inspired by this Theorem, we develop a spectral clustering algorithm HyperClus-G to optimize the NCut value by relaxing the combinatorial optimization constraint.
Theorem 2. (Hypergraph Spectral Clustering Algorithm) There erists algorithm for hypergraph spectral clustering that can be applied to EDVW-formatier hypergraphs, and always returns approzimately linearly optimal clustering in terms of Normalized Cut and conductance. In other words, approzimately, the NCut of the relurned partition N and the optimal NCu of any partition * sulisfy N < <(N*).
We name this algorithm as HyperClus-G. G, whose pseudo code is given in Algorithm with complexity analyzed in Appendix B. Moreover, to extend the hypergraph spectral theory, for the first time, we give complete proof regarding the hypergraph Cheeger Inequality. In the meantime, by proving Theorem 3 the previous result hypergraph Cheeger Inequality (Theorem 5.1 in (Chitra & Raphael 2019h) is fixed and upgraded.
Theorem 3. (Hypergraph Cheeger Inequality) freduced verbosity] Let H. W, be hypergraph in the EDVW formatting. Define ((H) = minsgv (SS). Then the second smallest eigenvector X of the normalized hypergraph Laplacion II 1/2 LII à satisfies
(7))2
< X < (7(
(3)
2
3

---

Published in Transactions on Machine Learning Research (11/2025)
Definition
CDVW Hypeegraph; Random
Walk; Staticuary Distribution)
Theoven Slationnry Distribation Existemce)
Chisra & Raplael 2019
Definittion
Definition
Definition
(DDVW Laplaciaus)
De
Volumees)
(Rayleigh Quolient)
(Noemalized Cut)
(Conductaune)
Theorem
Theorema 15 Rayleigh Quolient mani Laplacion))
Theorem 10 Corollary
20
Theorem
Cheeger Inequality
(Algeboriic Connecionn
(Condaclance Bound)
for EDWW Hypergraph)
Theorem
myperChus.C Algorishm
Optimality)
Figure 2: Logical flow of our work. 'A->B' means A is required for developing B.
In fact, this theorem shows that our HyperClus-G is also approximately linearly optimal in terms of conductance. In other words, the conductance of the returned cluster & and the optimal conductance Tx satisfy + < O( As shown in Table we bridge the gap between the previous work Chitra & Raphael 2019 to broader spectral applications by further developing spectral theories on EDVW formulation.
Technical Overview. [reduced verbosity] The technical map is summarized in Figure 2 The key in- sight from the previous work (Chitra & Raphael 2019h is to model the hypergraphs similar to directed graphs through the equivalence of random walks. Unlike classical graph theory, such directed graphs are odge-weighted, weig-weigh and contain self-loops. In this work, inspired by the definitions of Rayleigh Quotient, NCut, boundary /cut, volume, and conductance in graphs, we develop these definitions in the con- text of EDVW hypergraphs. We show that Theorem and Theorem 3 properties that hold for graphs, still hold for hypergraphs using unified definitions. From Theorem HyperChus-C G is approximately linearly optimal in terms of both NCut and conductance.
can further prove that our proposed
Our Appendix contains supplementary contents, such as trivial proofs and experimental details.
Paper Organization. [reduced verbosity] In Section 2 we introduce notations regarding EDVW hyper- graphs. Tn Section 3 we introduce our definition of hypergraph Rayleigh Quotient, and show its connection with the Laplacian and NCut. Then, we propose our HyperClus-G inspired by such connection. In section we prove the Cheeger Inequality of EDVW hypergraph, then show the oplimality of our HyperClus-G. Finally, Section presents comprehensive experiments to validate theoretical findings.
2 Preliminaries
We use calligraphic letters (c.g., A) for sets, capital letters for matrices (c.g., A), and umparenthesized superscripts to denote the power (e.g., A*). For matrix indices, we use Ar, or A(i,j) interchangeably to denote the entry in the ith row and the jth column. For row vector or column vector v, we use v(i) to index ,th entry. Also, we denote hypergraph as H and graph as G.
Table contains important notation and hyperparameters for quick reference. A hypergraph consists of vertices and hyperedges. A hyperedge is a connection between two or more vertices. We the notation E if the hyperedge connects vertex This is also called "e is incident to vt. Definition 4 and 5 provide necessary notations to define the hypergraph random walk in Definition 6 The transition matrix P of EDVW hypergraphs is consistent with that of graphs.
Definition [Chitra & Raphael, 2019) (EDVW hyperyraph). hypergraph H (V, E, with edge- dependent verter weight defined as set of vertices V, set E C. 22 of hyperedges, weight mapping w(e): E + R4 on every hyperedge E E, and weight mappings 7e(u): V -+ Roo corresponding to on every
4

---

Published in Transactions on Machine Learning Research (11/2025)
Table 3: Table of Notation
Symbol
Definition and Description
H = (V,E,w,))
hypergraph being investigated, with verlex set V. hyperedge set E, edge weight mapping w and odge-depeudent verlex weight mapping ?
[V]
number of vertices in Hypergraph
m
number of hyperedge-vert vertex connections Hypergraph H. m Eeee
d(p)
degree of vertex v, d(u) = EeEE(e) w(e))
d(e)
degree of hyperedge e, = 7c(1)
R
[ [
vertex-weight matrix
W
M
[|]
weiehedge-weight matrix
Dv
M vertex-degree matrix
Dg
E g
hyperedge-degree matrix
P
M V
transition matrix of random walk on 7
1 [V] stationary distribution of random walk
11
V x V diagoual stationary distribution matrix
L
V x V random-walle saalom-wall-based Laplacian
1 x [ probability distribution on y
vertex v. For ei * e2, Tex (v) and Yea (v) may be different. Without loss of generality, we inder the vertices by 1, 1V., and let V (1, .... |/]..
For an EDVW hypergraph Moreover, (v) >0 > V E For instance, in a citation hypergraph, each publication is captured by hyperedge. While each publication may have different citations (i.e., edge- w(e)), each author may have individual weight of contributions (i.e., publication-dependerr (v)).
(V,E,,,)) w(e) > for any e E 7e(e) 2 for any e E & and E
Definition [Chitra & Raphael, 2019) weight matriz, weight matrir, verter-degree ma- triz, and deperedge-degree matrir of an EDVW hypergraph). E(v) = {E E s.l.v E J is the set of hyperedges incident to vertez d(v) EcER(N) w(e) denotes the degree of verter v. 5(e) =vee Yc(v) denotes the degree of hyperedge e. The vertez-weight weight matrix R is an |E] [V] matrir with entries A(e,e) = = The heperedgee-wiighe matria W is [V] |ε\ matrix with entries W(,,e) w(e) if e, and W(r, e) = otherwise. The verter- degree matriz Dy is [V| diagonal matriz with entries Dy d(v). The hyperedge- degree matriz De is El x |8| diagonal matrix with entries De(e,e) 8(e)).
Assumption 1. Since we are dealing with clustering, without loss of generality, we assume the hypergraph H is connected. A rigorous definition of hypergraph conneclivity is provided in Appendir A.1
The random walk on EDVW hypergraph was proposed in CChitra & Raphael 2019). Intuitively, at time t, =(c) then pick a ó(e) and finally move to vertex at time t + 1. We can define the transition matrir P to be a [V] x [V] matrix with entries Pu.e to be the transition probability from u to y as follows.
random walker at vertex u will first pick an edge incident to u with the probability a[u)
vertex from the picked edge with the probability ne(e).
Definition 6. Chitra & Raphael 2019) (Hypergraph random walk). A random walk on hypergraph with edge-dependent vertex weights H. (V,E,w, 7) is Markov Chain on V with transition probabilities
w(e) (e(v)
P Pup Σ
(4)
d(u) 8(e)
(E
P. can be written in matriz form as P= D WD'' R and it has row sum of 1. (Proof in Appendir A.2
Random walks and stationary distribution serve a basis when conducting spectral analysis. Under as- sumption 1 unique stationary distribution exists (referring to Theorem
5

---

Published in Transactions on Machine Learning Research (11/2025)
Definition 7. (Stationary distribution of hypergraph random walk). The stationary distribution of the random walk with transition matriz P is a alala x [V] row vector & such that
= p > OVEEV;
Σ [(u)= =1
(5)
WEV
From 1, define the stationary distribulion malrir to be [V] [V] diagonal matriz with enlries Th +(i). Theorem 8. CChtrra & Raphael 2019). The stationary distribulion @ of hypergraph random walk: crists.
Theorem has been proved Chitra Appendix A.4
Raphael 2019 In this paper, we give a simplified proof in
Definition 9. (Chitra & Raphael, 2019) (random-utd wwlloom-wwll-aaee walk-based hypergraph Laplacian). Let = (V, w, 7 a heperyraph with adge-dependent vertex weight. Let P be the transition matrix and TT be the corresponding stationary distribution matria. Then, the random-wodd based hypergraph Leplacion L
L L= 1IP I'I+
(6)
2
In this work, Appendix A.5 we further show that consistent with graph Laplacian in terms of eigensystem as evidence of the rationality of Definition 9
3 Spectral Properties Inspire Global Partitioning
In this section, we first extend the spectral theory for EDVW hypergraphs, then we introduce our HyperClus- G algorithm. Specifically, we show that using our definitions, there are algebraic connections among hyper- graph NCut, Rayleigh Quotient, and Laplacian (Theorem D which are consistent with pair-wise graphs.
From Definition 10 to Definition 13 in the context of EDVW hypergraph, re-define the volume of boundaries and vertex sets. We show that our definitions have properties that consistent with those graphs. Given vertex set S C V, we use S to denote its complementary set, where SUS V and Sns 0. We have the following definition regarding the probability of a set.
Definition 10. (Probability of a sel). For distribution p on the vertices such that Yo E V, V,p(v) 2 0 and P(U) = 1, we denote
P(S) = Σ VS
(7)
ZES
Equivalently, we can regard p as a 1 | vector with p; = p(). From this definition, 6(S) + 6(S) 1. By definition of random walk and its stationary distribution,
((S) (sP)(S) ((S)
Σ p(u)Pu.v +
Σ (l.)
(8)
uES
uES,
Therefore, we have the following Theorem that, in the stationary state, for any set S, the probability of walking into S or out of S are the same.
Theorem 11. Let H (V.E,w,)) be hypergraph with edge-dependent verter weights. Let P be the transition matrix and & be the corresponding stationary distribution. Then, for any vertex set S CV
Σ p(u)
Σ p(u)Pu.
99)
For unweighted and undirected graphs, the volume of the boundary/cut of partition is defined as 0S K[x,y Elæ E S.y S)). The intuition behind is the symmetric property jas] = las]. Theorem 11 also describes such property, and find it intuitively suitable to be extended to the following definition.

---

Published in Transactions on Machine Learning Research (11/2025)
Definition 12. (Volume of hypergroph boundary). cut between S and S, by [os) = Σ
We define the volume of the hypergraph boundory, i.e.,
Pau)
Σ
((u) Pu,
(10)
uES,uES
uES,
Furthermore, 0 S |as] S Enes ((u) S |as| jas).
For unweighted, undirected graphs, the volume of vertex set S is defined as the degree sum of the vertices in S. With the observation that (u)) = EvEs,rEv P u.,s @(u) itself is already a sum of the transition probabilities and can be an analogy to vertex degree. We extend this observation the following definition.
Definition 13. (Volume of hypergraph verter set), We define the volume of a verter set C V in hypergraph H by
vol(S) = Σ (d())
E 10
(11)
Furthermore, we have vol(0) 0, vol(V) = and vol(S) + vol(S) = 1. Definition 12 and Definition 13 will serve as the basis of our unified formulation. By these two definitions, we also have [as vol(S), which is consistent with those on unweighted and undirected graphs
Typically, for a graph G and its Laplacian Lg = Dg - Ag, the unweighted Rayleigh Quotient is defined as a function R₁ : IR" \ {0} - R such that
x Eiien [x(i)= x())²
RLo (x)
(12)
x²aa x
Liev, |z())
According the form of generalized Rayleigh Quotient R2 (x) x²
Golub & Loan 1996), we extend
x² Dz
this generalized Rayleigh Quotient to EDVW hypergraphs follows.
Definition 14. (Hypergroph Rayleigh Quotient). We define Rayleigh Quotient on H. of any di-dimensional real vector to be
R(x) E..o [z(u)= x(v)R E. (Q)
(13)
We prove the following theorem which validates that our definition is consistent with the Rayleigh Quot ient on graphs and satisfies the property similar to Equation I2 Theorem 15. For any [Vlddimensoonal real vector x,
x² Lx
xx L.
R(x) = x TI
= 2.
(14)
x III
(Proof in Appendir A.6
The 2-way Normalized Cut, well-known measurement of the cluster quality, is defined as vol(S) Analogically, we derive the NCut for EDVW hypergraphs using Definition 12
[88)
+
|os
(S)
Definition 16. (Hypergraph Normalized Cut). For any verter set SVV,
NCut(S, ( (o)
Σ
((u)
(15)
(S)
WES,
Following this definition, the problem of global partitioning on EDVW hypergraphs aims to find a vertez set S that minimizes the NCut value. We now derive the association between our hypergraph Neut, Rayleigh Quotient, and Laplacian, which directly inspires spectral 2-way clustering approach (Algorithm 1

---

Published in Transactions on Machine Learning Research (11/2025)
Theorem 1. (Restatement of Theorem in Main Results) For any vertez set S S V, we define |V-- dimensional vector x such that
s(u)= = vol(S) vol(S) A '
(16)
vOl(S) vol(S)
<(u)
V ú S.
x² La
then NCut(S, S) - R(x) x² 1Ir
(17)
(Proof in Appendia A.7
By Theorem the original global partitioning problem becomes
min R(x) s.b. x is defined Eq 16 (fixed labeling index)
(18)
The above an No-copllete problem Shi Malik 2000 If we relax the restriction of that each entry
has to be either
S) [S] or
(Q for some S, then the problem becomes
[S]
Lx for x E3 \
min R(x) min
(19)
x "Ixx"
Using the property of Rayleigh Quotient, the minimum can be achieved by choosing æ to be the eigenvector associated with the second smallest eigenvalue of the generalized eigenvalue system Lx ATTa Ghojogh et al. (2019). Replacing 11 we have
La Mll + -II = =
(20)
11 -II 1 A=
-II- is symmetric and positive semi-definite matrix, for which all eigenvalues non-negative real numbers. As the smallest cigenvalue is zero, and the associated clusters are trivial (V and (), we select the second smallest eigenvalue as the corresponding solution. Since the second smallest eigenvalue of 11 - denoted by Åι, is real, there exists a real vector z such that
LI 3 A1Z
(21)
We can then approximate the solution of the original global partitioning by choosing
if 2 2 0 u e if xu)) 0
u E S
(22)
Moreover, we define a new variant hypergraph Laplacian.
Definition 17. (Symmetric normalized random-walk-hon based hypergraph Laplacian). Let 7L - (V,E, w. be
a hypergraph with edge-depence dependetn verter weight. Let P be the transition matria and II be the corresponding stationary distributton matria. Then, the symmetric normalized random- aadom--walk-ao based hypergraph Taplacian Lagm
Leym = + = P
(23)
2
Lagm also real and symmetric, and hence hermitian. The eigenvectors of Laym provide an approximate solution of 2-way hypergraph clustering. The formulation of this Laplacian is consistent with that for digraphs (Chung 2005).
8

---

Published in Transactions on Machine Learning Research (11/2025)
Algorithm HyperClus-G
Require: EDVW hypergraph H (V,),,,)
Ensure:
two clusters of vertices
Compute R, W, Dy; DE according to Definition 5
Compute the transition matrix P by Definition
3: Compute the stationary distribution by power iteration.
4: Construct the stationary distribution matrix II and compute the Laplacian by Definition
5: Compute eigenvector of II LIT associated with the second smallest eigenvalue.
6: Return the clusters based on the signs of the entries in the computed eigenvector.
4 Hypergraph Cheeger Inequality and Optimality of HyperClus-G
In this section, we show the hypergraph Cheeger Inequality (Theorem Bi, which is consistent with the Cheeger Inequality pair-wise graphs. The Cheeger Incquality requires the below definition of conductance. From the Cheeger Inequality, we prove the approximate linear optimality of HyperClus-G terms of both NCut and Conductance.
Definition 18. (Hypergraph conductance). The conductance of a cluster S on
[as|
Φ(S)
min(vol(S), (o)
jas
(24)
min(vol(S), 1- vol(S)) -oo((()
ExeS,eEs ((u)
min ( u(u), - Enes o(u))
Theorem 19. For any verter set S C V, our hypergraph conductance D(S) [0, 1], which is consistent with graph conductance (Proof in Appendia A.8
4.1 Hypergraph Cheeger Inequality
Cheeger Inequality can be proved for our newly defined Symmetric normalized random-walk-ben based hyper- graph Laplacian (Definition I7.. The proof is similar to that for digraphs CChung 2005) and shows the rationality of our definitions.
Theorem 3. (Hypergraph Cheeger Inequality, Restatement of Theorem in Main Results) Let H. (V. 8, T) be on EDVW hypergraph. Define ((H)) minscv 4(S), where 4(S) is defined in Defonition 18 Then the second smallest eigenvector X the normalized hypergraph Laplacian Lay satisfies
{HH) S 5 (4(H)
(25)
(Proof in Appendia A.9
4.2 Approximate Linear Optimality of HyperClus-G
Optimality in terms of NCut. From Theorem [ and the relaxation of the restriction, the second smallest cigenvector À of the normalized hypergraph Laplacian Laym is an approximation of both optimal NCut and the NCut of the returned cluster. Therefore, the returned cluster is approximately linearly optimal in terms of NCut.
Optimality in terms of conductance. Using the RHS of Hypergraph Cheoger Incquality (Thcorem 3 À satisfies À < 2H(H), where ((H) minscy (SS) is the optimal conductance. Additionally, we have the following corollary from Definition 16 and 18 connecting NCut and conductance.
Corollary 20. For any cluster S, $(S) NCut(S,S).
9

---

Published in Transactions on Machine Learning Research (11/2025)
Proof. From Definition 16 and 18 reeuueed space cost]
|as]
Enes,ves Pu. min(vol(S) vol(S))
(S) min(vol(S), vol(S))
(26)
Σ P NCut(S,S)
vol(()) voo(s))
u
Therefore, let the returned cluster be Steturn, then we have
(Sreturr)) I NCut(Sreturn Stetura) = A S (
(27)
which shows the approximately linear optimality of the returned partition from HyperClus-G. In fact, we can make the "se more rigorous by observing that À = min (0) 1/2 [xx) R()) { = NCCut(Sreturrn Syeturn); where # defined according to Theorem [ with S = Syeturn. However, it is impossible to bound (CeutSSeetuu Sreturn) in terms of big-O of X, since there exist counterexamples for sign-threshold spec- tral graph partitioning (and thus also for EDVW hypergraphs) where can be arbitrarily small while N C'ut remains arbitrarily large.
5 Supportive Experiments
In this section, we demonstrate the effectiveness of our HyperClus-G on real-world data. We first describe the experimental settings and then discuss the experiment results. Details are provided in Appendix C
5.1 Global Partitioning Setup
Datasets and Hypergraph Constructions. We use 9 datasets, all from the UC Trvine Machine Learning Repository. The datasets cover biology, computer science, business, and other subject areas. The construc- tion progress of hypergraphs is the same as the seminal works (Zhou al.) 2006 Li & Milenkovic 2018 Hein et al. 2013): for each dataset, each instance is vertex, and use group of hyperedges to capture each feature. For example, in the Mushroom dataset, for its "stalk-shape" feature, we connect all the instances that have an enlarging stalk shape by a hyperedge, and connect all the instances that have a tapering stalk shape by another hyperedge. We use one hyperedge for each categorical feature. For numerical features, we first quantize them into bins of equal size, then map them hyperedges. More details of each dataset and construction can be found in Appendix C.2
EDVW Assignments. Each dataset contains at least classes. For any dataset, assume set V/ contains all vertices in class k; for any hyperedge e, assume Ve contains all vertices that connects, then we assign the deterministic EDVW:
(v) = 1Vx VvVe E V
(28)
In other words, for any hyperedge e and any vertex v in class k %e(v) is the number of vertices in class k that e connects. This assignment makes the vertex weights for different hyperedges highly different. We intentionally and implicitly encode the label information into the vertex weights to validate that our HyeprClus-G can take the fine-grained information that is usually ignored by other hypergraph modeling methods.
Settings and Metrics. Among the 9 datasots, 5 of them have 2 classes, and 4 of them have at least 3 classes. For 2-class datasets, we apply HyperClus-G to partition the whole EDVW hypergraph into 2 clusters. For k-class datasets (A: 2 3), we call HyperClus-C G iteratively for times to get a k-way clustering. We first measure the quality of clusters by NCut. The 2-way clustering NCut has been provided Definition 16 and we further define the k-way clustering NCut here.
For example, dumbhell graphs consisting of two large cliques (or expanders) connected by a single edge.
10

---

Published in Transactions on Machine Learning Research (11/2025)
Table NCut Comparison()) of Global Partitioning Task on EDVW Hypergraphs.
way Clustrring
k-way Clustering (k 2 3)
Method Name
Mushroom
Rice
Car
Digit-24
Covertype
Zoo
Wine
Lester
Digit
STAR++
0.6484
0.3479
0.8347
0.6458
0.8912
5.1402
1.5799
2.1866
8.4951
CLIQUE++
0.6426
0.1011
0.8317
0.6115
0.8887
5,14178
1.67122
2.2177
8.4351
DiffEg
0.9425
0.7445
0.9729
0.9611
0,9895
5.8772
1.9667
2.8406
8,9477
node2vec
0.8500
0,7596
0.9334
0.6:17
0.9676
5.5537
1,8253
2.1663
8,47-15
hyperedge2vec
0.6856
0,3936
0,8360
0.6155
0,9102
5,1443
1.6203
2.1258
8,4517
artual class label
0.6778
0.3801
0.8490
0.6415
0,9300
5.4676
1.9883
2.5765
8.7046
HyperClus-G (Ours)
0.6388
0.3577
0.8320
0.6412
0.8911
5.1386
1.5831
2.1184
8.4197
Table 5: Fis Comparison(t) of Global Partitioning Task on EDVW Hypergraphs.
2-way Clustoring
K-way Clustering (k
3)
Method Name
Mushroom
Rioe
Car
Digit-24
Covertype
7on
Wine
Letter
Digit
STAR++
0,903, 0.874
0.900) 0.855
0.569, 0.550
0,980, 0.980
0.694, 0.436
[1880
0.385
0.626
0.514
CLIQUE++
0.898, 0.870
0.854, 0.843
0.569, 0.550
0,983, 0.983
0.701, 0.455
0.706
0.385
0.531
0.633
Difleq
0.691, 0.247
0.765, 0.344
0,653, 0.154
0.687, 0.278
0.837, 0.158
0.313
0.369
0,275
node2vee
0.531, 0.508
0.663, 0.148
0.640, 0.541
0.985, 0.985
0.688, 0.064
0.452
0.300
0.647
0.545
hyperedge2vec
0.8411, 0.835
0.8413 0.808
0.571, 0.545
0.971, 0.970
0.677, 0,290
0.861
0.393
0.587
0.451
HyperClus-G (Ours)
0.915, 0.889
0.917, 0.932
0.706, 0.697
0.996, 0.996
0.701, 0.188
0.893
0.395
0.704
0.629
Definition 21. For any k-way clustering of vertex set V,
jas
NCut(SS,.... Sx) =
(29)
(S,
Another metric cluster quality is whether the partition aligns with the 'ground-truth" label data. The vertices in the same cluster are determined by the algorithms to be closely related in structure, while the vertices in the same label class should also be internally similar. These two similarities usually align, and therefore we greedily match the clusters with classes and see if each matching has a high F1 score. For 2-way clustering, we report the Fl scores of both clusters, For k-way clustering, we report the weighted Fl scores of all clusters. More details are provided in Appendix C.3)
Baselines. We compare our HyperClus-G with multiple state-of-the-art methods. STAR+ and CLIQUE++ expansions convert the hypergraph into weighted graphs and then adopt spectral clustering graphs. Moreover, since it is proven that, the EIVW Laplacian proposed by (Zhou et al. 2006 is equal to the Laplacian of the corresponding STAR++ expanded graph (Agarwal et al. [2066] Chitra & Raphael 2019), our STAR++ baseline is equivalent to spectral clustering on EIVW hypergraphs by ignoring the as- signed EDVW. DiffEq (Takai et al. 2020) is based on differential operators. node2vec (Grover Leskoved 2016) and 2ven (a.k.a., hyperedge2vec) (Fu et al., (019) are two unsupervised graph embedding meth- ods. We first convert the hypergraph into the required input graph form, then call the k-means algorithm after we get the vertex embedding. We also compare with the NCut of the actual labeled classes (Vi,..,, Vi partitioning). For the nondeterministie baselines, run the experiment 10 times and report the mean. The standard deviations are relatively small, and we put them in Appendix C.6.1 More details on baselines are provided in Appendix C.5
5.2 Results
The global partitioning experiment results are shown in Tables 4 and 5 bold, and the second-best results are marked with underlines. For 2-way clustering, we also consider that the two Fls of high-quality partition should be fairly similar. First, our algorithm HyperClus-G generally outperforms the bascline methods in terms of NCut. It worth noting that, facing a combinatorial opti- mization problem, our HyperClus-G constantly outperforms the actual-class partition, and may already get very close to the imal NCut. Second, STAR++ and CLIQUE++ expansions, as graph approximations
The best results are marked in
11

---

Published in Transactions on Machine Learning Research (11/2025)
Table Execution (1me(4) on Global Partitioning Task in seconds. Full Table in Appendix C.6.2
2-way Clustering
R-wny Clustering (l 2 3)
Meshod
Mushroom
Rice Covertype
Wine Letter
Digit
STAR
72.82
50.80
318.55
32.18
37.54
59.05
CLIQUE++
216.01
13.32
77.75
50.25
297.37
HyperClus-G
17.73
5.04
87.72
11.48 35.13
26.49
for hypergraphs, are very strong baselines and can generate sub-optimal clustering. Third, in terms of Fl scores matched with actual classes, our HyperClus-G also achieves the best performance in general. The only exception is Digit k-way clustering, where HyperClus-G achieves the second best, but is very close to the best. This again shows that STAR+ and CLIQUE++ expansions are strong baselines. Unsupervised embedding methods can beat STAR++ and CLIQUE++ expansions on smaller datasets. Fourth, though HyperClus-G not designed for k-way clustering, applying it multiple times returns high-quality k-way clustering. Fifth, it turns out. that the second smallest eigenvalue of Lyym is a good approximation for NCut (Refer to Section 5.3 for details), which is consistent with our theoretical analysis. Sixth, report the execution time in Table D in fact, for NCut in Rice, Covertype, and F1 in Digit, where STAR++ CLIQUE+ expansion achieves the best performance, it needs to take 10x time compared to HyperClus-G.
Table 7: Comparison of 2-way NCut and its Eigenvalue Approximation.
2-way Clusteriag
Value
Mushroom
Rice
Digit-21
Covertype
2-way NCut value of HyperClu-- results
0.6388
0.3577
0.8320
0.6112
0.8911
2nd smallest rigenvalue of fagm (Definition
17
0.6171
0.2686
0.7655
0.6220
0.8663
relutive error eigenvalue nend| / nent
3.397%
24.91%
7.983%
2.994%
2,783%
5.3 Validation of the Eigenvalue Approximation
According to theoretical study of Theorem and the later transformation of the problem, the second smallest eigenvalue of the symmetric normalized random- waannn-wwll---a based hypergraph Laplacian Leym should be approximation of the NCut value by relaxing the combinatorial optimization constraint. We validate this by showing the 2-way NCut value of the clustering result from our algorithm HyperClus-Ga, and compare it with the second smallest cigenvalue of Laym- The data are shown in Table 7 turns out that the two numbers are positively correlated, and the error lends to be small. The Rice dataset, which has much more hyperedges than other datasots, has the largest relative error.
5.4 Ablation Study
To show that our algorithm exploits the EDVW information, we conduct an ablation study of STAR+++. CLIQUE++, and HyperClus-G on the EIVW hypergraphs where the EDVW is set to be constant value of one. From the results, observe that the clustering performance of HyperClus-G on EIVW hypergraphs is the same STAR++. First, this validates that the performance boost given EDVW hypergraphs is because our ElyperClus-e G can exploit EDVW. Second, the conjecture that our HyperClus-G degenerates to STAR+ given an all-one-EDVW hypergraph, is naturally raised, even though the dimensions of their Laplacians are different. Experimentally, we observe that for all-one-EDV of Laym has the same direction as the sub-vector of all the original vertices of the second smallest eigenvector of the random-wall Laplacian of the STAR++ graph. This an interesting phenomenon that is worth studying in the future.
hypergraphs, the second smallest eigenvector
12

---

Published in Transactions on Machine Learning Research (11/2025)
Table 8: NCut Comparison (1) of Global Partitioning Task on EIVW Hypergraphs.
2-way Clustering
Method Name
Mushroom
Rice
Car
Digit-24
Covertype
STAR+
0.6926
0.3754
0.8340
0.7047
0.8884
CLIQUE+++
0.6870
0,4318
0.8340
0.7045
0.89413
actual class label
0.7554
0,4833
0.8782
0,7080
0.9339
HyperClus-G (Ours)
0.6926
0.3754
0.8340
0.7047
0.8884
Table 9: Comparison (t) of Global Partitioning Task on EIVW Hypergraphs.
2-way Clustering
Method Name
Mushroom
Rice
Car
Digit-24
Covertype
STAR+
0.903, 0.874
0.900, 0.855
0.569, 0.550
0.980, 0.980
0.694, 0.436
CLIQUE++
0.898, 0.870
0.854, 0.843
0.569, 0.550
0.983, 0.983
0.701, 0.455
HyperChus.G G (Ours)
0.903, 0.874
0.900, 0.855
0.569, 0.550
0.980, 0.980
0.694, 0.436
6
Conclusion
This work advances a unified random walk-based formulation of hypergraphs based EDVW modeling, We introduce key definitions, such Rayleigh Quotient, NCut, and conductance, aligning them with graph theory to advance spectral analysis. By establishing the relationship between the normalized hypergraph Laplacian and the NCut value, we develop the HyperClus-G algorithm for spectral clustering on EDVW hypergraphs. Our theoretical analysis and extensive experimental validation demonstrate that HyperClus-C G achieves approximately optimal partitioning and outperforms existing methods practice.
Acknowledgment
This work is supported by National Science Foundation under Award No. IIS-2117902 and AFOSR (FA9550- 24-1-0002). The views and conclusions are those of the authors and should not be interpreted as representing the official policics of the funding agencies or the government.
References
Sameer Agarwal, Kristin Branson, and Serge J. Belongie. Higher order learning with graphs. In William W. Cohen and Andrew W. Moore (eds.), Machine Learning, Proceedings of the Twenly- Third International Conference (ICML 2006), Pittsburgh, Pennsylvania, USA, June 25-29, 2006, volume 148 of ACM In- lernational Conference Proceeding Series, pp. 17 24. ACM, 2006. doi: 10.145//14384441148888 URL https://doi.org 10. 1145/1143844, 1143847
Timoteo Carletti, Duccio Fanelli, and Renaud Lambiotte. Random walks and community detection in hypergraphs. CoRR, abs/22010.14355 2020. URL
14355
Uthsav Chitra and Benjamin J. Raphael. Random walks on hypergraphs with edge-dependent vertex weights. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9- June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 1172-1181. PMLR, 2019. URL TTRphhttp://prrceeddaaa mlr wttpa/sssl..........ee hatt.press/v/// chitra192 html
Fan Chung. Laplacians and the cheeger inequality for directed graphs. Annals of Combinatorics, 9:1-19, 2005.
13

---

Published in Transactions on Machine Learning Research (11/2025)
Haoyi Fan, Fengbin Zhang, Yuxuan Wei, Zuoyong Li, Changqing Zou, Yue Gao, and Qionghai Dai. Het- erogeneous hypergraph variational autoencoder for link prediction. IEEF Trans. Pollern Anal. Mach. Intell, 44(8):4125 4138, 2022. doi: TAL10//TPAMML22223555511 URL https:///oi.oon 1109/
TPAMI 3059833
Song Feng, Emily Heath, Brett A. Jefferson, Cliff A. Joslyn, Henry Kvinge, Hugh D. Mitchell, Brenda Praggastis, Amie J. Eisfeld, Amy C. Sims, Larissa B. Thackray, Shufang Fan, Kevin B. Walters, Peter J. Halfmann, Danielle Westhoff-Smith, Qing Tan, Vineet D. Menachery, Timothy P. Sheahan, Adam S. Cock- rell, Jacob F. Kocher, Kelly G. Stratton, Natalie C. Heller, Lisa M. Bramer, Michael S. Diamond, Ralph S. Baric, Katrina M. Waters, Yoshihiro Kawaoka, Jason E. McDermott, and Emilie Purvine. Hypergraph models of biological networks to identify genes critical to pathogenic viral response. BMC Bioinform.. 22 (1):287, 2021. doi: 10.1186 N0.1186/S12859-11 11111///522299002--1111777 021-04197-2. UtLpttts:: //doi. org/10. 110011////116-000--0011--------1
Yifan Feng, Haoxuan You, Zizhao Zhang, Rongrong Ji, and Yue Gao. Hypergraph neural networks. CoRR, abs/1809.09401 2018. URL http://arxiv org/abs/1809
Guoji Fu, Bo Yuan, Qiqi Duan, and Xin Yao. Representation learning for heterogencous information networks via embedding events. In Tom Gedeon, Kok Wai Wong, and Minho Lee (eds.), Newral Information Processing 26th International Conference, ICONIP 2019, Sydney, NSW, Australia, December 12- 15, 2019, Proceedings, Part I, volume 11953 of Lecture Notes in Computer Science pp. 327-339. Springer, 2019. doi: /L.1007/978-3- 0177783-030-3670000 36700--677------ 4' 27. URL https://doi..rgs 1007/978 3- 00--000033767 4_27
Valerio La Gatta, Vincenzo Moscato, Mirko Pennone, Mareo Postiglione, and Giancarlo Sperlí. Music recommendation via hypergraph embedding. IEEE Trans. Neural Networks Learn. Syst., 34(10):7887 7899, 2023. doi: 20.1099/NNNLSS.222..11...
URL https://doi.org/// http://0d...rr/111111///////////
3146968,
Benyamin Ghojogh, Fakhri Karray, and Mark Crowley. Eigenvalue and generalized cigenvalue problems: Tutorial. CoRR, abs/ (bs/1193.111 11240, 2019. URL http:://aaxiii/
11240
Gene H. Golub and Charles F. Van Loan. Matria Computations, Third Edition. Johns Hopkins University Press, 1996. ISBN 978-0-8018-5414-9.
Jacopo Grilli, György Barabés, Matthew Michalska-Smithh and Stefano Allesina. Higher-order interactions stabilize dynamics in competitive network models. Nature, 548(76666):10 211-211,, 2017.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Balaji Krishnapuram, Mohak Shah, Alexander J. Smola, Charu C. Aggarwal, Dou Shen, and Rajeev Rastogi (eds.), Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 19-17, 2016, pp. 855 864. ACM, 2016. doi: 01114//993967..2020 https://doi. .eria.orr//// 10. 1111119996661.22222 2939754
URL
William L. Hamilton. Graph Representation Learning. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, 2020. ISBN 978-3-031-00460-5. doi: 10.2200/ /200//00005551111122200022222220
WWL.EEDDDVVVYY200AAAAA... URL
Matthias Hein, Simon Setzer, Leonardo Jost, and Syama Sundar Rangapuram. The total variation hyper- graphs- learning on hypergraphs revisited. In Christopher J. C. Burges, Léon Bottou, Zoubin Ghahramani, and Kilian Q. Weinberger (eds.), Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, neurips.
2013, Lake Tahoe, Nevado, United States, pp. 2427 2435, 2013. URL
Roger A. Horn and Charles R. Johnson. Matriz Analysis, 2nd Ed. Cambridge University Press, 2012. ISBN 9780521548236. doi: 10.1017/CB009781130000000 URL
Jie Huang, Chuan Chen, Fanghua Ye, Weibo Hu, and Zibin Zheng. Nonuniform hyper-network embodding with dual mechanism. ACM Trans. Inf. Syst., 3833):28:1-288: 188:188 2020. doi: 10.1145/3388924 URL
https://doi. http:///bo.oo//1111111100 1r1//11..14///3899944
14

---

Published in Transactions on Machine Learning Research (11/2025)
Yuchi Huang, Qingshan Liu, and Dimitris N. Metaxas. Video object segmentation by hypergraph cut. In 2009 IEEF Computer Sociely Conference on Computer Vision and Pallern Recognilion (CVPR 2009), 20-25 June 2009, Miami, Florida, USA, pp. 1738 1745. IEEE Computer Society, 2009. doi: 10.1109/ CVVPR.000.52067790 URL https: org/10 10. 1109//100PPC 5206795
Jürgen Jost and Raffaella Mulas. Hypergraph laplace operators for chemical reaction networks. Advances in mathematics, 351:870-896, 2019.
Giorgios Kollias, Shahin Mohammadi, and Ananth Grama. Network similarity decomposition (NSD): A fast and scalable approach to network aligument. IEEE Trans. Knowl. Dala Eng., 24(12):2232 2243, 2012. doi: 10000//KDEE......7...7 URL httpps://dii org/10. 1111//DDEE.. www.EE.EE......... 2011. 174
Jianbo Li, Jingrui Hc, and Yada Zhu E-tail product return prediction via hypergraph-based local graph cut. In Yike Guo and Faisal Farooq (eds.), Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery 8 Data Mining, KDD 2018, London, UK, August 19-23, 2018, pp. 519-527. ACM, 2018. doi: 10.1145/3219819 12111///3219999.211922... URL httpps///oi..oo http://......./.....//.... 1ttp://...111//2221 01..00..115///21111 3219829
Pan Li and Olgica Milenkovic. Submodular hypergraphs: p-laplacians, cheeger incqualities and spectral clustering. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässun, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 3020 3029. PMLR, 2018. URL htttp://rocceeding/g mlr. ww.pppssss////epp 1110e. html
Canwei Liu, Tingqin He, Hangyu Zhu, Yanlu Li, Songyou Xie, and Osama Hosam. A survey of recommender systems based on hypergraph neural networks. In Meikang Qiu, Zhihui Lu, and Cheng Zhang (eds.); Smart Compuling and Communication. 7th International Conference, SmariCom 2022, New York Cily, NY, USA, November 18-20, 2022, Proceedings, volume 13828 of Lecture Notes in Computer Science, pp. 95 106. Springer, 2022. doi: (0.1007/978-3-001-281 031---2---2122-2-2
10. URL https: http://....ogg/..100/0100 org/10.1007/
Huifang Ma, Di Zhang, Weizhong Zhao, Yanru Wang, and Zhongzhi Shi. Leveraging hypergraph random walk tag expansion and user social relation for microblog recommendation. In IEEE International Conference on Data Mining, ICDM 2018, Singapore, November 17-20, 2018, pp. 1158 1163. IEEE Computer Society, URL
2018. doi:
http://......//.....o.oo/o.../.. 2011000012
Raffaella Mulas, Danijela Horak, and Jürgen Jost. Graphs, simplicial complexes and hypergraphs: spectral thoory and topology. In Higher-order systems, pp. 1-58. Springer, 2022.
Alicia Gorosiis Djordje Bajić, Melisa L Osborne, Juan F Poyatos, and Alvaro Sanchez. High- order interactions distort the functional landscape of microbial consortia. PLoS Biology, 17(12))e3005550 2019.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Trons. Pattern Anal. Mach. Intell,, 22(8):888 905, 2000. doi: 10.1109/34 001///34.....8.... URL
1wtp://...10//4...ee. 868688
Xiangguo Sun, Hongzhi Yin, Bo Liu, Hongxu Chen, Qing Meng, Wang Han, and Jiuxin Cao. Multi-level hyperedge distillation for social linking prediction sparsely observed networks. In Jure Leskovee, Marko Grobelnik, Mare Najork, Jie Tang, and Leila Zia (eds.). WWW '21: The Web Conference 2021, Virtual Event/ / Ljubljana, Slovenia, April 19-23, 2021, pp. 2934-2945. ACM / TW3C2, 2021. doi: 10.1145/ URL https:://dol /ttt::://doi.oo//10. /115/1444281.
Yuuki Takai, Atsushi Miyauchi, Masahiro Ikeda, and Yuichi Yoshida. Hypergraph clustering based on pagerank. In Rajesh Gupta, Yan Liu, Jiliang Tang, and B. Aditya Prakash (eds.), KDD 220: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23-27, 2020, pp. 1970-1978. ACM, 2020. doi: 011144/3394466.4400 11 1145/3394486. 3403248.
URL https://doi.org/
15

---

Published in Transactions on Machine Learning Research (11/2025)
Hanghang Tong, Christos Faloutsos, and Jia-Yu Pan. Fast random walk with restart and its applications. In Proceedings of the 6th. IEEE International Conference on Dala Mining (TCDM 2006), 18-22 December 2006, Hong Kong, China, pp. 613 622. IEEE Computer Society, 2006. doi: 10. D0.1109/ICIDM.2006.11 URL https://dol /ww. org/ 10. 1109/ICDMM 2006.70
Yanbang Wang and Jon Kleinberg. From graphs to hypergraphs: Hypergraph projection and its remediation. arXiv preprinl ar Axi:24411008111 2024.
Longean Wu, Daling Wang, Kaisong Song, Shi Feng, Yifei Zhang, and Ge Yu. Dual-view hypergraph neural networks for attributed graph learning. Knowl. Based Syst., 227:107185, 2021. doi: J.KNO/J. 2021.107185. URL stttps://dol.. /ttp::///ooo..o//1./o 1016//.0016/ knosys 10221.117111
Liqiao Xia, Pai Zheng, Xiao Huang, and Chao Liu. A novel hypergraph convolution network- based approach for prodicting the material removal rate chemical mochanical planarization. J. Intell. Manuf. 33(8):2295 2306, 2022. doi: 10.107/$10645-02-0177444 URL fttts:://doi.orr/100..o
610845-021-01784-1
Naganand Yadati, Madhav Nimishakavi, Prateek Yadav, Vikram Nitin, Anand Louis, and Partha Talukdar. Hypergen: A new method for training graph convolutional networks on hypergraphs. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d'Alché-Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Newral Information Processing Systems 32: Annual Confer- ence Neural Information Processing Systems 2019, NewrIPS 2019, December 8-14, 2019, Vancou- ver, BC, Canada, pp. 1509-1520, 2019. URL https://proceeddin neuteitppnnnn............ sea.rippscc/pppor/011/////
Befe3bbaaadd333001116666333333 -tt.:ossss..94ba--attrtt....... Abstract.
Jacwon Yang and Jure Leskovec. Defining and ovaluating network communities based ground-truh. Knowl. Inf. Syst., 42(1):181-211 2015. doi: 10.1007/$101155-13--0000 013-0693-.. URL https://doi.org: http///ooo.rr//1..
1007/s10115-013-06533
Dengyong Zhou, Jiayuan Huang, and Bernhard Schölkopf. Learning with hypergraphs: Clustering, clas- sification, and embedding. In Bernhard Schölkopf, John C. Platt, and Thomas Hofmann (eds.), Ad- vances in Newral Information Processing Systems 19, Proceedings of the Twentieth Annual Confer- ence Neural Information Processing Systems, Vancouver, Brilish Columbia, Canada, December 4-7, 2006, pp. 1601 1608. MIT Press, 2006. URL https://proceeddngss htwpeedddnnn.eerrs..ccceeeeeeeee http:://www.....//////////////// dFF86r2ac333155445eeee2222222222 Absaaaaaaaa229---taaataaaa. Abstract html
Lei Zhu, Jialic Shen, Hai Jin, Ran Zheng, and Liang Xie. Content-based visual landmark scarch via mul- timodal hypergraph learning. IEEE Trans. Cybern., 45(12):2756 2769, 2015. doi: 10. 10.1109/TCYB.2014
2383389. URL https://doi org/10. 1109/TCYB. 2014. 2383389
Yu Zhu, Ziyu Guan, Shulong Tan, Haifeng Liu, Deng Cai, and Xiaofei He. Heterogeneous hypergraph embedding for document recommmnattiinniioono Newrocomputing, 216:150-100 162, 2016. doi: 10.1016/I.EEUOO... 2016.07.085 030. URL ottp: www.:/...............m.......... 2016.07.2... 07.6007.030
16

---

Published in Transactions on Machine Learning Research (11/2025)
A Supplementary Definitions, Proof of Lemmas and Theorems
A.1 Definition of Hyperpath and Hypergraph Connectivity
Definition 22. [Zhou et al, 2006) (Hyperpath and hypergraph connectivily). We soy there is hyperpath between vertices U1 and Uk when there is sequence of distinct vertices and hyperedges v1, 02 62, ... Ck-1, such that vi E 6 and 1++1 E e4 for 1 S < k 1. A hypergraph H is connected if there exists a hyperpath for any pair of vertices.
A.2 Proof of Definition 6 that P has row sum
Proof. The sum of the th row of P is:
w(e)
Te(u)
Σ Po.= -
(30)
d(o) d(e)
eE
Since H connected, there exists e E Elu) and therefore,
w(c)
Σ Te(u)
w(c)
Po.u- Σ CEB(v)
Σ
(31)
d(v)
8(e)
d(r)
cEB(v)
A.3 P is Irreducible
Lemma 23. The transition matria P of hoperryrahh random walk defined in definition 0 is irveducible.
Proof. First, we create a new matrix Q by replacing Pu,, by 1 if Pa,y > O, and prove that Q is irreducible. Hence, P holds the same feature.
By the assumption that the undirected hypergraph H is connected, every node is reachable from any node A through sequence of hyperedges. Qu, = 1 if and only if Pa. > 0.
By the definition of P.
w(e) ye(v) d(u) 8(e)
Pu.v Σ
(32)
eEE(v)
if there is hyperedge connecting and Therefore, the directed graph G with Q as the adjacency matrix can be constructed by replacing every hyperedge with a directed fully-connected clique.
For any node pair u u, by the assumption of H, there exists a sequence of hyperedges from v to u; hence, G, there also exists a sequence of directed edges from e to u. This means G strongly connected, and Q is irreducible, According Theorem 6.2.44 in Matrix Analysis (Horn & Johnson, 2012), P is irreducible. 3
A.4 Proof of Theorem g
Proof. According to the Perron-Frobennus Theorem and Lemma 23 the irredueible matrix P has a unique left. eigenvector with all entries positive. We denote and normalize this row vector as & and prove oP Φ + pT = According to the definition of Φ,
pd Th p(P)
(33)
17

---

Published in Transactions on Machine Learning Research (11/2025)
where p(P) is the spectral radius, which is the maximum eigenvalue of p(P).
V
M Σ
PP)
xP)
Σ
(1)
i=1
==1
MI
IV
V
M
Σ
T
(
P
(34)
==
==1
t=1
VI
Σ o"
(j)
Therefore, & satisfies p o, Vu p(u) 0 and Σn b(u) = 1.
A.5 Additional Lemma to Support Landom-walk-basedd Hypergraph Laplacian (Definition 9)
Lemma 24. For graph 9 with pair-wise relations, let D be its degree matrix and A be its adjacency matria. -1 be the transition matriz of graph random walk, and 1Ig be the stationary distribution of Pg. Then 1lg P P Ilf has the same eigenveclors as the graph Laplacian Lg D A.
Let Pg = 1-1
2
Proof. This lemma serves as an evidence that
L II + PI
(35)
2
can be degenerated into unweighted non-hyper graphs (graphs with only pair-wise relations). For pair-wise d(a)
graphs, given Pg (AD-1) = D D-1 AT = DD-A, we have dg(uu) = Σ. d(v)
because,
V oo) Σ
IV Po(i,)) ((()) = Σ
Ai
d()
Σ Aij
VI
d(i)
(36)
d()) En d(u)
Σ, d(r) Σ, d(v)
1=1
==1
Hence,
D Bg E.d(v)
(37)
Therefore, for regular graphs, follow the same definition of hypergraph Laplacian as of equation 35
DD-1A AD-ID D-A
L E. d(v)
(38)
2 d d(v)
E.d(v)
which has the same eigenvectors as the regular graph Laplacian D A.
A.6 Proof of Theorem 15
Proof. Notice that when x" AAr is scalar,
x² Ax (x Ax)" = =TAA. AT
(39)
substituting A IIP, we have
T TTP xT FPp TT Tla
(40)
18

---

Published in Transactions on Machine Learning Research (11/2025)
Also note that
E = P (u))(u)
=
>
(41)
Σ (v))(())) Σ )v((v) Σ ((u) Definstion Σ (t)((e)
Then,
R(x) = Emp(olu) - x(t)))=b(u)PP (() x II
Enp x2 (u) + En, (v)o(u) - -m (())
x² Il
(2) + E. (v)((()) - 2 xJJ IIPx
Equation
x r-Il
(42)
Equation 40
2x Hr 2.
+ x- lIx)
Ia
x² (II
IP+P II
x
2.
2
x²x ILx 1L
Definition
x" Lx 2. x: "'
A.7
Proof of Theorem i
Proof. For a partition SUŠ=V: v,5 = 0, we have [V] x vector s(u), where
PoliSi [o](S]
if S
(u)
(43)
[
i
(S)
19

---

Published in Transactions on Machine Learning Research (11/2025)
From the definition of NCut in Eq 16 we compute R(æ) as follows:
R(x) = En,o (x(u) x(v)? ((u)
En [(()] 2 ((u)
E (ESSswES VES) [S] vol(S)
(o)(S) nol(S)
2) ((u))a,v
Eves
((u) + Enes vols d(u)
vols
volS+ + +olS+volS vo18
LI (u(u) Pa.e
voiS
voIS E (u))
vots vots
Q()
volS+volS vo18
E uES ((()) Pu,v + EuES, p(u) Puw)
nolS
(44)
volS val.S
Σ WES p(u)
+ vols vo18
EuesØ(u)
pooS++ vol
gillS tooS
)2 Σ EuES.VES (b(u) P
valS
volS
v
Σ HES ((u) +
pois
Σ ((u)
volS
nots
2(volS volS)
EnES,NES =bu)) Pu.
hot5
volS
vels volS
Eues o(u) +
vols volš
Eves ((u)
2(volS + NCCt)))
volS + volS
2NCut(S.S)
A.8 Proof of Theorem 19
Proof. Recall from the definition
18 and 13
the numerator and denominator are both non-negative, and
|oS|
|os|
((S)
(45)
min(vol(S), vol(S))
min(vol(S), co))(
Since |as| S col(S),laS} < vS)( 0 5 Φ(S) <
min(vol( .rol)) min(vol(SS).oll 1.
A.9 Proof of Theorem 3
Proof. From Theorem 15
LL La
1
X = min
min =ER"\(0)
7 R(x))
(46)
(() "Ir
s if u E
Let S = arg gin (S'',, v(u) =
then continue with Equation 46
ST otherwise
20

---

Published in Transactions on Machine Learning Research (11/2025)
1 [((x)
A min (0R
2
R(y)
1 En, (u(u) -
En (Q)
Σ VES (y(u) (u))PP(u))P un + Eues (u(n) Pp())
2
Eves ( + +ness (u(u)
Eves,ves vol(S) 1- --vol(s) (2 EuES, [S) vol(s) )
EveS vol(S) (0(()) + EnEE 1-00((37 (0((u)
(47)
)2 (uUES,EES ((u) + EnEs,res ((u)Pu..)
1
(S)(() +
1 vol(s)
(Vo Enes p(u) (I-vol,s7) )2 Eves (uu)
1
jS
)2
US) 1 vol(s)
(o)( (voo(S) + (1 )2 vol(S))
jas]
vol(S)( - vS)
(1)o(()
2|85|
min(vol(S), -
(²H
Thus, the LFS has been proven. For the RHS, assume w is the eigenvector of the normalized Laplacian associated with X, let vector III w.. Then,
Af(u)o(u) = A(II (w)())((u) = (II 2 Logi (u))(()) = (IIII 1 & Lygm w) (u)
-IT Lagm 12 (()) (L))(u) [III IIP 11++P* PT Ml(u)
o(u)f(u) E. ((U)((u)P
E. (v)
(48)
2
E((()) f(v))((l)) + ((.)).,))
2
Therefore, Yu
- (())()))) + (u,) 2f(u)o(u)
A =
(49)
f(u), if f(u) .ten
Let V4 (u: f(u) 0} and let vector g(n)
0, otherwisc
X = Ever, f(u) (((())))(())()))))))))) + P(.)
Evey_ (w)2
Everg(u) E,(((u) ((o)) + Po.) Swer2g(u)=00)
(50)
Eng(u) E, (g(u) - ((v))(((T) P + (un)Pu,) E. (,22(()2(())
We resort the vertices in V such that f(v1) 2 f(02) 2 2 f(ep)) Also, can change the direction of w that Estweo Φ(u) 2 Extnzo d(u).
21

---

Published in Transactions on Machine Learning Research (11/2025)
From the definition of ((H) minsgv ((S) mii(ual(S).eol(5))) for every i such that f(e)) 2 0,
88
((H)= < Exciel Pu $(H)
Σ o(1s) S
Σ
(51)
(11))
55
kSiKi
One can validate that
(((()) E((u) ((t))( + Pan) = ΣΣ (o(u) g(u)))((t)PPps
(52)
Continue with Equation 50 with Theorem 3 in CChung 2005
2 Σ, (g(u)) - g(t))
Σn 2g(u)2((())
(. - ((0))
Σn ( (o( - ((u))) Pu
(2n En g())² - ((u))
(53)
E [ug(u)p(())
Ex Eis)(((n)) 8( (o(x)) v.) ((v)) P(kk, n)))²
8 E. ((u)
Ex(o(v))² - g(v++1)
Plo
8 S.
Using Equation
51
continue with Equation 53
x g(v++1) (ose))))eeeee(oPPPsss)0))))))))
8(E, g())2((u))
(x(o(v)) g(vN+ 1( (H) Eiso o1::))2
8(E, (())²((u))²
)(H) ((v)) Σ (()))()))>- -ggggg-u+ ((
(54)
g(u)o(()))
'(H)²
gu))((())
((H)²
2
B Algorithm Complexity
B.1 Worst-case Time Complexity of HyperClus-G
The pseudo-code of HyperClus-G is given in Algorithm [ Assume have direct access to the support of each %e. Assume the number of hyperedgo-vertex connections is m, which is the sum of the sizes of the support sets of all Te.
The computation of R and W takes ((m). The constructed R and W both have m non-zero entries. The construction of Dy takes O(D)) and the construction of De takes O((E).. Given that each hyperedge has at least 2 vertices and each vertex has at least one hyperedge incident to it, step 1 takes O(m).
Given that W and both have m non-zero elements, the multiplication P D''WD=' RR takes O(m?)
using CSR format sparse matrix. Therefore step 2 takes 0(m²).
22

---

Published in Transactions on Machine Learning Research (11/2025)
Computing the stationary distribution @ of P takes O(12)) using power iteration. Constructing the sta- tionary distribution matrix II from takes O(1))). Computing the random-walk-base hypergraph Laplacian takes O(V)). Therefore step 3 and step 4 takes O(1))).
Step 5, computing the eigenvector associated with the second smallest eigenvalue, takes 0(111)) And step takes O(V))- Therefore step and step 6 together take ((1))))
Therefore the worst-case complexity of HyperClus-G is
(mm) + + 0(121) + +(IM)) + 1213)
(55)
B.2 Worst-case Space Complexity of HyperClus-G
We make the same assumption as in Section B.1 The storage of R. W, Dy, Dg takes O(m). The storage of P and takes 0(IV2). The storage of stationary distribution and the intermediate results takes ((V)). The intermediate results for eigendecomposition take O(IV)²).
Therefore, the worst-case space complexity for HyperClus-Gi is
((m) + +(1))) + + 0(V13) 0(m + (V]?)
(56)
In our experiments, the largest dataset Covertype's GPU usage is Gigabytes.
C Experiemnt Details
C.1 Environments
We run all our exporiments on a Windows machine with 13th Gen Intel(R) Core(TM) 19- 19-13900H CPU, 64GB RAM, and an NVIDIA RTX A4500 GPU. One can also run the code Linux machine. All the code of our algorithms is written in Python. The Python version in environment is 3.11.4. In order to run our code, one has to install some other common libraries, including PyTorch, pandas, numpy, scipy, and ucimirepo. Please refer to our README in the code directory for downloading instructions.
C.2 Datasets
Table 10 Bunmarizes the statistics and altributes of each dataset we used in the experiments.
includes categorical descriptions of 8124 mushrooms in the Agaricus and Lepiota Family. Each species labeled as edible or poisonous. This dataset contains missing data the "stalk-root' feature. As (Zhou el al. 2006) did, we removed the feature that contains missing labels. The two clusters have 4208 and 3916 instances, respectively.
Mushroom (uttps://archive.iis wwt.:iiiss..iii..i. wwrssuui.eeduuue wcc..cct//ds..eee////mmsrooooo
Rice /https://archiiee ics uui. and Osmancik). A total of 3810 rice grain's images were taken for the two species, processed, and feature inferences were made. 7 morphological features were obtained for each grain of rice. This dataset does not have missing data. The feature types are real, including integer values, continuous values, and binary values. The two clusters have 2180 and 1630 instances, respectively. For each contimuous feature, we first find the maximum value this feature, then normalize all the numbers in this feature by the maximum value. This results in 10 bins of equal size [0, 0.1], (0.1, ...))...(0..9. 1]. Then, we convert the quantified bins to categorical features by using categorical feature to mark which bins continuous value originally belongs to.
a.k.a., Rice (Cammeo
a.k.a., Car Evaluation. Originally, this dataset contained 1728 cars with labeled acceptability related to 6 features. This dataset does not have missing data. We extract all the cars that are labeled "good" or "vgood' (very good) and construct a smaller dataset 134 cars. The two clusters have 65 and 69 instances, respectively.
Car (https://archiv) ics. uci wat.://atasete/////aaaaaaaaaaaaa
Digit-24 a subset of Digit (attps://archive. ics uci htt.://c//aaaatte///////paaaaaaa handwrit ttteuriitttttdisss.... a.k.a. Optical Recognition of Handwritten Digits. This dataset contains matrix
23

---

Published in Transactions on Machine Learning Research (11/2025)
of 8x8 where each element is integer in the range O, 1, ... 16. This reduces dimensionality and gives invariance to small distortions. This dataset does not have missing data. The original Digit datasets have 10 classes, and we extract all the instances of numbers 2 and 4 to construct Digit-24 for 2-way clustering. We simply regard the integer feature type to be categorical, that cach integer is one category. The number of instances each digit class approximately the same.
The task of this dataset is the classification of pixels into 7 forest cover types based attributes such elevation, aspect, slope, hillshade, soil-type, and more. We follow (Hein et al., 2013) and extract the instances of classes 4 and 5 to construct dataset for 2-way clustering. The numerical feature values in this dataset can vary within large range. Therefore, we first quantize the numerical values into 10 bins of equal size. We use the same strategy as described in the Rice dataset above to convert the features into categorical features. The two clusters have 9493 and 2747 instances, respectively.
Covertype (https://archive.. ics. wtt.:ic.......datttaeeeeeeeeeeee htt..///ddaaaeee//////errrpppppp
Zoo (https://archive.iee www.ci........ooooooooooo....cce www..cii.uuuuu. .et.///aaaaaeee/////ooo is simple database containing 17 Boolean- valued attributes. We simply regard the integer feature type to be categorical, that each integer is one category. The seven clusters of instances have 41, 20, 13, 10, 8, 5 and 4 instances, respectively.
Wine-567 (attps://archive ics uci www.edddddaaaa http://aaaassee/////aeeeaaaalaaa of this dataset is to model wine quality based on physicochemical tests. In the original dataset, each instance has a quality score between to 10. The majority of instances have scores 5, 6, or 7. We extract all the instances that have scores 5, 6, or to construct our Wine-567 dataset for 3-way clustering. We quantize the real feature values described in the Rice dataset above, except that the number of bins is 20 instead of 10. The three clusters of instances have 2836, 2138, and 1079 instances, respectively.
a.k.a., Wine Quality. The goal
Letter (https: ics. uci
htt.aa/ee/./epop.aaaaaooooooooro iarpilonnooohhnvovoo thanwrrittonndigitta.
a.k.a. Letter Recognition, which is a database of character image features, aiming to identify the letter. We extract all the instances of numbers 2 and 4 to construct our Letter datasct. The objective is to idontify each of a large number of black-and- rectangular pixel displays as one of C, I, L, or M. The number of instances in each letter class approximately the same. We simply regard the integer feature type to be categorical, that each integer is one category.
Table 10: Statistics of Constructed Hyporgraphs in Global Partitioning Experiments
Hypergmah
[V]
[8]
Evey E(v)
# classes
[8] clique
# original features
Subject Are
Feature Type
Mushrom
8124
111
162480
2
65891252
22
Biology
Categorical
Rice
3810
3838
17410
2
14272406
7
Biology
Real
Car
131
16
801
2
28821
6
Others
Categorical
Digit-24
1125
880
69750
69750
64
Computer Science
Integer
Covertype
12240
111
428400
149805360
52
Riology
Categorical, Integer
Zoo
101
36
1616
10100
16
Biology
Categorical, Integer
Wine-507
6053
136
60583
36630116
Business
Real
Letter
30:11
18701
8098180
Computer Scieuce
Integer
Digit
5620
348440
10
31578780
Computer Science
Integer
Table 10 shows the statisties of our datasets used in the global partitioning experiments. The meanings of columns are the name of the hypergraphs, number of pertices/instances number of hyperedges, number of hyperedge-vertex connections, number of classes, number of edges in the clique expansion graphs, number of original features in the dataset, the subject area of the dataset, and the types of features.
C.3 Global Partitioning Metrics
The F1 score between two sets Au and Ae is defined as
24

---

Published in Transactions on Machine Learning Research (11/2025)
TP Positive) = Am n Adl
FP (False Positive)
Am \ Ac
FN Negative)
LA \ Am
TP
precision TP+
(57)
TP
recall TP+
F1 2 x precision x recall
precision recall
Assume for k-way clustering (in this section, k can be 2), the algorithm returns the result S1, S2, Sk, then the NCut value is computed as
k |
k Enes,nEs ((u) vol(S)
N1 S&)
10,
(58)
vol
Assume the actual labeled classes are V1, V2..... ... Vk, where V; all the vertices in class i. We first compute the F1 scores between S; and V, for j E (1, -.. k,,,, then greedily match the resulted sets with the actual labeled classes (Kollias et al. 2012 For example, if we have three classes with the F1 matrix, where Fi-15-1 is the F1 score of S; and V;
Specifically, for 2-way NCut, we have another equivalent Definition 16
0.9
0
F
0.8
0
(59)
0.7
0.6
Then, we first match S with V22 because they have the highest F1 score of 0.9. Then we match 82 with Vi because they have the second largest F1 score of 0.8. Then we try to match Sa with V/ because they have a third largest Fl score of 0.7, but V/2 has already been matched with S3, so we cannot match it again. Then, we try to match S3 with V/8 and this time none of Sy and V2 has been matched. As all the sets have been matched, the greedy-match algorithm ends.
We calculate the weighted Fl score as the final metric of clustering. For each match S3, with Vi, we weigh its F1 by number of instances in Vr,
|1 Pi=1
W eighttdd F1
F Fj,
15-1.-11
E [0
(60)
Vi
C.4 From 2-way Clustering to k-way Clustering
We have two strategies from 2-way clustering to k-way clustering. For the datasets that each actual labeled class has a similar number of instances, apply 2-way clustering on the largest cluster every time to split it into two clusters. For k-way clustering, this process calls the 2-way clustering k-1 times.
When the number of instances in each actual labeled class varies a lot, when we have clusters, we call 2-way clustering on each cluster to get (+1 clusters, then pick the best of / results in terms of NCut. For k-way clustering, this process calls the 2-way clustering k(k-1) times.
Another promising future direction to develop a direct spectral analysis for the k-way case. This, however, involves non-trivial technical challenges and lies beyond the scope of the present work. We note that such an extension should also draw inspiration from analogous results in graphs, such the k-way NCut formulation.
25

---

Published in Transactions on Machine Learning Research (11/2025)
Definition 25 (k-way Normalized Cut). Let H WW,), be EDVW hypergraph with stationary distribulion & and transition matrir P. For any k-way partition (Si,..., Sk} of V inlo non-emply disjoinl. subsets, the k-way normalized cut (NCut) is defined as
Σ WE NES,
d(u)
|as|
SI.,
(61)
Σ ((u)
where (S,) Enes, p(u) is the slationary volume of cluster St, and |oS;| = Eues. (()) denoles the boundary volume between S₁ and its complement.
C.5 Baselines
CLIQUE++. For each hyperedge e, each u E e with + v, we add an edge wv of weight w(e). Then, compute the adjacency matrix A and degree matrix D. We calculate the graph Laplacian matrix by L= D D A. Finally, we do eigen-decomposition for the random walk Laplacian Law D-*L, whose eigenvalues are associated with the graph NCut value (Hamilton 2020). We calculate the eigenvector associated with the second smallest eigenvalue for global partitioning: we put the non-negative entries as one cluster and the negative entries as another.
For each hyperedge e, we introduce a new vertex Ve- For each vertex E e, we add an edge we of weight w(e)/lel. After converting the hypergraph into star graph, we do the same algorithm for global partitioning as in CLIQUE++.
S
DiffEq Takai et al. 2020 We directly use the official code of this algorithm. This method sweeps over the sweep sets obtained by differential equations for local clustering. For global partitioning, it simply calls local clustering for every vertex and returns the best in terms of conductance. Originally, this algorithm could only take one starting vertex for local clustering. We modified the code to add one additional vertex that connects the starting verticos in each observation. Then regard the newly added vertex as the starting verlex, so that can oblain the local cluster for the given 5 starting vertices.
node2vec (Grover & Leskovec 2016). node2vec embeds a graph using random walks. Since have the random walk matrix P on the hypergraph, we construct a directed weighted graph by P as the input of node2vec. However, given that there are too many non-zero entries in P, node2vec is extremely slow. Therefore, after we get P, we only keep the entries P that are larger than a small threshold. This threshold is tuned so that the (1) execution time is acceptable; (2) the NCut value and F1 value of the result are both near convergence. We did not modify other default hyperparameters in node2vee. After obtain the vertex embedding, we call KMMaan from scikit-learn to directly obtain k clusters for k-way clustering.
event2vec/ wvent2vec/hyperedgee/ 2ee Fu et al. 2019 We directly use the official of this algorithm. event2vec was originally designed for heterogeneous graphs. For example, in a citation network that has publications and authors, each publication is an event. We notice that here an event is equivalent to a hyperedge. We first convert the hypergraph into a STAR graph, then we rogard each added vertex as an event and call 2vec to obtain vertex embeddings. We tune the training epochs near default so that (1) execution time is acceptable; (2) the NCut value and Fl value of the result are both near convergence. We did not modify other default hyperparameters in event2vec. After obtain the vertex embedding, call KMeans from scikit-learn to directly obtain k clusters for k-way clustering.
htte:
based_on_ on_PagnRank
26

---

Published in Transactions on Machine Learning Research (11/2025)
C.6 Supplementary Experiment Data
C.6.1 Standard Deviations of Nondeterministic Algorithms on Global Partitioning
We report the standard deviation of nondeterministic algorithms on global partitioning. The nondeterminis- tic algorithms are node2vec + kmeans and hyperedge2vec kmeans. The standard deviations of the NCut are reported in Table 11 and those of the F1 scores reported in Table 12
Table 11: Standard Deviations of NCut on Global Partitioning Task.
2-w Clustering
w-y Clustering (k
Method
Mushroom
Rice
Car
Digit-24 Covertype
Zoo
Wine Letter Digit
node2vee
le-5
0.049
0.006
le-4
le-5
0.014
0.001
0.046 0.039
hyperedge@vec
0.002
0.038
0.006
0.001
0.024
0.008
0.026 0.017 0.009
Table 12: Standard Deviations of F1 scores Global Partitioning Task
2- way Clustering
k-way Clustering (k >
Method
Mushroom
Rice
Car
Digit-24
Covertype
Zoo
Wine Letter Digit
node2vee
le-5, le-5 0.056, 0.054 0.032, 0.031
7e-4, 7e-4
0.027, 0.024
0.023
0.001
0.078
0.079
2y 0.196, 0.197 0.110, 0.109 0.174, 0.171 0.050, 0.050 0.124, 0.129
0.046
0.010
0.060
0.006
C.6.2 Time Comparison on Global Partitioning
The execution time of all the methods is reported in Table 13 Our HyperClus-C outperforms the baseline methods on 8/9 datasets. Note that DiffEq is written in C# while others are written in Python. may not be fair comparison since C# is of the fastest. programming languages, but we still report the total execution time (including compiling) of all the algorithms for reference.
After STAR+ expansion, the dimension of the matrix gets larger because we need to introduce additional vertices into the graph. For CLIQUE++ expansion, since we convert the hyperedge to the fully connected CLIQUE graph, the conversion itself makes the program slower. Also, the random walks and calculation of Laplacian will be slower compared to HyperClus-G. G. DiflEq finds the global partition by actually finding local cluster and taking its complementary set. As the graph becomes large, sweeping over to find the local cluster will consume more time. node2vec and wenntt2eee/yypredgevee need to train the embedding model, which consumes much time. We have tuned the number of training epochs to let the model stop near convergence.
27

---

Published in Transactions on Machine Learning Research (11/2025)
Table 13: Execution Time Comparison (V) Global Partitioning Task (unit: seconds).
2-way Clustering
b-way Clustering
Method
Mushroom
Rice
Car
Digit-24 Covertype
Zoo
Wine
Letter
Digit
STAR + expansion
72.82
50.80
1.43
3:37
318.55
0.654
32 18
37.34
59.05
CLIQUE++ expansion
216.04
13.32
1.38
7.50
1099.03
0.629
77.75
50.25
297.37
DiffEq (C#)
39.03
8.15
1.43
18.36
149.49
8.79
33.09
20.94
613.22
node2vec kmeans
101.05
73.08
3.54
12.63
175.58
2,238
39.66
32.68
48.59
hyperedgeévee kmeans
88.96
47.03
5.59
20.29
367.53
4.62
28.40
113.33
Hyper Clus-G(Our))
17.73
5.04
1.37
2.18
87.72
0.595
11.48
35.13
26.49
Tiet of Pyshon Baseltnes tnee ratio
CyperClleee
24.34%
37.83%
99.27%
64.69%
49.96%
94.59%
35.67%
123.7%
44.86%
28


Reviews:
[{"review_id": "dviCxpzNov", "reviewer": "Reviewer_K9i9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- To the reviewer's knowledge, this work presents some of the first results on spectral theory for EDVW hypergraphs.\n- The paper is well-motivated.\n- Empirically the proposed clustering algorithm (HyperClus-G) consistently performs well across several datasets and is on-par or outperforms other relevant methods.\n\n**Weaknesses**\n- The theory is limited to the $2$-way global partitioning case. It could be interesting to extend the theory to the case of $k > 2$-way global partitioning.\n- I think that there are certain aspects of the presentation that can be improved. For example, I think that the paper could benefit from a more in-depth discussion of how the current work improves upon prior work and what some of the main differences are in the results. This is discussed more in the requested changes.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper focuses on developing fundamental theory for hypergraphs, with a specific focus on the edge-dependent vertex weights (EDVW) model proposed in prior work. Specifically, hypergraphs are useful in modeling higher-order relations between groups and recent work has aimed to formalize hypergraphs that can capture such structure and design algorithms to learn them. However, as this work is nascent, this area lacks spectral theory akin to classical graph-based learning techniques. The present work aims to fill this gap by developing and analyzing the following notions for the EDVW hypergraph model:\n- Spectral theoretical notions, such as Rayleigh quotient, NCut, volume, and conductance\n- A clustering algorithm that is approximately linearly optimal for both NCut and conductance\n- A Cheeger inequality for EDVW hypergraphs\n- Empirics validating their approach, showing that their clustering algorithm improves performance.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Discussion with some results in (Chitra & Raphael, 2019)**\n\nIt would be beneficial to get a better sense of how some of the results in this work are different or improve upon those in prior work. For example, Theorem 5.1 in (Chitra & Raphael, 2019) also provides a bound on the least eigenvalue of the Laplacian while this work focuses on the second smallest eigenvector of the normalized laplacian. It would be good to more explicitly state the benefits of the new Theorem 3 and what are the advances potentially in terms of the proof technique, since both Theorem 5.1 and Theorem 3 use results from (Chung, 2005) to prove it. This discussion could also arise while defining the new Rayleigh quotient near Theorem 15.\n\n**Minor changes**\n- For the proof of Lemma 22, it would be better to make the $\\approx$ in (27) more rigorous by perhaps referencing/showing how NCut is big O of $\\lambda$\n- Some sections have no narrative text between Definitions, Assumptions, or results (e.g., Definition 6, 7 -> Theorem 8). It could help to add narrative text between these for improved readability.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "cLDkIHuEUy", "reviewer": "Reviewer_zoDJ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n- The theoretical core of the paper is strong, well-motivated, and impactful. The strength of the theoretical results presented in this paper is that they establish spectral techniques that can be used in the EDVW model proposed by (Chitra & Raphael, 2019).\n- Based on the EDVW hypergraph random walk theory, the paper presents an algebraic connection between Rayleigh quotient and Normalized Cut (Theorem 1), and proves the approximately linear optimality of the proposed hypergraph spectral clustering algorithm (Theorem 2). These results appear to be a good extension of spectral graph theory to EDVW hypergraphs.\n\nWeaknesses\n\n- A significant number of theoretical proofs need revision. Some proofs show elementary mistakes in formal logic, and there are unnecessarily verbose sections that require effort to enhance the expertise. The labeling of theorems is also cumbersome as one needs to move back and forth multiple times between the main text and the appendix while reading. Efforts are needed to improve the readability of the paper.\n- The proof of the Cheeger inequality presented in the paper borrows proof techniques from (F. Chung, 2005). This proof appears to tediously apply calculations used in the proof of the Cheeger inequality for weighted directed graphs corresponding to hypergraphs, as mentioned in (Chitra & Raphael, 2019) (Appendix A.9). In the reviewer's opinion, the authors should be more cautious about claiming that this aspect was \"non-proved\" in previous papers or that they have \"upgraded\" existing results. The reviewer recommends that the authors clearly articulate the specific differences between the Cheeger inequality proposed in this paper and the results in existing papers, and illuminate their relationship, which would be a better way to explain their contribution.\n\n[Chitra & Raphael, 2019] Random walks on hypergraphs with edge-dependent vertex weights. ICML, 2019.\n\n[F. Chung, 2005] Laplacians and the Cheeger inequality for directed graphs, Annals of Combinatorics, 9:1-19, 2005.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents spectral properties, clustering algorithms, and the Cheeger inequality for edge-dependent vertex weights (EDVW) modeling of hypergraphs. It establishes an algebraic connection between the combinatorial Normalized Cut optimization objective and the spectral Rayleigh Quotient of a random-walk-based hypergraph Laplacian. Based on this connection, it proposes `HyperClus-G`, a spectral clustering algorithm that is claimed to achieve approximately linear optimality for partitioning EDVW hypergraphs.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- (p2) I recommend introducing terminology before introducing the main results.\n- (p3) The authors claimed that:\n    \n    > This is the first work regarding the Rayleigh Quotient on hypergraphs.\n    \n    The reviewer would like to point out that (Jost & Mulas, 2019; Mulas et al., 2022) also proposed the Rayleigh Quotient on hypergraphs. Although they assumed the EIVW model, the authors need to clarify that the proposed work is the first work on the EDVW hypergraphs model.\n    \n- When introducing spectral properties in Section 3, there is a need to explain what stationary distribution will be used. In the case of a connected hypergraph assumed in the main text, it is irreducible and aperiodic, so by the Perron-Frobenius theorem, there exists a unique stationary distribution with all positive entries (Section A.4). I believe mentioning this part would ensure readers understand that concepts introduced in section 3 such as volume, Rayleigh quotient, and normalized cut are well-defined.\n- (p7) Since Theorem 17 is identical to Theorem 1, it would be better for readability not to define the labeling anew.\n- (p7) In Eq.(18), the referenced Eq.(42) is identical to Eq.(16), so I recommend making the labeling consistent to avoid confusion for readers.\n- (p9) Theorem 17 is identical to Theorem 1.\n- (p9) Using the “$\\leq$” → Using the RHS.\n- (p9) Lemma 22 appears to have more of a corollary character than a lemma.\n- (p18) In Section A.6, the calculations in Eq.(39), (40), 41) are somewhat redundant. There is insufficient explanation for non-trivial propositions, and it is unnecessary to write out trivial calculations at length.\n- (p18) In Eq.(42), the numerator and denominator are switched for $u \\in \\bar{\\mathcal{S}}$.\n- (p18) In Eq.(43), $X(u), X(v) \\rightarrow x(u), x(v)$.\n- (p19) The proof in Section A.8 is also verbose. According to Definition 12, $ |\\partial S| \\leq \\text{vol}(S) $ and $ |\\partial \\bar{S}| \\leq \\text{vol}(\\bar{S}) $ hold, so it is trivial.\n- (p19) Change \"\\leq\" → RHS, \"\\geq\" → LHS.\n\n[Chitra & Raphael, 2019] Random walks on hypergraphs with edge-dependent vertex weights. ICML, 2019.\n\n[Jost & Mulas, 2019] Hypergraph Laplace operators for chemical reaction networks. Advances in Mathematics, 2019.\n\n[Mulas et al., 2022] Graphs, Simplicial Complexes and Hypergraphs: Spectral Theory and Topology. Higher-Order Systems, 2022.", "broader_impact_concerns": "There is no issue since this is a theoretical paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZqrW43w3EY", "reviewer": "Reviewer_AWKa", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "To the best of my knowledge, the proposed approach, called HyperClus-G, is truly novel and brings a lot to the table of spectral hypergraphs analysis. The proposed approach incorporates  EDVW info instead of losing them by approximation, leading to stronger results, in particular: \n\n1. Directly incorporates edge-dependent weights, as opposed to other, which approximates hypergraphs as graphs, losing EDVW info\n2. Matches or exceeds F1 scores, while other approaches reach suboptimal due to information loss in conversion\n3. HyperClus-G runs up to 10× faster than STAR++/CLIQUE++ on datasets like Rice and Covertype, despite handling more complex hypergraph structures\n4. Experiments show the second smallest eigenvalue of closely approximates the NCut value achieved by HyperClus-G, with relative errors under 25% (suggesting further room for improvements) \n\nAdditionally, such results are supported by theoretical proofs: \n\n1. HyperClus-G guarantees that the NCut of its partitions satisfies NCut≤O(NCut*) , where NCut* is the optimal value\n2. he algorithm’s performance is bounded by the hypergraph Cheeger inequality, linking λ2 to the conductance of the partition\n\nHowever, the proposed approach has its limitations. In particular, storing the matrices can be prohibitive and computing the second eigenvector could be a bottleneck due to the complexity required for the exact solution; the employed Recursive Bipartitioning has its own drawbacks (such as accumulates errors in hierarchical divisions or suboptimally results on datasets with imbalanced cluster densities). Said so, the method is strong and convincing.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In the paper, the authors propose a novel approach to optimizes the Normalized Cut (NCut) value in hypergraphs with edge-dependent vertex weights (EDW) through a spectral clustering approach grounded in hypergraph Laplacian theory. The algorithm is called HyperClus-G, and approximates the optimal NCut value, which is the second-smallest eigenvalue, after building the random-walk-based Laplacian of \nthe hypergraph.\n\nThis approach seem to bring important advancements in the field of spectral hypergraphs analysis.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "My only concern is about the structure of the paper. Starting from the abstract, which focuses more on what is missing on the literature than what the paper brings to the table, to the flow of the paper. \n\nIn particular, many concepts are introduced multiple times, and in combination with the heavy density of maths formulas, I found the paper hard to navigate. For example, the Main Results sections could be integrated in the Introduction one in a less formal way, removing or compressing some maths formulation. Additionally, some sentences seem disconnected from the others, and could be better integrated. \n\nHowever, such are minor problems, and even if such minor changes could improve the readability, I suggest accepting the manuscript.", "broader_impact_concerns": "I have no concerns about the ethical implications of the work", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)