[图数据管理和挖掘]笔记 – 上

参加“ADL33-图数据学科前沿讲习班”的笔记。(下面的所有图都是从各位老师的slides中截取的。)

Big Graph Challenges – Haixun Wang

海勋老师提到,图数据的处理已经热了4,5年了。在刚刚结束的SIGMOD 2013的371个submission中,有44篇是关于图数据处理的。
越来越多的真实的超大规模的图数据出现了:

image

但是现阶段,还没有一个比较general的能应用于大规模的图数据系统出现:

graph-scale

还提到,图数据的处理有个非常大的特点,就是存在大量的join。而传统的DB对于大量join操作的性能是不好的。关于这一点,后面的talk也反复提到了。

总的来说,海勋老师只是给了个泛泛的开头,热个场,并没有太深入。

Graph-based RDF Data Management – Lei Zou

这个talk主要是关于如何处理RDF这种特定的图数据。因为本人对Semantic Web不太感冒,所以没有引起我个人太大的共鸣。但是整个talk还是很有料的,另外,Lei Zou老师主要是从数据库的角度出发,强调scalability和performance,而不是reasoning的那套东西,所以还是听的比较投入。

talk开始交代了一些Semantic Web的基本常识,比如RDFa,RDF中的Triple,SPARQL语言等等。还提到web3.0时代是“connection of data”,这点我倒是比较同意的。未来如何找到各种数据之间的connection绝对是个关键的问题。
此外,还谈谈了Semantic Web的前景,如下图所示,Semantic Web应该还需要十年的时间(more than 10 years):

image

之所以RDF数据处理和graph相关,是因为RDF本身是一条条三元组形式的记录,这些记录可以构成一个非常大的graph,而一个SPARQL查询可以被转换成子图匹配(subgraph matching)的问题。

重点提及了RDF数据存储和管理的整个历史发展过程,从最传统的RDBMS到现在的一些distributed triple store:

image

Graph Search – Shuai Ma

在此之前,我对graph search一无所知。所以马老师的talk,我大概只吸收了那些入门的内容。talk首先介绍了一些应用场景:
Complex object identification
Software plagiarism detection
Transport routing
Recommender systems
Graph search is a useful tool for recommendations
Biological data analysis

Graph Search的定义就是在一个Graph中判断是否包含某个Graph Pattern,并且找出所有match该pattern的子图。
如果将match的含义泛化,那么可以认为很多问题都是Graph Search的问题。

重点介绍了三种类型的graph search:

Cohesive Subgraphs就是查找graph中的凝聚子图。这个在social network中很有用。
凝聚子图的定义有很多种:
clique – 它的问题是: Cliques can overlap(没理解); Too many or too few cliques emerge(没理解); The problem is NP-complete.
所以又出现了一些放宽了限制的定义:
n-clique
n-clan
k-core
其实这些定义和centrality中的degree, closeness, betweenness的定义形式很类似。

Keyword search很重要的一点是,找到了那些节点后需要ranking。

Graph pattern matching细分其实有两类任务:
Subgraph Isomorphism
Graph Simulation
子图同构(Subgraph Isomorphism)它是需要在Graph中找出一个和pattern完全一致的子图。”Keep exact structure topology”。
它的问题是复杂度是NP-complete。而且对于很多场景来说限制太严格了。
“hinder the usability in emerging applications, e.g., social networks”
Graph Simulation我不太了解,但基本的思想是它要比子图同构更宽松。因此复杂度也会随之降低。

image

最后介绍了一些目前用于解决big graph的Graph Search问题常用的方法:
Distributed Processing — 分布式的处理
Incremental Techniques — 增量技术
Data Preprocessing — 预处理,包括:
data sampling
data compression
所谓的compression是指将原图压缩成一个更小的图,然后在小图上做处理。其实就是在做降维。
indexing
data partitioning

Managing Big Graph – Yanghua Shaw

这个talk是我本人收获最多的,可能也是因为之前做了些相关的工作,比较容易产生共鸣。

肖老师首先提到了现在的big graph带来的挑战:
1. 数据量很大
传统的图的算法很多只能够作用于百万级的节点,而现在的很多大图,例如facebook,可能有billion级的节点;
(确实,我看过很多相关的paper,虽然号称是large-scale的算法,但其实也就是百万级的规模。我个人认为百万级和千万级甚至billion级的差别在于是否需要分布式)

2. 网络本身比较复杂
Skewed degree distribution(冥律分布):
节点度数分布的不均衡,会导致unbalance load。这个在我上篇blog中其实已经有提及了。
small world:
小世界现象表示着图的密度很高,一个节点很短的距离范围内都能够覆盖大量的其它节点。如果算法需要去遍历节点的周边,意味着它需要扫描大量节点。
unclear community structures:
社团边界的不清楚,意味着partitioning a graph is hard.

3. 图的操作算法复杂
Real Graphs have Complex Operations:
例如subgraph matching,例如图的clustering/classification,等等,确实大部分的图算法在复杂度上都很可观
Graph Operations need Random Access:
图本身代表了很多的关系,对应到算法上就需要大量的“jump”或者称“random access”,即沿着边从一个节点跳到下一个节点。这从系统角度看是个很cost的事情
Order-dependent logic:
很多的算法因为有顺序执行的关系,所以很难并行化

提及了Hadoop并不适合big graph的处理,它可能只适用于Vertex-Centric这一类的算法:

image

然后分别从Graph Partitioning,Graph Traversal,Graph Queries,Graph Analytics 4个方面举例说明了他们做的工作:

image

Graph Partitioning
肖老师将Graph Partitioning称为最关键的问题,因为其它的方法都需要作用于分布的数据之上,而数据如何分布/partition则直接影响了后续的算法。

partitioning有两个目标:
1. 切分后的各部分包含的节点尽可能相等 – 为了load balance;
2. 各部分之间连接的边尽可能的少 – 为了reduce communication;
当然,实际中,这两个目标是有矛盾的,所以需要tradeoff。

现有方法:
Classical partitioning algorithm – KL [kernighan 72]
Multi-level partitioning solutions – METIS [Karypis95]
Parallelized Multi-level partitioning solutions – ParMetis [Karypis98]

但目前大部分的系统采用的是random partitioning。

一些新的思路:
Repartitioning
Partitioning with replication
Streaming graph partitioning (SGP)

shortest distance query
对于这个问题,给出了一个distance oracle的思路。
所谓distance oracle的意思,就是“Report approximate distance between any two vertices in a graph in constant time by pre-computation”,是一个近似的方法。
例如,可以考虑将这个图应该到一个k维空间上,将计算两点间的shortest distance转换成在k维空间上直接计算亮点的距离。

image

那么如何映射呢?需要选择一些landmark (landmark一般选择betweenness比较高的节点),然后:
Precisely calculate the distance from each landmark to all other vertices by BFS starting from each landmark;
Calculate the coordinates of landmarks by simplex downhill according to the precise distance among landmarks;
Calculate the coordinates of other vertexes by simplex downhill according to the distance from these vertex to each landmark;

Graph Traversal – BFS
Betweenness computation
这两个其实也非常的重要,但是肖老师讲得匆忙,我也没抓到什么太有价值的信息。

相关的slides可以在肖老师实验室主页上找到。

(to be continue.)

Advertisements
相册 | 此条目发表在Large Scale, Social Network分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s