1、大數據技術基礎培訓1GraphLab 技術培訓2Social Media3圖用來編碼/描述知識和聯系：:Big: billions of vertices and edges and rich metadataAdvertisingScienceWeb人事實產品興趣想法4圖是機器學習和數據挖掘的重要基礎之一發現有影響力的人或者信息發現社區或者社交圈或者團伙精準廣告/產品定位 復雜數據/知識依賴性建模圖并行算法的特性DependencyGraphIterativeComputationWhat I LikeWhat My Friends LikeFactored Computation 為什么M

2、apReduce不合適Map-Reduce不能高效表示依賴圖User must code substantial data transformations Costly data replicationIndependent Data RowsSlowProcessor為什么MapReduce不合適(2)Map-Reduce 無法高效描述迭代算法:DataDataDataDataDataDataDataDataDataDataDataDataDataDataCPU 1CPU 2CPU 3DataDataDataDataDataDataDataCPU 1CPU 2CPU 3DataDataDat

3、aDataDataDataDataCPU 1CPU 2CPU 3IterationsBarrierBarrierBarrier為什么MapReduce不合適(3)圖算法通常只有一部分數據（子圖）需要計算:DataDataDataDataDataDataDataDataDataDataDataDataDataDataCPU 1CPU 2CPU 3DataDataDataDataDataDataDataCPU 1CPU 2CPU 3DataDataDataDataDataDataDataCPU 1CPU 2CPU 3IterationsBarrierBarrierBarrier為什么MapRedu

4、ce不合適(4)Hadoop Map/Reduce沒有為迭代算法優化DataDataDataDataDataDataDataDataDataDataDataDataDataDataCPU 1CPU 2CPU 3DataDataDataDataDataDataDataCPU 1CPU 2CPU 3DataDataDataDataDataDataDataCPU 1CPU 2CPU 3IterationsDisk PenaltyDisk PenaltyDisk PenaltyStartupPenaltyStartup PenaltyStartup Penalty10圖并行算法抽象A user-def

5、ined Vertex-Program runs on each vertexGraph constrains interaction along edgesUsing messages (e.g. Pregel PODC09, SIGMOD10)Through shared state (e.g., GraphLab UAI10, VLDB12)Parallelism: run multiple vertex programs simultaneously11示例Whats the popularityof this user?Popular?Depends on popularityof

6、her followersDepends on the popularity their followersPageRank AlgorithmUpdate ranks in parallel Iterate until convergenceRank of user iWeighted sum of neighbors ranks12BarrierPregel (Giraph)Bulk Synchronous Parallel Model:ComputeCommunicate14The Pregel AbstractionVertex-Programs interact by sending

7、 messages.iPregel_PageRank(i, messages) : / Receive all the messages total = 0 foreach( msg in messages) : total = total + msg / Update the rank of this vertex Ri = 0.15 + total / Send new messages to neighbors foreach(j in out_neighborsi) : Send msg(Ri * wij) to vertex jMalewicz et al. PODC09, SIGM

8、OD1015The GraphLab AbstractionVertex-Programs directly read the neighbors stateiGraphLab_PageRank(i) / Compute sum over neighbors total = 0 foreach( j in in_neighbors(i): total = total + Rj * wji / Update the PageRank Ri = 0.15 + total / Trigger neighbors to run again if Ri not converged then foreac

9、h( j in out_neighbors(i): signal vertex-program on jLow et al. UAI10, VLDB12自然圖16Power-Law Degree Distribution冪律分布 長尾分布17Power-Law Degree DistributionTop 1% of vertices are adjacent to50% of the edges!High-Degree VerticesNumber of VerticesAltaVista WebGraph1.4B Vertices, 6.6B EdgesDegreeMore than 10

10、8 vertices have one neighbor.Asynchronous Executionrequires heavy locking (GraphLab)18Challenges of High-Degree VerticesTouches a largefraction of graph(GraphLab)Sequentially processedgesSends manymessages(Pregel)Edge meta-datatoo large for singlemachineSynchronous Executionprone to stragglers (Preg

11、el)19Power-Law Degree Distribution“Star Like” MotifPresidentObamaFollowers20Power-Law Graphs are Difficult to PartitionPower-Law graphs do not have low-cost balanced cuts Leskovec et al. 08, Lang 04Traditional graph-partitioning algorithms perform poorly on Power-Law Graphs.Abou-Rjeili et al. 06CPU

12、1CPU 2Machine 1Machine 221Split High-Degree verticesNew Abstraction Equivalence on Split VerticesPowerGraphProgramFor ThisRun on ThisGather InformationAbout NeighborhoodUpdate VertexSignal Neighbors &Modify Edge Data22A Common Pattern forVertex-ProgramsGraphLab_PageRank(i) / Compute sum over neighbo

13、rs total = 0 foreach( j in in_neighbors(i): total = total + Rj * wji / Update the PageRank Ri = 0.1 + total / Trigger neighbors to run again if Ri not converged then foreach( j in out_neighbors(i) signal vertex-program on j23GAS DecompositionY+ + YParallelSumUser Defined:Gather( ) Y1 + 2 3YGather (R

14、educe)Apply the accumulated value to center vertexApplyUpdate adjacent edgesand vertices.ScatterAccumulate information about neighborhoodY+ User Defined:Apply( , ) YYYYUpdate Edge Data &Activate NeighborsUser Defined:Scatter( ) YY24PageRank in PowerGraphPowerGraph_PageRank(i)Gather( j i ) : return w

15、ji * Rjsum(a, b) : return a + b;Apply(i, ) : Ri = 0.15 + Scatter( i j ) :if Ri changed then trigger j to be recomputedMachine 2Machine 1Machine 4Machine 325Distributed Execution of a PowerGraph Vertex-Program1234+ + + YYYYYYYYGatherApplyScatterMasterMirrorMirrorMirror26Minimizing CommunicationYYYA v

16、ertex-cut minimizes machines each vertex spansPercolation theory suggests that power law graphs have good vertex cuts. Albert et al. 2000Communication is linear in the number of machines each vertex spansNew Approach to PartitioningRather than cut edges:we cut vertices:27CPU 1CPU 2YYMust synchronize

17、 many edgesCPU 1CPU 2YYMust synchronize a single vertexNew Theorem:For any edge-cut we can directly construct a vertex-cut which requires strictly less communication and storage.System DesignImplemented as C+ APIUses HDFS for Graph Input and OutputFault-tolerance is achieved by check-pointing Snapsh

18、ot time 5 seconds for twitter network28EC2 HPC NodesMPI/TCP-IPPThreadsHDFSPowerGraph (GraphLab2) SystemImplemented Many AlgorithmsCollaborative FilteringAlternating Least SquaresStochastic Gradient DescentSVDNon-negative MFStatistical InferenceLoopy Belief PropagationMax-Product Linear ProgramsGibbs SamplingGraph Analyti