Graph layout customization based on user-specified examples

doi:10.11996/JG.j.2095-302X.2025020402

Abstract

Abstract:

Traditional automatic graph layout algorithms, while ensuring the overall aesthetic properties of graph lay-outs, are unable to generate customized graph layouts. In different practical application scenarios, users often need to adjust the automatically generated graph layouts to meet specific requirements. Existing graph layout adjustments mainly fall into two categories: manual node-level adjustments and constraint-based graph layouts. The former is extremely time-consuming and monotonous, while the latter often lacks flexibility. A customized graph layout adjustment method based on user examples was proposed. This method primarily utilized graph blending theory to integrate the attributes and characteristics of example graphs into the source graphs, thereby achieving flexible and efficient customized graph layout adjustments. Initially, the examples were preprocessed. Two mapping examples and six mapping modes were then designed to generate node-level mapping matrices between the examples and the source graphs. The mapping matrices were employed to align the example graph with the source graph, and the graphs were blended at a certain ratio to obtain the customized graph layout adjustments. A web-based interactive system was designed and developed to implement this method, supporting example Sketch drawing, example importing and selection, source graph importing and selection, mapping mode selection, graph blending ratio control, and node-level fine-tuning. Case studies and evaluation experiments were conducted to validate the feasibility and effectiveness of the proposed method.

Key words: graph layout, node-link diagram, user interactions, graph visualization

CLC Number:

CHEN Junxu, WU Ziliang, ZHU Minfeng, CHEN Wei. Graph layout customization based on user-specified examples[J]. Journal of Graphics, 2025, 46(2): 402-414.

Figures/Tables 10

Fig. 1 The process of graph layout customization based on user-specified examples

Fig. 2 System interface ((a) Preview view; (b) Candidate view; (c) Exploration view; (d) Example view-Network example; (e) Toolbar-Network tools)

Fig. 3 System interface ((a) Preview view; (b) Candidate view; (c) Exploration view; (d) Example view-Sketch example: interactive drawing example; (e) Toolbar-Sketch tools)

Table 1 Case 1-2, Sketch example & two types of mapping

映射	样例	源图 (混合前)	源图 (混合后)
线性映射
指定映射

Table 2 Case 3-7, Network example & five types of mapping

映射	样例	源图 (混合前)	源图 (混合后)
指定映射
中介中心性映射
接近中心性映射
聚类系数映射
度中心性映射

Fig. 4 Route views Networks Case ((a) Source graph before adjustment; (b) Source graph after adjustment; (c) Selected structure in the source graph for adjustment; (d) User-customized Sketch example used to adjust the source graph structure)

Fig. 5 Facebook100 Case ((a) Source graph before adjustment; (b) Network example; (c) Source graph after adjustment with 90% blend ratio)

Table 3 The time complexity of mapping matrix construction in the six mapping modes(n=max(n1,n2), m=max(m1,m2))

映射	稀疏图	稠密图
线性映射	O(n)	O(n)
指定映射	O(n)	O(n)
度中心性映射	O(nlogn+m)	O(nlogn+m)
聚类系数映射	O(nlogn+m)	O(n³)
中介中心性映射	O(n²)	O(n³)
接近中心性映射	O(n²)	O(n³)

Fig. 6 Comparison of the timeliness of graph blending under six mapping modes and two classic force-directed layout algorithms (CPU: 15-core Xeon(R) Gold 5218)

Fig. 7 Timeliness analysis of linear mapping and specific mapping when there is a significant difference in the number of nodes between the sample (10 nodes) and the source graph. (CPU: 15-core Xeon(R) Gold 5218)

References 32

[1]	XUE M L, WANG Z, ZHONG F H, et al. Taurus: towards a unified force representation and universal solver for graph layout[J]. IEEE Transactions on Visualization and Computer Graphics, 2023, 29(1): 886-895.
[2]	BALCI H, DOGRUSOZ U. fCoSE: a fast compound graph layout algorithm with constraint support[J]. IEEE Transactions on Visualization and Computer Graphics, 2022, 28(12): 4582-4593.
[3]	张野, 王松, 吴亚东. FMR: 基于FR的快速多层次算法[J]. 图学学报, 2019, 40(1): 78-86. DOI
	ZHANG Y, WANG S, WU Y D. FMR: a fast multilevel algorithm based on FR[J]. Journal of Graphics, 2019, 40(1): 78-86 (in Chinese). DOI
[4]	汤颖, 汪斌, 范菁. 节点属性嵌入的改进图布局算法[J]. 计算机辅助设计与图形学学报, 2016, 28(2): 228-237.
	TANG Y, WANG B, FAN J. An improved graph layout algorithm of embedded node attributes[J]. Journal of Computer-Aided Design & Computer Graphics, 2016, 28(2): 228-237 (in Chinese).
[5]	王智, 薛明亮, 王一凡, 等. 基于无冲突并行随机梯度下降的图布局求解方法[J/OL]. (2024-08-21)[2024-10-01]. http://kns.cnki.net/kcms/detail/11.2925.TP.20240820.1554.006.html.
	WANG Z, XUE M L, WANG Y F, et al. Graph drawing by conflict-free parallel stochastic gradient descent[J/OL]. (2024-08-21)[2024-10-01]. http://kns.cnki.net/kcms/detail/11.2925.TP.20240820.1554.006.html (in Chinese).
[6]	EADES P. A heuristic for graph drawing[J]. Congressus Numerantium, 1984, 42(11): 149-160.
[7]	FRUCHTERMAN T M J, REINGOLD E M. Graph drawing by force‐directed placement[J]. Software: Practice and Experience, 1991, 21(11): 1129-1164.
[8]	HU Y. Efficient, high-quality force-directed graph drawing[J]. Mathematica Journal, 2006, 10(1): 37-71.
[9]	ZHONG F H, XUE M L, ZHANG J, et al. Force-directed graph layouts revisited: a new force based on the t-distribution[J]. IEEE Transactions on Visualization and Computer Graphics, 2024, 30(7): 3650-3663.
[10]	KAMADA T, KAWAI S. An algorithm for drawing general undirected graphs[J]. Information Processing Letters, 1989, 31(1): 7-15.
[11]	DAVIDSON R, HAREL D. Drawing graphs nicely using simulated annealing[J]. ACM Transactions on Graphics, 1996, 15(4): 301-331.
[12]	TORGERSON W S. Multidimensional scaling: I. Theory and method[J]. Psychometrika, 1952, 17(4): 401-419.
[13]	VAN DER MAATEN L,. HINTON G. Visualizing data using t-SNE[J]. Journal of Machine Learning Research, 2008, 9(86): 2579-2605.
[14]	MCINNES L, HEALY J, MELVILLE J. UMAP: uniform manifold approximation and projection for dimension reduction[EB/OL]. [2024-06-01]. https://arxiv.org/abs/1802.03426.
[15]	MI P, SUN M Y, MASIANE M, et al. Interactive graph layout of a million nodes[J]. Informatics, 2016, 3(4): 23.
[16]	JUSUFI I, KERREN A, ZIMMER B. Multivariate Network exploration with JauntyNets[C]// The 17th International Conference on Information Visualisation. New York: IEEE Press, 2013: 19-27.
[17]	HOSOBE H. A high-dimensional approach to interactive graph visualization[C]// 2004 ACM Symposium on Applied Computing. New York: ACM, 2004: 1253-1257.
[18]	PETZOLD J, DOMRÖS S, SCHÖNBERNER C, et al. An interactive graph layout constraint framework[EB/OL]. [2024-06-22]. https://www.scitepress.org/Link.aspx?doi=10.5220/0011803000003417.
[19]	GUCHEV V, GENA C. Sketch-based interactions for untangling of force-directed graphs[C]// 2017 21st International Conference Information Visualisation. New York: IEEE Press, 2017: 288-291.
[20]	HENRY N, FEKETE J D, MCGUFFIN M J. NodeTrix: a hybrid visualization of social Networks[J]. IEEE Transactions on Visualization and Computer Graphics, 2007, 13(6): 1302-1309. PMID
[21]	RYALL K, MARKS J, SHIEBER S. An interactive constraint-based system for drawing graphs[C]// The 10th Annual ACM Symposium on User Interface Software and Technology. New York: ACM, 1997: 97-104.
[22]	SCHREIBER F, DWYER T, MARRIOTT K, et al. A generic algorithm for layout of biological Networks[J]. BMC Bioinformatics, 2009, 10: 375. DOI PMID
[23]	HOFFSWELL J, BORNING A, HEER J. SetCoLa: high-level constraints for graph layout[J]. Computer Graphics Forum, 2018, 37(3): 537-548.
[24]	MASUI T. Graphic object layout with interactive genetic algorithms[C]// The IEEE Workshop on Visual Languages. New York: IEEE Press, 1992: 74-80.
[25]	DWYER T, MARRIOTT K, WYBROW M. Dunnart: a constraint-based Network diagram authoring tool[C]// The 16th International Symposium on Graph Drawing. Cham: Springer, 2009: 420-431.
[26]	BURCH M, TEN BRINKE K B, CASTELLA A, et al. Guiding graph exploration by combining layouts and reorderings[C]// The 13th International Symposium on Visual Information Communication and Interaction. New York: ACM, 2020: 1-5.
[27]	KWON O H, MA K L. A deep generative model for graph layout[J]. IEEE Transactions on Visualization and Computer Graphics, 2020, 26(1): 665-675.
[28]	GIOVANNANGELI L, LALANNE F, AUBER D, et al. Toward efficient deep learning for graph drawing (DL4GD)[J]. IEEE Transactions on Visualization and Computer Graphics, 2024, 30(2): 1516-1532.
[29]	LING H Y, JIANG Z M, LIU M, et al. Graph mixup with soft alignments[EB/OL]. [2024-06-22]. https://dl.acm.org/doi/10.5555/3618408.3619287.
[30]	BLONDEL V D, GUILLAUME J L, LAMBIOTTE R, et al. Fast unfolding of communities in large Networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2008, 2008(10): P10008.
[31]	MO Y J, PENG L, XU J, et al. Simple unsupervised graph representation learning[C]// The 36th AAAI Conference on Artificial Intelligence. Palo Alto: AAAI Press, 2022: 7797-7805.
[32]	ZHOU Z G, SHI C, SHEN X L, et al. Context-aware sampling of large Networks via graph representation learning[J]. IEEE Transactions on Visualization and Computer Graphics, 2021, 27(2): 1709-1719.

映射	样例	源图 (混合前)	源图 (混合后)
指定映射
中介中心性映射
接近中心性映射
聚类系数映射
度中心性映射

映射	样例	源图 (混合前)	源图 (混合后)
指定映射
中介中心性映射
接近中心性映射
聚类系数映射
度中心性映射