Recently, Graph Cities [1, 2] have been proposed as scalable 3d visual representations of graph edge partitions where each subgraph in the partition is a “fixed point of degree peeling”. In this work, we propose “intuitive” primitives to extract language semantics from the topology of these fixed points aided by provided graph vertex labels. The main approach is to view the collection of data labels as a set system derived from the graph topology and to derive “intuitive” language semantics from a specially derived set system intersection meta-graph. Exploration primitives include a glyph grid map of the distribution of all fixed points in the data set and a textual summary tool. We illustrate our approach with a variety of fixed points subgraphs extracted from “large” datasets that include a patent citation network (16.5 million edges) [ 3], a movie keywords co-occurrence network derived from the Internet Movie Database (5 million edges), a paper citation network derived from arXiv Computer Science papers (1.5 million edges), and a Parler dataset [4].
for scalable interactive visual representations an area of pressing importance. Two of the main questions in this type of investigation relate to the Screen and I/O Bottlenecks [5, 6]. The I/O bottleneck refers to the fact that specialized “external memory” algorithms [7] are required to process graphs when their edge set resides on disk but the full adjacency list does not fit in the computer’s RAM. The screen bottleneck emphasizes the need to devise visual representations that are aware of the computer screen size at diferent levels of resolution and with diferent user interactivity requirements. The overall goal is to amplify the user’s understanding of the essential properties of a non-RAM resident graph by ofering exploration and summarization tools whose combination becomes a “graph sense making” machinery.
We invite the reader to consider graphs with several billion edges (i.e., GigaGraphs) residing on files on a comvise a “small” visual representation that can be explored interactively at diferent levels of resolution and that can be used to generate a “summary” of selected graph properties? Ideally, the visual representation should be suitable to be used as a “visual stamp” of the overall network “structure”. Graph Cities constitute an example of nEvelop-O (H. Zhang) Proceedings of the 6th International Workshop on Big Data Visual Exploration and Analytics co-located with EDBT/ICDT 2023 Joint Congraphs, however, such approaches are not yet suitable Copyright © 2023 for this paper by its authors. Use permitted under Creative Commons License have been proposed to learn low-level embeddings of for the extraction of label semantics from billion-edge graphs.
We built on previous work on Graph Cities [
Even though our current results are preliminary they are very encouraging and we will be focusing in the near future on the creation at a scale of the fixed point semantic approach reported here.
summary of the fixed point vertex labels.
The paper layout is as follows: Section 2 presents the details of global and local views of fixed points as directed meta-graphs and introduces a glyph map that provides direct access to any fixed point. Section 3 lays out the construction of a set system of labels derived from the layered topology of the input fixed point, and provides sample results from a citation network [21, 22], the PanThe fundamental graph theoretical building units used in this work are fixed points of minimum degree peeling 2. A glyph map (Figure 2) that is used as a visual [23]. The reason is that the edges of any graph can be index for fixed point selection. partitioned into maximal subgraphs that are Fixed Points. 3. Editing facilities for users to select and annotate To our knowledge, the best algorithm for the iterative subgraph patterns of his/her own interests that edge decomposition of any graph into fixed points has can be incorporated into graph city galleries complexity ( √||||) and this follows from the fact that a graph cannot have more than √|| diferent peel values.
Figure 4 depicts a small fixed point. It consists of a sequence of waves, and each wave consists of an ordered sequence of edge sets called edge fragments adjacent to disjoint sets of vertices called layers.
An alternative view of an overall edge partition of a graph into fixed points is to consider the intersection meta-graph determined by the vertex sets of the fixed points, i.e. two fixed points < , > are connected if their vertex sets intersect and their connecting edge is weighted by the cardinality of their intersection divided by the size of their union. A spanning directed subgraph view of this fixed point intersection meta-graph can be obtained by collapsing each connected fixed point into a meta-node and directing all edges from lower fixed point values to higher fixed point values (Figure 2). This is a Directed Acyclic Meta-Graph (DAMG) view of the fixed point decomposition of the entire dataset.
Fixed Points Glyph Grid Map. To provide easy access to any fixed point subgraph of a graph city, a grid map is provided, where each point is addressable by a bucket size indicator (x-axis) and a fixed point value (y-axis) (see Figure 2).
Each point in this grid has an associated glyph (see ). Those endpoints of edges in Fragment( ) that are not Figure 3) that summarizes the collection of the corre- in are called the Boundary vertexes of Fragment( ). sponding connected fixed points with the same fixed A fixed point as a stack of edge fragments . A fixed point value and similar edge size within a logarithmic point can be viewed as a directed graph by iterative refactor (i.e., the same bucket). A circular glyph represents stricted exploration of its edge fragments as follows (see a fixed point, whose area and color of the ring encode the Figure 4). Take all vertexes of degree as its seed source ifxed point edge size and average density, respectively. set, mark them as visited, and mark all edges “touching” Internally, a circular glyph contains a clockwise sequence this source set as visited. Update the degrees by subtractof spikes that corresponds to the sequence of waves of ing from each vertex the number of newly visited edges the corresponding fixed point. The number of spikes is adjacent to it, i.e. update the leftover out degree. Proceed equal to the number of waves. Each spike corresponds to iteratively by visiting in parallel the neighborhoods of a triangle that encodes the wave seed set and the number those boundary vertexes whose leftover out-degree is of wave edges. The wave density is color encoded. The strictly less than . If there are no boundary vertices adstarting angle from the left to the first spike encodes the jacent to the set of visited vertices with leftover degrees ratio between the fixed point’s average degree and its less than it means that a new seed set of leftover degrees peel value. When a set of fixed points have the same exactly equal to must be used for further exploration. peel value and similar sizes within a logarithmic factor, This is an indication of the beginning of a new subgraph a spiral glyph summarization represents the edge size of the fixed point that is generated by a new seed set of and density of the union by its area and color. The spiral leftover out-degree . (See next subsection). These maxilength encodes the number of fixed points in the collec- mal subgraphs generated by maximal disjoint seed sets of tion, and the start angle from the left to the outer end vertices of minimum degree are what are called Graph represents the ratio between the average degree of the Waves in [20]. In summary, Fixed points of peel value union and the peel value. contain maximal subsets of “seed” vertices of degree
Since a glyph grid map provides a 2-dimension sum- that generate edge disjoint maximal subgraphs called the
mary for a graph city, it can be used as a selector for waves associated with the seed sets. Each of these waves
“interesting” fixed points. (See Figure 3 (middle).) Hover- has a beginning and an ending set of vertices with some
ing on a particular glyph in the grid map displays some collection of paths interconnecting them [
Users can filter “interesting” fixed points by querying seed sets form an ordered partition of the vertex set of for the largest, densest, or most diverse. the wave. We direct edges according to the fixed point seed set ordering. An edge with both endpoints in the 2.2. Fixed Points as Sequence of Waves same seed set is called local, and edges directed from the lower seed set to the higher seed set are called out-going and Fragments edges, otherwise, they are called in-coming edges. The number of outgoing edges incident to a vertex is called its left-over degree. With these preliminaries, we can introduce a Directed Acyclic Meta-Graph (DAMG) view of a ifxed point as follows: The connected components of the subgraphs induced by the seed sets become meta-notes.
Edges running from a connected component in a seed set to a connected component in a diferent seed set are aggregated as a directed meta-edge (, , |(, )|) , where |(, )| encodes the number of directed edges running from to .
graph, its edge fragment Fragment( ) consists of all those edges with at least one endpoint in (i.e. edges touching
Figure 5 illustrates the interface layout. We refer to the middle area of the screen as the canvas. On the top of the canvas, there is a grid map from which users can display a maximum spanning tree of the label set sysselect a fixed point (in red). To the left, a textual tree of tem intersection meta-graph. When a user hovers over a hi-frequency labels is derived from a binary tree traver- link, its corresponding labels are displayed in an infobox. sal as explained below. In the canvas of the screen, we On the right-hand side, a label frequency bar chart is displayed and interactively updated according to users’ desired specifications.
The complexity of generating summaries is (| | 2), We are currently designing navigation and summarizawhere | | is the number of vertices in the fixed point. tion tools so that a user can annotate those subgraph Please notice that non-quadratic implementations are patterns that he/she finds interesting. Currently, a user possible by using Locally Sensitive Hashing [24]. can annotate subgraph patterns indicating his findings
Assuming that the vertices of a fixed point are labeled and adding the corresponding subgraph patterns to a patby sets of words, we describe next how we rely on the tern gallery accessible from the top of the user interface. layered topological view of a fixed point to generate a A fisheye view on the textural tree set system of labels whose intersection graph is used to generate a hierarchical summary of the overall fixed 4.1. Open Problems point vertex labels.
Generating a set system of labels from the 1. What is the I/O complexity of computing the edge vertex labels. Denote by (, ℎ) a vertex labeled decomposition of a fully external memory graph? ifxed point with peel value consisting of ℎ frag- Namely, neither the vertices nor the edges fit in ments with a corresponding ordered sequence of seed RAM. sets 0, 1, …, ℎ−1 according to their fragment indices 2. Is there an eficient method to compute the fixed 0, 1, …, ℎ−1. We output a hierarchical sum- point edge decomposition in a streaming fashion? mary of the overall fixed point set of labels by building 3. What are examples of graph computations whose a bottom-up aggregation of the vertex labels in the non- solutions can be obtained as compositions of their decreasing order of fragment indices. Initially, we com- solutions on the graph fix points? pute the connected components of the subgraph induced 4. The decomposition of the edges of a graph into by the seed set 0 and assign to each such component ifxed points defines intrinsically an intersection the union of the sets of labels of its vertices. We derive graph of the collection of sets of vertices appeara Label Set System from the fixed point layered view ing on each fixed point. What are the properties decomposition as follows: Bottom-up, for each vertex of the graphs that are the intersection graphs of ∈ , = 0, 1, ..., ℎ − 1 , update the label set of as ifxed point edge graph decompositions? the union of all its incoming neighbors’ label sets. For each pair of vertices (, ) from diferent fragments, if there exists a directed upward path from to , then 5. Conclusions connect (, ) with a semantic edge weighted as the cardinality of the labels’ set intersection between and . Devising visual representations of very large graphs is a Call this graph IntersectionLabelSetSystem( (, ℎ) ). From tantalizing area of research. Coming up with tools that this intersection label set system, we extract a summa- “explain” the semantics encoded by graph data labels at rization based on maximum spanning trees and a binary diferent levels of granularity is in our view a completree traversal. Visually, we build a color map according mentary endeavor that deserves more attention from the to the distribution of weights in the maximum spanning community. It opens avenues of interdisciplinary work tree of the IntersectionLabelSetSystem( (, ℎ) ). A textual involving at least natural language processing (textual summary is extracted by a binary tree traversal of the and semantic similarity [25]), computer human interacmaximum spanning tree according to the non-increasing tion, and machine learning. We hope this modest contriorder of weights, and we select from each tree edge being bution entices other researchers to join us in this quest. visited a label that has not been seen during the traversal.
We illustrate the hierarchical labeling results obtained for ifxed points selected from a patent citation network (Figure 5 (top)), a movies-to-movies-and-keywords dataset (Figure 5 (bottom)), a paper citation network (Figure 6 (top)), and the Parler dataset (Figure 6 (bottom)). The displayed labels are those that have a “substantial” number of co-occurrence in the set system of label sets.
1563816, IIS-1563971, and mgvis.com. Thanks to the DIMACS staf for their support, and to Prof. Tim Tangherlini and Dr. Peter Broadwell for providing a curated version of the Parler dataset. buildings, waves, and fragments, IEEE Computer tributed pathfinder network scaling, in: 2017 IEEE Graphics and Applications 42 (2022) 53–64. 7th Symp. on Large Data Anal. and Vis., 2017, pp. [3] J. Leskovec, A. Krevl, {SNAP Datasets}: {Stanford} 74–83.
large network dataset collection, 2014. [18] W. L. Hamilton, R. Ying, J. Leskovec, Representation [4] M. M. Aliapoulios, E. Bevensee, J. Blackburn, learning on graphs: Methods and applications, IEEE B. Bradlyn, E. D. Cristofaro, G. Stringhini, S. Zan- Data Engineering Bulletin (2017). nettou, A large open dataset from the parler social [19] R. Yang, J. Shi, X. Xiao, Y. Yang, S. S. Bhowmick, Honetwork, in: International Conference on Web and mogeneous network embedding for massive graphs Social Media, 2021. via reweighted personalized pagerank, Proceedings [5] J. Abello, Hierarchical graph maps, Computers & of the VLDB Endowment 13 (2019) 670 – 683.
Graphics 28 (2004) 345–359. [20] J. Abello, D. Nakhimovich, Graph waves, in: The [6] J. Abello, A. L. Buchsbaum, J. R. Westbrook, A 3rd International Workshop on Big Data Visual Exfunctional approach to external graph algorithms, ploration and Analytics with EDBT/ICDT, 2020. in: European Symp. on Alg., Springer, 1998, pp. [21] K. Wang, Z. Shen, C. Huang, C.-H. Wu, Y. Dong, 332–343. A. Kanakia, Microsoft academic graph: When ex[7] A. Aggarwal, S. Vitter, Jefrey, The input/output perts are not enough, Quantitative Science Studies complexity of sorting and related problems, Com- 1 (2020) 396–413.
munications of the ACM 31 (1988) 1116–1127. [22] T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, [8] Z. Lin, N. Cao, H. Tong, F. Wang, U. Kang, Inter- J. Dean, Distributed representations of words and active multi-resolution exploration of million node phrases and their compositionality, Advances in graphs, in: IEEE Conference on Visual Analytics neural information processing systems 26 (2013).
Science and Technology, Poster, 2013. [23] J. Abello, F. Queyroi, Fixed points of graph peeling, [9] P. Mi, M. Sun, M. Masiane, Y. Cao, C. North, Interac- in: Proc. of the 2013 IEEE/ACM Int. Conf. on Adv. tive graph layout of a million nodes, in: Informatics, in Soc. Net. Anal. and Mining, 2013, pp. 256–263. volume 3, Multidisciplinary Digital Publishing In- [24] A. Rajaraman, J. D. Ullman, Mining of massive stitute, 2016, p. 23. datasets, 2011. [10] N. Bikakis, J. Liagouris, M. Krommyda, G. Papaste- [25] D. Chandrasekaran, V. Mago, Evolution of semanfanatos, T. K. Sellis, graphvizdb: A scalable platform tic similarity—a survey, ACM Computing Surveys for interactive large graph visualization, 2016 IEEE (CSUR) 54 (2021) 1–37. 32nd International Conference on Data Engineering (ICDE) (2016) 1342–1345. [11] V. Yoghourdjian, T. Dwyer, K. Klein, K. Marriott,
M. Wybrow, Graph thumbnails: Identifying and comparing multiple graphs at a glance, IEEE Transactions on Visualization and Computer Graphics 24 (2018) 3081–3095. [12] K. Van Koevering, A. Benson, J. Kleinberg, Random graphs with prescribed k-core sequences: A new null model for network analysis, in: Proceedings of the Web Conference 2021, 2021, pp. 367–378. [13] R. Laishram, A. Erdem Sar, T. Eliassi-Rad, A. Pinar,
S. Soundarajan, Residual core maximization: An eficient algorithm for maximizing the size of the k-core, in: Proc. of Int. Conf. on Data Mining, SIAM, 2020, pp. 325–333. [14] N. Wang, D. Yu, H. Jin, C. Qian, X. Xie, Q.-S. Hua,
Parallel algorithm for core maintenance in dynamic graphs, in: Prof. of ICDCS, 2017, pp. 2366–2371. [15] V. Batagelj, M. Zaveršnik, Fast algorithms for determining core groups in social networks, Adv. in
Data Anal. and Class. 5 (2011) 129–145. [16] H. Kabir, K. Madduri, Shared-memory graph truss decomposition, in: 2017 IEEE 24th Int. Conf. on
High Perf. Comput. (HiPC), IEEE, 2017, pp. 13–22. [17] A. Arleo, O.-H. Kwon, K.-L. Ma, Graphray: Dis