I need to combine my affinity matrices for a project using the Affinity Aggregation Spectral Clustering (AASC) algorithm. I have implemented the AASC Algorithm 1 proposed in this paper (link below) to calculate the weight parameters of individual affinity matrices in Python code. However, I am having trouble updating the weighting parameters (vk values) in the loop that was suggested in the paper.

The paper can be found at here and a screenshot of the proposed algorithm in the paper here

In step 12 of the algorithm, I expected to obtain a scalar as the weight parameter for an individual affinity matrix (vk[k]). However, I always receive a vector instead. Unfortunately, I have not been able to identify the problem in any of the previous algorithm steps.

Below, you will find my used python code and a fictitious example of data and affinity matrices. The step numbers correspond to the steps in the paper/algorithm 1.

Can someone please tell me where I made a mistake in my code implementation or the mathematical misinterpretation? Thanks a lot.

import numpy as np
from scipy.linalg import eigh
from scipy.optimize import minimize

def affinity_aggregation_spectral_clustering(data, affinities, C):
# Step 1
    n = data.shape[0] 
    m = len(affinities) 
# Step 2
    vk = np.ones(m) / m  # vk = array([0.5, 0.5])
# Step 3
    max_iter = 100
    epsilon = 1e-5
    for _ in range(max_iter):
# Step 4
        W = np.zeros((n, n)) 
# Step 5
        for k, affinity in enumerate(affinities):
            W += np.dot(vk[k]**2, affinity) 
        D = np.diag(np.sum(W, axis=1)) 
# Step 6        
        L = D - W 
        _, eigenvectors = eigh(L, D)  
# Step 7
        indicators = eigenvectors[:, 1:C+1]  
# Step 8
# Step 9
        alpha_k = np.dot(np.dot(indicators.T, D), indicators) 
        beta_k = np.dot(np.dot(indicators.T, (D-W)), indicators) 
        gamma_k = beta_k/alpha_k 
# Step 10
        def objective_function(lambda_1, gammas, alphas): 
            numerator = np.sum([1 / ((gamma_k - lambda_1) * alpha_k) for gamma_k, alpha_k in zip(gammas, alphas)])
            denominator = np.sum([1 / ((gamma_k - lambda_1) ** 2 * alpha_k) for gamma_k, alpha_k in zip(gammas, alphas)])  
            expression_value = numerator ** 2 / denominator
            return abs(expression_value - 1)
    
        initial_guess = 0.01
        result = minimize(objective_function, initial_guess, args=(gamma_k, alpha_k))
        lambda_1 = result.x[0] 
# Step 11
        denominator = np.sum([1 / ((gamma_k - lambda_1) * alpha_k) for gamma_k, alpha_k in zip(gamma_k, alpha_k)])
        lambda_2 = 1 / denominator 
# Step 12
        vk = lambda_2 / ((gamma_k - lambda_1) * alpha_k) # vk = array([[-1.94517448e-13 -1.81958962e+05], [ 1.81959962e+05 -1.65511496e-13]]) which is not the correct format, see step 2
# Step 13       
        if np.linalg.norm(vk - np.ones(m) / m) < epsilon:
            break
# Step 14
    # I need only the weight values for my project. Therefore, I have not implemented this step.
# Step 15
    return vk

# -------------------------------------------------------
# Test example

data = np.array([[-1, -3], [1, 1], [0, 3], [6, 4], [4, -5]])
affinity_1 = np.array([[1, 0.5, 0.4, 0.1, 0.2],
                       [0.5, 1, 0.3, 0.2, 0.4],
                       [0.4, 0.3, 1, 0.5, 0.5],
                       [0.1, 0.2, 0.5, 1, 0.3],
                       [0.2, 0.4, 0.5, 0.3, 1]])
affinity_2 = np.array([[1, 0.2, 0.2, 0.9, 0.4],
                       [0.2, 1, 0.6, 0.4, 0.5],
                       [0.2, 0.6, 1, 0.1, 0.6],
                       [0.9, 0.4, 0.1, 1, 0.8], 
                       [0.4, 0.5, 0.6, 0.8, 1]])
affinities = [affinity_1, affinity_2]
C = 2 # number of clusters

vk = affinity_aggregation_spectral_clustering(data, affinities, C)
print("Weights vk:", vk)

0

There are 0 best solutions below