Nonlinear Laplacian for Digraphs
and Its Applications to NetworkAnalysis
Yuichi Yoshida
National Institute of Informatics &Preferred Infrastructure, Inc.
@WSDM 2016

Question
Can we develop spectral graph theory for digraphs?
•Spectral graph theory analyzes graph properties via
eigenpairs of associated matrices.
– Adjacency matrix, incidence matrix, Laplacian• Applications– Approximation to graph parameters (e.g, chromaticnumber), community detection, visualization, etc.
• Well established for undirected graphs.

Question
Can we develop spectral graph theory for digraphs?
• Many real-world networks are directed!
– Web graph, Twitter followers, phone calls, paper citations,food web, metabolic network.
• Extensions for digraphs are largely unexplored andunsatisfying.

Laplacian••••Graph G = (V, E)
Adjacency matrix: AG
Degree matrix: DG
Laplacian LG := DG – AGGDG
3000020000201234AG000
3-0111100
11001LG
1110=3−1−1−1−120−1−102−1−1−1−13• Normalized Laplacian 𝓛G := DG-1/2 LG DG-1/2 = I - DG-1/2 AG DG-1/2

Interpretation of Laplacian• Regard G as an electric circuit.
• An edge = a resistance of 1Ω.
• Flow a current of b(u) ampere to each vertex u ∈ V.
The voltages of vertices can be computed by solving LGx = b
1A0.5
10.25
2

30.25

40.0

1A

Extensions for Digraphs
Existing extensions of Laplacians for digraphs:
1. LG = DG+ – AG– Asymmetric and hence eigenpairs are complex-valued.
2. Chung’s Laplacian– Assume strong connectivity. Need random walks tointerpret its eigenpairs.
Our contributions
1. Laplacian for digraphs whose eigenpairs can beinterpreted more combinatorially.
2. Algorithm that computes a small eigenvalue.
3. Applications to visualization and community detection.

Nonlinear Laplacian
Nonlinear Laplacian LG: ℝn→ℝn for a digraph G:
From a vector x∈ℝn, we compute LG(x) as follows
1. Define an undirected graph as follows: for each arc u → v• If x(u) ≥ x(v), add an (undirected) edge {u, v}.
• Otherwise, add self-loops.
2. Let LH be the Laplacian of H.
3. Output LHx.
1.0v10.8v2v10.6v4

0.4v3v2v4v3

Interpretation• Regard G = (V, E) as an electric circuit.
• An edge = a diode of 1Ω (current flows only one way).
• Flow a current of b(u) ampere to each vertex u ∈ V.
The voltages of vertices can be computed by solving LG(x) = b.
1A1
10.5
2

30.5

40.01A

Eigenpair of Nonlinear Laplacian• Normalized Laplacian 𝓛G : x ⟼ DG-1/2 LG (DG-1/2x)• (λ, v) is an eigenpair of 𝓛G if 𝓛G(v) = λv
– Trivial eigenpair: (λ1 = 0, v1).
For any subspace U of positive dimension, ΠU𝓛G has aneigenpair. (ΠU = Projection matrix to U)⇒ Nontrivial eigenpair of 𝓛G exists by choosing U = v1⊥.
Let λ2 be the smallest eigenvalue orthogonal to v1.

Algorithm
Computing λ2 is (likely to be) NP-hard.
Suppose we start the diffusion process
𝑑𝒙 = −Π+ ℒ- 𝒙 𝑑𝑡
from a vector in the subspace U = v1⊥.
• x converges to an eigenvector orthogonal to v1.
•𝒙𝑻 23 ℒ4 (𝒙)Rayleigh quotient ℛ- 𝒙 : =never increases𝒙𝑻 𝒙

during the process.

⇒ We can get a eigenvector of a small eigenvalue.

Visualization: Chung’s & Nonlinear Laplacian
Friendship network at a high school in Illinois• u → v: u regards v as a friend.
Reorder vertices according to the eigenvector computed by thediffusion process.
Chung’s Laplacian
Nonlinear Laplacian

Our method shows the directivity of the network more clearly.

Visualization: Interpretation
Laplacian for undirected graphs
λ2 = min ∑ =,? ∈A 𝒙 𝑢 − 𝒙 𝑣

𝟐s.t. ‖x‖ = 1, x ⊥ v1

• Adjacent vertices are placed near.
Chung’s Laplacian
λ2 = min ∑=→?∈A 𝒙 𝑢 − 𝒙 𝑣

𝟐

𝜋= /𝑑=Ds.t. ‖x‖ = 1, x ⊥ v1.

• Important vertices (w.r.t. RW) are placed in the middle.
Nonlinear Laplacian
λ2 = min∑=→?∈A max(𝒙 𝑢 − 𝒙 𝑣 , 0)𝟐s.t. ‖x‖ = 1, x ⊥ v1.
• If x(u) ≤ x(v), then we get no penalty.
• In particular, λ2 = 0 when G is a DAG.

Community Detection: Undirected Graphs
S: Vertex set
vol(S): Total degree of vertices in Scut(S): # of edges between S and V-S
cut(J)
The conductance φ(S) of S isKLM(vol J ,vol QRJ )SSmall conductance→ Good communityφ(S) = 4/12 = 1/3

Community Detection: Undirected Graphs

Cheeger’s inequality (‘70)

λ2/2 ≤ minSφ(S) ≤ √(2λ2)• We can efficiently compute S with φ(S) ≤ √(2λ2) from v2.
• Still widely used.

Community Detection: Digraphs
S: Vertex set
vol(S): Total indegrees + outdegrees of vertices in S
cut+(S): # of arcs from S to V-SKLM(cut S J ,cut S (QRJ))(Directed) conductance φ(S) of S isKLM(vol J ,vol QRJ )Sφ+(S) = 2/12 = 1/6

Community Detection: Digraphs
Cheeger’s inequality for digraphs

λ2/2 ≤ minSφ(S) ≤ 2√λ2
• We can efficiently compute S with φ(S) ≤ 2√𝓡G(x) from x.

Community Detection: Digraphs
Reorder vertices according to the obtained eigenvector in thehigh school network, and plot φ of each prefix set.

• φ is low everywhere = directivity• φ rapidly increases = community

SummaryNonlinear Laplacian for digraphs• Strong connectivity is not needed.
• Eigenpairs are combinatorially interpretable.
• Applications to visualization and community detection.
Future Work• Approximation of λ2.
• Finding a community in time proportional to its size.
• Other applications.