Papers^γ

Interesting paper around the question: "Can machine learning be used to cheaply detect and exploit structure in practically relevant instances of NP-hard problems that come from the same distribution?". The problem of listing all maximum cliques in a graph is considered. A binary classifier is trained to discriminate between a node belonging to a maximum clique and a node that do not belong to a maximum clique: logistic regression is used with node features such as the total number of edges, node degree, clustering coefficient and trained on a set of graphs. The classifier is then used to prune the search space of a test graph: nodes that are labeled "not belonging to a maximum clique" by the classifier are removed. Some speedup is observed when comparing the running time of state-of-the-art methods on the original graph (or on a graph pruned using a baseline pruning method (degree pruning)) and on the pruned graph. # A more challenging baseline pruning For the baseline pruning: a heuristic is used to find a large clique and then if the found clique has size $k$, all nodes of degree $k-2$ or less are removed. It would have been better to iteratively remove all nodes of degree $k-2$ or less till there is no more such nodes and thus only keeping the $(k-1)$-core of the graph (it seems that only nodes of degree $k-2$ or less in the original graphs are removed). That would lead to much smaller graphs and a more challenging baseline pruning. How good is this k-core pruning? In table 1, the speedup obtained with degree pruning is not reported for igraph and EmMCE. Is the speedup obtained by the proposed pruning much better than the one obtained by the degree pruning for these two programs? # Setting the confidence threshold The confidence threshold used for the logistic regression classifier is arbitrarily fixed to $q=0.55$. If $q$ is higher, then the list of maximum cliques computed on the pruned graph may not be correct (i.e. it may not be the same as in the original graph as nodes belonging to a maximum clique would be pruned). It is not clear to me why all results are exact in table 1: just luck? How about using $q=0.6$ or $0.7$? Parameter sensitivity is not discussed. Note that if there is a single maximum clique of size $k$ and many cliques of size $k-1$ then removing a node from the maximum clique will completely change the output (which may then be many cliques of size $k-1$ instead of a single clique of size $k$).

Very good article from GroupLens team about the diversity narrowing effect and the role of the recommender system. Experimental measurements on the MovieLens platform, the content of movies is described with tag-genome, the RS is an item-item collaborative filtering. ### Introduction ##### two research questions : - Do recommender systems expose users to narrower content over time? - How does the experience of users who take recommendations differ from that of users who do not regularly take recommendations? ##### method - users in two categories (following / ignoring ~ control group) - then sort of A/B testing to measure consumption diversity and enjoyment at the individual level ##### 4 contributions : - method to analyze the effects of RS on users - give quantitative proofs that users using RS have a better experience than others - show that diversity reduction effect is small - show that users using RS tend to consume more divers contents ### Related work - Pariser (11) on filter bubble - Tetlock (16) measures bias induce by bubbles (among economists) - Sunstein (15) thinks that personnalization tends to reduce the space of shared experience among users - Negroponte (MIT MediaLab co-founder) defends that algorithms may also open horizons - Linden (Amazon RS contributer, 5) thinks that reco can generate some form of serendipity and oppose to Pariser's thesis - Fleder et al (2) use simulation to show that RS tend to uniform experience / Hosanagar et al (3) use measurements, but limitations to these studies, e.g. simplistic model of human behavior (Fleder) ### Data & metrics ##### Dataset MovieLens (September 2013) : - 220.000 users - 20M ratings, 20000 movies - RS (item-item Collaborating Filtering, similar to Ama) propose "top picks" per user (15 default value) ##### Tag-genome to describe movie content - information space which describes movies with tags given by users - 9500 movies in tag-genome (april 2013) and 1100 tags => 10-11M pairs ##### Time period - 21 months from Feb 2008 to Aug 2010 (because less missing data) ##### preprocessing : - 15 first ratings taken out (platform propositions) - then first 3 months taken out (as many ratings are "catching up" + to give users time to get used to ML and ML to get info from the user ##### recommendation blocks definition : - several possibilities: per login session, per periods of time, but as users don't have the same activity - => blocks of 10 consecutive ratings, 10 is roughly the median of number of ratings per 3 months ##### users and items : - only users who have their first rating during the period of interest and who have at least 3 rating blocks => 1400 users with 3 to 200 rating blocks - 173,000 ratings on 10500 movies, all in tag genome (small inconsistency: there is only 9500 movies in the tag-genome ##### Identifying consumed recommendations in a rating block - groups based on the number of reco followed by users - criterion to consider that reco followed: in the list of top picks between 3h and 3 months before evaluation ##### Ignoring group vs following group - 2 groups of users - pb: some users take a lot of reco during a period and then very few - => rank users depending on the proportion of rating blocks during which they followed a reco (Fig4) - then if >50% : following group (286 users); if 0% : ignoring group (430 users) (seems quite ad hoc, but makes sense as differences are not very large and following reco must be quite rare) ##### Measuring content diversity: tag genome (see figure 5) - matrix movie-tag with 1 to 5 relevance score - movie is then a vector of scores - distance between movies is euclidean distance in this space (rather than cosine similarity because of matrix density) - order of magnitudes: min distance 5.1 (Halloween 4 - Halloween 5), max distance 44.2 (Matrix - Paris was a woman), mean 23.4 - authors defend that tag-genome is very expressive (more than cosine similarity), also benefits from the continuous input from users (illustrate on examples) ##### Measuring the effect of recommender systems ###### # content diversity metrics (standard) - average pairwise distance of the movies in the list - maximum pairwise distance of the movies in the list - on recommended movies (15 top picks) - on rated movies - more or less normally distributed (see fig6) ###### # user experience : - average rating per user - more or less normally distributed ###### # analysis : - mean shift for users in both groups - measure difference between groups and within group at different times - within group : use standard t-test (as same size) - between groups : use Welch t-tests (as different sizes) ### Results ##### Research Question 1: do RS expose users to narrower content over time ? - diversity on recommended movies: see tab2 - statistically significant drop on following group - significant drop (?) on ignoring group - following more diverse than ignoring (significant), but gap narrows over time ##### Research Question 2: does the experience of users who take recommendations differ from that of users who do not regularly take recommendations ? - diversity on rated movies using mean distance: see tab3 - beginning: no significant difference - end: significant drop for both groups - diversity on rated movies using max distance: see tab4 - same trend - enjoyment evaluated with rating between first and last block for both groups: see tab5 - following group gives higher ratings, and the rating drop is lower in following than in ignoring group - similar trend with rating means (see tab7) - refined analysis in tab6 with ratings depending on the fact that movies rated are recommended or not => better experience if movie recommended (complement) - rank together all blocks of all groups at all times per increasing average rating - => block located in this ranking with its percentile (ex: first block, ignoring group ~ 63rd percentile) - in tab8: percentile drop for both groups => percentile drop for ignoring is high (-19) not in the following (-1) ### Discussion ##### summary - diversity tends to narrow in anyway over time - effect subdued for the group which follows reco - users following reco get more diverse recommendations - ratings seem to encourage RS to broaden recommendations ##### prospects - is there a natural trend to narrow consumption diversity? - they think that item-item CF slows this effect down - the RS can also inform the user of his or her consumption diversity - finally RS can be designed to intentionally force diversity ##### limitations - restriction to top picks - restriction to one dataset and one system (item-item CF) (note: on current platform (May 2019), 4 different RS: peasant/bard/warrior/wizard, the one described in the article seems to be warrior, default RS)

Very well written paper proposing an interesting algorithm to solve (lossless and lossy) graph summarization problems (cf problem definition). The algorithm is parallelizable in a shared memory environment and can be distributed using mapreduce. The theoretical analysis is sound and shows that the algorithm has a linear time complexity in practical scenarios. The experimental evaluation shows that the algorithm achieves a better trade-of between time and quality than existing approaches. In particular, the algorithm is faster than the greedy heuristic while leading to similar results. The proposed algorithm can be seen as a scalable implementation of the greedy heuristic: using shingle hashing of nodes allows to prune the search space and consider only some relevant pairs of nodes instead of considering all pairs of nodes (or all pairs of nodes sharing at least one neighbor). ### No theoretical approximation guarantees: The graph summarization problem is well defined and has an optimal solution. The proposed algorithm does not seem to have any theoretical approximation guarantees. According to the experimental evaluation, the quality of the output is similar to the one of the (straightforward) greedy heuristic, but we do not know how far from optimality it is. Is there any algorithm for the problem with some theoretical approximation guarantees? ### Absolute performance: While the performance relatively to other algorithms is good, the absolute performance of the algorithm is somehow disappointing. Figure 3: we see that the size of the output graphs is larger than 40% the size of the input graphs (in terms of (super) edges) for all graphs (and in many cases larger than 70%) except for the two web graphs (it is known that web graphs can be compressed efficiently (cf the webgraph framework)) and surprisingly a protein interaction graph (only 10% of edges are kept).

Very good article on segregation phenomena as measured on online news consumption. ### Introduction * question asked: impact of technological changes on ideological segregation * two conflicting hypotheses: either consumption increased of like-minded opinions (echo chambers) - ex: Sunstein, 2009, or access to broader spectrum of information implies more consumption of opposite opinions - ex: Benkler, 2006 * work proposed: study 50,000 anon users from the US who regularly consume online news * ML algorithms identify hard news, then divide them in descriptive reporting vs opinion pieces * defines ideological segregation as the difference of the expected share of conservative news consumption between two random individuals * observes that segregation tends to be higher when users come from social media * observes that individual users tend to read news only from one side of the spectrum * observes counter-intuitively that reading of opposite sides tends to append more often from channels with highest segregation (social, search) * descriptive reporting corresponds to about 75% of the traffic * online news consumption still dominated by mainstream medias ### Data and methods * data collection: from Bing toolbar for IE => 1.2M US citizens from March to May 2013 * focus son 50,000 regular newsreaders => 2.3 billion pages (median:~1000 pages per user) * selection bias: individuals who accept to share their info ; IE users in general more aged * test representativeness by measuring Spearman coefficient of consumption on the dataset with Quantcast and Alexa rankings: 0.67 et 0.7 ; while Spearman(Quantcast, Alexa) ~ 0.64 ##### identifying news and opinion articles : * use Open Directory Project => identify ~8000 domains as news, politics, etc. * contain major national sources, important regional outlets, important blogs * isolate 4.1M articles, but not always relevant in terms of ideology (e.g. sports, weather,...) => isolate with ML 1.9M of "front section news", among which 200,000 opinion stories (Tab1 indicates terms highly predictive of the categories) ##### measuring the political slant of publishers * impossible to do it manually, but no easy way to do it automatically for all 1.9M articles => assign slant of the outlet * use outlet readers slant, inferred from vote at the presidential election, which is inferred from the location through the IP address * robustness check: Tab2 lists top20 consistent to common knowledge and consistent with previous studies (Gentzkow et Shapiro, 2011) ##### inferring consumption channels * 4 info channels: direct (visit the domain), social (TB, Twitter, mail), search (Google, Bing, Yahoo), aggregator (Google news) * use the referrer domain to define the channel (interpretations pb to solve, eg if ref=Facebook and 4 articles read, are all of them from social origin?) ##### limiting to active news consumers : * limit = 10 news articles and 2 opinion pieces during the 3 months period => from 1.2M to 50.000 users (so 4%) * RK: some conclusions are still true with looser threshold ### Results #### overall segregation * individual polarity = average from polarities of the outlets consumed * segregation = distance between polarity scores * naive estimation insufficient => use of a hierarchical bayesian model ##### bayesian model * process standard in the literature? see Gelman et Hill, 2007 * look for sigma_d global dispersion * polarity of user i supposed to be distributed according to a normal law with latent variables * evaluate parameters using approximate marginal likelihood estimate ##### segregation * distribution of users polarity obtained: see fig2 * segregation = sqrt(2).sigma_p = 0.11 * 2/3 of the scores are between 0.41 and 0.54 => most people are moderate #### segregation by channel and article subjectivity * pb of data scarcity exacerbated by dividing data into channels * but for a user polarity probably correlated for different channels * same type of bayesian model but with a 8 dimension vector * 8 dimensions = 4 channels * 2 classes (opinion and report) ##### results on fig3 : segregation per channel * trend: segregation effect stronger for opinions * trend: social media tend to increase segregation effects * strongest segregation for search ; possible explanations: 1) search formulations are already oriented, 2) when search formulated, users read like-minded medias * as access to a large variety of media comes from the technology, they cause the segregation effect * trend: aggregators => less segregation * interpretation of overall segregation effect weakness: even after pre-filtering, many news are not polarizing * general conclusion: there is a filter bubble effect but still limited #### ideological isolation ##### two conflicting hypotheses * moderate polarization and individuals consume a large spectrum of opinions * moderate polarization but individuals consume a thin spectrum of opinions * dispersion sigma_d=0.06, very small => rather second hypothesis * explanation: 78% of users use only 1 source, 94% one or two sources * RK: still true for users with larger number of sources ##### Dispersion per user and per channel: Fig4a * more or less identical for news and opinions * direct: lowest dispersion, search: highest dispersion ##### Dispersion per individual polarity: Fig4b * most polarized individuals are also ones with highest dispersion ##### Does it mean that highly polarized individuals see opposite opinions? (Fig5) * test by ranking medias with l from left (0) to right (1) * define opposing partisan exposure o_i = min (l_i , 1-l_i) * fig5: percentage of exposure to opposite opinion articles, depending on the channel and on the user polarity * lower than 20% in all cases * weaker for opinion pieces than reports * lowest for most partisan users * conclusion: users read ideologically homogeneous outlets, and partisan users are in general exposed only to their side of the spectrum ### Discussion and conclusion ##### Overall * with social media and web search in general more segregation than with direct consumption * however, channels with more segregation are counter-intuitively related to a wider range of opinions * majority of online behaviors mimick reading habits: most users go to their favorite outlet (which are predominantly mainstream) ##### Limits * measure slant of the outlet, not of an article * focus only on consumption, not on the vote itself * no measure of amplifying effect of social medias or search engines

Question asked: how can you audit a recommender system if you don't have access to user-item interactions? Answer proposed: use a "recommendation graph" and simulate user behavior with a random walk with teleportation. Legitimate question, I am not completely convinced by the answer but it has some merits, in particular, simplicity. ### Introduction - to measure : diversity / segregation-polarization (not accuracy) - use the structure of an underlying network - 3 datasets, all movies RS : IMDB, Google Play, Netflix ; films have a genre in a list ##### Contributions : quantifying diversity - use a notion of graph: directed link from i to j if j is recommended on i page - measures based on films genre ; popularity based on the graph structure: in-degree, PageRank - segregation quantified with concentration and evenness (8: Chakraborti et al, 2017) ### Related work ##### diversity in RS - 9 : Nguyen et al, WWW 2014: CF impact on user behaviors - 10: Zhou et al, PNAS 2010 (Auralist) defines novelty - 11: Santini and Castells defines diversity et novelty with a fuzzy interpretation - 12: Vargas et Castells, RecSys 2011: novelty and diversity from a user perspective - 13: Lathia et al, SIGIR 2010: considers temporal aspects ##### on polarization dynamics - 20: DeGroot explanation from opinion modeling - 17: Dandekar et al, PNAS 2013 : polarizing effects of RS algorithms - two main schools of thought to explain polarization: either opinion is reinforced by interactions with like-minded people or people are exposed to opposite views then reject them (hence polarization ### Framework for auditing RS ##### Network construction : see above - possible to give weights to the links in tne network depending on item-item similarities, or based on the rank of j reco on i page - but overall different with literature: directed network and not based on similarity ##### User modeling : see above (RW with teleport), as we don't have access to navigation logs - then we consider distribution of types visited during the RW ##### Datasets : see above - general stats : see tab1 - collect by snowball sampling (from one node, then neighbors, then neighbors of neighbors... like a BFS) - to account for personalization effects, crawling from a unique IP adress - film genres: 15 for GP, 29 for Netflix and IMDB - compare distributions for 400 steps RW with no teleport (so, sort of random sampling): GP dominated by Action, IMDB more balanced ### Diversity in RS ##### existing measures - similarity between items computed with Jaccard coefficient => possible to compute usual measures (ILS (15), long-tail novelty (14), unexpectedness (23), source-list diversity(16)) - Table 2 : traditional measures on the datasets - observation : Netflix has greater source-list diversity, but IMDB more diverse according to other measures ##### new measures - assortativity by genre, by popularity (using as a proxy normalized centralities: in-degree, pagerank) => see Table III - contingency matrices: fraction of links from genre to genre (fig2); in general RS recommend from a genre to the same one + some specific relation between specific genres - equivalent for popularity: bins of popularity (bottom/middle/top) then count links from a bin to another (fig3); in general push toward long-tail, especially on IMDB ##### New measures based on RW - entropy of the genre distribution obtained - exploration when parameters vary (N = RW length, tp = teleportation probability, starting point) - fig4a : evol with t_p (small increase then plateau) - fig4b : évol with N (growth) - note that the RW is finite and we do not reach the steady state ##### Information segregation in RS * use measures in Chakraborty et al.(8) : evenness and concentration * evenness : to what extent a group is exposed uniformly to info units , it (1-Gini) with Gini computed on the genres consumed by the users of the group (1 ~ even consumption) * concentration : 1/2 . sum (fraction of films i consumed by the group).(fraction of the films consumed by the groups).(fraction of the films of genre i) ; if concentration is low what is consumed is close to what is proposed * results on fig5