論文の概要: Beyond Homophily: Community Search on Heterophilic Graphs

• arxiv url: http://arxiv.org/abs/2601.01703v1
• Date: Mon, 05 Jan 2026 00:44:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-06 16:25:22.657952
• Title: Beyond Homophily: Community Search on Heterophilic Graphs
• Title（参考訳）: Beyond Homophily: 好ましくないグラフのコミュニティ検索
• Authors: Qing Sima, Xiaoyang Wang, Wenjie Zhang,
• Abstract要約: コミュニティ検索は、あるクエリに最も関連性の高い、洗練されたノードのセットを特定することを目的としている。 ホモ親和グラフとは異なり、多くの実世界のネットワークは異種ノードを主に接続する異種ネットワークである。 i)マルチホップ信号とマルチ周波数信号を分離し、スムーズな(ホモ親和性)とコントラストな(ヘテロ親和性)の関係を捕捉するAdaptCS、(ii)主要な計算ボトルネックを除去するメモリ効率の低い低ランク最適化、(iii)オンライン検索をガイドするAdaptive Community Score(ACS)の3つの主要な設計を特徴とする統合フレームワークを提案する。
• 参考スコア（独自算出の注目度）: 9.691955358608537
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Community search aims to identify a refined set of nodes that are most relevant to a given query, supporting tasks ranging from fraud detection to recommendation. Unlike homophilic graphs, many real-world networks are heterophilic, where edges predominantly connect dissimilar nodes. Therefore, structural signals that once reflected smooth, low-frequency similarity now appear as sharp, high-frequency contrasts. However, both classical algorithms (e.g., k-core, k-truss) and recent ML-based models struggle to achieve effective community search on heterophilic graphs, where edge signs or semantics are generally unknown. Algorithm-based methods often return communities with mixed class labels, while GNNs, built on homophily, smooth away meaningful signals and blur community boundaries. Therefore, we propose Adaptive Community Search (AdaptCS), a unified framework featuring three key designs: (i) an AdaptCS Encoder that disentangles multi-hop and multi-frequency signals, enabling the model to capture both smooth (homophilic) and contrastive (heterophilic) relations; (ii) a memory-efficient low-rank optimization that removes the main computational bottleneck and ensures model scalability; and (iii) an Adaptive Community Score (ACS) that guides online search by balancing embedding similarity and topological relations. Extensive experiments on both heterophilic and homophilic benchmarks demonstrate that AdaptCS outperforms the best-performing baseline by an average of 11% in F1-score, retains robustness across heterophily levels, and achieves up to 2 orders of magnitude speedup.
• Abstract（参考訳）: コミュニティ検索は、不正検出からレコメンデーションまでのタスクをサポートする、特定のクエリに最も関連性の高い、洗練されたノードセットを特定することを目的としている。 ホモ親和グラフとは異なり、多くの実世界のネットワークは異種ノードを主に接続するヘテロ親和性を持つ。 したがって、かつて滑らかで低周波の類似性を反映した構造信号は、今では鋭く高周波のコントラストとして現れる。 しかし、古典的アルゴリズム(例えば、k-core、k-truss)と最近のMLベースのモデルの両方は、エッジ記号やセマンティクスが一般に不明なヘテロ親和性グラフ上の効果的なコミュニティ探索を達成するのに苦労している。 アルゴリズムベースの手法は、しばしば混合クラスラベルを持つコミュニティを返却するが、GNNは、ホモフィリーでスムーズな意味のある信号に基づいて構築され、コミュニティの境界を曖昧にしている。 そこで我々は,Adaptive Community Search (AdaptCS)を提案する。 (i)マルチホップ信号とマルチ周波数信号とをアンタングルするAdaptCSエンコーダにより、モデルがスムーズ(ホモフィル性)とコントラスト(ヘテロフィル性)の両方を捕捉することができる。 (II)主要な計算ボトルネックを排除し、モデルのスケーラビリティを保証するメモリ効率の低い低ランク最適化。 (iii) 埋め込み類似性とトポロジカルな関係をバランスさせてオンライン検索を誘導する適応型コミュニティスコア(ACS)。 ヘテロ親和性およびホモ親和性ベンチマークの広範な実験により、AdaptCSはF1スコアにおいて平均11%の性能のベースラインを上回り、ヘテロフィリーレベルの堅牢性を保ち、最大2桁のスピードアップを達成することを示した。

関連論文リスト

• Interpretable and Adaptive Node Classification on Heterophilic Graphs via Combinatorial Scoring and Hybrid Learning [1.2691047660244335]
  グラフニューラルネットワーク(GNN)は、ホモフィルグラフ上で強い性能を達成するが、隣接するノードがしばしば異なるクラスに属しているため、しばしば過度に苦労する。 本稿では、深いメッセージパッシングではなく、明示的な推論に基づく半教師付きノード分類のための解釈可能かつ適応的なフレームワークを提案する。 ヘテロ親和性および遷移性ベンチマークの実験は、現代のGNNと競合する性能を示し、解釈可能性、マグロ、計算効率の利点を提供する。
  論文  参考訳（メタデータ） (2025-12-22T20:50:44Z)
• HiLoMix: Robust High- and Low-Frequency Graph Learning Framework for Mixing Address Association [4.848214568017272]
  混合サービスは、不正取引のために悪意あるアクターによってますます悪用されている。 アドレスアソシエーションの混合に特化して設計されたグラフベースの学習フレームワークであるHiLoMixを提案する。 実験により、HiLoMixはアドレス関連を混合する既存の手法よりも優れていることが示された。
  論文  参考訳（メタデータ） (2025-11-11T02:19:00Z)
• Limits of message passing for node classification: How class-bottlenecks restrict signal-to-noise ratio [0.6117371161379209]
  メッセージパッシングニューラルネットワーク(MPNN)はノード分類の強力なモデルであるが、グラフのヘテロフィリーおよび構造的ボトルネックの下でのパフォーマンス制限に悩まされている。 本稿では,MPNN表現の信号対雑音比(SNR)を用いて,ヘテロフィリとボトルネックの関係を明らかにする。 高次ホモフィリーを最大化するための最適グラフ構造は、単クラスおよび二クラス二部体の解離結合であることを示す。 これにより、全てのホモフィリーにおけるほぼ完璧な分類精度を達成するグラフアンサンブルに基づく再配線アルゴリズムBRIDGEが得られる。
  論文  参考訳（メタデータ） (2025-08-25T09:25:14Z)
• ReDiSC: A Reparameterized Masked Diffusion Model for Scalable Node Classification with Structured Predictions [64.17845687013434]
  本稿では,構造化ノード分類のための構造拡散モデルであるReDiSCを提案する。 本稿では,ReDiSCが最先端のGNN,ラベル伝搬,拡散ベースラインと比較して,優れた,あるいは高い競争力を発揮することを示す。 特にReDiSCは、従来の構造化拡散法が計算制約によって失敗する大規模データセットに効果的にスケールする。
  論文  参考訳（メタデータ） (2025-07-19T04:46:53Z)
• Efficient Bilateral Cross-Modality Cluster Matching for Unsupervised Visible-Infrared Person ReID [56.573905143954015]
  本稿では, クラスタ間マッチングによるモダリティギャップを低減するための, クラスタマッチングに基づく新たな学習フレームワークを提案する。 このような監視信号の下では、クラスタレベルで特徴を協調的に整列させるために、モダリティ・特定・モダリティ・非依存(MSMA)コントラスト学習フレームワークが提案されている。 公開SYSU-MM01とRegDBデータセットの実験により,提案手法の有効性が示された。
  論文  参考訳（メタデータ） (2023-05-22T03:27:46Z)
• Revisiting Heterophily For Graph Neural Networks [42.41238892727136]
  グラフニューラルネットワーク(GNN)は、関係帰納バイアスに基づくグラフ構造を用いて基本ニューラルネットワーク(NN)を拡張する(ホモフィリー仮定) 最近の研究は、NNと比較してパフォーマンスが不十分な、非自明なデータセットのセットを特定している。
  論文  参考訳（メタデータ） (2022-10-14T08:00:26Z)
• Spatial-spectral Hyperspectral Image Classification via Multiple Random Anchor Graphs Ensemble Learning [88.60285937702304]
  本稿では,複数のランダムアンカーグラフアンサンブル学習(RAGE)を用いた空間スペクトルHSI分類手法を提案する。 まず、各選択されたバンドのより記述的な特徴を抽出し、局所的な構造と領域の微妙な変化を保存するローカルバイナリパターンを採用する。 次に,アンカーグラフの構成に適応隣接代入を導入し,計算複雑性を低減した。
  論文  参考訳（メタデータ） (2021-03-25T09:31:41Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。