# Graphs from Features: Tree-Based Graph Layout for Feature Analysis
## 2 Related Work  
### Automatic Graph-Based Feature Selection Methods  
Some works in the literature use graphs to model and solve the feature selection problem. The approaches vary largely on how the problem is modeled by a graph and on the algorithmic solutions. The references in the sequel provide an overview of such strategies. [PERSON] and [PERSON] [13] construct a graph having one vertex for each labeled instance connected by edges weighted by the heterogeneous value diference metric [14], which combines numeric and categorical attributes. A minimum spanning tree of this graph is used to evaluate local and global uncertainty measures. A greedy forward feature selection is then performed using the value of a homogeneity hypothesis test on the uncertainty measures as a threshold. The authors also report improving the computational performance of their algorithm using a nearest neighbor graph with similar results. [PERSON] et al. [15] use a graph to estimate the Shannon entropy of a set of features more efficiently and less prone to noise in data. [PERSON] et al. [16] then apply this evaluation technique to select features based on mutual information using a greedy forward selection algorithm, which starts with a small set of features and adds one feature at a time. For a partially labeled dataset, [PERSON] et al. [17] propose selecting a subset of features using a supervised algorithm. Then the following procedure is repeated a certain number of times. A complete graph is built having each sample as a vertex and the weight of each edge is evaluated using the subset of features selected so far as a parameterized exponential function. Class labels probabilities are propagated throughout the graph taking edge weights into account in a probabilistic transition model and a fraction of the best classified vertices are labeled. A new supervised feature selection is performed and its average confidence is evaluated. At the end of the process, the subset of features with the largest prediction confidence is selected. [PERSON] et al. [18] proposes using a hybrid graph that includes pairs of classified instances and pairs of features as colored vertices depending on their classes. Edges are added depending on the state of a feature in the incident vertices. A feature selection problem is then defined in terms of a minimal subset of vertices subject to color and degree constraints, and then refined to include edge weights and a limit on the number of features. The authors then solve both integer linear programs in combination using a commercial solver. [PERSON] et al. [19] build a complete graph where vertices represent both discrete features and labels. Edge weights are calculated as the symmetric uncertainty (a normalized form of multiple information). Then the attribute vertices whose distance to any label is smaller than or equal to \(k\) are selected and a ranking of features is produced as well. [PERSON] and [PERSON] [20] propose the construction of a complete undirected graph with a vertex for each feature where edge weight is the mutual information between features. Then they partition the graph into a set of dominating vertices and a set of non-dominating vertices. This procedure is applied recursively to the set of non-dominating vertices while it is not empty. From the sets of dominating vertices, up to \(k\) features are selected based on the multidimensional interaction information. Dominating-set clustering was defined in [21] to capture the notion of a set of vertices connected by edges with large weights among each other and connected by edges with small weights to any other vertices. With that formulation, a dominant-set may be found solving a quadratic program. In a latter work, [PERSON] and [PERSON] [22] model the problem as a hyper-graph having features as vertices and adding hyper-edges for large values of the multidimensional interaction information measure. Then the most informative features subset is found by solving a non-linear optimization problem followed by an iterative adjustment of edge weights.