{"id":316961,"date":"2016-11-07T09:34:36","date_gmt":"2016-11-07T17:34:36","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?post_type=msr-research-item&#038;p=316961"},"modified":"2018-10-16T20:06:33","modified_gmt":"2018-10-17T03:06:33","slug":"sparse-exchangeable-graphs-limits-via-graphon-processes","status":"publish","type":"msr-research-item","link":"https:\/\/www.microsoft.com\/en-us\/research\/publication\/sparse-exchangeable-graphs-limits-via-graphon-processes\/","title":{"rendered":"Sparse Exchangeable Graphs and Their Limits Via Graphon Processes"},"content":{"rendered":"<p>In a recent paper, Caron and Fox suggest a probabilistic model for sparse graphs which are exchangeable when associating each vertex with a time parameter in <span id=\"MathJax-Element-1-Frame\" class=\"MathJax\" tabindex=\"0\"><span id=\"MathJax-Span-1\" class=\"math\"><span id=\"MathJax-Span-2\" class=\"mrow\"><span id=\"MathJax-Span-3\" class=\"msubsup\"><span id=\"MathJax-Span-4\" class=\"texatom\"><span id=\"MathJax-Span-5\" class=\"mrow\"><span id=\"MathJax-Span-6\" class=\"mi\">R<\/span><\/span><\/span>\u00a0<span id=\"MathJax-Span-7\" class=\"mo\">+<\/span>\u00a0<\/span><\/span>\u00a0<\/span><\/span><script id=\"MathJax-Element-1\" type=\"math\/tex\">\/\/ <![CDATA[\n\\mathbb{R}_+\n\/\/ ]]><\/script>. Here we show that by generalizing the classical definition of graphons as functions over probability spaces to functions over <span id=\"MathJax-Element-2-Frame\" class=\"MathJax\" tabindex=\"0\"><span id=\"MathJax-Span-8\" class=\"math\"><span id=\"MathJax-Span-9\" class=\"mrow\"><span id=\"MathJax-Span-10\" class=\"mi\">\u03c3<\/span><\/span>\u00a0<\/span><\/span><script id=\"MathJax-Element-2\" type=\"math\/tex\">\/\/ <![CDATA[\n\\sigma\n\/\/ ]]><\/script>-finite measure spaces, we can model a large family of exchangeable graphs, including the Caron-Fox graphs and the traditional exchangeable dense graphs as special cases. Explicitly, modelling the underlying space of features by a <span id=\"MathJax-Element-3-Frame\" class=\"MathJax\" tabindex=\"0\"><span id=\"MathJax-Span-11\" class=\"math\"><span id=\"MathJax-Span-12\" class=\"mrow\"><span id=\"MathJax-Span-13\" class=\"mi\">\u03c3<\/span><\/span>\u00a0<\/span><\/span><script id=\"MathJax-Element-3\" type=\"math\/tex\">\/\/ <![CDATA[\n\\sigma\n\/\/ ]]><\/script>-finite measure space <span id=\"MathJax-Element-4-Frame\" class=\"MathJax\" tabindex=\"0\"><span id=\"MathJax-Span-14\" class=\"math\"><span id=\"MathJax-Span-15\" class=\"mrow\"><span id=\"MathJax-Span-16\" class=\"mo\">(<\/span><span id=\"MathJax-Span-17\" class=\"mi\">S<\/span><span id=\"MathJax-Span-18\" class=\"mo\">,<\/span><span id=\"MathJax-Span-19\" class=\"texatom\"><span id=\"MathJax-Span-20\" class=\"mrow\"><span id=\"MathJax-Span-21\" class=\"mi\">S<\/span><\/span><\/span><span id=\"MathJax-Span-22\" class=\"mo\">,<\/span><span id=\"MathJax-Span-23\" class=\"mi\">\u03bc<\/span><span id=\"MathJax-Span-24\" class=\"mo\">)<\/span><\/span>\u00a0<\/span><\/span><script id=\"MathJax-Element-4\" type=\"math\/tex\">\/\/ <![CDATA[\n(S,\\mathcal{S},\\mu)\n\/\/ ]]><\/script>and the connection probabilities by an integrable function <span id=\"MathJax-Element-5-Frame\" class=\"MathJax\" tabindex=\"0\"><span id=\"MathJax-Span-25\" class=\"math\"><span id=\"MathJax-Span-26\" class=\"mrow\"><span id=\"MathJax-Span-27\" class=\"mi\">W<\/span><span id=\"MathJax-Span-28\" class=\"mo\">:<\/span><span id=\"MathJax-Span-29\" class=\"mi\">S<\/span><span id=\"MathJax-Span-30\" class=\"mo\">\u00d7<\/span><span id=\"MathJax-Span-31\" class=\"mi\">S<\/span><span id=\"MathJax-Span-32\" class=\"mo\">\u2192<\/span><span id=\"MathJax-Span-33\" class=\"mo\">[<\/span><span id=\"MathJax-Span-34\" class=\"mn\">0<\/span><span id=\"MathJax-Span-35\" class=\"mo\">,<\/span><span id=\"MathJax-Span-36\" class=\"mn\">1<\/span><span id=\"MathJax-Span-37\" class=\"mo\">]<\/span><\/span>\u00a0<\/span><\/span><script id=\"MathJax-Element-5\" type=\"math\/tex\">\/\/ <![CDATA[\nW\\colon S\\times S\\to [0,1]\n\/\/ ]]><\/script>, we construct a random family <span id=\"MathJax-Element-6-Frame\" class=\"MathJax\" tabindex=\"0\"><span id=\"MathJax-Span-38\" class=\"math\"><span id=\"MathJax-Span-39\" class=\"mrow\"><span id=\"MathJax-Span-40\" class=\"mo\">(<\/span><span id=\"MathJax-Span-41\" class=\"msubsup\"><span id=\"MathJax-Span-42\" class=\"mi\">G<\/span>\u00a0<span id=\"MathJax-Span-43\" class=\"mi\">t<\/span>\u00a0<\/span><span id=\"MathJax-Span-44\" class=\"msubsup\"><span id=\"MathJax-Span-45\" class=\"mo\">)<\/span>\u00a0<span id=\"MathJax-Span-46\" class=\"texatom\"><span id=\"MathJax-Span-47\" class=\"mrow\"><span id=\"MathJax-Span-48\" class=\"mi\">t<\/span><span id=\"MathJax-Span-49\" class=\"mo\">\u2265<\/span><span id=\"MathJax-Span-50\" class=\"mn\">0<\/span><\/span><\/span>\u00a0<\/span><\/span>\u00a0<\/span><\/span><script id=\"MathJax-Element-6\" type=\"math\/tex\">\/\/ <![CDATA[\n(G_t)_{t\\geq0}\n\/\/ ]]><\/script>of growing graphs such that the vertices of <span id=\"MathJax-Element-7-Frame\" class=\"MathJax\" tabindex=\"0\"><span id=\"MathJax-Span-51\" class=\"math\"><span id=\"MathJax-Span-52\" class=\"mrow\"><span id=\"MathJax-Span-53\" class=\"msubsup\"><span id=\"MathJax-Span-54\" class=\"mi\">G<\/span>\u00a0<span id=\"MathJax-Span-55\" class=\"mi\">t<\/span>\u00a0<\/span><\/span>\u00a0<\/span><\/span><script id=\"MathJax-Element-7\" type=\"math\/tex\">\/\/ <![CDATA[\nG_t\n\/\/ ]]><\/script>are given by a Poisson point process on <span id=\"MathJax-Element-8-Frame\" class=\"MathJax\" tabindex=\"0\"><span id=\"MathJax-Span-56\" class=\"math\"><span id=\"MathJax-Span-57\" class=\"mrow\"><span id=\"MathJax-Span-58\" class=\"mi\">S<\/span><\/span>\u00a0<\/span><\/span><script id=\"MathJax-Element-8\" type=\"math\/tex\">\/\/ <![CDATA[\nS\n\/\/ ]]><\/script>with intensity <span id=\"MathJax-Element-9-Frame\" class=\"MathJax\" tabindex=\"0\"><span id=\"MathJax-Span-59\" class=\"math\"><span id=\"MathJax-Span-60\" class=\"mrow\"><span id=\"MathJax-Span-61\" class=\"mi\">t<\/span><span id=\"MathJax-Span-62\" class=\"mi\">\u03bc<\/span><\/span>\u00a0<\/span><\/span><script id=\"MathJax-Element-9\" type=\"math\/tex\">\/\/ <![CDATA[\nt\\mu\n\/\/ ]]><\/script>, with two points <span id=\"MathJax-Element-10-Frame\" class=\"MathJax\" tabindex=\"0\"><span id=\"MathJax-Span-63\" class=\"math\"><span id=\"MathJax-Span-64\" class=\"mrow\"><span id=\"MathJax-Span-65\" class=\"mi\">x<\/span><span id=\"MathJax-Span-66\" class=\"mo\">,<\/span><span id=\"MathJax-Span-67\" class=\"mi\">y<\/span><\/span>\u00a0<\/span><\/span><script id=\"MathJax-Element-10\" type=\"math\/tex\">\/\/ <![CDATA[\nx,y\n\/\/ ]]><\/script>of the point process connected with probability <span id=\"MathJax-Element-11-Frame\" class=\"MathJax\" tabindex=\"0\"><span id=\"MathJax-Span-68\" class=\"math\"><span id=\"MathJax-Span-69\" class=\"mrow\"><span id=\"MathJax-Span-70\" class=\"mi\">W<\/span><span id=\"MathJax-Span-71\" class=\"mo\">(<\/span><span id=\"MathJax-Span-72\" class=\"mi\">x<\/span><span id=\"MathJax-Span-73\" class=\"mo\">,<\/span><span id=\"MathJax-Span-74\" class=\"mi\">y<\/span><span id=\"MathJax-Span-75\" class=\"mo\">)<\/span><\/span>\u00a0<\/span><\/span><script id=\"MathJax-Element-11\" type=\"math\/tex\">\/\/ <![CDATA[\nW(x,y)\n\/\/ ]]><\/script>. We call such a random family a graphon process.<\/p>\n<p>We prove that a graphon process has convergent subgraph frequencies (with possibly infinite limits) and that, in the natural extension of the cut metric to our setting, the sequence converges to the generating graphon. We also show that the underlying graphon is identifiable only as an equivalence class over graphons with cut distance zero. More generally, we study metric convergence for arbitrary (not necessarily random) sequences of graphs, and show that a sequence of graphs has a convergent subsequence if and only if it has a subsequence satisfying a property we call uniform regularity of tails. Finally, we prove that every graphon is equivalent to a graphon on <span id=\"MathJax-Element-12-Frame\" class=\"MathJax\" tabindex=\"0\"><span id=\"MathJax-Span-76\" class=\"math\"><span id=\"MathJax-Span-77\" class=\"mrow\"><span id=\"MathJax-Span-78\" class=\"msubsup\"><span id=\"MathJax-Span-79\" class=\"texatom\"><span id=\"MathJax-Span-80\" class=\"mrow\"><span id=\"MathJax-Span-81\" class=\"mi\">R<\/span><\/span><\/span>\u00a0<span id=\"MathJax-Span-82\" class=\"mo\">+<\/span>\u00a0<\/span><\/span>\u00a0<\/span><\/span><script id=\"MathJax-Element-12\" type=\"math\/tex\">\/\/ <![CDATA[\n\\mathbb{R}_+\n\/\/ ]]><\/script>equipped with Lebesgue measure.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In a recent paper, Caron and Fox suggest a probabilistic model for sparse graphs which are exchangeable when associating each vertex with a time parameter in R\u00a0+\u00a0\u00a0. Here we show that by generalizing the classical definition of graphons as functions over probability spaces to functions over \u03c3\u00a0-finite measure spaces, we can model a large family [&hellip;]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"footnotes":""},"msr-content-type":[3],"msr-research-highlight":[],"research-area":[13561],"msr-publication-type":[193716],"msr-product-type":[],"msr-focus-area":[],"msr-platform":[],"msr-download-source":[],"msr-locale":[268875],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-316961","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-algorithms","msr-locale-en_us"],"msr_publishername":"","msr_edition":"","msr_affiliation":"","msr_published_date":"2016-01-26","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"","msr_chapter":"","msr_isbn":"","msr_journal":"","msr_volume":"","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"","msr_how_published":"","msr_notes":"","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":1,"msr_main_download":"","msr_publicationurl":"https:\/\/arxiv.org\/abs\/1601.07134","msr_doi":"","msr_publication_uploader":[{"type":"url","title":"https:\/\/arxiv.org\/abs\/1601.07134","viewUrl":false,"id":false,"label_id":0}],"msr_related_uploader":"","msr_attachments":[{"id":0,"url":"https:\/\/arxiv.org\/abs\/1601.07134"}],"msr-author-ordering":[{"type":"user_nicename","value":"borgs","user_id":31278,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=borgs"},{"type":"user_nicename","value":"jchayes","user_id":32200,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=jchayes"},{"type":"user_nicename","value":"cohn","user_id":31460,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=cohn"},{"type":"text","value":"Nina Holden","user_id":0,"rest_url":false}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[],"msr_project":[],"publication":[],"video":[],"download":[],"msr_publication_type":"inproceedings","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/316961"}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":1,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/316961\/revisions"}],"predecessor-version":[{"id":522604,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/316961\/revisions\/522604"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=316961"}],"wp:term":[{"taxonomy":"msr-content-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-content-type?post=316961"},{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=316961"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=316961"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=316961"},{"taxonomy":"msr-product-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-product-type?post=316961"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=316961"},{"taxonomy":"msr-platform","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-platform?post=316961"},{"taxonomy":"msr-download-source","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-download-source?post=316961"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=316961"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=316961"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=316961"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=316961"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=316961"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=316961"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}