論文の概要: Matching and mixing: Matchability of graphs under Markovian error

• arxiv url: http://arxiv.org/abs/2601.20020v1
• Date: Tue, 27 Jan 2026 19:53:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-29 15:46:06.640358
• Title: Matching and mixing: Matchability of graphs under Markovian error
• Title（参考訳）: マッチングと混合:マルコフ誤差下のグラフのマッチング可能性
• Authors: Zhirui Li, Keith D. Levin, Zhiang Zhao, Vince Lyzinski,
• Abstract要約: 我々はマルコフ連鎖ノイズモデルが世界規模で混合される前に匿名化が発生することを示す。 我々は,Facebookの友情ネットワークと欧州の研究機関の電子メール通信ネットワークから得られた実世界のデータセットについて調査を行った。
• 参考スコア（独自算出の注目度）: 1.2559534897613556
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of graph matching for a sequence of graphs generated under a time-dependent Markov chain noise model. Our edgelighter error model, a variant of the classical lamplighter random walk, iteratively corrupts the graph $G_0$ with edge-dependent noise, creating a sequence of noisy graph copies $(G_t)$. Much of the graph matching literature is focused on anonymization thresholds in edge-independent noise settings, and we establish novel anonymization thresholds in this edge-dependent noise setting when matching $G_0$ and $G_t$. Moreover, we also compare this anonymization threshold with the mixing properties of the Markov chain noise model. We show that when $G_0$ is drawn from an Erdős-Rényi model, the graph matching anonymization threshold and the mixing time of the edgelighter walk are both of order $Θ(n^2\log n)$. We further demonstrate that for more structured model for $G_0$ (e.g., the Stochastic Block Model), graph matching anonymization can occur in $O(n^α\log n)$ time for some $α<2$, indicating that anonymization can occur before the Markov chain noise model globally mixes. Through extensive simulations, we verify our theoretical bounds in the settings of Erdős-Rényi random graphs and stochastic block model random graphs, and explore our findings on real-world datasets derived from a Facebook friendship network and a European research institution email communication network.
• Abstract（参考訳）: 時間依存型マルコフ連鎖雑音モデルの下で生成されるグラフ列に対するグラフマッチングの問題点を考察する。 我々のエッジライトエラーモデルは、古典的なランプライトのランダムウォークの変種であり、エッジ依存ノイズを伴うグラフ$G_0$を反復的に破損させ、ノイズの多いグラフコピー$(G_t)$を生成する。 グラフマッチングの文献の多くは、エッジ非依存ノイズ設定における匿名化しきい値に焦点を合わせており、このエッジ依存ノイズ設定において、$G_0$と$G_t$をマッチングする際に、新しい匿名化しきい値を確立する。 さらに,この匿名化閾値とマルコフ連鎖雑音モデルの混合特性を比較する。 エルデシュ=レーニモデルから$G_0$が引かれるとき、グラフマッチング匿名化しきい値とエッジライトウォークの混合時間の両方が、次数$(n^2\log n)$であることを示す。 さらに、より構造化された$G_0$(例えば、確率ブロックモデル)に対して、グラフマッチングの匿名化は$O(n^α\log n)$時間に発生し、マルコフ連鎖ノイズモデルがグローバルに混合される前に匿名化が発生することを示す。 広範囲にわたるシミュレーションを通じて、エルデシュ・レニイランダムグラフと確率ブロックモデルランダムグラフの設定における理論的境界を検証し、Facebookの友情ネットワークとヨーロッパの研究機関の電子メール通信ネットワークから得られた実世界のデータセットについての知見を探索する。

関連論文リスト

• DREAM: Dual-Standard Semantic Homogeneity with Dynamic Optimization for Graph Learning with Label Noise [53.55187452152358]
  本稿では,ラベル付きグラフ上での信頼度,関係インフォームド最適化のためのDREAM(Dual-Standard Semantic Homogeneity with Dynamic Optimization)を提案する。 具体的には、グラフ内の各ラベル付きノードの信頼性を反復的に再評価するリレーショナルインフォームド動的最適化フレームワークを設計する。
  論文  参考訳（メタデータ） (2026-01-24T12:54:18Z)
• Sparse Training of Discrete Diffusion Models for Graph Generation [45.103518022696996]
  SparseDiffは、ほとんど全ての大きなグラフがスパースであるという観察に基づく、新しい拡散モデルである。 エッジのサブセットを選択することで、SparseDiffは、ノイズ発生過程とノイズ発生ネットワーク内のスパースグラフ表現を効果的に活用する。 本モデルでは,小規模・大規模両方のデータセットにおいて,複数のメトリクスにわたる最先端性能を示す。
  論文  参考訳（メタデータ） (2023-11-03T16:50:26Z)
• Graph Mixup with Soft Alignments [49.61520432554505]
  本研究では,画像上での使用に成功しているミキサアップによるグラフデータの増大について検討する。 ソフトアライメントによるグラフ分類のための簡易かつ効果的な混合手法であるS-Mixupを提案する。
  論文  参考訳（メタデータ） (2023-06-11T22:04:28Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。 キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。 オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
  論文  参考訳（メタデータ） (2023-02-08T08:17:43Z)
• GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
  本稿では,高次元分布をモデル化し,グラフスケルトンと整合した複雑な関係特徴構造を持つデータの新しい例を生成することの問題点を考察する。 提案するモデルは,タスクを2つのフェーズに分割することで,各データポイントのグラフ構造に制約されたデータ特徴を生成する問題に対処する。 第一に、与えられたグラフのノードに関連する機能の分布をモデル化し、第二に、ノードのフィーチャに条件付きでエッジ機能を補完する。
  論文  参考訳（メタデータ） (2022-12-01T11:49:07Z)
• DiGress: Discrete Denoising diffusion for graph generation [79.13904438217592]
  DiGressは、分類ノードとエッジ属性を持つグラフを生成するための離散化拡散モデルである。 分子と非分子のデータセットで最先端のパフォーマンスを実現し、最大3倍の妥当性が向上する。 また、1.3Mの薬物様分子を含む大規模なGuacaMolデータセットにスケールする最初のモデルでもある。
  論文  参考訳（メタデータ） (2022-09-29T12:55:03Z)
• Causal Inference Despite Limited Global Confounding via Mixture Models [4.721845865189578]
  そのようなモデルの有限$k$-mixtureは、図式的により大きなグラフで表される。 空でないDAGの混合を学習するための最初のアルゴリズムを与える。
  論文  参考訳（メタデータ） (2021-12-22T01:04:50Z)
• Neighborhood Random Walk Graph Sampling for Regularized Bayesian Graph Convolutional Neural Networks [0.6236890292833384]
  本稿では,近隣ランダムウォークサンプリング(BGCN-NRWS)を用いたベイジアングラフ畳み込みネットワーク(Bayesian Graph Convolutional Network)を提案する。 BGCN-NRWSは、グラフ構造を利用したマルコフ・チェイン・モンテカルロ(MCMC)に基づくグラフサンプリングアルゴリズムを使用し、変分推論層を用いてオーバーフィッティングを低減し、半教師付きノード分類における最先端と比較して一貫して競合する分類結果を得る。
  論文  参考訳（メタデータ） (2021-12-14T20:58:27Z)
• Order Matters: Probabilistic Modeling of Node Sequence for Graph Generation [18.03898476141173]
  グラフ生成モデルはグラフ上の分布を定義する。 グラフ上の正確な結合確率とシーケンシャルプロセスのノード順序を導出する。 我々は,従来の手法のアドホックノード順序を使わずに,この境界を最大化してグラフ生成モデルを訓練する。
  論文  参考訳（メタデータ） (2021-06-11T06:37:52Z)

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

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