Summary

• Page properties (2 modified, 0 added, 0 removed)

Details

Page properties

Title

...	...	@@ -1,1 +1,1 @@
1		-A Machine Learning Approach for Node Size Approximation in Top-down Layout
	1	+Force-directed Layout of Hypergraphs in 3D Space

Content

...	...	@@ -1,45 +1,40 @@
1		-Top-down Layout is a technique to draw large hierarchical diagrams from the root node downwards, scaling children down to fit in the space provided by their parents. This is in contrast to bottom-up layout where children are laid out first and the parents' dimensions are determined accordingly afterwards.
	1	+A relatively simple approach to drawing straightline graphs in a 2D plane is the //force-directed// approach. There are some variations in how the forces are modeled. One such variation is //stress majorization//.
2	2
3		-In top-down layout a strategy needs to be used to set node sizes without knowledge of the hierarchical contents of the node as that has not been processed/laid out at that point. Current strategies are:
	3	+A //hypergraph// is a graph where an edge is not restricted to connect only two vertices but may connect any number of nodes. A //k-uniform hypergraph// is a hypergraph where each edge is incident to k vertices. For this thesis we are only interested in 3-uniform hypergraphs.
4	4
5		-* Using a default base size
6		-* Counting the number of children and taking the square root as a multiplication factor for the default base size
7		-* Computing the layout of only the children (look-ahead layout)
	5	+There are several approaches to draw hypergraphs, but the typical approach is to transform them and ultimately draw them in a 2D plane. With this thesis we want to explore a more unconventional approach.
8	8
9		-The main challenge is to get an approximation that gives a suitable aspect ratio (close to what will actually be required).
	7	+The set of edges of a graph are a binary relation on the set of its vertices. The set of edges of a 3-uniform hypergraph are a ternary relation on the set of its vertices. We call an edge in this hypergraph a //tredge//.
10	10
11		-Graphs are complex feature vectors and the solution space is very large without necessarily one correct and optimal answer. Therefore, a machine learning (ML)-based approach may help find good solutions.
	9	+The goal is to implement a version of force-directed (or similar) layout for this type of hypergraphs within a three-dimensional space. Vertices are mapped to (x,y,z) coordinates and tredges should be mapped to triangular planes connecting the three incident vertices. Tredges should avoid intersecting similar to how edges should avoid crossing. The solution should be implemented in a suitable language such as python and a visualization should be created using the API of the open-source [[Blender>>https://www.blender.org/]] tool. Blender provides us with an easy way to view and navigate 3D environments and therefore lends itself naturally to this task.
12	12
13		-== Example Top-down Layout of an SCChart ==
14		-
15		-[[image:attach:Controller_topdown_v3.png]]
16		-
17	17	= Goals =
18	18
19		-* Use the KiCoDia benchmarking tool to extract feature vectors from existing models
20		-* Train and evaluate an ML model on the extracted data sets
21		-* Integrate the model as a new node size approximator into top-down layout
	13	+* generalization of force-directed/stress majorization layout approach to 3-uniform hypergraphs embedded in 3D space
	14	+* implementation of algorithm (recommended: Python)
	15	+* visualization in a suitable tool (recommended: Blender)
22	22
23	23	= Scope =
24	24
25		-Master's (Bachelor's) Thesis
	19	+Master's Thesis
26	26
27	27	= Related Work/Literature =
28	28
29		-[Under Review] M. Kasperowski and R. von Hanxleden, //Top-down Layout: Effectively Utilizing Zoom for Drawings of Compound Graphs//
	23	+[[Thomas M. J. Fruchterman>>url:https://dblp.org/pid/39/1546.html]], [[Edward M. Reingold>>url:https://dblp.org/pid/r/EMReingold.html]]: Graph Drawing by Force-directed Placement. [[Softw. Pract. Exp. 21(11)>>url:https://dblp.org/db/journals/spe/spe21.html#FruchtermanR91]]: 1129-1164 (1991)
30	30
31		-M. Nielsen, //Neural Networks and Deep Learning//, Determination Press, 2015 ([[http:~~/~~/neuralnetworksanddeeplearning.com/index.html>>url:http://neuralnetworksanddeeplearning.com/index.html||shape="rect"]])
	25	+[[Emden R. Gansner>>url:https://dblp.org/pid/35/6095.html]], [[Yehuda Koren>>url:https://dblp.org/pid/k/YehudaKoren.html]], [[Stephen C. North>>url:https://dblp.org/pid/n/StephenCNorth.html]]: Graph Drawing by Stress Majorization. [[GD 2004>>url:https://dblp.org/db/conf/gd/gd2004.html#GansnerKN04]]: 239-250
32	32
33		-I. Goodfellow and Y. Bengio and A. Courville, //Deep Learning//, MIT Press, 2016 ([[https:~~/~~/www.deeplearningbook.org/>>url:https://www.deeplearningbook.org/||shape="rect"]])
	27	+[[Naheed Anjum Arafat>>url:https://dblp.org/pid/204/2502.html]][[image:https://dblp.org/img/orcid-mark.12x12.png]], [[Stéphane Bressan>>url:https://dblp.org/pid/b/SBressan.html]]: Hypergraph Drawing by Force-Directed Placement. [[DEXA (2) 2017>>url:https://dblp.org/db/conf/dexa/dexa2017-2.html#ArafatB17]]: 387-394
34	34
	29	+
	30	+
35	35	= Involved Languages/Technologies =
36	36
37		-* Java / Xtend, Python
38		-* KiCo
39		-* ML Frameworks (to be chosen)
	33	+* Python
	34	+* Blender
40	40
41	41	= Supervised by =
42	42
43		-Maximilian Kasperowski in cooperation with the [[Intelligent Systems>>url:https://www.ins.informatik.uni-kiel.de/en||shape="rect"]] group.
	38	+Maximilian Kasperowski
44	44
45	45	mka@informatik.uni-kiel.de