Axton

大数据'18 图数据流的模型、算法和系统

· Axton

1.大规模流数据的机遇与挑战

图模型的点、边元素非常适用于建模复杂数据中的对象以及对象间的关联和交互，点和边上的属性、标签以及相关数据等的自由定义使得图模型能够很容易地以统一的形式表达不同的对象及其间的交互行为。

图模型非常适合用来建模大规模复杂数据。图模型上的计算却很难应对图数据高速更新的场景。

数据流中的元素往往具有统一简单的格式，并且元素之间相对独立，缺少对对象关联的建模。数据流模型的相关算法很难扩展到需要图模型建模的复杂数据上。

人们急需一种既能够为复杂数据建模，又能够应对更新挑战的新的数据模型、技术来满足相应的信息管理需求。

2.流计算系统

这些流系统和流计算库的核心思想都是针对流式的输入利用集群进行协作计算，而整体的数据依赖所形成的框架则为一个有向无环图，因此集群的整体协作更像是流水线的协作，计算框架中的数据依赖所形成的数据流动方向基本上是单一既定的。

对于很多图计算而言，计算的逻辑并不是流水线式的流系统能容易处理 的 。图具有很强的表达能力，数据与数据之间的关联紧密，路径、连通分量等图计算使数据间的独立性比较低，单条边的变化可能对整个图的结构特征产生全局的影响。而且，图数据计算中的中间结果较多（如子图查询中的部分解），在分布式集群下的传输代价很高。因此，流式系统往往难以支撑大规模图数据流的计算。

3.图数据流模型

3.1 图的流式计算

定义：给定一个静态的图，在一遍或多遍顺序地读取对应的图数据的过程中，获得预期数据信息或完成既定操作的计算问题。

  • 关注的重点主要是在空间有限无法载入整个大图时，如何多次遍历图数据完成相应图计算
  • 流式计算涉及很多经典的图计算问题，包括多种图的属性特征计算和相关的图结构操作等
  • 图流式访问的研究问题包含众多图计算的经典问题
    • 三角形计算
      • Bar-YossefZ等人1结合relative近似和ratio-近似，提出了一个基于归约（reduction）的流式访问模型下的流算法，其中就以三角形计数流算法作为应用来分析，主要提到了两种流访问的形式：
        • 一种是以边为项的邻接边流（adjacency流），边的前后顺序任意；
        • 另一种是以点及其邻居的星状点流（incidence流），每个项是一个顶点及其邻居形成的星状结构。
        • 其后的聚焦在相同问题的两个工作2 3基本沿着近似的思路以及adjacency流和incidence流的模型研究流式访问的三角形计数问题，并给出了更优的时间和空间上的相应算法的复杂度
    • 可达性
      • UnelG等人4使用区间标记解决流式访问的图可达性问题。
        • 首先在必要时对图进行可达性上等价的去环转化，转化过程是线性的。
        • 其次，根据图的去环转化的过程将顶点从前到后打上时间标签，然后流式访问时就按这个时间标签从前到后进行，也就是说这个图数据流模型是设定了流的顺序进行访问的，因为目标在于对大图的可达性的计算，所以这种假设除了离线的时间开销外并没有实际限制。
        • 这种情况下，去环的图可以转化为树，从而将图数据流上的可达性转化为树上的可达性问题，而显然后者是有高效算法的，而且树的空间效率相比图也有很大的提高。
    • 最短路径
      • 有向图流式访问上的最短路径问题最早是在DemetrescuC等人5的一个工作中提出的，是图数据流上空间复杂度和计算所需的遍历次数的权衡问题下的一个图算法的应用。
      • 研究的结论是在给定比特的空间下，有向图的单源最短路径问题可以在\(O(n·logn)\)次遍历过程中解决。

有学者将这类图的流式计算称为图数据流6，但考虑到数据仍是已知的静态图，只是读取的方式是流式的，因此本文将这类能够多遍顺序读取图的计算模型称为图的流式计算模型。

  • 图的流式计算并不能满足当前大规模复杂数据流的计算需求
    • 大规模复杂数据流很难进行多遍读取。图的流式计算中，全局的数据是给定的，而当前应用中实时产生的大量图结构数据则是无限增长的。
    • 流式计算很难应对数据的过期更新操作。图的流式计算显然并不支持数据的删除更新。

以节约内存为初衷而出现的图的流式计算，尽管结合了图模型和类似于数据流模型的流式计算，但显然并不适用于大规模图结构数据流的场景。

3.2 图数据流算法

已有的图数据流模型可以分为 3 种

  • 第一种是基于边流，即边的增删的图数据流。
    • SongCY等人7提出图数据流下的强仿真计算，对应的图数据流定义为一个包含顶点集、边集、标签集以及时间戳函数的有向图，其中流动的元素为按时间戳先后顺序排列的边，并且在边流上引入了时间窗的概念。
    • AngelA等人8最先研究了在实时更新的边流上维护密集子图的算法，其边流定义为一个无限序列，序列中的每个元素为给定边及其边权的变化值（增/减）。边本身没有时间戳的概念，但是边权更新的操作带有时间戳。
    • 此外，FANWF等人9以及ChoudhuryS等人10各自的图数据流子图同构中的模型均属于第一种模型。
  • 第二种是基于子图流，即数据流中的元素为一个个小的子图，边本身没有时间戳的概念，而流中的子图元素才有。
    • IBMWatson研究中心的AggarwalCC等人11利用Min-Hash的相似度衡量方法，将以子图流为形式的图数据流采样成一个静态的抽样集，进而把研究图数据流上的子图模式挖掘转换成了静态的抽样集的频繁模式挖掘的问题。
    • 这个工作中的图数据流模型不支持删除操作，只考虑不断新增的小图，这些小图是作为整个图数据流对应的子图而定义的，彼此之间并不是独立的图。
  • 第三种则是图数据流中，元素是定义在不同点或边集上的独立图数据。
    • ValariE等人12提出了一个给定动态的大图集合的模型，即大图的数量是一个固定的常数，每次集合都将按增加一个新大图、删除一个最旧的大图的方式更新，进而形成动态的大图集合，然后在大图集合上研究Topk的密集子图的计算算法。
    • 值得注意的是，这个图数据流模型中，不同的大图是定义在不同的顶点集之上的，并不存在这些大图的公共超图的语义。

3.3 图数据流模型定义

数据流模型下的数据元素为图模型定义的元素，图数据中点的意义主要通过边来体现，孤立点在现实中的意义有限，给定一个图的边集就能明确地获得非孤立点的点集。

图数据流：图数据流是一个无限地随时间不断变长的边序列，其中每条边在序列中都有一个对应的时间戳，序列中边的时间戳从前往后是非降序的。

以无限边序列定义的图数据流更具一般性和统一性。

现实应用高速生成数据的同时往往伴随已有数据的高速失效。例如利用社交网络数据进行广告投放时，过时数据的参考价值显然没有新近数据高，而大量的过时数据又会带来高的处理开销，因此，往往可以利用时间窗的概念来聚焦更有时效性的数据。时间窗主要分为两种：基于数据规模的时间窗13和基于时间跨度的时间窗14

时间窗：给定一个图数据流，基于数据规模的时间窗定义为包含最近的给定N条数据边的边序列区间，时间窗内的数据则是最近的N条边；基于时间跨度的时间窗定义为以当前时间为结尾的一个给定时间段\((T_1,T_2)\)内的数据边所形成的边序列区间，而窗口内的边即为过去\(T_2\)-\(T_1\)时间内的所有数据边。

3.4 图数据流与动态图

动态图是指给定一个大图，在大图上出现数据增删的动态行为的模型。

图数据流具有的时间信息更贴合现实世界的交互与联系，而动态图强调图结构随时间的变化，并不一定强调数据自身的时间信息。

4.图数据流的研究前景：算法和系统

传统的图计算的问题在图数据流模型下仍然会有研究价值，包括三角形计算15 16、最短路径17 18、子图查询19、子图挖掘20以及图分类21、图聚类22等。

4.1 问题的角度

  • 图数据流的一个非常本质的特征就是边的时间信息。
    • 图数据流的查询问题可以引入时序的限制。
      • 例如，在子图查询中引入对边的时序限制7。
    • 引入基于边的时间间隔限制等，以丰富图数据流相关查询的语义
  • 利用图数据流的时间维度分析和挖掘数据的变化行为。
  • 充满挑战但又有极大研究价值的图数据流上的行为预测，即根据已有的图数据流上的数据分布、行为变化，综合关联的结构信息，预测未来一段时间可能出现的图数据特征，包括分布、关联等。
    • 例如，在交通网络上将交通站点建模成顶点，站点间的车流建模成边，这个模型下一个值得研究的问题就是如何根据过去几个小时的车流信息预测未来一个时间段内各条道路可能的车流密度。
    • 在网络信息传输管道上，如何根据当前的网络状况预测接下来的网络流量拥堵情况，进而进行更合理的路由调度等，也是值得研究的问题。

4.2 方法的角度

核心挑战：加速计算带来的更新开销

  • 以图数据流上的子图查询为例
    • 如果通过构建复杂的索引来加速子图查询，那么在数据更新时必然需要更新相应的索引。如果不构建索引，则更新发生时，为了处理子图查询需要重新进行计算，而实际上一次更新往往涉及的只是局部的数据，完全重新计算将会有大量计算结果同上一个时间点的计算结果重叠，造成冗余计算。
    • 处理图数据流上的计算的关键是如何避免冗余计算，同时还能加速查询的响应。
      • 需要考虑保存哪些已有的计算结果；
      • 在确定需要保存的计算结果上，要相应地保存组织的策略，即如何优化空间开销。
  • 图数据流计算的首要研究思路就是
    • 加速计算的中间结果的选取与保留数据的组织形式；
    • 利用并行技术加速图数据流的更新与计算。

4.3 图数据流管理系统

图数据流管理系统的大致框架

  • 框架主要分为3层
    • 图数据流的基本数据层
      • 该层负责管理图数据流的最基本的边序列的存储、增删和基本的访问。其中访问操作包括图数据的一些基本操作，如访问节点度数、节点的邻居等。
    • 算法和索引的逻辑层(包含核心算法和相应的索引数据的逻辑层)
      • 其包含的索引数据能够根据数据层的增删而进行更新，从而保持与数据层的逻辑一致性。
      • 而核心算法则涉及图相关的基本算法，包括路径、子图等的经典计算以及图数据流下边的行为分析等。同时，还需要提供图数据流一般性的聚集查询与相关数据统计等逻辑接口。
    • 向上支撑的各种应用的应用层
      • 逻辑层之上则是需要支撑的应用层，针对现实应用数据的分析需求，定制更为复杂的计算接口。
      • 例如进行基于子图挖掘的事件侦测、城市交通的智能分析与管理和信息或话题的传播跟踪等。

5.结束语

  • 图数据流是图模型和数据流模型相融合形成的数据模型
    • 一方面具备图模型对复杂数据的强表达能力
    • 另一方面又结合数据流的更新场景来建模复杂数据的高速生成行为
  • 未来针对图数据流的研究工作有3个较为重要的路线：
    • 一是基于已有的大量图算法/算子等，研究图数据流场景下相关计算操作的实现和优化；
    • 二是基于图数据流场景独自的特点和现实应用需求，提出新的图数据流研究问题及其解决方案；
    • 三是针对图数据流模型本身的数据管理系统，研究其存储、索引、数据的增删改查的基本操作、并发管理以及一致性保证等问题，进而设计结合现实需求的图数据流管理系统

  1. BAR-YOSSEFF Z, KUMART R, SIVAKUMAR D. Reductions in streaming algorithms, with an application to counting triangles in graphs[C]//The 13th Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, USA. Philadelphia: Society for Industrial and Applied Mathematics, 2002: 623-632. ↩︎

  2. J O WHARI H, GHODSI M. New streaming algorithms for counting triangles in graphs[C]//The 11th Annual International Conference, August 16-19, 2005, Kunming, China. [S.l.:s.n.], 2005: 710-716. ↩︎

  3. BURIOL L S, FRAHLING G, LEONARDI S, et al. Counting triangles in data streams[C]//The 25th ACM SIGMODSIGACT-SIGART Symposium on Principles of Database Systems, June 26-28, 2006, Chicago, USA. New York: ACM Press, 2006: 253-262 ↩︎

  4. UNEL G, FISCHER F, BISHOP B. Answering reachability queries on streaming graphs[C]//The 1st International Workshop Stream Reasoning, May 31, 2009, Heraklion, Greece. [S.l.:s.n.], 2009. ↩︎

  5. DEMETRESCU C, FINOCCHI I, RIBICHINI A. Trading off space for passes in graph streaming problems[J]. ACM Transactions on Algorithms, 2006, 6(1): 1-17. ↩︎

  6. MCGREGOR A. Graph stream algorithms: a survey[J]. ACM SIGMOD Record, 2014, 43(1): 9-20. ↩︎

  7. SONG C Y, GE T, CHEN C, et al. Event pattern matching over graph streams[J]. Proceedings of the VLDB Endowment, 2014, 8(4): 413-424. ↩︎ ↩︎

  8. ANGELA, KOUDAS N, SARKAS N, et al . Dense subgraph maintenance under streaming edge weight updates for realtime story identification[J]. VLDB Journal, 2014, 23(2): 175-199. ↩︎

  9. FAN W F, WANG X, WU Y, et al. Incremental graph pattern matching[J]. ACM Transactions on Database Systems, 2013, 38(3): 925-936. ↩︎

  10. CHOUDHURY S, HOLDER L, CHIN G, et al. A selectivity based approach to continuous pattern detection in streaming graphs[J]. Computer Science, 2015, 93(8): 939-945. ↩︎

  11. AGGARWAL C C, LI Y, YU P S, et al. On dense pattern mining in graph streams[J]. Proceedings of the VLDB Endowment, 2010, 3(1-2): 975-984. ↩︎

  12. VALARI E, KONTAKI M, PAPADOPOULOS A N. Discovery of top-k dense subgraphs in dynamic graph collections[C]//The 24th International Conference on Scientific and Statistical Database Management, June 25-27, 2012, Chania, Greece. Heidelberg: Springer, 2012: 213-230. ↩︎

  13. CHI Y, WANG H, YU P S, et al. Moment: Maintaining closed frequent itemsets over a stream sliding window[C]//The 4th IEEE International Conference on Data Mining, November 1-4, 2004, Brighton, UK. Piscataway: IEEE Press, 2004: 59-66. ↩︎

  14. SOLOMON M M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations Research, 1987, 35(2): 254-265. ↩︎

  15. SCHANK T, WAGNER D. Finding, counting and listing all triangles in large graphs, an experimental study[C]// The 36th Annual ACM Symposium on Theory of Computing, June 13-16, 2004, Chicago, USA. Heidelberg: Springer, 2005: 606-609. ↩︎

  16. KOLOUNTZAKIS M N, MILLER G L, PENG R, et al. Efficient triangle counting in large graphs via degree-based vertex partitioning[J]. Internet Mathematics, 2012, 8(1-2): 161-185. ↩︎

  17. ZILIASKOPOULOS A K, MAHMASSANI H S. Time dependent, shortest-path algorithm for real-time intelligent vehicle highway system applications[J]. Transportation Research Record, 1993(1408): 94-100. ↩︎

  18. CLIMACO J C N, MARTINS E Q V. A bicriterion shortest path algorithm[J]. European Journal of Operational Research, 1982, 11(4): 399-404. ↩︎

  19. YUAN Y, WANG G, WANG H, et al. Efficient subgraph search over large uncertain graphs[J]. Proceedings of the VLDB Endowment, 2011, 4(11): 876-886. ↩︎

  20. YAN X, HAN J. gSpan: graph-based substructure pattern mining[C]//The 2002 IEEE International Conference on Data Mining, December 9-12, 2002, Maebashi City, Japan. Piscataway: IEEE Press, 2002: 721-724. ↩︎

  21. KASHIMA H, INOKUCHI A. Kernels for graph classification[C]// The 2002 IEEE International Conference on Data Mining, December 9-12, 2002, Maebashi City, Japan. Piscataway: IEEE Press, 2002. ↩︎

  22. SCHAEFFER S E. Graph clustering[J]. Computer Science Review, 2007, 1(1): 27-64. ↩︎