論文の概要: Directed Graph Topology Inference via Graph Filter Identification
- arxiv url: http://arxiv.org/abs/2606.27455v1
- Date: Thu, 25 Jun 2026 18:25:57 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-29 18:24:25.286468
- Title: Directed Graph Topology Inference via Graph Filter Identification
- Title（参考訳）: グラフフィルタ同定による直接グラフトポロジ推論
- Abstract要約: 本稿では,グラフ畳み込みフィルタが生成するノイズ測定から有向ネットワークを推定する問題に対処する。
また、上記のステップを交互に交互に組み合わせて、サンプルの複雑さを向上する結合グラフフィルタとトポロジー同定アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 54.541275287889164
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We address the problem of inferring a directed network from nodal measurements generated by linear diffusion dynamics on the sought graph. Observations are modeled as the outputs of a graph convolutional filter, i.e., a polynomial (with unknown coefficients) of a local diffusion graph-shift operator encoding the latent graph topology, excited with an ensemble of independent graph signals with arbitrarily-correlated nodal components. Unlike prior efforts that considered undirected graphs and white signal excitations, here the graph-shift operator and the observations' covariance matrix are not simultaneously diagonalizable. In this challenging context, we first rely on measurements of the output signals along with prior statistical information on the inputs to identify the diffusion filter. Such system identification problem involves solving a system of quadratic matrix equations, which we show is identifiable under spectral-diversity assumptions on the input covariances. For algorithmic purposes we recast it as a smooth quadratic minimization subject to Stiefel manifold constraints. Subsequent identification of the network topology given the graph filter estimate boils down to finding a sparse and structurally admissible shift that commutes with the given filter, thus, forcing the latter to be a polynomial in the sought graph-shift operator. A joint graph filter and topology identification algorithm is also proposed, which alternates between the aforementioned steps in a mutually reinforcing fashion to offer improved sample complexity. Numerical tests corroborate the effectiveness of the proposed algorithms in recovering synthetic digraphs and real-data case studies, and illustrate their potential utility on urban mobility analyses as well as portfolio optimization.
- Abstract（参考訳）: 探索グラフ上の線形拡散力学により生成されるノイズ測定から有向ネットワークを推定する問題に対処する。
観測はグラフ畳み込みフィルタの出力、すなわち潜在グラフトポロジーを符号化する局所拡散グラフシフト作用素の多項式(未知の係数)としてモデル化され、任意に相関した結節成分を持つ独立グラフ信号のアンサンブルで励起される。
無向グラフや白色信号の励起を考慮した以前の試みとは異なり、グラフシフト演算子と観測者の共分散行列は同時に対角化できない。
この挑戦的な文脈では、まず、拡散フィルタを特定するために、入力に関する事前統計情報とともに出力信号の測定に依存する。
このようなシステム同定問題は、2次行列方程式の系を解くことを含み、入力共分散に関するスペクトル多様性の仮定の下で同定可能であることを示す。
アルゴリズム的な目的のために、我々はそれをスティーフェル多様体の制約を受ける滑らかな二次最小化として再考する。
その後のグラフフィルタの推定値によるネットワークトポロジーの同定は、与えられたフィルタと通勤するスパースかつ構造的に許容可能なシフトを見つけるために沸騰し、後者は探索されたグラフシフト演算子の多項式となる。
また、上記のステップを相互強化的に交互に交互に交互に交互に行い、サンプルの複雑さを向上するジョイントグラフフィルタとトポロジー同定アルゴリズムを提案する。
数値実験は, 提案アルゴリズムが合成ダイグラフと実データケーススタディを復元する際の有効性を裏付けるものであり, 都市移動解析およびポートフォリオ最適化におけるその有用性を示すものである。
関連論文リスト
- Generative Diffusion Models of Stochastic Graph Signals [74.4097723209053]
本稿では,条件付きグラフ信号生成モデルの問題に取り組み,単一の拡散フレームワークを用いてそれらに取り組む。
グラフトポロジとノード機能側情報に基づいて直接条件付きグラフ信号を描画するグラフニューラルネットワーク(GNN)によりパラメータ化された逆拡散過程を学習する。
本稿では,株価予測と最適無線リソース割り当てという2つの生成課題について,両領域で広範囲に数値計算を行った。
論文 参考訳（メタデータ） (2026-07-07T22:02:13Z) - Grassmanian Interpolation of Low-Pass Graph Filters: Theory and Applications [13.83778274369268]
低域グラフフィルタは、グラフやその他の非ユークリッド領域における信号処理の基本である。
グラスマン多様体上の正規座標におけるリーマン座標に基づく低域グラフフィルタの新しいアルゴリズムを提案する。
ノードの特徴の時間的進化は、ネットワークのホモフィリ次数を調整するために類似性補正によって、進化するグラフに変換される可能性があると論じる。
第2に、与えられた静的グラフによって誘導されるドット積グラフファミリを提案し、フィルタトポロジによって促進されるノード分類のための改良されたメッセージパッシングスキームを推論する。
論文 参考訳（メタデータ） (2025-10-27T11:40:14Z) - A Spectral Interpretation of Redundancy in a Graph Reservoir [51.40366905583043]
この研究はMRGNN(Multi resolution Reservoir Graph Neural Network)における貯留層の定義を再考する。
コンピュータグラフィックスにおける表面設計の分野で最初に導入されたフェアリングアルゴリズムに基づく変種を提案する。
この論文の中核的な貢献は、ランダムウォークの観点からのアルゴリズムの理論解析にある。
論文 参考訳（メタデータ） (2025-07-17T10:02:57Z) - Signed Graph Learning: Algorithms and Theory [17.374356596021936]
実世界のデータは、しばしばデータサンプル間の関係を通して表現され、グラフ構造を形成する。
現在のグラフ学習研究は主に符号なしグラフに焦点を当てている。
我々はスムーズな符号付きグラフ信号の集合をキャプチャする手法を開発した。
論文 参考訳（メタデータ） (2025-07-13T17:33:26Z) - Diffusion Maps for Signal Filtering in Graph Learning [0.0]
本稿では,合成温度センサデータと実世界の温度センサデータを用いた実例を通して,本手法の有効性を示す。
その結果、複雑で非ユークリッド的なデータ構造の分析と理解に新たなアプローチが得られた。
論文 参考訳（メタデータ） (2023-12-22T15:17:44Z) - Supercharging Graph Transformers with Advective Diffusion [28.40109111316014]
本稿では,この課題に対処するために,物理に着想を得たグラフトランスモデルであるAdvDIFFormerを提案する。
本稿では,AdvDIFFormerが位相シフトによる一般化誤差を制御できることを示す。
経験的に、このモデルは情報ネットワーク、分子スクリーニング、タンパク質相互作用の様々な予測タスクにおいて優位性を示す。
論文 参考訳（メタデータ） (2023-10-10T08:40:47Z) - Representing Edge Flows on Graphs via Sparse Cell Complexes [6.74438532801556]
本稿では, フロー表現学習問題,すなわち, 観測されたグラフをセルの集合で拡張する問題を紹介する。
この問題はNPハードであり,その解に対する効率的な近似アルゴリズムを導入している。
論文 参考訳（メタデータ） (2023-09-04T14:30:20Z) - Geometric Graph Filters and Neural Networks: Limit Properties and
Discriminability Trade-offs [122.06927400759021]
本稿では,グラフニューラルネットワーク (GNN) と多様体ニューラルネットワーク (MNN) の関係について検討する。
これらのグラフ上の畳み込みフィルタとニューラルネットワークが連続多様体上の畳み込みフィルタとニューラルネットワークに収束することを示す。
論文 参考訳（メタデータ） (2023-05-29T08:27:17Z) - Multilayer Clustered Graph Learning [66.94201299553336]
我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。
実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。
クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
論文 参考訳（メタデータ） (2020-10-29T09:58:02Z) - Joint Inference of Multiple Graphs from Matrix Polynomials [34.98220454543502]
ノード上の観測からグラフ構造を推定することは重要かつ一般的なネットワーク科学課題である。
ノードの信号の観測から複数のグラフを共同で推定する問題について検討する。
本稿では,真のグラフの回復を保証するための凸最適化手法を提案する。
論文 参考訳（メタデータ） (2020-10-16T02:45:15Z) - Offline detection of change-points in the mean for stationary graph
signals [55.98760097296213]
グラフ信号定常性の概念に依存するオフライン手法を提案する。
我々の検出器は、漸近的でない不等式オラクルの証拠を伴っている。
論文 参考訳（メタデータ） (2020-06-18T15:51:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。