# SumMER: Structural Summarization for RDF/S KGs
## 4 Constructing Schema Summaries
### Linking Selected Schema Nodes  
Assuming that the previous two steps were successful in selecting the most important nodes, next we focus on linking those nodes with appropriate paths out of the original schema graph to generate a sub-graph of it. The direction of the edges is irrelevant as we seed only to connect the selected schema nodes. Past approaches in the area exploit the maximum-cost-spanning tree, linking the most important nodes using paths from the selected maximum-cost-spanning tree (MST) [18]. The target in those approaches is to that maximize the total weight of the selected sub-graph. However, as the MST identifies the paths that maximize the weight for the whole graph, linking the top-k schema nodes using paths from the MST, introduces a significant number of additional nodes in the result summary highly reducing the value of the generated summary, as the new nodes might not have a high value. In this paper, we model the problem of linking the most important nodes as a variation of the well-known graph Steiner-Tree problem (GSTP) pursuing a different optimization objective. To reduce the number of additional schema nodes introduced to the result summary. **Definition 11**. : _(The Graph Steiner-Tree problem (GSTP)) Given an undirected graph \(G=\) (\(V\), \(E\)), with edge weights and a node set \(S\), called terminals, where \(S\subseteq V\), find a minimum-weight tree \(T=(V_{t},\,E_{t})\in G\) such that \(S\subseteq V_{t}\) and \(E_{t}\subseteq E\)._  
In our case, the graph given as input to the algorithm is the schema graph, ignoring the direction in the edges, as our target is to link the top-k nodes independent of the direction of the edges in between. Our objective now is not to increase the total weight of the summary graph but to introduce as less as possible additional nodes to the summary required for linking the top-k ones. This is since introducing a lot of additional nodes shifts the focus of the summary and decreases the summary's quality. For resolving this problem optimal solutions have been already proposed by [PERSON] [19] and [PERSON] [20] independently. The problem is an NP-hard problem and remains NP-complete if all edge weights are equal. Algorithms, Approximation & Heuristics  
There had been various exact algorithms for the GSTP. [PERSON] [19] proposed the first brute force, exact algorithm for resolving the GSTP problem. The algorithm enumerates all minimum spanning trees of sub-networks of \(G\) included by super-sets of terminals that runs in \(O(2^{V-t}\)\(V^{2}+V^{3})\). The first dynamic programming algorithms were proposed independently by [PERSON] [21] and by [PERSON] [20]. The former runs in \(O(3^{t}\)\(V+2^{t}\)\(V^{2}+V^{3})\) whereas the latter in \(O(3^{t}\)\(V+2^{t}\)\(V^{2}+t^{2}\)\(V)\) and they are based on the optimal decomposition property by creating two node sets, removing one node at each step and solving the GSTP by connecting each set. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Algorithm** & **Training** & **Prediction** \\ \hline Decision Tree & \(O(n^{2}p)\) & \(O(p)\) \\ Random Forest & \(O(n^{2}pn_{trees})\) & \(O(pn_{trees})\) \\ Extremely Random Trees & \(O(np_{trees})\) & \(O(np_{trees})\) \\ Gradient Boosting & \(O(np_{trees})\) & \(O(pn_{trees})\) \\ Linear Regression & \(O(n^{2}p+n^{3})\) & \(O(p)\) \\ Adaptive Boosting & \(O(np_{trees})\) & \(O(pn_{trees})\) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Complexity of algorithms (\(n\) the number of samples, \(p\) the number of features, \(n_{trees}\) the number of trees). [PERSON]'s method uses a recursive optimization approach that pre-computes the possible subtrees. Since all algorithms have an exponential running time, various approximations such as [22; 23; 24] have been proposed in order to find good solutions for large networks. A central theme in these approximations is the use of some principles known from the two classic algorithms for solving the minimum spanning tree problem, Prim's and Kruskal's [24].