arXiv:2106.03476

Local Algorithms for Estimating Effective Resistance

Pan Peng, Daniel Lopatta, Yuichi Yoshida, Gramoz Goranci

제출 2021-06-07

원문 초록

Effective resistance is an important metric that measures the similarity of two vertices in a graph. It has found applications in graph clustering, recommendation systems and network reliability, among others. In spite of the importance of the effective resistances, we still lack efficient algorithms to exactly compute or approximate them on massive graphs. In this work, we design several \emph{local algorithms} for estimating effective resistances, which are algorithms that only read a small portion of the input while still having provable performance guarantees. To illustrate, our main algorithm approximates the effective resistance between any vertex pair $s,t$ with an arbitrarily small additive error $\varepsilon$ in time $O(\mathrm{poly}(\log n/\varepsilon))$, whenever the underlying graph has bounded mixing time. We perform an extensive empirical study on several benchmark datasets, validating the performance of our algorithms.

함께 살펴볼 논문

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

arXiv:2610.01533v1cs.AI공통 태그 Clustering, Recommendation Systems

흑백의 이분법을 넘어: 그래프 기반 시맨틱 ID(GrIS)를 통한 시맨틱 및 협업 신호의 균형

Neither Black nor White: Balancing Semantic and Collaborative Signals with Graph-Informed Semantic IDs (GrIS)

생성형 추천을 위한 시맨틱 ID(Semantic ID, SID)에 관한 기존 연구들은 SID 구축을 표현 학습(representation learning) 문제로 취급하여, 아이템을 양자화된 잠재 공간으로 인코딩하고 코드를 읽어내는 방식을 취합니다. 본 논문에서는 이러한 관점이 본질적이지 않다고 주장합니다. SID 구축은 본질적으로 재귀적 클러스터링(recursive clustering) 문제이며, 이렇게 정의하면 클러스터링할 자연스러운 대상은 노드가 시맨틱 콘텐츠를 담고 에지가 협업 신호(collaborative signal)를 전달하는 그래프가 됩니다. 즉, SID 할당은 계층적 그래프 분할(hierarchical graph partition)이 됩니다. 이러한 재구성을 통해 기존 접근 방식을 대체하기보다는 포괄하는 통합 프레임워크인 그래프 기반 시맨틱 ID(Graph-Informed Semantic IDs, GrIS)를 도출합니다. RQ-VAE 및 RQ-KMeans는 그래프가 비어 있는 특수한 경우로 환원되며, 이는 콘텐츠 전용 양자화가 지금까지 하나로 뭉쳐져 있던 두 축인 그래프 구축과 재귀적 분할 알고리즘으로 이루어진 더 큰 설계 공간의 한 단면에 불과함을 보여줍니다. 본 연구에서는 두 가지 대조적인 구현체를 탐색합니다. 하나는 미분 가능한 그래프 풀링(pooling)을 통해 계층적 할당을 수행하는 RecDMoN이고, 다른 하나는 그래프 인식 아이템 표현과 그래프 재구성 목적 함수를 통해 RQ-VAE를 확장하는 RQ-GAE입니다. 여러 실제 데이터셋에서 GrIS는 협업 필터링(CF) 인식 최신 기술(SOTA) 대비 일관되게 향상된 성능을 보여주며, Hit@10에서 최대 +52%의 성능 향상을 달성합니다. 그래프 구축과 분할이 명시적이고 개별적으로 구성 가능한 컴포넌트이기 때문에, 두 축 중 어느 한쪽의 개선점이라도 결합하여 체계적으로 평가할 수 있습니다.

arXiv:2607.20863v1cs.IR공통 태그 Clustering, Recommendation Systems

온라인 추천을 위한 확률적 잔차 학습

Probabilistic Residual Learning for Online Recommendations

현대 추천 시스템은 일반적으로 심층 학습(DL) 모델을 기반으로 하며, 밀집 인코더(dense encoder)가 사용자와 아이템의 표현(representation)을 학습한다. 그 결과 이러한 시스템은 기반 모델의 블랙박스 특성과 계산 복잡성으로 인해 추천 성능을 체계적으로 향상시키기 어려운 경우가 많다. 이 문제를 해결하기 위해, 우리는 Probabilistic Residual Learning(PRL)을 제안한다. 이는 실제값(ground-truth)과 기본 예측(base prediction) 사이의 잔차(residual)를 모델링하여 기존 시스템의 목표 지향적 정제(refinement)를 가능하게 하는 인과적 베이지안 추천 모델이다. 구체적으로 PRL은 (1) 국소적 잔차 모델링을 위해 사용자를 확률적으로 그룹화하고, (2) 사용자 및 아이템 표현에 영향을 미치는 도메인 수준 교란 변수(domain-level confounder)를 모델링하며, (3) do-calculus를 사용하여 교란 변수에 대한 클러스터별 잔차 예측을 집계한다. 실험 결과, 플러그앤플레이(plug-and-play) 방식의 PRL이 다양한 기본 심층 학습 추천 시스템과 호환되며 성능을 향상시키는 동시에 의미 있는 사용자 클러스터를 자동으로 발견함을 보여준다.

arXiv:2607.12246v1cs.LG공통 태그 Clustering, Recommendation Systems

Proximity Features: Airbnb의 개인정보 준수 콜드 스타트 개인화

Proximity Features: Privacy-Compliant Cold-Start Personalization at Airbnb

양면 마켓플레이스에서의 개인화는 사용자 수준 특징에 크게 의존하지만, 구매 빈도가 낮고 구매 전 고려가 긴 플랫폼의 경우 유료 및 자연(organic) 채널 모두에 걸쳐 효과적인 추천을 위한 충분한 이력을 갖추지 못한 사용자가 상당수 존재한다. Airbnb에서는 상당 비율의 검색 요청이 로그아웃 상태이거나 첫 방문 사용자로부터 발생하며, 이 문제는 유료 채널 랜딩 페이지에서 특히 두드러져 전체 트래픽의 상당 부분에서 기존 사용자 수준 특징을 사용할 수 없게 한다. 개인정보 규제와 서드파티 쿠키에 대한 점점 강화되는 제한은 비필수 사용 사례에 대한 식별자 기반 추적을 더욱 제한한다. 본 논문은 geo-IP 데이터와 적응형 클러스터링 알고리즘을 사용하여 지리적 근접성에 따라 사용자를 그룹화하고, 추론 시 지속적인 개별 식별자 없이도 약 1,000명의 인근 사용자 그룹에 대한 집계된 사용자 수준 신호를 생성하는 개인정보 준수 특징 시스템인 Proximity Features(근접 특징)를 제안한다. 개인정보 보호는 설계상 보장된다. 파이프라인은 동의 기반 프라이버시 통제 내에서 동의된 집계 데이터만으로 동작한다. 이 시스템은 Airbnb 프로덕션에 배포되어 마케팅 랜딩 페이지, 목적지 추천 등 여러 접점에 서비스되고 있으며, engagement 이메일 통합이 진행 중이다. 온라인 A/B 실험은 예약 건수에서 통계적으로 유의미한 향상을 보여주며, 이력이 없거나 오래된 사용자에서 가장 큰 이득이 관찰되었다.

토론

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