11institutetext: Autonomous Ground Vehicle Research Group
Indian Institute of Technology Kharagpur
Kharagpur, WB 721302, India

# Entity Augmentation for Efficient Classification of Vertically Partitioned
Data with Limited Overlap

Avi Amalanshu, Equal contribution.Corresponding author. Email:
<EMAIL_ADDRESS>Viswesh Nagaswamy* G.V.S.S. Prudhvi* Yash
Sirvi* Debashish Chakravarty

###### Abstract

Vertical Federated Learning (VFL) is a machine learning paradigm for learning
from vertically partitioned data (i.e. features for each input are distributed
across multiple “guest" clients and an aggregating “host" server owns labels)
without communicating raw data. Traditionally, VFL involves an “entity
resolution" phase where the host identifies and serializes the unique entities
known to all guests. This is followed by private set intersection to find
common entities, and an “entity alignment" step to ensure all guests are
always processing the same entity’s data. However, using only data of entities
from the intersection means guests discard potentially useful data. Besides,
the effect on privacy is dubious and these operations are computationally
expensive. We propose a novel approach that eliminates the need for set
intersection and entity alignment in categorical tasks. Our Entity
Augmentation technique generates meaningful labels for activations sent to the
host, regardless of their originating entity, enabling efficient VFL without
explicit entity alignment. With limited overlap between training data, this
approach performs substantially better (e.g. with 5% overlap, 48.1% vs 69.48%
test accuracy on CIFAR-10). In fact, thanks to the regularizing effect, our
model performs marginally better even with 100% overlap.

###### Keywords:

Federated Learning Vertical Federated Learning Sample Efficiency.

##  1 Introduction

Federated Learning (FL) [13] is a recent distributed machine learning
strategy. FL aims to achieve communication efficiency and data privacy by
never communicating the raw data. In FL, data-owning participants (“guests")
train models on their local data, coordinated and aggregated by a label-owning
“host". FL typically implies a “horizontal" distribution, where a participant
holds its own set of samples within a global dataset. Vertical Federated
Learning (VFL) is a variant where parties holding different _features_ of the
same samples collaborate without pooling data to learn joint representations.
This is essential for sensitive cross-institution collaborations, such as in
healthcare, emphasizing the importance of aligning records to the same
entities for cohesive, privacy-preserving model training.

VFL effectively splits the parameters of a global model across the network.
The host has the deeper layers and makes a prediction at each
training/inference iteration. For the prediction to be meaningful, all guests
must have passed their features of the same entity. But, this means they must
discard data on entities not known to all participants– potentially valuable
for training local models. In systems with a small intersection, there may be
insufficient samples to train a VFL model effectively, hindering VFL’s
scalability.

For example, cameras and traffic sensors at an intersection may struggle to
detect crashes if the number of frames where the crash is visible to all
cameras is small. The entity alignment process introduces significant
computational overhead, hampering real-world VFL deployment at scale,
affecting overall efficiency. Other challenges include data skew, where data
distribution across entities varies drastically, and privacy risks during
alignment despite VFL’s principle of avoiding direct data sharing. This raises
the question: are PSI and entity alignment truly necessary during training?

Figure 1: Example forward pass with entity augmentation. Both clients forward
activations from arbitrary inputs to the host, which is aware of the identity
of said inputs. Half the features in the host input correspond to the number 1
and the other half correspond to 0. The interpolated label is their weighted
average.

We introduce _Entity Augmentation_ , a strategy for VFL that eliminates the
need for PSI and entity alignment. Instead of agreeing on a single entity (or
batch), the host computes a weighted average of labels for all entities
processed by any guest. The weights are proportional to the total dimension of
the input vector corresponding to each entity’s features. Hosts may calculate
meaningful losses for any activations received, as long as each corresponds to
labelled entities.

In this paper, we:

  * •

Propose Entity Augmentation, a novel strategy that interpolates labels for all
entities sent by all guests, weighted by their contribution to the host input,
synthesizing semantically coherent labels for guest activations.

  * •

Demonstrate that VFL with Entity Augmentation achieves performance on par
(better on some datasets) with VFL with entity alignment.

These empirical results indicate that Entity Augmentation is a viable
alternative to traditional FL pipelines, offering substantial improvements in
data utilization, computational efficiency, and ease of deployment.

##  2 Background

###  2.1 VFL Participants

#### Guests.

Consider a consortium $\mathcal{G}$, comprising participants each with a
distinct feature set. For a guest $i\in\mathcal{G}$, the dataset is
$\mathcal{D}_{i}=\\{\mathbf{x}_{j}\in\mathbb{R}^{|F_{i}|}:j\in\\{1,2,...,|\mathcal{S}_{i}|\\}\\}$,
where:

  * •

$\mathcal{S}_{i}$ is the set of unique entities recorded in $\mathcal{D}_{i}$.

  * •

$F_{i}$ captures the attributes of these entities observed by guest $i$.

  * •

Entities are considered samples from a distribution $X$.

The guest model
$m_{i}(\cdot;\theta_{i}):\mathbb{R}^{|F_{i}|}\rightarrow\mathbb{R}^{\text{out}_{i}}$
is defined by parameters $\theta_{i}$.

These models aim to encode the features $F_{i}$ of entities
$\mathbf{x}\in\bigcap_{i=1}^{|\mathcal{G}|}\mathcal{S}_{i}$ for the host $h$
to utilize in predictions, without sharing their model parameters or direct
data features, including labels.

#### Host.

The host $h$ coordinates the training process, holding the label set
$\mathcal{L}=\\{\mathbf{y}_{j}\in\mathbb{R}^{\text{out}}:j\in\\{1,2,...,|\mathcal{S}_{h}|\\}\\}$,
where $\mathcal{S}_{h}$ is the set of unique entities with labels. A crucial
intersection $|\mathcal{S}_{\mathcal{G}}\cap\mathcal{S}_{h}|>0$ ensures shared
entities for training.

The host model
$m_{h}(\cdot;\theta_{h}):\mathbb{R}^{\text{out}_{1}}\times\mathbb{R}^{\text{out}_{2}}\times...\times\mathbb{R}^{\text{out}_{|\mathcal{G}|}}\rightarrow\mathbb{R}^{\text{out}}$
is parameterized by $\theta_{h}$, aiming to minimize expected loss for optimal
parameters
$\theta=(\theta_{1},\theta_{2},...,\theta_{|\mathcal{G}|},\theta_{h})$.

###  2.2 Entity Alignment

In VFL, coherence during training is ensured through data synchronization,
formalized as
$\mathcal{S}_{\mathcal{G}}=\bigcap_{i=1}^{|\mathcal{G}|}\mathcal{S}_{i}$. This
uses a private set intersection (PSI, [14, 12]) multiparty computation,
preserving privacy while identifying intersecting entities across
$\mathcal{G}$.

Following PSI, the host $h$ processes $\mathcal{S}_{\mathcal{G}}$, ensuring
uniform model training across the federated network. This step is vital for
coherent aggregation of model updates, reflecting the collective knowledge of
$\mathcal{G}$.

Without proper alignment, i.e., if $\mathcal{S}_{\mathcal{G}}$ is not
established, issues like data inconsistency
($\mathcal{S}_{i}\not\subseteq\mathcal{S}_{\mathcal{G}}$ for any $i$) arise,
leading to degraded model performance from training on non-corresponding
entities. Additionally, without alignment, the federated model faces privacy
vulnerabilities and inefficiencies in learning. Thus, Entity Alignment is
crucial in vertical federated learning.

##  3 Related Work

###  3.1 Entity Resolution in Federated Learning

In the absence of unique IDs, the task of resolving common entities between
datasets based on their features is called Entity Resolution. In 2017, Hardy
et al. [5] introduced one of the first privacy-preserving strategies for
learning from vertically partitioned data. The work proposes a pipeline of
entity resolution, distributed logistic regression, and Paillier encryption to
maintain privacy without noise addition. The authors demonstrate this works
under certain entity resolution error assumptions without impacting model
performance. This suggests certain errors do not alter optimal classifier
performance.

Nock et al. [15] investigate the the empirical impact of entity resolution
errors on FL. The authors provide bounds on deviations in classifier
performance due to these errors, and demonstrate the benefits of using label
information with entity resolution algorithms.

###  3.2 Data Augmentation for Classification Generalization

CutMix [21] is a data augmentation technique used in image classification to
enhance deep learning model training by combining parts of different images
and their corresponding labels. Unlike traditional methods that process each
image individually, CutMix creates new training examples by patching segments
from multiple images together.

Given two images $A$ and $B$, and their corresponding one-hot encoded labels
$\mathbf{y}_{A}$ and $\mathbf{y}_{B}$, the CutMix process involves:

  1. 1.

Randomly selecting a region $R$ within image $A$.

  2. 2.

Replacing region $R$ in image $A$ with the corresponding region from image $B$
to generate a new training image $A^{\prime}$.

  3. 3.

Combining the labels proportionally to the number of pixels of each class
present in the new image, resulting in a mixed label
$\mathbf{y}^{\prime}=\lambda\mathbf{y}_{A}+(1-\lambda)\mathbf{y}_{B}$, where
$\lambda$ is the ratio of the remaining area of image $A$ to the area of the
original image.

Mathematically, for a region $R$ with bounding box coordinates
$(r_{x},r_{y},r_{w},r_{h})$, the new training image $A^{\prime}$ is
represented as:

$A^{\prime}=\begin{cases}B_{r_{x}:r_{x}+r_{w},r_{y}:r_{y}+r_{h}}&\text{for
}(i,j)\in R\\\ A_{i,j}&\text{otherwise}\end{cases}$ (1)

Here, $(i,j)$ is the pixel location in the images. The label mixing
coefficient $\lambda$ is typically sampled from a Beta distribution, which
controls the strength of the mixing.

CutMix improves model robustness and generalization by forcing the network to
learn regionally informative features, rather than relying on specific
patterns in the training set. This generates diverse examples within each
mini-batch, helping to prevent overfitting.

###  3.3 Sample Efficient Vertical Federated Learning

Work on sample efficiency is scarce, despite its absence greatly limiting the
applicability of VFL to carefully designed systems with significant overlap in
sample spaces.

Sun et al. propose a method [17] to solve this problem. Following a few epochs
of VFL training on aligned data, guests cluster their remaining datasets based
on gradients received during the aligned training. The authors experimentally
show that this approach is performant. However, as suggested by Amalanshu et
al. [1] this is a form of privacy-breaching label inference attack.

In that paper, the authors present an unsupervised method of training guest
models independently from host models, hence allowing them to exploit data
outside the intersection without breaching privacy. However, task-relevant
transfer learning still uses aligned datasets.

##  4 Proposed Method

VFL typically assumes that the input datasets for each model are “aligned,"
meaning that records are consistent across entities indexed in
$\left(\bigcap_{i=1}^{|\mathcal{G}|}\mathcal{S}_{i}\right)\cap\mathcal{S}_{h}$.
We propose a novel training approach for categorical tasks that allows each
dataset to be sized
$\min_{i\in\\{1,\ldots,|\mathcal{G}|\\}}|\mathcal{S}_{i}\cap\mathcal{S}_{h}|$,
or
$\max_{i\in\\{1,\ldots,|\mathcal{G}|\\}}|\mathcal{S}_{i}\cap\mathcal{S}_{h}|$
if guests may reuse data.

Extending the idea of the CutMix regularization, we propose entity
augmentation for training the owner model. We construct artificial entity
samples by combining features from various entities and averaging their
labels. This approach enables training on a minimal subset of samples.

There are various ways such a scheme might be implemented. For instance,
entity augmentation may be precomputed before training begins– the host may
inform the guests which order to process their entities, and memoize the
corresponding augmented labels. Alternatively, the augmented labels could be
computed at training time as long as the host is aware of the identities of
all the entities whose encoded features it has just received. Algorithm 1
outlines one way of achieving the latter for models trained via gradient-based
algorithms.

Using a queue to store the latest activations and sample IDs, we also achieve
some fault tolerance– if a guest fails to send an activation, the host simply
uses the last one received. We outline the procedure for entity alignment and
augmentation in categorical tasks.

The proposed method optimizes data use, enhancing the robustness and
generalization of the learned models. Empirical results demonstrating the
effectiveness of our approach, including in scenarios with deliberate sample
misalignment, are presented in Section 5.

Algorithm 1 Neural Network Training with Entity Augmentation

1:$\mathcal{D}_{i}\forall i\in\\{1,2,\dots,|\mathcal{G}|,h\\}$: Datasets of
guests $i\in\mathcal{G}$ and host $h$

2:$\mathcal{S}_{i}\ \forall i\in\\{1,2,\dots,|\mathcal{G}|\\}$: Serialized
sets of of entities for which guests $i$ have features

3:$\mathcal{S}_{h}$: Set of entities for which the label owner has labels

4:Label set $\mathcal{L}=\\{\mathbf{y}_{j}\in\mathbb{R}^{c}:\mathbf{y}_{j}$ is
the one-hot label for entity $\mathbf{x}_{j}\\}$

5:$\text{optim}_{i}\forall i\in\\{1,2,\dots,|\mathcal{G}|,h\\}$: parameter
optimizer for each participant

Guest training iteration (for guest $i$)

1:Retrieve the features $\mathbf{x}_{j,i}$ of the next entity $\mathbf{x}_{j}$
in its dataset

2:Calculate guest model output $\mathbf{a}_{i}\leftarrow
m_{i}(\mathbf{x}_{j,i};\theta_{i})$

3:Send $\mathbf{a}_{i}$ and sample ID $j$ to host

4:Receive loss gradient $\nabla_{\mathbf{a}_{i}}\ell$ from the host

5:Perform backpropagation to obtain $\nabla_{\theta_{i}}\ell$

6:Calculate weight update
$\theta_{i}\leftarrow\text{optim}_{i}\left(\nabla_{\theta_{i}}\ell,\theta_{i}\right)$

Server executes

1:Initialize empty activation queues $Q_{i}$ and label queues
$Q_{\text{label},i}$ for each guest.

2:repeat

3: for all guests $i\in\mathcal{G}$ in parallel do

4: Initiate guest training iteration $\triangleright$ send $\mathbf{a}_{i}$,
$j$

5: Add $\mathbf{a}_{i}$ to $Q_{i}$ and $j$ to $Q_{\text{label},i}$

6: end for

7: Read $\hat{\mathbf{a}}_{i}\forall i$ from the top of each $Q_{i}$

8: Calculate prediction $\mathbf{y}\leftarrow
m_{h}(\hat{\mathbf{a}}_{1},\dots,\hat{\mathbf{a}}_{|\mathcal{G}|};\theta_{h})$

9: Read $\mathbf{j}_{i}\forall i$ from the top of each $Q_{\text{label}_{i}}$

10: Retrieve label $\mathbf{y}_{j_{i}}\forall j_{i}$ read

11: Form label
$\mathbf{y}=\frac{\displaystyle\sum_{i=1}^{|\mathcal{G}|}w_{i}\mathbf{y}_{j_{i}}}{\displaystyle\sum_{i=1}^{|\mathcal{G}|}w_{i}}$
where $w_{i}$ is the dimension of $\mathbf{a}_{i}$ $\triangleright$ Entity
Augmentation

12: Compute loss $\ell$

13: Perform backpropagation to obtain $\nabla_{\theta_{h}}\ell$ and
$\nabla_{\mathbf{a}_{i}}\ell\forall i\in\\{1,2,\dots,|\mathcal{G}|\\}$

14: Send all gradients to their respective participants.

15: Calculate weight update
$\theta_{h}\leftarrow\text{optim}_{h}\left(\nabla_{\theta_{h}}\ell,\theta_{h}\right)$

16: for all guests $i\in\mathcal{G}$ in parallel do

17: Complete guest training iteration

18: end for

19:until convergence or a fixed number of iterations

##  5 Experiments

To evaluate the effectiveness of the proposed algorithm, we conduct
experiments on six different real-world datasets using three distinct
architecture models in a SplitNN fashion. [4, 2] The experiments are divided
into the following setups: (1) aligned data setup, where the dataset is
entity-aligned; and (2) misaligned data setup, where the dataset is entity-
augmented/misaligned. This division helps us mimic real-world scenarios where
data may not always be perfectly aligned between clients.

We hope to demonstrate the following:

  1. 1.

Entity Augmentation leads to meaningful learning, that is, Entity Augmentation
allows us to exploit data outside the intersection
$\mathcal{S}_{\mathcal{G}}\cap S_{h}$ (namely, members of
$\bigcup_{i=1}^{|\mathcal{G}|}\left(\mathcal{S}_{i}\cap\mathcal{S}_{h}\right)$).

  2. 2.

Training on datasets with Entity Augmentation and without alignment outperform
that on aligned datasets if there are sufficiently long-range semantic
correlations.

We also provide a brief comparison to few-shot VFL [17] in Table 1.

###  5.1 Datasets

We use the following datasets and architectures for our experiments:

  * •

Computer Vision (CV) Datasets: MNIST [10] and CIFAR-10 split into two guests.
[9] with ResNet-18, ResNet-56 [6], and ResNeXt-29 (8x64d) [19].

  * •

Tabular Datasets: Parkinsons [16] and Credit Card [20].

  * •

Multiview Datasets: Handwritten Digits [3] and Caltech-7 [11].

The tabular and multiview datasets are divided evenly across four guests.

###  5.2 Model Details

Models used for VFL datasets
Handwritten. Guests: linear(120) $\to$ linear(70) $\to$ ReLU; Hosts:
linear(280) $\to$ linear(120) $\to$ LeakyReLU$\to$ linear(40) $\to$ linear(10)
CalTech-7. Guests: linear(512) $\to$ linear(256) $\to$ ReLU; Hosts:
linear(1024) $\to$ linear(512) $\to$ linear(256) $\to$ LeakyReLU $\to$
linear(128) $\to$ linear(7)
Credit Card. Guests: linear(5) $\to$ linear(2) $\to$ ReLU; Hosts: linear(22)
$\to$ linear(10) $\to$ linear(8) $\to$ linear(4) $\to$ linear(1)
Parkinsons. Guests: linear(94) $\to$ linear(47) $\to$ ReLU; Hosts: linear(94)
$\to$ linear(47) $\to$ LeakyReLU $\to$ linear(22) $\to$ linear(10) $\to$
LeakyReLU $\to$ linear(1)

Guest-Host Model Splits for ResNet-like Models
For all our CV models (ResNet-18, ResNet56, ResNeXt-29 8x64), each guest owns
its own CNN filter as well as half of the first fully connected layer. The
remaining fully connected layers are owned by the host.

###  5.3 Nomenclature

We will use the following terminology for the remainder of the paper

  * •

Aligned Data: Refers to entity-aligned/private set intersection data. For
example, in the case of two clients, each client inputs corresponding parts of
the same image into their respective models.

  * •

Misaligned Data: Refers to intentionally misaligned data– the members and
order of the “misaligned" sample space are different for each guest. In this
case, clients input parts of different images into their respective models.

###  5.4 Experimental Setup

#### Exploiting data outside the intersection.

To evaluate the effect of entity augmentation, we propose an experiment where
the dataset is divided into $x\%$ entity-aligned data and
$\frac{(100-x)}{2}\%$ misaligned data for two clients. That is to say, we have
$x\%$ of the dataset aligned between the two guests. where corresponding parts
of the data are assigned to each client. The remaining $(100-x)\%$ is shuffled
and split evenly between the two clients, i.e. each client gets a slice from a
totally non-overlapping subset of the sample space. We attempt to train a
split neural network with just the aligned data and investigate the impact on
performance when the misaligned data is also used via Entity Augmentation.

#### Entity Alignment vs Misaligned Augmentation.

To test the hypothesis that training on misaligned data can outperform aligned
data given long-range semantic correlations, we conduct experiments on fully
aligned and intentionally misaligned data. For each dataset, we train models
on both aligned and misaligned data. We compare the performance of the models
to assess if misaligned data with sufficient long-range semantic correlations
can lead to better learning outcomes. The results of these experiments
demonstrate the impact of data alignment on model performance and the improved
performance of entity augmentation.

###  5.5 Implementation Details

For the CV datasets, we apply the proposed algorithm using ResNet and ResNeXt
architectures. For tabular and multiview datasets, we employ the SplitNN
architecture. Each experiment is run for 60 epochs, with two guests for the CV
and tabular datasets. For multiview datasets, we set the number of guests to
be equal to the number of views. We implement our models in PyTorch and train
them to minimize binary cross entropy loss. The PyTorch implementation
internally calculates a sigmoid. We use the Adam optimizer with
$\beta_{1}=0.9,\beta_{2}=0.999$. We use a learning rate of $0.001$ for all CV
experiments, $0.1$ for both multiview datasets, and $5\times 10^{-4}$ for both
tabular datasets.

Table 1: We compare our method to the results on vanilla VFL and 5-shot VFL due to Sun et al. [17] using the same model. We measure accuracy when a certain number of training samples (denoted in the table as $|\cap\mathcal{S}|$) overlap between the guests, and the remaining samples are split evenly between the two. The host is assumed to know labels for all samples. Entity Augmentation cannot exploit as many samples as few-shot VFL but significantly more than standard VFL, and as a result is performant without requiring guests to guess private labels. Method | Samples Used | Privacy | Accuracy (%) at $\left|\displaystyle\cap\mathcal{S}\right|$
---|---|---|---
256 | 512 | 1024 | 2048
Entity Aug. (Ours) | $\displaystyle\bigcup_{i=1}^{|\mathcal{G}|}\mathcal{S}_{i}\cap S_{h}$ | ✓ | 67.82 | 73.35 | 73.87 | 74.25
Few-shot VFL [17] | $\displaystyle\bigcup_{i=1}^{|\mathcal{G}|}\mathcal{S}_{i}$ | X | 78.93 | 83.03 | 85.68 | 87.23
Standard VFL [17] | $\mathcal{S}_{h}\cap\left(\displaystyle\bigcap_{i=1}^{|\mathcal{G}|}\mathcal{S}_{i}\right)$ | ✓ | 31.47 | 35.33 | 42.71 | 50.75

##  6 Results and Discussions

Table 2: Accuracy comparison between entity aligned and entity misaligned data with Entity Augmentation on MNIST and CIFAR datasets. Dataset |  | Accuracy
---|---|---
Architecture | Aligned | Misaligned
CIFAR10 | ResNet-18 | 72.92% | 74.34%
ResNet-56 | 77.09% | 79.12%
ResNeXt-29 8x64 | 81.08% | 82.06%
MNIST | ResNet-18 | 99.25% | 98.20%
ResNet-56 | 99.34% | 98.44%
ResNeXt-29 8x64 | 99.12% | 98.43%

#### Entity Alignment vs Misaligned Augmentation.

Our experiments with entity augmentation, as shown in Tables 2 and 3,
demonstrate that our method achieves comparable results on the MNIST dataset
and improved performance on the CIFAR, Handwritten, Caltech-7, Credit Card and
Parkinson’s datasets. This is not unexpected since Entity Augmentation is
functionally a form of CutMix, which has been shown to have a regularizing
effect. [21]

MNIST, with its single color channel and simpler, well-defined shapes,
presents fewer long-range feature variations compared to datasets with complex
imagery. For instance, a straight line in the top quarter could ambiguously
belong to a 5 or 7. Thus, performance gains from CutMix are less pronounced on
MNIST.

Figure 2: Training Curves for CIFAR, MNIST, Handwritten, Caltech-7,
Parkinson’s, and Credit Card datasets. Significant convergence improvements
are observed with our method on CIFAR and MNIST. The efficacy extends to
datasets like Handwritten, Caltech-7, Credit Card, and Parkinson’s.

CIFAR 5%

CIFAR 10%

CIFAR ResNet-18

CIFAR ResNet-56

CIFAR ResNext

MNIST 5%

MNIST 10%

MNIST ResNet-18

MNIST ResNet-56

MNIST ResNext

Handwritten

Caltech-7

Credit Card

Parkinson’s

Table 3: Accuracy comparison between training on entity-aligned data vs entity augmented misaligned data on the view-partitioned datasets Handwritten and Caltech-7, and the vertically partitioned tabular datasets Credit Card and Parkinsons.  Dataset | Aligned | Misaligned
---|---|---
Handwritten | 98.25% | 98.63%
Caltech-7 | 98.98% | 98.98%
Credit Card | 81.55% | 81.95%
Parkinsons | 86.34% | 87.22%

#### Exploiting data outside the intersection.

From the results of our experiment in Table 3, it is visible that when only a
tiny entity-aligned dataset is available, using entity misaligned/augmented
data (i.e., with no private set intersection) along with it for training
provides better performance compared to training only on the aligned dataset.
These results clearly support our claim that entity-misaligned/augmented data
is helpful for training and results in better performance than only using
entity-aligned data, resulting in seamless integration of diverse data
sources, reduced data wastage, and enhanced model learning efficiency.

Table 4: Accuracy comparison between training a ResNet–18 on only a small intersection of entity-aligned data vs that entity-aligned data combined with entity augmented misaligned data on MNIST and CIFAR datasets.  Dataset | Accuracy
---|---
| Aligned | Aligned + Misaligned
CIFAR10 ($x=5\%$) | 48.1% | 69.48%
MNIST ($x=5\%$) | 97.1% | 98.37%
CIFAR10 ($x=10\%$) | 54.34% | 70.4%
MNIST ($x=10\%$) | 97.92% | 98.5%

#### More efficient training.

Figures 2 reveal that Entity Augmentation not only boosts the skyline
performance of VFL models, but also allow them to converge substantially
faster. Experiments using only $x\%$ aligned data plateaus at a much lower
accuracy and at a far earlier epoch. A similar trend may be seen in our
experiments on fully aligned vs fully misaligned data. Another interesting
phenomenon is the stability of training– the test accuracy is qualitatively
smoother and more stable wherever Entity Augmentation is used.

##  7 Future Work

The proposed method shows promising results for training pipelines where the
label can be represented in a one-hot encoded fashion. Subsequently, we seek
to extend the idea of generating synthetic labels for regressive tasks. In
this light, Verma et al. [18] investigate the potential of swapping weights in
the penultimate layer to create samples through inference. Expanding upon
this, Hwang et al. [7] use linear interpolation and constrained sampling for
data augmentation. Furthermore, Jiang et al. [8] employ Gaussian Mixture
Models to facilitate the generation of synthetic and continuous sensor data.
Our future endeavours will focus on incorporating such augmentation techniques
within the Vertical Federated Learning (VFL) framework. This integration seeks
to optimize the utilization of data that lies beyond the confines of the
Private Set Intersection, thereby enhancing the efficiency and effectiveness
of the VFL pipeline for regressive tasks.

##  8 Conclusion

This work presents Entity Augmentation, a strategy for generating semantically
meaningful labels for guest activations without entity alignment. We
interpolate labels weighted by features to synthesize labels for training. We
subsequently demonstrate that our pipeline achieves performance on par with
traditional FL approaches that require entity alignment. Our evaluations on
the CIFAR10 and MNIST datasets showed improved results across various baseline
architectures, and we achieved competitive results on Handwritten, Caltech-7,
Parkinsons and Credit Card datasets. In future, we seek to extend the
augmentation technique to regressive tasks and experiment with Gaussian
mixture models and constrained sampling.

## References

  * [1] Amalanshu, A., Sirvi, Y., Inouye, D.I.: Decoupled vertical federated learning for practical training on vertically partitioned data (2024). arXiv:2403.03871
  * [2] Ceballos, I., Sharma, V., Mugica, E., Singh, A., Roman, A., Vepakomma, P., Raskar, R.: Splitnn-driven vertical partitioning (2020). arXiv:2008.04137
  * [3] Dua, D., Graff, C.: UCI machine learning repository (2017), http://archive.ics.uci.edu/ml
  * [4] Gupta, O., Raskar, R.: Distributed learning of deep neural network over multiple agents. Journal of Network and Computer Applications 116, 1–8 (Aug 2018). https://doi.org/10.1016/j.jnca.2018.05.003, https://doi.org/10.1016/j.jnca.2018.05.003
  * [5] Hardy, S., Henecka, W., Ivey-Law, H., Nock, R., Patrini, G., Smith, G., Thorne, B.: Private federated learning on vertically partitioned data via entity resolution and additively homomorphic encryption (2017). arXiv:1711.10677
  * [6] He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition (2015). arXiv:1512.03385
  * [7] Hwang, S.H., Whang, S.E.: Regmix: Data mixing augmentation for regression (2022). arXiv:2106.03374
  * [8] Jiang, X., Yao, L., Yang, Z., Song, Z., Shen, B.: Gaussian mixture model and double-weighted deep neural networks for data augmentation soft sensing. In: 2023 IEEE 12th Data Driven Control and Learning Systems Conference (DDCLS). pp. 1914–1919 (2023). https://doi.org/10.1109/DDCLS58216.2023.10166693
  * [9] Krizhevsky, A.: Learning multiple layers of features from tiny images. Tech. rep. (2009)
  * [10] LeCun, Y., Cortes, C., Burges, C.: Mnist handwritten digit database. ATT Labs [Online]. Available: http://yann.lecun.com/exdb/mnist 2 (2010)
  * [11] Li, F.F., Andreeto, M., Ranzato, M., Perona, P.: Caltech 101 (April 2022). https://doi.org/10.22002/D1.20086
  * [12] Lu, L., Ding, N.: Multi-party private set intersection in vertical federated learning. 2020 IEEE 19th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom) pp. 707–714 (2020), https://api.semanticscholar.org/CorpusID:231916141
  * [13] McMahan, B., Moore, E., Ramage, D., Hampson, S., Arcas, B.A.y.: Communication-Efficient Learning of Deep Networks from Decentralized Data. In: Singh, A., Zhu, J. (eds.) Proceedings of the 20th International Conference on Artificial Intelligence and Statistics. Proceedings of Machine Learning Research, vol. 54, pp. 1273–1282. PMLR (20–22 Apr 2017), https://proceedings.mlr.press/v54/mcmahan17a.html
  * [14] Morales, D., Agudo, I., Lopez, J.: Private set intersection: A systematic literature review. Computer Science Review 49, 100567 (2023). https://doi.org/https://doi.org/10.1016/j.cosrev.2023.100567, https://www.sciencedirect.com/science/article/pii/S1574013723000345
  * [15] Nock, R., Hardy, S., Henecka, W., Ivey-Law, H., Patrini, G., Smith, G., Thorne, B.: Entity resolution and federated learning get a federated resolution (2018). arXiv:1803.04035
  * [16] Sakar, C.O., Serbes, G., Gunduz, A., Tunc, H.C., Nizam, H., Sakar, B.E., Tutuncu, M., Aydin, T., Isenkul, M.E., Apaydin, H.: A comparative analysis of speech signal processing algorithms for parkinson’s disease classification and the use of the tunable q-factor wavelet transform. Applied Soft Computing 74, 255–263 (2019)
  * [17] Sun, J., Xu, Z., Yang, D., Nath, V., Li, W., Zhao, C., Xu, D., Chen, Y., Roth, H.R.: Communication-efficient vertical federated learning with limited overlapping samples. In: Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV). pp. 5203–5212 (October 2023)
  * [18] Verma, V., Lamb, A., Beckham, C., Najafi, A., Mitliagkas, I., Courville, A., Lopez-Paz, D., Bengio, Y.: Manifold mixup: Better representations by interpolating hidden states (2019). arXiv:1806.05236
  * [19] Xie, S., Girshick, R., Dollár, P., Tu, Z., He, K.: Aggregated residual transformations for deep neural networks (2017). arXiv:1611.05431
  * [20] Yeh, I.C., Lien, C.h.: The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert systems with applications 36(2), 2473–2480 (2009)
  * [21] Yun, S., Han, D., Oh, S.J., Chun, S., Choe, J., Yoo, Y.: Cutmix: Regularization strategy to train strong classifiers with localizable features (2019). arXiv:1905.04899


# Adaptive Collaborative Similarity Learning for Unsupervised
Multi-view Feature Selection

Xiao Dong1, Lei Zhu1, Xuemeng Song2, Jingjing Li3, Zhiyong Cheng4
1 School of Information Science and Engineering, Shandong Normal University,
China
2 School of Computer Science and Technology, Shandong University, China
3 University of Electronic Science and Technology of China, China
4 School of Computing, National University of Singapore, Singapore
<EMAIL_ADDRESS>Corresponding Author

###### Abstract

In this paper, we investigate the research problem of unsupervised multi-view
feature selection. Conventional solutions first simply combine multiple pre-
constructed view-specific similarity structures into a collaborative
similarity structure, and then perform the subsequent feature selection. These
two processes are separate and independent. The collaborative similarity
structure remains fixed during feature selection. Further, the simple
undirected view combination may adversely reduce the reliability of the
ultimate similarity structure for feature selection, as the view-specific
similarity structures generally involve noises and outlying entries. To
alleviate these problems, we propose an adaptive collaborative similarity
learning (ACSL) for multi-view feature selection. We propose to dynamically
learn the collaborative similarity structure, and further integrate it with
the ultimate feature selection into a unified framework. Moreover, a
reasonable rank constraint is devised to adaptively learn an ideal
collaborative similarity structure with proper similarity combination weights
and desirable neighbor assignment, both of which could positively facilitate
the feature selection. An effective solution guaranteed with the proved
convergence is derived to iteratively tackle the formulated optimization
problem. Experiments demonstrate the superiority of the proposed approach.

##  1 Introduction

With the advent of big data, multi-view features with high dimensions are
widely employed to represent the complex data in various research fields, such
as multimedia computing, machine learning and data mining Liu et al. (2016,
2017); Zhu et al. (2017b, 2015); Cheng and Shen (2016); Cheng et al. (2016).
On the one hand, with multi-view features, the data could be characterized
more precisely and comprehensively from different perspectives. On the other
hand, high-dimensional multi-view features will inevitably generate expensive
computation cost and cause massive storage cost. Moreover, they may contain
adverse noises, outlying entries, irrelevant and correlated features, which
may be detrimental to the subsequent learning process Zhu et al. (2016b, a,
2017a). Unsupervised multi-view feature selection Wang et al. (2016); Li and
Liu (2017) is devised to alleviate the problem. It selects a compact subset of
informative features from the original features by dropping irrelevant and
redundant features with advanced unsupervised learning. Due to the
independence on semantic labels, high computing efficiency and well
interpretation capability, unsupervised multi-view feature selection has
received considerable attention in literature. It becomes a prerequisite
component in various machine learning models Li et al. (2017).

The key problem of multi-view feature selection is how to effectively exploit
the diversity and consistency of multi-view features to collaboratively
identify the feature dimensions, which could retain the key characteristics of
the original features. Existing approaches can be categorized into two major
families. The first kind of methods first concatenates multi-view features
into a vector and then directly imports it into the conventional single-view
feature selection model. The candidate features are generally ranked based on
spectral graph theory. Typical methods of this kind include Laplacian Score
(LapScor) He et al. (2005), spectral feature selection (SPEC) Zhao and Liu
(2007) and minimum redundancy spectral feature selection (MRSF) Zhao et al.
(2010). Commonly, the pipeline of these methods follows two separate
processes: 1) Similarity structure is constructed with fixed graph parameters
to describe the geometric structure of data. 2) Sparsity and manifold
regularization are employed together to identify the most salient features.
Although these methods are reported to achieve certain success, they treat
features from different views independently and unfortunately neglect the
important view correlations.

Another family of methods considers view correlation when performing feature
selection. Representative works include adaptive multi-view feature selection
(AMFS) Wang et al. (2016), multi-view feature selection (MVFS) Tang et al.
(2013) and adaptive unsupervised multi-view feature selection (AUMFS) Feng et
al. (2013). These methods first construct multiple view-specific similarity
structures111In this paper, view-specific similarity structure is constructed
with the corresponding view-specific feature. and then perform the subsequent
feature selection based on the collaborative (combined) similarity structure.
These two processes are separate and independent. The collaborative similarity
structure remains fixed during feature selection. The latently involved data
noises and outlying entries in the view-specific similarity structures will
adversely reduce the reliability of the ultimate collaborative similarity
structure for feature selection. Furthermore, conventional approaches
generally employ $k$-nearest neighbors assignment to construct the view-
specific similarity structures and the simple weighted combination for
ultimate similarity structure generation. This strategy can hardly achieve the
ideal state for clustering that the number of connected components in the
ultimate similarity structure is equal to the number of clusters Nie et al.
(2014). Thus, suboptimal performance may be caused under such circumstance.

In this paper, we introduce an adaptive collaborative similarity learning
(ACSL) for unsupervised multi-view feature selection. The main contributions
of this paper can be summarized as follows:

  * •

Different from existing solutions, we integrate the collaborative similarity
structure learning and multi-view feature selection into a unified framework.
The collaborative similarity structure and similarity combination weights
could be learned adaptively by considering the ultimate feature selection
performance. Simultaneously, the feature selection can preserve the
dynamically adjusted similarity structure.

  * •

We impose a reasonable rank constraint to adaptively learn an ideal
collaborative similarity structure with proper neighbor assignment which could
positively facilitate the ultimate feature selection. An effective alternate
optimization approach guaranteed with convergence is derived to iteratively
solve the formulated optimization problem.

##  2 Related Work

One kind of unsupervised multi-view feature selection methods directly imports
the concatenated features in multiple views into the single-view feature
selection model. In He et al. (2005), Laplacian score (LapScor) is employed to
measure the capability of each feature dimension on preserving sample
similarity. Zhao and Liu (2007) proposes a general spectral theory based
learning framework to unify the unsupervised and supervised feature selection.
Zhao et al. (2010) adopts an embedding model to handle feature redundancy in
the spectral feature selection. These methods generally rank the candidate
feature dimensions with various graphs which characterize the manifold
structure. They treat features from different views independently and
unfortunately ignore the important correlation of different feature views.
Another kind of methods directly tackles the multi-view feature selection.
They consider view correlations when performing feature selection. Adaptive
multi-view feature selection (AMFS) Wang et al. (2016) is an unsupervised
feature selection approach which is developed for human motion retrieval. It
describes the local geometric structure of data in each view with local
descriptor and performs the feature selection in a general trace ratio
optimization. In this method, the feature dimensions are determined with trace
ratio criteria. Adaptive unsupervised multi-view feature selection (AUMFS)
Feng et al. (2013) addresses the feature selection problem for visual concept
recognition. It employs $l_{2,1}$ norm Nie et al. (2010) based sparse
regression model to automatically identify discriminative features. In AUMFS,
data cluster structure, data similarity and the correlations of different
views are considered for feature selection. Multi-view feature selection
(MVFS) Tang et al. (2013) investigates the feature selection for multi-view
data in social media. A learning framework is devised to exploit the relations
of views and help each view select relevant features.

##  3 The Proposed Methodology

###  3.1 Notations and Definitions

Throughout the paper, all the matrices are written in uppercase with boldface.
For a matrix $\textbf{M}\in\mathcal{R}^{N\times d}$, its $i_{th}$ row is
denoted by $\textbf{M}_{i^{\prime}}\in\mathcal{R}^{N\times 1}$, its $j_{th}$
column is denoted by $\textbf{M}_{j}\in\mathcal{R}^{d\times 1}$. The element
in the $i_{th}$ row and $j_{th}$ column is represented as $M_{ij}$. The trace
of the matrix M is denoted as $Tr(\textbf{M})$. The transpose of matrix M is
denoted as $\textbf{M}^{\texttt{T}}$. The $l_{2,1}$ norm of the matrix M is
denoted as $||\textbf{M}||_{2,1}$, which is calculated by
$\sum_{i=1}^{N}\sqrt{\sum_{j=1}^{d}M_{i,j}^{2}}$. The Frobenius norm of M is
denoted by
$||\textbf{M}||_{F}=\sqrt{\sum_{i=1}^{N}\sum_{j=1}^{d}M_{i,j}^{2}}$. 1 denotes
a column vector whose all elements are one. $\textbf{I}_{k\times k}$ denotes
$k\times k$ identify matrix.

The feature matrix of data in the $v_{th}$ view is denoted as
$\textbf{X}^{v}=[\textbf{x}_{1}^{v},\textbf{x}_{2}^{v},...,\textbf{x}_{N}^{v}]^{\texttt{T}}\in\mathcal{R}^{N\times
d_{v}}$, $\textbf{x}_{1}^{v}\in\mathcal{R}^{d_{v}\times 1}$, $d_{v}$ is the
dimension of feature in the $v_{th}$ view, $N$ is the number of data samples.
We pack the feature matrices in $V$ views $\\{\textbf{X}^{v}\\}_{v=1}^{V}$ and
the overall feature matrix of data can be represented as
$\textbf{X}=[\textbf{X}^{1},\textbf{X}^{2},...,\textbf{X}^{V}]\in\mathcal{R}^{N\times
d}$, $\sum_{v=1}^{V}d_{v}=d$. The objective of unsupervised multi-view feature
selection is to identify $l$ most valuable features with only X.

###  3.2 Formulation

The importance of feature dimensions are primarily determined by measuring the
their capabilities on preserving the similarity structures in multiple views.
In this paper, we develop a unified learning framework to learn an adaptive
collaborative similarity structure with automatic neighbor assignment for
multi-view feature selection. In our model, the neighbors in the collaborative
similarity structure could be adaptively assigned by considering the feature
selection performance, and simultaneously the feature selection could preserve
the dynamically constructed collaborative similarity structure. Given $V$
similarity structures constructed in multiple views
$\\{\textbf{S}^{v}\\}_{v=1}^{V}$, $V$ is the number of views, we can
automatically learn a collaborative similarity structure S by combining
$\\{\textbf{S}^{v}\\}_{v=1}^{V}$ with $V$ weights.

$\displaystyle\arg\min_{\textbf{S},\textbf{W}}\
\sum_{j=1}^{N}||\textbf{S}_{j}-\sum_{v=1}^{V}w_{j}^{v}\textbf{S}_{j}^{v}||_{F}^{2}$
(1) $\displaystyle s.t.\ \forall j\
\textbf{1}_{N}^{\texttt{T}}\textbf{S}_{j}=1,\textbf{S}_{j}\geq\textbf{0},\textbf{W}_{j}^{\texttt{T}}\textbf{1}_{V}=1$

where $\textbf{S}_{j}\in\mathcal{R}^{N\times 1}$ characterizes the
similarities between any data points with $j$, it should be subjected to the
constraint that
$\textbf{1}^{\texttt{T}}\textbf{S}_{j}=1,\textbf{S}_{j}\geq\textbf{0}$,
$\textbf{W}_{j}=[w_{j}^{1},w_{j}^{2},...,w_{j}^{V}]^{\texttt{T}}\in\mathcal{R}^{V\times
1}$ is comprised of view weights for the $j_{th}$ column of similarities, it
is constrained with $\textbf{W}_{j}^{\texttt{T}}\textbf{1}_{V}=1$,
$\textbf{W}=[\textbf{W}_{1},\textbf{W}_{2},...,\textbf{W}_{N}]\in\mathcal{R}^{V\times
N}$ is view weight matrix for all columns in the similarity structures. As
indicated in recent work Nie et al. (2014), a theoretically ideal similarity
structure for clustering should have the property that the number of connected
components is equal to the number of clusters. The similarity structure with
such neighbor assignment could benefit the subsequent feature selection.
Unfortunately, the similarity structure learned from Eq.(LABEL:eq:sh) does not
have such desirable property.

To tackle the problem, in this paper, we impose a reasonable rank constraint
on the Laplacian matrix of the collaborative similarity structure to enable it
to have such property. Our idea is motivated by the following spectral graph
theory.

######  Theorem 1.

If the similarity structure S are nonnegative, the multiplicity of eigen-
values $0$ corresponding to its Laplacain matrix is equal to the number of
components of S. Alavi (1991)

As mentioned above, the data points can be directly partitioned into $k$
clusters if the number of components in the similarity structure S is exactly
equal to $k$. Theorem 1 indicates that this condition can be achieved if the
rank of Laplacian matrix is equal to $n-k$. With the analysis, we add a
reasonable rank constraint in Eq.(LABEL:eq:sh) to achieve the condition. The
optimization problem becomes

$\displaystyle\arg\min_{\textbf{S},\textbf{W}}\
\sum_{j=1}^{N}||\textbf{S}_{j}-\sum_{v=1}^{V}\
w_{j}^{v}\textbf{S}_{j}^{v}||_{F}^{2}$ (2) $\displaystyle s.t.\ \forall
j\quad\textbf{1}_{N}^{\texttt{T}}\textbf{S}_{j}=1,\textbf{S}_{j}\geq\textbf{0},\textbf{W}_{j}^{\texttt{T}}\textbf{1}_{V}=1,rank(\textbf{L}_{S})=n-k$

where
$\textbf{L}_{S}=\textbf{D}_{S}-\frac{\textbf{S}^{\texttt{T}}+\textbf{S}}{2}$
is the Laplacain matrix of similarity structure S,
$\textbf{D}_{S}=\textbf{S}\textbf{1}$ is diagonal matrix. As shown in
Eq.(LABEL:eq:si), directly imposing the rank constraint
$rank(\textbf{L}_{S})=n-k$ will make the above problem hard to solve.
Fortunately, according to Ky Fan’s Theorem K. (1949), we can have
$\sum_{i=1}^{k}\delta_{i}(\textbf{L}_{S})=\arg\min_{\textbf{F}\in\mathcal{R}^{n\times
k},\textbf{F}^{\texttt{T}}\textbf{F}=\textbf{I}_{k}}Tr(\textbf{F}^{\texttt{T}}\textbf{L}_{S}\textbf{F})$,
where $\delta_{i}(\textbf{L}_{S})$ is the $i_{th}$ smallest eigen-values of
$\textbf{L}_{S}$ and $\textbf{F}\in\mathcal{R}^{N\times k}$ is the relaxed
cluster indicator matrix. Obviously, the rank constraint
$rank(\textbf{L}_{S})=n-k$ can be satisfied when
$\sum_{i=1}^{k}\delta_{i}(\textbf{L}_{S})=0$. To this end, we reformulate the
Eq.(LABEL:eq:si) as the following simple equivalent form

$\displaystyle\arg\min_{\textbf{F},\textbf{S},\textbf{W}}\
\sum_{j=1}^{N}||\textbf{S}_{j}-\sum_{v=1}^{V}w_{j}^{v}\textbf{S}_{j}^{v}||_{F}^{2}+\alpha
Tr(\textbf{F}^{\texttt{T}}\textbf{L}_{S}\textbf{F})$ (3) $\displaystyle s.t.\
\forall
j\quad\textbf{1}_{N}^{\texttt{T}}\textbf{S}_{j}=1,\textbf{S}_{j}\geq\textbf{0},\textbf{W}_{j}^{\texttt{T}}\textbf{1}_{V}=1,\textbf{F}\in\mathcal{R}^{N\times
k},\textbf{F}^{\texttt{T}}\textbf{F}=\textbf{I}_{k}$

As shown in the above equation, when $\alpha>0$ is large enough, the term
$Tr(\textbf{F}^{\texttt{T}}\textbf{L}_{S}\textbf{F})$ is forced to be
infinitely approximate 0 and the rank constraint can be satisfied accordingly.
By simply transforming the rank constraint to trace in objective function, the
problem in Eq.(LABEL:eq:si) can be tackled more easily.

The selected features should preserve the dynamically learned similarity
structure. Conventional approaches separate the similarity structure
construction and feature selection into two independent processes, which will
potentially lead to sub-optimal performance. In this paper, we learn the
collaborative similarity structure dynamically and further integrate it with
feature selection into a unified framework. Specifically, based on the
collaborative similarity structure learning in Eq.(LABEL:eq:sj), we employ
sparse regression model to learn a projection matrix
$\textbf{P}\in\mathcal{R}^{d\times k}$, so that the projected low-dimensional
data XP can approximate the relaxed cluster indicator F. To select the
features, we impose $l_{2,1}$ norm penalty on P to force it with row sparsity.
The importance of features can be measured by the $l_{2}$ norm of each row
feature in P. The overall optimization formulation can be derived as

$\displaystyle\arg\min_{\textbf{P},\textbf{F},\textbf{S},\textbf{W}}\
\boldsymbol{\Omega}(\textbf{P},\textbf{F},\textbf{S},\textbf{W})=\sum_{j=1}^{N}||\textbf{S}_{j}-\sum_{v=1}^{V}w_{j}^{v}\textbf{S}_{j}^{v}||_{F}^{2}+$
(4) $\displaystyle\qquad\qquad\qquad\alpha
Tr(\textbf{F}^{\texttt{T}}\textbf{L}_{S}\textbf{F})+\beta(||\textbf{X}\textbf{P}-\textbf{F}||_{F}^{2}+\gamma||\textbf{P}||_{2,1})$
$\displaystyle s.t.\ \forall
j\quad\textbf{1}_{N}^{\texttt{T}}\textbf{S}_{j}=1,\textbf{S}_{j}\geq\textbf{0},\textbf{W}_{j}^{\texttt{T}}\textbf{1}_{V}=1,\textbf{F}\in\mathcal{R}^{N\times
k},\textbf{F}^{\texttt{T}}\textbf{F}=\textbf{I}_{k}$

With P, the importance of features are measured by
$||\textbf{P}_{i^{\prime}}||_{2}$. The features with the $l$ largest values
can be finally determined.

###  3.3 Alternate Optimization

As shown in Eq.(LABEL:eq:overall), the objective function is not convex to
three variables simultaneously. In this paper, we propose an effective
alternate optimization to iteratively solve the problem. Specifically, we
optimize one variable by fixing the others.

Update P. By fixing the other variables, the optimization for P can be derived
as

$\displaystyle\arg\min_{\textbf{P}}$ $\displaystyle\
||\textbf{X}\textbf{P}-\textbf{F}||_{F}^{2}+\gamma||\textbf{P}||_{2,1}$ (5)

This equation is not differentiable. Hence, we transform it to following
equivalent equation Nie et al. (2010)

$\displaystyle\arg\min_{\textbf{P}}$ $\displaystyle\
||\textbf{X}\textbf{P}-\textbf{F}||_{F}^{2}+\gamma
Tr(\textbf{P}^{\texttt{T}}\boldsymbol{\Gamma}\textbf{P})$ (6)

$\boldsymbol{\Gamma}\in\mathcal{R}^{d\times d}$ is diagonal matrix whose
$i_{th}$ diagonal element is
$\frac{1}{2\sqrt{\textbf{P}_{i^{\prime}}\textbf{P}_{i^{\prime}}^{\texttt{T}}}+\epsilon}$.
$\epsilon$ is small enough constant. It is used to avoid the condition that
$||\textbf{P}_{i^{\prime}}||_{2}$ is zero. By calculating the derivations of
the objective function with P and setting it to zeros, we can obtain the
updating rule for P as

$\displaystyle\textbf{P}=(\textbf{X}^{\texttt{T}}\textbf{X}+\gamma\boldsymbol{\Gamma})^{-1}\textbf{X}^{\texttt{T}}\textbf{F}$
(7)

Note that $\boldsymbol{\Gamma}$ is dependent on P. We develop an iterative
approach to solve P and $\boldsymbol{\Gamma}$ until convergence. Specifically,
we fix $\boldsymbol{\Gamma}$ to solve P, and vice versa.

Update F. By fixing the other variables, the optimization for F can be derived
as

$\displaystyle\arg\min_{\textbf{F}}$ $\displaystyle\
Tr(\textbf{F}^{\texttt{T}}\textbf{L}_{S}\textbf{F})+\beta(||\textbf{X}\textbf{P}-\textbf{F}||_{F}^{2}+\gamma
Tr(\textbf{P}^{\texttt{T}}\boldsymbol{\Gamma}\textbf{P}))s.t.\textbf{F}^{\texttt{T}}\textbf{F}=\textbf{I}_{c}$
(8)

By substituting Eq.(7) into the objective function in Eq.(8), we arrive at

$\displaystyle
Tr(\textbf{F}^{\texttt{T}}\textbf{L}_{S}\textbf{F})+\beta(||\textbf{X}\textbf{P}-\textbf{F}||_{F}^{2}+\gamma
Tr(\textbf{P}^{\texttt{T}}\boldsymbol{\Gamma}\textbf{P}))$ (9)
$\displaystyle=Tr(\textbf{F}^{\texttt{T}}(\textbf{L}_{S}+\beta\textbf{I}_{N}-\beta\textbf{X}\textbf{Q}^{-1}\textbf{X}^{\texttt{T}})\textbf{F})$

where
$\textbf{Q}=\textbf{X}^{\texttt{T}}\textbf{X}+\gamma\boldsymbol{\Gamma}$. With
the transformation, the optimization for updating F can be solved by simple
eigen-decomposition on the matrix
$\textbf{L}_{S}+\beta\textbf{I}_{N}-\beta\textbf{X}\textbf{Q}^{-1}\textbf{X}^{\texttt{T}}$.
Specifically, the columns of F are comprised of the $k$ eigenvectors
corresponding to the $k$ smallest eigenvalues.

Update S. By fixing the other variables, the optimization for S becomes

$\displaystyle\arg\min_{\textbf{S}}\sum_{j=1}^{N}||\textbf{S}_{j}-\sum_{v=1}^{V}w_{j}^{v}\textbf{S}_{j}^{v}||_{F}^{2}+\alpha
Tr(\textbf{F}^{\texttt{T}}\textbf{L}_{S}\textbf{F})$ (10) $\displaystyle s.t.\
\forall j\
\textbf{1}_{N}^{\texttt{T}}\textbf{S}_{j}=1,\textbf{S}_{j}\geq\textbf{0}$

The above equation can be rewritten as

$\displaystyle\arg\min_{\textbf{S}_{j}}\sum_{j=1}^{N}||\textbf{S}_{j}-\sum_{v=1}^{V}w_{j}^{v}\textbf{S}^{v}_{j}||_{F}^{2}+\alpha\sum_{i,j=1}^{N}||\textbf{f}_{i}-\textbf{f}_{j}||_{2}^{2}S_{i,j}$
(11) $\displaystyle s.t.\ \forall j\
\textbf{1}_{N}^{\texttt{T}}\textbf{S}_{j}=1,\textbf{S}_{j}\geq\textbf{0}$

where $S_{i,j}$ denotes the element in the $i_{th}$ row and $j_{th}$ column of
S. The optimization processes for the columns of S are independent with each
other. Hence, they can be optimized separately. Formally, S can be solved by

$\displaystyle\arg\min_{\textbf{S}_{j}}||\textbf{S}_{j}-\sum_{v=1}^{V}w_{j}^{v}\textbf{S}^{v}_{j}||_{F}^{2}+\alpha\textbf{A}_{j}^{\texttt{T}}\textbf{S}_{j}\quad
s.t.\ \forall j\
\textbf{1}_{N}^{\texttt{T}}\textbf{S}_{j}=1,\textbf{S}_{j}\geq\textbf{0}$ (12)

Let $\textbf{A}_{j}$ be row vector with $N\times 1$ dimensions. Its $i_{th}$
element is $||\textbf{f}_{i}-\textbf{f}_{j}||_{2}^{2}$. The above optimization
formula can be transformed as

$\displaystyle\arg\min_{\textbf{S}_{j}}||\textbf{S}_{j}+\frac{\alpha}{2}\textbf{A}_{j}-\sum_{v=1}^{V}w_{j}^{v}\textbf{S}^{v}_{j}||_{F}^{2}\quad
s.t.\ \forall j\
\textbf{1}_{N}^{\texttt{T}}\textbf{S}_{j}=1,\textbf{S}_{j}\geq\textbf{0}$ (13)

This problem can be solved by an efficient iterative algorithm Huang et al.
(2015).

Update W. Similar to S, the optimization processes for the columns of W are
independent with each other. Hence, they can be optimized separately.
Formally, its $j_{th}$ column $\textbf{W}_{j}$ is solved by

$\displaystyle\arg\min_{\textbf{W}_{j}}\
||\textbf{S}_{j}-\sum_{v=1}^{V}w_{j}^{v}\textbf{S}^{v}_{j}||_{F}^{2}\quad
s.t.\ \textbf{W}_{j}^{\texttt{T}}\textbf{1}_{V}=1$ (14)

The objective function in Eq.(LABEL:eq:updateweight) can be rewritten as

$\displaystyle||\textbf{S}_{j}-\sum_{v=1}^{V}w_{j}^{v}\textbf{S}^{v}_{j}||_{F}^{2}=||\sum_{v=1}^{V}w_{j}^{v}\textbf{S}_{j}-\sum_{v=1}^{V}w_{j}^{v}\textbf{S}^{v}_{j}||_{F}^{2}$
(15)
$\displaystyle=||\sum_{v=1}^{V}w_{j}^{v}(\textbf{S}_{j}-\textbf{S}^{v}_{j})||_{F}^{2}=||\textbf{B}_{j}\textbf{W}_{j}||_{F}^{2}=\textbf{W}_{j}^{\texttt{T}}\textbf{B}_{j}^{\texttt{T}}\textbf{B}_{j}\textbf{W}_{j}$

where $\textbf{B}_{j}^{v}=\textbf{S}_{j}-\textbf{S}^{v}_{j}$,
$\textbf{B}_{j}=[\textbf{B}_{j}^{1},...,\textbf{B}_{j}^{v},..,\textbf{B}_{j}^{V}]$.

We can obtain the Lagrangian function of problem (LABEL:eq:updateweight)

$\displaystyle\mathcal{L}(W_{j},\psi)=\textbf{W}_{j}^{\texttt{T}}\textbf{B}_{j}^{\texttt{T}}\textbf{B}_{j}\textbf{W}_{j}+\psi(1-\textbf{W}_{j}^{\texttt{T}}\textbf{1}_{V})$
(16)

$\psi$ is also Lagrangian multiplier. By calculating the derivative of (16)
with $\textbf{W}_{j}$ and setting it to 0, we obtain the updating rule of
$\textbf{W}_{j}$ as

$\displaystyle\textbf{W}_{j}=\frac{(\textbf{B}_{j}^{\texttt{T}}\textbf{B}_{j})^{-1}\textbf{1}_{V}}{\textbf{1}_{V}^{\texttt{T}}(\textbf{B}_{j}^{\texttt{T}}\textbf{B}_{j})^{-1}\textbf{1}_{V}}$
(17)

Dataset | Feature dimension | LapScor | SPEC | MRSF | MVFS | AUMFS | AMFS | ACSL
---|---|---|---|---|---|---|---|---
| 100 | 0.2867 | 0.2952 | 0.2838 | 0.2762 | 0.2810 | 0.28571 | 0.3000
| 200 | 0.2952 | 0.2905 | 0.3152 | 0.2905 | 0.3143 | 0.2895 | 0.3124
MSRC-V1 | 300 | 0.2905 | 0.3119 | 0.2895 | 0.2833 | 0.2833 | 0.2952 | 0.3124
| 400 | 0.2952 | 0.3181 | 0.3057 | 0.3000 | 0.2952 | 0.2924 | 0.3219
| 500 | 0.3038 | 0.2976 | 0.3038 | 0.3095 | 0.3048 | 0.2990 | 0.3400
| 100 | 0.5844 | 0.4795 | 0.6207 | 0.5938 | 0.3345 | 0.3302 | 0.6106
| 200 | 0.6148 | 0.5520 | 0.6002 | 0.5820 | 0.4225 | 0.4226 | 0.6389
Handwritten Numeral | 300 | 0.5980 | 0.5384 | 0.6028 | 0.5737 | 0.4757 | 0.4497 | 0.5930
| 400 | 0.6068 | 0.6102 | 0.5890 | 0.5808 | 0.4909 | 0.4755 | 0.6327
| 500 | 0.5909 | 0.5666 | 0.5795 | 0.5888 | 0.4889 | 0.5006 | 0.5969
| 100 | 0.2873 | 0.2873 | 0.2851 | 0.2717 | 0.1305 | 0.2165 | 0.2861
| 200 | 0.2896 | 0.2840 | 0.2754 | 0.2774 | 0.1274 | 0.2313 | 0.2924
Youtube | 300 | 0.2835 | 0.2832 | 0.2862 | 0.2828 | 0.1357 | 0.2374 | 0.2906
| 400 | 0.2862 | 0.2889 | 0.2779 | 0.2807 | 0.1329 | 0.2433 | 0.2993
| 500 | 0.2857 | 0.2853 | 0.2802 | 0.2854 | 0.1329 | 0.2546 | 0.3003
| 100 | 0.3687 | 0.3327 | 0.3707 | 0.2044 | 0.4231 | 0.4313 | 0.5845
| 200 | 0.3619 | 0.3295 | 0.3501 | 0.2104 | 0.4656 | 0.4816 | 0.5616
Outdoor Scene | 300 | 0.3634 | 0.3740 | 0.3576 | 0.2150 | 0.4949 | 0.4854 | 0.5801
| 400 | 0.3804 | 0.3653 | 0.3679 | 0.2153 | 0.5061 | 0.4926 | 0.5927
| 500 | 0.3574 | 0.3620 | 0.3687 | 0.2255 | 0.5003 | 0.5045 | 0.6103
Table 1: ACC of different methods with different numbers of selected features
by using K-means for clustering.

The main steps for solving problem (LABEL:eq:overall) are summarized in
Algorithm 1.

Algorithm 1 Multi-view feature selection via collaborative similarity
structure learning with adaptive neighbors.

0: The pre-constructed similarity structures in $v$ views
$\\{\textbf{S}^{v}\\}_{v=1}^{V}$, the number of clusters $k$, the parameters
$\alpha,\beta,\gamma$.

0: The collaborative similarity structure S, the projection matrix P for
feature selection, $l$ identified features.

1: Initialize W with $\frac{1}{V}$, the collaborative similarity structure S
with the weighted sum of $\\{\textbf{S}^{v}\\}_{v=1}^{V}$. We also initialize
F with the solution of problem (8) by substituting the Laplacian matrix
calculated from the new S.

2: repeat

3: Update P with Eq.(7).

4: Update F by solving the problem in Eq.(8).

5: Update S with Eq.(LABEL:eq:updateS3).

6: Update W with Eq.(17).

7: until ConvergenceFeature Selection

8: Calculate $||\textbf{P}_{i^{\prime}}||_{2},(i=1,2,...,d)$ and rank them in
descending order. The $l$ features with the top rank orders are finally
determined as the features to be selected.

###  3.4 Convergence Analysis

The convergence of solving problem (6) can be proven by the following theorem.

######  Theorem 2.

The iterative optimization process for solving Eq.(5) will monotonically
decrease the objective function value until convergence.

###### Proof.

Let $\widehat{\textbf{P}}$ be the newly updated P, we can obtain the following
inequality

$\displaystyle||\textbf{X}\widehat{\textbf{P}}-\textbf{F}||_{F}^{2}+\gamma
Tr(\widehat{\textbf{P}}^{\texttt{T}}\boldsymbol{\Gamma}\widehat{\textbf{P}})\leq||\textbf{X}\textbf{P}-\textbf{F}||_{F}^{2}+\gamma
Tr(\textbf{P}^{\texttt{T}}\boldsymbol{\Gamma}\textbf{P})$ (18)

By adding
$\gamma\sum_{i=1}^{d}\frac{\epsilon}{2\sqrt{\textbf{P}_{i^{\prime}}^{\texttt{T}}\textbf{P}_{i^{\prime}}}+\epsilon}$
to the both sides of the inequality (LABEL:ieq:1) and substituting
$\boldsymbol{\Gamma}$, the inequality can be rewritten as

$\displaystyle||\textbf{X}\widehat{\textbf{P}}-\textbf{F}||_{F}^{2}+\gamma\sum_{i=1}^{d}\frac{\widehat{\textbf{P}}_{i^{\prime}}^{\texttt{T}}\widehat{\textbf{P}}_{i^{\prime}}+\epsilon}{2\sqrt{\textbf{P}_{i^{\prime}}^{\texttt{T}}\textbf{P}_{i^{\prime}}+\epsilon}}\leq$
(19)
$\displaystyle||\textbf{X}\textbf{P}-\textbf{F}||_{F}^{2}+\gamma\sum_{i=1}^{d}\frac{\textbf{P}_{i^{\prime}}^{\texttt{T}}\textbf{P}_{i^{\prime}}+\epsilon}{2\sqrt{\textbf{P}_{i^{\prime}}^{\texttt{T}}\textbf{P}_{i^{\prime}}+\epsilon}}$

On the other hand, according to the Lemma 1 in Nie et al. (2010), we can
obtain that for any positive number $u$ and $v$, we can have

$\displaystyle\sqrt{u}-\frac{\sqrt{u}}{2\sqrt{v}}\leq\sqrt{v}-\frac{\sqrt{v}}{2\sqrt{v}}$
(20)

Then, we can obtain that

$\displaystyle\gamma\sum_{i=1}^{d}\sqrt{\widehat{\textbf{P}}_{i^{\prime}}^{\texttt{T}}\widehat{\textbf{P}}_{i^{\prime}}+\epsilon}-\gamma\sum_{i=1}^{d}\frac{\widehat{\textbf{P}}_{i^{\prime}}^{\texttt{T}}\widehat{\textbf{P}}_{i^{\prime}}+\epsilon}{2\sqrt{\textbf{P}_{i^{\prime}}^{\texttt{T}}\textbf{P}_{i^{\prime}}+\epsilon}}$
(21)
$\displaystyle\leq\gamma\sum_{i=1}^{d}\sqrt{\textbf{P}_{i^{\prime}}^{\texttt{T}}\textbf{P}_{i^{\prime}}+\epsilon}-\gamma\sum_{i=1}^{d}\frac{\textbf{P}_{i^{\prime}}^{\texttt{T}}\textbf{P}_{i^{\prime}}+\epsilon}{2\sqrt{\textbf{P}_{i^{\prime}}^{\texttt{T}}\textbf{P}_{i^{\prime}}+\epsilon}}$

By summing the above inequalities (19) and (21), we arrive at

$\displaystyle||\textbf{X}\widehat{\textbf{P}}-\textbf{F}||_{F}^{2}+\gamma\sum_{i=1}^{d}\sqrt{\widehat{\textbf{P}}_{i^{\prime}}^{\texttt{T}}\widehat{\textbf{P}}_{i^{\prime}}+\epsilon}$
(22)
$\displaystyle\leq||\textbf{X}\textbf{P}-\textbf{F}||_{F}^{2}+\gamma\sum_{i=1}^{d}\sqrt{\textbf{P}_{i^{\prime}}^{\texttt{T}}\textbf{P}_{i^{\prime}}+\epsilon}$

We can derive that

$\displaystyle||\textbf{X}\widehat{\textbf{P}}-\textbf{F}||_{F}^{2}+\gamma||\widehat{\textbf{P}}||_{2,1}\leq||\textbf{X}\textbf{P}-\textbf{F}||_{F}^{2}+\gamma||\textbf{P}||_{2,1}$
(23)

∎

The convergence of solving Algorithm 1 can be proven by the following theorem.

######  Theorem 3.

The iterative optimization in Algorithm 1 can monotonically decrease the
objective function of problem (LABEL:eq:overall) until convergence.

###### Proof.

As shown in Theorem 2, updating P will monotonically decrease the objective
function in problem (LABEL:eq:overall) ($t$ is number of iterations).

$\small\boldsymbol{\Omega}(\textbf{P}^{(t)},\textbf{F},\textbf{S},\textbf{W})\geq\boldsymbol{\Omega}(\textbf{P}^{(t+1)},\textbf{F},\textbf{S},\textbf{W})$
(24)

By fixing other variables and updating F, the objective function in Eq.(8) is
convex (The Hessian matrix of the Lagrangian function of Eq.(8) is positive
semidefinite Alavi (1991)). Therefore, we can obtain that

$\small\boldsymbol{\Omega}(\textbf{P},\textbf{F}^{(t)},\textbf{S},\textbf{W})\geq\boldsymbol{\Omega}(\textbf{P},\textbf{F}^{(t+1)},\textbf{S},\textbf{W})$
(25)

By fixing other variables and updating S, optimizing the
Eq.(LABEL:eq:updateS3) is a typical Quadratic programming problem. The Hessian
matrix of the Lagrangian function of problem (LABEL:eq:updateS3) is also
$\textbf{1}_{N}\textbf{1}_{N}^{\texttt{T}}$ that is positive semidefinite.
Therefore, we can obtain that

$\small\boldsymbol{\Omega}(\textbf{P},\textbf{F},\textbf{S}^{(t)},\textbf{W})\geq\boldsymbol{\Omega}(\textbf{P},\textbf{F},\textbf{S}^{(t+1)},\textbf{W})$
(26)

By fixing other variables and updating W, the Hessian matrix of Eq.(16) is
$\textbf{B}_{j}^{\texttt{T}}\textbf{B}_{j}$. It is positive semidefinite as
$\textbf{W}_{j}^{\texttt{T}}\textbf{B}_{j}^{\texttt{T}}\textbf{B}_{j}\textbf{W}_{j})=||\textbf{B}_{j}\textbf{W}_{j}||_{F}^{2}\geq
0$. Hence, the objective function for optimizing W is also convex. Then, we
arrive at

$\small\boldsymbol{\Omega}(\textbf{P},\textbf{F},\textbf{S},\textbf{W}^{(t)})\geq\boldsymbol{\Omega}(\textbf{P},\textbf{F},\textbf{S},\textbf{W}^{(t+1)})$
(27)

∎

Dataset | Feature dimension | LapScor | SPEC | MRSF | MVFS | AUMFS | AMFS | ACSL
---|---|---|---|---|---|---|---|---
| 100 | 0.1653 | 0.1930 | 0.1555 | 0.1362 | 0.1146 | 0.12681 | 0.1635
| 200 | 0.1730 | 0.1518 | 0.1754 | 0.1502 | 0.1799 | 0.1591 | 0.1875
MSRC-v1 | 300 | 0.1632 | 0.1637 | 0.1713 | 0.1358 | 0.1341 | 0.1609 | 0.1912
| 400 | 0.1815 | 0.2195 | 0.1787 | 0.1407 | 0.1716 | 0.1595 | 0.1905
| 500 | 0.1672 | 0.2027 | 0.1813 | 0.1798 | 0.1735 | 0.1670 | 0.2146
| 100 | 0.5967 | 0.4751 | 0.5927 | 0.5485 | 0.2738 | 0.2744 | 0.6403
| 200 | 0.6050 | 0.5413 | 0.5943 | 0.5538 | 0.3720 | 0.3718 | 0.6513
Handwritten Numeral | 300 | 0.5962 | 0.6068 | 0.6051 | 0.5584 | 0.4101 | 0.4013 | 0.5932
| 400 | 0.6014 | 0.6010 | 0.6015 | 0.5690 | 0.4436 | 0.4423 | 0.6025
| 500 | 0.6078 | 0.5799 | 0.5983 | 0.5974 | 0.4796 | 0.4831 | 0.5926
| 100 | 0.2690 | 0.2683 | 0.2610 | 0.2531 | 0.0121 | 0.1280 | 0.2705
| 200 | 0.2693 | 0.2688 | 0.2561 | 0.2604 | 0.0108 | 0.1474 | 0.2699
Youtube | 300 | 0.2627 | 0.2673 | 0.2677 | 0.2605 | 0.0152 | 0.1597 | 0.2570
| 400 | 0.2670 | 0.2647 | 0.2606 | 0.2736 | 0.0142 | 0.1817 | 0.2743
| 500 | 0.2641 | 0.2696 | 0.2635 | 0.2771 | 0.0123 | 0.1982 | 0.2736
| 100 | 0.2228 | 0.1933 | 0.2203 | 0.0595 | 0.3314 | 0.3267 | 0.4717
| 200 | 0.2174 | 0.2023 | 0.2021 | 0.0522 | 0.3801 | 0.3772 | 0.4860
Outdoor Scene | 300 | 0.2264 | 0.2414 | 0.2142 | 0.0562 | 0.4157 | 0.3975 | 0.4838
| 400 | 0.2358 | 0.2337 | 0.2211 | 0.0588 | 0.4152 | 0.4023 | 0.5111
| 500 | 0.2163 | 0.2316 | 0.2196 | 0.0769 | 0.4210 | 0.4159 | 0.5211
Table 2: NMI of different methods with different numbers of selected features
by using K-means for clustering.

##  4 Experiments

###  4.1 Experimental Datasets

1) MSRC-v1 Winn and Jojic (2005). The dataset contains 240 images in 8 class
as a whole. Following the setting in Grauman and Darrell (2006), we select 7
classes composed of tree, building, airplane, cow, face, car, bicycle and each
class has 30 images. We extract 5 visual features from each image: color
moment with dimension 48, GIST with 512 dimension, SIFT with dimension 1230,
CENTRIST feature with 210 dimension, and local binary pattern (LBP) with 256
dimension. 2) Handwritten Numeral van Breukelen et al. (1998). This dataset is
comprised of 2,000 data points from 0 to 9 digit classes. 6 features are used
to represent each digit. They are 76 dimensional Fourier coefficients of the
character shapes, 216 dimensional profile correlations, 64 dimensional
Karhunen-love coefficients, 240 dimensional pixel averages in $2\times 3$
windows, 47 dimensional Zernike moment and 6 dimensional morphological
features. 3) Youtube Liu et al. (2009). This real-world dataset is collected
from Youtube. It contains intended camera motion, variations of the object
scale, viewpoint, illumination and cluttered background. The dataset is
comprised of 1,596 video sequences in 11 actions. 4) Outdoor Scene Monadjemi
et al. (2002). The outdoor scene dataset contains 2,688 color images that
belong to 8 outdoor scene categories. 4 visual features are extracted from
each image: color moment with dimension 432, GIST with dimension 512, HOG with
dimension 256, and LBP with dimension 48.

###  4.2 Experimental Setting

Baselines. We compare ACSL with several representative unsupervised multi-view
feature selection methods on clustering performance. The compared methods
include, three single view feature selection approaches (Laplacian score
(LapScor) He et al. (2005), spectral feature selection (SPEC) Zhao and Liu
(2007) and minimum redundancy spectral feature selection (MRSF) Zhao et al.
(2010)), and three multi-view feature selection approach (adaptive multi-view
feature selection (AMFS) Wang et al. (2016), multi-view feature selection
(MVFS) Tang et al. (2013) and adaptive unsupervised multi-view feature
selection (AUMFS) Feng et al. (2013)). Evluation Metrics. We employ standard
metrics: clustering accuracy (ACC) and normalized mutual information (NMI),
for performance comparison. Each experiment is performed 50 times and the mean
results are reported. Parameter Setting. In implementation of all methods, the
neighbor graph is adopted to construct the initial affinity matrices. The
number of neighbors is set to 10 in all methods. In ACSL,
$\alpha,\beta,\gamma$ are chosen from $10^{-4}$ to $10^{4}$. The parameters in
all compared approaches are carefully adjusted to report the best results.

(a) $\alpha$ is fixed to $10^{4}$ (b) $\beta$ is fixed to $10^{-2}$ (c)
$\gamma$ is fixed to $10^{3}$

Figure 1: Clustering accuracy variations with parameters $\alpha,\beta,\gamma$
in Eq.(LABEL:eq:overall) on MSRC-V1.

(a) MSRC-V1 (b) Handwritten Numeral

Figure 2: Variations of the objective function value in Eq.(LABEL:eq:overall)
with the number of iterations on MSRC-V1 and Handwritten Numeral.

###  4.3 Comparison Results

The comparison results measured by ACC and NMI are reported in Table 1 and
Table 2, respectively. For these metrics, the higher value indicates the
better feature selection performance. Each metric penalizes or favors
different properties in feature selection. Hence, we report results on these
diverse measures to perform a comprehensive evaluation. The obtained results
demonstrate that ACSL can achieve superior or at least comparable performance
than the compared approaches. The promising performance of ACSL is attributed
to the reason that the proposed collaborative similarity structure learning
with proper neighbor assignment could positively facilitate the ultimate
multi-view feature selection.

###  4.4 Parameter and Convergence Experiment

We investigate the impact of parameters $\alpha$, $\beta$ and $\gamma$ in
Eq.(LABEL:eq:overall) on the performance of ACSL. Specifically, we vary one
parameter by fixing the others. Figure 1 presents the main results on MSRC-V1.
The obtained results clearly show that ACSL is robust to the involved three
parameters. Figure 2 records the variations of the objective function value in
Eq.(LABEL:eq:overall) with the number of iterations on MSRC-V1 and Handwritten
Numeral. We can easily observe that the convergence curves become stable
within about 5 iterations. The fast convergence ensures the optimization
efficiency of ACSL.

##  5 Conclusion

In this paper, we propose an adaptive collaborative similarity structure
learning for multi-view feature selection. Different from existing approaches,
we integrate collaborative similarity learning and feature selection into a
unified framework. The collaborative similarity structure with the ideal
neighbor assignment and similarity combination weights are adaptively learned
to positively facilitate the subsequent feature selection. Simultaneously, the
feature selection can supervise the similarity learning process to dynamically
construct the desirable similarity structure. Experiments show the superiority
of the proposed approach.

## References

  * Alavi [1991] Y. Alavi.  The laplacian spectrum of graphs.  Graph theory, combinatorics, and applications, 2(12):871–898, 1991\.
  * Cheng and Shen [2016] Zhiyong Cheng and Jialie Shen.  On very large scale test collection for landmark image search benchmarking.  Signal Processing, 124:13 – 26, 2016.
  * Cheng et al. [2016] Zhiyong Cheng, Jialie Shen, and Haiyan Miao.  The effects of multiple query evidences on social image retrieval.  Multimedia Systems, 22(4):509–523, 2016.
  * Feng et al. [2013] Yinfu Feng, Jun Xiao, Yueting Zhuang, and Xiaoming Liu.  Adaptive unsupervised multi-view feature selection for visual concept recognition.  In ACCV, 2013.
  * Grauman and Darrell [2006] K Grauman and T Darrell.  Unsupervised learning of categories from sets of partially matching image features.  In CVPR, pages 19–25, 2006.
  * He et al. [2005] Xiaofei He, Deng Cai, and Partha Niyogi.  Laplacian score for feature selection.  In NIPS, pages 507–514, 2005.
  * Huang et al. [2015] Jin Huang, Feiping Nie, and Heng Huang.  A new simplex sparse learning model to measure data similarity for clustering.  In IJCAI, pages 3569–3575, 2015.
  * K. [1949] Fan K.  On a theorem of weyl concerning eigenvalues of linear transformations.  Proc Natl Acad Sci U S A, 11(35):652–655, 1949.
  * Li and Liu [2017] Jundong Li and Huan Liu.  Challenges of feature selection for big data analytics.  IEEE Intelligent Systems, 32(2):9–15, 2017.
  * Li et al. [2017] Yun Li, Tao Li, and Huan Liu.  Recent advances in feature selection and its applications.  Knowledge and Information Systems, 53(3):551–577, 2017.
  * Liu et al. [2009] J. Liu, Yang Yang, and M. Shah.  Learning semantic visual vocabularies using diffusion distance.  In CVPR, pages 461–468, 2009.
  * Liu et al. [2016] An-An Liu, Wei-Zhi Nie, Yue Gao, and Yu-Ting Su.  Multi-modal clique-graph matching for view-based 3d model retrieval.  TIP, 25(5):2103–2116, 2016.
  * Liu et al. [2017] A. A. Liu, Y. T. Su, W. Z. Nie, and M. Kankanhalli.  Hierarchical clustering multi-task learning for joint human action grouping and recognition.  TPAMI, 39(1):102–114, 2017.
  * Monadjemi et al. [2002] A. Monadjemi, B. T. Thomas, and M. Mirmehdi.  Experiments on high resolution images towards outdoor scene classification.  Computer Vision Winter Workshop, 2002.
  * Nie et al. [2010] Feiping Nie, Heng Huang, Xiao Cai, and Chris H. Q. Ding.  Efficient and robust feature selection via joint l21-norms minimization.  In NIPS, pages 1813–1821, 2010.
  * Nie et al. [2014] Feiping Nie, Xiaoqian Wang, and Heng Huang.  Clustering and projected clustering with adaptive neighbors.  In KDD, pages 977–986, 2014.
  * Tang et al. [2013] Jiliang Tang, Xia Hu, Huiji Gao, and Huan Liu.  Unsupervised feature selection for multi-view data in social media.  In SDM, pages 270–278, 2013.
  * van Breukelen et al. [1998] M P. W van Breukelen, D M. J Tax, and J E den Hartog.  Handwritten digit recognition by combined classifiers,.  Kybernetika, 34:381–386, 1998.
  * Wang et al. [2016] Zhao Wang, Yinfu Feng, Tian Qi, Xiaosong Yang, and Jian J. Zhang.  Adaptive multi-view feature selection for human motion retrieval.  Signal Processing, 120(C):691 – 701, 2016.
  * Winn and Jojic [2005] J. Winn and N. Jojic.  Locus: learning object classes with unsupervised segmentation.  In ICCV, pages 756–763, 2005.
  * Zhao and Liu [2007] Zheng Zhao and Huan Liu.  Spectral feature selection for supervised and unsupervised learning.  In ICML, pages 1151–1157, 2007.
  * Zhao et al. [2010] Zheng Zhao, Lei Wang, and Huan Liu.  Efficient spectral feature selection with minimum redundancy.  In AAAI, 2010.
  * Zhu et al. [2015] Lei Zhu, Jialie Shen, Hai Jin, Ran Zheng, and Liang Xie.  Content-based visual landmark search via multimodal hypergraph learning.  TCYB, 45(12):2756–2769, 2015.
  * Zhu et al. [2016a] L. Zhu, J. Shen, L. Xie, and Z. Cheng.  Unsupervised topic hypergraph hashing for efficient mobile image retrieval.  TCYB, 47(11):3941–3954, 2016.
  * Zhu et al. [2016b] Lei Zhu, Jialie She, Xiaobai Liu, Liang Xie, and Liqiang Nie.  Learning compact visual representation with canonical views for robust mobile landmark search.  In IJCAI, pages 3959–3965, 2016.
  * Zhu et al. [2017a] L. Zhu, Z. Huang, X. Liu, X. He, J. Sun, and X. Zhou.  Discrete multimodal hashing with canonical views for robust mobile landmark search.  TMM, 19(9):2066–2079, 2017.
  * Zhu et al. [2017b] Lei Zhu, Jialie Shen, Liang Xie, and Zhiyong Cheng.  Unsupervised visual hashing with semantic assistant for content-based image retrieval.  TKDE, 29(2):472–486, 2017.