{"id":"f085ac12-2d3f-4f30-82fe-30c87898705f","arxiv_id":"1908.08572","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Random walk and feature diffusion embeddings are community-based, while graphlet- and feature-based walk embeddings are role-based.","lead":"This paper separates two kinds of network embeddings: those that capture communities (close, dense groups) and those that capture structural roles (similar jobs, like hub or bridge). It proves that random walks and feature smoothing produce community embeddings, and gives a taxonomy of which methods preserve roles.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof that GCN/GraphSAGE yield community-based embeddings only covers linear smoothing; with nonlinearities, learned weights, and finite layers, the same mechanism can align structurally identical nodes across communities.","rationale":"The reader identified the low-conductance assumption as the weakest point. That is a real limitation of the random-walk argument, but the claim about feature propagation is more directly undercut by the gap between Theorem 4.1 and the actual GCN/GraphSAGE architectures. Theorem 4.1 is a statement about infinite iteration of a fixed linear operator; GCN/GraphSAGE use a small number of layers with nonlinearities and learned weights. The theorem cannot rule out that these models learn to map structurally identical local neighborhoods to the same embedding. For example, in a graph with two identical structures far apart, a 1-layer linear GCN with constant features assigns identical embeddings to the corresponding nodes; adding ReLU and training only expands this capacity. The paper's categorical statement that such methods are community-based therefore overreaches its proof. This justifies the reader's CONDITIONAL verdict and provides a concrete, falsifiable check: if a GCN trained on role labels fails to align the two bridge endpoints, the concern is mitigated; if it succeeds, the taxonomy needs revision. Agreement with the reader is partial because they flagged learned parameters only in the rationale, not as the weakest assumption.","tokens_in":37159,"tokens_out":13084,"duration_ms":144998,"concrete_test":"Use a barbell graph (two cliques of size 10 connected by a single bridge edge), assign random i.i.d. Gaussian features to all nodes, and predefine two roles: the two bridge endpoints are role A, all other nodes role B. Train a 2-layer GCN (Eq. 18) with ReLU and cross-entropy on a subset of labels (e.g., both role-A nodes and 20% of role-B nodes) and evaluate on the remaining nodes. Then compute the cosine similarity between the two role-A endpoints' output embeddings and between each endpoint and its own clique's role-B nodes. If the endpoint-endpoint similarity exceeds the endpoint-community similarity after training, the GCN has produced role-based embeddings that group structurally equivalent nodes across communities, contradicting the paper's classification.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4.2 classifies GCN and GraphSAGE as community-based based on the claim that feature diffusion is 'fundamentally tied to communities' and uses Theorem 4.1 as support. Theorem 4.1 applies to the linear smoothing operators (D^-1 A)^t and (D^-1/2 A D^-1/2)^t, proving convergence to a common vector (or degree-proportional vector) as t goes to infinity. It does not analyze GCN's actual layer (Eq. 18): X^(t) = sigma(D^-1/2 A D^-1/2 X^(t-1) W^(t)), which contains a nonlinearity sigma and learned per-layer weights W^(t), and is used for a small finite number of layers. The paper asserts that trainable parameters merely 'learn better community/proximity-based embeddings' without proof. This matters because with finite layers and shared weights, the propagation computes features of local neighborhoods; if two nodes have isomorphic k-hop neighborhoods and identical input features, they receive identical embeddings—precisely a role-based equivalence (Definition 14), not a community-based one. Thus the universal claim that these methods 'do not preserve structural roles' is not established by the supplied argument.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper distinguishes two complementary notions in network embeddings: community-based (proximity/density) embeddings and role-based (structural similarity) embeddings. It formalizes these notions, proposes feature/embedding-based role equivalences, and identifies general mechanisms that allegedly produce each type: random walks and feature propagation/diffusion are claimed to always yield community-based embeddings, while graphlets, feature-based walks, and feature-based matrix factorization are claimed to yield role-based embeddings. The main formal result is Theorem 4.1, showing that repeated Laplacian smoothing converges to identical or degree-proportional feature vectors. The paper also categorizes existing methods (DeepWalk, node2vec, LINE, GCN, GraphSAGE, etc.) into the two classes and discusses applications where each type is appropriate.","tokens_in":37447,"tokens_out":4190,"duration_ms":43868,"significance":"If the taxonomy were fully established, it would be valuable: practitioners could decide which embedding method to use based on the graph's community structure and the downstream task. The paper's conceptual distinction between communities and roles, and its emphasis on mechanisms rather than individual methods, are useful contributions. Theorem 4.1 is a correct and standard spectral result, and the paper's discussion of applications (homophily vs. heterophily, cross-network transfer, anomaly detection) is thoughtful. The main deficit is that the broad classification claims go beyond what the theorem and the surrounding arguments actually prove; several load-bearing assertions about specific method families are supported only by heuristic reasoning.","major_comments":[{"comment":"The universal claim that 'any walk-based embedding method that uses either implicit walks or explicit walks outputs community-based embeddings' is not established for graphs without strong community structure. The argument relies on Eq. (10), which bounds the probability of an ℓ-step walk staying inside a low-conductance community C. For graphs with high conductance or no clear communities, this bound is vacuous, and random walks may mix globally, so the embeddings need not be community-based. Since this claim is load-bearing for the paper's central taxonomy, it should be qualified to graphs with sufficiently low-conductance communities, or a separate proof must be provided for the general case.","section":"Section 4.1, after Eq. (10)"},{"comment":"Theorem 4.1 applies only to the linear smoothing operators (D^{-1}A)^t and (D^{-1/2}AD^{-1/2})^t. It does not cover GCN's actual layer, which includes a nonlinearity σ and learned per-layer weight matrices W^{(t)} (Eq. 18), nor the aggregation used by GraphSAGE. The paper's assertion that trainable parameters merely 'learn better community/proximity-based embeddings' is an extrapolation, not a consequence of the theorem. In fact, a finite-layer GCN with shared weights can map structurally identical nodes (i.e., nodes with isomorphic k-hop neighborhoods and identical input features) to identical embeddings, which would satisfy the role-based condition in Definition 14 rather than a community-based condition. Thus the classification of GCN and GraphSAGE as community-based is not proven by the supplied argument.","section":"Section 4.2, Theorem 4.1 and Eq. (18)"},{"comment":"Definition 14 defines role-based features partly by condition (2), which requires that the features are 'not correlated with graph proximity and/or density.' The paper later asserts that graphlet counts are role-based features without independently demonstrating that they satisfy this uncorrelatedness condition. In practice, graphlet counts are often correlated with degree, density, and community structure, so this condition is non-trivial and not automatic. Consequently, the claim that graphlet-based methods (Section 5.1) yield role-based embeddings rests in part on an assumption embedded in the definition rather than on an independent proof, which is a circularity concern for the taxonomy.","section":"Section 3.2, Definition 14"}],"minor_comments":[{"comment":"The header 'Structural eqivalence' contains a typo; it should read 'Structural equivalence.'","section":"Section 3.2, Definition 8"},{"comment":"The statement that Eq. (19) 'converges to identical feature vectors for all nodes' is imprecise: the limit matrix has identical rows, but the value of the common vector y depends on the initial features X and the graph structure. Explicitly stating that y is a linear function of X would avoid confusion.","section":"Theorem 4.1 statement"},{"comment":"The column headings in Table 3 are not fully aligned with the checkmarks; for example, the 'Features/attributes' column appears to be checked for several methods where it is unclear whether the method consumes node attributes as input. Clarifying the legend would improve readability.","section":"Table 3"},{"comment":"The claim that 'any matrix factorization method applied to A directly results in community-based embeddings' is overly broad and appeared without a formal proof in this work; it relies on a citation to prior work and would benefit from at least a brief justification or a pointer to the specific result.","section":"Section 4.1, after Eq. (12)"},{"comment":"Figure 3 is referenced in the text but does not appear in the body of the paper at the point of reference; the figure placement should be adjusted so that readers can view the graphlets and orbits when they are discussed.","section":"Section 5.1, Figure 3"}],"recommendation":"major_revision","confidential_remarks":"The paper is a conceptual/taxonomy contribution that is within the scope of TKDD. It leans heavily on the authors' own prior work (Rossi and Ahmed 2015; Ahmed et al. 2018) for key definitions and claims, which may be worth monitoring for citation balance. The main concern is that the central classification claims are more sweeping than the formal support; I would be comfortable with publication after the authors either prove the general claims under stated assumptions or appropriately qualify the conclusions, particularly regarding GCN/GraphSAGE and graphs without strong community structure."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This is the clearest written treatment I know of the roles-versus-communities distinction in graph embeddings. The taxonomy is genuinely useful: Table 2 alone is worth the download, and the formal embedding-based equivalences in Section 3 are a real service to a literature that routinely confuses structural equivalence with proximity. The applications section is practical and sensible. I would send this to review.\n\nThe main theorem, Theorem 4.1, is correct as stated: under connectedness and non-bipartiteness, repeated application of the random-walk or normalized Laplacian smoothing operators makes features converge to a common or degree-proportional vector. That is standard spectral theory, but it is properly stated and proved.\n\nThe soft spot is Section 4.2. The paper classifies GCN and GraphSAGE as community-based because their aggregation resembles Laplacian smoothing. The proof, however, only covers the linear infinite-time limit. A real GCN layer has a nonlinearity, learned weights, and a small finite number of layers. With finite layers and shared weights, two nodes with isomorphic local neighborhoods and identical input features receive identical embeddings. That is role-like, not community-like. The stress-test note lands: the claim that trainable parameters merely learn better community embeddings is asserted, not shown.\n\nThere is a second caveat, in Section 4.1. The argument that walk-based methods are community-based relies on the graph having good low-conductance communities (Equation 10). On graphs without strong community structure, walks mix more globally, and the same reasoning does not establish a community-based embedding. This makes the universal claims conditional, not false.\n\nOne circularity is worth noting but minor: Definition 14 builds \"not correlated with proximity\" into feature-based structural similarity, so the later claim that graphlet features are role-based is partly true by construction. That is a reasonable convention, but it is a convention, not an empirical discovery.\n\nThe citation pattern is fine. The heavy reliance on Rossi and Ahmed (2015) is natural because this paper extends that framework; it is not a flaw in itself.\n\nBottom line: this paper deserves a serious referee, and I would ask for revision that makes Section 4.2 explicitly finite-depth and conditional, acknowledging that trained GNNs can learn role-like functions. The taxonomy will be cited and used regardless.","headline":"A genuinely useful taxonomy of community- vs role-based embeddings, with a correct but narrow theorem that Section 4.2 over-extends to trained GNNs.","tokens_in":37903,"tokens_out":2207,"would_cite":true,"duration_ms":27379,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Walk-based graph embeddings capture communities, not structural roles.","keywords":["role-based structural embeddings","community-based embeddings","proximity","structural similarity","random walks","feature diffusion","graphlets","network representation learning"],"falsifier":"On a graph formed from two identical dense clusters joined by one edge, train an explicit-walk embedding such as DeepWalk or node2vec and measure the distance between nodes that occupy the same structural position in the two clusters. The paper's claim predicts those role-aligned cross-cluster pairs are no closer than arbitrary cross-cluster pairs because the walks rarely cross the bridge; if they come out closer than same-cluster non-role pairs, the community-based conclusion is contradicted.","tokens_in":37028,"feed_emoji":"🕸","tokens_out":9811,"duration_ms":90439,"temperature":0.7,"pith_summary":"Networks can be organized in two fundamentally different ways: by community, where nodes are grouped because they are close and densely interconnected, or by structural role, where nodes are grouped because their local wiring is similar even when the nodes are far apart. This paper argues that the mechanisms behind most popular node-embedding methods, random walks and feature propagation, inherently produce community-based embeddings rather than role-based ones. It proves that repeated Laplacian smoothing drives feature vectors of nodes in the same community to become identical or degree-proportional, and that walks on a low-conductance graph almost never leave their starting community. The consequence is that methods such as DeepWalk, node2vec, LINE, GCN, and GraphSAGE should be understood as proximity embeddings, while role-based structure requires graphlet and motif features, feature-based walks, or matrix factorization over structural features.","feed_headline":"Proven: walk-based embeddings capture communities, not roles","feed_subtitle":"New proof: random-walk and feature-diffusion methods such as DeepWalk and GCN cannot preserve structural roles.","key_machinery":"The load-bearing object is Theorem 4.1, the Laplacian-smoothing convergence theorem: for a connected non-bipartite graph, $\\lim_{t\\to\\infty}(D^{-1}A)^t X = \\mathbf{1}y^{\\top}$ and $\\lim_{t\\to\\infty}(D^{-1/2}AD^{-1/2})^t X = D^{-1/2}\\mathbf{1}y^{\\top}$. Together with the conductance bound that an $\\ell$-step walk stays in a low-conductance set $C$ with probability at least $1-\\ell\\Phi(C)/2$, this theorem converts the intuition that walks and diffusions stay inside communities into the paper's classification claim. It also marks the escape hatch: graphlet and motif features and feature-based walks are role-based precisely because they avoid smoothing raw node-id proximity.","core_discovery":"The paper's central claim is that any embedding method built on implicit walks (counts of walks between nodes) or explicit walks (sampled sequences of node ids) outputs community-based, proximity-driven embeddings, and so does any method built on feature propagation over the graph. For explicit walks, the argument is quantitative: in a graph with good communities, an $\\ell$-step random walk stays inside its starting community with probability at least $1-\\ell\\Phi(C)/2$, so the contexts a walk-based model sees are dominated by same-community nodes. For propagation, Theorem 4.1 shows that repeatedly applying the smoothing operators $D^{-1}A$ or $D^{-1/2}AD^{-1/2}$ to any feature matrix $X$ drives all node vectors to a common limit, identical vectors in the first case and degree-proportional vectors in the second, meaning nodes in the same community become indistinguishable. The paper further argues that claims that such methods preserve structural equivalence or regular equivalence are not well-posed, because those equivalences are defined on the graph itself, not on embedding vectors; role-based embeddings require structural features such as graphlets, feature-based walks, or factorization of a structural feature matrix.","pith_inferences":["An inference I draw beyond the paper: any method whose input is a function of the adjacency matrix, including attention-based message passing without structural features, likely inherits the same community bias, because the same confinement argument applies to its diffusion.","The theorem is asymptotic, so finite-depth models on graphs without clear community structure may sit between roles and communities; a testable prediction is that their behavior degrades exactly when conductance stops being small.","The mechanism test suggests a practical benchmark: role-aligned nodes in disconnected identical components should be separated by walk-based embeddings but aligned by graphlet-based role embeddings; applying this benchmark to new methods would reveal which family they belong to."],"forward_implications":["DeepWalk, node2vec, LINE, and GraRep should be described and used as proximity or community embeddings; their strong results on homophily-driven node classification reflect that mechanism.","GCN, GraphSAGE, and other feature-propagation models are community-based and cannot by themselves serve as structural-role embeddings for transfer across networks.","Claims that an embedding method preserves structural or regular equivalence are not well-posed, because those equivalences are defined on the original graph, not on embedding vectors.","Role-based embeddings are the appropriate tool for across-network classification, weak-homophily or heterophily settings, long-range link prediction, network alignment, and structural anomaly detection.","A new embedding method can be classified by its mechanism: raw walks or raw diffusion makes it community-based, while graphlets, feature-based walks, or structural-feature matrix factorization make it role-based."],"supporting_citations":[{"why":"Defines DeepWalk, the canonical explicit-walk embedding method the paper classifies as community-based.","marker":"[Perozzi et al. 2014]"},{"why":"node2vec, the main target of the misconception argument because it claims to preserve both proximity and structural equivalence.","marker":"[Grover and Leskovec 2016]"},{"why":"GCN, the representative feature-propagation method whose Laplacian smoothing is shown by Theorem 4.1 to be community-based.","marker":"[Kipf and Welling 2017]"},{"why":"Supplies the conductance bound that keeps a random walk inside a low-conductance community.","marker":"[Spielman and Teng 2013]"},{"why":"Provides the spectral-graph facts about Laplacian eigenvalues used in the proof of Theorem 4.1.","marker":"[Chung 1997]"},{"why":"Defines feature-based roles and role discovery, the conceptual basis for the paper's role-based embedding mechanisms.","marker":"[Rossi and Ahmed 2015]"},{"why":"Introduces feature-based walks and the formal link between random walks and communities used in Section 4.1.","marker":"[Ahmed et al. 2018]"},{"why":"RolX, the representative feature-based matrix-factorization role method used to illustrate the role-based mechanism.","marker":"[Henderson et al. 2012]"}],"fun_headline_variants":["Walk-based embeddings capture communities, not roles","Proof: random walks yield community embeddings, not role-based","Misconception clarified: walks preserve proximity, not roles","Role-based embeddings need structural features, not walks"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument assumes the graph is made of genuinely dense clusters with few links between them, so that a random walk or diffusion almost never crosses from one cluster to another; if that assumption fails, the proof that walk-based embeddings are community-based does not go through.","fun_headline_variants_meta":{"raw":{"variants":["Walk-based embeddings capture communities, not roles","Proof: random walks yield community embeddings, not role-based","Misconception clarified: walks preserve proximity, not roles","Role-based embeddings need structural features, not walks"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000243,"raw_usage":{"total_tokens":1568,"prompt_tokens":1026,"completion_tokens":542,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":642,"completion_tokens_details":{"reasoning_tokens":480}},"tokens_in":642,"tokens_out":542,"duration_ms":5805,"temperature":1.0,"reasoning_tokens":480,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:34:55.813624+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a graph formed from two identical dense clusters joined by one edge, train an explicit-walk embedding such as DeepWalk or node2vec and measure the distance between nodes that occupy the same structural position in the two clusters. The paper's claim predicts those role-aligned cross-cluster pairs are no closer than arbitrary cross-cluster pairs because the walks rarely cross the bridge; if they come out closer than same-cluster non-role pairs, the community-based conclusion is contradicted.","supporting_citations":[],"review_version":1}