1 of 26

Temporal graph motifs and how to find them

or how I inadvertently got into big data engineering 😳

Naomi Arnold

NetPLACE

1

Wednesday, 12 April 2023

2 of 26

A temporal network

NetPLACE

2

Wednesday, 12 April 2023

id:NaomiArnold

Postdoc

t2021-t2023

id:ATI

Postdoc

t2021-t2023

id:Raphtory

Developer

t2020-

PhD CS

t2017-t2021

id:QMUL

id:FETA

Lead developer

t2017-

id:Pometry

Enterprise spinout

T2021-

Adviser

t2021-

BA Maths

t2014-t2017

Postdoc

T2023+

id:NULondon

3 of 26

Introducing Raphtory

4 of 26

Raphtory overview�The first platform built especially for large temporal networks

 

 

 

 

 

 

 

Distributed graph with full history stored

User endpoint for querying the graph

Attach data from anywhere

Converted to

updates

5 of 26

Shortest Path

PageRank

Cycle Detection

Cascade Spreading

Similarity

Degree Centrality

Triadic Motifs

Temporal LPA

30+ algorithms out of the box

With ability to extend or write your own in minutes

6 of 26

Raphtory x Temporal Motif analysis in Crypto

7 of 26

Temporal Motifs in dark market trades�The case of the Alphabay market

NetPLACE

7

Wednesday, 12 April 2023

Wallet

Wallet

Sends money to

  • Users make purchases from Alphabay or peer-to-peer transactions using Bitcoin
  • Dataset includes all entities who interacted with the Alphabay market and their transactions

8 of 26

What do we mean by temporal motif?

NetPLACE

8

Wednesday, 12 April 2023

Introducing a δ-temporal motif

7

13

9

12

5

21

9

7

13

l

9 of 26

NetPLACE

9

Wednesday, 12 April 2023

  • Motifs on three edges and up to three nodes
  • Limit to those which complete within 1 hour

Pairwise trading between users.

Fanning out of money. User making batch purchases? Mixer splitting a transaction?

Funnelling of money. Vendor receiving purchase orders? Recipient of a split transaction?

What motifs are we looking for?

And what might they tell us ?

10 of 26

NetPLACE

10

Wednesday, 12 April 2023

Dataset and Experiment

~ 11 million nodes (users)

~ 33.6 million transactions

Dataset of all users who have transacted with Alphabay and their transactions

Local motif counting algorithm implemented in Raphtory, took 2hrs in total to build the graph and run the algorithm

11 of 26

Motifs in Alphabay

NetPLACE

11

Wednesday, 12 April 2023

Fanout motif (all outgoing) the most prevalent by orders of magnitude

Followed by single-direction pairwise motif

Followed largely by funneling (all incoming) motifs

12 of 26

Motifs local to the node

NetPLACE

12

Wednesday, 12 April 2023

What is the spread of motifs that nodes participate in?

13 of 26

Motifs of heavy hitting nodes

NetPLACE

13

Wednesday, 12 April 2023

Top two nodes with the highest number of motifs

Alphabay market node (not even in the top 10!!!)

All outgoing. Mixer service? Crypto on-ramp?

All incoming. Crypto exchange? Big seller?

Conveyance-style motif. Consistent with being an escrow service

14 of 26

NetPLACE

14

Wednesday, 12 April 2023

Total motif counts of different types

Composition of different motifs

The sharp downturn in motifs is long before Alphabay is shut down

Change from peer-to-peer motifs to star motifs which doesn’t return after Alphabay shut down

Motifs in Alphabay over time

15 of 26

Future directions�Motif-based clustering of wallets

Turns out nodes can be clustered very well based on their motif participation!

Are there salient groups of nodes which have similar types of motifs (possibly playing a similar role in the system)

16 of 26

Why can working with large networks be so damn difficult?

17 of 26

Power laws everywhere

NetPLACE

17

Wednesday, 12 April 2023

The power laws/heavy tails of complex systems that make them so fascinating can take many algorithms into a worst case scenario and makes problems hard to distribute

18 of 26

Memory constraints and long runtimes

NetPLACE

18

Wednesday, 12 April 2023

Large networks are a challenge to represent in-memory especially when they are temporal. End up spending £££ on big AWS/Azure boxes

YAY! It took 24 hours but I finally got my results out

That’s brilliant news! What does it look like with delta = 1 day instead of 1 hour? What about if you remove the top 10 nodes? I’m really curious to see about…

Code that takes a long time to run inhibits your enthusiasm for experimentation with different parameters/setups

19 of 26

What did I learn from the process to pass on?

20 of 26

Get a crash course on data structures�Example: Arrays vs Lists

NetPLACE

20

Wednesday, 12 April 2023

Source: https://www.bigocheatsheet.com/

 

What data structure out of lists, sets, arrays, vectors makes sense?

​

  • Do I know its size beforehand? Do I need to add or remove things from it?
  • Do I care about the order or multiplicity of the items? Do I need to check if items are in there?
  • Will I be accessing specific items or things from the start or end?

21 of 26

Learn how to use and interpret a code profiler

Memory profiler – monitors the objects being held in-memory and their sizes. Can be useful for spotting memory leaks (variables not being cleared up when they are done with) or heavy objects.

CPU profiler – shows how long (in a sense) the program is spending in different routines. If the program is spending > 80% of time in one routine, it’s almost certainly something you can optimize.

NetPLACE

21

Wednesday, 12 April 2023

22 of 26

Find a programming buddy who can help you

NetPLACE

22

Wednesday, 12 April 2023

“Rubber ducking” process – even the act of explaining how your procedure works might help you realise why it’s slow or not scaling well

End up with bonus hacky skills that you wouldn’t have even thought to look for

The longer you have programmed for, the more eagle-eyed you become for spotting potentially inefficient routines or data structures

23 of 26

What it feels like pair programming with someone more experienced than you

NetPLACE

23

Wednesday, 12 April 2023

24 of 26

Bigger picture outcomes for Raphtory

25 of 26

Raphtory improvements as a result

  • Motifs algorithm went from taking 24hrs -> 12hrs -> 8hrs -> 2hrs on the largest dataset by finding optimisations for it.

​

  • Optimised some crucial low-level functions and storage of Raphtory e.g. building views of a graph through time

​

  • New rewrite in Rust for achieving the best possible storage capabilities and better Python integration

​

  • Alphabay dataset: 200GB -> 4GB. No longer a need for pricey cloud credits!!

NetPLACE

25

Wednesday, 12 April 2023

26 of 26

Thank you for listening!

Questions/thoughts?

narnolddd

narnolddd

naomi.arnold@nulondon.ac.uk

Thanks to Richard Clegg, Peijie Zhong, Raul Mondragon (QMUL), Felix Cuadrado (UPM), Ben Steer and Fabian Murariu (Pometry)

Github.com/Raphtory

pip install raphtory