인접행렬 (Adjacency Matrix)
쉽게 풀면
친구 관계를 떠올려봅시다. 사람 5명이 있고 누가 누구와 친구인지를 표로 정리한다면, 가로줄과 세로줄에 모두 같은 5명의 이름을 적고, 두 사람이 친구면 1, 아니면 0을 칸에 적어 넣을 수 있습니다. 이렇게 만든 표(행렬)가 바로 인접행렬입니다. 노드(사람, 도시, 웹페이지 등)와 그 사이의 연결(친구 관계, 도로, 링크 등)로 이루어진 구조를 "그래프"라고 하는데, 인접행렬은 이 그래프의 연결 정보를 컴퓨터가 계산하기 쉬운 숫자 표 형태로 바꿔주는 역할을 합니다. 단순히 연결 여부만이 아니라 거리나 강도 같은 가중치를 숫자로 넣을 수도 있습니다.
왜 중요한가
많은 실세계 데이터는 개체와 개체 사이의 관계로 자연스럽게 표현됩니다. 소셜 네트워크의 팔로우 관계, 분자 구조의 원자 간 결합, 교통망의 도로 연결, 추천 시스템의 사용자-상품 상호작용이 모두 그래프 구조를 이룹니다. 인접행렬은 이런 그래프를 행렬 연산이 가능한 형태로 바꿔주기 때문에, 그래프 신경망(GNN)이나 스펙트럴 분석처럼 행렬 대수를 활용하는 방법론의 출발점이 됩니다. 그래서 그래프를 다루는 논문에서는 데이터를 어떻게 행렬로 구성했는지가 방법론 설명의 기본 전제로 자주 등장합니다.
논문에서는 이렇게 쓰입니다
이 문장은 연구 대상인 관계형 데이터(팔로우 관계)를 그래프로 보고, 그 연결 구조를 행렬 형태로 정리해 분석 모델에 넣었다는 것을 설명하고 있습니다.
생물정보학 분야의 예로, 단백질 간 상호작용이라는 생물학적 관계를 그래프로 모델링한 뒤 인접행렬을 이용해 수학적 군집화 기법을 적용한 사례입니다.
교통·물류 분야에서는 물리적 공간의 연결 구조(도로망)를 인접행렬로 표현해 경로 탐색 알고리즘을 실험하는 데 활용하는 경우가 많습니다.
조금 더 깊게 보면
인접행렬을 조금 더 깊이 들여다보면, 대각선 원소를 어떻게 처리하는지(자기 자신과의 연결, 즉 셀프 루프를 포함할지), 방향성이 있는 그래프인지 무방향 그래프인지에 따라 행렬이 대칭인지 아닌지가 달라진다는 점을 알아둘 필요가 있습니다. 또한 그래프 신경망 논문에서는 인접행렬을 그대로 쓰기보다 차수(degree) 정보로 정규화한 형태를 사용하는 경우가 많고, 이 정규화된 행렬은 라플라시안 행렬 같은 관련 개념과도 연결됩니다. 대규모 그래프에서는 대부분의 원소가 0인 희소행렬 형태로 저장·연산하는 것이 일반적이므로, 논문에서 어떤 저장 방식과 정규화 방식을 택했는지를 함께 확인하면 방법론을 더 정확히 이해할 수 있습니다.
주의할 점
노드 수가 매우 많아지면 인접행렬의 크기도 노드 수의 제곱만큼 커지기 때문에, 실제 연결이 적은(희소한) 대규모 그래프에서는 메모리를 많이 낭비할 수 있습니다. 이런 경우 논문에서는 인접행렬 대신 연결 목록 같은 더 효율적인 방식으로 그래프를 저장하기도 하므로, 어떤 표현 방식을 썼는지도 함께 살펴보는 것이 좋습니다.