Clustering and Community Detection in Directed Networks: A Survey
원문 초록
Networks (or graphs) appear as dominant structures in diverse domains, including sociology, biology, neuroscience and computer science. In most of the aforementioned cases graphs are directed - in the sense that there is directionality on the edges, making the semantics of the edges non symmetric. An interesting feature that real networks present is the clustering or community structure property, under which the graph topology is organized into modules commonly called communities or clusters. The essence here is that nodes of the same community are highly similar while on the contrary, nodes across communities present low similarity. Revealing the underlying community structure of directed complex networks has become a crucial and interdisciplinary topic with a plethora of applications. Therefore, naturally there is a recent wealth of research production in the area of mining directed graphs - with clustering being the primary method and tool for community detection and evaluation. The goal of this paper is to offer an in-depth review of the methods presented so far for clustering directed networks along with the relevant necessary methodological background and also related applications. The survey commences by offering a concise review of the fundamental concepts and methodological base on which graph clustering algorithms capitalize on. Then we present the relevant work along two orthogonal classifications. The first one is mostly concerned with the methodological principles of the clustering algorithms, while the second one approaches the methods from the viewpoint regarding the properties of a good cluster in a directed network. Further, we present methods and metrics for evaluating graph clustering results, demonstrate interesting application domains and provide promising future research directions.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
고정된 확산 없는 고정점: 수렴하는 테스트 시점 연산을 위한 암시적 신경 층
Fixed Points Without Fixed Diffusion: Implicit Neural Sheaves for Convergent Test-Time Computation
암시적 그래프 신경망(IGNN)은 노드 표현을 그래프 신경 연산자의 고정점(fixed point)으로 정의하여 실질적으로 무한한 깊이의 전파, 반복(iteration) 독립적인 매개변수화, 유연한 테스트 시점 연산(test-time computation)을 가능하게 합니다. 그러나 이러한 이점은 평형점이 유일하며 고정점 반복을 통해 도달할 수 있는지 여부에 달려 있습니다. 기존의 구조들은 이러한 보장을 얻기 위해 순환 업데이트에 제약을 가하는 경우가 많아 평형 상태에서 사용 가능한 변환을 제한했습니다. 이는 핵심적인 질문을 제기합니다: IGNN이 평형 정식화의 고유한 강점을 유지하면서 더 풍부한 엣지 의존적 변환을 통해 표현력을 얻을 수 있을까요? 본 논문에서는 적응형 신경 층(neural-sheaf) 전파를 갖춘 준동차(subhomogeneous) 심층 평형 아키텍처인 SheafDEQ를 소개합니다. 학습된 행렬 값 층 제한 사상(sheaf restriction map)은 이웃한 표현들을 정렬, 혼합 또는 반전시킬 수 있습니다. 완만한 정칙성 조건 하에서, SheafDEQ가 임의의 양의 초기 상태로부터 고정점 반복을 통해 전역적으로 도달 가능한 유일한 평형점을 가짐을 증명합니다. 나아가 축약성(contractivity)은 유계된 통신 지연(staleness) 하에서도 수렴을 보장합니다. 본 연구는 반복적인 비국소적 집계가 필요한 분산 추론(inference) 태스크와 연결 재구성이 점차 커뮤니티 간 상호작용을 선호하게 되는 커뮤니티 탐지 태스크에서 SheafDEQ를 평가합니다. SheafDEQ는 Sums, MNIST Terrain, Coordinates 태스크 및 연결성이 점차 이종친화적(heterophilic)으로 변하는 커뮤니티 탐지에서 암시적 베이스라인보다 향상된 성능을 보입니다. 또한 SheafDEQ는 평형 보장이 없는 순환 모델들과 비교해도 경쟁력을 유지합니다. 연속 반복 진단 결과 유한 구간(finite-horizon) 대조군과 달리 100회 반복까지 잔차가 감소하고 테스트 정확도가 유지됨을 확인하였으며, 지연 업데이트 실험에서는 유계된 통신 지연에 대해 낮은 민감도를 나타냈습니다.
AI 통합 과학 탐구: 과학 교육을 위한 실천 중심 비전
AI-Integrated Scientific Inquiry: A Practice-Centered Vision for Science Education
인공지능(AI)은 과학 탐구의 일부가 되었다. 과학자들은 AI를 사용해 현상을 관찰·측정하고, 데이터에서 패턴을 식별하며, 모델을 구축한다. AI가 과학 탐구에 들어오면서 과학 교육과의 연관성도 커진다. 학생들은 AI가 과학적 실천을 어떻게 바꾸고 있는지 배워야 하며, 이상적으로는 AI 통합 과학 탐구에 직접 참여하면서 배워야 한다. 이러한 교수를 어떻게 설계할지—독립 주제로 가르치기보다는 진정한 과학적 실천에 기반하여—는 여전히 열린 질문이다. 우리의 비전(본 논문에서 설명함)에서 AI는 학생들이 차세대 과학 기준(Next Generation Science Standards)이 설명하는 과학적 실천 안에서 사용하는 일련의 과학적 도구로 취급된다. 각 도구는 진정한 과학적 도구이되 교육적으로 범위가 설정된다. 즉, 핵심 과학적 기능은 보존하면서 조작은 단순화된다. 이 접근법에는 두 가지 목표가 있다. 학생들을 진정한 과학 탐구에 참여시키는 것, 그리고 과학에서 AI가 어떻게 사용되는지와 어디서 오해를 불러일킬 수 있는지에 대한 이해를 형성하는 것(학문 분야 기반 AI 리터러시, DAIL)이다. 본 논문에서는 탐구의 조사 핵심—관찰, 분석, 모델링—에 초점을 맞추고, 각각에 대해 하나의 대표적인 AI 도구를 설명한다. 관찰에는 컴퓨터 비전(computer vision), 분석에는 클러스터링(clustering), 모델링에는 생성 모델링(generative modeling)이다. 우리는 과학 교육의 모든 AI 도구는 AI 도구 자체에 대한 비판적 평가를 촉진하는 별도의 성찰 지점(reflection point)을 갖춰야 한다고 주장한다. 마지막으로, 단일 실천이 아니라 전체 탐구 과정에 걸쳐 작동하는 에이전트 AI(agentic AI)를 어떻게 표현할 수 있는지 설명하며, 학생들은 에이전트 AI에 의존하기 전에 과학 탐구와 AI 도구에 대한 기초적 이해를 먼저 형성해야 한다고 주장한다.
Grassmann 다양체 상의 정규화 최적화: 이론, 알고리즘 및 응용
Regularized Optimization on Grassmann Manifold: Theory, Algorithm and Applications
스펙트럴 방법은 커뮤니티 탐지, 클러스터링, 그래프 학습에서 가장 널리 사용되는 기법 중 하나이다. 그러나 그 성능은 근본적인 스펙트럴 부분공간의 정확한 추정에 크게 의존하며, 노이즈, 이상치, 또는 모델 교란이 존재할 경우 상당히 악화될 수 있다. 이 한계를 해결하기 위해, 우리는 rank-$K$ 투영 행렬의 강건한 추정을 위한 정규화 투영 행렬 근사(Regularized Projection Matrix Approximation, RPMA) 프레임워크를 제안한다. RPMA는 정규화 항을 통합하여 고전적인 스펙트럴 투영을 확장하며, 더 강건하고 희소하며 해석 가능한 투영 추정치를 생성한다. 우리는 제안된 모델을 rank-$K$ 투영 행렬의 다양체 상의 최적화 문제로 공식화하고, Grassmann 다양체와의 기하학적 동등성을 활용한다. 이 다양체 특성화를 바탕으로, 1차 및 2차 최적성 조건을 유도하고, 정규화된 선행 고유공간의 국소 안정성을 확립하며, 충분히 작은 정규화 하에서 임계점 경관의 안정성을 특성화한다. 결과적인 비볼록 최적화 문제를 효율적으로 풀기 위해, 역추적 선 탐색(backtracking line search)을 갖춘 Riemann 그래디언트 투영 알고리즘과, 반복적인 고유값 분해를 피하는 보다 효율적인 Cayley--Sherman--Morrison--Woodbury(Cayley--SMW) 그래디언트 방법을 개발한다. 합성 및 실제 데이터셋에 대한 광범위한 실험은 RPMA가 투영 행렬의 복원 정확도를 크게 향상시키며, 노이즈가 있는 환경에서 커뮤니티 탐지 및 클러스터링을 위한 기존 스펙트럴 투영 방법보다 일관되게 우수한 성능을 보임을 입증한다.
클러스터형 엣지 지능: 엣지 컴퓨팅과 AI의 단순한 수렴을 넘어
Clustered Edge Intelligence: Beyond Just Convergence of Edge Computing and AI
우리는 정보 시대에서 지능 시대로 나아가고 있다. 10년, 혹은 그보다 짧은 기간 안에 데이터는 더 이상 금(gold)이 아니라, 데이터와 네트워크 엣지(edge)에서 보유한 정보로부터 파생된 지능이 그 역할을 대신할 것이다. 기존 엣지 지능(Edge Intelligence) 연구는 주로 두 방향에 집중한다: 엣지 자원 관리를 위한 AI 활용, 그리고 엣지 디바이스에 경량 AI 모델 배포. 그러나 기존 엣지 컴퓨팅 연구에는 파생된 지능을 1급(first-class)이며 독립적으로 관리 가능한 개체로 취급하고, 이를 기술(describe), 발견(discover), 관찰(observe), 공유(share), 재사용(reuse), 이기종(heterogeneous) 엣지 디바이스와 애플리케이션 간에 동적으로 클러스터링할 수 있는 지능 중심(intelligence-centric) 프레임워크가 부재하다. 이러한 연구 공백을 해소하기 위해, 우리는 비전형 지능 중심 접근법인 클러스터형 엣지 지능(Clustered Edge Intelligence, CEI)을 제안한다. CEI의 목표는 지능을 공유 가능하고 재사용 가능한 1급 개체로 만들어, 분산된 엣지-클라우드 연속체(edge-cloud continuum) 전반에 걸쳐 독립적으로 표현, 발견, 관찰, 교환, 관리할 수 있게 하는 것이다. 우리는 3층 CEI 아키텍처를 제시하고, 지능 인벤토리(intelligence inventories), 의미론적 지식 표현(semantic knowledge representation), 통신(communication), 발견 가능성(discoverability), 관찰 가능성(observability), 수명주기 자동화(lifecycle automation), 클러스터링 메커니즘(clustering mechanisms), 마켓플레이스(marketplaces), 상호운용성(interoperability), 표준화(standardization) 등을 포함한 지원 기술과 연구 차원을 검토한다.
Simultaneous Linear Multi-view Attributed Graph Representation Learning and Clustering
Efficient graph convolution for joint node representation learning and clustering
토론
이 논문과 연결된 포럼 글이 아직 없습니다.