In this work, we present a novel approach to the streaming graph partitioning problem which handles unbounded streams.Graph partitioning is a process of dividing a graph into groups of nodes or edges. Traditional, offline partitioning methods require a priori access to the entire graph and make multiple passes over the data in order to compute partitions. However, recently the demand for real-time analysis of graph data sparked the prospect of online partitioning. In such an approach, the graph arrives as a stream of nodes or edges which are assigned to partitions as they come and are never reassigned again. Additionally, in the case of modern systems, where graphs constantly grow, the streams are unbounded. The main goals of graph partitioning are preserving data locality, so related items belong to the same partitions, and load balance, so partitions have similar sizes.State-of-the-art streaming graph partitioning algorithms fulfil the two latter requirements. However, they make their partitioning decisions based on internal state, which grows as new items arrive. Thus, they are not capable of processing unbounded streams. At some point, the state will exceed the memory capacity of the machine the algorithm is running on. Moreover, modern stream data processors run in a distributed environment. In such a setting synchronisation of a shared state is an expensive operation.In the proposed approach, in addition to structural information about the graph, we utilise attributes associated with vertices such as user’s location, age, or previous actions. In order to do that, we employ a graph convolutional network (GCN), which is a novel method of graph representation learning. A GCN can embed both structural and feature-based characteristics of each vertex into a low-dimensional space. Secondly, we feed these representations into a neural network, which assigns incoming items to partitions. Such a method requires only the networks’ parameters’ values in order to make a partitioning decision. Thus, the size of the state remains constant regardless of the length of the stream.We present both unsupervised and supervised approaches to train the proposed framework. Moreover, we describe a method to apply the models to partition the streaming graph. We evaluate the performance of our novel method on three real-world graph datasets and compare it with the state-of-the-art HDRF algorithm as well as a simple, stateless hash-based approach. The experimental results show the generalisation capabilities of our models. Moreover, our methods can yield up to 16% lower replication factor than hash partitioning which corresponds to only 1% increase compared to HDRF. At thesame time, we reduce state requirements from linear to constant, which for the graph with 230k vertices and 5.7M edges translates to 125 times smaller size of the state and allows for processing unbounded streams. Nevertheless, the latency of our methods is about 20 times higher than HDRF. / I det här arbetet presenterar vi en ny metod för grafpartitionering av obundna strömmar.Grafpartitionering är en process att dela upp en graf i grupper av noder eller kanter. Traditionella, offline-partitioneringsmetoder kräver en priori åtkomst till hela grafen och gör flera passeringar över datan för att beräkna partitioner. Nyligen gjorde dock efterfrågan på realtidsanalys av grafdata möjligheterna att partitionera online. I ett sådant tillvägagångssätt ankommer grafen som en ström av noder eller kanter som tilldelas partitioner när de kommer och aldrig tilldelas igen. Dessutom, för moderna system, där grafer ständigt växer, är strömmarna obegränsade. Huvudmålen för grafpartitionering är att bevara datalokalitet, så relaterade objekt tillhör samma partitioner och lastbalans, så partitioner har liknande storlekar.Avancerade algoritmer för strömmande grafpartitionering uppfyller de två senare kraven. De fattar emellertid sina partitionsbeslut baserade på internt tillstånd, som växer när nya artiklar kommer. Således kan de inte bearbeta obundna strömmar. Vid någon tidpunkt kommer tillståndet att överskrida minneskapaciteten för maskinen som algoritmen kör på. Dessutom körs moderna databehandlare i en distribuerad miljö. I en sådan inställning är synkronisering av ett delat tillstånd en dyr operation.I det föreslagna tillvägagångssättet använder vi, utöver strukturell information om grafen, attribut som är förknippade med hörn som användarens plats, ålder eller tidigare åtgärder. För att göra det använder vi ett grafkonvolutional nätverk (GCN), som är en ny metod för grafrepresentation. En GCN kan bädda in både strukturella och funktionsbaserade egenskaper hos varje toppunkt i ett lågdimensionellt utrymme. För det andra matar vi dessa representationer i ett neuralt nätverk, som tilldelar inkommande objekt till partitioner. En sådan metod kräver bara nätverksparametrarnas värden för att fatta ett partitionsbeslut. Således förblir tillståndets storlek konstant oavsett strömmens längd.Vi presenterar både obevakade och övervakade tillvägagångssätt för att utbilda det föreslagna ramverket. Dessutom beskriver vi en metod för att tillämpa modellerna för att partitionera strömningsgrafen. Vi utvärderar prestandan för vår nya metod på tre grafiska datauppsättningar i verkligheten och jämför den med den senaste HDRF-algoritmen samt en enkel, statslös hashbaserad strategi. De experimentella resultaten visar generaliseringsförmågan hos våra modeller. Dessutom kan våra metoder ge upp till 16% lägre replikationsfaktor än hashpartitionering, vilket motsvarar endast 1% ökning jämfört med HDRF. Samtidigt minskar vi tillståndskraven från linjär till konstant,vilket för diagrammet med 230k vertikaler och 5,7M kanter motsvarar 125 gånger mindre storlek på tillståndet. Trots det är latens för våra metoder ungefär 20 gånger högre än HDRF.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-280320 |
| Date | January 2020 |
| Creators | Zwolak, Michal |
| Publisher | KTH, Skolan för elektroteknik och datavetenskap (EECS) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-EECS-EX ; 2020:539 |
Page generated in 0.0032 seconds