<jupyter_start><jupyter_text>page 66, kernel on Laplacian and normalised adjacency matrix<jupyter_code>import matplotlib.pyplot as plt
import networkx as nx
import numpy as np

import scipy as sc

G = nx.karate_club_graph()
nx.draw(G, with_labels=True)
A = nx.adjacency_matrix(G)
A = A.toarray()
A<jupyter_output><empty_output><jupyter_text>Normalising Matrix<jupyter_code># degree matrix
D = np.diag(list(dict(G.degree()).values()))
D_neg_half = sc.linalg.fractional_matrix_power(D, -1/2)
D
# normalised adjacency matrix
N = D_neg_half @ A @ D_neg_half
N
# laplacian matrix

# L = nx.linalg.laplacianmatrix.laplacian_matrix(G).toarray()
L = D - A
L
# normalised laplacian matrix

Z = D_neg_half @ L @ D_neg_half
# Z = nx.linalg.normalized_laplacian_matrix(G).toarray()
Z
"""
matrix power
check validity of spectral transformation
"""

def testMatrixPower(X, k=4):

    # eigenvalue decomposition. Don't use SVD, it doesn't return similar U and U.T
    V, U = np.linalg.eig(X)

    # transform
    Xk_pred = U @ np.diag(V ** k) @ U.T
    Xk_pred = Xk_pred.real

    # number of paths 2nd neighbors
    Xk = np.linalg.matrix_power(X, k)

    return np.round(Xk - Xk_pred).sum()

testMatrixPower(A), testMatrixPower(N), testMatrixPower(L), testMatrixPower(Z)<jupyter_output><empty_output><jupyter_text>Kernelunderstand eigenvalue decomposition of N, L and Z<jupyter_code>def testExponentialKernel(X, alpha=0.2):

    # eigenvalue decomposition. Don't use SVD, it doesn't return similar U and U.T
    V, U = np.linalg.eig(X)

    # transform
    def transform(V, alpha=1):
        return np.array([np.exp(alpha*lamb) for lamb in V])

    expX_pred = U @ np.diag(transform(V, alpha)) @ U.T
    expX_pred = expX_pred.real

    # actual
    expX = sc.linalg.expm(X * alpha)

    return expX, expX_pred, np.round(expX - expX_pred).sum()

_, _, diff = testExponentialKernel(A)
print(diff)

# normalised exponential kernel 
expN, expN_pred, diff = testExponentialKernel(N)
print(diff)

# heat diffusion
_, heatPred, diff = testExponentialKernel(L, -0.2)
print(diff)

# normalized heat diffusion
_, normHeatPred, diff = testExponentialKernel(Z, -0.2)
print(diff)

def testNeumannKernel(X, alpha=0.01):

    # neumann inverse
    I = np.eye(X.shape[0])
    neu = np.linalg.inv(I - X * alpha)

    # eigenvalue decomposition. Don't use SVD, it doesn't return similar U and U.T
    V, U = np.linalg.eig(X)

    # transform
    def transform(V, alpha):
        return np.array([1 / (1-(alpha*lamb)) for lamb in V])

    neu_pred = U @ np.diag(transform(V, alpha)) @ U.T
    neu_pred = neu_pred.real

    return neu, neu_pred, np.round(neu - neu_pred).sum()

# normalized neumann kernel
neuN, neuN_pred, diff = testExponentialKernel(N)
print(diff)

# regularized laplacian kernel
_, _, diff = testExponentialKernel(L, alpha=-0.01)
print(diff)

# normalized regularized laplacian kernel
_, _, diff = testExponentialKernel(Z, alpha=-0.01)
print(diff)

def testPathCountingKernel(X):

    # eigenvalue decomposition. Don't use SVD, it doesn't return similar U and U.T
    V, U = np.linalg.eig(X)

    # transform
    V_ = V + V**2 + V**3 + V**4
    PC_pred = U @ np.diag(V_) @ U.T
    PC_pred = PC_pred.real

    # original
    PC = X + np.linalg.matrix_power(X, 2) + np.linalg.matrix_power(X, 3) + np.linalg.matrix_power(X, 4)

    return PC, PC_pred, np.round(PC - PC_pred).sum()

# normalized path counting (finite sum)
_, _, diff = testPathCountingKernel(N)
print(diff)
# Moore-Penrose pseudoinverse
def testPseudoinverseKernel(X):
    # moore-penrose pseudoinverse
    pi = np.linalg.pinv(X)

    # eigenvalue decomposition. Don't use SVD, it doesn't return similar U and U.T
    V, U = np.linalg.eig(X)

    # transform
    def transform(V):
        # add 1e-10 instead of 0 as minimum because of rounding error
        return np.array([1/lamb if lamb > 1e-10 else 0 for lamb in V])

    pi_pred = U @ np.diag(transform(V)) @ U.T
    pi_pred = pi_pred.real

    return pi, pi_pred, np.round(pi - pi_pred).sum()

# commute-time kernel
pi, pred, diff = testPseudoinverseKernel(L)
print(diff)

# normalized commute-time kernel
pi, pred, diff = testPseudoinverseKernel(Z)
print(diff)

# generalized laplacian kernel (finite-power)
def testGeneralizedLaplacianKernel(X):

    # eigenvalue decomposition. Don't use SVD, it doesn't return similar U and U.T
    V, U = np.linalg.eig(X)

    # transform
    V_ = V + V**2 + V**3 + V**4
    # inverse of sum
    def transform(V):
        # add 1e-10 instead of 0 as minimum because of rounding error
        return np.array([1/lamb if lamb > 1e-10 else 0 for lamb in V])
    V_ = transform(V_)
    PC_pred = U @ np.diag(V_) @ U.T
    PC_pred = PC_pred.real

    # original
    PC = X + np.linalg.matrix_power(X, 2) + np.linalg.matrix_power(X, 3) + np.linalg.matrix_power(X, 4)
    # pseudoinverse of sum
    PC = np.linalg.pinv(PC)

    return PC, PC_pred, np.round(PC - PC_pred).sum()

# normalized path counting (finite sum)
PC, PC_pred, diff = testGeneralizedLaplacianKernel(L)
diff
PC, PC_pred
# generalized normalized laplacian kernel

def testGeneralizedNormLaplacianKernel(Z):

    # eigenvalue decomposition. Don't use SVD, it doesn't return similar U and U.T
    V, U = np.linalg.eig(Z)

    # transform
    V_ = (1-V) + (1-V)**2 + (1-V)**3 + (1-V)**4
    PC_pred = U @ np.diag(V_) @ U.T
    PC_pred = PC_pred.real

    # original
    I = np.eye(Z.shape[0])
    PC = (I-Z) + np.linalg.matrix_power((I-Z), 2) + np.linalg.matrix_power((I-Z), 3) + np.linalg.matrix_power((I-Z), 4)

    return PC, PC_pred, np.round(PC - PC_pred).sum()

# normalized path counting (finite sum)
ori, pred, diff = testGeneralizedNormLaplacianKernel(Z)
print(diff)<jupyter_output>0.0
{'fraction_non_alphanumeric': 0.12552668539325842, 'fraction_numerical': 0.011938202247191011, 'mean_word_length': 3.5869565217391304, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 14, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '351200', 'license': 'BSD-3-Clause', 'n_tokens_mistral': 2241, 'n_tokens_neox': 2100, 'n_words': 541, 'path': 'edward_exp/normalised_spectral_transformation.ipynb', 'repo_name': 'edwardelson/networkx', 'size': '5696'}