論文の概要: Mining Large Independent Sets on Massive Graphs

• arxiv url: http://arxiv.org/abs/2208.07777v4
• Date: Tue, 28 Oct 2025 11:42:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-29 15:35:35.51395
• Title: Mining Large Independent Sets on Massive Graphs
• Title（参考訳）: 大規模グラフ上の大規模独立集合のマイニング
• Authors: Yu Zhang, Witold Pedrycz, Chanjuan Liu, Enqiang Zhu,
• Abstract要約: ARCISは、巨大なグラフ上の大きな独立した集合をマイニングするための効率的なアルゴリズムである。 ARCISは、ほとんどのインスタンスで最高の、または最も結びついたソリューション品質が得られることを示す。
• 参考スコア（独自算出の注目度）: 47.21699378695116
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Maximum Independent Set problem is fundamental for extracting conflict-free structure from large graphs, with applications in scheduling, recommendation, and network analysis. However, existing heuristics can stagnate when search schedules are fixed and information from past solutions is underused, leading to wasted effort in low-quality regions of the search space. We present ARCIS, an efficient algorithm for mining large independent sets on massive graphs. ARCIS couples two main components. The first is an adaptive restart policy that refreshes exploration when progress slows. The second is Consensus-Guided Vertex Fixing, which restricts the search to the non-consensus region of the graph by fixing vertices consistently observed within a round. The consensus is maintained as a running intersection within each round, and because it is recomputed at every restart, the fixing is reversible. Vertices that later lose support are automatically unfixed and their neighborhoods re-enter the working graph, which corrects occasional mistakes while preserving progress. Experiments on 222 graphs from four benchmark suites show that ARCIS attains the best or tied-best solution quality in most instances while delivering competitive runtime and low variability. Ablation studies isolate the impact of each component, indicating that ARCIS is a practical and robust method for large-scale graph mining.
• Abstract（参考訳）: 最大独立集合問題(英: Maximum Independent Set problem)は、スケジューリング、レコメンデーション、ネットワーク分析に応用した、大きなグラフから競合のない構造を抽出するための基本問題である。 しかし、検索スケジュールが固定され、過去のソリューションからの情報が過小評価されると、既存のヒューリスティックスは停滞し、検索空間の低品質領域では無駄な労力がかかる。 本稿では、大規模グラフ上の大規模独立集合をマイニングする効率的なアルゴリズムARCISを提案する。 ARCISは2つの主要なコンポーネントを結合する。 ひとつは、進捗が遅くなると探索をリフレッシュするアダプティブリスタートポリシーです。 2つ目はConsensus-Guided Vertex Fixing(英語版)であり、これはグラフの非Consensus領域への探索を、丸の中で一貫して観察される頂点を固定することによって制限する。 コンセンサスは各ラウンド内の実行交差点として維持され、再起動毎に再計算されるため、修正は可逆である。 後でサポートを失う検証は自動的にアンフィックスされ、その地区はワークグラフに再入力される。 4つのベンチマークスイートから得られた222のグラフの実験によると、ARCISは競争力のあるランタイムと低変動性を提供しながら、ほとんどのインスタンスで最高の、または最も結びついたソリューション品質を達成している。 アブレーション研究は各成分の影響を分離し、ARCISが大規模グラフマイニングの実用的で堅牢な方法であることを示唆している。

関連論文リスト

• HELP: HyperNode Expansion and Logical Path-Guided Evidence Localization for Accurate and Efficient GraphRAG [53.30561659838455]
  大きな言語モデル(LLM)は、しばしば固有の知識境界と幻覚に苦しむ。 Retrieval-Augmented Generation (RAG) は、マルチホップ推論に不可欠な構造的相互依存性をしばしば見落としている。 ヘルプは、複数の単純でマルチホップなQAベンチマークで競合性能を達成し、グラフベースのRAGベースラインよりも28.8$times$のスピードアップを実現している。
  論文  参考訳（メタデータ） (2026-02-24T14:05:29Z)
• Dynamic Deep Graph Learning for Incomplete Multi-View Clustering with Masked Graph Reconstruction Loss [26.31060859315329]
  textbfIncomplete textbfMulti-textbfView textbfClustering with textbfMasked Graph Reconstruction Loss (DGIMVCM)を提案する。 次に、グラフ畳み込み埋め込み層を設計し、主要な特徴を抽出し、動的なビュー固有のグラフ構造を洗練し、グローバルグラフを利用して、不足するビューの計算を行う。
  論文  参考訳（メタデータ） (2025-11-14T11:26:38Z)
• On the Effectiveness of Graph Reordering for Accelerating Approximate Nearest Neighbor Search on GPU [14.338954144116759]
  グラフベースの近似Nearest Neighbor Search (ANNS)は、現代のAIアプリケーションにおいて支配的なパラダイムとなっている。 本稿では,GPU上でのグラフベースのANNSに対するグラフの並べ替え効果について,初めて体系的に検討する。
  論文  参考訳（メタデータ） (2025-08-21T10:50:49Z)
• A Reduction-Driven Local Search for the Generalized Independent Set Problem [29.094247069747073]
  本稿では,これらのリダクションルールを前処理,初期解生成,局所探索コンポーネントに組み込むリダクション駆動ローカルサーチ(RLS)アルゴリズムを提案する。 RLSは、異なるアプリケーションシナリオから生じる278のグラフで実証的に評価される。 他の既知の解法に比べてはるかに優れた解を実現し、2億6000万を超えるグラフに対する解を効果的に提供する。
  論文  参考訳（メタデータ） (2025-05-27T11:39:05Z)
• Preference Optimization for Combinatorial Optimization Problems [54.87466279363487]
  強化学習(Reinforcement Learning, RL)は、ニューラルネットワーク最適化のための強力なツールとして登場した。 大幅な進歩にもかかわらず、既存のRLアプローチは報酬信号の減少や大規模な行動空間における非効率な探索といった課題に直面している。 統計的比較モデルを用いて定量的報酬信号を定性的選好信号に変換する新しい手法であるPreference Optimizationを提案する。
  論文  参考訳（メタデータ） (2025-05-13T16:47:00Z)
• Learning-guided iterated local search for the minmax multiple traveling salesman problem [13.924692115320553]
  本稿では, ミンマックス多旅行セールスマン問題に対する, 傾き駆動型局所探索手法を提案する。 提案アルゴリズムは,ソリューションの品質と実行時間の観点から,優れた結果が得られることを示す。 特に、32の既知の結果が新たに達成され、35の他のインスタンスで最もよく知られた結果と一致している。
  論文  参考訳（メタデータ） (2024-03-19T02:57:10Z)
• Dynamic Incremental Optimization for Best Subset Selection [15.8362578568708]
  最良のサブセット選択は、多くの学習問題に対する金の標準と見なされている。 主問題構造と双対問題構造に基づいて,効率的な部分集合双対アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-02-04T02:26:40Z)
• Quality-Diversity Algorithms Can Provably Be Helpful for Optimization [24.694984679399315]
  QD(Quality-Diversity)アルゴリズムは、ハイパフォーマンスだが多様なソリューションのセットを見つけることを目的としている。 本稿では,厳密な実行時間解析によってQDアルゴリズムの最適化能力に光を当てようとしている。
  論文  参考訳（メタデータ） (2024-01-19T07:40:24Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。 提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
  論文  参考訳（メタデータ） (2024-01-12T17:57:07Z)
• BalMCTS: Balancing Objective Function and Search Nodes in MCTS for Constraint Optimization Problems [7.196057722218442]
  制約問題最適化(COP)は、通常ブランチ・アンド・バウンド(B&B)法によって解決される問題において、複雑な課題を提起する。 COPを解くための深度優先探索アルゴリズムに基づく新しいニューラルネットワークアルゴリズムを提案する。 提案手法は,最初の5つの実現可能な解のうち17.63%未満のギャップを有する実現可能な解を同定する。
  論文  参考訳（メタデータ） (2023-12-26T03:09:08Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• New Characterizations and Efficient Local Search for General Integer Linear Programming [17.80124240223163]
  本研究では境界解の概念を用いた線形プログラミング(ILP)の新たな特徴付けを提案する。 そこで我々は,局所探索アルゴリズムのLocal-ILPを開発した。 MIPLIBデータセットで行った実験は、大規模ハードILP問題の解法におけるアルゴリズムの有効性を示した。
  論文  参考訳（メタデータ） (2023-04-29T07:22:07Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。 キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。 オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
  論文  参考訳（メタデータ） (2023-02-08T08:17:43Z)
• Best Subset Selection with Efficient Primal-Dual Algorithm [24.568094642425837]
  多くの学習問題に対するベストサブセット選択は「ゴールドスタンダード」と見なされている。 本稿では,$ell$-regularized問題系の二重形式について検討する。 主問題構造と双対問題構造に基づく効率的な主対法が開発されている。
  論文  参考訳（メタデータ） (2022-07-05T14:07:52Z)
• Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration [72.15369769265398]
  実験により、ECORDは最大カット問題に対するRLアルゴリズムのための新しいSOTAを実現する。 最も近い競合と比較して、ECORDは最適性ギャップを最大73%削減する。
  論文  参考訳（メタデータ） (2022-05-27T17:13:10Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Graph Denoising with Framelet Regularizer [25.542429117462547]
  本稿では,特徴雑音と構造雑音の両面からグラフデータの正則化を行う。 本モデルでは, グラフが汚染されている場合でも, 一般的なグラフ畳み込みと比較して, 性能が著しく向上する。
  論文  参考訳（メタデータ） (2021-11-05T05:17:23Z)
• Spatial-spectral Hyperspectral Image Classification via Multiple Random Anchor Graphs Ensemble Learning [88.60285937702304]
  本稿では,複数のランダムアンカーグラフアンサンブル学習(RAGE)を用いた空間スペクトルHSI分類手法を提案する。 まず、各選択されたバンドのより記述的な特徴を抽出し、局所的な構造と領域の微妙な変化を保存するローカルバイナリパターンを採用する。 次に,アンカーグラフの構成に適応隣接代入を導入し,計算複雑性を低減した。
  論文  参考訳（メタデータ） (2021-03-25T09:31:41Z)
• PAMELI: A Meta-Algorithm for Computationally Expensive Multi-Objective Optimization Problems [0.0]
  提案アルゴリズムは,実モデルのモデルによって定義される一連の代理問題の解法に基づく。 また,最適化ランドスケープのための最適なサロゲートモデルとナビゲーション戦略のメタ検索を行う。
  論文  参考訳（メタデータ） (2021-03-19T11:18:03Z)
• Learning to Schedule Heuristics in Branch-and-Bound [25.79025327341732]
  現実世界のアプリケーションは通常、迅速な意思決定を可能にするために、検索の早い段階で優れたソリューションを見つける必要があります。 正確なMIPソルバにおけるスケジューリングのための最初のデータ駆動フレームワークを提案する。 最先端の学術MIPソルバーのデフォルト設定と比較して、挑戦的なインスタンスのクラスで平均プライマリ積分を最大49%削減することができます。
  論文  参考訳（メタデータ） (2021-03-18T14:49:52Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。 スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。 その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
  論文  参考訳（メタデータ） (2021-03-10T03:16:12Z)
• Resource Allocation via Model-Free Deep Learning in Free Space Optical Communications [119.81868223344173]
  本稿では,自由空間光学(FSO)通信におけるチャネルフェージング効果の緩和のための資源配分の一般的な問題について検討する。 本フレームワークでは,FSO資源割り当て問題を解決する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-07-27T17:38:51Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• The limits of min-max optimization algorithms: convergence to spurious non-critical sets [82.74514886461257]
  min-max最適化アルゴリズムは周期サイクルや同様の現象が存在するため、はるかに大きな問題に遭遇する。 問題のどの点も引き付けないアルゴリズムが存在することを示す。 ほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほとんどである。
  論文  参考訳（メタデータ） (2020-06-16T10:49:27Z)
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
  近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。 最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。 提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
  論文  参考訳（メタデータ） (2020-06-08T09:25:47Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。 我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
  論文  参考訳（メタデータ） (2020-01-29T09:40:58Z)

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

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