1 of 14

ALT 2023

Adaptive Power Method:

Eigenvector Estimation from Sampled Data

Seiyun Shin, Han Zhao, and Ilan Shomorony

University of Illinois at Urbana-Champaign

Email: seiyuns2@Illinois.edu

2 of 14

Old Problem: Eigenvector Computation

Compute top eigenvector of a matrix A

Many applications in data science:

PCA, low-rank approximation, spectral clustering
Network analysis: eigenvector centrality

The higher the value, the greater the level of influence

=

2

3 of 14

Old Problem: Eigenvector Computation

Compute top eigenvector of a matrix A

Challenge:

Matrix A could be large and stored in distributed manner
Fully observing A may be costly or infeasible
e.g., large social networks, biological networks

=

C. elegans connectome

3

4 of 14

Eigenvector Estimation from Partial Observations

Symmetric matrix

Budget B of entry observations

=

Questions:

How large does B have to be for ?
Can adaptivity help in improving the estimation?

4

5 of 14

Main Result

Adaptive Power Method (APM)

Adaptively select new observations based on current

Theorem (informal): With observations,

with probability .

update

5

6 of 14

Power Method (classical)

Start with random unitary vector

=

normalize

After iterations,

What if we can only observe A partially?

We can estimate each

6

7 of 14

Adaptive Power Method

Start with random unitary vector

…

observe w. p.

scale by

With observations per iteration, w. p. ,

Proof is based on Bernstein’s inequality
Will converge to ?

7

8 of 14

Adaptive Power Method

Noisy Power Method

(Hardt and Price, 2014)

Theorem: NPM converges to if all satisfy

NPM:

8

9 of 14

Adaptive Power Method

…

observe w. p.

scale by

View APM as a version of the Noisy Power Method

Theorem: Suppose . Using observations and iterations, APM estimates the top eigenvector with , with probability .

9

10 of 14

Main Theorem

Implication 1: The case recovers the informal result

Implication 2: As long as , there still exists a sample complexity gain

Suppose APM is run for iterations with�� samples. Then the eigenvector

estimate satisfies ��with probability at least

10

11 of 14

Adaptive Power Method Refinement

…

observe w. p.

scale by

observe w. p.

This choice of minimizes variance of the estimator
Non-uniform budget allocation; favors large eigenvector entries
We call this APM++

11

12 of 14

Numerical Results

Drug-drug interaction network (Open Graph Benchmark)

4k nodes and 2M edges

B = 50% of entries

Non-adaptive

APM

APM++

Non-adaptive

APM

APM++

top-500 entries of

12

13 of 14

Numerical Results

Stanford’s “ego-facebook” network

4k nodes and 90k edges

B = 5% of entries

Non-adaptive

APM

APM++

Non-adaptive

APM

APM++

top-500 entries of

90%

13

14 of 14

Concluding Remarks

APM: adaptively estimate top eigenvector

Generalizations:

Asymmetric A, top-k eigenvectors?

Very sparse graphs? Exploit community structure?
Partial graph observation in other settings: Graph NNs?

Budget:

Error:

Thank you! 😁🙏

14