目錄

庫中的圖形分析算法

獲取Katana圖形庫

使用Katana圖形庫

鄰接矩陣的輸入

來自邊緣列表的輸入

來自Pandas DataFrame的輸入

來自GraphML的輸入

執(zhí)行圖分析算法

Metagraph支持

Katana圖形庫有多快？

我在哪里可以了解更多信息？

參考

---

根據(jù)?Gartner, Inc.的數(shù)據(jù)，圖形處理是2021年十大數(shù)據(jù)分析趨勢之一。它是一個(gè)新興的應(yīng)用領(lǐng)域，也是數(shù)據(jù)科學(xué)家處理關(guān)聯(lián)數(shù)據(jù)集（例如社交、電信和金融）的必要工具網(wǎng)絡(luò)；網(wǎng)絡(luò)流量；和生化途徑）。實(shí)際應(yīng)用中的圖往往很大，而且越來越大。例如，當(dāng)今的社交網(wǎng)絡(luò)可以擁有數(shù)十億個(gè)節(jié)點(diǎn)和邊緣，因此高性能并行計(jì)算至關(guān)重要。

為此，Katana Graph與英特爾合作，設(shè)計(jì)了一個(gè)高性能、易于使用的圖形分析Python庫，具有(a)高度優(yōu)化的重要圖形分析算法的并行實(shí)現(xiàn)；(b)一個(gè)高級Python接口，用于在底層C++圖形引擎之上編寫自定義并行算法；(c)與pandas、scikit-learn和Apache Arrow以及?英特爾AI?軟件堆棧中的工具和庫的互操作性；(d)全面支持各種格式的提取、轉(zhuǎn)換和加載(ETL)；(e)?Metagraph?插件。

本文將介紹庫中的內(nèi)容、如何訪問庫、使用示例和基準(zhǔn)數(shù)據(jù)以突出性能。

庫中的圖形分析算法

圖形處理管道中常用的關(guān)鍵算法預(yù)先打包在Katana庫中。目前可用的算法如下：

• 廣度優(yōu)先搜索：?返回從源節(jié)點(diǎn)開始的廣度優(yōu)先搜索構(gòu)造的定向樹
• 單源最短路徑：?計(jì)算從源節(jié)點(diǎn)開始到所有節(jié)點(diǎn)的最短路徑
• 連接的組件：?查找圖的內(nèi)部連接但未連接到其他組件的組件（即節(jié)點(diǎn)組）
• 網(wǎng)頁級別：?根據(jù)傳入鏈接的結(jié)構(gòu)計(jì)算圖中節(jié)點(diǎn)的排名
• 中介中心性：?根據(jù)通過每個(gè)節(jié)點(diǎn)的最短路徑數(shù)計(jì)算圖中節(jié)點(diǎn)的中心性
• 三角形計(jì)數(shù)：?計(jì)算圖形中三角形的數(shù)量
• 魯汶社區(qū)檢測：?使用魯汶啟發(fā)式計(jì)算最大化模塊化的圖社區(qū)
• 子圖提取：?提取圖的誘導(dǎo)子圖
• Jaccard相似度：?計(jì)算給定節(jié)點(diǎn)與圖中每個(gè)其他節(jié)點(diǎn)的Jaccard系數(shù)
• 使用標(biāo)簽傳播的社區(qū)檢測：?使用標(biāo)簽傳播算法計(jì)算圖中的社區(qū)
• 局部聚類系數(shù)函數(shù)：?衡量圖中節(jié)點(diǎn)傾向于聚集在一起的程度
• K-Truss：?找到包含至少三個(gè)頂點(diǎn)的圖的最大誘導(dǎo)子圖，其中每條邊都與至少K-2個(gè)三角形相關(guān)
• K-Core：?查找包含度數(shù)為K或以上的節(jié)點(diǎn)的最大子圖

更多算法被添加到庫中，用戶可以輕松添加自己的算法，我們將在下面演示。

獲取Katana圖形庫

Katana Graph的分析庫是開源的，在?3-Clause BSD許可下免費(fèi)提供。它可以在?GitHub?上找到，也可以從Anaconda.org輕松安裝：

$ conda install -c katanagraph/label/dev -c conda-forge katana-python

使用Katana圖形庫

Katana的Python庫支持各種格式的ETL，例如鄰接矩陣、pandas DataFrames、NumPy數(shù)組、邊列表、GraphML、NetworkX等。下面顯示了幾個(gè)示例：

import numpy as np import pandas from katana.local import Graph from katana.local.import_data import (from_adjacency_matrix,from_edge_list_arrays,from_edge_list_dataframe,from_edge_list_matrix,from_graphml)

鄰接矩陣的輸入

katana_graph = from_adjacency_matrix(np.array([[0, 1, 0], [0, 0, 2], [3, 0, 0]]))

來自邊緣列表的輸入

katana_graph = from_edge_list_arrays(np.array([0, 1, 10]), np.array([1, 2, 0]),prop = np.array([1, 2, 3]))

來自Pandas DataFrame的輸入

katana_graph = from_edge_list_dataframe(pandas.DataFrame(dict(source=[0, 1, 10],destination=[1, 2, 0],prop = [1, 2, 3])))

來自GraphML的輸入

katana_graph = from_graphml(input_file)

執(zhí)行圖分析算法

以下示例計(jì)算輸入圖的介數(shù)中心性：

import katana.local from katana.example_utils import get_input from katana.property_graph import PropertyGraph from katana.analytics import betweenness_centrality,BetweennessCentralityPlan,BetweennessCentralityStatistics katana.local.initialize()property_name = "betweenness_centrality" betweenness_centrality(katana_graph, property_name, 16,BetweennessCentralityPlan.outer()) stats = BetweennessCentralityStatistics(g, property_name)print("Min Centrality:", stats.min_centrality) print("Max Centrality:", stats.max_centrality) print("Average Centrality:", stats.average_centrality)

Katana的Python庫可與pandas、scikit-learn和Apache Arrow互操作。

除了前面列出的預(yù)打包例程外，數(shù)據(jù)科學(xué)家還可以使用簡單的Python接口編寫自己的圖形算法，該接口公開了Katana Graph的優(yōu)化C++引擎及其并發(fā)數(shù)據(jù)結(jié)構(gòu)和并行循環(huán)結(jié)構(gòu)。Katana Graph庫已經(jīng)包含廣度優(yōu)先搜索實(shí)現(xiàn)，但以下示例說明了使用API實(shí)現(xiàn)此類算法是多么容易：

def bfs(graph: Graph, source):"""Compute the BFS distance to all nodes from source.The algorithm in bulk-synchronous level by level.:param graph: The input graph.:param source: The source node for the traversal.:return: An array of distances, indexed by node ID."""next_level_number = 0# The work lists for the current and next levels using a # Katana concurrent data structure.curr_level_worklist = InsertBag[np.uint32]()next_level_worklist = InsertBag[np.uint32]()# Create and initialize the distance array.# source is 0, everywhere else is INFINITYdistance = np.empty((len(graph),), dtype=np.uint32)distance[:] = INFINITYdistance[source] = 0# Start processing with just the source node.next_level_worklist.push(source)# Execute until the worklist is empty.while not next_level_worklist.empty():# Swap the current and next work listscurr_level_worklist, next_level_worklist = next_level_worklist,curr_level_worklist# Clear the worklist for the next level.next_level_worklist.clear()next_level_number += 1# Process the current worklist in parallel by applying# bfs_operator for each element of the worklist.do_all(curr_level_worklist,# The call here binds the initial arguments of bfs_operator.bfs_operator(graph, next_level_worklist,next_level_number, distance))return distance# This function is marked as a Katana operator, meaning that it will # be compiled to native code and prepared for use with Katana do_all. @do_all_operator() def bfs_operator(graph: Graph, next_level_worklist,next_level_number, distance, node_id):"""The operator called for each node in the work list.The initial four arguments are provided by bfs above.node_id is taken from the worklist and passed to thisfunction by do_all.:param next_level_worklist: The work list to add next nodes to.:param next_level_number: The level to assign to nodes we find.:param distance: The distance array to fill with data.:param node_id: The node we are processing.:return:"""# Iterate over the out edges of our nodefor edge_id in graph.edges(node_id):# Get the destination of the edgedst = graph.get_edge_dest(edge_id)# If the destination has not yet been reached, set its level# and add it to the work list so its out edges can be processed# in the next level.if distance[dst] == INFINITY:distance[dst] = next_level_numbernext_level_worklist.push(dst)# There is a race here, but it's safe. If multiple calls to# operator add the same destination, they will all set the# same level. It will create more work because the node will# be processed more than once in the next level, but it avoids# atomic operations so it can still be a win in low-degree graphs.

Metagraph支持

Katana Graph的Python分析庫將通過?Metagraph?插件提供。Metagraph為圖形分析提供了一致的Python入口點(diǎn)。可以使用標(biāo)準(zhǔn)API編寫圖形工作流，然后將其分發(fā)到可插入Metagraph的兼容圖形庫。現(xiàn)在，開源圖形社區(qū)將能夠直接使用Katana Graph的高性能應(yīng)用程序。Metagraph插件包含在Anaconda包中，可以按如下方式安裝和調(diào)用：

$ conda create -n metagraph-test -c conda-forge \-c katanagraph/label/dev \-c metagraph metagraph-katanaimport metagraph as mg bfs = mg.algos.traversal.bfs_iter(katana_graph, <start node>)

Katana圖形庫有多快？

Katana庫已針對其他圖形分析框架進(jìn)行了廣泛的基準(zhǔn)測試，并且始終顯示出與?GAP Benchmark Suite?相當(dāng)或更好的性能。?表1?顯示了Katana Graph相對于來自不同領(lǐng)域的各種圖的GAP參考實(shí)現(xiàn)的性能。

表 1. 使用GAP Benchmark Suite測量Katana Graph性能。該數(shù)據(jù)取自Azad等人。(2020)2。系統(tǒng)：雙路 2.0 GHz Intel? Xeon? Platinum 8153 處理器（64個(gè)邏輯內(nèi)核）和 384 GB DDR4 內(nèi)存。有關(guān)性能和基準(zhǔn)測試結(jié)果的更完整信息，請?jiān)L問?www.intel.com/benchmarks。

Katana Graph庫在最近的字節(jié)可尋址內(nèi)存技術(shù)上也被證明在超大圖上表現(xiàn)良好，例如Clueweb12和WDC12（分別有42和1280億條邊，這些是一些最大的公開可用圖）例如英特爾? 傲騰? DC持久內(nèi)存（圖 1）。

圖 1. Katana Graph BFS在超大圖上的性能。它將單個(gè)基于英特爾傲騰內(nèi)存的節(jié)點(diǎn)的性能與具有多個(gè)節(jié)點(diǎn)的集群進(jìn)行了比較。每個(gè)TACC Stampede Skylake集群節(jié)點(diǎn)都有兩個(gè)2.1 GHz Intel Xeon Platinum 8160處理器和192 GB DDR4內(nèi)存。Cascade Lake服務(wù)器具有兩個(gè)2.2 GHz第二代Intel Xeon可擴(kuò)展處理器，配備6 TB Intel Optane PMM和384 GB DDR4 DRAM。Ice Lake服務(wù)器有兩個(gè)2.2 GHz Intel Xeon Platinum 8352Y處理器，8 TB Intel Optane PMM和1 TB DDR4 DRAM。有關(guān)性能和基準(zhǔn)測試結(jié)果的更完整信息，請?jiān)L問?www.intel.com/benchmarks。

我在哪里可以了解更多信息？

我希望您確信Katana Graph庫是用于圖形分析的多功能、高性能選項(xiàng)。您可以在GitHub 站點(diǎn)上了解有關(guān)該庫的更多信息、提出問題、發(fā)布功能請求等?。

參考

Nguyen, D.、Lenharth, A.和Pingali, K. (2013)。?用于圖形分析的輕量級基礎(chǔ)架構(gòu)。第24屆ACM操作系統(tǒng)原理研討會(huì)論文集 (SOSP '13)。

阿扎德，A. 等人。（2020年）。?使用GAP基準(zhǔn)套件、IEEE工作負(fù)載表征國際研討會(huì)(IISWC)評估圖形分析框架。

ClueWeb12數(shù)據(jù)集

Web Data Commons – 超鏈接圖

Gill, G.、Dathathri, R.、Hoang, L.、Peri, R.和Pingali, K. (2020)?使用英特爾傲騰DC持久內(nèi)存對海量數(shù)據(jù)集進(jìn)行單機(jī)圖分析?。VLDB捐贈(zèng)基金會(huì)議記錄，13(8), 1304–1318。

Dathathri, R. 等人。（2019）。?Gluon-Async：用于分布式和?異構(gòu)圖形分析的批量異步系統(tǒng)。第28屆并行架構(gòu)和編譯技術(shù)國際會(huì)議論文集(PACT)。

https://www.codeproject.com/Articles/5317383/Katana-s-High-Performance-Graph-Analytics-Library

總結(jié)

以上是生活随笔為你收集整理的Katana的高性能图形分析库的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。