대규모 그래프 및 라벨 세트에서의 효율적이고 정확한 라벨 전파

Source

• Evernote/Inbox/Efficient and Accurate Label Propagation on Large Graphs and Label Sets.md

Summary

이 논문은 웹 기반 애플리케이션(검색, 추천, 광고 등)에서 희소하고 노이즈가 있는 라벨로부터 라벨 분포를 추론하는 문제를 다룹니다. 기존 Adsorption 알고리즘은 각 전파 단계 사이에 노드별 라벨 벡터의 재정규화(interleaved normalization)를 수행하여 모든 라벨 분포를 동기화해야 했고, 이는 표준 선형대수 방법(BiCGStab 등)의 사용을 방해했습니다. 본 연구는 재정규화를 전파 시작 전의 단일 사전 정규화(pre-normalization)로 대체하여, 선택적 라벨 계산(label slicing)과 대규모 행렬 해법(BiCGStab)을 사용할 수 있도록 개선했습니다. 이를 통해 더 큰 그래프와 라벨 세트를 처리할 수 있으며, 더 적은 전파 단계로 더 정확한 해를 얻을 수 있음을 웹 도메인 토픽 라벨링 실험을 통해 입증했습니다.

Key Points

• 기존 Adsorption 알고리즘의 단계별 재정규화(interleaved normalization)는 계산 병목과 선형대수 기법 적용을 제한함
• 단계별 재정규화를 전파 시작 전의 단일 사전 정규화(pre-normalization)로 대체하여 알고리즘 효율성 개선
• 개선된 방법은 선택적 라벨 계산(label slicing)과 안정화된 쌍접합 그라디언트 하강법(BiCGStab) 등 대규모 행렬 해법 사용 가능
• 더 큰 규모의 그래프와 라벨 세트를 처리하며, 기존 방법보다 적은 단계로 더 정확한 라벨 분포 추론 가능
• 웹 도메인 토픽 라벨링 실험을 통해 개선된 Adsorption 알고리즘의 유효성 검증

Related

• 대규모 다중 라벨 전파를 위한 효율적인 희소 그래프 구성

• 웹 데이터베이스 검색 결과 자동 주석 처리 (Automatic Annotation of Web Database Search Results)

• An Unsupervised Feature Selection Framework for Social Media Data

• Image Annotation in Presence of Noisy Labels

• Protecting Sensitive Labels in Social Network Data Anonymization

• Classifying with Confidence From Incomplete Test Data

• Interactive Image Tagging을 위한 인간 라벨링 최적화

• Transfer Learning In MIR: Sharing Learned Latent Representations For Music Audio Classification And Similarity

• 대규모 네트워크에서의 멀웨어 전파 모델

• 훈련 레이블 정제를 통한 텍스트 분류 정확도 향상

• Streaming Balanced Graph Partitioning for Random Graphs

• Efficient Inference and Structured Learning for Semantic Role Labeling

• Discriminative Segment Annotation in Weakly Labeled Video

• 이미지 주석 및 검색을 위한 Feature-Word-Topic 모델

• Feature Ensemble Plus Sample Selection: Domain Adaptation for Sentiment Classification

• Cross-Media Tag Transfer (CMTT): 이미지에서 비디오로 태그 지식 이전

• Regularized Latent Semantic Indexing (RLSI): 대규모 토픽 모델링을 위한 새로운 접근법

• Social Event Classification via Boosted Multimodal Supervised Latent Dirichlet Allocation

• 대규모 소셜 네트워크에서의 비용 효율적 바이럴 마케팅 (VirAds)

• 음성 피드백 고려)

• Cross-Domain Multi-Event Tracking via CO-PMHT

• Cross-Domain Feature Learning in Multimedia

• Similarity Preserving Feature Selection (SPFS)

• Transfer Joint Embedding for Cross-Domain NER

• TPCKT: Two-Level Progressive Cross-Media Knowledge Transfer

• Active Learning through Adaptive Heterogeneous Ensembling (AHE)

• K-RBMs를 이용한 다중 비선형 부분공간 학습

• 시간적 이미지 시퀀스를 위한 최적화된 만화 스토리텔링 시스템

• Classification of Homogeneous Data With Large Alphabets

• 대규모 저장소에서의 효율적인 비디오 스트림 모니터링 및 유사 중복 탐지

• Enlisting the Ghost: Modeling Empty Categories for Machine Translation

• 다중 특징 분석 및 시맨틱 컨텍스트 학습을 통한 이미지 분류

• Multiprotocol Label Switching (MPLS)

• YouTube 채널 분류를 위한 실용적 시스템

• Latent Mixture of Discriminative Experts (LMDE)

• Efficient Closed-Form Solution to Generalized Boundary Detection

• Supervised Robust Discrete Multimodal Hashing (SRDMH)

• Sparse Hashing (SH) for Fast Multimedia Search

• 대형 및 느슨한 커뮤니티의 압축 (Compacting Large and Loose Communities)

• Weakly Supervised Learning of Object Segmentations from Web-Scale Video

• A Top-Down Approach for Video Summarization

• 예측 모델링에 대한 실용서

• A Hamming Embedding Kernel with Informative Bag-of-Visual Words for Video Semantic Indexing

• All Smiles: 얼굴 표정 분석을 통한 자동 사진 보정

• 대규모 희소 네트워크의 커뮤니티 검출을 위한 의사 가능도 방법

• 이미지 기반 추천 시스템에서의 정서적 라벨링 (Affective Labeling)

• Meta-Learning 기반 Instance Selection을 위한 복잡도 측정 지표

• Query-Adaptive Image Search With Hash Codes

• 대용량 텍스트 컬렉션에서의 효율적 퍼지 검색

• Attribute-Augmented Semantic Hierarchy (A2SH) for CBIR

• Rolling Up Random Variables in Data Cubes

• Smooth Nonnegative Matrix Factorization for Unsupervised Audiovisual Document Structuring

• Unsupervised Spatial Event Detection in Targeted Domains with Applications to Civil Unrest Modeling

• 멀티미디어 마이크로블로그의 단어-이미지 연관성 모델링

• FSR: 안전한 인터도메인 라우팅을 위한 형식 분석 및 구현 툴킷

• Moment-Based Spectral Analysis of Large-Scale Networks Using Local Structural Information

• 정보 기하학을 통한 순수 고차 단어 연관성 마이닝

• 실시간 스토리 식별을 위한 스트리밍 환경에서의 밀집 부분 그래프 유지

• Patch-Based Image Warping for Content-Aware Retargeting

• 마이크로블로그 스트림의 소셜 이벤트 멀티미디어 요약

• When Amazon Meets Google: Product Visualization by Exploring Multiple Web Sources

• 실시간 트윗 검색을 위한 블룸 필터 체인(Bloom Filter Chains) 기반 후보 생성

• 대규모 Express 코드베이스를 위한 컨트롤러 구조화 방법

• Fast Near-Duplicate Image Detection Using Uniform Randomized Trees

• Information-Theoretic Outlier Detection for Large-Scale Categorical Data

• Data Enriched Linear Regression

• Reversible Data Hiding With Optimal Value Transfer

• Improved Domain Adaptation for Statistical Machine Translation

• 심층 피처 합성 (Deep Feature Synthesis) 개요

• Localized Tensor Completion (LTC) for Network Data Recovery

• Universal Dependency Annotation for Multilingual Parsing

• 멀티미디어 공유 웹사이트에서의 사회적 영향력 분석 및 적용

• 그래프 전파를 통한 개인화 비디오 추천