arXiv:2102.03609

Understanding Higher-order Structures in Evolving Graphs: A Simplicial Complex based Kernel Estimation Approach

Manohar Kaul, Masaaki Imaizumi

제출 2021-02-06

원문 초록

Dynamic graphs are rife with higher-order interactions, such as co-authorship relationships and protein-protein interactions in biological networks, that naturally arise between more than two nodes at once. In spite of the ubiquitous presence of such higher-order interactions, limited attention has been paid to the higher-order counterpart of the popular pairwise link prediction problem. Existing higher-order structure prediction methods are mostly based on heuristic feature extraction procedures, which work well in practice but lack theoretical guarantees. Such heuristics are primarily focused on predicting links in a static snapshot of the graph. Moreover, these heuristic-based methods fail to effectively utilize and benefit from the knowledge of latent substructures already present within the higher-order structures. In this paper, we overcome these obstacles by capturing higher-order interactions succinctly as \textit{simplices}, model their neighborhood by face-vectors, and develop a nonparametric kernel estimator for simplices that views the evolving graph from the perspective of a time process (i.e., a sequence of graph snapshots). Our method substantially outperforms several baseline higher-order prediction methods. As a theoretical achievement, we prove the consistency and asymptotic normality in terms of the Wasserstein distance of our estimator using Stein's method.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2412.05641v2cs.LG공통 태그 Link Prediction공식 코드 · Papers with Code

하이퍼그래프 신경망을 활용한 하이퍼에지 이상 탐지

Hyperedge Anomaly Detection with Hypergraph Neural Network

하이퍼그래프(hypergraph)는 데이터 개체 간의 고차(higher-order) 관계를 모델링할 수 있게 해주는 데이터 구조입니다. 기존의 그래프 구조 데이터는 쌍별(pairwise) 관계만을 표현할 수 있는 반면, 하이퍼그래프는 여러 개체를 제한 없이 연결할 수 있어 다양한 실제 응용 분야에서 필수적입니다. 노드(node) 분류, 링크 예측 등 다양한 문제 설정에 대해 하이퍼그래프 학습 알고리즘이 활발히 연구되어 왔습니다. 그러나 하이퍼그래프에서의 이상 탐지(anomaly detection)에 대한 연구는 훨씬 덜 진행되었습니다. 이상 탐지는 일반적인 패턴에서 벗어나는 이벤트를 식별하며, 하이퍼그래프에 적용하여 비정상적인 고차 관계를 탐지할 수 있습니다. 본 연구에서는 하이퍼그래프 내 이상 관계를 식별하기 위한 엔드투엔드(end-to-end) 하이퍼그래프 신경망 기반 모델(model)을 제안합니다. 제안된 알고리즘은 레이블이 지정된 데이터 없이도 비지도 방식으로 작동합니다. 여러 실제 데이터셋에 대한 광범위한 실험을 통해 이상 하이퍼에지를 탐지하는 데 있어 우리 모델의 효과성을 입증합니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.