WIXLIB

FASCINATE: Fast Cross-Layer DependencyInference on Multi-Layered NetworksPresented by Chen ChenChen Chen-1-Hanghang TongLei XieLei YingQing HeArizona State University

Multi-Layered Networks are Everywhere!Power GridAS NetworkTransportation NetworkIntra-LayerCross-Layer-2-Infrastructure NetworksCollaboration PlatformsBio SystemsPower GridAS NetworkTransportation NetworkTeam NetworkSocial NetworkInformation NetworkChemical NetworkDrug NetworkDisease NetworkPPI NetworkPower Supply, Control(Power Station Routers)Power Supply, Fuel Supply(Power Station Transportation)Control(Routers Transportation)Membership(Team Employees)SpecializationEmployee InformationComposition(Chemical Drug)Treatment(Drug Disease)Association(Disease PPI)Arizona State University

Cross-Layer Dependency Role: Unique topology characteristic of multi-layerednetworksPower GridPower GridAS NetworkControlTransportation NetworkAS NetworkTransportation Network Importance: Key to multi-layered network mining tasks(e.g. connectivity control, robustness analysis) Challenge: Incomplete cross-layer dependencies-3-Arizona State University

Infer Cross-Layer DependencyPower GridAS NetworkTransportation NetworkNetwork DynamicsIncomplete RecordLimited Accessibility Q1: How to infer the hidden cross-layerdependencies?-4-Arizona State University

Dependencies of Zero-Start nodes Obs.: New nodes are emerging over timePower GridAS NetworkTransportation Network Q2: How to efficiently infer the dependenciesof zero-start nodes?-5-Arizona State University

Roadmap Motivation Q1: Cross-Layer Dependency Inference Q2: Dependencies for Zero-Start Nodes Evaluations Conclusions-6-Arizona State University

Background: A (Simplified) Multi-layeredNetwork ModelControl LayerA four-layered networklayer-layerdependency networkPhysical LayerCommunication Layer A tuple Γ 𝐺, 𝑨, 𝑫 – G: layer-layer dependency network– A: intra-layer connectivity– D: cross-layer dependence-7-Chen Chen, Jingrui He, Nadya Bliss, Hanghang Tong: On the Connectivity of Multi-layered Networks:Arizona State UniversityModels, Measures and Optimal Control. ICDM 2015: 715-720

Q1: Dependency Inference Key Idea 1: Collaborative FilteringDependency Only v1 v2 v3u1u2u3u4u5u6 Rv8 v9 v10u1u2u3u4u5u6 𝑭𝟏 v1 v2 v3 v8 v9 v10𝑭𝟐𝐑 𝑭𝟏 𝑭𝟐 ′Users Routers Movies Transportation Known Ratings Observed Cross-Layer Dependency-8-Arizona State University

Q1: Dependency Inference Key Idea 2: Collaborative Filtering withSide InformationTwo-layered NetworkMovies𝑨𝟏 ( 𝑭𝟏 )𝑨𝟏Transportation NetworkAS Network-9-𝑨𝟐𝐑 𝑭𝟏 𝑭𝟐 ′𝑨𝟐 ( 𝑭𝟐 )Movie-Movie Similarity Transportation Network Social Network AS NetworkArizonaState UniversityKnown Ratings Support from Routers to TransportationNetwork

Node Homophily Assumption: closely connected entitieswithin each layer tend to have similar latentprofilesPower GridAS Networku1Transportation Networku2 𝑭(𝒖𝟏, : ) 𝑭(𝒖𝟐, : ) (min 𝒕𝒓(𝑭′ 𝑫𝑼 𝑼 𝑭) )- 10 -Celebrities Power Plants Users Routers Movies TransportationArizonaState UniversityKnown Ratings, Movie Cast, Fans Observed Cross-LayerDependencies

Q1: Dependency Inference Key Idea 3: Collective Collaborative FilteringActor SimilarityMulti-layered Network𝐀𝟏 𝑭𝟏Actor-Movie Cast𝑫𝟏,𝟑 𝑭𝟏 𝑭𝟑 ′Movie Similarity𝐀𝟑 𝑭𝟑Power GridAS NetworkActor-User Fans𝑫𝟏,𝟐 𝑭𝟏 𝑭𝟐 ′User-Movie Ratings𝑫𝟐,𝟑 𝑭𝟐 𝑭𝟑 ′User SimilarityTransportation Network𝐀𝟐 𝑭𝟐- 11 -Celebrities Power Plants Users Routers Movies TransportationArizonaState UniversityKnown Ratings, Movie Cast, Fans Observed Cross-LayerDependencies

Optimization Problem Objective Function:min𝐹𝑖 0(𝑖 1, ,𝑔) 𝐽 𝑊𝑖,𝑗 (𝐷𝑖,𝑗 𝐹𝑖 𝐹𝑗 ′) 2𝐹 𝑖,𝑗:𝐺 𝑖,𝑗 1Matching observed cross-layer dependencies𝛼 𝑡𝑟(𝐹𝑖 ′(𝑇𝑖 𝐴𝑖 )𝐹𝑖 ) 𝛽 𝐹𝑖 2𝐹𝑖Node homophily𝑖Regularization Challenge: Not jointly convex w.r.t. 𝐹𝑖(𝑖 1, ,𝑔) !Hard to find global optimal solution! Q: How to find a local optimal?- 12 -Arizona State University

FACINATE: Proposed Solution Obs.: J becomes convex if we fix all butone (e.g. Fi) latent matrices Method: Block coordinate descentFixing all other 𝐹𝑗(𝑗 𝑖) , the objective function w.r.t. 𝐹𝑖 ismin𝐹𝑖 0 𝐽𝑖 𝑊𝑖,𝑗 (𝐷𝑖,𝑗 𝐹𝑖 𝐹𝑗 ′) 2𝐹 𝛼𝑡𝑟(𝐹𝑖 ′(𝑇𝑖 𝐴𝑖 )𝐹𝑖 ) 𝛽 𝐹𝑖 2𝐹𝑗:𝐺 𝑖,𝑗 1Cross-layer dependencies that involvelayer 𝑖Homophily inlayer 𝑖LayerregularizationJi is convex w.r.t. Fi Multiplicative Update Rules:𝑋(𝑢, 𝑣)𝐹𝑖 (𝑢, 𝑣) 𝐹𝑖 (𝑢, 𝑣)𝑌(𝑢, 𝑣)- 13 -𝑋 σ𝑗:𝐺 𝑖,𝑗 1(𝑊𝑖,𝑗 𝑊𝑖,𝑗 𝐷𝑖,𝑗 )𝐹𝑗 𝛼𝐴𝑖 𝐹𝑖𝑌 σ𝑗:𝐺 𝑖,𝑗 1(𝑊𝑖,𝑗 𝑊𝑖,𝑗 (𝐹𝑖 𝐹j ′))𝐹𝑗 𝛼𝑇𝑖 𝐹𝑖 𝛽Arizona State University

Roadmap Motivation Q1: Cross-Layer Dependency Inference Q2: Dependencies for Zero-Start Nodes Evaluations Conclusions- 14 -Arizona State University

Q2: Dependencies for zero-start nodes𝐴1Power Grid𝐹𝑖 𝐹 𝑖 (𝑖 1)𝒔AS Network𝐴መ 1 𝐴1 𝑠′𝑠 0𝐹1 𝐹 1 [𝐹 1(𝑛1 𝑟 ),𝑓]Existing Nodes New NodeTransportation NetworkDecompose Objective Function𝑗Ƹ 𝐽 𝐽1𝐽: objective function without zero-start node𝑛1𝐽1 : 𝛼 σ𝑣 1𝒔 𝑣 𝑓 𝐹 1 (𝑣, : ) 22 𝑓 22Local Neighbors- 15 -Arizona State University

Q2: Dependencies for zero-start nodes Objective Function with Zero-Start Node:𝑚𝑖𝑛𝐹 𝑖 0 𝑗Ƹ 𝐽 𝐽1𝐽: objective function without zero-start node𝑛1𝐽1 : 𝛼 σ𝑣 1𝒔 𝑣 𝑓 𝐹 1 (𝑣, : ) 22 𝑓 22 Local Search Assumption:𝐹 1𝑛1 𝑟 𝐹1𝐹 𝑖 𝐹𝑖 (𝑖 1) Solution:𝑚𝑖𝑛𝐹 𝑖 0 𝑗Ƹ 𝐽 𝐽1𝛼𝒔𝐹1 𝑓 𝑛1𝛽 𝛼 σ𝑣 1𝒔(𝑣)- 16 -𝑚𝑖𝑛𝑓 0 𝐽1 sub. to 𝐹 1𝑛1 𝑟 𝐹1 Only related to zero-startnode’s local neighbors!Arizona State University

Roadmap Motivation Q1: Cross-Layer Dependency Inference Q2: Dependencies for Zero-Start Nodes Evaluations Conclusions- 17 -Arizona State University

Experimental Set-up 2629,86128,023,500 Evaluation Objectives:– Effectiveness: How accurate is FACSINATE?– Efficiency: How fast is FACSINATE?- 18 -Arizona State University

Effectiveness of FASCINATE (Q1)Cross-layer dependency inference on BIO datasetFASCINATE performs best!- 19 -MAP: Mean Average Precision R-MPR: Reverse Mean Percentage RankingArizonaStateatUniversityHLU: Half-Life Utility AUC: Area Under ROC Curve Prec@K:PrecisionK

Parameter Studies Parameters: 𝛼, 𝛽, 𝑟min𝐹𝑖 0 𝐽 𝑖,𝑗:𝐺 𝑖,𝑗 1 𝑊𝑖,𝑗 (𝐷𝑖,𝑗 𝐹𝑖 𝐹𝑗 ′) 2𝐹 𝜶 𝑡𝑟(𝐹𝑖 ′(𝑇𝑖 𝐴𝑖 )𝐹𝑖 ) 𝜷 𝐹𝑖 2𝐹𝑖𝑖(𝒓: rank of 𝐹𝑖 (𝑖 1, ,𝑔) )Impact of 𝛼 and 𝑟Impact of 𝛽 and 𝑟Impact of 𝛼 and 𝛽FASCINATE is stable in wide range of parameter settings!- 20 -Arizona State University

Effectiveness of FASCINATE-ZERO (Q2) FASCINATE-ZERO vs. FASCINATEFASCINATE-ZERO: similar performance, faster speed!- 21 -Arizona State University

ScalabilityFASCINATE (Q1)Linear- 22 -FASCINATE-ZERO (Q2)Sub-linearArizona State University

Roadmap Motivation Q1: Cross-layer Dependency Inference Q2: Dependencies for Zero-Start Nodes Evaluations Conclusions- 23 -Arizona State University

Conclusions Cross-Layer Dependency Inference– Key Ideas: Collective Collaborative Filtering Node Homophily Local Search (for zero-start nodes)– Methods: FASCINATE & FASCINATE-ZERO Results– Effectiveness: 8.2%-41.9% over best competitors– Efficiency: linear (FASCINATE), sublinear (FASCINATE-ZERO) More in paper– Variants– Convergence analysis & Effectiveness results Code: [http://www.public.asu.edu/ cchen211]- 24 -Arizona State University

FASCINATE: Fast Cross-Layer Dependency Inference on Multi-Layered Networks Presented by Chen Chen - 1 - Chen Chen Hanghang Tong Lei Xie Lei Ying Qing He. Arizona State University Multi-Layered Networks are Every