<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Win Suen on Medium]]></title>
        <description><![CDATA[Stories by Win Suen on Medium]]></description>
        <link>https://medium.com/@wsuen?source=rss-f101ab538d21------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*m6IgOJMMn1GQiAOegZz2Lg.jpeg</url>
            <title>Stories by Win Suen on Medium</title>
            <link>https://medium.com/@wsuen?source=rss-f101ab538d21------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 02:01:12 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@wsuen/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Large-scale Graph Mining with Spark: Part 2]]></title>
            <link>https://medium.com/data-science/large-scale-graph-mining-with-spark-part-2-2c3d9ed15bb5?source=rss-f101ab538d21------2</link>
            <guid isPermaLink="false">https://medium.com/p/2c3d9ed15bb5</guid>
            <category><![CDATA[big-data]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[spark]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Win Suen]]></dc:creator>
            <pubDate>Tue, 09 Oct 2018 18:43:03 GMT</pubDate>
            <atom:updated>2026-07-16T20:40:19.291Z</atom:updated>
            <content:encoded><![CDATA[<p>A tutorial in 2 parts:</p><p><a href="https://medium.com/data-science/large-scale-graph-mining-with-spark-750995050656"><strong>Part 1</strong></a>: Graphs for unsupervised learning.</p><p><strong>Part 2 (you are here!)</strong>: How you can wield magical graph powers. We’ll talk about label propagation, Spark GraphFrames, and results. Repo with sample graph and notebook here: <a href="https://github.com/wsuen/pygotham2018_graphmining">https://github.com/wsuen/pygotham2018_graphmining</a></p><p>In Part 1 (<a href="https://towardsdatascience.com/large-scale-graph-mining-with-spark-750995050656">here</a>), we saw how to solve unsupervised machine learning problems with graphs because <strong>communities are clusters</strong>. We can leverage edges between nodes as an indicator of similarity or relation, the same way distances in a feature space is used for other types of clustering.</p><p>Here, we dive into the hows of <strong>community detection</strong>. We build and mine a large web graph, learning how to implement a community detection method called Label Propagation Algorithm (LPA) in Spark.</p><h3>Detect Communities with Label Propagation</h3><p>Though there are many community detection techniques, I focus only on one: <strong>label propagation</strong>. For an overview of other methods, I recommend <a href="https://arxiv.org/pdf/0906.0612.pdf">Santo Fortunato’s “Community Detection in Graphs”</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/440/0*1hEEs72y_1i4Uj9b.gif" /><figcaption>Graph with communities. From Girvan, Michelle, and Mark EJ Newman. “Community structure in social and biological networks.” <em>Proceedings of the national academy of sciences</em> 99.12 (2002): 7821–7826.</figcaption></figure><p>Enter the <strong>Label Propagation Algorithm (LPA)</strong> proposed by <a href="https://arxiv.org/pdf/0709.2938.pdf">Raghavan, Albert, and Kumara (2007)</a>. LPA is an iterative community detection solution whereby information “flows” through the graph based on underlying edge structure. Here’s how LPA works:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/863/1*3JWfnhL0xZQH497_j4piBA.png" /><figcaption>Raghavan, Usha Nandini, Réka Albert, and Soundar Kumara. “Near linear time algorithm to detect community structures in large-scale networks.” <em>Physical review E</em> 76.3 (2007): 036106.</figcaption></figure><ol><li>At the beginning, each node starts in its own community.</li><li>For each iteration, go through all your nodes randomly. For each node, update that node’s community label with the label of the majority of its neighbors. Randomly break any ties.</li><li>If nodes are now labelled with the majority label of their neighbors, the algorithm has achieved the stop criterion. If not, repeat step 2.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*z7UuSIqXYlQ2mU1pbDdYxA.png" /><figcaption>Image <a href="https://www.slideshare.net/yamaguchiyuto/pakdd15-talk">Source</a></figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/397/0*oZKLAIidU4S1t1yp.jpg" /><figcaption>Or just, you know, stay home? Image <a href="http://media.iwm.org.uk/iwm/mediaLib//138/media-138601/large.jp">Source</a>.</figcaption></figure><p>Label propagation makes sense <strong>intuitively</strong>. Let’s say one day at work, someone gets a <strong><em>cold</em></strong> and “propagates” the illness until <em>everyone</em> in your workplace is as sick as their neighbors. Meanwhile, employees of FoobarCo across the street catch and spread the <strong><em>flu</em></strong>. There’s not much contact between you and FoobarCo, so “propagation” stops when members of each community have caught the ailment du jour. Convergence achieved! Too bad about the sniffling and headaches though.</p><h3>Why use LPA?</h3><ul><li><strong>Labelled data is nice, but not required</strong>. Makes LPA suitable for our unsupervised machine learning use case.</li><li><strong>Parameter tuning is straightforward</strong>. LPA runs with a max_iterations parameter, and you can get some good results using the default value of 5. Raghavan and her coauthors tested LPA against several labelled networks. They discovered that at least 95% of nodes are correctly classified in 5 iterations.</li><li><strong>A priori number of clusters, cluster size, other metric not required</strong>. This is crucial if you don’t want to assume your graph has a certain structure or hierarchy. I had no a priori assumptions about the network structure of my web graph, the number of communities I had data for, or the expected sizes of these communities.</li><li><strong>Near linear runtime</strong>. Each iteration of LPA is O(m), linear in number of edges. The whole sequence of steps runs in near linear time, compared to O(n log n) or O(m+n) for some previous community detection solutions.</li><li><strong>Interpretability</strong>. When someone asks, you can explain why a node was grouped into a certain community.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/848/1*sbBPBPI6ZgFqDLGKwfPVIQ.png" /><figcaption>Language communities in Belgium mobile network (red = French, green = Dutch). Image from Blondel, Vincent D., et al. “Fast unfolding of communities in large networks.” <em>Journal of statistical mechanics: theory and experiment</em> 2008.10 (2008): P10008..</figcaption></figure><h3>Tool Selection</h3><p>First, a quick and non-exhaustive breakdown of the tools landscape. I divided the tools based on graph size, whether the library plays nicely with Python, and how easily I could generate simple visualizations.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*c1bLA6krLU8B6fknvQAA_Q.png" /><figcaption>Some common graph-mining tools.</figcaption></figure><p>A non-exhaustive menu of tools:</p><ul><li>For data that fit onto a single machine, the<strong> </strong><a href="https://networkx.github.io/"><strong>networkx</strong></a><strong> Python package</strong> is a good choice for easy-to-use graph exploration. It implements the most common algorithms (including label propagation, PageRank, maximum clique detection, and much more!). Simple visualizations are also possible.</li><li><a href="https://gephi.org/"><strong>Gephi</strong></a> is an open graph analysis tool. Gephi isn’t a Python package, but a standalone tool with a robust UI and impressive graph visualization capabilities. If you are working with smaller graphs, need strong visualizations, and prefer a UI to working in Python, give Gephi a try.</li><li>Spark has 2 graph libraries, <a href="https://spark.apache.org/docs/latest/graphx-programming-guide.html"><strong>GraphX</strong></a> and<strong> </strong><a href="https://graphframes.github.io/"><strong>GraphFrames</strong></a>. Spark is a great solution when you have graph data too large to fit onto a single machine (limited to amount of resources allocated to your Spark application), want to take advantage of parallel processing, and some of Spark’s built-in fault tolerance features. Pyspark, Spark’s Python API, is nicely suited for integrating into other libraries like scikit-learn, matplotlib, or networkx.</li><li><a href="https://giraph.apache.org/"><strong>Apache Giraph</strong></a> is the open-source implementation of <a href="https://kowshik.github.io/JPregel/pregel_paper.pdf">Pregel</a>, a graph processing architecture created by Google. Giraph had a higher barrier to entry compared to the previous solutions. While Giraph is very powerful for large scale graph analysis deployments, I chose something more lightweight that had both Scala and Python APIs.</li><li><strong>Neo4j</strong> is a graph database system. It does have a Python client, though you have to install Neo4j separately. Since my analysis was only a POC, I wanted to avoid maintaining and deploying an entirely separate tool that did not integrate with my existing code.</li><li>Finally, you could in theory <strong>implement</strong> <strong>your own solution.</strong> For initial data science exploration, I would discourage this. Many bespoke graph mining algorithms are for very specific use cases (for instance— be super efficient at graph clustering only, not other things). If you <em>do</em> need to work with very, very large datasets, first consider sampling your graph, filtering subgraphs of interest, inferring relationships from examples, basically anything to get more mileage from one of the existing tools.</li></ul><p>Given the data size I was working with, I chose <strong>Spark GraphFrames</strong>.</p><blockquote>Remember: the best graph library for your project depends on languages, graph size, how you store your graph data, and personal preference!</blockquote><h3>Building a Common Crawl Web Graph</h3><blockquote>Great! I’m fully convinced how awesome graphs are, and they’re the coolest things ever! How do I get started using community detection on real data?</blockquote><blockquote>-you</blockquote><h4>Steps</h4><p>1.<strong> Obtain data</strong>: The <a href="https://commoncrawl.org/the-data/get-started/">Common Crawl dataset</a> is an open web crawl corpus well-suited for web graph research. The crawl results are stored in <a href="https://en.wikipedia.org/wiki/Web_ARChive">WARC</a> (Web Archive) format. In addition to page contents, the dataset contains crawl date, headers used, and other metadata.</p><p>I sampled 100 files from the <a href="https://commoncrawl.org/2017/09/september-2017-crawl-archive-now-available/">September 2017 crawl</a>. The file warc.paths.gz contains pathnames; using these pathnames, download the respective files from s3.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/456/1*vfA6UVsdbUfAft_k4pDiIQ.png" /><figcaption>Indeed.</figcaption></figure><p>2. <strong>Parse and clean data</strong>: As a first pass, we want the html content of each page. For each page, we collect the URL <em>and</em> the URLs of any links to create our graph.</p><p>To<strong> extract edges</strong> from raw WARC files, I wrote some data cleaning code that probably should never see the light of day. At least it got the job done so I can focus on more fun things! My parsing code was written in Scala, but my demo is in pyspark. I used <a href="https://github.com/kris-sigur/jwat/blob/master/jwat-warc/src/main/java/org/jwat/warc/WarcReaderFactory.java">WarcReaderFactory</a> and <a href="http://jericho.htmlparser.net/docs/index.html">Jericho parser</a>. For python, a library like <a href="https://github.com/internetarchive/warc">warc</a> looks like it could cover your data munging needs.</p><p>After I had all the href links out of the html content,</p><ul><li>I drew <strong>edges between domains rather than full URLs</strong>. Instead of medium.com/foo/bar and medium.com/foobar, I only created one node, medium.com, that captured link relationships to and from other domains.</li><li>I filtered out <strong>loops</strong>. Loops are edges that connect a node to itself, not useful for my purposes. No edges drawn if medium.com/foobar linked to same domain, say, medium.com/placeholderpage.</li><li>I removed many of the most popular <strong>resource links, </strong>including popular CDNs, trackers, and assets. For my preliminary exploration, I only wanted to focus on webpages a human would likely visit.</li></ul><p>3. <strong>Initialize a Spark Context</strong>: For those following along at home, see demo at <a href="https://github.com/wsuen/pygotham2018_graphmining"><strong>https://github.com/wsuen/pygotham2018_graphmining</strong></a><strong>. </strong>This demo only runs on your local machine. You won’t get all the computational resources of a distributed cluster, but you <em>will</em> get an idea of how to get started with Spark GraphFrames.</p><p>I’ll be working with Spark 2.3. Import pyspark and other needed libraries, including graphframes. Then create a SparkContext, which will allow you to run a pyspark application.</p><pre># add GraphFrames package to spark-submit<br>import os<br>os.environ[&#39;PYSPARK_SUBMIT_ARGS&#39;] = &#39;--packages graphframes:graphframes:0.6.0-spark2.3-s_2.11 pyspark-shell&#39;</pre><pre>import pyspark</pre><pre># create SparkContext and Spark Session<br>sc = pyspark.SparkContext(&quot;local[*]&quot;)<br>spark = SparkSession.builder.appName(&#39;notebook&#39;).getOrCreate()</pre><pre># import GraphFrames<br>from graphframes import *</pre><p>4. <strong>Create a GraphFrame</strong>: Once you have your cleaned data, you can load your vertices and edges into Spark DataFrames.</p><ul><li>vertices contains an idfor each node, and the name of the node, which indicates the domain.</li><li>edges contains my directed edges, from source domain src to the domain the source links to, dst.</li></ul><pre># show 10 nodes<br>vertices.show(10)</pre><pre>+--------+----------------+<br>|      id|            name|<br>+--------+----------------+<br>|000db143|         msn.com|<br>|51a48ea2|tradedoubler.com|<br>|31312317|   microsoft.com|<br>|a45016f2|     outlook.com|<br>|2f5bf4c8|        bing.com|<br>+--------+----------------+<br>only showing top 5 rows</pre><pre># show 10 edges<br>edges.show(10)</pre><pre>+--------+--------+<br>|     src|     dst|<br>+--------+--------+<br>|000db143|51a48ea2|<br>|000db143|31312317|<br>|000db143|a45016f2|<br>|000db143|31312317|<br>|000db143|51a48ea2|<br>+--------+--------+<br>only showing top 5 rows</pre><p>You can then create a GraphFrame object with your vertices and edges. Voila! You have a graph!</p><pre># create GraphFrame<br>graph = GraphFrame(vertices, edges)</pre><p>5. <strong>Running LPA</strong>: One line of code allows you to run LPA. Here, I run LPA with 5 iterations (maxIter).</p><pre># run LPA with 5 iterations<br>communities = graph.labelPropagation(maxIter=5)</pre><pre>communities.persist().show(10)</pre><pre>+--------+--------------------+-------------+<br>|      id|                name|        label|<br>+--------+--------------------+-------------+<br>|407ae1cc|             coop.no| 781684047881|<br>|1b0357be|  buenacuerdo.com.ar|1245540515843|<br>|acc8136a|   toptenreviews.com|1537598291986|<br>|abdd63cd| liberoquotidiano.it| 317827579915|<br>|db5c0434|          meetme.com| 712964571162|<br>|0f8dff85|           ameblo.jp| 171798691842|<br>|b6b04a58|             tlnk.io|1632087572480|<br>|5bcfd421|         wowhead.com| 429496729618|<br>|b4d4008d|investingcontrari...| 919123001350|<br>|ce7a3185|   pokemoncentral.it|1511828488194|<br>+--------+--------------------+-------------+<br>only showing top 10 rows</pre><p>Running graph.labelPropagation() returns a DataFrame with nodes and a label denoting which community that node belongs in. You can use label to understand distribution of community size and zoom in on areas of interest. For example, to discover every other website in the same community as pokemoncentral.it (and honestly, who wouldn’t?), filter for all other nodes where label = 1511828488194.</p><h3>Results</h3><p>What happened when I ran LPA on my sample Common Crawl web graph?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*6lP2aOXvqf4-HruOD6mvNg.png" /></figure><ul><li>I began with <strong>over 15 million web sites </strong>in my raw data. That’s a lot of nodes, many of which contained redundant information. The cleaning process I described condensed the graph into fewer, more meaningful edges.</li><li>LPA discovered <strong>over 4,700 communities</strong>. However, over half of these communities contained only one or two nodes.</li><li>On the other end of the size spectrum, the <strong>largest community was over 3,500 different websites</strong>! To give an idea of scope, this was around 5% of the nodes in my final graph post-filtering.</li></ul><p>The extremes in community size illustrate one drawback of LPA. Too much convergence, and there could be clusters that are too large (caused by certain labels dominating densely connected networks). Too little convergence and you may get more, smaller communities that are less useful. I found that the most interesting clusters ended up being somewhere between the two extremes.</p><h4>Convergence and the small-world network effect</h4><p>In my dataset, LPA did <strong>converge around 5 iterations</strong>. You can see the number of communities level off at about 4,700. Raghavan and her colleagues showed this property with their labelled graphs as well.</p><p>One possible mechanism that explains this is the <em>small-world network effect</em> — the tendency for graphs to cluster, but also to have short path lengths compared to number of nodes. In other words, although graphs have clusters, but you would also expect to be able to travel from, say, one friend to another in your network within 5–6 jumps. Many real-world graphs, including the Internet and social networks, share this property. You may also know this as the <em>six degrees of separation</em> phenomenon.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Ya5R9VeKoHxTctTtJsjVMA.png" /><figcaption>Number of communities levels off after 5 iterations.</figcaption></figure><h4>Sample clusters</h4><p>At a coarse level, let’s see some samples clusters. As with traditional unsupervised clustering, the communities can be a mix of different sites, although <strong>there are topics of interest that we would not have discovered without LPA</strong>! From left to right:</p><ul><li><em>E-learning sites</em>: Sites related to or linking to e-learning pages. Time for me to find some new data science MOOCs!</li><li><em>Bedbug sites</em>: Sites related to real estate and bed bugs. All these sites used the same template/images, just with slightly different domain names. Don’t think I ever got to the bottom of this.</li><li><em>Star Wars community</em>: Sites that talk about Star Wars movies, events, and memorabilia frequently link to each other.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*jtdJTaXDfFlUFiqRPzwycQ.png" /></figure><p>It’s worth emphasizing that we obtained this clusters <strong>without </strong>text processing and feature selection, manual labelling, domain name features, or even knowing how many communities to find. We found communities of interest by <strong>leveraging the underlying network structure of the web graph!</strong></p><h3>Where to go from here</h3><p>I’ve barely scratched the surface of web graph communities. There are<em> so many</em> directions future research could go. For example:</p><ul><li>Layer in and propagate <strong>metadata</strong>: If we add information such as edge weights, link types, or external labels to the data, how well can we propagate this information through the graph?</li><li><strong>Remove/add nodes </strong>and measure impact on communities: I’m curious how adding or taking away nodes of high edge centrality change effectiveness of LPA and quality of resulting communities.</li><li>Observe web graph <strong>evolution over time</strong>: There is a new Common Crawl dataset each month! Would be interesting to see what clusters emerge over time. Conversely, what communities remain unchanged? As we know, the Internet isn’t static.</li></ul><p>The <a href="https://github.com/wsuen/pygotham2018_graphmining">Github repo for the demo</a> contains a small sample web graph of 10k nodes. There are also instructions for getting setup with Docker and running the pyspark notebooks. I hope this will be helpful in jump-starting experimentation with web graph data, and learning Spark GraphFrames for your own data science problems.</p><p>Happy exploring!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*GD89TLit2fuYM5Qb.jpg" /><figcaption>We’re pioneers! Graph pioneers. :) Image <a href="http://www.nasa.gov/centers/ames/news/2013/pioneer11-40-years.html">Source</a>.</figcaption></figure><h4>Acknowledgements</h4><p>Thanks to Dr. <a href="https://medium.com/u/b0a63e587893">Yana Volkovich</a> for deepening my learning of graph theory and being a great mentor. Thanks also to my other colleagues who gave feedback on my talk.</p><h4>References</h4><p>Adamic, Lada A., and Natalie Glance. “The political blogosphere and the 2004 US election: divided they blog.” Proceedings of the 3rd international workshop on Link discovery. ACM, 2005.<br> <br> Common Crawl dataset (September 2017).<br> <br> Farine, Damien R., et al. “Both nearest neighbours and long-term affiliates predict individual locations during collective movement in wild baboons.” <em>Scientific reports</em> 6 (2016): 27704<br> <br> Fortunato, Santo. “Community detection in graphs.” Physics reports 486.3–5 (2010): 75–174.<br> <br> Girvan, Michelle, and Mark EJ Newman. “Community structure in social and biological networks.” <em>Proceedings of the national academy of sciences</em> 99.12 (2002): 7821–7826.<br> <br> Leskovec, Jure, Anand Rajaraman, and Jeffrey David Ullman. <em>Mining of massive datasets</em>. Cambridge University Press, 2014.<br> <br> Raghavan, Usha Nandini, Réka Albert, and Soundar Kumara. “Near linear time algorithm to detect community structures in large-scale networks.” <em>Physical review</em><strong> </strong>E 76.3 (2007): 036106.<br> <br> Zachary karate club network dataset — KONECT, April 2017.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2c3d9ed15bb5" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/large-scale-graph-mining-with-spark-part-2-2c3d9ed15bb5">Large-scale Graph Mining with Spark: Part 2</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Large-scale Graph Mining with Spark: Part 1]]></title>
            <link>https://medium.com/data-science/large-scale-graph-mining-with-spark-750995050656?source=rss-f101ab538d21------2</link>
            <guid isPermaLink="false">https://medium.com/p/750995050656</guid>
            <category><![CDATA[spark]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[unsupervised-learning]]></category>
            <dc:creator><![CDATA[Win Suen]]></dc:creator>
            <pubDate>Sat, 06 Oct 2018 11:54:46 GMT</pubDate>
            <atom:updated>2026-07-16T20:40:59.241Z</atom:updated>
            <content:encoded><![CDATA[<p>This tutorial is divided into 2 parts:</p><p><strong>Part 1</strong> <strong>(you are here!)</strong>: Graphs for unsupervised learning.</p><p><a href="https://medium.com/data-science/large-scale-graph-mining-with-spark-part-2-2c3d9ed15bb5"><strong>Part 2 (click here</strong></a><strong>)</strong>: How you can wield magical graph powers. We’ll talk about label propagation, Spark GraphFrames, and results. Repo with sample graph and notebook here: <a href="https://github.com/wsuen/pygotham2018_graphmining">https://github.com/wsuen/pygotham2018_graphmining</a></p><p>I am also giving a talk on this topic at <a href="https://2018.pygotham.org/">PyGotham 2018</a>. :)</p><p>If you’re an engineer, you’ve most likely used graph data structures for implementing search and lookups algorithms. Have you also used them for machine learning problems?</p><h4><em>Why you care about graphs</em>?</h4><p>For data scientists, graphs are an incredibly fascinating topic of research. <strong>Labelled data is not always available</strong> for machine learning problems.<strong> </strong>Graphs can be powerful in these unsupervised contexts because <strong>they make the most of the data you have</strong> by leveraging the underlying substructures of your data.</p><p>For some machine learning problems, graphs can help you <strong>derive labelled data where there were none!</strong></p><p>I will teach you how to find <strong>clusters</strong> of related data points in graphs, using a set of methods known as<strong> community detection</strong>. We will use Spark GraphFrames for working with the large web graph I created from the September 2017 <a href="https://commoncrawl.org/the-data/">Common Crawl dataset</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/568/0*RyIenK4DYq7_XTrp.jpg" /><figcaption>Hey Boromir, have you tried community detection?</figcaption></figure><h3>Graphs 101</h3><p>A <em>graph</em> is a data structure for representing pairwise relationships between objects. Graphs are comprised of <em>nodes</em> (also called <em>vertices</em>) and <em>edges</em>. They can also be directed or undirected. For instance, Twitter follows can be a directed graph; the relationship is one-way. Just because I follow another user, doesn’t mean they follow me!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/464/1*dklRK02NzhGH1A7pI4O1gw.png" /><figcaption>Example of a directed graph.</figcaption></figure><p>I focus on web graphs. Web graphs capture link relationships between different websites. Each webpage is a node. If there is an html link from one page to another, draw an edge between those two nodes.</p><p>As you do this for more and more pages, you’ll notice substructures emerge. On real web data, these substructures can be quite large and complex!</p><p>Here’s a sample graph of all the pages under a single news site.</p><ul><li>Each light blue dot represents a single webpage, or <em>node</em>.</li><li>Each dark blue line represents a link between 2 pages, an <em>edge</em>.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*k8mvibWFxH6Bgo6eBBbxJw.png" /><figcaption>Subpage structure of a news site, generated by me using Gephi.</figcaption></figure><p>Even at this level, you can see dense <strong>clusters, </strong>or<strong> communities, </strong>of pages. You can spot nodes of higher degree centrality (pages with a large number of other pages linking to them).</p><p>If a single site is so dense with connections, imagine what we can mine from tens of thousands of sites!</p><h3>Why are graphs useful?</h3><blockquote>OK, that blue jellyfish thingy looks cool and all, but why even do all this?</blockquote><blockquote>-you</blockquote><p>There are many machine learning problems where <em>labels</em> (information on whether a data point is of one class or another) are not available. <strong>Unsupervised learning </strong>problems rely on finding similarities between data points to classify data into groups or clusters. Contrast this with supervised approaches, where data is labelled with the appropriate class and your model learns to differentiate classes using these labels.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*kmxAV-U407a_W30751OOtQ.png" /><figcaption>Source: <a href="http://beta.cambridgespark.com/courses/jpm/01-module.html">http://beta.cambridgespark.com/courses/jpm/01-module.html</a></figcaption></figure><p>Unsupervised learning is very useful when you can’t easily get more data, so you leverage more value out of what data you do have. Labels can be unavailable; even if they are, they may be too time-consuming or expensive to obtain. At the start of a machine learning problem, we also may not know exactly how many classes of objects we are looking for!</p><p>Here’s why we want graphs in our toolkit:</p><blockquote>Graphs allow us to get more value from our data in an unsupervised setting. We can get clusters from graphs.</blockquote><p><strong>Unsupervised learning is not unlike how humans learn!</strong> How did you first learn to tell the difference between dogs and cats? I’d guess for most people, no one sat your young self down and defined in precise taxonomic terms what a dog or cat was. Nor did your parents give you a corpus of thousands of cat and dog photos, each labelled, and ask you to draw a decision boundary that accurately divides the two classes of animals.</p><p>If your childhood was anything like mine, you probably met a few cats and met a few dogs. All the while, your young mind identified the salient differences between the 2 animals, as well as relevant common traits within each type of animal. Our brains are incredible at <strong>soaking up information</strong> from our environment, <strong>synthesizing</strong> this data, and <strong>formulating commonalities</strong> between the vastly different things we come across over the course of our lives.</p><p>There are many exciting <strong>applications of clustering</strong>. A few examples that come up in my work:</p><ul><li><strong>Predicting class labels</strong><em> </em>for datasets where there were no labels to learn from.</li><li>Generate grouping for<strong> audience segmentation and classification</strong>.</li><li>Build a <strong>recommender</strong> for similar web sites.</li><li>Find <strong>anomalies</strong>.</li><li>Use clusters as part of a <strong>semi-supervised machine learning ensemble</strong>. Clusters can help you extend know labels to nearby data points to increase training data size, or they can be used outright if labels are needed immediately until a secondary system can classify them.</li></ul><p>Here’s the kicker: in unsupervised learning, clusters are communities! And communities are clusters!</p><blockquote>Graph communities are clusters too!</blockquote><p>The only difference is, <strong>instead of using engineered features, you’re relying on the underlying network structure in your graph to derive clusters</strong>. Instead of a predefined distance metric, you use edges in your graph to measure similarity between data points.</p><p>I alluded to them earlier, so I should properly introduce communities. There is no single unique definition. One general description: a <em>community</em> is a substructure of a graph where nodes within the structure are more densely connected with each other than they are to nodes outside the substructure. The process of finding these communities, or clusters, is called<em> community detection</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/522/1*PtqBX4_zF8W4pv81hoU_KA.png" /><figcaption>Zachary karate club. Image from: KONECT, April 2017., dataset from original 1977 Zachary study.</figcaption></figure><p>The Zachary karate club dataset models the relationship of various members of a karate club. At one point, two members of the club had a conflict and the club ending up splitting into multiple communities. You can see the communities represented in 4 colors.</p><p>Think about how an unsupervised clustering algorithm works. You rely on the fact that some data points are closer than others in your selected feature space. The closer data are, the more similar they are. Based on a distance metric of choice, you then assign data into clusters of similar objects.</p><p>Graphs can help you achieve similar clusters, <em>without</em> the hassle of selecting features in the same way you might for traditional clustering.</p><h3>Wait, why does this work?</h3><p>Let’s dig deeper! What assumptions are we making that let us rely on community detection to find related nodes?</p><p>The most important one:</p><blockquote>Edges between nodes are not random.</blockquote><p>If your graph is <em>random</em>, none of this will work. However, most graphs in real life aren’t random; the edges are correlated in some way. Two mechanisms that help explain why this is the case:</p><ol><li><strong>Influence</strong>. <em>Nodes that are connected tend to share or spread traits.</em> Imagine several of your friends learned how amazing Spark was to use. From being connected with them, you may be more inclined to start using Spark as well. <strong>“All my friends are doing it, so I will too.”</strong></li><li><strong>Homophily</strong>.<em> Nodes that share a trait or have some sort of relationship are more likely to connect.</em> For example, if you and I both share an interest in python and graphs, we are more likely to be connected on a graph. This is also called <em>assortative mixing</em>. <strong>“Birds of a feather flock together.”</strong></li></ol><p>In real life, these mechanisms can and do interact!</p><p>Researchers have leveraged these phenomenon to model interesting problems with graphs. For example, Farine et al predicted a baboon’s location based on the locations of an animal’s strongest connections — a good application of <strong>influence</strong> to behavioral ecology.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/734/1*OpTfQDBM_JBjoT0Br_CIMA.png" /><figcaption>Farine, Damien R., et al. “Both nearest neighbours and long-term affiliates predict individual locations during collective movement in wild baboons.” <em>Scientific reports</em> 6 (2016): 27704</figcaption></figure><p><strong>Homophily</strong> is frequently used in social network research. Adamic and Glance did a fascinating study on political blogs during the 2004 election. They generated a graph showing how different blogs cited each other; the blue nodes represent liberal blogs, the red nodes are conservative blogs. Perhaps unsurprisingly, they discovered that blogs tend to cite other blogs of the same political leaning.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/502/1*TYQNmq4gDER53wgB_0RmQA.png" /><figcaption>Adamic, Lada A., and Natalie Glance. “The political blogosphere and the 2004 US election: divided they blog.” <em>Proceedings of the 3rd international workshop on Link discovery</em>. ACM, 2005.</figcaption></figure><p>Even on a personal level, homophily makes sense. Chances are your own friend network is comprised of people who may be the same age as you, live in the same town, have the same hobbies, or went to the same school! You’re a living, breathing example of homophily at work. Feel free to add that to your resume!</p><p>We’ve talked about how graphs can leverage the underlying network characteristics of your data to return clusters. In web graphs, these clusters are super useful for applications such as recommender systems, audience segments, anomaly detection, and much more.</p><p>In <a href="https://towardsdatascience.com/large-scale-graph-mining-with-spark-part-2-2c3d9ed15bb5">Part 2</a> (posted <a href="https://towardsdatascience.com/large-scale-graph-mining-with-spark-part-2-2c3d9ed15bb5">here</a>), we’ll dive into community detection techniques, and learn how to derive clusters from a web graph we create using the Common Crawl dataset.</p><h4>Acknowledgements</h4><p>Thanks to Dr. <a href="https://medium.com/u/b0a63e587893">Yana Volkovich</a> for deepening my learning of graph theory and being a great mentor. Thanks also to my other colleagues who gave feedback on my talk.</p><h4>References</h4><p>Adamic, Lada A., and Natalie Glance. “The political blogosphere and the 2004 US election: divided they blog.” Proceedings of the 3rd international workshop on Link discovery. ACM, 2005.<br> <br> Common Crawl dataset (September 2017).<br> <br> Farine, Damien R., et al. “Both nearest neighbours and long-term affiliates predict individual locations during collective movement in wild baboons.” <em>Scientific reports</em> 6 (2016): 27704<br> <br> Fortunato, Santo. “Community detection in graphs.” Physics reports 486.3–5 (2010): 75–174.<br> <br> Girvan, Michelle, and Mark EJ Newman. “Community structure in social and biological networks.” <em>Proceedings of the national academy of sciences</em> 99.12 (2002): 7821–7826.<br> <br> Leskovec, Jure, Anand Rajaraman, and Jeffrey David Ullman. <em>Mining of massive datasets</em>. Cambridge University Press, 2014.<br> <br> Raghavan, Usha Nandini, Réka Albert, and Soundar Kumara. “Near linear time algorithm to detect community structures in large-scale networks.” <em>Physical review</em><strong> </strong>E 76.3 (2007): 036106.<br> <br> Zachary karate club network dataset — KONECT, April 2017.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=750995050656" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/large-scale-graph-mining-with-spark-750995050656">Large-scale Graph Mining with Spark: Part 1</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[KDD 2018 Top 10 Paperlist]]></title>
            <link>https://medium.com/@wsuen/wins-kdd-2018-top-10-c0be4e0af4ac?source=rss-f101ab538d21------2</link>
            <guid isPermaLink="false">https://medium.com/p/c0be4e0af4ac</guid>
            <category><![CDATA[statistics]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[recommendations]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[ai]]></category>
            <dc:creator><![CDATA[Win Suen]]></dc:creator>
            <pubDate>Wed, 12 Sep 2018 00:46:38 GMT</pubDate>
            <atom:updated>2018-09-14T18:12:32.808Z</atom:updated>
            <content:encoded><![CDATA[<p>From deep within my post-KDD paper pile, I’m sharing some of the cool research I came across. Extremely biased sampling, because I have my own favorite topics and skewed towards more applied than theoretical talks.</p><h3>My KDD 2018 Top 10 Hits <a href="https://emojipedia.org/musical-note/">🎵</a></h3><ol><li><strong>Recommender systems: </strong>Many novel applications from multiple companies! <a href="https://dl.acm.org/citation.cfm?id=3219885">AirBnb</a>, <a href="http://www.kdd.org/kdd2018/accepted-papers/view/qr-a-two-stage-approach-toward-interactive-recommendation">Google/YouTube</a>, <a href="https://medium.com/@Pinterest_Engineering/pinsage-a-new-graph-convolutional-neural-network-for-web-scale-recommender-systems-88795a107f48">Pinterest</a>, <a href="http://www.kdd.org/kdd2018/accepted-papers/view/learning-tree-based-deep-model-for-recommender-systems">Alibaba</a>.</li><li><strong>Beyond bipartite graph matching</strong>: Google Algorithms Research team walked through of some more advanced algorithms for <a href="https://orc.mit.edu/events/robust-allocation-and-online-bundling-online-advertising">solving online ad delivery problems in practice</a>.</li><li><strong>Large-scale graph mining</strong>: Google Algorithms Research team also presented <a href="https://sites.google.com/view/lsga/home">on their internal large scale graph mining tool</a> that leverages MapReduce framework for filtering, maximal matching, balanced partitioning, and more.</li><li><a href="http://www.kdd.org/kdd2018/accepted-papers/view/rosetta-large-scale-system-for-text-detection-and-recognition-in-images">Rosetta — large scale system for text detection and recognition in images</a>: <strong>Large-scale, real-time OCR</strong> is hard. First, find text (bounding boxes). Then, find text within rectangles with CNN. Training data selection and metric selection were critical lessons. For instance, they discovered some training images didn’t represent text-on-image examples in production!</li><li><a href="https://dstillery.com/wp-content/uploads/resources/white_paper/Audience-Size-Forecasting-KDD2018-Whitepaper.pdf">Audience Size Forecasting</a> (Dstillery): Applied <strong>cardinality estimation (MinHash and Bloom filters)</strong> to estimate avails for campaigns, enabling speedy estimates for large datasets.</li><li><a href="https://gvrkiran.github.io/polarization/">Polarization on social media workshop</a>. Would recommend especially “<strong>polarization models</strong>” section though parts are math heavy. Also “mitigating polarization.”</li><li><a href="https://dl.acm.org/citation.cfm?id=3219830">Customized regression model for Airbnb Dynamic Pricing</a>: Turns out, Airbnb has some weird listings (treehouses, castles, dungeons)! How do you recommend pricing when <strong>no 2 listings are identical</strong>? Airbnb’s pricing system solution into account booking probability, strategy, and personalized recommendations.</li><li><a href="https://dl.acm.org/citation.cfm?id=3219819.3219847">Online parameter selection for web-based rankings</a>: Accounting for competing metrics in ranking what shows up on your LinkedIn news feed when optimal values for these metrics change over time. Good if you like hearing about real-world <strong>challenges of recommenders and rankings</strong>.</li><li><strong>Seq2seq</strong> tutorial from the Github team: <a href="https://kddseq2seq.com/">https://kddseq2seq.com/</a>. Have been wanting to learn more about this topic; this workshop was a nice chance to do that.</li><li>Didi used <a href="http://www.kdd.org/kdd2018/accepted-papers/view/efficient-large-scale-fleet-management-via-multi-agent-deep-reinforcement-l">graph matching framework for representing ride dispatch challenges</a>. <strong>Reinforcement learning</strong> solution maximized global resource use across their ride-hailing product, bumping performance by 0.5–5% without negatively impacting user experience.</li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c0be4e0af4ac" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>