大数据图分析系统

需积分: 10 102 浏览量更新于2024-07-17 收藏 1.46MB PDF 举报

" Systems for Big Graph Analytics 由 Da Yan, Yuanyuan Tian 和 James Cheng 在 2017 年撰写，是 Springer Briefs in Computer Science 系列的一部分，该系列由多位知名计算机科学领域的专家编辑。书中探讨了大规模图数据分析系统的重要性和相关技术。" 在大数据时代，图数据分析（Graph Analytics）已成为研究和解决复杂网络问题的关键工具。"Systems for Big Graph Analytics" 这本书聚焦于处理大规模图数据的系统和方法，这对于理解现实世界中的社交网络、互联网结构、生物信息学网络以及各种其他复杂关系网络至关重要。图数据结构通过节点和边来表示实体和它们之间的关系，使得分析这些关系变得更加直观和有效。书中的内容可能涵盖了以下关键知识点： 1. **图数据模型**：介绍如何用图模型来表示现实世界的问题，包括节点、边和属性，以及如何设计有效的数据结构来存储和检索大规模图数据。 2. **图算法**：讨论经典的图算法如最短路径、遍历算法（如深度优先搜索和广度优先搜索）、社区检测算法（如 pagerank 和 Louvain 方法）以及新的优化算法，用于在大规模图上高效执行。 3. **分布式图计算框架**：如 Apache Giraph、Pregel、GraphX 和 PowerGraph 等，这些都是用于处理大规模图数据的分布式计算系统，它们的设计原理和应用案例可能会在书中详细阐述。 4. **并行与并发处理**：讲述如何利用多核处理器或GPU进行图计算的加速，以及如何通过并发策略优化图算法的性能。 5. **内存计算与数据压缩**：针对大数据量的挑战，可能讨论内存管理和数据压缩技术，以提高处理速度和降低存储需求。 6. **实时与流式图分析**：介绍如何处理不断变化的数据流，以及实时图更新和分析的挑战与解决方案。 7. **应用案例**：书中可能包含来自不同领域的实例，如社交网络分析、推荐系统、网络安全和生物信息学等，展示图分析如何解决实际问题。 8. **性能评估与优化**：对不同的图分析系统进行性能比较，以及如何根据特定需求进行系统优化。 9. **未来趋势**：展望图数据分析领域的未来发展方向，如机器学习与图神经网络在图分析中的融合，以及云计算和边缘计算对图数据分析的影响。 "Systems for Big Graph Analytics" 是一本深入探讨大规模图数据处理的书籍，对于理解和掌握这个领域的理论知识和技术实践有着重要的指导价值。对于数据科学家、软件工程师、计算机科学研究者以及对大数据分析感兴趣的读者来说，这本书提供了一个全面且深入的视角去理解如何分析和挖掘隐藏在复杂网络中的信息。

2.1 Google’s Pregel 9

Constraints 1–3 offers good load balancing and linear cost at each superstep, while

Constraint 4 controls the total running time. Note that a Pregel algorithm with a large

number of supersteps is inefﬁcient since each superstep requires a global barrier at

the end, which incurs round-trip network delay (assuming that the reliable transport-

layer protocol TCP is adopted).

For some graph problems, the vertex-grained requirements of BPPA can be too

strict, and we can only achieve overall linear space usage, computation cost, and

communication cost (still in O.log jVj/ rounds). We call such a Pregel algorithm

simply as a practical Pregel algorithm (PPA).

The Hash-Min algorithm presented in Sect. 2.1.1 is not a PPA, since it takes

O.ı/ supersteps; if the whole graph is just a long path and the vertex with the

smallest ID is on one end of the path, Hash-Min runs for jEj supersteps. To achieve

the O.log jVj/-superstep bound, it is usually necessary to use the pointer jumping

(a.k.a. path doubling) technique where a vertex needs to send messages to non-

neighbors. Pointer jumping is used in many Pregel algorithms, such as the S-V

algorithm for computing CCs [31], the algorithm of [31] for computing biconnected

components, and the algorithm of [21] for computing minimum spanning forest.

We now illustrate the idea of applying pointer jumping in Pregel by looking at two

PPAs.

Example 2.3 (List Ranking) List ranking is an important step of the Euler tour

technique and ﬁnds wide applications such as computing biconnected compo-

nents [31]. The problem is deﬁned as follows. We assume elements in a list are

linked backwards from the tail to the head (the algorithm for forward linking is

similar). Consider a linked list L with n vertices (or items), where each vertex v is

associated with a value val.v/ and a link to its predecessor pred.v/. The vertex v

at the head of L has pred.v/ D null. For each v 2 L, let us deﬁne sum.v/ to be the

sum of the values of all the vertices from v following the predecessor link to the

head. The goal is to compute sum.v/ for every v 2 L

.Ifval.v/ D 1 for any v 2 L

(see Fig. 2.1), then sum.v/ is simply the rank of v in the list, i.e., the number of

vertices preceding v plus 1. Note that vertices of the input data are stored in a DFS

in arbitrary order.

We now describe a BPPA for list ranking. Initially, each vertex v assigns

sum.v/ val.v/. Then in each round, each vertex v does the following: If

pred.v/ ¤ null, v sets sum.v/ sum.v/ C sum.pred.v// and pred.v/

pred.pred.v//; otherwise, v votes to halt. The if-branch is accomplished in three

supersteps: (1) v sends a message (whose value is its own ID) to u D pred.v/

requesting for the values of sum.u/ and pred.u/;(2)u sends back the requested

values to each requesting vertex v; and (3) v updates sum.v/ and pred.v/ using the

received values. This process repeats until pred.v/ D null for every vertex v,at

which point all vertices vote to halt and we have sum.v/ as desired.

Figure 2.1 illustrates how the algorithm works. Initially, objects v

–v

form

a linked list with sum.v

/ D val.v

/ D 1 and pred.v

/ D v

i1

. Let us now

focus on v

. In Round 1, we have pred.v

/ D v

and so we set sum.v

sum.v

/Csum.v

/ D 1C1 D 2 and pred.v

/ pred.v

/ D v

. One can verify the

2.2 Pregel-Like Systems 11

The algorithm repeats these two steps until no vertex v has DŒv updated in

a round (checked by using aggregator), by which time every vertex is in a star

(i.e., tree of height 1), and each star corresponds to a connected component. Since

DŒv monotonically decreases during the computation, at the end DŒv equals the

smallest vertex in v’s CC (which is also the root of v’s star). Similar to the request-

respond operation in list ranking, each step of S-V can be formulated in Pregel as

a constant number of supersteps, and since shortcutting guarantees the O.log jVj/-

round bound, the algorithm is a PPA. However, it is not a BPPA since a parent

vertex may communicate with many more vertices than its own neighbors (e.g., a

root). Moreover, a vertex v communicates with DŒv, which may not be its direct

neighbor.

2.2 Pregel-Like Systems

In this section, we introduce the various off-the-shelf open-source Pregel-like

systems, so that readers can get familiar with their features and be able to choose a

proper one to use according to their needs. There are two critical aspects to consider

when choosing a Pregel-like system: (1) system efﬁciency and the supported

optimizations, (2) software robustness which is often decided by the amount of users

and the technical group supporting the system.

At the early stage, as Google did not open source Pregel, other companies in need

of a vertex-centric graph system started to build one of their own. The collaborative

effort gave rise to an open-source system called Giraph,

similar to the effort

of open-source Google File System [8] and MapReduce [6] over 10 years ago

which created Hadoop.

Giraph was initiated as a side project at Yahoo!, and made

efﬁcient and popular due to improvements by Facebook researchers. Giraph was

written in Java, and thus naturally integrates with Hadoop. It is probably the most

popular Pregel-like system for the time being, with project team members spanning

Facebook, LinkedIn, Twitter, Pivotal, HortonWorks, etc. While there exists some

minor optimizations to the original model of Pregel, the main goal of Giraph is to

open-source Pregel.

Another system, GraphX [10], provides vertex-centric API for graph processing

on top of Spark [34], a general-purpose big data system. The beneﬁt of using

GraphX is that, for a complex task where graph processing is only part of it, the

whole task can be written in Spark to avoid data import/export overhead between

graph and non-graph jobs, hence improving the overall end-to-end performance.

For graph processing alone, we recommend Giraph over GraphX, since we found

that GraphX requires signiﬁcantly more memory space which translates to renting

more machines in a cloud service, and GraphX is also slower since its underlying

http://giraph.apache.org/.

http://hadoop.apache.org/.

12 2 Pregel-Like Systems

engine is a dataﬂow engine not dedicatedly designed for vertex-centric graph

processing. Also, Spark’s advantage is mainly enjoyed by operations with “narrow

dependency”, such as condition-based ﬁltering of data items, where a partition

of ﬁltered data can be directly generated in a machine without communicating

with other machines, and if the partition is lost, it can be recovered from the

data partition that it ﬁlters from. Pregel’s vertex-wise message passing has “wide

dependency”, where network communication dominates the cost and discounts the

beneﬁt of memory caching of data. Fault tolerance in GraphX also reverts back

to checkpointing, since a lost data partition (e.g., messages received by a set of

vertices) is often contributed by many (if not all) previous data partitions, which has

to be recovered ﬁrst.

We focus here more on the academic perspective, i.e., novel technical contribu-

tions (e.g., optimization techniques) on top of Pregel’s original model. Numerous

systems have been developed to optimize Pregel’s simple model from various

aspects including communication mechanism, load balancing, out-of-core support,

fault recovery, and on-demand querying. While some systems (often just prototypes)

from the academia are not as robust as those from the industry (if ever open-sourced)

due to lack of testing and small number of users, there are good systems with high

performance such as GraphLab [9, 15] (now commercialized as the company

Turi

and focuses more on machine learning), and the graph processing platform

BigGraph@CUHK.

Both GraphLab and BigGraph@CUHK were implemented in C++. In contrast,

Giraph (resp. GraphX) was implemented in Java (resp. Scala) that runs on top

of JVM. Unfortunately, Java is ill-suited to hold a large number of objects (e.g.,

vertices) in memory due to the overhead of GC (Garbage Collection) and a higher

per-object memory footprint [3]. In fact, the old Giraph version maintains vertices,

edges and messages as native Java objects, which consume excessive memory

and garbage collection overhead; Facebook researchers solved the problem by

serializing the edges and messages into byte arrays to reduce the number of

objects [5]. We remark that while Java (and Scala) allows system developers to

be more productive (important for commercial purposes which play an important

part in inﬂuencing the Big Data market), C++ permits higher efﬁciency. The

programming simplicity of both C++ and Java solutions are the same as their end-

users program with the same vertex-centric API adopted from Pregel.

The rest of this section is organized according to the optimization aspects of

existing Pregel-like systems, which are more from the academic perspective and

provides a big picture of the various possibilities beyond the basic model of Pregel.

https://turi.com/.

http://www.cse.cuhk.edu.hk/systems/graph/.

2.2 Pregel-Like Systems 13

2.2.1 Communication Mechanism

In Sect. 2.1.1, we described two algorithms for computing PageRanks and connected

components, whose compute(.) is distributive and message combiner is applicable;

in Sect. 2.1.2, we presented the S-V algorithm where a parent vertex v needs to

respond its attribute to all requesting children vertices (that are not necessarily direct

neighbors), and message combiner is inapplicable. Existing optimization techniques

are mostly designed for the former type of Pregel algorithms, while Pregel+ [29]

provides separate techniques for both types of algorithms.

Giraph [5] is improved by Facebook from its earlier version. The improvements

including multithreading support, vertex serialization (mentioned before), and a

superstep splitting technique to reduce the memory space consumed by buffering

messages. Superstep splitting is only applicable to Pregel algorithms whose com-

pute(.) is distributive. The technique splits a message-heavy superstep into several

steps, so that the number of messages transmitted in each step is reduced. The

message values received by each vertex are directly aggregated (i.e., combined but

at receiver side) and there is no need to buffer them. MOCgraph [35] eliminates the

memory space consumed by messages, through a more aggressive message online

computing (MOC) model that lets in-memory vertices absorb incoming messages

directly without buffering them.

Pregel+ [29] developed two techniques to reduce the number of messages. The

ﬁrst technique is designed for combiner-applicable algorithms, and creates mirrors

of each high-degree vertex v on all other machines that contain v’s neighbor(s). The

adjacency list of v is partitioned among its mirrors on different machines. To see

how vertex mirroring reduces communication, consider the Hash-Min algorithm:

when a high-degree v broadcasts a.v/ to all its neighbors, it only needs to send

a.v/ to every mirror, which then forwards the value to all local neighbors. The

message value may also be post-processed by a mirror using the edge value in local

adjacency list. Since each machine has at most one mirror for v, the total number

of messages sent by v is bounded by the number of machines which can be much

smaller than v’s degree. However, since a mirrored vertex forwards its value directly

to its mirrors, it loses the chance of sender-side message combining, and thus low-

degree vertices should not be mirrored. Yan et al. [29] prove a degree threshold to

guide vertex mirroring that minimizes the number of messages. GPS [20] provides a

similar technique called LALP but provides no analysis on the tradeoff with message

combining. In fact, it simply does not perform sender-side message combining at all.

Pregel+’s second technique extends the basic API of Pregel with a request-

respond functionality, which is designed for pointer jumping algorithms like S-V

where a vertex needs to communicate with a large number of other vertices that may

not be its neighbors. For example, consider later rounds of S-V, where a root vertex

r needs to communicate with many other vertices v in r’s component with DŒv D r.

Here, each vertex v will send requests to r for DŒr in a superstep, and r

will receive

these requests and respond DŒr back in the next superstep. The request-respond API

allows v to pose requests to r, and each machine combines all local requests to r as

剩余92页未读，继续阅读

weixin_38290023

粉丝: 4
资源: 224

大数据图分析系统

Big.Data.Technologies.and.Applications

介绍一下PyTorch-BigGraph

Wait-for Graph

x = [] edge_index = [] edge_attr = [] for node in graph.nodes(): node_attrs = [] for label in graph.nodes[node]['labels']: node_attrs.append(label) for prop in graph.nodes[node]['source_props']: node_attrs.append(prop) x.append(node_attrs)代码详细注释

Compare adjacency matrix and adjacency list for graph representation. How you choose which presentation to use depending on task and graph?

Dual graph convolutional network

Towards Generalizable Neural Networks for Graph Applications发表在哪里

解释这行代码：connected_graph = [connected_graph.subgraph(item_graph).copy() for item_graph in nx.connected_components(connected_graph) if len(item_graph) > 100]

最新资源