Description
1. Assignment Overview The goal of this assignment is to let you be familiar with matrix representation of graph, graph Laplacian, and spectral methods. They are covered in Week7 slides, Page 59. 2. Requirements 2.1 Programming Environment Python 3.6. You could use spark, numpy, scipy, pandas, sklearn, matplotlib. You are NOT supposed to use networkx for any purpose in this homework. The goal of the homework is let you familiar with matrix representation of graph, so please build these matrix yourself. If you need to use additional libraries, you must have approval from TA and declare it in requirements.txt There will be a 20% penalty if we cannot run your code due to Python version inconsistency or undeclared 3rd party library. 2.2 Write your own code Do not share code with other students! For this assignment to be an effective learning experience, you must write your own code! We emphasize this point because you will be able to find Python implementations of some of the required functions on the web. Please do not look for or at any such code! TAs will combine all the code we can find from the web (e.g., Github) as well as other students’ code from this and other (previous) sections for plagiarism detection. We will report all detected plagiarism. 2.3 What you need to turn in The submission format will be the same as homework 2. Your submission must be a zip file with name: firstname_lastname_hw4.zip (all lowercase). You need to pack the following files in the zip: a. Six files, named: (all lowercase) firstname_lastname_task1.txt, firstname_lastname_task2.txt, firstname_lastname_task3.py, firstname_lastname_task4.py, firstname_lastname_task5.py, firstname_lastname_task6.py, Note the first 2 are txt files, the last 4 are python scripts. 3. Tasks 3.1 Task 1: 2-way spectral graph partition on a small graph (5 pts) Study slides, especially page 80. Then perform 2-way graph partition on the unweighted, undirected graph below: Task: 1. Compute its Laplacian matrix (nodes sorted by node index, in increasing order) 2. Calculate the second smallest eigenvector 3. Do graph partition. Output format: Create firstname_lastname_task1.txt First 12 rows: Laplacian matrix. Numbers are separated by comma. 13 th row: second smallest eigenvector. Numbers are separated by comma 14 th row: partition result. Written in two brackets, separated by comma (see page 80). Sorted by node index in each bracket and between brackets. Note: 1. The partition result is obvious in visual, but you should be able to get it from eigenvector. 2. It could be computed by numpy.linalg.eig. Please refer to the document for its usage. Note its return values are NOT sorted by eigenvalue. 3. Don’t worry about rounding or scaling of eigenvectors. 3.2 Task 2: 4-way spectral graph partition on a small graph (5 pts) Study slides, especially page 91, 83. If we represent the eigenvectors in the layout of page 83, each row is an embedding of a node. We found similar nodes (eg, node 2 and 5) have similar embedding! So, the complex graph topology has been represented in a simple vector space, and algorithms like clustering, classification could be used on them easily. Practically, columns corresponding to zero or negative eigenvalue should not be included in the embedding, as they will be a constant for all nodes. (Think about why). The column corresponding to smaller positive eigenvalue contains more useful information, so usually, only the left few columns are used as embedding. Task: 1. Compute node embedding for the same graph as in task 1. Only keep the first 3 dimensions. 2. Use k-means on the embedding. Nodes belong to the same cluster in the embedding space also belong to the same cluster in the original graph. Output format: Create firstname_lastname_task2.txt First 12 rows: Node embedding. Numbers are separated by comma. 3 numbers in each row. (nodes sorted by node index, in increasing order) 13 th -16th row: Clustering centers. Numbers are separated by comma. 3 numbers in each row. Row order doesn’t matter 17th row: Partition result. Written in 4 brackets, separated by comma (see page 80). Sorted by node index in each bracket and between brackets. Note: 1. The partition result is obvious in visual, but you should be able to get it from k-means. 2. You could use sklearn.cluster.KMeans or write your own, in all tasks. 3.3 Task 3: k-way spectral graph partition on a large graph (15pts) Now, let’s apply the spectral graph partition algorithm on some real-world data, for example, a graph of email communication. (https://snap.stanford.edu/data/email-Eucore.html). Open the link for more information about the dataset. The dataset is included in the data folder. It includes two files, email-Eu-core.txt contains edge information, each line represents an edge between two nodes. File email- Eu-core-department-labels.txt contains node label information, each line specifies the label of a node, 42 labels in total. They are ground truth cluster labels. Task: Clustering a large graph into k clusters. Input format: python firstname_lastname_task3.py edge_filename: Path to edge file, e.g.: data/email-Eu-core.txt output_filename: Path to the the output file k: Number of clusters, e.g.: 42 Output format: Similar to email-Eu-core-department-labels.txt, the second column should be predicted cluster label. The absolute value of the labels doesn’t matter. See the note #5 below. Note: 1. You should read the input and output path from the command line argument. We may test your code on a different dataset. 2. The dataset is directed, but this simple spectral method requires the graph to be undirected! Add edge in both directions when you construct the graph. Spectral methods for directed graph is possible but much more complicated. 3. If computed eigen value/vector are complex number, you should convert it to real number via np.real. 4. You need to decide which eigenvectors should be included in the node embedding. Bigger embedding is not necessarily better, it may be noisier. Hint: Those corresponding to smaller positive eigenvalue contains more useful information. 5. Clustering is unsupervised learning: you should NOT read ground truth cluster label in your submitted program! 6. The evaluation should be done in another program (no need to submit). Quality of clustering could be evaluated by Adjusted Rand index (sklearn.metrics. adjusted_rand_score). This metric is independent of the absolute values of the labels: a permutation of the class or cluster label values won’t change the score value in any way. Its range is [-1, 1]. A score of 1 means perfect match, a positive score means two clustering results are similar, a 0 means they are irrelevant. Grading: 1. 20 points in total 2. 0 point if your spectral graph partition is provided by a library. But you could use sklearn to perform k-means, and/or other auxiliary steps. 3. As long as your Adjusted Rand index >= 0.06, you get full points. Since k-means algorithm has randomness in nature, we will run your program multiple times and take the best result. 3.4 Task 4: Node classification based on spectral embedding (10pts) Task: Perform node classification based on learned spectral embedding. A sample train/test split is provided as labels_train.csv/labels_test.csv Input format: python firstname_lastname_task4.py edge_filename: Path to edge file, e.g.: data/email-Eu-core.txt label_train_filename: Path to train label file. e.g.: data/labels_train.csv label_test_filename: Path to test label file. e.g.: data/labels_test.csv output_filename: Path to the output file In labels_test.csv, the second column is filled with 0. If you want to evaluate your model’s performance, you need to compare your prediction with labels_test_truth.csv Output format: Similar to labels_test_truth.csv, the second column should be your model’s prediction. This time the absolute value of the labels DO matter. You can’t permutate labels. Note: 1. Same as task 3, Note 1-3 2. We have performed node classification in homework3, that is based on the external features on each node, like tweets they tweeted. Here the node classification is solely based on graph topology represented in spectral embedding. 3. You could compute the spectral embedding for all nodes at once, then train the classifier only with nodes in the training set. You don’t have to (and actually impossible to) compute embedding for training nodes and test nodes separately. Graph is not like other data that each entry could be processed independently, graph should considered as an indivisible object, that removing one node will change embedding for all other nodes too. 4. You could use k-nearest neighbors classifier. (sklearn.neighbors. KNeighborsClassifier) Other classifiers like logistic regression are also fine. 5. Think about the difference between supervised and unsupervised learning, k-nearest neighbors, and k-means before proceeds. 6. Node classification is supervised learning: you could read ground truth label information from the training set, but NOT from test set. 7. The optimal embedding dimension may be different for classification task and clustering task. 8. The evaluation should be done in another program (no need to submit). You could use accuracy (sklearn.metrics.accuracy_score). Grading: 1. 10 points in total 2. 0 point if your spectral embedding is provided by a library. But you could use sklearn’s KNN or other classifiers, and/or other auxiliary steps. 3. As long as your Test Accuracy >= 0.6, you get full points. 3.5 Task 5: Spectral graph partition on non-graph data (15pts) Correct partition Incorrect partition by k-means See the above example of non-spherical data (provide in data/non-spherical.json). K-means method couldn’t partition them correctly. However, if construct a graph based on these data, and partition the graph nodes using spectral methods, they could be partitioned correctly. The idea is constructing a k-nearest neighbor graph: Each data point corresponding to a node and is connected to k closest nodes measured in Euclidean distance. Construct an adjacency matrix based on the graph. Then perform spectral graph partition. For nodes in the same graph partition, their original data points should be in the same partition. Task: Perform spectral graph partition on non-spherical data. Input format: python firstname_lastname_task5.py edge_filename: Path to edge file, e.g.: data/non-spherical.json output_filename: Path to output file. It will have .png as its suffix. Output format: 1. A plot (in png format) showing the data points and coloring the clustering result. Other settings like size, color used, labels don’t matter. Please refer to the “Correct partition” figure showing above. Make sure your program saves a figure rather than displaying it (via plt.savefig) Note: 1. You should read the input and output path from the command line argument. We may test your code on a different dataset, but they will always contain 2 clusters. 2. The constructed adjacency matrix should satisfy the property listed in slide page 75: Zero on diagonal and symmetric. 3. You could find k-nearest nodes using a double loop, or use sklearn.neighbors. NearestNeighbors or sklearn.neighbors.kneighbors_graph. Think about the connection between NearestNeighbors and KNeighborsClassifier 4. The optimal embedding dimension may be different in this task. Since we are doing 2- way clustering, maybe we don’t need to construct embedding at all? (Recall task 1) 3.6 Task 6: Identify important nodes in a graph via page rank (10pts) Page rank is initially used to find important webpages, but it generalizes to find important nodes in any type of graph, for example, important persons in an email communication graph. (reusing the dataset in task 3) The same hypothesis in page rank could be used in email communication: if a lot of emails are sending to a person, then that person is very likely to be important. Getting an email from an important person makes you more likely to be an important person. Task: Find the 20 most important nodes in a graph via page rank. Use random teleport with 𝛽 = 0.8 and always teleport for dead ends. Input format: python firstname_lastname_task6.py edge_filename: Path to edge file, e.g.: data/email-Eu-core.txt output_filename: Path to output file Output format: A text file contains node index of the 20 most important nodes, sorted by their importance in decreasing order, one node index per line. Note: 1. You should read the input and output path from the command line argument. We may test your code on a different dataset. 2. You MUST ignore self-loop. In general, adding self-loop or not are both fine in page rank. But here, the graph is not strongly connected, couldn’t use page rank algorithm. But by ignoring self-loop, components will get connected via random teleport. 3. The graph here is very small, we could compute eigenvectors directly, and don’t have to use a random walk-based method. The web graph is so large that it’s impractical to perform eigen decomposition, so a random walk-based method is necessary. 4. The dataset is directed, you should construct a directed graph, and the transition matrix is NOT symmetry. Grading: 1. 10 points in total 2. 0 point if your page rank is provided by a library. 3. Your answer should exactly match the solution. If not, 5 points deducted, and we will inspect your code to determine the remaining points. Hint: The two most important nodes are node #160 and #62. 4. Grading Criteria The perfect score for this assignment is 60 points. Assignment Submission Policy Homework assignments are due at 11:59 pm on the due date and should be submitted in Blackboard. Every student has FIVE free late days for the homework assignments. You can use these five days for any reason separately or together to avoid the late penalty. There will be no other extensions for any reason. You cannot use the free late days after the last day of the class. You can submit homework up to one week late, but you will lose 20% of the possible points for the assignment. After one week, the assignment cannot be submitted. (% penalty = % penalty of possible points you get) 1. You can use your free 5-day extension separately or together. 2. If we cannot run your programs with the command we specified, there will be 80% penalty. 3. If your program cannot run with the required Python/Spark versions, there will be 20% penalty. 4. If our grading program cannot find a specified tag, there will be no point for this question. 5. If the outputs of your program are unsorted or partially sorted, there will be 50% penalty. 6. If the header of the output file is missing, there will be 10% penalty. 7. We can regrade on your assignments within seven days once the scores are released. No argue after one week. There will be 20% penalty if our grading is correct. 8. There will be 20% penalty for late submission within a week and no point after a week. 9. There will be no point if the total execution time exceeds 15 minutes.
