Я хочу получить список смежности с помощью pytorch geo. Есть ли какой-нибудь метод в pytorch для преобразования матрицы смежности, но оптимизированный, а не циклический?

Под отказом от использования циклов я предполагаю, что вы имеете в виду отказ от таких вложенных циклов:

import torch

def adjacency_matrix_to_list_with_loops(adj_matrix):
    num_nodes = adj_matrix.shape[0]
    adj_list = []
    for i in range(num_nodes):
        neighbors = []
        for j in range(num_nodes):
            if adj_matrix[i][j] == 1:
                neighbors.append(j)
        adj_list.append(neighbors)
    return adj_list

Если вы не хотите использовать дополнительную библиотеку, например networkx, вам нужно будет использовать хотя бы один цикл для перебора узлов матрицы.

Результатом torch.nonzero является тензор формы (n, 1) (где n — количество ненулевых элементов). Метод .squeeze() удаляет одноэлементное измерение, в результате чего получается тензор формы (n,).

import torch

def adjacency_matrix_to_list(adj_matrix):
    num_nodes = adj_matrix.shape[0]
    adj_list = []
    for i in range(num_nodes):
        # Find indices of non-zero elements in the i-th row
        neighbors = torch.nonzero(adj_matrix[i]).squeeze()
        adj_list.append(neighbors.tolist())
    return adj_list

Производительность этого метода будет зависеть от размера графа и разреженности матрицы смежности. Для очень больших графов решение networkx может оказаться более оптимизированным.

Вы не можете избежать использования цикла. В лучшем случае вы можете выполнить цикл на более низком уровне, который работает быстрее, чем стандартный Python.

Вы можете использовать torch.nonzero, чтобы найти ненулевые значения и перебрать их для построения выходного словаря.

import torch
from collections import defaultdict

# ie init random adjacency matrix
adj_matrix = (torch.rand(10,10)>0.8).float()

# grab nonzero values
nonzero_vals = torch.nonzero(adj_matrix)

# init output adjacency list
adj_list = defaultdict(set)

# add nonzero rows/cols to output dict 
for (row, col) in nonzero_vals.tolist():
    adj_list[row].update([col])
    if row != col:
        adj_list[col].update([row])
    
adj_list = {k:list(v) for k,v in adj_list.items()}

Нет прямого пути. Пожалуйста, используйте следующие методы.

Использование torch.tensor

Метод 1:

import torch
from scipy.sparse import csr_matrix
import torch
from numpy import nonzero
import networkx as nx
import matplotlib.pyplot as plt


adj_matrix = torch.tensor([[0, 1, 0],
                           [1, 0, 1],
                           [0, 1, 0]])

# Convert adjacency matrix to adjacency list
src_indices, dst_indices = adj_matrix.nonzero().unbind(-1)
"""
split_sizes : it tells us how many outgoing edges (neighbors) each node has in the graph.
minlength=adj_matrix.size(0) => the same length as the number of nodes in the graph.
torch.bincount: This function is used to count the number of occurrences 
of each element in the input tensor src_indices.

It counts the occurrences of each unique value in src_indices.
"""
split_sizes = torch.bincount(input=src_indices, minlength=adj_matrix.size(0))
"""
counts the occurrences of each unique value in src_indices
"""
adj_list = torch.split(dst_indices, split_sizes.tolist())

# Convert adjacency list tensors to regular lists
res = [x.tolist() for x in adj_list]
print(res)#[[1], [0, 2], [1]]

Метод 2:

from scipy.sparse import csr_matrix
from numpy import nonzero
import torch

adj_matrix = torch.tensor([[0, 1, 0],
                           [1, 0, 1],
                           [0, 1, 0]])

mask = (adj_matrix != 0)
source_indices  = mask.nonzero(as_tuple=True)[0]
print(source_indices )
destination_indices = mask.nonzero(as_tuple = True)[1]
print(destination_indices)
"""
It holds a tensor where each row represents an edge in the graph. 
The first element in each row is the source node index, 
and the second element is the destination node index.
dim=1: This argument specifies that the tensors should be stacked along 
the first dimension (columns in this case)
"""
edge_index = torch.stack(tensors = (source_indices,destination_indices), dim=1)
print(edge_index)
"""
tensor([[0, 1],
        [1, 0],
        [1, 2],
        [2, 1]])
"""
"""
.sum(dim=1): This performs a summation along dimension 1 (columns) for each row.
It counts the number of True values (non-zero elements) in each row.
adj_list  : Stores the number of outgoing edges (neighbors) for each node in the graph. 
"""
adj_list = (adj_matrix != 0 ).sum(dim=1).tolist()
print(adj_list)#[1, 2, 1]
adj_list = [[] for _ in adj_list]
print(adj_list)#[[], [], []]
"""
src: Represents the source node index (the node where the edge originates).
dst: Represents the destination node index (the node where the edge points to)
"""

# Scatter destination nodes into their corresponding lists
for i, (src, dst) in enumerate(edge_index):
    adj_list[src.item()].append(dst.item())  # Append destination node directly

print(adj_list)#[[1], [0, 2], [1]]
    

Без использования torch.tensor

import numpy as np
from scipy.sparse import csr_matrix 

# Example with sparse CSR matrix
sparse_adj_matrix = csr_matrix([[0, 1, 0],
                                [1, 0, 1],
                                [0, 1, 0]])

def adjacency_matrix_to_list(adj_matrix):
    if not isinstance(adj_matrix, csr_matrix):
    # Convert dense matrix to sparse CSR format for potential efficiency gains
     adj_matrix = csr_matrix(adj_matrix)

    num_nodes = adj_matrix.shape[0]
    print('num_nodes :', num_nodes) #3
    
    # Extract neighboring nodes using CSR matrix attributes
    split_indices = np.split(adj_matrix.indices,adj_matrix.indptr[1:-1] )
    print('split_indices :',split_indices) #split_indices : [array([1]), array([0, 2]), array([1])]

    # Convert split_indices to a list of lists
    adj_list = [arr.tolist() for arr in split_indices]

    return adj_list

adj_list = adjacency_matrix_to_list(sparse_adj_matrix)
print(adj_list)  # Output: [[1], [0, 2], [1]]

Или менее эффективный

adj_matrix = np.array([[0, 1, 0],
                       [1, 0, 1],
                       [0, 1, 0]])


adj_list = [list(np.where(row)[0]) for row in adj_matrix]

print(adj_list)  # Output: [[1], [0, 2], [1]]