超图中依赖边的顶点权重随机游走理论

需积分: 0 155 浏览量更新于2024-06-30 收藏 906KB PDF 举报

"2019年，Uthsav Chitra和Benjamin J Raphael在普林斯顿大学计算机科学系合作撰写了一篇关于"边缘依赖顶点权重的超图随机游走"的论文。该研究主要关注超图在机器学习中的应用，尤其是用于捕捉数据中更高阶关系时的谱方法理论。相比于传统的图谱理论，超图谱理论仍是一个活跃的研究领域。论文的核心内容涉及对具有边缘依赖顶点权重的超图进行随机游走的研究。在这样的超图中，每个顶点v与每条关联的超边e都关联一个权重γe(v)，这个权重描述了v对于超边e的贡献。作者引入了基于随机游走的超图拉普拉斯算子，这是一种矩阵表示，它在超图上模拟了扩散过程，有助于理解超图结构的局部和全局性质。论文的重要贡献之一是给出了这种类型超图随机游走的混合时间（mixing time）的界限，即随机游走达到平衡状态所需的时间。这有助于评估随机游走在探索超图结构上的效率，并为优化算法设计提供了理论依据。此外，作者探讨了边缘依赖顶点权重的超图随机游走与传统图随机游走之间的等价条件。这表明，那些依赖于边缘独立顶点权重的超图拉普拉斯矩阵计算出的机器学习方法可能并未充分利用数据中的高阶关系。这一发现对于理解当前算法的局限性和提升性能具有重要意义。最后，通过实证演示，作者揭示了边缘依赖顶点权重的超图在某些情况下相较于边缘独立权重的超图具有优势，比如在处理复杂网络结构和多模态数据时，能更准确地捕捉到数据间的深层联系。这篇论文深化了对边缘依赖顶点权重超图的谱分析，提出了新的随机游走理论框架，并对未来基于超图的机器学习方法提供了理论支持，强调了在处理高阶关系数据时考虑超图特性的必要性。"

weights on the clique graph

such that random walks on

and

are “close”? We provide a partial

answer to this question in Section 5, where we show that, for a specic choice of weights on

, the

second-smallest eigenvalues of the Laplacian matrices of H and G

are close.

4 Stationary Distribution and Mixing Time

4.1 Stationary Distribution

Recall the formula for the stationary distribution of a random walk on a graph. If

G = (V , E, w)

is a graph,

then the stationary distribution π of a random walk on G is

= ρ

e ∈E(v)

w(e), (3)

where

ρ =



e ∈E

w(e)



−1

. We derive a formula for the stationary distribution for a random walk on a

hypergraph with edge-dependent vertex weights; the formula is analogous to equation

(3)

above with two

important changes: rst, the proportionality constant

depends on the hyperedge, and second, each term

in the sum is multiplied by the vertex weight γ

(v).

eorem 6.

Let

H = (V , E, ω, γ )

be a hypergraph with edge-independent vertex weights. ere exist positive

constants ρ

such that the stationary distribution π of a random walk on H is

e ∈E(v)

ω(e)γ

(v). (4)

Moreover, ρ

can be computed in time O



|E|

+ |E|

· |V |



Note that while the vertex weights

(v)

can be scaled arbitrarily without aecting the properties of

the random walk, eorem 6 suggests that ρ

is the “correct” scaling factor.

When the hypergraph has edge-independent vertex weights (i.e.

(v) = γ (v)

for all incident hyperedges

e), ρ

(

v ∈V

γ (v)d(v)

)

−1

, leading to the following formula for the stationary distribution:

d(v)γ (v)

v ∈V

d(v)γ (v)

. (5)

Furthermore, if the vertex weights are trivial (i.e.

γ (v) =

1) then

= d(v)/

v ∈V

d(v)

, recovering

the formula derived in Zhou et al.

[43]

for the stationary distribution of hypergraphs with trivial vertex

weights.

4.2 Mixing Time

In this section, we derive a bound on the mixing time of a random walk on

H = (V , E, ω, γ )

. First, we recall

the denition of the mixing time of a Markov chain.

Denition 7.

Let

be a Markov chain with states

and probability transition matrix

. e mixing time

of M is

mix

(ϵ) = min{t ≥ 0 : ||P

(s, ·) −π ||

T V

≤ ϵ, ∀s ∈ S },

where || · ||

T V

is the total variation distance.

We derive the following bound on the mixing time for a random walk on a hypergraph with edge-

dependent vertex weights.

剩余28页未读，继续阅读

李诗旸

粉丝: 32
资源: 328

超图中依赖边的顶点权重随机游走理论

随机行走（random walk）

Random Walk 随机漫步

藏经阁-Random Walks on Large Scale Graphs with Spark.pdf

matlab分时代码-link-prediction-with-supervised-random-walks:迄今为止最热门的社交网络之一的

2019-KDD-Graph Recurrent Networks with Attributed Random Walks-网

随机游走matlab代码-Video-Supervoxels-Using-Partially-Absorbing-Random-Walks-:

Lazy-random-walks-for-superpixel-segmentation-master.zip

随机游走matlab代码-QUT-Random-Walks:使用随机游走的人群在大学校园内行走的Matlab模拟

随机游走matlab代码-random-walks-and-reactions:粒子之间的随机游走和React。Matlab、fortran、

Traffic fluctuation of random walks on weighted networks

最新资源