論文の概要: The impossibility of low rank representations for triangle-rich complex
networks
- arxiv url: http://arxiv.org/abs/2003.12635v1
- Date: Fri, 27 Mar 2020 20:57:56 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-19 04:55:10.369633
- Title: The impossibility of low rank representations for triangle-rich complex
networks
- Title（参考訳）: 三角形リッチ複素ネットワークに対する低階表現の不可能性
- Authors: C. Seshadhri and Aneesh Sharma and Andrew Stolman and Ashish Goel
- Abstract要約: このようなグラフ埋め込みは複素ネットワークの健全な性質を捉えないと主張する。
数学的には、これらの2つの性質をうまく生成できる埋め込みは、頂点数においてほぼ線型でなければならない。
このことは、Singular Value Decompositionやnode2vecのような一般的な埋め込み技術が現実世界の複雑なネットワークの構造的側面を捉えていないことを証明している。
- 参考スコア（独自算出の注目度）: 9.550745725703292
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The study of complex networks is a significant development in modern science,
and has enriched the social sciences, biology, physics, and computer science.
Models and algorithms for such networks are pervasive in our society, and
impact human behavior via social networks, search engines, and recommender
systems to name a few. A widely used algorithmic technique for modeling such
complex networks is to construct a low-dimensional Euclidean embedding of the
vertices of the network, where proximity of vertices is interpreted as the
likelihood of an edge. Contrary to the common view, we argue that such graph
embeddings do not}capture salient properties of complex networks. The two
properties we focus on are low degree and large clustering coefficients, which
have been widely established to be empirically true for real-world networks. We
mathematically prove that any embedding (that uses dot products to measure
similarity) that can successfully create these two properties must have rank
nearly linear in the number of vertices. Among other implications, this
establishes that popular embedding techniques such as Singular Value
Decomposition and node2vec fail to capture significant structural aspects of
real-world complex networks. Furthermore, we empirically study a number of
different embedding techniques based on dot product, and show that they all
fail to capture the triangle structure.
- Abstract（参考訳）: 複雑なネットワークの研究は現代科学において重要な発展であり、社会科学、生物学、物理学、計算機科学を豊かにしてきた。
このようなネットワークのモデルとアルゴリズムは私たちの社会に広く浸透しており、ソーシャルネットワーク、検索エンジン、レコメンデーターシステムを通じて人間の行動に影響を与える。
このような複雑なネットワークをモデル化するためのアルゴリズム的手法は、ネットワークの頂点の低次元ユークリッド埋め込みを構築することである。
一般的な見解とは対照的に、そのようなグラフ埋め込みは複素ネットワークの健全な性質を捉えない。
私たちが注目する2つの特性は、低次と大きなクラスタリング係数であり、実世界のネットワークに実証的に当てはまるように広く確立されています。
我々は、これらの2つの性質をうまく作成できる埋め込み(ドット積を用いて類似度を測定する)が頂点数でほぼ線形であることを数学的に証明する。
このことは、Singular Value Decompositionやnode2vecのような一般的な埋め込み技術が現実世界の複雑なネットワークの構造的側面を捉えていないことを証明している。
さらに,ドット生成物に基づく様々な埋め込み手法を実証的に研究し,それらすべてが三角形の構造を捉えていないことを示す。
関連論文リスト
- Sifting out communities in large sparse networks [2.666294200266662]
大規模ネットワークにおけるクラスタリングの結果の質を定量化するための直感的な客観的関数を導入する。
この領域に特に適したコミュニティを特定するために,2段階の手法を用いる。
数万のノードからなる大規模ネットワークにおける複雑な遺伝的相互作用を同定する。
論文 参考訳（メタデータ） (2024-05-01T18:57:41Z) - Defining Neural Network Architecture through Polytope Structures of Dataset [53.512432492636236]
本稿では, ニューラルネットワーク幅の上下境界を定義し, 問題となるデータセットのポリトープ構造から情報を得る。
本研究では,データセットのポリトープ構造を学習したニューラルネットワークから推定できる逆条件を探索するアルゴリズムを開発した。
MNIST、Fashion-MNIST、CIFAR10といった一般的なデータセットは、顔の少ない2つ以上のポリトップを用いて効率的にカプセル化できることが確立されている。
論文 参考訳（メタデータ） (2024-02-04T08:57:42Z) - Unsupervised Graph Attention Autoencoder for Attributed Networks using
K-means Loss [0.0]
我々は、属性付きネットワークにおけるコミュニティ検出のための、教師なしのtextbfGraph Attention textbfAutotextbfEncoder に基づく、シンプルで効率的なクラスタリング指向モデルを提案する。
提案モデルは,ネットワークのトポロジと属性情報の両方から表現を十分に学習し,同時に2つの目的,すなわち再構築とコミュニティ発見に対処する。
論文 参考訳（メタデータ） (2023-11-21T20:45:55Z) - HyperS2V: A Framework for Structural Representation of Nodes in Hyper
Networks [8.391883728680439]
ハイパーネットワークは、ノード間のより複雑な関係を描写し、広範な情報を格納する能力を持っている。
本研究では,ハイパーネットワークの構造的類似性に着目したノード埋め込み手法であるHyperS2Vを紹介する。
論文 参考訳（メタデータ） (2023-11-07T17:26:31Z) - Riemannian Residual Neural Networks [58.925132597945634]
残余ニューラルネットワーク(ResNet)の拡張方法を示す。
ResNetは、機械学習において、有益な学習特性、優れた経験的結果、そして様々なニューラルネットワークを構築する際に容易に組み込める性質のために、ユビキタスになった。
論文 参考訳（メタデータ） (2023-10-16T02:12:32Z) - Data Topology-Dependent Upper Bounds of Neural Network Widths [52.58441144171022]
まず、3層ニューラルネットワークがコンパクトな集合上のインジケータ関数を近似するように設計可能であることを示す。
その後、これは単純複体へと拡張され、その位相構造に基づいて幅の上界が導かれる。
トポロジカルアプローチを用いて3層ReLUネットワークの普遍近似特性を証明した。
論文 参考訳（メタデータ） (2023-05-25T14:17:15Z) - Provable Guarantees for Nonlinear Feature Learning in Three-Layer Neural
Networks [49.808194368781095]
3層ニューラルネットワークは,2層ネットワークよりも特徴学習能力が豊富であることを示す。
この研究は、特徴学習体制における2層ネットワーク上の3層ニューラルネットワークの証明可能なメリットを理解するための前進である。
論文 参考訳（メタデータ） (2023-05-11T17:19:30Z) - Low-Rank Representations Towards Classification Problem of Complex
Networks [0.0]
社会的相互作用、脳活動、分子構造を表す複雑なネットワークは、それらの特性をグラフとして理解し予測するために広く研究されている。
これらのネットワークのモデルとアルゴリズムは、検索エンジンやレコメンデーターシステムのような現実のアプリケーションで使用される。
ネットワーク分類問題における実生活ネットワークの低ランク表現の性能について検討する。
論文 参考訳（メタデータ） (2022-10-20T19:56:18Z) - Rank Diminishing in Deep Neural Networks [71.03777954670323]
ニューラルネットワークのランクは、層をまたがる情報を測定する。
これは機械学習の幅広い領域にまたがる重要な構造条件の例である。
しかし、ニューラルネットワークでは、低ランク構造を生み出す固有のメカニズムはあいまいで不明瞭である。
論文 参考訳（メタデータ） (2022-06-13T12:03:32Z) - Learning Connectivity of Neural Networks from a Topological Perspective [80.35103711638548]
本稿では,ネットワークを解析のための完全なグラフに表現するためのトポロジ的視点を提案する。
接続の規模を反映したエッジに学習可能なパラメータを割り当てることにより、学習プロセスを異なる方法で行うことができる。
この学習プロセスは既存のネットワークと互換性があり、より大きな検索空間と異なるタスクへの適応性を持っている。
論文 参考訳（メタデータ） (2020-08-19T04:53:31Z) - Node Embeddings and Exact Low-Rank Representations of Complex Networks [30.869784223109832]
Seshadhriらによる最近の研究は、そのような埋め込みは複雑なネットワークで生じる局所構造を捉えることができないことを示唆している。
Seshadhriらの結果は、複雑なネットワークの低次元構造ではなく、それらが使用するモデルに密接に関連していることを示す。
論文 参考訳（メタデータ） (2020-06-10T01:09:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。