発表ファイル 数理物理・物性基礎論セミナー abashima2

First eigenvalue/eigenvector in 

sparse symmetric random matrices

Y. Kabashima (Tokyo Tech.)  Collaborators:  

H. Takahashi (ISM) and O. Watanabe (Tokyo  Tech.)

Refs) YK and H. Takahashi, J. Phys. A: Math. Theor. 45 325001 (2012),  

      YK, H. Takahashi and O. Watanabe, J. Phys. Conf. Ser. 233, 012001(11 pages) (2010)

2014/12/20 ^{数物 ＠ 茶 水女子大学}

Outline

•  Background and moSvaSon 

•  Problem seTng 

•  Cavity method 

•  Two analyScally solvable examples 

–  Single degree model  –  Defect models 

•  More general cases and development of approximaSons 

•  Summary 

2014/12/20 ^{数物 ＠ 茶 水女子大学}

Background

•  The first (largest) eigenvalue and its (first) eigenvector are  relevant to many problems in various fields 

–  InformaSon science 

•  InformaSon extracSon (PCA, PageRank, recommendaSon  systems, etc.) 

•  Spectral analysis of graph bisecSon problem, 3SAT, etc. 

•  Network science 

–  Physics 

•  Quantum mechanics 

•  Spin glasses 

• LocalizaSon in disordered systems

2014/12/20 ^{数物 ＠ 茶 水女子大学}

Example 1)  Graph BisecSon 

Graph BisecSon 

Instance:   graph  G = ( V, E ) 

Ans:   parSSon  V1  and  V2  of  V  s.t. 

‐ V  = V1  U  V2  ^, and 

      ‐ min. crossing edges 

2014/12/20 ^{数物 ＠ 茶 水女子大学}

Graph BisecSon 

 Planted SoluSon Model 

prob. p

         r

 generate an instance  from its soluSon 

  _Graph G

p + r        # of edges

2014/12/20 ^{数物 ＠ 茶 水女子大学}

Spectral method

Adjacency matrix 

_{A = a ( )}

⎧

⎨⎪

⎩⎪

Graph Laplacian 

L = ^δij ^aik

∑

⎛

⎝⎜

⎞

⎠⎟

⎛

⎝⎜

⎞

⎠⎟ ^{− A}

Degree(=#connecSons) of node i

Pothen, Simon and Liou (1990): 

Let      be the eigenvector of the 2^nd largest eigenv. of         .  The following acts as a fairly good heurisSc for a certain class of  graphs.

v = (v^{i )}

_−L

put i to

V _{1, if v}

i

_{> 0}

V _{2, if v}

i

_{< 0}

⎧

⎨ ⎪

⎩⎪

#The largest eigenv. is 0 and its eigenvector is trivially      

#So, this is pracScally a method based on the first eigenvector.  1 = 1,1,...,1^{( )T}

2014/12/20 ^{数物 ＠ 茶 水女子大学}

Example 2) LocalizaSon 

Inverse parScipaSon raSo (IPR):

Characterizes  the profile of   vectors

IPR _≡

v_i⁴

i =1

∑

v_i²

i =1

∑

⎛

⎝⎜

⎞

⎠⎟

2 ^⎯N^⎯⎯_→∞^→

> 0, localized

= 0, extended

⎧⎨

⎪

⎩⎪

IPR>0 IPR → 0

v

v

2014/12/20 ^{数物 ＠ 茶 水女子大学}

IPR of eigenvectors

Biroli and Monasson (1999): 

Laplacian of E‐R sparse random matrix. Eigenvectors of large/ small eigenvalues tend to be localized.   

Large IPR  (=localized) Large IPR 

(=localized)

2014/12/20 ^{数物 ＠ 茶 水女子大学}

Two disSnct features of the first 

eigenvector

Example 1) Graph bisec2on

•  Ordered and extended 

0 20 40 60 80 100

0 1 2 3 4 5 6 7

i

v i

0 20 40 60 80 100

−2

−1 0 1 2

i

v i

Example 2) Localiza2on 

•  Randomly localized 

V ₂

V ₁

2014/12/20 ^{数物 ＠ 茶 水女子大学}

MoSvaSon

• QuesSon: What factors cause the difference of the two  features of the first eigenvector? 

•  We will examine details of a simple model system for geTng  useful insights for answering this quesSon.  

2014/12/20 ^{数物 ＠ 茶 水女子大学}

MoSvaSon’

•  後藤君＠H22 度卒業生 修論 

–  ^{ン 用い 評価表現辞書構築 け 統計力学的精度改}

善法  

–  課題：多数 >=数万 ^単語  posiSve   negaSve  ^{機械的 分類} 

•  ^{ロ 評 分析 要}

–  先行研究：高村 東工大 ^{仮想的 ン 構成 自}

動分類 行う方法 提案 い  

•  結果 見 ^{，性能 有限温度 最大 ，低温 破綻 い}  

→^{第 固有ベ 使え い， いう う 話 そう} 

•  詳 く調べ ^{， ワ 構成法 都合 ，第 固有ベ 強}

磁性 分類 関係 そ ，単純 第 固有値 成分 消せ

性能 う _→　実際 性能 向  

•  欲 出 ^{，大 固有値 成分 消 ，性能 向}

い _→ 大 固有値 成分 ほ _localize  い  

•  有限温度 う くいく原因 ，正 負 種単語 対 ^{localize 無数 固}

有 感 率 程 く混 ， う ，相転移 得

対称性 破 状態 情報 担 い く，種単語 対 応

答 使 分類 行う方法 あ いえ  

2014/12/20 ^{数物 ＠ 茶 水女子大学}

Problem seTng

•         random matrix: 

•  CharacterisSc properSes 

–  Symmetry  

– Bimodal degree distribuSon 

– Binary dist. of non‐zero elements

N _{× N}

_{J = J}

( )

J

_{= J}

p(k) = p

^δ

+ p

^δ

J_{ij =}

J ^{: Prob. 1 + Δ} 2

−J : Prob. ^{1− Δ} 2

⎧

⎨

⎪⎪

⎩

⎪⎪

+ 

‐ 

 … 

+ 

‐ 

+  

₊  

0  0 

0 

0 

J =

k = 3

k

p(k)

c 1 ^c 2

p

p

2014/12/20 ^{数物 ＠ 茶 水女子大学}

Our quesSon

•  How do the properSes of the first eigenvalue/

eigenvector depend on the system parameters  

       ?  _c

1

^{, c}

^{, p}

= 1 − p

^, Δ

2014/12/20 ^{数物 ＠ 茶 水女子大学}

MathemaScal formulaSon

•  The first eigenvalue problem is formulated as a maximizaSon  problem of the  quadraSc form. 

Λ = ¹

N ^max

v

Jv

{ } subj. to v

^{= N}

V = _{arg max}

v

v

Jv

{ } subj. to v

= N

2014/12/20 ^{数物 ＠ 茶 水女子大学}

IntuiSve consideraSon (I)

v

_{Jv = J}

ij

^v

^v

∑

^{= v}

^J

^v

⎛ ∑

⎝⎜

⎞

⎠⎟

i₌₁

∑

•  Assigning larger absolute values to sites of larger degree nodes  

  makes the quadraSc form larger when the power         is constrained.    

•    

v ² c_{2 − c1} : sufficiently large

p₂ : sufficiently small

V : localized

Any criScal relaSon expressed by       ?  c

, c

, p

2014/12/20 ^{数物 ＠ 茶 水女子大学}

IntuiSve consideraSon (II)

•    _{Δ = 1} ^•    _{Δ = 0}

+ 

+ 

+ 

+ 

+ 

+   +   +  

+  

+  

PosiSve 

+  

‐  ₊  ⁺ 

+   ^‐ 

‐ 

‐  ‐ 

PosiSve or negaSve  randomly 

−v

^v _−v

^v

v

*

> 0

(< 0)

M ₌ ¹

N

v

* i₌₁

N

∑ > 0

N → ∞

v

*

= ± randomly

(∀i = 1, 2,…, N )

N → ∞

M ₌ ¹

N

v

* i₌₁

N

∑ ^{→ 0}

2014/12/20 ^{数物 ＠ 茶 水女子大学}

IntuiSve consideraSon (II)

•    _{Δ = 1} ^•    _{Δ = 0}

+ 

+ 

+ 

+ 

+ 

+   +   +  

+  

+  

PosiSve 

+  

‐  ₊  ⁺ 

+   ^‐ 

‐ 

‐  ‐ 

PosiSve or negaSve  randomly 

−v

^v _−v

^v

min w.r.t.       s.t.  ^v _{| v |} ²_{= N} min w.r.t.       s.t.  ^v _{| v |} ²_{= N}

v

*

> 0

(< 0)

M ₌ ¹

N

v

* i₌₁

N

∑ > 0

N → ∞

v

*

= ± randomly

(∀i = 1, 2,…, N )

N → ∞

M ₌ ¹

N

v

* i₌₁

N

∑ ^{→ 0}

10.3.7 IW‐SMI2010@Kyoto

How are        and       determined?  

Histogram 

Normaliza2on:   

Expected behavior in   

^{N → ∞}

| v |

= N

N _i ^δ

=1 N

∑

M

0 _{Δ Δ}

c

1

Δ

^{M (or P(v))}

0

0

v

v

2014/12/20 ^{数物 ＠ 茶 水女子大学}

Cavity method

•  Mezard et al (1987) 

–  A kind of mean field approximaSon (MFA): 

approximate a many‐body problem by a bunch of single body  problems 

–  Construct a MFA by leaving each variable out 

Original system  Cavity system 

i _i

j ∈∂i

2014/12/20 ^{数物 ＠ 茶 水女子大学}

Why cavity?

•  Natural introducSon of “local tree structure” 

–  Can suppress approx. biases of self‐interacSon caused by cycles 

•  In the current system, the cavity method 

–  Can be regarded as a macroscopic descripSon of ^belief   propagaSon (BP) 

–  Expected to provide “exact results” as  

N → ∞

Cavity system 

i

j ∈∂i

2014/12/20 ^{数物 ＠ 茶 水女子大学}

ApplicaSon to the first eigenvalue 

Problem

•  First eigenvalue as a Lagrange mulSplier

( ^Λ , v

) = arg extr

λ ,v

{v

^{Jv − λ} (| v |

− N )}

Original (many‐body) problem

V

_{= argmax}

{− ^A

^v

+ 2 ^H

^v

^}

(i = 1, 2,…, N )

Λ

^V

∑

= N

{

Mean field approximaSon

A bunch of   single‐body  problems 

2014/12/20 ^{数物 ＠ 茶 水女子大学}

ApplicaSon to the first eigenvalue 

Problem

•  First eigenvalue as a Lagrange mulSplier

( ^Λ , v

) = arg extr

λ ,v

{v

^{Jv − λ} (| v |

− N )}

Original (many‐body) problem

V

_{= argmax}

{− ^A

^v

+ 2 ^H

^v

^}

(i = 1, 2,…, N )

Λ

^V

∑

= N

{

Mean field approximaSon

A bunch of   single‐body  problems 

How can we determine  these parameters (mean  fields)? 

2014/12/20 ^{数物 ＠ 茶 水女子大学}

カ

•  確率分布 以 ^{う 表現 場合 考え}  

•  依存関係 ^{タ 表現}

P _{( )} x ₌ ¹

Z ^ψ

x

( )

a₌₁ M

∏

^{( )}

xa : subset of x

_{

_}

x1

x2 ^x3

x4

x5

ψ₁^(x₁^{, x}₂^{, x}₃⁾

ψ₂^(x₃^{, x}₄^{, x}₅⁾ P_{(x) =} ¹

Z ^{ψ1(x1, x2, x3)ψ2(x3, x4, x5)}

ポ ン 関数

2014/12/20 ^{数物 ＠ 茶 水女子大学}

表現 統計的独立性

•  確率変数 対応 ^{○ 互い 交わ い異}

部分 含 ⇒ 確率変数 統計的 独立 

x1

x2 ^x3

x4

x5

ψ₁^(x₁^{, x}₂⁾

ψ₂(x₃, x₄) P_{(x) =} ¹

Z ^{ψ1(x1, x2)ψ 2(x4, x5)}

= P x

₍

₎

₍

₎

確率変数 互い 統計的 独立 あ ，確率推論 必要 計算 減

⇒　 表現 確率推論 計算 密接 関係 い

2014/12/20 ^{数物 ＠ 茶 水女子大学}

周辺分布 キ 分布

•  周辺 ^{体 分布 い 厳密 成 立 公式}

Pi^(xi^{) = P} x_{\ xi}

∑ ^{( )}

^{( )}

a=1

∏

∑

^{( )}

a_∈∂i

⎛

∏

⎝⎜

⎞

⎠⎟

x_{\ xi}

∑

^{( )}

b_∉∂i

⎛

∏

⎝⎜

⎞

⎠⎟

= ^{Z\ i}

Z ^ψa

xa

( )

a_∈∂i

⎛

∏

⎝⎜

⎞

⎠⎟

x_{\ xi}

∑

b

_{( )}

⎛

∏

⎝⎜

⎞

⎠⎟ Z\ i

=

ψa

_{( )}

⎛

∏

⎝⎜

⎞

⎠⎟ ^{P\ i}

⁽

⁾

x_{\ xi}

∑

ψa

_{( )}

⎛

∏

⎝⎜

⎞

⎠⎟ ^{P\ i}

⁽

⁾

∑

=

ψa

_{( )}

∏

\ i

ψa

_{( )}

∏

x_i \ i

∑

ψ ^effi ^x

_{( )}

ψ ^{effi x}

( )

x_i

∑

キ 分布

_P

\ i

^{( x \ x}

⁾

キ 分布 均

2014/12/20 ^{数物 ＠ 茶 水女子大学}

カ 表現

•  周辺分布＝直接繋 ^{い ポ ン 関数 積 キ}

分布 均 規格化

xi

∂i

ψ

eff

x

( )

^{= ψ}

( ) ^x

a_∈∂i

∏

\ i

外側 キ 空孔 分布  

い  

2014/12/20 ^{数物 ＠ 茶 水女子大学}

パ 特

(a) (b)

a

b ^c

a

b ^c

i i

a, b, c,… ∈∂i ^{い x}_a, x_b, x_c,… 共通 含 　　^x_i (a):

(b):^除く 　　　　　　　 含 部分 互い 交わ 持 こ く

　　　分離 ⇒ 各部分 含 確率変数 統計的 独立

xi a, b, c,… ∈∂i

2014/12/20 ^{数物 ＠ 茶 水女子大学}

パ

ψ

_{( )} ^x

^{= Tr}

x \ x_i

^ψ

x

( )

a_∈∂i

⎛ ∏

⎝⎜

⎞

⎠⎟ ^P

^{( x \ x}

⁾

= ^Tr

xa^{\ x}i

ψ

_{( )} ^x

^m

_{( )} ^x

j

^∏

⎛

⎝⎜

⎞

⎠⎟

⎛

⎝ ⎜ ^⎞

⎠ ⎟

a_∈∂i

∏

m

_{( )} x

^:

周辺分布

x

計算 い

楽 計算

x

a

m_j→a

_{( )}

2014/12/20 ^{数物 ＠ 茶 水女子大学}

belief propagaSon (BP)

•  キ ^{系 周辺分布 漸化式 求}

こ 考え  

ψ_i→a^eff

_{( )}

xb^\xi

ψ_b

_{( )}

_{( )}

j

^∏

⎛

⎝⎜

⎞

⎠⎟

⎛

⎝⎜ ^⎞

⎠⎟

b

^∏

こ 規格化 ，_aキ 系 周辺分布

m_i→a

_{( )}

xTr

b\ xi

ψ_b

( )

_{( )}

^∏

⎛

⎝⎜

⎞

⎠⎟

⎛

⎝⎜ ^⎞

⎠⎟

b

^∏

Trx_i ^xTr_{b\ xi} ^ψb

xb

( )

_{( )}

j

^∏

⎛

⎝⎜

⎞

⎠⎟

⎛

⎝⎜ ^⎞

⎠⎟

b

^∏

伝搬 漸化式 解釈 こ

x

a

m_j→b

_{( )}

a^{キ 系}

2014/12/20 ^{数物 ＠ 茶 水女子大学}

和 積 分け 表現

(a)

a _i i

(b)

a

m_{a→i ( )}x_i =α_{a→i Tr}

x_j∈x_{a\ xi}^ψa

xa

( ) ^mj→a

_{( )}

^∏

mi_{→a ( )}^xi = ^αi_→a ^mb_{→i ( )}^xi b_∈∂i\a

∏

和 ：_{○→□ 使 □→○ 更新}

水

積 ：_{□→○ 使 ○→□ 更新}

垂直

こ ，分 和積 ゴ sum-product algorithm

2014/12/20 ^{数物 ＠ 茶 水女子大学}

周辺分布 評価

•  周辺分布 ≡ ^{○ 流入 べ □}

掛け合わせ こ 求

Pi^(xi ^{) = α}i ^ma_→i

_{( )}

∏ i

2014/12/20 ^{数物 ＠ 茶 水女子大学}

パ 対 成立 性質

•  厳密 評価 ^{い け ベ 近似 一般化}  

•  ^{BP 度伝搬 せ け い} 

•  計算  

m_a→i

_{( )}

xa^{\ x}i

ψ_a

( )

_{( )}

^∏

⎛

⎝⎜

⎞

⎠⎟ mi→a

_{( )}

_{( )}

b_{∈∂i \a}

∏

!O

₍

_{( (}

_{) ) )}

!O ∂i −

₍

₎

疎 木 あ 大 比例 く い 時間  

厳密 期待値評価 可能 

Pi^(xi ^{) = α}i ^ma_→i

_{( )}

∏

( )

2014/12/20 ^{数物 ＠ 茶 水女子大学}

木 い場合 _BP

•  厳密 評価 ^い 

•  ^{，局所的 伝搬 復法 適用 可能} 

–  ^{束性 保証 い ， 更新あ 計算 木 場合 同}

疎 木 あ 大 比例 く い 時間  

近似的 期待値評価 可能 

m_a→i

_{( )}

x_{a\ xi}^ψa

xa

( )

_{( )}

^∏

⎛

⎝⎜

⎞

⎠⎟ mi→a

_{( )}

_{( )}

b_{∈∂i \a}

∏

!O

₍

_{( (}

_{) ) )}

!O ∂i −

₍

₎

Pi^(xi ^{) = α}i ^ma_→i

_{( )}

∏

( )

2014/12/20 ^{数物 ＠ 茶 水女子大学}

固有値問題 関係

•  対称行列 固有値問題→ 次形式 最大化→確率推論

特 場合

1 2 ^v

T_{Jv − λ}

| v |²

( )

2 ij

⁽

⁾

∑

P v ₍ β ₎ =

β 2 ^v

T_Jv−λ|v|2

( )

e

Z _{( )} β ⁼

1

Z _{( )} β ^e

−^β

2

⁽

⁾

∏

カ カ 分布

arg max

v

v

Jv _{− λ | v |}

{ } ⁼

^{lim Tr vP v ( β )}

ロ温度極限 最大化 解い い 同

2014/12/20 ^{数物 ＠ 茶 水女子大学}

固有値問題 ロ温度 _BP

m_{i→ ij ( )}v_i = ^{βAi→ j} 2^{π e}

−^{βAi→ j} 2 ^vi−

H_{i→ j} A_{i→ j}

⎛

⎝⎜ ^⎞

⎠⎟

2

m_{ij →i( )}v_i = e⁻

βA^ˆ_j→i 2 ^vi

2_+βHˆ j→i^vi

和

m _{ij →i}

_{( )}

β^Aˆ_j→i 2 ^vi

2_+βHˆ j→i^vi

= dv_je

βJ_ij

2 ^vivj_m

j_{→ ij}

_{( )}

∫

= dv_je

βJij

2 ^{vivj βAj→i}

2π ^e

−^βAj→i 2 ^vj−

H_j→i A_j→i

⎛

⎝⎜ ^⎞

⎠⎟

2

∫

= e

βJ_ij² 2^Aj→i

v_i²+^βJijHj→i A_j→i

Aˆ_{j→i = −} ^Jij

2

A_j→i ^,

Hˆ _{j→i =} ^JijHj→i A_j→i

積

m_{i→ ij}

_{( )}

−^{βAi→ j} 2 ^vi−

H_{i→ j} A_{i→ j}

⎛

⎝⎜ ^⎞

⎠⎟

2

= _{αi→ ij} e⁻

βλ 2 ^vi

2

m _{ki →i}

k

^∏

v_i

( )

= _{αi→ ij} e

−^βλ 2 ^vi

2_{+ −}β^Aˆ_k→i 2 ^vi

2_+βHˆ k→i^vi

⎛

⎝⎜

⎞

k_{∈∂i\ j}^∑ ⎠⎟

A_{i→ j = λ +} A^ˆ_k→i

k∈∂i\ j

∑

∑

2014/12/20 ^{数物 ＠ 茶 水女子大学}

＝ 体問題

A_{i→ j =} ^{λ − Jki}

2

A_k→i

k∈∂i\ j

∑

k∈∂i\ j

∑

＝ 体問題

P_i

_{( )}

−^βAi 2 ^vi−

H_i A_i

⎛

⎝⎜

⎞

⎠⎟

2

= _αie⁻

βλ 2 ^vi

2

m _{ji →i}

∏

^{( )}

2 ^vi

2_{+ −}^βAˆj→i

2 ^vi

2_+βHˆ j_→i^vi

⎛

⎝⎜ ^⎞

⎠⎟

j_∈∂i

∑

A_{i =} ^λ ₊ A^ˆ_j→i

j∈∂i

∑

∑

変数 消去

A_{i =} ^{λ − Jij}

2

A_j→i

j∈∂i

∑

j∈∂i

∑

和 積

体問題

2014/12/20 ^{数物 ＠ 茶 水女子大学}

Belief propagaSon

•  CM naturally reproduces belief propagaSon for this task 

Cavity system 

i

∂i

l

J

J

Messages (cavity fields)

A_{i→l =} ^{λ − Jij}

2

A_j→i

j∈∂i\l

∑

A_j→i

j∈∂i\l

∑

Beliefs (mean fields)

Al _{= λ −}

Jlk 2

Ak→l k∈∂l

∑

k∈∂l k→l

∑

for all directed edges  ^{i → l}

for all nodes  ⁱ

2014/12/20 ^{数物 ＠ 茶 水女子大学}