More Web Proxy on the site http://driver.im/

research-article

Scalable Hypergraph Visualization

Authors:

Yue ZhangAuthors Info & Claims

IEEE Transactions on Visualization and Computer Graphics, Volume 30, Issue 1

Pages 595 - 605

https://doi.org/10.1109/TVCG.2023.3326599

Published: 01 January 2024 Publication History

Abstract

Hypergraph visualization has many applications in network data analysis. Recently, a polygon-based representation for hypergraphs has been proposed with demonstrated benefits. However, the polygon-based layout often suffers from excessive self-intersections when the input dataset is relatively large. In this paper, we propose a framework in which the hypergraph is iteratively simplified through a set of atomic operations. Then, the layout of the simplest hypergraph is optimized and used as the foundation for a reverse process that brings the simplest hypergraph back to the original one, but with an improved layout. At the core of our approach is the set of atomic simplification operations and an operation priority measure to guide the simplification process. In addition, we introduce necessary definitions and conditions for hypergraph planarity within the polygon representation. We extend our approach to handle simultaneous simplification and layout optimization for both the hypergraph and its dual. We demonstrate the utility of our approach with datasets from a number of real-world applications.

References

[1]

World trade organization regional trade agreements database, May 2022.

[2]

C. J. Alpert, L. W. Hagen, and A. B. Kahng. A hybrid multilevel/genetic approach for circuit partitioning. In Proceedings of APCCAS'96-Asia Pacific Conference on Circuits and Systems, pp. 298–301. IEEE, 1996.

[3]

B. Alsallakh, W. Aigner, S. Miksch, and H. Hauser. Radial sets: Interactive visual analysis of large overlapping sets. IEEE Transactions on Visualization and Computer Graphics, 19 (12): pp. 2496–2505, 2013.

Digital Library

[4]

B. Alsallakh, L. Micallef, W. Aigner, H. Hauser, S. Miksch, and P. Rodgers. The state-of-the-art of set visualization. Comput. Graph. Forum, 35 (1): pp. 234–260, Feb. 2016.

Digital Library

[5]

N. A. Arafat and S. Bressan. Hypergraph drawing by force-directed placement. In Database and Expert Systems Applications, pp. 387–394. Springer International Publishing, Cham, 2017.

[6]

A. A. Benczúr and D. R. Karger. Approximating st minimum cuts in õ (n 2) time. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp. 47–55, 1996.

Digital Library

[7]

C. Berge. Graphs and hypergraphs. Amsterdam: North-Holland mathematical library, v. 6. North-Holland Pub. Co., [2d rev. ed.] translated by Edward Minieka. ed., 1976.

[8]

U. Brandes. A faster algorithm for betweenness centrality. Journal of mathematical sociology, 25 (2): pp. 163–177, 2001.

[9]

G. Bravo-Hermsdorff and L. M. Gunderson. A unifying framework for spectrum-preserving graph sparsification and coarsening. arXiv preprint arXiv:, 2019.

[10]

A. Bretto. “Hypergraph theory”. in An introduction. Mathematical Engineering. Cham: Springer, 2013.

[11]

T. N. Bui and C. Jones. A heuristic for reducing fill-in in sparse matrix factorization. Technical report, 12 1993.

[12]

C. Chekuri and C. Xu. Minimum cuts and sparsification in hypergraphs. SIAM Journal on Computing, 47 (6): pp. 2118–2156, 2018.

Digital Library

[13]

Y. Chen, S. Khanna, and A. Nagda. Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries. In N. Bansal, E. Merelli, and J. Worrell, eds., 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), vol. 198 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 53:1–53:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2021.

[14]

C.-K. Cheng and Y.-C. Wei. An improved two-way partitioning algorithm with stable performance (vlsi). IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 10 (12): pp. 1502–1511, 1991.

Digital Library

[15]

J. Cong and M. Smith. A parallel bottom-up clustering algorithm with applications to circuit partitioning in vlsi design. In 30th ACM/IEEE Design Automation Conference, pp. 755–760. IEEE, 1993.

Digital Library

[16]

K. D. Devine, E. G. Boman, R. T. Heaphy, R. H. Bisseling, and U. V. Catalyurek. Parallel hypergraph partitioning for scientific computing. In Proceedings 20th IEEE International Parallel & Distributed Processing Symposium, p. 10-pp. IEEE, 2006.

[17]

M. Dörk, N. Henry Riche, G. Ramos, and S. Dumais. Pivotpaths: Strolling through faceted information spaces. IEEE Transactions on Visualization and Computer Graphics, 18 (12): pp. 2709–2718, 2012.

Digital Library

[18]

F. Frank, M. Kaufmann, S. Kobourov, T. Mchedlidze, S. Pupyrev, T. Ueckerdt, and A. Wolff. Using the metro-map metaphor for drawing hyper-graphs. In T. Bureš, R. Dondi, J. Gamper, G. Guerrini, T. Jurdziński, C. Pahl, F. Sikora, and P. W. Wong, eds., SOFSEM 2021: Theory and Practice of Computer Science, pp. 361–372. Springer International Publishing, Cham, 2021.

Digital Library

[19]

J. Garbers, H. J. Promel, and A. Steger. Finding clusters in vlsi circuits. In 1990 IEEE International Conference on Computer-Aided Design, pp. 520–521. IEEE Computer Society, 1990.

[20]

Gazepoint. Gp3 eye-tracker. [Online]. Available: https://www.gazept.com, 2021.

[21]

L. Hagen and A. Kahng. Fast spectral methods for ratio cut partitioning and clustering. In 1991 IEEE international conference on computer-aided design digest of technical papers, pp. 10–11. IEEE Computer Society, 1991.

[22]

L. Hagen and A. B. Kahng. A new approach to effective circuit clustering. In ICCAD, vol. 92, pp. 422–427, 1992.

[23]

S. Hauck and G. Borriello. An evaluation of bipartitioning techniques. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 16 (8): pp. 849–866, 1997.

Digital Library

[24]

B. Hendrickson and R. Leland. A multi-level algorithm for partitioning graphs. In SC Conference, p. 28. IEEE Computer Society, Los Alamitos, CA, USA, dec 1995.

[25]

M. Imre, J. Tao, Y. Wang, Z. Zhao, Z. Feng, and C. Wang. Spectrum-preserving sparsification for visualization of big graphs. Computers & Graphics, 87: pp. 89–102, 2020.

[26]

P. Isenberg, F. Heimerl, S. Koch, T. Isenberg, P. Xu, C. Stolper, M. Sedlmair, J. Chen, T. Möller, and J. Stasko. vispubdata.org: A metadata collection about IEEE visualization (VIS) publications. IEEE Transactions on Visualization and Computer Graphics, 23 (9): pp. 2199–2206, Sept. 2017.

Digital Library

[27]

B. Jacobsen, M. Wallinger, S. Kobourov, and M. Nöllenburg. Metrosets: Visualizing sets as metro maps. IEEE Transactions on Visualization and Computer Graphics, 27 (2): pp. 1257–1267, 2021.

[28]

I. Kabiljo, B. Karrer, M. Pundir, S. Pupyrev, A. Shalita, A. Presta, and Y. Akhremtsev. Social hash partitioner: a scalable distributed hyper-graph partitioner. 10 (11): pp. 1418–1429, aug 2017.

Digital Library

[29]

M. Kapralov, R. Krauthgamer, J. Tardos, and Y. Yoshida. Spectral hypergraph sparsifiers of nearly linear size. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 1159–1170. IEEE, 2022.

[30]

G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar. Multilevel hypergraph partitioning: Applications in vlsi domain. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 7 (1): pp. 69–79, 1999.

Digital Library

[31]

G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on scientific Computing, 20 (1): pp. 359–392, 1998.

Digital Library

[32]

B. Kim, B. Lee, and J. Seo. Visualizing set concordance with permutation matrices and fan diagrams. Interacting with Computers, 19 (5–6): pp. 630–643, 2007.

Digital Library

[33]

D. Kogan and R. Krauthgamer. Sketching cuts in graphs and hypergraphs. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS '15, pp. 367–376. Association for Computing Machinery, New York, NY, USA, 2015.

Digital Library

[34]

C. Kuratowski. Sur le problème des courbes gauches en topologie. Fundamenta Mathematicae, 15 (1): pp. 271–283, 1930.

[35]

A. Lex, N. Gehlenborg, H. Strobelt, R. Vuillemot, and H. Pfister. Upset: Visualization of intersecting sets. IEEE Transactions on Visualization and Computer Graphics, 20 (12): pp. 1983–1992, 2014.

[36]

M. Ley. DBLP Computer Science Bibliography, 2005.

[37]

D. C. Liu and J. Nocedal. On the limited memory BFGS method for large scale optimization. Mathematical Programming, 45 (1): pp. 503–528, 1989.

Digital Library

[38]

A. Louis. Hypergraph markov operators, eigenvalues and approximation algorithms. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC '15, pp. 713–722. Association for Computing Machinery, New York, NY, USA, 2015.

Digital Library

[39]

L. Micallef and P. Rodgers. eulerAPE: Drawing area-proportional 3-Venn diagrams using ellipses. PloS One, 9: p. e101717, 07 2014.

[40]

B. Qu, P. Kumar, E. Zhang, P. Jaiswal, L. Cooper, J. Elser, and Y. Zhang. Interactive design and visualization of n-ary relationships. In SIGGRAPH Asia 2017 Symposium on Visualization, p. 15. ACM, 2017.

Digital Library

[41]

B. Qu, E. Zhang, and Y. Zhang. Automatic polygon layout for primal-dual visualization of hypergraphs. IEEE Transactions on Visualization and Computer Graphics, 28 (1): pp. 633–642, 2022.

Digital Library

[42]

N. H. Riche and T. Dwyer. Untangling Euler diagrams. IEEE Transactions on Visualization and Computer Graphics, 16 (6): pp. 1090–1099, 2010.

Digital Library

[43]

P. Rodgers, L. Zhang, and A. Fish. General Euler diagram generation. In Proceedings of the 5th International Conference on Diagrammatic Representation and Inference, Diagrams '08, pp. 13–27. Springer-Verlag, Berlin, Heidelberg, 2008.

Digital Library

[44]

D. Ron, I. Safro, and A. Brandt. Relaxation-based coarsening and multi-scale graph organization. Multiscale Modeling & Simulation, 9 (1): pp. 407–423, 2011.

[45]

R. Sadana, T. Major, A. Dove, and J. Stasko. Onset: A visualization technique for large-scale binary set data. IEEE Transactions on Visualization and Computer Graphics, 20 (12): pp. 1993–2002, 2014.

[46]

R. Santamaría and R. Therón. Visualization of Intersecting Groups Based on Hypergraphs. IEICE Transactions on Information and Systems, 93 (7): pp. 1957–1964, Jan. 2010.

[47]

P. Simonetto, D. Archambault, and C. Scheidegger. A simple approach for boundary improvement of euler diagrams. IEEE Transactions on Visualization and Computer Graphics, 22 (1): pp. 678–687, 2015.

Digital Library

[48]

P. Simonetto, D. Auber, and D. Archambault. “Fully automatic visualisation of overlapping sets”. In Computer Graphics Forum, vol. 28, pp. 967–974. Wiley Online Library, 2009.

Digital Library

[49]

T. Soma and Y. Yoshida. Spectral sparsification of hypergraphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2570–2581. SIAM, 2019.

[50]

D. A. Spielman and S.-H. Teng. Spectral sparsification of graphs. SIAM Journal on Computing, 40 (4): pp. 981–1025, 2011.

Digital Library

[51]

G. Stapleton, J. Flower, P. Rodgers, and J. Howse. Automatically drawing Euler diagrams with circles. J. Vis. Lang. Comput., 23 (3): pp. 163–193, June 2012.

Digital Library

[52]

J. Stasko, C. Gorg, Z. Liu, and K. Singhal. Jigsaw: Supporting investigative analysis through interactive visualization. In 2007 IEEE Symposium on Visual Analytics Science and Technology, pp. 131–138, 2007.

Digital Library

[53]

C. Thomassen. Plane representations of graphs. Progress in graph theory, 1984.

[54]

A. Trifunović and W. J. Knottenbelt. Parallel multilevel algorithms for hypergraph partitioning. Journal of Parallel and Distributed Computing, 68 (5): pp. 563–581, 2008.

Digital Library

[55]

P. Valdivia, P. Buono, C. Plaisant, N. Dufournaud, and J.-D. Fekete. Analyzing dynamic hypergraphs with parallel aggregated ordered hypergraph visualization. IEEE transactions on visualization and computer graphics, 27 (1): pp. 1–13, 2019.

Digital Library

[56]

H.-Y. Wu, B. Niedermann, S. Takahashi, M. J. Roberts, and M. Nöllenburg. A survey on transit map layout - from design, machine, and human perspectives. Computer Graphics Forum, 39 (3): pp. 619–646, 2020.

[57]

A. A. Zykov. Hypergraphs. Russian Mathematical Surveys, 29 (6): p. 89, 1974.

Cited By

Oliver PZhang EZhang Y(2024)Structure-Aware Simplification for Hypergraph VisualizationIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2024.345636731:1(667-676)Online publication date: 10-Sep-2024
https://dl.acm.org/doi/10.1109/TVCG.2024.3456367
Zhou HLai PSun ZChen XChen YWu HWang Y(2024)AdaMotif: Graph Simplification via Adaptive Motif DesignIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2024.345632131:1(688-698)Online publication date: 10-Sep-2024
https://dl.acm.org/doi/10.1109/TVCG.2024.3456321
Yan XRodgers PRottmann PArchambault DHaunert JWang B(2024)EulerMerge: Simplifying Euler Diagrams Through Set MergesDiagrammatic Representation and Inference10.1007/978-3-031-71291-3_16(190-206)Online publication date: 27-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71291-3_16

Index Terms

Scalable Hypergraph Visualization

Index terms have been assigned to the content through auto-classification.

Recommendations

Hypergraph Based Berge Hypergraphs
Abstract
Fix a hypergraph $F$ . A hypergraph $H$ is called a Berge copy of $F$ or Berge- $F$ if we can choose a subset of each hyperedge of $H$ to obtain a copy of $F$ . A hypergraph $H$ is Berge- $F$ -free if it does not contain a subhypergraph which is Berge copy of $F$ . This ... $^{}$
Acyclic Hypergraph Projections

Hypergraphs can be partitioned into two classes: tree (acyclic) hypergraphs and cyclic hypergraphs. This paper analyzes a new class of cyclic hypergraphs called Xrings. HypergraphHis an Xring if the hyperedges ofHcan be circularly ordered so that for ...
Selective hypergraph colourings

We look at colourings of r -uniform hypergraphs, focusing our attention on unique colourability and gaps in the chromatic spectrum. The pattern of an edge E in an r -uniform hypergraph H whose vertices are coloured is the partition of r induced by the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Visualization and Computer Graphics

IEEE Transactions on Visualization and Computer Graphics Volume 30, Issue 1

Jan. 2024

1456 pages

Issue’s Table of Contents

1077-2626 © 2023 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 January 2024

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 29 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Oliver PZhang EZhang Y(2024)Structure-Aware Simplification for Hypergraph VisualizationIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2024.345636731:1(667-676)Online publication date: 10-Sep-2024
https://dl.acm.org/doi/10.1109/TVCG.2024.3456367
Zhou HLai PSun ZChen XChen YWu HWang Y(2024)AdaMotif: Graph Simplification via Adaptive Motif DesignIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2024.345632131:1(688-698)Online publication date: 10-Sep-2024
https://dl.acm.org/doi/10.1109/TVCG.2024.3456321
Yan XRodgers PRottmann PArchambault DHaunert JWang B(2024)EulerMerge: Simplifying Euler Diagrams Through Set MergesDiagrammatic Representation and Inference10.1007/978-3-031-71291-3_16(190-206)Online publication date: 27-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71291-3_16

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents