Mayfly: a Neural Data Structure for Graph Stream Summarization
Authors: Yuan Feng
Yukun Cao
Wang Hairu
Xike Xie
S Kevin Zhou
Venue: ICLR 2024 spotlight (2024)
Keywords: Meta-Learning;Memory Augmented Neural Network; Deep Neural Network Application;Graph Summarization
Primary area: transfer learning, meta learning, and lifelong learning
TL;DR: a Neural Data Structure for Graph Stream Summarization

Abstract: A graph is a structure made up of vertices and edges used to represent complex relationships between entities, while a graph stream is a continuous flow of graph updates that convey evolving relationships between entities. The massive volume and high dynamism of graph streams promote research on data structures of graph summarization, which provides a concise and approximate view of graph streams with sub-linear space and linear construction time, enabling real-time graph analytics in various domains, such as social networking, financing, and cybersecurity.
In this work, we propose the Mayfly, the first neural data structure for summarizing graph streams. The Mayfly replaces handcrafted data structures with better accuracy and adaptivity.
To cater to practical applications, Mayfly incorporates two offline training phases.
During the larval phase, the Mayfly learns basic summarization abilities from automatically and synthetically constituted meta-tasks, and in the metamorphosis phase, it rapidly adapts to real graph streams via meta-tasks.
With specific configurations of information pathways, the Mayfly enables flexible support for miscellaneous graph queries, including edge, node, and connectivity queries.
Extensive empirical studies show that the Mayfly significantly outperforms its handcrafted competitors.

Published as a conference paper at ICLR 2024
MAYFLY: A NEURAL DATA STRUCTURE FOR GRAPH STREAM SUMMARIZATION
Yuan Fengl.3; Yukun Cao Hairu Wang 13 ,3, Xike Xie and S. Kevin Zhou 2.3
1 School of Computer Science, University of Science and Technology of China (USTC), China School of Biomedical Engineering, USTC, China
Data Darkness Lab, MIRACLE Center, Suzhou Institute for Advanced Research, USTC, China (yfung, ykcho, wanghairs ru) @mail. uste. edu. cn, xkxie@ustc edu. kevin. zhouê gma i 1 com
ABSTRACT
A graph is structure made up of vertices and edges used to represent complex relationships between entities, while graph stream is a continuous flow of graph updates that convey evolving relationships between entities. The massive volume and high dynamism of graph streams promote research data structures of graph summarization, which provides a concise and approximate view of graph streams with sub- sub-linear space and lincar construction time, enabling real-time graph analytics in various domains, such as social networking, financing, and cybersecurity. In this work, propose the Mayfly, the first neural data structure for summarizing graph streams. The Mayfly replaces handcrafted data structures with better accuracy and adaptivity. To cater to practical applications, Mayfly incorporates two offline training phases, namely larval and metamorphosis phases. During the larval phase, the Mayfly learns basic summarization abilities from automatically and synthetically constituted meta-tasks. In the metamorphosis phase, it rapidly adapts to real graph streams via meta-tasks. With specific configurations of information pathways, the Mayfly enables flexible support for miscellaneous graph queries, including edge, node, and connectivity queries. Extensive empirical studies show that the Maytly significantly outperforms its handcrafted competitors.
INTRODUCTION
Recently, it shows prominence in using neural networks as alternatives for handcrafted data structures
(Cao et al., 2023) et al. 2023: Bertsimas & Digalakis 2021 Rae et al. 2019) Hsu et al.) 2019 Kraska al. 2018), especially in data stream applications, where neural data structures designed by harnessing the abilities of neural networks, providing two key benefits. First, they exploit deep- level implicit information (e.g., dense vectors), enabling superior summarization capabilities to handcrafted data structures which maintain explicit counts. Second, they facilitate diversified query evaluation over data summarization via data streaming patterns captured in deep networks.
One important but under-explored data stream application for neural data structures is graph streams. graph stream refers to the continuous sequence of streaming edges, each of which is associated with two incident nodes and an edge weight. Graph streams represent the evolutionary process of a dynamic graph and play vital role online graphical analytics (McGregor) 2014a| Stanton Kliot et al., 2010 7ou et al. 2022 Kong et al. 2022). For example, in a social network (Mislove et al. 2007] Zhao et al.) 2016), graph streams capture the evolving relation between entities,
where the edge weight is indicative of the strength of social connections. In network traffic analysis
(Guha & McGregor 2012; D' D'Alooozo et al. 2019), graph streams highlight the communication between networking devices aiding in monitoring tasks, such as locating security threats (Hong et al.)
2017 Gou et al.) 2022) or identifying network structures (Ahn et al. 2012 Gou et al.) 2022).
Ordinary data streams are with two prominent characteristics, massive volume and high dynamism, so that challenges arise in meeting the space and time constraints on the stream processing. In particular,
Equal Contribution
*Corresponding Author

---

Published as a conference paper at ICLR 2024
it requires data streams to be processed in one-pass fashion with limited space budgets (Charikar
et al.
2002 Cormode & Muthukrishnan, 20055 Babcock et al.) 2002; Broder & Mitzenmacherr
2004 Graph streams post the additional variety challenge in sustaining the representation of
complex relationships in-between graph entities, putting heavier burdens on contending with the space and time challenges. Existing handcrafted solutions (Cormode & Muthukrishnan) 2005 (Zhao ct al. 2011 Tang et al., 2016; Gou ct al.] (022)) summarize graph streams by small (sub-linear summarization structure within linear construction time and allow for the evaluation of graph queries. Early methods, such as CM-Sketch (Cormode & Muthukrishnan 2005) and gSketch (Zhao et al. 2011). hash streaming edges to counters of 2D storage array. However, they overlook the importance of graph connectivity which is essential in addressing advanced graph queries. Afterwards, the TCM (Tang et al., 2016), independently hashes streaming nodes and edges, while preserving the graph connectivity to support diverse graph queries. GSS (Gou et al., 2022) extends the underlying structure of TCM with auxiliary storage to improve the query accuracy. Auxo (Jiang et al. 2023) builds upon GSS and incorporates a prefix embedded tree, to accelerate the process of GSS buffer expansion, particularly in high-budget scenarios. However, the optimization comes at a cost of increased time complexity and its linear memory expansion does not meet the low-budget constraints commonly associated with the majority of existing sketches. In our paper, we emphasize smaller memory budgets (e.g.. below 100KB) (Liu & Xie 2 2023). With such budget constraints, existing structures falter. TCM, if constrained by budgets, faces severe hash collisions, causing excessive query errors. Similarly, GSS (Auxo) cannot fetch external storage that exceeds the budgets, thereby resulting in unacceptable query hit rates.
In this paper, we propose the first neural data structure, called the Mayfly, for graph stream sum- marization, going beyond state-of-the tht-he-rrtt art handcrafted solutions, such as TCM and GSS. However, challenges arise in determining the appropriate design of network structures and training methods, specifically in meeting the stringent requirements of graph summarization in terms of space and time efficiency, while supporting diverse graph queries, including edge queries, node queries, connectivity queries, path queries, and subgraph queries.
Starting from the premises, the Mayfly based on memory-auggeente network (Graves et al. 2014 2016), is trained by one-shot meta-learning (Vinyals et al.) 2016) Santoro et al. 2016) based on two types of auto-generated meta-tasks, larval tasks and metamorphosis tasks, leading to two corresponding training phases, larval and metamorphosis phases. In the larval phase, the Mayfly learns the fundamental ability to summarize graph streams based on larval tasks generated from synthetic data, focusing on the generalization ability. In the metamorphosis phase, the Mayfly equipped with basic abilities is swiftly adapted to metamorphosis tasks, which are sampled from real graph streams to enhance the specialization ability. The Mayfly adopts a novel method of jointly storing edges/nodes information aligning with the workflow of conventional structures of graph summarization and guaranteeing space efficiency. Moreover, we introduce information pathways coupled with meta-learning guiding offering full coverage of diverse graph query types, liberating the model from full retraining for each type. It simultaneously meets the ubiquitous need to execute multiple query types following one-pass storing in graph streaming scenarios.
Our contributions include: structure based on memory-augmented networks with novel storage paradigm and training strategies tailored for graph stream scenarios. Mayfly takes the graph structure into account and can be rapidly adapted to real graph stream distributions. It introduces a novel concept of altering information pathways in memory networks to facilitate the expansion of multiple graph query types, which hold the potential to facilitate research in other scenarios with diverse query types. Extensive empirical studies show that our proposal significantly outperforms state-of-the-art methods.
We propose the Mayfly, the first neural graph stream summarization
2 RELATED WORKS
2.1 NEURAL DATA STRUCTURE
Mayfly draws inspiration from two recent neural data structures: NBF (Neural Bloom Filter) (Rae et al. 2019) and MS (Meta-Sketchh (Cao et al. 2023). While NBF filters redundant streaming items and MS counts streaming item frequencies, Mayfly introduces significant innovations. Primarily, it is custom-desse destined for graph stream scenarios, emphasizing separate compressed storage for node and edge weights, capture graph structural information. In contrast, NBF and MS do not account for
2

---

Published as a conference paper at ICLR 2024
this structural information, making them less apt for such contexts. Additionally, the Mayfly solves the NBF and MS's dependencies on specific datasets by employing randomized IDs for pre-training. A notable addition from Mayfly in neural data structures is the information pathway. Modifying these pathways in the memory network facilitates the extension of query types in graph stream contexts.
2.2 GRAPH STREAM SUMMARIZATION
As outlined in Section 1, current methods for graph stream summarization primarily hinge on summarization structures. Tracing back, graph stream summarization has evolved from traditional graph summarization, with methods such as Sparsification (Li et al.) 2022), Bit compression (Zhou a.). Tensor factorization (Fernandes et al., 202T). and GNN-based techniques (Shabani al. 2023 having been proposed. But the majority of these methods are designed for static graphs (Liu et al. 2018). If one attempts customize other dynamic graph methods to support graph streams, restricted query capabilities and significantly reduced efficiency can not be avoided. For example, the classic TimeCrunch (Shah et al. 2015) fails to support basic accumulated weight queries in stream contexts, while the advanced Mosso (Ko et al. (020) and its variant (Ma et al. (20TT) suffer from significantly throughput delays in handling stream tasks, performing at a rate approximately 103 times slower than GSS (Gou et al. 2022). In contrast, the Mayfly's 's primary focus lies in improving and ad advancing summarization structures within the context of graph streams.
3 CONCEPTS
We formalize graph streams and define atomic queries supported by graph stream summarization to clarify conceptual barriers. A graph stream So (Definition
[T) is represented by the directed graph G(V, E), where V denotes the node set and E the edge set. Thus, for an arbitrary edge ej E E, there exist one or more streaming edges in Sç with origin node o(e;) and destination node d(e,). so that the weight of e; is equal to the summation of the weights of all corresponding streaming edges.
Definition 1 (Graph Streams (McGregor 2014b Gou et al. 2022 A graph stream Sg {I1, 22......... is a time-evolving sequence, where each item x; represents a streaming edge from origin node o(r;) to destination node d(z,) with incremental weight Aw; at time i.
The technique stack of graph stream summarization builds upon three atomic query types: edge, node, and connectivity queries (Tang et al., 2016; Gou et al. (022). Among these, the edge query, which retrieves the weight of specified edge (Definition 2). is of paramount importance, since it serves as the basis for evaluating other query types. Mayfly is primarily trained on meta-tasks related to edge queries. Once trained, the Mayfly can be swiftly transited to the processing of node queries and connectivity queries (Definition 3 [ndd(4 More complex queries, such as path and subgraph queries, can be disassembled to series of atomic queries. For simplicity, investigate the Mayfly training guided by edge queries in Section 4 and study the extensions to other query types in Section
Definition (Edge Queries). An edge query, denoted as Que(ez), aims to retrieve the cumu- lative weight of given edge 6j on graph G(V, E) rendered by graph stream Sa: Qule,)
E (o(. ((z:)))(((5) Aw;
Definition (Node Queries). Given a node um of graph G(V, E) rendered by graph stream SG, a node query aims to retrieve either the sum of the cumulative weights of U. 's outgoing edges or its incoming edges: Qract (Um) = Exje,es, =m Aw; or Qnan (Um) = , Aws.
Definition& 4 (Connectivity Queries). Given nodes Un and Vas in a graph G(V, E) represented by graph stream Sg, a connectivity query determines if there's 's directed edge ej from node um to node Vnd. Formally, Qe(Umn Um!) True if eg E and False otherwise.
4 METHODOLOGY
4.1 OVERVIEW
Overall, the Mayfly framework utilizes a storage matrix M as the foundation for summarizing graph streams by writing sequentially arriving streaming edges into it in one pass. Built upon the
3

---

Published as a conference paper at ICLR 2024
SG
Store & Query
Shouning
Only Store
4
Metacnorpbose Phase
Only Query
Blxt,
Mitamerphok
Graph at 1-1
F2
fr.
Spanastoc
o(x))
Sublmago
d(x))
Awy
fn
fa
Larval Phane
F++1
MM gestisst
Qu
Extended Queny Typas
Graph G 1+1
WM
Taols
Graph Stream
Mayfly Framework
Mayfly Training
Figure 1: Mayfly Overview
storage matrix, the framework consists of three functional modules, namely Representution (R), Addressing (A), and Decoding (D), as shown in Figure [ Similar to traditional summarization structures, we define two types of operations for the Mayfly in association with the three modules, which are a unified Store operation and a customizable Query operation. Specifically, the Store operation first inputs each incoming streaming edge into R. for representation learning, considering the joint information of the two incident nodes of the incoming edge. Then, based on the address obtained from A, the representation vector and corresponding weights are written into M. The Query operation can be instantiated for different types of graph stream queries via the specific configuration of information pathways. Remarkably, different Query operation instances generally follow a similar process, where they utilize the address from A to read information vectors from M and decode the retrieved information through D to get the query result.
The Mayfly adopts the idea of meta-learning, which involves learning the ability to solve a class of domain tasks from auto- generated meta-tasks, rather than memorizing a specific task. To satisfy the one-pass processing for graph streams, we employ one-shot meta- meta-traing training strategy (Rae et al. 2019)] Vinyals et al. 2016),, which enables efficient meta-optimization within a single base learning episode (Hospedales et al. 2021). Moreover, the Mayfly benefits from the paradigm of "pre-training and fine-tuming" consisting of two training phases, the larval phase and the metanorphosis phase, to gracefully handle the complex real-world graph stream applications. In the larval phase, the Mayfly learns the fundamental techniques of summarizing graph streams by undergoing the training with larval tasks, to reach the subimagio state. In the metamorphosis phase, the subimago form of the Mayfly quickly transforms to the imago state, by rapid adapting to the metamorphosis tasks, to gain the ability on the real graph streams.
4.2 MODULES
Representation (R). The main function of module R is to learn representations for incoming streaming edge H;, while edges are represented in the same way during the Query operation. We use a set of representation vectors for node o(x;)) and d(x;). denoted as {n=(==), nn())) to represent streaming edge z,. The information of a streaming edge is implicitly encoded in these representation vectors (i.e., "representing" function), which also serve as the basis for deriving the certain read/write addresses (i.e., "addressing" function). Specifically, R contains network component, the represen- lation network fn. For streaming edge I4, its out/in nodes o(z;), d(x;)) E V is numerically encoded and then input to fo to get {n)(=,) nd()))) E R The out/in bidirectional representation adequately represents the stacked edges while avoiding confusion in both the outgoing and incoming directions.
R|z.1- - R[Ho((.)) d(x.)H + (ff())())),, fo (d(x.)) + (()))) d(:::))
(1)
We adopt a unified encoding for nodes of a graph stream, where for each node a unique numerical ID (e.g., 1, ....... is assigned and then converted to binary encoding. The unified encoding strategy allows the Mayfly to be independent of node information in graph stream, conducting pre-training independent of real dataset. By establishing the same encoding mapping for various streams, the Mayfly can be trained once and deployed for multiple applications without being retrained.
Addressing (A). The module A aims to derive the read/write addresses storage matrix M for each streaming edge r,, To reconcile the conflict between the "representing" and "addressing" functions of the representation vectors and increase the diversity of network pathways, we extract the intermediate
4

---

Published as a conference paper at ICLR 2024
representations (i.e., output results of specific hidden layer in f.) of {fn(o(z))) fn (d(x:))))
denoted as (no(x)' na(x)))), ), and imput them into a network component to obtain the refined vector set (n ). ). (n - fro(s)) rd(a)) } E R as the basis of addressing,
Aln ma H1 SparseMax(1$ (f-(n N, (f N)NN)) - (a a d( (2)
Here, . E R4X,, is an addressing matrix with learnable parameters, which can be viewed as differentiable simulation of the hashing process used in traditional summarization structures (Rae) al., 2019). Then, the matrix multiplication of V and the transpose of (ro(xz) ,d(==)) results in the addresses (xx))) and d((x)) The two addresses, corresponding to out/in direction, jointly determine the storage positions of the representation vectors (i.e., (no(s;) nd(x=))) of streaming edge within 1,2 slots in the memory matrix M E Rl,,,, Specifically, we treat a((=)) as the row address and ad(xa) as the column address, and determine the specific storage positions (=()))d(( E RR. xL, of
(no(z)) nd(x:)) in M. In combination with the out/in bidirectional representation vectors of length 21, in one slot for different edges, M provides a joint compression storage for nodes and edges. This efficient and interpretable novel storage paradigm not only provides sufficient information for decoding, but also lays the foundation for the extension of multiple graph query types as shown in Section 6 Moreover, we utilize Sparse SoftMax (Laha et al. 2018 Martins & Astudillo 2016) for the normalization of addresses to reduce the noise in information stacking The B is a learnable scale value that controls the sparsity of addresses, which is verified in Appendix A.6
Decoding (D). Given a query edge Ej. the module D aims to decode the stacked information of ey read from M based on address d((s)),d(ss) to obtain the corresponding query result. The module has one network component Sa.
Dia ((s))))). M, n (loe)) (n))))))))))))))))))))) (e,,) ((S)) fa(a ((t) o,, n (e5)) on dley), W(S))) (e,)) (3)
Here, the representation vectors (e,) and (e,) for ej. along with the total sum of all incremental weights of the graph stream WSG),, are fed into fa as auxiliary decoding information, where symbol @ denotes the vector concatenation operation. The ((e)),d(es) .M represents the operation for
reading ey's 's information from matrix M. In this paper, the implementation of o adheres to the
classical content- content-based read mechanism (Wu et al. 2018 Rae et al. 2019 Graves et al., 2016 2014).
and incorporates an auxiliary MinGain term:
a so(l))) M a olee))alee) @ M min( mine(aatey)ddle) @ ot gn ((ep))
(4)
Content Based Read
MinGain Term
Here, the @ represents the summation of all slots in M weighted by address d(c)) The MinGain represessssntss the minimum value in a (())) @ .M after normalization based on n p(es) @ n (e;)) aiming extract the crucial low numerical value bits for decoding but are easily overshadowed by stacked noise from other large value bits. The detailed formalization is outlined in Appendix A.
4.3 OPERATIONS
Operation Store is executed by feeding an incoming streaming edge x; into R and A to obtain rep- resentation vectors (n=() nd(())) and address d(x.), Then, concatenation vector is additively stored to M after being multiplied by incremental weight Aws,
== M + a ((x)), @ (n @ n n=d(=))) Awy
Here, C represents element-wise matrix multiplication. Additive storing (Rac et al. 2019 is an efficient and commonly used method in memory networks. Note that the out/in bidirectional storage of origin node information no())) and destination node information d((a)) are independent in one memory slot(i.e., first in bits are for ((2;) and last L, bits are for n n=(()))
Operation Query estimates the cumulative weight of a given query edge ej after storing a graph stream Sg. Firstly, representation vectors (no())) n dlls)) and the address a (((s))d(es) are obtained, following a similar process of the Store operation. Then, ((((e)).d(e,) o MM, n @ dilss) and the summation of all weights W (Sc) are jointly input into 'D to obtain the estimated weight (ez). For detailed description about operations, please refer to Appendix[A.]
Relevant ablation experiments be found in Appendix A.7
5

---

Published as a conference paper at ICLR 2024
4.4 TRAINING
The Mayfly employs a meta-learning training algorithm to endow effective parameters in all learnable network modules. Jn. fa. A. and fa. Adhering to the standard setup of meta-learning, the fundamental unit of the Mayfly training is the meta-task, which guides the latent optimization direction. In our paper, the Mayfly consists of two offline training phases in correspondence larval tasks and metamorphosis tasks. Both phases share the same training algorithm. And the formal algorithms for training and generating meta tasks are discribed in Appendix A..
two types of meta-tasks.
Training Algorithm. During training process, the Mayfly iterates over the set of larval tasks or metamorphosis tasks. We can view the training process on a single task as simulating the storing and querying of a graph stream instance while computing the error for optimizing the learnable modules. Therefore, a (larval or metamorphosis) task l. consists of two parts, a support set 85; and a query set (k) (k)
Ge- The support set s {2) , 222 .... represents graph stream instance S(k) with streaming edges
(R) Qw (e... represents the edges {ej (*) to be queried along { ). while the query set qx:(e]
with their query results (e, )). We use the balanced (relative) mean squared error as the loss function L with learned parameters X and X2 (Kendall et al. 2018).
(6) Larval Task Generation. In the larval phase, the target of larval tasks is to train the Mayfly with basic abilities to summarize graph streams while maintaining generality to different graph streams. In practical applications, the distribution of edge weights in graph often follows skewed distributions, especially the Zipf distributions (Kali) 2003 Chen & Wang 2010, Aiello et al. 2002). So, we constitute larval tasks by making the edge weights follow a wide range of Zipf distributions with varied parameter a. The family of Zipf distributions constitute distribution pool P. Note that the Mayfly does not rely on the clumsy memorization of larval tasks. The basic summarization capabilities learned in this phase apply for diverse graph streams beyond the larval tasks.
- (e,) (w(e))) /2> + (Qw(e,) (e(e) + log d1
A larval task l is generated through three steps, which essentially synthesize a graph stream S First, we synthesize streaming edges (ar(*) with the stream length | E [1, where the two nodes of streaming edge are randomly sampled and encoded from unified numerical ID space. Second, a distribution instance (*) is sampled from the distribution pool P. For each ar! (R( a weight is assigned, which is obtained by the product of total weight sum W (s(()) and a sample from the
distribution p(A). Finally, the synthetic graph stream (&)) serves as the support set 8k, and the query result (e ) for all e// constitutes the query set Ok-
Metamorphosis Task Generation. In the metamorphosis phase, the metamorphosis task aims to capture and reflect typically skewed patterns found in real graph streams. If the empirical weight distribution is available (e.g., from historical records sampled episodes of real graph streams), it can be used to generate the metamorphosis tasks. To generate metamorphosis tasks, we extract consecutive portions of different lengths from the real stream. In addition, we intentionally blur the relationship between edges and their weights in these extracted portions. This deliberate blurring allows the metamorphosis tasks effectively represent the concept drift characteristics of the stream (see extra experiments in Appendix A.9 AA.9)
5
EXPERIMENTS
5.1
SETUP
Datasets. We use four commonly used public graph stream datasets, comprising two medium-
datasets (Lkml, Enron) and two large-scale datasets (Coauthor, Twitter). The Lkml (Gou et al. 2022 Xu & Zhou 2018) and Enron Shin et al. (2020); Lee et al. (2020) pertain to communication/sochi social networks. Specifically, Lkml contains 1,096.4 4.0 communication records exchanged among 63,399 Linux kernel mail network nodes, and Enron captures 475,097 email exchanges across 17,733 addresses. Coauthor (Newman 2001) represents the co-authorship social network among researchers, embodying 2,668,965 streaming edges. The original Twitter dataset is static with no duplication, encompassing 52,579,682 (,2 nodes and 1,963,263,82 edges. We follow the setting of (Gou et al. 2022)

---

Published as a conference paper at ICLR 2024
Table 1: Results in Lkml & Enron Dataset
1kmll Datnset
Faron Dataset
Model
Length
20K
SOK
200K
800K
20K
40K
200K
400K
TCM
ARE:
10.09
10.22
15.89
10.48
66.30
1.77 10.02
3.71
10.03
16.01
1.0002
25.07
10.01
(B=64KB)
AAE
1.93
10.14
9.84
+0025
26.11
+0.88
110.56
=0.38
2.08
+0002
4.56
+0.03
24.13
4:003
45.06
#0.01
Subimago
ARE
6,24
1.97
11.21
+4.07
18.12
+5.83
42.96
11118
3.80
3.80
+0005
4.13
=0.03
7.51
+0.05
10.00
=0.01
(B=6KBB)
AAE
9.05
+3220
18.33
47.19
11.14
77.07
=2.35
4.30 +0.03
4.91
+0.03
11.13
20.04
17.73
=0.01
Imago
ARE
0.94
10005
1.33 1.006
2.07 10.07
5.86
0.01
1.00 1.001
1.10 10001
2.37 10.01
3.42 10.01
(BKK))
AAF
1.57 1.008
2.62 1:0.12
3.92
10.12
9.62
=003
1 1:000
1,43 10.01
3.72 10.00
6.14 10.01
TCM
ARE
0.52 10.05
2.77 1:0.1
7.34 1.019
31.34
00005
0.66 1.0001
1.50 1.001
6.90 10.01
10.22 10.0
(B=128KB
AAE
0.81 +0.08
4.55 +0.11
12.34
+0.29
53.44
00.16
0.79 +0001
1.87 =0.02
10.57
40.01
19.82 #0.01
Subimago
ARE
2.43 1:037
4.30 1:060
6.46 1:0.6
16.89 00220
2.58 10002
3.22 10.02
4,93 40.02
6.37 10.01
B
AAE
3,36 1.062
6.78 11.13
10.76 1:668
29.03 0.36
2.89 1:000
3,80 10.03
7.34 10.02
11.43 10.01
Imago
ARE
0.50 0.002
0.77 4.003
1.00 0.003
2.51 0.00
0.31 10.01
0.60
10.01
1.67 1:001
2.42 =0.01
(B=128KB)
AAE
0.96 +0.03
1866 0.008
2.63 00008
5.17
0.00
0.50
#0.01
0.93 #0.01
2.88 +0001
4,70 10.01
which assigns weights to all edges using Zipf distributions, resulting in 10.929,000 229,,205,002. streaming edges. These datasets exhibit varying degrees of deviation from the ideal Zipf distributions. Please refer to the Appendix A.4 for the visualization of dataset statistics. In addition, each node in the four datasets assigned a numerical ID in binary encoding.
Baselines. We have chosen TCM and GSS as the competitors, which are SOTA under small budgets. Two commonly accepted metrics, average absolute error (AAE) and average relative error (ARE), are adopted for evaluation. The code for Mayfly has been included in the supplementary materials. GSS and TCM, utilize the open-source code provided alongside their papers.
Parameters. We have implemented In and f, in MLP with 5-layer and 2-layer of size 32, followed by the batch normalization. The intermediate representation of the third layer of fn is fed into fr as inputs. The fa is implemented in a 3-layer MLP with residual connections, where each layer is of size 64. Relu function is chosen for layer connections. The space budget (B) of the Mayfly is allocated matrix M following the common setting of neural data structures (Rae al. 2019). Further parameter details, including module sizes and settings of M, can be found in Appendix A.5
We set 7 60, 000 and use the Zipf distributions with a ranging from 0.3 to 0.8 to build the distribution pool P. The total weight sum is ranging from 5 to 50 times of the edges in graph. The number of training steps is 500,000 and the learning rate is 0.0005.
Larval Phase.
Metamorphosis Phase.
We split each dataset into Drroin and Drest, using a 2:8 based on timestamps. By doing so, there must be large population of streaming edges in Drest that never appear in Dirain. for examining the generality of the Mayfly. Derain is used for metamorphosis task generation, and Drest used for testing. The number of training steps is only 10% of that in the larval phase.
5.2 RESULTS ON REAL DATASETS
We extract set of sub-streams with different lengths from Diest of two medium-sized real dataset, Lkml and Enron, for testing how the data summarization technique scales. Table T shows the performance Lkml and Enron, where imago dominates TCM in all testing cases. For example, the AAE of TCM is about 45 (Enron, B=64KB, length=40OK), and the AAE of imago is only 6, which is 6.5 times lower. Also, it shows that all methods degrade w.r.t. the stream length, while the performances of imago and subimago are quite stable, compared to the dramatic degrading of TCM. For example, when increasing the stream length from 20K to 800K (Lkml, B=64KB), the AAE value of TCM increases about 52 times, while the AAE of imago only increases about 5 times, which is an order of magnitude lower, An interesting point is that subimago outperforms TCM, when the stream length is higher than 200K, demonstrating the strong knowlegee generality of Mayfly.
We evaluate the Mayfly's performance on two large-scale datasets. For million-scale Coauthor, we deploy a 256KB-sized Mayfly. For billion-scale Twitter dataset, we adopt pragmatic approach to circumvent the extensive training time of higher-budgeted Mayfly. Specifically, we employ a simple hash function, which evenly maps the streaming edges over cluster of 128KB-sizer Mayfly instances, The space budget is 0.5GB, a reasonable but relatively small allocation, as in previous settings (Tang al. 2016: Gou et al. 2022). Table 2soows Mayfly consistently outperforms TCM.
We proceed to compare the performance of our method with another SOTA, GSS. We find that GSS incurs considerable missing hits when the budget is tight, so that the result is often not found for low-weight querying edges. For example, in Figure 2 the hit rate of GSS is less than 20% in all cases, while the hit rates of TCM and imago are 100%. To force the comparison happen, we consider
7

---

Published as a conference paper at ICLR 2024
Table 2: Results in Coauthor & Twitter Dataset
Model
TCM
Subinago
Imago
Dataset
ARB
AAE
ARE
AAE
ARE
AAE
13.41 10.01
61,70 10001
4.51 10.01
19.32 10001
1.54 10.01
8.81 1.00
63.02 40.12
245.25 1:051
16.30 +0008
63.53 10037
2.18
4:001
8,50 0.05
Table 3: Results in Synthetic Datasets
64KB
128KB
Zipf
0.2
0.6
0.2
0.6
ARE
15.45
10002
18.12 1.002
20.70 10006
6.71 00.01
7.61 1:001
8.36 10.01
TCM
AAE
33.13
40009
77.50 -:0.08
41.21 #0.08
38.58 =0.03
32.54 +0.03
+0.02
ARE
1.23 +0001
2,05 +0001
5.31 #0.24
1.01 =0.01
1.72 10.01
4,45 +0.03
Sublmago
AAE
6.92 1:001
8.48 1:0.02
10.58 10.44
5.61 00011
7.14 10001
8.80 +0.08
kmm
ARE
0.44 00.01
0,97 +0.03
1.44
0.39 =0001
0.38 =0.01
2.28 +0.56
AAE
2.54
0.004
4.68 1:013
10.41 42292
2.40 =0.01
2.83 1.003
5.55 11.13
ImagoFarrnn
1.001
10001
10001
0.17
10001
2.21
AAE
2.66
4.0.1
4.82
+0002
7.17
10007
1.05 0.01
3.21 10.01
4.92 1:0.09
the heavy edge query Tang al. 2016), a variant of the edge query which considers high-weigh edges. We compute the top 5% and top 10% heavy edges from the original data as the ground truth. For each of the heavy edges, we retrieve its weight from imago, TCM, and GSS, and compare them with the ground truth. The results on Lkml and Enron are shown in Figure (a) and (b), respectively. The result shows that the performance of imago dominates those of TCM and GSS. For example. the AAE value of imago is about 14.5, while the AAE values of GSS and TCM are 23.9 and 55.6, respectively (Enron, B=64KB, length= 400K).
100
60
10
50
500
1003
7500
2000
St Jangeh
Stramm
Adapton 2003
Adaptor
(a) Lkml
(b) Enron
(a) zipf:
(b) zipf:0.4
Figure 2: Heavy Edge Queries and Hit Rates
Figure 3: Concept Drifts
5.3 RESULTS ON SYNTHETIC DATASET
To investigate Mayfly's performance in potential data stream concept drift (i.e., distributional shift) scenarios, we evaluate subimago synthetic graph streams of length 500K, where the accumulative weight of an edge follows Zipf distributions with a E {0.2, 0.6, 1.0]. Note that 0.2 and 1.0 are not covered by the distribution pool P in the larval phase, for testing the generalization. We also examine the performance of imagos, which have been adapted to Lkml and Enron, on synthetic datasets. Table ademonstrates the result on synthetic graph streams, where subimago outperforms TCM in all testing cases, highlighting its robust knowleeeee generalization capabilities. For example, when Zipf parameter 0.2 with 64KB budget, the ARE of subimago 1.23, whereas the ARE of TCM is 15.45. Furthermore, the performance of imago remains impressive, indicating that Mayfly retains its robust generalization capabilities, even after adapting to specific distributions.
To delve deeper into concept drifts, we show the real-time performance of imago several different distributions, when adapting to a specific Zipf distribution a=1.0. The Figure 3 along with the Figure 12 in Appendix A.12 shows a significant improvement with the adapted Zipf distribution
==1.0. Mcanwhile there is a slight fluctuation with other distributions a E {0.4, 0.6, 0.8). imago still exhibits superior performance. For more analysis of concept drifts, please refer to Appendix A.9
EXTENSION
6.1 EXTENSION TO ATOMIC QUERIES BY CONSTRUCTING NEW INFORMATION PATHWAY
After the metamorphosis phase, the imago form of the Mayfly has acquired the capability in summa- rizing graph streams and handling edge queries, laying down a foundation for other types of queries. We study on extending the Mayfly to two other new types of atomic queries on graph streams, node queries and connectivity queries by constructing new information pathways coupled with adding new decoding modules, rather than starting the entire training process from scratch.
8

---

Published as a conference paper at ICLR 2024
3.0
1.0
ICM
Imago39
12009 (mag
64K2 TOM
TCM
2.0
2.5
12698, Prago
32898
TCV
200
250
120KB Image
ME6 TOM
0.8
64K5 Foays
5 1.5
6400 m1
4 150
$4K3
0.7
100
1.0
100
0.5
50
0.5
20K
40K
6OK
BOK
100K
5K
10K 15K
20K
25c
8
10
Stream, krream.erngh
Stream, longth
Path. lotgh
Scale_ rotlot
Figure 4: Connectivity Query
Figure 5: Node Query
Figure 6: Path Query Figure 7: Subgraph Query
Firstly, we craft new information pathways for the new atomic queries, which determine how the information in M is utilized. Subsequently. introduce new Decoding modules trained on relevant meta-tasks for new atomic queries. This approach enables Mayfly to adapt to new atomic query types by solely updating the new Decoding modules while keeping other module parameters unchanged.
We elaborate this extension strategy using node queries which have significantly different information pathways from the edge queries. Firstly, for a given query node Um. we derive vector n nm and address amm using the representation and addressing modules. As described in Section 4.3 the source and destination node information of streaming edges are stored separately within a single slot of M. Specifically, the source node information occupies the first l, positions of the slot, while the destination node information occupies the remaining i, positions. Therefore, Queue (v,.) is relevant to the slice .M E RR', constituted by the first I, of 21, positions for all slots in M, and Qn.., (Um) is relevant to the slice constituted by the rest ln positions, Ma M M Next, the retrieved information a"m o M (or am o M along with the auxiliary information nm and W (Sa), are jointly input into the decoding module to obtain the estimated Q (or Qm..):
Dia"m o Mo/d ,n"" W(S6)] > fa(a"m o Mo/d "T"" ,T ((G))) + @mout/in
Figure 5 shows the performance of the imago on Quoue on Lkml, which significantly outperforms that of TCM, especially when the length of the graph stream increases.
The operation of connectivity queries is similar to that of edge queries with the sole distinction being that the output the decoding module takes the form of binary classification labels indicating the connectivity. In addition, we examine the query accuracy for high- weight edges, which are more significant in the graph (Tang et al., 2016). We use edges with top 50%, 30,, and 10% weights as positive samples in test tasks. Figure 4 shows the accuracy of the extended imago form of the Mayfly on the test tasks, based on Drest of the Lkml dataset. demonstrates that imago exhibits a more stable performance, especially for high-weight connectivity queries over varied stream lengths. Conversely, TCM exhibits insensitivity to edge weights and incurs a notable performance drop.
6.2 EXTENSION TO MISCELLANEOUS QUERIES BY INVOKING ATOMIC QUERIES
Consistent with TCM and GSS, we could amalgamate multiple invocations of the above atomic queries to cater to a diverse range of graph queries. We construct and evaluate the path queries and subgraph queries (Tang et al. 2016) using edge queries and connectivity queries the main building blocks. The graph path queries aim to find the maximum flow along a given path which is a sequence of directed edges. The subgraph queries retrieve the aggregated weight for the edges within the subgraph. For detailed information about these query semantics, please refer to Appendix 10 Figures ( and demoonstaae the results of two queries (Lkml, length 20K). It shows that imago outperforms TCM on path queries in all cases. Also, imago exhibits superior performance to TCM in subgraph queries, showing much better stability as the size of the subgraph increases.
7 CONCLUSION
In this paper, we propose the first neural data structure for graph stream summarization, called the Mayfly. The Mayfly is based on memory-augmented networks and meta-learning, allowing it to be pretrained through automatic and synthetic meta-tasks, and rapidly adapt to real data streams. With specific configurations of information pathways, the Mayfly enables flexible support for a broad range of graph queries, including edge, node, path, and subgraph queries. We conduct extensive experiments and detailed analysis to demonstrate the superiority of the Mayfly compared to its handcrafted competitors and gain insights into our proposals.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work is supported by NSFC (No.61772492, 62072428).
REFERENCES
Charu C Aggarwal, Yao Li, Philip S Yu, and Ruoming Jin. On dense pattern mining in graph streams. Proceedings of the VLDB Endowment, 3(1-2):9759984, 2010.
Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Analyzing graph structure via linear measure- ments. Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms. pp. SIAM, 2012.
William Aiello, Fan Chung, and Linyuan Lu. Random evolution in massive graphs. Handbook of massive data sets, pp. 97-122, 2002.
Brian Babcock, Shivnath Babu, Mayur Datar, Rajeev Motwani, and Jennifer Widom. Models and issues in data stream systems. In Proceedings of the Iwenty-frrs ACM CGGMOD-SGAATT-SIGART symposium on Principles of database systems, pp. 1-16, 2002.
Dimitris Bertsimas and Vassilis Digalakis. Frequency estimation in data streams: Learning the optimal hashing scheme. IEEE Transactions Knowledge and Data Engineering, 2021.
Andrei Broder and Michael Mitzenmacher. Network applications of bloom filters: A survey. Internet mathematics, 1(4):485-509, 2004.
Yukun Cao, Yuan Feng, and Xike Xie. Meta-sketch: a neural data structure for estimating item frequencies of data streams. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 37, pp. 6916-6924, 2023.
Moses Charikar, Kevin Chen, and Martin
Finding frequent items in data streams, In Automata, Languages and Progranming: 29th International Colloquium, ICALP 2002 Málaga, Spain, July 8-13, 2002 Proceedings 29, pp. 693-703. Springer, 2002.
Lei Chen and Changliang Wang. Continuous subgraph pattern search over certain and uncertain graph streams. IEEE Transactions on Knowledge and Data Engineering, 1293)1093-1 2010.
Graham Cormode and Shan Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithuss, 55(1):58-75, 2005.
Alessandro D' Alconzo, Idilio Drago, Andrea Morichetta, Marco Mellia, and Pedro Casas. A survey on big data for network traffic monitoring and analysis. IEEE Transactions on Network and Service Management, 16(3):800 813, 2019.
Sofia Fernandes, Hadi Fanaee-T, and João Gama. Tensor decomposition for analysing time-evolving social networks: An overview. Artificial Intelligence Review, 54:2891-2916, 2021.
Xiangyang Gou, Lei Zou, Chenxingyu Zhao, and Tong Yang. Graph stream sketch: Summariz- ing graph streams with high speed and accuracy. IEEE Transactions Knowledge and Data Engineering. 2022.
Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. arXiv preprint 140.541410.5401, 2014.
Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Daníhelka, Agnieszka Grabska- Barwiáska, Sergio Gómez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John Agapiou, et al. Hybrid computing using a neural network with dynamic external memory. Nature, 538(7626): 471-476, 2016.
Sudipto Guha and Andrew McGregor. Graph synopses, sketches, and streams: A survey, Proceedings of the VLDB Endowment, 5 5(12):2030-2033 2012.
Jin B Hong, Dong Scong Kim, Chun-Jen Chung, and Dijiang Huang. A survey on the usability and practical applications of graphical security models. Computer Science Review, 26:1-16, 2017.
10

---

Published as a conference paper at ICLR 2024
Timothy Hospedales, Antreas Antoniou, Paul Micaelli, and Amos Storkey. Meta-learning in neural networks: A survey. IEEE transactions on pattern analysis and machine intelligence, 44(9): 5149-5169, 2021.
Chen-Yu Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning-based frequency estimation algorithms. In International Conference on Learning Representations, 2019.
Zhiguo Jiang, Hanhua Chen, and Hai Jin. Auxo: A scalable and efficient graph stream summarization structure. Proceedings of the VLDB Endowment, 16(6):1386-133 1398, 2023.
Raja Kali. The city as giant component: random graph approach to zipf"s law. Applied Economics Letters, 10:717 720, 2003.
Alex Kendall, Yarin Gal, and Roberto Cipolla. Multi-task learning using uncertainty to weigh losses for scene geometry and semantics. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 7482-7491, 2018.
Jihoon Ko, Yunbum Kook, and Kijung Shin. Incremental lossless graph summarization. In Proceed- ings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 317-327, 2020.
Deyu Kong, Xike Xie, and Zhuoxu Zhang. Clustering- based partitioning for large web graphs. In 2022 IEEE 38th International Conference on Data Engineering (ICDE), pp. 593-606. IEEE, 2022.
Tim Kraska, Alex Beutel, Ed H Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings of the 2018 international conference on management of data, pp. 489-504, 2018.
Anirban Laha, Saneem Ahmed Chemmengath, Priyanka Agrawal, Mitesh Khapra, Karthik Sankara- narayanan, and Harish G Ramaswamy. On controllable sparse alternatives to softmax. Advances in neural information processing systems, 31, 2018.
Dongjin Lee, Kijung Shin, and Christos Faloutsos. Temporal locality- sampling for accurate triangle counting in real graph streams. The VLDB Journal, 29:1501-1525, 2020.
Jiayu Li, Tianyun Zhang, Hao Tian, Shengmin Jin, Makan Fardad, and Reza Zafarani. Graph sparsification with graph convolutional networks. International Journal of Data Science and Analytics, pp. 1-14, 2022.
Yi Li, Honghao Lin, Simin Liu, Ali Vakilian, and David Woodruff. Learning the positions in countsketch. In The Eleventh International Conference on Learning Representations, 2023. URL ltttss://ppeneeiiee net www.mmiid--V
Yike Liu, Tara Safavi, Abhilash Dighe, and Danai Koutra. Graph summarization methods and applications: A survey. ACM computing surveys (CSUR), 51(3):1-34, 2018.
Yongqiang Liu and Xike Xie. Xy-sketch: on sketching data streams at web scale. In Proceedings of the Web Conference 2021, WWW '21, pp. 1169-1180, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450383127.
doi: 00114553442381.34499998 URL htttp:://di..ogge 1et...115531333 11t.....11111111111111 34499844
Yongqiang Liu and Xike Xie. A probabilistic sketch for summarizing cold items of data streams. IEEE/ACM Transactions on Networking, 2023.
Ziyi Ma, Jianye Yang, Kenli Li. Yuling Liu, Xu Zhou, and Yikun Hu. A parameter-free approach for lossless streaming graph summarization. In Database Systems for Advanced Applications: 26th International Conference, DASFAA 2021, Taipei, Taiwan, April 11 11-14, 2021, Proceedings, Part I 26, pp. 385-393. Springer, 2021.
Andre Martins and Ramon Astudillo. From softmax to sparsemax: A sparse model of attention and multi-label classification. In International conference on machine learning, pp. 1614-1623. PMLR, 2016.
Andrew McGregor. Graph stream algorithms: survey. ACM SIGMOD Record, 43(1):9-20, 2014a.
11

---

Published as a conference paper at ICLR 2024
Andrew McGregor. Graph stream algorithms: survey. ACM SIGMOD Record, 43(1): 2014b.
Alan Mislove, Massimiliano Marcon, Krishna P Gummadi, Peter Druschel, and Bobby Bhattacharjee. Measurement and analysis of online social networks. In Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, pp. 29-42, 2007.
Mark EJ Newman. The structure of scientific collaboration networks. Proceedings the national academy of sciences, 98(2):404 409, 2001.
Jack Rac, Sergey Bartumov, and Timothy Lillicrap. Meta-learning neural bloom filters. In International Conference on Machine Learning, pp. 527 5271-5 PMLR, 2019.
Adam Santoro, Sergey Bartunov, Matthew Botvinick, Daan Wierstra, and Timothy Lillicrap. Meta- learning with memory-augmentted neural networks. In International conference machine learning, pp. 1842-1850. PMLR, 2016.
Nasrin Shabani, Jia Wu, Amin Beheshti, Quan Z. Sheng, Jin Foo, Venus Haghighi, Ambreen Hanif, and Maryam Shahabikargar. A comprehensive survey on graph summarization with graph neural networks, 2023.
Neil Shah, Danai Koutra, Tianmin Zou, Brian Gallagher, and Christos Faloutsos. Timecrunch: Inter- pretable dynamic graph summarization. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1055-1064) 2015.
Kijung Shin, Sejoon Oh, Jisu Kim, Bryan Hooi, and Christos Faloutsos. Fast, accurate and provable triangle counting in fully dynamic graph streams. ACM Transactions on Knowledge Discovery from Data (TKDD), 14(2):1-39, 2020.
Isabelle Stanton and Gabriel Kliot. Streaming graph partitioning for large distributed graphs. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1222-1230, 2012.
Nan Tang, Qing Chen, and Prasenjit Mitra. Graph stream summarization: From big bang to big crunch. In Proceedings of the 2016 International Conference on Management of Data, pp. 1481-1496 2016.
Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, et al. Matching networks for one shot learning. Advances neural information processing systems, 29, 2016.
Yan Wu, Greg Wayne, Alex Graves, and Timothy Lillicrap. The kanerva machine: generative distributed memory. arXiv preprint 1XXXv:88040017555 2018.
Yulin Xu and Minghui Zhou. A multi-level dataset of linux kernel patchwork. In Proceedings of the 15th international conference on mining software repositories, pp. 54-57, 2018.
Peixiang Zhao, Charu C Aggarwal, and Min Wang. gsketch: On query estimation in graph streams. arXiv preprint arXiv:111..7166 2011.
Peixiang Zhao, Charu Aggarwal, and Gewen He. Link prediction in graph streams. In 2016 IEEE 32nd international conference data engineering (ICDE), pp. 553-564, IEEE, 2016.
Houquan Zhou, Shenghua Liu, Kyuhan Lee, Kijung Shin, Huawei Shen, and Xueqi Cheng. DPGS: Degree-Preservving Graph Summarization, pp. 280-288. doi: 10. 137/1 978161 1976700.32. URL
httts:://ppbbr a am. org/ dol/ atto//a/////// 00 1ww.1117/.... 9781 1971709
Kai Zou, Xike Xie, Qi Li, and Deyu Kong. Gx-plug: middleware for plugging accelerators to distributed graph processing. In 2022 IEEE 38th International Conference on Data Engineering (ICDE), pp. 2682-2694, 2022. doi: 10. 00.1099CCDDE3375500220222
12

---

Published as a conference paper at ICLR 2024
A APPENDIX
A.1 DETAILS OF MAYELY OPERATIONS
[ describes the details of Mayfly's ss operations on (stream) edge ej. including dimensions conversion operations and broadcast operations.
Algorithm 1: Details of Mayfly Operations
Operation Store (o(2;), d(z;), Aw,, M):
nofx)) n nolass ,ndlt)) ,n diaa) + Reprosentation ion (R) (o(zs), aate) ddaa)
adll + -Addressing (A) (n)())) mlld)
(ata)ia (a ((
n + nno())) nd)e))
n &- ChangeShapeen" R R4x4x22, ((()))d(())) + ChangeShape(aatuul M (z))),((a)) @ n Aw,
glaxl, Rlaxlx2la))
Operation Query (ole;), d(e,), M, W(S))):
noles) n n(te)' in ,n n diee)'' + Representaticn (R) (o(e)), d(e,))
ae(s)), ddee)) (o(s))d(es)) + (ale)))
( + Addressing (A) (ndles) n(te))'
Qu(es) t Decoding (D) ((a M}, (lss)) @ nlo)) W(G))):
return (e));
Module Representation (R) d(2)))
no(z)) n o (o(o)))
dlaa) (edd,, naaay +- fa(d(zs))
return n ((m)) nolae) ,n(tn), daa)
Module Addressing (A) (na) nn da))) ):
p((z)) - fr(o(xi))) r(tt)) fol((zi)))
(zx)) + 8. (oole))TA a + B- (Idtz)yT
ozz)) + SparseMaz( (lr))); old)) + SparseMaz(addd))
return a ofm)) d(ra))
Module Decoding (D) (e M), nles) @ (ee)) W(Sa)):
n t- n((e) @ n d(es)
c + Content RasedeeddM ((s))))(es))
é MinGain(cfi,ni n5)
info + Concatenate(( ct W(S)))
(w()s) <- Salinfo)
return (e))
Function ChangeShape (Vector, R" R", ):
Change shape of a vector from R" to R
return vector
Function Contant (M, d((es),d(e)) a (ec)))((e)) + (alumggeShappeaaateee.e.. pelx 1 (x(
M' + ChangeShapee (M, R x1,21, x221))
c² = o M'
da & ChangeSSappe(mi R122l,, R22))
return c
Function MinGain (n
+ where(n" ni
t where(n < MAX,0) 0)
e [(ct + //2 I.mnn()
return
c
13

---

Published as a conference paper at ICLR 2024
A.2 DETAILS OF TRAINING ALGORITHM FOR MAYFLY
We give a detailed training algorithm of Mayfly in Algorithm
Algorithm 2: Mayfly Training Framework
Data: Mayfly (R, A, D) with all learnable parameters 0, larval task set T or metamorphosis
task set TM:
for each task tx (sk. 9k)
TM/TMMM do
Initialize ((s = 0;
(k) for s; 88 do
store (o(x)"), (H)) Aw! (8) M);
((S + Aw!!)
for Qm(()
(k)) E qb do
Qm(e))) + Query (o(e)))), (.) M, ((
L LossFunc(Quu (1) (m(()))))
Backprop through queries and stores: dL/d0;
Update learnable parameters: 0 - Optimizer(OO dL;/d0;; Normalize N:
Clear M;
A.3 DETAILS OF ALGORITIM FOR LARVAL/METAMORPIISII TASK GENERATION
The detailed generating algorithms for larval/mettamrrphoiis meta-tasks are shown in Algorithm and Algorithm respectively.
Algorithm 3: Generating Larval Task
Data: Zipf distribution pool P; Stream length range [1, 7]: Result: larval task t&:
Sample stream length (s()) from [1,7]:
Sample total weight sum ((((()) from 5 x (5())) 1,50 |
Sample distribution instance p P:
for i E [ do
Systhesize streaming edge x Sample p; (k) ~ (() and Aw! (k) + ((s x (k),
add .x( to the 4 store set (sx) with weight (t)
Construct &g 's query set (gx) with all (e) Qu (ef))))
return a larval task txi
Table 4: parametes Considered
Learning rate
1E-4,5E
Hidden size of fn.
32,64
Hidden size of fr
32,64
Hidden size of fa
32,64,128
A.4 VISUALIZATION OF DATASETS
Table showss the statistics each datasets. We also present the distributional characteristics of Enron, LKML and Coauthor datasets on log-log scale in Figure g These datasets exhibit varying
14

---

Published as a conference paper at ICLR 2024
Algorithm 4: Generating a Metamorphosis Task
Data: Training set Dirain;
Result: A metamorphosis meta-task 1x: Sample stream length [ from [1, Dirain
Extract continuous substream from Dtrain with length |sg support set Shuffle the correspondence between edges and their weights in support set sxi Multiply all weight Aw; in support set St by multiplier [0]
Construct i& s query set qs with all (e))) Qu(e, )+)
return metamorphosis task tx:
Table 5: Settings of N and M
B
1
I,
1
64KB
32
8
16
128KB
45
8
16
degrees of deviation from the ideal Zipf distribution, which is typically represented as straight line in the figure.
A.5 DETAILED SETTINGS OF EXPERIMENT
We did not deliberately tune the parameters of the Mayfly. Instead, we tried few conventional neural network settings in Table (best parameters are bolded) on an early instance of Mayfly and settled on one that strikes balance between accuracy and efficiency. All the other experiments just simply followed the same setup. In addition, the default settings N Rixx,, and M E gl x21, under different budgets are shown in Table 5 Table 7 below presents a detailed breakdown of parameters for each network module, alongside the classic networks AlexNet and VGG16 for comparison. They are all small-scale neural networks with relatively low storage and training overheads. In addition, according to the consensus in neural data structures, the overheads of other modules can be amortized across different applications (Rae et al.) 2019 Cao al. 2023). After training, they be copied to multiple application scenarios, analogous to the overhead of loading hash function libraries dynamically in TCM.
All of our experiments run at a NVIDIA DGX workstation with CPU Xcon-8358 (2.60GHz, 32 cores), and 4 NVIDIA A100 GPUs (6912 CUDA cores and 80GB GPU memory on each GPU).
A.6 ADDRESSING MECHANISM
We gain insights into the addressing mechanism of the Mayfly by observing key variables in the addressing module during the larval phase. According to the properties of Sparse SoftMax (Laha) et al. 2018 Martins & Astudillo 2016), the 2-norm of 3 continuously changes to control the sparsity of addresses (i.e., the proportion of non-zero bits in the vector), while the 2-norms of other variables, such as representation vectors and refined vectors, remain stable, as shown in Figure 9 (a). It is also evident that the 2-norm of 3 increases progressively to encourage the sparsity of addresses, ultimately converging to 1, as shown in Figure (a) and (b). It indicates that the Mayfly tends to allocate the cumulative information of an edge only one slot of M, thus alleviating information overlap. Moreover, Figure (c) shows that the variance of the number of stored edges across multiple slots
Datasets
Lkmi
Enron
Coauthor
Twitter
Number of Nodes Number of Streaming Edges Graph Type
63,399
17,733
40,421
52.579.682 10,929,205. 002 Social
1,096,440 Communication
475,097
2,668,965
Communication
Co-authorship
Table 6: Statistics of Datasets
15

---

Published as a conference paper at ICLR 2024
1000
Zipt Enron
Zipf
Zipf Coauther
Lkml
Weight
100
Weight
Weight
100
10
0
10
100
1000
10000
0
10
100
1000
10000
0
1000
1000000
Rank
Rank
Rank
(a) Enron Dataset
(b) Lkml Dataset
(c) Coauthor Dataset
Figure 8: Visualization of Datasets
Table 7: Module Parameters
Model Parameter
Maylly64KB
Maydhy|2KK
Maylly256KB
AlexNet
VGGT6
Embedding Module
1.93K
1.93K
1.93K
Addressing Module
2.09K
2.30K
2.62K
Decoding Module
5.27K
5.27K
5.27K
Total
9.29K
9.51
9.82K
60907.38K
1115786.64K
in M continuously decreases, indicating its automatic learning of evenly storing edges to the set of slots to maximize the storage utilization.
A.7 ABLATION STUDY
Ablation experiments, shown in Figure 10 show that Mayfly with MinGain leads faster convergence, enhanced stability, and superior training performance. We further conducted ablation experiments for Sparse softmax, which demonstrates that the Mayfly with Sparse softmax achieves faster convergence rates and better performance during training.
A.8 THROUGHPUT
We evaluate the throughput of Mayfly comparison with TCM and GSS in Table Mayfly and TCM use a space budget of 64KB for processing Lkml of length 800,000. As an exception, GSS is allowed to allocate extra space if its 64KB budget is exhausted. For the implementation on CPUs, the Mayfly (Python) achieves similar querying throughput to GSS (C++), while TCM (C++) performs the best, due to its simple hash-based structure. However, by employing simple parallel algebraic operations on GPUs, Mayfly achieves a remarkably high throughput, which is about 28 and 18 times higher than the storing and querying throughputs of TCM on CPUs. Mayfly may benefit from the growing trend of integrating GPU-based neural data structures in streaming applications, where inputs are either ephemeral or at high throughputs (Rae et al. 2019).
Table 8: Result Throughput (Mops)
Model
Store
Edge-query
Node-query
Model TCM(CPU) GSS(CPU)
Store
Edge-query
Node-query
Mayfly(GPU)
64.01
54.98
27.09
2.18
2.10
1.40
Mayfly(CPU)
0.09
0.43
0.13
0.55
0.58
0.10
A.9 ROBUST FOR DYNAMIC CONCEPT DRIFT
simple approach for learned data structures leverages neural networks to predict and classify high/low-frequeee items, thereby reducing hash conflicts and prediction errors (Hsu et al. 2019). However, this approach lacks robustness against dynamic drift in data streams. In contrast, our proposed Mayfly does not mechanically memorize the correspondence between specific items and their frequencies (see metamorphosis task generation in section 4.4), providing robustness against concept drift in dynamic stream scenarios.
To demonstrate the efficacy of the Mayfly on the dynamic drift, we implement an enhanced version of the TCM, termed LTCM, per previous work (Hsu al. 2019. The LTCM optimizes by capturing
16

---

Published as a conference paper at ICLR 2024
Ver of stored edges
160
l|Bliz
Addrrece Sparsity
20
1.6
2-Norm
120
12-
11.2
8
0.8
0.4
8M
0.1M
0.5M
00
10K
0.2M 0.3M Train_step
0.5M
Train_step
Train
(a) [|3||| //I /| 222 and |
(bb Average Sparsity of Addresses (c) Average Variance of Edges
Figure 9: Addressing Analysis
Heyfy, Barelie
Mayll, Sastlite
Haylyy
Kisdy Bsseire R Ansanjatstion
Vaniain Allation
Vendain, Aowein
Mincenn Massen
ARB
Spamellar Aobrin
Spareelas Attitio Altition
Spameltas Aitition
Spare Re 10 atter
100K 200K
300K 400K
500K
100K 200K
100K 400K SO0K
100K
200K
10CK
400K
soox
100K 2006 300K 40DK SODc Stop
Train step
Train Train_ttpp
Train_step step
(a) zipf:0.6 40n
(b) zipf:0.6 80n
(c) zipf:0.8 Length:40K
(d) zipf:0.8 Length:80K
Figure 10: Ablation Study
1 % and 5% of high-frequency terms. We select a real substream (B=64KB, Lkml) of length 80K from Deest and progressively shuffle the item-frequency correspondence shown in Figure [T] As the shuffle ratio increases from 0% to 100%, the AAE of the Mayfly fluctuates minimally between 2.40 and 2.62. In contrast, the AAE of LTCM (5%) starts at 8.34 and escalates 10.60. This increase is attributed to the classifier of LTCM incurring more errors due to the dynamic shift, leading to rise in estimation eтrоr and ultimately surpassing the original TCM's average AAE of 9.84.
10
TCM
TCM
4
LTCM 1%
AAE
LTCM 1%
LTCM_5% 5%
LTCM 5%
Imago
Imago
1
0.0
0.2 0.4 0.6 0.8 1.0
0.0 0.2 0.4 0.6 0.8 1.0 Shuffle_ratio ratio
Shuffle ratio
(a) ARE
(b) AAE
Figure 11: LTCM vs. Mayfly
A.10 DEFINITION OF COMPLEX QUERY
We provide formal definitions for path queries and subgraph queries (see Analysis Section).
Path Query. We adopt a prevalent path query, maximum flow path query, as detailed Algorithm 5 The maximum flow in path defined by finite set of directed edges, corresponds to the minimum edge weight in the path. Note that the maximum flow defaults to 0 if any edge is not exist.
Subgraph Query. The Subgraph Query, detailed in Algorithm 6 adheres to the query semantics of TCM. Its objective is to compute the sum of the weights all edges a subgraph Go of the original graph G.
17

---

Published as a conference paper at ICLR 2024
Algorithm 5: Path Query
Data: graph G: query path gi; result MAX_AAA MAX_INT
Result: the maximum flow in v5
for e E & do
if not Qo(o(e), d(e)) then
result=0;
break;
if (e) result then
L result= = Qw)e);
return result;
Algorithm 6: Subgraph Query
Data: graph G; query subgraph Go; result 0
Result: the aggregated weight of query subgraph Gq
for e E Go do
not (o(e)), d(e)) then
result=0;
break;
else
result += Qm
return result;
A.11 LIMITATION AND FUTURE WORK
As the inaugural neural data structure for graph stream summarization, the Mayfly presents substantial opportunities for enhancement. However, our focus is not on its intentional optimization. Insights into the workings of each Mayfly module can be found in the Analysis Section. For example, exploiting prevalent sparsity in addresses could markedly improve storage and query efficiency. Moreover, integrating additional effective reading heads could notably boost query accuracy.
A. SUPPLEMENTARY RESULTS
Due to the space constraint, the real-time performance of imago with a E {0.6, 0.8) under concept shift is shown in Figure T2
10.0
9.5
Maydy
W8.0
W9.0
<1.0
<1.0
0.5
0.5
0.0
0.0
500
1000
1500
2000
500
1000
1500
2000
Adaption_step
Adaption_stee sttoppppppppepee
(a)
zipf:0.6
(b) zipf:0.8
Figure 12: Other Concept Drifts
18


Reviews:
[{"review_id": "Uq1I1JSMFU", "reviewer": "Reviewer_wDZJ", "summary": "The authors propose a Mayfly framework consisting of two stages (larval and metamorphosis) for summarizing graph streams. It is the first neural data structure for graph stream summarization. The Mayfly acquires basic summarization capabilities by learning from synthetic data and can be rapidly adapted to real graph streams. The Mayfly framework is agile and customizable, supporting a broad range of graph queries with lightweight information pathway configurations.", "questions": "Please refer to weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "S1: The authors' integration of Mayfly with machine learning is interesting.\nS2: Well-written.", "weaknesses": "W1: It seems that this paper leans more towards an engineering-oriented research, and its technology appears to be quite fundamental. For instance, it utilizes techniques like meta-learning and follows the paradigm of pre-training and fine-tuning. In my view, there's very little innovation at the model level, which is the most fundamental reason for my minor rejection.\nW2: The authors' integration of graph streams with the Mayfly framework is indeed intriguing. However, from my perspective, it appears to be a fundamental application of pre-training and fine-tuning methods. I believe the authors should provide a clear explanation in the introduction or methodology section regarding why the Mayfly framework is particularly suitable for adapting to graph data streams.\nW3: While the authors propose the Mayfly framework with the aim of enhancing data stream processing efficiency, I did not see a clear experimental demonstration of its efficiency gains. In other words, I would appreciate a more tangible comparison between the Mayfly framework and the comparative algorithms in terms of actual runtime efficiency under the same spatial budget.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FGSYhruypQ", "reviewer": "Reviewer_GvCp", "summary": "This work proposes a neural data structure for graph stream summarization, which has neatly designed modules (representation, addressing and decoding), as well as corresponding operations such as store and multiple types of queries. Experiments on Lkml and Enron datasets demonstrate the superiority of the designed approach compared to the SOTA TCM and GSS baselines.", "questions": "1. In addition to throughput, is there any other metric to evaluate the efficiency of the method (e.g., query time)?\n2. How to balance between the parameter size and model accuracy?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The paper studies an interesting topic on using neural data structure for graph stream summarization, and designed the approach very neatly. In general, the presentation of the methodology is very clear and makes it easier to understand the nontrivial details.\n\n2. The training strategy is inspiring, following the paradigm of \"pre-training and fine-tuning\", and thus has two stages called larval phase and metamorphosis phase.\n\n3. Comprehensive experimental results demonstrate both the effectiveness of the method on different types of queries and throughputs.", "weaknesses": "1. Minor: A table of dataset statistics is suggested to make it more straightforward.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "H47Um3DWvB", "reviewer": "Reviewer_AAng", "summary": "The authors utilize memory-augmented networks for summarizing graph streams into a fixed space. Given the compressed result and a specific edge (or a subset of edges), one can approximate the edge's weight. The neural network is first pre-trained on synthetic graph streams and later fine-tuned using a fraction of the input stream. When compared to sketching-based approaches, the suggested method shows a better approximation accuracy for a given compression size.", "questions": "Q1. Can complex graph algorithms, like Dijkstra's, be executed using the summary? If they can, does it substantially impact the time complexity compared to executing the algorithms on the uncompressed graph?\n\nQ2.  Can you provide a more detailed explanation of how the MiGain term contributes? The present explanation seems too concise.\n\nQ3. What is the time complexity of the addressing, decoding, and store operations?\n\nQ4. The reported ARE and AAE seem quite large. What are their values when we use the mean as the estimate of all edge weights?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "S1. The overall design of the suggested proposed, particularly the use of memory-augmented networks for compressing graph streams, seems reasonable.\n\nS2. The introduced method exhibits significant improvements compared to sketching-based approaches.\n\nS3. The proposed successfully applies to billion-scale graphs, highlighting its practicality for real-world scenarios.", "weaknesses": "W1. The paper lacks a theoretical analysis of complexity and accuracy.\n\nW2. The presentation could be clearer. The insights and novelties of the addressing, decoding, and store operations could be specified.\n\nW3. The proposed method seems to only support weight-related queries, not graph algorithms like Dijkstra’s.\n\nW4. While somewhat expected, the throughput of the proposed method is not as high as that of rule-based baseline methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)