# Graphs from Features: Tree-Based Graph Layout for Feature Analysis
## 1 Introduction  
Many data analysis tasks are performed on datasets where each data item (also referred to as sample, example or instance) has a set of features (also referred to as variables or attributes) that define it. When the set of features is large, and this is currently the typical case, exploring and analyzing the data is harder: more computing resources will be demanded and inaccurate relations among data will be introduced just by chance, either locally or globally, making it harder to understand. Exploratory tasks that are often performed during data analysis, like data classification, clustering,and the construction of representations to unveil correlations and causal effects among samples and features, are affected [1]. Two main strategies have been proposed for dimensionality reduction of datasets: feature selection and feature transformation [2]. Feature selection techniques discard features in the quest for a small subset of features that preserves relationships among data. Feature transformation (also referred to as feature extraction) techniques build a new, smaller, feature space from the original features. Selecting a subset of features that still preserves the correlations in the original space is known to be a computationally hard (NP-hard) problem under a variety of formulations [3]. This is not a surprise, as the number of subsets of a set of \(d\) features is \(2^{d}\). The problem gets specially daunting with typical \(d\) in the order of hundreds or thousands for multimedia and textual datasets. From a combinatorial perspective, the feature selection problem has been approached with a variety of exact and heuristic techniques, such as branch-and-bound [4], local search [5; 6], evolutionary algorithms [7; 8; 9] and integer programming [6]. In addition to this scenario, automatic feature selection or transformation strategies fail to consider the user expertise [10]. From a data visualization perspective, an attempt to relief the intrinsic hardness of the problem is the inclusion of an specialist in the process through an interactive tool that provides a layout of the data and means to interfere or guide the feature selection, typically in cycles. Graphs are an expressive means to represent a non-euclidean geometry, being often a natural model for a dataset and for the representation of intricate relations among samples, represented as vertices, with weighted edges representing similarity (or dissimilarity, or other type of measure) between samples. Alternatively, features may be represented as vertices connected by weighted edges representing correlation, mutual information or another measure of their mutual importance or similarity for data description. As the underlying representation for a visual map of data, graphs are rapidly overflowed by edges, (\(O(n^{2})\) for \(n\) vertices on a complete graph), and drawing the graph in a visually suitable layout is computationally hard (for instance, recognizing whether a graph may be realized on the plane having at most one crossing per edge is an NP-complete [11] problem). Some open problems in graph aesthetics are related to determining minimum area requirements under assumptions on the maximum number of edge crossings. While exploring graph drawing alternatives and algorithms is possible, resorting to the more sparse representation provided by trees is a computationally light alternative that has various visual favourable characteristics, perhaps the most appealing being putting a backbone of vertices relationship in evidence [12]. In this article, we propose a visual analysis framework for a graph representation of the attributes (or feature vectors) in a dataset, with features represented as vertices and feature similarity as edges. From that graph, that we call _graph from features_, we generate a tree aiming at reflecting the similarity structure among attributes.