Từ điển

Thước đo tỉ lệ một node nằm trên đường đi ngắn nhất giữa các cặp node khác. Betweenness cao = cầu nối giữa các cộng đồng. Một loại quyền lực khác hẳn với degree cao.

Được Linton Freeman chính thức hóa năm 1977. Trong khi degree centrality đo node có bao nhiêu hàng xóm, betweenness centrality đo bao nhiêu cặp node khác cần đi qua node này để đến được nhau. Một node có thể có degree thấp nhưng betweenness rất cao nếu nó là cầu nối giữa hai cộng đồng vốn không liên thông — và mất node đó sẽ phân mảnh luồng thông tin ngay cả khi không mất hub nào. Medici nổi lên ở Florence thế kỷ 15 không phải vì họ là ngân hàng lớn nhất mà vì họ ngồi ở trung tâm betweenness của mạng thương gia và chính trị (Padgett và Ansell, 1993). Cùng thước đo này giải thích tại sao "weak ties" (Granovetter, 1973) mang đến cho bạn cơ hội việc làm mà bạn thân không thể: chúng là cầu nối giữa các cộng đồng.

Tìm các nhóm trong một mạng lưới từ chính cấu trúc kết nối, không có định nghĩa nhóm cho trước. Sức mạnh và cạm bẫy là cùng một sự thật: thuật toán luôn trả về một cách chia, kể cả trên nhiễu thuần.

Phân loại truyền thống đi từ định nghĩa đến phần tử: định nghĩa nhóm trước, gán phần tử vào sau. Community detection đi ngược, để cấu trúc kết nối tự lộ nhóm, rồi con người đi tìm nghĩa cho cái đã lộ. Vì không có định nghĩa trước, không gì ràng buộc thuật toán phải trả lời "ở đây không có nhóm nào"; nó luôn trả về một cách chia, và điều đó đảo chiều gánh nặng chứng minh về phía người dùng. Quy trình có trách nhiệm là vòng nghi ngờ ba bước sau mỗi lần chạy: quét tham số resolution và tin vùng plateau nơi cấu trúc đứng yên, đo độ ổn định qua nhiều lần chạy với seed khác nhau và khai báo vùng biên là vùng mờ, và đặt tên từng cụm sống sót cùng người hiểu domain. Một cụm không ai đặt tên nổi sau nỗ lực tử tế là triệu chứng của resolution sai, edge sai, hoặc nhiễu. Khác với clustering trên thuộc tính (k-means và họ hàng): giống nhau là quan hệ giữa thuộc tính của từng điểm, thuộc về nhau là quan hệ trong cấu trúc kết nối giữa các điểm, và hai câu hỏi có thể chia cùng một bộ dữ liệu theo hai đường hoàn toàn khác.

Phả hệ của dữ liệu: một đồ thị ghi lại job nào đọc bảng nào và ghi vào bảng nào, lần từ nguồn đến dashboard. Phân tích impact đi xuôi dòng; câu hỏi truy nguyên đi ngược dòng.

Một lineage graph ghi lại các quan hệ đọc-từ và ghi-vào giữa dataset, job, và báo cáo trên một nền tảng dữ liệu. Hai câu hỏi định nghĩa nó đều là reachability: xuôi dòng ('bảng nguồn này đổi schema giữa đêm; dashboard, báo cáo, model nào đang sai theo mà chưa ai biết?') và ngược dòng ('con số trên dashboard ban giám đốc trông đáng ngờ; nó được tính từ những cột và phép biến đổi nào?'). Điểm phân biệt lineage với các dependency graph được khai báo như của hệ build là không ai khai báo nó: dữ liệu chảy qua hàng nghìn pipeline, SQL viết tay, notebook, và những job cron bị quên, nên các nền tảng như Databook của Uber và hệ sinh thái OpenLineage chọn khai quật đồ thị bằng cách parse query log và metadata của job. Hệ quả là mỗi edge mang theo một vấn đề độ tin: edge suy ra từ parse có thể thiếu (SQL sinh động lúc runtime, job ngoài hệ thống thu thập) hoặc thừa, nên một lineage graph khai quật luôn là phép xấp xỉ, và các hệ trưởng thành công bố độ phủ thay vì giả vờ đầy đủ.

Bài toán xác định những mention nào trong corpus trỏ về cùng một thực thể trong thế giới thật, rồi gộp chúng về một danh tính canonical duy nhất. Điều kiện tiên quyết để bất kỳ metric nào trên graph có nghĩa.

Entity resolution (còn gọi là record linkage hoặc deduplication) có cấu trúc là một graph problem: thu thập tất cả mention, tính similarity từng cặp dựa trên tên, context và loại entity, rồi cluster những mention đủ tương đồng về cùng một node canonical. Chi phí của việc bỏ qua bước này là ẩn, một người có tám mươi connections thật bị split thành ba mention-node, mỗi node chỉ thấy khoảng hai mươi lăm đến ba mươi connections, và không node nào được xếp là hub trong graph. Community detection tìm community sai vì boundary giả do entity split tạo ra, và centrality rankings loại người đó ra khỏi mọi danh sách degree cao. Không có lỗi nào hiện ra từ ngoài graph nếu không có ground truth về entity nào là canonical. Entity resolution phải chạy sau extraction và trước mọi bước phân tích, không phải tính năng nâng cao cho version 2.0 mà là điều kiện cần để bất kỳ metric nào trên graph có nghĩa.

Khi một con số đo lường trở thành mục tiêu, nó ngừng là con số đo lường tốt. Bất kỳ chỉ số nào được dùng để kiểm soát đều bị biến dạng bởi chính hành động kiểm soát đó.

Ban đầu được Charles Goodhart phát biểu trong "Problems of Monetary Management" (1975) trong bối cảnh chính sách tiền tệ. Phiên bản được trích dẫn rộng rãi hơn — "When a measure becomes a target, it ceases to be a good measure" — là paraphrase của Marilyn Strathern năm 1997. Quy luật này mô tả một động lực gần như phổ quát: khi một chỉ số đại diện được nâng lên thành mục tiêu, những người tham gia bắt đầu tối ưu hóa cho chỉ số đó thay vì cho thứ nó đại diện. Chỉ số cải thiện, thực tế không đổi hoặc tệ hơn. Áp dụng vào phần mềm: khi velocity trở thành KPI, developer không học cách làm việc nhanh hơn mà học cách estimate cao hơn.

Tính chất lưu trữ trong đó mỗi node giữ tham chiếu vật lý trực tiếp đến hàng xóm của nó, nên đi qua một cạnh tốn như nhau bất kể cả đồ thị lớn đến đâu. Luận điểm kiến trúc trung tâm của các graph database thuần.

Thuật ngữ được Neo4j phổ biến để gọi tên thứ làm một graph store 'thuần' khác với một relational engine trả lời cùng câu hỏi. Trong relational database, đi thêm một bước quan hệ nghĩa là một lần join, tức là tra một index toàn cục có chi phí lớn lên theo kích thước của cả bảng liên kết. Với index-free adjacency, hàng xóm của một node được truy cập bằng cách lần theo con trỏ từ chính node đó, nên chi phí một bước tỷ lệ với degree cục bộ, không phải với kích thước của thế giới. Đây là lý do các traversal sâu, độ sâu không biết trước, là địa hình mà graph store thắng áp đảo. Luận điểm này cũng gây tranh cãi: cái giá được trả ở chỗ khác, ở write amplification, ở sự cứng nhắc của storage layout, và ở việc mất đi bốn mươi năm trưởng thành của query optimizer quan hệ cho mọi thứ không phải traversal.

Xã hội thành tích — thuật ngữ của Byung-Chul Han cho một trật tự xã hội mà áp lực lớn nhất đặt lên cá nhân không đến từ bên ngoài mà từ chính bên trong: tự tối ưu hóa và tự kiệt sức.

Từ Müdigkeitsgesellschaft (Xã Hội Kiệt Sức, 2010) của Han. Trong Leistungsgesellschaft, chủ thể không còn là chủ thể phục tùng của xã hội kỷ luật mà là chủ thể thành tích — người tin rằng mình đang tự do trong khi thực ra đang tự bóc lột chính mình. Kiệt sức không phải là thất bại của hệ thống, mà là triệu chứng của sự thành công của nó.

Con số chấm điểm cho một cách chia mạng lưới: edge bên trong các cụm dày hơn bao nhiêu so với kỳ vọng nếu cũng từng ấy edge được rải ngẫu nhiên. Vế so với ngẫu nhiên là vế giữ cho định nghĩa khỏi vô nghĩa.

Cách làm chặt phổ biến nhất cho chữ "thuộc về nhau" trong community detection. Một cách chia tốt là cách chia mà edge bên trong từng cụm dày hơn hẳn mức kỳ vọng nếu cũng từng ấy edge được rải ngẫu nhiên giữa cũng từng ấy node; không so với ngẫu nhiên thì mọi đám đông đều trông như cụm, kể cả đám đông sinh từ tung xúc xắc. Tìm chính xác cách chia điểm cao nhất là bất khả thi (số cách chia bùng nổ), nên các thuật toán thực dụng đi tham lam: Louvain (Blondel et al., 2008) cho mỗi node thử chuyển sang cụm hàng xóm, giữ nước đi làm điểm chung tăng nhiều nhất, rồi nén mỗi cụm thành một node lớn và lặp lại ở tầng trên, rẻ đến mức chạy được trên graph hàng trăm triệu edge bằng một máy. Hai vết nứt phải biết: resolution limit (Fortunato & Barthélemy, 2007), modularity thuần có cỡ cụm ưa thích phụ thuộc cỡ toàn graph nên cụm nhỏ có thật bị nuốt, vì vậy các cài đặt cho tham số resolution, nghĩa là số cụm một phần là lựa chọn của người hỏi chứ không phải hằng số của dữ liệu; và Louvain có thể trả về cụm rời rạc bên trong, khuyết điểm dẫn đến Leiden (Traag, Waltman & van Eck, 2019), bảo đảm cụm liên thông và nhanh hơn.

Quyết định về việc hệ thống gồm những loại thứ gì và chúng được quan hệ với nhau ra sao: khái niệm nào là thực thể, khái niệm nào là thuộc tính, quan hệ nào được phép tồn tại. Các tranh luận khó nhất trong knowledge graph là tranh luận ontology, không phải tranh luận kỹ thuật.

Mượn từ triết học (môn nghiên cứu về cái tồn tại) vào biểu diễn tri thức, nơi ontology là bản đặc tả tường minh các khái niệm và quan hệ của một domain. Trong thực hành kỹ thuật, nó hiện ra dưới dạng những câu hỏi nghe nhỏ mà chia đôi căn phòng: thành phố là node hay là property của listing? Mỗi đáp án mở và đóng cả những họ truy vấn. Là property, thành phố là một chuỗi ký tự không có hàng xóm; là node, nó nối được với vùng, mùa, và các thành phố tương đồng, đổi lại cái giá entity resolution (mọi cách viết của 'Tokyo' phải về một danh tính) và chi phí curate vĩnh viễn. Tính chất then chốt của quyết định ontology là bản thân domain không chứa câu trả lời; câu trả lời đến từ việc sản phẩm cần trả lời loại câu hỏi nào và trong chân trời thời gian nào. Đội có bộ câu hỏi ổn định, biết trước, đúc được ontology tối giản cứng; đội có không gian câu hỏi còn đang nở thì mua sự rộng rãi và trả bằng curate.

Một độ đo centrality thuộc họ eigenvector: một trang quan trọng nếu được các trang quan trọng trỏ tới, định nghĩa đệ quy. Điểm số bằng xác suất một người lướt web ngẫu nhiên đi theo link đủ lâu sẽ đang đứng ở trang đó.

Được Sergey Brin và Lawrence Page giới thiệu trong "The Anatomy of a Large-Scale Hypertextual Web Search Engine" (1998). Bước nhảy modeling là đọc mỗi hyperlink như một phiếu bầu, rồi từ chối đếm phiếu bình đẳng: phiếu của trang quan trọng nặng hơn, và sự quan trọng của trang bầu lại được định nghĩa bằng đúng quy tắc đó, đệ quy. Sự luẩn quẩn bề ngoài có lời giải hội tụ, trở nên trực quan qua mô hình người lướt web ngẫu nhiên: tưởng tượng một người đi theo link mãi, thỉnh thoảng nhảy sang một trang bất kỳ (xác suất nhảy về sau quen gọi là damping factor); điểm PageRank của một trang là xác suất bắt gặp người đó đang đứng ở trang ấy sau đủ lâu. PageRank thắng phép đếm in-degree thuần vì nó đắt hơn để làm giả, muốn được trang quan trọng trỏ tới tốn kém hơn nhiều so với tạo nghìn trang rác, và cũng chính vì thắng mà nó trở thành mục tiêu của cả một nền kinh tế link farm, một ví dụ giáo khoa của Goodhart’s law áp vào centrality.

Metadata gắn vào từng edge ghi lại nguồn gốc của nó: tài liệu nguồn, đoạn văn, timestamp extraction, version model và prompt. Ranh giới giữa graph có thể debug và graph phải rebuild từ đầu để điều tra.

Provenance trong graph được LLM extract là metadata per-edge: định danh tài liệu, đoạn văn hoặc chunk cụ thể, timestamp của lần extraction, và version model cùng prompt đã tạo ra claim đó. Giá trị của nó không mang tính nghi lễ, không có provenance thì không có đường debug từ câu trả lời sai về edge gây ra lỗi, và điều tra đòi phải re-extract toàn bộ graph và so sánh. Khi có provenance, con đường là: câu trả lời sai, node sai, edge sai, tài liệu nguồn, câu cụ thể. Quyết định thiết kế là lưu ở đâu: inline trong graph database (query nhanh, chi phí lưu trữ ở hàng triệu edge) hay trong separate store dùng edge ID làm key (chuẩn hoá hơn, join chậm hơn). Không có lựa chọn nào đúng tuyệt đối, lựa chọn duy nhất không có là không lưu. Tác dụng bậc hai quan trọng không kém: provenance là eval infrastructure. Khi không có benchmark chuẩn cho LLM-extracted graph quality, khả năng trace từng edge về tài liệu nguồn là cơ chế duy nhất để debug có mục tiêu khi downstream trả lời sai.

Câu hỏi một node có đến được từ một node khác hay không, trực tiếp hoặc qua bất kỳ số trung gian nào. Là problem class phổ biến nhất và bị đánh giá thấp nhất trong các hệ thống production.

Về hình thức, node B reachable từ node A nếu tồn tại một đường đi có hướng từ A đến B; tính câu trả lời đầy đủ cho mọi cặp là transitive closure của đồ thị. Điều làm reachability thú vị trong thực tế không phải thuật toán (BFS hay DFS là đủ) mà là tần suất nó ẩn trong các requirement được phát biểu không có một từ vựng graph nào: 'rốt cuộc ai đọc được file này' (thừa kế phân quyền), 'đổi API này thì những service nào vỡ' (phân tích tác động, đi ngược chiều mũi tên phụ thuộc), 'bảng nguồn này sai thì những dashboard nào sai theo' (data lineage), 'ai liên hệ với tài khoản gian lận này trong vòng N bước'. Cái bẫy lặp lại là độ sâu traversal thuộc về dữ liệu chứ không phải một hằng số biết trước lúc viết query, đúng tính chất mà ngôn ngữ truy vấn quan hệ không có cách phát biểu tự nhiên.

Một common table expression trong SQL tự tham chiếu chính nó, cho phép query lặp lại một bước (như lần theo liên kết thêm một tầng) cho đến khi không còn dòng mới. Là cách SQL phát biểu một traversal có độ sâu không biết trước lúc viết query.

Được chuẩn hoá trong SQL:1999 dưới dạng WITH RECURSIVE, một recursive CTE gồm hai phần: phần anchor sinh các dòng khởi đầu, và phần đệ quy join ngược lại kết quả trước đó của chính CTE, chạy lặp cho đến khi đạt fixpoint. Đây là cơ chế duy nhất trong SQL chuẩn cho các câu hỏi kiểu 'mọi hậu duệ của node này' hay 'mọi thứ đến được trong vòng N bước' khi N là tham số hoặc không chặn, và thực tế gần như luôn cần một điều kiện chống lặp tường minh vì dữ liệu liên kết ngoài đời luôn có vòng. Cấu trúc này trung thực nhưng gượng: mỗi vòng lặp vẫn là một lần join toàn cục với cả bảng liên kết, nên chi phí lớn lên theo kích thước bảng thay vì kích thước vùng lân cận đang được khám phá. Một recursive CTE bốn mươi dòng trả lời một câu hỏi business một dòng là một trong những dấu hiệu đáng tin nhất rằng một graph problem đang được giải bằng một cách biểu diễn không sinh ra cho nó.

Biến một quan hệ thành một thực thể độc lập: đường kẻ giữa hai chấm trở thành một chấm. Bắt buộc xảy ra khi quan hệ cần thuộc tính riêng trong truy vấn, cần được tham chiếu, hoặc cần tham gia vào quan hệ khác.

Thuật ngữ có gốc từ biểu diễn tri thức, xuất hiện tường minh trong đặc tả RDF của W3C (RDF reification biến một statement thành đối tượng để mô tả về chính statement đó); trong data modeling kinh điển, họ hàng gần của nó là associative entity trong mô hình ER. Bài kiểm tra thực dụng có ba tín hiệu: quan hệ mang thuộc tính tham gia vào điều kiện truy vấn (giờ cất cánh của chuyến bay nằm trong mệnh đề lọc của mọi câu hỏi nối chuyến, không phải trang trí), quan hệ cần được tham chiếu đích danh ('đổi khách sang chuyến muộn hơn' đòi mỗi chuyến có danh tính riêng), hoặc quan hệ tham gia vào quan hệ khác (ràng buộc nối chuyến giữa hai chuyến bay là một quan hệ mà hai đầu là hai quan hệ, và không hệ hình thức lành mạnh nào cho edge trỏ vào edge). Khớp một tín hiệu là quan hệ đã ứng cử vào ghế node. Cái bẫy sâu hơn là reification không có điểm dừng tự nhiên: mọi quan hệ đều thành node được, mọi thuộc tính đều tách thành quan hệ trỏ đến node giá trị được, nên mô hình nào cũng 'làm giàu' thêm được. Dừng ở đâu do bộ câu hỏi mà mô hình phải trả lời quyết định, không do lý thuyết.

Thời gian được giải phóng khỏi mọi nghĩa vụ — điều kiện mà việc học vốn được hiểu là diễn ra trong đó. Gốc của từ 'school' trong tiếng Anh.

Từ tiếng Hy Lạp σχολή. Skholē không phải sự nhàn rỗi đơn thuần; đó là thời gian được giải phóng khỏi sự tất yếu, để con người có thể theo đuổi điều gì đó vì chính bản thân nó, không phải vì kết quả. Aristotle lập luận rằng chỉ qua skholē con người mới có thể phát triển những năng lực cao nhất. 'School' hiện đại vẫn giữ từ nhưng đảo ngược tinh thần của nó.

Thuật ngữ của Aristotle cho sự chiêm nghiệm thuần túy — hoạt động được thực hiện như mục đích trong chính nó, không phải phương tiện cho điều gì khác. Aristotle coi đây là hình thức sống cao nhất của con người.

Từ tiếng Hy Lạp θεωρία. Trong Nicomachean Ethics, Aristotle phân biệt giữa hoạt động làm vì mục đích khác và hoạt động hoàn chỉnh trong chính nó. Theoria — sự vận dụng trí tuệ vào những đối tượng cao nhất — là loại sau. Nó không tạo ra thứ gì ngoài chính nó, và chính điều đó làm cho nó là biểu hiện đầy đủ nhất của con người. Khái niệm này gắn liền với skholē: chỉ khi có thời gian được giải phóng khỏi sự cần thiết, theoria mới trở nên khả thi.

Câu trả lời được tính sẵn cho mọi câu hỏi reachability trên một đồ thị: với mỗi node, tập đầy đủ các node đến được từ nó. Mua tốc độ đọc mili giây bằng cái giá cập nhật lại mỗi lần đồ thị thay đổi.

Về hình thức, bao đóng bắc cầu của đồ thị có hướng G là đồ thị G* chứa cạnh (u, v) bất cứ khi nào v đến được từ u trong G. Trong thực hành, nó là một cực của trade-off vận hành trung tâm trong các hệ reachability: materialize (tính sẵn và lưu, trả lời trong mili giây, trả giá ở mỗi lần đồ thị đổi) đối lại tính on-demand (luôn tươi, trả giá theo độ sâu traversal ở mỗi lần hỏi). Không bên nào đúng tuyệt đối; con số quyết định là tần suất hỏi chia tần suất đổi. Hệ build bị hỏi ở mỗi lần compile bởi hàng nghìn kỹ sư nghiêng hẳn về materialize; câu query audit mỗi quý một lần nên ở lại on-demand. Cách hỏng kinh điển là materialize bằng nửa dữ kiện: mê tốc độ đọc mà quên rằng chi phí thật không nằm ở lần tính đầu tiên mà ở mọi lần cập nhật về sau, kéo dài chừng nào hệ thống còn sống. Topological sort, nhìn từ góc này, là một dạng materialize đặc biệt: thứ tự build tính sẵn là câu trả lời đóng gói cho cả họ câu hỏi cái-gì-phải-xong-trước.