## 3 Proposed Method  
This paper presents a novel method for the unsupervised feature selection problem, which is termed as densest feature graph augmentation with disjoint feature clusters (DFG-A-DFC). Figure 1 illustrates the block diagram of the proposed method. The proposed method works in two phases:  
1. **First Phase:** Finding the maximally non-redundant feature subset. 2. **Second Phase:** Maintaining the cluster structure of the original subspace at the cost of including some redundant features. Algorithm 1 describes the pseudo-code of the proposed unsupervised feature selection method. Given an undirected fully connected graph (G), wherein vertex set (\(V\)) represents the feature set while edge weight between any two vertices depicts the MICI value between the corresponding vertices, the first phase works on identifying the densest subgraph. In Algorithm 1, steps 1 to 6 detail the first phase of the proposed method. The densest subgraph is constructed by heuristically removing the vertices that have a lower edge-weighted degree than the average edge-weighted degree of the current subgraph. As the  
Figure 1: Block diagram of the proposed method. edge weight between two vertices represents the dissimilarity between them, the removal of edges heuristically benefits the identification of features with unique information and maximizes the average edge-weighted degree. These steps are repeated until the density of the current subgraph is lower than the one in the previous iteration. The resultant of the first phase is the feature set (S1), which corresponds to the vertices of the current subgraph. ```
Input: Graph \(G\) = (\(V\),\(E\),\(W\)); Parameters \(0<\beta<=1\), \(k>=0\) Output: Resultant Feature Subset \(S\) (1) Set \(S\) = \(V\) (2) Find \(S^{\prime}\) s.t. \(\forall\;i\in S\), \(\delta(S,\;i)\geq\delta_{mean}(S)\;\Rightarrow i\in S^{\prime}\) (3) if \(d(S^{\prime})\geq d(S)\) then (4) Set \(S=S^{\prime}\) (5) go to 2 (6) end if (7) Find \(N=\frac{|V|}{|S|}\) (8) \(\forall\;i\in V\), Generate nearest neighbor list containing \(N\) nearest neighbors of \(i\) (9) Initialize C as an empty list of clusters (10) Let C\({}^{\prime}\) = C (11) for each \(i\in V\) do (12) Generate \(C_{i}\) s.t. \(a\in C_{i}\Rightarrow(\;a\in C^{\prime}\;)\;\wedge\;(\;\exists\;j\in a\;s.t.\; iRj)\) (13) if \(\;\mid C_{i}\mid\;\
eq 0\) then (14) \(\forall\;a\in C_{i}\;remove\;a\;from\;C^{\prime}\) (15) Add \(\cup_{a\;\in\;C_{i}}a\) to C\({}^{\prime}\) (16) else (17) Add \(\{i\}\) to C\({}^{\prime}\) (18) end if (19) end for (20) if \(\mid C^{\prime}\mid\;<k\) then (21) Set \(C=C^{\prime}\) (22) if \(\mid C\mid\;=0\) then (23) Set \(N=N-1\) (24) go to 10 (25) end if (26) end if (27) if \(C^{\prime}\
eq C\) then (28) Set \(C=C^{\prime}\) (29) go to 10 (30) end if (31) \(for\;each\;\;c\;\in C^{\prime}\) do (32) if \(\
eg\;(\exists\;x\in c\;s.t.\;x\in S)\) then (33) Add \(i\) to \(S\) where \((i\in c)\wedge\
eg\;(\exists\;j\in c\;s.t.\;((j\
eq i)\;\wedge(\sum\limits_{k \in S}W_{k}<\sum\limits_{k\in S}W_{jk})))\) (34) end if (35) end for (36) Output the set \(S\)
```  
**Algorithm 1**Densest Feature Graph Augmentation with Disjoint Feature Clusters  
In the second phase, the disjoint features are added to the feature set (S1) by following steps 7 to 36 of Algorithm 1. For this, the value of shared nearest neighbors (\(N\)) is calculated according to Equation (7). \[N=\frac{|V|}{|S|} \tag{7}\]  
Further, the '\(k^{\prime}\) parameter defines the number of vertices to be clustered while maintaining the minimum number of clusters. The value of '\(k^{\prime}\) is kept 0.5. The subgraph corresponding to a cluster (\(C_{i}\)) is considered 'connected' if the connection between two vertices ('\(i\)' and '\(j\)') are related by Relation \(R\) which is depicted in Equation (8).