Cutsize Distributions of Balanced Hypergraph
Bipartitions for Random Hypergraphs
Takayuki Nozaki
Yamaguchi UniversityISIT2016
2016/7/15

T. Nozaki (Yamaguchi Univ.)

Cutsize Distributions of Balanced Hypergraph Bipartitions for Random
2016/7/15
Hypergraphs
1 / 18

Outline
Previous Work (ISIT2015)
We presented a parallel encoding algorithm for LDPC codes
The processing time of encoding depends on parallel degree K
Maximum parallel degree Kmax depends on parity check matrix H

Aim of ResearchAnalyze the processing time of this encoding algorithm⇒ Analyze the parallel degree Kmax of this encoding algorithm

Main result of this work (1)The parallel degree Kmax depends on the minimum cutsize in balanced
K-way partition for hypergraph representation of H
However, balanced hypergraph partitioning problem is NP-hard...
T. Nozaki (Yamaguchi Univ.)

Cutsize Distributions of Balanced Hypergraph Bipartitions for Random
2016/7/15
Hypergraphs
2 / 18

Outline (2)Solution: We take coding theoretic approach(Similar technique to derive minimum distance for the LDPC ensemble)
1 considering a random hypergraph ensemble
2 deriving the ensemble average of cutsize distribution (balancedpartitions with a given cutsize)
3 analyzing the growth rate for the cutsize distribution
4 clarifying the typical minimum cutsize for the hypergraph ensemble

Main result of this work (2)Deriving the typical minimum cutsize of balanced bipartitions (K = 2) for
random hypergraph ensemble defined from regular LDPC ensemble
Related works
Analysis of random graphs by using coding theoritic approaches[Fujii-Wadayama2012], [Yano-Wadayama2012], [Fujii-Wadayama2013]

Analysis of cutsize in random graph bisection [Dembo et al.2015]
T. Nozaki (Yamaguchi Univ.)

Cutsize Distributions of Balanced Hypergraph Bipartitions for Random
2016/7/15
Hypergraphs
3 / 18Preliminaries (1: Hypergraph Representation of code)
Hypergraph H = (U, E)
U := {u1 , u2 , . . . , um } : Set of vertices
E := {e1 , e2 , . . . , en } : Set of nets (hyperedges)
Each net connects to at least 1 vertices.

Hypergraph representation of LDPC codei-th column ⇒ i-th net ei
j-th row ⇒ j-th vertex uj
If hi,j = 1, j-th net connects to i-th vertex
1
 0

 0

 1
 0 10

10001
101000010

1000
1
000
10
100
1

T. Nozaki (Yamaguchi Univ.)

0
1
00
10
1

0
1
00
00
10
10
0
0
0
000
1
1000

00
10
1
100
0
1000
1

00 

1 
1 
0 

0 0

e1

e5u1

e2

e7u2

e6u4e3

e8u3

e10u5

e9u7u6e4

e11e12Cutsize Distributions of Balanced Hypergraph Bipartitions for Random
2016/7/15
Hypergraphs
4 / 18Preliminaries (2: Balanced Hypergraph Partitioning)
K-way partition ΠK = {U1 , U2 , . . . , Uk }(1) ∅ ̸= Ui ⊆ U ,(2) Ui ∩ Uj = ∅ (for i ̸= j),

(3)

∪K

i=1 Ui = U

A K-way partition is ϵ-balanced if
max

i=1,2,...,K|Ui | ≤|U|
(1 + ϵ)K(Note) If ϵ = 0, then all the parts are same size
Cut set X (ΠK ) is the set of vertices connecting to at least 2 parts fora partition ΠK
Cutsize is the number of elements in X (ΠK )T. Nozaki (Yamaguchi Univ.)

Cutsize Distributions of Balanced Hypergraph Bipartitions for Random
2016/7/15
Hypergraphs
5 / 18Preliminaries (3: Example of Hypergraph Partitioning)
K=2
U1 = {u1 , u4 , u5 , u6 }U2 = {u2 , u3 , u7 }

e1e5
u1

e2

e6u4

Cut setX (Π2 ) = {e5 , e6 , e10 , e11 , e12 }Cutsize : |X (Π2 )| = 5e7u2e3e8u3e10u5e9u7u6e4e11e12

T. Nozaki (Yamaguchi Univ.)

Cutsize Distributions of Balanced Hypergraph Bipartitions for Random
2016/7/15
Hypergraphs
6 / 18

Condition for Parallel Encodable (1)(Definition) K parallel encodable by block-diagonalization
For a given H, an LDPC code is K parallel encodable if there exists a pairof permutation matrices P, Q such that(PHQ = HPHP,1) HI = OO..

.
HP,K


HI,1..  ,. 
HI,Kand HP,i is a non-singularmi × mi matrix for i = 1, 2, . . . , K, where mi∑is almost equal size ( i mi = m and maxi mi ≤ (1 + ϵ)m/K)
If H is K-parallel encodable, the parity part of codeword
p = (p1 , p2 , . . . , pK ) is parallelly solved from
HP,1 pT1 = −HI,1 iT ,···

HP,K pTK = −HI,K iT(i : information part of codeword)
T. Nozaki (Yamaguchi Univ.)

Cutsize Distributions of Balanced Hypergraph Bipartitions for Random
2016/7/15
Hypergraphs
7 / 18

Condition for Parallel Encodable (2)[Proposition 1] Necessary condition of K parallel encodable
If an LDPC code defined by H is K parallel encodable byblock-diagonalization, the following condition holds:(ϵ)

n − m ≥ min |X (ΠK )|.
(ϵ)ΠKThere exists the maximum parallel degree{Kmax := max}(ϵ)
K | n − m ≥ min |X (ΠK )|(ϵ)ΠK

Hence, processing time of encoding algorithm depends on(ϵ)
minΠ(ϵ) |X (ΠK )|K(ϵ)

However, It is diﬃcult to calculate minΠ(ϵ) |X (ΠK )|K(since balanced hypergraph partition problem is NP-hard)
T. Nozaki (Yamaguchi Univ.)

Cutsize Distributions of Balanced Hypergraph Bipartitions for Random
2016/7/15
Hypergraphs
8 / 18Cutsize distribution (1: Hypergraph ensemble)
Hypergraph ensemble derived from E(n, γ, δ)
1Define regular LDPC ensemble E(n, γ, δ)
n: codelength
γ: degree of variable node
δ: degree of check node2

Convert Tanner graph to Hypergraphvariable node → netcheck node → vertex

T. Nozaki (Yamaguchi Univ.)

Cutsize Distributions of Balanced Hypergraph Bipartitions for Random
2016/7/15
Hypergraphs
9 / 18Cutsize distribution (2: Definition)(Definition) Cutsize distribution
AH (s, m1 ) : the number of bipartitions s.t. |X (Π2 )| = s, |U1 | = m1
and |U2 | = m2 = m − m1 for a hypergraph H
A(s, m1 ): ensemble average of AH (s, m1 )A(s, m1 ) := EH∈E(n,γ,δ) [AH (s, m1 )] =1
ξ!

∑AH (s, m1 ).

H∈E(n,γ,δ)BH (s, ϵ) : the number of ϵ-balanced bipartitions with cutsize s for ahypergraph H
B(s, ϵ) : ensemble average of BH (s, ϵ)B(s, ϵ) := EH∈E(n,γ,δ) [BH (s, ϵ)] =∑A(s, m1 ),m1 ∈Mϵwhere Mϵ := [[m(1 − ϵ)/2, m(1 + ϵ)/2]].
T. Nozaki (Yamaguchi Univ.)

Cutsize Distributions of Balanced Hypergraph Bipartitions for Random
2016/7/15
Hypergraphs
10 / 18

Cutsize distribution (3: Theorem)(Theorem 1) Cutsize distribution
For an ensemble E(n, γ, δ), the cutsize distribution A(s, m1 ) is given as
follows:( m )(n)sA(s, m1 ) = m( 1δm ) Coef(f (u)n , uδm1 )δm1× I[s ≤ δm1 ]I[s ≤ δ(m − m1 )],s/nf (u) := p(u)q(u)1−s/n ,p(u) := (1 + u)γ − 1 − uγ ,q(u) := 1 + uγ .

where Coef(f (x), xi ) is the coeﬃcient of xi in the polynomial f (x)T. Nozaki (Yamaguchi Univ.)

Cutsize Distributions of Balanced Hypergraph Bipartitions for Random
2016/7/15
Hypergraphs
11 / 18

Typical Minimum Cutsize (1: Definitions)(Definition) Growth rate
Define the growth rate g(σ, µ1 ) and h(σ, ϵ) for the cutsize distributions
A(σn, µ1 m) and B(σn, ϵ) asg(σ, µ1 ) = lim

1n→∞ nlog A(σn, µ1 m),1log B(σn, ϵ),n→∞ nh(σ, ϵ) = lim

RemarkIf h(σ, ϵ) < 0, then B(σn, ϵ) is exponentially decreasing
If h(σ, ϵ) > 0, then B(σn, ϵ) is exponentially increasing

T. Nozaki (Yamaguchi Univ.)

Cutsize Distributions of Balanced Hypergraph Bipartitions for Random
2016/7/15
Hypergraphs
12 / 18

Typical Minimum Cutsize (2: Definition)(Definition) Typical minimum cutsize
Defineα∗ (µ1 ) := inf{σ > 0 | g(σ, µ1 ) > 0},β ∗ (ϵ) := inf{σ > 0 | h(σ, ϵ) > 0}.
We refer the value α∗ (µ1 ) and β ∗ (ϵ) as the relative typical minimum
cutsizes for E(n, γ, δ).

[Proposition2] Necessary condition of 2 parallel encodable
If a code H ∈ E(n, γ, δ) is 2 parallel encodable by theblock-diagonalization with high probability, the following condition holds:
1−T. Nozaki (Yamaguchi Univ.)γ≥ β ∗ (ϵ).
δCutsize Distributions of Balanced Hypergraph Bipartitions for Random
2016/7/15
Hypergraphs
13 / 18

Typical Minimum Cutsize (3: Growth rate)[Theorem 2] Growth rateδ−1H2 (µ1 )δ+ inf {σ log p(u) + (1 − σ) log q(u) − µ1 γ log u}.

g(σ, µ1 ) = H2 (σ) − γu>0A point u achieving the infimum satisfies
σup′ (u)q(u) + (1 − σ)up(u)q ′ (u) = µ1 γp(u)q(u),dpwhere p′ (u) := du.

h(σ, ϵ) = max g(σ, µ1 ).
µ1 ∈M̄ϵT. Nozaki (Yamaguchi Univ.)

Cutsize Distributions of Balanced Hypergraph Bipartitions for Random
2016/7/15
Hypergraphs
14 / 18

Typical Minimum Cutsize (3: Property of growth rate)[Proposition 3] Existence of typical minimum cutsize
For a fixed µ1 , there exist σ0 such that g(σ0 , µ1 ) = 0
For a fixed ϵ, there exist σ0 such that h(σ0 , ϵ) = 0[Lemma 1] Closed form lower boundh(σ, ϵ) > h(σ, 0) = g(σ, 1/2).
g(σ, 1/2) = H2 (σ) + σ log(2γ−1 − 1) − γ

T. Nozaki (Yamaguchi Univ.)δ−1+ 1.
δCutsize Distributions of Balanced Hypergraph Bipartitions for Random
2016/7/15
Hypergraphs
15 / 18

Typical Minimum Cutsize (4: Numerical Example)
10.5
0-0.5
(3,4)
(3,5)
(3,6)
(3,7)
(3,8)
0-1-1.5
-20

0.2

0.4

0.6

0.8

1σGrowth rate h(σ, 0) for hypergraph ensemble derived from (3, δ)-regularLDPC ensemble.

T. Nozaki (Yamaguchi Univ.)

Cutsize Distributions of Balanced Hypergraph Bipartitions for Random
2016/7/15
Hypergraphs
16 / 18

Condition for Parallel Encodable(Recall) Necessary condition of 2 parallel encodable
If a code H ∈ E(n, γ, δ) is K = 2 parallel encodable by theblock-diagonalization with high probability, the following condition holds:1−γ≥ β ∗ (ϵ).
δ(1)

Table: The left and right hand sides of (1) for γ = 3

δ
1 − γ/δβ ∗ (0)40.2500
0.263650.4000
0.315760.5000
0.354570.57140.384980.6250
0.409490.6667
0.4297The ensemble E(n, 3, δ) for δ ≥ 5 satisfies the necessary condition ofparallel encodable.
T. Nozaki (Yamaguchi Univ.)

Cutsize Distributions of Balanced Hypergraph Bipartitions for Random
2016/7/15
Hypergraphs
17 / 18

Conclusion and Future Works
Conclusion
We give a necessary condition for K parallel encodable
We derive the cutsize distribution for hypergraph ensembleWe give the growth rate of hypergraph ensemble
We give the typical minimum cutsize for hypergraph ensemble

Future works
Consider K ≥ 3
Irregular LDPC ensemble case

T. Nozaki (Yamaguchi Univ.)

Cutsize Distributions of Balanced Hypergraph Bipartitions for Random
2016/7/15
Hypergraphs
18 / 18