Metraipolis › archive › dc_64bc0bf55615

Moment-guided edge sampling — arXiv:2609.30472

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.30472
License (as archived)
CC0-1.0
Archived
2026-10-08T02:08:52.494Z
SHA-256 of the archived text
b684950ed3a8b71e5696550842b187361a6d3a642bfc40fab673bf7486e14412
Stable URL of this page
https://metraipolis.com/documento/dc_64bc0bf55615

How to cite

Moment-guided edge sampling — arXiv:2609.30472 — arXiv (en), https://arxiv.org/abs/2609.30472 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_64bc0bf55615 (Metraipolis archive dc_64bc0bf55615, sha256 b684950ed3a8b71e5696550842b187361a6d3a642bfc40fab673bf7486e14412)
BibTeX
@misc{dc64bc0bf55615,
  title = {Moment-guided edge sampling — arXiv:2609.30472},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.30472},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_64bc0bf55615; sha256 b684950ed3a8b71e5696550842b187361a6d3a642bfc40fab673bf7486e14412},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.30472. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Edge sampling makes local decisions to achieve graph-level objectives, such as preserving structural properties. This creates a fundamental challenge: \textit{how can the effect of a local edge edit (i.e., edge addition or removal) on global graph structure be quantified and controlled?} We address this challenge with a \textit{moment-guided edge sampling framework} based on spectral moments of the random-walk transition matrix. We compute exact moment changes through two complementary methods: a combinatorial method with closed-form updates for low-order moments, and a low-rank method that exploits \textit{locality} and \textit{cyclic trace invariance} to compress computations to edited endpoints, supporting arbitrary moment orders and batched edits. For single-edge edits at fixed moment orders, the low-rank method reduces the cost from $O(mn)$ to $O(m)$, while the combinatorial method evaluates low-order changes in constant time given maintained local statistics. These moment changes provide \textbf{interpretable structural signatures} of local edge motifs that aggregate into graph-level fingerprints. This structural meaning motivates us to ask whether preserving moments also preserves the graph properties. We further derive and validate that moment-preserving sampling can \textbf{retain related structural properties}, including triangle-weighted clustering coefficient. These structural insights enable \textbf{analysis and improvement of graph learning}: different edge structures have distinct effects on supervised node classification, while moment-guided augmentation is competitive for graph contrastive learning. Together, these findings establish moments as an interpretable and controllable bridge from local edge edits to global graph structure and learning.

Tema degli esploratori: governance digitale e beni comuni (retro-catalogo arXiv: annunci del 2026-09-28 in cs.SI).
Categorie arXiv: Machine Learning (cs.LG) ; Social and Information Networks (cs.SI).
Pagina del lavoro: https://arxiv.org/abs/2609.30472 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T01:42:09.661Z dalla pagina https://arxiv.org/catchup/cs.SI/2026-09-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).